當(dāng)我們想要購(gòu)買一個(gè)電腦時(shí)，我們不會(huì)僅僅聽(tīng)信銷售員的一面之詞就購(gòu)買，因?yàn)橐粋€(gè)人的意見(jiàn)是比較主觀的，但是如果詢問(wèn)5個(gè)人，例如同事或者你的朋友，甚至更多人，他們大多都推薦同款商品，那基本差不到哪去。機(jī)器學(xué)習(xí)中的集成學(xué)習(xí)也是類似的思路，它可以結(jié)合多種模型來(lái)提升整體的性能。

1. 集成學(xué)習(xí)Ensemble learning

集成學(xué)習(xí)通過(guò)構(gòu)建并結(jié)合多個(gè)學(xué)習(xí)器machine來(lái)完成學(xué)習(xí)任務(wù)，有時(shí)也被稱為多分類系統(tǒng)multi-classifier system、基于委員會(huì)的學(xué)習(xí)committee-based learning等。它由一系列的個(gè)體學(xué)習(xí)器組成individual learner或者稱為基學(xué)習(xí)器based learner,再由不同的策略結(jié)合在一起，結(jié)合后?？色@得比單一學(xué)習(xí)器更好的泛化性能。

弱學(xué)習(xí)器 Weak learner: 指其泛化性能略優(yōu)于隨機(jī)猜測(cè)的學(xué)習(xí)器 e.g. 二分類問(wèn)題上精度略高于50%。

在集成學(xué)習(xí)中，很多時(shí)候使用弱學(xué)習(xí)器作為基學(xué)習(xí)器。

集成學(xué)習(xí)

集成學(xué)習(xí)方法大致可以分成兩大類：

1. 個(gè)體學(xué)習(xí)器之間不存在強(qiáng)依賴關(guān)系，其代表為Bagging 和隨機(jī)森林 Random Forest?

2. 個(gè)體學(xué)習(xí)器之間存在強(qiáng)依賴關(guān)系，其代表為Boosting

2. Bagging?

Wiki: Baggin 又名 Boostrap aggregating, 是機(jī)器學(xué)習(xí)中的一種擊沉學(xué)習(xí)算法，它可與其他分類、回歸算法結(jié)合，提高其準(zhǔn)確率、穩(wěn)定性的同時(shí)，通過(guò)降低結(jié)果的方差，避免過(guò)擬合的發(fā)生。

自助抽樣法 Bootstrapping,?是一種從給定訓(xùn)練集中有放回的均勻抽樣，也就是說(shuō)，每當(dāng)選中一個(gè)樣本，它會(huì)重新放回到訓(xùn)練集中，可能會(huì)被重新抽到。一般子集的大小與原始集的大小相同。

一、 Bagging算法流程：

對(duì)于有m個(gè)樣本的數(shù)據(jù)集（假設(shè)有T個(gè)基學(xué)習(xí)器）

1. 根據(jù) Bootstrap方法重新采樣?

每次選取1個(gè)樣本進(jìn)入采樣集，將其放回訓(xùn)練集，反復(fù)操作m次，得到一組樣本集。因?yàn)槲覀冃枰?xùn)練T個(gè)基學(xué)習(xí)器，所以生成T個(gè)分別包含m個(gè)樣本的數(shù)據(jù)集（當(dāng)然樣本數(shù)量也可以少于m）。注意，T個(gè)訓(xùn)練集之間是獨(dú)立的。

取樣

2. 基于每個(gè)數(shù)據(jù)集，訓(xùn)練一個(gè)基學(xué)習(xí)器（weak learner），訓(xùn)練過(guò)程同時(shí)運(yùn)行，且彼此獨(dú)立

3. 結(jié)合這些基學(xué)習(xí)器的學(xué)習(xí)結(jié)果，在結(jié)合過(guò)程中，

????對(duì)于分類問(wèn)題，Bagging通常使用投票法，如果投票結(jié)果一樣，則隨機(jī)選擇一個(gè)

????對(duì)于回歸問(wèn)題，則采用平均法，即平均多個(gè)模型結(jié)果

Bagging 過(guò)程（圖片來(lái)源于機(jī)器之心）

3. Boosting

Boosting是另外一種集成學(xué)習(xí)方法，它可以將弱學(xué)習(xí)器通過(guò)加權(quán)和提升為強(qiáng)學(xué)習(xí)器。

$\hat{f}(\boldsymbol{x})=\sum_{i=1}^{N} \alpha_{i} \hat{h}_{i}(\boldsymbol{x})$ ， $\hat{h}_{i}(\boldsymbol{x})$ 代表每個(gè)弱學(xué)習(xí)器模型， $\alpha_{i}$ 是其對(duì)應(yīng)模型的系數(shù)。

