# Derivation of normal equations for maximum likelihood and least squares

The question stems from the text Pattern Recognition and Machine Learning by Christopher Bishop, Chapter 3.1.1. To say my maths is rusty is an understatement so I would appreciate any nudge in the right direction regarding the below.

The logarithm of the likelihood functions of a standard univariate Gaussian is given below:

$$(1)\quad \frac{N}{2} \ln \beta - \frac{N}{2}\ln 2 \pi - \frac{\beta}{2}\sum_{n=1}^N\{t_n - \mathbf w^T \mathbf \phi(\mathbf x_n) \}^2$$

Taking the gradient(derivative) with respect to $\mathbf w$ and setting this equal to zero we get:

$$(2)\quad0 = \sum_{n=1}^N\{t_n - \mathbf w^T \mathbf \phi(\mathbf x_n) \}\phi(\mathbf x_n)^T$$

$$(3)\quad0 = \sum_{n=1}^Nt_n \phi(\mathbf x_n)^T - \mathbf w^T(\sum_{n=1}^N \mathbf \phi(\mathbf x_n) \phi(\mathbf x_n)^T)$$

Solving for $\mathbf w$ we get:

$$(4)\quad\mathbf w_{ML}=(\mathbf \Phi^T \mathbf \Phi)^{-1} \mathbf \Phi^T \mathbf {\mathtt t}$$

where

$$(5)\quad\mathbf \Phi = \phi_j(\mathbf x_n)$$

Now for the questions.

(a) In (2) when using the chain rule why do we get $\phi(\mathbf x_n)^T$ instead of $\phi(\mathbf x_n)?$

(b) Is the following valid to get from (3) to (4)? Continuing from (3)

$$\mathbf w^T(\sum_{n=1}^N \mathbf \phi(\mathbf x_n) \phi(\mathbf x_n)^T) = \sum_{n=1}^Nt_n \phi(\mathbf x_n)^T$$

$$[\mathbf w^T(\sum_{n=1}^N \mathbf \phi(\mathbf x_n) \phi(\mathbf x_n)^T)]^T = [\sum_{n=1}^Nt_n \phi(\mathbf x_n)^T]^T$$

$$\mathbf w_{ML}(\sum_{n=1}^N \mathbf \phi(\mathbf x_n) \phi(\mathbf x_n)^T) = \sum_{n=1}^N \phi(\mathbf x_n) t_n$$

Where $\sum_{n=1}^N \mathbf \phi(\mathbf x_n) \phi(\mathbf x_n)^T$ = $(\mathbf \Phi^T \mathbf \Phi)$ and $\sum_{n=1}^N \phi(\mathbf x_n) t_n = \mathbf \Phi^T \mathbf {\mathtt t}$

$$\mathbf w_{ML}(\mathbf \Phi^T \mathbf \Phi)(\mathbf \Phi^T \mathbf \Phi)^{-1}=(\mathbf \Phi^T \mathbf \Phi)^{-1} \mathbf \Phi^T \mathbf {\mathtt t}$$

$$(4)\quad\mathbf w_{ML}=(\mathbf \Phi^T \mathbf \Phi)^{-1} \mathbf \Phi^T \mathbf {\mathtt t}$$

If it is not valid can you please point out where.

(a) no reason, really. Expressing the gradient as a row vector sets up for what is done in step 3, but you could also have is proportional to $\phi(x_n)$ and then write $(t_n-w^T\phi(x_n))^2 = (t_n-\phi(x_n)^Tw)^2$ and then multiply this scalar by the column vector $\phi(x_n)$ on the left.

(b) Yes, but in the third line $w_{ML}$ should be on the right of $\Phi^T\Phi.$ Also you should probably be explicit about which index is which here. $\Phi = \phi_j(x_n)$ seems to suggest the second index is $n$ but what you really have in this notation is $\Phi_{nj} = \phi_j(x_n).$

(a) Chris Bishop's presentation is dual to the one in Bierman's Factorization Methods for Discrete Sequential Estimation.". In Bishop's, the weights — uknown quantities to be estimated — are in an $M$‑dimensional column vector and the values of the basis functions — the modeling functions that purport to match the data within some error — are also assembled in $M$‑dimensional column vectors, $N$ of them, one $M$‑dimensional value for each input datum $\boldsymbol{x}_{n\in[1..N]}$. The components of the evaluated modeling functions are assembled in Bishop's design matrix

