1.2 多维时间序列图模型的基本知识

本节介绍相关的图模型基本概念和定理（Whittaker ^[18] ，Lauritzen ^[19] ）及几类多维数据和多维时间序列的图模型.

1.2.1 图模型基本概念和术语

图 G =（ V ， E ）由两个集合组成，其中有限集合 V 被称为顶点集，边集 E 由从顶点集中取出的元素对组成.如果 E 同时包含（ i ， j ）和（ j ， i ），则称顶点之间存在无向边.如果只有（ i ， j ）∈ E ，则称顶点之间存在从 i 到 j 的有向边（或箭头）.称（ i ， i ）∈ E 为一个环.称只有无向边的图为无向图.

本书只考虑不包含环的简单图.图中每一个顶点均用一个圆圈表示；如果有两个顶点之间存在无向边，就用线连接对应的两个圆圈；用箭头表示有向边.这就构成了图的图形表示.

设 A 是图 G =（ V ， E ）的顶点集 V 的一个非空子集，以 A 作为顶点集，以两端点均在 A 中的边的全体为边集的子图，被称为由 A 导出的 G 的子图，记为 G _A =（ V ， E _A ），即 G _A 是 G 的导出子图（Induced Subgraph）.

每一对不同的顶点均有一条有向边或无向边相连的图被称为完全图（Complete Graph）.如果某子集的导出子图是完全图，再加入一个顶点会导致不完全子图，则称这个子集是一个团（Clique）.

如果存在从 i 指向 j 的有向边，则称 i 为 j 的父亲（Parent）， j 为 i 的孩子（Child）. j 的父亲集记为pa（ j ）， i 的孩子集记为ch（ i ）.如果 i 和 j 之间存在无向边，则称 i 和 j 是相邻的或是邻居（Neighbour），顶点 i 的邻居集表示为ne （ i ）.如果 i 和 j 之间既没有有向边，也没有无向边，则称 i 和 j 不相邻.

分别用pa （ A ），ch （ A ），ne （ A ）表示集合 A 中元素的那些不在 A 中的父亲集、孩子集、邻居集： .

子集 A 的边界bd （ A ）是 V \ A 中 A 的父亲集或邻居集，即bd （ A ）=pa （ A ） ∪ ne （ A ）.

不同顶点组成的从 i 到 j 的序列 i = i ₀ ， i ₁ ， … ， i _n = j ，如果满足条件：对 k =1，2， … ， n ，有（ i _{k -1} ， i _k ）∈ E ，则称该序列为从 i 到 j 的长为 n 的路.如果存在从 i 到 j 的路，则称 i 导致 j ，记为 .如果 和 同时成立，则称 i 和 j 是相连的，记为 i⇌ j .如果图中所有顶点都是相连的，则称图为连通图.⇌是一个等价关系，对应等价类[ i ]，其中 j ∈[ i ]⇔ i⇌ j ，是图 G 的连通元素.如果存在从 i 到 j 的有向路 i → … → j ，并且 i = j ，则称路组成了一个循环.

如果所有从 i 到 j 的路都通过子集 C ⊆ V ，则称 C 为一个（ i ， j ） 分离子（Separator）.在无向图中， C 是一个（ i ， j ）分离子当且仅当[ i ] _{V \ C} ≠[ j ] _{V \ C} .如果对于每一对 i ∈ A ， j ∈ B ， C 都是（ i ， j ）分离子，则称子集 C 从 A 分离 B .

如果顶点 i 满足条件 和 ，则称 i 为 j 的祖先（Ancestor），记为an （ j ）； i 的后代de（ i ）为满足条件 和 的顶点 j .非后代为nd（ i ）= V \（de（ i ） ∪i ）.

如果对于所有 i ∈ A ，有bd （ i ）⊆ A ，则称 A 是一个祖先集（Ancestralset）.在一个有向图中，集合 A 是祖先集当且仅当对于所有 i ∈ A ，an（ i ）⊆ A 成立.在一个无向图中，祖先集是连通元素的并集.祖先集的交集仍为祖先集.因此，对于任意的顶点集 A ，存在最小的包含 A 的祖先集，记为an（ A ）.

