Model Families

Recall that we expressed our fraud dataset in terms of seven numerical features: four features from the raw data and three from the one-hot encoding of the payment method. We can thus think of each transaction as a point in a seven-dimensional real vector space, and our goal is to divide up the space into areas of fraud and nonfraud transactions. The “model” output by our machine learning algorithm is a description of this division of the vector space.

In theory, the division of our vector space into fraud and nonfraud areas can be infinitely complex; in practice, most algorithms produce a decision boundary, which is a surface in the vector space.⁷ One side of the decision boundary consists of the points labeled as fraud, and the other side consists of the points labeled as nonfraud. The boundary can be as simple as a line (or hyperplane in higher dimensions) or as complex as a union of nonlinear disconnected regions. Figure 2-1 presents some examples.

Figure 2-1. Examples of two-dimensional spaces divided by a decision boundary

If we want to be more granular, instead of mapping each point in the vector space to either “fraud” or “nonfraud,” we can map each point to a probability of fraud. In this case our machine learning algorithm outputs a function that assigns each point in the vector space a value between 0 and 1, to be interpreted in our example as the probability of fraud.

Any given machine learning algorithm restricts itself to finding a certain type of decision boundary or probability function that can be described by a finite number of model parameters. The simplest decision boundary is a linear decision boundary—that is, a hyperplane in the vector space. An oriented hyperplane H in an n-dimensional vector space can be described by an n-dimensional vector $\mathit{\theta }$ orthogonal to the hyperplane, plus another vector $\mathit{\beta }$ indicating how far the hyperplane is from the origin:

This description allows us to divide the vector space in two; to assign probabilities we want to look at the distance of the point $\mathit{x}$ from the hyperplane H. We can thus compute a real-valued “score”:

where we have let $b=-\mathit{\theta }·\mathit{\beta }$. Our model to compute the score can thus be described by n + 1 model parameters: n parameters to describe the vector $\mathit{\theta }$, and one “offset” parameter b. To turn the score into a classification, we simply choose a threshold t above which all scores indicate fraud, and below which all scores indicate nonfraud.

If we want to map the real-valued score $s\left(\mathit{x}\right)$ to a probability, we must apply a function that maps the real numbers to the interval [0,1]. The standard function to apply is known as the logistic function or sigmoid function,⁸ as illustrated in Figure 2-2. It is formulated as:

Figure 2-2. The sigmoid function

The output of the logistic function can be interpreted as a probability, allowing us to define the likelihood of the dependent variable taking on a particular value given some input feature vector $\mathit{x}$.

Loss Functions

Now that we have restricted our choice of prediction algorithms to a certain parametrized family, we must choose the best one for the given training data. How do we know when we have found the best algorithm? We define the best algorithm to be one that optimizes some quantity computed from the data. This quantity is called an objective function. In the case of machine learning, the objective function is also known as a cost function or loss function, because it measures the “cost” of wrong predictions or the “loss” associated with them.

Mathematically, a loss function is a function that maps a set of pairs of (predicted label, truth label) to a real number. The goal of a machine learning algorithm is to find the model parameters that produce predicted labels for the training set that minimize the loss function.

In regression problems, for which the prediction algorithm outputs a real number instead of a label, the standard loss function is the sum of squared errors. If $y_i$ is the true value and ${\widehat{y}}_i$ is the predicted value, the loss function is as follows:

We can use this loss function for classification problems as well, where $y_i$ is either 0 or 1, and ${\widehat{y}}_i$ is the probability estimate output by the algorithm.

For logistic regression, we use negative log likelihood as the loss function. The likelihood of a set of probability predictions $\left\{p_i\right\}$ for a given set of ground truth labels $\left\{y_i\right\}$ is defined to be the probability that these truth labels would have arisen if sampled from a set of binomial distributions according to the probabilities $\left\{p_i\right\}$. Concretely, if the truth label $y_i$ is 0, the likelihood of 0 is $1-p_i$—the probability that 0 would have been sampled from a binomial distribution with mean $p_i$. If the truth label $y_i$ is 1, the likelihood is $p_i$.

The likelihood of the entire set of predictions is the product of the individual likelihoods:

The goal of logistic regression is to find parameters that produce probabilities $\left\{p_i\right\}$ that maximize the likelihood.

To make computations easier, and, in particular, because most optimization methods require computing derivatives of the loss function, we take the negative log of the likelihood. As maximizing the likelihood is equivalent to minimizing the negative log likelihood, we call negative log likelihood the loss function:

Here we have used the fact that $y_i$ is always 0 or 1 to combine the two products into a single term.

Optimization

The last step in the machine learning procedure is to search for the optimal set of parameters that minimizes the loss function. To carry out this search we use an optimization algorithm. There may be many different optimization algorithms available to you when fitting your machine learning model.⁹ Most scikit-learn estimators (e.g., LogisticRegression) allow you to specify the numerical solver to use, but what are the differences between the different options, and how do you go about selecting one?

The job of an optimization algorithm is to minimize (or maximize) an objective function. In the case of machine learning, the objective function is expressed in terms of the model’s learnable parameters ($\mathit{\theta }$ and b in the previous example), and the goal is to find the values of $\mathit{\theta }$ and b that optimize the objective function.

Optimization algorithms mainly come in two different flavors:

First-order algorithms

These algorithms optimize the objective function using the first derivatives of the function with respect to the learnable parameters. Gradient descent methods are the most popular types of first-order optimization algorithms; we can use them to find the inputs to a function that give the minimum (or maximum) value. Computing the gradient of a function (i.e., the partial derivatives with respect to each variable) allows us to determine the instantaneous direction that the parameters need to move in order to achieve a more optimal outcome.

Second-order algorithms

As the name suggests, these algorithms use the second derivatives to optimize the objective function. Second-order algorithms will not fall victim to paths of slow convergence. For example, second-order algorithms are good at detecting saddle points, whereas first-order algorithms are likely to become stuck at these points. However, second-order methods are often slower and more expensive to compute.

First-order methods tend to be much more frequently used because of their relative efficiency. Picking a suitable optimization algorithm depends on the size of the dataset, the nature of the cost function, the type of learning problem, and speed/resource requirements for the operation. In addition, some regularization techniques can also have compatibility issues with certain types of optimizers. First-order algorithms include the following:

