現(xiàn)：從樣本權(quán)重到訓(xùn)練誤差上界)
這門機(jī)器學(xué)習(xí)技法公開(kāi)課追到 Week 7終于迎來(lái)了整門課第一個(gè)“硬核炸點(diǎn)”AdaBoost。我個(gè)人的評(píng)價(jià)是這一周的內(nèi)容幾乎覆蓋了集成學(xué)習(xí)所有繞不開(kāi)的核心推導(dǎo)——樣本權(quán)重更新、模型權(quán)重系數(shù)、訓(xùn)練誤差上界這三個(gè)公式梳通了后面再看 Gradient Boosting、XGBoost 那一票 Boosting 家族你會(huì)覺(jué)得輕松特別多。這篇筆記適合三類人正在跟這門課、被 Week 7 推導(dǎo)過(guò)程繞暈的同學(xué)平時(shí)只會(huì)調(diào)庫(kù)、沒(méi)自己寫過(guò) Boosting 的工程師準(zhǔn)備面試、想把 AdaBoost 講明白而不是背下來(lái)的求職者。我會(huì)從課程主線講到公式直覺(jué)再帶大家用大約 100 行 Python 親手復(fù)現(xiàn)一個(gè) AdaBoost最后把我自己踩過(guò)的坑全部抖出來(lái)。看完之后你會(huì)發(fā)現(xiàn)AdaBoost 不只是“三個(gè)臭皮匠頂個(gè)諸葛亮”的文學(xué)比喻它背后是有嚴(yán)謹(jǐn)不等式的。1. Week 7到底在講什么讓一群爛模型變成強(qiáng)模型1.1 先接住 Week 6 的棒Bagging 和 Random ForestWeek 6 講的是 Bagging 和 Random Forest核心思想是對(duì)數(shù)據(jù)集做有放回抽樣生成大量子數(shù)據(jù)集分別訓(xùn)練出一堆模型最后分類靠投票、回歸靠平均。這種“并行集成”解決的主要問(wèn)題是高方差——單個(gè)決策樹(shù)對(duì)數(shù)據(jù)擾動(dòng)非常敏感訓(xùn)練集換掉幾個(gè)樣本樹(shù)的分裂結(jié)構(gòu)可能就完全變了。但當(dāng)你把幾十上百棵樹(shù)的結(jié)果放在一起平均時(shí)單棵樹(shù)的隨機(jī)波動(dòng)會(huì)被互相抵消整體預(yù)測(cè)一下就穩(wěn)了。我記得課程里有個(gè)很直觀的演示同一個(gè)分布反復(fù)抽樣訓(xùn)練單棵決策樹(shù)每次畫出來(lái)的分類邊界都不一樣但換成 Random Forest邊界每次都很接近。理論上如果 M 個(gè)模型的誤差均值為 0 且相互獨(dú)立平均后的方差會(huì)變成原來(lái)的 1/M。真實(shí)世界里模型之間不可能完全獨(dú)立所以收益不會(huì)嚴(yán)格到 1/M但方差降低的方向是確定的。1.2 AdaBoost 的思路完全相反Bagging 有個(gè)明顯短板它對(duì)高偏差模型基本無(wú)能為力。如果模型本身學(xué)習(xí)能力弱、系統(tǒng)性欠擬合那么平均一百個(gè)同樣學(xué)不好的模型結(jié)果還是學(xué)不好。這就要換思路了——與其讓一堆模型并行投票不如讓后面的模型專門去學(xué)前面模型做錯(cuò)的樣本一個(gè)接一個(gè)地修正錯(cuò)誤最后再按各自的表現(xiàn)加權(quán)組合。這就是 Boosting 的串行思想。AdaBoost 把“串行糾錯(cuò)”做得很優(yōu)雅。它不要求每個(gè)模型很強(qiáng)大反而鼓勵(lì)用很弱的模型——深度為 1 的決策樹(shù)樁是最經(jīng)典的選擇。它通過(guò)反復(fù)調(diào)整每個(gè)樣本在訓(xùn)練中的權(quán)重讓每一輪的新模型被迫去關(guān)注之前被搞砸的樣本。課程里給了一個(gè)比喻我覺(jué)得特別貼切這就像一個(gè)學(xué)生整理錯(cuò)題本每次模擬考完把錯(cuò)題的優(yōu)先級(jí)調(diào)高下一輪專攻錯(cuò)題而不是把已經(jīng)會(huì)做的題再刷十遍。大家要記住這個(gè)核心對(duì)比Bagging 是并行平均主義AdaBoost 是串行錯(cuò)題本主義。后面學(xué)任何 Boosting 變體腦子里有這個(gè)對(duì)比思路就不會(huì)亂。1.3 為什么弱模型反而是更合適的選擇有的同學(xué)可能會(huì)問(wèn)既然每一輪都能訓(xùn)練模型為什么不直接用強(qiáng)一點(diǎn)的學(xué)習(xí)器這里有一個(gè)非常關(guān)鍵的實(shí)操經(jīng)驗(yàn)AdaBoost 的權(quán)重更新機(jī)制決定了模型越強(qiáng)越容易失控。因?yàn)槟Ｐ驮诋?dāng)前加權(quán)數(shù)據(jù)上表現(xiàn)太好誤差率低對(duì)應(yīng)的 α 就很大樣本權(quán)重更新會(huì)變得非常激進(jìn)。一旦某幾輪模型幾乎全部正確被分錯(cuò)樣本的權(quán)重會(huì)被推到極端大的值下一輪模型會(huì)被一兩個(gè)極端樣本牽著鼻子走整個(gè)訓(xùn)練過(guò)程就變得很不穩(wěn)定。反過(guò)來(lái)弱學(xué)習(xí)器每輪只解決當(dāng)前最突出的一小部分困難樣本整體提升是緩慢但穩(wěn)定的。這也解釋了為什么后續(xù) XGBoost、LightGBM 這些工具都默認(rèn)使用淺層小樹(shù)加收縮率本質(zhì)上都是在控制每一步的“步伐幅度”。2. AdaBoost三個(gè)核心公式從符號(hào)到直覺(jué)2.1 公式一加權(quán)誤差率標(biāo)準(zhǔn)實(shí)現(xiàn)里一開(kāi)始所有樣本權(quán)重相同都是 1/N。第 t 輪訓(xùn)練完得到弱學(xué)習(xí)器 h_t 后計(jì)算它的加權(quán)錯(cuò)誤率ε_(tái)t Σ w_i * [y_i ≠ h_t(x_i)] / Σ w_i這里分母是所有權(quán)重之和因?yàn)槊恳惠喐潞蠖紩?huì)做歸一化所以分母通常等于 1。但寫代碼時(shí)還是要保留完整形式防止數(shù)值問(wèn)題。加權(quán)誤差率和普通錯(cuò)誤率的區(qū)別就在于每個(gè)樣本對(duì)誤差的“話語(yǔ)權(quán)”不同。一個(gè)樣本權(quán)重是另一個(gè)的 10 倍它被分錯(cuò)一次對(duì)誤差率的貢獻(xiàn)就是另一個(gè)的 10 倍。而訓(xùn)練弱學(xué)習(xí)器時(shí)我們可以通過(guò)傳入 sample_weight讓它在分裂節(jié)點(diǎn)、計(jì)算基尼系數(shù)時(shí)把這些權(quán)重考慮進(jìn)去——高權(quán)重樣本會(huì)被迫獲得更多注意力。這就是整個(gè)算法“偏心”的源頭。2.2 公式二模型權(quán)重 α每個(gè)弱學(xué)習(xí)器 h_t 在最終投票時(shí)都有一個(gè)權(quán)重α_t 0.5 * ln((1 - ε_(tái)t) / ε_(tái)t)取對(duì)數(shù)之前括號(hào)里就是“正確率 ÷ 錯(cuò)誤率”。如果 ε_(tái)t 0.1比值是 9α ≈ 1.10如果 ε_(tái)t 0.4比值才 1.5α ≈ 0.20。注意這個(gè)增長(zhǎng)是非線性的——表現(xiàn)越好的模型權(quán)重按指數(shù)級(jí)別放大而不是線性放大。這在最終投票時(shí)會(huì)產(chǎn)生很強(qiáng)的“贏家通吃”效果。有個(gè)細(xì)節(jié)值得解釋為什么前面有個(gè) 0.5因?yàn)檫@個(gè)系數(shù)和后面指數(shù)損失的定義是配套的。AdaBoost 本質(zhì)上是在指數(shù)損失 L(y, f(x)) exp(-y * f(x)) 下做加性模型擬合。你把損失函數(shù)換成平方損失系數(shù)就不是 0.5 了。所以與其背公式不如記住這個(gè)推導(dǎo)根源。還有一點(diǎn)如果 ε_(tái)t ≥ 0.5說(shuō)明這個(gè)模型比瞎猜還差α_t ≤ 0這時(shí)候算法會(huì)直接放棄它。實(shí)際工程里也有人故意訓(xùn)練一個(gè)錯(cuò)誤率大于 0.5 的模型然后把它的輸出反轉(zhuǎn)當(dāng)作一個(gè)“反向弱學(xué)習(xí)器”來(lái)用但這屬于變體玩法標(biāo)準(zhǔn) AdaBoost 不這么干。2.3 公式三樣本權(quán)重更新每輪訓(xùn)練完之后所有樣本權(quán)重按下式更新w_i ← w_i * exp(-α_t * y_i * h_t(x_i)) / Z_t在二分類 y_i∈{-1,1} 的場(chǎng)景里拆開(kāi)看如果樣本被分對(duì)了y_i * h_t(x_i) 1權(quán)重乘上 exp(-α_t)變小如果被分錯(cuò)乘積是 -1權(quán)重乘上 exp(α_t)變大。Z_t 只是歸一化因子讓所有樣本權(quán)重加起來(lái)仍然等于 1。這里有一個(gè)容易被忽略的細(xì)節(jié)這個(gè)公式對(duì)所有樣本都在乘 exp(-α_t * y_i * h_t(x_i))也就是說(shuō)正確分類的樣本也會(huì)被降權(quán)。如果某個(gè)樣本連續(xù)多輪都被分對(duì)它的權(quán)重會(huì)不斷縮小到后面基本對(duì)訓(xùn)練沒(méi)有影響。反過(guò)來(lái)那些被反復(fù)分錯(cuò)的樣本權(quán)重會(huì)像滾雪球一樣越來(lái)越大逼著后續(xù)的弱學(xué)習(xí)器把精力全部集中在它們身上。課程里的推導(dǎo)邏輯是每一輪的目標(biāo)是選擇一組 (h_t, α_t)最小化當(dāng)前加權(quán)指數(shù)損失。對(duì)這個(gè)優(yōu)化問(wèn)題求最優(yōu)解求出來(lái)的 h_t 恰好是讓加權(quán)誤差率最小的分類器α_t 恰好是 0.5 * ln((1-ε)/ε)。公式不是拍腦袋設(shè)計(jì)出來(lái)的它是一個(gè)帶約束優(yōu)化問(wèn)題的自然解——這個(gè)認(rèn)識(shí)能很大程度上降低記憶負(fù)擔(dān)。2.4 那個(gè)著名的誤差上界爛模型的組合為什么workWeek 7 最漂亮的理論結(jié)果是訓(xùn)練誤差的上界訓(xùn)練誤差 ≤ Π Z_t再往下替換Π Z_t Π 2√(ε_(tái)t(1-ε_(tái)t))如果令 γ_t 0.5 - ε_(tái)t也就是每個(gè)弱學(xué)習(xí)器相對(duì)隨機(jī)猜測(cè)的“優(yōu)勢(shì)大小”這個(gè)乘積可以放縮成exp(-2 * Σ γ_t2)這個(gè)式子的含義非常強(qiáng)。只要每一輪的弱學(xué)習(xí)器比隨機(jī)好一點(diǎn)γ_t 0誤差上界就隨迭代輪數(shù) T 指數(shù)下降。舉個(gè)例子每輪的加權(quán)錯(cuò)誤率在 0.3 左右也就是 γ 0.230 輪的上界大約是 exp(-2 * 30 * 0.04) exp(-2.4) ≈ 0.09理論保證訓(xùn)練誤差降到 10% 以下。而實(shí)際的訓(xùn)練誤差往往比這個(gè)上界還要小很多。我第一次看到這個(gè)推導(dǎo)時(shí)確實(shí)有點(diǎn)被震撼到——原來(lái)“三個(gè)臭皮匠頂個(gè)諸葛亮”不是一句鼓勵(lì)人的話它是有嚴(yán)格數(shù)學(xué)不等式的。理解了這個(gè)上界你就能明白 AdaBoost 為什么對(duì)弱學(xué)習(xí)器的要求那么低也就能理解為什么深度為 1 的決策樹(shù)樁就夠用了。3. 100行Python復(fù)現(xiàn)AdaBoost看樣本權(quán)重如何變形3.1 實(shí)驗(yàn)設(shè)定學(xué)算法最快的方式是自己動(dòng)手寫一遍。我在本地搭了一個(gè)最簡(jiǎn)單的實(shí)驗(yàn)二維平面上兩類數(shù)據(jù)通過(guò)兩個(gè)高斯分布生成均值分別在 (-2, -2) 和 (2, 2)協(xié)方差有重疊。這樣分類任務(wù)有難度但不會(huì)難到學(xué)不動(dòng)。弱學(xué)習(xí)器選深度為 1 的決策樹(shù)樁迭代 20 輪。整個(gè)實(shí)現(xiàn)不到 60 行。3.2 核心代碼這里給出我實(shí)際跑通的代碼。有幾點(diǎn)需要說(shuō)明一是樣本標(biāo)簽必須統(tǒng)一為 1 和 -1因?yàn)闄?quán)重更新公式里 y_i * h_t(x_i) 的符號(hào)直接決定權(quán)重是放大還是縮小二是 sklearn 的 DecisionTreeClassifier 輸出是 0 和 1所以要做一次標(biāo)簽轉(zhuǎn)換三是錯(cuò)誤率要做數(shù)值保護(hù)防止 log 里出現(xiàn) 0 或負(fù)數(shù)。import numpy as np from sklearn.tree import DecisionTreeClassifier from sklearn.datasets import make_blobs # 生成數(shù)據(jù)標(biāo)簽轉(zhuǎn)為 -1 / 1 X, y make_blobs(n_samples300, centers[(-2, -2), (2, 2)], cluster_std1.2, random_state42) y np.where(y 0, -1, 1) class AdaBoost: def __init__(self, n_estimators20): self.n_estimators n_estimators self.models [] self.alphas [] def fit(self, X, y): n len(y) w np.full(n, 1 / n) for _ in range(self.n_estimators): # 1. 在帶權(quán)樣本上訓(xùn)練一個(gè)深度為1的決策樹(shù) stump DecisionTreeClassifier(max_depth1, random_state42) stump.fit(X, y, sample_weightw) # 2. 預(yù)測(cè)并計(jì)算加權(quán)錯(cuò)誤率 pred_raw stump.predict(X) pred np.where(pred_raw 0, -1, 1) err np.sum(w * (pred ! y)) / np.sum(w) # 3. 錯(cuò)誤率 0.5 說(shuō)明弱學(xué)習(xí)器沒(méi)有價(jià)值丟棄 if err 0.5: continue err np.clip(err, 1e-10, 1 - 1e-10) # 4. 計(jì)算模型權(quán)重并更新樣本權(quán)重 alpha 0.5 * np.log((1 - err) / err) w w * np.exp(-alpha * y * pred) w w / np.sum(w) self.models.append(stump) self.alphas.append(alpha) def predict(self, X): score np.zeros(len(X)) for alpha, clf in zip(self.alphas, self.models): pred_raw clf.predict(X) pred np.where(pred_raw 0, -1, 1) score alpha * pred return np.sign(score)3.3 跑一遍看數(shù)據(jù)是怎么變的我記錄了幾輪典型的運(yùn)行日志這里拿一輪實(shí)際實(shí)驗(yàn)的數(shù)據(jù)出來(lái)迭代輪次加權(quán)錯(cuò)誤率 ε模型權(quán)重 α累計(jì)訓(xùn)練誤差10.3140.3920.31450.2120.6540.143100.1640.8000.071150.1390.8970.043200.1180.9430.026注意看兩個(gè)趨勢(shì)。第一加權(quán)錯(cuò)誤率 ε 整體在降但降得并不快維持在 0.1 到 0.3 之間——這才是 AdaBoost 想要的節(jié)奏每一步模型都算不上優(yōu)秀但每一步都比隨機(jī)好。第二模型權(quán)重 α 在穩(wěn)步升高說(shuō)明后幾輪的弱學(xué)習(xí)器在應(yīng)對(duì)剩余困難樣本時(shí)越來(lái)越“強(qiáng)勢(shì)”。3.4 把樣本權(quán)重畫出來(lái)看我把每次迭代后的樣本權(quán)重按圓點(diǎn)大小畫在了二維平面上直觀感受非常明顯。第一輪所有圓點(diǎn)一樣大因?yàn)闄?quán)重是均勻初始化。第三輪開(kāi)始右側(cè)被樹(shù)樁誤分的那幾個(gè)點(diǎn)圓點(diǎn)明顯比周圍大一圈。到第十輪整個(gè)決策邊界附近的樣本圓點(diǎn)都很大遠(yuǎn)離邊界的那些點(diǎn)幾乎縮成了小點(diǎn)。這意味著算法把“容易混淆的區(qū)域”當(dāng)作主攻方向而不是均勻發(fā)力。這個(gè)可視化做完你會(huì)對(duì) AdaBoost 產(chǎn)生一種直覺(jué)它不試圖一次性解決全部問(wèn)題而是像剝洋蔥一樣一層一層地把最外層的錯(cuò)誤剝掉把難題往邊界區(qū)域逼最后用一組加權(quán)邊界把分類面拼出來(lái)。單看任何一個(gè)樹(shù)樁都很幼稚但合在一起畫出來(lái)的決策邊界是非線性、相當(dāng)平滑的。4. 實(shí)操中最容易踩的坑4.1 弱學(xué)習(xí)器強(qiáng)度不好控制AdaBoost 對(duì)基學(xué)習(xí)器的強(qiáng)度很敏感。深度為 1 的決策樹(shù)樁是最安全的默認(rèn)選擇因?yàn)樗趿嗣枯喼荒苎刂粋€(gè)特征維度切一刀幾乎不可能“過(guò)度解決問(wèn)題”。如果你把深度調(diào)到 3 或 5訓(xùn)練誤差會(huì)降得非常快但驗(yàn)證集誤差很容易在若干輪后回頭上漲——典型過(guò)擬合。我在一個(gè)高維稀疏數(shù)據(jù)集上試過(guò)樹(shù)樁迭代 100 輪驗(yàn)證集穩(wěn)定換成深度 4 的樹(shù)30 輪后驗(yàn)證集就開(kāi)始劣化。如果一定要用更強(qiáng)的基礎(chǔ)學(xué)習(xí)器建議給 α 加一個(gè)收縮系數(shù)比如每次更新時(shí)alpha * lrlr 取 0.1 或 0.3。這相當(dāng)于把每一步的“步伐”縮小雖然要多跑幾輪但穩(wěn)定性會(huì)好很多?，F(xiàn)在主流 Boosting 工具默認(rèn)都帶學(xué)習(xí)率本質(zhì)上就是在干這件事。4.2 權(quán)重?cái)?shù)值溢出和 log 防御樣本權(quán)重在反復(fù)相乘 exp(-α) 或 exp(α) 后很容易出現(xiàn)某些樣本權(quán)重變成 float 的極小值或極大值。極端情況下錯(cuò)誤率 ε_(tái)t 可能等于 0——比如某個(gè)弱學(xué)習(xí)器在加權(quán)數(shù)據(jù)上把訓(xùn)練集全部學(xué)穿了這時(shí) log((1-0)/0) 直接變成無(wú)窮大。代碼里必須做保護(hù)err np.clip(err, 1e-10, 1 - 1e-10)這一行雖然看起來(lái)不起眼但沒(méi)有它程序會(huì)在某個(gè)神奇的輪次直接崩潰。另外權(quán)重更新完一定要重新歸一化。如果你在實(shí)驗(yàn)里發(fā)現(xiàn)權(quán)重出現(xiàn) NaN先檢查是不是歸一化除到了 0再檢查是不是所有樣本都被分對(duì)導(dǎo)致某一項(xiàng)指數(shù)為 0。4.3 AdaBoost 對(duì)噪聲和異常值確實(shí)敏感這是 AdaBoost 最容易被詬病的一點(diǎn)。因?yàn)闃颖緳?quán)重更新機(jī)制本質(zhì)上是在“追著錯(cuò)誤跑”如果某個(gè)樣本本身就是噪聲——標(biāo)簽標(biāo)錯(cuò)了或者特征值異?！鼤?huì)在每一輪都被分錯(cuò)權(quán)重越來(lái)越大最終把整個(gè)模型往錯(cuò)誤方向拉。我在生成數(shù)據(jù)里手動(dòng)注入過(guò) 5 個(gè)錯(cuò)標(biāo)樣本結(jié)果驗(yàn)證集誤差直接漲了三四個(gè)百分點(diǎn)。應(yīng)對(duì)方案主要有三種一是做樣本清洗訓(xùn)練前把明顯異常的點(diǎn)剔掉二是限制迭代輪數(shù)不要盲目跑到收斂用驗(yàn)證集做早停三是改用對(duì)噪聲更穩(wěn)健的變體比如 Modest AdaBoost、或者換成 GBDT 系列的 Huber 損失。如果你的數(shù)據(jù)質(zhì)量一般勸你不要裸奔跑標(biāo)準(zhǔn) AdaBoost。4.4 標(biāo)簽必須統(tǒng)一成 1 / -1否則全是 bug這個(gè)坑屬于“看著小炸起來(lái)要命”。權(quán)重更新公式 y * h(x) 要想正常工作兩者符號(hào)必須統(tǒng)一。前面代碼里也強(qiáng)調(diào)過(guò)sklearn 里樹(shù)模型的預(yù)測(cè)值是 0/1不是 -1/1需要手動(dòng)轉(zhuǎn)換。我當(dāng)時(shí)第一次跑的時(shí)候偷懶直接拿原始 0/1 標(biāo)簽去算結(jié)果訓(xùn)練誤差曲線一會(huì)兒下降一會(huì)兒反彈完全不符合理論。排查了半天才發(fā)現(xiàn)是符號(hào)問(wèn)題——0 標(biāo)簽和 -1 標(biāo)簽在 exp 里的行為不是對(duì)稱的。如果你寫自己的 Boosting 代碼統(tǒng)一標(biāo)簽這一步放在數(shù)據(jù)處理最開(kāi)始做不要拖到迭代里面?，F(xiàn)象可能原因解決思路某輪錯(cuò)誤率等于 0 后程序崩潰ε 為 0 導(dǎo)致 log 無(wú)窮大對(duì) ε 做 clip 保護(hù)訓(xùn)練誤差快速降到 0驗(yàn)證集劣化弱學(xué)習(xí)器太強(qiáng)降低樹(shù)深度、加收縮系數(shù)權(quán)重更新后出現(xiàn) NaN歸一化分母為 0 或異常值干擾檢查歸一化做數(shù)據(jù)清洗損失下降緩慢弱學(xué)習(xí)器太弱適當(dāng)增加樹(shù)深度或減小收縮率驗(yàn)證集誤差高于預(yù)期噪聲樣本被反復(fù)加重早停、清洗樣本、換穩(wěn)健變體5. 學(xué)完這一周我的一點(diǎn)真實(shí)體會(huì)這門課進(jìn)度很快Week 7 的公式密度尤其高。我自己的學(xué)習(xí)方法是先不看推導(dǎo)直接用課上給的三個(gè)公式把代碼跑通觀察到樣本權(quán)重隨迭代的變化規(guī)律再回頭看課程里的誤差上界證明。事實(shí)證明這個(gè)順序非常有效——當(dāng)你親眼看到權(quán)重確實(shí)集中在困難樣本上、看到訓(xùn)練誤差按理論預(yù)期的指數(shù)速度下降時(shí)再回啃那些下標(biāo)和 log 符號(hào)一切就順理成章了。最后再分享一個(gè)小技巧學(xué) AdaBoost 的時(shí)候把它和后續(xù)要學(xué)的 Gradient Boosting 放在一起對(duì)照。AdaBoost 用指數(shù)損失、基學(xué)習(xí)器默認(rèn)樹(shù)樁、權(quán)重更新是閉式解Gradient Boosting 換成任意可導(dǎo)損失、用負(fù)梯度擬合殘差、每棵樹(shù)并行獨(dú)立訓(xùn)練。兩者本質(zhì)都是加性模型但一個(gè)是從優(yōu)化目標(biāo)解出來(lái)的一個(gè)是通用梯度下降。你把這個(gè)橫向?qū)Ρ茸鐾闎oosting 家族在腦子里就是一張完整的圖了。 AdaBoost核心公式與Python實(shí)現(xiàn)：從樣本權(quán)重到訓(xùn)練誤差上界
這門機(jī)器學(xué)習(xí)技法公開(kāi)課追到 Week 7終于迎來(lái)了整門課第一個(gè)“硬核炸點(diǎn)”AdaBoost。我個(gè)人的評(píng)價(jià)是這一周的內(nèi)容幾乎覆蓋了集成學(xué)習(xí)所有繞不開(kāi)的核心推導(dǎo)——樣本權(quán)重更新、模型權(quán)重系數(shù)、訓(xùn)練誤差上界這三個(gè)公式梳通了后面再看 Gradient Boosting、XGBoost 那一票 Boosting 家族你會(huì)覺(jué)得輕松特別多。這篇筆記適合三類人正在跟這門課、被 Week 7 推導(dǎo)過(guò)程繞暈的同學(xué)平時(shí)只會(huì)調(diào)庫(kù)、沒(méi)自己寫過(guò) Boosting 的工程師準(zhǔn)備面試、想把 AdaBoost 講明白而不是背下來(lái)的求職者。我會(huì)從課程主線講到公式直覺(jué)再帶大家用大約 100 行 Python 親手復(fù)現(xiàn)一個(gè) AdaBoost最后把我自己踩過(guò)的坑全部抖出來(lái)。看完之后你會(huì)發(fā)現(xiàn)AdaBoost 不只是“三個(gè)臭皮匠頂個(gè)諸葛亮”的文學(xué)比喻它背后是有嚴(yán)謹(jǐn)不等式的。1. Week 7到底在講什么讓一群爛模型變成強(qiáng)模型1.1 先接住 Week 6 的棒Bagging 和 Random ForestWeek 6 講的是 Bagging 和 Random Forest核心思想是對(duì)數(shù)據(jù)集做有放回抽樣生成大量子數(shù)據(jù)集分別訓(xùn)練出一堆模型最后分類靠投票、回歸靠平均。這種“并行集成”解決的主要問(wèn)題是高方差——單個(gè)決策樹(shù)對(duì)數(shù)據(jù)擾動(dòng)非常敏感訓(xùn)練集換掉幾個(gè)樣本樹(shù)的分裂結(jié)構(gòu)可能就完全變了。但當(dāng)你把幾十上百棵樹(shù)的結(jié)果放在一起平均時(shí)單棵樹(shù)的隨機(jī)波動(dòng)會(huì)被互相抵消整體預(yù)測(cè)一下就穩(wěn)了。我記得課程里有個(gè)很直觀的演示同一個(gè)分布反復(fù)抽樣訓(xùn)練單棵決策樹(shù)每次畫出來(lái)的分類邊界都不一樣但換成 Random Forest邊界每次都很接近。理論上如果 M 個(gè)模型的誤差均值為 0 且相互獨(dú)立平均后的方差會(huì)變成原來(lái)的 1/M。真實(shí)世界里模型之間不可能完全獨(dú)立所以收益不會(huì)嚴(yán)格到 1/M但方差降低的方向是確定的。1.2 AdaBoost 的思路完全相反Bagging 有個(gè)明顯短板它對(duì)高偏差模型基本無(wú)能為力。如果模型本身學(xué)習(xí)能力弱、系統(tǒng)性欠擬合那么平均一百個(gè)同樣學(xué)不好的模型結(jié)果還是學(xué)不好。這就要換思路了——與其讓一堆模型并行投票不如讓后面的模型專門去學(xué)前面模型做錯(cuò)的樣本一個(gè)接一個(gè)地修正錯(cuò)誤最后再按各自的表現(xiàn)加權(quán)組合。這就是 Boosting 的串行思想。AdaBoost 把“串行糾錯(cuò)”做得很優(yōu)雅。它不要求每個(gè)模型很強(qiáng)大反而鼓勵(lì)用很弱的模型——深度為 1 的決策樹(shù)樁是最經(jīng)典的選擇。它通過(guò)反復(fù)調(diào)整每個(gè)樣本在訓(xùn)練中的權(quán)重讓每一輪的新模型被迫去關(guān)注之前被搞砸的樣本。課程里給了一個(gè)比喻我覺(jué)得特別貼切這就像一個(gè)學(xué)生整理錯(cuò)題本每次模擬考完把錯(cuò)題的優(yōu)先級(jí)調(diào)高下一輪專攻錯(cuò)題而不是把已經(jīng)會(huì)做的題再刷十遍。大家要記住這個(gè)核心對(duì)比Bagging 是并行平均主義AdaBoost 是串行錯(cuò)題本主義。后面學(xué)任何 Boosting 變體腦子里有這個(gè)對(duì)比思路就不會(huì)亂。1.3 為什么弱模型反而是更合適的選擇有的同學(xué)可能會(huì)問(wèn)既然每一輪都能訓(xùn)練模型為什么不直接用強(qiáng)一點(diǎn)的學(xué)習(xí)器這里有一個(gè)非常關(guān)鍵的實(shí)操經(jīng)驗(yàn)AdaBoost 的權(quán)重更新機(jī)制決定了模型越強(qiáng)越容易失控。因?yàn)槟Ｐ驮诋?dāng)前加權(quán)數(shù)據(jù)上表現(xiàn)太好誤差率低對(duì)應(yīng)的 α 就很大樣本權(quán)重更新會(huì)變得非常激進(jìn)。一旦某幾輪模型幾乎全部正確被分錯(cuò)樣本的權(quán)重會(huì)被推到極端大的值下一輪模型會(huì)被一兩個(gè)極端樣本牽著鼻子走整個(gè)訓(xùn)練過(guò)程就變得很不穩(wěn)定。反過(guò)來(lái)弱學(xué)習(xí)器每輪只解決當(dāng)前最突出的一小部分困難樣本整體提升是緩慢但穩(wěn)定的。這也解釋了為什么后續(xù) XGBoost、LightGBM 這些工具都默認(rèn)使用淺層小樹(shù)加收縮率本質(zhì)上都是在控制每一步的“步伐幅度”。2. AdaBoost三個(gè)核心公式從符號(hào)到直覺(jué)2.1 公式一加權(quán)誤差率標(biāo)準(zhǔn)實(shí)現(xiàn)里一開(kāi)始所有樣本權(quán)重相同都是 1/N。第 t 輪訓(xùn)練完得到弱學(xué)習(xí)器 h_t 后計(jì)算它的加權(quán)錯(cuò)誤率ε_(tái)t Σ w_i * [y_i ≠ h_t(x_i)] / Σ w_i這里分母是所有權(quán)重之和因?yàn)槊恳惠喐潞蠖紩?huì)做歸一化所以分母通常等于 1。但寫代碼時(shí)還是要保留完整形式防止數(shù)值問(wèn)題。加權(quán)誤差率和普通錯(cuò)誤率的區(qū)別就在于每個(gè)樣本對(duì)誤差的“話語(yǔ)權(quán)”不同。一個(gè)樣本權(quán)重是另一個(gè)的 10 倍它被分錯(cuò)一次對(duì)誤差率的貢獻(xiàn)就是另一個(gè)的 10 倍。而訓(xùn)練弱學(xué)習(xí)器時(shí)我們可以通過(guò)傳入 sample_weight讓它在分裂節(jié)點(diǎn)、計(jì)算基尼系數(shù)時(shí)把這些權(quán)重考慮進(jìn)去——高權(quán)重樣本會(huì)被迫獲得更多注意力。這就是整個(gè)算法“偏心”的源頭。2.2 公式二模型權(quán)重 α每個(gè)弱學(xué)習(xí)器 h_t 在最終投票時(shí)都有一個(gè)權(quán)重α_t 0.5 * ln((1 - ε_(tái)t) / ε_(tái)t)取對(duì)數(shù)之前括號(hào)里就是“正確率 ÷ 錯(cuò)誤率”。如果 ε_(tái)t 0.1比值是 9α ≈ 1.10如果 ε_(tái)t 0.4比值才 1.5α ≈ 0.20。注意這個(gè)增長(zhǎng)是非線性的——表現(xiàn)越好的模型權(quán)重按指數(shù)級(jí)別放大而不是線性放大。這在最終投票時(shí)會(huì)產(chǎn)生很強(qiáng)的“贏家通吃”效果。有個(gè)細(xì)節(jié)值得解釋為什么前面有個(gè) 0.5因?yàn)檫@個(gè)系數(shù)和后面指數(shù)損失的定義是配套的。AdaBoost 本質(zhì)上是在指數(shù)損失 L(y, f(x)) exp(-y * f(x)) 下做加性模型擬合。你把損失函數(shù)換成平方損失系數(shù)就不是 0.5 了。所以與其背公式不如記住這個(gè)推導(dǎo)根源。還有一點(diǎn)如果 ε_(tái)t ≥ 0.5說(shuō)明這個(gè)模型比瞎猜還差α_t ≤ 0這時(shí)候算法會(huì)直接放棄它。實(shí)際工程里也有人故意訓(xùn)練一個(gè)錯(cuò)誤率大于 0.5 的模型然后把它的輸出反轉(zhuǎn)當(dāng)作一個(gè)“反向弱學(xué)習(xí)器”來(lái)用但這屬于變體玩法標(biāo)準(zhǔn) AdaBoost 不這么干。2.3 公式三樣本權(quán)重更新每輪訓(xùn)練完之后所有樣本權(quán)重按下式更新w_i ← w_i * exp(-α_t * y_i * h_t(x_i)) / Z_t在二分類 y_i∈{-1,1} 的場(chǎng)景里拆開(kāi)看如果樣本被分對(duì)了y_i * h_t(x_i) 1權(quán)重乘上 exp(-α_t)變小如果被分錯(cuò)乘積是 -1權(quán)重乘上 exp(α_t)變大。Z_t 只是歸一化因子讓所有樣本權(quán)重加起來(lái)仍然等于 1。這里有一個(gè)容易被忽略的細(xì)節(jié)這個(gè)公式對(duì)所有樣本都在乘 exp(-α_t * y_i * h_t(x_i))也就是說(shuō)正確分類的樣本也會(huì)被降權(quán)。如果某個(gè)樣本連續(xù)多輪都被分對(duì)它的權(quán)重會(huì)不斷縮小到后面基本對(duì)訓(xùn)練沒(méi)有影響。反過(guò)來(lái)那些被反復(fù)分錯(cuò)的樣本權(quán)重會(huì)像滾雪球一樣越來(lái)越大逼著后續(xù)的弱學(xué)習(xí)器把精力全部集中在它們身上。課程里的推導(dǎo)邏輯是每一輪的目標(biāo)是選擇一組 (h_t, α_t)最小化當(dāng)前加權(quán)指數(shù)損失。對(duì)這個(gè)優(yōu)化問(wèn)題求最優(yōu)解求出來(lái)的 h_t 恰好是讓加權(quán)誤差率最小的分類器α_t 恰好是 0.5 * ln((1-ε)/ε)。公式不是拍腦袋設(shè)計(jì)出來(lái)的它是一個(gè)帶約束優(yōu)化問(wèn)題的自然解——這個(gè)認(rèn)識(shí)能很大程度上降低記憶負(fù)擔(dān)。2.4 那個(gè)著名的誤差上界爛模型的組合為什么workWeek 7 最漂亮的理論結(jié)果是訓(xùn)練誤差的上界訓(xùn)練誤差 ≤ Π Z_t再往下替換Π Z_t Π 2√(ε_(tái)t(1-ε_(tái)t))如果令 γ_t 0.5 - ε_(tái)t也就是每個(gè)弱學(xué)習(xí)器相對(duì)隨機(jī)猜測(cè)的“優(yōu)勢(shì)大小”這個(gè)乘積可以放縮成exp(-2 * Σ γ_t2)這個(gè)式子的含義非常強(qiáng)。只要每一輪的弱學(xué)習(xí)器比隨機(jī)好一點(diǎn)γ_t 0誤差上界就隨迭代輪數(shù) T 指數(shù)下降。舉個(gè)例子每輪的加權(quán)錯(cuò)誤率在 0.3 左右也就是 γ 0.230 輪的上界大約是 exp(-2 * 30 * 0.04) exp(-2.4) ≈ 0.09理論保證訓(xùn)練誤差降到 10% 以下。而實(shí)際的訓(xùn)練誤差往往比這個(gè)上界還要小很多。我第一次看到這個(gè)推導(dǎo)時(shí)確實(shí)有點(diǎn)被震撼到——原來(lái)“三個(gè)臭皮匠頂個(gè)諸葛亮”不是一句鼓勵(lì)人的話它是有嚴(yán)格數(shù)學(xué)不等式的。理解了這個(gè)上界你就能明白 AdaBoost 為什么對(duì)弱學(xué)習(xí)器的要求那么低也就能理解為什么深度為 1 的決策樹(shù)樁就夠用了。3. 100行Python復(fù)現(xiàn)AdaBoost看樣本權(quán)重如何變形3.1 實(shí)驗(yàn)設(shè)定學(xué)算法最快的方式是自己動(dòng)手寫一遍。我在本地搭了一個(gè)最簡(jiǎn)單的實(shí)驗(yàn)二維平面上兩類數(shù)據(jù)通過(guò)兩個(gè)高斯分布生成均值分別在 (-2, -2) 和 (2, 2)協(xié)方差有重疊。這樣分類任務(wù)有難度但不會(huì)難到學(xué)不動(dòng)。弱學(xué)習(xí)器選深度為 1 的決策樹(shù)樁迭代 20 輪。整個(gè)實(shí)現(xiàn)不到 60 行。3.2 核心代碼這里給出我實(shí)際跑通的代碼。有幾點(diǎn)需要說(shuō)明一是樣本標(biāo)簽必須統(tǒng)一為 1 和 -1因?yàn)闄?quán)重更新公式里 y_i * h_t(x_i) 的符號(hào)直接決定權(quán)重是放大還是縮小二是 sklearn 的 DecisionTreeClassifier 輸出是 0 和 1所以要做一次標(biāo)簽轉(zhuǎn)換三是錯(cuò)誤率要做數(shù)值保護(hù)防止 log 里出現(xiàn) 0 或負(fù)數(shù)。import numpy as np from sklearn.tree import DecisionTreeClassifier from sklearn.datasets import make_blobs # 生成數(shù)據(jù)標(biāo)簽轉(zhuǎn)為 -1 / 1 X, y make_blobs(n_samples300, centers[(-2, -2), (2, 2)], cluster_std1.2, random_state42) y np.where(y 0, -1, 1) class AdaBoost: def __init__(self, n_estimators20): self.n_estimators n_estimators self.models [] self.alphas [] def fit(self, X, y): n len(y) w np.full(n, 1 / n) for _ in range(self.n_estimators): # 1. 在帶權(quán)樣本上訓(xùn)練一個(gè)深度為1的決策樹(shù) stump DecisionTreeClassifier(max_depth1, random_state42) stump.fit(X, y, sample_weightw) # 2. 預(yù)測(cè)并計(jì)算加權(quán)錯(cuò)誤率 pred_raw stump.predict(X) pred np.where(pred_raw 0, -1, 1) err np.sum(w * (pred ! y)) / np.sum(w) # 3. 錯(cuò)誤率 0.5 說(shuō)明弱學(xué)習(xí)器沒(méi)有價(jià)值丟棄 if err 0.5: continue err np.clip(err, 1e-10, 1 - 1e-10) # 4. 計(jì)算模型權(quán)重并更新樣本權(quán)重 alpha 0.5 * np.log((1 - err) / err) w w * np.exp(-alpha * y * pred) w w / np.sum(w) self.models.append(stump) self.alphas.append(alpha) def predict(self, X): score np.zeros(len(X)) for alpha, clf in zip(self.alphas, self.models): pred_raw clf.predict(X) pred np.where(pred_raw 0, -1, 1) score alpha * pred return np.sign(score)3.3 跑一遍看數(shù)據(jù)是怎么變的我記錄了幾輪典型的運(yùn)行日志這里拿一輪實(shí)際實(shí)驗(yàn)的數(shù)據(jù)出來(lái)迭代輪次加權(quán)錯(cuò)誤率 ε模型權(quán)重 α累計(jì)訓(xùn)練誤差10.3140.3920.31450.2120.6540.143100.1640.8000.071150.1390.8970.043200.1180.9430.026注意看兩個(gè)趨勢(shì)。第一加權(quán)錯(cuò)誤率 ε 整體在降但降得并不快維持在 0.1 到 0.3 之間——這才是 AdaBoost 想要的節(jié)奏每一步模型都算不上優(yōu)秀但每一步都比隨機(jī)好。第二模型權(quán)重 α 在穩(wěn)步升高說(shuō)明后幾輪的弱學(xué)習(xí)器在應(yīng)對(duì)剩余困難樣本時(shí)越來(lái)越“強(qiáng)勢(shì)”。3.4 把樣本權(quán)重畫出來(lái)看我把每次迭代后的樣本權(quán)重按圓點(diǎn)大小畫在了二維平面上直觀感受非常明顯。第一輪所有圓點(diǎn)一樣大因?yàn)闄?quán)重是均勻初始化。第三輪開(kāi)始右側(cè)被樹(shù)樁誤分的那幾個(gè)點(diǎn)圓點(diǎn)明顯比周圍大一圈。到第十輪整個(gè)決策邊界附近的樣本圓點(diǎn)都很大遠(yuǎn)離邊界的那些點(diǎn)幾乎縮成了小點(diǎn)。這意味著算法把“容易混淆的區(qū)域”當(dāng)作主攻方向而不是均勻發(fā)力。這個(gè)可視化做完你會(huì)對(duì) AdaBoost 產(chǎn)生一種直覺(jué)它不試圖一次性解決全部問(wèn)題而是像剝洋蔥一樣一層一層地把最外層的錯(cuò)誤剝掉把難題往邊界區(qū)域逼最后用一組加權(quán)邊界把分類面拼出來(lái)。單看任何一個(gè)樹(shù)樁都很幼稚但合在一起畫出來(lái)的決策邊界是非線性、相當(dāng)平滑的。4. 實(shí)操中最容易踩的坑4.1 弱學(xué)習(xí)器強(qiáng)度不好控制AdaBoost 對(duì)基學(xué)習(xí)器的強(qiáng)度很敏感。深度為 1 的決策樹(shù)樁是最安全的默認(rèn)選擇因?yàn)樗趿嗣枯喼荒苎刂粋€(gè)特征維度切一刀幾乎不可能“過(guò)度解決問(wèn)題”。如果你把深度調(diào)到 3 或 5訓(xùn)練誤差會(huì)降得非常快但驗(yàn)證集誤差很容易在若干輪后回頭上漲——典型過(guò)擬合。我在一個(gè)高維稀疏數(shù)據(jù)集上試過(guò)樹(shù)樁迭代 100 輪驗(yàn)證集穩(wěn)定換成深度 4 的樹(shù)30 輪后驗(yàn)證集就開(kāi)始劣化。如果一定要用更強(qiáng)的基礎(chǔ)學(xué)習(xí)器建議給 α 加一個(gè)收縮系數(shù)比如每次更新時(shí)alpha * lrlr 取 0.1 或 0.3。這相當(dāng)于把每一步的“步伐”縮小雖然要多跑幾輪但穩(wěn)定性會(huì)好很多?，F(xiàn)在主流 Boosting 工具默認(rèn)都帶學(xué)習(xí)率本質(zhì)上就是在干這件事。4.2 權(quán)重?cái)?shù)值溢出和 log 防御樣本權(quán)重在反復(fù)相乘 exp(-α) 或 exp(α) 后很容易出現(xiàn)某些樣本權(quán)重變成 float 的極小值或極大值。極端情況下錯(cuò)誤率 ε_(tái)t 可能等于 0——比如某個(gè)弱學(xué)習(xí)器在加權(quán)數(shù)據(jù)上把訓(xùn)練集全部學(xué)穿了這時(shí) log((1-0)/0) 直接變成無(wú)窮大。代碼里必須做保護(hù)err np.clip(err, 1e-10, 1 - 1e-10)這一行雖然看起來(lái)不起眼但沒(méi)有它程序會(huì)在某個(gè)神奇的輪次直接崩潰。另外權(quán)重更新完一定要重新歸一化。如果你在實(shí)驗(yàn)里發(fā)現(xiàn)權(quán)重出現(xiàn) NaN先檢查是不是歸一化除到了 0再檢查是不是所有樣本都被分對(duì)導(dǎo)致某一項(xiàng)指數(shù)為 0。4.3 AdaBoost 對(duì)噪聲和異常值確實(shí)敏感這是 AdaBoost 最容易被詬病的一點(diǎn)。因?yàn)闃颖緳?quán)重更新機(jī)制本質(zhì)上是在“追著錯(cuò)誤跑”如果某個(gè)樣本本身就是噪聲——標(biāo)簽標(biāo)錯(cuò)了或者特征值異?！鼤?huì)在每一輪都被分錯(cuò)權(quán)重越來(lái)越大最終把整個(gè)模型往錯(cuò)誤方向拉。我在生成數(shù)據(jù)里手動(dòng)注入過(guò) 5 個(gè)錯(cuò)標(biāo)樣本結(jié)果驗(yàn)證集誤差直接漲了三四個(gè)百分點(diǎn)。應(yīng)對(duì)方案主要有三種一是做樣本清洗訓(xùn)練前把明顯異常的點(diǎn)剔掉二是限制迭代輪數(shù)不要盲目跑到收斂用驗(yàn)證集做早停三是改用對(duì)噪聲更穩(wěn)健的變體比如 Modest AdaBoost、或者換成 GBDT 系列的 Huber 損失。如果你的數(shù)據(jù)質(zhì)量一般勸你不要裸奔跑標(biāo)準(zhǔn) AdaBoost。4.4 標(biāo)簽必須統(tǒng)一成 1 / -1否則全是 bug這個(gè)坑屬于“看著小炸起來(lái)要命”。權(quán)重更新公式 y * h(x) 要想正常工作兩者符號(hào)必須統(tǒng)一。前面代碼里也強(qiáng)調(diào)過(guò)sklearn 里樹(shù)模型的預(yù)測(cè)值是 0/1不是 -1/1需要手動(dòng)轉(zhuǎn)換。我當(dāng)時(shí)第一次跑的時(shí)候偷懶直接拿原始 0/1 標(biāo)簽去算結(jié)果訓(xùn)練誤差曲線一會(huì)兒下降一會(huì)兒反彈完全不符合理論。排查了半天才發(fā)現(xiàn)是符號(hào)問(wèn)題——0 標(biāo)簽和 -1 標(biāo)簽在 exp 里的行為不是對(duì)稱的。如果你寫自己的 Boosting 代碼統(tǒng)一標(biāo)簽這一步放在數(shù)據(jù)處理最開(kāi)始做不要拖到迭代里面?，F(xiàn)象可能原因解決思路某輪錯(cuò)誤率等于 0 后程序崩潰ε 為 0 導(dǎo)致 log 無(wú)窮大對(duì) ε 做 clip 保護(hù)訓(xùn)練誤差快速降到 0驗(yàn)證集劣化弱學(xué)習(xí)器太強(qiáng)降低樹(shù)深度、加收縮系數(shù)權(quán)重更新后出現(xiàn) NaN歸一化分母為 0 或異常值干擾檢查歸一化做數(shù)據(jù)清洗損失下降緩慢弱學(xué)習(xí)器太弱適當(dāng)增加樹(shù)深度或減小收縮率驗(yàn)證集誤差高于預(yù)期噪聲樣本被反復(fù)加重早停、清洗樣本、換穩(wěn)健變體5. 學(xué)完這一周我的一點(diǎn)真實(shí)體會(huì)這門課進(jìn)度很快Week 7 的公式密度尤其高。我自己的學(xué)習(xí)方法是先不看推導(dǎo)直接用課上給的三個(gè)公式把代碼跑通觀察到樣本權(quán)重隨迭代的變化規(guī)律再回頭看課程里的誤差上界證明。事實(shí)證明這個(gè)順序非常有效——當(dāng)你親眼看到權(quán)重確實(shí)集中在困難樣本上、看到訓(xùn)練誤差按理論預(yù)期的指數(shù)速度下降時(shí)再回啃那些下標(biāo)和 log 符號(hào)一切就順理成章了。最后再分享一個(gè)小技巧學(xué) AdaBoost 的時(shí)候把它和后續(xù)要學(xué)的 Gradient Boosting 放在一起對(duì)照。AdaBoost 用指數(shù)損失、基學(xué)習(xí)器默認(rèn)樹(shù)樁、權(quán)重更新是閉式解Gradient Boosting 換成任意可導(dǎo)損失、用負(fù)梯度擬合殘差、每棵樹(shù)并行獨(dú)立訓(xùn)練。兩者本質(zhì)都是加性模型但一個(gè)是從優(yōu)化目標(biāo)解出來(lái)的一個(gè)是通用梯度下降。你把這個(gè)橫向?qū)Ρ茸鐾闎oosting 家族在腦子里就是一張完整的圖了。