Machine Learning Lecture Notes (Undergrad)

Parush Arora

1 Fundamentals of Machine Learning

1.1 Conditional Expectation
Let’s assume we are interested in knowing about some variable, say wage. The first thing you can do is plot
the histogram/density.
Having knowledge about some other related variable helps us make inference about the population in a
much better way. The extra information coming from X is used to shrink the distribution of Y (reducing
uncertainty). See Figure 1.

Figure 1

Rather than considering the whole distribution, we focus on one point (expectation). Unconditional expecta-
tion E(Y ) does not take into account relation between Y and X but E(Y |X) does. Conditional expectation
use extra information to make better inference. See Figure 2.

Figure 2

1.2 Framework
We are interested in predicting Y given X1 , . . . , Xp . For example, we want to predict sales of a product,
given advertisement expenditure, past sales etc. Here, Y is output/response/dependent variable and X =
{X1 , . . . , Xp } are a set of input/predictor/independent variables. There is some true association between Y
and X which is unknown to us. We can represent the problem as

Y = f (X1 , . . . , Xp ) + ϵ
= f (X) + ϵ

1
Here f is some fixed and unknown function and ϵ is the error term where EY (ϵ) = 0 and EY (ϵf (X)) = 0. f
represents the systematic information that X provides about Y . ϵ contains information about Y which X
cannot provide (unobserved variables) Taking expectations

EY (Y ) = EY (f (X)) + EY (ϵ)
= f (X)

Why estimate f ? Either for the purpose of inference or prediction. This course will focus on the prediction

aspect.

Y = fˆ(X) + ν

where ν = ϵ + (f (X) − fˆ(X)), EY (fˆ(X)) = f (X) and EY (ϵ(f (X) − fˆ(X))) = 0. The term f (X) − fˆ(X)
represents the estimation error induced due to using sample instead of population.

1.3 Bias-Variance Trade off

The model accuracy can be estimated using mean square error (MSE) given as

MSE = E(Y − fˆ(X))2

Let’s assume we have a training data of size n as {(y1 , x1 ), . . . , (yn , xn )} where yi represents ith observation
for dependent variable and xi = {xi1 , . . . , xip }T represents ith observation for independent variable. The
data is called the training data because we will use them to train our method/model in estimating f as fˆ.
To test model accuracy, we can calculate MSE on a test data say {(yn+1 , xn+1 ), . . . , (ym , xm )}
m
1 X
MSE = (yj − fˆ(xj ))2
m j=n+1

2
Test data is previously unseen observation not used to train the method/model. MSE can be expanded as

MSE = EY (Y − fˆ(X))2
= EY (Y − f (X) + f (X) − fˆ(X))2
= EY (Y − f (X))2 + EY (f (X) − fˆ(X))2 + 2EY (Y − f (X))(f (X) − fˆ(X))
= EY (ϵ)2 + EY (f (X) − fˆ(X))2 + 2EY (ϵ(f (X) − fˆ(X)))
= EY (ϵ)2 + EY (f (X) − fˆ(X))2
| {z } | {z }
Irreducible Reducible

= V arY (ϵ) + EY (f (X))2 + EY (fˆ(X))2 − 2EY (f (X)fˆ(X))

= V arY (ϵ) + V arY (f (X)) + (EY (f (X)))2 + V arY (fˆ(X)) + (EY (fˆ(X)))2 − 2EY (f (X)fˆ(X))
= V arY (ϵ) + V arY (fˆ(X)) + (EY (fˆ(X)))2 + f (X)2 − 2f (X)EY (fˆ(X))
= V arY (ϵ) + V arY (fˆ(X)) + (f (X) − EY (fˆ(X)))2
| {z }
Bias

= V arY (ϵ) + V arY (fˆ(X)) + Bias2

The term V arY (ϵ) represents irreducible error which cannot be eliminated given X. The term V arY (fˆ(X))
represents how much fˆ(X) will change if we change the training data. The term f (X) − EY (fˆ(X)) is bias
which means if we take infinite samples and estimate infinite fˆ(X), how far is the mean of those infinite
fˆ(X) from f (X). The distance is called bias.
Generally, flexible models have low bias but high variance and inflexible models have high bias and low
variance. The concept of overfitting and underfitting are related to them.

Underfitting means model is too simple or inflexible and thus not able to fit the training data. This model
has low variance (V arY (fˆ(X))) but high bias. Overfitting means a model is too complicated and responds
to noise in the training data leading to low bias but high variance. It fits the training data extremely well
but poorly on the test data. A good model responds to the real patterns in the data and ignore noise which
occurs due to randomness in the training sample. Figure ?? captures the idea.

1.4 Other Distinctions

