On the Complexity of Function Learning

The majority of results in computational learning theory are concerned with concept learning, i.e. with the special case of function learning for classes of functions with range {0, 1}. Much less is known about the theory of learning functions with a larger range such as or . In particular relatively few results exist about the general structure of common models for function learning, and there are only very few nontrivial function classes for which positive learning results have been exhibited in any of these models.We introduce in this paper the notion of a binary branching adversary tree for function learning, which allows us to give a somewhat surprising equivalent characterization of the optimal learning cost for learning a class of real-valued functions (in terms of a max-min definition which does not involve any learning model).Another general structural result of this paper relates the cost for learning a union of function classes to the learning costs for the individual function classes.Furthermore, we exhibit an efficient learning algorithm for learning convex piecewise linear functions from ^d into . Previously, the class of linear functions from ^d into was the only class of functions with multidimensional domain that was known to be learnable within the rigorous framework of a formal model for online learning.Finally we give a sufficient condition for an arbitrary class of functions from into that allows us to learn the class of all functions that can be written as the pointwise maximum ofk functions from . This allows us to exhibit a number of further nontrivial classes of functions from into for which there exist efficient learning algorithms.     

Learning from a Population of Hypotheses

We introduce a new formal model in which a learning algorithm must combine a collection of potentially poor but statistically independent hypothesis functions in order to approximate an unknown target function arbitrarily well. Our motivation includes the question of how to make optimal use of multiple independent runs of a mediocre learning algorithm, as well as settings in which the many hypotheses are obtained by a distributed population of identical learning agents.     

Toward Efficient Agnostic Learning

In this paper we initiate an investigation of generalizations of the Probably Approximately Correct (PAC) learning model that attempt to significantly weaken the target function assumptions. The ultimate goal in this direction is informally termed agnostic learning, in which we make virtually no assumptions on the target function. The name derives from the fact that as designers of learning algorithms, we give up the belief that Nature (as represented by the target function) has a simple or succinct explanation. We give a number of positive and negative results that provide an initial outline of the possibilities for agnostic learning. Our results include hardness results for the most obvious generalization of the PAC model to an agnostic setting, an efficient and general agnostic learning method based on dynamic programming, relationships between loss functions for agnostic learning, and an algorithm for a learning problem that involves hidden variables.     

The Power of Self-Directed Learning

This article studies self-directed learning, a variant of the on-line (or incremental) learning model in which the learner selects the presentation order for the instances. Alternatively, one can view this model as a variation of learning with membership queries in which the learner is only charged for membership queries for which it could not predict the outcome. We give tight bounds on the complexity of self-directed learning for the concept classes of monomials, monotone DNF formulas, and axis-parallel rectangles in {0, 1, , n – 1} ^d . These results demonstrate that the number of mistakes under self-directed learning can be surprisingly small. We then show that learning complexity in the model of self-directed learning is less than that of all other commonly studied on-line and query learning models. Next we explore the relationship between the complexity of self-directed learning and the Vapnik-Chervonenkis (VC-)dimension. We show that, in general, the VC-dimension and the self-directed learning complexity are incomparable. However, for some special cases, we show that the VC-dimension gives a lower bound for the self-directed learning complexity. Finally, we explore a relationship between Mitchell's version space algorithm and the existence of self-directed learning algorithms that make few mistakes.     

一种新的连续动作集学习自动机

学习自动机（Learning automation,LA）是一种自适应决策器。其通过与一个随机环境不断交互学习从一个允许的动作集里选择最优的动作。在大多数传统的LA模型中,动作集总是被取作有限的。因此,对于连续参数学习问题,需要将动作空间离散化,并且学习的精度取决于离散化的粒度。本文提出一种新的连续动作集学习自动机（Continuous action set learning automaton,CALA）,其动作集为一个可变区间,同时按照均匀分布方式选择输出动作。学习算法利用来自环境的二值反馈信号对动作区间的端点进行自适应更新。通过一个多模态学习问题的仿真实验,演示了新算法相对于3种现有CALA算法的优越性。     

Transfer in variable-reward hierarchical reinforcement learning

Transfer learning seeks to leverage previously learned tasks to achieve faster learning in a new task. In this paper, we consider transfer learning in the context of related but distinct Reinforcement Learning (RL) problems. In particular, our RL problems are derived from Semi-Markov Decision Processes (SMDPs) that share the same transition dynamics but have different reward functions that are linear in a set of reward features. We formally define the transfer learning problem in the context of RL as learning an efficient algorithm to solve any SMDP drawn from a fixed distribution after experiencing a finite number of them. Furthermore, we introduce an online algorithm to solve this problem, Variable-Reward Reinforcement Learning (VRRL), that compactly stores the optimal value functions for several SMDPs, and uses them to optimally initialize the value function for a new SMDP. We generalize our method to a hierarchical RL setting where the different SMDPs share the same task hierarchy. Our experimental results in a simplified real-time strategy domain show that significant transfer learning occurs in both flat and hierarchical settings. Transfer is especially effective in the hierarchical setting where the overall value functions are decomposed into subtask value functions which are more widely amenable to transfer across different SMDPs.     

