[DeepBayes2018]Day 1, lecture 3. Models with latent variables and EM-algorithm

隐变量模型

在隐变量模型这堂课中，主要内容为以下几个方面

KL散度
混合高斯模型
EM算法
离散型和连续型隐变量
案例：Word2Vec

1. KL散度（Kullback-Leibler divergence, KL divergence）

通常需要计算对象之间的距离和差异性。概率论的研究对象是分布，分布之间差异性的常见量化方式之一是KL散度

定义：在同一个随机变量上的两个分布 $\,q\,$ 和 $\,p\,$ ，它们的 $KL$ 散度定义成：
$\begin{equation} KL(q(x)||p(x))=\int{q(x)log{\frac{q(x)}{p(x)}}\mathrm{d}x}=E_q\,log\frac{q(x)}{p(x)} \tag{1.1} \end{equation}$
这里是积分形式的定义，实际应用时主要是计算离散形式的。此时需要注意的问题是：
- $q$ 出现等于0的情况
- $p$ 出现等于0的情况
解决的方法是使用平滑法，这篇文章有说明

另外，为什么叫 $KL$ 散度，不叫 $KL$ 距离，课中Dmitry Vetrov老师的解释是 $KL$ 不满足三角不等式（两边之和大于第三边）和对称性，即 $KL(p||q)\neq KL(q||p)$ （课程中举了单峰分布与双峰分布的KL散度来直观地理解不对称性）但其实日常一般也可以叫做 $KL$ 距离
与信息论的联系： $KL(q||p)$ 等于 $\,q\,$ 和 $\,p\,$ 的交叉熵减去 $\,q\,$ 的信息熵，计算如下：
$\begin{equation} \begin{split} KL(q(x)||p(x)) &=\int{q(x)log{\frac{q(x)}{p(x)}}\mathrm{d}x}\\ &=\int{q(x)log{\,q(x)}\mathrm{d}x}-\int{q(x)log{\,p(x)}\mathrm{d}x}\\ &=CrossEntropy-Entropy \end{split} \end{equation} \tag{1.2}$
非负性，证明如下：
$\begin{equation} \begin{split} KL(q(x)||p(x)) &=\int{-log{\frac{p(x)}{q(x)}}\cdot q(x)\mathrm{d}x}=E_q[-log\frac{p(x)}{q(x)}]\\ \end{split} \end{equation}$
根据Jensen不等式，对于随机变量 $X$ 和凸函数 $\varphi$ ，有 $\varphi(EX)=E(\varphi(X))$ 。凸函数的判断方式是函数二阶导数为0。正好 $KL$ 距离可以表现为期望形式，而 $-log(x)$ 的二阶导数大于0，因此利用不等式，得
$\begin{equation} \begin{split} KL(q(x)||p(x)) &=E_q[-log\frac{p(x)}{q(x)}]\\ &\geq-log(E_q[\frac{p(x)}{q(x)}])=-log\int{\frac{p(x)}{q(x)}\cdot q(x)\mathrm{d}x}\\ &=-log\int{p(x)\mathrm{d}x}=-log\,1=0 \end{split} \end{equation}$
即证。另外根据 $KL$ 距离的定义可知，当 $q(x)=p(x)$ 时， $KL$ 距离为0

注1（可略）：课程中给出的证明中，如下
$\int{q(x)log\frac{p(x)}{q(x)}\mathrm{d}x}\leq log\int{q(x)\frac{p(x)}{q(x)}\mathrm{d}x}=log\int{p(x)\mathrm{d}x}=log\,1=0$
跟Jensen不等式不同，貌似是如果是凹函数，不等式号就变成小于号了吗？其实这个也是根据Jensen不等式来的。但这个还有另外一个名字，叫Gibbs不等式。

注2（可略）：课程还提到了any concave function f such that f(1)=0 define its own divergence。这是因为注1最右边中需满足 $f(1)=0$ 才能保证散度的非负性

2. 混合高斯分布

