Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
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 ...


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

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 ...


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