GMM基础

GMM

定义

高斯混合模型就是用高斯概率密度函数(正态分布曲线)精确地量化事物，它是一个将事物分解为若干的基于高斯概率密度函数(正态分布曲线)形成的模型。

几何表示

假如我们我们现有的数据分布如红线所示，可以发现用一个高斯分布很难较好的描述这组数据的分布，所以我们能够用两个高斯分布加权平均得到一个新的分布，其中每一个数据点都有一定概率属于两个高斯分布中的一个。

GMM只是若干个高斯分布的加权平均（上图中是两个高斯分布）
$$P(x)=\sum _{k=1}^K{\alpha }_{k}N({\mu }_k,{\Sigma }_k)\sum _{k=1}^K{\alpha }_k=1$$
每个数据点都有属于每个高斯分布的可能性，我们用概率去描述这个可能性

设 $x$ 表示观测数据；$z$ 是我们引入的隐变量，用于表示对应的样本属于哪一个高斯分布。

在$GMM$中，$Z$ 是离散型的随机变量。

引入隐变量 $Z$ 后，有：
P ( x ∣ θ ) = ∑ k = 1 K P ( x , z k = c k ∣ θ ) = ∑ k = 1 K P ( z k = c k ∣ θ ) P ( x ∣ z k = c k , θ ) = ∑ k = 1 P k ⋅ N ( x ∣ μ k , Σ k ) P(x|θ)=K∑k=1P(x,zk=ck|θ)=K∑k=1P(zk=ck|θ)P(x|zk=ck,θ)=∑k=1Pk·N(x|μk,Σk)

P(x∣θ)​=k=1∑K​P(x,zk​=ck​∣θ)=k=1∑K​P(zk​=ck​∣θ)P(x∣zk​=ck​,θ)=k=1∑​Pk​⋅N(x∣μk​,Σk​)​​

用途

GMM，是一种业界广泛使用的聚类算法，该方法使用了高斯分布作为参数模型，并使用了期望最大（Expectation Maximization，简称EM）算法进行训练。

证明推导

极大似然估计（MLE）

极大似然估计，通俗理解来说，就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值！
$$模型+数据\to 参数$$
怎样的参数是最好的？使得观测数据出现的概率(即所谓likelihood，似然)最大的参数就是最好的。这个朴素的思想，就是极大似然估计(Maximum Likelihood Estimation, MLE)。对一个独立同分布(i.d.d)的样本集来说，总体的似然就是每个样本似然的乘积。

假设我们已知模型是高斯分布$N(\mu ,\sigma ),\mu 未知，\sigma 已知$，和一组数据$X$，那么它的似然就是
$$L(\mu )=\prod _i^N\frac{1}{\sqrt{2\pi }\sigma }{e}^{-\frac{(X_i-\mu {)}^2}{2{\sigma }^2}}$$
在实际中，因为连乘计算起来比较麻烦，并且概率都很小，难免越乘越接近0最终引发数值bug，因此多对其取log， 得到log似然( log likelihood)：
$$LL(\mu )=\sum _i^N\frac{(X_i-\mu {)}^2}{2{\sigma }^2}-\frac{N}{2}log2\pi -Nlog\sigma$$
log并不改变似然函数的凸性，因此可令其对u取极值(函数取极值的方法：导数为0的点，边界点。)，显然得到:
$$\mu =\frac{{\sum }_i^N{X}_i}{N}$$
　这就完成了对高斯分布均值的极大似然估计。值得一提的是，该例的log似然实在是太简单，所以这个极值可以直接得到；在更多的情况下，我们需要通过梯度下降法等最优化算法来求解。

GMM 参数求解

$GMM$模型似然函数
L ( θ ) = ∏ i = 1 n p ( x ( i ) ∣ θ ) = ∏ i = 1 n ∑ k = 1 K α k N ( x ( i ) ∣ μ k , σ k ) = ∏ i = 1 n ∑ k = 1 K p ( x ( i ) , z ( i ) = k ∣ θ ) = ∏ i = 1 n ∑ k = 1 K p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = k , θ ) (1) L(θ)=n∏i=1p(x(i)|θ)=n∏i=1K∑k=1αkN(x(i)|μk,σk)=n∏i=1K∑k=1p(x(i),z(i)=k|θ)=n∏i=1K∑k=1p(z(i)=k|θ)p(x(i)|z(i)=k,θ)

