小象-机器学习-14.em算法

本课件包括演示文稿、示例、代码、题库、和在课程范围外向任何第散播。任何其他人或机构不得盗版、、仿造其中的创意及内容，我们 课 咨

主要内通过实例直观求 混合模型适合快速掌握GMM，及编程实通过极大似然估计详细推导EM算适合理论层面的深入理用坐标上升理解EM的过推导GMM的参数φ、µ、复习多 模复 日乘子

EM

复习：Jensen不等式：若f是凸函基本Jensen不等

：K-means算假定输入样本为S=x1,x2,...,xm，则算法步

j更新簇中心：j

1

1|cj

中止条件：迭代次数/簇中心变化率/最小平方误差

K-means

思

极大似然估10次抛硬币的结果是：正正反正正正反反正 pp1pppp1p1 p71最优解是

二项分布的极大似然估N-n次朝下hpnN 1

pn

进一

按照MLE的过程分 f

nLxn

xi

化简对数似然函xilxlog e 2 xilog e 2

2

x2i i

参数估计的结

lx

nlog221xi i

n

i2

xi i

符合直观想1nini2

xi i 该结论将作为下面分析的基

无监督分类：聚类

从直观理解猜测GMM的参数估 分布的概率为π1π2...πK，第i个

建立目标函

Nx|,

目标函由于在对数函数里面又有加和，我们没法直

第一步：估算数据来自哪个组估计数据由每个组份生成的概率：对于每个样本xi，i,k

kNxi|k,kKKj

jNxi

j,j上式中的µ和Σ也是待估计的值，因此采样迭代法：需要先验给定µ和Σγ(i,k亦可看成组份k在生成数据xi

第二步：估计每个组份的做生成了ikxi|i1,2,!N这些点。组份k一个标准 分布，利用上面的结论NN

i,k

N 1 N

Nk

i,k

Nni Nni

EM算法的提

通过极大似然估计建立目标函

问题的提

Jensen不等令Qi是z的某一个分布，Qi≥0，有

寻找尽量紧的下

进一步分

EM算法整体框

坐标上

从理论公式推导 分布的概率为φ1φ2...φK，第i个

E-

M-将多项分布 分布的参数带入

对均值求偏

分布的均

分布的方差：求偏导，等于

多项分布的参

日乘子 φi一定非负，所以，不用考

求偏导，等于

总对于所有的数据点，可以看作组份k生成了这些点。组份k是一个标准的分布，利用上面的结论：i,kxi|i1,2,!N1

ii

Nk N 1N

i,kxx

1

NN

EM

GMM与图

pLSA模基于概率统计的pLSA模型LatentSemantic

pLSA模D代表文档，Z代 (隐含类别)，W代表单词 zk的出现概率 zk出现单词wj的概率每个 整个文档的生成过程是这样

pLSA模 Pd,wPw|dPd Pw|d k

Pw|zPz|d 而Pw|z,Pz|d对应了两组多项分布，而

NMNM

j

Pd,wPw|dPd

ndi,

|

Pwj|

k

wj|

Pzk| nd,w

Pw|zPz|dPd

nd,w Pw|zPz|dPd

目标函数分观察数据为(di,wj)对 zk是隐含变量目标函

nd,w

Pw|zPz|dPdl

未知变量/自变量Pwj|zk,Pz|d 使用逐 近的办法的似然函数期望的极大值，得到最优解P(zk|di)、P(wj|zk，即：EM

求隐含变 zk的后验概假定P(zk|di)、P(wj|zk)已知，求隐含变量zk Pw|zPz|d Pz|d, K Pz|dKPwj| l在(di,wj,zk)已知的前提下，求关于参数P(zk|di)、P(wj|zk)的似然函数期望的极大值，得到最优解P(zk|di)、P(wj|zk，带入上一步，从

分析似然函数期在(di,wj,zk)已知的前提下，求关于参数P(zk|di)、P(wj|zk)的似然函数期望的极大值，得到最优解P(zk|di)、P(wj|zk，带入上一步，从

nd,wlogPw|d

i

nd,wKPz|d,wlogPw,z|d

j k1

nd,w

Pz|d,wlogPw|zPz|d k

完成目标函数的建关于参数P(zk|di)、P(wj|zk的函数E，并且， End,w k

Pz|d,wlogPw|zPz|d k PwjkK

|z|di

目标函数的求

KPz|d,wlogPw|zPz|dLagndi,wj k

|z Pz|di

k j

k

ndi,wjPzk|di,wj

令 Pw|z

Pw|z 令ndi,wjPzk|di,wj 令

|di

Pzk|di

分析第一个等

ndi,wjPzk|di,wj 令iPw|z 令i

kndi,wjPzk|di,wjkPwj|zkiMMm1iMMm1i

|d,w |d,w

|zkk|zkk nd,wPz|d,w m1i

nd,wPz|d,w nd,wPz|d,wPw|z m1

ndi,wjPzk|di,wjPwj|zk Mnd,wPz|d,wM m1

同理分析第二个等求极值时的解——M- ndi,wjPzk|di,wj

nd,wPz|d,w nd,wPz|d

di,wjPk Pz|d,w

|d,w Pw|zPz|d 别忘了E-