Course Notes: Probabilistic and Unsupervised Learning (COMP0086)

October 25, 2026 Course Notes WIP

信息论

1. 定理内容 (The Source Coding Theorem)

  • 前提条件:假设符号或词服从概率分布 \(P\),并从中独立同分布(i.i.d.)地采样得到一个序列 \(X_1, \dots, X_n\)。

  • 定理表述:对于任意给定的微小正数 \(\varepsilon > 0\),只要序列长度 \(n\) 足够大,就必定存在一个无损编码器,使得平均每个符号所需的编码长度满足以下不等式: \(\mathbf{H}(P) \le \mathbb{E}\left[\frac{1}{n} \cdot \text{length}(\text{encoding}(X_1, \dots, X_n))\right] < \mathbf{H}(P) + \varepsilon\)

  • \(\mathbf{H}(P)\):分布 \(P\) 的香农熵(Shannon Entropy),代表信源的不确定性或平均信息量。
  • \(\text{length}(\text{encoding}(X_1, \dots, X_n))\):对长度为 \(n\) 的序列进行无损编码后占用的比特总数。
  • \(\mathbb{E}\left[\frac{1}{n} \cdot \dots \right]\):每个符号平均所需的期望编码比特数(即平均编码速率)。

  • 平均比特数:
    • 也就是说,对于长为 \(n\) 的序列 \(X_1, \dots, X_n\),平均可以使用大约 \(n \mathbf{H}(P)\) 个比特来实现无损编码。
  • 极限与下界 (Lower Bound):
    • 香农熵 \(\mathbf{H}(P)\) 是无损压缩的理论极限下界。没有任何编码算法能够达到比 \(\mathbf{H}(P)\) 更低(更优)的平均比特率。
  • 定长编码的失真极限:
    • 如果采用定长编码(Fixed-length codes),当编码速率小于熵 \(\mathbf{H}(P)\) 时,随着序列长度 \(n \to \infty\),信息发生丢失/解码错误的概率将趋近于 1。

Word-by-word Compression

  • 词频分布规律:英语单词按出现频率排序后,能够很好地通过齐普夫分布(Zipf Distribution)进行近似。
  • 低熵特性:文本高度集中于少数极其常见的词汇上,这使得单词维度的分布具有相对较低的信息熵。
  • 相比字符分割,将文本切分为单词进行编码能够实现高得多的压缩率。
  • 常见的实用无损压缩算法(如 Lempel-Ziv / LZ 算法)通常并不严格按单词分割,而是将文本切分为重复出现的子字符串(Substrings)来进行高效压缩。

相对熵与 KL 散度

如果数据的真实生成分布是 \(P\),但我们误以为/使用了另一个模型分布 \(Q\) 来进行编码,会产生怎样的后果?我们该如何量化分布 \(P\) 与分布 \(Q\) 之间的差异?

1. Heuristic Motivation

  1. 理想假设下的期望信息增益:
    • 如果样本直接来自分布 \(Q\),使用对应编码 \(J_Q(X) = -\log Q(X)\) 的期望信息量(即熵)为 \(H[Q] = \mathbb{E}_Q[J_Q(X)]\)。
  2. 实际采样下的期望信息/编码长度:
    • 如果样本实际来自分布 \(P\),但我们却用分布 \(Q\) 的信息量/编码标准 \(J_Q(X)\) 去度量它,则实际的期望编码长度为: \(\mathbb{E}_P[J_Q(X)] = -\sum_{x \in \mathcal{X}} P(x) \log Q(x)\)
  3. 归一化与差异度量:
    • 一个合理的分布差异度量指标在 \(Q = P\) 时应当为 \(0\)。
    • 当 \(Q = P\) 时,\(\mathbb{E}_P[J_Q(X)] = H(P)\)(通常不为 0)。因此需要通过减去真实分布的熵 \(H(P)\) 来进行基线归一化。
    • 物理含义:减去 \(H(P)\) 后的差值,正好代表了因使用了错误分布 \(Q\) 代替真实分布 \(P\) 而付出的额外编码开销(多消耗的比特数)。

      2. KL 散度的定义 (Definition)

      分布 \(P\) 与分布 \(Q\) 的 Kullback-Leibler 散度(又称相对熵 / Relative Entropy) 定义为: \(KL(P \vert{}\vert{} Q) := \mathbb{E}_P[J_Q(X)] - H(P) = \sum_{x \in \mathcal{X}} P(x) \log \frac{P(x)}{Q(x)}\)

      3. 核心数学性质 (Properties)

    • 正定性 (Positive Definiteness): \(KL(P \vert{}\vert{} Q) \ge 0 \quad \text{且} \quad KL(P \vert{}\vert{} Q) = 0 \iff P = Q\) (注:该性质可通过 Jensen 不等式严格证明,见第 117 页)
    • 凸性 (Convexity): \(KL(P \vert{}\vert{} Q)\) 关于参数分布 \(P\) 和 \(Q\) 均为凸函数(Convex Function)。

4. 物理意义

  • 理想情况(基准):如果数据的真实分布是 \(P(X)\),根据香农信源编码定理,最优编码方案为每个符号 \(x\) 分配的长度为 \(J_P(x) = -\log P(x)\)。平均编码长度即为信息熵 \(H(P)\)。
  • 如果我们误以为数据分布是 \(Q(X)\)(比如我们在模型中对数据的估计),并基于 \(Q\) 设计了编码器(每个符号分配长度 \(J_Q(x) = -\log Q(x)\))。
  • 物理意义:当用基于 \(Q\) 设计的编码去压缩真实来自分布 \(P\) 的数据时,平均每个符号多消耗/浪费的比特数(编码惩罚),恰好就是 \(KL(P\vert{}\vert{}Q)\)。\(\text{KL 散度 } KL(P\vert{}\vert{}Q) = \text{交叉熵 } H(P, Q) - \text{信息熵 } H(P)\)
    • 交叉熵 \(H(P,Q)\):用模型 \(Q\) 编码真实数据 \(P\) 的总期望成本。
    • 信息熵 \(H(P)\):理论上不可避免的最小固有成本。
    • KL 散度:消除固有随机性后,仅由模型预测失真(\(Q \neq P\))所带来的纯粹损失。
  • 极大似然估计(MLE)的本质:在机器学习中,我们寻找参数 \(\theta\) 使模型 \(Q_\theta\) 拟合训练数据 \(P_{\text{data}}\)。最大化对数似然,等价于最小化 \(KL(P_{\text{data}} \vert{}\vert{} Q_\theta)\)。

KL 散度的非对称性 (Asymmetry of the KL Divergence)

既然 KL 散度用于度量两个概率分布的差异,那它在数学上能否被称为距离(Metric)?为什么交换 \(P\) 和 \(Q\) 的位置会导致完全不同的结果?

1. 非距离特质 (Mathematical Non-Metric Properties)

在离散与连续概率分布的场合下,KL 散度均具备以下性质:

  • 非对称性 (Non-symmetric):一般情况下,\(KL(p\vert{}\vert{}q) \neq KL(q\vert{}\vert{}p)\)。
  • 不满足三角不等式 (Triangle Inequality):对于三个分布 \(p, q, r\),通常不满足 \(KL(p\vert{}\vert{}r) \le KL(p\vert{}\vert{}q) + KL(q\vert{}\vert{}r)\)。
  • 核心结论:KL 散度不是概率分布空间上的严格数学距离(Not a metric)。
  • 几何特质:尽管不是严格距离,但 KL 散度拥有丰富的几何结构(信息几何 Information Geometry),例如满足类似于毕达哥拉斯定理(勾股定理)的几何性质。

    2. 非对称性的机理

    为什么 \(KL(p\vert{}\vert{}q)\) 与 \(KL(q\vert{}\vert{}p)\) 不相等?这归因于对数运算与概率质量分布的相互作用:

    1. 极端惩罚机制:
    • 若分布 \(p\) 在某个区域赋予了概率质量,而分布 \(q\) 在该区域几乎趋近于 0,则比值 \(p/q\) 会变得非常庞大。 2. 非线性无法抵消:
    • 由于 \(p\) 与 \(q\) 均经过归一化,必然会在其他区域存在 \(p/q\) 较小的情形。
    • 但由于对数函数 \(\log(p/q)\) 的非线性凸性特征,两端的差值无法相互抵消。

      几何示例(高斯分布错配):

  • \(KL(p_{\text{窄}} \vert{}\vert{} q_{\text{宽}})\):真实分布 \(p\) 很集中(如低方差高斯分布),而估计分布 \(q\) 较宽(高方差)。在 \(p\) 有值的区域 \(q\) 均有值,因此比值 \(p/q\) 较小,产生的 KL 散度较小(表现为包容性 Mode-covering)。
  • \(KL(p_{\text{宽}} \vert{}\vert{} q_{\text{窄}})\):真实分布 \(p\) 较宽,而估计分布 \(q\) 很窄。在 \(p\) 有值的边缘区域 \(q\) 几乎为 0,导致产生极大的 \(\log(p/q)\) 惩罚,产生非常大的 KL 散度(表现为排他性 Mode-seeking)。

Mutual Information

有了 KL 散度这个强力工具后,我们能用它来解决一个机器学习和概率论中的核心问题——两个变量 \(X\) 和 \(Y\) 到底有没有关系?它们之间共享了多少信息?

1. 物理意义

核心:“已知 \(X\),能帮我减少多少关于 \(Y\) 的不确定性?”

  • 假设 \(Y\) 是“今天会不会下雨”,\(X\) 是“天空中的云量”。如果我们观察到了 \(X\)(云层密布),关于 \(Y\)(下雨)的不确定性就会大幅降低。这说明 \(X\) 和 \(Y\) 共享了大量的信息。
  • 如果 \(X\) 是“今天食堂吃什么”,它对于预测 \(Y\)(下雨)毫无帮助。它们共享的信息就是 0。

    公式构造:

    1. 如果两个变量 \(X\) 和 \(Y\) 毫无关系(完全独立),根据概率论,它们的联合概率分布应该刚好等于各自边缘分布的乘积: \(P_{\text{独立}}(x,y) = P(x) P(y)\)
    2. 但在现实中,它们往往是有联系的,真实的联合分布是 \(P(x,y)\)。
    3. 关键 Insight:想知道 \(X\) 和 \(Y\) 的关联有多紧密,只要看真实的联合分布 \(P(x,y)\) 距离完全独立的假设 \(P(x)P(y)\) 有多远
    4. 直接套用KL 散度测这两个分布的距离

      2. 数学定义

      互信息 \(I[X; Y]\) 定义为真实联合分布与独立分布之间的 KL 散度: \(I[X; Y] := KL\Big( P(x,y) \;\big\Vert{}\; P(x)P(y) \Big) = \sum_{x,y} P(x,y) \log \frac{P(x,y)}{P(x)P(y)}\)

      消除困惑量:

      在信息论中,它等价于以下极具物理意义的形式: \(I[X; Y] = H(Y) - H(Y\vert{}X) = H(X) - H(X\vert{}Y)\)

  • \(H(Y)\):在不知道 \(X\) 时,对 \(Y\) 的原始困惑度(信息熵)。
  • \(H(Y\vert{}X)\):在知道 \(X\) 之后,对 \(Y\) 还剩下的残留困惑度(条件熵)。
  • \(I[X; Y]\)(互信息):已知 \(X\) 帮你消除掉的困惑量。
  • 传统相关系数:只能测量线性关系。如果 \(Y = X^2\),且 \(X\) 在 \([-1, 1]\) 上均匀分布,计算出来的相关系数是 \(0\)!线性相关系数会“误以为”它们毫无关系。
  • 互信息 \(I[X; Y]\):能够捕捉任何复杂的非线性关系!只要 \(X\) 的变化对 \(Y\) 的分布产生影响,\(I[X; Y]\) 就会大于 0。
  • 独立性等价条件:\(I[X; Y] = 0 \iff X \text{ 与 } Y \text{ 完全独立 } (X \perp\!\!\!\perp Y)\)

连续型随机变量:微分熵、KL 散度与互信息

在前述讨论中,随机变量均处于离散空间,信息量计算采用对概率质量函数 \(P(x)\) 的求和符号 \(\sum\)。 当样本空间 \(\mathcal{X}\) 为不可数集(如 \(\mathbb{R}^d\))时,概率质量函数被概率密度函数pdf \(p(x)\) 替代,求和运算相应转化为积分运算 \(\int\)。

1. 微分熵 (Differential Entropy)

(1) 数学定义

对于连续随机变量 \(X\) 及其概率密度函数 \(p(x)\),其微分熵定义为:

\(H[X] := -\int_{\mathcal{X}} p(x) \log p(x) \, dx\)

(2) 核心性质与物理意义差异

  • 可能为负值:离散熵必定是非负的(\(H \ge 0\)),但概率密度函数 \(p(x)\) 的取值可以大于 \(1\)(只需全局积分为 \(1\))。当 \(p(x) > 1\) 时,\(\log p(x) > 0\),因此微分熵 \(H[X]\) 可以为负数。
  • 相对不确定性:离散熵测量的是信息的“绝对不确定性”;而微分熵测量的是相对于连续空间无穷小划分的“相对不确定性”。

    2. 连续情形下的 KL 散度与互信息

    在连续空间中,KL 散度与互信息的定义保持形式对称:

  • 连续 KL 散度:\(KL(p \,\vert{}\vert{}\, q) := \int_{\mathcal{X}} p(x) \log \frac{p(x)}{q(x)} \, dx\)
  • 连续互信息:
    \(I[X, Y] := \int_{\mathcal{X}} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \, dx dy\)

3. 核心:为何 KL 散度与互信息不受连续化影响?

  • 基本性质保持一致:与微分熵不同,连续情形下的 KL 散度与互信息完全保留了离散情形下的所有核心性质:
    1. \(KL(p \,\vert{}\vert{}\, q) \ge 0\),当且仅当 \(p(x) = q(x)\) 几乎处处成立时等号成立。
    2. \(I[X, Y] \ge 0\),当且仅当 \(X\) 与 \(Y\) 相互独立时等号成立。
  • 物理机制(量纲抵消):
    • 微分熵依赖于具体坐标系的度量划分。
    • KL 散度与互信息的对数项内部均为两个概率密度的比值(\(\frac{p(x)}{q(x)}\) 与 \(\frac{p(x,y)}{p(x)p(y)}\))。坐标变换时的雅可比行列式(Jacobian)在分子分母中被相消,使得这两个量具备坐标变换不变性(Coordinate Invariance)。

信息论与经典统计学

信息论不仅用于数据压缩与编码,它与传统统计学及机器学习模型之间存在深层的映射与统一性

(1) 指数族分布是“最大熵模型” (Exponential Families as Maximum Entropy Models)

  • 定理表述:若固定足够统计量 \(T(X)\) 的期望值为 \(t\),在所有满足该约束条件的概率分布中,使信息熵达到最大值的分布必为指数族分布(Exponential Family)。
  • 物理 Insight:熵最大化体现了最大熵原理(Maximum Entropy Principle),即“在已知有限约束下,不引入任何主观偏见或多余假设,保持最大的随机性与无知”。例如:在仅约束均值与方差时,熵最大的分布即为高斯分布;在仅约束事件平均发生率时,最大熵分布为指数分布。

    (2) 极大似然估计等价于最小化 KL 散度 (MLE Minimizes KL Divergence)

  • 定理表述:参数估计中的极大似然估计(Maximum Likelihood Estimation, MLE),在数学上完全等价于最小化经验分布 \(P_{\text{emp}}\)(训练数据分布)与模型分布 \(Q_\theta\) 之间的 KL 散度。
  • 数学等效: \(\arg\max_\theta \sum_{i=1}^n \log Q_\theta(x_i) \iff \arg\min_\theta KL(P_{\text{emp}} \;\vert{}\vert{}\; Q_\theta)\)
  • 物理 Insight:模型拟合的过程,本质上就是寻找一组参数 \(\theta\),使模型对真实数据的概率估计错配所带来的额外编码惩罚(比特浪费)达到最小。

    (3) 经典统计量是信息论指标的低阶展开 (Taylor Approximations)

  • 一阶近似:方差(Variance)与协方差(Covariance)可视为信息熵(Entropy)和互信息(Mutual Information)的一阶泰勒近似。
  • 二阶近似:卡方检验统计量(\(\chi^2\)-statistic)可视为 KL 散度的二阶泰勒展开近似。
  • Insight:传统统计学指标通常是信息论通用量在局部平滑条件下的代数近似。

    (4) 独立成分分析 (Independent Component Analysis, ICA)

  • 范式替换:将传统统计算法中的线性关联指标替换为信息论指标,可构建表达能力更强的无监督学习算法。
  • 算法对比:
    • 主成分分析 (PCA):以最小化协方差为目标,仅能消除变量间的线性相关性。
    • 独立成分分析 (ICA):以最小化互信息为目标(逼近成分间的相互独立性),能够分离出存在高阶非线性关联的隐变量。

