Machine learning: overview

• In this module, I will provide an overview of the topics we plan to cover under machine learning.
 Course plan

Search problems
Markov decision processes Constraint satisfaction problems
Adversarial games Bayesian networks

Reflex States Variables Logic

”Low-level intelligence” ”High-level intelligence”

Machine learning

CS221 2
• Recall that machine learning is the process of turning data into a model. Then with that model, you can perform inference on it to make
predictions.
 Course plan

Search problems
Markov decision processes Constraint satisfaction problems
Adversarial games Bayesian networks
Reflex States Variables Logic
”Low-level intelligence” ”High-level intelligence”

Machine learning

CS221 4
• While machine learning can be applied to any type of model, we will focus our attention on reflex-based models, which include models such
as linear classifiers and neural networks.
• In reflex-based models, inference (prediction) involves a fixed set of fast, feedforward operations.
 Reflex-based models

predictor
input x y output
f

CS221 6
• Abstractly, a reflex-based model (which we will call a predictor f ) takes some input x and produces some output y.
• (In statistics, y is known as the response, and when x is a real vector, it is known as covariates or sometimes predictors, which is an unfortunate
naming clash.)
• The input can usually be arbitrary (an image or sentence), but the form of the output y is generally restricted, and what it is determines the
type of prediction task.
 Binary classification
classifier
x y ∈ {+1, −1} label
f

Fraud detection: credit card transaction → fraud or no fraud

Toxic comments: online comment → toxic or not toxic

Higgs boson: measurements of event → decay event or background

CS221 8
• One common prediction task is binary classification, where the output y, typically expressed as positive (+1) or negative (-1).
• In the context of classification tasks, f is called a classifier and y is called a label (sometimes class, category, or tag).
• Here are some practical applications.
• One application is fraud detection: given information about a credit card transaction, predict whether it is a fradulent transaction or not, so
that the transaction can be blocked.
• Another application is moderating online discussion forums: given an online comment, predict whether it is toxic (and therefore should get
flagged or taken down) or not.
• A final application comes from physics: After the discovery of the Higgs boson, scientists were interested in how it decays. The Large Hadron
Collider at CERN smashes protons against each other and then detects the ensuing events. The goal is to predict whether each event is a
Higgs boson decaying (into two tau particles) or just background noise.
• Each of these applications has an associated Kaggle dataset. You can click on the pictures to find out more details.
• As an aside, multiclass classification is a generalization of binary classification where the output y could be one of K possible values. For
example, in digit classification, K = 10.
 Regression

x f y∈R response

Poverty mapping: satellite image → asset wealth index

Housing: information about house → price

Arrival times: destination, weather, time → time of arrival

CS221 10
• The second major type of prediction task we’ll cover is regression. Here, the output y is a real number (often called the response or target).
• One application is poverty mapping: given a satellite image, predict the average asset wealth index of the homes in that area. This is used
to measure poverty across the world and determine which areas are in greatest need of aid.
• Another application: given information about a house (e.g., location, number of bedrooms), predict its price.
• A third application is to predict the arrival time of some service, which could be package deliveries, flights, or rideshares.
• The key distinction between classification and regression is that classification has discrete outputs (e.g., ”yes” or ”no” for binary classification),
whereas regression has continuous outputs.
 Structured prediction

x f y is a complex object

Machine translation: English sentence → Japanese sentence

Dialogue: conversational history → next utterance

Image captioning: image → sentence describing image

Image segmentation: image → segmentation

CS221 12
• The final type of prediction task we will consider is structured prediction, which is a bit of a catch all.
• In structured prediction, the output y is a complex object, which could be a sentence or an image. So the space of possible outputs is huge.
• One application is machine translation: given an input sentence in one language, predict its translation into another language.
• Dialogue can be cast as structured prediction: given the past conversational history between a user and an agent (in the case of virtual
assistants), predict the next utterance (what the agent should say).
• In image captioning, say for visual assistive technologies: given an image, predict a sentence describing what is in that image.
• In image segmentation, which is needed to localize objects for autonomous driving: given an image of a scene, predict the segmentation of
that image into regions corresponding to objects in the world.
• Generating an image or a sentence can seem daunting, but there’s a secret here. A structured prediction task can often be broken up into a
sequence of multiclass classification tasks. For example, to predict an entire sentence, predict one word at a time, going left to right. This is
a very powerful reduction!
• Aside: one challenge with this approach is that the errors might cascade: if you start making errors, then you might go off the rails and start
making even more errors.
 Roadmap
Models
Tasks
Non-linear features
Linear regression
Feature templates
Linear classification
Neural networks
K-means
Differentiable programming

Algorithms Considerations
Stochastic gradient descent Generalization

Backpropagation Best practices

CS221 14
• Here are the rest of the modules under the machine learning unit.
• We will start by talking about regression and binary classification, the two most fundamental tasks in machine learning. Specifically, we study
the simplest setting: linear regression and linear classification, where we have linear models trained by gradient descent.
• Next, we will introduce stochastic gradient descent, and show that it can be much faster than vanilla gradient descent.
• Then we will push the limits of linear models by showing how you can define non-linear features, which effectively gives us non-linear
predictors using the machinery of linear models! Feature templates provide us with a framework for organizing the set of features.
• Then we introduce neural networks, which also provide non-linear predictors, but allow these non-linearities to be learned automatically from
data. We follow up immediately with backpropagation, an algorithm that allows us to automatically compute gradients needed for training
without having to take gradients manually.
• We then briefly discuss the extension of neural networks to differentiable programming, which allows us to easily build up many of the
existing state-of-the-art deep learning models in NLP and computer vision like lego blocks.
• So far we have focused on supervised learning. We take a brief detour and discuss K-means, which is a simple unsupervised learning algorithm
for clustering data points.
• We end on a more reflective note: Generalization is about answering the question: when does a model trained on set of training examples
actually generalize to new test inputs? This is where model complexity comes up. Finally, we discuss best practices for doing machine
learning in practice.
Machine learning: linear regression
• In this module, we will cover the basics of linear regression.
 The discovery of Ceres

1801: astronomer Piazzi discovered Ceres, made 19 observations of location before it

was obscured by the sun

Time Right ascension Declination

Jan 01, 20:43:17.8 50.91 15.24
Jan 02, 20:39:04.6 50.84 15.30
... ... ...
Feb 11, 18:11:58.2 53.51 18.43

When and where will Ceres be observed again?

CS221 2
• Our story of linear regression starts on January 1, 1801, when an Italian astronomer Giuseppe Piazzi noticed something in the night sky while
looking for stars, which he named Ceres. Was it a comet or a planet? He wasn’t sure.
• He observed Ceres over 42 days and wrote down 19 data points, where each one consisted of a timestamp along with the right ascension and
declination, which identifies the location in the sky.
• Then Ceres moved too close to the sun and was obscured by its glare. Now the big question was when and where will Ceres come out again?
• It was now a race for the top astronomers at the time to answer this question.
 Gauss’s triumph

September 1801: Gauss took Piazzi’s data and created a model of Ceres’s orbit, makes
prediction

December 7, 1801: Ceres located within 1/2 degree of Gauss’s prediction, much more accurate
than other astronomers

Method: least squares linear regression

CS221 4
• Carl Friedrich Gauss, the famous German mathematician, took the data and developed a model of Ceres’s orbit and used it to make a
prediction.
• Clearly without a computer, Gauss did all his calculations by hand, taking over 100 hours.
• This prediction was actually quite different than the predictions made by other astronomers, but in December, Ceres was located again, and
Gauss’s prediction was by far the most accurate.
• Gauss was very secretive about his methods, and a French mathematician Legendre actually published the same method in 1805, though
Gauss had developed the method as early as 1795.
• The method here is least squares linear regression, which is a simple but powerful method used widely today, and it captures many of the key
aspects of more advanced machine learning techniques.
 Linear regression framework
4
training data
3 input 3
x y
2

y
example
1 1 learning algorithm
example f predictor
2 3 1
example
4 3
0
2.71 output 0 1 2 3 4 5

Design decisions:
Which predictors are possible? hypothesis class
How good is a predictor? loss function
How do we compute the best predictor? optimization algorithm

CS221 6
• Let us now present the linear regression framework.
• Suppose we are given training data, which consists of a set of examples. Each example (also known as data point, instance, case) consists
of an input x and an output y. We can visualize the training set by plotting y against x.
• A learning algorithm takes the training data and produces a model f , which we will call a predictor in the context of regression. In this
example, f is the red line.
• This predictor allows us to make predictions on new inputs. For example, if you feed 3 in, you get f (3), corresponding to the gray circle.
• There are three design decisions to make to fully specify the learning algorithm:
• First, which predictors f is the learning algorithm allowed to produce? Only lines or curves as well? In other words, what is the hypothesis
class?
• Second, how does the learning algorithm judge which predictor is good? In other words, what is the loss function?
• Finally, how does the learning algorithm actually find the best predictor? In other words, what is the optimization algorithm?
 Hypothesis class: which predictors?
4

3
f (x) = 1 + 0.57x
2

y
f (x) = 2 + 0.2x
1

f (x) = w1 + w2 x 0
0 1 2 3 4 5

Vector notation:
weight vector w = [w1 , w2 ] feature extractor φ(x) = [1, x] feature vector

fw (x) = w · φ(x) score

fw (3) = [1, 0.57] · [1, 3] = 2.71

Hypothesis class:
F = {fw : w ∈ R2 }
CS221 8
• Let’s consider the first design decision: what is the hypothesis class? One possible predictor is the red line, where the intercept is 1 and the
slope is 0.57, Another predictor is the purple line, where the intercept is 2 and the slope is 0.2.
• In general, let’s consider all predictors of the form f (x) = w1 + w2 x, where the intercept w1 and and the slope w2 can be arbitrary real
numbers.
• Now let us generalize this further using vector notation. Let’s pack the intercept and slope into a single vector, which we will call the weight
vector (more generally called the parameters of the model).
• Similarly, we will define a feature extractor (also called a feature map) φ, which takes x and converts it into the feature vector [1, x].
• Now we can succinctly write the predictor fw to be the dot product between the weight vector and the feature vector, which we call the
score.
• To see this predictor in action, let us feed x = 3 as the input and take the dot product.
• Finally, define the hypothesis class F to be simply the set of all possible predictors fw as we range over all possible weight vectors w. This
is the possible functions that we want our learning algorithm to consider.
 Loss function: how good is a predictor?
4

training data Dtrain 3

x y 2

y
fw (x) = w · φ(x)
w = [1, 0.57] 1 1 residual
φ(x) = [1, x] 1
2 3
4 3 0
0 1 2 3 4 5

Loss(x, y, w) = (fw (x) − y)2 squared loss

Loss(1, 1, [1, 0.57]) = ([1, 0.57] · [1, 1] − 1)2 = 0.32
Loss(2, 3, [1, 0.57]) = ([1, 0.57] · [1, 2] − 3)2 = 0.74
Loss(4, 3, [1, 0.57]) = ([1, 0.57] · [1, 4] − 3)2 = 0.08

1
P
TrainLoss(w) = |Dtrain | (x,y)∈Dtrain Loss(x, y, w)
TrainLoss([1, 0.57]) = 0.38
CS221 10
• The next design decision is how to judge each of the many possible predictors.
• Going back to our running example, let’s consider the red predictor defined by the weight vector [1, 0.57], and the three training examples.
• Intuitively, a predictor is good if it can fit the training data. For each training example, let us look at the difference between the predicted
output fw (x) and the actual output y, known as the residual.
• Now define the loss function on given example with respect to w to be the residual squared (giving rise to the term least squares). This
measures how badly the function f screwed up on that example.
• Aside: You might wonder why we are taking the square of the residual as opposed to taking an absolute value of the residual (known as the
absolute deviation): the answer for now is both mathematical and computational convenience, though if your data potentially has outliers, it
is beneficial to use the absolute deviation.
• For each example, we have a per-example loss computed by plugging in the example and the weight vector. Now, define the training loss
(also known as the training error or empirical risk) to be simply the average of the per-example losses of the training examples.
• The training loss of this red weight vector is 0.38.
• If you were to plug in the purple weight vector or any other weight vector, you would get some other training loss.
 Loss function: visualization
1 X
TrainLoss(w) = (fw (x) − y)2
|Dtrain |
(x,y)∈Dtrain
minw TrainLoss(w)

CS221 12
• We can visualize the training loss in this case because the weight vector w is only two-dimensional. In this plot, for each w1 and w2 , we have
the training loss. Red is higher, blue is lower.
• It is now clear that the best predictor is simply the one with the lowest training loss, which is somewhere down in the blue region. Formally,
we wish to solve the optimization problem.
 Optimization algorithm: how to compute best?
Goal: minw TrainLoss(w)

Definition: gradient

The gradient ∇w TrainLoss(w) is the direction that increases the

training loss the most.

Algorithm: gradient descent

Initialize w = [0, . . . , 0]
For t = 1, . . . , T : epochs
w ← w − η ∇w TrainLoss(w)
|{z} | {z }
step size gradient

CS221 14
• Now the third design decision: how do we compute the best predictor, i.e., the solution to the optimization problem?
• To answer this question, we can actually forget that we’re doing linear regression or machine learning. We simply have an objective function
TrainLoss(w) that we wish to minimize.
• We will adopt the ”follow your nose” strategy, i.e., iterative optimization. We start with some w and keep on tweaking it to make the
objective function go down.
• To do this, we will rely on the gradient of the function, which tells us the direction to move in that will decrease the objective function the
most.
• Formally, this iterative optimization procedure is called gradient descent. We first initialize w to some value (say, all zeros).
• Then perform the following update T times, where T is the number of epochs: Take the current weight vector w and subtract a positive
constant η times the gradient. The step size η specifies how aggressively we want to pursue a direction.
• The step size η and the number of epochs T are two hyperparameters of the optimization algorithm, which we will discuss later.
 Computing the gradient
Objective function:

1 X
TrainLoss(w) = (w · φ(x) − y)2
|Dtrain |
(x,y)∈Dtrain

Gradient (use chain rule):

1 X
∇w TrainLoss(w) = 2( w · φ(x) − y )φ(x)
|Dtrain | | {z }
(x,y)∈Dtrain
prediction−target

CS221 16
• To apply gradient descent, we need to compute the gradient of our objective function TrainLoss(w).
• You could throw it into TensorFlow or PyTorch, but it is pedagogically useful to do the calculus, which can be done by hand here.
• The main thing here is to remember that we’re taking the gradient with respect to w, so everything else is a constant.
• The gradient of a sum is the sum of the gradient, the gradient of an expression squared is twice that expression times the gradient of that
expression, and the gradient of the dot product w · φ(x) is simply φ(x).
• Note that the gradient has a nice interpretation here. For the squared loss, it is the residual (prediction - target) times the feature vector
φ(x).
• Aside: no matter what the loss function is, the gradient is always something times φ(x) because w only affects the loss through w · φ(x).
 Gradient descent example
training data Dtrain

x y 1
P
∇w TrainLoss(w) = |Dtrain | (x,y)∈Dtrain 2(w · φ(x) − y)φ(x)
1 1
Gradient update: w ← w − 0.1∇w TrainLoss(w)
2 3
4 3

t ∇w TrainLoss(w) w
[0, 0]
1
(2([0, 0] · [1, 1] − 1)[1, 1] + 2([0, 0] · [1, 2] − 3)[1, 2] + 2([0, 0] · [1, 4] − 3)[1, 4])
1 3
| {z } [0.47, 1.27]
=[−4.67,−12.67]

1
(2([0.47, 1.27] · [1, 1] − 1)[1, 1] + 2([0.47, 1.27] · [1, 2] − 3)[1, 2] + 2([0.47, 1.27] · [1, 4] − 3)[1, 4])
2 3
| {z } [0.25, 0.54]
=[2.18,7.24]

... ... ...

1
(2([1, 0.57] · [1, 1] − 1)[1, 1] + 2([1, 0.57] · [1, 2] − 3)[1, 2] + 2([1, 0.57] · [1, 4] − 3)[1, 4])
200 3
| {z } [1, 0.57]
=[0,0]

CS221 18
• Let’s step through an example of running gradient descent.
• Suppose we have the same dataset as before, the expression for the gradient that we just computed, and the gradient update rule, where we
take the step size η = 0.1.
• We start with the weight vector w = [0, 0]. Let’s then plug this into the expression for the gradient, which is an average over the three
training examples, and each term is the residual (prediction - target) times the feature vector.
• That vector is multipled by the step size (0.1 here) and subtracted out of the weight vector.
• We then take the new weight vector and plug it in again to the expression for the gradient. This produces another gradient, which is used to
update the weight vector.
• If you run this procedure for long enough, you eventually get the final weight vector. Note that the gradient at the end is zero, which indicates
that the algorithm has converged and running it longer will not change anything.
 Gradient descent in Python

[code]

CS221 20
• To make things even more concrete, let’s code up gradient descent in Python.
• In practice, you would probably use TensorFlow or PyTorch, but I will go with a very bare bones implementation on top of NumPy just to
emphasize how simple the ideas are.
• Note that in the code, we are careful to separate out the optimization problem (what to compute), that of minimizing training loss on
the given data, from the optimization algorithm (how to compute it), which works generically with the weight vector and gradients of the
objective function.
 Summary
4
training data
3 3
x y
2

y
1 1 learning algorithm
f predictor
2 3 1

4 3
0
2.71 0 1 2 3 4 5

x
Which predictors are possible? Linear functions
Hypothesis class F = {fw (x) = w · φ(x)}, φ(x) = [1, x]

How good is a predictor? Squared loss

Loss function Loss(x, y, w) = (fw (x) − y)2

How to compute best predictor? Gradient descent

Optimization algorithm w ← w − η∇TrainLoss(w)
CS221 22
• In this module, we have gone through the basics of linear regression. A learning algorithm takes training data and produces a predictor f ,
which can then be used to make predictions on new inputs.
• Then we addressed the three design decisions:
• First, what is the hypothesis class (the space of allowed predictors)? We focused on linear functions, but we will later see how this can be
generalized to other feature extractors to yield non-linear functions, and beyond that, neural networks.
• Second, how do we assess how good a given predictor is with respect to the training data? For this we used the squared loss, which gives us
least squares regression. We will see later how other losses allow us to handle problems such as classification.
• Third, how do we compute the best predictor? We described the simplest procedure, gradient descent. Later, we will see how stochastic
gradient descent can be much more computational efficient.
• And that concludes this module.
Machine learning: linear classification
• We now present linear (binary) classification, working through a simple example just like we did for linear regression.
 Linear classification framework
3

2
training data decision boundary
[2, 0] input 1
x1 x2 y

x2
example 0
0 2 1 learning algorithm
example f classifier
-1
-2 0 1
example
1 -1 -1 -2
-1 label -3
-3 -2 -1 0 1 2 3

x1

Design decisions:
Which classifiers are possible? hypothesis class
How good is a classifier? loss function
How do we compute the best classifier? optimization algorithm
CS221 2
• Here is the linear classification framework.
• As usual, we are given training data, which consists of a set of examples. Each example consists of an input x = (x1 , x2 ) and an output
y. We are considering two-dimensional inputs now to make the example a bit more interesting. The examples can be plotted, with the color
denoting the label (orange for +1 and blue for -1).
• We still want a learning algorithm that takes the training data and produces a model f , which we will call a classifier in the context of
classification.
• The classifier takes a new input and produces an output. We can visualize a classifier on the 2D plot by its decision boundary, which divides
the input space into two regions: the region of input points that the classifier would output +1 and the region that the classifier would output
−1. By convention, the arrow points to the positive region.
• Again, there are the same three design decisions to fully specify the learning algorithm:
• First, which classifiers f is the learning algorithm allowed to produce? Must the decision boundary be straight or can it curve? In other words,
what is the hypothesis class?
• Second, how does the learning algorithm judge which classifier is good? In other words, what is the loss function?
• Finally, how does the learning algorithm actually find the best classifier? In other words, what is the optimization algorithm?
 An example linear classifier
3

