Machine learning models: SVR, trees and ensembles

1. Machine learning, beyond the neural

The deck begins with the standard definition: machine learning is the study of computer algorithms that can improve automatically by the use of data. It is seen as a part of artificial intelligence. Machine learning algorithms build a model based on sample data, known as "training data", in order to make predictions or decisions without being explicitly programmed to do so.

Then the scope note that gives the chapter its title: several ML models can be applied to forecasting: neural networks, but also decision trees, support vector machines (SVMs), Bayesian networks, and others. Chapter 5 covered the neural branch; here the deck gives a hint of SVMs and decision tree learning — and the tree branch is not optional reading, because the exam project requires one regression-tree-based method.

2. Support Vector Machines

Support Vector Machines are machine learning classifiers which, given labeled training data (supervised learning), compute an optimal hyperplane which separates (categorizes) the examples. The word doing the work is optimal, and the deck defines it: optimality comes from maximizing the margin around the separating hyperplane. This increases robustness in classification.

The separating hyperplane is determined by coefficients (w, b), and the classes are labelled by the sign of f(w,b), i.e. the output is in {-1, +1}.

The intuition is geometric and worth holding onto: among the infinitely many hyperplanes that separate two labelled clouds, SVM picks the one that sits as far as possible from the nearest points of either class. Those nearest points are the support vectors — the only observations that actually determine the solution.

3. Support Vector Regression and the ε-insensitive tube

SVR uses hyperplane and margin too, but with differences in their definitions. The two differences are the whole method:

• The margin, called the ε-insensitive tube, is the error tolerance of the model. This tube allows some deviation of the data points from the hyperplane.
• The hyperplane is the best fit possible to the data that fall within the ε-insensitive tube.

So where a classifier maximises a margin that must contain no points, a regressor defines a tube that should contain all points — and only deviations outside the tube are penalised. Support Vector Regression with ε-insensitive loss function (Vapnik, 1995) allows a tolerance degree to errors not greater than ε, and gives us through ε the flexibility to define how much error is acceptable in our model, finding an appropriate line or hyperplane to fit the data.

The kernel trick

Training data for the regression model is {(x₁,y₁), …, (x_ℓ,y_ℓ)}. SVR (like SVM) applies to the input points a transformation function Φ (defining a kernel function) to a higher-dimensional Feature Space F. In F, we construct a linear model, corresponding to a non-linear model in the input space.

That sentence is the whole idea of kernel methods: the model stays linear, the space becomes nonlinear. And the payoff comes from a computational accident — solving the dual form and projecting to higher dimensional spaces in order to achieve nonlinear separations (kernel trick), an inner product appears, K(x_i,x_j) = Φ(x_i)·Φ(x_j), where K is named Kernel function. You never have to compute Φ explicitly; you only need the inner products. Standard kernels are proposed for actual applications — rbf being the default in the code below.

The optimization problem

The goal of the ε-insensitive loss function is to find a function that (1) fits training data with deviation less or equal to ε, and (2) is as flat as possible. On each:

1. Usually impossible, so we introduce slack variables ξ⁺, ξ^- to allow errors greater than ε.
2. Obtained by minimizing weights, for example their quadratic norm ‖w‖².

min   ½‖w‖²  +  C Σᵢ (ξᵢ⁺ + ξᵢ⁻)

s.t.   yᵢ - (‹w, Φ(xᵢ)› + b)  ≤  ε + ξᵢ⁺
       (‹w, Φ(xᵢ)› + b) - yᵢ  ≤  ε + ξᵢ⁻
       ξᵢ⁺, ξᵢ⁻ ≥ 0,   i = 1, …, ℓ

sc_X = StandardScaler(); sc_y = StandardScaler()
X = X.reshape(-1, 1)
X = sc_X.fit_transform(X)
y = sc_y.fit_transform(Y)

from sklearn.svm import SVR
regressor = SVR(kernel='rbf', C=250.0, gamma=20, epsilon=0.2)
regressor.fit(X, y.flatten())

