Machine Learning 1. Lecture 10. Linear Ensembles

What this lecture is about

Today we have a very important topic, and I will begin straight away with a motivator. The answer to the question "name the three strongest machine learning methods" has stayed the same for more than twenty years: SVM, boosting and neural networks. Clearly everyone talks about neural networks now, but there are many problems where both SVM and boosting are still ahead. And boosting is a linear ensemble, so the topic is important.

A small spoiler. We will begin with general definitions and simple things, and in the second part there will be precisely that boosting with which everything began. It is an old method; something better has been done since, and I will tell about that something in the next lecture. But the meanings here are so dense that one cannot pass them by: it was a very serious turn in machine learning. Not such as with the appearance of large language models, of course, but still. We will talk about that too.

Ensembles of models

What are ensembles about at all? About our solving some machine learning problem, and it turns out to be hard. We build one algorithm, a second, train different models, and somehow nothing works out. Here we have built many different not very successful algorithms, and the question arises: could one successful one be assembled from them?

This suggests an analogy with how we make measurements in physics. If we cannot measure a quantity accurately once, we measure it many times and then average the measurements; the accuracy of the mean grows in proportion to the square root of the number of measurements. On these ideas, in the eighties, people widely put forward the hypothesis that one could probably assemble one strong classifier from many weak ones. That is exactly how Kearns and Valiant formulated this idea in 1989, and that is exactly how it is cited in the foreign literature. Ten years earlier Yurii Ivanovich Zhuravlev formulated it slightly differently and developed his approach, which he called the algebraic approach to pattern recognition. The terminology I will now use comes from the algebraic approach; it is good in that it is very general and covers all variants of compositions altogether.

The formulation of the problem

Let us begin with the formal notation. A training sample is given, and we build base algorithms. An algorithm, let me remind you, is what we call a mapping from $X$ to $Y$, a trainable mapping. How it is trained is also called an algorithm in Western literature, but in my course, so as not to get confused, I call that a training method.

So the idea is to assemble one good algorithm from many bad ones. For this, in Zhuravlev's terms, such a decomposition of base algorithms is made. Base algorithms $a_t$ are, as a rule, and most classification methods are arranged this way, a superposition. The main mapping translates $x$ into some space of estimates $R$; these are, for example, estimates of the degree of membership of an object in the classes. And then these estimates are coarsened and turn into $y$: in a classification problem $Y$ is a discrete set. If we tried to do the correction, the aggregation, over the answers of the base algorithms themselves in the discrete set $Y$, nothing much would come of it: it would be a rather weak construction. For correction we need finer estimates: they contain more information about the classes.

So a decomposition arises: a superposition of two, in the general case trainable, transformations $C$ and $b$. The $b$ are called algorithmic operators, $C$ the decision rule. Now we, as it were, break the base algorithms, tear $C$ away from $b$, and say that we will carry out the composition, or correction, or aggregation of the base algorithms in the space of estimates $R$. This is done by a correcting operation, a function from $R^T$ to $R$: at the input it takes $T$ answers of the base algorithmic operators and aggregates them somehow into the answer of the composition. This is to a large extent a technical device of decomposition; it allows us to work in convenient spaces of estimates and to introduce them as we like.

Let me explain on examples what a space of estimates is and how decision rules can be arranged in this connection. The first example is classification. One can, in principle, make a composition over the classifications themselves; then $C$ is the identity transformation, the decision rule is simply not used, and $R$ is the space of classes itself. Why it is bad to do so I have already said: in the space $Y$ the class of correcting operations is too poor; there is nothing to choose from except perhaps some voting.

The second example is classification into two classes; we have already seen many such problems. The classes are denoted $-1$ and $+1$, and the algorithm is arranged as a superposition of the decision rule $C$ and the base algorithmic operator $b$, in Zhuravlev's terms. In the English terminology that has taken root, $b$ is called a real-valued classifier. The decision rule here is simple and untrainable: it is simply the sign function, there are no parameters in it.

The third example: what if there are many classes? We have seen this construction, for example, when we talked about metric classifiers or about logistic regression, and will see it again when we talk about Bayesian classification theory. The classifiers are arranged as an $\arg \max$ over the classes, and $b_y(x)$ is the estimate of the degree of membership of the object $x$ in the class $y$. These are our base algorithmic operators, or real-valued classifier, but now it returns not one number but as many numbers as there are classes: for each class its own estimate of the degree of membership. And the $\arg \max$ is the decision rule, now of $M$ arguments.

And the fourth example, similar to the first: in regression problems decision rules need not be used, because $Y=\mathbb{R}$ is a space convenient in itself for building any correcting operation in it.

Correcting functions

Now about aggregating, or correcting, functions; I keep saying both these words, because in the literature they are called both ways.

Let us think about what axiomatic requirements should be imposed on an aggregating function. Probably the range of its values on the $T$ answers of the base algorithms should lie between the minimal and the maximal of them: it would be strange if we went outside this range; there we no longer have information about how the base algorithms worked. Any such aggregating value in this range is called a generalised Cauchy mean: these are some variants of averaging, but there can be many different ones.

The second requirement is more substantial: $F$ must be a monotone function in all its arguments $b_1,\dots ,b_T$. Imagine this situation: all the base algorithms return on an object the same answer as before, and one of them begins to return a larger one. It would be strange if as a result of the correction the answer of the composition decreased. This is a very natural consideration, and this requirement is directly the definition of a monotone function of $T$ arguments.

What aggregating functions are most often used in practice? Averaging, of course; I began with that: the mean of physical measurements is more accurate than an individual measurement. Simple averaging in the case of classification is called simple voting; it is probably the simplest thing one can think of. In weighted voting we add the coefficients ${\alpha }_t$; before, they were all the same. Some base algorithms work better, some worse; those that are better we trust more, and they should probably be given a larger weight. So ${\alpha }_t$ is in essence a discrete distribution on the weights: non-negative coefficients normalised to one.

And the coolest generalisation of the mean is a mean in which the coefficients ${\alpha }_t$ are replaced by functions of $x$. We say: in one part of the space one base algorithm works well, and in another another; and these parts of the space are described by the competence functions of the base algorithms, or gates. In English these are gating functions; in Russian they are translated in different ways, as sluices, as valves. Today we will talk about simple and weighted voting, and we will touch on mixtures of algorithms next time.

The problem of diversity of base algorithms

Let us return once more to the analogy with physical measurements. Why will it not work directly in machine learning problems, and how can this idea still be advanced?

The analogy works well when the observations are independent: then we know that with the mean we estimate the expectation, and the variance of this estimate tends to zero as $T$ tends to infinity. But the base algorithms, or rather their answers, the vector of $T$ answers, are certainly not independent random variables. Why? Because the base algorithms solved one and the same problem, we trained them on the same data, on one and the same target vector, and, moreover, they are usually also chosen from one and the same model. There are, of course, approaches where heterogeneous classifiers are aggregated: let us take a neural network, a decision tree, something else like nearest neighbour, models that in themselves divide the space differently. Such an approach exists, but it is rarely used; most often the base algorithms are taken from one model.

So the variance will certainly no longer decrease at the same rate as when averaging independent variables. But such an aim is still set: one still wants to achieve a decrease of the variance with the growth of the number of base algorithms. What should one strive for to achieve this? That the base algorithms be different: if they are the same or almost the same, there will be no sense in building a composition from them.

Here there is a contradiction, a double-edged sword. On the one hand, the base algorithms must work reasonably well, at least better than random guessing, for a good solution to be assembled from them. On the other hand, if they all work well, it means they are similar to each other and lack diversity, and then there is no sense in building a composition. Diversity will help reduce the variance: the base algorithms will not, of course, become independent variables, but they will depend on each other less, and this will probably have a positive effect on the variance decreasing as the number of base algorithms grows.

How can diversity be increased, what ideas come to mind here? One can train the base algorithms not on the whole sample, one and the same for all, but on random subsamples: we introduce some noise, randomness, but all the base algorithms still solve one and the same problem; we only shorten their training samples. One can cut down their sets of features: random subspaces of features. One can, as I have already said, take them from different parametric models. One can deliberately introduce some randomisation. One can even deliberately spoil the data, put noise either on $x$ or on $y$; this too is done, and it even works. Let us try to combine at least some of these ideas and do it in the simplest way possible.

Simple voting: bagging and random subspaces

We have gone through the setting-up stage, given definitions, and now we will take up methods. The first method is called bagging. This word was cooked up from bootstrap aggregating.

Methods of stochastic ensembling

The bootstrap is choosing objects "with replacement": we choose a random object from the sample but return it, so that we have a chance to choose it again, perhaps even several times. With such choosing with replacement not all objects get into the sample: some will be chosen several times, and some not once. We keep the sample size the same, $\ell$: choosing objects with replacement, we get exactly as many objects as there were, but this sample will be, as it were, a random incarnation of the original one; there will be repetitions in it. What is the share of objects that will enter the bootstrap sample? It is estimated very well, and as $\ell$ tends to infinity we will see here literally the definition of the number $e$: it is $63.2\%$. That is, roughly two thirds of the sample get into the subsample each time, and there will be repetitions among these selected objects.

This is not the only way, though the most popular. Why? Because many interesting theorems have been proved about the bootstrap, including that this sample is unbiased. Do not be troubled that objects repeat in it, although there were no repetitions in the original sample, and that something seems wrong with such a distribution. Nevertheless it is a sample from the same distribution, and in this sense it is unbiased. The bootstrap has useful theoretical properties, so it is often used.

But, of course, one can also use simply random training subsamples: pasting. Especially when you know that in your particular problem the training sample is highly redundant: you have, perhaps, a million objects, and you suspect that you will tune the model quite well on a thousand. Should one sample a million again from a million by bootstrap? By and large, no: one can randomly reduce the amount of data and, if the data were originally redundant, not lose much in quality.

What else can be done? Let us look at the "objects–features" matrix: the rows are objects, the columns features. We have just chosen a random subset of rows; the same can be done with the columns. These are random subspaces: we choose a random subset of features. And if we pull out of the "objects–features" matrix a submatrix, a subset of rows and a subset of columns, these are random patches on the matrix. And finally, one can do all sorts of cross-validations: split the sample into blocks and train on all the blocks except one. There are in fact many different techniques, and the essence of all of them is one: select a random part of the data on which one can nevertheless train a decent model.

Now let us agree: we have a training method $\mu$, which takes as input a subsample of objects $U$ and a subset of features $G$ from the set of all features. We will never get inside the training method, and this is really great. This is called a wrapper over an already existing training method: we simply feed it a subset of the data at the input.

Stochastic ensembling in one pseudocode

In this pseudocode I have combined two methods. Bagging is based on bootstrap aggregating, on forming training subsamples by bootstrap, and the random subspace method on choosing random subsets of features. One can do either the one or the other, or both at once.

What happens here? In turn, for all base algorithms, we take a random subsample, and there may be many methods of choosing a random subsample, I have just roughly described them; the pseudocode does not fix the method. We have formed a random subsample and a random subset of features, and we build a base algorithm. It may happen that the subsample is too small or there has simply been a failure, and the base algorithm has come out bad. Let us introduce a parameter ${\epsilon }_1$ that controls the quality on the training subsample itself: if the error is above the given threshold ${\epsilon }_1$, we will not include such a base algorithm in the ensemble; it did not come out. For example, we look, and its share of errors on training is more than a half. Why can this happen? Some needed features did not enter; there were not enough informative features to build a classifier of acceptable quality. Let us not take it, let us discard it at once: it was unlucky.

