摘要

机器学习是计算机科学中发展最快的领域之一，实际应用广泛。这本教材的目标是从理论角度提供机器学习的入门知识和相关算法范式。本书全面地介绍了机器学习背后的基本思想和理论依据，以及将这些理论转化为实际算法的数学推导。在介绍了机器学习的基本内容后，本书还覆盖了此前的教材中一系列从未涉及过的内容。其中包括对学习的计算复杂度、凸性和稳定性的概念的讨论，以及重要的算法范式的介绍（包括随机梯度下降、神经元网络以及结构化输出学习）。同时，本书引入了最新的理论概念，包括PAC-贝叶斯方法和压缩界。本书为高等院校本科高年级和研究生入门阶段而设计，不仅计算机、电子工程、数学统计专业学生能轻松理解机器学习的基础知识和算法，其他专业的读者也能读懂。

深入理解机器学习 从原理到算法 内容简介

本书介绍机器学习方法的原理及方法，同时引入了学习的计算复杂性、凸性和稳定性、PAC贝叶斯方法、压缩界等概念，以及随机梯度下降、神经元网络和结构化输出等方法。作者既讲述重要的机器学习算法的工作原理和动机，还指出其固有的优势和缺点，是有兴趣了解机器学习理论和方法以及应用的学生和专业人员的良好教材或参考书。

深入理解机器学习 从原理到算法 目录

第1章 引论

1.1 什么是学习

1.2 什么时候需要机器学习

1.3 学习的种类

1.4 与其他领域的关系

1.5 如何阅读本书

1.6 符号

第一部分 理论基础

第2章 简易入门

2.1 一般模型——统计学习理论框架

2.2 经验风险最小化

2.3 考虑归纳偏置的经验风险最小化

2.4 练习

第3章 一般学习模型

3.1 PAC学习理论

3.2 更常见的学习模型

3.2.1 放宽可实现假设——不可知PAC学习

3.2.2 学习问题建模

3.3 小结

3.4 文献评注

3.5 练习

第4章 学习过程的一致收敛性

4.1 一致收敛是可学习的充分条件

4.2 有限类是不可知PAC可学习的

4.3 小结

4.4 文献评注

4.5 练习

第5章 偏差与复杂性权衡

5.1 “没有免费的午餐”定理

5.2 误差分解

5.3 小结

5.4 文献评注

5.5 练习

第6章 VC维

6.1 无限的类也可学习

6.2 VC维概述

6.3 实例

6.3.1 阈值函数

6.3.2 区间

6.3.3 平行于轴的矩形

6.3.4 有限类

6.3.5 VC维与参数个数

6.4 PAC学习的基本定理

6.5 定理6.7的证明

6.5.1 Sauer引理及生长函数

6.5.2 有小的有效规模的类的一致收敛性

6.6 小结

6.7 文献评注

6.8 练习

第7章 不一致可学习

7.1 不一致可学习概述

7.2 结构风险最小化

7.3 最小描述长度和奥卡姆剃刀

7.4 可学习的其他概念——一致收敛性

7.5 探讨不同的可学习概念

7.6 小结

7.7 文献评注

7.8 练习

第8章 学习的运行时间

8.1 机器学习的计算复杂度

8.2 ERM规则的实现

8.2.1 有限集

8.2.2 轴对称矩形

8.2.3 布尔合取式

8.2.4 学习三项析取范式

8.3 高效学习，而不通过合适的ERM

8.4 学习的难度

8.5 小结

8.6 文献评注

8.7 练习

第二部分 从理论到算法

第9章 线性预测

9.1 半空间

9.1.1 半空间类线性规划

9.1.2 半空间感知器

9.1.3 半空间的VC维

9.2 线性回归

9.2.1 最小平方

9.2.2 多项式线性回归

9.3 逻辑斯谛回归

9.4 小结

9.5 文献评注

9.6 练习

第10章 boosting

10.1 弱可学习

10.2 AdaBoost

10.3 基础假设类的线性组合

10.4 AdaBoost用于人脸识别

10.5 小结

10.6 文献评注

10.7 练习

第11章 模型选择与验证

11.1 用结构风险最小化进行模型选择

11.2 验证法

11.2.1 留出的样本集

11.2.2 模型选择的验证法

11.2.3 模型选择曲线

11.2.4 k折交叉验证

11.2.5 训练-验证-测试拆分

11.3 如果学习失败了应该做什么

11.4 小结

11.5 练习

第12章 凸学习问题

12.1 凸性、利普希茨性和光滑性

12.1.1 凸性

12.1.2 利普希茨性

12.1.3 光滑性

12.2 凸学习问题概述

12.2.1 凸学习问题的可学习性

12.2.2 凸利普希茨/光滑有界学习问题

12.3 替代损失函数

12.4 小结

12.5 文献评注

12.6 练习

第13章 正则化和稳定性

13.1 正则损失最小化

13.2 稳定规则不会过拟合

13.3 Tikhonov正则化作为稳定剂

13.3.1 利普希茨损失

13.3.2 光滑和非负损失

13.4 控制适合与稳定性的权衡

13.5 小结

13.6 文献评注

13.7 练习

第14章 随机梯度下降

14.1 梯度下降法

14.2 次梯度

14.2.1 计算次梯度

14.2.2 利普希茨函数的次梯度

14.2.3 次梯度下降

14.3 随机梯度下降

14.4 SGD的变型

14.4.1 增加一个投影步

14.4.2 变步长

14.4.3 其他平均技巧

14.4.4 强凸函数

14.5 用SGD进行学习

14.5.1 SGD求解风险极小化

14.5.2 SGD求解凸光滑学习问题的分析

14.5.3 SGD求解正则化损失极小化

14.6 小结

14.7 文献评注

14.8 练习

第15章 支持向量机