凸性

凸集

在无监督学习与概率图模型中,无论是求解最大似然估计、推导变分下界(EM 算法中的 Free Energy),还是求解带约束的优化问题,都需要对参数空间或函数进行优化。凸性(Convexity) 是确保这些优化问题能够收敛到全局最优解的核心几何性质。

1. 几何定义

  • 一个集合如果“没有任何内部凹陷或穿孔”,它就是凸集。
  • 直线判别法:在集合 \(A\) 内部任意挑选两个点 \(x\) 和 \(y\),只要连接这两点的整条线段完全包含在集合 \(A\) 的内部,则称 \(A\) 为凸集。
  • 反例(非凸集):形如“月牙形”、“齿轮形”或中间有孔洞的区域。如果在凹陷两侧各取一点,连接两点的线段会穿过集合外部(即“出界”),因而非凸。

    2. 定量数学表达

    集合 \(A \subset \mathbb{R}^d\) 为凸集,当且仅当对于任意 \(x, y \in A\) 及任意 \(\lambda \in [0, 1]\),均满足: \(\lambda x + (1-\lambda)y \in A\)

    代数与几何

  • 凸组合(Convex Combination):\(\lambda x + (1-\lambda)y\) 代表点 \(x\) 与点 \(y\) 的加权平均。
  • 当 \(\lambda = 1\) 时,坐标为 \(x\);当 \(\lambda = 0\) 时,坐标为 \(y\)。
  • 当 \(\lambda\) 在 \([0, 1]\) 之间连续变化时,该代数式连续扫过了连接 \(x\) 与 \(y\) 的线段上的每一个点。该数学条件本质上就是“线段不出界”的精准代数描述。

    3. 在机器学习中

    1. 可行域(Feasible Set)的良好性质:
    • 在带约束的优化问题(如支持向量机 SVM 或 EM 算法中的约束条件)中,如果可行域(即变量允许取值的集合)是一个凸集,能够防止优化过程陷入断裂的局部孤岛中。 2. Jensen 不等式的几何基石:
    • 后续推导 EM 算法变分下界时所依赖的 Jensen 不等式,前提条件正是要求概率分布的支撑集或函数的定义域具备凸性。

凸函数

有了良好的可行域约束后,我们需要进一步探讨定义在该区域上的目标函数具备怎样的性质。本页将凸性概念从“点集”延伸至“函数”,代数与几何上严谨地刻画了“局部最优即全局最优”的函数特征。

1. 几何

(1) “碗状”几何特征

  • 直观上,凸函数的图像展现为一个向上开口的凹槽(碗状)。
  • 割线高于曲线:在函数曲线上任意挑选两点并连接成一条直线段(割线),整个割线段永远悬在函数曲线的上方。

    (2) 与“凸集”的深层等价性

  • 上方图(Epigraph):函数的凸性有一个优雅的几何映射——如果一个函数是凸函数,那么位于该函数图像上方所有点构成的区域,在几何空间中必然是一个凸集。这在代数与几何之间搭建了直接桥梁。

    (3) 物理 Insight(重力滑落模型)

  • 想象一个小球在曲面上依靠重力下滑:
    • 非凸曲面:存在许多“伪低谷”(局部极小值),小球很容易卡在半山腰无法继续下滚。
    • 凸曲面:由于曲面整体向上弯曲,不存在任何伪低谷。小球只要顺着梯度方向下滑,必定能顺畅滑落到最底部的全局最低点。

      2. 数学定义

      (1) 一阶代数定义 (Definition)

      函数 \(f\) 为凸函数,当且仅当对其定义域内的任意两点 \(x, y\) 以及任意权重参数 \(\lambda \in [0, 1]\),均满足: \(\lambda f(x) + (1-\lambda)f(y) \ge f(\lambda x + (1-\lambda)y)\)

  • 代数含义拆解:
    • 左项 \(\lambda f(x) + (1-\lambda)f(y)\):代表 \(x\) 与 \(y\) 两点在函数图像上对应高度的加权平均,即割线上对应点的高度。
    • 右项 \(f(\lambda x + (1-\lambda)y)\):代表两点加权平均坐标处的真实函数高度。
    • 不等式几何含义:割线高度始终不低于曲线高度。

      (2) 二阶微积分判别法 (Second-order Criterion)

      对于二次可微的函数 \(f\):

  • 一维标量情形:若其二阶导数处处非负,即 \(f''(x) \ge 0\),则 \(f\) 为凸函数。
    • Insight:二阶导数为正意味着一阶导数(斜率)是单调递增的,函数曲线始终向上弯曲。
  • 多维向量情形:若其海森矩阵(Hessian Matrix \(H_f(x)\))在整个定义域内处处为半正定矩阵(Positive Semidefinite),则 \(f\) 为凸函数。

凸对偶性 (Convex Duality)

前两页分别建立了凸集(无凹陷的可行域)与凸函数(碗状、无局部伪极小值)的定义。当我们需要衡量一个点 \(x\) 与一个凸集 \(A\) 之间的“最短距离”时,如何从“对偶(Duality)”的视角,利用超平面(Hyperplane)来等价表示这个几何距离?

1. 几何直觉

(1) 原问题:直接测量距离的难点

  • 在高维空间中,直接计算点 \(x\) 到复杂凸集 \(A\) 的距离 \(d(x, A)\),需要寻找集合内部使距离最小的点 \(y \in A\)(属于带约束优化问题)。

    (2) 对偶视角:分离超平面 (Separating Hyperplane)

  • 分离超平面的存在性:由于集合 \(A\) 为凸集且点 \(x\) 位于 \(A\) 外部,空间中必然存在至少一个超平面 \(H\)(二维空间中为直线,三维空间中为平面),将点 \(x\) 与凸集 \(A\) 完全隔离在两侧。
  • 距离的下界与极限:
    • 对于任意一个将点 \(x\) 与集合 \(A\) 完全分隔开的超平面 \(H\),点 \(x\) 到该平面 \(H\) 的垂直距离 \(d(x, H)\),必然小于或等于点 \(x\) 到凸集 \(A\) 的真实最短距离 \(d(x, A)\)。
    • 若调整并推移该超平面 \(H\),使其紧紧“贴”住凸集 \(A\) 的边界,点 \(x\) 到该平面的距离将达到最大值,且该最大值恰好等于点 \(x\) 到凸集 \(A\) 的最短距离。
  • 核心 Insight:“点到凸集的最近距离”(在凸集点集中寻找最近点),等价于“在该点与凸集的所有分离超平面中,寻找使点到平面距离最大的最远距离(上确界 \(\sup\))”。这种将“原空间点集搜索”转换为“对偶空间平面搜索”的思想,即为凸对偶性。

    2. 数学公式与代数拆解

    点 \(x\) 到凸集 \(A\) 的最短距离可以通过对偶表述等价计算: \(d(x, A) = \sup_{H \text{ 为分离超平面}} d(x, H)\)

  • 原问题(Primal Problem): \(d(x, A) = \inf_{y \in A} \Vert{}x - y\Vert{}\) 即在凸集 \(A\) 内部寻找一点 \(y\),使两点间的欧氏距离达到下确界(最小)。
  • 对偶问题(Dual Problem): \(\sup_{H \text{ 分离 } x \text{ 与 } A} d(x, H)\) 在所有满足“分隔点 \(x\) 与凸集 \(A\)”条件的超平面 \(H\) 的集合中,寻找使点到平面距离 \(d(x, H)\) 最大的超平面 \(H^*\)。

    3. 在机器学习中

    1. 强对偶性(Strong Duality)的几何基石:
    • 凸集的几何可分离性保证了原问题与对偶问题的最优解完全一致(对偶间隙 Dual Gap 为 0)。 2. 支持向量机(SVM)的几何原型:
    • 支持向量机中寻找最大间隔分类超平面的过程,本质上正是利用超平面分隔两类数据的凸包(Convex Hulls),并最大化边界到超平面的距离。

琴生不等式

如果输入的不是单纯的两个点 \(x\) 和 \(y\),而是一个遵从某种概率分布的随机变量 \(X\),那么“先求期望再取函数值 \(f(\mathbb{E}[X])\)”与“先取函数值再求期望 \(\mathbb{E}[f(X)]\)”之间有什么定量关系?

1. 物理意义

(1) 通俗直觉:先平均 vs 后平均

  • 凸函数(碗状向上 \(f'' \ge 0\)):
    • \(f(\mathbb{E}[X])\)(先平均再评价):把所有可能的输入值先加权平均得到一个中间点,再计算该点处的函数高度。
    • \(\mathbb{E}[f(X)]\)(先评价再平均):把各个输入值对应的函数高度全部算出来,再做加权平均(相当于在弦/割线上取点)。
    • 直觉结论:由于凸函数的割线永远悬在曲线上方,“先取函数值再平均”永远大于或等于“先平均再取函数值”。

      (2) 凹函数(如对数函数 \(f(x) = \log x\))的对偶情况

  • 凹函数像一把向上拱起的伞(\(f'' \le 0\))。此时不等式方向反转:\(\mathbb{E}[\log(X)] \le \log(\mathbb{E}[X])\)。
  • 如果给对数加上负号,\(f(x) = -\log x\) 就变成了凸函数:\(-\log(\mathbb{E}[X]) \le \mathbb{E}[-\log(X)]\)

    2. 数学表述与代数拆解

    对于定义在凸集上的概率分布 \(P\) 和凸函数 \(f:\mathbb{R}^d \to \mathbb{R}\),琴生不等式表达为: \(f(\mathbb{E}_P[X]) \le \mathbb{E}_P[f(X)]\)

    (1) 离散概率形式拆解

    若离散随机变量取值为 \(x_i\),概率权重为 \(p_i \ge 0\) 且 \(\sum_i p_i = 1\): \(f\left( \sum_i p_i x_i \right) \le \sum_i p_i f(x_i)\)

  • 等号成立条件:当且仅当函数 \(f\) 为线性函数(直线/平面),或者随机变量 \(X\) 在概率支撑集上几乎处处为常数(即没有任何随机不确定性)时,等号才成立。

    (2) 对数函数示例 (\(f(x) = -\log x\))

    对于点集 \(x_i > 0\) 及概率权重 \(p_i\): \(-\log \left( \sum_i p_i x_i \right) \le -\sum_i p_i \log(x_i)\)

    3. 在机器学习中

    1. 解决“对数里面有求和/积分”的推导
    • 在潜在变量模型(如 GMM、VAE)中,边缘对数似然为 \(\log P(X) = \log \sum_Z P(X, Z)\)。对数外置在求和符号外(即 \(\log(\mathbb{E}[\cdot])\))使得积分求导极其困难。
    • 借助琴生不等式,可以将对数移入求和内部(转化为 \(\mathbb{E}[\log(\cdot)]\)),从而构造出易于优化的变分下界 / 自由能(Free Energy) 2. 证明信息论基本定理
    • 琴生不等式可以直接用来推导 \(KL(P\vert{}\vert{}Q) \ge 0\)、互信息非负性 \(I(X;Y) \ge 0\) 以及信息不减原理。

KL 散度非负性的严格证明

运用琴生不等式,严谨地证明 \(KL(p\vert{}\vert{}q) \ge 0\)(即无论模型估计得多糟糕,浪费的编码比特数绝不可能为负数),并导出等号成立的唯一条件。

1. Mathematical Derivation

第一步:改写 KL 散度形式

根据定义,KL 散度的代数式可变形为: \(KL(p\vert{}\vert{}q) = \mathbb{E}_p \left[ \log \frac{p(X)}{q(X)} \right] = \mathbb{E}_p \left[ -\log \frac{q(X)}{p(X)} \right]\)

第二步:引入凸函数并应用琴生不等式

  • 考虑函数 \(f(t) = -\log t\)。由于对数函数 \(\log t\) 是严格凹函数,负对数函数 \(-\log t\) 是严格凸函数。
  • 设随机变量 \(Y = \frac{q(X)}{p(X)}\),根据琴生不等式 \(\mathbb{E}_p[f(Y)] \ge f(\mathbb{E}_p[Y])\),我们有: \(KL(p\vert{}\vert{}q) = \mathbb{E}_p \left[ -\log \frac{q(X)}{p(X)} \right] \ge -\log \left( \mathbb{E}_p \left[ \frac{q(X)}{p(X)} \right] \right)\)

    第三步:计算内部期望值

    计算随机变量 \(Y = \frac{q(X)}{p(X)}\) 在分布 \(p\) 下的期望值: \(\mathbb{E}_p \left[ \frac{q(X)}{p(X)} \right] = \sum_x p(x) \cdot \frac{q(x)}{p(x)} = \sum_x q(x) = 1\) (注:此处利用了概率分布 \(q(x)\) 的全局归一化公理 \(\sum_x q(x) = 1\))。

    第四步:导出非负结论

    将期望值 \(1\) 代回不等式右端: \(KL(p\vert{}\vert{}q) \ge -\log(1) = 0\)

    2. 取等条件 (Equality Condition)

  • 等号成立的充分必要条件:琴生不等式取等号当且仅当随机变量 \(Y = \frac{q(X)}{p(X)}\) 在概率支撑集上几乎处处为常数。
  • 由于该常数的期望值为 \(1\),因此必须满足

\(\frac{q(x)}{p(x)} = 1 \iff p(x) = q(x) \quad (\text{对所有 } x \text{ 成立})\)

  • 结论:\(KL(p\vert{}\vert{}q) = 0\) 当且仅当分布 \(p\) 与分布 \(q\) 完全相同。
  • 真实分布 \(p\) 对应的编码是理论上的“最优编码”。基于任何其他分布 \(q\) 设计的编码系统,平均编码长度必然大于或等于最优编码长度,多出的浪费量(即 \(KL(p\vert{}\vert{}q)\))绝不可能为负。

Expectation Maximisation

EM算法

从这里开始正式引入 EM 算法(Expectation-Maximization,期望最大化) 的理论。本页首先比较两类模型:

  1. 常规模型:仅处理可观测数据,例如指数族分布模型。
  2. 潜变量模型(Latent Variable Models):包含无法直接观测的隐藏变量 核心是梳理这两类模型的对数似然函数在数学结构上的差异,以及这种差异如何增加优化的难度。

    1. 两种模型的对数似然对比

    (1) 指数族模型 (Exponential Family Models)

    • 概率密度:\(p(x\vert{}\theta) = f(x) e^{\theta^T T(x)} / Z(\theta)\)
    • 对数似然:\(l(\theta) = \theta^T \sum_{i=1}^n T(x_i) - n \log Z(\theta) + \text{常数}\)
    • 结构特点:
      • 取对数后消除了指数项,关于参数 \(\theta\) 是凹函数(Concave Function)。
      • 凹函数的局部极值即为全局极值(Global Maximum),可以通过偏导数设为 0 求解解析解(Closed-form solution),或者进行简单高效的数值优化。

        (2) 隐变量模型 (Latent Variable Models)

    • 边缘概率密度(通过消去未观测的隐变量 \(z\)):\(p(x\vert{}\theta_x, \theta_z) = \int dz \, p(x\vert{}z, \theta_x) p(z\vert{}\theta_z)\)
    • 对数似然: \(l(\theta_x, \theta_z) = \sum_{i=1}^n \log \left( \int dz \, p(x_i\vert{}z, \theta_x) p(z\vert{}\theta_z) \right)\)
    • 结构特点:
      • 呈现“对数里面包含积分/求和(\(\log \int\) 或 \(\log \sum\))”的复杂结构。
      • 不再是凹函数,参数空间存在多个局部极值(Local Maxima)。
      • 通常不存在解析解,直接使用梯度下降等数值优化方法极其困难。
  • 如果隐变量 \(z\) 已知,则退化为普通指数族模型,估计参数 \(\theta\) 非常简单;
  • 如果参数 \(\theta\) 已知,则根据观测数据 \(x\) 计算隐变量的后验分布 \(p(z\vert{}x, \theta)\) 也非常简单;
  • 但现实中 \(z\) 与 \(\theta\) 均未知,二者紧密耦合,无法一步到位直接求解。
  • 对数在求和号外(\(\sum \log P\))时,乘积转化为求和,各参数可分离求导;而对数在求和号内(\(\log \sum P\))时,非线性对数函数阻断了各项的独立拆解与偏导化简。

