(a) (b) (c)

Figure 6: PCA: (a) the original data; (b) two principal components displayed as vectors; (c)
the data projected on the first principal component.

Consider a two-dimensional data as shown in fig. 6a. Principal components are vectors that
define a new coordinate system in which the first axis goes in the direction of the highest
variance in the data. The second axis is orthogonal to the first one and goes in the direction
of the second highest variance in the data. If our data was three-dimensional, the third axis
would be orthogonal to both the first and the second axes and go in the direction of the third
highest variance, and so on. In fig. 6b, the two principal components are shown as arrows.
The length of the arrow reflects the variance in this direction.
Now, if we want to reduce the dimensionality of our data to Dnew < D, we pick Dnew
largest principal components and project our data points on them. For our two-dimensional
illustration, we can set Dnew = 1 and project our examples to the first principal component
to obtain the orange points in fig. 6c.

To describe each orange point, we need only one coordinate instead

of two: the coordinate with respect to the first principal component.
When our data is very high-dimensional, it often happens in practice
that the first two or three principal components account for most of the
variation in the data, so by displaying the data on a 2D or 3D plot we
can indeed see a very high-dimensional data and its properties.

9.3.2 UMAP

The idea behind many of the modern dimensionality reduction algorithms, especially those
designed specifically for visualization purposes, such as t-SNE and UMAP, is basically
the same. We first design a similarity metric for two examples. For visualization purposes,
besides the Euclidean distance between the two examples, this similarity metric often reflects

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 15

some local properties of the two examples, such as the density of other examples around
them.
In UMAP, this similarity metric w is defined as follows,

def
w(xi , xj ) = wi (xi , xj ) + wj (xj , xi ) ≠ wi (xi , xj )wj (xj , xi ). (5)

The function wi (xi , xj ) is defined as,

3 4
def d(xi , xj ) ≠ fli
wi (xi , xj ) = exp ≠ ,
‡i

where d(xi , xj ) is the Euclidean distance between two examples, fli is the distance from xi
to its closest neighbor, and ‡i is the distance from xi to its k th closest neighbor (k is a
hyperparameter of the algorithm).
It can be shown that the metric in eq. 5 varies in the range from 0 to 1 and is symmetric,
which means that w(xi , xj ) = w(xj , xi ).
Let w denote the similarity of two examples in the original high dimensional space and let
wÕ be the similarity given by the same eq. 5 in the new low-dimensional space. Because the
values of w and wÕ lie in the range between 0 and 1, we can see them as two probability
distributions. A widely used metric of similarity between two probability distributions is
cross-entropy:

A B A B
w(xi , xj ) 1 ≠ w(xi , xj )
N ÿ
ÿ N
C(w, wÕ ) = w(xi , xj ) ln + (1 ≠ w(xi , xj )) ln , (6)
i=1 j=1
wÕ (xiÕ , xjÕ ) 1 ≠ wÕ (xiÕ , xjÕ )

where xÕ is the low-dimensional “version” of the original high-dimensional example x.

As you can see from eq. 6, when w(xi , xj ) is similar to wÕ (xiÕ , xjÕ ), for all pairs (i, j), then
C(w, wÕ ) is minimized. And this is precisely what we want: for any two examples xi and
xj , we want their similarity metric in the original and the lower-dimensional spaces to be as
similar as possible.
In eq. 6 the unknown parameters are xiÕ (for all i = 1, . . . , N ) and we can compute them by
gradient descent by minimizing C(w, wÕ ).

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 16

 PCA UMAP Autoencoder
Figure 7: Dimensionality reduction of the MNIST dataset using three different techniques.

In fig. 7, you can see the result of dimensionality reduction applied to the MNIST dataset of
handwritten digits. MNIST is commonly used for benchmarking various image processing
systems; it contains 70,000 labeled examples. Ten different colors on the plot correspond to
ten classes. Each point on the plot corresponds a specific example in the dataset. As you can
see, UMAP separates examples visually better (remember, it doesn’t have access to labels).
In practice, UMAP is slightly slower than PCA but faster than autoencoder.

9.4 Outlier Detection

Outlier detection is the problem of detecting in the dataset the examples that are very
different from what a typical example in the dataset looks like. We have already seen several
techniques that could help to solve this problem: autoencoder and one-class classifier learning.
If we use autoencoder, we train it on our dataset. Then, if we want to predict whether an
example is an outlier, we can use the autoencoder model to reconstruct the example from
the bottleneck layer. The model will unlikely be capable of reconstructing an outlier.
In one-class classification, the model either predicts that the input example belongs to the
class, or it’s an outlier.

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 17

 The
