Keywords: Time series, classication, uncertainty, explainability, shapelet, astrophysics, transient. 3

Time series classication is one of the must studied and applied time series analysis tasks. Several methods have been proposed to perform this task accurately, eciently and sometimes in an explainable way. However, situations where the time series are made of uncertain values are still under-explored although any physical measurement is subject to uncertainty. The existing works in this elds are based on uncertain similarity measures such as DUST, MUNICH, and FOTS which have the same main limitation of not propagating uncertainty to the next step of the classication process. This behavior causes the last parts of the process to treat the data as if they were certain while they are not, leading to untrustable predictions. This thesis tackles this limitation by proposing ecient, robust and explainable methods for uncertain time series classication (uTSC). We start by proposing a general framework for uncertain time series classication which propagates uncertainty from the beginning to the end of the process. Then, we instantiate this framework using uncertainty propagation arithmetic to propose the UST model which outperformed existing uTSC models while being explainable. We continue by improving the scalability of UST by proposing the SAST and the uSAST models. SAST is a novel accurate, scalable and interpretable method that we propose for time series classication. uSAST is the extension of SAST to uTSC. We show the eectiveness our methods on simulated datasets, on state-of-the-art datasets, and on a real-world uncertain time series dataset from the astrophysics domain. The source codes and the data used in the work are all available publicly.

Résumé

La classication de séries temporelles est l'une des tâches d'analyse de séries temporelles les plus étudiées et les plus appliquées. Plusieurs méthodes performantes et des fois interprétables ont été proposées pour réaliser cette tâche. Cependant, les cas où les séries temporelles sont faites de valeurs incertaines restent sous-explorés, et ceci malgré que toute mesure physique soit sujette à incertitude. Les travaux existants dans ce domaine sont basés sur des mesures de similarité incertaine telles que DUST, MUNICH et FOTS qui partagent la principale limite de ne pas propager l'incertitude à la prochaine étape de la classication. Par conséquent, les dernières étapes du processus de classication ne sont pas conscientes du fait que les données sont incertaines et les traitent donc comme si elles étaient certaines, conduisant ainsi à des prédictions non ables. Cette thèse a pour but de corriger cette limite en proposant des méthodes ecaces, robustes et interprétables pour la classication de séries temporelles incertaines. Nous commençons par proposer un cadre général pour la classication de séries temporelles incertaines qui propage l'incertitude du début à la n du processus de classication. Nous instancions ensuite ce cadre en utilisant l'arithmétique de propagation de l'incertitude pour proposer la méthode UST qui a donné des résultats meilleurs que ceux données par les méthodes existantes de classication de séries temporelles incertaines tout en étant interprétable.

Par la suite, nous améliorons le temps de calcul requis par UST en proposant les méthodes SAST et uSAST. SAST est une nouvelle approche performante, rapide et interprétable que nous avons proposé pour la classication de séries temporelles, et uSAST est son extension aux séries temporelles incertaines. Nous évaluons nos méthodes sur des jeux données simulées, sur des données de l'état de l'art et sur un jeu de données réel provenant du domaine de l'astrophysique. Les codes sources et les données utilisés dans ce travail sont rendus disponible sur internet.

Mots clés: Série temporelle, classication, incertitude, interprétabilité, shapelet, astrophysique, objet transitoire.

Introduction

This chapter gives the motivation of this thesis and summarizes its main contributions. Whether it is in the eld of transportation [Lopez Conde & Twinn 2019, Zheng et al. 2021], medicine [START_REF] May | Eight ways machine learning is assisting medicine[END_REF][START_REF] Miller | Radar-based monitoring system for medication tampering using data augmentation and multivariate time series classication[END_REF], industry or in physics [Boone 2019, Leoni et al. 2021]. ML is used not only to assist corresponding domain experts, but also to improve how the task is done and the service quality. ML is used to make predictions and to discover new knowledge from raw data. This is made possible by the data collection capabilities that are available today and the proliferation of tremendous techniques to analyze dierent types of data including tabular, image , video, audio and time series data. Most of the time however, and specically for time series, the data are required to be precise for ML algorithms to perform well. This is not the case in every application as the data are sometimes uncertain because of many factors including noise, sensors precision, privacy preservation, and collection methods [Mazzi et al. 2019[START_REF] Abdar | A review of uncertainty quantication in deep learning: Techniques, applications and challenges[END_REF]]. Being able to analyze uncertain data is at least as important as being able to analyze certain data. The goal of this thesis is to build ML methods for the analysis of uncertain time series data. Although there are many types of uncertainty, in this work we focus on imprecision, a special type of uncertainty. There are three key properties that we would like our methods to have, namely:

Eciency: the methods should produce accurate results, uses as less resource as possible, and be competitive with state-of-the-art methods.

Robustness: the methods should be resilient to the variation of data uncertainty.

Explainability: the methods should be inherently explainable or explainable by other means.

Let us discuss these three properties in details and understand why they are important to have. Eciency is the ability of a machine learning model to achieve good performance while being trained using a small quantity of memory and computation time [START_REF] Hernandez & Brown | [END_REF]. The magnitude of small" quantity is application dependent and may vary a lot. For instance, a model that detects anomalous heartbeats should report anomalies as soon as they appear and not many hours after the patient cannot be saved anymore [Lu et al. 2022]. On the contrary, a model trained to detect plagiarism could take three hours to run. For Internet Of Things systems, which are governed by limited memory and computation power, eciency is a must [START_REF] Sliwa | LIM-ITS: Lightweight machine learning for IoT systems with resource limitations[END_REF]. In any case, it is always good to have models that are ecient as inecient ones have higher carbon footprint [START_REF] Patterson | [END_REF].

The robustness property is another important qualier of machine learning models and reects its capability of achieving similar performance on both training and new data. This property is even more important nowadays as it has been proved that machine learning models can be fooled by malicious individuals (adversaries), noisy and uncertain data [Fawaz et al. 2019a, Yang et al. 2020]. In this work, the importance of this property is emphasized by the fact that we are dealing with uncertain data.

The explainability of a machine learning model is the ability to explain its decisions, to describe its weaknesses and strengths, and to convey an understanding of how it will behave in the future [DARPA ]. Beyond understanding the model and increasing its faithfulness and adoption by humans, explainability helps in debugging machine learning models by revealing the features used by the model to make its predictions [START_REF] Ribeiro | [END_REF]]. In the case where the wrong features are used, the model can be modied correspondingly.

With these three characteristics, we would like to ensure in the rst hand that the proposed methods work correctly and do what they have been built for using acceptable amount of resources. On the second hand, we would like the proposed methods to be adopted with condence by domain experts as well as any end users.

0.2 Uncertainty, not a bad thing ! Uncertainty is ubiquitous in real life, the majority of the decisions we take everyday is based on uncertain knowledge. For instance, we choose how we dress regarding an uncertain and changing forecasting of the weather [START_REF] Slingo | Uncertainty in weather and climate prediction[END_REF]; we plan our future without having the certitude that we are going to live up to that future; we learn lot of things at school hoping that it will be useful someday in someway [Kauman et al. 2022]. There are many of such examples. Similarly, any 0.2. Uncertainty, not a bad thing ! 3 collected data is associated with an uncertainty coming from the precision of sensor used, the environmental condition of the measurement, the source of the data, and other application-dependent constraints. It is sometimes possible to reduce the uncertainty, but it cannot be completely suppressed [Taylor 1996]. Therefore, uncertainty cannot be avoided and needs to be properly taken into account in machine learning algorithms as learning from uncertain data may lead to uncertain and inaccurate predictions.

Uncertainty is usually seen as a problem, a hindrance to learning from data.

This is why it is usually handled during the preprocessing step, during which some assumptions are considered in order to get rid of uncertainty. The preprocessing of uncertainty requires domain knowledge, limiting the usability of this approach of uncertainty handling. Furthermore, assumptions made for getting rid of uncertainty actually add more uncertainty in the process as they are based on an incomplete knowledge of the system that generated the data.

Uncertainty comes with challenges for decision-making systems [START_REF] Stanton | [END_REF], but it also brings some advantages.

In particular, uncertain data can be used to model situations on which we have incomplete knowledge and on which we do not have a total control like modeling the climate change; they are more expressive and less prone to assumptions that may not hold in practice.

Learning from uncertain data has gained a lot of interest recently. For instance, there is a community working on imprecise probabilities (SIPTA [SIPTA ]) , there are international workshops organized for uncertain machine learning (Workshop on Uncertain Machine Learning [WUML 2020], Online

Learning from Uncertain Data Streams [START_REF] Olud | OLUD. Workshop on Online Learning from Uncertain Data Streams[END_REF]). For these communities, uncertainty is not a problem, but an additional input that should be taken into account in order to build more robust and trustable machine learning systems.

These systems are expected to be aware of uncertainty, should be at least as eective as if there was no uncertainty, and should be used without requiring domain knowledge.

This thesis focuses on the classication of uncertain time series. Unlike, regular/certain time series which are generated from a stochastic process assumed to be completely known, uncertain time series are generated by processes that are only partially known. Some authors have worked on uncertain time series classication (uTSC) and have proposed dierent methods to perform this task. The main component of all these works is a similarity measure for uncertain data. These measures are named uncertain similarity measures [Dallachiesa et al. 2012]. They take as input two uncertain time series, and output a real number representing the similarity between the two objects. We claim in this work that modeling the similarity with a real number is enough for certain data, but is not sucient for uncertain data. In fact, as the compared objects are uncertain, their similarity should also be uncertain.

Existing works have never discussed how uncertain is the similarity computed by their uncertain measures, how this uncertainty might inuence the nal prediction, and even less, how this uncertainty could be computed. In this work, we address these limitations.

Main contributions

We mentioned in the previous section that existing uncertain time series classication methods share the same limitation of not providing the similarity uncertainty.

In addition to this limitation, we identied three other lacks in the state-of-the-art of uncertain time series classication, namely the absence of published applications on real uncertain datasets and the diculty to reproduce existing works. The four main contributions that we did throughout this thesis are guided by these limitations and the key properties presented in Section 0.1. These contributions are described in the following subsections:

Contribution 1: Uncertain shapelet transform

We rst observed that with the existing uTSC approaches, uncertainty is not handled throughout the whole classication process. This is because the proposed uncertain similarities give the similarity without any information about the uncertainty on that similarity. This behavior is rstly not natural as the compared objects are uncertain. Secondly, it is misleading, as the end-user may think that the similarity between two uncertain objects is certain though it is not guaranteed. We tackled this limitation by proposing an explainable and accurate method for uTSC named UST, for Uncertain Shapelet Transform. UST is described in detailed in Chapter 2.

Contribution 2: Scalable subsequence transform Shapelet approaches are known to be accurate and interpretable. However, they are computationally expensive. In this thesis, we proposed a new design of shapeletbased TSC, allowing us to signicantly improve the scalability of shapelet approaches while slightly increasing the classication performance. Our method is named SAST for Scalable and Accurate Subsequence Transform and it is presented in Chapter 3.

In Chapter 4, we extend SAST to uncertain time series classication.

Contribution 3: Real-word application

The authors of existing uTSC methods have limited their experiments on datasets with simulated uncertainties. This observation may question the usability of these methods in real world. In this thesis, we applied our method on real uncertain time series dataset. As described in Chapter 4, our method achieves good classication performance while being interpretable by astrophysicists.

Contribution 4: Reproducibility

The last contribution of this thesis is that all the datasets used, including the datasets with the simulated uncertainties that we created are publicly available.

Elsewhere, the source codes of our experiments are accessible on public repositories.

We wanted to make this work easily reproducible by anyone in order to facilitate 0.4. Report structure 5 subsequent contributions to the eld of uncertain time series classication in particular, and in the eld of uncertain time series analysis in general.

Report structure

In the previous section, we gave our main contributions while specifying in which part of this report each contribution is detailed; however, we nd it clearer and more informative to present the organization of this report in a dedicated section. We organized this report in 6 chapters: Chapter 0, this one, is actually the rst and it gives this work's context, its motivations and goals, summarizes the main contributions and presents how this report is organized. A detailed background and related works of time series classication in the absence and presence of uncertainty is given in Chapter 1. For readers who are not familiar with time series classication or with uncertainty, we strongly suggest reading this chapter before the following ones as subsequent chapters use concepts described in Chapter 1. Next comes Chapter 2 which describes our rst main contribution UST. The second main contribution, SAST, is described in Chapter 3 as our proposed solution to improve UST's time complexity. Chapter 4 extends SAST to uncertain time series and details its performance on a real uncertain time series dataset. Finally, a general conclusion and some possible future directions of this work are given in Chapter 5.

Chapter 1

Background and related work

In this chapter, we give in-depth background required for understanding this work.

What is a time series

A time series is a type of data that allows the modeling of the evolution of a phenomenon through time. Dierently said, a time series is used to see how an object changes with time. A time series is formally dened as follows:

Denition 1.1 (Time series). A time series (TS) is a nite sequence of objects ordered in time.

T = (t d 1 , t d 2 , ..., t dm ), ∀j ∈ [1, m], d j ∈ D, t d j ∈ Ω, m ∈ N, m ≥ 1 (1.1)
In the previous denition, D is a totally ordered set and for any pair of integers j 1 and j 2 such that j 1 < j 2 , we have d j 1 < d j 2 . The set Ω is the domain of the objects whose evolution in time is tracked. The objects in Ω are generally of the same nature, for instance, it could be a set of numbers, images, videos, audio, text, etc. Finally, m is the length of the time series. When Ω is an ordered set, the time series can be represented as a line plot on a 2 dimensional space where the x-axis is labeled by sorted objects from the set D and the y-axis is labeled by objects from Chapter 1. Background and related work In this thesis, we consider only the case where the set Ω is the set of real numbers.

Therefore, we reduce the denition of time series to a nite set of numbers ordered in time.

Notion of uncertainty

Any measurement is subject to uncertainty, and unlike error which can be avoided by being careful, uncertainty cannot be avoided [Taylor 1996]. It can be reduced to a certain level but it cannot be eliminated. Many factors can lead to uncertain measurements including the sensitivity and the precision of the sensor used to make the measurement, the environmental conditions in which the measurement is done and the privacy preservation constraints. To make this clear, let's assume we want to know the height of a person who is 500 meters far away, we could estimate that he measures between 150 centimeters and 160 centimeters with some level of condence given our experience. The uncertainty here is due to the fact that the person is far away, and hence, it is dicult to make a more precise estimation of its height.

This uncertainty can be reduced by getting closer to the person. A more precise height can be obtained using a meter, but the precision of this measurement will still be limited by the graduation of the meter. A meter graduated in centimeter will give less precise measurements than a meter graduated in millimeter. It is dicult and even impossible in some applications to obtain the required level of certainty. Therefore, it is necessary to build ML tools that could work well despite the uncertainty in the data.

There exists two types of uncertainty: aleatoric and epistemic. Also called statistical, aleatoric uncertainty is due to the unknowns that dier each time a measurement is made. A typical source of aleatoric uncertainty is the random seed used for random numbers generation in computer science. Epistemic uncertainty, which is also called systematic uncertainty is due to things that should be known in principle, but are not in practice. The uncertainty in the measurement of a person height as described in the previous paragraph is epistemic as it is possible to measure a person height with precision using an appropriate tool. Some subtypes of epistemic uncertainty are imprecision, incompletion and unreliability. Imprecision is when there are many possible outputs for the same measurement and the exact output is unknown. An example is to give an interval in which a person height is known to be instead of a crisp real number. Incompletion is when some measurement are unknown or missing. A typical example is missing values in datasets. Unreliability is when it is not guarantee at 100% if the output of a measurement is correct or not.

Figure 1.4 summarizes the categorization of the dierent types of uncertainty that have just been described. Is it due to unknown ?

Figure 1.4: Categorization of uncertainty types of the value and the deviation is the maximal possible error on that estimate.

x = x ± δx, x ∈ R, δx ∈ R + (1.2)
Therefore, the exact value is somewhere in the interval [x -δx, x + δx].

Denition 1.3 (Multiset uncertain value

). An uncertain value can be given as a set of all the possible exact values. These values could be equiprobable or not.

x = {x 1 , x 2 , ..., x s }, ∀i, x i ∈ R, s ∈ N + (1.3)
The exact value is either one of the values in the set or a value close to one of the values in the set. . Let D = {(T 1 , c 1 ), (T 2 , c 2 ), ..., (T n , c n )} be a dataset, where each T i is a time series and c i the associated class label taken from a nite set of discrete classes C = {c 1 , c 2 , ..., c nc } (n c is the number of classes and C ⊂ N). The classication task for this dataset consists of learning a function f (also called a classier) such that:

f (T i ) = c i (1.4)
Once the function is learned, it can be applied to new time series to automatically predict their class labels. In practice, learning the exact function f is generally a dicult problem depending on the complexity of the relationship between the time series and the classes. Instead, an approximated function f , close as possible to f is learned. The quality of the approximation is measured using a loss function l which computes how far is the approximation from the exact function. One of the most used loss functions is the categorical cross entropy dened as follows: Denition 1.6 (Cross entropy). The cross entropy loss of a classier f on a given time series T i is dened as follows:

l(T i , c i ) = c i log f (T i ) (1.5)
The overall loss is obtained by averaging the losses for every time series in the dataset. Denitions 1.5 and 1.6 remain valid when the time series are uncertain. Regarding the discriminative features used to classify the data, the existing methods have been grouped in ve categories which are: whole series, interval, shapelet, dictionary and spectral approaches [START_REF] Bagnall | [END_REF]. In order to include the methods proposed subsequently, we add three other categories, namely: subsequence, hybrid and deep learning approaches.

Whole series

Whole series approaches classify time series using the k-Nearest Neighbor (k-NN) classier. In particular, a new time series is aected to the class of its rst nearest 1.2. Related work 15 neighbor. The neighborhood is dened using a distance that measures the dissimilarity between two times series. The Euclidean distance is one of the most used distances in machine learning, and time series classication is not an exception.

Denition 1.7 (Euclidean distance (ED)). Given two times series T 1 and T 2 of same length m, the Euclidean distance between them is dened as follows:

ED(T 1 , T 2 ) = m i=1 (t 1i -t 2i ) 2 (1.6)
where t 1i and t 2i are the respective values of T 1 and T 2 .

