uniform机器学习极简入门5—EM算法

上一节我们介绍了高斯混合模型（GMM），这个模型在求解的时候我们提到了EM算法，本节我们详细介绍下EM算法的基本流程，其实在KMeans中也有EM的思想，EM算法在很多概率求解中都有用到，我们也会在后续中一一提到。

1 EM算法概述

我们先简单描述EM算法

EM算法就是用来解决存在隐变量的参数估计问题

在GMM模型中，我们在利用样本估计每个高斯分量模型的参数之前，需要先确定每个样本的所属类别，然后才能根据类别对应的样本利用最大似然函数来求解。具体步骤可以拆成如下

先给每个样本估计一个类别概率

根据样本所属类别概率求解各个类别对应的参数，利用最大似然估计的方法

这里的类别就是EM中提到的隐变量，传统的似然函数估计是
$\{x_1, x_2,...\} ->\theta$
现在似然函数变得更复杂
$\{x_1, x_2,...\} -> {z_1, z_2, ...} -> \theta$
下面我们就推导下这个更加泛化的过程

2 EM算法推导

首先我们先假设某个样本的概率
$P(x_j;\theta)$
这里的样本x对应的概率参数还由隐变量z决定，我们可以根据联合概率和边际概率得到
$P(x_j;\theta)=\sum_{z_j}P(z_j)P(x_j|z_j;\theta)$
$=\sum_{z_j}P(x_j,z_j;\theta)\ \ \ (1)$

我们的目标还是希望似然函数最大化，那么对应样本集合，我们有
$L = \prod_{j=1}^mP(x_j;\theta)$

$logL = \sum_{j=1}^mlogP(x_j;\theta)$
$=\sum_{j=1}^mlog[\sum_{z_j}P(x_j,z_j;\theta)] \ \ \ \ (2)$
上面我们把公式1带入到最大似然求解中，可以得到公式2，但是这里有个很麻烦的log，无法直接求解极值，下面对P()进行转换，表示成期望
$logL=\sum_{j=1}^mlog\sum_{z_J}Q(z_j)\frac{P(x_j,z_j;\theta)}{Q(z_j)} \ \ \ \ (3)$
这里Q(z)是z的分布，由Jensen不等式我们知道，对于凸函数有

凸函数

E[f(x)]>=f[E(x)]

凹函数则相反。

公式3中，log正好是凹函数根据Jensen不等式可以得到
$logL>=\sum_{j=1}^m\sum_{z_j}Q(z_j)log\frac{P(x_j,z_j;\theta)}{Q(z_j)} \ \ \ \ \ (4)$
Jensen不等式使得等号成立的条件是x为常数
$\frac{P(x_j,z_j;\theta)}{Q(z_j)}=c \ \ \ \ \ (5)$
已知Q(z)属于概率分布，有如下条件
$\sum_{z_j}Q(z_j)=1 \ \ \ \ (6)$
根据公式（5）（6）得到
$Q(z_j)=\frac{P(x_j,z_j;\theta)}{\sum_{z_j} {P(x_j,z_j;\theta)}}$
$=P(z_j|x_j;\theta)$
得到Q(z)之后，我们就可以求解公式(4)。

所以这里的EM步骤可以归纳为

E步（expctation）
根据参数初始值或者上一轮的迭代参数结果来计算隐变量的后验概率，即隐变量的期望
$Q(z_j)=p(x_j|x_j;\theta)$
M步，求解使得似然函数最大化的参数
$argmax_{\theta}\sum_j\sum_{z_j}{Q(z_j)}log(\frac{P(x_j,z_j;\theta)}{Q(z_j)})$

大白话解释就是：

先根据分布参数计算每个样本属于各个隐变量的概率
利用各个样本所属的类别概率，然后最大化似然函数，更新分布的参数

kmeans

kmeans计算就是这样，我们先随机初始化各个类别的中心向量，然后根据中心向量计算各个样本的所属类别（E步骤），然后根据各个样本所属类别来更新各个类别的参数（中心向量；M步骤）

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 195,980评论 5赞 462
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 82,422评论 2赞 373
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 143,130评论 0赞 325
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,553评论 1赞 267
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,408评论 5赞 358
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,326评论 1赞 273
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,720评论 3赞 386
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,373评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,678评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,722评论 2赞 312
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,486评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,335评论 3赞 313
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,738评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,009评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,283评论 1赞 251
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,692评论 2赞 342
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,893评论 2赞 335

uniform机器学习极简入门5—EM算法

1 EM算法概述

2 EM算法推导

推荐阅读更多精彩内容