Deriving the maximum likelihood for the parameters in linear regression

Question

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?

Answer 1

$$ 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 $$