In practice, the square root can be omitted to save computation since its eect is only to change the dissimilarity scale. The main limitation of ED appears when the compared time series are not aligned, for instance when there is a time shift. To illustrate this situation, let us consider the the time series T 1 = (0, 0, 0, 2, 2, 2, 0, 0, 0, 0) and T 2 = (0, 0, 0, 0, 2, 2, 2, 0, 0, 0). It can be seen that T 2 is obtained by shifting T 1 one time step to the right. However the ED between them is not 0, meaning that this time series are not similar. The reason behind this behavior is that ED is computed assuming that the time series are naturally aligned as depicted in Figure and realign one speech signal to perfectly match another one [START_REF] Sakoe | Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition[END_REF].

The optimal alignment found using DTW is illustrated on Figure 1.8. The Euclidean distance computed with respect to this alignment is 0, meaning that these two time series are exactly the same.

Combining DT W and the 1-NN has been the state-of-the-art approach to classify time series [START_REF] Bagnall | [END_REF] a parameter called the warping window in order to reduce the computation time complexity [START_REF] Sakoe | Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition[END_REF][START_REF] Ratanamahatana | Making time-series classication more accurate using learned constraints[END_REF]]. Beside DTW, there exists other elastic distances that has been used in time series analysis, but DTW performs better. Unlike ED which has a linear time complexity, elastic distances generally have a quadratic time complexity as the optimal alignment is obtained using dynamic programming. Some pruning and early abandon techniques has been proposed to accelerate this computation [START_REF] Herrmann | Early abandoning and pruning for elastic distances including dynamic time warping[END_REF]. Given the success of ensemble techniques in machine learning, and the fact that dierent distances computes dierent dissimilarities, whole series approaches has been combined in order to improve the classication. Elastic Ensemble (EE), proposed in [Lines et al. 2018] is one of these ensemble methods. EE's time complexity has been signicantly reduced in [Tan et al. 2020] to obtain the Fast Elastic Ensemble (FastEE).

Interval

Whole series approaches assume that the whole time series is important to achieve the classication. It is said that these approaches perform classication regarding the global features of the time series. By doing so, the computational time is high. On the contrary, interval approaches hypothesize that only a limited portion of the time series are relevant for classication. For instance, consider the time series dataset on Figure 1.9. It can be realized that the classication could be done regarding only the subsequences that are inside the gray rectangles, the remaining parts of the time series do not bring more information as these parts are similar regardless of the time series' class. Interval approaches are suitable for these type of datasets.

An interval approach for time series classication works in tree steps: intervals selection, features computation, and nally, classication. Relevant intervals identication is generally done randomly or using an heuristic. The next step after the selection of relevant intervals is the computation of a set of statistics on these intervals. In particular the mean, the standard deviation, the slope, the median, etc are computed for each interval and for each time series in the dataset. The last step is the actual classication using any supervised classier on the computed statistics.

This process in summarized on Figure 1.10.

State-of-the-art methods that follow the interval based approach are the time

Shapelet

A Shapelets is a time series primitive proposed by [Ye & Keogh 2009b] as an eective and interpretable feature for time series classication. Simply said, a shapelet is subsequence (a set of consecutive values in a time series) that is characteristic of a class in a dataset. This notion is illustrated on Figure 1.11 on which the shapelets are the subsequences located in the rectangles. It can be seen that these subsequences are enough to perform the classication eectively as the green shapelets are only present in the green time series, while the blue shapelets are only present in the blue ones. Therefore, similarly to interval approaches, shapelet methods assume that only a subpart of the time series are relevant for the classication. However, unlike intervals whose locations are xed once for all, shapelets can appear at any location on the time series: shapelet are phase-independent, while interval are phase-Chapter 1. Background and related work dependent. The classication of a time series using a shapelet approach is done with respect to the similarity between the time series and the shapelets. More specically, if a time series contains a subsequence that is similar to a shapelet, then it is consider as being from the same class as the shapelet. The similarity is computed using a distance function, generally the Euclidean distance, but any distance can be also used.

A shapelet approach performs classication in three steps: shapelets extraction, shapelets transformation, and nally, the actual classication. Extracting shapelets consists in nding the top most relevant shapelets from the training set. This is done by generating all the subsequences from the dataset, then computing the information gain obtained by splitting the dataset with respect to each subsequence (the split is done by creating two groups: one containing time series that are the most similar to the subsequence, and the other containing time series that are the less similar to the subsequence). Finally, the subsequences with the highest information gain are selected as shapelets. Then comes the second step which consists of transforming the original time series dataset to a tabular dataset. This is achieved by replacing each time series in the dataset by the vector of its distances to the selected shapelets. The nal step is the training of any supervised classier on the the transformed dataset. Figure 1.12 summarizes how time series classication with shapelets is performed.

This approach is said to be interpretable since the selected shapelet are mean-

Dictionary

Shapelet, interval and whole series approaches work in the time domain as they perform classication based directly on the observed values of the time series. In some cases, this could be ineective. The dataset shown on Figure 1.13 illustrates a situation where these approaches may not be suitable. This is because the time series are made of similar subsequences with dierent frequencies depending on the time series class. Fourier Approximation (SFA [Schäfer & Högqvist 2012]) and the Symbolic Aggregate approXimation (SAX [Lin et al. 2007]). We illustrate the discretization using the example of SAX on Figure 1.14. This kind of datasets are preponderant in the eld of speech analysis. features. The eectiveness of using Fourier coecients, autocorrelation and power spectrum has been demonstrated in [START_REF] Bagnall | [END_REF]. [START_REF] Corduas | Marcella Corduas and Domenico Piccolo. Time series clustering and classication by the autoregressive metric[END_REF] used dierent supervised classiers on autoregressive features in order to perform time series clustering and classication. [Fawaz et al. 2019b]. This study includes recent advances in time series classication, but also many methods that were not considered in [START_REF] Wang | [END_REF]].

Furthermore, with the availability of more open time series datasets, this review also considered more diverse application domains. This time, ResNet signicantly outperformed the others deep learning methods, followed by the FCN. Additionally, the state-of-the-art handcrafted features method at this time, HIVE-COTE [Lines et al. 2018], achieved better classication performance compared to ResNet. HIVE-COTE will be described in the next section. Subsequently, the deep learning method InceptionTime has been proposed [Fawaz et al. 2020]. It is an ensemble of convolutional neural network models that include residual connections as in ResNet.

The state-of-the-art deep learning method for time series classication is ROCKET [START_REF] Dempster | ROCKET: Exceptionally fast and accurate time series classication using random convolutional kernels[END_REF]. It is a special kind of convolutional neural network as it uses random lters. In fact, instead of learning convolutional kernels by optimization as it is generally done in deep learning, ROCKET uses random kernels sampled from a uniform distribution. As there is no learning, this method is extremely fast. Additionally, ROCKET uses a new feature called the proportion of positive values (PPV) computed after applying the convolutions. PPV allows ROCKET to achieve comparable performance to state-of-the-art methods. An almost deterministic variant of ROCKET has been developed recently under the name MiniRocket [Dempster et al. 2021]. Another variant of ROCKET is MultiROKET which extract features from the rst order derivative of the raw time series in addition to features extracted on the raw time series [Tan et al.

Hybrid approaches

Some time series datasets simultaneously contains whole series, shapelet, interval, dictionary and spectral features. In this situation, using a single type of feature to perform the classication leads to poor performance. Moreover, it would be benecial to have a method than could perform well on any dataset. Hybrid approaches has been proposed to tackle these challenges. The main idea is to extract every type of features, then use a strategy to merge the predictions from each feature type to obtain the nal prediction. For instance, the Random Interval Spectral Ensemble (RISE [Lines et al. 2018 STC, TDE, ROCKET and CIF.

The most important limitation of HIVE-COTE is the computational time which is in the order of O(n 2 m 4 ) for a dataset of n time series of length m. This limitation is solved in practice by searching shapelet for a given amount of time only. Although this works well in practice, there is no guarantee that some interesting shapelets will not be missed by the algorithm. The Time Series Combination of Heterogeneous and Integrated Embedding Forest (TS-CHIEF [START_REF] Shifaz | [END_REF]) combines whole series, interval and dictionary features in a forest of trees fashion in order to reduce the variance, increase the classication performance, while reducing the computational time. The authors did not include shapelet features because they are computationally expensive. TS-CHIEF achieves performance comparable to the rst HIVE-COTE version while being much more scalable. However, the second HIVE-COTE version is signicantly more accurate than TS-CHIEF.

Summary of time series classication approaches

It can be realized by looking carefully at the existing time series classication approaches that they follow the same pattern to perform classication. In fact, each approach works in three main steps: features extraction, feature transformation, and nally classication. This process is summarized in Figure 1.16 and is described as follow: Given a dataset of time series with their class labels, a feature extractor is used to extract relevant features (shapelets, intervals, words, articial neural network (ANN) weighs, etc), then the input dataset is transform with respect to the Chapter 1. Background and related work extracted features (shapelet transformation, interval transformation, histogram, forward pass for ANN, etc), and nally, a supervised classier is trained on the obtained tabular dataset. The feature transformation is performed using the function v(T, f ) which computes the values of the feature f for the the time series T . This function is the distance function in shapelet and whole series approaches, it is the statistic functions (mean, standard deviation, median, etc) for interval approaches, it is the count for dictionary approaches, it is the correlation for spectral approaches, and it is the forward pass for deep learning approaches. We synthesized the existing methods for time series classication in Table 1.1.

The rst two columns respectively indicate the category and the features that are used for classication. The last column gives some state-of-the-art methods in the corresponding category. The third column indicates the type of explainability, which is either absent when the method is not explainable, by design when the method is explainable right after training without using any additional tool, and post hoc when the method is explainable after the training by using additional techniques such as LIME [START_REF] Ribeiro | [END_REF] and SHAP [Lundberg & Lee 2017]. Note that although post hoc explainability methods such as LIME and SHAP are model-agnostic, and thus are applicable to any method, there is no theoretical guarantee that the result will be meaningful to the end-users.

Uncertain time series classication approaches

Existing uncertain time series classication (uTSC) approaches are inspired from regular time series classication (TSC) approaches. The general idea is to take uncertainty into account in an existing TSC approach by the means of some adap- small. Moreover, it does not compute a probability on the similarity, but the similarity itself. DUST assumes that the imprecision in the time series follows a normal distribution. N_DUST is a DUST variant that assumes the best estimate to be normally distributed while U_DUST considers uniform distribution.

Denition 1.8 (DUST). The DUST similarity is dened as follows:

U _DU ST (T 1 , T 2 ) = l 1 t 1,i -t 2,i 2σ i 2 (1.7) N _DU ST (T 1 , T 2 ) = l 1 t 1,i -t 2,i 2σ i (1 + σ 2 i ) 2 (1.8)
where σ i is the uncertainty at time step i.

Since DUST requires the compared values to have the same uncertainty, we Denition 1.9 (FOTS). The FOTS similarity is dened as follows:

consider σ i = max(δt 1,i , δt 2,i ) in
F OT S(T 1 , T 2 ) = l i=1 k j=1 (U 1 -U 2 ) 2 ij (1.9)
where U 1 and U 2 are the k rst Eigenvector matrices of the local auto-covariance matrices of T 1 and T 2 respectively.

The local auto-covariance at timestamp t of a time series T is computed using M sliding windows of size w as follows:

Γ t (T, w, M ) = t τ =t-M +1 T τ,w ⊗ T τ,w (1.10)
where T τ,w is the subsequence of length w from T and which starts at timestamp τ . ⊗ is the outer product operator.

DUST, MUNICH, PROUD have been compared against each other on some time series analysis tasks such as querying and classication [Dallachiesa et al. 2012]. In the same work, the authors proposed the uncertain moving average (UMA), a moving average strategy for uncertain time series.

We have noted four main limitations in the existing works on uncertain time series:

1. First, existing similarity measures give the similarity between two uncertain time series as an exact similarity without any uncertainty information. Since the compared objects are uncertain, it is natural to expect the similarity between them to have some uncertainty. Elsewhere, since the existing measures do not give the uncertainty on the similarity, the classier cannot be aware that the input data are uncertain. Likewise, the result of applying UMA is provided without the associated uncertainty, 2. second, except FOTS which has been proved to be more robust for clustering uncertain time series than Euclidean distance, the other uncertain measures have not been proved to be more eective compared to any exact distance that ignores uncertainty. This opens a question: are the existing uncertain similarity measures really necessary/useful? 3. third, the existing uncertain similarity measures have never been applied on real uncertain time series datasets, but always on exact time series on which random uncertainty have been added, 4. Finally, the synthetic uncertain time series data on which the existing methods have been tested are never provided, making it dicult to reproduce or verify the published results.

The Uncertain Euclidean Distance (UED) that we are proposing in Section 2.2 is a solution for the rst aforementioned limitations. This thesis mitigates the second limitation by giving a comparison of DUST, which is to our knowledge the stateof-the-art uncertain measure, to Euclidean distance. In addition, we also consider FOTS and UED in this comparison. We apply these measures on synthetic datasets, but also on PLAsTiCC, an astronomical dataset of time series with real uncertainty [START_REF] Allam | The photometric LSST astronomical time-series classication challenge (PLAsTiCC): Data set[END_REF]. Finally, we share the source code, datasets and results of our experiment on a public repository to encourage reproducibility and re-usability.

As mentioned earlier, the existing methods are based on the combination of a similarity measure with a 1-NN classier and it has been shown that this approach is signicantly less eective than approaches that extract local and/or global features on which classication is then performed [START_REF] Bagnall | [END_REF]. The UST and uSAST methods, which we respectively propose in Chapter 2 and Chapter 4 are based on shapelet features which are known to be very competitive for exact time series classication when tested on the UCR archive [Dau et al. 2019]. Beside giving accurate classication, shapelet features provide an inherent and easy explanation of the predictions [START_REF] Hills | Classication of time series by shapelet transformation[END_REF].

Figure 1.17 summarizes existing uncertain time series classication methods.

Because the existing uncertain similarity measures do not provide the similarity uncertainty, the brutal disappearance of the uncertainty at the very beginning of the classication process can be observed, misleading the remaining part of the process to wrongly believes that the input data is certain. In the next chapter, we follow our proposed design by propagating uncertainty in the euclidean distance in order to obtain the uncertain euclidean distance (UED) which allows us not only to have the similarity, but also the quantication of the uncertainty on that similarity. Subsequently, UED is used to perform uTSC classication eciently.

Chapter 2

Uncertain Time Series Classication With Shapelet Transform

Time series classication is a task that aims at classifying chronological data. It is used in a diverse range of domains such as meteorology, medicine and physics.

In the last decade, many algorithms have been built to perform this task with very appreciable accuracy.

Introduction

The last decade has been characterized by the availability of measurements in a large and variate set of domains such as meteorology, astronomy, medicine and object tracking. Generally, these measurements are represented as time series

Chapter 2. Uncertain Time Series Classication With Shapelet Transform [Dallachiesa et al. 2012], that means a sequence of data ordered in time. Time series classication is used in many applications such as astronomy, land cover classication and human activity recognition. Meanwhile, there has been an increase of the number of methods for time series classication [START_REF] Shifaz | [END_REF], Bagnall et al. 2017].

However, to the best of our knowledge, these methods do not take data uncertainty into account. Any measurement is subject to uncertainty that can be due to the environment, the mean of measurement, privacy constraints and other factors. Furthermore, even if uncertainty can be reduced, it cannot be eliminated [Taylor 1996].

In some applications, uncertainty cannot be neglected and has to be explicitly handled [START_REF] Sarangi | [END_REF].

Shapelet based methods are one of the best approaches that have been developed

for time series classication. A shapelet is a subseries that is representative for a class of time series. These methods are especially appreciated for their interpretability, their robustness and their classication speed [Ye & Keogh 2009b].

Almost every time series classication methods are built by coupling a similarity measure with a supervised classier. We follow this pattern in this chapter to build an uncertain time series classier. We are not aware of any existing method in the literature for the classication of uncertain time series.

Our contribution is as follows, we rst propose an uncertain dissimilarity measure based on Euclidean distance. Secondly we use it to build the uncertain shapelet transform algorithm, which is the shapelet transform algorithm adapted to the classication of time series with available uncertainty information.

The rest of this chapter is organized as follows: In Section 2.2, we present a new uncertain dissimilarity measure called UED, and in Section 2.3, we present the uncertain shapelet transform algorithm (UST). Section 2.4 is about experiments and Section 2.5 nally concludes this chapter.

UED: a new uncertain dissimilarity measure

As stated by [Taylor 1996], uncertainty is dierent from error since it cannot be eliminated, but it can be reduced up to a certain magnitude. Regardless of the measurement method, there is always an uncertainty and uncertain measures cannot be compared with a 100% reliability: the result of the comparison of uncertain values should also be uncertain.

From now on, we consider only PDF-based representation of uncertain values.

Let x be an uncertain value, we have x = x ± δx, the exact value of x follows a probability distribution and lies in the interval [x -δx, x + δx]. x is the best guess of the exact value of x. Let y be another uncertain value, any mathematical operator applied on x and y produces a new uncertain value. We have the following uncertainty propagation properties [Taylor 1996]:

z = x + y = (x + ŷ) ± (δx + δy) z = x -y = (x -ŷ) ± (δx + δy) z = x × y = (x × ŷ) ± ( δx |x| + δy |ŷ| ) × (|x × ŷ|) z = x y = x ŷ ± ( δx |x| + δy |ŷ| ) × |x| |ŷ| Euclidean distance (ED) is
U ED(T 1 , T 2 ) = n i=1 ( t 1i -t 2i ) 2 ± 2 n i=1 | t 1i -t 2i | × (δt 1i + δt 2i ) (2.1)
where Ti is the time series of the best guesses of T i .

The output of UED is an uncertain measure representing the similarity between the two uncertain time series given as inputs. In order to use UED to classify time series, especially with a shapelet algorithm, an ordering relation for the set of uncertain measures is needed. We propose three ways to compare uncertain measures: the rst one is the simpler one and is based on condence, the second one is a stochastic order and the last one is an interval number ordering.

Simple ordering for uncertain measures

This ordering is based on two simple properties. Let x and y be two PDF-based uncertain measures, the rst property is the property of equality and states that two uncertain measures are equal if their best guesses and their uncertainties are equals.

x = y ⇐⇒ x = ŷ ∧ δx = δy (2.2)
The property of inferiority is the second one and states that the uncertain measure x is smaller than the uncertain measure y if and only if the best guess of x is smaller than the best guess of y. In the case where x and y have the same best guesses, the smaller is the one with the smallest uncertainty.

x < y ⇐⇒ (x < ŷ) ∨ ((x = ŷ) ∧ (δx < δy))

(2.3) Unlike the property of equality which is straightforward, the property of inferiority need some explanations. Unfortunately, we don't have a mathematical justication of this property but it is guided by two points: rstly we are in some way condent Chapter 2. Uncertain Time Series Classication With Shapelet Transform about the best guess since it must have been given by an expert, and secondly we are more condent with smaller uncertainties.

Of course, these properties do not always give a correct ordering; in fact, if

x = 2 ± 0.5 and y = 2 ± 0.1 then the inferiority property says that y < x. Now, if

there is an oracle able to compute the exact value of any uncertain measure, it might says that x = 1.8 and y = 2, and thus invalidating our ordering. This observation also holds for the properties of equality.

Stochastic ordering of uncertain measures

X ≤ st Y ⇐⇒ P r[X > t] ≤ P r[Y > t] ∀t ∈ I ⇐⇒ 1 -P r[X > t] > 1 -P [Y > t] ∀t ∈ I ⇐⇒ P r[X ≤ t] > P r[Y ≤ t] ∀t ∈ I ⇐⇒ CDF X (t) > CDF Y (t) ∀t ∈ I (2.4)
CDF X (t) is the cumulative distribution function of the random variable X evaluated at t. Because the cardinality of I is innite, we discretized it as being the set of the following values:

min(I) + i × max(I) -min(I) k 0 ≤ i ≤ k and
k is a whole number to be dened.

(2.5) Unlike the simple ordering which is a total order, the stochastic ordering is a partial order. That means, the relation stochastically less than or equal to is not dened for any two random variables as the condition may not hold for every t in I, and thus, sorting some uncertain measures using the stochastic ordering is impossible. This is clearly a limitation, but we did not nd a total stochastic ordering in the literature.

Interval numbers ordering

Denition 2.1 (Interval number). An interval number i n is a number represented as an interval, that is

i n = [i l n , i u n ]
, where i l n and i u n are respectively the lowest and highest possible values of the number.

A PDF-based uncertain value is by denition an interval number, enhanced with a probability distribution in that interval. Given two uncertain values x and y, the interval number-based ordering can be estimated using the following probability [START_REF] Xu | [END_REF], Yue 2011]

: P r[x ≥ y] = max(1 -max( ŷ + δy -x + δx 2δx + 2δy
))

(2.6)

Unlike the stochastic ordering, the simple ordering and the interval numberbased ordering do not exploit the uncertainty distribution, nor the best guess given by the expert. The simple ordering required the best guess to be known, and this is not always the case in practice. If the compared uncertain values do not overlap at all, that is they do not have some possible exact values in common, all the three ordering give the same order.

Now that we know how to sort uncertain measures, let us see how to use UED to classify uncertain time series.

UST: The uncertain shapelet transform classication

In this section, we describe how to classify uncertain time series using shapelets.

Uncertain observations are represented using the probability density function model (or simply PDF model). We start by dening the concepts that are used in our algorithm, then we describe the algorithm itself.

Denition of concepts

Denition 2.2 (Uncertain subsequence). An uncertain subsequence S of an uncertain time series T is a series of l consecutive uncertain values in T .

S = Ŝ ± δS = ( ti+1 ± δt i+1 , ..., ti+l ± δt i+l ) 1 ≤ i ≤ m -l, 1 ≤ l ≤ m, m = |T | (2.7)
Denition 2.3 (Distance). The distance between a subsequence S of length l and a time series of length m is dened as follows:

Dist(S, T ) = min

P ∈T l dist(S, P ),
, where

T l = {(t i , t i+1 , ..., t i+l )| 1 ≤ i ≤ m -l + 1}
The dist(•, •) function in Denition 2.3 could be any distance metric. In practice the Euclidean Distance (ED) and the Dynamic Time Warping (DTW) are generally used. The denition is also applicable between uTS and uncertain subsequence by ignoring the uncertainty or by taking it into account using an uncertain distance, namely the UED distance.

Let D = {(T i , c i )|1 ≤ i ≤ n} be a dataset of n time series T i (respectively uncertain time series) with their class labels c i taken from a discrete nite set C such that the cardinality of C is much less than n. We can dene the notions of separator and shapelet for this dataset.

Chapter 2. Uncertain Time Series Classication With Shapelet Transform

Denition 2.4 (Separator). A separator (respectively uncertain separator) is a pair of a subsequence S (respectively uncertain subsequence) and a threshold ε that divide the dataset in two groups D L and D R such that:

D L = {(T i , c i )|Dist(S, T i ) < ε, 1 ≤ i ≤ n} D R = {(T i , c i )|Dist(S, T i ) ≥ ε, 1 ≤ i ≤ n} Denition 2.5 (Shapelet). Given a dataset D = {(T 1 , c 1 ), (T 2 , c 2 ), ..., (T n , c n )} of
time series with their class labels c i taken from a nite set of classes C, a shapelet S ⋆ is a separator that maximizes the information gain.

S ⋆ = arg max S∈W IG(D, S), with W being the set of all subsequences in D.

(2.8) Denition 2.6 (Information gain (IG)). Let D be a time series dataset and S a shapelet.

Let D L = {T ∈ D | dist(T, S) ≤ ε} and D R = {T ∈ D | dist(T, S) > ε}, then IG(D, S) = max ε∈SP ⊂R H(D) - |D L | |D| H(D L ) - |D R | |D| H(D R ) , with H(D) = - c∈C p c log p c (2.9)
H(•) is the entropy, p c is the probability of having the class c in the dataset D, C is the set of classes in D, and SP is the set of possible split points.

Shapelets have been introduced as primitives for time series classication by [Ye & Keogh 2009b]. The authors proposed a shapelet based decision tree in which each node is a subsequence and the time series arriving at a node are split in two groups such that one group contains data that are similar to the subsequence at that node, and the other group is the set of data that are not similar to the subsequence.

UST: The uncertain shapelet transform classication 37

This training is done in a top-down approach as in a classical decision tree using the information gain (IG) at each node to nd the best split.

Uncertain shapelet transform classication

Our algorithm for uncertain time series classication is an extension of the shapelet transform algorithm [START_REF] Hills | Classication of time series by shapelet transformation[END_REF].

Given a dataset D of uncertain time series, the rst step is to select the top k best uncertain shapelets from the dataset. This step is achieved using the procedure described by Algo. 1, which takes as input, the dataset D, the maximum number of uncertain shapelets to be extracted k, The next step after the top-k uncertain shapelets selection is the uncertain shapelet transformation. This step is done using Algo. 2, which takes as input the dataset D, the set of the top-k uncertain shapelets S and the number of uncertain shapelets k. For each uncertain time series in the dataset, its uncertain feature vector of length k is computed using U ED. The i th element of the vector is the U ED between the uncertain time series and the uncertain shapelet i. Because the uncertainties add up during the transformation, the uncertain feature vectors are such that the scale of the best guesses is smaller than the scale of the uncertainties.

It is very important to have everything on the same scale. The second for loop of Algo. 2 performs the standard normalization of the transformed dataset. We use D:j to represent the list of the best guesses of uncertain dissimilarities between every uncertain time series and the j th uncertain shapelet, and δD :j is the list of the Chapter 2. Uncertain Time Series Classication With Shapelet Transform If instead of U ED, one of the existing metrics from the state of the art (DUST, MUNICH, PROUD or FOTS) is used, the classier would not be able to learn while being aware of uncertainty in the input since the output of these metrics are apparently 100% reliable; most importantly, it would not be possible to take advantage of an uncertain classier.

Algorithm 1: Top-K Uncertain Shapelet Selection Input: D, k, M IN, M AX 1 begin 2 C ← ∅; Q ← ∅ 3 for i ← 1, n do 4 cands ← GenCand(T i , M IN, M AX) 5 qualities ← AssessCand(cands, D) 6 C ← C + cands 7 Q ← Q + qualities 8 end 9 S ← ExtractBest(C, Q, k)

Compared models

We have compared dierent models which are dierent congurations of the UST model. In particular, our models are built regarding the following attributes: uncertain similarity, ordering strategy, and supervised classier.

Uncertain similarity

This is how the dissimilarity between uncertain subsequences is computed by UST.

This attribute has ve possible values which are ED, UED, FOTS, U_DUST, and N_DUST.

We set the parameter of FOTS following the specications in its original paper

Ordering strategy

This is the method used to sort uncertain measures, that is simple, stochastic or interval ordering. When measures are not uncertain (when using FOTS or DUST),

we use the natural order.

For the stochastic ordering we consider an uncertain measure x to be normally distributed. Given this assumption, the following cumulative distribution function can be used

CDF X (t) = 1 2 (1 + erf ( t - x δx √ 2
))

(2.10)

where erf (•) is the Gauss error function. To discretize I (using Eq. 2.5), we xed the value of k to 100. For the interval ordering, we say that x ≤ y if P r[x ≤ y] > 0.5

Supervised classier

This is the model used to classify the transformed dataset in the last step of UST.

We used the classical Gaussian Naive Bayes (GNB) and the Uncertain Gaussian Naive Bayes (UGNB) models. We implemented UGNB following [START_REF] Qin | [END_REF]].

