Decision list

Decision lists are a representation for Boolean functions which can be easily learnable from examples.^[1] Single term decision lists are more expressive than disjunctions and conjunctions; however, 1-term decision lists are less expressive than the general disjunctive normal form and the conjunctive normal form.

The language specified by a k-length decision list includes as a subset the language specified by a k-depth decision tree.

Learning decision lists can be used for .^[2]

Definition[]

A decision list (DL) of length $r$ is of the form:

if  $f 1$  then 
    output  $b 1$ 
else if  $f 2$  then
    output  $b 2$ 
...
else if  $f r$  then
    output  $b r$

where $f i$ is the $i$ th formula and $b i$ is the $i$ th boolean for $i\in \{1...r\}$ . The last if-then-else is the default case, which means formula $f r$ is always equal to true. A $k$ -DL is a decision list where all of formulas have at most $k$ terms. Sometimes "decision list" is used to refer to a 1-DL, where all of the formulas are either a variable or its negation.

References[]

^ Ronald L. Rivest (Nov 1987). "Learning decision lists" (PDF). Machine Learning. 2 (3): 229–246. doi:10.1023/A:1022607331053.
^ Adam R. Klivans and Rocco A. Servedio, "Toward Attribute Efficient Learning of Decision Lists and Parities", Journal of Machine Learning Research 7:12:587-602 ACM Digital Library full text

This artificial intelligence-related article is a stub. You can help Wikipedia by .

[1] Ronald L. Rivest (Nov 1987). "Learning decision lists" (PDF). Machine Learning. 2 (3): 229–246. doi:10.1023/A:1022607331053.

[2] Adam R. Klivans and Rocco A. Servedio, "Toward Attribute Efficient Learning of Decision Lists and Parities", Journal of Machine Learning Research 7:12:587-602 ACM Digital Library full text

[1]

[2]

Decision list

Definition[]

See also[]

References[]