一、 Boosting算法流程：

????1.先從初始訓(xùn)練集中訓(xùn)練出一個(gè)基學(xué)習(xí)器 $h_i(x)$ 與其系數(shù) $\alpha_{i}$ ，再根據(jù)其表現(xiàn)對(duì)訓(xùn)練樣本的權(quán)重 $w_{i}^{\mu}$ 進(jìn)行調(diào)整

????2. 基于調(diào)整后的訓(xùn)練樣本訓(xùn)練下一個(gè)基學(xué)習(xí)器 $h_{i+1}(x)$ 與基學(xué)習(xí)器的系數(shù) $\alpha_{i+1}$ ,并得到新的樣本權(quán)重

????3. 重復(fù)進(jìn)行，直到訓(xùn)練完事先指定的值N

????4. 最終將這N個(gè)基學(xué)習(xí)器進(jìn)行加權(quán)結(jié)合?

主流的Boosting 算法有：AdaBoost（Adaptive Boosting，自適應(yīng)增強(qiáng)算法）。

（下面介紹的AdaBoost有助于更好地理解Boosting）

Bagging 和Boosting的區(qū)別

樣本選擇

????Bagging: 訓(xùn)練集是從原始數(shù)據(jù)集中有放回地選取，每一輪得到的數(shù)據(jù)集是獨(dú)立的。采用均勻取樣，每個(gè)樣本的權(quán)重都相等。

????Boosting: 每一輪的數(shù)據(jù)集是不變的，但是數(shù)據(jù)對(duì)于的權(quán)重是變化的。通過(guò)錯(cuò)誤率調(diào)整樣本權(quán)重，錯(cuò)誤率越高，權(quán)重越大。

基學(xué)習(xí)器

? ? Bagging: 基學(xué)習(xí)器可以并行生成，所有基學(xué)習(xí)器的系數(shù)相等。

? ? Boosting: 基學(xué)習(xí)器按順序生成，是串行的，不同的基學(xué)習(xí)器有對(duì)應(yīng)的系數(shù)，對(duì)于分類誤差大的基學(xué)習(xí)器，具有越小的系數(shù)。

4. Bias 和 Variance 方差

Bagging

Bagging對(duì)數(shù)據(jù)重新采樣，并訓(xùn)練不同的基學(xué)習(xí)器，最終結(jié)果是對(duì)這一系列的模型取平均。由于子樣本的相似性，這些基學(xué)習(xí)器具有近似相等的bias和方差variance。每個(gè)子分布 $X_{i}$ 的bias為 $\mu = \mathbb{E}\left[X_{i}\right]$ ,方差為 $\sigma ^{2}$

則bagging后的整體bias： $\mathbb{E}\left[\hat{\mu}_{n}\right]=\mathbb{E}\left[\frac{1}{n} \sum_{i=1}^{n} X_{i}\right]=\frac{1}{n} \sum_{i=1}^{n} \mathbb{E}\left[X_{i}\right]=\frac{1}{n} \sum_{i=1}^{n} \mu=\mu$

Variance方差：

$\begin{aligned} Var=\mathbb{E}\left[\left(\hat{\mu}_{n}-\mu\right)^{2}\right] &=\frac{1}{n^{2}} \mathbb{E}\left[\left(\sum_{i=1}^{n}\left(X_{i}-\mu\right)\right)^{2}\right] \\ & =\frac{1}{n^{2}} \mathbb{E}\left[\sum_{i=1}^{n}\left(X_{i}-\mu\right)^{2}+\sum_{i=1}^{n} \sum_{j=1 \atop j \neq i}^{n}\left(X_{i}-\mu\right)\left(X_{j}-\mu\right)\right] \\ &=\frac{1}{n^{2}} \sum_{i=1}^{n}\left(\mathbb{E}\left[\left(X_{i}-\mu\right)^{2}\right]+\sum_{j=1 \atop j \neq i}^{n} \mathbb{E}\left[\left(X_{i}-\mu\right)(X_{j}-\mu) \right]\right) \\ & \end{aligned}$

令 $\rho=\mathbb{E}\left[\left(X_{i}-\mu\right)\left(X_{j}-\mu\right)\right] / \sigma^{2}$ ，可以認(rèn)為是兩兩分布之間的相關(guān)性，則 $\begin{aligned} Var & =\frac{1}{n^{2}} \sum_{i=1}^{n}\left(\sigma^{2}+\sum_{j=1 \atop j \neq i}^{n} \sigma^{2}\rho\right) \\ &=\frac{1}{n^{2}} n (\sigma^{2}+(n-1)\rho\sigma^{2})=\rho\sigma^{2}+\frac{(1-\rho)\sigma^{2}}{n} \end{aligned}$

