从两个例子理解EM算法

本文是作者对EM算法学习的笔记，从EM算法出发介绍EM算法，为了更好理解，用两个应用EM算法求解的例子进一步解释EM的应用。

EM算法

EM算法引入

EM算法，指的是最大期望算法（Expectation Maximization Algorithm，期望最大化算法），是一种迭代算法，在统计学中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。基本思想是首先随机取一个值去初始化待估计的参数值，然后不断迭代寻找更优的参数使得其似然函数比原来的似然函数大。

EM算法当做最大似然估计的拓展，解决难以给出解析解（模型中存在隐变量）的最大似然估计（MLE）问题
在算法中加入隐变量的思想可以类比为几何题中加入一条辅助线的做法。

假定有训练集{

x

(

1

)

,

x

(

2

)

,

.

.

.

x

(

m

)

(

)

(

)

(

)

$x^{(1)},x^{(2)},...x^{(m)}$
}，包含

$m$
个独立样本，希望从中找到该组数据的模型

$p (x, z)$

p (x, z)

$p(x,z)$
的参数。

对数似然函数表达如下：

这里写图片描述

在表达式中因为存在隐变量，直接找到参数估计比较困难，所以我们通过EM算法迭代求解下界的最大值，直到收敛。

我们通过以下的图片来解释这一过程：

这里写图片描述

图片上的紫色部分是我们的目标模型

p

(

x

|

θ

)

(

)

$p(x|\theta)$
曲线，该模型比较复杂，难以直接求解其解析解，为了消除隐变量

$z$
带来的影响，我们可以得到一个不包含的

$z$

z

$z$
的模型

r

(

x

|

θ

)

(

)

$r(x|\theta)$
(该函数是我们自己选定的，因此最大值可求解)，同时满足条件

r

(

x

|

θ

)

≤

p

(

x

|

θ

)

(

)

≤

(

)

$r(x|\theta) \leq p(x|\theta)$
。

我们先取一个

θ

1
不断重复以上过程，在更新过程中始终满足

r

≤

p

从以上过程来看，EM算法的核心就是如何找到这个

$r$
，即

$p$

$p$

$p$
的下界函数。

这个下界函数有多种方法理解，我们从Jensen不等式的角度来理解。

这里写图片描述

上述等号成立的条件是

p

(

x

(

i

)

,

z

(

i

)

;

θ

)

Q

i

(

z

(

i

)

)

=

c

(

)

(

)

;

)

(

)

c

$\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} = c$
,

∑

z

Q

i

(

z

(

i

)

)

=

1

(

)

1

$\sum_z Q_i(z^{(i)}) = 1$
,所以：

这里写图片描述

最终框架如下：

这里写图片描述

EM推导高斯混合模型

高斯混合模型GMM

设有随机变量

$X$
, 则高斯混合模型可以用

$p (x) = \sum_{K} π_{k} N (x | μ_{k}, Σ_{k})$

p (x) = \sum_{K} π_{k} N (x | μ_{k}, Σ_{k})

$p(x) = \sum_K \pi_k \mathcal{N} (x|\mu_k, \Sigma_k)$
，其中



(

x

|

μ

k

,

Σ

k

)

(

)

$\mathcal{N} (x|\mu_k, \Sigma_k)$
表示混合模型中的第

$k$
个分量

$π_{k}$

π_{k}

$\pi_k$
表示混合系数，满足

∑

k

π

k

=

1

，

0

≤

π

k

≤

1

，

≤

1

$\sum_k \pi_k =1， 0 \leq \pi_k \leq 1$
。

我们知道高斯函数的概率分布为

f

(

x

)

=

1

(

√

2

π

)

σ

e

x

p

(

−

(

x

−

μ

)

2

2

σ

2

)

(

)

(

)

(

−

(

−

)

)

$f(x) = \frac{1}{\sqrt(2 \pi)\sigma} exp( -\frac{(x-\mu)^2}{2\sigma^2})$
, 在混合高斯分布中待估计变量就包括了

μ

,

σ

,

π

π

$\mu, \sigma,\pi$
。

对数似然函数为

l

μ

,

Σ

,

π

=

∑

N

i

