传播动态学的主动监控：一种组稀疏贝叶斯学习方法

雷锋网(公众号：雷锋网) 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.

雷锋网特约稿件，未经授权禁止转载。详情见。