Chapter 5
Machine Learning Basics
Deep learning is a specific kind of machine learning. To understand deep learning
well, one must have a solid understanding of the basic principles of machine learning.
This chapter provides a brief course in the most important general principles that
are applied throughout the rest of the book. Novice readers or those who want a
wider perspective are encouraged to consider machine learning textbooks with a
more comprehensive coverage of the fundamentals, such as Murphy (2012) or Bishop
(2006). If you are already familiar with machine learning basics, feel free to skip
ahead to section 5.11. That section covers some perspectives on traditional machine
learning techniques that have strongly influenced the development of deep learning
algorithms.
We begin with a definition of what a learning algorithm is and present an
example: the linear regression algorithm. We then proceed to describe how the
challenge of fitting the training data differs from the challenge of finding patterns
that generalize to new data. Most machine learning algorithms have settings
called hyperparameters, which must be determined outside the learning algorithm
itself; we discuss how to set these using additional data. Machine learning is
essentially a form of applied statistics with increased emphasis on the use of
computers to statistically estimate complicated functions and a decreased emphasis
on proving confidence intervals around these functions; we therefore present the
two central approaches to statistics: frequentist estimators and Bayesian inference.
Most machine learning algorithms can be divided into the categories of supervised
learning and unsupervised learning; we describe these categories and give some
examples of simple learning algorithms from each category. Most deep learning
algorithms are based on an optimization algorithm called stochastic gradient
96
CHAPTER 5. MACHINE LEARNING BASICS
descent. We describe how to combine various algorithm components, such as
an optimization algorithm, a cost function, a model, and a dataset, to build a
machine learning algorithm. Finally, in section 5.11, we describe some of the
factors that have limited the ability of traditional machine learning to generalize.
These challenges have motivated the development of deep learning algorithms that
overcome these obstacles.
5.1 Learning Algorithms
A machine learning algorithm is an algorithm that is able to learn from data.
But what do we mean by learning? Mitchell (1997) provides a succinct definition:
“A computer program is said to learn from experience
E
with respect to some
class of tasks
T
and performance measure
P
, if its performance at tasks in
T
, as
measured by
P
, improves with experience
E
.” One can imagine a wide variety of
experiences
E
, tasks
T
, and performance measures
P
, and we do not attempt in
this book to formally define what may be used for each of these entities. Instead,
in the following sections, we provide intuitive descriptions and examples of the
different kinds of tasks, performance measures, and experiences that can be used
to construct machine learning algorithms.
5.1.1 The Task, T
Machine learning enables us to tackle tasks that are too difficult to solve with
fixed programs written and designed by human beings. From a scientific and
philosophical point of view, machine learning is interesting because developing our
understanding of it entails developing our understanding of the principles that
underlie intelligence.
In this relatively formal definition of the word “task,” the process of learning
itself is not the task. Learning is our means of attaining the ability to perform the
task. For example, if we want a robot to be able to walk, then walking is the task.
We could program the robot to learn to walk, or we could attempt to directly write
a program that specifies how to walk manually.
Machine learning tasks are usually described in terms of how the machine
learning system should process an
example
. An example is a collection of
features
that have been quantitatively measured from some object or event that we want
the machine learning system to process. We typically represent an example as a
vector
x ∈ R
n
where each entry
x
i
of the vector is another feature. For example,
the features of an image are usually the values of the pixels in the image.
97
CHAPTER 5. MACHINE LEARNING BASICS
Many kinds of tasks can be solved with machine learning. Some of the most
common machine learning tasks include the following:
• Classification
: In this type of task, the computer program is asked to specify
which of
k
categories some input belongs to. To solve this task, the learning
algorithm is usually asked to produce a function
f
:
R
n
→ {
1
, . . . , k}
. When
y
=
f
(
x
), the model assigns an input described by vector
x
to a category
identified by numeric code
y
. There are other variants of the classification
task, for example, where
f
outputs a probability distribution over classes.
An example of a classification task is object recognition, where the input
is an image (usually described as a set of pixel brightness values), and the
output is a numeric code identifying the object in the image. For example,
the Willow Garage PR2 robot is able to act as a waiter that can recognize
different kinds of drinks and deliver them to people on command (Good-
fellow et al., 2010). Modern object recognition is best accomplished with
deep learning (Krizhevsky et al., 2012; Ioffe and Szegedy, 2015). Object
recognition is the same basic technology that enables computers to recognize
faces (Taigman et al., 2014), which can be used to automatically tag people
in photo collections and for computers to interact more naturally with their
users.
• Classification with missing inputs
: Classification becomes more chal-
lenging if the computer program is not guaranteed that every measurement in
its input vector will always be provided. To solve the classification task, the
learning algorithm only has to define a single function mapping from a vector
input to a categorical output. When some of the inputs may be missing,
rather than providing a single classification function, the learning algorithm
must learn a set of functions. Each function corresponds to classifying
x
with
a different subset of its inputs missing. This kind of situation arises frequently
in medical diagnosis, because many kinds of medical tests are expensive or
invasive. One way to efficiently define such a large set of functions is to
learn a probability distribution over all the relevant variables, then solve the
classification task by marginalizing out the missing variables. With
n
input
variables, we can now obtain all 2
n
different classification functions needed
for each possible set of missing inputs, but the computer program needs
to learn only a single function describing the joint probability distribution.
See Goodfellow et al. (2013b) for an example of a deep probabilistic model
applied to such a task in this way. Many of the other tasks described in this
section can also be generalized to work with missing inputs; classification
with missing inputs is just one example of what machine learning can do.
98
CHAPTER 5. MACHINE LEARNING BASICS
• Regression
: In this type of task, the computer program is asked to predict a
numerical value given some input. To solve this task, the learning algorithm
is asked to output a function
f
:
R
n
→ R
. This type of task is similar to
classification, except that the format of output is different. An example of
a regression task is the prediction of the expected claim amount that an
insured person will make (used to set insurance premiums), or the prediction
of future prices of securities. These kinds of predictions are also used for
algorithmic trading.
• Transcription
: In this type of task, the machine learning system is asked
to observe a relatively unstructured representation of some kind of data
and transcribe the information into discrete textual form. For example, in
optical character recognition, the computer program is shown a photograph
containing an image of text and is asked to return this text in the form of
a sequence of characters (e.g., in ASCII or Unicode format). Google Street
View uses deep learning to process address numbers in this way (Goodfellow
et al., 2014d). Another example is speech recognition, where the computer
program is provided an audio waveform and emits a sequence of characters or
word ID codes describing the words that were spoken in the audio recording.
Deep learning is a crucial component of modern speech recognition systems
used at major companies, including Microsoft, IBM and Google (Hinton
et al., 2012b).
• Machine translation
: In a machine translation task, the input already
consists of a sequence of symbols in some language, and the computer program
must convert this into a sequence of symbols in another language. This is
commonly applied to natural languages, such as translating from English to
French. Deep learning has recently begun to have an important impact on
this kind of task (Sutskever et al., 2014; Bahdanau et al., 2015).
• Structured output
: Structured output tasks involve any task where the
output is a vector (or other data structure containing multiple values) with
important relationships between the different elements. This is a broad
category and subsumes the transcription and translation tasks described
above, as well as many other tasks. One example is parsing—mapping a
natural language sentence into a tree that describes its grammatical structure
by tagging nodes of the trees as being verbs, nouns, adverbs, and so on.
See Collobert (2011) for an example of deep learning applied to a parsing
task. Another example is pixel-wise segmentation of images, where the
computer program assigns every pixel in an image to a specific category.
99
CHAPTER 5. MACHINE LEARNING BASICS
For example, deep learning can be used to annotate the locations of roads
in aerial photographs (Mnih and Hinton, 2010). The output form need
not mirror the structure of the input as closely as in these annotation-style
tasks. For example, in image captioning, the computer program observes an
image and outputs a natural language sentence describing the image (Kiros
et al., 2014a,b; Mao et al., 2015; Vinyals et al., 2015b; Donahue et al., 2014;
Karpathy and Li, 2015; Fang et al., 2015; Xu et al., 2015). These tasks
are called structured output tasks because the program must output several
values that are all tightly interrelated. For example, the words produced by
an image captioning program must form a valid sentence.
• Anomaly detection
: In this type of task, the computer program sifts
through a set of events or objects and flags some of them as being unusual
or atypical. An example of an anomaly detection task is credit card fraud
detection. By modeling your purchasing habits, a credit card company can
detect misuse of your cards. If a thief steals your credit card or credit card
information, the thief’s purchases will often come from a different probability
distribution over purchase types than your own. The credit card company
can prevent fraud by placing a hold on an account as soon as that card has
been used for an uncharacteristic purchase. See Chandola et al. (2009) for a
survey of anomaly detection methods.
• Synthesis and sampling
: In this type of task, the machine learning al-
gorithm is asked to generate new examples that are similar to those in the
training data. Synthesis and sampling via machine learning can be useful
for media applications when generating large volumes of content by hand
would be expensive, boring, or require too much time. For example, video
games can automatically generate textures for large objects or landscapes,
rather than requiring an artist to manually label each pixel (Luo et al., 2013).
In some cases, we want the sampling or synthesis procedure to generate a
specific kind of output given the input. For example, in a speech synthesis
task, we provide a written sentence and ask the program to emit an audio
waveform containing a spoken version of that sentence. This is a kind of
structured output task, but with the added qualification that there is no
single correct output for each input, and we explicitly desire a large amount
of variation in the output, in order for the output to seem more natural and
realistic.
• Imputation of missing values
: In this type of task, the machine learning
algorithm is given a new example
x ∈ R
n
, but with some entries
x
i
of
x
100
CHAPTER 5. MACHINE LEARNING BASICS
missing. The algorithm must provide a prediction of the values of the missing
entries.
• Denoising
: In this type of task, the machine learning algorithm is given as
input a corrupted example
˜
x ∈ R
n
obtained by an unknown corruption process
from a clean example
x ∈ R
n
. The learner must predict the clean example
x
from its corrupted version
˜
x
, or more generally predict the conditional
probability distribution p(x |
˜
x).
• Density estimation
or
probability mass function estimation
: In the
density estimation problem, the machine learning algorithm is asked to learn a
function
p
model
:
R
n
→ R
, where
p
model
(
x
) can be interpreted as a probability
density function (if
x
is continuous) or a probability mass function (if
x
is
discrete) on the space that the examples were drawn from. To do such a task
well (we will specify exactly what that means when we discuss performance
measures
P
), the algorithm needs to learn the structure of the data it has seen.
It must know where examples cluster tightly and where they are unlikely to
occur. Most of the tasks described above require the learning algorithm to at
least implicitly capture the structure of the probability distribution. Density
estimation enables us to explicitly capture that distribution. In principle,
we can then perform computations on that distribution to solve the other
tasks as well. For example, if we have performed density estimation to obtain
a probability distribution
p
(
x
), we can use that distribution to solve the
missing value imputation task. If a value
x
i
is missing, and all the other
values, denoted
x
−i
, are given, then we know the distribution over it is given
by
p
(
x
i
| x
−i
). In practice, density estimation does not always enable us to
solve all these related tasks, because in many cases the required operations
on p(x) are computationally intractable.
Of course, many other tasks and types of tasks are possible. The types of tasks
we list here are intended only to provide examples of what machine learning can
do, not to define a rigid taxonomy of tasks.
5.1.2 The Performance Measure, P
To evaluate the abilities of a machine learning algorithm, we must design a
quantitative measure of its performance. Usually this performance measure
P
is
specific to the task T being carried out by the system.
For tasks such as classification, classification with missing inputs, and tran-
scription, we often measure the
accuracy
of the model. Accuracy is just the
101
CHAPTER 5. MACHINE LEARNING BASICS
proportion of examples for which the model produces the correct output. We can
also obtain equivalent information by measuring the
error rate
, the proportion
of examples for which the model produces an incorrect output. We often refer to
the error rate as the expected 0-1 loss. The 0-1 loss on a particular example is 0
if it is correctly classified and 1 if it is not. For tasks such as density estimation,
it does not make sense to measure accuracy, error rate, or any other kind of 0-1
loss. Instead, we must use a different performance metric that gives the model
a continuous-valued score for each example. The most common approach is to
report the average log-probability the model assigns to some examples.
Usually we are interested in how well the machine learning algorithm performs
on data that it has not seen before, since this determines how well it will work when
deployed in the real world. We therefore evaluate these performance measures using
a
test set
of data that is separate from the data used for training the machine
learning system.
The choice of performance measure may seem straightforward and objective,
but it is often difficult to choose a performance measure that corresponds well to
the desired behavior of the system.
In some cases, this is because it is difficult to decide what should be measured.
For example, when performing a transcription task, should we measure the accuracy
of the system at transcribing entire sequences, or should we use a more fine-grained
performance measure that gives partial credit for getting some elements of the
sequence correct? When performing a regression task, should we penalize the
system more if it frequently makes medium-sized mistakes or if it rarely makes
very large mistakes? These kinds of design choices depend on the application.
In other cases, we know what quantity we would ideally like to measure, but
measuring it is impractical. For example, this arises frequently in the context of
density estimation. Many of the best probabilistic models represent probability
distributions only implicitly. Computing the actual probability value assigned to
a specific point in space in many such models is intractable. In these cases, one
must design an alternative criterion that still corresponds to the design objectives,
or design a good approximation to the desired criterion.
5.1.3 The Experience, E
Machine learning algorithms can be broadly categorized as
unsupervised
or
supervised
by what kind of experience they are allowed to have during the
learning process.
Most of the learning algorithms in this book can be understood as being allowed
102
CHAPTER 5. MACHINE LEARNING BASICS
to experience an entire
dataset
. A dataset is a collection of many examples, as
defined in section 5.1.1. Sometimes we call examples data points.
One of the oldest datasets studied by statisticians and machine learning re-
searchers is the Iris dataset (Fisher, 1936). It is a collection of measurements
of different parts of 150 iris plants. Each individual plant corresponds to one
example. The features within each example are the measurements of each part
of the plant: the sepal length, sepal width, petal length and petal width. The
dataset also records which species each plant belonged to. Three different species
are represented in the dataset.
Unsupervised learning algorithms
experience a dataset containing many
features, then learn useful properties of the structure of this dataset. In the context
of deep learning, we usually want to learn the entire probability distribution that
generated a dataset, whether explicitly, as in density estimation, or implicitly, for
tasks like synthesis or denoising. Some other unsupervised learning algorithms
perform other roles, like clustering, which consists of dividing the dataset into
clusters of similar examples.
Supervised learning algorithms
experience a dataset containing features,
but each example is also associated with a
label
or
target
. For example, the Iris
dataset is annotated with the species of each iris plant. A supervised learning
algorithm can study the Iris dataset and learn to classify iris plants into three
different species based on their measurements.
Roughly speaking, unsupervised learning involves observing several examples
of a random vector
x
and attempting to implicitly or explicitly learn the proba-
bility distribution
p
(
x
), or some interesting properties of that distribution; while
supervised learning involves observing several examples of a random vector
x
and
an associated value or vector
y
, then learning to predict
y
from
x
, usually by
estimating
p
(
y | x
). The term
supervised learning
originates from the view of
the target
y
being provided by an instructor or teacher who shows the machine
learning system what to do. In unsupervised learning, there is no instructor or
teacher, and the algorithm must learn to make sense of the data without this guide.
Unsupervised learning and supervised learning are not formally defined terms.
The lines between them are often blurred. Many machine learning technologies can
be used to perform both tasks. For example, the chain rule of probability states
that for a vector x ∈ R
n
, the joint distribution can be decomposed as
p(x) =
n
i=1
p(x
i
| x
1
, . . . , x
i−1
). (5.1)
This decomposition means that we can solve the ostensibly unsupervised problem of
103
CHAPTER 5. MACHINE LEARNING BASICS
modeling
p
(
x
) by splitting it into
n
supervised learning problems. Alternatively, we
can solve the supervised learning problem of learning
p
(
y | x
) by using traditional
unsupervised learning technologies to learn the joint distribution
p
(
x, y
), then
inferring
p(y | x) =
p(x, y)
y
p(x, y
)
. (5.2)
Though unsupervised learning and supervised learning are not completely formal
or distinct concepts, they do help roughly categorize some of the things we do with
machine learning algorithms. Traditionally, people refer to regression, classification
and structured output problems as supervised learning. Density estimation in
support of other tasks is usually considered unsupervised learning.
Other variants of the learning paradigm are possible. For example, in semi-
supervised learning, some examples include a supervision target but others do
not. In multi-instance learning, an entire collection of examples is labeled as
containing or not containing an example of a class, but the individual members
of the collection are not labeled. For a recent example of multi-instance learning
with deep models, see Kotzias et al. (2015).
Some machine learning algorithms do not just experience a fixed dataset. For
example,
reinforcement learning
algorithms interact with an environment, so
there is a feedback loop between the learning system and its experiences. Such
algorithms are beyond the scope of this book. Please see Sutton and Barto (1998)
or Bertsekas and Tsitsiklis (1996) for information about reinforcement learning,
and Mnih et al. (2013) for the deep learning approach to reinforcement learning.
Most machine learning algorithms simply experience a dataset. A dataset can
be described in many ways. In all cases, a dataset is a collection of examples,
which are in turn collections of features.
One common way of describing a dataset is with a design matrix. A design
matrix is a matrix containing a different example in each row. Each column of the
matrix corresponds to a different feature. For instance, the Iris dataset contains
150 examples with four features for each example. This means we can represent
the dataset with a design matrix
X ∈ R
150×4
, where
X
i,1
is the sepal length of
plant
i
,
X
i,2
is the sepal width of plant
i
, etc. We describe most of the learning
algorithms in this book in terms of how they operate on design matrix datasets.
Of course, to describe a dataset as a design matrix, it must be possible to
describe each example as a vector, and each of these vectors must be the same size.
This is not always possible. For example, if you have a collection of photographs
with different widths and heights, then different photographs will contain different
numbers of pixels, so not all the photographs may be described with the same
104
CHAPTER 5. MACHINE LEARNING BASICS
length of vector. In Section 9.7 and chapter 10, we describe how to handle different
types of such heterogeneous data. In cases like these, rather than describing the
dataset as a matrix with
m
rows, we describe it as a set containing
m
elements:
{x
(1)
, x
(2)
, . . . , x
(m)
}
. This notation does not imply that any two example vectors
x
(i)
and x
(j)
have the same size.
In the case of supervised learning, the example contains a label or target as
well as a collection of features. For example, if we want to use a learning algorithm
to perform object recognition from photographs, we need to specify which object
appears in each of the photos. We might do this with a numeric code, with 0
signifying a person, 1 signifying a car, 2 signifying a cat, and so forth. Often when
working with a dataset containing a design matrix of feature observations
X
, we
also provide a vector of labels y, with y
i
providing the label for example i.
Of course, sometimes the label may be more than just a single number. For
example, if we want to train a speech recognition system to transcribe entire
sentences, then the label for each example sentence is a sequence of words.
Just as there is no formal definition of supervised and unsupervised learning,
there is no rigid taxonomy of datasets or experiences. The structures described here
cover most cases, but it is always possible to design new ones for new applications.
5.1.4 Example: Linear Regression
Our definition of a machine learning algorithm as an algorithm that is capable
of improving a computer program’s performance at some task via experience is
somewhat abstract. To make this more concrete, we present an example of a
simple machine learning algorithm:
linear regression
. We will return to this
example repeatedly as we introduce more machine learning concepts that help to
understand the algorithm’s behavior.
As the name implies, linear regression solves a regression problem. In other
words, the goal is to build a system that can take a vector
x ∈ R
n
as input and
predict the value of a scalar
y ∈ R
as its output. The output of linear regression is
a linear function of the input. Let
ˆy
be the value that our model predicts
y
should
take on. We define the output to be
ˆy = w
x, (5.3)
where w ∈ R
n
is a vector of parameters.
Parameters are values that control the behavior of the system. In this case,
w
i
is
the coefficient that we multiply by feature
x
i
before summing up the contributions
from all the features. We can think of
w
as a set of
weights
that determine how
105
CHAPTER 5. MACHINE LEARNING BASICS
each feature affects the prediction. If a feature
x
i
receives a positive weight
w
i
,
then increasing the value of that feature increases the value of our prediction
ˆy
.
If a feature receives a negative weight, then increasing the value of that feature
decreases the value of our prediction. If a feature’s weight is large in magnitude,
then it has a large effect on the prediction. If a feature’s weight is zero, it has no
effect on the prediction.
We thus have a definition of our task
T
: to predict
y
from
x
by outputting
ˆy = w
x. Next we need a definition of our performance measure, P .
Suppose that we have a design matrix of
m
example inputs that we will not
use for training, only for evaluating how well the model performs. We also have
a vector of regression targets providing the correct value of
y
for each of these
examples. Because this dataset will only be used for evaluation, we call it the test
set. We refer to the design matrix of inputs as
X
(test)
and the vector of regression
targets as y
(test)
.
One way of measuring the performance of the model is to compute the
mean
squared error
of the model on the test set. If
ˆ
y
(test)
gives the predictions of the
model on the test set, then the mean squared error is given by
MSE
test
=
1
m
i
(
ˆ
y
(test)
− y
(test)
)
2
i
. (5.4)
Intuitively, one can see that this error measure decreases to 0 when
ˆ
y
(test)
=
y
(test)
.
We can also see that
MSE
test
=
1
m
||
ˆ
y
(test)
− y
(test)
||
2
2
, (5.5)
so the error increases whenever the Euclidean distance between the predictions
and the targets increases.
To make a machine learning algorithm, we need to design an algorithm that
will improve the weights
w
in a way that reduces
MSE
test
when the algorithm
is allowed to gain experience by observing a training set (
X
(train)
, y
(train)
). One
intuitive way of doing this (which we justify later, in section 5.5.1) is just to
minimize the mean squared error on the training set, MSE
train
.
To minimize MSE
train
, we can simply solve for where its gradient is 0:
∇
w
MSE
train
= 0 (5.6)
⇒ ∇
w
1
m
||
ˆ
y
(train)
− y
(train)
||
2
2
= 0 (5.7)
106
CHAPTER 5. MACHINE LEARNING BASICS
⇒
1
m
∇
w
||X
(train)
w − y
(train)
||
2
2
= 0 (5.8)
⇒ ∇
w
X
(train)
w − y
(train)
X
(train)
w − y
(train)
= 0 (5.9)
⇒ ∇
w
w
X
(train)
X
(train)
w − 2w
X
(train)
y
(train)
+ y
(train)
y
(train)
= 0
(5.10)
⇒ 2X
(train)
X
(train)
w − 2X
(train)
y
(train)
= 0 (5.11)
⇒ w =
X
(train)
X
(train)
−1
X
(train)
y
(train)
(5.12)
The system of equations whose solution is given by equation 5.12 is known as
the
normal equations
. Evaluating equation 5.12 constitutes a simple learning
algorithm. For an example of the linear regression learning algorithm in action,
see figure 5.1.
It is worth noting that the term
linear regression
is often used to refer to
a slightly more sophisticated model with one additional parameter—an intercept
term b. In this model
ˆy = w
x + b, (5.13)
so the mapping from parameters to predictions is still a linear function but the
mapping from features to predictions is now an affine function. This extension to
−1.0 −0.5 0.0 0.5 1.0
x
1
−3
−2
−1
0
1
2
3
y
Linear regression example
0.5 1.0 1.5
w
1
0.20
0.25
0.30
0.35
0.40
0.45
0.50
0.55
MSE
(train)
Optimization of w
Figure 5.1: A linear regression problem, with a training set consisting of ten data points,
each containing one feature. Because there is only one feature, the weight vector
w
contains only a single parameter to learn,
w
1
. (Left)Observe that linear regression learns
to set
w
1
such that the line
y
=
w
1
x
comes as close as possible to passing through all the
training points. (Right)The plotted point indicates the value of
w
1
found by the normal
equations, which we can see minimizes the mean squared error on the training set.
107
CHAPTER 5. MACHINE LEARNING BASICS
affine functions means that the plot of the model’s predictions still looks like a
line, but it need not pass through the origin. Instead of adding the bias parameter
b
, one can continue to use the model with only weights but augment
x
with an
extra entry that is always set to 1. The weight corresponding to the extra 1 entry
plays the role of the bias parameter. We frequently use the term “linear” when
referring to affine functions throughout this book.
The intercept term
b
is often called the
bias