caa a22 4500 467947562 CHVBK 20180323165701.0 cr unu---uuuuu 170328e19871101xx s 000 0 eng 10.1007/BF00058680 doi (NATIONALLICENCE)springer-10.1007/BF00058680 (NATIONALLICENCE)springer-10.1023/A:1022607331053 Rivest Ronald Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, Massachusetts, U.S.A. aut Learning decision lists [Elektronische Daten] [Ronald Rivest] 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. Kluwer Academic Publishers, 1987 Learning from examples nationallicence decision lists nationallicence Boolean formulae nationallicence polynomial-time identification nationallicence Machine Learning Kluwer Academic Publishers 2/3(1987-11-01), 229-246 0885-6125 2:3<229 1987 2 10994 https://doi.org/10.1007/BF00058680 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00058680 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Rivest Ronald Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, Massachusetts, U.S.A aut NATIONALLICENCE 773 0- Machine Learning Kluwer Academic Publishers 2/3(1987-11-01), 229-246 0885-6125 2:3<229 1987 2 10994 NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1022607331053 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Rivest Ronald Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, Massachusetts, USA aut NATIONALLICENCE 773 0- Machine Learning Kluwer Academic Publishers-Plenum Publishers 2/3(1987-11-01), 229-246 0885-6125 2:3<229 1987 2 10994 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE NATIONALLICENCE NL-springer