机器学习：从基础理论到典型算法（原书第2版）

译者序
前言
第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
0章　排序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
1章　回归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
2章　 熵模型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
3章　条件 熵模型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
4章　算法稳定性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
5章　降维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
6章　学习自动机和语言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
7章　强化学习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