We chosen these classiers for their simplicity in order to evaluate UED and the importance of propagating uncertainty followed by the use of a classier that takes uncertainty into account during its training phase.

For each model, the parameter M IN and M AX are set to 3 and m -1 respectively, where m is the length of the uncertain time series in the dataset being processed. Because of the high time complexity of the algorithm, we have used a time contract to limit the execution time of each model. After the evaluation of an uncertain shapelet candidate, the next candidate is evaluated only if there is time remaining in the contract; otherwise the shapelet search is ended. Because FOTS is more time consuming than ED, UED and DUST, we set FOTS's time contract 12 times higher above the time limit of other measures.

Tab. 2.1 gives a summary of the dierent models that are evaluated and compared throughout our experiments. In order to apply the model UST(UED, GNB), Since the datasets in this repository are without uncertainty, we manually add uncertainty in the datasets listed in Tab. 2.2. Given a dataset, the standard deviation σ i of each timestep is computed. For each time series in the dataset, the added uncertainty for the observation at timestep i follows a normal distribution with mean 0 and standard deviation c×σ, where σ is randomly chosen from a normal distribution with mean 0 and standard deviation σ i . We used dierent values of c ranging from 0.1 to 2.

Results

For each of the models we compared, we have recorded the obtained accuracy, the training duration and the testing duration. These values are recorded for each level of uncertainty.

Accuracy analysis

In this analysis, UST(UED, GNB) and UST(UED, UGNB) use the interval ordering only. UED-based models are better than the others. They are even better when the uncertain naive bayes is used as classier, that is UST(UED, UGNB). We observe also that the accuracy of each model decreases when the uncertainty level increases; Uncertainty is unpredictable, and because we are dealing with it, it is dicult to identify in which uncertain situation our approach will work well. For this reason, we use dierent levels of uncertainty in our experiment, expecting to cover at most possible situations as we can. The uncertainty levels from c = 1 to c = 2 are more likely to be extreme and may not be found in a real application, but it is important to see how the model's behavior as the uncertainty becomes too large.

We manually added uncertainty in our datasets. Applying our model on a real uncertain dataset will strengthen our contribution. Nevertheless, by using dierent levels of uncertainty in our datasets, we expect to cover any real situation.

The uncertain classier we used is the uncertain naive Bayes. We choose it for its simplicity.

There are other uncertain classiers [Li et al. 2020a, Aggarwal & Yu 2009], and they can be used in UST, but we did not try them because our goal was to show how important it is to correctly handle uncertainty in the context of uncertain time series classication. We highly recommend to try other uncertain classiers when in real application.

Finally, the time contract we set during our experiments limits in some ways the discovery of more, and why not better uncertain shapelets. In fact, maybe new uncertain shapelets might have been discovered with a larger time contract.

Conclusion

The goal of this chapter was to classify uncertain time series using the shapelet transform approach. To achieve this goal, we use uncertainty propagation techniques to dene an uncertain dissimilarity measure called U ED. Similarly to shapelet transform, UST's high computation time for identifying shapelets is one the of the greatest limitations of the approach. In the next chapter, we will describe a novel design of shapelet-based classication that overcomes this limitation while keeping at least the same level of accuracy.

Key points

We proposed the Uncertain Euclidean Distance (UED) which provides uncertain similarities between uncertain time series.

We used UED to take uncertainty into account in the shapelet-based classication and proposed the Uncertain Shapelet Transform (UST).

We shown that using UED leads to better classication than using existing uncertain measures in the state-of-the-art.

Communications

Michael F. Time series classication using phase-independent subsequences called shapelets is one of the best approaches in the state of the art. This approach is especially characterized by its interpretable property and its fast prediction time. However, given a dataset of n time series of length at most m, learning shapelets requires a computation time of O(n 2 m 4 ) which is too high for practical datasets. In this chapter, we exploit the fact that shapelets are shared by the members of the same class to propose the SAST (Scalable and Accurate Subsequence Transform) algorithm which has a time complexity of O(nm 3 ). SAST is accurate, interpretable and does not learn redundant shapelets. The experiments we conducted on the UCR archive datasets shown that SAST is more accurate than the state of the art Shapelet Transform algorithm while being signicantly more scalable.

Introduction

Time series classication with shapelets is accurate, robust to noise and interpretable [Ye & Keogh 2009b]. In particular, the shapelet transform algorithm is known to be among the most eective when tested on the UEA & UCR archive [START_REF] Bagnall | [END_REF]. Shapelet have also been proved to be eective in time series clustering [START_REF] Fotso | [END_REF], showing how useful shapelets are. The interpretability of a shapelet method is obtained by visualizing the subsequences that triggered the class label of a given instance. Since the introduction of time series classication using shapelets, one of the major limitations of the developed algorithms is their time complexity. In fact, the state-of-the-art time complexity of shapelet based methods is n 2 m 4 where n is the number of time series in the dataset and m is the length of the longest time series. This high time complexity is due to the large number of shapelet candidates that need to be evaluated in order to nd the top best shapelets.

A human brain is able to recognize a lot of variations of an object after seeing a single variant. For instance, we are able to recognize any model of car after seeing one of them, we can recognize many species of dog if we have ever seen a dog. This ability is called core object recognition [START_REF] Dicarlo | [END_REF]]. Inspired by this amazing behavior of our brain, we claim that a shapelet model should be able to recognize any variant of a shapelet if it knows one or a few number of its variants. Simply dened, a shapelet is a pattern that is shared by the time series that belong to the same class. Therefore, any single instance of a class should contain all the shapelet or at least a variant of each shapelet for that class. Guided by this observation, we propose the Scalable and Accurate Subsequence Transform (SAST) algorithm, a time series classication algorithm that is accurate, scalable and whose predictions are interpretable.

Existing shapelet based methods use the whole dataset to generate shapelet candidates, then use information gain to select the top best shapelets before doing the classication using a supervised classier. We claim that it is not necessary to generate the shapelet candidates from the whole dataset, only one or few instances per class is enough. We also claim that pruning shapelet candidates without taking into account the classier can lead to inaccurate classication. We propose the SAST model to support our claims ; it uses only a single instance per class in order to generate shapelet candidates. Furthermore, shapelet candidates are not assessed beforehand of classication. The supervised classier automatically identies the top best shapelets during its training phase. The key points of our contribution are the following:

We introduce the core shapelet recognition task which aims to recognize any variant of a shapelet from one or few variants of that shapelet. We claim that time series classication by shapelets is a core shapelet recognition task and therefore the size of the shapelet space is considerably reduced without losing crucial information.

SAST: Scalable and Accurate Subsequence Transform 49

We propose the SAST method, which successfully performs the core shapelet recognition task in order to accurately classify time series. SAST is also more scalable than the state of the art shapelet methods. In particular, SAST took 1 second to classify the Chinatown dataset with an accuracy of 96%, while the state of the art shapelet based algorithm STC took 51 seconds and achieved an accuracy of 97% on the same computer. Furthermore our proposed method can successfully classify some datasets on which STC fails.

The rest of this chapter is organized as follows: In Section 3.2 we describe our proposed method SAST, which is inspired by the core object recognition capability of human brain. In Section 3.3, we assess SAST on various datasets and compare it to state of the art shapelet and non-shapelet based methods. Section 3.4 summarizes this work and presents future direction.

SAST: Scalable and Accurate Subsequence Transform

In time series classication, a shapelet is ideally a pattern that is shared by every instances 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 n time series of length m is O(nm 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. Finally we present a novel method for shapelet based time series classication.

Reducing the number of shapelet candidates

Human brain eortlessly performs core object recognition, the ability to recognize objects despite substantial appearance variations [START_REF] Dicarlo | [END_REF]. This gives human the capability to recognize a vast number of objects that have the same name just by seeing a few of them. [START_REF] Heeger | [END_REF]] used Figure 3.1 in his lecture notes on Perception to illustrate the notion of invariance in recognition. This gure shows dierent ducks. Some are in water while others are not, some ducks are photographs and other are drawings. Furthermore, the ducks have dierent sizes, colors, etc. Despite all these variabilities, a human brain that has already seen a duck is able to recognize that each object on this gure is a duck.

A shapelet is a pattern, a shape that is common to time series that have the same class label. By common, we do not mean that these time series have exactly that shapelet, but they have a pattern that is very similar to the shapelet. Any pattern that is similar to a shapelet can be considered as a variant of that shapelet. Proof. Let's assume that classes in D are distinguishable using shapelets and that there exists a shapelet shp for the dataset D that is not similar to any time series in the set D c . Since D c contains at least a time series of each class in D, any shapelet for the dataset D must be similar to at least one time series in D c . It follows from there that assuming shp to be a shapelet is wrong. Therefore the statement is true.

From the previous proposition, any shapelet shp of D is always similar to a pattern in D c . Therefore, a shapelet algorithm that generated shapelet candidates from D c can achieve the same accuracy as if D was used. We run the shapelet transform algorithm (STC) [START_REF] Hills | Classication of time series by shapelet transformation[END_REF] on the Chinatown dataset and plotted the top 5 shapelets that have been selected for each class on Figure 3.4. The shapelets on the rst row clearly identify the valley at the beginning of time series in class 1.

