12. 不完整观测的学习

上一章我们讨论了完整观测数据集的情况下有向图和无向图的参数学习方法， 所谓完成观测数据是指图中的所有变量都能观测到，即观测集中每条观测样本都包含了图中所有变量的观测值。 但有些时候，我们是无法观测到图中所有的变量的，观测样本数据只包含图中部分变量的观测值， 这时我们称为不完整观测(Partial Observations)。本章节我们讨论在不完整观测的情况下，图模型的参数学习方法。

12.1. 隐变量

我们已经知道通常模型参数估计的方法是使用极大似然估计，似然函数的含义是观测数据的概率。 假设模型中变量集合是 \(X=\{X_1,\dots,X_M\}\) ， 模型的参数集合是 \(\theta=\{\theta_1,\dots,\theta_K \}\) ，模型的联合概率分布记作 \(P(X;\theta)=P(X_1,\dots,X_M;\theta)\) ， 我们知道无论是有向图、无向图还是因子图，模型的联合概率分布都是可以分解成多个因子函数的乘积形式的

(12.1.2)\[P(X;\theta)=P(X_1,\dots,X_M;\theta)=\prod_{c \in C} \psi_c (X_c;\theta_c)\]

假设模型独立同分布的观测样本集是 \(\mathcal{D}=\{ X^{(1)},\ldots,X^{(N)} \}\) ，上标表示样本编号，此观测数据的对数似然函数为：

(12.1.3)\[ \begin{align}\begin{aligned}\ell(\theta;\mathcal{D}) &= \ln P(\mathcal{D};\theta)\\&= \ln\prod_{i=1}^N P(X^{i};\theta)\\&= \sum_{i=1}^N \ln P(X^{i};\theta)\\&= \sum_{i=1}^N \ln\prod_{c \in C} \psi_c (X_c;\theta_c)\\&= \sum_{i=1}^N \sum_{c \in C} \ln \psi_c (X_c;\theta_c)\end{aligned}\end{align} \]

在这个过程中利用对数函数的性质，把对数符号里面的乘法(连乘)转变成对数符号外面的加法(求和)， 这样对数似然函数就拆解成很多因子函数的的对数的加和， 这时有两个特点：

  1. 每个因子函数的参数 \(\theta_c\) 只出现在其中一个子项中。

  2. 各个因子函数之间是加法。

我们通过极大化对数似然函数 \(\ell(\theta;\mathcal{D})\) 来求解参数，这时需要求解每个参数的偏导数， 而根据求偏导的规则，在满足上面两个特点的时，参数之间的偏导数是互不相关的，也就一个每个参数的偏导数不包含其它参数， 这使得极大似然求解称为可能。

提示

如果参数的偏导数中还包含其它参数，那么将使得解析解或者迭代法都无法实现。

然而在有些情形下观测数据不包含模型的全部变量，模型中的部分变量无法观测到。 我们把模型中无法观测到的变量称为 隐变量 或者 潜在变量(Latent variable)。 潜变量是不能直接观测到的, 包含潜变量的模型称为 潜变量模型 (latent variable models, LVM)。 此时可以把模型中的变量分为两类，一类是可以观测（有观测样本）到的变量集合，称为 可观测变量 或 显变量， 用符号 \(X\) 表示； 另一类是不可观测（没有观测样本）到的变量集合，称为 不可观测变量 或 隐变量，用符号 \(Z\) 表示。 注意，这里 \(X\) 和 \(Z\) 分别表示 多个变量的集合，因为一个模型中变量可以有许多个。 完整的图模型联合概率分布记作 \(P(X,Z;\theta)\) 。 依据前面章节的知识，模型中观测变量集合 \(X\) 的边缘概率分布 \(P(X;\theta)\) 需要通过边际化的方法的到

(12.1.4)\[P(X;\theta)= \sum_{z} P(X,Z;\theta)\]

观测数据的对数似然函数也就变成了如下形式：

