Article

Learning DNF by decision trees

Author:

Giulia PagalloAuthors Info & Claims

IJCAI'89: Proceedings of the 11th international joint conference on Artificial intelligence - Volume 1

Pages 639 - 644

Published: 20 August 1989 Publication History

Abstract

We investigate the problem of learning DNF concepts from examples using decision trees as a concept description language. Due to the replication problem, DNF concepts do not always have a concise decision tree description when the tests at the nodes are limited to the initial attributes. However, the representational complexity may be overcome by using high level attributes as tests. We present a novel algorithm that modifies the initial bias determined by the primitive attributes by adaptively enlarging the attribute set with high level attributes. We show empirically that this algorithm outperforms a standard decision tree algorithm for learning small random DNF with and without noise, when the examples are drawn from the uniform distribution.

References

[1]

[Blumer et al, 1987] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Occam's razor. Information Processing Letters, 24:377-380, 1987.

Digital Library

[2]

[Breiman et al, 1984] L. Breiman, J.H. Friedman, R.A. Olsen, and C.J. Stone. Classification and Regression Trees. Wadsworth Statistic/Probability Series, 1984.

[3]

[Haussler, 1988] D. Haussler. Quantifying inductive bias: AI learning algorithms and Valiant's learning framework. Artificial Intelligence, (36):177-221, 1988.

[4]

[Michalski, 1983] R. Michalski. A theory and methodology of learning. In Machine Learning: An Artificial Intelligence Approach, pages 83-134. Morgan Kaufmann, 1983.

[5]

[Muggleton, 1987] S. Muggleton. Duce, an oracle based approach to constructive induction. In Proc. IJCAI-81, pages 287-292. Morgan Kaufmann, 1987.

[6]

[Pagallo and Haussler, 1988] G. Pagallo and D. Haussler. Feature discovery in empirical learning. Technical Report UCSC-CRL-88-08, Dept. of Comp. Science, Univ. California, Santa Cruz, 1988.

[7]

[Quinlan, 1986] J.R. Quinlan. Induction of Decision Trees. Machine Learning, 1:81-106, 1986.

[8]

[Quinlan, 1987a] J.R. Quinlan. Generating production rules from decision trees. In Proc. IJCAI-87, volume 1, pages 304-307. Morgan Kauffman, 1987.

[9]

[Quinlan, 1987b] J.R. Quinlan. Simplifying decision trees. International Journal of Man-machine Studies, 27:221 234, 1987.

Digital Library

[10]

[Rivest, 1987] R. Rivest. Learning decision lists. Machine Learning, 2:229 246, 1987.

[11]

[Schlimmer, 1986] J. C. Schlimmer. Concept acquisition through representational adjustment. Machine Learning, 1:81 106, 1986.

[12]

[Subutai and Tesauro, 1988] A. Subutai and G. Tesauro. Scaling and generalization in neural networks: A case study. In Proc. IEEE-88 Conf. on Neural Inf. Proc. Systems - Natural and Synthetic, 1988.

[13]

[Utgoff and Mitchell, 1982] P. Utgoff and T. M. Mitchell. Acquisition of appropriate bias for inductive concept learning. In Proc. AAA 1-82, pages 414-417. Morgan Kaufmann, 1982.

[14]

[Valiant, 1985] L. G. Valiant. Learning disjunctions of conjunctions. In Proc. IJCAJ-85, pages 560-566. Morgan Kaufmann, 1985.

[15]

[Vapnik, 1982] V. N. Vapnik. Estimation of Dependencies Based on Empirical Data. Springer Verlag, 1982.

Digital Library

[16]

[Wilson, 1987] S. W. Wilson. Classifier systems and the animat problem. Machine Learning, 2:199228, 1987.

Cited By

Poon HDomingos P(2011)Sum-product networksProceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence10.5555/3020548.3020588(337-346)Online publication date: 14-Jul-2011
https://dl.acm.org/doi/10.5555/3020548.3020588
Piramuthu SSikora R(2009)Iterative feature construction for improving inductive learning algorithmsExpert Systems with Applications: An International Journal10.1016/j.eswa.2008.02.01036:2(3401-3406)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.eswa.2008.02.010
Apté CHong S(1994)Predicting equity returns from securities data with minimal rule generationProceedings of the 3rd International Conference on Knowledge Discovery and Data Mining10.5555/3000850.3000892(407-418)Online publication date: 31-Jul-1994
https://dl.acm.org/doi/10.5555/3000850.3000892

Learning DNF by decision trees
1. Computing methodologies
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Agnostically learning decision trees
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

We give a query algorithm for agnostically learning decision trees with respect to the uniform distribution on inputs. Given black-box access to an *arbitrary* binary function f on the n-dimensional hypercube, our algorithm finds a function that agrees ...
Exact learning of DNF formulas using DNF hypotheses
Special issue on COLT 2002

We show the following: (a) For any @e>0, log^(^3^+^@e^)n-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) For sufficiently large t, t-term DNF formulas cannot be polynomial-query learned with ...
Lower Bounds on Learning Decision Lists and Trees

k-Decision lists and decision trees play important roles in learning theory as well as in practical learning systems.k-Decision lists generalize classes such as monomials,k-DNF, andk-CNF, and like these subclasses they are polynomially PAC-learnable R. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IJCAI'89: Proceedings of the 11th international joint conference on Artificial intelligence - Volume 1

August 1989

854 pages

Sponsors

The International Joint Conferences on Artificial Intelligence, Inc.

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 20 August 1989

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Poon HDomingos P(2011)Sum-product networksProceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence10.5555/3020548.3020588(337-346)Online publication date: 14-Jul-2011
https://dl.acm.org/doi/10.5555/3020548.3020588
Piramuthu SSikora R(2009)Iterative feature construction for improving inductive learning algorithmsExpert Systems with Applications: An International Journal10.1016/j.eswa.2008.02.01036:2(3401-3406)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.eswa.2008.02.010
Apté CHong S(1994)Predicting equity returns from securities data with minimal rule generationProceedings of the 3rd International Conference on Knowledge Discovery and Data Mining10.5555/3000850.3000892(407-418)Online publication date: 31-Jul-1994
https://dl.acm.org/doi/10.5555/3000850.3000892

View Options

View options

Figures

Tables

Media

View Table of Conten