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

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

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

早期预测三种示例

背景与动机

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

目前面临的问题

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

亮点与贡献

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

核心：多目标强化学习

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

模型架构

STEMO

图为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}
}

本文原文来自腾讯云开发者社区，原始发表于2024-06-12。