16
$\begingroup$

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?

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The reference does not include any information on KNN. Is it the right one? $\endgroup$ – bayerj Jul 14 '14 at 18:48
  • 1
    $\begingroup$ I meant it to enphasize what is understood for a discriminative algorithm vs a generative. $\endgroup$ – jpmuc Jul 15 '14 at 7:32
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I do not agree. "Generative classifiers learn a model of the joint probability, p(x, y), of the inputs x and the label y, and make their predictions by using Bayes rules to calculate p(ylx), and then picking the most likely label y. Discriminative classifiers model the posterior p(ylx) directly, or learn a direct map from inputs x to the class labels". See "On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes. $\endgroup$ – jpmuc May 27 '17 at 11:35
2
$\begingroup$

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: enter image description here

$\endgroup$
  • $\begingroup$ Must be a mistake.. $\endgroup$ – user46925 Jul 18 '16 at 18:08
1
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ A generative model learns P(Ck,X), so you can generate more data using that joint distribution. In contrast, a discriminative model would learn P(Ck|X). This is what @juampa is pointing at with KNN. $\endgroup$ – Zhubarb Oct 8 '14 at 7:24
  • 1
    $\begingroup$ At classification time, both generative and discriminative ends up using conditional probabilities to make predictions. However, generative classifiers learns the joint probability and by Bayes rule it computes the conditional, while in discriminative a classifier either computes directly the conditional, or provides an approximation for that as good as it can get. $\endgroup$ – rapaio Oct 8 '14 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy