Linear Regression

(Reading: Ch 13)

(Slides adapted from Sandrine Dudoit and Joey Gonzalez)

UC Berkeley Data 100 Summer 2019

Sam Lau

Learning goals:

• Reframe loss minimization framework for modeling.
• Introduce multivariable linear models within the loss minimization framework.

Announcements

• HW4 due Tuesday
• HW5 out Tuesday, due Friday
• Leo was out sick! Hopefully back today.
• Today’s lecture might get split into two
• Ask lots of questions if we’re going too fast

Last Time

• Draw conclusions about population using a sample through statistical estimation.
• Make estimations by picking the estimator that minimizes empirical risk / loss.
• Today:
• Connect estimation with prediction and modeling.
• First foray into machine learning with linear models.

Modeling

Making Predictions

• Loss minimization framework useful for predictions too!
• Suppose we have a dataset of cars and we’d like to predict fuel efficiency (miles per gallon, or mpg):

Models

• To make a prediction, we choose a model.
• Takes input data and outputs a prediction.
• Constant model:

• Simple linear model:

Two model weights

The Constant Model

• Start simple: if constant model, how do we pick θ?

• Intuition: pick θ to be close to most of the values in data

Model Loss

• Use x_i to denote what we use to make predictions
• Use y_i to denote what we’re trying to predict
• But both x and y come from a single sample
• Idea: Pick the θ that minimizes the average loss between y in our sample and model predictions.

Constant Model Loss

• Remember this expression from last lecture?
• θ = sample mean is the best model parameter.
• So, for car MPGs, we set θ = mean(mpg)

Modeling is Estimation in New Clothes

• Estimation: making best guess at population parameter
• Modeling: making predictions for population values
• Two sides of the same coin! Why?
• Modeling assumes pop values generated by parameters:

• RTA: assume that data from population generated by taking a constant θ^* and adding noise ϵ.
• Estimation = Finding θ̂, our best estimate for θ^*
• Modeling = Using θ̂ to make predictions

The Modeling Pipeline

We choose what goes in the blue boxes!

Fit a model by finding weights that minimize loss.

Minimizing sample loss approximates minimizing population loss.

The Modeling Recipe

• Pick a model, pick a loss function, fit the model to sample.
• Preview of model and loss function combos:

Linear Models

Using Our Data

• If we’re trying to predict MPG, we can do better than a constant model by incorporating more information.
• E.g. higher horsepowers have lower MPGs:

Simple Linear Model

• We want our predictions to depend on the input data x.
• Simple linear model:

• As usual, we can minimize the loss. This time, we have two parameters.

Simple Linear Model

• This ends up being a lot of algebra, so we’ll skip to the answer.

Skipping Ahead

• Data 8 textbook has example slope/intercept calculations.
• Takeaway: Can derive these formulas by minimizing loss.
• You should know how to take the derivative but won’t need to solve it.

Multivariable Linear Model

• Simple linear model uses one variable to predict:

• Time to graduate from Data 8!
• Multivariable linear model uses ≥1 variable:

• x is a vector containing one row of input data.
• IOW: Predict by combining multiple features together.

Intuition

• Using horsepower and model year to predict mpg
• Expect θ₁ to be negative and θ₂ to be positive. Why?

Using Matrix Multiplication

• This means our model is:

• Many terms to write! We’ll use a trick: add a column of 1s to the table:

Bolded letters means vector or matrix.

More Notation!

Your turn: Write the matrix expression that computes a vector with a fitted linear model’s predictions for all sample points.

Your Turn

Write the matrix expression that computes a vector with a fitted linear model’s predictions for all sample points.

Your Turn

Write the matrix expression that computes the average MSE loss for all data points (this is a scalar!).

Your Turn

Write the matrix expression that computes the average MSE loss for all data points (this is a scalar!).

Using matrix notation takes a lot of practice to get used to, but the results are worth it. Always check your dimensions!

Fitting a Linear Model

• How do we pick θ to minimize loss?

• Want to take partial derivatives for θ₀, θ₁, ...
• Instead, we’ll take the gradient and set it equal to zero.
• This solves for all model weights at once!

The Normal Equation

• Saving the setup for the Gradient Descent lecture
• Again, you need to know how to take the gradient but not how to solve for θ.
• Skipping ahead to the answer:

• Expression above called normal equation
• Gives a closed-form recipe for fitting linear model

What are the matrix shapes in these expressions?

The Abnormal Equation

• In practice, it takes too long to compute this:

• Inverting an (n x n) matrix takes at least O(n²) time.
• State of the art: O(n^2.3)
• Takeaway: analytic solutions are elegant but are sometimes hard to find and slow.
• Next lecture: gradient descent

Demo: Predicting MPGs

Break!

Fill out Attendance:

http://bit.ly/at-d100

Feature Engineering

(moved to Wed lecture)

Linear Models Level Up

• Horsepower and mpg have a nonlinear relationship.
• Can still use linear regression to capture this!
• Feature engineering: creating new features from data to give model more complexity.

Adding Features

• For now, predict MPG from horsepower alone.
• Insight: Add a new column to X with horsepower².

• Now we fit a quadratic function!

• This is still linear in model weights θ, so we call it a linear model.

(Demo)

Polynomial Regression

• For polynomial features of degree n, usually add every possible combination of columns.
• 4 original columns, degree 2:

• Can end up being a lot of columns
• To cope, use kernel trick (covered in advanced courses)

Categorical Features

• Origin column is correlated with MPG. Can we use it?
• Idea: Encode categories as numbers in a smart way.
• Discuss: Why can’t we just encode “usa” as 0, “japan” as 1, “europe” as 2?

One-Hot Encoding

• One-hot encoding makes one new column for each unique category:

One-Hot Encoding

• What do you expect the largest weight to be?

• Can interpret weight as “contribution” of that category

One Hot Problem

• Problem: Adding a new column for each category makes columns of X linearly dependent! Why?
• One-hot columns always sum to 1:

• This makes normal equations unsolvable.

Not invertible ^

=

+

+

Weight Interpretation

• Invertibility isn’t a problem for gradient descent, but this still affects how we interpret the model weights.
• Linearly dependent columns can “swap” weights:
• Left: All categories matter. Right: No categories matter!

Drop it Like it’s Hot

• Simple fix: Drop the last one-hot column.
• In this case, the weight for USA can be interpreted as “change in MPG between USA and Japan”.

Features feat. More Features

• Feature engineering is often domain-specific:
• Standardizing: “How many SDs away from average?”
• Log transform: Used to fit exponential models.
• Absolute difference: “How different is the current temperature from 70°?”
• Binning data, then one-hot encoding: “Are we driving during morning rush hour? Evening rush hour?”
• Date-related features: year, month, weekday
• Image-related features: blurring, edge detection, etc.

Summary

• Modeling and estimation are closely related.
• We can view modeling as estimation of model parameters.
• Linear models can incorporate an arbitrary number of features to make a prediction.
• Feature engineering extends linear models to generate more complex models.