Linear Regression

What are the 4 pillars that every ML lecture follows?

Every lecture in this course follows the same four-step framework:

Data, Model, Loss, and Optimization.

Data is what we collect — our examples.

Model is the function we use to make predictions.

Loss is how we measure how wrong the model is.

Optimization is how we find the best parameters to minimize that loss.

Every single ML method we study this semester follows this exact structure:

Data → Model → Loss → Optimization.

topics

SECTION 1 — WHAT IS REGRESSION?

1. Regression = we want to know how yy relates to x1,…,xdx1​,…,xd​.

2. The regression model: y=h(x)+zy=h(x)+z.

3. The dataset: D={(yi,xi)}i=1nD={(yi​,xi​)}i=1n​.

4. The modeling assumption: yi=h∗(xi)+ziyi​=h∗(xi​)+zi​.

5. The goal: learn h^h^, predict y=h^(x)y=h^(x) for new xx.

6. Why we need a hypothesis class HH.

7. Parameterized hypothesis class — learning reduces to estimating θθ.

8. The learning problem: θ^=arg⁡min⁡θ∑loss(hθ(xi),yi)θ^=argminθ​∑loss(hθ​(xi​),yi​).

9. Four-pillar framework: Data → Model → Loss → Optimization.

---

SECTION 1.1 — LINEAR MODEL

10. The linear model: hθ(xi)=⟨xi,θ⟩=xiTθhθ​(xi​)=⟨xi​,θ⟩=xiT​θ — weighted sum.

11. The linear hypothesis class: H={hθ(x)=⟨x,θ⟩:θ∈Rd}H={hθ​(x)=⟨x,θ⟩:θ∈Rd}.

12. Generative model: y=Xθ∗+zy=Xθ∗+z.

13. Intercept:

    • Intercept θ0θ0​ = baseline prediction when all features are zero.

    • Model with intercept: yi=θ0+⟨xi,θ⟩+ziyi​=θ0​+⟨xi​,θ⟩+zi​.

    • Absorb it: x~i=[1,xi]x~i​=[1,xi​], θ~=[θ0,θ]θ~=[θ0​,θ].

    • Then yi=⟨θ~,x~i⟩+ziyi​=⟨θ~,x~i​⟩+zi​.

    • "Without loss of generality" — any model with intercept can be rewritten without one on augmented features.

---

SECTION 1.2 — LEAST SQUARES ESTIMATION (Coming next)

14. Squared error for one example.

15. MSE (Mean Squared Error).

16. Matrix form of MSE.

17. Least squares estimate: θ^LS=arg⁡min⁡θR^(θ)θ^LS​=argminθ​R^(θ).

18. Closed-form solution: θ^LS=(XTX)−1XTyθ^LS​=(XTX)−1XTy.

---

SECTION 1.3 — ANALYSIS OF LEAST SQUARES (Later)

19. Unbiasedness.

20. Error bound and singular values.

21. Multicollinearity.

---

SECTION 2 — RIDGE REGRESSION (Later)

22. Ridge estimate.

23. Bias-variance tradeoff of ridge.

---

SECTION 3 — BIAS-VARIANCE TRADEOFF (Later)

24. Prediction error decomposition.

25. Bias, variance, irreducible error.

What is Linear Regression?

Linear Regression is a supervised learning algorithm.

Supervised means we have labeled data — input and output pairs.

It predicts a continuous output, meaning the prediction can be any real number, not a fixed category.

It does this by finding the best-fitting linear function — a weighted sum of the input features.

We use it when we believe the output changes at a constant rate when we change an input. For example, every extra bedroom adds exactly $50k to a house price regardless of how many bedrooms already exist — that's a linear relationship.

What is regression?

Regression is the problem of understanding how a quantity of interest y relates to several observed variables x1​,…,xd​.

We want to predict y for new inputs we have not seen.

The quantity y is called the response or dependent variable, and

the variables x1​,…,xd​ are called covariates, features, or independent variables.

The regression model

The regression model says the response y is determined by some function h applied to the features x,plus some unknown noise z.

We write it as

y=h(x)+z

We do not know h — we only see the output y, which is h(x) plus noise.

The noise captures measurement error, unobserved factors, and randomness.

dataset D

a collection of n training examples

D={(y1​,x1​),…,(yn​,xn​)}.

Each example is a pair (yi,xi)where yi∈R is the real-valued output and xi∈Rd is the input vector of d features.

The dataset is also called the training set

What is the modeling assumption about how the data is generated?

We assume that each output yi is generated as

yi= h^* (xi​)+zi

where h^* is the true underlying function and zi is the noise for example i.

This is a modeling assumption, typically not exactly satisfied in practice, but it makes the problem tractable.

(one that can be solved or computed efficiently in practical time and with realistic computational resources)

Why do we need a hypothesis class H?

Because learning an arbitrary function is intractable and not a well-posed problem — infinitely many functions fit any finite dataset.

We restrict the function to lie in a specific class H of allowable functions.

This makes the problem solvable.

What does it mean to say a hypothesis class is parameterized?

It means each function in the class is determined by a parameter or weight vector θ .

Instead of searching over all possible functions, we search over all possible values of θ.

Each θ gives us one specific function.

So learning h reduces to estimating θ.

What is the linear model?

The linear model predicts an output as a weighted sum of features.

We write it as

hθ(xi)=⟨xi​,θ⟩=x_i^T θ.

Here hθ​(xi​) is the predicted output for example i, xi​ is the input vector of features, and θ is the weight vector.

Expanded, this is

xi₁*θ₁+xi₂*θ₂+⋯+xi_d*θ_d

So each feature is multiplied by its weight, and all the products are added together.

That is why we call it a weighted sum — the prediction is the dot product of the features and the weights.

What is the hypothesis class H for linear regression?

The hypothesis class for linear regression is

H={hθ(x)=⟨x,θ⟩: θ∈ R^d}

for linear regression, we only consider linear functions. Each linear function takes the features x, multiplies each feature by its weight θ, and adds them up. Different weights θ give different linear functions. So H is the collection of all possible linear regression functions one for each possible θ.

What is the generative model for linear regression?

We assume the data is generated as

y_i=⟨x_i,θ^*⟩+z_i

for i=1,…,n

Each output is the dot product of the true parameter vector θ^* with the features, plus noise zi​.

In matrix form, this is

y=Xθ^*+z

where y∈Rⁿ is the vector of outputs, X∈R^nxd is the design matrix with one row per example, θ^*∈R^d is the true parameter, and z∈Rⁿ is the noise vector.

How do we include an intercept term in linear regression?

In practice, we usually fit a model with a constant term

θ_{0 :} y_i = θ₀ + <x_i , θ> + z<sub>i.

To absorb the intercept into the model, we define</sub>

_{new features x}

x_i=[1,x_i]∈ R^d+1

and a new parameter

θ=[θ₀,θ] ∈ R^d+1

Then

yi=⟨θ~,x~i⟩+zi

So a model with an intercept is just a model without an intercept on the augmented features. Without loss of generality, we can assume the linear model passes through the origin.

What is the least squares cost function?

The least squares cost function is