Day 8: What is Linear Regression with Derivation.
Introduction to Linear Regression. Derivation of Ordinary Least Square method.
Jun 08, 2021
Simple Linear Regression / Univariate Linear Regression
As the name suggests this algorithm is used for Regression problems and again from the name we can infer that Linear Regression is a Linear Model. This basically means that this algorithm establishes a linear relationship between the input variable(X) and the single output variable (Y). It is the simplest model in Machine Learning.
When there are multiple input variables(X), it is called Multiple Linear Regression.
Wanna jump right to code, check out complete code on Github.
In this algorithm we consider an input variable - X and one output variable - Y. We have to establish a linear relationship between them. The linear relationship can be defined as follows.
$$ Y = \beta_{0} + \beta_{1}X $$
- $\beta_{1}$ is called scale factor or slope or coefficient
- $\beta_{0}$ is called intercept or bias coefficient
This equation is similar to the slope of a line ie $y = mx +b$ where $m = \beta_{1}$ (Slope of the line) and $b = \beta_{0}$ (Intercept). Hence we can state that in the Simple Linear Regression model we want to draw a line between X and Y which defines the relationship between them.
Assumptions for Linear Regression
- A linear relationship between features and the target variable.
- Additivity means that the effect of changes in one of the features on the target variable does not depend on values of other features. For example, a model for predicting the revenue of a company has one of the two features - the number of items "a" sold and the number of items "b" sold. When a company sells more items "a" the revenue increases and this is independent of the number of items "b" sold. But, if customers who buy "a" stop buying "b", the additivity assumption is violated.
- No correlation between features (no collinearity). This affects the model severely.
- Homoscedasticity
Different types of Linear Regression
- Univariate Linear Regression or Simple Linear Regression - Single Variable Linear Regression is a technique used to model the relationship between a single input independent variable (feature variable) and an output dependent variable using a linear model i.e a line.
- Multiple Linear Regression - It is a statistical technique that uses several explanatory variables to predict the outcome of a single dependent variable.
- Ridge Regression - Ridge Regression is a technique for analyzing multiple regression data that suffer from multicollinearity. When multicollinearity occurs, least squares estimates are unbiased, but their variances are large so they may be far from the true value. By adding a degree of bias to the regression estimates, ridge regression reduces the standard errors
- Lasso Regression - Lasso regression is a type of linear regression that uses shrinkage. Shrinkage is where data values are shrunk towards a central point, like the mean. The lasso procedure encourages simple, sparse models (i.e. models with fewer parameters).
How does Simple Linear Regression work?
The main task of this algorithm is to find the best line which fits the given input data.
The hypothesis is defined by
$$ h_{\theta}(x_{i}) = \beta_{0} + \beta_{1} x_{i}$$
which can be rewritten as
$$\hat{y_{i}} = \beta_{0} + \beta_{1} x_{i} \tag{1}$$
where $h_{\theta}(x_{i})$ represents the predictive response for $i_{th}$ observation.
Ordinary Least Square
One of the most common and accurate methods is the Ordinary Least Square method.
Let us create a dataset first
Our goal is to find a model whose line fits best with respect to the given data.
There should be a minimal error between predicted values and actual values.
Error is the distance (d) of the actual point from the model fit line. The Sum of all the errors can be denoted by E. So we can say
$$ E = \sum_{i=0}^{n} (y_{(actual)} - y_{(predicted)})^2$$
which can be written as for $i_{th}$ value
$$ E = \sum_{i=0}^{n} (y_{i} - \hat{y_{i}})^2 \tag{2}$$
where n is total number of inputs
The square is taken because some points are above the line and some points are below. So to eliminate the negatives we square the value.
The algorithm's goal is to minimize this error function.
Derivation
- Given n inputs and outputs $(x_{i}, y_{i})$
- Find best fit for the line in equation 1 $y_{i} = \beta_{0} + \beta_{1} X_{i}$
- The best fit line should have minimum error. To achieve the same we will have to minimize the error function defined above
Using equation 1 and equation 2
$$ E = \sum_{i=0}^{n} (y_{i} - \beta_{0} - \beta_{1} x_{i})^2 \tag{3} $$
To minimize our above-mentioned cost function, as we have learned in calculus, a univariate optimization involves taking the derivative and setting equal to 0. Similarly, this minimization problem above is solved by setting the partial derivatives equal to 0. That is, take the derivative of (1) with respect to $\beta_{0}$ and set it equal to 0. We then do the same thing for $\beta_{1}$. This gives us,
$$
\frac{\partial E}{\partial \beta_{0}}=\sum_{i=1}^{n}-2\left(y_{i}-\beta_{0}-\beta_{1} x_{i}\right)=0 \tag{4}
$$
and
$$
\frac{\partial E}{\partial \beta_{1}}=\sum_{i=1}^{n}-2x_{i}\left(y_{i}-\beta_{0}-\beta_{1} x_{i}\right)=0 \tag{5}
$$
respectively
Before going further we know for the fact that
$$
\sum_{i=1}^{N} y_{i}=N \bar{y} \tag{6}
$$
where $\bar{y}$ is mean of y
Now let us find the value of $\beta_{0}$ first from equation 2
We can simply divide both sides with -2 which will give
$$
\frac{\partial E}{\partial \beta_{0}}=\sum_{i=1}^{n} \left(y_{i}-\beta_{0}-\beta_{1} x_{i}\right)=0
$$
Using equation 6
$$
n \beta_{0}=n \bar{y}-n \beta_{1} \bar{x}
$$
We simply divide everything by n and amazingly!
$$
\beta_{0}=\bar{y}-\beta_{1} \bar{x} \tag{7}
$$
Now let us find the value of $\beta_{1}$ from equation 5
We can simply divide both sides with -2 again which will give
$$
\sum_{i=1}^{n} x_{i} y_{i}-\beta_{0} x_{i}-\beta_{1} x_{i}^{2}=0
$$
Using equation 6, we can substitute $\beta_{0}$ in the above equation
$$
\sum_{i=1}^{n} x_{i} y_{i}-\left(\bar{y}-\beta_{1} \bar{x}\right) x_{i}-\beta_{1} x_{i}^{2}=0
$$
Note that the summation is applying to everything in the above equation. We can distribute the sum to each term to get,
$$
\sum_{i=1}^{n} x_{i} y_{i}-\bar{y} \sum_{i=1}^{n} x_{i}+\beta_{1} \bar{x} \sum_{i=1}^{n} x_{i}-\beta_{1} \sum_{i=1}^{n} x_{i}^{2}=0
$$
Using equation 6 again we get
$$
\beta_{1}=\frac{\sum_{i=1}^{n} x_{i} y_{i}-n \bar{x} \bar{y}}{\sum_{i=1}^{n} x_{i}^{2}-n \bar{x}^{2}}
$$
You can either look up or derive for yourself that $\sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)\left(y_{i}-\bar{y}\right)=\sum_{i=1}^{n} x_{i} y_{i}-n \bar{x} \bar{y}$. You can also easily derive that $\sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)^{2}=\sum_{i=1}^{n} x_{i}^{2}-n \bar{x}^{2}$. These two can be derived very easily using algebra. Give it a shot yourself.
$$
\beta_{1}=\frac{\sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)\left(y_{i}-\bar{y}\right)}{\sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)^{2}}
$$
Voila! we are done.
Get the complete code on GitHub.