Learning decision lists
Tóm tắt
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.
Tài liệu tham khảo
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.