Abstract
This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples. More precisely, this result is established for k-DL the set of decision lists with conjunctive clauses of size k at each decision. Since k-DL properly includes other well-known techniques for representing Boolean functions such as k-CNF (formulae in conjunctive normal form with at most k literals per clause), k-DNF (formulae in disjunctive normal form with at most k literals per term), and decision trees of depth k, our result strictly increases the set of functions that are known to be polynomially learnable, in the sense of Valiant (1984). Our proof is constructive: we present an algorithm that can efficiently construct an element of k-DL consistent with a given set of examples, if one exists.
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
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1986). Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (pp. 273–282). Berkeley, CA.
Blumer, A., Ehrenfeucht, A., Haussler, D. & Warmuth, M. K. (1987). Occam's Razor. Information Processing Letters, 24, 377–380.
Kearns, M., Li, M., Pitt, L., & Valiant, L. (1987). On the learnability of Boolean formulae. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (pp. 285–295). New York, NY.
Masek, W. (1976). Some NP-complete set-covering problems. Unpublished manuscript, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA.
Pearl, J. (1978). On the connection between the complexity and credibility of inferred models. Journal of General Systems, 4, 255–264.
Pitt, L., & Valiant, L. G. (1986). Computational limitations on learning from examples (Technical Report). Cambridge, MA: Harvard University, Aiken Computation Laboratory.
Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81–106.
Quinlan, J. R. (1987). Generating production rules from decision trees. Proceedings of the Tenth International Joint Conference on Artificial Intelligence (pp. 304–307). Milan, Italy: Morgan Kaufmann.
Rissanen, J. (1978). Modeling by shortest data description. Automatica, 14, 465–471.
Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27, 1134–1142.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rivest, R.L. Learning decision lists. Mach Learn 2, 229–246 (1987). https://doi.org/10.1007/BF00058680
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00058680