How they analyze security

What algorithm used to solve SD(1) ?

1 ISDs (Information Set Decoding) as usual 2 In the case of SDiTH the field size is big q = 256 or q = 251 3 They claim that it is enough to stop at Stern's algorithm [Stern,1989]

SDITH security

Based on d-split syndrom decoding problem (a key recovery attack on SDiTH is as hard as solving the d-split Syndrome Decoding problem) Problem (d-split Syndrome Decoding SD(d, H, s, t))

Given a matrix H ∈ F (n-k)×n q , a syndrome s ∈ F n-k q and a distance t ∈ 0, n , one wants to find a vector e = (e1, . . . , e d ) ∈ (F n/d q ) d such that He = s and ∀i ∈ 1, d , |ei| = t/d.

SDiTH framework

Solve the SD(d, H, s, t) problem with : a random H s from an injected solution (s = He such that |ei| = t/d)

Reduce SD(d) to SD(1) ?

In the specification, they use [Feneuil,Joux,Rivain,2022] results to obtain the following bound Reduction from SD(d) to SD(1)

T SD(d) ⩾ n/d t/d d n t T SD(1)
Idea : Consider an algorithm A which solves SD (d) Let (H, s, t) be an instance of SD(1) Run A on (Hσ, sσ, t) with a random permutation at each step There is a probability

( n/d t/d ) d ( n t )
of obtaining an instance of SD(d) at each step.

Problem

This bound is tight only when t → 0 (we will see why)

Security assessment in the specification

Based on Stern algorithm

They perform non-asymptotic analysis to gain security bits They use Peters' tricks [Peters,2010] to optimize the non-asymptotic complexity of Stern

Stern algorithm

Input :

H ∈ F (n-k)×n q
, s ∈ F n-k q and t ∈ 0, n Output : e ∈ F n q such that He = s and |e| = t Parameters : p ∈ 0, min(t,k) 2 and ℓ ∈ 0, n -k -t + 2p

Repeat as many time as necessary :

1 draw I ⊆ 1, n of size k uniformly at random 2 J ← 1, n \ I 3 P ← H -1
J HI 4 y ← H -1 J s 5 P ′ ← the ℓ first rows of P and y ′ ← the ℓ first positions of s 6 Bet that :

e I = (x 1 , x 2 ) ∈ F k/2 q such that |x 1 | = |x 2 | = p e J = (0 l , x 3 ) ∈ F l q × F n-k-l q such that |x 3 | = t -2p
Security Analysis in NIST specification Correction of the analysis Improved attack with projective space How to find e with betting ?

With the bet, we have :

P ′ x2 x3 = y ′ -P ′ x1 y ′′ -P ′′ (x1 + x2) 7 L1 ← y ′ -P ′ x1 : x1 ∈ F ⌊k/2⌋ q × 0 k-⌊k/2⌋ and |x1| = p L2 ← P ′ x2 : x2 ∈ 0 ⌊k/2⌋ × F k-⌊k/2⌋ q and |x2| = p 8 For all (y ′ -P ′ x1, P ′ x2) ∈ L1 × L2 such that y ′ -P ′ x1 = P ′ x2 If |P(x 1 + x 2 ) -y| = t -2p, return e, such that e I def = x1 + x2 e J def = y -P(x1 + x2)

Stern complexity

T SD(1) =   TGauss + T lists + T checks 1 -(1 -pe) N sol   log2(q)
TGauss : complexity of Gaussian elimination T lists : complexity of constructing lists T checks : complexity of collision checking pe : probability of finding a particular solution N sol : expected number of solutions to the problem

L1 = P ′ x1 -y ′ : x1 ∈ F ⌊k/2⌋ q
and |x1| = p and

L2 = P ′ x2 : x2 ∈ F k/2-⌊k/2⌋ q × and |x2| = p
Choose an enumeration order σ on x ∈ F ⌊k/2⌋ q : |x| = p such that x σ(i) and x σ(i+1) differ by 1 on at most two successive coordinates depending on the case : Precompute the sums of two successive columns of P ′ Construct an element of the list ⇒ one addition of one column of size ℓ (except the first which requires p -1 or p addition of columns depending of the list)

T lists = ℓk + ℓ(2p -1) + ℓ (|L1| + |L2|) (1.1)

Second and third tricks

The second trick comes into collision checking

|P(x1 -x2) -y| = t -2p (1.2)
Verify that the Hamming weight of a certain vector of length n -k -ℓ equals t -2p

Remarks that the vector is actually a random vector when it does not come from a wanted solution On the wrong candidates, check the Hamming weight over q q-1 (t -2p + 1) positions on average Checking on each coordinate for each position : 2p additions, 2p q-2 q-1 multiplications

T checks = q q-1 (t -2p + 1)2p 1 + q-2 q-1 |L1| |L2| q ℓ
Third trick

The third trick concerns Gaussian elimination but they neglect it because they claim that its cost is negligible

Their complexity result

Let's summarize their results :

Complexité

L1 := |L1| = ⌊ k 2 ⌋ p (q -1) p L2 := |L2| = k-⌊ k 2 ⌋ p (q -1) p TGauss = 1 2 (n -k) 2 (n + k) T lists = ℓk + ℓ(2p -1) + ℓ (|L1| + |L2|) T checks = q q-1 (t -2p + 1)2p 1 + q-2 q-1 |L1| |L2| q ℓ pe = L1L2 n-k-ℓ t-2p n t (q -1) 2p N sol = 1
d GV (n, k) def = inf t ∈ 0, n -n q : n t (q -1) t ⩾ q n-k
1 With their parameters, they take t = d GV (n, k), they assume that the factor N sol (1) is one (we only have the injected solution)

2 It is only true asymptotically with n

3 With their range of parameters N sol (1) ∈ 412, 1056 ⇒ between 8.7 and 10 bits lost The reduction bound is not tight

They do not take into account N sol Without N sol : pe(1) ⩾ ( n/d t/d ) d ( n t ) pe(d) With N sol : pe(1)N sol (1) ⩾ pe(d) ( n/d t/d ) d ( n t ) 1 + (N sol (d) -1) ( n t ) ( n/d t/d ) d
The precise reduction from SD(d) to SD(1) give

1 N sol (d) = 1 ⇒ pe(1)N sol (1) ⩾ ( n/d t/d ) d ( n t ) pe(d)N sol (d) 2 N sol (d) >> 1 ⇒ pe(1)N sol (1) ⩾ pe(d)N sol (d) N sol (d) ∈ 30,

Result after correction

  748 so we are in the second case givingT SD(d) ⩾ T SD(1)ConsequencesTheir bound is therefore optimistic, with the real bound they gain security bitsStern algorithm adapted to SD(d)it's interesting to directly solve the problem SD(d) here. We therefore adapt Stern to SD(d) Principle of adaptation 1 Split the information set I as I1 ∪ • • • ∪ I d where Ii is of size k d and is randomly chosen in I. 2 Make a bet on each of them. The fact that TI (d) ⩽ TI (1) makes us gain in complexity compared to the theoretical bound.

  E over Fq ∀x, y ∈ E, x ∼ y ⇐⇒ ∃α ∈ F * q , x = αy [x] def = {y ∈ E : y ∼ x} E / ∼ def = {[x] : x ∈ E}