单一情形：所有样本来自于同一个高斯分布时，需要估计高斯总体的均值和方差。用矩估计、极大似然估计等方法都能估计出参数来。
复杂情形：样本来自多个多个高斯分布，即混合高斯分布。每个高斯分布的参数都不同。此时如果我们知道每个样本来自于哪个分布地话，仍然可以很容易解出来。把属于每个分布的样本放一起，一个个分别作估计就行。
- 但如果不知道呢？可以将其中视为一个高斯分布，从而求解。但更好的方法是隐变量模型
加隐变量。为每个对象 $x_i$ 新建一个隐变量 $z_i$ ，代表该对象属于第几个高斯分布
构建似然模型。当只考虑一个高斯分布的话，似然函数就是 $p(X|\theta)$ 。现在加了隐变量后的似然函数就是 $p(X,Z|\theta)$
- 注（个人理解）：之前纠结为什么是 $p(X,Z|\theta)$ ，而不是 $p(X|\theta)$ 。原因在于似然函数的思想就是认为大概率事件更有可能发生，所以是找到参数使得目前样本产生的联合概率最大。不考虑隐变量时，就只有 $X$ 。有了隐变量，比如100中有99个都是来自于一个高斯分布，只有1个来自于另一个高斯分布。根据似然函数的思想，当然是样本来自于第一个高斯分布的概率更大。所以，隐变量模型，要把 $Z$ 和 $X$ 放一起。
- 似然函数如下：
  $\begin{equation} \begin{split} p(X,Z|\boldsymbol{\theta}) &=\displaystyle\prod_{i=1}^np(x_i,z_i|\boldsymbol{\theta})=\displaystyle\prod_{i=1}^np(x_i|z_i,\boldsymbol{\theta})p(z_i|\boldsymbol{\theta})\\ &=\displaystyle\prod_{i=1}^n\pi_{z_i}\mathcal{N}(x_i|\mu_{z_i},\sigma_{z_i}^2) \end{split} \end{equation}$
  如果知道 $X$ 和 $Z$ 的话，直接似然函数对数化，偏导为0求解就可以了。但 $Z$ 并不知道
  
  因此退而求其次，去最大化不完全似然函数 $log(X|\boldsymbol{\theta})$
- 不完全似然函数
  $\begin{equation} \begin{split} log\,p(X|\boldsymbol{\theta}) &=\int{q(Z)log\,p(X|\boldsymbol{\theta})\mathrm{d}Z}\\ &=\int{q(Z)log\frac{p(X,Z|\boldsymbol{\theta})}{p(Z|X,\boldsymbol{\theta})}\mathrm{d}Z}\\ &=\int{q(Z)log\frac{q(Z)p(X,Z|\boldsymbol{\theta})}{q(Z)p(Z|X,\boldsymbol{\theta})}\mathrm{d}Z}\\ &=\int{q(Z)log\frac{p(X,Z|\boldsymbol{\theta})}{q(Z)}\mathrm{d}Z}+\int{q(Z)log\frac{q(Z)}{p(Z|X,\boldsymbol{\theta})}\mathrm{d}Z}\\ &=\mathcal{L}(q,\boldsymbol{\theta})+KL(q||p)\\ &\geq\mathcal{L}(q,\boldsymbol{\theta}) \end{split} \end{equation}$
  将 $\mathcal{L}(q,\boldsymbol{\theta})$ 称为变分下界（variational lower bound）
  
  放弃最大化 $log\,p(X|\boldsymbol{\theta})$ ，改为最大化 $\mathcal{L}(q,\boldsymbol{\theta})$ ，得到最优的 $\,\boldsymbol{\theta}\,$ 和 $q(Z)$
  
  问题：为什么最大化变分下界可以达到最优化不完全似然函数 $log\,p(X|\boldsymbol{\theta})$ 的目的。先看看变分下界的定义和性质
- 变分下界
  
  $g(\xi,x)$ 是 $f(x)$ 的变分下界，当且仅当
  1. $\forall\;\xi,x$ ，满足 $f(x)\geq g(\xi,x)$
  2. $\forall\;x_0, \exists\;\xi(x_0)$ 使得 $f(x_0)=g(\xi(x_0),x_0)$
  看上面的 $\mathcal{L}(q,\boldsymbol{\theta})$ ，满足
  1. $\forall\;q,\boldsymbol{\theta}$ ，都有 $log\,p(X|\boldsymbol{\theta})\geq\mathcal{L}(q,\boldsymbol{\theta})$
  2. $\forall\;\boldsymbol{\theta}_0, \exists\;q(\boldsymbol{\theta}_0)$ 使得 $log\,p(X|\boldsymbol{\theta}_0)=\mathcal{L}(q(\boldsymbol{\theta}_0)),\boldsymbol{\theta}_0)$ ，此时就是 $KL(q||p)$ 等于0的情况， $q(\boldsymbol{\theta}_0))=p(Z|X,\boldsymbol{\theta}_0)$
  因此它是一个变分下界
