EM算法（2）

1.EM算法
   假定有训练数据集
$\left\{x^{(1)}, x^{(2)}, \cdots, x^{(m)}\right\}${x(1),x(2),⋯,x(m)}
   包含m个独立样本，希望从中找出该组数据得模型模型$p(x, z)$p(x,z)得参数。
   取对数似然函数
$\begin{aligned} &l(\theta)=\sum_{i=1}^{m} \log p(x ; \theta)\\ &=\sum_{i=1}^{m} \log \sum_{z} p(x, z ; \theta) \end{aligned}$​l(θ)=i=1∑m​logp(x;θ)=i=1∑m​logz∑​p(x,z;θ)​
   z是隐随机变量，不方便直接找到参数估计，使用下面的策略找出：计算$1(\theta)$1(θ)的下界，求该下界最大值；重复该过程，直到收敛到局部最大值。

   令$Q_i$Qi​是z的某一个分布，$Q_i \geq 0$Qi​≥0，有：
$l(\theta)=\sum_{i=1}^{m} \log \sum_{z} p(x, z ; \theta)=\sum_{i=1}^{m} \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right)$l(θ)=i=1∑m​logz∑​p(x,z;θ)=i=1∑m​logz(i)∑​p(x(i),z(i);θ) $\begin{aligned} &=\sum_{i=1}^{m} \log \sum_{z^{(M}} Q_{i}\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\\ &\geq \sum_{i=1}^{m} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \end{aligned}$​=i=1∑m​logz(M∑​Qi​(z(i))Qi​(z(i))p(x(i),z(i);θ)​≥i=1∑m​z(i)∑​Qi​(z(i))logQi​(z(i))p(x(i),z(i);θ)​​
   寻找尽量紧的下界，可以令：
$\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}=c$Qi​(z(i))p(x(i),z(i);θ)​=c
   进一步分析：
$\begin{array}{c} Q_{i}\left(z^{(i)}\right) \propto p\left(x^{(i)}, z^{(i)} ; \theta\right) \quad \sum_{z} Q_{i}\left(z^{(i)}\right)=1 \\ Q_{i}\left(z^{(i)}\right)=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{\sum_{z} p\left(x^{(i)}, z^{(i)} ; \theta\right)} \\ =\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{p\left(x^{(i)} ; \theta\right)} \\ =p\left(z^{(i)} | x^{(i)} ; \theta\right) \end{array}$Qi​(z(i))∝p(x(i),z(i);θ)∑z​Qi​(z(i))=1Qi​(z(i))=∑z​p(x(i),z(i);θ)p(x(i),z(i);θ)​=p(x(i);θ)p(x(i),z(i);θ)​=p(z(i)∣x(i);θ)​
   EM算法整体框架：

2.从理论公式推导GMM
   随机变量X是由K个高斯分布混合而成，取各个高斯分布的概率为$\varphi_{1} \varphi_{2} \cdots \varphi_{K}$φ1​φ2​⋯φK​,第i个高斯分布的均值为$\mu_i$μi​，方差为$\sum_i$∑i​。若观测到随机变量X的一系列样本$\mathrm{x}_{1}, \mathrm{x}_{2}, \ldots, \mathrm{x}_{\mathrm{n}}$x1​,x2​,…,xn​,试估计参数$\varphi, \quad \boldsymbol{\mu}, \quad \boldsymbol{\Sigma}$φ,μ,Σ。
   E-step
$w_{j}^{(i)}=Q_{i}\left(z^{(i)}=j\right)=P\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)$wj(i)​=Qi​(z(i)=j)=P(z(i)=j∣x(i);ϕ,μ,Σ)
   M-step
   将多项分布和高斯分布的参数带入:
$\begin{array}{l} \sum_{i=1}^{m} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \phi, \mu, \Sigma\right)}{Q_{i}\left(z^{(i)}\right)} \\ \quad=\sum_{i=1}^{m} \sum_{j=1}^{k} Q_{i}\left(z^{(i)}=j\right) \log \frac{p\left(x^{(i)} | z^{(i)}=j ; \mu, \Sigma\right) p\left(z^{(i)}=j ; \phi\right)}{Q_{i}\left(z^{(i)}=j\right)} \\ \quad=\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \frac{\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_{j}\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right)\right) \cdot \phi_{j}}{w_{j}^{(i)}} \end{array}$∑i=1m​∑z(i)​Qi​(z(i))logQi​(z(i))p(x(i),z(i);ϕ,μ,Σ)​=∑i=1m​∑j=1k​Qi​(z(i)=j)logQi​(z(i)=j)p(x(i)∣z(i)=j;μ,Σ)p(z(i)=j;ϕ)​=∑i=1m​∑j=1k​wj(i)​logwj(i)​(2π)n/2∣Σj​∣1/21​exp(−21​(x(i)−μj​)TΣj−1​(x(i)−μj​))⋅ϕj​​​
   对均值求偏导
