美文网首页
统计机器学习-EM算法(期望极大算法)

统计机器学习-EM算法(期望极大算法)

作者: 又双叒叕苟了一天 | 来源:发表于2020-07-02 22:29 被阅读0次

EM算法用于含有隐变量的概率模型参数的极大似然估计。这里首先对隐变量解释,举下面的例子

(三硬币模型)假设有3枚硬币,分别记做ABC,这些硬币正面出现的概率分别是\pipq。进行如下掷硬币试验:先掷硬币A,根据其结果选出硬币B或硬币C,正面选硬币B,反面选硬币C;然后掷选出的硬币,掷硬币的结果,出现正面记做1,出现反面记做0;独立的重复n次试验(这里,n=10),观测结果如下:
1,1,0,1,0,0,1,0,1,1
假设能观测到掷硬币的结果,不能观测掷硬币的过程,问如何估计三硬币正面出现的概率,即三硬币模型的参数\pipq

其中掷硬币A的结果是未观测的,叫做隐变量,记做z。将观测数据表示为Y=(Y_1,Y_2,\cdots,Y_n)^T,未观测数据表示为Z=(Z_1,Z_2,\cdots,Z_n)^T,则观测数据的似然函数为
P(Y|\theta)=\sum_ZP(Y,Z|\theta)=\sum_ZP(Z|\theta)P(Y|Z,\theta)\tag1

P(Y|\theta)=\prod_{j=1}^n[\pi p^{y_j}(1-p)^{1-y_i}+(1-\pi)q^{y_j}(1-q)^{1-y_j}]\tag2
对模型参数\theta=(\pi,p,q)进行极大似然估计,即
\hat\theta=\arg\max_\theta\log P(Y|\theta)\tag3
因为掷硬币A的结果未知,所以没有这个问题解析解,只能通过迭代的方式,逐步增加对数似然函数,找到一个解。EM算法解决的就是这样的一类问题。

接下来首先提出EM算法,然后对其进行解释。

EM算法

EM算法叫做Exception maximization算法,顾名思义,包含求期望(Exception )和极大化(maximization)两个步骤。

输入:观测变量数据Y,隐变量数据Z,联合分布P(Y,Z|\theta),条件分布P(Z|Y,\theta)

输出:模型参数\theta

(1)选择参数的初值\theta^{(0)},开始迭代;

(2)E步:记\theta^{(i)}为第i次迭代参数\theta的估计值,在第i+1次迭代的E步,计算
\begin{align} Q(\theta,\theta^{(i)})&=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ &=\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta) \end{align}
这里P(Z|Y,\theta^{(i)})是在给定观测数据Y和当前参数估计\theta^{(i)}下隐变量数据Z的条件概率分布;

(3)M步:求使Q(\theta,\theta^{(i)})极大化的\theta,确定第i+1次迭代的参数的估计值\theta^{(i+1)}
\theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)})
(4)重复第(2)步和第(3)步,直到收敛。

第(2)步中Q(\theta,\theta^{(i)})是EM算法的核心,称为Q函数。

Q函数定义:完全数据的对数似然函数\log P(Y,Z|\theta)关于给定观测数据Y和当前参数\theta^{(i)}下对未观测数据Z的条件概率分布P(Z|Y,\theta^{(i)})的期望称为Q函数,即
Q(\theta,\theta^{(i)})=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]
因为E_Z[g(z)]=\sum_Zp(z)g(z),所以
\begin{align} Q(\theta,\theta^{(i)})&=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ &=\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta) \end{align}\tag4
其中,因为数据Y未包含隐变量Z的结果,所以称为不完全数据,\log P(Y|\theta)称为不完全数据的对数似然函数,而数据Y,Z则称为完全数据,\log P(Y,Z|\theta)称为完全数据的对数似然函数。
下面关于EM算法作几点说明:

  • 步骤(1)参数的初值可以任意选择,但需注意EM算法对初值是敏感的。
  • 步骤(2)E步求Q(\theta,\theta^{(i)})。Q函数式中Z是未观测数据,Y是观测数据,注意,Q(\theta,\theta^{(i)})的第1个变元表示要极大化的参数,第2个变元表示参数的当前估计值。每次迭代实际在求Q函数及其极大。
  • 步骤(3)M步求Q(\theta,\theta^{(i)})的极大化,得到\theta^{(i+1)},完成一次迭代\theta^{(i)}\rightarrow\theta^{(i+1)}
  • 步骤(4)给出停止迭代的条件,一般是对较小的正数\varepsilon_1\varepsilon_2,若满足

