面向故障間格蘭杰因果發現的霍克斯過程研究

蔡瑞初，吳思宇，喬杰

（廣東工業大學 計算機學院，廣州 510006）

0 概述

故障事件序列由連續時間下的離散事件組成，常以服務器狀態日志、設備運行記錄、系統異常告警的形式出現在大型應用程序［1-3］、自動化系統［4-6］、通信網絡［7-8］等現實應用場景中。基于故障事件序列數據發現故障之間的格蘭杰因果關系，對研究故障機制、預測預防潛在故障［9-10］以及定位故障根因［11-12］等工作有重要的推動作用。以大型的通信網絡場景為例，由于具有網絡規模巨大、設備類型多樣等特點，單點故障極易引發大規模相關故障事件，通過人工難以對大量故障事件進行及時響應和定位根因。因此，基于歷史故障事件序列發現網絡故障類型之間的因果關系，有助于高效準確地定位告警根因，提高運維效率，降低運維成本。

然而故障事件序列所具有的數據稀疏、信息量少、時間精度低的特點，對現有的格蘭杰因果發現算法帶來許多挑戰。另外，在現實場景的應用中，為了保證算法結果的可靠性，降低線上應用風險，常要求模型算法能夠引入一些由專家標注、業務反饋得到的直接、非直接因果結構先驗（無環先驗、依賴性先驗、故障根因標注等），并在此基礎上進行格蘭杰因果關系發現。因此，如何有效引入結構先驗，是實現事件序列因果關系建模落地應用亟需解決的問題。

現有的許多工作被提出用于發現事件序列背后的因果關系，其中包括基于約束的時序快速因果推斷算法（time series Fast Causal Inference，tsFCI）［13］、瞬時條件獨立彼得-克拉克算法（Peter&Clark algorithm with Momentary Conditional Independence test，PCMCI）［14］、

基于轉移熵的方法［15-16］。將這類方法運用到故障事件序列因果發現場景，需要將故障事件序列數據轉化為等時間間隔中事件發生次數所組成的時間序列，這導致部分時間數據丟失。另一種更多應用于事件序列的因果發現場景的方法是多變量霍克斯過程［17-19］。這類方法利用點過程建模故障事件序列，利用由基礎強度和激發強度構成的強度函數刻畫格蘭杰因果機制，并利用稀疏正則項對事件間的影響強度參數進行稀疏約束，如乘法交替方向法［10］（Alternating Direction Method of Multipliers and Majorization Minimization，ADM4）和基于稀疏群套索正則的最大似然估計算法［8］（Maximum Likelihood Estimator with Sparse-Group-Lasso，MLE-SGL）。然而這類方法在優化過程中存在無法有效引入因果先驗、剔除間接因果影響、保證稀疏性的問題，使得結果可靠性不足，效果十分依賴于強度閾值的選擇。

針對現有模型存在的問題，本文提出一種面向故障序列的格蘭杰因果發現的霍克斯過程模型。在霍克斯過程模型基礎上，設計基于貝葉斯信息準則（Bayesian Information Criterion，BIC）的兩步結構優化算法，用于發掘故障事件序列背后的格蘭杰因果關系?；谪惾~斯信息準則構造的目標函數，以?0范數作為稀疏懲罰項，有效隔離間接因果效應，保證結構的稀疏性。為優化這一目標函數，將基于期望最大化（Expectation-Maximization，EM）算法的參數優化模塊與基于爬山法的結構搜索模塊相結合，提出兩步結構優化算法，通過迭代優化格蘭杰因果網絡參數和結構，在保證優化效率的同時，有效引入因果結構先驗，提高模型可靠性。而對于故障運維場景中時間記錄精度低的問題，將霍克斯過程模型擴展到離散時間域上，從強度函數和目標函數兩個角度，討論霍克斯模型在離散時間域和連續時間域上的關聯。

1 面向故障事件格蘭杰因果發現的霍克斯過程

