Abstract
We investigate the problem of learning Boolean functions with a short DNF representation using decision trees as a concept description language. Unfortunately, Boolean concepts with a short description may not have a small decision tree representation when the tests at the nodes are limited to the primitive attributes. This representational shortcoming may be overcome by using Boolean features at the decision nodes. We present two new methods that adaptively introduce relevant features while learning a decision tree from examples. We show empirically that these methods outperform a standard decision tree algorithm for learning small random DNF functions when the examples are drawn at random from the uniform distribution.
Article PDF
Similar content being viewed by others
References
Beach, L.R. (1964). Cue probabilism and inference behavior. Psychological Monographs, Whole. 582.
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1987). Occam's razor. Information Processing Letters. 24:377-380.
Breiman, L., Friedman, J.H., Olsen, R.A., & Stone, C.J. (1984). Classification and Regression Trees. Wadsworth Statistic/Probability Series.
Carbonell, J., Michalski, R., & Mitchell, T. (1983). An overview of machine learning. In Machine Learning: An Artificial Intelligence Approach, 3-24 Morgan Kaufmann.
Clark, P. & Niblett, T. (1989). The CN2 induction algorithm. Machine Learning, 3:251-283.
Flann, N. & Dietterich, T. (1986). Selecting appropriate representation for learning from examples. Proceedings of AAAl-86,(pp.460-466). Morgan Kaufmann.
Haussler, D. (1988). Quantifying inductive bias: AI learning algorithms and Valiant's learning framework. Ar-tificial Intelligence, 36: 177-221.
Kearns, M., Li, M. & Valiant, L. (1987). Recent results on Boolean concept learning. Proceedings of 4th International Workshop on Machine Learning, (pp.337-352). Morgan Kaufmann.
Matheus, C. (1989). Feature Construction: An Analytic Framework and An Application to Decision Trees. Ph. D. thesis, University of Illinois, December 1989. In preparation.
Muggleton, S. (1987). Duce, an oracle-based approach to constructive induction. Proceedings oflJCAI-87,(pp. 287-292). Morgan Kaufmann.
Pagallo, G. and Haussler, D. (1989). A greedy method for learning /DNF functions under the uniform distribu-tion. (Technical Report UCSC-CRL-89-12, Santa Cruz: Dept. of Computer and Information Sciences, University of California at Santa Cruz.
Pagallo, G. (1989). Learning DNF by decision trees. Proceedings of lJCAI-89,(pp.639-644). Morgan Kaufmann.
Quinlan, J.R. (1986). Induction of decision trees. Machine Learning,1: 81-106.
Quintan, J.R. (1987a). Generating production rules from decision trees. Proceedings of lJCAI-87,1;(pp.304-307). Morgan Kaufmann.
Quinlan, J.R. (1987b). Simplifying decision trees. International Journal of Man-machine Studies,27: 221-234.
Quinlan, J.R. (1988). An empirical comparison of genetic and decision tree classifiers. Proceedings of the 5th International Conference on Machine Learning (pp.135-141). Morgan Kaufmann.
Rivest, R. (1987). Learning decision lists. Machine Learning,2: 229-246.
Schlimmer, J.C. (1986). Concept acquisition through representational adjustment. Machine Learning,1: 81-106.
Utgoff, P. and Mitchell, T.M. (1982). Acquisition of appropriate bias for inductive concept learning. Proceedings of AAAI-82,(pp.414-417). Morgan Kaufmann.
Valiant, L.G. (1984). A theory of the learnable. Communications of ACM,27: 1134-1142.
Valiant, L.G. (1985). Learning disjunctions of conjunctions. Proceedings of IJCAI-85,(pp.560-566). Morgan Kaufmann.
Vapnik, V.N. (1987). Estimation of Dependencies Based on Empirical Data. Springer Verlag.
Wilson, S.W. (1987). Classifier systems and the animat problem. Machine Learning,2: 199-228,1987.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pagallo, G., Haussler, D. Boolean Feature Discovery in Empirical Learning. Machine Learning 5, 71–99 (1990). https://doi.org/10.1023/A:1022611825350
Issue Date:
DOI: https://doi.org/10.1023/A:1022611825350