人工神经网络与深度学习

历史背景

人工神经网络如今已成为机器学习的主流方法。在计算机发展初期，由于算力限制，无法模拟大量神经元，因此神经网络一直未能得到广泛应用。2010年后，移动互联网快速发展，网络上积累了海量数据，这为人工智能的崛起提供了基础。从数学角度看，神经网络不像SVM那样有优雅的理论框架，但其核心理论实际上仍是1950-60年代建立的那一套，并没有本质突破。

1943年，心理学家McCulloch和数理逻辑学家Pitts建立了神经元的数学模型，称为MP模型，这是最早的感知器雏形。

感知器

问题定义

感知器要解决的是一个二分类问题：给定一组输入输出对 (x, y)，其中 y = \pm 1，目标是找到一个函数 f，使得 f(x) = y。

感知器采用的模型形式是：

这里 W 是权重向量，b 是偏置，\text{sign} 是符号函数。当 W^T x + b > 0 时输出 +1，否则输出 -1。感知器算法的任务就是从训练数据中自动学习出合适的 W 和 b。

算法流程

算法的具体步骤如下：

（1）随机初始化 W 和 b。

（2）取一个训练样本 (x, y)，检查分类是否正确：

（3）再取另一个样本 (x, y)，回到步骤（2）。

（4）终止条件：当所有训练样本都不满足步骤（2）中的任一条件时，算法结束。

与SVM的思想对比

感知器和SVM的优化思路完全不同。SVM是将所有训练数据 (x_i, y_i) 一次性输入，构造一个全局优化问题，然后求解这个优化问题得到最优分类面，这是一种全局视角的优化方式。而感知器采用的是逐样本试错的策略：每次只看一个样本，如果分类正确就保持参数不变，如果分类错误就调整参数，然后继续检查下一个样本。

参数更新规则的推导

现在解释为什么当分类错误时要按上述规则调整参数。以 y = -1 而 W^T x + b > 0 的情况为例：此时模型预测为正类，但真实标签是负类，说明当前的 (W, b) 对样本 x 分类错误。我们希望调整后 W^T x + b 的值能变小，趋向于负值。

按照更新规则：

将新参数代入计算：

由于 \|x\|^2 + 1 > 0，所以更新后的值比原来减小了 \|x\|^2 + 1，确实在朝着负方向调整。同理可以验证另一种情况的更新规则也是合理的。

增广向量的引入

为了简化算法的表述，引入增广向量的概念。

首先定义增广输入向量 \vec{x}，其定义与标签 y 相关：

然后定义增广权重向量：

这里把原来的权重 w 和偏置 b 合并成一个向量。

简化后的感知器算法

使用增广向量后，原问题可以转化为更简洁的形式：

（1）输入增广向量 \vec{x_i}，随机初始化 W，选取一个样本 \vec{x_i}。

（2）若 W^T \vec{x_i} < 0，则更新 W = W + \vec{x_i}。

（3）回到步骤（1），选取下一个样本。

（4）终止条件：当所有 \vec{x_i} 都满足 W^T \vec{x_i} \geq 0 时，算法终止。

增广形式与原形式的等价性

原本的分类条件是：

使用增广后的表达形式后，我们希望找到一个增广权重向量：

使得对于每一个样本 \vec{x_i}，都有：

这等价于以下两种情况之一成立（取决于 y）：

当 y = +1 时，\vec{x} = \begin{bmatrix} x \\ 1 \end{bmatrix}，则：

当 y = -1 时，\vec{x} = \begin{bmatrix} -x \\ -1 \end{bmatrix}，则：

即 w^T x + b \leq 0，与原条件一致。

通过增广向量的技巧，原本需要分两种情况讨论的更新规则被统一成了一个简洁的形式，这大大简化了算法的描述和分析。

感知器收敛定理

定理陈述

给定一组增广向量 \{\vec{x_i}\}_{i=1 \sim N}，如果这组数据是线性可分的，即存在某个 W_{\text{opt}} 使得对所有 i 都有 W_{\text{opt}}^T \vec{x_i} > 0，那么感知器算法必定在有限步内终止，得到一个 W 满足：

这个定理保证了在数据线性可分的前提下，感知器算法一定能够找到一个可行解，不会陷入无限循环。

证明过程

证明的核心思想是构造一个"距离函数"，然后证明每次参数更新时这个距离都会减小至少1。由于距离是非负的且有初始值，所以更新次数必然是有限的。

首先假设 \|W_{\text{opt}}\| = 1。这个假设是合理的，因为如果 W_{\text{opt}} 是一个可行解，那么对任意正数 c，cW_{\text{opt}} 也是可行解，所以我们总可以将其归一化。

假设在第 k 步时的权重为 W(k)，并且存在某个样本 \vec{x_i} 使得 W(k)^T \vec{x_i} < 0（即分类错误），根据感知器算法的更新规则：

现在引入一个参数 \alpha，考察 W(k) 与 \alpha W_{\text{opt}} 之间的距离如何变化。从更新规则可得：

对两边取范数的平方：

展开这个范数平方，利用 \|a + b\|^2 = \|a\|^2 + \|b\|^2 + 2a^T b：

现在分析最后两项的符号。根据假设，W(k)^T \vec{x_i} < 0（这正是触发更新的条件），而由于 W_{\text{opt}} 是可行解，所以 W_{\text{opt}}^T \vec{x_i} > 0。因此当 \alpha > 0 时，2W(k)^T \vec{x_i} - 2\alpha W_{\text{opt}}^T \vec{x_i} 这两项之和是负的。这说明只要 \alpha 取得足够大，就能使整个表达式的增量为负，即距离在减小。

确定参数α的取值

为了得到更精确的收敛速度估计，定义两个常数：

\beta 是所有增广向量的最大范数，\gamma 是最优解在所有样本上的最小间隔。由于数据线性可分且样本数有限，所以 \beta > 0，\gamma > 0。

取：

将这个 \alpha 代入之前的展开式。注意到 \|\vec{x_i}\|^2 \leq \beta^2 以及 W_{\text{opt}}^T \vec{x_i} \geq \gamma，所以：

由于 W(k)^T \vec{x_i} < 0，所以 2W(k)^T \vec{x_i} < 0，因此：

这个不等式表明，每次发生参数更新时，W 到 \alpha W_{\text{opt}} 的距离平方至少减少1。

收敛步数的上界

设初始距离为：

由于每次更新距离平方至少减少1，而距离平方始终非负，所以更新次数不会超过 D^2 次。这里需要注意的是，这个计数只包括实际发生参数更新的步骤（即存在分类错误的情况）。当不存在任何分类错误时，算法自然终止，此时得到的 W 就是满足条件的解。

因此，感知器算法至多经过 D^2 步更新后必然收敛。

人工神经网络的第一次寒冬

感知器算法虽然在线性可分的情况下能够保证收敛，但现实世界中的很多问题并非线性可分的。在1956年感知器刚提出时，研究者们并没有清晰地区分线性可分与线性不可分这两个概念。直到1969年，Minsky和Papert在他们的著作中严格地指出了感知器的局限性：单层感知器只能解决线性可分问题，而日常生活中大量问题是非线性可分的。

一个典型的例子是判断二值图像（每个像素非黑即白）是否全连通，即图像中所有白色像素是否可以通过相邻关系连接成一个整体。全连通的图像归为一类，非全连通的归为另一类。这个分类问题无法用一个线性超平面来划分，因此是非线性可分的。这个问题直接导致了神经网络研究的第一次寒冬，研究经费大幅削减，相关工作几乎停滞。

多层神经网络

网络结构

为了突破单层感知器的局限，需要引入多层神经网络。以一个简单的两层网络为例，设输入为 x_1, x_2，网络的计算过程如下：

第一层（隐藏层）的线性组合：

经过非线性激活函数 \phi(\cdot)：

第二层（输出层）的线性组合得到最终输出：

将整个过程合并起来，可以写成：

非线性激活函数的必要性

非线性函数 \phi(\cdot) 在多层网络中起着关键作用。如果没有这个非线性函数，即令 \phi 为恒等映射，那么上述表达式将变为：

展开后：

这可以简化为：

其中 \tilde{W}_1, \tilde{W}_2, \tilde{b} 是某些常数。这说明无论堆叠多少层线性变换，最终的效果都等价于一个单层的线性模型，网络的表达能力没有任何提升。因此，非线性激活函数是多层网络能够超越单层感知器的关键所在。

激活函数的选择

最初使用的非线性函数是阶跃函数（也称为Heaviside函数），其输出只有0和1两个值。通过使用阶跃函数作为激活函数，可以证明神经网络能够逼近任意复杂的决策边界。

三层神经网络的表达能力

存在一个基本定理：三层神经网络可以模拟任意的决策面。这里的"决策面"指的是在特征空间中划分不同类别的边界。在二维情况下，决策面退化为决策曲线。

从理论到实践的鸿沟

尽管有了三层网络可以逼近任意决策面的理论保证，但从理论到实际应用仍然存在巨大差距。在实际问题中，我们只有训练数据 (x_i, y_i)，需要从数据中学习出网络的权重 W 和偏置 b。如何确定网络应该有多少层、每层应该有多少个神经元、如何有效地训练网络参数——这些问题在当时都没有完善的理论指导，更多依赖于经验积累和反复试验。

反向传播算法

梯度下降法

反向传播算法（Back Propagation，简称BP）是训练神经网络的核心方法，其主要思想基于梯度下降法求局部极值。

考虑如何寻找一个函数 f(w) 的最小值点。首先随机选取一个初始值 w_0，计算该点处的导数：

导数的符号指示了函数增长的方向，因此沿着导数的反方向移动就是函数下降的方向。不断重复这个过程，直到到达极值点，此时导数为零。需要注意的是，这个方法的效果与初始值的选取密切相关，不同的初始值可能导致收敛到不同的局部极小值。

梯度下降法的具体步骤如下：

（1）选取初始值 w_0。

（2）设 k = 0，检查 \frac{df(w)}{dw}\Big|_{w_k} 是否为零。若为零则停止，否则按以下规则更新：

• 其中 \lambda > 0 是步长参数（也称学习率）。

梯度下降法的数学解释

用泰勒展开可以解释为什么沿负梯度方向能使函数值下降。对 f(w + \Delta w) 在 w 处展开：

其中 o(\Delta w) 是 \Delta w 的高阶无穷小项。将更新规则代入

此时

因此

忽略高阶项后：

由于 \alpha > 0 且 \left[\frac{df(w)}{dw}\Big|_{w_k}\right]^2 \geq 0，所以

函数值确实在下降。

梯度只是提供了一个下降方向，具体的更新策略可以有很多变种，例如自适应调整步长 \alpha，这催生了诸如Adam、RMSprop等优化算法。

BP算法的推导

问题设定

继续使用之前的两层神经网络作为例子。网络的计算过程为：

合并后的表达式为：

假设网络结构已经确定，给定训练数据 \{(x_i, Y_i)\}_{i=1..N}，目标是调节所有的权重 W 和偏置 b，使得网络输出 y 尽量接近真实标签 Y。

损失函数的定义

对于输入 (x, Y)，定义损失函数（也称目标函数）：

这里 Y 是真实标签（在SVM中 Y \in \{+1, -1\}），系数 \frac{1}{2} 是为了求导后能消去平方带来的系数2，使表达式更简洁。

BP算法的整体流程

（1）随机初始化所有参数 (W_1, W_2, W_{11}, W_{12}, W_{21}, W_{22}, b_1, b_2, b)。

（2）计算损失函数对所有参数的偏导数：

（3）按梯度下降规则更新参数：

（4）当所有偏导数都为零时，算法终止。

偏导数的计算

BP算法的核心在于如何高效地计算 \frac{\partial E}{\partial W} 和 \frac{\partial E}{\partial b}。虽然计算过程略显繁琐，但思路很简单，利用链式法则，从输出层向输入层逐层计算。

