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.

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.

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