高斯混合模型.doc

高斯混合模型（Gaussian Mixture Model, GMM）
(2011-12-30 23:50:01)
标签：
校园
分类： 工作篇
高斯混合模型
　　高斯模型就是用高 斯概率密度函数（正态分布曲线）精确地量化事物，将一个事物分解为若干的基于高斯概率密度函数（正态分布曲线）形成的模型。对图像背景建立高斯模型的原理 及过程：图像灰度直方图反映的是图像中某个灰度值出现的频次，也可以以为是图像灰度概率密度的估计。如果图像所包含的目标区域和背景区域相比比较大，且背 景区域和目标区域在灰度上有一定的差异，那么该图像的灰度直方图呈现双峰-谷形状，其中一个峰对应于目标，另一个峰对应于背景的中心灰度。对于复杂的图 像，尤其是医学图像，一般是多峰的。通过将直方图的多峰特性看作是多个高斯分布的叠加，可以解决图像的分割问题。在智能监控系统中，对于运动目标的检测是 中心内容，而在运动目标检测提取中，背景目标对于目标的识别和跟踪至关重要。而建模正是背景目标提取的一个重要环节。
　　我们首先要提起背 景和前景的概念，前景是指在假设背景为静止的情况下，任何有意义的运动物体即为前景。建模的基本思想是从当前帧中提取前景，其目的是使背景更接近当前视频 帧的背景。即利用当前帧和视频序列中的当前背景帧进行加权平均来更新背景,但是由于光照突变以及其他外界环境的影响，一般的建模后的背景并非十分干净清 晰，而高斯混合模型
　　(GMM)是建模最为成功的方法之一。
　　英文翻译及缩写：Gaussian mixture model (GMM)　
　　混合高斯模型使用K（基本为3到5个）个高斯模型 来表征图像中各个像素点的特征,在新一帧图像获得后更新混合高斯模型,用当前图像中的每个像素点与混合高斯模型匹配,如果成功则判定该点为背景点, 否则为前景点。通观整个高斯模型，他主要是有方差和均值两个参数决定，,对均值和方差的学习,采取不同的学习机制,将直接影响到模型的稳定性、精确性和收 敛性。由于我们是对运动目标的背景提取建模，因此需要对高斯模型中方差和均值两个参数实时更新。为提高模型的学习能力,改进方法对均值和方差的更新采用不 同的学习率;为提高在繁忙的场景下,大而慢的运动目标的检测效果,引入权值均值的概念,建立背景图像并实时更新,然后结合权值、权值均值和背景图像对像素点进行前景和背景的分类。具体更新公式如下：
　　μt= (1 - ρ)μt- 1 +ρxt (1)
　　σ2t = (1 - ρ)σ2t- 1 +ρ( xt -μt ) T ( xt -μt ) (2)
　　ρ =αη( xt | μκ,σκ ) (3)
　　| xt -μt - 1 | ≤ 2. 5σt- 1 (4)
　　w k , t = (1 - α) w k , t - 1 +αMk , t (5)
　　式中ρ为学习率，即反映当前图像融入背景的速率。
　　建模过程中，我们 需要对混合高斯模型中的方差、均值、权值等一些参数初始化，并通过这些参数求出建模所需的数据，如马兹距离。在初始化过程中，一般我们将方差设置的尽量大 些（如15），而权值则尽量小些（如0.001）。这样设置是由于初始化的高斯模型是一个并不准确，可能的模型，我们需要不停的缩小他的范围，更新他的参 数值，从而得到最可能的高斯模型，将方差设置大些，就是为了将尽可能多的像素包含到一个模型里面，从而获得最有可能的模型。部分代码如下：
　　for(i=0; i<K_MODELS; i++) //K_MODELS为预先定义的模型数 { // calculate the vector, v = (X - u) for(j=0; j<3; j++) v[j] = pixel[j] - model[i]->mean[j]; // calculate the squared distance, d = |v|^2 model[i]->dist2 = v[0]*v[0] + v[1]*v[1] + v[2]*v[2]; // zot: this is only equal to mahalanobis distance // when covariance matrix = vI // (v = scalar variance for all channels) model[i]->mah2 = model[i]->dist2 / model[i]->var; //即为马兹距离 // see if X is close enough to this model if (model[i]->mah2 < SFSquared) break; // the current pixel matches one of the K models //SFSquared是预定义的值 } 同时这时又产生了一个疑问，那么如何得知我们的模型是否超过预定义的模型数了呢？这便是我们设置权值的其中一个原因了。根据大量的试验，我们得出当前面几 个模型数的权值之和在T值（一般设为0.75）之内时，效果最好，因此当我们将前面的模型权值相加，当超过0.75时便舍去后面的模型。当然其中还有一个 重要的问题，我们是如何得知前面的模型是相对来说最有可能的模型，而非被舍去的模型呢？在这里我们首先要对各个模型的权值进行排序，按照权值与方差的比率 的从大到小，对模型进行排序。由于一开始建立的模型肯定是不可靠的，在最后基本会被舍弃，因此我们在初始化的时候将初始模型的方差尽量大，而权值尽量小， 从而使最不可能的模型排在比较后面。到这里为止，混合高斯模型的建模基本完成，我在归纳一下其中的流程，首先初始化预先定义的几个高斯模型，对高斯模型中 的参数进行初始化，并求出之后将要用到的参数。其次，对于每一帧中的每一个像素进行处理，看其是否匹配某个模型，若匹配，则将其归入该模型中，并对该模型 根据新的像素值进行更新，若不匹配，则以该像素建立一个高斯模型，初始化参数，代理原有模型中最不可能的模型。最后选择前面几个最有可能的模型作为背景模 型，为背景目标提取做铺垫。

