HOME/Articles/

1.概念复习

Article Outline

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)为:

image-20210116162816270

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

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

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

image-20210116163359989

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

对上式做一个转换:

image-20210116163912493

其中

image-20210116164214973

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

image-20210116164348031

image-20210116164400142

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

image-20210116164515664

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

image-20210116164640576

下界越大,代表似然函数$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$变成常数:

image-20210116165245222

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

image-20210116165314987

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

image-20210116165428539

image-20210116165500660

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

image-20210116170252153

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

3.1 GMM概念

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

image-20210116170447394

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

image-20210116170727257

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

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

image-20210116171111545

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

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

image-20210116171334172

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

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

3.2 GMM公式怎么来的

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

image-20210116172449726

所以动作有:

  • 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$的概率密度函数为:

image-20210116173031139

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

image-20210116173149469

写的通用一点就是:

image-20210116173226866

image-20210116173303191

其中

image-20210116173317817

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

那么:

image-20210116173433738

这就是GMM的公式。

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

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

image-20210116173721185

此时:

image-20210116173805229

3.3 GMM似然函数估计

继续糖果的例子。

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

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

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

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

image-20210116174235870

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

image-20210116175247176

image-20210116175257776

Jensen's inequality

image-20210116175320571

所以:

image-20210116175335504

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

定义一个函数$q$

image-20210116175558331

上式可以简化为:

image-20210116175612895

所以式子右边那一串(三项相加)等于$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)}))$变大。

3.4 GMM-EM

GMM-EM算法流程:

给定样集合${x_1,x_2,\ldots,x_n}$

  • 1.初始化参数

    设定$K$个数,$t$(第t次计算)设定为0

image-20210116180227039

  • E-step

    假设所有参数$\Theta ^{(t)}$已知,计算

    image-20210116180310031

  • M-step

    利用MLE去估计$q(\Theta ^{(t)},\Theta ^{(t+1)})$的参数$\Theta ^{(t+1)}$

image-20210116180435992

参数估计出来为:

image-20210116180503017

image-20210116180516738

重复2 -3步直到满足收敛条件(参数收敛或者似然函数收敛)

3.5 GMM-EM详细推导

E-step

image-20210116180737346

然后

image-20210116180751267

M-step

image-20210116180806943

在M-step要估计的参数是什么?分别是:

image-20210116180839969

我们将M-step拆成两项来看

image-20210116180907566

我们先解$\alpha _k ^{(t+1)}$

因为我们有限制K个糖果袋子的权重和为1,因此$q_1$的最优化问题为:

image-20210116181104153

用Lagrange函数来解:

image-20210116181137335

求导:

image-20210116181151124

对上式将所有的高斯分布$(k=1,2,\ldots,K)$相加起来

image-20210116181239066

image-20210116181248021

所以就找到$\alpha _k^{(t+1)}$的解了。

再来解高斯概率密度函数参数$\mu _k ^{(t+1)},\Sigma _k^{(t+1)}$

从$q_2$着手:

image-20210116181447985

对$q_2$求偏导:

image-20210116181528485

image-20210116181559652

image-20210116181609969

image-20210116181646330

参考:

[1] 機器學習: EM 演算法(Expectation-Maximization Algorithm, EM)、高斯混合模型(Gaussian Mixture Model, GMM)和GMM-EM詳細推導 | by Tommy Huang | Medium

[2] (EM算法)The EM Algorithm - JerryLead - 博客园 (cnblogs.com)