Hsuan-Tien Lin's ML Foundations L9–L10: From the Closed-Form Solution of Linear Regression to Gradient Descent for Logistic Regression

🌏 中文版

This is part 5 of the Reading NTU Hsuan-Tien Lin Machine Learning Foundations & Techniques series, following VC Dimension, Noise and Error Measures. It covers Lecture 9, Linear Regression, and Lecture 10, Logistic Regression, from Machine Learning Foundations. This is where the course reaches its third big question: "How Can Machines Learn?"

The previous post ended with this: the error an algorithm actually optimizes, êrr, should be either plausible or friendly. This post gives two friendly examples. Squared error has a closed-form solution. Cross-entropy does not, but it is smooth enough for gradient descent.

Official materials used:

• MOOC slides 09_handout.pdf and 10_handout.pdf; Fall 2024 versions 09u and 10u.
• Videos 34–41 of the Foundations YouTube playlist. Lectures are in Mandarin; slides are in English.
• Textbook Learning from Data (LFD): 3.2 for L9 and 3.3 for L10, per the Fall 2024 course page.
• Practice: the regression problems and cpusmall experiments in Fall 2024 HW3, and Q1 of Fall 2024 HW4.

Access level: videos and slides alone are A2. With the Fall 2024 homework PDFs and the public LIBSVM data sets it reaches A3, but there are no official solutions and grading is for enrolled students only. The grading scale is defined in the global AI/CS course map.

Version differences: the Fall 2024 09u slides have only three sections; the MOOC section Linear Regression for Binary Classification is gone, and the Fall 2024 L11 slides (11u) open with Linear Models for Binary Classification. This post still covers the MOOC section. The Fall 2026 course page schedules L9–L10 for W5 (10/07); as of 2026-09-30 that week's 09u slides are not yet public.

Part 1: Linear regression

The problem: real-valued output

Slides 2–5 change the credit card question from "approve or not" to "how large a credit limit". The output space is Y = ℝ, which makes it regression. The hypothesis is almost a perceptron, minus the sign:

h(x) = w^Tx

The goal is a line or hyperplane with small residuals, measured by squared error: E_in(w) = (1/N) Σ (w^Tx_n − y_n)².

The algorithm: one step

Stack the N examples into an N × (d+1) matrix X and an N-vector y. Then (slide 7):

E_in(w) = (1/N) ‖Xw − y‖²

It is continuous, differentiable and convex, so the optimum is where the gradient is zero (slide 8). Expanding and differentiating (slide 9):

∇E_in(w) = (2/N) (X^TXw − X^Ty)

Setting this to zero (slide 10):

• If X^TX is invertible, the unique solution is w_LIN = (X^TX)⁻¹X^Ty. Since N is usually much larger than d + 1, this is the common case.
• If X^TX is singular, there are many optimal solutions, and defining X† in other ways still gives one of them.

Both cases fold into w_LIN = X†y, where X† is the pseudo-inverse. The slide's practical advice: when the matrix is nearly singular, use a well-implemented † routine rather than computing (X^TX)⁻¹X^T yourself. It is more numerically stable.

The whole algorithm is three steps (slide 11): build X and y, compute X†, return X†y.

Is this really "learning"?

Slide 13 argues both sides. No: it is a closed-form solution, instant, with no step-by-step improvement of E_in. Yes: E_in is optimal, finite d_VC guarantees E_out as well, and pseudo-inverse routines iterate internally anyway. The verdict: if E_out(w_LIN) is good, learning happened.

The hat matrix: a guarantee simpler than VC

The prediction vector is ŷ = Xw_LIN = XX†y. Slide 14 calls H = XX† the hat matrix because it puts a hat on y to make ŷ.

Geometrically (slide 15), ŷ must lie in the span of the columns of X. For y − ŷ to be as short as possible, y − ŷ must be perpendicular to that span. So H projects y onto the column space of X, and I − H turns y into the residual perpendicular to it. The slide leaves a question: why is trace(I − H) = N − (d + 1)?

