EM 算法原理及其应用 罗维
大纲 基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 2
EM 算法的名字由来 E 步 M 步 Expectation 期望 Maximization 最大化 EM(Expectation Maximization, 期望最大化 ) 算法 3
笼统的 EM 算法描述 Loop { E 步 : 求期望 (expectation) } M 步 : 求极大 (maximization) 什么函数关于什么分布的期望? 关于什么函数的最大化? 鸡生蛋, 蛋生鸡 4
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.edu/~icdm/algorithms/icdm06-panel.pdf [2] 机器学习十大算法 (ICDM2006) ( 中文翻译 ) www.itfront.cn/attachment.aspx?attachmentid=1565 6
涉及到的基本概念 无监督学习 生成式模型 隐变量 先验概率 后验概率 似然概率 7
无监督学习 无监督学习 : 样本没有标注 聚类 概率密度估计 变量说明 :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
生成式模型 生成式模型 带有一个故事 ( 称呼为生成故事 ) 方法对什么建模模型举例 生成式模型 P(X, y i ) Naïve Bayes, HMM, GMM, plsa, LDA 判别式模型 P(y i X) NN, LR, ME, SVM, GBDT 参考文献 :http://luowei828.blog.163.com/blog/static/31031204201022824726471/ 9
隐变量 隐变量 (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
先验概率 后验概率 似然概率 贝叶斯公式 X: 标量或者向量 Y: 标量或者向量 后验概率 似然概率 先验概率 11
涉及到的数学基础 凸集 (convex sets) 凸函数 (convex functions) Jensen 不等式 KL 距离 高斯分布 12
凸集 参考文献 :http://cs229.stanford.edu/section/cs229-cvxopt.pdf 13
凸函数 参考文献 : https://www.cs.utah.edu/~piyush/teaching/em_algorithm.pdf 14
Jensen 不等式 参考文献 :http://cs229.stanford.edu/section/cs229-cvxopt.pdf 15
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 参考文献 :https://www.cs.princeton.edu/courses/archive/fall11/cos597d/l03.pdf 16
高斯分布 参考文献 :PRML 书的第 2.3 节 17
大纲 基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 18
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
k-means 算法 目标函数有 2 类参数 r nk 和 μ k 要学习 算法流程 初始化 μ k Loop { E 步 } M 步 是一种坐标调参法 是一种 EM 算法 hard-em 20
k-means 算法 优点 方法简单, 易理解 缺点 局部最优解 计算量大 算法改进 k-means++: 效果优化 基于三角不等式的性能优化 基于 k-d 树的性能优化 21
EM 算法应用 : 以 GMM 为例 GMM: Gaussian Mixture Model 高斯混合模型 or 混合高斯模型 一种混合模型 一种概率密度估计模型 一种图模型 不但能做概率密度估计, 也可以做聚类 Soft-EM 算法 22
GMM 约束条件 : (1) (2) 引入隐变量 z,1-of-k 编码的 K 维向量 只有一个维度的值为 1, 其他维度的值为 0 23
GMM 计算条件概率 P(z x) ( 很重要的一个数 ) 优化目标函数 log-likelihood 24
EM for GMM 对 μ k 求偏导 对 Σ k 求偏导 对 π k 求偏导 进一步化简得到 其中 N k 是 25
EM for GMM 算法伪代码 26
EM for GMM 27
大纲 基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 28
正经的 EM 算法陈述 以 EM for MLE 为例 鸡生蛋, 蛋生鸡 优化目标 ( 当 Z 为离散变量时 ) 变量说明 : X: 样本 Z: 隐变量 θ: 模型参数 {X, Z}: 完整数据 ;{X}: 不完整数据 P(X, Z θ) 好算 P(X θ) 不好算但 P(Z X, θ) 好算 29
30
EM 算法的收敛性证明 (1) 基于等式 P(X θ) = P(X, Z θ) / P(Z X, θ), 有 其中, 因为 KL(q p) 恒大于等于 0, 所以 L(q, θ) 是 ln P(X θ) 的下界 31
EM 算法的收敛性证明 (2) 假设当前轮 θ 的值为 θ old 固定 θ old, 寻找 q(z) 使得 L(q, θ old ) 最大 32
EM 算法的收敛性证明 (3) 为什么是 L(q, θ)? 将 q(z) = P(Z X, θ old ) 带入 L(q, θ) 表达式得到 伪代码中的 Q 函数 33
EM 算法的收敛性证明 (4) 固定 q(z), 寻找 θ new 使得 L(q, θ) 最大 34
EM 算法的效果示意图 35
思考 EM for PLSA? 隐变量 Z 表示主题 topic {D, W, Z} 表示完整数据 {D,W} 表示不完整数据 PLSA : Probabilistic Latent Semantic Analysis 概率潜在语义分析 36
EM for PLSA 参考文献 [1] Thomas Hofmann. Probabilistic Latent Semantic Analysis. UAI 1999. [2] http://zhikaizhang.cn/2016/06/17/%e8%87%aa%e7%84%b6%e8%af%ad%e8%a8%80%e5%a4%84%e7%90%86%e4%b9%8bplsa/ 37
大纲 基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 38
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
Variational EM 当 E 步的 P(Z X, θ old ) 不好计算时 可以基于 KL 距离找个与 P(Z X, θ old ) 分布近似的 q(z) 来代替, 且 L(q, θ old ) 大于 L(q old, θ old ) 40
Generalization EM 当 M 步不能基于梯度直接给出新参数的解析解时 意味着 : 在 M 步, 还需要内嵌一个迭代算法计算 θ new 可以采用非线性优化算法 ( 比如共轭梯度法 ) 或者坐标调参法 Loop { E 步 : 求期望 (expectation) M 步 : 求极大 (maximization)loop { 计算 θ new_of_inner_loop } 得到 θ new } 41
Online EM Online learning vs batch learning Online EM vs batch EM 42
其他变种 融入 feature 后的 EM 算法 Taylor Berg-Kirkpatrick, et al. Painless Unsupervised Learning with Features. ACL 2010. 43
主要参考文献 Christopher M. Bishop. Pattern Recognition and Machine Learning 李航. 统计学习方法 44
45 谢谢