为解决“对数号内部求和/积分”这一数学屏障,我们需要引入琴生不等式构造变分下界(Variational Lower Bound / 自由能 Free Energy),通过交替优化隐变量分布与模型参数,这便是 EM 算法 的核心机制

高斯混合模型的对数似然

1. 高斯混合模型(GMM)的定式化

  • 观测数据 (Data): \(\mathcal{D} = \{x_1, \dots, x_n\}\)
  • 隐过程 (Latent Process): 离散隐变量 \(s_i \sim \text{Disc}[\pi]\),表示数据点 \(x_i\) 来自第几个高斯分量(类别)。
  • 分量分布 (Component Distributions): 属于第 \(k\) 个分量时的条件概率分布:\(x_i \mid (s_i = k) \sim \mathcal{P}_k[\theta_k] = \mathcal{N}(\mu_k, \Sigma_k)\)
  • 边缘分布 (Marginal Distribution): 消去隐变量 \(s_i\) 后,数据点 \(x_i\) 的边缘概率密度: \(P(x_i) = \sum_{k=1}^K \pi_k P_k(x_i; \theta_k)\)

    2. GMM 的对数似然函数

    对全体观测数据 \(\mathcal{D}\) 的对数似然 \(l(\{\mu_k\}, \{\Sigma_k\}, \pi)\) 为: \(l(\{\mu_k\}, \{\Sigma_k\}, \pi) = \sum_{i=1}^n \log \sum_{k=1}^K \frac{\pi_k}{\sqrt{\vert{}2\pi \Sigma_k\vert{}}} e^{-\frac{1}{2}(x_i - \mu_k)^T \Sigma_k^{-1} (x_i - \mu_k)}\)

The Joint-Data Likelihood and EM

隐变量模型(如 GMM)之所以难以直接求解,是因为我们无法观测隐变量 \(z\),必须对 \(z\) 求和/积分。这产生了 \(\log \sum\) 的结构,导致参数高度耦合且无法消去对数。假设隐变量 \(z\) 能够被直接观测到(称为“完全数据” Joint/Complete Data),或者我们已经知道了参数 \(\theta\),求解过程会发生什么变化?

1. 物理意义

(1) 完全数据(Complete Data)的数学红利

  • 完全数据 指的是由“观测数据 \(x\) + 隐变量 \(z\)”构成的整体 \((x_i, z_i)\)。
  • 一旦隐变量 \(z_i\) 已知,对数符号 \(\log\) 就能直接作用于联合概率 \(P(x_i, z_i \vert{} \theta)\) 上。如果分量分布属于指数族分布,对数与指数相抵消,复杂的乘积结构立即转化为线性可加结构,优化变得极其简单。

    (2) 交替优化机制Bootstrapping

  • 方向一(已知 \(z\) 求 \(\theta\)):若隐变量 \(z\) 的取值或分布已知,最大化联合对数似然求解参数 \(\theta\) 是简单且存在解析解的。
  • 方向二(已知 \(\theta\) 求 \(z\)):若模型参数 \(\theta\) 已知,利用贝叶斯公式推导隐变量的事后分布 \(P(z\vert{}x, \theta)\)(即推断 Inference)同样非常简单。
  • 自洽解(Self-consistent Answer):既然两者互为前提,我们可以从一个随机初始化的参数 \(\theta^{(0)}\) 开始,交替执行这两个简单步骤,直直到二者收敛到一个自洽的稳定点。这正是 EM 算法(期望最大化算法) 的核心直觉。

    2. 数学形式

    若隐变量 \(z_i\) 可观测,联合数据的对数似然函数可展开为: \(l(\theta_x, \theta_z) = \sum_{i=1}^n \phi(\theta_x, z_i)^T T_x(x_i) + \theta_z^T \sum_{i=1}^n T_z(z_i) - \sum_{i=1}^n \log Z_x(\phi(\theta_x, z_i)) - n \log Z_z(\theta_z)\)

  • 结构优势:
    1. 参数 \(\theta_x\)(观测模型参数)与 \(\theta_z\)(隐变量先验参数)在代数上完全解耦(Decoupled),可以分别独立求解。
    2. 针对 \(\theta_x\) 和 \(\theta_z\) 的求导不包含任何嵌套的求和项,退化为标准的指数族参数估计问题。

标准定义、操作流程及其在机器学习与统计学中的核心特性

1. EM 算法的操作流程 (Algorithm Procedure)

EM 算法旨在求解含隐变量模型的极大似然估计或局域极值。算法从任意指定的参数初始值 \(\theta^{(0)}\) 开始,交替迭代执行以下两个步骤直至收敛:

  • E 步(Expectation / 期望步):inference
    • 基于当前步骤的参数估计值,计算已知观测数据下隐变量的后验分布,对“缺失”的隐变量信息进行填补或求期望。
  • M 步(Maximization / 最大化步):learning
    • 假定隐变量的分布已由 E 步确定(即隐变量不再隐藏),最大化完全数据的对数似然期望值,更新模型参数 \(\theta\)。

      算法特性

      (1) 分解思想

  • 拆解难题:EM 算法将直接优化难以处理的非凸对数似然函数(包含 \(\log \sum\) 结构)的过程,分解为一轮轮容易求解的子任务序列。

    (2) 无需学习率

  • 相比于传统的梯度下降法(Gradient Descent)需要小心翼翼地调优学习率(Step size/Learning rate)以防步子过大发散或过小收敛极慢,EM 算法不需要设置任何学习率。其 M 步通常能直接计算出当前变分下界的最优闭式解。

    (3) 跨学科术语对齐 (Terminology Alignment)

  • 机器学习(ML)与统计学(Statistics)对这两步的命名视角有所不同:
    • E 步:机器学习中称为 推断(Inference);统计学中称为 插补 / 填补(Imputation)。
    • M 步:机器学习中称为 学习(Learning);统计学中称为 估计(Estimation)。

      (4) 算法的适用性

  • 对于混合高斯模型(GMM)或因子分析(FA)等简单模型,梯度下降法也能工作,但 EM 算法通常收敛更快、更稳定。
  • 对于更复杂的离散/连续混合概率图模型(如 HMM、SSM),EM 算法是构建原则性近似推断(如变分推导 Variational Inference)的理论骨架。

EM 算法的变分下界与“自由能”,or ELBO,Evidence Lower Bound,证据下界

1. 变分下界的数学推导

(1) 起点:难以直接优化的边缘对数似然

设观测数据为 \(\mathcal{D}=\{x_i\}\),隐变量为 \(\mathcal{Z}=\{z_i\}\),模型参数为 \(\theta = \{\theta_x, \theta_z\}\)。消去隐变量后的边缘对数似然为: \(l(\theta) = \log P(\mathcal{D}\vert{}\theta) = \log \int d\mathcal{Z} \, P(\mathcal{Z}, \mathcal{D}\vert{}\theta)\)

(2) 引入变分分布 \(q(\mathcal{Z})\)

为了破除对数号内部的积分求和屏障,在积分号内部分子分母同时乘以一个关于隐变量的任意合法概率分布 \(q(\mathcal{Z})\)(满足 \(\int d\mathcal{Z} \, q(\mathcal{Z}) = 1\) 且 \(q(\mathcal{Z}) \ge 0\)): \(l(\theta) = \log \int d\mathcal{Z} \, q(\mathcal{Z}) \frac{P(\mathcal{Z}, \mathcal{D}\vert{}\theta)}{q(\mathcal{Z})}\)

(3) 运用琴生不等式(Jensen’s Inequality)导出下界

由于对数函数 \(\log(\cdot)\) 是凹函数,根据琴生不等式 \(\log(\mathbb{E}_q[Y]) \ge \mathbb{E}_q[\log(Y)]\),将对数符号移入积分号内部: \(l(\theta) \ge \int d\mathcal{Z} \, q(\mathcal{Z}) \log \frac{P(\mathcal{Z}, \mathcal{D}\vert{}\theta)}{q(\mathcal{Z})} \stackrel{\text{def}}{=} \mathcal{F}(q, \theta)\)

2. 自由能 \(\mathcal{F}(q,\theta)\) 的代数拆解

将分式对数拆开展开: \(\mathcal{F}(q, \theta) = \int d\mathcal{Z} \, q(\mathcal{Z}) \log P(\mathcal{Z}, \mathcal{D}\vert{}\theta) - \int d\mathcal{Z} \, q(\mathcal{Z}) \log q(\mathcal{Z})\) 注意到第二项 \(-\int d\mathcal{Z} \, q(\mathcal{Z}) \log q(\mathcal{Z})\) 正是分布 \(q(\mathcal{Z})\) 的香农信息熵 \(H(q)\)!因此自由能可简洁表达为: \(\mathcal{F}(q, \theta) = \big\langle \log P(\mathcal{Z}, \mathcal{D}\vert{}\theta) \big\rangle_{q(\mathcal{Z})} + H(q)\)

核心

  1. 第一项 \(\big\langle \log P(\mathcal{Z}, \mathcal{D}\vert{}\theta) \big\rangle_{q(\mathcal{Z})}\)(完全数据对数似然的期望):
    • 鼓励分布 \(q(\mathcal{Z})\) 将概率质量集中在能够高概率解释观测数据与隐变量组合的区域(即提升模型的“拟合度”)。
  2. 第二项 \(H(q)\)(隐变量分布的信息熵):
    • 鼓励分布 \(q(\mathcal{Z})\) 保持分散与不确定性,防止过早坍缩或过拟合到单一孤立点上(即保持“最大熵原则”)。
  3. 统计物理学
    • 在热力学中,自由能定义为“能量 - 温度 \(\times\) 熵”。此处的变分自由能借用了相同的数学表达,优化过程本质上是在最大化模型拟合能量与最大化隐变量不确定性熵之间寻找平衡。

      3. 总结

    • 无论选择怎样合法的分布 \(q(\mathcal{Z})\),变分自由能 \(\mathcal{F}(q, \theta)\) 始终是真实边缘对数似然 \(l(\theta)\) 的一个下界。
    • 边缘对数似然 \(l(\theta)\) 的优化难题,由此成功转化为对变分下界 \(\mathcal{F}(q, \theta)\) 关于分布 \(q\) 和参数 \(\theta\) 进行交替上升优化的过程。

E 步与 M 步

借助自由能 \(\mathcal{F}(q,\theta)\),将 EM 算法的两步(E 步与 M 步)重新定义为对同一个统一目标函数 \(\mathcal{F}\) 进行的坐标上升法(Coordinate Ascent)。

1. 从自由能视角看 E 步与 M 步

(1) E 步(Expectation Step / 期望步)—— 关于分布 \(q\) 最大化

  • 操作:保持模型参数 \(\theta^{(t-1)}\) 固定不变,调整隐变量分布 \(q(\mathcal{Z})\),以最大化自由能 \(\mathcal{F}\):\(q^{(t)}(\mathcal{Z}) := \arg\max_{q(\mathcal{Z})} \mathcal{F}\big(q(\mathcal{Z}), \, \theta^{(t-1)}\big)\)
  • E 步本质上是在当前固定参数下,将变分下界 \(\mathcal{F}\) 向上“抬高”,使其在当前参数点尽可能贴紧真实的边缘对数似然 \(l(\theta^{(t-1)})\)。

    (2) M 步(Maximization Step / 最大化步)—— 关于参数 \(\theta\) 最大化

  • 操作:保持 E 步求解得到的隐变量分布 \(q^{(t)}(\mathcal{Z})\) 固定不变,调整模型参数 \(\theta\),以最大化自由能 \(\mathcal{F}\):\(\theta^{(t)} := \arg\max_{\theta} \mathcal{F}\big(q^{(t)}(\mathcal{Z}), \, \theta\big) = \arg\max_{\theta} \big\langle \log P(\mathcal{Z}, \mathcal{D}\vert{}\theta) \big\rangle_{q^{(t)}(\mathcal{Z})}\)
  • 代数简化
    • 在自由能展开式 \(\mathcal{F}(q, \theta) = \big\langle \log P(\mathcal{Z}, \mathcal{D}\vert{}\theta) \big\rangle_{q^{(t)}} + H(q^{(t)})\) 中,第二项香农熵 \(H(q^{(t)})\) 仅与分布 \(q^{(t)}\) 有关,不显式依赖于参数 \(\theta\)。
    • 因此对 \(\theta\) 求最大化时,熵项 \(H(q^{(t)})\) 作为常数可以直接省去,M 步的优化目标简化为完全数据对数似然在 \(q^{(t)}\) 下的期望值。

      2. Coordinate Ascent

  • 原本看似独立的两个步骤(“推断隐变量”与“更新参数”),在变分框架下被统一为对单一标量目标函数 \(\mathcal{F}(q, \theta)\) 的最大化过程。
  • 目标函数 \(\mathcal{F}(q, \theta)\) 定义在“分布空间 \(\times\) 参数空间”构成的联合空间中。
  • E 步:固定 \(\theta\),沿 \(q\) 方向(分布空间)搜寻最高点;
  • M 步:固定 \(q\),沿 \(\theta\) 方向(参数空间)搜寻最高点。
  • 这种交替轮换方向上升的优化机制,在数学上就是标准的坐标上升法(Coordinate Ascent)

E 步的代数实质

在所有可能的概率分布空间中,究竟哪一个分布 \(q(\mathcal{Z})\) 能使自由能 \(\mathcal{F}\) 达到最大值?通过对自由能进行代数变形,推导出 E 步最优解的精确数学形式。

1. 自由能的代数变形与 KL 散度

将自由能 \(\mathcal{F}(q, \theta)\) 定义式中的联合概率 \(P(\mathcal{Z}, \mathcal{D}\vert{}\theta)\) 依据贝叶斯乘法公式拆解为后验概率与边缘似然的乘积 \(P(\mathcal{Z}\vert{}\mathcal{D}, \theta) P(\mathcal{D}\vert{}\theta)\): \(\begin{aligned} \mathcal{F}(q, \theta) &= \int q(\mathcal{Z}) \log \frac{P(\mathcal{Z}, \mathcal{D}\vert{}\theta)}{q(\mathcal{Z})} \, d\mathcal{Z} \\ &= \int q(\mathcal{Z}) \log \frac{P(\mathcal{Z}\vert{}\mathcal{D}, \theta) P(\mathcal{D}\vert{}\theta)}{q(\mathcal{Z})} \, d\mathcal{Z} \\ &= \int q(\mathcal{Z}) \log P(\mathcal{D}\vert{}\theta) \, d\mathcal{Z} + \int q(\mathcal{Z}) \log \frac{P(\mathcal{Z}\vert{}\mathcal{D}, \theta)}{q(\mathcal{Z})} \, d\mathcal{Z} \\ &= \log P(\mathcal{D}\vert{}\theta) \int q(\mathcal{Z}) \, d\mathcal{Z} - \int q(\mathcal{Z}) \log \frac{q(\mathcal{Z})}{P(\mathcal{Z}\vert{}\mathcal{D}, \theta)} \, d\mathcal{Z} \\ &= l(\theta) - KL\Big(q(\mathcal{Z}) \;\Big\Vert{}\; P(\mathcal{Z}\vert{}\mathcal{D}, \theta)\Big) \end{aligned}\)

2. 核心数学与物理 Insight

(1) 下界的代数表达拆解