1.4.1 Supervised Vs Unsupervised Learning
Supervised learning is what is been covered so far. We have a response variable (Y ) associated with the
controls (X). It is supervised by the aim of predicting Y as precisely as possible. On the other hand,
unsupervised learning is when we only have X but no Y .

1.4.2 Regression Vs Classification Problems

Under supervised learning, if the response variable is continuous or quantitative, then the problem is referred
as regression problem. if the response variable is discrete or qualitative, then the problem is referred as
classification problem.

1.4.3 Parametric Vs Semi Parametric Methods

There are two ways to estimate f .

3
 1. Parametric Methods: Make an assumption about the functional form. Then estimate the parameters
in the form. For example, linear regression model takes the form
f (X) = β1 X1 + . . . + βp Xp
where β1 , . . . , βp are parameters which will be estimated.
2. Non Parametric Methods: No functional form is assumed. f (X) is estimated directly.
There is a trade off between interpretability and model accuracy. Parametric methods impose a functional
form making them inflexible which hurts the model accuracy. Though, because of the structure imposed, it
is easier to interpret the model. Whereas, non-parametric methods are flexible and can take any form but
lack interpretability.

2 Linear Regression
Under supervised learning when the dependent variable is quantitative/continuous. It captures the linear
association between the dependent variable and the controls. Considering one independent variable, the true
DGP is given as
Y = f (X) + ϵ
Linear regression imposes a linear functional form as follows
Y = α + βX + ϵ
The benefit of the assumption is that it allows for easier estimation and clear inference. The cost is that the
assumption can be wrong. By estimating α and β, we estimate the average relationship between Y and X,
i.e., when X changes, how on average Y would change. So the eventual aim is to estimate the conditional
expectation function (CEF) which is E(Y |X).

2.1 Estimation
Let’s assume we have data for wages and education as {(x1 , y1 ), . . . , (xn , yn )}. Each observation is indepen-
dent and identically distributed (i.i.d). We can write the model as
yi = α + βxi + ϵi ∀ i = 1, . . . , n.
We are interested in estimating α and β. We minimizes the following objective function to estimate our
parameters.
n
X
{α̂, β̂} = arg min (yi − α − βxi )2
α,β
i=1

The objective function is called Residual sum of squares (RSS) because it can be written as
n
X n
X
(yi − α − βxi )2 = ϵ2
i=1 i=1

Taking first order conditions, we can estimate α and β as

n
∂RSS X
= −2 (yi − α − βxi )
∂α i=1
n
∂RSS X
= −2 (yi − α − βxi )xi
∂β i=1
Equating the first order conditions to 0 and solving them
α̂ = ȳ − β̂ x̄
1
Pn
n i=1 (yi − ȳ)(xi − x̄)
β̂ = 1
Pn 2
n i=1 (xi − x̄)
Cov(xi , yi )
=
V ar(xi )
Thus, the estimated regression looks like
yi = α̂ + β̂xi + ϵ̂i ∀ i = 1, . . . , n.
where ϵ̂i is the residual term or unexplained part of yi .

4
 Figure 3

2.2 Multiple Linear Regression

Now we consider the vector form which is given as
 
α
 β1 

 
yi = 1 x1i ... xki  .  + ϵ
 .. 
βk
= x′i β + ϵi
Then we estimate the parameters by minimizing
n
X
β̂ = arg min (yi − x′i β)2
α,β
i=1

The first order conditions take the following form

n
∂RSS X
= −2 xi (yi − x′i β)
∂β i=1

Equating to 0 and solving for β

n
X n
X
β̂ = ( xi x′i )−1 ( xi yi )
i=1 i=1

where β̂ is a (k + 1) × 1 vector of estimated coefficients. A useful property is that E(β̂) = β making it

unbiased.
n
X Xn
E(β̂) = E(( xi x′i )−1 ( xi yi ))
i=1 i=1
n
X Xn
= E(( xi x′i )−1 ( xi (x′i β + ϵ)))
i=1 i=1
n
X Xn n
X n
X
= E(( xi x′i )−1 ( xi x′i )β + ( xi x′i )−1 ( xi ϵ))
i=1 i=1 i=1 i=1
Xn X n
= β+ ( xi x′i )−1 ( xi E(ϵ))
i=1 i=1
= β

2.3 How accurate are the coefficients?

We estimate standard errors to get a sense of how much the estimated value varies with change in sample.
Treating xi as given

5
 n
X Xn
V ar(β̂) = V ar(( xi x′i )−1 ( xi yi ))
i=1 i=1
n
X Xn
= V ar(( xi x′i )−1 ( xi (x′i β + ϵ)))
i=1 i=1
n
X Xn n
X n
X
= V ar(( xi x′i )−1 ( xi x′i )β + ( xi x′i )−1 ( xi ϵi ))
i=1 i=1 i=1 i=1
n
X Xn
= V ar(β + ( xi x′i )−1 ( xi ϵi ))
i=1 i=1
n
X n
X Xn
= ( xi x′i )−1 ( xi x′i V ar(ϵi ))( xi x′i )−1 )
i=1 i=1 i=1
n
X
= V ar(ϵi )( xi x′i )−1
i=1

Since we don’t know V ar(ϵi ), we replace it as

RSS/(n − k)
V ˆar(β̂) = Pn ′
i=1 xi xi
q
The standard errors is defined as SE(ˆ β̂) = V ˆar(β̂). Thus, we have E(β) and V ˆar(β̂) for the sampling
distribution of β. Using Central Limit Theorem, we make an assumption that the sampling distribution of β
converges to normal distribution in large samples. Under small samples, we assume the sampling distribution
of β takes the form of t distribution which has broader tails.

2.4 Hypothesis Testing - Inference

Hypothesis is a mathematical proposition. Null hypothesis (H0 ) is the proposition that we assume to be
true at the start of the analysis. Alternative hypothesis (HA ) are the potential proposition apart from H0 .
How to test hypothesis?

2.4.1 T-test
Let’s assume that for the linear regression we considered, we are interesting in testing the following hypothesis.
Null Hypothesis: H0 : βj = 0 (the predictor has no effect)
Alternative Hypothesis: H1 : βj ̸= 0 (the predictor is significant)

The test statistic is:

θ̂ − θ0
t =
SE(θ̂)
β̂j
=
SE(β̂j )

where, β̂j is the estimated coefficient and SE(β̂j ) is the standard error of β̂j . t statistic captures the
distance between the estimated coefficient and Null hypothesis in terms of standard error. Greater the
distance, more is the evidence to reject Null.

• If |tj | is large, we reject H0 , meaning the predictor is statistically significant.

• If |tj | is small, we fail to reject H0 , meaning the predictor is not statistically significant.

6
2.4.2 Confidence Interval
A (1 − α) × 100% confidence interval for βj is:

β̂j ± tα/2,n−2 · SE(β̂j )

where:
• tα/2,n−2 is the critical value from the t-distribution.

The confidence interval comments on the probability of interval containing β̂j . If the interval contains zero,
we do not have enough evidence to conclude that βj is significantly different from zero.

2.4.3 p-Value
The p-value tells us the probability of obtaining a test statistic at least as extreme as the observed one
under H0 . It is computed as:
p = 2 · P (T > |tobs |)
for two sided test where T ∼ tn−2 .
• If p ≤ α, reject H0 (evidence that Xj is a significant predictor).
• If p > α, fail to reject H0 (insufficient evidence to claim significance).

2.5 Model Performance

2.5.1 Coefficient of Determination (R2 )
The coefficient of determination, R2 , measures how well the regression model explains the variation in the
dependent variable.
Explained Variation RSS
R2 = =1−
Total Variation TSS
where:
TSS = (yi − ȳ)2 is the total sum of squares.
P

RSS = (yi − ŷi )2 is the residual sum of squares (unexplained variation).

P

ESS = (ŷi − ȳ)2 is the explained sum of squares.

P

Since TSS = ESS + RSS, we can express R2 as:

ESS (yi − ŷi )2

P
2
R = =1− P
TSS (yi − ȳ)2

R2 ranges from 0 to 1.
R2 = 1 means the model perfectly explains the variation in Y .
R2 = 0 means the model does not explain any variation.

A higher R2 indicates a better fit, but it does not imply causation or correctness of the model.
Since adding more predictors to a model increases R2 (even if they are irrelevant), the adjusted R2 accounts
for model complexity:

RSS/(n − k − 1)
 
2
Radj =1−
TSS/(n − 1)
where k = number of independent variables and n = number of observations.

7
2.5.2 F-Statistic for Overall Model Significance
The F-statistic tests whether at least one predictor in the model has a significant effect on Y . It is based on
the decomposition:

TSS = ESS + RSS

F-Statistic Formula
ESS
k
F = RSS
n−k−1

where k = number of independent variables and n − k − 1 = degrees of freedom for the residuals.

H0 : All regression coefficients (β1 , β2 , . . . , βk ) are equal to zero.

H1 : At least one βj ̸= 0 (the model has predictive power).
The test follows an F (k, n − k − 1) distribution. If F is large, we reject H0 , meaning the model explains
significant variation in Y .

2.5.3 Prediction
Given an estimated simple linear regression model:

yˆi = β̂0 + β̂1 xi

we can predict the value of y for a new observation x∗j for j = 1, . . . , m as

ŷj∗ = β̂0 + β̂1 x∗j