Table -

 - SDiTH security in the specificationThey do not take into account the N sol factor

	The choice of a non-asymptotic analysis
	Security Analysis in NIST specification
	Advantage
	Parameter Sets Bit gain on security Correction of the analysis Category First problem SDitH-L1-gf256 I SDitH-L1-gf251 I Second problem Inconvenience Very accurate calculations ⇒ easy to make mistakes Security Specification p l T SD(1) ( n/d d t/d ) ( n t ) target 1 2 143.46 143 1 2 143.45 143 Third problem	SD Parameters n k t 256 230 126 q 79 251 230 126 79	d 1 1
	SDitH-L3-gf256 We are exposed to more attacks which bring non-asymptotic gains III 2 5 207.67 207 256 352 193 120 2
	SDitH-L3-gf251 Improved attack with projective space III 2 5	207.61	207	251 352 193 120 2
	SDitH-L5-gf256	V	2 5	272.35	272	256 480 278 150 2
	SDitH-L5-gf251	V	2 5	272.29	272	251 480 278 150 2

Definition

Let N sol (d) denote the expected number of solutions of

SD(d)

Table -

 - Correction of the analysisRemarkWe have not yet corrected the complexity of Gaussian elimination, we have to consider[Bernstein,Lange,Peters,2008] and[Peters,2010]

		Security Analysis in NIST specification
			Correction of the analysis
		Improved attack with projective space
	Security Analysis in NIST specification
	Parameter Sets	Security Specification	Correction		SD Parameters
	p l T SD(1) Correction of the analysis	( n/d t/d ) ( n t )	d	p l	T SD(d)	q	n	k	t	d
	SDitH-L1-gf256 First problem	1 2	143.46		1 2 134.61	256 230 126	79	1
	SDitH-L1-gf251 Second problem	1 2	143.45		1 2 133.61	251 230 126	79	1
	SDitH-L3-gf256 Third problem	2 5	207.67		2 5 206.16	256 352 193 2
	SDitH-L3-gf251	2 5	207.61		2 5 205.02	251 352 193 2
	SDitH-L5-gf256	2 5	272.35		2 5 271.30	256 480 278 2
	SDitH-L5-gf251 Improved attack with projective space 2 5 272.29		2 5 269.81	251 480 278 2

On the same support :x σ(i) = (. . . , d, . . . , 0) ⇒ x σ(i+1) = (. . . , d + 1, . . . , 0) ⇒ One coordinate

Change of support : x σ(i) = (. . . , q -1, 0, . . . ) ⇒ x σ(i+1) = (. . . , 0, 1 . . . , 0) ⇒ Two successive coordinates

They consider that Gaussian elimination is negligible

In the case of SDitH-L1-gf256 with q, n, k, t, d = 256, 230, 126, 79, 1 Their optimal cases : We have to consider [Bernstein,Lange,Peters,2008] and [Peters,2010] to improve TGauss Observation Suppose we are trying to solve the problem SD(1) in the case of a 0 syndrome.

We get a good solution if and only if we find x1 and x2 such that

We calculate (q -1) times too much solution

How to exploit that ?

Adaptation of Stern's algorithm in projective space

Impact on complexity

We divide the size of the lists by a (q -1) factor ⇒ we hope to gain a factor (q -1) on the complexity What if the syndrome is non-zero ?

Reduction of the Syndrome Decoding problem to the low weight code words search

The reduction :

We look for e such that He = s and |e| = t.

Let C be the code associated with the parity check matrix H.

1 Find z such that Hz = s (z = (0, s))

2 Let Hz a parity check matrix of the code ⟨C, z⟩.

3 Find e such that Hze = 0

Analysis

The algorithm finds e such that He = αs (for a α ∈ Fq).

(So just divide by α and we solved the problem)

Proof on board

What about the complexity

The reduction cost almost nothing (a factor q q-1 ) We reduced the problem to dimension k + 1 ⇒ possible loss To exploit the idea, we want to take the lists in projective space to divide their size as well as the number of collisions by (q -1) :

We must take precautions A collision of equivalence classes does not necessarily induce a collision

) induce a collision We cannot do a naive search for such a couple otherwise we lose the gain of the factor (q -1)

The solution

We build good representatives who induce a collision

Particular representative

For all [x] ∈ F k+1 2 q / ∼ we define x as the unique representative of [x] such that :

We now have the desired property Property

The algorithm

The only things that change with the classic Stern algorithm are the following :

The possible losses on the theoretical gain of the factor (q -1) : problem one

We must adapt Peters' tips to our new algorithm ⇒ potential losses problem two

We go from dimension k to dimension (k + 1) ⇒ potential losses

Adaptation of tricks

The tricks on list construction : Use as before an enumeration order on x ∈ F (k+1)/2 q : x = (0, . . . , 0, 1, . . . ) and |x| = p to compute P ′ x in one addition of one columns by elements.

Normalize P ′ x by its first non-zero coordinate to get P ′ x (We lose a factor of 2 here on the trick)

The second trick on collision checking :

We just need to normalize x on collisions to get x which takes 2p operations per collisions (negligible). We can then apply the trick as before.

The real gain

For the other complexity values, we have :

≈ 1 4 for the range of parameters)

Expected gain

We lose 2 bits due to the transition from dimension k to dimension k + 1.

We lose

We should have an additional gain between 5 and 6 bits with the projections

Remark

We can adapt the Stern projectif algorithm to the problem SD(d) as previously The loss of 0.5 bits on the expected results is linked to the fact that the Gaussian elimination is not negligible.

Work in coming

Improvement of TGauss with [Bernstein,Lange,Peters,2008] and [Peters,2010] Apply the adaptation of projective spaces to [Dumer,1991] to see if we obtain a gain

Try to generalize the idea to the Grassmannian (generalization of projective spaces with several dimensions)


Thom Scott-Phillips
email: thom.scottphillips@gmail.com

Daniel Nettle

Cognition & society: Prolegomenon to a dialogue VERSION May 2022, FINAL

Keywords: cognitive science, social science, dialogue

One of the original and putative goals of cognitive science is to describe and explain causal links between individual minds, on the one side, and the collective phenomena of society on the other.

Yet, substantive connections are still only patchy at best, and deep methodological and philosophical differences are a persistent thorn in the side of further progress. Addressing this problem is critical both for the future advancement of cognitive science in its own right, and to increase its broader societal relevance. Here, we describe how future advances can be catalyzed by new and innovative fora for dialogue across the cognitive-societal divide. Such dialogues, and the synthetic research programs they might provoke, would not only advance knowledge and understanding in their own right, but also increase returns on existing bodies of more specialized knowledge. They would also put to work one the major findings of cognitive science itself, namely that human reasoning functions most effectively in interactive contexts.

Societies are clearly made up of individuals and individual minds-but how? How do many interacting minds generate and constrain the group level phenomena that are collectively called 'society'? Or is it better to think of generation and constraint from the other direction, that the kind of minds people have depends on the societies they belong to? These questions are basic to the original and putative goals of cognitive science as a scholarly enterprise, touching on many familiar and persistent dualities: reductionism and holism; micro and macro; nature and society. Yet, the study of mind is currently pursued rather independently from the study of society. For the most part, the cognitive sciences study individual and interactive phenomena such as communication, decision-making, political attitudes and moral reasoning. They also default towards the universal [START_REF] Levinson | The original sin of cognitive science[END_REF]. The social sciences, meanwhile, study collective phenomena such as languages, economies, democracies, technologies, institutions and laws; and they are chary of assuming generalizability across history or contexts. The differences between the cognitive and social sciences in methodological procedures and theoretical vocabularies are often profound, and this may be partly justified by their different levels of enquiry. However, these differences make it hard to discern the important implications each body of knowledge must have for the other. Too often, we seem to be on one side or another of a large divide.

