马尔可夫性

本章最重要的概念就是马尔可夫性. 马尔可夫性是指变量的状态只与其前一个时刻的状态有关, 而与其他的状态无关, 称为 “无后效性” . 这里可以作一个拓展, 即指变量的状态只与其周围的变量状态有关, 这里的 ‘周围’ 既可以是时间也可以是空间.

隐马尔可夫模型

隐马尔可夫模型包括两条链, 一条是由可观测的状态组成的, 一条是由不可观测的状态 (隐变量) 组成的. 那么究竟是什么呢, 我们举个例子.

假设每天的天气只与前一天的天气有关. 比如今天如果是晴天, 那么明天有的可能还是晴天, 有的可能是阴天. 如果今天是阴天, 那么明天有的可能是晴天, 有的可能还是阴天. 一天只能有一种天气, 所以我们每天都能观测到一种天气, 这是可观测的. 比如经过一个星期, 我们得到了天气关于时间的一个序列

1234567

现在假设你有个朋友在国外, 你想要知道他们那边的天气, 但是你只了解你的朋友是在家里还是外出, 并不知道具体天气如何, 而且你还知道假如是晴天, 那么他有的可能出去, 有的可能呆在家, 如果是阴天, 那么有的可能出去, 有的可能呆在家. 假如又过了一个星期, 虽然这个星期里的天气是确实存在的, 可是你并不知道, 这就是那条由隐变量组成的 “隐链” . 你的朋友的状态和天气有关, 你也了解你的朋友的状态, 那么朋友这一个星期里的状态也构成一天链, 这就是由可观测的状态组成的 “明链” .

1234567
出去在家在家在家在家出去

明链和暗链结合在一起, 就有了隐马尔可夫模型.

以上面的例子来说明.就是第天的天气,是你朋友第天的活动. 而状态转移概率

输出观测概率

初始状态概率

产生观测序列的过程书上已经有了, 这里不再详细叙述.

当然, 一个确定的模型并不一定能产生确定的结果, 上面的例子只是一种可能结果, 还有其他很多种结果, 出现的概率各不相同.

而隐马尔可夫模型的三个基本问题我们也用例子来说一下:

  • 即我们得到了朋友这一个星期的状态, 那么给定模型, 计算出出现这个状态的概率.
  • 给定模型以及朋友这个星期的状态, 那么推测出这个星期朋友那里的天气是怎样的.
  • 给出朋友这个星期的状态, 如何调整参数才能使朋友出现这样的状态的可能性最大.

马尔可夫随机场

Hammersley-Clifford 定理

 定理指出概率无向图模型的联合概率可以分解为定义在极大团上的势函数的乘积. 即

定理充分性的证明在西瓜书中其实已经给出. (即西瓜书中所说的简单的验证)

极大团

若在一个团中加入另外任何一个节点都不再写成团, 则称该团为 “极大团” (maximal); 换言之, 极大团就是不能被其他团所包含的团.

换句话讲就是, 找不到这个团之外的一个结点和这个团中所有结点之间都有边, 那么这个团就是极大团. 可以利用反证法证明: 如果极大团被其他团所包含, 那么根据团的定义, 这个极大团之外还会有一个结点 (该结点在这个极大团之外却在那个包含这个极大团的团之内) 与团中所有节点都有边, 违背了极大团的定义, 因此不成立.

势函数

势函数从何而来, 为什么是这样定义? 相信你一开始也和我一脸懵逼. 现在我试着将我所理解的势函数尽我所能表达出来.

势函数本身用来刻画某种 ‘偏好’ . 即你依靠经验认为结点之间应该有某种关系. 比如说你如果认为结点之间的值应该要差不多, 那么当它们的值确实差不多时, 你应该给出更高的分数, 如果他们的值相差较大, 你就应该给出更低的分数. 依靠这样的准则, 就可以构造出一个势函数, 来实现你的给分策略. 势函数的形式不是唯一的, 只不过常用指数函数来定义势函数. 使用指数函数的目的是为了满足非负性 (概率总不可能是负的吧) .

至于势函数和后面提到的特征函数到底有什么根本上的区别… 好吧我也不清楚.

规范化因子

其中是规范化因子, 那么它究竟起到什么作用呢? 其实它起到的作用就是保证, 即保证我们算出的是一个 “概率” . 而概率具有的性质就是所有可能结果的概率和为.

**马尔可夫性

事实上, 这些 ‘**马尔可夫性’ 成立的前提都在于某个变量只与其相邻变量有关.

全局马尔可夫性

简单的来说, 就是两 ‘团’ 变量被中间的 ‘变量墙’ 隔开, 因此具有独立性.

局部马尔可夫性

可以形象的认为像一圈围墙将包围了起来, 这堵墙存在时 (变量给定时) , 会将与外界分离 (即独立于外界) .

这里说明一个可能不太清楚的点.

为图的结点集,为结点在图上的邻接结点,, 有.

这里的中的应该是集合去除集合. 所有的运算都是集合去掉其中的集合部分.

成对马尔可夫性

只要两个变量不在同一条边上, 那么就可以将这两个变量完全用其他结点隔离开, 最极端的情况就是把除了这两个变量的节点都当成 ‘墙’ , 这两个变量的周围都是 ‘墙’ , 被这堵墙隔开后, 它们就具有独立性. 这就是成对马尔可夫性. 如果这两个变量在同一条边上, 那么无论是多厚的墙, 两个变量间还是有一条绳子 (边) 连着, 他们仍然不会分离, 不具有成对马尔可夫性.

条件随机场

条件随机场与隐马尔可夫模型、马尔可夫随机场的最主要区别在于条件随机场是判别式模型, 而隐马尔可夫模型和马尔科夫随机场是生成式模型. 顾名思义, 条件随机场就是有 ‘条件’ 的 马尔可夫 ‘随机场’ . 同样基于最大团定义了势函数, 只不过还多引入了一个特征函数.

条件随机场的结构是任意的. 但是一般我们会考虑 “链式条件随机场” ().

特征函数

特征函数刻画了相邻变量之间的相关关系以及观测序列对它们的影响.

学习与推断

变量消去

变量消去一般用来求边缘概率 (可以理解为求和的过程可以一个个的 ‘消去’ 变量, 故为变量消去). 如果进行暴力求和来求边缘概率, 那么时间复杂度会达到可怕的, 其中是变量可能的取值数,是要消去变量的总数. 这个复杂度可以说是基本上不可能进行求解的, 但好在我们有更快的算法, 那就是动态规划.

动态规划

上式可以等价的表达为

注意一个问题, 这里面加不加括号都是一样的, 什么意思呢? 其实就是

首先我们从最后一个开始算

可以看到这只与有关, 即这是一个关于的函数, 我们简写为那么我们再寻找从何而来

这里就有了(前面的是对求和), 因此就可以结合起来

这是一个只与有关的函数, 同样简写为.

我们按照这样的方法一个个去向前推进, 即每次寻找未提供的变量 (就是没有说这个变量具体的值, 又或者说目前的函数可以表达为只与这个变量有关的函数) 在哪 (即下的变量), 然后互相结合递推, 注意到, 可能有两个未提供的变量同时与一个有关, 比如同时与有关, 于是分别求出, 再与结合.

这样算法的复杂度就降为了.

但是就是有一个缺点, 再次计算另一个边缘分布时有些变量又要求一遍, 造成冗余计算.

信念传播

信念传播其实就是基于变量消去做了一些改进, 可以理解为存储了中间变量 (比如), 这样计算的时候直接使用就行了.

近似推断

我们的目标是要计算函数在概率密度函数下的期望

由于积分比较困难, 所以可以根据采样作无偏估计

但是如果较为复杂, 直接采样可能比较复杂, 因此就有了其他间接采样的方法.就是概率图模型中最常用的方法.

MCMC 采样

 方法是构造一条马尔可夫链, 此马尔科夫链的平稳分布正是. 也就是说, 运行马尔科夫链一段时间后 (即收敛到平稳分布), 此时产出的样本近似服从分布.

具体来说,有一个代表算法.

Metropolis-Hastings

令转移核为

其中分别称为建议分布和接受分布. 建议分布是一个你自由选择的分布, 一般来说要比较容易抽样 (比如均匀分布) . 接受分布

因此可以写为

假设在时刻处于状态, 即, 那么有

. 按照建议分布 $\,q(x, x’)\,$ 抽取一个候选状态 $\,x’\,$

. 按照接受分布决定是否接受. 接受则产生下一个样本, 拒绝就让. 同时, 然后回退到步骤.

这个抽取样本过程等价于直接按照抽取.

每次抽样时刻都会增加. 那么当经过一段时间后, 马尔可夫链可以达到平稳分布, 而正是其平稳分布. 这是因为对于分布来说, 这个马尔可夫链是可逆的, 而可逆马尔科夫链是平稳分布的充分条件. 达到平稳分布后, 其后产生的样本即满足分布, 此时我们就能轻松抽样了.

单变量 Metropolis-Hastings 算法

单变量算法与传统算法的区别就在于单变量算法是每一次样本产生是对多元变量的每一分量依次抽样, 从而实现对整个多元变量的一次抽样, 这大概就是 ‘单变量’算法名字的由来.

吉布斯采样

吉布斯采样是算法的特例, 更准确的说应该是单变量算法的特例. 它将建议分布设置成, 即

 即为除了外的其他分量的集合.

这样就可以让接受概率, 从而大大提高采样效率.

变分推断

EM 算法

 算法在节就已经作了一个介绍, 其分为步和步. 对于某时刻的来说, 可以根据与已观测变量计算隐变量的分布, 并且还要计算出一个与有关的函数(以便后续步计算期望) . 然后步即令新的参数能够最大化对数似然

这个式子其实是对数似然函数在分布下的期望.

式 14.36 推导

根据

为了简化, 我们将简写为

代入可得

注意到

其中是一个向量,的一个分量,是除了以外的分量集合.

更一般的, 可以将拆分成互斥的分量集合, 然后像这样嵌套积分.

因此

为了表达更清晰, 这里的符号和西瓜书稍稍不同, 这里代表了对除了以外的分量积分, 西瓜书应该也是表达这个意思, 但是符号不太清晰.

同时由于没有关系, 所以提出积分

我们单独取后一项进行进一步分析

对于每一个来说, 有

由于没有关系, 于是可以提出积分

注意到也没有关系, 而且, 于是

事实上, 可以一直反复这种提取, 消去的过程, 最终得到

于是

我们只关心与有关的变量, 因此后面的项可以当作常量.

因此

(理解倒是不难, 可是这公式也太多了吧…写了我好长一段时间..公式是真的难写…)

式 14.40 推导

而又因为

于是

由于, 因此

话题模型

其实就是一个具体的模型, 理解了前面的内容这里应该也没什么问题. 当然这只是看懂, 如果要理解背后的原理, 就需要亿点点数学基础了.

最近看了 LDA 数学八卦, 感觉写的还是很不错的, 公式一遍遍细细的看, 是能够看懂的, 想要了解 LDA 的推荐看一看.


参考

网络资料

书籍

  • 《统计学习方法》李航