Understanding no free lunch theorem in Duda et al's Pattern Classification

Question

I have some questions about the notations used in Section 9.2 Lack of Inherent Superiority of Any Classifier in Duda, Hart and Stork's Pattern Classification. First let me quote some relevant text from the book:

• For simplicity consider a two-category problem, where the training set $D$ consists of patterns $x^i$ and associated category labels $y_i = ± 1$ for $i = 1,..., n$ generated by the unknown target function to be learned, $F(x)$, where $y_i = F(x^i)$.
• Let $H$ denote the (discrete) set of hypotheses, or possible sets of parameters to be learned. A particular hypothesis $h(x) \in H$ could be described by quantized weights in a neural network, or parameters 0 in a functional model, or sets of decisions in a tree, and so on.
• Furthermore, $P(h)$ is the prior probability that the algorithm will produce hypothesis $h$ after training; note that this is not the probability that $h$ is correct.
• Next, $P(h|D)$ denotes the probability that the algorithm will yield hypothesis $h$ when trained on the data $D$. In deterministic learning algorithms such as the nearest-neighbor and decision trees, $P(h|D)$ will be everywhere zero except for a single hypothesis $h$. For stochastic methods (such as neural networks trained from random initial weights), or stochastic Boltzmann learning, $P(h|D)$ can be a broad distribution.
• Let $E$ be the error for a zero-one or other loss function.

The expected off-training-set classification error when the true function is $F(x)$ and the probability for the $k$th candidate learning algorithm is $P_k(h(x)|D)$ is given by $$ \mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D) $$

Theorem 9.1. (No Free Lunch) For any two learning algorithms $P_1 (h |D)$ and $P_2(h|D)$, the following are true, independent of the sampling distribution $P(x)$ and the number $n$ of training points:

1. Uniformly averaged over all target functions $F$, $\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n) = 0$

2. For any fixed training set $D$, uniformly averaged over $F$, $\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D) = 0$

Part 1 is actually saying $$\sum_F \sum_D P(D|F) [\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n)] = 0$$

Part 2 is actually saying $$\sum_F [\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D)] = 0$$

My questions are

1. In the formula of $\mathcal{E}_k(E|F,n)$, i.e. $$ \mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D), $$ can I replace $P_k(h(x)|D)$ with $P_k(h|D)$ and move it outside the sum $\sum_{x \notin D}$, because it is really a distribution of $h$ over $H$ given $D$ for the $k$th stochastic learning algorithm?
2. Given that the $k$th candidate learning algorithm is a stochastic method, why in the formula of $\mathcal{E}_k(E|F,n)$, there is no sum over $h$, i.e. $\sum_{h \in H}$?

3. How are $\mathcal{E}_i (E|F, D)$ and $\mathcal{E}_i (E|F, n)$ different from each other?

   Does $\mathcal{E}_i (E|F, D)$ mean the off-training error rate given a training set $D$?

   Does $\mathcal{E}_i (E|F, n)$ mean the off-training error rate, average over all training set given a training size $n$? If yes, why does part 1 in NFL theorem average $\mathcal{E}_i (E|F, n)$ over training sets again by writing $\sum_D$, and why in the formula for $\mathcal{E}_k(E|F,n) $, there is no average over all training set given a training size $n$?

4. In part 1 of NFL theorem, does $\sum_D$ mean summing over all training sets with a fixed training size $n$?
5. If further summing over all possible values in $\mathbb{N}$ of training size $n$ in part 1, the result is still 0, right?
6. In the formula of $\mathcal{E}_k(E|F,n)$, if I change $\sum_{x \notin D}$ to $\sum_x$, i.e. $x$ is not necessarily restricted to be outside the training set, will both parts in NFL theorem still be true?
7. If the true relation between $x$ and $y$ are not assumed to be a deterministic function $F$ as $y=F(x)$, but instead conditional distributions $P(y|x)$, or a joint distribution $P(x,y)$ which is equivalent to knowing $P(y|x)$ and $P(x)$ (also see my another question), then I can change $\mathcal{E}_k (E|F,n)$ to be $$ \mathcal{E}_k(E|P(x,y),n) = \mathcal{E}_{x,y} [1-\delta(y, h(x))] P_k(h(x)|D) $$ (with the strange $P_k(h(x)|D)$ pointed out in part 1 and 2). Are the two parts in NFL theorem still true?

Thanks and regards!

Answer 1

I will answer the questions that I think I know the answers to.

1. This answer is no because you are picking an $x$ that wasn't part of the fit set $D$ and so $h$ depends on $x$.
2. $h$ is only evaluated at the values $x$ in the test set to obtain the expected error rate so it is not evaluated over the entire set $H$ but only at the discrete set of $x$'s in the test set.
3. $\mathcal{E}_i(E|F, D)$ is the expected off training set error rate given the function $F$ and the training set $D$. But $\mathcal{E}_i(E|F, n)$ I think is different because you are only conditioning on the number of training points $n$ and not the actual $x$ values. But this is puzzling given the subsequent statements.
4. $D$ is the set of training vectors. There are $n$ training vectors in $D$. So you are summing over the fixed $n$ training vectors in $D$. There is only one set $D$.
5. I think the answer to 5 is no. The notation seems to be a bit confusing.

Can't comment on 6 and 7.