Difference between Bayes classifier, KNN classifier and Naive Bayes Classifier Question 1 :- Is there any difference between Bayes Classifier and Naive Bayes Classifier ? Is there any fundamental difference ? I searched the web and unable to find a good solution.
Question 2 :- From Statistical Learning Page 39

In theory we would always like to predict qualitative responses using
  the Bayes classiﬁer. But for real data, we do not know the conditional
  distribution of Y given X, and so computing the Bayes classiﬁer is
  impossible. Therefore, the Bayes classiﬁer serves as an unattainable
  gold standard against which to compare other methods. Many approaches
  attempt to estimate the conditional distribution of Y given X, and
  then classify a given observation to the class with highest estimated
  probability. One such method is the K-nearest neighbors (KNN)
  classiﬁer.

Question 2.A 
For real data, we do not know the conditional distribution of Y given X, and so computing the Bayes classiﬁer is impossible. ? 
Can you give me an example why we are unable to find conditional distribution of Y given X ? From my perspective I am able to find the conditional distribution of Y given X (In supervised and semi-supervised learning).   If I consider the below example then Why am I unable to find conditional distribution of Y given X in real data ? 
Suppose I have 100 mangoes. Some of them are rotten and we can identify using properties like their shapes, sizes and their smells. Based on these properties we can find out whether we the mangoes are completely rotten , half rotten or fresh. In this way get we our training data and testing data which helps to build and test the model using Bayes classifier. Am I right or my logic is flawed ? 
Question 2.B
I can also use the KNN classifier here. The only difference is KNN classifier assign the category based on selected nearest neighbors probability. The prob of new observation assigned as completely rotten, half rotten or Fresh is based on the nearest neighbors value. Am I right again or my logic is flawed again ?
Question 3 :- If the Bayes and Naive Bayes Classifier are different then what are the differences in their approach to solve a problem . You can use the above problem to differentiate these two methods.
Please Help.
 A: 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 classiﬁer 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
A: *

*Is there any difference between Bayes Classifier and Naive Bayes Classifier ? Is there any fundamental difference ?
Yes, not a fundamental though. Naive Bayes Classifier simplifies the Bayes rule by introducing the assumption that the predictors $x_1, x_2, \dots x_n$ are independent of each other (mango smell does not depend on its shape or size) and equally influence the response $Y$. This has an immediate effect on the original Bayes rule:
$P(Y|x_0, x_1, \dots, x_n) = \dfrac{P(x_0, x_1, \dots, x_n|Y)P(Y)}{P(x_0, x_1, \dots, x_n)}$
becomes
$P(Y|x_0, x_1, \dots x_n) = P(x_0|Y)\cdot P(x_1|Y)\cdot P(x_n|Y) P(Y)$
We multiply the conditional probabilities of each predictor and drop the denominator. Assuming that features are independent is naive, hence Naive Bayes.

*

*Why am I unable to find conditional distribution of Y given X in real data ?

I am able to find the conditional distribution of Y given X.
Suppose I have 100 mangoes.

That is where you make a mistake. In order to apply the Bayes rule, 100 mangoes are not enough. 100 mangoes are 100 mangoes, what about all other mangoes in this world that can be fresh or rotten? If you train your classifier on 100 only, it will not be a Bayes Classifier because your conditional distribution will be a rough approximation. You have to get data on all the existing mangoes in the world to be able to compute the true conditional distribution of Y given X. That's why in real world "we often don't know the conditional distribution".

*

*I can also use the KNN classifier here. The only difference is KNN classifier assign the category based on selected nearest neighbors probability. The prob of new observation assigned as completely rotten, half rotten or Fresh is based on the nearest neighbors value. Am I right again or my logic is flawed again ?
Yes, you can use KNN classifier method with your 100 observations. It will be inferior to Bayes Classifier because you don't have the true conditional distribution but its approximation.

*

*If the Bayes and Naive Bayes Classifier are different then what are the differences in their approach to solve a problem . You can use the above problem to differentiate these two methods.
Naive assumption that there is no relationship between the predictors.
