Decision list

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 fi is the ith formula and bi is the ith boolean for i \in \{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.

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.



Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Edit decision list — An edit decision list or EDL is a way of representing a film or video edit. It contains an ordered list of reel and timecode data representing where each video clip can be obtained in order to conform the final cut.EDLs are created by offline… …   Wikipedia

  • Edit Decision List — Eine Schnittliste, engl. Edit Decision List (EDL), ist die Beschreibung einer Schnittfassung eines Films oder Videos. Sie beinhaltet eine Liste von Bildnummern oder Timecodes, die beschreibt, wie Ausschnitte von Quell Filmrollen oder Videobändern …   Deutsch Wikipedia

  • 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… …   Wikipedia

  • Edit Decision List — F/A/V The list of SMPTE codes, in footage and frames, and including instructions for fades, dissolves and other special effects which corresponds to all the segments that the editor of a film or videotape production has decided to use in the… …   Audio and video glossary

  • Edit Decision List (EDL) — PP A list of edits that describes how to piece together the sequence from the source footage. This is useful for negative cutting, grading and online editing …   Audio and video glossary

  • List of film topics — This is a list of film related topics. National cinemas | glossary | Lists... | genres/plots | personnel | details | success | recognition | links | geography | other | see also National and regional cinemas: *African Cinema *Cinema of Albania… …   Wikipedia

  • List of environmental agreements — List of international environmental agreements. Most of the following agreements are legally binding. Agreements are listed in both alphabetical order and in order of topic.These lists need tidying up and making congruent with one… …   Wikipedia

  • Decision-making software — (DMS) is a term integrating decision analysis tools to facilitate a person s decision making process, which results in a choice of a course of action or a variant among several alternatives. DMS belongs to the class of decision support systems… …   Wikipedia

  • List of Bilderberg attendees — is a list of prominent persons who have attended one or more conferences organized by the Bilderberg Group. The list is currently organized by category. It is not a complete list and it includes both living and deceased people. Where known, the… …   Wikipedia

  • List of National Historic Landmarks in Alabama — …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”