OMP Orthogonal Matching Pursuit SVMs Support Vector Machines p.d positive definite TsPrima Time series Pre-image MDS Multidimensional Scaling RKHS Reproducing Kernel Hilbert space 6DMG 6 Dimensional Motion Gesture xi

Keywords: Time series, temporal kernel, pre-image estimation, representation learning, dimensionality reduction, dictionary learning . . . . . . . . . . . . . . 39 . . . . . . . . . . . analytics . . . . . . . . . . . . . . . . . . . . . . . DTAK Dynamic Time Alignment Kernel DTW Dynamic Time Warping KGA Kernel Global Alignment KDTW Kernel Dynamic Time Warping k-SVD k-Singular Value Decomposition PCA

Kernel methods are known to be effective to analyse complex objects by implicitly embedding them into some feature space. To interpret and analyse the obtained results, it is often required to restore in the input space the results obtained in the feature space by using pre-image estimation methods. This work proposes a pre-image estimation method for time series kernel analytics that consists of two steps. In the first step, a time warp function, driven by distance constraints in the feature space, is defined to embed time series in a metric space where analytics can be performed conveniently. In the second step, the time series pre-image estimation is cast as learning a linear (or a nonlinear) transformation that ensures a local isometry between the time series embedding space and the feature space.

The proposed method is compared to state of the art through three major tasks that require pre-image estimation: 1) time series averaging, 2) time series reconstruction and denoising, and 3) time series representation learning. The extensive experiments conducted son 33 publicly-available datasets show the benefits of the pre-image estimation for time series kernel analytics.

Résumé

Les méthodes à noyaux sont connues pour être efficaces pour l'analyse d'objets complexes en les plongeant implicitement dans un espace de caractéristiques (feature-space). Pour interpréter et analyser les résultats obtenus, il est souvent nécessaire de restaurer dans l'espace d'entrée les résultats obtenus dans l'espace des caractéristiques à l'aide de méthodes d'estimation de la pré-image. Ce travail propose une méthode d'estimation de la pré-image pour rendre interprétable les méthodes d'analyse de séries temporelles à base de noyaux. Dans la première étape, une fonction de déformation temporelle, supervisée par des contraintes de distances, est définie pour plonger les séries dans un espace métrique où des analyses pratiques peuvent être menées. Dans la deuxième étape, l'estimation de la pré-image des séries temporelles est obtenue par l'apprentissage d'une transformation linéaire (ou non linéaire) assurant une isométrie locale entre le nouvel espace métrique des séries et l'espace des caractéristiques. La méthode proposée est comparée aux méthodes de l'état de l'art au travers de trois tâches principales requérant l'estimation de la pré-image: 1) le centrage des séries temporelles, 2) la reconstruction et le débruitage des séries temporelles et 3) l'apprentissage de représentations pour des séries temporelles.

Mots-clés : Séries temporelles , noyau temporel , estimation de pré-images, apprentissage de représentation, réduction de dimension, apprentissage de dictionnaire. 4.1 In the left, the temporal alignment between x i (t i = 5) and x j (t j = 6), the optimal alignment π * is indicated in red. In the right, the optimal alignment is illustrated as connections between two time series. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2 Illustration of the DTW constraints . . . . . . . . . . . . . . . . . . 51 4.3 In the left, the temporal alignment between x i (t i = 5) and x r (t * = 6), the optimal alignment π * is indicated in red. In the right, the adjacency binary matrix related to the optimal temporal alignment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

List of Figures

1

Introduction

Over the past two decades, machine learning has become one of the fastest-growing areas involved with computer science and statistics. Machine learning plays a vital role in the revolution of science and technology in multiple fields as biomedical informatics, computer vision and natural language processing. Kernel methods [START_REF] Schölkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF] are among the major machine learning approaches, known to be effective in dealing with nonlinear problems and complex data as time series, sequences and graphs. The main idea of kernel methods is to map the data in the input space X to a feature space H via a nonlinear mapping Φ, where the data can be processed conveniently by linear approaches, as illustrated in Figure 1.1. Kernel trick, defines the main concept behind kernel machines, that consists to process all data computations by implicitly using the inner products Φ(x), Φ(x ) = κ(x, x ), where κ is a valid kernel. Since then, many nonlinear algorithms have been developed for analysis [START_REF] Mika | Fisher discriminant analysis with kernels[END_REF] and support vector machines [START_REF] Cortes | Support-vector networks[END_REF], for dimensionality reduction with kernel principal component analysis [START_REF] Mika | Kernel pca and de-noising in feature spaces[END_REF], for sparse coding with kernel k-SVD [START_REF] Van Nguyen | Kernel dictionary learning[END_REF] and for clustering with kernel k-means [START_REF] Grigorios | The global kernel k-means algorithm for clustering in feature space[END_REF]. The price that one should pay for the efficient kernel machinery is that the solutions are only obtained as expansions in terms of the mapped input samples into the feature spaces. However, in many situations, for analysis and interpretation purposes, there is a need of the reverse mapping of the obtained results from the feature space back to the input space, called pre-image estimation problem. For instance, given some noisy samples, kernel PCA first applies linear PCA on the mapped samples in the feature space, then perform denoising by projecting them onto the subspace defined by the leading eigenvectors. The projections have then to be mapped back to the input space to recover the denoised samples. The pre-image estimation is of a high interest in many other kernel tasks to obtain, for instance, the reverse mapping of the centroids of a kernel clustering or the pre-image of the atoms and the sparse representations of a kernel dictionary learning, among others. In view of the importance of the pre-image estimation issue and of its benefits in machine learning, several major propositions have been developed.

The first study proposed by Schölkopf [START_REF] Schölkopf | Kernel pca pattern reconstruction via approximate pre-images[END_REF] gives the exact pre-image solution based on the inner product between the pre-image and a set of vectors of an orthonormal basis into the input space. This method underlines two strict conditions: the existence of the pre-image solution and the inversion of the function f κ , where κ(x, y) = f κ ( x, y ), that are unsatisfied in general. Thus, several pre-image estimation solutions have been proposed. First, in Mika [START_REF] Mika | Kernel pca and de-noising in feature spaces[END_REF], the problem is formalised as a nonlinear optimization problem, which for the particular case of the Gaussian kernel allows to estimate the reverse mapping based on a fixed-point iterative process. To avoid numerical instabilities of the latter approach, in Kwok [START_REF] Kwok | The pre-image problem in kernel methods[END_REF], the relationship between the distances in the feature and the input spaces is established for isotropic kernels and then is used to approximate pre-images by multidimensional scaling. In Bakir [START_REF] Gökhan | Learning to find preimages[END_REF], the pre-image estimation problem is cast as a regression problem between the input and the mapped data and the learned regression model is used to predict pre-images. Honeine and Richard proposed in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] an approach in which the main idea is to estimate, from the mapped data, a coordinate system that ensures an isometry with the input space. This approach has the advantage to provide a closed-form solution, to be independent of the kernel nature and to involve only linear algebra.

All the proposed methods for pre-image estimation are either based on optimization schemas, such as gradient descent or fixed-point iterative solution or based on ideas borrowed from dimension reduction methods. In particular, these methods are developed for Euclidean input spaces, as derivations are straightforward owing to linear algebra (see [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] for a survey on the resolution of the pre-image problems in machine learning). A major challenge arises when dealing with non-Euclidean input spaces, which are often used to represent structured data as sequences, time series or graphs. In particular, for time series data, thanks to temporal kernels ( [START_REF] Cuturi | A kernel for time series based on global alignments[END_REF], [START_REF] Hiroshi | Dynamic time-alignment kernel in support vector machine[END_REF]), kernel machinery has been increasingly investigated with success for time series kernel analytics ( [START_REF] Yuan | A large margin time series nearest neighbour classification under locally weighted time warps[END_REF], [START_REF] Cao-Tri | Multi-modal and multi-scale temporal metric learning for a robust time series nearest neighbors classification[END_REF], [START_REF] Soheily-Khah | Generalized k-means-based clustering for temporal data under weighted and kernel time warp[END_REF], [START_REF] Varasteh Yazdi | Time warp invariant dictionary learning for time series clustering: application to music data stream analysis[END_REF][START_REF] Varasteh Yazdi | Time warp invariant ksvd: Sparse coding and dictionary learning for time series under time warp[END_REF]), the pre-image problem for temporal data remains unaddressed. In addition, time series data, that include temporal dependency and time delays, are naturally lying in a non-Euclidean input space, preventing the application of the traditional approaches for pre-image estimation.

This thesis aims to fill this gap by proposing a pre-image estimation approach for time series kernel analytics. The main idea of the proposed method consists of two steps. In the first step, a time warp function, driven by distance constraints in the feature space, is defined to embed time series into a metric space where analytics can be performed conveniently. In the second step, the time series preimage estimation is cast as learning a linear (or a nonlinear) transformation that ensures a local isometry between the time series embedding space and the feature space. The relevance of the proposed time series pre-image estimation is studied through three major tasks :

-time series averaging, -time series reconstruction and denoising under kernel PCA, -time series sparse representation under kernel dictionary learning.

The benefits of the proposed method are assessed through extensive experiments conducted on 33 publicly-available time series datasets, including univariate and multivariate time series that may include varying delays and be of the different lengths. The main contributions of this thesis are:

1. We propose a time warp function, driven by distance constraints in the feature space, that embeds time series into an Euclidean space.

2. We cast the time series pre-image estimation approach as learning linear or nonlinear transformations in the feature space.

3. We propose a tractable solution that ensures a local isometry between the temporal embedded space and the feature space.

4. We conduct wide experiments to compare the proposed approach to the major alternative pre-image estimation methods under three crucial tasks:

1) time series averaging, 2) time series reconstruction and denoising, and 3) dictionary learning and sparse representations for time series.

In the thesis, the remainder is summarised as follows. Chapter 2 gives a brief introduction to kernel PCA, kernel k-SVD and kernel regression, three important machine learning methods that crucially require pre-image estimation. Then we present the major related works for pre-image estimation in Chapter 3. In Chapter 4, we formalise the pre-image estimation problem for time series and develop the proposed method as well as the corresponding solution. In Chapter 5, we detail the experiments conducted and discuss the obtained results. Finally, in Chapter 6, we conclude this thesis and point out some perspectives for this work.

Notations

Importance of pre-image in kernel machinery

This chapter gives a brief introduction to kernel PCA [START_REF] Schölkopf | Kernel principal component analysis[END_REF], kernel k-SVD [START_REF] Van Nguyen | Kernel dictionary learning[END_REF] and kernel regression [START_REF] Saunders | Ridge regression learning algorithm in dual variables[END_REF], three methods largely used in machine learning tasks where the pre-image estimation is highly required. Let X be a compact set in R d . The positive definite (reproducing) kernel κ(., .) is a function on X 2 → R, which for all sets of input samples {x i } N i=1 ⊂ X gives positive matrices K with entries K ii = κ(x i , x i ). By [START_REF] Aronszajn | Theory of reproducing kernels[END_REF], there exists a unique reproducing kernel Hilbert space H (RKHS) that is associated with kernel κ via feature mapping Φ : X → H. That means kernel κ can be evaluated as inner product in H:

κ(x i , x i ) = Φ(x i ), Φ(x i )
Kernel methods [START_REF] Schölkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF] rely on embedding samples x ∈ X with Φ(x) into a feature space H, of arbitrary large and possibly infinite dimension. The map function Φ needs not to be explicitly defined, since computations conducted in H can be carried out by a kernel function that measures the inner product in that space,

namely κ(x i , x i ) = Φ(x i ), Φ(x i ) for all x i , x i .
Given a set of input samples {x i } N i=1 , x i ∈ R d , let K be the Gram matrix related to the kernel κ. With some abuse of notation, let Φ(X) be the row vector of entries Φ(x 1 ), ..., Φ(x N ). Note that kernel κ is supposed to be positive definite, then K is a positive matrix whose all of eigenvalues are positive.

In the following, the two first Sections describe kernel PCA and kernel k-SVD, as nonlinear extensions of the well-known PCA and k-SVD. While both methods estimate a linear combination for optimal reconstruction of the input samples, the former forces the orthogonality of the atoms that leads to an orthonormal basis basis, and the latter forces the sparsity while relaxing the orthogonality condition.

Kernel PCA

Principal Component Analysis (PCA) is a powerful technique for extracting structure from possibly high-dimensional datasets. PCA is an orthogonal transformation of the coordinate system in which we describe data. The new coordinate system is obtained by projection onto the so-called principal components of the data. A small number of principal components can be sufficient to account for most of the structure in the data.

Given a set of samples {x i } N i=1 ⊂ R d which, for clarity reasons, are assumed centered, namely N i=1 x i = 0, PCA finds the principal components by diagonalizing the covariance matrix:

C = 1 N N i=1 x i x T i . (2.1)
C is positive definite that can thus be diagonalized (Problem (2.1)) by solving the eigendecomposition:

λ j u j = Cu j . (2.2)
with eigenvalues λ j ≥ 0 and nonzero eigenvectors u j ∈ R d \ {0}. Substituting Eq.

(2.1) into the expression (2.2)

λ j u j = Cu j = 1 N N i=1 x i , u j x i .
we see that all solutions u j with λ j = 0 lie in the span of x 1 , . . . , x N , hence for the solutions Eq. (2.2) is equivalent to

λ j x i , u j = x i , Cu j , ∀i = 1, . . . , N.
The ratio of eigenvalues λ j is the ratio of explanatory importance of the principal components with respect to the variables. If a principal component has a low eigenvalue, then it is contributing little to the explanation of variances in the variables and may be ignored as redundant with more important principal components. Hence, for dimensionality reduction or compression data, one can choose the number p of principal components such that p = arg min

p∈N * p j=1 λ j N j=1 λ j ≥ 0.95, (2.3)
where 0.95 is the proportion of information extracted from the input data.

Standard PCA only allows linear dimensionality reduction. However, if the data has more complicated structures which cannot be well represented in a linear space, standard PCA will not be very helpful. Fortunately, based on kernel trick, kernel PCA extends standard PCA to find principal components that are nonlinearly related to the input variables (illustrated in Figure 2.1). For that, the principal components are rather determined in the feature space. Similarly, for the sake of clarity, we assume for now that we are dealing with centered mapped data, namely N i=1 Φ(x i ) = 0. The covariance matrix in the feature space takes

