简介

这是一篇来自2021年AAAI的会议文章，主要讲述的是一种基于Shapelet的MTSC(Multivariate Time Series Classfication)的方法，文章模型基于UEA数据集(一个多元时序数据集，共30个子数据集)进行训练和测试，在效果上打败了前一年同样在AAAI上发表的MTSC模型TapNet。基于这篇文章，我会按以下几个部分:第一部分：前置知识，主要是原始的Shapelet是什么，时序序列之间距离的度量方式等；第二部分：文章的模型及相关工作，从我的角度出发进行解读，其中的一些见解和想法仅供大家参考。还是那句话：不喜勿喷，谢谢！

第一部分

Shapelet:一种时序序列度量的”度量衡”

Shapelet其实就是一种表征某些序列特点，以达到区分序列的效果。最初的Shapelet被用于做两种不同的荨麻叶的分类，如下所示

对于某类特殊的荨麻叶，我们可以按照其形状，使用angle-based method对原始的绿叶形状进行转化，变成一个时序序列。如下所示。

显然，不同的事物必定会存在着不同的特征以供区分。这两种荨麻叶也存在着不同的特征。如下所示

第一类荨麻叶的根茎和叶片的夹角是一个钝角，第二类荨麻叶的根茎和叶片的夹角近似为一个直角，而两者表现在时序序列中的特点就是所谓的Shapelet。

以此为分类的判定基准，对于任一一片这两种荨麻叶，只要将这个荨麻叶按照相同的特定的某种方法(angle-based method)将之转换为时序序列，然后计算时序序列和两个Shapelet之间的最小距离，两者中距离值较小的那个就可以判定，待测的荨麻叶属于Shapelet获取处的那一类荨麻叶。

至于，什么是angle-based method,这里不作介绍，想继续深入了解的小伙伴可以去参考论文《LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures》。下面将介绍一下有关距离度量的具体方法。

时序序列度量方法:欧氏距离度量和DTW(Dynamic Time Warpping)动态时间规整

传统的计算两个等长的时序序列$X=x_1,x_2,\dots ,x_l$和$Y=y_1,y_2,\dots ,y_l$之间差异的方法就是计算每个点对应的欧式距离，即

$$Dist(X,Y)=\sum _{i=0}^l\sqrt{(x_i-y_i{)}^2}$$

但是，两段时间序列不可能平行，即对应同一角标的点，可能不是一组离得最近的点。就如下图所示：

这样就带来了一个问题：如果两个时间序列长的不是很像(即距离最近的一对点不是同一下标)，而我们需要的差异需要考虑到两段相似时间序列特征之间的距离，并非简单地定义点到点之间的距离。那么，怎么办呢？

首先，找到第一个时间序列上每个点到另一个时间序列上最近点的一个对应关系，如上图所示，就是一个DTW(Dynamic Time Warpping)的典型例子。我们可以使用动态规划的方法，不断找出对应的点。
一般的动态规划的算法如下所示：

$$dp(i,j)=min(dp(i-1,j-1),dp(i-1,j),dp(i,j-1))+d(i,j)$$

SubsequenceDist(Shapelet)

考虑完了等长序列的情况了，那么，如果遇上了两段时间序列不等长的情况，该怎么做呢？

Shapelet的论文中提出一种易于理解的方法：先从长度较大的时间序列中开始处截取出一段和短时间序列等长的时间序列，然后，计算子序列和短序列之间的距离，然后在长序列上以步长为1滑动子序列，计算每次滑动出的子序列和短序列之间的距离，选出这些距离中的最小值，作为原短序列和长序列之间的距离。
具体的定义：SubsequenceDist(T,S) 是一个距离函数，以时间序列T和子序列S作为输入，返回一个非负值d，即为T到S的距离。

$$SubsequenceDist(T,S)=min(Dist(S,S^{{}^{\prime }}))，S^{{}^{\prime }}\in {\text{S}}_T^{|S|}$$

$S^{{}^{\prime }}$即为T中长度为|S|的子序列。

TCN(Temporal Convolution Network) & Causal Convolution & Dilated Convolution & ResBlock

TCN是时域卷积网络的缩写，由具有相同的输入和输出长度的扩展卷积(Dilated Convolution)和因果卷积(Causal Convolution)组成。

而本论文中的方法主要参考的是TCN，这篇文章提出一种既能提升感受野，并且加入ResBlock，能够使之具有较大深度的时序网络模型。

现在我简单的阐述以下扩展卷积、因果卷积是什么。

Causal Convolution

对于一维全卷积来说，无非就是卷积核在原始的时间序列上进行滑动，然后依次对其做卷积运算，得出输出序列，而这样的操作往往会使得序列被不断地压缩，就是一个下采样的过程，而因果卷积却能保证输出的序列长度和输入的序列长度一致。那么，这又是怎么保证的呢？ 答案无非是零填充以及对卷积运算的一些简单的重定义。

首先，要保证输入和输出的长度一致，最常用也最直接的方法就是对输入数据作零填充，那么，怎么作零填充呢？是两边同时零填充还是一边作零填充呢？

我们先来看一下这张因果卷积图，然后再慢慢分析。

从左往右看，分析选中的输入和输出元素，此时卷积核的大小为2，步长为1，我们做了一下1位的左零填充，如图所示，输入和输出(其实就是第一隐层)的长度是一样的，原因在于做了一位的左零填充，并且，对于输入长度$\{0,\dots ,inputlength-1\}$(这里是{0,1,2,3}),输出的第i个元素与输入的$\{0,\dots ,i\}$个元素有关。