1.2.2 多维数据的图模型

1.条件独立图

设连续型随机变量 X 和 Y ，其边缘概率密度函数分别为 f _X （ x ）和 f _Y （ y ），联合概率密度函数为 f _{X ， Y} （ x ， y ）.在给定 Y 的条件下， X 的条件概率密度函数为

如果对∀ x ， y ，以下等式成立：

则称 X 和 Y 独立，记为 X ⊥ Y .

如果对满足条件 f _X （ x ）＞0的∀ x ， y ， z ，以下等式成立：

则称在给定 X 的条件下， Y 和 Z 条件独立，记为 Y ⊥ Z | X .

Whittaker ^[18] 证明了条件独立性满足下面的块独立引理（或称交叉性质），定义了条件独立图模型并证明了条件独立图的分离定理.

命题 1.1 （块独立引理） 如果（ X ， Y ， Z ₁ ， Z ₂ ）是随机向量的一个分割，并且联合概率密度函数 f （·）是正定的，则下面两个结论等价：

(1) Y ⊥( Z ₁ , Z ₂ )| X ;

（2） Y ⊥ Z ₁ |（ X ， Z ₂ ）和 Y ⊥ Z ₂ |（ X ， Z ₁ ）.

块独立引理的重要性在于可以用两个变量成对条件独立的描述建立多个变量群体条件独立的描述.

定义1.2 （条件独立图） 设变量集合（ X ₁ ， X ₂ ， … ， X _n ），无向图 G =（ V ， E ），顶点集 V ={1，2， … ， n }，其中顶点 i 表示随机变量 X _i ，两个顶点 i 和 j 之间存在无向边对应于在给定除 i 和 j 表示的变量外的所有其他变量的条件下，顶点 i 和 j 所表示的随机变量之间存在条件相依联系，称这样的图为条件独立图（Conditional Independence Graph，CIG）.

图 1.1 是一个条件独立图的示意图，顶点集 V ={1，2，3，4}表示随机变量集合（ X ₁ ， X ₂ ， X ₃ ， X ₄ ），从图 1.1 中可知，在给定变量 X ₁ 和 X ₂ 的条件下，变量 X ₃ 和 X ₄ 不是条件独立的；而在给定变量 X ₂ 和 X ₄ 的条件下，变量 X ₁ 和 X ₃ 是条件独立的，因为在图1.1中，顶点 X ₁ 和 X ₃ 不是邻居.

条件独立图主要描述变量之间的相依联系，特别是两个顶点是否相邻，如果不相邻，则描述它们是如何被分离的.Whittaker ^[18] 提出的条件独立图的分离定理（或称整体Markov性质）从理论上证明了，不相邻的变量在仅给定分离集的条件下是独立的.

定理1.3 （分离定理） 如果 X _A 、 X _B 和 X _C 是由（ X ₁ ， X ₂ ， … ， X _n ）中的不交子集组成的随机向量，且在（ X ₁ ， X ₂ ， … ， X _n ）的条件独立图中， B 中的每个顶点和 C 中的每个顶点都被子集 A 分离，则有

2.有向非循环图

对条件独立图中的每个边，都给出一个方向，就引入了变量之间相依联系的因果关系概念.Whittaker ^[18] 证明了，在假设图中的顶点为完全排序的条件下可以排除存在循环的情况.有向非循环图仅包含有向边（→），并且所有的路都不组成循环，具有简单的因果可解释性和建模要求的性质，在实际中常用来表示各种数据的产生过程.

定义 1.4 （有向非循环图） 在条件独立图 G =（ V ， E ）中，给定无向边的方向，用于表示变量之间因果关系的方向，则 G 成为有向图.如果在 G 中从任意顶点 i ∈ V 出发，沿相同方向的边走下去，不能回到 i ，称这样的图为有向非循环图（DAG）.