高斯混合模型（Gaussian Mixture Model, GMM）是语音信号处理中的一种常用的统计模型，该模型的一个基本理论前提是只要高斯混合的数目足够多，一个任意的分布就可以在任意的精度下用这些高斯混合的加权平均来逼近。
有限高斯混合模型可以以任意精度正逼近实数上的非负黎曼可积函数,特别可以逼近任意的概率分布密度函数。
高斯模型就是用高斯概率密度函数（正态分布曲线）精确地量化事物，将一个事物分解为若干的基于高斯概率密度函数（正态分布曲线）形成的模型。 对图像背景建立高斯模型的原理及过程：图像灰度直方图

利用高斯混合模型实现概率密度函数逼近
在图像处理中,经常需要知道图像的概率分布密度函数,然而图像的概率密度函数经常是很难准确求解的,通常的办法是通过某个已知的分布密度函数进行逼近,例如:高斯(Gaussian)分布、对数正态分布、伽玛分布、贝塔分布、指数分布、韦布尔分布、瑞利分布等,然而这类参数化分布密度要求是单峰形式,即只有一个极大值,而实际问题中,可能包含多峰的密度形式,在特征空间中往往表现为多种密度分布的混合,很难把这种复杂的分布通过单一的参数化密度函数表示出来[1]。R.Wilson在文献[2]中讨论了多分辨率高斯混合模型的函数逼近能力。在此基础上本文证明了有限高斯混合模型可以以任意精度正逼近实数上的非负黎曼可积函数,特别可以逼近任意的概率分布密度函数,并利用实例说明了有限高斯混合密度函数具有较强的逼近能力。1 有限混合密度函数在图像处理领域,有限混合分布理论的方法就是将全部像素值拟合成一个加权混合的概率密度函数,使每个权重正是该对象的像素在整个像素集里 所占的比例。高斯模型涉及均值(μ)和方差(σ2)的选择。定义1有限混合密度模型假设数据x(x∈RP)来自多个分布的混合体。

