EM 算法总结

2020-09-19 本文已影响0人 zidea

machine_learning.jpg

我们之前学习线性模型，是在这样数据集上样本 X 和对应标签 Y 上找到 X 与 Y 之间关系
$D=\{(x^{(1)},y^{(2)},(x^{(2)},y^{(1)},\dots,(x^{(N)},y^{(N)})\}$
之前线性模型我们是在给定上面数据后找到一种函数来表示 x 和 y 之间映射关系
$f(x^{(i)}) \rightarrow y^{(1)}$
而在统计学模型中，我们模型是在给定 x 来出现的 y 概率有多大，这是将机器学习问题变成概率估计问题
$p(y^{(i)}|x^{(i)}) = ?$

在开始今天新的内容我们先对今天会用到一些知识点回顾一下，以便大家理解今天的 EM 算法。
- 朴素贝叶斯

极大似然估计
联合概率和边缘概率
伯努利分布和二项分布
Jense 不等式

极大似然估计

在统计学中，我们在给定数据，通常会认为这些数据是服从某种分布。假设数据服从正态分布
$p(x|\mu,\sigma)$

我们要做就是根据数据估计出参数 $\mu,\sigma$ ,我们可以根据极大似然值来估计参数 $\mu,\sigma$
$L(\mu,\sigma) = \prod_{i=1}^N p(x^{(i)}|\mu,\sigma)$
$L(\mu,\sigma) = \sum_{i=1}^N \log p(x^{(i)}|\mu,\sigma) p$
通过极大似然可以求出最好 $\mu,\sigma$ 。
这里还是举一个例子就是投掷硬币，我们投掷N(10次）有 k
次正面朝上的概率 p 是多少
$p = p^7(1-p)^3 \, p \in [0,1]$
$p(k|p) = \log(p^k(1-p)^{N-k}$
$\frac{\partial f(p)}{\partial p} = \frac{k}{p} - \frac{N-k}{1-p} \Rightarrow p = \frac{k}{N}$

所以
$p = \frac{7}{10} = 0.7$

贝叶斯概率

假设我样本输入两个类别，样本是高维数据。
$c \in \{0,1\}$
$\begin{aligned} p(c|x) = p(x|c)p(c) \\ \propto \prod_{j=1}^n p(x_i|c)p(c) \end{aligned}$
上面推导过程我就不做过多解释，想必大家一看就到，如果还有问题可以看一看朴素贝叶斯的内容。

联合概率和边缘概率

$p(x) = \prod_{j=1}^n p(x_j) \, x_i \perp x_j \, i \neq j \, i,j = 1,2, \dots , n$
解释上面公式就是 x 是高维(特征)向量，假设特征间是不相关的我们就可以通过特征联合概率来表示样本的概率。

如果我们发现 x 与隐含变量 z 相关，那么就下面公式
$p(x) = \sum_z p(x,z) = \sum_z p(x|z)p(z)$
如果不好理解可以想象图模型来解释一下因为 x 依赖 z 所以就有
$p(x|z)p(z)$ 然后我们罗列出所有 z 情况也就是计算出了 p(x) 的概率。

伯努利分布

回顾一下伯努利分布和二项分布，我们还是拿投掷硬币p(x),大家可能都知道这个问题是服从伯努利分布。伯努利分布就是一个离散的二值分布。
$p(x) = \theta^x(1-\theta)^{1-x}$
$\begin{cases} p(x=0) = 1 - \theta \\ p(x=1) = \theta \end{cases}$
所以伯努利就是简单的二项分布，离散二值化分布。 $\theta$ 表示正面的概率有多大。每一次投掷硬币服从伯努利分布，那么投掷 N 次就是二项式分布。
投掷 N 次出现 k 次正面
$\left( \begin{matrix} N \\ K \end{matrix} \right) \theta^k (1 - \theta)^{N - k}$

Jense 不等式

图
如果 f(x) 凸函数，那么在 a 和 b 在 f(x) 两点连接线段上点值一定位于 f(x) 上方。
我们在曲线任意取两点 a 和 b 坐标分别是 $x_1$ 和 $x_2$ ，然后在 a 和 b 之间取一点， $\theta$ 表示该点

$f(\theta x_1 + (1 - \theta) x_2) \le \theta f(x_1) + (1 - \theta) f(x_2)$

假设 $\theta_1 + \theta_2 = 1$ 上面公式就可以写成
$f(\theta_1 x_1 + \theta_2 x_2) \le \theta_1 f(x_1) + \theta_2 f(x_2)$
$\theta_1 + \theta_2 + \dots + \theta_k = 1$
$f(\theta_1 x_1 + \theta_2 x_2 + \dots + \theta_k x_k) \le \theta_1 f(x_1) + \theta_2 f(x_2) + \dots +\theta_k f(x_k)$

通常概率模型使用 $p(y|\theta)$ 。我们通过一个问题来引出今天EM算法，模型都是为了解决问题。问题是这样的，有 B和 C 两个硬币他们投掷正面(H)的概率是 p 和 q，每次具体投掷哪一个硬币是由 A 硬币来决定，也就是当 A 投掷硬币为正面(H)时，会投掷 B 反之投掷 C 。我们看到只是投掷 B 或 C 出现正面或背面的结果，我们并不知道正面或反面是由哪个硬币投掷出来的。可以将 A 看做隐含变量，无法直接观察到隐含变量。

然后定义一下参数，A 投掷出正面概率为 $\pi$ 。那么我们模型参数是 $\pi$ ，q 和 p 三个参数。接下来我们就研究如何通过模型来表示(解决)出个问题。

已知条件

有参数模型 $\theta = (\pi,p,q)$
$p(y|\theta) = \sum_z p(y,z|\theta)$ 给定 y 我们来估计 $\theta$ ,
那么通过以上已知条件我们需要回答一个问题下一次投掷出现正面的概率

$p(y) = \sum_z p(y|z,\theta) p(z|\theta)$
有了之前边缘概率我们对这个公式就不难理解了。

我们先解决 $p(z|\theta)$ 问题
$p(z|\theta) = p(z|(\pi,q,p)) = \pi$
上面表示投掷 B 硬币的概率
$\begin{cases} p(z=1|\theta) = \pi \\ p(z=0|\theta) = 1 - \pi \end{cases}$

然后我们再解决 $p(y|z,\theta)$ 有了上面推导和边缘概率我们就很容将这个式进行展开
$p(y|z,\theta) = p(y|z=1,\theta) + p(y|z=0,\theta)$
那么如果已知 z=1 也就是投掷硬币 B 硬币投掷出正面概率 p 我们现在问题就是在已知 B 缩小问题范围，B 投掷出正面概率为 p ，根据伯努利分布就可以的下面式子，C 也是同样道理
$\begin{cases} p(y|z=1,\theta) = p^y(1-p)^{1-y}\\ p(y|z=0,\theta) = q^y(1-q)^{1-y} \end{cases}$

通过以上我们就可以得到
$p(y|\theta) = \pi p^y(1-p)^{1-y} + (1-\pi)q^y(1-q)^{1-y}$
现在我们就用所有参数 $\pi,p,q$ 将问题清楚表示出来。二项式分布在生活也是常见，很多选择都是二选一。

$Y = (y^{(1)},y^{(2)},\dots,y^{(N)})$

$p(Y|\theta) =$
$\begin{aligned} p(Y|\theta) = \prod_{i=1}^N p(y{(i)}|\theta)\\ = \pi p^{y^{(i)}}(1-p)^{1-y^{(i)}} + (1-\pi)q^{y^{(i)}}(1-q)^{1-y^{(i)}} \end{aligned}$

$p(Y|\theta) = \prod_{i=1}^N p(y^{(i)}|\theta)$
$p(Y|\theta) = \prod_{i=1}^N \pi p^{y^{(i)}}(1-p)^{1-y^{(i)}} + (1-\pi)q^{y^{(i)}}(1-q)^{1-y^{(i)}}$

$p(Y|\theta) = \sum_{i=1}^N \log p(y^{(i)}|\theta)$
现在问题就变成我们怎样计算 $p,q,\theta$ ，接下来介绍一种算法来计算，那么在开始介绍算法我们要知道现在模型是一个混合模型。

混合模型

假设我们有学生身高样本，但是我们知道女生和男生的身高正态分布式两个不同正态分布。那么我们样本 N 是由表示女生 N1 和表示男生 N2 两个部分数据组成，随机找到学生，他是男生概率假设为 $\pi$ 。假设 N1 服从 $N(\mu_1,\sigma_1)$ , N2 服从 $N(\mu_2,\sigma_2)$ 。
$p(x|\mu_1,\mu_2,\sigma_1,\sigma_2,\pi)$
这里 $\pi$ 表示 N1 的权重所以我们模型是两个模型混合按一定权重的组合。

$p(x|\mu_1,\mu_2,\sigma_1,\sigma_2,\pi) = \pi N(\mu_1,\sigma_1) + (1-\pi)N(\mu_2,\sigma_2)$

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H | T | H | H |T | T | H | H | T | T | H |
| B | C | B |B | C | C | B | C | B | C | B |

$\begin{cases} p = \frac{ count(1)}{count(B)}\\ p = \frac{ count(1)}{count(C)}\\ \pi = \frac{count(C)}{count(C) + count(B)} \end{cases}$

如果我们知道那一次是由 B 投掷出的结果，我们问题就迎刃而解了， $\pi = \frac{6}{11} \, p = \frac{5}{6} \, q = \frac{1}{5}$ 。那么现在就是知道我们难点就是弄清每一次是由哪个一个硬币投掷出来来到的这件事。
我们这里引入一个参数 $\mu$ 表示在 j 次是由 B 投掷出来的概率，假定我们已经知道 $\pi,p,q$ 这三个参数了，我们估计一下 $\mu$

$\mu_{i} = \frac{\pi p^{y^{(i)}}(1-p)^{1-y^{(i)}}}{\pi p^{y^{(i)}}(1-p)^{1-y^{(i)}} + (1-\pi)q^{y^{(i)}}(1-q)^{1-y^{(i)}}}$

这里有点绕，我希望大家能够理解，看的时候可能感觉已经明白，但是一旦自己列出上面式子，就会有点懵。在之前推导公式
$p(Y|\theta) = \pi p^{y^{(i)}}(1-p)^{1-y^{(i)}} + (1-\pi)q^{y^{(i)}}(1-q)^{1-y^{(i)}}$
$\begin{cases} p(z=1|\theta) = \pi p^{y^{(i)}}(1-p)^{1-y^{(i)}} \\ p(z=0|\theta) = (1-\pi)q^{y^{(i)}}(1-q)^{1-y^{(i)}} \end{cases}$
这是之前我们推导出来公式，有了这这些式子，我想不用解释大家也都明白了 $\mu_i$ 的来历了吧。可以先随机给出 $\pi,p,q$ 的值来计算 $\mu$ 的值然后在根据 $\mu$ 的值计算 $\pi,p,q$ 的值。

第一个我们先计算 $\pi$ ,我们知道 $\mu$ 代表每一次投掷出 B 概率，那么对 $\mu$ 求和取均值不就是 $\pi$ 的值吗。
$\pi = \sum_{j=1}^N \mu_j \frac{1}{N}$
第二我们来求 p 也就是 B 硬币投掷正面的概率，我们来看看怎么用 $\mu$ 来表示这个问题。
$p = \frac{\sum_{j=1}^{N} \mu_j y^{(j)}}{\sum_{j=1}^N \mu_{j}}$
首先我们计算出B 出现概率，然后我们在B出现时为真面的概率和，当 $y^{(j)}=1$ 时候为 $\mu_j$ 当 $y^{(j)}=0$ 这样就可以计算出 p 概率
最后计算 C 硬币投掷正面概率 q ，我们知道每一次是 B 概率为 $\mu_j$ 那么是 C 概率就是 $1 - \mu_j$
$q = \frac{\sum_{j=1}^N(1- \mu_j)y^{(j)}}{\sum_{j=1}^N(1- \mu_j)}$

好上面说了这么多，大家有点感觉没，这个难题我们解决分两个步骤，我们通过添加下角标来表示参数先后顺序，那么我们

E step

我们在开始也就是 t = 0 时候我们估计出 $\pi_0,p_0,q_0$ 值然后带入下面公式得到 $\mu_1$ 的值

$\mu_{t+1}^{i} = \frac{\pi_{t} p_t^{y^{(i)}}(1-p_t)^{1-y^{(i)}}}{\pi p_t^{y^{(i)}}(1-p_t)^{1-y^{(i)}} + (1-\pi)q_t^{y^{(i)}}(1-q_t)^{1-y^{(i)}}}$

M step

有了 $\mu_1$ 我们就计算出 $\pi_1,p_1,q_1$ 的值然后在用这些值推算出 $\mu_2$

$\begin{cases} \pi_{t+1} = \sum_{j=1}^N \mu^{(j)}_{t+1} \frac{1}{N}\\ p_{t+1} = \frac{\sum_{j=1}^{N} \mu^{(j)}_{t+1} y^{(j)}}{\sum_{j=1}^N \mu_{j}}\\ q_{t+1} = \frac{\sum_{j=1}^N(1- \mu^{(j)}_{t+1})y^{(j)}}{\sum_{j=1}^N(1- \mu^{(j)}_{t+1})} \end{cases}$

突然感觉这个算法有点像动态规划，其实我们可以用穷举方法来分别固定两个参数然后第三个参数从 0 到 1 进行迭代，这样一来我们计算量就会很大，这里用了更聪明方法方法就会估计初始值，然后不断迭代来进行计算。

现在我们回顾整理一下到底什么是 EM 算法

$\begin{aligned} \sum_{i=1}^N \log p(x^{(i)}|\theta) = \sum_{i=1}^N \log \sum_{z^{(i)}} p(x^{(i)}|\theta) \tag{1} \end{aligned}$

在(1)中，求极大似然值，我们引入隐含变量 z 然后对其求和。

$\pi p_t^{y^{(i)}}(1-p_t)^{1-y^{(i)}} + (1-\pi)q_t^{y^{(i)}}(1-q_t)^{1-y^{(i)}}$

我们引入隐含 $Q_i(z^{(i)})$ 概率分布，在函数乘以 $Q_i(z^{(i)})$ 再除以 $Q_i(z^{(i)})$
$\sum_{i=1}^N \log p(x^{(i)}|\theta) = \sum_{i=1}^N \log \sum_{z^{(i)}} Q_i(z^{(i)}) \frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)}) }$

