机器学习：从基础理论到典型算法（原书第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
第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　对偶定理的证明23