Files in this item
Files  Description  Format 

application/pdf 9328958.pdf (8MB)  (no description provided) 
Description
Title:  On the Learnability of Disjunctive Normal Form Formulas and Decision Trees 
Author(s):  Aizenstein, Howard Jay 
Doctoral Committee Chair(s):  Pitt, L., 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Artificial Intelligence
Computer Science 
Abstract:  The learnability of disjunctive normal form formulas and decision trees is investigated. Polynomial time algorithms are given, and nonlearnability results are obtained, for restricted versions of these general learning problems. Polynomial time algorithms are presented for exactly learning (with membership and equivalence queries) readtwice DNF and readkdisjoint DNF. A readtwice DNF formula is a boolean formula in disjunctive normal form where each variable appears at most twice. A readk disjoint DNF formula f is a DNF formula where each variable appears at most k times (for an arbitrary positive integer k) and every assignment to the variables satisfies at most one term of f. The readk disjoint DNF result also applies for a generalization of this class, which we call readk satj DNF. For a similar learning protocol, it is shown that, assuming NP $\not=$ coNP, there does not exist a polynomial time algorithm for learning readthrice DNF formulasboolean formulas in disjunctive normal form where each variable appears at most three times. This result contrasts with our polynomial time algorithm for learning readtwice DNF, and adds evidence to the conjecture that DNF is hard to learn in the membership and equivalence query model. Nonlearnability results are also obtained for the class of readk decision trees. It is shown that this class is hard to learn in the membership and equivalence query model, provided that the equivalence queries are also required to be readk decision trees. It is also shown that readk decision trees are hard to learn in the PAC model (without membership queries). A different type of nonlearnability result is obtained for the class of arbitrary DNF formulas. A natural approach for learning DNF formulas (suggested by Valiant in a seminal paper of learning theory) is to greedily collect the prime implicants of the hidden function. We show that no algorithm using such an approach can learn DNF in polynomial time. Results which suggest that DNF formulas are hard to learn rely on the construction of rare hardtolearn formulas. This raises the question of whether most DNF formulas are learnable. For certain natural definitions of most DNF formulas, this question is answered affirmatively. 
Issue Date:  1993 
Type:  Text 
Description:  132 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1993. 
URI:  http://hdl.handle.net/2142/72083 
Other Identifier(s):  (UMI)AAI9328958 
Date Available in IDEALS:  20141217 
Date Deposited:  1993 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois