Ex. 5.16

Ex. 5.16

Consider the ridge regression problem (5.53), and assume $M\ge N$. Assume you have a kernel $K$ that computes the inner product $K(x,y)=\sum _{m=1}^M{h}_m(x)h_m(y)$.

(a)

Derive (5.62) on page 171 in the text. How would you compute the matrices $\mathbf{\text{V}}$ and ${\mathbf{\text{D}}}_{\gamma }$, given $K$? Hence show that (5.63) is equivalent to (5.53).

(b)

Show that

$$\begin{array}{rcl}\hat{\mathbf{f}}& =& \mathbf{\text{H}}\hat{\beta }\\ & =& \mathbf{\text{K}}(\mathbf{\text{K}}+\lambda \mathbf{\text{I}}{)}^{-1}\mathbf{\text{y}},\end{array}$$

where $\mathbf{\text{H}}$ is the $N\times M$ matrix of evaluations $h_m(x_i)$, and $\mathbf{\text{K}}=\mathbf{\text{H}}{\mathbf{\text{H}}}^T$ the $N\times N$ matrix of inner-product $h(x_i{)}^{T}h(x_j)$.

(c)

Show that

$$\begin{array}{rcl}\hat{f}(x)& =& h(x{)}^T\hat{\mathit{\beta }}\\ & =& \sum _{i=1}^{N}K(x,x_i)\widehat{{\mathit{\alpha }}_i}\end{array}$$

and $\hat{\mathit{\alpha }}=(\mathbf{\text{K}}+\lambda \mathbf{\text{I}}{)}^{-1}\mathbf{\text{y}}$.

(d)

How would you modify your solution if $M<N$?

Soln. 5.16

(a)

By definition of the kernel $K$, we have

$$K(x,y)=\sum _{m=1}^M{h}_m(x)h_m(y)=\sum _{i=1}^{\mathrm{\infty }}{\gamma }_i{\varphi }_i(x){\varphi }_i(y).$$

Multiply each summand above by ${\varphi }_k(x)$ and calculate $⟨K(x,y),{\varphi }_k(x)⟩$,

$$\begin{array}{}\text{(1)}& \sum _{m=1}^M⟨h_m(x),{\varphi }_k(x)⟩h_m(y)=\sum _{i=1}^{\mathrm{\infty }}⟨{\varphi }_i(x),{\varphi }_k(x)⟩{\varphi }_i(y).\end{array}$$

Since $\{{\varphi }_i,i=1,...,\mathrm{\infty }\}$ are orthogonal, we have

