目录
一.引例
1.引例11
设四种实验结果发生的概率依次为：
1
2
−
θ
4
,
1
4
−
θ
4
,
1
4
+
θ
4
,
θ
4
\frac{1}{2}-\frac{\theta}{4},\frac{1}{4}-\frac{\theta}{4},\frac{1}{4}+\frac{\theta}{4},\frac{\theta}{4}
21−4θ,41−4θ,41+4θ,4θ;
发生的次数依次为：
y
1
,
y
2
,
y
3
,
y
4
y_1,y_2,y_3,y_4
y1,y2,y3,y4次，求
θ
^
\hat \theta
θ^.
- 最大似然估计：
L ( θ ) = ( 1 2 − θ 4 ) y 1 ( 1 4 − θ 4 ) y 2 ( 1 4 + θ 4 ) y 3 ( θ 4 ) y 4 ln L ( θ ) = y 1 ln ( 1 2 − θ 4 ) + y 2 ln ( 1 4 − θ 4 ) + y 3 ln ( 1 4 + θ 4 ) + y 4 ln ( θ 4 ) d ln L ( θ ) d θ = − y 1 2 − θ − y 2 1 − θ − y 3 1 + θ − y 4 θ = 0 \begin{aligned}L(\theta) &=(\frac{1}{2}-\frac{\theta}{4})^{y_1}(\frac{1}{4}-\frac{\theta}{4})^{y_2}(\frac{1}{4}+\frac{\theta}{4})^{y_3}(\frac{\theta}{4})^{y_4}\\ \ln{L(\theta)} &= y_1\ln{(\frac{1}{2}-\frac{\theta}{4})} +y_2\ln{(\frac{1}{4}-\frac{\theta}{4})} +y_3\ln{(\frac{1}{4}+\frac{\theta}{4})} +y_4\ln{(\frac{\theta}{4})} \\ \frac{\mathrm{d}\ln{L(\theta)}}{\mathrm{d}\theta}&=-\frac{y_1}{2-\theta} -\frac{y_2}{1-\theta}-\frac{y_3}{1+\theta}-\frac{y_4}{\theta}=0 \end{aligned} L(θ)lnL(θ)dθdlnL(θ)=(21−4θ)y1(41−4θ)y2(41+4θ)y3(4θ)y4=y1ln(21−4θ)+y2ln(41−4θ)+y3ln(41+4θ)+y4ln(4θ)=−2−θy1−1−θy2−1+θy3−θy4=0
由于导数是关于 θ \theta θ的一元三次方程，求解困难，当然也可以用数值方法求解，但是如果涉及的实验结果不止4个，就显得麻烦，所以为了使方法更加通用化，则使用EM算法来求解. - EM算法
1）把事件拆分为两个和事件：
假设发生结果概率为 1 2 − θ 4 \frac{1}{2}-\frac{\theta}{4} 21−4θ的事件拆分为发生概率为 1 4 − θ 4 \frac{1}{4}-\frac{\theta}{4} 41−4θ和 1 4 \frac{1}{4} 41的两个事件，发生次数分为 z 1 , y 1 − z 1 ; z_1,y_1-z_1; z1,y1−z1;
假设发生结果概率为 1 4 + θ 4 \frac{1}{4}+\frac{\theta}{4} 41+4θ的事件拆分为发生概率为 θ 4 \frac{\theta}{4} 4θ和 1 4 \frac{1}{4} 41的两个事件，发生次数分为 z 2 , y 3 − z 2 ; z_2,y_3-z_2; z2,y3−z2;
2）由最大似然估计：
L ( θ ) = ( 1 4 ) y 1 − z 1 ( 1 4 − θ 4 ) y 2 + z 1 ( 1 4 ) y 3 − z 2 ( θ 4 ) y 4 + z 2 ln L ( θ ) = ( y 1 − z 1 ) ln 1 4 + ( y 2 + z 1 ) ln ( 1 4 − θ 4 ) + ( y 3 − z 2 ) ln 1 4 + ( y 4 + z 2 ) ln θ 4 d ln L ( θ ) d θ = − y 2 + z 1 1 − θ + y 4 + z 2 θ = 0 \begin{aligned}L(\theta) &=(\frac{1}{4})^{y_1-z_1}(\frac{1}{4}-\frac{\theta}{4})^{y_2+z_1}(\frac{1}{4})^{y_3-z_2}(\frac{\theta}{4})^{y_4+z_2}\\ \ln{L(\theta)} &= (y_1-z_1)\ln{\frac{1}{4}} +(y_2+z_1)\ln{(\frac{1}{4}-\frac{\theta}{4})} +(y_3-z_2)\ln{\frac{1}{4}} +(y_4+z_2)\ln{\frac{\theta}{4}} \\ \frac{\mathrm{d}\ln{L(\theta)}}{\mathrm{d}\theta}&=-\frac{y_2+z_1}{1-\theta}+\frac{y_4+z_2}{\theta}=0 \end{aligned} L(θ)lnL(θ)dθdlnL(θ)=(41)y1−z1(41−4θ)y2+z1(41)y3−z2(4θ)y4+z2=(y1−z1)ln41+(y2+z1)ln(41−4θ)+(y3−z2)ln41+(y4+z2)ln4θ=−1−θy2+z1+θy4+z2=0
θ ^ = z 2 + y 4 z 2 + z 1 + y 2 + y 4 (1) \hat \theta =\frac{z_2+y_4}{z_2+z_1+y_2+y_4} \tag1 θ^=z2+z1+y2+y4z2+y4(1)
3）由于 z 1 , z 2 z_1,z_2 z1,z2未知，但次数服从二项分布，故 z 1 ∼ B ( y 1 , 1 4 − θ 4 1 2 − θ 4 = 1 − θ 2 − θ ) z_1 \sim B(y_1,\frac{\frac{1}{4}-\frac{\theta}{4}}{\frac{1}{2}-\frac{\theta}{4}}=\frac{1-\theta}{2-\theta}) z1∼B(y1,21−4θ41−4θ=2−θ1−θ),同理， z 2 ∼ B ( y 3 , θ 1 + θ ) z_2 \sim B(y_3,\frac{\theta}{1+\theta}) z2∼B(y3,1+θθ)
4）EM算法：- 第一步（E步）：求期望；目的：消去潜在变量
z
1
,
z
2
z_1,z_2
z1,z2
E ( z 1 ) = y 1 1 − θ 2 − θ , E ( z 2 ) = y 3 θ 1 + θ E(z_1)=y_1\frac{1-\theta}{2-\theta},E(z_2)=y_3\frac{\theta}{1+\theta} E(z1)=y12−θ1−θ,E(z2)=y31+θθ
对 ( 1 ) (1) (1)式两边求期望，带入即可. - 第二步（M步）：求最大
带入后得： θ ^ = y 3 θ 1 + θ + y 4 y 3 θ 1 + θ + y 1 1 − θ 2 − θ + y 2 + y 4 \hat \theta =\frac{y_3\frac{\theta}{1+\theta}+y_4}{y_3\frac{\theta}{1+\theta}+y_1\frac{1-\theta}{2-\theta}+y_2+y_4} θ^=y31+θθ+y12−θ1−θ+y2+y4y31+θθ+y4
迭代法求：
θ i + 1 = y 3 θ i 1 + θ i + y 4 y 3 θ i 1 + θ i + y 1 1 − θ i 2 − θ i + y 2 + y 4 \theta^{i+1} =\frac{y_3\frac{\theta^i}{1+\theta^i}+y_4}{y_3\frac{\theta^i}{1+\theta^i}+y_1\frac{1-\theta^i}{2-\theta^i}+y_2+y_4} θi+1=y31+θiθi+y12−θi1−θi+y2+y4y31+θiθi+y4
- 第一步（E步）：求期望；目的：消去潜在变量
z
1
,
z
2
z_1,z_2
z1,z2
2.引例22
3枚硬币A，B，C出现正面的概率分别为：
π
,
p
,
q
\pi,p,q
π,p,q.现做如下实验：先抛硬币A，若出现正面选B，若出现反面选C，再投掷选出的硬币，出现正面记为1，反面记为0；独立重复
n
n
n次实验,假设只能观测掷硬币的结果，不能观测掷硬币的过程，如何求出
π
,
p
,
q
\pi,p,q
π,p,q？
P
(
y
∣
θ
)
=
∑
z
P
(
y
,
z
∣
θ
)
=
∑
z
P
(
z
∣
θ
)
P
(
y
∣
z
,
θ
)
=
π
p
y
(
1
−
p
)
1
−
y
+
(
1
−
π
)
q
y
(
1
−
q
)
1
−
y
\begin{aligned}P(y\vert \theta) &= \sum_zP(y,z\vert \theta)=\sum_zP(z\vert \theta)P(y\vert z,\theta) \\&=\pi p^y(1-p)^{1-y}+(1-\pi)q^y(1-q)^{1-y}\end{aligned}
P(y∣θ)=z∑P(y,z∣θ)=z∑P(z∣θ)P(y∣z,θ)=πpy(1−p)1−y+(1−π)qy(1−q)1−y
其中
y
y
y为一次观测的结果，
z
z
z为隐变量，即中间A的结果，
θ
=
(
π
,
p
,
q
)
\theta=(\pi,p,q)
θ=(π,p,q).
将观测数据表示为：
Y
=
(
y
1
,
y
2
,
…
,
y
n
)
T
Y=(y_1,y_2,\dots,y_n)^\mathrm{T}
Y=(y1,y2,…,yn)T,隐变量表示为：
Z
=
(
z
1
,
z
2
,
…
,
z
n
)
T
Z=(z_1,z_2,\dots,z_n)^\mathrm{T}
Z=(z1,z2,…,zn)T,则：
P
(
Y
∣
θ
)
=
∏
j
=
1
n
[
π
p
y
j
(
1
−
p
)
1
−
y
j
+
(
1
−
π
)
q
y
j
(
1
−
q
)
1
−
y
j
]
P(Y\vert \theta)=\prod^n_{j=1}[\pi p^{y_j}(1-p)^{1-{y_j}}+(1-\pi)q^{y_j}(1-q)^{1-{y_j}}]
P(Y∣θ)=j=1∏n[πpyj(1−p)1−yj+(1−π)qyj(1−q)1−yj]
根据最大似然估计：
θ
^
=
arg
max
θ
log
P
(
Y
∣
θ
)
\hat \theta=\arg \max_\theta\log P(Y\vert \theta)
θ^=argθmaxlogP(Y∣θ)
由于这个问题无解析解，故用数值方法迭代法求解，即EM法.
以下介绍EM算法的理论由来部分.
二.证明EM的收敛性3
1.单个高斯
当总体
X
∼
N
(
μ
,
σ
2
)
,
x
i
∼
i
i
d
X
,
i
=
1
,
2
,
…
,
n
X\sim N(\mu,\sigma^2),x_i\overset{iid}{\sim}X,i=1,2,\dots,n
X∼N(μ,σ2),xi∼iidX,i=1,2,…,n,令
θ
=
(
μ
,
σ
2
)
\theta=(\mu,\sigma^2)
θ=(μ,σ2)
θ
^
=
arg
max
θ
∑
i
=
1
n
log
N
(
x
i
∣
μ
,
σ
2
)
(2)
\hat \theta = \arg\max_{\theta} \sum_{i=1}^n\log N(x_i\vert\mu,\sigma^2) \tag2
θ^=argθmaxi=1∑nlogN(xi∣μ,σ2)(2)
当总体服从单个高斯分布时，易根据最大似然估计法求得：
μ
^
=
x
ˉ
,
σ
2
^
=
S
2
\hat \mu=\bar x,\hat {\sigma^2}=S^2
μ^=xˉ,σ2^=S2;
其中
L
(
θ
∣
x
1
,
x
2
,
…
,
x
n
)
=
∑
i
=
1
n
log
N
(
x
i
∣
μ
,
σ
2
)
L(\theta\vert x_1,x_2,\dots,x_n)=\sum_{i=1}^n\log N(x_i\vert\mu,\sigma^2)
L(θ∣x1,x2,…,xn)=∑i=1nlogN(xi∣μ,σ2)称为对数似然函数.
2.高斯混合模型
当总体服从混合高斯模型时，假设有
k
k
k个高斯模型，样本
x
i
,
i
=
1
,
2
,
…
,
n
x_i,i=1,2,\dots,n
xi,i=1,2,…,n ,
θ
=
(
μ
1
,
μ
2
,
…
,
μ
k
,
σ
1
2
,
σ
2
2
,
…
,
σ
k
2
,
λ
1
,
λ
2
,
…
,
λ
k
−
1
)
\theta=(\mu_1,\mu_2,\dots,\mu_k,\sigma^2_1,\sigma^2_2,\dots,\sigma^2_k,\lambda_1,\lambda_2,\dots,\lambda_{k-1})
θ=(μ1,μ2,…,μk,σ12,σ22,…,σk2,λ1,λ2,…,λk−1),则
x
i
x_i
xi出现的概率为
k
k
k个高斯的叠加，即：
P
(
x
i
∣
θ
)
=
∑
j
=
1
k
λ
j
N
(
μ
j
,
σ
j
2
)
s
.
t
.
∑
j
=
1
k
λ
j
=
1
\begin{aligned}P(x_i \vert \theta) &=\sum_{j=1}^k\lambda_j N(\mu_j,\sigma^2_j)\\ \mathrm{s.t.}\sum_{j=1}^{k}\lambda_j &=1\end{aligned}
P(xi∣θ)s.t.j=1∑kλj=j=1∑kλjN(μj,σj2)=1
若使用最大似然估计，则得(即用
P
(
x
i
∣
θ
)
P(x_i \vert \theta)
P(xi∣θ)代替
(
2
)
(2)
(2)式的
N
(
x
i
∣
μ
,
σ
2
)
N(x_i\vert\mu,\sigma^2)
N(xi∣μ,σ2))：
θ
^
=
arg
max
θ
∑
i
=
1
n
log
∑
j
=
1
k
λ
j
N
(
μ
j
,
σ
j
2
)
\hat \theta = \arg\max_{\theta} \sum_{i=1}^n\log \sum_{j=1}^k\lambda_j N(\mu_j,\sigma^2_j)
θ^=argθmaxi=1∑nlogj=1∑kλjN(μj,σj2)
由于对每一个参数求导为零是一件很困难的事，所以使用迭代的方法(EM法)求解
θ
^
\hat \theta
θ^,迭代公式为：
θ
(
g
+
1
)
=
arg
max
θ
∫
Z
log
P
(
X
,
Z
∣
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
s
.
t
.
log
P
(
X
∣
θ
(
g
+
1
)
)
≥
log
P
(
X
∣
θ
g
)
(4)
\begin{aligned}\theta^{(g+1)} &=\arg\max_\theta \int_Z\log P(X,Z \vert\theta)P(Z \vert X,\theta^{g})\mathrm{d}Z\\ \mathrm{s.t.} \log P(X \vert \theta^{(g+1)}) &\geq \log P(X \vert \theta^{g}) \tag4\end{aligned}
θ(g+1)s.t.logP(X∣θ(g+1))=argθmax∫ZlogP(X,Z∣θ)P(Z∣X,θg)dZ≥logP(X∣θg)(4)
其中
Z
Z
Z为隐变量集合，
X
X
X为数据集合
3.收敛性证明
即证明：
log
P
(
X
∣
θ
(
g
+
1
)
)
≥
log
P
(
X
∣
θ
g
)
\log P(X \vert \theta^{(g+1)})\geq \log P(X \vert \theta^{g})
logP(X∣θ(g+1))≥logP(X∣θg)
证明：
由：
log
P
(
X
∣
θ
)
=
log
P
(
X
,
Z
∣
θ
)
−
log
P
(
Z
∣
X
,
θ
)
(3)
\log P(X \vert \theta)=\log P(X,Z \vert \theta)-\log P(Z \vert X,\theta) \tag 3
logP(X∣θ)=logP(X,Z∣θ)−logP(Z∣X,θ)(3)
因为P(AB)=P(A)P(B|A),故 log P ( A ) = log P ( A B ) − log P ( B ∣ A ) \log P(A)=\log P(AB)-\log P(B|A) logP(A)=logP(AB)−logP(B∣A),两边同时加上 θ \theta θ即可
对
(
3
)
(3)
(3)式两边对分布
P
(
Z
∣
X
,
θ
g
)
P(Z|X,\theta^g)
P(Z∣X,θg)求期望：
∫
Z
log
P
(
X
∣
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
=
∫
Z
log
P
(
X
,
Z
∣
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
−
∫
Z
log
P
(
Z
∣
X
,
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
\int_Z \log P(X \vert \theta)P(Z|X,\theta^g)\mathrm{d}Z=\int_Z \log P(X,Z \vert \theta)P(Z|X,\theta^g)\mathrm{d}Z-\int_Z \log P(Z \vert X,\theta) P(Z|X,\theta^g)\mathrm{d}Z
∫ZlogP(X∣θ)P(Z∣X,θg)dZ=∫ZlogP(X,Z∣θ)P(Z∣X,θg)dZ−∫ZlogP(Z∣X,θ)P(Z∣X,θg)dZ
左
端
=
log
P
(
X
∣
θ
)
左端=\log P(X \vert \theta)
左端=logP(X∣θ)
令
Q
(
θ
,
θ
g
)
=
∫
Z
log
P
(
X
,
Z
∣
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
Q(\theta,\theta^g)=\int_Z \log P(X,Z \vert \theta)P(Z|X,\theta^g)\mathrm{d}Z
Q(θ,θg)=∫ZlogP(X,Z∣θ)P(Z∣X,θg)dZ
H
(
θ
,
θ
g
)
=
∫
Z
log
P
(
Z
∣
X
,
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
H(\theta,\theta^g)=\int_Z \log P(Z \vert X,\theta) P(Z|X,\theta^g)\mathrm{d}Z
H(θ,θg)=∫ZlogP(Z∣X,θ)P(Z∣X,θg)dZ
故：
右
端
=
Q
(
θ
,
θ
g
)
−
H
(
θ
,
θ
g
)
右端=Q(\theta,\theta^g)-H(\theta,\theta^g)
右端=Q(θ,θg)−H(θ,θg)
假设：
∀
θ
,
都
有
H
(
θ
g
,
θ
g
)
≥
H
(
θ
,
θ
g
)
\forall \theta,都有H(\theta^g,\theta^g)\geq H(\theta,\theta^g)
∀θ,都有H(θg,θg)≥H(θ,θg),得：
H
(
θ
g
,
θ
g
)
≥
H
(
θ
(
g
+
1
)
,
θ
g
)
H(\theta^g,\theta^g)\geq H(\theta^{(g+1)},\theta^g)
H(θg,θg)≥H(θ(g+1),θg);又由
(
4
)
(4)
(4)式，得
Q
(
θ
g
,
θ
g
)
≤
Q
(
θ
(
g
+
1
)
,
θ
g
)
Q(\theta^g,\theta^g) \leq Q(\theta^{(g+1)},\theta^g)
Q(θg,θg)≤Q(θ(g+1),θg)故：
Q
(
θ
g
,
θ
g
)
−
H
(
θ
g
,
θ
g
)
≤
Q
(
θ
(
g
+
1
)
,
θ
g
)
−
H
(
θ
(
g
+
1
)
,
θ
g
)
Q(\theta^g,\theta^g)-H(\theta^g,\theta^g) \leq Q(\theta^{(g+1)},\theta^g)-H(\theta^{(g+1)},\theta^g)
Q(θg,θg)−H(θg,θg)≤Q(θ(g+1),θg)−H(θ(g+1),θg)
由此可得
log
P
(
X
∣
θ
(
g
+
1
)
)
≥
log
P
(
X
∣
θ
g
)
\log P(X \vert \theta^{(g+1)}) \geq \log P(X \vert \theta^{g})
logP(X∣θ(g+1))≥logP(X∣θg).
现证满足假设：
∀
θ
,
都
有
H
(
θ
g
,
θ
g
)
≥
H
(
θ
,
θ
g
)
\forall \theta,都有H(\theta^g,\theta^g)\geq H(\theta,\theta^g)
∀θ,都有H(θg,θg)≥H(θ,θg)
证明：
H
(
θ
g
,
θ
g
)
−
H
(
θ
,
θ
g
)
=
∫
Z
log
P
(
Z
∣
X
,
θ
g
)
P
(
Z
∣
X
,
θ
g
)
d
Z
−
∫
Z
log
P
(
Z
∣
X
,
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
=
∫
Z
−
log
P
(
Z
∣
X
,
θ
)
P
(
Z
∣
X
,
θ
g
)
P
(
Z
∣
X
,
θ
g
)
d
Z
≥
∗
0
\begin{aligned}H(\theta^g,\theta^g)- H(\theta,\theta^g) &=\int_Z \log P(Z \vert X,\theta^g) P(Z|X,\theta^g)\mathrm{d}Z-\int_Z \log P(Z \vert X,\theta) P(Z|X,\theta^g)\mathrm{d}Z \\ &=\int_Z -\log \frac{P(Z \vert X,\theta)}{P(Z \vert X,\theta^g)} P(Z|X,\theta^g)\mathrm{d}Z \\& \overset{*}{\geq} 0\end{aligned}
H(θg,θg)−H(θ,θg)=∫ZlogP(Z∣X,θg)P(Z∣X,θg)dZ−∫ZlogP(Z∣X,θ)P(Z∣X,θg)dZ=∫Z−logP(Z∣X,θg)P(Z∣X,θ)P(Z∣X,θg)dZ≥∗0
（ *）步得由来：
f ( x ) = − log x f(x)=-\log x f(x)=−logx是一个凸函数，即满足定义域内 ∀ x , y ， λ ∈ [ 0 , 1 ] \forall x,y，\lambda\in[0,1] ∀x,y，λ∈[0,1]， s . t . λ f ( x ) + ( 1 − λ ) f ( y ) ≥ f ( λ x + ( 1 − λ ) y ) \mathrm{s.t.} \lambda f(x)+(1-\lambda)f(y)\geq f(\lambda x+(1-\lambda)y) s.t.λf(x)+(1−λ)f(y)≥f(λx+(1−λ)y)
即：两点连线在函数的上方.
还可以将式子两边视作期望：函数的期望大于等于期望的函数；
故函数 − log P ( Z ∣ X , θ ) P ( Z ∣ X , θ g ) -\log \frac{P(Z \vert X,\theta)}{P(Z \vert X,\theta^g)} −logP(Z∣X,θg)P(Z∣X,θ)的期望等于它期望的函数：
∫ Z − log P ( Z ∣ X , θ ) P ( Z ∣ X , θ g ) P ( Z ∣ X , θ g ) d Z ≥ − log { ∫ Z P ( Z ∣ X , θ ) P ( Z ∣ X , θ g ) P ( Z ∣ X , θ g ) d Z } ≥ − log 1 ≥ 0 \begin{aligned}\int_Z -\log \frac{P(Z \vert X,\theta)}{P(Z \vert X,\theta^g)} P(Z|X,\theta^g)\mathrm{d}Z &\geq -\log\{\int_Z \frac{P(Z \vert X,\theta)}{P(Z \vert X,\theta^g)}P(Z|X,\theta^g)\mathrm{d}Z\} \\ &\geq -\log1 \\&\geq 0\end{aligned} ∫Z−logP(Z∣X,θg)P(Z∣X,θ)P(Z∣X,θg)dZ≥−log{∫ZP(Z∣X,θg)P(Z∣X,θ)P(Z∣X,θg)dZ}≥−log1≥0
三.EM算法的步骤
由：
θ
(
g
+
1
)
=
arg
max
θ
∫
Z
log
P
(
X
,
Z
∣
θ
)
P
(
Z
∣
X
,
θ
g
)
d
Z
\begin{aligned}\theta^{(g+1)} &=\arg\max_\theta \int_Z\log P(X,Z \vert\theta)P(Z \vert X,\theta^{g})\mathrm{d}Z \end{aligned}
θ(g+1)=argθmax∫ZlogP(X,Z∣θ)P(Z∣X,θg)dZ
我们只需要得知每个模型的
P
(
X
,
Z
∣
θ
)
P(X,Z \vert\theta)
P(X,Z∣θ)和
P
(
Z
∣
X
,
θ
g
)
P(Z \vert X,\theta^{g})
P(Z∣X,θg)即可迭代求出
θ
^
\hat \theta
θ^
四.混合高斯举例
- 求
P
(
X
,
Z
∣
θ
)
P(X,Z \vert\theta)
P(X,Z∣θ)
P ( X , Z ∣ θ ) = ∏ i = 1 n P ( x i , z i ∣ θ ) = ∏ i = 1 n P ( x i ∣ z i , θ ) P ( z i ∣ θ ) = ∏ i = 1 n λ z i N ( x i ∣ μ z i , σ z i 2 ) P(X,Z \vert\theta)=\prod_{i=1}^nP(x_i,z_i|\theta)=\prod_{i=1}^nP(x_i|z_i,\theta)P(z_i|\theta)=\prod_{i=1}^n\lambda_{z_i}N(x_i|\mu_{z_i},\sigma^2_{z_i}) P(X,Z∣θ)=i=1∏nP(xi,zi∣θ)=i=1∏nP(xi∣zi,θ)P(zi∣θ)=i=1∏nλziN(xi∣μzi,σzi2) - 求
P
(
Z
∣
X
,
θ
g
)
P(Z \vert X,\theta^{g})
P(Z∣X,θg)
P ( Z ∣ X , θ g ) = ∏ i = 1 n P ( z i ∣ x i , θ g ) = ∗ ∗ λ z i N ( x i ∣ μ z i , σ z i 2 ) ∑ z i = 1 k λ z i N ( x i ∣ μ z i , σ z i 2 ) \begin{aligned}P(Z \vert X,\theta^{g})& =\prod_{i=1}^n P(z_i \vert x_i,\theta^{g})\\ &\overset{**}{=}\frac{\lambda_{z_i}N(x_i|\mu_{z_i},\sigma^2_{z_i})}{\sum_{z_i=1}^k\lambda_{z_i}N(x_i|\mu_{z_i},\sigma^2_{z_i})}\end{aligned} P(Z∣X,θg)=i=1∏nP(zi∣xi,θg)=∗∗∑zi=1kλziN(xi∣μzi,σzi2)λziN(xi∣μzi,σzi2)
(**)是由全概率公式： P ( A ∣ B ) = P ( B ∣ A ) P ( A ) ∑ i = 1 n P ( B ∣ A ) P ( A ) P(A|B)=\frac{P(B|A)P(A)}{\sum_{i=1}^n P(B|A)P(A)} P(A∣B)=∑i=1nP(B∣A)P(A)P(B∣A)P(A)
推导而来
-
带入 ( 4 ) (4) (4)式：
- E-step(即求期望步骤)：
原 式 = ∑ z 1 = 1 k ∑ z 2 = 1 k ⋯ ∑ z n = 1 k [ ∑ i = 1 n ( log λ z i + log N ( x i ∣ μ z i , σ z i 2 ) ) ∏ i = 1 n P ( z i ∣ x i , θ g ) ] = ∗ ∗ ∗ ∑ i = 1 n ∑ z i = 1 k ( log λ z i + log N ( x i ∣ μ z i , σ z i 2 ) ) P ( z i ∣ x i , θ g ) \begin{aligned}原式& =\sum_{z_1=1}^{k}\sum_{z_2=1}^{k}\dots\sum_{z_n=1}^{k}[\sum_{i=1}^n(\log \lambda_{z_i}+\log N(x_i|\mu_{z_i},\sigma^2_{z_i}))\prod_{i=1}^n P(z_i \vert x_i,\theta^{g})]\\ &\overset{***}{=}\sum_{i=1}^n\sum_{z_i=1}^{k}(\log \lambda_{z_i}+\log N(x_i|\mu_{z_i},\sigma^2_{z_i}))P(z_i|x_i,\theta^g)\end{aligned} 原式=z1=1∑kz2=1∑k⋯zn=1∑k[i=1∑n(logλzi+logN(xi∣μzi,σzi2))i=1∏nP(zi∣xi,θg)]=∗∗∗i=1∑nzi=1∑k(logλzi+logN(xi∣μzi,σzi2))P(zi∣xi,θg)
(***)的由来：
令 f i ( z i ) = log λ z i + log N ( x i ∣ μ z i , σ z i 2 ) , P ( z 1 , z 2 , … , z n ) = ∏ i = 1 n P ( z i ∣ x i , θ g ) f_i(z_i)=\log \lambda_{z_i}+\log N(x_i|\mu_{z_i},\sigma^2_{z_i}),P(z_1,z_2,\dots,z_n)=\prod_{i=1}^n P(z_i \vert x_i,\theta^{g}) fi(zi)=logλzi+logN(xi∣μzi,σzi2),P(z1,z2,…,zn)=∏i=1nP(zi∣xi,θg)
原 式 = ∑ z 1 = 1 k ∑ z 2 = 1 k ⋯ ∑ z n = 1 k ( f 1 ( z 1 ) + f 2 ( z 2 ) + f n ( z n ) ) P ( z 1 , z 2 , … , z n ) = ∑ z 1 = 1 k ∑ z 2 = 1 k ⋯ ∑ z n = 1 k f 1 ( z 1 ) P ( z 1 , z 2 , … , z n ) + … = ∑ z 1 = 1 k f 1 ( z 1 ) ∑ z 2 = 1 k ⋯ ∑ z n = 1 k P ( z 1 , z 2 , … , z n ) + … = ∑ z 1 = 1 k f 1 ( z 1 ) P ( z 1 ) + … \begin{aligned}原式 &=\sum_{z_1=1}^{k}\sum_{z_2=1}^{k}\dots\sum_{z_n=1}^{k}(f_1(z_1)+f_2(z_2)+f_n(z_n))P(z_1,z_2,\dots,z_n) \\&=\sum_{z_1=1}^{k}\sum_{z_2=1}^{k}\dots\sum_{z_n=1}^{k}f_1(z_1)P(z_1,z_2,\dots,z_n) +\dots \\ &=\sum_{z_1=1}^{k}f_1(z_1)\sum_{z_2=1}^{k}\dots\sum_{z_n=1}^{k}P(z_1,z_2,\dots,z_n) +\dots \\&=\sum_{z_1=1}^kf_1(z_1)P(z_1)+\dots\end{aligned} 原式=z1=1∑kz2=1∑k⋯zn=1∑k(f1(z1)+f2(z2)+fn(zn))P(z1,z2,…,zn)=z1=1∑kz2=1∑k⋯zn=1∑kf1(z1)P(z1,z2,…,zn)+…=z1=1∑kf1(z1)z2=1∑k⋯zn=1∑kP(z1,z2,…,zn)+…=z1=1∑kf1(z1)P(z1)+…- M-step(argmax步骤)
- 求
λ
z
i
\lambda_{z_i}
λzi：
d log λ z i P ( z i ∣ x i , θ g ) d λ z i = 令 0 \frac{\mathrm{d}\log \lambda_{z_i}P(z_i|x_i,\theta^g)}{\mathrm{d}\lambda_{z_i}} \overset{令}{=}0 dλzidlogλziP(zi∣xi,θg)=令0
s . t . ∑ z i = 1 k = 1 \mathrm{s.t.} \sum_{z_i=1}^{k}=1 s.t.zi=1∑k=1
用拉格朗日乘数法求解即可.
解得： λ z i = 1 n ∑ i = 1 n P ( z i ∣ x i , θ ) \lambda_{z_i}=\frac{1}{n}\sum_{i=1}^{n}P(z_i|x_i,\theta) λzi=n1∑i=1nP(zi∣xi,θ)
含义：所有的高斯的占比的和求平均. - 求
μ
i
,
σ
i
2
\mu_i,\sigma^2_i
μi,σi2:
用矩阵求导为零计算所得.
综上所述：
λ l ( g + 1 ) = 1 n ∑ l = 1 n P ( l ∣ x l , θ g ) μ l ( g + 1 ) = ∑ l = 1 n x l P ( l ∣ x l , θ g ) ∑ l = 1 n P ( z l ∣ x l , θ g ) σ l 2 ( g + 1 ) = ∑ l = 1 n ( x l − μ l l + 1 ) ( x l − μ l l + 1 ) T P ( l ∣ x l , θ g ) ∑ l = 1 n P ( l ∣ x l , θ g ) \begin{aligned}\lambda_{l}^{(g+1)}&=\frac{1}{n}\sum_{l=1}^{n}P(l|x_l,\theta^g)\\ \mu_l^{(g+1)}&=\frac{\sum_{l=1}^{n}x_lP(l|x_l,\theta^g)}{\sum_{l=1}^{n}P(z_l|x_l,\theta^g)}\\{\sigma^2_l}^{(g+1)} &=\frac{\sum_{l=1}^{n}(x_l-\mu_l^{l+1})(x_l-\mu_l^{l+1})^\mathrm{T}P(l|x_l,\theta^g)}{\sum_{l=1}^{n}P(l|x_l,\theta^g)}\end{aligned} λl(g+1)μl(g+1)σl2(g+1)=n1l=1∑nP(l∣xl,θg)=∑l=1nP(zl∣xl,θg)∑l=1nxlP(l∣xl,θg)=∑l=1nP(l∣xl,θg)∑l=1n(xl−μll+1)(xl−μll+1)TP(l∣xl,θg)
- 求
λ
z
i
\lambda_{z_i}
λzi：
- E-step(即求期望步骤)：
五.EM算法推广——GEM
…