Classification of Long Sequential Data using Circular Dilated Convolutional Neural Networks

Lei Cheng, Ruslan Khalitov, Tong Yu, Zhirong Yang

Introduction

Sequence classification is the task of predicting class labels for sequences. It is of central importance in many applications, such as document classification, genomic analysis, and health informatics. For example, classifying documents into different topic categories is a challenge for library science, especially for modern digital libraries . Genomic classification help researchers to further understand some diseases . Classifying ECG time series tells if someone is a healthy person or a patient with heart disease .

Machine Learning, especially Deep Learning, becomes widely used in end-to-end sequence classification, where a single model learns all steps between the initial inputs and the final outputs. Recurrent Neural Networks (RNNs), Transformers, and Convolutional Neural Networks (CNNs) are three primary techniques for analyzing sequential data.

RNNs use their internal states to process the sequence step by step. Despite success for short sequences, traditional RNNs cannot scale to very long sequences . One reason is that they are challenging to train due to exploding or vanishing gradient problems . In addition, the prediction of each timestep must wait for all its predecessors to complete, which makes RNNs difficult to parallelize. Transformers are a family of models relying on self-attention mechanism . They have quadratic time and memory complexities to the input sequence length because they compute pairwise dot-products. Comprehensive approximations are required to reduce the cost .

In contrast, CNNs are able to handle very long sequences. A convolutional layer uses sparse connections and no recurrent nodes. Therefore, CNNs are easier to train and parallelize. In addition, dilated convolutions can exponentially enlarge the receptive fields, allowing CNNs to use fewer layers to capture long-term dependencies. For example, Temporal Convolutional Networks (TCNs) recently provide remarkable performance on sequence regression tasks . However, the performance of TCNs for classification tasks is not satisfactory. TCNs use causal convolutions which implement a skewed connection protocol. The asymmetric design causes a tendency to focus on the latter part of a sequence.

In this paper, we propose a novel convolutional architecture named Circular Dilated Convolutional Neural Network (CDIL-CNN), which can scale to very long sequences and have superior performance on various classification tasks. Unlike TCNs, we use symmetric convolutions to mix information, and thus every position can receive both earlier and later information from previous layers in a circular manner. Unlike conventional pyramid-like CNN architecture, every position of the last convolutional layer in our design has an equal chance to receive all information from the whole sequence and gives its classification logits. Then a simple average ensemble learning helps our model achieve better accuracy.

We have tested our model on extensive sequence classification tasks, including synthetic data, images, texts, and audio series. Experimental results show that CDIL-CNN outperforms several state-of-the-art models. Our method can accurately and robustly classify across tasks with both short-term and long-term dependencies for very long sequences.

The remaining of the paper is organized as follows. We review some popular models for sequential data and their limitations in Section 2. In Section 3, we present our model, CDIL-CNN, including its connection protocol and network architecture. Experimental tasks and results are provided in Section 4, and we discover that the simple convolutional network has superior performance over other models in various scenarios. Finally, we conclude the paper in Section 5.

Related Works

Many deep neural networks have been proposed for various sequence classification tasks. RNNs, Transformers, and CNNs are three significant branches for learning from sequential data.

RNNs read and process inputs sequentially. At each timestep, an RNN takes the current sequence element and the hidden state as the input and outputs the next hidden state. The hidden state at a timestep is expected to act as the representation of all its earlier inputs. Because the prediction of each timestep must wait for all its predecessors to complete, the sequential process is difficult to parallelize, which makes RNNs hard to handle very long sequences. Moreover, basic RNNs suffer from vanishing and exploding gradient problems, making model training very difficult for long sequences . Gated RNNs, such as Long Short-Term Memory (LSTM) and Gated Recurrent Unit (GRU) , have been proposed to relieve the gradient problems. They have many additional gates to regulate the flow of information. The gated RNNs are used in many sequence classification tasks, such as ECG arrhythmia and text . However, they can process only short sequences (about 500-1000 timesteps) .

