# Tag Info

4

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) is a model of computation which describes a language. The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision ...

3

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 adapted to have a best-case complexity of $O(n)$, where $n$ is the size of the input, by simply running a preliminary check that verifies if the input instance ...

3

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 $[n]$. Because $S \subseteq [n]$, it is easy to understand $x|_S$ (as is stated in the question). This is just the usual notation for the restriction of a ...

2

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 do classification: given a 4-vector, predict a song. It might feel silly to call the songs a "category", but when you look past the naming in this particular ...

2

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 &= \sum_{k=1}^d \frac{(p_k-\hat{p}_k)^2}{\hat{p}_k}\\ \Delta_2 &= \sum_{k=1}^d \frac{(n_k-\hat{n}_k)^2}{\hat{n}_k}. \end{align*} Then $\Delta_1$ is ...

2

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, they have different properties (that follow from this difference in their definition).

2

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$ which is entirely in $S$ (this is known as path-connectedness). This defines an equivalence relation on $S$, and a connected component of $S$ is an equivalence ...

2

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 made, then the graph will have at least two connected components, and in particular, we can partition it into two non-empty sets $A_1,A_2$ with no edges between ...

2

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 right then depends on which side of the hyperplane $x_i = c$ the input is located. The possible hyperplanes which come up this way are not arbitrary – they ...

2

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 a palindrome but an arbitrary string, then you need to at least read the input and therefore $\Omega(N)$ is a trivial lower bound.

2

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 Exercise 2, suppose $f_k = X_1 \lor \cdots \lor X_k$. An optimal decision tree simulates the following algorithm: If $X_1 = 1$, output 1, else continue. If $X_2 = 1$,...

2

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. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\{0,1\}$. Each internal node has one ...

2

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 real numbers. To evaluate the decision tree on an input $(x_1,\ldots,x_n) \in \{0,1\}^n$, we just follow the tree from the root to a leaf, and output the value on ...

1

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-based minimum algorithms (in which nodes represent the comparisons and edges the results of those comparisons). This is an application of Lemma 1 here, which ...

1

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)}$.

1

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 for decision trees, since there is a simple polynomial-time algorithm for translating such trees into deterministic and decomposable Boolean circuits. For the ...

1

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 the path depth $d$ instead of $n$, and we can also save ourselves the iteration over sets with $|S|=l$ and thus improve the time complexity. Suppose we have a ...

1

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 it takes at least $\lceil \lg N \rceil$ comparisons. (Proof: given $k$ comparisons, you can only produce $2^k$ different outcomes.) Here $N=3$.

1

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 is $1$. Therefore, it is natural to say that its entropy is 1 bit. More generally, consider a random value that is distributed uniformly on the set of $n$-...

1

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}$ be the random variable corresponding to $n$ independent samples of $X$. Then $$\lim_{n\to\infty} \frac{T(X^{\otimes n})}{n}.$$ Shannon's source coding ...

1

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 particular, this shows that for $k \geq 2$,  \binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\...

1

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. Whenever the algorithm compares two elements $s<t$, the answer is always $A[s]<A[t]$ unless $s=n-1$ and $t=n$, in which case the answer is \$A[n-1]>A[...

Only top voted, non community-wiki answers of a minimum length are eligible