本節將形式化定義本文重點解決的問題，進而從多變量點過程定義出發，介紹霍克斯過程，并給出霍克斯過程下格蘭杰因果的定義。

1.1 問題定義

在自動化系統的運維場景中，故障可以抽象為由類型和發生時間表示的事件，因此，系統在一段時間內發生采集到的故障告警記錄可以用事件序列形式化地表示。其中：V表示事件類型的集合；T表示事件序列的記錄時間范圍；(vn,tn)表示第n個事件，其發生在tn時刻，類型為vn。為了方便建模，事件序列可以等價地轉化為函數形式，用一個計數函數族C={Cv(t)|t∈T,v∈V}表示。其中：Cv(t)記錄了發生在時刻t之前的v類事件的數量；dCv=Cv(t+dt)-Cv(t)。事件類型之間的格蘭杰因果結構則能用有向圖G=(N,E)表示。其中：E表示因果邊的集合。因此，對于這個事件序列的格蘭杰因果發現問題，給出如下定義：

定義1利用給定事件序列的觀測數據E=發現不同事件類型V背后的因果結構G=(N,E)。

1.2 多變量霍克斯過程

多變量點過程作為一個隨機過程模型，常被用于建模刻畫多種類型的事件序列之間的影響機制。多變量點過程的建模核心是構造各個事件類型發生的強度函數λv(t)：

本文所采用的霍克斯過程［20］是點過程的一種特殊形式，常被用于建模事件之間的相互激發的機制。霍克斯過程考慮了一種特定類型的強度函數，該函數測量過去事件對于當前時刻強度的激發程度，這種激發影響隨時間變化而變化，具體形式如下：

在本文中，使用不同衰減系數δk的指數函數作為基函數，即κk(t)=δkexp(-δkt)。

在現實場景中，故障序列數據往往以一定的時間間隔進行采集，如每秒更新一次數據，存在記錄精度不夠的情況。因此，本文工作還關注離散時域下事件序列的建模。在離散時間域下，T變為一個離散時間域T={0,Δt,2Δt,…,T}，其中Tt-={t′|t′∈T,t′≤t-Δt}。因此，事件序列Xv,t=Cv(t+Δt)-Cv(t)可以用時間序列X={Xv,t|v∈V,t∈T}表示，表示時間間隔[t,t+Δt)中事件的發生次數。在這種情況下，給出離散時間域下霍克斯過程模型的擴展，其強度函數的表示形式如下：

在離散時間域的事件序列建模中，λv(t)表示的是每個時間間隔[t,t+Δt)中的平均強度，Xv,t取值服從期望為λv(t)Δt的泊松分布。而在理想狀態下，記錄時間精度提高，時間間隔趨近于0，則有Δt→dt，Xv,t→dCv(t)，那么離散時間域強度函數（式（4））則會轉化為連續時間下的強度函數（式（3））。

1.3 霍克斯過程中的格蘭杰因果關系

在文獻［21］中，作者對點過程格蘭杰因果關系的定義［22］，揭示了霍克斯過程的強度函數和格蘭杰因果結構之間的關系，具體如下：

定理1假設一個霍克斯過程其條件強度函數如式（2）所示，且滿足格蘭杰因果結構G=(N,E)，則格蘭杰因果邊v'→v?E，當且僅當所有t∈T滿足?v',v(t)=0。

根據定理1 可以進一步得出，在模型（式（3））中，v' 不是v的格蘭杰原因當且僅當對于所有k∈{1,2,…,K}滿足αv',v,k=0。那么在給定因果結構G=(N,E)下，能夠對霍克斯過程的強度函數（式（3））做進一步簡化：

在離散時間域下，強度函數的形式為：

其中：Pv表示給定格蘭杰因果結構G=(N,E)下，事件類型v的格蘭杰原因事件類型的集合，即v在G中的父節點。

2 霍克斯過程下的貝葉斯評分準則

基于定理1 可知，為了獲得合理的因果結構，稀疏性約束是至關重要的。因此，本文在似然度的框架下，基于貝葉斯信息準則構造目標函數，將?0范數作為稀疏懲罰項，以保證結構的稀疏性。

