本文内容是我在学习过程中对资料的一个个人总结与学习笔记。引用内容写在灰色的引用框中。如有错误欢迎指正
这篇文章的主题是高斯混合模型(GMM),GMM与最大期望(EM)方法有很大的联系,而在GMM的求解过程中使用了极大似然估计法
一、极大似然估计
我们先来复习一下极大似然估计法是怎么进行的,来看一个概率论课上的实例
设样本服从正态分布\(N(\mu,\sigma^2)\),则似然函数为\[L(\mu,\sigma^2)=\prod^{N}_{i=1}\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x_{i}-\mu)^2}{2\sigma^2}}\]
试估计参数\(\mu\)与\(\sigma^2\)的值 其中\(x_{i}\)是样本,也就是说这个函数\(L(\mu,\sigma^{2})\)是各个样本的概率的积。
我们需要做的是由似然函数估计出参数\(\mu\)与\(\sigma^2\)的值。之所以说是估计,是因为使用有限的样本不可能准确求出原本高斯分布的参数。 那么怎么由似然函数求值呢? 1. 首先我们要对似然函数求对数,这是因为似然函数是各个事件发生的概率的积,当很多概率乘在一起时,会导致这个似然函数的值非常小,计算机由于精度的原因无法处理 2. 对参数求导,再令导数为0。我们知道,这样求出的点是似然函数的极值点,而我们需要的是使得似然函数取得最大值时的参数值。这样这个极值点便很可能是我们要求的参数值 3. 求解上述似然方程 --- 求解过程如下 对似然函数取对数得到 \[\ln L(\mu,\sigma^2)=\sum_{i=1}^N \ln\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x_{i}-\mu)^2}{2\sigma^2}}\] 化简得到\[\ln L(\mu,\sigma^2) = -\frac{n}{2}\ln(2\pi)-\frac{n}{2}\ln(\sigma^2)-\frac{1}{2\sigma^2}\sum_{i=1}^n(x_{i}-\mu)^2\]
对参数求导得到 \[ \left \{ \begin{aligned} & \frac{\partial \ln L(\mu,\sigma^2)}{\partial\mu}=\frac{1}{\sigma^2}\sum_{i = 1}^{n}(x_i-\mu) =0\\ & \frac{\partial \ln L(\mu,\sigma^2)}{\partial\sigma}=-\frac{n}{2\sigma^2}+\frac{1}{2\sigma^4}\sum_{i=1}^n(x_i-\mu)^2 \end{aligned} \right.\] 联合求解得到 \[ \left \{ \begin{aligned} & \hat{\mu}=\overline x = \frac{1}{n}\sum_{i=1}^N x_i \\ & \hat\sigma^2=\frac{1}{n}\sum_{i=1}^N(x_i-\overline x)^2 \end{aligned} \right.\]
现在我们来概括一下,极大似然法分为如下几步 > (1)写出似然函数; > (2)对似然函数取对数,并整理 (3)求导数; (4)解似然方程。
最大似然估计的特点:
1.比其他估计方法更加简单;
2.收敛性:无偏或者渐近无偏,当样本数目增加时,收敛性质会更好;
3.如果假设的类条件概率模型正确,则通常能获得较好的结果。但如果假设模型出现偏差,将导致非常差的估计结果。
一定要注意一点,我们在进行极大似然估计时,样本服从什么分布是我们假定的。 另外,极大似然估计方法也可以用一个简单的式子来概括: \[θ=arg\max_θ∑_i \log P(x^{(i)};θ)\] 也即\(\theta\)为使得似然函数取最大值时对应的\(\theta\)值
二、GMM原理
首先我们来了解一下机器学习中的归纳偏执(bias) >在机器学习中,一个学习算法也会有一个前提假设,这里被称作“归纳偏执 (bias)”(bias 这个英文词在机器学习和统计里还有其他许多的意思)。例如线性回归,目的是要找一个函数尽可能好地拟合给定的数据点,它的归纳偏执就是“满足要求的函数必须是线性函数”。一个没有归纳偏执的学习算法从某种意义上来说毫无用处,就像一个完全没有归纳能力的人一样,在第一次看到鱼的时候有人告诉他那是鱼,下次看到另一条鱼了,他并不知道那也是鱼,因为两条鱼总有一些地方不一样的,或者就算是同一条鱼,在河里不同的地方看到,或者只是看到的时间不一样,也会被他认为是不同的,因为他无法归纳,无法提取主要矛盾、忽略次要因素,只好要求所有的条件都完全一样──然而哲学家已经告诉过我们了:世界上不会有任何样东西是完全一样的,所以这个人即使是有无比强悍的记忆力,也绝学不到任何一点知识。 这个问题在机器学习中称作“过拟合 (Overfitting)”,例如前面的回归的问题,如果去掉“线性函数”这个归纳偏执,因为对于 N 个点,我们总是可以构造一个 N-1 次多项式函数,让它完美地穿过所有的这 N 个点,或者如果我用任何大于 N-1 次的多项式函数的话,我甚至可以构造出无穷多个满足条件的函数出来。如果假定特定领域里的问题所给定的数据个数总是有个上限的话,我可以取一个足够大的 N ,从而得到一个(或者无穷多个)“超级函数”,能够 fit 这个领域内所有的问题。然而这个(或者这无穷多个)“超级函数”有用吗?只要我们注意到学习的目的(通常)不是解释现有的事物,而是从中归纳出知识,并能应用到新的事物上,结果就显而易见了。 没有归纳偏执或者归纳偏执太宽泛会导致 Overfitting ,然而另一个极端──限制过大的归纳偏执也是有问题的:如果数据本身并不是线性的,强行用线性函数去做回归通常并不能得到好结果。难点正在于在这之间寻找一个平衡点。不过人在这里相对于(现在的)机器来说有一个很大的优势:人通常不会孤立地用某一个独立的系统和模型去处理问题,一个人每天都会从各个来源获取大量的信息,并且通过各种手段进行整合处理,归纳所得的所有知识最终得以统一地存储起来,并能有机地组合起来去解决特定的问题。这里的“有机”这个词很有意思,搞理论的人总能提出各种各样的模型,并且这些模型都有严格的理论基础保证能达到期望的目的,然而绝大多数模型都会有那么一些“参数”(例如 K-means 中的 k ),通常没有理论来说明参数取哪个值更好,而模型实际的效果却通常和参数是否取到最优值有很大的关系,我觉得,在这里“有机”不妨看作是所有模型的参数已经自动地取到了最优值。另外,虽然进展不大,但是人们也一直都期望在计算机领域也建立起一个统一的知识系统(例如语意网就是这样一个尝试)。
GMM就是这样的一种归纳偏执:我们假定样本服从一种高斯分布,不过这种高斯分布与"单一的"高斯分布不一样,它由若干个高斯分布混合起来而形成。
Gaussian Mixture Model (GMM)。 GMM 和 k-means 很像,不过 GMM 是学习出一些概率密度函数来(所以 GMM 除了用在 clustering 上之外,还经常被用于 density estimation ),简单地说,k-means 的结果是每个数据点被 assign 到其中某一个 cluster 了,而 GMM 则给出这些数据点被 assign 到每个 cluster 的概率,又称作 soft assignment 。
每个 GMM 由 K 个 Gaussian 分布组成,每个 Gaussian 称为一个“Component”,这些 Component 线性加成在一起就组成了 GMM 的概率密度函数:
\[\displaystyle \begin{aligned} p(x) & = \sum_{k=1}^K p(k)p(x|k) \\ & = \sum_{k=1}^K \pi_k \mathcal{N}(x|\mu_k, \Sigma_k) \end{aligned}\] >根据上面的式子,如果我们要从 GMM 的分布中随机地取一个点的话,实际上可以分为两步:首先随机地在这 K 个 Component 之中选一个,每个 Component 被选中的概率实际上就是它的系数 _k ,选中了 Component 之后,再单独地考虑从这个 Component 的分布中选取一个点就可以了──这里已经回到了普通的 Gaussian 分布,转化为了已知的问题。
高斯混合模型解决了一个这样的问题:如果一个样本集的分布有明显的聚类特征,那么我们可以利用GMM来近似这种分布。利用GMM,不仅完成了对样本集的分类,还得到了它的一个概率密度函数。 利用概率密度函数,我们很容易就可以得到所谓似然函数
,再对它进行求解,便可以得到高斯混合模型的参数。 显然,它的似然函数是\[L= \prod_{i=1}^N \sum_{k=1}^K \pi_k \mathcal{N}(x ; \mu_k, \Sigma_k)\] log-likelihood function为: \[L_{log}=\displaystyle
\sum_{i=1}^N \log \left\{\sum_{k=1}^K \pi_k \mathcal{N}(x_i ; \mu_k, \Sigma_k)\right\}
\] 然后求解这个似然函数即可,求解过程是一个纯技术问题,我们暂时把它忽略。 总之,求解的结果是一个\(N\times K\)的矩阵,这个矩阵的每一行代表了样本属于各个component的概率,对于每一个 \(x_i\) ,我们只要取该矩阵第 i 行中最大的那个概率值所对应的那个 Component 为 \(x_i\) 所属的 cluster 就可以实现一个完整的聚类方法了。 >从上面的分析中我们可以看到 GMM 和 K-means 的迭代求解法其实非常相似,因此也有和 K-means 同样的问题──并不能保证总是能取到全局最优,如果运气比较差,取到不好的初始值,就有可能得到很差的结果。对于 K-means 的情况,我们通常是重复一定次数然后取最好的结果,不过 GMM 每一次迭代的计算量比 K-means 要大许多,一个更流行的做法是先用 K-means (已经重复并取最优值了)得到一个粗略的结果,然后将其作为初值(只要将 K-means 所得的 centroids 传入 gmm 函数即可),再用 GMM 进行细致迭代。
如我们最开始所讨论的,GMM 所得的结果(Px)不仅仅是数据点的 label ,而包含了数据点标记为每个 label 的概率,很多时候这实际上是非常有用的信息
三丶EM算法
我们可以看到,K-means与GMM实际上是有几分相似的,并且它们都可以追溯到EM算法。 EM算法是一种利用似然函数来获取模型参数的算法。 首先我们来复习两个概念
边缘分布
摘取百度百科对边缘分布的解释 >边缘分布(Marginal Distribution)指在概率论和统计学的多维随机变量中,只包含其中部分变量的概率分布。
假设有一个和两个变量相关的概率分布: \[P(x|y)\] 关于其中一个特定变量的边缘分布则为给定其他变量的条件概率分布:(增加了一个y和求和符号) \[P(x)=\sum_{y}P(x,y)=\sum_yP(x|y)P(y)\]
在这个边缘分布中,我们得到只关于一个变量的概率分布,而不再考虑另一变量的影响,实际上进行了降维操作。在实际应用中,例如人工神经网络的神经元互相关联,在计算它们各自的参数的时候,就会使用边缘分布计算得到某一特定神经元(变量)的值。
Jensen不等式
定理:X为一随机变量,如果\(f\)是凸函数,那么有\[E[f(X)]\ge f[E(X)]\]
推导
问题引入
现在我们有一组观测样本\[\vec x=(x_1,x_2...x_m)\] 在确定了归纳偏执之后,我们希望获得模型的参数,那么有 \[θ=arg\max_θ∑\log P(x_i;θ)\] 但是很不幸,我们的观测数据实际上还有隐藏的观测值数据 \[\vec z=(z_1,z_2,...z_i)\] 那么我们利用边缘分布的定义,极大化模型分布的对数似然函数如下: \[θ=arg\max_θ∑logP(x_i;θ)=arg\max_θ∑log∑_{z_i}P(x_i,z_i;θ)\] 这个式子怎么求解呢?所需要用到的方法就是EM算法了
求解过程
概括如下 >EM是一个在已知部分相关变量的情况下,估计未知变量的迭代技术。EM的算法流程如下: 初始化分布参数 重复直到收敛: E步骤:根据参数的假设值,给出未知变量的期望估计,应用于缺失值。 M步骤:根据未知变量的估计值,给出当前的参数的极大似然估计。
现在我们总结下EM算法的流程。 输入:观察数据x=(x(1),x(2),...x(m)),联合分布p(x,z;θ), 条件分布p(z|x;θ), 最大迭代次数J。 1) 随机初始化模型参数θ的初值θ0。 2) for j from 1 to J开始EM算法迭代: a) E步:计算联合分布的条件概率期望: \[Qi(z(i))=P(z(i)|x(i),θj))\] \[L(θ,θ_j)=∑_{i=1}^m∑_{z_i}Q_i(z_i)logP(x_i,z_i;θ)\] b) M步:极大化L(θ,θj),得到θj+1: \[θ_{j+1}=arg\max_θL(θ,θ_j)\] c) 如果θj+1已收敛,则算法结束。否则继续回到步骤a)进行E步迭代。 输出:模型参数θ。 ### 证明 关于证明我就不ctrl+c/ctrl+v了,直接传送门~ 传送门 # 参考资料 * 边缘分布百度百科 * EM介绍 * EM详细推导 * EM文库 * GMM原理 * 极大似然估计介绍