Learnable Dynamic Temporal Pooling for Time Series Classification

With the increase of available time series data, predicting their class labels has been one of the most important challenges in a wide range of disciplines. Recent studies on time series classification show that convolutional neural networks (CNN) achieved the state-of-the-art performance as a single classifier. In this work, pointing out that the global pooling layer that is usually adopted by existing CNN classifiers discards the temporal information of high-level features, we present a dynamic temporal pooling (DTP) technique that reduces the temporal size of hidden representations by aggregating the features at the segment-level. For the partition of a whole series into multiple segments, we utilize dynamic time warping (DTW) to align each time point in a temporal order with the prototypical features of the segments, which can be optimized simultaneously with the network parameters of CNN classifiers. The DTP layer combined with a fully-connected layer helps to extract further discriminative features considering their temporal position within an input time series. Extensive experiments on both univariate and multivariate time series datasets show that our proposed pooling significantly improves the classification performance.


Introduction
In the last two decades, time series classification has been dominated by nearest neighbor classifiers which utilize handcrafted feature-based representations (Baydogan, Runger, and Tuv 2013;Schäfer 2015) or various distance measures between time series (Zhao and Itti 2018;Yuan et al. 2019b). Recently, there have been several attempts to exploit deep neural networks (DNN) for time series classifiers (Zheng et al. 2016;Zhao et al. 2017;Wang, Yan, and Oates 2017); they do not require heavy crafting on feature engineering or data preprocessing, and easily be applied to multivariate time series as well. In practice, fully convolutional networks (FCN) and residual networks (ResNet) designed for time series classification (Wang, Yan, and Oates 2017) showed the state-of-the-art accuracy among various DNN competitors (Fawaz et al. 2019).
However, the existing convolutional neural networks (CNN) are not able to fully utilize the temporal information of high-level features for their classification. On top of convolutional layers, the CNN classifiers adopt global average pooling (GAP) or global max pooling (GMP) that simply aggregates all hidden vectors along the time axis. By doing so, they can obtain a global representation for an input time series, as well as avoid the overfitting problem with the help of much fewer model parameters. Nevertheless, such global aggregation discards the temporal position of the hidden features, which makes the CNN learn only positioninvariant temporal features. Since each temporal position itself could be a useful feature for discrimination among different classes in time series classification, the global pooling layer eventually degrades the performance of the classifiers.
To address this limitation, we propose a novel pooling method that effectively reduces the temporal size (i.e., length) of network outputs while minimizing the loss of temporal information. Motivated by the observations that time series instances consist of multiple segments with distinct patterns, our dynamic temporal pooling (DTP) outputs a pooled vector for each segment rather than the one for a whole series. The DTP layer produces segment-level representations by aggregating hidden vectors in each segment, thus it enables to model the classification score based on segment-specific class weights. In other words, our CNN classifiers replace the global pooling with the segmentlevel pooling (being followed by a fully-connected layer), which allows extracting further class-discriminative features and improves the classification accuracy. We additionally present the class activation map (CAM) specifically for our DTP layer, indicating how much each temporal region contributes to predicting the class label of an input time series.
The challenge here is to find out consistent segments from input time series instances that are not temporally aligned with each other. To this end, the DTP layer performs semantic segmentation by using dynamic time warping (DTW). We first introduce trainable latent vectors as many as the number of segments to be identified, termed as prototypical hidden series, for encoding the prototypical features of each segment into them in a temporal order. Then, the DTP layer aligns the network outputs (i.e., the series of hidden vectors) with the prototypical hidden series while keeping their temporal order based on DTW; this generates the set of consecutive time points matching with each segment. In the end, we simultaneously optimize the network parameters of CNN classifiers and the prototypical hidden series, thereby both of them collaboratively improve with each other. That is, training the CNN assists to capture the prototypical features of the segments, and also learning the prototypical hidden series helps the CNN to extract discriminative features. Our empirical evaluation on extensive univariate and multivariate time series datasets demonstrates that the proposed pooling technique significantly improves the discrimination power of the CNN classifiers, regardless of its network architecture or pooling operation. The CNN classifiers with the DTP layer also beat nearest neighbor classifiers that use various distance measures by a large margin. Furthermore, we qualitatively show that the DTP layer is capable of providing an interpretable analysis on its classification result by localizing discriminative regions within a target time series.