因?yàn)樽臃植?img class="math-inline" src="https://math.jianshu.com/math?formula=X_%7Bi%7D" alt="X_{i}" mathimg="1">相關(guān)性較少甚至彼此之間獨(dú)立，即 $\rho$ 很小甚至趨近于0，所以方差趨近于 $\frac{1}{n}\sigma ^{2}$ 。這也說(shuō)明，Bagging可以顯著降低方差,盡管相對(duì)于子分布，整體的bias沒(méi)什么變化。

（方差的推導(dǎo)參考以下公式）

Boosting

Boosting使用forward-stagewise這種貪心法來(lái)最小化損失函數(shù)。每一輪訓(xùn)練都是通過(guò)最小化誤差來(lái)生成基學(xué)習(xí)器，模型的最終結(jié)果也必將獲得較小的bias。由于每一輪的訓(xùn)練都是依賴于上一次的訓(xùn)練結(jié)果，子分布之間存在較強(qiáng)的關(guān)聯(lián)關(guān)系，所以方差不能得到顯著的降低。

5. AdaBoost

AdaBoost，是英文"Adaptive Boosting"（自適應(yīng)增強(qiáng)）的縮寫，是一種用于二分類的集成學(xué)習(xí)算法。它是自適應(yīng)在于：前一個(gè)基本分類器分錯(cuò)的樣本會(huì)得到加強(qiáng)，加權(quán)后的全體樣本再次被用來(lái)訓(xùn)練下一個(gè)基本分類器。同時(shí)，在每一輪中加入一個(gè)新的弱分類器，直到達(dá)到某個(gè)預(yù)定的足夠小的錯(cuò)誤率或達(dá)到預(yù)先指定的最大迭代次數(shù)。

假如對(duì)于二分類任務(wù)，我們的有數(shù)據(jù)集 $\mathcal{D}=\left\{\left(\boldsymbol{x}^{\mu}, y^{\mu}\right) | \mu=1,2, \ldots, m\right\}$ 且 $y^{\mu} \in\{-1,1\}$

第i個(gè)弱分類器的預(yù)測(cè)結(jié)果為 $\hat{h}_{i}\left(\boldsymbol{x}^{\mu}\right) \in\{-1,1\}$

基學(xué)習(xí)器的線性組合為 $C_{n}(\boldsymbol{x})=\alpha_{1} \hat{h}_{1}(\boldsymbol{x})+\alpha_{2} \hat{h}_{2}(\boldsymbol{x})+\cdots+\alpha_{n} \hat{h}_{n}(\boldsymbol{x})$

指數(shù)損失函數(shù)Exponential loss function

它通過(guò)最小化指數(shù)損失來(lái)逐步學(xué)習(xí)

$min \sum_{\mu=1}^{m} \mathrm{e}^{-y^{\mu} C_{n}\left(\boldsymbol{x}^{\mu}\right)}$ ?，其中 $y^{u}$ 為真實(shí)值， $C_{n}(x)$ 為預(yù)測(cè)結(jié)果。

從下圖可以看出，當(dāng)真實(shí)值與預(yù)測(cè)值同號(hào)時(shí)即預(yù)測(cè)正確，損失很??；異號(hào)時(shí)，損失值很大。

誤差函數(shù)

基分類器的系數(shù) $\alpha_{n}$

在每一輪訓(xùn)練中都依次加入一個(gè)新的弱分類器? $C_{n}(\boldsymbol{x})=C_{n-1}(\boldsymbol{x})+\alpha_{n} \hat{h}_{n}(\boldsymbol{x})$

令 $w_{n}^{\mu}=\mathrm{e}^{-y^{\mu} C_{n-1}\left(\boldsymbol{x}^{\mu}\right)}$ ?且 $w_{1}^{\mu}=\frac{1}{m}$ ， $\mu$ 取決于樣本數(shù)， $n$ 取決于迭代數(shù)，即基函數(shù)的數(shù)量

則損失函數(shù)可以化簡(jiǎn)為