This provides a point prediction, but it does not capture uncertainty. We can test the accuracy of the
prediction using mean square error (MSE).
m
1 X
(yj − ŷj∗ )2
m j=1

A prediction interval (PI) estimates an interval for Y ∗ , given X ∗ . The (1 − α) × 100% PI for the mean
response is:
Ŷ ∗ ± tα/2,n−2 · SE(Ŷ ∗ )
where: s
1 (X ∗ − X̄)2
SE(Ŷ ∗ ) = σ̂ +P
n (Xi − X̄)2
The PI is always wider than the CI since it includes both model uncertainty and individual variation.
CI estimates the mean response E(Y |X ∗ ).PI estimates the actual response Y ∗ , which includes additional
variation.

2.6 Issues with Linear Regression

When we fit a linear regression model to a particular data set, many problems may occur. Most common
among these are the following:
1. Non-linearity of the response-predictor relationships.
Do residual plot against fitted dependent variable to check.
Try non linear transformations of independent variables in case there is non linearity.

2. Correlation of error terms.

Independent observations have more information than dependent observations
Correlation between error terms will lead to deflated standard errors which will give narrowed CI
(a false sense of confidence).

3. Non-constant variance of error terms.

8
 Do residual plot against fitted dependent variable to check.
Do weighted least squares
n n
X xi x′ i −1
X xi yi
β̂w = ( ) ( )
i=1
σi2 i=1
σi2

4. Outliers.
Unusual value of fitted value of dependent variable compared to actual value
Check studentized residuals
ϵ̂i
se(ϵ̂i )

5. High-leverage points.
Unusual value of independent variable.
Might be more dangerous than outlier because of the extrapolation in a space where not a lot of
data is available. Thus, prediction relies on only one/few observations.
Calculate the leverage values (will not go into formula).
6. Collinearity.
High standard errors
May remove one of the predictors

3 Classification
Example: A person arrives at the emergency room with a set of symptoms that could possibly be attributed
to many medical conditions. Which of the the conditions does the individual have? The dependent variable
is discrete/category. Just like for the case of continuous dependent variable, we will train our model on the
training data and then test it on test data. Discrete data can be nominal or ordinal.

3.1 Why not Regression?

• Linear regression impose ordering on the outcome in case it is nominal. Not possible if categories are
more than two.
• In case of nominal with two categories, linear regression estimates probability P r(Y |X) which may lie
outside 0 and 1.

Figure 4

• In case the outcome is ordinal, linear regression impose equidistant assumption which might not be
true if we care about ranking only.

9
3.2 Logistic Regression for Binary Dependent Variable
In linear probability model (LPM or linear regression), the probability is defined as
P (y|x) = α + β1 x1 + . . . + βk xk
In logistic regression, the probability is defined as
eα+β1 x1 +...+βk xk
P (y|x) =
1 + eα+β1 x1 +...+βk xk
Or written in a different manner
 P (y|x) 
log = α + β1 x 1 + . . . + βk x k
1 − P (y|x)
The idea is to have a function which stays between 0 and 1. Other famous model is Probit model which uses
CDF of normal distribution.

Figure 5

3.2.1 Estimation
We will model an example where the dependent variable (yi ) is binary where it takes value 1 if the patient
has disease and 0 otherwise. We also have data on the symptoms and patient’s characteristics (xi ). We
will start modeling the problem at an observation level. Let patient has a disease with probability p and no
disease with probability 1 − p. The probability mass function (PMF) for y will take the form.
p(yi ) = pyi (1 − p)1−yi
Here y is a Bernoulli random variable. But we have data on n patients. Therefore, assuming random sample
(i.i.d) the joint PMF will look like
n
Y
p(y1 , . . . , yn ) = pyi (1 − p)1−yi
i=1

Replace p with P (y|x) and maximize the likelihood function with respect to β.

3.2.2 Prediction
Once β is estimated, we can estimate P (y ∗ |x∗ ) for a new observation x∗ and if P (y ∗ |x∗ ) > 0.5 we predict
disease and if P (y ∗ |x∗ ) ≤ 0.5 we predict no disease.
∗ ∗
∗ ∗ eα̂+β̂1 x1 +...+β̂k xk
P̂ (y |x ) = ∗ ∗
1 + eα̂+β̂1 x1 +...+β̂k xk

3.3 Multinomial Logistic Regression

In multinomial logistic regression with P categories, the probability is defined as
eαp +β1p x1 +...+βkp xk
P (y = p|x) = PP −1 α +β x +...+β x
1 + j=1 e j 1j 1 kj k

for p = 1, . . . , P − 1. We select a single category to serve as the baseline; without loss of generality, we select
the pth category for this role.

