0
$\begingroup$

By the representer theorem of RKHS, the solution of kernel ridge-regression in RKHS, $$\underset{f\in \mathcal{H}}{\min} \sum_{i=1}^N (f(x_i) - y_i)^2 +\lambda\|f\|_\mathcal{H},$$ where $\mathcal{H}$ is an RKHS, is given by a linear combination of the kernel functions, i.e., $\hat{f} = \sum_{i=1}^N c_i k(\cdot, x_i)$. This seems like finding a function to interpolate $y_i$'s. Is there any specific benefit/insight of such a formulation using reproducing kernel, rather than using other nonlinear functions such as Fourier basis? Or in general, what is the benefit of using kernel methods in RKHS?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

It is fast because we are effectively solving a linear problem. And yet we get a high performing non linear function. This is crucial for any application (think of an SVM classifying millions of data points). Any minimizer of the functional $$\mathcal F (f) = \frac{1}{n} \sum\limits_{i=1}^{n} l(f(X_i), Y_i) + G(\|f\|^2_{\mathcal H_K})$$ where $l$ is a loss function, $G$ is a strictly non-decreasing function of the squared norm of $f$ in the RKHS with kernel $K$ has the form $$f^*(.) = \sum\limits_{i=1}^{n} \alpha_i K (x_i, . )$$

This is called the representer theorem. In the proof below, we see that what we are actually doing is minimizing over a subspace of ${\mathcal H_K}$, i.e $S= \operatorname{span}\{ K(x_i, .) | 1 \leq i \leq n\}$, and the repesenter theorem guarantees that the minimizer we obtain is the minimizer over the whole space ${\mathcal H_K}$. If you proceed like this with another subspace, say the span of the Legendre polynomials or other Fourier basis, it does not hold in general that the minimizer over that subspace is actually the global minimizer.

The representer theorem has huge implications in practice. Let us look at an example. Let $\mathcal H_K$ be a RKHS with kernel $K$. Suppose we are interested in minimizing a regularization of the squared error risk

$$\hat f_{n,\lambda} = \operatorname{argmin}_{f \in \mathcal H_K} \frac{1}{n} \sum\limits_{i=1}^{n} (f(x_i) - y_i)^2 + \lambda \|f\|_{\mathcal H_K}^2$$

Then we know that any minimizer $f$ has the form

$$ f(.) = \sum\limits_{j=1}^{n} \alpha_j K(x_j,.)$$

Observe that

$$f(x_i) = \sum\limits_{j=1}^{n} \alpha_j K(x_j,x_i) = \sum\limits_{j=1}^{n} \alpha_j K(x_i,x_j)$$

and that

\begin{align} \|f\| ^2_{\mathcal H_K} &= \langle { f, f }\rangle_{\mathcal H_K} \\ &= \Big\langle { \sum\limits_{i=1}^{n} \alpha_i K(x_i,.), \sum\limits_{j=1}^{n} \alpha_j K(x_j,.) }\Big\rangle_{\mathcal H_K} \\ &= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \alpha_i \alpha_j \big\langle {K(x_i,.), K(x_j,.) }\big\rangle_{\mathcal H_K} \end{align}

Using matrix notation $\mathbb K_{ij}:=\big\langle K(x_i,.), K(x_j,.) \big\rangle_{\mathcal H_K}$, we get

$$\hat f_{n,\lambda} = \sum\limits_{j=1}^{n} \alpha_j^* K(x_j,.)$$

where

$$\mathbb \alpha^* = \operatorname{argmin}_{\mathbb \alpha} \frac{1}{n} \|{\mathbb Y-\mathbb K \mathbb \alpha}\|^2 + \lambda \mathbb \alpha \mathbb K \mathbb \alpha $$

This is a convex differentiable cost function, we can find its minimum by setting its gradient to zero

$$ - \mathbb K ( \mathbb Y - \mathbb K \alpha^*) + \lambda n \mathbb K \alpha^* = 0 $$

which implies, when matrix $\mathbb K$ is strictly positive definite, that

$$\alpha^* = ( \mathbb K + \lambda n \mathbb I )^{-1} \mathbb Y$$

