Adeline Fermanian
email: adeline.fermanian@upmc.fr

Embedding and learning with signatures

published or not. The documents may come

Introduction

Sequential or temporal data are arising in many fields of research, due to an increase in storage capacity and to the rise of machine learning techniques. An illustration of this vitality is the recent relaunch of the Time Series Classification repository [START_REF] Bagnall | The uea & ucr time series classification repository[END_REF], with more than a hundred new datasets. Sequential data are characterized by the fact that each sample consists of an ordered array of values. Although the ordering often corresponds to time, it is not always the case. For example, text documents or DNA sequences have an intrinsic ordering, and can, therefore, be considered as sequential. Besides, when time is involved, several values can be recorded simultaneously, giving rise to an ordered array of vectors, which is, in the field of time series, often referred to as multidimensional time series. To name only a few domains, market evolution is described by financial time series, and physiological variables (e.g., electrocardiograms, electroencephalograms...) are recorded simultaneously in medicine, yielding multidimensional time series. We can also mention smartphone and GPS sensors data, or character recognition problems, where data has both a spatial and temporal aspect. These high-dimensional datasets open up new theoretical and practical challenges, as both algorithms and statistical methods need to be adapted to their sequential nature.

For the past decades, different communities have addressed this problem. First, time series forecasting has been an active area of research in statistics since the 1950s, resulting in several monographs, such as [START_REF] Hamilton | Time Series Analysis[END_REF] or [START_REF] Box | Time Series Analysis: Forecasting and Control[END_REF], to which we refer the reader for an overview of the domain. In essence, time series are considered as realizations of various stochastic processes, the most famous being ARIMA models. Much work in this field has been done on parameter estimation and model selection. These models have been developed for univariate time series but have been extended to the multivariate case (L ütkepohl, 2005), with the limitation that they become more complicated and harder to fit. More recently, the field of functional data analysis has extended traditional statistical methods, in particular regression and Principal Components Analysis, to functional inputs. The monographs by [START_REF] Ramsay | Functional Data Analysis[END_REF] and [START_REF] Ferraty | Nonparametric Functional Data Analysis: Theory and Practice[END_REF] will provide the reader with introductions to the area. However, methods from both time series and functional data analysis rely on strong assumptions on the regularity of the data and need to be adapted to each specific application. Therefore, modern datasets have highlighted their limitations: a lot of choices, in basis functions or model parameters, need to be handcrafted and are valid only on a small-time range. Moreover, these techniques struggle to model multidimensional series, in particular, to incorporate information about interactions between various dimensions.

On the other side, time series classification has aroused the interest of the data mining community. A broad range of algorithms have been developed, reviewed by [START_REF] Bagnall | The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances[END_REF] in the univariate case. Much attention has been paid to the development of similarity measures adapted to temporal data, a popular baseline being the Dynamic Time Wrapping transform [START_REF] Berndt | Finding patterns in time series: a dynamic programming approach[END_REF], followed by a 1-nearest neighbor algorithm. [START_REF] Bagnall | The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances[END_REF] state that this baseline is beaten only by ensemble strategies, which combine different feature mappings. However, a great limitation of these methods is their complexity, as they have difficulty handling large time series. Recently, deep learning seems to be a promising approach and solves some problems mentioned above. For example, [START_REF] Fawaz | Deep learning for time series classification: a review[END_REF] claim that some architectures perform systematically better than previous data mining algorithms. Nevertheless, deep learning methods are costly in memory and computing power, and often require a lot of training data.

Our goal in the present article is to discuss a novel approach for sequential learning, called the signature method, and coming from rough path theory. Its main idea is to summarize temporal or sequential inputs by the graded feature set of their iterated integrals, the signature. Note that, in rough path theory, functions are referred to as paths, to insist on their geometrical aspects. Indeed, the importance of iterated integrals had been noticed by geometers in the 60s, as presented in the seminal work of [START_REF] Chen | Integration of paths-a faithful representation of paths by non-commutative formal power series[END_REF]. It has been rediscovered by [START_REF] Lyons | Differential equations driven by rough signals[END_REF] in the context of stochastic analysis and controlled differential equations, and is at the heart of rough path theory. This theory, of which [START_REF] Lyons | Differential Equations driven by Rough Paths[END_REF] and [START_REF] Friz | Multidimensional Stochastic Processes as Rough Paths: Theory and Applications[END_REF] give a recent account, focuses on developing a new notion of paths to make sense of evolving irregular systems. Notably, [START_REF] Hairer | Solving the KPZ equation[END_REF] was awarded a Fields medal in 2014 for its solution to the Kardar-Parisi-Zhang equation built with rough path theory. In this context, it has been shown that the signature provides an accurate summary of a path and allows to obtain arbitrarily good linear approximations of continuous functions of paths. Therefore, assuming we want to learn an output Y ∈ R, which depends on a random path X : [0, 1] → R d , rough path theory suggests that the signature is a relevant feature set to describe X.

As can be expected, the signature has recently received the attention of the machine learning community and has achieved a series of successful applications. To cite some of them, [START_REF] Yang | Deepwriterid: An end-to-end online text-independent writer identification system[END_REF] have achieved state-of-the-art results for handwriting recognition with a recurrent neural network combined with signature features. [START_REF] Graham | Sparse arrays of signatures for online character recognition[END_REF] have used the same approach for character recognition, and Gyurk ó et al. ( 2014) have coupled Lasso with signature features for financial data streams classification. [START_REF] Kormilitzin | Application of the signature method to pattern recognition in the cequel clinical trial[END_REF] have investigated its use for the detection of bipolar disorders, and [START_REF] Yang | Leveraging the path signature for skeleton-based human action recognition[END_REF] for human action recognition.

For a gentle introduction to the signature method in machine learning, we refer the reader to [START_REF] Chevyrev | A primer on the signature method in machine learning[END_REF].

However, despite many promising empirical successes, a lot of questions remain open, both practical and theoretical. In particular, to compute the signature, it is necessary to embed discretely sampled data points into paths. While authors use different approaches, this embedding is only mentioned in some articles, and rarely discussed. Thus, our purpose in this paper is to take a step forward in understanding how signature features should be constructed for machine learning tasks, with a special focus on the embedding step. Our document is organized as follows.

(i) First, in Section 2, we give a brief exposition of the signature definition and properties, along with a survey of different approaches undertaken in the literature to combine signatures with machine learning algorithms. Datasets used throughout the paper are also presented in Section 3.

(ii) Then, we review in Section 4 potential embeddings and compare their predictive performance. We emphasize that the embedding is as a crucial step as the algorithm choice since it can drastically change accuracy results. Moreover, we point out that one embedding, called lead-lag, performs systematically better than others, and this consistently other different datasets and learning algorithms.

(iii) Furthermore, we investigate in Section 5 the choice of signature domain. Indeed, signatures can be computed on any sub-interval of the path definition domain, and it is natural to wonder whether some local information is lost when signatures of the whole path are computed. We end the section by showing that, with a good embedding, the signature combined with a simple algorithm, such as a random forest classifier, obtains results comparable to state-of-the-art approaches in different application areas, while remaining a generic approach and computationally simple.

(iv) Finally, we discuss in Section 6 some open questions that we find worth investigating in future work.

