機器學習：從基礎理論到典型算法（原書第2版） Foundations of Machine Learning, 2/e

譯者序
前言
第1章引言1
1.1 什麼是機器學習1
1.2 機器學習可以解決什麼樣的問題2
1.3 一些典型的學習任務2
1.4 學習階段3
1.5 學習情境4
1.6 泛化5
第2章PAC學習框架7
2.1 PAC學習模型7
2.2 對有限假設集的學習保證——一致的情況11
2.3 對有限假設集的學習保證——不一致的情況14
2.4 泛化性16
2.4.1 確定性與隨機性情境16
2.4.2 貝葉斯誤差與噪聲17
2.5 文獻評註18
2.6 習題18
第3章Rademacher複雜度和VC-維23
3.1 Rademacher複雜度23
3.2 生長函數27
3.3 VC-維28
3.4 下界34
3.5 文獻評註38
3.6 習題39
第4章模型選擇46
4.1 估計誤差和近似誤差46
4.2 經驗風險最小化47
4.3 結構風險最小化47
4.4 交叉驗證50
4.5 n-折交叉驗證52
4.6 基於正則化的算法53
4.7 凸替換項損失54
4.8 文獻評註57
4.9 習題58
第5章支持向量機59
5.1 線性分類59
5.2 可分情況60
5.2.1 原始優化問題60
5.2.2 支持向量61
5.2.3 對偶優化問題62
5.2.4 留一法63
5.3 不可分情況64
5.3.1 原始優化問題65
5.3.2 支持向量66
5.3.3 對偶優化問題67
5.4 間隔理論67
5.5 文獻評註74
5.6 習題74
第6章核方法77
6.1 引言77
6.2 正定對稱核79
6.2.1 定義79
6.2.2 再生核希爾伯特空間81
6.2.3 性質82
6.3 基於核的算法85
6.3.1 具有PDS核的SVM85
6.3.2 表示定理86
6.3.3 學習保證87
6.4 負定對稱核88
6.5 序列核90
6.5.1 加權轉換器90
6.5.2 有理核93
6.6 近似核特徵映射96
6.7 文獻評註100
6.8 習題100
第7章boosting106
7.1 引言106
7.2 AdaBoost算法107
7.2.1 經驗誤差的界109
7.2.2 與坐標下降的關係110
7.2.3 實踐中的使用方式112
7.3 理論結果113
7.3.1 基於VC-維的分析113
7.3.2 L1-幾何間隔113
7.3.3 基於間隔的分析115
7.3.4 間隔最大化118
7.3.5 博弈論解釋119
7.4 L1-正則化120
7.5 討論122
7.6 文獻評註122
7.7 習題124
第8章在線學習129
8.1 引言129
8.2 有專家建議的預測130
8.2.1 錯誤界和折半算法130
8.2.2 加權多數算法131
8.2.3 隨機加權多數算法132
8.2.4 指數加權平均算法135
8.3 線性分類137
8.3.1 感知機算法137
8.3.2 Winnow算法143
8.4 在線到批處理的轉換145
8.5 與博弈論的聯繫147
8.6 文獻評註148
8.7 習題149
第9章多分類153
9.1 多分類問題153
9.2 泛化界154
9.3 直接型多分類算法159
9.3.1 多分類SVM159
9.3.2 多分類boosting算法160
9.3.3 決策樹161
9.4 類別分解型多分類算法164
9.4.1 一對多164
9.4.2 一對一165
9.4.3 糾錯輸出編碼166
9.5 結構化預測算法168
9.6 文獻評註169
9.7 習題170
第10章排序172
10.1 排序問題172
10.2 泛化界173
10.3 使用SVM進行排序175
10.4 RankBoost176
10.4.1 經驗誤差界178
10.4.2 與坐標下降的關係179
10.4.3 排序問題集成算法的間隔界180
10.5 二部排序181
10.5.1 二部排序中的boosting算法182
10.5.2 ROC曲線下面積184
10.6 基於偏好的情境184
10.6.1 兩階段排序問題185
10.6.2 確定性算法186
10.6.3 隨機性算法187
10.6.4 關於其他損失函數的擴展188
10.7 其他的排序準則189
10.8 文獻評註189
10.9 習題190
第11章回歸191
11.1 回歸問題191
11.2 泛化界192
11.2.1 有限假設集192
11.2.2 Rademacher複雜度界193
11.2.3 偽維度界194
11.3 回歸算法196
11.3.1 線性回歸196
11.3.2 核嶺回歸198
11.3.3 支持向量回歸201
11.3.4 Lasso204
11.3.5 組範數回歸算法206
11.3.6 在線回歸算法207
11.4 文獻評註207
11.5 習題208
第12章最大熵模型210
12.1 密度估計問題210
12.1.1 最大似然解210
12.1.2 最大後驗解211
12.2 添加特徵的密度估計問題212
12.3 最大熵準則212
12.4 最大熵模型簡介213
12.5 對偶問題213
12.6 泛化界216
12.7 坐標下降算法217
12.8 拓展218
12.9 L2-正則化220
12.10 文獻評註222
12.11 習題223
第13章條件最大熵模型224
13.1 學習問題224
13.2 條件最大熵準則224
13.3 條件最大熵模型簡介225
13.4 對偶問題226
13.5 性質227
13.5.1 優化問題227
13.5.2 特徵向量228
13.5.3 預測228
13.6 泛化界228
13.7 邏輯回歸231
13.7.1 優化問題231
13.7.2 邏輯模型231
13.8 L2-正則232
13.9 對偶定理的證明233
13.10 文獻評註235
13.11 習題235
第14章算法穩定性237
14.1 定義237
14.2 基於穩定性的泛化保證238
14.3 基於核的正則化算法的穩定性239
14.3.1 應用於回歸算法：以SVR和KRR為例242
14.3.2 應用於分類算法：以SVM為例243
14.3.3 討論244
14.4 文獻評述244
14.5 習題244
第15章降維246
15.1 主成分分析247
15.2 核主成分分析248
15.3 KPCA和流形學習249
15.3.1 等距映射249
15.3.2 拉普拉斯特徵映射249
15.3.3 局部線性嵌入250
15.4 Johnson-Lindenstrauss引理251
15.5 文獻評註252
15.6 習題253
第16章學習自動機和語言255
16.1 引言255
16.2 有限自動機256
16.3 高效精確學習257
16.3.1 被動學習257
16.3.2 通過查詢學習258
16.3.3 通過查詢學習自動機259
16.4 極限下的識別262
16.5 文獻評註267
16.6 習題268
第17章強化學習270
17.1 學習情境270
17.2 馬爾可夫決策過程模型271
17.3 策略272
17.3.1 定義272
17.3.2 策略值272
17.3.3 最優策略273
17.3.4 策略評估274
17.4 規划算法275
17.4.1 值迭代275
17.4.2 策略迭代277
17.4.3 線性規劃279
17.5 學習算法279
17.5.1 隨機逼近280
17.5.2 TD（0）算法283
17.5.3 Q-學習算法283
17.5.4 SARSA算法286
17.5.5 TD（λ）算法286
17.5.6 大狀態空間287
17.6 文獻評註288
後記289
附錄A 線性代數回顧290
附錄B 凸優化295
附錄C 概率論回顧308
附錄D 集中不等式315
附錄E 信息論回顧328
附錄F 符號337
參考文獻338
索引352