Leonard Pitt

AIJ Journal 2004 Journal Article

Version spaces and the consistency problem

• Haym Hirsh
• Nina Mishra
• Leonard Pitt

A version space is a collection of concepts consistent with a given set of positive and negative examples. Mitchell [Artificial Intelligence 18 (1982) 203–226] proposed representing a version space by its boundary sets: the maximally general (G) and maximally specific consistent concepts (S). For many simple concept classes, the size of G and S is known to grow exponentially in the number of positive and negative examples. This paper argues that previous work on alternative representations of version spaces has disguised the real question underlying version space reasoning. We instead show that tractable reasoning with version spaces turns out to depend on the consistency problem, i. e. , determining if there is any concept consistent with a set of positive and negative examples. Indeed, we show that tractable version space reasoning is possible if and only if there is an efficient algorithm for the consistency problem. Our observations give rise to new concept classes for which tractable version space reasoning is now possible, e. g. , 1-decision lists, monotone depth two formulas, and halfspaces.

SODA Conference 2001 Conference Paper

Sublinear time approximate clustering

• Nina Mishra
• Daniel Oblinger
• Leonard Pitt

ICML Conference 1993 Conference Paper

Learning From Entailment: An Application to Propositional Horn Sentences

• Michael Frazier
• Leonard Pitt

TCS Journal 1992 Journal Article

On the necessity of Occam algorithms

• Raymond Board
• Leonard Pitt

The distribution-independent model of concept learning from examples (“PAC-learning”) due to Valiant (1984) is investigated. It has been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class (Blumer 1987, 1989). (An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.) In this paper it is shown for many natural concept classes that the PAC-learnability of the class implies the existence of an Occam algorithm for the class. More generally, the property of closure under exception lists is defined, and it is shown that for any concept class with this property, PAC-learnability of the class is equivalent to the existence of an Occam algorithm for the class. An interpretation of these results is that for many classes, PAC-learnability is equivalent to data compression.

FOCS Conference 1992 Conference Paper

Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries

• Howard Aizenstein
• Lisa Hellerstein
• Leonard Pitt

A general technique is developed to obtain nonlearnability results in the model of exact learning from equivalence and membership queries. The technique is applied to show that, assuming NP not=co-NP, there does not exist a polynomial-time membership and equivalence query algorithm for exactly learning read-thrice DNF formulas-boolean formulas in disjunctive normal form where each variable appears at most three times. This result adds evidence to the conjecture that DNF is hard to learn in the membership and equivalence query model. >

FOCS Conference 1991 Conference Paper

Exact Learning of Read-Twice DNF Formulas (Extended Abstract)

• Howard Aizenstein
• Leonard Pitt

A polynomial-time algorithm is presented for exactly learning the class of read-twice DNF formulas, i. e. Boolean formulas in disjunctive normal form where each variable appears at most twice. The (standard) protocol used allows the learning algorithm to query whether a given assignment of Boolean variables satisfies the DNF formula to be learned (membership queries), as well as to obtain counterexamples to the correctness of its current hypothesis which can be any arbitrary DNF formula (equivalence queries). The formula output by the learning algorithm is logically equivalent to the formula to be learned. >

FOCS Conference 1990 Conference Paper

Learning Conjunctions of Horn Clauses (Extended Abstract)

• Dana Angluin
• Michael Frazier
• Leonard Pitt

An algorithm for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses is presented. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable). The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula. >

STOC Conference 1990 Conference Paper

On the Necessity of Occam Algorithms

• Raymond A. Board
• Leonard Pitt

STOC Conference 1989 Conference Paper

The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial

• Leonard Pitt
• Manfred K. Warmuth

I&C Journal 1988 Journal Article

Probability and plurality for aggregations of learning machines

• Leonard Pitt
• Carl H. Smith

A new notion of probabilistic team inductive inference is introduced and compared with both probabilistic inference and team inference. In many cases, but not all, probabilism can be traded for pluralism, and vice versa. Necessary and sufficient conditions are given describing when a team of deterministic or probabilistic learning machines can be coalesced into a single learning machine. A subtle difference between probabilism and pluralism is revealed.

STOC Conference 1987 Conference Paper

On the Learnability of Boolean Formulae

• Michael J. Kearns
• Ming Li 0001
• Leonard Pitt
• Leslie G. Valiant

FOCS Conference 1984 Conference Paper

A Characterization of Probabilistic Inference

• Leonard Pitt

Inductive Inference Machines (IlMs) attempt to identify functions given only input-output pairs of the functions. Probabilistic IlMs are defined, as is the probability that a probabilistic IlM identifies a function with respect to two common identification criteria: EX and BC. Let ID denote either of these criteria. Then ID/sub prob/(p) is the family of sets of functions U for which there is a probabilistic IlM identifying every f /spl epsi/ U with probability /spl ges/ p. It is shown that for all positive integers n, ID/sub prob/(1/n) is properly contained in ID/sub prob/(1/(n+1)), and that this discrete hierarchy is the "finest" possible. This hierarchy is related to others in the literature.