\tag1 L(θ)​=i=1∏n​p(x(i)∣θ)=i=1∏n​k=1∑K​αk​N(x(i)∣μk​,σk​)=i=1∏n​k=1∑K​p(x(i),z(i)=k∣θ)=i=1∏n​k=1∑K​p(z(i)=k∣θ)p(x(i)∣z(i)=k,θ)​(1)

对数似然
L L ( θ ) = l n L ( θ ) = ∑ i = 1 n l n ∑ k = 1 K α k N ( x ( i ) ∣ μ k , σ k ) = ∑ i = 1 n l n ∑ k = 1 K p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = k , θ ) LL(θ)=lnL(θ)=n∑i=1lnK∑k=1αkN(x(i)|μk,σk)=n∑i=1lnK∑k=1p(z(i)=k|θ)p(x(i)|z(i)=k,θ)

LL(θ)​=lnL(θ)=i=1∑n​lnk=1∑K​αk​N(x(i)∣μk​,σk​)=i=1∑n​lnk=1∑K​p(z(i)=k∣θ)p(x(i)∣z(i)=k,θ)​​
$GMM$通过求不完全数据的边缘概率来得到完全数据的似然函数，因此：
$$\theta =\underset{\theta }{argmax}L{L}_X$$

EM 算法求解参数

接下来使用EM算法来求解参数，EM算法分为E步，求期望；和M步，求期望最大化时的参数值。

E-step

直接求导来求得参数解不太现实，想办法将它转化。先给转化后的形式，再给分析：
L L ( θ ) = ∑ i = 1 n l n ∑ k = 1 K p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = k , θ ) = ∑ i = 1 n l n ∑ k = 1 K ω k ( i ) p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = k , θ ) ω k ( i ) ≥ ∑ i = 1 n ∑ k = 1 K ω k ( i ) l n p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = k , θ ) ω k ( i ) LL(θ)=n∑i=1lnK∑k=1p(z(i)=k|θ)p(x(i)|z(i)=k,θ)=n∑i=1lnK∑k=1ω(i)kp(z(i)=k|θ)p(x(i)|z(i)=k,θ)ω(i)k≥n∑i=1K∑k=1ω(i)klnp(z(i)=k|θ)p(x(i)|z(i)=k,θ)ω(i)k

LL(θ)​=i=1∑n​lnk=1∑K​p(z(i)=k∣θ)p(x(i)∣z(i)=k,θ)=i=1∑n​lnk=1∑K​ωk(i)​ωk(i)​p(z(i)=k∣θ)p(x(i)∣z(i)=k,θ)​≥i=1∑n​k=1∑K​ωk(i)​lnωk(i)​p(z(i)=k∣θ)p(x(i)∣z(i)=k,θ)​​​
步骤$2$给每个样本$i$引入一个分布${\omega }^{(i)}$，满足
$$\sum _{i=1}^K{\omega }_k^{(i)}=1$$
步骤$3$由$jensen$不等式得到

