8
$\begingroup$

How can I prove that linear combination of two kernel functions is also a kernel function?

\begin{align} k_{p}( x, y) = a_1k_1( x, y) + a_2k_2(x,y) \end{align}

given $k_1(,)$ and $k_2(,)$ are valid kernel functions.

In general to prove any such results involving dot product , cascading.. etc. , what methodology can be followd to prove RHS is a kernel function given k's in LHS all are kernel?

$\endgroup$
4
  • 1
    $\begingroup$ Only linear combinations with positive coefficients are always valid. $\endgroup$ – Marc Claesen Oct 15 '15 at 17:34
  • 5
    $\begingroup$ @MarcClaesen Just to clarify a minor point: only positive linear combinations are necessarily valid. It's possible for one with some negative coefficients to still be psd; this arises in multiple kernel learning problems, where the optimization becomes a semidefinite program. $\endgroup$ – Danica Oct 15 '15 at 17:36
  • $\begingroup$ @Dougal point taken! $\endgroup$ – Marc Claesen Oct 15 '15 at 17:37
  • $\begingroup$ I recommend these lecture notes alex.smola.org/teaching/cmu2013-10-701x/slides/… and the book kernel-methods.net for more detailed explanations. $\endgroup$ – JStrahl Sep 20 '16 at 12:59
10
$\begingroup$

A necessary and sufficient condition for a function $\kappa(\cdot,\cdot)$ to be expressible as an inner product in some feature space $\mathcal{F}$ is a weak form of Mercer's condition, namely that:

$$ \int_\mathbf{x} \int_\mathbf{y} \kappa(\mathbf{x},\mathbf{y})g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y} \geq 0, $$ for all square, integrable functions $g(\cdot)$ [1,2].

In your case, this reduces to the following: $$ \begin{align} &\int_\mathbf{x} \int_\mathbf{y} \big(a_1\kappa_1(\mathbf{x},\mathbf{y}) + a_2 \kappa_2(\mathbf{x},\mathbf{y})\big)g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y} \\ &= a_1 \underbrace{\int_\mathbf{x} \int_\mathbf{y} \kappa_1(\mathbf{x},\mathbf{y})g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y}}_{\geq 0} + a_2 \underbrace{\int_\mathbf{x} \int_\mathbf{y}\kappa_2(\mathbf{x},\mathbf{y})g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y}}_{\geq 0} \geq 0. \end{align} $$ Since $\kappa_1(\cdot,\cdot)$ and $\kappa_2(\cdot,\cdot)$ are given to be kernel functions, their integrals both satisfy Mercer's condition. Finally, if $a_1 \geq 0$ and $a_2 \geq 0$, then the overall integral is guaranteed to satisfy it too. $\blacksquare$

Note that, as @Dougal correctly pointed out, it is still possible to get a valid kernel function with negative $a_1$ or $a_2$ (not both), but that depends on several factors.

[1] Vladimir N. Vapnik. Statistical learning theory. Wiley, 1 edition, September 1998.

[2] Richard Courant and David Hilbert. Methods of Mathematical Physics, volume 1. Interscience Publishers, Inc., New York, NY, 1953

$\endgroup$
0
5
$\begingroup$

As an alternative approach to Marc's:

A symmetric function $k : \mathcal X \times \mathcal X \to \mathbb R$ is a kernel function iff there is some "feature map" $\varphi : \mathcal X \to \mathcal H$ such that $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$, where $\mathcal H$ is a Hilbert space.

Let $\varphi_i$ be the feature map for $k_i$, and $\mathcal H_i$ its Hilbert space.

Now, $\mathcal H_p := \mathcal H_1 \oplus \mathcal H_2$ is a Hilbert space, and $\varphi_p := \sqrt{a_1} \varphi_1 \oplus \sqrt{a_2} \varphi_2$ is a feature map from $\mathcal X$ to it as long as $a_1, a_2 \ge 0$. (For finite-dimensional feature spaces, this is just concatenating the feature maps together.) Note that \begin{align} \langle \varphi_p(x), \varphi_p(y) \rangle_{\mathcal H_p} &= \langle \sqrt{a_1} \varphi_1(x) \oplus \sqrt{a_2} \varphi_2(x), \sqrt{a_1} \varphi_1(y) \oplus \sqrt{a_2} \varphi_2(x) \rangle_{\mathcal H_1 \oplus \mathcal H_2} \\&= a_1 \langle \varphi_1(x), \varphi_1(y) \rangle_{\mathcal H_1} + a_2 \langle \varphi_2(x), \varphi_2(y) \rangle_{\mathcal H_2} \\&= k_p(x, y) ,\end{align} so $k_p$ has feature map $\varphi_p$, and is therefore a valid kernel.


To your "in general" question at the end: if you want to prove them for arbitrary kernels, the two main techniques are the one Marc used and the one I used. Often, though, for Marc's approach we directly use the Mercer condition rather than the integral form, which can be easier to reason about:

A symmetric function $k : \mathcal X \times \mathcal X \to \mathcal R$ is positive semidefinite if and only if for all $M$, all $x_1, \dots, x_M \in \mathcal X$, and all $c_1, \dots, c_M \in \mathbb R$, $\sum_{i=1}^M \sum_{j=1}^M c_i k(x_i, x_j) c_j \ge 0$.

We can also use the following equivalent form:

A symmetric function $k : \mathcal X \times \mathcal X \to \mathcal R$ is positive semidefinite if and only if for all $M$, all $x_1, \dots, x_M \in \mathcal X$, the matrix $K$ with $K_{ij} = k(x_i, x_j)$ is positive semidefinite.

I previously gave brief proofs for several such properties in this answer.

$\endgroup$
9
  • $\begingroup$ Does having a feature mapping of form $a(x)^Ta(x)$ a sufficient condition for it to be valid kernel? $\endgroup$ – tusharfloyd Oct 15 '15 at 20:08
  • 1
    $\begingroup$ @tusharfloyd Yes; the properties of inner products guarantee Mercer's condition. $\endgroup$ – Danica Oct 15 '15 at 20:11
  • $\begingroup$ Is it true because an inner product k(i,j) will always produce a positive semi-definite K (Gram Matrix) $\endgroup$ – tusharfloyd Oct 15 '15 at 20:15
  • $\begingroup$ @tusharfloyd Yep, exactly. $\endgroup$ – Danica Oct 15 '15 at 20:15
  • 1
    $\begingroup$ For inner product being psd: $\sum_{i,j} c_i \langle x_i, x_j \rangle c_j = \langle \sum_i c_i x_i, \sum_i c_i x_i \rangle \ge 0$ by the properties of inner products. $\endgroup$ – Danica Oct 15 '15 at 20:38

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.