时序论文分享
0%

syd 【NIPS2019】TWNet:a Dynamic Time Warping Network

Posted on Edited on In

【NIPS2019】

Abstract

DTW常用于相似性度量，由于DTW对时间轴的规整不变性，可以提供信号间的差异测量。本文提出了ANN的新组件，利用DTW进行特征提取（以往常用DTW作为损失函数）。从理论上分析了DTW损失，用随机反向传播机制来提高DTW学习的准确率和效率。所提出的框架可用作数据分析工具，进行数据分解。

1. Introduction

相似性度量很重要，闵可夫斯基距离比较常用，$dist(x,y)=(\sum_{k=1}^{d}|x_k-y_k|^p)^{1/p}$（p=1，曼哈顿距离；p=2，欧氏距离）；马氏距离是扭曲的欧氏距离，$dist(x,y)=((x-y)^T\sum^{-1}(x-y))^{1/2}$。闵可夫斯基距离和马氏距离不能反应序列数据之间的真正相似性，DTW具有对时间规整的不变性。DTW还可作为特征提取工具，可以通过DTW计算定义预定义模式，后续可以用这些模式对时间数据进行分类。

DTW通过cost矩阵C、动态规划得到最佳归整路径：

DTW虽然可以进行相似性评估、特征提取，但是对深度学习领域没有很大贡献。好的特征提取器是ANN的关。DTW有非线性变换特性（规整），提供了针对多普勒效应的目标总结，是潜在的ANN特征提取器。本文提出了DTWNet，有可学习DTW核的神经网络。

主要贡献：

  1. 在神经网络中应用可学习的DTW核来表现多普勒不变性；
  2. 采用基于规整路径的随机反向传播来计算动态规划的梯度，进而学习DTW核；给出了反向传播的收敛性分析；
  3. 首次对DTW损失函数进行理论分析；
  4. 提出了一种可微流DTW学习，来克服由标准DTW的全局对齐导致的局部特征缺失问题；
  5. 实证研究表明，该方法是有效的，并成功地利用DTW核捕获特征，还演示了一个数据分解应用。

2.1 DTW简介

DTW由于多普勒效应不变性，适于处理声学数据；处理ECG、EEG等生物信号来发现潜在疾病。DTW与预定义模式结合，是时序分类任务中一个强大的特征提取器。

DP时间复杂度高，而且DP是顺序过程，所以DTW计算不能并行，已有一些加速计算的技巧。

2-D DTW：DTW扩展到二维可用于图像匹配

2.2 SPRING算法：DTW的流版本

为了处理DTW度量下的流数据，[18]提出了一种DTW的变体——SPRING。原始DTW找到从两个序列起始到结束的最佳对齐；流版本试图从一个给定的序列中识别所有接近于某个给定模式的子序列。SPRING算法复杂度$O(nl)$，与标准DTW一致。

SPRING核原始DTW计算有两个不同：首先，它在模式前添加一个通配符（模式的起点能匹配输入序列的任何位置）；利用辅助矩阵记录动态规划矩阵中每一个入口的源，这个源矩阵记录每一条候选路径，可以从尾端回溯。

2.3 DTW损失函数

DTW是顺序过程，计算DP矩阵过程中每一步都要最小化，最小化操作是不连续的，梯度和次梯度都不好定义。可以用soft-min代替min操作，[19]给出了soft-min的梯度，用小波学习来提高测试数据有限的时序分类效果。还有研究利用DTW中最小算子的连续松弛来解决视频对齐和分割问题。采用soft-min方法，[4]说明DTW作为损失函数比欧氏距离更好。

3. Proposed DTW Layer and its Backpropogation

DTW层包括多个提取特征的DTW核，每个核产生一个通道，产生一个DTW距离值。如果有滑窗，每个核会产生一个距离序列（像卷积核一样），DTW层可以接线形层，得到分类/回归结果。算法1给出分类任务上的DTWNet示例。

梯度计算和反向传播

DP过程后得到规整路径，序列长n，核长l，路径最长不超过$(n+l)$，DTW距离的平方为：

路径已经确定，只需沿着路径微分，DTW距离对x求导：

