前言
EM算法，在学术界的重视程度，要高于在工业界。
它是一个做数据优化的方法。
比如现在如果遇到问题，如果想对问题做优化，大家或许只会用最大似然估计(MLE)写目标函数，当然也可以换成最大熵模型的目标函数。
但是如果遇到参数的个数比目标函数的值还要多的时候，没有办法进行求解，即数据中存在隐变量，即存在不可观测变量，还想对参数求极值，但有些隐变量y不知道，只知道x，即需要求解(x, y, θ)中的参数θ，当然顺便想求解隐变量y本身。
这种时候，可以尝试期望最大化算法，即EM算法
主要内容
该算法的提出时间为1977年。
EM算法可以解决很多问题，比如估计身高。
此节课的内容分两部分：
第一部分：使用欧拉(Euler)式的方法来讨论
可能并不是对的，但很直观，了解即可。
第二部分：使用高斯(Gauss)式的方法来讨论。
非常严格，过程一步一步，一环扣一环。但是需要掌握
名词解释
EM算法本身是一个求解带隐变量y，以及含有模型参数θ的模型，当然，往往是要求取给定的样本x，即P(x|y, θ)
但是落地的时候，说的模型是假设数据服从混合高斯模型(GMM)，利用EM算法，求解混合高斯模型的参数。
亦即有两个或多个高斯模型：
如均值是μ1, 方差是σ12，即α1N(μ1, σ12)
此外还有：
α2N(μ2, σ22)
...
αkN(μk, σk2)
即k个高斯模型。
将这些高斯模型混在一起，形成高斯混合模型，即GMM。
其实在讲解K均值（K-Means）时，已经谈到过，即：
方差：σ12 = σ22 = ... = σk2，并且它们都是对角阵，其实就可以使用K均值算法，对每个样本做簇的标记。
但是如果方差不相等的话，推广为一般的高斯分布，那么K均值可能并不适用
那么此时可以尝试EM算法。
注意： EM，即期望最大化，是需要解释说明的算法(Algorithm)；GMM，高斯混合模型，是需要落地的模型(Model)
课堂问答
问：EM算法主要运用在哪一块？是自然语言处理么？
答：不见得只是用于自然语言处理。有可能会用在哪呢？比如如果想用于主题模型，比如有一些文档，每个文档有若干个词，这些都是已知的。我们希望了解每个文档有哪些topic，即这些Topic是什么？(Topic Model)，拿天龙八部为例，比如“契丹”，即主题或许是政治；“王语嫣”，即主题或许偏向爱情。
即可以得到统计：
文档：天龙八部；武侠主题比重0.8，爱情比重0.15，历史、政治。。。这些主题的比重各是多少？
这相当于主题分布，有多少个主题就是多少个类别。
然后每一个主题，比如：P(大理|武侠)，即武侠这个主题当中，大理出现的比例是多少？假定有10万个词，在下图中的p(Wj|Zk)，即10万点分布。
下面的模型的意义在于：
通过文档->得到N个主题->主题对应N个词，任何节点D，任何节点Z，任何节点W都是随机变量，并且给定文档时候的主题，其概率是多项分布，给定文档的词也是多项分布。
当给定多篇文档的时候，比如M篇文档，文档本身我们知道，词本身我们也知道，但是每一个文档包含的主题是什么，每一个主题所对应的词分布是什么，是未知的，但是通过文档看到词的概率是已知的。
因为文档是已给定的，我们只需要通过频率去统计一下。我们认为频率的极限是概率，总是可以去解释的。
主要问题在于我们不知道隐变量Z，然后我们现在有的是文档和词语，将文档与词语的配对，记为样本数据，即X向量：(D, W)。
P(z|d)与P(w|z)，我们认为目的是求参数θ，Z本身是隐变量主题模型，这其实就是：P(θ, Z|X)，即X有了，但是隐变量Z不清楚，我们的参数θ想估计一个这个问题。
EM算法即可以解决这种P(θ, Z|X)类似的问题。
这个并不是高斯混合模型（GMM），这其实是两个多项分布。
虽然EM算法落地可以通过高斯混合模型来讲，但是本质来说，高斯混合模型与EM算法并没有什么关系。
邹博老师举的例子：比如小龙女与王语嫣本身没关系，但是演过小龙女的演员，或许也可以演王语嫣，就感觉这两个人很像。
问：EM算法能用在金融领域么？
答：不清楚，至少邹博目前在金融领域没有用到EM算法。
问：K-Means仅适用于各个变量呈正态分布的情况，而EM算法对数据的要求没有要求是么？
答：EM算法对数据分布要求是先有先验判定，比如我们将数据建模为多个多项分布或者高斯混合分布，即人工先建模，然后推公式，再迭代。
而K-Means算法必然是服从混合高斯分布的。
问：K-Means的数据不一定需要呈现正态分布？
答：从理论上说，K-Means算法需要满足混合高斯分布，但不等同于高斯分布。如果不满足的话，效果不一定非常差，但是不够符合理论。
问：EM算法解决的事情有隐藏的东西，需要求参数也要求中间隐藏东西？
答：是的。
问：貌似θ才是隐变量，Z是观测值？
答：Z是隐变量啊，即主题模型，因为不看文档，只根据词汇，完全不知道主题是什么。所以Z是观测不到的隐变量。
使用欧拉(Euler)式的方法来讨论
如图，K-Means算法无法给出某个样本属于该簇的后验概率。
如果需要计算后验概率，就需要使用EM算法。
最大似然估计
MLE(Maximum likelihood estimation)即最大似然估计的缩写：
对似然概率取对数，化简：
对μ与σ分别求偏导，并且偏导等于0，其中μ为均值，σ为伪方差（因为方差应该是除以n-1）。通过样本得到均值与方差，就能得到估计值，这就是最大似然估计的最终结论：
设定一个场景，解释EM算法：
延伸，用于解释问题是什么：
接上图，Σi有可能是数字，也可能是nxn的矩阵，μi有可能是数字，也可能是n维的向量。
关键在于样本是一元还是多元的。
举例：
如果设定有数据身高=h，体重=w，腰围=r，则构成(h, w, r)，任何一个样本给定了3x3维度的正定对称的方阵(如身高与身高的方差，身高与体重的方差，身高与腰围的方差。。。)：
Σ =
(σhh2 σhw2 σhr2
σwh2 σww2 σwr2
σrh2 σrw2 σrr2)
现在估计参数π1π2...πk是什么，估计μ以及Σ是什么
课堂问答
问：神经网络能不能做无监督学习？
答：我们现在其实是利用输出的值去做，但是可以做自编码。如果假定没有y，输入是x，输出其实还是x。我们来调整中间网络权值，得到自编码，最后把x扔了。这样倒数第二列是x的特征，这个时候我们可以认为实现了无监督学习。但是是用有监督的方式，做无监督的事。
问：做最大似然估计是不是要求目标函数必须是凸函数？
答：不要求。比如，K-Means算法其实给定目标函数也是最大似然估计所给的，但并不是凸函数。因为K-Means对初值敏感，有多个极值，所以不会是凸函数。
只是我们与大家所见到的函数，大多是指数族分布，如果有极值，只有一个，所以感觉是凸函数。
问：μ与Σ是可观测变量还是隐变量？π是隐变量么？
答：这里μ，Σ与π都是我们想去求解的未知的值，如果一定要区分，比如男性，女性的性别是隐变量，μi与π都是参数θ。
求解的过程：
首先建立目标函数
N(xi|μk, Σk)，这个是一个给定了某个均值，方差之后，第i个样本的概率密度。
本质上是这个(一元的)，只是 把μ替换为μk，把σ替换为 σk
只要μk与σk是已知的，那么给定一个样本xi的时候，概率密度的值是可以计算的。
此时如果有先验概率πk，则下述式子是可以计算出来的（即第i个样本发生的概率）：
课堂问答
问：隐变量有多少如何确定？
答：隐变量有多少，与K均值取几个类似，不容易判定。至于有多少，需要根据样本的特定，进行尝试，即隐变量其实是超参数。
问：刚刚的对数似然函数不用加负号么？
答：如果加负号就变成了取最小值，即变成了损失函数。不加负号是取最大值。通常做的时候，会取负对数似然，否则就变成取最大值。
邹博首先通过欧拉的方式来讨论：
1. Euler：
下面要做两件事情：
PPT如下：
举个例子：
假定得到x1, x2, x3, ..., xm，共m个样本。
然后希望得到各个样本的性别是男孩还是女孩：sex: boy/girl，
即认为boy服从高斯分布：N(μ1, σ1)，女孩服从高斯分布：N(μ2, σ2)。
然后各自与π1，π2相乘后，再相加，所得到的结果：
π1·N(μ1, σ1)
+π2·N(μ2, σ2)
其目的就是求得其中的π1，μ1, σ1以及π2，μ2, σ2
第一步：先验知识（蒙或者猜）
比如均值μ1 = 1.75；方差σ1 = 100
均值μ2 = 1.62；方差σ2 = 80
这里是随便说的，没有什么道理。。。
π1 = π2 = 0.5
即，假定男女各半
老师的相关草稿如下：
继续往下计算结果。
比如x1的值是2.26，既然已经通过先验得到假定均值与方差，那么就可以求概率密度：
如图，等式右侧可得到一个为常数的概率密度，假定是0.01，然后乘以π1 ，概率密度的意思：如果这个人是男孩的概率密度是几；那么π1=0.5的含义是：在m个人随机挑出一个人，是男孩的概率。
下面的草稿，是将μ与σ的参数1替换为参数2的值，然后得到另外一个概率：
现在对2.26这个人算出是男孩还是女孩的概率密度，做一个规划，然后将第一次计算的值，替换为规划计算之后的值：
即得到：身高为2.26的人，在先验参数下，是男孩的概率是71.42%，是女孩的概率是28.57%.
这是第一个样本，即身高为2.26的情况。
同理可以选更多样本的情况，如
x2: 1.70
x3: 1.58
然后，将每个样本，都按照第一个样本的形式算一遍，分别得到各个样本在先验概率情况下，是男孩或女孩的概率：
然后可以往下计算新的一种情况：
将2.26 x 0.71, 2.26 x 0.29; 1.70 x 0.51, 1.70 x 0.49....，得到下面的草图：
通过概率来解释，即，2.26米的人，71%的概率是男的，29%的概率是女的。
男孩服从N(μ1, σ1)的高斯分布，如果是高斯分布，均值与方差能否按照下述公式计算？
把刚刚计算的结论给代进去，即将右侧的计算结果给代进去：
μ1的估计值 = (1.6046 + 0.87 + 0.474 + 1.287) / (0.71 + 0.51 + 0.3 + ... + 0.65)
σ12的估计值可以将μ1的估计值代入公式求得。
这样，男孩的μ1的估计值与σ12的估计值就有了。
同理，可以求得女孩的μ2的估计值与σ22的估计值。
同时μ1 / m即可得到所谓的π1的估计值
同理，μ2 / m也可以得到所谓的π2的估计值
回到刚刚随便猜的地方:
再回到计算得来的估计值，即得到了一定的样本信息：
同时，还有先验的一些情况，可能没有收敛，但是没关系。
可以把计算出来的各个估计值，再重新做计算。
即重新算男孩，女孩的均值与方差，以及参数π。
如此重复计算几十次，相信足够收敛了。
收敛之后的参数们，就是我们要求的结论。
这个过程不难，可能并不严格，而这一过程，就是欧拉式的方法
下半段，再利用严格的高斯的解法，解释这样做的结论，为什么是对的。
课堂问答
问：可以理解成身高 * 人数，人数是总人数 * 是男性的概率。然后把总人数除掉归一化？
答： 是的，不过我们是用身高 * 是男孩或女孩的概率，比如男孩概率是0.65，女孩概率是0.35，
问： 第一次的先验参数怎么给出？是随便给么？
答：我们根据先验经验给的
问：与K-Means一样，随便给个初值，然后不断收敛就行？
答：是的。
问：后面得出的结果会和给出的先验参数有很大关系吧？
答：可能有关系，后半段会进行解释。
问：高斯混合聚类的过程就是这样，只是多了一步，最后把样本归类为概率最大的那一类？
答：是的。
问：随便给一个初值会不会影响收敛？这个函数是局部收敛还是全局收敛？
答：是局部收敛的，它可能有多个极值。
问：随便给的话，要是我全给一样的值，那最后算出来的岂不是还是一样的？
答：这样的话，就真的分不开了。
问：这里的隐变量是哪一个？
答：π或者说男孩与女孩的概率是隐变量。
问：这应该算一个无监督模型吧?
答：是的。
问：第一次的参数是随机估计的，计算1轮后各个参数向哪个方向调整呢？需要梯度下降求偏导么？
答：不需要。刚才那个方法就是相关的做法。EM本身自带梯度下降。
问：如果不同分布，例如泊松分布，都会收敛么？
答：可以这么做。假定细胞培养皿，存在青霉素，红霉素，以及其他毒素，每个毒素的个数都服从泊松分布，最终数一数细菌个数。它应该符合混合泊松分布。
问：会不会最后男女弄反了？
答：可能会的。不过无监督模型目的分簇，至于簇是什么，再进行给定就可以了。
问：什么是高斯混合模型？
答：刚刚的例子，比如男孩符合高斯分布，女孩符合高斯分布，将其混在一起，就可以了。
问：对初值还是有限制的啊？
答：当然，不能随便给哈，至少符合常识~~~
问：为什么身高乘以概率？
答：身高乘以概率，目的是提取纯男孩或纯女孩的部分
问：高斯模型相交的越多越难分吧？
答：是的
问：为什么均值这个参数是求的概率的平均值来迭代呢？
答：因为我们刚才所说的符合高斯分布，就可以用这个公式求均值：
2018-10-10 20_48_21-【邹博_chinahadoop】机器学习升级版VII（七）.png
严格的推导过程：使用高斯(Gauss)式的方法来讨论
开始来想目标函数的问题
如下图：p(x|θ)就是目标函数，最大似然概率，
其局部极值对应的θ，是需要寻找的最优值。
l(θ) >= r(θ)，而r(θ)是l(θ)的下界。
而r(θ)求极值是可以做的。
通过定义多个可以计算的r(θ)函数，逐步获得θ1，直到获取l(θ)的局部最大值θ，则此时的θ为局部最优解。
以上推导，为EM算法的整体思路。
课堂问答
问：这种算法是按梯度上升么？
答：不见得是按梯度上升。如用某种方式求得蓝色函数的极大值，方式为让期望值取最大。这个就是EM的意思。
问：一般只能收到局部最优么？
答：举例，我们生活在这个世界，一直在做局部最优。
问：学机器学习的人应该越来越多了，怎么会越来越缺了？
答：因为应用机器学习的人越来越多了。
问：r函数是什么样的？
答：r函数是一会要说的重点。
问：如何没有服从分布的假设，也就没有了参数，那么假设数据分布就是EM算法的前提么？
答：是的。
问：什么叫吉布斯采样？
答：在说到LDA的时候会谈到这个。
Jensen不等式
z是一个隐变量，
如x1, x2, ..., xi..., xm共有m个样本，
x1的隐变量记为z1，x2的隐变量记为z2，xi的隐变量记为zi..., xm的隐变量记为zm
这样的话，任何一个xi有隐变量zi，zi的分布，选择某一个分布，记作Qi(zi)，即第i个样本它的分布。
l(θ)为最大似然函数，将样本代入，公式推断部分的part1 >= part2, 其中part1为对数函数，为红线弧线，part2为线段部分。
课堂问答
问：假设数据分布然后求参数，感觉EM算法的思路和解决的问题似乎和MCMC有点相似？
答：它们相似程度并不大，EM算法是指样本服从分布并求解决，是基于推导的；MCMC（蒙特卡洛马尔科夫采样）采样方式，是关于采样的。
寻找尽量紧的下界
解决什么时候取等号的问题。
P(x, z)/Q(z) 为定值c
即，Q(z) = c * P(x, z)
下面来看，Jensen不等式什么时候取等号：
如图，y1 = y2, 则汇聚为1个点，换句话说p(x, z)/ Q(z) = C即定值，即满足要求。
即Q(z) = C * p(x, z)
假定z是随机变量，
其对应
z: z1, z2, ..., zk
其概率p对应: q1, q2, .. qk
q1+q2+...+qk = 1
则：
Q(z1) = q1 ... Q(zk) = qk
即C * p(x1, z1) + C * p(x2, z2) + ... + C * p(xk, zk) = 1
Q(z) = p(x, z) / Σzp(x, z)
继续推证：
Q(z1) = p(x1, z1) / Σzp(x, z)
Q(z2) = p(x2, z2) / Σzp(x, z)
。。。
Q(zk) = p(xk, zk) / Σzp(x, z)
如此可以确保Q(z1) +Q(z2) + 。。。 + Q(zk) = 1
Σzp(x, y) = p(x)，=> p(x, z)/ p(x) = p(z|x) = Q(z)
即取条件概率Q(z) = p(z|x)，可以使得Jensen不等式的两边取得等号。
Jensen不等式的>=的后面部分其实就是下图红框中函数r(x|θ)：
将两个过程综合起来，即得到EM算法整体框架：
其中θ作为初值，是随机给的，或者根据先验情况，给出的θ，然后x是样本，然后其得到z的条件概率Qi(z(i))，本质上，我们希望Jensen不等式能够取等号。
将下图红框，当做Y，即ΣQQ * Y = EQ(Y)，或者说是对Y在Q的分布上求期望。
进一步换算为：lnEQ(Y) >= EQ(lnY)，但是我们取的Q 如果等于 p(z|x, θ)，能够使得期望取相等，即：
第一步是取期望的过程。
第二步，将Q替换为p(z|x, θ)，即相当于关于θ的函数：γ(θ)，对于这样一个函数就来去想任何一个办法，求取它的最大值：
θ = arg maxθγ(θ)
第二步就是取θ的最大值
然后不停的迭代，即不断求期望与θ最大值的过程
最后，如果z的条件概率收敛了，不再发生变化了，θ也不再发生变化了，隐变量与参数θ就都有了。
下图红框内容，即显示迭代求取E与M的过程，这就是EM算法：
课堂问答
问：θ也是求局部最大么？
答：是的
问：每个样本Xi对应隐变量Z的分布Q都不一样么？所以才记做Qi?
答：是的
从理论公式推导高斯混合模型(GMM):
第一步，求期望值，即求取条件概率的过程：
给定样本，看样本属于哪一个分布的概率
第二步，求最大值：
对均值μ求偏导：
令偏导等于0：
对方差求偏导，令其等于0：
求关于φ的极值：
结论与欧拉式的推论，其实没什么区别的
EM算法与什么分布没什么关系，只要了解EM算法整体过程就可以。
pLSA用法没那么多，但有助于理解EM算法
课堂问答
问：EM算法有哪些具体应用？有Scikit-Learn包么？隐马尔科夫模型的概率是由EM算法计算的么？
答：Scikit-Learn有关于高斯混合模型的包，隐马尔科夫模型，一个方式是可以使用EM算法来算，还有可以直接使用最大似然估计来算。
问：假设的分布必须是相同的么？
答：如果分布不同理论是可以的，但是推导公式会麻烦很多。比如高斯分布于高斯指数分布混合，那么公式就麻烦很多。在应用中，大多都是相同分布。
问：如SVM，Logistic回归等模型参数，可以用EM算法求解么？
答：没必要。
问：也就是参数非常多的时候采用EM？
答：不是，与参数多少没关系。只和有没有隐变量有关系。