【论文题名】  利用高斯混合模型实现概率密度函数逼近 
【英文题名】  Probability Density Function Approximation Using Gaussian Mixture Model 
【 刊  名 】  无线电通信技术 
【英文刊名】  RADIO COMMUNICATIONS TECHNOLOGY 
【 分类号 】  TP301.6 
【 作  者 】  李钊 
【作者单位】  
【 年卷期 】  2007年 33卷 02期 20-22页 
【 关键词 】  高斯混合模型;函数逼近;概率密度函数;高斯分布 
【基金名称】  国家自然科学基金 
【 摘  要 】  针对图像的概率分布密度函数的不确定,利用有限高斯混合模型逼近图像的概率分布密度函数.理论上证明了有限高斯混合模型可以以任意精度正逼近实数上的非负 黎曼可积函数,特别可以逼近任意的概率分布密度函数.实例表明有限高斯混合模型逼近已知分布密度函数或未知分布密度函数时,具有逼近精度高等优点,为函数 逼近提供了理论和技术支持. 
利用高斯混合模型实现概率密度函数逼近袁礼海  李钊  宋建社 
【摘要】：针对图像的概率分布密度函数的不确定,利用有限高斯混合模型逼近图像的概率分布密度函数。理论上证明了有限高斯混合模型可以以任意精度正逼近实 数上的非负黎曼可积函数,特别可以逼近任意的概率分布密度函数。实例表明有限高斯混合模型逼近已知分布密度函数或未知分布密度函数时,具有逼近精度高等优 点,为函数逼近提供了理论和技术支持。
【作者单位】： 第二炮兵工程学院导弹工程研究所 驻石家庄地区军事代表室 第二炮兵工程学院导弹工程研究所
【关键词】： 高斯混合模型 函数逼近 概率密度函数 高斯分布
【基金】：国家自然科学基金(60272022)
【分类号】：TP391.41
【正文快照】：
0引言在图像处理中,经常需要知道图像的概率分布密度函数,然而图像的概率密度函数经常是很难准确求解的,通常的办法是通过某个已知的分布密度函数进行逼 近,例如:高斯(Gaussian)分布、对数正态分布、伽玛分布、贝塔分布、指数分布、韦布尔分布、瑞利分布等,然而这类参数化分布

高斯模型有单高斯模型（SGM）和混合高斯模型（GMM）两种。
（1）单高斯模型：

为简单起见，阈值t的选取一般靠经验值来设定。通常意义下，我们一般取t=0.7-0.75之间。

二维情况如下所示：

（2）混合高斯模型：

      对于(b)图所示的情况，很明显，单高斯模型是无法解决的。为了解决这个问题，人们提出了高斯混合模型（GMM），顾名思义，就是数据可以看作是从数个高斯分布中生成出来的。虽然我们可以用不同的分布来随意地构造 XX Mixture Model ，但是 GMM是 最为流行。另外，Mixture Model 本身其实也是可以变得任意复杂的，通过增加 Model 的个数，我们可以任意地逼近任何连续的概率密分布。
    每个 GMM 由 K 个 Gaussian 分布组成，每个 Gaussian 称为一个“Component”，这些 Component 线性加成在一起就组成了 GMM 的概率密度函数：

                （1）
其中，πk表示选中这个component部分的概率，我们也称其为加权系数。
根据上面的式子，如果我们要从 GMM 的分布中随机地取一个点的话，实际上可以分为两步：
（1）首先随机地在这 K 个 Component 之中选一个，每个 Component 被选中的概率实际上就是它的系数 πk，选中了 Component 之后，再单独地考虑从这个 Component 的分布中选取一个点就可以了──这里已经回到了普通的 Gaussian 分布，转化为了已知的问题。假设现在有 N 个数据点，我们认为这些数据点由某个GMM模型产生，现在我们要需要确定 πk,μk,σk 这些参数。很自然的，我们想到利用最大似然估计来确定这些参数，GMM的似然函数如下：
        （2）

在最大似然估计里面，由于我们的目的是把乘积的形式分解为求和的形式，即在等式的左右两边加上一个log函数，但是由上文博客里的（2）式可以看出，转化为log后，还有log(a+b)的形式，因此，要进一步求解。
我们采用EM算法，分布迭代求解最大值：
EM算法的步骤这里不作详细的介绍，可以参见博客：
http://blog.pluskid.org/?p=39

