傳播動態學的主動監控：一種組稀疏貝葉斯學習方法

雷鋒網 AI 科技評論按：本文作者吉林大學博士生裴紅斌，本文為對他發表在 AAAI 2018 論文的獨家解讀稿件，未經許可不得轉載。

Group Sparse Bayesian Learning for ActiveSurveillance on Epidemic Dynamics

傳播動態學的主動監控：一種組稀疏貝葉斯學習方法

https://arxiv.org/pdf/1712.00328.pdf

裴紅斌是吉林大學三年級在讀博士，師從吉林大學楊博教授。他近期的研究是利用機器學習技術解決人類傳染病的監控、預測、和控制問題，為公共衛生提供人工智慧支持。他與香港浸會大學劉際明教授合作，相關工作發表在 TPAMI 2017 和 AAAI 2018。

傳播現象是廣泛存在於真實世界的一類動態學過程，例如疾病傳播、信息擴散等。預測傳播動態學（epidemic dynamics）對於理解和控制傳播具有非常重要的意義。基於動態系統模型，預測傳播動態學可直觀地定義為：已知系統的當前狀態估計其未來的狀態。可以看到，預測的基礎在於監控，即及時地收集和報告系統的當前狀態。

在實際應用中傳播動態學的監控非常困難，因為真實的傳播現象通常涉及巨大的時空範圍，有限的人力物力等監控資源難以覆蓋大規模的監控範圍。例如，由於毗鄰緬甸以及自身地理環境，雲南省騰衝市是我國瘧疾的重發區，2005 至 2011 年共確認 7,835 名瘧疾患者。然而，騰衝市疾控中心（CDC）執行日常病例調查的工作人員卻僅有幾人！騰衝市幅員 5,845 平方公里（略小於上海市），共有 18 個鄉、221 個村、658,207 位居民。顯然有限的人力無法滿足及時、全面監控瘧疾的需求。在其他傳播監控中，資源有限的挑戰也普遍存在，例如空氣質量檢測[1]、互聯網輿情感知[2]、城市交通監控[3]。

主動監控（active surveillance）是解決上述資源有限問題的可行策略：選擇並監控動態系統中的少數關鍵節點，進而利用這些節點的信息來預測整個系統未來的傳播動態學。主動監控策略僅關注系統中的少數關鍵節點，能滿足有限監控資源的約束，並較準確地預測傳播動態學，因此有著重要的實踐價值。實現主動監控的核心的問題是：在系統中如何評價和識別對傳播預測最關鍵的節點？該問題非常具有挑戰性，因為系統中各部分間的交互結構是高度異構且隱藏的。

現有的感測器部署（sensor deployment）工作大多假設系統中的交互結構已知，從而將關鍵節點識別問題轉換為有限候選集上的組合優化問題，進而使用啟發式演算法對其求解，如次模最大化（sub-modular maximization）。然而在真實傳播現象中，這種交互結構（有時被稱作擴散網路）往往無法被觀察，如傳染病在隱藏的人口接觸網路上傳播[4]。另一類方法是利用高斯過程來預測未觀測節點的狀態，並使用主動學習策略（如信息熵、互信息）來識別對預測最重要的節點[5]。高斯過程是黑盒模型，傳播機制等先驗知識不易被融入，也就是說，高斯過程的參數學習倚重於大量的訓練數據。然而，真實傳播現象積累的歷史數據往往是很有限的。

本文主動監控框架

我們首先提出面向傳播動態學預測的主動監控框架。這個一般性的框架分為三步：

Step 1: 在 N 個感興趣的節點上收集傳播動態學數據。

Step 2: 從所收集數據中挖掘哨兵網路（sentinel network），其中哨兵節點（sentinel node）個數 k 由預算決定。

Step 3: 基於哨兵網路和 k 個哨兵上的監控數據，預測全部 N 個節點未來的傳播動態學。

後兩步是主動監控框架的關鍵，我們在接下來對其進行詳細介紹。

問題定義

