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!


1 Answer 1


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$ Commented Oct 28, 2020 at 20:40
  • $\begingroup$ Yes, it's just $1-P(X=x)=P(X\neq x)$, did you notice that? $\endgroup$
    – gunes
    Commented Oct 28, 2020 at 20:41
  • $\begingroup$ Yes, I did! I was kinda confused with the problem statement. I got it now. Thank you so much! $\endgroup$ Commented Oct 28, 2020 at 20:48

Your Answer

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

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