Decision list

Decision lists are a representation for Boolean functions^[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 attribute efficient learning^[2].

Definition

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

if f1 then output b1
else if f2 then output b2
...
else if fr then output br

where f_i is the ith formula and b_i is the ith 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

1. ^ Rivest R. (1987) _Learning decision lists_ Machine Learning pp. 229-246
2. ^ A. Klivans and R. Servedio. (2004) _Toward Attribute-Efficient Learning of Decision Lists and Parities._ Seventeenth Annual Conference on Computational Learning Theory (COLT), 2004, pp. 234-248.