Announcements

• Reminder: Masks are required!

• Homework 1: Due in one week (next Wednesday at 8pm)!

• Requiring submission of Python file in addition to iPython Notebook file (see
announcement on Ed Discussion for details)

• Quiz 1 will be posted on canvas tonight: Due in one week!

• Waitlist
• Admitted to capacity
• Only considering additional applications if students do not enroll or drop
Project: Goals
• Apply algorithms you learn in this class to a real-world dataset

• Must go beyond simply applying an existing machine learning

algorithm to an existing dataset
Project: Goals
• Data: Collect a new dataset, augment an existing one, or modify data
preprocessing to improve performance

• Algorithm: Modify an existing algorithm, by changing the neural

network architecture, etc. to improve performance

• Analysis: Analyze sensitivity to hyperparameters, out-of-distribution

inputs, etc.
Project: Grading
• You will be graded on your understanding of ML covered in this
class, and the quality and value of your novel contributions
• Applying an existing algorithm to a standard dataset is not enough

• We will share a link to past projects

• [Link] or [Link] can also be good starting points
Project: Logistics
• Teams of 3 students
• Find teammates on your own
• Email instructors by Friday, 9/28 and we will do our best to help

• Project milestones
• Milestone 1 (2 pages, due 10/12): Project proposal (with groups chosen)
• Milestone 2 (4 pages, due 11/9): Preliminary results
• Milestone 3 (6 pages, due 12/7): Final reports
Lecture 2: Linear Regression (Part 1)
CIS 4190/5190
Fall 2022
Recap: Types of Learning
• Supervised learning
• Input: Examples of inputs and outputs
• Output: Model that predicts unknown output given a new input

• Unsupervised learning
• Input: Examples of some data (no “outputs”)
• Output: Representation of structure in the data

• Reinforcement learning
• Input: Sequence of interactions with an environment
• Output: Policy that performs a desired task
Today
• Deep dive into linear regression
• Basic example of a supervised learning algorithm

• Captures many fundamental machine learning concepts

• Function approximation view of machine learning
• Bias-variance tradeoff
• Regularization
• Training/validation/test split
• Optimization and gradient descent
Agenda
• Function approximation view of machine learning
• Modern strategy for designing machine learning algorithms
• By example: Linear regression, a simple machine learning algorithm

• Bias-variance tradeoff
• Fundamental challenge in machine learning
• By example: Linear regression with feature maps
Machine Learning for Prediction
New input

Data 𝑍 Machine learning Model 𝑓

algorithm
Predicted output

Question: What model family (a.k.a. hypothesis class) to consider?

Linear Functions
• Consider the space of linear functions 𝑓! 𝑥 defined by
𝑥#
𝑓! 𝑥 = 𝛽 " 𝑥 = 𝛽# ⋯ 𝛽$ ⋮ = 𝛽# 𝑥# + ⋯ + 𝛽$ 𝑥$
𝑥$
Linear Functions
• Consider the space of linear functions 𝑓! 𝑥 defined by
𝑥#
𝑓! 𝑥 = 𝛽 " 𝑥 = 𝛽# ⋯ 𝛽$ ⋮ = 𝛽# 𝑥# + ⋯ + 𝛽$ 𝑥$
𝑥$

• 𝑥 ∈ ℝ$ is called an input (a.k.a. features or covariates)

• 𝛽 ∈ ℝ$ is called the parameters (a.k.a. parameter vector)
• 𝑦 = 𝑓! 𝑥 is called the label (a.k.a. output or response)
Linear Regression Problem
• Input: Dataset 𝑍 = 𝑥# , 𝑦# , … , 𝑥% , 𝑦% , where 𝑥& ∈ ℝ$ and 𝑦& ∈ ℝ
• Output: A linear function 𝑓! 𝑥 = 𝛽 " 𝑥 such that 𝑦& ≈ 𝛽 " 𝑥&

• Typical notation
• Use 𝑖 to index examples 𝑥! , 𝑦! in data 𝑍
• Use 𝑗 to index components 𝑥" of 𝑥 ∈ ℝ#
• 𝑥!" is component 𝑗 of input example 𝑖

• Goal: Estimate 𝛽 ∈ ℝ$
Linear Regression Problem
• Input: Data 𝑍 = 𝑥# , 𝑦# , … , 𝑥% , 𝑦% , where 𝑥& ∈ ℝ$ and 𝑦& ∈ ℝ
• Output: A linear function 𝑓! 𝑥 = 𝛽 " 𝑥 such that 𝑦& ≈ 𝛽 " 𝑥&
NSIDC Index of Arctic Sea Ice in September
9.0
8.0
7.0 𝑓! 𝑥

