精确推断

申明：概率图模型基于R语言读书笔记

1、HMM（隐马尔可夫模型）

马尔可夫的模型态仅依赖于之前的状态，隐马尔可夫就是模型状态不能被直接观测到，存在一个观测变量。
卡尔曼滤波器就是隐马尔可夫模型的离散变量换成换成符合高斯分布（正态分布）的连续变量。

2、变量消解算法（VE）

推断：给定模型中变量子集的观测值后，计算其它变量子集的后验概率。
O记号表示计算时间的上界与括号中的函数成比例。

变量消解法的核心思想是当我们在消解模型变量时，可以只考虑与消解变量相关的节点对应的概率表达式，将这个变量消去的数据暂存，其实就是将这个节点消去的图暂存，这个图中与消去节点相关的节点概率分布是经过更新的，我们可以将这个结果暂存，在后续的推理中降低复杂度。
实例：

解释案例.png
在这个图中我们如果想求解D的边缘分布，就必须将前面三个节点逐一消解，这个计算复杂度是随节点的个数呈指数倍增长，但是通过将前面计算的中间结果保留，复杂度就大大的降低了，如果我们保留了C节点的边缘分布，计算D节点边缘分布的复杂度就从k的4次方变成k的2次方。
保留中间结果在公式中对应的就是含有各个变量的节点对应的条件概率分类消解，不要按照顺序消解。对于这个例子：
P(D)=SUMcP(D|C)SUMbP(C|B)SUMaP(A)P(B|A)
我们将每一个SUM求值后的结果暂存，就对应将每一个节点从图模型中切除后的新的图暂存。

3、和积与信念更新

边缘化：通过在一个变量（或者变量子集）上求和来把变量从表达式中消解出去。

和积信念更新本质上说是一种VE算法的抽象表达，我们将原来的概率表示变成函数表示，并对它们进行边缘化，我们需要的变量是因子集合，要消解的变量集合，以及消解顺序，这里要说明的一点是边缘化算法。
还是上面的例子，当我们用矩阵的形式将节点的条件概率分布表示出来的时候。
B=A'B'=(0.8 0.2)(0.6 0.4;0.3 0.7)=(P(A=1)P(B=1|A=1)+P(A=0)P(B=1|A=0);(P(A=0)P(B=1|A=0)+P(A=1)P(B=0|A=1))
这样的出来的结果就是边缘化A之后，得到的更新了的B的新的概率概率分布，按照消解顺序，继续消解，就可以得到D的边缘分布。
我们可以看出这个算法与VE算法并没有太大差别，但是它更加抽象的表达了消元的概念，又同时更加具象的表达了边缘化的算法，通过边缘化实际上更新的是我们对某个节点的置信度。
代码：

# Sum-product and beliefs update examples
A=matrix(c(.8,.2),2,1)
B=matrix(c(.6,.4,.3,.7),2,2)
C=matrix(c(.5,.5,.8,.8),2,2)
D=matrix(c(.3,.7,.4,.6),2,2)

Bs = t(A) %*% t(B)
Cs = Bs %*% t(C)
Ds = Cs %*% t(D)
Ds

运行结果.PNG

4、联结树算法

变量消解算法可以用在任何类型的树上（除了带有回路的图中），和积算法可以保存中间结果以便使计算高效，变量消解算法只能用在树中，我们需要把带有回路的图转换为表示等价分布分解形式的树。联结树结合了信念传播算法和积的效率以及变量消解过程的通用性。它需要把带有回路的图转换为表示等价分布分解形式的树。

联结树算法中有一个很重要的步骤就是联结树的构建。
举个例子：

解释案例.png
CodeCogsEqn.png
将条件概率用贝叶斯规则表示，得到的分母集合集合之间分子，分子是联合分布。
联结树构建的4个步骤：
（1）对图模块化，将每一个节点的父节点两两相连
（2）将图转换成无向图，此时所有节点及其父节点都在同一个团中
（3）对图三角化，使属于同一个无向回路的节点两两相连
（4）转化成聚类树，找出三角化图中的每一个团，构建新的节点，注意在每一个聚类节点之间都存在一个分隔节点
联结树上的推断是通过从一个聚类传递信息给另一个聚类实现的
联结树的概率分布：
CodeCogsEqn.gif
其中，分子表示每一个聚类因子，分子表示每一个分隔因子。
联结树.png 三角化.png 解释案例2.png
以上是一个简单的联结树构建例子。
联结树中每一个聚类节点都是节点及其父节点的集合，每一个分隔节点都是既有父节点又有子节点的中间节点，这一点在第一个简单的例子中我们就形象的展示了。通过求解聚类节点的概率分布，更新分隔节点的概率分布，保存中间结果，降低模型复杂度，在变量消解的方法中我们可以针对树结构求解，在联结树算法中我们将一般的图转换为树结构。
联结树就是通过分隔节点将每一个聚类连接起来
聚类就是保存了求解过程中的联合分布
代码：

library(gRbase)
library(gRain)

val=c("true","false")
F = cptable(~F, values=c(10,90),levels=val)
C = cptable(~C|F, values=c(10,90,20,80),levels=val)
E = cptable(~E|F, values=c(50,50,30,70),levels=val)
A = cptable(~A|C, values=c(50,50,70,30),levels=val)
D = cptable(~D|E, values=c(60,40,70,30),levels=val)
B = cptable(~B|A:D, values=c(60,40,70,30,20,80,10,90),levels=val)

plist = compileCPT(list(F,E,C,A,D,B))
plist

print(plist$F)
print(plist$B)

jtree = grain(plist)
jtree

querygrain(jtree, nodes=c("F"), type="marginal")
querygrain(jtree, nodes=c("C"), type="marginal")
querygrain(jtree, nodes=c("B"), type="marginal")
querygrain(jtree, nodes=c("A","B"), type="joint")
querygrain(jtree, nodes=c("A","B","C"), type="joint")

jtree2 = setEvidence(jtree, evidence=list(F="true"))
querygrain(jtree, nodes=c("F"), type="marginal")
querygrain(jtree2, nodes=c("F"), type="marginal")
querygrain(jtree, nodes=c("A"), type="marginal")
querygrain(jtree2, nodes=c("A"), type="marginal")
querygrain(jtree, nodes=c("B"), type="marginal")
querygrain(jtree2, nodes=c("B"), type="marginal")

jtree3 = setEvidence(jtree, evidence=list(F="true",A="false"))
querygrain(jtree, nodes=c("C"), type="marginal")
querygrain(jtree2, nodes=c("C"), type="marginal")
querygrain(jtree3, nodes=c("C"), type="marginal")

#source("http://bioconductor.org/biocLite.R")
#biocLite("bnlearn")

运行结果：

加入两个证据节点后新的边缘分布.PNG 加入证据节点后新的边缘分布.PNG 查询边缘分布和联合分布.PNG jtree.PNG plist计算边缘分布.PNG

这里通过联合树算法，我们不仅可以求边缘分布，还可以求联合分布，而且还可以通过增加证据节点得到新的概率分布，但是当然有一个问题，就是之前我们可以对一个节点赋予一串的值，比如硬币接下来的生产状况，但在联合树中的证据节点就是已知节点，不再代表新添加的数据，也就是通过上一节的程序我们能够更新模型，通过这一节的程序我们能够通过证据节点，得到任意观测节点的变化。
plist让我们能够看任意节点组合的分布，grain让我们能够设置证据变量（已知节点）查询其它节点的办法。