[机器学习]概率图模型

本文档记录了《机器学习》第 14 章概率图模型相关内容

概率图模型

隐马尔科夫模型

生成式模型有向图模型参数

初始隐状态概率隐状态转移概率隐状态-输出观测概率基本问题

评估模型与观测序列的匹配程度：给定模型和观测序列，计算生成观测序列的概率。根据观测序列推断出隐状态：给定模型和观测序列，寻找最有可能的隐状态序列。模型参数训练：给定观测序列，调整模型使其最大化观测序列的概率。

马尔科夫随机场

生成式模型无向图

结点表示变量边表示依赖关系

势函数（因子）

定义在变量子集上的非负实函数，主要用于定义概率分布函数。

团/极大团

团：给定一个结点子集，其中任意两个结点之间都有边连接。极大团：一个团中加入另外任何一个结点都不再形成团，则称为极大团。

观测到变量 x={x1,x2...,xn} 的联合概率：

P(x)=1Z∏Q∈ψQ(xQ)

其中  为团的集合， ψ(Q) 为团 Q 对应的势函数。

可以寻找极大团集合∗降低上式复杂程度。

分离集

若从结点集 A 到结点集 B 中任意一个结点，都要经历结点集 C 中的结点，则称 A 和 B 被 C分离，C 即为分离集。

全局马尔科夫性：给定任意两个结点集 xA 和 xB 的分离集 xC ，则这两个结点集条件独立，记为 xA⊥xB|xC 。

证明很重要！见 P324

局部马尔科夫性：给定结点 v 的邻接结点集n(v)，总结点集为 V ，则有xv⊥xV−n(v)−v|xn(v)成对马尔科夫性：给定所有其他结点，对于图中任意两个结点 u 、v，如果两个结点之间没有边相连，则有 xu⊥xv|xV−u−v

势函数的常见定义

为了保证势函数的非负性，常引入指数函数： ψQ(xQ)=e−HQ(xQ) 其中 HQ(xQ)=∑u,v∈Q,u≠vαuvxuxv+∑v∈Qβvxv ， αuv 为一对结点间的关系， βv 为单结点的权重。

条件随机场

判别式模型：给定观测值 x 的马尔科夫随机场，标记变量y可以是结构性变量，即分量之间具有某种相关性。无向图

形式化定义

令 G=⟨V,E⟩ 表示结点与标记变量 y 中元素一一对应的无向图，yv表示与结点 v 对应的标记变量，n(v)表示结点 v 的邻接结点，若图G的每个变量 yv 都满足马尔科夫性，即

P(yv|x,yV−v)=P(yv|x,yn(v))

则 (y,x) 构成一个条件随机场。

条件概率（势函数+团）

链式 CRF

标记转移特征函数：相邻标记变量之间的相关关系以及观测序列对它们的影响

tj(yi+1,yi,x,i)

状态特征函数：观测序列对标记变量的影响

sk(yi,x,i)

条件概率：

P(y|x)=1Zexp(∑j∑i=1n−1λjtj(yi+1,yi,x,i)+∑k∑i=1nμksk(yi,x,i))

学习与推断

边际化与边际分布

边际化：给定参数，为了求解某个变量的分布，对联合分布中其它无关变量进行积分的过程。边际分布：对无关变量求和或积分后得到的分布。

精确推断

存在问题

计算复杂度随着极大团规模的增长呈指数增长。

变量消去

主要思想：利用图模型所描述的条件独立性来削减计算目标概率所需的计算量，本质是一种动态规划的算法。缺点：当需要计算多个边际分布时会产生重复计算。

信念传播（Belief Propagation）

主要思想：为了解决计算多个边际分布时的重复计算，将变量消去法中的操作看作消息传递的过程。每次消息传递操作仅与当前结点及其邻接结点直接相关，只有当一个结点接收到了它的所有邻接结点（不包含需要发送的结点？？？）之后才能向另一个结点发送消息。

形式化定义：