||\theta^{(i+1)}-\theta^{(i)}||\lt\varepsilon_1\ \ 或\ \ ||Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})||\lt\varepsilon_2

​ 则停止迭代。

下面给出这种做法为什么可以对观测数据(不完全数据)进行极大似然估计。

EM算法的导出

对于一个含有隐变量的模型,目标是极大化观测数据(不完全数据)Y关于参数\theta的对数似然函数,即最大化
L(\theta)=\log P(Y|\theta)=\log\sum_ZP(Y,Z|\theta)=\log\bigg(\sum_ZP(Y|Z,\theta)P(Z|\theta)\bigg)\tag5
上面第一步用到边缘概率和联合概率的关系P(Y|\theta)=\sum_ZP(Y,Z|\theta),第二步用到的是条件分布公式P(AB)=P(A|B)P(B)。对这一对数似然函数极大化的困难是因为上式中包含未观测数据Z

但是如果通过第i次迭代得到估计的参数\theta^{(i)},此时再找到一个参数\theta,使得L(\theta)\gt L(\theta^{(i)})(和IIS算法思路有点类似),那么同样也可以起到极大似然估计的效果。为此,考虑两者的差
L(\theta)-L(\theta^{(i)})=\log\bigg(\sum_ZP(Y|Z,\theta)P(z|\theta)\bigg)-\log P(Y|\theta^{(i)})

利用Jensen不等式,过程略,得到其下界:
L(\theta)-L(\theta^{(i)})\geq\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\tag6
于是得到对数似然函数的下界
L(\theta)\geq L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\tag7
定义
B(\theta,\theta^{(i)})\hat=L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\tag8

L(\theta)\geq B(\theta,\theta^{(i)})
并且
\begin{align} B(\theta^{(i)},\theta^{(i)})&=L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta^{(i)})P(Z|\theta^{(i)})}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\\ &=L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y,Z|\theta^{(i)})}{P(Y,Z|\theta^{(i)})}\\ &=L(\theta^{(i)}) \end{align}
即可以使B(\theta,\theta^{(i)})可以增大的\theta,也可以使L(\theta)增大,所以极大似然估计变成了使B(\theta,\theta^{(i)})极大化的问题,即
\theta^{(i+1)}=\arg\max_\theta B(\theta,\theta^{(i)})
所以
\theta^{(i+1)}=\arg\max_\theta B(\theta,\theta^{(i)})=\arg\max_\theta\bigg(L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\bigg)
省去不包含变量\theta的常数项L(\theta^{(i)})P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)}),得到
\begin{align} \theta^{(i+1)}&=\arg\max_\theta\bigg(\sum_ZP(Z|Y,\theta^{(i)})\log P(Y|Z,\theta)P(Z|\theta)\bigg)\\ &=\arg\max_\theta\bigg(\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta)\bigg)\\ &=\arg\max_\theta Q(\theta,\theta^{(i)}) \end{align}
所以,在EM算法中最大化Q函数,就等同于最大对数似然函数的下界,从而进行极大似然估计。但是这种算法并不能保证找到全局最优值。

EM算法可以用于无监督学习,略。EM算法的收敛性证明略。

EM算法在高斯混合模型学习中的应用

高斯混合模型定义

高斯混合模型是指具有如下形式的概率分布模型:
P(y|\theta)=\sum_{k=1}^K\alpha_k\phi(y|\theta_k)\tag9
其中,\alpha_k是系数,\alpha_k\geq0\sum_{k=1}^K\alpha_k=1\phi(y|\theta_k)是高斯分布密度,\theta_k=(\mu_k,\sigma_k^2)
\phi(y|\theta_k)=\frac{1}{\sqrt{2\pi}\sigma_k}\exp\bigg(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg)
称为第k个模型。

高斯混合模型参数估计的EM算法