10
3.4 Summary
1. We are interested in estimating P (y|x) where y is a discrete variable. It is interpreted as the probability
that y takes the following category given x. Thus, we define the P (y|x) as a function of x. LPM defines
it as a linear function and logistic defines it as non linear as seen above.
2. Once P (y|x) is modeled, we maximize an objective function (likelihood function) which takes the form
of joint probability of independent Bernoulli trials. The objective function takes the probability which
is modeled in step 1 and is given as
n 
Y eα+β1 x1 +...+βk xk yi  eα+β1 x1 +...+βk xk 1−yi
L(α, β1 , . . . , βk |y1 , . . . , yn ) = 1 −
i=1
1 + eα+β1 x1 +...+βk xk 1 + eα+β1 x1 +...+βk xk

3. We obtain estimates as {α̂, β̂1 , . . . , β̂k } which are used to predict probability for new units/individuals
(say y ∗ ) whose x (say x∗) is known in the following way
∗ ∗
∗ ∗ eα̂+β̂1 x1 +...+β̂k xk
P̂ (y |x ) = ∗ ∗
1 + eα̂+β̂1 x1 +...+β̂k xk

4. We predict y ∗ = 1 or 0 depending upon whether P̂ (y|x∗ ) > 0.5 or < 0.5. For multinomial logit, we
classify y∗ in the category with highest probability.

3.5 Linear Discriminant Analysis

So rather than modeling P (y|x) directly, we can model P (y|x) using Bayes theorem as
P (y = p)P (x|y = p)
P (y = p|x) = PP
j=1 P (y = j)P (x|y = j)

P (y = p|x) is the posterior probability that an observation posterior x belongs to the pth class, P (y = p)
is the prior probability that a randomly chosen observation comes from the prior pth class and P (x|y = p)
is conditional density of x given y interpreted as given the category y = p, what is the probability of x
occurring.
In linear discriminant analysis (LPA), we model the conditional density and prior density as follows
np
P̂ (y = p) =
n
1 n −(x − µ )2 o
p
P (x|y = p) = √ exp
2πσ 2 2σ 2
where np is the number of observations falling in p category and n is total category. We don’t have the
values µp and σ 2 .
1 X
µ̂p = xi
np i:y=p
P
1 X X
σ̂ = (xi − µi )2
n − P p=1 i:y=p

Therefore, the estimated P (x|y = p) takes the form

np
P̂ (y = p) =
n
1 n −(x − µ̂ )2 o
p
P̂ (x|y = p) = √ exp
2πσ̂ 2 2σ̂ 2

3.5.1 Prediction
Once P (y = p) and P (x|y = p) are estimated, we can estimate P (y|x) for a new observation and classify the
observation to the category with the maximum estimator posterior probability given as.

P̂ (y = p)P̂ (x|y = p)
P̂ (y = p|x) = PP
j=1 P̂ (y = j)P̂ (x|y = j)

11
3.5.2 Another Perspective
For two classification problem, minimize the following objective function
µ1 − µ2
v̂ = max
v,||v||=1 2σ 2

where v is 2 × 1 vector whose some is 1, µ1 and µ2 are means and σ 2 is the variance on a 1D projection
space. In LDA, we assume variances to be same. The optimal v should be such that µ1 − µ2 should be large
and σ 2 should be small.

Figure 6

3.5.3 Quadratic Discriminant Analysis

For two classification problem, minimize the following objective function
µ1 − µ2
v̂ = max
v,||v||=1 σ12 + σ22

where, σ12 and σ22 are the variances on a 1D projection space. QDA assumes variance to be different compared
to LDA.

3.6 Naive Bayes

As the name suggests, we model P (y|x) using Bayes theorem as

P (y = p)P (x|y = p)
P (y = p|x) = PP
j=1 P (y = j)P (x|y = j)

The prior density is estimated similarly to how we did in LDA and QDA which is given as
np
P̂ (y = p) =
n
The conditional density in LDA and QDA for a category p is assumed to be normally distributed whose
variance covariance matrix is k × k. Naive Bayes assumes conditional density of k predictors for a given
observation as product of k independent densities as

P (x|y = p) = P (x1 |y = p)P (x2 |y = p) . . . P (xk |y = p)

This is similar to QDA as it allows for varying variances for each category but the off diagonal terms are 0 due
to independence between predictors. That helps in estimation in high dimension. The conditional density
then can be estimated by assuming univariate normal distribution for each predictor, kernal estimation etc.
The final prediction takes the form

P̂ (y = p)ˆ
ˆP (x1 |y = p)P̂ (x2 |y = p) . . . P̂ (xk |y = p)
P̂ (y = p|x) = PP
ˆ
j=1 P̂ (y = j)ˆP (x1 |y = j)P̂ (x2 |y = j) . . . P̂ (xk |y = j)