Although they are coming from dierent time series, they are very similar in shape.

Likewise, the shapelets on the last row identify the at starting of instances in class 2. Generating shapelet candidates from the whole dataset makes STC learns dierent variants of the same patterns. The variations are in terms of starting position, length and shape. By applying proposition 3.2.1 in the STC algorithm, we introduce STC-k, a variation of the STC algorithm that uses at most k time series from each class to generate the shapelet candidates. Hence, for a dataset with c classes, the number of shapelet candidates to be evaluated in STC-k is O(ckm 2 ) unlike STC in which O(nm 2 ) need to be evaluated. Algorithm 3 is an outline of the STC-k algorithm.

The only dierence with STC is that the size of the shapelet space can be controlled by the parameter k. For a more detailed description of the algorithm, the reader should refer to the original STC's paper [START_REF] Hills | Classication of time series by shapelet transformation[END_REF].

By default, the length_list parameter is the set {3, 4, ..., m}, where m is the length of the time series in the dataset. min_ig 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. 2020a] stated that in one hour of searching per dataset, the result is not signicantly worse than the full search.

Let D f = {(x 1 , c 1 ), (x 2 , c 2 ), ..., (x n , c n )} be a dataset such that x i = [x i:1 , x i:2 , ..., x i:|S| ],
where x i:j = dist(T i , S j ). If the j th feature is an important feature given by the analysis of feature importance for the dataset D f , then S j is a shapelet for the dataset D.

Proof. Let's suppose the j th feature is an important feature, and that S j is not a shapelet for the dataset. By denition 2.5, not being a shapelet means that the information gain of S j is not high enough, and whether a time series T is similar or not to S j does not give any clue about the class of T . Therefore, knowing dist(T, S j ) doesn't help to classify T . In other words, the j th feature is not correlated to 54 Chapter 3. Scalable and Accurate Subsequence Transform for TSC the target variable. Hence, it cannot be an important feature. This proves the statement.

The importance of a feature in a tree based algorithm determines how much it reduces the variance of the data compared to the parent node [START_REF] Dash | Feature selection for classication[END_REF], Molnar 2020]. This corresponds exactly to the denition of a shapelet (see Denition 2.5). In a linear model, the absolute value of the weight of an important feature will be greater than the one of a less important feature [Molnar 2020]. Classiers such as decision trees and linear models are said to be inherently interpretable since a post hoc analysis is not required to interpret their predictions. More generally, when a classier is tted, a post hoc explainer can be used to nd most important features [START_REF] Murdoch | [END_REF] The classication 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 classier (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 classier. For inherently interpretable classiers such as decision trees, the importance of each feature is computed while tting the classier. For other classiers, eventually not inherently interpretable, an existing post hoc explainer such as LIME [START_REF] Ribeiro | [END_REF]] can be used to nd the importance of each feature.

A pseudo code of the SAST algorithm is given by Algorithm 4. SAST takes as input the time series dataset D, the number k 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 nally the supervised classier C that is going to be trained on the transformed dataset.

SAST time complexity

Each step of the SAST algorithm runs in a nite amount of time, therefore the algorithm always terminates. Selecting k reference time series is done in O(c) time complexity, c is the number of classes in the dataset. There are m -l + 1 subsequences of length l in a time series of length m. The total number of subsequences for a time series is m(m+1) 2

. Since there are kc reference time series in a dataset with c classes, generating all shapelet candidates is done in O(kcm 2 ). The transformation step requires O(nm 2 ) distance computations, each of which requires O(l) (l is the length of the subsequence) point wise operations. As the maximum subsequence length is m, the time complexity of the transformation step is O(nm 3 ). Therefore, to total time complexity of SAST is O(c) + O(kcm 2 ) + O(nm 3 ) + O(classif ier), where O(classif ier) is the time complexity of the classier used. The overall asymptotic time complexity of the SAST algorithm is therefore O(nm 3 ) + O(classif ier).

SAST is much faster than the state of the art shapelet transform algorithm (STC) 56 Chapter 3. Scalable and Accurate Subsequence Transform for TSC [START_REF] Hills | Classication of time series by shapelet transformation[END_REF]] which time complexity is O(n 2 m 4 ) + O(classif ier).

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 dicult 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 [Breiman 1996] to leverage these possible issues and we call the obtained model SASTEnsemble (or SASTEN in reduced form). SASTEN is obtained by ensembling r SAST models. Each individual model in the ensemble uses randomly selected reference time series and may also have dierent parameters, especially the parameters controlling the length of shapelet candidates (that is length_list in Algorithm 4). The nal prediction is obtained by averaging the predictions of every SAST models in the ensemble.

The time complexity of SASTEN is r times the time complexity of SAST if run sequentially. But this can be reduced using parallelization. SASTEN uses r times more memory than a regular SAST.

Experiments

We have implemented STC-k, SAST and SASTEN in Python. Our implementation is based on the scikit-learn machine learning library [Pedregosa et al. 2011]. 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 Classier) from the sktime library [Löning et al. 2019]. The source code of our experiments and all the results we discuss here are publicly available here 1 . In all our experiments, the number of reference time series per class (that is the parameter k in Algorithm 4) is always set to one. The supervised classier used in STC-k, STC and SAST is the Ridge classier with Leave-One-Out (LOO) cross validation. This classier is available in the scikit-learn library. The LOO cross validation is used to nd the best regularization parameter among 10 log spaced values ranging from -3 to 3 (these values are inspired from [START_REF] Dempster | ROCKET: Exceptionally fast and accurate time series classication using random convolutional kernels[END_REF]).

The other parameters are left to their default values and are not ne tuned.

We have also used the Random Forest classier in SAST. For this classier all features are evaluated at each node to nd 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 1 https://github.com/frankl1/sast/tree/master 3.3. Experiments 57 ensemble is trained on a random subset of the training set. This classier is also available in the scikit-learn library.

We make use of the Wilcoxon signicance test with a p-value of 0.05 to compare our models. We give the result of this test as a critical dierence diagram on which models that are not signicantly dierent from each other are linked with a bold line. The code used for this test and to draw critical dierence diagrams is from [Fawaz et al. 2019b].

Table 3.1 describes the models that we use in our experiments.

We experiment using 72 randomly selected datasets from the UEA & UCR repository [Anthony [START_REF] Bagnall | The UEA & UCR Time Series Classication Repository. www.timeseriesclassification.com[END_REF]. The datasets in the repository are dierent 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 signicantly worse than the full search on the UEA & UCR archive [Middlehurst et al. 2020a], we used a time contract of one hour for each STC-k models as well as for STC.

Accuracy

In this subsection, we compare the models in terms of accuracy and we use scatter plots and critical dierence diagrams to summarized the results. However, the exact accuracy of SAST, STC and STC-k, which are the core models of this work are given in Table A.2.

STC-k results

We have evaluated STC-k on 72 datasets with dierent value of the parameters k.

We have considered STC-1, STC-0.25, STC-0.5, STC-0.75 and STC. These models are described in Table 3.1. Figure 3.7 shows pairwise comparisons of these model accuracies on the test set of each dataset.

STC is better than any STC-k on almost every datasets. 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 dierence diagram on Figure 3.8 shows that STC-0.75 is not signicantly more accurate than STC-0.5, which is signicantly more accurate than STC-0.25, which is in turn signicantly more accurate than STC-1. Therefore, STC-k accuracy increases with the value of the parameter k. All STC-k models are considerably less accurate than STC.

We have observed that, STC generally fails at classifying datasets that have few time series in the training set. In particular, STC failed to nd shapelets on the Fungi datasets. This dataset has 18 classes with one instance per class in the training set. In this particular case, STC is exactly the same as STC-1. 3.1 on the 39 datasets marked with a star in Table A.2. The rst thing to note is that SAST-Ridge is generally more accurate than SAST-RF on our datasets (Figure 3.10a). 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 default SAST model and as the pivot in our comparison.

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 dierence diagram between these four models is given in Figure 3.9.

There is no signicant dierence between the models, however the model using length_list = {7, 11, 15} is the best of all. When not clearly precised in the

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 of Figure 3.12. 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 dierence between these two models is that the Ridge classier 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 signicantly better. This is the case for the datasets Crop, ElectricDevices and Fungi. These datasets contain respectively 24, 7 and 18 classes.

It is dicult to nd 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 other to dierentiate classes, and since all the subsequences are available in SAST, this combination is automatically learned by the classier. Elsewhere SAST achieves 90% accuracy on the dataset Fungi, while The critical dierence diagram on Figure 3.13 reveals that SAST is generally more accurate that STC, but the dierence is not highly signicant. We also compare our proposal to methods that learn shapelets, namely Learning time series Shapelets or LS [START_REF] Grabocka | [END_REF] and ELIS++ [Zhang et al. 2021].

The accuracy of ELIS++, FS and LS are taken from the ELIS++ paper and we considered the same 35 datasets they used (marked with a plus sign in Table A.2). The average accuracies of these models on the 35 datasets are 0.78±0.14, 0.81±0.14, 0.83 ± 0.13 and 0.85 ± 0.14 for FS, LS, SAST and ELIS++ respectively. Pedestrian; so we excluded these 5 datasets from this comparison. Elsewhere, we believe that the comparison we are doing here is not fair since these methods are not based on only shapelet features. However, considering the no free lunch theorem [START_REF] Wolpert | [END_REF], SAST could outperform these models on some datasets and the goal of this experiment is to see how SAST stands w.r.t to these methods that are based on combination of features.

Although our model uses only shapelet features, it manages to outperform ROCKET on 5 among the 67 with 4 draws (Figure 3.16a). Elsewhere, SAST respectively outperforms HIVE-COTE and TS-CHIEF on 10 and 9 datasets among the 67 with 4 and 3 draws. Since SAST can perform better than HIVE-COTE on some datasets, replacing the shapelet module in HIVE-COTE with a SAST based model The Wilcoxon statistical test failed to reject the null hypothesis with a p-value of 0.05, meaning that these four models are not signicantly dierent on the considered 67 datasets. In fact, SAST, ROCKET, HIVE-COTE and TS-CHIEF respectively achieve an average accuracy of 0.84 ± 0.12, 0.88 ± 0.11, .88 ± 0.11 and 0.88 ± 0.12.

These average scores clearly show that SAST is comparable to ROCKET and HIVE-COTE in terms of accuracy, and in addition SAST is more interpretable as it is a shapelet based method [Ye & Keogh 2009b, Bagnall et al. 2017].

Model accuracies per dataset type

The datasets on the UEA & UCR archive are categorized in problem types. Among the 72 datasets we have experimented on, there is 1 electric device problem, 4 ECG problems, 1 High Resolution Melt (HRM) problem, 25 image problems, 9 motion recognition problems, 1 power consumption problem, 16 sensor reading problems, 7 simulated dataset problems, 6 spectrograph problems and 2 trac problems.

We would like to see the method that is more appropriate for each problem type.

However, be careful drawing too much conclusions because the number of datasets per problem type is relatively small to be representative. We compute these statistics among three groups of methods as in the previous subsections: the rst group is SAST, STC-1 and STC; the second group is SAST, ELIS++, FS and LS; and the last group is SAST, ROCKET, TS-CHIEF and HIVE-COTE. For each group and for each problem type, the percentage of times each method achieves the highest accuracy is computed. These statistics are shown as stacked bar plots with problem types on the x-axis and the number of times the highest accuracy is achieved on the y-axis. Above each bar, the number of datasets in the corresponding problem type 64 Chapter 3. Scalable and Accurate Subsequence Transform for TSC is displayed. Since more than one model can achieve the highest accuracy on the same dataset, summing the percentage in a bar could be greater than 100% and the value above a bar can be less than the bar height.

Figure 3.17 shows the percentage of times SAST, STC-1 and STC achieve the highest accuracy per problem type. STC-1 achieves the highest accuracy on the image dataset MiddlePhalanxOutlineAgeGroup and on the sensor dataset Earthquake. STC is the only method that achieves the highest accuracy for ECG and Power. Elsewhere STC seems more appropriate for simulated datasets. SAST tends to be generally the best choice for electric device, HRM, image, motion recognition, sensor and is always the best for spectrograph problems compared to STC approaches.

Figure 3.17: SAST, STC-1 and STC percentage of wins per dataset type When comparing SAST to other shapelet methods (ELIS++, FS and LS), we can see on Figure 3.18 that SAST always achieves the highest accuracy on spectrograph problems and is therefore a good choice for this problem type. Elsewhere it achieves the highest accuracy on more than 25% of image and sensor datasets. ELIS++ is more suitable for ECG, image, motion, and sensor problem types. LS is a good choice for simulated datasets.

Finally, Figure 3.19 reveals that ROCKET, TS-CHIEF and HIVE-COTE win on more datasets than SAST, but with a relatively small dierence in accuracy.

ROCKET seems to be the most promising method for ECG, motion, sensor, simulated , spectrograph and trac datasets while HIVE-COTE is a good choice for image and power datasets. TS-CHIEF is a fair option for device.

Although SAST achieves the highest accuracy than ROCKET, HIVE-COTE and TS-CHIEF on some datasets, it sometimes obtains the same average accuracy as these methods. In fact, Table 3.2 gives the mean and standard deviation of each model accuracy per dataset type. We can see that SAST achieves the same average accuracy as the state of the art methods on spectrograph and is on average relatively closed on many other data types, except device (but there is only one dataset of that type). This results emphasize the fact that SAST can achieve accuracy equal to or closed to the state of the art method accuracy while oering easier interpretability.

Scalability

The scalability of SAST based models and STC is assessed regarding two criteria:

the time series length and the number of time series in the dataset. In this experiment, the time contract is not used for STC, and therefore the full search is performed. Elsewhere, the training set and the test set are exactly the same. For each model, the time taken to t the model on the training set and then predict the test set is recorded.

Time series length

Here we use the dataset HouseTwenty from the UEA & UCR repository

[Anthony Bagnall & Keogh 2018].
It is a binary dataset of electricity usage in houses. The training set has 34 time series and of length 3000 each. We vary the series length starting at 32 and only the rst time steps up to the current length are used to train our models. More precisely, we consider the HouseTwenty dataset with time series truncated at length 2 5 , 2 6 , 2 7 and nally 2 8 . The running time of each model is given in Figure 3.20a.

For each of the four models, the running time increases with the length of time series in the dataset. However, SAST models are much more scalable than STC, and SASTEN-A is the most scalable of all, since it uses a xed number of shapelet 66 Chapter 3. Scalable and Accurate Subsequence Transform for TSC minutes to train on a dataset of 34 time series of length 64, while SAST, SASTEN and SASTEN-A take about 13 seconds, 27 seconds and 8 seconds respectively. For the same number of time series but now of length 256, STC takes a bit more than a day, while SAST, SASTEN and SASTEN-A take about 14 minutes, 26 minutes and 2 minute respectively. Therefore, even our slowest method SASTEN is 55 times faster than STC. SASTEN-A and SAST are respectively 1440 times and 102 times faster than STC.

Interpretability

The predictions of a SAST model trained on a dataset are explained by identifying and visualizing the shapelets that have been learned for that dataset. This is how the explanation of shapelet methods is given in the litterature [Ye & Keogh 2009b, Wang et al. 2020]. This is done using feature importance analysis (see Proposition 3.2.2). Each feature is related to a shapelet candidate extracted from a time series whose class label is known. Shapelet candidates related to the most important features are the top best shapelets. We say that any shapelet candidate is from the class of the time series from which it has been extracted. Therefore, the class label of a time series can be interpreted by looking at the class labels of the shapelet candidates to which it is the most similar. Let us interpret the predictions of SAST-RF and SAST-Ridge trained on the Chinatown dataset. We consider this dataset because it has only two classes and time series of length 24, it is therefore easy to visualize this dataset. However, what we are doing here is applicable to any dataset.

Since SAST-RF uses a tree based classier, information gain is used as feature importance. With SAST-Ridge, the importance of feature is given by the absolute value of the corresponding learned weight. Although feature importance is computed dierently for both models, we show that their predictions are interpretable in the same manner. In order to predict the class label of a test time series, SAST identies the most important features similar to the time series. In other words, SAST checks if the time series contains subsequences that are similar to the most important features.

Figure 3.23 shows the matches between the top 5 most important features learned by SAST-Ridge and two randomly selected test time series. We can note that the model correctly predicts the class labels. Since the top 5 shapelets learned by SAST-Ridge are from class 1, there are near perfect matches with the test instance from class 1

(see Figure 3.23 top). A near perfect match between a subsequence and shapelet candidate means that the subsequence is a variant of that shapelet candidate. No good match is found with the test instance from class 2 (see Figure 3.23 bottom).

Therefore, we have an explanation (i.e the most important features that triggered the predicted class label) of why the rst instance is predicted as coming from class 3.3. Experiments 69 1, while the second one is predicted as coming from class 2.

The same analysis is shown for SAST-RF in Figure 3.24. Like SAST-Ridge, SAST-RF also predicted the class labels correctly. The rst test time series has a near perfect match with the second top best shapelet candidate (see Figure 3.24 top)

which is a shapelet candidate of class 1. The other top best shapelet candidates, which are all from class 2 do not match with the rst time series. This explains why the predicted class label for the rst time series is class 1 and not class 2. The rst, third, fourth and fth top best shapelet candidates, which are all from class 2 have near perfect matches with the second time series, while the second top best shapelet candidate, which is from class 1 does not match (see Figure 3.24 bottom).

Hence, we can interpret why the class label of the second instance is predicted as class 2 and not class 1.

Conclusion

In this work, we shown that the number of shapelet candidates in a shapelet algorithm can be reduced considerably without losing accuracy. We also shown that it is not always necessary to learn shapelets beforehand of classication. We introduced the Scalable and Accurate Subsequence Transform (SAST) algorithm which is interpretable, accurate and a more scalable alternative to the Shapelet Transform algorithm. Furthermore, SAST is comparable in terms of accuracy to the state of the art methods ROCKET, HIVE-COTE and TS-CHIEF, especially for the spectrograph dataset type, while oering easier interpretability. Our experiments revealed that a good trade-o between accuracy and scalability can be found by ensembling dierent SAST models, each one focusing on dierent length of shapelet candidates.

We have also introduced the core shapelet recognition task which consists of learning a shapelets model using only few variants of each shapelet candidate. SAST achieves this task accurately and we hope future shapelet methods will follow the design we introduced.

We plan to do many improvements on the SAST algorithm in the future. Particularly, distance computation could be speed up using lower bounding and early abandon techniques. Dierent variants of the same shapelet can be present in the same time series, therefore similar subsequences can be pruned in order to further reduce the number of shapelet candidates. We are also planing to explore how core shapelet recognition can be applied in TS-CHIEF in order to take shapelet features into account.

Although we focused on time series classication in this chapter, we hope that the same idea can be used in the near future to increase the scalability of shapeletbased time series clustering [START_REF] Fotso | [END_REF]].

