4 机器学习：监督学习

4.1 机器学习基本概念

机器学习是智能体从数据中自动学习知识的一种人工智能方法。其目标是从原始数据中提取特征，学习一个映射函数$f$将特征映射到语义空间，寻找数据和任务目标之间的关系。

4.1.1 机器学习的种类

机器学习通常分为三大类：

• 监督学习：给定带标签信息的数据集 $\mathcal{D}=\{({\mathbf{x}}_i,{\mathbf{y}}_i){\}}_{i=1}^N$，学习从输入 $x$ 到输出 $y$ 的映射。常用于回归（输出为连续值）和分类（输出为离散类别）。
• 无监督学习：数据无标签，给定 D={xi}i=1N\mathcal{D} = \{\boldsymbol{x}_i\}_{i=1}^{N}D={xi​}i=1N​，目标是挖掘数据内在结构。常用于聚类和降维。
• 强化学习：一种序列决策学习方法，智能体通过与环境的交互，根据奖励/惩罚来学习在不同状态下如何选择最优行动。

此外，介于监督学习和无监督学习之间还有半监督学习，它依赖于少量标注数据和大量未标注数据。

4.1.2 监督学习的基本概念

监督学习从标注数据出发，学习一个映射函数 $f$。模型的预测结果 $f(x_i)$ 与真实值 $y_i$ 之间的差异由损失函数衡量，训练目标是使所有样本的“损失和”最小。

常见损失函数