对于一个有向非循环图 G =（ V ， E ）， G 中所有顶点表示的多维随机变量的联合概率密度函数可以被分解成每个顶点表示的变量在给定其父亲顶点表示的变量的条件下的概率密度函数的乘积

在许多情形下，比较容易得到的是描述系统中变量之间条件独立性的条件独立图.但是，能够表示系统因果结构的是有向非循环图.为达到因果推断的目的，必须先考虑哪些可能的有向非循环图会产生观测到的条件独立图.这就需要首先知道这些条件独立图是如何由有向非循环图产生的.

定义1.5 （交叉） 在有向非循环图 G =（ V ， E ）中，如果有 i → j ← k 且在 i 和 k 之间没有边，则称 i → j ← k 是一个交叉（Immorality）.

图1.2（a）就是一个交叉的例子.

定义1.6 （Wermuth条件） 如果一个有向图 G 不包含如图1.2（a）所示结构的子图，则称图 G 满足Wermuth条件.

同一个模型的条件独立图和有向非循环图表示之间存在如下关系.

定义 1.7 （图的相容性） 如果条件独立图 G ^U =（ V ， E ^U ）和有向非循环图 G ^D =（ V ， E ^D ）表示的条件独立结构是等价的，则称图 G ^U 和 G ^D 是相容的（Consistent）.

Whittaker ^[18] 证明了，与图1.2（a）（即定义1.5中的交叉）相容的无向图是图1.2（b）.

定义1.8 （去交叉图） 设 是一个有向非循环图， G ^m =（ V ， E ^m ）是一个无向图，其顶点集和 的相同，边集包含 中的所有边和从 中消除禁止的Wermuth条件需要增加的边，则称 G ^m 是 的去交叉图（Moral Graph）.

定理1.9 有向非循环图 与其去交叉图 G ^m 具有同样的Markov性质.

因此，要建立可能产生观测到的条件独立图的有向非循环图，首先要对边安排方向，然后考虑是否去掉那些为了消除禁止的 Wermuth 条件而增加的边.与有向非循环图交叉后得到唯一的条件独立图不同，一般没有唯一的与原来的条件独立图相容的有向非循环图（Spirtes等 ^[9] ，Pearl ^[67] ）.一个例子如图1.3所示，图（a）为一个条件独立图，图（b）～（d）为与图（a）相容的部分有向非循环图.

1.2.3 多维时间序列图模型

1.多维时间序列的偏相关图

假设{ Y _{i ， t} ， t ∈ Z }（ i ∈ V ）是一个 K 维时间序列，其中顶点集 V ={1，2， … ， K }.为定义时间序列{ Y _{j ， t} }和{ Y _{k ， t} （} j ， k ∈ V ）的偏相关关系，Dahlhaus ^[29] 首先定义了偏误差过程{ Y _{j | V \{ j ， k }， t} }，用于表示从时间序列{ Y _{j ， t} }中去掉除{ Y _{k ， t} }外其他序列的线性影响后的残差序列

式中， 和 为使下式

值最小的 μ _j 和 φ _j （ u ）.

定义1.10 （时间序列的偏不相关） 考虑多维时间序列{ Y _{i ， t} ， t ∈ Z }（ i ∈ V ），如果对于所有滞后阶数 u ∈ Z ，随机变量 Y _{j | V \{ j ， k }， t} 和 Y _{k | V \{ j ， k }， t + u} 都是不相关的，则称序列 Y _j 和 Y _k （ j ， k ∈ V ）在给定剩余分量序列 Y _{V \{ j ， k }} 的条件下是偏不相关的，记为

定义1.11 （偏相关图） 设{ Y _{i ， t} ， t ∈ Z }（ i ∈ V ）是一个多维时间序列， G =（ V ， E ）是一个无向图.如果对于所有 j ， k ∈ V ，以下关系成立

则称 G 为{ Y _{i ， t} ， t ∈ Z }的偏相关图.

2.结构向量自回归模型的有向非循环图

