3
$\begingroup$

I was reading/watching CalTech's ML course and it said that one could derive the RBF Gaussian kernel from the solution to smoothest interpolation that minimizes squared loss. i.e. one can derive the predictor/interpolator:

$$ f(x) = \sum^{K}_{k=1} c_k \exp( -\beta_k \| x - w_k \|^2 )$$

from the Empirical Risk minimizer with a smoothest Regularizer:

$$ f^* = arg \min_f \mathcal{E}_S(f) = \sum^{N}_{n=1} (f(x_n) - y_n)^2 + \lambda R(f) $$

$$ f^* = arg \min_f \mathcal{E}_S(f) = \sum^{N}_{n=1} (f(x_n) - y_n)^2 + \lambda \sum^{\infty}_{k=0} a_j \int^{\infty}_{- \infty} \left( \frac{d^k h}{d x^k} \right) dx$$

unfortunately, they do not show the derivation of this. Thus I was wondering if someone could show me how minimizing the ERM using that regularizer, one could derive the RBF kernel function. In particular I am very interested in the exact mathematical details and if there is any maths I need to learn I am motivated to learn it to understand this derivation.

I believe they mentioned that this regularizer was for some simplified case (not sure which one) but I would be interested to start of in the simple explanation of this derivation (I believe its using only 1D calculus?) and then generalizing as it needed. As a first suggestion the generalization could be the answer to the question Why does minimizing $H[f] =\sum^{N}_{i=1}(y_i-f(x_i))^2+\lambda \| Pf \|^2 $ leads to solution of the form $ f(x) =\sum^N_{i=1}c_iG(x; x_i)+p(x)$? .

$\endgroup$
  • $\begingroup$ are the sample points $w_k$ equally spaced ? if so, it becomes the en.wikipedia.org/wiki/Kernel_density_estimation which is in my opinion the solution you get when minimizing the quadratic criterion : squared error + smoothness $\endgroup$ – reuns Aug 25 '16 at 21:22
  • $\begingroup$ @user1952009 they are not equally spaced. I don't think I left out any crucial detail to solve my problem. I am pretty sure the $w_k$ should be the data set points because of the Representer Theorem (en.wikipedia.org/wiki/Representer_theorem), though your suggestion is an interesting one regardless. $\endgroup$ – Charlie Parker Aug 26 '16 at 0:45
1
$\begingroup$

de Boor (2001) addresses this, citing Whittaker (1923) and Reinsch (1967). Reinsch (1967) gives a useful explanation

Reinsch states that that penalizing the L2 norm of the second derivative corresponds to an optimal cubic spline basis, and penalizing the L2 norm of the m'th derivative corresponds to an optimal (2m - 1)-order polynomial spline basis. This is based on the use of Euler-Lagrange equations (A system of differential equations).

I assume that, if we allow the order of penalized derivatives to approach infinity, this yields a Gaussian radial basis because it is the limit of that Taylor series. But I do not have a source and that and haven't worked it out.

$\endgroup$
  • $\begingroup$ nice, I will check the papers out! Do you have a link to the original papers (beyond just pics of part of them)? Or maybe the names so I can find them? thanks! $\endgroup$ – Charlie Parker Jan 15 '18 at 15:59
0
$\begingroup$

The Gaussian is another way of representing it as Fourier series. This is explained in Applied Partial Differential Equations in chapter 10. There are a number of other books that show that Fourier series is the best fit in the L2 sense. I believe it is actually determined by your spacing you need to use Chebyschev spacing.

$\endgroup$
  • $\begingroup$ in machine learning you can't choose the spacing. Its given to you by the data. $\endgroup$ – Charlie Parker Jan 18 '18 at 15:47
  • $\begingroup$ You can reproject it. Its called a chebyschev reprojection. $\endgroup$ – user3417 Jan 18 '18 at 16:17

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.