Linear Regression and Gradient Descent for Optimization

• Fardina Fathmiul Alam

Modular Approach to ML Algorithm Design

So far, we have talked about procedures for learning.

• E.g. KNN, Decision trees.

Modular Approach to ML Algorithm Design

For the remainder of this course, we will take a more modular approach:

• Choose a model describing the relationships between variables of interest
• Define a loss function quantifying how bad the fit to the data is.
• Fit the model that minimizes the loss function and satisfy the constraint/penalty imposed by the regularizer, possibly using an optimization algorithm.

Mixing and matching these modular components gives us a lot of new ML methods.

Regression vs. Classification

What we've been doing so far has been classification--predicting the category data will fall into. The other branch of supervised learning is regression.

• Classification predicts which discrete, mutually exclusive category a datapoint belongs to.
• Regression takes in input data and predicts a real valued (continuous) feature.

​

How Does this Differ From Classification?

If you are trying to decide if something is a cat or a dog, you can't be half right; it's either a cat or a dog

If you are trying to predict how much a house will sell for, you can be more or less correct.

Identify: Classification or Regression?

Problem Setup: Let’s Say

We’ve collected Weight and Height measurements from 5 people, and we want to use Weight to predict Height, which is continuous value.

We want to know height (output) of a new person X based on his/her weight (input)

If we want to find a simple and effective model for this situation, we'll start by using a simple regression model.

Problem Setup:

We’ve collected Weight and Height measurements from 5 people, and we want to use Weight to predict Height, which is continuous value.

Regression is a statistical method used to understand the relationship between a dependent variable and one or more independent variables.

​

Goal: Create a model that can predict the dependent variable based on the independent variable(s).

In this scenario, since we only have one independent variable (Weight) and one dependent variable (Height), we'll use simple linear regression.

Problem Setup:

We want to use Weight to predict Height, which is

continuous.

Plotting data

Training data

Linear Equation with 1 Feature

We want to use Weight to predict Height (continuous).

Any linear relationship between two variables can be represented as a straight line.

Y= ꞵ₀ + ꞵ₁. X

​

​

Here,

Model: y is a linear function of x:

Y= ꞵ0 + ꞵ1. X; where:

​

“Y” is target or prediction → Height

“X” is feature → Weight

“ꞵ₀,ꞵ₁” → Model’s parameter or coefficient

​

​

(Independent Variable)

(Dependent

Variable)

We usually like to add a line to the data so we can see what the trend is

What if there are multiple features?

Linear Equation with Multiple P Features

Any general linear equation with multiple features can be written as

• x_i are features
• 𝛽_i are model parameters or coefficients
• Y is target variable

Terminology:

Slope and Intercept

“m”

“c”

Slope (β₁): Also known as the gradient, it shows how steep the line is, indicating how much the dependent variable changes when the independent variable changes by one unit.

Intercept (β₀): It's where the line intersects the y-axis, representing the starting value of the dependent variable when the independent variable is zero.

Back to: Goal of Regression

Y= ꞵ₀ + ꞵ₁. X

​

​

Find a function that best represents the relationship between the input variables (independent variables) and the output variable (dependent variable), which is continuous.

For a new data X, we want to predict height, based on the weight

β₀ represents the y-intercept of the line

β₁ represents the slope of the line

Regression Line or Line of Best Fit

The best fit line, often referred to as the "line of best fit" or "regression line," is a straight line that best represents the relationship between two variables in a set of data.

But how do we know which one is the best line?

How to find the optimal line to fit our data?

A reasonable criterion for a line to be the “best” is for it to have the smallest possible overall error among all straight lines.

But how do we know which one is the best line? cont.

Why that particular line?

We aim to choose a line that

• Best Fit: The chosen regression line accurately fits the data.
• Minimizes Errors: Aims to reduce differences between predicted and actual values.
• Captures Relationship: Shows the relationship between variables for accurate predictions.

So, we need a process of determining the best-fitting line → Linear Regression Method

REMEMBER: “The best fit line will have the least error”.

Linear Regression

Linear Regression is a statistical method used to find the relationship between variables by finding the best fit line.

