多維時間序列Granger因果圖Markov性

魏岳嵩

（淮北師范大學 數(shù)學科學學院，安徽 淮北 235000 ）

1 引言

自從1969年Granger［1］提出Granger因果性概念以來，Granger因果性已成為衡量系統(tǒng)變量間動態(tài)關(guān)系的重要依據(jù)，在金融經(jīng)濟、信號處理、神經(jīng)網(wǎng)絡(luò)、醫(yī)學等［2-5］眾多領(lǐng)域都有著廣泛的應(yīng)用.Granger指出：如果在其余變量信息給定的情況下，融入某一變量的信息有助于對另一變量將來值的預(yù)測，則該變量是另一變量的原因.當前對系統(tǒng)變量間Granger因果關(guān)系的研究多采用兩變量Granger因果性檢驗法［6-7］，由于經(jīng)常忽視其他重要解釋變量所產(chǎn)生的影響，常會導致偽因果關(guān)系的出現(xiàn).此外，兩變量Granger因果性檢驗只能檢驗兩變量間長期的因果關(guān)系，卻無法度量變量間的即時因果關(guān)系，這些都限制了該檢驗方法的使用范圍.

近年來，作為分析和處理多元數(shù)據(jù)重要工具的圖模型方法已經(jīng)被廣泛用于時間序列問題的研究.利用圖模型方法研究時間序列變量之間的Granger因果性，能夠直觀地呈現(xiàn)變量間的多種因果關(guān)系，同時也可檢驗多個變量間的Granger 因果關(guān)系.Eichler［8］首先利用圖模型方法研究變量間的因果關(guān)系，建立了Granger 因果圖，并在Granger 因果圖中融入變量間的即時因果關(guān)系.魏岳嵩等［9］則討論了Granger 因果圖結(jié)構(gòu)的辨識問題，提出了Granger因果圖的條件互信息辨識方法.在此基礎(chǔ)上，本文進一步討論Granger因果圖的相關(guān)性質(zhì).

2 多維時間序列Granger因果圖

令V是一非空有限集，圖G=(V,E)是一有序集，其中V中的元素稱為圖的頂點，而E={(a,b)|a,b∈V}中的元素稱為邊.一條邊(a,b)稱為圖G中的無向邊，若(a,b)∈E并且(b,a)∈E,在圖中用a-b表示，此時稱a和b為鄰居.a的鄰居集記為ne(a).一條邊 (a,b)稱為圖G中的有向邊，如果 (a,b)∈E但 (b,a)?E,在圖中用a→b表示，此時稱a為b的父親，b為a的孩子.a的父親集記為pa(a)，a的孩子集記為ch(a).若圖G中既有有向邊又有無向邊，則稱其為混合圖.長度為n的從a到b的路徑是指由不同頂點組成的從a到b的序列 {a=i0,i1,…,in=b}，滿足對所有的k=1,2,…,n都有 (ik-1,ik)∈E.如果對于所有的k=1,2,…,n都有(ik-1,ik)∈E但(ik,ik-1)?E，則稱該路徑為有向路徑.若在圖G中存在由a到b的有向路徑，則稱a是b的祖先，b是a的后代.a的所有祖先組成的集合稱為a的祖先集，記為an(a).

如果A?V,EA?E，則稱圖GA=(A,EA)為圖G=(V,E)的子圖.如果EA=E?(A×A)，則稱GA是由A導出的G的子圖.此外，用分別表示集合A的父親集、孩子集和鄰居集.

設(shè)X(t)=(X1(t),X2(t),…,Xk(t))T是定義在概率空間(Ω,F,P)上的k維隨機過程，V={1,2,…,k}為相應(yīng)的指標集.對任意A?V，以XA={Xa,a∈A}表示XV=X(t)的多變量子過程，以X(t)={X(s),s＜t}表示在時刻t之前該隨機過程的信息集，以G=(V,Ed,Eu)表示頂點集為V的混合圖，其中Ed?{(u,v)∈V×V|u≠v}為有向邊集，而Eu?{(u,v)∈V×V|u≠v}為無向邊集.