Related Work Deep Learning for Time Series Classification
With the great success of deep learning, a variety of deep neural networks (DNN) have been applied to time series classification, and they achieved higher accuracy than conventional nearest neighbor classifiers (Fawaz et al. 2019). Among them, convolutional neural networks (CNN) have gained much attention, such as fully convolutional networks (FCN) and residual networks (ResNet) (Wang, Yan, and Oates 2017), because of their capability of capturing local patterns as well as efficient inference by parallel computations. As presented in Figure 1, the stack of multiple convolutional layers outputs the hidden vector at each time point, 1 which eventually encodes high-level features about the local temporal context 2 surrounding the time point. Based on global average pooling (GAP) or global max pooling (GMP), all the hidden vectors are summarized along the time axis into a single vector (Figure 1a), and it is finally used for computing classification scores.
However, such global pooling causes the loss of information about temporal dynamics of the high-level features, and this leads to the limited performance. In case of time series classification, local temporal patterns can have different meanings depending on their temporal positions where they occur (i.e., position-variant), unlike image classification where the position of visual semantic features does not much affect its class label (i.e., position-invariant). Nevertheless, using the fully-connected layer (with local pooling after each convolution) instead of the global pooling layer, e.g., Time-LeNet (Le Guennec, Malinowski, and Tavenard 2016), not only requires a large number of parameters increasing with the length of time series but also makes the network overfitted to the training data (Fawaz et al. 2019).

Differentiable Dynamic Time Warping
Dynamic time warping (DTW) is a popular technique for measuring the distance between two time series of different lengths, based on point-to-point matching with the temporal consistency. Given two times series X and Y of length M and N , the (m, n)-th entry of its cost matrix ∆(X, Y ) ∈ R M ×N represents the distance (or alignment cost) between X m and Y n . The DTW distance between X and Y is defined by the minimum inner product of the cost matrix and any binary alignment matrix A, where A ⊂ {0, 1} M ×N is the set of possible binary alignment matrices whose (m, n)-th entry indicates whether X m and Y n are aligned or not. Each alignment matrix corresponds to a warping path that connects the upper-left (1, 1)th entry to the lower-right (L, T )-th entry using ↓, →, moves. That is, DTW searches for the optimal warping path that minimizes the total alignment cost, and the path eventually represents the best temporal alignment between the two series. The DTW distance and its alignment matrix can be efficiently obtained by dynamic programming based on Bellman recursion, which takes a quadratic O(M N ) cost.
Recently, the continuous relaxation of DTW (Cuturi and Blondel 2017), named as soft-DTW, has been proposed in order to calculate the gradient of DTW with respect to its input series. Instead of the discontinuous (i.e., nondifferentiable) hard-min operation taking only the minimum value in Equation (1), soft-DTW utilizes the soft-min operation with a smoothing parameter γ by adopting the concept of global alignment kernels (Cuturi et al. 2007). The soft-DTW distance between X and Y is calculated by (2) Note that the original DTW is the special case of soft-DTW with γ = 0. The differentiability of soft-DTW facilitates the optimization of distance (or similarity) among time series in deep learning frameworks.

Dynamic Temporal Pooling Problem Formulation
Given a training set of N time series instances from C classes, we aim to train a CNN classifier that accurately predicts the class label of an input time series instance. For each

