8 EM 算法及其推广

#EM #GMM #JensenInequality #GEM #LagrangeMethod

EM 算法用于含有隐变量的概率模型参数的极大似然估计. 它大体上分为

E 步 (Expectation),
M 步 (Maximization).

1 EM 算法的引入

1.1 EM 算法

例子(三硬币模型)

设有硬币 $A, B, C$ . 正面朝上的概率分别为 $π, p, q$ . 进行如下实验: 先抛 $A$ , 正面选 $B$ , 反面选 $C$ , 根据选择的结果抛硬币, 正面记为 $1$ , 反面为 $0$ ; 独立的重复 $n = 10$ 次, 观测结果为 $1, 1, 0, 1, 0, 0, 1, 0, 1, 1.$ (我们无法看到抛硬币的过程, 只能看到结果) 现在要确定 $π, p, q$ .
为此, 将模型写作 $\begin{aligned} P (y | θ) & = \sum_{z} P (y, z | θ) = \sum_{z} P (z | θ) P (y | z, θ) \\ = π p^{y} (1 - p)^{1 - y} + (1 - π) q^{y} (1 - q)^{1 - y}, \end{aligned}$ $z$ 即是隐变量, $θ = (π, p, q)$ 是参数.
将观测数据表示为 $Y = (Y_{1}, \dots, Y_{n})^{T}$ , 未观测数据表示为 $Z = (Z_{1}, \dots, Z_{n})^{T}$ , 则观测数据的似然函数为 $\begin{aligned} P (Y | θ) = & \sum_{Z} P (Z | θ) P (Y | Z, θ) \\ = & \prod_{j = 1}^{n} [π p^{y_{j}} (1 - p)^{1 - y_{j}} (1 - p)^{1 - y_{j}} + (1 - π) q^{y_{j}} (1 - q)^{1 - y_{j}}] . \end{aligned}$ 则极大似然估计为 $\hat{θ} = \arg max_{θ} \log P (Y | θ),$ 只能通过迭代的方法求解. 我们下面直接给出 EM 算法在这里的的表达式:

选取初值 $θ^{(0)} = (π^{(0)}, p^{(0)}, q^{(0)})$ , 设第 $i$ 次迭代得到 $θ^{(i)} = (π^{(0)}, p^{(i)}, q^{(i)})$ . 则在第 $i + 1$ 次,

E 步, 计算 $π^{(i)}, p^{(i)}, q^{(i)}$ 下 $y_{j}$ 来自 $B$ 的概率 $μ_{j}^{(j + 1)} = \frac{π^{(i)} (p^{(i)})^{y_{j}} (1 - p^{(i)})^{1 - y_{j}}}{π^{(i)} (p^{(i)})^{y_{j}} (1 - p^{(i)})^{1 - y_{j}} + (1 - π^{(i)}) (q^{(i)})^{y_{j}} (1 - q^{(i)})^{1 - y_{j}}} .$

M 步, 计算新的估计值 $π^{(i + 1)} = \frac{1}{n} \sum_{j = 1}^{n} μ_{j}^{(i + 1)}, p^{(i + 1)} = \frac{\sum_{j = 1}^{n} μ_{j}^{(i + 1)} y_{j}}{\sum_{j = 1}^{n} μ_{j}^{(i + 1)}}, q^{(i + 1)} = \frac{\sum_{j = 1}^{n} (1 - μ_{j}^{(i + 1)}) y_{j}}{\sum_{j = 1}^{n} (1 - μ_{j}^{(i + 1)})} .$

在上面的例子中, $Y$ 表示观测变量, $Z$ 表示隐变量. $Y, Z$ 连在一起称为完全数据, $Y$ 自己称为不完全数据. 这里 $Y$ 的似然函数是 $P (Y | θ)$ , 对数似然是 $\log P (Y | θ)$ . EM 算法即要求 $L (θ) = \log P (Y | θ)$ 的极大似然估计.

EM算法

输入 $Y, Z, P (Y, Z | θ), P (Z | Y, θ)$
输出模型参数 $θ$

选取初值 $θ^{(0)}$ .
E 步: 在第 $i + 1$ 次迭代, 计算 $\begin{aligned} Q (θ, θ^{(i)}) & = E_{Z} [\log P (Y, Z | θ) | Y, θ^{(i)}] \\ (1.1) & = \sum_{z} \log P (Y, Z | θ) P (Z | Y, θ^{(i)}) . \end{aligned}$
M 步: $\begin{matrix} (1.2) & θ^{i + 1} = \arg max_{θ} Q (θ, θ^{(i)}) . \end{matrix}$
重复 2, 3, 直到收敛.

上面的 $Q (θ, θ^{(i)})$ 是算法核心, 称为** $Q$ 函数**.

算法各步骤的说明

参数的初值可以任意选择, 但是 EM 算法对初值敏感.

尽管 $Q (θ, θ^{(i)})$ 的两个参数分别表示要极大化的参数和当前的估计值, 但实际上是在求 $Q$ 函数的极大值.

后面将证明每次迭代会使似然函数增大或达到局部极值.

体制迭代条件一般为对于较小的 $ε_{1}, ε_{2} > 0$ , $| | θ^{(i + 1)} - θ^{(i)} | | < ϵ_{1} \lor | | Q (θ^{(i + 1)}, θ^{(i)}) - Q (θ^{(i)}, θ^{(i)}) | | < ε_{2} .$

1.2 EM 算法的导出

我们希望极大化观测数据 $Y$ 关于 $θ$ 的对数似然函数 $L (θ) = \log P (Y | θ) = \log \sum_{Z} P (Y, Z | θ) = \log (\sum_{Z} P (Y | Z, θ) P (Z | θ)) .$ 假设经过某种迭代后 $θ$ 的估计值是 $θ^{(i)}$ , 希望新的估计值使得 $L$ 增加, 也即 $L (θ) > L (θ^{(i)})$ . 根据 Jensen不等式, $\log \sum_{j} λ_{j} y_{j} \geq \sum_{j} λ_{j} \log y_{j}$ , 则

\begin{aligned} L (θ) - L (θ^{(i)}) & = \log (\sum_{Z} P (Y | Z, θ) P (Z | θ)) - \log P (Y | θ^{(i)}) \\ \geq \sum_{Z} P (Z | Y, θ^{(i)}) \log \frac{P (Y | Z, θ) P (Z | θ)}{P (Z | Y, θ^{(i)})} - \log P (Y | θ^{(i)}) \\ = \sum_{Z} P (Z | Y, θ^{(i)}) \log \frac{P (Y | Z, θ) P (Z | θ)}{P (Z | Y, θ^{(i)}) P (Y | θ^{(i)})} . \end{aligned}

令 $B (θ, θ^{(i)}) = L (θ^{(i)}) + \sum_{Z} P (Z | Y, θ^{(i)}) \log \frac{P (Y | Z, θ) P (Z | θ)}{P (Z | Y, θ^{(i)}) P (Y | θ^{(i)})} \leq L (θ),$ 且容易知道 $L (θ^{(i)}) = B (θ^{(i)}, θ^{(i)}) .$ 因此任意让 $B (θ, θ^{(i)})$ 增大的 $θ$ 也可以让 $L (θ)$ 增大. 为了让增大尽可能大, 则 $\begin{aligned} θ^{(i + 1)} & = \arg max_{θ} B (θ, θ^{(i)}) \\ = \arg max_{θ} (L (θ^{(i)}) + \sum_{Z} P (Z | Y, θ^{(i)}) \log \frac{P (Y | Z, θ) P (Z | θ)}{P (Z | Y, θ^{(i)}) P (Y | θ^{(i)})}) \\ = \arg max_{θ} (\sum_{Z} P (Z | Y, θ^{(i)}) \log P (Y | Z, θ) P (Z | θ)) \\ = \arg max_{θ} Q (θ, θ^{(i)}) . \end{aligned}$
这与 (1.1),(1,2) 等价.
Pasted image 20241127133756.png|300
从这张图看出, $B (θ, θ^{(i)}), L (θ)$ 在 $θ^{(i)}$ 处相等, 随着 $θ^{(i + 1)}$ 的取值, $L$ 也相应的增大, 此时 $B (θ, θ^{(i + 1)})$ 的图像进行偏移, 进而迭代地找到 $L$ 的极大值点. 从这里也可以看出, EM 算法无法找到全剧最值点.