$\begin{aligned} l=\left(\alpha_{n}\right) &=\sum_{\mu=1}^{m} \mathrm{e}^{-y^{\mu} C_{n}\left(\boldsymbol{x}^{\mu}\right)}=\sum_{\mu=1}^{m} \mathrm{e}^{-y^{\mu}\left(C_{n-1}\left(\boldsymbol{x}^{\mu}\right)+\alpha_{n} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)\right)} \\ &=\sum_{\mu=1}^{m} w_{n}^{\mu} \mathrm{e}^{-\alpha_{n} y^{\mu} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} \\ & = \sum_{\mu: \boldsymbol{y}^{\mu} \neq \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} ^{m} w_{n}^{\mu} e^{\alpha_{n} } + \sum_{\mu: \boldsymbol{y}^{\mu} = \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} ^{m} w_{n}^{\mu} e^{-\alpha_{n} } \end{aligned}$ ?

$y^{\mu} , h_{n}\in\{-1,1\}$ ,分類正確時(shí) $y^{\mu} \hat{h}_{n}=1$ ，即 $\mathrm{e}^{-\alpha_{n} y^{\mu} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}=e^{-\alpha_{n}}$ ；分類錯(cuò)誤則為 $\mathrm{e}^{\alpha_{n} }$ 。用下圖來(lái)解釋則為 $3*\mathrm{e}^{-\alpha_{n} }+2*\mathrm{e}^{\alpha_{n} }$ （當(dāng)然，請(qǐng)不要忽略權(quán)值w）

誤差化簡(jiǎn)

為了最小化損失，對(duì)損失函數(shù)進(jìn)行求導(dǎo)，并讓其為0

$\frac{\partial l}{\partial \alpha_{n}}=\sum_{\mu: y^{\mu} \neq \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}^{\mu} w^{\mu}\mathrm{e}^{\alpha_{n}}-\sum_{\mu: y^{\mu}=\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} w^{\mu}\mathrm{e}^{-\alpha_{n}}=0$ ?可得? $\alpha_{n}=\frac{1}{2} \log \left(\frac{\sum_{\mu: y^{\mu} =\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}{\sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}\right)$ ? ?

每一輪的誤差為? $e_{n}= \sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}$ ,??則 $\alpha_{n}=\frac{1}{2} \log \frac{ 1-e_{n}}{ e_{n}}$

AdaBoost算法步驟：

?1. 初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。每一個(gè)訓(xùn)練樣本最開(kāi)始時(shí)都被賦予相同的權(quán)值：1/m, 即 $D_{1}(x)=\frac{1}{m}$ ,? $D_{1}$ 有m個(gè)樣本，每個(gè)的權(quán)值都為1/m

for n=1,2,...,N do

????2. 基于具有權(quán)值分布 $D_{n}$ 的訓(xùn)練數(shù)據(jù)集進(jìn)行訓(xùn)練，計(jì)算誤差（選擇最小的），從而得到基學(xué)? ? ? ? ?習(xí)器? ??

?????? $e_{n}= \sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}$

????4. 計(jì)算基分類器的系數(shù)，更新模型

? ?????? $\alpha_{n}=\frac{1}{2} \log \left(\frac{\sum_{\mu: y^{\mu} =\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}{\sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}\right)=\frac{1}{2} \log \frac{ 1-e_{n}}{ e_{n}}$

????5. 更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布

? ?????? $w_{n+1}^{\mu}=\frac{w_{n}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{n} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}}{Z_{n}}$ ，即? $D_{n+1} = \left\{ w_{n+1}^{1}, w_{n+1}^{2}.., w_{n+1}^{m}\right\}$

????????其中， $Z_{n}=\sum_{\mu=1}^{m} w_{n+1}^{\mu}$ ,是一個(gè)規(guī)范化因子，來(lái)確保 $D_{n+1}$ 是一個(gè)分布，即確保權(quán)值<=1

6. 得到強(qiáng)分類器

$H(x)=sign(\sum\nolimits_{n=1}^N \alpha_{n}h_{n}(x) )$

AdaBoost方法對(duì)于噪聲數(shù)據(jù)和異常數(shù)據(jù)很敏感。但在一些問(wèn)題中，它不會(huì)很容易出現(xiàn)過(guò)擬合現(xiàn)象。AdaBoost方法中使用的分類器可能很弱，但只要它的分類效果比隨機(jī)好一點(diǎn)（比如兩類問(wèn)題分類錯(cuò)誤率略小于0.5），就能夠改善最終得到的模型。而錯(cuò)誤率高于隨機(jī)分類器的弱分類器也是有用的，因?yàn)樵谧罱K得到的多個(gè)分類器的線性組合中，可以給它們賦予負(fù)系數(shù)，同樣也能提升分類效果。

題目

原始數(shù)據(jù)

由于以上的數(shù)據(jù)可以分成{0 1 2},{3 4 5},{6 7 8},{9}這幾類,所以根據(jù)主觀的感覺(jué)，數(shù)據(jù)的分隔點(diǎn)分別為2.5、5.5、8.5