In the next chapter, we will improve SAST by removing duplicate subsequences and extend it to uncertain time series using uncertainty propagation.

Conclusion 71 Key points

We introduced the core shapelet recognition task, consisting of building a ML model able to recognize any shapelet by seeing one or a few number of its variants.

We proposed the Scalable and Accurate Subsequence Transform (SAST), a novel design of subsequence-based time series classication approach which is many magnitudes more scalable than shapelet transform while being more accurate.

We demonstrated SAST's eectiveness on respectively 72 and 8 stateof-the-art datasets and methods.

We demonstrated that SAST is an interpretable-by-design method.

Communications

Michael F. for i ← 1 to n do Chapter 4. Explainable Classication of Astronomical uTS which appear in the sky for a limited period of time then disappear forever, there is a small time-window of opportunities when such measurements can be taken.

x i ← [] for j ← 1 to |S| do 9 x i [j] ← dist(T i , S j ) 10 end 11 D f ← D f ∪ {(x i , c i )}
Alternatively, we can also associate dierent classes of astronomical transients to the respective shape of their light curves (brightness variation as a function of time). In this case, we need to repeatedly measure the brightness of the source in a relatively broad region of the wavelength spectrum. This process, called photometry, is less expensive and imposes more manageable constraints on observation conditions. However, measurements are more prone to uncertainties (due to moonlight, twilight, clouds, etc) in the ux determination and the distinction between light curves from dierent classes is subtle, resulting in less accurate classication.

Nevertheless, since there is not enough spectroscopic resources to provide denite label for all photometric observed objects, being able to eectively analyze uncertain photometric light curves means that a wider range of the universe can be quickly understood and at a lower cost.

The Vera C. Rubin Observatory 1 is a ground-based observatory, currently under construction in Chile, whose goal is to conduct the 10-year Legacy Survey of Space and Time (LSST) in order to produce the deepest and widest images of the universe.

The observatory is expected to start producing data in early 2024, and in order to prepare the community for the arrival of its data, one important data challenge was put in place: the Photometric LSST Astronomical Time-Series Classication Challenge or simply PLAsTiCC [START_REF] Allam | The photometric LSST astronomical time-series classication challenge (PLAsTiCC): Data set[END_REF]. The goal was to identify machine learning models able to classify 14 types of transients in simulated data, represented by uncertain time series, or light curves. The ultimate goal behind the challenge was to understand which methods are expected to perform better in LSST-like data, thus preparing the community to the arrival of its data and help understanding the universe's expansion history. Therefore, using interpretable approaches was very important. However, contributors focused on minimizing the classication loss by employing techniques such as mixture of classiers and data augmentation [Hloºek et al. 2020] Given a time series dataset, SAST follows four steps: i), one instance is randomly selected from each class: these are called reference time series; ii) a set containing every subsequences from the selected time series is created; iii) each instance in the dataset is replaced by the vector of its distances to each subsequence obtained in the second step; iv) a supervised classier is trained on the transform dataset.

Performing classication following the SAST steps could be inecient because of the redundancy in the set of subsequences obtained at the second step. The redundancy is particularly high for small length subsequences and in datasets such as electrocardiogram (ECG) and PLAsTiCC, in which repetitive patterns occur very often. Furthermore, the third step is based on the application of Denition 2.3 using the Euclidean distance and, therefore, only the most similar subsequence is considered; however, taking into account the number of occurrences of the best match is important in some contexts. To overcome these limitations, we dene the notion of ε-similarity as follows: Denition 4.1 (ε-similarity). Two subsequences (respectively uncertain subsequences) S 1 and S 2 of same length l are ε-similar if the distance between them is less than or equal to a user-dened threshold ε ≥ 0.

ε-similar(S 1 , S 2 ) = T rue, if dist(S 1 , S 2 ) ≤ ε F alse, otherwise
Theorem 4.2.1. The ε-similar relationship is not transitive.

Proof. Let X, Y , and Z be three subsequences of same length l such that ε-similar(X, Y ) = T rue and ε-similar(Y, Z) = T rue. Let us assume that the transitivity property is veried, that is ε-similar(X, Z) = T rue. A counterexample is built by considering X, Y , and Z as points in a high dimensional space (R l ) such that dist(X, Y ) = dist(Y, Z) = ε, and XY ⊥ XZ. The following derivation proves the theorem:

Chapter 4. Explainable Classication of Astronomical uTS and the number of occurrences of the subsequence S j in Similarly to the Uncertain Shapelet Transform, the uncertain SAST+ ( uSAST+) is obtained by using UED as the distance metric in Algorithm 5; allowing uncertainties to be propagated to the classier which then uses these uncertainties to learn robust decision boundaries.

dist(X, Z) = dist(X, Y ) 2 + dist(Y, Z) 2 = ε 2 + ε 2 =ε √ 2 >ε =⇒ ε-similar(X, Z) = F
T i */ 8 x i [j], x i [j + |S|] ← distAndCount(T i , S j , ε) 9 end 10 D f ← D f ∪ {(x i , c i )}

Experiment

The PLAsTiCC dataset

As far as we know, existing methods published on uTS classication have never been evaluated on real uncertain time series datasets, but solely on simulated datasets.

The corresponding simulated datasets have never been made publicly accessible neither for reproducibility reasons, nor for facilitating research on uTS. In this work, we evaluate our method on a realistic publicly available uncertain time series dataset from the astrophysics domain.

The Photometric LSST Astronomical Time-Series Classication Challenge (PLAsTiCC) dataset contains uncertain time series representing the brightness evolution of astronomical transients including supernovae, kilonovae, active galactic nuclei and eclipsing binary systems [START_REF] Allam | The photometric LSST astronomical time-series classication challenge (PLAsTiCC): Data set[END_REF], among others. The uncertainty in this dataset is modeled by the probability density-based model. Therefore, for each measurement, the astrophysicists provides a best estimate and the maximal possible deviation from that estimate. Each object is represented as a multivariate uncertain time series of 6 dimensions named u, g, r, i, z, y, each corresponding to a particular broadband wavelength lter. After the challenge was nished, the organizers made available an updated version of the data through Zenodo [PLASTICC Team and PLASTICC Modelers 2019] with some bug xes and the classication answers for both the training and test sets. In this work, we demonstrate our method using only uncertain time series from the training set, but the methodology is general enough to be extended to the test set. There are 7848 transients in the dataset, grouped in 14 dierent classes, and the number of objects in the classes are highly imbalanced. More specically, the most underpopulated class has only 0.3% of objects, whereas the most populated one contains 29% of the objects. Furthermore, the dataset contains a lot of missing observations. We handled this with the help of astrophysicists who suggested to ll missing data using a rolling average with a window of length 5. Missing values and corresponding error bars are replaced by the mean and standard deviation of the window. This procedure translated the original dataset into a homogeneously sampled uncertain time series.

Chapter 4. Explainable Classication of Astronomical uTS

The preprocessed dataset is made public 2 .

Our implementation uses the Python programming language and is based on the Scikit-learn machine learning library [Pedregosa et al. 2011] and the Sktime time series dedicated machine learning library [Löning et al. 2019]. The experiment is run on a computing node equipped with 1 Gb of RAM and an AMD EPIC 7452 processor containing 64 logical cores of 2.35 GHz frequency. The source code of our experiments and all the results we discuss in this chapter are publicly available on GitHub 3 .

Results et discussion

Since PLAsTiCC is a multivariate uncertain time series dataset, the subsequence transformation is performed on each dimension independently. The transformations from each dimension are then concatenated together to build a large matrix which is subsequently fed to the supervised classier. We used 80% of the data for training and the remaining is used for testing.

Shapelet-based methods results:

Shapelet-based classication is a special case of subsequence-based classication which consider only shapelets as relevant subsequences. We considered two shapeletbased methods STC [START_REF] Hills | Classication of time series by shapelet transformation[END_REF]] and UST for their interpretability. For both methods, we kept every parameters to their default values except the minimum information gain parameter which is the threshold used to decide if a separator is a valid shapelet. We tried dierent values for this parameter without success, none of these methods were able to nd a single valid shapelet in the dataset. Since feature extraction was not successful, classication was not possible. This result is due to the dataset being highly imbalanced and the uncertain time series from dierent classes being too similar in shape. The same dimension of two randomly selected samples from two dierent classes is shown on Figure 4.1. The left gure which is a Supernova Type Ia-x (SNIax) looks like a left-shifted version of the right gure which is a Supernova Type Ia-91bg (SNIa-91bg). SNIax and SNIa-91bg are known to be dicult to distinguish by astrophysicists. This observation holds, with dierent magnitude, for other classes in the PLAsTiCC dataset and therefore, any shapelet-based methods might struggle to nd shapelets in this dataset.

SAST-based methods results:

For this experiment we considered dierent SAST+ congurations in order to measure the eect of taking uncertainty into account, dropping duplicates and counting the number of occurrences of patterns (i.e patterns frequency). We named congurations that ignore uncertainty as SAST<X> and those which take uncertainty into account as uSAST<X>, where <X> is either : i) an empty string to specify (a) Supernova Type Ia-x (b) Supernova Type Ia-91bg that duplicate subsequences are not removed and the patterns frequency is ignored;

ii) the character d, meaning that duplicate patterns are removed; iii) the string dc, meaning that duplicate patterns are removed and the frequency of patterns is taken into account.

We use three dierent supervised classiers, namely Random Forest (RF), eXtreme Gradient Boosting (XGBoost) and the Ridge regression with Leave-One-Out cross-validation (RidgeCV). The cross-validation procedure is used to nd the best regularization parameter. We set the minimum and maximum subsequence lengths to 20 and 60 respectively, with a step of 10. Compared to a step of 1, a step of 10 reduces the chance of having similar subsequences while reducing the number of subsequences to be used. We observed that the classication performance is better with this setup as can be seen in Appendix B. The ε-similarity is computed with ε = 0.25 as experiments shown that too much relevant subsequences are discarded with higher values. The parameters of the classiers are left to their default values, except for the regularization parameter in RidgeCV which is selected using cross-validation. As the reference time series are chosen randomly, we run each experiment 3 times and we report the average precision, recall, F1 score, cross entropy loss and the time taken for training and inference (in hours). As PLAsTiCC is an imbalanced multiclass dataset, we use a weighted average to compute the precision, recall and F1 score; the weights being the percentage of each class in the dataset. The data set includes 6 classes with overall similar behavior (42,52,62,67,90,95). Among these, astronomers are specially interested in type 90 (SNIa), which is used as distance indicator in cosmological analysis [START_REF] Ishida | [END_REF]]. Reporting our results as a binary problem with class 90 against all others, we achieve 85% precision, 81% recall and 82% F1 score. Therefore, our method is able to correctly classify a high proportion of SNIa despite its similar behavior to other classes.

Ablation study:

Here, we study the impact of taking uncertainty into account. In particular, we compare the results obtained when uncertainty is ignored (Table 4.3) to the results obtained when uncertainty is taken into account (Table 4.1).

Explainability:

One of the best properties of subsequence-based classication is its interpretability.

The explanation could be done either locally, when it concerns only a single instance, or globally when it concerns the whole model. In any case, this is generally done by inspecting the model in order to extract the most discriminative subsequences [Ye & Keogh 2009a]. These subsequences could also be found using a posthoc method such as LIME [START_REF] Ribeiro | [END_REF] or SHAP [Lundberg & Lee 2017],

but since our approach is explainable-by-design, inspecting the model is sucient.

More specically, since the classier used in our model is tree-based, the information gain can be used as a measure of the discriminative power of the subsequences similarly to what is done in shapelet-based methods. The local explainability of our method is obtained by inspecting the subsequence on which the model focused the most in order to make the prediction for a single instance, these are the subsequences which led to the highest information gain (see Denitions 2.4 and 2.5). . This conrms that our model focuses on the relevant regions and dimensions of the time series to make the classication. Being able to correctly learn the dimension's relevance is crucial as the discriminative subsequence may appear only in a subset of the dimensions. Furthermore, the location of the discriminative subsequence may not be the same on every dimension. In PLAsTiCC in fact, depending how far is the object, the light may be visible only on some wavelengths (i.e. dimension). Due to the accelerated expansion of the universe, objects which are further away are also moving with a higher velocity. Thus, there is a Doppler eect in the observed light which shifts it to higher wavelengths. Thus, closer (galactic) objects will generally have higher signals in lower wavelengths than further away (extragalactic) ones. Our method perfectly captures the Doppler effect unlike XEM which cannot identify from which dimensions the discriminative subsequences is located. It is observed that the discriminative power is generally due to the value, but sometimes it is due to the uncertainty (for example subsequences #18 and #19).

Seeing that some subsequences are important because of their uncertainty emphasizes the fact that taking uncertainty into account is important and improves the classication performance. There are also some subsequences that are too similar despite the fact that duplicate subsequences have been dropped; for instance, the subsequences #3 and #7. This is because the similarity between subsequences is computed using the Uncertain Euclidean Distance (UED) which considers the subsequences to be perfectly aligned. This problem can be resolved by using an elastic distance such as the DTW distance at the cost of more computational time since such distances generally have at least quadratic time complexity while UED is linear. From the domain knowledge point of view, these discriminative subsequences are able to grasp the important shapes commonly associated with their respective class of astronomical transients. Subsequences #1 and #6 were taken from class 16 (eclipsing binary) and clearly show the expected light curve from a well measured binary system where one star eclipses the other exactly in the line of sight, thus leading to a decrease in brightness. Subsequence #19 is also associated to the eclipsing binary class, but in this case the signal is less clear, corresponding to an object which is further away thus leading to low signal and large uncertainties.

We also call attention to the supernova-like behavior exhibited by subsequences #4 and #9 one single burst events whose brightness are only visible for weeks to

Conclusion and future directions

The classication of time series with available uncertainty measures is an underexplored and challenging task. In this work, we proposed an approach to perform this task with a global F1 score of 70%, without using techniques such as data augmentation nor oversampling. The explainability of the proposed approach allows domain experts to not only understand individual predictions, but also to characterized each class by a set of subsequences with high discriminative power, which can then be used to perform other important tasks in astrophysics such as novel astronomical transients detection and anomaly detection. The ablation study shown the positive impact of taking uncertainty into account. A limitation of the approach is the time complexity, which could be considerably high for datasets with relatively long uncertain time series. A future direction would consist of further reducing the number of subsequences to be used and optimizing the computation time of the method. Another future direction would consist of nding a better way of managing uncertainty during the classication step in order to improve the performances. Nevertheless, the results presented in this work illustrate how our approach is eective in identifying meaningful subsequences which, beyond the classication performance, can provide important information to the expert. The approach is exible enough to be applied to other scientic domains where uncertain time series are the common, thus enabling future advances in multiple subject areas.

Key points

We reduced SAST's computational time and proposed the uncertain SAST (uSAST), an extension of SAST to uncertain time series classication.

We applied uSAST to a realistic uncertain time series dataset and demonstrated its classication eectiveness as well as explainability.

Communications

Michael F. Chapter 5

General conclusion and future directions

In this chapter, we summarize our contributions, discuss the limitations of this work and give some future directions. We also give the list of publications that we did throughout this thesis. Finally we proposed uSAST, an extension of SAST to uncertain time series classication. We assessed uSAST not only on simulated datasets, but also on a real uncertain time series dataset from the astrophysics domain named PLAsTiCC.

As far as we know, this is the rst open-sourced experiment on real uncertain data.

uSAST shown good classication performance on PLAsTiCC as well as great local and global explanations.

Scientic valorization

We valorized and shared our contributions at national and international conferences.

In particular, the rst UST version has been accepted and presented at the French

Limitations and perspectives

We proposed to use uncertainty propagation to take uncertainty into account in uncertain time series classication. We shown that this approach lead to models that are more robust and accurate, but also more natural to users and therefore, more trustable. Both UST and uSAST have three steps: feature selection, feature transformation and classication. We successfully took uncertainty into account in the three steps, but we strongly believe that uncertainty handling could be improved in the classication step. In fact, we used regular supervised classiers (Random Forest, XGBoost, etc) for this step, these classiers consider uncertainties as regular features although they should be considered as meta features. This step would be more eective if the classier used was aware of uncertainties and dierentiated them from regular features. Few works exist in the literature to achieve that, namely the Decision Tree for Uncertain data [START_REF] Qin | [END_REF], Qin et al. 2011]. Therefore, it would be interesting to explore how the work started in this thesis could be improved using uncertain supervised classiers.

Given that preprocessing generally makes learning easier, it would be legitimate to ask why we did not mention it in this work. In fact, preprocessing is generally application and data-dependent, and therefore not straightforward to be integrated in an end-to-end approach. Instead, we wanted our models to have good performance on the raw data. Nevertheless, it would be a good future direction to see if the performance of our models could be improved by applying some preprocessing of the time series rst. One of this techniques could be the uncertain moving average (UMA) and the uncertain exponential moving average (UEMA) [Dallachiesa et al. 2012].

In order to ensure the explainability of our methods, we used only the shapelet features, which are acknowledge in the literature for their natural explainability.

However, it has been shown in the literature that time series classication is more eective when dierent features (shapelet, interval, word, etc) are combined together. Hence, another future direction will be to take uncertainty into account in interval, dictionary, spectral, hybrid and deep learning methods for time series classication.

