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的子图，记为GA=（V， EA），即GA是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=i0，i1，…，in= j，如果满足条件：对k=1，2，…，n，有（ik-1，ik）∈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，其边缘概率密度函数分别为 fX（x）和 fY（y），联合概率密度函数为 fX，Y（x， y）.在给定Y的条件下， X 的条件概率密度函数为
如果对∀x， y，以下等式成立：
则称X 和Y独立，记为X ⊥Y.
如果对满足条件 fX（x）＞0的∀x，y，z，以下等式成立：
则称在给定X 的条件下，Y和Z条件独立，记为Y ⊥Z|X.
Whittaker[18]证明了条件独立性满足下面的块独立引理（或称交叉性质），定义了条件独立图模型并证明了条件独立图的分离定理.
命题 1.1（块独立引理） 如果（X，Y，Z1，Z2）是随机向量的一个分割，并且联合概率密度函数 f （·）是正定的，则下面两个结论等价：
(1)Y ⊥(Z1,Z2)|X;
（2）Y ⊥Z1|（X，Z2）和Y ⊥Z2|（X，Z1）.
块独立引理的重要性在于可以用两个变量成对条件独立的描述建立多个变量群体条件独立的描述.
定义1.2（条件独立图） 设变量集合（X1，X2，…，Xn），无向图G=（V，E），顶点集V={1，2，…，n}，其中顶点i表示随机变量Xi，两个顶点i和j之间存在无向边对应于在给定除i和j表示的变量外的所有其他变量的条件下，顶点i和j所表示的随机变量之间存在条件相依联系，称这样的图为条件独立图（Conditional Independence Graph，CIG）.
图 1.1 是一个条件独立图的示意图，顶点集V={1，2，3，4}表示随机变量集合（X1，X2，X3，X4），从图 1.1 中可知，在给定变量X1和X2的条件下，变量X3和X4不是条件独立的；而在给定变量X2和X4的条件下，变量X1和X3是条件独立的，因为在图1.1中，顶点X1和X3不是邻居.
图1.1 条件独立图
条件独立图主要描述变量之间的相依联系，特别是两个顶点是否相邻，如果不相邻，则描述它们是如何被分离的.Whittaker[18]提出的条件独立图的分离定理（或称整体Markov性质）从理论上证明了，不相邻的变量在仅给定分离集的条件下是独立的.
定理1.3（分离定理） 如果XA、XB和XC是由（X1，X2，…，Xn）中的不交子集组成的随机向量，且在（X1，X2，…，Xn）的条件独立图中，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 （图的相容性） 如果条件独立图GU=（V， EU）和有向非循环图G D=（V， E D）表示的条件独立结构是等价的，则称图GU和G D是相容的（Consistent）.
图1.2 一个交叉的例子
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.3 一个例子
1.2.3 多维时间序列图模型
1.多维时间序列的偏相关图
假设{Yi，t，t∈Z}（i∈V）是一个K维时间序列，其中顶点集V={1，2，…，K}.为定义时间序列{Yj，t}和{Yk，t（} j，k∈V）的偏相关关系，Dahlhaus[29]首先定义了偏误差过程{Yj|V\{j，k}，t}，用于表示从时间序列{Yj，t}中去掉除{Yk，t}外其他序列的线性影响后的残差序列
式中，
和
为使下式
值最小的μj和φj（u）.
定义1.10（时间序列的偏不相关） 考虑多维时间序列{Yi，t，t∈Z}（ i∈V），如果对于所有滞后阶数u∈Z，随机变量Yj|V\{j，k}，t和Yk|V\{j，k}，t+u都是不相关的，则称序列Yj和Yk（ j， k∈V）在给定剩余分量序列YV\{j，k}的条件下是偏不相关的，记为
定义1.11（偏相关图） 设{Yi，t，t∈Z}（i∈V）是一个多维时间序列，G=（V，E）是一个无向图.如果对于所有 j， k∈V，以下关系成立
则称G为{Yi，t，t∈Z}的偏相关图.
2.结构向量自回归模型的有向非循环图
在时间序列典型向量自回归（Canonical Vector Auto Regressive，CVAR）模型中，仅允许存在当前时刻变量与过去值的相依联系，残差通常表示存在同期相依联系.与之对应的结构向量自回归（VAR）模型允许存在当前时刻变量之间的同期相依联系，而假定残差不存在同期相依联系，模型的递归结构可以用有向非循环图描述.Reale[35]以多维时间序列的结构表示以及有效的参数化（即稀疏的参数结构）为目标考虑建模方法，提出了用有向非循环图辨识结构VAR模型的稀疏结构和因果关系.
定义1.12（VAR（p）模型） 设平稳过程{Yt， t∈Z}均值为0，对任意t，有
式中，Yt=（Y1，t，Y2，t，…，Yk，t）′，A1，A2，…，Ap为k×k矩阵.{Ut}为序列无关的随机向量序列，其数学期望E[Ut]=0，协方差矩阵Σ=E[UtUt′]，一般设Ut是多元正态随机向量.称{Yt，t∈Z}是均值为0的p阶VAR模型，其中称Yt=（Y1，t，Y2，t，…，Yk，t）′为当前变量（Current Variables）或同期变量（Contemporaneous Variables），称Yt-u=（Y1，t-u，…，Yk，t-u）′（u=1，2，…， p）为滞后变量（Lag Variables）.
定义1.13（结构VAR（p）模型） 式（1-10）两边左乘矩阵Φ0，Φ0使D=Φ0ΣΦ0′ 成为对角矩阵
式中，
，Φ0Ut=at，E[atat′]=D.称模型（1-11）为结构VAR（p）模型.
模型（1-11）的一种更常用的表示形式为
式中，I为k×k单位矩阵.
以下考虑模型（1-12）的图模型表示.
定义1.14（结构VAR（p）模型的条件独立图） 设平稳过程{Yt， t∈Z}为结构VAR（p）模型，图G=（V， E）的顶点集V 由Yt，Yt-1，…，Yt-p的分量组成.两个顶点Yi，t-u和Yj，t-v之间没有边相连当且仅当在给定除Yi，t-u和Yj，t-v外的所有其他变量的条件下Yi，t-u和Yj，t-v是条件独立的.假设模型（1-12）中at是多元正态随机向量，则条件独立表示条件偏自相关系数为0，即
式中，{Yk，t-ω}表示除Yi，t-u和Yj，t-u外所有到滞后阶数p的变量集合；h和l分别表示变量Yi，t-u和Yj，t-v在矩阵W 和ΣY中的标号，并且
，ΣY为图G中所有变量集合的协方差矩阵.则称图G为结构VAR（p）模型的条件独立图.
定义1.15（结构VAR（p）模型的有向非循环图[5]） 设平稳过程{Yt， t∈Z}为结构VAR（p）模型，图G=（V， E）的顶点集V 由Yt，Yt-1，…，Yt-p的分量组成，存在从Yi，t-u到Yj，t-v的有向边当且仅当下面两个条件之一成立：
（a） 0＜u-v≤p，矩阵
的第 j行第i列元素不为0；
（b） u=v，i≠ j，矩阵（ I-Φ0）的第 j行第i列元素不为0.
则称图G为结构VAR（p）模型的有向非循环图.