w φ(x) 2
z }| { z }| {
f (x) = sign([−0.6, 0.6] · [x1 , x2 ]) 1

x2
0
 x1 x2 f (x) -1
+1 if z > 0

0 2 1
sign(z) = −1 if z < 0 -2
 -2 0 1
0 if z = 0

-3
1 -1 -1 -3 -2 -1 0 1 2 3

x1

f ([0, 2]) = sign([−0.6, 0.6] · [0, 2]) = sign(1.2) = 1

f ([−2, 0]) = sign([−0.6, 0.6] · [−2, 0]) = sign(1.2) = 1
f ([1, −1]) = sign([−0.6, 0.6] · [1, −1]) = sign(−1.2) = −1

Decision boundary: x such that w · φ(x) = 0

CS221 4
• Before we talk about the hypothesis class over all classifiers, we will start by exploring the properties of a specific linear classifier.
• First take the dot product between a fixed weight vector w and the identity feature vector φ(x). Then take the sign of the dot product.
• The sign of a number z is +1 if z > 0 and −1 if z < 0 and 0 if z = 0.
• Let’s now visualize what f does. First, we can plot w either as a point or as a vector from the origin to that point; the latter will be most
useful for our purposes.
• Let’s feed some inputs into f .
• Take the first point, which can be visualized on the plot as a vector. Recall from linear algebra that the dot product between two vectors is
the cosine of the angle between them. In particular, the dot product is positive iff the angle is acute and negative iff the angle is obtuse. The
first point forms an acute angle and therefore is classified as +1, which can also be verified mathematically.
• The second point also forms an acute angle and therefore is classified as +1.
• The third point forms an obtuse angle and is classified as −1.
• Now you can hopefully see the pattern now. All points in this region (consisting of points forming an acute angle) will be classified +1, and
all points in this region (consisting of points forming an obtuse angle) will be classified −1.
• Points x which form a right angle (w · φ(x) = 0) form the decision boundary.
• Indeed, you can see pictorially that the decision boundary is perpendicular to the weight vector.
 Hypothesis class: which classifiers?
3

1
φ(x) = [x1 , x2 ]

x2
0
f (x) = sign([−0.6, 0.6] · φ(x)) -1

f (x) = sign([0.5, 1] · φ(x)) -2

-3
-3 -2 -1 0 1 2 3

x1

General binary classifier:

fw (x) = sign(w · φ(x))
Hypothesis class:
F = {fw : w ∈ R2 }

CS221 6
• We’ve looked at one particular red classifier.
• We can also consider an alternative purple classifer, which has a different decision boundary.
• In general for binary classification, given a particular weight vector w we define fw to be the sign of the dot product.
 Loss function: how good is a classifier?
3

2
training data Dtrain
1

x1 x2 y

x2
fw (x) = w · φ(x) 0
w = [0.5, 1] 0 2 1 -1
φ(x) = [x1 , x2 ]
-2 0 1
-2
1 -1 -1
-3
-3 -2 -1 0 1 2 3

x1

Loss0-1 (x, y, w) = 1[fw (x) 6= y] zero-one loss

Loss([0, 2], 1, [0.5, 1]) = 1[sign([0.5, 1] · [0, 2]) 6= 1] = 0
Loss([−2, 0], 1, [0.5, 1]) = 1[sign([0.5, 1] · [−2, 0]) 6= 1] = 1
Loss([1, −1], −1, [0.5, 1]) = 1[sign([0.5, 1] · [1, −1]) 6= −1] = 0

TrainLoss([0.5, 1]) = 0.33

CS221 8
• Now we proceed to the second design decision: the loss function, which measures how good a classifier is.
• Let us take the purple classifier, which can be visualized on the graph, as well as the training examples.
• Now we want to define a loss function that captures how the model predictions deviate from the data. We will define the zero-one loss to
check if the model prediction fw (x) disagrees with the target label y. If so, then the indicator function 1[fw (x) 6= y] will return 1; otherwise,
it will return 0.
• Let’s see this classifier in action.
• For the first training example, the prediction is 1, the target label is 1, so the loss is 0.
• For the second training example, the prediction is -1, the target label is 1, so the loss is 1.
• For the third training example, the prediction is -1, the target label is -1, so the loss is 0.
• The total loss is simply the average over all the training examples, which yields 1/3.
 Score and margin
3

Predicted label: fw (x) = sign(w · φ(x))

x2
0

-1
Target label: y -2

-3
-3 -2 -1 0 1 2 3

x1

Definition: score

The score on an example (x, y) is w · φ(x), how confident we are

in predicting +1.

Definition: margin

The margin on an example (x, y) is (w · φ(x))y, how correct we

are.
CS221 [score,margin] 10
• Before we move to the third design decision (optimization algorithm), let us spend some time understanding two concepts so that we can
rewrite the zero-one loss.
• Recall the definition of the predicted label and the target label.
• The first concept, which we already have encountered is the score. In regression, this is the predicted output, but in classification, this is the
number before taking the sign.
• Intuitively, the score measures how confident the classifier is in predicting +1.
• Points farther away from the decision boundary have larger scores.
• The second concept is margin, which measures how correct the prediction is. The larger the margin the more correct, and non-positive
margins correspond to classification errors. If y = 1, then the score needs to be very positive for a large margin. If y = −1, then the score
needs to be very negative for a large margin.
• Note that if we look at the actual prediction fw (x), we can only ascertain whether the prediction was right or not.
• By looking at the score and the margin, we can get a more nuanced view into the behavior of the classifier.
 Zero-one loss rewritten
4

Loss(x, y, w)
Definition: zero-one loss 3

2
Loss0-1 (x, y, w) = 1[fw (x) 6= y]
1
= 1[(w · φ(x))y ≤ 0]
| {z }
margin 0
-3 -2 -1 0 1 2 3

margin (w · φ(x))y

CS221 12
• Now let us rewrite the zero-one loss in terms of the margin.
• We can also plot the loss against the margin.
• Again, a positive margin yields zero loss while a non-positive margin yields loss 1.
 Optimization algorithm: how to compute best?
Goal: minw TrainLoss(w)
To run gradient descent, compute the gradient:
1
P
∇w TrainLoss(w) = |Dtrain | (x,y)∈Dtrain ∇Loss0-1 (x, y, w)

∇w Loss0-1 (x, y, w) = ∇1[(w · φ(x))y ≤ 0]

4
Loss(x, y, w)

2
Gradient is zero almost everywhere!
1

0
-3 -2 -1 0 1 2 3

margin (w · φ(x))y
CS221 14
• Now we consider the third design decision, the optimization algorithm for minimizing the training loss.
• Let’s just go with gradient descent. Recall that to run gradient descent, we need to first compute the gradient.
• The gradient of the training loss is just the average over the per-example losses. And then we need to take the gradient of indicator function...
• But this is where we run into problems: recall that the zero-one loss is flat almost everywhere (except at margin = 0), so the gradient is zero
almost everywhere.
• If you try running gradient descent on a function with zero gradient, you will be stuck.
• One’s first reaction to why the zero-one loss is hard to optimize is that it is not differentiable (everywhere). However, that is not really the
real reason. The real reason is because it has zero gradients.
 Hinge loss
4

Loss(x, y, w)
3
Loss0-1
2
Losshinge
1

0
-3 -2 -1 0 1 2 3

margin (w · φ(x))y

Losshinge (x, y, w) = max{1 − (w · φ(x))y, 0}

CS221 16
• To fix this problem, we have to choose another loss function.
• A popular loss function is the hinge loss, which is the maximum over a descending line and the zero function. It is best explained visually.
• If the margin is at least 1, then the hinge loss is zero.
• If the margin is less than 1, then the hinge loss rises linearly.
• The 1 is there to provide some buffer: we ask the classifier to predict not only correctly, but by a (positive) margin of safety.
• Aside: Technically, the 1 can be any positive number. If we have regularization, it is equivalent to setting the regularization strength.
• Also note that the hinge loss is an upper bound on the zero-one loss, so driving down the hinge loss will generally drive down the zero-one
loss. In particular, if the hinge loss is zero, the zero-one loss must also be zero.
 Digression: logistic regression
Losslogistic (x, y, w) = log(1 + e−(w·φ(x))y )
4

Loss(x, y, w)
3
Loss0-1
2 Losshinge
1
Losslogistic

0
-3 -2 -1 0 1 2 3

margin (w · φ(x))y
Intuition: Try to increase margin even when it already exceeds 1

CS221 18
• Another popular loss function used in machine learning is the logistic loss.
• The main property of the logistic loss is no matter how correct your prediction is, you will have non-zero loss, and so there is still an incentive
(although a diminishing one) to push the loss down by increasing the margin.
 Gradient of the hinge loss
4

Loss(x, y, w)
3

2 Losshinge
1

0
-3 -2 -1 0 1 2 3

margin (w · φ(x))y

Losshinge (x, y, w) = max{1 − (w · φ(x))y, 0}

(
−φ(x)y if {1 − (w · φ(x))y} > {0}
∇Losshinge (x, y, w) =
0 otherwise

CS221 20
• You should try to ”see” the solution before you write things down formally. Pictorially, it should be evident: when the margin is less than 1,
then the gradient is the gradient of 1 − (w · φ(x))y, which is equal to(−φ(x)y. If the margin is larger than 1, then the gradient is the gradient
−φ(x)y if (w · φ(x))y < 1
of 0, which is 0. Combining the two cases: ∇w Losshinge (x, y, w) =
0 if (w · φ(x))y > 1.
• What about when the margin is exactly 1? Technically, the gradient doesn’t exist because the hinge loss is not differentiable there. But in
practice, you can take either −φ(x)y or 0.
• Technical note (can be skipped): given f (w), the gradient ∇f (w) is only defined at points w where f is differentiable. However, subdiffer-
entials ∂f (w) are defined at every point (for convex functions). The subdifferential is a set of vectors called subgradients z ∈ f (w) which
define linear underapproximations to f , namely f (w) + z · (w0 − w) ≤ f (w0 ) for all w0 .
 Hinge loss on training data
3

2
training data Dtrain
1

x1 x2 y

x2
fw (x) = w · φ(x) 0
w = [0.5, 1] 0 2 1 -1
φ(x) = [x1 , x2 ]
-2 0 1
-2
1 -1 -1
-3
-3 -2 -1 0 1 2 3

x1

Losshinge (x, y, w) = max{1 − (w · φ(x))y, 0}

Loss([0, 2], 1, [0.5, 1]) = max{1 − [0.5, 1] · [0, 2](1), 0} = 0 ∇Loss([0, 2], 1, [0.5, 1]) = [0, 0]
Loss([−2, 0], 1, [0.5, 1]) = max{1 − [0.5, 1] · [−2, 0](1), 0} = 2 ∇Loss([−2, 0], 1, [0.5, 1]) = [2, 0]
Loss([1, −1], −1, [0.5, 1]) = max{1 − [0.5, 1] · [1, −1](−1), 0} = 0.5 ∇Loss([1, −1], −1, [0.5, 1]) = [1, −1]
TrainLoss([0.5, 1]) = 0.83 ∇TrainLoss([0.5, 1]) = [1, −0.33]

CS221 22
• Now let us revisit our earlier setting with the hinge loss.
• For each example (x, y), we can compute its loss, and the final loss is the average.
• For the first example, the loss is zero, and therefore the gradient is zero.
• For the second example, the loss is non-zero which is expected since the classifier is incorrect. The gradient is non-zero.
• For the third example, note that the loss is non-zero even though the classifier is correct. This is because we have to have a margin of 1, but
the margin in this case is only 0.5.
 Gradient descent (hinge loss) in Python

[code]

CS221 24
• Let us start from the regression code and change the loss function.
• Note that we don’t have to modify the optimization algorithm at all, a benefit of decoupling the objective function from the optimization
algorithm.
 Summary so far
w · φ(x)
| {z }
score

Regression Classification

Prediction fw (x) score sign(score)

Relate to target y residual (score − y) margin (score y)

zero-one
squared
Loss functions hinge
absolute deviation
logistic

Algorithm gradient descent gradient descent

CS221 26
• Let us end by comparing and contrasting linear classification and linear regression.
• The score is a common quantity that drives the prediction in both cases.
• In regression, the output is the raw score. In classification, the output is the sign of the score.
• To assess whether the prediction is correct, we must relate the score to the target y. In regression, we use the residual, which is the difference
(lower is better). In classification, we use the margin, which is the product (higher is better).
• Given these two quantities, we can form a number of different loss functions. In regression, we studied the squared loss, but we could also
consider the absolute deviation loss (taking absolute values instead of squared). In classification, we care about the zero-one loss (which
corresponds to the missclassification rate), but we optimize the hinge or the logistic loss.
• Finally, gradient descent can be used in both settings.
Machine learning: stochastic gradient descent
• In this module, we will introduce stochastic gradient descent.
 Gradient descent is slow
1 X
TrainLoss(w) = Loss(x, y, w)
|Dtrain |
(x,y)∈Dtrain

Algorithm: gradient descent

Initialize w = [0, . . . , 0]
For t = 1, . . . , T :
w ← w − η∇w TrainLoss(w)

Problem: each iteration requires going over all training examples — expensive when have lots
of data!

CS221 2
• So far, we’ve seen gradient descent as a general-purpose algorithm to optimize the training loss.
• But one problem with gradient descent is that it is slow.
• Recall that the training loss is a sum over the training data. If we have one million training examples, then each gradient computation requires
going through those one million examples, and this must happen before we can make any progress.
• Can we make progress before seeing all the data?
 Stochastic gradient descent
1 X
TrainLoss(w) = Loss(x, y, w)
|Dtrain |
(x,y)∈Dtrain

Algorithm: stochastic gradient descent

Initialize w = [0, . . . , 0]
For t = 1, . . . , T :
For (x, y) ∈ Dtrain :
w ← w − η∇w Loss(x, y, w)

CS221 4
• The answer is stochastic gradient descent (SGD).
• Rather than looping through all the training examples to compute a single gradient and making one step, SGD loops through the examples
(x, y) and updates the weights w based on each example.
• Each update is not as good because we’re only looking at one example rather than all the examples, but we can make many more updates
this way.
• Aside: there is a continuum between SGD and GD called minibatch SGD, where each update consists of an average over B examples.
• Aside: There are other variants of SGD. You can randomize the order in which you loop over the training data in each iteration. Think about
why this is important if in your training data, you had all the positive examples first and the negative examples after that.
 Step size
w←w− η ∇w Loss(x, y, w)
|{z}
step size

Question: what should η be?

0 1
η
conservative, more stable aggressive, faster

Strategies:
• Constant: η = 0.1
√
• Decreasing: η = 1/ # updates made so far

CS221 6
• One remaining issue is choosing the step size, which in practice is quite important.
• Generally, larger step sizes are like driving fast. You can get faster convergence, but you might also get very unstable results and crash and
burn.
• On the other hand, with smaller step sizes you get more stability, but you might get to your destination more slowly. Note that the weights
do not change if η = 0
• A suggested form for the step size is to set the initial step size to 1 and let the step size decrease as the inverse of the square root of the
number of updates we’ve taken so far.
• Aside: There are more sophisticated algorithms like AdaGrad and Adam that adapt the step size based on the data, so that you don’t have
to tweak it as much.
• Aside: There are some nice theoretical results showing that SGD is guaranteed to converge in this case (provided all your gradients are
bounded).
 Stochastic gradient descent in Python

[code]

CS221 8
• Now let us code up stochastic gradient descent for linear regression in Python.
• First we generate a large enough dataset so that speed actually matters. We will also generate 1 million points according to x ∼ N (0, I) and
y ∼ N (w∗ · x, 1), where w∗ is the true weight vector, but hidden to the algorithm.
• This way, we can diagnose whether the algorithm is actually working or not by checking whether it recovers something close to w∗ .
• Let’s first run gradient descent, and watch that it makes progress but it is very slow.
• Now let us implement stochastic gradient descent. It is much faster.
 Summary
1 X
TrainLoss(w) = Loss(x, y, w)
|Dtrain |
(x,y)∈Dtrain

gradient descent stochastic gradient descent

Key idea: stochastic updates

It’s not about quality, it’s about quantity.

CS221 10
• In summary, we’ve shown how stochastic gradient descent can be faster than gradient descent.
• Gradient just spends too much time refining its gradient (quality), while you can get a quick and dirty estimate just from one sample and
make more updates (quantity).
• Of course, sometimes stochastic gradient descent can be unstable, and other techniques such as mini-batching can be used to stabilize it.
Machine learning: group DRO
• Thus far, we have focused on finding predictors that minimize the training loss, which is an average (of the loss) over the training examples.
• While averaging seems reasonable, in this module, I’ll show that averaging can be problematic and lead to inequalities in accuracy across
groups.
• Then I’ll briefly present an approach called group distributional robust optimization (group DRO), which can mitigate some of these
inequalities.
 [Buolamwini & Gebru 2018]

Gender Shades

Inequalities arise in machine learning

CS221 2
• is the Gender Shades project by Joy Buolamwini and Timnit Gebru (paper).
• In this project, they collected an evaluation dataset of face images, which aimed to have balanced representation of both faces with lighter
and darker skin tones, and across men and women. To do this they curated the public face images from members of parliament across several
African and European countries.
• Then, they evaluated three commercial systems, from Microsoft, Face++, and IBM, on the task of gender classification (which in itself maybe
a dubious task, but was one of the services offered by these companies).
• The results were striking: all three systems got nearly 100% accuracy for lighter-skinned males, but they all got much worse accuracy for
darker-skinned females.
• Gender Shades is just one of many examples pointing at a general and systemic problem: machine learning models, which are typically
optimized to maximize average accuracy, can yield poor accuracies for certain groups (subpopulations).
• These groups can be defined by protected classes as given by discrimination law such as race and gender, or perhaps defined by the user
identity or location.
 [from a New York Times article]

False arrest due to facial recognition

Real-life consequences

CS221 4
• Poor accuracy of machine learning systems can have serious real-life consequences. In one vivid case, a Black man by the name of Robert
Julian-Borchak Williams was wrongly arrested due to a incorrect match with another Black man captured from a surveillance video, and this
mistake was made by a facial recognition system.
• Given the Gender Shades project, we can see that lower accuracies for some groups might even lead to more arrests, which adds to the already
problematic inequalities that exist in our society today.
• In this module, we’ll focus only on performance disparities in machine learning and how we can mitigate them.
• But even if facial recognition worked equally well for all groups of people, should it even be used for law enforcement? Should it be used at
all? These are bigger ethical questions, and it’s always important to remember that sometimes, the issue is not with the solution, but the
framing of the problem itself.
 Linear regression with groups
training data 8
group 7
x y g
example 3 input 6
1 4 A
5
example
2 8 A 4

y
example learning algorithm
5 5 B f predictor 3
6 6 B 2

7 7 B 3.27 output
1
0
8 8 B 0 1 2 3 4 5 6 7 8

fw (x) = w · φ(x) w = [w] φ(x) = [x]

Note: predictor fw does not use group information g

CS221 6
• Gender Shades was an example of classification, but to make things simpler, let us consider linear regression.
• We start with training data, but this time, each example consists of not only the input x and the output y, but also a group g (e.g., gender).
• In this example, we will assume we have two groups, A and B. As we see on the plot, the A points rise quickly, and the B points lie on the
identity line, so the points behave differently.
• Recall the goal of regression is to produce a predictor that can take in a new input and predict an output.
• In linear regression, each predictor fw computes the dot product of the weight vector w and a feature vector φ(x), and for this example, we
define the feature map φ(x) to be the identity map, so that our hypothesis class consists of lines that pass through the origin.
• Looking ahead a bit, we see that there is a bit of a tension, where what slope w is best for group A is not the same as what is best for group
B. The question is how we can compromise.
• Note that in this setting, the predictor fw does not use the group information g, so it cannot explicitly specialize to the different groups. The
group information is only used by the learning algorithm as well as to evaluate the performance across different groups.
 Average loss
Loss(x, y, w) = (fw (x) − y)2
80

TrainLoss
x y g 60
1 4 A

loss
2 8 A 40
5 5 B
6 6 B 20
7 7 B
8 8 B 0
0 1 2

w
1 X
TrainLoss(w) = Loss(x, y, w)
|Dtrain |
(x,y)∈Dtrain

TrainLoss(1) = 16 ((1 − 4)2 + (2 − 8)2 + (5 − 5)2 + (6 − 6)2 + (7 − 7)2 + (8 − 8)2 ) = 7.5

CS221 8
• Recall that in regression, we typically use the squared loss, which measures how far away the prediction fw (x) is away from the target y.
• Also recall that we defined the training loss to be an average of the per-example losses. This gives us a loss value for each value of w (see
plot).
• So if we evaluate the training loss at w = 1, we’re averaging over the 6 examples. For each example, the prediction fw (x) is just x (since
w · φ(x) = [1] · [x] = x, so we can average the squared differences between x and y, producing a final answer of 7.5.
• If you evaluate w at a different value, you get a different training loss.
• If we minimize the training loss, then we can find this point w = 1.09.
 Per-group loss
80

TrainLossA
x y g 60
1 4 A
TrainLossB

loss
2 8 A 40
5 5 B
6 6 B 20
7 7 B
8 8 B 0
0 1 2

w
1 X
TrainLossg (w) = Loss(x, y, w)
|Dtrain (g)|
(x,y)∈Dtrain (g)

TrainLossA (1) = 12 ((1 − 4)2 + (2 − 8)2 ) = 22.5

TrainLossB (1) = 14 ((5 − 5)2 + (6 − 6)2 + (7 − 7)2 + (8 − 8)2 ) = 0

CS221 10
• Let us now take a careful look at the loss of each group.
• First, define Dtrain (g) to be the set of examples in group g. For example, Dtrain (A) = {(1, 4), (2, 8)}.
• Then define the per-group loss TrainLossg of a weight vector w to be the average loss over the points in group g.
• If we choose w = [1] as our running example (because it’s easy to compute), we see that the per-group loss on group A is 22.5, while the
per-group loss on group B is 0.
• So note that even though the average loss was only 7.5, there is a huge performance disparity, with group A suffering a much larger loss.
 Maximum group loss
80

TrainLossA
x y g 60
TrainLossB
1 4 A
TrainLossmax

loss
2 8 A 40
5 5 B
6 6 B 20
7 7 B
8 8 B 0
0 1 2

TrainLossmax (w) = max TrainLossg (w)

g

TrainLossA (1) = 22.5

TrainLossB (1) = 0
TrainLossmax (1) = max(22.5, 0) = 22.5

CS221 12
• We now want to somehow capture the per-group losses by one number. To do this, we look at the worst-case over groups.
• We now define the maximum group loss to be the largest over all groups. This function is the pointwise maximum of the per-group losses,
which you can see on the plot as taking the upper envelope of the two per-group losses.
• We call this method group distributionally robust optimization (group DRO), because it is a special case of a broader framework Distributionally
robust optimization (DRO).
• Going back to our running example with w = [1], we take the maximum of 22.5 and 0, which is 22.5.
• Note that this is much higher than the average loss (7.5), signaling that some group(s) are far less well off than the average.
 Average loss versus maximum group loss
80
8
TrainLoss 7
x y g 60
1 4 A
TrainLossmax 6
5

loss
2 8 A 40
4

y
5 5 B
3
6 6 B 20
2
7 7 B
1
8 8 B 0
0 1 2 0
0 1 2 3 4 5 6 7 8
w
x

Standard learning:
minimizer of average loss: w = 1.09
Group distributionally robust optimization (group DRO):
CS221 minimizer of maximum group loss: w = 1.58 14
• Let us now compare the old average loss (the standard training loss) TrainLoss and the new maximum group loss TrainLossmax .
• We minimize the average loss by setting the slope w = [1.09], yielding an average loss of 7.29. However, this setting gets much higher
maximum group loss (over 20). Pictorially, we see that this w heavily favors the majority group (B).
• If instead we minimize the maximum group loss directly, we would choose w = 1.58, yielding a maximum group loss of 15.59. Pictorially, we
see that this solution pays more attention to (is closer to) the A points.
• Intuitively, the average loss favors majority groups over minority groups, but the maximum group loss gives a stronger voice to the minority
groups, and as we see here, their influence is felt to a greater extent.
 Training via gradient descent
80

TrainLossA
x y g 60
TrainLossB
1 4 A
TrainLossmax

loss
2 8 A 40
5 5 B
6 6 B 20
7 7 B
8 8 B 0
0 1 2

TrainLossmax (w) = max TrainLossg (w)

g

∇TrainLossmax (w) = ∇TrainLossg∗ (w)

where g ∗ = arg max TrainLossg (w)
g

CS221 16
• In general, we can find minimize the maximum group loss by gradient descent.
• We just have to be able to take the gradient of TrainLossmax , which is a maximum over the per-group losses.
• The gradient of a max is simply the gradient of the term that achieves the max.
• So algorithmically, it’s very intuitive: you first compute whichever group (g ∗ ) has the highest loss, and then you just evaluate the gradient
only on per-group loss of that group (g ∗ ).
• but you can see this paper for more details.
 Summary
80
8
TrainLoss 7
x y g 60
1 4 A
TrainLossmax 6
5

loss
2 8 A 40
4

y
5 5 B
3
6 6 B 20
2
7 7 B
1
8 8 B 0
0 1 2 0
0 1 2 3 4 5 6 7 8
w
x

• Maximum group loss 6= average loss

• Group DRO: minimize the maximum group loss
• Many more nuances: intersectionality? don’t know groups? overfitting?

CS221 18
• To summarize, we’ve introduced the setting where examples are associated with groups. We see that by default, doing well on average is not
the same as doing well on all groups (in other words, average loss is not the same as the maximum group loss), and the optimal solution for
one objective is not optimal for the other objective.
• We presented an approach, group DRO that can ensure that the worst-off group is doing well.
• One parting remark is that while group DRO offers a mathematically clean solution, there are many subtleties when applying this to the real
world. Intersectionality refers to the fact that groups which are defined by the conjunction of multiple attributes (e.g., White woman) may
behave differently than the groups defined by individual attributes. What if you don’t even have group information? How do you deal with
overfitting (we’ve only looked at the training loss)?
• These are questions that are beyond the scope of this module, but I hope this short module has raised the need to think about about inequality
as a first-class citizen, and piqued your interest to learn more.
• For further reading, consider checking out the book Fairness and machine learning: Limitations and Opportunities,
Machine learning: non-linear features
• In this module, we’ll show that even using the machinery of linear models, we can obtain much more powerful non-linear predictors.
 Linear regression
training data
3
x y
1 1 learning algorithm
Which predictors are possible?
f predictor
2 3 Hypothesis class
4 3
2.71

F = {fw (x) = w · φ(x) : w ∈ Rd }

4

3
φ(x) = [1, x]
2

y
f (x) = [1, 0.57] · φ(x)
1

f (x) = [2, 0.2] · φ(x) 0

0 1 2 3 4 5

CS221 2
• We will look at regression and later turn to classification.
• Recall that in linear regression, given training data, a learning algorithm produces a predictor that maps new inputs to new outputs. The first
design decision: what are the possible predictors that the learning algorithm can consider (what is the hypothesis class)?
• For linear predictors, remember the hypothesis class is the set of predictors that map some input x to the dot product between some weight
vector w and the feature vector φ(x).
• As a simple example, if we define the feature extractor to be φ(x) = [1, x], then we can define various linear predictors with different intercepts
and slopes.
 More complex data
4

y
1

0
0 1 2 3 4 5

How do we fit a non-linear predictor?

CS221 4
• But sometimes data might be more complex and not be easily fit by a linear predictor. In this case, what can we do?
• One immediate reaction might be to go to something fancier like neural networks or decision trees.
• But let’s see how far we can get with the machinery of linear predictors first.
 Quadratic predictors

φ(x) = [1, x, x2 ]
Example: φ(3) = [1, 3, 9]

f (x) = [2, 1, −0.2] · φ(x) 4

3
f (x) = [4, −1, 0.1] · φ(x)
2

y
f (x) = [1, 1, 0] · φ(x)
1
3
F = {fw (x) = w · φ(x) : w ∈ R }
0
0 1 2 3 4 5

Non-linear predictors just by changing φ

CS221 6
• The key observation is that the feature extractor φ can be arbitrary.
• So let us define it to include an x2 term.
• Now, by setting the weights appropriately, we can define a non-linear (specifically, a quadratic) predictor.
• The first two examples of quadratic predictors vary in intercept, slope and curvature.
• Note that by setting the weight for feature x2 to zero, we recover linear predictors.
• Again, the hypothesis class is the set of all predictors fw obtained by varying w.
• Note that the hypothesis class of quadratic predictors is a superset of the hypothesis class of linear predictors.
• In summary, we’ve seen our first example of obtaining non-linear predictors just by changing the feature extractor φ!
• Advanced: here x ∈ R is one-dimensional, so x2 is just one additional feature. If x ∈ Rd were d-dimensional, then there would be O(d2 )
quadratic features of the form xi xj for i, j ∈ {1, . . . , d}. When d is large, then d2 can be prohibitively large, which is one reason that using
the machinery of linear predictors to increase expressivity can be problematic.
 Piecewise constant predictors

φ(x) = [1[0 < x ≤ 1], 1[1 < x ≤ 2], 1[2 < x ≤ 3], 1[3 < x ≤ 4], 1[4 < x ≤ 5]]

Example: φ(2.3) = [0, 0, 1, 0, 0]

3
f (x) = [1, 2, 4, 4, 3] · φ(x)
2

y
f (x) = [4, 3, 3, 2, 1.5] · φ(x)
1

F = {fw (x) = w · φ(x) : w ∈ R5 } 0

0 1 2 3 4 5

Expressive non-linear predictors by partitioning the input space

CS221 8
• Quadratic predictors are still a bit restricted: they can only go up and then down smoothly (or vice-vera).
• We introduce another type of feature extractor which divides the input space into regions and allows the predicted value of each region to
vary independently, yielding piecewise constant predictors (see figure).
• Specifically, each component of the feature vector corresponds to one region (e.g., [0, 1)) and is 1 if x lies in that region and 0 otherwise.
• Assuming the regions are disjoint, the weight associated with a component/region is exactly the predicted value.
• As you make the regions smaller, then you have more features, and the expressivity of your hypothesis class increases. In the limit, you can
essentially capture any predictor you want.
• Advanced: what happens if x were not a scalar, but a d-dimensional vector? Then if each component gets broken up into B bins, then there
will be B d features! For each feature, we need to fit its weight, and there will in generally be too few examples to fit all the features.
 Predictors with periodicity structure

φ(x) = [1, x, x2 , cos(3x)]

Example: φ(2) = [1, 2, 4, 0.96]

3
f (x) = [1, 1, −0.1, 1] · φ(x)
2

y
f (x) = [3, −1, 0.1, 0.5] · φ(x)
1
F = {fw (x) = w · φ(x) : w ∈ R4 }
0
0 1 2 3 4 5

Just throw in any features you want

CS221 10
• Quadratic and piecewise constant predictors are just two examples of an unboundedly large design space of possible feature extractors.
• Generally, the choice of features is informed by the prediction task that we wish to solve (either prior knowledge or preliminary data exploration).
• For example, if x represents time and we believe the true output y varies according to some periodic structure (e.g., traffic patterns repeat
daily, sales patterns repeat annually), then we might use periodic features such as cosine to capture these trends.
• Each feature might represent some type of structure in the data. If we have multiple types of structures, these can just be ”thrown in” into
the feature vector.
• Features represent what properties might be useful for prediction. If a feature is not useful, then the learning algorithm can assign a weight
close to zero to that feature. Of course, the more features one has, the harder learning becomes.
 Linear in what?
Prediction:

fw (x) = w · φ(x)

Linear in w? Yes
Linear in φ(x)? Yes
Linear in x? No!

Key idea: non-linearity

• Expressivity: score w · φ(x) can be a non-linear function of x

• Efficiency: score w · φ(x) always a linear function of w

CS221 12
• Wait a minute...how are we able to obtain non-linear predictors if we’re still using the machinery of linear predictors? It’s a linguistic sleight
of hand, as ”linear” is ambiguous.
• The score is w · φ(x) linear in w and φ(x). However, the score is not linear in x (it might not even make sense because x need not be a
vector at all — it could be a string or a PDF file).
• The significance is as follows: From the feature extractor’s viewpoint, we can define arbitrary features that yield very non-linear functions in
x.
• From the learning algorithm’s viewpoint (which only looks at φ(x), not x), linearity us to optimize the weights efficiently.
• Advanced: if the score is linear in w and the loss function Loss is convex (which holds for the squared, hinge, logistic losses but not the
zero-one loss), then minimizing the training loss TrainLoss is a convex optimization problem, and gradient descent with a proper step size is
guaranteed to converge to the global minimum.
 Linear classification

3
φ(x) = [x1 , x2 ]
2
f (x) = sign([−0.6, 0.6] · φ(x))
1

x2
0

-1

-2

-3
-3 -2 -1 0 1 2 3

x1

Decision boundary is a line

CS221 14
• Now let’s turn from regression to classification.
• The story is pretty much the same: you can define arbitrary features to yield non-linear classifiers.
• Recall that in binary classification, the classifier (predictor) returns the sign of the score.
• The classifier can be therefore be represented by its decision boundary, which divides the input space into two regions: points with positive
score and points with negative score.
• Note that the classifier fw (x) is a non-linear function of x (and φ(x)) no matter what (due to the sign function), so it is not helpful to talk
about whether fw is linear or non-linear. Instead we will ask whether the decision boundary corresponding to fw is linear or not.
 Quadratic classifiers
φ(x) = [x1 , x2 , x21 + x22 ] 3

f (x) = sign([2, 2, −1] · φ(x)) 2

1
Equivalently:(

x2
0
1 if {(x 1 − 1)2 + (x 2 − 1)2 ≤ 2}
f (x) = -1
−1 otherwise
-2

-3
-3 -2 -1 0 1 2 3

x1

Decision boundary is a circle

CS221 16
• Let us see how we can define a classifier with a non-linear decision boundary.
• Let’s try to construct a feature extractor that induces a decision boundary that is a circle: the inside is classified +1 and the outside is
classified -1.
• We will add a new feature x21 + x22 into the feature vector, and define the weights to be as follows.
√
• Then rewrite the classifier to make it clear that it is the equation for the interior of a circle with radius 2.
• As a sanity check, we you can see that x = [0, 0] results in a score of 0, which means that it is on the decision boundary. And as either of x1
or x2 grow in magnitude (either |x1 | → ∞ or |x2 | → ∞), the contribution of the third feature dominates and the sign of the score will be
negative.
 Visualization in feature space
Input space: x = [x1 , x2 ], decision boundary is a circle

Feature space: φ(x) = [x1 , x2 , x21 + x22 ], decision boundary is a line

CS221 18
• Let’s try to understand the relationship between the non-linearity in x and linearity in φ(x).
• Click on the image to see the linked video (which is about polynomial kernels and SVMs, but the same principle applies here).
• In the input space x, the decision boundary which separates the red and blue points is a circle.
• We can also visualize the points in feature space, where each point is given an additional dimension x21 + x22 .
• In this three-dimensional feature space, a linear predictor (which is now defined by a hyperplane instead of a line) can in fact separate the red
and blue points.
• This corresponds to the non-linear predictor in the original two-dimensional space.
 Summary

fw (x) = w · φ(x)
linear in w, φ(x)
non-linear in x

• Regression: non-linear predictor, classification: non-linear decision boundary

• Types of non-linear features: quadratic, piecewise constant, etc.

Non-linear predictors with linear machinery

CS221 20
• To summarize, we have shown that the term ”linear” is ambiguous: a predictor in regression is non-linear in the input x but is linear in the
feature vector φ(x).
• The score is also linear with respect to the weights w, which is important for efficient learning.
• Classification is similar, except we talk about (non-)linearity of the decision boundary.
• We also saw many types of non-linear predictors that you could create by concocting various features (quadratic predictors, piecewise constant
predictors).
• So next time someone on the street asks you about linear predictors, you should first ask them ”linear in what?”
Machine learning: feature templates
• In this module, we’ll talk about how to use feature templates to construct features in a flexible way.
 Feature extraction + learning
F = {fw (x) = sign(w · φ(x)) : w ∈ Rd }
All predictors
F
Learning
Feature extraction
fw

• Feature extraction: choose F based on domain knowledge

• Learning: choose fw ∈ F based on data

Want F to contain good predictors but not be too big

CS221 2
• Recall that the hypothesis class F is the set of predictors considered by the learning algorithm. In the case of linear predictors, F is given by
some function of w · φ(x) for all w (sign for classification, no sign for regression). This can be visualized as a set in the figure.
• Learning is the process of choosing a particular predictor fw from F given training data.
• But the question that will concern us in this module is how do we choose F? We saw some options already: linear predictors, quadratic
predictors, etc., but what makes sense for a given application?
• If the hypothesis class doesn’t contain any good predictors, then no amount of learning can help. So the question when extracting features is
really whether they are powerful enough to express good predictors. It’s okay and expected that F will contain bad ones as well. Of course,
we don’t want F to be too big, or else learning becomes hard, not just computationally but statistically (as we’ll explain when we talk about
generalization).
 Feature extraction with feature names
Example task:
classifier
string (x) valid email address? (y)
fw (x) = sign(w · φ(x))

Question: what properties of x might be relevant for predicting y?

Feature extractor: Given x, produce set of (feature name, feature value) pairs

length>10 :1
fracOfAlpha : 0.85
[email protected] feature extractor φ contains @ :1
endsWith com : 1
x arbitrary! endsWith org : 0

CS221 [features]
φ(x) 4
• To get some intuition about feature extraction, let us consider the task of predicting whether whether a string is a valid email address or not.
• We will assume the classifier fw is a linear classifier, which is given by some feature extractor φ.
• Feature extraction is a bit of an art that requires intuition about both the task and also what machine learning algorithms are capable of.
The general principle is that features should represent properties of x which might be relevant for predicting y.
• Think about the feature extractor as producing a set of (feature name, feature value) pairs. For example, we might extract information about
the length, or fraction of alphanumeric characters, whether it contains various substrings, etc.
• It is okay to add features which turn out to be irrelevant, since the learning algorithm can always in principle choose to ignore the feature,
though it might take more data to do so.
• We have been associating each feature with a name so that it’s easier for us (humans) to interpret and develop the feature extractor. The
feature names act like the analogue of comments in code. Mathematically, the feature name is not needed by the learning algorithm and
erasing them does not change prediction or learning.
 Prediction with feature names
Weight vector w ∈ Rd Feature vector φ(x) ∈ Rd
length>10 :-1.2 length>10 :1
fracOfAlpha :0.6 fracOfAlpha :0.85
contains @ :3 contains @ :1
endsWith com:2.2 endsWith com:1
endsWith org :1.4 endsWith org :0

Score: weighted combination of features

Pd
w · φ(x) = j=1 wj φ(x)j

Example: −1.2(1) + 0.6(0.85) + 3(1) + 2.2(1) + 1.4(0) = 4.51

CS221 6
• A feature vector formally is just a list of numbers, but we have endowed each feature in the feature vector with a name.
• The weight vector is also just a list of numbers, but we can endow each weight with the corresponding name as well.
• Recall that the score is simply the dot product between the weight vector and the feature vector. In other words, the score aggregates the
contribution of each feature, weighted appropriately.
• Each feature weight wj determines how the corresponding feature value φj (x) contributes to the prediction.
• If wj is positive, then the presence of feature j (φj (x) = 1) favors a positive classification (e.g., ending with com). Conversely, if wj is
negative, then the presence of feature j favors a negative classification (e.g., length greater than 10). The magnitude of wj measures the
strength or importance of this contribution.
• Advanced: while tempting, it can be a bit misleading to interpret feature weights in isolation, because the learning algorithm treats w
holistically. In particular, a feature weight wj produced by a learning algorithm will change depending on the presence of other features. If
the weight of a feature is positive, it doesn’t necessarily mean that feature is positively correlated with the label.
 Organization of features?
length>10 :1
fracOfAlpha : 0.85
[email protected] feature extractor φ contains @ :1
endsWith com : 1
x arbitrary! endsWith org : 0

φ(x)

Which features to include? Need an organizational principle...

CS221 8
• How would we go about about creating good features?
• Here, we used our prior knowledge to define certain features (contains @) which we believe are helpful for detecting email addresses.
• But this is ad-hoc, and it’s easy to miss useful features (e.g., endsWith us), and there might be other features which are predictive but not
intuitive.
• We need a more systematic way to go about this.
 Feature templates

Definition: feature template

A feature template is a group of features all computed in a similar way.

endsWith aaa : 0
endsWith aab : 0
endsWith aac : 0
[email protected] last three characters equals ...
endsWith com : 1
...
endsWith zzz : 0

Define types of pattern to look for, not particular patterns

CS221 10
• A useful organization principle is a feature template, which groups all the features which are computed in a similar way. (People often use
the word ”feature” when they really mean ”feature template”.)
• Rather than defining individual features like endsWith com, we can define a single feature template which expands into all the features that
computes whether the input x matches any three characters.
• Typically, we will write a feature template as an English description with a blank ( ), which is to be filled in with an arbitrary value.
• The upshot is that we don’t need to know which particular patterns (e.g., three-character suffixes) are useful, but only that existence of
certain patterns (e.g., three-character suffixes) are useful cue to look at.
• It is then up to the learning algorithm to figure out which patterns are useful by assigning the appropriate feature weights.
 Feature templates example 1
Input:

[email protected]

Feature template Example feature

Last three characters equals Last three characters equals com : 1
Length greater than Length greater than 10 : 1
Fraction of alphanumeric characters Fraction of alphanumeric characters : 0.85

CS221 12
• Here are some other examples of feature templates.
• Note that an isolated feature (e.g., fraction of alphanumeric characters) can be treated as a trivial feature template with no blanks to be
filled.
• In many cases, the feature value is binary (0 or 1), but they can also be real numbers.
 Feature templates example 2
Input:

Latitude: 37.4068176
Longitude: -122.1715122

Feature template Example feature name

Pixel intensity of image at row and column ( channel) Pixel intensity of image at row 10 and column 93 (red channel) : 0.8
Latitude is in [ , ] and longitude is in [ , ] Latitude is in [ 37.4, 37.5 ] and longitude is in [ -122.2, -122.1 ] : 1

CS221 14
• As another example application, suppose the input is an aerial image along with the latitude/longitude corresponding where the image was
taken. This type of input arises in poverty mapping and land cover classification.
• In this case, we might define one feature template corresponding to the pixel intensities at various pixel-wise row/column positions in the
image across all the 3 color channels (e.g., red, green, blue).
• Another feature template might define a family of binary features, one for each region of the world, where each region is defined by a bounding
box over latitude and longitude.
 Sparsity in feature vectors
endsWith a :0
endsWith b :0
endsWith c :0
endsWith d :0
endsWith e :0
endsWith f :0
endsWith g :0
endsWith h :0
endsWith i :0
endsWith j :0
endsWith k :0
endsWith l :0
endsWith m:1
[email protected] last character equals endsWith n :0
endsWith o :0
endsWith p :0
endsWith q :0
endsWith r :0
endsWith s :0
endsWith t :0
endsWith u :0
endsWith v :0
endsWith w :0
endsWith x :0
endsWith y :0
endsWith z :0

Compact representation:
CS221 {"endsWith m": 1} 16
• In general, a feature template corresponds to many features, and sometimes, for a given input, most of the feature values are zero; that is,
the feature vector is sparse.
• Of course, different feature vectors have different non-zero features.
• In this case, it would be inefficient to represent all the features explicitly. Instead, we can just store the values of the non-zero features,
assuming all other feature values are zero by default.
 Two feature vector implementations
Arrays (good for dense features): Dictionaries (good for sparse features):

pixelIntensity(0,0) : 0.8 fracOfAlpha : 0.85

pixelIntensity(0,1) : 0.6 contains a : 0
pixelIntensity(0,2) : 0.5 contains b : 0
pixelIntensity(1,0) : 0.5 contains c : 0
pixelIntensity(1,1) : 0.8 contains d : 0
pixelIntensity(1,2) : 0.7 contains e : 0
pixelIntensity(2,0) : 0.2 ...
pixelIntensity(2,1) : 0 contains @ : 1
pixelIntensity(2,2) : 0.1 ...

[0.8, 0.6, 0.5, 0.5, 0.8, 0.7, 0.2, 0, 0.1] {"fracOfAlpha": 0.85, "contains @": 1}

CS221 18
• In general, there are two common ways to implement feature vectors: using arrays and using dictionaries.
• Arrays assume a fixed ordering of the features and store the feature values as an array. This implementation is appropriate when the number
of nonzeros is significant (the features are dense). Arrays are especially efficient in terms of space and speed (and you can take advantage of
GPUs). In computer vision applications, features (e.g., the pixel intensity features) are generally dense, so arrays are more common.
• However, when we have sparsity (few nonzeros), it is typically more efficient to implement the feature vector as a dictionary (map) from
strings to doubles rather than a fixed-size array of doubles. The features not in the dictionary implicitly have a default value of zero. This
sparse implementation is useful for natural language processing with linear predictors, and is what allows us to work efficiently over millions
of features. In Python, one would define a feature vector φ(x) as the dictionary {"endsWith "+x[-3:]: 1}. Dictionaries do incur extra
overhead compared to arrays, and therefore dictionaries are much slower when the features are not sparse.
• One advantage of the sparse feature implementation is that you don’t have to instantiate all the set of possible features in advance; the weight
vector can be initialized to {}, and only when a feature weight becomes non-zero do we store it. This means we can dynamically update a
model with incrementally arriving data, which might instantiate new features.
 Summary
F = {fw (x) = sign(w · φ(x)) : w ∈ Rd }
Feature template:
endsWith aaa : 0
endsWith aab : 0
endsWith aac : 0
[email protected] last three characters equals ...
endsWith com : 1
...
endsWith zzz : 0

Dictionary implementation:
{"endsWith com": 1}

CS221 20
• The question we are concerned with in this module is to how to define the hypothesis class F, which in the case of linear predictors is the
question of what the feature extractor φ is.
• We showed how feature templates can be useful for organizing the definition of many features, and that we can use dictionaries to represent
sparse feature vectors efficiently.
• Stepping back, feature engineering is one of the most critical components in the practice of machine learning. It often does not get as much
attention as it deserves, mostly because it is a bit of an art and somewhat domain-specific.
• More powerful predictors such as neural networks will alleviate some of the burden of feature engineering, but even neural networks use feature
vectors as the initial starting point, and therefore its effectiveness is ultimately governed by how good the features are.
Machine learning: neural networks
• In this module, I will present neural networks, a way to construct non-linear predictors via problem decomposition.
 Non-linear predictors
4

Linear predictors: 2

y
1
fw (x) = w · φ(x), φ(x) = [1, x] 0
0 1 2 3 4 5

Non-linear (quadratic) predictors: 3

y
fw (x) = w · φ(x), φ(x) = [1, x, x2 ] 1

0
0 1 2 3 4 5

x
4

Non-linear neural networks: 2

y
fw (x) = w · σ(Vφ(x)), φ(x) = [1, x] 1

0
0 1 2 3 4 5

CS221 2
• Recall that our first hypothesis class was linear (in x) predictors, which for regression means that the predictors are lines.
• However, we also showed that you could get non-linear (in x) predictors by simply changing the feature extractor φ. For example, by adding
the feature x2 , one obtains quadratic predictors.
• One disadvantage of this approach is that if x were d-dimensional, one would need O(d2 ) features and corresponding weights, which presents
considerable computational and statistical challenges.
• We will show that with neural networks, we can leave the feature extractor alone, but increase the complexity of predictor, which can also
produce non-linear (though not necessarily quadratic) predictors.
• It is a common misconception that neural networks allow you to express more complex predictors. You can define φ to include essentially all
predictors (as is done in kernel methods).
• Rather, neural networks yield non-linear predictors in a more compact way. For instance, you might not need O(d2 ) features to represent the
desired non-linear predictor.
 Motivating example
Example: predicting car collision

Input: positions of two oncoming cars x = [x1 , x2 ]

Output: whether safe (y = +1) or collide (y = −1)

Unknown: safe if cars sufficiently far: y = sign(|x1 − x2 | − 1)

3

2
x1 x2 y 1
0 2 1

x2
0
2 0 1 -1

0 0 -1 -2

2 2 -1 -3
-3 -2 -1 0 1 2 3

x1
CS221 4
• As a motivating example, consider the problem of predicting whether two cars are going to collide given the their positions (as measured from
distance from one side of the road). In particular, let x1 be the position of one car and x2 be the position of the other car.
• Suppose the true output is 1 (safe) whenever the cars are separated by a distance of at least 1. This relationship can be represented by
the decision boundary which labels all points in the interior region between the two red lines as negative, and everything on the exterior (on
either side) as positive. Of course, this true input-output relationship is unknown to the learning algorithm, which only sees training data.
Consider a simple training dataset consisting of four points. (This is essentially the famous XOR problem that was impossible to fit using
linear classifiers.)
 Decomposing the problem
3

Test if car 1 is far right of car 2: 2 h2 (x)

h1 (x) = 1[x1 − x2 ≥ 1] 1

x2
0
Test if car 2 is far right of car 1:
-1
h2 (x) = 1[x2 − x1 ≥ 1]
-2 h1 (x)
Safe if at least one is true:
-3
f (x) = sign(h1 (x) + h2 (x)) -3 -2 -1 0 1 2 3

x1

x h1 (x) h2 (x) f (x)

[0, 2] 0 1 +1
[2, 0] 1 0 +1
[0, 0] 0 0 −1
[2, 2] 0 0 −1
CS221 6
• One way to motivate neural networks (without appealing to the brain) is problem decomposition.
• The intuition is to break up the full problem into two subproblems: the first subproblem tests if car 1 is to the far right of car 2; the second
subproblem tests if car 2 is to the far right of car 1. Then the final output is 1 iff at least one of the two subproblems returns 1.
• Concretely, we can define h1 (x) to be the output of the first subproblem, which is a simple linear decision boundary (in fact, the right line in
the figure).
• Analogously, we define h2 (x) to be the output of the second subproblem.
• Note that h1 (x) and h2 (x) take on values 0 or 1 instead of -1 or +1.
• The points can then be classified by first computing h1 (x) and h2 (x), and then combining the results into f (x).
 Rewriting using vector notation
Intermediate subproblems:

h1 (x) = 1[x1 − x2 ≥ 1] = 1[[−1, +1, −1] · [1, x1 , x2 ] ≥ 0]

h2 (x) = 1[x2 − x1 ≥ 1] = 1[[−1, −1, +1] · [1, x1 , x2 ] ≥ 0]

   
  1
−1 +1 −1 
h(x) = 1  x 1  ≥ 0
−1 −1 +1
x2

Predictor:

f (x) = sign(h1 (x) + h2 (x)) = sign([1, 1] · h(x))

CS221 8
• Now let us rewrite this predictor f (x) using vector notation.
• We can define a feature vector [1, x1 , x2 ] and a corresponding weight vector, where the dot product thresholded yields exactly h1 (x).
• We do the same for h2 (x).
• We put the two subproblems into one equation by stacking the weight vectors into one matrix. Recall that left-multiplication by a matrix is
equivalent to taking the dot product with each row. By convention, the thresholding at 0 (1[· ≥ 0]) applies component-wise.
• Finally, we can define the predictor in terms of a simple dot product.
• Now of course, we don’t know the weight vectors, but we can learn them from the training data!
 Avoid zero gradients
Problem: gradient of h1 (x) with respect to v1 is 0
h1 (x) = 1[v1 · φ(x) ≥ 0]

Solution: replace with an activation function σ with non-zero gradients

5

4
σ(z)

3 Threshold: 1[z ≥ 0]
1
Logistic: 1+e−z
1
ReLU: max(z, 0)
0
-5 -3 0 3 5

z = v1 · φ(x)
h1 (x) = σ(v1 · φ(x))
CS221 10
• Later we’ll show how to perform learning using gradient descent, but we can anticipate one problem, which we encountered when we tried to
optimize the zero-one loss.
• The gradient of h1 (x) with respect to v1 is always zero because of the threshold function.
• To fix this, we replace the threshold function with an activation function with non-zero gradients
• Classically, neural networks used the logistic function σ(z), which looks roughly like the threshold function but has non-zero gradients
everywhere.
• Even though the gradients are non-zero, they can be quite small when |z| is large (a phenomenon known as saturation). This makes optimizing
with the logistic function still difficult.
• In 2012, Glorot et al. introduced the ReLU activation function, which is simply max(z, 0). This has the advantage that at least on the
positive side, the gradient does not vanish (though on the negative side, the gradient is always zero). As a bonus, ReLU is easier to compute
(only max, no exponentiation). In practice, ReLU works well and has become the activation function of choice.
• Note that if the activation function were linear (e.g., the identity function), then the gradients would always be nonzero, but you would lose
the power of a neural network, because you would simply get the product of the final-layer weight vector and the weight matrix (w> V),
which is equivalent to optimizing over a single weight vector.
• Therefore, that there is a tension between wanting an activation function that is non-linear but also has non-zero gradients.
 Two-layer neural networks
Intermediate subproblems: φ(x)
h(x) V


=σ

Predictor (classification): h(x)

w

fV,w (x) = sign ·

Interpret h(x) as a learned feature representation!

Hypothesis class:
F = {fV,w : V ∈ Rk×d , w ∈ Rk }

CS221 12
• Now we are finally ready to define the hypothesis class of two-layer neural networks.
• We start with a feature vector φ(x).
• We multiply it by a weight matrix V (whose rows can be interpreted as the weight vectors of the k intermediate subproblems.
• Then we apply the activation function σ to each of the k components to get the hidden representation h(x) ∈ Rk .
• We can actually interpret h(x) as a learned feature vector (representation), which is derived from the original non-linear feature vector φ(x).
• Given h(x), we take the dot product with a weight vector w to get the score used to drive either regression or classification.
• The hypothesis class is the set of all such predictors obtained by varying the first-layer weight matrix V and the second-layer weight vector
w.
 Deep neural networks
1-layer neural network: φ(x)
w
score = ·

2-layer neural network: φ(x)

V
w  
score = ·σ

3-layer neural network: φ(x)

V2 V1
w   
score = ·σ σ

CS221 14
• We can push these ideas to build deep neural networks, which are neural networks with many layers.
• Warm up: for a one-layer neural network (a.k.a. a linear predictor), the score that drives prediction is simply a dot product between a weight
vector and a feature vector.
• We just saw for a two-layer neural network, we apply a linear layer V first, followed by a non-linearity σ, and then take the dot product.
• To obtain a three-layer neural network, we apply a linear layer and a non-linearity (this is the basic building block). This can be iterated any
number of times. No matter now deep the neural network is, the top layer is always a linear function, and all the layers below that can be
interpreted as defining a (possibly very complex) hidden feature vector.
• In practice, you would also have a bias term (e.g., Vφ(x) + b). We have omitted all bias terms for notational simplicity.
[figure from Honglak Lee]

Layers represent multiple levels of abstractions

CS221 16
• It can be difficult to understand what a sequence of (matrix multiply, non-linearity) operations buys you.
• To provide intuition, suppose the input feature vector φ(x) is a vector of all the pixels in an image.
• Then each layer can be thought of producing an increasingly abstract representation of the input. The first layer detects edges, the second
detects object parts, the third detects objects. What is shown in the figure is for each component j of the hidden representation h(x), the
input image φ(x) that maximizes the value of hj (x).
• Though we haven’t talked about learning neural networks, it turns out that the ”levels of abstraction” story is actually borne out visually
when we learn neural networks on real data (e.g., images).
 Why depth?
φ(x)
h1 (x) h2 (x) h3 (x) h4 (x)
score

Intuitions:

• Multiple levels of abstraction

• Multiple steps of computation

• Empirically works well

• Theory is still incomplete

CS221 18
• Beyond learning hierarchical feature representations, deep neural networks can be interpreted in a few other ways.
• One perspective is that each layer can be thought of as performing some computation, and therefore deep neural networks can be thought of
as performing multiple steps of computation.
• But ultimately, the real reason why deep neural networks are interesting is because they work well in practice.
• From a theoretical perspective, we have a quite an incomplete explanation for why depth is important. The original motivation from
McCulloch/Pitts in 1943 showed that neural networks can be used to simulate a bounded computation logic circuit. Separately it has been
shown that depth k + 1 logic circuits can represent more functions than depth k. However, neural networks are real-valued and might have
types of computations which don’t fit neatly into logical paradigm. Obtaining a better theoretical understanding is an active area of research
in statistical learning theory.
 Summary
φ(x)
V
w
score = · σ( )

• Intuition: decompose problem into intermediate parallel subproblems

• Deep networks iterate this decomposition multiple times

• Hypothesis class contains predictors ranging over weights for all layers

• Next up: learning neural networks

CS221 20
• To summarize, we started with a toy problem (the XOR problem) and used it to motivate neural networks, which decompose a problem into
intermediate subproblems, which are solved in parallel.
• Deep networks iterate this multiple times to build increasingly high-level representations of the input.
• Next, we will see how we can learn a neural network by choosing the weights for all the layers.
Machine learning: backpropagation
• In this module, I’ll discuss backpropagation, an algorithm to automatically compute gradients.
• It is generally associated with training neural networks, but actually it is much more general and applies to any function.
 Motivation: regression with four-layer neural networks
Loss on one example:
Loss(x, y, V1 , V2 , V3 , w) = (w · σ(V3 σ(V2 σ(V1 φ(x)))) − y)2

Stochastic gradient descent:

V1 ← V1 − η∇V1 Loss(x, y, V1 , V2 , V3 , w)
V2 ← V2 − η∇V2 Loss(x, y, V1 , V2 , V3 , w)
V3 ← V3 − η∇V3 Loss(x, y, V1 , V2 , V3 , w)
w ← w − η∇w Loss(x, y, V1 , V2 , V3 , w)

How to get the gradient without doing manual work?

CS221 2
• So far, we’ve defined neural networks, which take an initial feature vector φ(x) and sends it through a sequence of matrix multiplications and
non-linear activations σ. At the end, we take the dot product between a weight vector w to produce the score.
• In regression, we predict the score, and use the squared loss, which looks at the squared difference betwen the score and the target y.
• Recall that we can use stochastic gradient descent to optimize the training loss (which is an average over the per-example losses). Now, we
need to update all the weight matrices, not just a single weight vector. This can be done by taking the gradient with respect to each weight
vector/matrix separately, and updating the respective weight vector/matrix by subtracting the gradient times a step size η.
• We can now proceed to take the gradient of the loss function with respect to the various weight vector/matrices. You should know how to
do this: just apply the chain rule. But grinding through this complex expression by hand can be quite tedious. If only we had a way for this
to be done automatically for us...
 Computation graphs
Loss(x, y, V1 , V2 , V3 , w) = (w · σ(V3 σ(V2 σ(V1 φ(x)))) − y)2

Definition: computation graph

A directed acyclic graph whose root node represents the final mathematical expression
and each node represents intermediate subexpressions.

Upshot: compute gradients via general backpropagation algorithm

Purposes:
• Automatically compute gradients (how TensorFlow and PyTorch work)
• Gain insight into modular structure of gradient computations

CS221 4
• Enter computation graphs, which will rescue us.
• A computation graph is a directed acyclic graph that represents an arbitrary mathematical expression. The root of that node represents the
final expression, and the other nodes represent intermediate subexpressions.
• After having constructed the graph, we can compute all the gradients we want by running the general-purpose backpropagation algorithm,
which operates on an arbitrary computation graph.
• There are two purposes to using computation graphs. The first and most obvious one is that it avoids having us to do pages of calculus, and
instead delegates this to a computer. This is what packages such as TensorFlow or PyTorch do, and essentially all non-trivial deep learning
models are trained like this.
• The second purpose is that by defining the graph, we can gain more insight into the nature of how gradients are computed in a modular way.
 Functions as boxes
c=a+b c=a·b
c + c ·
∂c ∂c ∂c ∂c
∂a =1 ∂b =1 ∂a =b ∂b =a

a b a b

(a + ) + b = c + 1 (a + )b = c + b
a + (b + ) = c + 1 a(b + ) = c + a

Gradients: how much does c change if a or b changes?

CS221 6
• The first conceptual step is to think of functions as boxes that take a set of inputs and produces an output.
• For example, take c = a + b. The key question is: if we perturb a by a small amount , how much does the output c change? In this case,
the output c is also perturbed by 1, so the gradient (partial derivative) is 1. We put this gradient on the edge.
• We can handle c = a · b in a similar way.
• Intuitively, the gradient is a measure of local sensivity: how much input perturbations get amplified when they go through the various functions.
 Basic building blocks
+ − ·

1 1 1 −1 b a

a b a b a b

(·)2 max σ

2a 1[a > b] 1[a < b] σ(a)(1 − σ(a))

a a b a

CS221 8
• Here are some more examples of simple functions and their gradients. Let’s walk through them together.
• These should be familiar from basic calculus. All we’ve done is present them in a visually more intuitive way.
• For the max function, changing a only impacts the max iff a > b; and analogously for b.
• For the logistic function σ(z) = 1+e1−z , a bit of algebraic elbow grease produces the gradient. You can check that the gradient is zero when
|a| → ∞.
• It turns out that these simple functions are all we need to build up many of the more complex and potentially scarier looking functions that
we’ll encounter.
 Function composition
c (·)2

∂c
∂b = 2b

b (·)2

∂b
∂a = 2a

a
Chain rule:
∂c ∂c ∂b
∂a = ∂b ∂a = (2b)(2a) = 4a3

CS221 10
• Given these building blocks, we can now put them together to create more complex functions.
• Consider applying some function (e.g., squared) to a to get b, and then applying some other function (e.g., squared) to get c.
• What is the gradient of c with respect to a?
• We know from our building blocks the gradients on the edges.
• The final answer is given by the chain rule from calculus: just multiply the two gradients together.
• You can verify that this yields the correct answer (2b)(2a) = 4a3 .
• This visual intuition will help us better understand more complex functions.
 Linear classification with hinge loss
loss max
Loss(x, y, w) = max{1 − w · φ(x)y, 0}
1[1 − margin > 0]

− 0 ∇w Loss(x, y, w) = −1[margin < 1]φ(x)y

−1
+ − ·
1 margin · 1 1 1 −1 b a

y a b a b a b

score · y (·)2 max σ

2a 1[a > b] 1[a < b] σ(a)(1 − σ(a))

φ(x)

a a b a
w φ(x)

CS221 12
• Now let’s turn to our first real-world example: the hinge loss for linear classification. We already computed the gradient before, but let’s do
it using computation graphs.
• We can construct the computation graph for this expression, proceeding bottom up. At the leaves are the inputs and the constants. Each
internal node is labeled with the operation (e.g., ·) and is labeled with a variable naming that subexpression (e.g., margin).
• In red, we have highlighted the weights w with respect to which we want to take the gradient. The central question is how small perturbations
in w affect a change in the output (loss).
• We can examine each edge from the path from w to loss, and compute the gradient using our handy reference of building blocks.
• The actual gradient is the product of the edge-wise gradients from w to the loss output.
 Two-layer neural networks
loss (·)2

2(residual) 2
Loss(x, y, V, w) = (w · σ(Vφ(x)) − y)

residual −
∇w Loss(x, y, V, w) = 2(residual)h
1

∇V Loss(x, y, V, w) = 2(residual)w ◦ h ◦ (1 − h)φ(x)>

score · y

h w + − ·

1 1 1 −1 b a
w h σ
a b a b a b

h ◦ (1 − h)
(·)2 max σ

· 2a 1[a > b] 1[a < b] σ(a)(1 − σ(a))

a a b a
φ(x)

V φ(x)
CS221 14
• We now finally turn to neural networks, but the idea is essentially the same.
• Specifically, consider a two-layer neural network driving the squared loss.
• Let us build the computation graph bottom up.
• Now we need to take the gradient with respect to w and V. Again, these are just the product of the gradients on the paths from w or V to
the loss node at the root.
• Note that the two gradients have in common the the first two terms. Common paths result in common subexpressions for the gradient.
• There are some technicalities when dealing with vectors worth mentioning: First, the ◦ in h ◦ (1 − h) is elementwise multiplication (not the
dot product), since the non-linearity σ is applied elementwise. Second, there is a transpose for the gradient expression with respect to V and
not w because we are taking Vφ(x), while taking w · h = w> h.
• This computation graph also highlights the modularity of hypothesis class and loss function. You can pick any hypothesis class (linear
predictors or neural networks) to drive the score, and the score can be fed into any loss function (squared, hinge, etc.).
 Backpropagation
Loss(x, y, w) = (w · φ(x) − y)2
loss = 9 (·)2 1

2(residual) w = [3, 1], φ(x) = [1, 2], y = 2

residual = 3 − 6 backpropagation
∇w Loss(x, y, w) = [6, 12]
1

score = 5 · 6 y=2
Definition: Forward/backward values
φ(x) = [1, 2]

Forward: fi is value for subexpression rooted at i

w = [3, 1] [6, 12] φ(x) = [1, 2]
Backward: gi = ∂loss
∂fi is how fi influences loss

Algorithm: backpropagation algorithm

Forward pass: compute each fi (from leaves to root)

Backward pass: compute each gi (from root to leaves)

CS221 16
• So far, we have mainly used the graphical representation to visualize the computation of function values and gradients for our conceptual
understanding.
• Now let us introduce the backpropagation algorithm, a general procedure for computing gradients given only the specification of the function.
• Let us go back to the simplest example: linear regression with the squared loss.
• All the quantities that we’ve been computing have been so far symbolic, but the actual algorithm works on real numbers and vectors. So let’s
use concrete values to illustrate the backpropagation algorithm.
• The backpropagation algorithm has two phases: forward and backward. In the forward phase, we compute a forward value fi for each node,
coresponding to the evaluation of that subexpression. Let’s work through the example.
• In the backward phase, we compute a backward value gi for each node. This value is the gradient of the loss with respect to that node,
which is also the product of all the gradients on the edges from the node to the root. To compute this backward value, we simply take the
parent’s backward value and multiply by the gradient on the edge to the parent. Let’s work through the example.
• Note that both fi and gi can either be scalars, vectors, or matrices, but have the same dimensionality.
 A note on optimization
minV,w TrainLoss(V, w)
Linear predictors Neural networks

(convex) (non-convex)

Optimization of neural networks is in principle hard

CS221 18
• So now we can apply the backpropagation algorithm and compute gradients, stick them into stochastic gradient descent, and get some answer
out.
• One question which we haven’t addressed is whether stochastic gradient descent will work in the sense of actually finding the weights that
minimize the training loss?
• For linear predictors (using the squared loss or hinge loss), TrainLoss(w) is a convex function, which means that SGD (with an appropriately
step size) is theoretically guaranteed to converge to the global optimum.
• However, for neural networks, TrainLoss(V, w) is typically non-convex which means that there are multiple local optima, and SGD is not
guaranteed to converge to the global optimum. There are many settings that SGD fails both theoretically and empirically, but in practice,
SGD on neural networks can work much better than theory would predict, provided certain precautions are taken. The gap between theory
and practice is not well understood and an active area of research.
 How to train neural networks

φ(x)
V
w
score = · σ( )

• Careful initialization (random noise, pre-training)

• Overparameterization (more hidden units than needed)
• Adaptive step sizes (AdaGrad, Adam)

Don’t let gradients vanish or explode!

CS221 20
• Training a neural network is very much like driving stick. In practice, there are some ”tricks” that are needed to make things work properly.
Just to name a few to give you a sense of the considerations:
• Initialization (where you start the weights) matters for non-convex optimization. Unlike for linear models, you can’t start at zero or else all
the subproblems will be the same (all rows of V will be the same). Instead, you want to initialize with a small amount of random noise.
• It is common to use overparameterized neural networks, ones with more hidden units (k) than is needed, because then there are more
”chances” that some of them will pick out on the right signal, and it is okay if some of the hidden units become ”dead”.
• There are small but important extensions of stochastic gradient descent that allow the step size to be tuned per weight.
• Perhaps one high-level piece of advice is that when training a neural network, it is important to monitor the gradients. If they vanish (get
too small), then training won’t make progress. If they explode (get too big), then training will be unstable.
 Summary
loss (·)2

2(residual)

residual −

score · y

h w

w h σ

h ◦ (1 − h)

φ(x)

V φ(x)

• Computation graphs: visualize and understand gradients

• Backpropagation: general-purpose algorithm for computing gradients

CS221 22
• The most important concept in this module is the idea of a computation graph, allows us to represent arbitrary mathematical expressions,
which can just be built out of simple building blocks. They hopefully have given you a more visual and better understanding of what gradients
are about.
• The backpropagation algorithm allows us to simply write down an expression, and never have to take a gradient manually again. However,
it is still important to understand how the gradient arises, so that when you try to train a deep neural network and your gradients vanish, you
know how to think about debugging your network.
• The generality of computation graphs and backpropagation makes it possible to iterate very quickly on new types of models and loss functions
and opens up a new paradigm for model development: differential programming.
Machine learning: differentiable programming
• In this module, I’ll briefly introduce the idea of differentiable programming, which runs with the ideas of computation graphs and backpropa-
gation that we developed for simple neural networks.
• There is enough to say here to fill up an entire course, so I will keep things high-level but try to highlight the power of composition.
• Aside: Differentiable programming is closely related to deep learning. I’ve adopted the former term as a more precise way to highlight the
mechanics of writing models as you would write code.
 Deep learning models
BERT [Devlin+, 2018]

VGGNet [Simoyan/Zisserman, 2014]

CS221 2
• If you look around at deep learning today, there are some pretty complex models which have many layers, attention mechanisms, residual
connections, layerwise normalization, to name a few, which might be overwhelming at first glance.
• However, if you look closer, these complex models are actually composed of functions, which themselves are composed of even simpler
functions.
• This is the ”programming” part of differentiable programming, which allows you to build up increasingly more powerful and sophisticated
models without losing track of what’s going on.
 Feedforward neural networks
φ(x)
b2 V2 b1 V1
b3 V3   
score = + σ + σ +

FeedForward
x x
 
=σ +

Performs one step of processing.

score = FeedForward(FeedForward(FeedForward(φ(x)))) = FeedForward3 (φ(x))

CS221 4
• Let’s revisit our familiar example, the three-layer neural network. In this model, we start with the feature vector φ(x) apply some operations
(left-multiply by a matrix, add a bias term) to get the score.
• (Note that we highlight that each of these matrices should be interpreted as a collection of rows.)
• The main differences from before are that we’ve added bias terms and renamed the final weight vector w to V3 for consistency with the other
layers.
• Let us now factor out a function of this model and call it FeedForward. This is a function that takes a fixed-dimensional vector x and
produces another vector (with potentially another dimensionality). This function is implemented by multiplying by a matrix and applying an
activation function (e.g., ReLU).
• Now we can not worry too much about the implementation, and just think of this as performing one step of processing. Compared to normal
programming, this is admittedly vague, because the parameters (e.g., the red quantities) are not specified but rather learned from data. So
differentiable programming requires us to necessarily be a bit loose.
• Using this brand new function, we can rewrite the three-layer neural network as follows. Strictly speaking, when we write FeedForward, we
mean a function that has its own private parameters that need to be set via backpropagation.
• Another simplification is that we are eliding the input and output dimensionality (6 to 4, 4 to 3, and 3 to 1 in this example). These are
hyperparameters which need to be set before learning.
 Representing images
x

Problems:
• Matrix is huge (depending on resolution of image)
• Does not capture the spatial structure (locality) of images

CS221 6
• Now suppose we want to do image classification. We need to have some way of representing images.
• The FeedForward function takes in a vector as input, and we can represent an image as a long vector containing all the pixels (say, by
concatenating all the rows).
• But then we would then have to have a huge matrix to transform this input, resulting in a lot of parameters (especially if the image is high
resolution), which might be difficult to learn.
• The issue is that we’re not leverage knowledge that these are images. If you permute the components of the input vector x and re-train, you
will just get a permuted parameters, but the same predictions.
 Convolutional neural networks

[Andrej Karpathy’s demo]

CS221 8
• Convolutional neural networks (ConvNets or CNNs) is a refinement of the vanilla fully-connected neural networks tailored for images.
• It is also used for sequences such as text (everything is just 1D instead of 2D) or video (everything is 3D instead of 2D).
• Here is a visualization of a ConvNet making a prediction on this car image. There are a sequence of layers which turn the image into something
increasingly abstract, and finally we get a vector representing the probabilities of the different object categories.
• You can click on this link to see Andrej Karpathy’s demo, where you can create and train ConvNets in your browser.
 Convolutional neural networks
Conv MaxPool
x x

Detect local patterns with filters. Take the max over each 2x2 region.

[Andrej Karpathy’s demo]

AlexNet(x) = FeedForward3 (MaxPool(Conv3 (MaxPool(Conv(MaxPool(Conv(x)))))))

CS221 10
• So let us now define the two basic building blocks of ConvNets. We’re not going to go through the details, but simply focus on the interface.
(You should take CS231N if you want to learn more about ConvNets.)
• First, Conv takes as input an image, which can be represented as a volume, which is a matrix for each channel (red, green, blue), and each
matrix has same height and width as the image.
• This function produces another volume whose height and width are either the same or a bit smaller than that of the input volume, and the
number of output channels could be different.
• The output volume is constructed by sweeping a filter over the input volume, and taking the dot product of the filter with a local part of the
input volume. That produces a number which you write into the output volume. The number of filters determines the number of channels
in the output volume.
• The second operation is MaxPool, which simply takes an input volume and reduces the width and height by taking the max over local regions.
• Note that MaxPool does not have any parameters and has the same number of input channels as output channels.
• Given just these two functions, Conv and MaxPool, as well as our friend FeedForward, we can express the famous AlexNet architecture,
which won the ImageNet competition in 2012 and arguably kicked off deep learning revolution.
• Note that each of these functions has its own parameters that need to be trained.
• Each one also has its own hyperparameters (number of channels, filter size, etc.).
 Representing natural language

CS221 12
• Now let us turn our attention to natural language processing. As a motivating example, suppose we wanted to build a question answering
system.
• Here are examples of questions from the SQuAD question answering benchmark, where the input is the paragraph, a question, and the goal
is to select the span of the paragraph that answers the question.
• This requires somehow relating the paragraph to the question; sometimes string match will work (e.g., ”precipitation”), and sometimes they
don’t (e.g., ”causes” and ”product”).
 Embedding tokens
EmbedToken

x
abc
Looks up the vector for a token.

In meterology, precipitation is any product of the condensation of atmospheric water vapor that falls under gravity.

Meaning of words/tokens depends on context...

CS221 14
• Words are discrete objects, whereas neural networks speak vectors.
• So the first step is to embed the words (more generally, tokens) into vectors. This is usually just accomplished by looking up the token in a
dictionary that maps tokens to vectors.
• Now given a sentence (sequence of tokens), we just embed each of the tokens independently to produce a sequence of vectors.
• However, this is not quite satisfactory because the meaning of words depends on context. For example, ”product” could mean result or it
could mean multiplication.
 Representing sequences
SequenceModel
x1 x2 x3 x4

Process each element of a sequence with respect to other elements.

Two implementations:
• Recurrent neural networks
• Transformers

CS221 16
• We’re now going to define an abstract function SequenceModel (to continue the programming metaphor).
• SequenceModel takes a sequence of vectors and produces a corresponding sequence of vectors, where each vector has been ”contextualized”
with respect to the other vectors.
• We will see two implementations, recurent neural networks and Transformers.
 Recurrent neural networks
In meterology, precipitation is any product of the condensation of atmospheric water vapor that falls under gravity.

SequenceRNN : SequenceModel
x1 x2 x3 x4 x5

RNN(h,x)

h1 h2 h3 h4 h5
Read left-to-right, updating hidden state.

CS221 18
• A recurrent neural network (RNN) can be thought of as reading left to right. It maintains a hidden state which represents the past and gets
updated with each new input vector.
• At the end of the day, however, it still produces a sequence of (contextualized) vectors given a sequence of input vectors.
• We still have to specify how the RNN computes the new hidden state given the old hidden state and the new input.
 Recurrent neural networks
SimpleRNN : RNN
x
x
h h
 
=σ +

Update hidden state given a new input.

LSTM : RNN

x
h

Update hidden state given a new input without forgetting the past.

CS221 20
• There are two types of RNNs I will talk about.
• A Simple RNN takes the old hidden state h, a new input x and produces a new hidden state.
• Both h and x get multiplied by a vector; the result is summed, and we apply the activation function as usual.
• Note that this is equivalent to just applying FeedForward on the concatenation of h and x.
• One problem with simple RNNs is that they suffer from the vanishing gradient problem, which makes them hard to train.
• Long Short-Term Memory (LSTMs) were developed in response to this problem. We won’t go over the details, but will just say that it
privileges h and makes sure that h doesn’t forget the history of inputs.
 Collapsing to a single vector
Collapse
x1 x2 x3 x4

Summarize using one vector (first, last, or average).

Example text classification model:

In meterology, precipitation is any product of the condensation of atmospheric water vapor that falls under gravity.

score = w· Collapse(SequenceModel3 (EmbedToken(x)))

CS221 22
• Note that the sequence model produces a variable number of vectors. In order to do classifaction, we need to Collapse the vectors into one,
which can then be used to drive the score for classification.
• There are three common things that are done: return the first vector, return the last vector, or return the average of all of them.
 Long-range dependencies
[CLS] What causes precipitation to fall? [SEP] In meterology, precipitation is any product of the condensation of atmospheric water vapor that falls under gravity.

Problem: RNN (and ConvNets) are very local

SequenceRNN : SequenceModel
x1 x2 x3 x4 x5

RNN(h,x)

h1 h2 h3 h4 h5
Read left-to-right, updating hidden state.

CS221 24
• This is all nice, but there is one big problem with RNNs, which is that they are very local, meaning that the vector produced at a given
position will in practice only depend on a small neighborhood.
• On the other hand, language often has long-range dependencies.
• For the model to leverage this knowledge, it has to remember the first material in the hidden state, update that hidden state repeatedly
without forgetting what it learned.
• Instead we would like an architecture that can allow information to propagate more quickly and freely across the sequence. This architecture
is the Transformer. But we need to introduce a few preliminaries first.
 Attention mechanism
Attention
x y
x>
 
x1 x2 x3 x4 y softmax

= x y
x>
 
softmax

Process y by comparing it to each xi .

Attention : SequenceModel
x1 x2 x3 x4 Attention(x, x1 ) Attention(x, x2 ) Attention(x, x3 ) Attention(x, x4 )

CS221 26
• This is a big slide.
• Attention is the core mechanism that allows us to model long-range dependencies effectively.
• Formally, attention takes a collection of input vectors x1 , . . . , xn , a query vector y, and the goal is to process y in the context of the input
vectors.
• Let’s walk through the diagram slowly. We start with y and reduce its dimensionality. Similary, we can reduce the dimensionality for all rows
of x> .
• Now the key part is to take the dot product between the representation of y and the representation of each xi .
• We now have one column representing similarity scores (positive or negative) between y and each xi .
• We apply the softmax, which exponentiates each component and then normalizes to 1.
• We can use the distribution to take a convex combination of the columns of x. And finally we project onto the desired dimensionality.
• The above calculations is one attention head. In parallel, we go through the same motions to construct another vector. These are concantenated
together and projected down to the original space.
• Another form of easy attention (called self-attention) is self-attention, in which case the queries are simply the same elements.
• This provides a sequence model where all pairs of elements of the sequence interact.
 Layer normalization and residual connections
AddNorm(f ) : SequenceModel
x1 x2 x3 x4

Applies f to x safely.
AddNorm(f , x) = LayerNorm(x + f (x))

CS221 28
• There are two other pieces we need to introduce before we can fully define the Transformer: layer normalization and residual connections.
• They can be thought of as technical devices to make the final network easier to train.
• Together, they can be packed up into AddNorm. The interface is the same as a sequence model: it takes a sequence of vectors and produces
a corresponding sequence of vectors.
• AddNorm takes a function f and applies it to the input x. Then we add x (called a residual connection), which allows information from x
to be directly passed through in case f is somehow messed up (say, early in training).
• Then we apply layer normalization, which takes a vector x and makes sure it’s not too small or big (or else gradients might vanish or explode).
Specifically, it subtracts the average of the elements of x and divides by the standard deviation. We do this for each vector in x.
• In summary, AddNorm applies f to x safely.
 Transformer
TransformerBlock : SequenceModel
x1 x2 x3 x4

Processes each object xi in context.

TransformerBlock(x) = AddNorm(FeedForward, AddNorm(Attention, x))

CS221 30
• Finally, we are ready to introduce the Transformer, which was introduced in 2017 and has really overthrown RNNs as the sequence model of
choice.
• The TransformerBlock is a sequence model that takes a sequence of vectors to corresponding sequence of contextual vectors.
• We’ve already defined all the pieces, so the Transformer is just a one-liner.
• First, we apply self-attention to x to contextualize the vectors. Then we apply AddNorm (layer normalization with residual connections) to
make things safe.
• Second, we apply a feedforward network to further process each vector independently. Then we do another AddNorm, and that’s it.
• Note: in the actual Transformer, the FeedForward function has an extra matrix at the end.
 [Devlin+, 2018]

BERT

[CLS] What causes precipitation to fall? [SEP] In meterology, precipitation is any product of the condensation of atmospheric water vapor that falls under gravity.

BERT(x) = TransformerBlock24 (EmbedToken(x))

CS221 32
• Now we can explain BERT, the large unsupervised pretrained model which transformed NLP in 2018. Before then, there were many specialized
architectures for different tasks but BERT was a single model architecture that worked well across many tasks.
• BERT is a function that takes a sentence, turns it into a sequence of vectors, and then just applies a Transformer block 24 times.
• When it’s used for question answering, you concatenate the question with the paragraph.
• There are some details omitted: BERT defines tokens as word pieces as opposed to words. It also uses positional encodings as the Transformer
block is invariant to the order of the vectors.
• Note that we are also not talking about the objective function (masked language modeling, next sentence prediction) used to train BERT.
 Generating tokens
GenerateToken

x
y
abc

Generate token y based on x· EmbedToken(y).

EmbedToken

x
abc
Looks up the vector for a token.

CS221 34
• So far, we’ve mostly studied how to design functions that can process a sentence (sequence of tokens or vectors).
• We can also generate new sequences.
• The basic building block for generation is something that takes a vector and outputs a token.
• This process is the reverse of EmbedToken, but uses it as follows: we compute a score x· EmbedToken(y) for each candidate token.
• Then we apply softmax (exponentiate and normalize) to get a distribution over words y. From this distribution, we can either take the token
with the highest probability or simply sample a word from this distribution.
 Generating sequences
LanguageModel

x
fox
the quick brown
Generate next token in the sequence.
LanguageModel(x) = GenerateToken(Collapse(SequenceModel(EmbedToken(x))))

CS221 36
• In language modeling, we wish to generate (predict) the next token given the previous words generated so far.
• In this case, we simply take the history, which is a sequence of tokens, embed them, apply a sequence model (e.g., RNN or a Transformer).
• We then Collapse this into one vector (usually the last one).
• Now we’ve reduced the problem to something that GenerateToken can solve.
 Sequence-to-sequence models
SequenceToSequence

x LanguageModel the blue house

la maison bleue
Generate a sequence from another sequence.

Applications:
• Machine translation: sentence to translation
• Document summarization: document to summary
• Semantic parsing: sentence to code

CS221 38
• Perhaps the most versatile interface is sequence-to-sequence models, where the model takes as input a sequence of tokens and produces an
sequence of tokens.
• Importantly, the input sequence and the output sequence are not in 1:1 correspondence, and in general they have different lengths.
• Sequence-to-sequence models can be reduced to language modeling, where you feed in the input x along with the output tokens that you’ve
generated so far, and ask for the next token.
• There are a number of applications (mostly in NLP) that uses sequence-to-sequence models: machine translation, document summarization,
and semantic parsing to name a few.
 Summary
FeedForward Conv MaxPool
EmbedToken SequenceRNN SimpleRNN LSTM
Attention AddNorm TransformerBlock BERT
Collapse GenerateToken LanguageModel SequenceToSequence
SequenceModel
x1 x2 x3 x4

Process each element of a sequence with respect to other elements.

CS221 40
• In summary, we’ve done a whirlwind tour over different types of differentiable programs from deep learning.
• We started with feedforward networks (FeedForward), and then talked about convolutional neural networks (Conv, MaxPool).
• Then we considered token sequences (e.g., text), where we always start by embedding the tokens into vectors (EmbedToken).
• There are two paths: The first uses RNNs and the second uses Transformers.
• There are many details that we have glossed over, but the thing you should take away is to understand rigorously what the type signature of
all these functions are, and some intuition behind what the function is meant to be doing.
Machine learning: generalization
• In this module, I will talk about the generalization of machine learning algorithms.
 Minimizing training loss
Hypothesis class:
fw (x) = w · φ(x)
Training objective (loss function):
1 X
TrainLoss(w) = Loss(x, y, w)
|Dtrain |
(x,y)∈Dtrain

Optimization algorithm:
stochastic gradient descent

Is the training loss a good objective to optimize?

CS221 2
• Recall that our machine learning framework consists of specifying the hypothesis class, loss function, and the optimization algorithm.
• The hypothesis class could be linear predictors or neural networks. The loss function could be the hinge loss or the squared loss, which is
averaged to produce the training loss.
• The default optimization algorithm is (stochastic) gradient descent.
• But let’s be a bit more critical about the training loss. Is the training loss the right thing to optimize?
 A strawman algorithm

Algorithm: rote learning

Training: just store Dtrain .

Predictor f (x):
If (x, y) ∈ Dtrain : return y.
Else: segfault.

Minimizes the objective perfectly (zero), but clearly bad...

CS221 4
• Here is a strategy to consider: the rote learning algorithm, which just memorizes the training data and crashes otherwise.
• The rote learning algorithm does a perfect job of minimizing the training loss.
• But it’s clearly a bad idea: It overfits to the training data and doesn’t generalize to unseen examples.
• So clearly machine learning can’t be about just minimizing the training loss.
 Overfitting pictures

Classification Regression

CS221 6
• This is an extreme example of overfitting, which is when a learning algorithm outputs a predictor that does well on the training data but not
well on new examples.
• Here are two pictures that illustrate what overfitting looks like for binary classification and regression.
• On the left, we see that the green decision boundary gets zero training loss by separating all the blue points from the red ones. However, the
smoother and simpler black curve is intuitively more likely to be the better classifier.
• On the right, we see that the predictor that goes through all the points will get zero training loss, but intuitively, the black line is perhaps a
better option.
• In both cases, what is happening is that by over-optimizing on the training set, we risk fitting noise in the data.
 Evaluation

Dtrain learning algorithm f

How good is the predictor f ?

Key idea: the real learning objective

Our goal is to minimize error on unseen future examples.

Don’t have unseen examples; next best thing:

Definition: test set

Test set Dtest contains examples not used for training.

CS221 8
• So what is the true objective then? Taking a step back, machine learning is just a means to an end. What we’re really doing is building a
predictor to be deployed in the real world, and we just happen to be using machine learning. What we really care about is how accurate that
predictor is on those unseen future inputs.
• Of course, we can’t access unseen future examples, so the next best thing is to create a test set. As much as possible, we should treat the
test set as a pristine thing that’s unseen. We definitely should not tune our predictor based on the test set, because we wouldn’t be able to
do that on future examples.
• Of course at some point we have to run our algorithm on the test set, but just be aware that each time this is done, the test set becomes
less good of an indicator of how well your predictor is actually doing.
 Generalization
When will a learning algorithm generalize well?

Dtrain Dtest

CS221 10
• So far, we have an intuitive feel for what overfitting is. How do we make this precise? In particular, when does a learning algorithm generalize
from the training set to the test set?
 Approximation and estimation error
All predictors
F
∗ Learning
f approx. error est. error
g fˆ

• Approximation error: how good is the hypothesis class?

• Estimation error: how good is the learned predictor relative to the potential of the
hypothesis class?
Err(fˆ) − Err(f ∗ ) = Err(fˆ) − Err(g) + Err(g) − Err(f ∗ )
| {z } | {z }
estimation approximation

CS221 12
• Here’s a cartoon that can help you understand the balance between fitting and generalization. Out there somewhere, there is a magical
predictor f ∗ that classifies everything perfectly. This predictor is unattainable; all we can hope to do is to use a combination of our domain
knowledge and data to approximate that. The question is: how far are we away from f ∗ ?
• Recall that our learning framework consists of (i) choosing a hypothesis class F (e.g., by defining the feature extractor) and then (ii) choosing
a particular predictor fˆ from F.
• Approximation error is how far the entire hypothesis class is from the target predictor f ∗ . Larger hypothesis classes have lower approximation
error. Let g ∈ F be the best predictor in the hypothesis class in the sense of minimizing test error g = arg minf ∈F Err(f ). Here, distance is
just the differences in test error: Err(g) − Err(f ∗ ).
• Estimation error is how good the predictor fˆ returned by the learning algorithm is with respect to the best in the hypothesis class:
Err(fˆ) − Err(g). Larger hypothesis classes have higher estimation error because it’s harder to find a good predictor based on limited data.
• We’d like both approximation and estimation errors to be small, but there’s a tradeoff here.
 Effect of hypothesis class size
All predictors
F
Learning
f∗ approx. error est. error
g fˆ

As the hypothesis class size increases...

Approximation error decreases because:
taking min over larger set
Estimation error increases because:
harder to estimate something more complex

How do we control the hypothesis class size?

CS221 14
• The approximation error decreases monotonically as the hypothesis class size increases for a simple reason: you’re taking a minimum over a
larger set.
• The estimation error increases monotonically as the hypothesis class size increases for a deeper reason involving statistical learning theory
(explained in CS229T).
 Strategy 1: dimensionality
w ∈ Rd

Reduce the dimensionality d (number of features):

CS221 16
• Let’s focus our attention to linear predictors. For each weight vector w, we have a predictor fw (for classification, fw (x) = w · φ(x)). So the
hypothesis class F = {fw } is all the predictors as w ranges. By controlling the number of possible values of w that the learning algorithm is
allowed to choose from, we control the size of the hypothesis class and thus guard against overfitting.
• One straightforward strategy is to change the dimensionality, which is the number of features. For example, linear functions are lower-
dimensional than quadratic functions.
 Controlling the dimensionality
Manual feature (template) selection:
• Add feature templates if they help
• Remove feature templates if they don’t help
Automatic feature selection (beyond the scope of this class):
• Forward selection
• Boosting
• L1 regularization

It’s the number of features that matters

CS221 18
• Mathematically, you can think about removing a feature φ(x)37 as simply only allowing its corresponding weight to be zero (w37 = 0).
• Operationally, if you have a few feature templates, then it’s probably easier to just manually include or exclude them — this will give you
more intuition.
• If you have a lot of individual features, you can apply more automatic methods for selecting features, but these are beyond the scope of this
class.
• An important point is that it’s the number of features that matters, not the number of feature templates. (Can you define one feature
template that results in severe overfitting?) Nor is it the amount of code that you have to write to generate a particular feature.
 Strategy 2: norm
w ∈ Rd

Reduce the norm (length) kwk:

CS221 20
• A related way to keep the weights small is called regularization, which involves adding an additional term to the objective function which
penalizes the norm (length) of w. This is probably the most common way to control the norm.
 Controlling the norm
Regularized objective:
λ
min TrainLoss(w) + kwk2
w 2

Algorithm: gradient descent

Initialize w = [0, . . . , 0]
For t = 1, . . . , T :
w ← w − η(∇w TrainLoss(w)+λw)

Same as gradient descent, except shrink the weights towards zero by λ.

CS221 22
• This form of regularization is also known as L2 regularization, or weight decay in deep learning literature.
• We can use gradient descent on this regularized objective, and this simply leads to an algorithm which subtracts a scaled down version of w
in each iteration. This has the effect of keeping w closer to the origin than it otherwise would be.
• Note: Support Vector Machines are exactly hinge loss + L2 regularization.
 Controlling the norm: early stopping

Algorithm: gradient descent

Initialize w = [0, . . . , 0]
For t = 1, . . . , T :
w ← w − η∇w TrainLoss(w)

Idea: simply make T smaller

Intuition: if have fewer updates, then kwk can’t get too big.

Lesson: try to minimize the training error, but don’t try too hard.

CS221 24
• A really cheap way to keep the weights small is to do early stopping. As we run more iterations of gradient descent, the objective function
improves. If we cared about the objective function, this would always be a good thing. However, our true objective is not the training loss.
• Each time we update the weights, w has the potential of getting larger, so by running gradient descent a fewer number of iterations, we are
implicitly ensuring that w stays small.
• Though early stopping seems hacky, there is actually some theory behind it. And one paradoxical note is that we can sometimes get better
solutions by performing less computation.
 Summary
Not the real objective: training loss
Real objective: loss on unseen future examples
Semi-real objective: test loss

Key idea: keep it simple

Try to minimize training error, but keep the hypothesis class small.

CS221 26
• In summary, we started by noting that the training loss is not the objective. Instead it is minimizing unseen future examples, which is
approximated by the test set provided you are careful.
• We’ve seen several ways to control the size of the hypothesis class (and thus reducing the estimation error) based on either reducing the
dimensionality or reducing the norm.
• It is important to note that what matters is the size of the hypothesis class, not how ”complex” the predictors in the hypothesis class look.
To put it another way, using complex features backed by 1000 lines of code doesn’t hurt you if there are only 5 of them.
• So far, we’ve talked about the various knobs that we can turn to control the size of the hypothesis class, but how much do we turn each
knob?
Machine learning: best practices
• We’ve spent a lot of talking about the formal principles of machine learning.
• In this module, I will discuss some of the more empirical aspects you encounter in practice.
 Choose your own adventure
Hypothesis class:
Feature extractor φ: linear, quadratic
fw (x) = sign(w · φ(x))
Architecture: number of layers, number of hidden units

Training objective:
1
P Loss function: hinge, logistic
|Dtrain | (x,y)∈Dtrain Loss(x, y, w) + Reg(w)
Regularization: none, L2

Optimization algorithm:
Number of epochs
Algorithm: stochastic gradient descent
Step size: constant, decreasing, adaptive
Initialize w = [0, . . . , 0]
For t = 1, . . . , T : Initialization: amount of noise, pre-training
For (x, y) ∈ Dtrain :
Batch size
w ← w − η∇w Loss(x, y, V, w)
CS221
Dropout 2
• Recall that there are three design decisions for setting up a machine learning algorithm: the hypothesis class, the training objective, and the
optimization algorithm.
• For the hypothesis class, there are two knobs you can turn. The first is the feature extractor φ (linear features, quadratic features, indicator
features on regions, etc. The second is the architecture of the predictor: linear (one layer) or neural network with layers, and in the case of
neural networks, how many hidden units (k) do we have.
• The second design decision is to specify the training objective, which we do by specifying the loss function depending how we want the
predictor to fit our data, and also whether we want to regularize the weights to guard against overfitting.
• The final design decision is how to optimize the predictor. Even the basic stochastic gradient descent algorithm has at least two knobs: how
long to train (number of epochs) and how aggressively to update (the step size). On top of that are many enhancements and tweaks common
to training deep neural networks: changing the step size over time, perhaps adaptively, how we initialize the weights, whether we update on
batches (say of 16 examples) instead of 1, and whether we apply dropout to guard against overfitting.
• So it is really a choose your own machine learning adventure. Sometimes decisions can be made via prior knowledge and are thoughtful (e.g.,
features that capture periodic trends). But in many (even most) cases, we don’t really know what the proper values should be. Instead, we
want a way to have these just set automatically.
 Hyperparameters

Definition: hyperparameters

Design decisions (hypothesis class, training objective, optimization algorithm) that

need to be made before running the learning algorithm.

How do we choose hyperparameters?

Choose hyperparameters to minimize Dtrain error?

No - optimum would be to include all features, no regularization, train forever

Choose hyperparameters to minimize Dtest error?

No - choosing based on Dtest makes it an unreliable estimate of error!

CS221 4
• Each of these many design decisions is a hyperparameter.
• We could choose the hyperparameters to minimize the training loss. However, this would lead to a degenerate solution. For example, by
adding additional features, we can always decrease the training loss, so we would just end up adding all the features in the world, leading to
a model that wouldn’t generalize. We would turn off all regularization, because that just gets in the way of minimizing the training loss.
• What if we instead chose hyperparameters to minimize the test loss. This might lead to good hyperparameters, but is problematic because
you then lose the ability to measure how well you’re doing. Recall that the test set is supposed to be a surrogate for unseen examples, and
the more you optimize over them, the less unseen they become.
 Validation set

Definition: validation set

A validation set is taken out of the training set and used to optimize hyperparameters.

Dtrain \Dval Dval Dtest

For each setting of hyperparameters, train on Dtrain \Dval , evaluate on Dval

CS221 6
• The solution is to invent something that looks like a test set. There’s no other data lying around, so we’ll have to steal it from the training
set. The resulting set is called the validation set.
• The size of the validation set should be large enough to give you a reliable estimate, but you don’t want to take away too many examples
from the training set.
• With this validation set, now we can simply try out a bunch of different hyperparameters and choose the setting that yields the lowest error
on the validation set. Which hyperparameter values should we try? Generally, you should start by getting the right order of magnitude (e.g.,
λ = 0.0001, 0.001, 0.01, 0.1, 1, 10) and then refining if necessary.
• In K-fold cross-validation, you divide the training set into K parts. Repeat K times: train on K − 1 of the parts and use the other part as
a validation set. You then get K validation errors, from which you can compute and report both the mean and the variance, which gives you
more reliable information.
 Model development strategy

Algorithm: Model development strategy

• Split data into train, validation, test

• Look at data to get intuition
• Repeat:
• Implement model/feature, adjust hyperparameters
• Run learning algorithm
• Sanity check train and validation error rates
• Look at weights and prediction errors
• Evaluate on test set to get final error rates

CS221 8
• This slide represents the most important yet most overlooked part of machine learning: how to actually apply it in practice.
• We have so far talked about the mathematical foundation of machine learning (loss functions and optimization), and discussed some of the
conceptual issues surrounding overfitting, generalization, and the size of hypothesis classes. But what actually takes most of your time is not
writing new algorithms, but going through a development cycle, where you iteratively improve your system.
• The key is to stay connected with the data and the model, and have intuition about what’s going on. Make sure to empirically examine the
data before proceeding to the actual machine learning. It is imperative to understand the nature of your data in order to understand the
nature of your problem.
• First, maintain data hygiene. Hold out a test set from your data that you don’t look at until you’re done. Start by looking at the (training or
validation) data to get intuition. You can start to brainstorm what features / predictors you will need. You can compute some basic statistics.
• Then you enter a loop: implement a new model architecture or feature template. There are three things to look at: error rates, weights, and
predictions. First, sanity check the error rates and weights to make sure you don’t have an obvious bug. Then do an error analysis to see
which examples your predictor is actually getting wrong. The art of practical machine learning is turning these observations into new features.
• Finally, run your system once on the test set and report the number you get. If your test error is much higher than your validation error, then
you probably did too much tweaking and were overfitting (at a meta-level) the validation set.
 Model development strategy example

Problem: simplified named-entity recognition

Input: a string x (e.g., Governor Gavin Newsom in)

Output: y, whether x (excluding first/last word) is a person or not (e.g., +1)

[code]

CS221 10
• Let’s try out the model development strategy on the task of training a classifier to predict whether a string is person or not (excluding the
first and last contxt words).
• First, let us look at the data (names.train). Starting simple, we define the empty feature template, which gets horrible error.
• Then we define a single feature template ”entity is ”. Look at weights (person names have positive weight, city names have negative
weight) and error-analysis.
• Let us add ”left is ” and ”right is ” feature templates based on the errors (e.g., the word ”said” is indicative of a person). Look at
weights (”the” showing up on the left indicates not a person) and error-analysis.
• Let us add feature templates ”entity contains ”. Look at weights and error-analysis.
• Let us add feature templates ”entity contains prefix ” and ”entity contains suffix ”. Look at weights and error-analysis.
• Finally we run it on the test set.
 Tips
Start simple:
• Run on small subsets of your data or synthetic data
• Start with a simple baseline model
• Sanity check: can you overfit 5 examples
Log everything:
• Track training loss and validation loss over time
• Record hyperparameters, statistics of data, model, and predictions
• Organize experiments (each run goes in a separate folder)
Report your results:
• Run each experiment multiple times with different random seeds
• Compute multiple metrics (e.g., error rates for minority groups)
CS221 12
• There is more to be said about the practice of machine learning. Here are some pieces of advice. Note that many related to simply good
software engineering practices.
• First, don’t start out by coding up a large complex model and try running it on a million examples. Start simple, both with the data (small
number of examples) and the model (e.g., linear classifier). Sanity check that things are working first before increasing the complexity. This
will help you debug in a regime where things are more interpretable and also things run faster. One sanity check is to train a sufficiently
expressive model on a few very examples and see if the model can overfit the examples (get zero training error). This does not produce a
useful model, but is a diagnostic to see if the optimization is working. If you can’t overfit on 5 examples, then you have a problem: maybe
the hypothesis class is too small, the data is too noisy, or the optimization isn’t working.
• Second, log everything so you can diagnose problems. Monitor the losses over epochs. It is also important to track the training loss so that
if you get bad results, is it due to bad optimization or overfitting. Record all the hyperparameters, so that you have a full record of how to
reproduce the results.
• Third, when you report your results, you should be able to run an experiment multiple times with different randomness to see how stable the
results are. Report error bars. And finally, if it makes sense for your application to report more than just a single test accuracy. Report the
errors for minority groups and add if your model is treating every group fairly.
 Summary

Dtrain \Dval Dval Dtest

Don’t look at the test set!

Understand the data!

Start simple!

Practice!

CS221 14
• To summarize, we’ve talked about the practice of machine learning.
• First, make sure you follow good data hygiene, separating out the test set and don’t look at it.
• But you should look at the training or validation set to get intuition about your data before you start.
• Then, start simple and make sure you understand how things are working.
• Beyond that, there are a lot of design decisions to be made (hyperparameters). So the most important thing is to practice, so that you can
start developing more intuition, and developing a set of best practices that works for you.
Machine learning: k-means
• In this module, we’ll talk about K-means, a simple algorithm for clustering, a form of unsupervised learning.
[Brown et al, 1992]

Word clustering
Input: raw text (100 million words of news articles)...
Output:
Cluster 1: Friday Monday Thursday Wednesday Tuesday Saturday Sunday weekends Sundays Saturdays
Cluster 2: June March July April January December October November September August
Cluster 3: water gas coal liquid acid sand carbon steam shale iron
Cluster 4: great big vast sudden mere sheer gigantic lifelong scant colossal
Cluster 5: man woman boy girl lawyer doctor guy farmer teacher citizen
Cluster 6: American Indian European Japanese German African Catholic Israeli Italian Arab
Cluster 7: pressure temperature permeability density porosity stress velocity viscosity gravity tension
Cluster 8: mother wife father son husband brother daughter sister boss uncle
Cluster 9: machine device controller processor CPU printer spindle subsystem compiler plotter
Cluster 10: John George James Bob Robert Paul William Jim David Mike
Cluster 11: anyone someone anybody somebody
Cluster 12: feet miles pounds degrees inches barrels tons acres meters bytes
Cluster 13: director chief professor commissioner commander treasurer founder superintendent dean custodian
Cluster 14: had hadn’t hath would’ve could’ve should’ve must’ve might’ve
Cluster 15: head body hands eyes voice arm seat eye hair mouth

CS221 2
• Here is a classic example of clustering from the NLP literature, called Brown clustering. This was the unsupervised learning method of choice
before word vectors.
• The input to the algorithm is simply raw text, and the output is a clustering of the words.
• The first cluster more or less represents days of the week, the second is months, the third is natural resources, and so on.
• It is important to note that no one told the algorithm what days of the week were or months or family relations. The clustering algorithm
discovered this structure automatically.
• On a personal note, Brown clustering was actually my first experience that got me to pursue research in NLP. Seeing the results of unsupervised
learning when it works was just magical. And of course today, we’re seeing even more strongly the potential of unsupervised learning with
neural language models such as BERT and GPT-3.
 Classification (supervised learning)

2
training data Dtrain
[2, 0] 1
φ(x)1 φ(x)2 y

φ(x)2
0
0 2 1 learning algorithm
f classifier
-1
-2 0 1
1 -1 -1 -2
-1 -3
-3 -2 -1 0 1 2 3

φ(x)1

Labeled data is expensive to obtain

CS221 4
• I want to contrast unsupervised learning with supervised learning.
• Recall that in classification you’re given a set of labeled training examples.
• A learning algorithm produces a classifier that can classify new points.
• Note that we’re now plotting the (two-dimensional) feature vector rather than the raw input, since the learning algorithms only depend on
the feature vectors.
• However, the main challenge with supervised learning is that it can be expensive to collect the labels for data.
 Clustering (unsupervised learning)
training data Dtrain
assignments
φ(x)1 φ(x)2
3 z 3
-2 1
2 1 2
0 1
1 1 1
φ(x)2

φ(x)2
-2 3
0
learning algorithm
1 0

-1 0 3 -1
1
-2 2 -1 -2
2
-3 1 -2 -3
-3 -2 -1 0 1 2 3 2 -3 -2 -1 0 1 2 3

φ(x)1 2 -3 φ(x)1
2
3 -2
2

Intuition: Want to assign nearby points to same cluster

Unlabeled data is very cheap to obtain

CS221 6
• In contrast, in clustering, you are only given unlabeled training examples.
• Our goal is to assign each point to a cluster. In this case, there are two clusters, 1 (blue) and 2 (orange).
• Intuitively, nearby points should be assigned to the same cluster.
• The advantage of unsupervised learning is that unlabeled data is often very cheap and almost free to obtain, especially text or images on the
web.
 Clustering task

Definition: clustering

Input: training points

Dtrain = [x1 , . . . , xn ]
Output: assignment of each point to a cluster
z = [z1 , . . . , zn ] where zi ∈ {1, . . . , K}

CS221 8
• Formally, the task of clustering is to take a set of points as input and return a partitioning of the points into K clusters.
• We will represent the partitioning using an assignment vector z = [z1 , . . . , zn ].
• For each i, zi ∈ {1, . . . , K} specifies which of the K clusters point i is assigned to.
 Centroids

Each cluster k = 1, . . . , K is represented by a centroid µk ∈ Rd

µ = [µ1 , . . . , µK ]
3

φ(x)2
0

-1

-2

-3
-3 -2 -1 0 1 2 3

φ(x)1

Intuition: want each point φ(xi ) to be close to its assigned centroid µzi

CS221 10
• What makes a cluster? The key assumption is that each cluster k is represented by a centroid µk .
• Now the intuition is that we want each point φ(xi ) to be close to its assigned centroid µzi .
 K-means objective
3

2
φ(x)2 1
n
0 X
-1
Losskmeans (z, µ) = kφ(xi ) − µzi k2
-2
i=1

-3
-3 -2 -1 0 1 2 3

φ(x)1

min min Losskmeans (z, µ)

z µ

CS221 12
• To formalize this, we define the K-means objective (distinct from the K-means algorithm).
• The variables are the assignments z and centroids µ.
• We examine the squared distance (dashed lines) from a point φ(xi ) to the centroid of its assigned cluster µzi . Summing over all these squared
distances gives the K-means objective.
• This loss can be interpreted as a reconstruction loss: imagine replacing each data point by its assigned centroid. Then the objective captures
how lossy this compression was.
• Now our goal is to minimize the K-means loss.
 Alternating minimization from optimum
0 1 2 10 11 12

1 1 2 2

If know centroids µ1 = 1, µ2 = 11:

z1 = arg min{(0 − 1)2 , (0 − 11)2 } = 1
z2 = arg min{(2 − 1)2 , (2 − 11)2 } = 1
z3 = arg min{(10 − 1)2 , (10 − 11)2 } = 2
z4 = arg min{(12 − 1)2 , (12 − 11)2 } = 2

If know assignments z1 = z2 = 1, z3 = z4 = 2:
µ1 = arg minµ (0 − µ)2 + (2 − µ)2 = 1
µ2 = arg minµ (10 − µ)2 + (12 − µ)2 = 11

CS221 14
• Before we present the K-means algorithm, let us form some intuitions.
• Consider the following one-dimensional clustering problem with 4 points. Intuitively there are two clusters.
• Suppose we know the centroids. Then for each point the assignment that minimizes the K-means loss is the closer of the two centroids.
• Suppose we know the assignments. Then for each cluster, we average the points that are assigned to that cluster.
 Alternating minimization from random initialization
Initialize µ:
0 2 10 12

Iteration 1:
0 2 8 10 12

1 2 2 2

Iteration 2:
0 1 2 10 11 12

1 1 2 2

Converged.

CS221 16
• But of course we don’t know either the centroids or assignments.
• So we simply start with an arbitrary setting of the centroids.
• Then alternate between choosing the best assignments given the centroids, and choosing the best centroids given the assignments.
• This is the K-means algorithm.
 K-means algorithm
Algorithm: K-means

Initialize µ = [µ1 , . . . , µK ] randomly.

For t = 1, . . . , T :
Step 1: set assignments z given µ
For each point i = 1, . . . , n:
zi ← arg min kφ(xi ) − µk k2
k=1,...,K
Step 2: set centroids µ given z
For each cluster k = 1, . . . , K:
1 X
µk ← φ(xi )
|{i : zi = k}|
i:zi =k

CS221 18
• Now we can state the K-means algorithm formally. We start by initializing all the centroids randomly. Then, we iteratively alternate back
and forth between steps 1 and 2, optimizing z given µ and vice-versa.
• Step 1 of K-means fixes the centroids µ. Then we can optimize the K-means objective with respect to z alone quite easily. It is easy to show
that the best label for zi is the cluster k that minimizes the distance to the centroid µk (which is fixed).
• Step 2 turns things around and fixes the assignments z. We can again look at the K-means objective function and optimize it with respect
to the centroids µ. The best µk is to place the centroid at the average of all the points assigned to cluster k.
 Local minima
K-means is guaranteed to converge to a local minimum, but is not guaranteed to find the global
minimum.

[demo: getting stuck in local optima, seed = 100]

Solutions:
• Run multiple times from different random initializations
• Initialize with a heuristic (K-means++)

CS221 20
• K-means is guaranteed to decrease the loss function each iteration and will converge to a local minimum, but it is not guaranteed to find the
global minimum, so one must exercise caution when applying K-means.
• Advanced: One solution is to simply run K-means several times from multiple random initializations and then choose the solution that has
the lowest loss.
• Advanced: Or we could try to be smarter in how we initialize K-means. K-means++ is an initialization scheme which places centroids on
training points so that these centroids tend to be distant from one another.
 Summary
Clustering: discover structure in unlabeled data
K-means objective: K-means algorithm:
3

1 assignments z centroids µ
φ(x)2

-1

-2

-3
-3 -2 -1 0 1 2 3

φ(x)1

Unsupervised learning use cases:

• Data exploration and discovery
• Providing representations to downstream supervised learning
CS221 22
• In summary, K-means is a simple and widely-used method for discovering cluster structure in data.
• Note that K-means can mean two things: the objective and the algorithm.
• Given points we define the K-means objective as the sum of the squared differences between a point and its assigned centroid.
• We also defined the K-means algorithm, which performs alternating optimization on the K-means objective.
• Finally, clustering is just one instance of unsupervised learning, which seeks to learn models from the wealth of unlabeled data alone.
Unsupervised learning can be used in two ways: exploring a dataset which has not been labeled (let the data speak), and learning representations
(discrete clusters or continuous embeddings) useful for downstream supervised applications.
Examples: [class] [email] [regression] [noise] [nonlinear] [cluster] [new]
[Background] [Documentation]
Algorithm: stochastic gradient descent on Losshinge (x, y, w) = max{1 − (w · φ(x))y, 0}

Step (or press ctrl-enter in text box)

Train error: 4/4 = 1
Start of algorithm. Click ”Step” to step through it.
 Learning algorithms

• An example is an input-output pair (x, y). The input could be anything (strings, images, videos). In principle the output could be anything, but we will focus
on the case where the output y ∈ {+1, −1} (binary classification) and y ∈ R (regression).
• We are given a set of training examples Dtrain and a set of test examples Dtest .
• Given an input x, we define a feature vector φ(x) ∈ Rd , which maps x into a high-dimensional point, each feature representing some useful aspect of x.
• This demo implements the following learning algorithms: rote learning, nearest neighbors, and stochastic gradient descent for linear predictors.
• Rote learning computes, for each possible feature vector φ(x), a histogram of possible outputs y based on the training data. Given a new input x, the most
frequent y for φ(x) is returned.
• Nearest neighbors returns a predictor, which given an input x, returns the output of the closest x0 (that is, kφ(x0 ) − φ(x)k2 is the smallest.

CS221 2
 Learning algorithms: loss minimization
P
• Now we discuss the loss minimization framework, which is to find w that minimizes (x,y)∈Dtrain Loss(x, y, w) + Penalty(w). This captures many of the
learning algorithms based on linear predictors.
• The possible loss functions for binary classification are Lossperceptron (Perceptron algorithm), Losshinge (support vector machines), and Losslogistic (logistic
regression). The possible loss functions for regression are Losssquared (least squares regression) and Lossabsdev (least absolute deviations regression).
• We will only work with L2 regularization, in which Penalty(w) = λ2 kwk2 .
• The linear predictor is specified by a weight vector w ∈ Rd , so that the prediction for regresion is fw (x) = w · φ(x) and fw (x) = sign(w · φ(x)) for binary
classification.
• The stochastic gradient descent (SGD) algorithm is an iterative algorithm. It repeatedly picks up an example (x, y) ∈ Dtrain and updates the weights in a way
to reduce Loss(x, y, w). This is done by computing the gradient and performing w ← w − ηt ∇w Loss(x, y, w), where ηt is the step size at iteration t. For
example, we can take ηt = 1/tα , where α is the reduction.

CS221 4
 Documentation

This demo allows you to create your own examples, feature extractors, and step through various learning algorithms.

• Problem definition

– trainExample(x, y), testExample(x, y): adds a training/test example with input x and output y (e.g., trainExample(’hello’, +1)).
– featureExtractor(func): adds a feature extractor func(ex, fv), which takes an example object ex = {x:x, y:y} and a feature vector fv, which
you can add features to by calling fv.add(feature, value).
• Learning algorithms

– roteLearning(opts): simply memorizes the training data.

– nearestNeighbors(opts): run the nearest neighbors algorithm.
– sgd(opts): run stochastic gradient descent on the opts.loss (which can be perceptron, hinge, logistic, squared, absdev). opts.lambda is the amount
of regularization. opts.steps is the number of steps to take at once. opts.reduction is the reduction for the step size. opts.ordered: if set to true,
don’t randomize order of training examples.

CS221 6