1.概念复习

1.1 凸函数

$f$为实数$x$的函数，如果$f^{''}(x) \geq 0$，则称$f$为凸函数，如果$f^{''}(x)$>0则称为严格凸函数。 $$ f^{''}(x) \geq 0,\forall x \in R $$ 如果$f$为向量$x$的函数，二阶微分矩阵(Hessian Matrix,H)如果是半正定(determinant(H)$\geq$0)的,则称$f$为凸函数，如果determinant(H)>0，则称为严格凸函数。 $$ H \geq 0,\forall x \in R^d $$

1.2 Jensen's inequality

从概率角度，如果$\varphi$是凸函数，$X$是随机变量： $$ E[\varphi(X)] \geq \varphi(E[X]) $$ 其中，E为期望,计算如下：

如果$x$是连续值：$E[x]=\int x f(x)dx$
如果$x$是离散值：$E[x]=\Sigma xf(x)$

$f(x)$是概率密度函数。

2.EM算法

假设有n个样本$x={{x^{(1)},x^{(2)},\ldots,x^{(n)}}}$，每个样本之间彼此独立，这组样本的似然函数(likelihood function)为：

其中，f为概率密度函数，$\theta$为概率密度函数的参数。

上式简单的说就是因为一组样本的似然函数为每个样本的概率密度函数相乘(假设样本独立).这里对概率密度函数取了对数,方便求导计算。

假设每个样本都有一些隐藏变量$z$，我们要找到$z$使得似然函数最大化：

如果要直接求$\theta$，因为有隐变量$z$存在会比较困难。但当$z$确定后，使用MLE求解就容易很多。EM算法就是用来解决样本存在隐变量的问题的最佳方法。因为我们无法直接最大化$L(\theta)$，所以我们可以不断建立$L(\theta)$的下界(E-step),然后最大化下界(M-step)，所以一般EM算法都会存在E-step和M-step两步。

对上式做一个转换：

其中

也就是将其看作变量$X$，那么$\varphi=ln(X)$则是凹函数，所以上述式子可以用Jensen's inequality表示，但等式要取反：

因为$\varphi=ln(X)$是凹函数，所以：

所以似然函数$L(\theta)$的下界(Lower Bound,LB)出来了：

下界越大，代表似然函数$L(\theta)$越大，跟MLE理念相同，我们希望估计出来的似然函数可以越大越好。

假设$\theta给定，$那$L(\theta)$的值取决于$q(z^{(i)})$和$f(x^{(i)},z(i))$。所以我们可以通过这两个函数来使下界不断上升，去逼近$L(\theta)$。当不等式变成等式时，表示我们调整出来的$q(z^{(i)})$和$f(x^{(i)},z(i))$可以让下界等于$L(\theta)$。

根据Jensen's inequality，要让等式成立需要让随机变量$X$变成常数：

因为$q(x)$是概率密度函数：

因为分子除以分母是常数，当分母是1时，分子项相加和为那个常数，因此：

上述就是E-step的结果，结果就是后验概率，解决了$q(z^{(i)})$如何选择地问题，建立了$L(\theta)$的下界。EM算法就是不断地重复E-step和M-step，直到收敛。M-step就是在给定$q(z^{(i)})$后，调整$\theta$，去极大化$L(\theta)$的下界(在固定$q(z^{(i)})$后，下界还可以调整的更大)。那么EM算法的一般步骤就是：

3.高斯混合模型(Gaussian Mixed Model)

3.1 GMM概念

一般在讲高斯模型都会假设说样本分布来自一个高斯分布，高斯分布如下：

假设有一组从高斯分布(均值为160,方差为5)抽样出来的样本100个，然后取直方图，理论上样本的分布要跟高斯分布很像，实际上也很像(见下图).如果抽样越多，红色线跟蓝色线就越像：

<center>蓝色是抽样的样本，红色是高斯分布N(160,5)</center>

但假设我从高斯分布(均值为160，方差为5)的样本中抽样100个，从另一个高斯分布(均值为180，方差为5)的样本中抽样100个。此刻有200个样本，如果一样用单一的高斯分布去估计这200个样本就可能有问题，如下图：

<center>蓝色是抽样样本，红色是高斯分布N(170,10)</center>

根据上图可知不能用单一的高斯分布去估计样本分布，因此可以使用两个高斯分布去估计样本分布。此时估计出来的分布就比较像实际样本分布，这个过程就称为高斯混合模型。

<center>蓝色是抽样样本的分布，黑色是高斯分布N(160,5),绿色是高斯分布N(180,5),红色是黑色加绿色的高斯混合分布(N(160,5)+N(180,5))</center>

有了上述概念再来看高斯混合模型(Gaussian mixture model,GMM)就比较简单。上面说为什么我们需要用很多个高斯模型来形容我们的样本分布，至于是多少个高斯模型比较合适就是需要去测试才知道，也就是隐变量的个数是未知的，为超参数。

3.2 GMM公式怎么来的

假设有K个袋子每个袋子有无穷多个糖果，每个袋子的概率密度函数都是高斯函数。当我们要拿一颗糖出来的时候，我们要先选择一个袋子，然后从袋子拿一颗糖出来，我们总共重复抽取n次。

所以动作有：

1.先选一个袋子

这时候选袋子就是一种随机变量，这里假设是离散型随机变量： $$ Z=[z_1,z_2,\ldots,z_K] $$
从袋子拿一颗糖果 $$ z_k=1且z_i=0，i\neq k,代表第k个袋子被选中 $$

从这个例子我们知道，$z$是无法观测的随机变量即隐变量，且其先验概率为： $$ p(z_k=1)=\alpha_k,k=1,\ldots K $$ $\alpha _k$也就是第$k$个袋子(高斯分布)被选中的概率。

因此隐变量$z$的概率密度函数为：

假设我们今天选中第$k$个袋子，然后抽中糖果$x$的概率是：

写的通用一点就是：

其中

$\Theta$称为高斯混合模型的参数集。

那么：

这就是GMM的公式。

$\alpha _k$等于每个高斯分布的介于[0,1]的权重，和为1。

假设我们已经直到高斯混合模型的参数$\Theta$了，此刻我们有一颗糖果$x$，根据它的后验概率就可以计算出来是来自第几个袋子，或者说这颗糖果在各个袋子的概率。

此时：

3.3 GMM似然函数估计

继续糖果的例子。

假设我们抽了$n$个糖果，$x={{x_1,x_2,\ldots,x_n}}$,要用这些糖果来反推参数，分别是：

选中每个糖果袋子的概率$p(z_k=1)=\alpha_k$
每个糖果袋子的概率密度函数的参数(高斯分布的参数，$\mu _k,\Sigma_k$)

听起来很困难是吧，从抽出来的糖果去推这么多的东西，EM算法似乎是一个有效的估计方法。

这里将抽取的$n$的糖果的似然函数写出来，然后取对数：

EM是一种不断迭代的算法，所以参数会不断地更新，这里假设：

Jensen's inequality

所以：

因为已经在算$t+1$次了，所以第t次的参数$\Theta (t)$固定时，式子可视为一个常数$C$不重要，可以删除。

定义一个函数$q$

上式可以简化为：

所以式子右边那一串(三项相加)等于$ln(L(\Theta^{(t+1)}))$的下界。

原本目的是希望$t$+1次的对数似然函数的$ln(L(\Theta^{(t+1)}))$最大化，但计算比较困难，所以我们去最大化$ln(L(\Theta^{(t+1)}))$的下界会比较容易一些，因此最大化$q(\Theta ^{(t)},\Theta ^{(t+1)})$会使得$ln(L(\Theta^{(t+1)}))$变大。