机器学习(十九)EM:期望最大算法

简介: 机器学习(十九)EM:期望最大算法

1 EM算法简介


最大期望算法(Expectation Maximization Algorithm,又译期望最大化算法),是一种迭代算法,用于含有隐变量(hidden variable)的概率参数模型的最大似然估计或极大后验概率估计。


在统计计算中,最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计或者最大后验估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。


未观测变量的学名是“隐变量”(latent variable)。EM算法是常用的估计参数隐变量的利器,它是一种迭代式的方法,其基本思想是:若参数θ已知,则可根据训练数据推断出最优隐变量Z的值(E步);反之,若Z的值已知,则可以方便地对参数θ做极大似然估计(M步)。


于是,以初始值θ0为起点,可迭代执行以下步骤直至收敛:

  • 基于θt推断隐变量Z的期望,记为Zt;
  • 基于已观测变量X和Zt对参数θ做极大似然估计,记为θt+1


2  抛硬币例子


我们现在考虑两个抛硬币的例子:

"给定两个硬币A和B,随机抛掷后正面朝上概率分别记为 p'和'q'。每次随机选择一个硬币并投掷。有以下观察序列:H A H A T B T A T B H B H B T A H B H A T A T A H A H B H A T B,从给定数据估计出'p'和'q'的值"。


我们很容易计算出p:


22.png


相似地可以计算出q:


23.png



这很容易,因为计算未知参数所需的所有信息都是可获得的。但是,如果硬币上的标签(A和B)被隐藏起来,不知道每次投掷哪个硬币。鉴于A和B硬币同样可能被选中,那我们如何估计未知参数'p'和'q'?

我们将尝试通过多次迭代计算来解决问题。在每次迭代中,我们有两个步骤,'E'步骤和'M'步骤。


“E”步骤(期望):

  1. 首先初始化p和q的值(初始猜测)。
  2. 我们不是说掷硬币来自特定的硬币,而是说它以概率为'x'来自硬币A,来自硬币B概率'1-x'。
  3. 计算每枚硬币的正反面期望数量。

“M”步骤(最大化):

  1. 从“E”步骤计算步骤3中每个硬币的正反面期望的对数似然,类似于MLE计算。
  2. 最大似然估计出隐变量,并重新估计p和q的新值
  3. 使用新的p和q值重复“E”步骤,直到它收敛为止。


让我们举一个例子,其中进行了5次实验并且在每次实验中进行了10次抛掷。(使用两个硬币)。


24.png


我们从对未知参数进行初始化猜测,假设p = 0.6和q = 0.5。让我们进行第一轮实验。将此观察序列称为'S',我们想要估计观察'S'来自硬币A的可能性是多少,即P(A | S)。回想贝叶斯定理:


25.png


P(A)是选择硬币A的概率,它是0.5(因此是P(B)),因为我们知道每个硬币具有相同的被选择的概率。P(S|A)是观察的概率,因为它来自硬币A,即使用二项分布,我们推断它是:

26.png


同样地有,


27.png


P(S)是观察序列的概率。由于观察可以来自硬币A或硬币B或两者,因此:

28.png


然后可以得到:

29.png


将初始猜测的值代入p = 0.6和q = 0.5,得到P(A | S)= 0.45,因此P(B | S)= 1-P(A | S)= 0.55。

30.png


因此,给定观察序列S,它来自硬币A的概率是0.45并且来自硬币B的概率是0.55。因此,来自硬币A正面期望数量 = 5 * 0.45并且反面期望数量= 5 * 0.45,类似地,来自硬币B的正面的期望数量= 5 * 0.55并且反面期望数量= 5 * 0.55。对其他四个实验重复相同的期望(E)步骤,我们得到硬币A 正面期望总数= 21.3和反面期望总数= 8.6,类似于硬币B,正面期望总数= 11.7,反面期望总数= 8.4


因此,对未知参数p和q的新估计是:

31.png



32.png


上一步是“M”步骤或最大化步骤。我们重复上述EM步骤,直到'p'和'q'的值收敛。在这个例子中,'p'和'q'的值在大约10步中收敛到最终值p = 0.8和q = 0.52。


33.png


以上是EM算法应用的一个非常简单的例子。它用于表明给定具有缺失数据(含有隐变量)的参数估计问题,EM算法可以通过生成对丢失数据的可能猜测来迭代地解决该问题,然后通过使用这些猜测来最大化观察的可能性。除了简单的投掷硬币示例之外,EM已成功用于训练隐藏状态的HMM,EM也用于  聚类应用  和  半监督学习


3 EM算法推导



