<p>Let <span class="math-container">$\Omega$</span> be a finite set and <span class="math-container">$F=\{0,1\}^\Omega$</span> be the (finite) collection of all Boolean functions on <span class="math-container">$\Omega$</span>. We claim that for any <span class="math-container">$h\in F$</span> and any distribution <span class="math-container">$P$</span> on <span class="math-container">$\Omega$</span>, the following holds:
<span class="math-container">$$
(*)=\frac{1}{|F|}\sum_{f\in F}\mathbb{E}_{x\sim P}1[h(x)\neq f(x)]=\frac12.
$$</span>
Indeed, we can treat <span class="math-container">$\frac{1}{|F|}\sum_{f\in F}$</span> as taking an expectation over <span class="math-container">$f\sim Q$</span>, where <span class="math-container">$Q$</span> is the uniform distribution over <span class="math-container">$F$</span>. By symmetry and Fubini's theorem (i.e., exchanging the order of the 2 expectations), this is equivalent to labeling each point <span class="math-container">$x$</span> independently with a Bernoulli<span class="math-container">$(1/2)$</span> label <span class="math-container">$B(x)$</span>. Thus,
<span class="math-container">$$
(*)=\mathbb{E}_{x\sim P}1[h(x)\neq B(x)]=\frac12.
$$</span></p>