And if we have random subsamples being formed, then there are objects left on which we did not train. That is great! It means we can get an unbiased estimate of the generalisation ability of the base algorithm, and put a threshold on it too, ${\epsilon }_2$: if the base algorithm has come out too bad already from the point of view of working on an independent validation sample, we will not take it into the ensemble either. Such is the method, please welcome it: bagging, even with a generalisation towards the random subspace method.

And what to do with these base algorithms? The simplest answer there can be: simple voting, just average them. We tried to make them as independent of each other as possible. And by the way, we built them on random subsamples, without peeking at each other, which means that the loop over $t$ can be executed in parallel altogether. This is very good news: the method is very easily parallelised; the base algorithms can be built independently of each other.

The unbiased out-of-bag estimate

One more very important thing we get here for free when we build base algorithms on random subsamples. $U_t$ is a random subsample, and $X^{\ell }\setminus U_t$ then turns out to be a test sample: there are objects on which we did not train this base algorithm, and it would be good to check it on them along the way. How is this to be done?

Look what an unusual idea. For each $i$-th object let us take the set $T_i$ of base algorithms that did not train on it. Recall bagging: each base algorithm trains on roughly $63\%$ of the objects, so roughly $37\%$ of the base algorithms did not train on each given object. That is quite a lot: if we build a composition of a hundred base algorithms, roughly 37 of them, give or take, did not train on a given object. We can average over them, precisely over these algorithms, not over all, but only over those for which the $i$-th object was a validation one and not a training one.

Now we average these out-of-bag estimates over all objects and look at the mean losses over the whole sample. This will be an unbiased estimate of the error of the ensemble on the training sample. This is really great: without explicitly doing a hold-out split into train and test, we have got a split into train and test for each base algorithm of its own, and have been able to use all these splits at once to estimate the generalisation ability of the whole ensemble.

What does this allow? Well, simply making an unbiased estimate of quality is already great. But one can also extract from it estimates of the importance of features. Since the out-of-bag estimate is unbiased, we can apply it to an ensemble in which the $j$-th feature is used and to an ensemble from which the $j$-th feature has been removed. One can do this honestly: when training the base algorithms, forbid them all to use the $j$-th feature. One can, but it takes long. Or one can do it more simply: when computing $b_t(x_i)$ for out-of-bag, we take and randomly shuffle the values of the feature on all validation objects. We will not rebuild the model; let it still use this feature, but on the validation objects we shuffle its values among the objects. What have we done? We still feed the model this feature from the same distribution at the input, only it is shuffled: it has become noise, uninformative. If the out-of-bag sagged badly as a result, it means the feature was very important for the model. The greater the relative difference in the quality of the model with the spoiled feature and with all features, the higher the informativeness of the $j$-th feature. This estimate is built into all decent implementations of bagging, and the estimates of the informativeness of features are, as a rule, built in too. They can and should be used.

From simple voting to weighted voting

To finish with simple voting: can one, having built base algorithms as we have just done, use not simple voting but weighted voting?

Yes, of course one can: then you simply build a linear classifier over the base algorithms as over features. You have already trained them; for you they are fixed functions on the objects of the sample, and now one can build a linear classifier over them as over features, and if it is a matter of regression, a linear regression. If uninformative ones have to be found among these base algorithm features, please: we use LASSO, impose constraints on the coefficients $\alpha$, or inequality constraints, so that there are no negative ones among them. These ways in effect allow the composition of base algorithms to be regularised and the superfluous ones thrown out of it, if there are any.

There is one more way; we will understand it better when we have the lecture on Bayesian classification theory and learn what the naive Bayes classifier is. It assumes that the features are independent; in our case, building weighted voting, we will assume the independence of the base algorithms. Now, stop, stop, stop: we only just said, ten minutes ago, that this certainly does not hold, and even in bagging we try to make the base algorithms as different as possible. Well, still, then as a heuristic. If the base algorithms are independent as random variables, the optimal solution for the coefficients ${\alpha }_t$ can be obtained analytically, and it looks like this, where $p_t$ is the share of errors, the estimate of the probability of error of the base algorithm. Clearly: the more a base algorithm errs, the smaller its ${\alpha }_t$ will be, and if it errs fifty-fifty, that is, is engaged in random guessing, then ${\alpha }_t$ will be zero. By such formulas, without any optimisation, without any training, fairly crudely, but already taking into account the quality of the individual base algorithms, one can compute the coefficients ${\alpha }_t$.

The random forest

How did things develop further? Bagging was invented around 1996, as far as I remember, and people at once began to try different base algorithms, to try to answer the question over which family of base algorithms this aggregation technique works better. They tried a lot: neural networks, SVM, nearest neighbours, rules, and decision trees, and settled on decision trees. Why? Because they have one remarkable drawback that bagging turns into a merit. Decision trees are very unstable to changes in the composition of the sample: if you change even something small in the sample, and all the more when you do bagging and train on random subsamples, the trees become highly diverse, and their quality may suffer. But that is exactly what is needed for aggregation! When building individual trees, instability, a strong dependence of the structure of the tree on the composition of the training sample, is a drawback; we always say that it is bad. But in this case it is, on the contrary, good, because it increases the difference between the base algorithms.