$$⟨{\varphi }_i(x),{\varphi }_k(x)⟩=\{\begin{array}{ll}1& \text{ if }i=k,\\ 0& \text{ otherwise.}\end{array}$$

Thus, $\text{(1)}$ becomes

$$\sum _{m=1}^M⟨h_m(x),{\varphi }_k(x)⟩h_m(y)={\gamma }_k{\varphi }_k(y).$$

Let $g_{km}=⟨h_m(x),{\varphi }_k(x)⟩$ and calculate $⟨K(x,y),{\varphi }_l(y)⟩$, we get

$$\begin{array}{rcl}\sum _{m=1}^M{g}_{km}{h}_m(y)& =& {\gamma }_k{\varphi }_k(y),\\ \sum _{m=1}^M{g}_{km}⟨h_m(y),{\varphi }_l(y)⟩& =& {\gamma }_k⟨{\varphi }_k(y),{\varphi }_l(y)⟩,\\ \sum _{m=1}^M{g}_{km}{g}_{lm}& =& {\gamma }_k{\delta }_{k,l}\end{array}$$

where ${\delta }_{k,l}=1$ if $k=l$ and 0 otherwise.

Let ${\mathbf{\text{G}}}_M=\{g_{nm}\}\in {\mathbb{R}}^{M\times N}$, we have

$${\mathbf{\text{G}}}_M{\mathbf{\text{G}}}_M^T=\text{diag}\{{\gamma }_1,{\gamma }_2,...,{\gamma }_M\}={\mathbf{\text{D}}}_{\gamma }.$$

Let ${\mathbf{\text{V}}}^T={\mathbf{\text{D}}}_{\gamma }^{-\frac{1}{2}}{\mathbf{\text{G}}}_M$, we have

$$\mathbf{\text{V}}{\mathbf{\text{V}}}^T{\mathbf{\text{G}}}_M^T={\mathbf{\text{G}}}_M^T{\mathbf{\text{D}}}_{\gamma }^{-1}{\mathbf{\text{G}}}_M={\mathbf{\text{I}}}_N.$$

Let $h(x)=(h_1(x),h_2(x),...,h_M(x){)}^T$ and $\varphi (x)=({\varphi }_1(x),{\varphi }_2(x),...,{\varphi }_M(x){)}^T$, then the three equations above can be rewritten as

$$\begin{array}{rcl}{\mathbf{\text{G}}}_{M}h(x)& =& {\mathbf{\text{D}}}_{\gamma }\varphi (x)\\ \mathbf{\text{V}}{\mathbf{\text{D}}}_{\gamma }^{-\frac{1}{2}}{\mathbf{\text{G}}}_{M}h(x)& =& \mathbf{\text{V}}{\mathbf{\text{D}}}_{\gamma }^{-\frac{1}{2}}{\mathbf{\text{D}}}_{\gamma }\varphi (x)\\ h(x)& =& \mathbf{\text{V}}{\mathbf{\text{D}}}_{\gamma }^{\frac{1}{2}}.\end{array}$$

To show that (5.63) is equivalent to (5.53) in the text, we start with (5.63). Let $\beta =({\beta }_1,{\beta }_2,...,{\beta }_m{)}^T$ and $c={\mathbf{\text{D}}}_{\gamma }^{\frac{1}{2}}{\mathbf{\text{V}}}^T\beta$,

$$\begin{array}{rcl}& & \underset{\{{\beta }_m{\}}_1^M}{min}\sum _{i=1}^N{(y_i-\sum _{m=1}^M{\beta }_m{h}_m(x_i))}^2+\lambda \sum _{m=1}^M{\beta }_m^2\\ & =& \underset{\beta }{min}\sum _{i=1}^N(y_i-{\beta }^{T}h(x_i){)}^2+\lambda {\beta }^T\beta \\ & =& \underset{\beta }{min}\sum _{i=1}^N(y_i-{\beta }^T\mathbf{\text{V}}{\mathbf{\text{D}}}_{\gamma }^{\frac{1}{2}}\varphi (x_i){)}^2+\lambda {\beta }^T\beta \\ & =& \underset{c}{min}\sum _{i=1}^N(y_i-c^T\varphi (x_i){)}^2+\lambda (\mathbf{\text{V}}{\mathbf{\text{D}}}_{\gamma }^{\frac{1}{2}}c{)}^T\mathbf{\text{V}}{\mathbf{\text{D}}}_{\gamma }^{\frac{1}{2}}c\\ & =& \underset{c}{min}\sum _{i=1}^N(y_i-c^T\varphi (x_i){)}^2+\lambda c^{T}c{\mathbf{\text{D}}}_{\gamma }^{-1}\\ & =& \underset{\{c_j{\}}_1^{\mathrm{\infty }}}{min}\sum _{i=1}^N{(y_i-\sum _{j=1}^{\mathrm{\infty }}{c}_j{\varphi }_j(x_i))}^2+\lambda \sum _{j=1}^{\mathrm{\infty }}\frac{c_j^2}{{\gamma }_j},\end{array}$$

which is (5.53) in the text.

(b)

Recall that in (a) we have

$$\underset{\beta }{min}\sum _{i=1}^N(y_i-{\beta }^{T}h(x_i){)}^2+\lambda {\beta }^T\beta .$$

Taking derivative w.r.t $\beta$ and setting it to be zero yields

$$-{\mathbf{\text{H}}}^T(\mathbf{\text{y}}-\mathbf{\text{H}}\hat{\beta })+\lambda \hat{\beta }=0.$$

Thus we have

$$\hat{\beta }=({\mathbf{\text{H}}}^T\mathbf{\text{H}}+\lambda \mathbf{\text{I}}{)}^{-1}{\mathbf{\text{H}}}^T\mathbf{\text{y}}$$

and

$$\hat{\mathbf{f}}=\mathbf{\text{H}}({\mathbf{\text{H}}}^T\mathbf{\text{H}}+\lambda \mathbf{\text{I}}{)}^{-1}{\mathbf{\text{H}}}^T\mathbf{\text{y}}.$$

By Woodbury matrix identity, we have

$$\begin{array}{rcl}({\mathbf{\text{H}}}^T\mathbf{\text{H}}+\lambda \mathbf{\text{I}}{)}^{-1}& =& \frac{1}{\lambda }\mathbf{\text{I}}-\frac{1}{\lambda }\mathbf{\text{I}}{\mathbf{\text{H}}}^T{(\mathbf{\text{I}}+\frac{1}{\lambda }\mathbf{\text{H}}{\mathbf{\text{H}}}^T)}^{-1}\mathbf{\text{H}}\cdot \frac{1}{\lambda }\mathbf{\text{I}}.\end{array}$$

Therefore, we have

$$\begin{array}{rcl}\hat{\mathbf{f}}& =& \frac{1}{\lambda }\mathbf{\text{H}}{\mathbf{\text{H}}}^T\mathbf{\text{y}}-\frac{1}{\lambda }\mathbf{\text{H}}{\mathbf{\text{H}}}^T{(\lambda \mathbf{\text{I}}+\mathbf{\text{H}}{\mathbf{\text{H}}}^T)}^{-1}\mathbf{\text{H}}{\mathbf{\text{H}}}^T\mathbf{\text{y}}\\ & =& \frac{1}{\lambda }\mathbf{\text{H}}{\mathbf{\text{H}}}^T[\mathbf{\text{I}}-(\lambda \mathbf{\text{I}}+\mathbf{\text{H}}{\mathbf{\text{H}}}^T{)}^{-1}\mathbf{\text{H}}{\mathbf{\text{H}}}^T]\mathbf{\text{y}}\\ & =& \frac{1}{\lambda }\mathbf{\text{H}}{\mathbf{\text{H}}}^T[(\lambda \mathbf{\text{I}}+\mathbf{\text{H}}{\mathbf{\text{H}}}^T{)}^{-1}(\lambda \mathbf{\text{I}}+\mathbf{\text{H}}{\mathbf{\text{H}}}^T)-(\lambda \mathbf{\text{I}}+\mathbf{\text{H}}{\mathbf{\text{H}}}^T{)}^{-1}\mathbf{\text{H}}{\mathbf{\text{H}}}^T]\mathbf{\text{y}}\\ & =& \frac{1}{\lambda }\mathbf{\text{H}}{\mathbf{\text{H}}}^T[(\lambda \mathbf{\text{I}}+\mathbf{\text{H}}{\mathbf{\text{H}}}^T{)}^{-1}\lambda \mathbf{\text{I}}]\mathbf{\text{y}}\\ & =& \mathbf{\text{H}}{\mathbf{\text{H}}}^T(\lambda \mathbf{\text{I}}+\mathbf{\text{H}}{\mathbf{\text{H}}}^T{)}^{-1}\mathbf{\text{y}}\\ & =& \mathbf{\text{K}}(\mathbf{\text{K}}+\lambda \mathbf{\text{I}}{)}^{-1}\mathbf{\text{y}}.\end{array}$$

(c)

This is directly derived from (b).

(d)

The solution remains the same as $\mathbf{\text{K}}+\lambda \mathbf{\text{I}}$ is invertible as long as $\lambda \ne 0$. When $\lambda =0$ however, we have

$$\hat{\mathbf{f}}=\mathbf{\text{H}}\hat{\beta }=\mathbf{\text{H}}({\mathbf{\text{H}}}^T\mathbf{\text{H}}{)}^{-1}{\mathbf{\text{H}}}^T\mathbf{\text{y}}=\mathbf{\text{y}}.$$