假設(shè)序列X(t)滿足以下條件：

（C1）X(t)=(X1(t),X2(t),…,Xk(t))T是概率空間(Ω,F,P)上的平穩(wěn)隨機過程.

（C2）序列中所有變量都是可觀測的，即滿足因果充分性條件.

（C3）所有變量的聯(lián)合分布關(guān)于某一乘積測度是絕對連續(xù)的，并且具有正的連續(xù)概率密度.

定義1（Granger因果性）設(shè)A和B是V的不相交子集，XA和XB是XV的相應(yīng)子過程，XV(t)表示在時刻t的所有有關(guān)V的信息集.

（2）如果XB(t)⊥XA(t)|{XV(t),XV{A,B}(t)}，則稱XA和XB關(guān)于XV(t)是非同期因果的，記為XA?XB[XV].

定義2（Granger因果圖）設(shè)X(t)=(X1(t),X2(t),…,Xk(t))T是定義在概率空間(Ω,F,P)上的k維平穩(wěn)隨機過程，如果以下條件成立，則以{X(t)}各分量為頂點集V={1,2,…,k}的混合圖G=(V,Ed,Eu)稱為Granger因果圖.

（1）對任意i,j∈V且i≠j有

（2）對任意i,j∈V且i≠j有

3 Granger因果圖的Markov性

設(shè)G=(V,E)是Granger因果圖，a和b是G中的兩個頂點，π=(e1,e2,…,en)是a和b之間的一條路徑，其中a=i0,i1,…,in=b.若路徑 π 包含結(jié)構(gòu) →ik←, -ik←, →ik-之一，則稱點ik是路徑π 上的p-對沖點，否則稱ik是路徑π 上的非p-對沖點.如果路徑π 中所有的中間點都為對沖點，則該路徑為完全對沖路徑.設(shè)C?V{a,b}，如果條件（1）{ik|ik是π上的非p-對沖點}?C≠?和條件（2）{ik|ik是π上的p-對沖點}??C≠?至少有一個成立，則稱在圖G中路徑 π 被C阻斷，否則稱在給定C的條件下路徑π 在圖G中連通.如果在圖G中a和b之間的所有路徑都被C阻斷，則稱在圖G中C p-分離a和b，否則稱C p-連通a和b.設(shè)A,B和C是V中兩兩互不相交子集，其中A和B非空，若對任意a∈A和b∈B，在G中C p- 分離a和b，則稱C在G中p- 分離A和B.

定義3（Granger 因果圖Markov 性）設(shè)G=(V,E)是時間序列Granger 因果圖，如果對于所有a，b∈V,a≠b有a→b?E?Xa■Xb[XV]及a-b?E?Xa?Xb[XV]，則稱圖G滿足成對Granger因果Markov 性，記為 PGCM.如果對于所有a∈V有，則稱G滿足局部Granger 因果Markov 性，記為LGCM.如果對于V的所有子集A有G滿足塊遞歸Granger因果Markov性，記為BGCM.

定理1設(shè)G=(V,E)是Granger 因果圖，A，B和C是V中兩兩互不相交子集，且V=A?B?C（其中A和B非空），則A和B被C分離當且僅當A中任意點a和B中任意點b之間不存在完全對沖路徑.

證明（必要性）假設(shè)點a∈A和b∈B，π=(e1,e2,…,en)是G中a和b之間的一條完全對沖路徑，且a=i0,i1,…,in=b.為簡單起見，不妨設(shè)該路徑是A和B之間所有完全對沖路徑中的最短路徑，則對所有的k∈{1,2,…,n-1}，都有ik∈C，否則，若存在r∈{1,2,…,n-1}，使得ir∈A（或者ir∈B），則此時(er+1,er+2,…,en)（或者(e1,e2,…,er)）是A和B之間一條比 π 更短的完全對沖路徑，矛盾.由于路徑 π 是完全對沖路徑，因此路徑中的所有中間點都為對沖點，從而該路徑在給定C的條件下是連通路徑，這和已知條件矛盾，因此A中任意點a和B中任意點b之間不存在完全對沖路徑.

