# EM算法

## 1）思路

​ EM算法解决这个的思路是先全部假设出来

​ 想象一下平均分米，先随便分，然后多的给少的划入一些，直到大家都感觉差不多了，那其实真就差不了多少了，不信去称一下，重量几乎差不多的。EM就是这么个思路。

## 2）估计

​ 这个时候，对于每一个样本，就有两个东西需要猜测或者估计：每一个样本属于哪个分布。（是男还是女）、每一个分布对应的参数。（男女分布的均值、方差）

## 3）基本流程

![img](https://img-blog.csdnimg.cn/20190227164401793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nNDI1Nzc2MDI0,size_16,color_FFFFFF,t_70)

> 例：
>
> （a）E初始化参数：先初始化男簇身高的正态分布的参数：如均值=1.7，方差=0.1，女性同样。
>
> （b）E:（有了（a）的参数，就能）计算每一样本更可能属于男生分布或者女生分布了（如男:0.55,女:0.45，于是标记为男）；
>
> （c）M：标为男的有n个样本，现在用这n个样本的数据来重新估计男生身高分布的参数（最大似然估计），女生分布也按照相同的方式估计出来，更新分布。
>
> （d）（c）后，两个分布的参数可能变了，那每个样本的概率又可以从新算了（原来男:0.55,女:0.45更可能属于男的，结果女:0.65,男:0.35更可能是女了），然后重复步骤（1）至（3），直到参数不发生变化收敛为止。
>
> （e）然后我们就神奇的认为，我们学到了这个数据的分布，每个样本的类别标记，并且能拿来预测新的未知样本属于男、女的概率。

## 4）具体的计算推导

​ 基本流程知道后，核心就是怎么更新参数了，这个在任何一个介绍EM算法里面只会给出一个抽象的概念，因为分布有千万种，更新分布的参数只能抽象来讲。

​ 具体来讲会放大下一节高斯混合模型HMM来讲，因为此时分布就是高斯分布，要更新的就是均值和方差

a）问题由来

> 对于m个样本的数据集$$D=(x^{(1)},x^{(2)},...x^{(m)})$$
>
> 如果我们知道m个样本的类型是$$z=(z^{(1)},z^{(2)},...z^{(m)})$$，显然，在假设出分布后（如服从高斯分布），概率论中常见的（对数）极大似然法，就能得到我们分布的参数了:$$\theta = arg \max \limits\_{\theta}\sum\limits\_{i=1}^m lnP(x^{(i)};\theta) = arg \max \limits\_{\theta}\sum\limits\_{i=1}^m ln\sum\limits\_{z^{(i)}}P(x^{(i)})$$
>
> 然而，如果类型z是未知的，这里面的参数用极大似然是求不出的，因此EM出来解决这个问题，转为可以极大似然求解的迭代形式。

b）额外知识

> 先看这个Jensen原理：<https://blog.csdn.net/jiang425776024/article/details/87992127>
>
> Jensen不等式的表述是，如果f(x)是[凸函数](https://blog.csdn.net/jiang425776024/article/details/87607848)，x是随机变量，则不等式成立：$$E(f(x))\ge f(E(x))$$
>
> 如果是凹函数：$$E(f(x))\le f(E(x))$$
>
> E是数学期望，对于离散型随机变量，数学期望是求和，对连续型随机变量则为求定积分。
>
> 如果f(x)是一个严格凹/凸函数，当且仅当x是常数时不等式取等号：$$E(f(x))= f(E(x))$$

c）假设样本xi为类型zi（隐变量）的概率分布为Qi

> 什么意思？就是概率的概率分布，xi属于类别zi的概率的概率分布，显然根据分布，必须有这些条件成立：
>
> $$Q\_i(z\_i)=p(z\_i|x\_i;\theta)$$
>
> $$\sum\_{z}p(z)=1$$
>
> $$p(z) \ge0$$

d）利用b）的知识，和c）的概率的概率分布假设，就能对a）中的极大似然目标做转换了

> 记：$$f(x)=lnx$$
>
> 根据b），因为f(x)=lnx为凹函数，所以：$$E(f(x)) \le f(E(x))$$
>
> **记这里的x就是a)下面ln后面那个，且转换为分布：**
>
> $$x=\sum\_{zi}Q\_i(z\_i) \frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}=E\_{Q\_i(z\_i)}(\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)})$$
>
> （显然： f(x)=lnx中的x，被强行看做是$$\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}$$的期望，Qi为$$\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}$$的概率；因为累加$$Q\_i(z\_i).\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}$$很像是求期望的形式）
>
> 则a)中极大对数似然中的lnx可以写成：
>
> $$
> \begin{aligned}
> \&ln\sum\_{z\_i}Q\_i(z\_i).\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}\\
> &=f(E\_{Q\_i(z\_i)}(\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}))=ln(E\_{Q\_i(z\_i)}(\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}))\\
> &\ge E\_{Q\_i(z\_i)}(f(\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}))=E\_{Q\_i(z\_i)}(l n(\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}))\\
> &=\sum\_{z\_i}Q\_i(z\_i)ln\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}
> \end{aligned}
> $$
>
> 也就是说，a)中的极大似然估计的那个对数似然，可这样转变：
>
> $$
> \begin{aligned}
> &\sum\limits\_{i=1}^m lnP(x^{(i)};\theta) = \sum\limits\_{i=1}^m ln\sum\limits\_{z^{(i)}}P(x^{(i)},z\_i;\theta)\\
> &=\sum\limits\_{i=1}^m ln \sum\_{z\_i}Q\_i(z\_i)\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}\\
> &\ge \sum\limits\_{i=1}^m  \sum\_{z\_i}Q\_i(z\_i)ln\frac{p(x\_i,z\_i;\theta)}{Q\_i(z\_i)}
> \end{aligned}
> $$
>
> 显然，**这个下界函数更容易求极值，**&#x56E0;为对数函数里面已经没有求和项，对参数求导并令导数为0时一般可以得到公式解。

去掉上式中为常数的部分，我们要做到，就是**不断提高上面最后那个函数的的上界，也就是提高目标函数的下界（极大似然）：**

![](https://img-blog.csdnimg.cn/20190301204108487.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nNDI1Nzc2MDI0,size_16,color_FFFFFF,t_70)

## 5）EM算法流程

​ 首先初始化参数θ的值（当然不是随机的，要满足概率和为1），接下来循环迭代直至收敛，每次迭代时分为两步：

> E步：基于当前的参数（第一次就是基于随机的参数，后面的就是基于计算出来的参数了）估计x的隐变量z的条件概率：
>
> （比如有了θ就能估计属于男、女类的概率）
>
> $$Q\_i(z\_i)=p(z\_i|x\_i;\theta)$$
>
> M步：基于E步参数极大化4）步中的下界函数
>
> （有了E计算的概率，取概率最大的为样本的类标记，于是就确定了样本本次的类标记，就能用常规的极大似然法了。）
>
> （比如一堆数据男女类别都标好了，假设服从高斯分布，还算不出这个模型的参数了？现在当然能算了，这个M步argmax过程就是这么个极大似然过程。显然很抽象，结合到GMM的时候看到会详细点）


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/ml/em.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.