DataWhale-03-EM算法

2020-04-23 本文已影响0人 evanzh7

理论部分
EM算法，全称Expectation Maximization Algorithm，译作最大期望化算法或期望最大算法，它是一种迭代算法，用于含有隐变量（hidden variable）的概率参数模型的最大似然估计或极大后验概率估计。

相关概念
- 极大似然估计法（Maximum Likelihood Estimate，MLE）
  极大似然估计提供了一种给定观察数据来评估模型参数的方法，即：“模型已定，参数未知”。通过若干次试验，观察其结果，利用试验结果得到某个参数值能够使样本出现的概率为最大，则称为极大似然估计。由于样本集中的样本都是独立同分布，可以只考虑一类样本集D，来估计参数向量θ
- 贝叶斯估计方法（Bayesian estimation）
  利用贝叶斯定理结合新的证据及以前的先验概率，来得到新的概率。它提供了一种计算假设概率的方法，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。
EM基本原理
EM算法是机器学习十大算法之一，它很简单，但是也同样很有深度，简单是因为它就分两步求解问题，
E步：求期望（expectation）
M步：求极大（maximization)
深度在于它的数学推理涉及到比较繁杂的概率公式等。
输入：观测变量数据Y，隐变量数据Z，联合分布 $P(Y, Z | \theta)$ ，条件分布 $P(Z | Y, \theta)$
输出：模型参数 $\theta$

选择参数的初值 $\theta^{0}$ ，开始迭代
E步：记 $\theta^{i}$ 为第i次迭代参数 $\theta$ 的估计值，在第i+1次迭代的E步，计算
$\begin{aligned} Q\left(\theta, \theta^{i}\right) &=E_{Z}\left[\log P(Y, Z | \theta) | Y, \theta^{\prime}\right] \\ &=\sum_{Z} \log P(Y, Z | \theta) P\left(Z | Y, \theta^{i}\right) \end{aligned}$
这里 $P\left(Z | Y, \theta^{i}\right)$ 是在给定观测数据Y和当前的参数估计 $\theta^{i}$ 下隐变量数据Z的条件概率分布。
M步骤：求使 $Q\left(\theta, \theta^{i}\right)$ 极大化的 $\theta$ ，确定第i+1次迭代的参数的估计值 $\theta^{i+1}$ ，
$\theta^{i+1}=\arg \max _{\theta} Q\left(\theta, \theta^{i}\right)$
$Q\left(\theta, \theta^{i}\right)$ 是EM算法的核心，称为Q函数（Q function），这个是需要自己构造的。
重复第2，3步骤，直到收敛，收敛条件： $\| \theta^{i+1}-\theta^{i \|<\varepsilon_{1}}$
或者，
$\left\|Q\left(\theta^{i+1}, \theta^{i}\right)-Q\left(\theta^{i}, \theta^{i}\right)\right\|<\varepsilon_{2}$ ，收敛迭代就结束了。

推导、证明
高斯混合分布
正态分布（Normal distribution），也称“常态分布”，又名高斯分布（Gaussian distribution）。
高斯混合模型（Gaussian Mixed Model）指的是多个高斯分布函数的线性组合，理论上GMM可以拟合出任意类型的分布，通常用于解决同一集合下的数据包含多个不同的分布的情况（或者是同一类分布但参数不一样，或者是不同类型的分布，比如正态分布和伯努利分布）。

如图1，图中的点在我们看来明显分成两个聚类。这两个聚类中的点分别通过两个不同的正态分布随机生成而来。但是如果没有GMM，那么只能用一个的二维高斯分布来描述图1中的数据。图1中的椭圆即为二倍标准差的正态分布椭圆。这显然不太合理，毕竟肉眼一看就觉得应该把它们分成两类。

图1
这时候就可以使用GMM了！如图2，数据在平面上的空间分布和图1一样，这时使用两个二维高斯分布来描述图2中的数据，分别记为 𝒩(μ1,Σ1) 和𝒩(μ2,Σ2). 图中的两个椭圆分别是这两个高斯分布的二倍标准差椭圆。可以看到使用两个二维高斯分布来描述图中的数据显然更合理。实际上图中的两个聚类的中的点是通过两个不同的正态分布随机生成而来。如果将两个二维高斯分布𝒩(μ1,Σ1) 和𝒩(μ2,Σ2)合成一个二维的分布，那么就可以用合成后的分布来描述图2中的所有点。最直观的方法就是对这两个二维高斯分布做线性组合，用线性组合后的分布来描述整个集合中的数据。这就是高斯混合模型（GMM）。

图2
高斯混合模型（GMM）公式：
设有随机变量X，则混合高斯模型可以用下式表示：
$p(\boldsymbol{x})=\sum_{k=1}^{K} \pi_{k} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)$
其中 $\mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)$ 称为混合模型中的第k个分量（component）。如前面图2中的例子，有两个聚类，可以用两个二维高斯分布来表示，那么分量数K=2。 $\pi_{k}$ 是混合系数（mixture coefficient），且满足
$\begin{aligned} &\sum_{k=1}^{K} \pi_{k}=1\\ &0 \leq \pi_{k} \leq 1 \end{aligned}$

练习部分

算法实现

Reference

阿拉丁吃米粉：高斯混合模型（GMM）及其EM算法的理解

DataWhale-03-EM算法

猜你喜欢

热点阅读