=

1

l

o

g

(

∑

K

k

=

1

)

π

k



(

x

i

|

μ

k

,

Σ

k

)

)

∑

(

∑

)

(

)

)

$l_{\mu, \Sigma,\pi} = \sum_{i=1} ^ N log(\sum_{k=1} ^K)\pi_k \mathcal{N}(x_i|\mu_k, \Sigma_k))$

EM 推导过程

第一步：估算数据来自于哪个组分，即估计每一个组分生成的概率，对每个样本

x

i

i

$x_i$
，它由第

$k$
个组份生成的概率可以记作：

$γ (i, k) = \frac{π_{k} N (x_{i} | μ_{k}, Σ_{k})}{\sum_{j} π_{j} N (x_{i} | μ_{j}, Σ_{j})}$

γ (i, k) = \frac{π_{k} N (x_{i} | μ_{k}, Σ_{k})}{\sum_{j} π_{j} N (x_{i} | μ_{j}, Σ_{j})}

$\gamma(i,k) = \frac{\pi_k \mathcal{N}(x_i|\mu_k, \Sigma_k)}{\sum_j\pi_j \mathcal{N}(x_i|\mu_j, \Sigma_j)}$

第二步：估计每个组份的参数

E-step: 在给定了样本和每个高斯分布的参数以及组份的分布函数的情况下

w

(

i

)

j

=

Q

i

(

z

(

i

)

=

j

)

=

p

(

z

(

i

)

)

=

j

|

x

(

i

)

;

ϕ

,

μ

,

Σ

)

(

)

(

)

(

)

(

)

;

)

$w_j^{(i)} = Q_i(z^{(i)} = j) = p(z^{(i)}) = j | x^{(i)};\phi, \mu, \Sigma)$

M-step：将多项式分布和高斯分布的参数带入：

∑

m

i

=

1

∑

z

(

i

)

Q

i

(

z

(

i

)

)

l

o

g

p

(

x

(

i

)

,

z

(

i

)

;

ϕ

,

μ

,

Σ

)

Q

i

(

z

(

i

)

)

∑

(

)

(

)

(

)

(

)

;

)

(

)

)

$\sum_{i=1}^m\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p( x^{(i)}, z^{(i)};\phi, \mu, \Sigma)}{Q_i(z^{(i)})}$

=

∑

m

i

=

1

∑

k

j

=

1

Q

i

(

z

(

i

)

=

j

)

l

o

g

p

(

x

(

i

)

|

z

(

i

)

=

j

;

ϕ

,

μ

,

Σ

)

p

(

z

(

i

)

=

j

;

ϕ

)

Q

i

(

z

(

i

)

)

∑

(

)

(

)

(

)

;

)

(

)

;

)

(

)

)

$=\sum_{i=1}^m\sum_{j=1}^kQ_i(z^{(i)}=j)log\frac{p( x^{(i)}| z^{(i)}=j;\phi, \mu, \Sigma)p(z^{(i)}=j; \phi)}{Q_i(z^{(i)})}$

∑

m

i

=

1

∑

k

j

=

1

w

(

i

)

j

l

o

g

1

(

2

π

)

n

2

|

Σ

j

|

(

1

2

)

e

x

p

(

−

1

2

(

x

(

i

)

−

μ

j

)

T

Σ

−

1

j

(

x

(

i

)

−

μ

j

)

)

ϕ

j

w

(

i

)

j

∑

(

)

(

)

(

)

(

−

(

)

−

)

−

(

)

−

)

(

)

$\sum_{i=1}^m\sum_{j=1}^k w_j^{(i)} log \frac{ \frac{1}{(2\pi) ^{\frac{n}{2}}|\Sigma_j|^{(\frac{1}{2})}} exp(-\frac{1}{2}(x^{(i)}-\mu_j)^T \Sigma_j^{-1} (x^{(i)}-\mu_j)) \phi_j }{ w_j^{(i)}}$

分别对其中的未知参数求偏导数：

对均值求偏导

∇

u

j

∑

m

i

=

1

∑

k

j

=

1

w

(

i

)

j

l

o

g

1

(

2

π

)

n

2

|

Σ

j