- EM算法
  
  E步：计算 $q(Z)$ ， $q(Z)=p(Z|X,\boldsymbol{\theta}))$ ，这其实是变分下界的第二条，对应当前的参数 $\boldsymbol{\theta})$ 找到一个 $q$ 使得不完全似然函数等于变分下界。正好当 $KL$ 散度为0时，可以找到
  
  M步：更新参数 $\boldsymbol{\theta}$ ，在E步更新 $q(Z)$ 后，此时 $log\,p(X|\boldsymbol{\theta})=\mathcal{L}(q,\boldsymbol{\theta})$ ，此时最大化不完全似然函数就等于最大化变分下界。
  
  可以看到 $\displaystyle\mathcal{L}(q,\boldsymbol{\theta})=\int{q(Z)log\;q(Z)\mathrm{d}Z+\int q(Z)p(X,Z|\boldsymbol{\theta}})\mathrm{d}Z$ ，而第一项是与参数无关，所以可
  
  以直接去除。这样就得到 $\boldsymbol{\theta}=arg\,max_\boldsymbol{\theta}\;\mathbb{E}_q\;p(X,Z|\boldsymbol{\theta})$
  
  同时可以看到求期望的项 $p(X,Z|\boldsymbol{\theta})$ 就是完全似然函数，对隐变量 $Z$ 求期望。这样就可以理解期望最
  
  大算法的字面含义了。
  
  依次循环执行，直至收敛。可以证明 $\mathcal{L}(q,\boldsymbol{\theta})$ 的值在迭代过程中是单调递增的。因为在第k-1次迭代中，
  
  E步： $\mathcal{L}(q_{k-1},\boldsymbol{\theta}_{k-2})\geq\mathcal{L}(q_{k-2},\boldsymbol{\theta}_{k-2})$
  
  M步： $\mathcal{L}(q_{k-1},\boldsymbol{\theta}_{k-1})\geq\mathcal{L}(q_{k-1},\boldsymbol{\theta}_{k-2})$

三、两种形式的隐变量

离散型隐变量
- $x_i$ 的边缘分布， $p(x_i|\theta)=\displaystyle\sum^K_{k=1}p(x_i|k,\theta)p(z_i=k|\theta)$
- E步： $\displaystyle{q(z_i=k)=p(z_i=k|x_i,\theta)=\frac{p(x_i|k,\theta)p(z_i=k|\theta)}{\displaystyle\sum^K_{l=1}p(x_i|l,\theta)p(z_i=l|\theta)}}$
- M步： $\mathbb{E}_q\;p(X,Z|\theta)=\displaystyle\sum^n_{i=1}\mathbb{E_{z_i}}log\;p(x_i,z_i|\theta)=\displaystyle\sum^n_{i=1}\sum^K_{k=1}q(z_i=k)logp(x_i,k|\theta)$
- 注意，这里都写成了单个对象 $x_i$ 的形式，因为将 $p(X|\theta)$ 进行对数化之后就变成了 $log\;p(x_i|\theta)$ 的和
连续型隐变量
- 所有步骤同上，只需要将对 $z_i$ 的求和改成积分就行
- 课中提到连续型隐变量可以用于表征学习（representation learning），这个还不是太理解

难点
- 存在高维离散型隐变量
- 既有离散型，又有连续型隐变量
- 连续型隐变量的先验分布不是共轭分布，会导致E步难以求解
- 解决办法：变分贝叶斯

四、Word2vec模型

简单理解Skip-Gram模型，参考知乎上的一个回答

常规方法

$\displaystyle p(y|x,\theta)=\frac{exp(In(x)^TOut(y))}{\sum_{y'}exp(In(x)^TOut(y'))}$

根据极大似然估计，就是要求 $\arg max_\theta P(Y|X,\theta) , \theta=\{In,Out\}$

如果词典里的词为 $V$ ，那对每个词 $x$ 而言的时间复杂度就是 $O(V)$
Hierarchical Soft-max
1. 构建一个叶子节点数为 $V$ 的哈夫曼树
2. 定义 $Path(y)$ 为从根节点到叶子结点上的路径上的节点序列，不包括叶子结点
3. 每个非叶子结点都对应了有个向量，维度为词向量相同
目的仍然是计算 $y$ 的出现概率，现在的计算方式是，从哈夫曼树的根节点开始随机选择左边还是右边进入子树，将词向量与节点上向量进行內积并通过soft-max函数计算概率，来确定往左还是往右。如果总是假设向左的概率为 $\sigma(In(x)^TOut(c))，\displaystyle \sigma(x)=\frac{1}{1+e^{-x}}$ ， $c$ 为到 $y$ 路径上的一个非叶子节点。那往右的概率就等于 $1-\sigma(In(x)^TOut(c))=\sigma(-In(x)^TOut(c))$