We modeled uncertainty in this work using two values which are the best estimate (or guess) and the standard deviation from that estimate, however, there exist other representations: random sets, possibility distributions, probability intervals, etc [START_REF] Destercke | Unifying practical uncertainty representationsI: Generalized p-boxes[END_REF] which have particular properties. It is worthy to analyze how these representation could be used with time series data. For instance, using imprecise probability modeling will ease the adaptation of existing works to time series data [START_REF] Destercke | Ranking of fuzzy intervals seen through the imprecise probabilistic lens[END_REF], Carranza Alarcon & Destercke 2019].

  Contents 0.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0.2 Uncertainty, not a bad thing ! . . . . . . . . . . . . . . . . . . 2 0.3 Main contributions . . . . . . . . . . . . . . . . . . . . . . . . 4 0.4 Report structure . . . . . . . . . . . . . . . . . . . . . . . . . . 5 0.1 Context In this era of Big Data, machine learning (ML) has become ubiquitous in almost any aspect of human life.

  Contents 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 What is a time series . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Notion of uncertainty . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Time series classication . . . . . . . . . . . . . . . . . . . . . 12 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.1 Certain time series classication approaches . . . . . . . . . . 14 1.2.2 Uncertain time series classication approaches . . . . . . . . 24 1.3 Our proposed general approach for uTSC . . . . . . . . . . . 28 1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ω.

  In order to better understand this general denition of time series, concrete examples are shown on Figures 1.1 and 1.2.

Figure 1

 1 Figure 1.1: A time series modeling the the evolution of daily new covid-19 cases in Africa

Figure 1

 1 Figure 1.2: A time series modeling the groundwater level in the french department Puy-de-dôme

Figure 1 .

 1 Figure 1.5 illustrates some uncertain time series. The rst two gures are from [Siyou Fotso et al. 2020] and show a multiset uncertain time series (Figure 1.5a) and a probability density function uncertain time series (Figure 1.5b). The last two gures use the PDF representation, the blue lines are obtained by connecting the best estimates, these lines can be seen as the best estimate of the uncertain time series. The red bars are the possible deviation from the best estimates. Unlike Figure 1.5b, the probability distributions are unknown on the last two gures.

1. 7 .Figure 1

 71 Figure 1.7: Natural alignment of both time series. ED(T 1 , T 2 ) = 2.82

Figure 1 . 8 :

 18 Figure 1.8: Elastic alignment of both time series. DT W (T 1 , T 2 ) = 0

Figure 1 . 9 :

 19 Figure 1.9: Relevant intervals in a dataset (image obtained by annotating an original image from [Lines et al. 2018])

Figure 1 .

 1 Figure 1.10: Overview of time series classication based on intervals

Figure 1 .

 1 Figure 1.11: Illustration of shapelets (image obtained by annotating an original image from [Lines et al. 2018])

Figure 1

 1 Figure 1.12: Overview of time series classication based on shapelets

Figure 1 .

 1 Figure 1.13: Illustration of a dictionary dataset [Lines et al. 2018]

  Figure 1.14: SAX illustration [Lin et al. 2007]. The string representing the time series is baabccbc.

Figure 1 .

 1 Figure 1.15: Illustration of spectral dataset [Lines et al. 2018]

  2022]. In addition to PPV, MultiROCKET considers the Mean of Positive Values (MPV), the Mean of Indices of Positive Values (MIPV) and the Longest Stretch of Positive Values (LSPV).

Figure 1

 1 Figure 1.16: Overview of existing time classication approaches

  the fact that any measure is uncertain (either for epistemic, or for aleatoric reasons), researchers have not focused on uTSC as much as they did for TSC.The few methods that exist for uncertain time series classication work in the same way: combining an uncertain similarity measure with the 1-Nearest Neighbor (1-NN) classier. The development has been therefore focused on the building of similarity measures for uncertain time series. al. 2009] and can be used when the uncertainty is represented by a set of possible observations at each time step. It is used to compute the probability that the similarity between two uncertain time series is below a user-dened threshold. Therefore, MUNICH does not actually compute the uncertain similarity and has never been used in a classication context. The uncertain similarity measure PROUD [Yeh et al. 2009] also computes the probability of the similarity being below a threshold, but unlike MUNICH, uses PDF representation of uncertain time series. The uncertain similarity distance DUST [Sarangi & Murthy 2010] has been been proposed as a generalized notion of distance between uncertain time series to overcome the limitation of PROUD and MUNICH. It makes fewer assumptions on the uncertainty compared to PROUD, is computationally less expensive compared to MUNICH and degenerates to the Euclidean distance when the uncertainty is very

  this work. About 10 years after DUST, the uncertain similarity measure FOTS has been proposed [Siyou Fotso et al. 2020]. Compared to DUST, MUNICH and PROUD, FOTS does not explicitly model the uncertainty, but assumes the time series are noisy and there is no information nor assumptions made on that noise. FOTS uses Eigenvalues decomposition to keep only the most important components of the uTS and to reduce the noise.

Figure 1 Figure 1

 11 Figure 1.17: Overview of existing uncertain time classication approaches

Figure 2 .

 2 Figure2.1 illustrates a node in the proposed decision tree. The blue time series contain the subsequence in the node (i.e they are similar to the subsequence at the node), so they follow the branch labeled with yes. The red time series does not contain the subsequence in the node (i.e they are not similar to the subsequence at the node), therefore the follow the branch labeled with no.

Figure 2

 2 Figure 2.1: An illustration of a node in a shapelet decision tree for a binary time series classication

  the minimum and the maximum length of an uncertain shapelet M IN and M AX. This algorithm uses three subprocedures: GenCand(T, M IN, M AX) which generates every possible uncertain shapelet candidates from the input uncertain time series T . These candidates are uncertain subsequences of T , with length at least M IN and at most M AX. AssessCand(cands, D) which computes the quality of each candidate in the list of candidates cands. The quality of a candidate is the information gain it produces when used as a separator for the dataset. ExtractBest(C, Q, k) which takes the list of uncertain shapelet candidates C, their associated qualities Q and returns rst k uncertain shapelets with highest qualities. In summary, Algo. 1 generates every uncertain subsequences of length at least M IN and at most M AX from the dataset, assesses the quality of each one by computing the information gain obtained when it is used as a separator for the dataset and nally returns the k subsequences that produce the highest information gain. The parameters M IN and M AX should be optimized to reduce the execution time of the algorithm. With the knowledge of the domain, the length of a typical shapelet can be estimated and used to set M IN and M AX in order to reduce the number of shapelet candidates. By default M IN is set to 3 and M AX is set to m -1, where m is the length of the time series.

  10 return S // Top k uncertain shapelets 11 end corresponding uncertainties. The scaled and transformed dataset is nally returned by the algorithm. The third and last step is the eective classication. A supervised classier is trained on the uncertain transformed dataset, such that, given the feature vector of an unseen uncertain time series, it can predict its class label. Since the uncertainty have been propagated, the training process can be aware of uncertainty by taking it as part of the input. More specically, best guesses are features and uncertainties are features of best guesses, and thus are meta-features.There exists many supervised classiers in the literature for the classication of uncertain tabular data[Li et al. 2020a, Aggarwal & Yu 2009]. We have decision tree-based methods[START_REF] Tsang | [END_REF], Qin et al. 2009], SVM-based methods[Bi & Zhang 2005, Yang & Gunn 2007, Li et al. 2020b] and Naive Bayes-based methods[START_REF] Qin | [END_REF], Qin et al. 2010]. Since the transformed data is an uncertain tabular data, uncertain supervised classiers can be used for the classication step. Furthermore, any supervised classier can be used as soon as the transformed dataset is formatted in a way that is accepted by that classier.

Fig. 2

 2 Fig. 2.2 gives an overview of the classication process. During the training step, top-k uncertain shapelets are selected and an uncertain supervised model (illustrated here by a decision tree for simplicity) is trained on the uncertain transformed dataset. During the test step, the uncertain shapelets extracted during the training step are used to transform the test set, and the trained model is used to predict the class labels of the test set according to the result of the transformation. We call this model UST for Uncertain Shapelet Transform classication.

[

  [START_REF] Fotso | [END_REF]. Hence, the number of windows (m) is equal to the length of a window (w) which is equal to half the length of the time series. The time index (t) used to compute the auto-covariance matrices is equal to half the length of the time series, and nally the number of eigenvectors (k) is set to 4.

  The uncertainty result for an instance from the Chinatown dataset is shown by Fig.2.3 for c = 0.6. The orange line is the original time series, and the blue one is the obtained uncertain time series. Sometimes, the original time series does not cross the uncertainty interval (vertical red bars), these cases are there to represent situations where the uncertainty has not been well estimated, maybe because the expert has been too optimistic. Situations where the expert had been too pessimistic are represented by very large uncertainty bars. During the training phase, original time series are not used, only the uncertain time series are used. We implemented UST in the Python programming language, and we used the open source package sktime [Löning et al. 2019]. The code and the data used for our experiment are publicly available 1 .

Figure 2

 2 Figure 2.3: Illustration of uncertainty for an instance from the Chinatown dataset. the uncertainty level is c = 0.6

  Figure 2.4: Critical dierence diagrams of UED-based models regarding the ordering strategy for some levels of uncertainty

  Then we adapt the well known shapelet algorithm to the context of uncertain time series using Chapter 2. Uncertain Time Series Classication With Shapelet Transform U ED and propose the uncertain shapelet transform algorithm (UST). We have run experiments on state of the art datasets. The results show that propagating uncertainty during the shapelet transformation and then using an uncertain classier lead to a more accurate model for uncertain time series classication. The idea of uncertainty propagation can be used with any dissimilarity measure, and any uncertain supervised classier can be used in the classication phase.

  Contents 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 SAST: Scalable and Accurate Subsequence Transform . . . 49 3.2.1 Reducing the number of shapelet candidates . . . . . . . . . . 49 3.2.2 Identify shapelets using feature importance analysis . . . . . 53 3.2.3 Time series classication with SAST . . . . . . . . . . . . . . 54 3.2.4 SAST time complexity . . . . . . . . . . . . . . . . . . . . . . 55 3.2.5 Ensemble of SAST models . . . . . . . . . . . . . . . . . . . . 56 3.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.1 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3.2 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.3.3 Interpretability . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 48 Chapter 3. Scalable and Accurate Subsequence Transform for TSC

50

  Figure 3.1: Illustration of invariance in recognition.

Figure 3 .

 3 Figure 3.3 shows 4 randomly selected instances for each class. Instances of the same class are superposed in order to expose global patterns. The gure emphasizes the previous observation that class 1 contains instances that start by a deep valley while class 2 are instances that are more at at the beginning.Based on this observation, we propose the following statement:

52

  Figure 3.4: Top 5 shapelets extracted for each class of the Chinatown dataset by the shapelet transform algorithm.

Following

  Figure 3.5. Dierent variants of the same shapelet are not learned anymore. Forthis dataset, exactly one shapelet has been selected for each class. As we will show in Section 3.3, STC-k is signicantly less accurate than STC, even when k is equal

Figure 3

 3 Figure 3.5: Shapelets extracted by STC on the Chinatown dataset using a single randomly selected instance per class to generate shapelet candidates.

Figure 3 . 6 :

 36 Figure 3.6: Overview of the SAST method

58

  Figure 3.7: Comparison of STC-k to STC in terms of accuracy

  chapter, SAST-Ridge-A is the approximated SAST-Ridge model with length_list = {7, 11, 15}.

Figure 3 . 9 :

 39 Figure 3.9: Critical dierence diagram between approximated SAST models

Figure 3 .

 3 Figure 3.11: Critical dierence diagram between SAST models

  -1 fails to nd any shapelet on it. These results conrm our though that pruning shapelet candidates, without taking into account the classier can lead to very inaccurate classication.

  Figure 3.12: Pairwise comparison of SAST, STC and STC-1

Figure 3 .

 3 Figure 3.13: Critical dierence diagram between SAST, STC and STC-1

Figure 3 .

 3 Figure3.14 shows a pairwise comparison of these method and the critical different diagram on Figure3.15 shows how signicant is each model compared to others in terms of accuracy. LS, ELIS++ and SAST are not signicantly dierent in terms of accuracy, however they outperform FS. It is important to note that LS and ELIS++ do not select shapelets from the training set, but learn them through an optimization process. Therefore the shapelet space is unlimited, the learned shapelets are unpredictable as well as the time required for convergence. Furthermore, nding the hyper-parameters and the appropriate shapelet initialization for

  -COTE accuracy and could reduce its time complexity since the shapelet module is the most time consuming one in HIVE-COTE. When TS-CHIEF was proposed, their authors decided not to exploit shapelet features because of their computation time. With the core shapelet recognition task we introduce in this work, we believe that shapelet feature can be added in TS-CHIEF a low cost and that this could increase the accuracy of this model .

  Figure 3.16: SAST vs SOTA

Figure 3 .

 3 Figure 3.18: SAST, ELIS++, LS and FS percentage of wins per dataset type considering the 35 datasets used in ELIS++ paper.

Figure 3 .

 3 Figure 3.19: SAST, HIVE-COTE, TS-CHIEF and ROCKET percentage of wins per dataset type

Figure 3 .

 3 Figure 3.21 and 3.22 show the top 5 best shapelets plotted on the reference time series for the Chinatown dataset with respect to SAST-Ridge and SAST-RFrespectively. The top rows of the gures are the reference time series selected from class 1, while the second rows are the reference time series selected from class 2. A perfect match between a shapelet candidate and a reference time series means that the shapelet has been extracted from that reference time series. Hence, the top 5

Figure 3 .

 3 Figure 3.21: Top 5 shapelets learned by SAST-Ridge on Chinatown.

Figure 3 .

 3 Figure 3.22: Top 5 shapelets learned by SAST-RF on Chinatown.

Figure 3 .

 3 Figure 3.23: Explanation of SAST-Ridge predictions on two random test instances

  Input: D = {(T 1 , c 1 ), (T 2 , c 2 ), ..., (T n , c n )}, k: the number of instances to use per class, length_list: the list of subsequence lengths, C: the classier to use begin /* randomly select k instances per class from the dataset */ D c ← randomlySelectInstancesP erClass(D, k) /* generate every patterns of length in length_list from D c */ S ← generateShapeletCandidates(D c , length_list) /* transformed the dataset using every patterns in S */ D f ← ∅for i ← 1 to n dox i ← [] for j ← 1 to |S| do 8 x i [j] ← dist(T i , S j ) end 10 D f ← D f ∪ {(x i , c i )} 11 end /*train the classifier on the transformed dataset */ 12 clf ← trainClassif ier(C, D f ) 13 return (clf , S) ; // the trained classifier and the shapelet candidates 14 end 74 Chapter 3. Scalable and Accurate Subsequence Transform for TSC

  alse Using Denition 4.1, we can reduce redundancies and count subsequence frequencies in SAST. The updated SAST method, hereafter SAST+, is detailed in Algorithm 5. Algorithm 5: SAST+ Input: D = {(T 1 , c 1 ), (T 2 , c 2 ), ..., (T n , c n )}, k: the number of instances to use per class, length_list: the list of subsequence lengths, C: the classier to use, ε: ε-similarity parameter. 1 begin Randomly select k instances per class from the dataset 2 D c ← randomlySelectInstancesP erClass(D, k) /* Generate every patterns of length in length_list from D c , using 1 to |S| do /* The procedure distAndCount(T i , S j , ε) returns Dist(T i , S j )

  clf , S) /* The trained classifier and the subsequences */ 13 end The time complexity of the SAST method is O(N c ) + O(kN c m 2 ) + O(nm 3 ) + O(classif ier), where N c is the number of classes, n the number of time series, m the length of the time series and k the number of reference time series per class. In practice, it is not necessary to have k greater than one. Removing re-dundancies in SAST is done only once (during the training phase) with a theoretical time complexity of O(km 4 ) ; counting frequencies is done while computing the distance in a constant time. Therefore, the SAST+ time complexity is O(N c ) + O(kN c m 2 ) + O(nm 3 ) + O(classif ier) + O(km 4 ) which is asymptotically equivalent to O(classif ier)+O(km 4 ). Removing redundancies makes SAST+ much faster than SAST during inference.

Figure 4 . 1 :

 41 Figure 4.1: Two supernova from PLAsTiCC. They look similar in terms of shapes although they are from distinct classes.

Figure 4 .

 4 Figure 4.2 shows local explanations for a Supernova Type Ia (SNIa) and a Corecollapse Supernova Type II-P (SNII-P) correctly classied by the model. The P in the denomination of the latter references the plateau phase observed in its timeseries just after maximum brightness. This feature is clearly shown in the bottom panel of Figure (4.2). This conrms that our model focuses on the relevant regions

A

  global explanation is obtained by building a subsequence-based prole of each of the class. The top 20 most discriminative subsequences from the uSASTd model are shown in Figure 4.3. Subsequences that are from the same class label are plotted with the same color, its rank, its class label and its type are given at the top of its corresponding plot. The type is either Value if the discriminative power comes from the value itself or Uncertainty if the discriminative powers comes from the

Figure 4 . 2 :

 42 Figure 4.2: Local explainability of a Supernova Type Ia (top) and a Core-collapse Supernova Type II (bottom)

Figure 4 . 3 :

 43 Figure 4.3: The top 20 most discriminative subsequences in the PLAsTiCC dataset

  months. The fact that such characteristic behaviors are easily spotted in the list of most important subsequences certies that our nal classication results are in line with the expert denition of such classes and hence, shows that our model is safe and trustworthy. Moreover, further investigations of a more extensive list of impor-4.4. Conclusion and future directions 87 tant subsequences have the potential to reveal unexpected time series shapes and promote the development of more detail theoretical models for such astrophysical sources.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.1.1 Main contributions . . . . . . . . . . . . . . . . . . . . . . . . 90 5.1.2 Scientic valorization . . . . . . . . . . . . . . . . . . . . . . 90 5.1.3 Open sourced codes and data . . . . . . . . . . . . . . . . . . 90 5.2 Limitations and perspectives . . . . . . . . . . . . . . . . . . 91 5.3 Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.4 List of publications . . . . . . . . . . . . . . . . . . . . . . . . 92 5.4.1 First-authored publications . . . . . . . . . . . . . . . . . . . 92 5.4.2 Non rst-authored publications . . . . . . . . . . . . . . . . . 93 5.1 Conclusion In this thesis, we addressed the task of classifying uncertain time series. The uncertainty in the data makes this task more challenging than a regular time series classication task. We dened what are uncertainty and uncertain time series, then we shown that the current state-of-the-art on the classication of uncertain time series is limited and dicult to adopt by end-users because of a brutal disappearance of the uncertainty in the classication process. This work advances the state-ofthe-art of uncertain time series classication by proposing explainable, robust and ecient methods. Specically, we proposed a novel general design of uncertain time series classication which propagates uncertainty throughout the whole classication process. The propagation is achieved using uncertainty propagation techniques, widely used in physics. 90 Chapter 5. General conclusion and future directions5.1.1 Main contributionsFrom the novel design, we derived the Uncertain Shapelet Transform (UST) which is a shapelet-based, hence explainable method for the classication of uncertain time series. UST internally uses the Uncertain Euclidean Distance (UED) that we proposed as a novel similarity measure for uncertain time series with the ability to give not only the similarity, but also the uncertainty on that similarity. We demonstrated the performance of UST on synthetic datasets.Given the high time complexity of existing shapelet-based methods (including UST), we proposed the Scalable And Accurate Subsequence Transform (SAST), a subsequence-based method to signicantly reduce the computation time without losing accuracy, nor interpretability.Concretely, while the state-of-the-art shapelet-based method STC's time complexity is O(n 2 m 4 ), SAST's time complexity is O(nm 3 ), where n and m are respectively the number and the length of time series. This correspond to a reduction by a factor of nm. We also shown that SAST is competitive with state-of-the-art methods for regular time series classication HIVE-COTE and ROCKET. We have also demonstrated SAST explainability on the Chinatown dataset from the UCR & UEA archive.

  national conference on articial intelligence (CNIA 2020) and at the Workshop on Uncertainty in Machine Learning (WUML 2020) which was hosted by the European Conference on Machine Learning (ECML/PKDD 2020). Later on, the nal UST version has been presented at the workshop on Large-Scale Industrial Time Series Analysis (LITSA 2021) hosted by the IEEE International Conference on Data Mining (IEEE ICDM 2021). SAST has been accepted for a long presentation at the french conference on machine learning (CAp 2021) and is currently under review at the Elsevier journal Pattern Recognition. A working paper on uSAST is available on the open archive HAL.5.1.3 Open sourced codes and dataWe open sourced the codes and data used throughout this thesis in order to facilitate research and applications in uncertain time series classication in particular, and in uncertain time series analysis in general. Access links are given below: 5.2. Limitations and perspectives 91 UST: https://github.com/frankl1/ustc SAST: https://github.com/frankl1/sast uSAST: https://github.com/frankl1/usast

Figure A. 1

 1 Figure A.1 shows a zoom on Figure 3.20b. We can now clearly see that SASTEN is slower than SAST and SASTEN-A whatever the number of time series in the dataset. SASTEN-A running time is quite linear because the shapelet space is constant and only the transform time increases with the number of series.

Figure A. 1 :

 1 Figure A.1: Running time in seconds of SAST, SASTEN and SASTEN-A regarding the number of time series

  Lewandowski et al. 2010, Lin et al. 2007]. Others time series analysis tasks are forecasting [Hewamalage et al. 2022, Mbouopda 2022, Mbouopda et al. 2022], novelty detection [Ma & Perkins 2003], anomaly detection [Nakamura et al. 2020, Audibert et al. 2020], motif discovery [Yeh et al. 2018] and querying [Ding et al. 2008, Yagoubi et al. 2018]. These tasks can be classied as either supervised or unsupervised as shown on Figure 1.6.

	1.1. Background		Chapter 1. Background and related work	13
	1.2 Related work
	1.2.1 Certain time series classication approaches Classification This subsection describes the existing approaches to perform time series classica-
	tion when uncertainty is assumed to be absent or negligible: this is what we call
	certain or regular time series classication.
	Denition	1.5	(Time	Supervised series	classication)	Regression
	Time series analysis			Unsupervised	Motif discovery	Clustering Forecasting	novelty/anomaly	detection	Figure 1.6: Time series analysis tasks hierarchy
						Dimensionality	reduction
	This thesis focuses on the classication task of time series whose values are
	uncertain. The presence of uncertainty makes this task more complicated, since even for humans, it is not easy to take decisions when the possessed information are inaccurate. Because the existing methods for the classication of uncertain time Querying
	series are inspired from certain time series classication methods, we present the
	later methods rst.