1. 初始化權(quán)值w1=0.1? $D1=\left\{ 0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1 \right\}$

2. 迭代訓(xùn)練弱分類器

第1次迭代：

? ? （1）閾值T=2.5時(shí)，誤差率為0.3（x>2.5，取值-1，此時(shí){6,7,8}分類錯(cuò)誤）

????????????閾值T=5.5時(shí)，誤差率為0.4（x>5.5，取值-1，此時(shí){0,1,2,9}分類錯(cuò)誤）

????????????閾值T=8.5時(shí)，誤差率為0.3（x>8.5，取值-1，此時(shí){3,4,5}分類錯(cuò)誤）

? ? ? ? ? ? 最小的閾值為0.3，分別為T=2.5 和T=8.5，隨機(jī)取T=2.5，此時(shí)e=0.3, 第一個(gè)基分類器為 $h_{1}(x)=\left\{\begin{array}{ll}{1,} & {x<2.5} \\ {-1,} & {x>2.5}\end{array}\right.$

? ? ? ? （2）計(jì)算第一個(gè)基分類器的系數(shù)

$\alpha_{1}=\frac{1}{2} \log \left(\frac{\sum_{\mu: y^{\mu} =\hat{h}_{1}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}{\sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}\right)= \frac{1}{2} \log \frac{1-e}{e} = 0.4236$

? ? ? ? ? (3)計(jì)算權(quán)值? $w_{2}^{\mu}=\frac{w_{1}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{1} \hat{h}_{1}\left(\boldsymbol{x}^{\mu}\right)}}{Z_{1}}$

? ? ? ? ? ? 錯(cuò)誤的分類，第7個(gè)數(shù)據(jù)即 x=6,它新的權(quán)值為 $w_{2,7}^{\mu}=w_{1,7}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{1} \hat{h}_{1}\left(\boldsymbol{x}^{\mu}\right)} = w_{1,6}^{\mu} \mathrm{e}^{\alpha_{1}}$

????????????正確的分類x=1,? $w_{2,2}^{\mu}=w_{1,2}^{\mu} \mathrm{e}^{-\alpha_{1}}$

? ? ? ? ? ? 對(duì)他們進(jìn)行標(biāo)準(zhǔn)化，即把每個(gè)新的w除以 $Z_{1}$ , $Z_{1}=\sum_{1}^{10} w_{2,i} ^{\mu}$ ,可得

? ?????????? $w_{2,7}^{\mu}=0.1* \mathrm{e}^{\alpha_{1}}/Z_{1}=0.1666$ , $w_{2,2}^{\mu}=0.1* \mathrm{e}^{-\alpha_{1}}/Z_{1}=0.0715$

$D2=\left\{ 0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,\underline{ 0.1666,0.1666,0.1666},0.0715 \right\}$

第2次迭代：? ? ? ?

????（1）閾值T=2.5時(shí)，誤差率為0.1666*3（x>2.5，取值-1，此時(shí){6,7,8}分類錯(cuò)誤）? ? ?

????????????閾值T=5.5時(shí)，誤差率為0.0715*4（x>5.5，取值-1，此時(shí){0,1,2,9}分類錯(cuò)誤）

????????????閾值T=8.5時(shí)，誤差率為0.0715*3（x>8.5，取值-1，此時(shí){3,4,5}分類錯(cuò)誤）

? ? ? ? ? ? 選取最小的閾值T=8.5，e=0.0715*3, 第2個(gè)基分類器為 $h_{2}(x)=\left\{\begin{array}{ll}{1,} & {x<8.5} \\ {-1,} & {x>8.5}\end{array}\right.$

? ? （2）計(jì)算第2個(gè)基分類器的系數(shù)? $\alpha_{2}=\frac{1}{2} \log \frac{ 1-e_{2}}{ e_{2}} = 0.6496$

? ? （3）計(jì)算權(quán)值

? ? ? ? 根據(jù)公式 $w_{3}^{\mu}=\frac{ w_{2}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{2} \hat{h}_{2}\left(\boldsymbol{x}^{\mu}\right)}} {Z_{2}}$ ? $Z_{2}=\sum_{i=1}^{10} w_{3,i} ^{\mu}$ ，可得 $D3=\left\{ 0.0455, 0.0455, 0.0455,\underline{ 0.1666,0.1666,0.1666},0.1060, 0.1060, 0.1060, 0.0455 \right\}$ ,可見(jiàn)被錯(cuò)誤分類的權(quán)值會(huì)被提高