声学模型
声学模型是语音识别系统中最为重要的部分之一，目前的主流系统多采用隐马尔科夫模型进行建模。隐马尔可夫模型的概念是一个离散时域有限状态自动机，隐马尔可夫模型HMM是指这一马尔可夫模型的内部状态外界不可见，外界只能看到各个时刻的输出值。
　 　对语音识别系统，输出值通常就是从各个帧计算而得的声学特征。用HMM刻画语音信号需作出两个假设，一是内部状态的转移只与上一状态有关，另一是输出值 只与当前状态（或当前的状态转移）有关，这两个假设大大降低了模型的复杂度。HMM的打分、解码和训练相应的算法是前向算法、Viterbi算法和前向后 向算法。[
输出概率
　　声学模型的输入是由特征提取模块提取的特征。一般来说，这些特征是多维的向量，并且其取值可以是离散或连续的。早期的声学模型常常采用矢量聚类(Vector Quantification)的方法，将信号直接映射到某个码本k，而后再计算某个模型j输出该码本的概率bj(k)。但是这一方法是比较粗糙的，其性能受到VQ算法的极大影响，如果VQ本身性能就很差，声学模型的估计就会很不准确。因此，对于连续取值的特征应当采用连续的概率分布。由于语音信号特征的分布并不能用简单的概率分布，例如高斯分布等来直接描述，故而常用混合高斯模型或混合拉普拉斯模型等方法对语音信号的分布进行拟合。在此，混合高斯分布可以表示为若干高斯分量Gi的加权组合。即： 　　G(x) = \prod_{i=1}^{n}w_i\cdot G_i(x) 其中Gi(x)是均值为μi方差为σi的高斯分布。从数学角度看，当i趋向于无穷时，任何连续分布都可以用混合高斯模型来逼近。但是，高斯混合模型也存在着问题，那就是其计算量偏大。假设对于一个包含n个混合分量的混合高斯模型，其维度为m维，那么至少要进行m\times n次运算才能得到结果，如果有i个模型需要计算，那么时间复杂度就是O(mnk)。相比之下，离散HMM就相对简单，只需要进行一次VQ，再进行i次查表操作，就能够计算所有模型的概率值。因此，也出现了将二者结合起来的半连续隐马模型。其思路是输出概率不仅仅由bj(k)来决定，还乘上了VQ的概率，亦即该信号属于次码本的概率。 　　从精确度上看，连续隐马模型要优于半连续隐马模型，而半连续隐马模型又优于离散隐马模型。从算法复杂度上来看则正好相反。[2] 　　高斯混合模型（Gaussian Mixture Model, GMM）是语音信号处理中的一种常用的统计模型，该模型的一个基本理论前提是只要高斯混合的数目足够多，一个任意的分布就可以在任意的精度下用这些高斯混合的加权平均来逼近。一个包含M个分量的高斯混合分布的概率密度函数是M个高斯概率密度分布函数的加权组合，定义为[3]: 　　p(x|\lambda) = \sum_{i}^{M}\omega_ip_i(x) 其中的x是D维随机矢量，p_i(x), i = 1, 2, \cdots,M为M个概率密度函数分量，\omega_i, i = 1,2,\cdots,M为各个概率密度函数分量的权重。在上式中，每个概率密度函数分量pi(x)都服从D维高斯分布，即 　　p_i(x)=\frac{1}{(2\pi)^{D/2}|\Sigma_i|} \exp\left\{-\frac{1}{2}(x-\mu)'\Sigma_i^{-1(x-\mu_i)}\right\} 其中，μi表示该高斯分量的均值，Σi表示该高斯分量的协方差矩阵。另外，为了满足概率密度函数分布的要求，上式中各个概率密度函数分量的权重必须满足\sum_{i=1}^{M}w_i = 1的要求。 　　在高斯混合模型中，每一个高斯概率密度函数分量pi(x)都可以由其权重wi、均值μi和协方差矩阵Σi来描述。这样，一个完整的M分量混合的高斯分布就可以由以下的三元组集合来表示： 　　\lambda=\left\{w_i,\mu_i,\Sigma_i\right\} \quad\quad i=1,2,\cdots,M GMM模型的主要问题为训练问题，亦即参数估计问题数估计，使得GMM模型和训练数据之间达到最佳的匹配程度。GMM的参数估计方法有多种方法，其中应用最广泛的是基于最大似然准则(Maximum Likelihood Estimation, MLE)的方法。 　　对于一段给定的训练语音特征序列O = O_1,O_2,\cdots,O_T ，GMM模型的似然度定义为： 　　p(O|\lambda) = \prod_{t=1}^{T}p(O_t|\lambda) 最大似然估计的主要思想就是要找到使得GMM模型对于训练语料的似然度最大的模型参数λ。同HMM的训练类似，GMM训练也可以通过EM进行训练，其模型参数更新公式为： 　　\hat{w}_i = \frac{1}{T}\sum_t^{T}p(i|x_t,\lambda) \hat{\mu}_i = \frac{\sum_{t=1}^{T}p(i|x_t,\lambda)x_t}{\sum_{t=1}^{T}p(i|x_t,\lambda)} \hat{\sigma}_i = \frac{\sum_{t=1}^{T}p(i|x_t,\lambda)x^{2}_t}{\sum_{t=1}^{T}p(i|x_t,\lambda)\hat{\mu}_i^2}- 　　其中p(i | xt,λ)表示xt属于第i个高斯分量的后验概率。而w_i,\mu_i,\sigma_i^2分表表示上一步迭代中模型的权重、均值、协方差矩阵，而\hat{w_i},\hat{\mu_i},\hat{\sigma}_i^2则是更新后的对应参数。p(i | xt,λ)的定义为： 　 　p(i|x_t,\lambda) = \frac{w_ip_i(x_i)}{\sum_{k=1}^M w_kp_k(x_i)} 如果随机矢量各维间的是独立的，那么可以采用对角协方差阵，亦即仅估计方差。这种方法能够极大减少模型参数，让模型训练更加充分。同时，需要注意的是，在 某些情况下，对角协方差阵可能会出现非常小的方差值，从而使得协方差阵奇异。因此在训练对角协方差阵的时候必须采用最小方差约束。亦即当新估计出的某维方 差\hat{\sigma}_i小于设定σmin时，让\hat{\sigma}_i等于σmin。 　　在声学模型训练中常用GMM为状态输出概率建模，同时GMM也常用于其他声音分类任务中，例如声音分割与分类，说话人识别等。
模型拓扑结构
　　由于语音的时序性，隐马模型的拓扑结构一般都取为自左向右的结构。一般每个状态都包括自跳转弧。是否允许跨状态跳转则没有一个定论。 　　下图是典型的模型拓扑结构示意图。 　　状态个数的选择对于系统性能的影响是很大的。 　　建模单元选择 　　声学模型的建模单元的选择需要考虑三方面的因素。其一是该单元的 可训练性，亦即是否能够得到足够的语料对每个单元进行训练，以及训练所需要的时间长短是否可接受。其二是该单元的可推广性，当语音识别系统所针对的词汇 集\mathcal{W}发生变化时，原有建模单元是否能够不加修改的满足新的词汇集\mathcal{W'}。最后还需要考虑建模的精确性。 　　根据时间尺度的长短，建模单元可以选择为句子，短语，词，音节， 音子乃至更小的半音子。一般可以认为有这样的原则，时间尺度越短的建模单元，其可训练性及推广性就越强，而时间尺度越长的单元，其精确性就越强。同时，可 以看出，句子、短语、词三个概念是语言学上的概念，而音节、音子则是语音学上的概念，一般来说，如果声学模型所针对的应用环境不是确定词汇量的系统，那么 采用语言学的概念的建模单元是不具备推广性的。 　　为了将协同发音现象(Coarticulation)融入建模中，上下文相关的建模单元(Context Dependent Modeling Units, CD uinits)是一个很好的选择。其思路是，对于某个音子ah，根据上下文的不同将其拆分成不同的建模单元。例如，用b-ah+d表示ah在b之后，d之前发音的具体实现。上下文的选择方法有很多，最常见的是三音子建模单元，也就是考虑左上文右下文各一个音子，加上中心音子形成三音子对。 　　上下文相关建模大大提高了建模的准确性，但是同时也使得模型数量急剧膨胀，使得模型的可训练性大大降低。为了解决这一问题，就需要引入某些聚类算法来减少模型中需要训练的参数。
聚类方法
　　为了解决模型参数过多的问题，可以使用某些聚类方法来减小模型中的参数数量，提高模型的可训练性。聚类可以在模型层次，状态层次乃至混合高斯模型中每个混合的层次进行。可以将半连续隐马模型看作进行高斯混合进行聚类后的连续隐马模型。目前应用最多的方法是对状态聚类的方法。其思路是，根据状态间混合高斯模型概率输出的相似性，将输出概率接近的状态聚合在一起，以便对其的训练更加充分。聚类的方法有基于规则的方法和数据驱动方法两类。 　　聚类后的状态被称为Senone，每个Senone都是完整独立的高斯混合模型，它也是解码过程中的最基本单元
参数估计
　　传统上，参数估计使用的方法为Baum-Welch算法，属于最大似然准则下的EM算法。目前研究者提出了多种区分性训练方法（仍然属于产生式模型，但使用区分性准则）进行训练，取得了较好的效果。
参考资料
　　^ 高勤 汉语语音文档检索技术研究及系统实现 北京大学硕士研究生学位论文 ^ L.R. Rabiner, “A tutorial on Hidden Markov Models and selected applications in speech recognition”, in Proceedings of the IEEE, vol. 77, pp. 257–287, 1989 ^ D.A. Reynolds and R.C. Rose, “Robust text-independent speaker identification using Gaussian mixture speaker models”, IEEE Transaction on Speech Audio Process, vol. 3, pp. 72–83, 1995. ^ K.F. Lee, Large-vocabulary speaker independent continuous speech recognition, the Sphinx system, Ph.D. thesis, Carnegie Mellon University, 1988.

Expectation–maximization algorithm

Wikipedia on A:
Expectation–maximization algorithm

Home > Library > Miscellaneous > Wikipedia
In statistics, an expectation–maximization (EM) algorithm is an iterative method for finding maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables. The EM iteration alternates between performing an expectation (E) step, which computes the expectation of the log-likelihood evaluated using the current estimate for the parameters, and a maximization (M) step, which computes parameters maximizing the expected log-likelihood found on the E step. These parameter-estimates are then used to determine the distribution of the latent variables in the next E step.
Contents
· 1 History
· 2 Description
· 3 Properties
· 4 Alternative description
· 5 Applications
· 6 Variants
· 7 Relation to variational Bayes methods
· 8 Geometric interpretation
· 9 Example: Gaussian mixture
o 9.1 E step
o 9.2 M step
· 10 References
· 11 References
· 12 External links
History
The EM algorithm was explained and given its name in a classic 1977 paper by Arthur Dempster, Nan Laird, and Donald Rubin.[1] They pointed out that the method had been "proposed many times in special circumstances" by earlier authors. In particular, a very detailed treatment of the EM method for exponential families was published by Rolf Sundberg in his thesis and several papers[2][3][4] following his collaboration with Per Martin-Löf and Anders Martin-Löf.[5][6][7][8][9][10][11] The Dempster-Laird-Rubin paper in 1977 generalized the method and sketched a convergence analysis for a wider class of problems. Regardless of earlier inventions, the innovative Dempster-Laird-Rubin paper in the Journal of the Royal Statistical Society received an enthusiastic discussion at the Royal Statistical Society meeting with Sundberg calling the paper "brilliant". The Dempster-Laird-Rubin paper established the EM method as an important tool of statistical analysis.
The convergence analysis of the Dempster-Laird-Rubin paper was flawed and a correct convergence analysis was published by C. F. Jeff Wu in 1983. Wu's proof established the EM method's convergence outside of the exponential family, as claimed by Dempster-Laird-Rubin.[12]
Description
Given a statistical model consisting of a set of observed data, a set of unobserved latent data or missing values , and a vector of unknown parameters , along with a likelihood function , the maximum likelihood estimate (MLE) of the unknown parameters is determined by the marginal likelihood of the observed data

However, this quantity is often intractable.
The EM algorithm seeks to find the MLE of the marginal likelihood by iteratively applying the following two steps:
Expectation step (E step): Calculate the expected value of the log likelihood function, with respect to the conditional distribution of given under the current estimate of the parameters :

Maximization step (M step): Find the parameter that maximizes this quantity:

Note that in typical models to which EM is applied:
1. The observed data points may be discrete (taking values in a finite or countably infinite set) or continuous (taking values in an uncountably infinite set). There may in fact be a vector of observations associated with each data point.
2. The missing values (aka latent variables) are discrete, drawn from a fixed number of values, and there is one latent variable per observed data point.
3. The parameters are continuous, and are of two kinds: Parameters that are associated with all data points, and parameters associated with a particular value of a latent variable (i.e. associated with all data points whose corresponding latent variable has a particular value).
However, it is possible to apply EM to other sorts of models.
The motivation is as follows. If we know the value of the parameters , we can usually find the value of the latent variables by maximizing the log-likelihood over all possible values of , either simply by iterating over or through an algorithm such as the Viterbi algorithm for hidden Markov models. Conversely, if we know the value of the latent variables , we can find an estimate of the parameters fairly easily, typically by simply grouping the observed data points according to the value of the associated latent variable and averaging the values, or some function of the values, of the points in each group. This suggests an iterative algorithm, in the case where both and are unknown:
1. First, initialize the parameters to some random values.
2. Compute the best value for given these parameter values.
3. Then, use the just-computed values of to compute a better estimate for the parameters . Parameters associated with a particular value of will use only those data points whose associated latent variable has that value.
4. Iterate steps 2 and 3 until convergence.
The algorithm as just described monotonically approaches a local minimum of the cost function, and is commonly called hard EM. The k-means algorithm is an example of this class of algorithms.
However, we can do somewhat better by, rather than making a hard choice for given the current parameter values an