機器學習提升法 理論與算法 Boosting: Foundations and Algorithms

Yoav Freund

紐約微軟主任研究員。

Robert. E. Schapire

加利福尼亞大學圣迭戈分校計算機科學與工程系教授。
他們因為在提升法方面的研究工作，
獲得了2003 年的哥德爾獎和2004 年的ACM Kanellakis 理論與實踐獎。

目錄
第1章　引言1
1.1　分類問題與機器學習2
1.2　提升法3
1.2.1　一個“玩具”例子6
1.2.2　算法的實驗性能9
1.2.3　一個醫學診斷的例子10
1.3　抗過擬合與間隔理論12
1.4　基礎理論與算法14
1.5　小結16
1.6　參考資料16
1.7　練習16

第一部分　算法核心分析
第2章　機器學習基礎21
2.1　機器學習直接分析方法21
2.1.1　學習的充分條件21
2.1.2　與另外一種算法的比較25
2.2　通用分析方法26
2.2.1　一個假設26
2.2.2　有限假設空間28
2.2.3　無限假設空間30
2.2.4　更抽象的公式34
2.2.5　一致性假設35
2.2.6　基於壓縮的界36
2.2.7　討論37
2.3　提升法研究基礎38
2.3.1　性能的絕對保證　38
2.3.2　弱可學習與提升法40
2.3.3　分析提升法的方法　41
2.4　小結43
2.5　參考資料43
2.6　練習44

第3章　用AdaBoost最小化訓練誤差46
3.1　AdaBoost算法訓練誤差的界　46
3.2　弱可學習的充分條件49
3.3　與切諾夫界的關系52
3.4　基學習算法的設計和使用53
3.4.1　使用樣本的權重　54
3.4.2　算法設計55
3.4.3　在人臉識別中的應用58
3.5　小結60
3.6　參考資料61
3.7　練習61

第4章　泛化誤差的直接界63
4.1　基於VC理論的泛化誤差的界63
4.1.1　基本假設63
4.1.2　AdaBoost分類器的形式與復雜度64
4.1.3　有限基假設空間66
4.1.4　無限基分類器空間68
4.2　基於壓縮的界70
4.2.1　主要思想70
4.2.2　混合壓縮模式71
4.2.3　應用到AdaBoost72
4.3　強學習與弱學習的等價性73
4.4　小結75
4.5　參考資料75
4.6　練習75

第5章　用間隔理論解釋提升法的有效性78
5.1　間隔作為置信度的度量79
5.2　泛化誤差的基於間隔的分析81
5.2.1　直觀感受81
5.2.2　有限基假設空間82
5.2.3　無限基假設空間87
5.3　基於Rademacher復雜度的分析89
5.4　提升法對間隔分佈的影響93
5.4.1　AdaBoost間隔的界93
5.4.2　更積極的間隔最大化95
5.4.3　弱可學習的充分必要條件97
5.5　偏差、方差和穩定性98
5.6　與支持向量機的關系102
5.6.1　支持向量機概覽102
5.6.2　與提升法的比較105
5.7　間隔的實際應用106
5.7.1　為了獲得更高的準確率拒絕低置信度的預測106
5.7.2　主動學習108
5.8　小結110
5.9　參考資料110
5.10　練習111

第二部分　基本觀點
第6章　博弈論、在線學習和提升法117
6.1　博弈論117
6.1.1　隨機玩法118
6.1.2　序列玩法119
6.1.3　極小極大理論120
6.2　從重復博弈中學習121
6.2.1　學習模型121
6.2.2　基本算法122
6.2.3　分析122
6.2.4　極小極大理論的證明126
6.2.5　一個游戲的近似解127
6.3　在線預測128
6.4　提升法131
6.4.1　提升法和極小極大理論131
6.4.2　提升法的思想133
6.4.3　分析135
6.5　應用於“讀心術”游戲136
6.6　小結141
6.7　參考資料141
6.8　練習142

第7章　損失最小化與Boosting算法的泛化145
7.1　AdaBoost的損失函數146
7.2　坐標下降法149
7.2.1　AdaBoost的泛化149
7.2.2　收斂性150
7.2.3　其他損失函數151
7.3　損失最小化不能解釋泛化能力152
7.4　泛函梯度下降154
7.4.1　另外一種泛化155
7.4.2　與坐標下降法的關系157
7.4.3　對通用損失函數進行分類和回歸158
7.5　邏輯斯蒂回歸和條件概率159
7.5.1　邏輯斯蒂回歸159
7.5.2　修改AdaBoost用於邏輯斯蒂損失161
7.5.3　估計條件概率164
7.6　正則化166
7.6.1　避免過擬合166
7.6.2　提升法與早停之間的關系169
7.6.3　與間隔最大化的關聯172
7.7　應用到數據有限的學習173
7.7.1　引入先驗知識173
7.7.2　半監督學習177
7.8　小結179
7.9　參考資料179
7.10　練習180

