在 Kaggle 及其它機器學習任務中，集成方法非常流行，不論是 XGBoost 還是隨機森林，它們都強大無比。而本文作者從最基礎的 Boosting 概念到 AdaBoost 算法進行了詳細的介紹，並展示瞭如何實現 AdaBoost，這些都是走進集成方法大家族的敲門磚。
最近，Boosting 技術在 Kaggle 競賽以及其它預測分析任務中大行其道。本文將盡可能詳細地介紹有關 Boosting 和 AdaBoost 的相關概念。
本文將涉及：
- 對 bagging（裝袋法）的快速回顧
- bagging 的侷限性
- Boosting 的概念細節
- boosting 的計算效率
- 代碼示例
Bagging 的侷限性
接下來，我們不妨考慮一個二元分類問題。我們把一個觀測結果分類為 0 或 1。儘管這並不是本文的目的，但是為了清晰起見，讓我們回顧一下 Bagging 的概念。
Bagging 指的是一種叫做「Bootstrap Aggregating」（自助聚合）的技術。其實質是選取 T 個 bootstrap 樣本，在每個樣本安裝一個分類器，然後並行訓練模型。通常，在隨機森林中，決策樹是並行訓練的。然後，將所有分類器的結果平均化，得到一個 bagging 分類器：
Bagging 分類器的公式
該過程可以通過以下方式來說明。讓我們考慮 3 個分類器，它們生成一個分類結果，該結果可能是對的也可能是錯的。如果我們繪製 3 個分類器的結果，會有一些區域代表分類器的結果是錯誤的。在下圖中，這樣的區域用紅色表示：
Bagging 適用場景的示例
這個示例可以很好地起到說明作用，其中有一個分類器的結果是錯誤的，而另外兩個分類器的結果是正確的。通過對分類器進行投票，你可以獲得很高的分類準確率。但正如你可能會猜到的那樣，bagging 機制有時並不能很好地起作用，這時所有的分類器都會在同一個區域內獲得錯誤的分類結果。
出於這個原因，對 boosting 方法背後的直觀想法是：
- 我們需要串行訓練模型，而不是並行訓練。
- 每個模型需要重點關注之前的分類器表現不佳的地方。
Boosting 簡介
概念
上述想法可以詮釋為：
- 在整個數據集上訓練模型 h1
- 對 h1 表現較差的區域的數據加權，並在這些數據上訓練模型 h2
- 對 h1 ≠ h2 的區域的數據加權重，並在這些數據上訓練模型 h3
- ...
我們可以串行地訓練這些模型，而不是並行訓練。這是 Boosting 的本質！
Boosting 方法會隨著時間的推移，通過調整誤差度量來訓練一系列低性能算法，稱之為弱學習器。弱學習器指的是那些誤差率略低於 50% 的算法，如下圖所示：
誤差率略低於 50% 的弱分類器
加權誤差
我們如何才能實現這樣的分類器呢？實際上，我們是通過在整個迭代過程中加權誤差做到的。這樣，我們將為之前分類器表現較差的區域賦予更大的權重。
不妨想想二維圖像上的數據點。有些點會被很好地分類，有些則不會。通常，在計算誤差率時，每個誤差的權重為 1/n，其中 n 是待分類的數據點個數。
未加權的誤差
現在讓我們對誤差進行加權！
加權後的誤差
現在，你可能注意到了，我們對沒有被很好地分類的數據點賦予了更高的權重。加權的過程如下圖所示：
加權過程示例
最終，我們希望構建如下圖所示的強分類器：
強分類器
決策樹樁
你可能會問，我們需要實現多少個分類器才能讓整個 Boosting 系統很好地工作呢？在每一步中如何選擇分類器？
答案是所謂的「決策樹樁」！決策樹樁是指一個單層決策樹。主要思想是，我們在每一步都要找到最好的樹樁（即得到最佳的數據劃分），它能夠使整體的誤差最小化。你可以將一個樹樁看做一個測試，其中，我們假設位於樹樁某一側的所有數據點都屬於 1 類，另一側的所有數據點都屬於 0 類。
決策樹樁的組合可能有很多種。接下來，讓我們看看在這個簡單的示例中有多少種樹樁組合？
待劃分的 3 個數據點
實際上，本例中有 12 種樹樁組合！這看起來可能有些令人驚訝，但其實很容易理解。
12 個決策樹樁
我們可以對上面的情況做 12 種可能的「測試」。每條分割線邊上的數字「2」簡單地表示了這樣一個事實：位於分割線某一側的所有點都可能屬於 0 類或 1 類。因此，每條分割線嵌入了 2 個「測試」。
在每一輪迭代 t 中，我們將選擇能夠最好地劃分數據的弱分類器 ht，該分類器能夠最大限度地降低整體誤差率。回想一下，這裡的誤差率是一個經過加權修正之後的誤差率版本，它考慮到了前面介紹的內容。
尋找最佳劃分
如上所述，通過在每輪迭代 t 中識別最佳弱分類器 ht（通常為具有 1 個節點和 2 片葉子的決策樹（決策樹樁））來找到最佳劃分。假設我們試圖預測一個想借錢的人是否會是一個好的還款人：
找出最佳劃分
在這種情況下，t 時刻的最佳劃分是將「支付歷史」作為樹樁，因為這種劃分的加權誤差是最小的。
只需注意，實際上，像這樣的決策樹分類器可能具備比簡單的樹樁更深的結構。這將會是一個超參數。
融合分類器
自然而然地，下一步就應該是將這些分類器融合成一個符號分類器。根據某個數據點處於分割線的哪一側，將其分類為 0 或 1。該過程可以通過如下方式實現：
融合分類器
你發現了可能提升分類器性能的方法嗎？
通過為每個分類器加權，可以避免賦予不同的分類器相同的重要性。
AdaBoost
小結一下
讓我們把到目前為止本文已經介紹過的內容總結在一段小小的偽代碼中。
偽代碼
其中需要記住的關鍵點是：
- Z 是一個常數，其作用是對權重進行歸一化，使得它們加起來等於 1！
- α_t 是應用於每個分類器的權重
大功告成！這種算法就是「AdaBoost」。如果你想充分理解所有的 boosting 方法，那麼這是你需要理解的最重要的算法。
計算
Boosting 算法訓練起來非常快，這太棒了。但是我們考慮到了所有樹樁的可能性並且採用了遞歸的方法計算指數，為什麼它還會訓練地這麼快？
現在，神奇的地方來了！如果我們選擇了恰當的 α_t 和 Z，本該在每一步變化的權重將簡化成如下的簡單形式：
選擇了恰當的α 和 Z 之後得到的權重
這是一個非常強的結論，這與權重應該隨著迭代而變化的說法並不矛盾。因為錯誤分類的訓練樣本數量減少了，它們的總權重仍然是 0.5！
- 無需計算 Z
- 無需計算 α
- 無需計算指數
另外一個小訣竅是：任何試圖將兩個已經被很好地分類的數據點劃分開的分類器都不會是最優的。我們甚至不需要對其進行計算。
動手編程試一下吧！
現在，本文將帶領讀者快速瀏覽一個代碼示例，看看如何在 Python 環境下使用 Adaboost 進行手寫數字識別。
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import cross_val_predict
from sklearn.model_selection import train_test_split
from sklearn.model_selection import learning_curve
from sklearn.datasets import load_digits
首先，載入數據：
dataset = load_digits()
X = dataset['data']
y = dataset['target']
X 包含長度為 64 的數組，它們代表了簡單的 8x8 的平面圖像。使用該數據集的目的是為了完成手寫數字識別任務。下圖為一個給定的手寫數字的示例：
如果我們堅持使用深度為 1 的決策樹分類器（決策樹樁），以下是如何在這種情況下實現 AdaBoost 分類器：
reg_ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1))
scores_ada = cross_val_score(reg_ada, X, y, cv=6)
scores_ada.mean()
這樣得到的分類準確率的結果應該約為 26%，還具有很大的提升空間。其中一個關鍵的參數是序列決策樹分類器的深度。那麼，決策樹的深度如何變化才能提高分類準確率呢？
score = []
for depth in [1,2,10] :
reg_ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=depth))
scores_ada = cross_val_score(reg_ada, X, y, cv=6)
score.append(scores_ada.mean())
在這個簡單的例子中，當決策樹的深度為 10 時，分類器得到了最高的分類準確率 95.8%。
結語
研究人員已經針對 AdaBoost 是否會過擬合進行了深入的探討。近來，AdaBoost 被證明在某些時候會發生過擬合現象，用戶應該意識到這一點。同時，Adaboost 也可以作為迴歸算法使用。
在人臉識別任務中，AdaBoost 被廣泛用於評估視頻中是否存在人臉。本文作者將就此話題在近期內撰寫另外一篇文章！在後續文章中，還將介紹梯度增強方法！
閱讀更多 機器之心 的文章