How to build more substantive bridges is a puzzle. Academic rewards work mostly in the direction of narrow specialization. The deep expertise acquired in this way is essential and rightly valued very highly, but it also generates silos. Some scholars pioneer broad frameworks by starting from their own domain of expert knowledge and building outwards. This can be highly productive, but it also runs the risk of being cavalier, or even imperialistic, in that it may not link deeply with what is already known and discussed on the other side.

In our view, if integration and consilience are the main goal, then the first, most pressing question should not be (for instance), 'How can moral cognition explain legal systems?', but rather, where does what we already know about moral cognition interface with what legal scholars already know about legal systems? Likewise, the question should not be, 'What happens in the brain when people visit an art gallery?', but rather, how does what we know about the neuroscience of aesthetics and interpretation interface with what art theorists have debated and established within that domain? Addressing such questions is, we believe, critical both for the future advancement of cognitive science in its own right, and to demonstrate the broader relevance of a cognitive perspective for the human sciences, and for society at large.

Here are three specific examples of domains in which the cognitive-societal divide is of paramount importance, with the first case being the one with the deepest history. This is of course not an exhaustive list. Our goal with these examples is not to describe how particular fields might or should proceed, but rather to highlight the diversity of issues that under the page of shared umbrella of 'cognition and society'. It is plausible to us that lessons learned in one or another domain will generalize to others.

Communication & languages. Sometimes called the "problem of linkage" (Kirby, 1999, p.19), the question of how language use (an individual phenomenon) links with language structure (a collective phenomenon) is an established and fundamental problem in language science. This fact alone marks out the language sciences as further ahead than other domains with respect to the cognitive-social divide. However, while several ongoing research programs speak to the issue (e.g. [START_REF] Adgar | Language Unlimited[END_REF][START_REF] Gibson | How efficiency shapes human language[END_REF] Inequalities. Ecological, technological and demographic factors systematically generate inequalities in society, often dramatically so. These inequalities are accepted and sometimes institutionalized, at times with the apparent consent of those who are disadvantaged by them.

Loose claims that humans are 'naturally egalitarian' or 'naturally selfish' do not hold up. Rather, people accept some kinds of inequalities as moral and appropriate, and others as wrongs that need to be collectively righted. Cognitive appraisals matter: inequalities are perceived as more acceptable if they are related to variation in effort; if the people involved are perceived as fundamentally different; and in the absence of common shared threats [START_REF] Starmans | Why people prefer unequal societies[END_REF] Nettle & Saxe 2020). These regularities might explain, though also might reflect, historical changes in inequality, as well as the rhetorical strategies employed by those who seek to increase or reduce it.

How to best address these diverse issues, and hence create healthy connective tissue across the cognitive-societal divide, will vary on a case-by-case basis. One approach will be through careful empirical work, with clear methodological and thematic roots on both sides [START_REF] Astuti | Constraints on conceptual development: A case study of the acquisition of folkbiological and folksociological knowledge in Madagascar[END_REF] is a fine example). Beyond this, we would like to advocate for a particular kind of conversation, or dialogue, between cognitive and social scientists, targeted at the mutual page of identification of open issues. Our question is not, 'Who is right?'. The questions are rather, 'How do the research agendas, findings and insights on one side connect with those on the other?', 'Are these findings aligned, or are there tensions to be identified and addressed?', and 'Do these tensions suggest fruitful new areas of enquiry, or important open questions, for either or both sides?'.

Developing good answers to these questions is likely to have many potential payoffs.

First, answering these questions will directly advance understanding in its own right. Second, it will increase returns on existing, specialized knowledge. Third, it is likely to catalyze new, synthetic research programs helping to link cognition and society in a substantive way. More broadly, we are not calling for a revolution, but revitalisation of dialogue as an important tool of scientific progress. Cognitive science itself has shown that human reason is most productive when used in interaction [START_REF] Mercier | The Enigma of Reason[END_REF]Scott-Phillips, in press). We are advocating for the application of this insight to the identification of key questions for future research programs, in a domain that should be fundamental for cognitive science but is in fact relatively neglected.