Arctic Sea Ice Extent

(millions of sq km)
6.0
5.0
4.0
3.0
𝑦& is the sea ice extent
2.0
1.0 𝑥& ∈ ℝ# is the year
0.0
1975 1985 1995 2005 2015 2025
Photo by NASA Goddard
Year
14
Image: [Link]
Data from [Link]
Linear Regression Problem
What does this mean?
• Input: Data 𝑍 = 𝑥# , 𝑦# , … , 𝑥% , 𝑦% , where 𝑥& ∈ ℝ$ and 𝑦& ∈ ℝ
• Output: A linear function 𝑓! 𝑥 = 𝛽 " 𝑥 such that 𝑦& ≈ 𝛽 " 𝑥&
NSIDC Index of Arctic Sea Ice in September
9.0
8.0
7.0 𝑓! 𝑥

Arctic Sea Ice Extent

(millions of sq km)
6.0
5.0
4.0
3.0
𝑦& is the sea ice extent
2.0
1.0 𝑥& ∈ ℝ# is the year
0.0
1975 1985 1995 2005 2015 2025
Photo by NASA Goddard
Year
15
Image: [Link]
Data from [Link]
Choice of Loss Function
• 𝑦& ≈ 𝛽 " 𝑥& if 𝑦& − 𝛽 " 𝑥& ' small 𝑦 𝑓! 𝑥 = 𝛽 " 𝑥
• Mean squared error (MSE):
%
1
𝐿 𝛽; 𝑍 = 4 𝑦& − 𝛽 " 𝑥& '
𝑛
&(#

𝑥
• Computationally convenient and
works well in practice
𝜖$ + 𝜖$ + 𝜖$ + 𝜖$ + 𝜖$
𝐿 𝛽; 𝑍 =
𝑛
Linear Regression Problem
• Input: Data 𝑍 = 𝑥# , 𝑦# , … , 𝑥% , 𝑦% , where 𝑥& ∈ ℝ$ and 𝑦& ∈ ℝ
• Output: A linear function 𝑓! 𝑥 = 𝛽 " 𝑥 such that 𝑦& ≈ 𝛽 " 𝑥&
Linear Regression Problem
• Input: Data 𝑍 = 𝑥# , 𝑦# , … , 𝑥% , 𝑦% , where 𝑥& ∈ ℝ$ and 𝑦& ∈ ℝ
• Output: A linear function 𝑓! 𝑥 = 𝛽 " 𝑥 that minimizes the MSE:
%
1
𝐿 𝛽; 𝑍 = 4 𝑦& − 𝛽 " 𝑥& '
𝑛
&(#
Linear Regression Algorithm
• Input: Dataset 𝑍 = 𝑥# , 𝑦# , … , 𝑥% , 𝑦%
• Compute

𝛽5 𝑍 = arg min 𝐿 𝛽; 𝑍
!∈ℝ!
# %
5
𝛽 𝑍 = arg min % ∑&(# 𝑦& − 𝛽 " 𝑥& '
!∈ℝ!

• Output: 𝑓!+ , 𝑥 = 𝛽5 𝑍 " 𝑥

• Discuss algorithm for computing the minimal 𝛽 later
Intuition on Minimizing MSE Loss
• Consider 𝑥 ∈ ℝ and 𝛽 ∈ ℝ

3 5
4
2 3
𝑦 𝐿(𝛽; 𝑍) 2
1
1
0 0
0 1 2 3 0 0.5 1 1.5 2
𝛽=1 𝑥 𝛽
Intuition on Minimizing MSE Loss
• Consider 𝑥 ∈ ℝ and 𝛽 ∈ ℝ

3 5
4
2 3
𝑦 𝐿(𝛽; 𝑍) 2
1
1
0 0
0 1 2 3 0 0.5 1 1.5 2
𝛽 = 0.5 𝑥 𝛽
Intuition on Minimizing MSE Loss
• Consider 𝑥 ∈ ℝ and 𝛽 ∈ ℝ

3 5
4
2 3
𝑦 𝐿(𝛽; 𝑍) 2
1
1
0 0
0 1 2 3 0 0.5 1 1.5 2
𝛽 = 0.25 𝑥 𝛽
Intuition on Minimizing MSE Loss
• Consider 𝑥 ∈ ℝ and 𝛽 ∈ ℝ

3 5
4
2 3
𝑦 𝐿(𝛽; 𝑍) 2
1
1
0 0
0 1 2 3 0 0.5 1 1.5 2
𝑥 𝛽
Intuition on Minimizing MSE Loss
• Convex (“bowl shaped”) in general
𝛽'

𝐿 𝛽; 𝑍

𝛽#

Slide by Andrew Ng
“Good” Mean Squared Error?
• Need to compare to baseline!
• Constant prediction
• Handcrafted model
•…

• Later: Training vs. test MSE

Alternative Loss Functions
#
• Mean absolute error: ∑%&(# |𝑦@& − 𝑦& |
%

# % -" /."
.
• Mean relative error: ∑&(#
% |." |

𝟐 234
• 𝑹 score: 1−
567869:;
• “Coefficient of determination”
• Higher is better, 𝑅$ = 1 is perfect
Alternative Loss Functions
# % (.= " />
? )(." /?)
• Pearson correlation: ∑&(#
% >A
A
• Usually estimated from some sampled measurements of those variables, and
denoted as 𝑅 (related to 𝑅$ on the last slide!)

• Rank-order correlation:
• First rank the measurements of 𝑦3𝒊 and 𝑦 separately, then replace each value
in 𝑦 by its rank, and ditto for 𝑦3
• Then measure the linear correlation between those ranks
Taking a Step Up…
Function Approximation View of ML

Data 𝑍 Machine learning Model 𝑓

algorithm

ML algorithm outputs a model 𝑓 that best “approximates” the given data 𝑍

Function Approximation View of ML
• Framework for designing machine learning algorithms

• Two design decisions

• What is the family of candidate models 𝑓? (E.g., linear functions)
• How to define “approximating”? (E.g., MSE loss)
Aside: “True Function”
• Input: Dataset 𝑍
• Presume there is an unknown function 𝑓 ∗ that generates 𝑍

• Goal: Find an approximation 𝑓! ≈ 𝑓 ∗ in our model family 𝑓! ∈ 𝐹

• Typically, 𝑓 ∗ not in our model family 𝐹

𝑓! 𝐹
𝑓∗
Function Approximation View of ML
• Framework for designing machine learning algorithms

• Two design decisions

• What is the family of candidate models 𝑓? (E.g., linear functions)
• How to define “approximating”? (E.g., MSE loss)

• How do we specialize to linear regression?

Function Approximation View of ML

Data 𝑍 Machine learning Model 𝑓

algorithm
Loss Minimization

Data 𝑍 Machine learning Model 𝑓

algorithm
Loss Minimization

Data 𝑍 Machine learning Model 𝑓'

algorithm

Parametric model family (i.e., 𝐹 = 𝑓' 𝛽 ∈ ℝ# )

Loss Minimization

Data 𝑍 𝛽5 𝑍 = arg min' 𝐿(𝛽; 𝑍) Model 𝑓'( )

ML algorithm minimizes loss of parameters 𝛽 over data 𝑍

Loss Minimization for Supervised Learning

Data 𝑍 𝛽5 𝑍 = arg min' 𝐿(𝛽; 𝑍) Model 𝑓'( )

Loss Minimization for Supervised Learning

,
Data 𝑍 = 𝑥! , 𝑦! !*+ 𝛽5 𝑍 = arg min' 𝐿(𝛽; 𝑍) Model 𝑓'( )
𝐿 encodes 𝑦! ≈ 𝑓' 𝑥!

Goal is for function to approximate label 𝑦 given input 𝑥

Loss Minimization for Regression

,
Data 𝑍 = 𝑥! , 𝑦! !*+ 𝛽5 𝑍 = arg min' 𝐿(𝛽; 𝑍) Model 𝑓'( )
𝐿 encodes 𝑦! ≈ 𝑓' 𝑥!

Label is a real number 𝑦! ∈ ℝ

Linear Regression

,
Data 𝑍 = 𝑥! , 𝑦! !*+ 𝛽5 𝑍 = arg min' 𝐿(𝛽; 𝑍) Model 𝑓'( )
𝐿 encodes 𝑦! ≈ 𝑓' 𝑥!

MSE loss Model is a linear function 𝑓' 𝑥 = 𝛽-𝑥

Linear Regression
General strategy Linear regression strategy
• Model family 𝐹 = 𝑓! • Linear functions 𝐹 = 𝑓! 𝑥 = 𝛽 " 𝑥
!
#
• Loss function 𝐿 𝛽; 𝑍 • MSE 𝐿 𝛽; 𝑍 = ∑%&(# 𝑦& − 𝛽 " 𝑥& '
%

Linear regression algorithm

𝛽5 𝑍 = arg min 𝐿 𝛽; 𝑍
!
Agenda
• Function approximation view of machine learning
• Modern strategy for designing machine learning algorithms
• By example: Linear regression, a simple machine learning algorithm

• Bias-variance tradeoff
• Fundamental challenge in machine learning
• By example: Linear regression with feature maps
Example: Quadratic Function

𝑦
𝑓! 𝑥 = 𝑥/2

𝑥
Example: Quadratic Function

𝑓! 𝑥 = 𝑥
𝑦

Can we get a better fit?

Feature Maps
General strategy Linear regression with feature map
• Model family 𝐹 = 𝑓! • Linear functions over a given feature
!
map 𝜙: 𝑋 → ℝ$
• Loss function 𝐿 𝛽; 𝑍
𝐹 = 𝑓! 𝑥 = 𝛽 " 𝜙 𝑥

# '
• MSE 𝐿 𝛽; 𝑍 = ∑%&(# "
𝑦& − 𝛽 𝜙 𝑥&
%
Quadratic Feature Map
• Consider the feature map 𝜙: ℝ → ℝ' given by
𝑥
𝜙 𝑥 = '
𝑥

• Then, the model family is

𝑓! 𝑥 = 𝛽# 𝑥 + 𝛽' 𝑥 '
Quadratic Feature Map

𝑓! 𝑥 = 0𝑥 + 1𝑥 '
𝑦

𝑥
0
In our family for 𝛽 = !
1
Feature Maps
• Powerful strategy for encoding prior knowledge

• Terminology
• 𝑥 is the input and 𝜙 𝑥 are the features
• Often used interchangeably
Examples of Feature Maps
• Polynomial features
• 𝜙 𝑥 = 𝛽+ + 𝛽$𝑥+ + 𝛽.𝑥$ + 𝛽/𝑥+$ + 𝛽0𝑥+𝑥$ + 𝛽1𝑥$$ + ⋯
• Quadratic features are very common; capture “feature interactions”
• Can use other nonlinearities (exponential, logarithm, square root, etc.)

• Intercept term
• 𝜙 𝑥 = 1 𝑥+ … 𝑥# -
• Almost always used; captures constant effect

• Encoding non-real inputs

• E.g., 𝑥 = “the food was good” and 𝑦 = 4 stars
• 𝜙 𝑥 = 1 “good” ∈ 𝑥 1 “bad” ∈ 𝑥 … -
Algorithm
• Reduces to linear regression

• Step 1: Compute 𝜙& = 𝜙 𝑥& for each 𝑥& in 𝑍

• Step 2: Run linear regression with 𝑍 C = 𝜙# , 𝑦# , … , 𝜙% , 𝑦%

Question
• Why not throw in lots of features?
• 𝜙 𝑥 = 𝛽+ + 𝛽$𝑥+ + 𝛽.𝑥$ + 𝛽/𝑥+$ + 𝛽0𝑥+𝑥$ + 𝛽1𝑥$$ + ⋯
• Can fit any 𝑛 points using a polynomial of degree 𝑛
𝑦
𝑓! 𝑥

𝑥
Prediction
• Issue: The goal in machine learning is prediction
• Given a new input 𝑥, predict the label 𝑦3 = 𝑓' 𝑥

𝑦
𝑓! 𝑥

𝑥
The errors on new inputs is very large!
Prediction
• Issue: The goal in machine learning is prediction
• Given a new input 𝑥, predict the label 𝑦3 = 𝑓' 𝑥

𝑓! 𝑥

𝑥
Vanilla linear regression actually works better!
Training vs. Test Data
• Training data: Examples 𝑍 = 𝑥, 𝑦 used to fit our model

• Test data: New inputs 𝑥 whose labels 𝑦 we want to predict

Overfitting vs. Underfitting
• Overfitting • Underfitting
• Fit the training data 𝑍 well • Fit the training data 𝑍 poorly
• Fit new test data 𝑥, 𝑦 poorly • (Necessarily fit new test data
𝑥, 𝑦 poorly)
𝑦 𝑦
𝑓! 𝑥

𝑓! 𝑥

𝑥 𝑥
Aside: Why Does Overfitting Happen?
• Overfitting typically due to fitting noise in the data

• Noise in labels 𝒚&

• True data generating process is more complex than we can capture
• May depend on unobserved features

• Noise in features 𝒙&

• Measurement error in the feature values
• Errors due to preprocessing
• Some features might be irrelevant to the decision function

56
Training/Test Split
• Issue: How to detect overfitting vs. underfitting?
• Solution: Use held-out test data to estimate loss on new data
• Typically, randomly shuffle data first

Given data 𝑍

Training data 𝑍#$%&' Test data 𝑍#()#

Training/Test Split Algorithm
• Step 1: Split 𝑍 into 𝑍D7689 and 𝑍D;ED

Training data 𝑍#$%&' Test data 𝑍#()#

• Step 2: Run linear regression with 𝑍D7689 to obtain 𝛽5 𝑍D7689

• Step 3: Evaluate
• Training loss: 𝐿23456 = 𝐿 𝛽5 𝑍23456 ; 𝑍23456
• Test (or generalization) loss: 𝐿2782 = 𝐿 𝛽5 𝑍23456 ; 𝑍2782
Training/Test Split Algorithm
• Overfitting • Underfitting
• Fit the training data 𝑍 well • Fit the training data 𝑍 well
• Fit new test data 𝑥, 𝑦 poorly • (Necessarily fit new test data
𝑥, 𝑦 poorly)
𝑦 𝑦
𝑓! 𝑥

𝑓! 𝑥

𝑥 𝑥
Training/Test Split Algorithm
• Overfitting • Underfitting
• 𝐿23456 is small • Fit the training data 𝑍 well
• 𝐿2782 is large • (Necessarily fit new test data
𝑥, 𝑦 poorly)
𝑦 𝑦
𝑓! 𝑥

𝑓! 𝑥

𝑥 𝑥
Training/Test Split Algorithm
• Overfitting • Underfitting
• 𝐿23456 is small • 𝐿23456 is large
• 𝐿2782 is large • 𝐿2782 is large

𝑦 𝑦
𝑓! 𝑥

𝑓! 𝑥

𝑥 𝑥
Aside: IID Assumption
• Underlying IID assumption
• Future data are drawn IID from same data distribution 𝑃 𝑥, 𝑦 as 𝑍2782
• IID = independent and identically distributed
• This is a strong (but common) assumption!

• Time series data

• Particularly important failure case since data distribution may shift over time
• Solution: Split along time (e.g., data before 9/1/20 vs. data after 9/1/20)
How to Fix Underfitting/Overfitting?
• Choose the right model family!
Role of Capacity
• Capacity of a model family captures “complexity” of data it can fit
• Higher capacity à more likely to overfit (model family has high variance)
• Lower capacity à more likely to underfit (model family has high bias)

• For linear regression, capacity corresponds to feature dimension 𝑑

• I.e., number of features in 𝜙 𝑥
Bias-Variance Tradeoff
• Overfitting (high variance) • Underfitting (high bias)
• High capacity model capable of • Low capacity model that can only
fitting complex data fit simple data
• Insufficient data to constrain it • Sufficient data but poor fit
𝑦 𝑦
𝑓! 𝑥

𝑓! 𝑥

𝑥 𝑥
Bias-Variance Tradeoff

Underfitting Ideal Overfitting

Loss

Test loss

Training loss
Capacity

Slide by Padhraic Smyth, UCIrvine

Bias-Variance Tradeoff
• For linear regression, increasing feature dimension 𝑑…
• Tends to increase capacity
• Tends to decrease bias but increase variance

• Need to construct 𝜙 to balance tradeoff between bias and variance

• Rule of thumb: 𝑛 ≈ 𝑑 log 𝑑
• Large fraction of data science work is data cleaning + feature engineering
Bias-Variance Tradeoff
• Increasing number of examples 𝑛 in the data…
• Tends to increase bias and decrease variance

• General strategy
• High bias: Increase model capacity 𝑑
• High variance: Increase data size 𝑛 (i.e., gather more labeled data)
Housing Dataset

• Sales of residential property in Ames, Iowa from 2006 to 2010

• Examples: 1,022
• Features: 79 total (real-valued + categorical), some are missing!
• Label: Sales price
...
...
...
...
...
...
...
...
...
...

Data from: De Cock. Journal of Statistics Education 19(3), 2011

Housing Dataset

• [Link]()

...
Feature Correlation Matrix
Features Most Correlated with Label
Missing Values
Feature % Missing Values
PoolQC 99.5108
• Possible ways to handle missing values
MiscFeature 96.0861
• Numerical: Impute with mean
Alley 93.5421
• Categorical: Impute with mode
Fence 80.2348
FireplaceQu 47.6517
LotFrontage 18.5910
GarageCond 05.2838
GarageType 05.2838
GarageYrBlt 05.2838
GarageFinish 05.2838
GarageQual 05.2838
BsmtFinType1 02.5440
...
Other Preprocessing

• Categorical: Featurize using one-hot encoding

• Ordinal
• Convert to integer (e.g., low, medium, high à 1, 2, 3)
• Does not fully capture relationships (try different featurizations!)
Evaluation
• 438 test examples, preprocessed same as training data
• Sorted by prediction error