【论文阅读】Modeling Extreme Events in Time Series Prediction

Metadata

authors:: Daizong Ding, Mi Zhang, Xudong Pan, Min Yang, Xiangnan He
container:: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
year:: 2019
DOI:: 10.1145/3292500.3330896
rating:: ⭐⭐⭐️
share:: true
comment:: 以GRU为基础，主要针对损失函数进行了修改，强调极端值的模型预测中的作用。

---

前言

时间序列预测是数据挖掘中一个深入研究的课题。尽管取得了相当大的进步，但最近基于深度学习的方法忽略了极端事件的存在，这导致将它们应用于实时序列时性能较弱。

在本文中，探讨了提高深度学习建模极端事件以进行时间序列预测的能力。

1. Extreme Value Loss (EVL)

   论文发现深度学习方法的弱点源于传统形式的二次损失函数。为了解决这个问题，论文从极值理论中汲取灵感，开发了一种新的损失函数，称为极值损失（EVL），用于检测未来发生的极端事件。

2. Memory Network

   使用记忆网络来记忆历史记录中的极端事件。通过将 EVL 与经过调整的记忆网络模块相结合，实现了一个端到端的框架，用于极端事件的时间序列预测。

Introduction

在时间序列预测中，时间序列中的不平衡数据（或极端事件）也对深度学习模型有不好的影响。直观地看，时间序列中的极端事件通常具有极小或极大的值，即不规则和罕见的事件。

论文训练一个标准 GRU 来预测一维时间序列，其中某些阈值用于将一小部分数据集标记为极端事件

学习模型会遇到两种情况：

1. 在图 a 中，它的大部分预测都受到阈值的限制，因此它无法识别未来的极端事件，称为欠拟合现象。
2. 在图 b 中，尽管模型正确地学习了训练集中的极端事件，但它在测试集上的表现很差，称为过拟合现象。

然而, 如果一个时间序列预测模型能够通过合理的预测来识别未来的极端事件，这将是非常有价值的。

基于上述动机，在本文中专注于提高 DNN 在预测具有异常的时间序列方面的性能。

通过极值理论 (EVT) 的视角，论文观察到主要原因在于先前选择的损失函数，它天生缺乏对极端事件进行精细建模的能力。因此，论文提出了一种称为极值损失 (EVL) 的新型损失函数，以改进对极端事件的预测。

此外，在记忆网络的帮助下，提供了一种神经架构来记忆历史数据的极端事件。与 EVL 一起，构建了端到端框架，以便更好地预测具有极端事件的时间序列数据。

主要贡献

• 提供了关于为什么深度神经网络在预测具有极端事件的时间序列数据时会出现欠拟合或过拟合现象的分析。
• 提出了一种基于极值理论的、称为极值损失（EVL）的新型损失函数，它可以更好地预测极端事件的未来发生。
• 提出了一种全新的基于记忆网络的神经架构来记忆历史上的极端事件，从而更好地预测未来的极端值。

准备工作

时间序列预测

假设有$N$个固定长度$T$的序列。 对于第$i$个序列，时间序列数据可以描述为:

$$(X_{1:T}^{(i)}, Y_{1:T}^{(i)}) = [(x_1^{(i)}, y_1^{(i)}), (x_2^{(i)}, y_2^{(i)}), \cdots, (x_T^{(i)}, y_T^{(i)})]$$

时间序列预测的目标是，给定值 $X_{1:T} = [x_1, \cdots, x_T], Y_{1:T} = [y_1, \cdots, y_T]$, 和未来输入 $X_{T:T+K}$, 预测未来的输出 $Y_{T:T+K}$.

假设模型在$t$时刻的预测为$o_t$, 则常见的优化目标是:

$$\min \sum_{t=1}^T \Vert o_t - y_t \Vert^2$$

极端事件

尽管像 GRU 这样的 DNN 在预测时间序列数据方面取得了显着的进步，但如果使用不平衡的时间序列进行训练，该模型往往会陷入过拟合或欠拟合。

为了理解这一现象，引入一个辅助指标序列$V_{1:T} = [v_1, \cdots, v_T]$

$$v_t = \begin{cases} 1 & y_t > \epsilon_1 \\ 0 & y_t \in [-\epsilon_2, \epsilon_1] \\ -1 & y_t < -\epsilon_2 \end{cases}$$

其中，$\epsilon_1, \epsilon_2$是极端事件的阈值。

对于时刻$t$, 如果$v_t=0$, 则将$y_t$定义为正常事件，如果$v_t>0$, 则将$y_t$定义为右极端事件，如果$v_t<0$, 则将$y_t$定义为左极端事件。

长尾分布(Heavy-tailed Distributions)

现实世界数据的经验分布似乎总是长尾的。

直观地说，如果说随机变量 $Y$ 符合长尾分布，那么它通常具有不可忽略的大值（大于阈值）的概率 。

事实上，包括高斯、泊松在内的大多数广泛应用的分布都不是长尾分布，而是轻尾分布。使用轻尾参数分布进行建模会在数据的尾部带来不可避免的损失。（因为实际数据大体上是长尾分布）

预测有极端事件的时间序列

为了将先验信息强加于 DNN 观察的尾部，关注两个因素：记忆极端事件和建模尾部分布。

记忆网络模块(Memory Network Module)

对于每个时间步 $t$，首先随机采样一系列窗口 $W = {w_1,····,w_M}$，其中 $M$ 是记忆网络的大小。

