Difference between revisions of "Decision tree complexity"
m |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | 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. | |
| − | |||
| − | + | == Bit query decision trees == | |
| + | 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 ''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 | ||
| + | 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 [[#Deterministic decision tree complexity | deterministic decision tree complexity]] of ''f''. | ||
| + | |||
| + | == Deterministic decision tree complexity == | ||
| + | For <math>x \in \{-1,1\}^n</math> we let <math>c(A, x)</math> be the number of queries that the [[decision tree]] ''A'' (also called algorithm) asks when the input to ''f'' is ''x''. Let <math>c(A) := \max_x c(A, x)</math> be the maximum number of queries that ''A'' makes which we view as the cost of ''A'' on ''f''. This is the same as the depth of the [[decision tree]]; the maximum distance of a leaf from the root. The deterministic complexity (also called the decision tree complexity) of a Boolean function ''f'', denoted by ''D(f)'', is the minimum of ''c(A)'' over all deterministic algorithms ''A'' for ''f'', so that <math>D(f) = \min_A \max_x c(A,x).</math> | ||
| + | It can be shown that if <math>D(f)=n</math> if and only if the function ''f'' is [[evasive]].<ref>László Lovász and Neal E Young. “Lecture notes on evasiveness of graph properties”. In: arXiv preprint cs/0205031 (2002).</ref> | ||
| + | |||
| + | == Randomized decision tree complexity == | ||
| + | The randomized complexity of a Boolean function ''f'', denoted by ''R(f)'', is the minimum of ''c(A)'' over all randomized algorithms ''A'' for ''f'', so that <math>D(f) = \min_A \max_x c(A,x).</math> | ||
| + | The cost <math>c(A,x)</math> can also be seen as the expected number of queries performed on input ''x'', where we use a distribution ''D'' over deterministic algorithms, so that | ||
| + | <math>R(f) = \min_{D} \max_x \mathbb{E}_A^{D}[c(A,x)],</math><ref>Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.</ref> | ||
| + | |||
| + | == Level-''p'' complexity == | ||
| + | The level-''p''-complexity of a Boolean function ''f'', denoted by <math>D_p(f)</math>, is the minimum over all (deterministic) algorithms ''A'' for ''f'' of the expected number of questions that are asked when the input has distribution <math>\pi_p</math>, so that <math>D_p(f) = \min_A \mathbb{E}_x^{\pi_p}[c(A,x)],</math> where <math>\mathbb{E}_x^{\pi_p}[c(A,x)]</math> denotes the expectation of ''c(A,x)'' when <math>x\sim \pi_p</math>. We use the distribution <math>\pi_p</math> which means that the input bits are i.i.d. with Bernoulli distribution with parameter <math>p \in (0,1)</math>.<ref>Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.</ref> | ||
| + | |||
| + | == References== | ||
Latest revision as of 10:21, 20 March 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.
Contents
Bit query decision trees
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 deterministic decision tree complexity of f.
Deterministic decision tree complexity
For [math]x \in \{-1,1\}^n[/math] we let [math]c(A, x)[/math] be the number of queries that the decision tree A (also called algorithm) asks when the input to f is x. Let [math]c(A) := \max_x c(A, x)[/math] be the maximum number of queries that A makes which we view as the cost of A on f. This is the same as the depth of the decision tree; the maximum distance of a leaf from the root. The deterministic complexity (also called the decision tree complexity) of a Boolean function f, denoted by D(f), is the minimum of c(A) over all deterministic algorithms A for f, so that [math]D(f) = \min_A \max_x c(A,x).[/math] It can be shown that if [math]D(f)=n[/math] if and only if the function f is evasive.[1]
Randomized decision tree complexity
The randomized complexity of a Boolean function f, denoted by R(f), is the minimum of c(A) over all randomized algorithms A for f, so that [math]D(f) = \min_A \max_x c(A,x).[/math] The cost [math]c(A,x)[/math] can also be seen as the expected number of queries performed on input x, where we use a distribution D over deterministic algorithms, so that [math]R(f) = \min_{D} \max_x \mathbb{E}_A^{D}[c(A,x)],[/math][2]
Level-p complexity
The level-p-complexity of a Boolean function f, denoted by [math]D_p(f)[/math], is the minimum over all (deterministic) algorithms A for f of the expected number of questions that are asked when the input has distribution [math]\pi_p[/math], so that [math]D_p(f) = \min_A \mathbb{E}_x^{\pi_p}[c(A,x)],[/math] where [math]\mathbb{E}_x^{\pi_p}[c(A,x)][/math] denotes the expectation of c(A,x) when [math]x\sim \pi_p[/math]. We use the distribution [math]\pi_p[/math] which means that the input bits are i.i.d. with Bernoulli distribution with parameter [math]p \in (0,1)[/math].[3]
References
- ↑ László Lovász and Neal E Young. “Lecture notes on evasiveness of graph properties”. In: arXiv preprint cs/0205031 (2002).
- ↑ Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.
- ↑ Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.