Temporal Pooling based on Segmentation
The purpose of our temporal pooling is to reduce the temporal size T of the hidden representation (i.e., the output of f ), while minimizing the loss of temporal information in the time series. The key idea is to partition a series of hidden vectors into L segments (L T ) then generate pooled representations by summarizing the vectors in each segment. Formally, the temporal pooling layer outputs the series of pooled vectorsH = [h 1 , . . . ,h L ] ∈ R K×L of length L, whose l-th vector is obtained as follows.
where φ is the pooling operation, and T l = {t l−1 +1, . . . , t l } is the set of consecutive time points belonging to the l-th segment (t 0 = 0, t L = T ). Three functions can be used for the pooling operation: calculating the average value (denoted by avg), the summation value (denoted by sum), and the maximum value (denoted by max) for each latent dimension. A straightforward strategy for segmentation is to partition a whole time series into shorter ones of the same length in a static manner (Figure 1b), but it has several limitations that have to be addressed. First, time points from different time series instances are not temporally aligned in general, which makes it difficult to find absolute temporal locations for segmentation (Figure 2, upper). Furthermore, considering a segmentation task aims to discover distinct temporal patterns which are internally homogeneous, the length of each optimal time series segment cannot be the same as the others' in most cases (Figure 2, lower).
To tackle these challenges, we perform semantic segmentation by matching each time point with its semanticallyclosest segment in a temporal order. To this end, we first introduce a prototypical hidden series P = [p 1 , . . . , p L ] ∈ R K×L of length L which best summarizes the high-level features of L segments. Our proposed method, termed as dynamic temporal pooling (DTP), temporally aligns the series of prototypical hidden vectors (i.e., P) with that of target hidden vectors (i.e., H) by using DTW. Based on the result of DTW alignment, the series of hidden vectors is partitioned into L segments (Figure 3), and each of them is pooled by Equation (3). In this case, the optimal alignment matrix A * between P and H can be obtained by ∆ ∈ R L×T is the alignment cost matrix whose (l, t)-th entry δ(p l , h t ) encodes the distance between p l and h t . We define the cost by using their cosine similarity as follows. 4 δ(p l , ht) = 1 − p l · ht p l 2 ht 2 .
Unlike eligible warping paths of conventional DTW, we need to impose an additional constraint that each time point should be aligned only with a single segment. Thus, we limit A to the set of possible binary alignment matrices representing a path that connects the upper-left (1, 1)-th entry to the lower-right (L, T )-th entry using only →, moves.
As we discussed, soft-DTW is differentiable with respect to its input, thus P can be easily optimized using the gradients ∇ P DTW γ produced by Equation (6). Similar to the original DTW, the soft-DTW distance (and the soft alignment matrix) can be obtained by solving a dynamic program based on Bellman recursion. Algorithm 1 describes the process of forward and backward recursions to compute the alignment cost DTW γ (P, H) and its gradient ∇ P DTW γ (P, H). Please refer to (Cuturi and Blondel 2017) for more details of deriving the algorithms. Note that a single time point should not be aligned with multiple consecutive segments. For this reason, our forward recursion does not allow the ↓ relation in its recurrence (i.e., R l,t depends on only R l−1,t−1 and R l,t−1 ), and accordingly, the backward recursion does not consider the ↑ relation (i.e., E l,t is obtained from E l,t+1 and E l+1,t+1 ).
Learning the parameters of the CNN classifier Instead of the class weight vector w (c) ∈ R K that learns the importance of each latent dimension for class c, we introduce a class weight matrix W (c) = [w L ] ∈ R K×L in order that the class weights are independently modeled for each segment. Using the pooled vectors and the class weight matrices, we calculate the classification score s (c) = L l=1h l · w (c) l , and the posterior probability that an input time series instance belongs to class c is defined as follows: The network parameters W and class weight matrices {W (c) } are optimized by the following classification loss.
log P (y = y n |X n ) (8) To sum up, our CNN classifier adopts the segment-level fully-connected layer for time series classification, by combining Equation (7) with the DTP layer.
Optimization All the parameters including the prototypical hidden series, the network parameters, and the class weight matrices are effectively optimized at the same time, by minimizing the corresponding losses: Note that we consider H = f (X; W) rather than X for DTW alignment (Equations (4) and (6)), so as to perform semantic segmentation in the latent space where the high-level features are embedded. For this reason, P and H collaboratively improve with each other during the training, and each of them respectively captures stereotypical macro-patterns and discriminative micro-ones. Training the network parameters of CNN classifiers (Equation (8)) helps to learn the prototypical high-level features of each segment, while optimizing the prototypical hidden series (Equation (6)) facilitates the CNN to learn further discriminative features by providing more consistent segments.