$\begin{array}{l} \nabla_{\mu_{l}} \sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \frac{\frac{1}{\left.\left.(2 \pi)^{n / 2}\right|\sum_ j\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right)\right) \cdot \phi_{j}}{w_{j}^{(i)}} \\ \quad=-\nabla_{\mu_{l}} \sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right) \\ \quad=\frac{1}{2} \sum_{i=1}^{m} w_{l}^{(i)} \nabla_{\mu_{l}} 2 \mu_{l}^{T} \Sigma_{l}^{-1} x^{(i)}-\mu_{l}^{T} \Sigma_{l}^{-1} \mu_{l} \\ \quad=\sum_{i=1}^{m} w_{l}^{(i)}\left(\Sigma_{l}^{-1} x^{(i)}-\Sigma_{l}^{-1} \mu_{l}\right) \end{array}$∇μl​​∑i=1m​∑j=1k​wj(i)​logwj(i)​(2π)n/2∣∑j​∣∣​1/21​exp(−21​(x(i)−μj​)TΣj−1​(x(i)−μj​))⋅ϕj​​=−∇μl​​∑i=1m​∑j=1k​wj(i)​21​(x(i)−μj​)TΣj−1​(x(i)−μj​)=21​∑i=1m​wl(i)​∇μl​​2μlT​Σl−1​x(i)−μlT​Σl−1​μl​=∑i=1m​wl(i)​(Σl−1​x(i)−Σl−1​μl​)​
   令上式等于0，解的均值为：
$\mu_{l}:=\frac{\sum_{i=1}^{m} w_{l}^{(i)} x^{(i)}}{\sum_{i=1}^{m} w_{l}^{(i)}}$μl​:=∑i=1m​wl(i)​∑i=1m​wl(i)​x(i)​
   对方差求偏导，等于0
$\Sigma_{j}=\frac{\sum_{i=1}^{m} w_{j}^{(i)}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} w_{j}^{(i)}}$Σj​=∑i=1m​wj(i)​∑i=1m​wj(i)​(x(i)−μj​)(x(i)−μj​)T​
   多项分布参数，考察M-step的目标函数，对于$\phi$ϕ，删除常数项
$\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \frac{\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_{j}\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right)\right) \cdot \phi_{j}}{w_{j}^{(i)}}$i=1∑m​j=1∑k​wj(i)​logwj(i)​(2π)n/2∣Σj​∣1/21​exp(−21​(x(i)−μj​)TΣj−1​(x(i)−μj​))⋅ϕj​​
   得到
$\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \phi_{j}$i=1∑m​j=1∑k​wj(i)​logϕj​
   拉格朗日乘子法
   由于多项分布的概率和为1，建立拉格朗日方程
$\mathcal{L}(\phi)=\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \phi_{j}+\beta\left(\sum_{j=1}^{k} \phi_{j}-1\right)$L(ϕ)=i=1∑m​j=1∑k​wj(i)​logϕj​+β(j=1∑k​ϕj​−1)
   求偏导，等于0
$\begin{array}{c} \frac{\partial}{\partial \phi_{j}} \mathcal{L}(\phi)=\sum_{i=1}^{m} \frac{w_{j}^{(i)}}{\phi_{j}}+\beta \\ -\beta=\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)}=\sum_{i=1}^{m} 1=m \\ \phi_{j}:=\frac{1}{m} \sum_{i=1}^{m} w_{j}^{(i)} \end{array}$∂ϕj​∂​L(ϕ)=∑i=1m​ϕj​wj(i)​​+β−β=∑i=1m​∑j=1k​wj(i)​=∑i=1m​1=mϕj​:=m1​∑i=1m​wj(i)​​
   总结，对于所有的数据点，可以看作组份k生成了这些点。组份k是一个标准的高斯分布，利用上面结论：$\left\{\gamma(i, k) x_{i} | i=1,2, \cdots N\right\}${γ(i,k)xi​∣i=1,2,⋯N}。
$\left\{\begin{array}{l} \mu_{k}=\frac{1}{N_{k}} \sum_{i=1}^{N} \gamma(i, k) x_{i} \\ \Sigma_{k}=\frac{1}{N_{k}} \sum_{i=1}^{N} \gamma(i, k)\left(x_{i}-\mu_{k}\right)\left(x_{i}-\mu_{k}\right)^{T} \\ \pi_{k}=\frac{1}{N} \sum_{i=1}^{N} \gamma(i, k) \\ N_{k}=N \cdot \pi_{k} \end{array}\right.$⎩⎪⎪⎪⎨⎪⎪⎪⎧​μk​=Nk​1​∑i=1N​γ(i,k)xi​Σk​=Nk​1​∑i=1N​γ(i,k)(xi​−μk​)(xi​−μk​)Tπk​=N1​∑i=1N​γ(i,k)Nk​=N⋅πk​​