可以设想观测数据y_jj=1,2,\cdots,N,是这样产生的:首先,依概率\alpha_k选择第 k个高斯分布分模型\phi(y|\theta_k);然后依第k个分模型的概率分布\phi(y|\theta_k)生成观测数据y_j,这是观测数据y_jj=1,2,\cdots,N,是已知的;反应观测数据y_j来自第k个分模型的数据是未知的,k=1,2,\cdots,K,以隐变量\gamma_{jk}表示,其定义如下:
\gamma_{jk}= \begin{cases}1,\ \ &第j个观测来自第k个分模型\\ 0,\ \ & 否则 \end{cases}\\ j=1,2,\cdots,N;\ \ k=1,2,\cdots,K
\gamma_{jk}是0,1随机变量。

有了观测数据y_j及未观测数据\gamma_{jk},那么完全数据是
(y_j,\gamma_{j1},\gamma_{j2},\cdots,\gamma_{jK}),\ \ j=1,2,\cdots,N
于是可以写出完全数据的似然函数:
\begin{align} P(y,\gamma|\theta)&=\prod_{j=1}^NP(y_j,\gamma_{j1},\gamma_{j2},\cdots,\gamma_{jK}|\theta)\\ &=\prod_{k=1}^K\prod_{j=1}^N[\alpha_k\phi(y_j|\theta_k)]^{\gamma_{jk}}\\ &=\prod_{k=1}^K\alpha_k^{n_k}\prod_{j=1}^N[\phi(y_j|\theta_k)]^{\gamma_{jk}}\\ &=\prod_{k=1}^K\alpha_k^{n_k}\prod_{j=1}^N\bigg[\frac{1}{\sqrt{2\pi}\sigma_k}\exp\bigg(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg)\bigg]^{\gamma_{jk}} \end{align}
其中,n_k=\sum_{j=1}^N\gamma_{jk}(依赖第k个分类器的样本数),\sum_{k=1}^Kn_k=N

那么完全数据的对数似然函数为
\log P(y,\gamma|\theta)=\sum_{k=1}^K\bigg\{n_k\log\alpha_k+\sum_{j=1}^N\gamma_{jk}\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}
确定Q函数
\begin{align} Q(\theta,\theta^{(i)})&=E_{P(\gamma|y,\theta^{(i)})}[\log P(y,\gamma|\theta)]\\ &=E_{P(\gamma|y,\theta^{(i)})}\sum_{k=1}^K\bigg\{n_k\log\alpha_k+\sum_{j=1}^N\gamma_{jk}\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}\\ &=\sum_{k=1}^K\bigg\{\sum_{j=1}^N(E\gamma_{jk})\log\alpha_k+\sum_{j=1}^N(E\gamma_{jk})\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}\\ \end{align}\tag{10}
其中
\begin{align} E\gamma_{jk}&=\hat\gamma_{jk}=E(\gamma_{jk}|y,\theta)=P(\gamma_{jk}=1|y,\theta)\\ &=\frac{P(\gamma_{jk}=1,y_j|\theta)}{\sum_{k=1}^KP(\gamma_{jk}=1,y_j|\theta)}\\ &=\frac{P(y_j|\gamma_{jk}=1,\theta)P(\gamma_{jk}=1|\theta)}{\sum_{k=1}^KP(y_j|\gamma_{jk}=1,\theta)P(\gamma_{jk}=1|\theta)} \end{align}

\hat\gamma_{jk}是在当前模型参数下第j个观测数据来自第k个分模型的概率,称为分模型k对观测数据y_j的响应度。