(12.1.5)\[ \begin{align}\begin{aligned}\ell(\theta;\mathcal{D}) &= \ln \prod_{i=1}^N P(X^{i};\theta)\\&= \ln \prod_{i=1}^N \sum_{z} P(X^{i},Z);\theta)\\&= \sum_{i=1}^N \ln \sum_{z} P(X^{i},Z;\theta)\end{aligned}\end{align} \]

发现没有，对数操作里面有求和符号 \(\sum_{z}\) ，这就导致 \(\ln\) 里面的内容无法再继续拆解成独立的子项。 这时再对参数求偏导将变得十分困难。所以，我们需要解决这个求和符号的问题。

提示

如果隐变量 \(Z\) 是连续变量，只需把求和符号换成积分即可，结论不变。

鉴于此，如果随机变量 \(X,Z\) 都是可观测的，则对数似然你函数记作 \(\ell_c(\theta;X,Z)=\ln P(X,Z;\theta)\) ，我们称其为 完整数据对数似然(complete data log-likelihood) 。 反之，如果模型包含不可观测的隐变量集合 \(Z\) ，则对数似然函数记作 \(\ell(\theta;X)=\ln \sum_{z} P(X,z;\theta)\) ，我们能称其为 不完整数据对数似然(incomplete data log-likelihood)。 隐变量的出现，给模型的参数估计带来了极大的困难。

12.2. 期望最大化算法(EM)

不完整数据对数似然函数中，对数操作里面含有求和(或者积分)导致无法进行拆解， 也就无法很好的通过偏导数进行极大化对数似然函数求解。有一个算法可以解决这个问题， 那就是期望最大化算法(Expectation-Maximization,EM)。 这个算法的核心就是利用Jensen不等式为对数似然函数找到了一个下界函数， 通过极大化下界函数求解参数值。 首先，我们回顾一下Jensen不等式定理。

定理1 Jensen不等式 :

当 f 是一个下凸函数，并且Y是一个随机变量时，有:

(12.2.10)\[E[f(Y)] \ge f(E[Y])\]

当 f 是一个上凹函数，并且Y是一个随机变量时，有:

(12.2.11)\[E[f(Y)] \le f(E[Y])\]

Jensen不等式是一个关于期望的不等式运算， 观察下不完整数据（包含隐变量的）对数似然函数（公式(12.1.5)）， 其对数里面的存在一个求和符号， 并且求和符号是关于隐变量集合 \(Z\) 的， 可以通过引入一个隐变量 \(Z\) 的概率分布函数，把这个求和操作转成一个求期望的操作， 然后就可以利用上Jensen不等式的性质。

下界函数

定义一个隐变量 \(Z\) 的概率密度（质量）函数，记作 \(q(Z)\) ，这个函数具体形式先不讨论，稍后再做讨论。 注意 \(q(Z)\) 是与观测样本无关的，对所有样本都是相同的，即与 \(i\) 无关的。 接下来，通过在 公式(12.1.5) 中引入 \(q(Z)\) 对其进行一些变换。 为了符号的简洁，我们忽略对所有观测样本的求和操作，暂时只关注一条样本的对数似然。

(12.2.12)\[ \begin{align}\begin{aligned}\ell(\theta;X^{i}) &= \ln P(X^{i};\theta)\\ &= \ln \sum_{z} P(X^{i},Z;\theta)\\&= \ln \sum_{z} q(Z) \frac{P(X^{i},Z;\theta)}{q(Z)}\\&= \ln\mathbb{E}_{q(Z) } \left [ \frac{P(X^{i},Z;\theta)}{q(Z)} \right ]\\& \ge \mathbb{E}_{q(Z) } \ln\left [ \frac{P(X^{i},Z;\theta)}{q(Z)} \right ] \ \ \ \text{根据Jensen不等式}\\ &= \sum_{z} q(Z) \ln \left [ \frac{P(X^{i},Z;\theta)}{q(Z)} \right ]\\&= \left [ \sum_{z} q(Z) \ln P(X^{i},Z;\theta) - \sum_{z} q(Z) \ln q(Z) \right ]\\&\triangleq \mathcal{L}(q,\theta)\end{aligned}\end{align} \]

