Partial observability and learnability

When sensing its environment, an agent often receives information that only partially describes the current state of affairs. The agent then attempts to predict what it has not sensed, by using other pieces of information available through its sensors. Machine learning techniques can naturally aid this task, by providing the agent with the rules to be used for making these predictions. For this to happen, however, learning algorithms need to be developed that can deal with missing information in the learning examples in a principled manner, and without the need for external supervision. We investigate this problem herein.We show how the Probably Approximately Correct semantics can be extended to deal with missing information during both the learning and the evaluation phase. Learning examples are drawn from some underlying probability distribution, but parts of them are hidden before being passed to the learner. The goal is to learn rules that can accurately recover information hidden in these learning examples. We show that for this to be done, one should first dispense the requirement that rules should always make definite predictions; “don't know” is sometimes necessitated. On the other hand, such abstentions should not be done freely, but only when sufficient information is not present for definite predictions to be made. Under this premise, we show that to accurately recover missing information, it suffices to learn rules that are highly consistent, i.e., rules that simply do not contradict the agent's sensory inputs. It is established that high consistency implies a somewhat discounted accuracy, and that this discount is, in some defined sense, unavoidable, and depends on how adversarially information is hidden in the learning examples.Within our proposed learning model we prove that any PAC learnable class of monotone or read-once formulas is also learnable from incomplete learning examples. By contrast, we prove that parities and monotone-term 1-decision lists, which are properly PAC learnable, are not properly learnable under the new learning model. In the process of establishing our positive and negative results, we re-derive some basic PAC learnability machinery, such as Occam's Razor, and reductions between learning tasks. We finally consider a special case of learning from partial learning examples, where some prior bias exists on the manner in which information is hidden, and show how this provides a unified view of many previous learning models that deal with missing information.We suggest that the proposed learning model goes beyond a simple extension of supervised learning to the case of incomplete learning examples. The principled and general treatment of missing information during learning, we argue, allows an agent to employ learning entirely autonomously, without relying on the presence of an external teacher, as is the case in supervised learning. We call our learning model autodidactic to emphasize the explicit disassociation of this model from any form of external supervision.     

On the non-efficient PAC learnability of conjunctive queries

This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct (PAC) model, paying clear attention to the complicating fact that this concept class lacks the polynomial-size fitting property, a property that is tacitly assumed in much of the computational learning theory literature; (ii) we establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs), including acyclic CQs for a wide range of notions of acyclicity; (iii) we show that CQs (and UCQs) are efficiently PAC learnable with membership queries.     

Efficient PAC Learning for Episodic Tasks with Acyclic State Spaces

This paper considers the problem of computing an optimal policy for a Markov decision process, under lack of complete a priori knowledge of (1) the branching probability distributions determining the evolution of the process state upon the execution of the different actions, and (2) the probability distributions characterizing the immediate rewards returned by the environment as a result of the execution of these actions at different states of the process. In addition, it is assumed that the underlying process evolves in a repetitive, episodic manner, with each episode starting from a well-defined initial state and evolving over an acyclic state space. A novel efficient algorithm for this problem is proposed, and its convergence properties and computational complexity are rigorously characterized in the formal framework of computational learning theory. Furthermore, in the process of deriving the aforementioned results, the presented work generalizes Bechhofer’s “indifference-zone” approach for the ranking & selection problem, that arises in statistical inference theory, so that it applies to populations with bounded general distributions.

PAC Analogues of Perceptron and Winnow Via Boosting the Margin

We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit sample complexity bounds remarkably similar to those of known online algorithms such as Perceptron and Winnow, thus suggesting that these well-studied online algorithms in some sense correspond to instances of boosting. We show that the new algorithms can be viewed as natural PAC analogues of the online p-norm algorithms which have recently been studied by Grove, Littlestone, and Schuurmans (1997, Proceedings of the Tenth Annual Conference on Computational Learning Theory (pp. 171–183) and Gentile and Littlestone (1999, Proceedings of the Twelfth Annual Conference on Computational Learning Theory (pp. 1–11). As special cases of the algorithm, by taking p = 2 and p = we obtain natural boosting-based PAC analogues of Perceptron and Winnow respectively. The p = case of our algorithm can also be viewed as a generalization (with an improved sample complexity bound) of Jackson and Craven's PAC-model boosting-based algorithm for learning sparse perceptrons (Jackson & Craven, 1996, Advances in neural information processing systems 8, MIT Press). The analysis of the generalization error of the new algorithms relies on techniques from the theory of large margin classification.     

Dependency trees in sub-linear time and bounded memory

We focus on the problem of efficient learning of dependency trees. Once grown, they can be used as a special case of a Bayesian network, for PDF approximation, and for many other uses. Given the data, a well-known algorithm can fit an optimal tree in time that is quadratic in the number of attributes and linear in the number of records. We show how to modify it to exploit partial knowledge about edge weights. Experimental results show running time that is near-constant in the number of records, without significant loss in accuracy of the generated trees. Work done at Carnegie-Mellon university. This research was sponsored by the National Science Foundation (NSF) under grant no. ACI-0121671 and no. DMS-9873442.     

Uniform-distribution attribute noise learnability

We study the problem of PAC-learning Boolean functions with random attribute noise under the uniform distribution. We define a noisy distance measure for function classes and show that if this measure is small for a class and an attribute noise distribution D then is not learnable with respect to the uniform distribution in the presence of noise generated according to D. The noisy distance measure is then characterized in terms of Fourier properties of the function class. We use this characterization to show that the class of all parity functions is not learnable for any but very concentrated noise distributions D. On the other hand, we show that if is learnable with respect to uniform using a standard Fourier-based learning technique, then is learnable with time and sample complexity also determined by the noisy distance. In fact, we show that this style algorithm is nearly the best possible for learning in the presence of attribute noise. As an application of our results, we show how to extend such an algorithm for learning AC⁰ so that it handles certain types of attribute noise with relatively little impact on the running time.     

On PAC learnability of functional dependencies

This paper proposes a kind of probably approximately correct (PAC) learning framework for inferring a set of functional dependencies (FDs) from example tuples. A simple algorithm is considered that outputs a set of all FDs which hold in a set of example tuples. Letr be a relation (a set of tuples). We define the error for a set of FDsFS as the minimum Σ _t∈ν; where ν (ν ⊂r) is a set such thatFS holds inr − ν, andP(t) denotes the probability that tuplet is picked fromr. Our attention is focused on the sample complexity, and we show that the number of example tuples required to infer a set of FDs whose error does not exceed ω with probability at least 1 − δ under an arbitrary probability distribution is. Tatsuya Akutsu, Ph. D.: He is an associate professor of Department of Computer Science, Gunma University. He received the B. E. degree in 1984, the M. E. degree in 1986 and the Dr. Eng. degree in 1989 from The University of Tokyo. From 1989 to 1994, he was with Mechanical Engineering Laboratory, MITI, Japan. His research interests are design and analysis of algorithms, computational learning theory and bioinformatics.     

An introduction to some statistical aspects of PAC learning theory

In this paper, a brief introduction is given to some statistical aspects of PAC (probably approximately correct) learning theory. It is shown that there is a close connection between the principal results in PAC learning theory and those in empirical process theory, the latter being a well-established branch of probability theory. The main results in each area are summarized without proofs, and the reader is directed to appropriate sources in the literature.     

Abductive Explanation-Based Learning: A Solution to the Multiple Inconsistent Explanation Problem

One problem which frequently surfaces when applying explanation-based learning (EBL) to imperfect theories is themultiple inconsistent explanation problem. The multiple inconsistent explanation problem occurs when a domain theory produces multiple explanations for a training instance, only some of which are correct. Domain theories which suffer from the multiple inconsistent explanation problem can occur in many different contexts, such as when some information is missing and must be assumed: since such assumptions can be incorrect, incorrect explanations can be constructed. This paper proposes an extension of explanation-based learning, calledabductive explanation-based learning (A-EBL) which solves the multiple inconsistent explanation problem by using set covering techniques and negative examples to choose among the possible explanations of a training example. It is shown by formal analysis that A-EBL has convergence properties that are only logarithmically worse than EBL/TS, a formalization of a certain type of knowledge-level EBL; A-EBL is also proven to be computationally efficient, assuming that the domain theory is tractable. Finally, experimental results are reported on an application of A-EBL to learning correct rules for opening bids in the game of contract bridge given examples and an imperfect domain theory.     

An improved lower bound on query complexity for quantum PAC learning

In this paper, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. For a concept class with VC dimension d, the lower bound is for ? accuracy and 1−δ confidence, where e can be an arbitrarily small positive number. The lower bound is very close to the best lower bound known on query complexity for the classical PAC learning model, which is .     

Can PAC learning algorithms tolerate random attribute noise?

This paper studies the robustness of PAC learning algorithms when the instance space is {0,1}ⁿ, and the examples are corrupted by purely random noise affecting only the attributes (and not the labels). Foruniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that PAC learns monomials for any (unknown) noise rate less than ₂ ¹ . Contrasting this positive result, we show thatproduct random attribute noise, where each attributei is flipped randomly and independently with its own probability p_i, is nearly as harmful as malicious noise-no algorithm can tolerate more than a very small amount of such noise.The research of S. A. Goldman was supported in part by a GE Foundation Junior Faculty grant and NSF Grant CCR-9110108. Part of this research was conducted while the author was at the M.I.T. Laboratory for Computer Science and supported by NSF Grant DCR-8607494 and a grant from the Siemens Corporation. The research of R. H. Sloan was supported in part by NSF Grant CCR-9108753. Part of this research was conducted while the author was at Harvard and supported by ARO Grant DAAL 03-86-K-0171.     

Parallel algorithm for calculation of the exact partition function of a lattice polymer

We develop a parallel algorithm that calculates the exact partition function of a lattice polymer, by enumerating the number of conformations for each energy level. An efficient parallelization of the calculation is achieved by classifying the conformations according to the shape of the box spanned by a conformation, and enumerating only those in a given box at a time. The calculation time for each box is reduced by preventing the conformations related by symmetries from being generated more than once. The algorithm is applied to study the collapse transition of a lattice homopolymer on a square lattice, by calculating the specific heat for chain lengths up to 36.     

PAC最优的RMAX-KNN探索算法

探索与利用的均衡是强化学习研究的重点之一。探索帮助智能体进一步了解环境来做出更优决策;而利用帮助智能体根据其自身当前对于环境的认知来做出当前最优决策。目前大多数探索算法只与值函数相关联,不考虑当前智能体对于环境的认知程度,探索效率极低。针对此问题,提出了一种基于状态空间自适应离散化的RMAX-KNN强化学习算法,算法根据当前智能体对于环境状态空间的离散化程度改写值函数形式,然后基于此值函数对环境进行合理的探索,逐步实现对于环境状态空间的自适应离散化划分。RMAXKNN算法通过将探索与环境状态空间离散化相结合,逐渐加深智能体对于环境的认知程度,进而提高探索效率,同时在理论上证明该算法是一种概率近似正确(PAC)最优探索算法。在Benchmark环境上的仿真实验结果表明,RMAX-KNN算法可以在探索环境的同时实现对于环境状态空间的自适应离散化,并学习到最优策略。     

概率近似正确的强化学习算法解决连续状态空间控制问题

在线学习时长是强化学习算法的一个重要指标.传统在线强化学习算法如Q学习、状态–动作–奖励–状态–动作(state-action-reward-state-action,SARSA)等算法不能从理论分析角度给出定量的在线学习时长上界.本文引入概率近似正确(probably approximately correct,PAC)原理,为连续时间确定性系统设计基于数据的在线强化学习算法.这类算法有效记录在线数据,同时考虑强化学习算法对状态空间探索的需求,能够在有限在线学习时间内输出近似最优的控制.我们提出算法的两种实现方式,分别使用状态离散化和kd树(k-dimensional树)技术,存储数据和计算在线策略.最后我们将提出的两个算法应用在双连杆机械臂运动控制上,观察算法的效果并进行比较.     

Discriminative learning can succeed where generative learning fails

Generative algorithms for learning classifiers use training data to separately estimate a probability model for each class. New items are classified by comparing their probabilities under these models. In contrast, discriminative learning algorithms try to find classifiers that perform well on all the training data.We show that there is a learning problem that can be solved by a discriminative learning algorithm, but not by any generative learning algorithm. This statement is formalized using a framework inspired by previous work of Goldberg [P. Goldberg, When can two unsupervised learners achieve PAC separation?, in: Proceedings of the 14th Annual COLT, 2001, pp. 303-319].     

PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs are a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. Recent work on learning PDFAs from random examples has used the KL-divergence as the error measure; here we use the variation distance. We build on recent work by Clark and Thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.     

On exact solutions to the Euclidean bottleneck Steiner tree problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal -time exact algorithm for k=1 and an O(n²)-time algorithm for k=2. Also, we present an optimal -time exact algorithm for any constant k for a special case where there is no edge between Steiner points.     

Closure properties of uniform convergence of empirical means and PAC learnability under a family of probability measures

Open Problem No. 12.2 of (Vidyasagar, A Theory of Learning and Generalization: with Application to Neural Networks and Control Systems, Springer, London, 1997) asks: “Are the properties of uniform convergence of empirical means, and learnability preserved when the family of probability measures is replaced by its closure?” In this note, the question is answered in the affirmative. Further, it is shown that these properties are not preserved in general if the family of probability measures is replaced by its convex closure. An open question is posed as to whether it is possible to replace the family of probability measures by its convex closure in case the family is compact.     

Learning From Noisy Examples

Machine Learning - The basic question addressed in this paper is: how can a learning algorithm cope with incorrect training examples? Specifically, how can algorithms that produce an...