损失函数名称	定义
0-1损失	$Loss(y_i,f(x_i))=\{\begin{array}{ll}1,& f(x_i)\ne y_i\\ 0,& f(x_i)=y_i\end{array}$
平方损失	$Loss(y_i,f(x_i))=(y_i-f(x_i){)}^2$
绝对损失	$Loss(y_i,f(x_i))=|y_i-f(x_i)|$
对数损失	$Loss(y_i,P(y_i|x_i))=-\log P(y_i|x_i)$

风险与泛化

• 经验风险：模型在训练集上的平均损失。 $\frac{1}{n}{\sum }_{i=1}^{n}Loss(y_i,f(x_i))$

• 期望风险：模型在真实数据分布上的平均损失。 ${\int }_{x,y}Loss(y,f(x))P(x,y)dxdy$

• 目标：机器学习的目标是最小化期望风险，但现实中只能通过最小化经验风险来近似。

• 结构风险最小化：为防止过拟合，在经验风险上加入表示模型复杂度的正则化项（惩罚项）： $\frac{1}{n}{\sum }_{i=1}^{n}Loss(y_i,f(x_i))+\lambda J(f)$

  • $J(f)$ 为模型复杂度，$\lambda$ 为惩罚系数，用于平衡经验风险与模型复杂度。

• 模型泛化能力关系

经验风险	期望风险	泛化能力
小	小	强
小	大	过学习 (过拟合)
大	大	欠学习 (欠拟合)
大	小	“神仙算法”

判别方法与生成方法

• 判别方法：直接学习决策函数 $f(X)$ 或条件概率分布 $P(Y|X)$。典型模型：回归、SVM、AdaBoost。
• 生成方法：学习数据和类别的联合概率分布 $P(X,Y)$，再通过贝叶斯公式求取后验概率 $P(Y|X)$。典型模型：贝叶斯方法、隐马尔可夫模型。

4.2 回归分析

分析不同变量之间存在的依赖关系的方法。线性回归模型假设关系是线性的。

4.2.1 一元线性回归

• 模型假设：$y=ax+b$
• 核心思想：寻找一条直线，使得所有样本点到该直线的残差平方和（RSS） 最小。
• 优化目标：${\min }_{a,b}L(a,b)={\sum }_{i=1}^n(y_i-a{x}_i-b{)}^2$
• 求解方法（最小二乘法）：分别对 $a$ 和 $b$ 求偏导并令其为0，解得参数。
  • $b=\bar{y}-a\bar{x}$
  • $a=\frac{{\sum }_{i=1}^n{x}_i{y}_i-n\bar{x}\bar{y}}{{\sum }_{i=1}^n{x}_i^2-n{\bar{x}}^2}$

4.2.2 多元线性回归

• 模型假设：$f(x_i)=a_0+{\sum }_{j=1}^D{a}_j{x}_{i,j}=a^T{x}_i$ （将 $a_0$ 视为 $x_{i,0}=1$ 的系数）
• 优化目标：最小化均方误差 $J(a)=(y-X^{T}a{)}^T(y-X^{T}a)$
• 闭式解：$a=(X{X}^T{)}^{-1}Xy$

4.2.3 逻辑斯蒂回归 (对数几率回归)

• 目的：解决线性回归对离群点敏感的问题，并用于二分类任务。

• 模型：在线性回归基础上套上 Sigmoid 函数将输出压缩到 $(0,1)$ 之间，产生概率意义。

  • $y=\frac{1}{1+e^{-(w^{T}x+b)}}=P(y=1|x)$

• Sigmoid 函数性质：单调递增，值域 $(0,1)$，$z=0$ 时输出为 $0.5$。

• 损失函数：基于极大似然估计推导出对数损失函数 (交叉熵)。

  $$J(\theta )=-\sum _{i=1}^n[y_i\log (h_{\theta }(x_i))+(1-y_i)\log (1-h_{\theta }(x_i))]$$

• 求解方法（梯度下降）：通过迭代调整参数，沿梯度负方向寻找最小损失。
  迭代公式：${\theta }_j={\theta }_j-\eta \frac{\partial J(\theta )}{\partial {\theta }_j}$
  求偏导并代入后得：${\theta }_j={\theta }_j-\eta {\sum }_{i=1}^n(y_i-h_{\theta }(x_i))x_i$

  • $\eta$ 为学习率。

4.3 决策树

一种通过树形结构进行分类的方法。每个非叶子结点代表对一个属性的判断，每个分支代表一个判断结果，每个叶结点代表一种分类结果。

4.3.2 构建决策树

决策树构建的关键是选择划分属性的顺序，目的是使分支结点的“纯度”越来越高。

纯度度量指标

• 信息熵：衡量样本集合的不确定性。熵越小，纯度越高。
  $$E(D)=-\sum _{k=1}^K{p}_k{\log }_2{p}_k$$

• 信息增益：使用某个属性 $A$ 划分前后，信息熵减少的量。信息增益越大，意味着使用属性 $A$ 划分所得到的“纯度提升”越大。
  $$Gain(D,A)=Ent(D)-\sum _{i=1}^n\frac{|D_i|}{|D|}Ent(D_i)$$
  缺点：偏向于选择取值数目较多的属性。

• 信息增益率：对信息增益进行改进，对取值数目多的属性增加惩罚项。
  $$Gain\_ratio=\frac{Gain(D,A)}{IV(a)}，IV(a)=-\sum _{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$$

• 基尼系数：另一种衡量纯度的指标，计算更简便。
  $$Gini(D)=1-\sum _{k=1}^K{p}_k^2$$

4.4 线性判别分析 (LDA)

一种监督学习的降维方法。核心思想是，将数据投影到一个低维空间，使得同类样本尽可能靠近（类内方差小），不同类样本尽可能远离（类间间隔大）。

• 二分类问题优化目标：$J(w)=\frac{\Vert m_2-m_1{\Vert }_2^2}{s_1+s_2}=\frac{w^T{S}_{b}w}{w^T{S}_{w}w}$
  • $S_b=(m_2-m_1)(m_2-m_1{)}^T$ 为类间散度矩阵。
  • $S_w={\Sigma }_1+{\Sigma }_2$ 为类内散度矩阵。
• 求解：通过拉格朗日乘子法求解，得到最佳投影方向 $w=S_w^{-1}(m_2-m_1)$。
• 降维维度：LDA 降维后的维度最多为 $\min (K-1,d)$。
• 与 PCA 的区别：PCA 是无监督的，目标是让投影后方差最大；LDA 是有监督的，目标是让投影后类内聚合、类间分离。

4.5 Ada Boosting (自适应提升)

核心思想：将一个复杂的分类任务分解为若干个子任务，通过集成多个弱分类器（精度略高于随机猜测）来构建一个强分类器。

• 理论基础：PAC (概率近似正确) 可学习理论，证明了强可学习与弱可学习是等价的。

4.5.2 Ada Boosting 算法

算法通过序列化迭代，每一轮都根据上一轮的结果调整样本权重，最终将各轮弱分类器加权组合成强分类器。

1. 初始化样本权重：每个样本的权重相等，$w_{1,i}=\frac{1}{N}$。
2. 迭代训练 $M$ 个弱分类器：
   • 训练：基于当前样本权重 $D_m$ 训练一个弱分类器 $G_m(x)$。
   • 计算误差：$er{r}_m={\sum }_{i=1}^N{w}_{m,i}I(G_m(x_i)\ne y_i)$
   • 计算权重：为当前分类器 $G_m$ 计算在最终强分类器中的权重 ${\alpha }_m=\frac{1}{2}\ln \frac{1-er{r}_m}{er{r}_m}$。误差越小，权重越大。
   • 更新样本权重：增加被 $G_m$ 错误分类的样本的权重，减小被正确分类样本的权重。
     $$w_{m+1,i}=\frac{w_{m,i}}{Z_m}\exp (-{\alpha }_m{y}_i{G}_m(x_i))$$
3. 组合强分类器：$G(x)=sign\left({\sum }_{m=1}^M{\alpha }_m{G}_m(x)\right)$

• 本质：AdaBoost 算法是在以指数损失函数为优化目标，采用分步优化的方式，不断拟合前向阶梯模型的加法模型。

4.6 支持向量机 (SVM)

核心思想：寻找一个超平面，使得其不仅能分开两类样本，而且分类间隔最大。基于结构风险最小化原则，旨在平衡经验风险和置信风险。

4.6.1 VC维与结构风险最小化

• 期望风险 $\le$ 经验风险 $+$ 置信风险。
• VC维：衡量假设空间复杂度的指标。VC维越高，模型越复杂，置信风险越大。
• 结构风险最小化：在保证分类精度（经验风险小）的同时，尽量增大分类间隔（从而降低VC维），以控制期望风险。

4.6.2 线性可分支持向量机

• 目标：最大化分类间隔 $\gamma =\frac{2}{\Vert w\Vert }$。
• 优化问题：
  $$\underset{w,b}{\min }\frac{1}{2}{w}^{T}w$$
  $$\text{s.t. }{y}_i(w^T{x}_i+b)\ge 1,i=1,2,...,n$$
• 支持向量：距离超平面最近的，使 $y_i(w^T{x}_i+b)=1$ 成立的样本点。最终模型只与支持向量有关。

4.6.3 松弛变量与软间隔

若数据不完全线性可分，可引入“软间隔”，允许部分样本被分错。

• 引入松弛变量 ${\xi }_i\ge 0$：表示第 $i$ 个样本被分类错误所付出的代价。
• 优化目标：
  $$\underset{w,b}{\min }\frac{1}{2}{w}^{T}w+C\sum _{i=1}^n{\xi }_i$$
  $$\text{s.t. }{y}_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$
• $C>0$ 为惩罚参数，用于平衡间隔最大化和误分类点个数。

4.6.4 核函数

若数据在原始空间线性不可分，可将样本映射到一个高维特征空间，使其在此空间内线性可分。

• 核函数 $\kappa (x_i,x_j)$：定义在原始空间中，其计算结果等于两个样本在某个高维特征空间中的内积，即 $\kappa (x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$。
• 这样，无需显式计算高维特征向量的 $\varphi (x)$，避免了“维数灾难”。
• 常见核函数：线性核、多项式核、径向基函数(RBF)核、Sigmoid 核。

4.7 生成学习模型

与判别式方法不同，生成式方法学习联合概率分布 $P(X,C)$。

• 核心公式：根据贝叶斯公式，后验概率 $P(c_i|x)=\frac{P(x|c_i)P(c_i)}{P(x)}$，分类时选择后验概率最大的类别。
• 关键思想：模型“学会”了数据是如何生成的，即学习到了似然概率 $P(x|c_i)$ 和先验概率 $P(c_i)$。
• 典型模型：隐马尔可夫模型(HMM)、隐狄利克雷分布(LDA)。
• 与判别式模型对比：
  • 判别模型：直接学习决策边界，渐近误差更小。
  • 生成模型：对数据分布的建模更充分，收敛到自身渐近误差的速度更快，在训练样本较少时可能表现更好。

4.8 小结

监督学习从标注数据中学习从输入到输出的映射函数。本章介绍了多种经典模型：回归分析拟合变量关系；决策树通过树状规则分类；线性判别分析实现有监督的降维；Ada Boosting集成多个弱分类器；支持向量机寻找最大间隔超平面；生成模型则从概率角度建模数据分布。这些方法共同构成了监督学习的基础。

5 统计机器学习：无监督学习

无监督学习从无标注数据出发，学习数据中蕴含的模式。由于数据是内容的载体，刻画相同内容的数据具有相似模式，因此可从无标注数据中挖掘其固有模式。

常用算法包括：

• 聚类：K均值聚类、层次聚类
• 降维：主成分分析（PCA）、特征人脸
• 隐变量学习：期望最大化（EM）算法
• 其他：自编码器、生成对抗网络（GAN）

5.1 K均值聚类（K-means）

K-means是一种将 $n$ 个 $d$ 维数据划分为 $K$ 个聚簇的聚类算法，目标是最小化簇内方差。

算法流程

算法 5.1 K-means 聚类

• 输入：$n$ 个 $d$ 维数据，聚簇数目 $K$
• 输出：每个数据所属聚簇标签

步骤	操作
1. 初始化	初始化 $K$ 个聚类质心 c={c1,c2,…,cK}c = \{c_1, c_2, \dots, c_K\}c={c1​,c2​,…,cK​}
2. 聚类	计算每个数据与各质心的欧氏距离，将其划入距离最近的质心所在聚簇：$dist(x_i,c_j)=\sqrt{{\sum }_{o=1}^d(x_{i,o}-c_{j,o}{)}^2}$
3. 更新质心	根据当前聚类结果，重新计算每个聚簇的质心（均值）：$c_j=\frac{1}{|G_j|}{\sum }_{x_i\in G_j}{x}_i$
4. 迭代终止	重复步骤2和3，直到质心不再变化或达到最大迭代次数

目标函数

K-means本质上是在最小化每个聚簇的方差：

$$argmi{n}_G\sum _{i=1}^K\sum _{x\in G_i}\Vert x-c_i{\Vert }^2=argmi{n}_G\sum _{i=1}^K|G_i|\mathrm{var}{G}_i$$

特点与局限性

特点	说明
优点	算法简单高效，收敛速度快（通常为 $O(n^{dK+1})$）
对离群点敏感	均值操作易受离群点影响，可用 $K$-medoids 算法替代
需预设 $K$ 值	需要事先确定聚类数目，但实际中往往未知
对数据尺度敏感	不同特征的量纲会影响欧氏距离，导致结果偏差
硬聚类	每个数据只能完全属于一个聚簇，不存在“模糊归属”（可被高斯混合模型解决）

常见初始化方法

• Forgy：随机选取 $K$ 个样本点作为初始质心
• Random Partition：随机分配每个样本到一个类，然后计算初始质心

应用举例

• 图像压缩：将图像像素颜色聚类为 $K$ 种，用质心颜色替代簇内像素，减少存储空间（$K$ 越小压缩率越高，但失真越严重）
• 文本聚类、入侵检测、客户细分等

5.2 主成分分析（PCA）

PCA是一种特征降维方法，通过找到数据的主要成分来代替原始数据，可消除噪声和冗余，并加深对数据本身的理解。其核心要求是：降维后的结果要最大程度保持原始数据的方差结构。

PCA也被称为 KL变换（Karhunen-Loeve Transform）、霍特林变换（Hotelling Transform）或本征正交分解（POD）。

5.2.1 方差、协方差与相关系数

方差

描述样本数据的波动程度：

$$\mathrm{var}(X)=\frac{1}{n-1}\sum _{i=1}^n(x_i-\mu {)}^2,\mu =\frac{1}{n}\sum _{i=1}^n{x}_i$$

【注】分母为 $n-1$ 是为了使方差估计为无偏估计。

协方差

衡量两个变量之间的相关度：

$$\mathrm{cov}(X,Y)=\frac{1}{n-1}\sum _{i=1}^n(x_i-E(X))(y_i-E(Y))$$

取值	含义
$\mathrm{cov}(X,Y)>0$	$X$ 与 $Y$ 正相关
$\mathrm{cov}(X,Y)<0$	$X$ 与 $Y$ 负相关
$\mathrm{cov}(X,Y)=0$	$X$ 与 $Y$ 不相关

皮尔逊相关系数

将协方差规整到 $[-1,1]$ 范围内，消除量纲影响：

$$\mathrm{corr}(X,Y)=\frac{\mathrm{cov}(X,Y)}{{\sigma }_X{\sigma }_Y}$$

性质：

• $|\mathrm{corr}(X,Y)|\le 1$
• $\mathrm{corr}(X,Y)=1⟺$ 存在 $a,b$ 使得 $Y=aX+b$
• 刻画的是变量间的线性相关程度
• 线性无关 $\ne$ 独立：独立必然线性无关，但线性无关不一定独立

5.2.2 主成分分析

基本思想

将 $d$ 维数据映射到 $l$ 维空间（$l\ll d$），使得投影后数据的方差尽可能大。

算法推导

算法 5.2 主成分分析

• 输入：$n$ 个 $d$ 维样本数据构成的矩阵 $X$，降维后维度 $l$
• 输出：映射矩阵 W={w1,w2,…,wl}W = \{w_1, w_2, \dots, w_l\}W={w1​,w2​,…,wl​}

步骤	操作
1. 中心化	对每个样本 $x_i=x_i-\mu$，其中 $\mu =\frac{1}{n}{\sum }_{j=1}^n{x}_j$
2. 计算协方差矩阵	$\Sigma =\frac{1}{n-1}{X}^{T}X$
3. 特征值分解	对 $\Sigma$ 进行特征值分解，按特征值从大到小排序 ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_d$
4. 取前 $l$ 个特征向量	取前 $l$ 个最大特征值对应的特征向量组成映射矩阵 $W$

数学原理

• 降维后数据 $Y=XW$（$Y\in {\mathbb{R}}^{n\times l}$）
• 降维后方差：$\mathrm{var}(Y)=tr(W^T\Sigma W)$
• 优化目标：${\max }_{W}tr(W^T\Sigma W),s.t.w_i^T{w}_i=1$
• 使用拉格朗日乘子法求解，得 $\Sigma w_i={\lambda }_i{w}_i$
• 每一个 $w_i$ 是协方差矩阵 $\Sigma$ 的特征向量，${\lambda }_i$ 是对应特征值
• 最优化方差等于所有选取特征值之和：$tr(W^T\Sigma W)={\sum }_{i=1}^l{\lambda }_i$

5.2.3 其他常用降维方法

1. 非负矩阵分解（NMF）

• 将非负大矩阵 $D\in {\mathbb{R}}^{n\times d}$ 分解为两个非负小矩阵 $W\in {\mathbb{R}}^{n\times l}$ 和 $H\in {\mathbb{R}}^{l\times d}$
• $D\approx WH$，所有元素均非负
• 体现了**“部分组成整体”**的思想（纯加性描述）
• 两种常用代价函数：
  • 欧式距离平方：$\Vert D-WH{\Vert }_F^2$
  • KL散度：$D_{KL}(D\Vert WH)={\sum }_{i,j}(D_{i,j}\log \frac{D_{i,j}}{(WH{)}_{i,j}}-D_{i,j}+(WH{)}_{i,j})$

2. 多维尺度法（MDS）

• 思想：保持原始数据的两两距离不变
• 步骤：计算原始数据的距离矩阵 $A\to$ 中心化得 $B=-\frac{1}{2}HAH\to$ 对 $B$ 做奇异值分解得降维结果
• 缺点：存在 out-of-sample 问题，无法对新数据降维

3. 局部线性嵌入（LLE）

• 一种非线性降维方法
• 基本假设：一个流形的局部可近似于欧式空间，每个样本可由其近邻线性重构
• 利用局部线性逼近全局非线性，通过重叠的局部邻域提供全局结构信息

5.3 特征人脸方法

一种基于外观的人脸识别方法，使用 PCA 的手段提取人脸图像集合中的特征信息，用少量特征脸有效表示原始面部图像。核心思想是：使用一组特征向量（特征人脸）线性组合来表示原始人脸。

5.3.1 奇异值分解（SVD）

在特征维度较高时，暴力求解协方差矩阵的特征向量耗时很大。SVD 提供了一种更高效的计算方式。

• 分解形式：$A=UD{V}^T$

  • $A\in {\mathbb{R}}^{n\times d}$：原始数据矩阵
  • $U\in {\mathbb{R}}^{n\times n}$，$V\in {\mathbb{R}}^{d\times d}$ 均为酉矩阵（$U^{T}U=I,V^{T}V=I$）
  • $D\in {\mathbb{R}}^{n\times d}$：对角矩阵，对角元素为奇异值

• 与 PCA 的关系：

  • $A{A}^T=U{D}^2{U}^T⟹U$ 是 $A{A}^T$ 的特征向量矩阵
  • $A^{T}A=V{D}^2{V}^T⟹V$ 是 $A^{T}A$ 的特征向量矩阵
  • 从 $U$ 选取前 $l$ 个奇异向量可压缩矩阵的行数；从 $V$ 选取前 $l$ 个奇异向量可压缩特征维度（PCA 的目标）

• 高效计算技巧：当 $d^2\gg n$ 时，先求 $n\times n$ 的 $\Phi {\Phi }^T$ 特征向量，再利用关系 $v_i={\Phi }^T{u}_i$ 得到特征人脸，避免直接求解巨大的 $d^2\times d^2$ 矩阵。

5.3.2 特征人脸方法流程

1. 计算均值人脸：$\Psi =\frac{1}{n}{\sum }_{i=1}^n{\Gamma }_i$
2. 中心化：${\varphi }_i={\Gamma }_i-\Psi$
3. SVD求解：利用 SVD 高效计算中心化矩阵 $\Phi$ 的特征向量（即特征人脸）
4. 投影：将每个人脸图像映射到特征人脸空间：${\Omega }_i=({\varphi }_i{)}_{1\times d^2}{V}_{d^2\times n}$
5. 识别比较：通过比较两个人脸图像在特征人脸空间的表示 ${\Omega }_i$ 和 ${\Omega }_j$ 判断是否相似

【注】

• 选取的特征人脸数量 $l$ 是对重建质量和算法复杂度（时间、空间）的权衡
• 特征人脸能较好表达人脸的全局信息，但无法凸显局部特性（如眼睛、嘴巴细节），这与非负矩阵分解形成对比

5.4 潜在语义分析（LSA）

一种从海量文本中学习单词与单词、单词与文档、文档与文档之间隐性语义关系的方法。基本思想是综合考虑单词在哪些文档中同时出现，以此判断词语含义的相似度。

5.4.1 潜在语义分析思想

1. 构建单词-文档矩阵 $A$：尺寸 $M\times N$，$M$ 为单词数目，$N$ 为文档数目。矩阵元素表示某单词在某文档中出现次数（也可用 TF-IDF 等加权）。
2. SVD分解：$A=UD{V}^T$
   • $U\in {\mathbb{R}}^{M\times R}$：LSI单词向量，每行是一个单词在隐空间中的表示
   • $V\in {\mathbb{R}}^{N\times R}$：LSI文档向量，每行是一个文档在隐空间中的表示
   • $D\in {\mathbb{R}}^{R\times R}$：对角矩阵，对角线上按从大到小排列的奇异值
   • $R$ 为矩阵 $A$ 的秩
3. 低秩近似：取前 $k$ 个最大奇异值及其对应向量，重构矩阵 $A_k={\sum }_{i=1}^k{u}_i{\sigma }_i{v}_i^T$
   • $A_k$ 是对原始矩阵 $A$ 的近似，但两者不完全相同

5.4.2 潜在语义分析的效果

通过对重建后的矩阵分析，可以发现：

• 同一类别文档之间的相关性显著提升
• 同一类别内单词之间的语义相似度被明确刻画
• 揭示了在原始矩阵中未被显式表达出来的隐性语义关联

应用场景

• 自动文档分类
• 文本摘要
• 信息检索中的同义词处理
• 关系发现

5.5 期望最大化算法（EM算法）

当模型含有隐变量（未观测变量） 时，无法直接使用最大似然估计求解参数。EM算法通过迭代方式，逐步优化模型参数以最佳“拟合”观测数据。

EM算法分为两步，不断交替直至收敛：

• E步骤（Expectation）：基于当前参数，估计隐变量的取值或分布
• M步骤（Maximization）：基于观测数据和E步骤得到的隐变量，最大化似然函数，更新模型参数

【注】EM算法不能保证找到全局最优解，可能收敛到鞍点或局部最优。结果受初始值影响。

5.5.1 二硬币投掷例子

问题设定：有A和B两枚硬币，进行5轮实验。每轮先随机选一个硬币，然后掷10次记录正反面（H / T），但不记录所选硬币是A还是B。观测结果仅知道每次投掷的正反面，所选硬币是隐变量。

目标：估计硬币A和B各自的正面概率 θ={θA,θB}\theta = \{\theta_A, \theta_B\}θ={θA​,θB​}。

EM算法迭代过程：

1. 初始化 ${\hat{\theta }}_A^{(0)}=0.60,{\hat{\theta }}_B^{(0)}=0.50$
2. E步骤：计算在当前参数下，每轮实验选择硬币A或B的概率
3. M步骤：根据E步骤计算的期望，重新估计 ${\theta }_A$ 和 ${\theta }_B$
4. 重复E、M步骤直至收敛

【注】经过多次迭代后，算法收敛于 ${\theta }_A=0.797,{\theta }_B=0.520$（该结果与初始值有关）

5.5.3 EM算法一般形式

• 观测数据 X={x1,…,xn}X = \{x_1, \dots, x_n\}X={x1​,…,xn​}，隐变量 Z={z1,…,zn}Z = \{z_1, \dots, z_n\}Z={z1​,…,zn​}
• 优化目标：最大化对数似然函数 $L(\Theta ,Z)={\sum }_{i=1}^n\log {\sum }_{z_i}P(x_i,z_i|\Theta )$
• 核心思想：不断构造对数似然函数的一个下界（E步骤），然后最大化这个下界（M步骤）

数学推导：

$$L(\Theta )=\sum _{i=1}^n\log \sum _{z_i}P(x_i,z_i|\Theta )=\sum _{i=1}^n\log \sum _{z_i}{Q}_i(z_i)\frac{P(x_i,z_i|\Theta )}{Q_i(z_i)}$$

由 Jensen 不等式，得到下界：

$$L(\Theta )\ge \sum _{i=1}^n\sum _{z_i}{Q}_i(z_i)\log \frac{P(x_i,z_i|\Theta )}{Q_i(z_i)}$$

等号成立条件为 $\frac{P(x_i,z_i|\Theta )}{Q_i(z_i)}=c$（常数）。取 $Q_i(z_i)=P(z_i|x_i,\Theta )$ 时等号成立。

最终迭代公式：

$${\Theta }^{(t+1)}=argma{x}_{\Theta }\sum _{i=1}^n\sum _{z_i}P(z_i|x_i,{\Theta }^{(t)})\log P(x_i,z_i|\Theta )$$

5.6 小结

本章从聚类、特征降维和模型学习三个角度介绍了无监督学习的核心方法：

• K-means聚类：通过最小化簇内方差将数据划分为 $K$ 类
• 主成分分析（PCA）：提取数据方差最大的方向实现降维
• 特征人脸：PCA在人脸识别中的具体应用，通过SVD高效计算
• 潜在语义分析（LSA）：利用SVD挖掘单词与文档间的隐性语义
• 期望最大化（EM）算法：解决含隐变量模型的参数估计问题

这些方法共同构成了在无标注数据中“透过数据看本质”的理论和算法基础。

6 深度学习

深度学习是近期在诸多领域取得显著效果的一种方法。与传统监督学习依赖手工构造特征不同，深度学习通过构造**“端到端”**的多层网络结构，自动学习隐含在数据内部的层级化特征表达。

6.1 深度学习的历史发展

深度学习的思想源于对人脑神经系统的模拟。其发展历程中经历了多次起伏，最终在海量数据、强大算力和算法改进的共同推动下，成为当前人工智能的核心技术。

6.2 前馈神经网络

前馈神经网络是深度学习的基础架构。信息从输入层开始，逐层向前传播，经过若干隐藏层，最终到达输出层，网络中没有反馈回路。

6.2.1 若干概念

M-P神经元模型

神经网络的基本计算单元。一个神经元接收来自 $n$ 个其他神经元的输入信号 $(x_1,\dots ,x_n)$，通过带权重的连接进行传递，总输入与阈值 $\theta$ 比较后，经过激活函数 $f$ 处理产生输出：

$$y=f\left(\sum _{i=1}^n{w}_i{x}_i-\theta \right)$$

常见激活函数

激活函数的作用是为神经网络引入非线性表达能力。若无激活函数，多层网络将退化为单一的线性映射。

激活函数	表达式	特点
Sigmoid	$\sigma (z)=\frac{1}{1+e^{-z}}$	输出范围 $(0,1)$，常用于二分类输出层；易产生梯度消失
Tanh	$\tanh (z)=\frac{e^z-e^{-z}}{e^z+e^{-z}}$	输出范围 $(-1,1)$，零中心化；仍存在梯度消失
ReLU	$\text{ReLU}(z)=\max (0,z)$	计算简单，缓解梯度消失；输出非零中心；可能出现神经元“死亡”
Leaky ReLU	$\text{Leaky ReLU}(z)=\max (\alpha z,z)$	解决ReLU神经元死亡问题，给负区间一个微小斜率
Softmax	$\text{Softmax}(z_i)=\frac{e^{z_i}}{{\sum }_j{e}^{z_j}}$	将输出转换为概率分布，常用于多分类输出层

多层前馈网络结构

• 输入层：接收原始数据，神经元数量等于特征维度
• 隐藏层：位于输入层和输出层之间，对数据进行特征变换和提取。可以有多个隐藏层
• 输出层：产生最终预测结果
• 全连接：相邻层之间的神经元两两连接，每条连接有一个权重

万能近似定理

具有至少一个隐藏层、且隐藏层使用“挤压”性质激活函数（如Sigmoid）的前馈网络，只要隐藏层神经元数量足够多，可以以任意精度逼近任意连续函数。但定理并未说明需要多少神经元，也未保证实际训练能收敛到该函数。

6.2.2 感知机模型

感知机是由两层神经元组成的最简单前馈网络（输入层 + 输出层），只能解决线性可分问题。

• 模型：$y=sign({\mathbf{w}}^T\mathbf{x}+b)$
• 学习策略：误分类驱动。对误分类样本 $(x_i,y_i)$，更新权重：$w\leftarrow w+\eta y_i{x}_i$
• 收敛性：若数据线性可分，感知机算法必收敛
• 局限：无法解决异或（XOR）等线性不可分问题，这直接导致了神经网络研究的第一次低潮

6.2.3 参数优化与学习

多层网络的学习远比感知机复杂，需借助误差反向传播算法与梯度下降进行参数优化。

误差反向传播（Backpropagation, BP）

BP算法的核心思想是：利用链式法则，将输出层的误差从后向前逐层传递，从而高效计算出损失函数对网络中每个参数的梯度。

算法流程：

1. 前向传播：将输入样本送入网络，逐层计算各神经元的输出，最终得到预测值
2. 计算输出层误差：根据损失函数，计算预测值与真实值之间的误差
3. 反向传播：从输出层开始，利用链式法则将误差逐层向前反向传播，计算每层神经元权重的梯度
4. 更新参数：利用梯度下降法更新各层权重和偏置

批量梯度下降 vs 随机梯度下降 vs 小批量梯度下降

方法	描述	特点
批量梯度下降（BGD）	使用全部训练数据计算梯度	收敛稳定但速度慢，内存开销大
随机梯度下降（SGD）	每次使用一个样本计算梯度	更新快，但收敛过程波动大
小批量梯度下降（Mini-batch SGD）	每次使用一小批样本计算梯度	最常用，兼顾稳定性和效率

6.3 卷积神经网络（CNN）

卷积神经网络是专门为处理网格化结构数据（如图像）而设计的深度学习架构。其核心组件包括卷积层、池化层和全连接层。

CNN的主要特点：

• 局部连接：每个神经元只与上一层的局部区域连接，减少参数数量
• 权值共享：同一卷积核在整个输入上滑动，共享权重参数
• 层次化特征提取：低层提取边缘、纹理等简单特征，高层组合成复杂语义特征

6.3.1 卷积计算

卷积核（滤波器）在输入特征图上滑动，每次与对应位置的局部区域做逐元素乘积后求和，生成输出特征图。多个卷积核可提取多种不同特征。

卷积操作的核心参数：

参数	说明
卷积核大小	感受野的大小，如 $3\times 3$、$5\times 5$
步长（Stride）	卷积核每次移动的像素数
零填充（Padding）	在输入特征图边缘补零，控制输出尺寸

输出尺寸计算公式：
假设输入尺寸为 $W_{in}\times H_{in}$，卷积核大小为 $F\times F$，步长为 $S$，填充为 $P$，则输出尺寸为：

$$W_{out}=\frac{W_{in}-F+2P}{S}+1,H_{out}=\frac{H_{in}-F+2P}{S}+1$$

6.3.2 池化（Pooling）

池化层对特征图进行下采样，减少特征图尺寸，从而降低计算量和参数量，同时增加感受野，具有一定的不变性（如平移不变性）。

池化类型	操作	特点
最大池化	取局部区域的最大值	最常用，保留最显著特征
平均池化	取局部区域的平均值	保留整体信息，更平滑

6.3.3 神经网络正则化

为防止过拟合，常用以下正则化技术：

方法	核心思想
L1/L2正则化	在损失函数中加入权重的 L1 或 L2 范数惩罚项，限制权重大小
Dropout	训练时随机“丢弃”一部分神经元，相当于每次训练一个子网络，有效防止过拟合。测试时使用全部神经元
数据增强	通过旋转、翻转、裁剪、色彩变换等手段生成更多训练样本
批归一化（Batch Normalization）	对每层输入进行归一化，加速训练，减少对初始化的敏感度

6.4 循环神经网络（RNN）

循环神经网络专门用于处理序列数据（如文本、语音、时间序列），其核心特点是具有记忆能力，当前时刻的输出不仅依赖当前输入，还依赖之前时刻的隐藏状态。

6.4.1 循环神经网络模型

核心思想：在每个时间步 $t$，RNN 接收当前输入 $x_t$ 和上一时刻的隐藏状态 $h_{t-1}$，计算当前隐藏状态 $h_t$ 和输出 $y_t$：

$$h_t=f(W_{xh}{x}_t+W_{hh}{h}_{t-1}+b_h)$$
$$y_t=g(W_{hy}{h}_t+b_y)$$

• $W_{xh},W_{hh},W_{hy}$ 在所有时间步共享，大大减少参数数量。
• 通过沿时间的反向传播（Backpropagation Through Time, BPTT）进行训练。

RNN的局限性：

• 梯度消失/爆炸：序列较长时，梯度在反向传播中呈指数级衰减或增长，导致难以学习长期依赖关系。
• 短时记忆问题：标准RNN仅能有效记住较短时间步之前的信息。

6.4.2 长短时记忆网络（LSTM）

LSTM 是为解决标准RNN的长期依赖问题而设计的改进模型。它引入门控机制和细胞状态，可以学习何时记住、何时遗忘信息。

LSTM的核心组件：

组件	功能
遗忘门	决定从细胞状态中丢弃哪些信息：$f_t=\sigma (W_f\cdot [h_{t-1},x_t]+b_f)$
输入门	决定将哪些新信息存入细胞状态：$i_t=\sigma (W_i\cdot [h_{t-1},x_t]+b_i)$
候选细胞状态	生成候选的新信息：${\tilde{C}}_t=\tanh (W_C\cdot [h_{t-1},x_t]+b_C)$
更新细胞状态	整合遗忘门和输入门：$C_t=f_t\odot C_{t-1}+i_t\odot {\tilde{C}}_t$
输出门	决定输出什么信息：$o_t=\sigma (W_o\cdot [h_{t-1},x_t]+b_o)$
隐藏状态	$h_t=o_t\odot \tanh (C_t)$

6.4.3 门控循环单元（GRU）

GRU 是 LSTM 的简化变体，将遗忘门和输入门合并为更新门，将细胞状态和隐藏状态合并。参数更少，计算效率更高，在很多任务上效果与 LSTM 相当。

• 更新门 $z_t$：控制保留多少过去信息，以及接收多少新信息
• 重置门 $r_t$：控制忽略多少过去信息

6.5 深度生成学习

深度生成模型旨在学习数据的概率分布，从而能够生成新的、与训练数据相似的样本。

6.5.1 生成对抗网络（GAN）

GAN 由 Goodfellow 于 2014 年提出，由两个网络组成，通过对抗训练共同优化：

• 生成器（Generator, G）：接收随机噪声 $z$，生成伪造样本 $G(z)$，目标是“骗过”判别器
• 判别器（Discriminator, D）：接收真实样本或生成样本，判断输入是真实的还是伪造的

核心思想：两个网络间进行极小极大博弈（Minimax Game）。

6.5.2 生成对抗网络算法

优化目标函数：

$$\underset{G}{\min }\underset{D}{\max }V(D,G)={\mathbb{E}}_{x\sim p_{data}(x)}[\log D(x)]+{\mathbb{E}}_{z\sim p_z(z)}[\log (1-D(G(z)))]$$

• 判别器优化：最大化 $V$，即正确分类真实样本和生成样本
• 生成器优化：最小化 $V$，即最小化 $\log (1-D(G(z)))$，等价于最大化 $\log D(G(z))$，让判别器将生成样本判为真

训练过程：交替训练判别器和生成器，二者在对抗中共同提升。理论上，当 $p_G=p_{data}$ 时，博弈达到纳什均衡，此时 $D(x)=\frac{1}{2}$。

6.5.3 条件生成对抗网络（CGAN）

原始 GAN 无法控制生成样本的类别。CGAN 通过向生成器和判别器额外输入条件变量 $c$（如类别标签），使生成过程可控，可生成指定类别的样本。

• 生成器：$G(z,c)$，根据随机噪声和条件生成样本
• 判别器：$D(x,c)$，不仅判断样本真假，还判断样本与条件是否匹配
• 优化目标：
  $$\underset{G}{\min }\underset{D}{\max }V(D,G)={\mathbb{E}}_{x\sim p_{data}}[\log D(x,c)]+{\mathbb{E}}_{z\sim p_z}[\log (1-D(G(z,c),c))]$$

6.5.4 用生成对抗网络抵御对抗样本攻击

对抗样本：在原始输入上添加微小、人眼不可察觉的扰动后，会导致深度学习模型以高置信度做出错误预测。这种现象揭示了深度学习模型的脆弱性。

防御思路：利用GAN生成对抗样本，将其加入训练数据，使模型“见过”对抗样本后获得鲁棒性，从而抵御对抗攻击。

6.6 深度学习在自然语言和计算机视觉上的应用

6.6.1 词向量模型（Word2Vec）

• 目的：将单词从离散的独热编码（One-hot）映射到低维稠密的连续向量空间，使语义相似的词在向量空间中距离也相近。
• 核心假设：分布假说——“一个词的含义可由其上下文推断”
• 主要模型：
  • Skip-gram：用中心词预测周围上下文词
  • CBOW（Continuous Bag of Words）：用上下文词预测中心词
• 著名特性：词向量能捕获语义关系，如“国王 - 男人 + 女人 = 王后”

6.6.2 图像分类与目标定位

CNN 在计算机视觉领域取得了突破性进展，典型网络架构包括：

模型	特点
AlexNet	2012年 ImageNet 冠军，首次展示深度学习潜力（ReLU + Dropout）
VGGNet	使用堆叠的小卷积核（$3\times 3$），网络结构规整
GoogLeNet（Inception）	引入 Inception 模块，并行使用多种大小卷积核提取多尺度特征
ResNet	引入残差连接（跳层连接），解决深层网络退化问题，可训练上百层网络

除图像分类外，CNN 还广泛用于目标检测（Faster R-CNN、YOLO）、语义分割（FCN、U-Net）等视觉任务。

6.7 小结

深度学习通过构建多层神经网络，实现端到端的特征学习和任务求解。

• 前馈神经网络是网络基础，通过反向传播算法进行参数优化
• CNN 利用卷积、池化等操作，极大推动了计算机视觉的发展
• RNN/LSTM/GRU 的循环结构和门控机制，为处理序列数据提供了有效方案
• GAN 开创了对抗训练范式，使模型具备生成逼真数据的能力

7 强化学习

强化学习解决的是序贯决策优化问题。智能体通过与环境的不断交互，根据环境反馈的奖励或惩罚来学习在不同状态下应采取的最优动作，目标是最大化累积奖励。

与监督学习、无监督学习的核心区别：

• 数据在序列交互中产生，非一次性给定
• 决策是序列决策，而非单步静态决策
• 学习依据是评价性反馈（奖励值），而非明确的正确标签

7.1 强化学习问题定义

7.1.1 强化学习基本概念

强化学习的基本框架包含以下要素：

要素	说明
智能体（Agent）	执行动作并与环境交互的学习主体
环境（Environment）	智能体所处的外部世界，对动作做出响应
状态 $s$	智能体在某一时刻对环境的观察描述
动作 $a$	智能体在某一状态下可采取的行为
奖励 $r$	环境对智能体执行某动作后给出的即时反馈（正数为奖励，负数为惩罚）
策略 $\pi$	智能体选择动作的规则，$\pi (a|s)$ 表示在状态 $s$ 下选择动作 $a$ 的概率
轨迹（Trajectory）	智能体与环境交互产生的一系列状态-动作-奖励序列

交互过程：在时间步 $t$，智能体观察到状态 $s_t$，执行动作 $a_t$，环境返回奖励 $r_t$，智能体进入新状态 $s_{t+1}$。

学习目标：找到最优策略 ${\pi }^{\ast }$，使得累计奖励的期望最大。累计奖励通常定义为回报（Return）：

$$G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k}$$

其中 $\gamma \in [0,1]$ 为折扣因子，用于调节当前奖励与未来奖励的相对重要性。

7.1.2 马尔可夫决策过程（MDP）

强化学习问题通常被建模为马尔可夫决策过程。

定义：一个MDP由五元组 $(S,A,P,R,\gamma )$ 组成：

符号	含义
$S$	有限的状态集合
$A$	有限的动作集合
$P$	状态转移概率：$P(s_{t+1}|s_t,a_t)$
$R$	奖励函数：$R(s_t,a_t,s_{t+1})$
$\gamma$	折扣因子

马尔可夫性质：下一状态只依赖于当前状态和当前动作，与历史状态无关：

$$P(s_{t+1}|s_t,a_t)=P(s_{t+1}|s_0,a_0,s_1,a_1,\dots ,s_t,a_t)$$

7.1.3 强化学习问题定义要素

强化学习在MDP框架下，需定义以下要素：

• 状态空间 $S$：所有可能状态的集合
• 动作空间 $A$：所有可能动作的集合
• 状态转移函数 $P(s^{\prime }|s,a)$：在状态 $s$ 执行动作 $a$ 后转移到状态 $s^{\prime }$ 的概率
• 奖励函数 $R(s,a,s^{\prime })$：在状态 $s$ 执行动作 $a$ 转移到 $s^{\prime }$ 后获得的奖励
• 折扣因子 $\gamma$：权衡短期和长期奖励

7.1.4 贝尔曼方程

贝尔曼方程是强化学习的理论基石，它将状态价值函数进行递归分解。

状态价值函数 $V^{\pi }(s)$

在策略 $\pi$ 下，从状态 $s$ 出发所能获得的期望累计回报：

$$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k+1}|s_t=s\right]$$

动作价值函数 $Q^{\pi }(s,a)$

在策略 $\pi$ 下，从状态 $s$ 出发、执行动作 $a$ 后所能获得的期望累计回报：

$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k+1}|s_t=s,a_t=a\right]$$

贝尔曼期望方程

将价值函数分解为即时奖励与后续状态价值之和：

$$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)\sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\left[R(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })\right]$$

$$Q^{\pi }(s,a)=\sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\left[R(s,a,s^{\prime })+\gamma \sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\right]$$

贝尔曼最优方程

最优策略 ${\pi }^{\ast }$ 下的价值函数满足：

$$V^{\ast }(s)=\underset{a\in A}{\max }\sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\left[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })\right]$$

$$Q^{\ast }(s,a)=\sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\left[R(s,a,s^{\prime })+\gamma \underset{a^{\prime }\in A}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })\right]$$

7.2 基于价值的强化学习

基于价值的方法通过估计状态价值函数或动作价值函数，隐式地确定最优策略（通常为贪心策略）。

7.2.1 策略迭代的基本模式

策略迭代是求解MDP的经典方法，交替执行以下两步直至收敛：

1. 策略评估：基于当前策略 $\pi$，计算其价值函数 $V^{\pi }$
2. 策略改进：根据 $V^{\pi }$ 更新策略，使用贪心策略 ${\pi }^{\prime }(s)=argma{x}_a{\sum }_{s^{\prime }}P(s^{\prime }|s,a)[R+\gamma V^{\pi }(s^{\prime })]$