Our empirical results are based on three recent datasets, in different fields of application. One is a univariate sound recording dataset, called Urban Sound [START_REF] Salamon | A dataset and taxonomy for urban sound research[END_REF], whereas the others are multivariate. One has been made available by [START_REF] Google | The quick, draw! dataset[END_REF], and consists of drawing trajectories, while the other is made up of 12 channels recorded from smartphone sensors [START_REF] Malekzadeh | Protecting sensory data against sensitive inferences[END_REF]. They are each of a different nature and present a variety of lengths, noise levels, and dimensions. In this way, we intend to get generic results, independent of particular domain-specific aspects of the data. The code generating results of Sections 4 and 5 is available at https://github.com/afermanian/embedding_with_signatures.

A first glimpse of the signature method

Definition and main properties

We introduce in this subsection the notion of signature and review some of its important properties. The reader is referred to [START_REF] Lyons | Differential Equations driven by Rough Paths[END_REF] or [START_REF] Friz | Multidimensional Stochastic Processes as Rough Paths: Theory and Applications[END_REF] for a more involved mathematical treatment with proofs. Throughout the article, our basic objects are paths, that is functions from [0, 1] to R d , where d ∈ N * . The main assumption is that these paths are of bounded variation, i.e., they have finite length.

Definition 1 Let

X : [0, 1] -→ R d t -→ (X 1 t , . . . , X d t ).
The total variation of X is defined by

X 1-var = sup D ∑ t i ∈D X t i -X t i-1 ,
where the supremum is taken over all finite partitions

D = (t 0 , . . . , t k ) | k ≥ 1, 0 = t 0 < t 1 < • • • < t k-1 < t k = 1 of [0, 1]
, and • denotes the Euclidean norm on R d . The path X is said to be of bounded variation if its total variation is finite.

The set of bounded variation paths is exactly the set of functions whose first derivatives exist almost everywhere. Being of bounded variation is therefore not a particularly restrictive assumption. It contains, for example, all Lipschitz functions. In particular, if X is continuously differentiable, and Ẋ denotes its first derivative with respect to t, then

X 1-var = 1 0 Ẋt dt.
The assumption of bounded variation allows to define Riemann-Stieljes integrals along paths. We do not give a detailed exposition of this integration theory here, but we refer the interested reader to [START_REF] Lyons | Differential Equations driven by Rough Paths[END_REF]. From now on, we assume that the integral of a continuous path

Y : [0, 1] → R d against a path of bounded variation X : [0, 1] → R d is well-defined on any [s, t] ⊂ [0, 1], and denoted by t s Y u dX u =     t s Y 1 u dX 1 u . . . t s Y d u dX d u     ∈ R d ,
where X = (X 1 , . . . , X d ), and Y = (Y 1 , . . . , Y d ). When X is continuously differentiable, this integral is equal to the standard Riemann integral, that is,

t s Y u dX u = t s Y u Ẋu du.
As an example, assume that X is linear, i.e.,

X t = (X 1 t , . . . , X d t ) = (a 1 + b 1 t, . . . , a d + b d t), 0 ≤ t ≤ 1, a 1 , . . . , a d , b 1 , . . . b d ∈ R. (1) Then, t s dX u = t s Ẋu du =     t s b 1 du . . . t s b d du     =    b 1 (t -s) . . . b d (t -s)    .
The formula above is useful, since in practice we only compute the integral of linear paths, as discussed later in this subsection. We are now in a position to define the signature.

Definition 2 Let X : [0, 1] → R d be a path of bounded variation, I = (i 1 , . . . , i k ) ⊂ {1, . . . d} k , k ∈ N * , be a multi-index of length k, and [s, t] ⊂ [0, 1] be an interval. The signature coefficient of X corresponding to the index I on [s, t] is defined by

S I (X) [s,t] = • • • s≤u 1 <•••<u k ≤t dX i 1 u 1 . . . dX i k u k = t s t u 1 t u 2 • • • t u k-1 dX i k u k dX i 2 u 2 dX i 1 u 1 . (2)
S I (X) [s,t] is then said to be a signature coefficient of order k.

The signature of X is the sequence containing all signature coefficients, i.e.,

S(X) [s,t] = 1, S (1) (X) [s,t] , . . . , S (d) (X) [s,t] , S (1,1) (X) [s,t] , S (1,2) (X) [s,t] , . . . , S (i 1 ,...,i k ) (X) [s,t] , . . . .
The signature of X truncated at order K, denoted by S K (X), is the sequence containing all signature coefficients of order lower than or equal to K, that is

S K (X) [s,t] = 1, S (1) (X) [s,t] , S (2) (X) [s,t] , . . . , S K (d, . . . , d) (X) [s,t] .
For simplicity, when [s, t] = [0, 1], we omit the interval in the notations, and, e.g., write S K (X) instead of S K (X) [0,1] . Before giving an example of signature, some comments are in order. First, we note that, for a path in R d , there are d k coefficients of order k. The signature truncated at order K is therefore a vector of dimension

K ∑ k=0 d k = d K+1 -1 d -1 if d = 1,
and K + 1 if d = 1. Unless otherwise stated, we assume that d = 1, as this is in practice usually the case. Thus, the size of S K (X) increases exponentially with K, and polynomially with dsome typical values are presented in Table 1. The set of coefficients of order k can be seen as an element of the kth tensor product of R d with itself, denoted by (R d ) ⊗k . For example, we can write the d coefficients of order 1 as a vector, and the d 2 coefficients of order 2 as a matrix, i.e.,    S (1) (X) . . .

S (d) (X)    ∈ R d ,    S (1,1) (X) . . . S (1,d) (X) . . . . . . S (d,1) (X) . . . S (d,d) (X)    ∈ R d×d ≈ (R d ) ⊗2 .
Similarly, coefficients of order 3 can be written as a tensor of order 3, and so on. Then, S(X) can be seen as an element of the tensor algebra

R ⊕ R d ⊕ (R d ) ⊗2 ⊕ • • • ⊕ (R d ) ⊗k ⊕ • • • .
This structure of tensor algebra will not be used in the present article but is extremely useful to derive properties of the signature [START_REF] Lyons | Differential equations driven by rough signals[END_REF][START_REF] Friz | Multidimensional Stochastic Processes as Rough Paths: Theory and Applications[END_REF][START_REF] Hambly | Uniqueness for the signature of a path of bounded variation and the reduced path group[END_REF]. Finally, it should be noted that, due to the ordering in the integration domain in (2), signature coefficients are not symmetric. For example, S (1,2) (X) is a priori not equal to S (2,1) (X).

As a toy example, let us consider the linear path (1) again, and assume for simplicity that d = 2:

X t = X 1 t X 2 t = a 1 + b 1 t a 2 + b 2 t . d = 2 d = 3 d = 6 K = 1 2 3 6 K = 2 6 12 42 K = 5 62 363 9330 K = 7 254 3279 335922
Table 1: Typical sizes of S K (X) for different values of K and d, where

X : [0, 1] → R d .
Then, for any [s, t] ⊂ [0, 1] the signature coefficients of order 1 are

S (1) (X) [s,t] = t s dX 1 u = b 1 (t -s) and S (2) (X) [s,t] = t s dX 2 u = b 2 (t -s).
The first coefficient of order 2 is

S (1,1) (X) [s,t] = t s t u 1 dX 1 u 2 dX 1 u 1 = t s t u 1 b 2 1 du 2 du 1 = b 2 1 t s (t -u 1 )du 1 = b 2 1 (t -s) 2 2 .
Similarly,

