Hands On Machine Learning Chapter 4 - Training Models

Having a good understanding of how things [machine learning models] work can help you quickly home in on the appropriate model, the right training algorithm to use, and a good set of hyperparameters for your task. Understanding what's under the hood will also help you debug issues and perform error analysis more efficiently. Lastly, most of the topics discussed in this chapter will be essential in understanding, building, and training neural networks.

We will start this chapter by looking at the Linear Regression model, one of the simplest models there is. There are two very different ways to train it:

1. Using a direct "closed-form" equation that directly computes the model parameters that best fit the model to the training set (i.e., the model parameters that minimize the cost function over the training set).
2. Using an iterative approach, called Gradient Descent (GD), that gradually tweaks the model parameters to minimize the cost function over the training set, eventually converging to the same set of parameters as the first method.

Next, we will look at Polynomial Regression, a more complex model that can fit non-linear datasets. Since this model has more parameters, it is more prone to overfitting, so we will look at how to prevent this. Finally, we will look at two more models that are commonly used for classification tasks: Logistic Regression and Softmax Regression.

A linear model makes a prediction by simply computing a weighted sum of the input features, plus a constant called the bias term (also called the intercept term):

This equation can be written more concisely in the vectorized form:

Training a model means setting its parameters so that the model best fits the training set. For this purpose, we need a measure of how well (or poorly) the model fits the training data. A common performance measure of a regression model is the Root Mean Square Error (RMSE). Therefore, to train a Linear Regression model, you need to find the value of $\mathit{\theta }\backslash bm\{\backslash theta\}$θ that minimizes the RMSE. (Minimizing the MSE is simpler and the same thing in practice).

The Normal Equation

To find a value of $\mathit{\theta }\backslash bm\{\backslash theta\}$θ that minimizes the cost function, there is a closed-form solution - in other words, a mathematical equation that gives the result directly. This is called the Normal Equation:

Below, there is code that shows computing the best parameter vector using numpy, the LinearRegression class of Scikit-Learn, and scipy. The scipy and Scikit-Learn implementations of the Normal Equation calculate the pseudoinverse of $\mathbf{\text{X}}\backslash textbf\{X\}$X (specifically, the Moore-Penrose inverse). The pseudo inverse itself is computed using a standard matrix factorization technique called Singular Value Decomposition (SVD) that can decompose the training set matrix $\mathbf{\text{X}}\backslash textbf\{X\}$X into the matrix multiplication of three matrices $\mathbf{\text{U}}\mathbf{\Sigma }{\mathbf{\text{V}}}^T\backslash textbf\{U\}\; \backslash bm\{\backslash Sigma\}\; \backslash textbf\{V\}^T$UΣVT. This equation handles edge cases nicely: the Normal Equation may not work if the matrix ${\mathbf{\text{X}}}^T\mathbf{\text{X}}\backslash textbf\{X\}^T\backslash textbf\{X\}$XTX is not invertible, but the pseudoinverse is always defined.

Computational Complexity

The computational complexity of inverting a matrix is typically about $O(n^{2.4})O(n^\{2.4\})$O(n2.4) to $O(n^3)O(n^3)$O(n3) (where $nn$n is the number of features).In other words, if you double the number of features, you multiply the computation time by rough;y 5.3 to 8. The SVD approach used by Scikit-Learn's LinearRegression class is about $O(n^2)O(n^\{2\})$O(n2), so if you double the number of features, you multiply the computation time by 4. Both the Normal Equation and SVD approach get very slow when the number of features grows large. On the positive sie, both are linear with regards to number of instances in the training set, so they can handle large training sets well provided they can fit in memory. Predictions are very fast with a linear model once you have trained it - the computational complexity is linear with regards to the number of instances you want to make predictions on.

