第 2 章　机器学习概述

第一部分 · 机器学习基础课件 59 页讲义约 35 分钟Machine Learning Overview

▶ 浏览课件⬇ 课件 PDF（3.1 MB）📖 教材原书 PDF✎ 习题

学习目标

• 理解机器学习的基本概念与三要素：模型、学习准则、优化算法；
• 掌握常见损失函数，理解期望风险、经验风险与结构风险，以及过拟合与正则化；
• 掌握梯度下降、随机梯度下降与小批量梯度下降，理解学习率的作用；
• 以线性回归为例，掌握经验风险最小化、结构风险最小化、最大似然估计、最大后验估计四种参数估计方法及其联系；
• 理解偏差-方差分解、PAC 学习理论、没有免费午餐定理、奥卡姆剃刀与归纳偏置。

课件幻灯片

1 / 59

跳转到1. 机器学习概述2. 教学内容3. 机器学习 ≈ 构建一个映射函数4. 为什么要“机器学习”？5. 什么是机器学习？6. 机器学习的三要素7. 常见的机器学习问题8. 模型9. 学习准则10. 学习准则11. 最优化问题12. 梯度下降法（ Gradient Descent ）13. 学习率是十分重要的超参数！14. 随机梯度下降法15. 随机梯度下降法16. 机器学习 = 优化？17. 泛化错误18. 如何减少泛化错误？19. 正则化（regularization）20. 提前停止21. 线性回归22. 线性回归（Linear Regression）23. 优化方法24. 经验风险最小化25. 矩阵微积分26. 经验风险最小化27. 经验风险最小化28. 结构风险最小化29. 最大似然估计30. 关于概率的一些基本概念31. 概率的一些基本概念32. 概率的一些基本概念33. 概率的一些基本概念34. 例子35. 似然（Likelihood）36. 从概率角度来看线性回归37. 线性回归中的似然函数38. 最大似然估计39. 最大后验估计40. 最大后验估计41. 总结42. 多项式回归43. 一个例子：Polynomial Curve Fitting44. Which Degree of Polynomial?45. Controlling Overfitting: Regularization46. Controlling Overfitting: Regularization47. Controlling Overfitting: Dataset size48. 机器学习的几个关键点49. 常见的机器学习类型50. 如何选择一个合适的模型？51. 模型选择：偏差与方差52. PAC学习53. 样本复杂度54. 常用的定理55. 常用的定理56. 常用的定理57. 常用的定理58. 归纳偏置(Inductive Bias)59. 课后作业

PDF

提示：点击幻灯片左右两侧或使用 ← → 键翻页，手机上左右滑动；按 F 全屏。

讲义

2.1 什么是机器学习

现实世界的问题往往非常复杂，很难通过手工规则实现，因此需要“机器学习”。幻灯片 4 机器学习是指通过算法使得机器能从大量数据中学习规律，从而对新的样本做决策；这里的“规律”就是一个决策（预测）函数。幻灯片 5

我们假设样本 $(\mathit{x},y)$ 从某个未知的数据分布 $p_r(\mathit{x},y)$ 中独立同分布（i.i.d.）地采样得到，训练集记为 $\mathcal{D}=\{({\mathit{x}}^{(n)},y^{(n)}){\}}_{n=1}^N$。机器学习的目标是找到一个函数 $f^{\ast }(\mathit{x})$，使其对新样本的预测 $\hat{y}=f^{\ast }(\mathit{x})$ 尽可能准确。

常见的机器学习问题包括回归（输出连续值）、分类（输出离散类别）和聚类（无标签的分组）。幻灯片 7

2.2 机器学习的三要素

flowchart LR
  D["训练集 𝒟"] --> M["① 模型 f(x;θ)<br/>假设空间"]
  M --> C["② 学习准则<br/>损失函数 / 风险"]
  C --> O["③ 优化算法<br/>梯度下降"]
  O --> P["学到的参数 θ*"]

（1）模型。我们先确定一个假设空间 $\mathcal{F}$，即一个参数化的函数族 $\mathcal{F}=\{f(\mathit{x};\theta )\mid \theta \in {\mathbb{R}}^D\}$。以线性回归为例，模型为 $f(\mathit{x};\mathit{w},b)={\mathit{w}}^{\mathrm{\top }}\mathit{x}+b$。幻灯片 8 非线性模型可以写成 $f(\mathit{x};\theta )={\mathit{w}}^{\mathrm{\top }}\varphi (\mathit{x})+b$，其中 $\varphi (\mathit{x})$ 是非线性基函数；当 $\varphi$ 本身可学习时，就得到了神经网络。

