Decision lists

Decision lists are a representation for Boolean functions [Rivest R. (1987) _Learning decision lists_ Machine Learning pp. 229-246] . 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.

Learning decision lists can be used for attribute efficient learning [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. ] .

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