The time is now. Demands for deeper ideas and integration across (sub)disciplines are historically common in the human sciences, but have grown stronger and more urgent in light of the ongoing 'replication crisis' in psychology and related fields. Many contributions to present debate about the future of the human sciences have emphasized the need for better foundations and transdisciplinary synthesis, alongside essential methodological reform (e.g. [START_REF] Eronen | The theory crisis in psychology: How to move forward[END_REF][START_REF] Flis | The function of literature in psychological science[END_REF][START_REF] Scheel | Why most psychological research findings are not even wrong[END_REF]. Good faith dialogues across the cognitive-social divide will help to meet this demand directly.

  , broad consensus is not yet achieved. Different theoretical schools of thought have clear and different-sometimes radically different -candidate answers. Law. Bodies of law transcend and outlast the desires, intentions or interests of any particular individual. That, indeed, is their point. Nonetheless, they must be somehow connected to individual senses of right and wrong, acceptable and unacceptable-but how exactly? To what extent do existing legal systems satisfy Oliver Wendall Holmes' demand that "The first requirement of a sound body of law is that it should correspond with the actual feelings and demands of the community" (cited in Giffin & Lombrozo 2016)? Large literatures exist on moral judgment and punitive sentiment, but these are only patchily connected to legal scholarship. Issues of the appropriate direction of causal arrow loom large here: Do people know what is right and wrong because the law tells them, or do they invent the laws that correspond to their sense of right and wrong?

Acknowledgements

We have benefited from dialogue and are grateful for it. We acknowledge in particular Christophe Heintz, Rebecca Saxe, and students on the course 'From Cognition to Society' at the Central European University in Vienna 2021.

Funding statement


Nicolas Rojas Varela

Michael Franklin Mbouopda
email: mf.mbouopda@gmail.com

Engelbert Mephu Nguifo
email: engelbert.mephunguifo@uca.fr

RSAST: Sampling Shapelets for Time Series Classification

Keywords: Time series Classification, Shapelet, Scalability, Interpretability, ANOVA, ACF, PACF

Shapelet-based techniques are widely utilized in time series classification due to their combination of interpretability and accuracy. However, these methods tend to be less scalable than other state-of-the-art approaches. Because of this, we propose RSAST as a shapeled-based technique that utilizes a stratified technique and certain statistical criteria to randomly select the shapelets. We conducted experiments on 128 datasets from the UCR archive, showcasing the comparative accuracy of RSAST against its baseline methods SAST and STC, as well as other state-of-the-art techniques. Notably, the method we propose, RSAST, preserve the accuracy and interpretability of the baseline methods while reducing the computation time. For example, with Earthquakes, one of the largest datasets from the UCR archive, RSAST took 6 minutes and 36 seconds to complete the training process, whereas SAST took 2 hours and 37 minutes.

I. INTRODUCTION

Time series data is a type of data that is measured over time. This type of data has applications in various tasks such as time series anomaly detection, time series forecasting and time series classification. In particular, this work is focus on the time series classification task which contemplated various methodologies such as STC, SAST, HIVE-COTE, ROCKET, RDST among others. Notably, the Scalable and Accurate Subsequence Transform (SAST) [START_REF] Mbouopda | Scalable and accurate subsequence transform for time series classification[END_REF] stands out as one of the most precise and interpretable techniques. So, our work aims to study SAST approach and propose an improvement of the method.

In the state-of-the-art there are many algorithms for time series classification which uses different features for the classification. Depending of the features the methods can be categorized into eight groups [START_REF] Middlehurst | Bake off redux: a review and experimental evaluation of recent time series classification algorithms[END_REF]:

• Distance-based methods: In this category, entire time series are compared using distance measures in combination with nearest neighbor (NN) classifiers. Examples of such approaches include the Elastic Ensemble (EE) [START_REF] Lines | Time series classification with ensembles of elastic distance measures[END_REF], which involves an ensemble of 11 1-NN classifiers weighted with a variety of elastic distance measures. Another method is Proximity Forest (PF) [4], which utilizes the same 11 distance functions as EE but with improved accuracy and scalability..

• Feature-based methods: These methods involve extracting features from the time series and using them in a classifier. Various feature extraction techniques can be employed, including statistical measures, frequency domain analysis, and time-domain characteristics. For example, Catch22 [5], one of these methods, utilizes 22 hctsa features identified as the most discriminatory in a set. These features encompass a broad spectrum, including basic statistics of time series values, linear correlations, and entropy. Similarly, TSFresh [6] was introduced as a collection of approximately 800 features extracted from time series. • Interval-based methods: In these approaches, it is selected one or more intervals within a time series rather than using the entire sequence. Multiple intervals can be chosen, and summary measures from these intervals are then utilized as features for classification. One example of this approach is TSF [7], which extracts three summary statistics (mean, variance, and slope) from randomly selected intervals. Similarly, RISE [8] generates random intervals but employs spectral features instead. • Shapelet-based methods: Algorithms in this category aim to identify short patterns known as shapelets, which define a class. These shapelets can appear anywhere in the series and are not dependent on the phase. A class is distinguished by the presence or absence of one or more shapelets within the entire series. The baseline from this methods in the literature it is STC [9] since is a pipeline which searches the training data for shapelets, transforms the time series and builds a classifier with the tranformed data. Later RDST [START_REF] Guillaume | Random dilated shapelet transform: A new approach for time series shapelets[END_REF] uses randomly selecting shapelets from the train data to transform the dataset and train a classifier introducing the concept of dilated shapelets. • the frequency of subseries repetition is more crucial than their mere presence or absence. These methods involve creating frequency counts of recurring patterns and developing classifiers based on the resulting histograms.

For instance, BOSS [START_REF] Schäfer | The boss is concerned with time series classification in the presence of noise[END_REF] utilizes sliding windows that are transformed into words using SFA. This process generates a feature vector by counting the occurrences of each word across all windows. • Convolution-based methods: These methods consist in the application of convolution and pooling operations to time series, transforming the original space into a new dataset suitable for classification. The most representative method in this category is the Random Convolutional Kernel Transform (ROCKET) [12]. ROCKET generates a large number of randomly parameterized convolutional kernels, typically ranging from thousands to tens of thousands, and uses them to transform the data. Also, there are several variants of ROCKET, such as MiniROCKET [START_REF] Dempster | Minirocket: A very fast (almost) deterministic transform for time series classification[END_REF], which significantly accelerates ROCKET with no substantial difference in accuracy.

• Deep learning-based methods: This category utilizes neural network structures for time series classification. Examples of methods in this category include the Residual Network (ResNet) [START_REF] Lucas | Proximity forest: an effective and scalable distance-based classifier for time series[END_REF] and InceptionTime [15], each employing distinct architectures for classification. • Hybrid approaches: These approaches involve combining algorithms from two or more of the previously mentioned approaches into a single classifier. These methods aim to leverage the strengths of different techniques for improved performance. For example, HIVE-COTE [START_REF] Christ | Time series feature extraction on basis of scalable hypothesis tests (tsfresh-a python package)[END_REF] is a heterogeneous ensemble containing five modules, each from a different representation. Another example is TS-CHIEF, which is a homogeneous ensemble where hybrid features are embedded in tree nodes.

Despite the high accuracy of state-of-the-art time series classification algorithms, they often suffer from computationally intensive calculations or lack interpretability of the results. Because of this, our work will focus on shapelet approaches, which offer interpretability and accuracy.

The Scalable and Accurate Subsequence Transform (SAST) [START_REF] Mbouopda | Scalable and accurate subsequence transform for time series classification[END_REF] method was proposed as a method based on shapelets and builded upon STC [9]. SAST reduces the search space for shapelets by selecting only a few instances per class from the dataset, resulting in a complexity of O(nm 3 ) + O(classifier).

So, in order to increase the scalability of SAST, we propose a novel approach called Random SAST (RSAST). RSAST avoids the use of a searching algorithm by employing a stratified sampling technique to select candidate shapelets. By doing so, RSAST significantly reduces the computational burden while maintaining competitive accuracy and interpretability.

Mainly, RSAST utilizes fundamental statistical concepts such as ANOVA, Autocorrelation Function (ACF), and Partial Autocorrelation Function (PACF). So, the ANOVA test enables a more accurate selection of starting points for the shapelets, while ACF and PACF assist in identifying the most relevant lengths for these subsequences.

The Analysis of Variance (ANOVA) assesses variability within and between classes using a statistical test known as the F-test, allowing for a comparison of mean similarities. Depending on the number of classes being analyzed, various ANOVA variations can be employed [17]. Notably, RSAST predominantly utilizes one-factor ANOVA, as many time series classification tasks typically involve considering just one factor or class for classification. Also for RSAST it is assumed the independence, normality, and homogeneity of variances of the values.

Although there are alternative methods for ANOVA to compare the similarity of groups, such as the Kruskal-Wallis test, Mood's median test, or even information gain, [9] demonstrated that there are no significant differences in accuracy when choosing between these alternatives. Consequently, RSAST only considers ANOVA to compare values across time series.

Thus, the contributions of our work can be summarized as follows:

• Utilizing a stratified sampling strategy for subsequences selection, as in SAST, but taking into account certain statistical criteria such as ANOVA, ACF and PACF. The subsequent sections of our work will delve into the background and related work to the topic (Section II). Also, we will provide a detailed explanation of the method (Section III), and showcase the experimental results obtained using RSAST (Section IV). By presenting these sections, we aim to demonstrate the effectiveness and advantages of RSAST in time series classification tasks.

II. BACKGROUND AND RELATED WORKS

A. Definitions

In this section, we provide an overview of the key concepts used to describe RSAST methodology.

1) Time Series Classification: It is a task in machine learning that involves predicting the class or category of a time series dataset. 2) Time Series: A time series (TS) is a sequence of data points collected over time, where each data point is associated with a specific timestamp. TS can be used within a instance pair {x, y}, where x is the TS with m observations (x 1 , x 2 , ..., x m ), and y is a discrete class variable with |c| possible values. The list of n cases with associated class labels can be represented as T = (X, y) = ((x 1 , y 1 ), (x 2 , y 2 ), ..., (x n , y n )). 3) Classifier: refers to a function or mapping that operates on the input space and assigns a probability distribution over the possible class variable values. 4) Shapelets: shapelets are subsequences, denoted as S = {s 1 , ..., s l } with length l, that can effectively differentiate between different classes or categories in a time series dataset [18]. 5) Autocorrelation Function (ACF): is a tool used to measure the similarity between a time series and a delayed version of itself [19].

6) Partial Autocorrelation Function (PACF): similar to ACF, is a measure of the correlation between a time series and a lagged version of itself, after removing the effects of all the shorter lags [START_REF] Shumway | Time Series Analysis and Its Applications: With R Examples[END_REF]. 7) Analysis of variance (ANOVA): is a statistical method used to analyze the difference between the means of two or more groups. It is used to determine if there is a significant difference between the means of two or more groups based on the variation in the data [17].

B. Shapelet Approaches

