3
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MotiN Nov 17 '16 at 13:45
  • $\begingroup$ @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$? $\endgroup$ – Dejan Nov 17 '16 at 15:40
  • $\begingroup$ @MotiNisenson I edited question. I hope that now is more clear what is the question. $\endgroup$ – Dejan Nov 17 '16 at 16:04
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dejan Nov 18 '16 at 21:49
  • $\begingroup$ 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. $\endgroup$ – jld Nov 18 '16 at 21:54
  • $\begingroup$ 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. $\endgroup$ – Dejan Nov 18 '16 at 23:11

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.