由于在連續時間域下，霍克斯過程的似然函數已經在許多工作中被很好地定義，為了將離散時間域的事件序列建模也引入到本文的模型框架中，本節針對離散時間域，從泊松分布的角度構造似然度函數。在本文模型中，似然度是關于G和Θ的函數，給定事件序列觀測數據，對數似然函數如式（7）所示：

進一步地，通過對Δt取極限，令Δt→dt，能夠將離散時間域下的似然函數擴展到連續時間域上，從而得到連續時間域下霍克斯過程的似然函數：

然而只將對數似然函數作為目標函數容易產生過多的冗余因果邊。為了保證結構的稀疏性，將貝葉斯信息準則的懲罰項引入本文的目標函數中，從而得到如下目標函數：

其中：p=|V|+K|E|表示模型的參數數目［23］；m表示在T中發生的所有的事件數目。BIC 懲罰項等價于關于模型參數的?0范數正則項。p為參數的?0范數，而正則項的權重能夠隨樣本數目變化而調整，具有更強的適應性。

3 基于EM 和爬山法的兩步稀疏優化算法

本節將介紹如何優化上述帶?0稀疏約束的目標函數。雖然現有工作針對這一問題已經提出了多種方法，如ADM4 方法采用低秩約束對鄰接矩陣進行約束，MLE-SGL 方法進一步引入了對因果強度的稀疏性正則化，但它們的性能很大程度上取決于稀疏性正則化權重的選擇或結構剪枝的閾值，并且現有方法存在無法引入直接、間接因果性先驗的不足。

針對上述問題，本文提出基于EM 和爬山法的兩步稀疏優化算法（Two Step Sparse Optimization，TSSO），迭代進行參數估計和結構搜索的步驟，以保證學到一個稀疏的因果結構，并提供了在結構搜索過程中引入先驗信息的方法。算法求解部分可以分為結構評分模塊和結構搜索模塊。結構評分模塊通過給定因果結構，利用EM 優化參數計算結構的BIC評分，即(G,Θ；E)；結構搜索模塊利用爬山法搜索BIC評分最高的因果結構，即

3.1 格蘭杰因果結構評分模塊——EM 算法

在格蘭杰因果結構評分模塊中，對于給定的因果結構G，本文利用EM 算法估計參數Θ，計算結構G的BIC 評分基于EM 算法的思想，通過引入隱變量z∈N×T×{1,2,…,K}，用于告警事件發生的具體原因，推導出參數Θ的迭代優化公式。

參數μv的迭代公式為：

而參數αv',v,k的迭代公式為：

在格蘭杰因果結構評分模塊中，利用上述公式迭代更新給定結構G的模型參數，直至收斂，具體的算法流程如算法1 所示。

算法1因果結構評分模塊

需要注意的是，由于目標函數的非凸性質，EM算法存在收斂到局部最優解的風險，因此在實踐中，通常會嘗試不同的參數初始起點進行優化，并取評分最高的參數作為結果。

3.2 格蘭杰因果結構搜索模塊——爬山法

為搜索最優的格蘭杰因果結構，本文參照文獻［24］，使用爬山法，以通過EM 的優化得到的BIC評分為基礎，選出BIC 評分——最高的結構G，具體的算法流程如算法2 所示。

算法2因果結構搜索模塊

在算法2 中，V(G′)表示G′的鄰居結構，即通過對結構G′進行一次增邊、刪邊或轉邊的操作，得到的結構的集合。在結構搜索模塊中，通過初始化搜索結構（步驟1）、加入對搜索空間的約束（步驟7）等形式，靈活地引入直接、非直接的因果先驗。具體地，在步驟7 中，通過將不滿足無環條件的格蘭杰因果結構剔除的方式，引入因果無環先驗性先驗。

