No free lunch theorem proof

Question

Assume that learning algorithm $A$ is fixed. Let $D = \{(x_1,y_1),...,(x_N,y_N)\}$, $F$ is set of a data-generating functions(meaning $f \in F$ then $f(x_i) = y_i$ and that functions in $F$ are consistent with the data )and $h:X\rightarrow Y$ is a classifier trained by the algorithm $A$. $L(f(x),y) $ is 1/0-loss function. Then i want to show that $\frac{1}{|F|}\sum_{f \in F}E[L(f(q),h(q))] = \frac{1}{2}$ where $q$ is a test point such that $x_i \neq q$ for all $i$.

My attempt $E[L(f(q),h(q))] = E[I_{f(q) \neq h(q) }(q)] = P(\{f(q) \neq h(q))$ where $I_{f(q) \neq h(q) }(q)$ is an indicator function. How should i evaluate $P(\{f(q) \neq h(q)\})$? My intuition says that $P(\{f(q)\neq h(q)\}) = \frac{1}{2}$, but i cant come up with a formal argument for that.

Any help is apperciated.

Update: Could i argue that if $h$ just makes a random-guess then the probability that the guess is correct is $\frac{1}{2}$ so therefore $P(\{h(q) \neq f(q)\}) = \frac{1}{2}$ and then the claim follows.

Update2: If i think the problem this way: for all $f \in F$ there exists a classifier $h$ which is trainable by the algorithm $A$. I still need the fact that how good the classifier $h$ is, which is quite hard to find out

Update3 I assume that data-generating functions $f$ are equally likely and that $h$ is fixed. I still think how i define probability of goodness of $h$ given $f$.

Answer 1

For the usual set-up of the No Free Lunch theorem there's less here than meets the eye. The domain ${\cal X}$ is discrete, ${\cal F}$ is the (finite) set of all (deterministic) functions from ${\cal X}$ to $\{0,1\}$ such that $f(x_i)=y_i$ for data in the training set. That is, for every $x$ not in the training set, ${\cal F}$ contains exactly as many functions with $f(x)=1$ and $f(x)=0$, and that's why better-than-chance prediction is impossible.

In the question as given it's not clear what is random in the expectation, but the basic argument will be the same whatever it is. If you want the average performance of $h$ over all possible test data (or, equivalently, over a random sample of test data drawn with equal probability from all possibilities), then you will be accurate exactly half the time with a binary $Y$. This is true regardless of your algorithm for choosing $h$: whatever $h$ is, for any given $x$ either $h(x)=1$ or $h(x)=0$ and each option is wrong exactly half the time.

The No Free Lunch theorem isn't actually very useful because we never actually care about the average performance with equal weight on all possible test data. It's mainly interesting because it shows you can't possibly have a proof that an algorithm A_1 is uniformly better than another algorithm A_2 (only that it's better on some interesting subclass of problems)

Answer 2

Your question is pretty ill-posed as stated, but answerable with some additional assumptions. In this answer, I will give a "mathematically formal" version of the (correct, +1) argument given by @Thomas Lumley above, while highlighting what assumptions are used and when.

First, I will denote $h:=h_A(D)$ to make it clear that it is the classifier learned by algorithm $A$ from sample $D$. Next, I'll assume that $Y = \{0,1\}$ and that $q$ is a fixed point in $X$ (not random) which is different from all $x_i$.
So, with these assumptions, the quantity you want to compute is $$\frac{1}{|F|}\sum_{f \in F}\mathbb P\big[f(q)=1-h_A(D)[q]\mid D\big] \tag1 $$ (Note the conditional probability here : the classifier $h_A$ is a function of the sample $D$ so the probability is conditional on it.)

Now, let $U$ be the uniform distribution over the set of functions $F$ (that is, for any $f\in F, \mathbb P(U=f)=1/|F|$). $(1)$ is now given by : $$\mathbb E_{f\sim U}\left[\mathbb P(f(q)=1-h_A(D)[q]\mid D)\right]\tag2 $$ But now notice that conditional on $D$, $1-h_A(D)[q] $ is a constant : it is either $1$ or $0$. This is where we need the additional assumption stated in @Thomas Lumley's answer above that $F$ is the set of all deterministic functions $X\to Y$ that agree with the sample $D$.
(Here, since you assume that $|F|$ is finite, that also implies that $|X|$ is finite, which is again a common assumption for some versions of the NFL theorem, as explained by Thomas).

With this extra assumption, it follows from the law of total expectation that $$\begin{align}&\quad\ \, \mathbb E_{f\sim U}\left[ \mathbb P(f(q)=1-h_A(D)[q])\mid D\right]\\ &=\mathbb E_{f\sim U}\left[\mathbb P(f(q)=1)\mid h_A(D)[q]=0, D\right]\cdot\mathbb P(h_A(D)[q]=0\mid D)\\ &+\mathbb E_{f\sim U}\left[\mathbb P(f(q)=0)\mid h_A(D)[q]=1, D\right]\cdot\mathbb P(h_A(D)[q]=1\mid D)\\ &=1/2\cdot\mathbb P(h_A(D)[q]=0\mid D)+1/2\cdot\mathbb P(h_A(D)[q]=1\mid D)\\ &=1/2\end{align}$$ which implies the desired result.

Answer 3

Let $q \in X$ be a fixed test point and let $h$ be a classifier trained by the fixed learning algorithm $A$. Notice that $1_{\{f(q) \neq h(q)\}}(q) = (\frac{f(q)-h(q)}{2})^2$ since $f(x)^2=h(x)^2 = 1$ for all $x \in X$. Then we have that $\frac{1}{|F|}\sum_{f \in F}E[L(f(q),h(q))] = \frac{1}{|F|}\sum_{f \in F} E[1_{\{f(q) \neq h(q) \}}(q)] = \frac{1}{|F|}\sum_{f \in F} (\frac{f(q)-h(q)}{2}) ^ 2 = \frac{1}{2|F|}\sum_{f \in F}(1-h(q)f(q)) = \frac{1}{2}$

since $\sum_{f \in F}f(q) = 0$.