这里需要注意，激活函数 \phi 不能是阶跃函数（因为阶跃函数不可导），而应该是连续可导的函数，如sigmoid或tanh。

首先计算几个关键节点处的偏导数，因为它们位于网络的连接处，后续计算会用到：

上式是损失函数对网络输出的偏导，由 E = \frac{1}{2}(y-Y)^2 直接求导得到。

这两个偏导数用到了链式法则，从 E 到 a_1 需要经过 y \to z_1 \to a_1 这条路径。

有了这三个关键偏导数，计算其他参数的偏导就变得简单了。

输出层参数的偏导数：

隐藏层参数的偏导数：

为什么叫反向传播

算法的名称来源于计算顺序。首先输入一个样本 x，进行前向计算，依次得到 a_1, a_2, z_1, z_2, y 的数值，然后计算偏导数时，顺序是从后向前的：先计算 \frac{\partial E}{\partial y}，再利用它计算 \frac{\partial E}{\partial a_1} 和 \frac{\partial E}{\partial a_2}，最后计算各层参数的偏导数。误差信号从输出层向输入层逐层"反向传播"，这就是BP算法名称的由来。这种计算顺序的好处是避免了重复计算，每个中间结果只需计算一次就可以被多次复用。

激活函数的选择与改造

阶跃函数的局限性

前面提到激活函数 \phi(x) 如果选用阶跃函数，会面临一个根本性问题：阶跃函数在跳变点处不可导，在其他点导数为零。这意味着无法计算 \phi'(x)，整个BP算法的链式求导就无法进行。因此必须对激活函数进行改造，使其既保持非线性特性，又处处可导（或几乎处处可导）。

Sigmoid函数

第一种改造方案是Sigmoid函数：

这个函数的输出范围是 (0, 1)，当 x \to +\infty 时输出趋近于1，当 x \to -\infty 时输出趋近于0，形状类似于平滑化的阶跃函数。

Sigmoid函数的导数：

因此

一旦计算出 \phi(x) 的值，其导数可以直接用这个值本身表示，无需额外计算指数函数。同时，Sigmoid函数同样能够解决阶跃函数所能解决的非线性分类问题。

Tanh函数

第二种改造方案是双曲正切函数：

其输出范围是 (-1, 1)，相比Sigmoid是零中心化的。导数为：

同样地，导数可以用函数值本身来表示。

ReLU函数

在深度学习兴起后，出现了新的激活函数设计。ReLU（Rectified Linear Units，修正线性单元）定义为：

其导数为：

ReLU将所有负值压缩为零，这可以有效减少每一层中活跃神经元的数量，降低计算负担，同时也起到一定的稀疏化作用。但这种做法可能过于激进，当输入为负时梯度完全为零，可能导致某些神经元永远无法被激活。

Leaky ReLU函数

为了缓解ReLU的问题，引入了Leaky ReLU：

其导数为：

这里 \beta 是一个较小的正数（如0.01）。当输入为负时，输出不再是零，而是一个较小的负值，这样梯度也不会完全消失，神经元仍有机会被更新。

多层神经网络的矩阵表示

前向传播的一般形式

对于更复杂的多层神经网络，需要用矩阵形式来统一描述。设输入为 x，网络的前向传播过程如下：

第一层：

这里 z^{(1)} 是第一层的线性组合结果，a^{(1)} 是经过激活函数后的输出。

第二层：

以此类推，第 m 层的计算为：

权重矩阵的结构

假设输入有 n 个变量，第一层有 m 个神经元，则第一层的权重矩阵 W^{(1)} 的维度为 m \times n：

矩阵的第 i 行对应第 i 个神经元的所有输入权重。这样 W^{(1)} x 就是一个 m 维向量，每个分量是一个神经元的线性组合结果。

输出层

设网络共有 L 层，最后一层的计算为：

网络的最终输出为：

这种矩阵表示法将之前针对单个神经元的计算推广到了任意规模的网络，使得理论分析和代码实现都更加简洁统一。后续在设计更复杂的网络结构时，会在这个框架基础上进一步扩展。

BP算法的完整推导

符号定义

在推导之前，先明确符号约定：

（1）网络共有 L 层。

（2）z^{(k)}、a^{(k)}、b^{(k)} 分别表示第 k 层的线性组合向量、激活输出向量和偏置向量，它们的维度与第 k 层的神经元个数一致。

（3）z_i^{(k)}、a_i^{(k)}、b_i^{(k)} 表示上述向量的第 i 个分量，即第 k 层第 i 个神经元对应的值。

（4）用 y_i 表示网络输出 y 的第 i 个分量，Y_i 表示真实标签的第 i 个分量。

BP算法流程

（1）随机初始化所有参数 (W, b)。

（2）给定训练样本 (x, Y)，其中 x 是输入特征，Y 是期望输出。这里先假设只有一个训练样本，将 x 代入网络进行前向传播，计算出所有层的 (z, a) 以及最终输出 y。

（3）定义目标函数（损失函数）：

目标是最小化 E。接下来通过链式法则计算 E 对所有参数的偏导数。

（4）按梯度下降规则更新参数：

关键节点的定义

为了高效地计算所有偏导数，定义关键中间量：

这个量表示损失函数对第 m 层第 i 个神经元线性组合输出的偏导数。一旦知道了所有的 \delta，就可以方便地计算出对权重和偏置的偏导数。

输出层的δ计算

对于输出层（第 L 层），由于 y_i = a_i^{(L)} = \varphi(z_i^{(L)})，根据链式法则：

上面的求导用到了以下两个公式

损失函数:

激活函数的导数

隐藏层的δ递推公式

对于隐藏层（第 m 层，1 \leq m \leq L-1），根据反向传播，需要利用已知的第 m+1 层的 \delta 来计算第 m 层的 \delta。

根据链式法则：

回顾激活函数的导数

第一项 \frac{\partial E}{\partial a_i^{(m)}} 需要考虑 a_i^{(m)} 如何影响下一层。由于 a_i^{(m)} 会通过权重连接到第 m+1 层的所有神经元，设第 m+1 层有 s_{m+1} 个神经元，则：

这里 w_{ji}^{(m+1)} 是从第 m 层第 i 个神经元到第 m+1 层第 j 个神经元的权重。

综合起来，隐藏层的递推公式为：

权重和偏置的偏导数

有了所有层的 \delta 值后，计算权重和偏置的偏导数如下：

权重 w_{ij}^{(m)}（从第 m-1 层第 i 个神经元到第 m 层第 j 个神经元）的梯度等于目标神经元的 \delta 乘以源神经元的激活值。

偏置的梯度就是对应神经元的 \delta 值本身。

神经网络训练的实际问题

待解决的问题

完整的BP算法还需要解决几个实际问题：如何初始化参数 W 和 b、目标函数 E 如何设定、训练何时停止。

监控训练过程

训练过程中，应当监控目标函数在训练集上的平均值（通常称为cost或loss）。正常情况下，随着训练的进行，cost应该逐渐减小。如果cost出现增大，需要停下来检查原因。可能的情况有两种：一是模型不够复杂，无法完全拟合训练数据；二是模型已经训练得足够好了。

验证集的使用

训练的最终目的不是在训练集上取得最低的loss，而是让模型在未见过的数据上有良好的泛化能力。因此需要从数据中划分出一部分作为验证集（Validation Set），验证集不参与训练过程。每训练一段时间后，在验证集上测试模型的识别率，保存在验证集上表现最好的模型参数作为最终结果。

学习率的调整

学习率 \alpha 的选择对训练效果影响很大。如果刚开始训练几步cost就上升，通常说明学习率过高，参数更新幅度太大，跳过了极值点。如果每次cost变化很小，训练进展缓慢，则说明学习率过低，需要适当提高。

过拟合问题

模型可能出现过拟合（overfitting）的情况：在训练集上表现很好，但在验证集或测试集上表现较差。这类似于一个只会死记硬背的学生，虽然能完美记住所有习题，但遇到新题就无法应对。验证集的作用正是作为一个独立的评判标准，帮助我们发现过拟合并及时停止训练，选择泛化能力最好的模型。

随机梯度下降

批量训练的思想

在实际训练中，并不是每输入一个样本就立即更新参数。更常用的做法是：将多个样本组成一批（称为一个Batch或Mini-Batch），计算这批样本梯度的平均值，然后根据这个平均值来更新参数。

使用批量训练的好处是可以减少噪声的影响。单个样本可能具有一定的随机性，其梯度方向未必是全局最优的下降方向。通过对多个样本的梯度求平均，可以得到一个更稳定、更具代表性的下降方向，从而使训练过程更加平稳。

训练技巧

数据归一化

训练数据在输入网络之前，通常需要进行归一化处理。常用的方法是对数据做均值和方差的归一化：

归一化后的数据均值为0，方差为1。这样做可以使不同特征处于相同的尺度，避免某些特征因数值过大而主导训练过程。

参数初始化与梯度消失

参数 (W, b) 的初始化对训练效果有重要影响。如果初始化不当，可能会出现梯度消失现象：当 W^T x + b 的值一开始就很大或很小时，激活函数（如Sigmoid或Tanh）会进入饱和区，此时激活函数的导数趋近于0。根据BP算法的链式法则，这个接近0的导数会向前传播，导致前面所有层的梯度也趋近于0，使得训练变得极其缓慢甚至停滞。

为了避免这个问题，需要让 W^T x + b 的初始值在零附近。一种简单有效的初始化方法是：从区间 \left(-\frac{1}{\sqrt{d}}, \frac{1}{\sqrt{d}}\right) 均匀随机采样来初始化 (W, b)，其中 d 是该层的神经元个数。

假设输入 x 服从均值为0、方差为1的正态分布，且各维度相互独立，而 (W, b) 从 \left(-\frac{1}{\sqrt{d}}, \frac{1}{\sqrt{d}}\right) 均匀分布中采样，可以证明 W^T x + b 服从均值为0、方差为 \frac{1}{3} 的正态分布。这样就保证了线性组合的输出不会过大或过小。

Batch Normalization

参数初始化问题实际上相当复杂，因为即使初始时分布合适，经过多层传播后分布也可能发生变化。一种更彻底的解决方案是Batch Normalization（批归一化）：对每一层的输出都做归一化处理，使每一层的输入都保持在0附近，分布稳定。

但直接归一化会带来一个问题：如果每层输出都被强制归一化到均值0、方差1，那么网络的表达能力会受限，趋向于线性化。为了解决这个问题，引入两个可学习的参数 \gamma 和 \beta，对归一化后的值进行缩放和平移：

这样既保持了归一化的稳定性，又通过可学习的参数恢复了网络的非线性表达能力。

目标函数的选择

添加正则项

为了防止过拟合，可以在目标函数中添加正则项（Regularization Term）。带正则项的目标函数形式为：

其中 F(W) 是原始的损失函数，R(W) 是正则项。一个常见的形式是：

第一项是预测误差的平方和，第二项是所有权重的平方和（L2正则），\beta 是正则化系数。正则项的作用是惩罚过大的权重值，鼓励模型学习更平滑的函数，从而提高泛化能力。

Softmax函数与交叉熵

对于分类问题，损失函数 F(W) 通常采用Softmax函数和交叉熵的组合。

Softmax函数将网络输出转换为概率分布。设网络最后一层的输出为 z_1, z_2, \ldots, z_N（对应 N 个类别），Softmax函数定义为：

经过Softmax变换后，q_i \geq 0 且 \sum_{i=1}^N q_i = 1，可以解释为样本属于第 i 类的预测概率。

我们希望网络学习从输出向量 Z = \begin{bmatrix} z_1 \\ z_2 \\ \vdots \\ z_N \end{bmatrix} 到真实概率分布 P = \begin{bmatrix} p_1 \\ p_2 \\ \vdots \\ p_N \end{bmatrix} 的映射