y_pred = regressor.predict([[6.5]])
y_pred = sc_y.inverse_transform(y_pred)

Note the standardisation of both X and y, and the inverse transform at the end — chapter 3 again. And note the three hyperparameters that will need the tuning machinery of chapter 9: C (how heavily slack is punished), gamma (the width of the RBF kernel) and epsilon (the tube). For forecasting, the slides add the simple statement that regression models can be directly projected to future periods.

4. Decision trees and ID3

A decision tree is a tree-like structure where at every node we make a decision and continue doing it till we reach a conclusion. The deck is careful about the algorithmic character of the thing: the corresponding search algorithm implements a heuristic function using probabilities as comparison values, but does not implement backtracking (greedy). That word greedy is the one to remember — once a split has been chosen, it is never revisited, so a decision tree is a locally optimal structure, not a globally optimal one.

One of the first popular decision tree algorithms was ID3. Basically, it only constructs a tree data structure and implements two mathematical formulas to build the complete algorithm — entropy and information gain, section 5.

The classic example: a tree that advises, based on weather conditions, whether to play ball or not. If the outlook is sunny and the humidity is less than or equal to 70, then it is probably OK to play.

The five steps

1. It begins with the original set S as the root node.
2. On each iteration, it iterates through every so-far unused attribute of the set S and calculates entropy (H) or information gain (IG) of this attribute.
3. It then selects the attribute which has the smallest entropy or largest information gain.
4. The set S is then split by the selected attribute to produce a subset of the data.
5. The algorithm continues to recur on each subset, considering only attributes never selected before.

# x: examples in the training set, y: the set of attributes
# labels: classification values, e.g. {0, 1, 0, 1}
def ID3(x, y, label, node):
  initialize node as a new node instance
  if all rows in x only have single classification c:
    insert label c into node
    return node
  if x is empty:
    insert dominant label in x into node
    return node
  bestAttr is an attribute with maximum information gain in x
  insert attribute bestAttr into node
  for vi in values of bestAttr:
    # e.g. Outlook has three values: Sunny, Overcast, Rain
    insert value vi as branch of node
    create viRows with rows that only contain value vi
    if viRows is empty:
      this node branch ended by a leaf with the dominant label in x
    else:
      newY = list of attributes y with bestAttr removed
      nextNode = ID3(viRows, newY, label, nextNode)
  return node

The two base cases are worth naming. Pure node: every row has the same class, so emit a leaf. Empty node: no rows reached here, so emit the dominant label of the parent. Everything else recurses on a strictly smaller attribute set, which is what guarantees termination.

5. Entropy, information gain and the split criterion

Some criteria are proposed for solving this attribute selection problem, and the deck lists six:

These criteria will calculate values for every attribute. The values are sorted, and attributes are placed in the tree by following the order.

Information entropy

Information entropy is a fundamental quantity commonly used in information theory to measure importance of information relative to its size. If X is the training set containing positive and negative examples, the entropy of X relative to this classification is the usual -Σ p_i log₂ p_i.

And the operational rule ID3 follows: a branch with an entropy of zero is a leaf node, and a branch with entropy more than zero needs further splitting. Zero entropy means the node is pure.

Information gain

Information gain is a statistical property that measures how well a given attribute separates the training examples according to their target classification. Information gain is a decrease in entropy. It computes the difference between entropy before split and average entropy after split of the dataset based on given attribute values.

IG(x, y) = H(x)  -  Σᵥ ( |xᵥ| / |x| ) · H(xᵥ)

Constructing a decision tree requires finding an attribute that returns the highest information gain and the smallest entropy. Those are the same requirement stated twice: gain is high exactly when the weighted post-split entropy is low.

6. From classification trees to regression trees

This is the section the exam project depends on. Decision trees (e.g. ID3) were originally designed to predict discrete class labels. They split the data based on features to maximize class purity (e.g. information gain). For regression, the structure remains the same: recursive partitioning of feature space.