This is what the Random Forest method consists of: we do bagging over decision trees, and we do not try to make the individual decision trees as good as possible. In particular, we do no pruning, and the feature at each node is chosen from a random subset of features. We do still keep an element of training, an element of optimisation. Remember, in a decision tree, when choosing the branching criterion at each node, we go over all the features, simply a loop over $j$ from one to $n$? Well, here the search is not over all the features but over a random subset of $k$ of the $n$.

How to take this number $k$ is the subject of a certain holy war. Clearly it depends on the problem, on the number of noisy, noise, uninformative features; it is an individual property of each problem, and there are no universal recipes here. In Leo Breiman's paper there was this recommendation: $k$ roughly a third of the features for regression and, for some reason, the root of $n$ for classification. I would say that it depends rather on the problem after all, and one should search, not use heuristics of this sort.

In random forests there are not many parameters, and by choosing them one can build a very effective ensemble. There will be many trees, each individual tree will work poorly, but all together, even after simple, unweighted voting, they give a more or less reliable classifier. Random Forest is considered one of the best universal machine learning methods: it cracks problems of any complexity. If the boundaries between your classes are of very complex shape, Random Forest is what should be applied.

What can be tuned here? Clearly, the number of base algorithms, of trees. The number $k$, how many features we select at random; this is a very important parameter, which is, as a rule, chosen, and literally a few values are enough to search over. The maximal depth of the trees: if the depth is small, many trees will be needed, and individually they will not be very good; the greater the depth, the better the quality of the individual trees, but they may turn out overfitted. One can search over much else too: the minimal number of objects of the sample from which we determine the feature in the branching criterion; the minimal number of objects falling into a leaf, which is something like a pre-pruning criterion. People also tried different branching criteria. But the main parameters are, of course, the first three.

On the internet there is a huge number of examples of what compositions of decision trees look like when enough trees are built. On the slide are wonderful pictures from Alexander Dyakonov's blog, where there are many articles about machine learning, including about ensembles: the separation of a sample by individual trees (with their bootstrap subsamples) and by a random forest of 10, 100 and 1000 trees. The sample is the famous "two bananas", or two moons: classes penetrating each other, a hard problem for a linear classifier. For trees it is not very simple either: one can see that an individual tree classifies not very well somehow; the separating surface of individual trees is angular. But look how everything is smoothed out: even ten trees are, by and large, enough for the boundary to be built more or less, and with a thousand trees it did not particularly improve. When angular trees are averaged, even ten turn out to be enough for the separating surface between the classes to be smoothed out.

On the topic of decision forests, from the mid-nineties and especially from the early 2000s, there was a huge amount of research, and people tried to build all sorts of things here. I will not dwell on this; well, for example, rotation forest. It turned out that if we build trees like this, not very accurately, on subsets of features, and then allow ourselves to optimise the rotation of the whole tree in space, then optimising these rotations, even roughly, allows a classifier to be built that works even better. Not always, without a guarantee, but still it is one of the successful heuristics.

So what are the advantages and limitations? The advantage is that this is a wrapper method: the base algorithms can be anything, we simply feed them a subset of objects and a subset of features at the input and do not get inside. This is a splendid property: methods of this kind are easily generalised to regression, classification and other machine learning problems; everything depends on how the loss function is set, and in different problems it is set differently. A very simple implementation, very easily parallelised: bagging is good precisely for this purely technical feature. There is the unbiased out-of-bag estimate of quality and the possibility of estimating the importance of features from these unbiased estimates. And, as I have already said, Random Forest is generally one of the leaders in universality: the hardest problems from the most diverse fields are solved by the Random Forest method, and, as a rule, a rather high generalisation ability results. Thanks to what, we will still talk about today, but in rough terms: thanks to the base algorithms being averaged and their errors compensating each other: the error is smeared out, its variance decreases.

But there are also limitations, drawbacks. First, sometimes very many base algorithms are required; these may be not even hundreds but thousands. And if we are talking about decision trees, what do we love them for? For being interpretable; they have a very simple and clear structure. But if we take a thousand trees, there is no longer any question of interpretation; interpretability is lost. And one more limitation, which, if we have time, we will work on at the end of the lecture. Trees are unstable; they respond strongly to the composition of the training sample and even change their structure. But there are methods that are, on the contrary, super-stable, for example SVM. Building bagging from SVM is something nobody has particularly managed, by and large, precisely for this reason: you make subsamples, and the set of support objects stays the same or almost the same, and no diversity of base algorithms results.

Weighted voting: AdaBoost

Now the most interesting and the most important thing for today's lecture: boosting, as it was invented in the mid-nineties. I will tell about AdaBoost, with which all this hype began.

Boosting for binary classification

We consider the problem of classification into two classes. The base algorithms return $-1$, $0$ or $+1$; zero means abstaining from classification. Clearly, when we average by weighted voting, a zero answer of a base algorithm means that in the composition it is not taken into account on this object. In English this property is called abstain: classification algorithms are supposed to return plus or minus one, but if they return zeros, they are said to abstain from classification. Here a simplification is used that I scolded at the beginning of the lecture: we do not apply the decision rule to the base algorithms; they themselves already give discrete-valued answers, and we average these answers, and take the sign only of the composition. This is a limitation that we will later give up: in the next lecture I will tell about gradient boosting, which removes this limitation completely and passes into AdaBoost as a special case.

So weighted voting is a linear classifier where the base algorithms $b_t(x)$ are used as features; $T$ is the number of base algorithms. Our task is to build a composition, that is, to find at once all the base algorithms $b_t$ and the coefficients ${\alpha }_t$ at them so as to minimise the number of errors on the training sample. The difficulty is that the problem comes out heterogeneous. If it is posed as simultaneous training of both $\alpha$ and $b$ for all base algorithms, it stops being a wrapper, while we would dream of making a method that uses standard methods of training base algorithms.

