EM算法及其推广

《统计学习方法》笔记 第9章

Posted by Cheereus on February 16, 2020

第9章 EM算法及其推广

EM 算法是一种迭代算法,用于含有隐变量(hidden variable)的概率模型参数的极大似然估计,或极大后验概率估计。

EM 算法的每次迭代由两步组成:E 步,求期望(expectation);M 步,求极大(maximization)。所以这一算法称为期望极大算法(expectation maximization algorithm),简称 EM 算法。

9.1 EM算法的引入

9.1.1 EM算法

输入:观测变量数据 $Y$,隐变量数据 $Z$,联合分布 $P(Y,Z\vert\theta)$,条件分布 $P(Z\vert Y,\theta)$;

输出:模型参数 $\theta$。

(1) 选择参数的初值 $\theta^{(0)}$,开始迭代;

(2) E 步:记 $\theta^{(i)}$ 为第 $i$ 次迭代参数 $\theta$ 的估计值,在第 $i+1$ 次迭代的 E 步,计算

\[Q(\theta,\theta^{(i)})=E_Z[\log P(Y,Z\vert\theta)\vert Y,\theta^{(i)}]\] \[=\sum_Z \log P(Y,Z\vert\theta)P(Z\vert Y,\theta^{(i)})\]

这里,$P(Z\vert Y,\theta^{(i)})$ 是在给定观测数据 $Y$ 和当前的参数估计 $\theta^{(i)}$ 下隐变量数据 $Z$ 的条件概率分布;

(3) M 步:求使 $Q(\theta,\theta^{(i)})$ 极大化的 $\theta$,确定第 $i+1$ 次迭代的参数的估计值 $\theta^{(i+1)}$

\[\theta^{(i+1)}=\arg\underset{\theta}{\max}Q(\theta,\theta^{(i)})\]

(4) 重复第 (2) 步和第 (3) 步,直到收敛。

其中函数 $Q(\theta,\theta^{(i)})$ 是 EM 算法的核心,称为 $Q$ 函数($Q$ function),其定义为:

完全数据的对数似然函数 $\log P(Y,Z\vert\theta)$ 关于在给定观测数据 $Y$ 和当前参数 $\theta^{(i)}$ 下对未观测数据 $Z$ 的条件概率分布 $P(Y,Z\vert\theta)$ 的期望称为 $Q$ 函数,即:

\[Q(\theta,\theta^{(i)})=E_Z[\log P(Y,Z\vert\theta)\vert Y,\theta^{(i)}]\]

9.1.2 EM算法的导出

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

9.2 EM算法的收敛性

关于 EM 算法 收敛性的两个定理

定理1

设 $P(Y\vert\theta)$ 为观测数据的似然函数,$\theta^{(i)}(i=1,2,\cdots)$ 为 EM 算法得到的参数估计序列,$P(Y\vert\theta^{(i)})(i=1,2,\cdots)$ 为对应的似然函数序列,则 $P(Y\vert\theta^{(i)})$ 是单调递增的,即

\[P(Y\vert\theta^{(i+1)})\geq P(Y\vert\theta^{(i)})\]

定理2

设 $L(\theta)=P(Y\vert\theta)$ 为观测数据的对数似然函数,$P(Y\vert\theta^{(i)})(i=1,2,\cdots)$ 为 EM 算法得到的参数估计序列,$L(\theta^{(i)})(i=1,2,\cdots)$ 为对应的对数似然函数序列。

(1) 如果 $P(Y\vert\theta)$ 有上界,则 $L(\theta^{(i)})=\log P(Y\vert\theta^{(i)})$ 收敛到某一值 $L^*$;

(2) 在函数 $Q(\theta,\theta’)$ 与 $L(\theta)$ 满足一定条件下,由 EM 算法得到的参数估计序列 $\theta^{(i)}$ 的收敛值 $\theta^*$ 是 $L(\theta)$ 的稳定点。

9.3 EM算法在高斯混合模型学习中的应用

9.3.1 高斯混合模型

高斯混合模型是指具有如下形式的概率分布模型:

\[P(y\vert\theta)=\sum_{k=1}^K \alpha_k\phi(y\vert\theta_k)\]

其中,$\alpha_k$ 是系数,$\alpha\geq 0$,$\displaystyle\sum_{k=1}^K\alpha_k=1$;$\phi(y\vert\theta_k)$ 是高斯分布密度,$\theta_k=(\mu_k,\sigma_k^2)$,

\[\phi(y\vert\theta_k)=\frac{1}{\sqrt{2\pi}\sigma_k}\exp\bigg(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg)\]

称为第 $k$ 个分模型。

一般混合模型可以由任意概率分布密度代替上式中的高斯分布密度。

9.3.2 高斯混合模型参数估计的 EM 算法

输入:观测数据 $y_1,y_2,\cdots,y_N$,高斯混合模型;

输出:高斯混合模型参数。

(1) 取参数的初始值开始迭代;

(2) E 步:依据当前模型参数,计算分模型 $k$ 对观测数据 $y_j$ 的响应度

\[\hat{\gamma}_{jk}=\frac{\alpha_k\phi(y\vert\theta_k)}{\displaystyle\sum_{k=1}^K\alpha_k\phi(y_j\vert\theta_k)}\]

(3) M 步:计算新一轮迭代的模型参数

\[\hat{\mu}_k=\frac{\displaystyle\sum_{j=1}^N\hat{\gamma}_{jk}y_j}{\displaystyle\sum_{j=1}^N\hat{\gamma}_{jk}},\ k=1,2,\cdots,K\] \[\hat{\sigma}_k^2=\frac{\displaystyle\sum_{j=1}^N\hat{\gamma}_{jk}(y_j-\mu_k)^2}{\displaystyle\sum_{j=1}^N\hat{\gamma}_{jk}},\ k=1,2,\cdots,K\] \[\hat{\alpha}_k=\frac{\displaystyle\sum_{j=1}^N\hat{\gamma}_{jk}}{N},\ k=1,2,\cdots,K\]

(4) 重复第 (2) 步和第 (3) 步,直到收敛。

9.4 EM算法的推广

9.4.1 F函数的极大-极大算法

假设隐变量数据 $Z$ 的概率分布为 $\widetilde{P}(Z)$,定义分布 $\widetilde{P}$ 与参数 $\theta$ 的函数 $F(\widetilde{P},\theta)$ 如下:

\[F(\widetilde{P},\theta)=E_{\widetilde P}[\log P(Y,Z\vert\theta)]+H(\widetilde{P})\]

称为 $F$ 函数。式中 $H(\widetilde{P})=-E_{\widetilde P}\log\widetilde{P}(Z)$ 是分布 $\widetilde{P}(Z)$ 的熵。

EM 算法的一次迭代可由 $F$ 函数的极大-极大算法实现。

设 $\theta^{(i)}$ 为第 $i$ 次迭代参数 $\theta$ 的估计,$\widetilde{P}^{(i)}$ 为第 $i$ 次迭代函数 $\widetilde{P}$ 的估计。在第 $i+1$ 次迭代的两步为:

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

(2) 对固定的 $\widetilde{P}^{(i+1)}$,求 $\theta^{(i+1)}$ 使 $F(\widetilde{P}^{(i+1)},\theta)$ 极大化。

9.4.2 广义极大(GEM)算法

GEM算法 1

输入:观测数据,$F$ 函数;

输出:模型参数。

(1) 初始化参数 $\theta^{(0)}$,开始迭代;

(2) 第 $i+1$ 次迭代,第 1 步:记 $\theta^{(i)}$ 为参数 $\theta$ 的估计值,$\widetilde{P}^{(i)}$ 为函数 $\widetilde{P}$ 的估计,求 $\widetilde{P}^{(i+1)}$ 使 $\widetilde{P}$ 极大化 $F(\widetilde{P},\theta^{(i)})$;

(3) 第 2 步:求 $\theta^{(i+1)}$ 使 $F(\widetilde{P}^{(i+1)},\theta)$ 极大化;

(4) 重复 (2) 和 (3),直到收敛。

在 GEM 算法 1 中,有时求 $Q(\theta,\theta^{(i)})$ 的极大化是很困难的。下面的 GEM 算法 2 和算法 3 并不是直接求 $\theta^{(i+1)}$ 使 $Q(\theta,\theta^{(i)})$ 达到极大的 $\theta$,而是找一个 $\theta^{(i+1)}$ 使得 $Q(\theta^{(i+1)},\theta^{(i)})>Q(\theta^{(i)},\theta^{(i)})$。

GEM 算法 2

输入:观测数据,$Q$ 函数;

输出:模型参数。

(1) 初始化参数 $\theta^{(0)}$,开始迭代;

(2) 第 $i+1$ 次迭代,第 1 步:记 $\theta^{(i)}$ 为参数 $\theta$ 的估计值,计算

\[Q(\theta,\theta^{(i)})=E_Z[\log P(Y,Z\vert\theta)\vert Y,\theta^{(i)}]\] \[= \sum_Z P(Z\vert Y,\theta^{(i)})\log P(Y,Z\vert\theta)\]

(3) 第 2 步:求 $\theta^{(i+1)}$ 使

\[Q(\theta^{(i+1)},\theta^{(i)})>Q(\theta^{(i)},\theta^{(i)})\]

(4) 重复 (2) 和 (3),直到收敛。

当参数 $\theta$ 的维数为 $d(d\geq2)$ 时,可采用一种特殊的 GEM 算法,它将 EM 算法的 M 步分解为 $d$ 次条件极大化,每次只改变参数向量的一个分量,其余分量不变。

GEM 算法 3

输入:观测数据,$Q$ 函数;

输出:模型参数。

(1) 初始化参数 $\theta^{(0)}=(\theta^{(0)}_1,\theta^{(0)}_2,\cdots,\theta^{(0)}_d)$,开始迭代;

(2) 第 $i+1$ 次迭代,第 1 步:记 $\theta^{(i)}=(\theta^{(i)}_1,\theta^{(i)}_2,\cdots,\theta^{(i)}_d)$ 为参数 $\theta=(\theta_1,\theta_2,\cdots,\theta_d)$ 的估计值,计算

\[Q(\theta,\theta^{(i)})=E_Z[\log P(Y,Z\vert\theta)\vert Y,\theta^{(i)}]\] \[= \sum_Z P(Z\vert Y,\theta^{(i)})\log P(Y,Z\vert\theta)\]

(3) 第 2 步:进行 $d$ 次条件极大化:

首先,在 $\theta^{(i)}_2,\cdots,\theta^{(i)}_d$ 保持不变的条件下求使 $Q(\theta,\theta^{(i)})$ 达到极大的 $\theta^{(i+1)}_1$;

然后,在 $\theta_1=\theta^{(i+1)}_1,\theta_j=\theta^{(i+1)}_j,j=3,4,\cdots,d$ 的条件下求使 $Q(\theta,\theta^{(i)})$ 达到极大的 $\theta^{(i+1)}_2$;

如此继续,经过 $d$ 次条件极大化,得到 $\theta^{(i+1)}=(\theta^{(i+1)}_1,\theta^{(i+1)}_2,\cdots,\theta^{(i+1)}_d)$ 使得

\[Q(\theta^{(i+1)},\theta^{(i)})>Q(\theta^{(i)},\theta^{(i)})\]

(4) 重复 (2) 和 (3),直到收敛。

第9章完结


如果对您有帮助,欢迎赞助一杯咖啡!