gtsam库学习一（因子图理论基础）

编程入门行业动态更新时间:2024-10-10 17:23:08

gtsam库学习一（<a href=https://www.elefans.com/category/jswz/34/1756367.html style= 因子图理论基础）"/>

gtsam库学习一（因子图理论基础）

官方教程

一有向图无向图

来自如下链接

图
有向图(Undirected Graph):无向边构成图
无向图(Directed Graph):有向边构成图
出度和入度（有向图）
出度：以自身为起点的边的个数
入度：以自身为终点的边的个数
A的度为5，3个入度，2个出度
邻接矩阵
V : 顶点集 V = v 1 , v 2 , . . . , v n ，边集 E : e 1 , e 2 , . . . , e n V:顶点集V=v_1,v_2,...,v_n，边集E:e_1,e_2,...,e_n V:顶点集V=v1,v2,...,vn，边集E:e1,e2,...,en
假设无向图 G = ( V , E ) G=(V,E) G=(V,E)
a i j : 表示第 i 个顶点与第 j 个顶点是否相连 a_{ij}:表示第i个顶点与第j个顶点是否相连 aij:表示第i个顶点与第j个顶点是否相连
临界矩阵为 A = A ( G ) = ( a i j ) n ∗ n A=A(G)=(a_{ij})_{n*n} A=A(G)=(aij)n∗n
下图的临界矩阵为：
A = [ a 1 a 2 . . . a n ] [ 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 ] [ a 1 a 2 . . . a n ] T A=\left[\begin{matrix}a_{1}\\ a_2\\ ...\\ a_n\end{matrix}\right]\left[\begin{matrix} 0&1&1&1\\ 1&0&1&0\\ 1&1&0&1\\ 1&0&1&0\end{matrix}\right]\left[\begin{matrix}a_{1}\\ a_2\\ ...\\ a_n\end{matrix}\right]^T A=⎣⎢⎢⎡a1a2...an⎦⎥⎥⎤⎣⎢⎢⎡0111101011011010⎦⎥⎥⎤⎣⎢⎢⎡a1a2...an⎦⎥⎥⎤T
特点：
（1）：无向图的邻接矩阵一定是一个对称矩阵，有向图不一定是
（2）邻接矩阵所需的存储空间值域只与顶点数有关系。
（3）用邻接矩阵存储图，容易判断两个点之间是否有边。
（4）如果一个有向图的邻接矩阵为三角矩阵（主对角线为0），则它的拓扑排序一定存在。
关联矩阵
用 m i j m_{ij} mij表示顶点 v i vi vi与边 e j ej ej关联的关系，可能取值为 0 , 1 , − 1 0,1,-1 0,1,−1，称所得矩阵 M ( G ) = ( m i j ) m ∗ n M(G)=(m_{ij}){m*n} M(G)=(mij)m∗n为图G的关联矩阵,上图的关联矩阵为：
m i j = [ v 1 v 2 v 3 v 4 ] [ 1 0 0 − 1 1 − 1 − 1 0 0 0 0 1 1 0 − 1 0 0 − 1 1 0 ] [ e 1 e 2 e 3 e 4 e 5 ] T m_{ij}=\left[\begin{matrix}v_1\\v_2\\v_3\\v_4\end{matrix}\right] \left[\begin{matrix}1&0&0&-1&1\\-1&-1&0&0&0\\0&1&1&0&-1\\0&0&-1&1&0\end{matrix}\right]\left[\begin{matrix}e_1\\e_2\\e_3\\e_4\\e_5\end{matrix}\right]^T mij=⎣⎢⎢⎡v1v2v3v4⎦⎥⎥⎤⎣⎢⎢⎡1−1000−110001−1−100110−10⎦⎥⎥⎤⎣⎢⎢⎢⎢⎡e1e2e3e4e5⎦⎥⎥⎥⎥⎤T
连通图、连通分量、强连通图、强连通分量
连通图：无向图中，若从顶点u到顶点v有路径，称为u，v是连通的。若图中任意两个顶点均是连通的，则称为连通图。
连通分量：无向图中极大连通子图称为连通分量
强连通图：有向图中，若从顶点u到顶点v有路径，称为u，v是连通的。若图中任意两个顶点均是连通的，则称为强连通图。
连通分量：无向图中极大连通子图称为强连通分量。特：强连通图只有强连通分量（本身），非强连通图有多个强连通分量。

