Introduction

Over the years, I keep finding myself to revisit concepts of linear regression, and how it is related to other concepts within statistics, machine learning - which is primarily the reason why I started this site. The goal is to cover the following concepts:

• Regression formulation
• Derivation of solutions
• Variants of Regression / Model Selection methods
• How is Regression related to Anova
• Link to Logistic Regression

I assume knowledge of calculus and linear algebra at the undergraduate level.

Regression

The goal is to estimate a linear relationship between the target variable $Y$ with data/predictors $X$ and parameter $\beta_i$.

In Matrix Notation:

Note, in matrix notation, $\beta_0$ is the intercept term with $x_{i,0}$ equals to some constant. To illustrate:

Assumptions

1. Linear Function - The mean response $E(Y_i )$ at each set of the predictors is a linear function.
2. Independent - The errors $\epsilon_i$ are independent
3. Normally distributed - The errors $\epsilon_i$ at each set of values of predictors are normally distributed.
4. Equal Variances ($\sigma^2$) - Also known as Homoscedasticity : The errors $\epsilon_i$ at each set of values of predictors have equal variances.

In other words,

Problem Formulation

We want to find parameters $\hat{\beta}$ to minimize the mean squared error (MSE) denoted as follows:

where:

• $\hat{y}$ denotes the model prediction
• $x_{i,j}$ denotes the i data point with j predictor. (i-row, j-column)
• $\epsilon_i$ denotes the residual $y_i - \hat{y}_i$
• Total of $N$ data points, with $K$ predictors. Note, in the case where $j$ starts from $0$,then $\beta_0$ is removed and instead $x_{0i}$ is simply 1 or some constant to represent the intercept term.

In Matrix Notation,we denote $e = y-X\hat{\beta}$, then the mean squared error would be defined as:

The notation $e'$ represents transpose, $e^T$ is sometimes used instead.

Note, depending on journals and books:

• error is the difference between the observed value and the true value, this is usually unknown.
• residual is the difference between the observed value and the predicted value by the model. Sometimes we represent this with $\hat{e_i}$.

Solving

Here are the various ways to solve to get $\hat\beta$. Here are a few:

• Ordinary Least Squares Method (OLE)
• Maximum Likelihood Estimation Method (MLE)
• Gradient Descent Method

OLE

Given:

To minimize, we need to find first derivative.

Set derivative to be equals to 0,