$jensen$不等式：对于一个凸（或凹）函数$f(x)$，其满足$E(f(x))\ge f(E(x))$（或）$f(E(x))\ge E(f(x))$，当且仅当变量x为常数是等号成立，对数$ln(\cdot )$为凹函数，因此
$$ln\sum _{k=1}^K{\omega }_k^{(i)}\frac{p(z^{(i)}=k|\theta )p(x^{(i)}|z^{(i)}=k,\theta )}{{\omega }_k^{(i)}}\ge \sum _{k=1}^K{\omega }_k^{(i)}ln\frac{p(z^{(i)}=k|\theta )p(x^{(i)}|z^{(i)}=k,\theta )}{{\omega }_k^{(i)}}$$
即期望的函数大于等于函数的期望。下一步是要使步骤三中的等号成立，使得对原优化问题转化为对步骤三的优化。前面说过，等号成立的条件是随机变量为常数，即
$$\frac{p(z^{(i)}=k|\theta )p(x^{(i)}|z^{(i)}=k,\theta )}{{\omega }_k^{(i)}}=c(常数)$$
所以
$$\begin{gathered} p(z^{(i)}=k|\theta )p(x^{(i)}|z^{(i)}=k,\theta )=c{\omega }_k^{(i)} \\ \sum _{k=1}^{K}p(z^{(i)}=k|\theta )p(x^{(i)}|z^{(i)}=k,\theta )=\sum _{k=1}^{K}c{\omega }_k^{(i)} \\ \sum _{k=1}^{K}p(z^{(i)}=k|\theta )p(x^{(i)}|z^{(i)}=k,\theta )=c(常数) \end{gathered}$$
则
ω k ( i ) = p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = k , θ ) c = p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = k , θ ) ∑ k = 1 K p ( z ( i ) = k ∣ θ ) p ( x ( i ) ∣ z ( i ) = α k N ( x ( i ) ∣ μ k , σ k ) ∑ k = 1 K α k N ( x ( i ) ∣ μ k , σ k ) ω(i)k=p(z(i)=k|θ)p(x(i)|z(i)=k,θ)c=p(z(i)=k|θ)p(x(i)|z(i)=k,θ)∑Kk=1p(z(i)=k|θ)p(x(i)|z(i)=αkN(x(i)|μk,σk)∑Kk=1αkN(x(i)|μk,σk)

ωk(i)​​=cp(z(i)=k∣θ)p(x(i)∣z(i)=k,θ)​=∑k=1K​p(z(i)=k∣θ)p(x(i)∣z(i)p(z(i)=k∣θ)p(x(i)∣z(i)=k,θ)​=∑k=1K​αk​N(x(i)∣μk​,σk​)αk​N(x(i)∣μk​,σk​)​​​
即在给定$\theta$后，我们就能使用上式求出${\omega }^{(i)}$，${\omega }_k^{(i)}$成为样本$i$对第$k$个分模型的响应度。GMM中这一步其实就是在对每个样本点聚类操作。确定了${\omega }_k^{(i)}$后，问题就退化成只关于的函数。

M-step

求模型参数：固定${\omega }^{(i)}$后的最大化
$$\sum _{i=1}^n\sum _{k=1}^K{\omega }_k^{(i)}ln\frac{p(z^{(i)}=k|\theta )p(x^{(i)}|z^{(i)}=k,\theta )}{{\omega }_k^{(i)}}=\sum _{i=1}^n\sum _{k=1}^K{\omega }_k^{(i)}ln\frac{{\alpha }_{k}N(x^{(i)}|{\mu }_k,{\sigma }_k)}{{\omega }_k^{(i)}}$$
求解模型参数，即
$${\theta }^{t+1}=\underset{\theta }{argmax}\sum _{i=1}^n\sum _{k=1}^K{\omega }_k^{(i)}\frac{{\alpha }_{k}N(x^{(i)}|{\mu }_k,{\sigma }_k)}{{\omega }_k^{(i)}}$$

算法步骤

1. 初始化模型的参数值。EM算法对初始值较敏感，不同的初始值可能得到不同的参数估计值。

2. E-step：依据当前模型参数，计算分模型k对观测样本数据的响应度
   $${\omega }_k^{(i)}=\frac{{\alpha }_{k}N(x^{(i)}|{\mu }_k,{\sigma }_k)}{{\sum }_{k=1}^K{\alpha }_{k}N(x^{(i)}|{\mu }_k,{\sigma }_k)}$$

3. M-step：计算新一轮迭代的模型参数

4. 重复步骤（2）（3），直至达到收敛。

高维高斯分布基础

一维标准正态分布
$$p(x)=\frac{1}{\sqrt{2\pi }}{e}^{-(\frac{x^2}{2})}$$
二维标准正态分布，就是两个独立的一维标准正态分布随机变量的联合分布：
$$p(x,y)=p(x)p(y)=\frac{1}{2\pi }{e}^{-(\frac{x^2+y^2}{2})}$$

把两个随机变量组合成一个随机向量：$v=[xy{]}^T$，则有
$$p(\mathbf{v})=\frac{1}{2\pi }{e}^{-\frac{1}{2}{\mathbf{v}}^{\mathbf{T}}\mathbf{v}}$$

然后从标准正态分布推广到一般正态分布，办法是通过一个线性变换：$v=A(x-\mu )$
$$p(\mathbf{x})=\frac{|\det (A)|}{2\pi }{e}^{[-\frac{1}{2}(\mathbf{x}-\mu {)}^{\mathbf{T}}{\mathbf{A}}^{\mathbf{T}}\mathbf{A}(\mathbf{x}-\mu )]}$$
注意前面的系数多了一个$|\det (A)|$（A的行列式的绝对值）。

可以证明这个分布的均值为μ，协方差为$(A^{T}A{)}^{-1}$。记$\Sigma =(A^{T}A{)}^{-1}$，那就有
$$p(\mathbf{x})=\frac{1}{2\pi |\Sigma {|}^{1/2}}{e}^{[-\frac{1}{2}(\mathbf{x}-\mu {)}^{\mathbf{T}}{\mathbf{\Sigma }}^{-1}(\mathbf{x}-\mu )]}$$
高维情形同理。