（充分性）已知A中任意點a和B中任意點b之間不存在完全對沖路徑，假設(shè)A和B不被C分離，則存在a1∈A和b1∈B，以及a1和b1之間的一條關(guān)于C連通的路徑π=(e1,e2,…,en).不妨設(shè)該路徑是A和B之間所有連通路徑中的一條最短路徑，則對所有的k∈{1,2,…,n-1}，都有ik∈C.否則，存在r∈{1,2,…,n-1}使得ir∈A（或者ir∈B），此時 (er+1,er+2,…,en)（或者 (e1,e2,…,er)）是A和B之間一條比 π更短的連通路徑，矛盾.由于路徑π 關(guān)于C是連通的，且所有的中間點都屬于C，因此所有的中間點都為對沖點，從而π 是完全對沖路徑，和已知矛盾，因此A和B被C分離.

定理2設(shè)G=(V,E)是Granger 因果圖，A和B是V的兩個互不相交子集，則A和B被V{A,B}分離當且僅當 (A? ch(A))?(B?ch(B))=?且ne(A?ch(A))?(B? ch(B))=?.

證明（必要性）已知A和B被V{A,B}分離，如果(A?ch(A))?(B?ch(B))≠?，則存在i∈(A?ch(A))且i∈(B?ch(B)).當i∈A時，由于A和B互不相交，此時必有i∈ch(B)，從而A和B不能被V{A,B}分離；當i∈ ch(A)且i∈B時，顯然A和B不能被V{A,B}分離；當i∈ ch(A)且i∈ch(B)時，必存在a∈A和b∈B使得a→i←b，此 時A和B也 不 能 被V{A,B} 分 離.綜 上 可 知 (A?ch(A))?(B?ch(B))=?.若ne(A? ch(A))?(B? ch(B))≠?，則存在i∈ne(A?ch(A))且i∈(B? ch(B))，即存在a∈A使得a-i或者存在a∈A及k?A使得a→k-i，同時i∈B或者存在b∈B使得b→i成立，顯然無論哪種情況，A和B都不能被V{A,B}分離，因此必有ne(A?ch(A))?(B?ch(B))=?.

（充分性）已知 (A?ch(A))?(B?ch(B))=?且ne(A?ch(A))?(B? ch(B))=?，設(shè)A和B不被V{A,B}分離，則存在a∈A和b∈B以及a和b之間的一條路徑 π=(e1,e2,…,en)，且該路徑關(guān)于C是連通的.不妨設(shè)該路徑是A和B之間所有連通路徑中的最短路徑，則由定理1知對所有的k∈{1,2,…,n-1}都有ik∈C且π是完全對沖路徑，故 π 必是以下4 種形式之一：a→c←b，a→c-b，a-c←b，a→c-d←b，顯然有(A? ch(A))?(B? ch(B))≠?或者ne(A? ch(A))? (B? ch(B))≠?，矛盾.因此A和B被V{A,B}分離.

定理3設(shè)G=(V,E)是Granger 因果圖，π=(e1,e2,…,en)是a和b之間的一條路徑，其中a=i0,i1,…,in=b，記C={ik|ik是π上的對沖點}，則{i0,i1,…,in}?an({a,b}?C).

證明當n=1 時結(jié)論顯然成立.下面考慮n≥2 的情形.以m表示路徑π 中對沖點的個數(shù)，現(xiàn)對m利用歸納法證明命題結(jié)論.

若m=0 即C=?時，路徑π只有兩種可能形式，即存在r滿足0≤r≤n，π 為a=i0←…←ir-1←ir→ir+1→…→in=b，或者存在r滿足0≤r≤n，π為a=i0←…←ir-1-ir→ir+1→…→in=b，顯然對于兩種情況都有{i0,i1,…,in}?an({a,b}?C).

