Decision lists are a representation for Boolean functions which can be easily learnable from examples. 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.

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 fi is the ith formula and bi is the ith boolean for . The last if-then-else is the default case, which means formula fr 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.


This article uses material from the Wikipedia article Decision list, which is released under the Creative Commons Attribution-Share-Alike License 3.0.