where $\mathbb I$ is the identity matrix. This is a $n \times n$ linear system. It can be solved numerically by means of Cholesky factorization (complexity of $O(n^3)$).

Once the $\alpha^*$ computed, we can use $\hat f_{n,\lambda}$ on new data

$$\hat f_{n,\lambda} (x_{\text{new}}) = \sum\limits_{j=1}^{n} \alpha_j^* K(x_j,x_{\text{new}}) = \mathbb K_{x_{\text{new}}} \alpha^* = \mathbb K_{x_{\text{new}}}( \mathbb K + \lambda n \mathbb I )^{-1} \mathbb Y$$

This operation has cost $O(n^2)$ for each new example.

Here is the proof of the representer theorem where we explicitly use the reproducing property.

We project $f$ onto the subspace

$$S= \operatorname{span} \{ K(x_i, .) | 1 \leq i \leq n\}$$

By the orthogonal decomposition theorem in Hilbert spaces, we have $f= f_1 +f_2$, where $f_1$ is the component in $S$ and $f_2$ the one orthogonal to $S$. By Pythagoras theorem, we have

$$ \|f\|^2 \geq \|f_1\|^2$$

Since $G$ is non-decreasing, we have

$$G(\|f\|^2_{\mathcal H_K}) \geq G(\|f_1\|^2_{\mathcal H_K})$$

Notice that (using the reproducing property)

$$f(x_i)= \langle f, K(x_i,.) \rangle = \langle f_1, K(x_i,.) \rangle + \langle f_2, K(x_i,.) \rangle = \langle f_1, K(x_i,.) \rangle = f_1(x_i)$$

This implies that

$$l(f(x_i), y_i) = l(f_1(x_i), y_i)$$

So the loss function only depends on the component in $S$ and $G$ is minimized if $f$ lies in $S$. Hence we can find a minimizer in $S$

$$f^*(.) = \sum\limits_{i=1}^{n} \alpha_i K(x_i,.)$$

As $G$ is strictly non-decreasing, $||f_2||$ must be zero for $f$ to be a minimizer of $\mathcal F (f)$. In conclusion, any minimizer has the above form.

$\endgroup$
12
  • $\begingroup$ Thanks for the answer here! My concern is that we can literally expand $f$ using any basis, say $f = \sum_{i=1}^n \alpha_i \phi_i$. Then the coefficients can be solved in a similar way as you mentioned here by letting $\mathbb{K}_{ij} = \langle \phi_i, \phi_j\rangle$. This also just requires $O(n^2)$ to solve the linear inverse problem. Many existing literatures report setting $\phi_i$'s as reproducing kernels gives us good results, comparing to setting them to other basis such as Fourier or Legendre. But I don't see any reason for this. $\endgroup$
    – mw19930312
    Feb 24, 2020 at 22:21
  • $\begingroup$ Of course, performance depends on the choice of kernel. In general, you will get worse results with the Laplacian kernel rather than with the Gaussian kernel for example. This is because, when you do not know anything specific about the data, your best bet is to produce a smooth predictor. Gaussian kernels produce smooth $f$. You can see this by building a feature map $\phi$ explicitly (use the Fourier transform of the kernel). You can assume that the Hilbert space is $l^2$. But the whole points of kernel methods is to not build the feature map, just use the geometry of the problem instead. $\endgroup$
    – user748358
    Feb 24, 2020 at 23:06
  • $\begingroup$ Thanks for the further explanation. But I still feel my question not fully answered. I assume there are other choices of expansions, other than reproducing kernels, that yield a smooth predictor. Then how reproducing kernels are better? $\endgroup$
    – mw19930312
    Feb 27, 2020 at 21:02
  • $\begingroup$ Or to be more specific, is there any advantage of using `reproducing' kernel, over using other types of kernel as in general spectral methods? $\endgroup$
    – mw19930312
    Feb 27, 2020 at 21:52
  • $\begingroup$ No worries, you should ask questions until you are satisfied. I am still unsure of what you are asking. The whole point of working in a $RKHS$ is that we know the minimizer of the functional has that form above. If you do not use the reproducing kernel, nothing guarantees that you are minimizing the functional. Would you like to see the proof of the representer theorem above ? I will edit my post $\endgroup$
    – user748358
    Feb 27, 2020 at 23:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .