GMM\EM算法详解——附代码示例

目录

代码地址:6.1公布
笔者能力有限,如有错误请指正!感谢您的阅读!

潜(隐)变量模型

观测变量:直接观测的数据
潜变量:

  • 无法直接被观测到,需要通过模型和观测变量进行推断
  • 利用潜变量来判断观测变量的模型,GMM HMM都是潜变量模型
  • 潜变量模型将不完数据(只有观测数据)的边缘分布转化为容易处理的完全数据(观测数据+潜变量)的联合分布。

如:聚类问题,潜变量是类别(未知),观测变量是数据点,给定观测变量,如果推断哪些是同一类?K-means

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思路:

  1. 引入K个D维均值向量 μ k , k = 1 , 2 , . . . , K \mathbf{\mu}_k,k=1,2,...,K μk​,k=1,2,...,K, μ k \mathbf{\mu}_k μk​是第k个类别的聚类中心。
  2. 计算数据点 x n \mathbf{x}_{\mathbf{n}} xn​和所有类中心 μ k \mathbf{\mu}_k μk​的距离,类中心距离此数据点最近的类别,即为当前数据点的类别。
  3. 根据新的聚类结果,使用当前聚集到各个类别的数据的均值来更新当前类别的类中心。
  4. 返回第2步,直到满足一定的停止准则。

引入潜变量

  • 对于每一个数据点 x n \mathbf{x}_{n} xn​引入一个指示因子 r n k ∈ { 0 , 1 } r_{nk} \in \{0,1\} rnk​∈{0,1},如果 x n \mathbf{x}_{n} xn​属于第k类,则 r n k = 1 r_{nk}=1 rnk​=1,否则 r n k = 0 , r_{nk}=0, rnk​=0, r n k r_{nk} rnk​即为潜变量
  • 定义目标函数 J = ∑ n = 1 N ∑ k = 1 K r n k ∥ x n − μ k ∥ 2 J=\sum_{n=1}^{N} \sum_{k=1}^{K} r_{n k}\left\|\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right\|^{2} J=∑n=1N​∑k=1K​rnk​∥xn​−μk​∥2
  • 优化目标:寻找合适的$r_{nk} 和 和 和\boldsymbol{\mu}_{k}$使目标函数最小。

模型优化:两阶段迭代优化(简单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∑N​rnk​(xn​−μk​)=0→μk​=∑n​rnk​∑n​rnk​xn​​

K-means应用:图像分割和压缩

GMM模型

高斯分布

  • D维高斯变量的高斯分布:
    N ( x ∣ μ , Σ ) = 1 ( 2 π ) D / 2 1 ∣ Σ ∣ 1 / 2 exp ⁡ { − 1 2 ( x − μ ) T Σ − 1 ( x − μ ) } (1) \mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}, \mathbf{\Sigma})=\frac{1}{(2 \pi)^{D / 2}} \frac{1}{|\mathbf{\Sigma}|^{1 / 2}} \exp \left\{-\frac{1}{2}(\mathbf{x}-\boldsymbol{\mu})^{\mathrm{T}} \boldsymbol{\Sigma}^{-1}(\mathbf{x}-\boldsymbol{\mu})\right\} \tag{1} N(x∣μ,Σ)=(2π)D/21​∣Σ∣1/21​exp{−21​(x−μ)TΣ−1(x−μ)}(1)
    ​ 其中, μ ∈ R D \boldsymbol{\mu} \in R^{D} μ∈RD,高斯分布的均值向量, Σ ∈ R D × D \mathbf{\Sigma} \in R^{D \times D} Σ∈RD×D,高斯分布的协方差矩阵。