If the inverse $(X'X)^{-1}$ exist, then:

Min

To prove that this is indeed the minimum, we find the second derivative and prove that it is always greater than 0.

Under certain conditions, $X'X$ is positive definite. hence for all values of $\hat\beta$, the second derivative is always greater than 0. This proofs that it is the minimum.

Extra Matrix Info

Note, earlier we made some assumptions, to address them:

• If all predictors are independent and $n>k$, then $X$ must have full rank.
  • This might not always be true in practice, e.g if $n<k$ i.e there are more features than data points, OR:
  • some features are a linear combination of other features.
  • usually not a problem and there are tricks to overcome it (feature selection, sampling, using gradient solvers etc)
• A matrix is invertible if and only if it is full rank.
• This implies that $X^TX$ is positive definite. (which states that for any matrix A, A is positive definite if $x^TAx >0 \forall x\in\mathbb{R}$)

Variance of Coefficients

The variance-covariance matrix for $\beta$ is defined as:

and $\sigma^2$ is estimated from $\hat{\sigma}^2$:

Full Proof Notes

Proof of variance

First, Recall that $var(AX) = A(var(x))A^T$.

We start with the following equation and define matrix $A$:

This implies that:

and $\sigma^2$ is estimated with $\hat\sigma = \frac{e'e}{n-k}$.

MLE

Another method or thought process to arrive at the same formulation is by making use of the assumption that residuals are normally distributed, independent with mean 0 and constant variance. This implies that:

The normal density function for the errors is:

Since:

• $\varepsilon_i$ is a function of $\beta,\sigma^2$
  • Think of it as each error depends on the value of $\beta$ and variance.
• each $\varepsilon_i$ is independent, then the joint probability is the product:

Since to maximize the MLE is the same as maximizing the log likelihood since it is a monotonic increasing function, then:

To find $\hat\beta$ we take the first derivative:

This is exactly the same equation as the OLS method, thus:

Gradient Descent

There is another way of solving the values of $\beta$, via gradient descent. This is the algorithm:

Denote the cost function to be $J$ and the predict function to be $h_\beta$:

The additional 1/2 in the cost function to make the derivation easier, but there is no actual impact if you exclude it.

$x_{i,j}$ denotes $i$ data point at $j$ predictor, i.e the $(i,j)$ value in the dataset.

Here is the full procedure,

Simultaneously update $\beta_j$ until convergence with learning rate $\alpha$:

SLR

In the case of simple linear regression, then:

Relation to correlation

Perhaps one way to better understand $\beta$ is to see how it is related to correlation $\rho$ in simple linear regression. To explain this, we need to look at coefficient of determination

Coefficient of determination

The coefficient of determination measures the percentage of variability within the values that can be explained by the regression model. For example $R^2$ x 100 percent of the variation in y is explained by the variation in predictor x.

SST is the maximum sum of squares of errors for the data.

• SST: Total variability in the y value (total sum of squares)
• SSR: Variability explained by the model (Regression sum of squares)
• SSE: Unexplained Variability (Error sum of squares)

Extra Notes on why this relationship is true

(Person) Correlation Coefficient, $r$

The correlation coefficient, $r$, is directly related to the coefficient of determination $R^2$. If $R^2$ is represented in decimal form, then the correlation is the sqaure root. The sign will follow the sign of the slope coefficient $b_1$.

This shows that the coefficient of determination of a simple linear regression is the square of the sample correlation coefficient of $(x_1,y_1),...,(x_n,y_n)$.

Is the Model useful?

In multiple linear regression, a reasonable question to ask is:

Does the regression model contain at least one predictor that is useful?

There are three possible hypothesis testing that are possible,

• All $\beta$ are zero
• A subset of the slope parameters is zero
• one slope parameter is zero

There are others concepts such as sequential sum of squares, or interaction effects, which will not be covered here. IF you are interested:

• 1-way anvoa from scratch
• Anova three types of estimating sum of squares

For the next section,we will talk about anova for the hypothesis $\beta_i = \beta_j =0$.

Anova table

ANOVA stands for ‘Analysis of variance’ as it uses the ratio of between group variation to within group variation, when deciding if there is a statistically significant difference between the groups. Within group variation measures how much the individuals vary from their group mean. Each difference between an individual and their group mean is called a residual. These residuals are squared and added together to give the sum of the squared residuals or the within group sum of squares SSW. Between group variation measures how much the group means vary from the overall mean SSB.

Let's take a look at the Anova table:

The F-statistics with $H_0 : \beta_i =\beta_j = 0$, and $H_a: \beta_i \neq 0$

The F-Test of overall significance in regression is a test of whether or not your linear regression model provides a better fit to a dataset than a model with no predictor variables.

Fisher's LSD tests

The Fishers LSD test is basically a set of individual t tests. It is only used as a followup to ANOVA.

Model Selection

In this section we talk about how to select a subset of predictors. Denote $L(\hat\beta)$ as the likelihood function for the model. This is related to stepwise selection, where we take each set of predictors and evaluate which gives a better information criterion and proceed iteratively.

The next two sections on talks about information criterion, namely AIC and BIC:

AIC

Stands for Akaike information criterion and choose the best model with the lowest AIC:

where k is the number of parameters.

The equation means that we must improve the log-likelihood for every one unit of extra parameter. It is asymptotically equivalent to leave-one-out cross validation.

BIC

Stands for Bayes information criterion, which penalizes complex model more severely. Similarly lowest BIC is taken to identify the "best" model.

Cross Validation

The other method is to do cross validation, such as leave one out, k-fold, etc.

Regularization

This is sort of related to model selection in a way, since we use these methods for feature selection / prevent over fitting.

L1 (Lasso)

Lasso regression is a type of linear regression that uses shrinkage. The acronym “LASSO” stands for Least Absolute Shrinkage and Selection Operator.

The cost function is:

(Note that $|x|$ is not Differentiable at x=0)

This is why in L1 regression, if $\lambda$ is sufficiently large, some of the coefficients will shrink to $0$ due to the absolute value. (e.g it always reduces by that amount as compared to ridge regression!)

L2 (Ridge)

Ridge Regression is a technique for analyzing multiple regression data that suffer from multicollinearity. This basically allows you to always make your matrix invertible - since it adds the identity matrix.

There is also a closed form matrix solution:

Elastic Net

A combination of L1 and L2:

GLM

Generalizing the linear regression model gives generalized linear model (GLM), where each outcome $Y$ to be related to the response variable via a link function. The linear regression is also known as the identity link.

The family of link functions can be found in wikipedia - GLM

We use logistic regression as a motivating example. The link function $g$ is defined by:

Logistic Regression

Recall in logistic regression we are predicting binary class, ${1,0}$.

The logit link function is:

This looks exactly like the sigmoid function which outputs a number between ${0,1}$ - like a probability! Recall:

If we tried to calculate the cost function, we will arrive at a non-convex function with many local minimums. So we need to introduce a new cost function, which is known as sigmoid cross entropy loss.

Introduction to logistic regression

Sigmoid Derivative

The sigmoid derivative is given by:

Given a function linear $z = X \beta$, then

The proof is omiitted.

Cross Entropy

Lets re-define $\sigma(z) = h_\beta(x) = \frac{1}{1+e^{-X\beta}}$ with the following cost function:

Interpretation:

Suppose $\varepsilon$ is small, then $log(\varepsilon)$ can be huge!

For example, $X\beta$ outputs a huge negative value and hence the output prediction $h_\beta(x)$ is $0.00001$ which implies that $\hat{y} = 0$. However if in reality it is $1$, then the cost is equals to $-log 0.00001 = 11.51$!

With this, we can formalize our new cost function:

Gradient Descent

Finding a solution to logistic regression starts from the likelihood function, and there is no analytical solution - instead, gradient descent is used. To find the derivative,

The gradient descent algorithm is as follows:

Surprisingly, the update rule is the same as the one derived by using the sum of the squared errors in linear regression. As a result, we can use the same gradient descent formula for logistic regression as well.

Other/Future notes

These are also useful concepts closely related to regression which are not covered here:

• Different types of Anova
  • Two way Anova,
  • Multivariate Anova,
  • Ancova,
• Model diagnosis
  • Lack of fit
  • Order (Where the order of data matters)
• Bias variance trade off
• Confidence Interval
• Prediction Interval
• Higher order Interactions
• Degree of freedoms
• Dealing with troublesome features
  • uncorrelated
  • multi correlated
  • High dimension
  • Categorical Features
• Relation to time series
• Linear mixed models
• Bayesian linear model

References

PennState - STAT 501; Regression methods

Towards Data Science - Linear Regression

Stanford OLS notes - might be gone in the future

Scribber - one way anova

Scribber - multiple linear regression

Medium - Derivative of log loss for logistic regression