Is KNN a discriminative learning algorithm?

Question

It seems that KNN is a discriminative learning algorithm but I can't seem to find any online sources confirming this.

Is KNN a discriminative learning algorithm?

Answer 1

KNN is a discriminative algorithm since it models the conditional probability of a sample belonging to a given class. To see this just consider how one gets to the decision rule of kNNs.

A class label corresponds to a set of points which belong to some region in the feature space $R$. If you draw sample points from the actual probability distribution, $p(x)$, independently, then the probability of drawing a sample from that class is, $$ P = \int_{R} p(x) dx $$

What if you have $N$ points? The probability that $K$ points of those $N$ points fall in the region $R$ follows the binomial distribution, $$ Prob(K) = {{N} \choose {K}}P^{K}(1-P)^{N-K} $$

As $N \to \infty$ this distribution is sharply peaked, so that the probability can be approximated by its mean value $\frac{K}{N}$. An additional approximation is that the probability distribution over $R$ remains approximately constant, so that one can approximate the integral by, $$ P = \int_{R} p(x) dx \approx p(x)V $$ where $V$ is the total volume of the region. Under this approximations $p(x) \approx \frac{K}{NV}$.

Now, if we had several classes, we could repeat the same analysis for each one, which would give us, $$ p(x|C_{k}) = \frac{K_{k}}{N_{k}V} $$ where $K_{k}$ is the amount of points from class $k$ which falls within that region and $N_{k}$ is the total number of points belonging to class $C_k$. Notice $\sum_{k}N_{k}=N$.

Repeating the analysis with the binomial distribution, it is easy to see that we can estimate the prior $P(C_{k}) = \frac{N_{k}}{N}$.

Using Bayes rule, $$ P(C_{k}|x) = \frac{p(x|C_{k})p(C_{k})}{p(x)} = \frac{K_{k}}{K} $$ which is the rule for kNNs.

Answer 2

Answer by @jpmuc doesn't seem to be accurate. Generative models model the underlying distribution P(x/Ci) and then later use Bayes theorem to find the posterior probabilities. That is exactly what has been shown in that answer and then concludes the exact opposite. :O

For KNN to be a generative model, we should be able to generate synthetic data. It seems that this is possible once we have some initial training data. But starting from no training data and generating synthetic data is not possible. So KNN doesn't fit nicely with generative models.

One may argue that KNN is a discriminative model because we can draw discriminant boundary for classification, or we can compute the posterior P(Ci/x). But all these are true in the case of generative models as well. A true discriminative model doesn't tell anything about the underlying distribution. But in the case of KNN we know a lot about the underlying distribution, infact we are storing the entire training set.

So it seems KNN is mid-way between generative and discriminative models. Probably that is why KNN is not categorized under any of generative or discriminative models in reputed articles. Let's just call them non-parametric models.

Answer 3

I have come accross a book which says the opposite (i.e. a Generative Nonparametric Classification Model)

This is the online link: Machine Learning A Probabilistic Perspective by Murphy, Kevin P. (2012)

Here the excerpt from the book:

Answer 4

I agree that kNN is discriminative. The reason is that it does not explicitly store or tries to learn a (probabilistic) model that explains the data (as opposed to, e.g. Naive Bayes).

The answer by juampa confuses me since, to my understanding, a generative classifier is one that attempts to explain how the data is generated (e.g. using a model), and that answer says that it is discriminative because of this reason...