The Strength of Weak Learnability

This paper addresses the problem of improving the accuracy of an hypothesis output by a learning algorithm in the distribution-free (PAC) learning model. A concept class is learnable (or strongly learnable) if, given access to a source of examples of the unknown concept, the learner with high probability is able to output an hypothesis that is correct on all but an arbitrarily small fraction of the instances. The concept class is weakly learnable if the learner can produce an hypothesis that performs only slightly better than random guessing. In this paper, it is shown that these two notions of learnability are equivalent.A method is described for converting a weak learning algorithm into one that achieves arbitrarily high accuracy. This construction may have practical applications as a tool for efficiently converting a mediocre learning algorithm into one that performs extremely well. In addition, the construction has some interesting theoretical consequences, including a set of general upper bounds on the complexity of any strong learning algorithm as a function of the allowed error .     

意义性笔手势的分类及其实验评估

通过文献调研和用户问卷调查,探查现存的笔手势的特征和分类,分析探讨良好、易学的笔手势的应当具备的特征;然后,从命令与笔手势联结是否紧密的角度提出意义性笔手势的概念,并将意义性笔手势分为3类:指示性笔手势、实物隐喻笔手势和文化约定笔手势;最后,通过相应的学习实验来验证根据本研究的分类所设计的意义性笔手势在易学性方面的优势.结果表明,意义性笔手势比其他非意义性笔手势更易学、易用.此结果可以用心理学中双重编码理论进行解释,同时可以作为设计笔手势的基本指导原则之一.     

Identification in the limit of categorial grammars

It is proved that for any k, the class of classical categorial grammars that assign at most k types to each symbol in the alphabet is learnable, in the Gold (1967) sense of identification in the limit from positive data. The proof crucially relies on the fact that the concept known as finite elasticity in the inductive inference literature is preserved under the inverse image of a finite-valued relation. The learning algorithm presented here incorporates Buszkowski and Penn's (1990) algorithm for determining categorial grammars from input consisting of functor-argument structures.     

Noise-Tolerant Occam Algorithms and Their Applications to Learning Decision Trees

In the distribution-independent model of concept learning of Valiant, Angluin and Laird have introduced a formal model of noise process, called classification noise process, to study how to compensate for randomly introduced errors, or noise, in classifying the example data. In this article, we investigate the problem of designing efficient learning algorithms in the presence of classification noise. First, we develop a technique of building efficient robust learning algorithms, called noise-tolerant Occam algorithms, and show that using them, one can construct a polynomial-time algorithm for learning a class of Boolean functions in the presence of classification noise. Next, as an instance of such problems of learning in the presence of classification noise, we focus on the learning problem of Boolean functions represented by decision trees. We present a noise-tolerant Occam algorithm for k-DL (the class of decision lists with conjunctive clauses of size at most k at each decision introduced by Rivest) and hence conclude that k-DL is polynomially learnable in the presence of classification noise. Further, we extend the noise-tolerant Occam algorithm for k-DL to one for r-DT (the class of decision trees of rank at most r introduced by Ehrenfeucht and Haussler) and conclude that r-DT is polynomially learnable in the presence of classification noise.     

A new character recognition scheme with lower ambiguity and higher recognizability

The concepts of degrees of recognizability, learnability and ambiguity for handwritten characters are investigated. It is shown that ambiguity plays a key role as a criterion of recognizability as well as learnability. Two experiments using two different categories of recognition schemes have been conducted. It is shown that the one with a lower degree of ambiguity possesses an inherent advantage of recognition. Several topics of future research are also discussed.     

Measurement for evaluating the learnability and resilience of methods of cognitive work