Better suited for cases where there are a large number of features, or too many training instances to fit in memory. Gradient Descent is a very generic optimization algorithm capable of finding optimal solutions to a wide range of problems. The general idea of Gradient Descent is to tweak parameters iteratively in order to minimize a cost function. Gradient Descent measures the local gradient of the error function with regards to the parameter vector $\mathit{\theta }\backslash bm\{\backslash theta\}$θ, and it goes in the direction of the descending gradient. Once the gradient is 0, you have reached a minimum. Concretely, you start by filling $\mathit{\theta }\backslash bm\{\backslash theta\}$θ with random values (this is called random initialization) and then you improve it gradually, taking one baby step at a time, each step attempting to decrease the cost function (e.g., the MSE), until the algorithm converges to a minimum.

An important parameter in Gradient Descent in the size of the steps, determined by the learning rate hyperparameter. If the learning rate is too small, the algorithm will have to go through too many iterations to converge (too slow). If the learning rate is too high, then the algorithm might diverge, with larger and larger values, failing to find a good solution.

Finally, not all cost functions look like nice regular bowls. There may be holes, ridges, plateaus, and all sorts of irregular terrains, making convergence to the minimum very difficult. You might converge to a local minimum, which is not as good as a global minimum.

The MSE cost function for a Linear Regression model happens to be a convex function, which means that if yoy pick any two points on the curve, the line segment joining them never crosses the curve - this implies that there are no local minima, just one global minimum. It is also a continuous function with a slope that never changes abruptly. These two facts have a great consequence: Gradient Descent is guaranteed to approach arbitrarily close to the global minimum. In fact, the cost function has the shape of a bowl, but it can be an elongated bowl if the features have different scales. The image below shows why you should ensure that all features have a similar scale when using Gradient Descent - it will be faster. The diagram also illustrates the fact that training a model means searching for a combination of model parameters that minimizes a cost function (over the training set). It is a search in the model's parameter space: the more parameters a model has, the more dimensions this space has, and the harder teh search is: searching for a needle in a 300-dimensional haystack is much trickier than in three dimensions. Fortunately, since the cost function is convex in the case of Linear Regression, the needle is simply at the bottom of the bowl.

Batch Gradient Descent

To implement Gradient Descent, you need to compute the gradient of the cost function with regards to each model parameter ${\theta }_j\backslash theta\; \_j$θj​. In other words, you need to calculate how much the cost function will change if you change ${\theta }_j\backslash theta\; \_j$θj​ just a little bit. This is called the partial derivative.

Partial Derivative of the Cost Function:

Instead of computing the partial derivatives individually, you can use the equation below. The gradient vector, denoted ${\mathrm{\nabla }}_{\mathit{\theta }}\text{MSE}(\mathit{\theta })\backslash nabla\; \_\{\backslash bm\{\backslash theta\}\}\; \backslash text\{MSE\}(\backslash bm\{\backslash theta\})$∇θ​MSE(θ), contains all of the partial derivatives of the cost function (one for each model parameter). This formula involves calculations over the full training set $\mathbf{\text{X}}\backslash textbf\{X\}$X at every Gradient Descent step. This is why it is called Batch Gradient Descent. As a result, it is terribly slow on very large training sets, but it scales well with the number of features.

Once you have the gradient vector which points uphill, just go in the opposite direction to go downhill. This means subtracting ${\mathrm{\nabla }}_{\mathit{\theta }}\text{MSE}(\mathit{\theta })\backslash nabla\; \_\{\backslash bm\{\backslash theta\}\}\; \backslash text\{MSE\}(\backslash bm\{\backslash theta\})$∇θ​MSE(θ) from $\mathit{\theta }\backslash bm\{\backslash theta\}$θ. This is where the learning rate $\eta \backslash eta$η comes into play: multiply the gradent vector by $\nu \backslash nu$ν to determine the size of the downhill step:

Below you can see a quick implementation of this algorithm:

The image above shows different learning rates. On the left, the learning rate is too small and it will take a while to find a solution. On the right, the learning rate is too high and the algorithm diverges. In the middle, the learning rate converges to a solution in a few iterations. To find a good learning rate, you can use grid search. However, you may want to limit the number of iterations so that grid search can eliminate models that take too long to converge. Setting the Number of Iterations: A simple solution is to set a very large number of iterations but to interrupt the algorithm when the gradient vector becomes tiny - that is, when the norm becomes smaller than a number $ϵ\backslash epsilon$ϵ, called the tolerance - becuase this happens when Gradient Descent has almost reached the minimum.