For this the following heuristic is introduced: we will add base algorithms to the composition one at a time, considering that all the previous ones have already been built and fixed. That is, this is a greedy method of building a composition. And one more heuristic: we will use smooth approximations of the threshold loss function. The loss function here is in effect "the margin is less than zero", an unpleasant, piecewise-constant one, and we will replace it by a smooth loss function. We have already met this trick: logistic regression, SVM and much else. The only question is which approximation we will take.

Smooth approximations of the threshold loss function

In the boosting I will now tell about, the approximation is exponential. It was tried first, and this gave a semi-analytical solution of the optimisation problem, which is splendid and very convenient. Then people began to try all the others too, got, of course, to logistic regression and to SVM, and different variants of boosting over other loss functions appeared. Each such study was a separate scientific paper finding out whether it works better than AdaBoost or worse. But historically the first in this line was AdaBoost, so that is what we will now consider.

The exponential approximation

So what do we do? We build an upper bound of the quality functional $Q_T$: we replace the threshold function "the margin is less than zero" by the exponential function and get an upper bound for our functional, which will be denoted ${\tilde{Q}}_T$. Now let us use a remarkable property of the exponential: the exponential of a sum equals the product of exponentials. We agreed that all the previous base algorithms have already been built and are fixed for us, so we take their sum under the exponential out, and it will be a factor, and the second factor, a separate exponential, will be the algorithm we are now going to build, and the coefficient ${\alpha }_T$ at it.

Let us think about what the first factor, the weight $w_i$, means: which objects will get large weights and which small ones? By and large it is clear: if the margin is large and negative, the exponential will be large. This means that if on the $i$-th object the whole previous composition made a big error, then for building the next algorithm precisely this object will have the largest weight. Large weights go to those objects on which the whole previous composition erred most. This seems very logical, and we understood it literally at once, after the very first line of the derivation, when we passed to the exponential approximation of the threshold loss function.

We will normalise the weights and denote the normalised weights ${\tilde{w}}_i$. Next we will need a definition that will be used in the theorem. For an arbitrary normalised non-negative weight vector $U^{\ell }$, it is the same as ${\tilde{W}}^{\ell }$, but for generality I write $u_i$, let us define the weighted share of wrong classifications $N$: it is a sum over objects with weights $u_i$ whose sum equals one, and the condition in brackets means that the algorithm errs on the object, errs but does not abstain from classification. In exactly the same way, the weighted share of correct classifications $P$, where the condition in brackets means that the base algorithm $b$ gives the correct answer on $x_i$. One can also compute the share of objects on which the base algorithm returns zero, that is, abstains from classification: it equals $1-N-P$. A base algorithm has three possible answers, plus or minus one and zero, and the shares will of course sum to one, because the weights are normalised.

The main theorem of boosting

Classical AdaBoost was invented for the situation where the base algorithms do not abstain from classification. A little later the same authors, Freund and Schapire, invented a scheme with the abstain property, abstention from classification, and showed on experimental data that such compositions work better. That is, if a base algorithm is not confident in its answer, let it rather return zero: let it not lie but honestly say that this is not its area of competence. For the composition this turned out to be good, so I begin at once with this generalisation, although it was invented a year later.

Suppose that for any normalised weight vector, in the base family of algorithms, the parametric family of functions from which we choose $b$, there exists an algorithm that classifies the sample at least slightly better than at random. The requirement is non-trivial, because it contains the quantifier "for any normalised weight vector". If one takes a fixed weight vector, practically any family will satisfy this requirement. But "for any" is already a stronger restriction. In practice, however, as a rule all the families we use, decision trees certainly, satisfy this requirement, so it does not restrict us much.

Then the minimum of the approximated functional ${\tilde{Q}}_T$ is attained when two very interesting formulas hold, which in effect tell us that base algorithms can be built very easily and quickly, and the coefficients ${\alpha }_T$ at them determined simply by an analytical formula. The theorem says that one has to maximise this interesting criterion: $\sqrt{P}-\sqrt{N}$. When in the last lecture we talked about informativeness criteria for logical rules, I wrote out this criterion and promised to show where it comes from. Now there will be the proof of the theorem, and you will understand that it comes from the exponential approximation of the threshold loss function. And for ${\alpha }_T$ there is this simple formula.

The proof is not difficult, very instructive and beautiful, and I hope we will understand it quickly. This is the rare case when I do insert a mathematical proof into my course: it seems to me interesting.

Freund and Schapire are geniuses, of course: to think of such a simple thing and to prove so simply and elegantly that with the exponential approximation of the loss function compositions are easily built by an iterative process, where each base algorithm is built by the criterion of maximum of $\sqrt{P}-\sqrt{N}$. Great!

Convergence

Let us obtain a couple more facts as corollaries. The first: it turns out that we have convergence on the training sample; in the limit we get an algorithm that makes no errors at all. Whether this is good or bad has to be discussed separately. It would seem that it is bad, because it is guaranteed overfitting; but it is good if we are talking about the ability of the classifier to minimise the number of errors on training.

That is, if the family is so rich that at each step it ensures the building of a base algorithm whose $\sqrt{P}-\sqrt{N}$ is not simply greater than zero but greater than some positive number $\gamma$, then in a finite number of steps a correct algorithm will be built, making not a single error on the training sample. The proof is simple and beautiful.

This is an interesting fact about convergence, but it is, of course, convergence not in the sense of generalisation ability but only in the sense of the number of errors on the training sample.

Classical AdaBoost

One more corollary. As I have already said, the original variant of AdaBoost was invented for base algorithms that cannot abstain from classification. Then it is simply a corollary of the previous theorem.