Some experiments on human–computer interaction are aimed at evaluating hypotheses concerning cognitive work. Other experiments are intended to evaluate the software tools that shape the cognitive work. In both cases, effective experimentation is premised on the control and factorial analysis of sources of variability. This entails programmes of experimentation. However, sociotechnical systems are generally a ‘moving target’ in terms of the pace of change. The objective of this study was to create a general approach to experimental design and the measurement of cognitive work that can satisfy the requirements for experimentation and yet can also provide a ‘fast track’ to the evaluation of software-supported cognitive work. A measure called i-bar is presented, which is the inverse of the mid-range. The statistic is derived from data on trials-to-criterion in tasks that require practice and learning. This single measure is interpreted as a conjoint measurement scale, permitting: (a) evaluation of sensitivity of the principal performance measure (which is used to set the metric for trials to criterion); (b) evaluation of the learnability of the work method (i.e. the goodness of the software tool); (c) evaluation of the resilience of the work method. It is shown that it is possible to mathematically model such order statistics and derive methods for estimating likelihoods. This involves novel ways of thinking about statistical analysis for discrete non-Gaussian distributions. The idea and method presented herein should be applicable to the study of the effects of any training or intervention, including software interventions designed to improve legacy work methods and interventions that involve creating entirely new cognitive work systems.     

Implementing Valiant's Learnability Theory Using Random Sets

A general learning framework which uses random sets is introduced for solving discrete-space classification problems. This framework is based on the pac-learning formalism introduced by Valiant (1984) and generalized in set-theoretic terms by Blumer, et al., (1989). The random set version of this theory is used to develop an algorithm which is a particularly efficient search scheme. This is accomplished by recasting the representational class and constructive proof presented in Valiant (1984) into random set terms and implementing it as an exhaustive search algorithm. The algorithm is a problem-specific incremental (psi) approach in that it satisfies learnability criteria for distribution-specific problems as examples are being sampled. Some theoretical and empirical analyses are presented to demonstrate the convergent pac-learnability and sample complexity of this psi-algorithm. Its performance is then tested on the multiplexor class of problems. This class has been analyzed by others as a benchmark for decision trees and genetic classifiers. Results from these test cases show that, despite using an exhaustive search, this random set implementation is computationally competitive with these more established methods (which use empirically proven heuristics). Conclusions are drawn about potential further improvements in the efficiency of this approach.     

Iterative learning control applied to distributed-order linear time invariant MIMO systems to achieve learnability

Sufficient and necessary conditions for a distributed-order linear time invariant system to be positive real are derived in terms of linear matrix inequalities. The positive realness condition is derived for three of the most usual cases presented in literature, in the realm of distributed-order linear time invariant systems. As an additional product of this paper, the strictly positive realness condition can be derived. In addition, the concept of learnability of fractional-order multi-input multi-output systems is extended to the case of distributed-order systems, which is approached from the concept of output-dissipativity by using an iterative learning scheme.     

Meaning From Environmental Sounds: Types of Signal-Referent Relations and Their Effect on Recognizing Auditory Icons.

This article addresses the learnability of auditory icons, that is, environmental sounds that refer either directly or indirectly to meaningful events. Direct relations use the sound made by the target event whereas indirect relations substitute a surrogate for the target. Across 3 experiments, different indirect relations (ecological, in which target and surrogate coexist in the world; metaphorical, in which target and surrogate have similar appearance or function, and random) were compared with one another and with direct relations on measures including associative strength ratings, amount of exposure required for learning, and response times for recognizing icons. Findings suggest that performance is best with direct relations, worst with random relations, and that ecological and metaphorical relations involve distinct types of association but do not differ in learnability. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

The classification game: combining supervised learning and language evolution

We study the emergence of shared representations in a population of agents engaged in a supervised classification task, using a model called the classification game. We connect languages with tasks by treating the agents’ classification hypothesis space as an information channel. We show that by learning through the classification game, agents can implicitly perform complexity regularisation, which improves generalisation. Improved generalisation also means that the languages that emerge are well adapted to the given task. The improved language-task fit springs from the interplay of two opposing forces: the dynamics of collective learning impose a preference for simple representations, while the intricacy of the classification task imposes a pressure towards representations that are more complex. The push–pull of these two forces results in the emergence of a shared representation that is simple but not too simple. Our agents use artificial neural networks to solve the classification tasks they face, and a simple counting algorithm to learn a language as a form-meaning mapping. We present several experiments to demonstrate that both compositional and holistic languages can emerge in our system. We also demonstrate that the agents avoid overfitting on noisy data, and can learn some very difficult tasks through interaction, which they are unable to learn individually. Further, when the agents use simple recurrent networks to solve temporal classification tasks, we see the emergence of a rudimentary grammar, which does not have to be explicitly learned.