900字范文 > PRML第八章读书笔记——Graphical Models 生成式模型/超先验/层次贝叶斯模型 d-分

PRML第八章读书笔记——Graphical Models 生成式模型/超先验/层次贝叶斯模型 d-分

时间：2023-09-09 02:05:11

（终于读到概率图了，从这一章开始应该算是PRML的精华内容了。过于基础的东西就不写了，主要写自己不会的）

8.1 Bayesian NetworksP365 祖先采样法ancestral samplingP365 生成式模型generative modelsP366 离散变量P370 线性高斯模型P372 超先验hyperprior与层次贝叶斯模型hierarchical Bayesian model8.2 Conditional IndependenceP378 d-分离 d-seperationP380 朴素贝叶斯P381 有向分解directed factorizationP382 马尔可夫毯Markov blanket8.3 Markov Random FieldsP384 独立性P384 无向图的马尔可夫毯P385 最大团maximal cliques与势函数P390 有向图转无向图P392 D图（D map, dependency map）、I图（I map, independence map)、完美图（perfect map）、链图（chain graphs）8.4 Inference in Graphical ModelsP396 变量消去P395 链推断P398 树tree和多树polytreeP399 因子图factor graphP402 和积算法The sum-product algorithmP411 最大和算法The max-sum algorithm与反向跟踪back-trackingP416 带环图的推断——联合树算法junction tree algorithm和循环置信传播loopy belief propagationP418 学习图结构

所有的概率推断和学习，都是概率加法法则和乘法法则（回顾第一章）的运用

贝叶斯网络 -> 有向图模型

马尔科夫随机场 -> 无向图模型

因子图：能把有向图和无向图都转化成的一个表示形式。

概率图的一个优点是能减少参数，构建分布的复杂度在全连接图和完全独立节点的两种情况之间

8.1 Bayesian Networks

有向无环图directed acyclic graphs(DAGS)

贝叶斯线性回归示例

P365 祖先采样法ancestral sampling

有向图中根据拓扑顺序采样。为了从边缘分布中采样，可以用祖先采样法求取结点值，并扔掉其他结点值。

P365 生成式模型generative models

图模型描述了生成观测数据的一种因果关系，因此这种模型叫做生成式模型。例如图片的生成过程

线性回归不是生成式模型，因为没有建模p(x)p(x)p(x)

隐变量本身可以没有物理含义，仅仅用来从简单成分构建复杂概率分布

P366 离散变量

省参数的几种方式：

用少量边图代替全连接图参数共享（sharing，参数捆扎typeing）

对条件概率使用参数化模型。例如用逻辑回归代替所有情况的指数种组合

P370 线性高斯模型

其中pai\text{pa}_ipai表示xix_ixi的父节点

这里x=(x1,…,xD)T\bm x=(x_1,\dots,x_D)^Tx=(x1,…,xD)T，const\text{const}const是与x\bm xx无关的项。注意上式是x\bm xx的二次函数，所以p(x)p(\bm x)p(x)是多维高斯分布。易得

其中ϵ\bm \epsilonϵ是标准多维高斯分布

（感觉这里iii必须不能在jjj的拓扑排序后面，否则ϵj\epsilon_jϵj和xix_ixi不独立）

如果节点表示高维高斯分布的变量，则条件分布形式为

可以证明联合分布仍然是高斯分布

P372 超先验hyperprior与层次贝叶斯模型hierarchical Bayesian model

高斯变量xxx的均值μ\muμ的共轭先验是μ\muμ的高斯分布。μ\muμ上的概率分布的参数是控制先验分布的参数，所以可以看作是超参数。超参数本身未知，又可以引入超参数上的先验分布，被称为超先验hyperprior，它仍然是高斯分布。这种构造方法可以扩展到任意层次（套娃），这就是层次贝叶斯模型hierarchical Bayesian model

8.2 Conditional Independence

在给定ccc的条件下，a,ba,ba,b独立，记为a⊥⁣ ⁣ ⁣⊥b∣ca\perp \!\!\! \perp b|ca⊥⊥b∣c，形式化为

也可等价写成

P378 d-分离 d-seperation

A,B,CA,B,CA,B,C是任意不相交的结点集合，考虑A,BA,BA,B是否关于CCC条件独立

