5
$\begingroup$

Notation: $\textbf{w}$ is an M-dimensional vector of parameters (including the bias parameter), $\textbf{x}_n$ is an M-dimensional vector of the features of each training example, $\textbf{t}$ is an N-dimensional vector of target values - where $t_n$ is the output of the nth training example and finally, $\Phi$ is an $M \times N$ design matrix.

During studying linear regression, I naturally came across the derivation of the normal equation. In his book, Christopher M. Bishop begins by the log of the likelihood function given by:

$$ \frac{N}{2} \ln \beta - \frac{N}{2} \ln(2\pi) - \frac{\beta}{2}\sum_{n=1}^N\{t_n - \textbf{w}^T \phi(\textbf{x}_n)\}^2 \tag{1} $$

With the goal of calculating the maximum likelihood of the parameters, he then calculates the derivative with respect to $w$:

$$ \bigtriangledown p(\textbf{t}| \textbf{w},\beta) = \beta \sum_{n=1}^N\{t_n - \textbf{w}^T \phi(\textbf{x}_n)\}\phi(\textbf{x}_n)^T \tag 2 $$

After which he sets the derivative to zero, in order to maximise the likelihood function

$$ 0 = \sum_{n=1}^N t_n \phi(\textbf{x}_n)^T - \textbf{w}^T \bigg(\sum_{n=1}^N \phi(\textbf{x}_n)\phi(\textbf{x}_n)^T \bigg) \tag 3 $$

So far so good. But then, the result for the maximum likelihood of the parameters $w$ is written as:

$$ \textbf{w}_{ML} = (\Phi^T\Phi)^{-1} \Phi^T \textbf{t} \tag 4 $$

My own derivation from equation $(3)$ to equation $(4)$ goes along the following lines:

\begin{align*} \Phi^T \Phi \textbf{w} &= \Phi^T \textbf{t} \tag 5 \\ (\Phi^T \Phi)^{-1} \Phi^T \Phi \textbf{w} &= (\Phi^T \Phi)^{-1} \Phi^T \textbf{t} \tag 6 \\ \textbf{w} &= (\Phi^T \Phi)^{-1} \Phi^T \textbf{t} \tag 7 \end{align*}

My question is this: How does one go from equation $(3)$ to equation $(4)$. How does the supposed $ \textbf{w}^T \phi(\textbf{x}_n) \phi(\textbf{x}_n)$ become $\Phi^T \Phi \textbf{w}$ ? I do of course understand that given the dimensions of the matrix $\Phi$ and the vector $\textbf{w}$, that this is the only way to multiply the two entities. But what is the steps that one would follow in a formal derivation in order to reach such a result?

$\endgroup$
4
$\begingroup$

$$ 0 = \sum_{n=1}^N t_n \phi(\textbf{x}_n)^T - \textbf{w}^T \bigg(\sum_{n=1}^N \phi(\textbf{x}_n)\phi(\textbf{x}_n)^T \bigg) \tag 3 $$

$$ \textbf{w}^T \bigg(\sum_{n=1}^N \phi(\textbf{x}_n)\phi(\textbf{x}_n)^T \bigg) = \sum_{n=1}^N t_n \phi(\textbf{x}_n)^T \tag a $$

Recall the Delta Matrix is defined as: $$ \Phi =\begin{pmatrix} \phi _{ 0 }(x_{ 1 }) & \phi _{ 1 }(x_{ 1 }) & \dots & \phi _{ M-1 }(x_{ 1 }) \\ \phi _{ 0 }(x_{ 2 }) & \phi _{ 1 }(x_{ 2 }) & \dots & \phi _{ M-1 }(x_{ 2 }) \\ \vdots & \vdots & \ddots & \vdots \\ \phi _{ 0 }(x_{ N }) & \phi _{ 1 }(x_{ N }) & \dots & \phi _{ M-1 }(x_{ N }) \end{pmatrix}$$

We can show that below $$ \sum_{n=1}^N \phi(\textbf{x}_n)\phi(\textbf{x}_n)^T = \Phi^T\Phi$$

