Name
Abstract | ||
|---|---|---|
We define the rank of a decision tree and show that for any fixed r , the class of all decision trees of rank at most r on n Boolean variables is learnable from random examples in time polynomial in n and linear in 1/ɛ and log(1/δ), where ɛ is the accuracy parameter and δ is the confidence parameter. Using a suitable encoding of variables, Rivest's polynomial learnability result for decision lists can be interpreted as a special case of this result for rank 1. As another corollary, we show that decision trees on n Boolean variables of size polynomial in n are learnable from random examples in time linear in n O (log n ) , 1/ɛ, and log(1/δ). As a third corollary, we show that Boolean functions that have polynomial size DNF expressions for both their positive and their negative instances are learnable from random examples in time linear in n O ((log n ) 2 ) , 1/ɛ, and log(1/δ). |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1016/0890-5401(89)90001-1 | Information and Computation/information and Control |
Keywords | DocType | Volume |
decision tree | Conference | 82 |
Issue | ISSN | Citations |
3 | Information and Computation | 64 |
PageRank | References | Authors |
28.73 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Ehrenfeucht | 1 | 1823 | 497.83 |
| David Haussler | 2 | 8327 | 3068.93 |