From Boosting Learning to Neural Networks: Seeing Mountains as Mountains?

AdaBoost Algorithm

Boosting learning belongs to the category of ensemble models. Of course, rather than calling it an algorithm, it is better described as a way of thinking about problem-solving. Taking supervised classification as an example, it suggests that weak classifiers (as long as their accuracy is strictly greater than that of a random classifier) can be combined in a certain way to obtain an excellent classifier (theoretically achieving 100% accuracy). The AdaBoost algorithm is an example of a Boosting algorithm, proposed by Schapire in 1996. It constructed an explicit scheme for Boosting learning and provided a theoretical proof regarding the error rate.

Taking a binary classification problem as an example, assume we have a set of samples \{x_i, y_i\}, i=1, 2, \dots, n, where x_i is the sample data (potentially multi-dimensional input) and y_i \in \{1, -1\} is the sample label. Using 1 and -1 to describe labels instead of the usual 1 and 0 is merely for convenience in later proofs and has no special meaning. Next, assume we already have a weak classifier G(x), such as Logistic Regression, SVM, or a Decision Tree. The only requirement for the classifier is that its accuracy must be strictly greater than random (strictly greater than 0.5 in a binary classification problem). "Strictly greater" means there exists a constant \epsilon > 0 such that the accuracy at each step is no less than \frac{1}{2} + \epsilon.

The idea of the AdaBoost algorithm is: Before training with the weak classifier G(x) each time, set different weights w_{k,1}, w_{k,2}, \dots, w_{k,n} for the samples (increasing the weights of previously mispredicted samples). This way, models with different parameters G_1(x), G_2(x), \dots, G_m(x) are obtained each time (these can be the same model with different parameters or a combination of different models), and then they are combined as follows: y = \bar{G}(x) = \text{sign}[f(x)] = \text{sign}\left[\sum_{k=1}^m \alpha_k G_k(x)\right] Here f(x) = \sum_{k=1}^m \alpha_k G_k(x). Finally, it can be proven that \bar{G}(x) is an excellent classifier. Since the AdaBoost algorithm is not the main focus of this article, I have placed the specific mathematical details at the end to avoid distracting from the main point.

Seeing Mountains as Mountains, Seeing Waters as Waters

Putting aside the mathematical details, let us reflect: what exactly does the AdaBoost algorithm do? Or more broadly, what is the essence of ensemble models?

When we build a classification model, the typical process is as follows:

1. Find a set of labeled data, such as sentiment reviews in a text sentiment classification model;
2. Construct features;
3. Choose an appropriate model, such as Logistic Regression, SVM, or Neural Networks;
4. Input the data into the model for training;
5. Verify the results and optimize/improve.

Beginners often focus their energy on step 3, becoming obsessed with high-precision non-linear models. In fact, models with very high precision often incorporate a strong process of feature construction. If the features are well-constructed, even a simple linear model (like Logistic Regression) can achieve high precision. In other words, the most important step in modeling should be the second step—feature construction.

Of course, constructing good features is also the hardest step. Good features require a thorough understanding of the data and sometimes professional background knowledge. There is no unified method for combining existing features into better ones. At this stage, we often struggle with feature construction and look forward to surprises in the prediction results. This is the so-called "seeing mountains as mountains, seeing waters as waters" (features are just features, results are just results).

Seeing Mountains Not as Mountains, Seeing Waters Not as Waters

However, why not be a bit more imaginative? Again, assume we have a binary classification task, such as text sentiment classification. We use existing data to train a model, say Logistic Regression, obtain the parameters, and output some prediction results with an accuracy higher than 50%. Are these prediction results merely results?

From a mathematical perspective, these results are derived through a linear combination of the original data followed by a non-linear transformation via a logistic function. Simply put, they are obtained through operations on the original features. Looking at it this way, why not view it as a way of constructing features?