二贝叶斯网络(有向无环图模型、信念网络)

有向无环图模型:如果一个有向图无法从某个顶点出发经过若干条边回到该点
<>有向无环图未必能转化成树，但任何有向树均为有向无环图
来自这篇
来自这篇

贝叶斯定理
条件概率 : P ( A ∣ B ) 条件概率:P(A|B) 条件概率:P(A∣B)
边缘概率 : P ( B ) 边缘概率:P(B) 边缘概率:P(B)
P ( A ∣ B ) = P ( A B ) P ( B ) P(A|B)=\frac{P(AB)}{P(B)} P(A∣B)=P(B)P(AB)
贝叶斯网络
主要用来描述随机变量之间的条件依赖，用圈表示随机变量(random variables)，用箭头表示条件依赖(conditional dependencies)
网络拓扑结构为有向无环图。
E , H ：为节点，箭头有因指向果 , E 为因， H 为果 E,H：为节点，箭头有因指向果,E为因，H为果 E,H：为节点，箭头有因指向果,E为因，H为果
P ( H / E ) : 条件概率（或称连接强度） P(H/E):条件概率（或称连接强度） P(H/E):条件概率（或称连接强度）

性质（1）：有向无环图（贝叶斯网络）数学描述：
I : 图形中所有点的集合 I:图形中所有点的集合 I:图形中所有点的集合
E : 所有线段的集合 E:所有线段的集合 E:所有线段的集合
G = ( I , E ) G=(I,E) G=(I,E)
性质（2）：联合概率
x p a ( i ) : x i 的因节点 x_{pa(i)}:x_i的因节点 xpa(i):xi的因节点
P ( x ) = Π i ∈ I P ( x i ∣ x p a ( i ) ) P(x)=\Pi_{i\in I}P(x_i|x_{pa(i)}) P(x)=Πi∈IP(xi∣xpa(i))
贝叶斯网络的3种结构形式:
（1）：head-to-head

P ( c ) = P ( c ∣ a , b ) , 此时， a 与 b 是阻断的 ( a , b 互相独立 ) 即 : P ( a , b ) = P ( a ) P ( b ) P(c)=P(c|a,b),此时，a与b是阻断的(a,b互相独立)即:P(a,b)=P(a)P(b) P(c)=P(c∣a,b),此时，a与b是阻断的(a,b互相独立)即:P(a,b)=P(a)P(b)
即联合条件概率分布为:
∑ c P ( a , b , c ) = ∑ c P ( a ) P ( b ) P ( c ∣ a , b ) \sum_cP(a,b,c)=\sum_c P(a)P(b)P(c|a,b) c∑P(a,b,c)=c∑P(a)P(b)P(c∣a,b)
（2）：tail-to-tail

P ( a ) = P ( a ∣ c ) P(a)=P(a|c) P(a)=P(a∣c)
P ( b ) = P ( b ∣ c ) P(b)=P(b|c) P(b)=P(b∣c)
联合条件分布:
P ( a , b , c ) = P ( c ) P ( a ∣ c ) P ( b ∣ c ) P(a,b,c)=P(c)P(a|c)P(b|c) P(a,b,c)=P(c)P(a∣c)P(b∣c)
a,b是否独立:
<1> c未知： P ( a , b , c ) = P ( c ) P ( a ∣ c ) P ( b ∣ c ) P(a,b,c)=P(c)P(a|c)P(b|c) P(a,b,c)=P(c)P(a∣c)P(b∣c)无法得到 P ( a , b ) = P ( a ) P ( b ) P(a,b)=P(a)P(b) P(a,b)=P(a)P(b)
<2> c已知(c 阻断)： P ( a , b , c ) = P ( a , b , c ) / P ( c ) = P ( c ) P ( a ∣ c ) P ( b ∣ c ) / P ( c ) = P ( a ∣ c ) P ( b ∣ c ) P(a,b,c)=P(a,b,c)/P(c)=P(c)P(a|c)P(b|c)/P(c)=P(a|c)P(b|c) P(a,b,c)=P(a,b,c)/P(c)=P(c)P(a∣c)P(b∣c)/P(c)=P(a∣c)P(b∣c) a,b互相独立

