EM算法及其应用GMM/pLSA/LDA

EM算法及其应用GMM，pLSA

问题定义

从样本观察数据（显性特征x）中，找出样本的模型参数（ $\theta$ ）。最常用的方法就是极大化模型分布的对数似然函数。

$p(x,y)$ 是样本特征和label的联合分布， $p(x,y) = p(x|y)p(y)$ ，为了使得估计的结果泛化能力更好，我们将 $p(x|y)$ 分解为 $\sum_z p(x|z)p(z|y)$ ， $z$ 就是隐变量。

这类问题有：

主题模型：把文章（显性特征x）描述为主题（隐性特征z）的叠加
GMM：把某堆样本（显性特征x）描述为K个高斯分布（隐性特征z）的叠加

以上问题，主要是通过引入隐变量，把样本表述为隐变量的分布，从而简化每个样本点表述。对于此问题通用的数学描述为：

给定一个样本集 $X=\{x^{(1)},…,x^{(m)}\}$ ，我们假设观察到的 $x^{(i)}$ 还对应着隐含变量的概率分布 $z^{(i)}$ ，记 $Z=\{z^{(1)},…,z^{(m)}\}$ 。则该模型 $P(x,z;\theta)$ 的对数似然函数为：
$\begin{equation*} L(\theta;X)=log{P(X;\theta)}=\log{\sum_Z P(X,Z;\theta)} \end{equation*}$
而 $P(X,Z;\theta)$ 根据具体的问题来定义。

目标是求得参数 $\theta$ ，使得对数似然函数最大：
$\begin{equation*}\theta=\arg\max_\theta{L(\theta;X)}\end{equation*}$

这时候，交叉熵为：
$\begin{equation}S=-\sum_{x,y}\tilde{p}(x,y)\log\sum_z p(x|z)p(z|y)p(y)\end{equation}$
优化目标为：
$\begin{equation}S=-\sum_{x,y}\tilde{p}(x,y)\log\sum_z p(x|z)p(z|y)\end{equation}$
它的梯度是
$\begin{equation}\begin{aligned}&\frac{\partial S}{\partial p(x|z)} = -\sum_{y}\frac{\tilde{p}(x,y)}{\sum_z p(x|z)p(z|y)}p(z|y)\\ &\frac{\partial S}{\partial p(z|y)} =-\sum_{x} \frac{\tilde{p}(x,y)}{\sum_z p(x|z)p(z|y)}p(x|z)\end{aligned}\end{equation}$
$p(x|z),p(z|y)$ 都是概率分布，即大于0且满足：
$\begin{equation}\sum_x p(x|z) = 1,\quad \sum_z p(z|y)=1\end{equation}$

直接梯度下降是行不通的，这就需要借助EM算法。

EM 算法的过程

随机选取或者根据某种先验知识来初始化 $\theta_0$ 。
循环执行以下两步直到对数似然函数收敛：
1. E-step（Expectation）：基于当前的 $\theta$ 求出 $Z$ 的后验概率 $P(Z|X;\theta_t)$ ，进而求出 $L(\theta;X,Z)$ 在分布 $Z \sim P(Z|X;\theta)$ 上的期望 $E_{Z|X;\theta_t}[L(\theta;X,Z)]$
  
  $\begin{align*} E_{Z|X;\theta_t}[L(\theta;X,Z)] &:= E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \\ &= \sum_Z P(Z|X;\theta_t) \log{P(X,Z;\theta)} \end{align*}$
2. M-step（Maximization）：求 $\theta$ 使得上面求得 $E_{Z|X;\theta_t}[L(\theta;X,Z)]$ 最大化
  
  $\begin{equation*} \theta_{t+1} := \arg\max_\theta E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \end{equation*}$

原理

对于最大似然函数的参数求解：
$\theta=\arg\max_\theta{L(\theta;X)}$$

$\begin{align*} L(\theta) &= \log{P(X;\theta)} \\ &= \log{\sum_Z P(X,Z;\theta)} \end{align*}$

$Z$ 是隐变量，观测不到，为了求解上式，假设我们知道 $Z$ 的概率分布 $Q(Z)$ ：

$\begin{align*} L(\theta) &= \log{\sum_Z P(X,Z;\theta)} \\ &= \log{\sum_Z Q(Z) \frac{P(X,Z;\theta)}{Q(Z)}} \\ &= \log E_{Z \sim Q}\left[ \frac{P(X,Z;\theta)}{Q(Z)} \right] \end{align*}$
根据 Jensen 不等式 [1]，对于任意分布 $Q$ 都有：

$\begin{equation*} L(\theta) = \log E_{Z \sim Q}\left[ \frac{P(X,Z;\theta)}{Q(Z)} \right] \geq E_{Z \sim Q}\left[ \log\frac{P(X,Z;\theta)}{Q(Z)} \right] \end{equation*}$
且上面的不等式在 $\frac {P(X,Z;\theta)} {Q(Z)}$ 为常数时取等号。

（备注：关键的点就是Jensen不等式在x为常数时取等号（x的所有值重叠，等于1个值）。这里正好对应隐变量的分布的确定，即E步求解的隐变量的分布）