S (1,2) (X) [s,t] = S (2,1) (X) = b 1 b 2 (t -s) 2 2 and S (2,2) (X) [s,t] = b 2 2 (t -s) 2 2 .
For any index I = (i 1 , . . . , i k ) ⊂ {1, 2} k , we easily obtain

S (i 1 ,...,i k ) (X) [s,t] = • • • s≤u 1 <•••<u k ≤t dX i 1 u 1 . . . dX i k u k = b i 1 . . . b i k (t -s) k k! . (3)
A crucial feature of the signature is that it encodes geometric properties of the path. Indeed, it is clear that coefficients of order 2 correspond to some areas outlined by the path, as shown in Figure 1. For higher orders of truncation, the signature contains information about the joint evolution of tuples of coordinates (see, e.g., [START_REF] Yang | Leveraging the path signature for skeleton-based human action recognition[END_REF]. Furthermore, the signature possesses several properties that make it a good statistical summary of paths, as shown in the next four propositions.

Proposition 1 Let X : [0, 1] → R d be a path of bounded variation, and ψ :

[0, 1] → [0, 1] be a non-decreasing surjection. Then, if X t = X ψ(t) is the reparametrization of X under ψ, S( X) = S(X).
This proposition is a consequence of the properties of integrals and bounded variation paths (Friz and Victoir, 2010, Proposition 7.10). In other words, the signature of a path is the same up to any reasonable time change. There is, therefore, no information about the path travel time in signature coefficients. However, when relevant for the application, it is possible to include this information by adding the time parametrization as a coordinate of the path. This procedure plays a crucial role in the construction of time embeddings, which will be thoroughly discussed in Section 4.

A second important property is a condition ensuring uniqueness of signatures.

Proposition 2 If X has at least one monotonous coordinate, then S(X) determines X uniquely. It should be noticed that having a monotonous coordinate is a sufficient condition, but a necessary one can be found in the monograph by [START_REF] Hambly | Uniqueness for the signature of a path of bounded variation and the reduced path group[END_REF], together with a proof of the proposition. The principal significance of this result is that it provides a practical procedure to guarantee signature uniqueness: it is sufficient to add a monotonous coordinate to the path X. For example, the time embedding mentioned above will satisfy this condition.

This result does not provide a practical procedure to reconstruct a path from its signature. However, this is an active area of research [START_REF] Chang | Signature inversion for monotone paths[END_REF][START_REF] Lyons | Differential equations driven by rough signals[END_REF]Xu, 2017, 2018). In particular, [START_REF] Lyons | Hyperbolic development and inversion of signature[END_REF] derive an explicit expression of rectilinear paths, defined in Section 4.1, in terms of their signatures; and Lyons and Xu (2018) construct, from the signature of a C 1 path, a sequence of piecewise linear approximations converging to the initial path.

The next proposition reveals that the signature linearizes functions of X. We refer the reader to Király and Oberhauser (2019, Theorem 1) for a proof.

Proposition 3 Let D be a compact subset of the space of bounded variation paths from [0, 1] to R d . Let f : D → R be continuous. Then, for every > 0, there exists N ∈ N, w ∈ R N , such that, for any X ∈ D, f (X)w, S(X) ≤ , where •, • denotes the Euclidean scalar product on R N .

This proposition is a consequence of the Stone-Weierstrass theorem. The classical Weierstrass approximation theorem states that every real-valued continuous function on a closed interval can be uniformly approximated by a polynomial function. Similarly, we obtain here that any real-valued continuous function on a compact subset D of bounded variation paths can be uniformly approximated by a linear form on the signature. Linear forms on the signature can, therefore, be thought of as the equivalent of polynomial functions for paths.

Finally, Chen's theorem [START_REF] Chen | Integration of paths-a faithful representation of paths by non-commutative formal power series[END_REF]) provides a formula to compute recursively the signature of a concatenation of paths. Let

X : [s, t] → R d and Y : [t, u] → R d be two paths, 0 ≤ s < t < u ≤ 1, the concatenation of X and Y, denoted by X * Y, is defined as the path from [s, u] to R d such that, for any v ∈ [s, u], (X * Y) v = X v if v ∈ [s, t], X t + Y v -Y t if v ∈ [t, u].
Proposition 4 (Chen) Let X : [s, t] → R d and Y : [t, u] → R d be two paths with bounded variation. Then, for any multi-index (i 1 , . . . , i k ) ⊂ {1, . . . , d} k ,

S (i 1 ,...,i k ) (X * Y) = k ∑ =0 S (i 1 ,...,i ) (X) • S (i +1 ,...,i k ) (Y). ( 4
)
This proposition is an immediate consequence of the linearity property of integrals (Lyons et al., 2007, Theorem 2.9). However, it is essential for the explicit calculation of signatures. Indeed, in practice, since we are given a finite number of observations sampled from X, we must interpolate these points, which yields a continuous piecewise linear path. To compute its signature, it is then sufficient to iterate the following two steps:

1. Compute with equation ( 3) the signature of a linear section of the path.

Concatenate it to the other pieces with Chen's formula (4).

This procedure is implemented in the Python library iisignature [START_REF] Reizenstein | The iisignature library: efficient calculation of iterated-integral signatures and log signatures[END_REF]. Thus, for a sample consisting of p points in R d , if we consider the path formed by their linear interpolation, the computation of the path signature truncated at level K takes O(pd K ) operations. The complexity is therefore linear in the number of sampled points but exponential in the truncation order K. Notice that the size of the signature vector is also exponential in the truncation order K, as shown in Table 1. Therefore, in applications, K is constrained to remain small, typically of order less than 10.

Signature and machine learning

Now that we have presented the signature and its properties, we focus on its use in machine learning. In this context, we place ourselves in a statistical framework, and assume that our goal is to understand the relationship between a random input path X : [0, 1] → R d and a random output Y ∈ R. In a classical setting, we would be given a sample of independent and identically distributed (i.i.d.) observations (X 1 , Y 1 ), . . . , (X n , Y n ) , drawn from (X, Y). However, in applications, we only observe a realization X i sampled at a discrete set of times 0 ≤ t 1 < • • • < t p i ≤ 1, p i ∈ N * . Therefore, we are given an i.i.d. sample

(x 1 , Y 1 ), . . . , (x n , Y n ) , where x i takes the form of a matrix, i.e.,

x i =     x 1 i,1 . . . x 1 i,p i . . . . . . x d i,1 . . . x d i,p i     ∈ R d×p i .
(5)

In this notation, x k i,j denotes the kth coordinate of the ith sample observed at time t j . If d = 1, we are in a classical setting of time series, where each sample is sampled in a finite number of points. However, d may here differ from 1, so we find ourselves in a more general situation where we want to learn from multidimensional time series. Moreover, it is worth noting the dependence of the number of sampled points p i on i. In other words, each observation may have a different length. The signature dimension being independent of the number of sampled points, representing time series by their signature naturally handles inputs of various lengths, whereas traditional methods often require them to be normalized to a fixed length. To sum up, the signature method is appropriate for learning with discretely sampled multidimensional time series, possibly of different lengths.