7.2.2 策略优化定理

定理：如果 ${\pi }^{\prime }$ 是对 $\pi$ 的贪心改进，即 $Q^{\pi }(s,{\pi }^{\prime }(s))\ge V^{\pi }(s)$ 对所有 $s$ 成立，则 ${\pi }^{\prime }$ 一定不比 $\pi$ 差，即 $V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s)$。

这保证了策略迭代过程单调改善，最终收敛到最优策略。

7.2.3 策略评估方法

当状态转移概率已知时，可采用迭代方法进行策略评估。

迭代策略评估

从任意的初始价值函数 $V_0$ 开始，使用贝尔曼方程迭代更新，直到收敛：

$$V_{k+1}(s)=\sum _{a\in A}\pi (a|s)\sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\left[R(s,a,s^{\prime })+\gamma V_k(s^{\prime })\right]$$

当 $k\to \infty$ 时，$V_k\to V^{\pi }$。

7.2.4 基于价值的强化学习算法

Q-learning（Q学习）

Q学习是一种无模型、离策略的强化学习算法，直接学习最优动作价值函数 $Q^{\ast }(s,a)$。

核心更新公式（时间差分更新）：

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_t+\gamma \underset{a^{\prime }}{\max }Q(s_{t+1},a^{\prime })-Q(s_t,a_t)\right]$$

• $\alpha$：学习率，控制新信息对Q值的影响程度
• $r_t+\gamma {\max }_{a^{\prime }}Q(s_{t+1},a^{\prime })$：TD目标（Temporal Difference Target）
• $r_t+\gamma {\max }_{a^{\prime }}Q(s_{t+1},a^{\prime })-Q(s_t,a_t)$：TD误差

Q表格：为每个状态-动作对维护一个Q值，最终策略为 $\pi (s)=argma{x}_{a}Q(s,a)$。

特点：

• 离策略：学习最优Q值时采用的行为策略（如 $ϵ$-贪心）与学习的目标策略（贪心策略）可以不同
• 局限性：Q表格无法处理大规模或连续状态空间

SARSA（状态-动作-奖励-状态-动作）

SARSA是一种同策略算法，更新公式中使用实际执行的动作：

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right]$$

与Q-learning的区别：SARSA的更新依赖于实际采取的下一个动作 $a_{t+1}$，而Q-learning使用 ${\max }_{a^{\prime }}Q(s_{t+1},a^{\prime })$。

7.2.5 探索与利用

强化学习中的核心矛盾：探索（Exploration）与利用（Exploitation）。

策略	说明
贪心策略	总是选择Q值最大的动作，只利用不探索
$ϵ$-贪心策略	以概率 $ϵ$ 随机选择动作（探索），以 $1-ϵ$ 选择最优动作（利用）。$ϵ$ 通常随时间衰减
Softmax策略	根据Q值使用Boltzmann分布选择动作，Q值越高的动作被选中的概率越大

