分布式处理与计算：随机模拟和统计推断

例子一:指数分布#

要产生 $n$ 个服从指数分布 $\text{Exp}(\lambda)$ 的随机数。指数分布的概率密度函数与分布函数分别是

$f(x) = \lambda e^{-\lambda x}, \quad F(x) = 1 - e^{-\lambda x} \quad (x \ge 0)$

令 $U = F(X) = 1 - e^{-\lambda X}$,反解出

$X = -\frac{1}{\lambda}\ln(1 - U)$

$1-U$ 与 $U$ 同分布(都是 $U(0,1)$),结果也可以写成 $X = -\dfrac{1}{\lambda}\ln U$

例子二:标准 Laplace 分布#

要产生 $n$ 个服从标准 Laplace 分布的随机数。Laplace 分布(双指数分布)的概率密度函数为

$f(x) = \frac{1}{2} e^{-|x|}$

对它积分,可得累积分布函数为分段形式:

$F(x) = \begin{cases} \dfrac{1}{2}e^{x}, & x < 0 \\[2mm] 1 - \dfrac{1}{2}e^{-x}, & x \ge 0 \end{cases}$

令 $U = F(X)$ 分别在两段上反解,就得到逆函数:

$X = \begin{cases} \ln(2U), & 0 < U < \tfrac{1}{2} \\[2mm] -\ln\big(2(1-U)\big), & \tfrac{1}{2} \le U < 1 \end{cases}$

按这个式子把均匀随机数代进去,就得到 Laplace 分布的随机数。

例子一:遗传模型(genetic linkage model)#

设一次实验可能出现四个结果,发生概率分别为

$\frac{1}{2} + \frac{\theta}{4},\quad \frac{1-\theta}{4},\quad \frac{1-\theta}{4},\quad \frac{\theta}{4}, \qquad 0 \le \theta \le 1$

现在进行了 197 次试验,四种结果的发生次数分别为 125、18、20、34。要求出分布中参数 $\theta$ 的一个好的估计。

引入隐变量:第一类结果的概率 $\tfrac{1}{2} + \tfrac{\theta}{4}$ 可以拆成 $\tfrac{1}{2}$ 和 $\tfrac{\theta}{4}$ 两部分,于是把观测到的 125 拆成两块 $y_1 = 125 - z$ 和 $z$,对应概率分别为 $\tfrac{1}{2}$ 和 $\tfrac{\theta}{4}$,其中 $z$ 就是看不到的隐变量。

完全似然函数可以写成(带隐变量 $z$)

$L(\theta) \propto \left(\frac{1}{2}\right)^{125-z}\left(\frac{\theta}{4}\right)^{z}\left(\frac{1-\theta}{4}\right)^{18}\left(\frac{1-\theta}{4}\right)^{20}\left(\frac{\theta}{4}\right)^{34}$

对数似然(去掉与 $\theta$ 无关的常数)为

$\log L(\theta) \propto (z + 34)\log\theta + (18+20)\log(1-\theta)$

E 步:在当前估计 $\theta^{(i)}$ 下,$z$ 是二项分布的条件期望,即把 125 按两部分概率比例分:

$z^{(i)} = E\big[z \mid \theta^{(i)}\big] = 125 \cdot \frac{\tfrac{\theta^{(i)}}{4}}{\tfrac{1}{2} + \tfrac{\theta^{(i)}}{4}} = 125 \cdot \frac{\theta^{(i)}}{2 + \theta^{(i)}}$

M 步:对 $Q$(即上面对数似然把 $z$ 换成 $z^{(i)}$)求 $\theta$ 的偏导并令其为 0

$\frac{\partial}{\partial\theta}\Big[(z^{(i)}+34)\log\theta + 38\log(1-\theta)\Big] = \frac{z^{(i)}+34}{\theta} - \frac{38}{1-\theta} = 0$

解得迭代公式

$\theta^{(i+1)} = \frac{z^{(i)} + 34}{z^{(i)} + 34 + 38} = \frac{z^{(i)} + 34}{z^{(i)} + 72}$

反复用这两步迭代,$\theta$ 就会收敛到极大似然估计。