Suppose y is some ideal f(X) in the span plus noise with per-dimension level σ². I − H wipes out the ideal part and acts only on the noise, which gives (slide 16):

• average E_in = σ² · (1 − (d+1)/N)
• average E_out = σ² · (1 + (d+1)/N) (the slide notes this derivation is more complicated)

These two expressions are the learning curve of linear regression (slide 17). As N goes to infinity, both converge to the noise level σ². The expected generalization error is 2(d+1)/N, similar in shape to the worst-case VC guarantee.

A quiz on slide 18 lists properties of H: it is symmetric, H² = H (projecting twice is the same as once), and (I − H)² = I − H. All three follow from the physical meaning of projection.

Try this: in NumPy, generate random data with N = 100 and d = 5. Compare np.linalg.pinv(X) @ y with inv(X.T @ X) @ X.T @ y. Then make one column exactly twice another so X^TX becomes singular, and see which one breaks.

Part 2: Logistic regression

The problem: we want a probability

Slides 2–4 switch to heart attack prediction. Hard classification asks "will it happen?", with ideal target sign(P(+1|x) − ½). A doctor would rather hear "80% risk". Then the target is f(x) = P(+1|x) ∈ [0, 1], which the course calls soft binary classification.

The catch is the data. We never see each patient's true probability, only a ○ or × drawn from P(y|x). The data looks exactly like hard classification data; only the target function differs.

The logistic hypothesis

Compute a weighted risk score s = w^Tx, then squash it into [0, 1] with the logistic function (slides 5–6):

θ(s) = 1 / (1 + e^−s), with θ(−∞) = 0, θ(0) = ½, θ(∞) = 1

It is smooth, monotonic and S-shaped (a sigmoid). Logistic regression approximates P(+1|x) with h(x) = θ(w^Tx).

Slide 8 lines up three linear models. They compute the same score s = w^Tx and differ only in how they treat the output and which error they use.

From likelihood to cross-entropy

What error should logistic regression use? Slides 9–11 go through maximum likelihood:

1. If h ≈ f, the probability that h generates this data (its likelihood) should be close to the probability that f generates it, and f usually generates the data in hand with high probability. So pick the h with the largest likelihood.
2. The logistic function is symmetric: 1 − θ(s) = θ(−s). So whether a label is ○ or ×, each example's probability can be written h(y_nx_n), and the likelihood is proportional to Π θ(y_nw^Tx_n).
3. Take the log, negate, divide by N, and maximizing becomes minimizing:

E_in(w) = (1/N) Σ ln(1 + exp(−y_nw^Tx_n))

Each term err(w, x, y) = ln(1 + exp(−y w^Tx)) is the cross-entropy error. The quiz on slide 12 asks you to plot it against the score s. It is always above 0, below ln 2 when the prediction is right, at least ln 2 when it is wrong, and it has no upper bound.

The gradient, and why there is no closed form

E_in is continuous, twice differentiable and convex (slide 13), so again we look for a zero gradient. The chain rule gives (slide 14):

∇E_in(w) = (1/N) Σ θ(−y_nw^Tx_n) · (−y_nx_n)

This is a weighted sum of −y_nx_n, with weights θ(−y_nw^Tx_n). Slide 15 asks when it can be zero. Either every θ is 0, which only happens when the data is linearly separable and every y_nw^Tx_n is far above 0, or the weighted terms cancel exactly, which is a nonlinear equation in w. No closed-form solution.

The quiz on slide 17 explains the weights. Since θ is monotonic, the example with the smallest y_nw^Tx_n, the one that is most badly wrong, contributes most to the gradient.

Gradient descent

Without a closed form, go back to the spirit of PLA: start from some w₀ and repeat w_t+1 ← w_t + ηv (slide 16). In PLA, v comes from correcting a mistake. With a smooth E_in, you can pick a v that rolls the ball downhill.

The derivation takes three steps (slides 18–22):