• LIBLINEAR¹⁰ is the default solver for the linear estimators in scikit-learn. This algorithm tends to not do well on larger datasets; as suggested by the scikit-learn documentation, the Stochastic Average Gradient (SAG) or SAGA (improvement to SAG) methods work better for large datasets.¹¹

  Different optimization algorithms deal with multiclass classification differently. LIBLINEAR works only on binary classification. For it to work in a multiclass scenario, it has to use the one-versus-rest scheme; we discuss this scheme more fully in Chapter 5.

• Stochastic Gradient Descent (SGD) is a very simple and efficient algorithm for optimization that performs a parameter update for each separate training example. The stochastic nature of the gradient descent means that the algorithm is more likely to discover new and possibly better local minima as compared to standard gradient descent. However, it typically results in high-variance oscillations, which can result in a delay in convergence. This can be solved with a decreasing learning rate (i.e., exponentially decrease the learning rate) that results in smaller fluctuations as the algorithm approaches convergence.

  The technique called momentum also helps accelerate SGD convergence by navigating the optimization movement only in the relevant directions and softening any movement in irrelevant directions, which stabilizes SGD.

• Optimization algorithms such as AdaGrad, AdaDelta, and Adam (Adaptive Moment Estimation) allow for separate and adaptive learning rates for each parameter that solve some problems in the other simpler gradient descent algorithms.

• When your training dataset is large, you will need to use a distributed optimization algorithm. One popular algorithm is the Alternating Direction Method of Multipliers (ADMM).¹²

Example: Gradient descent

To conclude this section, we go briefly into the details of gradient descent, a powerful optimization algorithm that has been applied to many different machine learning problems.

The standard algorithm for gradient descent is as follows:

1. Select random starting parameters for the machine learning model. In the case of a linear model, this means selecting a random normal vector $\mathit{\theta }$ and offset $\mathit{\beta }$, which results in a random hyperplane in n-dimensional space.

2. Compute the value of the gradient of the loss function for this model at the point described by these parameters.

3. Change the model parameters in the direction of greatest gradient decrease by a certain small magnitude, typically referred to as the α or learning rate.

4. Iterate: repeat steps 2 and 3 until convergence or a satisfactory optimization result is attained.

Figure 2-3 illustrates the intermediate results of a gradient descent optimization process of a linear regression. At zero iterations, observe that the regression line, formed with the randomly chosen parameters, does not fit the dataset at all. As you can imagine, the value of the sum-of-squares cost function is quite large at this point. At three iterations, notice that the regression line has very quickly moved to a more sensible position. Between 5 and 20 iterations the regression line slowly adjusts itself to more optimal positions where the cost function is minimized. If performing any more iterations doesn’t decrease the cost function significantly, we can say that the optimization has converged, and we have the final learned parameters for the trained model.

Figure 2-3. Regression line after a progressive number of iterations of gradient descent optimization (0, 3, 5, and 20 iterations of gradient descent, shown at the upper left, upper right, lower left, and lower right, respectively)

Logistic Regression

Although we discussed logistic regression in some detail earlier, we go over its key properties here. Logistic regression takes as input numerical feature vectors and attempts to predict the log odds¹³ of each data point occurring; we can convert the log odds to probabilities by using the sigmoid function discussed earlier. In the log odds space, the decision boundary is linear, so increasing the value of a feature monotonically increases or decreases (depending on the sign of the coefficient) the score output by the model.

Logistic regression is one of the most popular algorithms in practice due to a number of properties: it can be trained very efficiently and in a distributed manner, it scales well to millions of features, it admits a concise description and fast scoring algorithm (a simple dot product), and it is explainable—each feature’s contribution to the final score can be computed.

However, there are a few important things to be aware of when considering logistic regression as a supervised learning technique:

• Logistic regression assumes linearity of features (independent variables) and log odds, requiring that features are linearly related to the log odds. If this assumption is broken the model will perform poorly.

• Features should have little to no multicollinearity;¹⁴ that is, independent variables should be truly independent from one another.

• Logistic regression typically requires a larger sample size compared to other machine learning algorithms like linear regression. Maximum likelihood estimates (used in logistic regression) are less powerful than ordinary least squares (used in linear regression), which results in requiring more training samples to achieve the same statistical learning power.¹⁵

Decision Trees

Decision trees are very versatile supervised learning models that have the important property of being easy to interpret. A decision tree is, as its name suggests, a binary tree data structure that is used to make a decision. Trees are a very intuitive way of displaying and analyzing data and are popularly used even outside of the machine learning field. With the ability to predict both categorical values (classification trees) and real values (regression trees) as well as being able to take in numerical and categorical data without any normalization or dummy variable creation,¹⁶ it’s not difficult to see why they are a popular choice for machine learning.

Let’s see how a typical (top-down) learning decision tree is constructed:

1. Starting at the root of the tree, the full dataset is split based on a binary condition into two child subsets. For example, if the condition is “age ≥ 18,” all data points for which this condition is true go to the left child and all data points for which this condition is false go to the right child.

2. The child subsets are further recursively partitioned into smaller subsets based on other conditions. Splitting conditions are automatically selected at each step based on what condition best splits the set of items. There are a few common metrics by which the quality of a split is measured:

   Gini impurity

   If samples in a subset were randomly labeled according to the distribution of labels in the set, the proportion of samples incorrectly labeled would be the Gini impurity. For example, if a subset were made up of 25% samples with label 0 (and 75% with label 1), assigning label 0 to a random 25% of all samples (and label 1 to the rest) would give 37.5% incorrect labels: 75% of the label-0 samples and 25% of the label-1 samples would be incorrect. A higher-quality decision tree split would split the set into subsets cleanly separated by their label, hence resulting in a lower Gini impurity; that is, the rate of misclassification would be low if most points in a set belong to the same class.

   Variance reduction

   Often used in regression trees, where the dependent variable is continuous. Variance reduction is defined as the total reduction in a set’s variance as a result of the split into two subsets. The best split at a node in a decision tree would be the split that results in the greatest variance reduction.

   Information gain

   Information gain is a measure of the purity of the subsets resulting from a split. It is calculated by subtracting the weighted sum of each decision tree child node’s entropy from the parent node’s entropy. The smaller the entropy of the children, the greater the information gain, hence the better the split.