为什么使用高斯分布?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∏N​p(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∑N​lnp(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θmax​lnp(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​=N1​n∑​xn​,ΣML​=N1​n∑​(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​πk​N(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/21​exp{−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},Σk​zk​=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∏K​N(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​πkzk​​N(x∣uk​,Σk​)zk​

  • 边缘分布

    • 使用贝叶斯公式对潜变量求和: p ( x ) = ∑ z p ( x , z ) = ∑ z p ( z ) p ( x ∣ z ) = ∑ k = 1 K π k N ( x ∣ μ k , Σ k ) p(\mathbf{x})=\sum_{\mathbf{z}} p(\mathbf{x}, \mathbf{z})=\sum_{\mathbf{z}} p(\mathbf{z}) p(\mathbf{x} \mid \mathbf{z})=\sum_{k=1}^{K} \pi_{k} \mathcal{N}\left(\mathbf{x} \mid \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right) p(x)=∑z​p(x,z)=∑z​p(z)p(x∣z)=∑k=1K​πk​N(x∣μk​,Σk​)
    • 对每一个观测 x n \mathbf{x}_n xn​,都有一个潜变量 z n \mathbf{z}_n zn​和其对应,上述公式将变量 x \mathbf{x} x和潜变量 z \mathbf{z} z联系起来,并且引入了联合分布 p ( x , z ) p(\boldsymbol{x}, \boldsymbol{z}) p(x,z),完成了将观测数据的边缘分布转换成观测和潜变量的联合分布
  • 后验分布
    γ ( 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=1K​p(zj​=1)p(x∣zj​=1)p(zk​=1)p(x∣zk​=1)​=∑j=1K​πj​N(x∣μj​,Σj​)πk​N(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∑N​ln{k=1∑K​πk​N(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} π,μ,Σ求导:

  1. 对 μ \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​πj​N(xn​∣μj​,Σj​)πk​N(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​=Nk​1​∑n=1N​γ(znk​)xn​Nk​=∑n=1N​γ(znk​)

  2. 对 Σ \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​πj​N(xn​∣μj​,Σj​)πk​N(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​=Nk​1​∑n=1N​γ(znk​)(xn​−μk​)(xn​−μk​)T

  3. 对 π \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​πj​N(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​πj​N(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​πj​N(xn​∣μj​,Σj​)πk​N(xn​∣μk​,Σk​)​+λ∑k​πk​0=∑n=1N​∑j​πj​N(xn​∣μj​,Σj​)∑k​πk​N(xn​∣μk​,Σk​)​+λλ=−N​

GMM模型参数估计的EM算法总结

上述参数估计方法并不是一个严格的解析解,因为公式中有后验概率 γ ( z n k ) \gamma\left(z_{n k}\right) γ(znk​),依赖于每个高斯的代估计参数。上述推导过程给出了一个迭代的估计参数的过程,并能保证似然逐步增加。

给定一个GMM模型, 优化目标是寻找使似然函数最大的各个高斯成分的均值向量、协方差矩阵和混合系数

  1. 初始化 初始化参数 μ k , Σ k , π k \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}, \pi_{k} μk​,Σk​,πk​
  2. E步 使用当前参数计算后验概率
    γ ( z n k ) = π k N ( x n ∣ μ k , Σ k ) ∑ j π j N ( x n ∣ μ j , Σ j ) \gamma\left(z_{n k}\right)=\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}, \boldsymbol{\Sigma}_{j}\right)} γ(znk​)=∑j​πj​N(xn​∣μj​,Σj​)πk​N(xn​∣μk​,Σk​)​
  3. M步 使用后验重新估计参数
    μ k n e w = 1 N k ∑ n = 1 N γ ( z n k ) x n Σ k n e w = 1 N k ∑ n = 1 N γ ( z n k ) ( x n − μ k n e w ) ( x n − μ k n e w ) T π k n e w = N k N , N k = ∑ n = 1 N γ ( z n k ) \begin{array}{c} \boldsymbol{\mu}_{k}^{n e w}=\frac{1}{N_{\mathrm{k}}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right) \mathbf{x}_{n} \\ \Sigma_{k}^{n e w}=\frac{1}{N_{k}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}^{ {new }}\right)\left(\mathbf{x}_{\mathrm{n}}-\boldsymbol{\mu}_{k}^{ {new }}\right)^{T} \\ \pi_{k}^{ new }=\frac{N_{k}}{N}, \quad N_{k}=\sum_{n=1}^{N} \gamma\left(z_{n k}\right) \end{array} μknew​=Nk​1​∑n=1N​γ(znk​)xn​Σknew​=Nk​1​∑n=1N​γ(znk​)(xn​−μknew​)(xn​−μknew​)Tπknew​=NNk​​,Nk​=∑n=1N​γ(znk​)​
  4. 重新计算似然函数, 重复2-4,直至满足收敘条件

GMM模型和K-means的联系

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πϵ)21​1​exp{−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​πj​exp{−2ϵ1​∥∥​xn​−μj​∥∥​2}πk​exp{−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是一种软对齐方式,使用后验概率来表示某个数据点由某个类别产生的概率。


EM算法

上述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​= NM​1​∑m=1NM​​xm​,ΣM​= NM​1​∑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​=∑1N​p(zi​=1)1​∑m=1NM​​p(zi​=1)xm​

如何获得 p ( z i ) p(z_i) p(zi​)?可以采用迭代估计法:

  1. \quad 先给出一组随机的参数取值 ( μ M , Σ M , μ W , Σ W ) \left(\mu_{M}, \Sigma_{M}, \mu_{W}, \Sigma_{W}\right) (μM​,ΣM​,μW​,ΣW​)
  2. \quad 更新 p ( z i = 1 ) = N ( x i ∣ μ M , Σ M ) N ( x i ∣ μ M , Σ M ) + N ( x i ∣ μ W , Σ W ) p\left(z_{i}=1\right)=\frac{\mathcal{N}\left(\mathrm{x}_{i} \mid \mu_{M}, \Sigma_{M}\right)}{\mathcal{N}\left(\mathrm{x}_{i} \mid \mu_{M}, \Sigma_{M}\right)+\mathcal{N}\left(\mathrm{x}_{i} \mid \mu_{W}, \Sigma_{W}\right)} p(zi​=1)=N(xi​∣μM​,ΣM​)+N(xi​∣μW​,ΣW​)N(xi​∣μM​,ΣM​)​
  3. 使用新的p更新 ( μ M , Σ M , μ W , Σ W ) \left(\mu_{M}, \Sigma_{M}, \mu_{W}, \Sigma_{W}\right) (μM​,ΣM​,μW​,ΣW​), 重复2-3

含隐变量模型的最大似然估计->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∣θ)

  1. 初始化 初始化参数 θ o l d \theta^{old} θold
  2. E步 计算潜变量的后验概率p(Z|X, θ o l d \theta^{{old}} θold)
  3. 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 =θargmax​Q(θ,θ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{∑Z​p(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∣θ)]

  • 寻找使Q函数最大的新参数:
    θ new  = arg ⁡ max ⁡ θ Q ( θ , θ old  ) \theta^{\text {new }}=\underset{\theta}{\arg \max } {Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) θnew =θargmax​Q(θ,θold )

当尝试使用EM算法来解决自己的问题时,需要明确Q函数。

使用EM算法通用步骤重新考虑GMM参数估计

在之前的推导中,我们引入了潜变量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​πkznk​​N(xn​∣μk​,Σk​)znk​lnp(X,Z∣μ,Σ,π)=∑n=1N​∑k=1K​znk​{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∏N​k=1∏K​[πk​N(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∑N​k=1∑K​γ(znk​){lnπk​+lnN(xn​∣μk​,Σk​)}

EM算法通用解释

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∣θ)=∑Z​q(Z)lnp(X∣θ)=∑Z​q(Z)ln{q(Z)p(X,Z∣θ)​p(Z∣X,θ)q(Z)​}=∑Z​q(Z)lnq(Z)p(X,Z∣θ)​−∑Z​q(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)
GMM\EM算法详解——附代码示例

其中: 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时等号成立。

  • K L ( q ∥ p ) ≥ 0 \mathrm{KL}(q \| p) \geq 0 KL(q∥p)≥0,所以 ln ⁡ p ( X ∣ θ ) ≥ L ( q , θ ) \ln p(\mathbf{X} \mid \boldsymbol{\theta}) \geq \mathcal{L}(q, \boldsymbol{\theta}) lnp(X∣θ)≥L(q,θ),只有当后验分布 p ( Z ∣ X , θ ) p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta}) p(Z∣X,θ)和 q ( Z ) q(\mathbf{Z}) q(Z)相等时,等号成立。
  • L ( q , θ ) \mathcal{L}(q, \boldsymbol{\theta}) L(q,θ)可以看作是 ln ⁡ p ( X ∣ θ ) \ln p(\mathbf{X} \mid \boldsymbol{\theta}) lnp(X∣θ)的下界,如果我们无法直接提升 ln ⁡ p ( X ∣ θ ) \ln p(\mathbf{X} \mid \boldsymbol{\theta}) lnp(X∣θ)的准确值,我们可以提升其下界。

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,θ) 最大。

GMM\EM算法详解——附代码示例

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 ) 的增加

GMM\EM算法详解——附代码示例

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,θ)。

上一篇:Birkhoff-von Neumann Crossbar 光交换网络的调度方案


下一篇:6.1通量和散度