​

One of the most important algorithms in machine learning.

• Measure the relationship between one or more independent variables vs one dependent variable.
• Independent variables → predictors (inputs)
• Dependent variables → outcome of interest
• Example: Years of Experience vs Salary, Area vs House Price.

Goal of the linear regression algorithm

Find the best values for β₀ and β₁ to find the best fit line*.

​

​

​

*The best fit line is a line that has the least error which means the error between predicted values and actual values should be minimum.

Find the best values for β0 and β1 to find the best fit line.

​

​

To do that, we use the method of 'Least Squares' or minimize the cost function, typically the Mean Squared Error (MSE), to fit a line to the data.

Terminologies: Residual or Error

Error/Residuals: the difference between the actual value of y and the predicted value of y.

Residual Error, ε = Y(actual) - Y(predicted)

​

A well-fitting model should have small residuals on average.

Square Error: RSS or SSE

The residual sum of squares (RSS), also known as the sum of squared residuals (SSR) or the sum of squared errors (SSE) or squared error (says how bad the fit is) [ref: Wiki]

Now, we measures the loss function which the squared distances (residuals) between the observed data points and the predicted values, and then sums these squares to evaluate how well the model fits the data.

Square Error: RSS or SSE

Terminologies: Cost Function

Cost Function: the least Sum of Squares of Errors is used as the cost function for Linear Regression.

Here, loss function averaged over all training example.

Mean Squared Error

Cost Function

This equation is same as before, just using the different terms or synonyms. And The 1/2 factor is multiplied just to make the calculations convenient.

Back to Terminologies

Error/Residuals: the difference between the actual value of y and the predicted value of y.

Cost Function: the least Sum of Squares of Errors is used as the cost function for Linear Regression.

​

For all possible lines, we calculate the sum of squares of errors. The line which has the least sum of squares of errors is the best fit line.

REMEMBER: Data points far from the regression line lead to higher errors (residuals), resulting in a higher cost function, while closer points yield lower errors and a reduced cost function.

Summary so far

the cost function need to be minimized to find that value of β0 and β1, to find that best fit of the predicted line.

This become a ML Optimization problem now!

​

Minimize (Cost Function)!

In the context of linear regression, optimization is employed to find the optimal coefficients (slopes and intercept) for the linear equation that best fits the data.

There are some Helping Slides!!

How Linear Regression aim to find the best-fit line among all possible lines

​

Check by yourself if you want to!

In the context of linear regression, optimization is employed to find the optimal coefficients (slopes and intercept) for the linear equation that best fits the data.

We Now Have a Function to Minimize

We want to find the coefficients (slope β1, constant/Interceptβ0) of the line:

​

​

That minimize cost:

+

Target: Update coefficient values iteratively to minimize the cost.

This now lead to a population Optimization Algorithm

Known as “Gradient Descent”

• An iterative optimization algorithm to find the minimum of a function.

*** The gradient is a vector that indicates the direction and steepness of the slope of a function at a specific point (check helping slide)

Gradient Descent

Process:

• Initialization: Start with initial values for β0 and β1.
• Cost Calculation: Calculate the cost function (RSS).
• Parameters Adjustment: Adjust (increases or decreases t) parameters (β0, β1) on the gradient o find the next cost value.
• Iterations: Repeat process until the minimum cost is achieved.

In linear regression, optimize the Residual sum of squares cost function. How?

Gradient descent iteratively finds optimal parameter values by minimizing a cost function.

Importance of the “Derivative” in Minimization

The derivative, a key concept from calculus indicates the slope of the function at a given point.

• Knowing the slope helps determine the direction (sign) to move in order to adjust the coefficient values so that we achieve a lower cost in the next iteration

extremely important technique to minimise the cost function to get the minimum point.

Gradient Descent Algorithm

Learning Step / Learning Rate (alpha)

Learning Rate (α): Determines the size of steps taken in Gradient Descent.

Large Learning Rate: Covers more ground per step but risks overshooting the minimum.

Small Learning Rate: Ensures precise movement but may result in slow convergence due to frequent gradient calculations.