Transformers, a family of models based on attention mechanism, quantify the interdependence within the sequence elements (self-attention). Originally, attention was used in conjunction with recurrent networks and convolutional networks . Later, Transformer, an architecture based solely on attention mechanism, was proposed. The vanilla Transformer computes pairwise dot-products between all sequence elements, which leads to a quadratic complexity w.r.t. the sequence length and makes it infeasible to process very long sequences. Approximated attention methods have been proposed to tackle this problem. Sparse Transformer , LogSparse Transformer , Longformer , and Big Bird use sparse attention mechanism. Linformer and Synthesizer apply low-rank projection attention. Performer , Linear Transformer , and Random Feature Attention rely on kernel approximation. Reformer , Routing Transformer , and Sinkhorn Transformer follow the paradigm of re-arranging sequences. However, their approximation quality is questionable. Later in Section 4, we will show that their performance is inferior for long sequence classification.

CNNs are good at processing data that has a grid-like topology. Two-dimensional CNNs achieve great success in computer vision , while one-dimensional CNNs are commonly used for sequential data . Among these models, TCNs which use causal convolutions with skewed connections attempt to capture the temporal interactions and have been applied to various regression tasks, such as action segmentation and detection , lip-reading , and ENSO prediction . The comparison of the convolutional and recurrent architectures shows that a simple TCN outperforms canonical RNNs across a wide range of sequence modeling tasks .

Circular Dilated CNN

Although TCN is suitable for long sequence regression, their performance for classification is not satisfactory. In this paper, we propose a new convolutional model, named CDIL-CNN, to overcome the TCN drawbacks in long sequence classification. More details are described as follows.

Our model uses symmetric convolutions that can receive both earlier and later information from previous layers. Because no information is allowed to be leaked from future to past in regression tasks, TCN uses causal convolutions that implement a skewed connection protocol, meaning that the output at timestep $t$ can only receive information of $t$ and earlier from previous layers. However, classification tasks do not have the restriction because the classification result depends on the whole sequence. Therefore, symmetric convolutions help our model better capture interactions.

Our model also uses increasing dilation sizes with the depth of the network. Dilated convolutions (or atrous convolutions) were originally introduced for dense image prediction, where they helped the model to capture multi-scale information . For 1D CNNs, dilated convolutions are generally used to enlarge the receptive fields . Following these works, we increase the dilation sizes exponentially, i.e., $d_{l}=2^{l-1}$ where $d_{l}$ is the dilation size at the $l$ -th convolutional layer. The combination of deep networks and exponentially dilated convolutions enables the receptive fields to expand quickly, which makes our model scalable to very long sequences. Our model needs $\lceil\log_{2}\frac{N}{2}\rceil$ or $O(\log_{2}N)$ layers to achieve a full receptive field for sequence length $N$ .

To avoid notional clutter, we start from the $D=1$ case. Let $[a_{1},a_{2},\cdots,a_{N}]$ denotes an 1-dimensional input sequence of the $l$ -th convolutional layer. The convolutional output $b_{t}$ at the $t$ -th ( $1\leq t\leq N$ ) position is computed by $b_{t}=\sum\limits_{k=0}^{K-1}w^{(l)}_{k}\cdot a_{t+\left(k-\frac{K-1}{2}\right)\cdot d_{l}}$ , where the kernel size $K$ is usually an odd numberWe used $K=3$ in all our experiments. and $w^{(l)}$ are the convolution coefficients of the $l$ -th layer. See Figure 1 for an illustration of a 3-layer symmetric dilated convolutions with $K=3$ . It is straightforward to extend the convolution with the bias term and for the $D>1$ cases.

2 Circular Mixing

We use a circular protocol because its corresponding circular padding can relieve the boundary effect . In our model, a signal on one end is no longer convoluted with zeros but with signals from the other end. Circular padding makes our model more robust to data shift and less sensitive to absolute position information. The circular dilated convolutions are shown in Figure 2. The convolutional output $b_{t}$ becomes

Using circular dilated convolutions, our model can connect boundary positions and learn long-term dependencies even in the first layer, unlike lower layers of traditional CNNs which only focus on local information. In our design, every position of the last convolutional layer has an equal chance to receive all information of the whole input sequence. Therefore, our model can apply a simple average ensemble learning as below.

3 Ensemble Learning

