机器学习基础

本书从概率近似正确（PAC）理论出发探讨机器学习的基础理论与典型算法，包括PAC学习框架、VC-维、支持向量机、核方法、在线学习、多分类、排序、回归、降维、强化学习等丰富的内容。此外，附录部分简要回顾了与机器学习密切相关的概率论、凸优化、矩阵以及范数等必要的预备知识。

本书重在介绍典型算法的理论支撑并指出算法在实际应用中的关键点，注重理论细节与证明过程，可作为高等院校机器学习、统计学等课程的教材，或作为相关领域研究人员的参考读物。

 

译者序

前言

第1章　引言1

　1.1　应用与问题1

　1.2　定义与术语2

　1.3　交叉验证4

　1.4　学习情境5

　1.5　本书概览6

第2章　PAC学习框架8

　2.1　PAC学习模型8

　2.2　对有限假设集的学习保证——一致的情况12

　2.3　对有限假设集的学习保证——不一致的情况16

　2.4　泛化性18

　　2.4.1　确定性与随机性情境18

　　2.4.2　贝叶斯误差与噪声19

　　2.4.3　估计误差与近似误差19

　　2.4.4　模型选择20

　2.5　文献评注21

　2.6　习题22

第3章　Rademacher复杂度和VC-维25

　3.1　Rademacher复杂度25

　3.2　生长函数29

　3.3　VC-维31

　3.4　下界36

　3.5　文献评注41

　3.6　习题42

第4章　支持向量机47

　4.1　线性分类47

　4.2　可分情况下的支持向量机48

　　4.2.1　原始优化问题48

　　4.2.2　支持向量49

　　4.2.3　对偶优化问题50

　　4.2.4　留一法51

　4.3　不可分情况下的支持向量机52

　　4.3.1　原始优化问题53

　　4.3.2　支持向量54

　　4.3.3　对偶优化问题55

　4.4　间隔理论56

　4.5　文献评注62

　4.6　习题62

第5章　核方法65

　5.1　引言65

　5.2　正定对称核67

　　5.2.1　定义67

　　5.2.2　再生核希尔伯特空间69

　　5.2.3　性质70

　5.3　基于核的算法73

　　5.3.1　具有PDS核的SVM73

　　5.3.2　表示定理74

　　5.3.3　学习保证75

　5.4　负定对称核76

　5.5　序列核78

　　5.5.1　加权转换器79

　　5.5.2　有理核82

　5.6　文献评注85

　5.7　习题85

第6章　boosting89

　6.1　引言89

　6.2　AdaBoost算法90

　　6.2.1　经验误差的界92

　　6.2.2　与坐标下降的关系93

　　6.2.3　与逻辑回归的关系94

　　6.2.4　实践中的标准使用方式95

　6.3　理论结果95

　　6.3.1　基于VC-维的分析96

　　6.3.2　基于间隔的分析96

　　6.3.3　间隔最大化100

　　6.3.4　博弈论解释101

　6.4　讨论103

　6.5　文献评注104

　6.6　习题105

第7章　在线学习108

　7.1　引言108

　7.2　有专家建议的预测109

　　7.2.1　错误界和折半算法109

　　7.2.2　加权多数算法110

　　7.2.3　随机加权多数算法111

　　7.2.4　指数加权平均算法114

　7.3　线性分类117

　　7.3.1　感知机算法117

　　7.3.2　Winnow算法122

　7.4　在线到批处理的转换124

　7.5　与博弈论的联系127

　7.6　文献评注127

　7.7　习题128

第8章　多分类133

　8.1　多分类问题133

　8.2　泛化界134

　8.3　直接型多分类算法139

　　8.3.1　多分类SVM139

　　8.3.2　多分类boosting算法140

　　8.3.3　决策树141

　8.4　类别分解型多分类算法144

　　8.4.1　一对多144

　　8.4.2　一对一145

　　8.4.3　纠错编码146

　8.5　结构化预测算法148

　8.6　文献评注149

　8.7　习题150

第9章　排序152

　9.1　排序问题152

　9.2　泛化界153

　9.3　使用SVM进行排序155

　9.4　RankBoost156

　　9.4.1　经验误差界158

　　9.4.2　与坐标下降的关系159

　　9.4.3　排序问题集成算法的间隔界160

　9.5　二部排序161

　　9.5.1　二部排序中的boosting算法162

　　9.5.2　ROC曲线下面积164

　9.6　基于偏好的情境165

　　9.6.1　两阶段排序问题166

　　9.6.2　确定性算法167

　　9.6.3　随机性算法168

　　9.6.4　关于其他损失函数的扩展168

　9.7　讨论169

　9.8　文献评注170

　9.9　习题171

第10章　回归172

　10.1　回归问题172

　10.2　泛化界173

　　10.2.1　有限假设集173

　　10.2.2　Rademacher复杂度界174

　　10.2.3　伪维度界175

　10.3　回归算法177

　　10.3.1　线性回归178

　　10.3.2　核岭回归179

　　10.3.3　支持向量回归182

　　10.3.4　Lasso186

　　10.3.5　组范数回归算法188

　　10.3.6　在线回归算法189

　10.4　文献评注190

　10.5　习题190

第11章　算法稳定性193

　11.1　定义193

　11.2　基于稳定性的泛化保证194

　11.3　基于核的正则化算法的稳定性196

　　11.3.1　应用于回归算法：SVR和KRR198

　　11.3.2　应用于分类算法：SVM200

　　11.3.3　讨论200

　11.4　文献评述201

　11.5　习题201

第12章　降维203

　12.1　主成分分析204

　12.2　核主成分分析205

　12.3　KPCA和流形学习206

　　12.3.1　等距映射206

　　12.3.2　拉普拉斯特征映射207

　　12.3.3　局部线性嵌入207

　12.4　Johnson-Lindenstrauss引理208

　12.5　文献评注210

　12.6　习题210

第13章　学习自动机和语言212

　13.1　引言212

　13.2　有限自动机213

　13.3　高效精确学习214

　　13.3.1　被动学习214

　　13.3.2　通过查询学习215

　　13.3.3　通过查询学习自动机216

　13.4　极限下的识别220

　13.5　文献评注224

　13.6　习题225

第14章　强化学习227

　14.1　学习情境227

　14.2　马尔可夫决策过程模型228

　14.3　策略229

　　14.3.1　定义229

　　14.3.2　策略值229

　　14.3.3　策略评估230

　　14.3.4　最优策略230

　14.4　规划算法231

　　14.4.1　值迭代231

　　14.4.2　策略迭代233

　　14.4.3　线性规划235

　14.5　学习算法235

　　14.5.1　随机逼近236

　　14.5.2　TD（0）算法239

　　14.5.3　Q-学习算法240

　　14.5.4　SARSA242

　　14.5.5　TD（λ）算法242

　　14.5.6　大状态空间243

　14.6　文献评注244

结束语245

附录A　线性代数回顾246

附录B　凸优化251

附录C　概率论回顾257

附录D　集中不等式264

附录E　符号273

索引274

参考文献

　参考文献为网络资源，请访问华章网站www.hzbook.com下载。——编辑注