考虑从AAA到BBB的所有路径，路径被阻塞当且仅当路径上的某个结点满足下面两条性质之一

以头尾或尾尾的方式交汇，且该结点在CCC中以头头方式交汇，且该结点和后继都不在CCC中

如果所有路径都堵塞，则A⊥⁣ ⁣ ⁣⊥B∣CA\perp \!\!\! \perp B|CA⊥⊥B∣C

这种判断框架就是d-分离

P380 朴素贝叶斯

是一个生成模型。假设观测变量x=(x1,…,xD)T\bm x=(x_1, \dots, x_D)^Tx=(x1,…,xD)T，进行KKK分类，采用one-hot编码z\bm zz表示类别。定义生成模型p(z∣μ)p(\bm z | \bm \mu)p(z∣μ)，其中μk\mu_kμk是第kkk类的先验概率。引入p(x∣z)p(\bm x|\bm z)p(x∣z)

朴素贝叶斯naive Bayes之所以naive，是因为假设x1,…,xDx_1, \dots, x_Dx1,…,xD在给定z\bm zz的条件下独立。而p(x)p(\bm x)p(x)本身则不能分解

P381 有向分解directed factorization

把有向图看作是滤波器。如果一个概率分布ppp，能用有向图的方式进行分解，则通过了该滤波器。通过的子集记为DF\mathcal D\mathcal FDF。

还可以设计另一种滤波器，当概率分布ppp满足了某个有向图所有可能的d-分离对应的条件独立性，d-分离定理指出，该子集仍然是DF\mathcal D \mathcal FDF

注意如果，ppp有额外的独立性，则仍然能通过该滤波器

P382 马尔可夫毯Markov blanket

分子分母消掉和xi\bm x_ixi不相关的项，剩下的包括xi\bm x_ixi的子结点、父结点、子结点的其他父结点（co-parents）。这些点组成的集合称为xi\bm x_ixi的马尔可夫毯Markov blanket。这也是分类xi\bm x_ixi和其他结点的最小集合

8.3 Markov Random Fields

也叫做Markov网络，或无向概率图

P384 独立性

如果从集合AAA到集合BBB没有一条不经过集合CCC的路径，那么A⊥⁣ ⁣ ⁣⊥B∣CA \perp \!\!\! \perp B|CA⊥⊥B∣C

在这样的独立性要求下，无向图模型的形式化是可以推出的

P384 无向图的马尔可夫毯

无向图中xix_ixi的马尔可夫毯是xix_ixi的所有邻居结点子集，这比有向图的定义要简单。

P385 最大团maximal cliques与势函数

团cliques是结点子集，使子集内每个结点相连；图中不能再扩张的结点子集，就是最大团maximal cliques。有向图是在最大团CCC的势函数的乘积上定义的。Hammersley-Clifford定理指出，这种定义方法和独立性的要求是等价的！

为了让势函数ψ\psiψ严格为正，通常定义一个能量函数，满足

这种指数表示被称之为玻尔兹曼分布Boltzmann distribution，（原来玻尔兹曼机从这来的）

可以把势函数看作一种度量，表明局部变量的哪种配置优于其他配置。具有相对高概率的全局配置对于各个团的势函数的影响进行了很好的平衡。用这种思路，书中给出了一个去噪算法的实例，CVMLI也给出了这个例子。这里不写了

P390 有向图转无向图

对于线性依赖关系，直接转就行

让两者对应的方法为

注意，这样转换完之后配分函数Z=1Z=1Z=1，很方便。

考虑更一般的情况，为了能实现转换，有向图中的条件分布项必须在一个最大团内。

如果每个条件分布中只有一个父结点，那么直接把有向边改成无向边即可。

如果一项条件分布中有多个父结点，那么需要进行道德化moralization，在父结点之间添加边。这样得到的图称为道德图moral graph. 如图所示

然后让每项有向图中的条件分布放到相应的最大团中。这样，仍然有Z=1Z=1Z=1.

注意，对于多个父结点，因为无向图中他们在一个最大团里，但有向图中的在给定子节点情况下，父结点之间可能存在的条件独立性消失了。也即，转换之后的无向图对结点见独立性的要求变松了。当然，这种转换方式已经尽可能地保留了独立性

