网站设计的国际专业流程,网站买源代码,万江做网站的公司,扬州推广公司期望值最大化算法 EM#xff1a;睹始知终 算法思想算法推导算法流程E步骤#xff1a;期望M步骤#xff1a;最大化陷入局部最优的原因 算法应用高斯混合模型#xff08;Gaussian Mixture Model, GMM#xff09;问题描述输入输出Python代码实现 算法思想 期望值最大化方法睹始知终 算法思想算法推导算法流程E步骤期望M步骤最大化陷入局部最优的原因 算法应用高斯混合模型Gaussian Mixture Model, GMM问题描述输入输出Python代码实现 算法思想 期望值最大化方法是宇宙演变、物种进化背后的动力。 如果一个公司在制定年终奖标准时把每个员工一半的奖金和公司价值观挂钩人们就会背诵创始人每个语录 — 整个公司都会自动迭代寻找最优解每个人说话都是公司价值观。
如果一个国家足球不行把每个孩子的高考分数和足球水平挂钩人们就会大力投资足球设施大爷大妈也会把广场让出去给孙子踢足球谁跟我孙子抢我真的会发疯 — 整个国家都会自动迭代寻找最优解每个人说话都是公司价值观。
这个思想在算法中就是期望最大化 EM 算法只要给出一个收益函数 计算机就会自动的寻找收益最大的那个点。
在每一时刻算出能够最大化收益期望值的方向沿着这个方向走一小步然后再从新的起点重复这个过程不论从何处起始最后一定能够达到收益最大的那个终点 EM 算法本质是迭代策略用于含有隐变量的统计模型中交替计算期望步骤和最大化步骤来寻找参数的最优估计。
比如看故事书但故事中有一些缺失的部分这些就是隐变量。
你的目标是填补这些缺失部分使得整个故事变得连贯和合理。
EM 算法就像一个两步循环过程帮助你逐渐完善这个故事 期望步骤 (E 步骤) 在这一步你根据目前所知的信息对故事中缺失的部分做出最佳猜测。就好比你根据故事的上下文来推测这些缺失部分可能的内容。 最大化步骤 (M 步骤) 接下来你根据这些猜测来重新讲述整个故事并调整故事中其他已知部分的细节使得整体故事更加合理。这个过程就像根据新的假设来优化故事的连贯性。M步骤可以使用 MLE 或 MAP。
这个循环反复进行你根据当前的故事版本来改善你对缺失部分的猜测然后再用这些新猜测来优化整个故事。
随着每次迭代故事变得越来越连贯直到最终达到一个点你觉得再怎么调整也无法使故事更好了。
这时你就找到了最合适的版本来填补缺失部分你找到了模型参数的最优估计。 再如 市场营销策略 公司在设计营销策略时通常会试图理解消费者的隐藏需求和偏好隐藏变量并据此调整其产品或服务参数。 通过市场反馈公司不断调整其策略以最大化销售或品牌影响力这类似于EM算法的期望步骤和最大化步骤的迭代过程。
算法推导 EM 算法论文https://web.mit.edu/6.435/www/Dempster77.pdf 概率图模型再复杂都可以简化成俩个变量观测变量x、隐变量z
比如你正在看一部电影
电影中你能直接看到的场景和角色对话等就像是“观测变量”这些是你直接获得的信息不需要猜测或推理。然而电影也有许多你看不到的部分比如角色的内心想法、未展示的背景故事或者导演留下的悬念。这些就像是“隐变量”你无法直接观察它们但它们对整个故事的剧情发展趋势就是人心所向至关重要。 p ( x ∣ θ ) ∏ i 1 n p ( x i ∣ θ ) L ( θ ) log p ( x ∣ θ ) ∑ i 1 n log p ( x i ∣ θ ) ∑ i 1 n log ∑ z p ( x i , z i ∣ θ ) \begin{aligned} p(\mathbf{x}|\theta) \begin{aligned}\prod_{i1}^np(x_i|\theta)\end{aligned} \\ { L ( \theta )} \operatorname{log}p(\mathbf{x}|\theta) \\ \sum_{i1}^n\log p(x_i|\theta) \\ \sum_{i1}^n\log\sum_zp(x_i,z_i|\theta) \end{aligned} p(x∣θ)i1∏np(xi∣θ)L(θ)logp(x∣θ)i1∑nlogp(xi∣θ)i1∑nlogz∑p(xi,zi∣θ)
那我们逐步拆解公式原意 联合概率分布 第一行公式表示观测数据集 x 在给定参数 θ 的条件下的联合概率分布比如你有 3 张卡片每张卡片上都有一个秘密数字这个数字可以是 1、2、3 中的任何一个我们现在要猜每张卡片上的数字是什么。每张卡片上数字的猜测都是独立的不会影响其他卡片上的猜测。在数学中这就是我们说的“联合概率分布”即我们想知道所有卡片上每一种可能的数字组合出现的整体概率是多少。如所有卡片上都是1的概率是多少111、如所有卡片上是123的概率是多少123、222、321、…、333 所有可能的数字组合及其相应的概率。 对数似然函数 第二行公式为了不忘记我们的猜测我们决定把每次猜的结果写在一个日记本上。因为数字可能很大所以我们用一种特别的数学“捷径”来记日记这种捷径就是对数。这样即使我们猜的数字很大日记本上的数字也不会太长更容易计算。在数学中写在日记本上的这种方法叫做“对数似然函数”一个帮助我们处理大数字的数学工具。 对数似然的求和 第三行公式现在我们决定把日记本上所有的数字加起来因为我们用了对数所以加起来很容易。这就像是玩一个加法游戏把所有的小数字加起来得到一个总分。 边缘概率 第四行公式第1张是1、第2张是2第 3 张卡片藏在盒子里只有第 3 张未知我们只知道盒子里可能藏着什么数字1、2、3。那先专注于部分已知信息而忽略未知部分的具体细节猜对所有看得见的卡片的概率是多少。就是计算 第1张是1、第2张是2 的概率忽略第三张卡片可能的值。这就是数学中的“边缘概率” —— 它允许我们在部分信息未知的情况下仍对已知部分进行概率计算。
在概率分布上就是先猜一个 z 的分布记为 q使用 E、M 步骤去逼近真实分布 L ( θ ) L(\theta) L(θ) 最后让猜的分布像爬楼梯一样找到真实分布 L ( θ ) L(\theta) L(θ) 的最高点最优解。
用数学公式描述这个过程 L ( θ ) ∑ i 1 n log ∑ z p ( x i , z i ∣ θ ) ∑ i 1 n log ∑ z ∞ q i ( z ) p ( x i , z i ∣ θ ) q i ( z ) ≥ ∑ i 1 n ∑ z q i ( z ) log p ( x i , z i ∣ θ ) q i ( z ) \begin{aligned} L(\theta) \begin{aligned}\sum_{i1}^n\log\sum_zp(x_i,z_i|\theta)\end{aligned} \\ \begin{aligned}\sum_{i1}^n\log\sum_z^\infty q_i(z)\frac{p(x_i,z_i|\theta)}{q_i(z)}\end{aligned} \\ \geq\sum_{i1}^n\sum_zq_i(z)\log\frac{p(x_i,z_i|\theta)}{q_i(z)} \\ \end{aligned} L(θ)i1∑nlogz∑p(xi,zi∣θ)i1∑nlogz∑∞qi(z)qi(z)p(xi,zi∣θ)≥i1∑nz∑qi(z)logqi(z)p(xi,zi∣θ) 第一行 L ( θ ) ∑ i 1 n log ∑ z p ( x i , z i ∣ θ ) L(\theta) \sum_{i1}^n \log \sum_z p(x_i, z_i|\theta) L(θ)∑i1nlog∑zp(xi,zi∣θ) 比如你正在玩一个寻宝游戏你有一张地图 θ \theta θ地图上标记了很多可能藏宝的地方这里的藏宝地方就是 x i x_i xi 和 z i z_i zi。 x i x_i xi 是你可以看到的地方而 z i z_i zi 是地图上标记的但实际上可能藏宝也可能没藏宝的秘密地方。这一行的意思是你在尝试弄清楚根据地图每个地方藏宝的可能性有多大。 第二行 ∑ i 1 n log ∑ z ∞ q i ( z ) p ( x i , z i ∣ θ ) q i ( z ) \sum_{i1}^n \log \sum_z^\infty q_i(z) \frac{p(x_i, z_i|\theta)}{q_i(z)} ∑i1nlog∑z∞qi(z)qi(z)p(xi,zi∣θ) 这一步就像你在用一种特别的放大镜 q i ( z ) q_i(z) qi(z) 来看地图 θ \theta θ。这个放大镜可以告诉你每个秘密地方真的藏宝的机会有多大。你用这个放大镜和地图一起来计算每个地方可能藏宝的几率。 第三行 ≥ ∑ i 1 n ∑ z q i ( z ) log p ( x i , z i ∣ θ ) q i ( z ) \geq \sum_{i1}^n \sum_z q_i(z) \log \frac{p(x_i, z_i|\theta)}{q_i(z)} ≥∑i1n∑zqi(z)logqi(z)p(xi,zi∣θ) 最后这一步就像你在记录你的发现。对于地图上的每一个地方你都写下了根据我的放大镜和地图我认为这里藏宝的机会有多大。”这样你就得到了一个完整的藏宝地图上面标记了所有可能藏宝的地方和它们的可能性。
然后根据 Jeasen 不等式得到公式的下界。
最终的公式是 J ( z , q ) J(z,q) J(z,q)。
不断的改变 z就能不断搜索 θ \theta θ 最大值概率分布图中的最高点
于是EM 算法可分为 E 步骤、M 步骤。
算法流程
E步骤期望 E 步骤猜的分布 q 不变最大化 z。
在图中q 沿着 x 轴上升碰到真实分布z 就停止开始 M 步骤。
M步骤最大化 M 步骤猜的分布 q 寻优z 不变。
在图中q 沿着 y 轴水平移动碰不到真实分布z 就停止开始 E 步骤。
陷入局部最优的原因
EM 算法可能会陷入局部最优。 非凸目标函数EM算法通常用于优化非凸non-convex的目标函数。在非凸函数中可能存在多个局部最优解这意味着算法可能会在达到一个局部最优点后停止而这个点不一定是全局最优的。 初始值依赖性EM算法的结果往往依赖于初始参数的选择。如果初始参数选得不好算法可能会被引导到一个局部最优解而不是全局最优解。 迭代方式EM算法通过交替执行其两个步骤E步和M步来逐渐改进参数估计。这种迭代方式可能会导致算法“陷入”某个局部区域的最优解特别是在目标函数有多个峰值的情况下。 模型复杂性和数据的局限性在一些复杂模型或者数据不足的情况下EM算法可能无法准确估计出全局最优参数从而陷入局部最优。
解决这些问题的一种方法是通过多次运行算法每次使用不同的初始参数然后从中选择最好的结果。
此外还可以使用全局优化技术如模拟退火或遗传算法来辅助找到更接近全局最优的解。
算法应用
高斯混合模型Gaussian Mixture Model, GMM
问题描述
假设我们有一组观测数据点我们认为这些数据点是由两个不同的高斯分布生成的但我们不知道每个数据点来自哪个高斯分布。
我们的目标是估计这两个高斯分布的参数均值和方差以及每个分布对应的混合系数。
输入输出
输入一组观测数据点。输出两个高斯分布的参数均值和方差和混合系数。
Python代码实现
import numpy as np
from sklearn.mixture import GaussianMixture# 模拟数据生成
np.random.seed(0)
data np.concatenate([np.random.normal(0, 1, 300), np.random.normal(5, 1.5, 700)]).reshape(-1, 1)# 应用EM算法
gmm GaussianMixture(n_components2, random_state0)
gmm.fit(data)# 输出结果
print(f均值: {gmm.means_.ravel()})
print(f方差: {gmm.covariances_.ravel()})
print(f混合系数: {gmm.weights_.ravel()})这段代码首先生成了一些模拟数据数据是由两个不同的高斯分布合成的。
然后使用sklearn库中的GaussianMixture模型来应用EM算法。最后打印出两个高斯分布的均值、方差以及混合系数。