$Q_i(z^{(i)})$ 是关于 z 的概率分布，所以 $\sum_{z(i)}Q_i(z^{(i)})$ 对 z 求期望，根据 Jense 不等式可以函数期望变成期望的函数。

图
我们都是知道 log 是凹函数，所以有期望的函数大于函数的期望，也就是有这样 $log(E(x)) \ge E(log(x)$ 关系，所以从而得到这下面的不等式。

$\sum_{i=1}^N \log \sum_{z^{(i)}} Q_i(z^{(i)}) \frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)}) } \ge \sum_{i=1}^N \sum_{z^{(i)}} Q_i(z^{(i)}) \log \frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)}) }$

到这一步我们就完成不等式跃迁，我们知道 $\sum_{i=1}^N \log p(x^{(i)}|\theta)$ 的极大似然值要大于 $\sum_{i=1}^N \sum_{z^{(i)}} Q_i(z^{(i)}) \log \frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)}) }$ 那么我们只要将下界不断增大就会满足极大似然值。

$f\left(E_{z^{(i) \sim Q_i}}\left[\frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)}) }\right]\right) \ge E_{z^{(i) \sim Q_i}}\left[ f\left(\frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)}) }\ \right) \right]$

我们知道 $Q_i(z^{(i)})$ 是一个概率分布，当 $Q_i(z^{(i)})$ 比较均匀情况下，

$E_{z^{(i) \sim Q_i}}\left[ f\left(\frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)}) }\ \right) \right] = E_{z^{(i)} \sim Q_i} \left[ f(z^{(i)}) \right]$
当均匀分布时候值最大，也就是函数值相等时候期望最大，当函数里面的值都等于 c 是均匀的期望时最大的。
$\frac{p(x^{(i)},z^{(i)}|\theta)}{Q_i(z^{(i)})} = c$
从而得到下面正比关系
$Q_i(z^{(i)}) \propto p(x^{(i)},z^{(i)}|\theta)$