代码地址:6.1公布
笔者能力有限,如有错误请指正!感谢您的阅读!
观测变量:直接观测的数据
潜变量:
如:聚类问题,潜变量是类别(未知),观测变量是数据点,给定观测变量,如果推断哪些是同一类?K-means
给定一个含有N个数据点的集合 { x 1 , x 2 , … , x N } \left\{\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{N}\right\} {x1,x2,…,xN}, x n ∈ R D \mathbf{x}_{\mathbf{n}} \in R^{D} xn∈RD,聚类的目标是将此N个数据点聚类到K个类别中,且假设K给定。
K-means思路:
引入潜变量
模型优化:两阶段迭代优化(简单EM)
选择初始化的
μ
k
\boldsymbol{\mu}_{k}
μk值,并保持
μ
k
\boldsymbol{\mu}_{k}
μk固定,关于$r_{nk}
最
小
化
最小化
最小化J$(E步)
r
n
k
=
{
1
if
k
=
arg
min
j
∥
x
n
−
μ
j
∥
2
0
otherwise
r_{n k}=\left\{\begin{array}{ll} 1 & \text { if } k=\arg \min _{j}\left\|\mathbf{x}_{n}-\boldsymbol{\mu}_{j}\right\|^{2} \\ 0 & \text { otherwise } \end{array}\right.
rnk={10 if k=argminj∥∥xn−μj∥∥2 otherwise
保持
r
n
k
r_{nk}
rnk固定,关于
μ
k
\boldsymbol{\mu}_{k}
μk最小化
J
J
J(M步)
∂
J
∂
μ
k
=
2
∑
n
=
1
N
r
n
k
(
x
n
−
μ
k
)
=
0
→
μ
k
=
∑
n
r
n
k
x
n
∑
n
r
n
k
\frac{\partial J}{\partial \boldsymbol{\mu}_{k}}=2 \sum_{n=1}^{N} r_{n k}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)=0 \rightarrow \boldsymbol{\mu}_{k}=\frac{\sum_{n} r_{n k} \mathbf{x}_{n}}{\sum_{n} r_{n k}}
∂μk∂J=2n=1∑Nrnk(xn−μk)=0→μk=∑nrnk∑nrnkxn
K-means应用:图像分割和压缩
高斯分布
为什么使用高斯分布?1. 高斯分布在自然界的数据中广泛存在,2.中心极限定理:在适当条件下,大量相互独立随机变量的均值经适当标准化后依分布收敛于正太分布。
最大似然估计
假设随机变量
X
X
X 服从分布
p
(
X
∣
θ
)
p(X \mid \boldsymbol{\theta})
p(X∣θ), 即
X
∼
p
(
X
∣
θ
)
X \sim p(X \mid \boldsymbol{\theta})
X∼p(X∣θ), 其中,
θ
\boldsymbol{\theta}
θ 为待估计的参数,如果可以获得N个互相独立的
X
X
X 的采样点
{
x
1
,
x
2
,
…
,
x
N
}
\left\{\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{N}\right\}
{x1,x2,…,xN}, 则似然函数的定义为
p
(
x
1
,
x
2
,
…
,
x
N
)
=
∏
n
=
1
N
p
(
x
n
∣
θ
)
p\left(\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{N}\right)=\prod_{n=1}^{N} p\left(\mathbf{x}_{n} \mid \boldsymbol{\theta}\right)
p(x1,x2,…,xN)=n=1∏Np(xn∣θ)
在实际使用中,一般采用对数似然函数:
ln
p
(
x
1
,
x
2
,
…
,
x
N
∣
θ
)
=
∑
n
=
1
N
ln
p
(
x
n
∣
θ
)
\ln p\left(\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{N} \mid \boldsymbol{\theta}\right)=\sum_{n=1}^{N} \ln p\left(\mathbf{x}_{n} \mid \boldsymbol{\theta}\right)
lnp(x1,x2,…,xN∣θ)=n=1∑Nlnp(xn∣θ)
参数
θ
\boldsymbol{\theta}
θ 的最大似然估计为:
θ
=
arg
max
θ
ln
p
(
x
1
,
x
2
,
…
,
x
N
∣
θ
)
\boldsymbol{\theta}=\arg \max _{\boldsymbol{\theta}} \ln p\left(\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{N} \mid \boldsymbol{\theta}\right)
θ=argθmaxlnp(x1,x2,…,xN∣θ)
高斯模型的最大似然估计
μ M L = 1 N ∑ n x n , Σ M L = 1 N ∑ n ( x n − μ M L ) ( x n − μ M L ) T \boldsymbol{\mu}_{M L}=\frac{1}{N} \sum_{n} \mathbf{x}_{n}, \boldsymbol{\Sigma}_{M L}=\frac{1}{N} \sum_{n}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{M L}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{M L}\right)^{T} μML=N1n∑xn,ΣML=N1n∑(xn−μML)(xn−μML)T
高斯混合分布
p
(
x
)
=
∑
k
=
1
K
π
k
N
(
x
∣
μ
k
,
Σ
k
)
(2)
p(\mathbf{x})=\sum_{k=1}^{K} \pi_{k} \mathcal{N} {\left(\mathbf{x} \mid \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right)} \tag{2}
p(x)=k=1∑KπkN(x∣μk,Σk)(2)
N ( x ∣ μ , Σ ) = 1 ( 2 π ) D / 2 1 ∣ Σ ∣ 1 / 2 exp { − 1 2 ( x − μ ) T Σ − 1 ( x − μ ) } \mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}, \mathbf{\Sigma})=\frac{1}{(2 \pi)^{D / 2}} \frac{1}{|\boldsymbol{\Sigma}|^{1 / 2}} \exp \left\{-\frac{1}{2}(\mathbf{x}-\boldsymbol{\mu})^{\mathrm{T}} \boldsymbol{\Sigma}^{-1}(\mathbf{x}-\boldsymbol{\mu})\right\} N(x∣μ,Σ)=(2π)D/21∣Σ∣1/21exp{−21(x−μ)TΣ−1(x−μ)}
0
⩽
π
k
⩽
1
∑
k
=
1
K
π
k
=
1
0 \leqslant \pi_{k} \leqslant 1 \quad \sum_{k=1}^{K} \pi_{k}=1
0⩽πk⩽1k=1∑Kπk=1
π
k
\pi _{k}
πk,
μ
k
\boldsymbol{\mu}_k
μk,
Σ
k
\boldsymbol{\Sigma}_k
Σk为待估计参数。
π k \pi _{k} πk的解释(直观理解为第k个高斯所占的比重)
引入一个K维 one-hot(只有一维为1, 其余维度为0) 向量 z = [ z 1 , … , z k , … , z K ] , z k ∈ { 0 , 1 } , Σ k z k = 1 z=\left[z_{1}, \ldots, z_{k}, \ldots, z_{K}\right], z_{k} \in\{0,1\}, \Sigma_{k} z_{k}=1 z=[z1,…,zk,…,zK],zk∈{0,1},Σkzk=1, 概率 P ( z k = 1 ) P\left(z_{k}=1\right) P(zk=1) 为 向量z的第k维为的先验概率 p ( z k = 1 ) = π k p\left(z_{k}=1\right)=\pi_{k} p(zk=1)=πk,向量z的分布可以表示为 p ( z ) = ∏ k = 1 K π k z k p(\mathbf{z})=\prod_{k=1}^{K} \pi_{k}^{z_{k}} p(z)=∏k=1Kπkzk, 等价于 p ( z ) = π k \mathrm{p}(\mathrm{z})=\pi_{\mathrm{k}} p(z)=πk, where z k = 1 \mathrm{z}_{\mathrm{k}}=1 zk=1
条件分布 p ( x ∣ z k = 1 ) = N ( x ∣ μ k , Σ k ) p ( x ∣ z ) = ∏ k = 1 K N ( x ∣ μ k , Σ k ) z k (4) \quad p\left(\mathbf{x} \mid z_{k}=1\right)=\mathcal{N}\left(\mathbf{x} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right) \quad p(\mathbf{x} \mid \mathbf{z})=\prod_{k=1}^{K} \mathcal{N}\left(\mathbf{x} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)^{z_{k}} \tag{4} p(x∣zk=1)=N(x∣μk,Σk)p(x∣z)=k=1∏KN(x∣μk,Σk)zk(4)
联合分布
p ( x , z ) = ∏ k = 1 K π k z k N ( x ∣ u k , Σ k ) z k p(\boldsymbol{x}, \boldsymbol{z})=\prod_{k=1}^{K} \pi_{k}^{z_{k}} N\left(x \mid u_{k}, \Sigma_{k}\right)^{{z}_{k}} p(x,z)=k=1∏KπkzkN(x∣uk,Σk)zk
边缘分布
后验分布
γ
(
z
k
)
≡
p
(
z
k
=
1
∣
x
)
=
p
(
z
k
=
1
)
p
(
x
∣
z
k
=
1
)
∑
j
=
1
K
p
(
z
j
=
1
)
p
(
x
∣
z
j
=
1
)
=
π
k
N
(
x
∣
μ
k
,
Σ
k
)
∑
j
=
1
K
π
j
N
(
x
∣
μ
j
,
Σ
j
)
(3)
\begin{aligned} \gamma\left(z_{k}\right) \equiv p\left(z_{k}=1 \mid \mathbf{x}\right) &=\frac{p\left(z_{k}=1\right) p\left(\mathbf{x} \mid z_{k}=1\right)}{\sum_{j=1}^{K} p\left(z_{j}=1\right) p\left(\mathbf{x} \mid z_{j}=1\right)} \\ &=\frac{\pi_{k} \mathcal{N}\left(\mathbf{x} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\mathbf{x} \mid \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)} \end{aligned} \tag{3}
γ(zk)≡p(zk=1∣x)=∑j=1Kp(zj=1)p(x∣zj=1)p(zk=1)p(x∣zk=1)=∑j=1KπjN(x∣μj,Σj)πkN(x∣μk,Σk)(3)
γ ( z k ) \gamma\left(z_{k}\right) γ(zk)为得到观测 x x x后, z k = 1 z_{k}=1 zk=1的后验概率,理解为第k个高斯成分对于生成观测 x x x的贡献值。
GMM对数似然函数
ln
p
(
X
∣
π
,
μ
,
Σ
)
=
∑
n
=
1
N
ln
{
∑
k
=
1
K
π
k
N
(
x
n
∣
μ
k
,
Σ
k
)
}
\ln p(\mathbf{X} \mid \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma})=\sum_{n=1}^{N} \ln \left\{\sum_{k=1}^{K} \pi_{k} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\}
lnp(X∣π,μ,Σ)=n=1∑Nln{k=1∑KπkN(xn∣μk,Σk)}
其中,
X
=
[
x
1
T
⋮
x
N
T
]
\mathbf{X}=\left[\begin{array}{c}\mathbf{x}_{1}^{T} \\ \vdots \\ \mathbf{x}_{N}^{T}\end{array}\right]
X=⎣⎢⎡x1T⋮xNT⎦⎥⎤,给出潜变量矩阵定义
Z
=
[
z
1
T
⋮
z
N
T
]
\mathbf{Z}=\left[\begin{array}{c}\mathbf{z}_{1}^{T} \\ \vdots \\ \mathbf{z}_{N}^{T}\end{array}\right]
Z=⎣⎢⎡z1T⋮zNT⎦⎥⎤。
N
(
x
n
∣
μ
k
,
Σ
k
)
\mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)
N(xn∣μk,Σk)由公式(1)计算。
GMM模型参数估计的EM算法(最大似然准则)
计算似然函数 ln p ( X ∣ π , μ , Σ ) \ln p(\mathbf{X} \mid \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma}) lnp(X∣π,μ,Σ)分别对参数 π , μ , Σ \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma} π,μ,Σ求导:
对 μ \boldsymbol{\mu} μ求导:
0 = ∑ n = 1 N π k N ( x n ∣ μ k , Σ k ) ∑ j π j N ( x n ∣ μ j , Σ j ) ⏟ γ ( z n k ) Σ k − 1 ( x n − μ k ) 0=\sum_{n=1}^{N} \underbrace{\frac{\pi_{k} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{j}, \mathbf{\Sigma}_{j}\right)}}_{\gamma\left(z_{n k}\right)} \boldsymbol{\Sigma}_{k}^{-1}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right) 0=∑n=1Nγ(znk) ∑jπjN(xn∣μj,Σj)πkN(xn∣μk,Σk)Σk−1(xn−μk)
μ k = 1 N k ∑ n = 1 N γ ( z n k ) x n N k = ∑ n = 1 N γ ( z n k ) \boldsymbol{\mu}_{k}=\frac{1}{N_{k}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right) \mathbf{x}_{n} \quad N_{k}=\sum_{n=1}^{N} \gamma\left(z_{n k}\right) μk=Nk1∑n=1Nγ(znk)xnNk=∑n=1Nγ(znk)
对 Σ \boldsymbol{\Sigma} Σ求导:
0 = ∑ n = 1 N π k N ( x n ∣ μ k , Σ k ) ∑ j π j N ( x n ∣ μ j , Σ j ) ⏟ γ ( z n k ) ( 1 − ∣ Σ k ∣ ) 0=\sum_{n=1}^{N} \underbrace{\frac{\pi_{k} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{j}, \mathbf{\Sigma}_{j}\right)}}_{\gamma\left(z_{n k}\right)} \left(1-|\boldsymbol{\Sigma_k}|\right) 0=∑n=1Nγ(znk) ∑jπjN(xn∣μj,Σj)πkN(xn∣μk,Σk)(1−∣Σk∣)
Σ k = 1 N k ∑ n = 1 N γ ( z n k ) ( x n − μ k ) ( x n − μ k ) T \boldsymbol{\Sigma}_{k}=\frac{1}{N_{k}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}} Σk=Nk1∑n=1Nγ(znk)(xn−μk)(xn−μk)T
对
π
\boldsymbol{\pi}
π求导:
ln
p
(
X
∣
π
,
μ
,
Σ
)
+
λ
(
∑
k
=
1
K
π
k
−
1
)
0
=
∑
n
=
1
N
N
(
x
n
∣
μ
k
,
Σ
k
)
∑
j
π
j
N
(
x
n
∣
μ
j
,
Σ
j
)
+
λ
π
k
=
N
k
N
\begin{array}{l} \ln p(\mathbf{X} \mid \boldsymbol{\pi}, \boldsymbol{\mu}, \mathbf{\Sigma})+\lambda\left(\sum_{k=1}^{K} \pi_{k}-1\right) \\ 0=\sum_{n=1}^{N} \frac{\mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)}+\lambda \\ \pi_{k}=\frac{N_{k}}{N} \end{array}
lnp(X∣π,μ,Σ)+λ(∑k=1Kπk−1)0=∑n=1N∑jπjN(xn∣μj,Σj)N(xn∣μk,Σk)+λπk=NNk
用拉格朗日乘子法,求解
λ
\lambda
λ:
0
=
∑
n
=
1
N
N
(
x
n
∣
μ
k
,
Σ
k
)
∑
j
π
j
N
(
x
n
∣
μ
j
,
Σ
j
)
+
λ
0=\sum_{n=1}^{N} \frac{\mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)}+\lambda
0=n=1∑N∑jπjN(xn∣μj,Σj)N(xn∣μk,Σk)+λ
等号两边同时乘以
π
k
\pi_{k}
πk, 并对k求和
0
=
∑
n
=
1
N
∑
k
π
k
N
(
x
n
∣
μ
k
,
Σ
k
)
∑
j
π
j
N
(
x
n
∣
μ
j
,
Σ
j
)
+
λ
∑
k
π
k
0
=
∑
n
=
1
N
∑
k
π
k
N
(
x
n
∣
μ
k
,
Σ
k
)
∑
j
π
j
N
(
x
n
∣
μ
j
,
Σ
j
)
+
λ
λ
=
−
N
\begin{array}{c} 0=\sum_{n=1}^{N} \sum_{k} \frac{\pi_{k} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)}+\lambda \sum_{k} \pi_{k} \\ 0=\sum_{n=1}^{N} \frac{\sum_{k} \pi_{k} \mathcal{N}\left(\mathbf{x}_{\mathrm{n}} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{j}, \mathbf{\Sigma}_{j}\right)}+\lambda \\ \lambda=-N \end{array}
0=∑n=1N∑k∑jπjN(xn∣μj,Σj)πkN(xn∣μk,Σk)+λ∑kπk0=∑n=1N∑jπjN(xn∣μj,Σj)∑kπkN(xn∣μk,Σk)+λλ=−N
上述参数估计方法并不是一个严格的解析解,因为公式中有后验概率 γ ( z n k ) \gamma\left(z_{n k}\right) γ(znk),依赖于每个高斯的代估计参数。上述推导过程给出了一个迭代的估计参数的过程,并能保证似然逐步增加。
给定一个GMM模型, 优化目标是寻找使似然函数最大的各个高斯成分的均值向量、协方差矩阵和混合系数
K-means可以看作GMM模型的一个特殊情况,假设公式
(
2
)
(2)
(2)中,每个单高斯的分布都具有相同的协方差矩阵,并且有
Σ
=
ϵ
I
\boldsymbol{\Sigma}=\epsilon \mathbf{I}
Σ=ϵI,
I
\mathbf{I}
I是单位矩阵,高斯分布可以简化为:
p
(
x
∣
μ
k
,
Σ
k
)
=
1
(
2
π
ϵ
)
1
2
exp
{
−
1
2
ϵ
∥
x
−
μ
k
∥
2
}
p\left(\mathbf{x} \mid \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right)=\frac{1}{(2 \pi \epsilon)^{\frac{1}{2}}} \exp \left\{-\frac{1}{2 \epsilon}\left\|\mathbf{x}-\boldsymbol{\mu}_{k}\right\|^{2}\right\}
p(x∣μk,Σk)=(2πϵ)211exp{−2ϵ1∥x−μk∥2}
公式
(
3
)
(3)
(3)中的后验概率变为:
γ
(
z
n
k
)
=
π
k
exp
{
−
1
2
ϵ
∥
x
n
−
μ
k
∥
2
}
∑
j
π
j
exp
{
−
1
2
ϵ
∥
x
n
−
μ
j
∥
2
}
\gamma\left(z_{n k}\right)=\frac{\pi_{k} \exp \left\{-\frac{1}{2 \epsilon}\left\|\mathbf{x}_{\mathrm{n}}-\boldsymbol{\mu}_{k}\right\|^{2}\right\}}{\sum_{j} \pi_{j} \exp \left\{-\frac{1}{2 \epsilon}\left\|\mathbf{x}_{\mathrm{n}}-\boldsymbol{\mu}_{\mathrm{j}}\right\|^{2}\right\}}
γ(znk)=∑jπjexp{−2ϵ1∥∥xn−μj∥∥2}πkexp{−2ϵ1∥xn−μk∥2}
当
ϵ
→
0
\epsilon \rightarrow 0
ϵ→0,
−
1
2
ϵ
∥
x
n
−
μ
j
∥
2
→
−
∞
,
exp
{
−
1
2
ϵ
∥
x
n
−
μ
j
∥
2
}
→
0
-\frac{1}{2 \epsilon}\left\|\mathbf{x}_{\mathrm{n}}-\boldsymbol{\mu}_{\mathrm{j}}\right\|^{2} \rightarrow-\infty, \quad \exp \left\{-\frac{1}{2 \epsilon}\left\|\mathbf{x}_{\mathrm{n}}-\boldsymbol{\mu}_{\mathrm{j}}\right\|^{2}\right\} \rightarrow 0
−2ϵ1∥∥xn−μj∥∥2→−∞,exp{−2ϵ1∥∥xn−μj∥∥2}→0,对于分母中,假设第m项
∥
x
n
−
μ
m
∥
2
\left\|\mathbf{x}_{\mathrm{n}}-\boldsymbol{\mu}_{\mathrm{m}}\right\|^{2}
∥xn−μm∥2最小,那么分母上j=m这一项将在
ϵ
→
0
\epsilon \rightarrow 0
ϵ→0的时候以最慢的速度趋于0,因此只有分子上k=m时,
γ
(
z
n
k
)
→
1
,
k
≠
m
\gamma\left(z_{n k}\right) \rightarrow 1, k \neq m
γ(znk)→1,k=m,
γ
(
z
n
k
)
→
0
\gamma\left(z_{n k}\right) \rightarrow 0
γ(znk)→0,显然
γ
(
z
n
k
)
→
r
n
k
\gamma\left(z_{n k}\right) \rightarrow r_{nk}
γ(znk)→rnk。
K-means是一种硬对齐方式,某个数据点只能对应在某个类别上,GMM是一种软对齐方式,使用后验概率来表示某个数据点由某个类别产生的概率。
上述GMM参数估计过程中已经使用到GMM算法,现在具体看一下EM算法。首先通过一个例子来体会。
问题:假设随机抽取100个男生和女生的身高数据,假设男生和女生的身高分布分别服从高斯分布 N ( x ∣ μ M , Σ M ) \mathcal{N}\left(\mathrm{x} \mid \mu_{M}, \Sigma_{M}\right) N(x∣μM,ΣM)和 N ( x ∣ μ W , Σ W ) \mathcal{N}\left(\mathrm{x} \mid \mu_{W}, \Sigma_{W}\right) N(x∣μW,ΣW),请用最大似然法估计男生和女生身高分布的均值和方差。
这里分为两种情况:
情况1:已经知道每个数据对应的性别
男 | 女 | 女 | 男 | 女 | 女 |
---|---|---|---|---|---|
178 | 175 | 170 | 175 | 168 | 169 |
μ M = 1 N M ∑ m = 1 N M x m , Σ M = 1 N M ∑ m = 1 N M ( x m − μ M ) \mu_{M}=\frac{1}{\mathrm{~N}_{\mathrm{M}}} \sum_{m=1}^{N_{M}} x_{m}, \Sigma_{M}=\frac{1}{\mathrm{~N}_{\mathrm{M}}} \sum_{m=1}^{N_{M}}\left(x_{m}-\mu_{M}\right) μM= NM1∑m=1NMxm,ΣM= NM1∑m=1NM(xm−μM)
其中 N M N_M NM为男生总人数, x m x_m xm为每个男生的身高数据。同理,可求出女生的数据。
情况2:果冻大意了,只统计了身高数据
- | - | - | - | - | - |
---|---|---|---|---|---|
178 | 175 | 170 | 175 | 168 | 169 |
这种情况,我们引入一个新的变量 z z z, p ( z i = 1 ) p(z_i = 1) p(zi=1)表示第i个数据为男生身高的概率, p ( z i = 0 ) p(z_i = 0) p(zi=0)表示第i个数据为女生的身高的概率。
μ M = 1 ∑ 1 N p ( z i = 1 ) ∑ m = 1 N M p ( z i = 1 ) x m \mu_{M}=\frac{1}{\sum_{1}^{N} p\left(z_{i}=1\right)} \sum_{m=1}^{N_{M}} p\left(z_{i}=1\right) x_{m} μM=∑1Np(zi=1)1∑m=1NMp(zi=1)xm
如何获得 p ( z i ) p(z_i) p(zi)?可以采用迭代估计法:
含隐变量模型的最大似然估计->EM算法,隐变量与模型参数相互影响,分两步一静一动交替迭代。通用步骤:E步(求期望)、M步(最大化)、重复E、M
给定完全数据 { X , Z } \{\mathrm{X}, \mathrm{Z}\} {X,Z} 的联合概率分布 p ( X , Z ∣ θ ) \mathrm{p}(\mathrm{X}, \mathrm{Z} \mid \theta) p(X,Z∣θ), 待学习参数 θ \theta θ, 优化的目标是寻找 θ \theta θ来最大化似然函数p ( X ∣ θ ) (\mathrm{X} \mid \theta) (X∣θ)
- 初始化 初始化参数 θ o l d \theta^{old} θold
- E步 计算潜变量的后验概率p(Z|X, θ o l d \theta^{{old}} θold)
- M步 使用后验重新估计参数
Q ( θ , θ o l d ) = ∑ Z p ( Z ∣ X , θ o l d ) ln p ( X , Z ∣ θ ) = E Z ∼ p ( Z ∣ X , θ o l d ) [ ln p ( X , Z ∣ θ ) ] Q\left(\theta, \theta^{{old }}\right)=\sum_{Z} \mathrm{p}\left(\mathrm{Z} \mid \mathrm{X}, \theta^{{old }}\right) \ln \mathrm{p}(\mathrm{X}, \mathrm{Z} \mid \theta)=\mathrm{E}_{\mathrm{Z} \sim \mathrm{p}\left(\mathrm{Z} \mid \mathrm{X}, \theta^{ {old }}\right)}[\ln \mathrm{p}(\mathrm{X}, \mathrm{Z} \mid \theta)] Q(θ,θold)=Z∑p(Z∣X,θold)lnp(X,Z∣θ)=EZ∼p(Z∣X,θold)[lnp(X,Z∣θ)]
θ new = arg max θ Q ( θ , θ old ) \theta^{\text {new }}=\underset{\theta}{\arg \max } {Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) θnew =θargmaxQ(θ,θold )
4. 重算似然 重新计算似然函数,重复2-4, 更新参数 θ old ← θ new \theta^{\text {old }} \leftarrow \theta^{\text {new }} θold ←θnew 直至满足收敘条件
将不完全数据(只有观测数据)的边缘分布转换成容易处理的完全数据(观测数据+潜变量)的联合分布
深入理解EM算法
EM算法的目标是寻找潜变量模型的最大似然解。后边我们假定待估计的参数用 θ \theta θ
对数似然函数用完全数据的联合概率表示为:
ln p ( X ∣ θ ) = ln { ∑ Z p ( X , Z ∣ θ ) } \ln p(\mathbf{X} \mid \boldsymbol{\theta})=\ln \left\{\sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta})\right\} lnp(X∣θ)=ln{∑Zp(X,Z∣θ)}
使用EM算法,一般认为完全数据的联合概率分布的似然 ln p ( X , Z ∣ θ ) \ln p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta}) lnp(X,Z∣θ)容易计算。实际上,完全数据{X,Z}无法获取,但是潜变量Z的后验概率分布 p ( Z ∣ X , θ ) p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}) p(Z∣X,θ)可以进行估计。
计算完全数据的似然 ln p ( X , Z ∣ θ ) \ln p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta}) lnp(X,Z∣θ)在 Z ∼ p ( Z ∣ X , θ old ) \mathbf{Z} \sim p\left(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}^{\text {old }}\right) Z∼p(Z∣X,θold )时,关于变量Z的期望:
Q ( θ , θ o l d ) = ∑ Z p ( Z ∣ X , θ o l d ) ln p ( X , Z ∣ θ ) = E Z ∼ p ( Z ∣ X , θ o l d ) [ ln p ( X , Z ∣ θ ) ] Q\left(\theta, \theta^{{old }}\right)=\sum_{Z} \mathrm{p}\left(\mathrm{Z} \mid \mathrm{X}, \theta^{{old }}\right) \ln \mathrm{p}(\mathrm{X}, \mathrm{Z} \mid \theta)=\mathrm{E}_{\mathrm{Z} \sim \mathrm{p}\left(\mathrm{Z} \mid \mathrm{X}, \theta^{ {old }}\right)}[\ln \mathrm{p}(\mathrm{X}, \mathrm{Z} \mid \theta)] Q(θ,θold)=Z∑p(Z∣X,θold)lnp(X,Z∣θ)=EZ∼p(Z∣X,θold)[lnp(X,Z∣θ)]
当尝试使用EM算法来解决自己的问题时,需要明确Q函数。
在之前的推导中,我们引入了潜变量Z,但并没用用到完全数据的联合概率分布,而是直接对不完全数据X的对数似然进行了求解。根据EM算法的通用步骤,首先考虑完全数据的似然函数:
p
(
X
,
Z
∣
μ
,
Σ
,
π
)
=
∏
n
=
1
N
∏
k
=
1
K
π
k
z
n
k
N
(
x
n
∣
μ
k
,
Σ
k
)
z
n
k
ln
p
(
X
,
Z
∣
μ
,
Σ
,
π
)
=
∑
n
=
1
N
∑
k
=
1
K
z
n
k
{
ln
π
k
+
ln
N
(
x
n
∣
μ
k
,
Σ
k
)
}
\begin{array}{c} p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\mu}, \mathbf{\Sigma}, \boldsymbol{\pi})=\prod_{n=1}^{N} \prod_{k=1}^{K} \pi_{k}^{z_{n k}} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)^{z_{n k}} \\ \ln p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})=\sum_{n=1}^{N} \sum_{k=1}^{K} z_{n k}\left\{\ln \pi_{k}+\ln \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\} \end{array}
p(X,Z∣μ,Σ,π)=∏n=1N∏k=1KπkznkN(xn∣μk,Σk)znklnp(X,Z∣μ,Σ,π)=∑n=1N∑k=1Kznk{lnπk+lnN(xn∣μk,Σk)}
根据公式(4),计算Z的后验概率:
不
理
解
如
何
推
导
可
以
跳
过
\color{red}{不理解如何推导可以跳过}
不理解如何推导可以跳过
p
(
Z
∣
X
,
μ
,
Σ
,
π
)
∝
∏
n
=
1
N
∏
k
=
1
K
[
π
k
N
(
x
n
∣
μ
k
,
Σ
k
)
]
z
n
k
p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi}) \propto \prod_{n=1}^{N} \prod_{k=1}^{K}\left[\pi_{k} \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right]^{z_{n k}}
p(Z∣X,μ,Σ,π)∝n=1∏Nk=1∏K[πkN(xn∣μk,Σk)]znk
完全数据的对数似然关于潜变量的期望值:
E
Z
[
ln
p
(
X
,
Z
∣
μ
,
Σ
,
π
)
]
=
∑
n
=
1
N
∑
k
=
1
K
γ
(
z
n
k
)
{
ln
π
k
+
ln
N
(
x
n
∣
μ
k
,
Σ
k
)
}
\mathbb{E}_{\mathbf{Z}}[\ln p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})]=\sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right)\left\{\ln \pi_{k}+\ln \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\}
EZ[lnp(X,Z∣μ,Σ,π)]=n=1∑Nk=1∑Kγ(znk){lnπk+lnN(xn∣μk,Σk)}
EM算法的一般假设是直接优化观测数据的似然 p ( X ∣ θ ) p(X|\theta) p(X∣θ)十分复杂,但是优化完全数据的似然 p ( X , Z ∣ θ ) p(X,Z|\theta) p(X,Z∣θ)比较容易。引入一个关于变量Z的任意分布 q ( Z ) q(Z) q(Z):
为什么引用任意一个Z的分布?我们只知道Z服从某一个分布,但是并不知道具体服从什么分布,但是后面的推导会证明,无论Z的真实分布是什么都不影响推导。
ln
p
(
X
∣
θ
)
=
∑
Z
q
(
Z
)
ln
p
(
X
∣
θ
)
=
∑
Z
q
(
Z
)
ln
{
p
(
X
,
Z
∣
θ
)
q
(
Z
)
q
(
Z
)
p
(
Z
∣
X
,
θ
)
}
=
∑
Z
q
(
Z
)
ln
p
(
X
,
Z
∣
θ
)
q
(
Z
)
−
∑
Z
q
(
Z
)
ln
p
(
Z
∣
X
,
θ
)
q
(
Z
)
\begin{array}{l} \ln p(\mathbf{X} \mid \boldsymbol{\theta})=\sum_{Z} q(\mathbf{Z}) \ln p(\mathbf{X} \mid \boldsymbol{\theta})=\sum_{\mathbf{Z}} q(\mathbf{Z}) \ln \left\{\frac{p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta})}{q(\mathbf{Z})} \frac{q(\mathbf{Z})}{p(\mathbf{Z} \mid \mathbf{X}, \theta)}\right\}\\ =\sum_{\mathbf{Z}} q(\mathbf{Z}) \ln \frac{p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta})}{q(\mathbf{Z})}-\sum_{\mathbf{Z}} q(\mathbf{Z}) \ln \frac{p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta})}{q(\mathbf{Z})} \end{array}
lnp(X∣θ)=∑Zq(Z)lnp(X∣θ)=∑Zq(Z)ln{q(Z)p(X,Z∣θ)p(Z∣X,θ)q(Z)}=∑Zq(Z)lnq(Z)p(X,Z∣θ)−∑Zq(Z)lnq(Z)p(Z∣X,θ)
令:
L
(
q
,
θ
)
=
∑
Z
q
(
Z
)
ln
p
(
X
,
Z
∣
θ
)
q
(
Z
)
K
L
(
q
∥
p
)
=
−
∑
Z
q
(
Z
)
ln
p
(
Z
∣
X
,
θ
)
q
(
Z
)
\mathcal{L}(q, \boldsymbol{\theta})=\sum_{\mathbf{Z}} q(\mathbf{Z}) \ln \frac{p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta})}{q(\mathbf{Z})} \\ \mathrm{KL}(q \| p)=-\sum_{\mathbf{Z}} q(\mathbf{Z}) \ln \frac{p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta})}{q(\mathbf{Z})} \\
L(q,θ)=Z∑q(Z)lnq(Z)p(X,Z∣θ)KL(q∥p)=−Z∑q(Z)lnq(Z)p(Z∣X,θ)
KL散度是衡量两个概率分布之间差异的一个度量。
则:
ln
p
(
X
∣
θ
)
=
L
(
q
,
θ
)
+
KL
(
q
∥
p
)
\ln p(\mathbf{X} \mid \boldsymbol{\theta})=\mathcal{L}(q, \boldsymbol{\theta})+\operatorname{KL}(q \| p)
lnp(X∣θ)=L(q,θ)+KL(q∥p)
其中: L ( q , θ ) \mathcal{L}(q, \boldsymbol{\theta}) L(q,θ)是 q ( Z ) q(\mathbf{Z}) q(Z)和 θ \boldsymbol{\theta} θ的泛函, K L ( q ∥ p ) ≥ 0 \mathrm{KL}(q \| p) \geq 0 KL(q∥p)≥0,当且仅当 q = p q=p q=p时等号成立。
E步:寻找使 L ( q , θ ) \mathcal{L}(q, \boldsymbol{\theta}) L(q,θ) 最大的 q ( Z ) q(\mathbf{Z}) q(Z), 当 q ( Z ) = q(\mathbf{Z})= q(Z)= p ( Z ∣ X , θ ) p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}) p(Z∣X,θ) 时, K L ( q ∥ p ) = 0 \mathrm{KL}(q \| p)=0 KL(q∥p)=0, 此时 L ( q , θ ) \mathcal{L}(q, \boldsymbol{\theta}) L(q,θ) 最大。
M步: 固定 q ( Z ) q(\mathbf{Z}) q(Z), 寻找使 L ( q , θ ) \mathcal{L}(q, \boldsymbol{\theta}) L(q,θ) 增加 的新参数 θ new \boldsymbol{\theta}^{\text {new }} θnew ,因为参数更新, q ( Z ) q(\mathbf{Z}) q(Z) 和 p ( Z ∣ X , θ new ) p\left(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}^{\text {new }}\right) p(Z∣X,θnew ) 不再相等,此时 K L ( q ∥ p ) > 0 \mathrm{KL}(q \| p)>0 KL(q∥p)>0, 因此导致 ln p ( X ∣ θ new ) \ln p\left(\mathbf{X} \mid \boldsymbol{\theta}^{\text {new }}\right) lnp(X∣θnew ) 的增加
L ( q , θ ) \mathcal{L}(\mathbf{q}, \boldsymbol{\theta}) L(q,θ) 与 Q ( θ , θ old ) \boldsymbol{Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) Q(θ,θold ) 的关系
q ( Z ) = q(\mathbf{Z})= q(Z)= p ( Z ∣ X , θ o l d ) p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}^{old}) p(Z∣X,θold) , Q ( θ , θ old ) \boldsymbol{Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) Q(θ,θold ) 等价于 L ( q , θ ) \mathcal{L}(\mathbf{q}, \boldsymbol{\theta}) L(q,θ),推导如下:
L
(
q
,
θ
)
=
∑
Z
p
(
Z
∣
X
,
θ
o
l
d
)
ln
p
(
X
,
Z
∣
θ
)
−
∑
Z
p
(
Z
∣
X
,
θ
o
l
d
)
ln
p
(
Z
∣
X
,
θ
old
)
=
Q
(
θ
,
θ
old
)
+
c
o
n
s
t
\mathcal{L}(q, \boldsymbol{\theta})=\sum_{\mathbf{Z}} \boldsymbol{p}\left(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}^{\boldsymbol{o l d}}\right) \ln \boldsymbol{p}(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta})-\sum_{\mathbf{Z}} \boldsymbol{p}\left(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}^{\boldsymbol{o l d}}\right) \ln \boldsymbol{p}\left(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}^{\text {old }}\right) \\ =\boldsymbol{Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)+\mathrm{const}
L(q,θ)=Z∑p(Z∣X,θold)lnp(X,Z∣θ)−Z∑p(Z∣X,θold)lnp(Z∣X,θold )=Q(θ,θold )+const
因此,EM算法中,E步所计算的
Q
(
θ
,
θ
old
)
\boldsymbol{Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)
Q(θ,θold ) 实际上等价于计算
L
(
q
,
θ
)
\mathcal{L}(\mathbf{q}, \boldsymbol{\theta})
L(q,θ)。