As an example, we consider the Google dataset Quick, Draw! [START_REF] Google | The quick, draw! dataset[END_REF]. It consists of pen trajectories of millions of drawings, divided into 340 classes. Some samples are drawn in Figure 2. In this case, we see that the y i 's are discrete labels of the drawing's class, and the x i 's are matrices of pen coordinates. Therefore, in this example, d = 2 and p i varies for each drawing, but is typically in the order of a few dozen points. As discussed in the introduction, to use signature features, one needs to embed the observations x i into paths of bounded variation X i : [0, 1] → R d . This step, which also consists of adding other coordinates, such as time, will be thoroughly discussed in Section 4. Therefore, we assume for the moment that we are given a set of embeddings X i , 1 ≤ i ≤ n, from which signature features can be computed. When an embedding has been chosen, one can compute signature features and use them in combination with a learning algorithm. The procedure can be summarized as follows:

Raw data -→ Embedding -→ Signature features -→ Algorithm.

The literature on the combination of signature features with learning algorithms can be divided into three groups. These groups correspond to the nature of the algorithm's input: it is either a vector, a sequence or an image. In the context of deep learning, this division matches the different classes of neural network architectures: feedforward, recurrent and convolutional networks. The latter only deals with input paths in R 2 , with applications such as characters or handwriting recognition.

The first approach is to compute the signature of X on its whole domain, that is on [0, 1]. In this way, X is mapped into a finite set of coefficients, that is then fed into a predictive algorithm, typically a feedforward neural network. This strategy is implemented by [START_REF] Yang | Leveraging the path signature for skeleton-based human action recognition[END_REF] for skeleton-based human action recognition. From a sequence of human joints' positions, the authors construct a high dimensional vector of signature coefficients, which is then the input of a small dense network. Gyurk ó et al. ( 2014); [START_REF] Lyons | A feature set for streams and an application to highfrequency financial tick data[END_REF] also apply this method to financial time series, combining it with Lasso and OLS regression. The procedure is illustrated in Figure 3. A second family of methods consists in describing the input path by a sequence of signature coefficients. There are several variants of this approach, and we present here in detail the one chosen by [START_REF] Wilson-Nunn | A path signature approach to online arabic handwriting recognition[END_REF] for Arabic handwriting recognition, for its simplicity and representativeness. To create a signature sequence, the time interval

[0, 1] is divided into a dyadic partition 0 ≤ 2 -q < • • • < j2 -q < • • • < (2 q -1)2 -q ≤ 1, (6)
where q ∈ N. By computing the signature truncated at order K on every dyadic interval [j2 -q , (j + 1)2 -q ], 0 ≤ j < 2 q , we obtain a sequence of 2 q signature vectors, each of dimension (d K+1 -1)/(d -1). This sequence is typically fed into a recurrent network, as illustrated in Figure 4. We recall that recurrent networks are a class of neural networks that handle sequential inputs by recursively applying the same transformations to elements of a sequence but keeping in memory previous computations, so that dependence between consecutive elements is taken into account. In our case, the whole approach boils down to transforming the original sequential data into another sequence of signature coefficients. Such a procedure may be surprising, as the original data could have been itself the input of a recurrent network, instead of being mapped into a new signature sequence. Moreover, in the process, the dimension of the input of the recurrent network has been increased from d to (d K+1 -1)/(d -1). However, [START_REF] Wilson-Nunn | A path signature approach to online arabic handwriting recognition[END_REF] show the superiority of this approach and several other authors have successfully carried out this type of method. For example, [START_REF] Lai | Online signature verification using recurrent neural network and length-normalized path signature descriptor[END_REF] achieve state-ofthe-art results in the problem of recognizing genuine signatures from forgeries, and Liu et al.

(2017) of distinguishing different writers. In both cases, they use a sliding window over the character rather than a dyadic partition of the time interval, but otherwise, have an approach similar to [START_REF] Wilson-Nunn | A path signature approach to online arabic handwriting recognition[END_REF]. Finally, a third group of authors have taken these ideas further and created images of signature coefficients. Their rationale is to mix temporal and pictorial aspects of the data. Indeed, assuming that the input path is a trajectory in R 2 , it can be turned into an image by forgetting its temporal aspect and setting the pixel values to 1 along the trajectory, and 0 elsewhere. Then, starting from this representation, a bunch of images are created, such that each image corresponds to a signature coefficient, as shown in Figure 5. This can be done in various ways. However, the general idea is to consider a sliding window following the path and to set the pixel value at the center of the window to be equal to the signature coefficient computed over the window. This procedure is repeated by shifting the window by 1, as shown in Figure 6 for times t 4 , t 5 and t 6 . If the signature is truncated at order K, this yields 2 K+1 -1 sparse gray pictures, which can then be the input of a convolutional neural network. [START_REF] Graham | Sparse arrays of signatures for online character recognition[END_REF] and [START_REF] Yang | Deepwriterid: An end-to-end online text-independent writer identification system[END_REF][START_REF] Yang | Chinese character-level writer identification using path signature feature, dropstroke and deep cnn[END_REF] have obtained significant accuracy improvements for character recognition and writer identification with this approach. To sum up, we see that the signature may be used in various ways, and for different applications. Several points of view coexist, and none of them has shown to be systematically better. In particular, on the one hand, signatures may be used to remove temporal aspects and to reduce the dimension of the problem, whereas, on the other hand, they may do the opposite and increase the dimension of the algorithm's input. Moreover, they are combined with various learning algorithms and it may be hard to distinguish the properties of the signature from those of the algorithms. Nevertheless, all these methods assume that discrete data points have been embedded into actual continuous paths. As we will see in Section 4, the choice of path is crucial. Therefore, we describe in the next section the datasets used throughout the article, to understand their underlying structure and find suitable embeddings.

Datasets

The datasets used in this article have been chosen to cover a broad range of applications while being recent and challenging in various ways. Moreover, they present a variety of sampling frequencies and dimensions. They illustrate therefore different potential embeddings.

First, the Quick, Draw! dataset [START_REF] Google | The quick, draw! dataset[END_REF], which was already discussed in Section 2.2, and illustrated in Figure 2, is a public Google dataset. It consists of 50 million drawings, each drawing being a sequence of time-stamped pen stroke trajectories, divided into 340 categories. It takes approximately 7 gigabytes of hard disk space and is, therefore, a particularly large dataset. To compute the signature of every sample, it would thus be necessary to design a specific architecture, which cannot be implemented on a standard laptop computer. However, our goal in the present article is not to achieve the best possible performance, but to understand embedding properties. Moreover, we would like our experiments to be easily reproducible without requiring a lot of computational capacities. Therefore, we choose to use only a subset of the data. In Sections 4.2 and 5.1 we will use 68 000 training examples, while in Section 5.2, to improve accuracy, we will take around 12 million training samples.

Let us describe more precisely the data format. When someone draws an object, two pieces of information are recorded: pen positions, sampled at different times, and pen jumps. Therefore, one drawing consists of a set of strokes, one stroke being a segment of the drawing between two pen jumps, represented with different colors in Figure 2. As each stroke can be of different length, if p i,k is the number of points in the kth stroke of drawing number i, and if this drawing has K i strokes, then one drawing consists of K i tables of sizes 2 × p i,1 , . . . , 2 × p i,K i , where the factor 2 corresponds to the plane R 2 . For example, in Figure 2, the windmill drawing has 5 strokes: the first stroke is the blue one with 3 points, the second one the orange with 5 points, and so on. The data has been preprocessed by Google, resulting in the so-called "simplified drawing files". The preprocessing details are not given here, but we refer the reader to Google (2017) for a complete description. Finally, each sample i can be encoded under the following compact form:

x i =    x 1 i,1 . . . x 1 i,p i,1 . . . x 1 i,p i,1 +•••+p i,K-1 +1 . . . x 1 i,p i,1 +•••+p i,K x 2 i,1 . . . x 2 i,p i,1 . . . x 2 i,p i,1 +•••+p i,K-1 +1 . . . x 2 i,p i,1 +•••+p i,K 1 . . . 1 . . . K i . . . K i    ∈ R 3×p i , ( 7
)
where (x 1 i,j , x 2 i,j ) are the coordinates of the jth point of the drawing number i, and there is a pen jump when the last row of x i increases by 1. As in (5), p i = p i,1 + • • • + p i,K denotes the total number of points of drawing i.

The second dataset we are interested in is the Urban Sound dataset [START_REF] Salamon | A dataset and taxonomy for urban sound research[END_REF]. It consists of sound recordings, divided into 10 classes: car horn, dog barking, air conditioner, children playing, drilling, engine idling, gunshot, jackhammer, siren, and street music. It contains both mono and stereo recordings, so some samples take values in R, and some in R 2 . By averaging the two channels of stereo sounds, the data has been normalized to mono recordings, so that each sample is a one-dimensional time series. We thus have a collection of 5 435 time series of various lengths. On average, they are sampled at approximately 170 000 points, which makes them long time series, typically hard to model along the whole time range. Figure 7 depicts some examples of these noisy time series. Finally, we consider the MotionSense dataset, composed of smartphone sensory data generated by accelerometer and gyroscope sensors [START_REF] Malekzadeh | Protecting sensory data against sensitive inferences[END_REF]. This data has been recorded while some participants performed an activity among walking upstairs and downstairs, walking, jogging, sitting, and standing. In total, there are 10 classes and 360 recordings, which correspond to 24 participants performing 15 different trials. During each trial, 12 variables are measured: 3 directions for attitude, gravity, user acceleration, and rotation rate, respectively. Information about the participants is provided but we focus on the task of recognizing the activity performed from the multidimensional time series formed by sensors data. In Figure 8, three samples are shown, and, for each of them, curves of different colors correspond to the various quantities measured by sensors. Therefore, every sample is a time series in R 12 of different lengths. It is clear from Figure 8 that these series are noisy and highly dimensional. We can also note that they are shorter than the Urban sound's ones, with an average of approximately 4 000 time steps.

The embedding

We are now in a position to conduct a study of embeddings. In practice, we have at our disposal a matrix of observations x i ∈ R d×p i , written in ( 5), where columns correspond to points in R d sampled at times 0 ≤ t 1 < • • • < t p i ≤ 1. As already explained in Section 2.2, the goal is to construct a continuous path X i : [0, 1] → R d from the matrix x i . Therefore, we need to choose an interpolation method, but, to ensure some properties such as signature uniqueness (see Proposition 2), we may also create new coordinates to the path and in this way increase the dimension d of the embedding space. When not hidden, the embedding is generally only mentioned in the literature, without in-depth discussions. Therefore, our purpose here is not only to compare embeddings' performance, but also to give a first systematic survey of their use in the context of learning with signatures.

Definition and review of potential embeddings

We start in this subsection by reviewing different embeddings while adapting them to the Quick, Draw! dataset for illustrative purposes. The extension to other datasets follows immediately. All embeddings considered here are continuous piecewise linear, but their difference lies in the way this interpolation is performed. From a computational point of view, signatures of continuous piecewise linear paths can be computed with the library iisignature, as mentioned in Subsection 2.1. From now on, we fix a sample x ∈ R 3×p , which can be written as the matrix ( 7) where the index i has been removed to simplify notations.

Linear path.

A first natural choice is to interpolate data points linearly, that is to connect each consecutive points by a straight line. Note that for the Quick Draw! data, information about pen jumps is then lost. Thus, for a particular sample, if we are given p positions of the pen

[(x 1 1 , x 2 1 ), . . . , (x 1 p , x 2 p )], we consider a partition 0 = t 1 < t 2 < • • • < t p = 1 of [0, 1]
into p points, and define a piecewise linear path X : [0, 1] → R 2 , which is equal to (x 1 j , x 2 j ) at t j . We end up with a two-dimensional continuous path with coordinates (X 1 t , X 2 t ). This path, represented in Figure 9a, is the most often used in the literature, for example by [START_REF] Graham | Sparse arrays of signatures for online character recognition[END_REF], [START_REF] Lai | Online signature verification using recurrent neural network and length-normalized path signature descriptor[END_REF], or [START_REF] Yang | Deepwriterid: An end-to-end online text-independent writer identification system[END_REF].

