dataesr/scientific-paragraphs-categorization huggingface dataset:
This algorithm designs shapelet-based classification as a three step process. The first step is the selection of the top 𝑘 shapelets, this is equivalent to learning a bag of shapelets to represent the time series. The second step is the shapelet transformation where each time series in the dataset is replaced by a vector of its distances to each of the selected shapelets. The final step consists of training a supervised classifier on the transformed dataset. Although the time complexity of this algorithm is still 𝑛 2 𝑚 4 , it is the shapelet based algorithm that obtains the best classification accuracy on the UEA & UCR archive  [6]. Although shapelets are defined as subsequences selected from the considered time series, other approaches proposed to learn shapelets through an optimization process.
The first of these approaches is Learning Shapelet or LS  [17]  which starts with randomly initialized shapelets and uses logistic regression to adjust them iteratively with the goal of maximizing the classification accuracy. This allows the learning of shapelets that are not present in the training time series. However, the shapes of the learned shapelets are unpredictable and can be difficult to interpret. The time required by this method to be accurate depends on the initialization step and the optimization algorithm used. Unlike LS which initializes shapelets randomly, ELIS++  [16] , an improvement of ELIS  [34]  initializes shapelets by the subsequences contained in the training time series. Then Bayesian optimization is used to set the hyperparameters automatically. Furthermore, ELIS++ uses data augmentation in order to converge on small datasets.
The time complexity of HIVE-COTE is bounded by the complexity of its shapelet component, that is 𝑛 2 𝑚 4. Therefore decreasing the computation time of the shapelet component will make HIVE-COTE more efficient in terms of running time. TS-CHIEF is a forest of trees in which a time series follows a branch if it is closer to the reference time series (there is one reference time series for each class) associated with that branch than to the reference time series of other branches. TS-CHIEF does not use shapelet features because of the time complexity needed for their computation. ROCKET is the most scalable state of the art method, it is based on random convolutional kernels that are used to transform the dataset. ROCKET results are not easily interpretable because the kernels used are short, independent and not sampled from the dataset.
SAST, our proposal described in the next section is architecturally similar to ROCKET, however, the way both models work is different in two folds: firstly, the subsequences used in SAST (similar to convolutional kernels in ROCKET) are those of some reference time series randomly chosen from the dataset, and hence they are dependent and have variable lengths. Secondly, SAST does not use the convolution operator as similarity measure, but the Euclidean distance. These properties of SAST are the reasons of its scalability and interpretability. SAST is a scalable and accurate alternative to STC. It can be used to reduce the computation time of the shapelet module in HIVE-COTE, and can be integrated to TS-CHIEF at the cost of little computation time overhead. Adding shapelet features in TS-CHIEF would increase its classification performance.
SAST: Scalable and Accurate Subsequence Transform In TSC, a shapelet is ideally a pattern that is shared by every instance of the same class, and that instances of other classes do not have, they are called discriminative patterns or subsequences. The number of patterns in a dataset of 𝑛 time series of length 𝑚 is 𝑂(𝑛𝑚 2 ), and state of the art shapelet algorithms evaluate each of them by computing their information gain for a set of similarity thresholds before keeping the patterns and their corresponding similarity thresholds that give the highest information gain. Reducing the number of patterns to be assessed will make shapelet models faster to train. In this section we propose a way to reduce the number of shapelet candidates. Then we show that there is no need to select the top best shapelets beforehand.
Hence, instead of generating shapelet candidates from the whole dataset, we propose to use only one or a few number of instances per class. In fact, the members of a class should contain common patterns or at least different variants of the same pattern. In this way, the learning algorithm must focus on one (or a few number) variant of each shapelet candidate to learn how to classify a time series. We acknowledge that the more variants the model learns from, the more accurate the model would be. However, this can also cause the  model to overfit, especially when the training data is not representative of the testing data. There are known situations where the core shapelet recognition task cannot be solved: (1) The most obvious one is when no shapelet is present in the dataset, meaning that any shapelet approach would fail.
(2) The second one is when the shapelets representing a class are not all present in each individual time series of the class, but are distributed over several instances. In Fig. 3 , we have three randomly selected instances of the Chinatown dataset (containing two classes) from the UEA & UCR archive  [35]. The left example is from class 1 and the second example (in the middle) is from class 2. It is easy to observe that the instance from class 1 starts by a deep valley, while the instance of class 2 does not. One reason that can be considered in order to classify the instance on the right in class 2 is that it does not start by a valley. Hence, we claim that observing only one instance per class could be enough to discover discriminative patterns and successfully perform classification of new instances.
Fig. 3  is of course not enough to support our claim. However, the extensive experiment described in Section 4 and the obtained results give clear evidence supporting our claim. Based on this observation, we propose the following statement: Proof. Let us assume that classes in 𝐷 are distinguishable using shapelets and that there is a shapelet 𝑠ℎ𝑝 for the dataset 𝐷 that is not similar to any time series in the set 𝐷 𝑐. Since 𝐷 𝑐 contains at least a time series of each class in 𝐷, any shapelet for the dataset 𝐷 must be similar to at least one time series in 𝐷 𝑐. It follows from there that assuming 𝑠ℎ𝑝 to be a shapelet is wrong. Therefore the statement is true. □ Let us explain the expression ''distinguishable using shapelet'', we use it to characterize datasets on which shapelet-based methods are known to be accurate.
According to Bagnall et al. [6] , these datasets include electric device, ECG, sensor and simulated time series datasets. To the best of our knowledge, there is no way to know if a shapelet-based method would be suitable or not on a dataset without applying the method. This emphasizes the importance of improving the scalability of shapelet-based algorithms. From the previous proposition, any shapelet 𝑠ℎ𝑝 of 𝐷 is always similar to a pattern in 𝐷 𝑐. Therefore, a shapelet algorithm that generated shapelet candidates from 𝐷 𝑐 can achieve the same accuracy as if 𝐷 was used. We run the shapelet transform algorithm (STC)  [9]  on the Chinatown dataset and plotted the top-5 shapelets that have been selected for each class in Fig. 5. The shapelets on the first row clearly identify the valley at the beginning of time series in class 1.
Although they are coming from different time series, they are very similar in shape. Likewise, the shapelets on the last row identify the flat starting of instances in class 2. Generating shapelet candidates from the whole dataset makes STC learns different variants of the same patterns. The variations are in terms of starting position, length and shape. By applying Proposition 1 in the STC algorithm, we introduce STCk, a variation of the STC algorithm that uses at most 𝑘 time series from each class to generate the shapelet candidates. Hence, for a dataset with 𝑐 classes, the number of shapelet candidates to be evaluated in STC-k is 𝑂(𝑐𝑘𝑚 2 ) unlike STC in which 𝑂(𝑛𝑚 2 ) need to be evaluated. Algorithm 1 is an outline of the STC-k algorithm. The only difference with STC is that the size of the shapelet space can be controlled by the parameter 𝑘.
For a more detailed description of the algorithm, the reader should refer to the original paper of STC  [9]. By default, the 𝑙𝑒𝑛𝑔𝑡ℎ_𝑙𝑖𝑠𝑡 parameter is the set {3, 4, … , 𝑚}, where 𝑚 is the length of the time series in the dataset. 𝑚𝑖𝑛_𝑖𝑔 is set to 0. 05. In practice, two other parameters are used in STC: the maximum number of shapelets to keep per class and the time contract. The number of shapelets to keep per class is by default set to 200. The time contract is the maximum time allocated to the algorithm to search shapelets on the given dataset. Middlehurst et al. [12]  stated that in one hour of searching per dataset, the result is not significantly worse than the full search. Following the implementation of STC in the sktime library  [37] , our implementation of Algorithm 1 handles the time contract and the maximum number of shapelets to keep per class.
We use the Chinatown dataset from the UCR archive  [35]  as a toy dataset to assess STC-1 (that is STC-k with 𝑘 = 1). STC-1 took about 10 seconds to classify the Chinatown dataset with an accuracy of 96% (average over five runs), while the original STC algorithm took 51 seconds and gave an accuracy of 97% on the same computer. Therefore, the STC-1 algorithm is about 5 times faster and achieves almost the same accuracy as the original algorithm. The extracted shapelets are shown in Fig. 6. Different variants of the same shapelet are not learned anymore. For this dataset, exactly one shapelet has been selected for each class. As we will show in Section 4, STC-k is significantly less accurate that STC, even when 𝑘 is equal to 75% of the number of time series in each class.
Identify shapelets using feature importance analysis When TSC using shapelets was introduced, shapelets were learned while building a decision tree  [5]. Later, shapelet transform (STC)  [9]  has been proposed to allow the use of any supervised classifier. The algorithm proceeds by finding the top best shapelets, then transforms the dataset using the found shapelets and finally trains a classifier on the transformed dataset  [9, 33, 38]. Therefore, there are three main steps: feature extraction where best shapelets are selected, dataset transformation where each time series is replaced by a vector of its We propose to remove the feature extraction step and use every shapelet candidate to transform the dataset. After training the classifier on the transformed dataset, a post hoc method for model explanation can be used to find the most important features.
More methods can be found in the review of  [44]. Hence, selecting shapelets beforehand of classification using information gain can be skipped, since the classifier can automatically learn the top best shapelets during its training iterations and feature analysis can be used after training to get the learned shapelets. Proposition 2. Let 𝐷 = {(𝑇 1 , 𝑐 1 ), (𝑇 2 , 𝑐 2 ), … , (𝑇 𝑛 , 𝑐 𝑛 )} be a dataset of time series, and 𝑆 the set of all subsequences in 𝐷. Let 𝐷 𝑓 = {(𝑥 1 , 𝑐 1 ), (𝑥 2 , 𝑐 2 ), … , (𝑥 𝑛 , 𝑐 𝑛 )} be a dataset such that 𝑥 𝑖 = [𝑥 𝑖∶1 , 𝑥 𝑖∶2 , … , 𝑥 𝑖∶|𝑆| ], where 𝑥 𝑖∶𝑗 = 𝑑𝑖𝑠𝑡(𝑇 𝑖 , 𝑆 𝑗 ). If the 𝑗th feature is an important feature given by the analysis of feature importance for the dataset 𝐷 𝑓 , then 𝑆 𝑗 is a shapelet for the dataset 𝐷. Proof. Let us suppose the 𝑗th feature is an important feature, and that 𝑆 𝑗 is not a shapelet for the dataset.
Time series classification with SAST TSC with SAST (Scalable and Accurate Subsequence Transform) is designed with respect to Propositions 1 and 2. A visual view of the method is shown in Fig. 7. There are two main blocks: • The classification block: this block is actually the SAST algorithm and begins with the random selection of reference time series from which subsequences are then generated. Thereafter, the dataset is transformed by replacing each time series with a vector of its distances to each subsequence. Finally a supervised classifier (illustrated here by a decision tree) is trained on the transformed dataset. • The interpretability block: The role of this block is to explain the SAST algorithm by identifying shapelet candidates associated with the most important features learned by the classifier.
For inherently interpretable classifiers such as decision trees, the importance of each feature is computed while fitting the classifier. For other classifiers, eventually not inherently interpretable, an existing post hoc explainer such as LIME  [42]  can be used to find the importance of each feature. A pseudo code of the SAST algorithm is given by Algorithm 2. SAST takes as input the time series dataset 𝐷, the number 𝑘 of instances to randomly select from each class in order to create the shapelet candidates, the list of lengths to use to generate shapelet candidates, and finally the supervised classifier 𝐶 that is going to be trained on the transformed dataset. SAST starts by randomly sampling 𝑘 instances per class from the dataset (line 2). By default, 𝑘 is set to one. We call the selected instances reference time series.
The next step is the generation of all subsequences of length in 𝑙𝑒𝑛𝑔𝑡ℎ_𝑙𝑖𝑠𝑡 from the reference time series (line 3). The dataset transformation is performed from line 4 to 11. Here, the similarity between each time series in the dataset and each shapelet candidate is computed. The classifier taken as input is then trained on the transformed dataset (line 12). The algorithm returns the trained classifier and the shapelet candidates that have been generated. After the training is done, the class labels of a test dataset can be predicted in two steps: firstly the dataset is transformed using the shapelet candidates that have been generated during training, and finally the trained classifier is used to predict the class labels of the transformed test dataset. Since the number of time series in the dataset and the number of subsequences in a time series are limited, Algorithm 2 always terminates.
SAST time complexity Each step of the SAST algorithm runs in a finite amount of time, therefore the algorithm always terminates. Selecting 𝑘 reference time series is done in 𝑂(𝑐) time complexity, 𝑐 is the number of classes in the dataset. There are 𝑚 -𝑙 + 1 subsequences of length 𝑙 in a time series of length 𝑚. The total number of subsequences for a time series is 𝑚(𝑚+1).
2. Since there are 𝑘𝑐 reference time series in a dataset with 𝑐 classes, generating all shapelet candidates is done in 𝑂(𝑘𝑐𝑚 2 ). The transformation step requires 𝑂(𝑛𝑚 2 ) distance computations, each of which requires 𝑂(𝑙) (𝑙 is the length of the subsequence) point wise operations. As the maximum subsequence length is 𝑚, the time complexity of the transformation step is 𝑂(𝑛𝑚 3 ). Therefore, the total time complexity of SAST is 𝑂(𝑐) + 𝑂(𝑘𝑐𝑚 2 ) + 𝑂(𝑛𝑚 3 ) + 𝑂(𝑐𝑙𝑎𝑠𝑠𝑖𝑓 𝑖𝑒𝑟), where 𝑂(𝑐𝑙𝑎𝑠𝑠𝑖𝑓 𝑖𝑒𝑟) is the time complexity of the classifier used. The overall asymptotic time complexity of the SAST algorithm is therefore 𝑂(𝑛𝑚 3 ) + 𝑂(𝑐𝑙𝑎𝑠𝑠𝑖𝑓 𝑖𝑒𝑟). SAST is much faster than the state of the art shapelet transform algorithm (STC)  [9]  whose time complexity is 𝑂(𝑛 2 𝑚 4 ) + 𝑂(𝑐𝑙𝑎𝑠𝑠𝑖𝑓 𝑖𝑒𝑟).
Ensemble of SAST models SAST accuracy is highly dependent on the randomly selected reference series. If a reference time series is noisy or not representative of its class, then it could be difficult for SAST to learn the best shapelets for the dataset. Furthermore, the random selection of reference time series could lead to a variance in performance. We use Bagging  [45]  to leverage these possible issues and we call the obtained model SASTEnsemble (or SASTEN in reduced form). SASTEN is obtained by ensembling 𝑟 SAST models. Each individual model in the ensemble uses randomly selected reference time series and may also have different parameters, especially the parameters controlling the length of shapelet candidates (that is 𝑙𝑒𝑛𝑔𝑡ℎ_𝑙𝑖𝑠𝑡 in Algorithm 2). The final prediction is obtained by averaging the predictions of every SAST model in the ensemble.
Experiments We have implemented STC-k, SAST and SASTEN in Python. Our implementation is based on the scikit-learn machine learning library  [46]. We have also followed scikit-learn design principles so that our models are compatible with any scikit-learn pipeline. We have used the implementation of STC (Shapelet Transform Classifier) from the sktime library  [37]. The source code of our experiments and all the results we discuss in this paper are publicly available here. 1  In all our experiments, the number of reference time series per class (that is the parameter 𝑘 in Algorithm 2) is always set to one. The supervised classifier used in STC-k, STC and SAST is the Ridge classifier with Leave-One-Out (LOO) cross validation. This classifier is available in the scikit-learn library. The LOO cross validation is used to find the best regularization parameter among 10 log spaced values ranging from -3 to 3 (these values are inspired by Dempster et al.
[26] ). The other parameters are left to their default values and are not fine tuned. 1 https://github. com/frankl1/sast We have also used the Random Forest classifier in SAST. For this classifier all features are evaluated at each node to find the best split and a split is selected if the impurity decreases by about 0. 05, the minimal information gain for a shapelet like in STC. Although it is generally better to evaluate only a subset of the feature space in Random Forest in order to reduce the correlation between the trees, we have not followed this guideline in our work because we want the model to always select the best possible split (that is the best shapelet). However, each tree in the ensemble is trained on a random subset of the training set. This classifier is also available in the scikit-learn library.
We make use of the Wilcoxon significance test with a 𝑝-value of 0. 05 to compare our models. We give the result of this test as a critical difference diagram on which models that are not significantly different from each other are linked with a bold line. The code used for this test and to draw critical difference diagrams is from Fawaz et al. [27]. Table  1  describes the models that we use in our experiments. We experiment using 72 randomly selected datasets from the UEA & UCR repository  [35]. The datasets in the repository are different in terms of series length, number of series, number of classes and application domain. For each dataset, the repository provides a training set and a test set. Since searching shapelets for one hour is not significantly worse than the full search on the UEA & UCR archive  [12] , we used a time contract of one hour for each STC-k models as well as for STC.
STC-k results We have evaluated STC-k on 72 datasets with different value of the parameters 𝑘. We have considered STC-1, STC-0. 5, STC-0. 75 and STC. These models are described in Table  1. Fig. 8  shows pairwise comparisons of these model accuracies on the test set of each dataset. STC is better than any STC-k on almost every dataset. This is because an STC-k model does not search the whole shapelet space, and therefore the shapelets obtained using the minimum information gain are not good enough to classify the dataset. The critical difference diagram in Fig. 9  shows that STC-0. 75 is not significantly more accurate than STC-0. 5, which is significantly more accurate than STC-0. 25, which is in turn significantly more accurate than STC-1. Therefore, STC-k accuracy increases with the value of the parameter 𝑘.
SAST model results Before comparing SAST to STC, let us see how SAST and ensemble of SAST are compared to each other in terms of accuracy. Fig. 11  shows a pairwise comparison of the SAST based models described in Table  1  on the 39 datasets marked with a star in Table  4. The first thing to note is that SAST-Ridge is generally more accurate than SAST-RF on our datasets (Fig. 11(a) ). There are many parameters in RF that can be optimized in order to improve SAST-RF, but we did not perform parameter tuning in this work and we consider SAST-Ridge as the best model for our experiment. This is why we use SAST-Ridge as the  We tried several length_list for the approximated SAST model, and we are presenting here only the four that achieved the best accuracy on our datasets. The critical difference diagram between these four models is given in Fig.
10. There is no significant difference between the models, however, the model using 𝑙𝑒𝑛𝑔𝑡ℎ_𝑙𝑖𝑠𝑡 = {7, 11, 15} is the best of all. When not clearly precised in the rest of this paper, SAST-Ridge-A is the approximated SAST-Ridge model with 𝑙𝑒𝑛𝑔𝑡ℎ_𝑙𝑖𝑠𝑡 = {7, 11, 15}. The approximated SAST-Ridge is less accurate than SAST-Ridge in general (Fig. 11(b) ). However it is important to note that the approximated model wins on 9 datasets among 30. Therefore, knowing a prior about possible shapelet lengths can be used to train the model faster and without losing accuracy. Furthermore, ensembling approximated SAST models, each one focusing on different shapelet lengths is a possible way to improve accuracy while decreasing the computation time. In fact, SASTEN-Ridge-A is more accurate than SAST-Ridge on 20 datasets and less accurate on 18 (Fig.
11(c) ). Fig. 11(d ) reveals that ensembling SAST-Ridge models improves accuracy on almost every dataset. But the improvement is slight as even though the reference time series are chosen randomly, SAST-Ridge has very low variance in accuracy over multiple runs. We think that this capability comes from the fact that the model uses only one variant of each shapelet to learn the decision boundaries. The critical difference diagram between SAST models is shown in Fig. 12. SASTEN-Ridge is the best of all, followed by SASTEN-Ridge-A which is not significantly less accurate. SAST-Ridge is the third best model and is not significantly worse than SASTEN-Ridge-A, but is considerably less accurate than SASTEN-Ridge. SAST-Ridge-A and SAST-RF are significantly less accurate. Although SASTEN-Ridge and SASTEN-Ridge-A are more accurate than SAST-Ridge, we believe that the accuracy gain does not worth the computation time overhead required by SASTEN-Ridge or the engineering work required to find the appropriate 𝑙𝑒𝑛𝑔𝑡ℎ_𝑙𝑖𝑠𝑡 to use in SASTEN-Ridge-A.
SAST vs STC We now compare SAST (i. e SAST-Ridge) to STC, the state of the art shapelet method to our knowledge. This experiment is performed on the same 72 datasets and a pairwise comparison of SAST, STC and STC-1 is shown in Fig. 13. SAST is more accurate than STC on 43 datasets, worse on 27 and there are two draws. STC-1 is more accurate than SAST on only 5 datasets among 72, although the only difference between these two models is that the Ridge classifier in SAST is trained using the whole shapelet space while only a subset of the shapelet space is used in STC-1. STC-1, STC and SAST, respectively achieve an average accuracy of 0. 68 ± 0. 21, 0. 79 ± 0. 20 and 0. 84 ± 0. 12 on the 72 datasets. The standard deviation of STC and STC-1 models is higher due to the zero score obtained on one dataset (Fungi).
There are datasets on which STC and STC-1 hardly achieve 50% accuracy, while SAST performs significantly better. This is the case for   the datasets Crop, ElectricDevices and Fungi. These datasets contain respectively 24, 7 and 18 classes. It is difficult to find a subsequence in these datasets that is present in one class and not in the others. A subsequence is generally shared among multiple classes, and therefore is not highly discriminative in terms of information gain by itself. Subsequences need to be combined in order to differentiate classes, and since all the subsequences are available in SAST, this combination is automatically learned by the classifier. Elsewhere SAST achieves 90% accuracy on the dataset Fungi, while STC and STC-1 fail to find any shapelet on it. These results confirm our thought that pruning shapelet candidates, without taking into account the classifier can lead to very inaccurate classification.