CNN Kernels Can Be the Best Shapelets

Thanks for your valuable comments. Below we have addressed your questions and concerns point-by-point, and we have updated and added more clarifications to our manuscript accordingly.

Weaknesses

The paper lacks a comprehensive review of related work, and the selection of competitor approaches for comparison is odd.

Parts of the experimental section are unclear and require further clarification. The XAI evaluation is restricted to examples selected by the authors.

We have addressed them in the Questions section.

There is no discussion or citation concerning code implementation.

The code implementation is included in the supplementary material.

Questions

Lack of Comprehensive Review of Related Work:

• The authors focus exclusively on optimization-based shapelet approaches. While space is limited, notable methods like Random Shapelet Forest and standard shapelet transform should not be omitted. Dictionary-based and interval-based approaches are also relevant and have achieved state-of-the-art performance in time series classification, yet they are not mentioned. Furthermore, the competitor models used in the experimental section are largely transformer-based or rely on embeddings, making for an unusual selection. I recommend that the authors thoroughly review relevant literature on time series classification, such as the paper by Ruiz et al. (2021) and models like ROCKET by Dempster et al. (2020).

Thank you for the suggestions.

First, one kind of baseline models we have included in the Experiment section are shapelet related methods, which includes not only optimization-based shapelet approaches, but also the selection and generative based methods. The standard shapelet transform is denoted IGSVM in the table (Table F.1) and CD plot (Figure 3) according to the name in its paper. Besides, standard shapelet transform and its variants have also been mentioned in our related work like that: Traditional practice is to search the raw datasets with some speed-up strategies, like paralleling computing (Chang et al., 2012), SAX transformation(Rakthanmanon & Keogh, 2013) and procedure simplification through newly designed measurements (Lines et al., 2012; Guillaume et al., 2022; Zakaria et al., 2012).

Second, other two kinds of baselines are common deep learning methods (MLP, CNN, RNN) and state-of-the-art methods (TS2Vec, TST, DTW, etc), which covers various types of neural networks.

Third, we have added ROCKET as a baseline in the UCR dataset comparison upon your request. However, we also want to mention that ROCKET is already compared with some of our baselines, like TST and OS-CNN, in their papers. Since we are comparing with the state-of-the-art methods in recent two years, and many previous methods like HIVE-COTE and BOSS are already compared in our baselines' papers, we believe that superior performance over these state-of-the-art methods can well demonstrate the effectiveness of our model.

Finally, we have also updated our related work section by introducing non-deep-learning approaches like the dictionary-based method MUSE and the ensemble method HIVE-COTE.

Is the "Initialization" phase's cost included in the runtime?

Yes, it is included. We have clarified this in Table 1.

In Table 1, why do the methods differ with respect to the cd plots?

Why is the evaluation limited to 25 UCR datasets, and what was the criteria for selection?

In the CD plot (Figure 3), ShapeConv is compared with shapelet-based methods on 25 UCR datasets, and full results here are shown in Table F.1 in Appendix. In Table 1, ShapeConv is compared with state-of-the-art time-series classification models on 125 UCR and 29 UEA datasets, and the full results are shown in Table F.3 and F.4. Methods are different since they are two different experiments.

We use the subsets (25 UCR datasets) in the CD plot because the baseline (ADSN) only reported results on 25 UCR dataset, and the results of baselines are taken directly from the respective papers. Full results of ShapeConv and state-of-the-art classification methods on all 128 UCR datasets are shown in Table F.3 in Appendix.

Thanks for your valuable comments. Below we have addressed your questions and concerns point-by-point, and we have updated and added more clarifications to our manuscript accordingly.

Weaknesses

In the abstract (it is also said in the introduction in other words), it is stated that:

In this paper, we demonstrate that shapelets are essentially equivalent to a specific type of CNN kernel with a squared norm and pooling

In fact, this demonstration is not novel, it is for example stated in (Lods et al. 2017) (that is cited in the paper). However, it seems that here, the proof aims at more rigor, but Theorem 3.1 is not successful in this regard since it completely disregards the fact that the bias term in convolution is independent of the input, which is not the case in the $-\mathcal{N}(\mathbf{s_i}, \mathbf{X}_{j:j+l_s-1})$ term.