（2）学习准则。用损失函数 $\mathcal{L}(y,f(\mathit{x};\theta ))$ 度量预测与真实值的差异：幻灯片 9

• 0-1 损失：$\mathcal{L}(y,f(\mathit{x};\theta ))=I(y\ne f(\mathit{x};\theta ))$，直观但不连续、导数为 0，难以优化；
• 平方损失：$\mathcal{L}(y,f(\mathit{x};\theta ))=\frac{1}{2}(y-f(\mathit{x};\theta ){)}^2$，常用于回归；
• 交叉熵损失、Hinge 损失等将在第 3 章介绍。

理想的目标是最小化期望风险 $\mathcal{R}(\theta )={\mathbb{E}}_{(\mathit{x},y)\sim p_r}[\mathcal{L}(y,f(\mathit{x};\theta ))]$，但真实分布未知，只能用训练集上的平均损失——经验风险来近似：幻灯片 10

$${\mathcal{R}}_{\mathcal{D}}^{emp}(\theta )=\frac{1}{N}\sum _{n=1}^N\mathcal{L}(y^{(n)},f({\mathit{x}}^{(n)};\theta )),{\theta }^{\ast }=\arg \underset{\theta }{min}{\mathcal{R}}_{\mathcal{D}}^{emp}(\theta ).$$

这就是经验风险最小化（ERM）准则。

（3）优化算法。确定了学习准则，机器学习问题就转化为一个最优化问题。幻灯片 11 最常用的是梯度下降法：幻灯片 12

$${\theta }_{t+1}={\theta }_t-\alpha \frac{\partial {\mathcal{R}}_{\mathcal{D}}(\theta )}{\partial \theta }={\theta }_t-\alpha \frac{1}{N}\sum _{n=1}^N\frac{\partial \mathcal{L}(y^{(n)},f({\mathit{x}}^{(n)};\theta ))}{\partial \theta },$$

其中搜索步长 $\alpha$ 称为学习率。学习率是非常重要的超参数：过大会在最优点附近震荡甚至发散，过小则收敛缓慢。幻灯片 13

批量梯度下降每次都要遍历全部样本，计算开销大。随机梯度下降（SGD）每次只随机取一个样本估计梯度并更新；小批量梯度下降每次取 $K$ 个样本（mini-batch），兼顾了计算效率与梯度估计的稳定性，是深度学习的默认做法。幻灯片 14 随机梯度是真实梯度的无偏估计，其引入的噪声还有助于逃离鞍点和尖锐的局部极小值。幻灯片 15

你可以在 梯度下降与优化器演示 中拖动学习率滑块，观察学习率过大或过小时的行为。

2.3 泛化与正则化

机器学习 = 优化？不是！ 经验风险最小化很容易导致模型在训练集上错误率很低、在未知数据上错误率很高，即过拟合，其原因往往是训练数据少、噪声大或模型过于复杂。幻灯片 16 反之，模型能力不足、在训练集上也表现不好则称为欠拟合。

期望风险与经验风险之间的差异称为泛化错误：幻灯片 17

$${\mathcal{G}}_{\mathcal{D}}(f)=\mathcal{R}(f)-{\mathcal{R}}_{\mathcal{D}}^{emp}(f).$$

机器学习的目标是减少泛化错误，这需要在“优化（经验风险最小）”与“正则化（降低模型复杂度）”之间取得平衡。幻灯片 18 正则化泛指所有损害优化、但有助于泛化的方法：幻灯片 19

• 增加优化约束：${\ell }_1/{\ell }_2$ 约束、数据增强；
• 干扰优化过程：权重衰减、随机梯度下降、提前停止。

结构风险最小化（SRM）在经验风险上加一个正则化项：

$${\theta }^{\ast }=\arg \underset{\theta }{min}\frac{1}{N}\sum _{n=1}^N\mathcal{L}(y^{(n)},f({\mathit{x}}^{(n)};\theta ))+\frac{1}{2}\lambda \parallel \theta {\parallel }^2.$$

提前停止：使用一个验证集测试每次迭代后的参数，当验证集上的错误率不再下降时就停止迭代。幻灯片 20

2.4 线性回归：四种参数估计方法