每个窗口为 $w_j = [x_{t_j}, x_{t_j+1}, \cdots, x_{t_j+\Delta}]$

应用 GRU 模块将每个窗口嵌入到特征空间中。

具体来说，使用 $w_j$ 作为输入，并将 GRU 最后一个 hidden state 作为这个窗口的特征，表示为 $s_j = GRU([x_{t_j}, x_{t_j+1}, \cdots, x_{t_j+\Delta}]) \in \mathbb{R}^H$

同时，应用一个记忆网络模块来记忆每个窗口 $w_j$ 在 $x_{t_j+\Delta+1}$ 中是否存在极端事件: $q_j = v_{t_j+\Delta+1} \in \{-1,0,1\}$

在每个时间步长 $t$ 中，我们提出的架构的内存由以下两部分组成：

1. Embedding Module $S \in \mathbb{R}^{M \times H}$
2. History Module $Q \in \{-1,0,1\}^M$

注意力机制(Attention Mechanism)

在每个时间步 $t$，我们使用 GRU 来产生输出值：

$$\widetilde{o}_t = W_o^T h_t + b_o, \text{where } h_t = GRU([x_1, x_2, \cdots, x_t])$$

正如之前所讨论的, $\widetilde{o}_t$的预测可能缺乏识别未来极端事件的能力。

因此，还要求模型回溯其记忆，以检查目标事件与历史上的极端事件之间是否存在相似性。

利用注意力机制可以实现这一点:

$$\alpha_{tj} = \frac{\exp(c_{tj})}{\sum_{j=1}^M \exp{c_{tj}}}, \quad \text{where } c_{tj} = h_t^T s_j$$

最后，可以通过对 $q_j$ 施加注意力权重来衡量之后是否会发生极端事件的预测。

$$o_t = \widetilde{o}_t + b^T \cdot u_t, \quad \text{where } u_t = \sum_{j=1}^M \alpha_{tj} \cdot q_j$$

其中$u_t\in [-1,1]$是对时刻$t$之后是否会发生极端事件的预测。

极端值损失(Extreme Value Loss)

正如之前讲的那样，用平方损失作为优化目标，会导致 $y_t$ 的非参数近似, 很容易导致过拟合/欠拟合两种现象。

为简单起见，我们首先考虑右极端事件。

为了将尾分布与 $P(Y)$ 结合起来，对于观测值 $y_t$，近似值可以写为

$$1-F(y_t) \approx (1-P(v_t=1)) \log G(\frac{y_t-\epsilon_1}{f(\epsilon_1)})$$

将预测指标$u_t$视为$(y_t-\epsilon_1)/(f(\epsilon_1))$的近似，则:

$$\begin{aligned} EVL(u_t) =&- (1 - P(v_t=1)) [\log G(u_t)]v_t \log(u_t) \\ &- (1 - P(v_t=0)) [\log G(1-u_t)](1-v_t) \log(1-u_t) \\ =&-\beta_0 [1-\frac{u_t}{\gamma}]^{\gamma}v_t \log(u_t) \\ &- \beta_1 [1-\frac{1-u_t}{\gamma}]^{\gamma}(1-v_t) \log(1-u_t) \end{aligned}$$

其中$\beta_0 = P(v_t=0)$为正常事件的比例, $G()$为广义极值分布:

$$G(y) = \begin{cases} \exp(-(1 - \frac{1}{\gamma}y)^{\gamma}) & \gamma \neq 0, 1 - \frac{1}{\gamma}y > 0 \\ \exp(-e^{-y}) & \gamma = 0 \end{cases}$$

$$u_t = \sum_{j=1}^M \alpha_{tj} \cdot q_j$$

$$v_t = \begin{cases} 1 & y_t > \epsilon_1 \\ 0 & y_t \in [-\epsilon_2, \epsilon_1] \\ -1 & y_t < -\epsilon_2 \end{cases}$$

类似地，有二分类损失函数，用于检测未来是否会有左极端事件。结合两个损失函数，可以将 EVL 扩展到 $v_t =\{−1,0,1\}$的情形。

EVL 的关键是利用极值理论，通过在观测值的尾部分布上加上近似$\beta_0[1-u_t/\gamma]^{\gamma}$来找到合适的权值。

直观地说，当模型将该事件识别为正常事件时，$\beta_0$ 项会增加对右极端事件的惩罚。$[1-u_t/\gamma]^{\gamma}$也增加了模型识别可信度较低的极端事件时的惩罚。

Optimization

首先，为了将 EVL 与所提出的记忆网络结合起来，一个直接的思路是将预测的输出与极端事件发生的预测结合起来:

$$L_1 = \sum_{t=1}^T \Vert o_t - y_t \Vert^2 + \lambda_1EVL(u_t, v_t)$$

此外，为了提高 GRU 单元的性能，为每个窗口 $w_j$ 增加惩罚项，其目的是预测每个窗口 $w_j$ 的极端指标 $q_j$:

$$L_2 = \sum_{t=1}^T \sum_{j=1}^M EVL(p_j, q_j)$$

整体算法

实验

datasets:

• Stock Dataset
• Climate Datasets
• Pseudo Periodic Synthetic Dataset

参考资料

• Modeling Extreme Events in Time Series Prediction
• 论文笔记： Modeling Extreme Events in Time Series Prediction