Φ(x 2 ) Φ(x 1 ) Φ(x N ) Φ( . ) x N x 1 u 1 u p ℋ x i P (Φ(x 1 )) P (Φ(x i )) P (Φ(x N )) P (Φ(x)) Φ(x) x Figure 2.1: Illustration of kernel PCA then the form of C = 1 N N i=1 Φ(x i )Φ(x i ) T . (2.4)
Similarly to standard PCA, the objective comes to find the eigenvalues λ j ≥ 0 and eigenvectors u j ∈ H \ {0} that satisfies

λ j u j = Cu j . (2.5)
As each u j lie in the span of Φ(x 1 ), ..., Φ(x N ), there exist coefficients α 1j , . . . , α N j such that

u j = N i=1 α ij Φ(x i ), (2.6)
and for each Φ(x i )

λ j < u j , Φ(x i ) >=< Cu j , Φ(x i ) > . (2.7)
Combining Eq. (2.6) and Eq. (2.7), we get

λ j N i=1 α ij Φ(x i ), Φ(x i ) = C N i=1 α ij Φ(x i ), Φ(x i ) , λ j N i=1 α ij Φ(x i ), Φ(x i ) = 1 N N i=1 Φ(x i )Φ(x i ) T N i=1 α ij Φ(x i ), Φ(x i ) , (2.8)
λ j N i=1 α ij Φ(x j ), Φ(x i ) = 1 N N i=1 α ij N j=1 Φ(x j )Φ(x j ) T Φ(x i ), Φ(x i ) .
In terms of the Gram matrix K = (K ii ) ii related to the kernel κ:

K ii = κ(x i , x i ) =< Φ(x i ), Φ(x i ) >,
and α j = [α 1j , . . . , α N j ], we have:

λ j Kα j = 1 N K 2 α j .
(2.9)

The problem (2.6) remains to find the solution of the eigendecomposition problem:

λ j α j = 1 N Kα j .
(2.10)

Let λ 1 ≥ ... ≥ λ p (N λ j in Eq. (2.10)) be the p non-zero eigenvalues of 1 N K and α 1 , ..., α p their corresponding eigenvectors. The principal components in the feature space are then given by computing the projections P j (Φ(x)) of the sample x onto the eigenvector u j = Φ(X) α j :

P j (Φ(x)) =< u j , Φ(x) >= N i=1 α ij < Φ(x i ), Φ(x) >= k x α j , (2.11)
with k x = [κ(x 1 , x), ..., κ(x N , x)]. By denoting α = [α 1 , ..., α p ], the description P (Φ(x)) of Φ(x) into the sub-space of the p first principal components is then

P (Φ(x)) = (k x α) T . (2.12)
Two considerations should be taken in the above results. First, the eigenvectors u j should be normalised by:

1 = u j , u j = Φ(X) α j , Φ(X) α j = α T j Φ(X) T Φ(X)α j = α T j Kα j = α T j λ j α j = λ j α j , α j .
Secondly, as Φ(X) should be centered by considering Φ(X) = Φ(X)-1 N Φ(X)1 N 1 T N with 1 N = (1, . . . , 1) T ∈ R N the unit vector. The Gram matrix K in Eq. (2.10) and k x in Eq. (2.11) need to be substituted with their centered counterparts, namely K and k x , as follows:

K = Φ(X) T Φ(X) = Φ(X) - 1 N Φ(X)1 N 1 T N T Φ(X) - 1 N Φ(X)1 N 1 T N = Φ(X) T Φ(X) - 1 N Φ(X) T Φ(X)1 N 1 T N - 1 N 1 N 1 T N Φ(X) T Φ(X)+ + 1 N 2 1 N 1 T N Φ(X) T Φ(X)1 N 1 T N = K - 1 N K1 N 1 T N - 1 N 1 N 1 T N K + 1 N 1 N 1 T N K 1 N 1 N 1 T N = K -K1 N -1 N K + 1 N K1 N , (2.13)
with (1 N ) ij = 1/N for all i, j, and I N the identity matrix.

Similarly, k x is defined by:

k x = Φ(x 1 ), Φ(x) , ..., Φ(x N ), Φ(x) = Φ(x 1 ) - 1 N Φ(X)1 N , Φ(x) - 1 N Φ(X)1 N , ..., Φ(x N ) - 1 N Φ(X)1 N , Φ(x) - 1 N Φ(X)1 N = Φ(x i ), Φ(x) - 1 N Φ(x)Φ(X)1 N -Φ(x i ) 1 N Φ(X)1 N + + 1 N 2 1 T N Φ(X) T Φ(X)1 N N i=1 = κ(x i , x) - 1 N k x 1 N - 1 N k x i 1 N + 1 N 2 1 T N K1 N N i=1 = k x - 1 N k x 1 N 1 T N - 1 N 1 T N K - 1 N 2 1 T N K1 N 1 T N = k x (I N - 1 N 1 N 1 T N ) - 1 N 1 T N K(I N - 1 N 1 N 1 T N ) = (k x - 1 N 1 T N K) (I N -1 N ).
For centered data, the p principal components u 1 , . . . , u p are then:

u j = N i=1 α ij Φ(x i ),
where Φ(x j ) = Φ(x j ) -Φ and Φ = 1 N N i=1 Φ(x i ). The projection P ( Φ(x)) of Φ(x) onto the subspace of the p eigenvectors is defined by:

P ( Φ(x)) = p i=1 Φ(x), u i u i = p i=1 Φ(x), Φ(X)α i Φ(X)α i = p i=1 Φ(x), Φ(X) α i Φ(X)α i = p i=1 kx α i Φ(X)α i = p i=1 Φ(X)α i ( kx α i ) T = p i=1 Φ(X)α i α T i kT x = Φ(X)αα T kT x .
From that, we obtain the approximation of Φ(x) as

Φ(x) = Φ(x) + Φ ≈ P ( Φ(x)) + Φ = Φ(X)αα T kT x + Φ = Φ(X)(I N -1 N )αα T kT x + 1 N Φ(X)1 N = Φ(X) (I N -1 N )αα T kT x + 1 N 1 N . (2.14)
Note that Φ(x) is expressed as a linear combination of the mapped set Φ(X).

Kernel PCA first maps the data into the feature space via a nonlinear feature mapping Φ, then preforms linear PCA on the mapped data. This method is convenient to detect nonlinear structure in a given data [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF] and highly used for data compression, reconstructions and denoising. However, the results obtained by kernel PCA live in high dimensional feature space H. To make the compressed, denoised results expressed into the input space, a pre-image problem should be solved.

Kernel k-SVD

Sparse coding and dictionary learning become popular methods in machine learning and pattern recognition for a variety of tasks as feature extraction ( [START_REF] Mailhé | Shift-invariant dictionary learning for sparse representations: extending k-svd[END_REF], [START_REF] Barthélemy | Shift & 2d rotation invariant sparse coding for multivariate signals[END_REF], [START_REF] Varasteh Yazdi | Time warp invariant dictionary learning for time series clustering: application to music data stream analysis[END_REF]), reconstruction, denoising, compressed sensing ( [START_REF] Aharon | Sparse and redundant modeling of image content using an image signature dictionary[END_REF], [START_REF] David | Compressed sensing[END_REF]) and classification ( [START_REF] Wright | Robust face recognition via sparse representation[END_REF], [START_REF] Guha | Learning sparse representations for human action recognition[END_REF]). The aim of sparse coding methods is to represent input samples as a linear combination of few basis functions called atoms composing a given dictionary. Sparse coding is generally formalised as an optimisation problem that minimises the error of the reconstruction under l 0 or l 1 sparsity constraint. The l 0 constraint, that control the maximum number of involved atoms, leads to a nonconvex and NP-hard problem. This problem can however be solved efficiently by using the matching pursuit method ( [START_REF] Stéphane | Matching pursuits with time-frequency dictionaries[END_REF]) or its orthogonal variant ( [START_REF] Rezaiifar | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF]). Relaxing the sparsity constraint from l 0 to l 1 norm yields a convex sparse coding problem, also known a a LASSO problem ( [START_REF] Tibshirani | The lasso problem and uniqueness[END_REF]). In sparse coding, the used dictionary may be selected among pre-specified familly of basis functions as, among Fourier, Wavelets ( [START_REF] Mallat | A wavelet tour of signal processing[END_REF]), Curvelets ( [START_REF] Starck | The curvelet transform for image denoising[END_REF]), Contourlets ( [START_REF] Do | The contourlet transform: an efficient directional multiresolution image representation[END_REF]) and Gabor functions ( [START_REF] Zhang | Gabor feature based sparse representation for face recognition with gabor occlusion dictionary[END_REF]). Although these dictionaries allow fast transforms, their reconstribution potential is tightly related to the nature of the data. For instance, Wavelets show efficient reconstruction for natural images and textures ( [START_REF] Ophir | Multi-scale dictionary learning using wavelets[END_REF]), Curvelets for edges ( [START_REF] Zhang | Gabor feature based sparse representation for face recognition with gabor occlusion dictionary[END_REF]) and Gabor for sounds ( [START_REF] Ataee | Parametric dictionary learning using steepest descent[END_REF]). The alternative to the above basis functions is to use a dictionary learning approach to learn, from the input data, a set of atoms to sparse represent the input samples. To solve that dictionary learning problem most approaches alternate between two steps: 1) keep the dictionary fixed and find the sparse representation using a sparse approximation algorithm, e.g., orthogonal matching pursuit (OMP), 2) keep the representation fixed and update the dictionary, either all the atoms at once by using for instance MOD (method of optimal directions) ( [START_REF] Engan | Method of optimal directions for frame design[END_REF]) or one atom at a time as in k-SVD( [START_REF] Aharon | K-svd: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF]). In particular, k-SVD uses a singular value decomposition to learn jointly the dictionary as well as the sparse coefficient. k-SVD can be viewed as a generalisation of k-means algorithm that relaxes the assignment constrain to represent each input sample by a linear combination of few representative atoms (i.e., the centroids) instead by using only one centroid. In the following,we formalise the standard sparse coding and dictionary learning problem and present the standard efficient solution k-SVD. where a = (a 1 , . . . , a L ) T ∈ R L is the sparse code of x and D is in general a predefined (e.g., Fourier, Wavelet, Gabor basis functions) and overcomplete (i.e., d << L) dictionary. The l 0 sparsity constraint in Eq. (2.15) ensures to limit the maximum number of involved atoms to τ . Although the l 0 -norm renders the problem formalised in Eq. (2.15) nonconvex and NP-hard, it can be efficiently solved via matching pursuit ( [START_REF] Stéphane | Matching pursuits with time-frequency dictionaries[END_REF]) or its orthogonal variant OMP ( [START_REF] Rezaiifar | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF]). The main idea of OMP method is to select at each iteration the atoms d j that is highly correlated to the input sample or to its residual part. The coefficient a j , obtained by an orthogonal projection on the sub-space defined by the yet selected atoms, defines the contribution of d j to reconstruct x. The process is reiterated until the maximum number τ of atoms is reached. Algorithm 1 gives the main steps of the OMP method. It is worth noting that although initialising the dictionary with a given family of basis functions (e.g., Fourrier, Wavelet) hastens the process, the sparse coding result remain in general more precise when the dictionary are proposed in the literature, among them the k-SVD [START_REF] Aharon | Sparse and redundant modeling of image content using an image signature dictionary[END_REF] method that we detail in the following.

Let X ∈ R d×N : X = [x 1 , . . . , x N ] be the matrix giving the description of N input samples, with x i ∈ R d . The dictionary learning problem, that generalises the sparse coding given in Eq. (2.15), can be formalised as learning both the sparse coding and the dictionary D to minimise the error of reconstruction of a set input samples:

min A,D X -DA 2 F s.t. ∀i a i 0 ≤ τ, ∀j d j 2 = 1 (2.16)
where A = [a 1 , . . . , a N ] ∈ R L×N gives the sparse coding a i ∈ R L of samples x i and d j the jth atom of unit l 2 -norm. The above optimisation problem is not convex in both A and D, that is resolved in general by using a block-coordinate-descent method. This method consists of alternating two steps: 1) keep the dictionary D fixed and learn the sparse codes A and 2) keep the sparse codes A fixed and Algorithm 1 OMP

Input: x ∈ R d , D, τ . Output: a. 1: Initialization: r = x, Ω = {∅} 2: while |Ω| ≤ τ do 3:
Select the atom d j (j / ∈ Ω):

d j = arg max r T d j r 2 d j 2 4:
Update the set of selected atoms:

Ω = Ω ∪ j 5:
Update the coefficients:

a Ω = (D T Ω D Ω ) -1 (D T Ω x
) {where D Ω is the subs-dictionary of the selected atoms and a Ω the related coefficients}

6:

Estimate the residual:

r = x -D Ω a Ω 7: end while 8: Return a.
learn the dictionary D. The algorithm k-SVD uses a singular value decomposition (SVD) to learn jointly the dictionary as well as the sparse codes as follows.

Let us denote a j. = (a j1 , . . . , a jN ) is the jth row of matrix A, it provides the contribution of atom d j to reconstruct N input samples. To update d k , the objective function in Eq. (2.16) can be formulated as:

min A,D X -DA 2 F = min A,D X - L j=1 d j a j. 2 F = min A,D (X - j =k d j a j. ) -d k a k. 2 F = min A,D E k -d k a k. 2 F , (2.17)
where DA is expressed as the sum of L rank-1 matrices, each one giving the sparse representation of X involving one atom. The matrix E k ∈ R d×N stands for the error of reconstruction for the N samples excluding the kth atom. An SVD rank-1 approximation on E k can be used to find d k and a k. . However, the new a k.

may not be sparse anymore. To preserve the sparsity of a k. , the residual matrix

Algorithm 2 k-SVD Input: X = {x 1 , . . . , x N } ⊂ R d×N , D,τ . Output: D, A. 1: repeat 2:
for i = 1, . . . , N do

a i = OM P (x i , D, τ ) 3:
end for 4:

for k = 1, . . . , L do 5: Estimate E k = X -j =k d j a j. Ω k = {i/a ki = 0, i = 1, . . . , N } 6: Define E R k as the restriction of E k to Ω k 7:
Apply an SVD on E R k = U ΣV T

8:

Update

d k = u 1 and a R k. = σ 1 v 1 9:
end for 10: until convergence 11: Return D, A. E k is limited to only samples that involve atom d k . Denote ω k as the set of index where a k. is not zero and Ω k as a matrix of size N × |ω k | with 1 on the (ω k (i), i) entries and zeros elsewhere. a R k. and E R k are discarded the zeros columns of a k. and E k by multiplying to Ω k . Subsequently, SVD is used to estimate the closest rank-1 matrix that approximate E R k annd the first column u 1 , singular value σ 1 and right singular vector v 1 are then used to update the atom d k and its related coefficients a k. . k-SVD is an iterative algorithm (Algorithm 2) that alternates between sparse coding of the input samples based on the current dictionary and a process of updating the dictionary atoms to better fit the given data. The update of the dictionary columns is combined with an update of the sparse representations, thereby accelerating convergence. The k-SVD algorithm is flexible and can work with any pursuit method (e.g., basis pursuit, Focuss, or matching pursuit).

