14
$\begingroup$

This question concerns the generalized Representer Theorem, due to Schölkopf, Herbrich, and Smola. In this magnificent work, the authors provide two versions of the Representer Theorem, a non-parametric, and a semi-parametric one. Though, they provide a proof only for the non-parametric version, while they say that the proof for the semi-parametric version is slightly more technical, but straightforward.

I have also posted this question on MathOverflow, just in case there is someone there who can help, and -alas- does not use MathSE.

I fully understand the proof for the non-parametric version, but unfortunately I cannot find a way in order to start the proof of the semi-parametric.

Below, I give the statements of the above two versions of the Representer Theorem, as well as the proof for the non-parametric case, and I would like to discuss about the proof of the semi-parametric version.

Theorem 1 (Non-parametric Representer Theorem)

Suppose we are given a nonempty set $\mathcal{X}$, a positive definite real-valued kernel $k$ on $\mathcal{X}\times\mathcal{X}$, samples $(\mathbf{x}_1,y_1),\cdots,(\mathbf{x}_m,y_m)\in\mathcal{x}\times\mathbb{R}$, a strictly monotonically increasing real-valued function $g$ on $[0,\infty)$, an arbitrary cost function $c\colon(\mathcal{x}\times\mathbb{R}^2)^m\to\mathbb{R}\cup\{\infty\}$, and a class of functions $$ \mathcal{F}=\bigg\{ f\in\mathbb{R}^{\mathcal{X}} \mid f(\cdot)=\sum_{i=1}^{\infty}\beta_i k(\cdot, \mathbf{z}_i), \beta_i\in\mathbb{R}, \mathbf{z}_i\in\mathcal{X}, \lVert f \rVert < \infty \bigg\}. $$ Here, $\lVert\cdot\rVert$ denotes the norm in the Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}$ associated with $k$. Then any $f\in\mathcal{F}$ minimizing the regularized risk functional $$ c \Big( (\mathbf{x}_1,y_1,f(\mathbf{x}_1)), \cdots, (\mathbf{x}_m,y_m,f(\mathbf{x}_m)) \Big) + g\big(\lVert f \rVert\big) $$ admits a representation of the form $$ f(\cdot) = \sum_{i=1}^{m} \alpha_i k(\cdot,\mathbf{x}_i). $$

Proof: Let $\phi: \mathcal{X}\to\mathbb{R}^{\mathcal{X}}$, $$ \mathbf{x}\mapsto k(\cdot,\mathbf{x}). $$ Since $k$ is a reproducing kernel, evaluation of the function $\phi(\mathbf{x})$ on the point $\mathbf{x}'$ yields $$ (\phi(\mathbf{x}))(\mathbf{x}')=k(\mathbf{x}',\mathbf{x})=\langle \phi(\mathbf{x}'), \phi(\mathbf{x}) \rangle, $$ for all $\mathbf{x},\mathbf{x}'\in\mathcal{X}$. Here $\langle \cdot,\cdot \rangle$ denotes the dot product in $\mathcal{H}$. Given $\mathbf{x}_1,\cdots,\mathbf{x}_m$, any $f\in\mathcal{F}$ can be decomposed into a part that lives in the span of the $\phi(\mathbf{x}_i)$, and a part which is orthogonal to it, i.e. $$ f = \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u, $$ for some $\alpha\in\mathbb{R}^m$ and $u\in\mathcal{F}$ satisfying fot all $j$, $$ \langle u,\phi(\mathbf{x}_j) \rangle = 0. $$ Using the latter and the reproducing property mentioned above, application of $f$ to an arbitrary point $\mathbf{x}_j$ yields $$ f(\mathbf{x}_j) = \Big\langle \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u, \phi(\mathbf{x}_j) \Big\rangle = \sum_{i=1}^{m} \alpha_i \Big\langle \phi(\mathbf{x}_i),\phi(\mathbf{x}_j) \Big\rangle, $$ which is independent of $u$. Consequently, the first term of the regularized risk functional is independent of $u$. As for the second term, since $u$ is orthogonal to $\sum_{i=1}^{m}\alpha_i\phi(\mathbf{x}_i)$, and $g$ is strictly monotonic, we get $$ g\big(\lVert f \rVert\big) = g\bigg(\bigg\lVert \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u \bigg\rVert\bigg) = g\bigg( \sqrt{ \bigg\lVert \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) \bigg\rVert^2 + \bigg\lVert u \bigg\rVert^2 } \bigg) \geq g\bigg( \bigg\lVert \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) \bigg\rVert \bigg), $$ with equality iff $u=0$. Setting $u=0$ thus, does not affect the first term of the regularized risk functional, while strictly reducing the second term - hence, any minimizer must have $u=0$. Consequently, any solution takes the form $f=\sum_{i=1}^{m}\alpha_i\phi(\mathbf{x}_i)$, i.e., using the reproducing property, $$ f(\cdot) = \sum_{i=1}^{m}\alpha_i k(\cdot,\mathbf{x}_i). $$ Q.E.D.

