We show that randomly generated c log(n)-DNF formula can be learned exactly in probabilistic polynomial time using randomly generated examples. Our notion of randomly generated is with respect to a uniform distribution.

This paper describes new and efficient algorithms for learning deterministic finite automata. Our approach is primarily distinguished by two features: (1) the adoption of an average-case setting to model the “typical” labeling of a finite automaton, while retaining a worst-case model for the underlying graph of the automaton, along with (2) a learning model in which the learner is not provided with the means to experiment with the machine, but rather must learn solely by observing the automaton's output behavior on a random input sequence. The main contribution of this paper is in presenting the first efficient algorithms for learning non-trivial classes of automata in an entirely passive learning model. We adopt an on-line learning model in which the learner is asked to predict the output of the next state, given the next symbol of the random input sequence; the goal of the learner is to make as few prediction mistakes as possible. Assuming the learner has a means of resetting the target machine to a fixed start state, we first present an efficient algorithm that makes an expected polynomial number of mistakes in this model. Next, we show how this first algorithm can be used as a subroutine by a second algorithm that also makes a polynomial number of mistakes even in the absence of a reset. Along the way, we prove a number of combinatorial results for randomly labeled automata. We also show that the labeling of the states and the bits of the input sequence need not be truly random, but merely semi - random . Finally, we discuss an extension of our results to a model in which automata are used to represent distributions over binary strings.

We introduce and investigate a new model of learning probability distributions from independent draws. Our model is inspired by the popular Probably Approximately Correct (PAC) model for learning boolean functions from labeled

We consider the problem of learning a polynomial over an arbitrary field F defined on a set of boolean variables. We present the first provably effective algorithm for exactly identifying such polynomials using membership and equivalence queries. Our algorithm runs in time polynomial in n, the number of variables, and t, the number of nonzero terms appearing in the polynomial. The algorithm makes at most nt + 2 equivalence queries, and at most (nt + 1)(t + 3t)=2 membership queries. Our algorithm is equally effective for learning a generalized type of polynomial defined on certain kinds of semilattices. We also present an extension of our algorithm for learning multilinear polynomials when the domain of each variable is the entire field F . 1

Article Efficient learning of typical finite automata from random walks Share on Authors: Yoav Freund View Profile , Michael Kearns View Profile , Dana Ron View Profile , Ronitt Rubinfeld View Profile , Robert E. Schapire View Profile , Linda Sellie View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 315–324https://doi.org/10.1145/167088.167191Published:01 June 1993 28citation470DownloadsMetricsTotal Citations28Total Downloads470Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.