Time series analysis includes several tasks including the four classical machine learning tasks which are classication

[Ye & Keogh 2009b, Bagnall et al. 2017]

, clustering

[Ulanova et al. 2015, Siyou Fotso et al. 2020]

, regression

[Tan et al. 2021]

, and dimensionality reduction [

  , Flynn et al. 2019]) combines features from the frequency and interval domains, and uses ensemble techniques to reduce the variance. RISE is signicantly more accurate than any other spectral method.

	The	Hierarchical	Vote	Collective	of	Transformation-Based	Ensembles
	(HIVE-COTE) [Lines et al. 2018], inspired from the collective of transformation-based
	ensembles (COTE) is the state-of-the-art method for time series classication. It
	combined 35 time series classiers grouped in 5 modules: 1 shapelet module, 1
	whole series module, 1 dictionary module, 1 interval module and 1 spectral module.
	Each module is made of ensemble classiers. The nal classication is obtained by
	a majority vote. The second version of HIVE-COTE has been developed exploiting
	the recent advances in time series classication [Middlehurst et al. 2021]. This
	version is made of four modules of ensemble classiers whose base learners are:

Table 1 .

 1 1: Summary of the current time series classication state-of-the-art (SOTA)

	Category	Features	Explainability	SOTA methods
				1NN-DTW
	Whole series	time series	absent	EE
				FastEE
	Subsequence-based	subsequences	by design	XEM

  widely used in the literature to measure the dissimilarity between time series. It is particularly used in shapelet-based approaches [Ye & Keogh 2009b, Hills et al. 2014, Bagnall et al. 2017]. Using the uncertainty propagation properties, an uncertain dissimilarity measure based on ED can be computed for two uncertain time series T 1 and T 2 by propagating uncertainty in the ED formula. We name the obtained measure UED for Uncertain Euclidean Distance, and it is dened as follows:

  An uncertain measure can be considered as a random variable with mean equals to the best guess and standard deviation equals to the uncertainty. Given this

consideration, a stochastic order can be dened on the set of uncertain measures. A random variable X is stochastically less than or equal to (noted ≤ st ) another random variable Y if and only if P r[X > t] ≤ P r[Y > t] ∀t ∈ I, where I is the union of the domains of X and Y

[START_REF] Marshall | [END_REF]

. The stochastic order can be rewritten and developed as follows:

  Larger values of k lead to best approximation of I, however slow the classication process. We tried several values of k, but k = 100 worked better. We have also used a relaxed version of the stochastic ordering: given two random variables X and Y , we have X ≤ st Y if the number of values t in I such that CDF X (t) > CDF Y (t) is greater than the number of values t in I such that CDF

X (t) ≤ CDF Y (t).

Table 2 .

 2 1: Summary of the models that are compared in our experiments. used datasets from the well known UCR repository[Dau et al. 2019]. Instead of running our experiment on the whole repository, we use only datasets on which shapelet approaches are known to work well. According to[START_REF] Bagnall | [END_REF], shapelet approaches are more suitable for electric device, ECG, sensor and simulated datasets. Tab. 2.2 gives a summary of the 15 shapelet datasets on which we conducted our experiments. The rst column is the name of the dataset, the second is the number of instances in the training/test set, the third is the length of time series and the fourth and last column is the number of dierent classes in the dataset. Each dataset is already split into the training and the test sets on the repository.

	Name	Measure	Ordering	Classier Time contract
	ST	ED	Natural	GNB	10 minutes
	UST(DUST_NORMAL)	DUST NORMAL	Natural	GNB	10 minutes
	UST(DUST_UNIFORM)	DUST UNIFORM	Natural	GNB	10 minutes
	UST(FOTS)	FOTS	Natural	GNB	120 minutes
	UST(UED, GNB)	UED	Simple, Stochastic and Interval	GNB	10 minutes
	UST(UED, UGNB)	UED	Simple, Stochastic and Interval	UGNB	10 minutes
	each uncertain feature vector is atten such that the rst half contains the best
	guesses and the second half contains the uncertainty deviation. This is required
	because the Gaussian naive bayes (GNB) classier does not take uncertainty into
	account.
	2.4.2 Datasets

We

  Mbouopda, Engelbert Mephu Nguifo. Classication des Séries Temporelles Incertaines Par Transformation Shapelet. In Con-

	Chapter 3
	Scalable and Accurate
	Subsequence Transform for Time
	Series Classication
	férence Nationale en Intelligence Articielle (CNIA), pp.14-21, Jun.
	2020.
	Michael F. Mbouopda, Engelbert Mephu Nguifo. Classication of
	Uncertain Time Series by Propagating Uncertainty in Shapelet Trans-
	form. In ECML/PKDD Workshop on Uncertainty in Machine Learning
	(WUML), pp.1-12, Sep. 2020.
	Michael F. Mbouopda, and Engelbert Mephu Nguifo. Uncertain time
	series classication with shapelet transform. In International Confer-
	ence on Data Mining Workshops (ICDMW), pp. 259-266, Nov. 2020.

  in order to interpret predictions. Two examples of these post hoc explainers are LIME[START_REF] Ribeiro | [END_REF] and SmoothGrad[START_REF] Smilkov | [END_REF] for saliency maps. More methods can be found in the review of[Samek et al. 2020].

	Hence, selecting shapelets beforehand of classication using information gain can be
	skipped, since the classier can automatically learn the top best shapelets during its
	training iterations and feature analysis can be used after training to get the learned
	shapelets.
	3.2.3 Time series classication with SAST

Time series classication with SAST (Scalable and Accurate Subsequence Transform) is designed with respect to Proposition 3.2.1 and Proposition 3.2.2. A visual view of the the method is shown on Figure

3

.6. There are two main blocks:

  Chinatown dataset is used here. It is a binary dataset with time series of length 24. There are 20 instances in the training set and we use random oversampling to create bigger versions of this dataset. Figure 3.20b shows the running time of each model.The running time of each model increases nearly linearly with the number of time series in the dataset. STC running time starts higher and increases much faster compared to other models. This is not surprising since the training time of shapelet methods is extremely related to the number of shapelet candidates, and the number of shapelet candidates in STC increases with the number of time series while the number of shapelet candidates in a SAST model increases with the number of classes. More precisely, STC takes about 12 minutes on a dataset of 64 time series of length 24, while SAST takes only 2 seconds, SASTEN requires 10 seconds and SASTEN-A needs about 6 seconds. For a dataset with 1024 time series of length 24, SASTEN, SAST and SASTEN-A are respectively about 5000 times, 8000 times and 9000 times faster than STC.

	3.3. Experiments	67
	3.3.2.2 Training set size

The

  Mbouopda, Engelbert Mephu Nguifo. Scalable and Accurate Subsequence Transform for Time Series Classication. In Conférence sur l'Apprentissage automatique (CAp), pp 1-27, Jun. 2021. D = {(T 1 , c 1 ), (T 2 , c 2 ), ..., (T n , c n )}: the training dataset, k: the number of instances to use per class: the list of subsequence lengths, C: the classier to use, length_list: the list of subsequence lengths, min_ig: the minimum information gain to

	Algorithm 3: ShapeletTransformK
	Input: consider a subsequence as shapelet
	begin
	/* randomly select k instances per class from the dataset */
	D c ← randomlySelectInstancesP erClass(D, k)
	/* generate every subsequence of length in length_list from D c
	*/
	S ← generateShapeletCandidates(D c , length_list)
	/* compute the information gain of each subsequence and
	Michael F. Mbouopda, Engelbert Mephu Nguifo. Scalable and Accurate return the one that have at least the required
	Subsequence Transform for Time Series Classication. Pattern Recog-information gain */
	nition, pp 1-35, submitted in May 2021. S ← extractShapelet(S, D, min_ig)
	/* transformed the dataset using every patterns in S	*/
	D f ← ∅