Exactly! It is a result, but it is also a feature! You use one set of weights to train a Logistic Regression model and get a set of prediction results; you change the weights to train another Logistic Regression model with different parameters and get a new set of prediction results; and so on. Why not treat these results as features and feed them into another Logistic Regression model? This model, at the very least, will not be less accurate than any single original model, right? Thus, we reach a magical conclusion: models can be used to predict results, but they can also be used to construct features—results are features. At this point, we have reached the realm of "seeing mountains not as mountains, seeing waters not as waters"—the boundary between features and results has blurred.

Suddenly, it might become clear: the essence of Boosting learning is simply treating the results of models as features and then building another model on top of them. Since the results of the models are generally good features, the final step can significantly improve the classifier’s performance—good features naturally lead to high precision.

At this point, one cannot help but admire Laozi’s words: "The Tao that can be told is not the eternal Tao; the name that can be named is not the eternal name."

Seeing Mountains as Mountains Again, Seeing Waters as Waters Again

This is a new perspective: viewing model results as constructed features. However, have we not used this method before?

In fact, we have, though it might not have been obvious. Suppose there is a binary classification problem (e.g., predicting whether someone smokes), where one feature is gender, taking values Male/Female. How do we quantify this for the model? We might use 1 to represent Male and 0 to represent Female. Can this not be seen as constructing the following model? G(x) = \begin{cases} 1, & x = \text{Male} \\ 0, & x = \text{Female} \end{cases} Clearly, this can be viewed as a model (where the input is gender and the output is smoking status, with 1 representing smoking) to predict whether an individual smokes. What was originally just a method of representing a feature has now become the prediction result of a model, which we then input into a new model for prediction. Looking back at this process, is it not also treating a result as a feature to be fed into a model?

It turns out we have been using this idea for a long time; it just wasn’t explicit. Reflecting on this, we find its shadow in many aspects of data mining. Perhaps we have returned to simplicity, reaching the feeling of "seeing mountains as mountains again, seeing waters as waters again." The Boosting learning algorithm (AdaBoost) can be said to have carried this idea to its full potential. And after reading the description of the neural network section below, this feeling will be even stronger.

Neural Networks

However, the model that truly pushes this idea to the extreme is the neural network.

Do neural networks have a relationship with Boosting learning? Yes, a neural network can be seen as an enhanced version of a special case of AdaBoost. From this, we can also use the theoretical proofs of AdaBoost to explain why neural networks are so powerful.

How so? Let’s revisit what was said earlier:

Exactly! It is a result, but it is also a feature! You use one set of weights to train a Logistic Regression model and get a set of prediction results; you change the weights to train another Logistic Regression model with different parameters and get a new set of prediction results; and so on. Why not treat these results as features and feed them into another Logistic Regression model? This model, at the very least, will not be less accurate than any single original model, right?

What does this process look like if represented as a diagram? As shown below:

At first glance, isn’t this just a three-layer network model?

Exactly, this is a three-layer neural network model! Choosing Logistic Regression as the weak classifier and using the AdaBoost algorithm for ensemble learning results in something equivalent to a three-layer neural network model! However, neural networks are even more sophisticated. The AdaBoost algorithm is trained step-by-step, similar to a greedy algorithm, which likely leads to a local optimum. In contrast, neural networks leave all parameters to be determined and use a loss function to find the global optimum. From this perspective, neural networks are superior. Furthermore, neural networks can nest more layers (which can be seen as using AdaBoost as a weak classifier and combining it multiple times to obtain an even better classifier). Therefore, in the era of deep learning, the significance of the AdaBoost algorithm has diminished. What remains unchanged is that its core idea still holds important heuristic value.

Not only that, from the perspective of "treating prediction results as features," we can also derive the structure of RNNs (Recurrent Neural Networks)! We notice that the current AdaBoost algorithm only uses the outputs of previous models as features in the final step. Why not use both the previous outputs and the original data together as features for the model? If we do this, we form the prototype of an RNN—adding the previous output to the current input.

At this point, neural networks become a special case of the AdaBoost algorithm, but also its enhanced version. Perhaps it can be said that neural networks have pushed the idea of ensemble models to its pinnacle.