Our model also uses residual connections to facilitate the training and to improve the accuracy . A residual block contains a skip connection where the inputs are added before the block outputs. A schematic view of our model is depicted in Figure 3.

Experiments

We have compared our model with many popular models (including RNNs, Transformers, and CNNs) on various long sequential datasets in three groups of experiments. First, we used a synthetic dataset with increasing sequence lengths to show the scalability of our model. Then, we tested our model on the Long Range Arena (LRA) benchmark suite which contains different dependencies. Finally, we tried three time series classification datasets that contain important local information and much noise. All experiments were run on a Linux server with one NVIDIA-Tesla V100 GPU with 32 GB of memory. More details are given in the supplemental document.

The XOR problem is a classical classification problem in artificial neural network research which cannot be solved by a single perceptron . We created more challenging XOR tasks with increasing sequence lengths. For each length $N$ , a sequence consists of $N$ pairs of numbers, where the first number, called value, is randomly chosen from the interval $[0,1)$ , and the second number is used as a marker. Most markers are 0 except two 1’s at randomly selected positions. Let $X_{1}$ and $X_{2}$ denote the two values at the 1-marked positions. A sequence belongs to Class 0 if the values belong to the same half interval, i.e., $(X_{1}<0.5$ and $X_{2}<0.5)$ or $(X_{1}\geq 0.5$ and $X_{2}\geq 0.5)$ . Otherwise, the sequence is labeled as Class 1. Figure 4 shows four examples of the XOR problem. We have used $N=2^{n}$ , where $n=4,\dots,11$ . A larger $N$ corresponds to a more challenging task. For each $N$ , training, validation, and testing sets respectively have 10000 labeled sequences.

We have compared our model with several popular approaches: Transformer , Linformer , Performer , LSTM , GRU , TCN . We have also included

(Deformable): deformable convolutional networks that learn the adaptive receptive field using additional offsets ,

(CNN): conventional convolutional neural networks with dilation size 1,

All convolutional networks use the $n-1$ layers and 32 channels for a fair comparison.

The results are shown in Figure 5. Our model performs accurately for all sequence lengths, where CDIL-CNN achieves less than 1% error rate even when $N=2^{11}$ . Transformer and its variants, RNNs, and Deformable achieve comparable error rates for short sequences. However, they turn inaccurate ( $\sim 50\%$ accuracy) when the sequences become longer than $N=128$ . TCN and CNN perform even worse, where they respectively have 50% and 20% errors when $N=32$ . The results indicate that CDIL-CNN is more scalable than the other compared methods.

2 Long Range Arena Benchmark

Long Range Arena is a public benchmark suite for evaluating model quality in long-context scenarios . The suite consists of different data types, such as images and texts. Many Transformers have been evaluated on the suite . We compared our CDIL-CNN with other models on the following datasets:

Image. This is a 10-class image classification task. The images come from the gray-scale version of CIFAR-10 , where pixel intensities (0-255) are treated as categorical values. Two example images and their labels are shown in Figure 6. Every image is flattened to a sequence of length $N=1024$ . The task requires the model to learn the 2D spatial relations while using the 1D sequences.

Pathfinder. This is a synthetic image task motivated by cognitive psychology . The task requires the model to make a binary decision whether two highlighted points are connected by a dashed path. Two example images and their labels are shown in Figure 6. Similar to the Image task, every pathfinder image is flattened to a sequence of length $N=1024$ with an alphabet size of 256.

Text. This is a binary sentiment classification task of predicting whether an IMDb movie review is positive or negative . The task considers the character-level sequences which generate longer inputs and make the task more challenging. We use a fixed length $N=4000$ for every sequence, which is truncated or padded when necessary.

Retrieval. This is a character-level task with the ACL Anthology Network dataset . The task requires the model to process a pair of documents and determine whether they have a common citation. Like the Text task, every document is truncated or padded to the sequence length of $4000$ , making the total length $N=8000$ for the pair.