利用 Jensen 不等式的性质，可以为对数似然函数 \(\ell(\theta;X^{i})\) 找到一个下界函数 ，把这个下界函数记作 \(\mathcal{L}(q,\theta)\)。

(12.2.13)\[\mathcal{L}(q,\theta) = \sum_{z} q(Z) \ln P(X^{i},Z;\theta) - \sum_{z} q(Z) \ln q(Z)\]

由于观测数据的对数似然函数也被称作 证据(evidence)， 因此这个下界函数又被称为 证据下界（evidence lower bound,ELBO） 。这个下界函数的另一个常用名称是 负变分自由能（variational free energy）。

观察 公式(12.2.13)， 下界函数分为两部分，第一部分 \(\sum_{z} q(Z) \ln P(X^{i},Z;\theta)\) 可以看做完整数据对数似然（模型联合概率）的期望。 第二部分 \(\sum_{z} q(Z) \ln q(Z)\) 是 \(q(Z)\) 的 熵，记作 \(H(q)\) 。为了令公式更加简洁， 证据下界函数可以改写成如下形式

(12.2.14)\[ \begin{align}\begin{aligned}\mathcal{L}(q,\theta) &= \sum_{z} q(Z) \ln P(X^{i},Z;\theta) - \sum_{z} q(Z) \ln q(Z)\\&= \mathbb{E}_{z \sim q} [ \ln P(X^{i},Z;\theta) ] - \mathbb{E}_{z \sim q}[ \ln q(Z) ]\\&= \mathbb{E}_{z \sim q} [ \ell(\theta;X^{i},Z) ] - H(q(Z))\end{aligned}\end{align} \]

证据下界 \(\mathcal{L}(q,\theta)\) 是观测对数似然函数 \(\ell(\theta;\mathcal{D})\) 的一个下界函数，意味着有 \(\mathcal{L}(q,\theta) \le \ell(\theta;\mathcal{D})\) 一直成立，并且与 \(q(Z)\) 的具体形式无关， 换句话说，无论 \(q(Z)\) 是什么，这个不等式都成立。

此时，我们找到了对数似然函数 的一个下界函数 \(\mathcal{L}(q,\theta)\) ，并且 这个下界函数中对数内已经没有了求和(积分)符号，可以方便的求导和极大化 。 那么我们是不是可以通过极大化这个下界函数 \(\mathcal{L}(q,\theta)\) 去求解模型的原始参数值呢？

观察 公式(12.2.14)， 下界函数中含有联合概率分布 \(P(X,Z;\theta)\) ，根据链式法则，有两种分解方式。

(12.2.15)\[P(X,Z;\theta) = P(Z) P(X|Z)=P(X)P(Z|X)\]

其中 \(P(Z)\) 表示 \(Z\) 的先验概率分布，\(P(Z|X)\) 表示其后验概率分布。 接下来，分别用分解两种方式变换下界函数。

第一种形式，使用 \(Z\) 的先验分布 \(P(Z)\) :

(12.2.16)\[ \begin{align}\begin{aligned}\mathcal{L}(q,\theta) &= \mathbb{E}_{z \sim q} [ \ln P(X^{i},Z;\theta) ] - \mathbb{E}_{z \sim q}[ \ln q(Z))]\\&= \mathbb{E}_{z \sim q} [ \ln P(Z) + \ln P(X^{i}|Z;\theta) ] - \mathbb{E}_{z \sim q}[ \ln q(Z))]\\&= \mathbb{E}_{z \sim q} [ \ln P(Z) ] + \mathbb{E}_{z \sim q} [\ln P(X^{i}|Z;\theta) ] - \mathbb{E}_{z \sim q}[ \ln q(Z))]\\&= \mathbb{E}_{z \sim q} [\ln P(X^{i}|Z;\theta) ] + \underbrace{ \mathbb{E}_{z \sim q} [ \ln P(Z) ] - \mathbb{E}_{z \sim q}[ \ln q(Z))] }_{\text{KL散度}}\\&= \mathbb{E}_{z \sim q} [\ln P(X^{i}|Z;\theta) ] - \underbrace{ KL(q(Z)||P(Z))}_{q(Z) \text{和先验} P(Z) \text{的KL散度}}\end{aligned}\end{align} \]