As previously mentioned, time series classification (TSC) methods can be categorized into different categories, each with methods varying in their levels of accuracy, complexity, and interpretability [START_REF] Middlehurst | Bake off redux: a review and experimental evaluation of recent time series classification algorithms[END_REF].

Shapelets methods focus on finding subseries that allows distinguishing the different classes of time series. The process involves sliding these subseries across the time series and calculating the distance between the subseries and the segments of the time series.

The initial shapelet approach in the literature emerged with the work by [18]. This procedure introduced embedded shapelets within a decision tree classifier, showcasing the potential of employing shape-based features to enhance classification performance for time series data.

Following this, subsequent studies have been dedicated to two primary aspects: refining the accuracy of the original shapelet algorithm and addressing the inherent computational complexity associated with shapelet methods.

One improvement of accuracy is proposed with Shapelet Tranform [9], STC takes a multi-step approach to enhance accuracy in time series classification. Firstly, it conducts an exhaustive search for shapelets within the training data. Then, it transforms the time series into distance-based vectors, enabling the selection of the most distinguishable shapelets among classes using the information gain criterion. Then, with the selected shapelets, the algorithm constructs a classifier using the transformed series data.

Recently, some changes were introduced for STC [21] like a randomised search of shapelets with a search time as parameter, a binary shapelets evaluation against all other classes, and the use of Rotation Forest instead of HESCA classifier [START_REF] Middlehurst | Bake off redux: a review and experimental evaluation of recent time series classification algorithms[END_REF].

The Scalable and Accurate Subsequence Transform (SAST) aims to improve the complexity of STC by reducing the number of patterns to be assessed [START_REF] Mbouopda | Scalable and accurate subsequence transform for time series classification[END_REF], and as a consequence, making the model faster to train. To accomplish this, SAST reduces the number of shapelet candidates by selecting randomly k instances per class. Furthermore, it does not select the top best shapelets beforehand, as in STC, instead all shapelets are used to transform the data.

Moreover, in Fast Shapelets (FS) [START_REF] Rakthanmanon | Fast shapelets: A scalable algorithm for discovering time series shapelets[END_REF], it was introduced an enhanced version of the decision tree shapelet approach proposed in the original algorithm [18]. This approach focuses on accelerating shapelet discovery. Instead of performing an exhaustive search at every node, FS utilizes symbolic aggregate approximation (SAX) to discretize and approximate shapelets. SAX is a technique that transforms time series into strings, reducing their dimensionality using piecewise aggregate approximation (PAA) and discretizing them into bins based on equal probability areas of the normal distribution.

Similarly in Learned Shapelets (LS) [START_REF] Grabocka | Learning time-series shapelets[END_REF], it is introduced the use of a heuristic gradient descent shapelet search approach instead of the traditional enumeration strategy. Unlike FS and STC, LS is not constrained to identifying shapelets solely from subseries within the training data.

Another shapelet approach is the Generalised Random Shapelet Forest or RSF [START_REF] Karlsson | Generalized random shapelet forests[END_REF]. This method consists of a bagging-based tree ensemble that aims to improve computational efficiency and predictive accuracy. At each node of a different tree, r univariate shapelets are selected from the training data. Each shapelet has a random length within some predefined upper and lower bounds. Multiple trees are ensembled, so new instances are predicted by a majority vote on the trees' predictions.

Also, the Multiple Representation Sequence Learner (MrSEQL) [25], is another ensemble classifier which is based on SEQL classifier [26]. MrSEQL looks for the existence or non-existence of a shapelet within the data. However, instead of employing a distance-based technique to quantify this presence or absence, MrSEQL converts the subseries into symbolic words. Subsequently, these words are generated via two symbolic representations-SAX for the time domain and SFA for the frequency domain. A collection of distinctive words is chosen using Sequence Learner (SEQL). The training procedure culminates in a logistic regression model, yielding a set of important subsequences determined by the model's weights.

Lastly, a recent advancement in phase-independent approaches has been introduced with the Random Dilated Shapelet Transform or RDST [START_REF] Guillaume | Random dilated shapelet transform: A new approach for time series shapelets[END_REF]. This algorithm integrates various convolution techniques. RDST employs dilation with shapelets, which means that some spaces are defined between time points. Hence, a shapelet with dilation d is compared to time points d steps apart when computing distances between shapelet and time series. The method also uses two features in addition to distance, it uses the position of the minimum distance, and it measures the frequency of occurrences of the shapelet, based on a distance threshold. Consequently, the transformed data comprises 3k features (for k shapelets) subsequently employed in a classifier.

Although highly accurate RDST has deficiency in interpretability since the shapelets found could exhibits dilation, which is not natural for domain expert. An example of the lack of interpretability can be seen training the model with Coffee dataset from the UCR archive. Here, the first shapelet, according to a feature importance analysis, has a dilation of 13, the second most important shapelet has a dilation of 12 and the third shapelet has a dilation of 15 (see Fig. 1). As a consequence, when these shapelets are plotted on random instances from each class of the training set (see Fig. 2), it is observed that they do not seem to match perfectly with the time series, as it is the case of other methods like STC, SAST and RSAST. In consequence, it is not clear the distinct pattern which enables the differentiation of classes of the RDST approach. Besides, in RDST, the features are categorized into 3 types: the presence or absence of the shapelet (min), the position (arg min) and the frequency (SO). So, for the interpretation of the method, it is necessary to take into account the feature type as part of the analysis of the results. For instance, for Coffee dataset (see Fig. 2), the 3 most important shapelet are argmin type, indicating that their importance is determined by the location of the shapelets. For more details of RDST method it is suggested to read [START_REF] Guillaume | Random dilated shapelet transform: A new approach for time series shapelets[END_REF].

C. SOTA Approaches

There are some state-of-the-art methods, that focus on combining different types of features in order to achieve highest accuracy.

One of these main techniques that achieve the highest accuracy is a convolutional approach, called ROCKET, which stands for Random Convolutional Kernel Transform [12]. This method generates an extensive assortment of convolutional kernels with randomized parameters. These kernels are then utilized to transform the data through convolution and pooling operations like max pooling (identifying the maximum value) and the proportion of positive values (PPV). The results gives two features which are concatenated for all kernels. Thus, for k kernels, the transformed data has 2k features. These feature vectors are harnessed to train a Ridge Classifier, incorporating cross-validation to determine the L2-regularization parameter α. In scenarios involving larger datasets, a logistic regression classifier is proposed as an alternative.

Another accurate method is the Hierarchical Vote Collective of Transformation Ensembles (HIVE-COTE) [START_REF] Christ | Time series feature extraction on basis of scalable hypothesis tests (tsfresh-a python package)[END_REF]. This ensemble consists of five distinct modules, each capturing different features. These modules encompass the EE from distance-based representations, TSF from interval-based methods, BOSS from dictionary-based approaches, STC from shapelet-based methods, and a spectral method called RISE. Cross-validation Accuracy Weighted Probabilistic Ensemble (CAWPE) [27] is used to ensemble the results of the five modules.

HIVE-COTE demonstrated enhanced scalability in the HIVE-COTE v1.0 (HC1) [28], incorporating several advancements. HC1 introduced four modules, with cBOSS [START_REF] Middlehurst | Scalable dictionary classifiers for time series classification[END_REF] replacing BOSS. The updated randomised version of STC [START_REF] Bostrom | Binary shapelet transform for multiclass time series classification[END_REF] with a Rotation Forest classifier and a default one-hour shapelet search. Usability improvements were made to TSF and RISE. Notably, this version omitted the computationally intensive EE algorithm, resulting in improved efficiency without sacrificing accuracy.