Context counts: How learners' contexts influence learning in a MOOC

Massive Open Online Courses (MOOCs) require individual learners to self-regulate their own learning, determining when, how and with what content and activities they engage. However, MOOCs attract a diverse range of learners, from a variety of learning and professional contexts. This study examines how a learner's current role and context influences their ability to self-regulate their learning in a MOOC: Introduction to Data Science offered by Coursera. The study compared the self-reported self-regulated learning behaviour between learners from different contexts and with different roles. Significant differences were identified between learners who were working as data professionals or studying towards a higher education degree and other learners in the MOOC. The study provides an insight into how an individual's context and role may impact their learning behaviour in MOOCs.     

Exploring learnability between exact and PAC

We study a model of probably exactly correct (PExact) learning that can be viewed either as the Exact model (learning from equivalence queries only) relaxed so that counterexamples to equivalence queries are distributionally drawn rather than adversarially chosen or as the probably approximately correct (PAC) model strengthened to require a perfect hypothesis. We also introduce a model of probably almost exactly correct (PAExact) learning that requires a hypothesis with negligible error and thus lies between the PExact and PAC models. Unlike the Exact and PExact models, PAExact learning is applicable to classes of functions defined over infinite instance spaces. We obtain a number of separation results between these models. Of particular note are some positive results for efficient parallel learning in the PAExact model, which stand in stark contrast to earlier negative results for efficient parallel Exact learning.     

不同程度的监督机制在自动文本分类中的应用

自动文本分类技术涉及信息检索、模式识别及机器学习等领域。本文以监督的程度为线索，综述了分属全监督，非监督以及半监督学习策略的若干方法-NBC(Naive Bayes Classifier)，FCM(Fuzzy C-Means)，SOM(Self-Organizing Map)，ssFCM(serni-supervised Fuzzy C-Means)gSOM(guided Self-Organizing Map)，并应用于文本分类中。其中，gSOM是我们在SOM基础上发展得到的半监督形式。并以Reuters-21578为语料，研究了监督程度对分类效果的影响，从而提出了对实际文本分类工作的建议。     

学习控制技术·方法应用的发展新动向

分析和概述了当前学习控制系统所采用的技术、学习方法及应用的发展新动向 .从所采用的技术来看 ,学习控制正在从采用单一的技术向采用混合技术的方向发展 ;从学习方法和应用来看 ,学习控制正在从采用较为简单的参数学习向采用较为复杂的结构学习、环境学习和复杂对象学习的方向发展     

基于移动学习的学科主题学习资源设计研究

移动学习作为一种新型的学习方式正成为研究热点,而基于移动学习的学科主题学习资源相对缺乏。本文阐述了移动学习的概念及特点、主题学习、学科主题学习资源的理论基础,分析了基于移动学习的学科主题学习资源设计的基本原则,最后构建了基于移动学习的学科主题学习资源的设计框架。     

基于多核集成的在线半监督学习方法

在很多实时预测任务中,学习器需对实时采集到的数据在线地进行学习.由于数据采集的实时性,往往难以为采集到的所有数据提供标记.然而,目前的在线学习方法并不能利用未标记数据进行学习,致使学得的模型并不能即时反映数据的动态变化,降低其实时响应能力.提出一种基于多核集成的在线半监督学习方法,使得在线学习器即使在接收到没有标记的数据时也能进行在线学习.该方法采用多个定义在不同RKHS中的函数对未标记数据预测的一致程度作为正则化项,在此基础上导出了多核集成在线半监督学习的即时风险函数,然后借助在线凸规划技术进行求解.在UCl数据集上的实验结果以及在网络入侵检测上的应用表明,该方法能够有效利用数据流中未标记数据来提升在线学习的性能.     

Parallel Reinforcement Learning: A Framework and Case Study

In this paper, a new machine learning framework is developed for complex system control, called parallel reinforcement learning. To overcome data deficiency of current data-driven algorithms, a parallel system is built to improve complex learning system by self-guidance. Based on the Markov chain (MC) theory, we combine the transfer learning, predictive learning, deep learning and reinforcement learning to tackle the data and action processes and to express the knowledge. Parallel reinforcement learning framework is formulated and several case studies for real-world problems are finally introduced.      