（3）：head-to-tail

<1> c未知： P ( a , b , c ) = P ( c ) P ( c ∣ a ) P ( b ∣ c ) P(a,b,c)=P(c)P(c|a)P(b|c) P(a,b,c)=P(c)P(c∣a)P(b∣c)无法得到 P ( a , b ) = P ( a ) P ( b ) P(a,b)=P(a)P(b) P(a,b)=P(a)P(b),a,b不独立
<2> c已知(c 阻断)： P ( a , b ∣ c ) = P ( a , b , c ) ∣ P ( c ) = P ( a ) P ( c ∣ a ) P ( b ∣ c ) / P ( c ) = P ( a ∣ c ) P ( b ∣ c ) P(a,b|c)=P(a,b,c)|P(c)=P(a)P(c|a)P(b|c)/P(c)=P(a|c)P(b|c) P(a,b∣c)=P(a,b,c)∣P(c)=P(a)P(c∣a)P(b∣c)/P(c)=P(a∣c)P(b∣c)
（4）：根据（1）（2）（3）在xi给定的条件下， P ( x i + 1 ) P(x_i+1) P(xi+1)的分布和 P ( x 1 ) , P ( x 2 ) , … , P ( x i − 1 ) P(x1),P(x2),…,P(xi-1) P(x1),P(x2),…,P(xi−1)条件独立,当前状态只跟上一状态有关，跟上上或上上之前的状态无关。(马尔科夫链)

三因子图

由概率图导出

根据上图求解一个人已经呼吸困难（d），其抽烟（s）的概率( P ( s ∣ d ) P(s|d) P(s∣d))?
支气管炎的概率( b b b)：
肺癌的概率( c c c)
P ( d ) = 1 P(d)=1 P(d)=1
P ( s ∣ d ) = P ( s , d ) P ( d ) = P ( s , d = 1 ) = ∑ d = 1 , b , x , c P ( s ) P ( c ∣ s ) P ( d ∣ c , s ) P ( b ∣ s ) P ( d ∣ b ) P ( s ) ∑ d = 1 ∑ b P ( b ∣ s ) ∑ x ∑ c P ( c ∣ s ) P ( x ∣ x , s ) P ( d ∣ c , d ) P(s|d)=\frac{P(s,d)}{P(d)}= P(s,d=1)=\sum_{d=1,b,x,c}P(s)P(c|s)P(d|c,s)P(b|s)P(d|b)\\ P(s)\sum_{d=1}\sum_bP(b|s)\sum_x\sum_cP(c|s)P(x|x,s)P(d|c,d) P(s∣d)=P(d)P(s,d)=P(s,d=1)=d=1,b,x,c∑P(s)P(c∣s)P(d∣c,s)P(b∣s)P(d∣b)P(s)d=1∑b∑P(b∣s)x∑c∑P(c∣s)P(x∣x,s)P(d∣c,d)
为了更好解决此类问题引入了因子图的概念
因子图的定义（factor graph）
具有多变量的全局函数因子分解，得到几个局部函数的乘积，以此为基础得到的一个双向图叫做因子图.
X = X 1 , X 2 , . . . , X n : 变量节点 X={X_1,X_2,...,X_n}:变量节点 X=X1,X2,...,Xn:变量节点
F = { f 1 , f 2 , . . . , f m } : 因子节点 F=\{f_1,f_2,...,f_m\}:因子节点 F={f1,f2,...,fm}:因子节点
E : 边 E:边 E:边
数学表达式 : G = ( X , F , E ) 数学表达式:G=(X,F,E) 数学表达式:G=(X,F,E)
即:
g ( X 1 , X 2 , . . . , X n ) = Π j = 1 m f j ( S j ) ( S j ∈ { X 1 , X 2 , . . . , X n } ) g(X_1,X_2,...,X_n)=\Pi_{j=1}^mf_j(S_j)(S_j\in \{X_1,X_2,...,X_n\}) g(X1,X2,...,Xn)=Πj=1mfj(Sj)(Sj∈{X1,X2,...,Xn})
用图表示
有一个全局函数，其因式分解方程为：
f A , f B , f C , f D , f E 为节点函数，表示变量之间的关系，可以是条件概率也可以是其他关系 f_A,f_B,f_C,f_D,f_E为节点函数，表示变量之间的关系，可以是条件概率也可以是其他关系 fA,fB,fC,fD,fE为节点函数，表示变量之间的关系，可以是条件概率也可以是其他关系
g ( X ) = Π E ⊆ Q f c ( X c ) = g ( x 1 , x 2 , x 3 , x 4 , x 5 ) = f A ( x 1 ) f B ( x 2 ) f C ( x 1 , x 2 , x 3 ) f D ( x 3 , x 4 ) f E ( x 3 , x 5 ) g(X)=\Pi_{E\subseteq Q}f_c(X_c)=g(x_1,x_2,x_3,x_4,x_5)=f_A(x_1)f_B(x_2)f_C(x_1,x_2,x_3)f_D(x_3,x_4)f_E(x_3,x_5) g(X)=ΠE⊆Qfc(Xc)=g(x1,x2,x3,x4,x5)=fA(x1)fB(x2)fC(x1,x2,x3)fD(x3,x4)fE(x3,x5)
其对应因子图为：
顶点 : 变量节点或函数节点顶点:变量节点或函数节点顶点:变量节点或函数节点
边线表示它们之间的函数关系边线表示它们之间的函数关系边线表示它们之间的函数关系

