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
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...
and the
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
.
The language specified by a k-length decision list includes as a subset the language specified by a k-depth
decision tree
A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains condit ...
.
Learning decision lists can be used for
attribute efficient learning
Attribute may refer to:
* Attribute (philosophy), an extrinsic property of an object
* Attribute (research), a characteristic of an object
* Grammatical modifier, in natural languages
* Attribute (computing), a specification that defines a prope ...
.
[Adam R. Klivans and Rocco A. Servedio, "Toward Attribute Efficient Learning of Decision Lists and Parities", ''Journal of Machine Learning Research'' 7:12:587-60]
ACM Digital Libraryfull text
/ref>
Definition
A decision list (DL) of length is of the form:
if then
output
else if then
output
...
else if then
output
where is the th formula and is the th boolean for . The last if-then-else is the default case, which means formula is always equal to true. A -DL is a decision list where all of formulas have at most terms. Sometimes "decision list" is used to refer to a 1-DL, where all of the formulas are either a variable or its negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
.
See also
* Decision stump
A decision stump is a machine learning model consisting of a one-level decision tree. That is, it is a decision tree with one internal node (the root) which is immediately connected to the terminal nodes (its leaves). A decision stump makes a predi ...
References
Machine learning
{{AI-stub