面向类别不平衡数据的主动在线加权极限学习机算法

针对在样本类别分布不平衡场景下,现有的主动学习算法普遍失效及训练时间过长等问题,提出采用建模速度更快的极限学习机,即ELM(Extreme Learning Machine)作为主动学习的基分类器,并以加权ELM算法用于主动学习过程的平衡控制,进而在理论上推导了其在线学习的过程,大幅降低了主动学习的时间开销,并将最终的混合算法命名为AOW-ELM算法。通过12个基准的二类不平衡数据集验证了该算法的有效性与可行性。     

LEARNING TO SOLVE PROBLEMS FROM EXERCISES

It is a common observation that learning easier skills makes it possible to learn the more difficult skills. This fact is routinely exploited by parents, teachers, textbook writers, and coaches. From driving, to music, to science, there hardly exists a complex skill that is not learned by gradations. Natarajan's model of “learning from exercises” captures this kind of learning of efficient problem solving skills using practice problems or exercises ( Natarajan 1989 ). The exercises are intermediate subproblems that occur in solving the main problems and span all levels of difficulty. The learner iteratively bootstraps what is learned from simpler exercises to generalize techniques for solving more complex exercises. In this paper, we extend Natarajan's framework to the problem reduction setting where problems are solved by reducing them to simpler problems. We theoretically characterize the conditions under which efficient learning from exercises is possible. We demonstrate the generality of our framework with successful implementations in the Eight Puzzle, symbolic integration, and simulated robot planning domains illustrating three different representations of control knowledge, namely, macro‐operators, control rules, and decision lists. The results show that the learning rates for the exercises framework are competitive with those for learning from problems solved by the teacher.     

Query by diverse committee in transfer active learning

Transfer active learning, which is an emerging learning paradigm, aims to actively select informative instances with the aid of transferred knowledge from related tasks. Recently, several studies have addressed this problem. However, how to handle the distributional differences between the source and target domains remains an open problem. In this paper, a novel transfer active learning algorithm is proposed, inspired by the classical query by committee algorithm. Diverse committee members from both domains are maintained to improve the classification accuracy and a mechanism is included to evaluate each member during the iterations. Extensive experiments on both synthetic and real datasets show that our algorithm performs better and is also more robust than the state-of-the-art methods.     

一种聚类型基于示例学习新方法

借鉴聚类思想和万有引力计算方法,提出了解决基于示例学习中两个关键问题的新思路,这两个新思路分别是,利用示例邻近同类其它示例数目来描述该示例潜在预测能力,以及利用实例质量来帮助更加准确地预测新实例类别。据此构造了一种聚类型基于示例学习的新方法,并利用标准机器学习数据库中3个复杂数据样本,对所提方法的性能进行实验检测,有关的对比实验结果表明,所提方法在实例预测能力以及学习结果占用空间有效性方面,均优越其它多种基于示范学习方法。     

Indexing,Elaboration and Refinement: Incremental Learning of Explanatory Cases

This article describes how a reasoner can improve its understanding of an incompletely understood domain through the application of what it already knows to novel problems in that domain. Case-based reasoning is the process of using past experiences stored in the reasoner's memory to understand novel situations or solve novel problems. However, this process assumes that past experiences are well understood and provide good lessons to be used for future situations. This assumption is usually false when one is learning about a novel domain, since situations encountered previously in this domain might not have been understood completely. Furthermore, the reasoner may not even have a case that adequately deals with the new situation, or may not be able to access the case using existing indices. We present a theory of incremental learning based on the revision of previously existing case knowledge in response to experiences in such situations. The theory has been implemented in a case-based story understanding program that can (a) learn a new case in situations where no case already exists, (b) learn how to index the case in memory, and (c) incrementally refine its understanding of the case by using it to reason about new situations, thus evolving a better understanding of its domain through experience. This research complements work in case-based reasoning by providing mechanisms by which a case library can be automatically built for use by a case-based reasoning program.     

Exactly Learning Automata of Small Cover Time

We present algorithms for exactly learning unknown environments that can be described by deterministic finite automata. The learner performs a walk on the target automaton, where at each step it observes the output of the state it is at, and chooses a labeled edge to traverse to the next state. The learner has no means of a reset, and does not have access to a teacher that answers equivalence queries and gives the learner counterexamples to its hypotheses. We present two algorithms: The first is for the case in which the outputs observed by the learner are always correct, and the second is for the case in which the outputs might be corrupted by random noise. The running times of both algorithms are polynomial in the cover time of the underlying graph of the target automaton.