For a fair comparison, we followed the same data preprocessing and training/validation/testing splitting in . We quoted the results of Transformer and its variants from the literature and ran RNNs and CNNs for completeness. We used one layer with a hidden size of 128 for RNNs and 64 channels for CNNs. All experiments were run five times with different random seeds, where means and standard deviations are reported in Table 1. We have used paired $t$ -test at the significance level of 0.05 to verify whether CDIL-CNN is significantly different from RNNs or other CNNs.

Our model achieves the best mean accuracies in all tasks and is significantly better than RNNs and other CNNs in 17 out of 20 comparisons. The significant wins over all other methods hold for the Image and Pathfinder tasks. Espeicially for the Image task, CDIL-CNN achieves substantially higher mean accuracies (20.25% better than the best transformer variant, 20.09% better than the best RNN, 25.87% better than other CNNs). Deformable and CNN get comparable accuracies with CDIL-CNN for Text and Retrieval, probably because the two tasks mainly rely on local patterns.

3 Time Series

The UEA & UCR Repositoryhttp://www.timeseriesclassification.com/ consists of various time series classification datasets . Many time series classification problems can be solved by detecting local patterns . These tasks require the model to pick out important local information from long sequences which contain much noise. We compared our CDIL-CNN with other popular models on three audio datasets:

FruitFlies. The dataset comes from the same optical sensor which recorded the change in amplitude of an infra-red light as it was occluded by the wings of fruit flies during flight. The dataset contains 17259 training and 17259 testing sequences of length $N=5000$ . The task requires the model to classify a sequence as one of three species of the fruit fly.

RightWhaleCalls. Right whale calls are difficult to hear due to some low-frequency anthropogenic sounds. Up-calls are the most commonly documented right whale vocalization. The task requires the model to decide whether a sequence contains a set of right whale up-calls or not. The training and testing sizes of this dataset are 10934 and 1962, respectively. All sequences have a fixed length $N=4000$ .

MosquitoSound. The dataset represents the wing beat of the flying mosquito. Both training and testing sets have 139883 instances with sequence length $N=3750$ . The task requires the model to classify each sequence into one of six species.

We split every original training set into training (70%) and validation (30%) parts, and used the original testing set for testing.

We have compared our model with Transfomer, its two popular variants, RNNs, and CNNs. We also included dynamic convolutional neural networks (DCNNs) , because it combines CNN and dynamic time warping, a widely used component in many time series classifiers. We used 32 channels for every convolutional layer. The classification results are shown in Table 2.

Our model significantly wins all three tasks with mean accuracies of 97.09%, 91.99%, and 91.54%, respectively. Transformers and RNNs struggle in the time series classification tasks. We found that convolutional networks perform better, probably because local signals are more important in these tasks. However, other CNNs are still inferior to our model.

4 Ablation Study

Compared with conventional CNN, the proposed CDIL-CNN has two major contributed components: dilated convolution and circular mixing (padding). In this section we performed an ablation study to verify that both components are conducive to accurate and robust classifications. For this goal, we include a middle method called DIL that contains only the dilated convolution component but zero-padding. We then compare DIL with conventional CNN and CDIL-CNN.

For comparison, we first designed a more challenging XOR problem, where $N=2^{11}$ and the test data can have the same position distribution as the training/validation data (Similar Test) or a different distribution (Dissimilar Test). See Figure 7 for illustration. In training/validation datasets, the two marked values appear in the first half for Class 0 and in the second half for Class 1. The test data follows the same pattern in the Similar Test, while the halves flip in the Dissimilar Test. The data shift brings an extra challenge, where a non-robust model can wrongly classify the sequences by the absolute positions of the markers instead of the required XOR pattern from marked values.

The results are shown in Table 3. The CNN predictions are as bad as random guessing on both test sets, probably because it cannot capture the long-range interaction between the marked positions. DIL, equipped with dilated convolution, clearly improves the performance in Similar Test. However, DIL performs poorly on Dissimilar Test, which indicates that DIL overfits to training data and does not classify sequences by the required XOR pattern. CDIL-CNN differs from DIL by using circular padding instead of zero-padding. This change doesn’t affect prediction performance in Similar Test, while achieves nearly perfect predictions in Dissimilar Test. The winning of CDIL-CNN shows that both dilated convolution and circular padding are needed for robust classification.

