BayesNetwork

贝叶斯网络

有向图的定义

有向图是一种图论中的数据结构，由一组顶点（节点）和一组有方向的边组成，用于表示节点之间的单向关系。其数学定义为：
$$
G = (V, E)
$$

• $ V $：顶点的有限集合（如 ({A, B, C}))。
• $E $：有向边的集合，每条边是一个有序顶点对（如 $ (A \to B) $）表示从$A$指向$B$的边）。

---

关键特性

1. 方向性

   • 边 $ (u \to v) $ 表示从节点 $u $ 指向 $ v $ 的关系，不可逆（除非存在反向边 $(v \to u) $。
   • 示例：社交网络中“关注”关系（A关注B ≠ B关注A）。

2. 路径与连通性

   • 有向路径：一系列首尾相连的有向边（如 $ A \to B \to C $）。
   • 强连通图：任意两节点间存在双向路径（如 $A \to B \to A $）。

3. 环（Cycle）

   • 若存在从某节点出发回到自身的路径（如 $A \to B \to A $），称为有向环。
   • 无环有向图（DAG）：无任何环的图，是贝叶斯网络、任务调度的基础。

---

与无向图的区别

特性	有向图	无向图
边方向	单向$( A \to B $）	双向（$ A-B $）
关系语义	因果关系、依赖关系	对称关系（如合作、连接）
环检测	需考虑方向性	仅需路径闭合

---

常见应用场景

1. 依赖关系建模

   • 贝叶斯网络：用DAG表示变量间的条件依赖。
   • 任务调度：边 $A \to B $ 表示任务$A$必须在$B$前完成。

2. 网络与系统

   • 网页链接：超链接构成有向图（PageRank算法基础）。
   • 状态机：节点表示状态，边表示状态转移（如自动机理论）。

3. 社交与传播分析

   • 信息传播：边 $A \to B $ 表示$A$影响$B$（如谣言扩散模型）。

---

重要算法与操作

1. 拓扑排序

   • 仅适用于DAG，将节点排序为线性序列，保证所有边方向一致（如课程选修顺序）。

2. 强连通分量（SCC）

   • 将图分解为最大强连通子图（如Tarjan算法）。

3. 最短路径

   • Dijkstra算法（边权非负）或Bellman-Ford算法（支持负权边）。

贝叶斯网络

贝叶斯网络（Bayesian Network, BN）简介

贝叶斯网络是一种概率图模型，用于表示一组随机变量及其条件依赖关系。它结合了图论和概率论，通过有向无环图（DAG）直观地描述变量间的因果关系，并用条件概率表（CPT）量化这些关系。

从贝叶斯网络中推断出条件独立性

贝叶斯网络结构一 假设给定如图所示的贝叶斯网络：

graph TD
A[A]-->B[B]
A[A]-->C[C]

$$
\because P(A,B,C) = P(A)\times P(B|A) \times P(C|A)
=P(A)\times P(B|A) \times P(C|A,B)
$$

$$
\therefore P(C|A)= P(C|A,B)
$$

$$
\therefore P(B|A)P(C|A) = P(C|A,B)P(B|A) = P(B,C|A)
$$

由此可得$B$和$C$在条件$A$下相互独立。换句话说，若$A$被观测到，那么路径被阻塞（阻塞对应独立）。

贝叶斯网络结构二 假设给定如图所示的贝叶斯网络

graph LR
A[A]-->B[B]-->C[C]

这种贝叶斯网络结构也称为因果链。若$B$被观测到，则路径被阻塞。

贝叶斯网络结构三 假设给定如图所示的贝叶斯网络

graph TD
A[A]-->C[C]
B[B]-->C[C]

默认情况下，$A$和$B$先天相互独立，若$C$被观测到，则$A$和$B$之间不独立。

Proof
$$
\because P(A,B,C) = P(A)P(B)P(C|A,B) =P(A)P(B|A)P(C|A,B)
$$

$$
\therefore P(B|A) = P(B)
$$

$$
\therefore P(B|A)P(A) = P(A,B) = P(A)P(B)
$$

故$A$和$B$相互独立。

D Speration（判断给定观测集下贝叶斯网络中的变量独立关系）

算法来自于https://web.mit.edu/jmn/www/6.034/d-separation.pdf

该方法的步骤如下：

[Step 1]. Draw the ancestral graph.

根据原始概率图，构建包括表达式中包含的变量以及这些变量的ancestor节点（父节点、父节点的父节点…）的图。

[Step 2]. “Moralize” the ancestral graph by “marrying” the parents.

构建道德图。也就是将贝叶斯网络结构三的$A$和$B$节点相连，

[Step 3]. “Disorient“ the graph by replacing the directed edges (arrows) with undirected edges (lines).

去掉图中所有的路径方向，将directional graph变为non-directional graph。

[Step 4]. Delete the givens and their edges.

从图中删除需要判断的概率表达式中作为条件的变量，以及和他们相连的路径。比如“是否P(A|BDF) = P(A|DF)?”，我们删掉D, F变量以及他们的路径。

[Step 5]. Read the answer off the graph.

• 如果变量之间没有连接，则它们在给定条件下是独立的；
• 如果变量之间有路径连接，则它们不能保证是独立的（或者粗略地说他们是不独立的，基于概率图来说）；
• 如果其中一个变量或者两者都不包含在现在的图中（作为观测条件，在step 4 被删掉了），那么他们是独立的。