从无向图转有向图很少见，而且配分函数很难处理

P392 D图（D map, dependency map）、I图（I map, independence map)、完美图（perfect map）、链图（chain graphs）

如果一个概率分布中所有条件独立性质，都能通过一个图反映出来，那么这个图被称之为概率分布的D图。

一张完全不连接的图是任意分布的平凡D图

如果一个图的每个条件独立性都能由一个具体的分布满足，那么这个图被称之为条件分布的I图。

一张全连接图是任意分布的平凡I图

即是I图也是D图的就是完美图

不同分布，是否存在有向完美图或无向完美图，是不一定的，关系如图

这里给出有向图和无向图不能转换的各一个例子

将有向图和无向图结合起来，叫做链图chain graphs，显然有向图和无向图都是链图的special case。但是仍然存在分布，没有链图的完美图与之对应

8.4 Inference in Graphical Models

图中一些结点已知，希望计算一个或多个其他结点的后验概率。这里先关注精确推断，第十章会讨论近似推断

P396 变量消去

利用图中的条件独立性，重新调整图中的加和顺序，通过乘法分配律，使变量不断消去，加快计算效率。（这其实是一种动态规划）

如果图是全连接的，那么则必须对整张图计算，没有条件独立性可以用。

P395 链推断

对于链式模型，如果是单项有向图，可以转成无向图

对一个结点求边缘分布

调整加和顺序，可以写成

通过运用乘法分配律，可以看到左侧计算量为3次，右侧只有2次

μα\mu_\alphaμα可以动态规划进行计算

μβ\mu_\betaμβ类似. （μα,μβ\mu_\alpha, \mu_\betaμα,μβ都可以看作是信息messages）

这样的结构称之为马尔科夫链

对于配分函数ZZZ，可以利用公式（8.52）把所有的p(xn)p(x_n)p(xn)都算出来，然后加起来

如果链长为NNN，每个结点状态数为KKK，则上述求边缘分布的复杂度为O(NK2)\mathcal O(NK^2)O(NK2)，比暴力枚举的复杂度（关于KKK的指数次）低太多了

如果想求所有变量的边缘分布，则可以先把所有的μα,μβ\mu_\alpha, \mu_\betaμα,μβ都算出来，配分函数随便找一个变量算。这样复杂度仍然是O(NK2)\mathcal O(NK^2)O(NK2)如果某个结点已知值为x^n\hat x_nx^n，则该结点可以不用求和，只计算观测值。可以想象成把该结点有关的势函数乘上一个因子I(xn,x^n)I(x_n, \hat x_n)I(xn,x^n)，该式只有xn=x^nx_n=\hat x_nxn=x^n时取1，否则取0如果想计算两个相邻结点的联合分布，则采用

在已经观测到一些结点的情况下。如果想学习势函数中的参数，可以采用EM算法。可以证明，以任意观测数据为条件，团的局部联合分布恰好是EM算法中E步所需要的

P398 树tree和多树polytree

树中每两个节点只有一条路径相连

有向图的树中每个结点只有一个父结点

多树polytree则不然，这样的树会有超过一个结点没有父结点。多树在转无向图时会引入环

P399 因子图factor graph

有向图和无向图都能表示成一堆因子的乘积

有向图和无向图都是因子图的特例

因子图都是二分图（因子结点factor nodes和变量结点variable nodes）

一张有向图或无向图，可能对应多张不同结构的因子图。如图

有向或无向树模型转因子图仍然是树结构。多树在转因子图时，和带环的无向图不同，也可以写成不带环的树结构，如图所示

实际上，就算是原图带环，转因子图，仍然可以是不带环的树结构

因子图的表达更加具体，例如下图（b）和（c）两张因子图，转无向图时都能转成（a）。（注意这里是因子图转无向图，而不是无向图转因子图；如果是无向图转因子图，存在某些（a）使（c）无法表达）

P402 和积算法The sum-product algorithm

关于和积算法，之前写过一篇博客，可以对照看：置信传播（Belief Propagation）与链式有向图模型前向后向算法——CVMLI Prince读书随笔第11章

置信传播是和积算法在有向无环图的一种具体形式。

考虑树状的因子图（有向图和无向图都可以写成树状的因子图）