Rectilinear path. Another interpolation method is often used in the literature (see, e.g., [START_REF] Chevyrev | A primer on the signature method in machine learning[END_REF][START_REF] Kormilitzin | Application of the signature method to pattern recognition in the cequel clinical trial[END_REF] and referred to as "axis path" or "rectilinear path". It is also piecewise linear but each linear section is parallel to an axis. In other words, to move from one point (x 1 j , x 2 j ) to another point (x 1 j+1 , x 2 j+1 ), a first linear segment goes from (x 1 j , x 2 j ) to (x 1 j+1 , x 2 j ), parallel to the x-axis, and a second segment from (x 1 j+1 , x 2 j ) to (x 1 j+1 , x 2 j+1 ), parallel to the y-axis. This path is depicted in Figure 9b. A crucial aspect of this path is that there exists a simple way to reconstruct it from its signature features [START_REF] Lyons | Hyperbolic development and inversion of signature[END_REF]. Note that for unidimensional data, such as the Urban Sound dataset, the linear and rectilinear interpolations are identical. Time path. The third approach builds upon the linear path and enriches it by adding a monotonous coordinate. This ensures the uniqueness of the signature, as stated in Proposition 2. It usually corresponds to adding the time parametrization as a coordinate of the path, as is done by [START_REF] Yang | Leveraging the path signature for skeleton-based human action recognition[END_REF]. Therefore, if t → (X 1 t , X 2 t ) is the linear path described above, which is piecewise linear, we define the time embedding as the 3-dimensional path t → (X 1 t , X 2 t , t), shown in Figure 9c.

Lead-lag path. Introduced by [START_REF] Chevyrev | A primer on the signature method in machine learning[END_REF] and [START_REF] Flint | Discretely sampled signals and the rough Hoff process[END_REF], the lead-lag transformation has been applied by, e.g., Gyurk ó et al. ( 2014), [START_REF] Kormilitzin | Application of the signature method to pattern recognition in the cequel clinical trial[END_REF], [START_REF] Lyons | A feature set for streams and an application to highfrequency financial tick data[END_REF][START_REF] Yang | Leveraging the path signature for skeleton-based human action recognition[END_REF]. Building on the time path, the idea is to add lagged versions of the coordinates X 1 and X 2 as new dimensions. Let us assume that we are given p data points, and consider a partition 0 = t 1 < t 2 < • • • < t p < t p+1 = 1 of [0, 1] into p + 1 points. Then, the lead-lag path with lag 1 is defined by

X : [0, 1] → R 5 t → (X 1 t , X 2 t , t, X 3 t , X 4 t ).
In this definition, X 1 and X 2 are a linear interpolation of the sequence

(x 1 1 , x 2 1 ), . . . , (x 1 p , x 2 p ), (x 1 p , x 2 p ) ,
in which the last point is repeated twice, and

X 3 t = 0 if t < t 1 X 1 t-t 1 otherwise , X 4 t = 0 if t < t 1 X 2 t-t 1 otherwise . ( 8
)
This yields a 5-dimensional path such that the last two coordinates are delayed copies of the first two, with a delay of t 1 . The process can be iterated, creating a path in R 7 with two lags t → (X 1 t , X 2 t , t, X 3 t , X 4 t , X 5 t , X 6 t ), where X 1 and X 2 are linear interpolations of the data with the last point repeated three times, X 3 and X 4 are defined by ( 8), and

X 5 t = 0 if t < t 2 X 1 t-t 2 otherwise , X 6 t = 0 if t < t 2 X 2 t-t 2 otherwise .
In this way, the lead-lag path can naturally be defined for any lag in N * . This path is highly dimensional (in R 7 for a lag of 2) and cannot be represented easily. Therefore, we plot in Figure 10 some coordinates against time, namely X 1 , X 3 , and X 5 .

Figure 10: X 1 t (red), X 3 t (green), and X 5 t (blue), coordinates of the lead-lag embedding with lag 2 against t, for t ∈ [0, 1].

Stroke path. For the Quick, Draw! data, we are provided with extra information about pen jumps. In the context of Arabic handwriting recognition, Wilson-Nunn et al. ( 2018) have introduced the idea of encoding information about jumps into a new coordinate. In essence, the approach is to use a 3-dimensional path in which the last dimension corresponds to strokes, in a similar way to the encoding of matrix (7). This procedure can be deployed in various ways and we restrict our attention to three of them.

Our first approach uses the description of a drawing as given in (7). Recall that, in this matrix, the stroke categorical variable is initialized to 1, and increased by 1 each time a different stroke begins. The idea is then to simply interpolate linearly the columns of the matrix, considered as points in R 3 . As can be seen in Figure 9d, each stroke is then represented in a different horizontal plane. This procedure looks like the most natural way to encode jumps information, and from now on is called "version 1" of the stroke path.

A related approach is considered by [START_REF] Wilson-Nunn | A path signature approach to online arabic handwriting recognition[END_REF]. It is represented in Figure 9e and subsequently called "version 2". Here, each stroke is indexed by odd integers, that is the first stroke is indexed by 1, the second by 3,..., and the kth by 2k -1. Two intermediary points are added between each stroke, indexed by even integers. For example, if (x 1 p 1 , x 2 p 1 , 1) is the last point of the first stroke, and (x 1 p 1 +1 , x 2 p 1 +1 , 3) is the first point of the second stroke, the points (x 1 p 1 , x 2 p 1 , 2) and (x 1 p 1 +1 , x 2 p 1 +1 , 2) are added to the path and linearly interpolated. This is represented in Figure 9e. The only difference with the previous path is how the path moves from one plane to another one. Instead of doing a straight line, it moves in two steps: one in a horizontal plane and another one parallel to the vertical axis. With this embedding and a recurrent network, [START_REF] Wilson-Nunn | A path signature approach to online arabic handwriting recognition[END_REF] have achieved a significant decrease in the error rate of Arabic characters recognition.

Finally, for comparison purposes, we also define a strictly monotonous coordinate. It has jumps of 1 when a new stroke begins, and otherwise grows linearly inside one stroke, such that it has increased by 1 between the beginning and the end of the stroke. In this definition, our goal is to check whether having a strictly monotonous coordinate increases accuracy, while in the two previous versions the stroke coordinate is piecewise constant. This embedding can be seen as a mix between time and stroke paths and could inherit the good properties of both. The resulting path is called "version 3" and shown in Figure 9f.

To conclude, there exists a broad range of embeddings, living in spaces of various dimensions. They lead to different signature features, which therefore do not have the same statistical properties. We will see in the next section that the embedding choice has a significant influence on accuracy results and that some strategies are more adapted than others.

Results

We present in this subsection the results of our study on embedding performance. To this end, we implement the approach depicted in Figure 3. Starting from the raw data, we first embed it into a continuous path, then compute its truncated signature, and use this vector as input for a learning algorithm. We use the embeddings described in the previous section. Note that the lead-lag path is taken with lag 1, but other lags will be discussed in Section 5.2. Each feature is normalized by the absolute value of its maximum so that all input values lie in [-1, 1]. We want our findings to be independent of the data and the underlying statistical model so we use a range of different algorithms. Their hyperparameters have been set to their default values, without trying to optimize them for each dataset. Indeed, we stress that our goal is not to select the best algorithm or to achieve a particularly good accuracy, but rather to compare the performance of different embeddings. The classification metric to assess prediction quality is the accuracy score. Denoting by (y 1 , . . . , y n test ) the test set's labels, and ( ŷ1 , . . . , ŷn test ) the predicted labels, this score is defined by

Acc test = 1 n test n test ∑ i=1 1 ŷi =y i . (9)
The four following algorithms have been used throughout the study.

• Following [START_REF] Yang | Leveraging the path signature for skeleton-based human action recognition[END_REF], we first consider a dense network with one hidden layer composed of 64 units with linear activation functions. We use a softmax output layer and the categorical cross-entropy loss, which yields a linear model equivalent to a logistic regression. This architecture is a sensible choice, since Proposition 3 states that linear functions of the signature approximate arbitrarily well any continuous function of the input path. We have used Python's library keras [START_REF] Chollet | [END_REF], with TensorFlow backend. The network is regularized by adding a dropout layer after the input layer, with a rate of 0.5. Optimization is done with stochastic gradient descent with an initial learning rate of 1. It is reduced by 2 when no improvement is seen on a validation set during 10 consecutive epochs. The maximal number of epochs is set to 200 and the mini-batch size to 128.

• Furthermore, we test the performance of a random forest classifier with 50 trees, implemented in scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]. It is a nonlinear very popular method initially proposed by [START_REF] Breiman | Random forests[END_REF].

• We also use the XGBoost algorithm, introduced by Chen and Guestrin (2016), and implemented in the Python package xgboost. It is a state-of-the-art gradient boosting technique, building upon the work of [START_REF] Friedman | Greedy function approximation: a gradient boosting machine[END_REF]. We set a maximum of 100 iterations and use early stopping with a patience of 5 to prevent overfitting and speed up training.

The maximum depth of a tree is set to 3 and the minimum loss reduction to make a split to 0.5.

• Finally, we run a nearest neighbor classifier with scikit-learn implementation [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF], which has a default value of 5 neighbors. This method is known to suffer from the curse of dimensionality, so it will be of interest to see how the signature truncation order affects its performance.

For each of the algorithms described above and each dataset of Section 3 (Quick, Draw!, Urban Sound, and Motion Sense), the following steps are repeated:

1. Split the data into training, validation, and test sets, as described in Table 2.

2. Choose an embedding and transform samples x i into continuous paths

X i : [0, 1] → R d .
3. For k = 1, . . . , K:

(a) Compute S k (X i ), the signature truncated at order k, for every sample i. This results in training, validation and test sets of the form