12
 Figure 7

3.7 K-Nearest Neighbors

Given a positive integer K and a test observation x, K-nearest neighbors first identifies the K points in the
training data that are closest to x, say N0 . It then estimates the conditional probability for class p as the
fraction of points in N0 whose response values equal p:
1 X
P (y = p|x) = I(yi = p)
K
i∈N0

Finally, KNN classifies the test observation x to the class with the largest probability. Different distance
measures can be used such as Euclidean or Manhattan. If there are K predictors, then the Euclidean distance
can be estimated as
v
u J
uX
distance = t (xj − Xj )2
j=1

for each Xj and then the K points with smallest distance form N0 .

3.7.1 Choice of K
Smaller values of K makes the model overly flexible (low bias) but might have high variance (overfitting).
Larger values of K makes the model less flexible (low variance) but probably have high bias (underfitting).
The choice of K is crucial in KNN and resampling methods can be used to determine them.

4 Resampling Methods
Resampling methods involve repeatedly drawing samples from a training set and refitting a model of interest
on each sample in order to obtain additional information about the fitted model. The most famous resampling
techniques are cross validation and bootstrapping.

4.1 Cross Validation

In the absence of a very large designated test set that can be used to directly estimate the test error rate, a
number of techniques can be used to estimate this quantity using the available training data. Cross validation
is generally used for model selection.

4.1.1 Validation Set Approach

It involves randomly dividing the available set of observations into two parts, a training set and a validation
set or hold-out set.

13
4.1.2 Leave-One-Out Cross-Validation
If a sample consists of n observations as {(y1 , x1 ), . . . , (yn , xn )}, LOOCV leaves one observation out as
a test sample and fits the model on the remaining n − 1 observations. Calculate the Squared errors as
SEi = (yi − ŷi )2 and continue this exercise for all n observations. Finally, estimates the MSE as
n
1X
M SELOOCV = SEi
n i=1

LOOCV may pose computational problems, especially if n is extremely large.

4.1.3 K-Fold Cross-Validation

This approach involves randomly k-fold CV dividing the set of observations into k groups, or folds, of
approximately equal size. The first fold is treated as a validation set, and the method is repeated on the
remaining k − 1 folds. The mean squared error,M SE1 , is then computed on the observations in the held-out
fold. This procedure is repeated k times; a different fold is treated as a validation set each time. This process
results in k estimates of the test error, M SE1 , M SE2 , . . . , M SEk . The k-fold CV estimate is computed by
averaging these values,
k
1X
M SEkCV = M SEi
k i=1

k-CV is computationally less costly than LOOCV. The choice of k gives researcher the flexibility to effect
the bias-variance trade off. LOOCV might be on the end of high variance and low bias and validation set
approach is on the low variance and high bias end. A value of k in between might be optimum.

4.2 Bootstrapping
The bootstrap is used to quantify the uncertainty associated with a given estimator or statistical learning
method. It is a very general method to not only obtain an estimator, but to get standard errors and
confidence intervals. The following steps are performed as part of bootstrapping.
1. Start with a dataset containing n observations.

2. Randomly draw a sample of size n from the original dataset with replacement — meaning some samples
may appear multiple times while others may be excluded.
3. Repeat step 2 B times to generate multiple datasets.
4. For each bootstrapped dataset, train a model independently and estimate the parameter of interest.
Example, For regression tasks, obtain slope parameter for all B datasets or for classification, obtain
probability of success.
5. The eventual sampling distribution can be used to obtain mean, standard error or confidence intervals
for that estimator.
6. Measure model performance using out-of-bag (OOB) samples — the data points that weren’t selected
during a particular bootstrap round — to get unbiased error estimates.
This approach reduces overfitting and increases stability especially when n is small. This can be computa-
tionally expensive and depends strongly on the sample being representative of the population.

5 Linear Model Selection and Regularization

Here we discuss some ways in which the simple linear model can be improved, by replacing the plain least
squares fitting with some alternative fitting procedures. Assuming linear regression is a good approximation
to the true model, when sample size is relatively large compared to parameters to be estimated, the model
has low variance and low bias. As the sample size relative to parameters become smaller, the variance of the
model increase. By constraining or shrinking the estimated coefficients, we can often substantially reduce
the variance at the cost of a negligible increase in bias. This can lead to substantial improvements in the
accuracy with which we can predict the response for observations not used in model training

14
5.1 Subset Selection
The aim is to find the best model among the linear model. It means how many predictors should be added
to the regression. This exercise selects relevant predictors to be used for prediction.

5.1.1 Best Subset Selection

With p predictors, we estimate all 2p models and choose the one with the best performance (Adj R2 , MSE,
Cross Validation). The following steps are followed to conduct best subset selection and select the best set
of predictors.

