# True Error of a binary classifier

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?

• Yes, the two formulas are equivalent. Now try to see why this is the case. The first step is to understand the notations. – Yuval Filmus Jun 30 at 8:16
• 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? – 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}.$$

• 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. – Shiv Tavker Jun 30 at 18:10
• It’s there, hiding in the expectation operator. – Yuval Filmus Jun 30 at 18:13
• I am bit confused with the notation of expectation operator. Can you please clarify if the two expectation operators defined the same? – Shiv Tavker Jun 30 at 18:17
• Exactly the same. Expectation has only one meaning. – Yuval Filmus Jun 30 at 18:19
• 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? – Shiv Tavker Jun 30 at 18:29