线性回归的模型为 $f(\mathit{x};\mathit{w},b)={\mathit{w}}^{\mathrm{\top }}\mathit{x}+b$。为简化记号，引入增广特征向量 $\mathit{x}\leftarrow \mathit{x}\oplus 1$ 与增广权重向量 $\mathit{w}\leftarrow \mathit{w}\oplus b$，模型简写为 $f(\mathit{x};\mathit{w})={\mathit{w}}^{\mathrm{\top }}\mathit{x}$。幻灯片 22 记 $\mathit{X}=[{\mathit{x}}^{(1)},\cdots ,{\mathit{x}}^{(N)}]\in {\mathbb{R}}^{(D+1)\times N}$，$\mathit{y}=[y^{(1)},\cdots ,y^{(N)}{]}^{\mathrm{\top }}$。

（1）经验风险最小化：最小二乘法。采用平方损失，幻灯片 24 幻灯片 26

$$\mathcal{R}(\mathit{w})=\sum _{n=1}^N\frac{1}{2}(y^{(n)}-{\mathit{w}}^{\mathrm{\top }}{\mathit{x}}^{(n)}{)}^2=\frac{1}{2}\parallel \mathit{y}-{\mathit{X}}^{\mathrm{\top }}\mathit{w}{\parallel }^2.$$

利用矩阵微积分（分母布局）幻灯片 25，令梯度为 0：

$$\frac{\partial \mathcal{R}(\mathit{w})}{\partial \mathit{w}}=-\mathit{X}(\mathit{y}-{\mathit{X}}^{\mathrm{\top }}\mathit{w})=0\Rightarrow {\mathit{w}}^{\ast }=(\mathit{X}{\mathit{X}}^{\mathrm{\top }}{)}^{-1}\mathit{X}\mathit{y}.$$

这要求 $\mathit{X}{\mathit{X}}^{\mathrm{\top }}$ 可逆，即特征之间线性无关。幻灯片 27

（2）结构风险最小化：岭回归。当特征存在共线性或样本数少于特征维数时，$\mathit{X}{\mathit{X}}^{\mathrm{\top }}$ 不可逆或数值不稳定。给对角线加一个常数 $\lambda \mathit{I}$，等价于最小化 幻灯片 28

$$\mathcal{R}(\mathit{w})=\frac{1}{2}\parallel \mathit{y}-{\mathit{X}}^{\mathrm{\top }}\mathit{w}{\parallel }^2+\frac{1}{2}\lambda \parallel \mathit{w}{\parallel }^2\Rightarrow {\mathit{w}}^{\ast }=(\mathit{X}{\mathit{X}}^{\mathrm{\top }}+\lambda \mathit{I}{)}^{-1}\mathit{X}\mathit{y},$$

这就是岭回归，$\lambda >0$ 为正则化系数。

（3）最大似然估计。从概率角度看，假设 $y$ 由 ${\mathit{w}}^{\mathrm{\top }}\mathit{x}$ 加上高斯噪声生成：$y={\mathit{w}}^{\mathrm{\top }}\mathit{x}+ϵ$，$ϵ\sim \mathcal{N}(0,{\sigma }^2)$，即 幻灯片 36

$$p(y\mid \mathit{x};\mathit{w},\sigma )=\mathcal{N}(y;{\mathit{w}}^{\mathrm{\top }}\mathit{x},{\sigma }^2)=\frac{1}{\sqrt{2\pi }\sigma }\exp (-\frac{(y-{\mathit{w}}^{\mathrm{\top }}\mathit{x}{)}^2}{2{\sigma }^2}).$$

参数 $\mathit{w}$ 在训练集上的似然函数为 $p(\mathit{y}\mid \mathit{X};\mathit{w},\sigma )=\prod _{n=1}^{N}p(y^{(n)}\mid {\mathit{x}}^{(n)};\mathit{w},\sigma )$。幻灯片 37 最大似然估计（MLE）寻找使似然最大的参数。对数似然为

$$\log p(\mathit{y}\mid \mathit{X};\mathit{w},\sigma )=-\frac{1}{2{\sigma }^2}\sum _{n=1}^N(y^{(n)}-{\mathit{w}}^{\mathrm{\top }}{\mathit{x}}^{(n)}{)}^2+\text{const},$$

令其导数为 0，得到 ${\mathit{w}}^{ML}=(\mathit{X}{\mathit{X}}^{\mathrm{\top }}{)}^{-1}\mathit{X}\mathit{y}$——与最小二乘解完全相同。幻灯片 38 也就是说，平方损失隐含了高斯噪声假设。

概率基础回顾：概率分布、伯努利分布、二项分布、高斯分布、条件概率与贝叶斯公式 $p(y\mid x)={\displaystyle \frac{p(x\mid y)p(y)}{p(x)}}$，以及似然、先验、后验的含义见 幻灯片 30–幻灯片 35。

