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
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Beach, L.R. (1964). Cue probabilism and inference behavior.Psychological Monographs, Whole, 582.
BlumerA., EhrenfeuchtA., HausslerD. & WarmuthM. (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. InMachine Learning: An Artificial Intelligence Approach, 3–24 Morgan Kaufmann.
ClarkP. & NiblettT. (1989). The CN2 induction algorithm.Machine Learning,3:251–283.
Flann, N. & Dietterich, T. (1986). Selecting appropriate representation for learning from examples.Proceedings of AAAI-86, (pp. 460–466). Morgan Kaufmann.
Haussler,D. (1988). Quantifying inductive bias: AI learning algorithms and Valiant's learning framework.Artificial 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 of IJCAI-87, (pp. 287–292). Morgan Kaufmann.
Pagallo, G. and Haussler, D. (1989). A greedy method for learning μDNF functions under the uniform distribution. (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 IJCAI-89, (pp. 639–644). Morgan Kaufmann.
Quinlan, J.R. (1986). Induction of decision trees.Machine Learning, 1:81–106.
Quinlan, J.R. (1987a). Generating production rules from decision trees.Proceedings of IJCAI-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 Dependeneies Based on Empirical Data. Springer Verlag.
Wilson, S.W. (1987). Classifler 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
Bagallo, G., Haussler, D. Boolean feature discovery in empirical learning. Mach Learn 5, 71–99 (1990). https://doi.org/10.1007/BF00115895
Issue Date:
DOI: https://doi.org/10.1007/BF00115895