概率图模型

第14章 概率图模型(probabilistic model)

  • Page319: 马尔科夫网(Markov network)

    使用无向图表示变量间的相关关系的概率图模型。 概率图模型是一类用图来表达变量相关关系的概率模型。它以图为表示工具,最常见的是用一个结点表示一个或一组随机变量,结点之间的边表示变量间的概率相关关系,即『变量关系图』。根据边的性质不同,概率图模型可大致分为两类:第一类是使用有向无环图表示变量间的依赖关系,称为有向图模型或贝叶斯网;第二类是使用无向图表示变量间的相关关系,称为无向图模型或马尔科夫网。

  • Page319: 推断

    概率模型提供了一种描述框架,将学习任务归结于计算变量的概率分布。在概率模型中,利用已知变量推测未知变量的分布称为『推断』,其核心是如何基于可观测变量推测出未知变量的条件分布。

  • Page319: 隐马尔科夫模型(Hidden Markov Model)

    隐马尔科夫(HMM)模型是结构最简单的动态贝叶斯网,主要用于时序数据建模,在语音识别、自然语言处理等领域有广泛应用。

  • Page322: 马尔科夫随机场(Markov Random Field)

    马尔科夫随机场(MRF)是典型的马尔科夫网,一种著名的无向图模型。图中每个结点表示一个或一组变量,结点之间的边表示两个变量之间的依赖关系。

  • Page322: 势函数(potential functions)

    同因子。

  • Page322: 因子(factor)

    马尔科夫随机场有一组势函数,亦称『因子』,这是定义在变量子集上的非负实函数,主要用于定义概率分布函数。 对结点的一个子集,若任意两结点间都有边连接,则称该结点子集为一个『团』。在马尔科夫随机场中,多个变量之间的联合概率分布能基于团分解为多个因子的乘积,每个因子仅与一个团相关。

  • Page323: 全局马尔科夫性(global Markov property)

    在马尔科夫随机场中得到『条件独立性』需要借助『分离』的概念。若从结点集 A 中的结点到 B 中的结点都必须经过结点集 C 中的结点,则称结点集 A 和 B 被结点集 C 分离,C 称为『分离集』。 全局马尔科夫性就是指给定两个变量子集的分离集,则这两个变量子集条件独立。 也就是说,若令 A,B 和 C 对应的变量集分别为 XAX_AXBX_BXCX_C,则 XAX_AXBX_B 在给定 XCX_C 的条件下独立,记为:XAXBXCX_A \perp X_B \mid X_C

  • Page324: 局部马尔科夫性(local Markov property)

    由全局马尔科夫性得出的推论之一。给定某变量的邻接变量,则该变量条件独立于其他变量。 形式化地说,令 VV 为图的结点集,n(v)n(v) 为结点 vv 在图上的邻接结点,n(v)=n(v){v}n^*(v) = n(v) \cup \{v\},有 XvXVn(v)Xn(v)X_v \perp X_{V \setminus{n}^*(v)} \mid X_n(v). 注:\setminus 表示『非』

  • Page325: 成对马尔科夫性(pairwise Markov property)

    由全局马尔科夫性得出的推论之一。给定所有其他变量,两个非邻接变量条件独立。

    形式化地说,令图的结点集和边集分别为 VVEE,对图中的两个结点 uuvv,若 u,vE\langle u,v \rangle \notin E,则 XuXvXVu,vX_u \perp X_v \mid X_{V\setminus \langle u,v \rangle}. 注:\setminus 表示『非』

  • Page325: 马尔科夫毯(Markov blanket)

    某变量的所有邻接变量组成的集合称为该变量的马尔科夫毯。

  • Page325: 条件随机场(Conditional Random Field)

    一种判别式无向图模型。判别式模型对条件分布进行建模,可看作给定观测值的马尔科夫随机场,也可看作对率回归(常说的逻辑回归)的扩展。 条件随机场试图对多个变量在给定观测值后的条件概率进行建模。具体来说,若令 X={x1,x2,...,xn}X=\{x_1,x_2,...,x_n\} 为观测序列,y={y1,y2,...,yn}\mathrm{y} = \{y_1,y_2,...,y_n\} 为与之相应的标记序列,则条件随机场的目标是构建条件概率模型 P(yX)P(\mathrm{y}|X)

    标记变量 yy 可以是结构型变量,即其分量之间具有某种相关性。

    G=V,EG=\langle V,E \rangle 表示结点与标记变量 y\mathrm{y} 中元素一一对应的无向图,yv\mathit{y}_v 表示与结点 vv 对应的标记变量,n(v)n(v) 表示结点 vv 的邻接结点,若图 GG 的每个变量 yv\mathit{y}_v 都满足马尔科夫性,即: P(yx,yV{v})=P(yvx,yn(v))P(\mathit{y} \mid \mathrm{x}, \mathrm{y}_{V\setminus\{v\}}) = P(\mathit{y}_v \mid \mathrm{x}, \mathrm{y}_{n(v)})(y,x)(\mathrm{y}, \mathrm{x}) 构成一个条件随机场。

  • Page326: 链式条件随机场(chain-structured CRF)

    构成条件随机场的图 GG,理论上来说可具有任意结构,只要能表示标记变量之间的条件独立性关系即可。 但在现实应用中,尤其是对标记序列建模时,最常用的仍是链式结构,即:链式条件随机场(chain-structured CRF)

  • Page328: 边际分布(marginal distribution)

    边际分布是指对无关变量求和或积分后得到结果。 例如在马尔科夫网中,变量的联合分布被表示成极大团的势函数乘积,于是,给定参数 Θ\Theta 求解某个变量 xx 的分布,就变成对联合分布中其他变量进行积分的过程,这称为『边际化』(marginalization)。

  • Page328: 变量消去

    概率图模型的推断方法大致可以分为:精确推断方法和近似推断方法。 精确推断方法实质是一种动态规划算法,它利用图模型所描述的条件独立性来削减计算目标概率值所需的计算量。变量消去法是最直观的精确推断算法,也是构建其他精确推断算法的基础。 变量消去法通过利用乘法对加法的分配率,把多个变量的积的求和问题,转化为对部分变量交替进行求积与求和的问题。这种转化使得每次的求和与求积运算限制在局部,仅与部分变量有关,从而简化了运算。 它的一个明显的缺点是:若需计算多个边际分布,重复使用变量消去法将会造成大量的冗余计算。

  • Page330: 信念传播(340)(Belief Propagation)

    亦称 Sum-Product 算法,将变量消去法中的求和操作看作一个消息传递过程,较好地解决了求解多个边际分布时的重复计算问题。 信念传播算法最早由 Pearl 作为精确推断技术提出,后来衍生出多种近似推断算法。对一般的带环图,信念传播算法需在初始化、消息传递等环节进行调整,由此形成了迭代信念传播算法(Loopy Belief Propagation)。

  • Page331: MCMC(Markov Chain Monte Carlo)

    马尔科夫链蒙特卡洛方法,概率图模型中最常用的采样技术。 MCMC 方法先设法构造一条马尔科夫链,使其收敛至平稳分布恰为待估计参数的后验分布,然后通过这条马尔科夫链来产生符合后验分布的样本,并基于这些样本来进行估计。这里马尔科夫链转移概率的构造至关重要,不同的构造方法将产生不同的 MCMC 算法。

  • Page333: MH 算法(Metropolis-Hastings)

    MH(Metropolis-Hastings)算法是 MCMC 的重要代表。它基于『拒绝采样』来逼近平稳分布。算法每次根据上一轮采样结果获得候选样本,但这个候选样本会以一定概率被『拒绝』掉。

  • Page334: 变分推断(variational inference)

    变分推断通过使用已知简单分布来逼近需推断的复杂分布,并通过限制近似分布的类型,从而得到一种局部最优、但具有确定解的近似后验分布。 变分推断使用的近似分布须具有良好的数值性质,通常是基于连续型变量的概率密度函数来刻画的。

  • Page334: 盘式记法(plate notation)

    概率图模型一种简洁的表示方法。相互独立的、由相同机制生成的多个变量被放在一个方框(盘)内,并在方框中标出类似变量重复出现的个数 NN,方框可以嵌套。通常用阴影标注出已知的、能观察到的变量。在很多学习任务中,对属性变量使用盘式记法将使得图表示非常简洁。

  • Page335: KL 散度(414)(Kullback-Leibler divergence)

    亦称相对熵或信息散度,可用于度量两个概率分部之间的差异。给定两个概率分布 PPQQ,二者之间的 KL 散度定义为: KL(PQ)=p(x)logp(x)q(x)dxKL(P \parallel Q) = \int_{-\infty}^{\infty} p(x) \log \frac {p(x)}{q(x)}dx, 其中 p(x)p(x)q(x)q(x) 分别为 PPQQ 的概率密度函数。

  • Page337: 平均场(mean field)