（4）最大后验估计。最大似然估计在训练数据少时容易过拟合。贝叶斯观点把参数 $\mathit{w}$ 也看作随机变量，并给它一个先验，例如各向同性高斯先验 $p(\mathit{w};\nu )=\mathcal{N}(\mathit{w};\mathbf{0},{\nu }^2\mathit{I})$。由贝叶斯公式，后验正比于“似然 × 先验”：幻灯片 39 幻灯片 40

$$p(\mathit{w}\mid \mathit{X},\mathit{y};\nu ,\sigma )\propto p(\mathit{y}\mid \mathit{X},\mathit{w};\sigma )p(\mathit{w};\nu ).$$

最大后验估计（MAP）取后验最大的参数，取对数后

$$\log p(\mathit{w}\mid \mathit{X},\mathit{y})=-\frac{1}{2{\sigma }^2}\parallel \mathit{y}-{\mathit{X}}^{\mathrm{\top }}\mathit{w}{\parallel }^2-\frac{1}{2{\nu }^2}{\mathit{w}}^{\mathrm{\top }}\mathit{w}+\text{const},$$

这恰好等价于 $\lambda ={\sigma }^2/{\nu }^2$ 的岭回归。四种方法的关系可以总结为：幻灯片 41

	无先验	引入先验
平方误差	经验风险最小化	结构风险最小化
概率	最大似然估计	最大后验估计

2.5 多项式回归：一个过拟合的例子

用 $M$ 次多项式 $f(x;\mathit{w})=\sum _{m=0}^M{w}_m{x}^m$ 拟合由 $\sin (2\pi x)$ 加噪声生成的 10 个样本（Bishop PRML 第 1 章的经典例子）。幻灯片 43 $M=0,1$ 时欠拟合；$M=3$ 拟合良好；$M=9$ 时曲线穿过所有训练点，训练误差为 0，却剧烈振荡——典型的过拟合，这是一个模型选择问题。幻灯片 44 随着 $M$ 增大，系数的绝对值会急剧变大。两种控制过拟合的方法是：对大系数进行惩罚（正则化）幻灯片 45，以及增加训练数据。幻灯片 47

2.6 机器学习的几个关键点

机器学习的类型。按训练样本与反馈方式，可分为监督学习（回归、分类）、无监督学习（聚类、密度估计、特征学习）和强化学习（通过与环境交互、根据奖励学习）。幻灯片 49

偏差-方差分解。拟合能力强的模型复杂度高、容易过拟合；限制复杂度又可能欠拟合，如何选择模型？以回归为例，设 $f^{\ast }(\mathit{x})={\mathbb{E}}_{y\sim p_r(y|\mathit{x})}[y]$ 为最优模型，$f_{\mathcal{D}}(\mathit{x})$ 为在训练集 $\mathcal{D}$ 上学到的模型，则期望错误可以分解为 幻灯片 50

$${\mathbb{E}}_{\mathcal{D}}[(f_{\mathcal{D}}(\mathit{x})-f^{\ast }(\mathit{x}){)}^2]=\underset{(\text{偏差}{)}^2}{\underbrace{({\mathbb{E}}_{\mathcal{D}}[f_{\mathcal{D}}(\mathit{x})]-f^{\ast }(\mathit{x}){)}^2}}+\underset{\text{方差}}{\underbrace{{\mathbb{E}}_{\mathcal{D}}[(f_{\mathcal{D}}(\mathit{x})-{\mathbb{E}}_{\mathcal{D}}[f_{\mathcal{D}}(\mathit{x})]{)}^2]}},$$

再加上由数据噪声决定的、不可约减的部分 $\epsilon$。偏差衡量模型平均预测与最优预测的差距（拟合能力），方差衡量模型在不同训练集上的波动（对数据的敏感度）。模型越复杂，偏差越小、方差越大。集成模型是降低方差的有效方法。幻灯片 51

PAC 学习。根据大数定律，当训练集大小 $|\mathcal{D}|\to \mathrm{\infty }$ 时泛化错误趋于 0。但有限样本下，我们只能要求以一定概率学到一个近似正确的假设，这就是可能近似正确（Probably Approximately Correct, PAC）学习：幻灯片 52

$$P((\mathcal{R}(f)-{\mathcal{R}}_{\mathcal{D}}^{emp}(f))\le ϵ)\ge 1-\delta ,$$

其中 $ϵ$（$0<ϵ<0.5$）表示“近似正确”，$\delta$（$0<\delta <0.5$）表示“可能”。对有限假设空间 $\mathcal{F}$，达到上述要求所需的样本数（样本复杂度）满足 幻灯片 53