Stochastic Gradient Descent

The main problem with Batch Gradient Descent is the fact that it uses thw hole training set to compute the gradients at every step, which makes it very slow when the training set is large. At the opposite extreme, Stochastic Gradient Descent just picks a random instance in training set at every step and computes the gradients based only on that instance. This makes the algorithm much faster and able to train on very large data sets. Dur to its random (stochastic) nature, this algorithm is much less regular than Batch Gradient Descent. Instead of gently decreasing until it reaches the minimum, the cost function will bounce up or down, decreasing only on average. Once the algorithm stops, the final parameter values are good, but not optimal.

When the cost function is very irregular, the algorithm can jump oit of local minima, so Stochastic Gradient Descent has a better chance of finding the global minimum than Batch Gradient Descent. Randomness is good to escape from local optima, but bad because it means that the algorithm can never settle at the minimum. One solution is to gradually decrease the learning rate - start large then get smaller in a process called simulated annealing. The function that determines the learning rate at each iteration is called the learning schedule.

If the learning rate is reduced too quickly, you may get stuck in a local minimum, or even end up frozen halfway to the minimum. If the learning rate is reduced too slowly, you may jump around the minimum for a long time and end up with a suboptimal solution if you halt training too early. [...] By convention, we iterate by rounds of $mm$m iterations; each round is called an epoch.

Since the instances are picked randomly, some instances may be picked several times per epoch while others may not be picked at all. Of you want to be sure that the algorithm gets through every instance at each epoch, another approach is to shuffle the training set at each epoch. This generally converges more slowly.

To perform Linear Regression using SGD with Scikit-Learn, you can use the SGDRegressor class, which defaults to optimizing the squared error cost function.

Mini-batch Gradient Descent

Mini-batch Gradient Descent: at each step, instead of computing the gradients based on the full training set or based on just one instance, Mini-batch GD computes the gradients on small random sets of instances called mini-batches. The main advantage of Mini-batch GD over Stochastic GD is that you can get a performance boost from hardware optimization of matrix operations, especially when using GPUs. The algorithm's progress in parameter space is less erratic than SGD (see image below), especially with fairly large mini-batches. As a result, Mini-batch GD will end up walking around a bit closer to the minimum that SGD. But, on the other hand, it may be harder to escape from local minima,

Summary of Linear Regression

Note that $mm$m is the number of training instances, and $nn$n is the number of features.

Even if the data is not linear (see graph below), a linear model can still be used to fit the data. A simple way to do this is to add powers of each feature to new features, then train a linear model on this extended set of features. This technique is called Polynomial Regression. You can use Scikit-Learn's PolynomialFeatures class to transform the training data. You can then perform linear regression on the extended training data.

Not bad: The model estimates $\widehat{y}+0.473x_1^2+1,024x+2.1614\backslash hat\{y\}+0.473x\_1^2+1,024x+2.1614$y^​+0.473x12​+1,024x+2.1614 when the original function was $y=0.5x^2+x+2.0+\text{ Gaussian Noise}y=0.5x^2\; +\; x\; +\; 2.0\; +\; \backslash text\{\; Gaussian\; Noise\}$y=0.5x2+x+2.0+ Gaussian Noise. Note that when there are multiple features, Polynomial Regression is capable of finding relationships between features (which is something plain Linear Regression can not do). This is made possible by the fact that PolynomialFeatures also adds all combinations of features up to the given degree. For example, if there were two features $aa$a and $bb$b, PolynomialFeatures with degree=3 would not only add the features $a^{2}a^2$a2, $a^{3}a^3$a3, $b^{2}b^2$b2, and $b^{3}b^3$b3, but also the combinations $abab$ab, a^2b$, and $a{b}^{2}ab^2$ab2. You should beware of the combinatorial explosion of number of features:

Learning Curves

If you perform high degree Polynomial Regression, you will likely fit the training data much better than with plain Linear Regression. (See Image Below) Of course, this high Polynomial Regression is severely overfitting the training data, while the linear model is underfitting it. How can you decide how complex you model should be? You could use cross-validation to get an estimate of the model's generalization performance. Another way is to look at learning curves: there are plots of the model's performance on the training set and the validation set as a function of the training set size (or the training iteration). To generate the plots, simply train the model several times on different sized subsets of the training data.

The learning curves below are typical of an underfitting model:

First, let’s look at the performance on the training data: when there are just one or two instances in the training set, the model can fit them perfectly, which is why the curve starts at zero. But as new instances are added to the training set, it becomes impossible for the model to fit the training data perfectly, both because the data is noisy and because it is not linear at all. So the error on the training data goes up until it reaches a plateau, at which point adding new instances to the training set doesn’t make the average error much better or worse. Now let’s look at the performance of the model on the validation data. When the model is trained on very few training instances, it is incapable of generalizing properly, which is why the validation error is initially quite big. Then as the model is shown more training examples, it learns and thus the validation error slowly goes down. However, once again a straight line cannot do a good job modeling the data, so the error ends up at a plateau, very close to the other curve.

If your model is underfitting the training data, adding more training examples will not help. You need to use a more complex model or come up with better features. The second learning curve below:

1. The second leaning curve below shows that the error on the training data is much lower than the Linear Regression model.
2. There is a gap between the curves. This means that the model performs significantly better on the training data than on the validation data - the hallmark of an overfitting model.

One way to improve an overfitting model is to feed it more training data until the validation error reaches the training error.

The Bias / Variance Tradeoff

An important theoretical result of statistics and Machine Learning is the fact that a model's generalization error can be expressed as the sum of three very different errors:

1. Bias

• This part of the generalization error is due to wrong assumptions, such as assuming the data is linear when it is actually quadratic, A high-bias model is most likely to underfit the training data.

2. Variance

• This part is due to the model's excessive sensitivity to small variations in the training data. A model with many degrees of freedom (such as a high-degree polynomial model) is likely to have high variance, and thus to overfit the training data.

3. Irreducible Error

• This part is due to the noisiness of the data itself. The only way to reduce this part of the error is to clean up the data.

Increasing a models' complexity will typically increase its variance and reduce its bias. Conversely, reducing a model's complexity increases its bias and reduces its variance. This is why it is called a tradeoff.

A good way to reduce overfitting is to regularize the model (to constrain it): the fewer degrees of freedom it has, the harder it will be for it to overfit the data. For a linear model regularization is typically achieved by constraining the weights of the model. We will now look at Ridge Regression, Lasso Regression, and Elastic Net, which implement three different ways to constrain the weights.

Ridge Regression

Ridge Regression also called Tikhonov regularization is a regularized version of linear Regression: aregression term equal to $\alpha {\sum }_{i=1}^n{\theta }_i^2\backslash alpha\; \backslash sum\_\{i=1\}^n\; \backslash theta\; \_i^2$α∑i=1n​θi2​ is added to the cost function. This forces the learning algorithm to not only fit the data but also keep the model weights as small as possible. Once the model is trained, you want to evaluate the model's performance using the unregularized performance measure. The hyperparameter $\alpha \backslash alpha$α controls how much you ant to regularize the model. If it equals 0, then all weights are very close to 0. If $\alpha \backslash alpha$α is very largem then all weights end up very close to zero and the result is a flat line going through the data's mean. Note that the bias term ${\theta }_0\backslash theta\; \_0$θ0​ is not regularized and that the regularization term is equal to 1/2 times the ${\mathrm{\ell }}_2\backslash ell\; \_2$ℓ2​ norm of the weight vector squared (where the weight vector is the feature weights ${\theta }_1\backslash theta\; \_1$θ1​ to $\theta _n$). It is important to scale the data before performing Ridge regression.

Ridge Regression Cost Function