第二种形式，使用 \(Z\) 的后验验分布 \(P(Z|X)\) :

(12.2.17)\[ \begin{align}\begin{aligned}\mathcal{L}(q,\theta) &= \mathbb{E}_{z \sim q} [ \ln P(X^{i},Z;\theta) ] - \mathbb{E}_{z \sim q}[ \ln q(Z))]\\&= \mathbb{E}_{z \sim q} \left [ \ln P(X^{i};\theta) + \ln P(Z|X^{i}) \right ] - \mathbb{E}_{z \sim q}[ \ln q(Z))]\\&= \underbrace{\mathbb{E}_{z \sim q} [ \ln P(X^{i};\theta) ]}_{\text{与}z\text{无关，期望符号可以去掉}} + \mathbb{E}_{z \sim q} [\ln P(Z|X^{i}) ] - \mathbb{E}_{z \sim q}[ \ln q(Z))]\\&= \underbrace{\ln P(X^{i};\theta)}_{\text{观测数据对数似然}} + \underbrace{ \mathbb{E}_{z \sim q} [ \ln P(Z|X^{i})) ] - \mathbb{E}_{z \sim q}[ \ln q(Z)] }_{\text{KL散度}}\\&= \underbrace{ \ell(\theta;X^{i}) }_{\text{观测数据对数似然}} - \underbrace{ KL(q(Z)||P(Z|X^{i}))}_{ q(Z) \text{和后验验} P(Z|X) \text{的KL散度}}\end{aligned}\end{align} \]

这里我们重点关注第二种形式，公式(12.2.17) 可以写成

(12.2.18)\[\ell(\theta;X^{i}) = \mathcal{L}(q,\theta) + KL(q(Z)||P(Z|X^{i}))\]

观测数据的对数似然就等于下界函数加上 \(q(Z)\) 与后验 \(P(Z|X)\) 的KL散度， 我们知道KL散度是衡量两个概率分布是否相近的，如果两个概率分布完全一样，则KL散度的值为0。 也就是说如果令 \(q(Z)=P(Z|X^{i})\) 成立，则 \(KL(q(Z)||P(Z|X^{i}))=0\) ，此时就有 \(\ell(\theta;X^{i}) = \mathcal{L}(q,\theta)\) 成立。

到此，我们找到了含有隐变量模型参数估计的一个方法，首先利用观测样本求出隐变量的后验分布 \(q(Z)=P(Z|X)\) ，然后把这个后验分布带入到下界函数 \(\mathcal{L}(q,\theta)\) 中，并且极大化这个函数求解参数， 后验分布 \(P(Z|X)\) 可以利用贝叶斯定理得到，

(12.2.19)\[q(Z)=P(Z|X) = \frac{P(X|Z;\theta) P(Z;\theta) }{ \sum_{z} P(X|Z;\theta) P(Z;\theta)}\]

我们发现计算后验分布 \(q(Z)=P(Z|X)\) 依赖两个条件：

  1. 先验分布 \(P(Z;\theta)\) 及其参数。

  2. 条件概率分布 \(P(X|Z;\theta)\) 及其参数。

因此我们需要给出 \(P(Z;\theta)\) 和 \(P(X|Z;\theta)\) 的分布定义， 至于参数 \(\theta\) 的值，可以用迭代过程中上一轮的参数值，而这这就是EM算法的思想。

EM算法的过程

令符号 \(t\) 表示迭代的轮次，\(t-1\) 表示上一轮的迭代， \(t\) 表示当前轮的迭代。 首先利用上一轮的参数值以及观测数据得到隐变量的后验概率分布，

