6
$\begingroup$

This is more of a conceptual question.

I have learned about Neural Nets, and I have some clue as to how Support Vector Machines work. I read somewhere however that given the appropriate kernel (is that right?), the SVM is identical to the Neural Net. Could someone who understands this please enlighten me as to how that's possible?

$\endgroup$
2
  • $\begingroup$ Of the two topics, Neural Nets seems to be the broader category and Support Vector Machines the narrower one. I suspect you saw a claim that a neural net could be trained to perform the same discriminative classification task as an SVM. This seems like a reasonable notion. $\endgroup$
    – hardmath
    Dec 28 '13 at 15:20
  • $\begingroup$ Certainly SVMs will perform similarly to NNs on some tasks, and mixed on others. I think it was in this video that he said that SVMs could literally become NNs: videolectures.net/epsrcws08_campbell_isvm I'll have to look up which part, but I think it was towards the end of part 1. $\endgroup$
    – Josh F
    Dec 28 '13 at 16:58
6
$\begingroup$

If I understand the link of hardmath correctly, a "support vector machine" in its most simple form is just a glorious name for a linear function $f(x)=b^Tx+b_0$ dividing the space into two half spaces according to the sign of the values. And separating two given sets (with disjoint convex hulls for existence of a separating hyperplane).

The original perceptron that started all that neural network business was just such a linear function chained together with a sigmoid function $p(x)=\sigma(f(x))$, for instance

$$p(x)=\frac1{1+e^{-b_0-b^Tx}},$$

so that now you can say that a point $x$ is of class 1 if $p(x)\approx 0$, which happens when $f(x)$ is very clearly negative, and of class 2 if $p(x)\approx 1$, which happens whenever $f(x)$ is very positive. Points with values of $p(x)$ in between are not clearly classifiable. By scaling $(b_0,b)$ the separating hyperplane stayes fixed, but the region of uncertainty changes width.

So we got fuzzy logic before the age of fuzzy logic.

The classical back-propagation neural network consists of several layers of such perceptrons, where the input of each layer is the output of the previous layer, the first input is $x$ and the last output the (hopefully, after training) separating function value.

Still works best if the convex hulls of the classes are disjoint, but also non-convex shapes are trainable.


Essentially, neural networks and the more complex realizations of SVM are just non-linear functions with a huge parameter set making them very flexible to adapt to any desired shape, that is, they do interpolation.

So, take a neural network, take a linear combination of gaussian kernels, take any polynomial, all with unspecified parameters collected into one huge parameter vector $w$, and call the resulting function $f(w,x)$. Then one can pose the following non-linear optimization problem in the spirit of SVM

minimize $\frac12 \|w\|_2^2$ so that $y_i\cdot f(w,x_i)\ge 1$

or

minimize $\frac12 \|w\|_2^2+C\sum\xi_i$ so that $y_i\cdot f(w,x_i)\ge 1-\xi_i$

The training points constituting the active constraints are again the support vectors.

For this to work one has to make certain "niceness" conditions on the function. The parameters in $w$ should all have about the same influence on the function value in the region of the training set. For $w=0$, $f(0,x)=0$ or $f(0,x)$ very small across the training set. For $\|w\|\to\infty$, the function values should also grow largely above the level of $1$ in absolute value.


The easiest way to achieve this niceness is to have $f(w,x)$ linear in $w$. Then $f(w,x)=\langle w,\phi(x)\rangle$, with $w,\phi(x)$ in some Hilbert space with its scalar product $\langle\cdot,\cdot\rangle$. The whole machinery of the simple linear case still applies, $w=\sum\alpha_iy_i\phi(x_i)$, so that

$$f(w,x)=\sum_{α_i>0}α_iy_i\langle \phi(x_i),\phi(x)\rangle$$

so that then everything is reduced to the kernel $\kappa(x,y)=\langle \phi(x),\phi(y)\rangle$. Common examples are the the polynomials up to some degree $d$ and the gaussian functions,

$$\begin{array}{c|c} \phi(x)=(x^e:e\in\mathbb N^n, \;|e|\le d), & \phi(x)=\Bigl[u\mapsto \exp(\tfrac{\|u-x\|^2}{\sigma^2})\Bigr],\\ f(w,x)=\sum_{|e|\le d}c_ew_e\,x^e,& f(w,x)=\left[\frac{2}{\pi\sigma^2}\right]^{\frac n2}\int_{\mathbb R^n}w(u)\exp(\tfrac{\|u-x\|^2}{\sigma^2})\,du,\\ \kappa(x,y)=(1+\tfrac1{R^2}\langle x,y\rangle)^d;& \kappa(x,y)=\exp(\tfrac{\|x-y\|}{2\sigma^2}) \end{array}$$

where $R$ represents some scale of the data points $x_i$ and $\sigma$ the granularity of the data points, especially of the support vectors among them.


In this sense, the parametrization of neural networks is much too non-linear to directly fit into the idea of kernel based SVM. The flexibility however should be nearly the same.

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