• 探索：尝试未执行过的动作，获取更多环境信息
• 利用：根据已有经验，选择已知最佳的动作
• 目标：在探索和利用之间找到平衡，以获得最大的长期回报

7.2.6 参数化与深度强化学习

参数化Q函数（DQN）

当状态空间巨大或连续时，无法用Q表格存储。Deep Q-Network（DQN）使用深度神经网络逼近Q函数：$Q(s,a;\theta )\approx Q^{\ast }(s,a)$。

DQN的关键技术

技术	作用
经验回放	将交互经验 $(s_t,a_t,r_t,s_{t+1})$ 存入回放池，训练时随机采样小批量数据，打破数据相关性，提高样本利用率
目标网络	使用独立的、定期更新的目标网络计算TD目标，缓解训练中的震荡和不稳定

DQN的损失函数：

$$L(\theta )={\mathbb{E}}_{(s,a,r,s^{\prime })\sim \mathcal{D}}\left[{\left(r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime };{\theta }^{-})-Q(s,a;\theta )\right)}^2\right]$$

• $\theta$：当前Q网络参数
• ${\theta }^{-}$：目标Q网络参数（定期从 $\theta$ 复制）
• $\mathcal{D}$：经验回放池

7.3 基于策略的强化学习

基于价值的方法隐式推导策略（贪心），但在连续动作空间或随机策略场景下存在局限。基于策略的方法直接对策略进行参数化和优化。