$$ \begin{equation} \begin{split} \sum_{n=1}^N \phi(\textbf{x}_n)\phi(\textbf{x}_n)^T & = \begin{bmatrix} \phi _{ 0 }(x_{ 1 }) \\ \phi _{ 1 }(x_{ 1 }) \\ \vdots \\ \phi _{ M-1 }(x_{ 1 }) \end{bmatrix}\begin{bmatrix} \phi _{ 0 }(x_{ 1 }) & \phi _{ 1 }(x_{ 1 }) & \dots & \phi _{ M-1 }(x_{ 1 }) \end{bmatrix}+\dots \\ & +\begin{bmatrix} \phi _{ 0 }(x_{ N }) \\ \phi _{ 1 }(x_{ N }) \\ \vdots \\ \phi _{ M-1 }(x_{ N }) \end{bmatrix}\begin{bmatrix} \phi _{ 0 }(x_{ N }) & \phi _{ 1 }(x_{ N }) & \dots & \phi _{ M-1 }(x_{ N }) \end{bmatrix}\\ & = \begin{bmatrix} \phi _{ 0 }(x_{ 1 })\phi _{ 0 }(x_{ 1 }) & \phi _{ 0 }(x_{ 1 })\phi _{ 1 }(x_{ 1 }) & \dots & \phi _{ 0 }(x_{ 1 })\phi _{ M-1 }(x_{ 1 }) \\ \phi _{ 1 }(x_{ 1 })\phi _{ 0 }(x_{ 1 }) & \phi _{ 1 }(x_{ 1 })\phi _{ 1 }(x_{ 1 }) & \dots & \phi _{ 1 }(x_{ 1 })\phi _{ M-1 }(x_{ 1 }) \\ \vdots & \vdots & \ddots & \vdots \\ \phi _{ M-1 }(x_{ 1 })\phi _{ 0 }(x_{ 1 }) & \phi _{ M-1 }(x_{ 1 })\phi _{ 1 }(x_{ 1 }) & \dots & \phi _{ M-1 }(x_{ 1 })\phi _{ M-1 }(x_{ 1 }) \end{bmatrix}+\dots \\ & +\begin{bmatrix} \phi _{ 0 }(x_{ N })\phi _{ 0 }(x_{ N }) & \phi _{ 0 }(x_{ N })\phi _{ 1 }(x_{ N }) & \dots & \phi _{ 0 }(x_{ N })\phi _{ M-1 }(x_{ N }) \\ \phi _{ 1 }(x_{ N })\phi _{ 0 }(x_{ N }) & \phi _{ 1 }(x_{ N })\phi _{ 1 }(x_{ N }) & \dots & \phi _{ 1 }(x_{ N })\phi _{ M-1 }(x_{ N }) \\ \vdots & \vdots & \ddots & \vdots \\ \phi _{ M-1 }(x_{ N })\phi _{ 0 }(x_{ N }) & \phi _{ M-1 }(x_{ N })\phi _{ 1 }(x_{ N }) & \dots & \phi _{ M-1 }(x_{ N })\phi _{ M-1 }(x_{ N }) \end{bmatrix} \\ & = \begin{bmatrix} \sum _{ i }^{ N }{ \phi _{ 0 }(x_{ i })\phi _{ 0 }(x_{ i }) } & \sum _{ i=1 }^{ N }{ \phi _{ 0 }(x_{ i })\phi _{ 1 }(x_{ i }) } & \dots & \sum _{ i=1 }^{ N }{ \phi _{ 0 }(x_{ i })\phi _{ M-1 }(x_{ i }) } \\ \sum _{ i=1 }^{ N }{ \phi _{ 1 }(x_{ i })\phi _{ 0 }(x_{ i }) } & \sum _{ i=1 }^{ N }{ \phi _{ 1 }(x_{ i })\phi _{ 1 }(x_{ i }) } & \dots & \sum _{ i=1 }^{ N }{ \phi _{ 1 }(x_{ i })\phi _{ M-1 }(x_{ i }) } \\ \vdots & \vdots & \ddots & \vdots \\ \sum _{ i=1 }^{ N }{ \phi _{ M-1 }(x_{ i })\phi _{ 0 }(x_{ i }) } & \sum _{ i=1 }^{ N }{ \phi _{ M-1 }(x_{ i })\phi _{ 1 }(x_{ i }) } & \dots & \sum _{ i=1 }^{ N }{ \phi _{ M-1 }(x_{ i })\phi _{ M-1 }(x_{ i }) } \end{bmatrix} \\ & = \begin{bmatrix} \phi _{ 0 }(x_{ 1 }) & \phi _{ 0 }(x_{ 2 }) & \dots & \phi _{ 0 }(x_{ N }) \\ \phi _{ 1 }(x_{ 1 }) & \phi _{ 1 }(x_{ 2 }) & \dots & \phi _{ 1 }(x_{ N }) \\ \vdots & \vdots & \ddots & \vdots \\ \phi _{ M-1 }(x_{ 1 }) & \phi _{ M-1 }(x_{ 2 }) & \dots & \phi _{ M-1 }(x_{ N }) \end{bmatrix}\begin{bmatrix} \phi _{ 0 }(x_{ 1 }) & \phi _{ 1 }(x_{ 1 }) & \dots & \phi _{ M-1 }(x_{ 1 }) \\ \phi _{ 0 }(x_{ 2 }) & \phi _{ 1 }(x_{ 2 }) & \dots & \phi _{ M-1 }(x_{ 2 }) \\ \vdots & \vdots & \ddots & \vdots \\ \phi _{ 0 }(x_{ N }) & \phi _{ 1 }(x_{ N }) & \dots & \phi _{ M-1 }(x_{ N }) \end{bmatrix} \\ & = \Phi^T\Phi \end{split} \end{equation}$$

Therefore we get the following.

$$ \textbf{w}^T \bigg(\Phi^T\Phi \bigg) = \sum_{n=1}^N t_n \phi(\textbf{x}_n)^T \tag b $$

Next we transpose both sides

$$ \bigg( \textbf{w}^T \bigg(\Phi^T\Phi \bigg) \bigg)^T = \bigg(\sum_{n=1}^N t_n \phi(\textbf{x}_n)^T \bigg)^T \tag b $$

$$ \Phi^T\Phi \textbf{w} = \sum_{n=1}^N t_n \phi(\textbf{x}_n) \tag c $$

Similarly, $$\sum_{n=1}^N t_n \phi(\textbf{x}_n) = t_{ 1 }\begin{bmatrix} \phi _{ 0 }(x_{ 1 }) \\ \phi _{ 1 }(x_{ 1 }) \\ \vdots \\ \phi _{ M-1 }(x_{ 1 }) \end{bmatrix}\quad +\quad \dots \quad +\quad t_{ N }\begin{bmatrix} \phi _{ 0 }(x_{ N }) \\ \phi _{ 1 }(x_{ N }) \\ \vdots \\ \phi _{ M-1 }(x_{ N }) \end{bmatrix}\quad =\quad \Phi ^{ T }{ t }$$

Finally we get

$$ \Phi^T\Phi \textbf{w} = \Phi ^{ T }{ t } \tag 5 $$

$\endgroup$
  • $\begingroup$ @ NathanN - This is really a great help.. $\endgroup$ – KGhatak Dec 14 '19 at 9:57

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.