CC BY-SA 4.0
2022-04-18T10:03:35.863Z
ah so $f$ is a r.v and the test point.
voroshilov
CC BY-SA 4.0
2022-04-18T10:44:29.500Z
Yes, the label of any $x\in\Omega$ is a r.v. *not depending* on $x$.
Aryeh
CC BY-SA 4.0
2022-04-18T13:49:56.547Z
btw if we keep data-generating function fixed and take the average over all learning algorithms $A$ would this same argument work?
voroshilov
CC BY-SA 4.0
2022-04-18T14:07:00.400Z
You have to formalize things correctly. For one thing, you have to assume there's a finite set of learning algorithms.
Aryeh
CC BY-SA 4.0
2022-04-18T14:29:10.420Z
if $A$ is set of all possible algorithms then $\{ a(D) \in A\}$ is equivalent to set of classifiers where a is an algorithm and  D a fixed dataset(since algorithm $a$ outputs a classifier $h$ with dataset $D$). Or is there a case where two different algorithms output same classifier?
voroshilov
CC BY-SA 4.0
2022-04-18T14:37:47.150Z
Formally, an algorithm is distinct from a classifier: the former maps a labeled sample to a classifier, while the latter maps a point X to a point Y. However, in the finite case, one can cheat a little and conflate the two (e.g., by stipulating that an algorithm only looks at the *set* of labeled examples -- rather than the multiset [with repeats] or the sequence [where the order matters]). Under those fixes, I think my argument works for the set of all algs as well.
Aryeh
CC BY-SA 4.0
2022-04-22T11:20:38.347Z
do you think the solutions which i wrote is correct https://stats.stackexchange.com/questions/571804/no-free-lunch-theorem-proof ? not 100% of the last step since $h$ depends from $f$.
voroshilov
CC BY-SA 4.0
2022-04-23T17:48:02.237Z
Looks like you’re getting some pretty good feedback there.
Aryeh
CC BY-SA 4.0
2022-04-18T09:29:05.147Z
2022-04-18T09:29:05.147Z
Aryeh
<p>Assume that learning algorithm <span class="math-container">$A$</span> is fixed. Let <span class="math-container">$D = \{ (x_1,y_1),\dots, (x_N,y_N) \}$</span>, <span class="math-container">$F$</span> is set of a data-generating functions and <span class="math-container">$h : X \to Y$</span> is a classifier. <span class="math-container">$L(f(x),y) $</span> is <span class="math-container">$1$</span>/<span class="math-container">$0$</span>-loss function. Then I want to show that <span class="math-container">$$\frac{1}{|F|}\sum_{f \in F} E [L(f(q),h(q))] = \frac{1}{2}$$</span> where <span class="math-container">$q$</span> is a test point such that <span class="math-container">$x_i \neq q$</span> for all <span class="math-container">$i$</span>.</p>
<hr />
<p><strong>My attempt</strong></p>
<p><span class="math-container">$$E[L(f(q),h(q))] = E[I_{f(q) \neq h(q) }(q)] = P(\{f(q) \neq h(q))$$</span> where <span class="math-container">$I_{f(q) \neq h(q) }(q)$</span> is an indicator function. How should i evaluate <span class="math-container">$P(\{f(q) \neq h(q)\})$</span>?</p>
<p>My intuition says that <span class="math-container">$P(\{f(q)\neq h(q)\}) = \frac{1}{2}$</span>, but I cant come up with a formal argument for that. Any help would be appreciated.</p>

CC BY-SA 4.0
2022-04-17T06:35:48.237Z
You will obviously need some assumptions on F and the sampling distribution P. What if F={f} is a singleton, for example? What if P puts all of its mass on 1 point?
Aryeh
CC BY-SA 4.0
2022-04-17T07:19:58.290Z
Yeah then it could happen that the expected loss is 0. Any assumptions for F and P isnt given which is strange.
voroshilov
CC BY-SA 4.0
2022-04-17T07:25:08.737Z
Well, it's *your* problem, so you get to make up the rules. Or is it homework?
Aryeh
CC BY-SA 4.0
2022-04-17T07:26:09.360Z
Its a homework, therefore i find this quite strange that assumptions arent given.
voroshilov
CC BY-SA 4.0
2022-04-17T07:27:22.870Z
Why don't you post the whole problem, including source -- we'll see what we can do...
Aryeh
CC BY-SA 4.0
2022-04-17T07:31:21.213Z
https://imgur.com/a/lWHkiuN the problem
voroshilov
CC BY-SA 4.0
2022-04-17T07:32:01.690Z
Where's this from? Book, page?
Aryeh
CC BY-SA 4.0
2022-04-17T07:36:17.077Z
not a book, an exercise sheet problem 4 https://api11.ilovepdf.com/v1/download/zstzsr3vAvly9fgcsw1bsdq6ynbnb71mpsyyl71hgtl7vttfzqrnzAt80m7qpAt7fs71t7c7tAn8xp8r3z9rpx8hxr8z2swns4rrth4xvxwc7cy0ts9sysyvwth9jbnsmA7c6b10w7d2ws9yc555xm5wh2gvj89z9hf2qm7gftj3vb1j2pd1
voroshilov
CC BY-SA 4.0
2022-04-17T07:53:13.293Z
OK, it's clear from the text that it's trying to steer you in the direction of Wolpert's papers. I found both of them here:
https://gofile.io/d/W5FbNO
You should be able to supply the relevant assumptions and quote the relevant results (acknowledging the source, of course).
As I said, without additional assumptions it's not correct.
Aryeh
CC BY-SA 4.0
2022-04-17T07:56:37.777Z
ok thanks for the help :)
voroshilov
CC BY-SA 4.0
2022-04-17T18:23:49.817Z
Ok i think i need to assume that data-generating functions $f$ are uniformly distributed, but im still thinking how i can define probability of "goodness" of h given f.
voroshilov
CC BY-SA 4.0
2022-04-17T19:21:06.070Z
Presumably, that would be the “agreement” (or sample error) of $h$ w.r.t. $f$.
Aryeh
CC BY-SA 4.0
2022-04-18T07:13:23.573Z
I dont see why i need the fact about the distribution of the data-generating functions since we are summing over all of them. And in all cases $f_i \in F$ generates $D_{f_{i}}$ anyways. Is the set $F$ a distribution instead of an original set? I think im missunderstanding something
voroshilov
CC BY-SA 4.0
2022-04-18T07:35:59.003Z
and with the test point $q$ the classifier $h$ can make any amount of mistakes 1 or 0.
voroshilov
CC BY-SA 4.0
2022-04-18T09:30:01.273Z
I posted an answer. Your original question didn't make it clear that $F$ is the set of *all* possible functions, which is crucial.
Aryeh
<machine-learning>
No free lunch theorem
voroshilov
# No free lunch theorem

(Asked by: username_0 on 2022-04-15)

Assume that learning algorithm $A$ is fixed. Let $D = \{ (x\_1,y\_1),\dots, (x\_N,y\_N) \}$, $F$ is set of a data-generating functions and $h : X \to Y$ is a classifier. $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 would be appreciated.

**Tags:** machine-learning