When dealing with complex data, kernel k-SVD may be required to learn in the feature space the dictionary and the sparse representations of the mapped samples as a nonlinear combination of the dictionary atoms [START_REF] Van Nguyen | Kernel dictionary learning[END_REF]. This method improves the separating margin between dictionaries and allow better tolerance against different types of degradation. Moreover, kernel k-SVD can provide better discrimination than the standard k-SVD and kernel PCA. Let us introduce a brief description of kernel k-SVD.

Let D = [d 1 , ..., d L ] ∈ R d×L be the dictionary composed of L atoms d j ∈ R d . The embedded dictionary Φ(D) = Φ(X)B is defined as a linear representation of Φ(X),
since the atoms lie in the subspace spanned by the Φ(X). The kernel dictionary learning problem takes the form The kernel k-SVD algorithm iteratively cycles between two stages. In the first stage, the dictionary is assumed fixed with B known and a kernel orthogonal matching pursuit (KOMP) technique [START_REF] Chandra Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF] is deployed to estimate A as

min B,A Φ(X) -Φ(X)B A 2 F , (2.18
min a i Φ(x i ) -Φ(X)Ba i 2 2 , (2.19)
s.t. a i 0 ≤ τ, ∀i = 1, . . . , N.
As in standard OMP, given a sample x, we select the atoms that best reconstructs Φ(x) by using the iterative proceduce. We denote that:

Φ(x) = Φ(X) x + r,
where x and r are respectively the current estimation of x and the current residual based on the selected atoms. Let Ω be the set of indices of selected atoms. The residual r is projected on the remaining dictionary atoms:

r, Φ(X)β i = Φ(x) -Φ(X) x, Φ(X)β i , = (k x -x T K)β i , ∀i / ∈ Ω. (2.20)
The method selects a new dictionary atom in the remaining set that gives largest projection coefficient in Eq. (2.20). This selection guarantees the biggest reduction of approximation error:

Ω = Ω ∪ arg max i r, Φ(X)β i
The sparse representation of Φ(x) on the selected dictionary atoms are obtained by using the least square solution:

a x = arg min ax Φ(x) -Φ(X)β Ω a x 2 2 , a x = (Φ(X)β Ω ) T (Φ(X)β Ω ) -1 (Φ(X)β Ω ) T Φ(x), = (β T Ω Kβ Ω ) -1 (k x β Ω ) T .
The estimation x is updated by

x = β Ω a x
The procedure is reiterate until the selection of τ atoms. Once the sparse codes A of the N samples estimated, the second stage of the kernel k-SVD is performed to update the dictionary B and sparse coding A. For that, the reconstruction error is defined as

min B,A Φ(X) -Φ(X)BA 2 F = min B,A Φ(X) -Φ(X) L j=1 β j a j. 2 F , = min B,A Φ(X)(I N - j =k β j a j. ) -Φ(X)β k a k. 2 F , = min B,A Φ(X)E k -Φ(X)β k a k. 2
F , ∀k = 1, . . . , L, (2.21)
with a j. ∈ R N referencing the j-th row of A and E k = I Nj =k β j a j. the error of reconstruction matrix when removing the k-th atom. An eigendecomposition is then preformed to get

(Φ(X)E R k ) T (Φ(X)E R k ) = (E R k ) T KE R k = V ΣV T , (2.22)
where E R k is the error of reconstruction restricted to the samples that have involved the k-th atom. The dictionary β k and sparse coding a R k. are updated by using the

first eigenvector v 1 with a R k. = σ 1 v T 1 and β k = σ -1 1 E R k v 1 . (2.23)
Similarly to kernel PCA, the obtained dictionary Φ(X)B of kernel k-SVD, that is a linear combination of Φ(x 1 ), . . . , Φ(x N ), lives in the high dimensional feature space. To restitute the learned sparse representation as well as the learned dictionary into the input space, a pre-image estimation problem should be solved.

Kernel regression

The linear regression problem has been widely used in statistics and machine learning. The non linear kernel regression was proposed later [START_REF] Drucker | Support vector regression machines[END_REF], it performs a linear regression in the kernel feature space, which represents a nonlinear regression in the input space. To avoid a large number of parameter estimations and computational difficulties, a dual version of ridge regression is proposed in [START_REF] Saunders | Ridge regression learning algorithm in dual variables[END_REF], closely related to Vapnik's kernel method [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF].

Given two sets X = [x 1 , . . . , x N ] and Y = [y 1 , . . . , y N ] with x i ∈ R p and the repesctive y i ∈ R q . The linear regression problem aims to learn a linear transformation L ∈ R q×p such that:

L = arg min L Y -LX 2 F ,
then predict y with respect to a new sample x, based on the obtained transformation:

y = Lx.
The ridge regression adds a regularisation term to the linear regression problem as:

Y -LX 2 F + λ L 2 F . (2.24)
with the regularisation parameter λ ≥ 0. The constrained formulation of Eq.

(2.24) is then:

R 2 F + λ L 2 F s.t. R = Y -LX (2.25)
Using Lagrange multipliers A ∈ R N ×q , we can replace the above constrained optimisation problem by

λ L 2 F + R 2 F + trace A(Y -LX -R) (2.26)
In the Kuhn Tucker theorem, there exist values of Lagrange A for which, the problem (2.25) is equivalent to the problem (2.26). First, to minimise (2.26), we make the differential in L equal to 0:

2λL -A T X T = 0 L = 1 2λ A T X T (2.27)
Substituting Eq. (2.27) into Eq. (2.26), we have

λ 1 2λ A T X T 2 F + R 2 F + trace A(Y - 1 2λ A T X T X -R) = 1 4λ trace A T X T (A T X T ) T + R 2 F - 1 2λ trace(AA T X T X) + trace(AY ) -trace(AR) = 1 4λ trace A T X T XA + R 2 F - 1 2λ trace(AA T X T X) + trace(AY ) -trace(AR) = - 1 4λ trace(AA T X T X) + R 2 F + trace(AY ) -trace(AR) (2.28)
Set the derivative of (2.28) with respect to R equal to 0, we obtain

2R -A T = 0 R = 1 2 A T (2.29)
Substituting Eq. (2.29) into (2.28), it leads:

- 1 4λ trace(AA T X T X) + 1 2 A T 2 F + trace(AY ) -trace(A 1 2 A T ) = - 1 4λ trace(AA T X T X) - 1 4 AA T + trace(AY ) (2.30)
Make the derivative of (2.30) with respect to A equal to 0, we have

- 1 2λ X T XA - 1 2 A + Y T = 0 A = 2λ(X T X + λI N ) -1 Y T (2.31)
Given a new sample x, from Eq. (2.27) the prediction y can be given by

y = Lx = 1 2λ A T X T x = 1 2λ (2λ(X T X + λI N ) -1 Y T ) T X T x = λY (X T X + λI N ) -1 X T x. (2.32)
To make nonlinear regression between X and Y , [START_REF] Saunders | Ridge regression learning algorithm in dual variables[END_REF] embed the input data X into a high dimensional feature space H via the feature mapping Φ, then construct a linear regression in the feature space between Φ(X) and Y . This linear regression problem can then be formulated as learning a transformation L:

L = arg min L Y -LΦ(X) 2 F
Similar to the dual linear regression in the input space, given a new sample x, the prediction of y is then obtained by using Eq. (2.32) and substituting X T X and X T x by respectively Φ(X) T Φ(X) and Φ(X) T Φ(x) as:

y = λY (Φ(X) T Φ(X) + λI N ) -1 Φ(X) T Φ(x). (2.33)
Using the property Φ(x), Φ(x ) = κ(x, x ) for all x, x ∈ R p , we have:

Φ(X) T Φ(X) = [Φ(x 1 ), . . . , Φ(x N )] T [Φ(x 1 ), . . . , Φ(x N )] = ( Φ(x i ), Φ(x j ) ) ij = (κ(x i , x j )) ij , and
Φ(X) T Φ(x) = [Φ(x 1 ), . . . , Φ(x N )] T Φ(x) = ( Φ(x 1 ), Φ(x) , . . . , Φ(x 1 ), Φ(x) ) T = (κ(x 1 , x), . . . , κ(x N , x)) T .
Hence, Eq. (2.33) is rewritten as:

y = λY (K + λI N ) -1 k T x .
(2.34)

with K = (κ(x i , x i )) i,i ∈ R N ×N and k T x = (κ(x 1 , x), . . . , κ(x N , x)) T ∈ R N .
While kernel regression learns a nonlinear transformation between X and Y by embedding X into the feature space, kernel dependency [START_REF] Vapnik | Kernel dependency estimation[END_REF] learns a nonlinear transformation between X and Y by embedding both sets into different feature spaces. In the first step, Y is embeded into the feature space H κ associated kernel κ, where a kernel PCA is performed to obtain the representation of Φ κ(Y ).

The p principal components are denoted u 1 , . . . , u p in H κ. By kernel PCA, the coefficient of any feature vector Φ κ(ϕ) can be defined by

P (Φ κ(ϕ)) = ( Φ κ(ϕ), u 1 , . . . , Φ κ(ϕ), u p ) T . (2.35)
Similarly, X is embedded in the feature space H κ related to the Gram matrix

K ∈ R N ×N with entries K ii = κ(x i , x i ).
Subsequently, the problem is to learn a transformation L between P (Φ κ(Y )) and Φ κ (X) as

L = arg min L P (Φ κ(Y )) -LΦ κ (X) 2 F
In the second step, given a new sample x and by using Eq. (2.34), the prediction of P (Φ κ(y)) is obtained as:

P (Φ κ(y)) = λP (Φ κ(Y ))(K + λI N ) -1 (k x ) T . (2.36) Let's denote γ 1 = λP (Φ κ(Y ))(K + λI N ) -1 (k x ) T ,
( Φ κ(y), u 1 , . . . , Φ κ(y), u p ) T = γ 1 Φ κ(y) ≈ [u 1 , . . . , u p ]γ 1 Φ κ(y) ≈ [Φ κ(Y )α 1 , . . . , Φ κ(Y )α p ]γ 1 Φ κ(y) ≈ Φ κ(Y )αγ 1 (2.37)
where α = [α 1 , . . . , α p ] are eigenvectors of Gram matrix K with entries Kii = κ(y i , y i ). For the prediction of y, the pre-image estimation of Φ κ(y), that is a combination of Φ(y 1 ), . . . , Φ(y N ) in Eq. (2.37), should be solved:

y = arg min y * Φ κ(y * ) -Φ κ(y) 2 F . (2.38)
In this chapter, we introduce three well-known kernel methods that are kernel PCA, kernel SVD and kernel regression. These methods have been used commonly for the analysis of complex and unstructured data by embedding the data into a feature space via a kernel mapping. The main trick behind these methods is to learn nonlinear structures in the input space by learning linear models in the feature space. While such approaches are fruitful and have widely proven their efficiency, the results obtained are lying in the kernel feature space, limiting further interpretations and analysis. The pre-image problem in then crucial to complement the kernel approaches and allows for any result obtained in the feature space to be restored into the initial space.

Related works for pre-image estimation

In this chapter, we will report the state of the art of the pre-image estimation problem. The pre-image estimation problem is formalised and the major related works on pre-image estimation on static and unstructured data are presented.

From the representer theorem [START_REF] Schlegel | When is there a representer theorem?[END_REF], any feature vector ϕ ∈ H obtained by some kernel method may be expressed in the following form:

ϕ = N i=1 γ i Φ(x i ), (3.1)
that is as a linear combination of the mapped input samples {Φ(x i )} N i=1 , and γ = (γ 1 , . . . , γ N ) T is called the coefficient vector of ϕ with respect to the set

{Φ(x i )} N i=1 .
The pre-image problem aims to find out a sample x ∈ X such that Φ(x) = ϕ. Since the feature space H has a much higher dimension than the input space X , the pre-image x may not exist. The pre-image problem is an

φ Φ -1 ℋ x* x 1 x N x i Φ( . ) Φ(x*) Φ(x 1 ) Φ(x N ) Φ(x i ) ? Figure 3
.1: Illustration of the pre-image problem ill-posed problem (illustrated in Figure 3.1), that is often addressed by providing an approximate solution, namely by estimating x * such that Φ(x * ) ≈ ϕ. In this section, we will discuss the major proposed approaches for pre-image estimation problem. First, in [START_REF] Schölkopf | Advances in kernel methods[END_REF] an exact solution for pre-image problem is proposed under two assumptions: the existence of the pre-image and the inversion of the kernel mapping. However, the exact pre-image of a feature vector may not exist and the invertibility of Φ is only hold for some kernels. Second, [START_REF] Mika | Kernel pca and de-noising in feature spaces[END_REF] cast the preimage problem as a nonlinear optimisation problem, which for particular choices of kernels, can be solved by the fixed-point iteration method. However, this method suffers from local minimum and numerical instabilities. Latter, [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] determine a relationship between the distances in the feature space and the distances in the input space, then apply a multidimensional scaling technique (MDS) to obtain the pre-image estimation. Unlike the method proposed in [START_REF] Mika | Kernel pca and de-noising in feature spaces[END_REF], the [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] method is non-iterative, involves only linear algebra and does not suffer from numerical instabilities or the local minimum problem. However, the obtained pre-image estimation is reconstructed by using only local information. The method proposed by [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] learns a new coordinate system in H making an isometry between the feature space and the input space. By representing ϕ in this coordinate system, its pre-image estimation can be obtained thanks to the inner product between its preimage and the input samples. This method provides a natural pre-image technique, requires only linear algebra, and is universal in the sense of being independent of the type of adopted kernels. The role of the kernel in the pre-image solution may vanish under some regularisation specifications. Recently, [START_REF] Gökhan | Learning to find preimages[END_REF] propose a method based on kernel PCA and kernel regression or kernel dependency [START_REF] Vapnik | Kernel dependency estimation[END_REF] to reconstruct pre-image estimation. In the following, we describe these five major methods to estimate the pre-image x of a given feature vector ϕ = N i=1 γ i Φ(x i ) ∈ H.

Exact pre-image solution

In Schölkopf [START_REF] Schölkopf | Advances in kernel methods[END_REF], according to the theorem 3.1, it is shown that if an exact preimage of ϕ exists, it would be easy to compute x such that Φ(x) = ϕ.

Theorem 3.1. Given a feature vector ϕ = N i=1 γ i Φ(x i ). If there exists a sample x ∈ R d such that Φ(x) = ϕ,
and if κ is an invertible kernel e.i κ(x, y) = f κ ( x, y ) with invertible function f κ , then we can compute x as

x = d i=1 f -1 κ N j=1 γ j κ(x j , e i ) e i ,
with {e 1 , . . . , e d } is any orthonormal basis of input space.

Let {e 1 , . . . , e d } be any orthonormal basis of input space X = R d . The pre-image

x is represented by:

x = d i=1
x, e i e i .

As f κ is invertible, the inner products are rewritten by

x, y = f -1 κ κ(x, y) = f -1 κ Φ(x), Φ(y) , ∀x, y ∈ X .
Hence, x may be expandes as:

x = d i=1 f -1 κ Φ(x), Φ(e i ) e i .
(3.2)

As ϕ = Φ(x) = N i=1 γ i Φ(x i ), x is then obtained as x = d i=1 f -1 κ N j=1 γ j Φ(x j ), Φ(e i ) e i = d i=1 f -1 κ N j=1 γ j κ(x j , e i ) e i . (3.3)
This method provides the exact solution of pre-image problem. However, the assumption of the existence of the pre-image x is not satisfied in many situations.

For instance, we consider the feature mapping that is formulated by

Φ :X → R X (3.4) x → κ(., x) (3.5)
Only feature vectors ϕ in H, that can be written as κ(., x), have an exact preimage solution under the mapping Φ. In the case of Gaussian kernels, if a feature vector ϕ has an exact pre-image solution x, that means that the Gaussian function κ(., x) is as a linear combination of the Gaussian functions κ(., x i ) as:

ϕ = N i=1 γ i Φ(x i ) Φ(x) = N i=1 γ i Φ(x i ) κ(., x) = N i=1 γ i κ(., x i ) (3.6)
However, in [START_REF] Micchelli | Interpolation of scattered data: Distance matrices and conditionally positive definite functions[END_REF], it is shown that any Gaussian function can not be written as a linear combination of Gaussian functions of the other samples, the exact preimage x of feature vector ϕ obtained by Eq. (3.6) may not exist. Furthermore, the inversion of f κ is only satisfied for some kernels as polynomial and sigmoid kernels.

Without the existence of an exact solution, other methods focus on finding an approximation for the pre-image solution, denoted by x * in the following.

Pre-image estimation by fixed-point iteration

In [START_REF] Mika | Kernel pca and de-noising in feature spaces[END_REF], a new approach is investigated for the pre-image estimation under the Gaussian kernel. This method proposes an iterative scheme to estimate the preimage x * of a given feature vector ϕ, where under particular Gaussian kernels, the fixed-point iteration method can be used. The problem is formalised as a nonlinear optimisation:

x * = arg min z∈X Φ(z) -ϕ 2 H = arg min z∈X Φ(z), Φ(z) -2 Φ(z), ϕ + ϕ, ϕ . (3.7)
As ϕ = N i=1 γ i Φ(x i ), we have

ϕ, ϕ = N i=1 γ i Φ(x i ), N i=1 γ i Φ(x i ) = γ T Kγ. (3.8)
Hence, ϕ, ϕ is independent of z. After the kernel κ normalisation and for all z, Φ(z), Φ(z) = κ(z, z) is constant. Rather than minimising Eq. (3.7), we can consider the maximisation problem:

x * = arg max z∈X Φ(z), ϕ . (3.9)
Substituting Eq. (3.1) into Eq. (3.9), we deduce

x * = arg max z∈X Φ(z), N i=1 γ i Φ(x i ) = arg max z∈X N i=1 γ i Φ(z), Φ(x i ) , = arg max z∈X N i=1 γ i κ(z, x i ) = arg max z∈X F (z) (3.10)
The optimisation problem in Eq. (3.10) can be solved by using gradient descent.

In particular, for a Gaussian kernel κ(x, y) = exp(-||x-y|| 2 2σ 2 ), we can use fixedpoint iterative method. We take the derivative of F (z) with respect to z and set it to zero, then we have

∂F ∂z = ∂ ∂z N i=1 γ i κ(z, x i ) = 0, ⇒ z = N i=1 γ i exp -||z -x i || 2 /(2 σ 2 ) x i N i=1 γ i exp -||z -x i || 2 /(2 σ 2 )
.

By the fix point iteration theorem, x * is a convergent point of the sequences

{z n } ⇒ z n+1 = N i=1 γ i exp -||z n -x i || 2 /(2 σ 2 ) x i N i=1 γ i exp -||z n -x i || 2 /(2 σ 2 ) . (3.11)
This method gives an approximate solution. But even this is nontrivial as the dimensionality of the feature space can be infinite. [START_REF] Mika | Kernel pca and de-noising in feature spaces[END_REF] cast this as a nonlinear optimisation problem, which, for particular choices of kernels ( such as the Gaussian kernel), can be solved by a fixed-point iteration method. However, the considered optimisation problem is highly non-convex, this method suffers from numerical instabilities. Moreover, as in any nonlinear optimisation problem, one can get trapped in a local minimum an the obtained pre-image estimation is thus sensitive to the initial guess.

Pre-image estimation by distance constraints

Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] address the problem of finding the pre-image of a given feature vector in the feature space induced by a kernel. Unlike the method proposed in [START_REF] Mika | Kernel pca and de-noising in feature spaces[END_REF] which relies on nonlinear optimisation, the Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] method directly finds the location of the pre-image based on the distance constraints in the feature space. It is non-iterative, involves only linear algebra, and does not suffer from numerical instability or local minimum problems. The distances between ϕ and Φ(x i ) and their relation to the distances between the pre-image x * and x i are used to estimate x * , as illustrated in Figure 3.2. The main steps of the proposed approach are detailed in the following.