Now, it seems Boosting is everywhere; it truly is "seeing mountains as mountains again, seeing waters as waters again!" Because Boosting was never just an independent model; it is a profound problem-solving philosophy—and profound thoughts have far-reaching impacts.

Supplement: Related Derivations of the AdaBoost Algorithm

For the AdaBoost algorithm, it is not difficult to understand, but the challenge lies in how to select the weights w and \alpha. Schapire provided a selection scheme:

1. Initially, set w_{1,1}=w_{1,2}=\dots=w_{1,n}=\frac{1}{n}, and train the classifier G_1(x) with these weights.
2. In each subsequent step, update w and \alpha as follows: \begin{aligned} \alpha_k &= \frac{1}{2}\log\frac{1-\varepsilon_k}{\varepsilon_k} \\ w_{k+1,i} &= \frac{1}{Z_k}w_{k,i}\exp\left(-\alpha_k y_i G_k(x_i)\right) \end{aligned}

Where \varepsilon_k is the error rate, i.e., the number of mispredicted samples divided by n when using model G_k(x). Mathematically: \varepsilon_k = \sum_{i=1}^n w_{k,i} I\left(-y_i G_k(x_i)\right) Here I(x) is the indicator function: I(x) = \begin{cases} 1, & x > 0 \\ 0, & x \leq 0 \end{cases} When the prediction is correct, -y_i G_k(x_i) = -1, so I(-y_i G_k(x_i)) = 0. Conversely, I(-y_i G_k(x_i)) = 1. Thus, \sum I(-y_i G_k(x_i)) counts the errors. Z_k = \sum_{i=1}^n w_{k,i}\exp(-\alpha_k y_i G_k(x_i)) is the normalization factor.

The biggest question is why choose them this way? Analyzing the error rate provides some clues. The error rate \varepsilon of the final classifier \bar{G}(x) is estimated as: \begin{aligned} \varepsilon &= \frac{1}{n} \sum_{i=1}^{n} I\left(-y_i \bar{G}(x_i)\right) = \frac{1}{n} \sum_{i=1}^{n} I\left(-y_i f(x_i)\right) \\ & < \frac{1}{n} \sum_{i=1}^{n} \exp\left(-y_i f(x_i)\right) \end{aligned} Substituting the expression for f: \begin{aligned} \frac{1}{n} \sum_{i=1}^{n} \exp(-y_i f(x_i)) &= \frac{1}{n}\sum_{i=1}^{n} \exp\left(-y_i \sum_{k=1}^m \alpha_k G_k (x)\right) \\ &= \sum_{i=1}^{n} w_{1,i}\prod_{k=1}^m\exp\left(-y_i \alpha_k G_k (x)\right) \\ &= Z_1 Z_2 \dots Z_m \end{aligned} Looking at Z_k: \begin{aligned} Z_k &= \sum_{\text{correct}} w_{k,i}e^{-\alpha_k} + \sum_{\text{incorrect}} w_{k,i}e^{\alpha_k} \\ &= e^{-\alpha_k}(1-\varepsilon_k) + e^{\alpha_k} \varepsilon_k \\ &= 2\sqrt{(1-\varepsilon_k)\varepsilon_k} \quad (\text{substituting } \alpha_k) \\ &= \sqrt{1-4\gamma_k^2} \quad (\text{where } \gamma_k = \frac{1}{2}-\varepsilon_k) \\ &\leq \exp\left(-2\gamma_k^2\right) \end{aligned} So \varepsilon < Z_1 Z_2 \dots Z_m < \exp\left(-2\sum_{k=1}^m \gamma_k^2\right). If \gamma_k has a positive lower bound, the error rate decreases exponentially to 0.

For more on Boosting, refer to: http://www.52caml.com/head_first_ml/ml-chapter6-boosting-family/

Original address: https://kexue.fm/archives/3873

For more details on reprinting, please refer to: Scientific Space FAQ