在时间序列典型向量自回归（Canonical Vector Auto Regressive，CVAR）模型中，仅允许存在当前时刻变量与过去值的相依联系，残差通常表示存在同期相依联系.与之对应的结构向量自回归（VAR）模型允许存在当前时刻变量之间的同期相依联系，而假定残差不存在同期相依联系，模型的递归结构可以用有向非循环图描述.Reale ^[35] 以多维时间序列的结构表示以及有效的参数化（即稀疏的参数结构）为目标考虑建模方法，提出了用有向非循环图辨识结构VAR模型的稀疏结构和因果关系.

定义1.12 （VAR（ p ）模型） 设平稳过程{ Y _t ， t ∈ Z }均值为0，对任意 t ，有

式中， Y _t =（ Y _{1， t} ， Y _{2， t} ， … ， Y _{k ， t} ）′， A ₁ ， A ₂ ， … ， A _p 为 k × k 矩阵.{ U _t }为序列无关的随机向量序列，其数学期望 E [ U _t ]=0，协方差矩阵 Σ = E [ U _t U _t ′]，一般设 U _t 是多元正态随机向量.称{ Y _t ， t ∈ Z }是均值为0的 p 阶VAR模型，其中称 Y _t =（ Y _{1， t} ， Y _{2， t} ， … ， Y _{k ， t} ）′为当前变量（Current Variables）或同期变量（Contemporaneous Variables），称 Y _t-u =（ Y _{1， t-u} ， … ， Y _{k ， t-u} ）′（ u =1，2， … ， p ）为滞后变量（Lag Variables）.

定义1.13 （结构VAR（ p ）模型） 式（1-10）两边左乘矩阵 Φ ₀ ， Φ ₀ 使 D = Φ ₀ ΣΦ ₀ ′ 成为对角矩阵

式中， ， Φ ₀ U _t = a _t ， E [ a _t a _t ′]= D .称模型（1-11）为结构VAR（ p ）模型.

模型（1-11）的一种更常用的表示形式为

式中， I 为 k × k 单位矩阵.

以下考虑模型（1-12）的图模型表示.

定义1.14 （结构VAR（ p ）模型的条件独立图） 设平稳过程{ Y _t ， t ∈ Z }为结构VAR（ p ）模型，图 G =（ V ， E ）的顶点集 V 由 Y _t ， Y _{t -1} ， … ， Y _t-p 的分量组成.两个顶点 Y _{i ， t-u} 和 Y _{j ， t-v} 之间没有边相连当且仅当在给定除 Y _{i ， t-u} 和 Y _{j ， t-v} 外的所有其他变量的条件下 Y _{i ， t-u} 和 Y _{j ， t-v} 是条件独立的.假设模型（1-12）中 a _t 是多元正态随机向量，则条件独立表示条件偏自相关系数为0，即

式中，{ Y _{k ， t-ω} }表示除 Y _{i ， t-u} 和 Y _{j ， t-u} 外所有到滞后阶数 p 的变量集合； h 和 l 分别表示变量 Y _{i ， t-u} 和 Y _{j ， t-v} 在矩阵 W 和 Σ _Y 中的标号，并且 ， Σ _Y 为图 G 中所有变量集合的协方差矩阵.则称图 G 为结构VAR（ p ）模型的条件独立图.

定义1.15 （结构VAR（ p ）模型的有向非循环图 ^[5] ） 设平稳过程{ Y _t ， t ∈ Z }为结构VAR（ p ）模型，图 G =（ V ， E ）的顶点集 V 由 Y _t ， Y _{t -1} ， … ， Y _t-p 的分量组成，存在从 Y _{i ， t-u} 到 Y _{j ， t-v} 的有向边当且仅当下面两个条件之一成立：

（a） 0＜ u-v ≤ p ，矩阵 的第 j 行第 i 列元素不为0；

（b） u = v ， i ≠ j ，矩阵（ I-Φ ₀ ）的第 j 行第 i 列元素不为0.

则称图 G 为结构VAR（ p ）模型的有向非循环图. Pxij+D+tEjz9sRe/CjKt8WuUV4WSRKeTPJtpCbsFxwJy0l8CiQjr3HkrQvFOqhPP