或

四马尔可夫随机场（无向图、马尔科夫网络）

来自如下链接
来自如下链接

随机场
来自如下链接
对于一组数据，按照某种特定特规则进行取值，其取值后的全体叫做随机场。
<1> 有一个十个词形成的句子需要做词性标注。这十个词每个词的词性可以在我们已知的词性集合（名词，动词…)中去选择。当我们为每个词选择完词性后，这就形成了一个随机场
<2> 马尔科夫随机场。马尔科夫随机场是随机场的特例，它假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关，和与其不相邻的位置的赋值无关。
从马尔科夫随机场到条件随机场(扩展)
CRF是马尔科夫随机场的特例，它假设马尔科夫随机场中只有𝑋和𝑌两种变量，𝑋一般是给定的，而𝑌一般是在给定𝑋的条件下我们的输出。
对于条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X),给定X，随机变量Y构成马尔可夫随机场，称 P ( Y ∣ X ) P(Y|X) P(Y∣X)为条件随机场
条件随机场到线性链条件随机场（扩展）
X , Y X,Y X,Y, X = ( X 1 , X 2 , . . . , X n ) , Y = ( Y 1 , . . . , Y n ) X=(X_1,X_2,...,X_n),Y=(Y_1,...,Y_n) X=(X1,X2,...,Xn),Y=(Y1,...,Yn),
X , Y X,Y X,Y具有线性链表示的随机变量序列，在给定随机变量序列𝑋的情况下，随机变量𝑌的条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X)构成条件随机场,且满足马尔可夫性:
P ( Y i ∣ X , Y 1 , . . . , Y n ) = P ( Y i ∣ X , Y i − 1 , Y i ) P(Y_i|X,Y_1,...,Y_n)=P(Y_i|X,Y_{i-1},Y_i) P(Yi∣X,Y1,...,Yn)=P(Yi∣X,Yi−1,Yi)
则称 P ( Y ∣ X ) P(Y|X) P(Y∣X)为线性链随机场。
无向图：
一种图表算法
与有向图一样，详见
马尔可夫随机场(也叫马尔可夫网络)
来自如下链接
（1）：马尔可夫随机场（MRF）定义：
对于一般的联合概率 P ( x 1 , x 2 , . . . , x n ) P(x_1,x_2,...,x_n) P(x1,x2,...,xn)分解形式:
Z ϕ : 归一化因子，也称分配函数 Z ϕ = Π ϕ i ( D i ) D i : 随机变量的集合 ( 团 ) f i : 映射函数（也称因子或者势函数）将 D i 映射到某一个实数之上 Z_{\phi}:归一化因子，也称分配函数Z_{\phi}=\Pi\phi_i(D_i)\\ D_i:随机变量的集合(团)\\ f_i:映射函数（也称因子或者势函数）将D_i映射到某一个实数之上 Zϕ:归一化因子，也称分配函数Zϕ=Πϕi(Di)Di:随机变量的集合(团)fi:映射函数（也称因子或者势函数）将Di映射到某一个实数之上
P ( x 1 , x 2 , . . . , x n ) = 1 Z ϕ Π f i ( D i ) P(x_1,x_2,...,x_n)=\frac{1}{Z_{\phi}}\Pi f_i(D_i) P(x1,x2,...,xn)=Zϕ1Πfi(Di)