S k (X 1 ), . . . , S k (X n ) , where S k (X i ) ∈ R d k+1 -1 d-1 if d > 1, and R k if d = 1.
(b) Fit the algorithm on the training data. Validation data is used when the algorithm chosen is the linear neural network or XGboost, to adapt the learning rate and to implement early stopping, respectively.

(c) Compute the accuracy, defined by ( 9), on the test set.

For a path X in R d , the number of features is equal to (d k+1 -1)/(d -1) if d > 1, and to k if d = 1 (see Table 1 for some values). Therefore, the number of features depends on the dimension d of the embedding and the truncation order k. But d is different depending on the dataset and the embedding. Thus, to compare the quality of different embeddings, we plot the accuracy score against the log number of features, which yields one curve per embedding, where each point corresponds to a different truncation order k. We then check whether one embedding curve is above the others, which would mean that, at equal input size, this embedding is better for learning. The results of this procedure are plotted in Figures 11, 12 and 13, which correspond respectively to the Quick, Draw!, Urban Sound and Motion Sense datasets. A first striking fact is that some embeddings, namely the time and lead-lag, seem consistently better, whatever the algorithm and the data used. It suggests that this performance is due to intrinsic theoretical properties of signatures and embeddings, not to domain-specific characteristics. It is particularly remarkable as the dimension of input streams is different from one dataset to another.

The linear and rectilinear embeddings (red and pink curves), which are often used in the literature, appear to give the worst results. These two interpolation methods do not differ much in their results, although the linear path seems to be slightly better. Moreover, it seems that the smaller the dimension d, the worse they are. Indeed, the linear embedding performs especially bad for the Urban Sound dataset, which is unidimensional, whereas the difference is less pronounced for the Motion Sense dataset, which has values in R 12 . This bad performance can be explained by the fact that there is no guarantee that the signature transformation is unique when using the linear or rectilinear embeddings. Therefore, two different paths can have the same signature, without necessarily corresponding to the same class.

On the other hand, the best embedding is the lead-lag path (green curve), followed closely by the time path (brown curve). The difference between these two embeddings is again most important for the Urban Sound dataset. For the Quick, Draw! data, stroke paths have intermediate results, better than the linear path but still worse than the time and lead-lag paths. Yet stroke paths are the only embeddings in which new information, about pen jumps, is included. It is surprising how little impact this information seems to have on prediction accuracy. Note that in all of these cases, the uniqueness of the signature is ensured so it cannot explain the performance differences.

Good performance of the lead-lag path has already been noticed in the literature. However, up to our knowledge, there are few theoretical results. Still, [START_REF] Flint | Discretely sampled signals and the rough Hoff process[END_REF] have considered a discretely sampled input path X, assumed to be a continuous semimartingale, and have studied convergence results of its associated lead-lag path, called Hoff process, when sampling frequency increases. Thus, a lot of questions remain open concerning the statistical performance of the time and lead-lag embeddings, with, to our knowledge, no theoretical result in classification or regression frameworks.

To conclude this section, the take-home message is that using the lead-lag embedding seems to be the best choice, regardless of the data and algorithm used. It does not cost anything computationally and can drastically improve prediction accuracy. Moreover, the linear and stroke paths yield surprisingly poor results, despite their frequent use in the literature.

Signature domain and performance

Comparison of local and global signature features

As pointed out in Section 2.2, several authors do not compute signatures on the whole time interval but use instead a partition of [0, 1]. The rationale for this division is to describe the path by a sequence of truncated signatures, rather than one signature computed over the whole domain. Therefore, it is not surprising that this approach is typically used in combination with recurrent neural networks. In this section, we intend to investigate if signatures computed on a sub-interval contain some local information not present in signatures of the whole path. To this end, following [START_REF] Wilson-Nunn | A path signature approach to online arabic handwriting recognition[END_REF], we consider the dyadic partition of [0, 1] defined by ( 6

): 0 ≤ 2 -q < • • • < j2 -q < • • • < (2 q -1)2 -q ≤ 1, 0 < j ≤ 2 q
where q is the dyadic order. For different values of q, we compute signature coefficients on each interval (j -1)2 -q , j2 -q of the dyadic partition. Therefore, for each input path X i , we obtain a collection of signature vectors, which we concatenate altogether to obtain one big vector. This vector is then the input of a learning algorithm, and we compare the prediction accuracy curves of different dyadic orders. The time embedding with the linear neural network described in Section 4.2 is used. This process is summarized below.

1. Split the data into training, validation and test sets.

2. For q = 0, . . . , Q, and k = 1, . . . , K:

(i) For j = 1, . . . , 2 q , compute the signature truncated at order k on (j -1)2 -q , j2 -q , denoted by

S k (X i ) [(j-1)2 -q ,j2 -q ] ,
where X i is the time embedding of sample x i . Repeat this over all training samples.

(ii) For each training sample X i , concatenate all signature vectors and obtain one vector Sk (X i ) containing all S k (X i ) [(j-1)2 -q ,j2 -q ] , for j = 1, . . . , 2 q . This yields a dataset Sk (X 1 ), . . . , Sk (X n ) .

(iii) Fit a linear neural network with this data as features.

(iv) Compute accuracy on the test set.

The results of this procedure are shown in Figure 14. First, it is clear that a dyadic order of 0, which corresponds to computing the signature on the whole interval [0, 1], yields the best results. Indeed, the curve is always above the others for the Quick, Draw! and Motion Sense datasets. This is less obvious for the Urban Sound dataset, as the curve q = 0 is really close to the one corresponding to a dyadic order of 1. However, it still achieves a better result for most truncation orders k. This difference between datasets can be linked to their length: it seems that the longer the series, the better the accuracy of thin dyadic partitions. Indeed, high dyadic orders perform best for the Urban Sound dataset, which has an average of 170 000 sampled time points (see Table 2), whereas it is clear that each new dyadic split decreases accuracy for the Quick, Draw! data, which has an average of 44 sampled points. In a nutshell, few local information seems to be lost when the signature of the whole path is computed, although it may be worth considering partitions of the path for long streams.

Performance of the signature

The message of previous sections is that the lead-lag embedding is the most appropriate in a learning context and that signatures should be computed over the whole path domain. As a natural continuation, we propose in this section to examine more closely the effect of the algorithm and to compare our prediction scores to the literature. As we will see, the signature combined with a lead-lag embedding has an excellent representation power, to the extent that it achieves prediction scores close to state-of-the-art methods, without using any domain-specific knowledge.

Before we start the comparison, we point out that the lead-lag embedding has a hyperparameter that has not yet be tuned, which is the number of lags. In our experiments, it is selected with the same approach as in previous sections: for each lag, we plot the curve of test accuracy against the number of features, where each point of the curve corresponds to one signature truncation order. We plot and select the parameter which leads to the curve above others. Figure 15 highlights that curves overlap for the Motion Sense and Urban sound cases, therefore, when there is a doubt on which curve is above, we choose to pick the smallest lag. For the Quick, Draw! and Motion Sense datasets, the best lag is then 1, whereas it is 5 for the Urban Sound dataset. 2019) report an average F1 score above 92%, while the signature truncated at order 3 and combined with a XGBoost classifier achieves a F1 score of 93.5%. So these two scores are close, but our approach is computationally much less demanding. We end up by stressing the fact that the algorithms used here have not been tuned to a specific application. However, the combination signature + generic algorithm achieves results close to the state-of-the-art in several domains, while requiring few computing resources and no domain-specific knowledge. Indeed, it takes approximately 52 seconds to compute the signature at order 3 of 68 000 Quick, Draw! samples on one core of a laptop, which results in 0.0008 second per sample. Besides, signature computations can be parallelized, making the approach scalable to big datasets. Lastly, the signature method achieves its best results for the high dimensional Motion Sense dataset, which suggests that it is especially relevant for multidimensional streams.

