Problem: Consider a classifier C with K class labels trained on $(Y_i, X_i)$, $i = 0, . . . , n.$ Let $(Y_0, x_0)$ be a test observation and $\hat{Y}_0$ be the predicted class label (by $C$ ) for $x_0$. Prove that the probability of misclassification $P(\hat{Y}_0 \ne Y_0|x_0)$ satisfies $P(\hat{Y}_0 \ne Y_0|x_0) ≥ 1 − \max_{\{ k=1,...,K \}} P(Y_0 = k|x_0)$ .

My thinking: Let us suppose we have K classes $C_0, C_1, C_2,…C_{k-1}$. Then Bayes formula gives us:

$P(Y_0 = k|x_0)= \frac{P(x_0)\times P(Y_0=k)}{\sum^{k-1}_k{P(x_0)\times P(Y_0=k)}}$

The Bayes Rule for Minimum Error is to classify a case as belonging to $C_j$ if

${P(x_0)\times P(Y_0=k)} \ge \max_{\{ k=1,...,K \}}{P(x_0)\times P(Y_0=k)} $

Then I could not figure it to move further. I appreciate your suggestions. Thanks!


Substitute $P(\hat Y_0\neq Y_0|x_0)=1-P(\hat Y_0=Y_0|x_0)$, and you get $$P(\hat Y_0=Y_0|x_0)\leq \max_{k=1..K}P(Y_0=k|x_0)$$ which is true because $Y_0\in\{1...K\}$.

  • $\begingroup$ So I don't need Bayes formula? I just need to substitute the expression you gave in the probability of misclassification's condition. Right? $\endgroup$ – Simpson's Paradox Oct 28 '20 at 20:40
  • $\begingroup$ Yes, it's just $1-P(X=x)=P(X\neq x)$, did you notice that? $\endgroup$ – gunes Oct 28 '20 at 20:41
  • $\begingroup$ Yes, I did! I was kinda confused with the problem statement. I got it now. Thank you so much! $\endgroup$ – Simpson's Paradox Oct 28 '20 at 20:48

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.