7
$\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$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.