Hundred-
Page
Machine
Learning
Book
Andriy Burkov
 “All models are wrong, but some are useful.”
— George Box

The book is distributed on the “read first, buy later” principle.

Andriy Burkov The Hundred-Page Machine Learning Book - Draft

10 Other Forms of Learning

10.1 Metric Learning

I mentioned that the most frequently used metrics of similarity (or dissimilarity) between
two feature vectors are Euclidean distance and cosine similarity. Such choices of metric
seem logical but arbitrary, just like the choice of the squared error in linear regression. The
fact that one metric can work better than another depending on the dataset is an indicator
that none of them is perfect.
You can create your metric that would work better for your dataset. It’s then possible to
integrate your metric into any learning algorithm that needs a metric, like k-means or kNN.
How can you know, without trying all possibilities, which equation would be a good metric?
You can train your metric from data.
Remember the Euclidean distance between two feature vectors x and xÕ :

def  
d(x, xÕ ) = (x ≠ xÕ )2 = (x ≠ xÕ )(x ≠ xÕ ).

We can slightly modify this metric to make it parametrizable and then learn these parameters
from data. Consider the following modification:
Ò
def
dA (x, xÕ ) = Îx ≠ xÕ ÎA = (x ≠ xÕ )€ A(x ≠ xÕ ),

where A is a D ◊ D matrix. Let’s say D = 3. If we let A be the identity matrix,

S T
1 0 0
def
A = U0 1 0V ,
0 0 1

then dA becomes the Euclidean distance. If we have a general diagonal matrix, like this,
S T
2 0 0
def
A = U0 8 0V ,
0 0 1

then different dimensions have different importance in the metric. (In the above example,
the second dimension is the most important in the metric calculation.) More generally, to be
called a metric a function of two variables has to satisfy three conditions:

1. d(x, xÕ ) Ø 0 nonnegativity
2. d(x, xÕ ) Æ d(x, xÕ ) + d(xÕ , z) triangle inequality
3. d(x, xÕ ) = d(xÕ , x) symmetry

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 3

To satisfy the first two conditions, the matrix A has to be positive semidefinite. You can
see a positive semidefinite matrix as the generalization of the notion of a nonnegative real
number to matrices. Any positive semidefinite matrix M satisfies:

z€ Mz Ø 0.

The above property follows from the definition of a positive semidefinite matrix. The proof
that the second condition is satisfied when the matrix A is positive semidefinite can be found
on the book’s companion website.
To satisfy the third condition, we can simply take (d(x, xÕ ) + d(xÕ , x))/2.
Let’s say we have an unannotated set X = {xi }N i=1 . To build the training data for our
metric learning problem, we manually create two sets. The first set S is such that a pair of
examples (xi , xk ) belongs to set S if xi and xk are similar (from our subjective perspective).
The second set D is such that a pair of examples (xi , xk ) belongs to set D if xi and xk are
dissimilar.
To train the matrix of parameters A from the data, we want to find a positive semidefinite
matrix A that solves the following optimization problem:

ÿ ÿ
min Îx ≠ xÕ Î2A such that Îx ≠ xÕ ÎA Ø c,
A
(xi ,xk )œS (xi ,xk )œD

where c is a positive constant (can be any number).

The solution to this optimization problem is found by gradient descent

with a modification that ensures that the found matrix A is positive
semidefinite. We leave the description of the algorithm out of the scope
of this book for further reading. You should know that there are many
other ways to learn a metric, including non-linear and kernel-based.
However, the one presented in this book gives a good result for most
practical problems.

10.2 Learning to Rank

Learning to rank is a supervised learning problem. Among others, one frequent problem
solved using learning to rank is the optimization of search results returned by a search engine
for a query. In search result ranking optimization, a labeled example Xi in the training set
of size N is a ranked collection of documents of size ri (labels are ranks of documents). A
feature vector represents each document in the collection. The goal of the learning is to find
a ranking function f which outputs values that can be used to rank documents. For each

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 4