上面是EM算法的一个简单感性的例子,下面我们看看如何用数学推导EM算法。在引入EM算法之前,我们先了解一些基础知识。


3.1 凸函数(Convex Functions)


定义1  假设f是在区间I = [a, b]的一个实数函数,当满足以下条件时,可以说f在区间是凸函数,

34.png

此时,∀x1, x2 ∈ I, λ ∈ [0, 1]


定义2 如果-f是凸函数,那么f是凹函数.


定理1 如果f(x)在区间[a,b]上二阶可导,并且f''(x) ≥0,那么f(x)在[a,b]上是凸函数


证明

35.png


36.png

结论1 在(0, ∞),-ln(x)为凸函数,ln(x)为凹函数

证明

37.png


3.2 Jensen’s 不等式


在区间I上,f是一个凸函数,有x1, x2, . . . , xn∈I,λ1, λ2, . . . , λn ≥ 0,

并且

38.png


那么有

39.png

证明

40.png


41.png



因为ln(x)为凹函数,那么有


42.png


结论2 Jensen's不等式同时也证明了算数平均要大于等于几何平均


43.png


证明


44.png


3.3 EM推导


假设X是一个随机样本集,用来估计θ,我们希望找到一个θ使得P(X|θ) 最大,这就是称作为θ的最大似然估计。为了估计θ,通常是需要引入对数似然函数,定义为如下:



45.png


这个似然函数可以看作为给定样本集X上的关于θ的函数。因为ln(x)是一个严格单调递增函数,所以使P(X|θ)达到最大也会使L(θ)最大化。


EM算法是一个最大化L(θ)(或者说是极大似然估计)的迭代过程。假设在经过nth迭代之后,由θn得到当前估计θ,那么我们的目标是最大化L(θ),所以我们希望更新后的θ满足如下:

46.png


相应地,我们就是想最大化下面的差值:


47.png



EM算法是常用的估计参数隐变量的利器。到目前为止,我们还没有考虑任何不能观察到的变量或者缺失变量,对于上述情况,由于存在隐含变量,不能直接最大化l(θ),所以只能不断地建立l的下界(E-step),再优化下界(M-step),依次迭代,直至算法收敛到局部最优解。这就是EM算法的核心思想,简单的归纳一下:


EM算法通过引入隐含变量,使用MLE(极大似然估计)进行迭代求解参数。通常引入隐含变量后会有两个参数,EM算法首先会固定其中的第一个参数,然后使用MLE计算第二个变量值;接着通过固定第二个变量,再使用MLE估测第一个变量值,依次迭代,直至收敛到局部最优解。


E-Step和M-Step:

  • E-Step:通过observed data和现有模型估计参数估计值 missing data;
  • M-Step:假设missing data已知的情况下,最大化似然函数。


现在我们引入隐含变量的集合为Z,具体值记为z,那么P(X|θ) 可以写成:


48.png


带入之前的差值公式可以得到:


49.png

我们这里引入Jensen's不等式,


50.png


继续推导之前的公式:


51.png


从式子(12)到式子(13)我们用到了:

52.png


所以有:


53.png


为了方便,做如下变换:

54.png


我们有如下函数图像:

55.png


可以推导出:


56.png



我们发现l(θn|θn)始终在L(θ)之下,并且在θ时会相等,因此假如一个θ使得l(θn|θn)变大,那么L(θ)也会变大,所以求解转化为如下:


57.png


4 参考资料


相关文章
|
30天前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
17天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
25天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
50 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
1月前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
30天前
|
机器学习/深度学习 算法 Python
探索机器学习中的决策树算法:从理论到实践
【10月更文挑战第5天】本文旨在通过浅显易懂的语言,带领读者了解并实现一个基础的决策树模型。我们将从决策树的基本概念出发,逐步深入其构建过程,包括特征选择、树的生成与剪枝等关键技术点,并以一个简单的例子演示如何用Python代码实现一个决策树分类器。文章不仅注重理论阐述,更侧重于实际操作,以期帮助初学者快速入门并在真实数据上应用这一算法。
|
6天前
|
机器学习/深度学习 人工智能 算法
探索机器学习中的决策树算法
【10月更文挑战第29天】本文将深入浅出地介绍决策树算法,一种在机器学习中广泛使用的分类和回归方法。我们将从基础概念出发,逐步深入到算法的实际应用,最后通过一个代码示例来直观展示如何利用决策树解决实际问题。无论你是机器学习的初学者还是希望深化理解的开发者,这篇文章都将为你提供有价值的见解和指导。
|
27天前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
29 0
|
16天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
2天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。