當m＞ 0 時，設(shè)k∈C即k=ir(0＜r＜n)是 π 上的對沖點，則 π1=(e1,e2,…,er)是G中從a到k的路徑，π2=(er+1,er+2,…,en)是G中從k到b的路徑.令C1={is∈C|0＜s＜r}和C2={is∈C|r＜s＜n}分別是 π1和π2上的對稱點集，則兩個路徑中的對沖點數(shù)都少于m個，由歸納假設(shè)知{i0,i1,…,ir}?an({a,k}?C1)及{ir,ir+1,…,in}?an({k,b}?C2).由于k∈C，因此an({a,k}?C1)?an({a,b}?C)，an({k,b}?C2)?an({a,b}?C)，即{i0,i1,…,in}?an({a,b}?C).

定理4設(shè)G=(V,E)是Granger 因果圖,a和b是G中的兩個頂點，C?V{a,b}，則C在圖G中p- 分離a和b當且僅當C在圖Gan(a?b?C)中p- 分離a和b.

證明（必要性）假設(shè)在圖Gan(a?b?C)中，在給定C的條件下，a和b之間存在連通路徑 π.由于Gan(a?b?C)?G，故 π 也是G中相對于條件集C的連通路徑，矛盾.因此C在圖Gan(a?b?C)中p- 分離a和b.

（充分性）假設(shè)π=(e1,e2,…,en)是圖G中a和b之間關(guān)于C的連通路徑，令D是π 上的對沖點集，則由定理 3 知 π 也是圖Gan(a?b?D)中的一條路徑.由于D?an(C)，故Gan(a?b?D)?Gan(a?b?C)，從而 π 也是圖Gan(a?b?C)中關(guān)于C的連通路徑，矛盾.即C在圖G中p- 分離a和b.

推論1設(shè)G=(V,E)是Granger因果圖，A,B和C是V中兩兩互不相交子集，其中A和B非空，則C在圖G中p- 分離A和B當且僅當C在圖Gan(A?B?C)中p- 分離A和B.

定理5設(shè)X(t)=(X1(t),X2(t),…,Xk(t))T,t∈Z是n維平穩(wěn)隨機過程，G=(V,E)是相應(yīng)的時間序列Granger因果圖，A，B和C是V中兩兩互不相交子集，且V=A?B?C，則BGCM?LGCM?PGCM.

證明由［10］定理3.1知，當X(t)滿足條件（C3）時有

由［8］引理A.2知，BGCM?LGCM?PGCM.

［1］GRANGER C.Investigating causal relations by econometric models and cross-spectral methods［J］.Econometrica，1969，37：424-438.

［2］KAMINSKI M，DING Z，TRUCCOLO W，et al.Evaluating causal relations in neural systems：Granger causality，directed transfer function and statistical assessment of significance［J］.Biological Cybernetics，2001，85：145-157.

［3］KONYA L.Exports and growth：Granger causality analysis on OECD countries with a panel approach［J］.Economic Model?ling，2006，23（6）：978-992.

［4］NAGARAJAN R，UPRETI M.Comment on causality and pathway search in microarray time series experiment［J］.Bioinfor?matics，2008，24（7）：1029-1032.

［5］郭水霞.頻域格蘭杰因果關(guān)系及其在信號處理中的應(yīng)用［J］.計算機工程與應(yīng)用，2008，44（3）：5-9.

［6］MUKHOPADHYAY N，CHATTERJEE S.Causality and pathway search in microarray time series experiment［J］.Bioinfor?matics，2007，23：442-449.

［7］FIEUWS S，VERBEKE G，MOLENBERGHS G.Random-effects models for multivariate repeated measures［J］.Statistical Methods in Medical Research，2007，16（5）：387-397.

［8］EICHLER M.Granger causality and path diagrams for multivariate time series［J］.Journal of Econometrics，2007，137：334-353.

［9］魏岳嵩，田錚.多維時間序列Granger因果性的一種圖模型學習方法［J］.系統(tǒng)科學與數(shù)學，2011，31（5）：549-558.

［10］LAURITZEN SL.Graphical models［M］.Oxford：Oxford University Press，1996.