0
| 本文作者： 不靈叔 | 2018-03-20 15:53 |
雷鋒網(wǎng) AI 科技評論按：本文作者吉林大學(xué)博士生裴紅斌，本文為對他發(fā)表在 AAAI 2018 論文的獨家解讀稿件，未經(jīng)許可不得轉(zhuǎn)載。
Group Sparse Bayesian Learning for ActiveSurveillance on Epidemic Dynamics
傳播動態(tài)學(xué)的主動監(jiān)控：一種組稀疏貝葉斯學(xué)習(xí)方法
裴紅斌是吉林大學(xué)三年級在讀博士，師從吉林大學(xué)楊博教授。他近期的研究是利用機(jī)器學(xué)習(xí)技術(shù)解決人類傳染病的監(jiān)控、預(yù)測、和控制問題，為公共衛(wèi)生提供人工智能支持。他與香港浸會大學(xué)劉際明教授合作，相關(guān)工作發(fā)表在 TPAMI 2017 和 AAAI 2018。
傳播現(xiàn)象是廣泛存在于真實世界的一類動態(tài)學(xué)過程，例如疾病傳播、信息擴(kuò)散等。預(yù)測傳播動態(tài)學(xué)（epidemic dynamics）對于理解和控制傳播具有非常重要的意義。基于動態(tài)系統(tǒng)模型，預(yù)測傳播動態(tài)學(xué)可直觀地定義為：已知系統(tǒng)的當(dāng)前狀態(tài)估計其未來的狀態(tài)。可以看到，預(yù)測的基礎(chǔ)在于監(jiān)控，即及時地收集和報告系統(tǒng)的當(dāng)前狀態(tài)。
在實際應(yīng)用中傳播動態(tài)學(xué)的監(jiān)控非常困難，因為真實的傳播現(xiàn)象通常涉及巨大的時空范圍，有限的人力物力等監(jiān)控資源難以覆蓋大規(guī)模的監(jiān)控范圍。例如，由于毗鄰緬甸以及自身地理環(huán)境，云南省騰沖市是我國瘧疾的重發(fā)區(qū)，2005 至 2011 年共確認(rèn) 7,835 名瘧疾患者。然而，騰沖市疾控中心（CDC）執(zhí)行日常病例調(diào)查的工作人員卻僅有幾人！騰沖市幅員 5,845 平方公里（略小于上海市），共有 18 個鄉(xiāng)、221 個村、658,207 位居民。顯然有限的人力無法滿足及時、全面監(jiān)控瘧疾的需求。在其他傳播監(jiān)控中，資源有限的挑戰(zhàn)也普遍存在，例如空氣質(zhì)量檢測[1]、互聯(lián)網(wǎng)輿情感知[2]、城市交通監(jiān)控[3]。
主動監(jiān)控（active surveillance）是解決上述資源有限問題的可行策略：選擇并監(jiān)控動態(tài)系統(tǒng)中的少數(shù)關(guān)鍵節(jié)點，進(jìn)而利用這些節(jié)點的信息來預(yù)測整個系統(tǒng)未來的傳播動態(tài)學(xué)。主動監(jiān)控策略僅關(guān)注系統(tǒng)中的少數(shù)關(guān)鍵節(jié)點，能滿足有限監(jiān)控資源的約束，并較準(zhǔn)確地預(yù)測傳播動態(tài)學(xué)，因此有著重要的實踐價值。實現(xiàn)主動監(jiān)控的核心的問題是：在系統(tǒng)中如何評價和識別對傳播預(yù)測最關(guān)鍵的節(jié)點？該問題非常具有挑戰(zhàn)性，因為系統(tǒng)中各部分間的交互結(jié)構(gòu)是高度異構(gòu)且隱藏的。
現(xiàn)有的傳感器部署（sensor deployment）工作大多假設(shè)系統(tǒng)中的交互結(jié)構(gòu)已知，從而將關(guān)鍵節(jié)點識別問題轉(zhuǎn)換為有限候選集上的組合優(yōu)化問題，進(jìn)而使用啟發(fā)式算法對其求解，如次模最大化（sub-modular maximization）。然而在真實傳播現(xiàn)象中，這種交互結(jié)構(gòu)（有時被稱作擴(kuò)散網(wǎng)絡(luò)）往往無法被觀察，如傳染病在隱藏的人口接觸網(wǎng)絡(luò)上傳播[4]。另一類方法是利用高斯過程來預(yù)測未觀測節(jié)點的狀態(tài)，并使用主動學(xué)習(xí)策略（如信息熵、互信息）來識別對預(yù)測最重要的節(jié)點[5]。高斯過程是黑盒模型，傳播機(jī)制等先驗知識不易被融入，也就是說，高斯過程的參數(shù)學(xué)習(xí)倚重于大量的訓(xùn)練數(shù)據(jù)。然而，真實傳播現(xiàn)象積累的歷史數(shù)據(jù)往往是很有限的。
我們首先提出面向傳播動態(tài)學(xué)預(yù)測的主動監(jiān)控框架。這個一般性的框架分為三步：
Step 1: 在 N 個感興趣的節(jié)點上收集傳播動態(tài)學(xué)數(shù)據(jù)。
Step 2: 從所收集數(shù)據(jù)中挖掘哨兵網(wǎng)絡(luò)（sentinel network），其中哨兵節(jié)點（sentinel node）個數(shù) k 由預(yù)算決定。
Step 3: 基于哨兵網(wǎng)絡(luò)和 k 個哨兵上的監(jiān)控數(shù)據(jù)，預(yù)測全部 N 個節(jié)點未來的傳播動態(tài)學(xué)。
后兩步是主動監(jiān)控框架的關(guān)鍵，我們在接下來對其進(jìn)行詳細(xì)介紹。
考慮一次持續(xù)時間為 T 的傳播，其在 N 個興趣點上被觀測，觀測數(shù)據(jù) D 為 T 乘 N 的矩陣。D中元素可能是連續(xù)實數(shù)（如某區(qū)域空氣污染物濃度）或離散數(shù)值（如某條公路是否阻塞）。使用矩陣 Ds 表示 k 個哨兵節(jié)點上的監(jiān)控數(shù)據(jù)，即假若某節(jié)點為哨兵則 Ds 與 D 中該列元素相同，否則該列為零向量。f(Ds,S)表示利用監(jiān)控數(shù)據(jù) Ds 預(yù)測傳播動態(tài)學(xué)的動態(tài)系統(tǒng)函數(shù)，，其中 N 乘 N 的矩陣 S 是哨兵矩陣。哨兵矩陣是動態(tài)系統(tǒng)函數(shù)中一組關(guān)鍵參數(shù)，刻畫哨兵節(jié)點對其他節(jié)點的影響。換句話說，實現(xiàn)主動監(jiān)控的關(guān)鍵在于獲取動態(tài)系統(tǒng)函數(shù)f(Ds,S)。我們分別形式化定義上述框架中后兩步的計算問題。
問題一哨兵識別：如何從數(shù)據(jù) D 中識別哨兵節(jié)點并挖掘哨兵網(wǎng)絡(luò) S？
問題二哨兵預(yù)測：基于哨兵節(jié)點上收集的數(shù)據(jù) Ds，如何利用哨兵網(wǎng)絡(luò) S 預(yù)測所有 N 個節(jié)點未來的傳播動態(tài)學(xué)？
我們的基本思想非常直觀：在動態(tài)系統(tǒng)中，對其他節(jié)點沒有影響力的節(jié)點是不重要的；反之，重要的節(jié)點對其他節(jié)點有顯著的影響力，可主導(dǎo)整個系統(tǒng)未來的狀態(tài)，所以這類節(jié)點應(yīng)被選為哨兵節(jié)點。對應(yīng)于哨兵矩陣 S（S 編碼哨兵節(jié)點對其他節(jié)點的影響），我們可通過推斷行稀疏結(jié)構(gòu)來確定一個節(jié)點是否關(guān)鍵。換言之，不重要節(jié)點在 S 中應(yīng)對應(yīng)于稀疏行，即行中絕大多數(shù)元素為零；重要的節(jié)點則應(yīng)對應(yīng)于非稀疏行。圖1以線性動態(tài)系統(tǒng)為例演示了這一基本思想。
基于這一思路我們提出了一個新穎的指標(biāo)，γ 值，來評估節(jié)點的重要性：在哨兵矩陣的先驗結(jié)構(gòu)和后驗結(jié)構(gòu)中都重要的節(jié)點是對預(yù)測傳播動態(tài)學(xué)關(guān)鍵的節(jié)點。具體地，γ 值定義為哨兵矩陣先驗中的超參數(shù)，該參數(shù)同樣側(cè)寫了哨兵矩陣后驗結(jié)構(gòu)。數(shù)學(xué)定義如下，
公式中是第 i 個節(jié)點的 γ 值。接下來我們從先驗和后驗的視角分別介紹該指標(biāo)。
從基本思想出發(fā)，我們期望哨兵網(wǎng)絡(luò)具備行稀疏的結(jié)構(gòu)，即非零元素集中于哨兵所對應(yīng)的行中。因此，我們采用零均值的多元高斯分布作為的哨兵網(wǎng)絡(luò)的先驗：
通過上述建模，第 i 行的所有元素（即網(wǎng)絡(luò)中由i節(jié)點所發(fā)出的邊）被緊密地聯(lián)系在一起，且被共同的超參數(shù) γ 所控制。這類從數(shù)據(jù)中推斷的超參數(shù)被稱作自動相關(guān)確定（automatic relevancedetermination）機(jī)制[5]。當(dāng)?shù)趇行對應(yīng)的 γ 較小時，i 節(jié)點所發(fā)出的邊會變?nèi)酰瑒t i 節(jié)點是不重要的節(jié)點，那么將其舍棄不會對預(yù)測的準(zhǔn)確率造成太大影響。
如上所述， γ 值同樣反映了哨兵矩陣的后驗結(jié)構(gòu)。我們在線性連續(xù)系統(tǒng)和邏輯離散系統(tǒng)中分別建模了哨兵矩陣，這兩類系統(tǒng)被廣泛用于刻畫真實世界中的傳播現(xiàn)象。兩種系統(tǒng)中建模所對應(yīng)的圖模型如下圖所示。
將哨兵矩陣看做隱變量，我們采用期望最大化 EM 算法和變分近似近似方法求解超參數(shù)。我們分析 γ 求解公式后發(fā)現(xiàn)，γ 值實際刻畫了節(jié)點自身對其他節(jié)點的影響力，以及其影響力的不確定性。我們提出了一種后向選擇算法 SNMA 來篩選對預(yù)測最佳的哨兵集合。該算法開始于全部的 N 個興趣節(jié)點，每次迭代后舍棄一個節(jié)點，直到僅剩 k 個節(jié)點作為哨兵節(jié)點（k 的數(shù)量由預(yù)算決定）。每次迭代被舍棄的節(jié)點是對應(yīng) γ 值最小的節(jié)點。
一旦通過 SNMA 算法獲得了哨兵矩陣的后驗結(jié)構(gòu)，我們可利用監(jiān)控數(shù)據(jù)（即僅在 k 個哨兵節(jié)點上收集的數(shù)據(jù)）來預(yù)測整個系統(tǒng) N 個節(jié)點的傳播動態(tài)學(xué)。使用星號下標(biāo)表示一個新的監(jiān)控樣本，系統(tǒng)未來的狀態(tài)可由下面預(yù)測分布給出。
我們在人工合成數(shù)據(jù)集和真實數(shù)據(jù)集上分別驗證了該方法。采用兩種對比算法，基于互信息的高斯過程（GPs-MI）和 group lasso。GPs-MI 是一種流行的傳感器部署方法[6]，其效果好于實驗設(shè)計方法，如 A-, D-, 和 E-優(yōu)化設(shè)計。Group lasso 是一個典型的組稀疏學(xué)習(xí)方法，與我們所設(shè)計的 Bayesian group sparse 方法類似。該算法本身不具備主動監(jiān)控能力，但可嵌入我們提出的主動監(jiān)控框架中。
我們使用失敗率（failure rate）和均方根誤差 RMSE 兩個指標(biāo)來衡量算法效果。在人工數(shù)據(jù)實驗中，失敗率刻畫是否找到了正確的哨兵節(jié)點。RMSE 衡量哨兵預(yù)測結(jié)果與真實傳播動態(tài)學(xué)間的誤差。我們采用了5折交叉驗證方法。從圖3可以看出，在人工合成數(shù)據(jù)中，無論是線性連續(xù)系統(tǒng)還是邏輯離散系統(tǒng)，我們提出的 SNMA 算法有最低的失敗率和 RMSE。
我們首先使用 2009 年香港 H1N1 流感數(shù)據(jù)做實驗驗證。這次大流感在香港共造成 36,000 人感染，290 人病情嚴(yán)重，80 人死亡。我們研究該次流感自 2009 年 6 月 1 日后 105 天時間的感染病例。香港包含 18 個行政區(qū)域，因此將香港建模為包含 18 個節(jié)點的動態(tài)系統(tǒng)。因為 2009 年 H1N1 流感的感染期為三天，我們依據(jù)三天聚合數(shù)據(jù)后可得到 N=18，T=35 的流感動態(tài)學(xué)。
上圖是不同算法的哨兵預(yù)測結(jié)果，橫軸是所使用哨兵節(jié)點的數(shù)量，縱軸為對傳播的預(yù)測誤差。我們的方法 SNMA 在絕大多數(shù)情況下都有最好的預(yù)測結(jié)果。下圖更直觀地展示了不同算法的預(yù)測曲線，我們選擇哨兵數(shù)量為 8 的情況作為個案研究來比較不同算法表現(xiàn)。黑色星表示 2009 年香港 H1N1 流感的真實傳播趨勢。對三種方法，我們都使用 8 月 15 日前數(shù)據(jù)訓(xùn)練模型，預(yù)測之后的傳播動態(tài)學(xué)。
SNMA 算法所選擇對預(yù)測 2009 年 H1N1 最重要的 8 個哨兵節(jié)點對應(yīng)的空間分布如下圖所示。其中紅??泡標(biāo)識哨兵節(jié)點，氣泡下的紅圈指示該節(jié)點的監(jiān)控重要程度，?色點為不需要監(jiān)控的區(qū)域。和我們直覺相符大多哨兵節(jié)點集中于人口密集的港島和九龍地區(qū)。同樣有趣的是西貢、離島等偏遠(yuǎn)、人口稀少的區(qū)域也有較高的監(jiān)控重要性，可能是由于這里 H1N1 流感的傳播模式與港島和九龍不同。
類似地，我們還在 2005-2009 年騰沖市瘧疾爆發(fā)數(shù)據(jù)和 2015 年某中文在線社區(qū)中信息擴(kuò)散的真實數(shù)據(jù)上驗證了該方法。實驗顯示我們提出方法 SNMA 優(yōu)于 GPs-MI 和 group lasso。SNMA 算法的優(yōu)勢主要在于：
1.該算法是基于模型的，這使得先驗知識易于集成并且訓(xùn)練更為高效；
2.由于采用 Bayesian 框架建模了數(shù)據(jù)和參數(shù)中的不確定性，該算法可有效處理高噪音和訓(xùn)練數(shù)據(jù)不充分的問題。
[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.
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