Let d2 (ϕ, Φ(x j )) be the distances squared into the feature space between ϕ and Φ(x j ) defined as

d2 (ϕ, Φ(x j )) = ϕ -Φ(x j ) 2 F = ϕ, ϕ -2 ϕ, Φ(x j ) + Φ(x j ), Φ(x j ) = N i=1 γ i Φ(x i ), N i=1 γ i Φ(x i ) -2 N i=1 γ i Φ(x i ), Φ(x j ) + κ(x j , x j ) = γ T Kγ -2γ T K i. + K ij . (3.12)
where K i. and K ij are respectively the ith row and the ij entry of Gram matrix K.

Let Φ( ẋ1 ), . . . , Φ( ẋn ) denote the n-th closest elements to ϕ: For an isotropic kernel, the relation d 2 (x i , x j ) = g( d 2 (Φ(x i ), Φ(x j ))) between the distances in the input and the feature spaces can be established. For instance, with Gaussien kernel, given a parameter σ, we have

φ ℋ x* Φ • x 1 • x n • x i Φ( • x i ) Φ( • x 1 ) Φ( • x n )
g(z) = -2σ 2 ln(1 - 1 2 z) for z ∈ R. (3.14)
A solution is then deployed to determine the pre-image x such that

[d 2 (x, ẋ1 ), . . . , d 2 (x, ẋn )] = g( d 2 (Φ(x), Φ( ẋ1 ))), ..., g( d 2 (Φ(x), Φ( ẋn ))) , [ x -ẋ1 2 , . . . , x -ẋn 2 ] = [d 2 (x, ẋ1 ), . . . , d 2 (x, ẋn )].
For that, an SVD is deployed on the centered version of the submatrix X n = [ ẋ1 , ..., ẋn ], namely

X n (I n -1 n ) = U Λ V T = U Z, (3.15)
where U = [u 1 , . . . , u q ] is the d × q matrix of the left-singular vectors. Let Z = [z 1 , . . . , z n ] = ΛV T be the q × n matrix giving the projections of ẋi on the u j 's orthonormal vectors. We see the distance between x i to the origin equal to

d 2 0 = z i 2 .
Let z be the presentation of x in new system basic U , we have

d 2 (z, z i ) = d 2 (x, ẋi ). (3.16)
Following [START_REF] Gower | Adding a point to vector diagrams in multivariate analysis[END_REF], Eq. (3.16) can be shown to satisfy:

-2Z T z = (d 2 -d 2 0 ) - 1 n 1 n 1 T n (d 2 -d 2 0 ), (3.17)
with

d 2 0 = [ z 1 2 , ..., z n 2 ] T , d 2 = [d 2 1 , . . . , d 2 n ] T and d 2 i = g( d 2 (Φ(x), Φ( ẋi ))
). We multiple Z to Eq. (3.17):

-2ZZ T z = Z(d 2 -d 2 0 ) - 1 n Z 1 n 1 T n (d 2 -d 2 0 ). (3.18)
As Z is centered e.i. Z 1 n = 0, Eq. (3.18) is thus

-2ZZ T z = Z(d 2 -d 2 0 ), z * = - 1 2 (Z Z T ) -1 Z (d 2 -d 2 0 ). (3.19)
The pre-image x * estimation is then obtained as:

x * = U z * + 1 n X n 1 n . (3.20)
The proposed method that directly finds the location of the pre-image based on distance constraints. Applying a multidimensional scaling technique (MDS) leads to an inverse map estimate and thus to the pre-image. This method opens the door to a range of other techniques taking prior knowledge from input data in both space, such as manifold learning ( [START_REF] Etyngier | Shape priors using manifold learning techniques[END_REF]) and out-of-sample methods ( [START_REF] Bengio | Out-of-sample extensions forlle, isomap, mds, eigenmaps, and spectral clustering[END_REF], [START_REF] Arias | Connecting the out-ofsample and pre-image problems in kernel methods[END_REF]).

This method is non-iterative, involves only linear algebra and does not suffer from numerical instability or the local minimum problem. Moreover, it can be applied equally well to both isotropic kernel and dot product kernels. As the method uses distance constraints involved on the neighbourhood of ϕ, there is only the local information that may affect the pre-image estimation.

Pre-image estimation by isometry preserving

Solving the pre-image problem is pioneered by Mika's fixed point iterative optimisation technique. Recent approaches take advantage of prior knowledge provided by the input data , whose coordinates are known in the input space and implicitly in the feature space, a first step in this direction made by Kwork's algorithm based on multidimensional scaling. Using such prior knowledge, Paul Honeine [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] proposes a new approach to learn the pre-image, with the elegance that only linear algebre is involved. This method focus on learning a new coordinate system in RKHS, that preserves an isometry with the input space. That means the inner products between the input data are preserved in both representations. The representation of a given feature vector ϕ in the new coordinate system can give us some information to estimate its pre-image x. This proposed approach (illustrated in Figure 3.3) proceeds in two steps. First, a coordinate system, spanned by the feature vectors {Φ(x i )} N i=1 is learned to ensure an isometry with the input space; subsequently, the coordinate system is used to estimate the pre-image x of ϕ.

These two main steps are summarised in the followings: First, let Ψ = {ψ 1 , ..., ψ p } (p ≤ N ) be a coordinate system in the feature space with

ψ k = N i=1 α ik Φ(x i ) = Φ(X)α k , ∀k = 1, . . . , p,
e.i., each ψ k is defined as a linear combination of the mapped input samples Φ(x i ). This coordinate system can be written in a matrix form: Ψ = Φ(X)A, where A = [α 1 , . . . , α p ] ∈ R N ×p and Φ(X) = [Φ(x 1 ), . . . , Φ(x N )]. The projection of Φ(x) onto the coordinate system Ψ is defined by

ℋ Φ(x 1 ) Φ(x N ) Φ(x i ) x i x 1 x N ψ 1 ψ p ψ k x* φ Φ( . ) Figure 3.3:
The pre-image estimation by isometry preserving

P (Φ(x)) = [P 1 (Φ(x)), . . . , P p (Φ(x))] T = [ ψ 1 , Φ(x) , . . . , ψ p , Φ(x) ] T = [ Φ(X)α 1 , Φ(x) , . . . , Φ(X)α p , Φ(x) ] T = [k x α 1 , . . . , k x α p ] T = (k x [α 1 , . . . , α p ]) T = (k x A) T .
with k x = κ(x, x 1 ), . . . , κ(x, x N ) . Similarly, the projection of the mapped input set Φ(X) can be determined by

P (Φ(X)) = [P (Φ(x 1 )), . . . , P (Φ(x N ))] = [(k x 1 A) T , . . . , (k x N A) T ] = (KA) T .
Hence, to estimate the coordinate system Ψ that is isometric with the input space, the problem is determined by

P (Φ(x i )), P (Φ(x j )) = x i , x j ∀i, j ∈ {1, . . . , N }, P (Φ(X)), P (Φ(X)) = X, X , (KA) T , (KA) T = X, X , KAA T K = X T X. (3.21)
This leads to the following optimisation problem:

arg min A X T X -KAA T K F + λ p k=1 ψ i 2 , (3.22)
where λ is a the regularisation parameter of the term Ψ 2 F developed as follows:

p k=1 ψ i 2 = p k=1 ψ i , ψ i , = p k=1 Φ(X)α i , Φ(X)α i , = p k=1 Φ(X)α i α T i Φ(X) T , = Φ(X)AA T Φ(X) T = tr(KAA T ).
Hence, Eq. (3.22) is rewritten by using matrix formulation as

arg min A 1 2 X T X -K A A T K 2 F +λ tr(KA A T ) (3.23)
We write briefly A A T by Z, and call

f (Z) = 1 2 X T X -K Z K 2 F +λ tr(KZ), the derivation of f respected to Z computed by ∂f ∂Z = ∂[ 1 2 tr(X T X -K Z K)(X T X -K Z K) T + λtr(KZ)] ∂Z = 0, (3.24
)

∂f ∂Z = ∂[ 1 2 (tr((X T X) 2 ) -tr((X T X) K Z T K) -tr(K Z K (X T X))+ ∂Z +tr(K Z K K Z T K)) + λ tr(KZ)] ∂Z = 0, ∂f ∂Z = 1 2 (0 -K X T X K -K X T X K + K K Z K K + K K Z K K) + λ K = 0, K K Z K K = K P K -λ K = K (P -λ K -1 ) K, Z = K -1 (X T X -λ K -1 ) K -1 , AA T = K -1 (X T X -λ K -1 ) K -1 . (3.

25)

We use A A T to solve the pre-image problem rather that using A. Based on the isometric property, the pre-image x * is estimated as