min操作没有梯度，直接进行自动微分会导致很大的方差，可以用softmin来解决这个问题，soft-min复杂度$O(nl)$。只依赖于路径上的元素，无需对整个cost矩阵的所有entry进行求导，只对确定路径求导$O(n+l)$。每一次迭代DP扭曲路径不同，也会有方差，所以BP被看作一个随机过程。

时间复杂度：DP时间复杂度$O(nl)$，梯度计算时间复杂度$O(n+l)$

4. DTW Loss and Convergence

给定输入序列，目标是得到和y最佳对齐（通过最小化dtw距离）的核。核x随机初始化，通过梯度下降来学习，$d=H_yx$是动态规划得到的DTW距离。

定义1：所有可能的归整路径

$H_yx$和函数空间中的某个函数$f_y^{(u)}(x)$相等，所以用函数空间中的函数集合来估计$H_yx$（每一个x对应一个样本函数）。用$f_y^{(u)}(x)$的梯度进行梯度下降，问题是它的梯度是否等于$H_yx$的梯度。

$H_yx$在x的空间上不是处处光滑的，存在一些x：

动态规划矩阵在每一步都有3个可选方向，在边界处只有1个可选方向，所以有：

引理1：归整路径数$|F_y|<3^{n+l}$，其中n+l是最长归整路径

x空间被分成区域，在某个区域，可以用$f_y^{(u)}(x)$来估计$H_yx$。用2范数的平方作为DTW loss，则$H_yx$是x的分段二次函数，如果用绝对值作为DTW loss，则$H_yx$是x的分段线性函数。

图2a，2b给出了示意。生成点来计算DTW loss，x长度为6，y长度为10，只变化x中间的两个元素，便于画出三维图像。图2a说明2范数作为DTW loss时$H_yx$是x的分段二次函数，2b是线性分段函数情况。

逃离局部最优

有一些工作给出了非凸神经网络损失函数全局收敛性的证明，本文通过利用损失函数的二次分段（线性分段），区域数上界是$O（3^{n+l}）$。先分析用标准梯度下降分析逃离u来进入它的邻域v，假设$y_{p:p+q}$和$x_k$对齐，可以得到u的局部二次函数，以及对$x_k$的偏导：

令偏导等于0，得到稳定点：

相邻区域的函数$fy^{v}$除了$y{p+q+1}$的对齐外，都和$f_y^{u}$相同：

同理，该邻域左侧相邻区域的的稳定点如下：

考虑从u跳到v（u是碗状的，想跳出），区域v有三种情况：

  1. v的稳定点不在区域v内，在它的左侧。此时全局最优解一定不在v内，u内有一部分比它更小，如果跳到v，梯度会再次让它跳回u；
  2. u和v都是碗状的，需要从u到v，起点在最低点的左侧（如红色位置所示），否则会跳到w而不是v，为了保证一步跳到v，至多需要$(xk^{(v)*}-x{hat})$；
  3. v不是碗状的，$xk^{(v)}$在v的右端，走$(x_k^{(v)}-x{hat})$来跳到v，如果v的右邻域是碗状的，则v的右邻域更小，即使v的右邻域不是碗状的，组合区域[v, v+]也可以看作是准碗或扩展的v，所以跳到此处也是合理的。

考虑左邻域w，w的稳定点在w内或w左侧时，稳定点肯定在起点左侧；w的稳定点在w右侧时，把[w,u]合并为u’，u’的左邻域为w‘，上述分析对这三个新的区域仍然成立，所以有以下定理：

定理1.假设起点在u区域（由公式5定义）内，x和y的长度分别为n和l，为了跳出u区域到达紧邻的右侧区域，步长期望满足$E(\eta)>l/(2n)$

有若干个y，距离函数求和，梯度求和，通过小批量随机梯度下降来更新x。随机梯度是无偏估计，方差代表跳出局部最优解的能力。

5. Streaming DTW Learning

一个ECG序列有多个心跳脉冲，希望DTW核学到心跳脉冲模式，而端到端的DTW会使DTW核与整个序列对齐而不是一个脉冲。如果核很短，没学到有用的东西。为了解决这个问题，用SPRING算法来输出对齐子序列的模式（DTW核）：

其中i和y的长度待优化。