$$N(ϵ,\delta )\ge \frac{1}{2{ϵ}^2}(\log |\mathcal{F}|+\log \frac{2}{\delta }).$$

模型越复杂（假设空间越大），需要的样本越多；为提高泛化能力，通常需要正则化来限制模型复杂度。

几个常用定理与原则：幻灯片 55

• 没有免费午餐定理（NFL）：对于基于迭代的最优化算法，不存在某种算法对所有问题都有效；如果一个算法对某些问题有效，那么它一定在另一些问题上比纯随机搜索更差。不能脱离具体问题谈算法优劣。
• 丑小鸭定理：丑小鸭与白天鹅之间的区别和两只白天鹅之间的区别一样大——世界上不存在相似性的客观标准，一切相似性标准都是主观的。幻灯片 56
• 奥卡姆剃刀：如无必要，勿增实体。简单的模型泛化能力更好，这也是正则化的思想来源。幻灯片 57
• 归纳偏置：学习算法对问题所做的假设。例如最近邻分类器假设特征空间中一个小的局部区域内的样本大多属于同一类；朴素贝叶斯假设特征条件独立。在贝叶斯学习中，归纳偏置也常称为先验。幻灯片 58

本章小结

• 机器学习三要素：模型（假设空间）、学习准则（损失与风险）、优化算法（梯度下降及其随机版本）。
• 目标是降低泛化错误，而不仅仅是最小化训练误差；正则化在优化与泛化之间权衡。
• 线性回归的四种估计方法：最小二乘 ⇔ 最大似然（高斯噪声），岭回归 ⇔ 最大后验（高斯先验）。
• 偏差-方差分解解释了模型复杂度的权衡；PAC 学习给出了样本复杂度与模型复杂度的关系；NFL 定理提醒我们算法需要匹配问题，归纳偏置不可避免。

思考题与习题

1. （推导） 推导最小二乘解 ${\mathit{w}}^{\ast }=(\mathit{X}{\mathit{X}}^{\mathrm{\top }}{)}^{-1}\mathit{X}\mathit{y}$ 与岭回归解 $(\mathit{X}{\mathit{X}}^{\mathrm{\top }}+\lambda \mathit{I}{)}^{-1}\mathit{X}\mathit{y}$，并说明为什么后者对任意 $\lambda >0$ 都可逆。
2. （推导） 若噪声服从拉普拉斯分布 $p(ϵ)\propto \exp (-|ϵ|/b)$，最大似然估计对应什么损失函数？若参数先验为拉普拉斯分布，最大后验估计对应什么正则项？
3. （概念） 在一个分类任务中，0-1 损失为什么不适合直接用梯度下降优化？
4. （分析） 某模型训练准确率 99%、验证准确率 70%；另一模型训练准确率 72%、验证准确率 70%。分别判断偏差与方差的高低，并给出改进建议。
5. （证明） 证明偏差-方差分解公式（提示：在平方项中加减 ${\mathbb{E}}_{\mathcal{D}}[f_{\mathcal{D}}(\mathit{x})]$）。
6. （编程） 生成 $y=\sin (2\pi x)+ϵ$ 的 10 个样本，分别用 0、1、3、9 次多项式拟合，画出训练误差与测试误差随阶数的变化；再对 9 次多项式加入 ${\ell }_2$ 正则，观察不同 $\lambda$ 的效果。
7. （编程） 分别用闭式解、批量梯度下降和小批量 SGD 求解线性回归，比较收敛曲线，并尝试 3 种不同学习率。

部分提示

• 第 1 题：$\mathit{X}{\mathit{X}}^{\mathrm{\top }}$ 半正定，加上 $\lambda \mathit{I}$ 后所有特征值至少为 $\lambda >0$。
• 第 2 题：拉普拉斯噪声 → 绝对值损失（${\ell }_1$ 损失）；拉普拉斯先验 → ${\ell }_1$ 正则（Lasso）。
• 第 4 题：前者低偏差、高方差（过拟合），可加正则、增数据、减小模型；后者高偏差（欠拟合），可增大模型容量、改进特征。

延伸阅读

• 教材：邱锡鹏《神经网络与深度学习》第 2 章「机器学习概述」，附录 B（线性代数、微积分、优化）、附录 D（概率论）。
• Bishop C M. Pattern Recognition and Machine Learning, 第 1、3 章（多项式曲线拟合、线性回归的贝叶斯视角）。
• 实践：nndl-practice 第 2 章「机器学习概述」。
• 交互：梯度下降与优化器。
• 第二版对应章节：第 2 章「机器学习概述」。