硬EM算法
Ⅰ EM Algorithm
EM算法和之前学的都不太一样，EM算法更多的是一种思想，所以后面用几个例子讲解，同时也会重点讲解GMM高斯混合模型。
极大似然估计这里面用的比较多。假设我们想要知道我们学生身高的分布，首先先假设这些学生都是符合高斯分布 我们要做的就是要估计这两个参数到底是多少。学生这么多，挨个挨个来肯定是不切实际的，所以自然就是抽样了。
为了统计学生身高，我们抽样200个人组成样本
我们需要估计的参数 首先估计一下抽到这两百人的概率一共是多少，抽到男生A的概率 抽到学生B的概率 所以同时抽到这两个学生的概率就是 那么同时抽到这200个学生的G概率
最后再取一个对数就好了：
似然函数的执行步骤：
1.得到似然函数
2.取对数整理
3.求导数，另导数为零
4.解方程得到解
首先引出凸函数的概念 那么就是凸函数，所以它的图像就是一个勾形的，看起来是一个凹函数，实际上是凸函数。
正常来看先是要引入一个最大似然函数： 但这样其实是和难求的，P(x|θ)完全混在了一起，根本求不出来，所以我们要引入一个辅助变量z。
所以我们引入隐变量的原因是为了转化成和这几个高斯模型相关的式子，否则无从下手。化简一下上式子： 既然z可以指定x，那么我们只需要求解出z就好了。
注意上面凸函数所提到的一个期望性质，这里就可以使用了。因为虽然优化了上面的式子，还是不能求出来，因为z变量实在是太抽象了，找不到一个合适的公式来表示它。EM的一个方法就是用优化下界函数的方法来达到优化目标函数的目的。
既然z很抽象，那么我们就需要一个转变一下。对于每一个样例x都会对应一个z，那么假设一个分布Q(z)是满足了z的分布的，而Q(z)满足的条件是 Qi意味着每一个x对应的z都会对应着一个Q了，这里有点复杂，再详细解释一下。一个x对应一组z，z是一个向量，但是每一个z又会分别对应一个一个分布Q。以为最后得到的z不会是一个数字，而是一个概率，也就是说Q(z)得到的是这个x样例属于这个类别的概率是多少。而z的数量，一个是当前有多少个分布混合在一起的数量。
再梳理一下：现在的样本是xi，那么每一个xi将会对应着一组的z，每一个xi同时也会对应着一个分布Qi，z其实就是反应了这个样本是来自于哪个分布的。比如这个x是A1分布做了3，A2分布做了5，那么z可能就是={3,5}。所以Qi(z)得到的是这个x属于这些个分布的概率，也就是说这些分布对x做了多少百分比的功，自然就是要等于1了。
还要注意的是，上面的 这个并不能得到Qi(z)就是分布对x做了多少功的结论，得到这个结论是后面下界函数与目标函数相等得到的。这里只是知道了总和等于1，因为是分布的总和嘛。
现在就到了公式的化简：
仔细看一下这个式子 这个式子其实就是求 的期望，假设 ，那么可以利用上面 。于是化简：
这个时候就得到了下界函数，上面也讲过了，想要相等，自然就是x要是常数，所以 既然 ，而且z也是一样的，因为一个样本嘛。所以上下加和（如果是离散的，那就sum一下，连续的那就积分，这里是离散的，所以就是sum一下）。于是有
于是有：
这就是整一个EM算法的框架了，可以看到其实没有比较具体的算法，大致上就是一个框架。那么问题来了，怎么样证明这东西是一个收敛的？？
可以直接把高斯混合模型代入EM框架里面。
存在多个高斯分布混合生成了一堆数据X，取各个高斯分布的概率是 ，第i个高斯分布的均值是 ，方差是 ，求法φ，μ，σ。
按照套路，第一个E-step求出Q，于是有：
意思就是求出第i个样本属于第j个分布的概率是多少。之后就是M-step了，就是化简了：
这里可能需要解释一下，根据 至于条件，因为很明显，z是隐变量，只是指明了x是属于哪个类别，和μ，Σ没有什么关系，所以直接忽略那两个参数了，所以P(z)是没有那两个参数的，z是代表了分布，所以每一个分布的概率肯定是包括了，所以就只有一个概率的参数。P(x|z)是本身的概率，就是已经知道分布是那个了，求属于这个分布的概率是多少，既然已经选定了分布那么自然就不需要再看φ了，因为φ是各个分布的概率。
现在有两个硬币AB，进行5次试验每一次投10次，并不知道是哪个硬币投的，求两种硬币的正面的概率。
首先E-step：
首先先初始化一下，
第一个试验选中A的概率：
同样求得
计算机出每一个试验的概率然后相加求均值。
之后就是M-step了：
方差的求解就不玩了，主要就是迭代求解μ和φ的值了。
首先是生成数据，4个高斯分布，每一个高斯分布的sigma都是一样的，不一样的只有μ和α，也就是φ，习惯上把前面的一个参数叫做权值，所以用α来表示。
这四个模型的比例分别是1:2:3:4，使用EM来找到他们属于的类别。
其实如果用kmeans聚类的话更加快速，但是这里还是用EM。
E-step：
就是按照公式来求解w即可，求解每一个分布对样本点做了多少的功，之后求单个样本点求比例。
M-step：
直接按照公式优化即可。
运行函数。看看结果：
结果其实还是相差不大。达到预期。
上面所讲的其实只是一种理解方法，在李航老师的统计学习方法里面是另一种比较厉害的解法：
1.E-step：求出Q函数。
2.M-step：利用Q函数求极大值。
其实这两种方法是完全一样的，Q函数就是下界函数，
EM和Kmeans算法其实很类似，事实上步骤基本可以用EM框架来替换，但是Kmeans算法是硬分类，说一不二，但是EM算法不太一样，是软分类，百分之几是那个，百分之几是这个。
缺点也还是有的：初值敏感，局部最优。因为存在了隐变量，所以导致了直接对x做极大似然是不可行的，log已经在sum的外面了。所以EM算法就转向了下界函数，而这种方法本来就不保证找到局部最优解。
如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题。如果一个目标函数存在多个变量，那么梯度下降牛顿法这些逼近方法就用不了了。但我们可以使用坐标上升方法，固定一个变量，对另外一个求导数，然后替换最后逐步逼近极值点。对应到EM算法也是一样，E步求隐含的z变量，Mstep求解其他参数。
Ⅱ NLP自然语言处理
罗素悖论：由所有不包含自身的集合构成的集合
例子：理发师称只给那些不给自己理发的人理发。
基于集合论，理发师无论给自己理发还是不给自己理发都是矛盾的。
因此集合论不是完备的。 即使后面冯罗伊德等科学家提出了各种假定条件。
由于上述的原因，集合率无法很好的描述自然语言，科学家发现通过概率模型可以更好的描述自然语言。
深度学习来处理自然语言属于概率模型
证明最小点位于坐标轴上
h = f+c|x|
由于在x = 0处不可导
h-left'(0)*h-right'(0) = (f'+c)*(f'-c)
那么如果c>|f'(0)|可得，h在0处左右导数异号
0是最值。
那么在损失函数加入L1正则化后，可以得到某些维度容易为0，从而得到稀疏解
几乎所有的最优化手段，都将适用凸优化算法来解决
P(A|B) = P(A and B) / P(B)
if A and B 独立
=》P(A and B| C) = P(A|C)*P(B|C)
也可以推出
=>A(A|B and C) = P(A|C) (B交C不为空)
抛9次硬币，硬币出现正面的概率是0.5，出现k次的概率分布如下如
服从正态分布
x的平均值
E = x*p(x) + ...
x相对于期望的偏离
var = (x-E(x))^2
conv = (x - E(x))*(m - E(m))
描述x,m是否有同分布
按理协方差为0，并不代表x和m没有关系
例如下图
如果点的分布对称的分布，会得到协方差为0，但是其实他们是有关系的。
把每个相关的概率累加，得到联合概率
P(x1=m1,x2=m2...) = n!*P1 m1/m1!*P2 m2/m2!
T(n) = (n-1)!
T(x)用一条曲线逼近n!，进而可以求得非整数的阶乘
由二项式分布推出
P = T(a+b)*x (a-1)*(1-x) (b-1)/(T(a)*T(b))
则正态分布
y为0时，不考虑y‘。y为1时，y'越接近1，越小，越靠近0，越大
把D最小化，迫使y'逼近y
对于一个句子，有若干单词组成。例如
C1: The dog laughs.
C2: He laughs.
那么计算P(C1) = P(The, Dog, laughs)的概率和P(C2) = P(He, laughs)的概率。
根据历史文本的统计学习。
可以得到P(C1)<<P(C2)
P('I love the game') = P('I')*P('love')*P('the')*P('game')
其中P(<work>) = 频率/总单词数
计算一篇文章是积极的还是消极的。
P(y|x) = sigmod(wx)
x是文章内每个单词的频率
y表示积极和消极情感
其中P(xk|x1, x2,..xk-1) = frequence(x1, x2 ,, xk)/frequence(x1, x2..xk-1)
2-gram模型例子
把多个gram的模型进行线性整合
P(y|x1, x2, .. xn) = P(y)*P(x1, x2, ... xn|y) / P(x1, x2, ... xn)
y代表是否是垃圾邮件
x代表单词
广州市长寿路 -》 广州市长|寿路
广州市长寿路 -》 广州市|长寿路
匹配词袋：广州市，广州市长，长寿路
使用最大匹配发，第二个分词更优
通过统计P(A|B)，得出各个option的概率，取最大的概率，则为最后的分词
word => [0, 0 , ... 1, ... 0]
word => [0, 1, 0, 1, 0, ...]
可以解决词相似性问题
计算附近词的频率
word => [0, 3, 0, 1, 0, ...]
w是附近词的one-hot encoding
score是词的one-hot encoding
最后一层通过softmax，取拟合文本
最终中间层则为词向量
输入为词one-hot encoding
输出为附近此的one-hot encoding
最后通过softmax预测附近词
最后中间层则为结果词向量
混合模型是一种统计模型，问题中包含若干个子问题，每个子问题是一个概率分布，那么总问题就是若干个子问题的组合，也就是若干个子分部的组合，这样就形成了混合模型。
有红黑两种硬币，把它们放在盒子里，从盒子里随机抽取一个硬币并投币，抽到红色的概率是p，红色硬币正面的概率是q，黑色硬币正面的概率是m，假设我们没办法看到抽取出的硬币的颜色，只能看到最终是正面或者反面的结果，例如HTTHTTTTHHH (H:正面 T: 反面)。需要估计p,q,m三个参数。
此时可以计算出
通过EM算法迭代如下：
随机p q m
迭代以下过程：
计算上面table
p = (aC(正)+cC(反))/total
q = aC(正)/(aC正+cC正)
m = bC(正)/(bC正 + dC正)
假设有上述数据，需要用混合模型来逼近，通过分析，红色和蓝色数据分别为高斯正态分布，N(u, v)
此时可以得到如下表
p = pN红x/(pN红x+(1-p)N蓝x)
u = pN红x/n
v = pN红(x-u)^2/n
词性转换概率
词性到单词的转换概率
通过EM递归算法，训练以上参数，得到隐马尔可夫模型
PLSA主题模型
只统计词的频率，不计算词的相对位置
计算文档和单词频率的矩阵
进行奇异矩阵分解
得到A矩阵的压缩U，U中的k则为k个主题
通过分析，LSA得到的主题是跟现实无法关联，它只是一个量，而没有明显的意义。
PLSA为了解决此问题，引入概率模型，先确定主题个数
然后通过构建Doc->topic的概率table，和topic->word的概率table。
然后通过EM模型，得到这两个table的所有概率值。
进而得到文档的主题表示
PLSA的缺陷是，对于预测未知的doc，无法计算此文档的相关概率。随着doc数量的增加，PLSA模型的参数会线性增加，从而会造成过拟合。
LDA通过引入先验概率来克服PLSA的问题。
类似于编译原理的上下文无法句法分析，一颗语法树
通过对CFG引入概率参数
有了概率，可以计算每颗语法树的极大似然概率，并取最大概率的树为最终输出
上一个状态中间层的输出作为下一隐层的输入
类似于HMM的2-gram模型。t状态受到t-1时刻输出的影响，受t-k的输出的k越大，影响越小
由于RNN几乎只受到上一时刻的影响，而忽略了久远信息的影响。从而造成了一定的局限性。
LSTM通过引入长短记忆方法，来维持长记忆的信息。
通过训练核内的sigmod函数，使得LSTM可以根据不同的句子，有条件的保留和过滤历史信息，从而达到长记忆的功能。
GRU是LSTM的简化版，它只需要处理两个sigmod函数的训练，而LSTM需要三个sigmod函数的训练，减少了训练的参数，加快了训练的速度，但也损失了一部分模型的复杂，在处理较复杂问题时，没有LSTM那么好。
auto-encoder-decoder的特点是输出的单元数是固定的。对于一般自然语言处理，例如机器翻译，输入的单元个数跟输出单元的个数并不是一一对应的，此时就需要动态的生成输出单元。Seq2Seq通过动态的输出结束符，代表是否输出完成，达到可以动态的根据输入输出不同的单元个数。
seq2seq的缺点是，所有的输入序列都转化为单一的单元c，导致很多信息都将消失，对于不同的输出yi，它可能依赖的输入xj有可能不一样，此时通过加入注意力模型，通过对xi进行softmax处理，并加入到y权重的训练中，可以让不同的y，有不同的x对它进行影响
softmax的输入为输入单元x，和上一个输出单元y，联合产生softmax的权重，进而对不同的序列，对于同一个x，会有不同的注意力到输出
q = Wq(x)
k = Wk(x)
v = Wv(x)
x为词向量
通过训练，得到权重w，从而学习到这一层的softmax注意力参数
R是前一次encoder的输出
通过增加w的数量，产生多个z，并进行堆叠，通过前馈网络，最后产生z
在使用self attention处理句子时，是没有考虑单词在句子中的位置信息的。为了让模型可以加入考虑单词的位置信息，加入了位置编码的向量
计算如下：
pos为单词在句子中的位置
i为词向量的位置
d为句子的长度
位置编码加上词向量形成tranformer的输入
加入了归一化和残差网络
最终通过softmax，输出每个单词的概率，并最终输出单词
Ⅲ 期望最大算法(EM)
1977年，DempSter首次提出EM算法。
假设四种实验结果，发生的概率依次为 ，且发生的次数为 ，求 的估计。
解：使用MLE，得到：
上式是关于 的一元三次方程，不易解。
因此，以下另作处理（引入隐变量）：
将第一部分 分为 ，且出现次数为 次
将第三部分 分为 ，且出现次数为 次；
则
(1)
现在，并不知道 （隐变量）的值，只能知道分布的信息， 服从的分布为二项分布，概率数值类似于条件概率，第一个的概率是用 除以 得到的，第二个同理：
其中， ，
第一步（E步）：求期望的目的是为了消去隐变量 。
;
代入(1)式，得到：
第二步（M步）：取最大值。
EM算法使用迭代法来更新参数。 （精髓）
任意取 ，就可以开始按照上面的公式进行迭代了。
收敛性 ：
DempSter证明：在很一般的条件下，最后会收敛。（可以参考李航老师的《统计学习方法》）
解析解：能列出公式解决的，数值上是更准确的（相比迭代解），比如MLE就是列出公式求解。
迭代解：退而求其次，当解析解难求的时候，通过迭代逼近的方式，可以获得令人满意的解，比如EM就是为了解决当MLE遇到高次方程难以求解的时候，提出的方法。
问：给定参数 ，观测变量 ，隐变量 ，如何估计参数 ？
从观测序列，可以获得：
此时，对数似然函数为：
由于包含和（积分）的对数，因此直接求解困难。
解析解困难，转而使用迭代解：假设第i次迭代后的 为 ，由于我们希望似然函数 是增大的，即 。
此时，考虑两者的差：
不等式右边是 的下界，记为 ，那么，使得下界尽可能大，即：
Algorithm: Estimation Maximum (EM)
举例：以三硬币模型为例。有A、B、C三枚硬币，分别有 的概率为正面。每次试验为：先投A硬币，如果A为正面，则投B硬币；否则，投C硬币。最终，可以观测到的结果为硬币的正/反面，但是不知道是由B还是C投出的（隐变量）。问：如果某次试验数为10的结果为：{1,1,0,1,0,0,1,0,1,1}，如何估计参数 ？
显然，题目的 隐变量为A硬币投出的结果，此时可以采用EM解法。
先从“E”入手，求解Q函数：
然后，逐一击破：
回代 函数：
极大似然求导数，令其为0，能取得极值点：
令上式为0
------对应书(9.6)式
令上式为0
------对应书(9.7)式
令上式为0
------对应书(9.8)式
至此，只要根据当前迭代下的 ，就能得到不同 下标的 ，进而得到下一次迭代的 。
Ⅳ EM算法深度解析
最近在做文本挖掘的时候遇到了EM算法，虽然读书的时候简单地接触过，但当时并没有深入地去了解，导致现在只记得算法的名字。既然EM算法被列为数据挖掘的十大算法之一，正好借这个机会，重新学习一下这个经典的算法。学习的过程中，我发现网上的资料大多讲解地不够细致，很多地方解释得并不明了。因此我决定抛开别人的想法，仅从数学推导本身出发，尽力理解每一个公式的含义，并将其对应到实际的实验过程当中。这篇博客记录了我对与EM算法的思考与理解，也是我人生中的第一篇博客，希望能够对于想要学习EM算法的同学有所帮助。
前面谈到我在做文本挖掘的时候遇到了EM算法，EM算法用于估计模型中的参数。提到参数估计，最常见的方法莫过于极大似然估计——在所有的候选参数中，我们选择的参数应该让样本出现的概率最大。相信看到这篇笔记的同学一定对极大似然估计非常熟悉，而EM算法可以看作是极大似然估计的一个扩充，这里就让我们用极大似然估计来解决一个简单的例子，来开始正式的讨论。
有A，B，C三枚硬币，我们想要估计A，B，C三枚硬币抛出正面的概率 , , 。我们按如下流程进行实验100次：
记录100次实验的结果如下：
我们将上面的实验结果表述如下：
表示第i次实验中，硬币A的结果，1代表正面，0代表反面； 表示第i次实验中，硬币B或硬币C抛出正面的个数，则参数 的极大似然估计分别为：
即硬币A，B，C各自抛出正面的次数占总次数的比例，其中 为指示函数。
实验流程与1相同，但是我们不慎遗失了硬币A的记录结果，导致我们只知道随后十次抛出了多少次正面，多少次反面，却不知道实验结果来自于硬币B还是硬币C。在这种情况下，我们是否还能估计出 , , 的值呢？
这时候利用极大似然估计似乎行不通了， 因为这种情况下，我们不但缺失了硬币A产生的观测值，同时也不知道哪些观测值属于硬币B，哪些观测值属于硬币C。
有些同学可能会提出，虽然我们无法得到三个硬币各自产生的样本，但是我们依然可以得到每个观测值出现的概率。比如在第一次实验中， 我们抛出了5次正面5次反面，我们可以做如下思考：
假设这5次正面由硬币B得到，那么概率应该为 ，而这次观测值来自于硬币B，也就是硬币A抛出正面的概率为
假设这5次正面由硬币C得到，那么概率应该为 ，而这次观测值来自于硬币C，也就是硬币A抛出反面的概率为
综合起来，利用条件概率公式，这个观测值出现的概率就是
因此我们可以将样本整体的概率和似然函数利用 , , 表示出来，通过对似然函数求导，令其关于 的偏导数等于0，我们可以求出三个参数的值。
这个思路听上去十分合理，我们可以顺着这个思路进行数学推导，看看可以得到什么样的结果。首先我们计算样本的概率:
对应的似然函数为
其中 关于 的条件分布为
的分布为
因此我们可以得到
至此，我们成功地得到了似然函数。然而观察可以发现，这个函数是由100项对数函数相加组成，每个对数函数内部包含一个求和，想通过求导并解出导数的零点几乎是不可能的。当然我们可以通过梯度下降来极小化这个函数，借助深度学习库的自动微分系统在实现上也非常容易。但是这种做法过于简单粗暴，有没有办法来优雅地解决这个问题呢？在继续讨论之前，我们先将这类问题进行一般化表述：
我们观测到随机变量 产生的m个相互独立的样本 , 的分布由联合分布 决定， 是缺失数据或无法在实验中被直接观测到，称为 隐变量 ，我们想要从样本中估计出模型参数 的值。在接下来的讨论中，我们假定 的取值是离散的，于是可以得到似然函数如下:
接下来，我们就探讨一下，如何利用EM算法解决这个问题。
这一部分的数学推导，主要参考了吴恩达CS229n的笔记，并且根据个人的思考和理解，尽力对公式的每一步进行详细的解释。我们先简单地介绍一下琴生不等式。
琴生不等式有多种形式，下面给出其离散形式的表述和概率论中的表述:
1.若 为严格凹函数， 为定义域内的n个点， 是n个正实数，且满足 , 则下述不等式成立:
当且仅当 时，不等式取等号。
2.若 为严格凹函数， 为实值随机变量，且期望存在，则下述不等式成立:
当且仅当 ，即 为常数时，不等式取等号。
注： 这里将函数上方为凹集的函数称为凹函数， 例如 函数就是凹函数。
相信大家对琴生不等式都十分熟悉，因此这里就不做过多的说明。接下来，我们将琴生不等式应用到我们的问题中。
回到我们之前的问题上， 我们想要极大化下面这个函数:
但是我们无法对这个函数直接求导，因此我们借助琴生不等式，对这个函数进行变换。为了让过程看上去简洁，下面只对求和中的第 项进行计算。
令 满足 ，且 ，则根据琴生不等式，可以得到：
当且仅当 为常数时，上述不等式取等号。也就是说，对于任意 ， 是一个与 无关的量。设对于任意 ，我们可以得到：
因此当 时，不等式 取等号，容易验证此时 , 与 无关。将 综合一下，我们可以得到以下结论:
到这里为止，我们已经拥有了推导出EM算法的全部数学基础，基于 我们可以构建出E步和M步。上面的数学推导虽然看上去略为复杂，但实际上只用到了三个知识点：
1.琴生不等式:
2.条件概率:
3.联合分布求和等于边缘分布:
对上面的数学推导有疑问的同学，可以结合上面这三点，再将整个推导过程耐心地看一遍。
大部分关于EM算法的资料，只是在数学形式上引入了 函数，即 ，以满足琴生不等式的使用条件，却没有过多地解释 函数本身。这导致了很多人完全看懂了算法的推导，却还是不理解这些数学公式究竟在做什么，甚至不明白EM算法为什么叫做EM算法。所以在给出E步和M步之前，我想先谈一谈 函数。
我们回顾一下 函数所满足的条件（暂时不考虑琴生不等式取等号的限制），
在 所有可能的取值处有定义。可以看出， 是 的样本空间上任意的一个概率分布。因此，我们可以对不等式 进行改写。首先我们可以将含有 的求和写成期望的形式:
这里 指的是在概率分布 下，求随机变量 和 的期望。有同学会问，为什么我们平时求期望的时候只要写 ，并没有指明是在哪个概率分布下的期望。这是因为一般情况下，我们都清楚地知道随机变量 所服从的分布 ，并且默认在分布 下求期望。
举个例子，我手上有一个硬币，抛了10次，问抛出正面次数的期望。这种情况下，大部分人会默认硬币是均匀的，也就是说抛出正面的次数 服从二项分布 ，期望 。这时有人提出了质疑，他说我认为你这个硬币有问题，抛出正面的概率只有0.3，那么在他眼里， 期望 。
回到正题，我们利用等式 改写不等式 ，可以得到:
这正是琴生不等式在概率论中的形式。我们可以将不等式倒过来理解：
首先，假定随机变量 服从概率分布 ， 是 的样本空间上的任意一个概率分布。这里 可以是一组定值，也可以是关于参数 的函数。
显然，当我们取不同的 时，随机变量 的期望也会随之改变。需要注意的是，由于 与 相关，所以这里的期望不是一个数值，而是关于 的函数。
当我们令 为 的后验分布 时，上面的期望最大。这里有两点需要注意，1. 后验分布 也是一个关于参数 的函数。2. 由于期望是关于 的函数，所以这里的最大指的并非是最大值，而是最大的函数。
若对于每一个 ，我们都令 为 的后验分布 ，则上述期望之和等于我们要极大化的似然函数，即
通过上述分析，我们为寻找似然函数的极大值点 提供了一个思路。我们不去极大化似然函数本身，而是去极大化 。至于如何将这个思路实际应用，就要利用到EM算法中的E-step和M-step。
这一节中，我们先给出E-step和M-step的数学形式，随后在结合抛硬币的例子来解释这两步究竟在做什么。下面进入算法的流程，首先我们任意初始化 ，按下述过程进行迭代直至收敛：
在第 次迭代中，
(E-step)对于每个 ，令
(M-step)更新 的估计值，令
EM算法从任意一点 出发，依次利用E-step优化 ，M-step优化 ，重复上述过程从而逐渐逼近极大值点。而这个过程究竟是怎样的呢，就让我们一步步地揭开EM算法的面纱。
假设我们现在随机初始化了 ，进入第一轮迭代：
(E-step)
由于我们已经假定模型参数为 ，所以此时 不再是与 有关的函数，而是由一组常数构成的概率分布。结合抛硬币的例子来看，这一步是在我们已知模型参数 的基础上(虽然这是我们瞎猜的)，去推测每一次的观测值是由哪个硬币产生的，或者说我们对每一次观测值做一个软分类。比如我们根据初始化的参数，计算出 ， 。可以解释为第 个观测值有20%的概率来自于硬币B，80%的概率来自于硬币C；或者说硬币A抛出了0.2个正面，0.8个反面。
(M-step)
考虑到 是一组常数，我们可以舍弃常数项，进一步简化上面这个要极大化的函数
由于 不再与 相关，因此上面的函数变成了对数函数求和的形式，这个函数通常来说是容易求导的，令导数等于0，我们可以求出新的参数 。我们仍旧以抛硬币为例进行解释，
令 , 可以得到，
这三个参数的解释是显而易见的。我们在E-step中对每个观测值进行了软分类， 可以看成是硬币A抛出正面的次数，所以 是 的极大似然估计； 是我们抛硬币B的次数， 是硬币B抛出正面的次数，所以 是 的极大似然估计；对于 我们有相同的解释。
我们将这个结果与抛硬币1中极大似然估计的结果相比较可以发现，之前结果中的指示函数 变成了这里的 ，在指示函数下，某个观测值要么来自于硬币B，要么来自于硬币C，因此也称为硬分类。而在 函数下，某个观测值可以一部分来自于硬币B，一部分来自于硬币C，因此也称作软分类。
将上述两步综合起来，EM算法可以总结如下：我们首先初始化模型的参数，我们基于这个参数对每一个隐变量进行分类，此时相当于我们观测到了隐变量。有了隐变量的观测值之后，原来含有隐变量的模型变成了不含隐变量的模型，因此我们可以直接使用极大似然估计来更新模型的参数，再基于新的参数开始新一轮的迭代，直到参数收敛。接来下我们就讨论为什么参数一定会收敛。
前面写了太多的公式，但是这一部分我不打算给出收敛性的数学推导。其实数学上证明EM算法的收敛性很容易，只需要证明每一轮迭代之后，参数的似然函数递增，即
Ⅳ 大数据经典算法解析（5）一EM算法
姓名：崔升 学号：14020120005
【嵌牛导读】：
EM作为一种经典的处理大数据的算法，是我们在学习互联网大数据时不得不去了解的一种常用算法
【嵌牛鼻子】：经典大数据算法之EM简单介绍
【嵌牛提问】：EM是一种怎么的算法，其如何去观测其中隐变量的？
【嵌牛正文】：
1. 极大似然
极大似然（Maximum Likelihood）估计为用于已知模型的参数估计的统计学方法。比如，我们想了解抛硬币是正面（head）的概率分布θθ；那么可以通过最大似然估计方法求得。假如我们抛硬币1010次，其中88次正面、22次反面；极大似然估计参数θθ值：
θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2
其中，l(θ)l(θ)为观测变量序列的似然函数（likelihood function of the observation sequence）。对l(θ)l(θ)求偏导
∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8
因为似然函数l(θ)l(θ)不是凹函数（concave），求解极大值困难。一般地，使用与之具有相同单调性的log-likelihood，如图所示
凹函数（concave）与凸函数（convex）的定义如图所示：
从图中可以看出，凹函数“容易”求解极大值，凸函数“容易”求解极小值。
2. EM算法
EM算法（Expectation Maximization）是在含有隐变量（latent variable）的模型下计算最大似然的一种算法。所谓隐变量，是指我们没有办法观测到的变量。比如，有两枚硬币A、B，每一次随机取一枚进行抛掷，我们只能观测到硬币的正面与反面，而不能观测到每一次取的硬币是否为A；则称每一次的选择抛掷硬币为隐变量。
用Y表示观测数据，Z表示隐变量；Y和Z连在一起称为完全数据( complete-data )，观测数据Y又称为不完全数据(incomplete-data)。观测数据的似然函数：
P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)
求模型参数的极大似然估计：
θ^=argmaxθlogP(Y|θ)θ^=argmaxθlogP(Y|θ)
因为含有隐变量，此问题无法求解。因此，Dempster等人提出EM算法用于迭代求解近似解。EM算法比较简单，分为两个步骤：
E步（E-step），以当前参数θ(i)θ(i)计算ZZ的期望值
Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]
M步（M-step），求使Q(θ,θ(i))Q(θ,θ(i))极大化的θθ，确定第i+1i+1次迭代的参数的估计值θ(i+1)θ(i+1)
θ(i+1)=argmaxθQ(θ,θ(i))θ(i+1)=argmaxθQ(θ,θ(i))
如此迭代直至算法收敛。关于算法的推导及收敛性证明，可参看李航的《统计学习方法》及Andrew Ng的《CS229 Lecture notes》。 这里 有一些极大似然以及EM算法的生动例子。
3. 实例
[2]中给出极大似然与EM算法的实例。如图所示，有两枚硬币A、B，每一个实验随机取一枚抛掷10次，共5个实验，我们 可以 观测到每一次所取的硬币，估计参数A、B为正面的概率θ=(θA,θB)θ=(θA,θB)，根据极大似然估计求解
如果我们 不能 观测到每一次所取的硬币，只能用EM算法估计模型参数，算法流程如图所示：
隐变量ZZ为每次实验中选择A或B的概率，则第一个实验选择A的概率为
P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45
按照上面的计算方法可依次求出隐变量ZZ，然后计算极大化的θ(i)θ(i)。经过10次迭代，最终收敛。
4. 参考资料
[1] 李航，《统计学习方法》.
[2] Chuong B Do & Serafim Batzoglou, What is the expectation maximization algorithm?
[3] Pieter Abbeel, Maximum Likelihood (ML), Expectation Maximization (EM) .
[4] Rudan Chen, 【机器学习算法系列之一】EM算法实例分析 .
Ⅵ EM算法和混合高斯模型（一）
EM（Expectation Maximization）算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计，或极大后验估计。EM算法的每次迭代由两步组成：E步，求期望（expectation）；M步，求极大值，因而被称为期望极大算法，简称EM算法。
本文从EM算法的引入说起，简单介绍EM算法的推导过程，以及其在高斯混合模型中的应用。更多的关于EM算法的推导细节，可参见 人人都懂EM算法 。
假设我们需要调查我们学校学生的身高分布。我们先假设学校所有学生的身高服从正态分布 。( 注意：极大似然估计的前提一定是要假设数据总体的分布，如果不知道数据分布，是无法使用极大似然估计的 )，这个分布的均值μ和标准差为σ 未知，如果我们估计出这两个参数，那我们就得到了最终的结果。那么怎样估计这两个参数呢？
学校的学生这么多，我们不可能挨个统计吧？这时候我们需要用到概率统计的思想，也就是抽样，根据样本估算总体。假设我们随机抽到了 200 个人（也就是 200 个身高的样本数据，为了方便表示，下面“人”的意思就是对应的身高）。然后统计抽样这 200 个人的身高。根据这 200 个人的身高估计均值 μ和方差σ 。例子来自 人人都懂EM算法 。
现在我们假设这200个人的身高服从一个正态分布N(μ，σ)，因此可以直接使用极大似然估计方法估计出这个分布的参数μ和σ。
但是，这200个人的身高真的是服从同一个正态分布吗？实际情况并不是这样的，男生和女生分别服从两种不同的正态分布，即男生 女生各服从一个正态分布 ，( 注意：EM算法和极大似然估计的前提是一样的，都要假设数据总体的分布，如果不知道数据分布，是无法使用EM算法的 )，而且假设我们现在只有身高数据，丢失了性别数据，那么该怎样评估学生的身高分布呢？
这个时候，对于每一个样本或者你抽取到的人，就有两个问题需要估计了，一是这个人是男的还是女的，二是男生和女生对应的身高的正态分布的参数是多少。这两个问题是相互依赖的：
但是现在我们既不知道每个学生是男生还是女生，也不知道男生和女生的身高分布。这就成了一个先有鸡还是先有蛋的问题了。鸡说，没有我，谁把你生出来的啊。蛋不服，说，没有我，你从哪蹦出来啊。为了解决这个你依赖我，我依赖你的循环依赖问题，总得有一方要先打破僵局，不管了，我先随便整一个值出来，看你怎么变，然后我再根据你的变化调整我的变化，然后如此迭代着不断互相推导，最终就会收敛到一个解（草原上的狼和羊，相生相克）。这就是EM算法的基本思想了。
EM的意思是“Expectation Maximization”，具体方法为：
上面的学生属于男生还是女生我们称之为隐含参数，女生和男生的身高分布参数称为模型参数。
EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐含参数是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。我们基于当前得到的模型参数，继续猜测隐含参数（EM算法的 E 步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。
在开始介绍EM算法之前，让我们先来了解一个重要的定理——Jensen不等式。
如下图，如果函数f(x)是凸函数，x是随机变量，有 0.5 的概率是 a，有 0.5 的概率是 b， x的期望值就是 a 和 b 的中值了，那么：
对于m个相互独立的样本:
假如没有隐含变量z， 我们仅需要找到合适的θ极大化对数似然函数即可:
现在我们给定一个θ值（初始化θ），那么logL(θ)的值就取决于Q i (z)和P(x (i) ,z (i) )。我们可以通过调整这两个概率使下届逼近logL(θ)的真实值，当不等式变为等式时，说明我们调整后的下届就等于logL(θ)了。由Jeson不等式可知，等式成立的条件是随机变量是常数，则有：
如果Q i (z (i) ) = P(z (i) |x (i) , θ)，则（2）式使我们包含隐藏数据的对数似然函数的一个下届。如果我们能极大化这个下届，则也在尝试极大化我们的对数似然函数。即我们需要极大化下式：
由于对logaf(x)求导的结果与f(x)的系数无关（(ln(ax))'= (lna + lnx)'=1/x），因此对θ求极大似然时，可以去掉式中的常数部分Q i (z (i) )：
现在，让我们来总结一下EM算法的流程。
输入：观察数据x = (x (1) , x (2) , ... , x (m) ), 联合分布P(x, z|θ)，条件分布P(z|x,θ)，极大迭代次数J。
（1）随机初始化模型参数θ值；
（2）迭代求解各个分布模型的参数以及各个模型的概率：
for j from 1 to J:
输出：模型参数θ
图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。
这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步：固定 θ，优化Q；M步：固定 Q，优化 θ；交替将极值推向极大。
E步 ：初始化θ A =0.6和θ B =0.5（θ A 和θ B 分别表示两个硬币出现正面的概率），计算每次掷硬币选择A和B的概率，例如第一个实验中选择A的概率为：
M步 ：求出似然函数下届Q(θ，θ i ), y i 代表第j次试验正面朝上的个数，μ j 代表第j次试验选择硬币A的概率，1-μ j 代表第j次试验选择硬币B的概率。
参考：
人人都懂EM算法
《统计学习方法》. 李航
Ⅶ 从马尔可夫模型到隐马尔可夫模型
马尔可夫模型个人认为这个概念应该是从 随机过程 里面提出来的，由马尔可夫过程过来的概念。实际上掌握了随机过程里面对马尔可夫过程的特殊情况：离散参数离散状态的马尔可夫链的数学运算的话。就能够很好解决马尔可夫模型上面的计算问题，包括隐马尔科夫模型。讲马尔可夫模型以及过程重点在于其满足的性质-马尔可夫性。
随机过程：
现实中时常出现，某个事物满足一定的随机分布，但是其随机分布会随着时间的变化而变化。我们假设其在时刻 符合随机分布 并且用随机变量 来表示。假设 。但是在时间 的时候就符合随机分布 并且用随机变量 来表示。假设 。也就是说某个事物的某个特征会随着时间的变化其对应的分布也会发生变化。这样一个总体的过程，称之为 随机过程。
具体例子：
灯泡寿命问题，灯泡其实在每个时间点上都有一定的可能性会损坏，在这个时间点上损坏的可能性符合一个具体的正态分布（其 是确定的），而随着时间的久远，灯泡损坏的可能性就变大了。所以在之后的某个时间点上灯泡损坏的可能性可能就符合另外一个具体的正态分布（其 就和先前不一样了，会有变坏的趋势）。灯泡损坏在传统的概率论中也是一个经典例子，可能传统的概率论会认为灯泡的寿命长短符合一个随机分布，并且用一个随机变量来表示，我们研究这个分布的特征。这里和传统的概率论中不一样，可以发现的是，引入了随机过程，可以对随机现象更加深入彻底地描述和研究。
定义随机过程中的一些量。
参数：也就是上述的时间，如果是和时间有关，往往叫做时间序列。但是很多的现象研究不是和时间相关的。
状态：也就是上述的随着时间变化的随机变量。
马尔可夫过程：满足马尔科夫性的随机过程。
以后再解释
马尔可夫性：
马尔可夫链：
马尔可夫模型和上述的关系。
具体讲一下 隐马尔可夫模型。
和普通的马尔可夫不一样，马尔可夫模型是可以确定状态序列的。也就是说序列上的每个项的分布是怎么样的是已知的。而隐马尔可夫模型是连序列上的每个项的是什么分布都不能够知道，都是随机的。
对于这样的一个随机模型。
经常要解决三个基本问题：
1). 给定 和 ，求解 。 又叫作 计算问题。
2). 给定 和 ，求解一个状态转换序列 ，使得最优可能产生上面的序列。又叫做估计问题。
3). 在模型参数（A或者B）未知或者参数不准确的情况下，由 来调整参数。又叫做训练问题。
状态一定是按着产生了部分观察序列来的。考虑前缀。 表示处理到了n,观察序列到n为止都是答案的概率。但是不好转移，转移的时候要枚举前后隐藏状态，考虑把隐藏状态也表示出来。 表示处理到了n，并且第n个状态为j的概率。
范围：
结果：
初始化：
转移：
知道 和 ，求Q，状态序列，使得产生 的可能性最大。
定义：
这个函数的含义是：
模型在时刻t处于状态i，观察到 的最佳状态转换序列的概率。
从而有了转移方程：
而 就是
因此 的转移过程构成了一个图，而Q就是上面的最优路径。
利用 观察数据进行对模型参数 或者 或者 进行预测和修正，训练问题，又可以叫做预测问题。
并且这个问题其实是带有隐变量的最大似乎估计，也就是EM算法。
直接讲EM,用数学角度来引入 或者 用递归式来求解含有隐变量的参数估计 都是可以的，后者会比较清楚。
但是课上老师给出了另外一种比较好的解释：
考虑第三个问题，实际上应该分两种情况。
1：带指导的参数学习。
给出的数据是这样的：
状态/观察数据。
硬币中的例子就是
H/1 H/1 T/1 T/2 H/3 T/3 T/2 H/1 T/2 H/3 H/3 H/1
其实当拥有了数据 状态/观察数据 是可以直接对参数进行估计的。
假设是齐次的（一般也是齐次的，概率只和状态有关，和时间关系不大，放在词句中就是词语所在的句子的部位关系不是很大，而是上下文内容关系比较大。），
考虑aij 指的是在状态i和状态j的转移概率。
可以直接对上面2个2个统计进行参数估计。
考虑bi(o_j)也就是状态为i输出为o_j的。
一个一个枚举来即可。
考虑pi_i。也就是初始状态。
一个一个枚举状态即可。
带有指导的是有缺点的：
数据上不可行，状态这样的数据其实都是人工标注的。
数据量要求比较大。
但是在NLP中这个方法是很重要的。因为效果比较好。
2：不带指导的参数学习
数据上只给出了 观察序列，没有状态序列。
实际上1中就出了答案。没有状态序列，我们就枚举状态序列。
比如上述。如果观察出来了
1 2 2
那么我们就考虑以下
1 2 2
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT
所有情况。
所以就产生了
H/1 H/2 H/2
H/1 H/2 T/2
....
然后分组进行统计参数估计即可。
但是这里有两个问题：
1：状态太多了。N^T。
2：给每个状态的权重是一样的。不是很科学。（实际上还行，如果使用熵最大原理。）
那么怎么办？解决2考虑给不同状态加权重，那么要有一个先验的的知识：
咱们先给出先验的 模型参数。
那么就可以计算P(Q|O,人)P（Q,O|人）这样的东西了。
明显可以用P(Q|O,人)作为一个路径序列的权重。
但是这样计算的时候，路径序列很长。并且转移路径还是N^T条。
不可行。
避开对路径的考虑。考虑参数abt最多只有涉及两个时间点的。
我们如果只关注两个时间点之间的状态。那么就可以变成二维的。
使Q不是一个路径的。而是只是两个时间点之间的状态。
q_t = i q_t+1 = j 。把这个概率计算出来的话。就能直接对aij这样的进行估计了。
（实际上只是换了一种计数方式，就减少了问题规模，因为咱们关注的也只是路径上两个点两个点之间的。）
由此引出Baum_Welch算法：
定义以下：
这样就能对参数们进行评估了。有以下：
这样只要挑一个满足条件的初始值，然后迭代求解即可。