首页 > 编程学习 > 机器学习:图文详解影响流动与有向分离(D-分离)(附Python实现)

目录

  • 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(ZX)P(YZ)

    从而:

    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,YZ)=P(Z)P(X,Y,Z)=P(Z)P(X)P(ZX)P(YZ)=P(XZ)P(YZ)

    所以 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(XZ)P(YZ)

    从而:
    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,YZ)=P(Z)P(X,Y,Z)=P(Z)P(Z)P(XZ)P(YZ)=P(XZ)P(YZ)

    所以 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(ZX,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,YZ)=P(Z)P(X,Y,Z)=P(Z)P(X)P(Y)P(ZX,Y)=P(XZ)P(YZ)

    而不给定 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)=ZP(X,Y,Z)=P(X)P(Y)ZP(ZX,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 X1X2Xn是贝叶斯网络图 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} Xi1XiXi+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 X1X2Xn是一条有效迹,随机变量 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} XX ∀ Y ∈ Y \forall Y\in \boldsymbol{Y} YY间均不存在有效迹,那么 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) dsepG(X;YZ)。根据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)={(XYZ):dsepG(X;YZ)}

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从入门到精通》
  • 《机器人原理与技术》
  • 《机器学习强基计划》
  • 《计算机视觉教程》

👇源码获取 · 技术交流 · 抱团学习 · 咨询分享 请联系👇
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式