Table 3 .

 3 1: List of models used in our experiments

	Name		classier	length_list	Description
	STC-1		Ridge classier	{3, 4, .., m}	STC-k with k = 1, mean-
							ing that shapelets are selected
							from a randomly selected time
							series per class
	STC-0.25		Ridge classier	{3, 4, .., m}	STC-k that select shapelets
							from 25% of time series per
							each class randomly selected
	STC-0.5		Ridge classier	{3, 4, .., m}	STC-k that select shapelets
							from 50% of time series per
							each class randomly selected
	STC-0.75		Ridge classier	{3, 4, .., m}	STC-k that select shapelets
							from 75% of time series per
							each class randomly selected
	STC		Ridge classier	{3, 4, .., m}	STC-k that select shapelets
							from every time series in the
							dataset
	SAST-RF		Random Forest	{3, 4, .., m}	SAST model using Random
							Forest classier
	SAST-Ridge	Ridge classier	{3, 4, .., m}	SAST model using Ridge clas-
							sier with LOO
	SAST-Ridge-A	Ridge classier	{9, 13, 15},	Approximated	SAST-Ridge,
					{7, 11, 15},	that is a SAST-Ridge which
					{7, 9, 15}	or	considers only some subse-
					{9, 11, 15}	quence lengths
	SASTEN-Ridge	Ridge classier	-		Ensemble of 3 SAST-Ridge
	SASTEN-Ridge-A	Ridge classier	-		Ensemble of 3 Approximated
							SAST-Ridge with length_list
							{3, 4, .., 9},	{10, 11, ..., 16},
							and	{17, 18, ..., 23} respec-
							tively
		Table 3.2: Average accuracy of each model per problem type
		HIVE-COTE	ROCKET		SAST	TS-CHIEF	Number of datasets
	Device	0.75 ± 0.0	0.73 ± 0.0		0.62 ± 0.0	0.76 ± 0.0	1
	ECG	0.95 ± 0.06	0.96 ± 0.05 0.93 ± 0.07	0.94 ± 0.07	4
	Image	0.82 ± 0.12	0.82 ± 0.12		0.78 ± 0.12 0.83 ± 0.12	25
	Motion	0.93 ± 0.09 0.93 ± 0.07	0.88 ± 0.1	0.93 ± 0.09	9
	Power	1.0 ± 0.0	0.94 ± 0.0		0.91 ± 0.0	0.99 ± 0.0	1
	Sensor	0.89 ± 0.12	0.9 ± 0.11		0.85 ± 0.14	0.89 ± 0.13	13
	Simulated	0.99 ± 0.02	1.0 ± 0.01		0.95 ± 0.04	1.0 ± 0.01	7
	Spectro	0.87 ± 0.11 0.87 ± 0.12 0.87 ± 0.11 0.87 ± 0.11	6
	Trac	0.98 ± 0.0	0.98 ± 0.0		0.96 ± 0.0	0.97 ± 0.0	1
	Average	0.88 ± 0.11	0.88 ± 0.11		0.84 ± 0.12	0.88 ± 0.12

  while neglecting explainability. In this chapter, we address this problem with explainability in mind.[START_REF] Gruber | [END_REF], Liu et al. 2021] and particularly uncertain time series. By using a single random instance from each class, SAST is more scalable and at least as accurate as STC while keeping STC interpretability capabilities.

	4.2. Uncertain Subsequence Transform Classication	77
	70% while providing faithful explanation similarly to STC. The rest of this chapter is
	organized as follows: we start by describing the uSAST method (Section 4.2). Then,
	we detail our experiments and the obtained results Section 4.3 before concluding this
	Chapter in Section 4.4.
	4.2 Uncertain Subsequence Transform Classication
	In this section, we describe a new uncertain time series classication method based
	on uncertainty propagation as in UST and subsequence transform as in SAST. In
	fact, uncertainty propagation is an eective approach to analyze uncertain data
	[
	We consider two approaches to classify uTS in an explainable manner : the rst
	one ignores uncertainty and uses only the best estimates, while the second one takes
	uncertainty into account. Ignoring uncertainty makes the task a regular time series
	classication task, allowing the usage of Shapelet Transform Classication or simply
	STC [Hills et al. 2014], an eective and explainable regular time series classication
	algorithm. This model failed to nd a valid shapelet on PLAsTiCC, and therefore
	could not perform the classication task. We performed extensive hyper-parameter
	tuning tests, but the result was the same. We also tried to take uncertainty into
	account by using the Uncertain Shapelet Transform algorithm, but as expected, this
	method also failed since it is an extension of STC for uncertain time series.
	In this chapter, we propose the Uncertain Scalable and Accurate Subsequence
	Transform (or uSAST for short) method which is able to achieve an F1-score of

Table 4 .

 4 1 shows the result using the XGBoost classier only as it has led to the best classication performance. However, detailed results are available in Appendix B. Table4.1: Results on PLAsTiCC averaged over 3 runs.The rst observation is that any variant of our proposed method is able to achieve around 70% precision, recall and F1 score, unlike shapelet-based methods which completely failed on the PLAsTiCC dataset. This result corroborates with the claim that pruning subsequences before the eective classication could sometimes lead to poor performance. Dropping duplicates, counting patterns frequency or doing both does not have signicant impact on the classication performance. However, dropping duplicate makes the models faster. In particular, uSASTd is about 12 hours faster than uSAST. Counting pattern frequency does not add a computation overhead because it is done while computing the distance in O(1) time.Choosing the right subsequence lengths to considered is challenging and assessing all possible values is computationally expensive; However, domain knowledge could guide in setting this parameter as it is application-dependent.PLAsTiCC contains objects that are either galactic or extra-galactic, and whose light curves were obtained following a Deep Drilling Fields (DDF) or Wide Fast Deep (WFD) observation strategy. Extra-galactic objects are further away than galactic ones, they are fainter and more dicult to be observed. DDF light curves contain more frequent observation points than WFD ones. Thus, DDF light curves provide a more certain determination of the time series properties than their WFD counterparts which have more uncertainties. Table4.2 gives the performances of the model uSASTd regarding if the objects are galactic or not, DDF or WFD. The model is considerably better at classifying galactic objects than extra-galactic ones, and a little better at classifying DDF objects than WFD ones. While the model achieves an F1 score of 94% for galactic objects in DDF, it achieves an F1 score of only 67% for extra-galactic objects in WFD. This is directly related to the astrophysical nature of

		Precision	Recall	F1 score	LogLoss	Time (h)
	uSAST	0.72 ± 0.01	0.72 ± 0.00	0.69 ± 0.01	0.96 ± 0.01	51.03 ± 0.12
	uSASTd 0.72 ± 0.00 0.73 ± 0.00 0.70 ± 0.01 0.97 ± 0.01 43.49 ± 0.27
	uSASTdc	0.71 ± 0.01	0.72 ± 0.01	0.69 ± 0.01	0.96 ± 0.01	43.52 ± 0.72

Table 4 .

 4 3: Results on PLAsTiCC averaged over 3 runs when uncertainty is ignored.Taking uncertainty into account increases the classication performance in terms of precision, recall, F1 score and cross entropy loss. In fact, from SASTd to uSASTd, there is a gain of 6% in precision, 5% in recall, 6% in F1 score. It can also be seen that the model is more condent on its predictions as the loss has decreased. However, this gain in performance requires almost four times more computation. In fact, ROCKET uses the proportion of positive values obtained after applying random convolutions. MUSE uses bag of words obtained after applying some transformations to the time series. These features have no particular meaning for domain experts. Our method does not have this limitation, as it is based on features that are intelligible to domain experts.

		Precision	Recall	F1 score	LogLoss	Time (h)
	SAST	0.65 ± 0.01 0.67 ± 0.00 0.63 ± 0.00 1.16 ± 0.01 16.41 ± 0.52
	SASTd	0.66 ± 0.02 0.68 ± 0.00 0.64 ± 0.00 1.14 ± 0.00 12.79 ± 0.84
	SASTdc	0.66 ± 0.01 0.68 ± 0.00 0.64 ± 0.01 1.14 ± 0.01 12.99 ± 0.30
	4.3.2.4 Comparison to SOTA:
	In this subsection, we compare our proposed method to the state-of-the-art multi-
	variate time series classication methods ROCKET [Dempster et al. 2020], MUSE
	[Schäfer & Leser 2017b] and XEM [Fauvel et al. 2022] which have been shown to
	be among the most accurate methods for this task [Ruiz et al. 2021]. Results are
	shown in Table 4.4.
				Table 4.4: uSASTd vs SOTA results.
			Precision	Recall	F1 score	Time (h)
	uSASTd		0.72 ± 0.00 0.73 ± 0.00 0.70 ± 0.01 43.49 ± 0.27
	MUSE		0.71 ± 0.01 0.73 ± 0.01 0.71 ± 0.01 3.36 ± 0.04
	ROCKET	0.77 ± 0.00 0.77 ± 0.00 0.75 ± 0.00	0.05 ± 00
	XEM		0.69 ± 0.01 0.71 ± 0.00 0.69 ± 0.00 12.24 ± 0.46
	The classication performance of our method is comparable to those of the SOTA
	methods. In particular, uSASTd achieves better precision, recall and F1 score com-
	pared to XEM on PLAsTiCC. uSASTd and MUSE have similar classication perfor-

mance. ROCKET achieves the best classication performance. SOTA methods are faster than our proposal. Except for XEM which is explainable-by-design, SOTA methods are not explainable.

  Mbouopda, Emille E. O. Ishida, Engelbert Mephu Nguifo, Emmanuel Gangler. Explainable Classication of Astronomical Uncertain Time Series. HAL preprint, pp 1-8. 2022.

Table A .

 A 2: Accuracy of models on 72 UEA & UCR datasets (average over 5 runs). The numbers are rounded at 2 decimals.Continued on next pageTable A.2: Accuracy of models on 72 UEA & UCR datasets (average over 5 runs). The numbers are rounded at 2 decimals. Continued on next page A.2. Scalability of SAST, SASTEN and SASTEN-A regarding the dataset size 99 Table A.2: Accuracy of models on 72 UEA & UCR datasets (average over 5 runs). The numbers are rounded at 2 decimals.

			STC-1 STC-1	STC-0.25 STC-0.25	STC-0.5 STC-0.5		STC-0.75 STC-0.75	STC STC	SAST SAST
	0.71 ± 0.02 0.77 ± 0.01 0.76 ± 0.01 0.77 ± 0.01 0.77 ± 0.01 0.76 ± 0.02 60 0.75 ± 0.05 0.81 ± 0.02 0.82 ± 0.03 0.83 ± 0.02 0.91 ± 0.03 0.97 ± 0.01
	0.66 ± 0.01 61 0.58 ± 0.05	0.68 ± 0.02 0.61 ± 0.02	0.69 ± 0.01 0.59 ± 0.07		0.69 ± 0.03 0.6 ± 0.09	0.71 ± 0.01 0.83 ± 0.02	0.74 ± 0.01 0.88 ± 0.02
	0.67 ± 0.01 0.68 ± 0.01 0.68 ± 0.01 0.68 ± 0.01 0.68 ± 0.0 62 0.91 ± 0.05 0.63 ± 0.07 0.93 ± 0.02 0.93 ± 0.01 0.95 ± 0.01 0.95 ± 0.0 0.67 ± 0.02
	0.43 ± 0.03 63 0.87 ± 0.02	0.47 ± 0.02 0.97 ± 0.01	0.54 ± 0.02 0.97 ± 0.01		0.52 ± 0.04 0.97 ± 0.01	0.47 ± 0.04 0.98 ± 0.0	0.61 ± 0.04 0.98 ± 0.0
	0.61 ± 0.09 64 0.88 ± 0.04	0.68 ± 0.11 0.91 ± 0.02	0.8 ± 0.02 0.94 ± 0.01		0.77 ± 0.03 0.95 ± 0.0	0.81 ± 0.03 0.95 ± 0.0	0.9 ± 0.02 0.88 ± 0.04
	0.94 ± 0.05 65 0.84 ± 0.08	0.97 ± 0.0 0.9 ± 0.04	0.96 ± 0.0 0.87 ± 0.02		0.97 ± 0.01 0.89 ± 0.02	0.97 ± 0.01 0.88 ± 0.03	0.98 ± 0.01 0.88 ± 0.03
	0.74 ± 0.07 0.85 ± 0.02 0.84 ± 0.01 0.85 ± 0.01 66 0.94 ± 0.07 0.99 ± 0.01 1.0 ± 0.0 1.0 ± 0.0	0.84 ± 0.0 0.99 ± 0.0	0.84 ± 0.03 1.0 ± 0.0
	0.91 ± 0.01 67 0.93 ± 0.04	0.93 ± 0.01 0.95 ± 0.02	0.93 ± 0.01 0.98 ± 0.03		0.93 ± 0.01 0.99 ± 0.01	0.94 ± 0.0 0.98 ± 0.01	0.94 ± 0.0 0.96 ± 0.03
	0.92 ± 0.05 68 0.56 ± 0.07	1.0 ± 0.0 0.61 ± 0.05	1.0 ± 0.0 0.64 ± 0.07		1.0 ± 0.0 0.64 ± 0.03	1.0 ± 0.0 0.81 ± 0.03	1.0 ± 0.0 0.99 ± 0.0
	0.75 ± 0.0 69 0.83 ± 0.07	0.75 ± 0.0 0.93 ± 0.03	0.75 ± 0.0 0.97 ± 0.03		0.75 ± 0.0 0.96 ± 0.03	0.75 ± 0.0 0.98 ± 0.01 0.98 ± 0.01 0.68 ± 0.04
	0.32 ± 0.04 70 0.99 ± 0.01	0.32 ± 0.07 1.0 ± 0.0	0.31 ± 0.05 1.0 ± 0.01		0.34 ± 0.05 1.0 ± 0.0	0.32 ± 0.03 1.0 ± 0.0	0.62 ± 0.01 1.0 ± 0.0
	0.43 ± 0.04 71 0.54 ± 0.06	0.46 ± 0.03 0.71 ± 0.1	0.44 ± 0.04 0.72 ± 0.07		0.47 ± 0.03 0.8 ± 0.04	0.74 ± 0.01 0.8 ± 0.06	0.78 ± 0.01 0.85 ± 0.06
	72	0.96 ± 0.06 0.4 ± 0.01	0.95 ± 0.03 0.45 ± 0.02	0.96 ± 0.06 0.47 ± 0.02		0.99 ± 0.01 0.44 ± 0.01	0.99 ± 0.01 0.56 ± 0.01	1.0 ± 0.01 0.7 ± 0.01
			0.71 ± 0.04	0.88 ± 0.01	0.92 ± 0.01		0.93 ± 0.01	0.94 ± 0.0	0.95 ± 0.0
			0.33 ± 0.06	0.29 ± 0.03	0.31 ± 0.02		0.31 ± 0.03	0.59 ± 0.01	0.77 ± 0.0
			0.95 ± 0.09	0.97 ± 0.03	0.96 ± 0.03		0.96 ± 0.03	0.97 ± 0.01	0.98 ± 0.01
			0.93 ± 0.1	0.91 ± 0.13	0.86 ± 0.17		0.87 ± 0.08	0.93 ± 0.03	0.73 ± 0.01
			0.0 ± 0.0	0.0 ± 0.0	0.0 ± 0.0		0.0 ± 0.0	0.0 ± 0.0	0.9 ± 0.0
			0.79 ± 0.05	0.94 ± 0.06	0.97 ± 0.02		0.96 ± 0.03	0.97 ± 0.02 0.97 ± 0.02
			0.84 ± 0.03	0.96 ± 0.01	0.97 ± 0.0		0.98 ± 0.0	0.97 ± 0.0	0.97 ± 0.0
			0.89 ± 0.05	0.97 ± 0.01	0.97 ± 0.01		0.98 ± 0.01	0.97 ± 0.01	0.99 ± 0.01
			0.75 ± 0.03	0.93 ± 0.02	0.95 ± 0.01	0.96 ± 0.01	0.95 ± 0.01	0.96 ± 0.02
			0.62 ± 0.06 0.72 ± 0.02 0.72 ± 0.04		0.7 ± 0.01	0.7 ± 0.02	0.71 ± 0.03
			0.59 ± 0.07	0.57 ± 0.04	0.58 ± 0.02		0.57 ± 0.06	0.62 ± 0.03	0.6 ± 0.04
			0.53 ± 0.02	0.56 ± 0.01	0.56 ± 0.01		0.54 ± 0.01	0.62 ± 0.0	0.56 ± 0.01
			STC-1 0.91 ± 0.06 0.63 ± 0.1	STC-0.25 0.96 ± 0.0 0.96 ± 0.01 0.96 ± 0.0 STC-0.5 STC-0.75 0.84 ± 0.04 0.77 ± 0.02 0.87 ± 0.03	STC 0.96 ± 0.0 0.96 ± 0.01 SAST 0.87 ± 0.06 0.92 ± 0.02
	1		0.29 ± 0.06 0.54 ± 0.02	0.32 ± 0.03 0.59 ± 0.03	0.34 ± 0.04 0.56 ± 0.01		0.34 ± 0.02 0.58 ± 0.02	0.48 ± 0.04 0.66 ± 0.01	0.68 ± 0.0 0.68 ± 0.01
	2		0.63 ± 0.06 0.3 ± 0.04	0.71 ± 0.08 0.3 ± 0.07	0.74 ± 0.03 0.3 ± 0.03		0.72 ± 0.04 0.28 ± 0.01	0.75 ± 0.03 0.72 ± 0.02	0.77 ± 0.02 0.87 ± 0.0
	3	0.65 ± 0.1 0.62 ± 0.02	0.68 ± 0.05 0.6 ± 0.01	0.86 ± 0.05 0.6 ± 0.02		0.95 ± 0.02 0.61 ± 0.02	0.87 ± 0.03 0.61 ± 0.02	0.87 ± 0.02 0.53 ± 0.02
	4		0.44 ± 0.05 0.57 ± 0.0	0.47 ± 0.09 0.65 ± 0.05	0.55 ± 0.09 0.66 ± 0.04		0.65 ± 0.06 0.62 ± 0.04	0.71 ± 0.09 0.65 ± 0.06	0.8 ± 0.02 0.83 ± 0.01
	5		0.74 ± 0.06 0.57 ± 0.02	0.79 ± 0.09 0.58 ± 0.02	0.78 ± 0.09 0.56 ± 0.01		0.77 ± 0.07 0.58 ± 0.01	0.78 ± 0.05 0.59 ± 0.02	0.8 ± 0.03 0.56 ± 0.02
	6		0.76 ± 0.1 0.8 ± 0.06	0.76 ± 0.1 0.79 ± 0.05	0.91 ± 0.04 0.85 ± 0.02	0.83 ± 0.14 0.87 ± 0.02	0.86 ± 0.1 0.89 ± 0.01	0.76 ± 0.1 0.85 ± 0.03
	7		0.88 ± 0.09 0.64 ± 0.01	0.95 ± 0.01 0.64 ± 0.01	0.96 ± 0.01 0.64 ± 0.0		0.96 ± 0.01 0.64 ± 0.0	0.95 ± 0.01 0.65 ± 0.01	0.98 ± 0.01 0.78 ± 0.01
	8		0.66 ± 0.04 0.97 ± 0.02	0.75 ± 0.02 0.99 ± 0.0	0.74 ± 0.02 1.0 ± 0.0		0.76 ± 0.03 1.0 ± 0.0	0.77 ± 0.06 1.0 ± 0.0	0.88 ± 0.01 1.0 ± 0.0
	9		0.91 ± 0.08 0.76 ± 0.03	0.95 ± 0.02 0.93 ± 0.02	0.95 ± 0.03 0.92 ± 0.02		0.96 ± 0.01 0.93 ± 0.02	0.97 ± 0.01 0.94 ± 0.02	0.96 ± 0.01 0.91 ± 0.02
	10 0.54 ± 0.02 0.85 ± 0.01	0.54 ± 0.01 0.85 ± 0.01	0.54 ± 0.01 0.86 ± 0.01		0.56 ± 0.0 0.85 ± 0.01	0.56 ± 0.0 0.86 ± 0.01	0.75 ± 0.04 0.85 ± 0.0
	11 0.96 ± 0.03 0.71 ± 0.03	0.99 ± 0.02 0.76 ± 0.03	0.99 ± 0.03 0.75 ± 0.04		1.0 ± 0.0 0.76 ± 0.01	1.0 ± 0.0 0.82 ± 0.02	1.0 ± 0.0 0.87 ± 0.01
	12 0.38 ± 0.04 0.77 ± 0.02 0.78 ± 0.01 0.78 ± 0.01 0.78 ± 0.0 0.35 ± 0.03 0.35 ± 0.01 0.38 ± 0.03	0.66 ± 0.02 0.77 ± 0.01	0.77 ± 0.01 0.78 ± 0.01
	13 0.41 ± 0.04 0.82 ± 0.15	0.36 ± 0.04 0.92 ± 0.06	0.35 ± 0.03 0.98 ± 0.01		0.42 ± 0.05 0.98 ± 0.02	0.64 ± 0.02 1.0 ± 0.0	0.74 ± 0.01 0.96 ± 0.01
	14 0.41 ± 0.06 0.68 ± 0.05	0.4 ± 0.06 0.91 ± 0.01	0.4 ± 0.03 0.94 ± 0.01	0.38 ± 0.03 0.95 ± 0.01 0.95 ± 0.01 0.69 ± 0.01	0.77 ± 0.01 0.91 ± 0.02
	15	0.08 ± 0.0 0.7 ± 0.14	0.08 ± 0.0 0.82 ± 0.03	0.08 ± 0.0 0.81 ± 0.02		0.08 ± 0.0 0.78 ± 0.05	0.08 ± 0.0 0.79 ± 0.04	0.73 ± 0.0 0.76 ± 0.05
	16	0.9 ± 0.03 0.75 ± 0.05	0.87 ± 0.06 0.84 ± 0.03	0.91 ± 0.04 0.86 ± 0.05		0.93 ± 0.02 0.83 ± 0.03	0.94 ± 0.04 0.88 ± 0.01	0.97 ± 0.0 0.85 ± 0.04

A.2 Scalability of SAST, SASTEN and SASTEN-A regarding the dataset size

https://github.com/frankl1/ustc/releases/tag/litsa

https://lsst.org/

Cleaned dataset: https://drive.uca.fr/f/f0741be3fb77402f8e82/

Source code: https://anonymous.4open.science/r/usast-FBC0/

work and for their constructive feedback, my family for their inestimable support, my friends. This work has been funded by the French Ministry of Higher Education, Research and Innovation, the LabEx IMobS3 and the CNRS PEPS project TransiXplore. Thank to the UEA & UCR Time Series Classication Repository which provides

List of Tables 1.1 Summary of the current time series classication state-of-the-art

Explainable Classication of Astronomical Uncertain Time Series

Exploring the expansion history of the universe, understanding its evolutionary stages, and predicting its future evolution are important goals in astrophysics. Today, machine learning tools are used to help achieving these goals by analyzing transient sources, which are modeled as uncertain time series. In this chapter, we propose an uncertainty-aware subsequence based model which achieves a classication comparable to that of state-of-the-art methods. Unlike conformal learning which estimates model uncertainty on predictions, our method takes data uncertainty as additional input. Moreover, our approach is explainable-by-design, giving domain experts the ability to inspect the model and explain its predictions. The explainability of the proposed method has also the potential to inspire new developments in theoretical astrophysics modeling by suggesting important subsequences which depict details of light curve shapes. In this work, we considered the case were input time series were uncertain while the labels were certain. In their current form, our proposed methods cannot be applied in scenarios where the labels are also uncertain. Given that this scenarios is likely to arise in practice, it is important to adapt or extend UST and uSAST to this case. A possible way of tackling this issue is to use belief function theory as proposed in [START_REF] Quost | Learning from data with uncertain labels by boosting credal classiers[END_REF]. Furthermore, it would be interesting to evaluate the condence of our methods on their predictions using conformal learning techniques. We expect our methods' condence to be correlated with the uncertainty level, that is, the more uncertain is the data, the less condent our model would be.

Combining conformal learning with the explainability of our methods will increase their trustability and adoption by end-users.

The last future direction, but not the least is to explore other time series analysis tasks. In particular, it would be worthy to see how our proposed uncertain similarity measure UED is compared to FOTS for the task of uncertain time series clustering.

Beyond that, assessing the performance of uncertainty propagation in the tasks of uncertain time series anomaly detection and forecasting would be good steps to advance the state-of-the-art of uncertain time series analysis in general.

Recommendations

Uncertain time series classication and more generally the classication of uncertain data is challenging, yet under-explored. We shown in this work that uncertainty is not necessarily a problem, but an additional input that can be used to improve the classication performance and the decision boundaries' robustness. We also hope that uncertainty quantication will be integrated in the data collection process so that the nal data is released with the associated uncertainty.

List of publications

During this thesis, we made many publications on the topic of uncertain time series