流版本试图从一个给定的序列中识别所有接近于某个给定模式的子序列。SPRING给出最佳匹配的子序列以及一系列有最小DTW距离的规整路径，提出两个机制：机制一，预设常数k，让SPRING选出k个最优的归整路径（k个不同的非重叠的、与模式x的DTW距离最小的子序列）；机制二，不是指定路径数，设置参数$\epsilon$，给出距离小于$(1+\epsilon)d^*$的路径（$d^*$是最佳归整路径的DTW距离）。随机/平均作为DTW计算结果。本文中，$\epsilon$设为0.1，随机采样。

流DTW的正则化矩阵

SPRING希望核x去学习输入序列中的重复模式，对模式的长度没有限制。输入数据中总会出现没有包含太多有效信息的公共部分，不加正则化的核很容易捕捉无用模式并陷入局部最优值。加入正则化来解决这个问题：

正则化会得到“完整”的模式，模式的起始相隔比较近。如图3a所示，有上半个/下半个半圆待学习，不进行正则化的话，核只能学到部分模式；加入弱正则化，学到更完整的模式；合适的$\alpha$能捕捉到完整的形状。

6. Experiments and Applications

将本方法与现存的方法对比，将端到端的DTW核称为Full DTW，将流版本称为 SPRING DTW。

6.1 与卷积核的对比

类别1有半个方形信号模式，类别2有下方的三角信号模式，模式的位置和长度随机，模式不重叠，图4a给出一些样本。

输入序列有100个点，模式长度从10-30不等，训练集100条（1：1），测试集100条（1：1），我们比较了Full DTW、SPRING DTW和卷积核，核的长度为10，再加三层线性层，

图4b给出了收敛后的习得的DTW核，Full DTW试图捕捉整个序列，整个序列有两个模式，Full DTW核也有两个峰；SPRING DTW只匹配部分模式，呈扫描状；图4c和4d给出了acc和loss曲线，两个DTW的曲线几乎一致，只画出了Full DTW的图。令人意外，卷积核未能到100%，MLP表现最差。可以将这个方法扩展到多元时间序列（无需作大的修改）

6.2 梯度计算评估

进行质心计算，评估提出的BP机制的效率和准确性，使用了UCR数据集，将我们的方法和SoftDTW、DBA、SSG进行对比，5次实验取平均。

质心实验旨在找到每一类输入序列的质心，计算DTW loss，loss越小，表现越好。

表1给出了实验结果，Win意思是在85个数据集上达到最小loss的次数，还给出了平均排名、平均loss，我们的方法性能比较好。

6.3 DTW分解的应用

将DTWNet作为时间序列数据分解工具，设计五个DTW层，每层有一个DTW核。关键是将第i层的残差向前传到下一层。计算DTW距离会得到规整路径，从$yj$中减去对应的$x{i,j}$

图5阐释了分解的影响，核0-核4对应第一层到最后一层，训练目标是最小化网络输出的残差，训练一定轮数后，不同层的核形成不同的形状，核0是低频的、数据整体形状，核4形状是高频的、曲折形状。层数越深，越能学到高频的部分，可被用作分解工具，可解释性强。

7. Conclusions and Future Work

将DTW核应用为特征提取器，提出了DTWNet框架。为了实现反向传播，通过动态规划评估了DTW距离，沿着确定规整路径的计算梯度，给出了DTW作为损失函数的理论研究，将DTW损失定义为分段二次/线性函数，描述了不同情况下的步长（为了跳出局部最优）。实验显示，在某些任务中DTW核比标准的卷积核表现好，评估了梯度计算核反向传播的有效性，给出了数据分解的应用。

本文由腾讯AI Lab主导，与康涅狄格大学合作完成。深度神经网络在处理时间序列数据时，传统的闵可夫斯基距离不适合作为反应序列相似度的损失函数，而动态时间规整算法（DTW）可以更好地计算序列距离，因此可以用作深度网络中的损失函数和特征提取算子。
本文提出了一种新的估计方法，使得DTW在作为算子时可以估计输入的梯度，从而实现神经网络中的反向传播。该方法首次分析了DTW作为损失函数的函数形态和应用梯度下降法的收敛性，并且首次提出了基于部分序列匹配的DTW梯度更新算法。实验结果表明，该方法作为一种新的特征抽取手段，可以更好地提取时间序列数据中的特征。此外，本文提出的梯度估算方法在实验中展现了良好的收敛性。本文也创造性地提出了该方法在数据分解上的拓展性应用。