Four changes, and only four:

And the consequence, stated by the deck in one phrase that tells you exactly what a tree forecast looks like when you plot it: result: piecewise constant approximation of the target function. A regression tree cannot extrapolate a trend — outside the range of its training targets it returns the nearest leaf average, flat. Chapter 3's differencing is therefore not optional for tree-based forecasting either.

The worked example

The deck turns a monthly sales series into a lagged dataset — the sliding window of chapter 5 once more — and grows a small tree on it.

7. Ensembles: why voting works

The basic idea of ensemble classifiers is stated in eight words: build different classifiers, and let them vote.

And then a small calculation that makes the case better than any argument. Suppose there are 25 base classifiers, each with error rate ε = 0.35, and assume independence among classifiers. The probability that the ensemble classifier makes a wrong prediction — that is, that thirteen or more of the twenty-five are wrong at once — is the binomial tail

P(ensemble wrong) = Σᵢ₊₁₃²⁵ C(25, i) εᵢ (1 - ε)²⁵⁻ᵢ  ≈  0.06

Each member is wrong 35% of the time; the committee is wrong 6% of the time. Note the assumption doing the heavy lifting: independence. Everything that follows in sections 8 and 9 — bootstrapping the data, sampling the features — is machinery for buying as much independence between the members as possible.

Two ways to build the committee

8. Boosting, gradient boosting, XGBoost

In boosting we train the individual models in a sequential way. Each individual model learns from mistakes made by the previous model. AdaBoost and Gradient Boost are named as different types of boosting methods.

The historical note in the deck is precise and worth quoting: boosting was originally developed by computational learning theorists to guarantee performance improvements on fitting training data for a weak learner that only needs to generate a hypothesis with a training accuracy greater than 0.5. It was then revised to be a practical algorithm, AdaBoost, for building ensembles that empirically improves generalization performance.

The practical improvement is weighting: instead of sampling, re-weigh examples. Examples are given weights. At each iteration, a new hypothesis is learned (weak learner) and the examples are reweighted to focus the system on examples that the most recently learned classifier got wrong. The final classification is based on a weighted vote of weak classifiers, where a better weak classifier gets a larger weight.

Gradient boosting decision trees

In gradient boosting decision trees, we combine many weak learners to come up with one strong learner. The weak learners here are the individual decision trees. All the trees are connected in series and each tree tries to minimize the error of the previous tree. The consequence is stated frankly: due to this sequential connection, boosting algorithms are usually slow to learn, but also highly accurate. The weak learners are fit in such a way that each new learner fits into the residuals of the previous step so that the model improves.

Why trees specifically? Decision trees are used as the weak learner in gradient boosting. Specifically, regression trees are used that output real values for splits and whose output can be added together, allowing subsequent models outputs to be added and correct the residuals in the predictions. Additivity is the requirement, and it is what makes a regression tree the natural choice.

Trees are constructed in a greedy manner, choosing the best split points based on purity scores like Gini or to minimize the loss. Initially — for instance in AdaBoost — very short decision trees are used that only had a single split, called a decision stump. Larger trees with 4-to-8 levels can later be used. And it is common to constrain the weak learners in specific ways, such as a maximum number of layers, nodes, splits or leaf nodes.

On the additive model itself: trees are added one at a time, and existing trees in the model are not changed (greedy). A gradient descent procedure is used to minimize the loss when adding trees. Instead of optimizing parameters, we add more specific decision trees. To perform the gradient descent, we add a tree to the model that most reduces the loss (i.e. we follow the gradient). Training stops when a fixed number of trees are added, or once loss reaches an acceptable level or no longer improves on an external validation dataset.

XGBoost in practice

The XGBoost library has its own Python API, but we can also use XGBoost models with the scikit-learn syntax via the XGBRegressor wrapper class.

9. Bagging and random forest

Bagging starts from an observation about trees: decision trees are sensitive to the specific data on which they are trained. If the training data is changed — e.g. a tree is trained on a subset of the training data — the resulting decision tree and the predictions can be quite different.

