Difference between revisions of "Decision tree"
| Line 2: | Line 2: | ||
Given a function <math>f:\{-1,1\}^n \to \{-1,1\}</math>, a simple decision tree for the | Given a function <math>f:\{-1,1\}^n \to \{-1,1\}</math>, a simple decision tree for the | ||
| − | function is a binary tree whose internal nodes have labels from <math>{1, 2, . . . , n}</math> | + | function is a binary tree whose internal nodes have labels from <math>\{1, 2, . . . , n\}</math> |
| − | and whose leaves have labels from <math>{-1, 1}</math>. If a node has label ''i'', then the test | + | and whose leaves have labels from <math>\{-1, 1\}</math>. If a node has label ''i'', then the test |
performed at that node is to examine the ''i''th bit of the input. If the result is | performed at that node is to examine the ''i''th bit of the input. If the result is | ||
-1, one descends into the left subtree, whereas if the result is 1, one descends | -1, one descends into the left subtree, whereas if the result is 1, one descends | ||
Latest revision as of 12:32, 27 February 2022
A decision tree is a tree representing the logical structure of certain algorithms on various inputs. The nodes of the tree represent branch points of the computation — places where more than one outcome are possible based on some predicate of the input — and the leaves represent possible outcomes. Given a particular input, one starts at the root of the tree, performs the test at that node, and descends accordingly into one of the subtrees of the root. Continuing in this way, one reaches a leaf node which represents the outcome of the computation.
Given a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math], a simple decision tree for the function is a binary tree whose internal nodes have labels from [math]\{1, 2, . . . , n\}[/math] and whose leaves have labels from [math]\{-1, 1\}[/math]. If a node has label i, then the test performed at that node is to examine the ith bit of the input. If the result is -1, one descends into the left subtree, whereas if the result is 1, one descends into the right subtree. The label of the leaf so reached is the value of the function on the input. While it is clear that any such function f has a simple decision tree, we will be interested in simple decision trees for f which have minimal depth decision tree complexity D(f). D(f) is called the decision tree complexity of f.
- ↑ László Lovász and Neal E Young. “Lecture notes on evasiveness of graph properties”. In: arXiv preprint cs/0205031 (2002).
