06/01/1990 09:00 AM
Computer Science
This thesis investigates the problem of designing learning algorithms that adaptively enlarge the set of primitive attributes with features (*adaptive algorithms*). We focus on learning algorithms that use decision trees as a concept description language. We motivate the need for this type of algorithm by characterizing the complexity of the decision tree representation for disjunctive concepts. Due to a representational problem, disjunctive concepts do not always have a concise decision tree description when the tests at the nodes are limited to the initial attributes. However, we show that this representational problem is overcome by using adequate features. We present two types of adaptive decision tree algorithms: iterative algorithms, and separate and conquer algorithms. Algorithms of the first type use an iterative control structure. In each iteration very simple combinations of features from previous iterations are proposed. More adequate and complex features are created as the number of iterations increases. Algorithms of the second type use a greedy top-down approach to explain the training examples by a restricted kind of decision tree, called a decision list. The performance of the algorithms is evaluated empirically on several synthetic and natural domains that have been used as benchmarks for other learning algorithms. The results establish that the algorithms outperform a standard decision tree method when the target concept can be described either by a small Disjunctive Normal Form (DNF) formula or by a small Disjunctive Linear Form formula whose nonzero weights have a magnitude 1 ((0,1)DLF), and the examples are drawn from the uniform distribution over the instance space. Finally, we prove that one of the algorithms is a Probably Approximately Correct (PAC) algorithm for learning muDNF concepts when the examples are drawn from the uniform distribution. Notes: Ph.D. Thesis