training example, an ideal function f would output values that induce the same ranking of
documents as given by labels.
Each example Xi , i = 1, . . . , N , is a collection of feature vectors with labels: Xi =
{(xi,j , yi,j )}rj=1
i
. Features in a feature vector xi,j represent the document j = 1, . . . , ri .
(1) (2)
For example, xi,j could represent how recent is the document, xi,j would reflect whether the
(3)
words of the query can be found in the document title, xi,j could represent the size of the
document, and so on. The label yi,j could be the rank (1, 2, . . . , ri ) or a score. For example,
the lower the score, the higher the document should be ranked.
There are three principal approaches to solve such a learning problem: pointwise, pairwise,
and listwise.
Pointwise approach transforms each training example into multiple examples: one example
per document. The learning problem becomes a standard supervised learning problem, either
regression or logistic regression. In each example (x, y) of the pointwise learning problem,
x is the feature vector of some document, and y is the original score (if yi,j is a score) or a
synthetic score obtained from the ranking (the higher the rank, the lower is the synthetic
score). Any supervised learning algorithm can be used in this case. The solution is usually
far from perfect. Principally, this is because each document is considered in isolation, while
the original ranking (given by the labels yi,j of the original training set) could optimize the
positions of the whole set of documents. For example, if we have already given a high rank to
a Wikipedia page in some collection of documents, we would not give a high rank to another
Wikipedia page for the same query.
In the pairwise approach, the problem also considers documents in isolation, however, in this
case, a pair of documents is considered at once. Given a pair of documents (xi , xk ) we want
to build a model f that, given (xi , xk ) as input, outputs a value close to 1 if xi has to be put
higher than xk in the ranking. Otherwise, f outputs a value close to 0. At the test time,
given a model, the final ranking for an unlabeled example X is obtained by aggregating the
predictions for all pairs of documents in X . Such an approach works better than pointwise,
but still far from perfect.
The state of the art rank learning algorithms, such as LambdaMART, implement the
listwise approach. In the listwise approach, we try to optimize the model directly on some
metric that reflects the quality of ranking. There are various metrics for assessing search
engine result ranking, including precision and recall. One popular metric that combines both
precision and recall is called mean average precision (MAP).
To define MAP, let us ask judges (Google call those people rankers) to examine a collection
of search results for a query and assign relevancy labels to each search result. Labels could
be binary (1 for “relevant” and 0 for “irrelevant”) or on some scale, say from 1 to 5: the
higher the value, the more relevant the document is to the search query. Let our judges build
such relevancy labeling for a collection of 100 queries. Now, let us test our ranking model on
this collection. The precision of our model for some query is given by:

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 5

 |{relevant documents} fl {retrieved documents}|
precision = ,
|{retrieved documents}|

where the notation | · | means “the number of.” The average precision metric, AveP, is
defined for a ranked collection of documents returned by a search engine for a query q as,
qn
k=1 (P (k)
◊ rel(k))
AveP(q) = ,
|{relevant documents}|

where n is the number of retrieved documents, P (k) denotes the precision computed for
the top k search results returned by our ranking model for the query, rel(k) is an indicator
function equaling 1 if the item at rank k is a relevant document (according to judges) and
zero otherwise. Finally, the MAP for a collection of search queries of size Q is given by,

qQ
AveP(q)
MAP =
q=1
.
Q

Now we get back to LambdaMART. This algorithm implements a pairwise approach, and it
uses gradient boosting to train the ranking function h(x). Then the binary model f (xi , xk )
that predicts whether the document xi should have a higher rank than the document xk (for
the same search query) is given by a sigmoid with a hyperparameter –,

