Stanford OnlineStanford CS229: Machine Learning - Linear Regression and Gradient Descent | Lecture 2 (Autumn 2018)
Summaries, chapters, transcripts, and FAQs on this page are made by uListen, not YouTube.
CHAPTERS
- 0:04 – 4:05
Overview and Motivating Linear Regression with House Prices
Andrew Ng previews the lecture: linear regression, batch and stochastic gradient descent, and the normal equations. He links linear regression to supervised learning and regression, then builds it up with a Portland housing data set and the training-set-to-hypothesis workflow.
- •Lecture plan covers linear regression, batch and stochastic gradient descent, and the normal equations
- •Supervised learning maps inputs X to outputs Y; regression means a continuous output
- •Housing example uses size in square feet and price in thousands of dollars from Portland
- •A learning algorithm takes a training set and outputs a hypothesis that predicts price from size
- 4:05 – 13:07
Representing the Hypothesis and Notation
Ng explains the key design decision of how to represent the hypothesis as a linear (technically affine) function. He extends it to multiple features and introduces the compact sum notation with a dummy feature x0 = 1, along with the notation m, n, x, y and superscript (i).
- •Hypothesis is a linear function of size with parameters theta
- •With two features, h(x) = theta0 + theta1 x1 + theta2 x2
- •Defining x0 = 1 lets the hypothesis be written as a sum of theta_j x_j
- •m is the number of training examples and n the number of features, so x and theta are (n+1)-dimensional
- •Superscript (i) indexes training examples and is not exponentiation
- 13:07 – 17:48
The Cost Function and Least Squares
Ng explains that parameters should be chosen so h(x) is close to y on the training examples. He builds the squared-error cost function J(theta), including the one-half convention, and defers the question of why squared error to the later discussion of generalized linear models.
- •Choose theta so predictions are close to known prices on training houses
- •Cost function is one-half the sum of squared differences between h(x) and y
- •The one-half simplifies the derivative math later
- •Linear regression is also called ordinary least squares
- •Why squared error is deferred to next week's generalized linear models, where it corresponds to Gaussian
- 17:48 – 23:04
Gradient Descent Intuition and Visualization
Ng introduces gradient descent as the algorithm for minimizing J(theta). Using a hill-walking analogy, he shows how it starts from an initial theta and repeatedly takes small steps downhill, and notes that general surfaces can have different local optima depending on initialization.
- •Start from some initial theta, such as all zeros, and keep changing it to reduce J
- •Visualization of J as a surface over theta0 and theta1
- •At each point take a small step in the direction of steepest descent
- •Different starting points can lead to different local minima
- •Linear regression will turn out to have no local optima
- 23:04 – 33:13
The Update Rule and Derivative Derivation
Ng formalizes the gradient descent update with the learning rate alpha and the partial derivative of the cost. After a student asks how to set the learning rate, he works through the derivative for a single example and then extends it to a sum over all m examples.
- •Colon-equals notation denotes assignment
- •Update: theta_j := theta_j minus alpha times the partial derivative of J
- •Initial advice on the learning rate is to start with 0.01 when features are scaled to about plus or minus one
- •Derivative for one example works out to (h(x) - y) times x_j
- •For the full cost function, sum this over all m training examples and repeat until convergence
- 33:13 – 39:08
Convergence, Learning Rate Choice, and Visualizing the Fit
Ng shows that J(theta) for linear regression is a quadratic bowl with elliptical contours and a single global minimum, so gradient descent converges. He discusses too-large and too-small learning rates and shows how the fitted line improves with each iteration on the 49-point data set.
- •J(theta) is quadratic, so the only local optimum is the global optimum
- •Contours are ellipses, and steepest descent is orthogonal to the contours
- •Too large a learning rate overshoots; too small makes the algorithm slow
- •A rising cost is a strong sign the learning rate is too large; try values on an exponential scale
- •Hypothesis line starts horizontal at zero and fits the data better each iteration
- 39:08 – 40:35
Why Subtract the Gradient
A student asks why the update subtracts alpha times the gradient instead of adding it. Ng explains that adding would go uphill and suggests working through J(theta) = theta squared at theta = 1 to see why subtracting is correct.
- •The gradient points uphill, so moving downhill requires subtracting it
- •Adding a multiple of the gradient would climb the surface
- •Worked example: J(theta)=theta squared at theta=1 has derivative positive, so theta should decrease
- 40:35 – 44:53
Batch Gradient Descent and Its Cost on Large Data
Ng names the algorithm batch gradient descent because each step uses the entire training set. He explains that with data sets of millions or hundreds of millions of examples, every single step requires scanning all the data, which becomes very slow and expensive.
- •Gradient descent still widely used and effective for linear regression
- •Batch means summing over all m training examples for every update
- •Big data sets can have hundreds of millions of examples or terabytes of data
- •One step requires a full pass over the data, repeated for hundreds to tens of thousands of iterations
- 44:53 – 48:12
Stochastic Gradient Descent
Ng introduces stochastic gradient descent, which updates the parameters using one training example at a time. It follows a noisy path toward the minimum and never fully converges, but makes much faster progress on large data sets and is used more often in practice.
- •Update parameters using the derivative from a single example i, looping i from 1 to m
- •Path is noisy but on average heads toward the global minimum
- •Parameters oscillate and never quite converge
- •Much faster progress on very large data sets, so used more in practice
- 48:12 – 53:05
Practical Questions: Mini-Batch, Decaying Learning Rate, Stopping, and Choosing Batch vs Stochastic
In response to student questions, Ng covers mini-batch gradient descent, slowly decreasing the learning rate to shrink oscillations, and monitoring J(theta) to decide when to stop. He also advises using batch gradient descent for small data sets and stochastic for very large ones.
- •Switching to batch is possible but rarely done; mini-batch uses about a hundred examples at a time
- •Stochastic gradient descent's result is usually good enough even if not the exact global minimum
- •Slowly decreasing the learning rate reduces oscillation
- •Stop by plotting J(theta) and watching for it to stop decreasing
- •For small data sets Ng would almost always use batch gradient descent as there's less to fiddle with
- 53:05 – 1:07:44
Matrix Derivative Notation and Trace Properties
Ng introduces the normal equation as a one-step solution that works only for linear regression. He defines derivatives with respect to vectors and matrices, then the trace operator and several of its properties, which are tools for the derivation.
- •Gradient descent is iterative and needed for many later algorithms; the normal equation is specific to linear regression
- •Matrix derivative notation allows the derivation in roughly four lines
- •Derivative of a function of a matrix is a matrix of the same size with element-wise partial derivatives
- •Trace is the sum of diagonal entries, with trace(A)=trace(A transpose) and trace(AB)=trace(BA)
- •Derivative of trace(AB) with respect to A is B transpose
- 1:07:44 – 1:18:16
Deriving the Normal Equations
Ng writes J(theta) in matrix-vector form using the design matrix X and label vector y, then outlines the derivative, sets it to zero, and arrives at the normal equations. He closes with the non-invertible case and a final question on choosing the learning rate.
- •Design matrix X stacks training examples as rows, so X theta is the vector of predictions
- •J(theta) = one-half (X theta - y) transpose (X theta - y)
- •Setting the derivative to zero gives X transpose X theta = X transpose y
- •Optimal theta = (X transpose X) inverse X transpose y, reaching the global minimum in one step
- •If X transpose X is non-invertible, features are likely redundant; pseudo-inverse helps but finding the repeated feature is better
- •Choosing the learning rate is quite empirical, with most people trying different values