（2）：性质：
<1> 团：来自
在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称为该无向图的团。
函数集合 f k （称，因子 / 特征 / 团因子），定义域为图 G 的团或者子团 f_k（称，因子/特征/团因子），定义域为图G的团或者子团 fk（称，因子/特征/团因子），定义域为图G的团或者子团
<2> 独立集：一个图中一些两两不相邻的顶点的集合。
<3> ：服从马尔可夫性质
图的顶点u在状态x_u的概率只依赖顶点u的最近临节点，并且顶点u对图中的其他任何节点是条件独立的。
<4> 邻接矩阵：同有向图
<5> 关联矩阵：同有向图
（3）：映射函数
马尔可夫网联络经常表示为对数线性模型即：
w i : 权重 w_i:权重 wi:权重
ϕ k : 势函数（吉布斯势） \phi_k:势函数（吉布斯势） ϕk:势函数（吉布斯势）
f i ( D i ) = e w i T ϕ i ( X i ) P ( x 1 , x 2 , . . . , x n ) = 1 Z e ∑ k w i T ϕ k ( X k ) f_i(D_i)=e^{w_i^T\phi_i(X_{i})}\\ P(x_1,x_2,...,x_n)=\frac{1}{Z}e^{\sum_{k}w_i^T\phi_k(X_{k})} fi(Di)=ewiTϕi(Xi)P(x1,x2,...,xn)=Z1e∑kwiTϕk(Xk)

五隐藏马尔可夫链

详见
本文自作简介方便查找：

基本假设：
<>齐次马尔可夫假设：假设隐藏的马尔可夫链在任一时刻t的状态只依赖于其前一个时刻的状态
<>观测独立性假设：假设任意时刻的观测状态只依赖于该时刻的马尔可夫链的状态，与其他的观测状态及状态都无关。
定义
<>假设有三个不同的骰子(6面、4面、8面)，每次先从三个骰子里面选择一个，每个骰子选中的概率为1/3，如下图所示，重复上述过程，得到一串数值[1,6,3,5,2,7]。这些可观测变量组成可观测状态链。同时，在隐马尔可夫模型中还有一条由隐变量组成的隐含状态链，在本例中即骰子的序列。比如得到这串数字骰子的序列可能为[D6, D8, D8, D6, D4, D8]。(右图为隐马尔可夫模型)

