Skip to main content

EM 算法 - 收敛性

· 6 min read
PuQing
PuQing
AI, CVer, Pythoner, Half-stack Developer

Expectation Maximization(EM) 算法，该算法用于解决具有隐变量的混合模型的高斯和分布（例子可以见 三硬币模型）。在比较理想的情况中，我们可以直接得出我们求得的参数的解析解，比如： MLE:p(X∣θ)\mathrm{MLE}:p(X\mid \theta)。我们想要求解的结果就是：

θMLE=arg⁡max⁡θ∑i=1Nlog⁡p(xi∣θ)\theta_{MLE} = \arg \max_{\theta}\sum_{i=1}^N \log p(x_{i}\mid \theta)

其中，∑i=1Nlog⁡p(xi∣θ)\sum_{i=1}^N\log p(x_{i}\mid \theta) 也被我们称为 对数似然函数。但是一旦引入隐变量，似然函数变为：

L(θ)=∑i=1Nlog⁡p(xi∣θ)=∑iNlog⁡[∑zip(xi,zi∣θ)]\mathcal{L}(\theta) = \sum_{i=1}^N \log p(x_{i}\mid \theta)=\sum_{i}^N \log \left[ \sum_{z_{i}} p(x_{i},z_{i}\mid \theta) \right]
其他格式：
L(θ)=∑iNlog⁡[∑zip(xi,zi;θ)]\mathcal{L}(\theta) = \sum_{i}^N \log \left[ \sum_{z_{i}}p(x_{i},z_{i};\theta) \right]

写成条件概率的形式 (该种写法在 混合模型 中有过推导)

L(θ)=∑iNlog⁡[∑zip(xi∣zi;θ)p(zi∣θ)]\mathcal{L}(\theta) = \sum_{i}^N \log \left[ \sum_{z_{i}}p(x_{i}\mid z_{i};\theta)p(z_{i}\mid \theta) \right]

这个式子变的难以求解

info

就拿上面 三硬币模型 来说，其似然函数可写为，

P(Y∣θ)=∏j=1n[πpyj(1−p)1−yj+(1−π)qyj(1−q)1−yj]P(Y \mid \theta)=\prod_{j=1}^{n}\left[\pi p^{y_{j}}(1-p)^{1-y_{j}}+(1-\pi) q^{y_{j}}(1-q)^{1-y_{j}}\right]

所以似然估计为

θ^=arg⁡max⁡θlog⁡P(Y∣θ)\begin{equation} \hat{\theta}=\arg \max _{\theta} \log P(Y \mid \theta) \end{equation}

即求下面函数的零点：

∑j=1nlog⁡(πpyj(1−p)1−yj+(1−π)qyj(1−q)1−yj)\sum_{j=1}^{n}\log\left(\pi p^{y_{j}}(1-p)^{1-y_{j}}+(1-\pi) q^{y_{j}}(1-q)^{1-y_{j}}\right)

分别对 π,p,q\pi,p,q 求偏导：

∂log⁡P(Y∣θ)∂π=∑j=1npyi(1−p)1−yi−qyi(1−q)1−yipyiπ(1−p)1−yi−qyi(1−q)1−yi(π−1)∂log⁡P(Y∣θ)∂p=∑j=1nπ(−pyiyi(1−p)2−yi+pyi+1(1−p)1−yi(1−yi))p(p−1)(pyiπ(1−p)1−yi−qyi(1−q)1−yi(π−1))∂log⁡P(Y∣θ)∂q=∑j=1n(π−1)(qyiyi(1−q)2−yi+qyi+1(1−q)1−yi(yi−1))q(q−1)(pyiπ(1−p)1−yi−qyi(1−q)1−yi(π−1))\begin{aligned} \frac{\partial \log P(Y\mid \theta)}{\partial\pi}&= \sum_{j=1}^n\frac{p^{y_{i}}(1-p)^{1-y_{i}}-q^{y_{i}}(1-q)^{1-y_{i}}}{p^{y_{i}} \pi(1-p)^{1-y_{i}}-q^{y_{i}}(1-q)^{1-y_{i}}(\pi-1)}\\ \frac{\partial \log P(Y\mid \theta)}{\partial p}&= \sum_{j=1}^n\frac{\pi\left(-p^{y_{i}} y_{i}(1-p)^{2-y_{i}}+p^{y_{i}+1}(1-p)^{1-y_{i}}\left(1-y_{i}\right)\right)}{p(p-1)\left(p^{y_{i}} \pi(1-p)^{1-y_{i}}-q^{y_{i}}(1-q)^{1-y_{i}}(\pi-1)\right)} \\ \frac{\partial \log P(Y\mid \theta)}{\partial q}&=\sum_{j=1}^n\frac{(\pi-1)\left(q^{y_{i}} y_{i}(1-q)^{2-y_{i}}+q^{y_{i}+1}(1-q)^{1-y_{i}}\left(y_{i}-1\right)\right)}{q(q-1)\left(p^{y_{i}} \pi(1-p)^{1-y_{i}}-q^{y_{i}}(1-q)^{1-y_{i}}(\pi-1)\right)} \end{aligned}

…这是及其难以求解的

EM 算法概述​

期望最大算法整体上利用了 MM algorithm 核心思想

warning

在 MM algorithm 中我们要求函数的最大值/最小值，我们可以构造一个代理函数 Q(θ,θt)Q(\theta,\theta_{t})，并且这个代理函数 Q(θ,θt)Q(\theta,\theta_{t}) 在 EM 算法中是对数似然函数 L(θ)\mathcal{L}(\theta) 的紧下界，应该满足如下两个条件：

Q(θ,θt)≤L(θ)Q(θt,θt)=L(θt)\begin{split} Q(\theta,\theta_{t}) \leq \mathcal{L}(\theta)\\ Q(\theta_{t},\theta_{t}) = \mathcal{L}(\theta_{t}) \end{split}

这样的话我们的目标由最大化对数似然函数 L(θ)\mathcal{L}(\theta) 转变为了一步一步迭代紧下界 Q(θ,θt)Q(\theta,\theta_{t})，于是：

θt+1=arg⁡max⁡θQ(θ,θt)\theta_{t+1} = \arg \max_{\theta}Q(\theta,\theta_{t})

因此，利用 MM algorithm 算法从第 tt 步迭代到第 t+1t+1 步利用了如下不等式关系

L(θt+1)≥Q(θt+1,θt)≥Q(θt,θt)=L(θt)\mathcal{L}(\theta_{t+1}) \geq Q(\theta_{t+1},\theta_{t}) \geq Q(\theta_{t},\theta_{t}) = \mathcal{L}(\theta_{t})

相关资料​