EM算法及其应用

Size: px

Start display at page:

Download "EM算法及其应用"

穰羿
6 years ago
Views:

1 EM 算法原理及其应用罗维

2 大纲基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 2

3 EM 算法的名字由来 E 步 M 步 Expectation 期望 Maximization 最大化 EM(Expectation Maximization, 期望最大化 ) 算法 3

4 笼统的 EM 算法描述 Loop { E 步 : 求期望 (expectation) } M 步 : 求极大 (maximization) 什么函数关于什么分布的期望? 关于什么函数的最大化? 鸡生蛋, 蛋生鸡 4

5 When & What 1977 年由 Dempster 等人总结提出一种优化算法框架, 用于含有隐变量 (hidden variable) 的概率模型参数的极大似然估计 (Maximum Likelihood Estimation, MLE), 或极大后验概率估计 (Maximum A Posterior estimation, MAP) 5

[1] 机器学习十大算法 (ICDM2006) ( 英文 ) http://119.90.25.20/www.cs.uvm.

6 [1] 机器学习十大算法 (ICDM2006) ( 英文 ) [2] 机器学习十大算法 (ICDM2006) ( 中文翻译 ) 6

7 涉及到的基本概念无监督学习生成式模型隐变量先验概率后验概率似然概率 7

8 无监督学习无监督学习 : 样本没有标注聚类概率密度估计变量说明 :X 表示样本 ( 标量 or 向量 ),y 表示标注 ( 标量 ) 方法处理怎样的数据模型举例无监督学习 (X) k-means, HMM, GMM, plsa, LDA 有监督学习 (X, y) Naïve Bayes, NN, LR, ME, SVM, GBDT 半监督学习 (X) + (X, y) self-training, co-training, S3VM 强化学习 (action, state, award) Markov Decision Process(MDP) 8

9 生成式模型生成式模型带有一个故事 ( 称呼为生成故事 ) 方法对什么建模模型举例生成式模型 P(X, y i ) Naïve Bayes, HMM, GMM, plsa, LDA 判别式模型 P(y i X) NN, LR, ME, SVM, GBDT 参考文献 : 9

10 隐变量隐变量 (latent variable) 可能是建模时就带有隐变量, 也可能是为了求解方便而引入含有隐变量, 通常的 MLE 估计 MAP 估计没法实施模型 k-means HMM GMM topic model (E.g. plsa, LDA) IBM Model for Word Alignment 模型的隐变量是什么样本所属的聚类中心点隐含状态 (E.g. 词性 for 词性标注 ; 状态 for 其他序列标注模型 ) 样本所属的高斯分布 (Gaussian Distribution) topic 词语对齐 E.g. ( 布什与沙龙举行了会谈 ) (Bush held a meeting with Sharon) 10

11 先验概率后验概率似然概率贝叶斯公式 X: 标量或者向量 Y: 标量或者向量后验概率似然概率先验概率 11

12 涉及到的数学基础凸集 (convex sets) 凸函数 (convex functions) Jensen 不等式 KL 距离高斯分布 12

13 凸集参考文献 : 13

14 凸函数参考文献 : 14

15 Jensen 不等式参考文献 : 15

16 KL 距离 KL 距离又称 KL 散度 (Kullback Leibler divergence) 又称相对熵 (relative entropy) 2 个主要性质非对称 :D(p(x) q(x)) 与 D(q(x) p(x)) 不一定相等恒大于等于 0: 当且仅当 p(x)=q(x) 时, D(p(x) q(x)) = 0 参考文献 : 16

17 高斯分布参考文献 :PRML 书的第 2.3 节 17

18 大纲基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 18

19 EM 算法应用 : 以 k-means 为例一种聚类算法当有数据集 {x 1, x 2, x 3,, x N } 时, 希望找到 K 个聚类中心点, 使得最小其中 : (1) r nk 是 1-of-K 编码的 K 维变量, 只有一个维度的值为 1, 其他维度的值为 0 表示节点 n 是否属于聚类 k (2) μ k 表示聚类 k 的中心点的向量 19

20 k-means 算法目标函数有 2 类参数 r nk 和 μ k 要学习算法流程初始化 μ k Loop { E 步 } M 步是一种坐标调参法是一种 EM 算法 hard-em 20

21 k-means 算法优点方法简单, 易理解缺点局部最优解计算量大算法改进 k-means++: 效果优化基于三角不等式的性能优化基于 k-d 树的性能优化 21