于是我们就得到了 $L(\theta;X)$ 的一个下界函数。我们要想套用上面的算法，还要让这个不等式在 $\theta_t$ 处取等号，这就这要求在 $\theta = \theta_t$ 时 $\frac {P(X,Z;\theta)} {Q(Z)}$ 为常数，即 $Q(Z) \propto P(X,Z;\theta_t)$ 。由于 $Q(Z)$ 是一个概率分布，必须满足 $\sum_z Q_i(z) = 1$ ，所以这样的 $Q(Z)$ 只能是 $Q(Z) = \frac{P(X,Z;\theta_t)} {\sum_Z P(X,Z;\theta_t)} = P(Z|X;\theta_t)$ 。那我们就把 $Q(Z) = P(Z|X;\theta_t)$ 代入上式，得到：

$\begin{equation*} L(\theta) \geq E_{Z|X;\theta_t}\left[ \log\frac{P(X,Z;\theta)}{P(Z|X;\theta_t)} \right] \end{equation*}$
最大化这个下界函数：

$\begin{align*} \theta_{t+1} &:= \arg\max_\theta E_{Z|X;\theta_t}\left[ \log\frac{P(X,Z;\theta)}{P(Z|X;\theta_t)} \right] \\ &\equiv \arg\max_\theta \sum_{Z} P(Z|X;\theta_t) \log\frac{P(X,Z;\theta)}{P(Z|X;\theta_t)} \\ &=\arg\max_\theta \sum_{Z} [P(Z|X;\theta_t)\log P(X,Z;\theta) - P(Z|X;\theta_t) \log P(Z|X;\theta_t)] \\ &= \arg\max_\theta \sum_{Z} P(Z|X;\theta_t)\log P(X,Z;\theta) \\ &\equiv \arg\max_\theta E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \end{align*}$
其中倒数第二步是因为 $- P(Z|X;\theta_t) \log P(Z|X;\theta_t)]$ 这一项与 $\theta$ 无关，所以就直接扔掉了。这样就得到了本文第二节 EM 算法中的形式——它就是这么来的。

以上就是 EM 了。至于独立同分布的情况推导也类似。

[1]
Jensen 不等式：

对于凸函数 $f(x)$ ，其函数的期望大于等于期望的函数 $\begin{equation*} E[f(X)]\geq f(E[X]) \end{equation*}$

若 $f$ 是严格凸的，则上式取等号当前仅当 $X$ 为常数。

在这里 $\log$ 函数是严格凹的，所以要把上面的不等号方向

EM算法应用示例

kmeans

GMM

问题描述

假设某个数据分布是由K个高斯分布加权叠加而来：
$p(x) = \sum_{k=1}^K{w_kg_k(x|\mu,\sigma)}$
目标是，求出这K个高斯分布及其权重。

换一种说法，也就是，用K个高斯分布的加权和来拟合数据分布 $p(x)$

相比于K-means，只是把原本样本一定属于某一类改成了一个样本属于某类的概率。K-means的结果是把每个数据点assign到其中某一个cluster,而GMM则是给出每个数据点被assign到每一个cluster的概率，又称作soft assignment。

求解过程

初始化：随机（或者按某种方式）初始化K个高斯分布
重复以下步骤，直至收敛：
- E-step：根据当前参数，计算每个样本 $x_i, i = 1,2,...,N$ 点来自于第 $k$ 个分模型 $g_k,k=1,2,...,K$ 的概率：
$z_k^i = \frac{w_kg_k(x|\mu,\sigma)}{\sum_jw_jg_j(x|\mu,\sigma)}\\ z_k = \sum_i{z_k^i}$

(注意，这里分子分母到底要不要加上 $w_k$ )
- M-step：根据所有的 $z_k^i$ ，更新一版参数（K个高斯分布的参数和权重）：
$\mu_k = \frac{\sum_i{z_k^ix_i}}{\sum_i{z_k^i}}\\ \sigma_k = \frac{\sum_i{z_k^i(x_i-\mu_k)^2}}{\sum_i{z_k^i}}\\ w_k = \frac{\sum_i{z_k^i}}{N}$

图示

image.png

pLSA

问题描述

pLSA 模型有两个基本的设定：

把文章看成一个词袋（bag-of-words），忽略词序关系。
pLSA是一个生成模型，其概率图为：

image.png

即：
$\begin{align*} P(d,w) &= P(d)P(w|d) \\ P(w|d) &= \sum_z P(w|z)P(z|d) \end{align*}$

而我们感兴趣的正是其中的 $P(z|d)$ 和 $P(w|z)$ ，即文章的主题分布，和主题的词分布。记 $\theta = (P(z|d), P(w|z))$ ，表示我们希望估计的模型参数（模型中共有 $|Z| \cdot |D| + |W| \cdot |Z|$ 个参数）。

求解过程