P (Φ(x i )), P (ϕ) = x i , x * , ∀i = 1, . . . , N, P (Φ(X)), P (ϕ) = X, x * , (KA) T , (Kγ) T = X, x * , KAA T γ = X T x * . (3.26)
Substituting Eq. (3.25) into Eq. (3.26), we have:

X T x * = K K -1 (X T X -λ K -1 ) K -1 Kγ, X T x * = (X T X -λ K -1 )γ, x * = arg min z X T z -(X T X -λ K -1 )γ 2 . ( 3.27)
The problem (3.27) defines a standard overdetermined equation system (N d)

that can be resolved as a least-square minimisation problem (i.e., any technique such as the pseudo-inverse or the eigendecomposition). The pre-image estimation is then:

x * = (X X T ) -1 X (X T X -λ K -1 ) γ. (3.28)
As opposed to previous method, the proposed method neither suffers from the numerical instability, not requires computing the distances in the input space and the feature space. Using the inner product information in both spaces, this method provides a coordinate system in H space to learn the inverse mapping. The major advantage of this method resides on its simplicity in dealing with the optimisation issus, thanks to conventional linear algebra. Moreover, it is universal in the sense that it is independent of the type of kernels and the feature under investigation.

Note that, for lower values of λ ≈ 0, the obtained solution is no longer dependent of the kernel κ:

x * = (X X T ) -1 X X T X γ,

x * = Xγ

Pre-image estimation by kernel regression

Bakir [START_REF] Gökhan | Learning to find preimages[END_REF] the pre-image estimation consists in learning a kernel regression function that maps all the Φ(x i ) in the feature space H related to the kernel K to x i in the input space R d . For that, first kernel PCA is deployed to embed Φ(X) into the subspace spanned by the eigenvectors u 1 , ..., u p defined in Eq. (2.6), with u j = Φ(X)α j . This embedding can be defined by:

P : H → R p Φ(x) → P (Φ(x)) = (k x α) T ,
where P (Φ(x)) is the coefficient of Φ(x) with respect to PCA system {u 1 , . . . , u p } in Eq. (2.12). Then, a kernel regression is learned between the set of the projections in the kernel PCA subspace and X by the pre-image mapping Γ as

Γ : R p → R d P (Φ(x)) → Γ(P (Φ(x))) = (Γ 1 (P (Φ(x))), . . . , Γ d (P (Φ(x)))) T ,
with

Γ i = arg min Γ i N j=1 ||x j (i) -Γ i (P (Φ(x j ))|| 2 + λΩ(Γ i ) ∀i = 1, . . . , d, (3.29)
with Γ i (P (Φ(x)) = N j=1 δ j i κ(P (Φ(x)), P (Φ(x i ))). Here, κ(., .) is a new kernel on R p and δ j i are unknown parameters to estimate .

Denote that B ∈ R d×N is the regression coefficient matrix and K is the Gram matrix with entries K ii = κ(P (Φ(x i )), P (Φ(x i ))). The problem is typically rewritten as arg min

B∈R d×N X -B K 2 F + λ B 2 F . (3.30) Note f (B) = X -B K 2 F +λ B 2 F .
To minimise the function f , we put its derivation with respect to B equal to zero:

∂f ∂B = ∂ X -B K 2 F +λ B 2 F ∂B = 0, ∂ tr((X -B K)(X -B K) T ) + λ tr(B B T ) ∂B = 0, ∂ tr(X X T ) -tr(X K T B T ) -tr(B K X T ) + tr(B K K T B T ) + λ tr(B B T ) ∂B = 0.
As K is symmetric, then we have:

0 -X K -X K + 2 B K 2 + λ 2 BI N = 0, B( K 2 + λ I N ) = X K, B = X K( K 2 + λ I N ) -1 . (3.31)
For a feature vector ϕ = Φ(X)γ ∈ H, its pre-image x * is then estimated as:

x * = B( k P (ϕ) ) T , (3.32)
with k P (ϕ) = [ κ(P (ϕ), P (Φ(x 1 ))), ..., κ(P (ϕ), P (Φ(x N )))],

where

P (ϕ) = (k ϕ α) T , = ( ϕ, Φ(x 1 ) , . . . , ϕ, Φ(x N ) )α T , = ( Φ(X)γ, Φ(x 1 ) , . . . , Φ(X)γ, Φ(x N ) )α T , = (k x 1 γ, . . . , k x N γ)α T , = γ T Kα T , = α T Kγ, and
P (Φ(x i )) = (k x i α) T = α T k T x i , with α = [α 1 , . . . , α p ].
The method introduces a technique based on kernel principal component analysis and regression to reconstruct corresponding pre-image in the input space.

This method avoids difficult and unstable numerical optimisation, is easy to implement, and permits the computation of pre-images in discrete input space.

By using the pre-image mapping, each pre-image can be computed very efficiently, and there are no longer issues with complex optimisation code. Moreover, the method proposed a nonlinear model to adapt to the flexible data as well as keep the important role of the kernel. However, as substituting feature vector to its projection by kernel PCA, it requires that the used input samples be representative. Besides, the choice of kernel κ for kernel regression is trick to select.

Overview

To sum up, the three major methods (Section 3.3, 3.4, 3.5) presented above define three different approaches for pre-image estimation problem. First of all, all the methods involve only linear algebra and propose solutions that don't suffer from numerical instabilities. In Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF], the solution is mainly requiring the definition of a relation between the distances into the input and the kernel feature spaces. That requirement limite the Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] approach to linear or isotropic kernels. Honeine et al. [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] alleviate that point by proposing a closed-form solution that is applicable to any type of kernels. Furthermore, while in Honeine et al. [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] the pre-image estimation is obtained by learning a linear transformation into the feature space that preserves the isometry between the input and the feature space, in Bakir et al. [START_REF] Gökhan | Learning to find preimages[END_REF], the pre-image estimation is obtained by using a nonlinear kernel regression that predicts the input samples from their images into the feature space. Finally, while both [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] and [START_REF] Gökhan | Learning to find preimages[END_REF] proposals involve the whole training samples for pre-image estimation, Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] uses only the samples on the neighborhood of ϕ, which offers a significant speed-up; highly valuable in the case of large scale data.

Pre-image estimation for time series kernel analytics

While kernel machinery has been increasingly investigated with success for time series analytics [START_REF] Cao-Tri | Multi-modal and multi-scale temporal metric learning for a robust time series nearest neighbors classification[END_REF][START_REF] Soheily-Khah | Generalized k-means-based clustering for temporal data under weighted and kernel time warp[END_REF][START_REF] Varasteh Yazdi | Time warp invariant dictionary learning for time series clustering: application to music data stream analysis[END_REF][START_REF] Varasteh Yazdi | Time warp invariant ksvd: Sparse coding and dictionary learning for time series under time warp[END_REF], the pre-image problem for temporal data remains in its infancy. In addition, time series data, that may involve varying delays and be of different lengths, are naturally lying in a non-Euclidean input space, that makes the pre-image methods presented in Chapter 3 inapplicable. This Chapter proposes a pre-image estimation approach for time series kernel analytics, that consists of two steps. In the first step, a time warp function, driven by distance constraints in the feature space, is defined to embed time series in a metric space.

Subsequently, the time series pre-image estimation is cast as learning a linear or a nonlinear transformation that ensures a local isometry between the time series embedding space and the feature space.

4.1 Pre-image estimation by isometry preserving between X and Y Let X = [x 1 , . . . , x N ] be a d × N matrix giving the description of N samples

x i ∈ R d , and Y = [y 1 , ..., y N ] be a q × N matrix giving the description of the same N samples. We formalise the pre-image problem as the estimation of a linear transformation R that ensures an isometry between X and Y :

R * = arg min R X T X -Y T R Y 2 F with R ∈ R q×q . (4.1)
Assume that Y Y T is invertible ( q << N ). The closed-form solution can be obtained as:

R * = (Y Y T ) -1 Y X T X Y T (Y Y T ) -1 . (4.2)
Based on the inner product preservation, the pre-image estimation x * of a given y ∈ [Y ] is then:

x * = (X X T ) -1 X Y T R * y. (4.3)
If XX T is not invertible, we can add the regularity term as

x * = (X X T + λ I d ) -1 X Y T R * y.
Substituting Eq. (4.2) into Eq. (4.3), we have

x * = (XX T ) -1 XY T (Y Y T ) -1 Y X T XY T (Y Y T ) -1 y. (4.4) If Y are invertible, then (Y Y T ) -1 = (Y T ) -1 Y -1
and the Eq. (4.4) is then simplified as:

x * = XY -1 y. (4.5)

Pre-image estimation by isometry preserving between X and Φ(X)

Let X = [x 1 . . . , x N ] ∈ R d×N be a matrix giving the description of N samples x i .

In the context of kernel machinery, Φ(X) is the embedding of X into the RKHS under the kernel κ. The proposed pre-image method relies on learning a linear transformation R in the feature space that ensures an isometry between X and Φ(X). This result, is then extended to learn a nonlinear transformation R.

Learning linear transformation for pre-image estimation

The main idea to solve the pre-image problem is the isometry preserving in the same spirit as the method described in Section 4.1. For this purpose, we formalise the pre-image problem as the estimation of the square matrix R that establishes an isometry between X and Φ(X), by solving the optimization problem

R * = arg min R X T X -Φ(X) T R Φ(X) 2 F . (4.6)
By using a kernel PCA where a relevant subspace is considered, an explicit description P (Φ(X)) ∈ R p×N of Φ(X) is given and Eq. (4.6) can thus be rewritten as:

R * = arg min R∈R p×p X T X -P (Φ(X)) T R P (Φ(X)) 2 F . (4.7)
As P (Φ(X)) P (Φ(X)) T is invertible, similarly to Eq. (4.2), a closed-form solution is given by:

R * = P (Φ(X))P (Φ(X)) T -1 P (Φ(X))X T X P (Φ(X)) T P (Φ(X))P (Φ(X)) T -1 . (4.8)
The pre-image estimation x * of ϕ = N i=1 γ i Φ(x i ), is then given by:

x * = (XX T ) -1 X P (Φ(X)) T R * P (ϕ). (4.9)

From Eq. (2.12) in kernel PCA 2.1, the projection P (Φ(X)) is defined by

P (Φ(X)) = (P (Φ(x 1 )), . . . , P (Φ(x N ))) = ((k x 1 α) T , . . . , k x N α) T ) = α T K. (4.10)
and P (ϕ) is determined by

P (ϕ) = ( ϕ, u 1 , . . . , ϕ, u p ) T = ( ϕ, Φ(X)α 1 , . . . , ϕ, Φ(X)α p ) T = ( Φ(X)γ, Φ(X)α 1 , . . . , Φ(X)γ, Φ(X)α p ) T = (γKα) T = α T Kγ. (4.11)
with α defined in Eq. (2.12). Substituting Eq. ( 4.11) into Eq. (4.9), we have:

x * = (XX T ) -1 X P (Φ(X)) T R * α T Kγ. (4.12)
One can easily include some regularisation terms in the optimisation problems (4.7) and (4.8), which can be easily propagated to the pre-image expression. For example, in the case of non-invertible XX T , a regularisation term is introduced in Eq. (4.12) as:

x * = (XX T + λI d ) -1 X P (Φ(X)) T R * α T Kγ, (4.13)
for some positive regularisation parameter λ.

Learning nonlinear transformation for pre-image estimation

In the following, we propose to extend the above result to learn nonlinear transformations for pre-image estimation. Let κ be a kernel defined on the feature space H, and Φ the corresponding embedding function that maps any element of H into the Hilbert space defined by κ. With some abuse of notation, we denote Φ(Φ(X))

the matrix of all mapped elements Φ(Φ(x i )), for i = 1, ..., N . Let K be the Gram matrix of general term κ(Φ(x i ), Φ(x j )).

The pre-image estimation problem can be then defined as learning a nonlinear transformation that defines an isometry between X and Φ(Φ(X)) as:

R * = arg min R X T X -Φ(Φ(X)) T R Φ(Φ(X)) 2 F . (4.14)
By using kernel PCA, Eq. ( 4.15) can be rewritten by:

R * = arg min R X T X -P ( Φ(Φ(X))) T R P ( Φ(Φ(X))) 2 F . (4.15)
Similarly, a closed-form solution for R * can be obtained as:

R * = (P ( Φ(Φ(X))) P ( Φ(Φ(X))) T ) -1 P ( Φ(Φ(X))) (4.16) X T XP ( Φ(Φ(X))) T (P ( Φ(Φ(X)))P ( Φ(Φ(X))) T ) -1 ,
and

P ( Φ(Φ(X))) = α T K. (4.17)
where α is a matrix of the eigenvectors of K. To estimate K, an indirect manner is to use a kernel PCA, with κ(Φ(x i ), Φ(x j )) ≈ κ(P (Φ(x i )), P (Φ(x j ))). A simpler way is possible when dealing with kernels that are radial basis functions. For example, for the well-known Gaussian kernel κ, K is estimated directly from K as:

κ(Φ(x i ), Φ(x j )) = exp - Φ(x i ) -Φ(x j ) 2 2σ 2 , = exp - Φ(x i ), Φ(x i ) -2 Φ(x i ), Φ(x j ) + Φ(x j ), Φ(x j ) 2σ 2 , = exp - κ(x i , x i ) -2κ(x i , x j ) + κ(x j , x j ) 2σ 2 . (4.18)
The estimation of the pre-image of ϕ = N i=1 γ i Φ(x i ) is then given by the time series x * :

x * = (XX T ) -1 X P ( Φ(Φ(X))) T R * P ( Φ(ϕ)), (4.19)
with P ( Φ(ϕ)) = ( k ϕ α) T , where k ϕ is the vector whose i-th entry is

κ(ϕ, Φ(x i )) = exp - ϕ -Φ(x i ) 2 2σ 2 , = exp - ϕ, ϕ -2 ϕ, Φ(x i ) + Φ(x i ), Φ(x i ) 2σ 2 , = exp - Φ(X)γ, Φ(X)γ -2 Φ(X)γ, Φ(x i ) + Φ(x i ), Φ(x i ) 2σ 2 , = exp - γ T Kγ -2 γ T k T x i + K ii 2σ 2 . (4.20)
The above proposed formulations and results for pre-image estimation (Section 4.2.1) present some similarities and differences with the method proposed in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] and presented in Section 3.4. First of all, both approaches propose formulations and solutions that only require linear algebra and are independent of the type of kernel. To establish the isometry, in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] a linear transformation restricted to the form R = Φ(X)AA T Φ(X) T is estimated, whereas in our proposal the estimated R may be linear Eq.(4.6) or non linear Eq.( 4.15) and is importantly unconstrained, namely of general form which enlarges its potential to deal with complex structures. Finally, while in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] the solution Eq.(3.28) involves the kernel information through the regularisation term, which may be canceled for lower values of λ, in the proposed solutions Eq.(4.13) and Eq.( 4. [START_REF] Chiba | Dynamic programming algorithm optimization for spoken word recognition[END_REF]) the kernel information is entirely considered regardless of the regularisation specifications.

