Probablistic counterpart for kNN We know that the Gaussian Mixture Model is a probabilistic counterpart of k-means algorithm. Is there a probabilistic counterpart for kNN? (which is similar to k-means, but supervised.)
 A: The way I'd model it (I haven't seen this in the literature, but it wouldn't surprise me if it were already out there) is:
I'd think of it as expressing the posterior distribution over class labels, 
given that you have a (test) sample $x$, as a marginalization over a sub-set of the training sample nodes, $n_i$:
$$
p(c \vert x) = \sum p(c \vert n_i ) p(n_i \vert x) 
$$
In the back of my mind, I have the idea that the test sample is assigned-to (or is essentially the same as) one of the test-samples; but since we don't know which one, we marginalize over all of the feasible ones.
The first factor defines, for each training-sample node, the probability
distribution over class labels, given that the test-sample was "assigned"
to node $n_i$.  If each training sample has a particular label, then this might be just an indicator function for that label; the various extensions to actual distributions are going to be problem domain specific.
The second factor is the probability that node $n_i$ is the correct assignment choice.  The direct mapping of $kNN$ is to have $p(n_i \vert x) = 1/k$ when $n_i$ is in the set of $kNN$'s, and zero otherwise; i.e. a cookie-cutter type of distribution.  Again, this could be generalized into something with a softer roll-off, e.g. a Gaussian type of shape in feature space, if desired.
In my opinion, this captures the the essential general structure of $kNN$:


*

*You pick a population who gets to  vote, this is achieved by $p(n_i \vert x)$, and then

*you combine the results of each vote, in this case each vote is a probability distribution over classes, $p(c \vert n_i)$


whether you want to have a soft or hard inclusion function, the exact methods for defining the vote probabilities distributions and so on are problem-specific details. 
A: Something very similar is Logistic regression with a Radial Basis Function (sometimes called Gaussian) kernel (http://en.wikipedia.org/wiki/Radial_basis_function_kernel), with all weights constrained to be $1$.
A fitted RBF kernel regression will compute weighted distances to various points, compute a Gaussian pseudo-probability of being a neighbor based on the distance, and average the values at the points in the training set weighted by that Gaussian pseudo-probability.
This is very similar to kNN, where $k$=size of the training set.
You can reduce the number of points under consideration via a Laplacian prior ($L_1$ regularization), but this won't have the same effect as varying $k$ in kNN, as the $k$ points chosen will be the only ones considered.
If weights are fixed at $1$, only the distance matters.  When weights are allowed to vary, it affects how much each point is allowed to vary.
A: This paper formulates explicitly a probabilistic version of KNN:
C.C. Holmes, N.M. Adams: A probabilistic nearest neighbour method for statistical pattern recognition. J. Roy. Statist. Soc. Ser. B, 64 (2) (2002), pp. 295–306.
Dave's idea also comes up in this paper:
A. Kaban. A probabilistic neighborhood translation approach for non-standard text categorization. Proc. Discovery Science (DS08), 2008.
A: Gaussian mixture model is rather a generalization of $k$-means where variances are not identity matrices.  One way to construct a probabilistic model which will be a generalization of kNN is to assume there is a gaussian centered at each data point with unknown variances whose distribution is fixed. 