The share of correct answers $P$ we can express as $1-N$, simplify the criterion for building base algorithms and see that it has become the ordinary formula of the method of empirical risk minimisation, only with weighted objects. $N$ is the weighted share of errors on the training sample: our usual functional, a sum over all the objects of the sample of the binary loss function "error or not error", but each object is taken with its own weight ${\tilde{w}}_i$. A huge number of machine learning methods are very easily adapted to empirical risk minimisation with weighted objects: adding weights to the optimisation problem and adapting the optimisation method to such a formulation is a simple exercise; it is always easy to do.

So such a method, AdaBoost, adaptive boosting, adaptive because it adapts the composition by adding each base algorithm so that it corrects the errors of the previous ones, also turns out to be a wrapper. If you can tune base algorithms on a weighted training sample, you can easily use AdaBoost to make a composition.

Let us put everything together. Two main operations: we train a base algorithm as usual, but with weights on the objects of the training sample, and determine the coefficient ${\alpha }_t$ by the formula from the theorem. The weights of the objects need not be recomputed from scratch each time: as the theorem shows, and we understood it even before the proof, after each base algorithm is built the weights are simply multiplied by these exponentials. True, after multiplication they have to be normalised.

When AdaBoost appeared, the whole machine learning community rushed to do experiments with boosting and, unexpectedly for itself, discovered an interesting thing: boosting does not overfit, although the number of base algorithms grows. It had always been considered that the complexity of a model is a misfortune that one has to get away from somehow; complexity has to be limited somehow. But here it turns out that the complexity of the composition can be increased practically without limit, that is, the number of base algorithms $T$ increased, and the generalisation ability gets better and better: the more base algorithms, the better the composition works. Intuitively one can understand why this might happen: we simply manage to make the base algorithms different enough. When we average them, they are not independent random variables, and we are, unfortunately, not under the conditions of the ordinary law of large numbers. But this difference turns out to be enough to reduce the variance and improve the generalisation ability of the composition as a whole. This is a non-trivial fact that came as a surprise: 1995 is, one may say, a turnaround in classification theory, where previously the complexity of a model had always been associated with the manifestation of overfitting: the higher the complexity, the sooner overfitting appears. But in boosting it is not so. We will talk about generalisation ability once more a little later; I will show one more theorem, this time without proof, but first, a few heuristics and recommendations.

Heuristics and recommendations

The base classifiers are most often trees. Recall bagging, recall Random Forest: there trees turned out to be the best choice, and for boosting too. Although experiments were also done with deliberately simple base algorithms, decision stumps: a tree sawn off at the root, with nothing left except the root. The base algorithms are simple threshold conditions on individual features, that is, in effect a binarisation of the features with only the threshold parameter tuned. In essence these are simply the original features, only binarised, and from them boosting assembles in essence a linear classifier over binarised features. This does not always work, but often it comes out quite well; true, very many such base algorithms are needed.

What else can be done? Let us note: when one and the same object turns out time after time to be unfortunate for each base algorithm, the error on it begins to grow and its weight begins to grow. This is both good and bad. Bad because we begin to train predominantly on literally a few objects, outlier objects whose weights have grown anomalously over the iterations of boosting, and we tune the next base algorithms mainly to noise objects. This is somehow wrong. But on the other hand, this is precisely a detector of anomalous objects. Let us take the objects with anomalously large weights somewhere at the tenth, twentieth, thirtieth iteration and simply throw them out of the sample.

Let me refer once more to the picture with the approximations of the loss function. If you looked at it carefully, a question might have arisen: what is this Gaussian curve, BrownBoost, where did it come from? From here: if an object has a large weight, that is, a very high loss has accumulated on it, it is most likely a noise object, and its weight should, on the contrary, be zeroed. Objects with small negative margins are still interesting for training, but in the zone of too large negative margins these are most likely outliers, and they should simply be removed from the training samples for the base algorithms. That too turned out to be an interesting heuristic.

Such a trouble may also arise, although it is rather the opposite of trouble: what if the denominator in the formula for $\alpha$ turns out to be zero? Actually that is strange: if the number of errors of a base algorithm is zero, why are we building a composition at all? Let us take this base algorithm and use it. In practice this happens extremely rarely; usually base algorithms do not give ideal quality on the training sample. But if the denominator is zero, then we add something small: sometimes only to the denominator, sometimes to both the denominator and the numerator, because this is a biased formula for a frequency estimate of probability. It is done differently.

And stopping criteria. The common practice is simply to set the number of base algorithms: we build 100, fine; we build 1000, also fine. But sometimes people look at the quality of the composition on the validation sample and stop when this quality begins to deteriorate. One can do it in different ways.

Comparison on model problems

Let us admire the model problems (the pictures on the slide). These too are "two bananas": two classes, red and blue, penetrating each other; clearly for linear classifiers this is a hard problem, they do not solve it. Look what an SVM with a radial basis function as the kernel is like there: it looks very attractive, but that is on advertising two-dimensional problems, and in practice it does not always work well. And here are the separating surfaces for individual decision trees, for random forests and for AdaBoost. At first sight AdaBoost gets some heavily jagged separating surface between the classes. But again, this is on such two-dimensional examples; on complex problems in multidimensional spaces both random forests and boosting build the boundary between the classes very carefully, and it may be arbitrarily complex. This, of course, is the advantage of all these methods. The solutions may look strange; nevertheless the random forest and boosting are considered the strongest universal methods in machine learning.

Why boosting does not overfit

Now let us return to an interesting theoretical question. How does it come about that a very complex algorithm, composed of individually not very good, weak base classifiers, has a generalisation ability that grows with the number of base algorithms?

Experiments