考慮一次持續時間為 T 的傳播，其在 N 個興趣點上被觀測，觀測數據D為 T 乘 N 的矩陣。D中元素可能是連續實數（如某區域空氣污染物濃度）或離散數值（如某條公路是否阻塞）。使用矩陣 Ds 表示 k 個哨兵節點上的監控數據，即假若某節點為哨兵則Ds與D中該列元素相同，否則該列為零向量。f(Ds,S)表示利用監控數據Ds預測傳播動態學的動態系統函數，，其中 N 乘 N 的矩陣S是哨兵矩陣。哨兵矩陣是動態系統函數中一組關鍵參數，刻畫哨兵節點對其他節點的影響。換句話說，實現主動監控的關鍵在於獲取動態系統函數f(Ds,S)。我們分別形式化定義上述框架中後兩步的計算問題。

問題一哨兵識別：如何從數據D中識別哨兵節點並挖掘哨兵網路S？

問題二哨兵預測：基於哨兵節點上收集的數據Ds，如何利用哨兵網路S預測所有 N 個節點未來的傳播動態學？

哨兵識別

我們的基本思想非常直觀：在動態系統中，對其他節點沒有影響力的節點是不重要的；反之，重要的節點對其他節點有顯著的影響力，可主導整個系統未來的狀態，所以這類節點應被選為哨兵節點。對應於哨兵矩陣 S（S 編碼哨兵節點對其他節點的影響），我們可通過推斷行稀疏結構來確定一個節點是否關鍵。換言之，不重要節點在 S 中應對應於稀疏行，即行中絕大多數元素為零；重要的節點則應對應於非稀疏行。圖1以線性動態系統為例演示了這一基本思想。

基於這一思路我們提出了一個新穎的指標，γ 值，來評估節點的重要性：在哨兵矩陣的先驗結構和後驗結構中都重要的節點是對預測傳播動態學關鍵的節點。具體地，γ 值定義為哨兵矩陣先驗中的超參數，該參數同樣側寫了哨兵矩陣後驗結構。數學定義如下，

公式中是第 i 個節點的 γ 值。接下來我們從先驗和後驗的視角分別介紹該指標。

先驗視角

從基本思想出發，我們期望哨兵網路具備行稀疏的結構，即非零元素集中於哨兵所對應的行中。因此，我們採用零均值的多元高斯分布作為的哨兵網路的先驗：

通過上述建模，第 i 行的所有元素（即網路中由i節點所發出的邊）被緊密地聯繫在一起，且被共同的超參數 γ 所控制。這類從數據中推斷的超參數被稱作自動相關確定（automatic relevancedetermination）機制[5]。當第i行對應的  γ 較小時，i 節點所發出的邊會變弱，則 i 節點是不重要的節點，那麼將其捨棄不會對預測的準確率造成太大影響。

後驗視角

如上所述， γ 值同樣反映了哨兵矩陣的後驗結構。我們在線性連續系統和邏輯離散系統中分別建模了哨兵矩陣，這兩類系統被廣泛用於刻畫真實世界中的傳播現象。兩種系統中建模所對應的圖模型如下圖所示。

將哨兵矩陣看做隱變數，我們採用期望最大化 EM 演算法和變分近似近似方法求解超參數。我們分析 γ 求解公式後發現，γ 值實際刻畫了節點自身對其他節點的影響力，以及其影響力的不確定性。我們提出了一種後向選擇演算法 SNMA 來篩選對預測最佳的哨兵集合。該演算法開始於全部的 N 個興趣節點，每次迭代後捨棄一個節點，直到僅剩 k 個節點作為哨兵節點（k 的數量由預算決定）。每次迭代被捨棄的節點是對應 γ 值最小的節點。

哨兵預測

一旦通過 SNMA 演算法獲得了哨兵矩陣的後驗結構，我們可利用監控數據（即僅在 k 個哨兵節點上收集的數據）來預測整個系統 N 個節點的傳播動態學。使用星號下標表示一個新的監控樣本，系統未來的狀態可由下面預測分布給出。

實驗結果