Class Activation Map for Temporal Pooling Layer
For further explanation on how much each temporal region (or time point) contributes to the classification of a target time series, we tailor a class activation map (CAM) (Zhou et al. 2016;Wang, Yan, and Oates 2017) for CNN classifiers with the DTP layer. CAM has been used to localize the regions relevant to the target class within a time series, but it cannot take into account the segment-specific class weights and also requires the class weights trained for the GAP layer.
Inspired by Grad-CAM (Selvaraju et al. 2017), we generalize the activation map for class c at time point t by The point-wise gradient ∂s (c) /∂h t,k , which implies the position-specific class weights, is used as the weight for each hidden feature h t,k . For example, M (c) t becomes equivalent to w (c) l · h t , if h t is aligned with the l-th segment by the temporal sum pooling. Using the CAM, we can identify discriminative regions or temporal patterns while considering different class weights for each segment.  from the UCR/UEA repository Dau et al. 2018). As the datasets are publicly available as well as collected from a wide range of domains, they have been widely used for the time series classification task.
Baselines As our main baselines, we use CNN classifiers equipped with different temporal pooling layers. For the experiments, we build three types of temporal pooling with avg, sum, and max operations: global temporal pooling (GTP), static temporal pooling (STP) with the fixed pooling size, and the proposed dynamic temporal pooling (DTP). We remark that several DNN architectures that have been studied for time series forecasting, for instance, dilated CNN (Oord et al. 2016), autoregressive model based on recurrent neural networks (Lai et al. 2018;Rangapuram et al. 2018), and transformer (Li et al. 2019), cannot be directly applied to time series classification (i.e., instance-level label prediction). All of them need to be customized or tuned to obtain the representation for an input time series instance; in this sense, our DTP layer can be easily generalized for the architectures as well, but we leave this for future work.
In addition, we compare our classifiers with nearest neighbor classifiers using various distance measures, especially for univariate time series. 5 Since the purpose of our work is to enhance the discrimination power of a single classifier, we exclude ensemble classifiers Lines and Bagnall 2015;Lines, Taylor, and Bagnall 2016) that require highly intensive computations for exploiting dozens of classifiers together. Implementation details We employ two CNN architectures, FCN and ResNet, specifically designed for time series classification (Wang, Yan, and Oates 2017); they showed the best accuracy among various types of DNNs (Fawaz et al. 2019). We implement all the CNN classifiers using PyTorch, and make use of the Numba compiler to compute the forward and backward recursions of the DTW (Algorithm 1) in parallel. 6 In order to eliminate the benefit from hyperparam- eter tuning, we train our classifiers without introducing the weight that balances the two losses, and also fix the number of segments L to 4 for STP and DTP. 7 Table 1 describes the details of hyperparameters used in our experiments.
Evaluation strategy For quantitative evaluation, we conduct the pairwise posthoc analysis (Benavoli, Corani, and Mangili 2016) that statistically ranks different classifiers according to their accuracy over multiple datasets, as done in (Fawaz et al. 2019;Yuan et al. 2019b). We visualize the results by the critical difference (CD) diagram (Demšar 2006) which indicates the average rank of each classifier with thick horizontal lines showing a group of classifiers that are not significantly different (p = 0.05). For all the datasets, we repeatedly train each classifier three times with different random seeds, and report the median accuracy.

Comparison of Different Pooling Layers
We first directly compare the classification accuracy of our proposed CNN classifier (using DTP) with that of the baseline CNN classifier (using GTP). In Figure 4, a single dot represents each dataset, thus how far each dot is located from the y = x line indicates the performance gap between the two pooling methods. For all the cases, we observe that most of the datasets are dotted in the lower right side of each figure, showing that DTP outperforms GTP regardless of its CNN architectures and pooling operations. In particular, the performance improvement of DTP over GTP becomes larger when it is used with the max operation. As the max pooling is effective to detect specific features in general,  the DTP-MAX becomes good at discovering such features segment-specifically, which makes the final representation further class-discriminative. For more statistical evaluation, we also compare different temporal pooling methods (i.e., GTP, STP, and DTP) based on pairwise statistical tests. Figure 5 presents their average rank over a bunch of datasets (85 for the univariate case, and 30 for the multivariate case) with the pairwise statistical differences. Specifically, DTP consistently performs the best among all types of temporal pooling while GTP performs the worst. In case of STP, it shows slightly better but not much statistically different performances than GTP, even though it considers the same number of segments with DTP; this implies that pooling the vectors from same-length segments at fixed temporal positions cannot effectively boost the accuracy of CNN classifiers. On the contrary, our DTP method, which uses variable-length segments identified by DTW, is capable of modeling high-level features depending on each segment, thus its discrimination power improves a lot. We can conclude that DTP successfully utilizes temporal information for its classification compared to GTP and STP.

