1.5 图模型
1.5.1 有向无环图
图G={V,E}由节点（或变量）集V={V1,V2,…,VN}和边集E组成，其中N为节点个数，如图1-2所示。在图G中，对于任意的节点对Vi,Vj∈V(i≠j)由一条有向边Vi→Vj（或Vi←Vj）或者一条无向边Vi－Vj连接。边集E是图G中节点之间的边的集合。如果集合E中所有的边都是无向边，则称G是一个无向图（Undirected Graph），如图1-2a所示。如果E中所有的边都是有向边，则称G是一个有向图（Directed Graph），如图1-2b和图1-2c所示。一条从节点Vi到另一节点Vj的路径p是由从Vi开始到Vj为止、依次有边相连、中间无重复节点的有向边或无向边组成的，如图1-2a中的路径A－C－E－Q和图1-2b中的路径A→C→E←Q。如果路径p上所有边的方向都是朝向Vj，即Vi→Vk→…→Vj，则称路径p是从Vi到Vj的有向路径，其中Vi是Vj在图G中的祖先节点（Ancestor），而Vj是Vi的子孙（或后代）节点（Descendant）。例如，图1-2c中的有向路径A→C→E→Q，其中A和C是Q的祖先节点，而Q是A和C的子孙节点。Vi→Vj表示Vi是Vj在图G中的父节点（Parent），而Vj是Vi的孩子节点（Child），例如，图1-2c中的A是C的父节点，C是A的孩子节点。一条从Vi到Vj以及再从Vj到Vi的有向路径称为一个有向环，例如，图1-2b中的E→F→Q→E是一个有向环。一个没有环的有向图称为有向无环图，例如，图1-2c是一个有向无环图。有向无环图是因果关系表示的最重要的图模型。如果赋予有向无环图中的有向边因果语义，即如果存在有向边Vi→Vj，则称Vi是Vj的直接原因，Vj是Vi的直接结果，那么有向无环图被称为因果图或因果结构。
图1-2 三种图模型
有向无环图由三种基本结构组成：链结构（Chain）、叉结构（Fork）、对撞结构（V-结构，V-Structure）（在第4章详细介绍），如图1-3所示。
图1-3 有向无环图中的三种基本结构
在一个有向无环图中，如果变量Vi和Vj之间存在一条单向路径，如Vi→Q→Vj或Vi←Q←Vj，这种类型的结构被称为链结构。叉结构为Vi←Q→Vj且Q是Vi和Vj的父节点或共同原因。如果Q是Vi和Vj的共同孩子节点且Vi和Vj之间无有向边连接，即Vi→Q←Vj，该结构被称为对撞结构（或V-结构），节点Q被称为对撞节点。基于这三种基本结构，下面我们介绍有向无环图中的重要概念：d-分离。
定义1-1 阻断路径（Blocked Path） 在有向无环图G中，如果以下两个条件满足任意一个，则节点Vi与Vj之间的一条路径p被条件集Z（可能为空集）阻断：
（1）路径p中存在链结构Vi→Q→Vj或叉结构Vi←Q→Vj，且Q在Z中；
（2）路径p中存在对撞结构Vi→Q←Vj，Q且Q的子孙节点都不在Z中。
在图1-4中，路径B→S←X是一个对撞结构，S是对撞节点，根据定义1-1，由于S不能出现在条件集Z中，因此，条件集Z为空集时，这条路径被Z阻断。B←Y→X是叉结构，X和B之间的路径被Y阻断，条件集Z为{Y}。路径Y→B→S和路径Y→X→S分别被B和X阻断。由于路径Y→X→N←S中有对撞结构，当条件集Z={X}、Z={X,N}或Z为空集时，该路径被Z阻断。
图1-4 有向无环图与d-分离示例
定义1-2 d-分离（有向分割，Directed Separation） 如果两个节点Vi与Vj之间的所有路径都被集合Z阻断，则Vi与Vj被集合Z“d-分离”。
如果Vi与Vj之间存在一条路径没有被集合Z阻断，那么Vi与Vj被“d-连接”（d-Connection）。d-分离体现了数据中变量之间的条件独立与条件依赖关系，同时它蕴含着图结构背后的数据生成机制，因此d-分离是有向无环图中最重要的概念之一。
在图1-4中，X和B之间共有三条路径：（1）B←Y→X；（2）B→S←X；（3）B→S→N←X。根据定义1-1，当条件集Z={Y}时，路径B←Y→X被Z阻断；当条件集Z为空集时，路径B→S←X被Z阻断。由于路径B→S→N←X中有对撞结构，当条件集Z={S}、Z={S,N}或Z为空集时，该路径被Z阻断。由于三条路径中有两条路径包含对撞结构，因此，综合这三条路径的条件集信息，X和B被Y“d-分离”。B和N之间共有四条路径：（1）B←Y→X→S→N，当Z为集合{S,X,Y}中任意不为空集的子集时，该路径被阻断；（2）B←Y→X→N，当Z为集合{X,Y}中任意不为空的子集时，该路径被阻断；（3）B→S→N，当Z={S}时，该路径被阻断；（4）B→S←X→N，当Z={X}、Z={
}或Z={X,S}时，该路径被阻断。根据定义1-1，综合这四路径的条件集信息，条件集{S,X}阻断了B和N之间所有四条路径，因此，B和N被集合{S,X}“d-分离”。
1.5.2 最大祖先图
当观测变量集V中没有隐变量时，我们一般称V满足因果充分性假设，见定义1-3。
定义1-3 因果充分性（Causal Sufficiency） 当观测变量集V中任意两个或多个变量的直接原因都存在V中时，则V满足因果充分性假设。
如果观测变量集不具有因果充分性，那么这个变量集中含有未观测到的变量，即存在隐变量。当观测数据中出现未观测到的隐变量时，有向无环图将难以有效表示这些隐变量。例如，图1-5a是一个由四个可观测变量{A,B,C,H}和一个不可观测变量（隐变量）L构成的因果图。根据d-分离，图1-5a涉及了三种依赖关系：A⊥H｜B、A⊥H｜C和﹁A⊥H｜{B,C}。其中⊥表示条件独立，｜表示条件依赖。显而易见，这三种依赖关系无法使用一个有向无环图表示。
图1-5 具有隐变量的有向无环图和最大祖先图
Richardson等提出了最大祖先图（Maximal Ancestral Graph，MAG）模型[8]。最大祖先图在有隐变量的情况下具有表示观测变量之间关系的能力。引入了最大祖先图的概念后，我们可以用图1-5b来表示图1-5a中存在的条件依赖关系。在介绍最大祖先图之前，我们先介绍混合图（Mixed Graph）和祖先图（Ancestral Graph）的概念。
定义1-4 混合图 混合图由三种基本类型的边组成：有向边（→或←）、双向边（↔）和无向边（－）。
例如，图1-6为定义在变量集V={A,B,C,H,E,F}上的混合图。如果两个变量之间存在一条边，则称这两个变量是邻接的。在混合图中，一条路径是指不同顶点{V1,V2,…,Vk}的一个序列，对于任意0＜i＜k，Vi和Vi+1是邻接的。如果给定一条路径，0＜i＜k，都有Vi→Vi+1，则称这条路径为有向路径。在图1-6中，{A,H,E,F}就是一条路径，而{A,H,B}是一条有向路径。
图1-6 混合图
在混合图中，如果存在Vi→Vj，则Vi是Vj的父节点，Vj是Vi的孩子节点；如果存在Vi↔Vj，则Vi是Vj的配偶节点，Vj也是Vi的配偶节点；如果存在Vi-Vj，则Vi是Vj的邻居节点，Vj也是Vi的邻居节点；如果存在一条从Vi指向Vj的有向路径，则Vi是Vj的祖先节点。在图1-6中，H是B、E的父节点，C是E的配偶节点，F是E的邻居节点，A是E的祖先节点。
令An(Vi)表示Vi的祖先节点集合，如果混合图中Vj→Vi和Vi∈An(Vj)同时存在，则混合图中存在一个有向环。在图1-6中，满足B→A且A∈An(B)，所以该混合图中存在一个有向环。如果混合图中Vj↔Vi和Vi∈An(Vj)同时存在，则混合图中存在一个几乎有向环（Almost Directed Cycle）。在图1-6中，满足E↔C且C∈An(E)，所以该混合图中存在一个几乎有向环。
定义1-5 祖先图 如果一个混合图满足下列条件，则该混合图被称为祖先图：
（1）混合图中不存在有向环；
（2）混合图中不存在几乎有向环；
（3）对于任意的无向边Vi-Vj，Vi和Vj在混合图中不存在父节点和配偶节点。
在祖先图中，Vi→Vj表示Vi是Vj的一个原因（或祖先），而Vj不是Vi的一个原因（或祖先）。Vi↔Vj表示Vi不是Vj的一个原因，而Vj也不是Vi的一个原因，Vi和Vj之间存在一个隐变量。如图1-7所示，在图1-7a中不存在有向环，不存在几乎有向环，也不存在无向边，所以该图是一个祖先图，而在图1-7b中存在H↔F且F∈An(H)这个几乎有向环，因此该图是一个非祖先图。
图1-7 祖先图与非祖先图
定义1-6 对撞节点和非对撞节点（Collider and Non-Collider） 在祖先图中，给定一条路径π和节点Vi，如果π存在*→Vi←*，其中*表示任意的边缘标记＞或-，则称Vi为对撞节点；否则称Vi为非对撞节点。
在祖先图中，三元组Vi→Vj←Vk、Vi↔Vj↔Vk、Vi↔Vj←Vk和Vi→Vj↔Vk中Vj都是对撞节点。例如在图1-5b中，A→B↔C、B↔C←H中B和C都是对撞节点。
定义1-7 对撞结构或V-结构 在祖先图中，给定三元组{Vi,Vj,Vk}，如果Vi和Vj是邻接的，Vj和Vk是邻接的，但是Vi和Vk不是邻接的，则称该三元组构成非封闭的三元组。在一个非封闭的三元组{Vi,Vj,Vk}中，如果Vj是对撞节点且∃Z⊆V\{Vi,Vj,Vk}满足Vi⊥Vk|Z且﹁Vi⊥Vk|{Z∪Vj}，则三元组{Vi,Vj,Vk}构成V-结构。
类似于DAG中的d-分离，祖先图通过一种称为m-分离的图形标准来表示变量之间的条件独立关系。
定义1-8 m-分离（m-Separation） 在祖先图中，给定一条路径π，如果条件集Z满足如下两个条件之一，则π被Z阻断：
（1）π中存在一条子路径{Vi,Vj,Vk}，Vj是一个非对撞节点且Vj∈Z；
（2）π中存在Vi*→Vj←*Vk，Vj∉Z且Z中不存在Vj的子孙节点。
在祖先图中，节点Vi和Vj被变量集Z⊆V\{Vi,Vj}m-分离，当且仅当Vi和Vj之间的所有路径都被Z阻断。
定义1-9 最大祖先图（Maximal Ancestral Graph，MAG） 如果一个祖先图G满足条件：对于图中每对不邻接的节点X和Y存在一个集合Z，使得X和Y在Z上是m-分离的，则称该祖先图G为最大祖先图。
在最大祖先图中，每对不邻接的节点都对应一个条件独立性关系。由定义1-9可知，并不是所有祖先图都是最大祖先图。
例如，在图1-8a中，节点B和H不邻接，但并不存在一个变量集合Z，使得B节点和H节点在Z上是m-分离的，所以它不是一个最大祖先图。如果在节点B和H之间添加一条双向边↔使得节点B和H邻接，得到图1-8b，此时图中所有节点都是邻接的，因此该图是最大祖先图。如果添加单向边B→H，虽然所有节点也是相邻的，但是同时存在F↔H和F∈An(H)构成了一个几乎有向环，此时该图是一个非祖先图。同理，如果添加B←H，则存在E↔B和E∈An(B)，也构成了一个几乎有向环，此时该图也是一个非祖先图。
图1-8 祖先图与最大祖先图
众所周知，满足同样条件独立性和具有相同对撞结构的DAG对应同一个马尔可夫等价类。同理，隐变量和观测变量的独立性关系可能与多个MAG一致。MAG的等价类由部分祖先图表示。
定义1-10 部分祖先图（Partial Ancestral Graph，PAG） 在一个PAG中，一条边的两端可能有三种类型端点：
（1）不变箭头，记为“＞”，表示等价类中的所有MAG在该端点处有一个箭头；
（2）不变尾部，记为“-”，表示等价类中的所有MAG在该端点处都有一个尾部；
（3）可变端点，记为“o”，表示等价类中的某些MAG在该端点处有箭头，而其他MAG在该端点处有一个尾部。
在PAG中，边“o→”表示等价类中的MAG在该位置可能有→或↔的边；边“o-o”表示等价类中的MAG在该位置有一条→、←、↔或-的边；边“-”表示是在所有等价的MAG中该边的方向是“-”。如图1-9c所示，部分祖先图中存在边Qo→S，那么它的等价类中的所有MAG在该位置可以有Q→S和Q↔S的边，同理，图1-9c中存在边Io-oS，那么它的等价类中的所有MAG在该位置可以有I→S、I←S、I-S和I↔S的边。图1-9c中存在边H-L，那么它的等价类中的所有MAG在该位置都应该存在边H-L，因此，图1-9a和图1-9b都是部分祖先图1-9c的等价类最大祖先图。
图1-9 等价类最大祖先图和部分祖先图