Expectation Maximization Algorithm

2022年05月11日 阅读数:3
这篇文章主要向大家介绍Expectation Maximization Algorithm,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Expectation Maximization Algorithm

Introduction

极大似然

假设咱们须要调查咱们学校的身高发布,而且假设这个身高分布知足正态分布,那么咱们的目的就是找到知足最符合这个分布的参数\(\mu和\sigma^2\),对此咱们抽样取得数据,而且抽样样本\(n=200\)算法

似然函数

对于以上问题,因为咱们对参数\(\mu和\sigma^2\)未知,也就是咱们对几率函数未知,而且咱们的目的是由已知数据推导咱们的几率参数,暂且对每一个数据创建几率模型app

\[P(x_i) = \frac 1 {\sqrt{2\pi}\sigma}e^{-\frac {(x_i-\mu)^2} {2\sigma^2}} \\ L(\theta)=L\left(x_{1}, x_{2}, \cdots, x_{n} ; \theta\right)=\prod_{i=1}^{n} p\left(x_{i} \mid \theta\right), \quad \theta \in \Theta \]

上述公式的\(\theta\)表示几率参数的\(\mu和\sigma,L(\theta)\)表示多个数据的联合几率函数,那么对于这个函数的处理就用到了咱们极大似然的思想,即咱们的目的是\(max \ L(\theta)\),因为连乘符号不便于计算,以此取对数获得对数似然函数机器学习

\[H(\theta)=\ln L(\theta)=\ln \prod_{i=1}^{n} p\left(x_{i} \mid \theta\right)=\sum_{i=1}^{n} \ln p\left(x_{i} \mid \theta\right) \]

极大似然思想

就像咱们对于线性回归时但愿咱们构造出来的曲线对已有数据的拟合最佳,这样才能更好的预测将来数据,极大似然的思想也是如此,但愿对已有数据的解释最佳,也就是咱们的几率函数要"站的住脚",就须要似然函数越大越好,这有点像数据的反推函数

计算极大似然的通常步骤

  1. 写出似然函数;
  2. 对似然函数取对数,并整理;
  3. 求导数,令导数为 0,获得似然方程;
  4. 解似然方程,获得的参数。

三硬币问题 -- 计算极大似然的困境

对于一个抛硬币的问题,咱们能够取随机变量X,它知足伯努利分布,假设\(p\)是硬币朝上的几率,\(q=1-p\)\(f(x|p)\)表示几率函数学习

\[f(x \mid p)= \begin{cases}p^{x} q^{1-x}, & \mathrm{x}=0,1 \\ 0, & x \neq 0,1\end{cases} \]

可是咱们假设咱们得到了三个神奇的硬币,这三个硬币咱们并不知道它正面朝上的几率,因而咱们只能经过试验得到样本反推它的几率,这里就要用到咱们的极大似然的方法,咱们对这个问题创建相应的几率模型优化

试验

因为技术问题,咱们只能进行一下试验,对于三个硬币\(a,b,c\),咱们抛三次硬币,若是\(a\)=1,那么咱们取\(b\)的值,反之咱们取\(c\)的值,(这里的取值是0和1,正面表示1,反面表示0)spa

\[假设对于三个硬币a,b,c它们的正面朝上的几率为\pi,p,q \\ \begin{aligned} P(y \mid \theta) &=\sum_{z} P(y, z \mid \theta)=\sum_{z} P(z \mid \theta) P(y \mid z, \theta) \\ &=\pi p^{y}(1-p)^{1-y}+(1-\pi) q^{y}(1-q)^{1-y} \end{aligned} \]

符号说明: \(P(y|\theta)\)表示再几率参数\(\pi,p,q\)下y的取值几率,\(z\)表示硬币\(a\)的取值,做为本次试验的隐数据(由于咱们并不对\(a\)的取值作统计,因此是为观测数据)3d

极大似然

似然函数:blog

\[P(Y \mid \theta)=\prod_{i=1}^{n}\left[\pi p^{y_{f}}(1-p)^{1-y_{J}}+(1-\pi) q^{y_{j}}(1-q)^{1-y_{j}}\right] \]

极大似然估计:博客

\[\hat{\theta}=\arg \max _{\theta} \log P(Y \mid \theta) \]

好的,咱们省略了中间的许多步骤,可是最终的目的是明确的,就是找到最佳的\(\theta\)来最大化咱们的联合似然函数,可是问题来了,这个似然函数彷佛很差计算,

  1. 变量不止一个,包含几率参数\(\pi,p,q\)
  2. 联合几率密度,要经过对数化计算