当前结点： xi 当前结点的邻接结点： n(xi) 结点之间（ xi 到 xj ）的消息： mij(xj)=∑xiψ(xi,xj)∏k∈{n(i)−j}mki(xi)

结点 xi 的边际分布：

P(xi)∝∏k∈n(i)mki(xi)

算法实现：

图中没有环，根结点需要人为指定

叶子结点 → 根结点：从所有叶子结点开始向根结点传递消息，直到根结点收到所有邻接结点的消息。根结点 → 叶子结点：根结点向叶子结点传递消息，直到所有叶子结点均收到消息。

近似推断

采样：通过随机化的方法完成近似。使用确定性近似完成近似推断。

随机化方法

MCMC——马尔科夫链蒙特卡罗采样

主要思想：直接计算或逼近目标值的期望，通过构造平稳分布为 p 的马尔科夫链来产生样本，并且基于大数定理，当样本数足够大的时候就能得到较高的近似精度。

马尔科夫链平稳条件

样本 x 在马尔科夫链中t时刻的分布： p(xt) 样本 x 转移到x′的（状态转移）概率： T(x′|x)

平稳条件：

p(xt)T(xt−1|xt)=p(xt−1)T(xt|xt−1) 算法过程：

构造一条马尔科夫链收敛到恰为待估计参数的后验分布对应的平稳分布（蒙特卡罗在有限时间内应该无法保证一定能满足约束条件吧？？？）通过平稳分布的马尔科夫链产生符合后验分布的样本基于所产生样本进行期望估计。

Metropolis-Hastings

主要思想：基于 MCMC，通过”拒绝采样“逼近平稳分布，每一轮采样的结果会以一定概率被拒绝。重要变量：

算法实现：

输入：用户给定的先验概率： Q(x∗|xt−1) 输出：采样的样本序列

算法：

init(x0)for t in range(1, MAX_T) dox_star = Q.sampling()u = uniform.sampling(1, 0) # 接收阈值if u <= A(x_star, x[t-1]):x[t] = x_star # 接受else:x[t] = x[t-1] # 拒绝end ifend forreturn x

吉布斯采样

主要思想：MH 的特例，马尔科夫链的平稳分布即为采样的目标分布 p(x) 。算法过程：

随机或以某种策略选取某变量 xi 。计算条件概率 p(xi|xi¯) ，其中 xi¯ 为不包含 xi 的采样序列。重新根据 p(xi|xi¯) 对 xi 采样并代替原有值。

确定化近似推理

变分推断

主要思想：使用已知的简单分布逼近需要推断的复杂分布，并且限制近似分布的类型，从而得到一个局部最优但具有确定解的近似后验分布。重要假设：复杂的目标变量可以拆解为一系列相互独立的多变量。形式化定义（P334）

目标多变量： z 互相独立的多变量：zi假设： q(z)=∏Mi=1qi(zi)

话题模型

生成式模型有向图主要用于处理离散型数据

形式化定义

话题： βk∈ℝN ， βk,n 表示话题 k 中词n的词频文档： wt∈ℝN ， wt,n 表示文档 t 中词n的词频话题分布（文档 t 中包含的每个话题的比例）：Θt∈ℝK， Θt,k 表示话题 k 在文档t中的比例生成文档 t ：

生成包含多个话题的文档：根据参数为α狄利克雷分布随机采样一个话题分布 Θt 生成文档中的 N 个词：

根据Θt进行话题指派，得到文档中词 n 对应的话题zt,n。根据话题 zt,n 对应的词频分布随机采样生成词。

LDA 隐狄利克雷模型

参数估计：给定文档集 W=w1,w2,...,wT ，通过极大似然估计寻找话题分布的参数 α 和话题词频模型的参数 η

LL(α,η)=∑t=1Tlnp(wt|α,η)

推断：模型参数 α 和 η 已知，根据词频推断文档集对应的话题结构

p(z,β,Θ|W,α,η)=p(W,z,β,Θ|α,η)p(W|α,η)