机器学习笔记之概率图模型(十)因子图
机器学习笔记之概率图模型——因子图
引言
本节针对精确推断之变量消去法中出现的存在环结构概率图的情况,介绍因子图(Factor Graph),其主要将带环的无向图结构转化为因子图结构。
回顾:图结构相关思想
针对贝叶斯网络/马尔可夫随机场,可以通过因子分解的形式对结点变量集合 X \mathcal X X的联合概率分布 P ( X ) \mathcal P(\mathcal X) P(X)进行表示:
- 贝叶斯网络(有向图)
在这里同样需要注意,这里的
i i i是结点变量的下标,它只能说‘有可能是特征下标’,即‘每个结点变量中均仅包含一个特征/变量’。
P ( X ) = ∏ X P ( x i ∣ x p a ( i ) ) \mathcal P(\mathcal X) = \prod_{\mathcal X} \mathcal P(x_i\mid x_{pa(i)}) P(X)=X∏P(xi∣xpa(i)) - 马尔可夫随机场(无向图)
P ( X ) ∏ i = 1 K ψ C i ( x C i ) \mathcal P(\mathcal X) \prod_{i=1}^{\mathcal K} \psi_{\mathcal C_i}(x_{\mathcal C_i}) P(X)i=1∏KψCi(xCi)
其中, x C i x_{\mathcal C_i} xCi表示编号为 i i i的最大团,无向图中一共包含 K \mathcal K K个极大团。而 ψ C i ( x C i ) \psi_{\mathcal C_i}(x_{\mathcal C_i}) ψCi(xCi)表示极大团 x C i x_{\mathcal C_i} xCi对应的势函数结果。
道德图的功能是将有向图转化为无向图,其主要针对贝叶斯网络中的
V
\mathcal V
V型结构,将该结构中的双亲结点进行连接,从而 引入环结构:
因子图
因子图引入的朴素思想依然是在推断过程中简化运算,在变量消去法介绍中出现的贝叶斯网络结构,在推断过程中产生阻碍。实际上,如果不对变量消去法进行改进,一般的变量消去法只能处理无环的树形结构。
因此,引入因子图的结构方式,通过将有环结构的图修改成因子图的形式,从而使用精确推断对因子图进行处理。
因子图的特点
因子图的特点在于:将结点之间的因子关系直接表现在图上。
其对应公式表示如下:
P
(
X
)
=
∏
S
f
S
(
X
S
)
\mathcal P(\mathcal X) = \prod_{\mathcal S} f_{\mathcal S}(\mathcal X_{\mathcal S})
P(X)=S∏fS(XS)
其中
S
\mathcal S
S表示图中结点变量集合的任意子集,相对应的
X
S
\mathcal X_{\mathcal S}
XS表示
S
\mathcal S
S子集对应在数据集合中的变量/特征集合。
f
S
f_{\mathcal S}
fS表示因子结点。
因子图示例如下:
上述无向图中一共包含
3
3
3个结点,并且包含环结构。右侧是它对应其中一种因子图表示。从而联合概率分布
P
(
X
)
\mathcal P(\mathcal X)
P(X)可表示为:
P
(
X
)
=
f
123
(
x
1
,
x
2
,
x
3
)
\mathcal P(\mathcal X) = f_{123}(x_1,x_2,x_3)
P(X)=f123(x1,x2,x3)
可以看出,变量结点之间不存在直接的边相关联,而是通过因子结点进行关联。
上述因子图并非唯一结果,由于
S
\mathcal S
S集合的任意性,可以随意修改结点子集
S
\mathcal S
S中的结点,从而构成一系列新的子集:
例如上图中的结点集合
X
\mathcal X
X可以包含
3
3
3个结点子集
S
1
,
S
2
,
S
3
\mathcal S_1,\mathcal S_2,\mathcal S_3
S1,S2,S3,各结点子集中包含的结点信息表示如下:
S
1
=
{
x
1
,
x
2
}
S
2
=
{
x
2
,
x
3
}
S
3
=
{
x
1
,
x
3
}
\mathcal S_1 = \{x_1,x_2\} \\ \mathcal S_2 = \{x_2,x_3\} \\ \mathcal S_3 = \{x_1,x_3\}
S1={x1,x2}S2={x2,x3}S3={x1,x3}
那么对应的因子结点
f
1
,
f
2
,
f
3
f_1,f_2,f_3
f1,f2,f3在因子图中表示如下:
对应的联合概率分布
P
(
X
)
\mathcal P(\mathcal X)
P(X)可表示为:
P
(
X
)
=
f
1
(
x
1
,
x
2
)
⋅
f
2
(
x
2
,
x
3
)
⋅
f
3
(
x
1
,
x
3
)
\mathcal P(\mathcal X) = f_{1}(x_1,x_2) \cdot f_{2}(x_2,x_3) \cdot f_{3}(x_1,x_3)
P(X)=f1(x1,x2)⋅f2(x2,x3)⋅f3(x1,x3)
更特殊的情况,结点子集也可存在仅包含一个结点的情况,这里不再赘述。
综上,因子图
G
(
X
,
F
,
E
)
\mathcal G(\mathcal X,\mathcal F,\mathcal E)
G(X,F,E)中对于边
E
\mathcal E
E的要求只需满足:
因子结点
f
j
∈
F
f_j \in \mathcal F
fj∈F和变量结点
x
k
∈
X
x_k \in \mathcal X
xk∈X之间存在边的充要条件是
x
k
x_k
xk在结点子集
S
j
\mathcal S_j
Sj内。即
x
k
∈
S
j
x_k \in \mathcal S_j
xk∈Sj。
基于因子分解的因子图本质上是对无向图因子分解的更泛化的表示。
上述因子图与无向图的因子分解分别表示如下:
{
P
(
X
)
=
ψ
01
(
i
0
,
i
1
)
⋅
ψ
123
(
x
1
,
x
2
,
x
3
)
⋅
ψ
34
(
i
3
,
i
4
)
P
(
X
)
=
f
1
(
i
0
,
i
1
)
⋅
f
2
(
i
1
,
i
2
,
i
3
)
⋅
f
3
(
i
3
,
i
4
)
\begin{cases} \mathcal P(\mathcal X) = \psi_{01}(i_0,i_1) \cdot \psi_{123}(x_1,x_2,x_3) \cdot \psi_{34}(i_3,i_4)\\ \mathcal P(\mathcal X) = f_1(i_0,i_1) \cdot f_2(i_1,i_2,i_3) \cdot f_3(i_3,i_4) \end{cases}
{P(X)=ψ01(i0,i1)⋅ψ123(x1,x2,x3)⋅ψ34(i3,i4)P(X)=f1(i0,i1)⋅f2(i1,i2,i3)⋅f3(i3,i4)
从变量结点归属结点子集的角度,上述两个公式之间没有区别。我们可以将因子图看作是因子分解的进一步分解:
上述无向图同样存在‘特殊情况’。
i
1
,
i
2
,
i
3
i_1,i_2,i_3
i1,i2,i3组成的结点子集,既是‘环状结构’,也是‘极大团’。如果结点数量多起来,可能出现‘存在环结构但不是极大团的情况’。那时无向图可能需要重新寻找极大团;
但‘因子图’并不存在这种限制,因为‘结点子集’
S
\mathcal S
S可以是‘结点变量’的任意子集。相比于无向图操作,因子图的‘因子结点’可以将图划分的更加细致。
至此,概率图模型部分介绍结束,下一节将介绍线性动态系统(Kalman Filter)。
相关文章
- 神经网络与机器学习 笔记—基本知识点(上)
- [吴恩达机器学习笔记]16推荐系统1-2基于内容的推荐系统
- [吴恩达机器学习笔记]15非监督学习异常检测7-8使用多元高斯分布进行异常检测
- [吴恩达机器学习笔记]12支持向量机1从逻辑回归到SVM/SVM的损失函数
- 机器学习数学笔记|极大似然估计
- 机器学习数学笔记|大数定理中心极限定理矩估计
- 机器学习笔记之K近邻学习算法
- 机器学习笔记之正则化(三)权重衰减角度(偏差方向)
- 机器学习笔记之流形模型——标准流模型基本介绍
- 机器学习笔记之前馈神经网络(一)基本介绍
- 机器学习笔记之受限玻尔兹曼机(六)对数似然梯度求解
- 机器学习笔记之高斯过程(二)高斯过程回归——权重空间角度
- 机器学习笔记之核方法(二)正定核函数的充要性证明
- 机器学习笔记之条件随机场(一)背景介绍
- 机器学习笔记之概率图模型(八)信念传播(Belief Propagation,BP)(基于树结构)
- 机器学习笔记之概率图模型(五)马尔可夫随机场的结构表示
- 机器学习笔记之概率图模型(一)背景介绍
- 机器学习笔记之降维(三)从最大投影方差角度观察主成分分析
- 机器学习笔记马尔可夫链蒙特卡洛方法(二)马尔可夫链与平稳分布
- 机器学习笔记之高斯分布(三)——从几何角度观察多维高斯分布
- 机器学习笔记之指数族分布——最大熵原理与softmax激活函数的关系
- 机器学习笔记——极大似然估计与最大后验概率估计
- Andrew Ng机器学习公开课笔记 -- 朴素贝叶斯算法
- 吴恩达机器学习笔记 —— 14 无监督学习
- 吴恩达机器学习笔记 —— 11 应用机器学习的建议
- Andrew Ng-机器学习基础笔记(上)-Python实现代码
- 【吴恩达机器学习】第七周课程精简笔记——支持向量机SVM
- 【吴恩达机器学习】第六周课程精简笔记——模型评估和机器学习系统设计
- 机器学习笔记——皮尔逊相关系数
- 机器学习笔记——贝叶斯学习