> **Comments:**
> **username_1**: You will obviously need some assumptions on F and the sampling distribution P. What if F={f} is a singleton, for example? What if P puts all of its mass on 1 point?  
> **username_0**: Yeah then it could happen that the expected loss is 0. Any assumptions for F and P isnt given which is strange.  
> **username_1**: Well, it's *your* problem, so you get to make up the rules. Or is it homework?  
> **username_0**: Its a homework, therefore i find this quite strange that assumptions arent given.  
> **username_1**: Why don't you post the whole problem, including source -- we'll see what we can do...  
> **username_0**: https://imgur.com/a/lWHkiuN the problem  
> **username_1**: Where's this from? Book, page?  
> **username_0**: not a book, an exercise sheet problem 4 https://api11.ilovepdf.com/v1/download/zstzsr3vAvly9fgcsw1bsdq6ynbnb71mpsyyl71hgtl7vttfzqrnzAt80m7qpAt7fs71t7c7tAn8xp8r3z9rpx8hxr8z2swns4rrth4xvxwc7cy0ts9sysyvwth9jbnsmA7c6b10w7d2ws9yc555xm5wh2gvj89z9hf2qm7gftj3vb1j2pd1  
> **username_1**: OK, it's clear from the text that it's trying to steer you in the direction of Wolpert's papers. I found both of them here: https://gofile.io/d/W5FbNO You should be able to supply the relevant assumptions and quote the relevant results (acknowledging the source, of course). As I said, without additional assumptions it's not correct.  
> **username_0**: ok thanks for the help :)  
> **username_0**: Ok i think i need to assume that data-generating functions $f$ are uniformly distributed, but im still thinking how i can define probability of "goodness" of h given f.  
> **username_1**: Presumably, that would be the “agreement” (or sample error) of $h$ w.r.t. $f$.  
> **username_0**: I dont see why i need the fact about the distribution of the data-generating functions since we are summing over all of them. And in all cases $f_i \in F$ generates $D_{f_{i}}$ anyways. Is the set $F$ a distribution instead of an original set? I think im missunderstanding something  
> **username_0**: and with the test point $q$ the classifier $h$ can make any amount of mistakes 1 or 0.  
> **username_1**: I posted an answer. Your original question didn't make it clear that $F$ is the set of *all* possible functions, which is crucial.  

---

## 1 answers

### Answer by username_1 on 2022-04-18. Score: 0 | Accepted answer

Let $\Omega$ be a finite set and $F=\{0,1\}^\Omega$ be the (finite) collection of all Boolean functions on $\Omega$. We claim that for any $h\in F$ and any distribution $P$ on $\Omega$, the following holds:
$$
(\*)=\frac{1}{|F|}\sum\_{f\in F}\mathbb{E}\_{x\sim P}1[h(x)\neq f(x)]=\frac12.
$$
Indeed, we can treat $\frac{1}{|F|}\sum\_{f\in F}$ as taking an expectation over $f\sim Q$, where $Q$ is the uniform distribution over $F$. By symmetry and Fubini's theorem (i.e., exchanging the order of the 2 expectations), this is equivalent to labeling each point $x$ independently with a Bernoulli$(1/2)$ label $B(x)$. Thus,
$$
(\*)=\mathbb{E}\_{x\sim P}1[h(x)\neq B(x)]=\frac12.
$$

> **Comments:**
> **username_0**: ah so $f$ is a r.v and the test point.  
> **username_1**: Yes, the label of any $x\in\Omega$ is a r.v. *not depending* on $x$.  
> **username_0**: btw if we keep data-generating function fixed and take the average over all learning algorithms $A$ would this same argument work?  
> **username_1**: You have to formalize things correctly. For one thing, you have to assume there's a finite set of learning algorithms.  
> **username_0**: if $A$ is set of all possible algorithms then $\{ a(D) \in A\}$ is equivalent to set of classifiers where a is an algorithm and  D a fixed dataset(since algorithm $a$ outputs a classifier $h$ with dataset $D$). Or is there a case where two different algorithms output same classifier?  
> **username_1**: Formally, an algorithm is distinct from a classifier: the former maps a labeled sample to a classifier, while the latter maps a point X to a point Y. However, in the finite case, one can cheat a little and conflate the two (e.g., by stipulating that an algorithm only looks at the *set* of labeled examples -- rather than the multiset [with repeats] or the sequence [where the order matters]). Under those fixes, I think my argument works for the set of all algs as well.  
> **username_0**: do you think the solutions which i wrote is correct https://stats.stackexchange.com/questions/571804/no-free-lunch-theorem-proof ? not 100% of the last step since $h$ depends from $f$.  
> **username_1**: Looks like you’re getting some pretty good feedback there.  

---

