Connection between SVM and Representer theorem

SVM over the set of examples $\{x_n,t_n\}_{n=1}^N$ considers minimization of the following objective function:

$$\displaystyle \frac{1}{2}||\mathbf{w}||^2 + C\sum_{n=1}^N \ell(\mathbf w, x_n, t_n),$$

considering $\ell_2$ regularization. On the other hand, the Representer theorem is considering minimization of the following objective function:

$$\Omega(||f||^2_H)+L\left ( (x_1, t_1, f(x_1)),\dots , (x_N, t_N, f( x_N))\right),$$

where $f(\cdot )=\sum_{n=1}^N \alpha_n k(x_n,\cdot )$ in dual space or $f(\cdot )=\mathbf w^T\phi(\cdot)$ in primal space.

Question: How to connect representer theorem with SVM? What is $\Omega(||f||^2_H)$ and what is $L(\dots)$ in case of SVM?

I tried the following:

In primal space:

$$L\left ( (x_1, t_1, f(x_1)),\dots , (x_N, t_N, f( x_N))\right) = C\sum_{n=1}^N \ell(\mathbf w, x_n, t_n)$$ but the regularization $\Omega(||f||^2_H)$ does not match \begin{align} ||f||^2_H = \int_{x \in X} f(x)f(x)dx &= \int_{x \in X} \mathbf w^T\phi(\mathbf x) \phi(\mathbf x)^T \mathbf w\, dx = \ldots? \end{align}

since I cannot get something close to $||\mathbf{w}||^2$.

In dual space: Equivalent dual SVM formulation with kernels is

$$\max_{\mathbf \alpha} \sum_{n=1}^N \alpha_n -\frac{1}{2} \sum_{n=1}^N \sum_{k=1}^N \alpha_n \alpha_k t_n t_k k(x_n, x_k), \\ \textrm{s.t.} \sum_{n=1}^N \alpha_n t_n =0$$

where I cannot recognize which part is $\Omega(||f||^2_H)$ and which one is $L(\dots)$?

\begin{align} ||f||^2_H = \int_{x \in X} f(x)f(x)dx &= \int_{x \in X} \sum_{n=1}^N \alpha_n k(x_n,x ) \sum_{k=1}^N \alpha_k k(x_k,x )dx \\ &=\sum_{n=1}^N \sum_{k=1}^N \alpha_n \alpha_k \int_{x \in X} k(x_n,x )k(x_k,x )dx=\ldots \end{align}

• I'm not sure what the question here is exactly - generally speaking if you have a RKHS, then the svm formulation is like that of the representer theorem. To see this, note than when you apply the kernel trick, you don't have $||w||^2$ but $||w||^2_H$ in the SVM formulation. The solution $w$ is in the RKHS and not in the input space. – MotiN Nov 17 '16 at 13:45
• @MotiNisenson Svm formulation is like that of the representer theorem, but I do not see this. I tried to see this connection in primal space, which I agree I was wrong. But I do not see this connection in dual space with introduced kernels, too. How to get $||w||^2_H$ in dual? If we transform primal formulation into dual one we get constraint optimization $\max_\alpha\mathbf \alpha^T\mathbf 1 - \frac{1}{2}\mathbf \alpha^T \mathbf K \mathbf \alpha$, subject to $\mathbf \alpha^T \mathbf t = 0$, where $\mathbf K$ is kernel matrix. What is here $\Omega(|| f||^2_H)$ and what is other part with $L$? – Dejan Nov 17 '16 at 15:40
• @MotiNisenson I edited question. I hope that now is more clear what is the question. – Dejan Nov 17 '16 at 16:04

I'm still not entirely sure on exactly what you're asking, but I think this might address it.

I'm going to let $k_i$ denote the representer of $x_i$ in our Hilbert space $\mathcal H$ (so $k_i = \phi(x_i)$). We know that $$f = \sum_i \alpha_i y_i k_i$$

is the function that is normal to our hyperplane (this is our $w$, but I'm using $f$ to emphasize that it is a function).

Computing the norm: $$\vert \vert f \vert \vert^2_\mathcal H = \int \left( \sum_i \alpha_i y_i k_i(z) \right)^2 dz = \sum_{ij} \alpha_i\alpha_j y_i y_j \int k_i(z) k_j(z) dz$$

$$= \sum_{ij} \alpha_i\alpha_j y_i y_j \langle k_i, k_j \rangle = \sum_{ij} \alpha_i\alpha_j y_i y_j K(x_i, x_j)$$ so if $K$ is the linear kernel we have that $$\vert \vert f \vert \vert^2_\mathcal H = \sum_{ij} \alpha_i\alpha_j y_i y_j x_i^T x_j = w^T w.$$

Does that help?

• This is exactly what I need. I understand part with norms which answers my question. Also, I have one remark for the terminology at the begining. $f$ and $k_i$ are functions, while $w$ and $\phi(x_i)$ are vectors. So $k_i$ cannot be equal to $\phi(x_i)$, and $f$ is not the same as $w$. I would write $f = \sum_i \alpha_i y_i k_i$ and $w = \sum_i \alpha_i y_i \phi(x_i)$ and only their norms are equal. If you agree you can edit the answer. – Dejan Nov 18 '16 at 21:49
• When we're using kernels the line between vector and function blurs, because functions are just vectors in infinite dimensional vector spaces. If we use a radial kernel then our $\phi(x_i)$ are infinite dimensional functions, where if we use a polynomial kernel they're finite dimensional vectors. But in either case $\phi$ is a mapping into a Hilbert space. Furthermore, if we use the counting measure $c$ rather than the Lebesgue measure then $\int w(z)^2 c(dz) = \sum_i w_i^2 = w^T w$ so this allows us to be quite casual with summation vs. integration and function vs. vector. – jld Nov 18 '16 at 21:54
• I agree. But such notation was confusing to me. In my mind, talking about SVMs I distinguish primal and dual spaces, vectors and functions, features and kernels, etc. – Dejan Nov 18 '16 at 23:11