For a given classifier h, How is the true error over a distribution D defined? \begin{align*} L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \begin{cases} \Pr[y \neq 0|x] & \text{if } h(x) = 0, \\ \Pr[y \neq 1|x] & \text{if } h(x) = 1. \end{cases} \end{align*}

I saw these two formulae here Showing that Bayes classifier is optimal Are these two equivalent?

  • $\begingroup$ Yes, the two formulas are equivalent. Now try to see why this is the case. The first step is to understand the notations. $\endgroup$ – Yuval Filmus Jun 30 at 8:16
  • $\begingroup$ Expanding the first one, we get Pr[h(x)=1, y=0] + Pr[h(x)=0, y=1]. If we assume h(x) = 0, that is Pr[h(x)=0] = 1. The term boils down to Pr[y≠0/h(x)=0] which is different from Pr[y≠0/x] right? $\endgroup$ – Shiv Tavker Jun 30 at 8:24

The first line should read $$ \Pr_{x,y \sim D}[h(x) \neq y]. $$ (This is assuming that the classifier is deterministic.)

We can sample $x,y \sim D$ in two steps: first sample $x \sim D'$, and then sample $y \sim C_x$, where $C_x$ is a distribution depending on $x$.

The second line expresses the idea $$ \operatorname*{\mathbb{E}}_{x \sim D'} \Pr_{y \sim C_x}[y \neq h(x)] $$ in an elaborate way.

Both of these are the same, and equal to $$ \operatorname*{\mathbb{E}}_{x \sim D'} \operatorname*{\mathbb{E}}_{y \sim C_x} 1_{h(x) \neq y}. $$

  • $\begingroup$ So should there not be a term, Pr(x) multiplied in the RHS which will account for the probability of sampling that specific x from the distribution D'. I agree that it doesn't have anything to do with the classifier h and hence while proving that the classifier is most optimal we can ignore that. $\endgroup$ – Shiv Tavker Jun 30 at 18:10
  • $\begingroup$ It’s there, hiding in the expectation operator. $\endgroup$ – Yuval Filmus Jun 30 at 18:13
  • $\begingroup$ I am bit confused with the notation of expectation operator. Can you please clarify if the two expectation operators defined the same? $\endgroup$ – Shiv Tavker Jun 30 at 18:17
  • $\begingroup$ Exactly the same. Expectation has only one meaning. $\endgroup$ – Yuval Filmus Jun 30 at 18:19
  • $\begingroup$ Please explain me this. Pr[y≠h(x)] = summation over all x Pr[y≠h(x)/x]*Pr[x]. I can right the term as E[Pr[y≠h(x)/x]]. This expectation is over all possible x correct? How does the outer expectation account for this? $\endgroup$ – Shiv Tavker Jun 30 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.