论文精读 | 2024[KDD]基于多目标强化学习的时空早期预测

题目：Spatio-temporal Early Prediction based on Multi-objective Reinforcement Learning

作者：Wei Shao(邵巍), Yufan Kang(康雨凡), Ziyan Peng(彭紫妍), Xiao Xiao(肖潇), Lei Wang(汪磊), Yuhui Yang(杨玉慧), Flora D Salim

机构：CSIRO， 皇家墨尔本理工大学（RMIT），西安电子科技大学，浙江大学，新南威尔士大学（UNSW）

TL; DR: 这篇论文介绍了一种基于多目标强化学习的时空早期预测模型STEMO，自适应地确定最佳预测时间，达到了时效性和准确性全新的平衡。该模型利用多图卷积神经网络（MGCN）和门控循环单元（GRU）捕捉和分析时空相关性，结合编码器输出的隐藏状态和节点嵌入利用基于偏置随机游走的节点嵌入技术来自适应地确定预测的最佳时间，同时捕捉了不同情境下的隐藏偏好。

arXiv网址：https://arxiv.org/abs/2406.04035

点击文末阅读原文跳转本文arXiv链接。

Abstract

在预测任务中，准确性和时效性往往难以同时优化。过早得到的预测结果可能会导致较高的误报率，而能够获取更多信息的延迟预测可能会使结果失去时效性。在野外火灾、犯罪和交通拥堵等现实场景中，及时预测对于保障人类生命财产安全至关重要。因此，平衡准确性和时效性是研究的一大热点。本文提出了一种基于多目标强化学习的时空早期预测模型，该模型可以根据偏好实施最优策略，或基于少量样本推断偏好。该模型解决了两个主要挑战：1）提高早期预测的准确性；2）提供了一种能够确定每个区域最优预测时间的优化策略。该方法在三个大规模真实数据集上表现优越，在早期时空预测任务中超越了现有方法。

Introduction

时空预测问题是地理信息系统、统计学和数据科学领域的创新交叉问题，主要应用于预测结果受地理位置和时间变化影响的任务中。该预测方法在气象学、流行病学、交通和城市规划等领域有着广泛的应用。

时空早期预测主要通过尽早检测跟随时间和空间变化的模式来预测未来事件，广泛应用于流行病学、环境研究和公共安全等现实领域。在这些领域中，检测早期的时空模式给管理者更好的决策建议，预防更坏的结果发生。例如，在预测疾病传播时，结果的时效性远比准确性更重要。过分追求准确而过时的预测结果可能会导致成千上万人不必要的死亡，及时但没那么精确的结果往往可以减少扩散的影响，维护人民生命财产安全。

现有的时空事件预测方法大致分为三种：传统方法、固定方法和自适应方法。例如，传统的预测方法考虑了全部的记录数据，在大数据集上十分耗时，并且其需要完整的先验数据收集，这常导致预测延迟，不适用于有时效要求的领域。相比之下，固定早期预测方法在设定的观察期内进行操作，便于在特定时间窗口内及时预测。虽然这种策略增强了时效性，但其固定的时间安排在观察窗口选择不当时可能会导致结果不准确。此外，在调整时间数据的变化和选择观察窗口时不灵活，会影响预测精度。第三种方法为自适应早期预测，基于数据特征动态地调整预测时间。该方法旨在平衡预测准确性和时效性，其动态适应的能力在处理时间变化方面提供了显著优势。

自适应早期预测方法在一些领域中取得了良好的结果，但在时空预测中仍存在许多挑战。主要包括：1）高度复杂环境中的实时双目标平衡：时空数据比时间序列数据更复杂，变化更快，需要动态的解决方案。传统的多目标优化方法是静态且计算量大的，无法有效适应不同场景。同时，早期预测需要即时结果，即使一分种的延迟也会导致不利后果。2）时空全局依赖性：单靠距离相关性进行时空预测可能难以快速捕捉关键数据特征。尽管距离相关性有效地反映了节点间的空间连接关系，但忽略了准确预测所必须的时间方面的依赖。3）隐藏偏好的发现：时效性和准确性之间的平衡因任务而异，每个任务可能都有不同的偏好。识别这些深层次的偏好是一项复杂的挑战，需要深入理解所面临的目标并为每种场景制定理想的平衡策略。

该研究引入基于多目标强化学习的时空早期预测模型（STEMO），主要贡献包括：

• 提出了一种多目标强化学习框架来优化时空预测的时效性和准确性。该方法通过实时反馈的交互式学习来适应多变的场景。
• 引入了多步相似性矩阵，使每个节点能够捕捉其他上游节点的趋势，从而更早地估计这些节点的变化。
• 开发了一种基于偏置随机游走的节点嵌入技术，提高了访问具有更高相似性的节点的概率，从而达到最佳时间。为解决非均匀对象尺度或单位问题，我们提出了一种发现隐藏偏好的方法并采用熵权法。

背景与动机