|

(

1

2

)

e

x

p

(

−

1

2

(

x

(

i

)

−

μ

j

)

T

Σ

−

1

j

(

x

(

i

)

−

μ

j

)

)

ϕ

j

w

(

i

)

j

=

−

∇

u

j

∑

m

i

=

1

∑

k

j

=

1

w

(

i

)

j

1

2

(

x

(

i

)

−

μ

j

)

T

Σ

−

1

j

(

x

(

i

)

−

μ

j

)

−

∇

∑

(

)

(

)

−

)

−

(

)

−

)

$=-\nabla_{u_j} \sum_{i=1}^m\sum_{j=1}^k w_j^{(i)}\frac{1}{2}(x^{(i)}-\mu_j)^T \Sigma_j^{-1} (x^{(i)}-\mu_j)$

=

∑

m

i

=

1

w

(

i

)

j

Σ

−

1

j

(

x

(

i

)

−

μ

j

)

=

0

∑

(

)

−

(

)

−

)

0

$=\sum_{i=1}^m w_j^{(i)}\Sigma_j ^{-1}(x^{(i)} -\mu_j) = 0$

可得

μ

j

=

∑

m

i

=

1

w

(

i

)

j

x

(

i

)

∑

m

i

=

1

w

(

i

)

j

∑

(

)

(

)

∑

(

)

$\mu_j = \frac{\sum_{i=1}^m w_j^{(i)} x^{(i)}}{\sum_{i=1}^m w_j^{(i)}}$

对方差求导：

∇

Σ

j

∑

m

i

=

1

∑

k

j

=

1

w

(

i

)

j

l

o

g

1

(

2

π

)

n

2

|

Σ

j

|

(

1

2

)

e

x

p

(

−

1

2

(

x

(

i

)

−

μ

j

)

T

Σ

−

1

j

(

x

(

i

)

−

μ

j

)

)

ϕ

j

w

(

i

)

j

=

∇

Σ

j

∑

m

i

=

1

∑

k

j

=

1

w

(

i

)

j

(

l

o

g

Σ

−

1

2

−

1

2

(

x

(

i

)

−

μ

j

)

T

Σ

−

1

j

(

x

(

i

)

−

μ

j

)

)

∇

∑

(

)

(

−

(

)

−

)

−

(

)

−

)

)

$=\nabla_{\Sigma_j}\sum_{i=1}^m\sum_{j=1}^k w_j^{(i)}(log\Sigma^{-\frac{1}{2}} -\frac{1}{2}(x^{(i)}-\mu_j)^T \Sigma_j^{-1} (x^{(i)}-\mu_j))$

=

∑

m

i

=

1

w

(

i

)

j

Σ

(

−

1

)

−

∑

m

i

=

1

w

(

i

)

j

(

x

(

i

)

−

μ

j

)

(

x

(

i

)

−

μ

j

)

T

Σ

(

−

2

)

=

0

∑

(

)

(

−

)

−

∑

(

)

(

)

−

)

(

)

−

)

(

−

)

0

$=\sum_{i=1}^m w_j ^{(i)} \Sigma^{(-1)} - \sum_{i=1}^m w_j ^{(i)} (x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T \Sigma^{(-2)} = 0$

可得

Σ

j

=

∑

m

i

=

1

w

(

i

)

j

(

x

(

i

)

−

μ

j

)

(

x

(

i

)

−

μ

j

)

T

∑

m

i

=

1

w

(

i

)

j

∑

(

)

(

)

−

)

(

)

−

)

∑

(

)

$\Sigma_j = \frac{\sum_{i=1} ^m w_j^{(i)}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1} ^m w_j^{(i)}}$

对

$\phi$
求偏导，等式约束，用到拉格朗日乘子法，删除常数项目得到：

∇

ϕ

j

∑

m

i

=

1

∑

k

j

=

1

w

(

i

)

j

l

o

g

(

ϕ

j

)

+

β

(

∑

k

j

=

1

ϕ

j

−

1

)

EM推导PLSA模型

详细过程可参考作者的另一篇博客

plsaEM的详细推导

原文链接：https://blog.csdn.net/ustbfym/article/details/79302652