1. Greedily search over unit-length v for the one that minimizes E_in(w_t + ηv). This is as hard as the original problem.
2. For small η, use a Taylor expansion as a linear approximation: E_in(w_t + ηv) ≈ E_in(w_t) + ηv^T∇E_in(w_t). The best v is the opposite of the gradient, −∇E_in/‖∇E_in‖.
3. Too small an η is slow; too large is unstable. The slides suggest making the step proportional to ‖∇E_in‖. The norms cancel, and you get gradient descent with a fixed learning rate: w_t+1 ← w_t − η∇E_in(w_t).

The full logistic regression algorithm (slide 23): initialize w₀, then repeatedly compute the gradient and update, until the gradient is close to zero or you have run enough iterations. Each iteration costs about the same as one pocket iteration.

The quiz on slide 24: with w₀ = 0 and η = 0.1, and since θ(0) = ½, the first step gives w₁ = 0.05 · (1/N) Σ y_nx_n. One step from the zero vector lands on a scaled average of y_nx_n.

Try this: write the update in ten lines of NumPy, run it on separable 2D data, and plot E_in against the iteration count. Then multiply η by ten and see whether the curve starts to oscillate.

Video list

L9 Linear Regression:

• Linear Regression Problem
• Linear Regression Algorithm
• Generalization Issue
• Linear Regression for Binary Classification

L10 Logistic Regression:

• Logistic Regression Problem
• Logistic Regression Error
• Gradient of Logistic Regression Error
• Gradient Descent

Practice: Fall 2024 HW3 and HW4 Q1

Problems in HW3 (released 2024-10-07, due 10/21) that match this post:

• Q2: the optimal w_lin for 1D linear regression h(x) = wx without x₀.
• Q3: which operation on X (scaling a row, scaling a column, multiplying everything by 2, adding columns to the first column) can change the hat matrix H.
• Q4: the likelihood of an estimate for samples drawn uniformly from [θ, 1].
• Q8: change every x₀ from 1 to 1126, rerun linear regression, and prove that the old and new solutions differ by a diagonal matrix D.
• Q9: switch to a different sigmoid hypothesis, follow the logistic regression steps to derive the new E_in, and find its gradient.
• Q10–12 (coding): use the cpusmall_scale data set from the LIBSVM site (8192 examples, 12 features). Q10 runs linear regression 1126 times with N = 32 and plots (E_in, E_out). Q11 averages 16 runs for each N = 25, 50, …, 2000 and plots learning curves. Q12 repeats Q11 with only the first 2 features and compares.

HW4 (released 2024-10-21, due 11/04):

• Q1: after mapping labels from {−1, +1} to {0, 1}, which expression is equivalent to the in-class cross-entropy? The problem also notes that the name "cross-entropy" comes from the p log q + (1 − p) log(1 − q) form.
• Extension: Q5 derives Newton's method from a second-order Taylor expansion and asks you to apply it to the cross-entropy of logistic regression, a natural step up from gradient descent.

Try this: compare the shape of your Q11 learning curves with σ²(1 ± (d+1)/N) from the hat matrix section. With no official solutions, cross-check w_lin against scikit-learn's LinearRegression or np.linalg.lstsq.

Next

The next post, Linear Models for Classification, SGD, Multiclass and Nonlinear Transforms, puts this post's three linear models on one error plot, turns gradient descent into stochastic gradient descent (SGD), and uses feature transforms to escape "straight lines only".

Further reading: the Stanford CS229 chapter guides on linear regression and logistic regression; Stanford CS109 on maximum likelihood estimation and logistic regression covers the same ground from a probability course.

References

• Machine Learning Foundations / Techniques MOOC page (Hsuan-Tien Lin)
• L9 Linear Regression slides
• L10 Logistic Regression slides
• Fall 2024 L9 slides (09u)
• Fall 2024 L10 slides (10u)
• Machine Learning Foundations YouTube playlist (lectures in Mandarin, slides in English)
• Machine Learning, Fall 2026 course page
• Machine Learning, Fall 2024 course page
• Fall 2024 Homework 3
• Fall 2024 Homework 4
• LIBSVM Data: cpusmall_scale
• Learning from Data textbook
• MOOC slide errata