[fundamentals of machine learning 01] blending, bagging and AdaBoost

Last year's study notes , Take out your recent review and sort it out .

Aggregation Model

Suppose there is $T$ A model $g_1,\cdots ,g_T$, Common aggregation methods are ：

1. Select the best from a validation set ：

$$G(\mathbf{x})=g_{t_{\ast }}(\mathbf{x})\text{ with }{t}_{\ast }={\mathrm{argmin}}_{t\in \{1,2,\dots ,T\}}{E}_{\text{val }}\left(g_t^{-}\right)$$

2. Average all models ：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^{T}1\cdot g_t(\mathbf{x})\right)$$

3. Weighted average all models ：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{\alpha }_t\cdot g_t(\mathbf{x})\right)\text{ with }{\alpha }_t\ge 0$$

4. Determine according to the current status ：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{q}_t(\mathbf{x})\cdot g_t(\mathbf{x})\right)\text{ with }{q}_t(\mathbf{x})\ge 0$$

These are all intuitive ideas , Now let's go further .

Blending

Mean fusion （Uniform Blending）

In the classification problem ：
$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{g}_t(\mathbf{x})\right)$$
The minority obeys the majority in multi classification tasks ：

In regression, the mean value of all model outputs is taken .

When $g_t$ Similar predicted values , Then the performance remains the same . When $g_t$ Diverse democracy , Some classification results $g_t(\mathbf{x})>f(\mathbf{x})$, Other classification results $ g_{t}(\mathbf{x})<f(\mathbf{x})$, Then the best solution can be obtained by averaging the ideal state . Combine the above two requirements , Diverse hypotheses It is easier to make the fusion model perform better .

It can be deduced theoretically , Mean value fusion can reduce the error ：
$$\mathrm{avg}\left(E_{\text{out }}\left(g_t\right)\right)=\mathrm{avg}\left(\mathcal{E}{\left(g_t-G\right)}^2\right)+E_{\text{out }}(G)$$
From the above equation we can see that unless all $g_t$ equal , Otherwise, the fused model $G$ The error of is smaller than the average error of all sub models （ There is a variance difference ）.

Linear fusion （Linear Blending）

Classification problem ：
$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{\alpha }_t\cdot g_t(\mathbf{x})\right)\text{ with }{\alpha }_t\ge 0$$
The return question ：
$$\underset{{\alpha }_t\ge 0}{\min }\frac{1}{N}\sum _{n=1}^N{\left(y_n-\sum _{t=1}^T{\alpha }_t{g}_t\left({\mathbf{x}}_n\right)\right)}^2$$
Then the optimization problem can be written as ：
$$\underset{\alpha t\ge 0}{\min }\frac{1}{N}\sum _{n=1}^N\mathrm{err}\left(y_n,\sum _{t=1}^T{\alpha }_t{g}_t\left({\mathbf{x}}_n\right)\right)$$
Use the training set to get $g_t$, But it's best to use a validation set to get ${\alpha }_t$.

Stacking

As shown in the figure above , The first part is to use $N$ Basic models such as xgb1、lgb1 Conduct $n$ Crossover verification , Then you get a $N\ast n$ Characteristic matrix of , This characteristic matrix is used as the input of the second layer model . The original data set shall also pass the test $N$ Base models are mapped to $N$ Dimensional space .

Bagging

Blending Is to learn something different $g_t$ And then put them together , Can we learn from it $g_t$ Edge aggregation .

Gain diversity $g_t$ The way to do this is ：

• diversity by different models
• diversity by different parameters: For example, optimization methods GD The step size of varies
• diversity by algorithmic randomness： For example, the model algorithm has its own randomness
• diversity by data randomness

Bootstrap Aggregation

Starting from data , If you can get a lot of diverse data sets $D_t$ To train a $g_t$ Just fine . Data resampling can be used to obtain simulated $D_t$：

1. The original size is $N$ Data set of $\mathcal{D}$ On , There is a sample put back $N^{\prime }$ Get the simulation data set for the second time ${\mathcal{D}}_t\to$ This step is Bootstrap operation
2. adopt $\mathcal{A}\left({\tilde{\mathcal{D}}}_t\right)$ obtain $g_t$, Then use the mean value fusion to obtain : $G=\mathrm{Uniform}\left(\left\{g_t\right\}\right)$ .

Boostrap The premise of reasonable method is ： Diversity of data sets and base algorithms $\mathcal{A}$ Sensitive to random data .

Adaptive Boosting （AdaBoost ） Actually from Bagging At the heart of bootstrap A fusion algorithm based on , Here is a detailed introduction .

AdaBoost

AdaBoost The core idea of is that the data of all current model misclassifications will be strengthened , Train the next weak classifier . Finally all weak classifiers vote . A classic diagram ：

Simple diagram of algorithm flow ：

Algorithm flow

To sum up the problem of binary classification ：

Enter as sample set $D=\left\{\left(x,y_1\right),\left(x_2,y_2\right),\dots \left(x_n,y_n\right)\right\}$,, Weak learner algorithm , Number of weak learner iterations $T$.

The output is the final strong learner $G(x)$.

1. The initialization sample set weight is

$${\mathbf{u}}^{(1)}=\left[\frac{1}{N},\frac{1}{N},\cdots ,\frac{1}{N}\right]$$

2. about $t=1,2,...,T$：

   (a) Use with weights ${\mathbf{u}}^{(t)}$ To train the data , Get the weak learner $g_t(x)$

   (b) Calculation $g_t(x)$ Classification error rate
   $${ϵ}_t=\frac{{\sum }_{n=1}^N{u}_n^{(t)}[y_n\ne g_t\left({\mathbf{x}}_n\right)]}{{\sum }_{n=1}^N{u}_n^{(t)}}$$
   Update the weight distribution of the sample set ： Samples of classification pairs , The weight $u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot \sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}$; Misclassified samples , The weight $u_n^{(t+1)}\leftarrow u_n^{(t)}/\sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}$

   (d) Calculate the coefficients of weak classifiers ：
   $${\alpha }_t=\ln \left(\sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}\right)$$

3. The final classifier is ：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{\alpha }_t{g}_t(\mathbf{x})\right)$$

The weakest classifier here can be a decision stump（ Single level decision tree ）, There are only three parameters ： Select a feature $i$, Set a threshold $\theta$, Determine what kind of threshold is $s$.