Comparison with Nearest Neighbor Classifiers
As the nearest neighbor classifier has been one of the powerful benchmarks in the field of univariate time series classification, we compare their performances with ours. For the nearest neighbor classifier, we consider 8 different dis-   (Yuan et al. 2019a), and LSDTW (Yuan et al. 2019b). Figure 6 clearly shows that the CNN classifiers (DTP-MAX) beat all the other classifiers by a large margin. In addition to its higher accuracy, the deep learning approach has some benefits in terms of efficiency and scalability. To predict the class label of an input time series instance, our classifiers require only a single CNN inference with an additional cost of O(LT ) for the DTW alignment between P and H. By contrast, the nearest neighbor classifiers need to perform O(N ) comparisons to find the closest instance from the input time series, and each comparison takes O(T 2 ) for computing the DTW-based distance based on point-to-point matching. This highly limits the scalability of the nearest neighbor classifiers with respect to N and T .

Parameter Analysis on L
We investigate the performance changes of the CNN classifiers (DTP-AVG and DTP-MAX) on the multivariate datasets, increasing the number of segments (i.e., L) from 2 1 to 2 4 . In Figure 7, a single line denotes each dataset, and its color is determined by the optimal value of L that achieves the highest accuracy. The tendency of performance changes is not consistent over most of the datasets, and also the optimal number of segments varies depending on the dataset. As illustrated in Figure 2, time series instances in a dataset share their own temporal patterns and lengths, which are distinguished from the ones in other datasets. For this reason, the optimal number of segments largely depends on such properties of each dataset. This result strongly indicates that finding the optimal L value for a target dataset can further enhance the performance of the CNN classifiers in practice, compared to the case of using the fixed L in our experiments.

Qualitative Analysis
To qualitatively compare the localization performance of GTP and DTP, we visualize their CAM scores by highlighting the input time series proportionally to the scores. In Figure 8a and 8b, the time series instances of class 1 and 2 are colored in red and blue, respectively, and we use the CAM scores after normalizing them in the range of [0, 1] for each time series instance. Although the two CNN classifiers achieve almost the same accuracy for both the datasets (i.e., GunPoint and TwoLeadECG), they highlight different regions as the discriminative temporal patterns that most contribute to predicting its class label. It is worth noting that the localized regions discovered by DTP are more clearly distinguishable between the classes compared to GTP, which results in better interpretability of the CNN classifiers. Furthermore, Figure 8c provides segmentation results obtained from the DTP layer; each time series instance is divided into four segments by vertical lines. The l-th segments (l = 1, . . . , 4) of all instances share similar (or consistent) temporal patterns, even where their original input series are not temporally aligned. The results support that our prototypical hidden series P successfully encodes the prototypical high-level features of the segments in a temporal order, thereby the DTP layer can perform semantic segmentation based on the DTW alignment between P and H.

Conclusion
This paper proposes a dynamic temporal pooling, termed as DTP, which outputs the pooled vectors from temporallyordered segments; this enables CNN classifiers to make use of the segment-level fully-connected layer for time series classification. We present a learning framework to simultaneously optimize the network parameters of a CNN classifier and the prototypical hidden series that encodes the latent semantic of the segments. By finding the optimal alignment between the prototypical hidden series and the hidden representation of a target time series, the DTP layer is able to partition the whole series into a fixed number of segments. Our extensive experiments show that the proposed DTP layer outperforms other baseline pooling layers, and it successfully identifies consistent segments from time series instances that are out of temporal alignment.