Chp9：参数推断 本节课内容：计算似然的极大值 牛顿法 EM算法.

Presentation on theme: "Chp9：参数推断 本节课内容：计算似然的极大值 牛顿法 EM算法."— Presentation transcript:

1 Chp9：参数推断 本节课内容：计算似然的极大值 牛顿法 EM算法

2 极大似然估计 似然函数：令 为IID，其pdf为 ，似然函数定义为 log似然函数： 极大似然估计（MLE）：使得 最大的 ，即

3 极大似然估计 计算MLE，需要求似然函数的极值 解析法（如本章已讲过的例子） 数值计算：通过迭代 牛顿法：简单 EM算法
迭代需要初始值，矩方法得到的结果是一个较好的初始值的选择

4 牛顿法 亦称牛顿-拉夫逊（ Newton-Raphson ）方法 在MLE计算中，求 的根 牛顿在17世纪提出的一种近似求解方程的方法
使用函数 的泰勒级数的前面几项来寻找方程 的根 在MLE计算中，求 的根 对应处似然函数 取极值

5 牛顿法 将log似然函数的导数 在 处进行Taylor展开： 从而得到 因此迭代机制为：

6 牛顿法 当参数 包含多个参数为向量时，迭代机制为： 其中 为log似然函数 一阶偏导数（向量）， 为二阶偏导数矩阵，

7 EM算法 (Expectation Maximization)
特别适合：“缺失数据”（missing data）问题中对参数用MLE求解 由于观测过程的限制或问题引起的数据缺失（如聚类问题） 直接对观测数据，似然函数极值解析不可求；但若假设缺失数据（隐含变量）的值已知，则似然函数形式很简单

8 EM算法 (Expectation Maximization)
E—步：求期望（Expectation ） 在给定观测数据的条件下，计算完整似然的期望（随机变量为隐含变量） 涉及计算缺失数据的条件期望，需要利用参数的当前估计值 M —步：求极大值（ Maximization ） 求使得完整似然的期望最大的参数 又是一个极大值求解问题。通常可以解析求解，这时EM是一个很方便的工具；否则，需借助一个可靠的最大化方法求解 完整似然的期望为边缘似然（非完整似然，在观测数据上的似然函数），即为我们感兴趣的似然

9 混合模型（Mixed Model） 混合模型： 其中 ，满足 即混合模型由K个成分组成，每个成分 的权重为 如一个班级每个学生的身高为 ，
其中 ，满足 即混合模型由K个成分组成，每个成分 的权重为 如一个班级每个学生的身高为 ， 假设男生身高和女生分别服从高斯分布 、 则 其中p为男生的比例 混合模型的参数估计是EM算法最典型的应用

10 混合高斯模型 (Mixture of Gaussians Model，GMM)
若混合模型中每个成分为高斯分布， 则称为混合高斯模型 假设每个数据点根据如下规则产生： 随机选择一个成分，选择第k个成分的概率为 从第k个成分产生数据： 即

11 混合高斯模型 问题：给定IID数据 ，求参数 MLE不能解析求得，因此我们通过数值计算（如EM算法）求解。 将非完整数据 转换为完整数据
将非完整数据 转换为完整数据 ，其中 为 所属的类别。

12 观测数据和缺失数据 观测数据：观测到随机变量X的IID样本： 缺失数据：未观测到的隐含变量Y的值：
在GMM中，若 来自第k个分成，则 完整数据：包含观测到的随机变量X和未观测到的随机变量Y的数据，

13 似然函数 给定观测数据 ，非完整数据的似然函数为： 涉及求和的log运算，计算困难

14 完整似然函数 若隐含变量的值 也已知，得到完整数据的似然函数为： 明显简化 若Yi未知，则对每个Xi，需要求和
若隐含变量的值 也已知，得到完整数据的似然函数为： 明显简化 若Yi未知，则对每个Xi，需要求和 若Yi已知，则对每个Xi，只需Yi

15 EM—Expectation 由于Y是未知的，计算完整似然函数对Y求期望 定义 根据贝叶斯公式：Y的分布为 去掉完整似然函数中的变量Y
刚好得到边缘似然—非完整似然，正好是感兴趣量

16 EM—Maximization 对E步计算得到的完整似然函数的期望 求极大值（Maximization），得到参数新的估计值，即
每次参数更新会增大似然（非完整似然）值 反复迭代后，会收敛到似然的局部极大值

17 EM的收敛性（1）

18 EM的收敛性（2） 所以相邻两次似然之差为 当 时

19 EM的收敛性（3） 所以 其中 为KL散度。 所以： 如果Q增大，则观测数据的似然增大 当Q 取极大值时，观测数据的似然也在相同点取极大值
在M步，Q肯定增大 当Q 取极大值时，观测数据的似然也在相同点取极大值 EM算法会收敛到似然的局部极大值

20 混合模型中的EM算法 完整似然函数： Y的条件分布：

21 Expectation t: 第t次猜测值

22 Expectation 当 yi  l等于0 提出的项与Yi无关

23 Expectation Y1与其它Y2没有关系，所以乘法与加法可以换位置

24 Expectation 1

25 Maximization 给定第t次的猜测 t, 我们计算，使得上述期望最大。 反复迭代，直到收敛。

26 混合高斯模型GMM）中的EM算法 目标： 高斯分布： 最大化：

27 混合高斯模型GMM）中的EM算法 只与l 相关 目标： 高斯分布： 只与l 相关 最大化：

28 计算 l 由于l有限制，我们引入Lagrange乘子 , 并解下述方程。

29 计算 l 1 n 1

30 计算l

31 只需最大化该项 计算 l 对GMM unrelated

32 计算l 因此，我们需要最大化： unrelated

33 计算l 因此，我们需要最大化：

34 计算l 因此，我们需要最大化：

35 总结 第t次的估计为 则第t+1次的估计为

36 GMM实验结果举例 来自Gaussian分布N(0,1)的5, 50个点

37 GMM实验结果举例 来自Gaussian分布N(0,1)的500, 5000个点

38 来自均分分布Uniform[-1,1]的500个点

39 来自分布 的50, 500个点

40 来自分布 的5000, 50000个点

41 来自分布 的个点（k=3, 4）

42 来自分布 的个点（k=3, 2）

43 EM总结 总结 参考文献 EM会收敛到局部极值，但不保证收敛到全局最优 对初值很敏感：通常需要一个好的、快速的初始化过程 适合的情况
如矩方法得到的结果 在GMM中，用K-means聚类 适合的情况 缺失数据不太多时 数据维数不太高时（数据维数太高的话，E步的计算很费时） 参考文献 Jeff A. Bilmes, A Gentle Tutorial of the Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models

44 下节课内容 下节课内容 Bootstrap实验 再下节课内容 假设检验：Chp10