Now, the statement of the semi-parametric version extends the non-parametric as follows:

Theorem 2 (Semi-parametric Representer Theorem)

Suppose that, in addition to the assumptions of the previous theorem, we are given a set of $M$ real-valued functions $\{\psi_p\}_{p=1}^{M}$ defined on $\mathcal{X}$, with the property that the $m\times M$ matrix $\big( \psi_p(\mathbf{x}_i) \big)_{ip}$ has rank $M$. Then, any $\tilde{f}:=f+h$, with $f\in\mathcal{F}$ and $h\in\operatorname{span}\{\psi_p\}$, minimizing the regularized risk functional $$ c \Big( (\mathbf{x}_1,y_1,\tilde{f}(\mathbf{x}_1)), \cdots, (\mathbf{x}_m,y_m,\tilde{f}(\mathbf{x}_m)) \Big) + g\big(\lVert f \rVert\big), $$ admits a representation of the form $$ \tilde{f}(\cdot) = \sum_{i=1}^{m}\alpha_i k(\cdot,\mathbf{x}_i) + \sum_{p=1}^{M}\beta_p \psi_p(\cdot), $$ with unique coefficients $\beta_p\in\mathbb{R}$, for all $p=1,\cdots,M$.

It would be nice if you could provide a meaningful sketch of the proof. I think it may help some other people as well, who study this theory, but unfortunately do not have the appropriate background to prove such theorems by themselves (yet!). Thanks a lot!

$\endgroup$
5
+50
$\begingroup$

Suppose that we have $\tilde f = f + h$ as described. Let $V = span( k(\cdot, x_i) )_{i=1,...,m}$. We can write any function $f \in \mathcal{F}$ as $f = f_s + f_p$ where $f_s \in V$ and $f_p \in V^{\perp}$.

This means that $$\tilde f(x_i) = f(x_i) + h(x_i) = f_s(x_i) + f_p(x_i) + h(x_i)$$ but since $f_p \in V^{\perp}$ we have that $f_p(x_i) =0$. Which yields: $$\tilde f(x_i) = f(x_i) + h(x_i) = f_s(x_i) + h(x_i)$$

Thus $$c( (x_i, y_i, \tilde f(x_i))_{i=1,...,m}) = c( (x_i, y_i, f_s(x_i) + h(x_i))_{i=1,...,m})$$ which means that $f_p$ has no effect on $c(\cdot)$. Moreover, since $$\|f\|^2 = \|f_s\|^2 + \|f_p\|^2$$ by the pythagorean theorem, we have $$\|f_s\| \le \|f\|$$ for all $f \in \mathcal{F}$. Thus $g(\|f_s\|) \le g(\|f\|)$ since $g$ is strictly increasing.

Thus we see if a function $\tilde f = f+h$ minimizes the cost function $f_p$ must be zero. Thus $\tilde f = f_s + h$ and since $f_s \in V$ we have that $$\tilde f = \sum_{i=1}^m a_i k(\cdot, x_i) + h$$

Finally when we evaluate $\tilde f(x_j) = \sum_{i=1}^m a_i k(x_j, x_i) + h(x_j)$ we get $m$ equations for $$h(x_j) = \sum_{p=1}^M \beta_p \psi_p(x_j) = \tilde f(x_j) - \sum_{i=1}^m a_i k(x_j, x_i).$$ By the assumptions on $\psi_p(x_j)$ we see that $(\psi_p(x_1),...,\psi_p(x_m))^T$ (for $p=1,2,...,M$) are linearly independent vectors, and thus the coefficients $\beta_p$ are uniquely determined.

$\endgroup$
  • $\begingroup$ Of course the award is yours! Thanks a lot @Joel! $\endgroup$ – nullgeppetto Jul 7 '14 at 21:32

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.