15.1 间隔与硬SVM

15.1.1 齐次情况

15.1.2 硬SVM的样本复杂度

15.2 软SVM与范数正则化

15.2.1 软SVM的样本复杂度

15.2.2 间隔、基于范数的界与维度

15.2.3 斜坡损失

15.3 最优化条件与“支持向量”

15.4 对偶

15.5 用随机梯度下降法实现软SVM

15.6 小结

15.7 文献评注

15.8 练习

第16章 核方法

16.1 特征空间映射

16.2 核技巧

16.2.1 核作为表达先验的一种形式

16.2.2 核函数的特征

16.3 软SVM应用核方法

16.4 小结

16.5 文献评注

16.6 练习

第17章 多分类、排序与复杂预测问题

17.1 一对多和一对一

17.2 线性多分类预测

17.2.1 如何构建Ψ

17.2.2 对损失敏感的分类

17.2.3 经验风险最小化

17.2.4 泛化合页损失

17.2.5 多分类SVM和SGD

17.3 结构化输出预测

17.4 排序

17.5 二分排序以及多变量性能测量

17.6 小结

17.7 文献评注

17.8 练习

第18章 决策树

18.1 采样复杂度

18.2 决策树算法

18.2.1 增益测量的实现方式

18.2.2 剪枝

18.2.3 实值特征基于阈值的拆分规则

18.3 随机森林

18.4 小结

18.5 文献评注

18.6 练习

第19章 最近邻

19.1 k近邻法

19.2 分析

19.2.1 1-NN准则的泛化界

19.2.2 “维数灾难”

19.3 效率实施

19.4 小结

19.5 文献评注

19.6 练习

第20章 神经元网络

20.1 前馈神经网络

20.2 神经网络学习

20.3 神经网络的表达力

20.4 神经网络样本复杂度

20.5 学习神经网络的运行时

20.6 SGD和反向传播

20.7 小结

20.8 文献评注

20.9 练习

第三部分 其他学习模型

第21章 在线学习

21.1 可实现情况下的在线分类

21.2 不可实现情况下的在线识别

21.3 在线凸优化

21.4 在线感知器算法

21.5 小结

21.6 文献评注

21.7 练习

第22章 聚类

22.1 基于链接的聚类算法

22.2 k均值算法和其他代价最小聚类

22.3 谱聚类

22.3.1 图割

22.3.2 图拉普拉斯与松弛图割算法

22.3.3 非归一化的谱聚类

22.4 信息瓶颈

22.5 聚类的进阶观点

22.6 小结

22.7 文献评注

22.8 练习

第23章 维度约简

23.1 主成分分析

23.1.1 当d＞＞m时一种更加有效的求解方法

23.1.2 应用与说明

23.2 随机投影

23.3 压缩感知

23.4 PCA还是压缩感知

23.5 小结

23.6 文献评注

23.7 练习

第24章 生成模型

24.1 极大似然估计

24.1.1 连续随机变量的极大似然估计

24.1.2 极大似然与经验风险最小化

24.1.3 泛化分析

24.2 朴素贝叶斯

24.3 线性判别分析

24.4 隐变量与EM算法

24.4.1 EM是交替最大化算法

24.4.2 混合高斯模型参数估计的EM算法

24.5 贝叶斯推理

24.6 小结

24.7 文献评注

24.8 练习

第25章 特征选择与特征生成

25.1 特征选择

25.1.1 滤波器

25.1.2 贪婪选择方法

25.1.3 稀疏诱导范数

25.2 特征操作和归一化

25.3 特征学习

25.4 小结

25.5 文献评注

25.6 练习

第四部分 高级理论

第26章 拉德马赫复杂度

26.1 拉德马赫复杂度概述

26.2 线性类的拉德马赫复杂度

26.3 SVM的泛化误差界

26.4 低e？范数预测器的泛化误差界

26.5 文献评注

第27章 覆盖数

27.1 覆盖

27.2 通过链式反应从覆盖到拉德马赫复杂度

27.3 文献评注

第28章 学习理论基本定理的证明

28.1 不可知情况的上界

28.2 不可知情况的下界

28.2.1 证明m（ε，δ）≥0.5log（1/（4δ））/ε2

28.2.2 证明m（ε，1/8）≥8d/ε2

28.3 可实现情况的上界

第29章 多分类可学习性

29.1 纳塔拉詹维

29.2 多分类基本定理

29.3 计算纳塔拉詹维

29.3.1 基于类的一对多

29.3.2 一般的多分类到二分类约简

29.3.3 线性多分类预测器

29.4 好的与坏的ERM

29.5 文献评注

29.6 练习

第30章 压缩界

30.1 压缩界概述

30.2 例子

30.2.1 平行于轴的矩形

30.2.2 半空间

30.2.3 可分多项式

30.2.4 间隔可分的情况

30.3 文献评注

第31章 PAC-贝叶斯

31.1 PAC-贝叶斯界

31.2 文献评注

31.3 练习

附录A 技术性引理

附录B 测度集中度

附录C 线性代数

参考文献

索引

深入理解机器学习 从原理到算法 精彩文摘

1．1什么是学习

我们首先来看几个存在于大自然的动物学习的例子。从这些熟悉的例子中可以看出，机器学习的一些基本问题也存在于自然界。

怯饵效应——老鼠学习躲避毒饵：当老鼠遇到有新颖外观或气味的食物时，它们首先会少量进食，随后的进食量将取决于事物本身的风味及其生理作用。如果产生不良反应，那么新的食物往往会与这种不良后果相关联，随之，老鼠不再进食这种食物。很显然，这里有一个学习机制在起作用——动物通过经验来获取判断食物安全性的技能。如果对一种食物过去的经验是负标记的，那么动物会预测在未来遇到它时也会产生负面影响。