(12.2.20)\[q(Z^{i}) = P(Z^{i}|X^{i};\theta^{t-1})\]

然后定义一个辅助函数(下界函数) \(Q(\theta,\theta^{t-1})\) ，通过极大化它求解本来的参数 \(\theta^t\) 。

(12.2.21)\[\begin{split}Q(\theta^t,\theta^{t-1}) &= \sum_{i=1}^N \sum_{z} P(Z^{i}|X^{i};\theta^{t-1}) \ln \left [ \frac{P(X^{i},Z^{i};\theta^t)}{P(Z^{i}|X^{i};\theta^{t-1})} \right ]\\ &=\sum_{i=1}^N \sum_{z} P(Z^{i}|X^{i};\theta^{t-1}) \left [ \ln P(X^{i},Z^{i};\theta^t) - \ln {P(Z^{i}|X^{i};\theta^{t-1})} \right ] \\ &= \sum_{i=1}^N \sum_{z} \left [ P(Z^{i}|X^{i};\theta^{t-1}) \ln P(X^{i},Z^{i};\theta^t) \right ] - \underbrace{\sum_{z} \left [ P(Z^{i}|X^{i};\theta^{t-1}) \ln {P(Z|X^{i};\theta^{t-1})} \right ]}_{\text{与参数} \theta^t 无关，可以去掉}\\ &\triangleq \sum_{i=1}^N \sum_{z} P(Z^{i}|X^{i};\theta^{t-1}) \ln P(X^{i},Z^{i};\theta^t)\end{split}\]

这个辅助函数中对数的内部就是模型的联合概率，这个完整数据观测的对数似然函数一样了， 可以方便的进行因子分解后求参数的偏导， 只需要极大化这个辅助函数得到本轮的参数值即可。

(12.2.22)\[\theta^t = \mathop{\arg \max}_{\theta} Q(\theta^t,\theta^{t-1}) = \mathop{\arg \max}_{\theta} \sum_{i=1}^N \sum_{z} P(Z^{i}|X^{i};\theta^{t-1}) \ln P(X^{i},Z^{i};\theta^t)\]

由于极大化的辅助函数是一个关于隐变量后验分布的期望形式，因此被称为期望最大化(Expectation-Maximization)算法，一般简称为EM算法。 最后整理一下算法的执行过程，EM算法是一个迭代式的算法， 每次迭代有两个过程：E(Expectation)步骤和M(Maximization)步骤， 交替的执行这两个过程，知道参数收敛。

初始： 初始化模型的参数，可以选择随机初始化赋值，也可以使用一些复杂的参数初始化方法。
(12.2.23)\[\theta = \theta_0\]
E步骤： 计算隐变量集合 \(Z\) 的后验概率分布，也可以看做是得到 \(Q(\theta^t,\theta^{t-1})\) 辅助函数。
(12.2.24)\[q(Z^{i}) = P(Z^{i}|X^{i};\theta^{t-1})\]
M步骤： 极大化辅助函数 \(Q(\theta^t,\theta^{t-1})\) 得到本轮迭代的参数值。
(12.2.25)\[\theta^t = \mathop{\arg \max}_{\theta} Q(\theta^t,\theta^{t-1}) = \mathop{\arg \max}_{\theta} \sum_{i=1}^N \sum_{z} P(Z^{i}|X^{i};\theta^{t-1}) \ln P(X^{i},Z^{i};\theta^t)\]

这里就和正常的极大似然估计是一样的了，可以通过梯度法得到最优的参数值。

迭代： 交替执行E步骤和M步骤，直到参数收敛。

EM算法有两个特点：

  1. EM算法得到的是局部最优解，不保证得到全局最优，这取决于似然函数是否是凸函数(或者凹函数)。

  2. 通常EM算法前几次迭代收敛较快，在之后收敛速度回急剧下降。

EM算法是一个伟大的发明，它是解决潜变量模型的常用算法，应用十分的广泛。 本章只有算法的理论过程，读者可以直接跳到 第20章 参考一个EM算法应用实例，进一步加深对算法的理解。