The remedy turns that weakness into the mechanism: to overcome this problem, we create N learners (decision trees) and produce N new training data sets by random sampling with replacement from the original set. The final prediction is the average of predictions from N decision trees.

Aggregate Bootstrapping
  Given a standard training set D of size n
  For i = 1 .. M
     draw a sample of size n' ≤ n from D uniformly and WITH REPLACEMENT
     learn classifier Cᵢ
  Final classifier derived from a vote by C₁ .. Cₓ

In operational terms: given a dataset S, at each iteration i a training set S_i is sampled with replacement from S (bootstrapping), and a classifier C_i is learned for each S_i. For classification, each C_i returns its class prediction and the bagged classifier H counts the votes, assigning the class with the most votes. For regression — the case that matters here — bagging can be applied to the prediction of continuous values by taking the average value of each prediction.

Random forest

Random forest is an ensemble of decision tree algorithms. It is an extension of bootstrap aggregation (bagging) of decision trees and can be used both for classification and regression problems. Each decision tree is fit on a slightly different training dataset, and in turn has a slightly different performance.

Two design decisions distinguish it from plain bagging, and both are aimed at decorrelating the members — buying back the independence the binomial calculation of section 7 assumed.

How it works, step by step

Each tree is grown on a bootstrap sample of the training set of n cases. A number m is specified much smaller than the total number of variables M (e.g. m = √M). At each node, m variables are selected at random out of the M, and the split used is the best split on these m variables. Final classification is done by majority vote across trees; a prediction on a regression problem is the average of the prediction across the trees.

The training procedure, for some number of trees T: sample N cases at random with replacement to create a subset of the data — the subset should be about 66% of the total set. At each node, m predictor variables are selected at random from all the predictor variables; the predictor variable that provides the best split, according to some objective function, is used to do a binary split on that node; at the next node, choose another m variables at random and do the same. The requirement is that m ≪ number of predictor variables, with suggested values √M, ½√M and 2√M.

from sklearn.ensemble import RandomForestRegressor
from sklearn.feature_selection import RFE
from sklearn.metrics import mean_absolute_error

df = pd.read_csv('BoxJenkins.csv', usecols=[1], names=['Passengers'], header=0)

lookback = 12                                   # rolling window dataset (see MLP)
X, y = create_dataset(df["Passengers"].values, lookback)
nfore = 12
x_train, _     = X[:-nfore], X[-nfore:]
y_train, ytest = y[:-nfore], y[-nfore:]

RFmodel = RandomForestRegressor(n_estimators=500, random_state=1)
RFmodel.fit(x_train, y_train)

# rolling 12 step prediction  — identical in shape to the XGBoost loop
xinput = x_train[-1]
yfore = []
for i in range(12):
   yfore.append(RFmodel.predict(xinput.reshape(1,12))[0])
   xinput = np.roll(xinput, -1)
   xinput[-1] = yfore[-1]

Two extras the deck shows are useful in a project write-up. Inspecting the ensemble:

n_nodes, max_depths = [], []
for ind_tree in RFmodel.estimators_:
    n_nodes.append(ind_tree.tree_.node_count)
    max_depths.append(ind_tree.tree_.max_depth)
print(f'Average number of nodes {int(np.mean(n_nodes))}')
print(f'Average maximum depth {int(np.mean(max_depths))}')

from sklearn.tree import plot_tree           # plot the first tree
plot_tree(RFmodel.estimators_[0], max_depth=2, filled=True,
          impurity=True, rounded=True)

and feature selection, which closes the loop with the dimensionality reduction of chapter 3:

# find the columns with most predictive power
rfe = RFE(RFmodel, n_features_to_select=4)    # Recursive Feature Elimination
fit = rfe.fit(X, y)
predictors = [names[i] for i in range(len(fit.support_)) if fit.support_[i]]
print("Columns with predictive power:", predictors)

Random forest compared with boosting

Check your understanding