Linear Regression

Linear Regression is a powerful tool used for prediction and forecasting in many fields. It's the starting point for regression analysis from an optimization viewpoint.

Suppose we have data with two features like in the figure below. This data represents the number of people in a specific state (x-axis) and the number of traffic accidents in each state (y-axis). We want to develop a model for this data. It looks like we can use a linear model (a straight line) to describe the relationship.

$f(x) = ax + b$

Optimization: Finding the Best Line

How do we find the best line (i.e., determine the parameters 'a' and 'b')? This is the crux of linear regression.

Cost Function: Measurement of Errors

Figure 2. The difference between the predicted value of the linear model and the actual data.

To determine which line best describes our data, we can define an error ( $e$ ) for each data point ( $i$ ) as follows:

$e_i = \hat{y_i} - y_i$

Here, $\hat{y_i}$ is the predicted y-value from our model, and $y_i$ is the actual y-value from our data.

To get a positive error irrespective of the sign, we square it:

$e_i = (\hat{y_i} - y_i)^2$

And to simplify future differentiation, we divide it by 2:

$e_i = \frac{1}{2}(\hat{y_i} - y_i)^2$

Now, the average error for all data (total number of data = N) is:

$E = \frac{1}{2N}\sum_{i=1}^N(\hat{y_i} - y_i)^2$

We already know that $\hat{y_i} = ax_i + b$ , so we substitute:

$E = \frac{1}{2N}\sum_{i=1}^N(ax_i + b - y_i)^2$

Cost Function: Visualization

The previously calculated $E$ is called a "cost function". The lower its value, the better the model's ability to explain the data.

We can view this cost function $E$ as a function of $a$ and $b$ , because $x_i$ and $y_i$ are given in our data.

$E = f(a,b) = \frac{1}{2N}\sum_{i=1}^N(ax_i + b - y_i)^2$

The challenge now is to find the values of $a$ and $b$ that minimize $E$ .

Figure 3. Cost function and its minimum value in a space where slope and intercept are domain.

Cost Function: Calculation

There are many ways to find the minimum value of a function, one common method being gradient descent.

Gradient descent is a method that allows us to iteratively move in the direction of steepest descent until we reach the minimum of the function.

Therefore, we can update the parameter $a,b$ after setting it to an arbitrary value in the function $f(a,b)$ we want to obtain.

The vector $\begin{bmatrix} a, b \end{bmatrix} ^ T$ may be updated as follows.

$\begin{bmatrix} a \\ b \end{bmatrix} := \begin{bmatrix} a \\ b \end{bmatrix} -α∇f(a,b)$

$α = learing rate$

We start with initial guesses for $a$ and $b$ and update these guesses iteratively using the following update rules:

$a:=a−α\frac{∂f}{∂a}$

$b:=b−α\frac{∂f}{∂b}$

Figure 5. The process of finding the minimum value of the cost function using gradient descent.

where $α$ is the learning rate, and $∂f/∂a$ and $∂f/∂b$ are the gradients of the function with respect to $a$ and $b$ .

By repeating these steps, we will eventually find the values of $a$ and $b$ that minimize the cost function $E = f(a,b)$ , thereby giving us the best line that fits our data.