We would like to emphasize that the bias term in convolution has no relation with the $-\mathcal{N}(\mathbf{s\_i}, \mathbf{X}\_{j:j+l\_s-1})$ term. The bias term, as we have explained in the end of Sec. 3.1, can be optionally added after the features are extrated with the shapelets (or CNN kernels). And the $-\mathcal{N}(\mathbf{s_i}, \mathbf{X}_{j:j+l_s-1})$ term is an additional squared L2 norm term added in ShapeConv besides the cross-correlation operator in CNN. The equivalence cannot be realized without this additional squared L2 norm. Therefore, the bias term do not influence the proof of equivalence, so that Theorem 3.1 is successful in the rigor equivalence between CNNs and shapelets.

Also, as a side note, in Theorem 3.1, Squared Euclidean distance is used, not Euclidean distance as stated.

Thanks for pointing out. We have revised our manuscript.

Moreover, the review of the Related Work is very succinct and a more thorough presentation of competing interpretable Shapelet-based methods would have been a plus. Similarly, a more detailed comparison of the interpretability of the ShapeConv model with those baselines is required to fully assess interpretability:

• Only toy examples are presented (eg. Fig 4: 2 shapelets), what does it give when training with a large amount of shapelets?
• Also, providing visualization for a large number of datasets instead of only GunPoint+Herring+ECG200 would be a real plus

For the visualizations, we did not choose "toy examples" - the ShapeConv in Fig 4 could achieve 0.75 accuracy on the Herring dataset with 2 shapelets. When the number of shapelets are large, the model tends to overfit for these simple datasets. As for examples with large number of shapelets, we provided a real-world application of ShapeConv in EEG (Appendix D) where 2,688 shapelets are trained. Two of them are visualized in Figure D.1, and they matched nicely with the EEG examples from textbook.

We also provided more visualizations in the appendix E, showing learnt shapelets in 4 additional datasets from UCR: DodgerLoopWeekend, SonyAIBORobotSurface1, ItalyPowerDemand, BME. ShapeConv captures the determinative regions in all of them.

In terms of interpretability, ShapeConv is generally shapelet-based method, so its interpretability inherits from shapelet. We have compared the interpretation results of ShapeConv with the other shapelet-based method (i.e., LTS) via visualizations, and results shows that ShapeConv is better at capturing discriminative sub-sequences, thus having better interpretability.

Questions

If you took your your ShapeConv model (with exact same initialization, regularization terms, etc.) and changed the ShapeConv layer with a convolutional one, what would you get in terms of performance? This experiment is required to fully assess if the norm terms a really helpful

