Ordinary Least Squares

Recall that Ordinary Least Squares is a regression problem aiming to minimize the mean squared loss, such that we have objective function:

$$J(\theta ,{\theta }_0)=\frac{1}{n}\sum _{i=1}^n({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)}{)}^2$$

This problem actually has an analytical solution based on calculus.

Analytical/Closed-Form Solution

We can approach this like a minimization problem by taking the derivative of $J$ with respect to $\theta$, set it to 0, and then solve for $\theta$. It’s possible to do this by:

• Finding $\frac{\partial J}{\partial {\theta }_k}$ for $k$ in $1,\dots ,d$
• Constructing a set of $k$ equations of the form $\frac{\partial J}{\partial {\theta }_k}=0$
• Solving the system for values of ${\theta }_k$.

We can work through this in a cool matrix view. Let’s also assume that $x^{(i)}$ have been augmented with an extra input dimension with a value of $1$, so that we can ignore ${\theta }_0$.

Let us think of our training data in terms of matrices $X$ and $Y$, where each column of $X$ is an example and each column of $Y$ is the corresponding output target value:

$$X=\left[\begin{array}{ccc}{x}_1^{(1)}& \dots & x_1^{(n)}\\ ⋮& \ddots & ⋮\\ x_d^{(1)}& \cdots & x_d^{(n)}\end{array}\right],Y=\left[\begin{array}{ccc}{y}^{(1)}& \dots & y^{(n)}\end{array}\right].$$

To make this easier and more standard with most textbooks, we define a new matrix and vector, $W$ and $T$, which are just transposes of our $X$ and $Y$:

$$W=X^T=\left[\begin{array}{ccc}{x}_1^{(1)}& \dots & x_d^{(1)}\\ ⋮& \ddots & ⋮\\ x_1^{(n)}& \cdots & x_d^{(n)}\end{array}\right],T=Y^T=\left[\begin{array}{c}{y}^{(1)}\\ ⋮\\ y^{(n)}\end{array}\right]$$

Now, each row of $W$ corresponds to a sample.

We can then write our objective as:

$$\begin{array}{rl}J(\theta )& =\frac{1}{n}\sum _{i=1}^n{\left(\left(\sum _{j=1}^d{W}_{ij}\theta j\right)-T_i\right)}^2\\ & =\frac{1}{n}\underset{1\times n}{\underbrace{(W\theta -T{)}^T}}\underset{n\times 1}{\underbrace{(W\theta -T)}}\end{array}$$

Here $W\theta$ is a vector of predictions. so $W\theta -T$ is a vector of differences between predictions and labels. When we do $(W\theta -T{)}^T(W\theta -T)$, we’re basically taking the dot product of the vector of differences with itself, which achieves a summing and squaring effect.

To solve this problem, we take the gradient and set it to zero:

$$\begin{array}{rl}{\nabla }_{\theta }J& =\left[\begin{array}{c}\frac{\partial J}{\partial {\theta }_1}\\ ⋮\\ \frac{\partial J}{\partial {\theta }_d}\end{array}\right]\\ & =\frac{2}{n}{W}^T(W\theta -T)\end{array}$$

The gradient has the same shape as $\theta$. The simplified version is basically just the power rule and chain rule (from equation $(2)$). Verifying the shapes, we see:

$$\frac{2}{n}\underset{d\times n}{\underbrace{W^T}}\underset{n\times 1}{\underbrace{(W\theta -T)}}$$

so our result would have shape $d\times 1$, which is the shape we want!

Setting to $0$ and solving, we get:

$$\begin{array}{rl}\frac{2}{n}{W}^T(W\theta -T)& =0\\ W^T(W\theta -T)& =0\\ W^{T}W\theta & =W^{T}T\\ \theta & =(W^{T}W{)}^{-1}{W}^{T}T\end{array}$$

And the dimensions work out!

$$\theta =\underset{d\times d}{\underbrace{(W^{T}W{)}^{-1}}}\underset{d\times n}{\underbrace{W^T}}\underset{n\times 1}{\underbrace{T}}$$

This is cool because it’s a rare closed-form solution!

To be really good and proper, we should also check that this solution wields a minimum, not just a critical point. Also, what if $(W^{T}W)$ is not invertible?