第1章 引论 1
1.1 什么是学习 1
1.2 什么时候需要机器学习 2
1.3 学习的种类 3
1.4 与其他领域的关系 4
1.5 如何阅读本书 4
1.6 符号 6
第一部分 理论基础 10
第2章 简易入门 10
2.1 一般模型——统计学习理论框架 10
2.2 经验风险最小化 11
2.3 考虑归纳偏置的经验风险最小化 12
2.4 练习 15
第3章 一般学习模型 17
3.1 PAC学习理论 17
3.2 更常见的学习模型 18
3.2.1 放宽可实现假设——不可知PAC学习 18
3.2.2 学习问题建模 19
3.3 小结 21
3.4 文献评注 21
3.5 练习 21
第4章 学习过程的一致收敛性 24
4.1 一致收敛是可学习的充分条件 24
4.2 有限类是不可知PAC可学习的 25
4.3 小结 26
4.4 文献评注 27
4.5 练习 27
第5章 偏差与复杂性权衡 28
5.1 “没有免费的午餐”定理 28
5.2 误差分解 31
5.3 小结 31
5.4 文献评注 32
5.5 练习 32
第6章 VC维 33
6.1 无限的类也可学习 33
6.2 VC维概述 34
6.3 实例 35
6.3.1 阈值函数 35
6.3.2 区间 35
6.3.3 平行于轴的矩形 35
6.3.4 有限类 36
6.3.5 VC维与参数个数 36
6.4 PAC学习的基本定理 36
6.5 定理6.7的证明 37
6.5.1 Sauer引理及生长函数 37
6.5.2 有小的有效规模的类的一致收敛性 39
6.6 小结 40
6.7 文献评注 41
6.8 练习 41
第7章 不一致可学习 44
7.1 不一致可学习概述 44
7.2 结构风险最小化 46
7.3 最小描述长度和奥卡姆剃刀 48
7.4 可学习的其他概念——一致收敛性 50
7.5 探讨不同的可学习概念 51
7.6 小结 53
7.7 文献评注 53
7.8 练习 54
第8章 学习的运行时间 56
8.1 机器学习的计算复杂度 56
8.2 ERM规则的实现 58
8.2.1 有限集 58
8.2.2 轴对称矩形 59
8.2.3 布尔合取式 59
8.2.4 学习三项析取范式 60
8.3 高效学习，而不通过合适的ERM 60
8.4 学习的难度 61
8.5 小结 62
8.6 文献评注 62
8.7 练习 62
第二部分 从理论到算法 66
第9章 线性预测 66
9.1 半空间 66
9.1.1 半空间类线性规划 67
9.1.2 半空间感知器 68
9.1.3 半空间的VC维 69
9.2 线性回归 70
9.2.1 最小平方 70
9.2.2 多项式线性回归 71
9.3 逻辑斯谛回归 72
9.4 小结 73
9.5 文献评注 73
9.6 练习 73
第10章 boosting 75
10.1 弱可学习 75
10.2 AdaBoost 78
10.3 基础假设类的线性组合 80
10.4 AdaBoost用于人脸识别 82
10.5 小结 83
10.6 文献评注 83
10.7 练习 84
第11章 模型选择与验证 85
11.1 用结构风险最小化进行模型选择 85
11.2 验证法 86
11.2.1 留出的样本集 86
11.2.2 模型选择的验证法 87
11.2.3 模型选择曲线 88
11.2.4 k折交叉验证 88
11.2.5 训练-验证-测试拆分 89
11.3 如果学习失败了应该做什么 89
11.4 小结 92
11.5 练习 92
第12章 凸学习问题 93
12.1 凸性、利普希茨性和光滑性 93
12.1.1 凸性 93
12.1.2 利普希茨性 96
12.1.3 光滑性 97
12.2 凸学习问题概述 98
12.2.1 凸学习问题的可学习性 99
12.2.2 凸利普希茨/光滑有界学习问题 100
12.3 替代损失函数 101
12.4 小结 102
12.5 文献评注 102
12.6 练习 102
第13章 正则化和稳定性 104
13.1 正则损失最小化 104
13.2 稳定规则不会过拟合 105
13.3 Tikhonov正则化作为稳定剂 106
13.3.1 利普希茨损失 108
13.3.2 光滑和非负损失 108
13.4 控制适合与稳定性的权衡 109
13.5 小结 111
13.6 文献评注 111
13.7 练习 111
第14章 随机梯度下降 114
14.1 梯度下降法 114
14.2 次梯度 116
14.2.1 计算次梯度 117
14.2.2 利普希茨函数的次梯度 118
14.2.3 次梯度下降 118
14.3 随机梯度下降 118
14.4 SGD的变型 120
14.4.1 增加一个投影步 120
14.4.2 变步长 121
14.4.3 其他平均技巧 121
14.4.4 强凸函数 121
14.5 用SGD进行学习 123
14.5.1 SGD求解风险极小化 123
14.5.2 SGD求解凸光滑学习问题的分析 124
14.5.3 SGD求解正则化损失极小化 125
14.6 小结 125
14.7 文献评注 125
14.8 练习 126
第15章 支持向量机 127
15.1 间隔与硬SVM 127
15.1.1 齐次情况 129
15.1.2 硬SVM的样本复杂度 129
15.2 软SVM与范数正则化 130
15.2.1 软SVM的样本复杂度 131
15.2.2 间隔、基于范数的界与维度 131
15.2.3 斜坡损失 132
15.3 最优化条件与“支持向量” 133
15.4 对偶 133
15.5 用随机梯度下降法实现软SVM 134
15.6 小结 135
15.7 文献评注 135
15.8 练习 135
第16章 核方法 136
16.1 特征空间映射 136
16.2 核技巧 137
16.2.1 核作为表达先验的一种形式 140
16.2.2 核函数的特征 141
16.3 软SVM应用核方法 141
16.4 小结 142
16.5 文献评注 143
16.6 练习 143
第17章 多分类、排序与复杂预测问题 145
17.1 一对多和一对一 145
17.2 线性多分类预测 147
17.2.1 如何构建Ψ 147
17.2.2 对损失敏感的分类 148
17.2.3 经验风险最小化 149
17.2.4 泛化合页损失 149
17.2.5 多分类SVM和SGD 150
17.3 结构化输出预测 151
17.4 排序 153
17.5 二分排序以及多变量性能测量 157
17.6 小结 160
17.7 文献评注 160
17.8 练习 161
第18章 决策树 162
18.1 采样复杂度 162
18.2 决策树算法 163
18.2.1 增益测量的实现方式 164
18.2.2 剪枝 165
18.2.3 实值特征基于阈值的拆分规则 165
18.3 随机森林 165
18.4 小结 166
18.5 文献评注 166
18.6 练习 166
第19章 最近邻 167
19.1 k近邻法 167
19.2 分析 168
19.2.1 1-NN准则的泛化界 168
19.2.2 “维数灾难” 170
19.3 效率实施 171
19.4 小结 171
19.5 文献评注 171
19.6 练习 171
第20章 神经元网络 174
20.1 前馈神经网络 174
20.2 神经网络学习 175
20.3 神经网络的表达力 176
20.4 神经网络样本复杂度 178
20.5 学习神经网络的运行时 179
20.6 SGD和反向传播 179
20.7 小结 182
20.8 文献评注 183
20.9 练习 183
第三部分 其他学习模型 186
第21章 在线学习 186
21.1 可实现情况下的在线分类 186
21.2 不可实现情况下的在线识别 191
21.3 在线凸优化 195
21.4 在线感知器算法 197
21.5 小结 199
21.6 文献评注 199
21.7 练习 199
第22章 聚类 201
22.1 基于链接的聚类算法 203
22.2 k均值算法和其他代价最小聚类 203
22.3 谱聚类 206
22.3.1 图割 206
22.3.2 图拉普拉斯与松弛图割算法 206
22.3.3 非归一化的谱聚类 207
22.4 信息瓶颈 208
22.5 聚类的进阶观点 208
22.6 小结 209
22.7 文献评注 210
22.8 练习 210
第23章 维度约简 212
23.1 主成分分析 212
23.1.1 当d＞＞m时一种更加有效的求解方法 214
23.1.2 应用与说明 214
23.2 随机投影 216
23.3 压缩感知 217
23.4 PCA还是压缩感知 223
23.5 小结 223
23.6 文献评注 223
23.7 练习 223
第24章 生成模型 226
24.1 极大似然估计 226
24.1.1 连续随机变量的极大似然估计 227
24.1.2 极大似然与经验风险最小化 228
24.1.3 泛化分析 228
24.2 朴素贝叶斯 229
24.3 线性判别分析 230
24.4 隐变量与EM算法 230
24.4.1 EM是交替最大化算法 232
24.4.2 混合高斯模型参数估计的EM算法 233
24.5 贝叶斯推理 233
24.6 小结 235
24.7 文献评注 235
24.8 练习 235
第25章 特征选择与特征生成 237
25.1 特征选择 237
25.1.1 滤波器 238
25.1.2 贪婪选择方法 239
25.1.3 稀疏诱导范数 241
25.2 特征操作和归一化 242
25.3 特征学习 244
25.4 小结 246
25.5 文献评注 246
25.6 练习 246
第四部分 高级理论 250
第26章 拉德马赫复杂度 250
26.1 拉德马赫复杂度概述 250
26.2 线性类的拉德马赫复杂度 255
26.3 SVM的泛化误差界 256
26.4 低e？范数预测器的泛化误差界 258
26.5 文献评注 259
第27章 覆盖数 260
27.1 覆盖 260
27.2 通过链式反应从覆盖到拉德马赫复杂度 261
27.3 文献评注 262
第28章 学习理论基本定理的证明 263
28.1 不可知情况的上界 263
28.2 不可知情况的下界 264
28.2.1 证明m（ε，δ）≥0.5log（1/（4δ））/ε2 264
28.2.2 证明m（ε，1/8）≥8d/ε2 265
28.3 可实现情况的上界 267
第29章 多分类可学习性 271
29.1 纳塔拉詹维 271
29.2 多分类基本定理 271
29.3 计算纳塔拉詹维 272
29.3.1 基于类的一对多 272
29.3.2 一般的多分类到二分类约简 273
29.3.3 线性多分类预测器 273
29.4 好的与坏的ERM 274
29.5 文献评注 275
29.6 练习 276
第30章 压缩界 277
30.1 压缩界概述 277
30.2 例子 278
30.2.1 平行于轴的矩形 278
30.2.2 半空间 279
30.2.3 可分多项式 279
30.2.4 间隔可分的情况 279
30.3 文献评注 280
第31章 PAC-贝叶斯 281
31.1 PAC-贝叶斯界 281
31.2 文献评注 282
31.3 练习 282
附录A 技术性引理 284
附录B 测度集中度 287
附录C 线性代数 294
参考文献 297
索引 305