22 EM 算法应用 : 以 GMM 为例 GMM: Gaussian Mixture Model 高斯混合模型 or 混合高斯模型一种混合模型一种概率密度估计模型一种图模型不但能做概率密度估计, 也可以做聚类 Soft-EM 算法 22

23 GMM 约束条件 : (1) (2) 引入隐变量 z,1-of-k 编码的 K 维向量只有一个维度的值为 1, 其他维度的值为 0 23

24 GMM 计算条件概率 P(z x) ( 很重要的一个数 ) 优化目标函数 log-likelihood 24

25 EM for GMM 对 μ k 求偏导对 Σ k 求偏导对 π k 求偏导进一步化简得到其中 N k 是 25

26 EM for GMM 算法伪代码 26

27 EM for GMM 27

28 大纲基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 28

29 正经的 EM 算法陈述以 EM for MLE 为例鸡生蛋, 蛋生鸡优化目标 ( 当 Z 为离散变量时 ) 变量说明 : X: 样本 Z: 隐变量 θ: 模型参数 {X, Z}: 完整数据 ;{X}: 不完整数据 P(X, Z θ) 好算 P(X θ) 不好算但 P(Z X, θ) 好算 29

30 30

31 EM 算法的收敛性证明 (1) 基于等式 P(X θ) = P(X, Z θ) / P(Z X, θ), 有其中, 因为 KL(q p) 恒大于等于 0, 所以 L(q, θ) 是 ln P(X θ) 的下界 31

32 EM 算法的收敛性证明 (2) 假设当前轮 θ 的值为 θ old 固定 θ old, 寻找 q(z) 使得 L(q, θ old ) 最大 32

33 EM 算法的收敛性证明 (3) 为什么是 L(q, θ)? 将 q(z) = P(Z X, θ old ) 带入 L(q, θ) 表达式得到伪代码中的 Q 函数 33

34 EM 算法的收敛性证明 (4) 固定 q(z), 寻找 θ new 使得 L(q, θ) 最大 34

35 EM 算法的效果示意图 35

36 思考 EM for PLSA? 隐变量 Z 表示主题 topic {D, W, Z} 表示完整数据 {D,W} 表示不完整数据 PLSA : Probabilistic Latent Semantic Analysis 概率潜在语义分析 36

37 EM for PLSA 参考文献 [1] Thomas Hofmann. Probabilistic Latent Semantic Analysis. UAI [2] 37

38 大纲基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 38

39 EM for MAP 极大后验概率估计 (Maximum A Posterior estimation, MAP) 优化目标 P(θ X) NOTE: 不同于 MLE 中的 P(X θ) 因为 P(θ X) = P(θ, X) / P(X), 所以有 ln P(θ X) = ln P(θ, X) - ln P(X), 继续展开有 ln P(X θ) 常量 P(θ) 是关于 θ 的先验分布 E 步不变,M 步加一项 ln P(θ) 后再求关于 θ 的最大值 39

40 Variational EM 当 E 步的 P(Z X, θ old ) 不好计算时可以基于 KL 距离找个与 P(Z X, θ old ) 分布近似的 q(z) 来代替, 且 L(q, θ old ) 大于 L(q old, θ old ) 40

41 Generalization EM 当 M 步不能基于梯度直接给出新参数的解析解时意味着 : 在 M 步, 还需要内嵌一个迭代算法计算 θ new 可以采用非线性优化算法 ( 比如共轭梯度法 ) 或者坐标调参法 Loop { E 步 : 求期望 (expectation) M 步 : 求极大 (maximization)loop { 计算 θ new_of_inner_loop } 得到 θ new } 41

42 Online EM Online learning vs batch learning Online EM vs batch EM 42

43 其他变种融入 feature 后的 EM 算法 Taylor Berg-Kirkpatrick, et al. Painless Unsupervised Learning with Features. ACL

44 主要参考文献 Christopher M. Bishop. Pattern Recognition and Machine Learning 李航. 统计学习方法 44

45 45 谢谢

Microsoft PowerPoint - 3-统计基础.pptx

Microsoft PowerPoint - 3-统计基础.pptx 机器学习 3. MLE&MAP 3. MLE & MAP 统计 / 概率基本概念与知识贝叶斯准则最大似然估计 (MLE) 最大后验估计 (MAP) MLE VS. MAP 高斯分布情形 3. MLE & MAP 统计 / 概率基本概念与知识贝叶斯准则最大似然估计 (MLE) 最大后验估计 (MAP) MLE VS. MAP 高斯分布情形基本概念概率采样空间, 事件, 代数概率公理,