若是用通常的方法,咱们彷佛要废掉不少头发,可是这就是我要引入的EM算法,也就是说EM算法能够用来计算这种极大似然很是复杂的状况

Algorithm

img

STEP

  1. 选取初值
  2. 获取样本
  3. 经过样本更新迭代参数值
  4. 屡次迭代直到收敛

咱们用三硬币问题来解释这个算法的步骤,

对于这个问题,咱们首先把咱们的几率参数\(\pi,p,q\)随机初始化得到初始值,再经过\(n\)次试验得到数据样本,对于样本的描述以下,咱们已知进行了\(n\)次采样,而且得到了每次采样的值\(y_i\),接下来就是算法的第三步,经过样本结合几率函数来优化你的参数,这里的数学原理要仔细思考

对于每一次实验,咱们能够获得咱们的几率函数以下

\[X=1 \\ \alpha(y_i) = \frac {\pi p} {\pi p + (1-\pi)q} \\ \lambda(y_i) = \frac {(1-\pi) q} {\pi p + (1-\pi)q} \\ \]

\[X=0\\ \beta(y_i) = \frac {\pi (1-p)} {\pi (1-p) + (1-\pi)(1-q)} \\ \gamma(y_i) = \frac {(1-\pi) (1-q)} {\pi(1-p)+(1-\pi)(1-q)} \]

符号说明:

\(a(y_i)\)表示实验序号\(i\)下,实验结果\(X=1\),结果来自硬币\(b\)的几率;\(\lambda(y_i)\)表示一样条件下,结果来自硬币\(c\)的几率;\(\beta(y_i)\)表示实验结果\(X=0\),结果来源于硬币\(b\)的几率,\(\gamma(y_i)\)表示结果出自\(c\)的几率

那么咱们能够给出下面的优化方程来迭代你几率参数

\[\pi = \frac {\sum_{x=1}\alpha(y_i)+\sum_{x=0}\beta(y_i)} {n} \\ p = \frac {\sum_{x=1}\alpha(y_i)} {\sum_{x=1}\alpha(y_i)+\sum_{x=0}\beta(y_i)} \\ q = \frac {\sum_{x=1}\lambda(y_i) } {\sum_{x=1}\lambda(y_i)+\sum_{x=0}\gamma(y_i)} \]

理解上面的优化方程,那么EM算法的基本层面是没有问题了,这里就不能给出更过的解释了,其实也是一种基于先验计算后验的方法

后续就是循环迭代,对于这个算法其实和K-means算法有类似之处,而且能够说明的是,它和K-means均可以用于聚类模型

再循环迭代上,能够说明的是,对于循环的结束怎么判断,

  • 参数变更小于临界值: $\left|\theta{(i+1)}-\theta{(i)}\right|<\varepsilon_{1} $
  • Q函数变更小于临界值:\(\left\|Q\left(\theta^{(i+1)}, \theta^{(i)}\right)-Q\left(\theta^{(i)}, \theta^{(i)}\right)\right\|<\varepsilon_{2}\)

对于\(Q\)函数的解释: 彻底数据的对数似然函数\(logP(Y,Z|Θ)\)关于在给定观测数 据Y和当前函数\(Θ(i)\)下对未观测数据Z的条件几率分布$ P(Z|Y, Θ(i))\(,的指望称为\)Q$函数

\[Q\left(\theta, \theta^{(l)}\right)=E_{Z}\left[\log P(Y, Z \mid \theta) \mid Y, \theta^{(l)}\right] \]

\(Q\)函数的理解具体看后面的数学推导

Mathematical Explanation of Algorithms

咱们已经了解了EM算法的步骤,可是对于其中较为深入的数学原理还不知道,这里其中包括了一下几个问题,

  1. 为何EM算法能近似实现对观测数据的极大似然估计
  2. 为何在EM算法下,几率参数最终可以收敛

对于上面的一些问题包括Q函数的来源包含复杂的数学推导,因为这些的数学推导不简单,内容比较多,推荐取看李航的《统计学习方法》,这本书给出了详细的解释

Application of EM Algorithm

在高斯混合模型(GMM)上的运用

EM算法的一个重要应用是高斯混合模型的参数估计,高斯混合模型应用普遍(好比机器学习的聚类),且因为他再极大似然上存在难度,因此EM算法是高斯混合模型参数估计的颇有效的方法,

对于这个的具体内容能够详细看个人其余博客

在无监督学习上的应用

​ 略

Conclusion

自我收获: EM算法是我目前学习的数学推导最多的算法,算上去,我从了解各类几率模型开始,而后先验分布和后验分布,其中看了不少他人的博客,在最开始理解算法的时候是看了B站的复旦老师的课程,后面对公式理解最多的地方是从李航的书上