第1篇 监督学习 3
第1章 统计学习及监督学习概论 3
1.1统计学习 3
1.2统计学习的分类 5
1.2.1基本分类 6
1.2.2按模型分类 11
1.2.3按算法分类 13
1.2.4按技巧分类 13
1.3统计学习方法三要素 15
1.3.1模型 15
1.3.2策略 16
1.3.3算法 19
1.4模型评估与模型选择 19
1.4.1训练误差与测试误差 19
1.4.2过拟合与模型选择 20
1.5正则化与交叉验证 23
1.5.1正则化 23
1.5.2交叉验证 24
1.6泛化能力 24
1.6.1泛化误差 24
1.6.2泛化误差上界 25
1.7生成模型与判别模型 27
1.8监督学习应用 28
1.8.1分类问题 28
1.8.2标注问题 30
1.8.3回归问题 32
本章概要 33
继续阅读 33
习题 33
参考文献 34
第2章 感知机 35
2.1感知机模型 35
2.2感知机学习策略 36
2.2.1数据集的线性可分性 36
2.2.2感知机学习策略 37
2.3感知机学习算法 38
2.3.1感知机学习算法的原始形式 38
2.3.2算法的收敛性 41
2.3.3感知机学习算法的对偶形式 43
本章概要 46
继续阅读 46
习题 46
参考文献 47
第3章 k近邻法 49
3.1 k近邻算法 49
3.2 k近邻模型 50
3.2.1模型 50
3.2.2距离度量 50
3.2.3 k值的选择 52
3.2.4分类决策规则 52
3.3 k近邻法的实现:kd树 53
3.3.1构造kd树 53
3.3.2搜索kd树 55
本章概要 57
继续阅读 57
习题 58
参考文献 58
第4章 朴素贝叶斯法 59
4.1朴素贝叶斯法的学习与分类 59
4.1.1基本方法 59
4.1.2后验概率最大化的含义 61
4.2朴素贝叶斯法的参数估计 62
4.2.1极大似然估计 62
4.2.2学习与分类算法 62
4.2.3贝叶斯估计 64
本章概要 65
继续阅读 66
习题 66
参考文献 66
第5章 决策树 67
5.1决策树模型与学习 67
5.1.1决策树模型 67
5.1.2决策树与if-then规则 68
5.1.3决策树与条件概率分布 68
5.1.4决策树学习 69
5.2特征选择 71
5.2.1特征选择问题 71
5.2.2信息增益 72
5.2.3信息增益比 76
5.3决策树的生成 76
5.3.1 ID3算法 76
5.3.2 C4.5的生成算法 78
5.4决策树的剪枝 78
5.5 CART算法 80
5.5.1 CART生成 81
5.5.2 CART剪枝 85
本章概要 87
继续阅读 88
习题 89
参考文献 89
第6章 逻辑斯谛回归与最大熵模型 91
6.1逻辑斯谛回归模型 91
6.1.1逻辑斯谛分布 91
6.1.2二项逻辑斯谛回归模型 92
6.1.3模型参数估计 93
6.1.4多项逻辑斯谛回归 94
6.2最大熵模型 94
6.2.1最大熵原理 94
6.2.2最大熵模型的定义 96
6.2.3最大熵模型的学习 98
6.2.4极大似然估计 102
6.3模型学习的最优化算法 103
6.3.1改进的迭代尺度法 103
6.3.2拟牛顿法 107
本章概要 108
继续阅读 109
习题 109
参考文献 109
第7章 支持向量机 111
7.1线性可分支持向量机与硬间隔最大化 112
7.1.1线性可分支持向量机 112
7.1.2函数间隔和几何间隔 113
7.1.3间隔最大化 115
7.1.4学习的对偶算法 120
7.2线性支持向量机与软间隔最大化 125
7.2.1线性支持向量机 125
7.2.2学习的对偶算法 127
7.2.3支持向量 130
7.2.4合页损失函数 131
7.3非线性支持向量机与核函数 133
7.3.1核技巧 133
7.3.2正定核 136
7.3.3常用核函数 140
7.3.4非线性支持向量分类机 141
7.4序列最小最优化算法 142
7.4.1两个变量二次规划的求解方法 143
7.4.2变量的选择方法 147
7.4.3 SMO算法 149
本章概要 149
继续阅读 152
习题 152
参考文献 153
第8章 提升方法 155
8.1提升方法AdaBoost算法 155
8.1.1提升方法的基本思路 155
8.1.2 AdaBoost算法 156
8.1.3 AdaBoost的例子 158
8.2 AdaBoost算法的训练误差分析 160
8.3 AdaBoost算法的解释 162
8.3.1前向分步算法 162
8.3.2前向分步算法与AdaBoost 164
8.4提升树 166
8.4.1提升树模型 166
8.4.2提升树算法 166
8.4.3梯度提升 170
本章概要 172
继续阅读 172
习题 173
参考文献 173
第9章 EM算法及其推广 175
9.1 EM算法的引入 175
9.1.1 EM算法 175
9.1.2 EM算法的导出 179
9.1.3 EM算法在无监督学习中的应用 181
9.2 EM算法的收敛性 181
9.3 EM算法在高斯混合模型学习中的应用 183
9.3.1高斯混合模型 183
9.3.2高斯混合模型参数估计的EM算法 183
9.4 EM算法的推广 187
9.4.1 F函数的极大-极大算法 187
9.4.2 GEM算法 189
本章概要 191
继续阅读 192
习题 192
参考文献 192
第10章 隐马尔可夫模型 193
10.1隐马尔可夫模型的基本概念 193
10.1.1隐马尔可夫模型的定义 193
10.1.2观测序列的生成过程 196
10.1.3隐马尔可夫模型的3个基本问题 196
10.2概率计算算法 197
10.2.1直接计算法 197
10.2.2前向算法 198
10.2.3后向算法 201
10.2.4一些概率与期望值的计算 202
10.3学习算法 203
10.3.1监督学习方法 203
10.3.2 Baum-Welch算法 204
10.3.3 Baum-Welch模型参数估计公式 206
10.4预测算法 207
10.4.1近似算法 208
10.4.2维特比算法 208
本章概要 212
继续阅读 212
习题 213
参考文献 213
第11章 条件随机场 215
11.1概率无向图模型 215
11.1.1模型定义 215
11.1.2概率无向图模型的因子分解 217
11.2条件随机场的定义与形式 218
11.2.1条件随机场的定义 218
11.2.2条件随机场的参数化形式 220
11.2.3条件随机场的简化形式 221
11.2.4条件随机场的矩阵形式 223
11.3条件随机场的概率计算问题 224
11.3.1前向-后向算法 225
11.3.2概率计算 225
11.3.3期望值的计算 226
11.4条件随机场的学习算法 227
11.4.1改进的迭代尺度法 227
11.4.2拟牛顿法 230
11.5条件随机场的预测算法 231
本章概要 235
继续阅读 235
习题 236
参考文献 236
第12章 监督学习方法总结 237
第2篇 无监督学习 245
第13章 无监督学习概论 245
13.1无监督学习基本原理 245
13.2基本问题 246
13.3机器学习三要素 249
13.4无监督学习方法 249
本章概要 253
继续阅读 254
参考文献 254
第14章 聚类方法 255
14.1聚类的基本概念 255
14.1.1相似度或距离 255
14.1.2类或簇 258
14.1.3类与类之间的距离 260
14.2层次聚类 261
14.3 k均值聚类 263
14.3.1模型 263
14.3.2策略 263
14.3.3算法 264
14.3.4算法特性 266
本章概要 267
继续阅读 268
习题 269
参考文献 269
第15章 奇异值分解 271
15.1奇异值分解的定义与性质 271
15.1.1定义与定理 271
15.1.2紧奇异值分解与截断奇异值分解 276
15.1.3几何解释 279
15.1.4主要性质 280
15.2奇异值分解的计算 282
15.3奇异值分解与矩阵近似 286
15.3.1弗罗贝尼乌斯范数 286
15.3.2矩阵的最优近似 287
15.3.3矩阵的外积展开式 290
本章概要 292
继续阅读 294
习题 294
参考文献 295
第16章 主成分分析 297
16.1总体主成分分析 297
16.1.1基本想法 297
16.1.2定义和导出 299
16.1.3主要性质 301
16.1.4主成分的个数 306
16.1.5规范化变量的总体主成分 309
16.2样本主成分分析 310
16.2.1样本主成分的定义和性质 310
16.2.2相关矩阵的特征值分解算法 312
16.2.3数据矩阵的奇异值分解算法 315
本章概要 317
继续阅读 319
习题 320
参考文献 320
第17章 潜在语义分析 321
17.1单词向量空间与话题向量空间 321
17.1.1单词向量空间 321
17.1.2话题向量空间 324
17.2潜在语义分析算法 327
17.2.1矩阵奇异值分解算法 327
17.2.2例子 329
17.3非负矩阵分解算法 331
17.3.1非负矩阵分解 331
17.3.2潜在语义分析模型 332
17.3.3非负矩阵分解的形式化 332
17.3.4算法 333
本章概要 335
继续阅读 337
习题 337
参考文献 337
第18章 概率潜在语义分析 339
18.1概率潜在语义分析模型 339
18.1.1基本想法 339
18.1.2生成模型 340
18.1.3共现模型 341
18.1.4模型性质 342
18.2概率潜在语义分析的算法 345
本章概要 347
继续阅读 348
习题 348
参考文献 349
第19章 马尔可夫链蒙特卡罗法 351
19.1蒙特卡罗法 351
19.1.1随机抽样 351
19.1.2数学期望估计 353
19.1.3积分计算 353
19.2马尔可夫链 355
19.2.1基本定义 355
19.2.2离散状态马尔可夫链 356
19.2.3连续状态马尔可夫链 362
19.2.4马尔可夫链的性质 363
19.3马尔可夫链蒙特卡罗法 367
19.3.1基本想法 367
19.3.2基本步骤 369
19.3.3马尔可夫链蒙特卡罗法与统计学习 369
19.4 Metropolis-Hastings算法 370
19.4.1基本原理 370
19.4.2 Metropolis-Hastings算法 373
19.4.3单分量Metropolis-Hastings算法 374
19.5吉布斯抽样 375
19.5.1基本原理 376
19.5.2吉布斯抽样算法 377
19.5.3抽样计算 378
本章概要 379
继续阅读 381
习题 381
参考文献 383
第20章 潜在狄利克雷分配 385
20.1狄利克雷分布 385
20.1.1分布定义 385
20.1.2共轭先验 389
20.2潜在狄利克雷分配模型 390
20.2.1基本想法 390
20.2.2模型定义 391
20.2.3概率图模型 393
20.2.4随机变量序列的可交换性 394
20.2.5概率公式 395
20.3 LDA的吉布斯抽样算法 396
20.3.1基本想法 396
20.3.2算法的主要部分 397
20.3.3算法的后处理 399
20.3.4算法 399
20.4 LDA的变分EM算法 401
20.4.1变分推理 401
20.4.2变分EM算法 403
20.4.3算法推导 404
20.4.4算法总结 411
本章概要 411
继续阅读 413
习题 413
参考文献 413
第21章 PageRank算法 415
21.1 PageRank的定义 415
21.1.1基本想法 415
21.1.2有向图和随机游走模型 416
21.1.3 PageRank的基本定义 418
21.1.4 PageRank的一般定义 421
21.2 PageRank的计算 423
21.2.1迭代算法 423
21.2.2幂法 425
21.2.3代数算法 430
本章概要 430
继续阅读 432
习题 432
参考文献 432
第22章 无监督学习方法总结 435
22.1无监督学习方法的关系和特点 435
22.1.1各种方法之间的关系 435
22.1.2无监督学习方法 436
22.1.3基础机器学习方法 437
22.2话题模型之间的关系和特点 437
参考文献 438
附录A梯度下降法 439
附录B牛顿法和拟牛顿法 441
附录C拉格朗日对偶性 447
附录D矩阵的基本子空间 451
附录E KL散度的定义和狄利克雷分布的性质 455
索引 457