Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have also posted this question on MathSE, so if you think it mustn't be here, please let me know, or just delete it. I was thinking that some people here are more appropriate to answer this question!

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 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!

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.