The image below shows Ridge Regression with different $\alpha \backslash alpha$α values. Note how increasing $\alpha \backslash alpha$α leads to a flatter (less extreme, more reasonable) predictions; this reduces the models' variance but increases its bias.

Ridge Regression Closed-Form Solution

Lasso Regression

Least Absolute Shrinkage and Selection Operator Regression (also called Lasso Regression) is another regularized version of Linear Regression: just like Ridge regression, it adds a regularization term to the cost function, but it uses the ${\mathrm{\ell }}_1\backslash ell\; \_1$ℓ1​ norm of the weight vector instead of half the square of the ${\mathrm{\ell }}_2\backslash ell\; \_2$ℓ2​ norm. The image below shows Lasso Regression in action.

Lasso Regression Cost Function

An important feature of Lasso Regression is that it tends to completely eliminate the weights of the least important features (i.e. , set them to zero). Lasso Regression automatically performs feature selection and outputs a sparse model (i.e., with few nonzero feature weights).

[Description of the Image Below]: on the top-left plot, the background contours (ellipses) represent an unregularized MSE cost func‐ tion ($\alpha$ = 0), and the white circles show the Batch Gradient Descent path with that cost function. The foreground contours (diamonds) represent the ${\mathrm{\ell }}_1\backslash ell\; \_1$ℓ1​ penalty, and the triangles show the BGD path for this penalty only ($\alpha \rightarrow \infty$). Notice how the path first reaches ${\theta }_1\backslash theta\; \_1$θ1​ = 0, then rolls down a gutter until it reaches ${\theta }_2\backslash theta\; \_2$θ2​ = 0. On the top-right plot, the contours represent the same cost function plus an ${\mathrm{\ell }}_1\backslash ell\; \_1$ℓ1​ penalty with $\alpha \backslash alpha$α = 0.5. The global minimum is on the ${\theta }_2\backslash theta\; \_2$θ2​ = 0 axis. BGD first reaches ${\theta }_2\backslash theta\; \_2$θ2​ = 0, then rolls down the gutter until it reaches the global minimum. The two bottom plots show the same thing but uses an ${\mathrm{\ell }}_2\backslash ell\; \_2$ℓ2​ penalty instead. The regularized minimum is closer to $\theta \backslash theta$θ = 0 than the unregularized minimum, but the weights do not get fully eliminated.

You need to gradually reduce the learning rate in order to actually converge to the global minimum with Lasso Regression.

Elastic Net

Elastic Net is a middle ground between Ridge Regression and Lasso Regression. The regularization term is a simple mix of both Ridge and Lasso's regularization terms, and you can control the mix ration $rr$r. When $r=0r=0$r=0, Elastic Net is equivalent to Ridge regression, and when $r=1r=1$r=1, it is equivalent to Lasso Regression.

Elastic Net Cost Function

It is almost always preferable to have at least a little bit of regularization, so generally you should avoid plain Linear Regression. Ridge is good by default, but if you suspect some features to be useless, it is best to use Elastic Net. In general, Elastic Net is preferable over lasso since Lasso might behave erratically when the number of features is greater than the number of training instances or several features are strongly correlated.

Early Stopping

A very different way to regularize learning algorithms such as Gradient Descent is to stop training as soon as validation error reaches a minimum. This is called early stopping.With early stopping, you just stop training as soon as the validation error reaches a minimum. It is such a simple and efficient regularization technique that Geoffrey Hinton called it a "beautiful free lunch".

Some regression algorithms can be used for classification as wll. Logistic Regression (also called Logit Regression) is commonly used to estimate the probability that an instance belongs to a particular class. If the estimated probability is greater than 50%, then the model predicts that the instance belongs to that class or else it predicts that it does not. This makes it a binary classifier.

Estimating Probabilities

Just like a Linear Regession model, a Logistic Regression model computes a weighted sum of the input features (plus a bias term), but instead of outputting the result directly like the Linear Regression model does, it outputs the logistic of this result

Logistic Regression Model Estimated Probability (Vectorized Form)

