Linear Regression

Linear Regression is defined as an algorithm that provides a linear relationship between an independent variable and a dependent variable to predict the outcome of future events. It’s a basic algorithm of supervised learning.

For example, from the price dataset of more than 4000 houses, we will build a model to predict the house price that based on 3 attributes: bedrooms, bathrooms & floors. The input values are defined as a column vector:

$$\mathbf{x}=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]$$

So we have the output model that depends on the input values:

$$\begin{array}{rl}y\approx \hat{y}=f(x)& =x_1{w}_1+x_2{w}_2+x_3{w}_3\\ & =\left[\begin{array}{ccc}{x}_1& x_2& x_3\end{array}\right]\left[\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right]\\ & ={\mathbf{x}}^T\mathbf{w}\end{array}$$

Our expectation is that the prediction error $e$ between $y$ & $\hat{y}$ should be minimum.

$$\begin{array}{r}\frac{1}{2}{e}^2=\frac{1}{2}(y-\hat{y}{)}^2=\frac{1}{2}(y-{\mathbf{x}}^T\mathbf{w}{)}^2\end{array}$$

We have to use the square of $e$ because $y-\hat{y}$ can be negative. $\frac{1}{2}$ is used to simplify the calculation of derivatives.

1. Loss function

When we have $N$ training data points, each traning data point has the prediction error. Our problem is to create a model so that the sum of the prediction errors is minimum. It’s similar to find the weight vector $\mathbf{w}$ so that the following function has the minimum value.

$$\begin{array}{r}\mathcal{L}(\mathbf{w})=\frac{1}{2N}\sum _{i=1}^N(y_i–{\mathbf{x}}_i^T{\mathbf{w}}_i{)}^2\end{array}$$

In machine learning, the loss function is the average of the error at each point that why we have the $\frac{1}{2N}$ in that formula. As you can see, $\mathcal{L}(\mathbf{w})$ has the relationship with 2-norm, so we can transform above formula to:

$$\begin{array}{rl}\mathcal{L}(\mathbf{w})& =\frac{1}{2N}||\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_N\end{array}\right]–\left[\begin{array}{c}{\mathbf{x}}_1^T\\ {\mathbf{x}}_2^T\\ ⋮\\ {\mathbf{x}}_N^T\end{array}\right]\mathbf{w}|{|}_2^2\\ & =\frac{1}{2N}\parallel \mathbf{y}–{\mathbf{X}}^{\mathbf{T}}\mathbf{w}{\parallel }_2^2\end{array}$$

2. Solution

The next step, we need to find the solution for that loss function by solving the derivative equation.

$$\begin{array}{rl}\mathcal{L}(\mathbf{w})& =\frac{1}{2N}\parallel \mathbf{y}–{\mathbf{X}}^{\mathbf{T}}\mathbf{w}{\parallel }_2^2\\ & =\frac{1}{2N}(\mathbf{y}–{\mathbf{X}}^{\mathbf{T}}\mathbf{w}{)}^T(\mathbf{y}–{\mathbf{X}}^{\mathbf{T}}\mathbf{w})(2.1)\end{array}$$

We have this transformation by using the equation $||x|{|}_2^2=x^{T}x$ when $x$ is a vector. Let’s prove this one:

$$\begin{array}{r}x=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]\Rightarrow x^{T}x=\left[\begin{array}{ccc}{x}_1& x_2& x_3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=x_1^2+x_2^2+x_3^2=||x|{|}_2^2\end{array}$$

From (2.1) we have

$$\begin{array}{rl}\frac{\mathrm{\nabla }\mathcal{L}(\mathbf{w})}{\mathrm{\nabla }\mathbf{w}}& =\frac{1}{N}(\mathbf{X}{\mathbf{X}}^{\mathbf{T}}\mathbf{w}–\mathbf{X}\mathbf{y})(2.2)\end{array}$$

You can read this post to understand about (2.2)

$$\begin{array}{r}\frac{\mathrm{\nabla }\mathcal{L}(\mathbf{w})}{\mathrm{\nabla }\mathbf{w}}=0⟺\mathbf{X}{\mathbf{X}}^{\mathbf{T}}\mathbf{w}=\mathbf{X}\mathbf{y}\end{array}(2.3)$$

$\mathbf{A}=\mathbf{X}{\mathbf{X}}^{\mathbf{T}}$ is a square matrix.

– If $\mathbf{A}$ is invertible, so (2.3) has the solution:

$$\mathbf{w}={\mathbf{A}}^{-1}\mathbf{X}\mathbf{y}$$

– If $\mathbf{A}$ is not invertible, we must find pseudoinverse ${\mathbf{A}}^{+}$ of $\mathbf{A}$. We know that every matrix has a SVD, so now the problem is to find pseudoinverse of a SVD.

$$\begin{array}{rl}\mathbf{w}& ={\mathbf{A}}^{+}\mathbf{X}\mathbf{y}\\ & =(U\mathrm{\Sigma }{V}^T{)}^{+}\mathbf{X}\mathbf{y}\\ & =V{\mathrm{\Sigma }}^{+}{U}^T\mathbf{X}\mathbf{y}\end{array}(2.4)$$

Where ${\mathrm{\Sigma }}^{+}$ is formed from $\mathrm{\Sigma }$ by taking the reciprocal of all the non-zero elements, leaving all the zeros alone, and making the matrix the right shape. If $\mathrm{\Sigma }$ is an $m\times n$ matrix, then ${\mathrm{\Sigma }}^{+}$ must be an $n\times m$ matrix.

In fact, solving derivative equations is an expensive calculation. So we need to use another way (Gradient Descent) to find the minimum of a function. It should be cheaper (faster) to find the solution using the gradient descent.