其中

在分类任务中，P 通常是one-hot编码，即真实类别对应的分量为1，其余为0。

交叉熵（Cross Entropy）用于衡量预测分布 Q 与真实分布 P 之间的差异，定义为：

当预测分布 Q 越接近真实分布 P 时，交叉熵越小。

Softmax与交叉熵组合的优势

当使用Softmax函数和交叉熵的组合作为目标函数时，求导会得到非常简洁的形式：

梯度就是预测概率与真实概率之差。如果预测正确（q_i 接近 p_i），梯度接近0，参数几乎不更新，如果预测错误，梯度较大，参数会有较大的调整。这种简洁的梯度形式不仅计算高效，而且数值稳定，是分类任务中的标准选择。

随机梯度下降法的问题与改进

SGD的两个主要问题

随机梯度下降法虽然简单有效，但存在两个主要问题。

第一个问题是各参数分量获得的梯度绝对值差异较大。某些参数的梯度很大，某些参数的梯度很小。由于所有参数使用相同的学习率，梯度大的参数更新幅度大，梯度小的参数更新幅度小，这会导致优化路径呈现Z字形震荡，而不是沿着最优方向直接前进。

第二个问题是梯度估计过于随机。由于每次更新使用的是不同的Batch数据，连续两次计算得到的梯度方向可能差异很大，导致优化方向不稳定，训练过程出现较大波动。

损失函数可以写成所有样本损失的平均：

对应的梯度为：

改进策略

针对上述问题，有几种常用的改进策略。

AdaGrad方法为每个参数维护一个历史梯度平方和，然后用这个累积量来自适应调整每个参数的学习率。梯度较大的参数会获得较小的有效学习率，梯度较小的参数会获得较大的有效学习率，从而缓解Z字形震荡问题。

RMSProp是AdaGrad的改进版本，使用指数移动平均来计算历史梯度的平方，避免了AdaGrad中累积量不断增大导致学习率趋近于零的问题。

Momentum方法引入动量的概念来平滑梯度的随机波动。其更新规则为：

这里 v_t 是动量项，\rho 是动量系数（通常取0.9左右）。动量项会累积历史梯度信息，使得更新方向更加稳定。如果连续多次梯度方向一致，动量会加速收敛；如果梯度方向频繁变化，动量会起到平滑作用。

Adam方法结合了Momentum和RMSProp的思想，同时维护梯度的一阶矩估计和二阶矩估计，是目前应用最广泛的优化器之一。

训练建议

Batch Normalization是一个非常有效的技术。使用Batch Normalization后，模型对学习率和参数更新策略的选择不太敏感。如果使用了Batch Normalization，更新策略用最简单的SGD即可，加上其他复杂的优化器反而可能效果变差。

如果不使用Batch Normalization，通过合理调整其他参数的组合，也可以达到训练目的，但需要更多的调参经验。

由于梯度累积效应，AdaGrad、RMSProp和Adam这三种策略在训练后期学习率会变得很小，导致收敛速度变慢。可以通过适当提高学习率来补偿这一效应。

从神经网络到深度学习

多层神经网络的优势

基本单元（单个神经元）非常简单，但多个基本单元组合起来可以表达非常复杂的非线性函数。这种模块化设计使得网络易于构建，同时具有很强的表达能力。

训练和测试过程中的矩阵运算具有很好的并行性，非常适合在GPU和分布式系统上运行，这是深度学习能够处理大规模数据的硬件基础。

神经网络的设计思想来源于对人脑的仿生研究，这个话题能够吸引来自神经科学、心理学、计算机科学等多个领域的研究人员参与，形成了丰富的研究生态。

多层神经网络的劣

从数学角度看不够优雅。优化算法只能找到局部极值而非全局最优，算法性能与参数初始化密切相关，缺乏像SVM那样的理论保证。

模型缺乏可解释性。训练得到的大量权重参数与实际任务之间的关联非常模糊，难以理解网络究竟学到了什么。

可调参数太多，包括网络层数、每层神经元个数、激活函数类型、学习率、优化方法、终止条件等，使得训练神经网络在很大程度上依赖经验和直觉

训练复杂网络需要海量数据。模型参数越多，需要的训练样本就越多，否则容易过拟合。

深度学习的主要内容

深度学习涉及的主要内容包括：常用数据库介绍、自编码器（Auto Encoder）、卷积神经网络（CNN）、深度学习工具（如TensorFlow和Caffe）、以及流行的网络结构（LeNet、AlexNet、VGGNet、GoogLeNet、ResNet等）。

卷积神经网络

从手工设计到自动学习卷积核

传统图像处理中，卷积核是人工设计的。例如傅里叶变换：

这里 e^{-j\omega t} 就是一种卷积核，通过不同频率的正弦波基函数与信号做内积，提取出各频率分量。Gabor变换是另一种常用的加权变换，其卷积核结合了正弦波和高斯包络。

卷积神经网络的核心思想是：不再人工设计卷积核，而是让网络自动从数据中学习最适合任务的卷积核。

卷积操作与权值共享

图像卷积可以看作全连接网络的一种特殊形式，其关键特性是权值共享。以一个简单的例子说明：设输入图像为 3 \times 3，卷积核为 2 \times 2，偏置为 2 \times 2，输出特征图为 2 \times 2：

展开计算每个输出：

可以看到 w_1, w_2, w_3, w_4 这四个权重在计算不同位置的输出时被重复使用，这就是权值共享。权值共享大大减少了网络的参数数量，同时使得卷积核能够检测图像中任意位置的相同模式。

特征图大小的计算

设输入图像大小为 M \times N，卷积核大小为 m \times n，步长为 (U, V)。卷积操作时，卷积核从左上角开始，每次水平移动 U 个像素、垂直移动 V 个像素。

以水平方向为例，第 k 个位置覆盖的范围是从 1 + (k-1)U 到 m + (k-1)U，要求不超过图像边界 M，即 m + (k-1)U \leq M。

因此，输出特征图的大小为：

卷积层的梯度计算

由于权值共享，计算权重梯度时需要把所有使用该权重的位置的贡献加起来。以 w_1 为例：

每一项对应 w_1 参与计算的一个输出位置，梯度等于该位置的误差信号乘以对应的输入值。

池化层

池化（Pooling）操作用于降低特征图的空间分辨率。例如从 6 \times 28 \times 28 变为 6 \times 14 \times 14，是对每个 2 \times 2 的区域取平均值（平均池化）或最大值（最大池化）。

在反向传播时，池化层的梯度处理相对简单：对于平均池化，将上层传来的梯度均分给池化区域内的每个位置；对于最大池化，梯度只传给池化区域内取得最大值的那个位置。

强化学习

强化学习与监督学习的区别

强化学习是一种与监督学习有本质区别的机器学习范式，主要体现在以下几个方面。

在监督学习中，训练数据由输入和对应的标签组成，模型的目标是学习从输入到标签的映射。而在强化学习中，训练数据没有标签，取而代之的是奖励函数（Reward Function），它告诉智能体某个行为的好坏程度，但不直接告诉它应该采取什么行为。

监督学习的训练数据是事先给定的静态数据集，而强化学习的训练数据是通过智能体的行为（Action）动态获得的。智能体与环境交互，根据采取的行为获得新的状态和奖励，这些构成了训练数据。

强化学习中，当前的行为不仅影响即时奖励，还会影响后续能够获得的状态和奖励。这种延迟效应使得问题变得复杂：一个短期看起来不好的行为，可能在长期带来更大的收益。

强化学习的最终目标是构建一个从状态（State）到行为（Action）的映射函数。状态描述了当前内部和外部环境的情况，智能体（Agent）根据这个函数在每个状态下决定应该采取的行为，使得长期累积的奖励最大化。

Q学习

基本定义

首先定义强化学习中的基本符号：

在基本的Q学习框架中，假设状态数有限，行为数也有限。这个假设使得问题可以用表格形式来表示和求解。

马尔可夫假设

强化学习通常基于以下几个关键假设。

马尔可夫假设：t+1 时刻的状态只与前一时刻 t 的状态有关，与更早的历史状态无关。用概率语言表达：

这个假设大大简化了问题的复杂度，因为不需要记录完整的历史轨迹，只需要知道当前状态即可。

状态转移假设：下一时刻的状态只与当前时刻的状态以及当前时刻的行为有关。定义状态转移概率：

这个概率描述了在状态 s 下采取行为 a 后，转移到状态 s' 的概率。

奖励函数假设：下一时刻的奖励只与当前时刻的状态及当前时刻的行为有关。定义期望奖励：

马尔可夫决策过程

过程描述

马尔可夫决策过程描述了智能体与环境交互的完整流程。

在 t=0 时刻，环境给出一个初始状态 s_0 \sim p(s_0)。

然后从 t=0 开始循环执行以下步骤：

• 智能体根据当前状态 s_t 选择行为 a_t
• 环境根据当前状态和行为采样奖励 r_t \sim R(\cdot \mid s_t, a_t)
• 环境产生下一个状态 s_{t+1} \sim P(\cdot \mid s_t, a_t)
• 智能体获得奖励 r_t 和下一个状态 s_{t+1}，然后进入下一轮循环。

学习目标

我们需要学习一个策略（Policy）\pi^*，这是一个从状态到行为的映射函数。给定任意状态，策略函数告诉我们应该采取什么行为。目标是找到最优策略，使得累积奖励最大化。

累积奖励

强化学习的优化目标是累积奖励，定义为：

这里 \gamma \in [0, 1) 是衰减因子。衰减因子的作用是让近期的奖励比远期的奖励更重要，同时保证无穷级数收敛。当 \gamma 接近0时，智能体只关注即时奖励；当 \gamma 接近1时，智能体更重视长期收益。

在这个框架中，已知的函数是 R_s^a = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a]，即在每个状态-行为对下能获得的期望奖励。需要学习的函数是策略 \pi(S_t, a_t) = p(a_t \mid S_t)，即在每个状态下应该以什么概率选择各个行为。

价值函数与Q函数

定义

根据一个策略 \pi，智能体与环境交互会产生一条轨迹：s_0, a_0, r_0, s_1, a_1, r_1, \ldots

价值函数（Value Function）衡量从某个状态出发，按照策略 \pi 行动，最终能获得多少累积奖励：

Q函数衡量从某个状态出发，首先采取某个特定行为，然后按照策略 \pi 行动，最终能获得多少累积奖励：

价值函数和Q函数的关系是：

状态 s 的价值等于在该状态下所有可能行为的Q值按行为概率加权求和。

贝尔曼方程的推导

价值函数可以进一步展开。将累积奖励拆分为即时奖励和未来奖励两部分：

注意到 \sum_{t=0}^{+\infty} \gamma^t r_{t+1} 正是从 s_1 出发的累积奖励，即 V^{\pi}(s_1)。将期望按照行为和下一状态展开：

这就是贝尔曼方程。它建立了当前状态价值与后继状态价值之间的递推关系。

在这个方程中，P_{ss'}^a（状态转移概率）和 R_s^a（期望奖励）是已知的环境参数。未知的是策略 p(a \mid s) 和价值函数 V^{\pi}(s')。

