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

Improve this question
$\endgroup$
3
  • $\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$
    – MotiNK
    Commented Nov 17, 2016 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
    Commented Nov 17, 2016 at 15:40
  • $\begingroup$ @MotiNisenson I edited question. I hope that now is more clear what is the question. $\endgroup$
    – Dejan
    Commented Nov 17, 2016 at 16:04

1 Answer 1

Reset to default
2
$\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?

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 18, 2016 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
    Commented Nov 18, 2016 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
    Commented Nov 18, 2016 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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