3. There are a few different methods for determining when to stop splitting nodes:

   • When all leaves of the tree are pure—that is, all leaf nodes each only contain samples belonging to the same class—stop splitting.

   • When a branch of the tree has reached a certain predefined maximum depth, the branch stops being split.

   • When either of the child nodes will contain fewer than the minimum number of samples, the node will not be partitioned.

4. Ultimately the algorithm outputs a tree structure where each node represents a binary decision, the children of each node represent the two possible outcomes of that decision, and each leaf represents the classification of data points following the path from the root to that leaf. (For impure leaves, the decision is determined by majority vote of the training data samples at that leaf.)

An important quality of decision trees is the relative ease of explaining classification or regression results, since every prediction can be expressed in a series of Boolean conditions that trace a path from the root of the tree to a leaf node. For example, if a decision tree model predicted that a malware sample belongs to malware family A, we know it is because the binary was signed before 2015, does not hook into the window manager framework, does make multiple network calls out to Russian IP addresses, etc. Because each sample traverses at most the height of the binary tree (time complexity $O\left(\log n\right)$), decision trees are also efficient to train and make predictions on. As a result, they perform favorably for large datasets.

Nevertheless, decision trees have some limitations:

• Decision trees often suffer from the problem of overfitting, wherein trees are overly complex and don’t generalize well beyond the training set. Pruning is introduced as a regularization method to reduce the complexity of trees.

• Decision trees are more inefficient at expressing some kinds of relationships than others. For example, Figures 2-5 and 2-6 present the minimal decision tree required to represent the AND, OR, and XOR relationships. Notice how XOR requires one more intermediate node and split to be appropriately represented, even in this simple example. For realistic datasets, this can quickly result in exploding model complexity.

  

  Figure 2-5. Decision tree for A-AND-B → y=1 (left), A-OR-B → y=1 (right)

  

  Figure 2-6. Decision tree for A-XOR-B → y=1 (bottom)

• Decision trees tend to be less accurate and robust than other supervised learning techniques. Small changes to the training dataset can result in large changes to the tree, which in turn result in changes to model predictions. This means that decision trees (and most other related models) are unsuitable for use in online learning or incremental learning.

• Split-quality metrics for categorical variables in decision trees are biased toward variables with more possible values; that is, splits on continuous variables or categorical variables with three or more categories will be chosen with a greater probability than binary variables.

• Greedy training of decision trees (as it is almost always done) does not guarantee an optimal decision tree because locally optimal and not globally optimal decisions are made at each split point. In fact, the training of a globally optimal decision tree is an NP-complete problem.¹⁷

Decision Forests

An ensemble refers to a combination of multiple classifiers that creates a more complex, and often better performing, classifier. Combining decision trees into ensembles is a proved technique for creating high-quality classifiers. These ensembles are aptly named decision forests. The two most common types of forests used in practice are decision forests and gradient-boosted decision trees:

• Random forests are formed by simple ensembling of multiple decision trees, typically ranging from tens to thousands of trees. After training each individual decision tree, overall random forest predictions are made by taking the statistical mode of individual tree predictions for classification trees (i.e., each tree “votes”), and the statistical mean of individual tree predictions for regression trees.

  You might notice that simply having many decision trees in the forest will result in highly similar trees and a lot of repeated splits across different trees, especially for features that are strong predictors of the dependent variable. The random forest algorithm addresses this issue using the following training algorithm:

  1. For the training of each individual tree, randomly draw a subset of N samples from the training dataset.

  2. At each split point, we randomly select m features from the p available features, where $m\le p$,¹⁸ and pick the optimal split point from these m features.¹⁹

  3. Repeat step 2 until the individual tree is trained.

  4. Repeat steps 1, 2, and 3 until all trees in the forest are trained.

  Single decision trees tend to overfit to their training sets, and random forests mitigate this effect by taking the average of multiple decision trees, which usually improves model performance. In addition, because each tree in the random forest can be trained independently of all other trees, it is straightforward to parallelize the training algorithm and therefore random forests are very efficient to train. However, the increased complexity of random forests can make them much more storage intensive, and it is much harder to explain predictions than with single decision trees.

• Gradient-boosted decision trees (GBDTs) make use of smarter combinations of individual decision tree predictions to result in better overall predictions. In gradient boosting, multiple weak learners are selectively combined by performing gradient descent optimization on the loss function to result in a much stronger learning model.

  The basic technique of gradient boosting is to add individual trees to the forest one at a time, using a gradient descent procedure to minimize the loss when adding trees. Addition of more trees to the forest stops either when a fixed limit is hit, when validation set loss reaches an acceptable level, or when adding more trees no longer improves this loss.

  Several improvements to basic GBDTs have been made to result in better performing, better generalizing, and more efficient models. Let’s look at a handful of them:

  1. Gradient boosting requires weak learners. Placing artificial constraints on trees, such as limits on tree depth, number of nodes per tree, or minimum number of samples per node, can help constrain these trees without overly diminishing their learning ability.

  2. It can happen that the decision trees added early on in the additive training of gradient-boosted ensembles contribute much more to the overall prediction than the trees added later in the process. This situation results in an imbalanced model that limits the benefits of ensembling. To solve this problem, the contribution of each tree is weighted to slow down the learning process, using a technique called shrinkage, to reduce the influence of individual trees and allow future trees to further improve the model.

  3. We can combine the stochasticity of random forests with gradient boosting by subsampling the dataset before creating a tree and subsampling the features before creating a split.

  4. We can use standard and popular regularization techniques such as $L_1$ and $L_2$ regularization to smooth final learned weights to further avoid overfitting.

  XGBoost²⁰ is a popular GBDT flavor that achieves state-of-the-art results while scaling well to large datasets. As the algorithm that was responsible for many winning submissions to machine learning competitions, it garnered the attention of the machine learning community and has become the decision forest algorithm of choice for many practitioners. Nevertheless, GBDTs are more prone to overfitting than random forests, and also more difficult to parallelize because they use additive training, which relies on the results of a given tree to update gradients for the subsequent tree. We can mitigate overfitting of GBDTs by using shrinkage, and we can parallelize training within a single tree instead of across multiple trees.

Support Vector Machines