Similarly HC1 was improved through HIVE-COTE v2.0 (HC2) [START_REF] Middlehurst | Hive-cote 2.0: a new meta ensemble for time series classification[END_REF]. In HC2, only STC is retained from the prior version, while the remaining modules undergo transformation. The substitution of modules is prominent. TDE supplants cBOSS, serving as the chosen dictionary classifier. Instead of TSF and RISE, the DrCIF method is introduced to handle the interval and frequency representations. Additionally, HC2 introduces Arsenal method, an ensemble of ROCKET classifiers.

Another notably accurate hybrid approach is The Time Series Combination of Heterogeneous and Integrated Embedding Forest (TS-CHIEF) [31]. This is a homogeneous ensemble of methods which means that hybrid features are embedded in tree nodes rather than separated in modules. In TS-CHIEF, each tree node evaluates a certain number of splitting criteria. Notably, for dictionary-based splits, the criteria are rooted in the BOSS method, while distance-based splits rely on EE, and interval-based splits draw from RISE. TS-CHIEF is distinct in its design to avoid the resource-intensive processing associated with HIVE-COTE.

III. RSAST METHOD

Although SAST demonstrated to be more efficient than STC there exist still a high complexity in the method attributed to its search space for subsequences (see Sect. III-B). Thus, we propose an improvement on SAST called Random SAST (RSAST). Through RSAST we propose randomly selecting the shapelets, taking into account certain statistical criteria. This is done by randomly selecting the starting point (t 0 ) of the subsequence from (k) randomly chosen time series (T i ) for each class. Moreover, the length of the shapelet is defined using the autocorrelation function (ACF) and partial autocorrelation function (PACF) of the time series (T i ) instead of using a pre-defined length list (l).

A. Main Ideas RSAST

The method starts with the precomputation of a list of weights which facilitates the selection of initial points for subsequences. This makes that when a starting point (t 0 ) is randomly chosen from a time series the selection prioritize the more relevant points according to this list of weights.

To compute the aforementioned list of weights, a one-way ANOVA test is executed for each time value, denoted as T i [j], with j varying from 0 to m, and m the length of the time series (refer to Algorithm 1). So the test detects distinctive starting points that exhibit statistically significant differences between classes, thereby prevents the selection of points that are inherently similar. The computation of PACF and ACF for each instance yields to a set of highly correlated lagged time points. These points are subsequently employed as potential lengths for the shapelets, utilizing the significant values obtained from each test. This approach leads to the exclusion of non-correlated points within the time series, thereby eliminating the need to exhaustively explore the complete range of potential lengths within a time series (ranging from 3 to m).

Finally, with the shapelet length determined, and utilizing the precalculated list of weights, a certain number of admis-sible starting points are sampled (without replacement) from each instance.

Thus, with these instances of reference, the possible lengths for the subsequences, and some chosen starting points, it is obtained a collection of relevant shapelet candidates (see Algorithm 2).

Additionally, given the selection of a specific amount of starting points (p), there is a upper limit, or maximum of shapelets to obtain, since the total number depends on the difference between the length of the time series and the length of the possible shapelets. Thus, this difference must be less than the required number of starting points (p > m -l + 1) in order to select all the required p values. Otherwise, if the difference is greater (p < m -l + 1), the set of possible starting points, and therefore the total number of shapelets, will be truncated. end for 11: end for 12: return S Once the subsequences have been generated, the followed stages of the algorithm involves computing distances between the shapelets and the time series. Thus, after the transformation is completed, a classifier is trained using the newly transformed dataset.

After the training of the model a post hoc method can be applied to interpret the results [32]. This allows to obtain the most important features and therefore the most important shapelets of the model. The analysis of importance identify how much a feature is correlated to the target variable, so, in a linear model, the absolute value of the weight will distinguish the importance of a feature with respect to another less important [33].

For a general understanding of the method, refer to Algorithm 3, which presents a comprehensive overview of the RSAST procedure. Additionally, Figure 3 provides an illustrative summary of the RSAST method.

B. Search Space of Shapelet Approaches

The time taken by shapelet approaches, which make the extraction of subsequences from the training dataset, is primarily due to the exploration and evaluation of these subsequences. x i [j] ← dist(T i , S j ) 12: end for 13: RSAST, in particular, does not explore the entire space of possible subsequences but instead performs a sampling of them, distinguishing it from its baseline STC and SAST. For instance, compared to SAST, RSAST does not utilize all potential starting points for the subsequences along the time series due to a parameter that controls the extraction of these random points. Thus, only when this parameter is set equal to or higher than the length of the time series does RSAST consider the same number of subsequences as SAST. Similarly, since RSAST consider a reduced amount of subsequences within the randomly selected instances of the training dataset, these can be adjusted to utilize all instances and all possible subsequence lengths, enabling the method to explore the same number of subsequences as STC.

D f ← D f ∪ {(x i , c i )}
Moreover, other shapelet approaches such as FS and RDST also utilize the training dataset to select candidate shapelets. For instance, FS employs multiple SAX words for the subsequences losing information in the new representation, while RDST generates the shapelets randomly considering some parameters like the number of shapelets to generate, the possible lengths, the proportion of shapelets that use normalization and the threshold for the shapelet frequency. Lastly, LS does not search for subsequences in the training dataset; instead, it utilizes a heuristic to learn near-optimal shapelets by exploring shapelet interactions.

C. Time Complexity

The complexity analysis of RSAST starts by the analysis of the computation of the list of weights. Since the method applies an ANOVA test for each point along the n time series of length m. This is accomplished with a complexity of O(n|c|m) with |c| the number of classes. Also, similar to SAST, RSAST selects k reference time series with |c| classes, in O(|c|) steps, resulting in a total of O(k|c|) reference time series within the dataset. So, given a predetermined set of p starting points and |L| possible lengths for the subsequences, O(k|c|p|L|) shapelet candidates are randomly selected. Therefore, in the worst scenario when |L| reach the maximum possible values m, the shapelet selection process has a complexity of O(k|c|pm).

Additionally, for the transformation step the method requires O(k|c|pm) distance computations over the O(n) time series with O(m) arithmetic operations, culminating in a time complexity of O(k|c|pnm 2 ).

Moreover, ACF and PACF tests are done in O(k|c|mlog(m)) and O(k|c|m 3 ) steps, respectively, when using ACF with Fast Fourier Transform and PACF with Ordinary Least Square regression.

Therefore, the total time complexity of RSAST is

O(n|c|m) + O(c) + O(k|c|mlog(m)) + O(k|c|m 3 ) + O(k|c|pm)+O(k|c|pnm 2 )+O(classif ier). Hence the overall complexity of RSAST is O(nm 2 ) + O(classif ier).

IV. EXPERIMENTS

RSAST was implemented in the Python programming language. The implementation was developed under SAST framework, following the scikit-learn design principles (URL: Repository RSAST). The repository contains the outcomes for the experimentation of the method.

A. Accuracy

In the following section, the results are presented in terms of accuracy, with a comparative analysis of RSAST against the original SAST algorithm and STC. Additionally, a comparison is provided between RSAST and other shapelet-based techniques like Fast Shapelet (FS) [START_REF] Rakthanmanon | Fast shapelets: A scalable algorithm for discovering time series shapelets[END_REF], Learned Shapelet (LS) [START_REF] Grabocka | Learning time-series shapelets[END_REF] and Random Dilated Shapelet Transform (RDST) [START_REF] Guillaume | Random dilated shapelet transform: A new approach for time series shapelets[END_REF]. Finally, a comparison is made between the proposed algorithm and some ensemble methods comprising state-of-the-art techniques like HIVE-COTE, TS-CHIEF, and ROCKET.