7.3.1 策略梯度定理

目标函数：$J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[G(\tau )]$，其中 $\tau$ 为一条轨迹，${\pi }_{\theta }$ 为参数化的策略。

策略梯度定理给出了目标函数关于策略参数 $\theta$ 的梯度：

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{{\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)Q^{{\pi }_{\theta }}(s,a)\right]$$

• 梯度方向使“好动作”（高Q值）的概率增大，“坏动作”（低Q值）的概率减小

7.3.2 基于蒙特卡洛采样的策略梯度法（REINFORCE）

REINFORCE 是最基本的策略梯度算法，使用蒙特卡洛采样估计梯度。

算法流程：

1. 使用当前策略 ${\pi }_{\theta }$ 采样完整的轨迹
2. 对轨迹中的每一步，计算回报 $G_t$
3. 更新参数：$\theta \leftarrow \theta +\alpha {\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)G_t$

特点：

• 无偏但高方差：使用真实回报 $G_t$ 无偏估计梯度的幅值
• 需要等待轨迹结束才能更新（回合更新，非单步更新）

7.3.3 Actor-Critic算法

Actor-Critic结合了基于策略的方法（Actor） 和基于价值的方法（Critic）：

组件	角色	功能
Actor（演员）	策略网络 ${\pi }_{\theta }(a|s)$	决定在状态下该做什么动作
Critic（评论家）	价值网络 $V_{\varphi }(s)$ 或 $Q_{\varphi }(s,a)$	评价Actor的动作好坏，提供梯度更新信号

• Critic 使用TD误差代替REINFORCE中的回报 $G_t$ 来估计梯度，显著降低方差
• Actor 根据Critic的评估信号更新策略参数

优势函数 $A(s,a)=Q(s,a)-V(s)$，衡量动作 $a$ 比平均表现好多少。使用优势函数可以进一步降低方差：

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{{\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)A^{{\pi }_{\theta }}(s,a)\right]$$

7.4 深度强化学习的应用

7.4.1 深度强化学习在围棋游戏中的应用

AlphaGo 是深度强化学习的里程碑式应用，结合了以下技术：

技术	作用
监督学习（策略网络）	从人类棋谱学习初始走棋策略
强化学习（策略提升）	通过自我博弈提高棋力
价值网络	估计当前棋盘局面的胜率
蒙特卡洛树搜索（MCTS）	在落子时进行前瞻搜索，选择最佳走法

AlphaGo在2016年击败了围棋世界冠军李世石，展示了深度强化学习的巨大潜力。

7.4.2 深度强化学习在实际应用中的问题

问题	说明
样本效率低	需要大量交互数据才能学到有效策略，在真实环境中成本高昂
奖励设计困难	复杂任务中，设计合适的奖励函数很困难；稀疏奖励导致学习缓慢
泛化能力差	训练环境和测试环境稍有不同，策略可能失效
稳定性问题	训练过程可能不稳定，收敛性难以保证
安全与伦理	探索过程中可能做出危险动作，部署前需在模拟器充分验证

7.5 小结

强化学习为智能体在环境中自主学习序列决策提供了理论框架和算法支持。

• MDP 是对序列决策问题的形式化建模
• 贝尔曼方程 将价值函数进行递归分解，奠定了求解基础
• 基于价值的算法（如Q-learning）通过学习最优Q函数导出策略
• 基于策略的算法（如REINFORCE、Actor-Critic）直接优化策略参数
• 深度强化学习（如DQN）利用神经网络处理高维状态空间，使得强化学习在围棋、游戏、机器人控制等领域取得了突破性进展

8 人工智能博弈

博弈论是研究多个智能体在竞争或合作环境中如何进行策略性决策的数学理论。传统博弈论与人工智能的深度融合，推动机器学习从“求取最优解”向“求取均衡解”转变。

8.1 博弈论的相关概念

8.1.1 博弈论的诞生

现代博弈论思想起源于1944年冯·诺依曼与摩根斯特恩合著的《博弈论与经济行为》，首次用数学形式阐述了博弈论及其应用。

约翰·纳什于1950年在其博士论文中提出非合作博弈及其均衡解一定存在的纳什均衡思想，将博弈论发扬光大，也因此获得1994年诺贝尔经济学奖。

博弈行为是多个带有相互竞争性质的主体，为达到各自目标和利益，采取的带有对抗性质的行为，即 “两害相权取其轻，两利相权取其重”。

8.1.2 博弈论术语与囚徒困境

基本术语

术语	说明
玩家（Player）	博弈的参与者
策略（Strategy）	玩家在每种可能情况下采取的行动方案
收益（Payoff）	玩家在博弈结束后获得的效用值
均衡（Equilibrium）	所有玩家策略达到稳定、无人愿单方面改变的状态

囚徒困境

两个共谋罪犯被捕，单独审讯。每人可选择坦白或抵赖。