1. Given you have P predictors, start with no predictors and thus mean value of dependent variable is
the prediction. Estimate some measure of model performance.
2. Start with p = 1, where p is the number of predictors considered in the model and rotate for all P
predictors

3. Consider p = 2, . . . , P and estimate all possible combinations of predictors for a given p.

4. Choose the model with the best performance.
It guarantees to give the best model among all combination but is computationally heavy.

5.1.2 Forward Subset Selection

Forward stepwise selection begins with a model containing no predictors, and then adds predictors to the
model, one-at-a-time, until all of the predictors are in the model. With p predictors, we estimate all 1+ p(p+1)
2
models and choose the one with the best performance (Adj R2 , MSE, Cross Validation). The following steps
are followed to conduct forward subset selection and select the best set of predictors.
1. Given you have P predictors, start with no predictors and thus mean value of dependent variable is
the prediction. Estimate some measure of model performance.
2. Start with p = 1, where p is the number of predictors considered in the model and rotate for all P
predictors
3. Choose the best model for p = 1, fix the predictor and estimate for p = 2 with one predictor being
fixed.

4. Continue for p = 3, . . . , P and choose the model with the best performance.
It is computationally more viable for example if p = 20, best subset selection requires fitting 1,048,576
models, whereas forward stepwise selection requires fitting only 211 models. But it does not guarantee the
best model.

5.1.3 Backward Subset Selection

Unlike forward stepwise selection, it begins with the full least squares model containing all p predictors, and
then iteratively removes the least useful predictor, one at a time. The following steps are followed to conduct
backward subset selection and select the best set of predictors.
1. Start with the model with all p predictors and measure the model performance.

2. Consider models that contain all but one of the predictors (p−1 predictors) and choose the best model.
3. Repeat step 2 for k where k = 2, . . . , p − 1 and you consider p − k predictors for model.
4. Choose the model with the best performance.
It is computationally more viable but it does not guarantee the best model.

15
5.1.4 Evaluation of Models
We already know MLE, R2 , adj R2 and accuracy to be metrics for model evaluation. MSE is defined in the
following way
RSS
M SE =
n
Pn
where RSS = i=1 (yi − ŷ) . One of the issues with MSE is that if we calculate it on training data, it
2

underestimates the value for the test data. This is because we specifically estimate the regression coefficients
such that the training RSS (but not the test RSS) is as small as possible. In particular, the training error
will decrease as more variables are included in the model, but the test error may not. So can we have model
evaluation metrics which will account for the bias that generates from the training data? We will talk about
two of them.
AIC criterion
1
AIC = (RSS + 2dσ̂ 2 )
n
where d is the number of predictors. AIC adds a penalty for each additional predictor.
BIC criterion
1
BIC = (RSS + log(n)dσ̂ 2 )
n
where d is the number of predictors. BIC adds a penalty for each additional predictor.
Of course we can use cross validation as well. AIC and BIC criteria allow for a quick model evaluation
compared to cross validation which is computationally expensive.

5.2 Shrinkage Methods

5.2.1 Ridge Regression
Ridge Regression is a regularization technique used to prevent overfitting in linear regression models by
adding a penalty term to the cost function. Consider the standard linear regression model:
y = Xβ + ϵ,
where:y is the response variable, X is the design matrix containing predictor variables, β is the vector of
regression coefficients and ϵ is the error term. The ordinary least squares (OLS) estimate is given by:
β̂ = (X ′ X)−1 X ′ y.
Ridge regression adds an L2 penalty term to the cost function to shrink the regression coefficients:
n
X p
X
min (yi − Xi β)2 + λ βj2 .
β
i=1 j=1

The penalty term is applied to coefficients and not the intercept. This results in the modified estimate:
β̂ridge = (X ′ X + λI)−1 X ′ y.
Ridge regression helps in handling multicollinearity by stabilizing the coefficient estimates.

5.2.2 Lasso Regression

Lasso regression adds an L1 penalty term to the cost function:
n
X p
X
2
min (yi − Xi β) + λ |βj |.
β
i=1 j=1

This penalty encourages sparsity, meaning that some coefficients may be exactly zero, effectively performing
variable selection.
• Ridge uses an L2 penalty (sum of squared coefficients), whereas Lasso uses an L1 penalty (sum of
absolute values of coefficients).
• Ridge regression shrinks coefficients continuously but does not set them exactly to zero, while Lasso
can shrink some coefficients to zero, performing feature selection.
• Ridge is useful when all predictors contribute to the model, while Lasso is preferred when only a few
predictors are expected to be significant.

16
5.3 Dimensionality Reduction
Principal Component Analysis (PCA) and Partial Least Squares (PLS) are widely used techniques for dimen-
sionality reduction and regression modeling. PCA transforms correlated variables into uncorrelated principal
components, whereas PLS finds components considering both predictors and response variables.