$$\left(\boldsymbol{\Phi}_{N\times{M}}\right)_{nj}=\phi_{j\in[1..M]}\left(\boldsymbol{x}_{n\in[1..N]}\right)=\phi\left(\boldsymbol{x}_n\right)\,\phi\left(\boldsymbol{x}_n\right)^\intercal$$

@spaceisdarkgreen above correctly clarified the indices: Bishop tacitly rotates his $N$ column vectors $\phi\left(\boldsymbol{x}_n\right)$ into rows to assemble $\boldsymbol{\Phi}$. Because of these choices, Bishop must write $\mathbf{t}=\boldsymbol{w}^\intercal\boldsymbol{\Phi}^\intercal$ to get all the "label" data $\mathbf{t}=\left(\boldsymbol{t}_1,\boldsymbol{t}_2,\ldots,\boldsymbol{t}_N,\right)^\intercal$ because he tacitly transposed each $\phi\left(\boldsymbol{x}_n\right)$ to build $\boldsymbol{\Phi}$ and must transpose $\boldsymbol{\Phi}$ again to use it.

Bierman, on the other hand, de-emphasizes the modeling functions and just calls their $N$ values "observation partials," each of dimension $M$. This means partial derivatives of each of the $N$ predicted labels with respect to the $M$ unknown parameters $\boldsymbol{w}$. As partial derivatives of $\boldsymbol{w}$, they are already row-vectors, and don't need transposing (in this answer, we can see Bierman's partials as values of covector differential forms in the $M$‑dimensional cotangent space of the outputs of the modeling functions; see Hubbard and Hubbard for differential forms).

Assembling these $N$ values of the $M$‑dimensional partials as rows is natural in this treatment, no transposes required. Bierman denotes the design matrix as $A$ and multiplies it on the left of the column vector $\boldsymbol{w}$ of parameters-to-estimate. Bierman writes $A\,{\boldsymbol{w}}$ in place of Bishop's

$$\boldsymbol{w}^\intercal\phi\left(\boldsymbol{x}_n\right)\,\phi\left(\boldsymbol{x}_n^\intercal\right)=\boldsymbol{w}^\intercal_{1\times{M}}\,\boldsymbol{\Phi}^\intercal_{M\times{N}}$$

Because of the transposes, Bishop's $\boldsymbol{w}^\intercal\,\boldsymbol{\Phi}^\intercal$ is dual to Bierman's $A\,\boldsymbol{w}$.

I'm a physicist, so I find Bierman's notion of observation partials intuitive. Partials are 1‑forms and thus covectors (row vectors); every physicist drills this ad nauseum. I also find Bierman's notation through his whole book less cumbersome than Bishop's; that's a mere matter of taste. So far as I can tell, the two treatments produce the same answers, at least after we figure out how Bishop's $\alpha$ and $\beta$ relate to Bierman's a-priori covariances in his ultimate destination: Kalman filtering. That's a non-trivial task I won't address here.

The duality might have a philosophical edge. Bishop comes at linear regression from the viewpoint of approximating arbitrary functions as linear combinations of a finite number $M$ of basis functions, and he is explicit about the generality of the basis functions through his $\phi$ notation. Bishop is functions first, weights second, if you will. Bierman comes at the same problem from the standpoint of fitting data via recursive filters like Kalman's and is preoccupied with various factorizations of the design-or-partials matrix for performance (memory and time) and numerical stability, e.g., SVD and Cholesky. Bierman's recursive filters process the $A$ matrix one row (one gradient) at a time, and so execute in constant, $O(M)$ memory at the outset (see Beckman's self-publshed papers on Kalman Folding [disclaimer; I wrote them]). Bierman is weights first, functions second if you will. He is less concerned with the source of the partials, be they through evaluating basis functions or through deeper approximation schemes, which are a cottage industry in Kalman filtering (see Zarchan and Musoff and Yaacov Bar-Shalom).

(b) I concur with the answer above.