Pre-image estimation for time series kernel analytics

In the previous Section 4.2.1, data are assumed static or be a set of time series of the same length and thus lying in a metric space. In this Section we consider X = {x i } N i=1 as instead composed of time series x i of different lengths t i that are located in a non-metric space, rendering the previous results as well as the pre-image estimation related works not applicable.

To address the pre-image estimation for such challenging time series, we define an embedding function that allows to represent the time series in a metric space, where the previous linear and nonlinear transformations method for pre-image estimation can be performed conveniently. Before that, we introduce the concept of time series alignment and give the definition of some temporal kernels.

Time series alignment

Let x i and x j be two time series. To resorb the delays arising in time series, a temporal alignment between each x i and x j is performed by dynamic programming. An alignment π of length |π| = m between x i and x j is defined as the set of m increasing couples π = ((π 1 (1), π 2 (1)), (π 1 (2), π 2 (2)), ..., (π 1 (m), π 2 (m))), where the applications π 1 and π 2 defined from {1, ..., m} to {1, ..., t i } and {1, ..., t j } respectively obey to the following boundary and monotonicity conditions:

1 = π 1 (1) ≤ π 1 (2) ≤ ... ≤ π 1 (m) = t i , 1 = π 2 (1) ≤ π 2 (2) ≤ ... ≤ π 2 (m) = t j , and ∀ l ∈ {1, ..., m}, π 1 (l + 1) ≤ π 1 (l) + 1 and π 2 (l + 1) ≤ π 2 (l) + 1, (π 1 (l + 1) -π 1 (l)) + (π 2 (l + 1) -π 2 (l)) ≥ 1.
Intuitively, an alignment π between x i and x j describes a way to associate each element of x i to one or more elements of x j and vice-versa. Such an alignment can be conveniently represented by a path in the t i × t j grid, as shown in Figure 4.1 (left), where the above monotonicity conditions ensure that the path is neither going back nor jumping. The optimal alignment π * between x i and x j is then obtained as:

π * = arg min π x π 1 i -x π 2 r 2 . (4.21)
where x π 1 i = (x i π 1 (1) , ..., x i π 1 (m) ) and x π 2 j = (x j π 2 (1) , ..., x j π 2 (m) ) are x i and x j aligned through π. In the left, the temporal alignment between x i (t i = 5) and x j (t j = 6), the optimal alignment π * is indicated in red. In the right, the optimal alignment is illustrated as connections between two time series.

Proximity measure between time series

Dynamic time warping [START_REF] Berndt | Using dynamic time warping to find patterns in time series[END_REF] is a well-known dissimilarity measure on time series that capture temporal distortions. Based on the optimal alignment π * , the Dynamic time warping (dtw) between two time series x i and x j is defined by

dtw(x i , x j ) = x π * 1 i -x π * 2 j 2 ,
where π * is determined in Eq. (4.21).

However, dtw is not a metric as not satisfy the triangle inequality:

dtw(x i , x j ) + dtw(x i , x k ) dtw(x k , x j ).
The dynamic programming approach [START_REF] Berndt | Using dynamic time warping to find patterns in time series[END_REF] is used to find the optimal alignment as well as the minimum distance dtw between two time series. The complexity of

t ∈ |x i | -T |x j | -T (t -T ), |x i | -T |x j | -T (t + T ) ∩ 1, . . . , |x i | .
The Itakura parallelogram describes a region that constrains the slope of a warping path. Given any slope S ∈ {R > 1}, the domain of Itakura parallelogram lies between two warping paths with the slopes of the values 1/S and S. These constraints significantly speed up the computation of dtw as well as any measure based on the optimal time warping alignment. For instance, in case of a Sakoe-Chiba of a band T , the complexity of computation is only

O(T × max(|x i |), |x j |) instead of O(|x i | × |x j |) required in standard dtw.
For temporal data, several kernels under time warping that are proposed in the last years allow to apply kernel methods for time series. First of all is the Gaussian dynamic time warping kernel (kdtw) [START_REF] Bahlmann | Online handwriting recognition with support vector machines-a kernel approach[END_REF] defined by

kdtw(x i , x j ) = exp - 1 σ dtw(x i , x j ) ,
where σ is a normalisation parameter. In general, kdtw is not positive definite kernel that allows to embed data into Hilbert feature space. However, this kernel can procedure good results in some cases [START_REF] Haasdonk | Tangent distance kernels for support vector machines[END_REF], [START_REF] Decoste | Training invariant support vector machines[END_REF].

The Dynamic time alignment kernel (dtak) proposed in [START_REF] Hiroshi | Dynamic time-alignment kernel in support vector machine[END_REF] adjust another similarity or kernel between two time series by finding the optimal alignment to maximise the accumulated similarity between two time series:

dtak(x i , x j ) = max π 1 |π| (t,t )∈π s(x it , x jt )
where in particular s(

x it , x jt ) = exp -1 σ 2 x it -x jt 2
, and in general s(., .) is any similarity measure on R d . dtak is a symmetric kernel function, however, it may be not a positive definite kernel. Note that, in practice, several ad-hoc methods that perturb the whole diagonal by the absolute of the smallest eigenvalue are used to ensure the positive definiteness of Gram matrix of dtak .

Global alignment kernel (kga) [START_REF] Cuturi | A kernel for time series based on global alignments[END_REF] is not based on the optimal alignment, but takes advantage of all accumulated similarity by all possible alignment, defined by:

kga(x i , x j ) = π (t,t )∈π κ(x it , x jt )
where

κ(x it , x jt ) = exp -λ( 1 2σ 2 x it -x jt 2 + log(2 -e -1 2σ 2 x it -x jt 2 )) .
kga that is positive definite kernel under mild condition, do a better job of quantifying all similarities coherently, because it consider all possible alignments. Global alignment kernel have been obtain success in different application fields [START_REF] Joder | Temporal integration for audio classification with application to musical instrument classification[END_REF], [START_REF] Ricci | Learning pedestrian trajectories with kernels[END_REF] and shown to be competitive to other kernels. However, similar to kdtw and dtak, kga has quadratic complexity of computation O(|x i | × |x j |).

Pre-image estimation for time series analytics

Let us consider now that X = {x i } N i=1 is a set of N time series, where each x i ∈ R d×t i is a multivariate time series that may have different length t i and involve varying delays. Let Φ(x i ) be the Φ-mapping of the time series x i into the Hilbert space H related to a temporal kernel κ(., .) that involves dynamic time alignments such as Dtak [START_REF] Hiroshi | Dynamic time-alignment kernel in support vector machine[END_REF], Kdtw [START_REF] Bahlmann | Online handwriting recognition with support vector machines -a kernel approach[END_REF], Kga [START_REF] Cuturi | A kernel for time series based on global alignments[END_REF]. Given ϕ = N i=1 γ i Φ(x i ) a result generated in H, the objective is to estimate the time series x * ∈ R d×t * that is the pre-image of ϕ. This problem is particularly challenging since, under varying delays, the time series are not longer lying into a metric space, which makes inapplicable the related work pre-image estimation approaches. Note that, if the time series are assumed of the same length and lying in a metric space, then the proposed method in Section 4.2 can be applied.

To address the pre-image estimation for such challenging time series, we propose an embedding function that allows to represent time series into a metric space, where the previous linear and nonlinear pre-image estimation can be performed conveniently.

For this purpose, first we define N ϕ in H and N -1 ϕ as the set of the n-closest neighbours of ϕ and its pre-image, given as:

N ϕ = Φ(x i ) Φ(x i ), ϕ = N j=1 γ j κ(x i , x j ) is among the n highest values (4.22) N -1 ϕ = x i Φ(x i ) ∈ N ϕ . (4.23)
Let Φ(x r ) be the representative of N ϕ with x r ∈ R d×t * defined as:

Φ(x r ) = arg max Φ(x i )∈Nϕ Φ(x j )∈Nϕ Φ(x i ), Φ(x j ) = arg max Φ(x i )∈Nϕ Φ(x j )∈Nϕ κ(x i , x j ). (4.24)
We define f r , the temporal embedding function, that allows to embed time series

1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 ir W                  𝑥 𝑟 𝑥 𝑖 𝑥 𝑟2 𝑥 𝑟1 𝑥 𝑟4 𝑥 𝑟3 𝑥 𝑟5 𝑥 𝑟6 𝑥 𝑖2 𝑥 𝑖1 𝑥 𝑖3 𝑥 𝑖4 𝑥 𝑖5 Figure 4.3:
In the left, the temporal alignment between x i (t i = 5) and x r (t * = 6), the optimal alignment π * is indicated in red. In the right, the adjacency binary matrix related to the optimal temporal alignment.

x i ∈ R d×t i into a new temporal metric space as:

f r : X -→ X ⊂ I = R d×t * x i -→ f r (x i ) = x i W ir N ir (4.25)
where W ir ∈ {0, 1} t i ×t * is the binary matrix related to the optimal temporal alignement between x i and x r , as shown in Figure 4.3 (right). The matrix

N ir = diag(W T ir 1 t i ) -1
is the weight diagonal matrix of order t * , of general term 1 |Nt| , that gives the weight of the element t of x r , where |N t | is the number of time stamps of x i aligned to t. In particular, note that x r remains unchanged by f r , as

W rr = N rr = diag([1, 1, . . . , 1]
). The set of embedded time series X = {f r (x 1 ), ..., f r (x N )} is for now lying in a metric space I, where the delays are resorbed w.r.t. the representative time series x r . The pre-image solution provided in the method described in Section 4.1 can be developed to establish a linear or nonlinear isometry between X and Φ(X).

Experimental results

In this section, we evaluate the efficiency of the proposed pre-image estimation method under three major time series analysis tasks: 1) time series averaging, 2) time series reconstruction and denoising and 3) time series representation learning. The proposed pre-image estimation method TsPrima is compared to three major alternative approaches introduced in Chapter 3 as Honeine in Section 3.4, [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF], Kwok in Section 3.3, [START_REF] Kwok | The pre-image problem in kernel methods[END_REF], and Bakir in Section 3.5, [START_REF] Gökhan | Learning to find preimages[END_REF] methods. The experiments are conducted on 33 public datasets (Table 5.1) including univariate and multivariate time series data, that may involve varying delays and be of the same or different lengths. The 25 first datasets in Table 5.1 are selected from the archive given in [START_REF] Keogh | The ucr time series data mining archive[END_REF][START_REF] Kamgar | The ucr time series classification archive[END_REF] To obtain a manageable number of datasets, the 3 above selection criteria are applied on the top 40 datasets, in the order set out in [START_REF] Hu | The ucr time series classification archive[END_REF]. The 25 obtained datasets are composed of univariate time series and half of the datasets include significant delays. We consider a dataset as including significant delays if the difference between the 1-NN Euclidean distance error and the 1-NN Dynamic time warping [START_REF] Chiba | Dynamic programming algorithm optimization for spoken word recognition[END_REF] error is greater than 5%. The 5 next datasets include univariate and multivari-ate time series covering local and noisy salient events as described in [START_REF] Varasteh Yazdi | Time warp invariant ksvd: Sparse coding and dictionary learning for time series under time warp[END_REF][START_REF] Soheily-Khah | Generalized k-means-based clustering for temporal data under weighted and kernel time warp[END_REF][START_REF] Frambourg | Learning multiple temporal matching for time series classification[END_REF] and the three last datasets are related to handwritten digits and characters, they are described as multivariate time series of variable lengths [START_REF] Chen | A new 6d motion gesture database[END_REF]. In the following, Section 5.1 gives the data description and Section 5.2 details the validation and evaluation process. Finally, we discuss the obtained results in Section 5.7.

Data description

The experiments are conducted on three groups of datasets. The first group is composed of the 25 datasets from ucr [START_REF] Keogh | The ucr time series data mining archive[END_REF] that is the most commonly used data for time series analytics. Each dataset is a collection of univariate time series of the same length and pre-divided into training and test sets. In the second group, we consider bme, umd, powercons and spiral datasets, where time series share local temporal features within the classes while being of distinctive global behaviour, and include huge noise (Figure 5.4). For example, bme (Figure 5.2) includes two challenging classes begin and end characterised by a small bell arising at the initial and final periods respectively. The overall behaviour may be different depending on whether the large bell is pointing upward or downward. umd (Figure 5.1) introduces more complexity with the classes up and down characterised by a small bell that may occur at different time stamps. spiral1 (Figure 5.3) and spiral2 (Figure 5.4) share a latent 3-D time series that may appear randomly at different time stamps, in particular of spiral2 time series involve high level of noise at the initial and final periods. - Nintendo device by different writers [START_REF] Chen | A new 6d motion gesture database[END_REF].

In summary, Table 5.1 indicates for each dataset: the number of classes (Nb.

Class), the size of training set (Train size), the size of test set (Test set), the time

Validation process

In this section, we evaluate the proposed method in the context of averaging, reconstruction and denoising, and representation learning. We conduct the four methods: Honeine, Kwok, Bakir and the proposed method TsPrima on the datasets (shown in Section 5.1). For the comparison, we rely on the standard dtak which measures the similarity between the obtained time series and the truth ones in denoising and reconstruction, representation, or the inertia of the obtained centroid in averaging, to evaluate each method. The higher the index, the better the agreement is. For each method, the related parameters indicated in Table 5.2 are learned by a grid search on validation set, the best parameters are then used to perform these tasks on the evaluation set. The process is iterated over 10 runs and the averaged performances are reported in Table 5.5, 5.4, and 5.6.

Time series averaging by pre-image estimation

Estimating the centroid of a set of time series is a major topic for many time series analytics as summarisation, prototype extraction or clustering. Time series averaging has been an active area in the last decade, where the propositions mainly focus on tackling the tricky problem of multiple temporal alignments [START_REF] Frambourg | Learning multiple temporal matching for time series classification[END_REF][START_REF] Soheily-Khah | Progressive and iterative approaches for time series averaging[END_REF][START_REF] Soheily-Khah | Generalized k-means-based clustering for temporal data under weighted and kernel time warp[END_REF].