根据最大log似然估计法，我们要求的就是
$\begin{align*} \arg\max_\theta L(\theta)&= \arg\max_\theta \sum_{d,w} n(d,w)\log P(d,w;\theta) \\ &= \arg\max_\theta \sum_{d,w} n(d,w)\log P(w|d;\theta)P(d) \\ &= \arg\max_\theta \left\{ \sum_{d,w} n(d,w)\log P(w|d;\theta) + \sum_{d,w} n(d,w)\log P(d) \right\} \end{align*}$
这里由于 $\sum_{d,w} n(d,w)\log P(d)$ 这一项与 $\theta$ 无关，在 $\arg\max_\theta$ 中可以被直接扔掉。 [1]

因此

$\begin{align*} \arg\max_\theta L(\theta) &=\arg\max_\theta\sum_{d,w} n(d,w)\log P(w|d;\theta) \\ &= \arg\max_\theta \sum_{d,w} n(d,w)\log \sum_z P(w|z)P(z|d) \end{align*}$
这里出现了 $\log$ 套 $\sum$ 的形式，导致很难直接拿它做最大似然。但假如能观察到 $z$ ，问题就很简单了。于是我们想到根据 EM 算法，可以用下式迭代逼近 $\arg\max_\theta L(\theta)$ ：

$\begin{equation*}\arg\max_\theta Q_t(\theta) = \arg\max_\theta \sum_{d,w} n(d,w) E_{z|d,w;\theta_t}[\log P(w, z|d;\theta)] \end{equation*}$
其中

$\begin{align*} E_{z|d,w;\theta_t}[\log P(w, z|d;\theta)] &= \sum_z P(z|d,w;\theta_t) \log P(w, z|d;\theta) \\ &= \sum_z P(z|d,w;\theta_t) [\log P(w|z) + \log P(z|d)] \\ \end{align*}$
在 E-step 中，我们需要求出 $Q_t(\theta)$ 中除 $\theta$ 外的其它未知量，也就是说对于每组 $(d^{(i)}, w^{(j)}, z^{(k)})$ 我们都需要求出 $P(z^{(k)}|d^{(i)},w^{(j)};\theta_t)$ 。根据贝叶斯定理贝叶斯定理，我们知道：

$\begin{equation*} P(z^{(k)}|d^{(i)},w^{(j)};\theta_t) = \frac{P_t(z^{(k)}|d^{(i)})P_t(w^{(j)}|z^{(k)})} {\sum_z P_t(z|d^{(i)})P_t(w^{(j)}|z)} \end{equation*}$
而 $P_t(z|d)$ 和 $P_t(w|z)$ 就是上轮迭代求出的 $\theta_t$ 。这样就完成了 E-step。

接下来 M-step 就是要求 $\arg\max_\theta Q_t(\theta)$ 了。利用基本的微积分工具 [2]，可以分别对每对 $(w^{(j)}, z^{(k)})$ 和 $(d^{(i)}, z^{(k)})$ 求出：

$\begin{align*} P_{t+1}(w^{(j)}|z^{(k)}) &= \frac {\sum_d n(d,w^{(j)})P(z^{(k)}|d,w^{(j)};\theta_t)} {\sum_{d,w} n(d,w)P(z^{(k)}|d,w;\theta_t)} \\ P_{t+1}(z^{(k)}|d^{(i)}) &= \frac {\sum_w n(d^{(i)},w)P(z^{(k)}|d^{(i)},w;\theta_t)} {\sum_{w,z} n(d,w)P(z|d^{(i)},w;\theta_t)} \end{align*}$
以上就是 pLSA 算法了。

忽略原理和证明，直接看求解过程：

EM求解方法：

E-step:
$P(z_k|d_i,w_j) = \frac{P(w_j|z_k)P(z_k|d_i)}{\sum_l P(w_j|z_l)P(z_l|d_i)}$
M-step:
$P(w_j|z_k) = \frac{\sum_i{n(d_i,w_j)P(z_k|d_i,w_j)}}{\sum_m\sum_i n(d_i,w_m)P(z_k|d_i,w_m)} \\ P(z_k|d_i) = \frac{\sum_i{n(d_i,w_j)P(z_k|d_i,w_j)}}{n(d_i)}$

LDA

在pLSA中用极大似然估计的思想去推断参数（文档的主题分布和主题的词分布），而LDA把这两参数视为概率分布，其先验信息为dirichlet分布。因此，在数据量不大的时候，LDA能缓解过拟合问题，而在数据量很大的时候，pLSA是比较好的选择。

LDA中，估计Φ、Θ这两未知参数可以用变分(Variational inference)-EM算法，也可以用gibbs采样，前者的思想是最大后验估计MAP，后者的思想是贝叶斯估计。

参考：

https://spaces.ac.cn/archives/4277

EM算法原理总结

Probabilistic latent semantic analysis (pLSA)

A Note on EM Algorithm and PLSA --- Xinyan Lu

李航-统计机器学习第一版

高斯混合模型

github
推荐我的开源项目 exFM c++ deepFM

最后编辑于：2021.11.02 11:05:00

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,504评论 6赞 496
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,434评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,089评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,378评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,472评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,506评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,519评论 3赞 413
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,292评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,738评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,022评论 2赞 329
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,194评论 1赞 342
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,873评论 5赞 338
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,536评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,162评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,413评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,075评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,080评论 2赞 352

EM算法及其应用GMM/pLSA/LDA