例子二:混合高斯模型(Gaussian Mixture Model, GMM)#

假设观测数据 $y_1, y_2, \dots, y_N$ 由高斯混合模型生成:

$P(y\mid\theta) = \sum_{k=1}^{K} \alpha_k\, \phi(y\mid\mu_k,\sigma_k^2)$

其中 $\alpha_k$ 是第 $k$ 个分模型的混合系数,满足 $\alpha_k \ge 0$、$\sum_k \alpha_k = 1$;$\phi(y\mid\mu_k,\sigma_k^2)$ 是第 $k$ 个高斯分模型的密度。要用 EM 算法估计参数 $\theta = \{\alpha_k, \mu_k, \sigma_k^2\}$。

定义隐变量 $\gamma_{jk}$:

$\gamma_{jk} = \begin{cases} 1, & \text{第 } j \text{ 个观测来自第 } k \text{ 个分模型} \\ 0, & \text{否则} \end{cases}$

有了观测数据 $y_j$ 和未观测数据 $\gamma_{jk}$,完全数据就是 $(y_j, \gamma_{j1}, \dots, \gamma_{jK})$。于是完全数据的似然函数为

$P(y,\gamma\mid\theta) = \prod_{k=1}^{K} \alpha_k^{\,n_k} \prod_{j=1}^{N} \Big[\phi(y_j\mid\mu_k,\sigma_k^2)\Big]^{\gamma_{jk}}, \qquad n_k = \sum_{j=1}^{N}\gamma_{jk}$

对应的完全数据对数似然为

$\log P(y,\gamma\mid\theta) = \sum_{k=1}^{K}\Big\{ n_k\log\alpha_k + \sum_{j=1}^{N}\gamma_{jk}\Big[\log\tfrac{1}{\sqrt{2\pi}} - \log\sigma_k - \tfrac{1}{2\sigma_k^2}(y_j-\mu_k)^2\Big]\Big\}$

E 步:确定 Q 函数。把 $\gamma_{jk}$ 换成它的条件期望 $\hat\gamma_{jk}$(称为”响应度”,即第 $j$ 个观测由第 $k$ 个分模型生成的后验概率):

$\hat\gamma_{jk} = \frac{\alpha_k\,\phi(y_j\mid\mu_k,\sigma_k^2)}{\sum_{l=1}^{K}\alpha_l\,\phi(y_j\mid\mu_l,\sigma_l^2)}$

把 $\hat\gamma_{jk}$ 和 $n_k=\sum_j\hat\gamma_{jk}$ 代入,就得到 Q 函数的具体表达式。

M 步:对各参数求偏导并令其为 0,得到更新公式:

$\mu_k = \frac{\sum_{j=1}^{N}\hat\gamma_{jk}\,y_j}{\sum_{j=1}^{N}\hat\gamma_{jk}}, \qquad \sigma_k^2 = \frac{\sum_{j=1}^{N}\hat\gamma_{jk}(y_j-\mu_k)^2}{\sum_{j=1}^{N}\hat\gamma_{jk}}, \qquad \alpha_k = \frac{\sum_{j=1}^{N}\hat\gamma_{jk}}{N} = \frac{n_k}{N}$

E 步、M 步交替迭代到收敛,就得到 GMM 的参数估计。

分布式 EM 算法#

在高斯混合模型下,当数据量 $y_1,\dots,y_N$ 很大时,可以把 EM 做成分布式的。

在 E 步把数据分散到各个节点,每个节点在本地算出各自数据的条件概率(响应度) $\hat\gamma_{jk}$ 以及对应的期望充分统计量(如 $\sum \hat\gamma_{jk}$、$\sum \hat\gamma_{jk}y_j$、$\sum \hat\gamma_{jk}y_j^2$);

到 M 步再把各节点的这些充分统计量汇总相加,统一更新全局参数 $\alpha_k, \mu_k, \sigma_k^2$。

由于充分统计量是可加的,这种”各节点局部求和 + 全局汇总”的方式与单机 EM 结果完全一致,却能利用 Spark 这类框架并行处理海量数据。