The logistic - noted $\sigma (\cdot )\backslash sigma\; (\backslash cdot)$σ(⋅) - is a sigmoid function that outputs a number between 0 and 1.

Logistic Function

Once the logistic model has estimated the probability, it makes the prediction $\widehat{y}\backslash hat\{y\}$y^​ easily:

Training and Cost Function

The objective of training is set the parameter vector $\mathit{\theta }\backslash bm\{\backslash theta\}$θ so that the model estimates high probabilities for positive instances and low probabilities for negative instances. This idea is captured by the cost function below:

The cost function over the whole function is simply the average cost over all training instances. It can be written in a single expression called the log loss:

The bad news is that there is no known closed-form equation to compute the value of $\mathbf{\theta }\backslash bf\{\backslash theta\}$θ that minimizes the cost function. But the good news is that this cost function is convex, so Gradient Descent is guaranteed to find the global minimum. The partial derivatives of the cost function with regards to the $j^{th}j^\{th\}$jth model parameter ${\theta }_j\backslash theta\; \_j$θj​ is given by:

Once you have the gradient vector containing all the partial derivatives, you can se it in the Batch Gradient Descent algorithm.

Decision Boundaries

Using the iris dataset to illustrate Logistic regression. This is a famous dataset that contains the sepal and petal length and width of 150 iris flowers of three different species: Iris Setosa, Iris-Versicolor, and Iris-Virginica.

There s a Decision Boundary at around 1.6cm where both probabilities are equal to 50%: if the petal width is higher than 1.6cm, the classifier will predict that the flower is an Iris-Virginica, or else it will predict that it is not (even if not very confident). The dashed line in the image below represents the model's decision boundary. Note that this is a linear boundary. Each parallel line represents the points where them model outputs a specific probability from 15% to 90%.

Softmax Regression

The Logistic Regression model can be generalized to support multiple classes directly, without having to train and combine multiple binary classifiers. This is called Softmax Regression, or Multinomial Logistic Regression. The idea is quite simple: when given an instance $\mathbf{\text{x}}\backslash textbf\{x\}$x , the Softmax Regression model first computes the score $s_k(\mathbf{\text{x}})s\_k(\backslash textbf\{x\})$sk​(x) for each class $kk$k, then estimates the probability of each class by applying the softmax function (also called the normalized exponential) to the scores.

Softmax Score for Class known

Note that each class has its own dedicated parameter vector ${\mathit{\theta }}^k\backslash bm\{\backslash theta\}^k$θk. All these vectors are typically stored as rows in a parameter matrix $\mathrm{\Theta }\backslash Theta$Θ. Once you compute the score for every class for the instance $\mathbf{\text{x}}\backslash textbf\{x\}$x, you can estimate the probability ${\widehat{p}}_k\backslash hat\{p\}\_k$p^​k​ that the instance belongs to class $kk$k by running the scores through the softmax function: it computes the exponential of every score, then normalizes them. The scores are generally called logits or log-odds.

Minimizing the cross entropy should lead to a model that estimates a high probability for the target class. Cross entropy is frequently used to measure how well a set of estimated class probabilities match the target class.

Scikit-Learn's LogisticRegression uses one-versus all by default when you train it on two or more classes, but you can set the multiclass hyperparameter to multinomial to switch it to Softmax Regression instead. You must also specify a solver that supports Softmax Regression, such as the "lbfgs solver. It applies ${\mathrm{\ell }}_2\backslash ell\; \_2$ℓ2​ regularization by default.

[The image below] shows the resulting decision boundaries, represented by the background colors. Notice that the decision boundaries between any two classes are linear. The figure also shows the probabilities for the Iris-Versicolor class, represented by the curved lines (e.g., the line labeled with 0.450 represents the 45% probability boundary). Notice that the model can predict a class that has an estimated probability below 50%. For example, at the point where all decision boundaries meet, all classes have an equal estimated probability of 33%

Cross Entropy

Cross entropy originated from information theory. Cross entropy measures the average number of bits you actually send per option. Here is a video on cross entropy