Common Learning Rates: 0.001, 0.003, 0.01, 0.03, 0.1, 0.3.

Line of Best Fit

Once we're done, we have a nice line of best fit.

Assumptions (L.I.N.E)

• Relationship must be linear
• Residuals must be independent
• Residuals must be normally distributed
• Equal variance of residuals

Linearity:

The relationship between the independent and dependent variables must be linear.

Independence of Residuals

Residuals must be independent of one another.

​

• There should be no autocorrelation in residuals for a linear regression model to be valid.

​

“Assumes that the residuals/ errors from one data point to another are independent.”

What is Autocorrelation

Autocorrelation occurs when residuals are correlated with each other.

​

E.g: In predicting students' exam scores based on study hours, if errors in predicting one student's score are consistently related to errors in predicting another student's score, it implies autocorrelation. This violates the assumption of independent errors in linear regression.

• Autocorrelation usually occurs if there is a dependency between residual errors
• Problem: any correlation in the error term will drastically reduce the accuracy of the model.

Residuals Must be Normally Distributed

If they are not, you're likely to have outliers

Homoscedasticity

The data must be homoscedastic, meaning the variance in the outliers must be constant.

• Residuals should have constant variance across all levels of the independent variable.
• ​

How Do We Know if Our Regression is Any Good?

Evaluating Linear Regression Performance

After building a linear regression model, it is important to evaluate its performance. The most commonly used metrics for evaluating the performance of linear regression models are R-Squared, Root Mean Squared Error (RMSE).

R²

R-squared is a statistical method that determines the goodness of fit.

It measures the strength of the relationship between the dependent and independent variables.

​

It measures the proportion of variance in the dependent variable explained by the independent variables in a regression model.

• R² shows how well the independent variables explain the variation in the dependent variable (the outcome you want to predict).

The coefficient of determination

R²

It typically ranges between 0 and 1, and shows how well our line fits the data. It technically can be negative if your fit is worse than a horizontal line.

Interpretation:

R² = 0: The model doesn’t explain any variation.

R² = 1: The model perfectly explains all variation.

Higher R²: Means the model does a good job of predicting the dependent variable.

The coefficient of determination

R²

calculated using the formula:

​

​

​

SS_res= is the sum of the squared residuals or errors (the difference between the actual Y values and the predicted Y values.

SS_tot=is the total sum of squares, which measures the total variance of the dependent variable around its mean.

• For each data point, calculate the difference between the observed value (Y) and the mean.

Negative R²

Root Mean Squared Error

Our actual loss function.

• Good at comparing two models for the same data BUT
• Is in the same units as whatever we're measuring, so is useless on its own

Types of Regression

Polynomial Regression

• Prone to overfitting
• Generally use it only for small degree polynomials

Polynomial regression is a type of regression analysis used when the relationship between the independent variable (x) and dependent variable (y) isn't linear. It involves fitting a polynomial equation to the data, allowing for curves instead of straight lines.

Random Forest Regression

You can modify a random forest to do regression.

In general, people often use this one compare to all the other types.

Regularization Technique in Machine Learning

Regularization is a technique used in machine learning and statistical modeling to prevent overfitting and improve the generalization performance of models.

Regularization adds a penalty term to the model's objective function, which penalizes complex models and encourages simpler ones.

The goal of regularization is to find a balance between fitting the training data well and avoiding overly complex models that may not generalize well to new, unseen data.

Other Types of Regression:

• Ridge Regression: A specific type of regression that does well in situations with multicollinearity, where two independent variables are correlated.
• Adds an L1 regularization penalty to the east squares objective function.
• The L1 penalty encourages sparsity in the solution by penalizing the sum of the absolute values of the coefficients.
• Lasso Regression: A type of regression that is useful when there are large numbers of potentially irrelevant features.
• Adds an L2 regularization penalty to the objective function; penalizes the sum of the squared coefficients, effectively shrinking them towards zero. (prevents the weights from getting too large and hence avoiding them to overfit)
• ElasticNet Regression: A type of regression that combines the loss functions of ridge and lasso regression to get the advantages of both