I'm reading the proof of No-Free-Lunch Theorem (quoted at the end of this question) in Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, p.37, the author wrote:

Let $C$ be a subset of $\mathcal{X}$ of size $2m$. Note that there are $T = 2^{2m}$ possible functions from $C$ to $\{0,1\}$. Denote these functions by $f_{1},...,f_{T}$. For each such function, let $D_{i}$ be a distribution over $C×\{0,1\}$ defined by:

$$ D_{i}(\{(x,y)\}) = \begin{cases} 1/|C|\text{ if }y=f_{i}(x)\\ 0 \text{ otherwise} \end{cases} $$

I'm suspecting that $D_{i}$ defined in this way is a valid distribution because even though on the surface we have $|C|(1/|C|)=1$, there's no guarantee that $f_{i}$ will return correct labels for all examples in $C$ and so the cumulative probability may less than $|C|(1/|C|) = 1$?

The Theorem stated in the book as follows:

Let $A$ be any learning algorithm for the task of binary classification with respect to the 0−1 loss over a domain X . Let m be any number smaller than $|X|/2$, representing a training set size. Then, there exists a distribution D over X ×{0,1} such that:

  1. There exists a function $f :X \to\{0,1\}$ with $L_{\mathcal{D}}(f)=0$.
  2. With probability of at least 1/7 over the choice of $S \sim D^{m}$ we have that $L_{\mathcal{D}}(A(S)) ≥ 1/8$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.