1.3 EM 算法在无监督学习中的应用

无监督学习的训练集为 ${(x_{1}, \cdot), \dots, (x_{N}, \cdot)}$ , 每个数据点没有对应的输出. 我们可以认为需要学习联合概率分布 $P (X, Y)$ , $X$ 为观测数据, $Y$ 为未观测数据.

2 EM 算法的收敛性

定理 2.1

设 $P (Y | θ)$ 为观测数据的似然函数, EM 算法得到参数序列 ${θ^{(i)}}$ , 则 $P (Y | θ^{(i)})$ 关于 $i$ 单调递增.

定理 2.2

若 $P (Y | θ)$ 有上界, 则 $L (θ^{(i)}) = \log P (Y | θ^{(i)})$ 收敛到某一个 $L^{*}$ .
在 $Q (θ, θ^{'})$ 与 $L (θ)$ 满足一定条件下, EM 算法得到的 $θ^{(i)}$ 的收敛值 $θ^{*}$ 是 $L (θ)$ 的稳定点.

3 EM 算法在 Gauss 混合模型学习的应用

3.1 Gauss 混合模型

Gauss 混合模型

有以下形式的概率分布模型 $\begin{matrix} (3.1) & P (y | θ) = \sum_{k = 1}^{K} α_{k} ϕ (y | θ_{k}) \end{matrix}$ 称为** Gauss 混合模型**(Gaussian mixture model, #GMM )
这里 $α_{k} \geq 0$ 是系数, $\sum_{k = 1}^{K} α_{k} = 1$ ; $θ_{k} = (μ_{k}, σ_{k}^{2})$ , $ϕ (y | θ_{k}) = \frac{1}{\sqrt{2 π} σ_{k}} \exp (- \frac{(y - μ_{k})^{2}}{2 σ_{k}^{2}}) .$ (也即 $Y_{k} \sim N (μ_{k}, σ_{k}^{2})$ .)

注意, 这里的求和的意思是, 观测值依概率 $α_{k}$ 属于第 $k$ 个子模型, 而非把每个模型的密度相加.

3.2 Gauss 混合模型参数估计的 EM 算法

假设观测数据 $y_{1}, \dots, y_{N}$ 由 (3.1) 生成, $θ = (α_{1}, \dots, α_{K}; θ_{1}, \dots, θ_{K})$ .

^ 明确隐变量, 写出完全数据的对数似然函数

$y_{1}, \dots, y_{N}$ 分别是依照概率 $α_{k}$ 来选择第 $k$ 个 Gauss 分布模型 $ϕ (y | θ_{k})$ , 并依此生成 $y_{j}$ . 因此, ${y_{j}}$ 已知, 但是 $y_{j}$ 来自哪个子模型 ( $k$ ) 未知, 用隐变量 $γ_{j k}$ 表示, 即 $γ_{j k} = {\begin{aligned} 1, 第 j 个观测来自第 k 个分模型, \\ 0, else . \end{aligned}$ 是 $0 - 1$ 随机变量. 这样, 完全数据(回顾定义)是 $(y_{j}, γ_{j 1}, \dots, γ_{j K})$ . 于是写出似然函数 $\begin{aligned} P (y, γ | θ) & = \prod_{j = 1}^{N} P (y_{j}, γ_{j 1}, \dots, γ_{j K} | θ) = \prod_{k = 1}^{K} \prod_{j = 1}^{N} [α_{k} ϕ (y_{j} | θ_{k})]^{γ_{j k}} \\ = \prod_{k = 1}^{K} α_{k}^{n_{k}} \prod_{j = 1}^{N} [ϕ (y_{j} | θ_{k})]^{γ_{j k}} = \prod_{k = 1}^{K} α_{k}^{n_{k}} \prod_{j = 1}^{N} {[\frac{1}{\sqrt{2 π} σ_{k}} \exp (- \frac{(y_{j} - μ_{k})^{2}}{2 σ_{k}^{2}})]}^{γ_{j k}}, \end{aligned}$
其中 $n_{k} = \sum_{j = 1}^{N} γ_{j k}, \sum_{k = 1}^{K} n_{k} = N .$ 因此对数似然函数为 $\log P (y, γ | θ) = \sum_{k = 1}^{K} {n_{k} \log α_{k} + \sum_{j = 1}^{N} γ_{j k} [\log (\frac{1}{\sqrt{2 π}}) - \log σ_{k} - \frac{(y_{j} - μ_{k})^{2}}{2 σ_{k}^{2}}]} .$

^ E 步: 确定 $Q$ 函数

\begin{aligned} Q (θ, θ^{(i)}) & = E [\log P (y, γ | θ) | y, θ^{(i)}] \\ = E {\sum_{k = 1}^{K} {n_{k} \log α_{k} + \sum_{j = 1}^{N} γ_{j k} [\log (\frac{1}{\sqrt{2 π}}) - \log σ_{k} - \frac{(y_{j} - μ_{k})^{2}}{2 σ_{k}^{2}}]} | y, θ^{(i)}} \\ = \sum_{k = 1}^{K} {\sum_{j = 1}^{N} (E (γ_{j k} | y, θ^{(i)})) \log α_{k} + \sum_{j = 1}^{N} (E (γ_{j k} | y, θ^{(i)})) [\log (\frac{1}{\sqrt{2 π}}) - \log σ_{k} - \frac{(y_{j} - μ_{k})^{2}}{2 σ_{k}^{2}}]} . \end{aligned}

记 ${\hat{γ}}_{j k} = E (γ_{j k} | y, θ)$ , 则 $\begin{aligned} {\hat{γ}}_{j k} & = E (γ_{j k} | y, θ) = P (γ_{j k} = 1 | y, θ) \\ = \frac{P (γ_{j k} = 1, y_{j} | θ)}{\sum_{k = 1}^{K} P (γ_{j k} = 1, y_{j} | θ)} \\ = \frac{P (y_{j} | γ_{j k} = 1, θ) P (γ_{j k} = 1 | θ)}{\sum_{k = 1}^{K} P (y_{j} | γ_{j k} = 1, θ) P (γ_{j k} = 1 | θ)} \\ = \frac{α_{k} ϕ (y_{j} | θ_{k})}{\sum_{k = 1}^{K} α_{k} ϕ (y_{j} | θ_{k})} . \end{aligned}$
${\hat{γ}}_{j k}$ 是当前模型参数下第 $j$ 个观测数据来自第 $k$ 个分模型的概率, 称为 $k$ 对 $y_{j}$ 的响应度. 将计算结果代入, 得

\begin{matrix} (3.2) & Q (θ, θ^{(i)}) = \sum_{k = 1}^{K} {n_{k} \log α_{k} + \sum_{j = 1}^{N} {\hat{γ}}_{j k} [\log (\frac{1}{\sqrt{2 π}}) - \log σ_{k} - \frac{(y_{j} - μ_{k})^{2}}{2 σ_{k}^{2}}]} . \end{matrix}

^ M 步: 迭代 $θ$

对于 (3.2), 分别对 ${\hat{μ}}_{k}, {\hat{σ}}_{k}^{2}$ 求偏导, 令其为 $0$ 即可; 对于 ${\hat{α}}_{k}$ , 在 $\sum_{k = 1}^{K} α_{k} = 1$ 下求偏导令为 $0$ . 最后的结果如下所示:

Gauss 混合模型参数估计的 EM 算法

输入 $y_{1}, \dots, y_{N}$ , GMM
输出 GMM 的参数

选取参数初始值.
E: 计算分模型 $k$ 对观测数据 $y_{j}$ 的响应度 ${\hat{γ}}_{j k} = \frac{α_{k} ϕ (y_{j} | θ_{k})}{\sum_{k = 1}^{K} α_{k} ϕ (y_{j} | θ_{k})}, 1 \leq j \leq N, 1 \leq k \leq K .$
M: 更新模型参数 ${\hat{μ}}_{k} = \frac{\sum_{j = 1}^{N} {\hat{γ}}_{j k} y_{j}}{\sum_{j = 1}^{N} {\hat{γ}}_{j k}}, {\hat{σ}}_{k}^{2} = \frac{\sum_{j = 1}^{N} {\hat{γ}}_{j k} (y_{j} - μ_{k})^{2}}{\sum_{j = 1}^{N} {\hat{γ}}_{j k}}, {\hat{α}}_{k} = \frac{\sum_{j = 1}^{N} {\hat{γ}}_{j k}}{N}, 1 \leq k \leq K .$
重复 2, 3, 直到收敛.

4 EM 算法的推广

4.1 $F$ 函数的极大-极大算法

F 函数

假设隐变量 $Z$ 的概率分布为 $\tilde{P} (Z)$ , 定义 $\tilde{P}$ 与参数 $θ$ 的函数 $F (\tilde{P}, θ)$ : $\begin{matrix} (4.1) & F (\tilde{P}, θ) = E_{\tilde{P}} [\log P (Y, Z | θ)] + H (\tilde{P}), \end{matrix}$ 称为 $F$ 函数. 这里的 $H (\tilde{P}) = - E_{\tilde{P}} \log \tilde{P} (Z)$ 是熵.

在定义中, 通常假设 $P (Y, Z | θ)$ 是 $θ$ 的连续函数, 因此 $F (\tilde{P}, θ)$ 是 $\tilde{P}, θ$ 的连续函数. $F (\tilde{P}, θ)$ 还有以下重要性质:

引理 4.1

对于固定的 $θ$ , $\exists! \tilde{P_{θ}}$ 可以极大化 $F (\tilde{P}, θ)$ , 此时 ${\tilde{P}}_{θ}$ 由下式给出 $\begin{matrix} (4.2) & {\tilde{P}}_{θ} (Z) = P (Z | Y, θ) . \end{matrix}$ 且 ${\tilde{P}}_{θ}$ 关于 $θ$ 连续.

证明

固定 $θ$ , 引入 Lagrange 乘子 $λ$ , 得到 Lagrange 函数 $L = E_{\tilde{P}} \log P (Y, Z | θ) - E_{\tilde{P}} \log \tilde{P} (Z) + λ (1 - \sum_{Z} \tilde{P} (Z)) .$ 令 $\begin{aligned} 0 = \frac{\partial L}{\partial \tilde{P} (Z)} = \log P (Y, Z | θ) - \log \tilde{P} (Z) - 1 - λ \\ \Rightarrow & \frac{P (Y, Z | θ)}{{\tilde{P}}_{θ} (Z)} = e^{1 + λ} . \end{aligned}$
再由约束条件 $\sum_{Z} {\tilde{P}}_{θ} (Z) = 1$ 得 (4.2).

引理 4.2

若 ${\tilde{P}}_{θ} (Z) = P (Z | Y, θ)$ , 则 $\begin{matrix} (4.3) & F (\tilde{P}, θ) = \log P (Y | θ) . \end{matrix}$

证明

根据 F函数的定义, 有 $\begin{aligned} F (\tilde{P}, θ) & = E_{\tilde{P}} [\log P (Y, Z | θ) - \log \tilde{P} (Z)] \\ = E_{\tilde{P}} \log \frac{P (Y, Z | θ)}{P (Z)} \\ \leq \log E_{\tilde{P}} \frac{P (Y, Z | θ)}{P (Z)} = \log P (Y | θ) . \end{aligned}$
由引理4.1, 这个不等号要取等(因为此时 $\tilde{P}$ 是极大值点).

定理 4.1

$L (θ) = \log P (Y | θ)$ , $θ^{(i)}$ , $F (\tilde{P}, θ)$ 定义如前. 如果 $F (\tilde{P}, θ)$ 在 ${\tilde{P}}^{*}, θ^{*}$ 有局部/全局极大值, 则 $L (θ)$ 在 $θ^{*}$ 也有局部/全局极大值.

证明

由引理4.1, 引理4.2, $\forall θ$ , $L (θ) = \log P (Y | θ) = F ({\tilde{P}}_{θ}, θ)$ . 特别地, $L (θ^{*}) = F ({\tilde{P}}_{θ^{*}}, θ^{*}) = F ({\tilde{P}}^{*}, θ^{*}) .$ 下面证明 $θ^{*}$ 也是 $L (θ)$ 的极大值点, 也即不存在接近 $θ^{*}$ 的 $θ^{* *}$ , 使得 $L (θ^{* *}) > L (θ^{*})$ . 否则如果它存在, 那么 $F ({\tilde{P}}^{* *}, θ^{* *}) > F ({\tilde{P}}^{*}, θ^{*})$ , 这里 ${\tilde{P}}^{* *} = {\tilde{P}}_{θ^{* *}}$ . 但是因为 ${\tilde{P}}_{θ}$ 随 $θ$ 连续变化, ${\tilde{P}}^{* *}$ 应该接近 ${\tilde{P}}^{*}$ , 这与 $({\tilde{P}}^{*}, θ^{*})$ 是 $F (\tilde{P}, θ)$ 的局部极大值点矛盾.
全局最大值类似可证.

定理 4.2 EM 算法的一次迭代可由

F

函数的极大-极大算法实现.

设 $θ^{(i)}, {\tilde{P}}^{(i)}$ 为第 $i$ 次迭代对应的估计, 在第 $i + 1$ 次迭代, 两步分别为

对固定的 $θ^{(i)}$ , 求 ${\tilde{P}}^{(i + 1)}$ 使 $F (\tilde{P}, θ^{(i)})$ 极大化;
对固定的 ${\tilde{P}}^{(i + 1)}$ , 求 $θ^{(i + 1)}$ 使 $F ({\tilde{P}}^{(i + 1)}, θ)$ 极大化.

证明

由引理4.1, 对固定的 $θ^{(i)}$ , ${\tilde{P}}^{(i + 1)} (Z) = {\tilde{P}}_{θ^{(i)}} (Z) = P (Z | Y, θ^{(i)})$ 可以极大化 $F (\tilde{P}, θ^{(i)})$ . 此时 $\begin{aligned} F ({\tilde{P}}^{(i + 1)}, θ) & = E_{{\tilde{P}}^{(i + 1)}} [\log P (Y, Z | θ)] + H ({\tilde{P}}^{(i + 1)}) \\ = \sum_{Z} \log P (Y, Z | θ) P (Z | Y, θ^{(i)}) + H ({\tilde{P}}^{(i + 1)}) . \end{aligned}$
由 $Q (θ, θ^{(i)})$ 的定义式 (1.1), $F ({\tilde{P}}^{(i + 1)}, θ) = Q (θ, θ^{(i)}) + H ({\tilde{P}}^{(i + 1)}) .$
固定 ${\tilde{P}}^{(i + 1)}$ , 求 $θ^{(i + 1)}$ 使 $F ({\tilde{P}}^{(i + 1)}, θ)$ 极大化, 得到 $θ^{(i + 1)} = \arg max_{θ} F ({\tilde{P}}^{(i + 1)}, θ) = \arg max_{θ} Q (θ, θ^{(i)}) .$

4.2 GEM 算法

GEM 算法 1

输入观测数据, $F$ 函数
输出模型参数

初始化 $θ^{(0)}$ .
第 $i + 1$ 次迭代,
1. 求 ${\tilde{P}}^{(i + 1)}$ 使 $\tilde{P}$ 极大化 $F (\tilde{P}, θ^{(i)})$ .
2. 求 $θ^{(i + 1)}$ 使 $F ({\tilde{P}}^{(i + 1)}, θ)$ 极大化.
重复 2, 3 直到收敛.

GEM 算法 2

输入观测数据, $Q$ 函数
输出模型参数

初始化 $θ^{(0)}$ .
第 $i + 1$ 次迭代,
1. 计算 $Q (θ, θ^{(i)}) = \sum_{Z} P (Z | Y, θ^{(i)}) \log P (Y, Z | θ) .$
2. 求 $θ^{(i + 1)}$ 使 $Q (θ^{(i + 1)}, θ^{(i)}) > Q (θ^{(i)}, θ^{(i)})$ .
重复 2, 3 直到收敛.

GEM 算法 3