I am solving this problem: $$ \sum_i \parallel f(x_i)- y_i\parallel_2^2 + \lambda <\psi f, \psi f>_{L_2}^2 $$ where the second part $<\psi f, \psi f>_2^2$ is regularizer using the linear operand in hilbert space $\psi$. When I model my function $f$ as $$ f(x)=\sum_k k(x, x_k) \alpha_k $$ the regression problem becomes $$ \parallel K\alpha -y \parallel_2^2 + \lambda \alpha^T F_{reg} \alpha $$

And now to the question:

Which functions types $k(x,y)$ can be used with respoect to the regularizer?

  • Gaussian: $F_{reg}=I$ since the kernel is the optimal result for the smoothness regularizer $\parallel \psi f\parallel^2=\int dx \sum_m \frac{\sigma^{2m}}{m!2^m}(\psi f)$ (see A. Smola, B. Schölkopf, On a Kernel-based Method for Pattern Recognition, Regression, Approximation, and Operator Inversion, 1997)

  • What happens in the case of a (conditional) positive semi definite function k like $$ k(x_i,x)=n_i^T(x_i-x) $$ with $n_i$ being the surface normal vector at $x_i$.

Will I need a polynomial $b(x)^Tc$ with orthogonality constraints to restrict the solution, like in the case of thin plate kernels? $$ \begin{pmatrix} K & B^T\\ B & 0\end{pmatrix} \begin{pmatrix} \alpha\\ c \end{pmatrix} = \begin{pmatrix} y\\0 \end{pmatrix} $$

Can I then design my regularizator using the standard procedure? $$ [F_{reg}]_{i,j}=<\psi f(x_i), \psi f(x_j)>_{L_2} $$ (where $[\cdot, \cdot]_{i,j}$ means the i-th and j-th element of the matrix in the braces).

  • A Hinge functions PSD ?? :)

Huge thanks to all comments!!

  • $\begingroup$ You can use any $\psi$ to define your kernel. If you want to specify the kernel function directly, a necessary condition is that the induced matrix $F_reg$ is positive semi-definite (PSD). $\endgroup$ – Theja Oct 14 '13 at 20:43
  • $\begingroup$ Ahh oh, cool! And what's about the case when I derive the kernel from $\psi$? Did I assume correctly that the regularization matrix should/may be $I$? Or even the same kernel? Or just PSD? :) $\endgroup$ – mojovski Oct 16 '13 at 16:24
  • $\begingroup$ When you specify $\psi$, you have defined a PSD kernel implicitly. For the $F_{reg}$ to be identity matrix, you need an identity map $\psi:\mathbb{R}^d\rightarrow\mathbb{R}^d$, that is $\psi(x) = x$ where $x$ is d-dimensional. $\endgroup$ – Theja Oct 16 '13 at 21:13

Your Answer

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

Browse other questions tagged or ask your own question.