ne(x)\text{ne}(x)ne(x)是xxx的邻居结点，XsX_sXs是xxx通过fsf_sfs相连的子树结点集合。FsF_sFs是和fsf_sfs有关的子树中所有因子项乘积。因为

从而

这里引入

可以看作是从fsf_sfs传信息给xxx。对于FsF_sFs，可以把fsf_sfs因子项单独拆出来，得到

其中GiG_iGi是和结点xix_ixi有关的子树所有项的集合。代入得到

这里ne(fs)\textbf{ne}(f_s)ne(fs)是fsf_sfs的邻居结点集合。我们定义了

从而

注意，如果变量结点只有两个邻居，则直接把信息往前传即可，没有额外计算。在计算时，把xxx当作根，从叶结点不断往上算。如果一个叶结点是变量结点，那么直接初始化

如果是因子结点，则初始化为

如图所示

如果想要计算所有变量结点的边缘分布，比较高效的办法是任选一个结点作为根，从叶结点向上传递信息；根结点收到所有信息后，又可以向下传递，从而遍历每个结点的每个方向。这样必须计算的信息数量是图中边的两倍，总计算量是计算一个边缘分布的两倍如果要找某个因子的结点的边缘分布，易得

xix_ixi的边缘分布又可以写成

如果某些结点已知值为v^\hat vv^，未知节点集合为h\bm hh，则和马尔科夫链类似，设计一个因子I(v,v^)I(v,\hat v)I(v,v^)，当v=v^v=\hat vv=v^时取1，否则取0。这个项要乘到所有和vvv相关的因子上。这个乘积对应p(h,v=v^)p(\bm h, \bm v = \hat \bm v)p(h,v=v^)，是p(h∣v=v^)p(\bm h|\bm v = \hat \bm v)p(h∣v=v^)的一个未归一化版本。从而归一化系数可以通过找一个局部计算得出来如果两个变量xa,xbx_a,x_bxa,xb不在一个因子图中，如果是离散变量的话，则可以先计算p(xb)p(x_b)p(xb)，再计算p(xa∣xb)p(x_a|x_b)p(xa∣xb)

P411 最大和算法The max-sum algorithm与反向跟踪back-tracking

找最大概率对应的变量和概率

与和积算法类似，也是构造一棵树，从叶结点算到根节点，不过算的时候把∑\sum∑换成max⁡\maxmax。注意这时候信息没有反向从根到叶结点的传递。这种算法的原理是

实际计算中，小概率的乘积可能会出数值问题，可以取对数之后进行，分配性质仍然成立，因为

此时，具体的信息传播方法为

初始化为

在根节点的计算公式为

这样算完之后，根结点的xxx值通过公式（8.98）算出来，其他结点的值，可以通过反向跟踪back-tracking的方式找到。

以马尔科夫链为例，在信息从叶结点向根节点传播时，需要记录一个ϕ(xn)\phi(x_n)ϕ(xn)，表示给定xnx_nxn的情况下，对应最大的xn=1x_{n=1}xn=1。

如果一个因子有多个结点连接，则ϕ(xn)\phi(x_n)ϕ(xn)输出多维度值。马尔科夫链的反向跟踪过程如图所示

这种算法在隐马尔可夫模型当中，被称为Viterbi算法（原来Viterbi算法是反向追踪的一个特例）

如果有已经观测到的变量，则仍然可以引入恒等函数III的方式进行处理

P416 带环图的推断——联合树算法junction tree algorithm和循环置信传播loopy belief propagation

简单介绍两种方法，不细搞

联合树算法。将无向图三角化，然后构造出联合树，树的结点对应三角化图的最大团。边将具有相同变量的团连在一起。构造一棵最大生成树……联合树对于任意图都是精确、高效的，对于一个给定的图，通常不存在代价更低的算法。循环置信传播是带环图的一种近似推断，仍然用和积算法，但是因为图中带环，这个过程会一直进行下去。如果一个结点aaa自上次向bbb发送信息后，收到了其他结点新的信息，则会向bbb发送一个信息挂起（message pending）。只有挂起的信息需要被传送。对于大部分应用，该方法会在一个一个合理的时间内收敛。当运行结束后，边缘概率可以通过结点最近收到的信息进行累积。