現有一些關于BIC 一致性以及爬山法的相關工作，也為本文算法的可靠性提供了理論支撐。根據文獻［23］中的證明可知，在給定足夠大的樣本量的情況下，霍克斯過程BIC 評分的一致性是漸進成立的。而文獻［25］中給出證明指出，由于BIC 得分所具有的一致性屬性，這種基于爬山法的結構優化算法能夠找到真實的因果圖。

3.3 復雜度分析

對本文算法的時間復雜度進行分析。在結構評分模塊中，計算復雜度主要取決于EM 算法。EM 算法的迭代次數為常數，因此，給定一個因果結構G，EM 算法的時間復雜度為O(Km3e)。其中：K代表核函數中的基函數κk的數目；m是指發生事件的總數；e表示因果結構G中因果邊的數目。需要注意的是，如果使用基函數κk滿足κk(t1+t2)=κk(t1)κk(t2)，那么EM 的計算復雜度就能降低為O(Km2e)，因為每個發生的事件的強度都可以只用前一個發生事件的強度來計算。因此，在實踐中，常使用指數形式函數作為基函數，降低計算復雜度O(Km2e)。為了使結果更具普適性，下面的分析將不考慮選擇特殊基函數的情況。

在結構搜索模塊中，時間復雜度主要取決于每個事件類型對應的原因類型的數目。根據BIC 評分的一致性假設，因果結構搜索會從邊數為0 的空圖開始，在找到所有的E條因果邊后結束。那么，最壞的情況下，即當所有的因果邊都指向同一個事件類型時，算法的時間復雜度最高，具體為：

在這種情況下，由于本文每次加邊只需要更新原因事件類型集合發生變化的事件類型對應的評分即可，因此每加一條邊的時間復雜度為O(Km3|V|e)。而最好的情況是因果邊都均勻地分布在每一種事件類型上，因此每一種類型的原因事件類型數目為在這種情況下，本文算法的時間復雜度將降低為：

在具體的工程實現過程中，得益于似然度函數能夠按事件類型進行分解的特性，結構搜索模塊能夠通過并行化計算進一步提高計算效率。

4 實驗

本節使用模擬數據以及兩個真實場景的數據對模型進行評估。將TSSO 與主流的事件序列格蘭杰因果發現方法進行對比，其中包括基于獨立性檢驗的PCMCI 算法、基于低秩約束的霍克斯過程模型的ADM4 算法，以及在此基礎上使用更加復雜強度函數的MLE-SGL 算法。本文采用F1 評分（F）作為評價指標，計算公式如下：

其中：TP表示算法預測正確的因果邊的數目；FP為算法預測錯誤的因果邊的數目；FN為真實因果結構中沒有被算法發現的因果邊的數目。

4.1 模擬數據實驗

在模擬數據實驗中設計5 個控制變量實驗，通過指數形式的霍克斯過程生成數據，強度函數為其中αv',v表示v'對v的激發強度。每次實驗都會隨機生成格蘭杰因果結構以及霍克斯過程參數。5 個實驗變量包括：不同的基礎強度采樣范圍｛（0.000 05，0.000 1），（0.000 1，0.000 5），（0.000 5，0.001），（0.001，0.005），（0.005，0.01）｝，激發強度系數取值范圍｛（0.01，0.03），（0.03，0.05），（0.05，0.07），（0.07，0.09），（0.1，0.3），（0.3，0.5），（0.5，0.7），（0.7，0.9）｝，平均入度｛0.5，1，1.5，2，3，4｝，樣本數量｛4 000，6 000，8 000，10 000，15 000，20 000，25 000，30 000｝，以及事件類型數目｛10，20，30，40，50｝。其中：加粗的部分為控制變量實驗中的默認設置；β默認為0.1。此外，為使數據更加接近真實場景情況，在模擬生成的事件發生時間的基礎上加上一個采樣出的高斯噪聲，并將事件發生事件的精度設置為1 s，模擬現實中故障記錄過程中存在時間偏差、精度不足的情況。