During the experiments the supervised classifier employed within RSAST is the Ridge classifier, likewise to ROCKET. So it is utilized the Ridge Classifier with Leave-One-Out (LOO) cross-validation for scenarios where the transformed dataset contains more features than instances. In cases where the opposite holds true, a Logistic Regression classifier is utilized. All the parameters for the classifiers are left at their default values and are not fine-tuned.

In addition, we employed the Wilcoxon significance test with a significance level of 0.05 to make the comparison of accuracy among the methods. So in order to visualize this, a critical difference diagrams were constructed following the methodology proposed in [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF]. These plots show the average ranks across all datasets and visualize them on a line, grouping classifiers into cliques where there exists no statistically significant difference in rank.

The experiment was run on an AMD EPYC 7763 64-Core Processor with 256 CPUs. The experiment encompassed the utilization of 128 datasets obtained from the UEA & UCR repository [35], employing the default training and test set provided by the repository. Furthermore, for specific comparative analyses involving other methods, RSAST was run with 10 resampling iterations, covering the same 128 datasets as before. This approach aimed to comprehensively evaluate RSAST's performance across different scenarios and datasets.

After evaluating the performance of RSAST by varying the hyperparameters of the method (k instances per class and p starting point) we set this values to k = 10 and p = 10. Increasing the number of instances did not yield a significant improvement in accuracy but exponentially increased the method's execution time. Also with this number of instances reduces the variability in accuracy that could lead to chose just one instance per class.

The outcomes for SAST were taken from the SAST original paper (72 datasets). While the results for the remaining methods were taken directly from the UEA & UCR webpage (85 Bake Off datasets) for the default train/test results as well as the resampled results.

1) Comparison RSAST, SAST and STC: We evaluated and compared RSAST in terms of accuracy against the original SAST algorithm altogether STC and 1-nearest neighbour with dynamic time warping (1NN-DTW) as a benchmark method. For the results of SAST there are 72 results from the original paper using the default train/test split from the UCR archive, which corresponds to 56 datasets from the 85 Bake Off [36]. Similarly, the results from STC correspond to the 85 Bake Off datasets from the UEA & UCR webpage with the default train/test results, leading to a comparable dataset of 56 datasets for further analysis.

Fig. 4, provides a visualization of the relative ranks of each method. Thus, it is observed that RSAST outperforms the accuracy of the TSC benchmark 1NN-DTW. Also, as it is showed by the clique in the critical difference diagram, RSAST achieves a similar level of accuracy to SAST and STC. So, RSAST attains comparable accuracy to its baseline counterparts while being faster to train. 2) Comparison RSAST and Shapelet Methods: For this section, we compared shapelet methods based on the availability of results in the UCR Repository [35], or using well- Hence, the comparison among shapelet methods includes Fast Shapelet (FS), Learned Shapelet (LS), Random Dilated Shapelet Transform (RDST), and the benchmark 1NN-DTW. In the case of RSAST, this is evaluated using 128 datasets from the UCR archive with 10 resamples. For the rest of methods the available results corresponds to the 85 Bake Off datasets. Consequently, the results are computed for the 85 datasets of the evaluation of RSAST in the Bake Off.

So, Fig 6 illustrates that RSAST outperforms FS and the benchmark method. Moreover, RSAST demonstrates a similar level of accuracy to LS. However, when comparing RSAST and RDST, the latter method performs better in most of the datasets. Some datasets exhibit substantial variations in results among shapelet approaches. For instance, in ElectricDevices and Lightning7, RSAST surpasses FS, with scores of 0.82 compared to 0.29, and 0.75 compared to 0.15, respectively. Additionally, RSAST outperforms LS significantly in the OliveOil dataset, achieving a score of 0.87 compared to 0.17. However, RSAST shows notably lower performance in the ShapeletSim dataset, compared to the rest of shapelet methods recording an accuracy of 0.48 compared to 1.0, 0.93, and 0.99 for FS, LS, and RDST, respectively.

3) Comparison RSAST and Other Categories: For this comparison we employed the most representative methods, previously introduced, from each category along with RSAST.

Therefore, specifically, we used Time Series Forest (TSF) for interval-based methods, Elastic Ensemble (EE) for distance-based methods, and Bag of Symbolic Fourier Approximation Symbols (BOSS) for dictionary-based methods. Similar to the shapelet methods comparison, we used the 128 results for RSAST with 10 resampling, but this time narrowed to 83 results of BOSS from the UCR webpage. As a result, the comparison against RSAST it is computed for a total of 83 datasets.

The mean rank (see Fig 8) for each of these methods shows that BOSS is the most accurate, followed by RSAST. However, RSAST is not significantly worse; in fact, it is comparable in terms of accuracy with all the methods. Lastly, the distance-based method (EE) and the interval-based method (TSF) present similar accuracy. 4) Comparison RSAST and SOTA methods: Similarly, as with shapelet methods, RSAST is compared with other stateof-the-art algorithms that are based on many type of features, sometimes including shapelets. For instance, some ensemble methods are included for the comparison such as: HIVE-COTE v1.0 which uses interval, dictionary, shapelet and spectral base features; TS-CHIEF which uses distance, dictionary and spectral base features; and ROCKET which extracts different The results indicate that RSAST appears to be less accurate than ROCKET, HIVE-COTE and TS-CHIEF (see Fig 10). However it is important to notice that RSAST is a single feature approach whereas in the ensemble methods there are many features used to make the classification. Moreover, the majority of these ensemble methods function as black box models, making it impossible to discern how the classification of time series is performed. In contrast, RSAST employs shapelets for this task, providing clarity in the classification process.

B. Scalability

The scalability assessment of RSAST followed a methodology similar to that of SAST, so we compared the training time of the models with respect the time series length and the number of time series within the dataset. So, for the length method in RSAST, we used the ACF&PACF criteria, varying the number of instances across 1, 10, while the number of random points ranged between 10 and 30. Additionally, we evaluated the most scalable methods, to our knowledge, like the original SAST algorithm, ROCKET, and RDST.

The experiments were performed using RSAST integrated with logistic regression for the section focused on increasing the training set size (Section IV-B1). However, in relation to the time series length, the experiments were conducted in conjunction with a ridge regression classifier (Section IV-B2).

Both experiments (time series length and training set size) were carried out locally utilizing an Intel Core i5-4300U processor. Also, in order to better show the results we re-scale the training time in a logarithmic scale.

1) Training set size:

To assess the scalability of the method concerning the training set size, a random oversampling of the Chinatown dataset was performed. Instances were selected with replacement from the original dataset within the range of The results are presented in Figure 12, showcasing the performance of the various tested approaches. Notably, RSAST demonstrates good performance compared to the other approaches. Specifically, as it is shown in Table I, RSAST with 1 instance and 10 random points exhibits the best time performance, taking only 0.3s, for 1024 instances. Additionally, RSAST with 10 instances, and 10 random points took 3.84s for the same number of time series.

It is noteworthy that ROCKET is the method that experiences the most significant increase in total training time as the number of time series (TS) rises, going from 0.97s to 7.79s for 16 and 1024 instances respectively.

The SAST approach, using a logistic regression classifier, took 3.1s for 1024 instances mirroring the tendency observed with RDST as the number of instances grows.

Lastly, RDST achieved a training time of 5.97 seconds for 1024 instances, showing similarity to RSAST with 10 instances and 10 random points. Figure 13, provides a visual representation of the escalating computation time exhibited by the various methods as the time series length grows. Notably, as it is shown in Table II, the SAST approach exhibits the highest training computation time, going from 0.87s with instances of length 32 to 18 hours, 45 minutes, and 48.02 seconds with instances of length 1024. On the other hand, RSAST, with 10 instances and 10 random points, took 38 minutes, and 1.96 second for time series of length 1024.

