5
$\begingroup$

I have a class assignment to provide a proof that Bayes classifier for the two label version is optimal in that it's error rate is always ${\le}$ any other classifier.

I've never worked through a proof before, or written one. I have a proof I've found online that I'm trying to understand. http://www.ee.columbia.edu/~vittorio/BayesProof.pdf

The exact question posed is this:

The true rate of error for a classifier ${h}$ is: ${L(h) = Pr ({h(X) = Y })}$

Consider the special case where ${Y \in y = \{0,1\}}$. Let

${r(x) = Pr(Y = 1 | X=x)}$

In the Bayes classification rule ${h^*}$ is

${h^*(x) = \{1\ \text{if}\ r(x) > 0.5, otherwise\ 0\}}$

Prove that if h is any other classifier ${L(h^*) \le L(h)}$.

The proof I have is this, my questions are below:

  1. function ${h: IR^d \mapsto \{0,1\}}$
  2. ${Pr(h(X) \neq Y | X=x) = 1 - Pr(h(X) = Y | X=x)}$
  3. ${1-Pr(h(X) = Y | X) = 1 - Pr(h(X) = 1, Y = 1 | X=x) - Pr(h(X) = 0, Y = 0)}$
  4. assume WLOG ${h(x) = 1}$ then ${Pr(h(x) = 0, Y = 0 | X=x) = 0}$
  5. ${Pr(h(X) = 1) = 0}$??
  6. ${Pr(h(X) = 0, Y = 0 | X=x) = Pr(h(X) = 0 | X=x)Pr(Y = 0 | X=x)}$
  7. ${Pr(h(x) = 1, Y = 1 | X=x) = Pr(Y = 1 | X=x)}$ - because ${Pr(h(x) = 1 | X=x) = 1}$.
  8. ${\forall x: h(x) = 1, Pr(h(X) = k, Y = k | X=x) = Pr(h(X) = k | X=x)Pr(Y = k | X=x)}$
  9. Same ${\forall x: h(x) = 0}$
  10. if ${1_A}$ is an indicator function:
  11. ${1-Pr(h(X) = Y | X) = 1-(1_{h(x) = 1}Pr(Y = 1 | X=x) + 1_{h(x) = 0}Pr(Y = 0 | X = x))}$
  12. now subtract ${Pr(h(x) = Y | X=x)}$ from ${Pr(h^*(X) = Y | X=x)}$
  13. ${Pr(h^*(X) = Y | X=x) - Pr(h(X) = Y | X=x)}$

= ${Pr(Y = 1 | X=x)(1_{h^*(x)=1} - 1_{h(x)=1})}$ + ${Pr(Y = 0 | X=x)(1_{h^*(x)=0} - 1_{h(x)=0})}$

  1. Since ${Pr(Y = 1 | X=x) = 1 - Pr(Y = 0 | X=x)}$:

${Pr(h^*(X) = Y | X=x) - Pr(h(X) = Y | X=x)}$

= ${Pr(Y = 1 | X=x)(1_{h^*(x)=1} - 1_{h(x)=1})}$ + ${(1 - Pr(Y = 1 | X=x))(1_{h^*(x)=0} - 1_{h(x)=0})}$

  1. Similarly, ${1_{h^*(x) = 0} = 1-1_{g*(x) = 1}}$:

${Pr(h^*(X) = Y | X=x) - Pr(h(X) = Y | X=x)}$

= ${Pr(Y = 1 | X=x)(1_{h^*(x)=1} - 1_{h(x)=1})}$ + ${(1 - Pr(Y = 1 | X=x))((1 - 1_{h^*(x)=1}) - (1 - 1_{h(x)=1}))}$

= (final) ${(2Pr(Y=1 | X=x)-1)(1_{g*(x)=1}-1_{h(x)=1})}$

  1. Now: for each x

if ${Pr(Y = 1 | X=x) > 0.5}$ then by definition of Bayes decision rule: ${1_{h^*(x) = 1} = 1}$ and in general ${1_{h(x)=1} \le 1}$

if ${Pr(Y = 1 | X=x) \le 0.5}$ then by definition of Bayes decision rule: ${1_{h^*(x) = 1} = 0}$ and in general ${1_{h(x)=1} \ge 0}$

Therefore in both cases (final) ${\ge 0}$

This is my interpretation (almost exact) of the proof in the link. My Questions

1) There seems to be a bug in step 4, if we assume ${h(x) = 1}$ then the probability of ${Pr(h(x) = 1 | X=x}$ must be 1, not 0?

2) What is the purpose of indicator functions in this case, ${h}$ already maps a vector to 0 or 1, and as far as I can tell ${1_{h(x)=1}}$ always returns 1 or 0, as it indicates membership in the set ${h(x)=1}$, is this not correct?

3) Why does the formula sometimes use ${X}$ and sometimes ${x}$ I understand that ${X}$ is a ${d}$ dimensional vector of independent random variables, and ${x}$ is a single value of ${X}$ - but why is ${Pr(h(X) =1)}$ (upper case) but ${1_{h(x)=1}}$ (lower case).

4) is ${Y}$ a vector? If so, surely we should be predicting that a specific ${y = 1}$ not that the vector ${Y = 1}$.

5) No mention is made of what the Bayes classifier does until the final step, surely any proof that a is better than b must specify how a and b work? It seems like at any point in the proof I could switch ${h^*}$ with ${g}$ and get a result saying ${g \ge h^*}$

6) How do we get (final) from step 14, I recognise this is not exactly part of the proof but a simplification, but I can't see how it works.

Thanks in advance

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.