经过展开后,变分自由能被清晰地拆解为两项之差:

  1. \(l(\theta) = \log P(\mathcal{D}\vert{}\theta)\):真实的边缘对数似然(与分布 \(q\) 无关的常数项)。
  2. \(KL\Big(q(\mathcal{Z}) \;\Big\Vert{}\; P(\mathcal{Z}\vert{}\mathcal{D}, \theta)\Big)\):变分分布 \(q(\mathcal{Z})\) 与真实隐变量条件后验分布 \(P(\mathcal{Z}\vert{}\mathcal{D}, \theta)\) 之间的 KL 散度。

    (2) E 步求解的最佳分布

    • 由于对数似然 \(l(\theta)\) 关于 \(q\) 是常数,最大化自由能 \(\mathcal{F}(q, \theta)\) 等价于最小化变分分布与真实后验分布之间的 KL 散度。
    • 根据 KL 散度的正定性(\(KL \ge 0\)),当且仅当变分分布与真实后验分布完全相同时,KL 散度降为最小取值 \(0\): \(q^{(t)}(\mathcal{Z}) = P(\mathcal{Z} \mid \mathcal{D}, \, \theta^{(t-1)})\)

      (3) 关键推论:E 步后的下界紧致性(Tightness)

    • 当 E 步将 \(q^{(t)}(\mathcal{Z})\) 设为真实后验分布 \(P(\mathcal{Z}\vert{}\mathcal{D}, \theta^{(t-1)})\) 后,KL 散度惩罚项归零。
    • 此时变分自由能完全触及边缘对数似然曲线: \(\mathcal{F}(q^{(t)}, \theta^{(t-1)}) = l(\theta^{(t-1)})\)
    • 物理含义:这揭示了 E 步的本质逻辑——在固定当前参数的前提下,通过精准估计隐变量的后验概率分布(即推断/填补过程),使变分下界在当前参数点完美贴合真实的边缘对数似然目标。

单调收敛性

当完成一轮完整的迭代(E 步 + M 步)后,真实的边缘对数似然 \(l(\theta)\) 究竟是增加了还是减少了?算法是否能够保证收敛?

1. 核心链式不等式

在第 \(k\) 轮迭代中,经过 E 步与 M 步后,边缘对数似然满足以下连续的不等式链: \(l(\theta^{(k-1)}) \stackrel{\text{(1) E 步}}{=} \mathcal{F}(q^{(k)}, \theta^{(k-1)}) \stackrel{\text{(2) M 步}}{\le} \mathcal{F}(q^{(k)}, \theta^{(k)}) \stackrel{\text{(3) Jensen / KL}}{\le} l(\theta^{(k)})\)

三步证明分解

  1. 第一步(E 步对齐等式):
    • 在 E 步更新分布为 \(q^{(k)}\) 后,自由能与旧参数下的对数似然完全相等(\(l(\theta^{(k-1)}) = \mathcal{F}(q^{(k)}, \theta^{(k-1)})\))。自由能下界曲线在当前参数点抬高并完全“接触”到了真实对数似然曲线。
  2. 第二步(M 步提升不等式):
    • M 步保持分布 \(q^{(k)}\) 固定,寻找使自由能最大的新参数 \(\theta^{(k)}\)。
    • 既然 \(\theta^{(k)}\) 是该分布下使 \(\mathcal{F}\) 达到最大(或至少更大)的值,那么新参数下的自由能必然不小于旧参数下的自由能:\(\mathcal{F}(q^{(k)}, \theta^{(k-1)}) \le \mathcal{F}(q^{(k)}, \theta^{(k)})\)。
  3. 第三步(下界关卡不等式):
    • 由琴生不等式(或 KL 散度非负性 \(KL \ge 0\))可知,对于任意参数 \(\theta\) 和任意分布 \(q\),自由能始终是边缘对数似然的下界:\(\mathcal{F}(q^{(k)}, \theta^{(k)}) \le l(\theta^{(k)})\)

      2. 结论

      (1) 单调非递减保证 (Monotonic Improvement Guarantee)

      首尾相连直接导出最终结论: \(l(\theta^{(k-1)}) \le l(\theta^{(k)})\)

    • 数学意义:每一轮 EM 迭代后,观测数据的真实边缘对数似然 \(l(\theta)\) 绝不减少(单调递增或保持不变)。
    • 这就是 EM 算法非常稳定、不需要设定学习率(Learning Rate) 且不会出现梯度爆炸或震荡发散的数学根源。

      (2) 不动点与局域极值 (Fixed Points and Local Maxima)

    • 若某一轮迭代中 \(l(\theta^{(k)}) = l(\theta^{(k-1)})\),算法到达不动点。
    • EM 算法的收敛不动点在数学上严格对应于边缘对数似然曲线 \(l(\theta)\) 的驻点或局域极小/极值点(Stationary Points / Local Maxima)。

EM Summary

1. Mathematical Framework

(1) 优化目标

EM 算法是一种迭代算法,旨在求解隐变量模型边缘对数似然的(局域)最大值: \(l(\theta) = \log P(X\vert{}\theta) = \log \int dZ \, P(X\vert{}Z, \theta) P(Z\vert{}\theta)\)

(2) 统一目标函数(变分下界 / 自由能)

通过引入变分分布 \(q(Z)\),将原问题转化为对变分自由能 \(\mathcal{F}(q, \theta)\) 的最大化过程: \(\mathcal{F}(q, \theta) = \big\langle \log P(Z, X \vert{} \theta) \big\rangle_{q(Z)} + H(q) = l(\theta) - KL\Big(q(Z) \;\Big\Vert{}\; P(Z\vert{}X, \theta)\Big) \le l(\theta)\)

(3) 坐标上升更新律 (Coordinate Ascent Rules)

  • E 步(分布空间最大化):\(q^{(k)}(Z) := \arg\max_{q(Z)} \mathcal{F}\big(q(Z), \theta^{(k-1)}\big) = P(Z \mid X, \theta^{(k-1)})\)
  • M 步(参数空间最大化):\(\theta^{(k)} := \arg\max_\theta \mathcal{F}\big(q^{(k)}(Z), \theta\big) = \arg\max_\theta \big\langle \log P(Z, X \vert{} \theta) \big\rangle_{q^{(k)}(Z)}\)

    2. 极值等效性

    (1) 下界紧致性与极大值等价

  • E 步完成后的状态:当变分分布更新为真实后验分布时,\(KL\) 散度降为 \(0\),变分自由能与边缘对数似然完全重合:\(\mathcal{F}(q^{(k)}, \theta^{(k-1)}) = l(\theta^{(k-1)})\)。
  • 极值等价性:由于自由能紧贴边缘对数似然,自由能 \(\mathcal{F}\) 的局域极大值点完全等价于边缘对数似然 \(l(\theta)\) 的局域极大值点。

    (2) EM 算法的本质解构

  • EM 算法的精髓在于化繁为简:它避免了直接对复杂的边缘对数似然 \(l(\theta)\) 求导,而是借由变分自由能 \(\mathcal{F}(q, \theta)\) 这个桥梁,将其拆解为分布空间(推断)与参数空间(学习)交替坐标上升的简单寻优动作。

图解

EM 算法在参数空间中是如何通过交替执行“构造下界相切”与“沿下界爬峰”来实现边缘对数似然 \(l(\theta)\) 极大化的

(1) 初始化阶段 (Initialization)

  • 几何状态:在参数空间中随机选定初始参数 \(\theta_0\)。黑线为真实的边缘对数似然曲线 \(l(\theta)\),蓝线为初始分布 \(q_0\) 对应的自由能下界曲线 \(\mathcal{F}(q_0, \theta)\)。
  • 状态特征:在 \(\theta_0\) 处,由于 \(q_0\) 尚未优化,蓝线位于黑线下方,二者之间存在间距(间距即为 KL 散度)。

    (2) E 步 1 (E-step 1)

  • 几何动作:固定参数 \(\theta_0\),更新变分分布为 \(q_1(\mathcal{Z}) = P(\mathcal{Z}\vert{}\mathcal{D}, \theta_0)\)。
  • 几何结果:蓝色的自由能曲线 \(\mathcal{F}(q_1, \theta)\) 被整体向上“抬高”,直到在当前参数点 \(\theta_0\) 处与黑色似然曲线 \(l(\theta)\) 精准相切(相碰)。此时 \(KL = 0\),下界完全贴合真实似然。

    (3) M 步 1 (M-step 1)

  • 几何动作:固定变分分布 \(q_1\),沿着蓝色的下界曲线 \(\mathcal{F}(q_1, \theta)\) 寻找其最高点。
  • 几何结果:参数从 \(\theta_0\) 移动到蓝色曲线的峰值点 \(\theta_1\)。由于是在下界曲线上往高处走,新参数 \(\theta_1\) 处的真实对数似然值 \(l(\theta_1)\) 被托举到了更高的位置。

    (4) E 步 2 (E-step 2)

  • 几何动作:在新的参数点 \(\theta_1\) 处,重新计算隐变量的后验分布 \(q_2(\mathcal{Z}) = P(\mathcal{Z}\vert{}\mathcal{D}, \theta_1)\)。
  • 几何结果:新的自由能曲线 \(\mathcal{F}(q_2, \theta)\) 再次向上抬升,与黑色似然曲线在 \(\theta_1\) 处重新贴合相切,为下一轮 M 步的进一步爬升搭建新的平台。

广义 EM 算法:部分 M 步与部分 E 步

在工业级海量数据或复杂高维模型中,精确求出后验分布(精确 E 步)或求出变分下界的闭式最大值解(精确 M 步)往往计算成本极高乃至无法求解。若我们在 E 步或 M 步中“不做到极致最大化”,仅仅是让自由能 \(\mathcal{F}\) 有所增加(Increase),算法是否依然成立?

1. 部分 M 步与广义 EM 算法 (Partial M Steps & GEM)

(1) 概念与机制

如果完全最大化自由能 \(\mathcal{F}\) 过于困难,只需选择一个新的参数 \(\theta^{(t)}\),使得自由能相比旧参数有所提升(\(\mathcal{F}(q^{(t)}, \theta^{(t)}) > \mathcal{F}(q^{(t)}, \theta^{(t-1)})\))即可。这种仅提升自由能而不强求全局/局部最大化的变体,称为广义 EM 算法(Generalized EM, GEM)。

(2) 梯度等效性

在 E 步完成后(此时 \(q^{(t)}(\mathcal{Z}) = P(\mathcal{Z}\vert{}\mathcal{D}, \theta^{(t-1)})\)),完全数据对数似然期望关于参数 \(\theta\) 的一阶偏导数,完全等于边缘对数似然 \(l(\theta)\) 关于参数 \(\theta\) 的一阶偏导数: \(\left. \frac{\partial}{\partial \theta} \right\vert{}_{\theta^{(t-1)}} \big\langle \log P(\mathcal{D}, \mathcal{Z} \mid \theta) \big\rangle_{q^{(t)}(\mathcal{Z})} = \left. \frac{\partial}{\partial \theta} \right\vert{}_{\theta^{(t-1)}} \log P(\mathcal{D} \mid \theta)\)

(3) 算法应用扩展

这一梯度等效性意味着,E 步不仅可用于标准 M 步,还可作为构建其他基于梯度的优化方案(例如“期望共轭梯度法 Expectation Conjugate Gradient”)的桥梁,直接通过对下界求一阶梯度来完成参数更新。

2. 部分 E 步 (Partial E Steps)

(1) 概念与机制

同理,我们不必每次都在全量数据集上更新所有隐变量的精确后验分布,可以仅对部分变分分布 \(q\) 进行更新来增加自由能 \(\mathcal{F}\)。

(2) 典型应用场景

  1. 在线 EM (Online EM):当数据呈流式源源不断到来时,仅根据当前到达的新数据小批量(Mini-batch)更新对应的隐变量后验。
  2. 稀疏 EM (Sparse EM):每一轮仅挑选活跃的数据子集进行后验更新。
  3. 坐标上升 E 步:在隐变量维度极高时,每次仅更新一部分隐变量的后验分布,保持其余隐变量后验固定

    3. 核心

    变分自由能 \(\mathcal{F}(q, \theta)\) 作为一个统一的标量优化目标,赋予了 EM 算法极高的灵活性。只要 E 步和 M 步的局部更新能够保证自由能 \(\mathcal{F}\) 单调不减,整体边缘对数似然的单调非递减收敛特性就依然得到完备保证。

高斯混合模型(GMM)的 EM 算法更新

将通用的 E 步与 M 步理论落地到具体的高斯混合模型(GMM / MoG)中,给出计算分量责任度(Responsibilities \(r_{im}\))和更新模型参数(均值 \(\mu_m\)、协方差 \(\Sigma_m\)、混合比率 \(\pi_m\))的显式闭式更新公式。

1. 算法步骤

(1) E 步:评估分量责任度 (Evaluate Responsibilities)