We anticipate your proposed ablation is to drop the squared $L_2$ norm term $\mathcal{N}(\mathbf{s_i}, \mathbf{X'})$ from Equation (4) in the loss. However, then the shape regularizer in the loss would become

where $Y(\mathbf{s_i},\mathbf{x})$ denotes the cross-correlation between kernel $\mathbf{s_i}$ and subsequence $\mathbf{x}$. Minimizing this regularizer would make the loss diverge and goes to negative infinity. This is because without the norm terms, the regularizer could not be interpreted as a distance and is not always nonnegative.

If we do not use the shape regularizer, the formulation would become similar with the CNN baseline. We tested the ShapeConv without Shape Loss (by setting the $\lambda_{shape}$ in Equation (8) to zero). The results for the GunPoint dataset is illustrated in appendix E.2. We found that its kernel is not interpretable and it performs worse than ShapeConv (it constantly overfits the training set). The result performance is similar with the CNN baseline. We did not include the full results in the paper due to space constraints.

Thanks for your valuable comments. Below we have addressed your questions and concerns point-by-point, and we have updated and added more clarifications to our manuscript accordingly.

Weaknesses

However, I have no confidence in any of the claims of interpretability and explainability. You made no effort to obtain ... go beyond downloading the UCR datasets. But if that is all you do, it seems like you should temper your claims about interpretability and explainability.

Thank you for the suggestions. We tried to access the original data of the GunPoint and Herring dataset, but it is not available. Nevertheless, to further support our claims about interpretability, we have added a real-world example usage of ShapeConv in EEG when stacked with deep models. Breifly speaking, we have excitedly discovered that a few shapelets are highly similar to waveforms in clinical textbooks. By aligning shapelets with data and conduct shapelet transform, we see clear separatable clusters. The overall experiments in Appendix D demonstrate the possibility of ShapeConv, when stacking with deep models, can benefit medical practitioners in practice by not only offering an accurate judgement, but also pointing out the area of interests with respect to their expert knowledge. Please kindly refer to the revised version of our manuscript, Appendix D, for figures and more details.

“In the realm of machine learning, interpretable time-series modeling stands as a pivotal endeavor, striving to encode sequences and forecast in a manner that resonates with human comprehension” This (and the rest of the paper) read like flowery language [a].

Thanks for the suggestion. We will go through the paper and try to make the sstatements simplified and less confusing in the final version.

In fig 1, can you move the legend away from the data?

Thank you for pointing out. We have moved the legend away from the data.

“is evaluated on the 25 UCR” Did you mean “125” or “25”?

Here the 25 UCR dataset is the subset of the 128 UCR dataset. We use this subset because the baseline method (ADSN) only reported this subset. We have clarified this in the paper.

“Figure 5: Shaplets learned” typo (Shapelets)

Thank you for pointing out. We have fixed the typo.

“It is evident that the shapelet learned by ShapeConv captures the distinguishing features of the class effectively” Evident to whom? You should argue that the blue shapelets correctly represents the actors hand having to hover over the gun holster, then reach down to the gun, then draw the gun.

Thank you for the suggestions. We have added more details in the paper.

“clustering task using 36 UCR univariate” Why 36? Why this particular 36?

We use the 36 UCR dataset because the baseline method (AutoShape) only reported this subset. We have clarified this in the paper.

“In response to the first RQ, we observe that ShapeConv’s shapelets (Figure 4 (a)) cover all turning points in the time series, where the two classes differ the most, while LTS’s shapelets (Figure 4 (b)) do not cover the targeted regions.” This evaluation is tautological. If “turning points” are the best places for shapelets, then we don’t need any search for shapelets at all.

In this example, the turning points are the best places for shapelets. However, we agree that this is not always the case. We have clarified this in the paper.

“In contrast, when using human initialization,..” Hmm, it is a bit tricky to claim results based on human initialization. Which humans, how trained are they in the system, how are they briefed. In my mind, that is a separate “human in the loop” paper.

We agree that this is tricky to claim. Our goal is to show that ShapeConv has the ability to use human knowledge as prior, which is not possible in other shapelet-based models.

However, despite ingenious, the performance (missing a word?) However, despite ingenious suggestions, the performance

gun out of the gun pocket (holster)

“while data from the “finger” class don’t.” “while data from the “finger” class do not.” (avoid contractions in scientific writing)

This illustrate how This illustrates how

Thank you for carefully reading the paper and pointing out these typos. We have fixed the typos.

In table E.5, why four significant digits? This is spurious accuracy.

We use four significant digits because the results are taken directly from the respective papers. We have revised this in the paper to make it consistent.

In table E.5 and elsewhere, you report the average accuracy. This is meaningless for datasets of different sizes, class skews, number of classes, default rates etc. To be clear, it is not a flawed metric, it is just meaningless.

We agree that the average accuracy is meaningless for different datasets. However, the community has been using this metric for a long time. We have to report this metric to compare with the previous methods.

Thanks for your valuable comments. Below we have addressed your questions and concerns point-by-point, and we have updated and added more clarifications to our manuscript accordingly.

Weaknesses

An analysis of the computational complexity and resource requirements of ShapeConv could make the paper more comprehensive.

The ShapeConv has the same computational complexity and resource requirements as the 1D convolution. The only difference is that ShapeConv has an additional regularization term and additional losses. These terms are negligible compared to the convolution operation. The total computational complexity of ShapeConv for a univariate time series is $O(l_x \times l_s \times n_{out})$, where $l_x$ is the length of the input time series; $l_s$ is the length of the shapelet, and $n_{out}$ is the number of shapelets. The advantage of ShapeConv is that is could be paralleled in GPU, making is much faster than traditional methods on CPU (2000x faster than LTS).

Though the model's performance is promising, concerns may arise regarding the complexity of implementing ShapeConv compared to other traditional or deep learning models.

ShapeConv is implemented as a Module in PyTorch similar to a common CNN layer, which can be easily integrated as a layer in any deep learning model. The implementation of ShapeConv is available at the supplementary material. Besides, the implementation of ShapeConv itself is simple and intuitive, which contains the convolution layer and some additional regularizers, aligning with Eq. (4) in Theorem 3.1.

Questions

This study opted for a combination of CNN and Shapelets to enhance interpretability while also boosting performance. For time series classification tasks, why not choose the stronger baseline models for research, such as RNN or Transformer?

RNN and Transformer-based methods are already included in our baselines. Table F.2 shows results of ShapeConv and various RNN-based methods, and we also compared with Transformer-based model, TST [1], in Table 1 and appendix Table F.3. ShapeConv outperforms these methods on most of the tasks. These methods are not listed in the main paper since we only include most related and competitive methods due to the limited spaces.

[1] George Z., et al. A transformer-based framework for multivariate time series representation learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2114–2124, 2021.

Thanks for your valuable comments. Below we have addressed your questions and concerns point-by-point, and we have updated and added more clarifications to our manuscript accordingly.

Weaknesses

The main contribution is based on Theorem 3.1, ... is equivalent to a convolution.

We argue that our work is definitely different from the work in [1] despite some faint connections. The authors of [1] discuss the connection between z-normalized Euclidean distance and dot products so as to utilize convolution techniques such as the fast Fourier transform (FFT) to achieve speed-ups in searching similar subsequences. The method are mentioned to "suggest" candidate shapelets as indicators, and barely limited to sub-sequences of the original time series which cannot meet the needs of deep learning. We, to be noticed, rigorously prove the equivalence between a certain neural convolutional layer (not just convolution) and the originally defined shapelet in order to propose a newly interpretable and learnable neural kernel for deep learning.

In fact, we have properly cited the papers of [2] and [3] (also discuss the relationship between convolution and shapelet) which are more relevant and compared them with our work to highlight our contribution of demonstrating the strict equivalence between shapelet transform and a certain learnable neural operator. With GPUs’ built-in parallel computation of for deep learning, our ShapeConv is naturally high-speed and does not need extra algorithms specifically designed for acceleration. Besides, we also put forward the diversity regularization and incorporate human-knowledge-based initialization to enhance the interpretability of our proposed method as non-negligible contributions.

[1] Yeh, C. C. M., et al. (2016). Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View that Includes Motifs, Discords and Shapelets. Proceedings of the IEEE International Conference on Data Mining (ICDM), 1317–1322.

[2] Arnaud L., et al. Learning dtw-preserving shapelets. In Advances in Intelligent Data Analysis XVI: 16th International Symposium, IDA 2017, London, UK, October 26–28, 2017, Proceedings 16, pp. 198–209. Springer, 2017.

[3] Yichang W., et al. Learning interpretable shapelets for time series classification through adversarial regularization. arXiv preprint arXiv:1906.00917, 2019.

An extensive review ... the best-performing algorithms of the state-of-the-art.

Since our proposed ShapeConv is a deep-learning based new method and some of our baseline have outperformed the state-of-the-art algorithms in [8,9] (e.g. OS-CNN[4] outranking HIVE-COTE[5], WEASEL+MUSE[6] and InceptionTime[7] on both univaraite and multivariate datasets), we only conduct most relevant comparison with shapelet-based and deep-learning based approaches to avoid redundancy. Besides, we add comparison with ROCKET[10] in our revised version.

[4] Wensi T., et al. Omni-scale cnns: a simple and effective kernel size configuration for time series classification. In International Conference on Learning Representations, 2021b.

[5] Jason L., et al. Hive-cote: The hierarchical vote collective of transformation-based ensembles for time series classification. In 2016 IEEE 16th international conference on data mining (ICDM), pp. 1041–1046. IEEE, 2016.

[6] Patrick S., Ulf L.. Multivariate time series classification with weasel+ muse. arXiv preprint arXiv:1711.11343, 2017.

[7] Hassan I. F., et. al. InceptionTime: Finding AlexNet for Time Series Classification. arXiv preprints, arXiv:1909.04939, 2019.

[8] Bagnall, A., et. al. (2017). The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Mining and Knowledge Discovery, 31(3).

[9] Middlehurst, M., et al. (2023). Bake off redux: a review and experimental evaluation of recent time series classification algorithms. arXiv: 2304.13029

[10] Angus Dempster, et. al. Rocket: Exceptionally fast and accurate time series classification using random convolutional kernels. Data Mining and Knowledge Discovery, pp. 1–42, 2020.

(Minor comment.) It is considered bad practice to start sentences with mathematical symbols.

Thanks for pointing out. We have revised the paper accordingly.

Revision: We add the visualization of actual hand movement in Appendix A.2 to verify our interpretations of the GunPoint dataset by shapelets.

We are learning from all the feedbacks from the reviewers. Reading your insightful praises and critism, we feel that this is a great opportunity to exchange ideas deeply. Therefore, we're making the following statements to ignite more discussion with the reviewers since we value more on the advances of the whole interpretable machine learning area, a more comprehensive understanding of what we are doing, than the acceptance of this specific paper, while we hope these discussions will not interfere the decision of this paper much.

Ultimately, I remain on the fence for this paper. It is nicely written, and the idea of combining the CNN kernels with shapelets is nice. But I was never really convinced by any claims of interpretability.

Again, we thank the reviewer's recognition of our paper. At the meantime, we're curious about the answer to the question, "What is interpretability? How can a method be treated as a really interpretable and helpful solution that does push the area moving forward", from all the readers seeing it. Or more specifically here, "how we can convince people that our method is really interpretable".

The answer may vary from person to person and these are some existing discussions [1,2], and here is the answer we'd like to convey through this paper. We believe that, a truly useful interpretation of a black-box model should be sensible, comprehensible, and verifiable by human. As for time-series classification, such element is the shape of the sequence. As long as a person sees a cliff, a spike, or irregular changes from the plot, he would immediately know "something different is happening". That's why we choose the shapelet as our start point.

Now let me reiterate the motivation of ShapeConv. We found that it's very hard to find the balance between comprehensibility (interpretability) and verifiability (effectiveness). Early shapelet works are easy to comprehend because they come directly from the original data, but can hardly beat contemporary deep models. On the other hand, the learning-based methods can achieve astonishing results, but the shapelets look like random sequences and can hardly provide true insights for human.

We abscribe the gap to the missing of a rigorous eqivalence between shapelets and deep learning. While we found the subtle relationship between convolution and shapelet are about to uncover the mystery, we feel that there is something missing as the finishing touches to make it truly useful. Then comes our ShapeConv - the proof to build the equivalence and several mechanism for applying it to reality.

Here is how we design the experiments to describe why it can be called an interpretable method based on our understanding of interpretability. 1) We visualized many shapelets to make it sensible; 2) We explains our shapelet-based findings in real-world datasets and check the human understanding for the question to confirm that it is comprehensible; 3) We run tests on a bunch of datasets to prove that it is verifiable.

The above statements are only based on our understanding of interpretable time-series classification, which may be controversial from concepts to details. Therefore, we did not include such statements in any part of our paper directly. We list them here because we're eager to learn from your perspective, and we hold the belief that our paper and such discussions will definitely advance the field.

[1] Doshi-Velez F, Kim B. Towards a rigorous science of interpretable machine learning[J]. arXiv preprint arXiv:1702.08608, 2017.

[2] Murdoch W J, Singh C, Kumbier K, et al. Definitions, methods, and applications in interpretable machine learning[J]. Proceedings of the National Academy of Sciences, 2019, 116(44): 22071-22080.