The experiments were done by the same Freund and Schapire with their co-authors (the figures on the slides are from their 1998 paper, the UCI problems letter and satimage). We increase the number of base decision trees to a thousand, and what do we see? In full accordance with the corollary on convergence, a zero number of errors quickly arises: not even ten base algorithms have been built yet, and on the training sample it is already zero. It would seem that we have met overfitting, and the number of errors on the validation sample should begin to grow at this moment. We are used to this: with a huge number of problems and different parametric families we have encountered this effect. But here nothing of the kind: a levelling off at a horizontal asymptote, and the more base algorithms we take, the better. On the training sample it has long been zero, while on the validation sample the quality continues to improve with the growth of the number of base algorithms.

This was unexpected, because all the theories that existed at the time, in the mid-nineties, said that with the growth of the complexity of a parametric family overfitting should appear. Before these experiments it was considered that increasing the complexity of a model, the number of parameters, inevitably leads to overfitting. But here each base algorithm adds new parameters to the composition, and yet, apparently, the way in which we train them leads not to a complication of the aggregate family but only to a smoothing of the results of the base algorithms. This had to be justified theoretically somehow.

Here is one more picture, which shows that overfitting does exist after all, but very weak. Patient Germans with a Japanese colleague in 1998 did more experiments, brought the number of base algorithms to 10 000 and showed that the error on the test did after all begin to grow. On model two-dimensional problems they showed that there is excessive jaggedness of the separating surfaces, that is, there is overfitting after all, but small, and on thousands of base classifiers; it is not much of a growth in losses.

G. Rätsch, T. Onoda, K.-R. Müller. An improvement of AdaBoost to avoid overfitting, 1998.

The theory of generalisation ability

The theoretical justification was given by the same Freund and Schapire with two more co-authors in 1998, by proving the following theorem. I will of course not consider the proof here: it is difficult; to explain this kind of theory properly one would have to give a whole course. Let us figure out in rough terms what this result means.

First, the notion of the strengthened error rate is introduced for a classifier of the form "the sign of some algorithmic operator". The only difference from how we usually define the error rate: the margin is compared not with zero but with a positive constant $\theta$. If this constant grows, the strengthened error rate increases: we penalise an object for approaching the boundary between the classes from the side of its own class. There is no error on it yet, but it is already borderline, dangerous: any moment now it will jump over the boundary between the classes. Let us already count this as an error. So the share of strengthened errors ${\nu }_{\theta }$ is a quantity greater than or equal to the ordinary ${\nu }_0$, simply the error rate of the classifier on the given sample.

The theorem is a probabilistic bound: for any $\eta$ from zero to one, with probability $1-\eta$ such a bound holds. Clearly $\eta$ must be fairly small, 5 % or 1 %; it is a kind of parametric family of bounds into which any $\eta$ can be substituted, and the more accurate the bound, the smaller the probability with which it holds. Such probabilistic estimation comes from mathematical statistics, from laws of convergence like the law of large numbers.

What does this bound say? On the left is written the probability of error of the composition on a new object: $yb(x)$ is the margin of the whole composition on an arbitrary object $x$, and the probability is taken over this object. That is, it is honestly the probability of error on a new object, not from the training sample but from the whole space. It is bounded from above by the share of errors in training, but with something extra: with the strengthened rate, which penalises objects that have come dangerously close to the boundary between the classes.

The second term is more interesting. The term with $\eta$ is a consequence of probabilistic estimation in general, an irreducible part; nothing can be done with it. But in the first term under the root we see, first, $\ln \ell /\ell$, which will decrease as $\ell$ tends to infinity. Hurray, there is convergence, there is learnability: as the length of the sample grows, one can show that the probability of error tends to zero, or at least to some small quantity. Second, there stands the logarithm of the cardinality of the base family of algorithms. How to estimate this quantity is a separate theory, but in rough terms it can even be estimated orally for decision stumps. Decision stumps are all possible features on which a threshold has been placed in all possible ways. How many different such classifiers are there in the base family? Very simple: we go over them by two nested loops, over features and then over thresholds, and that is a loop over objects, because, taking the value of a feature on an object, we get precisely a threshold. The sample is classified differently only when the threshold jumps over the nearest object. In total, the cardinality of the family of decision stumps is the number of features multiplied by the number of objects of the training sample. This is the simplest case; for trees it will be more complicated, and for some base algorithms estimating in how many different ways they are able to split the training sample is a non-trivial combinatorial problem altogether. What stands here is in effect the logarithm of the number of these ways.

The simpler the family of base algorithms, the smaller the second term will be; true, the simpler, the larger the first, the strengthened error rate. Here, of course, it is a double-edged sword, and the optimum of the complexity of the base family will have to be chosen.

Next it is interesting that ${\theta }^2$ stands in the denominator. To decrease the bound, $\theta$ has to be increased. But if we increase $\theta$, will the strengthened error rate not increase too? No, not always, and this is precisely the most interesting property of boosting: it turned out that as the number of base algorithms grows, boosting moves the classes apart, increases the gap between them. The more base algorithms are built, the larger the threshold $\theta$ that can be chosen: the objects move away from the separating surface between the classes, and that is good.

And now the main conclusion: the bound does not depend on the number of base algorithms $T$ at all. This is the most important result of the theorem: $T$ appears nowhere on the right-hand side. In a cunning way the bound does depend on $T$, but it is rather a dependence in the direction of decrease, not increase: as $T$ grows, we have the possibility of increasing $\theta$, and the strengthened error rate decreases as $T$ grows. This is a breakthrough theoretical result, unexpected for the mid-nineties. Before, it was considered that overfitting is connected with the complexity of the parametric family of functions. Boosting showed that if in a very complex parametric family the parameters are chosen competently, optimised competently, the complexity does not grow. Competent in our case turned out to be the greedy addition of algorithms one at a time: they are not trained all together, not fitted to each other, but each next base algorithm strives to correct the errors of the previous ones, and then they are averaged. And this averaging really does not increase complexity: the complexity of the whole composition, it turns out, depends only on the complexity of an individual base algorithm. This, of course, is great.