隐马尔科夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个可观测的随机序列的过程.
概念
<1> 状态序列;上图中的 D 6 , D 8 , D 8 , D 6 , D 4 , D 8 D6,D8,D8,D6,D4,D8 D6,D8,D8,D6,D4,D8
<2> 观测序列： 1 ， 6 ， 3 ， 5 ， 2 ， 7 1，6，3，5，2，7 1，6，3，5，2，7
隐马尔可夫模型由初始概率、状态转移分布、观测概率分布确定
Q = { q 1 , q 2 , . . . , q N } : 所有状态的集合 Q=\{q_1,q_2,...,q_N\}:所有状态的集合 Q={q1,q2,...,qN}:所有状态的集合
V = { v 1 , v 2 , . . . , v N } : 所有可能的集合 V=\{v_1,v_2,...,v_N\}:所有可能的集合 V={v1,v2,...,vN}:所有可能的集合
N : 可能的状态数 N:可能的状态数 N:可能的状态数
M : 可能的观测数 M:可能的观测数 M:可能的观测数
I = { i 1 , i 2 , . . , i t } : 长度为 t 的状态序列 I=\{i_1,i_2,..,i_t\}:长度为t的状态序列 I={i1,i2,..,it}:长度为t的状态序列
O = { o 1 , o 2 , . . . , o t } : 对应状态序列的观测序列 O=\{o_1,o_2,...,o_t\}:对应状态序列的观测序列 O={o1,o2,...,ot}:对应状态序列的观测序列
隐马尔科夫模型的三要素
（1）状态转移概率矩阵A：(状态t转换到t+1的概率矩阵)
A = a i j N × N ， ( a i j = P ( i t + 1 ∣ i t = q i ) , i , j ∈ N ) A={a_{ij}}_{N×N}，(a_{ij}=P(i_{{t+1}}|i_t=q_i),i,j\in N) A=aijN×N，(aij=P(it+1∣it=qi),i,j∈N)
（2）观测概率矩阵B
（3）初始状态矩阵C：
C i : 在时刻 t = 1 处于状态 q i 的概率 C_i:在时刻t=1处于状态q_i的概率 Ci:在时刻t=1处于状态qi的概率
C = ( C i ) , C i = P ( i 1 = q i ) , i ∈ 1 , 2 , . . , N C=(C_i),C_i=P(i_1=q_i),i\in 1,2,..,N C=(Ci),Ci=P(i1=qi),i∈1,2,..,N
隐马尔可夫列可用三元符号表示：
λ = { A , B , C } \lambda=\{A,B,C\} λ={A,B,C}
隐马尔可夫问题的三个基本问题
（1）概率计算问题：已知 λ = { A , B , C } \lambda=\{A,B,C\} λ={A,B,C},和观测序列 O = { o 1 , o 2 , . . . , o t } O=\{o_1,o_2,...,o_t\} O={o1,o2,...,ot},求解观测序列 O O O出现的概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)
（2）学习问题：已知一组 O = { o 1 , o 2 , . . . , o t } O=\{o_1,o_2,...,o_t\} O={o1,o2,...,ot}，使用最大似然函数求解最优的 λ = { A , B , C } \lambda=\{A,B,C\} λ={A,B,C}
（3）预测问题（或称解码的问题）：已知 λ = { A , B , C } \lambda=\{A,B,C\} λ={A,B,C}， O = { o 1 , o 2 , . . . , o t } O=\{o_1,o_2,...,o_t\} O={o1,o2,...,ot}，求解最优可能的状态序列： P ( I ∣ O ) P(I|O) P(I∣O)最大的一组状态序列 I = { i 1 , I 2 , . . . , i n } I=\{i_1,I_2,...,i_n\} I={i1,I2,...,in}
前向算法
（1）前向概率：已知 λ = { A , B , C } \lambda=\{A,B,C\} λ={A,B,C}，定义到t时刻的观测序列为 O = { o 1 , o 2 , . . . , o t } O=\{o_1,o_2,...,o_t\} O={o1,o2,...,ot},且t时刻状态为 q i q_i qi的概率。
记为： a t ( i ) = P ( o 1 , o 2 , . . . , o t , i t = q i ∣ λ ) a_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda) at(i)=P(o1,o2,...,ot,it=qi∣λ)
（2）前向算法：已知前向概率，输入隐马尔可夫模型和观测序列，根据前向概率算法计算输出结果为序列为O的概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)。
步骤如下：
<1>: 设定t=1的隐变量的初值：
a 1 ( i ) = C i b i ( o i ) , i = 1 , 2 , . . . , N a_1(i)=C_ib_i(o_i),i=1,2,...,N a1(i)=Cibi(oi),i=1,2,...,N
<2>:前向概率公式对前向概率进行递推， t = 1 , 2 , . . . , N − 1 t=1,2,...,N-1 t=1,2,...,N−1
a t 1 ( i ) = [ ∑ j + 1 N α t ( j ) a j i ] b i ( o i + 1 ) , i ∈ 1 , 2 , . . . , N a_{t_1}(i)=[\sum_{j+1}^N \alpha_t(j)a_{ji}]b_i(o_{i+1}),i\in1,2,...,N at1(i)=[j+1∑Nαt(j)aji]bi(oi+1),i∈1,2,...,N
<3>:最后对所有的前向概率进行求和得到最终的结果:
P ( P ∣ λ ) = ∑ i = 1 N α t ( i ) P(P|\lambda)=\sum_{i=1}^N\alpha_t(i) P(P∣λ)=i=1∑Nαt(i)
后向算法
已知t时刻隐变量的初值，求解t+1到T时刻的部分观测的观测序列 { o t + 1 , o t + 2 , . . . , o T } \{o_{t+1},o_{t+2},...,o_{T}\} {ot+1,ot+2,...,oT}:
β t ( i ) = P ( o t + 1 , o t + 2 , . . . , o T ∣ i t = q i , λ ) \beta_t(i)=P(o_{t+1},o_{t+2},...,o_{T}|i_t=q_i,\lambda) βt(i)=P(ot+1,ot+2,...,oT∣it=qi,λ)
求解后向概率 β t ( i ) \beta_t(i) βt(i),观测序列 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)
<1> 初值:
β T ( i ) = 1 , i ∈ 1 , 2 , . . . , N \beta_T(i)=1,i\in 1,2,...,N βT(i)=1,i∈1,2,...,N
<2> t=T-1,T-2,…,1
a i j : a_{ij}: aij:i->j的转移概率
b j : b_j: bj:表示观测概率
β t + 1 后向概率 : \beta_{t+1}后向概率: βt+1后向概率:
β t ( i ) = ∑ j = 1 N a i j b j ( o t + 1 ) β t + 1 ( j ) , i ∈ 1 , 2 , . . . , N \beta_t(i)=\sum^N_{j=1}a_{ij}b_j(o_{t+1})\beta_{t+1}(j),i\in1,2,...,N βt(i)=j=1∑Naijbj(ot+1)βt+1(j),i∈1,2,...,N
<3> 求和
π i : 初始状态矩阵 \pi_i:初始状态矩阵 πi:初始状态矩阵
P ( O ∣ λ ) = ∑ i = 1 N π i b i ( o 1 ) β 1 ( i ) P(O|\lambda)=\sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i) P(O∣λ)=i=1∑Nπibi(o1)β1(i)
实例详见

