4
votes
Accepted
How to convert a decision tree to an automaton?
A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context)...
- 279k
3
votes
Accepted
how does the shap algorithm work in polynomial time?
First, some notation.
A decision tree is a binary tree in which each internal node is labelled by one of $x_1,\ldots,x_n$, and has two outgoing edges labelled $0$ and $1$. Leaves are labelled with ...
- 279k
3
votes
Accepted
Lower bound and worst case scenario
When analyzing algorithms it makes little sense to consider the best-case scenario as it is very often trivial and not very informative.
You can convince yourself that almost every algorithm can be ...
- 29.6k
3
votes
In information theory, why is the entropy measured in units of bits?
Here is a simple intuition. Suppose we consider a random value that takes the values 0 or 1 with equal probability. Then this value can be represented in a single bit. Moreover, its Shannon entropy ...
D.W.♦
- 166k
3
votes
Accepted
What is the main difference between binary decision tree and binary decision diagram(BDD)?
One is a tree; one is not. A BDD is a directed acyclic graph (dag), but not necessarily a tree. This allows a BDD to be more compact, in some cases.
That's the only essential difference. Of course,...
D.W.♦
- 166k
3
votes
Accepted
What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?
It is a typo. $S$ indeed should be a subset of $[n] = \{1,2,\ldots,n\}$. On page 263, in the second sentence of their proof of Theorem 12.5, they list a 0-certificate (or 1-certificate) as a subset of ...
- 211
2
votes
Accepted
What machine learning training algorithm to use for this kind of string dataset?
You want to perform supervised learning, i.e., you have set of training examples (in this case, a set of 4-vectors with a label that corresponds to one of the 100 songs). So in particular, you want to ...
- 22.8k
2
votes
Accepted
Decision Tree Learning Deviation - Russell and Norvig
TL;DR: They are basically doing a chi-squared test to compare the distributions.
In more detail: Let's break this down into two parts, $\Delta = \Delta_1 + \Delta_2$ where
$$\begin{align*}
\Delta_1 &...
D.W.♦
- 166k
2
votes
Connected Components - Linear Decision Trees
Connected components are a concept of topology. Under the usual topology on $\mathbb{R}^n$, we say that two points $x,y \in S$ belong to the same connected component if there is a path from $x$ to $y$ ...
- 279k
2
votes
Accepted
Longest palindrome substring in logarithmic runtime complexity
If a you are given a palindrome $p$ of size $N$ (as you say in the beginning of the question), then the longest palindrome is $p$ itself and you don't need to do any computation.
If your input is not ...
- 29.6k
2
votes
Decision tree and information-theoretic lower bound
No. The outcome is the median, not the sorted list. Thus, there are only 3 possible outcomes, not 3! outcomes. The information-theoretic lower bound says that if there are N possible outcomes, then ...
D.W.♦
- 166k
2
votes
Accepted
Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
In fact, at least $n-1$ comparisons are needed. Indeed, consider the graph on the vertex set $A$ whose edges correspond to pairs of elements which were compared. If less than $n-1$ comparisons were ...
- 279k
2
votes
Accepted
decision trees and numeric attributes
Each vertex in a decision tree is associated with a question of the form "$x_i < c$?" (or "$x_i \leq c$?"), where $x_i$ is one of the input and $c$ is a constant. The decision whether to go left or ...
- 279k
2
votes
Expressivity of Polysize Decision Trees
This is not an exact characterization, but the class of languages recognizable by poly-size DT is included in $\mathrm{AC}^0$, specifically within its second level: that is, any DT can be converted to ...
- 2,231
2
votes
Accepted
Basic exercises on decision trees
ID3 is a heuristic. It is not guaranteed to generate an optimal decision tree.
Here is an algorithm for Exercise 1:
If $X_3 = 1$, then answer $2X_1-1$.
If $X_3 = 0$, then answer $2X_4-1$.
For ...
- 279k
2
votes
Accepted
Can inputs in the decision tree model be computed?
A decision tree is a special kind of "program" which computes a function, usual from $\{0,1\}^n$ to $\{0,1\}$. Let's take an example from Wikipedia:
A decision tree is a binary tree. ...
- 279k
2
votes
Accepted
Decision tree for searching element in sorted-array
You haven't really defined your computation model, so here is a suggestion.
The input to the algorithm is a sorted array $A$ of length $n$ and an element $x$.
The output is either a position $i$ such ...
- 279k
1
vote
Accepted
'Address Function' example of decision tree complexity is not clear
The decision tree that Arora and Barak mention gets as input $x,y$ and is only supposed to compute the function $f(x,y) = y_x$. It is not supposed to recover the entire input.
The decision tree ...
- 279k
1
vote
Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?
In theory, yes you should be able to create a decision tree for every comparison based sorting algorithm. You can write a program that will do so (for a fixed comparison-based sorting algorithm of ...
- 622
1
vote
Accepted
Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?
In general, a decision tree would enumerate all possible permutations $(N!)$ for given input of $N$ elements, out of which only $1$ would be desirable.
A sorting algorithm doesn't generate all ...
- 1,074
1
vote
How to come up with combination a short-circuit evaluation table?
Looking at your question again, I think you really may only need two simple rules. After reviewing these rules, then we can see how to build a table.
Note that I will write
$$(a || b) = (a \lor b)$$
$...
- 892
1
vote
how does the shap algorithm work in polynomial time?
In this paper: https://arxiv.org/pdf/2007.14045.pdf, a polynomial-time algorithm is given to compute the SHAP score for deterministic and decomposable Boolean circuits. This algorithm can also be used ...
- 11
1
vote
how does the shap algorithm work in polynomial time?
slight optimization over @yuval-filmus excellent answer.
In his comment here: https://github.com/slundberg/shap/issues/24 @sh1ng suggests an improvement. Rephrasing a bit, he's saying that we can use ...
- 369
1
vote
Why decision tree method for lower bound on finding a minimum doesn't work
In the comments I said that $n$ is the number of different possible outcomes of a minimum algorithm and that this is only a lower bound for the number of leaves of the decision trees of the comparison-...
- 549
1
vote
Why decision tree method for lower bound on finding a minimum doesn't work
Interesting question!
The way I understand this is that on sorting it happens that one comparison allows you to discard approximately a half of the possible answers. However on the case of the minimum,...
- 1,281
1
vote
Lower bound on comparison-based sorting
If there is a comparison sort whose running time is $f(n)$ on $g(n)$ of the inputs, then there are at least $g(n)$ leaves at depth at most $f(n)$, and so $g(n) \leq 2^{f(n)}$.
- 279k
1
vote
In information theory, why is the entropy measured in units of bits?
The entropy of a random variable $X$ can be described in terms of prefix-free binary encodings. Let $T(X)$ be the minimal average codeword length of a binary prefix code for $X$, and let $X^{\otimes n}...
- 279k
1
vote
Accepted
Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)
Stirling's formula shows that
$$
\binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}},
$$
where $H(p)$ is the binary entropy function:
$$
H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}.
$$
In ...
- 279k
1
vote
Decision tree complexity of deciding whether array is "zigzag"
You can prove a lower bound of $n-3$ comparisons, almost matching the trivial upper bound of $n-1$ comparisons (surely the gap can be closed with a bit more work). The proof uses an adversary argument....
- 279k
Only top scored, non community-wiki answers of a minimum length are eligible