We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms whic...
详细信息
We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small circuits attempting to compute hard functions. As our main result, we prove that if it is possible to find efficiently, in a particular interactive way, errors of many p-size circuits attempting to solve hard problems, then p-size circuits can be PAC learned over the uniform distribution with membership queries by circuits of subexponential size. The opposite implication holds as well. This provides a new characterization of learning algorithms and the natural proofs barrier of Razborov and Rudich. The proof is based on a method of reconstructing Nisan-Wigderson generators introduced by Kraj & iacute;& ccaron;ek (2010) and used to analyze complexity of circuit lower bounds in bounded arithmetic. An interesting consequence of known constructions of learning algorithms from circuit lower bounds is a learning speedup of Oliveira and Santhanam (2016). We present an alternative proof of this phenomenon and discuss its potential to advance the program of hardness magnification.
This study presents a survey on the most recent learning approaches and algorithms that are related to fuzzy cognitive maps (FCMs). FCMs are cognition fuzzy influence graphs, which are based on fuzzy logic and neural ...
详细信息
This study presents a survey on the most recent learning approaches and algorithms that are related to fuzzy cognitive maps (FCMs). FCMs are cognition fuzzy influence graphs, which are based on fuzzy logic and neural network aspects that inherit their main advantages. They gained momentum due to their dynamic characteristics and learning capabilities. These capabilities make them essential for modeling and decision-making tasks as they improve the performance of these tasks. An efficient number of learning algorithms for FCMs, by modifying the FCM weight matrix, have been developed in order to update the initial knowledge of human experts and/or include any knowledge from historical data in order to produce learned weights. The proposed learning techniques have mainly been concentrated on three directions: on the production of weight matrices on the basis of historical data, on adaptation of the cause-effect relationships of the FCM on the basis of experts' intervention, and on the production of weight matrices by combining experts' knowledge and data. The learning techniques could be categorized into three groups on the basis of the learning paradigm: Hebbian-based, population-based, and hybrid, which subsequently combine the main aspects of Hebbian-based- and population-based-type learning algorithms. These types of learning algorithms are the most efficient and widely used to train the FCMs, according to the existing literature. A survey on recent advances on learning methodologies and algorithms for FCMs that present their dynamic capabilities and application characteristics in diverse scientific fields is established here.
It is shown how learning algorithms are used to grow shared multicast trees, in order to minimise some performance index such as the average received packet delay or path length. In particular, automata are used to se...
详细信息
It is shown how learning algorithms are used to grow shared multicast trees, in order to minimise some performance index such as the average received packet delay or path length. In particular, automata are used to select a core to send a join request to in a dynamic membership environment. The motivation is to improve the performance of shared multicast trees while retaining their attractive scaling properties. It is shown that in the single source (single group) case, automata converge to the optimal shortest path tree solution. For multiple sources, automata reach a 'good' compromise solution. However, automata are most useful in heterogeneous scenarios where the resources are unevenly distributed, a situation which could easily arise due to consumption of resources by multiple priority traffics in future integrated-services networks.
The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategi...
详细信息
The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.
Negotiator often rely on learning an opponent's behavior and on then using the knowledge gained to arrive at a better deal. However, in an electronic negotiation setting in which the parties involved are often unk...
详细信息
The aim of this article is to investigate:a mechanical description of learning. A framework for local and simple learning algorithms based on interpreting a neural network as a set of configuration constraints ia prop...
详细信息
The aim of this article is to investigate:a mechanical description of learning. A framework for local and simple learning algorithms based on interpreting a neural network as a set of configuration constraints ia proposed. For any architectural design and learning task, unsupervised and supervised algorithms can be derived, optionally using unconstrained and hidden neurons. Unlike algorithms based on the gradient in weight space, the proposed tangential correlation (TC) algorithms move along the gradient in state space. This results in optimal scaling properties and simple expressions for the weight updates. The number of synapses is much larger than the number of neurons. A constraint for neural states does not impose a unique constraint for synaptic weights. Which weights to assign credit to can be selected from a parametrization of all weight changes equivalently satisfying the state constraints. At the heart of the parametrization are minimal weight changes. Two supervised algorithms (differing by their parametrizations) operating on a three-layer perceptron are compared with standard backpropagation. The successful training of fixed points of recurrent networks is demonstrated. The unsupervised learning of oscillations with variable frequencies is performed on standard and more sophisticated recurrent networks. The results presented here can be useful both for the analysis and for the synthesis of learning algorithms.
One difficulty for quaternion neural networks (QNNs) is that quaternion nonlinear activation functions are usually non-analytic and thus quaternion derivatives cannot be used. In this paper, we derive the quaternion g...
详细信息
One difficulty for quaternion neural networks (QNNs) is that quaternion nonlinear activation functions are usually non-analytic and thus quaternion derivatives cannot be used. In this paper, we derive the quaternion gradient descent, approximated quaternion Gauss-Newton and quaternion Levenberg-Marquardt algorithms for feedforward QNNs based on the GHR calculus, which is suitable for analytic and non-analytic quaternion functions. Meanwhile, we solve a widely linear quaternion least squares problem in the derivation of quaternion Gauss-Newton algorithm, which is more general than the usual least squares probZlem. A rigorous analysis of the convergence of the proposed algorithms is provided. Simulations on the prediction of benchmark signals support the approach.
The objective of this paper is to present an application of learning algorithms to the detection of anomalies in SOA system. As it was not possible to inject errors into the "real" SOA system and to analyze ...
详细信息
ISBN:
(纸本)9783642409257;9783642409240
The objective of this paper is to present an application of learning algorithms to the detection of anomalies in SOA system. As it was not possible to inject errors into the "real" SOA system and to analyze the effect of these errors, a special model of SOA system was designed and implemented. In this system several anomalies were introduced and the effectiveness of algorithms in detecting them were measured. The results of experiments can be used to select efficient algorithm for anomaly detection. Two algorithms: K-means clustering and Kohonen networks were used to detect the unused functionalities and the results of this experiment are discussed.
A fundamental assumption for any machine learning task is to have training and test data instances drawn from the same distribution while having a sufficiently large number of training instances. In many practical set...
详细信息
ISBN:
(纸本)9783642052231
A fundamental assumption for any machine learning task is to have training and test data instances drawn from the same distribution while having a sufficiently large number of training instances. In many practical settings, this ideal assumption is invalidated as the labeled training instances are scarce and there is a high cost associated with labeling them. On the other hand, we might have access to plenty of labeled data from a different domain, which can provide useful information for the present domain. In this paper, we discuss adaptive learning techniques to address this specific problem: learning with little training data from the same distribution along with a large pool of data from a different distribution. An underlying theme of our work is to identify Situations when the auxiliary data is likely to help in training with the primary data. We propose two algorithms for the domain adaptation task: dataset reweighting and Subset selection. We present theoretical analysis of behavior of the algorithms based on the concept of domain similarity, which we use to formulate error bounds for our algorithms. We also present an experimental evaluation of our techniques on data from a real world question answering system.
There have been proposed many learning algorithms for VQ based on the steepest descend method. However, any learning algorithm known as a superior one does not always work well. This paper proposes a new learning algo...
详细信息
ISBN:
(纸本)9781424416875
There have been proposed many learning algorithms for VQ based on the steepest descend method. However, any learning algorithm known as a superior one does not always work well. This paper proposes a new learning algorithm with boosting. Boosting is a general method which attempts to boost the accuracy of any given learning algorithm. The proposed method consists of three sub-learners. The first sub-learner is constructed by performing the conventional learning algorithm with data randomly selected from given data space. The second sub-learner is constructed by performing the conventional learning algorithm with data selected with higher probability from data incorrectly learned by the first sub-learner. The third sub-learner is constructed with data for which either the first or the second sub-learner is incorrectly learned. That is, the method attempts to construct different kinds of reference vectors by using different kinds of data sets constructed from the original data set The output for any input data is given as decision by averaging the outputs of three sub-learners. In order to show the effectiveness of the proposed algorithm, numerical simulations are performed.
暂无评论