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 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 fi is the ith formula and bi is the ith boolean for i∈{1...r}. 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.

## See also

* Decision stump

## References

1. ↑ Ronald L. Rivest (Nov 1987). "Learning decision lists". Machine Learning 2 (3): 229–246. doi:10.1023/A:1022607331053. http://people.csail.mit.edu/rivest/pubs/Riv87b.pdf.
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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Decision list. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Decision_list&oldid=175396"