甲\乙	乙抵赖	乙坦白
甲抵赖	各判1年	甲判10年，乙释放
甲坦白	甲释放，乙判10年	各判5年

• 个体理性：无论对方如何选择，坦白对自己更有利（严格占优策略）
• 均衡结果：双方都坦白，各判5年
• 集体最优：双方都抵赖，各判1年
• 困境本质：个体理性导致集体非最优的结果

8.1.3 博弈的分类

分类标准	类型	说明
是否合作	合作博弈 / 非合作博弈	玩家之间能否达成有约束力的协议
行动顺序	静态博弈 / 动态博弈	玩家是同时行动还是先后行动
信息完备性	完全信息 / 非完全信息	玩家是否知道其他玩家的收益函数
收益关系	零和博弈 / 非零和博弈	玩家收益之和是否恒为零
博弈次数	单次博弈 / 重复博弈	博弈是一次性还是多次重复进行

8.1.4 纳什均衡

定义：在一个策略组合中，每个玩家的策略都是对其他玩家策略的最优反应。没有任何玩家可以通过单方面改变自己的策略来获得更高的收益。

数学表达：
对于 $n$ 个玩家的博弈，策略组合 $s^{\ast }=(s_1^{\ast },s_2^{\ast },\dots ,s_n^{\ast })$ 是纳什均衡，当且仅当对每个玩家 $i$：

$$u_i(s_i^{\ast },s_{-i}^{\ast })\ge u_i(s_i,s_{-i}^{\ast }),\forall s_i\in S_i$$

• $u_i$：玩家 $i$ 的收益函数
• $s_{-i}^{\ast }$：除玩家 $i$ 外其他玩家的策略

纳什存在定理：任何具有有限玩家的有限策略博弈，至少存在一个纳什均衡（可能包含混合策略）。

策略类型	说明
纯策略	玩家确定性地选择某个具体动作
混合策略	玩家以一定的概率分布随机选择动作

8.1.5 人工智能与博弈论

人工智能与博弈论深度融合的研究方向：

• 博弈策略求解：寻找博弈中的均衡策略（如虚拟遗憾最小化算法）
• 博弈规则设计：设计机制使得个体理性行为导向合意的全局结果
• 多智能体学习：多个AI智能体在博弈环境中学习和进化

8.2 博弈策略求解

8.2.1 研究问题

在非完全信息博弈中，玩家不知道其他玩家的私有信息（如手牌），这大大增加了求解难度。核心目标是计算博弈中的纳什均衡策略或近似均衡策略。

挑战：

• 非完全信息博弈的状态空间极大（如德州扑克的博弈树规模约为 $10^{161}$）
• 需要考虑信息的不对称性和对手行为的不可预测性

8.2.2 虚拟遗憾最小化算法（Counterfactual Regret Minimization, CFR）

CFR 是求解大规模非完全信息博弈的里程碑算法，通过迭代自我博弈，使每个信息集上的虚拟遗憾值最小化，最终收敛到纳什均衡。

遗憾值（Regret）

• 遗憾值：实际采取某动作后，与事后知道的最佳动作相比，所遭受的损失
• 虚拟遗憾值（Counterfactual Regret）：在特定信息集上，对“如果采取了某动作”而“实际采取了另一动作”的遗憾进行虚拟计算，同时考虑对手到达该信息集的概率

CFR算法核心流程

CFR 使用反事实遗憾最小化来独立地最小化每个信息集上的遗憾：

1. 计算反事实价值：对每个信息集，计算采取每种动作所能获得的期望价值

2. 计算即时遗憾：$R_{imm}^T(I,a)=v(I,a)-v(I)$，即采取动作 $a$ 的价值与信息集平均价值的差值

3. 累积遗憾：$R^T(I,a)=R^{T-1}(I,a)+R_{imm}^T(I,a)$

4. 更新策略：使用遗憾匹配算法更新当前策略，使得正遗憾值的动作获得更高的选择概率：
   $${\sigma }^{T+1}(I,a)=\{\begin{array}{ll}\frac{\max (R^T(I,a),0)}{{\sum }_{a^{\prime }}\max (R^T(I,a^{\prime }),0)},& \text{if }{\sum }_{a^{\prime }}\max (R^T(I,a^{\prime }),0)>0\\ \frac{1}{|A(I)|},& \text{otherwise}\end{array}$$

5. 迭代：重复上述过程，最终平均策略收敛到纳什均衡

数学保证：CFR 算法保证在无限次迭代后，平均策略的遗憾上界趋近于零，即策略收敛到近似纳什均衡。

8.2.3 安全子博弈

在实际博弈求解中，常将完整的博弈分解为若干子博弈进行处理：

• 子博弈：从某个决策点开始的博弈子树
• 安全子博弈求解：在求解子博弈时，需要保留父博弈中对手可能策略的全部信息，避免信息丢失导致策略“不安全”

安全子博弈求解技术使 CFR 可以在博弈树的各个局部进行独立优化，同时保证全局策略的质量。

8.3 博弈规则设计

8.3.1 研究问题

博弈规则设计（机制设计）研究：如何在给定社会目标的前提下，设计博弈规则（机制），使得自利的个体在追求自身利益最大化的过程中，恰好实现设计者所期望的全局目标。

应用场景：

• 拍卖机制设计
• 匹配市场设计（如学生入学分配、器官移植匹配）
• 交通流量调度

8.3.2 双边匹配算法

问题描述：存在两类参与者（如申请者和接收者），需要在两类之间进行一一匹配，每个参与者对另一类参与者有严格的偏好排序。

延迟接受算法（Gale-Shapley算法）是求解稳定匹配的经典算法。

稳定匹配：不存在这样一对参与者，他们互相认为对方优于自己当前的匹配对象。

算法流程（以申请者主动为例）：

1. 每轮，每位未匹配的申请者向其偏好列表中尚未拒绝自己的最靠前接收者发出申请
2. 每个接收者保留当前最佳申请者（含上一轮暂留的），拒绝其余的
3. 重复直到没有新的申请发出

性质：

• 算法必然终止，且一定能找到稳定匹配
• 对主动方（申请者）是最优的，对被动方（接收者）是最劣的

8.3.3 单边匹配算法

问题描述：只有一类参与者（如室友分配），参与者之间相互匹配，每个参与者对所有其他参与者有偏好排序。

顶部交易循环算法（Top Trading Cycle, TTC）是求解单边匹配的经典方法，用于初始物品分配后的再交换等场景。

算法流程：

1. 每个参与者指向自己最喜欢（尚未被占有）的物品
2. 必然形成至少一个环路
3. 环路中的参与者互相交换物品，并离开市场
4. 重复以上步骤直到所有参与者离开

8.4 非完全信息博弈的实际应用

人工智能博弈的里程碑成果集中在非完全信息博弈领域：

AI系统	研发机构	博弈类型	成就
Libratus	卡内基梅隆大学	两人无限注德州扑克	2017年击败世界顶级人类玩家
Pluribus	卡内基梅隆大学 / Facebook	六人无限注德州扑克	2019年击败人类职业玩家
DeepStack	阿尔伯塔大学	两人无限注德州扑克	2017年达到职业玩家水平

这些系统综合运用了 CFR 算法、安全子博弈求解、蒙特卡洛采样、深度学习等技术，标志着人工智能在非完全信息博弈领域的重大突破。

8.5 小结

本章介绍了人工智能博弈的核心内容：

• 博弈论基础：博弈的要素、分类，以及核心概念纳什均衡
• 囚徒困境：经典的博弈模型，揭示了“个体理性并非总是导致集体最优”的现象
• 博弈策略求解：虚拟遗憾最小化（CFR）算法是求解大规模非完全信息博弈的关键方法，通过最小化累积遗憾使平均策略收敛到纳什均衡
• 博弈规则设计：通过设计匹配算法（如延迟接受算法、顶部交易循环算法），引导自利个体实现全局合意的结果
• 实际应用：在德州扑克等非完全信息博弈中，AI系统已达到甚至超越人类顶级玩家的水平