Furthermore, RDST and ROCKET emerges as the most scalable method, followed by RSAST with 1 instance and 10 random points, taking a training times of 12.45s, 7.96s and 3 minutes 15.76s, respectively for time series of length 1024.

C. Interpretability

Similar to the primitive approach [18], and the rest of shapelet approaches within the literature, the predictions made by RSAST can be interpreted through the identification and visualization of the selected shapelets.

Thus, for our method, this is done by the application of feature importance analysis, as in SAST. In this process, each feature is linked to a shapelet candidate extracted from a time series. The shapelet candidates that correspond to the most significant features are regarded as the top-performing shapelets.

Additionally, it is important to note that the class label associated with any given shapelet candidate is derived from the class of the time series from which it was originally extracted. So, the class label of a new time series can be obtained by using the class labels of the shapelet candidates to which it is the most similar.

Thus, RSAST predictions uses the significance of each feature, determined by the absolute value of its corresponding learned weight. So, as depicted in a example of the Coffee dataset from the UCR archive (see Figure 14), the extracted shapelets spanning short subsequences, from 13 points (feature 3), and larger shapelets with a length of 78 points (feature 1). Fig. 14: Shapelets for RSAST using Coffee dataset Moreover, Figure 15 illustrates the top 3 best shapelets extracted by RSAST, plotted on the reference time series, for the Coffee dataset. The top rows of the figures correspond to the reference time series selected from class 0, while the second rows represent the reference time series selected from class 1. A perfect match between a shapelet candidate and a reference time series implies that the shapelet has been extracted from that particular reference time series. Thus, in this case, the feature 1 is learned from class 0, while the feature 2 and 3 are learned from class 1. This visualization offers insights into the discriminatory patterns learned by RSAST for distinguishing between the two classes of the dataset. The Scalable and Accurate Subsequence Transform (SAST) is a state-of-the-art technique that makes use of these representative subsequences to train a classifier. However, despite its accuracy, SAST faces challenges in terms of scalability, particularly when dealing with longer time series.

Thus, in order to enhance the computational efficiency of the algorithm we proposed Random SAST (RSAST) a method that generates shapelets randomly, guided by certain statistical criteria, reducing the search space of shapelets.

RSAST demonstrates competitive accuracy when compared to other shapelet-based techniques, as well as against various state-of-the-art approaches. Moreover, its interpretability is a noteworthy feature, as it relies on the extraction of continuous subsequences from the training time series. This characteristic allows for a clearer understanding of the model's decisionmaking process.

Fig. 1 :

 1 Fig. 1: Shapelets for RDST using Coffee dataset.

Fig. 2 :

 2 Fig. 2: Top 3 shapelets, on TS, learned by RDST on Coffee dataset.

Algorithm 1 for c in classes do 7 :

 17 CalculateWeights Require: Dataset: D 1: classes ← uniqClasses(D) 2: weights ← [] 3: n, m ← size(D) 4: for i ← 1 to m do statsP erClass ← statsP erClass ∪ {(T c [i], c)} pV alue ← AN OV A(statsP erClass) 10: weights[i] ← 1 -pV alue 11: end for 12: return weights Then, analogous to the initial SAST algorithm, k instances per class are drawn (without replacement) from the training dataset. So, the autocorrelation function (ACF) and the Partial Autocorrelation Function (PACF) are applied to each of these selected instances.

Algorithm 2 generateRandomShapeletCandidates

 2 Require: Dataset: D, Length list: L, Random Points: p, Weights: W 1: S ← ∅ 2: n, m ← size(D) 3: for i ← 1 to n do 4: rP oints ← [] 5: for l in L do 6: rP oints ← randomlySelectP oints(T i , W, p) 7: for j in rP oints do 8:S ← S ∪ selectSubsequence(T i , j, l)

Fig. 3 :

 3 Fig. 3: Overview of RSAST method.

14 : end for 15 :

 1415 clf ← trainClassif ier(C, D f ) ▷ train the classifier on the transformed dataset 16: return (clf, S) As a result, reducing the number of shapelets can substantially decrease the overall training time of the method.

Fig. 4 :

 4 Fig. 4: Critical difference diagram between RSAST, SAST, STC and the benchmark 1NN-DTW

  Fig. 5: Pairwise comparison of RSAST against SAST, STC and 1NN-DTW

Fig. 6 :

 6 Fig. 6: Critical difference diagram between shapelet approaches and the benchmark 1NN-DTW.

Fig. 8 :

 8 Fig. 8: Critical difference RSAST with other categories

  Fig. 7: Pairwise comparison of shapelet approaches

Fig. 10 :

 10 Fig. 10: Critical difference diagram SOTA algorithms

Fig. 11 :

 11 Fig. 11: Pairwise comparison with SOTA methods

  Fig. 12: training time versus training set size 2) Time series length: To evaluate the scalability of the method in terms of the time series length, the HouseTwenty dataset is utilized, with time series truncated at lengths of 2 5 ,

Fig. 13 :

 13 Fig. 13: Training time versus time series length

Fig. 15 :

 15 Fig. 15: Top 3 shapelets, on TS, learned by RSAST on Coffee dataset.

TABLE I :

 I Summary training time versus training set size 2

6 , 2 7 , 2 8 , 2 9 , and 2 10 . A Ridge Classifier was employed for all the methods (RSAST, SAST, RDST and ROCKET).

  : min shapelet length=3 max shapelet length=m 0.87s 18h 45m 48.02s

			Length
	Method	32	1024
	RSAST: n random points=10 nb inst per class=1	0.05s	3m 15.76s
	RSAST: n random points=10 nb inst per class=10	0.24s	38m 1.96s
	RSAST: n random points=30 nb inst per class=1	0.07s	4m 26.37s
	RDST: n shapelets=10 000	0.04s	12.45s
	ROCKET: num kernels=10 000	0.48s	7.96s

SAST

TABLE II :

 II Summary training time versus time series length


Results

Methods Rationale

• Evolution of total creek length -Increase in total channel length for all sites considered

Discussion

Results

Methods Rationale

Conclusions

Despite progress in design, MR schemes:

-are flatter than natural saltmarshes -have a poorer creek distribution -have more homogeneous plant distribution Future schemes would be improved by the addition of small-scale topography features: greater variety of ecological niches, better biodeiversity, may promote drainage and creek formation However creek incision is likely to be hindered by over-compacted substrate: necessity to look into below-ground processes Discussion Results Methods Rationale

-•

  New creeks tend to form in clusters around the breach area, while furthest parts of site remain empty No change in creek extent between 2003 and 2017: stabilised • Straight drainage ditches remain clearly visible • Creeks mainly found in clusters near the breach, leaving some areas empty Brandy Hole, pasture/arable, storm-breached in 1897 Discussion Results Methods Rationale MR creeks evolve towards a mature state that is very different from that found in natural saltmarshes Long-term evolution Brandy Hole, pasture/arable, storm-breached in 1897 Mossman et al. in press Journal of Ecology; Lawrence et al in prep; Brooks et al (2015) Estuaries & Coasts Importance of initial template: MR lack topography Small-scale topography also focuses run-off into preferential flow paths and promotes creek development into more sinuousSoil in MR sites altered during the agricultural phase Over-compacted substrate may prevent water circulation, root penetration within the soil, and erosional processes

Special thanks to