随机模拟:马尔科夫链蒙特卡洛采样MCMC与EM算法「2.3」
cac55 2024-10-03 17:49 46 浏览 0 评论
最近学习了机器学习中的马尔科夫链蒙特卡洛(Markov Chain Monte Carlo, 简称MCMC) 相关的知识。
主要内容包括：
【1】蒙特卡洛原则，及其应用于采样的必要性（已经发布在头条）
【2】用于求解最大似然、近似推断、期望问题的经典采样算法：Metropolis-Hastings，Rejection，Importan，Metropolis和Gibbs算法。（本文属于此部分）
【3】马尔可夫链各个性质在蒙特卡洛采样问题中的应用，包括同质性，平移不变性
—————【2】—————
上一篇【2.2】中详细讨论了EM优化算法的推导和性质，EM算法通过不断提高下界来逼近最大似然，其中E步求Q(z)=p(z|x,θ)，此时的θ是上一个M步已经固定的，求得此θ对应的最大下界的Q(z)，更新Q(z)。M步固定Q(z)，求得此时使得下界最大的θ，更新θ，如此迭代，直到收敛到局部最优，得到最终估计值。
M步中对L最大化求新θ，等价于求使得Q(θ，θold)最大的θ值。因此，如果此后验概率p(z|x,θ)不能用分析式直接求得，可以用采样的方法近似之。Q(θ，θold)写成积分形式为 integral(p(z|x,θold)ln(p(z,x|θ)))dz。
这里，p(z|x,θ)成为我们采样的目标函数，分析式未知。
【蒙特卡洛期望最大化算法Monte Carlo EM algorithm】
MCEM算法可以解决此问题，该算法从当前p(z|x,θold)中取L个样本，根据积分的定义，Q(θ，θold)可由下式的样本逼近：
使用此算法计算Q，完成EM算法的运算。
以上就是EM算法和蒙特卡洛采样的关系。在上上篇文章讨论重要性采样算法时提到，其局限性在于假设分布和目标分布的差异不能太大。而MCMC采样可以克服此问题。
【马尔科夫链蒙特卡洛采样算法Markov Chain Monte Carlo】
MCMC是使用马尔科夫链生成样本的方法，这个链设计为在最重要的区域花费最多的时间，样本x的生成模拟从目标分布p(x)中产生的过程。
对比MCMC和重要性采样（见上上篇文章【2采样算法】），MCMC采用可变的假设分布，即使用q(x'|x)而不是q(x)，x'是新的要采样的状态，x是前一个样本。每产生一个样本，原假设分布都会更新为一个新的假设分布。
MCMC算法不是一个特定的算法，而是使用上述思想的一类算法。
从最简单的一个成员开始：
【Metropolis-Hasting算法】
1、初始化x0
2、循环N-1次：对i=0，1，一直到N-1
从【0，1】均匀分布中随机采样小数u；
从假设分布q(x'|xi)中随机采样x'；
判断：若u< min {1, p_(x')*q(xi|x')/(p_(xi)*q(x'|xi))},x(i+1)=x'接受x'为新样本，
否则x(i+1)=x(i)
例如，令每一个假设分布为均值等于x的高斯分布，【1蒙特卡洛原则】中已经讨论过p_(x)也易得，因此可以很方便对p(x)采样。
如图所示，每次取一个样本修正一次假设分布，避免了重要性采样算法的误差。马尔科夫链性质体现在假设分布的设置。
【废弃样本Burn-In period】
在MCMC算法中，初次取样本时，可能取在上图中的长尾之中，导致经过很多次迭代才把假设分布逐渐逼近到目标分布去，因此可能需要在采样完成后将前面这些废弃样本删除，例如前1000个样本可能都是无效的。
本文讨论了EM算法中应用蒙特卡洛采样，以及一种马尔可夫链蒙特卡洛采样算法-Metropolis hasting算法，之后将继续讨论其他MCMC算法。
相关推荐
- 服务器用的CPU和个人电脑用的CPU有什么区别?一篇文章告诉你!
-
服务器cpu和普通cpu的区别你的电脑CPU是‘短跑健将’，服务器CPU却是‘铁人三项选手’——它不追求瞬间爆发力，而要7×24小时扛住千军万马的数据洪流！想知道为什么企业机房敢收天价服务费？答案全藏...
- “吃鸡”新版本第1天，玩家进入游戏点击“立即更新”，后悔了!
-
欢迎诸位小伙伴们来到天哥开讲的《和平精英》“精英小课堂”~每逢两三个月，这款游戏就会迎来一次大版本迭代更新，很多朋友会在第一时间更新版本，前往全新的主题模式里一探究竟。不过也有一些老玩家并不会立刻更新...
- 中关村在线·aigo存储杯《无畏契约》全国高校争霸赛招募启事
-
以青春之名，燃电竞之火1赛事背景与宗旨在金秋送爽的9月，芊芊学子们即将回归校园生活。为了给精彩的校园生活锦上添花，由中关村在线与aigo存储联合主办的《无畏契约》全国高校争霸赛正式启幕，旨在为全国高...
- 【生肖狗】9.7-9.10提醒:人算不如天算，转变即是转机
-
九月上旬的风，带着秋意的清爽，也带着几分不可捉摸的变数。对于生肖狗的朋友们来说，9月7日到9月10日这四天，格外需要留意“计划与变化”的碰撞——你们向来习惯提前规划，做事稳妥周全...
- 转转客服IM系统的WebSocket集群架构设计和部署方案
-
本文由转转技术李帅分享，原题“转转客服IM的WebSocket集群部署方案”，下文有修订和重新排版。1、引言转转作为国内头部的二手闲置交易平台，拥有上亿的用户。用户在使用转转app遇到问题时，一般可以...
- 上线3天Steam好评率86%，《时间旅者:重生曙光》开启生存恐怖新篇章
-
这里究竟发生了什么?末日降临，真正的故事悄然启幕。目前，生存恐怖类游戏《时间旅者：重生曙光(Cronos:TheNewDawn)》已在PC(Steam、EpicGamesStore)、P...
- 什么神仙洗衣机让我一天有28小时?拆开松下「大四洗」藏了啥秘密
-
说起家庭洗衣的烦恼，想必很多人都有过类似的经历：贴身内衣要单独洗，宝宝的口水巾得小心呵护，宠物玩具怕藏污纳垢，床单被套又体积庞大，把这些东西混在一起洗担心越洗越脏，分开洗又得反复操作，洗完烘、烘完再洗...
- 爆料人挖出GTA6注册的奇葩域名 延续经典讽刺风格
-
等待《侠盗猎车手6》的日子跨越了数个春秋，在游戏圈期盼着这部可能成为史上最重磅游戏的过程中，每过一段时间就会有些许消息浮出水面。最新线索来自数据挖掘者Tez2在GTA论坛的发现，他可能偶然发现了关于...
- 跟着故事去旅行——读《驼峰间:旅行、探险与征服》
-
作者：郭冰茹《驼峰间》记录了旅行家伊本·白图泰有生之年流传的一则寓言，说一对父子被关进了监狱，有一天儿子问父亲他们每天吃的都是些什么肉，父亲说有牛、羊和骆驼，并且详细地描述了每种动物的特点。但不管父亲...
- 前端工程师需要熟悉的Linux服务器(SSH 终端操作)指令
-
在Linux服务器管理中，SSH（SecureShell）是远程操作的核心工具。以下是SSH终端操作的常用命令和技巧，涵盖连接、文件操作、系统管理等场景：一、SSH连接服务器1.基本连接...
- 跳票6年后，「丝之歌」首发把Steam服务器干爆了 | 玩点好的
-
文丨果脯樱花隧道昨天晚上22点，「鸽」了6年的《空洞骑士：丝之歌》终于上线，算是了却不少玩家的执念。毕竟，这款游戏实在让人等了太多太多年，而且曾有过多次定档后跳票的「案底」，不知道把多少人都整出了P...
- 对标魔兽失败!腾讯版“魔兽”运营一年多后，宣布国际服凉凉
-
大家好，这里是正惊游戏，我是正惊小弟。有很多游戏都想干掉《魔兽世界》，但是大部分魔兽杀手都知道自己不是魔兽的对手，不过是想蹭一下人气而已。腾讯也有一款曾经想对标魔兽的大作，可是上线才一年半国际服就宣布...
- 408 Request Timeout:服务器等待客户端发送请求的时间过长。
-
408RequestTimeout是HTTP状态码之一，表示客户端在发送请求时，服务器等待的时间过长，最终放弃了处理该请求。此问题通常与网络延迟、客户端配置、服务器设置或者应用程序的性能有关...
- 梦幻西游:9.9维护解读，全新时间服锁定129级
-
梦幻西游：9.9维护解读，全新时间服锁定129级9月9日维护解读。1、教师节活动开启，一共7天。挂机，答题，收笔墨纸砚，收海马，搞起来。或者是提前收点家具，教师节期间体力珍贵，家具会涨价。又或者是教师...
- 只是拆掉一面墙，空间就立马大变样，这种设计思路，值得学习
-
你有没有过这样的经历？刚买的房子户型图看起来方方正正，装修完却发现——玄关鞋柜只能塞在角落，进门就撞墙；餐厅正好在过道中间，吃饭像走流程；明明有四个房间，却有一个空着没用，像块食之无味的鸡肋；客餐厅之...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- 服务器用的CPU和个人电脑用的CPU有什么区别?一篇文章告诉你!
- “吃鸡”新版本第1天，玩家进入游戏点击“立即更新”，后悔了!
- 中关村在线·aigo存储杯《无畏契约》全国高校争霸赛招募启事
- 【生肖狗】9.7-9.10提醒:人算不如天算，转变即是转机
- 转转客服IM系统的WebSocket集群架构设计和部署方案
- 上线3天Steam好评率86%，《时间旅者:重生曙光》开启生存恐怖新篇章
- 什么神仙洗衣机让我一天有28小时?拆开松下「大四洗」藏了啥秘密
- 爆料人挖出GTA6注册的奇葩域名 延续经典讽刺风格
- 跟着故事去旅行——读《驼峰间:旅行、探险与征服》
- 前端工程师需要熟悉的Linux服务器(SSH 终端操作)指令
- 标签列表
-
- 如何绘制折线图 (52)
- javaabstract (48)
- 新浪微博头像 (53)
- grub4dos (66)
- s扫描器 (51)
- httpfile dll (48)
- ps实例教程 (55)
- taskmgr (51)
- s spline (61)
- vnc远程控制 (47)
- 数据丢失 (47)
- wbem (57)
- flac文件 (72)
- 网页制作基础教程 (53)
- 镜像文件刻录 (61)
- ug5 0软件免费下载 (78)
- debian下载 (53)
- ubuntu10 04 (60)
- web qq登录 (59)
- 笔记本变成无线路由 (52)
- flash player 11 4 (50)
- 右键菜单清理 (78)
- cuteftp 注册码 (57)
- ospf协议 (53)
- ms17 010 下载 (60)