根据开头的描述,P(y_j|\gamma_{jk}=1,\theta)=\phi(y_k|\theta_k)P(\gamma_{jk}=1|\theta)=\alpha_k,所以
E\gamma_{jk}=\hat\gamma_{jk}=E(\gamma_{jk}|y,\theta)=\frac{\alpha_k\phi(y_j|\theta_k)}{\sum_{k=1}^K\alpha_k\phi(y_j|\theta_k)}\tag{11}
\hat\gamma_{jk}=E\gamma_{jk}n_k=\sum_{j=1}^NE\gamma_{jk}(此处的n_k实际为E_{P(\gamma_{jk}|y,\theta)}n_kn_k=\sum_{j=1}^N\gamma_{jk})代入公式(10)得到
Q(\theta,\theta^{(i)})=\sum_{k=1}^K\bigg\{n_k\log\alpha_k+\sum_{j=1}^N\hat\gamma_{jk}\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}\tag{12}
接下来需要求Q函数的极大化(极大化观测数据对数似然函数的下界),即
\theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)})
其中\theta=(\alpha_k,\mu_k,\sigma_k^2)k=1,2,\cdots,K,将公式(12)对\mu_k\sigma_k^2求偏导等于0,得到第i+1次的更新值\hat\mu_k\hat\sigma_k^2,同样将公式(12)对\alpha_k求偏导等于0,加上条件\sum_{k=1}^K\alpha_k=1,求得更新值\hat\alpha_k。计算更新值时\hat\gamma_{jk}n_k用到的参数是第i次更新得到的值,所以可以通过迭代的方式不断更新参数直到收敛。求得的\hat\mu_k\hat\sigma_k^2\hat\alpha_k
\hat\mu_k=\frac{\sum_{j=1}^N}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K\tag{13}

\hat\sigma_k^2=\frac{\sum_{j=1}^N\hat\gamma_{jk}(y_j-\mu_k)^2}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K\tag{14}

\hat\alpha_k=\frac{n_k}N=\frac{\sum_{j=1}^N\hat\gamma_{jk}}N,\ \ k=1,2,\cdots,K\tag{15}

高斯混合模型参数估计的EM算法

输入:观测数据y_1,y_2,\cdots,y_N,高斯混合模型;

输出:高斯混合模型参数。

(1)取参数的初始值开始迭代(初值敏感)

(2)E步:依据当前模型参数,计算分模型k对观测数据y_j的响应度
\hat\gamma_{jk}=\frac{\alpha_k\phi(y_j|\theta_k)}{\sum_{k=1}^K\alpha_k\phi(y_j|\theta_k)},\ \ j=1,2,\cdots,N;\ \ k=1,2,\cdots,K
(3)M步:计算新一轮迭代的模型参数
\hat\mu_k=\frac{\sum_{j=1}^N}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K

\hat\sigma_k^2=\frac{\sum_{j=1}^N\hat\gamma_{jk}(y_j-\mu_k)^2}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K

\hat\alpha_k=\frac{n_k}N=\frac{\sum_{j=1}^N\hat\gamma_{jk}}N,\ \ k=1,2,\cdots,K

(4)重复第(2)步和第(3)步,直到收敛。

相关文章

  • 统计机器学习-EM算法(期望极大算法)

    EM算法用于含有隐变量的概率模型参数的极大似然估计。这里首先对隐变量解释,举下面的例子 (三硬币模型)假设有3枚硬...

  • Day 2083:学习

    统计学习 EM算法:一种迭代算法,用于含有隐变量的概率模型参数的极大似然估计。迭代分两步,E,求期望,M,求极大 ...

  • 6.2.高斯混合聚类

    EM算法 期望极大算法.它是一种迭代算法,用于含有隐变量的概率模型参数估计.EM算法的每次迭代由两步组成:E步求期...

  • EM算法-引入

    期望极大(EM)算法:是一种迭代算法,用于含有隐变量(latent variable)的概率模型参数的极大似然估计...

  • EM算法-一般形式

    期望极大(EM)算法:是一种迭代算法,用于含有隐变量(latent variable)的概率模型参数的极大似然估计...

  • 李航-第9章EM算法及其推广

    EM算法的每次迭代由两步组成:E步,求期望;M步,求极大。所以这一算法称为期望极大法(expectation ma...

  • EM算法

    EM算法 EM算法基本思想 ​ 最大期望算法(Expectation-Maximization algorit...

  • 机器学习(十):EM算法与GMM算法原理及案例分析

    一、简介 EM算法 最大期望算法(Expectation-maximization algorithm,简称EM,...

  • EM算法

    EM算法作为数据挖掘领域十大经典算法之一,在统计学习领域也有诸多应用。EM算法(Expectation-maxim...

  • EM算法及实现

    周志华老师在《机器学习》里这样评价 EM算法:EM算法是最常见的隐变量估计方法,在机器学习里有着极为广泛的用途,例...

网友评论

      本文标题:统计机器学习-EM算法(期望极大算法)

      本文链接:https://www.haomeiwen.com/subject/jwbdqktx.html