圖1 展示了不同基礎強度取值范圍下的實驗結果，可以看出，基礎強度對本文方法的影響不大，而對于其他方法，尤其是ADM4 和MLE-SGL，隨著基礎強度增大，其效果下降明顯。這是因為隨著基礎強度增大，自發發生事件的占比變多，容易與不同事件類型之間的相互影響相混淆，引入冗余的因果邊。這說明TSSO 中，基于貝葉斯信息準則的?0范數懲罰項能夠更有效剔除冗余的因果關系。

圖1 針對基礎強度的控制實驗結果Fig.1 Results of control experiments on base intensity

圖2 顯示了不同激發強度取值下的實驗，可以看出，由于激發強度取值跨度大，各種方法對于激發強度的取值大小都比較敏感。這是因為：直觀上，當激發強度取值過小，一些由于事件類型相互影響產生的事件容易與自發發生的事件混淆，導致因果邊的漏檢測、誤檢測；而由于模擬數據時間精度低，且存在記錄噪聲的情況，當激發強度過大時，原因和結果事件容易落在同一個時間間隔中（模擬數據為1 s），增大判斷格蘭杰因果方向的難度。在這種情況下，本文方法仍優于其他對比方法，表明本文方法具有較好的穩定性。

圖2 針對激發強度的控制實驗結果Fig.2 Results of control experiments on excitation intensity

如圖3 所示，本文方法在小樣本量的情況下仍然保持較好的性能表現，這主要是因為結構評分函數中的BIC 罰項能夠適應不同的數據樣本量，保證不同樣本量下BIC 評分的一致性。

圖3 針對樣本數量的控制實驗結果Fig.3 Results of control experiments on sample size

由圖4 和圖5 可以看出，事件類型數目和平均出度對于本文模型的影響不大，驗證了本文方法在格蘭杰因果結構規模及密度下的魯棒性。

圖4 針對事件類型數目的控制實驗結果Fig.4 Results of control experiments on number of event type

圖5 針對平均出度的控制實驗結果Fig.5 Results of control experiments on average out-degree

4.2 真實數據實驗

真實數據實驗分別在無線基站網絡告警場景和城際蜂窩網絡告警場景數據上進行測試。對比方法包括PCMCI 和MLE-SGL、ADM4。在實驗中，除了F1 評分之外，進一步引入精確率（P）和召回率（R）作為模型性能的評價指標，計算公式如下：

其中，真實結構標簽通過專家標注得到。

4.2.1 無線基站網絡告警場景

在無線基站網絡場景中，實驗所使用的數據采集于一個包含2 476 個基站設備的無線網絡，時間跨度為37 d，包含605 217 條故障告警記錄，涉及18 種告警類型。

需要注意的是，基于專家知識，在這個場景，故障之間的格蘭杰因果是滿足無環的先驗的。因此，在TSSO 的結構搜索模塊中（步驟7）加入結構無環的約束，將不滿足無環約束的因果結構從搜索空間中剔除。加入有向無環約束后的算法用TSSO-DAG表示。由表1 可以看出，本文方法在準確率和召回率上，相比對比方法都有明顯優勢（加粗數據表示最優值）。F1 評分比對比方法中表現最優的ADM4 高出了16.45%。這說明基于BIC 評分能夠在更有效地剔除冗余因果邊的同時，發現難以被其他方法檢測到格蘭杰因果關系。

表1 無線網絡故障數據上的實驗結果Table 1 Experimental results on wireless network alarm data

4.2.2 城際蜂窩網絡告警場景

為進一步測試算法的性能，在一個更具挑戰性的城際蜂窩網絡告警場景數據集上進行實驗。在這個場景中，數據是從配置了3 087 個網元設備的蜂窩網中采集的，包含228 030 條告警記錄，涉及18 種告警類型，時間跨度為7 d。在此數據集中，存在時間跨度小、樣本分布不平衡的情況。實驗結果如表2所示。其中：加粗數據表示最優值；TSSO 為不加無環先驗的算法；TSSO-DAG 表示加入無環約數的算法。

表2 蜂窩網絡告警數據集實驗結果Table 2 Experimental results on cellular network alarm dataset

