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