我們在人工合成數據集和真實數據集上分別驗證了該方法。採用兩種對比演算法，基於互信息的高斯過程（GPs-MI）和 group lasso。GPs-MI 是一種流行的感測器部署方法[6]，其效果好於實驗設計方法，如 A-, D-, 和 E-優化設計。Group lasso 是一個典型的組稀疏學習方法，與我們所設計的 Bayesian group sparse 方法類似。該演算法本身不具備主動監控能力，但可嵌入我們提出的主動監控框架中。

我們使用失敗率（failure rate）和均方根誤差 RMSE 兩個指標來衡量演算法效果。在人工數據實驗中，失敗率刻畫是否找到了正確的哨兵節點。RMSE 衡量哨兵預測結果與真實傳播動態學間的誤差。我們採用了5折交叉驗證方法。從圖3可以看出，在人工合成數據中，無論是線性連續系統還是邏輯離散系統，我們提出的 SNMA 演算法有最低的失敗率和 RMSE。

真實數據實驗

我們首先使用 2009 年香港 H1N1 流感數據做實驗驗證。這次大流感在香港共造成 36,000 人感染，290 人病情嚴重，80 人死亡。我們研究該次流感自 2009 年 6 月 1 日後 105 天時間的感染病例。香港包含 18 個行政區域，因此將香港建模為包含 18 個節點的動態系統。因為 2009 年 H1N1 流感的感染期為三天，我們依據三天聚合數據後可得到 N=18，T=35 的流感動態學。

上圖是不同演算法的哨兵預測結果，橫軸是所使用哨兵節點的數量，縱軸為對傳播的預測誤差。我們的方法 SNMA 在絕大多數情況下都有最好的預測結果。下圖更直觀地展示了不同演算法的預測曲線，我們選擇哨兵數量為 8 的情況作為個案研究來比較不同演算法表現。黑色星表示 2009 年香港 H1N1 流感的真實傳播趨勢。對三種方法，我們都使用 8 月 15 日前數據訓練模型，預測之後的傳播動態學。

SNMA 演算法所選擇對預測 2009 年 H1N1 最重要的 8 個哨兵節點對應的空間分布如下圖所示。其中紅??泡標識哨兵節點，氣泡下的紅圈指示該節點的監控重要程度，?色點為不需要監控的區域。和我們直覺相符大多哨兵節點集中於人口密集的港島和九龍地區。同樣有趣的是西貢、離島等偏遠、人口稀少的區域也有較高的監控重要性，可能是由於這裡 H1N1 流感的傳播模式與港島和九龍不同。

類似地，我們還在 2005-2009 年騰衝市瘧疾爆發數據和 2015 年某中文在線社區中信息擴散的真實數據上驗證了該方法。實驗顯示我們提出方法 SNMA 優於 GPs-MI 和 group lasso。SNMA 演算法的優勢主要在於：

1.該演算法是基於模型的，這使得先驗知識易於集成並且訓練更為高效；

2.由於採用 Bayesian 框架建模了數據和參數中的不確定性，該演算法可有效處理高噪音和訓練數據不充分的問題。

參考文獻

[1] Hsieh,Hsun-Ping, Shou-De Lin, and Yu Zheng. 2015. Inferring air quality for stationlocation recommendation based on urban big data. In Proceedings of the 21th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining. Sydney,Australia: ACM.

[2] Yan Chen, Hadi Amiri, Zhoujun Li, andTat-Seng Chua. Emerging topic detection for organizations from microblogs. InProceedings of the 36th International ACM SIGIR Conference on Research andDevelopment in Information Retrieval. ACM, 2013.

[3] Natali Ruchansky, Mark Crovella, andEvimaria Terzi. Matrix completion with queries. In Proceedings of the 21th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining. ACM,2015.

[4]Bo Yang, Hongbin Pei, Hechang Chen, Jiming Liu, and Shang Xia. Characterizingand discovering spatiotemporal social contact patterns for healthcare[J]. IEEEtransactions on pattern analysis and machine intelligence, 2017, 39(8):1532-1546.

[5]MacKay DJC: Probable networks and plausible predictions—a review of practicalBayesian methods for supervised neural networks. Network, 1995, 6(3): 469-505.

[6]Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placementsin Gaussian processes: Theory, efficient algorithms and empirical studies.Journal of Machine Learning Research, 9(Feb):235–284, 2008.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！