内层求和 \sum_{s' \in \mathcal{S}} P_{ss'}^a (R_s^a + \gamma V^{\pi}(s')) 正好等于 Q^{\pi}(s, a)，因此贝尔曼方程也可以写成：

策略迭代算法

基本思路

如果策略 \pi(s, a) = p(a \mid s) 已知，那么贝尔曼方程变成关于 V^{\pi}(s) 的线性方程组（状态数有限时），可以直接求解。

策略迭代的做法是交替进行两个步骤：固定策略求价值函数，然后固定价值函数改进策略。

首先给策略 p(a \mid s) 一个初始值。然后根据贝尔曼方程求解 V^{\pi}(s)。接下来利用 V^{\pi}(s) 计算Q函数：

策略改进

现在的问题是：如果 Q^{\pi}(s, a) 已知，如何调整 p(a \mid s) 使得 V^{\pi}(s) 最大？

由于

是Q值的加权平均，要使这个加权平均最大，最优策略是把所有概率集中到Q值最大的行为上。因此定义新策略：

这个策略称为贪心策略：在每个状态下，总是选择使Q值最大的行为。

迭代收敛

策略迭代算法不断重复上述过程：用当前策略计算价值函数，用价值函数计算Q函数，用Q函数改进策略。可以证明这个迭代过程必定收敛到最优策略（证明略）。

收敛后得到最优价值函数 V^*(s) 和最优策略 \pi^*，满足：

总结来说，策略迭代的核心思想是：固定 \pi 算 V，或者固定 V 算 \pi，交替进行直到收敛。

策略迭代算法的完整流程

算法输入

算法的输入是一个马尔可夫决策过程的完整描述 E = \langle S, A, P, R \rangle，其中 S 是状态集合，A 是行为集合，P 是状态转移概率，R 是奖励函数。

初始化

对所有状态 s \in S，将价值函数初始化为零：V(s) = 0。

将策略初始化为均匀随机策略：\pi(s, a) = \frac{1}{|A|}，即在每个状态下以相同概率选择所有可能的行为。这里 |A| 是行为的总数。

主循环结构

算法采用双层嵌套循环结构。外层循环负责策略改进，内层循环负责策略评估。

内层循环：策略评估

在策略 \pi 固定的情况下，通过迭代计算价值函数 V。对所有状态 s \in S，根据贝尔曼方程计算新的价值函数：

状态 s 的价值等于在该状态下按策略 \pi 选择各行为的概率，乘以每个行为带来的期望回报（即时奖励加上衰减后的后继状态价值），然后对所有行为和所有可能的后继状态求和。

计算完所有状态的新价值后，检查收敛条件：如果 \|V - V'\| < \epsilon，说明价值函数已经收敛，退出内层循环；否则令 V = V'，继续迭代。

策略改进

当内层循环收敛后，价值函数 V 已经稳定。接下来对所有状态 s \in S 和所有行为 a \in A，计算Q函数：

然后根据Q函数重新安排策略：

这是贪心策略改进：在每个状态下，选择使Q值最大的行为，将该行为的概率设为1，其他行为的概率设为0。

外层循环的终止条件

检查新策略 \pi 与旧策略 \pi' 的差异：如果 \|\pi - \pi'\| < \delta，说明策略已经稳定，不再发生变化，退出外层循环；否则令 \pi = \pi'，回到内层循环重新进行策略评估。

算法输出

当外层循环终止时，输出当前的策略 \pi，这就是算法找到的最优策略。

算法逻辑总结

首先固定策略，反复迭代直到价值函数收敛（策略评估），然后根据收敛的价值函数计算Q函数，并据此改进策略（策略改进），接着用新策略重新进行策略评估，如此交替进行，直到策略不再变化。由于每次策略改进都会使价值函数单调不减，而价值函数有上界，因此算法必定收敛。

策略迭代算法的局限性

前面介绍的策略迭代算法存在一个大问题：当状态数和行为数很多时，算法变得不现实。因为需要对每个状态-行为对都存储和更新Q值，空间复杂度和时间复杂度都与状态数和行为数的乘积成正比。只有在状态数和行为数都较少的情况下，算法才能有效收敛。

最优Q函数与贝尔曼最优方程

最优Q函数的定义

一个更聪明的做法是直接定义最优Q函数。不再针对某个特定策略 \pi 计算Q值，而是直接考虑所有可能策略中最优的那个：

在状态 s 下采取行为 a，然后按照最优策略行动，能够获得的最大累积奖励。这里遍历了所有可能的策略 \pi，取其中使累积奖励最大的那个。

贝尔曼最优方程

最优Q函数满足贝尔曼最优方程：

最优Q值等于即时奖励加上衰减后的后继状态最优Q值的最大值。与之前的贝尔曼方程不同，这里不需要对行为求期望（因为最优策略总是选择Q值最大的行为），而是直接取最大值。

深度Q网络

基本思路

当状态空间很大时（如图像输入），无法用表格存储所有状态-行为对的Q值。DQN的核心思想是用深度神经网络来近似最优Q函数：

其中 \theta 是神经网络的参数。网络的输入是状态 s，输出是该状态下所有行为的Q值。

损失函数

将贝尔曼最优方程与神经网络结合，构造损失函数。定义目标值：

这里使用上一轮的参数 \theta_{i-1} 计算目标值，而不是当前参数，这样可以提高训练稳定性。

损失函数定义为预测Q值与目标值之间的均方误差：

梯度计算

通过反向传播计算损失函数对参数的梯度：

括号内的第一部分是目标值与预测值的差（即TD误差），第二部分是Q网络输出对参数的梯度。

ε-贪心策略

在训练过程中，需要平衡探索（exploration）和利用（exploitation）。如果总是选择当前认为最优的行为，可能会陷入局部最优，错过更好的策略。\varepsilon-贪心策略的做法是：以小概率 \varepsilon 随机选择行为进行探索，以概率 1-\varepsilon 选择当前Q值最大的行为。

DQN算法完整流程

初始化

初始化Q网络参数 \theta，初始化经验回放内存 D。经验回放内存用于存储智能体与环境交互产生的经验数据。

外层循环：游戏回合

对 \text{episode} = 1 \sim M（共进行 M 次游戏）：

初始化 s_1，即进入游戏的初始状态（如游戏初始画面）。

内层循环：时间步

对 t = 1 \sim T（按时间步采样）：

首先根据 \varepsilon-贪心策略选择行为，如果随机数小于给定概率（即 \varepsilon），则采取随机行为 a_t，否则选择使Q值最大的行为：

执行行为后，环境返回下一状态和奖励：

将这次经验 (s_t, a_t, r_t, s_{t+1}) 存入经验回放内存 D。

从内存 D 中随机抽取一个batch的数据 (s_j, a_j, r_j, s_{j+1})_{j=1 \sim p}。随机抽样而非按顺序使用可以打破数据之间的时间相关性，提高训练稳定性。

对每个样本计算目标值：

如果下一状态是终止状态（如游戏结束），则没有后续奖励，目标值就是即时奖励，否则需要加上衰减后的未来最大Q值。

根据梯度下降更新参数：

算法输出

训练完成后，输出深度神经网络 Q(s, a; \theta)。给定任意状态，选择使Q值最大的行为即为最优策略。

Q-learning的局限性

Q-learning及其变体仍然存在一些根本性的局限。

在某些应用中，状态数或行为数非常庞大，使得Q函数极其复杂，难以收敛。以图像识别类应用为例，如果输入是一幅图像，状态数等于（每个像素可能的取值数）的（像素总数）次方，这是一个天文数字。DQN通过神经网络来近似Q函数，虽然缓解了这个问题，但本质上仍然是通过大量数据来拟合，对图像内容和任务本身缺乏真正的理解。

在很多实际问题中，如下棋程序，奖励只在最后才获得（赢或输），中间步骤没有明确的奖励信号。这种稀疏奖励问题使得Q-learning的信用分配变得困难：很难判断哪一步棋对最终结果贡献最大。

策略梯度方法

基本思想

策略梯度方法与Q-learning的思路不同。Q-learning是先学习Q函数，再根据Q函数推导策略，而策略梯度方法直接学习策略本身。

具体做法是：在每个状态下，根据当前的策略 P(a_t | s_t) 来采样行为 a_t。智能体与环境不断交互，产生一组状态-行为轨迹：s_1, a_1, s_2, a_2, \ldots, s_T, a_T。

在轨迹结束时，获得最终奖励 r_T。这个奖励可正可负：正值表示获得奖励（好的结果），负值表示惩罚（坏的结果）。

策略更新规则

根据最终奖励 r_T 来修改轨迹中每一步的策略概率：

如果最终获得了正奖励，说明这条轨迹上的行为选择是好的，应该增加这些行为被选中的概率，如果获得了负奖励，说明这些行为选择不好，应该降低它们的概率。

如果用神经网络参数化策略，即 P(a_t | s_t) \sim Q(s_t, a_t; \theta)，则参数更新规则变为：

这里 \nabla_{\theta} Q(s_t, a_t; \theta) 是Q网络输出对参数 \theta 的梯度。当 r_T > 0 时，参数沿着使该行为概率增大的方向调整，当 r_T < 0 时，参数沿着使该行为概率减小的方向调整。

策略梯度的缺点

策略梯度方法存在两个主要缺点。首先，训练过程比Q-learning更加缓慢，因为每次更新都需要完整地执行一条轨迹，而且梯度估计的方差较大。其次，需要特别精心地调节奖励 r_T 的设计，算法才能相对收敛。如果奖励设计不当，训练可能非常不稳定。

引入基线的改进

为了降低梯度估计的方差，引入一个基线（baseline）。改进后的更新规则为：

这里 V(s_t) 是状态 s_t 的价值函数，作为预期收益的估计。回顾价值函数的定义：

它衡量从状态 s 出发，按照策略 \pi 行动，最终能获得的期望累积奖励。

引入基线后，更新量变成了 r_T - V(s_t)，即实际获得的奖励与预期奖励之差。这个差值称为优势（advantage）：如果实际奖励高于预期，说明这个行为比平均水平好，应该增加其概率；如果实际奖励低于预期，说明这个行为不如平均水平，应该降低其概率。这种相对评价比绝对评价更加稳定。

当状态数很多时，无法用表格存储所有状态的价值函数。解决方法是用另一个深度神经网络来估计价值函数，这个网络称为估值网络（Critic）。输入是状态 s，输出是该状态的预期累积收益。

Actor-Critic算法

算法框架

Actor-Critic算法结合了策略梯度和价值函数估计两种方法。它同时维护两个网络：Actor网络 Q(s, a; \theta) 负责输出策略，Critic网络 V(s; \phi) 负责估计状态价值。

初始化

初始化Actor网络 Q(s, a; \theta)，初始化Critic网络 V(s; \phi)。策略定义为Q值的softmax：p_{\theta}(a | s) = \text{softmax}[Q(s, a; \theta)]，这样Q值越大的行为被选中的概率越高。

主循环

对 \text{episode} = 1 \sim M：

首先在当前策略 p_{\theta}(a | s) 下采样 m 条轨迹。每条轨迹是智能体与环境交互产生的状态-行为-奖励序列。

初始化梯度累积量 \Delta\theta \leftarrow 0。

对每条轨迹 i = 1 \sim m，对轨迹中的每个时间步 t = 1 \sim T：

计算优势函数：

第一项是从时刻 t 开始的实际累积奖励（带衰减），第二项是Critic网络估计的预期价值。两者之差就是优势：实际收益相对于预期的超额部分。

累积Actor的梯度：

这里 \nabla_{\theta} \log[p_{\theta}(a_t^i | s_t^i)] 是策略对数概率对参数的梯度，乘以优势 A_t^i 后，表示按优势大小调整策略。

计算Critic的梯度：

Critic网络的目标是让估计的价值尽可能接近实际收益，因此优势的平方作为损失函数，最小化这个损失。

完成所有轨迹的处理后，更新两个网络的参数：

算法输出

训练完成后，输出Actor网络 Q(s, a; \theta) 和Critic网络 V(s; \phi)。Actor网络给出最优策略，Critic网络给出状态价值估计。

强化学习总结

当前发展状况

强化学习在一些特定任务上已经达到甚至超过人类水平，例如围棋、电子游戏等。但在相对复杂的现实任务上，如自动驾驶，与人类仍存在明显差距。

非算法因素的影响

机器与人的差距不能完全归咎于算法本身。传感器的精度和可靠性、机械执行机构的物理限制等硬件因素，同样是决定系统性能的关键。算法再好，如果传感器无法准确感知环境，机械臂无法精确执行动作，系统整体表现也会受限。

数据效率的差距

机器与人的另一个重要差距在于学习效率。人类拥有一些基本概念和先验知识，依据这些概念，只需要很少的训练就能学会新任务。例如人类只需看几个例子就能理解一个新概念。但当前的机器学习方法通常需要大规模数据才能学会，缺乏这种举一反三的能力。

尽管存在上述差距，机器也有其独特优势：计算速度快、永不疲倦、可以并行处理。只要有源源不断的数据供给，在特定的、定义明确的任务上，机器超越人类是完全可以期待的。未来的发展方向可能是结合人类的概念学习能力和机器的大规模计算能力，取长补短。

其他机器学习方法

特征提取与特征选择

问题背景

在机器学习和模式识别中，原始数据通常具有很高的维度，但并非所有维度都对分类或回归任务有用。降低维度可以减少计算量、避免过拟合、并可能提高模型性能。降维的方法主要分为两类：特征选择和特征提取。

特征选择是从原有的 N 个维度中直接挑选出 M 个最有用的维度（M < N），使得识别率最高。被选中的特征保持原有的物理意义。

特征提取则是构造新的特征。给定 N 维特征向量 \{x_{i1}, x_{i2}, \ldots, x_{iN}\}，构造 M 个函数 f_1, f_2, \ldots, f_M，每个函数都是原始 N 个维度的某种组合。这样就将维度从 N 维降到 M 维，同时希望这 M 个新特征能充分保留原始数据中的有用信息。

问题设定

假设有一组向量 \{x_1, x_2, \ldots, x_p\}，其中每个向量 x_i = \{x_{i1}, x_{i2}, \ldots, x_{iN}\} 是 N 维的。每个样本 x_i 属于类别 C_1 或 C_2。特征向量的 N 个维度可能存在冗余，目标是在降维的同时保留尽可能多的有用信息。

主成分分析

基本形式

主成分分析的目标是构造一个线性变换：

其中各变量的维度为：

这里 \bar{x} = E(x) = \frac{1}{p} \sum_{j=1}^{p} x_j 是所有样本的均值向量。减去均值是为了将数据中心化，使得变换后的数据均值为零。

从结构上看，PCA可以视为一个单层神经网络，有 M 个神经元，输入是 N 维向量，输出是 M 维向量。与监督学习不同的是，PCA中的样本 x 没有标签，这是一种无监督学习方法。这与自编码器（Auto-Encoder）的思想类似，都是在无标签数据上学习有意义的表示。

核心思想

PCA的核心思想是：寻找数据方差最大的方向，并将数据投影到该方向上。

以二维降到一维为例（N = 2，M = 1）：在二维平面上有一组数据点，我们要找一条直线，使得所有点投影到这条直线上后，投影点的分布尽可能分散（方差最大）。方差最大意味着投影后保留了最多的信息，因为如果投影点都挤在一起，就丢失了区分不同样本的能力。

数学推导

矩阵 A 可以分解为 M 个行向量：

每个 a_i 是一个 1 \times N 的行向量，代表一个投影方向。对于样本 x_i，变换后的结果为：

第一主成分的求解

首先求第一个投影方向 a_1，使得投影后的方差最大。第 i 个样本在方向 a_1 上的投影为 y_{i1} = a_1(x_i - \bar{x})。

投影值的均值为：

将 a_1 提出来：

由于

所以

代入上式得：

这说明投影后的数据均值为零，这正是中心化的效果。

投影的方差为：

将平方展开为向量乘积的形式：

由于 a_1 不依赖于求和指标 i，可以提到求和号外面：

定义协方差矩阵：

则方差可以简洁地写成：

从维度分析来看：a_1 是 1 \times N，\Sigma 是 N \times N，a_1^T 是 N \times 1，所以结果是一个标量，符合方差是标量的预期。

约束优化问题

如果不对 a_1 的大小加以限制，可以通过无限放大 a_1 来使方差无限大，这没有意义。因此需要添加约束条件

优化问题变为：

使用拉格朗日乘子法，构造拉格朗日函数：

对 a_1 求导并令其为零：

整理得：

这正是特征值问题的标准形式：a_1^T 是协方差矩阵 \Sigma 的特征向量，\lambda 是对应的特征值。

将此结果代入目标函数：

因此，要最大化方差，就要选择 \Sigma 的最大特征值 \lambda，对应的特征向量（归一化后）就是第一主成分方向 a_1。

多个主成分的求解

在二维例子中，只需要一个投影方向。但在高维情况下，需要求多个主成分方向。

对于第二主成分 a_2，优化问题变为：

第一个约束是归一化条件。第二个约束要求 a_2 与 a_1 正交，即 a_2 \perp a_1。

正交约束的意义是：第二主成分应该捕获与第一主成分不同的信息，而不是重复第一主成分已经捕获的变化方向。

可以证明，在正交约束下，a_2 是协方差矩阵 \Sigma 的第二大特征值对应的特征向量。以此类推，第 k 个主成分方向是 \Sigma 的第 k 大特征值对应的特征向量，所有主成分方向相互正交。

因此，PCA的实现归结为对协方差矩阵进行特征值分解，取前 M 个最大特征值对应的特征向量作为投影矩阵 A 的行向量。

第二主成分的严格推导

拉格朗日函数

对于第二主成分 a_2，需要在归一化约束和正交约束下最大化方差。使用拉格朗日乘子法，构造拉格朗日函数：

这里 \lambda 是归一化约束 a_2 a_2^T = 1 对应的乘子，\beta 是正交约束 a_2 a_1^T = 0 对应的乘子。

对 a_2 求导并令其为零：

即：

证明 β 等于零

接下来证明正交约束对应的乘子 \beta 实际上等于零。

对上式取转置（注意协方差矩阵 \Sigma 是对称矩阵，即 \Sigma = \Sigma^T）：

协方差矩阵的对称性可以直接验证：

在等式 a_2 \Sigma - \lambda a_2 - \beta a_1 = 0 两边右乘 a_1^T：

利用已知的正交关系和归一化条件：

由前面第一主成分的推导，\Sigma a_1^T = \lambda_1 a_1^T，其中 \lambda_1 是 \Sigma 的最大特征值。代入上式：

第二主成分的结论

由于 \beta = 0，原来的驻点条件简化为：

这说明 a_2^T 也是 \Sigma 的特征向量。结合归一化条件 a_2 a_2^T = 1 和正交条件 a_2 a_1^T = 0（a_2 不能与 a_1 相同），可以得出：

其中 a_2 是 \Sigma 的第二大特征值对应的特征向量，\lambda 是第二大特征值（第一大特征值已经被 a_1 占用）。

更高阶主成分

如果要继续求第三主成分 a_3，优化问题变为：

用类似的方法可以证明，a_3 是 \Sigma 的第三大特征值对应的特征向量。以此类推，第 k 个主成分方向是 \Sigma 的第 k 大特征值对应的特征向量。

PCA算法总结

PCA算法的完整流程如下：

第一步：计算协方差矩阵

• 其中 \bar{x} = \frac{1}{p}\sum_{j=1}^{p} x_j 是样本均值。

第二步：求 \Sigma 的特征值并从大到小排序

对应的特征向量为：

实际计算中，通常使用奇异值分解（SVD，Singular Value Decomposition）算法来求特征值和特征向量，因为SVD在数值稳定性上优于直接求解特征值问题。

第三步：归一化所有特征向量

对每个 a_i 进行归一化，使得 a_i a_i^T = 1。

第四步：构建投影矩阵

取前 M 个特征向量构成投影矩阵：

第五步：计算降维后的表示

对每个样本计算其在新坐标系下的坐标：

这样就完成了从 N 维到 M 维的降维工作。

特征选择

与特征提取的区别

特征提取（如PCA）是构造一个函数，将原始的 N 个特征全部用上，通过某种变换（如线性组合）得到 M 个新特征。新特征是原特征的组合，失去了原有的物理意义。

特征选择则是从 N 个原始特征中直接挑选 M 个，使得用这 M 个特征进行分类或回归时识别率最高。被选中的特征保持原有的物理意义，未被选中的特征可能是噪声或冗余信息。

组合爆炸问题

从 N 个特征中选 M 个的方法数为：

当 N 较大而 M 较小时，这个值会非常大。例如从100个特征中选10个，可能的选法超过 10^{13} 种，无法逐一尝试。

这是一个离散优化问题。与连续优化问题不同，离散问题无法求导数，因此无法使用梯度下降等连续优化方法。

解决方法

对于离散优化问题，主要有两类方法：

暴力破解法：枚举所有可能的特征组合，评估每种组合的识别率，选择最优的。但当组合数巨大时，这种方法不可行。

启发式方法：不保证找到全局最优，但能在可接受的时间内找到较好的解。

递增法

从空集开始，逐步添加特征。首先从 N 个特征中选出使识别率最高的那一个特征 X_1。然后固定 X_1，从剩余的 N-1 个特征中选出一个 X_2，使得 \{X_1, X_2\} 组合的识别率最高。继续这个过程，直到选出 M 个特征。

这种贪心策略每一步都做局部最优选择，但不能保证最终结果是全局最优。

递减法

从全集开始，逐步删除特征。首先用全部 N 个特征测试识别率。然后逐一尝试删除每个特征，看哪个特征删除后识别率下降最少（或反而提高），删除该特征。继续这个过程，直到剩下 M 个特征。

现代方法

在实际应用中，上述传统的特征选择方法已经不常用。原因是神经网络可以自动完成特征选择的功能：通过端到端的训练，网络会自动学习哪些输入特征对任务有用，对无用特征赋予接近零的权重。正则化技术（如L1正则化）还可以显式地促使网络产生稀疏的权重，从而实现隐式的特征选择。

AdaBoost算法

问题设定

AdaBoost是一种集成学习方法，通过组合多个弱分类器来构建一个强分类器。

给定数据集 T = \{(x_1, y_1), \ldots, (x_N, y_N)\}，这是一个二分类问题，标签 Y \in \{-1, +1\}。

核心思想

AdaBoost的思想是迭代地构建弱分类器，每个弱分类器只使用一个特征，单独看识别率不高，但总比随机猜测好（错误率低于50%）。

算法的关键在于重采样过程。在训练完第一个弱分类器后，对训练样本进行重新采样：给被分错的样本更高的采样权重，给分对的样本更低的权重。这样，被分错的样本可能被采集多次，而某些分对的样本可能一次都不被采集。

在新的采样数据集上训练第二个弱分类器，它会更关注前一个分类器犯错的样本。继续这个过程：

• 如果前两个分类器都分对了某个样本，给它最小的权重
• 如果一个分对一个分错，给它较大的权重
• 如果两个都分错了，给它最大的权重

第三个分类器将在包含更多"难分"样本的数据集上训练。

最终，将所有弱分类器的输出进行加权平均，得到最终的强分类器。

算法流程

第一步：初始化采样权重

初始时，所有样本被采样到的概率都是 \frac{1}{N}，即均匀分布。

第二步：迭代训练弱分类器

对 m = 1, 2, \ldots, M（M 是弱分类器的总数）：

使用当前的权重分布 D_m 采样 N 个训练样本。在这个采样得到的训练集上，训练一个弱分类器 G_m(x)，其输出为 \pm 1。

第三步：计算加权错误率

计算弱分类器 G_m 在当前权重分布下的加权错误率：

其中 I(\cdot) 是指示函数，当条件成立时取1，否则取0。这个错误率必须满足 e_m < \frac{1}{2}，否则这个弱分类器不比随机猜测好，应该舍弃。

根据错误率计算该弱分类器的权重：

这个公式的设计使得

• 当 e_m 越小（分类器越准确），\alpha_m 越大（权重越高）
• 当 e_m 接近 \frac{1}{2} 时，\alpha_m 接近0

由于 e_m < \frac{1}{2}，所以 \frac{1-e_m}{e_m} > 1，从而 \alpha_m > 0。

第四步：更新权重分布

更新下一轮迭代的样本权重分布：

每个样本的新权重为：

其中 Z_m 是归一化因子，确保权重之和为1：

分析权重更新规则：

• 当 G_m(x_i) = y_i（分类正确）时，y_i G_m(x_i) = 1，指数项为 e^{-\alpha_m} < 1，权重变小
• 当 G_m(x_i) \neq y_i（分类错误）时，y_i G_m(x_i) = -1，指数项为 e^{\alpha_m} > 1，权重变大

这正是AdaBoost的核心：让下一个分类器更关注当前分类器分错的样本。

第五步：循环与最终输出

回到第二步，重复 M 次。

最终的分类器由所有弱分类器加权组合而成：

f(x) 是加权求和的结果，G(x) 取其符号作为最终分类：

• 若 f(x) > 0，输出 +1
• 若 f(x) < 0，输出 -1

训练误差上界定理

定理陈述

随着弱分类器数量 M 增加，AdaBoost最终分类器 G(x) 在训练集上的错误率会越来越小。

需要注意的是，训练集错误率过小可能导致过拟合。但AdaBoost有一个有趣的特性：它不太容易出现过拟合，即使训练误差降到很低，在测试集上的表现通常也不会急剧下降。

定理证明

训练集错误率定义为：

其中指示函数：

首先建立一个上界：

其中 f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)。

验证这个不等式。注意 G(x_i) 和 y_i 都只能取 \pm 1：

情况一： 若 G(x_i) = y_i（分类正确），则

此时 y_i 和 f(x_i) 同号（因为 G(x_i) = \text{sign}(f(x_i))），所以

从而

不等式成立。

情况二： 若 G(x_i) \neq y_i（分类错误），则

此时 y_i 和 f(x_i) 异号，所以

从而

不等式成立。

误差上界的进一步化简

接下来证明：

推导过程如下。将 f(x_i) = \sum_{m=1}^{M} \alpha_m G_m(x_i) 代入：

利用指数函数的性质，将求和的指数转化为指数的乘积：

这里用到了 W_{1i} = \frac{1}{N}。

将乘积的第一项分离出来：

根据权重更新公式

可得

代入：

由于 Z_1 不依赖于求和指标 i，可以提出来：

重复这个过程，不断将各项的 Z_m 提取出来，最终得到：

这说明训练误差的上界等于所有归一化因子的乘积。由于每个 Z_m < 1（可以证明），随着 M 增加，乘积会越来越小，从而训练误差的上界不断下降。

归一化因子的计算

定理

归一化因子 Z_m 可以表示为：

其中 e_m 是第 m 个弱分类器的加权错误率：

证明

根据 Z_m 的定义：

将求和拆分为分类正确和分类错误两部分。

• 当 y_i = G_m(x_i) 时，y_i G_m(x_i) = 1
• 当 y_i \neq G_m(x_i) 时，y_i G_m(x_i) = -1

• 第一项中的权重之和等于分类正确样本的总权重，即 1 - e_m
• 第二项中的权重之和等于分类错误样本的总权重，即 e_m

将 \alpha_m = \frac{1}{2}\log\frac{1-e_m}{e_m} 代入。首先计算：

代入 Z_m 的表达式：

结论

当 e_m < \tfrac{1}{2} 时，有

因此

这意味着每增加一个弱分类器，训练误差的上界 \prod_{m=1}^{M} Z_m 就会乘以一个小于 1 的因子，从而不断减小。

统计学习方法

概率分类法

基本思想

概率分类法是一种在深度学习之前就存在、并将长久存在于机器学习领域的方法。它用概率的思维和方法来处理分类问题。

基本问题设定如下：假设有两个类别 W_1 和 W_2，给定某个样本 X，它要么属于 W_1，要么属于 W_2。目标是计算 P(W_1 | X) 和 P(W_2 | X)，即给定样本 X 后，它属于各个类别的概率。

由于样本必属于某一类，所以：

分类问题就变成了比较后验概率的大小：

贝叶斯公式

根据贝叶斯公式，后验概率可以表示为：

比较两个后验概率的大小时，由于分母 P(X) 相同，只需比较分子：

概率术语

在贝叶斯框架中，涉及三类概率：

P(W_1) 和 P(W_2) 称为先验概率，表示在观察到任何数据之前，各类别出现的概率。

P(X | W_1) 和 P(X | W_2) 称为条件概率（或似然），表示在给定类别的条件下，观察到样本 X 的概率。

P(W_1 | X) 和 P(W_2 | X) 称为后验概率，表示在观察到样本 X 之后，它属于各类别的概率。

与神经网络的关系

之前学习的卷积神经网络和人工神经网络在做分类问题时，最后经过Softmax层输出的值，本质上是在模拟后验概率 P(W_1 | X) 和 P(W_2 | X)。

但在使用神经网络时，必须重视先验概率的问题。当用神经网络做二分类问题时，需要保证训练集中 W_1 和 W_2 出现的频率与实际应用场景中的比率大致一致。换句话说，训练数据和测试数据的先验概率分布应该大致相同。这一点在实际中往往比较难保证，需要特别注意。

简化的判别标准

现在假设先验概率 P(W_1) 和 P(W_2) 已知（例如可以通过统计获得）。如果先验概率未知，通常假设所有类别的先验概率相等。

在先验概率相等的假设下，判别标准进一步简化为只比较条件概率：

概率密度估计问题

在上述假设都成立的情况下，核心问题变成了：如何估计条件概率 P(X | W)？具体来说，给定一组属于类别 W 的样本 \{x_i\}_{i=1 \sim N} \in W，如何根据这些样本估计 P(x | W)？

这个问题称为概率密度估计问题。接下来将从简单到复杂逐步研究这个问题的各种解决方法。

概率密度估计方法

朴素贝叶斯分类器

朴素贝叶斯分类器是最基本的统计分类方法，它建立在两个限制条件之上。

第一个条件是特征 X 必须是离散的。设 X = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_m \end{bmatrix}，每个维度都取离散值。

第二个条件是 X 的各个维度相互独立（不相关）。这个独立性假设是"朴素"（Naive）一词的来源，因为在实际问题中各维度往往是有相关性的，但为了简化计算而强行假设独立。

应用：垃圾邮件分类

问题设定如下：

每封邮件可以表示为单词的集合 d = \{w_1, w_2, \ldots, w_n\}。

如果要用概率分类法，需要估计条件概率 P(d | C_1) 和 P(d | C_2)。

独立性假设下的概率计算

条件概率可以写成：

其中 C 是 C_1 或 C_2。由于单词是离散的，第一个限制条件满足。第二个独立性条件在实际中并不成立（单词之间显然有关联），但我们仍然假设它成立以简化计算。

在独立性假设下，联合概率可以分解为各维度概率的乘积：

每个单词在给定类别下出现的概率通过统计得到：

分子是单词 w 在类别 C_j 的所有邮件中出现的总次数，分母是类别 C_j 的所有邮件中所有单词出现的总次数。例如，P(\text{"免费"} | C_2) 就是"免费"这个词在垃圾邮件中出现的次数除以垃圾邮件中所有单词的总次数。

先验概率通过统计训练样本中各类别的比例得到：

分类规则为：

零概率问题与平滑

如果某个单词在训练样本中从未出现过，但在测试样本中出现了，按原公式会导致 P(w_i | C) = 0。由于概率是连乘的，一个零会使整个乘积为零，这显然不合理。

解决方法是引入拉普拉斯平滑，修改概率估计公式：

分子加1，分母加上词表大小 |V|。这样即使某个单词从未出现过，其概率也不为零，而是 \frac{1}{|V| + \text{总词数}}，是一个很小的正数。

高斯概率密度估计

一维情况

当特征是连续值时，朴素贝叶斯的离散假设不再适用。一种常用的方法是假设数据服从高斯分布（正态分布）。

给定一组属于类别 C 的样本 \{x_i\}_{i=1 \sim N} \in C，在一维情况下，假设概率密度为高斯分布：

参数 \mu 和 \sigma^2 通过样本估计：

多维情况

当 x 是 d 维向量时，假设概率密度是多维高斯分布：

待估计的参数有两个：均值向量 \mu（d \times 1 维）和协方差矩阵 \Sigma（d \times d 维）。|\Sigma| 表示协方差矩阵的行列式。

极大似然估计

给定样本 \{x_i\}_{i=1 \sim N}，使用极大似然法（Maximum Likelihood）来估计参数。

基本假设是所有样本独立同分布（i.i.d., independent and identically distributed）。在这个假设下，所有样本同时出现的概率是各样本概率的乘积。取对数后乘积变成求和，得到对数似然函数：

目标是找到使这个似然函数最大的参数 \mu 和 \Sigma，即找到使观测数据出现概率最大的参数值。

将高斯分布的表达式代入并展开：

求解均值

对 \mu 求偏导并令其为零：

由于 \Sigma^{-1} 是可逆矩阵，所以：

解得：

这就是样本均值，与直觉一致。

求解协方差矩阵

对 \Sigma 求偏导比较复杂，改为对 \Sigma^{-1} 求偏导会更方便。令 \frac{\partial E}{\partial \Sigma^{-1}} = 0：

由于协方差矩阵是对称的（\Sigma = \Sigma^T），解得：

这就是样本协方差矩阵。

由于高斯分布的对数似然函数是关于参数的凹函数（负对数似然是凸函数），上面求得的驻点就是全局最优解，可以直接使用。

参数估计总结

最终得到的参数估计公式为：

参数估计的一般流程

高斯概率密度估计展示了参数估计的一般流程：

第一步，假设 X 的概率分布具有某种具体形式 P(X | C)（本例中是高斯分布），这个形式中包含一些待定参数（本例中是 \mu 和 \Sigma）。

第二步，使用极大似然法构造优化目标函数，即对数似然函数。

第三步，求解优化问题，获得待求参数的估计值。

这个流程适用于各种参数化的概率分布，只是具体的求解过程会因分布形式不同而有所变化。

混合高斯模型与EM算法

问题引入

在很多情况下，即使构造出了目标函数，也无法直接求出解析解。这时有几种选择：梯度下降法、神经网络等数值方法。接下来介绍一个典型的例子——混合高斯模型（Gaussian Mixture Model，GMM），以及专门用于求解这类问题的EM算法。

混合高斯模型的定义

单个高斯分布只能描述单峰的数据分布，但现实中的数据往往呈现多峰结构。混合高斯模型通过将多个高斯分布加权叠加来描述更复杂的分布。

假设 X 的概率分布形式为：

其中每个高斯分量为：

如果 X 是 d 维向量，则：

模型共有 K 个高斯分量，每个分量有自己的均值 \mu_k 和协方差矩阵 \Sigma_k。

权重 \pi_k 满足约束：

\pi_k 表示第 k 个高斯分量在混合模型中所占的比例。例如，如果有两个高斯分量，可能 \pi_1 = 0.8（右边的峰占80%）和 \pi_2 = 0.2（左边的峰占20%），两者之和为1。

极大似然目标函数

使用极大似然法构造优化目标函数。待估计的参数为 \{\pi_k, \mu_k, \Sigma_k\}_{k=1 \sim K}。

对数似然函数为：

展开后：

与单高斯模型不同，这里对数函数内部有求和，无法像之前那样简单地将对数分配进去。这导致：

这组方程极其复杂，无法得到解析解。而且这是一个非凸优化问题，无法保证找到全局极值，只能寻求局部极值。

求解方法

对于这类问题，有几种常用的求解方法：

梯度下降法：直接对目标函数求梯度，迭代更新参数。需要仔细调节学习率等超参数。

启发式方法：如遗传算法、模拟退火等，是求解非凸优化问题的通用算法，但通常计算量较大。

EM算法：专门针对含有隐变量的概率模型设计的算法，具有独特的优势：不需要调节任何超参数（如学习率），保证收敛；编程实现简单；理论基础优美。

EM算法

算法思想

EM算法的名称来自两个步骤：E-step（Expectation，期望步）和M-step（Maximization，最大化步）。

核心思想是引入隐变量。在混合高斯模型中，每个样本实际上来自某一个高斯分量，但我们不知道是哪一个。如果知道每个样本属于哪个高斯分量，问题就简化为多个独立的单高斯参数估计问题。EM算法通过迭代交替地估计隐变量（样本的归属）和更新参数来解决这个问题。

高斯混合模型的EM算法流程

第一步：初始化

随机初始化所有参数 \{\pi_k, \mu_k, \Sigma_k\}_{k=1 \sim K}。

此时可以计算样本属于各高斯分量的先验概率。例如对于两个高斯分量：

第二步：E-step（期望步）

在当前参数下，计算每个样本属于每个高斯分量的后验概率（称为"责任"或"软分配"）：

\gamma_{nk} 表示第 n 个样本属于第 k 个高斯分量的概率。分子是第 k 个高斯分量生成该样本的加权概率，分母是所有高斯分量生成该样本的加权概率之和，起到归一化的作用。

对于每个样本 n，有 \sum_{k=1}^{K} \gamma_{nk} = 1，即该样本必定属于某个高斯分量。

第三步：M-step（最大化步）

首先计算每个高斯分量的"有效样本数"：

这表示所有 N 个样本中，按概率加权后有多少"属于"第 k 个高斯分量。由于 \sum_{k=1}^{K} \gamma_{nk} = 1，所以 \sum_{k=1}^{K} N_k = N。

然后更新各参数，更新混合权重：

这是第 k 个高斯分量占所有样本的比例。

更新均值：

这是属于第 k 个高斯分量的样本的加权平均值。

更新协方差矩阵：

这是属于第 k 个高斯分量的样本的加权协方差矩阵。

第四步：迭代

回到第二步，用更新后的参数重新计算 \gamma_{nk}，然后再次执行M-step更新参数。不断循环，直到参数收敛（即连续两次迭代参数变化很小）。

算法特点

EM算法的更新公式与单高斯模型的参数估计公式非常相似，只是多了权重 \gamma_{nk}。当所有样本都硬分配给某一个高斯分量（\gamma_{nk} 为0或1）时，公式就退化为单高斯的情形。

关于EM算法的收敛性，可以证明每次迭代后对数似然函数单调不减，且在一定条件下收敛到局部极值。具体证明涉及Jensen不等式和KL散度等概念，此处略去。

以上是混合高斯模型EM算法的完整流程，它是一类更广泛的含隐变量概率模型求解方法的典型代表。

K-均值聚类算法

问题设定

K-均值聚类是另一个可以用EM算法框架理解的经典算法。

这是一个无监督学习问题：给定一组没有标签的数据，将它们划分为 K 个类别。

如果已知 K 个类别的中心点 \mu_1, \mu_2, \ldots, \mu_K，归类就很简单：计算每个样本到各中心的距离，离哪个中心近就属于哪一类。但问题是我们只有数据点，不知道类别中心在哪里。

K-均值算法步骤

第一步：初始化

随机选取 K 个点作为初始类别中心 \mu_1, \mu_2, \ldots, \mu_K。

第二步：E-step（分配步）

对每个样本 x_i，将其分配给最近的类别中心：

即离哪个中心最近就属于哪一类。

第三步：M-step（更新步）

首先统计每个类别包含的样本数：

这表示 N 个样本中有多少属于第 k 类。

然后更新每个类别的中心为该类所有样本的均值：

第四步：迭代

回到第二步，重新分配样本，再更新中心，不断循环直至收敛（即类别分配不再变化）。

收敛性证明

构造目标函数（总的类内平方误差）：

这个目标函数衡量了所有样本到其所属类别中心的距离平方和，越小说明聚类效果越好。

先考虑一个子问题：给定一组点 \{x_i\}_{i=1 \sim N}，求一个点 C 使得

最小。对 C 求导并令其为零，可得

即样本均值。

回到 K-均值算法：

• E-step 中，固定中心 \mu_k，将每个样本分配给最近的中心，这一步使目标函数 E 不增（可能减小或不变）
• M-step 中，固定分配 z_i，将每个中心更新为该类样本的均值，根据上面的结论，这一步也使 E 不增。

由于 E 有下界0（距离平方和非负），且每次迭代 E 单调不增，因此算法必定收敛。

EM算法的一般形式与收敛性证明

问题框架

将边缘概率 p(x_i | \theta) 写成对隐变量的求和：

这里的困难在于对数函数内部有求和，无法直接优化。

Jensen不等式与下界构造

设 Q_i(z_i) 是关于隐变量 z_i 的某个概率分布，满足 \sum_{z_i} Q_i(z_i) = 1。

将目标函数改写为：

由于对数函数是凹函数，根据Jensen不等式（对凹函数，期望的函数值大于等于函数值的期望）：

记右边为 M(\theta, Q)，它是 E(\theta) 的一个下界。

等号成立条件

Jensen不等式取等号的条件是：\frac{p(x_i, z_i | \theta)}{Q_i(z_i)} 对所有 z_i 都相等，即 Q_i(z_i) 与 p(x_i, z_i | \theta) 成正比。

由于 Q_i(z_i) 必须满足归一化条件，所以：

即 Q_i(z_i) 应该取为给定观测 x_i 和参数 \theta 下隐变量 z_i 的后验分布。

EM算法的一般形式

第一步：初始化

随机选取初始参数 \theta_0。

第二步：E-step

在当前参数 \theta_k 下，计算隐变量的后验分布：

这一步使得下界 M(\theta_k, Q) 紧贴目标函数 E(\theta_k)，即 M(\theta_k, Q) = E(\theta_k)。

第三步：M-step

固定 Q_i(z_i)，最大化下界找新参数：

由于 Q_i(z_i) 不依赖于 \theta，这等价于最大化 \sum_{i=1}^{N} \sum_{z_i} Q_i(z_i) \log p(x_i, z_i | \theta)，即完全数据对数似然的期望。

第四步：迭代

回到第二步，循环直至收敛。

收敛性证明

定义辅助函数：

证明过程如下：

完成 E-step 后，由于 Q_i(z_i) 取为后验分布，Jensen 不等式取等号，因此

完成 M-step 后，由于 \theta_{k+1} 是 M(\theta) 的最大化点，因此

进入下一轮 E-step 后，有

即新的下界重新紧贴新的目标函数值。

综合以上三点：

这说明每次迭代后，对数似然函数单调不减。

由于 p(x_i | \theta) \leq 1，所以 \log p(x_i | \theta) \leq 0，因此 E(\theta) \leq 0 有上界。

一个单调不减且有上界的序列必定收敛，因此EM算法保证收敛。

K-均值算法与EM框架的对应关系

问题设定

将K-均值算法纳入EM算法的一般框架中进行分析。

输入为 N 个样本 \{x_i\}_{i=1 \sim N}，待求参数为 \theta = \{\mu_1, \mu_2, \ldots, \mu_K\}，即 K 个类别的中心点。

定义隐变量 \{z_i\}_{i=1 \sim N}，其中 z_i \in \{1, 2, 3, \ldots, K\}，表示第 i 个样本属于哪个类别。

联合概率的定义

为了套用EM框架，需要定义观测变量和隐变量的联合概率 p(x, z | \theta)。在K-均值算法中，定义：

只有当 z 是离 x 最近的那个类别时，联合概率才非零；否则为零。非零时的概率形式是一个协方差矩阵为单位阵的高斯分布（忽略了归一化常数中与 \mu 无关的部分）。

E-step分析

根据EM算法的一般形式，计算隐变量的后验分布：

由于 p(x_i, z_i | \theta_k) 只有在 z_i 是离 x_i 最近的类别时才非零，分子分母中只有这一项有贡献，因此：

这正是K-均值算法中的分配步骤：将每个样本分配给最近的类别中心。与高斯混合模型的"软分配"不同，这里是"硬分配"——每个样本确定地属于某一个类别。

M-step分析

固定 Q_i(z_i)，最大化下界函数找新参数：

由于 Q_i(z_i) 只在 z_i = j（x_i 被分配到的类别）处取值为1，其他地方为0，对 z_i 的求和实际上只剩下一项。因此优化问题简化为：

这里 \sum_{z_i} 这个求和被 z_i = j 的条件替代了，因为只有被分配到第 j 类的样本才对 \mu_j 的更新有贡献。

定义目标函数（忽略与 \mu_j 无关的常数项）：

对 \mu_j 求偏导并令其为零：

解得：

分子是所有属于第 j 类的样本之和，分母是属于第 j 类的样本个数，因此 \mu_j 就是所有属于第 j 类样本的均值。这正是K-均值算法的更新步骤。

迭代

回到E-step，重新分配样本，循环直至收敛。

关于高斯混合模型EM算法的推导

高斯混合模型的EM算法推导遵循类似的框架。主要区别在于：高斯混合模型中 Q_i(z_i) = \gamma_{ik} 是一个0到1之间的连续值（软分配），而K-均值中 Q_i(z_i) 只取0或1（硬分配）。具体推导可以作为练习自行完成。

EM算法的注意事项

EM算法有两个需要特别注意的地方。

第一，EM算法求的是局部极值而非全局极值。一旦模型和数据确定，算法不需要调节任何超参数（如学习率），只需迭代即可保证收敛。

第二，所有求局部极值算法都有一个共同的缺点：无法保证找到的解一定比其他方法更优。初始值的选择不同，最终收敛到的局部极值可能完全不同，而且没有办法在不穷举的情况下证明哪个局部极值更好。在实践中，常用的策略是多次随机初始化，运行多次算法，选择似然值最高的结果。

隐含马尔可夫模型（HMM）

问题背景：连续行为的识别

语音识别是一个典型的连续行为识别问题。对于一段声音文件，我们不知道每个字或音素所占的时间长度。传统的分类方法假设每个样本是独立的，但语音信号是一个时间序列，前后帧之间有很强的依赖关系。

解决连续行为识别问题主要有两种方法：

这类问题不仅限于语音识别，也适用于任何连续动作的识别。关键困难在于：我们不知道某一状态下的行为会持续多长时间，因此必须引入时间参数来建模。虽然可以用K-均值等聚类方法来处理，但效率很低，不实用。

HMM的基本结构

HMM处理的输入是一个观测序列：

每个 O_t 是一个特征向量。在语音识别中，通常使用MFCC（Mel频率倒谱系数）作为特征。

每个观测 O_t 对应一个隐含状态 q_t。隐含的意思是我们能观察到 O_t，但不知道它对应的状态 q_t 是什么。状态序列 q_1, q_2, \ldots, q_T 需要通过模型来推断。

HMM的三个组成部分

一个HMM由三部分参数组成，记为 \lambda = \{A, B, \pi\}：

假设系统共有 P 个可能的状态 \{S_0, S_1, \ldots, S_{P-1}\}。

状态先验概率 \pi

\pi(S_i) 表示系统一开始处于状态 S_i 的概率。这是初始时刻的状态分布，满足：

状态转移矩阵 A

状态转移矩阵 A = \{a_{ij}\} 描述了状态之间的转移概率。a_{ij} 定义为：

即在 t 时刻处于状态 S_i 的条件下，t+1 时刻转移到状态 S_j 的概率。

这里采用了马尔可夫链假设，具体包含两层含义：

这是一阶（单步）马尔可夫链。也可以扩展为多阶马尔可夫链：

这样下一时刻的状态就与之前所有时刻的状态都有关系。但为了简化计算，通常采用一阶马尔可夫假设。

对于每个状态 S_i，从它出发转移到所有状态的概率之和为1：

观测概率 B

观测概率 B = \{b_j(o)\} 描述了在给定状态下观测到特定输出的概率。b_j(o) 表示当系统处于状态 S_j 时，输出观测向量 o 的概率分布。

传统方法中，b_j(o) 通常用高斯混合模型来建模。每个状态对应一个GMM，参数包括混合权重、各高斯分量的均值和协方差矩阵。

HMM的核心问题

在HMM框架下，我们知道所有的观测序列 O_1, O_2, \ldots, O_T，但不知道每个观测 O_t 对应的状态 q_t。状态序列是"隐含"在观测序列中的，需要通过模型参数来推断。这就是"隐含马尔可夫模型"名称的由来。

HMM需要解决的三个基本问题是：评估问题（给定模型，计算观测序列的概率）、解码问题（给定模型和观测序列，找出最可能的状态序列）、学习问题（给定观测序列，估计模型参数）。

隐马尔可夫模型的三个基本问题

问题一：识别问题（评估问题）

给定一个观测序列 O = O_1, O_2, \ldots, O_T 和一个HMM模型 \lambda = \{A, B, \pi\}，计算该模型生成这个观测序列的概率 P(O | \lambda)。

这个问题的应用场景是：假设我们有多个HMM模型，每个模型对应一个类别（如数字0-9），对于一个待识别的观测序列，分别计算各模型生成它的概率，概率最大的模型对应的类别就是识别结果。

直接计算的困难

按照概率的定义，需要对所有可能的状态序列求和：

各项的含义如下：

• 每个状态 q_t 可以取 S_0 到 S_{P-1} 中的任意一个，需要把所有可能性都考虑进来
• a_{q_1 q_2} 是从状态 q_1 转移到状态 q_2 的概率
• b_{q_1}(O_1) 是在状态 q_1 下观测到 O_1 的概率。

这个求和的计算量是灾难性的。如果有 P = 5 个状态，序列长度 T = 50，则需要计算 5^{50} 项，这是不可接受的。

前向算法

通过定义前向变量，可以将计算复杂度从指数级降到多项式级。

定义前向变量：

它表示在模型 \lambda 下，观测到前 t 个输出 O_1, O_2, \ldots, O_t，且 t 时刻处于状态 S_i 的联合概率。

初始化（t = 1）：

初始状态为 S_i 的概率是 \pi(S_i)，在该状态下观测到 O_1 的概率是 b_i(O_1)，两者相乘即可。

递推公式（t \to t+1）：

推导过程：考虑前向变量

要在时刻 t+1 到达状态 S_j，可以从任意状态 S_i 转移过来。 对所有可能的前一状态 S_i 求和，每一项为：

• 在时刻 t 处于状态 S_i 的概率：\alpha_t(i)
• 乘以从 S_i 转移到 S_j 的概率：a_{ij}
• 再乘以在状态 S_j 下观测到 O_{t+1} 的概率：b_j(O_{t+1})

终止：

最终概率等于所有可能终止状态的前向变量之和。因为

对所有终止状态求和就消去了对 q_T 的依赖，得到 P(O | \lambda)。

识别问题的应用

以数字0-9识别为例：首先训练10个HMM模型 \lambda_0, \lambda_1, \ldots, \lambda_9，每个模型对应一个数字。对于待识别的观测序列 O，计算后验概率：

由于 P(O) 对所有模型相同，如果假设先验概率 P(\lambda_i) 也相同，则只需比较 P(O|\lambda_i)，取最大者对应的类别作为识别结果。

问题二：解码问题

给定HMM模型 \lambda = \{\pi, A, B\} 和观测序列 O = O_1, O_2, \ldots, O_T，找出最可能的状态序列 Q = q_1, q_2, \ldots, q_T，使得联合概率最大：

初始状态 q_1 的先验概率 \pi(S_{q_1})，在状态 q_1 下观测到 O_1 的概率 b_{q_1}(O_1)，从 q_1 转移到 q_2 的概率 a_{q_1 q_2}，以此类推。我们要找使这个乘积最大的状态序列。

这个问题本质上是给观测序列打标签——为每个观测确定其对应的隐含状态。

维特比算法（Viterbi Algorithm）

维特比算法是一种动态规划算法，通过保存到达每个状态的最优路径来高效求解。

定义：

\delta_t(i) 表示：在 t 时刻到达状态 S_i，且观测到 O_1, \ldots, O_t 的所有路径中，概率最大的那条路径的概率值。

递推公式：

\psi_{t+1}(j) 记录的是到达状态 S_j 的最优路径是从哪个前驱状态转移过来的。这个信息用于最后回溯得到完整的状态序列。

终止与回溯：

首先找到最终时刻概率最大的状态作为 q_T，然后利用 \psi 数组从后向前回溯，依次确定 q_{T-1}, q_{T-2}, \ldots, q_1。

问题三：训练问题

给定大量观测序列 O = O_1, O_2, \ldots, O_T，估计模型参数 \lambda = \{\pi, A, B\}，使得 P(O|\lambda) 最大。这是一个参数估计问题，由于存在隐变量（状态序列），使用EM算法来求解，在HMM中称为Baum-Welch算法。

前向-后向变量

除了前向变量 \alpha_t(i)，还需要定义后向变量：

它表示：在 t 时刻处于状态 S_i 的条件下，从 t+1 时刻到 T 时刻观测到 O_{t+1}, \ldots, O_T 的概率。

初始化（t = T）：

在最后时刻之后没有更多观测，条件概率为1。

递推公式（从后向前）：

从状态 S_i 出发，可以转移到任意状态 S_j（概率 a_{ij}），在 S_j 观测到 O_{t+1}（概率 b_j(O_{t+1})），然后从 S_j 出发产生后续观测（概率 \beta_{t+1}(j)）。

EM算法更新公式

第一步：随机初始化

随机初始化参数 \lambda = \{\pi, A, B\}。

第二步：E-step

计算状态转移的后验概率：

分子是 t 时刻在状态 S_i、t+1 时刻在状态 S_j、且产生完整观测序列的联合概率。分母是对所有可能的状态对求和，起归一化作用。

计算单个状态的后验概率：

第三步：M-step

更新初始状态分布：

即初始状态为 S_i 的概率等于在给定观测下第一个状态为 S_i 的后验概率。

更新状态转移概率：

分子是从状态 S_i 转移到状态 S_j 的期望次数，分母是处于状态 S_i 的期望次数，两者之比就是转移概率的估计。

更新观测概率 B：在得到新的 \pi^{\text{new}} 和 A^{\text{new}} 后，利用问题二的维特比算法可以得到观测序列对应的状态序列，从而可以更新每个状态对应的观测概率分布 b_j(o)。如果 b_j(o) 用高斯混合模型建模，则可以用GMM的EM算法来更新。

第四步：迭代

回到第二步，重复E-step和M-step，直至参数收敛。

循环神经网络（Recurrent Neural Network, RNN）

RNN与其他网络的区别

循环神经网络（RNN）与之前学过的各种网络有本质区别。它与RCN（Region-based Convolutional Network，用于图像分割）不同，RNN专门用于处理时间序列信号，在功能上与隐马尔可夫模型类似，但采用神经网络的方式来建模时间依赖关系。

RNN的基本思想

RNN的核心思想是：t 时刻的状态不仅与 t 时刻的输入有关，还与 t-1 时刻的状态有关。

其中 h_t 是 t 时刻的隐状态，x_t 是 t 时刻的输入，f_W 是由参数 W 确定的函数。

这个公式与HMM中的马尔可夫假设有相似之处：当前状态只依赖于前一时刻的状态和当前输入。但关键区别在于RNN中的函数 f_W 与时刻 t 无关，即所有时刻共享同一组参数。这种参数共享大大减少了模型的参数量，同时使模型能够处理任意长度的序列。

一层RNN的具体形式

当 f_W 采用单层神经网络时，具体形式为：

第一个方程计算隐状态的更新，第二个方程从隐状态计算输出。

这个公式可以写成更紧凑的形式。将 h_{t-1} 和 x_t 拼接成一个向量，将 W_{hh} 和 W_{xh} 拼接成一个矩阵：

其中 W = \begin{bmatrix} W_{hh} & W_{xh} \end{bmatrix}，\tanh 函数定义为：

\tanh 将任意实数映射到 (-1, 1) 区间，起到非线性激活的作用。

RNN与GMM-HMM的关系

如果 f_W 采用三层神经网络，且状态数有限，可以证明RNN能够模拟GMM-HMM。这是因为：三层神经网络具有足够的表达能力来近似任意连续函数，可以模拟HMM中的状态转移概率和高斯混合模型的观测概率。

输入输出的多种配置

RNN可以处理多种输入输出关系：

多对多：输入序列和输出序列长度相同，每个时刻都有输入和输出。典型应用如序列标注、机器翻译等。

多对一：输入是一个序列，输出是一个单一值。典型应用如情感分类——输入一段文本，输出正面/负面的判断。

一对多：输入是一个单一值，输出是一个序列。典型应用如图像描述生成——输入一张图片，输出描述图片的句子。

权值共享与梯度反向传播

由于RNN在所有时刻共享同一组权重 W，在反向传播时需要特殊处理。当同一个权重 W 在多个时刻被使用时，其梯度是各时刻贡献的梯度之和。具体做法是：计算每个时刻 W 对损失函数的偏导数，然后将它们加在一起作为 W 的总梯度。

Vanilla RNN的训练问题

梯度爆炸与梯度消失

Vanilla RNN（基础版RNN）在训练时存在严重的梯度问题。考虑一个长度为 T 的序列，损失函数对初始隐状态 h_0 的梯度需要通过链式法则从 h_T 一路传播回来。

在这个过程中，权重矩阵 W 的某个部分会被连续乘以 T 次。如果 W 的特征值大于1，梯度会指数级增长，导致梯度爆炸，如果特征值小于1，梯度会指数级衰减，导致梯度消失。

梯度爆炸会使参数更新过大，训练不稳定，梯度消失会使早期时刻的信息无法有效传递到后期，模型难以学习长距离依赖关系。

LSTM：长短期记忆网络

设计动机

LSTM（Long Short-Term Memory）是RNN的一种变体，专门用于解决Vanilla RNN的梯度问题。其核心思想是：增加RNN单元的复杂度，引入门控机制来控制信息的流动，使得模型能够选择性地记住或遗忘信息。

LSTM的数学形式

Vanilla RNN的更新公式很简单：

LSTM将其复杂化，引入了多个门控单元：

各符号的含义如下：

i 是输入门（input gate），控制有多少新信息被写入记忆单元。f 是遗忘门（forget gate），控制有多少旧信息被保留。o 是输出门（output gate），控制有多少记忆单元的信息被输出到隐状态。g 是候选记忆，表示当前时刻要写入的新信息。

c_t 是记忆单元（cell state），它是LSTM的核心。\sigma 是sigmoid函数，输出范围 (0, 1)，适合作为门控信号。\odot 表示逐元素乘法。

LSTM如何解决梯度问题

记忆单元 c_t 的更新公式 c_t = f \odot c_{t-1} + i \odot g 是关键。这是一个加法形式，而不是像Vanilla RNN那样的乘法形式。在反向传播时，加法操作使得梯度可以直接流过，不会像乘法那样导致梯度的指数级变化。

遗忘门 f 接近1时，梯度可以几乎无损地传播很远，遗忘门接近0时，可以有选择地截断某些梯度流。这种门控机制使得LSTM能够根据数据自适应地决定保留或遗忘信息，从而有效地学习长距离依赖关系。