PDF《机器学习》

机器学习 5.

GMM&EM算法 主要内容 ? GMM聚类 ? EM算法 ? 密度估计 GMM聚类 生成模型: p(x1,x2, … , xn|θ) = ? p(xi|θ) n i=1 ? 存在隐变量θ ? MLE 模型 ?混合概率分布模型:如何表达? ? 什么混合模型更易操作? GMM聚类 ? 混合高斯分布: GMM聚类 Gaussian Mixture Model ? K 个混合分布 ? 其中第 i 个分布为高斯分 布N(μi,Σi) ? 每个数据由以下过程产生: ? 根据概率πi = P(y = i)选择第 i 个混 合分布 ? 根据分布N(μi, Σi)产生数据 x ? 与K均值聚类的本质差别: GMM聚类 ? K均值:硬判断 ? 每个样本仅属于一个类 ? 确定性模型 ? 难以预测 ? GMM:软判断 ? 每个样本以概率属于多个类 ? 生成模型 ? 容易预测,并能再生新的数据 ? GMM的数据分布函数 GMM聚类 隐变量 观测数据 混合成分 混合比例 GMM聚类 为简单起见,假设Σi = σ2 I p(x|y = i) = N(μi, Σi) p(y = i) = πi 未知变量为μ1,μ2, … , μK,σ2 , π1, π2, … , πK GMM聚类 未知变量为μ1, μ2, … , μK,σ2 , π1, π2, … , πK 最大似然估计目标函数: GMM聚类 ? 决策过程:如何判断一个点属于哪个类? ?基于后验信息: ? 线性决策面! GMM聚类 ? 若约束选择为硬选择,即: p(y = i) = ? 1,若i=C(j) 0,其它 ? 最大似然估计函数为: ? 近似退化为K均值! ? 一般GMM模型 GMM聚类 ?后验决策: GMM聚类 ?后验决策: ? 二次决策面: ? 最大似然目标: GMM聚类 ? 怎样求解?求解难度在哪里? ? 梯度下降? ? EM!!! 主要内容 ? GMM聚类 ? EM算法 ? EM算法: ? 处理隐变量分布的一种一般、通用的方法 ? 可解释为在缺失(隐)变量数据下,最大 似然估计的一种优化方法 ? 比通常采用的优化方式,如梯度下降简单 的多 ? 迭代进行两个步骤: ? E步:用均值填充隐变量(计算隐变量概率) ? M步:在完整数据上用 标准MLE/MAP估计参数 EM算法 Expectation- Maximization Majorization Minimization Algorithm ?统计与优化领域非常常用的技术! Majorization Minimization Algorithm ? 最大似然目标: GMM聚类 简单情况: ? 无标号数据x1, x2,… , xn ? K 个类 ? p(y = i) = πi, i=1,2,…,K ? 已知共同方差σ2 ? 求均值变量μ1,μ2, … , μK MLE 目标函数 EM算法 ? E步骤 ? 假设上一步迭代获得的参数值为:θt?1 = [μ1 t?1 ,μ2 t?1 ,… ,μK t?1 ] ? 在当前 t 步,构造以下 Q 函数: 更新每个数 据归类于某 个聚类的概 率EM算法 ? M步骤 E步已获得 联合分布 更新聚 类中心 EM算法 巧妙在何处??? ? 综合EM步骤 ? E步:计算所有点归属于每类的概率: ? K均值为硬分配,GMM为软分配 ? M步:计算参数最大值: ? 等价于加权MLE. EM算法 ? 一般GMM情形: ? 无标号数据x1, x2,… , xn ? K 个类 ? p(y = i) = πi, i=1,2,…,K ? 已知共同方差σ2 ? 求μi,,

πi,Σi, i=1,2,…,K EM算法 ? 一般GMM情形: ? 需要学习:θ = {μi,,

πi,Σi, i=1,2,…,K} ? 假设在 t-1 步估计值为θt?1 ? 在t步,首先建立 Q 函数(E 步),然后最大化得 到θt (M 步) EM算法 ? E步:计算每个数据隶属概率 ? M步:计算加权MLE最大参数值: EM算法 ? 示例 EM算法 ? 为什么EM能够有效? ? 在一般情况下EM还能类似操作吗? EM算法 ? 问题: EM算法 ? 观察数据:D = {x1, x2, … , xn} ? 隐变量:y ? 参数:θ ? 目标:θn = arg maxθ log P(D|θ) ? 例子:隐马尔科夫模型: EM算法 ? 观察数据:D = {x1, x2, … , xn} ? 隐变量:y = y1, y2, … , yn ? 参数:θ = [πi,A,B] 初始概率:P(x1 = i) = πi 转换概率:P(yt+1 = j|yt = i) = Aij 掷色子概率:P(xt = l|yt = i) = Bil ? 目标:θn = arg maxθ log P(D|θ) ? 目标: EM算法 ? E步: ? M步: EM算法 ? E步: ? M步: ? 定理: EM算法 ? 目标: ? E步: ? M步: EM算法 ? 收敛原理图 EM算法 ? M步是否一定要找到最大? ? 是否存在局部极优问题? ? 如何尝试解决? ? 局部极优问题: ? 如何尝试克服? EM算法 1. GMM方法的基本原理 2. EM方法的基本思想 阅读: [1] Pattern Recognition and Machine Learning, Christopher , M. Bishop, Springer, 2006. 9. Mixture Models and EM 要求