时空预测在气象学、流行病学、交通运输和城市规划等领域具有重要应用，尤其在及时预测野火、犯罪和交通堵塞等方面对保障人类生命和财产安全至关重要。预测任务中的准确性和时效性往往是相互冲突，过早预测可能导致更高的误报率，而延迟预测虽然可以获取更多信息，达到更高的准确率，但可能失去时效性。时空预测不仅需要动态的解决方案，还需要同时考虑时间与空间维度的相关性。同时，不同任务对时效和准确性的平衡存在多样化的偏好。因此，高效且灵活地平衡预测结果的时效性与准确性是该研究的根本目标。

目前面临的问题

1. 时空数据需要动态的解决方案：时空数据比时间序列数据更复杂，变化更快，因此需要动态解决方案。传统的多目标优化方法是静态的且计算复杂，无法高效适应不同环境。早期预测需要即时结果，即使一分钟的延迟也可能导致不利的结果。
2. 时空综合依赖性：仅依靠距离相关性进行时空预测可能无法快速捕捉到关键数据特征。虽然距离相关性有效地反映了节点之间的空间连接，但忽略了数据的时间维度。
3. 隐藏偏好的挖掘：不同任务对时效和准确性的平衡存在多样化的偏好。识别这些微妙的偏好是一个复杂的挑战，需要对目标有深入理解，并为每种情景制定理想的及时性和准确性平衡。

亮点与贡献

1. 多目标强化学习：构建了多目标强化学习框架STEMO模型来优化时空预测的及时性和准确性，通过从实时反馈中进行互动学习，能够根据偏好实施最优策略，能够基于少量样本推断偏好，提高了对变化模式的适应能力。强化学习的核心在于模型能够在面对不同预测任务时，自主学习并优化多个目标（例如准确性和时效性），以实现最佳的预测效果。
2. 动态时间相似性矩阵：引入多步相似性矩阵，使每个节点能够捕捉其他上游节点的趋势，从而可以更早地估计节点变化。
3. 节点嵌入与偏置随机游走：开发了一种基于偏置随机游走的节点嵌入技术，增加了访问相似性更高节点的概率，并达到最佳时间
4. 隐藏偏好的发现：采用熵权法设计了一种发现隐藏偏好的方法，解决非均匀对象尺度或单位的问题。

核心：多目标强化学习

这篇论文的核心是多目标强化学习，它使模型能够在面对不同预测任务时，自适应地学习并优化准确性和时效性，平衡两者以实现最佳的预测效果。该模型可以根据不同情境和任务需求，发现隐藏偏好，动态调整预测的策略，以满足不同的要求。这不仅提高了预测的灵活性和适应性，还显著增强了模型在实际场景中的预测准确率。

模型架构

图为STEMO模型架构。该模型主要由三部分构成：

时空预测器（Spatio-Temporal Predictor）：负责处理时空数据，提取时空特征，并生成预测值。在时间，编码器（Encoder）利用GRU（门控循环单元）处理从时间到的记录值以提取时空特征，并生成隐藏状态。使用隐藏状态，解码器（Decoder）生成一系列预测值，特别关注时间的预测值。

状态生成器（State Generator）：在偏置随机游走中，引入了一些偏置项来改变选择相邻节点的概率，从而有目的地控制游走的方向和重点。状态生成器模块通过设计嵌入函数、结合节点嵌入和隐藏状态、使用偏置随机游走采样和word2vec方法，生成用于决策的节点在不同时间的状态信息。这些状态表示综合了节点当前的信息和邻居信息，用于优化预测时间，提高预测的准确性和及时性。

最优策略（Optimal Policies）：利用生成的状态信息，确定每个节点的最优预测时间。通过动作集决定是继续观察（Wait）还是暂停（Halt）。继续观察表示需要进一步观察记录值。暂停表示时间是节点的最优时间，相应的预测值被记录在预测值中。该模块使用神经网络表示Q值，结合状态、动作和用户偏好，采用贪婪策略选择动作，并设计奖励函数以优化预测准确性和时间。通过最小化损失函数训练神经网络，以找到最优策略集，适应所有偏好空间。

此外，模型预测过程中还会通过估计和优化截断多变量高斯分布的参数分析数据中的隐藏模式和偏好，有效地发现不同目标的优先级，优化预测过程，使得预测结果更准确和及时。

实验结果

g1侧重于效率，g2侧重于准确性

总结

在多个大规模真实数据集上的实验结果显示，STEMO模型在多种预测任务中均表现优越，验证了其在实际应用中的有效性和可行性。STEMO模型在提高时空预测任务的准确性和时效性方面取得了显著进展，提出的多目标强化学习方法和创新的技术手段为时空预测领域带来了新的视角和解决方案。

引用BibTex

@inproceedings{STEMO2024,
  author={Wei Shao and Yufan Kang and Ziyan Peng and Xiao Xiao and Lei Wang and Yuhui Yang and Flora D. Salim},
  title={Spatio-temporal Early Prediction based on Multi-objective Reinforcement Learning},
  booktitle={Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2024)},
  year={2024},
  url={https://arxiv.org/html/2406.04035v1}
}

欢迎各位作者投稿近期有关时空数据和时间序列录用的IJCAI、SIGIR、ICML以及KDD等顶级会议和期刊的优秀文章解读，我们将竭诚为您宣传,共同学习进步。如有意愿,请通过后台私信与我们联系。