但是，这样就会存在一个问题，这种输入和输出的关系是$i\to i$的，即是线性的，这样就会减小输出的感受野，并且当需要足够大的感受野时，就需要很大的模型深度，这也会存在梯度消失等问题，所以需要分别进行改进。

Dilated Convolution

扩张卷积其实是为了能够加大原本因果网络的感受野。扩张卷积定义了一个扩张因子d,使用感受野按层数呈指数型增长，如下图所示：是一个扩张因子为2的5层网络结构。

可以看出，扩展因子本身就是规定了卷积核中关联输入元素之间的距离，第一个隐层获得的输出，关联的输入元素之间差了$2^0=1$，第二个隐层即查了$2^1=2$个元素点，依此类推至更深层网络。

ResBlock

而ResBlock即是为了加深网络模型而加上的。

残差(Residual)可以加深网络深度的原因在于它们可以帮助解决深度神经网络中的梯度消失问题。在传统的神经网络中，每个层都会对输入进行转换，输出给下一层作为输入。随着网络层数的增加，这种转换会导致输入信号的信息逐渐丢失，导致梯度消失或梯度爆炸。

而引入了残差连接后，输入信号可以绕过某些层而直接到达后面的层，从而保留更多的信息。残差块内部的跳跃连接允许来自前一个层的信息以原始形式流经整个块，并与来自该层本身的信息相加。这使得网络能够更容易地学习到残差部分的变化，而不是试图重新学习整个映射。因此，残差连接可以提高模型的准确性和稳定性，使得网络可以更深、更复杂，同时仍然具有良好的收敛性和优化性能。

需要注意的是，因为本文中需要处理不同长度的输入数据而获得相同长度的输出，所以会出现输出和要连接的残差信息长度不一的情况，这时候就需要使用Identity Mapping的操作了。如下图所示

第二部分

这一部分主要描述论文中所提到的模型及相关损失函数的定义及方法思路。

模型

首先是，整个Paper用的网络模型，如下图所示。

从模型上来看，首先将多元数据进行滑窗处理，截取出许多不同长度的时间子序列，然后对这些子序列进行处理，获得相应的锚点、正例和负例，然后对数据使用Mdc-CNN进行Encoder操作。对Encoder后的Embeddings进行聚类，然后选取出每簇距离聚类中心最近的那一个点或者就是聚类中心，然后进行Decoder获取出对应的原始序列，然后使用shapelet transformation操作比较各个原始序列对于选取的shapelets(假设有n个)的SubsequenceDist，获得多个n元组，然后基于这些n元组进行聚类，即可达到MTSC的效果。

锚点生成

锚点的生成算法就原paper中没有提及，而在Paper的补充材料中有提及相应的伪代码，过程如下：

首先看伪代码：

整个算法的大致流程：将所有的候选波型进行聚类(聚类标准paper未提及，但从整个算法模型和代码上来看，应是按照序列波形之间的距离度量。sklearn.Kmeans) 假设共分为4类，先从第一类中随机选出一个锚点，然后从该类中选出距离最近的top-k个正例，然后从其他簇类中选出相当的负例。同理在其他三类上进行同样的算法。如下图所示：

但从作者公布的源代码来看，并不是这样生成的。

他是在使用KMeans算法后，计算每个点到其他点的距离后，获取distance_i后，然后选取距离最小的num_positive+1个点，然后将其中的第一个点作为锚点，这才是具体的生成过程。

损失函数

本文有提到很多聚类算法，这也就意味着会存在很多的损失函数，但用于网络模型优化的仅有一个损失函数，即cluster-wise triplet loss。

cluster-wise triplet loss

$$L_{triplet}=\log \frac{D_{AP}+\mu }{D_{AN}}+\beta D_{intra}$$

其中,$D_{AP}$ 表示锚点Anchor到正例Positive的距离， D_{AN}同理;

$$D_{intra}=D_{pos}+D_{neg}$$

而其中

DAP=1K+∑i=1K+∣∣f(x)−f(xi+)∣∣22,DAN=1K−∑i=1K−∣∣f(x)−f(xi−)∣∣22, D_{AP} = frac{1}{K^{+}}sum_{i=1}^{K^{+}} ||f(x) – f(x_i^{+}) ||^2_2,

D_{AN} = frac{1}{K^{-}}sum_{i=1}^{K^{-}} ||f(x) – f(x_i^{-}) ||^2_2,DAP​=K+1​i=1∑K+​∣∣f(x)−f(xi+​)∣∣22​,DAN​=K−1​i=1∑K−​∣∣f(x)−f(xi−​)∣∣22​,

$D_{pos}$表示所有正例之间距离的最大值，$D_{neg}$同理。

$$D_{pos}{=}_{i,j\in (1,K^{+})\cap i<j}^{max}\{||f(x_i^{+})-f(x_j{)}^{+}|{|}_2^2\}$$

而这个显然是不可导的，所以将之近似为

$$D_{pos}=\frac{{\sum }_{i=1}^{K^{+}}{\sum }_{j=1}^{K^{+}}{D}_{i,j}^{+}{e}^{\alpha D_{i,j}^{+}}}{{\sum }_{i=1}^{K^{+}}{\sum }_{j=1}^{K^{+}}{e}^{\alpha D_{i,j}^{+}}}$$

这个就能够求导，然后训练网络了。

至此，关于我对于ShapeNet这篇文章的一点见解已经全部写完，感谢您能够看到这。谢谢！如果有什么问题，欢迎留言，大家一起讨论，共同进步。