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$ 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
    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$ Oct 28, 2020 at 20:48

Your Answer

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

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