Conclusion

The signature method is a generic way of creating a feature set for sequential data and has recently caught the machine learning community's attention. Indeed, it yields results competitive with state-of-the-art methods, while being generic, computationally efficient, and able to handle multidimensional series. One of its appealing properties is that it captures geometric properties of the process underlying the data and does not depend on a specific basis. In this paper, we have reviewed its use in a learning process and surveyed several of its successful applications. The use of signatures relies on representing discretely sampled data as continuous paths, a mechanism called embedding. In the literature, authors use various embeddings, without any systematic comparison. We have compared different common embeddings and concluded that the lead-lag seems to be systematically better, whatever the algorithm or dataset used. Moreover, we have pointed out that the signature of the whole path appears to contain as much information as the signature of subpaths, therefore encoding both global and local properties of the input stream.

Our study is a first step towards understanding how signature features can be used in statistics, and a lot of issues remain open, both practical and theoretical. First, it would be of great interest to understand the theoretical statistical properties of embeddings, in particular, to explain the good performance of the lead-lag path. Moreover, in Section 2.2, we have seen that signature features may be combined with feedforward, recurrent, or convolutional neural networks. For each of these architectures, the point of view on signature features is different: they are considered respectively as a vector, a temporal process, or an image. A more detailed understanding of these representations would be valuable. Finally, it could be worth investigating the robustness of the signature method when the truncation order becomes large. Indeed,Figures 11,13,and 12 suggest that the signature is robust to dimension: the accuracy curves do not decrease when the number of features becomes large, even when a nearest neighbor algorithm is used with more than a hundred thousand features. In this situation, we would expect the variance to be large and to reduce accuracy, but that does not seem to be the case. This phenomenon may deserve a more in-depth study.

Figure 1 :

 1 Figure 1: Geometric interpretation of signature coefficients.

Figure 2 :

 2 Figure 2: 9 drawings from the Quick, Draw! dataset

Figure 3 :

 3 Figure 3: Signature and dense neural network.

Figure 4 :

 4 Figure 4: Signature and recurrent neural network.

Figure 5 :

 5 Figure 5: Signature and convolutional neural network.

Figure 6 :

 6 Figure 6: Construction of an image with signature coefficients.

Figure 7 :

 7 Figure 7: 5 samples from the Urban sound dataset

Figure 8 :

 8 Figure 8: 3 samples from the Motion sense dataset

  Stroke path, version 1. (e) Stroke path, version 2. (f) Stroke path, version 3.

Figure 9 :

 9 Figure 9: Different embeddings of a Quick, Draw! sample. Each stroke is plotted with a different color only for the sake of illustration.

Figure 11 :

 11 Figure 11: Quick, Draw! dataset: prediction accuracy on the test set, for different algorithms and embeddings.

Figure 12 :

 12 Figure 12: Urban Sound dataset: prediction accuracy for different algorithms and embeddings.

Figure 13 :

 13 Figure 13: Motion Sense dataset: prediction accuracy on the test set, for different algorithms and embeddings.

Figure 14 :

 14 Figure 14: Test accuracy for different dyadic partitions of the path.

Figure 15 :F1

 15 Figure 15: Test accuracy for different lags.

Table 2 :

 2 Table 2 some characteristics of these three datasets. They illustrate the diversity of problems in sequential learning, where time appears in different ways. Datasets summary

		Quick, Draw! Urban Sound Motion Sense
	Number of classes	340	10	6
	Dimension	2	1	12
	Average number of sampled points	44	171 135	3 924
	Training set size	68 000	4 435	300
	Validation set size	6 800	500	30
	Test set size	6 800	500	30

This work was supported by grants from Région Ile-de-France.

computing resources, as they have a reasonable size (a few hundred samples for Motion Sense and thousand for Urban Sound-see Table 2) and a small number of classes. On the other hand, the Quick, Draw! recognition task, which is comprised of 340 classes, is more involved and requires an elaborate algorithm as well as a significant number of training samples. Therefore, we will use more data than in the previous sections, with 12 185 600 training samples and 87 040 validation samples.

For the Quick, Draw! dataset, we have compared our results to a Kaggle competition (Kaggle.com, 2018). In this competition, 1 316 teams competed for a prize of 25 000$. State-of-the-art deep convolutional networks, such as MobileNet or ResNet, trained with several millions of samples, were among the best competitors. Teams on the podium used ensembles of such networks. We stress that these winning methods require a lot of computing resources and are specific to images. The metric used in the competition was the mean average precision, defined as follows. Denoting by {y 1 , . . . , y n test } the test set labels, three ranked predictions are made for each sample, denoted by

where ŷ1 i is the class with the largest probability, ŷ2 i the second largest, and so on. Then, the mean average precision at rank 3 is defined by

Mean average precision is computed by the competition platform on 91% of a test set of 112 200 samples. We enhance the small neural network used in Section 4.2 by using ReLU activation functions and adding three hidden layers with 256 nodes. The network is trained during 300 epochs with an Adam optimizer. At each epoch, it is trained on 609 280 samples randomly selected among the 12 185 600 training samples. The best team obtains a MAP 3 of 95% whereas this small network combined with signature features truncated at order 6 already reaches 54%. The winners use an ensemble of several dozens of deep neural networks, trained on 49 million samples. This kind of architectures requires considerably more computational capacities than ours.

For the Urban Sound dataset, state-of-the-art results are obtained by [START_REF] Ye | Urban sound event classification based on local and global features aggregation[END_REF]. The authors combine feature extraction with a mixture of expert models and achieve 77.36 % accuracy, defined by ( 9). The feature extraction step is specific to sound data and is based on several ingredients, such as whitened spectrogram, dictionary learning, soft-thresholding, recurrence quantification analysis, and so on. These crafting operations make use of a lot of domain-specific knowledge and cannot be extended easily to other applications. On the other hand, it is clear from Figure 12 that a random forest classifier performs well with signature features. Therefore, we tune its hyperparameters with a lead-lag embedding, a lag of 5, and a signature truncated at order 5. We obtain an accuracy of 70 % with 460 trees with a maximum depth of 30 and in which 500 random features are considered at each split.

Finally, [START_REF] Malekzadeh | Mobile sensor data anonymization[END_REF] tackle the problem of mobile sensor data anonymization. They build a deep neural network architecture that preserves user privacy but still detects the activity performed. The architecture is built on autoencoders combined with a multi-objective loss function. There is a trade-off between activity recognition and privacy but good activity recognition results are achieved. Performance of the classifier of [START_REF] Malekzadeh | Mobile sensor data anonymization[END_REF] is measured with the average F1 score, defined as follows. Assume there are L different classes, and denote by (y 1 , . . . , y n test ) the test labels, and by ( ŷ1 , . . . , ŷn test ) the predicted ones. Then, the