Like logistic regression, a support vector machine (SVM) is (in its simplest form) a linear classifier, which means that it produces a hyperplane in a vector space that attempts to separate the two classes in the dataset. The difference between logistic regression and SVMs is the loss function. Logistic regression uses a log-likelihood function that penalizes all points proportionally to the error in the probability estimate, even those on the correct side of the hyperplane. An SVM, on the other hand, uses a hinge loss, which penalizes only those points on the wrong side of the hyperplane or very near it on the correct side.

More specifically, the SVM classifier attempts to find the maximum-margin hyperplane separating the two classes, where “margin” indicates the distance from the separating plane to the closest data points on each side. For the case in which the data is not linearly separable, points within the margin are penalized proportionately to their distance from the margin. Figure 2-7 shows a concrete example: the two classes are represented by white and black points, respectively. The solid line is the separating plane and the dashed lines are the margins. The square points are the support vectors; that is, those that provide nonzero contribution to the loss function. This loss function is expressed mathematically as:

where $\beta$ is the margin, ${\xi }_i$ is the distance from the ith support vector to the margin, and C is a model hyperparameter that determines the relative contribution of the two terms.

Figure 2-7. Classification boundary (dark line) and margins (dashed lines) for linear SVM separating two classes (black and white points); squares represent support vectors

To classify a new data point x, we simply determine which side of the plane x falls on. If we want to get a real-valued score we can compute the distance from x to the separating plane and then apply a sigmoid to map to [0,1].

The real power of SVMs comes from the kernel trick, which is a mathematical transformation that takes a linear decision boundary and produces a nonlinear boundary. At a high level, a kernel transforms one vector space, $V_1$, to another space, $V_2$. Mathematically, the kernel is a function on $V_1\times V_1$ defined by $K(x,y)$, and each $x\in V_1$ is mapped to the function $K(x,·)$; $V_2$ is the space spanned by all such functions. For example, we can recover the linear SVM by defining K to be the usual dot product $K(x,y)=x·y$.

If the kernel is nonlinear, a linear classifier in $V_1$ will produce a nonlinear classifier in $V_2$. The most popular choice is the radial basis function $K(x,y)=e^{-\gamma |x-y|}$. Even though we omit the mathematical details here,²¹ you can think of an SVM with the RBF kernel as producing a sort of smoothed linear combination of spheres around each point x, where the inside of each sphere is classified the same as x, and the outside is assigned the opposite class. The parameter $\gamma$ determines the radius of these spheres; i.e., how close to each point you need to be in order to be classified like that point. The parameter C determines the “smoothing”; a large value of C will lead to the classifier consisting of a union of spheres, while a small value will yield a wigglier boundary influenced somewhat by each sphere. We can therefore see that too large a value of C will produce a model that overfits the training data, whereas too small a value will give a poor classifier in terms of accuracy. (Note that $\gamma$ is unique to the RBF kernel, whereas C exhibits the same properties for any kernel, including the linear SVM. Optimal values of these parameters are usually found using grid search.)

SVMs have shown very good performance in practice, especially in high-dimensional spaces, and the fact that they can be described in terms of support vectors leads to efficient implementations for scoring new data points. However, the complexity of training a kernelized SVM grows quadratically with the number of training samples, so that for training set sizes beyond a few million, kernels are rarely used and the decision boundary is linear. Another disadvantage is that the scores output by SVMs are not interpretable as probabilities; converting scores to probabilities requires additional computation and cross-validation, for example using Platt scaling or isotonic regression. The scikit-learn documentation has further details.

Naive Bayes

The Naive Bayes classifier is one of the oldest statistical classifiers. The classifier is called “naive” because it makes a very strong statistical assumption, namely that features are chosen independently from some (unknown) distribution. This assumption never actually holds in real life. For example, consider a spam classifier for which the features are the words in the message. The Naive Bayes assumption posits that a spam message is composed by sampling words independently, where each word w has a probability $p_{w,spam}$ of being sampled, and similarly for good messages. This assumption is clearly ludicrous; for one thing, it completely ignores word ordering. Yet despite the fact that the assumption doesn’t hold, Naive Bayes classifiers have been shown to be quite effective for problems such as spam classification.

The main idea behind Naive Bayes is as follows: given a data point with feature set $X=x_1,...,x_n$, we want to determine the probability that the label Y for this point is the class C. In Equation 2-1, this concept is expressed as a conditional probability.

Now using Bayes’ Theorem, this probability can be reexpressed as in Equation 2-2.

If we make the very strong assumption that for samples in each class the features are chosen independently of one another, we get Equation 2-3.

we can estimate the numerator of Equation 2-2 from labeled data: $Pr[X_i=x_i\mid Y=C]$ is simply the fraction of samples with the ith feature equal to $x_i$ out of all the samples in class C, whereas $Pr[Y=C]$ is the fraction of samples in class C out of all the labeled samples.

What about the denominator of Equation 2-2? It turns out that we don’t need to compute this, because in two-class classification it is sufficient to compute the ratio of the probability estimates for the two classes $C_1$ and $C_2$. This ratio (Equation 2-4) gives a positive real number score.

A score of $\theta$ > 1 indicates that $C_1$ is the more likely class, whereas $\theta$ < 1 indicates that $C_2$ is more likely. (If optimizing for one of precision or recall you might want to choose a different threshold for the classification boundary.)

The astute observer will notice that we obtained our score $\theta$ without reference to a loss function or an optimization algorithm. The optimization algorithm is actually hidden in the estimate of $Pr[X_i=x_i\mid Y=C]$; using the fraction of samples observed in the training data gives the maximum likelihood estimate, the same loss function used for logistic regression. The similarity to logistic regression doesn’t stop there: if we take logarithms of Equation 2-4 the righthand side becomes a linear function of the features, so we can view Naive Bayes as a linear classifier, as well.

A few subtleties arise when trying to use Naive Bayes in practice:

• What happens when all of the examples of some feature are in the same class (e.g. brand names of common sex enhancement drugs appear only in spam messages)? Then, one of the terms of Equation 2-4 will be zero, leading to a zero or infinity estimate for $\theta$, which doesn’t make sense. To get around this problem we use smoothing, which means adding “phantom” samples to the labeled data for each feature. For example, if we are smoothing by a factor of $\alpha$, we would calculate the value for a feature as follows:

  $$Pr[X_i=x_i\mid Y=C]=\frac{\left(\text{\# samples in class}C\text{with feature}{x}_i\right)+\alpha }{\left(\text{\# samples in class}C\right)+\alpha ·\left(\text{\# of features}\right)}$$

  The choice $\alpha$ = 1 is called Laplace smoothing, whereas $\alpha$ < 1 is called Lidstone smoothing.

• What happens if a feature $x_i$ appears in our validation set (or worse, in real-life scoring) that did not appear in the training set? In this case we have no estimate for $Pr[X_i=x_i\mid Y=C]$ at all. A naive estimate would be to set the probability to $Pr[Y=C]$; for more sophisticated approaches see the work of Freeman.²²

As a final note, we can map the score $\theta \in (0,\infty )$ to a probability in (0,1) using the mapping $\theta \to \frac{\theta }{1+\theta }$; however, this probability estimate will not be properly calibrated. As with SVMs, to obtain better probability estimates we recommend techniques such as Platt scaling or isotonic regression.

k-Nearest Neighbors

The k-nearest neighbors (k-NN) algorithm is the most well-known example of a lazy learning algorithm. This type of machine learning technique puts off most computations to classification time instead of doing the work at training time. Lazy learning models don’t learn generalizations of the data during the training phase. Instead, they record all of the training data points they are passed and use this information to make the local generalizations around the test sample during classification. k-NN is one of the simplest machine learning algorithms:

• The training phase simply consists of storing all the feature vectors and corresponding sample labels in the model.

• The classification prediction²³ is simply the most common label out of the test sample’s k nearest neighbors (hence the name).

The distance metrics for determining how “near” points are to each other in an n-dimensional feature space (where n is the size of the feature vectors) are typically the Euclidean distance for continuous variables and the Hamming distance for discrete variables.

As you might imagine, with such a simple algorithm the training phase of k-NN is typically very fast compared to other learning algorithms, at the cost of classification processing time. Also, the fact that all feature vectors and labels need to be stored within the model results in a very space-inefficient model. (A k-NN model that takes in 1 GB of training feature vectors will at least be 1 GB in size.)

The simplicity of k-NN makes it a popular example for teaching the concept of machine learning to novices, but it is rarely seen in practical scenarios because of the serious drawbacks it has. These include:

• Large model sizes, because models must store (at least) all training data feature vectors and labels.

• Slow classification speeds, because all generalization work is pushed off until classification time. Searching for the nearest neighbors can be time consuming, especially if the model stores training data points in a manner that is not optimized for spatial search. k-d trees (explained in “k-d trees”) are often used as an optimized data structure to speed up neighbor searches.²⁴

• High sensitivity to class imbalance²⁵ in the dataset. Classifications will be skewed towards the classes with more samples in the training data since there is a greater likelihood that samples of these classes will make it into the k-NN set of any given test sample.

• Diminished classification accuracy due to noisy, redundant, or unscaled features. (Choosing a larger k reduces the effect of noise in the training data, but also can result in a weaker learner.)

• Difficulty in choosing the parameter k. Classification results are highly dependent on this parameter, and it can be difficult to choose a k that works well across all parts of the feature space because of differing densities within the dataset.

• Breaks down in high dimensions due to the “curse of dimensionality.” In addition, with more dimensions in the feature space, the “neighborhood” of any arbitrary point becomes larger, which results in noisier neighbor selection.

Neural Networks

Artificial neural networks (ANNs) are a class of machine learning techniques that have seen a resurgence in popularity recently. One can trace the origins of neural networks all the way back to 1942, when McCulloch and Pitts published a groundbreaking paper postulating how neurons in the human nervous system might work.²⁶ Between then and the 1970s, neural network research advanced at a slow pace, in large part due to von Neumann computing architectures (which are quite in opposition to the idea of ANNs) being in vogue. Even after interest in the field was renewed in the 1980s, research was still slow because the computational requirements of training these networks meant that researchers often had to wait days or weeks for the results of their experiments. What triggered the recent popularity of neural networks was a combination of hardware advancements—namely graphics processing units (GPUs) for “almost magically” parallelizing and speeding up ANN training—and the availability of the huge amounts of data that ANNs need to get good at complex tasks like image and speech recognition.

The human brain is composed of a humongous number of neurons (on the order of 10 billion), each with connections to tens of thousands of other neurons. Each neuron receives electrochemical inputs from other neurons, and if the sum of these electrical inputs exceeds a certain level, the neuron then triggers an output transmission of another electrochemical signal to its attached neurons. If the input does not exceed this level, the neuron does not trigger any output. Each neuron is a very simple processing unit capable of only very limited functionality, but in combination with a large number of other neurons connected in various patterns and layers, the brain is capable of performing extremely complex tasks ranging from telling apart a cat from a dog to grasping profound philosophical concepts.

ANNs were originally attempts at modeling neurons in the brain to achieve human-like learning. Individual neurons were modeled with simple mathematical step functions (called activation functions), taking in weighted input from some neurons and emitting output to some other neurons if triggered. This mathematical model of a biological neuron is also called a perceptron. Armed with perceptrons, we then can form a plethora of different neural networks by varying the topology, activation functions, learning objectives, or training methods of the model.

Typically, ANNs are made up of neurons arranged in layers. Each neuron in a layer receives input from the previous layer and, if activated, emits output to one or more neurons in the next layer. Each connection of two neurons is associated with a weight, and each neuron or layer might also have an associated bias. These are the parameters to be trained by the process of backpropagation, which we describe simply and briefly. Before starting, all of the weights and biases are randomly initialized. For each sample in the training set, we perform two steps:²⁷

1. Forward pass. Feed the input through the ANN and get the current prediction.

2. Backward pass. If the prediction is correct, reward the connections that produced this result by increasing their weights in proportion to the confidence of the prediction. If the prediction is wrong, penalize the connections that contributed to this wrong result.

Neural networks have been extensively used in industry for many years and are backed by large bodies of academic research. There are hundreds of variations of neural network infrastructures, and we can use them for both supervised and unsupervised learning. An important quality of some ANNs is that they can perform unsupervised feature learning (which is different from unsupervised learning), which means that minimal or no feature engineering is required. For example, building a malware classifier with an SVM requires domain experts to generate features (as we discuss in Chapter 4). If we use ANNs, it is possible to feed the raw processor instructions or call graphs into the network and have the network itself figure out which features are relevant for the classification task.

Even though there are a lot of hardware and software optimizations available for the training of neural networks, they are still significantly more computationally expensive than training a decision tree, for instance. (Predictions, on the other hand, can be made rather efficiently because of the layered structure.) The number of model hyperparameters to tune in the training of ANNs can be enormous. For instance, you must choose the configuration of network architecture, the type of activation function, whether to fully connect neurons or leave layers sparsely connected, and so on. Lastly, although ANNs—or deep learning networks, as the deep (many-layered) variants of neural networks are popularly called—are frequently thought to be a silver bullet in machine learning, they can be very complex and difficult to reason about. There are often alternatives (such as the other algorithms that we discussed in this section) that are faster, simpler, and easier to train, understand, and explain.

Selecting a Model Family

In the previous section, we discussed a number of different supervised classification algorithms. How are you supposed to decide which one to pick for a given task? The best answer is to let the data decide: try a number of different approaches and see what works best. If you don’t have the time or infrastructure to do this, here are some factors to consider:

Computational complexity

You want to be able to train your model in a reasonable amount of time, using all of the data you have. Logistic regression models and linear SVMs can be trained very quickly. In addition, logistic regression and decision forests have very efficient parallel implementations that can handle very large amounts of data. Kernel SVMs and neural networks can take a long time to train.

Mathematical complexity

Your data might be such that a linear decision boundary will provide good classification; on the other hand, many datasets have nonlinear boundaries. Logistic regression, linear SVM, and Naive Bayes are all linear algorithms; for nonlinear boundaries you can use decision forests, kernel SVMs, or neural networks.

Explainability

A human might need to read the output of your model and determine why it made the decision it did; for example, if you block a legitimate user, you should educate them as to what they did that was suspicious. The best model family for explainability is a decision tree, because it says exactly why the classification was made. We can use relative feature weights to explain logistic regression and Naive Bayes. Decision forests, SVMs, and neural networks are very difficult to explain.

There are many opinions on what model to use in which situation; an internet search for “machine learning cheat sheet” will produce dozens. Our basic recommendation is to use decision forests for high accuracy on a moderate number of features (up to thousands), and logistic regression for fast training on a very large number of features (tens of thousands or more). But ultimately, you should experiment to find the best choice for your data.

Training Data Construction

In a supervised learning problem, you will (somehow) have assembled labeled examples of the thing that you want to classify—account registrations, user logins, email messages, or whatever. Because your goal is to come up with a model that can predict the future based on past data, you will need to reserve some of your labeled data to act as this “future” data so that you can evaluate your model. There are a number of different ways you can do this:

Cross-validation

This technique is a standard method for evaluating models when there is not a lot of training data, so every labeled example makes a significant contribution to the learned model. In this method, you divide the labeled data into k equal parts (usually 5 or 10) and train k different models: each model “holds out” a different one of the k parts and trains on the remaining k–1 parts. The held-out part is then used for validation. Finally, the k different models are combined by averaging both the performance statistics and the model parameters.

Train/validate/test

This approach is most common when you have enough training data so that removing up to half of it doesn’t affect your model very much. In this approach you randomly divide your labeled data into three parts. (See the left side of Figure 2-8.) The majority (say, 60%) is the training set and is input to the learning algorithm. The second part (say, 20%) is the validation set and is used to evaluate and iterate on the model output by the learning algorithm. For example, you can tune model parameters based on performance on the validation set. Finally, after you have settled on an optimal model, you use the remaining part (say, 20%) as the test set to estimate real-world performance on unseen data.

Out-of-time validation

This approach addresses the problem of validating models when the data distribution changes over time. In this case, sampling training and validation sets at random from the same labeled set is “cheating” in some sense—the distributions of the training and validation sets will match closely and not reflect the time aspect. A better approach is to split the training and validation sets based on a time cutoff: samples before time t are in the training set and samples after time t are in the validation set. (See the right side of Figure 2-8.) You might want to have the test set come from the same time period as the validation set, or a subsequent period entirely.

Figure 2-8. In-time validation (left) and out-of-time validation (right)

The composition of the training set might also require some attention. Let’s take a look at a few common issues.

Feature Selection

If you have a reasonably efficient machine learning infrastructure, most of your time and energy will be spent on feature engineering—figuring out signals that you can use to identify attacks, and then building them into your training and scoring pipeline. To make best use of your effort, you want to use only features that provide high discriminatory power; the addition of each feature should noticeably improve your model.

In addition to requiring extra effort to build and maintain, redundant features can hurt the quality of your model. If the number of features is greater than the number of data points, your model will be overfit: there are enough model parameters to draw a curve through all the training data. In addition, highly correlated features can lead to instability in model decisions. For example, if you have a feature that is “number of logins yesterday” and one that is “number of logins in the last two days,” the information you are trying to collect will be split between the two features essentially arbitrarily, and the model might not learn that either of these features is important.

You can solve the feature correlation problem by computing covariance matrices between your features and combining highly correlated features (or projecting them into orthogonal spaces; in the previous example, “number of logins in the day before yesterday” would be a better choice than “number of logins in the last two days”).

There are number of techniques to address the feature selection problem:

• Logistic regression, SVMs, and decision trees/forests have methods of determining relative feature importance; you can run these and keep only the features with highest importance.

• You can use $L_1$ regularization (see the next section) for feature selection in logistic regression and SVM classifiers.

• If the number n of features is reasonably small (say, n < 100) you can use a “build it up” approach: build n one-feature models and determine which is best on your validation set; then build n–1 two-feature models, and so on, until the gain of adding an additional feature is below a certain threshold.

• Similarly, you can use a “leave one out” approach: build a model on n features, then n models on n–1 features and keep the best, and so on until the loss of removing an additional feature is too great.

scikit-learn implements the sklearn.feature_selection.SelectFromModel helper utility that assists operators in selecting features based on importance weights. As long as a trained estimator has the feature_importances_ or coef_ attribute after fitting,²⁸ it can be passed into SelectFromModel for feature selection importance ranking. Assuming that we have a pretrained DecisionTreeClassifier model (variable name clf) and an original training dataset (variable name train_x) with 119 features, here is a short code snippet showing how to use SelectFromModel to keep only features with a feature_importance that lies above the mean:^29,30

from sklearn.feature_selection import SelectFromModel

sfm = SelectFromModel(clf, prefit=True)

# Generate new training set, keeping only the selected features
train_x_new = sfm.transform(train_x)

print("Original num features: {}, selected num features: {}"
      .format(train_x.shape[1], train_x_new.shape[1]))

> Original num features: 119, selected num features: 7

Choosing Thresholds and Comparing Models

The supervised classification algorithm you choose will typically output a real-valued score, and you will need to choose a threshold or thresholds³¹ above which to block the activity or show additional friction (e.g., require a phone number). How do you choose this threshold? This choice is ultimately a business decision, based on the trade-off between security and user friction. Ideally you can come up with some cost function—for example, 1 false positive is equal to 10 false negatives—and minimize the total cost on a representative sample of the data. Another option is to fix a precision or recall target—for example, 98%—and choose a threshold that achieves that target.

Now suppose that you have two versions of your model with different parameters (e.g., different regularization) or even different model families (e.g., logistic regression versus random forest). Which one is better? If you have a cost function this is easy: compute the cost of the two versions on the same dataset and choose the lower-cost option. If fixing a precision target, choose the version that optimizes recall, and vice versa.

Another common method for model comparison is to plot the receiver operating characteristic (ROC) curve and compute the area under the curve (AUC). The ROC curve plots false positive rate (FP / (FP + TN)) on the x-axis and true positive rate (TP / (TP + FN), also known as recall) on the y-axis. Each point on the curve corresponds to a score threshold and represents the (FPR, TPR) pair at that threshold. The AUC can be interpreted as the probability that a randomly chosen positive example has a higher score than a randomly chosen negative example; under this interpretation it’s easy to see that the worst case is AUC 0.5, which is equivalent to a random ordering of samples.³²

Figure 2-10 shows an example ROC curve, with the line y = x plotted for comparison. Because the AUC is very high, we have used a log scale to zoom in on the lefthand side, which is where differences between high-performance models will appear; if you are operating only in the high-precision region of the curve, you may want to calculate up to a threshold false positive rate, such as 1%.

One nice property of AUC is that it is unaffected by sampling bias. Thus, if you sample two classes with different weights, the AUC you get on the resulting dataset will be representative of the AUC on the unsampled dataset.

Figure 2-10. ROC curves

One common metric that is limited in real-world usefulness is the F-score, which is defined as follows:

The F-score combines precision and recall and harshly penalizes extremes; however, it requires choosing a threshold and a relative weighting of precision and recall (parametrized by $\alpha$).

Clustering Algorithms

The geometric intuition behind clustering is straightforward: you want to group together data points that are “close together” in some sense. Thus, for any algorithm to work you need to have some concrete way to measure “closeness”; such a measurement is called a metric. The metric and clustering algorithm you use will depend on the form your data is in; for example, your data might consist of real-valued vectors, lists of items, or sequences of bits. We now consider the most popular algorithms.

k-means

k-means is usually the first algorithm that comes to mind when you think of clustering. k-means applies to real-valued vectors, when you know how many clusters you expect; the number of clusters is denoted by k. The goal of the algorithm is to assign each data point to a cluster such that the sum of the distances from each point to its cluster centroid is minimized. Here the notion of distance is the usual Euclidean distance in a vector space:

$$d(x,y)=\sqrt{{\sum }_i{(x_i-y_i)}^2}$$

In mathematical terms, the k-means algorithm computes a cluster assignment f: X → {1,…k} that minimizes the loss function:

$$L(X)=\sum _{i}d(x_i,c_{f(x_i)})$$

where $X=\{x_1,...,x_n\}$ is your dataset, $c_j$ is the jth centroid, and d is the distance between two points. The value $L\left(X\right)$ is called “inertia.”

The standard algorithm for computing k-means clusters is as follows:

1. Choose k centroids $c_1,...,c_k$ at random.

2. Assign each data point $x_i$ to its nearest centroid.

3. Recompute the centroids $c_j$ by taking the average of all the data points assigned to the jth cluster.

4. Repeat (2) and (3) until the algorithm converges; that is, the difference between $L\left(X\right)$ on successive iterations is below a predetermined threshold.

k-means is a simple and effective clustering algorithm that scales well to very large datasets. However, there are some things for which you need to be on the lookout:

• Since k is a fixed parameter of the algorithm, you must choose it appropriately. If you know how many clusters you are looking for (e.g., if you are trying to cluster different families of malware), you can simply choose k to be that number. Otherwise, you will need to experiment with different values of k. It is also common to choose values of k that are between one to three times the number of classes (labels) in your data, in case some categories are discontinuous. Warning: loss functions computed using different values of k are not comparable to each other!

• You must normalize your data before using k-means. A typical normalization is to map the jth coordinate x_ij to (x_ij-µ_j)/σ_j, where µ_j is the mean of the jth coordinates, and σ_j is the standard deviation.

  To see why normalization is necessary, consider a two-dimensional dataset whose first coordinate ranges between 0 and 1, and whose second coordinate ranges between 0 and 100. Clearly the second coordinate will have a much greater impact on the loss function, so you will lose information about how close together points are in the first coordinate.

• Do not use k-means with categorical features, even if you can represent them as a number. For example, you could encode “red,” “green,” and “blue” as 0, 1, and 2, respectively, but these numbers don’t make sense in a vector space—there is no reason that blue should be twice as far from red as green is. This problem can be addressed by one-hot encoding the categorical features as multiple binary features (as discussed in the worked example earlier in this chapter), but…

• Beware when using k-means with binary features. k-means can sometimes be used with binary features, encoding the two responses as 0 and 1, or −1 and 1, but results here can be unpredictable; the binary feature might become the dominant feature determining the cluster, or its information might be lost entirely.

• k-means loses effectiveness in high dimensions, due to the “curse of dimensionality”—all points are roughly equally distant from each other. For best results use k-means in low dimensions or after applying a dimensionality reduction algorithm such as principal component analysis (PCA). Another option is to use the L-infinity distance, where the distance between two points is taken to be the maximum of the difference of any coordinate:

  $$d(x,y)=ma{x}_i\left(|x_i-y_i|\right)$$

• k-means works best when the initial centroids are chosen at random; however, this choice can make reproducing results difficult. Try different choices of initial centroids to see how the results depend on the initialization.

• k-means assumes that the clusters are spherical (globular) in nature. As you can imagine, it does not work well on non-spherical distributions, such as the one illustrated in Figure 2-11.

Figure 2-11. Nonspherical data distribution

Hierarchical clustering

Unlike the k-means algorithm, hierarchical clustering methods are not parametrized by an operator-selected value k (the number of clusters you want to create). Choosing an appropriate k is a nontrivial task, and can significantly affect clustering results. Agglomerative (bottom-up) hierarchical clustering builds clusters as follows (illustrated in Figure 2-12):

1. Assign each data point to its own cluster (Figure 2-12, bottom layer).

2. Merge the two clusters that are the most similar, where “most similar” is determined by a distance metric such as the Euclidean distance or Mahalanobis distance.

3. Repeat step 2 until there is only one cluster remaining (Figure 2-12, top layer).

4. Navigate the layers of this tree (dendrogram) and select the layer that gives you the most appropriate clustering result.

Divisive (top-down) hierarchical clustering is another form of hierarchical clustering that works in the opposite direction. Instead of starting with as many clusters as there are data points, we begin with a single cluster consisting of all data points and start dividing clusters based on the distance metric, stopping when each data point is in its own separate cluster.

Figure 2-12. Agglomerative hierarchical clustering dendrogram

There are some important points to take note of when considering whether to use hierarchical clustering:

• Hierarchical clustering produces a dendrogram tree model, as illustrated in Figure 2-12. This model can be more complex to analyze and takes up more storage space than the centroids produced by k-means, but also conveys more information about the underlying structure of the data. If model compactness or ease of analysis is a priority, hierarchical clustering might not be your best option.

• k-means works with only a small selection of distance metrics (mostly Euclidean distance) and requires numerical data to work. In contrast, hierarchical clustering works with almost any kind of distance metric or similarity function, as long as it produces a result that can be numerically compared (e.g., C is more similar to A than to B). You can use it with categorical data, mixed type data, strings, images, and so on as long as an appropriate distance function is provided.

• Hierarchical clustering has high time complexity, which makes it unsuitable for large datasets. Taking n to be the number of data points, agglomerative hierarchical clustering has a time complexity of $O(n^{2}log(n))$, and naive divisive clustering has a time complexity of $O(2^n)$.

Evaluating Clustering Results

It can sometimes be difficult to make sense of the results of clustering operations. Evaluating supervised learning algorithms is a much more straightforward task because we have access to the ground truth labels: we can simply count the number of samples to which the algorithm correctly and wrongly assigns labels. In the case of unsupervised learning, it is unlikely we have access to labels, though if we do evaluation becomes much easier.^37,38 For example, commonly used metrics for evaluating clustering results if the ground truth labels are known are:

Homogeneity

The degree to which each cluster contains only members of a single class.

Completeness

The degree to which all members of a certain class are assigned to the same cluster.

The harmonic mean of these two metrics is known as the V-measure,³⁹ an entropy-based score representing the clustering operation’s accuracy, which has the formula:

where h is homogeneity and c is completeness.

We will use the scikit-learn implementations of these clustering evaluation metrics in Chapter 5.

On the other hand, the fact that we are considering clustering at all means it is likely that we do not have any ground truth labels for our dataset. Instead, we can no longer use the V-measure because both homogeneity and completeness can be measured only by comparing prediction labels to ground truth labels. In this case, we have to rely on signals derived directly from the trained model itself. Essentially, we consider the clustering operation to be successful if samples assigned to the same cluster are all similar to one another, and samples assigned to different clusters are all completely dissimilar from one another. There are two popular ways to measure this:

Silhouette coefficient

This score is calculated separately for each sample in the dataset. Using some distance metric (e.g., Euclidean distance), we find the following two mean distances for some sample x:

• a: the mean distance between sample x and all other samples in the same cluster

• b: the mean distance between sample x and all other samples in the next nearest cluster

The Silhouette coefficient s is then defined as follows:⁴⁰

$$s=\frac{b-a}{max(a,b)}$$

For a clustering result that is hugely incorrect, the a will be much larger than b, resulting in the numerator being negative. Because the denominator will never be negative (distance metrics do not take on negative values), s will itself be negative. In fact, s is bounded between −1 and +1. The closer s is to +1, the better the clustering result. When s is very close to 0, we have highly overlapping clusters. Nevertheless, it is found that the Silhouette coefficient is biased toward distance-based (e.g., k-means), grid-based (e.g., STING⁴¹), and hierarchical clustering algorithms that produce convex clusters. It does not work well for clusters produced by density-based algorithms such as DBSCAN and OPTICS, because neither a nor b take cluster density into consideration. Also, because the Silhouette coefficient must be independently calculated for each sample in the dataset, it can be quite slow.

Calinski-Harabaz index

The Calinski-Harabaz (C-H) index⁴² is higher (better) when clusters are dense and well separated. By most measures, this measure of clustering effectiveness is closer to how humans evaluate clustering results. We consider a clustering result to be good if there are visibly separated and densely gathered groups of samples. The C-H index uses two measures:

• $W_k$: the within-cluster dispersion, a matrix of distances between samples in a cluster and the geometric center of the cluster

• $B_k$: the between-group dispersion, a matrix of distances between the center of a cluster and the centers of all other clusters

(Here, k is the number of clusters in the model.)

The C-H score (s) takes the ratio of $W_k$ and $B_k$ (where N is the number of samples in the dataset and tr is the trace of the matrix⁴³):

$$s=\frac{\mathrm{tr}\left(B_k\right)}{\mathrm{tr}\left(W_k\right)}\times \frac{N-k}{k-1}$$

The C-H score can be computed much more efficiently than the Silhouette index. Even though it is still biased against density-based clusters, it is comparatively more reliable than the Silhouette index.

No matter which method you choose, there will be some inherent limitations in evaluating clustering results without any human labeling. If you suspect that clustering models are not performing well in practice in spite of good evaluation metrics, it may be necessary to invest resources in manually labeling a subset of samples and use semi-supervised approaches to evaluate the model.