4
$\begingroup$

SVM using RBF kernel is claimed to be similar (equivalent) to the K nearest neighbor classification method. I am not very clear about the analysis process of building this kind of relationship. Thanks for explanations.

$\endgroup$
  • $\begingroup$ I am not aware of any claim that RBF SVM is similar to a K-NN classifier (it certainly isn't going to be equivalent). Can you give a reference to a place where such a claim has been made? $\endgroup$ – Dikran Marsupial Apr 20 '12 at 9:39
  • 2
    $\begingroup$ The similarity is that both classifiers calculate the distance between instances. In SVM these are the distances between the support vectors and new data and in kNN it is the distance between training all instances and new data. I think that's all. SVMs learn which support vectors they should choose and the number is usually much smaller than the size of the training set. kNN stores the whole training set. $\endgroup$ – alfa Apr 20 '12 at 17:08
3
$\begingroup$

The decision boundary for 1-NN algorithm is the union of the Voronoi cells of each training instance.

As for SVM, when you use RBf kernel and if there is no regularization, the decision boundary will also be an approximation of the union of the Voronoi cells. So in this case, these methods are the same in terms of performance, but depending on the structure of the dataset, their complexities could be very much different. If the number of suport vectors in SVM is high, then both training and testing complexities of SVM will be much higher than 1-NN.

The power of SVM, however, will become clear when you do regularization.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

They are not that similar, but they are related though. The point is, that both kNN and RBF are non-parametric methods to estimate the density of probability of your data.

To see this let us first consider the case of kernel methods. Say you consider a region of 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 region 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}$.

The idea of kernel methods is to split the feature space in several regions, estimate the counts for each region, and use those point estimates to interpolate across the whole feature space. That may sound gibberish.

First let us see how we can rewrite the estimate for the probability. Let $\{x_{i}\}_{1}^{N}$ be your data set. Consider a region $V = h^{d}$ which corresponds to a hypercube of side length $h$ in the $d$-dimensional feature space. The Heaviside function is defined by, $$ H(x) = \begin{cases} 1, \text{if } |x| < 1/2 & \\ 0, \text{otherwise} \end{cases} $$

Then we can write the total number of points that fall within the hypercube, $V$ as, $$ K = \sum_{n}H\left(\frac{x-x_{n}}{h}\right) $$ where $x$ is the center of the hypercube. Or else, V is the neighborhood centered in $x$ and this is the number of points close to $x$. If we substitute back, $$ p(x) \approx \sum_{n} \frac{1}{h^{d}}H\left(\frac{x-x_{n}}{h}\right) $$

The case of RBF is a smoothed version, where $H$ is taken to be a Gaussian. For the case of kNN, please refer to this other question.

Notice that this two algorithm approach the same problem differently: kernel methods fix the size of the neighborhood ($h$) and then calculate $K$, whereas kNN fixes the number of points, $K$, and then determines the region in space which contain those points.

So yes, they are related, but nor equivalent.

P.S. SVM does not estimate the density of probability, but finds the separating hyperplane. Here I just compared kernel methods vs. kNN for density estimation. Even for novelty detection, does SVM not estimate the p.d.f. but its support (those points for which $p(x) \gt 0$, which is a different story.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.