六转化因子图

贝叶斯网构造因子图

贝叶斯网络如下
其联合分布为： P ( u , w , x , y , z ) = p ( u ) p ( w ) p ( x ∣ u , w ) p ( y ∣ x ) p ( z ∣ x ) P(u,w,x,y,z)=p(u)p(w)p(x|u,w)p(y|x)p(z|x) P(u,w,x,y,z)=p(u)p(w)p(x∣u,w)p(y∣x)p(z∣x)

2:其对应因子图为
（1）贝叶斯网络中的一个因子对应因子图中的一个结点
（2）贝叶斯网络中的每一个变量在因子图上对应边或者半边
（3）结点g和边x相连当且仅当变量x出现在因子g中
得到下列图（两个都可以）

马尔可夫随机模型构造因子图

来自这篇
要对MRF中的因子转换成因子图中的因子即可

隐马尔科夫模型转换而成的因子图

求解n时刻的前向传播算法：
p ( x 0 , x 1 , x 2 , . . . , x n , y 1 , . . . , y n ) = p ( x 0 ) Π k = 1 n p ( x k ∣ x k − 1 ) p ( y k ∣ x k − 1 ) ) p(x_0,x_1,x_2,...,x_n,y_1,...,y_n)=p(x_0)\Pi_{k=1}^np(x_k|x_{k-1})p(y_k|x_{k-1})) p(x0,x1,x2,...,xn,y1,...,yn)=p(x0)Πk=1np(xk∣xk−1)p(yk∣xk−1))
转化为因子图如下：