机器学习：图文详解影响流动与有向分离(D-分离)(附Python实现)

0 写在前面

机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理；“广”在分析多个机器学习模型：决策树、支持向量机、贝叶斯与马尔科夫决策、强化学习等。

🚀详情：机器学习强基计划(附几十种经典模型源码合集)

---

在机器学习强基计划5-2：用一个例子通俗理解贝叶斯网络(附例题)中我们通过一个实例介绍了贝叶斯网络的概念，在机器学习强基计划5-3：图文详解因子分解与独立图I-Map(附例题分析+Python实验)中我们进一步介绍了网络中独立性条件与概率分布的关系，本文基于前面建立起的概念深入贝叶斯网络的微观结构，理解概率影响是如何在网络中传播的

1 影响流动性

贝叶斯网络的微观基本结构及其独立性如表所示，案例见机器学习强基计划5-2：用一个例子通俗理解贝叶斯网络(附例题)。贝叶斯网络可视为若干微观结构概率影响的组合，简单证明独立性结论，下面采用的概率分布$P$均根据图$\mathcal{G}$因子分解。

• 间接因果
  给定$Z$时，根据有向概率图因果关系可得：
  $$P\left(X,Y,Z\right)=P\left(X\right)P\left(Z|X\right)P\left(Y|Z\right)$$

  从而：

  $$\begin{gathered} 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) \end{gathered}$$

  所以$X$、$Y$在给定$Z$时条件独立。

• 间接证据
  不具有独立性，略

• 共同原因
  给定$Z$时，根据有向概率图因果关系可得：

  $$P\left(X,Y,Z\right)=P\left(Z\right)P\left(X|Z\right)P\left(Y|Z\right)$$

  从而：
  $$\begin{gathered} 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) \end{gathered}$$

  所以$X$、$Y$在给定$Z$时条件独立。

• 共同作用
  给定$Z$时，根据有向概率图因果关系可得：
  $$P\left(X,Y,Z\right)=P\left(X\right)P\left(Y\right)P\left(Z|X,Y\right)$$
  从而：
  $$\begin{gathered} 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) \end{gathered}$$

  而不给定$Z$时：

  $$\begin{gathered} 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) \end{gathered}$$

  所以$X$、$Y$在给定$Z$时不条件独立，不给定$Z$时条件独立。

随机变量间的相互影响在贝叶斯网络中流动。根据微观结构的独立性：当某些观测条件出现或移除时，网络中的影响流可能会产生阻塞

2 有效迹

形式化定义影响流。设$X_1{X}_2\cdots X_n$是贝叶斯网络图$\mathcal{G}$中的一条迹，在给定观测变量集$\mathbf{Z}$的条件下，若满足：

• 对于全体汇连结构$X_{i-1}\to X_i\leftarrow X_{i+1}$，则$X_i$或其至少一个子代在$\mathbf{Z}$中；
• 迹上其他节点都不在$\mathbf{Z}$中；

则$X_1{X}_2\cdots X_n$是一条有效迹，随机变量$X_1$产生的影响可以随有效迹流动到$X_n$。设$\mathbf{X}$、$\mathbf{Y}$、$\mathbf{Z}$是图$\mathcal{G}$的三个节点集，在给定$\mathbf{Z}$为观测变量集时，若$\forall X\in \mathbf{X}$与$\forall Y\in \mathbf{Y}$间均不存在有效迹，那么 $\mathbf{X}$、$\mathbf{Y}$间的影响流被阻塞，称$\mathbf{X}$、$\mathbf{Y}$关于$\mathbf{Z}$有向分离(Directional Separation)或D-分离，记作${\mathrm{d}}_{-}{\mathrm{sep}}_{\mathcal{G}}\left(\mathbf{X};\mathbf{Y}|\mathbf{Z}\right)$。根据D分离的概念可以导出图$\mathcal{G}$中的全体独立性断言

$$\mathcal{I}\left(\mathcal{G}\right)=\left\{\left(X\perp Y|Z\right):{\mathrm{d}}_{-}{\mathrm{sep}}_{\mathcal{G}}\left(\mathbf{X};\mathbf{Y}|\mathbf{Z}\right)\right\}$$

3 有向分离算法

识别给定观测变量$\mathbf{Z}$时，从$X$出发影响能经有效迹流通的节点集合的算法流程如表所示。除去影响可达与观测节点，其余节点与$X$关于$\mathbf{Z}$条件独立。遍历网络节点即可获得全体独立性断言集合

算法主要分为两步。第一步中用集合$A$记录了$\mathbf{Z}$及其祖先节点，用于识别有效迹中的汇连结构 。第二步中用$L$记录待访问的边、$V$记录已访问的边、$R$记录从$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从入门到精通》
• 《机器人原理与技术》
• 《机器学习强基计划》
• 《计算机视觉教程》
• …

👇源码获取 · 技术交流 · 抱团学习 · 咨询分享 请联系👇
转载：https://blog.csdn.net/FRIGIDWINTER/article/details/127335425