这样就像课程中所设置的，定义 $d_{c,y}$ 为从 $c$ 到 $y$ 的方向，而且
$d_{c,y}= \begin{cases} +1 & \quad \text{if }y\text{位于左子树}\\ -1 & \quad \text{if }y\text{位于右子树}\\ \end{cases}$
这样， $\displaystyle p(y|x,\theta)=\displaystyle\prod_{c\in Path(y)}\sigma(In(x)^TOut(c))$

常规方法计算 $\;y\;$ 的概率时，其分母需要计算 $V$ 个项，但在Hierarchical Soft-max下只需要计算至多 $O(log\;V)$
Word Ambiguity（词语歧义）与隐变量模型
- 定义隐变量 $z_i$ 代表词 $x_i$ 的某个含义
- 词向量由 $In(x_i)$ 变成了 $In(x_i,z_i)$
- $y_i$ 的概率就为 $p(y_i|x_i,z_i,\theta)=\displaystyle\prod_{c\in Path(y)}\sigma(d_{c,y_i}In(x_i,z_i)^TOut(c))$
- 完全似然函数 $p(y_i,z_i|x_i,\theta)=p(y_i|x_i,z_i,\theta)p(z_i|x_i)$ ， $z_i$ 的先验分布，对于无信息先验的情况，可以假设先验分布为均匀分布，即 $\displaystyle p(z_i|x_i)=\frac{1}{K(x_i)}$
- 因为是未知的，因此可以使用EM算法来求解
  - E步： $\displaystyle p(z_i=k|x_i,y_i,\theta)=\frac{p(y_i|x_i,z_i,\theta)p(z_i|x_i)}{\sum^{K(x_i)}_{l=1} p(y_i|x_i,l,\theta)p(z_i=l|x_i)}$ 。这样就可以知道目标词的各个含义的概率
  - M步： $\arg max_\theta\;\mathbb{E}_zlog\;p(Y|Z,X,\theta)P(Z|X)$ ，参数 $\theta=\{In(x,c),Out(y)\}$
  - 但是每一次迭代，都要把所有的 $z_i$ 的后验概率计算一遍
Large Scale EM
- 在M步，不再求最大值，只做一步的随机梯度下降
  
  公式
  $\begin{equation}\begin{split}\nabla_\theta\mathbb{E}_Zlog\;p(Y|Z,X,\theta)p(Z|X)&=\nabla_\theta\mathbb{E}_Z\displaystyle\sum^n_{i=1}(log\;p(y_i|z_i,x_i,\theta)+log\;p(z_i|x_i))\\&=\displaystyle\sum^n_{i=1}\mathbb{E}_{z_i}(\nabla_\theta p(y_i|z_i,x_i,\theta)+\nabla_\theta log\;p(z_i|x_i))\\&=\displaystyle\sum^n_{i=1}\mathbb{E}_{z_i}\nabla_\theta p(y_i|z_i,x_i,\theta)\end{split}\end{equation}$
  
  $\displaystyle\sum^n_{i=1}\mathbb{E}_{z_i}\nabla_\theta p(y_i|z_i,x_i,\theta)=\displaystyle n\sum^{K(x_i)}_{j=1}p(z_i=k|x_i,y_i,\theta)\nabla_\theta p(y_i|z_i,x_i,\theta)$
  
  $\theta_{new}=\theta_{old}+\alpha_i\displaystyle n\sum^{K(x_i)}_{j=1}p(z_i=k|x_i,y_i,\theta)\nabla_\theta p(y_i|z_i,x_i,\theta)$
- 这里用到了随机梯度下降,在EM算法的每次迭代中,只需要一个样本,极大增加计算效率。随机梯度下降会在下次的《随机优化》中有讲

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

[DeepBayes2018]Day 1, lecture 3. Models with latent variables and EM-algorithm

隐变量模型

1. KL散度（Kullback-Leibler divergence, KL divergence）

2. 混合高斯分布

三、两种形式的隐变量

四、Word2vec模型

推荐阅读更多精彩内容