11
$\begingroup$

It is considered the ideal case in which the probability structure underlying the categories is known perfectly.

Why is that with Bayes classifier we achieve the best performance that can be achieved ?

What is the formal proof/explanation for this? As we always use Bayes classifier as a benchmark to compare the performance of all other classifiers.

$\endgroup$
9
$\begingroup$

Why is that with Bayes classifier we achieve the best performance that can be achieved ? What is the formal proof/explanation for this?

Usually, a dataset $D$ is considered to consist of $n$ i.i.d. samples $x_i$ of a distribution that generates your data. Then, you build a predictive model from the given data: given a sample $x_i$, you predict the class $\hat{f}(x_i)$, whereas the real class of the sample is $f(x_i)$.

However, in theory, you could decide not to choose one particular model $\hat{f}_\text{chosen}$, but rather consider all possible models $\hat{f}$ at once and combine them somehow into one big model $\hat F$.

Of course, given the data, many of the smaller modells could be quite improbable or inappropriate (for example, models that predict only one value of the target, even though there are multiple values of the target in your dataset $D$).

In any case, you want to predict the target value of new samples, which are drawn from the same distribution as $x_i$s. A good measure $e$ of the performance of your model would be $$e(\text{model}) = P[f(X) = \text{model}(X)]\text{,}$$ i.e., the probability that you predict the true target value for a randomly sampled $X$.

Using Bayes formula, you can compute, what is the probability that a new sample $x$ has target value $v$, given the data $D$:

$$P(v\mid D) = \sum_{\hat{f}} P(v\mid \hat{f}) P(\hat{f}\mid D)\text{.}$$ One should stress that

  • usually $P(v\mid \hat{f})$ is either $0$ or $1$, since $\hat{f}$ is a deterministic function of $x$,
  • not usually, but almost all the time, it is impossible to estimate $P(\hat{f}\mid D)$ (except for the aforementioned trivial cases),
  • not usually, but almost all the time, the number of possible models $\hat{f}$ is too big, for the upper sum to be evaluated.

Hence, it is very hard to obtain/estimate $P(v\mid D)$ in most of the cases.

Now, we proceed to the Optimal Bayes classifier. For a given $x$, it predicts the value $$\hat{v} = \text{argmax}_v \sum_{\hat{f}} P(v\mid \hat{f}) P(\hat{f}\mid D)\text{.}$$ Since this is the most probable value among all possible target values $v$, the Optimal Bayes classifier maximizes the performance measure $e(\hat{f})$.

As we always use Bayes classifier as a benchmark to compare the performance of all other classifiers.

Probably, you use the naive version of Bayes classifier. It is easy to implement, works reasonably well most of the time, but computes only a naive estimate of $P(v\mid D)$.

$\endgroup$
  • $\begingroup$ Is the Bayes classifier (not naive bayes) the same as the bayes optimal classifier ???? and is $ P(v|f) $ the prior probability ? $\endgroup$ – RuiQi May 25 '16 at 1:18
  • $\begingroup$ @RuiQi I don't think that there is such thing as the Bayes classifier. I am aware of the naive Bayes classifier and the optimal Bayes classifier. $\endgroup$ – Antoine May 25 '16 at 8:27
  • $\begingroup$ @RuiQi $P(v\mid \hat{f})$ is the probability that a sample to be classified will fall into class $v$ if we use predictive model $\hat{f}$. I guess, you can call it prior probability. $\endgroup$ – Antoine May 25 '16 at 8:28
0
$\begingroup$

The performance in terms of success rate of a classifier relates to the probability that a true class $C_T$ equals the predicted class $C_P$.

You could express this probability as the integral over all possible situations of the feature vector $X$ (or sum when $X$ is discrete) and the conditional probability to classify correct for those $x$

$$P(C_T=C_P) = \int_{\text{all possible $X$}} f(x)P(C_T=C_P|x) \text{d}x$$

Where $f(x)$ is the probability density for the feature vector $X$.

If, for some possible set of features $x$, a classifier does not select the most probable class for that set of features then it can be improved upon.

The Bayes classifier always selects the most probable class for each set of features $x$ (the term $P(C_T=C_P|x)$ is maximum), thus can not be improved upon, at least not based on the features $x$.

$\endgroup$

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.