Short answer
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.
Long answer
Consider a model where we are trying to predict a categorical output variable $G$ based on some input variables $X$.
- Input: $\mathbf{X} = (X_1, X_2,...,X_p)\in \mathbb{R}^p$ is a random vector which comes from a $p$ dimensional space
- Output classification $\mathbf{G} \in \mathcal{G}$ where $\mathbf{G}$ is a random variable corresponding to the discrete output value, and $\mathcal{G}$ is the discrete output space.
- Joint distribution on the input and output $Pr(X,G)$
- Goal is to learn a function $f(x): \mathbb{R}^p \rightarrow \mathcal{G}$ which takes inputs from the $p$ dimensional input space and maps them to the discrete output space
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.
An idea: use the MLE
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.
Naive Bayes Classifier
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
An example - Gaussian Naive Bayes on simulated data
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) $$
Comparing Optimal vs Naive classifier
Case 1) Data comes from Gaussian with 0 off diagonal covariance matrix
Case 2) Data comes from Gaussian with correlation terms in covariance matrix
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
