I am reading the Pattern Recognition and Machine Learning book by Bishops. I have some difficulties proving the (6.21) equation. Can someone help me? Image from Bishops book

N.B: If someone has a better title for this question, i'm opened to it as i couldn't find the good words.


1 Answer 1


Here are two proofs:

Gram matrix is psd: For any set of points $\{x_i\}_{i=1}^n$, call the Gram matrix for $k_a$ $A$ and the Gram matrix for $k_b$ $B$. Then the Gram matrix for $k$ is just $A + B$, and we have $$ \alpha^T (A + B) \alpha = \alpha^T A \alpha + \alpha^T B \alpha \ge 0 $$ since $\alpha^T A \alpha \ge 0$, $\alpha^T B \alpha \ge 0$. Thus $k$ is a psd kernel.

Feature maps: This is effectively taking the direct sum of two kernels. Let $\mathcal H_a$ be the RKHS for kernel $k_a$, and $\mathcal H_b$ for $k_b$, with feature maps $\varphi_a : \mathcal X_a \to \mathcal H_a$ and $\varphi_b : \mathcal X_b \to \mathcal H_b$. Define the RKHS $\mathcal H = \mathcal H_a \oplus \mathcal H_b$, where an arbitrary element of $\mathcal H$ is $f_a \oplus f_b$.

(If $\mathcal H_a = \mathbb R^{d_a}$ and $\mathcal H_b = \mathbb R^{d_b}$ are Euclidean spaces, then $\mathcal H = \mathbb R^{d_a + d_b}$ and $f_a \oplus f_b$ is just the concatenation of $f_a$ and $f_b$.)

The inner product is then $$\langle f_a \oplus f_b, f_a' \oplus f_b' \rangle_{\mathcal H} = \langle f_a, f_a' \rangle_{\mathcal H_a} + \langle f_b, f_b' \rangle_{\mathcal H_b}.$$ So we just need to define $\varphi(x) = \varphi_a(x_a) \oplus \varphi_b(x_b)$, in which case we get \begin{align} k( x, x' ) &= \langle \varphi(x), \varphi(x') \rangle_{\mathcal H} \\&= \langle \varphi_a(x_a) \oplus \varphi_b(x_b), \varphi_a(x_a') \oplus \varphi_b(x_b') \rangle_{\mathcal H} \\&= \langle \varphi_a(x_a), \varphi_a(x_a') \rangle_{\mathcal H_a} + \langle \varphi_b(x_b), \varphi_b(x_b') \rangle_{\mathcal H_b} \\&= k_a(x_a, x_a') + k_b(x_b, x_b') .\end{align} We can easily verify this a valid RKHS (sum of two continuous functionals is continuous), and so $k$ is again a psd kernel.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.