A suitable way to circumvent the problem of multiple temporal alignments is to use a temporal kernel method to evaluate the time series centroid in the feature space. The pre-image of the centroid is then estimated to obtain the time series averaging in the input space.

In that context, let X = {x i } N i=1 and Φ(X) = {Φ(x i )} N i=1 be, respectively, a set of time series and their mapped images into the Hilbert space H related to the temporal kernel dtak [START_REF] Shimodaira | Dynamic time-alignment kernel in support vector machine[END_REF]. The centroid of X with respect to dtak is defined by

x * = arg max y∈X N i=1 dtak(y, x i ).
As Φ(z), Φ(z) = dtak(z, z) = 1 for any time series z, we have

x * = arg max
Φ(y) -Φ(x i ) 2 ⇒ Φ(x * ) = 1 N N i=1 Φ(x i )
Hence, let ϕ = 1 N N i=1 Φ(x i ) be the centroid of the mapped time series in the feature space and x * its pre-image in the input space. The quality of the obtained centroids is given by the within inertia i dtak(x * , x i ); the higher the within inertia, the better is the estimated centroid.

To evaluate the efficiency of each pre-image estimation method, the time series centroid is estimated for each class of the studied datasets and the induced within-class inertia is evaluated. The average within-class inertia is then reported in Table 5.3 for each dataset and each pre-image estimation method; the best values are indicated in bold (t-test at 5% risk). In addition, a Nemenyi test [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF] is performed to For the time series denoising task, first a kernel PCA is performed on the training set, then a (0, σ 2 ) Gaussian noise is added to the test samples x to generate noisy samples x with different variances σ 2 . The denoised sample is obtained as the preimage x * of its kernel PCA projection P (Φ( x)), with γ defined as in Eq. (5.1).

Similarly, the quality of the denoising is measured as the similarity dtak(x * , x) between x * and the initial x. Table 5.5 gives, for different values of σ 2 , the average quality of the denoising for some datasets. Figure 5.10 illustrates the denoising results for some challenging times series of the noisy spiral2 data and of the class "M" of upper dataset. the learned sparse representations is then measured as the similarity dtak(x i , x * i ) between each time series x i and the pre-image x * i of the sparse representation Φ(X)B a i . Table 5.6 gives the average quality of the learned representations for each dataset and each pre-image estimation method. Figure 5.11 gives the critical difference diagram related to the Nemenyi test for the average ranking comparison of the studied methods. Figure 5.12 shows the learned representations for some time series of digits, lower and upper datasets and Figure 5.13 illustrates, for a challenging sample of the class "k" of lower dataset, the learned representations as well as the top 3 atoms involved in its reconstruction.

Further comparison

In the previous experiments (Sections 5.3 to 5.5), we have evaluated the performances of TsPrima that are mainly due to two major ingredients : 1) the defined temporal embedding function f r (Section 4.3.3) and 2) the proposed transformation R to preserve an isometry between the time series embedding space and the feature space (Section 4.2). In this last part, the aim is to evaluate the efficiency of the proposed transformation R, regardless of the effect of f r . For that, TsPrima is compared to the alternative methods Honeine, Kwok and Bakir once all the time series embedded into the same metric space; namely, all the pre-image estimation methods are performed between the time series embedding space and the feature space. Similar experiments are performed on the 33 public datasets (Table 5.1), the results obtained for the three tasks are summarised into Table 5.7 and the related Nemenyi tests are given in Figure 5.14.

Overall analysis

The experiments conducted show that the proposed method TsPrima leads on almost all the datasets and through the three studied tasks to the best results.

On the other hand, the performances obtained by the alternative methods seem slightly equivalent and lower than those obtained by TsPrima.

In particular, for time series averaging task, we can see in Table 5. For time series reconstruction, Table 5.4, shows that TsPrima leads to the highest reconstruction accuracy through almost all the datasets, followed by Honeine, Bakir and Kwok methods. Figure 5.8 indicates that there is no significant difference between the performances of the three state of the art methods (connected by a solid bold line). These results are assessed in Figure 5.9 that shows, for some input time series, the quality of the reconstructions obtained by

TsPrima and the state of the art methods.

For the time series denoising task, we observe from Table 5.5 and for all the methods that the quality of the denoising decreases when the intensity of noise increases. This result is illustrated in Figure 5.10, that shows the denoising results of the time series "M" of upper dataset and of the highly noisy time series of spiral2 dataset. In particular, note that Kwok and TsPrima methods lead to the best results on spiral2 dataset and seem less sensitive to noise than Honeine and Bakir.

Lastly, for time series representation learning task, Table 5.6 indicates that each studied method leads to the best sparse representation for at least some datasets and that TsPrima perform better on almost all the datasets. Figure 5.12 shows the goodness of the sparse representation obtained. While all the methods succeed to sparse represent some input time series, the time series "k" and "B" classes appear challenging for Honeine and Bakir methods. In Figure 5.13, we get a look on the quality of the learned atoms, that are involved into the reconstruction of the input samples. The first row gives for some input samples "k" (on the left), the sparse representation learned by each method. The three next rows, provide the three first atoms involved into the reconstructions. We can see that while the first atom learned by TsPrima is nearly sufficient to sparse present the "k" input sample, the state of the art methods need obviously more that one atom to sparse represent the input sample. Finally, the analysis of Figure 5.13 indicates that Honeine method performs equivalently that Kwok and Bakir, whereas the Kwok performances are significantly better than those of Bakir method.

Further comparisons (Table 5.7) are conducted in Section 5.6 to evaluate the efficiency of TsPrima related to the learned transformation R, regardless of the temporal embedding f r . For averaging task, TsPrima, Honeine and Bakir lead equivalently to the best performances, followed by Kwok method (Figure 5.14 (a)). From these results we can conjecture that, linear transformations seem sufficient to achieve good pre-image estimations for averaging task on these datasets, as both linear and nonlinear approaches (TsPrima, Honeine, Bakir) perform equivalently. Furthermore, while Honeine and Bakir involve the whole datasets for the centroid pre-image estimations, Kwok uses a subset of samples into the neighbourhood of ϕ, which may explain the slightly lower performances of Kwok method. Note that, although TsPrima involves, similarly to Kwok method, fewer samples into the neighbourhood of ϕ, it succeeds to reach the best performances thanks to the efficiency of the learned transformation R. For the remaining tasks reconstruction, denoising and representation learning, TsPrima achieves the highest performances, followed by far by Finally, as all the studied methods propose closed-form solutions, they lead to comparable complexities. However, for large data, TsPrima and Kwok methods are expected to perform faster as requiring fewer samples on the neighbourhood of ϕ than Honeine and Bakir that involve the whole samples for pre-image estimation. Note that the complexity of the proposed solutions is mainly related to the matrix inversion operator. In Kwok method, the inversion of ZZ T required in Eq. 3.19, where Z is of dimension (q × n) and n is the neighbourhood size, induces a complexity of O(q 2 n) + O(q 3 ); as q is in general small and fixed beforehand, the overall complexity is about O(n). For Honeine method, Eq. Finally, as all the studied methods propose closed-form solutions, they lead to comparable complexities. However, for large data, TsPrima and Kwok methods are expected to perform faster as requiring fewer samples on the neighborhood of ϕ than Honeine and Bakir that involve the whole samples for pre-image estimation.

Conclusion

This work proposes TsPrima, a new closed-form pre-image estimation method for time series analytics under kernel machinery. The method consists of two stages.

In the first step, we define a time warp embedding function, driven by distance constraints in the feature space, that allows to embed the time series in a metric space. In the second step, the time series pre-image estimation is cast as learning a linear (or a nonlinear) transformation to ensure a local isometry between the time series embedding space and the feature space. Extensive experiments show the efficiency and the benefits of TsPrima through three major tasks that require pre-image estimation: 1) time series averaging, 2) time series reconstruction and denoising and 3) time series representation and dictionary learning.

Conclusion and future work

In Chapter 2, we introduce three well-known kernel methods that are kernel PCA, kernel SVD and kernel regression. These methods have been used commonly for the analysis of complex and unstructured data by embedding the data into a feature space via a kernel mapping. The main trick behind these methods is to learn nonlinear structures in the input space by learning linear models in the feature space. While such approaches are fruitful and have widely proven their efficiency, the results obtained are lying in the kernel feature space, limiting further interpretations and analysis. The pre-image problem in then crucial to complement the kernel approaches and allows for any result obtained in the feature space to be restored into the initial space.

In Chapter 3, the three major methods (Section 3.3, 3.4,3.5) presented above define three different approaches for pre-image estimation problem. First of all, all the methods involve only linear algebra and propose solutions that don't suffer from numerical instabilities. In Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF], the solution is mainly requiring the definition of a relation between the distances into the input and the kernel feature spaces. That requirement limits the Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] approach to linear or isotropic kernels. Honeine et al. [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] alleviate that point by proposing a closed-form solution that is applicable to any type of kernels. Furthermore, while in Honeine et al. [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] the pre-image estimation is obtained by learning a linear transformation into the feature space that preserves the isometry between the input and the feature space, in Bakir et al. [START_REF] Gökhan | Learning to find preimages[END_REF], the pre-image estimation is obtained by using a non linear kernel regression that predicts the input samples from their images into the feature space. Finally, while both [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] and [START_REF] Gökhan | Learning to find preimages[END_REF] proposals involve the whole training samples for pre-image estimation, Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] uses only the samples on the neighborhood of ϕ, which offers a significant speed-up; highly valuable in the case of large scale data.

Chapter 4 proposed formulations and results for pre-image estimation (Section 4.2.1) presented some similarities and differences with the method proposed in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] and presented in Section 3.4. First of all, both approaches propose formulations and solutions that only require linear algebra and are independent of the type of kernel. To establish the isometry, in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] a linear transformation restricted to the form R = Φ(X)AA T Φ(X) T is estimated, whereas in our proposal the estimated R may be linear Eq. (4.6) or non linear Eq. (4.15) and is importantly unconstrained, namely of general form which enlarges its potential to deal with complex structures. Finally, while in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] the solution Eq. (3.28) involves the kernel information through the regularisation term, which may be canceled for lower values of λ, in the proposed solutions Eq. (4.13) and Eq. (4.19) the kernel information is entirely considered regardless of the regularisation specifications.

To address the pre-image estimation for such challenging time series, we proposed an embedding function that allows to represent the time series in a metric space, where the previous linear and nonlinear transformations method for pre-image estimation can be performed conveniently.

Chapter 5 evaluated the efficiency of the proposed pre-image estimation method under three major time series analysis tasks: 1) time series averaging, 2) time series reconstruction and denoising and 3) time series representation learning.

The proposed pre-image estimation method TsPrima is compared to three major alternative approaches introduced in Chapter 3 as Honeine in Section 3.4, [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF],

Kwok in Section 3.3, [START_REF] Kwok | The pre-image problem in kernel methods[END_REF], and Bakir in Section 3.5, [START_REF] Gökhan | Learning to find preimages[END_REF] methods.

To sum up, this thesis proposes TsPrima, a new closed-form pre-image estimation method for time series analytics under kernel machinery. The method consists of two stages. In the first step, we define a time warp embedding function, driven by distance constraints in the feature space, that allows to embed the time series in a metric space. In the second step, the time series pre-image estimation is cast as learning a linear (or a nonlinear) transformation to ensure a local isometry between the time series embedding space and the feature space.

Extensive experiments show the efficiency and the benefits of TsPrima through three major tasks that require pre-image estimation: 1) time series averaging, 2) time series reconstruction and denoising and 3) time series representation and dictionary learning.

Future work will explore the benefits of pre-image estimation methods in several deep learning contexts. Indeed, although deep learning approaches remain among the powerful machine learning methods today, the results obtained and the performance achieved remain generally inexplicable and uninterpretable, which is a major drawback in the context of diagnostic analysis. Therefore, future studies will focus on exploring new approaches based on prior image estimation to make deep learning results interpretable and explainable.

1. 1 2 2. 1

 121 Illustration of kernel methods . . . . . . . . . . . . . . . . . . . . . Illustration of kernel PCA . . . . . . . . . . . . . . . . . . . . . . . 12 3.1 Illustration of the pre-image problem . . . . . . . . . . . . . . . . . 28 3.2 The pre-image estimation by distance constraints . . . . . . . . . . 33 3.3 The pre-image estimation by isometry preserving . . . . . . . . . . 36

Figure 1 . 1 :

 11 Figure 1.1: Illustration of kernel methods

  Given an input sample x ∈ R d and a dictionary D ∈ R d×L : D = [d 1 , . . . , d L ] composed of L atoms d j ∈ R d , the objective of sparse coding problem is to represent sparsely x by a linear combination of a few atoms of D. This problem is formalised as minimising the error of reconstruction of x under a sparsity constraint:

  ) s.t. a i 0 ≤ τ ∀i = 1, ..., N, where the matrix B = [β 1 , ..., β L ] ∈ R N ×L gives the representation of the embedded atoms into the base Φ(X) and A = [a 1 , ..., a N ] ∈ R L×N gives the sparse representations of Φ(X), with the sparsity level τ imposed by the above constraint.

Figure 3 . 2 :d 2

 322 Figure 3.2: The pre-image estimation by distance constraints

Figure 4 . 1 :

 41 Figure 4.1:In the left, the temporal alignment between x i (t i = 5) and x j (t j = 6), the optimal alignment π * is indicated in red. In the right, the optimal alignment is illustrated as connections between two time series.

  the dynamic time warping is O(|x i | × |x j |), where |x i |, |x i | are respectively lengths of x i and x j . Constraints are widely used to speed up dynamic time warping programming. Two well-known global constraint region are the Sakoe-Chiba band [4] and Itakura parallelogram [6], shown in Figure 4.2. The region of optimal alignment is selected only from respective shaded region. The Sakoe-Chiba band runs symmetrically along the diagonal and has a width

Figure 4 . 2 :

 42 Figure 4.2: Illustration of the DTW constraints

  by using three selection criteria: a) have a reasonable number of classes (Nb. of Classes < 50), b) have a sufficient size for train and test samples (Train size <= 500 and Test size < 3000), c) avoid time series of extra large lengths (Time series length < 700).

Figure 5 . 1 :Figure 5 . 2 :

 5152 Figure 5.1: Time series of umd dataset with classes: up, middle, down

YFigure 5 . 3 :

 53 Figure 5.3: Time series of spiral1 dataset.

Figure 5 . 4 :

 54 Figure 5.4: Time series of spiral2 dataset.