第8章　提升法、凸優化和信息幾何學184
8.1　迭代投影算法184
8.1.1　類歐幾里得184
8.1.2　信息論度量187
8.1.3　將AdaBoost看作迭代投影算法188
8.1.4　非空可行集的條件192
8.1.5　用非歸一化分佈的迭代投影195
8.2　證明AdaBoost的收斂性197
8.2.1　設置197
8.2.2　兩個問題合成一個198
8.2.3　證明199
8.2.4　凸對偶204
8.3　與邏輯斯蒂回歸的統一205
8.4　物種分佈建模的應用207
8.5　小結210
8.6　參考資料210
8.7　練習211

第三部分　算法擴展
第9章　基於置信度的弱預測219
9.1　框架220
9.2　算法設計的通用方法222
9.2.1　一般情況下如何選擇αt222
9.2.2　二分類預測223
9.2.3　有限範圍的預測224
9.2.4　可棄權的弱假設225
9.2.5　將參數αt隱入ht228
9.2.6　域分割的弱假設228
9.3　學習規則集231
9.4　交替決策樹233
9.5　小結239
9.6　參考資料239
9.7　練習239

第10章　多類別分類問題243
10.1　多類別問題的直接擴展244
10.2　一對其他歸約和多標簽分類248
10.2.1　多標簽分類249
10.2.2　漢明損失249
10.2.3　與“1錯誤”和單標簽分類的關系252
10.3　應用到語義分類問題253
10.4　應用輸出編碼的通用約簡257
10.4.1　多類別到多標簽257
10.4.2　更通用的編碼261
10.5　小結267
10.6　參考資料267
10.7　練習268

第11章　排序272
11.1　排序問題的形式化框架272
11.2　排序問題的提升法275
11.2.1　RankBoost275
11.2.2　選擇αt和弱學習器的標準277
11.2.3　RankBoost和AdaBoost的損失函數278
11.3　提高效率的方法280
11.3.1　約簡為二分類問題280
11.3.2　層級反饋282
11.3.3　準層級反饋284
11.4　多類別、多標簽分類288
11.5　應用290
11.5.1　解析英文句子290
11.5.2　找到癌症基因292
11.6　小結294
11.7　參考資料294
11.8　練習295第四部分高級理論

第12章達到盡可能高的準確度301
12.1　最優分類與風險最小化302
12.2　接近最優風險305
12.2.1　基假設的表達306
12.2.2　證明概覽306
12.2.3　正式的證明308
12.2.4　AdaBoost最小化經驗風險的速度的界310
12.2.5　夾緊效果的界315
12.2.6　經驗風險和真實風險之間的關系315
12.2.7　完成證明318
12.2.8　與基於間隔的界的對比318
12.3　風險最小化如何導致較差的準確性319
12.3.1　構建基於置信度的假設319
12.3.2　用二分類器進行構建322
12.3.3　均勻噪聲的困難324
12.4　小結326
12.5　參考資料326
12.6　練習327

第13章　效率最優的提升法332
13.1　BBM算法333
13.1.1　投票博弈333
13.1.2　一個籌碼游戲335
13.1.3　推導最優博弈336
13.1.4　一個容易處理的近似337
13.1.5　算法341
13.1.6　分析343
13.1.7　博弈論優化344
13.2　最優泛化誤差345
13.2.1　BBM的上界346
13.2.2　通用下界346
13.2.3　構建347
13.2.4　分析概述352
13.2.5　將提升器看作固定的函數353
13.2.6　誤差的分析355
13.2.7　將所有東西結合到一起358
13.3　與AdaBoost的關系359
13.3.1　誤差界的比較359
13.3.2　由BBM派生出AdaBoost360
13.3.3　權重的比較361
13.4　小結363
13.5　參考資料363
13.6　練習363

第14章　連續時間下的提升法367
14.1　連續時間極限下的適應性367
14.1.1　主要思想368
14.1.2　連續時間下的極限369
14.1.3　另一個推導過程372
14.2　BrownBoost375
14.2.1　算法375
14.2.2　分析377
14.3　AdaBoost作為BrownBoost的一個特例381
14.4　含噪聲的數據的實驗387
14.5　小結389
14.6　參考資料389
14.7　練習390

附錄A　符號、定義及其數學背景393
A.1　通用符號393
A.2　範式394
A.3　最大值、最小值、上確界、下確界394
A.4　極限395
A.5　連續性、閉集和緊性396
A.6　導數、梯度和泰勒定理397
A.7　凸集398
A.8　拉格朗日乘子法398
A.9　分佈和中心極限定理399