COLT

A formula is read-once if each variable appears on at most a single input. Angluin, Hellerstein, and Karpinski have shown that boolean formulas with AND, OR, and NOT gates are exactly identifiable in polynomial time using membership and equivalence ...

This paper solves the following open problem: Is there an algorithm for on-line learning of rectangles _i=1Π^d{a_i,a_i+1,…,b_i} over a discrete domain {1,…,n}^d whose error bound is polylogarithmic in the size n^d of the domain (i.e. polynomial in d and log n )...

We investigate cryptographic lower bounds on the number of samples and on computational resources required to learn several classes of boolean circuits on the uniform distribution. Under the assumption that solving n x n^1+ε subset sum is hard, we ...

We present an algorithm for learning sets of rules that are organized into up to k levels. Each level can contain an arbitrary number of rules “if c then l” where l is the class associated to the level and c is a concept from a given class of basic ...

Approximate inference of finite state machines from sparse labeled examples has been proved NP-hard when an adversary chooses the target machine and the training set [Ang78, KV89, PW89]. We have, however, empirically found that DFA's are approximately ...

We show that a DNF with terms of size at most d can be approximated by a function with at most d^{O(d log 1/ε)})non zero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most ε. This property is ...

We present a general technique to upper bound the spectral norm of an arbitrary function. At the heart of our technique is a theorem which shows how to obtain an upper bound on the spectral norm of a decision tree given the spectral norms of the ...

A polynomial-time algorithm is presented for exactly learning the class of read-k disjoint DNF formulas—boolean formulas in disjunctive normal form where each variable appears at most k) and every assignment to the variables satisfies at most one term ...

We consider the problem of learning k-term DNF formulas using equivalence queries and incomplete membership queries as defined by Angluin and Slonim. We demonstrate that this model can be applied to non-monotone classes. Namely, we describe a polynomial-...

We show that 2-term DNF formulae are learnable in quadratic time using only a logarithmic number of positive examples if we assume that examples are drawn from a bounded distribution. We also show that k-term DNF formulae are learnable in polynomial ...

The finite sample performance of a nearest neighbor classifier is analyzed for a two-class pattern recognition problem. An exact integral expression is derived for the m-sample risk R_m given that a reference m-sample of labeled points, drawn ...

A memory-based learning system is an extended memory management system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and retrieving functional information. The main generalization techniques ...

This paper considers the learnability of subsets of first-order logic. Piror work has established two boundaries of learnability: Haussler [1989] has shown that conjunctions in first-order logic cannot be learned in the Valiant model, even if the form ...

The field of Inductive Logic Programming (ILP) is concerned with inducing logic programs from examples in the presence of background knowledge. This paper defines the ILP problem, and describes the various syntactic restrictions that are commonly used ...

This paper deals with a class of Prolog programs, called context-free term transformations (CTF). We present a polynomial time algorithm to identify a subclass of CFT, whose program consists of at most two clauses, from positive data; The algorithm uses ...

A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented. The technique is applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis ...

We study the on-line learning of classes of functions of a single real variable formed through bounds on various norms of functions' derivatives. We determine the best bounds obtainable on the worst-case sum of squared errors (also “absolute” errors) ...

In this note, we consider the problem of learning a linear function from ** to ** online. Two previous algorithms have been presented which achieve an optimal sum of squared error terms. We show that neither algorithm performs well with respect to ...

This paper develops a new computational model for learning stochastic rules (i.e. conditional probabilities over the set of labels for given instances) on the basis of statistical hypothesis testing theory, and derives bounds on sample complexities ...

In this paper, we introduce an extension of the standard PAC learning model which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the ...

Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-...

Machine learning of limit programs (i.e., programs allowed finitely many mind changes about their legitimate outputs) for computable functions is studied. Learning of iterated limit programs is also studied. To partially motivate these studies, it is ...

We show that for every probabilistic FIN-type learner with success ratio greater than 24/49, there is another probabilistic FIN-type learner with success ratio 1/2 that simulates the former. We will also show that this simulation result is tight. We ...

There is proposed a formalization of case-based learning in terms of recursion-theoretic inductive inference. This approach is directly derived from some recently published case-based learning algorithms. The intention of the present paper is to exhibit ...

Generalization is a learning problem that has received considerable attention. The generalization problem is to take a finite sample of some concept and produce an algorithm that can produce all other (perhaps infinitely many) samples of the same ...

We consider learning in situations where the function used to classify examples may switch back and forth between a small number of different concepts during the course of learning. We examine several models for such situations: oblivious models in ...

In this paper, we consider the problem of learning a subset of a domain from randomly chosen examples when the probability distribution of the examples changes slowly but continually throughout the learning process. We give upper and lower bounds on the ...

We consider PAC-learning where the distribution is known to the student. The problem addressed here is characterizing when learnability with respect to distribution D₁ implies learnability with respect to distribution D₂.

The answer to the above question ...

In this work we study the relationship between PAC learning and the property of uniform convergence. We define the concept of polynomial uniform convergence of relative frequencies to probabilities in the distribution–dependent context. Let X_n = (0,1)_n, ...

To learn, it suffices to estimate the error of all candidate hypotheses simultaneously. We study the problem of when this “simultaneous estimation” is possible and show that it leads to new learning procedures and weaker sufficient conditions for a ...