ML (basic)

The Hundred-Page Machine Learning Book

Andriy Burkov

---

Preface

Let’s start by telling the truth: machines don’t learn. What a typical “learning machine” does, is finding a mathematical formula, which, when applied to a collection of inputs (called “training data”), produces the desired outputs. This mathematical formula also generates the correct outputs for most other inputs (distinct from the training data) on the condition that those inputs come from the same or a similar statistical distribution as the one the training data was drawn from.

Why isn’t that learning? Because if you slightly distort the inputs, the output is very likely to become completely wrong. It’s not how learning in animals works. If you learned to play a video game by looking straight at the screen, you would still be a good player if someone rotates the screen slightly. A machine learning algorithm, if it was trained by “looking” straight at the screen, unless it was also trained to recognize rotation, will fail to play the game on a rotated screen.

So why the name “machine learning” then? The reason, as is often the case, is marketing: Arthur Samuel, an American pioneer in the field of computer gaming and artificial intelligence, coined the term in 1959 while at IBM. Similarly to how in the 2010s IBM tried to market the term “cognitive computing” to stand out from competition, in the 1960s, IBM used the new cool term “machine learning” to attract both clients and talented employees.

As you can see, just like artificial intelligence is not intelligence, machine learning is not learning. However, machine learning is a universally recognized term that usually refers to the science and engineering of building machines capable of doing various useful things without being explicitly programmed to do so. So, the word “learning” in the term is used by analogy with the learning in animals rather than literally.

---

Who This Book is For

This book contains only those parts of the vast body of material on machine learning developed since the 1960s that have proven to have a significant practical value. A beginner in machine learning will find in this book just enough details to get a comfortable level of understanding of the field and start asking the right questions.

Practitioners with experience can use this book as a collection of directions for further self-improvement. The book also comes in handy when brainstorming at the beginning of a project, when you try to answer the question whether a given technical or business problem is “machine-learnable” and, if yes, which techniques you should try to solve it.

---

How to Use This Book

If you are about to start learning machine learning, you should read this book from the beginning to the end. (It’s just a hundred pages, not a big deal.) If you are interested in a specific topic covered in the book and want to know more, most sections have a QR code. By scanning one of those QR codes with your phone, you will get a link to a page on the book’s companion wiki theMLbook.com with additional materials: recommended reads, videos, Q&As, code snippets, tutorials, and other bonuses.

The book’s wiki is continuously updated with contributions from the book’s author himself as well as volunteers from all over the world. So this book, like a good wine, keeps getting better after you buy it.

---

Chapter 1: Introduction

1.1 What is Machine Learning

Machine learning is a subfield of computer science that is concerned with building algorithms which, to be useful, rely on a collection of examples of some phenomenon. These examples can come from nature, be handcrafted by humans or generated by another algorithm.

Machine learning can also be defined as the process of solving a practical problem by:

1. Gathering a dataset
2. Algorithmically building a statistical model based on that dataset

That statistical model is assumed to be used somehow to solve the practical problem.

To save keystrokes, I use the terms “learning” and “machine learning” interchangeably.

1.2 Types of Learning

Learning can be supervised, semi-supervised, unsupervised and reinforcement.

1.2.1 Supervised Learning

In supervised learning, the dataset is the collection of labeled examples $\{({\mathbf{x}}_i,y_i){\}}_{i=1}^N$. Each element ${\mathbf{x}}_i$ among $N$ is called a feature vector. A feature vector is a vector in which each dimension $j=1,\dots ,D$ contains a value that describes the example somehow. That value is called a feature and is denoted as $x^{(j)}$.

For instance, if each example $\mathbf{x}$ in our collection represents a person, then:

• the first feature $x^{(1)}$ could contain height in cm
• the second feature $x^{(2)}$ could contain weight in kg
• $x^{(3)}$ could contain gender

For all examples in the dataset, the feature at position $j$ in the feature vector always contains the same kind of information. It means that if $x_i^{(2)}$ contains weight in kg in some example ${\mathbf{x}}_i$, then $x_k^{(2)}$ will also contain weight in kg in every example ${\mathbf{x}}_k$, for $k=1,\dots ,N$.

The label $y_i$ can be either:

• an element belonging to a finite set of classes $\{1,2,\dots ,C\}$
• a real number
• a more complex structure, like a vector, a matrix, a tree, or a graph

Unless otherwise stated, in this book $y_i$ is either one of a finite set of classes or a real number. You can see a class as a category to which an example belongs. For instance, if your examples are email messages and your problem is spam detection, then you have two classes $\{\text{spam},\text{not\_spam}\}$.

The goal of a supervised learning algorithm is to use the dataset to produce a model that takes a feature vector $\mathbf{x}$ as input and outputs information that allows deducing the label for this feature vector. For instance, the model created using the dataset of people could take as input a feature vector describing a person and output a probability that the person has cancer.

1.2.2 Unsupervised Learning

In unsupervised learning, the dataset is a collection of unlabeled examples $\{{\mathbf{x}}_i{\}}_{i=1}^N$. Again, $\mathbf{x}$ is a feature vector, and the goal of an unsupervised learning algorithm is to create a model that takes a feature vector $\mathbf{x}$ as input and either transforms it into another vector or into a value that can be used to solve a practical problem.

For example:

• In clustering, the model returns the id of the cluster for each feature vector in the dataset.
• In dimensionality reduction, the output of the model is a feature vector that has fewer features than the input $\mathbf{x}$.
• In outlier detection, the output is a real number that indicates how $\mathbf{x}$ is different from a “typical” example in the dataset.

1.2.3 Semi-Supervised Learning

In semi-supervised learning, the dataset contains both labeled and unlabeled examples. Usually, the quantity of unlabeled examples is much higher than the number of labeled examples. The goal of a semi-supervised learning algorithm is the same as the goal of the supervised learning algorithm. The hope here is that using many unlabeled examples can help the learning algorithm to find a better model.

1.2.4 Reinforcement Learning

Reinforcement learning is a subfield of machine learning where the machine “lives” in an environment and is capable of perceiving the state of that environment as a vector of features. The machine can execute actions in every state. Different actions bring different rewards and could also move the machine to another state of the environment. The goal of a reinforcement learning algorithm is to learn a policy.

A policy is a function $f$ (similar to the model in supervised learning) that takes the feature vector of a state as input and outputs an optimal action to execute in that state. The action is optimal if it maximizes the expected average reward.

Reinforcement learning solves a particular kind of problems where decision making is sequential, and the goal is long-term, such as game playing, robotics, resource management, or logistics. In this book, I put emphasis on one-shot decision making where input examples are independent of one another and the predictions made in the past. I leave reinforcement learning out of the scope of this book.

1.3 How Supervised Learning Works

In this section, I briefly explain how supervised learning works so that you have the picture of the whole process before we go into detail. I decided to use supervised learning as an example because it’s the type of machine learning most frequently used in practice.

The Supervised Learning Pipeline

Step 1: Gather the data. The data for supervised learning is a collection of pairs (input, output). Input could be anything, for example, email messages, pictures, or sensor measurements. Outputs are usually real numbers, or labels (e.g. “spam”, “not_spam”, “cat”, “dog”, “mouse”, etc).

Step 2: Define the problem. Let’s say the problem that you want to solve using supervised learning is spam detection. You gather the data, for example, 10,000 email messages, each with a label either “spam” or “not_spam” (you could add those labels manually or pay someone to do that for us).

Step 3: Convert examples to feature vectors. Now, you have to convert each email message into a feature vector.

The data analyst decides, based on their experience, how to convert a real-world entity, such as an email message, into a feature vector. One common way to convert a text into a feature vector, called bag of words, is to take a dictionary of English words (let’s say it contains 20,000 alphabetically sorted words) and stipulate that in our feature vector:

• the first feature is equal to 1 if the email message contains the word “a”; otherwise, this feature is 0;
• the second feature is equal to 1 if the email message contains the word “aaron”; otherwise, this feature equals 0;
• the feature at position 20,000 is equal to 1 if the email message contains the word “zulu”; otherwise, this feature is equal to 0.

You repeat the above procedure for every email message in our collection, which gives us 10,000 feature vectors (each vector having the dimensionality of 20,000) and a label (“spam”/“not_spam”).

Step 4: Transform labels to numbers. Some learning algorithms require transforming labels into numbers. For example, some algorithms require numbers like 0 (to represent the label “not_spam”) and 1 (to represent the label “spam”). The algorithm I use to illustrate supervised learning is called Support Vector Machine (SVM). This algorithm requires that the positive label (in our case it’s “spam”) has the numeric value of $+1$ (one), and the negative label (“not_spam”) has the value of $-1$ (minus one).

Step 5: Train the model. At this point, you have a dataset and a learning algorithm, so you are ready to apply the learning algorithm to the dataset to get the model.

The SVM Algorithm

SVM sees every feature vector as a point in a high-dimensional space (in our case, space is 20,000-dimensional). The algorithm puts all feature vectors on an imaginary 20,000-dimensional plot and draws an imaginary 20,000-dimensional line (a hyperplane) that separates examples with positive labels from examples with negative labels. In machine learning, the boundary separating the examples of different classes is called the decision boundary.

The hyperplane equation is given by two parameters, a real-valued vector $\mathbf{w}$ of the same dimensionality as our input feature vector $\mathbf{x}$, and a real number $b$ like this:

$\mathbf{wx}-b=0$

where the expression $\mathbf{wx}$ means:

$\mathbf{wx}=w^{(1)}{x}^{(1)}+w^{(2)}{x}^{(2)}+\dots +w^{(D)}{x}^{(D)}$

and $D$ is the number of dimensions of the feature vector $\mathbf{x}$.

The prediction for some input feature vector $\mathbf{x}$ is given like this:

$y=\mathrm{sign}(\mathbf{wx}-b)$

where sign is a mathematical operator that takes any value as input and returns $+1$ if the input is a positive number or $-1$ if the input is a negative number.

The goal of the learning algorithm — SVM in this case — is to leverage the dataset and find the optimal values ${\mathbf{w}}^{\ast }$ and $b^{\ast }$ for parameters $\mathbf{w}$ and $b$. Once the learning algorithm identifies these optimal values, the model $f(\mathbf{x})$ is then defined as:

$f(\mathbf{x})=\mathrm{sign}({\mathbf{w}}^{\ast }\mathbf{x}-b^{\ast })$

Therefore, to predict whether an email message is spam or not spam using an SVM model, you have to take a text of the message, convert it into a feature vector, then multiply this vector by ${\mathbf{w}}^{\ast }$, subtract $b^{\ast }$ and take the sign of the result. This will give us the prediction ($+1$ means “spam”, $-1$ means “not_spam”).

The SVM Optimization Problem

Now, how does the machine find ${\mathbf{w}}^{\ast }$ and $b^{\ast }$? It solves an optimization problem. Machines are good at optimizing functions under constraints.

The constraints. First of all, we want the model to predict the labels of our 10,000 examples correctly. Remember that each example $i=1,\dots ,10000$ is given by a pair $({\mathbf{x}}_i,y_i)$, where ${\mathbf{x}}_i$ is the feature vector of example $i$ and $y_i$ is its label that takes values either $-1$ or $+1$. So the constraints are naturally:

\mathbf{w}\mathbf{x}_i - b &\geq 1 \quad \text{if } y_i = +1 \\ \mathbf{w}\mathbf{x}_i - b &\leq -1 \quad \text{if } y_i = -1 \end{aligned}$$ **Margin maximization.** We would also prefer that the hyperplane separates positive examples from negative ones with the largest **margin**. The margin is the distance between the closest examples of two classes, as defined by the decision boundary. A large margin contributes to a better generalization, that is how well the model will classify new examples in the future. To achieve that, we need to minimize the Euclidean norm of $\mathbf{w}$ denoted by $\|\mathbf{w}\|$ and given by: $$\|\mathbf{w}\| = \sqrt{\sum_{j=1}^{D}(w^{(j)})^2}$$ So, the optimization problem that we want the machine to solve looks like this: $$\min_{\mathbf{w}, b} \|\mathbf{w}\| \quad \text{subject to } y_i(\mathbf{w}\mathbf{x}_i - b) \geq 1 \text{ for } i = 1, \ldots, N$$ The expression $y_i(\mathbf{w}\mathbf{x}_i - b) \geq 1$ is just a compact way to write the above two constraints. The solution of this optimization problem, given by $\mathbf{w}^*$ and $b^*$, is called the **statistical model**, or, simply, the **model**. The process of building the model is called **training**. For two-dimensional feature vectors, the problem and the solution can be visualized as shown in fig. 1. The blue and orange circles represent, respectively, positive and negative examples, and the line given by $\mathbf{w}\mathbf{x} - b = 0$ is the decision boundary. **Why does minimizing $\|\mathbf{w}\|$ give the highest margin?** Geometrically, the equations $\mathbf{w}\mathbf{x} - b = 1$ and $\mathbf{w}\mathbf{x} - b = -1$ define two parallel hyperplanes, as you see in fig. 1. The distance between these hyperplanes is given by $\frac{2}{\|\mathbf{w}\|}$, so the smaller the norm $\|\mathbf{w}\|$, the larger the distance between these two hyperplanes. That's how Support Vector Machines work. This particular version of the algorithm builds the so-called **linear model**. It's called linear because the decision boundary is a straight line (or a plane, or a hyperplane). SVM can also incorporate kernels that can make the decision boundary arbitrarily non-linear. ### Summary At this point, you should retain the following: any classification learning algorithm that builds a model implicitly or explicitly creates a decision boundary. The decision boundary can be straight, or curved, or it can have a complex form, or it can be a superposition of some geometrical figures. The form of the decision boundary determines the accuracy of the model (that is the ratio of examples whose labels are predicted correctly). The form of the decision boundary, the way it is algorithmically or mathematically computed based on the training data, differentiates one learning algorithm from another. In practice, there are two other essential differentiators of learning algorithms to consider: speed of model building and prediction processing time. In many practical cases, you would prefer a learning algorithm that builds a less accurate model fast. Additionally, you might prefer a less accurate model that is much quicker at making predictions. ## 1.4 Why the Model Works on New Data Why is a machine-learned model capable of predicting correctly the labels of new, previously unseen examples? To understand that, look at the plot in fig. 1. If two classes are separable from one another by a decision boundary, then, obviously, examples that belong to each class are located in two different subspaces which the decision boundary creates. **Statistical reasoning.** If the examples used for training were selected randomly, independently of one another, and following the same procedure, then, statistically, it is more likely that the new negative example will be located on the plot somewhere not too far from other negative examples. The same concerns the new positive example: it will likely come from the surroundings of other positive examples. In such a case, our decision boundary will still, with high probability, separate well new positive and negative examples from one another. For other, less likely situations, our model will make errors, but because such situations are less likely, the number of errors will likely be smaller than the number of correct predictions. **The role of training set size.** Intuitively, the larger is the set of training examples, the more unlikely that the new examples will be dissimilar to (and lie on the plot far from) the examples used for training. To minimize the probability of making errors on new examples, the SVM algorithm, by looking for the largest margin, explicitly tries to draw the decision boundary in such a way that it lies as far as possible from examples of both classes. The reader interested in knowing more about the learnability and understanding the close relationship between the model error, the size of the training set, the form of the mathematical equation that defines the model, and the time it takes to build the model is encouraged to read about the PAC learning. The PAC (for "probably approximately correct") learning theory helps to analyze whether and under what conditions a learning algorithm will probably output an approximately correct classifier. --- # Chapter 2: Notation and Definitions ## 2.1 Notation Let's start by revisiting the mathematical notation we all learned at school, but some likely forgot right after the prom. ### 2.1.1 Scalars, Vectors, and Sets A **scalar** is a simple numerical value, like $15$ or $-3.25$. Variables or constants that take scalar values are denoted by an italic letter, like $x$ or $a$. A **vector** is an ordered list of scalar values, called attributes. We denote a vector as a bold character, for example, $\mathbf{x}$ or $\mathbf{w}$. Vectors can be visualized as arrows that point to some directions as well as points in a multi-dimensional space. We denote an **attribute** of a vector as an italic value with an index, like this: $w^{(j)}$ or $x^{(j)}$. The index $j$ denotes a specific dimension of the vector, the position of an attribute in the list. The notation $x^{(j)}$ should not be confused with the power operator, like this $x^2$ (squared) or $x^3$ (cubed). If we want to apply a power operator, say square, to an indexed attribute of a vector, we write like this: $\left(x^{(j)}\right)^2$. A variable can have two or more indices, like this: $x_i^{(j)}$ or like this $x_{i,j}^{(k)}$. For example, in neural networks, we denote as $x_{l,u}^{(j)}$ the input feature $j$ of unit $u$ in layer $l$. A **set** is an unordered collection of unique elements. We denote a set as a calligraphic capital character, for example, $\mathcal{S}$. A set of numbers can be finite (include a fixed amount of values). In this case, it is denoted using accolades, for example, $\{1, 3, 18, 23, 235\}$. A set can be infinite and include all values in some interval. If a set includes all values between $a$ and $b$, including $a$ and $b$, it is denoted using brackets as $[a, b]$. If the set doesn't include the values $a$ and $b$, such a set is denoted using parentheses like this: $(a, b)$. A special set denoted $\mathbb{R}$ includes all numbers from minus infinity to plus infinity. **Set operations:** - When an element $x$ belongs to a set $\mathcal{S}$, we write $x \in \mathcal{S}$. - We can obtain a new set $\mathcal{S}_3$ as an **intersection** of two sets $\mathcal{S}_1$ and $\mathcal{S}_2$: $$\mathcal{S}_3 \leftarrow \mathcal{S}_1 \cap \mathcal{S}_2$$ For example: $\{1, 3, 5, 8\} \cap \{1, 8, 4\} = \{1, 8\}$ - We can obtain a new set $\mathcal{S}_3$ as a **union** of two sets $\mathcal{S}_1$ and $\mathcal{S}_2$: $$\mathcal{S}_3 \leftarrow \mathcal{S}_1 \cup \mathcal{S}_2$$ For example: $\{1, 3, 5, 8\} \cup \{1, 8, 4\} = \{1, 3, 4, 5, 8\}$ ### 2.1.2 Capital Sigma Notation The summation over a collection $X = \{x_1, x_2, \ldots, x_{n-1}, x_n\}$ or over the attributes of a vector $\mathbf{x} = [x^{(1)}, x^{(2)}, \ldots, x^{(m-1)}, x^{(m)}]$ is denoted like this: $$\sum_{i=1}^{n} x_i \stackrel{\mathrm{def}}{=} x_1 + x_2 + \ldots + x_{n-1} + x_n$$ or equivalently: $$\sum_{j=1}^{m} x^{(j)} \stackrel{\mathrm{def}}{=} x^{(1)} + x^{(2)} + \ldots + x^{(m-1)} + x^{(m)}$$ The notation $\stackrel{\mathrm{def}}{=}$ means "is defined as". ### 2.1.3 Capital Pi Notation A notation analogous to capital sigma is the capital pi notation. It denotes a product of elements in a collection or attributes of a vector: $$\prod_{i=1}^{n} x_i \stackrel{\mathrm{def}}{=} x_1 \cdot x_2 \cdot \ldots \cdot x_{n-1} \cdot x_n$$ where $a \cdot b$ means $a$ multiplied by $b$. Where possible, we omit $\cdot$ to simplify the notation, so $ab$ also means $a$ multiplied by $b$. ### 2.1.4 Operations on Sets A **derived set creation operator** looks like this: $$\mathcal{S}' \leftarrow \{x^2 \mid x \in \mathcal{S}, x > 3\}$$ This notation means that we create a new set $\mathcal{S}'$ by putting into it $x$ squared such that $x$ is in $\mathcal{S}$ and $x$ is greater than 3. The **cardinality operator** $|\mathcal{S}|$ returns the number of elements in set $\mathcal{S}$. ### 2.1.5 Operations on Vectors **Vector sum and difference.** The sum of two vectors $\mathbf{x} + \mathbf{z}$ is defined as the vector: $$\mathbf{x} + \mathbf{z} = [x^{(1)} + z^{(1)}, x^{(2)} + z^{(2)}, \ldots, x^{(m)} + z^{(m)}]$$ The difference of two vectors $\mathbf{x} - \mathbf{z}$ is defined analogously. **Scalar multiplication.** A vector multiplied by a scalar is a vector: $$\mathbf{x}c \stackrel{\mathrm{def}}{=} [cx^{(1)}, cx^{(2)}, \ldots, cx^{(m)}]$$ **Dot-product.** A dot-product of two vectors is a scalar: $$\mathbf{w}\mathbf{x} \stackrel{\mathrm{def}}{=} \sum_{i=1}^{m} w^{(i)} x^{(i)}$$ In some books, the dot-product is denoted as $\mathbf{w} \cdot \mathbf{x}$. The two vectors must be of the same dimensionality. Otherwise, the dot-product is undefined. **Matrix-vector multiplication.** The multiplication of a matrix $\mathbf{W}$ by a vector $\mathbf{x}$ gives another vector as a result. When vectors participate in operations on matrices, a vector is by default represented as a matrix with one column. Let our matrix be: $$\mathbf{W} = \begin{pmatrix} w^{(1,1)} & w^{(1,2)} & w^{(1,3)} \\ w^{(2,1)} & w^{(2,2)} & w^{(2,3)} \end{pmatrix}$$ Let our vector be $\mathbf{x} \stackrel{\mathrm{def}}{=} [x^{(1)}, x^{(2)}, x^{(3)}]$. Then $\mathbf{W}\mathbf{x}$ is a two-dimensional vector defined as: $$\mathbf{W}\mathbf{x} = \begin{pmatrix} w^{(1,1)} & w^{(1,2)} & w^{(1,3)} \\ w^{(2,1)} & w^{(2,2)} & w^{(2,3)} \end{pmatrix} \begin{pmatrix} x^{(1)} \\ x^{(2)} \\ x^{(3)} \end{pmatrix} \stackrel{\mathrm{def}}{=} \begin{pmatrix} w^{(1,1)}x^{(1)} + w^{(1,2)}x^{(2)} + w^{(1,3)}x^{(3)} \\ w^{(2,1)}x^{(1)} + w^{(2,2)}x^{(2)} + w^{(2,3)}x^{(3)} \end{pmatrix} = \begin{pmatrix} \mathbf{w}^{(1)}\mathbf{x} \\ \mathbf{w}^{(2)}\mathbf{x} \end{pmatrix}$$ If our matrix had, say, five rows, the result of the above product would be a five-dimensional vector. **Transpose.** When the vector is on the left side of the matrix in the multiplication, then it has to be transposed before we multiply it by the matrix. The transpose of the vector $\mathbf{x}$ denoted as $\mathbf{x}^\top$ makes a row vector out of a column vector: $$\mathbf{x} = \begin{pmatrix} x^{(1)} \\ x^{(2)} \end{pmatrix}, \quad \mathbf{x}^\top \stackrel{\mathrm{def}}{=} \begin{pmatrix} x^{(1)}, x^{(2)} \end{pmatrix}$$ **Left-multiplication.** The multiplication of the vector $\mathbf{x}$ by the matrix $\mathbf{W}$ is given by $\mathbf{x}^\top \mathbf{W}$: $$\mathbf{x}^\top \mathbf{W} = \begin{pmatrix} x^{(1)}, x^{(2)} \end{pmatrix} \begin{pmatrix} w^{(1,1)} & w^{(1,2)} & w^{(1,3)} \\ w^{(2,1)} & w^{(2,2)} & w^{(2,3)} \end{pmatrix} \stackrel{\mathrm{def}}{=} \begin{pmatrix} w^{(1,1)}x^{(1)} + w^{(2,1)}x^{(2)}, \\ w^{(1,2)}x^{(1)} + w^{(2,2)}x^{(2)}, \\ w^{(1,3)}x^{(1)} + w^{(2,3)}x^{(2)} \end{pmatrix}$$ We can only multiply a vector by a matrix if the vector has the same number of dimensions as the number of rows in the matrix. ### 2.1.6 Functions A **function** is a relation that associates each element $x$ of a set $\mathcal{X}$, the domain of the function, to a single element $y$ of another set $\mathcal{Y}$, the codomain of the function. A function usually has a name. If the function is called $f$, this relation is denoted $y = f(x)$ (read "$f$ of $x$"), the element $x$ is the argument or input of the function, and $y$ is the value of the function or the output. **Local and global minima.** We say that $f(x)$ has a **local minimum** at $x = c$ if $f(x) \geq f(c)$ for every $x$ in some open interval around $x = c$. An **interval** is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. An **open interval** does not include its endpoints and is denoted using parentheses. For example, $(0, 1)$ means greater than 0 and less than 1. The minimal value among all the local minima is called the **global minimum**. A **vector function**, denoted as $\mathbf{y} = \mathbf{f}(x)$, is a function that returns a vector $\mathbf{y}$. It can have a vector or a scalar argument. ### 2.1.7 Max and Arg Max Given a set of values $\mathcal{A} = \{a_1, a_2, \ldots, a_n\}$: - The operator $\max_{a \in \mathcal{A}} f(a)$ returns the highest value $f(a)$ for all elements in the set $\mathcal{A}$. - The operator $\arg\max_{a \in \mathcal{A}} f(a)$ returns the element of the set $\mathcal{A}$ that maximizes $f(a)$. Sometimes, when the set is implicit or infinite, we can write $\max_a f(a)$ or $\arg\max_a f(a)$. Operators $\min$ and $\arg\min$ operate in a similar manner. ### 2.1.8 Assignment Operator The expression $a \leftarrow f(x)$ means that the variable $a$ gets the new value: the result of $f(x)$. We say that the variable $a$ gets assigned a new value. Similarly, $\mathbf{a} \leftarrow [a_1, a_2]$ means that the two-dimensional vector $\mathbf{a}$ gets the value $[a_1, a_2]$. ### 2.1.9 Derivative and Gradient A **derivative** $f'$ of a function $f$ is a function or a value that describes how fast $f$ grows (or decreases). If the derivative is a constant value, like 5 or $-3$, then the function grows (or decreases) constantly at any point $x$ of its domain. If the derivative $f'$ is a function, then the function $f$ can grow at a different pace in different regions of its domain: - If the derivative $f'$ is positive at some point $x$, then the function $f$ grows at this point. - If the derivative of $f$ is negative at some $x$, then the function decreases at this point. - The derivative of zero at $x$ means that the function's slope at $x$ is horizontal. The process of finding a derivative is called **differentiation**. **Basic derivatives.** Derivatives for basic functions are known: | Function $f(x)$ | Derivative $f'(x)$ | |---|---| | $x^2$ | $2x$ | | $2x$ | $2$ | | $2$ (constant) | $0$ | If the function we want to differentiate is not basic, we can find its derivative using the **chain rule**. For example if $F(x) = f(g(x))$, where $f$ and $g$ are some functions, then: $$F'(x) = f'(g(x)) g'(x)$$ **Chain rule example.** For $F(x) = (5x + 1)^2$: - $g(x) = 5x + 1$ - $f(g(x)) = (g(x))^2$ By applying the chain rule: $$F'(x) = 2(5x + 1) \cdot g'(x) = 2(5x + 1) \cdot 5 = 50x + 10$$ **Gradient.** Gradient is the generalization of derivative for functions that take several inputs (or one input in the form of a vector or some other complex structure). A gradient of a function is a vector of **partial derivatives**. You can look at finding a partial derivative of a function as the process of finding the derivative by focusing on one of the function's inputs and by considering all other inputs as constant values. For example, if our function is defined as $f([x^{(1)}, x^{(2)}]) = a x^{(1)} + b x^{(2)} + c$, then the partial derivative of function $f$ with respect to $x^{(1)}$, denoted as $\frac{\partial f}{\partial x^{(1)}}$, is given by: $$\frac{\partial f}{\partial x^{(1)}} = a + 0 + 0 = a$$ where $a$ is the derivative of the function $a x^{(1)}$; the two zeroes are respectively derivatives of $b x^{(2)}$ and $c$, because $x^{(2)}$ is considered constant when we compute the derivative with respect to $x^{(1)}$, and the derivative of any constant is zero. Similarly: $$\frac{\partial f}{\partial x^{(2)}} = 0 + b + 0 = b$$ The **gradient** of function $f$, denoted as $\nabla f$ is given by the vector: $$\nabla f = \left[ \frac{\partial f}{\partial x^{(1)}}, \frac{\partial f}{\partial x^{(2)}} \right]$$ The chain rule works with partial derivatives too, as illustrated in Chapter 4. ## 2.2 Random Variable A **random variable**, usually written as an italic capital letter, like $X$, is a variable whose possible values are numerical outcomes of a random phenomenon. There are two types of random variables: discrete and continuous. A **discrete random variable** takes on only a countable number of distinct values such as $\{\text{red}, \text{yellow}, \text{blue}\}$ or $\{1, 2, 3, \ldots\}$. The probability distribution of a discrete random variable is described by a list of probabilities associated with each of its possible values. This list of probabilities is called **probability mass function (pmf)**. For example: $$\Pr(X = \text{red}) = 0.3, \quad \Pr(X = \text{yellow}) = 0.45, \quad \Pr(X = \text{blue}) = 0.25$$ Each probability in a probability mass function is a value greater than or equal to 0. The sum of probabilities equals 1. A **continuous random variable** takes an infinite number of possible values in some interval. Examples include height, weight, and time. Because the number of values of a continuous random variable $X$ is infinite, the probability $\Pr(X = c)$ for any $c$ is 0. Therefore, instead of the list of probabilities, the probability distribution of a continuous random variable (a continuous probability distribution) is described by a **probability density function (pdf)**. The pdf is a function whose codomain is nonnegative and the area under the curve is equal to 1. ### Expectation and Standard Deviation Let a discrete random variable $X$ have $k$ possible values $\{x_i\}_{i=1}^k$. The **expectation** of $X$ denoted as $\mathbb{E}[X]$ is given by: $$\mathbb{E}[X] \stackrel{\mathrm{def}}{=} \sum_{i=1}^{k} x_i \Pr(X = x_i) = x_1 \Pr(X = x_1) + x_2 \Pr(X = x_2) + \ldots + x_k \Pr(X = x_k)$$ where $\Pr(X = x_i)$ is the probability that $X$ has the value $x_i$ according to the pmf. The expectation of a random variable is also called the **mean**, **average** or **expected value** and is frequently denoted with the letter $\mu$. The expectation is one of the most important statistics of a random variable. Another important statistic is the **standard deviation**. For a discrete random variable, the standard deviation usually denoted as $\sigma$ is given by: $$\sigma \stackrel{\mathrm{def}}{=} \sqrt{\mathbb{E}[(X - \mu)^2]} = \sqrt{\Pr(X = x_1)(x_1 - \mu)^2 + \Pr(X = x_2)(x_2 - \mu)^2 + \ldots + \Pr(X = x_k)(x_k - \mu)^2}$$ where $\mu = \mathbb{E}[X]$. The expectation of a continuous random variable $X$ is given by: $$\mathbb{E}[X] \stackrel{\mathrm{def}}{=} \int_{\mathbb{R}} x f_X(x) \, dx \tag{2}$$ where $f_X$ is the pdf of the variable $X$ and $\int_{\mathbb{R}}$ is the integral of function $x f_X$. **Integral.** The integral is an equivalent of the summation over all values of the function when the function has a continuous domain. It equals the area under the curve of the function. The property of the pdf that the area under its curve is 1 mathematically means that: $$\int_{\mathbb{R}} f_X(x) \, dx = 1$$ Most of the time we don't know $f_X$, but we can observe some values of $X$. In machine learning, we call these values **examples**, and the collection of these examples is called a **sample** or a **dataset**. ## 2.3 Unbiased Estimators Because $f_X$ is usually unknown, but we have a sample $\mathcal{S}_X = \{x_i\}_{i=1}^N$, we often content ourselves not with the true values of statistics of the probability distribution, such as expectation, but with their **unbiased estimators**. We say that $\hat{\theta}(\mathcal{S}_X)$ is an unbiased estimator of some statistic $\theta$ calculated using a sample $\mathcal{S}_X$ drawn from an unknown probability distribution if $\hat{\theta}(\mathcal{S}_X)$ has the following property: $$\mathbb{E}\left[\hat{\theta}(\mathcal{S}_X)\right] = \theta$$ where $\hat{\theta}$ is a sample statistic, obtained using a sample $\mathcal{S}_X$ and not the real statistic $\theta$ that can be obtained only knowing $X$; the expectation is taken over all possible samples drawn from $X$. Intuitively, this means that if you can have an unlimited number of such samples as $\mathcal{S}_X$, and you compute some unbiased estimator, such as $\hat{\mu}$, using each sample, then the average of all these $\hat{\mu}$ equals the real statistic $\mu$ that you would get computed on $X$. It can be shown that an unbiased estimator of an unknown $\mathbb{E}[X]$ (given by either eq. 1 or eq. 2) is given by: $$\hat{\mu} = \frac{1}{N} \sum_{i=1}^{N} x_i$$ This is called in statistics the **sample mean**. ## 2.4 Bayes' Rule The **conditional probability** $\Pr(X = x | Y = y)$ is the probability of the random variable $X$ to have a specific value $x$ given that another random variable $Y$ has a specific value of $y$. The **Bayes' Rule** (also known as the Bayes' Theorem) stipulates that: $$\Pr(X = x | Y = y) = \frac{\Pr(Y = y | X = x) \Pr(X = x)}{\Pr(Y = y)}$$ ## 2.5 Parameter Estimation Bayes' Rule comes in handy when we have a model of $X$'s distribution, and this model $f_\theta$ is a function that has some parameters in the form of a vector $\theta$. An example of such a function could be the **Gaussian function** that has two parameters, $\mu$ and $\sigma$, and is defined as: $$f_\theta(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x - \mu)^2}{2\sigma^2}\right)$$ where $\theta \stackrel{\mathrm{def}}{=} [\mu, \sigma]$. This function has all the properties of a pdf. Therefore, we can use it as a model of an unknown distribution of $X$. We can update the values of parameters in the vector $\theta$ from the data using the Bayes' Rule: $$\Pr(\theta = \hat{\theta} | X = x) \propto \Pr(X = x | \theta = \hat{\theta}) \Pr(\theta = \hat{\theta})$$ If we have a sample $\mathcal{S}$ of $X$ and the set of possible values for $\theta$ is finite, we can easily estimate $\Pr(\theta = \hat{\theta})$ by applying Bayes' Rule iteratively, one example $x \in \mathcal{S}$ at a time. The initial value $\Pr(\theta = \hat{\theta})$ can be guessed such that: $$\sum_{\hat{\theta}} \Pr(\theta = \hat{\theta}) = 1$$ This guess of the probabilities for different $\hat{\theta}$ is called the **prior**. First, we compute $\Pr(\theta = \hat{\theta} | X = x_1)$ for all possible values $\hat{\theta}$. Then, before updating $\Pr(\theta = \hat{\theta} | X = x)$ once again, this time for $x = x_2 \in \mathcal{S}$ using the equation above, we replace the prior $\Pr(\theta = \hat{\theta})$ by the new estimate: $$\Pr(\theta = \hat{\theta}) \leftarrow \frac{1}{N} \sum_{x \in \mathcal{S}} \Pr(\theta = \hat{\theta} | X = x)$$ The best value of the parameters $\theta^*$ given one example is obtained using the **principle of maximum-likelihood**: $$\theta^* = \arg\max_{\theta} \prod_{i=1}^{N} \Pr(\theta = \hat{\theta} | X = x_i) \tag{4}$$ If the set of possible values for $\theta$ isn't finite, then we need to optimize eq. 4 directly using a numerical optimization routine, such as gradient descent, which we consider in Chapter 4. Usually, we optimize the natural logarithm of the right-hand side expression in eq. 4 because the logarithm of a product becomes the sum of logarithms and it's easier for the machine to work with the sum than with a product. ## 2.6 Classification vs. Regression **Classification** is a problem of automatically assigning a label to an unlabeled example. Spam detection is a famous example of classification. In machine learning, the classification problem is solved by a **classification learning algorithm** that takes a collection of labeled examples as inputs and produces a model that can take an unlabeled example as input and either directly output a label or output a number that can be used by the data analyst to deduce the label easily. An example of such a number is a probability. In a classification problem, a label is a member of a finite set of classes: - If the size of the set of classes is two ("sick"/"healthy", "spam"/"not_spam"), we talk about **binary classification** (also called binomial in some books). - **Multiclass classification** (also called multinomial) is a classification problem with three or more classes. While some learning algorithms naturally allow for more than two classes, others are by nature binary classification algorithms. There are strategies allowing to turn a binary classification learning algorithm into a multiclass one. **Regression** is a problem of predicting a real-valued label (often called a **target**) given an unlabeled example. Estimating house price valuation based on house features, such as area, the number of bedrooms, location and so on is a famous example of regression. ## 2.7 Model-Based vs. Instance-Based Learning Most supervised learning algorithms are **model-based**. We have already seen one such algorithm: SVM. Model-based learning algorithms use the training data to create a model that has parameters learned from the training data. In SVM, the two parameters we saw were $\mathbf{w}^*$ and $b^*$. After the model was built, the training data can be discarded. **Instance-based** learning algorithms use the whole dataset as the model. One instance-based algorithm frequently used in practice is **k-Nearest Neighbors (kNN)**. In classification, to predict a label for an input example the kNN algorithm looks at the close neighborhood of the input example in the space of feature vectors and outputs the label that it saw the most often in this close neighborhood. ## 2.8 Shallow vs. Deep Learning A **shallow learning algorithm** learns the parameters of the model directly from the features of the training examples. Most supervised learning algorithms are shallow. The notorious exceptions are neural network learning algorithms, specifically those that build neural networks with more than one layer between input and output. Such neural networks are called **deep neural networks**. In deep neural network learning (or, simply, deep learning), contrary to shallow learning, most model parameters are learned not directly from the features of the training examples, but from the outputs of the preceding layers. Don't worry if you don't understand what that means right now. We look at neural networks more closely in Chapter 6. --- # Chapter 3: Fundamental Algorithms In this chapter, I describe five algorithms which are not just the most known but also either very effective on their own or are used as building blocks for the most effective learning algorithms out there. ## 3.1 Linear Regression Linear regression is a popular regression learning algorithm that learns a model which is a linear combination of features of the input example. ### 3.1.1 Problem Statement We have a collection of labeled examples $\{(\mathbf{x}_i, y_i)\}_{i=1}^N$, where: - $N$ is the size of the collection - $\mathbf{x}_i$ is the $D$-dimensional feature vector of example $i = 1, \ldots, N$ - $y_i$ is a real-valued target - every feature $x_i^{(j)}$, $j = 1, \ldots, D$, is also a real number We want to build a model $f_{\mathbf{w}, b}(\mathbf{x})$ as a linear combination of features of example $\mathbf{x}$: $$f_{\mathbf{w}, b}(\mathbf{x}) = \mathbf{w}\mathbf{x} + b \tag{1}$$ where $\mathbf{w}$ is a $D$-dimensional vector of parameters and $b$ is a real number. The notation $f_{\mathbf{w}, b}$ means that the model $f$ is parametrized by two values: $\mathbf{w}$ and $b$. We will use the model to predict the unknown $y$ for a given $\mathbf{x}$ like this: $y \leftarrow f_{\mathbf{w}, b}(\mathbf{x})$. Two models parametrized by two different pairs $(\mathbf{w}, b)$ will likely produce two different predictions when applied to the same example. We want to find the optimal values $(\mathbf{w}^*, b^*)$. Obviously, the optimal values of parameters define the model that makes the most accurate predictions. You could have noticed that the form of our linear model in eq. 1 is very similar to the form of the SVM model. The only difference is the missing sign operator. The two models are indeed similar. However, the hyperplane in the SVM plays the role of the decision boundary: it's used to separate two groups of examples from one another. As such, it has to be as far from each group as possible. On the other hand, the hyperplane in linear regression is chosen to be as close to all training examples as possible. ### 3.1.2 Solution To get this latter requirement satisfied, the optimization procedure which we use to find the optimal values for $\mathbf{w}^*$ and $b^*$ tries to minimize the following expression: $$\frac{1}{N} \sum_{i=1}^{N} \left( f_{\mathbf{w}, b}(\mathbf{x}_i) - y_i \right)^2 \tag{2}$$ In mathematics, the expression we minimize or maximize is called an **objective function**, or, simply, an **objective**. The expression $(f(\mathbf{x}_i) - y_i)^2$ in the above objective is called the **loss function**. It's a measure of penalty for misclassification of example $i$. This particular choice of the loss function is called **squared error loss**. All model-based learning algorithms have a loss function and what we do to find the best model is we try to minimize the objective known as the **cost function**. In linear regression, the cost function is given by the average loss, also called the **empirical risk**. The average loss, or empirical risk, for a model, is the average of all penalties obtained by applying the model to the training data. **Why squared loss?** Why is the loss in linear regression a quadratic function? Why couldn't we get the absolute value of the difference between the true target $y_i$ and the predicted value $f(\mathbf{x}_i)$ and use that as a penalty? We could. Moreover, we also could use a cube instead of a square. Now you probably start realizing how many seemingly arbitrary decisions are made when we design a machine learning algorithm: we decided to use the linear combination of features to predict the target. However, we could use a square or some other polynomial to combine the values of features. We could also use some other loss function that makes sense. If we made different decisions about the form of the model, the form of the loss function, and about the choice of the algorithm that minimizes the average loss to find the best values of parameters, we would end up inventing a different machine learning algorithm. People invent new learning algorithms for one of the two main reasons: 1. The new algorithm solves a specific practical problem better than the existing algorithms. 2. The new algorithm has better theoretical guarantees on the quality of the model it produces. One practical justification of the choice of the linear form for the model is that it's simple. Why use a complex model when you can use a simple one? Another consideration is that linear models rarely overfit. **Overfitting** is the property of a model such that the model predicts very well labels of the examples used during training but frequently makes errors when applied to examples that weren't seen by the learning algorithm during training. **Why squared error mathematically?** In 1705, the French mathematician Adrien-Marie Legendre, who first published the sum of squares method for gauging the quality of the model stated that squaring the error before summing is convenient. The absolute value is not convenient, because it doesn't have a continuous derivative, which makes the function not smooth. Functions that are not smooth create unnecessary difficulties when employing linear algebra to find closed form solutions to optimization problems. Closed form solutions to finding an optimum of a function are simple algebraic expressions and are often preferable to using complex numerical optimization methods, such as gradient descent. Intuitively, squared penalties are also advantageous because they exaggerate the difference between the true target and the predicted one according to the value of this difference. We might also use the powers 3 or 4, but their derivatives are more complicated to work with. Finally, why do we care about the derivative of the average loss? Remember from algebra that if we can calculate the gradient of the function in eq. 2, we can then set this gradient to zero and find the solution to a system of equations that gives us the optimal values $\mathbf{w}^*$ and $b^*$. ## 3.2 Logistic Regression The first thing to say is that logistic regression is not a regression, but a classification learning algorithm. The name comes from statistics and is due to the fact that the mathematical formulation of logistic regression is similar to that of linear regression. I explain logistic regression on the case of binary classification. However, it can naturally be extended to multiclass classification. ### 3.2.1 Problem Statement In logistic regression, we still want to model $y_i$ as a linear function of $x_i$, however, with a binary $y_i$ this is not straightforward. The linear combination of features such as $\mathbf{w}\mathbf{x}_i + b$ is a function that spans from minus infinity to plus infinity, while $y_i$ has only two possible values. At the time where the absence of computers required scientists to perform manual calculations, they were eager to find a linear classification model. They figured out that if we define a negative label as 0 and the positive label as 1, we would just need to find a simple continuous function whose codomain is $(0, 1)$. In such a case, if the value returned by the model for input $\mathbf{x}$ is closer to 0, then we assign a negative label to $\mathbf{x}$; otherwise, the example is labeled as positive. One function that has such a property is the standard **logistic function** (also known as the **sigmoid function**): $$f(x) = \frac{1}{1 + e^{-x}}$$ where $e$ is the base of the natural logarithm (also called Euler's number; $e^x$ is also known as the $\exp(x)$ function in Excel and many programming languages). By looking at the graph of the standard logistic function, we can see how well it fits our classification purpose: if we optimize the values of $\mathbf{x}$ and $b$ appropriately, we could interpret the output of $f(\mathbf{x})$ as the probability of $y_i$ being positive. For example, if it's higher than or equal to the threshold 0.5 we would say that the class of $\mathbf{x}$ is positive; otherwise, it's negative. In practice, the choice of the threshold could be different depending on the problem. So our logistic regression model looks like this: $$f_{\mathbf{w}, b}(\mathbf{x}) = \frac{1}{1 + e^{-(\mathbf{w}\mathbf{x} + b)}} \tag{3}$$ You can see the familiar term $\mathbf{w}\mathbf{x} + b$ from linear regression. Now, how do we find the best values $\mathbf{w}^*$ and $b^*$ for our model? In linear regression, we minimized the empirical risk which was defined as the average squared error loss, also known as the mean squared error or MSE. ### 3.2.2 Solution In logistic regression, instead of using a squared loss and trying to minimize the empirical risk, we **maximize the likelihood** of our training set according to the model. In statistics, the **likelihood function** defines how likely the observation (an example) is according to our model. For instance, assume that we have a labeled example $(\mathbf{x}_i, y_i)$ in our training data. Assume also that we have found (guessed) some specific values $\hat{\mathbf{w}}$ and $\hat{b}$ of our parameters. If we now apply our model $f_{\mathbf{w}, \hat{b}}$ to $\mathbf{x}_i$ using eq. 3 we will get some value $0 < p < 1$ as output. If $y_i$ is the positive class, the likelihood of $y_i$ being the positive class, according to our model, is given by $p$. Similarly, if $y_i$ is the negative class, the likelihood of it being the negative class is given by $1 - p$. The optimization criterion in logistic regression is called **maximum likelihood**. Instead of minimizing the average loss, like in linear regression, we now maximize the likelihood of the training data according to our model: $$L_{\mathbf{w}, b} \stackrel{\mathrm{def}}{=} \prod_{i=1}^{N} f_{\mathbf{w}, b}(\mathbf{x}_i)^{y_i} (1 - f_{\mathbf{w}, b}(\mathbf{x}_i))^{(1 - y_i)} \tag{4}$$ The expression $f_{\mathbf{w}, b}(\mathbf{x})^{y_i}(1 - f_{\mathbf{w}, b}(\mathbf{x}))^{(1 - y_i)}$ may look scary but it's just a fancy mathematical way of saying: "$f_{\mathbf{w}, b}(\mathbf{x})$ when $y_i = 1$ and $(1 - f_{\mathbf{w}, b}(\mathbf{x}))$ otherwise". Indeed, if $y_i = 1$, then $(1 - f_{\mathbf{w}, b}(\mathbf{x}))^{(1 - y_i)}$ equals 1 because $(1 - y_i) = 0$ and we know that anything to power 0 equals 1. On the other hand, if $y_i = 0$, then $f_{\mathbf{w}, b}(\mathbf{x})^{y_i}$ equals 1 for the same reason. You may have noticed that we used the product operator $\prod$ in the objective function instead of the sum operator $\sum$ which was used in linear regression. It's because the likelihood of observing $N$ labels for $N$ examples is the product of likelihoods of each observation (assuming that all observations are independent of one another, which is the case). Because of the exp function used in the model, in practice, it's more convenient to maximize the **log-likelihood** instead of likelihood. The log-likelihood is defined like follows: $$\log L_{\mathbf{w}, b} \stackrel{\mathrm{def}}{=} \ln(L_{\mathbf{w}, b}) = \sum_{i=1}^{N} y_i \ln f_{\mathbf{w}, b}(\mathbf{x}) + (1 - y_i) \ln (1 - f_{\mathbf{w}, b}(\mathbf{x}))$$ Because $\ln$ is a strictly increasing function, maximizing this function is the same as maximizing its argument, and the solution to this new optimization problem is the same as the solution to the original problem. Contrary to linear regression, there's no closed form solution to the above optimization problem. A typical numerical optimization procedure used in such cases is gradient descent. ## 3.3 Decision Tree Learning A **decision tree** is an acyclic graph that can be used to make decisions. In each branching node of the graph, a specific feature $j$ of the feature vector is examined. If the value of the feature is below a specific threshold, then the left branch is followed; otherwise, the right branch is followed. As the leaf node is reached, the decision is made about the class to which the example belongs. ### 3.3.1 Problem Statement Like previously, we have a collection of labeled examples; labels belong to the set $\{0, 1\}$. We want to build a decision tree that would allow us to predict the class of an example given a feature vector. ### 3.3.2 Solution There are various formulations of the decision tree learning algorithm. In this book, we consider just one, called **ID3**. The optimization criterion, in this case, is the average log-likelihood: $$\frac{1}{N} \sum_{i=1}^{N} y_i \ln f_{ID3}(\mathbf{x}_i) + (1 - y_i) \ln (1 - f_{ID3}(\mathbf{x}_i)) \tag{5}$$ where $f_{ID3}$ is a decision tree. By now, it looks very similar to logistic regression. However, contrary to the logistic regression learning algorithm which builds a parametric model $f_{\mathbf{w}^*, b^*}$ by finding an optimal solution to the optimization criterion, the ID3 algorithm optimizes it approximately by constructing a non-parametric model: $$f_{ID3}(\mathbf{x}) \stackrel{\mathrm{def}}{=} \Pr(y = 1 | \mathbf{x})$$ **The ID3 algorithm** works as follows. Let $\mathcal{S}$ denote a set of labeled examples. In the beginning, the decision tree only has a start node that contains all examples: $\mathcal{S} \stackrel{\mathrm{def}}{=} \{(\mathbf{x}_i, y_i)\}_{i=1}^N$. Start with a constant model $f_{ID3}^{\mathcal{S}}$: $$f_{ID3}^{\mathcal{S}} = \frac{1}{|\mathcal{S}|} \sum_{(\mathbf{x}, y) \in \mathcal{S}} y \tag{6}$$ The prediction given by the above model, $f_{ID3}^{\mathcal{S}}(\mathbf{x})$, would be the same for any input $\mathbf{x}$. Then we search through all features $j = 1, \ldots, D$ and all thresholds $t$, and split the set $\mathcal{S}$ into two subsets: $$\begin{aligned} \mathcal{S}_{-} &\stackrel{\mathrm{def}}{=} \{(\mathbf{x}, y) \mid (\mathbf{x}, y) \in \mathcal{S}, x^{(j)} < t\} \\ \mathcal{S}_{+} &\stackrel{\mathrm{def}}{=} \{(\mathbf{x}, y) \mid (\mathbf{x}, y) \in \mathcal{S}, x^{(j)} \geq t\} \end{aligned}$$ The two new subsets would go to two new leaf nodes, and we evaluate, for all possible pairs $(j, t)$ how good the split with pieces $\mathcal{S}_{-}$ and $\mathcal{S}_{+}$ is. Finally, we pick the best such values $(j, t)$, split $\mathcal{S}$ into $\mathcal{S}_{+}$ and $\mathcal{S}_{-}$, form two new leaf nodes, and continue recursively on $\mathcal{S}_{+}$ and $\mathcal{S}_{-}$ (or quit if no split produces a model that's sufficiently better than the current one). **Split evaluation via entropy.** Now you should wonder what do the words "evaluate how good the split is" mean. In ID3, the goodness of a split is estimated by using the criterion called **entropy**. Entropy is a measure of uncertainty about a random variable. It reaches its maximum when all values of the random variables are equiprobable. Entropy reaches its minimum when the random variable can have only one value. The entropy of a set of examples $\mathcal{S}$ is given by: $$H(\mathcal{S}) = -f_{ID3}^{\mathcal{S}} \ln f_{ID3}^{\mathcal{S}} - (1 - f_{ID3}^{\mathcal{S}}) \ln (1 - f_{ID3}^{\mathcal{S}})$$ When we split a set of examples by a certain feature $j$ and a threshold $t$, the entropy of a split, $H(\mathcal{S}_{-}, \mathcal{S}_{+})$, is simply a weighted sum of two entropies: $$H(\mathcal{S}_{-}, \mathcal{S}_{+}) = \frac{|\mathcal{S}_{-}|}{|\mathcal{S}|} H(\mathcal{S}_{-}) + \frac{|\mathcal{S}_{+}|}{|\mathcal{S}|} H(\mathcal{S}_{+}) \tag{7}$$ So, in ID3, at each step, at each leaf node, we find a split that minimizes the entropy given by eq. 7 or we stop at this leaf node. **Stopping criteria.** The algorithm stops at a leaf node in any of the below situations: - All examples in the leaf node are classified correctly by the one-piece model (eq. 6). - We cannot find an attribute to split upon. - The split reduces the entropy less than some $\epsilon$ (the value for which has to be found experimentally). - The tree reaches some maximum depth $d$ (also has to be found experimentally). Because in ID3, the decision to split the dataset on each iteration is local (doesn't depend on future splits), the algorithm doesn't guarantee an optimal solution. The model can be improved by using techniques like backtracking during the search for the optimal decision tree at the cost of possibly taking longer to build a model. ## 3.4 Support Vector Machine We already considered SVM in the introduction, so this section only fills a couple of blanks. Two critical questions need to be answered: 1. What if there's noise in the data and no hyperplane can perfectly separate positive examples from negative ones? 2. What if the data cannot be separated using a plane, but could be separated by a higher-order polynomial? ### 3.4.1 Dealing with Noise To extend SVM to cases in which the data is not linearly separable, we introduce the **hinge loss function**: $$\max(0, 1 - y_i(\mathbf{w}\mathbf{x}_i - b))$$ The hinge loss function is zero if the constraints $a$ and $b$ are satisfied, in other words, if $\mathbf{w}\mathbf{x}_i$ lies on the correct side of the decision boundary. For data on the wrong side of the decision boundary, the function's value is proportional to the distance from the decision boundary. We then wish to minimize the following cost function: $$C \|\mathbf{w}\|^2 + \frac{1}{N} \sum_{i=1}^{N} \max(0, 1 - y_i(\mathbf{w}\mathbf{x}_i - b))$$ where the hyperparameter $C$ determines the tradeoff between increasing the size of the decision boundary and ensuring that each $\mathbf{x}_i$ lies on the correct side of the decision boundary. SVMs that optimize hinge loss are called **soft-margin SVMs**, while the original formulation is referred to as a **hard-margin SVM**. **Effect of the $C$ hyperparameter.** As you can see, for sufficiently high values of $C$, the second term in the cost function will become negligible, so the SVM algorithm will try to find the highest margin by completely ignoring misclassification. As we decrease the value of $C$, making classification errors is becoming more costly, so the SVM algorithm will try to make fewer mistakes by sacrificing the margin size. As we have already discussed, a larger margin is better for generalization. Therefore, $C$ regulates the tradeoff between classifying the training data well (minimizing empirical risk) and classifying future examples well (generalization). ### 3.4.2 Dealing with Inherent Non-Linearity SVM can be adapted to work with datasets that cannot be separated by a hyperplane in its original space. However, if we manage to transform the original space into a space of higher dimensionality, we could hope that the examples will become linearly separable in this transformed space. In SVMs, using a function to implicitly transform the original space into a higher dimensional space during the cost function optimization is called the **kernel trick**. **The kernel trick.** Let's see how the optimization algorithm for SVM finds the optimal values for $\mathbf{w}$ and $b$. The method traditionally used to solve the optimization problem in eq. 8 is the method of **Lagrange multipliers**. Instead of solving the original problem from eq. 8, it is convenient to solve an equivalent problem formulated like this: $$\max_{\alpha_1, \ldots, \alpha_N} \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{k=1}^{N} y_i \alpha_i (\mathbf{x}_i \mathbf{x}_k) y_k \alpha_k$$ subject to: $$\sum_{i=1}^{N} \alpha_i y_i = 0 \quad \text{and} \quad \alpha_i \geq 0, \quad i = 1, \ldots, N$$ where $\alpha_i$ are called **Lagrange multipliers**. When formulated like this, the optimization problem becomes a convex quadratic optimization problem, efficiently solvable by quadratic programming algorithms. Now, you could have noticed that in the above formulation, there is a term $\mathbf{x}_i \mathbf{x}_k$, and this is the only place where the feature vectors are used. If we want to transform our vector space into higher dimensional space, we need to transform $\mathbf{x}_i$ into $\phi(\mathbf{x}_i)$ and $\mathbf{x}_j$ into $\phi(\mathbf{x}_j)$ and then multiply $\phi(\mathbf{x}_i)$ and $\phi(\mathbf{x}_j)$. It would be very costly to do so. On the other hand, we are only interested in the result of the dot-product $\mathbf{x}_i \mathbf{x}_k$, which, as we know, is a real number. We don't care how this number was obtained as long as it's correct. By using the **kernel trick**, we can get rid of a costly transformation of original feature vectors into higher-dimensional vectors and avoid computing their dot-product. We replace that by a simple operation on the original feature vectors that gives the same result. **Kernel trick example.** For example, instead of transforming $(q_1, p_1)$ into $(q_1^2, \sqrt{2} q_1 p_1, p_1^2)$ and $(q_2, p_2)$ into $(q_2^2, \sqrt{2} q_2 p_2, p_2^2)$ and then computing the dot-product of $(q_1^2, \sqrt{2} q_1 p_1, p_1^2)$ and $(q_2^2, \sqrt{2} q_2 p_2, p_2^2)$ to obtain $(q_1^2 q_2^2 + 2 q_1 q_2 p_1 p_2 + p_1^2 p_2^2)$ we could find the dot-product between $(q_1, p_1)$ and $(q_2, p_2)$ to get $(q_1 q_2 + p_1 p_2)$ and then square it to get exactly the same result $(q_1^2 q_2^2 + 2 q_1 q_2 p_1 p_2 + p_1^2 p_2^2)$. That was an example of the kernel trick, and we used the **quadratic kernel**: $$k(\mathbf{x}_i, \mathbf{x}_k) \stackrel{\mathrm{def}}{=} (\mathbf{x}_i \mathbf{x}_k)^2$$ **Popular kernels.** Multiple kernel functions exist, the most widely used of which is the **RBF kernel**: $$k(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|^2}{2\sigma^2}\right)$$ where $\|\mathbf{x} - \mathbf{x}'\|^2$ is the squared Euclidean distance between two feature vectors. The Euclidean distance is given by: $$d(\mathbf{x}_i, \mathbf{x}_k) \stackrel{\mathrm{def}}{=} \sqrt{(x_i^{(1)} - x_k^{(1)})^2 + (x_i^{(2)} - x_k^{(2)})^2 + \ldots + (x_i^{(N)} - x_k^{(N)})^2} = \sqrt{\sum_{j=1}^{D} (x_i^{(j)} - x_k^{(j)})^2}$$ It can be shown that the feature space of the RBF (for "radial basis function") kernel has an infinite number of dimensions. By varying the hyperparameter $\sigma$, the data analyst can choose between getting a smooth or curvy decision boundary in the original space. ## 3.5 k-Nearest Neighbors **k-Nearest Neighbors (kNN)** is a non-parametric learning algorithm. Contrary to other learning algorithms that allow discarding the training data after the model is built, kNN keeps all training examples in memory. Once a new, previously unseen example $\mathbf{x}$ comes in, the kNN algorithm finds $k$ training examples closest to $\mathbf{x}$ and returns the majority label (in case of classification) or the average label (in case of regression). The closeness of two points is given by a distance function. For example, **Euclidean distance** seen above is frequently used in practice. Another popular choice of the distance function is the **negative cosine similarity**. Cosine similarity defined as: $$s(\mathbf{x}_i, \mathbf{x}_k) \stackrel{\mathrm{def}}{=} \cos(\angle(\mathbf{x}_i, \mathbf{x}_k)) = \frac{\sum_{j=1}^{D} x_i^{(j)} x_k^{(j)}}{\sqrt{\sum_{j=1}^{D} \left(x_i^{(j)}\right)^2} \sqrt{\sum_{j=1}^{D} \left(x_k^{(j)}\right)^2}}$$ is a measure of similarity of the directions of two vectors. If the angle between two vectors is 0 degrees, then two vectors point to the same direction, and cosine similarity is equal to 1. If the vectors are orthogonal, the cosine similarity is 0. For vectors pointing in opposite directions, the cosine similarity is $-1$. If we want to use cosine similarity as a distance metric, we need to multiply it by $-1$. Other popular distance metrics include **Chebychev distance**, **Mahalanobis distance**, and **Hamming distance**. The choice of the distance metric, as well as the value for $k$, are the choices the analyst makes before running the algorithm. So these are hyperparameters. **Cost function analysis.** A reasonable question is what is the cost function here? Surprisingly, this question has not been well studied in the literature, despite the algorithm's popularity since the earlier 1960s. The only attempt to analyze the cost function of kNN I'm aware of was undertaken by Li and Yang in 2003. Below, I outline their considerations. For simplicity, let's make our derivation under the assumptions of binary classification $(y \in \{0, 1\})$ with cosine similarity and normalized feature vectors. Under these assumptions, kNN does a locally linear classification with the vector of coefficients: $$\mathbf{w}_{\mathbf{x}} = \sum_{(\mathbf{x}', y') \in \mathcal{R}_k(\mathbf{x})} y' \mathbf{x}' \tag{9}$$ where $\mathcal{R}_k(\mathbf{x})$ is the set of $k$ nearest neighbors to the input example $\mathbf{x}$. The above equation says that we take the sum of all nearest neighbor feature vectors to some input vector $\mathbf{x}$ by ignoring those that have label 0. The classification decision is obtained by defining a threshold on the dot-product $\mathbf{w}_{\mathbf{x}} \mathbf{x}$ which, in the case of normalized feature vectors, is equal to the cosine similarity between $\mathbf{w}_{\mathbf{x}}$ and $\mathbf{x}$. Now, defining the cost function like this: $$L = -\sum_{(\mathbf{x}', y') \in \mathcal{R}_k(\mathbf{x})} y' \mathbf{x}' \mathbf{w}_{\mathbf{x}} + \frac{1}{2} \|\mathbf{w}\|^2$$ and setting the first order derivative of the right-hand side to zero yields the formula for the coefficient vector in eq. 9. --- # Chapter 4: Anatomy of a Learning Algorithm ## 4.1 Building Blocks of a Learning Algorithm You may have noticed by reading the previous chapter that each learning algorithm we saw consisted of three parts: 1. A loss function; 2. An optimization criterion based on the loss function (a cost function, for example); and 3. An optimization routine that leverages training data to find a solution to the optimization criterion. These are the building blocks of any learning algorithm. Some algorithms were designed to explicitly optimize a specific criterion (both linear and logistic regressions, SVM). Some others, including decision tree learning and kNN, optimize the criterion implicitly. Decision tree learning and kNN are among the oldest machine learning algorithms and were invented experimentally based on intuition, without a specific global optimization criterion in mind. By reading modern literature on machine learning, you often encounter references to **gradient descent** or **stochastic gradient descent**. These are two most frequently used optimization algorithms used in cases where the optimization criterion is differentiable. **Gradient descent** is an iterative optimization algorithm for finding the minimum of a function. To find a local minimum of a function using gradient descent, one starts at some random point and takes steps proportional to the negative of the gradient (or approximate gradient) of the function at the current point. Gradient descent can be used to find optimal parameters for linear and logistic regression, SVM and also neural networks which we consider later. For many models, such as logistic regression or SVM, the optimization criterion is convex. Convex functions have only one minimum, which is global. Optimization criteria for neural networks are not convex, but in practice even finding a local minimum suffices. ## 4.2 Gradient Descent In this section, I demonstrate how gradient descent finds the solution to a linear regression problem. ### Setting Up the Problem I use a dataset with only one feature. However, the optimization criterion will have two parameters: $w$ and $b$. We have data for 200 companies, so we have 200 training examples. The linear regression model looks like this: $$f(x) = wx + b$$ We want to minimize the following cost function: $$l = \frac{1}{N} \sum_{i=1}^{N} (y_i - (wx_i + b))^2$$ ### Step 1: Calculate the Partial Derivatives **Gradient descent starts with calculating the partial derivative for every parameter:** $$\begin{aligned} \frac{\partial l}{\partial w} &= \frac{1}{N} \sum_{i=1}^{N} -2 x_i (y_i - (wx_i + b)) \\ \frac{\partial l}{\partial b} &= \frac{1}{N} \sum_{i=1}^{N} -2 (y_i - (wx_i + b)) \end{aligned} \tag{1}$$ **Derivation using the chain rule.** To find the partial derivative of the term $(y_i - (wx + b))^2$ with respect to $w$ we applied the chain rule. Here, we have the chain $F = f_2(f_1)$ where $f_1 = y_i - (wx + b)$ and $f_2 = f_1^2$. To find a partial derivative of $F$ with respect to $w$ we have to: - First find the partial derivative of $F$ with respect to $f_2$ which is equal to $2(y_i - (wx + b))$ (from calculus, we know that $\frac{\partial x^2}{\partial x} = 2x$) - Then multiply it by the partial derivative of $y_i - (wx + b)$ with respect to $w$ which is equal to $-x$ So overall: $$\frac{\partial l}{\partial w} = \frac{1}{N} \sum_{i=1}^{N} -2 x_i (y_i - (wx_i + b))$$ In a similar way, the partial derivative of $l$ with respect to $b$, $\frac{\partial l}{\partial b}$, was calculated. ### Step 2: Initialize Parameters and Update We initialize $w_0 = 0$ and $b_0 = 0$ and then iterate through our training examples, each example having the form of $(x_i, y_i) = (\text{Spendings}_i, \text{Sales}_i)$. For each training example, we update $w$ and $b$ using our partial derivatives. The learning rate $\alpha$ controls the size of an update: $$\begin{aligned} w_i &\leftarrow \alpha \cdot \frac{-2 x_i (y_i - (w_{i-1} x_i + b_{i-1}))}{N} \\ b_i &\leftarrow \alpha \cdot \frac{-2 (y_i - (w_{i-1} x_i + b_{i-1}))}{N} \end{aligned} \tag{2}$$ where $w_i$ and $b_i$ denote the values of $w$ and $b$ after using the example $(x_i, y_i)$ for the update. One pass through all training examples is called an **epoch**. Typically, we need multiple epochs until we start seeing that the values for $w$ and $b$ don't change much; then we stop. ### Step 3: Implement in Python The function that updates the parameters $w$ and $b$ during one epoch is shown below: ```python def update_w_and_b(spendings, sales, w, b, alpha): dl_dw = 0.0 dl_db = 0.0 N = len(spendings) for i in range(N): dl_dw += -2 * spendings[i] * (sales[i] - (w * spendings[i] + b)) dl_db += -2 * (sales[i] - (w * spendings[i] + b)) # update w and b w = w - (1 / float(N)) * dl_dw * alpha b = b - (1 / float(N)) * dl_db * alpha return w, b ``` The function that loops over multiple epochs is shown below: ```python def train(spendings, sales, w, b, alpha, epochs): for e in range(epochs): w, b = update_w_and_b(spendings, sales, w, b, alpha) # log the progress if e % 400 == 0: print("epoch:", e, "loss:", avg_loss(spendings, sales, w, b)) return w, b ``` The function `avg_loss` in the above code snippet is a function that computes the mean squared error: ```python def avg_loss(spendings, sales, w, b): N = len(spendings) total_error = 0.0 for i in range(N): total_error += (sales[i] - (w * spendings[i] + b)) ** 2 return total_error / float(N) ``` ### Step 4: Train and Predict If we run the train function for $\alpha = 0.001$, $w = 0.0$, $b = 0.0$, and 15000 epochs, we will see the following output (shown partially): ``` epoch: 0 loss: 92.32078294903626 epoch: 400 loss: 33.79131790081576 epoch: 800 loss: 27.9918542960729 epoch: 1200 loss: 24.33481690722147 epoch: 1600 loss: 22.028754937538633 epoch: 2800 loss: 19.07940244306619 ``` You can see that the average loss decreases as the train function loops through epochs. Finally, once we have found the optimal values of parameters $w$ and $b$, the only missing piece is a function that makes predictions: ```python def predict(x, w, b): return w * x + b ``` Try to execute the following code: ```python w, b = train(x, y, 0.0, 0.0, 0.001, 15000) x_new = 23.0 y_new = predict(x_new, w, b) print(y_new) ``` The output is 13.97. ### Gradient Descent Variants The gradient descent algorithm is sensitive to the choice of the step $\alpha$. It is also slow for large datasets. Fortunately, several significant improvements to this algorithm have been proposed. - **Stochastic gradient descent (SGD)** is a version of the algorithm that speeds up the computation by approximating the gradient using smaller batches (subsets) of the training data. - **Adagrad** is a version of SGD that scales $\alpha$ for each parameter according to the history of gradients. As a result, $\alpha$ is reduced for very large gradients and vice-versa. - **Momentum** is a method that helps accelerate SGD by orienting the gradient descent in the relevant direction and reducing oscillations. - In neural network training, variants of SGD such as **RMSprop** and **Adam** are most frequently used. Notice that gradient descent and its variants are not machine learning algorithms. They are solvers of minimization problems in which the function to minimize has a gradient in most points of its domain. ## 4.3 How Machine Learning Engineers Work Unless you are a research scientist or work for a huge corporation with a large R&D budget, you usually don't implement machine learning algorithms yourself. You don't implement gradient descent or some other solver either. You use libraries, most of which are open source. A library is a collection of algorithms and supporting tools implemented with stability and efficiency in mind. The most frequently used in practice open-source machine learning library is **scikit-learn**. It's written in Python and C. Here's how you do linear regression in scikit-learn: ```python def train(x, y): from sklearn.linear_model import LinearRegression model = LinearRegression().fit(x, y) return model model = train(x, y) x_new = 23.0 y_new = model.predict(x_new) print(y_new) ``` The output will, again, be 13.97. Easy, right? You can replace `LinearRegression` with some other type of regression learning algorithm without modifying anything else. It just works. The same can be said about classification. You can easily replace `LogisticRegression` algorithm with `SVC` algorithm (this is scikit-learn's name for the Support Vector Machine algorithm), `DecisionTreeClassifier`, `NearestNeighbors` or many other classification learning algorithms implemented in scikit-learn. ## 4.4 Learning Algorithms' Particularities Here we outline some practical particularities that can differentiate one learning algorithm from another. You already know that different learning algorithms can have different hyperparameters ($C$ in SVM, $\epsilon$ and $d$ in ID3). Solvers such as gradient descent can also have hyperparameters, like $\alpha$ for example. **Categorical vs. numerical features.** Some algorithms, like decision tree learning, can accept categorical features. For example, if you have a feature "color" that can take values "red", "yellow", or "green", you can keep this feature as is. SVM, logistic and linear regression, as well as kNN (with cosine similarity or Euclidean distance metrics), expect numerical values for all features. All algorithms implemented in scikit-learn expect numerical features. **Class weighting.** Some algorithms, like SVM, allow the data analyst to provide weightings for each class. These weightings influence how the decision boundary is drawn. If the weight of some class is high, the learning algorithm tries to not make errors in predicting training examples of this class (typically, for the cost of making an error elsewhere). That could be important if instances of some class are in the minority in your training data, but you would like to avoid misclassifying examples of that class as much as possible. **Output type.** Some classification models, like SVM and kNN, given a feature vector only output the class. Others, like logistic regression or decision trees, can also return the score between 0 and 1 which can be interpreted as either how confident the model is about the prediction or as the probability that the input example belongs to a certain class. **Online vs. batch learning.** Some classification algorithms (like decision tree learning, logistic regression, or SVM) build the model using the whole dataset at once. If you have got additional labeled examples, you have to rebuild the model from scratch. Other algorithms (such as Naive Bayes, multilayer perceptron, `SGDClassifier`/`SGDRegressor`, `PassiveAggressiveClassifier`/`PassiveAggressiveRegressor` in scikit-learn) can be trained iteratively, one batch at a time. Once new training examples are available, you can update the model using only the new data. **Versatility.** Some algorithms, like decision tree learning, SVM, and kNN can be used for both classification and regression, while others can only solve one type of problem: either classification or regression, but not both. Usually, each library provides the documentation that explains what kind of problem each algorithm solves, what input values are allowed and what kind of output the model produces. The documentation also provides information on hyperparameters. --- # Chapter 5: Basic Practice Until now, I only mentioned in passing some problems a data analyst can encounter when working on a machine learning problem: feature engineering, overfitting, and hyperparameter tuning. In this chapter, we talk about these and other challenges that have to be addressed before you can type `model = LogisticRegression().fit(x,y)` in scikit-learn. ## 5.1 Feature Engineering When a product manager tells you "We need to be able to predict whether a particular customer will stay with us. Here are the logs of customers' interactions with our product for five years." you cannot just grab the data, load it into a library and get a prediction. You need to build a dataset first. The problem of transforming raw data into a dataset is called **feature engineering**. For most practical problems, feature engineering is a labor-intensive process that demands from the data analyst a lot of creativity and, preferably, domain knowledge. For example, to transform the logs of user interaction with a computer system, one could create features that contain information about the user and various statistics extracted from the logs. We say that a **model has a low bias** when it predicts well the training data. That is, the model makes few mistakes when we try to predict labels of the examples used to build the model. ### 5.1.1 One-Hot Encoding Some learning algorithms only work with numerical feature vectors. When some feature in your dataset is categorical, like "colors" or "days of the week," you can transform such a categorical feature into several binary ones. If your example has a categorical feature "colors" and this feature has three possible values: "red," "yellow," "green," you can transform this feature into a vector of three numerical values: $$\begin{aligned} \text{red} &= [1, 0, 0] \\ \text{yellow} &= [0, 1, 0] \\ \text{green} &= [0, 0, 1] \end{aligned} \tag{1}$$ By doing so, you increase the dimensionality of your feature vectors. You should not transform red into 1, yellow into 2, and green into 3 to avoid increasing the dimensionality because that would imply that there's an order among the values in this category and this specific order is important for the decision making. ### 5.1.2 Binning An opposite situation, occurring less frequently in practice, is when you have a numerical feature but you want to convert it into a categorical one. **Binning** (also called **bucketing**) is the process of converting a continuous feature into multiple binary features called bins or buckets, typically based on value range. For example, instead of representing age as a single real-valued feature, the analyst could chop ranges of age into discrete bins. For example, suppose in our feature $j = 18$ represents age. By applying binning, we replace this feature with the corresponding bins. Let the three new bins, "age_bin1", "age_bin2" and "age_bin3" be added with indexes $j = 123$, $j = 124$ and $j = 125$ respectively. Now if $x_i^{(18)} = 7$ for some example $\mathbf{x}_i$, then we set feature $x_i^{(124)}$ to 1; if $x_i^{(18)} = 13$, then we set feature $x_i^{(125)}$ to 1, and so on. In some cases, a carefully designed binning can help the learning algorithm to learn using fewer examples. It happens because we give a "hint" to the learning algorithm that if the value of a feature falls within a specific range, the exact value of the feature doesn't matter. ### 5.1.3 Normalization **Normalization** is the process of converting an actual range of values which a numerical feature can take, into a standard range of values, typically in the interval $[-1, 1]$ or $[0, 1]$. For example, suppose the natural range of a particular feature is 350 to 1450. By subtracting 350 from every value of the feature, and dividing the result by 1100, one can normalize those values into the range $[0, 1]$. More generally, the normalization formula looks like this: $$\bar{x}^{(j)} = \frac{x^{(j)} - \min^{(j)}}{\max^{(j)} - \min^{(j)}}$$ where $\min^{(j)}$ and $\max^{(j)}$ are, respectively, the minimum and the maximum value of the feature $j$ in the dataset. **Why do we normalize?** Normalizing the data is not a strict requirement. However, in practice, it can lead to an increased speed of learning. Remember the gradient descent example. Imagine you have a two-dimensional feature vector. When you update the parameters of $w^{(1)}$ and $w^{(2)}$, you use partial derivatives of the average squared error with respect to $w^{(1)}$ and $w^{(2)}$. If $x^{(1)}$ is in the range $[0, 1000]$ and $x^{(2)}$ the range $[0, 0.0001]$, then the derivative with respect to a larger feature will dominate the update. Additionally, it's useful to ensure that our inputs are roughly in the same relatively small range to avoid problems which computers have when working with very small or very big numbers (known as numerical overflow). ### 5.1.4 Standardization **Standardization** (or **z-score normalization**) is the procedure during which the feature values are rescaled so that they have the properties of a standard normal distribution with $\mu = 0$ and $\sigma = 1$, where $\mu$ is the mean (the average value of the feature, averaged over all examples in the dataset) and $\sigma$ is the standard deviation from the mean. Standard scores (or z-scores) of features are calculated as follows: $$\hat{x}^{(j)} = \frac{x^{(j)} - \mu^{(j)}}{\sigma^{(j)}}$$ **Normalization vs. standardization.** There's no definitive answer to this question. Usually, if your dataset is not too big and you have time, you can try both and see which one performs better for your task. If you don't have time to run multiple experiments, as a rule of thumb: - Unsupervised learning algorithms, in practice, more often benefit from standardization than from normalization; - Standardization is also preferred for a feature if the values this feature takes are distributed close to a normal distribution (so-called bell curve); - Standardization is preferred for a feature if it can sometimes have extremely high or low values (outliers); this is because normalization will "squeeze" the normal values into a very small range; - In all other cases, normalization is preferable. Modern implementations of the learning algorithms, which you can find in popular libraries, are robust to features lying in different ranges. Feature rescaling is usually beneficial to most learning algorithms, but in many cases, the model will still be good when trained from the original features. ### 5.1.5 Dealing with Missing Features In some cases, the data comes to the analyst in the form of a dataset with features already defined. In some examples, values of some features can be missing. That often happens when the dataset was handcrafted, and the person working on it forgot to fill some values or didn't get them measured at all. The typical approaches of dealing with missing values for a feature include: - Removing the examples with missing features from the dataset. That can be done if your dataset is big enough so you can sacrifice some training examples. - Using a learning algorithm that can deal with missing feature values (depends on the library and a specific implementation of the algorithm). - Using a data imputation technique. ### 5.1.6 Data Imputation Techniques **Average imputation.** One technique consists in replacing the missing value of a feature by an average value of this feature in the dataset: $$\hat{x}^{(j)} = \frac{1}{N} \sum_{i=1}^{N} x_i^{(j)}$$ **Out-of-range imputation.** Another technique is to replace the missing value by the same value outside the normal range of values. For example, if the normal range is $[0, 1]$, then you can set the missing value equal to 2 or $-1$. The idea is that the learning algorithm will learn what is it better to do when the feature has a value significantly different from other values. **Mid-range imputation.** Alternatively, you can replace the missing value by a value in the middle of the range. For example, if the range for a feature is $[-1, 1]$, you can set the missing value to be equal to 0. **Regression-based imputation.** A more advanced technique is to use the missing value as the target variable for a regression problem. You can use all remaining features $[x_1^{(1)}, x_1^{(2)}, \ldots, x_i^{(j-1)}, x_i^{(j+1)}, \ldots, x_i^{(D)}]$ to form a feature vector $\hat{\mathbf{x}}_i$, set $\hat{y}_i = x^{(j)}$, where $j$ is the feature with a missing value. Now we can build a regression model to predict $\hat{y}$ from the feature vectors $\hat{\mathbf{x}}$. **Indicator features.** Finally, if you have a significantly large dataset and just a few features with missing values, you can increase the dimensionality of your feature vectors by adding a binary indicator feature for each feature with missing values. At prediction time, if your example is not complete, you should use the same data imputation technique to fill the missing features as the technique you used to complete the training data. Before you start working on the learning problem, you cannot tell which data imputation technique will work the best. Try several techniques, build several models and select the one that works the best. ## 5.2 Learning Algorithm Selection Choosing a machine learning algorithm can be a difficult task. If you have much time, you can try all of them. However, usually the time you have to solve a problem is limited. You can ask yourself several questions before starting to work on the problem: **Explainability.** Does your model have to be explainable to a non-technical audience? Most very accurate learning algorithms are so-called "black boxes." They learn models that make very few errors, but why a model made a specific prediction could be very hard to understand. Examples of such models are neural networks or ensemble models. On the other hand, kNN, linear regression, or decision tree learning algorithms produce models that are not always the most accurate, however, the way they make their prediction is very straightforward. **In-memory vs. out-of-memory.** Can your dataset be fully loaded into the RAM of your server or personal computer? If yes, then you can choose from a wide variety of algorithms. Otherwise, you would prefer incremental learning algorithms that can improve the model by adding more data gradually. **Number of features and examples.** How many training examples do you have in your dataset? How many features does each example have? Some algorithms, including neural networks and gradient boosting, can handle a huge number of examples and millions of features. Others, like SVM, can be very modest in their capacity. **Categorical vs. numerical features.** Is your data composed of categorical only, or numerical only features, or a mix of both? Depending on your answer, some algorithms cannot handle your dataset directly, and you would need to convert your categorical features into numerical ones. **Nonlinearity of the data.** Is your data linearly separable or can it be modeled using a linear model? If yes, SVM with the linear kernel, logistic regression or linear regression can be a good choice. Otherwise, deep neural networks or ensemble algorithms might work better for your data. **Training speed.** How much time is a learning algorithm allowed to use to build a model? Neural networks are known to be slow to train. Simple algorithms like logistic and linear regression as well as decision tree learning are much faster. **Prediction speed.** How fast does the model have to be when generating predictions? Will your model be used in production where very high throughput is required? Some algorithms, like SVMs, linear and logistic regression, or some types of neural networks, are extremely fast at the prediction time. Some others, like kNN, ensemble algorithms, and very deep or recurrent neural networks, can be slower. If you don't want to guess the best algorithm for your data, a popular way to choose one is by testing it on the validation set. ## 5.3 Three Sets Until now, I used the expressions "dataset" and "training set" interchangeably. However, in practice data analysts work with three sets of labeled examples: 1. **Training set** 2. **Validation set** 3. **Test set** Once you have got your annotated dataset, the first thing you do is you shuffle the examples and split the dataset into three subsets: training, validation, and test. The training set is usually the biggest one, and you use it to build the model. The validation and test sets are roughly the same sizes, much smaller than the size of the training set. The learning algorithm cannot use examples from these two subsets to build a model. That is why those two sets are often called **hold-out sets**. There's no optimal proportion to split the dataset into these three subsets. In the past, the rule of thumb was to use $70\%$ of the dataset for training, $15\%$ for validation and $15\%$ for testing. However, in the age of big data, datasets often have millions of examples. In such cases, it could be reasonable to keep $95\%$ for training and $2.5\% / 2.5\%$ for validation/testing. You may wonder, what is the reason to have three sets and not one. The answer is simple: when we build a model, what we do not want is for the model to only do well at predicting labels of examples the learning algorithms has already seen. A trivial algorithm that simply memorizes all training examples and then uses the memory to "predict" their labels will make no mistakes when asked to predict the labels of the training examples, but such an algorithm would be useless in practice. What we really want is that our model predicts well examples that the learning algorithm didn't see. So we want good performance on a hold-out set. Why do we need two hold-out sets and not one? We use the validation set to: 1. Choose the learning algorithm 2. Find the best values of hyperparameters We use the test set to **assess** the model before delivering it to the client or putting it in production. ## 5.4 Underfitting and Overfitting I mentioned above the notion of **bias**. I said that a model has a low bias if it predicts well the labels of the training data. If the model makes many mistakes on the training data, we say that the model has a **high bias** or that the model **underfits**. So, **underfitting** is the inability of the model to predict well the labels of the data it was trained on. There could be several reasons for underfitting, the most important of which are: - Your model is too simple for the data (for example a linear model can often underfit). - The features you engineered are not informative enough. The solution to the problem of underfitting is to try a more complex model or to engineer features with higher predictive power. **Overfitting** is another problem a model can exhibit. The model that overfits predicts very well the training data but poorly the data from at least one of the two hold-out sets. Several reasons can lead to overfitting, the most important of which are: - Your model is too complex for the data (for example a very tall decision tree or a very deep or wide neural network often overfit). - You have too many features but a small number of training examples. In the literature, you can find another name for the problem of overfitting: the problem of **high variance**. This term comes from statistics. The variance is an error of the model due to its sensitivity to small fluctuations in the training set. Several solutions to the problem of overfitting are possible: 1. Try a simpler model (linear instead of polynomial regression, or SVM with a linear kernel instead of RBF, a neural network with fewer layers/units). 2. Reduce the dimensionality of examples in the dataset (for example, by using one of the dimensionality reduction techniques). 3. Add more training data, if possible. 4. **Regularize** the model. Regularization is the most widely used approach to prevent overfitting. ## 5.5 Regularization Even the simplest model, such as linear, can overfit the data. That usually happens when the data is high-dimensional, but the number of training examples is relatively low. In fact, when feature vectors are very high-dimensional, the linear learning algorithm can build a model that assigns non-zero values to most dimensions $w^{(j)}$ in the parameter vector $\mathbf{w}$, trying to find very complex relationships between all available features to predict labels of training examples perfectly. Such a complex model will most likely predict poorly the labels of the hold-out examples. Regularization is an umbrella-term that encompasses methods that force the learning algorithm to build a less complex model. In practice, that often leads to slightly higher bias but significantly reduces the variance. This problem is known in the literature as the **bias-variance tradeoff**. The two most widely used types of regularization are called **L1 regularization** and **L2 regularization**. The idea is quite simple: to create a regularized model, we modify the objective function by adding a penalizing term whose value is higher when the model is more complex. For simplicity, I illustrate regularization using the example of linear regression. Recall the linear regression objective we want to minimize: $$\min_{\mathbf{w}, b} \frac{1}{N} \sum_{i=1}^{N} \left( f_{\mathbf{w}, b}(\mathbf{x}_i) - y_i \right)^2 \tag{2}$$ ### L1 Regularization An L1-regularized objective looks like this: $$\min_{\mathbf{w}, b} C |\mathbf{w}| + \frac{1}{N} \sum_{i=1}^{N} \left( f_{\mathbf{w}, b}(\mathbf{x}_i) - y_i \right)^2 \tag{3}$$ where $|\mathbf{w}| \stackrel{\mathrm{def}}{=} \sum_{j=1}^{D} |w^{(j)}|$ and $C$ is a hyperparameter that controls the importance of regularization. If we set $C$ to zero, the model becomes a standard non-regularized linear regression model. On the other hand, if we set $C$ to a high value, the learning algorithm will try to set most $w^{(j)}$ to a very small value or zero to minimize the objective, the model will become very simple which can lead to underfitting. ### L2 Regularization An L2-regularized objective will look like this: $$\min_{\mathbf{w}, b} C \|\mathbf{w}\|^2 + \frac{1}{N} \sum_{i=1}^{N} \left( f_{\mathbf{w}, b}(\mathbf{x}_i) - y_i \right)^2$$ where $\|\mathbf{w}\|^2 \stackrel{\mathrm{def}}{=} \sum_{j=1}^{D} (w^{(j)})^2 \tag{4}$ ### Practical Differences In practice, L1 regularization produces a **sparse model**, a model that has most of its parameters (in case of linear models, most of $w^{(j)}$) equal to zero (provided the hyperparameter $C$ is large enough). So L1 makes feature selection by deciding which features are essential for prediction and which are not. That can be useful in case you want to increase model explainability. However, if your only goal is to maximize the performance of the model on the hold-out data, then L2 usually gives better results. L2 also has the advantage of being differentiable, so gradient descent can be used for optimizing the objective function. L1 and L2 regularization methods are also combined in what is called **elastic net regularization** with L1 and L2 regularizations being special cases. You can find in the literature the name **ridge regularization** for L2 and **lasso** for L1. In addition to being widely used with linear models, L1 and L2 regularization are also frequently used with neural networks and many other types of models. ## 5.6 Model Performance Assessment Once you have a model which our learning algorithm has built using the training set, how can you say how good the model is? You use the **test set** to assess the model. The test set contains the examples that the learning algorithm has never seen before, so if our model performs well on predicting the labels of the examples from the test set, we say that our model **generalizes well** or, simply, that it's good. For regression, the assessment of the model is quite simple. A well-fitting regression model results in predicted values close to the observed data values. The mean model, which always predicts the average of the labels in the training data, generally would be used if there were no informative features. We compute the **mean squared error (MSE)** for the training, and, separately, for the test data. If the MSE of the model on the test data is substantially higher than the MSE obtained on the training data, this is a sign of overfitting. For classification, things are a little bit more complicated. The most widely used metrics and tools to assess the classification model are: - Confusion matrix - Accuracy - Cost-sensitive accuracy - Precision/recall - Area under the ROC curve ### 5.6.1 Confusion Matrix The **confusion matrix** is a table that summarizes how successful the classification model is at predicting examples belonging to various classes. One axis of the confusion matrix is the label that the model predicted, and the other axis is the actual label. In a binary classification problem with classes "spam" and "not_spam": | | spam (predicted) | not spam (predicted) | |---|---|---| | **spam (actual)** | 23 (TP) | 1 (FN) | | **not spam (actual)** | 12 (FP) | 556 (TN) | The above confusion matrix shows that of the 24 examples that actually were spam, the model correctly classified 23 as spam. In this case, we have 23 **true positives** or $\mathrm{TP} = 23$. The model incorrectly classified 1 example as not spam. In this case, we have 1 **false negative**, or $\mathrm{FN} = 1$. Similarly, of 568 examples that actually were not spam, 556 were correctly classified (556 **true negatives** or $\mathrm{TN} = 556$), and 12 were incorrectly classified (12 **false positives**, $\mathrm{FP} = 12$). ### 5.6.2 Precision/Recall The two most frequently used metrics to assess the model are precision and recall. **Precision** is the ratio of correct positive predictions to the overall number of positive predictions: $$\mathrm{Precision} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FP}}$$ **Recall** is the ratio of correct positive predictions to the overall number of positive examples in the test set: $$\mathrm{Recall} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FN}}$$ To understand the meaning and importance of precision and recall for the model assessment it is often useful to think about the prediction problem as the problem of research of documents in the database using a query. The precision is the proportion of relevant documents in the list of all returned documents. The recall is the ratio of the relevant documents returned by the search engine to the total number of the relevant documents that could have been returned. In the case of the spam detection problem, we want to have high precision (we want to avoid making mistakes by detecting that a legitimate message is spam) and we are ready to tolerate lower recall (we tolerate some spam messages in our inbox). Even if precision and recall are defined for the binary classification case, you can always use it to assess a multiclass classification model. To do that, first select a class for which you want to assess these metrics. Then you consider all examples of the selected class as positives and all examples of the remaining classes as negatives. ### 5.6.3 Accuracy **Accuracy** is given by the number of correctly classified examples divided by the total number of classified examples: $$\mathrm{Accuracy} = \frac{\mathrm{TP} + \mathrm{TN}}{\mathrm{TP} + \mathrm{TN} + \mathrm{FP} + \mathrm{FN}} \tag{5}$$ Accuracy is a useful metric when errors in predicting all classes are equally important. ### 5.6.4 Cost-Sensitive Accuracy For dealing with the situation in which different classes have different importance, a useful metric is **cost-sensitive accuracy**. To compute a cost-sensitive accuracy, you first assign a cost (a positive number) to both types of mistakes: FP and FN. You then compute the counts TP, TN, FP, FN as usual and multiply the counts for FP and FN by the corresponding cost before calculating the accuracy using eq. 5. ### 5.6.5 Area under the ROC Curve (AUC) The **ROC curve** (ROC stands for "receiver operating characteristic," the term comes from radar engineering) is a commonly used method to assess the performance of classification models. ROC curves use a combination the true positive rate (the proportion of positive examples predicted correctly, defined exactly as recall) and false positive rate (the proportion of negative examples predicted incorrectly) to build up a summary picture of the classification performance. The **true positive rate** and the **false positive rate** are respectively defined as: $$\mathrm{TPR} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FN}} \quad \text{and} \quad \mathrm{FPR} = \frac{\mathrm{FP}}{\mathrm{FP} + \mathrm{TN}}$$ ROC curves can only be used to assess classifiers that return some confidence score (or a probability) of prediction. For example, logistic regression, neural networks, and decision trees (and ensemble models based on decision trees) can be assessed using ROC curves. To draw a ROC curve, we first discretize the range of the confidence score. If this range for our model is $[0, 1]$, then we can discretize it like this: $[0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1]$. Then, we use each discrete value as the prediction threshold and predict the labels of examples in our dataset using our model and this threshold. The higher the area under the ROC curve (AUC), the better the classifier. A classifier with an AUC higher than 0.5 is better than a random classifier. If AUC is lower than 0.5, then something is wrong with your model. A perfect classifier would have an AUC of 1. ## 5.7 Hyperparameter Tuning When I presented learning algorithms, I mentioned that you as a data analyst have to select good values for the algorithm's hyperparameters, such as $\epsilon$ and $d$ for ID3, $C$ for SVM, or $\alpha$ for gradient descent. As you already know, hyperparameters aren't optimized by the learning algorithm itself. The data analyst has to "tune" hyperparameters by experimentally finding the best combination of values, one per hyperparameter. One typical way to do that, when you have enough data to have a decent validation set and the number of hyperparameters and their range is not too large is to use **grid search**. **Grid search** is the most simple hyperparameter tuning strategy. Let's say you train an SVM and you have two hyperparameters to tune: the penalty parameter $C$ and the kernel (either "linear" or "rbf"). If it's the first time you are working with this dataset, you don't know what is the possible range of values for $C$. The most common trick is to use a logarithmic scale. For example, for $C$ you can try the following values: $[0.001, 0.01, 0.1, 1.0, 10, 100, 1000]$. In this case you have 14 combinations of hyperparameters to try. You use the training set and train 14 models, one for each combination of hyperparameters. Then you assess the performance of each model on the validation data using one of the metrics we discussed in the previous section (or some other metric that matters to you). Finally, you keep the model that performs the best according to the metric. **Random search** differs from grid search in that you no longer provide a discrete set of values to explore for each hyperparameter; instead, you provide a statistical distribution for each hyperparameter from which values are randomly sampled and set the total number of combinations you want to try. **Bayesian techniques** differ from random or grid search in that they use past evaluation results to choose the next values to evaluate. The idea is to limit expensive optimization of the objective function by choosing the next hyperparameter values based on those that have done well in the past. There are also gradient-based techniques, evolutionary optimization techniques, and other algorithmic hyperparameter tuning techniques. ### 5.7.1 Cross-Validation When you don't have a decent validation set to tune your hyperparameters on, the common technique that can help you is called **cross-validation**. When you have few training examples, it could be prohibitive to have both validation and test set. You would prefer to use more data to train the model. In such a case, you only split your data into a training and a test set. Then you use cross-validation to on the training set to simulate a validation set. Cross-validation works like follows: 1. First, you fix the values of the hyperparameters you want to evaluate. 2. Then you split your training set into several subsets of the same size. Each subset is called a **fold**. Typically, five-fold cross-validation is used in practice. 3. With five-fold cross-validation, you randomly split your training data into five folds: $\{F_1, F_2, \ldots, F_5\}$. Each $F_k$ contains $20\%$ of your training data. 4. Then you train five models. To train the first model, $f_1$, you use all examples from folds $F_2, F_3, F_4, F_5$ as the training set and the examples from $F_1$ as the validation set. To train the second model, $f_2$, you use the examples from folds $F_1, F_3, F_4, F_5$ to train and the examples from $F_2$ as the validation set. 5. You continue building models iteratively like this and compute the value of the metric of interest on each validation set, from $F_1$ to $F_5$. 6. Then you average the five values of the metric to get the final value. You can use grid search with cross-validation to find the best values of hyperparameters for your model. Once you have found these values, you use the entire training set to build the model with these best values of hyperparameters you have found via cross-validation. Finally, you assess the model using the test set. --- # Chapter 6: Neural Networks and Deep Learning First of all, you already know what a neural network is, and you already know how to build such a model. Yes, it's logistic regression! As a matter of fact, the logistic regression model, or rather its generalization for multiclass classification, called the softmax regression model, is a standard unit in a neural network. ## 6.1 Neural Networks If you understood linear regression, logistic regression, and gradient descent, understanding neural networks would not be a problem. A neural network (NN), just like a regression or an SVM model, is a mathematical function: $$y = f_{NN}(\mathbf{x})$$ The function $f_{NN}$ has a particular form: it's a **nested function**. For a 3-layer neural network that returns a scalar, $f_{NN}$ looks like this: $$y = f_{NN}(\mathbf{x}) = f_3(\mathbf{f}_2(\mathbf{f}_1(\mathbf{x})))$$ In the above equation, $f_2, f_3$ are vector functions of the following form: $$\mathbf{f}_l(\mathbf{z}) \stackrel{\mathrm{def}}{=} \mathbf{g}_l(\mathbf{W}_l \mathbf{z} + \mathbf{b}_l) \tag{1}$$ where $l$ is called the **layer index** and can span from 1 to any number of layers. The function $\mathbf{g}_l$ is called an **activation function**. It is a fixed, usually nonlinear function chosen by the data analyst before the learning is started. The parameters $\mathbf{W}_l$ (a matrix) and $\mathbf{b}_l$ (a vector) for each layer are learned using the familiar gradient descent by optimizing, depending on the task, a particular cost function (such as MSE). Compare eq. 1 with the equation for logistic regression, where you replace $\mathbf{g}_l$ by the sigmoid function, and you will not see any difference. **Why the matrix $\mathbf{W}_l$?** You may probably wonder why a matrix $\mathbf{W}_l$ is used and not a vector $\mathbf{w}_l$. The reason is that $\mathbf{g}_l$ is a vector function. Each row $\mathbf{w}_{l,u}$ ($u$ for unit) of the matrix $\mathbf{W}_l$ is a vector of the same dimensionality as $\mathbf{z}$. Let $a_{l,u} = \mathbf{w}_{l,u} \mathbf{z} + b_{l,u}$. The output of $\mathbf{f}_l(\mathbf{z})$ is a vector: $$\mathbf{f}_l(\mathbf{z}) = [g_l(a_{l,1}), g_l(a_{l,2}), \ldots, g_l(a_{l, \mathrm{size}_l})]$$ where $g_l$ is some scalar function, and $\mathrm{size}_l$ is the number of units in layer $l$. ### 6.1.1 Multilayer Perceptron Example We have a closer look at one particular configuration of neural networks called **feed-forward neural networks (FFNN)**, and more specifically the architecture called a **multilayer perceptron (MLP)**. As an illustration, we consider an MLP with three layers. Our network takes a two-dimensional feature vector as input and outputs a number. The neural network is represented graphically as a connected combination of units logically organized into one or more layers. Each unit is represented by either a circle or a rectangle. The inbound arrow represents an input of a unit and indicates where this input came from. The outbound arrow indicates the output of a unit. The output of each unit is the result of the mathematical operation written inside the circle or a rectangle. Circle units don't do anything with the input; they just send their input directly to the output. The following happens in each rectangle unit: 1. **Join inputs.** All inputs of the unit are joined together to form an input vector. 2. **Linear transformation.** The unit applies a linear transformation to the input vector, exactly like linear regression model does with its input feature vector. 3. **Activation.** The unit applies an activation function $g$ to the result of the linear transformation and obtains the output value, a real number. In a vanilla FFNN, the output value of a unit of some layer becomes an input value of each of the units of the subsequent layer. In **multilayer perceptron** all outputs of one layer are connected to each input of the succeeding layer. This architecture is called **fully-connected**. ### 6.1.2 Feed-Forward Neural Network Architecture If we want to solve a regression or a classification problem discussed in previous chapters, the last (the rightmost) layer of a neural network usually contains only one unit: - If the activation function $g_{last}$ of the last unit is linear, then the neural network is a **regression model**. - If $g_{last}$ is a logistic function, the neural network is a **binary classification model**. The data analyst is free to choose any mathematical function as $g_{l,u}$, assuming it's differentiable. The latter property is essential for gradient descent. **Why nonlinearities?** The primary purpose of having nonlinear components in the function $f_{NN}$ is to allow the neural network to approximate nonlinear functions. Without nonlinearities, $f_{NN}$ would be linear, no matter how many layers it has. The reason is that $\mathbf{W}_l \mathbf{z} + \mathbf{b}_l$ is a linear function and a linear function of a linear function is also a linear function. **Popular activation functions.** The **hyperbolic tangent** function (TanH): $$\tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}}$$ The **rectified linear unit** function (ReLU): $$\mathrm{relu}(z) = \begin{cases} 0 & \text{if } z < 0 \\ z & \text{otherwise} \end{cases}$$ ReLU equals zero when its input $z$ is negative and to $z$ otherwise. The logistic function, already known to you, is another popular choice. ## 6.2 Deep Learning **Deep learning** refers to training neural networks with more than two non-output layers. In the past, it became more difficult to train such networks as the number of layers grew. The two biggest challenges were referred to as the problems of **exploding gradient** and **vanishing gradient** as gradient descent was used to train the network parameters. ### The Vanishing Gradient Problem What is vanishing gradient and why does it arise? To update the values of parameters in neural networks the algorithm called **backpropagation** is typically used. Backpropagation is an efficient algorithm for computing gradients on neural networks using the chain rule. During gradient descent, the neural network's parameters receive an update proportional to the partial derivative of the cost function with respect to the current parameter in each iteration of training. The problem is that in some cases, the gradient will be vanishingly small, effectively preventing some parameters from changing their value. In the worst case, this may completely stop the neural network from further training. Traditional activation functions, such as the hyperbolic tangent function I mentioned above, have gradients in the range $(0, 1)$, and backpropagation computes gradients by the chain rule. That has the effect of multiplying $n$ of these small numbers to compute gradients of the earlier (leftmost) layers in an $n$-layer network, meaning that the gradient decreases exponentially with $n$. While the problem of exploding gradient was easier to deal with by applying simple techniques like gradient clipping and L1 or L2 regularization, the problem of vanishing gradient remained intractable for decades. **Modern solutions.** Modern implementations of neural network learning algorithms allow you to effectively train very deep neural networks (up to hundreds of layers). The ReLU activation function suffers much less from the problem of vanishing gradient. Also, **long short-term memory (LSTM)** networks, as well as such techniques as **skip connections** used in residual neural networks allow you to train even deeper neural networks, with thousands of layers. Therefore, today, since the problems of vanishing and exploding gradient are mostly solved (or their effect diminished) to a great extent, the term "deep learning" refers to training neural networks using the modern algorithmic and mathematical toolkit independently of how deep the neural network is. In practice, many business problems can be solved with neural networks having 2-3 layers between the input and output layers. The layers that are neither input nor output are often called **hidden layers**. ### 6.2.1 Convolutional Neural Network You may have noticed that the number of parameters an MLP can have grows very fast as you make your network bigger. More specifically, as you add one layer, you add $\mathrm{size}_l (\mathrm{size}_{l-1} + 1)$ parameters (our matrix $\mathbf{W}_l$ plus the vector $\mathbf{b}_l$). That means that if you add another 1000-unit layer to an existing neural network, then you add more than 1 million additional parameters to your model. When our training examples are images, the input is very high-dimensional. If you want to learn to classify images using an MLP, the optimization problem is likely to become intractable. A **convolutional neural network (CNN)** is a special kind of FFNN that significantly reduces the number of parameters in a deep neural network with many units without losing too much in the quality of the model. CNNs have found applications in image and text processing where they beat many previously established benchmarks. **The intuition.** Because CNNs were invented with image processing in mind, I explain them on the image classification example. You may have noticed that in images, pixels that are close to one another usually represent the same type of information: sky, water, leaves, fur, bricks, and so on. The exception from the rule are the edges: the parts of an image where two different objects "touch" one another. So, if we can train the neural network to recognize regions of the same information as well as the edges, then this knowledge would allow the neural network to predict the object represented in the image. Having in mind that the most important information in the image is local, we can split the image into square patches using a moving window approach. We can then train multiple smaller regression models at once, each small regression model receiving a square patch as input. In CNNs, a small regression model has to learn the parameters of a matrix $\mathbf{F}$ (for "filter") of size $p \times p$, where $p$ is the size of a patch. Let's assume, for simplicity, that the input image is black and white, with 1 representing black and 0 representing white pixels. Assume also that our patches are 3 by 3 pixels ($p = 3$). For instance, assume that our filter $\mathbf{F}$ looks like a cross pattern. If we calculate the dot-product between matrices $\mathbf{P}$ (the patch) and $\mathbf{F}$ and then sum all values from the resulting vector, the value we obtain is higher the more similar $\mathbf{F}$ is to $\mathbf{P}$. For example, the dot product of $\mathbf{P}$ and $\mathbf{F}$ might give $[2, 9, 1]$, with the sum being $2 + 9 + 1 = 12$. This operation — the dot product between a patch and a filter and then summing the values — is called **convolution**. If our input patch $\mathbf{P}$ had a different pattern, the convolution would give a lower result. So, you can see the more the patch "looks" like the filter, the higher the value of the convolution operation is. For convenience, there's also a bias parameter $b$ associated with each filter $\mathbf{F}$ which is added to the result of a convolution before applying the nonlinearity. One layer of a CNN consists of multiple convolution filters (each with its own bias parameter), just like one layer in a vanilla FFNN consists of multiple units. Each filter of the first (leftmost) layer slides — or convolves — across the input image, left to right, top to bottom, and convolution is computed at each iteration. The numbers in the filter matrix, for each filter $\mathbf{F}$ in each layer, as well as the value of the bias term $b$, are found by the gradient descent with backpropagation, based on data by minimizing the cost function. A nonlinearity is applied to the sum of the convolution and the bias term. Typically, the **ReLU activation function** is used in all hidden layers. The activation function of the output layer depends on the task. Since we can have $\mathrm{size}_l$ filters in each layer $l$, the output of the convolution layer $l$ would consist of $\mathrm{size}_l$ matrices, one for each filter. ### 6.2.2 Recurrent Neural Network **Recurrent neural networks (RNNs)** are used to label, classify, or generate sequences. A sequence is a matrix, each row of which is a feature vector and the order of rows matters: - **Labeling a sequence** means predicting a class to each feature vector in a sequence. - **Classifying a sequence** means predicting a class for the entire sequence. - **Generating a sequence** means to output another sequence (of a possibly different length) somehow relevant to the input sequence. RNNs are often used in text processing because sentences and texts are naturally sequences of either words/punctuation marks or sequences of characters. For the same reason, recurrent neural networks are also used in speech processing. A recurrent neural network is not feed-forward, because it contains loops. The idea is that each unit $u$ of recurrent layer $l$ has a real-valued state $h_{l,u}$. The state can be seen as the memory of the unit. In RNN, each unit $u$ in each recurrent layer $l$ receives two inputs: a vector of outputs from the previous layer $l-1$ and the vector of states from this same layer $l$ from the previous time step. **The GRU unit.** The most effective recurrent neural network models used in practice are gated RNNs. These include the long short-term memory (LSTM) networks and networks based on the gated recurrent unit (GRU). The beauty of using gated units in RNNs is that such networks can store information in their units for future use, much like bits in a computer's memory. The difference with the real memory is that reading, writing, and erasure of information stored in each unit is controlled by activation functions that take values in the range $(0, 1)$. The simplest gated architecture (working well in practice) is called the minimal gated GRU and is composed of a memory cell, and a forget gate. Let's look at the math of a GRU unit on an example of the first layer of the RNN: $$\begin{aligned} \tilde{h}_{l,u}^{t} &\gets g_1(\mathbf{w}_{l,u} \mathbf{x}^{t} + \mathbf{u}_{l,u} \mathbf{h}_l^{t-1} + b_{l,u}) \\ \Gamma_{l,u}^{t} &\gets g_2(\mathbf{m}_{l,u} \mathbf{x}^{t} + \mathbf{o}_{l,u} \mathbf{h}^{t-1} + a_{l,u}) \\ h_{l,u}^{t} &\gets \Gamma_{l,u}^{t} \tilde{h}_{l}^{t} + (1 - \Gamma_{l,u}^{t}) h_{l}^{t-1} \\ \mathbf{h}_{l}^{t} &\gets [h_{l,1}^{t}, \ldots, h_{l, \mathrm{size}_l}^{t}] \\ \mathbf{y}_{l}^{t} &\gets g_3(\mathbf{V}_{l} \mathbf{h}_{l}^{t} + \mathbf{c}_{l,u}) \end{aligned}$$ where $g_1$ is the tanh activation function, $g_2$ is called the gate function and is implemented as the sigmoid function. **Softmax function.** Just like in standard RNNs, $g_3$ is usually **softmax**: $$\boldsymbol{\sigma}(\mathbf{z}) \stackrel{\mathrm{def}}{=} [\sigma^{(1)}, \ldots, \sigma^{(D)}], \quad \text{where } \sigma^{(j)} \stackrel{\mathrm{def}}{=} \frac{\exp\left(z^{(j)}\right)}{\sum_{k=1}^{D} \exp\left(z^{(k)}\right)}$$ The softmax function is a generalization of the sigmoid function to multidimensional data. It has the property that $\sum_{j=1}^{D} \sigma^{(j)} = 1$ and $\sigma^{(j)} > 0$ for all $j$. --- # Chapter 7: Problems and Solutions ## 7.1 Kernel Regression We talked about linear regression, but what if our data doesn't have the form of a straight line? Polynomial regression could help. Let's say we have a one-dimensional data $\{(x_i, y_i)\}_{i=1}^N$. We could try to fit a quadratic line $y = w_1 x_i + w_2 x_i^2 + b$ to our data. By defining the mean squared error cost function, we could apply gradient descent and find the values of parameters $w_1, w_2$, and $b$ that minimize this cost function. In one- or two-dimensional space, we can easily see whether the function fits the data. However, if our input is a $D$-dimensional feature vector, with $D > 3$, finding the right polynomial would be hard. **Kernel regression** is a non-parametric method. That means that there are no parameters to learn. The model is based on the data itself (like in kNN). In its simplest form, in kernel regression we look for a model like this: $$f(x) = \frac{1}{N} \sum_{i=1}^{N} w_i y_i, \quad \text{where } w_i = \frac{N k\left(\frac{x_i - x}{b}\right)}{\sum_{k=1}^{N} k\left(\frac{x_k - x}{b}\right)} \tag{1}$$ The function $k(\cdot)$ is a kernel. It can have different forms, the most frequently used one is the **Gaussian kernel**: $$k(z) = \frac{1}{\sqrt{2\pi}} \exp\left(\frac{-z^2}{2}\right)$$ The value $b$ is a hyperparameter that we tune using the validation set (by running the model built with a specific value of $b$ on the validation set examples and calculating the mean squared error). ## 7.2 Multiclass Classification In multiclass classification, the label can be one of the $C$ classes: $y \in \{1, \ldots, C\}$. Many machine learning algorithms are binary; SVM is an example. Some algorithms can naturally be extended to handle multiclass problems. **Decision trees.** ID3 and other decision tree learning algorithms can be simply changed like this: $$f_{ID3}^{\mathcal{S}} \stackrel{\mathrm{def}}{=} \Pr(y_i = c | \mathbf{x}) = \frac{1}{|\mathcal{S}|} \sum_{\{y | (\mathbf{x}, y) \in \mathcal{S}, y = c\}} y$$ for all $c \in \{1, \ldots, C\}$. **Logistic regression** can be naturally extended to multiclass learning problems by replacing the sigmoid function with the **softmax function**. **kNN** is also straightforward to extend to the multiclass case: when we find the $k$ closest examples for the input $\mathbf{x}$ and examine them, we return the class that we saw the most among the $k$ examples. SVM cannot be naturally extended to multiclass problems. **One vs. Rest.** What should you do if you have a multiclass problem but a binary classification learning algorithm? One common strategy is called **one versus rest**. The idea is to transform a multiclass problem into $C$ binary classification problems and build $C$ binary classifiers. For example, if we have three classes, $y \in \{1, 2, 3\}$, we create copies of the original datasets and modify them. In the first copy, we replace all labels not equal to 1 by 0. In the second copy, we replace all labels not equal to 2 by 0. In the third copy, we replace all labels not equal to 3 by 0. Now we have three binary classification problems where we have to learn to distinguish between labels 1 and 0, 2 and 0, and between labels 3 and 0. Once we have the three models and we need to classify the new input feature vector $\mathbf{x}$, we apply the three models to the input, and we get three predictions. We then pick the prediction of a non-zero class which is the most certain. In SVM, the analog of certainty is the distance from the input $\mathbf{x}$ to the decision boundary: $$d = \frac{\mathbf{w}^* \mathbf{x} + b^*}{\|w\|}$$ The larger the distance, the more certain is the prediction. ## 7.3 One-Class Classification **One-class classification**, also known as **unary classification** or **class modeling**, tries to identify objects of a specific class among all objects, by learning from a training set containing only the objects of that class. That is different from and more difficult than the traditional classification problem. A typical one-class classification problem is the classification of the traffic in a secure network as normal. In this scenario, there are few, if any, examples of the traffic under an attack or during an intrusion. However, the examples of normal traffic are often in abundance. There are several one-class learning algorithms. The most widely used in practice are **one-class Gaussian**, **one-class kmeans**, **one-class kNN**, and **one-class SVM**. **One-class Gaussian.** The idea behind the one-class Gaussian is that we model our data as if it came from a Gaussian distribution, more precisely **multivariate normal distribution (MND)**. The probability density function (pdf) for MND is given by: $$f_{\boldsymbol{\mu}, \boldsymbol{\Sigma}}(\mathbf{x}) = \frac{\exp\left(-\frac{1}{2}(\mathbf{x} - \boldsymbol{\mu})^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu})\right)}{\sqrt{(2\pi)^D |\boldsymbol{\Sigma}|}}$$ where $f_{\boldsymbol{\mu}, \boldsymbol{\Sigma}}(\mathbf{x})$ returns the probability density corresponding to the input feature vector $\mathbf{x}$. Values $\boldsymbol{\mu}$ (a vector) and $\boldsymbol{\Sigma}$ (a matrix) are the parameters we have to learn. The maximum likelihood criterion is optimized to find the optimal values for these two parameters. $|\boldsymbol{\Sigma}| = \det \boldsymbol{\Sigma}$ is the determinant of the matrix $\boldsymbol{\Sigma}$; the notation $\mathbf{a}^\top$ means the transpose of the vector $\mathbf{a}$, and $\boldsymbol{\Sigma}^{-1}$ is the inverse of the matrix $\boldsymbol{\Sigma}$. In practice, the numbers in the vector $\boldsymbol{\mu}$ determine the place where the curve of our Gaussian distribution is centered, while the numbers in $\boldsymbol{\Sigma}$ determine the shape of the curve. Once we have our model parametrized by $\boldsymbol{\mu}$ and $\boldsymbol{\Sigma}$ learned from the data, we predict the likelihood of every input $\mathbf{x}$ by using $f_{\boldsymbol{\mu}, \boldsymbol{\Sigma}}(\mathbf{x})$. Only if the likelihood is above a certain threshold, we predict that the example belongs to our class; otherwise, it is classified as the outlier. When the data has a more complex shape, a more advanced algorithm can use a combination of several Gaussians (called a **mixture of Gaussians**). ## 7.4 Multi-Label Classification In **multi-label classification**, each training example doesn't just have one label, but several of them. For instance, if we want to describe an image, we could assign several labels to it: "people," "concert," "nature," all three at the same time. **Approach 1: One vs. Rest with threshold.** If the number of possible values for labels is high, but they are all of the same nature, like tags, we can transform each labeled example into several labeled examples, one per label. These new examples all have the same feature vector and only one label. That becomes a multiclass classification problem. We can solve it using the one versus rest strategy. The only difference is that now we have a new hyperparameter: threshold. If the prediction score for some label is above the threshold, this label is predicted for the input feature vector. Multiple labels can be predicted for one feature vector. **Approach 2: Multi-label via neural networks.** Neural networks algorithms can naturally train multi-label classification models by using the **binary cross-entropy cost function**. The output layer of the neural network has one unit per label. Each unit of the output layer has the sigmoid activation function. Accordingly, each label $l$ is binary ($y_{i,l} \in \{0, 1\}$), where $l = 1, \ldots, L$ and $i = 1, \ldots, N$. The binary cross-entropy of predicting the probability $\hat{y}_{i,l}$ that example $\mathbf{x}_i$ has label $l$ is defined as: $$-\left(y_{i,l} \ln(\hat{y}_{i,l}) + (1 - y_{i,l}) \ln(1 - \hat{y}_{i,l})\right)$$ The minimization criterion is simply the average of all binary cross-entropy terms across all training examples and all labels of those examples. **Approach 3: Fake class enumeration.** In cases where the number of possible values each label can take is small, one can convert multilabel into a multiclass problem using a different approach. For example, create a new fake class for each combination of the original classes: | Fake Class | Real Class 1 | Real Class 2 | |---|---|---| | 1 | photo | portrait | | 2 | photo | paysage | | 3 | photo | other | | 4 | painting | portrait | | 5 | painting | paysage | | 6 | painting | other | Now we have the same labeled examples, but we replace real multi-labels with one fake label with values from 1 to 6. This approach works well in practice when there are not too many possible combinations of classes. The primary advantage of this latter approach is that you keep your labels correlated, contrary to the previously seen methods that predict each label independently of one another. ## 7.5 Ensemble Learning **Ensemble learning** is a learning paradigm that, instead of trying to learn one super-accurate model, focuses on training a large number of low-accuracy models and then combining the predictions given by those weak models to obtain a high-accuracy meta-model. Low-accuracy models are usually learned by **weak learners**, that is learning algorithms that cannot learn complex models, and thus are typically fast at the training and at the prediction time. The most frequently used weak learner is a decision tree learning algorithm in which we often stop splitting the training set after just a few iterations. The obtained trees are shallow and not particularly accurate, but the idea behind ensemble learning is that if the trees are not identical and each tree is at least slightly better than random guessing, then we can obtain high accuracy by combining a large number of such trees. To obtain the prediction for input $\mathbf{x}$, the predictions of each weak model are combined using some sort of weighted voting. The specific form of vote weighting depends on the algorithm, but, independently of the algorithm, the idea is the same: if the council of weak models predicts that the message is spam, then we assign the label spam to $\mathbf{x}$. Two most widely used and effective ensemble learning algorithms are **random forest** and **gradient boosting**. ### 7.5.1 Random Forest There are two ensemble learning paradigms: **bagging** and **boosting**. Bagging consists of creating many "copies" of the training data (each copy is slightly different from another) and then apply the weak learner to each copy to obtain multiple weak models and then combine them. The bagging paradigm is behind the random forest learning algorithm. **The bagging algorithm.** Given a training set, we create $B$ random samples $\mathcal{S}_b$ (for each $b = 1, \ldots, B$) of the training set and build a decision tree model $f_b$ using each sample $\mathcal{S}_b$ as the training set. To sample $\mathcal{S}_b$ for some $b$, we do the sampling with replacement. This means that we start with an empty set, and then pick at random an example from the training set and put its exact copy to $\mathcal{S}_b$ by keeping the original example in the original training set. We keep picking examples at random until $|\mathcal{S}_b| = N$. After training, we have $B$ decision trees. The prediction for a new example $\mathbf{x}$ is obtained as the average of $B$ predictions: $$y \leftarrow \hat{f}(\mathbf{x}) \stackrel{\mathrm{def}}{=} \frac{1}{B} \sum_{b=1}^{B} f_b(\mathbf{x})$$ in the case of regression, or by taking the majority vote in the case of classification. The **random forest** algorithm is different from the vanilla bagging in just one way. It uses a modified tree learning algorithm that inspects, at each split in the learning process, a **random subset of the features**. The reason for doing this is to avoid the correlation of the trees. The most important hyperparameters to tune are the number of trees, $B$, and the size of the random subset of the features to consider at each split. ### 7.5.2 Gradient Boosting Another effective ensemble learning algorithm is **gradient boosting**. Let's first look at gradient boosting for regression. To build a strong regressor, we start with a constant model: $$f = f_0(\mathbf{x}) \stackrel{\mathrm{def}}{=} \frac{1}{N} \sum_{i=1}^{N} y_i$$ Then we modify labels of each example $i = 1, \ldots, N$ in our training set like follows: $$\hat{y}_i \leftarrow y_i - f(\mathbf{x}_i) \tag{2}$$ where $\hat{y}_i$, called the **residual**, is the new label for example $\mathbf{x}_i$. Now we use the modified training set, with residuals instead of original labels, to build a new decision tree model, $f_1$. The boosting model is now defined as: $$f \stackrel{\mathrm{def}}{=} f_0 + \alpha f_1$$ where $\alpha$ is the learning rate (a hyperparameter). Then we recompute the residuals using eq. 2 and replace the labels in the training data once again, train the new decision tree model $f_2$, redefine the boosting model as $f \stackrel{\mathrm{def}}{=} f_0 + \alpha f_1 + \alpha f_2$ and the process continues until the maximum of $M$ (another hyperparameter) trees are combined. **Why gradient boosting?** To see the similarity between gradient boosting and gradient descent remember why we calculated the gradient in linear regression: we did that to get an idea on where we should move the values of our parameters so that the MSE cost function reaches its minimum. The gradient showed the direction, but we didn't know how far we should go in this direction, so we used a small step $\alpha$ at each iteration and then reevaluated our direction. The same happens in gradient boosting. However, instead of getting the gradient directly, we use its proxy in the form of residuals: they show us how the model has to be adjusted so that the error (the residual) is reduced. The three principal hyperparameters to tune in gradient boosting are the number of trees, the learning rate, and the depth of trees — all three affect model accuracy. It can be shown that training on residuals optimizes the overall model $f$ for the mean squared error criterion. You can see the difference with bagging here: boosting reduces the bias (or underfitting) instead of the variance. As such, boosting can overfit. **Gradient boosting for classification.** The gradient boosting algorithm for classification is similar, but the steps are slightly different. Let's consider the binary case. Assume we have $M$ regression decision trees. Similarly to logistic regression, the prediction of the ensemble of decision trees is modeled using the sigmoid function: $$\Pr(y = 1 | \mathbf{x}, f) \stackrel{\mathrm{def}}{=} \frac{1}{1 + e^{-f(\mathbf{x})}}$$ where $f(\mathbf{x}) = \sum_{m=1}^{M} f_m(\mathbf{x})$ and $f_m$ is a regression tree. We apply the maximum likelihood principle by trying to find such an $f$ that maximizes: $$L_f = \sum_{i=1}^{N} \ln(\Pr(y_i = 1 | \mathbf{x}_i, f))$$ ## 7.6 Learning to Label Sequences A sequence is one the most frequently observed types of structured data. In **sequence labeling**, a labeled sequential example is a pair of lists $(\mathcal{X}, \mathcal{Y})$, where $\mathcal{X}$ is a list of feature vectors, one per time step, $\mathcal{Y}$ is a list of the same length of labels. For example, $\mathcal{X}$ could represent words in a sentence such as `["big", "beautiful", "car"]`, and $\mathcal{Y}$ would be the list of the corresponding parts of speech, such as `["adjective", "adjective", "noun"]`. You have already seen that an RNN can be used to annotate a sequence. At each time step $t$, it reads an input feature vector $\mathbf{x}_i^{(t)}$, and the last recurrent layer outputs a label $y_{last}^{(t)}$ (in the case of binary labeling) or $\mathbf{y}_{last}^{(t)}$ (in the case of multiclass or multilabel labeling). **Conditional Random Fields (CRF).** The model called Conditional Random Fields (CRF) is a very effective alternative that often performs well in practice for the feature vectors that have many informative features. CRF is an interesting model and can be seen as a generalization of logistic regression to sequences. However, in practice, it has been outperformed by bidirectional deep gated RNN for sequence labeling tasks. CRFs are also significantly slower in training which makes them difficult to apply to large training sets. ## 7.7 Sequence-to-Sequence Learning **Sequence-to-sequence learning** (often abbreviated as **seq2seq learning**) is a generalization of the sequence labeling problem. In seq2seq, $\mathcal{X}_i$ and $\mathcal{Y}_i$ can have different length. seq2seq models have found application in machine translation, conversational interfaces, text summarization, spelling correction, and many others. Many but not most sequence-to-sequence learning problems are currently best solved by neural networks. All seq2seq network architectures have one property in common: they have two parts, an **encoder** and a **decoder** (for this reason they are also known as **encoder-decoder neural networks**). **Encoder.** In seq2seq learning, the encoder is a neural network that accepts sequential input. It can be an RNN, but also a CNN or some other architecture. The role of the encoder is to read the input and generate some sort of state (similar to the state in RNN) that can be seen as a numerical representation of the meaning of the input the machine can work with. The meaning of some entity, whether it be an image, a text or a video, is usually a vector or a matrix that contains real numbers. This vector (or matrix) is called in the machine learning jargon the **embedding** of the input. **Decoder.** The decoder in seq2seq learning is another neural network that takes an embedding as input and is capable of generating a sequence of outputs. As you could have already guessed, that embedding comes from the encoder. To produce a sequence of outputs, the decoder takes a start of sequence input feature vector $\mathbf{x}^{(0)}$ (typically all zeroes), produces the first output $\mathbf{y}^{(1)}$, updates its state by combining the embedding and the input $\mathbf{x}^{(0)}$, and then uses the output $\mathbf{y}^{(1)}$ as its next input $\mathbf{x}^{(1)}$. Both encoder and decoder are trained simultaneously using the training data. The errors at the decoder output are propagated to the encoder via backpropagation. **Attention.** More accurate predictions can be obtained using an architecture with attention. Attention mechanism is implemented by an additional set of parameters that combine some information from the encoder (in RNNs, this information is the list of state vectors of the last recurrent layer from all encoder time steps) and the current state of the decoder to generate the label. That allows for even better retention of long-term dependencies than provided by gated units and bidirectional RNN. ## 7.8 Active Learning **Active learning** is an interesting supervised learning paradigm. It is usually applied when obtaining labeled examples is costly. That is often the case in the medical or financial domains, where the opinion of an expert may be required to annotate patients' or customers' data. The idea is that we start the learning with relatively few labeled examples, and a large number of unlabeled ones, and then add labels only to those examples that contribute the most to the model quality. There are multiple strategies of active learning. Here, we discuss only the following two: 1. **Data density and uncertainty based** 2. **Support vector-based** **Density × Uncertainty strategy.** The former strategy applies the current model $f$, trained using the existing labeled examples, to each of the remaining unlabelled examples (or, to save the computing time, to some random sample of them). For each unlabeled example $\mathbf{x}$, the following importance score is computed: $$\text{importance}(\mathbf{x}) = \text{density}(\mathbf{x}) \cdot \text{uncertainty}_f(\mathbf{x})$$ Density reflects how many examples surround $\mathbf{x}$ in its close neighborhood, while $\text{uncertainty}_f(\mathbf{x})$ reflects how uncertain the prediction of the model $f$ is for $\mathbf{x}$. In multiclass classification, **entropy** can be used as a typical measure of uncertainty: $$H_f(\mathbf{x}) = -\sum_{c=1}^{C} \Pr(y^{(c)}; f(\mathbf{x})) \ln \Pr(y^{(c)}; f(\mathbf{x}))$$ where $\Pr(y^{(c)}; f(\mathbf{x}))$ is the probability score the model $f$ assigns to class $y^{(c)}$ when classifying $\mathbf{x}$. **Support vector-based strategy.** The support vector-based active learning strategy consists in building an SVM model using the labeled data. We then ask our expert to annotate the unlabeled example that lies the closest to the hyperplane that separates the two classes. ## 7.9 Semi-Supervised Learning In **semi-supervised learning (SSL)** we also have labeled a small fraction of the dataset; most of the remaining examples are unlabeled. Our goal is to leverage a large number of unlabeled examples to improve the model performance without asking an expert for additional labeled examples. Historically, there were multiple attempts at solving this problem. **Self-learning** is a frequently cited SSL method: in self-learning, we use a learning algorithm to build the initial model using the labeled examples. Then we apply the model to all unlabeled examples and label them using the model. If the confidence score of prediction for some unlabeled example $\mathbf{x}$ is higher than some threshold (chosen experimentally), then we add this labeled example to our training set, retrain the model and continue like this until a stopping criterion is satisfied. The recent advancements in neural network learning brought some impressive results. For example, it was shown that for some datasets, such as MNIST, the model trained in a semi-supervised way has an almost perfect performance with just 10 labeled examples per class. The neural network architecture that attained such a remarkable performance is called a **ladder network**. **Autoencoders.** To understand ladder networks you have to understand what an **autoencoder** is. An autoencoder is a feed-forward neural network with an encoder-decoder architecture. It is trained to reconstruct its input. So the training example is a pair $(\mathbf{x}, \mathbf{x})$. We want the output $\hat{\mathbf{x}}$ of the model $f(\mathbf{x})$ to be as similar to the input $\mathbf{x}$ as possible. An important detail here is that an autoencoder's network looks like an hourglass with a bottleneck layer in the middle that contains the embedding of the $D$-dimensional input vector; the embedding layer usually has much fewer units than $D$. The goal of the decoder is to reconstruct the input feature vector from this embedding. If the cost is the mean squared error, then it is given by: $$\frac{1}{N} \sum_{i=1}^{N} \|\mathbf{x}_i - f(\mathbf{x}_i)\|^2$$ where $\|\mathbf{x}_i - f(\mathbf{x}_i)\|$ is the Euclidean distance between two vectors. A **denoising autoencoder** corrupts the left-hand side $\mathbf{x}$ in the training example $(\mathbf{x}, \mathbf{x})$ by adding some random perturbation to the features. A **ladder network** is a denoising autoencoder with an upgrade. The encoder and the decoder have the same number of layers. The bottleneck layer is used directly to predict the label (using the softmax activation function). The combined cost function, $C_c + \sum_{l=1}^{L} \lambda_l C_d^l$ (averaged over all examples in the batch), is optimized by the stochastic gradient descent with backpropagation. ## 7.10 One-Shot Learning **One-shot learning** is typically applied in face recognition. We want to build a model that can recognize that two photos of the same person represent that same person. One way to build such a model is to train a **siamese neural network (SNN)**. To train an SNN, we use the **triplet loss function**. Let us have three images of a face: the image $A$ (for anchor), the image $P$ (for positive) and the image $N$ (for negative). $A$ and $P$ are two different pictures of the same person; $N$ is a picture of another person. Each training example $i$ is now a triplet $(A_i, P_i, N_i)$. The triplet loss for one example is defined as: $$\max\left(\|f(A_i) - f(P_i)\|^2 - \|f(A_i) - f(N_i)\|^2 + \alpha, 0\right) \tag{3}$$ The cost function is defined as the average triplet loss: $$\frac{1}{N} \sum_{i=1}^{N} \max\left(\|f(A_i) - f(P_i)\|^2 - \|f(A_i) - f(N_i)\|^2 + \alpha, 0\right)$$ where $\alpha$ is a positive hyperparameter. Intuitively, $\|f(A) - f(P)\|^2$ is low when our neural network outputs similar embedding vectors for $A$ and $P$; $\|f(A_i) - f(N_i)\|^2$ is high when the embedding for pictures of two different people are different. It's a common misconception that for one-shot learning we need only one example of each entity for training. In practice, we need much more than one example of each person for the person identification model to be accurate. When we have the model, to decide whether two pictures $A$ and $\hat{A}$ belong to the same person, we check if $\|f(A) - f(\hat{A})\|^2$ is less than some threshold $\tau$. ## 7.11 Zero-Shot Learning In **zero-shot learning (ZSL)** we want to train a model to assign labels to objects. The most frequent application is to learn to assign labels to images. However, we want the model to be able to predict labels that we didn't have in the training data. **Word embeddings.** The trick is to use embeddings not just to represent the input $\mathbf{x}$ but also to represent the output $y$. Imagine that we have a model that for any word in English can generate an embedding vector with the following property: if a word $y_i$ has a similar meaning to the word $y_k$, then the embedding vectors for these two words will be similar. For example, if our word embedding has four dimensions, then these four dimensions could represent such features of the meaning as animalness, abstractness, sourness, and yellowness. So the word bee would have an embedding like this $[1, 0, 0, 1]$, the word yellow like this $[0, 1, 0, 1]$, the word unicorn like this $[1, 1, 0, 0]$. In our classification problem, we can replace the label $y_i$ for each example $i$ in our training set with its word embedding and train a multi-label model that predicts word embeddings. To get the label for a new example $\mathbf{x}$, we apply our model $f$ to $\mathbf{x}$, get the embedding $\hat{\mathbf{y}}$ and then search among all English words those whose embeddings are the most similar to $\hat{\mathbf{y}}$ using cosine similarity. --- # Chapter 8: Advanced Practice This chapter contains the description of techniques that you could find useful in your practice in some contexts. It's called "Advanced Practice" not because the presented techniques are more complex, but rather because they are applied in some very specific contexts. ## 8.1 Handling Imbalanced Datasets In many practical situations, your labeled dataset will have underrepresented the examples of some class. This is the case, for example, when your classifier has to distinguish between genuine and fraudulent e-commerce transactions: the examples of genuine transactions are much more frequent. If you use SVM with soft margin, you can define a cost for misclassified examples. If you set the cost of misclassification of examples of the minority class higher, then the model will try harder to avoid misclassifying those examples. Some SVM implementations (including SVC in scikit-learn) allow you to provide weights for every class. **Resampling techniques:** - **Oversampling:** Try to increase the importance of examples of some class by making multiple copies of the examples of this class. - **Undersampling:** Randomly remove from the training set some examples of the majority class. **Synthetic data generation.** You might also try to create synthetic examples by randomly sampling feature values of several examples of the minority class and combining them to obtain a new example of that class. There are two popular algorithms that oversample the minority class by creating synthetic examples: the **synthetic minority oversampling technique (SMOTE)** and the **adaptive synthetic sampling method (ADASYN)**. SMOTE and ADASYN work similarly in many ways. For a given example $\mathbf{x}_i$ of the minority class, they pick $k$ nearest neighbors of this example (let's call this set of $k$ examples $\mathcal{S}_k$) and then create a synthetic example $\mathbf{x}_{new}$ as: $$\mathbf{x}_{new} = \mathbf{x}_i + \lambda (\mathbf{x}_{z_i} - \mathbf{x}_i)$$ where $\mathbf{x}_{z_i}$ is an example of the minority class chosen randomly from $\mathcal{S}_k$. The interpolation hyperparameter $\lambda$ is a random number in the range $[0, 1]$. Some algorithms are less sensitive to the problem of an imbalanced dataset. Decision trees, as well as random forest and gradient boosting, often perform well on imbalanced datasets. ## 8.2 Combining Models Ensemble algorithms, like Random Forest, typically combine models of the same nature. In practice, we can sometimes get an additional performance gain by combining strong models made with different learning algorithms. In this case, we usually use only two or three models. There are three typical ways to combine models: ### Averaging Averaging works for regression as well as those classification models that return classification scores. You simply apply all your models, let's call them base models, to the input $\mathbf{x}$ and then average the predictions. ### Majority Vote Majority vote works for classification models. You apply all your base models to the input $\mathbf{x}$ and then return the majority class among all predictions. In the case of a tie, you either randomly pick one of the classes, or, you return an error message. ### Stacking Stacking consists of building a meta-model that takes the output of your base models as input. Let's say you want to combine a classifier $f_1$ and a classifier $f_2$. To create a training example $(\hat{\mathbf{x}}_i, \hat{y}_i)$ for the stacked model, you set: $$\hat{\mathbf{x}}_i = [f_1(\mathbf{x}), f_2(\mathbf{x})] \quad \text{and} \quad \hat{y}_i = y_i$$ If some of your base models return not just a class, but also a score for each class, you can use these values as features too. The reason that combining multiple models can bring better performance overall is the observation that when several uncorrelated strong models agree they are more likely to agree on the correct outcome. ## 8.3 Training Neural Networks In neural network training, one challenging aspect is to convert your data into the input the network can work with. If your input is images, first of all, you have to resize all images so that they have the same dimensions. After that, pixels are usually first standardized and then normalized to the range $[0, 1]$. **Text processing.** Texts have to be tokenized (that is split into pieces, such as words, punctuation marks, and other symbols). For CNN and RNN, each token is converted into a vector using the one-hot encoding. Another, often a better way to represent tokens is by using word embeddings. **Architecture selection.** The choice of specific neural network architecture is a difficult one. For the same problem, like seq2seq learning, there is a variety of architectures, and new ones are proposed almost every year. In practice, the advantage of modern architecture over an older one becomes less significant as you preprocess, clean and normalize your data, and create a larger training set. Once you decided on the architecture of your network, you have to decide on the number of layers, their type, and size. It is recommended to start with one or two layers, train a model and see if it fits the training data well (has a low bias). If not, gradually increase the size of each layer and the number of layers until the model perfectly fits the training data. Once this is the case, if the model doesn't perform well on the validation data (has a high variance), you should add regularization to your model. ## 8.4 Advanced Regularization In neural networks, besides L1 and L2 regularization, you can use neural network specific regularizers: **dropout**, **batch normalization**, and **early stopping**. ### Dropout The concept of dropout is very simple. Each time you run a training example through the network, you temporarily exclude at random some units from the computation. The higher the percentage of units excluded the higher the regularization effect. The dropout parameter is in the range $[0, 1]$ and it has to be found experimentally. ### Batch Normalization Batch normalization (which rather has to be called batch standardization) is a technique that consists of standardizing the outputs of each layer before the units of the subsequent layer receive them as input. In practice, batch normalization results in a faster and more stable training, as well as in some regularization effect. ### Early Stopping Early stopping is the way to train a neural network by saving the preliminary model after every epoch and assessing the performance of the preliminary model on the validation set. If you keep, in a file, the version of the model after each epoch, you can stop the training once you start observing a decreased performance on the validation set. ### Data Augmentation Another regularization technique that can be applied not just to neural networks, but to virtually any learning algorithm, is called **data augmentation**. This technique is often used to regularize models that work with images. Once you have your original labeled training set, you can create a synthetic example from an original example by applying various transformations to the original image: zooming it slightly, rotating, flipping, darkening, and so on. ## 8.5 Handling Multiple Inputs In many of your practical problems, you will work with multimodal data. For example, your input could be an image and text and the binary output could indicate whether the text describes this image or not. Shallow learning algorithms are not particularly well suited to work with multimodal data. However, it doesn't mean that it is impossible. For example, you can train one model on the image and another one on the text. Then you can use a model combination technique. If you cannot divide your problem into two independent subproblems, you can try to vectorize each input and then simply concatenate two feature vectors together to form one wider feature vector. With neural networks, you have more flexibility. You can build two subnetworks, one for each type of input. For example, a CNN subnetwork would read the image while an RNN subnetwork would read the text. Both subnetworks have as their last layer an embedding. You can then concatenate two embeddings and then add a classification layer, such as softmax or sigmoid, on top of the concatenated embeddings. ## 8.6 Handling Multiple Outputs In some problems, you would like to predict multiple outputs for one input. We considered multi-label classification in the previous chapter. Some problems with multiple outputs can be effectively converted into a multi-label classification problem. However, in some cases the outputs are multimodal, and their combinations cannot be effectively enumerated. Consider the following example: you want to build a model that detects an object on an image and returns its coordinates. The same model has to also return the label of the object, such as "person," "cat," or "hamster." To handle a situation like this, you can create one subnetwork that would work as an encoder. Then you add two other subnetworks on top of the embedding layer: one for coordinates (with ReLU last layer and MSE cost $C_1$) and one for the label probabilities (with softmax last layer and cross-entropy cost $C_2$). You can define a combined cost function with hyperparameter $\gamma \in (0, 1)$: $$\gamma C_1 + (1 - \gamma) C_2$$ Then you tune the value for $\gamma$ on the validation data just like any other hyperparameter. ## 8.7 Transfer Learning **Transfer learning** is probably where neural networks have a unique advantage over the shallow models. In transfer learning, you pick an existing model trained on some dataset, and you adapt this model to predict examples from another dataset, different from the one the model was built on. Transfer learning in neural networks works like this: 1. **Build initial model.** You build a deep model on the original big dataset. 2. **Compile new dataset.** You compile a much smaller labeled dataset for your second model. 3. **Remove last layers.** You remove the last one or several layers from the first model. Usually, these are layers responsible for the classification or regression. 4. **Replace with new layers.** You replace the removed layers with new layers adapted for your new problem. 5. **Freeze parameters.** You "freeze" the parameters of the layers remaining from the first model. 6. **Train new layers.** You use your smaller labeled dataset and gradient descent to train the parameters of only the new layers. Even if you don't have an existing model, transfer learning can still help you in situations when your problem requires a labeled dataset very costly to obtain, but you can get another dataset for which labels are more readily available. ## 8.8 Algorithmic Efficiency Not all algorithms capable of solving a problem are practical. Some can be fast; some can be too slow. Some problems can be solved by a fast algorithm, for others, no fast algorithms can exist. Consider the following algorithm to find the maximum distance: ```python def find_max_distance(S): result = None max_distance = 0 for x1 in S: for x2 in S: if abs(x1 - x2) >= max_distance: max_distance = abs(x1 - x2) result = (x1, x2) return result ``` In the above algorithm, we loop over all values in $\mathcal{S}$, and at every iteration of the first loop, we loop over all values in $\mathcal{S}$ once again. Therefore, the above algorithm makes $N^2$ comparisons. The time complexity is $O(N^2)$. For the same problem, we can craft another algorithm: ```python def find_max_distance(S): result = None min_x = float("inf") max_x = float("-inf") for x in S: if x < min_x: min_x = x if x > max_x: max_x = x result = (max_x, min_x) return result ``` In the above algorithm, we loop over all values in $\mathcal{S}$ only once, so the algorithm's complexity is $O(N)$. In this case, we say that the latter algorithm is more efficient than the former. Usually, an algorithm is called efficient when its complexity in big O notation is polynomial in the size of the input. Therefore both $O(N)$ and $O(N^2)$ are efficient. However, for very large inputs an $O(N^2)$ algorithm can still be very slow. **Efficiency tips:** - Use efficient low-level operations (e.g., `numpy.dot` instead of explicit loops). - Use appropriate data structures. If the order of elements in a collection doesn't matter, use `set` instead of `list`. - Use `dict` for very fast lookups. - Unless you know exactly what you do, always prefer using popular libraries to writing your own scientific code. - If you need to iterate over a vast collection of elements, use generators. - Use `cProfile` package in Python to find inefficiencies in your code. - Use `multiprocessing` package to run computations in parallel. - Use PyPy, Numba or similar tools to compile your Python code into fast, optimized machine code. --- # Chapter 9: Unsupervised Learning Unsupervised learning deals with problems in which your dataset doesn't have labels. This property is what makes it very problematic for many practical applications. The absence of labels which represent the desired behavior for your model means the absence of a solid reference point to judge the quality of your model. In this book, I only present unsupervised learning methods that allow building models that can be evaluated based on data as opposed to human judgment. ## 9.1 Density Estimation **Density estimation** is a problem of modeling the probability density function (pdf) of the unknown probability distribution from which the dataset has been drawn. It can be useful for many applications, in particular for novelty or intrusion detection. Let $\{x_i\}_{i=1}^N$ be a one-dimensional dataset whose examples were drawn from a distribution with an unknown pdf $f$ with $x_i \in \mathbb{R}$ for all $i = 1, \ldots, N$. We are interested in modeling the shape of this function $f$. Our kernel model of $f$, let's denote it as $\hat{f}$, is given by: $$\hat{f}_b(x) = \frac{1}{Nb} \sum_{i=1}^{N} k\left(\frac{x - x_i}{b}\right) \tag{1}$$ where $b$ is a hyperparameter that controls the tradeoff between bias and variance of our model and $k$ is a kernel. Again, we use a Gaussian kernel: $$k(z) = \frac{1}{\sqrt{2\pi}} \exp\left(\frac{-z^2}{2}\right)$$ We look for such a value of $b$ that minimizes the difference between the real shape of $f$ and the shape of our model $\hat{f}_b$. A reasonable choice of measure of this difference is called the **mean integrated squared error**: $$\mathrm{MISE}(b) = \mathbb{E}\left[\int_{\mathbb{R}} (\hat{f}_b(x) - f(x))^2 \, dx\right] \tag{2}$$ To find the optimal value $b^*$ for $b$, we want to minimize the cost defined as: $$\int_{\mathbb{R}} \hat{f}_b^2(x) \, dx - \frac{2}{N} \sum_{i=1}^{N} \hat{f}_b^{(i)}(x_i)$$ We can find $b^*$ using grid search. For $D$-dimensional feature vectors $\mathbf{x}$, the error term $x - x_i$ in eq. 1 can be replaced by the Euclidean distance $\|\mathbf{x} - \mathbf{x}_i\|$. ## 9.2 Clustering **Clustering** is a problem of learning to assign a label to examples by leveraging an unlabeled dataset. Because the dataset is completely unlabeled, deciding on whether the learned model is optimal is much more complicated than in supervised learning. There is a variety of clustering algorithms, and unfortunately, it's hard to tell which one is better in quality for your dataset. ### 9.2.1 K-Means The **k-means** clustering algorithm works as follows: 1. The analyst has to choose $k$ — the number of classes (or clusters). 2. Then we randomly put $k$ feature vectors, called **centroids**, into the feature space. 3. We then compute the distance from each example $\mathbf{x}$ to each centroid $\mathbf{c}$ using some metric, like the Euclidean distance. 4. Then we assign the closest centroid to each example. 5. For each centroid, we calculate the average feature vector of the examples labeled with it. These average feature vectors become the new locations of the centroids. 6. We recompute the distance from each example to each centroid, modify the assignment and repeat the procedure until the assignments don't change after the centroid locations were recomputed. The initial position of centroids influence the final positions, so two runs of k-means can result in two different models. The value of $k$, the number of clusters, is a hyperparameter that has to be tuned by the data analyst. ### 9.2.2 DBSCAN and HDBSCAN While k-means and similar algorithms are centroid-based, **DBSCAN** is a density-based clustering algorithm. Instead of guessing how many clusters you need, by using DBSCAN, you define two hyperparameters: $\epsilon$ and $n$. The advantage of DBSCAN is that it can build clusters that have an arbitrary shape, while kmeans and other centroid-based algorithms create clusters that have a shape of a hypersphere. An obvious drawback of DBSCAN is that it has two hyperparameters and choosing good values for them (especially $\epsilon$) could be challenging. **HDBSCAN** is the clustering algorithm that keeps the advantages of DBSCAN, by removing the need to decide on the value of $\epsilon$. The algorithm is capable of building clusters of varying density. HDBSCAN only has one important hyperparameter: $n$, that is the minimum number of examples to put in a cluster. ### 9.2.3 Determining the Number of Clusters The most important question is how many clusters does your dataset have? There's one practically useful method of determining the reasonable number of clusters based on the concept of **prediction strength**. The idea is to split the data into training and test set, similarly to how we do in supervised learning. Once you have the training and test sets, $\mathcal{S}_{tr}$ of size $N_{tr}$ and $\mathcal{S}_{te}$ of size $N_{te}$ respectively, you fix $k$, the number of clusters, and run a clustering algorithm $\mathcal{C}$ on sets $\mathcal{S}_{tr}$ and $\mathcal{S}_{te}$ and obtain the clustering results $\mathcal{C}(\mathcal{S}_{tr}, k)$ and $\mathcal{C}(\mathcal{S}_{te}, k)$. Define the $N_{te} \times N_{te}$ **co-membership matrix** $\mathbf{D}[A, \mathcal{S}_{te}]$ as follows: $\mathbf{D}[A, \mathcal{S}_{te}]^{(i, i')} = 1$ if and only if examples $\mathbf{x}_i$ and $\mathbf{x}_{i'}$ from the test set belong to the same cluster according to the clustering $A$. Otherwise $\mathbf{D}[A, \mathcal{S}_{te}]^{(i, i')} = 0$. **Prediction strength formula.** More formally, the prediction strength for the number of clusters $k$ is given by: $$\mathrm{ps}(k) \stackrel{\mathrm{def}}{=} \min_{j=1, \ldots, k} \frac{1}{|A_j|(|A_j| - 1)} \sum_{i, i' \in A_j} \mathbf{D}[A, \mathcal{S}_{te}]^{(i, i')}$$ where $A \stackrel{\mathrm{def}}{=} \mathcal{C}(\mathcal{S}_{tr}, k)$, $A_j$ is $j$-th cluster from the clustering $\mathcal{C}(\mathcal{S}_{te}, k)$ and $|A_j|$ is the number of examples in cluster $A_j$. Experiments suggest that a reasonable number of clusters is the largest $k$ such that $\mathrm{ps}(k)$ is above $0.8$. ### 9.2.4 Other Clustering Algorithms: Gaussian Mixture Model DBSCAN and k-means compute so-called **hard clustering**, in which each example can belong to only one cluster. Gaussian mixture model (GMM) allows each example to be a member of several clusters with different membership score. In GMM, instead of having just one multivariate normal distribution (MND), we have a weighted sum of several MNDs: $$f_X = \sum_{j=1}^{k} \phi_j f_{\boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j}$$ where $f_{\boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j}$ is a MND $j$, and $\phi_j$ is its weight in the sum. For simplicity, let us look at the one-dimensional data. Also assume that there are two clusters: $k = 2$. In this case, we have two Gaussian distributions: $$f(x | \mu_1, \sigma_1^2) = \frac{1}{\sqrt{2\pi\sigma_1^2}} \exp\left(-\frac{(x - \mu_1)^2}{2\sigma_1^2}\right) \quad \text{and} \quad f(x | \mu_2, \sigma_2^2) = \frac{1}{\sqrt{2\pi\sigma_2^2}} \exp\left(-\frac{(x - \mu_2)^2}{2\sigma_2^2}\right) \tag{3}$$ We use the **EM algorithm** to estimate the parameters. EM works like follows. In the beginning, we guess the initial values for $\mu_1, \sigma_1^2, \mu_2, \sigma_2^2$, and set $\phi_1 = \phi_2 = \frac{1}{2}$. At each iteration of EM, the following four steps are executed: **Step 1:** For all $i = 1, \ldots, N$, calculate the likelihood of each $x_i$ using eq. 3: $$f(x_i | \mu_1, \sigma_1^2) \leftarrow \frac{1}{\sqrt{2\pi\sigma_1^2}} \exp\left(-\frac{(x_i - \mu_1)^2}{2\sigma_1^2}\right) \quad \text{and} \quad f(x_i | \mu_2, \sigma_2^2) \leftarrow \frac{1}{\sqrt{2\pi\sigma_2^2}} \exp\left(-\frac{(x_i - \mu_2)^2}{2\sigma_2^2}\right)$$ **Step 2:** Using Bayes' Rule, for each example $x_i$, calculate the likelihood $b_i^{(j)}$ that the example belongs to cluster $j \in \{1, 2\}$: $$b_i^{(j)} \leftarrow \frac{f(x_i | \mu_j, \sigma_j^2) \phi_j}{f(x_i | \mu_1, \sigma_1^2) \phi_1 + f(x_i | \mu_2, \sigma_2^2) \phi_2}$$ **Step 3:** Compute the new values of $\mu_j$ and $\sigma_j^2$, $j \in \{1, 2\}$ as: $$\mu_j \leftarrow \frac{\sum_{i=1}^{N} b_i^{(j)} x_i}{\sum_{i=1}^{N} b_i^{(j)}} \quad \text{and} \quad \sigma_j^2 \leftarrow \frac{\sum_{i=1}^{N} b_i^{(j)} (x_i - \mu_j)^2}{\sum_{i=1}^{N} b_i^{(j)}} \tag{4}$$ **Step 4:** Update $\phi_j$, $j \in \{1, 2\}$ as: $$\phi_j \leftarrow \frac{1}{N} \sum_{i=1}^{N} b_i^{(j)}$$ The steps $1-4$ are executed iteratively until the values $\mu_j$ and $\sigma_j^2$ don't change much. You may have noticed that the EM algorithm is very similar to the k-means algorithm: start with random clusters, then iteratively update each cluster's parameters by averaging the data that is assigned to that cluster. The only difference in the case of the GMM is that the assignment of an example $x_i$ to the cluster $j$ is **soft**: $x_i$ belongs to cluster $j$ with probability $b_i^{(j)}$. ## 9.3 Dimensionality Reduction Many modern machine learning algorithms handle well very high-dimensional examples. The most frequent use case for dimensionality reduction is data visualization: humans can only interpret on a plot the maximum of three dimensions. The three most widely used techniques of dimensionality reduction are **principal component analysis (PCA)**, **uniform manifold approximation and projection (UMAP)**, and **autoencoders**. ### 9.3.1 Principal Component Analysis **Principal component analysis** or PCA is one of the oldest methods. Consider a two-dimensional data. 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. If we want to reduce the dimensionality of our data to $D_{new} < D$, we pick $D_{new}$ largest principal components and project our data points on them. 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. In UMAP, this similarity metric $w$ is defined as follows: $$w(\mathbf{x}_i, \mathbf{x}_j) \stackrel{\mathrm{def}}{=} w_i(\mathbf{x}_i, \mathbf{x}_j) + w_j(\mathbf{x}_j, \mathbf{x}_i) - w_i(\mathbf{x}_i, \mathbf{x}_j) w_j(\mathbf{x}_j, \mathbf{x}_i) \tag{5}$$ The function $w_i(\mathbf{x}_i, \mathbf{x}_j)$ is defined as: $$w_i(\mathbf{x}_i, \mathbf{x}_j) \stackrel{\mathrm{def}}{=} \exp\left(-\frac{d(\mathbf{x}_i, \mathbf{x}_j) - \rho_i}{\sigma_i}\right)$$ where $d(\mathbf{x}_i, \mathbf{x}_j)$ is the Euclidean distance between two examples, $\rho_i$ is the distance from $\mathbf{x}_i$ to its closest neighbor, and $\sigma_i$ is the distance from $\mathbf{x}_i$ to its $k$-th closest neighbor ($k$ is a hyperparameter of the algorithm). A widely used metric of similarity between two probability distributions is **cross-entropy**: $$C(w, w') = \sum_{i=1}^{N} \sum_{j=1}^{N} w(\mathbf{x}_i, \mathbf{x}_j) \ln\left(\frac{w(\mathbf{x}_i, \mathbf{x}_j)}{w'(\mathbf{x}_i', \mathbf{x}_j')}\right) + (1 - w(\mathbf{x}_i, \mathbf{x}_j)) \ln\left(\frac{1 - w(\mathbf{x}_i, \mathbf{x}_j)}{1 - w'(\mathbf{x}_i', \mathbf{x}_j')}\right) \tag{6}$$ In eq. 6 the unknown parameters are $\mathbf{x}_i'$ (for all $i = 1, \ldots, N$) and we can compute them by gradient descent by minimizing $C(w, w')$. ## 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. --- # Chapter 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. You can create your metric that would work better for your dataset. We can modify the Euclidean distance to make it parametrizable and then learn these parameters from data. Consider the following modification: $$d_{\mathbf{A}}(\mathbf{x}, \mathbf{x}') = \|\mathbf{x} - \mathbf{x}'\|_{\mathbf{A}} \stackrel{\mathrm{def}}{=} \sqrt{(\mathbf{x} - \mathbf{x}')^\top \mathbf{A} (\mathbf{x} - \mathbf{x}')}$$ where $\mathbf{A}$ is a $D \times D$ matrix. If $\mathbf{A}$ is the identity matrix, then $d_{\mathbf{A}}$ becomes the Euclidean distance. If we have a general diagonal matrix, then different dimensions have different importance in the metric calculation. **Metric conditions.** More generally, to be called a metric a function of two variables has to satisfy three conditions: $$\begin{cases} d(\mathbf{x}, \mathbf{x}') \geq 0 & \text{(nonnegativity)} \\ d(\mathbf{x}, \mathbf{x}') \leq d(\mathbf{x}, \mathbf{x}') + d(\mathbf{x}', \mathbf{z}) & \text{(triangle inequality)} \\ d(\mathbf{x}, \mathbf{x}') = d(\mathbf{x}', \mathbf{x}) & \text{(symmetry)} \end{cases}$$ To satisfy the first two conditions, the matrix $\mathbf{A}$ has to be **positive semidefinite**. Any positive semidefinite matrix $\mathbf{M}$ satisfies: $$\mathbf{z}^\top \mathbf{M} \mathbf{z} \geq 0$$ To satisfy the third condition, we can simply take $(d(\mathbf{x}, \mathbf{x}') + d(\mathbf{x}', \mathbf{x})) / 2$. **Training the metric.** Let's say we have an unannotated set $\mathcal{X} = \{\mathbf{x}_i\}_{i=1}^N$. To build the training data for our metric learning problem, we manually create two sets. The first set $\mathcal{S}$ is such that a pair of examples $(\mathbf{x}_i, \mathbf{x}_k)$ belongs to set $\mathcal{S}$ if $\mathbf{x}_i$ and $\mathbf{x}_k$ are similar (from our subjective perspective). The second set $\mathcal{D}$ is such that a pair of examples $(\mathbf{x}_i, \mathbf{x}_k)$ belongs to set $\mathcal{D}$ if $\mathbf{x}_i$ and $\mathbf{x}_k$ are dissimilar. To train the matrix of parameters $\mathbf{A}$ from the data, we want to find a positive semidefinite matrix $\mathbf{A}$ that solves the following optimization problem: $$\min_{\mathbf{A}} \sum_{(\mathbf{x}_i, \mathbf{x}_k) \in \mathcal{S}} \|\mathbf{x} - \mathbf{x}'\|_{\mathbf{A}}^2 \quad \text{such that} \quad \sum_{(\mathbf{x}_i, \mathbf{x}_k) \in \mathcal{D}} \|\mathbf{x} - \mathbf{x}'\|_{\mathbf{A}} \geq c$$ where $c$ is a positive constant (can be any number). ## 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 $\mathcal{X}_i$ in the training set of size $N$ is a ranked collection of documents of size $r_i$ (labels are ranks of documents). A feature vector represents each document in the collection. Each example $\mathcal{X}_i$, $i = 1, \ldots, N$, is a collection of feature vectors with labels: $\mathcal{X}_i = \{(\mathbf{x}_{i,j}, y_{i,j})\}_{j=1}^{r_i}$. 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. **Pairwise approach:** the problem considers documents in pairs. Given a pair of documents $(\mathbf{x}_i, \mathbf{x}_k)$ we want to build a model $f$ that, given $(\mathbf{x}_i, \mathbf{x}_k)$ as input, outputs a value close to 1 if $\mathbf{x}_i$ has to be put higher than $\mathbf{x}_k$ in the ranking. Otherwise, $f$ outputs a value close to 0. **Listwise approach:** we try to optimize the model directly on some metric that reflects the quality of ranking. The state of the art rank learning algorithms, such as **LambdaMART**, implement the listwise approach. **MAP metric.** One popular metric that combines both precision and recall is called **mean average precision (MAP)**. The precision of our model for some query is given by: $$\mathrm{Precision@k} = \frac{\text{number of relevant documents among top } k}{k}$$ The average precision at position $k$ for a given query is the average of precision at each position $i \leq k$, where $i$ is a position where a relevant document was found. The mean average precision is simply the average of average precisions over all queries in our test set. ## 10.3 Learning to Recommend **Learning 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. 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. The content-based approach has many limitations, including the **filter bubble** problem. **Collaborative filtering** has a significant advantage over content-based filtering: the recommendations to one user are computed based on what other users consume or rate. 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. Two effective collaborative-filtering learning algorithms are **factorization machines (FM)** and **denoising autoencoders (DAE)**. ### 10.3.1 Factorization Machines The factorization machine model is defined as: $$f(\mathbf{x}) \stackrel{\mathrm{def}}{=} b + \sum_{i=1}^{D} w_i x_i + \sum_{i=1}^{D} \sum_{j=i+1}^{D} (\mathbf{v}_i \mathbf{v}_j) x_i x_j$$ where $b$ and $w_i$, $i = 1, \ldots, D$ are scalar parameters similar to those used in linear regression. Vectors $\mathbf{v}_i$, $i = 1, \ldots, D$, are $k$-dimensional vectors of factors. $k$ is a hyperparameter and is usually much smaller than $D$. The expression $(\mathbf{v}_i \mathbf{v}_j)$ is a dot-product of the $i$-th and $j$-th vectors of factors. Instead of having a parameter $w_{i,j}$ for each interaction, which would add an enormous quantity of new parameters to the model, we factorize $w_{i,j}$ into $\mathbf{v}_i \mathbf{v}_j$ by adding only $Dk \ll D(D-1)$ parameters to the model. Depending on the problem, the loss function could be squared error loss (for regression) or hinge loss. For classification with $y \in \{-1, +1\}$, with hinge loss or **logistic loss** the prediction is made as $y = \mathrm{sign}(f(x))$. The logistic loss is defined as: $$\mathrm{loss}(f(\mathbf{x}), y) = \frac{1}{\ln 2} \ln(1 + e^{-y f(\mathbf{x})})$$ ### 10.3.2 Denoising Autoencoders From Chapter 7, you know what a denoising autoencoder is: it's a neural network that reconstructs its input from the bottleneck layer. The fact that the input is corrupted by noise while the output shouldn't be, makes denoising autoencoders an ideal tool to build a recommender model. The idea is very straightforward: new movies a user could like are seen as if they were removed from the complete set of preferred movies by some corruption process. The goal of the denoising autoencoder is to reconstruct those removed items. ## 10.4 Self-Supervised Learning: Word Embeddings We have already discussed word embeddings in Chapter 7. Recall that word embeddings are feature vectors that represent words. They have the property that similar words have similar word vectors. In word embedding learning, our goal is to build a model which we can use to convert a one-hot encoding of a word into a word embedding. Let our dictionary contain 10000 words. **Skip-gram model.** Consider a sentence: "I almost finished reading the book on machine learning." Now, consider the same sentence from which we have removed some word, say "book." Our sentence becomes: "I almost finished reading the - on machine learning." Now let's only keep the three words before the - and three words after it: "finished reading the - on machine learning." Looking at this seven-word window around the -, if I ask you to guess what - stands for, you would probably say: "book," "article," or "paper." The piece "finished reading the - on machine learning" is called a **skip-gram** with window size 7 (3 + 1 + 3). Let's denote words in a skip-gram like this: $[x_{-3}, x_{-2}, x_{-1}, x, x_{+1}, x_{+2}, x_{+3}]$. The skip-gram model with window size 5 is a fully-connected network, like the multilayer perceptron. The input word is the one denoted as - in our skip-gram. The neural network has to learn to predict the context words of the skip-gram given the central word. You can see now why the learning of this kind is called **self-supervised**: the labeled examples get extracted from the unlabeled data such as text. The activation function used in the output layer is softmax. The cost function is the negative log-likelihood. The embedding for a word is obtained as the output of the embedding layer when the one-hot encoding of this word is given as the input to the model. Because of the large number of parameters in the word2vec models, two techniques are used to make the computation more efficient: **hierarchical softmax** and **negative sampling**. --- # Chapter 11: Conclusion Wow, that was fast! You are really good if you got here and managed to understand most of the book's material. If you look at the number at the bottom of this page, you see that we have overspent paper, which means that the title of the book was slightly misleading. I hope that you forgive me this little marketing trick. However, by stopping now, I feel confident that you have got everything you need to become a great modern data analyst or machine learning engineer. That doesn't mean that I covered everything, but what I covered in a hundred pages you would find in a bunch of books, each thousand-page thick. What exactly I didn't cover, but would have covered if it was a thousand-page machine learning book? ## 11.1 Topic Modeling In text analysis, topic modeling is a prevalent unsupervised learning problem. You have a collection of text documents, and you would like to discover topics present in each document. **Latent Dirichlet Allocation (LDA)** is a very effective algorithm of topic discovery. ## 11.2 Gaussian Processes **Gaussian processes (GP)** is a supervised learning method that competes with kernel regression. It has some advantages over the latter. For example, it provides confidence intervals for the regression line in each point. ## 11.3 Generalized Linear Models **Generalized linear model (GLM)** is a generalization of the linear regression to modeling various forms of dependency between the input feature vector and the target. Logistic regression, for instance, is one form of GLMs. ## 11.4 Probabilistic Graphical Models We have mentioned one example of probabilistic graphical models (PGMs) in Chapter 7: **conditional random fields (CRF)**. With CRF we can model the input sequence of words and relationships between the features and labels in this sequence as a sequential dependency graph. More generally, a PGM can be any graph. PGMs are also known under names of Bayesian networks, belief networks, and probabilistic independence networks. ## 11.5 Markov Chain Monte Carlo If you work with graphical models and want to sample examples from a very complex distribution defined by the dependency graph, you could use **Markov chain Monte Carlo (MCMC)** algorithms. ## 11.6 Genetic Algorithms **Genetic algorithms (GA)** are a numerical optimization technique used to optimize undifferentiated optimization objective functions. They use concepts from evolutionary biology to search for a global optimum (minimum or maximum) of an optimization problem, by mimicking evolutionary biological processes. GA work by starting with an initial generation of candidate solutions. If we look for optimal values of the parameters of our model, we first randomly generate multiple combinations of parameter values. Genetic algorithms allow finding solutions to any measurable optimization criteria. For example, GA can be used to optimize the hyperparameters of a learning algorithm. They are typically much slower than gradient-based optimization techniques. ## 11.7 Reinforcement Learning As we already discussed, **reinforcement learning (RL)** solves a very specific kind of problems where the decision making is sequential. Usually, there's an agent acting in an unknown environment. Each action brings a reward and moves the agent to another state of the environment (usually, as a result of some random process with unknown properties). The goal of the agent is to optimize its long-term reward. Reinforcement learning algorithms, such as **Q-learning**, as well as its neural network based counterparts, are used in learning to play video games, robotic navigation and coordination, inventory and supply chain management, optimization of complex electric power systems (power grids), and learning financial trading strategies.