基于当前参数,对于每个数据点 \(x_i\) 和第 \(m\) 个高斯分量,评估该分量生成该数据点的后验概率(称为责任度 \(r_{im}\)): \(r_{im} = \frac{P_m(x_i) \pi_m}{\sum_{m'} P_{m'}(x_i) \pi_{m'}}\)

  • \(r_{im}\) 代表第 \(m\) 个高斯分量对观测点 \(x_i\) 的“解释权重”或“归属概率”。它将传统 K-Means 算法中的硬分类(Hard Assignment,即一个点只能归属于单一簇 \(r_{im} \in \{0, 1\}\))推广为连续的概率分配(Soft Assignment \(r_{im} \in [0, 1]\))。

    (2) M 步:加权参数更新 (Update Parameters)

    固定 E 步计算出的责任度矩阵 \(r_{im}\),通过最大化期望对数似然,重新计算各个高斯分量的参数:

  • 均值向量更新(Mean Update):\(\mu_m \leftarrow \frac{\sum_i r_{im} x_i}{\sum_i r_{im}}\)
  • 新均值 \(\mu_m\) 不再是所有数据点的简单算术平均,而是以责任度 \(r_{im}\) 为权重的加权平均值。责任度越高的数据点,对该分量中心位置的牵引力越大。
  • 协方差矩阵更新(Covariance Update): \(\Sigma_m \leftarrow \frac{\sum_i r_{im} (x_i - \mu_m)(x_i - \mu_m)^T}{\sum_i r_{im}}\)
    • 衡量数据点围绕新均值 \(\mu_m\) 的加权离散程度(即加权离差矩阵的平均)。
  • 混合系数更新(Mixing Proportions Update): \(\pi_m \leftarrow \frac{\sum_i r_{im}}{N}\) - 物理 Insight:第 \(m\) 个分量的先验混合概率,等于分配给该分量的有效数据点总总数(\(\sum_i r_{im}\))占全量样本总数 \(N\) 的比例。

    2. 与 K-Means 的对应与指数族的优势

    1. 超越球形距离的软聚类:
    • K-Means 只能假设簇为等方差的球形,而 GMM 借助协方差矩阵 \(\Sigma_m\) 可以捕捉任意形状的椭圆簇分布。 2. 指数族的代数优雅性:
    • 由于高斯分布属于指数族分布,在 E 步固定 \(r_{im}\) 后,M 步的对数似然期望极值点可以通过直接偏导求零值获得解析闭式解,避免了缓慢的数值迭代求导。

一维高斯混合模型的 E 步与 M 步

1. E 步:基于贝叶斯后验计算责任度 (E-Step Derivation)

在一维 \(K\) 分量高斯混合模型中,数据点 \(x_i\) 的边缘概率密度函数为: \(p(x_i \mid \theta) = \sum_{m=1}^K P(s_i = m \mid \theta) \, p(x_i \mid s_i = m, \theta) = \sum_{m=1}^K \frac{\pi_m}{\sqrt{2\pi}\sigma_m} \exp \left\{ -\frac{(x_i - \mu_m)^2}{2\sigma_m^2} \right\}\) 其中 \(\theta = \{\mu_m, \sigma_m^2, \pi_m\}_{m=1}^K\) 为模型全局参数,\(s_i \in \{1, \dots, K\}\) 为指示数据点 \(x_i\) 来自哪个高斯分量的隐变量。

责任度 \(r_{im}\) 的计算:

根据贝叶斯定理,在当前参数 \(\theta\) 下,隐变量 \(s_i = m\) 的后验分布定义为第 \(m\) 个高斯分量对数据点 \(x_i\) 的责任度(Responsibility \(r_{im}\)): \(r_{im} \stackrel{\text{def}}{=} q(s_i = m) = P(s_i = m \mid x_i, \theta) = \frac{\pi_m \cdot \frac{1}{\sigma_m} \exp \left\{ -\frac{(x_i - \mu_m)^2}{2\sigma_m^2} \right\}}{\sum_{m'=1}^K \pi_{m'} \cdot \frac{1}{\sigma_{m'}} \exp \left\{ -\frac{(x_i - \mu_{m'})^2}{2\sigma_{m'}^2} \right\}}\)

  • 约束归一化:分母作为归一化因子,确保对任意数据点 \(x_i\),其归属于各个分量的责任度之和恒等于 1(即 \(\sum_{m=1}^K r_{im} = 1\))。

2. M 步:完全数据对数似然期望与求导 (M-Step Derivation)

(1) 期望对数似然函数 \(E\) 的构造

在 M 步中,固定 E 步求得的责任度 \(r_{im}\),写出完全数据联合概率对数在后验分布 \(q(s)\) 下的期望值 \(E = \big\langle \log p(x, s \mid \theta) \big\rangle_{q(s)}\): \(\begin{aligned} E &= \sum_{i=1}^N \sum_{m=1}^K q(s_i = m) \log \left[ P(s_i = m \mid \theta) \, p(x_i \mid s_i = m, \theta) \right] \\ &= \sum_{i=1}^N \sum_{m=1}^K r_{im} \left[ \log \pi_m - \log \sigma_m - \frac{(x_i - \mu_m)^2}{2\sigma_m^2} \right] + \text{常数} \end{aligned}\) (注:常数项包含无关于参数求导的 \(\log(2\pi)\))。

(2) 偏导求零与闭式解导出

  • 一、求解新均值 \(\mu_m\): 对 \(\mu_m\) 求偏导并令其等于零: \(\frac{\partial E}{\partial \mu_m} = \sum_{i=1}^N r_{im} \cdot \frac{x_i - \mu_m}{\sigma_m^2} = 0 \implies \mu_m = \frac{\sum_{i=1}^N r_{im} x_i}{\sum_{i=1}^N r_{im}}\)
  • 二、求解新标准差 \(\sigma_m\): 对 \(\sigma_m\) 求偏导并令其等于零:\(\frac{\partial E}{\partial \sigma_m} = \sum_{i=1}^N r_{im} \left[ -\frac{1}{\sigma_m} + \frac{(x_i - \mu_m)^2}{\sigma_m^3} \right] = 0 \implies \sigma_m^2 = \frac{\sum_{i=1}^N r_{im} (x_i - \mu_m)^2}{\sum_{i=1}^N r_{im}}\)
  • 三、求解新混合比例 \(\pi_m\)(拉格朗日乘子法): 由于混合比例满足概率约束条件 \(\sum_{m=1}^K \pi_m = 1\),构造拉格朗日函数 \(\mathcal{L}(\pi, \lambda) = E + \lambda \left( 1 - \sum_{m=1}^K \pi_m \right)\):\(\frac{\partial \mathcal{L}}{\partial \pi_m} = \frac{\sum_{i=1}^N r_{im}}{\pi_m} - \lambda = 0 \implies \pi_m = \frac{\sum_{i=1}^N r_{im}}{\lambda}\) 对所有 \(m\) 求和,利用 \(\sum_{m=1}^K \pi_m = 1\) 与 \(\sum_{m=1}^K r_{im} = 1\),可得 \(\lambda = N\)。故:\(\pi_m = \frac{\sum_{i=1}^N r_{im}}{N}\)

    3. 核心

  • 原本直接优化边缘似然时,\(\log \sum\) 导致参数之间深度耦合。然而在 M 步中,对数穿透到了求和符号内部(\(\sum r_{im} \log(\dots)\)),使得关于 \(\mu_m\)、\(\sigma_m^2\) 和 \(\pi_m\) 的偏导方程彼此解耦,从而能够一步直接求出解析解。
  • 均值、方差和混合比例的更新公式,在结构上完全等价于标准的高斯 MLE 估计,唯一的改变就是每个样本点 \(x_i\) 都附带了一个由 E 步赋予的权重 \(r_{im}\)。

指数族分布与指数族混合模型的 EM 算法

将 EM 算法从具体的高斯分布推广至通用的指数族分布(Exponential Family)及其混合模型。揭示为什么指数族分布与 EM 算法具备天然的代数契合度,并导出基于充分统计量期望(Expected Sufficient Statistics)的通用 EM 求解范式

1. 指数族联合分布下的 EM 算法 (EM for Exponential Families)

(1) 完全数据的指数族表达

假设由“观测变量 \(x\) + 隐变量 \(z\)”构成的完全数据 \(\xi = (z, x)\) 的联合概率分布属于指数族分布:\(p(\xi \mid \theta) = p(z, x \mid \theta) = \frac{f(\xi)}{Z(\theta)} \exp \left\{ \theta^T T(\xi) \right\}\) 其中 \(T(\xi) = T(z, x)\) 为模型的充分统计量(Sufficient Statistics),\(\theta\) 为自然参数(Natural Parameters),\(Z(\theta)\) 为配分函数(Partition Function / Normaliser)。

(2) 自由能 \(\mathcal{F}(q, \theta)\) 的代数简化

将完全数据概率代入变分自由能公式中(其中 \(H_q\) 仅与 \(q\) 相关,在 M 步视为常数):\(\begin{aligned} \mathcal{F}(q, \theta) &= \int q(z) \log p(z, x \mid \theta) \, dz + H_q \\ &= \int q(z) \left[ \theta^T T(z, x) - \log Z(\theta) + \log f(z, x) \right] dz + H_q \\ &= \theta^T \big\langle T(z, x) \big\rangle_{q(z)} - \log Z(\theta) + \text{常数} \end{aligned}\)

(3) E 步与 M 步的代数实质

  • E 步(算期望):由于 \(\mathcal{F}\) 关于参数 \(\theta\) 的依赖完全集中在 \(\big\langle T(z, x) \big\rangle_{q(z)}\) 上,E 步的核心任务简化为:仅需计算充分统计量在当前变分后验分布 \(q(z)\) 下的期望值。
  • M 步(矩匹配 Moment Matching): 对自由能 \(\mathcal{F}\) 关于自然参数 \(\theta\) 求偏导并令其等于 0 \(\frac{\partial \mathcal{F}}{\partial \theta} = \big\langle T(z, x) \big\rangle_{q(z)} - \frac{\partial \log Z(\theta)}{\partial \theta} = 0\) 利用指数族分布的性质 \(\frac{\partial \log Z(\theta)}{\partial \theta} = \big\langle T(\xi) \big\rangle_{p(\xi \mid \theta)}\)(即模型在该参数下的理论期望充分统计量),可得 M 步的方程:\(\big\langle T(z, x) \big\rangle_{q(z)} = \big\langle T(z, x) \big\rangle_{p(z, x \mid \theta)}\)

2. 指数族混合模型与示性向量 (EM for Exponential Family Mixtures)

为了严谨推导离散隐变量混合模型(如 Poisson 混合模型、Bernoulli 混合模型等),引入独热/示性向量(Indicator Vector \(\mathbf{s}_i\)) 代替标量隐变量 \(s_i\):\(\mathbf{s}_i = [0, \dots, \underset{\text{第 } m \text{ 位}}{1}, \dots, 0]^T\) 将 \(M\) 个指数族分量的自然参数收集为矩阵 \(\mathbf{\Theta} = [\theta_1, \dots, \theta_M]\),整个数据集的完全数据对数似然可统一写为:\(\log P(X, S) = \sum_{i=1}^N \left[ (\log \boldsymbol{\pi})^T \mathbf{s}_i + \mathbf{s}_i^T \mathbf{\Theta}^T T(x_i) - \mathbf{s}_i^T \log \mathbf{Z}(\mathbf{\Theta}) \right] + \text{常数}\)

算法更新两步法:

  1. E 步:
    • 计算责任度期望:\(\big\langle \mathbf{s}_i \rangle_q = [r_{i1}, \dots, r_{iM}]^T\)(即样本 \(x_i\) 属于分量 \(m\) 的后验概率)。
    • 计算责任度加权的充分统计量:\(\sum_{i=1}^N r_{im} T(x_i)\)。
  2. M 步:
    • 混合比例更新:\(\pi_m \propto \sum_{i=1}^N r_{im}\)。
    • 分量参数 \(\theta_m\) 更新:令加权充分统计量等于该分量在 \(\theta_m\) 下的理论期望 \(\big\langle T(x) \big\rangle_{p(x \mid \theta_m)} = \frac{\sum_i r_{im} T(x_i)}{\sum_i r_{im}}\)。

      3. 核心:指数族与EM

  3. 有限维信息压缩(有限维充分统计量):
    • 在一般的非指数族模型中,E 步需要维护整个复杂的连续分布 \(q(z)\)。但在指数族模型中,由 Pitman-Koopman-Darmois 定理,E 步只需要保存并传递有限维度的充分统计量期望值 \(\big\langle T(z, x) \big\rangle_{q(z)}\),极大节省了计算开销。
  4. M 步的全局凸性保障:
    • 指数族的对数配分函数 \(\log Z(\theta)\) 始终是关于自然参数 \(\theta\) 的凸函数。因此,M 步对 \(\mathcal{F}\) 的优化永远是一个良好的凹函数最大化问题,不存在多余的伪局域极值,通常直接存在封闭形式的解析解。

      MAP 框架下的 EM 算法

      之前的 EM 算法均服务于最大似然估计(MLE),即寻找单个最佳点估计参数 \(\theta\)。如果我们拥有关于参数的先验知识(即共轭先验 \(p(\theta)\)),希望进行最大后验估计(MAP, Maximum A Posteriori),EM 算法的变分框架该如何扩充?

      1. 扩充变分自由能 (Augmented Free Energy)

      在 MAP 求解中,我们的目标是最大化对数联合概率 \(\log P(X, \theta) = \log P(X\vert{}\theta) + \log p(\theta)\)。

      (1) 定义扩充自由能 \(\mathcal{F}_{\text{MAP}}(q, \theta)\)

      在原有的变分自由能 \(\mathcal{F}(q, \theta)\) 基础之上,直接叠加参数的对数先验项 \(\log p(\theta)\)\(\mathcal{F}_{\text{MAP}}(q, \theta) \stackrel{\text{def}}{=} \int q(Z) \log p(Z, X, \theta) \, dZ + H(q) \le \log P(X\vert{}\theta) + \log p(\theta)\) 根据琴生不等式(Jensen’s Inequality),\(\mathcal{F}_{\text{MAP}}(q, \theta)\) 始终是联合对数概率 \(\log P(X, \theta)\) 的严谨下界。

      (2) 指数族与共轭先验的代数代入

      假设完全数据属于指数族 \(p(\xi \mid \theta) = \frac{f(\xi)}{Z(\theta)} \exp\{\theta^T T(\xi)\}\),参数先验选用其共轭形式 \(p(\theta) = \frac{F(\nu, \tau)}{Z(\theta)^\nu} \exp\{\theta^T \tau\}\)(其中 \(\tau\) 表示先验伪观测充分统计量,\(\nu\) 表示先验伪样本量/浓度)。 将两者代入扩充自由能并整理展开:\(\begin{aligned} \mathcal{F}_{\text{MAP}}(q, \theta) &= \int q(Z) \left[ \theta^T \left( \sum_{i=1}^N T(\xi_i) + \tau \right) - (N + \nu) \log Z(\theta) \right] dZ + \text{常数} \\ &= \theta^T \left( \sum_{i=1}^N \big\langle T(\xi_i) \big\rangle_{q(Z)} + \tau \right) - (N + \nu) \log Z(\theta) + \text{常数} \end{aligned}\)

      2. 核心 Insight 与算法流程特性

      (1) E 步完全保持不变 (Unchanged E Step)

    • 代数原因:新增的先验项 \(\log p(\theta)\) 仅与模型参数 \(\theta\) 相关,完全不显式依赖于隐变量 \(Z\)。
    • 结论:在 E 步固定 \(\theta\) 关于变分分布 \(q(Z)\) 进行最大化时,先验项作为常数项不参与求导。因此,E 步计算隐变量后验 \(q(Z) = P(Z\vert{}X, \theta)\) 以及充分统计量期望 \(\big\langle T(\xi) \big\rangle_q\) 的过程与标准的 MLE EM 算法完全一致。

      (2) M 步的物理本质:先验做“正则化 / 伪样本” (Prior as Regularisation)

    • 在 M 步更新参数 \(\theta\) 时,先验参数 \(\tau\) 与 \(\nu\) 直接融入了更新公式中:
      • 观测数据充分统计量:由单纯的数据期望 \(\sum_i \big\langle T(\xi_i) \big\rangle_q\) 变更为修正后的总量 \(\sum_i \big\langle T(\xi_i) \big\rangle_q + \tau\);
      • 有效样本量:由数据量 \(N\) 修正为 \(N + \nu\)。
    • 工程 Insight:先验赋予了模型“伪样本”,这为数值计算提供了极佳的正则化(Regularization)保护。例如在大规模混合高斯模型(GMM)中,MAP-EM 可以完美防止某个高斯分量因分配到的样本过少而导致协方差矩阵奇异(崩溃为零方差)的问题.

      (3) 局域极大值的完全等效性

    • 在 E 步更新后,\(\mathcal{F}_{\text{MAP}}(q, \theta) = \log P(X, \theta)\)。因此,扩充自由能 \(\mathcal{F}_{\text{MAP}}\) 的局域极大值点完全等价于 MAP 目标(对数联合概率 \(\log P(X, \theta)\))的局域极大值点。

      3. 向变分贝叶斯 (Variational Bayes) 的前瞻

    • MAP-EM 依然只是对参数 \(\theta\) 求解了一个最佳点估计值(Point Estimate)。
    • 如果希望进一步对参数 \(\theta\) 的完整概率分布进行近似推断(保持参数的不确定性),我们需要将参数 \(\theta\) 与隐变量 \(Z\) 同等对待,这就引出了后续章节的变分贝叶斯(Variational Bayes, VB)框架。

EM 算法的不动点与对数似然的驻点

当 EM 算法经过多轮迭代最终停止更新,收敛到某一个固定不变的参数点 \(\theta^*\)(即不动点 Fixed Point)时,这个点在原问题的真实对数似然曲线 \(l(\theta)\) 上具备怎样的微积分性质?它是否一定保证是一阶导数为 0 的驻点(Stationary Point)?

1. 数学证明

(1) 不动点(Fixed Point)的严格代数定义

假设算法收敛于不动点 \(\theta^*\)。在不动点处,后验分布更新为 \(q^*(Z) = P(Z \mid X, \theta^*)\)。根据 M 步定义,\(\theta^*\) 必须是固定 \(q^*\) 条件下自由能 \(\mathcal{F}(q^*, \theta)\) 的极大值点:\(\left. \frac{\partial \mathcal{F}(q^*, \theta)}{\partial \theta} \right\vert{}_{\theta = \theta^*} = 0\)

(2) 自由能展开与导数分解

回忆前文推导的变分自由能恒等式\(\mathcal{F}(q^*, \theta) = l(\theta) - KL\Big(q^*(Z) \;\Big\Vert{}\; P(Z \mid X, \theta)\Big)\) 对两端关于参数 \(\theta\) 求偏导数,并代入 \(\theta = \theta^*\):\(\left. \frac{\partial \mathcal{F}(q^*, \theta)}{\partial \theta} \right\vert{}_{\theta = \theta^*} = \left. \frac{d l(\theta)}{d \theta} \right\vert{}_{\theta = \theta^*} - \left. \frac{\partial}{\partial \theta} KL\Big(q^*(Z) \;\Big\Vert{}\; P(Z \mid X, \theta)\Big) \right\vert{}_{\theta = \theta^*}\)

(3) \(KL\) 散度导数项的消失(关键突破点)

  • 注意第二项中,\(q^*(Z)\) 是固定不动的分布 \(P(Z \mid X, \theta^*)\)。
  • 当 \(\theta = \theta^*\) 时,后验分布 \(P(Z \mid X, \theta)\) 正好等于 \(q^*(Z)\),因此 \(KL\) 散度达到其全局极小值 \(0\)。
  • 根据微积分基本定理,一个连续可微函数在极小值点处的切线斜率(一阶导数)必然为零\(\left. \frac{\partial}{\partial \theta} KL\Big(q^*(Z) \;\Big\Vert{}\; P(Z \mid X, \theta)\Big) \right\vert{}_{\theta = \theta^*} = 0\)

    (4) 导出驻点结论

    将两个偏导数归零的结果代回分解式中:\(0 = \left. \frac{d l(\theta)}{d \theta} \right\vert{}_{\theta = \theta^*} - 0 \implies \left. \frac{d l(\theta)}{d \theta} \right\vert{}_{\theta = \theta^*} = 0\)

  • 结论:EM 算法的任何不动点 \(\theta^*\),都必然是边缘对数似然 \(l(\theta)\) 的驻点(Stationary Point)!

    2. 核心

    1. 算法收敛的微积分严谨性:
    • 该证明给出了强有力的理论保证:EM 算法绝对不会停留在对数似然曲面上斜率不为零的“半山腰”位置。只要参数不再发生改变,当前点在真实似然曲面上必定处于平坦的切线位置。 2. 驻点的多重可能性:
    • 在微积分中,一阶导数为零的驻点可能包含三种情况:局域极大值(Local Maxima)、鞍点(Saddle Points) 或 局域极小值(Local Minima)。
    • 结合对数似然单调非递减特性(\(l(\theta^{(k)}) \ge l(\theta^{(k-1)})\)),EM 算法会自动避开局域极小值点,并在绝大多数实用场景下稳定收敛至局域极大值点。

自由能局域极大值与对数似然局域极大值的等价性 (Maxima in \(\mathcal{F}\) correspond to Maxima in \(l\))

驻点包含局域极大值、局域极小值和鞍点。变分自由能 \(\mathcal{F}(q, \theta)\) 在联合空间 \((q, \theta)\) 中的局域极大值点(Local Maxima),必然精准对应于边缘对数似然 \(l(\theta)\) 在参数空间中的局域极大值点

(1) 定理表述

设 \((q^*, \theta^*)\) 为变分自由能 \(\mathcal{F}(q, \theta)\) 在变分分布与参数联合空间 \(\mathcal{Q} \times \Theta\) 中的一个局域极大值点,则 \(\theta^*\) 必为边缘对数似然 \(l(\theta) = \log P(X\vert{}\theta)\) 在参数空间 \(\Theta\) 中的局域极大值点。

(2) 代数证明链条拆解

  1. 后验紧致性(E 步重合): 由于 \((q^*, \theta^*)\) 极大化自由能,关于变分分布 \(q\) 求极大值的最优解必然是当前参数下的真实后验分布 \(q^*(Z) = P(Z \mid X, \theta^*)\)。在该点处 \(KL\) 散度为零,自由能与对数似然完全重合:\(\mathcal{F}(q^*, \theta^*) = l(\theta^*)\)
  2. 邻域下界关系: 考虑参数点 \(\theta^*\) 的一个足够小的局部邻域 \(U(\theta^*)\)。对于该邻域内的任意参数 \(\theta \in U(\theta^*)\),令其对应的真实隐变量后验分布为 \(q_\theta(Z) = P(Z \mid X, \theta)\)。 在参数 \(\theta\) 处,当变分分布取为真实后验 \(q_\theta\) 时,自由能同样触及对数似然:\(l(\theta) = \mathcal{F}(q_\theta, \theta)\)
  3. 联合空间局域极大性: 当 \(\theta\) 充分接近 \(\theta^*\) 时,后验分布 \(q_\theta\) 亦在 \(q^*\) 的邻域内。由于 \((q^*, \theta^*)\) 是 \(\mathcal{F}(q, \theta)\) 在联合空间中的局域极大值点,因此对邻域内任意组合 \((q_\theta, \theta)\),均满足: \(\mathcal{F}(q^*, \theta^*) \ge \mathcal{F}(q_\theta, \theta)\)
  4. 不等式闭环导出: 将等式代入上述不等式两端:\(l(\theta^*) = \mathcal{F}(q^*, \theta^*) \ge \mathcal{F}(q_\theta, \theta) = l(\theta)\) 即对于 \(\theta^*\) 邻域内的任意 \(\theta\),均有:\(l(\theta^*) \ge l(\theta)\) 这在微积分上完全符合边缘对数似然 \(l(\theta)\) 在 \(\theta^*\) 处取得局域极大值的严格定义。

EM 算法虽然直接操作的是辅助函数(变分自由能 \(\mathcal{F}\)),但本页定理与第 134 页的结合证明,确保了通过坐标上升法搜寻到的自由能极大值,就是真实边缘对数似然 \(l(\theta)\) 的极大值。这一等价性宣告了变分框架的正确性:只要我们能够构造并提升变分下界 \(\mathcal{F}\),就等价于在真实对数似然曲面上爬峰。

Markov Chains

在现实世界的许多无监督学习场景(如语音识别、自然语言处理、气象预测或生物基因序列)中,数据并非独立同分布(i.i.d.),而是具备前后时间关联性。为了对此类序列数据建立概率生成模型,我们需要引入马尔可夫链(Markov Chains)。通过限制每个时刻的状态仅依赖于前一个(或前几个)相邻状态,马尔可夫链使得高维连续或离散序列的联合概率分解成为可能

马尔可夫模型与条件独立性

1. 序列联合分布的三种概率建模表达 (Probabilistic Modeling of Sequences)

(1) 通用序列的全概率链式展开 (General Joint Distribution)

对任意时序列 \(\mathbf{x}_1, \dots, \mathbf{x}_t\),在不做任何独立性假设的情况下,其联合概率分布通过贝叶斯乘法公式展开为: \(P(\mathbf{x}_1, \dots, \mathbf{x}_t) = P(\mathbf{x}_1) P(\mathbf{x}_2 \mid \mathbf{x}_1) P(\mathbf{x}_3 \mid \mathbf{x}_1, \mathbf{x}_2) \cdots P(\mathbf{x}_t \mid \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_{t-1})\)

  • 建模代价:计算 \(P(\mathbf{x}_t)\) 时需要维护之前所有时刻 \((\mathbf{x}_1, \dots, \mathbf{x}_{t-1})\) 的完整历史记忆,随着时间 \(t\) 的增加,条件概率表的参数量成指数级增长。

    (2) 一阶马尔可夫模型 (First-Order Markov Model)

  • 核心代数分解:假设当前时刻 \(\mathbf{x}_t\) 仅显式依赖于紧邻的前一时刻 \(\mathbf{x}_{t-1}\): \(P(\mathbf{x}_1, \dots, \mathbf{x}_t) = P(\mathbf{x}_1) P(\mathbf{x}_2 \mid \mathbf{x}_1) \cdots P(\mathbf{x}_t \mid \mathbf{x}_{t-1}) = P(\mathbf{x}_1) \prod_{\tau=2}^t P(\mathbf{x}_\tau \mid \mathbf{x}_{\tau-1})\)
  • 概率图结构:由单向链式有向图表示:\(\mathbf{x}_1 \to \mathbf{x}_2 \to \mathbf{x}_3 \to \dots \to \mathbf{x}_T\)。

    (3) 二阶马尔可夫模型 (Second-Order Markov Model)

  • 核心代数分解:假设当前时刻 \(\mathbf{x}_t\) 显式依赖于过去连续的两个时刻 \((\mathbf{x}_{t-2}, \mathbf{x}_{t-1})\) \(P(\mathbf{x}_1, \dots, \mathbf{x}_t) = P(\mathbf{x}_1) P(\mathbf{x}_2 \mid \mathbf{x}_1) \cdots P(\mathbf{x}_{t-1} \mid \mathbf{x}_{t-3}, \mathbf{x}_{t-2}) P(\mathbf{x}_t \mid \mathbf{x}_{t-2}, \mathbf{x}_{t-1})\)
  • 概率图结构:每个节点同时接收来自前一级与前二级节点的有向边(例如 \(\mathbf{x}_1 \to \mathbf{x}_3\) 且 \(\mathbf{x}_2 \to \mathbf{x}_3\))。

    2. 条件独立

    (1) Markov本质上是指一种特定的条件独立关系(Conditional Independence Relationship)

    (2) “给定现在,过去与未来条件独立”

    以一阶马尔可夫模型为例,其物理与统计意义可精炼概括为:

  • 已知当前观察量 \(\mathbf{x}_t\)(Present): 未来时刻的序列 \((\mathbf{x}_{t+1}, \mathbf{x}_{t+2}, \dots)\)(Future)与过去时刻的历史 \((\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_{t-1})\)(Past)相互独立。
  • 条件独立写为:\((\mathbf{x}_{t+1}, \dots) \perp\!\!\!\perp (\mathbf{x}_1, \dots, \mathbf{x}_{t-1}) \mid \mathbf{x}_t\)。

    (3) 高阶马尔可夫模型的条件独立拓展

    在二阶马尔可夫模型中:

  • 已知连续两个时刻的观察量 \((\mathbf{x}_{t-2}, \mathbf{x}_{t-1})\): 时刻 \(\mathbf{x}_t\) 与更早的历史 \(\mathbf{x}_1, \dots, \mathbf{x}_{t-3}\) 独立(例如 \(\mathbf{x}_4\) 在给定 \(\mathbf{x}_2, \mathbf{x}_3\) 的条件下独立于 \(\mathbf{x}_1\))。

图表达与平稳性

以简单的二元状态马尔可夫链(Binary Chain)为例,介绍马尔可夫链的状态图表示法(Graphical Representation),并引出平稳性/时齐性(Stationarity)的基本概念。

1. 二元马尔可夫链的状态图表达 (A Simple Binary Chain)

考虑一个状态空间为 \(\mathcal{X} = \{0, 1\}\) 的马尔可夫链序列 \(X_0, X_1, X_2, \dots\):

  • 节点(Vertices):图中的节点代表变量可能处于的状态(States),即 0 和 1。
  • 有向边(Edges):节点之间的有向边代表相邻时刻的状态转移(Transition)\(X_{t-1} = i \to X_t = j\)。
  • 边权重(Edge Weights):每条有向边 \(i \to j\) 上标注的权重为条件转移概率:\(\phi(j \mid i) \stackrel{\text{def}}{=} P(X_t = j \mid X_{t-1} = i)\) (自环转移 \(\phi(0\vert{}0)\)、\(\phi(1\vert{}1)\),以及跨状态转移 \(\phi(1\vert{}0)\)、\(\phi(0\vert{}1)\))。

    2. 转移图 \(\neq\) 概率图模型

  • 差别本质:
    • 在概率图模型(如贝叶斯网络 \(\mathbf{x}_1 \to \mathbf{x}_2 \to \mathbf{x}_3\))中,每个节点代表一个随机变量;
    • 在马尔可夫链状态转移图中,每个节点仅代表单个随机变量可能取到的具体状态值(如状态 \(0\) 或状态 \(1\))。
  • 这种表示在自动机理论中严格对应于概率有限自动机(Probabilistic Finite Automaton, PFA)。

    3. 平稳性 / 时齐性 Stationarity / Time-Homogeneity

  • 绘制状态图的前提:只有当转移概率 \(\phi(j \mid i)\) 完全不依赖于具体的时间 \(t\) 时,才能画出一张固定的转移图。如果转移概率随时间变化,我们必须为每一个时刻 \(t\) 画一张不同的图。
  • 平稳马尔可夫链定义:如果转移概率 \(\phi(j \mid i) = P(X_t = j \mid X_{t-1} = i)\) 对任意时间 \(t\) 恒定不变,则该马尔可夫链被称为平稳的(Stationary)或时齐的(Time-Homogeneous)。平稳性假设(Stationarity Assumption)是马尔可夫链能够大幅降维的关键所在:不论序列长度 \(T\) 有多长,描述整个系统动态演化所需的转移参数都是固定且有限的。

    4. 示例一:独立投掷硬币序列 (Independent Coin Flips)

    (1) 问题设定

    假设 \(X_0, X_1, X_2, \dots\) 为一系列偏置硬币的投掷结果,且每次投掷完全独立(即 i.i.d. Bernoulli 过程,参数为 \(p\))

  • \[P(X_t = 1) = p\]
  • \(P(X_t = 0) = 1 - p\)

    (2) 状态转移概率

    由于各次投掷相互独立,无论前一时刻 \(X_{t-1}\) 是 0 还是 1,当前时刻 \(X_t\) 转移到状态 1 的概率恒为 \(p\),转移到状态 0 的概率恒为 \(1-p\):

  • \[\phi(1 \mid 0) = P(X_t = 1 \mid X_{t-1} = 0) = p\]
  • \[\phi(1 \mid 1) = P(X_t = 1 \mid X_{t-1} = 1) = p\]
  • \[\phi(0 \mid 0) = P(X_t = 0 \mid X_{t-1} = 0) = 1 - p\]
  • \(\phi(0 \mid 1) = P(X_t = 0 \mid X_{t-1} = 1) = 1 - p\)

    (3) 状态图特征

    从状态 0 和状态 1 出发射向状态 1 的有向边,其权重完全相同(均为 \(p\))。这表明前一时刻的状态对未来的转移方向没有任何区别对待,系统不具备任何关于过去的记忆。

    5. 示例二:打破独立性 (Breaking Independence)

    (1) 参数修改与状态图变动

    保持从状态 0 出发的转移概率不变(\(\phi(1 \mid 0) = p, \phi(0 \mid 0) = 1-p\)),仅对从状态 1 出发的转移概率做轻微修改:

  • 设 \(\phi(1 \mid 1) = 1\)(若当前处于状态 1,下一时刻必定保持状态 1)
  • 设 \(\phi(0 \mid 1) = 0\)(一旦进入状态 1,就无法再返回状态 0)

    (2) 概率性质的深刻变化

  • 仍然是合法的马尔可夫链:该序列依然严格满足一阶马尔可夫性(当前状态只依赖于紧邻的前一状态)。
  • 独立性被彻底打破:序列中的各个元素不再相互独立!一旦出现 \(X_t = 1\),所有未来的 \(X_{t+k}\) 都将恒为 1。这使得未来的概率分布高度依赖于历史状态。

    6. 核心

    1. 独立分布是马尔可夫链的特例: 当转移矩阵的各行完全相同(即 \(\phi(j \mid i)\) 与 \(i\) 无关)时,马尔可夫链即退化为独立的 i.i.d. 随机过程。
    2. 状态依赖的微小引入改变全局结构: 只需对转移矩阵中的某几个元素做出改动,就能在保留计算可行性的同时,使系统呈现出复杂的长程动态行为(如吸收态、周期震荡等)。

转移矩阵与初始分布 (Transition Matrix & Initial Distribution)

平稳马尔可夫链的严谨代数定式——引入转移矩阵(Transition Matrix \(\Phi\)) 与 初始分布(Initial Distribution \(P_{\text{init}}\)),并证明这两者足以完全确定整个有限状态马尔可夫链的联合分布

1. 转移概率与转移矩阵 (Transition Matrix \(\Phi\))

(1) 单步转移概率 (Transition Probabilities)

设状态空间为有限集 \(\mathcal{X}\),大小为 \(\vert{}\mathcal{X}\vert{} = K\)(例如 \(\mathcal{X} = \{1, 2, \dots, K\}\))。 条件概率 \(\phi(j \mid i)\) 定义为系统在当前时刻位于状态 \(i\) 的条件下,下一时刻转移到状态 \(j\) 的概率: \(\phi(j \mid i) \stackrel{\text{def}}{=} P(X_t = j \mid X_{t-1} = i)\)

(2) 转移矩阵的代数表达 (The \(K \times K\) Transition Matrix)

将所有状态对之间的转移概率收集为一个 \(K \times K\) 的二维矩阵 \(\Phi\):\(\Phi := (\phi(j \mid i))_{i, j \le K} = \begin{pmatrix} \phi(1 \mid 1) & \phi(2 \mid 1) & \dots & \phi(K \mid 1) \\ \phi(1 \mid 2) & \phi(2 \mid 2) & \dots & \phi(K \mid 2) \\ \vdots & \vdots & \ddots & \vdots \\ \phi(1 \mid K) & \phi(2 \mid K) & \dots & \phi(K \mid K) \end{pmatrix}\)

(3) 关键代数性质与图论对应

  • 按行归一化(Row Stochasticity):矩阵的第 \(i\) 行代表从状态 \(i\) 出发转移到各个状态的概率分布。因此第 \(i\) 行的元素之和恒等于 1:\(\sum_{j=1}^K \phi(j \mid i) = 1 \quad (\forall i \in \{1, \dots, K\})\)
  • 状态图的带权邻接矩阵:转移矩阵 \(\Phi\) 在几何上精确对应于状态转移图(State Graph)的带权邻接矩阵(Adjacency Matrix)。

    2. 初始状态分布 (Initial Distribution \(P_{\text{init}}\))

    (1) 定义

    时刻 \(t=0\) 时,系统处于各个状态的概率向量称为初始分布(Initial Distribution \(P_{\text{init}}\)): \(P_{\text{init}} \stackrel{\text{def}}{=} \left( P(X_0 = 1), P(X_0 = 2), \dots, P(X_0 = K) \right)\)

    (2) 概率归一化约束

    初始分布满足非负性与归一化约束:\(\sum_{k=1}^K P(X_0 = k) = 1\)。

    3. 核心

    (1) 完全决定性定理 (Completeness Theorem)

    一个具有有限状态空间的平稳/时齐马尔可夫链的全部统计性质,完全且唯一地由二元组 \((\Phi, P_{\text{init}})\) 所决定。

    (2) 任意序列路径的联合概率拆解

    借助一阶马尔可夫分解(第 140 页)与平稳转移矩阵,任意观察序列路径的联合概率可显式写为:

\[P(X_0 = s_0, X_1 = s_1, \dots, X_T = s_T) = P_{\text{init}}(s_0) \prod_{t=1}^T \phi(s_t \mid s_{t-1})\]

(3) 参数量的简化

  • 原本长度为 \(T\) 的 \(K\) 进制序列,其可能路径多达 \(K^{T+1}\) 种,直接建模需要指数级参数。
  • 借助平稳马尔可夫假设,只需存储 \(K \times K\) 的转移矩阵 \(\Phi\) 和 \(K\) 维初始向量 \(P_{\text{init}}\)(自由参数仅约 \(K^2\) 个),就完全解构了任意长度序列的概率分布。

状态边缘概率的 \(t\) 步时序推演 (State Probabilities & \(t\)-step Marginal Distributions)

在不需要知道中间具体路径的情况下,如何直接通过矩阵幂乘 \(P_t = P_{\text{init}} \Phi^t\) 快速求解时刻 \(t\) 的状态边缘分布 \(P_t\)

1. 第一步后的边缘分布推导 (Distribution After the First Step)

(1) 条件分布与已知初始状态

若已知系统初始确切处于状态 \(i\)(即 \(X_0 = i\)),则时刻 \(t=1\) 转移到状态 \(j\) 的概率就是转移矩阵的第 \(i\) 行第 \(j\) 列元素\(P(X_1 = j \mid X_0 = i) = \phi(j \mid i) = \Phi_{ij}\)

(2) 边缘分布 \(P_1\) 的边缘化(全概率公式)

在实际情况中,我们通常无法预先确定时刻 \(t=0\) 的确切状态,只掌握初始概率分布 \(P_{\text{init}}\)。 根据全概率公式(Marginalisation),消去初始状态 \(X_0\),可得时刻 \(t=1\) 处于状态 \(j\) 的边缘概率 \(P_1(j)\):\(P_1(j) \stackrel{\text{def}}{=} P(X_1 = j) = \sum_{i \in \mathcal{X}} P(X_1 = j \mid X_0 = i) P(X_0 = i) = \sum_{i \in \mathcal{X}} \phi(j \mid i) P_{\text{init}}(i)\)

(3) 向量-矩阵代数表达

由于 \(P_{\text{init}}\) 是长度为 \(K\) 的行向量,\(\Phi\) 是 \(K \times K\) 的转移矩阵,上述求和过程在代数上完全等价于向量与矩阵的乘积:\(P_1 = P_{\text{init}} \cdot \Phi\)

2. 多步状态演化与通用递推式 (\(t\)-step Marginal Distribution)

(1) 二步与三步推演

同理,利用马尔可夫无记忆性,时刻 \(t=2\) 的边缘分布可由时刻 \(t=1\) 的边缘分布再次乘以转移矩阵 \(\Phi\) 得到:\(P_2 = P_1 \cdot \Phi = (P_{\text{init}} \cdot \Phi) \cdot \Phi = P_{\text{init}} \cdot \Phi^2\)

(2) 任意 \(t\) 步通项公式

通过归纳法递推,系统在运行 \(t\) 步后的状态边缘概率分布向量 \(P_t\) 为: \(P_t = P_{\text{init}} \cdot \Phi^t\)

3. 核心

(1) 转移矩阵幂次 \(\Phi^t\) 的物理含义

  • 矩阵乘积 \(\Phi^t\) 的第 \(i\) 行第 \(j\) 列元素 \((\Phi^t)_{ij}\),精确代表系统从状态 \(i\) 出发,恰好经过 \(t\) 步后到达状态 \(j\) 的\(t\) 步转移概率 \(P(X_t = j \mid X_0 = i)\)。
  • 这在数学上等价于著名的 Chapman-Kolmogorov 方程:\((\Phi^t)_{ij} = \sum_k (\Phi^m)_{ik} (\Phi^{t-m})_{kj}\)

    (2) 动态演化的本质

  • 马尔可夫链的边缘概率推演避开了求和号对指数级状态路径(\(K^t\) 条路径)的显式遍历,而是将其转化为矩阵的算子作用与矩阵幂次运算。
  • 这种线性代数表示不仅极大地简化了计算复杂度,因而可以利用矩阵特征值与平稳分布研究系统长期极限行为(\(t \to \infty\) 时 \(P_\infty\) 的收敛性)

## 极限分布与平稳/不变分布 (Limits & Equilibrium Distributions)

与其仅关注某一个特定且巨大的时间步长 \(t\),我们更关心当时间趋于无穷大(\(t \to \infty\))时,系统状态的边缘概率分布是否会稳定收敛到某个固定的极限分布。

1. 极限分布 Limiting Distribution \(P_\infty\)

若极限存在,定义极限分布 \(P_\infty\) 为:

\[P_\infty \stackrel{\text{def}}{=} \lim_{t \to \infty} P_t = \lim_{t \to \infty} P_{\text{init}} \Phi^t\]

2. 平稳/不变分布 Equilibrium / Invariant Distribution

(1) Observation

若上述极限分布 \(P_\infty\) 确实存在,我们尝试让极限分布向量乘以转移矩阵 \(\Phi\):

\[P_\infty \cdot \Phi = \left( \lim_{t \to \infty} P_{\text{init}} \Phi^t \right) \cdot \Phi = \lim_{t \to \infty} P_{\text{init}} \Phi^{t+1} = P_\infty\]
  • 这一观察表明,极限分布 \(P_\infty\) 作用于转移矩阵 \(\Phi\) 后,其分布保持完全不变(Invariant)

    (2) 平稳/不变分布的定义

    设 \(\Phi\) 为马尔可夫链的转移矩阵。若状态空间上的某个概率分布 \(P\) 满足如下不变性条件:\(P \cdot \Phi = P\) 则称 \(P\) 为该马尔可夫链的平衡分布 / 平稳分布 / 不变分布(Equilibrium Distribution or Invariant Distribution)。

    3. 核心

    (1) 动态平衡的物理本质

  • \(P \cdot \Phi = P\) 并不意味着微观上各个样本不再发生状态转移,而是指流入某个状态的概率质量总和刚好等于流出该状态的概率质量总和。系统在宏观上达到了统计平衡状态。

    (2) 线性代数特征值视角

  • 平衡分布 \(P\) 在线性代数上精确对应于转移矩阵 \(\Phi\) 关于主特征值 \(\lambda = 1\) 的左特征向量(Left Eigenvector)。

    (3) 极限分布与平稳分布

  • 如果极限分布 \(P_\infty\) 存在,它必定是一个平稳分布;但反过来,并非所有马尔可夫链的极限分布都必然存在(例如存在周期震荡的情况。

平稳分布的存在性与唯一性

并非所有马尔可夫链都保证收敛或拥有唯一的平稳分布。判定平稳分布存在且唯一的两个核心条件——不可约性(Irreducibility) 与 非周期性(Aperiodicity),以及马尔可夫链遍历性主定理。

1. Structural Conditions

(1) 非周期性 (Aperiodic)

  • 条件与定义:如果转移矩阵的对角线元素严格大于零,即对所有状态 \(k \in \mathcal{X}\),系统留在当前状态的概率满足\(P(X_t = k \mid X_{t-1} = k) = \phi(k \mid k) > 0\)
  • 允许“留在原地(Self-loop)”破坏了固定的步数节奏,防止概率分布在不同的状态子集之间发生永不休止的周期性摆动与震荡。

    (2) 不可约性 (Irreducible)

  • 条件与定义:在状态转移图(Transition Graph)中,任意状态 \(i\) 与任意状态 \(j\) 之间,都存在一条转移概率严格大于零的可达路径(Path)。
  • 整个状态空间是一个全连通整体,不存在任何无法逃离的“陷阱区域”或隔离孤岛。

    2. 马尔可夫链遍历性主定理 (The Equilibrium Theorem)

    (1) Theorem

    若一个具有有限状态数(\(K < \infty\))的一阶平稳马尔可夫链同时满足不可约性与非周期性,则:

    1. 极限分布必定存在:\(P_\infty = \lim_{t \to \infty} P_{\text{init}} \cdot \Phi^t\) 必收敛。
    2. 极限分布即为平稳分布:极限分布完全满足平稳方程 \(P_\infty \cdot \Phi = P_\infty\)
    3. 平稳分布具备唯一性:整个系统存在且仅存在一个唯一的平稳分布 \(P_{\text{inv}}\)。
    4. 完全独立于初始状态:收敛结果与初始分布 \(P_{\text{init}}\) 的选择完全无关(无论系统从何处出发,最终都会到达相同的平稳状态)。

      3. 核心

    5. “无记忆性:
    • 不可约与非周期性保证了系统随着时间演化,会完全“磨灭”初始条件 \(P_{\text{init}}\) 的痕迹。 2. MCMC 采样的理论保障:
    • 只要我们构建的采样转移核满足不可约性与非周期性,无论初始随机样本选在何处,采样序列最终都会精确收敛至目标分布 \(P_{\text{inv}}\)。

      遍历性条件

      缺乏不可约性或缺乏非周期性,马尔可夫链在演化时的特征

      1. 条件一:不可约性(Irreducibility)—— 解决“平稳分布不唯一”问题

      (1) 反例构造(图示:分叉吸收链)

      考虑包含 3 个状态的马尔可夫链:状态 1 可以单向转移至状态 2 或状态 3,而状态 2 和状态 3 分别只有自我自环(如状态 2 只能留在状态 2,状态 3 只能留在状态 3)。

      (2) 平稳分布多解(Multiple Equilibria)

  • 在该链中,\(P = (0, 1, 0)\) 与 \(P' = (0, 0, 1)\) 均完全满足平稳方程 \(P \Phi = P\)。
  • 系统最终收敛到哪个平衡分布,完全取决于初始状态(如果初始在状态 2,就永久卡在 \(P\);如果初始在状态 3,就卡在 \(P'\);若从状态 1 出发,取决于第 1 步的随机选择)。

    2. 条件二:非周期性(Aperiodicity)—— 解决“极限分布不存在”问题

    (1) 反例构造(图示:二元交替震荡链)

    考虑包含 2 个状态的二部图马尔可夫链:状态 0 只能 100% 转移至状态 1,状态 1 只能 100% 转移至状态 0(即 \(0 \leftrightarrow 1\))。

    (2) 极限不存在

  • 在实数数列中,类似序列 \((-1)^n\) 发生永恒震荡而无极限。
  • 若系统初始处于状态 0,则状态 0 只能在偶数步到达,状态 1 只能在奇数步到达。
  • 边缘分布 \(P_t\) 会在 \(P_{\text{even}} = (1, 0)\) 和 \(P_{\text{odd}} = (0, 1)\) 之间永无止境地交替摆动,导致 \(t \to \infty\) 时极限分布 \(\lim_{t \to \infty} P_t\) 不存在

    3. 核心

  • 不可约性从空间上清除了分割孤岛与吸收陷阱,保证了平稳分布的唯一性;
  • 非周期性从时间上破除了固定的节奏震荡,保证了极限演化的存在性(收敛性)

Perron-Frobenius定理与转移矩阵的谱性质

不可约且非周期的转移矩阵 \(\Phi\) 一定收敛到唯一的平稳分布

定理内容

(1) 通用非负矩阵定理表述

设 \(A\) 为一个 \(K \times K\) 的非负矩阵(所有元素 \(A_{ij} \ge 0\)),定义其谱半径(Spectral Radius)为最大特征值模长 \(\rho(A) := \max_j \vert{}\lambda_j\vert{}\)。 若存在某个正整数 \(m \in \mathbb{N}\),使得矩阵幂次 \(A^m\) 的所有元素均严格大于零,Strictly Positive,则:

  1. 主特征值存在:谱半径 \(\rho(A)\) 本身就是 \(A\) 的一个特征值(即主特征值 \(\lambda_1 = \rho(A)\)),且所有其他特征值均严格小于主特征值:\(\vert{}\lambda\vert{} < \rho(A)\)。
  2. 特征向量严格正性与唯一性:对应于主特征值 \(\rho(A)\) 的左、右特征向量在缩放意义下是唯一的,且可以选定使其所有分量均严格为正数。

    (2) 转移矩阵 \(\Phi\) 的谱性质映射

    将定理应用于马尔可夫链的转移矩阵 \(A = \Phi\):

    • 行和归一化:由于转移矩阵的每一行概率和为 1,满足 \(\Phi \mathbf{1} = \mathbf{1}\)(其中 \(\mathbf{1}\) 为全 1 列向量),因此特征值 \(\lambda = 1\) 一定存在。同时特征值模长绝不超过 1,故谱半径 \(\rho(\Phi) = 1\)。
    • 条件对应:马尔可夫链满足“不可约且非周期”完全等价于“存在某个 \(m\) 使得 \(\Phi^m\) 元素全正”。因此主特征值 \(\lambda_1 = 1\) 唯一,其余所有特征值均满足 \(\vert{}\lambda_j\vert{} < 1\)。

      2. 特征向量基底 (When Do Eigenvectors Form a Basis?)

  3. 不同特征值构成基底: 若转移矩阵 \(\Phi\) 的 \(K\) 个特征值互不相同,则必存在由 \(K\) 个特征向量构成的线性空间基底。
  4. 细致平衡条件(Detailed Balance): 若马尔可夫链满足细致平衡条件(后续将在 MCMC 章节深入探讨),则转移矩阵可相似对角化,必定存在一组特征向量基底。 (注:若存在重特征值,通常也可借由若尔当标准型 Jordan Normal Form 导出相同收敛结论,但在本笔记中不作展开)。

    3. 核心

    • 主特征值 \(\lambda_1 = 1\) 对应的左特征向量归一化后,恰好就是系统唯一的平稳分布 \(P_{\text{inv}}\)(满足 \(P_{\text{inv}} \Phi = 1 \cdot P_{\text{inv}}\))。
    • 谱隙(Spectral Gap)控制收敛速率: 第二大特征值的模长 \(\vert{}\lambda_2\vert{}\) 决定了系统从任意初始状态向平稳分布衰减收敛的速度。

边缘分布收敛性的谱展开 Convergence Proof via Eigenvalue Spectrum Expansion

借助线性代数中的特征向量空间分解(Spectral Decomposition),推导时刻 \(t\) 的状态边缘分布 \(P_t = P_{\text{init}} \Phi^t\) 是如何随着时间指数级收敛至唯一平稳分布 \(P_{\text{inv}}\) 的,并给出收敛速率的代数解释。

1. 谱分解与收敛过程

(1) 初始分布在左特征向量基底下的展开

假设转移矩阵 \(\Phi\) 的 \(K\) 个特征向量构成状态空间的一组完整基底。我们将初始概率分布向量 \(P_{\text{init}}\) 按照 \(\Phi\) 的左特征向量 \(\xi_1, \xi_2, \dots, \xi_K\) 进行线性组合展开: \(P_{\text{init}} = \sum_{j=1}^K c_j \xi_j\)

  • 其中主特征值 \(\lambda_1 = 1\) 对应的左特征向量归一化后恰好就是平稳分布 \(\xi_1 = P_{\text{inv}}\)。
  • 对等式两端向量元素求和,利用概率分布归一化条件 \(\sum_k P_{\text{init}}(k) = 1\) 以及其余特征向量对应概率差值模式(分量和为 0),可得主系数 \(c_1 = 1\)。

    (2) 矩阵幂次作用与时间演化

    将 \(t\) 步演化公式 \(P_t = P_{\text{init}} \Phi^t\) 代入特征向量展开式中(利用左特征向量性质 \(\xi_j \Phi = \lambda_j \xi_j \implies \xi_j \Phi^t = \lambda_j^t \xi_j\)):\(\begin{aligned} P_t = P_{\text{init}} \Phi^t &= \left( \sum_{j=1}^K c_j \xi_j \right) \Phi^t = \sum_{j=1}^K c_j \lambda_j^t \xi_j \\ &= 1 \cdot (1)^t P_{\text{inv}} + \sum_{j=2}^K c_j \lambda_j^t \xi_j = P_{\text{inv}} + \sum_{j=2}^K c_j \lambda_j^t \xi_j \end{aligned}\)

    (3) 取极限 \(t \to \infty\) 导出收敛

    由于马尔可夫链满足不可约与非周期性,根据佩隆-弗罗贝尼乌斯定理,对于所有 \(j \ge 2\),特征值模长均满足 \(\vert{}\lambda_j\vert{} < 1\)。因此当时间 \(t \to \infty\) 时,高阶几何级数项全部指数级衰减归零: \(\lim_{t \to \infty} \lambda_j^t = 0 \quad (\forall j \ge 2) \implies \lim_{t \to \infty} P_t = P_{\text{inv}}\)

    2. 收敛速率与反例谱解释 (Convergence Rate & Spectral Insights)

    (1) 收敛速率与谱隙 (Spectral Gap)

  • 误差衰减阶数:边缘分布与平稳分布之间的偏差 \(\Vert{}P_t - P_{\text{inv}}\Vert{}\),其衰减速度由模长第二大的特征值 \(\lambda_2\) 占主导:\(\Vert{}P_t - P_{\text{inv}}\Vert{} = \mathcal{O}\left( \vert{}\lambda_2\vert{}^t \right)\)
  • 谱隙定义:定义 \(\gamma = 1 - \vert{}\lambda_2\vert{}\) 为转移矩阵的谱隙(Spectral Gap)。谱隙越大(即 \(\vert{}\lambda_2\vert{}\) 越小),误差衰减越快,马尔可夫链达到平稳状态的混合时间(Mixing Time)就越短

    (2) 与传统对称矩阵幂迭代法(Power Method)的对比

  • 在普通矩阵幂迭代 \(A^t v\) 中,通常只有向量的方向会收敛到主特征向量,向量的模长可能会爆炸或衰减。
  • 但对马尔可夫转移矩阵而言,由于 \(\lambda_1 \equiv 1\) 恒成立且每行概率归一,概率向量的总质量(求和为 1)在演化过程中被严格守恒,\(P_t\) 本身直接精准收敛于真实的概率向量 \(P_{\text{inv}}\)。

    (3) 条件失效时的谱视角剖析

    1. 周期链(Periodic Chain):存在模长等于 1 的复数特征值或 \(\lambda = -1\)。这导致 \((-1)^t\) 或震荡项永远无法衰减归零,从而破坏了极限的存在性。
    2. 可约链(Reducible Chain):主特征值 \(\lambda = 1\) 的重数大于 1(存在多个独立的主特征向量)。收敛结果由初始展开系数 \(c_1^{(1)}, c_1^{(2)}\) 共同决定,从而丢失了平稳分布的唯一性。

平稳分布的数值计算

将前述解析理论落地为计算机可执行的算法——幂法(Power Method)

1. 幂法算法流程 (The Power Method)

若马尔可夫链满足不可约性与非周期性,由于其极限分布必定等于平稳分布(\(\lim_{t \to \infty} P_t = P_\infty = P_{\text{inv}}\)),我们可以直接通过反复迭代矩阵乘法来数值逼近平稳分布:

  1. 初始化 (Initialization):选择任意合法的概率分布向量 \(P_{\text{init}}\) 作为起始点(例如最简单的均匀分布 \(P_{\text{init}} = (\frac{1}{K}, \dots, \frac{1}{K})\))。
  2. 迭代推演 (Iterative Step):交替执行向量-矩阵乘法,计算下一步的边缘分布:\(P_{t+1} = P_t \cdot \Phi\)
  3. 收敛检测与终止条件 (Termination Criterion):计算相邻两次迭代分布之间的范数距离,当变动量小于预设极小门限 \(\tau\) 时停止迭代:\(\Vert{}P_{t+1} - P_t\Vert{} < \tau\)

    2. 谱结构视角 (Eigenstructure Analysis)

    (1) 特征值 1 与不变性

    平稳分布的代数条件 \(P_{\text{inv}} = P_{\text{inv}} \cdot \Phi\) 在线性代数中意味着:\(P_{\text{inv}}\) 是转移矩阵 \(\Phi\) 关于特征值 \(\lambda_1 = 1\) 的左特征向量(Left Eigenvector)。

    (2) 主特征值的唯一性

    佩隆-弗罗贝尼乌斯定理保障了只要 \(\Phi\) 不可约且非周期,\(\lambda_1 = 1\) 就是模长严格最大的主特征值,且没有任何其他特征值满足 \(\vert{}\lambda\vert{} = 1\)。

    (3) 谱隙(Spectral Gap)与收敛速度

    • 幂法迭代本质上是用矩阵的幂次作用不断“放大”主特征向量成分,同时“压制”其他次要特征向量成分。
    • 算法收敛到平稳分布的速度,严格取决于主特征值 \(\lambda_1 = 1\) 与第二大特征值模长 \(\vert{}\lambda_2\vert{}\) 之间的比率(即谱隙 Spectral Gap)。
    • \(\vert{}\lambda_2\vert{}\) 越接近 0,谱隙越宽,幂法收敛就越快;若 \(\vert{}\lambda_2\vert{}\) 非常接近 1,算法收敛会非常缓慢。

      3. 核心 Insight

  4. 黑盒可计算性: 无需解复杂的方程组,只需重复执行最简单的“向量 \(\times\) 矩阵”乘法操作,就能自动收敛到复杂马尔可夫链的平稳分布。
  5. 连接理论与工程(PageRank 的基石): 幂法是处理超级大规模图结构(如包含几十亿网页的互联网链接图)时唯一可行的平稳分布计算手段。

    Web 图结构与Random Walk

    1. 网页图结构与邻接矩阵 (Web Graph Representation)

    (1) 图论表达 (Graph Formulation)

    互联网的所有网页及其超链接可以天然地构建为一个大型有向图(Directed Graph \(G\)):

    • 节点(Vertices):每个节点代表互联网上的一个网页,总节点数为网页总数 \(K\)。
    • 有向边(Directed Edges):如果网页 \(i\) 包含指向网页 \(j\) 的超链接,则存在一条从节点 \(i\) 指向节点 \(j\) 的有向边 \(i \to j\)。

      (2) 邻接矩阵(Adjacency Matrix \(A\))

      网页图的拓扑结构由一个 \(K \times K\) 的 0-1 邻接矩阵 \(A\) 唯一刻画:

\(A_{ij} = \begin{cases} 1, & \text{若网页 } i \text{ 包含指向网页 } j \text{ 的超链接} \\ 0, & \text{其它} \end{cases}\)

2. 网页图上的简单随机游走 (Simple Random Walk)

假设一个“随机上网者(Random Surfer)”在互联网网页之间随机浏览点击,这构成了定义在网页节点集合上的马尔可夫链:

(1) 初始分布 \(P_{\text{init}}\)

上网者随机挑选任意一个网页作为起始页,即初始概率分布为均匀分布: \(P_{\text{init}} = \left( \frac{1}{K}, \frac{1}{K}, \dots, \frac{1}{K} \right)\)

(2) 转移概率 \(\phi(j \mid i)\)

在时刻 \(t-1\) 处于网页 \(i\) 时,上网者从网页 \(i\) 包含的所有出链(Out-links)中等概率随机挑选一条点击跳转。 记 \(d_i^{\text{out}}\) 为网页 \(i\) 的出度(即网页 \(i\) 拥有的出链接总数),则条件转移概率为: \(\phi(j \mid i) = \begin{cases} \frac{1}{d_i^{\text{out}}}, & \text{若网页 } i \text{ 存在指向网页 } j \text{ 的链接} \\ 0, & \text{其它} \end{cases}\) 这所定义的随机过程被称为有向图 \(G\) 上的简单随机游走(Simple Random Walk)。

3. PageRank 算法

(1) 算法核心思想

  • PageRank 算法的代数本质,就是计算该简单随机游走马尔可夫链的极限/平稳分布 \(P_\infty\)。
  • 最终收敛的平稳分布向量 \(P_\infty = (P_\infty(1), P_\infty(2), \dots, P_\infty(K))\) 中,每个分量 \(P_\infty(v)\) 直接作为网页 \(v\) 的权威度/重要性得分(PageRank Score)。

    (2) 物理意义

网页 \(v\) 的平稳概率 \(P_\infty(v)\) 代表了一个无限长时间游走的随机上网者,在任意时刻停留在网页 \(v\) 的长期概率。该概率越高,说明该网页被访问的频次越高,网页价值与权威性越大。

4. 核心

  1. 结构决定重要性: PageRank 完全摆脱了对网页文本内容的依赖,纯粹利用马尔可夫链在图拓扑结构上的平稳分布来评价节点权威度。
  2. 计算挑战的前瞻: 实际网页图中的转移矩阵 \(T\)(由 \(d_i^{\text{out}}\) 归一化得到)往往不满足不可约性(例如存在没有出链的“死胡同/吸收节点”悬挂页),这会导致极限分布不存在或退化。

    PageRank

    1. 搜索引擎面临的挑战与数据局限 (Problem & Available Data)

    (1) 查询匹配与排序难题 (Query Matching)

    • 搜索引擎的第一步是找出所有包含用户关键词的网页,这一匹配集合往往包含数千万甚至数亿个页面。
    • 搜索结果是否有用的关键,在于能否把“最好、最权威”的网页筛选出来并排在最前面。

      (2) 数据可获得性的物理限制 (Available Data)

    • 可获数据:网络爬虫(Web Crawler)可以轻而易举地爬取并重建整个互联网的超链接拓扑结构(即知道有哪些网页,以及网页之间谁链接了谁)。
    • 不可获数据:搜索引擎在后台无法直接测量每一个网页的真实点击流量,也无法直接统计某个链接实际被用户点击了多少次。

      (3) PageRank 的代理指标逻辑 (Proxies for Quality)

      PageRank 通过双重“代理指标(Proxy)”巧妙避开了无法直接测量真实流量的难题

  3. 用入链接(Incoming Links)的数量与质量作为网页“受欢迎程度(Popularity)”的代理指标。
  4. 用网页的“受欢迎程度”作为网页“内容质量与实用性(Quality / Usefulness)”的代理指标。

    2. 权威度的层级递归与随机上网者模型 (Recursive Score & Random Surfer)

    (1) 递归加权机制(从 \(P_1\) 到 \(P_\infty\))

    • \(P_1\) 步推演:只衡量一个网页被多少其他网页直接链接(即粗糙的入度统计)。
    • \(P_2\) 步推演:不仅看入链数量,还根据“指向该网页的那些源网页本身被链接的频次”进行加权。来自高权威网页的推荐链接,权重远高于来自边缘无名网页的链接。
    • \(P_\infty\) 极限推演:随着时间步 \(t \to \infty\),权威度顺着整个互联网的超链接网络无限次流动与传递,最终达到全局自洽的稳定平衡。

      (2) “随机上网者”物理模型 (Random Surfer Interpretation)

    • PageRank 论文将平稳概率 \(P_\infty(v)\) 直观解释为:一个漫无目的的“随机上网者(Random Web Surfer)”,在互联网上沿着超链接连续随机点击极长时间后,最终停留在网页 \(v\) 的概率。
    • 借助遍历定理,只要马尔可夫链收敛,上网者从哪一个网页开始上网完全不影响最终的平稳概率值 \(P_\infty(v)\)。

      3. 核心

  5. 加权民主投票(Democratic Voting with Trust): 每一个超链接本质上都是一张“推荐票”。PageRank 的精髓在于“并非票票平等”——越权威的网页,其投出的推荐票价值越高。
  6. 局部无序导出的全局有序: 单个用户在局部网页上的盲目随机跳转(局部转移概率),在无限时间尺度下,被马尔可夫链的平稳分布转化为了刻画整个互联网知识图谱结构的全局权威度阶梯。

1. 朴素随机游走矩阵的缺陷 (Failure of Naive Random Walk)

(1) 朴素转移矩阵 \(T\)

网页图上的朴素单步转移矩阵 \(T\) 定义为:

\(T_{ij} := \begin{cases} \frac{1}{d_i^{\text{out}}}, & \text{若网页 } i \text{ 指向网页 } j \\ 0, & \text{其它} \end{cases}\) 其中 \(d_i^{\text{out}}\) 为网页 \(i\) 的出度(出链接数)。

(2) 缺陷: 可约性与悬挂页 (Reducibility & Dead Ends)

  • 实际互联网并非全连通图,存在大量没有出链接的网页(悬挂页 Dead Ends / Sink Nodes),或者陷入后无法逃离的封闭回路(Spider Traps)。
  • 这导致朴素转移矩阵 \(T\) 不满足不可约性(Not Irreducible)。根据第 146–147 页定理,这将导致平稳分布不存在、不唯一,或者概率质量被陷阱节点吸干归零。

    2. PageRank 正则化转移矩阵 (The Regularized Transition Matrix)

    为了强制满足遍历性定理,PageRank 对转移矩阵进行了凸组合正则化(Convex Regularization):

\(\Phi_{ij} := (1 - \alpha) T_{ij} + \frac{\alpha}{K}\) 其中 \(K\) 为网页总数,\(\alpha \in (0, 1)\) 为阻尼因子/随机跳转概率(常取 \(\alpha \approx 0.15\))。

(1) 双重随机行为的物理意义

正则化后的上网者行为分为两类组合:

  1. 以 \(1 - \alpha\) 的概率:继续沿着当前网页的超链接随机点击跳转(局部游走)。
  2. 以 \(\alpha\) 的概率:感到厌倦,直接在浏览器地址栏随机输入网址,以 \(\frac{1}{K}\) 的均匀概率瞬间传送(Teleport)到全网任意一个网页。

    (2) 理论保证 (Theoretical Guarantees)

    由于任意网页 \(i\) 到任意网页 \(j\) 的转移概率均满足 \(\Phi_{ij} \ge \frac{\alpha}{K} > 0\),正则化转移矩阵 \(\Phi\) 的所有元素均严格大于零

    • 严格不可约(Strictly Irreducible):任意两个网页之间均可单步直接到达。
    • 严格非周期(Strictly Aperiodic):对角线元素 \(\Phi_{ii} > 0\)(存在自我传送回路)。
    • 结论:佩隆-弗罗贝尼乌斯定理完全成立,确保存在唯一且收敛的平稳权威度分布 \(P_\infty\)!

      3. 计算

      (1) 幂法迭代与增量更新 (Incremental Re-running)

    • 利用幂法迭代 \(P_{t+1} = P_t \cdot \Phi\) 进行数值计算。
    • 由于互联网拓扑结构是动态变化的,Google 论文提出可以每隔几天重新运行一次幂法,并直接以几天前算出的平稳分布作为新的初始分布 \(P_{\text{init}}\)。由于初始向量已经极度接近真实平稳点,算法可以在极少数次迭代内迅速重新收敛。

      (2) 实证案例分析 (500 网页子图案例)

    • 邻接矩阵稀疏性:500 个以 Harvard 主页为根节点的网页邻接矩阵显示出极高的稀疏性与块状聚集结构。
    • 幂律长尾分布:计算出的平稳分布 \(P_\infty\) 展现出强烈的尖峰(Power-Law Spike),少数核心枢纽网页占据了极高的平稳概率,而绝大多数边缘网页的得分极低。

Latent Variable Models for Time Series