Figure 5 . 5 :

 55 Figure 5.5: 6dmg Air-Handwriting dataset with classes: digits, upper, lower

  ), Φ(y) -2 Φ(y), Φ(x i ) + Φ(x i ), Φ(x i ) = arg min y N i=1

Figure 5 . 7 :

 57 Figure 5.7: Time series centroids for some challenging classes of digits, lower, upper and spiral1 datasets.

Figure 5 . 8 :Figure 5 . 9 :

 5859 Figure 5.8: Nemenyi test: comparison of pre-image methods under kernel PCA reconstruction

5. 5 Figure 5 . 10 :

 5510 Figure 5.10: Time series denoising under kernel PCA of noisy samples of spiral2 and of the class "M" of upper dataset.

Figure 5 . 11 :Figure 5 . 12 :

 511512 Figure 5.11: Nemenyi test: comparison of pre-image methods under kernel k-SVD representation learning

Figure 5 . 13 :

 513 Figure 5.13: The sparse representation of a time series of the class "k" of lower dataset and the top 3 involved atoms for its reconstruction

Figure 5 . 14 :

 514 Figure 5.14: Nemenyi Tests.

  3 that the centroids estimated by TsPrima lead to the highest within-class similarity on almost all the datasets, namely, each centroid obtained by TsPrima is in general the closest to the set of time series it represents. The analysis of the critical difference diagram given in Figure 5.6 indicates that the next best results are obtained respectively by Bakir, Honeine, and Kwok methods. In addition, as the state of the art methods are connected by a solid bold line, their performances remain equivalent. From Figure 5.7, we can see that while all the methods succeed to restitute the centroids of some input classes (shown on the left column) as the class "6" of digits and "S" of upper datasets, only TsPrima succeeds to estimate the centroids of the most challenging classes, as the "k" class of lower dataset and spiral1.

Honeine,

  Kwok and Bakir (Figure 5.14 (b), (c) and (d)), which assesses the crucial contribution of the learned transformations R of TsPrima. Lastly, of particular note is that Honeine and Bakir that involve the whole training samples induce much computations, specifically for the time series embedding process, than Kwok and TsPrima that require fewer samples into the neighbourhood of ϕ.

3 . 28 requires

 328 two inversions of XX T and K, which induces, respectively, a complexity of O(d 2 N ) + O(d 3 ) and O(N 3 ), that leads to an overall complexity of O(N 3 ).For Bakir method, Eq. 3.31, requires the inversion of the Gram matrix, which leads to a complexity of O(N 3 ). For TsPrima, Eq. 4.12 involves the inversion of XX T , where X is of dimension (d × n), d is the time series length and n is the neighbourhood size. The induced complexity is of O(d 2 n) + O(d 3 ). For the time series embedding part, the complexity is mainly related to the time warping function which is of order O(d 2 n). As d is in general higher than the neighbourhood size n, the overall complexity for TsPrima is about O(d 3 ). To sum up, as the neighbourhood size n << N and d << N (for not extra large time series), the complexity induced by both Kwok and TsPrima remains lower than the one of Honeine and Bakir. Note that, the Honeine method can be developed to consider only the neighbourhoods instead of all samples.

  from Eq. (2.35) and the orthogonal PCA systems obtained in Eq. (2.6), we have

Table 5 .

 5

			1: Data Description
	Dataset	Nb. class Train	Test	Time series Univariate
			size	size	length
	cc	6	300	300	60
	gunpoint	2	50	150	150
	cbf	3	30	900	128
	osuleaf	6	200	242	427
	swedishleaf	15	500	625	128
	trace	4	100	100	275
	facefour	4	24	88	350
	lighting2	2	60	61	637
	lighting7	7	70	73	319
	ecg200	2	100	100	96
	adiac	37	390	391	176
	fish	7	175	175	463
	beef	5	30	30	470
	coffee	2	28	28	286
	oliveoil	4	30	30	570
	diatomsizer	4	16	306	345
	ecg5days	2	23	861	136
	facesucr	14	200	2050	131
	italypowerd	2	67	1029	24
	medicalimages	10	381	760	99
	motestrain	2	20	1252	84
	sonyaiboii	2	27	953	65
	sonyaibo	2	20	601	70
	symbols	6	25	995	398
	twoleadecg	2	23	1139	82
	spiral1	1	50	50	101
	spiral2	1	50	50	300
	powercons	2	73	292	144
	bme	3	30	150	128
	umd	3	36	144	150
	digits	10	100	100	29∼218
	lower	26	130	260	27∼163
	upper	26	130	260	27∼412

Table 5 . 2 :

 52 The descriptions of parameters

	Methods	Parameters	Range of values	Description
	All	σ t	{0.2, 0.5, 1, 2, 5, 10} * med(DT W (x, y))	width of dtak
	All	T	[0, 100] lag of 10	Sakoe-Chiba band
	TsPrima, Bakir	σ	{0.2, 0.5, 1, 2, 5, 10}	width of Gaussian kernel
	Honeine TsPrima, Kwok	λ n	10 -9 [2, round( √ N )] lag of 2	regulary term number of neighbors

Table 5 . 3 :

 53 Average within-class inertia of the estimated time series centroids

	Dataset	TsPrima Honeine Kwok Bakir
	cc	0.744	0.709 0.721 0.709
	gunpoint	0.902	0.910 0.882 0.886
	cbf	0.798	0.737 0.755 0.737
	osuleaf	0.985	0.987 0.986 0.987
	swedishleaf	0.910	0.920 0.920 0.92
	trace	0.998	0.992 0.991 0.992
	facefour	0.981	0.980 0.981 0.98
	lighting2	0.918	0.876 0.859 0.875
	lighting7	0.964	0.930 0.930 0.931
	ecg200	0.593	0.565 0.567 0.566
	adiac	0.997	0.997 0.996 0.997
	fish	0.996	0.995 0.994 0.995
	beef	0.900	0.892 0.898 0.89
	coffee	0.998	0.998 0.998 0.998
	oliveoil	0.999	0.999 0.998 0.999
	diatomsizer	0.997	0.997 0.997 0.997
	ecg5days	0.777	0.746 0.417 0.746
	facesucr	0.721	0.699 0.648 0.700
	italypowerd	0.610	0.552 0.420 0.542
	medicalimages 0.671	0.644 0.637 0.646
	motestrain	0.776	0.777 0.701 0.777
	sonyaiboii	0.749	0.740 0.716 0.740
	sonyaibo	0.960	0.962 0.955 0.962
	symbols	0.959	0.949 0.904 0.951
	twoleadecg	0.980	0.977 0.911 0.977
	spiral1	0.831	0.823 0.799 0.824
	spiral2	0.947	0.940 0.934 0.940
	powercons	0.458	0.328 0.436 0.33
	bme	0.701	0.572 0.638 0.555
	umd	0.800	0.765 0.724 0.755
	digits	0.746	0.575 0.657 0.581
	lower	0.713	0.544 0.645 0.545
	upper	0.764	0.572	0.57 0.573
	Nb. Best	28	9	4	8
	Avg. Rank	1.50	2.68	3.24	2.58

Table 5 . 4 :

 54 Quality of the time series reconstruction under kernel PCA

	Dataset	TsPrima Honeine Kwok Bakir
	cc	0.798	0.747	0.758 0.747
	gunpoint	0.994	0.996 0.992 0.99
	cbf	0.916	0.854	0.896 0.875
	osuleaf	0.997	0.998 0.995 0.998
	swedishleaf	0.798	0.701	0.69	0.65
	trace	0.689	0.519	0.597 0.519
	facefour	0.981	0.951	0.967 0.964
	lighting2	0.993	0.967	0.984 0.975
	lighting7	0.954	0.92	0.938 0.922
	ecg200	0.965	0.979 0.959 0.962
	adiac	0.194	0.127	0.139 0.125
	fish	0.779	0.58	0.586 0.579
	beef	0.528	0.703	0.643 0.704
	coffee	0.584	0.595	0.57 0.559
	oliveoil	0.150	0.125	0.141 0.121
	diatomsizer	0.330	0.174	0.186 0.173
	ecg5days	0.996	0.996 0.995 0.995
	facesucr	0.939	0.825	0.878 0.847
	italypowerd	0.831	0.892 0.023 0.851
	medicalimages	0.946	0.906	0.935 0.928
	motestrain	0.971	0.987	0.97 0.979
	sonyaiboii	0.978	0.989 0.969 0.985
	sonyaibo	0.939	0.98	0.924 0.967
	symbols	0.885	0.822	0.724 0.761
	twoleadecg	0.825	0.63	0.444 0.669
	spiral1	0.961	0.939	0.933 0.911
	spiral2	0.966	0.939	0.946 0.94
	powercons	0.971	0.966	0.955 0.977
	bme	0.896	0.800	0.858 0.666
	umd	0.885	0.855 0.904 0.797
	digits	0.84	0.721	0.798 0.726
	lower	0.787	0.696	0.747 0.685
	upper	0.856	0.678	0.787 0.687
	Nb. Best	22	9	1	3
	Avg. Rank	1.56	2.67	2.71	3.06

Table 5 . 5 :

 55 Quality of the denoising for several noise levels

	Dataset	σ 2	TsPrima	Honeine	Kwok	Bakir
	digits	0.01	0.832	0.669	0.782	0.666
		0.05	0.808	0.619	0.742	0.627
		0.1	0.791	0.605	0.723	0.612
		0.15	0.783	0.598	0.719	0.606
	lower	0.01	0.766	0.651	0.721	0.637
		0.05	0.746	0.614	0.689	0.606
		0.1	0.736	0.601	0.675	0.596
		0.15	0.729	0.594	0.67	0.591
	upper	0.01	0.837	0.627	0.765	0.638
		0.05	0.806	0.579	0.712	0.6
		0.1	0.789	0.561	0.688	0.59
		0.15	0.782	0.554	0.679	0.586
	Nb. Best		12	0	0	0
	Avg. Rank		1.00	3.58	2.00	3.42

Table 5 . 6 :

 56 Quality of the time series representation learning under Kernel k-SVD

	Dataset	TsPrima Honeine Kwok Bakir
	cc	0.788	0.73	0.751 0.732
	gunpoint	0.993	0.994 0.992 0.985
	cbf	0.917	0.862	0.9	0.872
	osuleaf	0.996	0.996 0.995 0.996
	swedishleaf	0.789	0.659	0.691 0.623
	trace	0.687	0.514	0.602 0.514
	facefour	0.971	0.94	0.959 0.947
	lighting2	0.991	0.961	0.982 0.968
	lighting7	0.961	0.934	0.947 0.934
	ecg200	0.953	0.957	0.95 0.941
	adiac	0.184	0.122	0.131 0.117
	fish	0.757	0.553	0.579 0.56
	beef	0.411	0.555	0.605 0.621
	coffee	0.596	0.607 0.586 0.56
	oliveoil	0.145	0.133 0.152 0.12
	diatomsizer	0.287	0.177	0.198 0.178
	ecg5days	0.996	0.996 0.995 0.994
	facesurc	0.917	0.834	0.878 0.842
	italypowerd	0.8	0.781	0.034 0.728
	medicalimages	0.937	0.86	0.93 0.878
	motestrain	0.969	0.97	0.971 0.97
	sonyaiboii	0.974	0.975 0.973 0.975
	sonyaibo	0.932	0.938	0.93 0.936
	symbols	0.811	0.785	0.794 0.755
	twoleadecg	0.81	0.617	0.411 0.629
	spiral1	0.944	0.913	0.92 0.914
	spiral2	0.964	0.936	0.949 0.937
	powercons	0.968	0.946	0.957 0.951
	bme	0.872	0.734	0.843 0.622
	umd	0.888	0.842 0.905 0.788
	digits	0.822	0.699	0.793 0.706
	lower	0.773	0.678	0.738 0.671
	upper	0.840	0.664	0.797 0.675
	Nb.Best	24	7	3	3
	Avg.Rank	1.50	3.02	2.33	3.15

Table 5 . 7 :

 57 Further comparisons for pre-image estimation

					TsPrima Honeine Kwok Bakir
	Averaging		Nb. Best	19	20	4	19
				Avg. Rank	2.23	2.21	3.35 2.21
	Reconstruction Nb. Best	24	10	0	1
	(kernel PCA)		Avg. Rank	1.56	2.35	3.05 3.05
	Denoising		Nb. Best	12	0	0	0
	(kernel PCA)		Avg. Rank	1.50	3.25	2.62 3.12
	Rep. Learning Nb. Best	25	8	1	2
	(kernel kSVD) Avg. Rank	1.44	2.67	2.58 3.32
	CD
	4	3	2	1
				2.2121 Honeine

Acknowledgements

First of all, I would like to express my gratitude to my supervisor, Prof. Ahlame Douzal, for her support, patience. She has spent a lot of her time and her energy to guide and teach me. It is great luck to be her Ph.D. student. I am thankful to my co-supervisor, Prof. Paul Honeine, for following each stage of my Ph.D. I also thank my co-supervisor, Dr. Saeed Varasteh Yazdi, to accompany and help me during my Ph.D. I would like to thank all members my jury for their interest in my work. I also thank Prof. Mohamed Nadif and Prof. Christophe Marsala for reviewing my thesis and providing helpful comments and suggestions. I thank Prof. Patrick Gallinari and Dr. Sihem Amer-Yahia for participating in my Ph.D. defense committee. I thank them all for their valuable time and useful feedback. I thank the AMA team for giving me the professional and intimate environment to work. I also thank my colleagues for encouraging me to overcome the difficulties of my Ph.D.

compare the significance of the obtained results, with the related critical difference diagram given in Figure 5.6. The estimated time series centroids for some challenging classes are shown in Figure 5.7, where we retain particularly spiral1 and the handwritten digits and characters datasets (digits, lower and upper) as they are more intuitive to visually evaluate the quality of the estimated time series centroids. The reconstruction and denoising tasks represent a standard application context for pre-image estimation. For time series reconstruction task, a kernel PCA is performed on the training set, the reconstruction of a given test sample x is then defined as the pre-image x * of its kernel PCA projection P (Φ(x)). The latter takes the form ϕ = Φ(X)γ, with γ defined as:

The quality of the reconstruction is then measured as the similarity dtak(x * , x)

between each test sample x and its reconstruction x * ; the higher the criterion, the better is the reconstruction. Table 5.4 gives the average quality of reconstruction obtained for each dataset and each method. of the studied methods. Figure 5.9 shows the reconstructions obtained for some challenging time series of digits, lower and upper datasets.