Can learning algorithms find a Nash equilibrium? This is a natural question for several reasons. learning algorithms resemble the behavior of players in many naturally arising games, and thus results on the convergenc...
详细信息
ISBN:
(纸本)9783642161698
Can learning algorithms find a Nash equilibrium? This is a natural question for several reasons. learning algorithms resemble the behavior of players in many naturally arising games, and thus results on the convergence or non-convergence properties of such dynamics may inform our understanding of the applicability of Nash equilibria as a plausible solution concept in some settings. A second reason for asking this question is in the hope of being able to prove an impossibility result, not dependent on complexity assumptions, for computing Nash equilibria via a restricted class of reasonable algorithms. In this work, we begin to answer this question by considering the dynamics of the standard multiplicative weights update learning algorithms (which are known to converge to a Nash equilibrium for zero-sum games). We revisit a 3 x 3 game defined by Shapley [10] in the 1950s in order to establish that fictitious play does not converge in general games. For this simple game, we show via a potential function argument that in a variety of settings the multiplicative updates algorithm impressively fails to find the unique Nash equilibrium, in that the cumulative distributions of players produced by learning dynamics actually drift away from the equilibrium.
An absorbing learning automaton which is based on the use of a stochastic estimator is introduced. According to the proposed stochastic estimator scheme, the estimates of the reward probabilities are computed stochast...
详细信息
ISBN:
(纸本)0769511651
An absorbing learning automaton which is based on the use of a stochastic estimator is introduced. According to the proposed stochastic estimator scheme, the estimates of the reward probabilities are computed stochastically. Actions that have not been selected many times have the opportunity to be estimated as optimal, to increase their choice probabilities, and consequently, to be selected. In this way, the automaton's accuracy is significantly improved. This proposed automaton is proven to be absolutely expedient in all stationary environments, while the simulation results demonstrate that the proposed scheme achieves a significantly higher performance in comparison with the deterministic estimator based schemes.
Expert based learning algorithms have been used by robots to choose satisfying reactions to human movements. These algorithms often demonstrate random performance that tries to hit a balance between adaptiveness and c...
详细信息
ISBN:
(纸本)9781509059928
Expert based learning algorithms have been used by robots to choose satisfying reactions to human movements. These algorithms often demonstrate random performance that tries to hit a balance between adaptiveness and consistency that matches human's preferences intuitively. This paper provides a rigorous way to quantify the adaptiveness and consistency of the expert based learning algorithms in the context of human robot interaction. It is discovered that a Markov chain model can be used to allow the analysis of both adaptiveness and consistency for several popular expert based learning algorithms. Success of the method has been seen in both simulation and experimental work.
Generalization analyses of deep learning typically assume that the training converges to a fixed point. But, recent results indicate that in practice, the weights of deep neural networks optimized with stochastic grad...
详细信息
ISBN:
(纸本)9781713871088
Generalization analyses of deep learning typically assume that the training converges to a fixed point. But, recent results indicate that in practice, the weights of deep neural networks optimized with stochastic gradient descent often oscillate indefinitely. To reduce this discrepancy between theory and practice, this paper focuses on the generalization of neural networks whose training dynamics do not necessarily converge to fixed points. Our main contribution is to propose a notion of statistical algorithmic stability (SAS) that extends classical algorithmic stability to non-convergent algorithms and to study its connection to generalization. This ergodic-theoretic approach leads to new insights when compared to the traditional optimization and learning theory perspectives. We prove that the stability of the time-asymptotic behavior of a learning algorithm relates to its generalization and empirically demonstrate how loss dynamics can provide clues to generalization performance. Our findings provide evidence that networks that "train stably generalize better" even when the training continues indefinitely and the weights do not converge.
This article describes the use of connectionist and symbolic learning algorithms in the problem of Bankruptcy Prediction. Data about Brazilian banks represented by 26 or 10 indicators of their current financial situat...
详细信息
ISBN:
(纸本)0780348605
This article describes the use of connectionist and symbolic learning algorithms in the problem of Bankruptcy Prediction. Data about Brazilian banks represented by 26 or 10 indicators of their current financial situation were used. The difference among the number of existent examples in the classes of bankrupt and non-bankrupt banks was livened up through the reduction of learning examples of the class of non-bankrupts and the addition of noise samples in the class of bankrupts.
This paper is theoretical. We present sufficient and ''almost'' necessary conditions for learning compatibility coefficients in relaxation labeling whose satisfaction will guarantee each desired sample...
详细信息
ISBN:
(纸本)0818679204
This paper is theoretical. We present sufficient and ''almost'' necessary conditions for learning compatibility coefficients in relaxation labeling whose satisfaction will guarantee each desired sample labeling to become consistent and each ambiguous or erroneous input sample labeling to Be attracted to the corresponding desired sample labeling. The derived learning conditions are parallel and local information based. In fact, they are organized as linear inequalities in unit wise and thus the perceptron like algorithms can be used to solve them efficiently with finite convergence.
Construction tasks involve various activities composed of one or more body motions. It is essential to understand the dynamically changing behavior and state of construction workers to manage construction workers effe...
详细信息
ISBN:
(纸本)9780784482438
Construction tasks involve various activities composed of one or more body motions. It is essential to understand the dynamically changing behavior and state of construction workers to manage construction workers effectively with regards to their safety and productivity. While several research efforts have shown promising results in activity recognition, further research is still necessary to identify the best locations of motion sensors on a worker's body by analyzing the recognition results for improving the performance and reducing the implementation cost. This study proposes a simulation-based evaluation of multiple motion sensors attached to workers performing typical construction tasks. A set of 17 inertial measurement unit (IMU) sensors is utilized to collect motion sensor data from an entire body. Multiple machine learning algorithms are utilized to classify the motions of the workers by simulating several scenarios with different combinations and features of the sensors. Through the simulations, each IMU sensor placed in different locations of a body is tested to evaluate its recognition accuracy toward the worker's different activity types. Then, the effectiveness of sensor locations is measured regarding activity recognition performance to determine relative advantage of each location. Based on the results, the required number of sensors can be reduced maintaining the recognition performance. The findings of this study can contribute to the practical implementation of activity recognition using simple motion sensors to enhance the safety and productivity of individual workers.
Spiking neural networks (SNNs) have received extensive attention in multi-disciplinary fields, due to their rich spatiotemporal dynamics and the potential for low processing delay and high energy efficiency on neuromo...
详细信息
ISBN:
(纸本)9781665488679
Spiking neural networks (SNNs) have received extensive attention in multi-disciplinary fields, due to their rich spatiotemporal dynamics and the potential for low processing delay and high energy efficiency on neuromorphic hardware. The research on SNN learning algorithms is active and diverse, and many algorithms differ significantly from those of DNN in terms of computation model/features and weight adjustment mechanisms. This paper proposes FABLE, a multi-level framework for building and running SNN learning algorithms efficiently. Its kernel is an adaptable computation model based on synchronous data flow, which can well express the spatiotemporal parallelism of SNN and then can organize and schedule the underlying SNN-custom tensor operators (OPs) to construct optimized computing procedures. It also provides a flexible programming interface for users to design or customize their learning algorithms. In addition, the implementation of FABLE has high compatibility: It extends PyTorch's OP library, scheduler, and APIs to take advantage of the ecology and usability of the latter. To show the flexibility of the framework, we have ported five different learning algorithms, each with less programming than its original implementation. Further experiments demonstrate that FABLE outperforms all of them (up to 2.61x) in terms of computing performance, while the original implementations are either based on PyTorch, based on some third-party tool using PyTorch, or based on GPGPU's runtime directly.
We study polynomial time learning algorithms for Multiplicity Automata (MA) and Multiplicity Automata Function (MAF) that minimize the access to one or more of the following resources: Equivalence queries, Membership ...
详细信息
ISBN:
(纸本)3540352945
We study polynomial time learning algorithms for Multiplicity Automata (MA) and Multiplicity Automata Function (MAF) that minimize the access to one or more of the following resources: Equivalence queries, Membership queries or Arithmetic operations in the field T. This is in particular interesting when access to one or more of the above resources is significantly more expensive than the others. We apply new algebraic approach based on Matrix Theory to simplify the algorithms and the proofs of their correctness. We improve the arithmetic complexity of the problem and argue that it is almost optimal. Then we prove tight bound for the minimal number of equivalence queries and almost (up to log factor) tight bound for the number of membership queries.
Linear separabilty of learning sets is a basic concept of neural networks theory. Exploration of the linear separability can be based on the minimization of the perceptron criterion function. Modification of the perce...
详细信息
ISBN:
(纸本)9783642410123;9783642410130
Linear separabilty of learning sets is a basic concept of neural networks theory. Exploration of the linear separability can be based on the minimization of the perceptron criterion function. Modification of the perceptron criterion function have been proposed recently aimed at feature selection problem. The modified criterion functions allows, among others, for discovering minimal feature subset that assure linear separability. learning algorithm linked to the modified function is formulated in the paper.
暂无评论