The distribution of margins

Why a separating strip between the classes appears, and why it widens as the complexity of the composition grows, is already a purely experimental fact, which was later even proved. What happens to the margins of the composition in boosting?

On the graph there are three curves of the distribution of margins; or rather two are visible, because the second and the third have merged with each other. Let us look at the distribution of margins after five iterations: one can see a certain number of objects whose margin is strictly positive, and there are no objects with negative margins; this is a consequence of that very theorem on convergence. But then something happens: as the number of base algorithms increases, the lower, zero shelf lengthens, the number of objects with strictly positive margins increases, and the minimal margin increases too; this too can be proved; we will not do that now.

How is this to be interpreted? As $T$ grows, the distribution of margins shifts to the right, that is, boosting moves the classes apart. Let us realise an important thing: in what space? In the space of vectors of growing dimension. If the base algorithms are treated as features, and a function of an object is a feature too, then this is a space of growing dimension: each base algorithm adds one to the dimension of the vector space of features of the objects. It is in precisely this space that we build a linear classifier, and in precisely this space that we speak of the margins of this linear classifier. And these margins have a remarkable property: as $T$ grows, that is, the dimension of the feature space for the linear classifier, in boosting the gap between the classes increases. That very gap we talked about when we discussed SVM, and increasing the gap between the classes promotes a more reliable solution of the classification problem. Such is a really great explanation; in its time it gave an impetus to the development of the theory of generalisation ability, to attempts to explain and understand why there is no growth of complexity for compositional schemes.

A couple more experiments. In the second half of the nineties there was a huge number of empirical studies: everyone rushed to compare boosting with bagging. Their strategies are slightly different: bagging is simple voting and random subsamples, boosting is a sequential algorithm, weighted voting, and the objects are weighted too, while in bagging the weights of objects are either zero or one. Which of them is better? It turned out that both methods are good: both reach horizontal asymptotes in quality on test data. But boosting effectively moves the classes apart in the space of growing dimension, while bagging does not do so: it does not have such a large number of objects with strictly positive and large margins. So their mechanisms of action are after all slightly different.

The drawbacks of AdaBoost

Let us go over the pluses and minuses of AdaBoost a little more. The exponential loss function penalises objects with large negative margins too heavily; this is a drawback, and, as I said, it can be fought by filtering out anomalous objects. Next: hundreds, sometimes thousands of base algorithms; if these are decision trees, it is of course a loss of interpretability. Attempts to build short compositions of strong stable algorithms of the SVM type led to nothing good, so this has to be done somehow differently. The remaining part of the lecture is precisely about one such way, a very simple, purely heuristic one: it grew out of an understanding of the merits and drawbacks of boosting and bagging and an attempt to adapt the greedy sequential scheme of building base algorithms so as to build neat compositions of a small number of stable strong base algorithms.

ComBoost: explicit optimisation of the distribution of margins

A couple of words about this method. It is our invention, from around the mid-2000s, an attempt to make our contribution to the theory and practice of boosting and bagging. What do we do here? We say: we will not use any approximations of the threshold loss function, because by doing so we do after all substitute the problem. We will minimise explicitly the number of errors of the composition on the training sample and, having realised that the whole thing lies in the distribution of margins, we will explicitly control this distribution of margins.

The problem is the same one with which AdaBoost began, only the ensemble is simple voting. But then we make no approximations, neither exponential nor any others, but simply consider the distribution of margins on the objects of the training sample for the composition of the first $t$ base algorithms. We have defined the margins. Now the heuristic: we will build the next base algorithm by training it on those objects whose margins are neither too large nor too small; we simply choose a certain subset of the training sample.

What does bagging do? It forms this subset by bootstrap, chooses at random. What does boosting do? It builds a distribution of weights of the objects and trains on the weighted sample. Let us do something in between: we will select objects for training, but by the distribution of margins, and our sample will be unweighted. This of course simplifies the procedure of building a base algorithm, although I said that generalising it to weights is not difficult, but here, as in bagging, we will have a pure wrapper method that can call the function for training base algorithms on a specially formed subsample.

How the subsample is formed is simplest to show in a picture. We take the margins of the objects and order them in ascending order. On the right is a region that does not interest us: on all these objects the composition is already good, and even if the next base algorithm errs there, the margin will not sag to zero; all will be well. On the left is a region that does not interest us either: these are noise objects, on which one should not even try to make a good positive margin. Everything is bad on them, and it will stay bad, it will not get better, so we simply get rid of these objects. And it turns out that by the margin criterion the middle region remains, the borderline objects; these are precisely the objects on which the next base algorithm should be trained. One could also build randomisation, the idea of bagging, into this, but we did not do that.

This is the pseudocode we got; we called this method ComBoost, committee boosting. What else is done here: when we train the next base algorithm, let us vary the size of the training sample. After all, we do not know exactly where on this distribution the noise objects ended and where the boundary between the borderline and the reliable ones runs; perhaps more of the reliable ones should be taken in. Let us make a whole series of training samples, build several base algorithms on them and choose the best of them as the next base algorithm of the composition.

That is the whole idea. It turned out to be enough to minimise the number of base algorithms and to use fairly strong methods, such as SVM, as the base ones. On several problems from the UCI repository it was shown that substantially fewer base algorithms are really needed: sometimes one can manage with literally a few of them. This is a rather old work of ours, done by my graduate student A. A. Matsenov.

Conclusions

Seminar