機(jī)器學(xué)習(xí)課件周志華Chap08集成學(xué)習(xí)

第八章：集成學(xué)習(xí)集成學(xué)習(xí)個(gè)體與集成

BoostingAdaboost

Bagging與隨機(jī)森林結(jié)合策略平均法投票法學(xué)習(xí)法多樣性誤差-分歧分解多樣性度量多樣性擾動(dòng)個(gè)體與集成集成學(xué)習(xí)(ensemble

learning)通過構(gòu)建并結(jié)合多個(gè)學(xué)習(xí)器來提升性能個(gè)體與集成考慮一個(gè)簡(jiǎn)單的例子，在二分類問題中，假定3個(gè)分類器在三個(gè)樣本中的表現(xiàn)如下圖所示，其中√

表示分類正確，X

號(hào)表示分類錯(cuò)誤，集成的結(jié)果通過投票產(chǎn)生。集成個(gè)體應(yīng)：好而不同個(gè)體與集成–簡(jiǎn)單分析考慮二分類問題，假設(shè)基分類器的錯(cuò)誤率為：

個(gè)體與集成–簡(jiǎn)單分析假設(shè)基分類器的錯(cuò)誤率相互獨(dú)立，則由Hoeffding不等式可得集成的錯(cuò)誤率為：

個(gè)體與集成–簡(jiǎn)單分析上面的分析有一個(gè)關(guān)鍵假設(shè)：基學(xué)習(xí)器的誤差相互獨(dú)立現(xiàn)實(shí)任務(wù)中，個(gè)體學(xué)習(xí)器是為解決同一個(gè)問題訓(xùn)練出來的，顯然不可能互相獨(dú)立事實(shí)上，個(gè)體學(xué)習(xí)器的“準(zhǔn)確性”和“多樣性”本身就存在沖突如何產(chǎn)生“好而不同”的個(gè)體學(xué)習(xí)器是集成學(xué)習(xí)研究的核心集成學(xué)習(xí)大致可分為兩大類集成學(xué)習(xí)個(gè)體與集成

BoostingAdaboost

Bagging與隨機(jī)森林結(jié)合策略平均法投票法學(xué)習(xí)法多樣性誤差-分歧分解多樣性度量多樣性擾動(dòng)Boosting個(gè)體學(xué)習(xí)器存在強(qiáng)依賴關(guān)系，串行生成每次調(diào)整訓(xùn)練數(shù)據(jù)的樣本分布Boosting

-

Boosting算法Boosting族算法最著名的代表是AdaBoostBoosting

–AdaBoost算法Boosting

–AdaBoost推導(dǎo)基學(xué)習(xí)器的線性組合最小化指數(shù)損失函數(shù)Boosting

–AdaBoost推導(dǎo)

Boosting

–AdaBoost推導(dǎo)

令指數(shù)損失函數(shù)的導(dǎo)數(shù)為0，即Boosting

–AdaBoost推導(dǎo)

泰勒展開近似為Boosting

–AdaBoost推導(dǎo)于是，理想的基學(xué)習(xí)器：注意到是一個(gè)常數(shù)，令Dt表示一個(gè)分布:

Boosting

–AdaBoost推導(dǎo)根據(jù)數(shù)學(xué)期望的定義，這等價(jià)于令:

Boosting

–AdaBoost推導(dǎo)最終的樣本分布更新公式則理想的基學(xué)習(xí)器Boosting

–AdaBoost注意事項(xiàng)數(shù)據(jù)分布的學(xué)習(xí)重賦權(quán)法重采樣法重啟動(dòng)，避免訓(xùn)練過程過早停止00.20.40.60.80.20.40.6好瓜壞瓜密度含糖率00.20.40.60.80.20.40.6好瓜壞瓜密度含糖率00.20.40.60.80.20.40.6好瓜壞瓜密度含糖率(a)3個(gè)基學(xué)習(xí)器(b)5個(gè)基學(xué)習(xí)器(c)11個(gè)基學(xué)習(xí)器Boosting

–AdaBoost實(shí)驗(yàn)從偏差-方差的角度：降低偏差，可對(duì)泛化性能相當(dāng)弱的學(xué)習(xí)器構(gòu)造出很強(qiáng)的集成集成學(xué)習(xí)個(gè)體與集成

BoostingAdaboost

Bagging與隨機(jī)森林結(jié)合策略平均法投票法學(xué)習(xí)法多樣性誤差-分歧分解多樣性度量多樣性擾動(dòng)Bagging與隨機(jī)森林個(gè)體學(xué)習(xí)器不存在強(qiáng)依賴關(guān)系并行化生成自助采樣法Bagging與隨機(jī)森林

-

Bagging算法Bagging與隨機(jī)森林-

Bagging算法特點(diǎn)時(shí)間復(fù)雜度低假定基學(xué)習(xí)器的計(jì)算復(fù)雜度為O(m)，采樣與投票/平均過程的復(fù)雜度為O(s)，則bagging的復(fù)雜度大致為T(O(m)+O(s))由于O(s)很小且T是一個(gè)不大的常數(shù)因此訓(xùn)練一個(gè)bagging集成與直接使用基學(xué)習(xí)器的復(fù)雜度同階可使用包外估計(jì)Bagging與隨機(jī)森林-包外估計(jì)