def 1
f (xi , xk ) = .
1 + exp((h(xi ) ≠ h(xk ))–

Again, as with many models that predict probability, the cost function is cross-entropy
computed using the model f . In our gradient boosting, we combine multiple regression trees
to build the function h by trying to minimize the cost. Remember that in gradient boosting
we add a tree to the model to reduce the error that the current model makes on the training
data. For the classification problem, we computed the derivative of the cost function to
replace real labels of training examples with these derivatives. LambdaMART works similarly,
with one exception. It replaces the real gradient with a combination of the gradient and
another factor that depends on the metric, such as MAP. This factor modifies the original
gradient by increasing or decreasing it so that the metric value is improved.
That is a very bright idea and not many supervised learning algorithms can boast that they
optimize a metric directly. Optimizing a metric is what we really want, but what we do in a
typical supervised learning algorithm is we optimize the cost instead of the metric. Usually,
in supervised learning, as soon as we have found a model that optimizes the cost function, we
try to tweak hyperparameters to improve the value of the metric. LambdaMART optimizes
the metric directly.

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 6

The remaining question is how do we build the ranked list of results based on the predictions
of the model f which predicts whether its first input has to be ranked higher than the second
input. It’s generally a computationally hard problem, and there are multiple implementations
of rankers capable of transforming pairwise comparisons into a ranking list. The most
straightforward approach is to use an existing sorting algorithm.

Sorting algorithms sort a collection of numbers in increasing or decreas-

ing order. (The simplest sorting algorithm is called bubble sort. It’s
usually taught in engineering schools.) Typically, sorting algorithms
iteratively compare a pair of numbers in the collection and change their
positions in the list based on the result of that comparison. If we plug
our function f into a sorting algorithm to execute this comparison, the
sorting algorithm will sort documents and not numbers.

10.3 Learning to Recommend

Leaning to recommend is an approach to build recommender systems. Usually, we have a

user who consumes some content. We have the history of consumption, and we want to
suggest this user new content that the user would like. It could be a movie on Netflix or a
book on Amazon.
Traditionally, two approaches were used to give recommendations: content-based filtering
and collaborative filtering.
Content-based filtering is based on learning what do users like based on the description of
the content they consume. For example, if the user of a news site often reads news articles on
science and technology, then we would suggest to this user more documents on science and
technology. More generally, we could create one training set per user and add news articles
to this dataset as a feature vector x and whether the user recently read this news article as a
label y. Then we build the model of each user and can regularly examine each new piece of
content to determine whether a specific user would read it or not.
The content-based approach has many limitations. For example, the user can be trapped in
the so-called filter bubble: the system will always suggest to that user the information that
looks very similar to what user already consumed. That could result in complete isolation of
the user from information that disagrees with their viewpoints or expands them. On a more
practical side, the users might just get recommendations of items they already know about,
which is undesirable.
Collaborative filtering has a significant advantage over content-based filtering: the recommen-
dations to one user are computed based on what other users consume or rate. For instance,
if two users gave high ratings to the same ten movies, then it’s more likely that user 1 will
appreciate new movies recommended based on the tastes of the user 2 and vice versa. The
drawback of this approach is that the content of the recommended items is ignored.

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 7

In collaborative filtering, the information on user preferences is organized in a matrix. Each
row corresponds to a user, and each column corresponds to a piece of content that user rated
or consumed. Usually, this matrix is huge and extremely sparse, which means that most of
its cells aren’t filled (or filled with a zero). The reason for such a sparsity is that most users
consume or rate just a tiny fraction of available content items. It’s is very hard to make
meaningful recommendations based on such sparse data.
Most real-world recommender systems use a hybrid approach: they combine recommendations
obtained by the content-based and collaborative filtering models.
I already mentioned that content-based recommender model could be built using a classifica-
tion or regression model that predicts whether a user will like the content based on content’s
features. Examples of features could include the words in books or news articles the user
liked, the price, the recency of the content, the identity of the content author and so on.
Two effective collaborative-filtering learning algorithms are factorization machines (FM)
and denoising autoencoders (DAE).

10.3.1 Factorization Machines

Factorization machines is a relatively new kind of algorithm. It was explicitly designed for
sparse datasets. Let’s illustrate the problem.

user movie rated movies

Ed Al Zak ... It Up Jaws Her It Up Jaws Her

x1 x2 x3 ... x21 x22 x23 x24 ... x40 x41 x42 x43 ... x99 x100 y

x(1) 1 0 0 ... 1 0 0 0 ... 0.2 0.8 0.4 0 ... 0.3 0.8 1 y(1)

x(2) 1 0 0 ... 0 1 0 0 ... 0.2 0.8 0.4 0 ... 0.3 0.8 3 y(2)

x(3) 1 0 0 ... 0 0 1 0 ... 0.2 0.8 0.4 0.7 ... 0.3 0.8 2 y(3)

x(4) 0 1 0 ... 0 0 1 0 ... 0 0 0.7 0.1 ... 0.35 0.78 3 y(4)

x(5) 0 1 0 ... 0 0 0 1 ... 0 0 0.7 0.1 ... 0.35 0.78 1 y(5)

x(6) 0 0 1 ... 1 0 0 0 ... 0.8 0 0 0.6 ... 0.5 0.77 4 y(6)

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

x(D) 0 0 0 ... 0 0 1 0 ... 0 0 1 0 ... 0.95 0.85 5 y(D)

Figure 1: Example for sparse feature vectors x and their respective labels y.

In fig. 1 you see an example of sparse feature vectors with labels. Each feature vector

Andriy Burkov The Hundred-Page Machine Learning Book - Draft 8