目录
0 写在前面1 影响流动性2 有效迹3 有向分离算法4 Python实现
0 写在前面
机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理；“广”在分析多个机器学习模型：决策树、支持向量机、贝叶斯与马尔科夫决策、强化学习等。
详情：机器学习强基计划(附几十种经典模型源码合集)
在机器学习强基计划5-2：用一个例子通俗理解贝叶斯网络(附例题)中我们通过一个实例介绍了贝叶斯网络的概念，在机器学习强基计划5-3：图文详解因子分解与独立图I-Map(附例题分析+Python实验)中我们进一步介绍了网络中独立性条件与概率分布的关系，本文基于前面建立起的概念深入贝叶斯网络的微观结构，理解概率影响是如何在网络中传播的
1 影响流动性
贝叶斯网络的微观基本结构及其独立性如表所示，案例见机器学习强基计划5-2：用一个例子通俗理解贝叶斯网络(附例题)。贝叶斯网络可视为若干微观结构概率影响的组合，简单证明独立性结论，下面采用的概率分布
P
P
P均根据图
G
\mathcal{G}
G因子分解。
间接因果 给定
Z
Z
Z时，根据有向概率图因果关系可得：
P
(
X
,
Y
,
Z
)
=
P
(
X
)
P
(
Z
∣
X
)
P
(
Y
∣
Z
)
P\left( X,Y,Z \right) =P\left( X \right) P\left( Z|X \right) P\left( Y|Z \right)
P(X,Y,Z)=P(X)P(Z∣X)P(Y∣Z) 从而：
P
(
X
,
Y
∣
Z
)
=
P
(
X
,
Y
,
Z
)
P
(
Z
)
=
P
(
X
)
P
(
Z
∣
X
)
P
(
Y
∣
Z
)
P
(
Z
)
=
P
(
X
∣
Z
)
P
(
Y
∣
Z
)
P\left( X,Y|Z \right) =\frac{P\left( X,Y,Z \right)}{P\left( Z \right)}\\=\frac{P\left( X \right) P\left( Z|X \right) P\left( Y|Z \right)}{P\left( Z \right)}\\=P\left( X|Z \right) P\left( Y|Z \right)
P(X,Y∣Z)=P(Z)P(X,Y,Z)=P(Z)P(X)P(Z∣X)P(Y∣Z)=P(X∣Z)P(Y∣Z) 所以
X
X
X、
Y
Y
Y在给定
Z
Z
Z时条件独立。 间接证据 不具有独立性，略 共同原因 给定
Z
Z
Z时，根据有向概率图因果关系可得：
P
(
X
,
Y
,
Z
)
=
P
(
Z
)
P
(
X
∣
Z
)
P
(
Y
∣
Z
)
P\left( X,Y,Z \right) =P\left( Z \right) P\left( X|Z \right) P\left( Y|Z \right)
P(X,Y,Z)=P(Z)P(X∣Z)P(Y∣Z) 从而：
P
(
X
,
Y
∣
Z
)
=
P
(
X
,
Y
,
Z
)
P
(
Z
)
=
P
(
Z
)
P
(
X
∣
Z
)
P
(
Y
∣
Z
)
P
(
Z
)
=
P
(
X
∣
Z
)
P
(
Y
∣
Z
)
P\left( X,Y|Z \right) =\frac{P\left( X,Y,Z \right)}{P\left( Z \right)}\\=\frac{P\left( Z \right) P\left( X|Z \right) P\left( Y|Z \right)}{P\left( Z \right)}\\=P\left( X|Z \right) P\left( Y|Z \right)
P(X,Y∣Z)=P(Z)P(X,Y,Z)=P(Z)P(Z)P(X∣Z)P(Y∣Z)=P(X∣Z)P(Y∣Z) 所以
X
X
X、
Y
Y
Y在给定
Z
Z
Z时条件独立。 共同作用 给定
Z
Z
Z时，根据有向概率图因果关系可得：
P
(
X
,
Y
,
Z
)
=
P
(
X
)
P
(
Y
)
P
(
Z
∣
X
,
Y
)
P\left( X,Y,Z \right) =P\left( X \right) P\left( Y \right) P\left( Z|X,Y \right)
P(X,Y,Z)=P(X)P(Y)P(Z∣X,Y) 从而：
P
(
X
,
Y
∣
Z
)
=
P
(
X
,
Y
,
Z
)
P
(
Z
)
=
P
(
X
)
P
(
Y
)
P
(
Z
∣
X
,
Y
)
P
(
Z
)
≠
P
(
X
∣
Z
)
P
(
Y
∣
Z
)
P\left( X,Y|Z \right) =\frac{P\left( X,Y,Z \right)}{P\left( Z \right)}\\=\frac{P\left( X \right) P\left( Y \right) P\left( Z|X,Y \right)}{P\left( Z \right)}\\\ne P\left( X|Z \right) P\left( Y|Z \right)
P(X,Y∣Z)=P(Z)P(X,Y,Z)=P(Z)P(X)P(Y)P(Z∣X,Y)=P(X∣Z)P(Y∣Z) 而不给定
Z
Z
Z时：
P
(
X
,
Y
)
=
∑
Z
P
(
X
,
Y
,
Z
)
=
P
(
X
)
P
(
Y
)
∑
Z
P
(
Z
∣
X
,
Y
)
=
P
(
X
)
P
(
Y
)
P\left( X,Y \right) =\sum_Z{P\left( X,Y,Z \right)}\\=P\left( X \right) P\left( Y \right) \sum_Z{P\left( Z|X,Y \right)}\\=P\left( X \right) P\left( Y \right)
P(X,Y)=Z∑P(X,Y,Z)=P(X)P(Y)Z∑P(Z∣X,Y)=P(X)P(Y) 所以
X
X
X、
Y
Y
Y在给定
Z
Z
Z时不条件独立，不给定
Z
Z
Z时条件独立。
随机变量间的相互影响在贝叶斯网络中流动。根据微观结构的独立性：当某些观测条件出现或移除时，网络中的影响流可能会产生阻塞
2 有效迹
形式化定义影响流。设
X
1
X
2
⋯
X
n
X_1X_2\cdots X_n
X1X2⋯Xn是贝叶斯网络图
G
\mathcal{G}
G中的一条迹，在给定观测变量集
Z
\boldsymbol{Z}
Z的条件下，若满足：
对于全体汇连结构
X
i
−
1
→
X
i
←
X
i
+
1
X_{i-1}\rightarrow X_i\gets X_{i+1}
Xi−1→Xi←Xi+1，则
X
i
X_i
Xi或其至少一个子代在
Z
\boldsymbol{Z}
Z中；迹上其他节点都不在
Z
\boldsymbol{Z}
Z中；
则
X
1
X
2
⋯
X
n
X_1X_2\cdots X_n
X1X2⋯Xn是一条有效迹，随机变量
X
1
X_1
X1产生的影响可以随有效迹流动到
X
n
X_n
Xn。设
X
\boldsymbol{X}
X、
Y
\boldsymbol{Y}
Y、
Z
\boldsymbol{Z}
Z是图
G
\mathcal{G}
G的三个节点集，在给定
Z
\boldsymbol{Z}
Z为观测变量集时，若
∀
X
∈
X
\forall X\in \boldsymbol{X}
∀X∈X与
∀
Y
∈
Y
\forall Y\in \boldsymbol{Y}
∀Y∈Y间均不存在有效迹，那么
X
\boldsymbol{X}
X、
Y
\boldsymbol{Y}
Y间的影响流被阻塞，称
X
\boldsymbol{X}
X、
Y
\boldsymbol{Y}
Y关于
Z
\boldsymbol{Z}
Z有向分离(Directional Separation)或D-分离，记作
d
−
s
e
p
G
(
X
;
Y
∣
Z
)
\mathrm{d}_-\mathrm{sep}_{\mathcal{G}}\left( \boldsymbol{X};\boldsymbol{Y}|\boldsymbol{Z} \right)
d−sepG(X;Y∣Z)。根据D分离的概念可以导出图
G
\mathcal{G}
G中的全体独立性断言
I
(
G
)
=
{
(
X
⊥
Y
∣
Z
)
:
d
−
s
e
p
G
(
X
;
Y
∣
Z
)
}
\mathcal{I} \left( \mathcal{G} \right) =\left\{ \left( X\bot Y|Z \right) :\mathrm{d}_-\mathrm{sep}_{\mathcal{G}}\left( \boldsymbol{X};\boldsymbol{Y}|\boldsymbol{Z} \right) \right\}
I(G)={(X⊥Y∣Z):d−sepG(X;Y∣Z)}
3 有向分离算法
识别给定观测变量
Z
\boldsymbol{Z}
Z时，从
X
X
X出发影响能经有效迹流通的节点集合的算法流程如表所示。除去影响可达与观测节点，其余节点与
X
X
X关于
Z
\boldsymbol{Z}
Z条件独立。遍历网络节点即可获得全体独立性断言集合
算法主要分为两步。第一步中用集合
A
A
A记录了
Z
\boldsymbol{Z}
Z及其祖先节点，用于识别有效迹中的汇连结构 。第二步中用
L
L
L记录待访问的边、
V
V
V记录已访问的边、
R
R
R记录从
X
X
X出发有效迹途径的节点，其余步骤算法流程图已经写得很详细了，不再赘述。
4 Python实现
算法实现层面完全和算法流程表对应
def getReachableNodes(self, nodes, observed=None):
# 观测变量集合
observedList = observed if observed else []
reachableDict = {}
# Step 1: 将观测变量及其祖先节点插入集合A
A, L = set(), set(observedList)
while L:
node = L.pop()
if node not in A:
L.update(self.predecessors(node))
A.add(node)
# Step 2: 遍历从X出发的有效迹, up表示从父节点流向子节点, down反之
for start in nodes if isinstance(nodes, list) else [nodes]:
L, V, R = set(), set(), set()
L.add((start, "up"))
while L:
node, direction = L.pop()
if (node, direction) not in V:
if node not in observedList:
R.add(node)
V.add((node, direction))
if direction == "up" and node not in observedList:
for parent in self.predecessors(node):
L.add((parent, "up"))
for child in self.successors(node):
L.add((child, "down"))
elif direction == "down":
if node not in observedList:
for child in self.successors(node):
L.add((child, "down"))
if node in A:
for parent in self.predecessors(node):
L.add((parent, "up"))
reachableDict[start] = R
return reachableDict
对于这个概率图而言
按照这个算法可以得到独立性断言集合
>>> (Intelligence ⟂ Difficulty)
>>> (Intelligence ⟂ Difficulty | SAT)
>>> (Intelligence ⟂ Letter | Grades)
>>> (Intelligence ⟂ Letter | SAT, Grades)
>>> (Intelligence ⟂ Letter | Difficulty, Grades)
>>> (Intelligence ⟂ Letter | SAT, Difficulty, Grades)
>>> (SAT ⟂ Difficulty)
>>> (SAT ⟂ Difficulty, Letter, Grades | Intelligence)
>>> (SAT ⟂ Letter | Grades)
>>> (SAT ⟂ Difficulty, Grades | Intelligence, Letter)
>>> (SAT ⟂ Difficulty, Letter | Intelligence, Grades)
>>> (SAT ⟂ Letter, Grades | Intelligence, Difficulty)
>>> (SAT ⟂ Letter | Difficulty, Grades)
>>> (SAT ⟂ Difficulty | Intelligence, Letter, Grades)
>>> (SAT ⟂ Grades | Intelligence, Letter, Difficulty)
>>> (SAT ⟂ Letter | Intelligence, Difficulty, Grades)
>>> (Letter ⟂ SAT | Intelligence)
>>> (Letter ⟂ SAT, Intelligence, Difficulty | Grades)
>>> (Letter ⟂ Intelligence, Difficulty | SAT, Grades)
>>> (Letter ⟂ SAT | Intelligence, Difficulty)
>>> (Letter ⟂ SAT, Difficulty | Intelligence, Grades)
>>> (Letter ⟂ SAT, Intelligence | Difficulty, Grades)
>>> (Letter ⟂ Difficulty | SAT, Intelligence, Grades)
>>> (Letter ⟂ Intelligence | SAT, Difficulty, Grades)
>>> (Letter ⟂ SAT | Intelligence, Difficulty, Grades)
>>> (Grades ⟂ SAT | Intelligence)
>>> (Grades ⟂ SAT | Intelligence, Letter)
>>> (Grades ⟂ SAT | Intelligence, Difficulty)
>>> (Grades ⟂ SAT | Intelligence, Letter, Difficulty)
>>> (Difficulty ⟂ SAT, Intelligence)
>>> (Difficulty ⟂ Intelligence | SAT)
>>> (Difficulty ⟂ SAT | Intelligence)
>>> (Difficulty ⟂ Letter | Grades)
>>> (Difficulty ⟂ Letter | SAT, Grades)
>>> (Difficulty ⟂ SAT | Intelligence, Letter)
>>> (Difficulty ⟂ SAT, Letter | Intelligence, Grades)
>>> (Difficulty ⟂ Letter | SAT, Intelligence, Grades)
>>> (Difficulty ⟂ SAT | Intelligence, Letter, Grades)
本文完整代码联系下方博主名片获取
更多精彩专栏：
《ROS从入门到精通》《机器人原理与技术》《机器学习强基计划》《计算机视觉教程》…
源码获取 · 技术交流 · 抱团学习 · 咨询分享 请联系
发表评论