Bagging泛化誤差的包外估計(jì)為：00.20.40.60.80.20.40.6好瓜壞瓜密度含糖率00.20.40.60.80.20.40.6好瓜壞瓜密度含糖率00.20.40.60.80.20.40.6好瓜壞瓜密度含糖率(a)3個(gè)基學(xué)習(xí)器(b)5個(gè)基學(xué)習(xí)器(c)11個(gè)基學(xué)習(xí)器Bagging與隨機(jī)森林-Bagging實(shí)驗(yàn)從偏差-方差的角度：降低方差，在不剪枝的決策樹、神經(jīng)網(wǎng)絡(luò)等易受樣本影響的學(xué)習(xí)器上效果更好Bagging與隨機(jī)森林-隨機(jī)森林隨機(jī)森林(Random

Forest，簡(jiǎn)稱RF)是bagging的一個(gè)擴(kuò)展變種采樣的隨機(jī)性屬性選擇的隨機(jī)性Bagging與隨機(jī)森林-隨機(jī)森林算法隨機(jī)森林算法Bagging與隨機(jī)森林-隨機(jī)森林實(shí)驗(yàn)集成學(xué)習(xí)個(gè)體與集成

BoostingAdaboost

Bagging與隨機(jī)森林結(jié)合策略平均法投票法學(xué)習(xí)法多樣性誤差-分歧分解多樣性度量多樣性擾動(dòng)(a)統(tǒng)計(jì)的原因(b)計(jì)算的原因(c)表示的原因同等性能的假設(shè)假設(shè)空間個(gè)體假設(shè)真實(shí)假設(shè)結(jié)合策略學(xué)習(xí)器的組合可以從三個(gè)方面帶來好處結(jié)合策略–平均法簡(jiǎn)單平均法加權(quán)平均法結(jié)合策略–平均法簡(jiǎn)單平均法是加權(quán)平均法的特例加權(quán)平均法在二十世紀(jì)五十年代被廣泛使用集成學(xué)習(xí)中的各種結(jié)合方法都可以看成是加權(quán)平均法的變種或特例加權(quán)平均法可認(rèn)為是集成學(xué)習(xí)研究的基本出發(fā)點(diǎn)加權(quán)平均法未必一定優(yōu)于簡(jiǎn)單平均法結(jié)合策略–投票法絕對(duì)多數(shù)投票法（majorityvoting）相對(duì)多數(shù)投票法（pluralityvoting）加權(quán)投票法（weightedvoting）結(jié)合策略–

學(xué)習(xí)法Stacking是學(xué)習(xí)法的典型代表

多響應(yīng)線性回歸(MLR)作為次級(jí)學(xué)習(xí)器的學(xué)習(xí)算法效果較好貝葉斯模型平均(BMA)集成學(xué)習(xí)個(gè)體與集成

BoostingAdaboost

Bagging與隨機(jī)森林結(jié)合策略平均法投票法學(xué)習(xí)法多樣性誤差-分歧分解多樣性度量多樣性擾動(dòng)多樣性–誤差-分歧分解

集成的分歧：多樣性–誤差-分歧分解

多樣性–誤差-分歧分解令表示個(gè)體學(xué)習(xí)器誤差的加權(quán)均值，有

多樣性–誤差-分歧分解

集成的泛化誤差為：令表示個(gè)體學(xué)習(xí)器泛化誤差的加權(quán)均值，表示個(gè)體學(xué)習(xí)器的加權(quán)分歧值，有多樣性–誤差-分歧分解

多樣性–多樣性度量多樣性度量(diversity

measure)用于度量集成中個(gè)體學(xué)習(xí)器的多樣性常見的多樣性度量不合度量(DisagreementMeasure)相關(guān)系數(shù)(CorrelationCoefficient)多樣性–多樣性度量常見的多樣性度量Q-統(tǒng)計(jì)量(Q-Statistic)K-統(tǒng)計(jì)量(Kappa-Statistic)多樣性–多樣性度量多樣性–多樣性度量

多樣性–多樣性增強(qiáng)常見的增強(qiáng)個(gè)體學(xué)習(xí)器的多樣性的方法數(shù)據(jù)樣本擾動(dòng)輸入屬性擾動(dòng)輸出表示擾動(dòng)算法參數(shù)擾動(dòng)多樣性–多樣性增強(qiáng)

-數(shù)據(jù)樣本擾動(dòng)數(shù)據(jù)樣本擾動(dòng)通常是基于采樣法Bagging中的自助采樣法Adaboost中的序列采樣對(duì)數(shù)據(jù)樣本的擾動(dòng)敏感的基學(xué)習(xí)器(不穩(wěn)定基學(xué)習(xí)器)決策樹，神經(jīng)網(wǎng)絡(luò)等對(duì)數(shù)據(jù)樣本的擾動(dòng)不敏感的基學(xué)習(xí)器(穩(wěn)定基學(xué)習(xí)器)線性學(xué)習(xí)器，支持向量機(jī)，樸素貝葉斯，k近鄰等數(shù)據(jù)樣本擾動(dòng)對(duì)“不穩(wěn)定基學(xué)習(xí)器”很有效隨機(jī)子空間算法(random

subspace)

多樣性–多樣性增強(qiáng)

–輸入屬性擾動(dòng)翻轉(zhuǎn)法(Flipping

Output)輸出調(diào)劑法(Output

Smearing)ECOC法多樣性–多樣性增強(qiáng)

–輸出表示擾動(dòng)負(fù)相關(guān)法不同的多樣性增強(qiáng)機(jī)制同時(shí)使用多樣性–多樣性增強(qiáng)

–算法參數(shù)擾動(dòng)閱讀材料集成學(xué)習(xí)方面的主要推薦讀物是[Zhou,2012]，本章提及的所有內(nèi)容在該書中都有更深入的詳細(xì)介紹。[Kuncheva,2004;Rockach,2010b]可供參考，[Schapire

and

Freund,2012]則是專門關(guān)于Boosting的著作，集成學(xué)習(xí)方面有一些專門性的會(huì)議MCS(International

Workshop

on

Multiple

Classifier

System).Boosting源于[Schapire,1990]對(duì)[Kearns

and

Va