Mr.Winter`

Mr.Winter`

关注
发信
关注(28)粉丝(399)

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

0 写在前面

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

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

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

1 影响流动性

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

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

  • 间接因果
    给定 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时条件独立。

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

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

2 有效迹

形式化定义影响流。设 X 1 X 2 ⋯ X n X_1X_2\cdots X_n X1​X2​⋯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 X1​X2​⋯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条件独立。遍历网络节点即可获得全体独立性断言集合

机器学习：图文详解影响流动与有向分离(D-分离)(附Python实现)-LMLPHP
算法主要分为两步。第一步中用集合 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

对于这个概率图而言

机器学习：图文详解影响流动与有向分离(D-分离)(附Python实现)-LMLPHP
按照这个算法可以得到独立性断言集合

>>> (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)

🔥 更多精彩专栏：


11-07 10:49
Powered by LMLPHP ©2024 Mr.Winter` 0.010316