使用变分法对隐变量进行推断,对隐变量 zjz_j 分布进行估计时,融合了 zjz_j 之外的其他 zijz_{i \ne j} 的信息,这是通过联合似然函数 lnp(x,z)\ln p(x,z)zjz_j 之外的隐变量分布上求期望的到的,称为平均场方法。

  • Page337: 话题模型(topic model)

    一族生成式有向图模型,主要用于处理离散型的数据(如文本集合),在信息检索、自然语言处理等领域有广泛应用。 话题表示一个概念,具体表示为一系列相关的词,以及它们在该概念下出现的概率。

  • Page337: 隐狄利克雷分配模型(Latent Dirichlet Allocation)

    隐狄利克雷分配模型(Latent Dirichlet Allocation,简称 LDA)是话题模型的典型代表。 现实任务中可通过统计文档中出现的词来获得词频向量,但通常并不知道这组文档谈论了哪些话题。LDA 从生成式模型的角度看待文档和话题。 具体来说,LDA 认为每篇文档包含多个话题,不妨用向量 ΘtRN\Theta_t \in \mathbb{R}^N 表示文档 tt 中所包含的每个话题的比例,Θt,k\Theta_{t,k} 即表示文档 tt 中包含话题 kk 的比例,进而通过下面的步骤由话题生成文档 tt

  • 根据参数为 α\alpha 的狄利克雷分布随机采样一个话题分布 Θt\Theta_t

  • 按如下步骤生成文档中的 NN 个词:

    • 根据 Θt\Theta_t 进行话题指派,得到文档 tt 中的词 nn 的话题 zt,nz_t,n

    • 根据指派的话题所对应的词频分布 βk\mathcal{\beta_k} 随机采样生成词。

  • Page340: 非参数化(non-parametric)法

    一般认为在一个统计推断问题中,如给定或者假定了总体分布的具体形式,只是其中含有若干个参数,要基于来自总体的样本对这些参数做出估计或者进行某种形式的假设检验,这类推断方法称为非参数化方法。非参数化是指参数的数目无须事先指定,是贝叶斯学习方法的重要发展。