5.3.1 Principal Component Analysis (PCA)

PCA is a statistical technique used to transform a dataset with correlated variables into a set of linearly
uncorrelated variables called principal components. This is achieved by computing the eigenvectors and
eigenvalues of the covariance matrix.
The first principal component of a set of features X1 , X2 , . . . , Xp is the normalized linear combination of the
features

Z1 = ϕ11 X1 + ϕ21 X2 + . . . + ϕp1 Xp

Pp
that has the largest variance given the constraint j=1 ϕ2j1 = 1. ϕ is referred to as loadings. How to estimate
phi?
n X
X p p
X
max ( ϕj1 xij )2 subject to ϕ2j1 = 1.
ϕ
i=1 j=1 j=1

The second principle is estimated with the constraint that it is orthogonal to the first principle and so on.
Another way to look at PCA is through linear algebra. Given a centered data matrix X (zero mean), the
covariance matrix is:
1
C = X T X.
n
Principal components are obtained by solving:

Cvi = λi vi ,

where vi are eigenvectors and λi are eigenvalues. The principal components are linear combinations of the
original variables:
Zi = Xvi .
Selecting the first k principal components captures most of the variance in the data, reducing dimensionality
while preserving essential information. The proportion of variance explained by the first k components is
given by:
Pk
λi
P V Ek = Ppi=1 .
j=1 λj

It is useful for
• Feature selection and dimensionality reduction.
• Noise filtering in high-dimensional datasets.
• Image compression and pattern recognition.

5.3.2 Principle Component Regression

PCR applies PCA to predictor variables before performing regression, mitigating multicollinearity. The steps
of PCR are:
1. Standardize the predictors.
2. Perform PCA and obtain principal components.
3. Use the first M components as predictors in regression.
4. Fit a linear model:
M
X
Y = β0 + βi Zi + ϵ.
i=1

PCR improves model interpretability and reduces overfitting.

17
5.3.3 Partial Least Squares (PLS)
PLS is a supervised technique that finds components considering both X and Y . Unlike PCA, PLS maximizes
covariance between the predictors and response.
1. Standardize X and Y .
2. Given the following equation
Z1 = ϕ11 X1 + ϕ21 X2 + . . . + ϕp1 Xp
Pp
we will estimate ϕ such that j=1 ϕ2j1 = 1 and it maximizes the covariance between Z1 and Y
3. Repeat to obtain multiple components.
While PCR extracts components without considering Y , PLS directly optimizes components to predict Y .
PLS often performs better when predictors are highly correlated.

6 Non-linear Estimation
6.1 Polynomial Regression

yi = β0 + β1 xi + β2 x2i + . . . + βd xdi + ϵ
For large values of d, polynomial regression can fit any function. Estimation is proceeded using OLS.
Generally speaking, it is unusual to use d greater than 3 or 4 because for large values of d, the polynomial
curve can become overly flexible and can take on some very strange shapes.

6.2 Step Functions

Using polynomial functions of the features as predictors in a linear model imposes a global structure on
the non-linear function of X. We can instead use step functions in order to avoid imposing such a global
structure. Here we break the range of X function into bins, and fit a different constant in each bin. This
amounts to converting a continuous variable into an ordered categorical variable. For K + 1 bins, we create
K cutpoints as
C1 (X) = I(X ≤ c1 )
C2 (X) = I(c1 X ≤ c1 )
.. ..
. .
CK (X) = I(cK−1 X ≤ cK )
CK+1 (X) = I(X ≥ cK )
We can use OLS to estimate
yi = β1 C1 (X) + β2 C2 (X) + . . . + βK+1 CK+1 (X) + ϵ

6.3 Regression Splines

6.3.1 Piecewise Polynomial
Instead of fitting a high-degree polynomial over the entire range of X, piecewise polynomial regression
involves fitting separate low-degree polynomials piecewise polynomial regression over different regions of X.
A piecewise cubic polynomial works by fitting a cubic regression model of the form
yi = β0 + β1 xi + β2 x2i + β3 x3i + ϵ
where the coefficients β0 , β1 , β2 , and β3 differ in different parts of the range of X. The points where the
coefficients change are called knots. A piecewise cubic polynomial with a single knot at a point c takes the
form
yi = β10 + β11 xi + β12 x2i + β13 x3i + ϵ if xi < c
yi = β20 + β21 xi + β22 x2i + β23 x3i + ϵ if xi ≥ c
In other words, we ft two different polynomial functions to the data.

18
6.3.2 Constraints and Splines
There can be discontinuity between knots. To remedy this problem, we can impose a constraint which
enforce continuity across knots.

19