WSDM2021论文阅读：时序演化状态图
本文简要介绍我们刚刚被WSDM2021会议录用并即将发表的论文"Time-Series Event Prediction with Evolutionary State Graph"(论文地址)，在文中我们提出了一种将时序转化为图进行表示建模的方法。同时我们把所实现的方法落地为阿里云·SLS的智能巡检服务，可以应用于大规模的时间序列异常检测与分析，辅助运维、运营、研发等诸多场景。
整体导读
- 文章通过真实场景下数据分析，发现了时间序列状态之间的动态关系对于时序事件预测很重要；
- 文章提出了演化状态图来捕获时序状态之间的关系，并提出了EvoNet模型对演化状态图进行建模分析，在提高事件预测准确度的同时，也具备良好的可解释性；
- 文章发表在数据挖掘领域顶级会议 WSDM 2021 上。
时间序列的状态
如何对时间序列进行有效的分析在学术界有广泛的研究，例如异常检测[2]，语音识别[3]等。工业界也有非常多的应用场景，通常需要模型在进行判断的同时（例如判断异常），给出所做判断的合理解释，这对帮助人们进行更好的决策有很大的作用。
可解释的时间序列分析通常需要我们提取时间序列中代表性的特征。以前的工作很大一部分从经典的特征工程和表示学习入手，这些方法具有很好的可解释性，但主要依靠人的经验，在复杂的场景下很难做到通用化。近年来随着深度学习的发展，许多工作开始尝试一些复杂的模型方法来自动的挖掘特征。然而，尽管这些方法取得了良好的效果，但由于模型的复杂度高以及难以对结果很好的解释，许多方法不能很好地满足实际工业落地的需求。
近年来，可解释的时序建模多着眼于离散时序，在时间轴上将时序分段，然后从分段中抓出可以用于判断异常的表示，常见的方法有：
- 字典方法[3]，找时序分段的特征值
- 形状方法[4]，找时序分段的特殊波形
- 聚类方法[5]，找时序分段的分类特征
这些方法可以有效的捕捉时序中的状态，即有表征意义的特征片段。然而，这些方式都是以静态的方式捕捉出特征，而忽略了时间序列是动态演变的。基于以上背景为出发，为了描述时间序列的动态信息，同时让模型学习更好的可解释性表示，该论文尝试捕捉时序状态随时间的动态变化信息，将相邻两时序段之间的状态变化用图（Graph）这种数据结构进行表示。整体时序的演变转化为动态图的变化，形成一种可推理可解释的方法用于时序建模与分析。
时序状态的识别
这里以时序聚类为例子，描述时序状态的识别以及在时序上的映射。这里时序状态定义为
，即将离散出的时序片段聚成
个特征类，抽取类的特征值。给定时序片段
和时序状态
，我们可以量化他们之间的距离来表示时序片段映射到时序状态的权重，具体为：
,
其中
描述时序片段与时序状态之间的距离。简单的，可以采用欧式距离。该距离越小，则识别的权重就越大。通过上面的方法，每个时序片段可以分别以不同的权重映射到个状态上。
时序演化状态图
当我们将时序段识别成带权重的状态集后，一种简单的方法是将时间序列视为最可能状态的新的序列，然后对新构建序列的马尔科夫性质进行建模分析[6]。 但是，一个时序段不只会属于一个状态，而应该将其识别为具有不同权重的多个状态。因此，这项工作提出了一种新颖的动态图结构来描述状态之间的关系，并探索状态的动态变化如何揭示时间序列的演化。
论文将演化状态图定义为一系列加权有向图
。具体地，每个图被表示为
以表示从时序段
的状态到
的状态的转变。图中的每个节点都表示一个状态
；每个边
表示从𝑣到
的转移关系（或简称关系），对应的转移权重为
。这里观察到的每个时序段的状态权重是独立的，那么转移权重可以由下式计算：
这是被识别为状态𝑣和
被识别为状态的联合权重。相比于构建新序列的方法，演化状态图通过对每个时序段中多个状态及其跨段的转移关系进行建模，沿时间轴保留了来自原始数据的更多信息。
上图展示了一个预测网络流量异常的演化状态图的示例，实线表示写入流量，虚线表示读取流量，红色表示当天发生异常事件。(a) 可视化了四种识别出的状态，而 (b) 呈现在四个不同的时间间隔（在(a)中标记的I，II，III，IV）的演化状态图。 从图中所示的案例可以看出，当发生异常事件时，状态转换（＃2→＃16）和（＃2→＃8）在时间I上更加频繁。 同样，状态转换（＃2→＃8）和（＃8→＃23）在时间II处很明显。 这些转变表明，写入和读取流量的不平衡（状态8和状态16）或流量下降（状态23）将导致网络异常。 在时间III，在此期间未发生异常，可以看到状态主要停留在＃2中。 然后在下一个时刻IV出现异常。 因此可以看到状态转换＃2→＃16的明显增加。
时序演化状态图网络
当时序转化为动态图·演化状态图之后，如何对这种动态图结构进行建模分析变为了主要的问题，受图神经网络（GNN）的启发[7]，该文的研究者设计了两种机制来对演化状态图进行建模与分析，即局部信息聚合和时间图传播。
上图说明了所提出的演化状态图网络（EvoNet）的总体结构。对于给定的时间序列以及事件
，该文首先识别每个分段的状态并构造演化状态图。接下来，该文定义表示向量
对于图中每个节点的信息进行编码，并定义表示向量
用于编码整个图的信息。
基于此，如图a，EvoNet通过消息传递网络（message passing）[8]来聚合局部的结构信息：
并使用循环神经网络[9] 进一步传播时间上的节点以及图的信息：
然后，EvoNet将学习到的特征表示
应用于下游的时序任务。具体的推导逻辑大家可以从原文[1]中获取，这里不做过多阐述。
特别的，在进行时间上信息聚合的操作中，该研究者们提出在点到点建模的同时，还应关注点到图的影响，即时序的演化不仅仅与状态与状态之间的转变有关，状态与整个时序片段之间的关系也有影响。因此，如图b，作者们采用层次循环神经网络机制，捕捉节点级别信息与图级别信息随时间的影响，通过有时间注意力机制（temporal attention）量化不同时间位置上影响的权重：
实验结果
文章对来自Kaggle的两个公共数据集，和来自国家电网、中国电信、阿里云的三个真实世界数据集进行时间序列事件预测任务。实验结果如下表所示：
工业落地实践
该文提出的算法已落地为阿里云·SLS的时间序列的异常检测服务。该方法可以提供大规模秒级别的实时异常检测，并给出异常判断初步解释，辅助于运维、运营、研发等诸多场景。详情请见[《阿里云SLS·机器学习服务》]。下面展现该文所列举的一个例子：
如图所示，图a 展现了云服务主机（ECS）监控下的秒级CPU利用率。红色表示1分钟内有异常。这个例子中设定了10个状态以构建演化状态图，并可视化了每个时间位置的时间注意力分数。
1.时间注意机制的有效性：如图b所示，热力图可视化了不同时间位置的注意力得分。我们可以看到注意分数成功地突出了图a中异常的位置。
2.演化状态图的可解释性：如图c-e所示，我们可以看到，时间位置I的图中有一个主要的转移＃2→＃4→＃0，而在时间位置II的图中则是＃3→＃5。请注意，II之后立即发生异常。当我们在时间轴上汇总所有演化状态图时（图d）可以发现，过渡＃2→＃4→＃0是图中的主要路径，而＃3→＃5是次要路径。这些观察结果表明，间隔II中发生的转移＃3→＃5是异常的。
如图e所可视化的不同状态的平均曲线，可以看到，转移＃2→＃4→＃0表示服务进程，即CPU利用率从0.25上升到0.75，并在保持一段时间后下降。相反，转移＃3→＃5表示CPU利用率上升到0.5，然后立即下降。这些观察结果表明，这种异常可能是由CPU的故障引起的。
Reference
[1] Wenjie, H; Yang, Y; Ziqiang, C; Carl, Y and Xiang, R, 2021, Time-Series Event Prediction with Evolutionary State Graph, In WSDM, 2021
[2] Chandola V, Banerjee A, Kumar V, et al. Anomaly detection: A survey[J]. ACM Computing Surveys, 2009, 41(3).
[3] Shimodaira, H.; Noma, K.-i.; Nakai, M.; and Sagayama, S. 2002. Dynamic time-alignment kernel in support vector machine. In _NIPS’02_, 921–928.
[4] Malhotra, P.; Ramakrishnan, A.; Anand, G.; Vig, L.; Agar- wal, P.; and Shroff, G. 2016. Lstm-based encoder-decoder for multisensor anomaly detection. _arXiv preprint arXiv:1607.00148_.
[5] Johnson, M.; Duvenaud, D. K.; Wiltschko, A.; Adams, R. P.; and Datta, S. R. 2016. Composing graphical models with neural networks for structured representations and fast inference. In _NIPS’16_, 2946–2954.
[6] Pierre Ailliot and Valerie Monbet. 2012. Markov-switching auto regressive models for wind time series. Environmental Modelling and Software 30 (2012), 92–101.
[7] Peter Battaglia, Jessica BHamrick, Victor Bapst, Alvaro Sanchezgonzalez, Vinicius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018. Relational inductive biases, deep learning, and graph networks. arXiv: Learning (2018).
[8] JustinGilmer,SamuelSSchoenholz,PatrickFRiley,OriolVinyals,andGeorgeEDahl. 2017. Neural Message Passing for Quantum Chemistry. ICML (2017)
[9] Yoshua Bengio, Patrice Y Simard, and Paolo Frasconi. 1994. Learning long-term dependencies with gradient descent is difficult. TNNLS 5, 2 (1994)
联系我们
纠错或者帮助文档以及最佳实践贡献，请联系：笃林
问题咨询或方法交流请加钉钉群：
