bayesbayesianclassificationprobability
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.
Question 1 : Is there any difference between Bayes Classifier and Naive Bayes Classifier ?
Question 2.A: For real data, we do not know the conditional distribution of Y given X, and so computing the Bayes classifier is impossible. ?
The Optimal Bayes Classifier chooses the class that has greatest a posteriori probability of occurrence (so called maximum a posteriori estimation, or MAP). It can be shown that of all classifiers, the Optimal Bayes Classifier is the one that will have the lowest probability of miss classifying an observation. So if we know the posterior distribution, then using the Bayes classifier is as good as it gets.
In real-life we usually do not know the posterior distribution, but rather we estimate it. The Naive Bayes classifier approximates the Optimal Bayes classifier by looking at the empirical distribution and by assuming conditional independence of explanatory variables, given a class. So the Naive Bayes classifier is not itself optimal, but it approximates the optimal solution.
Consider a model where we are trying to predict a categorical output variable $G$ based on some input variables $X$.
The optimal Bayes decision rule is to choose the class presenting the maximum posterior probability, given the particular observation at hand.
\begin{aligned} \hat f(x) & = argmax_g Pr(g | \vec x) \\ & = argmax_g \frac{Pr(\vec x | g) p(g)}{p(\vec x)} \\ & = argmax_g Pr(\vec x | g) p(g) \end{aligned}
The problem is that the distribution $Pr(g | \vec x)$ or $Pr(\vec x | g)$ are not known, so we need to estimate them.
One approach would be to use the MLE estimates which are the averages over the $m$ observations.
$$ \hat p(g | \vec x) = \frac{\sum_{i = 1}^m \mathcal{I}(G^{(i)} = g \cap \vec X^{(i)} = \vec x) }{\sum_{i = 1}^m \mathcal{I} ( \vec X^{(i)} = \vec x)}$$
But the MLE estimates are only good if there are many training vectors with the same identical features as $x$. In high dimensional space or with continuous $x$ this never happens and the numerator and denominator both tend to zero.
The naive assumption is that input values are independent given the class. This is a very bold assumption, but it allows us to compute the probability distribution much more easily:
\begin{aligned} p(\vec x | g) & = p(x_1 | g) \ p(x_2 | g, x_1) \ p(x_3 | g, x_1, x_2) \ ... \ p(x_p | g, x_1,...,x_{p-1}) & \text{Chain rule of probability} \\ & = p(x_1|g) \ p(x_2|g) \ ... \ p(x_p | g) & \text{Conditional independence} \\ & = \prod_{\alpha = 1}^p p(x_\alpha | g) & \text{Compact notation} \end{aligned}
As usual, the Bayes Classifier will predict the class for which the posterior probability (or a function proportional to the posterior probability) is the greatest:
\begin{aligned} h(\vec x) & = argmax_g p(g | \vec x) \\ & = argmax_g \prod_{\alpha = 1}^p p(x_\alpha | g) p(g) & \text{Naive assumption} \\ & = argmax_g \sum_{\alpha = 1}^p \log(p(x_\alpha| g)) + \log p(g) &\text{Log is monotonic} \end{aligned}
Now that we have an objective function, we can construct a Naive Bayes Classifier by calculating estimates of $p(x_\alpha| g)$ and $p(g)$ from the data. The actual formula of these estimates will depend on the structure of the problem, for example if you have categorical, or multinomial, or continuous features.
Question 3 :- If the Bayes and Naive Bayes Classifier are different then what are the differences in their approach to solve a problem
When feature $x_\alpha \in \mathcal{R}$ take on real values, we can use a Gaussian distribution
$$ p(x_\alpha | G = c) \sim \mathcal{N}(\mu_{\alpha c}, \sigma^2_{\alpha c}) = \phi(x | \mu_{\alpha c}, \sigma^2_{\alpha c} )$$
where we assume that each feature $\alpha$ comes from a class-conditional, univariate Gaussian distribution.
Parameters are estimated as
$$ \mu_{\alpha c} = \frac{1}{m_c} \sum_{i = 1}^m \mathcal{I}(G^{(i)} = c) x^{(i)}_\alpha \ \text{ and } \ \sigma^2_{\alpha c} = \frac{1}{m_c} \sum_{i = 1}^m \mathcal{I}(G^{(i)} = c) (x^{(i)}_\alpha - \mu_{\alpha c})^2$$ $$ m_c = \sum_{i = 1}^m \mathcal{I}(G^{(i)} = c) \ \text{ and } \ p(y = c) = \frac{1}{m} \sum_{i = 1}^m \mathcal{I}(G^{(i)} = c) $$
This shows that the naive assumption works very well when there is no correlation between the variables $x_1$ and $x_2$. When there is some correlation, the naive bayes classifier does less well, but is still surprisingly good, given the assumption is clearly violated.
See here for the code used to generate these figures and more details
There's no need to treat separately the cases where $X$ is discrete, continuous or neither. We are just taking an iterated expectation here, which is always permissible. The idea is that since probabilities are simply expectations of indicator random variables we can always write something like
\begin{align} P(g(X) \neq Y) &= \text{E} \left (I_{ \{ g(X) \neq Y \}} \right ) \\ &= \text{E} \left [ \text{E} \left (I_{ \{ g(X) \neq Y \}} \mid X \right ) \right ] \\ &= \text{E}[ P(g(X) \neq Y \mid X)] \end{align}
and the integral above is just another way of writing this down. Again, this holds true no matter what "type" of random variable $X$ happens to be.
Best Answer
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
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})$.
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)$.