由表2 可以看出，在召回率的指標上，各種方法的表現都不夠好，這可能是因為數據分布不均勻、采集時間跨度短，導致一些強度較弱的格蘭杰因果關系所對應的數據沒有被采集到。通過與其他方法對比可以得出，即使沒有引入無環先驗，TSSO 的結果仍明顯優于其他對比方法，尤其是在精確率指標上提升明顯。這說明本文方法能夠更有效地保證結構的稀疏性，剔除冗余、間接的格蘭杰因果關系。而從TSSO-DAG 的結果可以看出，在加入了無環性約束后，模型的表現有了進一步的提升，在F1 評分上，較對比方法中ADM4 高出15.18%，在精確率指標上，較沒有無環約束的TSSO 提升了13.49%。可以看出，在這個場景中，無環先驗的引入對于提升模型的可靠性有很大的幫助。

同時由表2 也可以看出，對于這種更具挑戰性的場景，先驗知識與反饋的引入就顯得尤為重要。因此，為進一步討論先驗知識引入的有效性和必要性，在此真實數據的基礎上設計兩個實驗，模擬兩種故障運維場景中常見的先驗、反饋形式，對本文方法進行測試。

1）引入根因標注案例反饋的實驗

在運維場景中，對于一段時間內出現的一系列告警，業務專家會標記出告警對應的根因并反饋給運維人員做進行處理。在本文方法中，能夠通過記錄所有案例中根因及其后繼節點，并將存在不滿足該條件的因果圖從搜索空間中剔除掉的方式，對模型進行矯正，從而引入根因標注案例反饋信息。本文通過對已知的因果圖中的告警類型進行隨機采樣（每次采樣選取5～10 個告警類型）模擬一段時間內出現的告警類型，并通過因果圖定位其中的根因，以此作為模擬根因標注案例反饋數據。如圖6 所示，相比于原始結果，少量的根因標注案例反饋的引入就能讓TSSO 的性能有顯著的提升，最終能使模型的F1 評分提高22.43%，其中精確率達到0.78，提升了20.98%。

圖6 引入根因標注案例反饋的實驗結果Fig.6 Results of experiment of introducing root cause feedback

2）引入因果依賴性先驗的實驗

依賴性先驗是指對于兩個故障類型，已知其存在因果依賴關系但是無法判斷其因果方向。在TSSO 中，通過修改結構搜索終止條件的方式，引入依賴性先驗，保證輸出的因果圖的骨架包含先驗告警對。在模擬依賴性先驗數據方面，本文對已知因果結構的骨架的邊集合進行采樣，模擬依賴性先驗數據，進行實驗。如圖7 所示，橫坐標表示格蘭杰因果骨架的采樣的比例，即先驗的故障對數目占真實因果邊的比例?？梢钥闯觯蕾囆韵闰炓雱t更側重于提高模型召回率，能夠在保證精確率穩定的情況下，使召回率得到顯著提升，且F1 評分提升29.93%。

圖7 引入因果依賴性先驗的實驗結果Fig.7 Results of experiment of introducing dependence priors

5 結束語

現有基于事件序列的格蘭杰因果發現算法難以有效引入因果先驗，保證所學因果結構的稀疏性，在稀疏、時間精度低故障事件數據上，存在結果不穩定、可靠性差的問題。本文提出一種面向故障序列的因果發現的霍克斯過程模型。將霍克斯過程拓展到離散時間域，并依據貝葉斯信息準則構造以?0范數為稀疏懲罰項的目標函數，保證因果結構稀疏性。同時通過結合EM 算法與爬山法，提出兩步迭代優化算法，發掘故障事件背后的格蘭杰因果關系，在保證優化效率的情況下，有效引入因果結構先驗，進一步提高模型的可靠性。實驗結果表明，與ADM4、MLE-SGL、TSSO 和PCMCI 算法相比，本文方法在模擬數據和真實數據下具有更高的準確率。后續將通過引入深度點過程模型的框架，使用表達能力更強的模型捕捉機制更復雜的因果關系。