We also created a noisy time series classification task using RightWhaleCalls, where the test data can have the same data shift as the training/validation data (Similar Test) or different shift (Dissimilar Test). We added the Gaussian noise of length 2000 at the end of every sequence in the training/validation set. The test set in Similar Test follows the same preprocessing, while in Dissimilar Test, the Gaussian noise part is inserted in front of each original test sequence. The mean and standard deviation of Gaussian noise equal those of the original sequence. Figure 8 shows examples of noisy RightWhaleCalls.

The results are reported in Table 4, which leads to similar conclusions in the XOR problem. CNN gives mediocre accuracies in both Similar Test and Dissimilar Test. Dilated convolution endows DIL better performance in Similar Test than CNN. However, zero-padding makes DIL sensitive to the data shift and degrades its performance close to random guessing in Dissimilar Test. Equipped with both dilated convolution and circular padding, CDIL-CNN can robustly and accurately classify (higher than 91% accuracy) the time series in both cases.

Next, we visualized an input sequence of the XOR problem and its output features of CNN, DIL, and CDIL-CNN in Figure 9. The visualization helps us understand the difference among the methods in terms of receptive field and boundary effect. In conventional CNN, the important information is present locally even in the last layer, which can lead to a wrong prediction if the two markers are distant. In contrast, the receptive field in DIL and CDIL-CNN is much wider because they use dilated convolution. It is known that zero-padding can cause boundary artifacts . As we can see, here DIL has such artifacts in the left-most part of its visualization. Consequently, DIL probably misses the left marked value and thus gives wrong classification. In comparison, CDIL-CNN with circular padding leads to more even output features across columns and does not suffer from boundary artifacts.

In summary, both dilated convolution and circular padding are useful for robust and accurate classification. With the two components, CDIL-CNN well mixes the signals from the input sequence to every output position. As a result, the subsequent averaging and linear classifier provide a good ensemble and do not lessen the contributions of the important information.

Conclusions

We have proposed a novel convolutional model named Circular Dilated Convolutional Neural Network (CDIL-CNN) for sequence classification. Based on the characteristic of very long sequential data, we have used a design that consists of multiple symmetric and circular convolutions with exponential dilation sizes. Therefore, our model can remove boundary effect and enlarge the receptive fields quickly. In this way, every position of the last convolutional layer has an equal chance to receive all information of the whole input sequence. Finally, a simple average ensemble learning is applied to improve the accuracy. Experimental results show that our model has superior performance over all other models on various long sequential datasets.

In the future, we could add other popular modules to our model, such as absolute positional encoding , relative positional encoding , and conditional positional encoding , which could further improve the performance. We could also pre-train our model for few-shot or zero-shot learning, where only a few supervised labels are required in training.

Acknowledgements

We acknowledge for using the IDUN computing cluster .

References

XOR Problem

In this group of experiments, we used the categorical cross-entropy loss function and the Adam optimizer with the learning rate of 0.001. We trained every model for 100 epochs using the batch size of 40. For RNNs, namely LSTM and GRU, we used 1 layer with a hidden size of 128. For Transformer, Linformer, and Performer, we used 32 dimensions, 4 layers, and 4 heads. In CNNs, we used the kernel size of 3 and 32 channels for every convolutional layer. We adopted the varying depth of CNNs so that the last position of TCN and each position of CDIL-CNN can cover the whole sequence, i.e., the depth $L=n-1$ for the sequence length $N=2^{n}$ . Other convolutional networks used the same layers for a fair comparison. Table 1 gives the model sizes.

Long Range Arena

For this group of experiments, we quoted Transformers’ results from reference papers and ran LSTM, GRU, TCN, CNN, Deformable, and CDIL-CNN for comparison. During training, we used the categorical cross-entropy loss function and the Adam optimizer with the learning rate of 0.001. For LSTM and GRU, we used 1 layer with a hidden size of 128. We used the kernel size of 3 and 64 channels for every convolutional layer. The depth was decided by the sequence length. All tasks had a vocabulary size of 256 and an embedding dimension of 64. Every model was trained for 100 epochs. More details of RNNs and CNNs are given in Table 2.