Learning From Data – A Short Course: Exercise 8.15

Consider two finite-dimensional feature transforms \Phi_{1} and \Phi_{2} and their corresponding kernels K_{1} and K_{2}.

(a) Define \Phi(x) = (\Phi_{1}(x), \Phi_{2}(x)). Express the corresponding kernel of \Phi in terms of K_{1} and K_{2}.

    \[ K(x, x') = \Phi(x)^{T}\Phi(x') = \begin{bmatrix} \Phi_{1}(x)^{T} & \Phi_{2}(x)^{T} \end{bmatrix}\begin{bmatrix} \Phi_{1}(x')\\ \Phi_{2}(x') \end{bmatrix} = \Phi_{1}(x)^{T}\Phi_{1}(x') + \Phi_{2}(x)^{T}\Phi_{2}(x') = K_{1}(x, x') + K_{2}(x, x') \]

(b) Consider the matrix \Phi_{1}(x)\Phi_{2}(x)^{T} and let \Phi(x) be the vector representation of the matrix (say, by concatenating all the rows). Express the corresponding kernel of \Phi in terms of K_{1} and K_{2}.

Let a = \Phi_{1}(x) and b = \Phi_{2}(x),we have:

    \[ K(x, x') = \Phi(x)^{T}\Phi(x') = \sum_{i=1}^{d}\sum_{j=1}^{d}a_{i}b_{j}a'_{i}b'_{j} = \sum_{i=1}^{d}a_{i}a'_{i}\sum_{j=1}^{d}b_{j}b'_{j} = \sum_{i=1}^{d}a_{i}a'_{i}K_{2}(x, x') = K_{2}(x, x')\sum_{i=1}^{d}a_{i}a'_{i} = K_{2}(x, x')K_{1}(x, x') \]

(c) Hence, show that if K_{1} and K_{2} are kernels, then so are K_{1} + K_{2} and K_{1}K_{2}.

We can prove this by contradiction, for example: Assume K_{1} and K_{2} are kernels but K_{1} + K_{2} is not, that means we can’t find any transform \Phi such that K(x, x') = K_{1}(x, x') + K_{2}(x, x') =  \Phi(x)^{T}\Phi(x'), however we have just found one possible transform above hence the contradiction, so one part of the above statement follows. The same goes for K_{1}K_{2}.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *