Data sample

Learned metric

Learned predictor

Consistency guarantees for the metric Generalization guarantees for the predictor using the metric

.1: The supervised machine learning workflow. The question of the generalization capacity can be asked at two levels: the metric and the predictor using it.

a label associated to each instance. The algorithm must learn to predict these labels for unseen examples. When the label comes from a discrete set of values (e.g. the gender of a person), the task is called classification. Conversely, when labels are continuous (e.g. prices), the task to be performed is regression. We will mainly focus on supervised tasks in this document. Unsupervised learning covers the case where no label information is available for the data. In this context, the algorithm is asked to perform a task for which label information is not necessary. For example, clustering tries to find an inherent pattern in the data which allows to divide examples into groups named clusters. Semi-supervised learning covers similar tasks to the supervised setting, but is able to additionally integrate unlabeled samples.

The performance of a learning algorithm is strongly related to the quantity and quality of data available. As in the case of all algorithms, performance measures for learning methods include time and space complexity. While computational efficiency is a significant concern in machine learning, more specific measures allow evaluating algorithms from a learning perspective. The most important of these is the quality of the prediction. An additional particular measure is sample complexity, which indicates the quantity of data required by an algorithm to learn to solve a certain task. More precisely, theoretical guarantees can be provided for the performance of a learning algorithm with respect to the quantity of data available and a notion of complexity of the chosen model. These types of guarantees can be derived using methods from statistical learning theory.

Most machine learning algorithms are brought to compare data instances, either for constructing the model or making predictions. Comparisons are performed using a notion of metric that gives a measure of resemblance between examples. This is true for supervised methods, like k-nearest neighbors or support vector machines, as well as for unsupervised ones, such as K-means. However, choosing an adapted metric can prove to be a difficult task, and the performance of the algorithm strongly depends on it. One hopes that the measure discriminates well the data for the given task (e.g. for classification, recognizing instances of the same label as similar). Moreover, standard metrics, such as the Euclidean distance, do not have the capacity to adapt to a task or to incorporate semantic constraints, thus sometimes missing the relevant information.

C Translation into French

Bibliography

Chapter 1

Introduction

The purpose of machine learning is to design accurate prediction algorithms based on available training data. This data can be seen as experience from which one can learn by example: the previous instances have to be taken into account when making decisions. The process is different from memory-based systems which only recognize past instances. In learning, the purpose is to determine the model associated with the data and be able to apply it on unseen instances. In most cases, once the modeling step is performed, the initial data can be discarded, and the model can predict outcomes for new data arriving in the system. In contrast to memory-based systems, this implies that machine learning has generalization capacities.

Learning algorithms are successfully used in a variety of applications, including:

• Computer vision (e.g. image segmentation, face detection, object recognition);

• Signal processing (e.g. speech recognition and synthesis, voice identification);

• Information retrieval (e.g. search engines, recommender systems);

• Unassisted vehicles (e.g. robots, drones, self-driven cars);

• Computational linguistics;

• Computational biology and genetics;

• Medical diagnosis.
This list is not a comprehensive one, and new applications for learning algorithms are designed every day.

Data can be made available to the algorithm in different forms. Feature vectors are often used to contain categorical or numerical information, like the location of a house, its price, its surface and so on. Structured data is used to represent information that cannot be directly stored in the previous form, such as strings (e.g. text documents), trees (e.g. XML content) or graphs (e.g. social networks). Another type of structured data present in numerous applications are time series, which follow the evolution of a process across time (e.g. stock values, patient vital signs or weather information). When presented with any of the previous types of data (or a mix of them), the algorithm can be asked to perform a certain number of learning tasks. In supervised learning, the data comes with Metric learning aims at solving exactly this problem by automatically learning custom metrics from data. This step is performed prior to applying another machine learning algorithm using the learned metric to solve a specific task. Learning metrics for the purpose of classification is the main subject that we address in this thesis. Metric learning can be seen as part of a larger topic termed representation learning: under the new metric, the representation used for the data changes. Representation learning also includes fields such as feature learning, deep learning, kernel learning and many others. Metric learning has received a lot of attention over the past fifteen years, especially for the supervised setting. Most methods learn the parameters of a Mahalanobis distance under constraints induced by the data, which is equivalent to changing the representation of the instances under a linear transformation. In the supervised case, the learned metric has the objective to represent the instances with the same or close (respectively different) labels as similar (respectively dissimilar). State of the art methods for feature vectors are more scalable and efficient in computation than previous approaches. On the other hand, metric learning for time series applications has received scarce attention, most likely because of the more complex structure of the data. Time series coming from real applications usually have different lengths, sampling rates and phases. For this reason, in order to compare two time series, one must first align them. Roughly speaking, this implies finding all the correspondences between time moments. Dynamic time warping (DTW) is the most well-known method for providing the optimal alignment, which is based on a cost matrix. Metric learning for time series usually aims at optimizing this cost under constraints deducted from the examples.

The current advancement of the metric learning field suffers from a few non-negligible limitations. The most important is probably the lack of theoretical analyses for most existing methods. To be more precise, one would want to evaluate the generalization capacity associated to learning a metric. For the particular case of metric learning, this notion can be declined under two aspects (see Figure 1.1). First, the metric should be consistent with the data, that is it should be able to generalize well outside the training data, on unseen examples from the same distribution. This type of guarantee has only been provided for a small number of methods. Second, the learned metric should be related to the algorithm that is using it, improving its performance with respect to standard metrics. For example, learning a metric from local constraints for a local classification rule might not perform well when used with a global linear classifier. This second type of guarantee is also rare in the field, and, even though some methods improve a criterion related to the classifier, this link is not formally established. In practice, the learned metric is plugged in the classifier in hope of making if better. The theory of ( , γ, τ )-good similarity functions has been one of the first results trying to relate the properties of a similarity function to the performance that can be expected of it in classification. We describe this framework in detail later in the thesis, as our contributions make use of it. A second limitation in metric learning comes from the fact that most methods work with metrics that enforce distance properties. Satisfying this type of constraints can be expensive even when using modern numerical optimization techniques, which increases the overhead of performing a metric learning step. This limitation joint with the lack of guarantees for performance amelioration implies that the effort spent in metric learning might actually result in an inadequate metric.

In this thesis, we aim to address the previously mentioned limitations. All our contributions are based on learning similarity functions, a different family of metrics which are less constraint than distances and constitute a promising, but less explored avenue for research. We also derive generalization guarantees for the learned metric and the associated classifier for all the methods we propose. First, we introduce a general framework for performing similarity and linear classifier learning simultaneously. This setting is designed for feature vectors and works for a wide range of similarity functions. Moreover, the approach is semi-supervised, which allows it to leverage unlabeled examples in order to improve performance. Our following contribution allows us to tackle the problem of metric learning for multivariate time series. We propose to learn a bilinear similarity function to be used for linear classification. The similarity uses the optimal alignments and allows to better reweigh the features.

Context of this work

The work for this thesis was performed in machine learning teams from two establishments: the Data Intelligence group of Laboratoire Hubert Curien UMR CNRS 5516, part of University of Saint-Étienne and University of Lyon, and the Data Analysis, Modeling and Machine Learning (AMA) group of Laboratoire Informatique de Grenoble, part of Grenoble Alps University. Funding for this project was provided by a grant from Région Rhône-Alpes.

Outline of the thesis This dissertation is organized as follows.

• Chapter 2 introduces the notions related to statistical machine learning that are necessary for the rest of this document. We begin with a formal presentation of supervised learning, then give some examples of classic learning algorithms, followed by the learning theory frameworks for deriving generalization guarantees.

• Chapter 3 is dedicated to metrics in general, and metric learning in particular. After presenting a number of standard metrics for feature vectors and time series, we provide a comprehensive survey of (semi-)supervised metric learning for these types of data. This chapter explains in more detail the limitations that have determined the direction of our contributions.

• Chapter 4 presents our contributions on metric learning for feature vectors. We introduce a general framework called JSL (Joint Similarity Learning) for learning a similarity function and a global linear classifier simultaneously. JSL is capable of integrating unlabeled information in the form of landmarks based on which global constraints are generated. This property allows our framework to adapt to the particular setting in which only a small amount of labeled data is available. The formulation optimizes the ( , γ, τ )-goodness of the similarity, which ensures its performance in classification. JSL is convex and can be solved efficiently under mild constraints over the choice of the similarity function. We derive theoretical guarantees for JSL using two different frameworks: the algorithmic robustness and the uniform convergence using Rademacher complexity. The experiments compare JSL to a large range of state of the art methods and prove its efficiency.

• Chapter 5 gathers our contributions on metric learning for temporal data by introducing SLTS (Similarity Learning for Time Series). We propose to learn a bilinear similarity function for multivariate time series based on the optimal alignment. The learned similarity is to be used in a classification task to determine a linear separator. The problem we solve is convex and easy to solve. Making use of the uniform stability framework, we provide the first theoretical guarantees in the form of a consistency bound for the learned similarity. Moreover, improving the ( , γ, τ )-goodness of the metric provides additional guarantees concerning its performance for linear classification. The experimental study shows that the proposed approach is efficient, while yielding sparse classifiers.

• Chapter 6 concludes our work and discusses avenues for possible future work.

Notation Table 1.1 explains the notations used throughout this thesis. A set of n elements from S X Input space Y Output space z = (x, y) ∈ X × Y A labeled instance x

An arbitrary vector x i

The i th component of x M

An arbitrary matrix I

The identity matrix M i,j

Entry at row i and column j of matrix Probability of an event

E[•]

The expectation of a random variable Table 1.1: Summary of notation.

Introduction

The practical objective of machine learning is to make correct predictions for items that were not seen before in an efficient and robust way. This is done based on a model inferred from available data instances.

A classic setting for this type of problem is supervised learning [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF]. Its particularity is that the available data for determining the model is labeled, i.e. the items are annotated with target values similar to those which the algorithm should predict.

When the annotation comes from a set of discrete categories, and the purpose is to assign a category to each new item, the problem is called classification. In contrast, if the output is a continuous, usually real-valued variable, the learning task is called regression.

A different setting is unsupervised learning, where the training data is a set of items with no target annotation. Here, the goal can be to discover a pattern that allows to aggregate the data in similar groups in the case of clustering [START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF], to determine the distribution of the data for density estimation [START_REF] Bernaard | Density Estimation for Statistics and Data Analysis[END_REF], or to perform data visualization in two or three dimensions by projecting it to such a low dimensional space [START_REF] Frits | Data Visualization: The State of the Art[END_REF].

Semi-supervised learning [START_REF] Chapelle | Semi-Supervised Learning[END_REF] covers the same tasks as the supervised setting when only part of the training data is annotated. The purpose is to extract additional information (typically, about their underlying statistical distribution) from the unlabeled data in order to perform better than based only on the labeled sample. This is usually done in a transductive setting, by label propagating onto close unlabeled examples [START_REF] Vladimir | Statistical Learning Theory[END_REF], or by integrating the structure of unlabeled neighborhoods through graph nodes adjacency information [START_REF] Zhu | Semi-Supervised Learning with Graphs[END_REF].

Other learning paradigms that are not in the scope of this document include transfer learning [START_REF] Sinno | A Survey on Transfer Learning[END_REF], which aims at better solving one learning problem by using information from another related problem, and reinforcement learning [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF], where the algorithm takes sequential actions to maximize a notion of reward, without being presented with an explicit access to correct results.

This dissertation focuses on (semi-)supervised learning, more precisely classification, which we introduce formally in the following section.

Supervised Learning

In a supervised setting, the learning algorithm has access to a labeled training set coming from a fixed but unknown distribution, used to create a model with prediction capacities. Let us define these notions formally.

Domain set

An arbitrary set X . Usually, domain points are vectors of features coming from X ⊆ R d and are referred to as instances. The features or the characteristics of the data have to be informative to guide the learning algorithm effectively. The choice of features is left to the user and reflects his prior knowledge about the task, but a lot of research effort has been put into making this selection automatically [START_REF] Guyon | An Introduction to Variable and Feature Selection[END_REF].

Label set Also known as annotations or target values, these are the feedback provided to the learning algorithm. In the classification setting, Y represents the set of all possible labels. For the purpose of this discussion, and without loss of generality, we will focus on binary labels, usually {-1, 1}.

Training data A training sample S is a set {z i = (x i , y i )} n i=1 of size n independent instances, identically distributed (i.i.d.) according to an unknown distribution P over the space of instances and labels Z = X × Y. Such labeled examples are often called training set and are the data based on which the algorithm learns.

Output We assume there exists a correct labeling function f : X → Y for which f (x) = y for all (x, y) drawn from P . The labeling function is unknown to the algorithm. Following the learning process, the algorithm provides a function h : X → Y coming from a hypothesis space H that best predicts the behavior of f . For instance, H can be the family of all linear separators (lines) in a plane. Note that Y can be different from the label space Y. h is also called a predictor, a hypothesis (or a classifier in classification), and is used to predict the labels of new instances arriving. We will denote by h S the model obtained from sample S. In many types of algorithms, the training data is not necessary anymore once the model is built, and prediction is done only based on the model h.

Throughout this dissertation, we will consider two types of data: feature vectors coming from X ⊆ R d and time series defined as follows.

Definition 2.1 (Time series). A time series is a sequence of values of a quantity obtained at successive times. The term univariate time series refers to a time series that consists of single (scalar) observations recorded sequentially over time increments, i.e. X ⊆ R. A multivariate time series is a time series that records multiple values at each time increment, i.e. where each time moment is a vector of features, and X ⊆ R d .

More formally, we can define supervised learning in the following way.

Definition 2.2 (Supervised learning). Supervised learning is the task of finding a modeling function h : X → Y coming from a hypothesis class H that best predicts the value of y given x for any (x, y) drawn from P .

As stated before, for a model to be of good quality, its predictions should match the true labels of the data. When choosing the best hypothesis to fit the data, its adequacy is measured through the use of a loss function : H × Z → R + . Loss functions are nonnegative and usually take value zero (or close to zero) when the prediction is correct and higher values otherwise. We define the true risk as the measure over P of the quality of a hypothesis h under .

Definition 2.3 (True risk). Given a hypothesis h ∈ H, the true risk R P of h with respect to a loss function is the expected loss suffered by h on the distribution P : R P (h) = E z∼P [ (h, z)].

The true risk is also known under the names of generalization error, risk or true error, which we use interchangeably throughout this document. Intuitively, it measures the capacity of h to make correct predictions for all instances (x, y) ∈ P . The goal of supervised learning is to find the hypothesis h that obtains the lowest true risk. However, since the risk is an expected true value and depends on the unknown distribution P , it cannot be computed directly. The learner should thus minimize a substitute value instead. This is usually the empirical value of the risk on the available sample S, also known as the empirical risk.

Definition 2.4 (Empirical risk). Given a hypothesis h ∈ H and a sample S = {z i } n i=1 of size n, the empirical risk (or empirical error) R S (h) with respect to a loss function is the average loss incurred by the algorithm on the instances of S:

R S (h) = 1 n n i=1
(h, z i ).

When using the previous notations, we omit the loss function when it is clear from the context.

The predictor h can take different forms, depending on the family of hypotheses learned: it can be a vector (usually from R p ), a matrix (from R p×p ), the parameters of a neural network, etc. For binary classification, h generally outputs a scalar in R. In this case, the most intuitive loss function is the zero-one loss, which tells for each instance if it has been labeled correctly:

0/1 (h, z) = 1 if yh(x) < 0, 0 otherwise.

The product yh(x), which represents the margin, determines if y and h(x) agree in sign; the error is thus 1 when this is not the case, computing the overall proportion of incorrect predictions. Even though this loss function is arguably the most adequate for binary classification, its mathematical properties make it hard to optimize, as we will see later.

In the next section we describe the most well known learning frameworks that use the current setting to provide a good model.

Learning Good Hypotheses

In this section, we give an intuition about what makes a good hypothesis and the most well known methods to learn one.

According to the law of large numbers, the empirical risk asymptotically converges to the true risk when the size of the sample is infinite. In practice, the quantity of data is always limited and sometimes rather small. Moreover, choosing a hypothesis class complex enough (e.g. a high degree polynomial) will allow to perfectly fit the training sample and artificially minimize the empirical error without also reducing the true risk. The result is a predictor with low generalization capacity. The phenomenon of conserving an elevated true risk in spite of a low sample error is called overfitting and is the result of a too complex hypothesis h or insufficient data available lying in high dimensional space (curse of dimensionality).

In this case, the model is too sensitive to small fluctuations in the training set, adapting to random noise. This behavior is also called high variance, in reference to the variance of the obtained estimator.

In contrast to overfitting, underfitting occurs when the algorithm is unable to learn the relevant relations between data and output. This behavior is usually induced by erroneous assumptions in the algorithm, i.e. the hypothesis class is not complex enough to justify the data. For example, a linear classifier will not be able to separate instances that are not linearly separable w.r.t. to P . This phenomenon is also called high bias, referring to the fact that the hypothesis is biased towards the assumptions that were made about the problem, instead of adapting to the sample.

Both elevated variance and bias can prevent a learning algorithm from generalizing well.

The bias-variance trade-off is the problem of finding the best compromise between these two sources of error: choosing a hypothesis that is just as complex as needed to model the data. Usually, the higher the variance, the smaller the bias, and vice-versa.

We now proceed to presenting the classic strategies for obtaining good hypotheses: mini-mizing the risk via the empirical error.

Empirical Risk Minimization Since the training sample is the only information available to the algorithm, minimizing the empirical risk on this data seems like a natural way to obtain a good hypothesis. This strategy is called empirical risk minimization (ERM) and is formulated as follows:

h S = arg min h∈H R S (h).
In this setting, h is chosen from a restricted class of functions H set in advance. Handpicking H can be a difficult task when no prior knowledge about the data is available. Although ERM can perform well in some cases, recall that the empirical error is often a too optimistic estimate for true error. There is always a hypothesis h complex enough to reproduce exactly the labels of the training set, making this framework suffer from overfitting.

In order to avoid overfitting, one should use the most simple hypothesis that explains the data, which is supported by Occam's razor principle. Two main approaches can be envisaged: limiting the class of functions H (through structural risk minimization) or favoring simple hypotheses over more complex ones (through regularized risk minimization). We present both these approaches in the following.

Structural Risk Minimization

In the case of structural risk minimization (SRM), an infinite number of hypothesis classes H 1 ⊂ H 2 ⊂ . . . of increasing sizes and complexities is considered. The hypothesis is chosen to fit the data while staying as simple as possible. This is done using a penalty on the complexity of the hypotheses class:

h S = arg min h∈Hn,n∈N R S (h) + penalty(H n ).
The penalty is proportional to a measure of complexity of H n (e.g. the Vapnik-Chervonenkis dimension [START_REF] Vapnik | On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities[END_REF]). This framework can be difficult to implement, as these measures can be sometimes hard to estimate, even for simple classes of hypotheses.

Regularized Risk Minimization Like SRM, Regularized Risk Minimization (RRM) builds upon limited spaces of hypotheses. Here, we choose one large hypothesis space that will be restricted through a penalty function, also known as a regularizer. The regularizer usually takes the form of a norm on h ( h ). The purpose is to reach a trade-off between best fitting the training data by minimizing the empirical risk, and controlling the complexity of the hypothesis:

h S = arg min h∈H R S (h) + λ h .
Choosing a type of regularizer for RRM is a delicate task, as each norm type enforces different characteristics on the model. Moreover, some choices make the problem easier to solve than others due to their good mathematical properties, e.g. convexity and/or smoothness. Table 2.1 presents the most common regularizers used in classification and their characteristics. The choice of the regularizer depends on the properties of the problem. The L 2 norm is easy to optimize and provides control over the values of a vector; the same

L 0 norm x 0 = 1 x i =0 + Sparsity M 0 = 1 M ij =0
-Non-convex, non-smooth

L 1 norm x 1 = |x i | + Convex, sparsity M 1 = |M ij | -Non-smooth (Squared) L 2 norm x 2 2 = x 2 i + Strongly convex, smooth (Squared) Frobenius norm M F = M 2 ij + Strongly convex, smooth L 2,1 norm M 2,1 = n j=1 M •,j 2 + Convex, group sparsity -Non-smooth Nuclear (trace) norm M * = singular values + Convex, low rank -Non-smooth
is true for its matrix counterpart, the Frobenius norm. However, when the data contains a large number of features and potentially not large enough number of examples, one would consider building a model relying only on a small number of features. The sparsity inducing norms, e.g. the L 1 and L 2,1 norms, can be used to achieve this purpose. As stated before, using regularization limits the complexity of the model to avoid overfitting and obtain better generalization. We will show in Section 2.7 how controlling the model through regularization can also help obtain theoretical guarantees on how well the model will generalize to unseen data.

Loss Functions

All the strategies presented earlier for finding a good model are based, at least in part, on minimizing the empirical error under a certain loss function . Although the zero-one loss 0/1 seems to be the most adapted for classification, this function is non-convex, non-smooth, and optimizing it directly is known to be NP-hard [START_REF] Ben-David | On the Difficulty of Approximately Maximizing Agreements[END_REF].

In practice, we replace it with a surrogate loss that approximates the real loss and has better computational properties. We remind the reader that a loss function is defined as : H × Z → R + . We now present the most frequently used margin-based surrogates for binary classification.

• The hinge loss is defined as:

hinge (h, z) = [1 -yh(x)] + = max(0, 1 -yh(x)).
It provides a relatively tight and convex upper bound for the zero-one loss, but it is not smooth (i.e. not differentiable) for the margin to be satisfied, that is yh(x) = 1. The hinge loss is closely related to support vector machines (SVMs) (Cortes & Vapnik, 1995a).

• The logistic loss log (h, z) = ln(1 + e -yh(x) ).

This function has a similar convergence rate as the hinge loss, being also smooth. Its main disadvantage is that its value is never zero, even for correctly classified points, which only incur a small penalty. This property makes logistic loss sensitive to outliers. The logistic loss is often associated with logistic regression [START_REF] Knoke | Log-Linear Models[END_REF].

• The exponential loss, defined as: x) , has similar properties to the logistic loss, but its values are closer to zero for correct predictions. The exponential loss is mostly known by being used in boosting [START_REF] Freund | A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting[END_REF].

exp (h, z) = e -yh(
Figure 2.1 depicts these surrogate loss functions, along with the zero-one loss. Note that all these surrogates give a loss penalty of 1 for yh(x) = 0.

Standard Classification Algorithms

In this section, we present two classic methods for supervised learning. Support vector machines (Section 2.5.1) represent one of the most largely used types of classifiers. The contributions we present in the following chapters are strongly related to this method, as we will see. The k-NN algorithm presented in Section 2.5.2 is one of the simplest, yet effective classification rules. It is also one of the methods that has been most explored in

x 1 x 2 w w x - b = 0 w x - b = 1 w x - b = - 1 b 2 | | w | | Figure 2
.2: Maximum-margin hyperplane and margins for a binary SVM. Support vectors are marked with a black outline. relation to learning metrics, as we will detail in the review of the state of the art methods for metric learning (Chapter 3).

Support Vector Machines

Support vector machines (SVM) [START_REF] Vapnik | A Note on One Class of Perceptrons[END_REF] are supervised methods adapted to classification and regression. We present here their formulation for binary classification. The algorithm computes the best separating hyperplane between the classes, i.e. the one that maximizes their separation. In their initial version, SVMs were only adapted for finding a linear separator, but this setting was extended to nonlinear decision functions using the so-called kernel trick [START_REF] Boser | A Training Algorithm for Optimal Margin Classifiers[END_REF] and projecting data in high-dimensional or even infinite spaces. For these two settings, the classes need to be linearly separable respectively in the input space and in the feature (projection) space. An important advantage of SVMs is that the equation of the separator only depends on the training points placed exactly on the required margin, also known as support vectors (Figure 2.2). The notion of margin of a separator with respect to a training set is defined to be the minimal distance between a point in the training set and the separator. Intuitively, between two predictors with the same error but different margins, the one with the larger margin is to be preferred, because it has a higher probability of still separating the training set under slight perturbations of the instances. SVMs aim at finding the maximum margin separator. Large margins on the training set translate into better upper bounds on the true risk. This constraint is relaxed in the soft margin SVM (Cortes & Vapnik, 1995b), which is able to compute a large margin separator while allowing for a small proportion of examples to violate the margin. When the classes are separable, choosing a very small margin in the soft margin SVM yields the previous hard margin formulation. Computing the classifier amounts to solving the following problem:

min w,b 1 n n i=1 [1 -y i (wx i + b)] + + λ w 2 2 .
The previous formulation learns a linear separator, but, as stated before, SVMs can be used to learn nonlinear classifiers. For this, we suppose that a kernel function K that measures similarity between points is given. We now give the definition of a kernel function.

Definition 2.5 (Mercer kernel). A pairwise similarity function K : X × X → R is a Mercer kernel if it is symmetric and positive semi-definite (PSD), i.e.

n i=1 n j=1 c i c j K(x i , x j ) ≥ 0
for all finite sequences x 1 , . . . , x n ∈ X and c 1 , . . . , c n ∈ R.

These properties of kernel functions are the basis for the kernel trick and dealing with classes that are not linearly separable. Positive semi-definiteness implies the existence of a Hilbert space H to which the data can be projected in order to obtain linear separation. The projection is done through a nonlinear function, which can be unknown or implicit.

Theorem 2.6 (Mercer theorem [START_REF] Mercer | Functions of Positive and Negative Type, and Their Connection with the Theory of Integral Equations[END_REF]). A kernel K : X × X → R is symmetric and positive semi-definite if and only if there exists a projection function φ from the instance space X to a Hilbert space H such that K(•, •) can be written as a proper inner product:

K(x, x ) = φ(x), φ(x ) , ∀x, x .
We provide some examples of kernels when discussing metrics for feature vectors (see Section 3.2.1). Given a kernel K, the equation of the separating hyperplane of an SVM is:

w = n i=1 c i y i φ(x i ).
The advantage of the kernel trick is that the mapping function φ can be unknown and is not necessary for solving the problem. Computing the classifier can be done by learning the values of the coefficients c i based on the kernel K:

max c i ,i∈{1,...,n} n i=1 c i - 1 2 n i=1 n j=1 y i y j c i c j K(x i , x j ) subject to n i=1 c i y i = 0 0 ≤ c i ≤ 1 2nλ
, ∀i ∈ {1, . . . , n}.

Finally, new points x can be classified to the positive (+1) or negative (-1) class using the

y = sgn n i=1 c i y i K(x i , x) + b .

Nearest Neighbor Classifier

The k nearest neighbors (k-NN) algorithm [START_REF] Thomas | Nearest Neighbor Pattern Classification[END_REF] is one of the most used classifiers, due to its simple classification rule. In contrast to SVM, the model is only approximated locally, without computing its overall explicit form. k-NN does not make any assumptions about the underlying distribution of the data, thus being non parametric. This is a lazy algorithm, as the training phase only stores the data, computation being deferred until the prediction phase. Upon the arrival of a new, unlabeled sample, its label is predicted as the most frequent class among the k training samples nearest to the point w.r.t. some distance function (see Algorithm 2.1 and Figure 2.3).

As k-NN uses a rule of majority voting, an important issue is breaking ties among the voters when two or more classes are majoritary. In a binary setting, choosing an odd value for k is enough to ensure that ties are not possible. In multiclass setting, a trivial heuristic is to break ties equally by randomly choosing one of the majority classes. Another solution is Distance Weighted k-NN [START_REF] Sahibsingh | The Distance-Weighted k-Nearest-Neighbor Rule[END_REF], which weighs the neighbors' votes proportionally to the inverse of their distance to the example.

Theoretically speaking, the higher k, the better the results of k-NN. However, this only holds when the number of examples n is infinite. In finite situations, the best choice for the size of the neighborhood k depends on the data. In general, larger values reduce the effect of noise but also smooth the decision boundary, making it harder to classify borderline examples. [START_REF] Hart | The Condensed Nearest Neighbor Rule[END_REF]) and reduced nearest neighbor (RNN) [START_REF] Gates | The Reduced Nearest Neighbor Rule[END_REF].

From a theoretical point of view, the classic k-NN algorithm has the property of its risk converging to the Bayes error when the number of examples n grows, for all values of k:

R Bayes P = E (x,y)∼P 1 -max y∈X Pr(y|x) Pr(x).
In the binary case, when the number of classes is limited to two, the following inequality holds:

R Bayes P ≤ R k-NN P ≤ 2R Bayes P .
The performance of the algorithm is sensitive to the metric through which the neighbors are computed. For feature vectors, the most common choice of metric is the Euclidean distance. A good strategy for improving k-NN performance is to learn a custom distance function from the data through metric learning. As we will see in Chapter 3, an important number of methods from this field has been dedicated to learning distances that minimize some form of empirical risk for k-NN classification.

Algorithms Evaluation

The performance of supervised machine learning algorithms can be compared through multiple measures. We provide here a discussion over these measures, data partitioning and parameter selection techniques for classification.

We start by illustrating all possible outcomes of the prediction for binary classification with respect to the actual target values in Table 2.2. The terms positive and negative refer to the classifier's prediction, while the terms true and false refer to whether that prediction corresponds to the instance label. The scores that are often computed from such a matrix are the following.

• Precision is referred to as positive predictive value: precision = tn tn + fp .

• Recall is referred to as the true positive rate or sensitivity: recall = tp tp + fn .

• The F-score (or F 1 score) is a measure that combines precision and recall as a harmonic mean:

F-score = 2 precision • recall precision + recall .
• Accuracy is a statistical measure of how well a binary classification model correctly identifies or excludes a condition. That is, the accuracy is the proportion of true results, both positives and negatives, among the total number of cases examined: accuracy = tp + tn tp + tn + fp + fn .

• Conversely, we can compute the error rate as:

error = 1 -accuracy .
Computing the error rate is the same as evaluating the zero-one loss over the whole sample. Throughout this dissertation, we will mostly rely on the accuracy and error rates for classification algorithms.

As we are interested in the performance of a model on unseen data, evaluating the predictive quality of a model should not be done on the same sample that has been used for learning. An additional reason is that the error on the training set is usually a too optimistic estimator of the model performance on unseen data.

To simulate new data from a finite sample, but still have access to the correct output, a common strategy is to take all available labeled data and randomly split it into training and test subsets. The training sample is then used by the algorithm to learn the model, while the test sample serves for evaluating the model and is unaccessible during training.

Other than the parameters learned by a model, the vast majority of methods depend on additional values (hyperparameters) that cannot be learned from the training set. They often leverage a trade-off, such as regularization parameters. These hyperparameters need to be tuned, and an additional independent sample is necessary to choose the best value. This validation sample is also set aside from the labeled sample, more specifically from the training set, as hyperparameter tuning is part of the learning process.

The traditional way for hyperparameter optimization is grid search, which exhaustively evaluates all possible combinations of parameters. For each setting, the model is estimated on a training set, then evaluated on the validation data. The values that performed the best are retained, and the model is trained once more, this time on the training set augmented with the validation set. The final model performance is computed on the test set.

Since the parameter space is often continuous, the value ranges and discretization steps have to be set manually for each parameter. When the number of hyperparameters and values to be explored is large, the size of the state space increases exponentially, making exhaustive grid search prohibitively expensive. Several alternatives to exhaustive search have been proposed. In particular, randomly sampling parameters a fixed number of times is an effective alternative in high-dimensional spaces [START_REF] Bergstra | Random Search for Hyper-Parameter Optimization[END_REF]. Both full and randomized grid searches are completely parallelizable.

By setting aside data for validation and testing, the size of the training set is diminished. Generally, the larger the training data the better the classifier, but also the larger the test data the more accurate the error estimate. In order to better exploit the data, crossvalidation allows to perform multiple rounds of evaluation on different splits of the data. Multiple heuristics for these splits exist:

• Multiple random splits (subsampling or repeated holdout method).

• K-fold cross-validation: the original sample is randomly partitioned into K mutually exclusive subsets (the "folds") of approximately equal size. Two folds are retained respectively for validation and testing, while the other K -2 folds are used for training.

• Leave-one-out cross-validation: on each run, one point is excluded from the training sample; it is instead used for testing. The learning process is performed once for each sample.

The price to pay for the previous heuristics comes as an increased time complexity.

Generalization Guarantees

In the previous sections, we have presented general frameworks for minimizing different versions of the empirical risk over a given sample. However, the objective of learning is to obtain a model with good generalization properties for unseen data. Generalization bounds allow to explicitly relate true risk to the empirical error of a hypothesis and to measure to which extent the empirical risk deviates from the true value over a sample. When the difference between the two measures is small, minimizing the (penalized) empirical error will have a high probability of yielding a model with low true error. This type of probabilistic bound is referred to as a Probably Approximately Correct (PAC) bound.

Generalization bounds measure the deviation of a random variable from its expected value, making concentration inequalities highly useful mathematical tools for deriving them. The most commonly used in practice are Hoeffding's inequality in the case of sums of variables and McDiarmid's inequality for bounded functions. We recall them in Appendix A.

We start by formally defining PAC learning, then move on to presenting three theoretical frameworks for deriving PAC generalization bounds: uniform convergence, uniform stability and algorithmic robustness. These frameworks will be used in Chapters 4 and 5 to derive generalization guarantees for the proposed learning methods.

PAC Learning

The idea of Probably Approximately Correct (PAC) learning [START_REF] Valiant | A Theory of the Learnable[END_REF] is that learning an unknown target concept should be considered successful only if a hypothesis good for approximating it can be found with high probability. The goal is thus that, with high probability (probably), the selected model function will have low generalization error (approximately correct).

The original framework is designed for learning the output of boolean functions. The instance space is assumed to be the set of all possible assignments of n Boolean variables X = {0, 1} n , and the probability of each instance is given by the distribution P over X . In this context, a concept c is a subset of X . A concept class C is a set of concepts over X . We can define PAC learnability as follows.

Definition 2.7 (PAC-learnable). Given 0 < δ, < 1, a concept class C is learnable by a polynomial time algorithm A if, for any distribution P of samples and any concept c ∈ C, there exists a polynomial p(•, •, •) such that A will produce with probability at least 1δ a hypothesis h ∈ C whose error is less than or equal to when given at least p(n, 1/δ, 1/ ) independent random examples.

The PAC framework was the first one to convey the notion of efficiency in learning in a similar way to complexity theory. The learning process must take place in polynomial time of the sample size and must use only a reasonable amount of examples, while providing a good approximation of the target concept. The smallest polynomial p for which learning C is possible represents the sample complexity of the algorithm A. The model is worst case, as it defines a unique bound for all target concepts and all distributions over the instance space.

Uniform Convergence

Uniform convergence analysis [START_REF] Vapnik | On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities[END_REF]) studies the concentration of empirical quantities towards their expected value. It is one of the most important tools for deriving PAC generalization bounds. These guarantees hold with high probability (usually 1δ, δ > 0) for a given hypothesis class and depend on the size of the training sample.

Through the law of large numbers, large samples provide higher confidence, while small samples or too large hypothesis classes come with small confidence and an important risk of overfitting. The classic convergence rate for this type of bounds is O(1/ √ n) in the size of the sample.

We have previously given the intuition of hypothesis complexity and its link to predictor performance. In practice, different measures exist for this complexity. In the case of finite hypothesis spaces, we get the following PAC bound: Theorem 2.8 (Uniform convergence bound for finite hypothesis spaces). Let S be a sample of size n drawn i.i.d. from a distribution P , H a finite hypothesis space of cardinality |H| and δ > 0. Then, with probability 1δ over the sample S, we have:

R P (h) ≤ R S (h) + ln |H| + ln (1/δ) 2n .
In the case of a continuous hypothesis space, |H| is no longer a finite value, thus the previous bound is no longer useful. Instead, we need measures that are capable of evaluating the complexity of a hypothesis space without considering its cardinality. These include the VC dimension [START_REF] Vapnik | On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities[END_REF], the fat-shattering dimension [START_REF] Michael | Efficient Distribution-Free Learning of Probabilistic Concepts[END_REF], the maximum discrepancy [START_REF] Peter | Model Selection and Error Estimation[END_REF], the Rademacher complexity [START_REF] Bartlett | Rademacher and Gaussian Complexities: Risk Bounds and Structural Results[END_REF][START_REF] Koltchinskii | Rademacher Penalties and Structural Risk Minimization[END_REF] and the Gaussian complexity [START_REF] Bartlett | Rademacher and Gaussian Complexities: Risk Bounds and Structural Results[END_REF].

Vapnik-Chervonenkis Dimension

The Vapnik-Chervonenkis (VC) dimension [START_REF] Vapnik | On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities[END_REF]) is one of the most important results in statistical learning theory. It has allowed to extent the learning theory from finite spaces to infinite ones, and is based on the observation that what matters is not the cardinality of H, but rather its expressive power.

Let us say we have a sample S containing n points. Intuitively, these n points can be labeled in 2 n ways as positive and negative, therefore defining 2 n labeling combinations.

If for any of these problems, we can find a hypothesis h ∈ H that separates the positive examples from the negative, then we say H shatters n points, i.e. any learning problem definable by n examples can be learned with no error by a hypothesis drawn from H. The maximum number of points that can be shattered by H is called the Vapnik-Chervonenkis (VC) dimension of H. We define this notion formally in the following way.

Definition 2.9 (VC dimension [START_REF] Vapnik | On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities[END_REF]). The VC dimension of a set of indicator functions H is the maximum number n of vectors x 1 , . . . , x n that can be separated into two classes in all 2 n possible ways using functions from H. If for any n there exists a set of n vectors that can be shattered by the set H, then the VC dimension is equal to infinity.

To illustrate this concept, consider the space of all linear classifiers in the plane (Figure 2.4).

The VC dimension of linear functions in the plane is 3 but not 4, since no four points can be shattered by a set of lines. In general, a linear function in an n dimensional space has VC dimension n + 1, which is also the number of free parameters.

Definition 2.9 has been extended to real-valued functions in [START_REF] Vladimi | Estimation of Dependences Based on Empirical Data[END_REF] and can be used to obtain generalization bounds of the following form.

Theorem 2.10 (Uniform convergence bound with VC dimension). Let S be a sample of size n drawn i.i.d. from a distribution P, H a hypothesis space of finite VC dimension VC(H) and δ > 0. Then, with probability 1δ over the sample S, we have:

R P (h) ≤ R S (h) + VC(H) ln 2n VC(h) + 1 + ln(4/δ) n .
It is worth noticing that a finite VC dimension for a hypothesis class H is equivalent to H being PAC-learnable under some regularity conditions. The VC dimension is a pessimistic measure, as it is distribution-free and evaluates the capacity of a class of functions in the worst case. On one hand, this is sometimes an advantage because it guarantees the bounds to hold for any data distribution. On the other hand, the bounds might not be tight for certain data distributions. Moreover, it does not take into account the way the algorithm learned the hypothesis h. In practice, the use of the VC dimension is limited, as some of classic machine learning algorithms have infinite VC dimensions (k-NN classifier, SVMs with certain kernels) and thus cannot be analyzed through this measure. We now turn to the Rademacher complexity, which is a sample-dependent measure that can provide a better insight into certain classes of functions than the VC dimension.

Rademacher Complexity

The uniform convergence bound based on the VC dimension is distribution independent.

In contrast, the Rademacher complexity is a more recent measure of complexity that allows to factor in the data distribution, or its empirical estimate. The method of Rademacher symmetrization has been thoroughly exploited in the empirical processes theory [START_REF] Gine | Some Limit Theorems for Empirical Processes[END_REF][START_REF] Koltchinskii | On the Central Limit Theorem for Empirical Measures[END_REF][START_REF] Pollard | A Central Limit Theorem for k-Means Clustering[END_REF], but its use in statistical inference has been limited until more recent years [START_REF] Koltchinskii | Rademacher Penalties and Structural Risk Minimization[END_REF].

Definition 2.11 (Empirical Rademacher complexity). Let S be a sample of size n drawn i.i.d. from a distribution P and H be a class of uniformly bounded functions. For every integer n, the empirical Rademacher complexity over H is

Rn (H) = E σ sup h∈H 1 n n i=1 σ i h(z i ) ,
where {σ i : i ∈ {1, . . . , n}} are independent Rademacher random variables, that is,

Pr(σ i = 1) = Pr(σ i = -1) = 1 2 .
Definition 2.12 (Rademacher complexity). The Rademacher complexity of H is defined as R n (H) = E S Rn (H).

Intuitively, for a given S and Rademacher vector σ, the supremum measures the maximum correlation between h(z i ) and σ i over all h ∈ H, that is the correlation of a learned hypothesis to a randomly relabeled sample. R n can be viewed as a measure of capacity of H to separate classes. As shown in [START_REF] Koltchinskii | Rademacher Penalties and Structural Risk Minimization[END_REF], if the value of R n is large, the class of hypothesis H will separate positive from negative examples even if the labels are assigned randomly. This is an indication that the hypothesis class is too large: a good choice for H would separate well the examples only when labels are assigned correctly. We now show a uniform convergence result for any class of bounded real-valued functions.

Theorem 2.13 (Uniform convergence bound using Rademacher complexity). With probability at least 1δ over S, every function h in H satisfies

R P (h) ≤ R S (h) + 2R n (H) + ln(1/δ) n .
Moreover, with probability at least 1δ over S, for every function h in H,

R P (h) ≤ R S (h) + 2 Rn (H) + 3 ln(2/δ) n .
Even though uniform convergence bounds do not take into account parameters from the learning algorithm, the Rademacher complexity term in the previous theorem can sometimes implicitly consider the impact of the regularization term. The second bound shows that the true risk can be bounded with respect to the empirical risk and the empirical Rademacher complexity, computed based on only one sample and one random vector σ.

Note that we will be using Rademacher complexity analysis in Chapter 4.

Independently of the choice of measure of complexity, uniform convergence analysis yields bounds based on the size of the training sample and the class of hypothesis selected. The main drawback of this characterization is that the bound does not take into account the learning algorithm, i.e. how the hypothesis h S is selected. We will now present two analytical frameworks that allow to derive generalization guarantees for a hypothesis h S based on the properties of the learning algorithm in a setting of regularized risk minimization.

Uniform Stability

Algorithmic stability (Bousquet & Elisseeff, 2001, 2002) is a framework based on sensitivity analysis, determining how much a variation in the input of a system can influence its output. The motivation in learning for such an analysis is to design robust algorithm that will not be affected by the sampling mechanisms providing the training set. From the different notions of stability, we will focus on uniform stability, the strongest notion from this family.

Recall that X and Y ⊂ R are respectively the input and the output space. Consider a labeled training sample S = {z i } n i=1 of size n in X × Y drawn i.i.d. from an unknown distribution P . We will denote by S i the training set obtained from S by replacing the ith example with a new independent one coming from the same distribution. In this setting, we can define uniform stability for a learning algorithm.

Definition 2.14 (Uniform stability [START_REF] Bousquet | Stability and Generalization[END_REF]). Given a loss function , a learning algorithm has a uniform stability in κ m with respect to , with κ ≥ 0 constant, if for all i,

∀S, |S| = n, sup z | (h S , z) -(h S i , z)| ≤ κ n .
Uniform stability ensures only small variations of the learned hypothesis are possible under minor perturbations in the training set. This property enables us to derive a generalization bound on the true error of an algorithm.

Theorem 2.15 (Uniform stability bound). Let S be a sample of size n drawn i.i.d. from a distribution P , a loss function upper-bounded by a constant B, and δ > 0. For any algorithm A with uniform stability of κ/n with respect to , with probability 1δ over the random sample S, we have:

R P (h S ) ≤ R S (h S ) + κ n + (2κ + B) ln(1/δ) 2n ,
for a hypothesis h S learned by the algorithm A from sample S.

The bounds obtained through uniform stability are relatively tight, as a consequence of taking into account the learning algorithm (more precisely, the loss function, the regularizer and the regularization parameter have an impact on κ). In contrast to uniform convergence, stability does not make any assumptions about the class of hypothesis. Notice that the two frameworks obtain the same convergence rate in the sample size. This framework can be applied to a large number of algorithms [START_REF] Bousquet | Stability and Generalization[END_REF], including k-NN classification, soft margin SVM classification and least squares regression. Its major drawback is that it can only be used with strongly convex regularization functions. [START_REF] Michael | Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation[END_REF] have shown that a finite VC dimension implies stability, in the sense that using the stability as a complexity measure does not yield worse bounds that the VC dimension.

Algorithmic Robustness

Algorithmic robustness [START_REF] Xu | Robustness and Generalization[END_REF][START_REF] Bellet | Supervised Metric Learning with Generalization Guarantees[END_REF] characterizes the capability of an algorithm to perform similarly on close training and test instances. While uniform stability covers the variations coming from the sample selection heuristic, robustness takes into account the other factor that justifies the randomness in learning, which is sample noise. For a robust algorithm, if a training sample and a test example are close to each other, then their associated loss values must also be close. The notion of closeness is based on a partitioning of the instance space Z based on covering numbers [START_REF] Kolmogorov | Entropy and -Capacity of Sets in Functional Spaces[END_REF].

Figure 2.5: Robustness using an L 1 norm cover. The difference in loss between z and z must be bounded.

Definition 2.16 (Covering number). For a metric space (S, ρ) and T ⊂ S, we say that T ⊂ S is an -cover of T , if ∀t ∈ T, ∃ t ∈ T such that ρ(t, t) ≤ . The covering number of

T is: N ( , T, ρ) = min{| T | : T is an -cover of T }.
In other words, the covering number is the number of spherical balls of a given size needed to completely cover a given space, with possible overlaps. The partition is used to determine closeness: two examples are close if they belong to the same region, implying that the norm between them is smaller than a fixed quantity ρ (Figure 2.5). Formally, the robustness is defined as follows.

Definition 2.17 (Algorithmic Robustness [START_REF] Xu | Robustness and Generalization[END_REF][START_REF] Bellet | Supervised Metric Learning with Generalization Guarantees[END_REF]). Algorithm A is (M, (•))-robust, for M ∈ N and (•) : Z n → R, if Z can be partitioned into M disjoint sets, denoted by {C i } M i=1 , such that the following holds for all S ∈ Z n :

∀z = (x, l(x)) ∈ S,∀z = (x , l(x )) ∈ Z, ∀i ∈ [M ] : if z, z ∈ C i , then | (A, z) -(A, z )| ≤ (S).
Roughly speaking, an algorithm is robust if for any test example z falling in the same subset as a training example z, the gap between the losses associated with z and z is bounded. This notion is a desired property of a learning algorithm, as it implies a lack of sensitivity to small perturbations in the data in the same sense as robust optimization. [START_REF] Xu | Robustness and Generalization[END_REF][START_REF] Bellet | Supervised Metric Learning with Generalization Guarantees[END_REF] have shown that robust algorithms generalize well in the following theorem.

Theorem 2.18 (Algorithmic robustness bound). Let be a loss function bounded by a constant B, and δ > 0. If an algorithm A is (M, (•))-robust, then, with probability 1δ, we have:

R P (h S ) ≤ R S (h S ) + (S) + B 2M ln 2 + 2 ln(1/δ) n ,
where h S is the hypothesis learned by A from the sample S.

Note that in the previous bound there is a trade-off between M and (S): the smaller the parts in the partition, the more of them there will be. Algorithmic robustness generalization bounds are usually not tight, due to the dependence on potentially large covering numbers.

Nevertheless, one important advantage of this framework is the capacity to integrate a large span of regularizers, including sparsity inducing norms.

Conclusion

In this chapter, we presented the setting for supervised learning, as well as the main frameworks for deriving generalization guarantees for learning algorithms. Based on these notions, Chapter 3 explains the impact of metrics on algorithm performance, along with presenting state of the methods in metric learning.

Chapter 3

Review of Metric Learning

Chapter abstract

In this chapter, we review the existing methods for supervised and semi-supervised metric learning. We begin by presenting an overview of some standard metrics. Our literature study covers supervised metric learning methods for feature vectors and time series. After discussing these aspects, we are able to conclude over the advantages and limitations of the state of the art methods, which represent the principal motivations for our contributions.

Introduction

The performance of most types of machine learning algorithms strongly depends on the representation of the data and the metrics used to compare instances. However, selecting an adapted metric or representation can prove to be a difficult task, and the choice should take into account multiple aspects, such as the field of application, the type of data, as well as the task to be accomplished. This is the reason for the important attention received by the topic of representation learning, which includes subjects like metric learning (Bellet et al., 2015), kernel learning [START_REF] Sonnenburg | Large Scale Multiple Kernel Learning[END_REF], feature learning [START_REF] Contardo | Recurrent Neural Networks for Adaptive Feature Acquisition[END_REF], etc. Examples of methods relying on metrics and the representation of the data include learning algorithms with different settings: [START_REF] Thomas | Nearest Neighbor Pattern Classification[END_REF], where the notion of neighborhood is defined with respect to a distance function.

• k-nearest neighbors (k-NN) classification (Cover &
• Kernel methods [START_REF] Schölkopf | Learning with Kernels[END_REF][START_REF] Shawe | Kernel Methods for Pattern Analysis[END_REF], where the data is projected in a new feature space through the use of a kernel function.

• K-means clustering [START_REF] Stuart | Least Squares Quantization in PCM[END_REF], which creates clusters of points in a way that minimizes within-class variance under a distance function.

• Information retrieval (Frakes & Baeza-Yates, 1992), where a similarity function is used to find the documents which are closest to a given query.

• Data visualization and dimensionality reduction [START_REF] Frits | Data Visualization: The State of the Art[END_REF], where a metric is often used to change the representation of the data.

The rest of this chapter is mainly split between two major parts. Section 3.2 establishes definitions and notations, before addressing the topic of standard metrics for features vectors and time series. Section 3.3 formally introduces metric learning and details the most relevant methods from this field dedicated to feature vectors and time series. This section is mostly dedicated to supervised and semi-supervised settings. Section 3.4 concludes this chapter by a discussion on the overall trend of state of the art methods in metric learning and their current limitations. This allows us to fully motivate the contributions that we propose in the following chapters.

Metrics

In this section, we provide an extended study of the most well-known measures for comparing vectors of features and time series. We start by formally defining distance and similarity functions.

Definition 3.1 (Distance function). A distance is a pairwise function d : X × X → R + which satisfies the conditions:

• d(x, y) ≥ 0 (non-negativity),

• d(x, y) = 0 ⇐⇒ x = y (identity of indiscernibles),

• d(x, y) = d(y, x) (symmetry),

• d(x, z) ≤ d(x, y) + d(y, z) (subadditivity or triangle inequality).

The first two conditions define a positive definite function. By relaxing the second condition, d becomes a pseudo-metric. The property of triangle inequality has already been vastly exploited to speed-up certain learning algorithms such as k-NN and K-means.

Definition 3.2 (Similarity function). A similarity function is a pairwise function K :

X × X → R. K is called symmetric if ∀x, x ∈ X , K(x, x ) = K(x , x).
Similarity functions can be any pairwise functions assigning scores to pairs of points.

Normally, they act in some sense as the inverse of distances: their values are high for similar (close) examples and low for distant ones, while dissimilarity functions behave like normalized distance functions. A special case of similarity functions are kernels, as presented in the previous chapter (Definition 2.5), which enforce the property of positive semi-definiteness.

Metrics for Feature Vectors

Minkowski distances Minkowski distances are a family of distances induced by the L p norms, defined for x, x ∈ R d and p ≥ 1 as When p < 1, the previous measure is not a proper distance anymore, since it violates triangle inequality. Minkowski distance is typically used with p being 1 or 2.

d p (x, x ) = x -x p = d i=1 |x i -x i | p 1/p . (3.1) p → 0 p = 0.3 p = 0.5 p = 1 p = 1.5 p = 2 p → ∞
When p = 1, we recover the Manhattan distance:

d 1 (x, x ) = x -x 1 = d i=1 |x i -x i |.
Similarly, for p = 2, we get the Euclidean distance:

d 2 (x, x ) = x -x 2 = d i=1 (x i -x i ) 2 1/2 = (x -x ) T (x -x ).
The Euclidean distance has the additional properties of being translation and rotation invariant, while Manhattan distance is only translation invariant. Note that Euclidean distance assumes all variables are independent and that variance across all dimensions is one, a scenario that is hardly achieved in real world. The limiting case of p reaching infinity defines the Chebyshev distance:

d ∞ (x, x ) = x -x ∞ = lim p→∞ d i=1 |x i -x i | p 1/p = max i |x i -x i |.

Mahalanobis distance

The Mahalanobis distance [START_REF] Prasanta | On the Generalised Distance in Statistics[END_REF] was originally defined as a measure of closeness between a point and a distribution. Given a vector x ∈ R d from a sample S of mean µ ∈ R d and covariance matrix Σ -1 , the Mahalanobis distance of x is:

d Σ -1 (x) = (x -µ) T Σ -1 (x -µ).
In a similar way, we can define the Mahalanobis distance between a pair of vectors x and x of the same distribution with the covariance matrix Σ -1 :

d Σ -1 (x, x ) = (x -x ) T Σ -1 (x -x ).
Currently, the term Mahalanobis distance often refers to its following variation, known also as the generalized ellipsoid distance (Ishikawa et al., 1998):

d M (x, x ) = (x -x ) T M(x -x ),
where M ∈ S d + . S d + denotes the cone of symmetric PSD d × d real-values matrices. This constraint on M makes d M a pseudo-metric. Setting M to the identity matrix yields the standard Euclidean distance. An intuition about the transformation applied through M can be found using Cholesky decomposition. Rewriting M as L T L, where L ∈ R r×d and r is the rank of M, gives:

d M (x, x ) = (x -x ) T M(x -x ) = (x -x ) T L T L(x -x ) = (Lx -Lx ) T (Lx -Lx ).
This decomposition shows that the Mahalanobis distance implies computing the Euclidean distance after a linear projection of the data using the matrix L. When r < d, M is low-rank, and the projection through L allows for a more compact representation of the data and cheaper computations. Because of its properties and intuitive interpretability, the Mahalanobis distance has attracted a considerable amount of interest in the metric learning community, as we will see in Section 3.3.

Cosine similarity

The cosine similarity is a measure of similarity between two vectors based on the cosine of the angle between them:

cos(x, x ) = x T x x 2 x 2 .
Its values range from -1, signifying complete dissimilarity, to 1, meaning exactly the same. When its value is 0, the cosine similarity indicates orthogonality (decorrelation). Figure 3.2 compares the behavior of the cosine similarity against the one of the Euclidean distance.

Cosine similarity is widely used in text mining, web mining and information retrieval [START_REF] Bao | Quick Asymmetric Text Similarity Measures[END_REF][START_REF] Grabowski | A Technique for Learning Similarities on Complex Structures with Applications to Extracting Ontologies[END_REF][START_REF] Hust | Learning Similarities for Collaborative Information Retrieval[END_REF], where documents are represented as vectors of words indicating term frequencies.

Bilinear similarity

The bilinear similarity is a generalization of the cosine similarity parameterized by the matrix M:

K M (x, x ) = x T Mx ,
where M is not required to be PSD. If the data is normalized, setting M to the identity matrix yields the cosine similarity. The advantage of the bilinear similarity w.r.t. the Linear kernel The simplest linear kernel is the dot product between instances in the original space X :

K lin (x, x ) = x T • x .
This kernel is equivalent to the cosine similarity without normalization or the bilinear similarity when M = I.

Polynomial kernel

K pol (x, x ) = ( x, x + 1) p ,
where p ∈ N is the degree of the polynomial. K pol projects the data into a nonlinear space of all monomials of degree up to p.

Gaussian kernel

The Gaussian kernel, also known as the radial basis function (RBF), is expressed as:

K RBF (x, x ) = exp - x -x 2 2 2σ 2 ,
where σ 2 > 0 is a variance (width) parameter. This kernel is a good example of a nonlinear implicit projection into an infinite-dimensional space.

Metrics for Time Series

The presence of time series in numerous fields of application makes them the object of considerable research effort for their classification or prediction, with impact in fields like speech and writing recognition [START_REF] Itakura | Minimum prediction residual principle applied to speech recognition[END_REF], energy consumption [START_REF] Dachraoui | Early Classification of Time Series as a Non Myopic Sequential Decision Making Problem[END_REF], object identification and tracking [START_REF] Papadimitriou | Streaming Pattern Discovery in Multiple Time-Series[END_REF], bioinformatics [START_REF] Aach | Aligning Gene Expression Time Series with Time Warping Algorithms[END_REF], patient care [START_REF] Tormene | Matching Incomplete Time Series with Dynamic Time Warping: An Algorithm and an Application to Post-Stroke Rehabilitation[END_REF], and many more. To solve such tasks, one is inherently brought to compare time series by pairs, in order to determine their closeness or common patterns. In this section, we present the main types of approaches for evaluating the distance or similarity between time series.

The Euclidean distance for two univariate time series X and X treats time moments as different features:

d 2 (X, X ) = t X t=1 (X i -X i ) 2 1/2
.

Short time series (STS) distance [START_REF] Möller-Levet | Fuzzy Clustering of Short Time-Series and Unevenly Distributed Sampling Points[END_REF] is designed for unevenly sampled time series, by explicitly modeling the varying length of sampling intervals:

d 2 ST S (X, X ) = t X -1 i=1 X i+1 -X i t i+1 -t i - X i+1 -X i t i+1 -t i 2 .
For the Euclidean distance and the STS distance, the series need to have the same phase and length, which is often not the case in practice.

Probability-based measures view time series as probability distributions. Probability-based distance [START_REF] Kumar | Clustering Seasonality Patterns in the Presence of Errors[END_REF] is based on the distribution of errors data, which they model through a Gaussian distribution. The resulting distance follows a Chi-square distribution and is scale invariant. Kullback-Leibler (KL) divergence (Warren [START_REF] Liao | Clustering of Time Series Data -A Survey[END_REF] for discrete distributions can be readily applied to time series. However, important differences in phase between the time series result in significant value differences between probability distributions. Moreover, KL divergence imposes that the two time series have the same length.

2-dimensional singular value decomposition (2dSVD) [START_REF] Weng | Classification of Multivariate Time Series Using Locality Preserving Projections[END_REF] uses the eigenvectors of row-row and column-column covariances as features, scoring the distance between two time series with the distance between these features. Locality preserving projections (LPP) [START_REF] Weng | Classification of Multivariate Time Series Using Locality Preserving Projections[END_REF] extends 2dSVD by trying to find a low-dimensional projection space for the features extracted with 2dSVD where samples from the same class are close. Both 2dSVD and LPP are sensitive to noisy data and outliers.

Complexity-invariant distance [START_REF] Gustavo | CID: An Efficient Complexity-Invariant Distance for Time Series[END_REF] uses information about complexity differences between two time series as a correction factor for existing distance measures. For example, the Euclidean distance can be made complexity-invariant through the following correction:

d CID (X, X ) = d 2 (X, X ) • max(CE(X), CE(X )) min(CE(X), CE(X )) ,
where CE is a complexity estimate defined as 2014), using the notion of compression rate instead of the complexity factor. The compression rate is computed based on the notion of entropy. The higher its value between two time series is, the closer they should be. Both distances can be computed efficiently in linear time in the length of the time series.

CE(X) = t X -1 t=1 (X t -X t+1 ) 2 . Compres- sion rate distance (Vinh & Anh, 2015) is based on Batista et al. (
Measuring the distance or similarity between time series that have the same length and are sampled uniformly is not a complex problem. However, in time series applications, the data is usually sampled by different sensors at different frequencies. In this case, there is no one-to-one correspondence between the time moments, and temporal distortions and shifts should be taken into account. To this end, time series need to be realigned before being compared.

Time series alignment Given two univariate or multivariate time series X and X , an alignment π is expressed as a sequence of pairs of indices:

π = π X (k) π X (k) , k = 1, . . . , t XX ,
where π X (k) is an index from time series X, π X (k) is an index from X , and t XX is the length of the alignment π. The pair of indices indicates that time moment X i of index π X (k) corresponds to time moment X j of index π X (k). Under an alignment, the two time series X and X can be extended to two new ones X and X , expressed as

Xk = X i X k = X j , k = 1, . . . , t XX .
X and X now have the same length and can be compared directly (e.g. through Euclidean distance). The warping path is correctly constructed if it satisfies the following constraints:

• Boundary constraint: π 1 = (1, 1), π t XX = (t X , t X );

• Monotonicity: if π k = (i, j) and π k+1 = (i , j ), then i ≥ i and j ≥ j, that is the alignment cannot progress backwards in time;

• Continuity: if π k = (i, j) and π k+1 = (i , j ), then i ≤ i + 1 and j ≤ j + 1, that is every point in the time series must be used in the alignment.

Under the previous constraints, an alignment is always at least as long as the longest of the two time series, but shorter than their cumulated lengths, i.e.

t XX ∈ [max(t X , t X ), t X +t X ].
In this dissertation, we will always consider alignments constructed with these properties. We now present the most well-known algorithm for computing the optimal alignment for a given pair of time series.

Dynamic time warping Dynamic time warping (DTW) [START_REF] Joseph | The Symmetric Time-Warping Problem: From Continuous to Discrete[END_REF]) is an elastic measure of the similarity between two time series which seeks to provide the best alignment between them. Its popularity is due to its capacity to work with series of different lengths and phases. DTW uses a dynamic programming technique to find the minimal distance between two time series, where sequences are warped by stretching or

Algorithm 3.1 Dynamic time warping Input Time series X of length t X , time series Y of length t Y , distance d(•, •) Output Distance between X and Y DTW := array(m, n) for i = 1 to t X do DTW[i, 0] ← ∞ end for for j = 1 to t Y do DTW[0, j] ← ∞ end for DTW[0, 0] ← 0 for i = 1 to t X do for j = 1 to t Y do DTW[i, j] ← d(X[i], Y [j]) + min(DTW[i -1, j], DTW[i, j -1], DTW[i -1, j -1]) end for end for return DTW[m, n]
shrinking the time dimension (see Figure 3.3). The method produces a valid alignment and can be summarized as follows. Given a pair of time series X and X , the first step is to construct a cost matrix C ∈ R t X ×t X where the entry at indices (i, j) represents the cost of aligning the time moment i from series X to the time moment j in X . The cost matrix can be known or fixed for certain tasks, but in most of the cases it is computed using a distance (usually, the Euclidean distance). Using C, DTW will compute a cumulative cost matrix C + ∈ R t X ×t X , where each element C + i,j represents the minimum cost for aligning series X up to point i with series X up to point j. This minimum cumulative cost is obtained using the relationship:

C + i,j = C i,j + min(C + i-1,j-1 , C + i,j-1 , C + i-1,j ), (3.2)
where

C + 1,1 = C 1,1 .
After computing all the elements in C + , the minimum distance under the best alignment is found in C + t X ,t X , and the alignment can be recovered through backtracking. The pseudo-code of DTW is detailed in Algorithm 3.1. DTW depends on the local distance defining the cost matrix used for the alignment. Using a task-specific cost matrix C can greatly improve performance of DTW. Notice that using a similarity (or affinity) matrix instead of a cost matrix transforms the computation of DTW in Equation (3.2) in a maximization problem. DTW is an elastic measure, it thus does not have distance properties, even when the cost matrix C is constructed using a proper distance.

The extensive comparative study from [START_REF] Ding | Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures[END_REF] proved that DTW is among the best measures for comparing time series and that the accuracy of the Euclidean distance converges to DTW as the size of the training set increases. Its major drawback is the quadratic complexity in the length of the time series. These two reasons have motivated an important research effort for improving the results of naive DTW, either by proposing efficient computation methods [START_REF] Al-Naymat | SparseDTW: A Novel Approach to Speed Up Dynamic Time Warping[END_REF][START_REF] Salvador | FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space[END_REF]) that reduce complexity, or by adjusting the constraints on the time deformation that is allowed.

Alignment constraints for DTW Applying additional constraints in the construction of the alignment has two main motivations: (i) it can speed up the computation by analyzing only a subset of all the possible warping paths and (ii) it can help avoid pathological warping (e.g. aligning the beginning of a time series with the end of another). Most heuristics for global constraints define a maximum range, usually around the diagonal, where the alignments are allowed. The Itakura parallelogram [START_REF] Itakura | Minimum prediction residual principle applied to speech recognition[END_REF] present a window which starts with width one at both ends of the time series and increases linearly from both ends to the middle of the time series (see Figure 3.4(a)); warping is possible only inside this area. Sakoe-Chiba band [START_REF] Sakoe | Dynamic-Programming Algorithm Optimization for Spoken Word Recognition[END_REF] was originally used for speech recognition and is now one of the most popular global path constraints. It imposes a band of constant width around the diagonal in which warping is allowed (Figure 3.4(b)), and is usually specified as a percentage of the length of the time series. In practice, small widths (<10%) work best in most of the cases (Keogh & Ratanamahatana, 2004). Setting the width of the band to zero yields the Euclidean distance. Ratanamahatana & Keogh (2004) proposed the Ratanamahatana-Keogh (R-K) band, an arbitrary shaped constraint computed from the data. The constraint can be written as a vector of values defining the allowed range of warping at each point of a time series, as depicted in Figure 3.4(c).

The authors propose a heuristic to automatically find the most appropriate width at each time point and show that the band improves classification performance, but determining the form of the band is computationally more expensive than fixed-size windows. The Sakoe-Chiba band and the Itakura parallelogram are special cases of the R-K band. [START_REF] Yu | Dynamic Time Warping Constraints Learning for Large Margin Nearest Neighbor Classification[END_REF] propose a large margin criterion to find the optimal bands which best separate the classes. Similarly to the R-K band, here also the constraint areas have variable widths depending on the time axis. The solution is found through brute force calculations, making the approach rather inefficient.

The common assumption on which most of the previous methods are based is that time series from the same class share a global pattern, while different classes are distinguishable on at least local some shapes. To handle the cases where this condition is not satisfied, They consider the original form of the Mahalanobis distance, based on the inverse covariance matrix of the data. As this matrix is not always invertible (i.e. when the number of samples is lower than the length of the time series), they use three heuristics for approximating it: a pseudoinverse, a covariance shrinkage method and a diagonal form of the matrix. The experiments show that these heuristics perform worse than the classic DTW, but have the advantage of being faster to compute.

Sequence alignment

The problem of aligning time series is strongly related to the more general one of sequence alignment. The latter is of impact in many applications in bioinformatics, like DNA and protein sequencing, as well as handwriting recognition, spell-checkers and natural language translation. Some of the measures used to compare sequences, more precisely character strings, have been adapted to time series comparison.

String edit distance [START_REF] Levenshtein | Binary Codes Capable of Correcting Deletions, Insertions, and Reversals[END_REF]) is a distance between strings of possibly different lengths built from a given alphabet. It is based on three types of operations: insertion, deletion and substitution of a symbol, each of which has a specific cost. A sequence of operations transforming a string into another is called an edit script. The edit distance between two strings is defined as the cost of the cheapest edit script that turns one string into the other. Computing the edit distance is done through a dynamic programming algorithm similar to DTW, that also has quadratic complexity. The Levenshtein distance is a particular form of edit distance which uses a unit cost matrix, thus corresponding to the minimum number of operations turning one string into another. The edit distance has been adapted to real sequences [START_REF] Lei Chen | Robust and Fast Similarity Search for Moving Object Trajectories[END_REF], making it readily applicable to time series. Longest common subsequence (LCS) metric [START_REF] Daniel | A Linear Space Algorithm for Computing Maximal Common Subsequences[END_REF][START_REF] Maier | The Complexity of Some Problems on Subsequences and Supersequences[END_REF] is also related to the edit distance, but it allows only insertion and deletion, not substitution. Its application to time series [START_REF] Vlachos | Indexing Time Series Under Conditions of Noise[END_REF]) is based on the idea that the longer common subsequences the two time series have, the closer they are. The most desirable characteristic in this distance is that it can waive noise and distortions in time series.

Temporal kernels [START_REF] Bahlmann | On-Line Handwriting Recognition with Support Vector Machines: A Kernel Approach[END_REF] proposed a kernel for time series based on the Euclidean distance and an optimal alignment between X and X :

K eucl (X, X ) = exp   -arg min π∈A(X,X ) 1 t XX t XX i=1 X i -X i 2   .
Another temporal kernel was proposed by [START_REF] Shimodaira | Dynamic Time-Alignment Kernel in Support Vector Machine[END_REF], based directly on the Gaussian kernel, also under an optimal alignment of the time series:

K gaus (X, X ) = arg max π∈A(X,X ) 1 t XX t XX i=1 exp(- 1 σ 2 X i -X i 2 ).
The exponentiation in the two previous formulations is introduced to make the kernels positive definite, but this property is not guaranteed neither in theory, nor in practice.

Global alignment (GA) kernel [START_REF] Cuturi | Fast Global Alignment Kernels[END_REF]; [START_REF] Cuturi | A Kernel for Time Series Based on Global Alignments[END_REF] is in turn not based on an optimal alignment under a certain criterion. It is instead defined as the exponentiated soft-minimum of all possible alignment distances,

K GA (X, X ) = π∈A(t X ,t X ) exp(-d X,X (π)).
In the sense of the kernel K GA , two sequences are similar if they share a wide set of efficient alignments. [START_REF] Cuturi | A Kernel for Time Series Based on Global Alignments[END_REF] show that the GA kernel is positive definite under mild conditions, while [START_REF] Cuturi | Fast Global Alignment Kernels[END_REF] proposes an efficient method for computing it.

Most of the metrics presented in this section, including DTW, are not implicitly designed to handle time series with multiple features. One way of adapting these methods is to weigh features equally, but that does not take into account the importance of each feature, nor the possible differences in scale. ten [START_REF] Gineke | Multi-dimensional dynamic time warping for gesture recognition[END_REF] proposed an adaptation of DTW to the multivariate case. [START_REF] Shokoohi-Yekta | On the Non-Trivial Generalization of Dynamic Time Warping to the Multi-Dimensional Case[END_REF] argue that DTW can be computed in two different ways: (i) when the features are strongly correlated, first compute a score for each time moment based on all features, then compute the DTW score for the whole time series using the local scores, or, (ii) when the features are only loosely coupled, compute the DTW score of each feature independently (treating them as univariate time series), then combine them in a global DTW score. They show that in practice there is not one of these methods that outperforms the other, but that the choice must be made depending on the application.

Metric learning

Metric Learning

Nonparametric distances or similarities do not have the capacity to adapt to the specificities of the problem, thus might not yield the best results. Moreover, the choice of metric has a crucial impact on performance.

In the previous sections, we have seen some parameterizable metrics which can be adapted to the problem at hand. Manually tuning these metrics can be a difficult task, especially when the number of parameters is elevated, or there is not much prior information available about the task. Metric learning aims at finding the parameters of a distance or similarity function that best account for the underlying geometry of the data. This section focuses on giving a comprehensive image of the state of the art in supervised and semi-supervised metric learning. For more details about these fields and some other settings that are not covered in this document, see the surveys from [START_REF] Bellet | A Survey on Metric Learning for Feature Vectors and Structured Data[END_REF]Bellet et al. ( , 2015)); [START_REF] Kulis | Metric Learning: A Survey[END_REF]; [START_REF] Yang | Distance Metric Learning: A Comprehensive Survey[END_REF].

In most instances of (semi-)supervised metric learning, the criterion that the learned metric should satisfy enforces class structure: examples from the same class are considered similar (or close in terms of distance) and should be placed together, while examples from different classes are dissimilar (far) and should not be mixed by the metric (see Figure 3.5). The parameters of the distance or similarity function are learned under the constraints induced by the previous intuition. The constraints from the data are usually integrated as weak supervision over pairs or triplets of points, with different semantics:

• Positive pairs (or must-link constraints): P = {(z, z ) ∈ S × S, where z and z should be similar};

• Negative pairs (or cannot-link constraints): N = {(z, z ) ∈ S × S, where z and z should be dissimilar};

• Relative triplets: R = {(z, z , z ) ∈ S × S × S, where z is more similar to z than to z }. Triplet constraints are a weaker form of supervision than pairs, thus being in many applications more easily available.

In a supervised setting, these constraints are easy to generate directly from the class information of the data. Nevertheless, producing all the pairs or triplets is costly and can yield an extremely large amount of constraints to satisfy, as the number of pairs (triplets) is quadratic (cubic) in the number of examples. On the other hand, the metric can be learned based only on a subset of constraints, but then the question of which pairs or triplets are more representative and how to find them becomes essential.

Under the constraints, the problem of learning the parameters of a metric function (usually the entries of a matrix) can be formulated as an optimization problem over a loss function in a regularized setting:

M = arg min M∈R d×d (M, P, N , R) + λ reg(M).
The methods from the state of the art are differentiated by the choice of the loss function , the regularizer reg(•), and the constraints they use (P, N , R), as we will see in the following.

Metric Learning for Feature Vectors

In the case of feature vectors, the instances are represented as vectors from a space X ⊆ R d . The methods in this category usually do not natively support categorical features. In this section, we review methods for supervised Mahalanobis distance learning (Section 3.3.1.1), supervised similarity learning (Section 3.3.1.2), semi-supervised metric learning (Section 3.3.1.3) and metric learning with generalization guarantees (Section 3.3.1.4). An overview of the other types of settings for learning metrics is given in Section 3.3.1.5.

Mahalanobis Distance Learning

Xing et al. [START_REF] Xing | Distance Metric Learning, with Application to Clustering with Side-Information[END_REF] proposed the first Mahalanobis distance learning method. Designed for clustering, the formulation aims at maximizing the distance between dissimilar points, while keeping the one between similar points under a certain threshold.

max M∈S d + (x i ,x j )∈N d M (x i , x j ) s.t. (x i ,x j )∈P d 2 M (x i , x j ) ≤ 1, (3.3)
where S d + the cone of symmetric PSD d×d real-values matrices. Problem (3.3) is convex and solved by a semi-definite programming (SDP) approach based on eigenvalue decomposition (cubic complexity in the number of features). This makes it intractable for medium and high-dimensional problems. Meanwhile, the lack of regularization makes it also sensitive to overfitting. [START_REF] Schultz | Learning a Distance Metric from Relative Comparisons[END_REF] learn a Mahalanobis distance M from a set of relative constraints, under the additional assumption that M = A T WA. Here, A is a fixed matrix, and W is diagonal. The squared Mahalanobis distance becomes

Schultz & Joachims

d 2 M (x i , x j ) = (Ax i -Ax j ) T W(Ax i -Ax j ).
The form of M ensures that it is PSD. W can be learned by solving the following quadratic program:

min W M 2 F s.t. d 2 M (x i , x k ) -d 2 M (x i , x j ) ≥ 1, ∀(z i , z j , z k ) ∈ R, (3.4)
where • 2 F is the squared Frobenius norm. This formulation is then adapted to allow margin violations by introducing slack variables. As the method only learns the diagonal matrix W, the metric is limited to a weighting of the Euclidean distance. Moreover, handpicking A can be difficult; in practice, it is set to I.

Goldberger et al. Neighborhood Component Analysis (NCA) [START_REF] Goldberger | Neighbourhood Components Analysis[END_REF]) learns a Mahalanobis distance that minimizes the expected leave-one-out error of the k-NN classifier. For this, they use the Cholesky decomposition of the matrix M = L T L. They define the probability that two points x i and x j are neighbors using a softmax rule over the Euclidean distance in the transformed space:

p ij = exp(-Lx i -Lx j 2 ) k =i exp(-Lx i -Lx k 2 , p ii = 0.
The distance is learned over L such that it maximizes the probability to correctly classify x i for all i: max

L i j:y i =y j p ij . (3.5)
When L is nonsquare, choosing L ∈ R d×d with d < d, induces a low-rank metric and allows to project the data in a lower dimensional space. The main limitation of solving Equation (3.5) over L is that the problem is nonconvex, thus being subject to local maxima. Moreover, d has to be selected by hand.

Shalev-Shwartz et al. POLA [START_REF] Shalev-Shwartz | Online and Batch Learning of Pseudo-Metrics[END_REF] is the first online method for learning a Mahalanobis distance from positive and negative pairs. The method learns the parameter matrix M, as well as a threshold b ≥ 1, used to separate classes, expressed for a tuple (z i , z j ) as:

y i y j (b -d 2 M (x i , x j )) ≥ 1.
The formulation considers one pair at a time and updates the parameters in two projection steps. The first step projects onto the set of admissible solutions for the current examples under hinge loss for large margin separation. This is obtained using an efficient closed-form solution. The second step projects the current solution matrix back onto the PSD cone.

Here, the projection is done efficiently, as it only needs to compute the minimum eigenvalue instead of a full eigenvalue decomposition (cubic complexity in the number of dimensions of the data). The online algorithm comes with a regret bound for the separable case, and POLA also has batch version.

Globerson & Roweis Maximally collapsing metric learning (MCML) [START_REF] Globerson | Metric Learning by Collapsing Classes[END_REF]) learns a Mahalanobis distance using the same probability distribution p ij as in NCA, but this time optimizing directly over M. The idea is to consider the best representation of the data to be of all members of a class as a single point, making the distance between them zero, while placing different classes at infinite distance. Their objective function minimizes the Kullback-Leibler divergence between p ij and the ideal mapping. The objective being convex in M, MCML does not have the difficulty of local optima as NCA. Instead, it suffers from the same expensive projections as MMC.

Weinberger & Saul Large margin nearest neighbor (LMNN) [START_REF] Kilian | Fast Solvers and Efficient Implementations for Distance Metric Learning[END_REF][START_REF] Villani | Optimal Transport: Old and New[END_REF][START_REF] Kilian | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF] is one of the most popular and effective methods for learning Mahalanobis distances for the k-NN classifier. The intuition is to obtain neighborhoods where all k points belong to the same class, while pushing instances from other classes outside the neighborhood. The method is based on positive and relative constraints, redefined through the notion of neighborhood:

P = {(z i , z j ) ∈ S × S, where y i = y j and x j is in the k-neighborhood of x i }, R = {(z i , z j , z k ) ∈ S × S × S
, where (z i , z j ) ∈ P and y i = y k }.

The distance matrix M is learned by solving a convex problem:

min M∈S d + ,ξ ijk ≥0
(1µ)

(x i ,x j )∈P d 2 M (x i , x j ) + µ i,j,k ξ ijk s.t. d 2 M (x i , x k ) -d 2 M (x i , x j ) ≥ 1 -ξ ijk ∀(i, j, k) ∈ R,
where µ ∈ [0, 1] is a trade-off parameter, and ξ ijk are slack variables that allow soft constraints. A specific solver based on subgradient descent and sets of active constraints allows the method to scale to millions of triplets. In spite of its lack of regularization, LMNN performs well in most cases and has been the basis of many variants. [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF] have shown that LMNN is prone to overfitting for high-dimensional data.

Davis et al. Information-theoretic metric learning (ITML) [START_REF] Davis | Information-Theoretic Metric Learning[END_REF] introduces LogDet divergence regularization for Mahalanobis distance learning, at the same time providing a cheap way for ensuring that M stays PSD. This Bregman divergence for PSD matrices is defined as:

D ld (M, M 0 ) = tr(M -1 0 ) -log det(M -1 0 ) -d,
where M 0 is a preset PSD matrix to which M should remain close, acting as a regularizer.

In practice, M 0 is usually set to the identity matrix, implying that M stays close to the Euclidean distance. The LogDet divergence is finite if and only if M is PSD, thus minimizing it yields a proper pseudo-distance. ITML is formulated as follows:

min M∈S d + D ld (M, M 0 ) s.t. d 2 M (x i , x j ) ≤ u ∀(x i , x j ) ∈ S d 2 M (x i , x k ) ≥ v ∀(x i , x k ) ∈ D, (3.6)
where u, v ∈ R are parameters for distance limits. Slack variables are further introduced to allow violations. This convex problem is solved efficiently, avoiding eigenvalue decomposition and semi-definite programming. Intuitively, minimizing D ld (M, M 0 ) is equivalent to reducing the KL divergence between two Gaussian distributions characterized by M and M 0 . Finally, M strongly depends on the initial value M 0 , which is an important shortcoming, as M 0 is handpicked.

P ij = 1, if x j is a neighbor of x i , otherwise, P ij = 0.
In addition to learning the matrix M parameterizing the Mahalanobis distance, this method also learns the target neighborhood to be considered, i.e. the constraints that work best for the problem. Their problem can be written as: min M,P,Ξ i,j

P ij • f ij (M, Ξ) s.t. i,j = |S| • K avg K max ≥ j P ij ≥ K min 1 ≥ P ij ≥ 0, constraints from the original problem,
where Ξ are the parameters specific to the original problem and f ij is the function relating the parameters M and Ξ to the neighborhood P ij in the original setting. Here, K max ≥ K avg ≥ K min are respectively the maximum, average and minimum number of neighbors an instance can have, and are set in advance. The problem is solved by alternating learning steps over the metric and the neighborhood, both of which are convex problems, provided that the initial metric learning approach is convex.

Huo et al. [START_REF] Huo | Robust and Effective Metric Learning Using Capped Trace Norm: Metric Learning via Capped Trace Norm[END_REF] introduce capped trace norm regularization for metric learning. Its purpose is to provide a low-rank metric without using Cholesky decomposition or having to manually tune the rank of the matrix M. The capped trace norm is defined as:

reg(M) = d i=1 min{σ i , },
where σ i represent the singular values of the learned matrix, and is a fixed threshold. The impact of this regularizer is that it only minimizes the singular values which are lower than . The method uses quadruplet constraints [START_REF] Marc | Quadruplet-Wise Image Similarity Learning[END_REF], which encompass the standard pair and triplet constraints and are expressed as:

A = {(z i , z j , z k , z l ) ∈ S × S × S × S : d 2 M (x k , x l ) ≥ d 2 M (x i , x j )}.
The constraints are used to solve the following problem:

min M∈S d + q∈A ξ q + (x i -x j ) T M(x i -x j ) -(x k -x l ) T M(x k -x l ) + + λ 2 reg(M),
where λ is the regularization parameter and ξ q are the margins for each quadruplet. The formulation is non-smooth and non-convex, so the authors solve a convex surrogate instead. However, using this approach, the final solution only converges to a local minima.

Similarity Learning

Qamar & Gaussier SiLA (Qamar & Gaussier, 2009b;[START_REF] Qamar | Similarity Learning for Nearest Neighbor Classification[END_REF] is an extension of the voted perceptron algorithm allowing to learn a generic similarity function of the form:

K M (x, x ) = x T Mx N (x, x ) ,
where N is a normalization depending on x and x . Like in the case of most similarity functions, M ∈ R d×d is a square matrix that is not necessarily PSD, nor symmetric. At each iteration, the algorithm proceeds to update the matrix in an online manner using the perceptron rule for the points that do not respect the separation criterion. This criterion is based on target neighborhoods similar to those from LMNN, but here the neighbors are recomputed between iterations under the new K M . The method comes with regret bounds for the separable and nonseparable settings, based on the theory of the voted perceptron.

Qamar & Gaussier gCosLA (Qamar & Gaussier, 2009a) is an online method for learning generalized cosine similarities defined as:

K M (x, x ) = x T Mx √ x T Mx √ x T Mx ,
where M ∈ R d×d is symmetric and PSD. Positive pairs are used to guide the method under a hinge loss function. The algorithm is a two steps approach, similar to POLA: a projection to obtain zero loss on the current pair, followed by a second one onto the cone of PSD matrices. The authors derive a closed-form solution for the former step, but the latter needs a full eigenvalue decomposition, making it computationally expensive. In practice, gCosLA improves performance over SiLA and has comparable results to LMNN and ITML. gCosLA also comes with regret bounds and a batch version.

Chechik et al. OASIS (Chechik et al., 2009) is an online approach for learning a bilinear similarity for image retrieval based on k-NN. The method uses relative constraints and a hinge loss over the triplets. Starting with M = I, each iteration t is performed by solving the following convex problem on one triplet drawn randomly:

M t = arg min M,ξ 1 2 M -M t-1 2 F + cξ s.t. 1 -d 2 M (x i , x j ) + d 2 M (x i , x k ) ≤ ξ ξ ≥ 0, (3.7)
where c is a trade-off parameter that controls how much the solution will be affected by each iteration, and ξ is a slack variable. If the triplet constraint is satisfied, then no update is performed; otherwise, the solution is updated through a closed-form update based on the passive-aggressive algorithm [START_REF] Crammer | Online Passive-Aggressive Algorithms[END_REF]. As a result of using a bilinear similarity, the method can handle sparse data (in their experiments, images stored through bag-of-words) in an efficient way, allowing it to scale to millions of examples.

Semi-Supervised Metric Learning

The following metric learning methods use a semi-supervised setting in order to improve the performance through the use of unlabeled data.

Hoi et al. Laplacian regularized metric learning (LRML) [START_REF] Steven | Semi-Supervised Distance Metric Learning for Collaborative Image Retrieval[END_REF][START_REF] Steven | Semi-Supervised Distance Metric Learning for Collaborative Image Retrieval and Clustering[END_REF] is one of the first methods to explore unlabeled data explicitly for distance learning. It learns a Mahalanobis distance M with manifold regularization using a Laplacian matrix which integrates neighborhood relations. The side information comes in the form of positive and negative pairs. LRML is formulated as:

min M∈S d + tr(XLX T M) + γ s (x i ,x j )∈P d 2 M (x i , x j ) -γ d (x i ,x k )∈N d 2 M (x i , x j ) s.t. log det(M) ≥ 0, (3.8)
where X is the data matrix where each x T is a row, γ d , γ s > 0 are trade-off parameters and tr is the trace operator. Here, L = D -W is a Laplacian regularizer, where W ∈ {0, 1} |S|×|S| is the Laplacian matrix and D ∈ N |S|×|S| is a diagonal matrix computed as D ii = j W ij , i.e. containing the total number of neighbors for each point. The constraint is introduced to prevent trivial solutions where the entire space is shrunken (M = 0). Problem (3.8) is solved either as a classic SDP or in a modified, faster version through matrix inversion.

LRML is used to solve image retrieval and image clustering applications, with particularly good results compared to fully supervised methods when side information is scarce. This indicates that semi-supervised metric learning can leverage additional information coming from unlabeled data for better performance.

Zha et al. Log-determinant regularized distance metric learning L-DML (Zha et al., 2009) uses a similar formulation to that of LRML, with the distinction that the regularization term is a weighted sum using multiple metrics, which are learned over various datasets different from the target task. The method learns one Mahalanobis distance using the positive and negative pairs from the given dataset to measure the loss, while the regularization term uses unlabeled data from different tasks.

min M∈S d + ,α K k=1 α k tr(XL k X T M) + γ s (x i ,x j )∈P d 2 M (x i , x j ) -γ d (x i ,x k )∈N d 2 M (x i , x j ) + β M 2 2 s.t. K k=1 α k = 1, α k ≥ 0, ∀k,
(3.9) where α contains the weights associated with each of the K metrics, β is a regularization parameter, and all the other notations correspond to the ones in LRML (Problem (3.8)). The authors propose to solve the problem by alternating optimization steps over M (SDP) and α (LP).

Niu et al. SERAPH [START_REF] Niu | Information-Theoretic Semi-Supervised Metric Learning via Entropy Regularization[END_REF] is a semi-supervised information-theoretic approach that learns a Mahalanobis distance. The metric is optimized to maximize the entropy over labeled similar and dissimilar pairs (in our notation, P and N ), and to minimize it over unlabeled data (U). Let p M ij (y) = p M (y|x i , x j ) be the probability of labeling (x, x ) with label y, parameterized by the distance matrix M. SERAPH is expressed as:

max M,κ P∪N ln p M ij (y ij ) - γ 2 κ 2 + µ U y p M ij ln p M ij (y) -λ tr(M), (3.10)
where µ, λ are trade-off parameters between supervision, unsupervised information and regularization, y ij is the (shared) label of x i and x j and κ is a dual variable. The penalty presumes a Gaussian prior on the expected data moments, following the generalized maximum entropy principle [START_REF] Jaynes | Information Theory and Statistical Mechanics[END_REF]. The formulation in Problem (3.10) is nonconvex, being solved through an expectation-maximization (EM) algorithm. In experiments for k-NN classification, SERAPH slightly outperforms fully supervised methods like LMNN.

Semi-supervised metric and kernel learning has also been used to aid unsupervised learning, more precisely clustering, through small amounts of labeled data (Baghshah & Shouraki, 2009;[START_REF] Bilenko | Integrating Constraints and Metric Learning in Semi-supervised Clustering[END_REF][START_REF] Yeung | A Kernel Approach for Semisupervised Metric Learning[END_REF][START_REF] Yin | Semi-Supervised Clustering with Metric Learning: an Adaptive Kernel Method[END_REF].

In Chapter 4, our contribution will show a different way of exploiting unlabeled data in a semi-supervised classification setup.

Metric Learning with Generalization Guarantees

Although a large number of methods have been developed for (semi-)supervised metric learning, few studies analyze the theoretical properties of this type of algorithm. In the context of metric learning, and in contrast to the general machine learning setting, generalization guarantees can be addressed from two points of view:

• The consistency of the learned metric, i.e. the capacity of the metric to unseen examples and constraints; in practice, this amounts to bounding the difference between its performance on the training sample and on unseen examples.

• The performance of the associated classifier for the given task in terms of generalization error when using the learned metric.

Another important distinction between generalization bounds for machine learning in general and metric learning comes from the sampling of the data. All the theoretical frameworks presented in Section 2.7 make the assumption that the examples are independent and identically distributed. While this claim is often satisfied when using labeled examples directly, as we have seen, metric learning algorithms usually incorporate constraints on pairs and triplets of points. Even though the examples themselves are drawn i.i.d., this is not the case for the constraints. For this reason, standard theoretical frameworks cannot be applied directly to metric learning. However, the exist strategies that allow to make the pairs or triplets independent.

We now discuss the two questions of metric consistency and classifier performance based on the studies that have explored them.

Metric consistency Jin et al. ( 2009) study a generic distance learning formulation under Frobenius regularization and pair constraints:

min M∈S d + 1 |S| 2 (z i ,z j )∈S×S (d 2 M , z i , z j ) + λ M F , (3.11)
where λ > 0 is the regularization parameter. The loss function they use is:

(d 2 M , z i , z j ) = f (y i y j (1 -d 2 M (x i , x j ))),
where f is convex and Lipschitz continuous. The paper adapts the framework of uniform stability (see Section 2.7.3) to the case of learning distances from pairs of examples. For their setting, they provide a generalization bound for the learned metric, but, as it is always the case for uniform stability, this limits their framework to Frobenius regularized formulations. The bound they deduce relates the true error of the learned metric R P to the empirical loss R S :

|R P (M) -R S (M)| ≤ 8L 2 R 2 λn + 8L 2 R 4 λ + 4Ls(d) + 2g 0 ln(2/δ) 2n ,
where the loss is L-lipschitz, sup x x 2 ≤ R, s(d) = min dg 0 2λ , η(d) , g 0 is the maximum loss when M = 0 and tr(M) ≤ η(d). In practice, Problem (3.11) is solved through an online approach, for which they provide regret bounds.

2009):

(

d 2 M , z i , z j ) = f (y i y j (c -d 2 M (x i , x j ))),
with c > 0 a threshold parameter separating positive from negative pairs, and f a convex and Lipschitz continuous function. The framework is formulated as follows:

min (M,c)∈Q 1 |S| 2 (z i ,z j )∈S×S (d 2 M , z i , z j ), (3.12)
where the set of constraints Q = {(M, c) : 0 M I, 0 ≤ c ≤ a 0 , a 0 > 0} plays the role of limiting the complexity of the hypothesis. The theoretical results prove the consistency of the learned distance, i.e. its convergence to the optimal value, as well as a generalization bound. This framework is applicable to a large range of loss functions, of which the authors study the logarithmic loss and a smoothed version of the hinge loss. However, the ERM design of the problem prevents it from being used with regularization. [START_REF] Cao | Generalization Bounds for Metric and Similarity Learning[END_REF] use the Rademacher complexity to derive consistency bounds for metrics learned under several matrix norm regularizers. The theoretical results cover the bilinear similarity and the Mahalanobis distance. Given a sample S of n instances, their learning formulation (using the Mahalanobis distance) is the following:

min M∈S d + ,b∈R 1 n(n -1) i,j∈Nn,i =j [1 + y i y j (d M (x i , x j ) -b)] + + λ M 2 , (3.13)
where b is an offset they learn at the same time as the metric, λ is the regularization parameter and • is a general matrix norm. The consistency bound derived for Problem (3.13) is the following:

R P (M, b) -R S (M, b) ≤ 4R n √ λ + 4(3 + 2X * / √ λ) √ n + 2(1 + X * / √ λ) 2 ln(1/δ) n ,
where R n is the Rademacher complexity and

X * = sup x,x (x -x )(x -x ) T * .
Bellet & Habrard (2015) adapt the notion of algorithmic robustness (presented in Section 2.7.4) to the metric learning setting, where data is accessed through pairs of points.

Their results hold for any matrix norm regularizer. For a (K, (•))-robust algorithm, with probability 1δ, we have:

R P (M) -R S (M) ≤ (S) + 2B 2K ln 2 + 2 ln(1/δ) n ,
where the loss function is bounded by B. Furthermore, they show that a weak notion of robustness is a necessary and sufficient condition for a metric learning algorithm to generalize.

Regressive virtual metric learning (RVML) [START_REF] Perrot | Regressive Virtual Metric Learning[END_REF] is a Mahalanobis distance learning method based on virtual points. These points are set beforehand and help setting the constraints for the metric: each training point is assigned a virtual point, to which the metric will try to bring it close. Assigning a single virtual point per example drastically reduces the number of constraints of the problem, but makes the strategy for choosing virtual points vital for performance. The authors propose two heuristics for virtual points selection, one based on optimal transport [START_REF] Villani | Optimal Transport: Old and New[END_REF], the other on choosing one virtual point per class and pushing all the points from the same class towards it. Once the virtual points are selected, RVML is formulated as a regularized least-squares problem over matrix L ∈ R d×d coming from the decomposition M = L T L:

min L 1 |S| XL -V 2 F + λ L 2 F , (3.14)
where X is the data matrix, V is the virtual points matrix, and λ is the regularization parameter. Problem (3.14) has a closed-form solution using matrix inversions, which limits its scaling capacities for high dimensional datasets. The matrix M is PSD by construction, thus avoiding expensive projections. RVML comes with a consistency bound based on uniform stability:

R P (M) -R S (M) ≤ 8C 2 v C 2 x λn 1 + C x √ λ 2 + 1 + 16C 2 x λ C 2 v 1 + C x √ λ 2 ln(1/δ) 2n ,
where the training examples are bounded w.r.t. a constant x 2 ≤ C x , and the landmarks are also bounded as v 2 ≤ C v . The authors further link their formulation to the general framework in Jin et al. (2009).

Classifier performance with learned metrics To the best of our knowledge, the problem of finding the link between the prediction performance and the properties of a learned metric has only been tackled for linear classification.

Similarity learning for linear classification (SLLC) [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF] uses the theory of ( , γ, τ )-good similarity functions [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF]Balcan et al., 2008b) to ensure the performance of the classifier constructed using the learned metric. The framework of ( , γ, τ )-good similarity functions is one of the first results that relates the properties of a similarity function to those of a linear classifier using it. The contributions in this thesis are strongly based on the ( , γ, τ )-good framework; we will thus present it in more detail in Chapter 4. [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF] propose to directly optimize the ( , γ, τ )-goodness of a bilinear similarity under Frobenius regularization before plugging it in the linear classifier proposed by Balcan et al. (2008b). They also derive consistency bounds for the metric through uniform stability.

Guo & Ying (2013) extend the results from [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF] to several matrix norms using a Rademacher complexity analysis, based on techniques from [START_REF] Cao | Generalization Bounds for Metric and Similarity Learning[END_REF].

Recently, this framework has further been adapted to regularized online learning from pairs of points with theoretical guarantees [START_REF] Guo | Online Regularized Learning with Pairwise Loss Functions[END_REF].

Other Types of Approaches

Nonlinear metric learning The approaches we have analyzed so far learn a linear metric. Only a small number of methods have directly used nonlinear forms of metrics.

The main difficulty is that introducing nonlinearity often makes problem suffer from non convexity. [START_REF] Chopra | Learning a Similarity Metric Discriminatively, with Application to Face Verification[END_REF] proposed the first method for learning nonlinear metrics. They aim to learn a low-dimensional representation of the data where the examples in positive pairs are represented as close, while negative pairs are far. The nonlinear projection is obtained through a multilayer convolutional neural network. The weights of this model are learned through back-propagation and stochastic gradient descent, minimizing a loss function which imposes a separation criterion.

Gradient-boosted LMNN (GB-LMNN) [START_REF] Kedem | Non-Linear Metric Learning[END_REF]) is a version of LMNN learning a distance in a projection space determined by a nonlinear function φ. The mapping is defined as a combination between the metric of standard LMNN and additive combination of gradient boosted regression trees [START_REF] Friedman | Greedy Function Approximation: A Gradient Boosting Machine[END_REF]. The algorithm is iterative and aims at adding to the solution a new tree from the set of all regression trees of fixed depth at each step.

Another way of introducing nonlinearity is to kernelize a linear method using the kernel trick, as it is often done for SVMs. Methods that we have presented earlier which have been kernelized include [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF]; [START_REF] Davis | Information-Theoretic Metric Learning[END_REF]; [START_REF] Schultz | Learning a Distance Metric from Relative Comparisons[END_REF]; [START_REF] Shalev-Shwartz | Online and Batch Learning of Pseudo-Metrics[END_REF].

Multiple metric learning Learning multiple linear metrics has the capacity to capture the heterogeneities of complex tasks for which using one metric does not perform well. The purpose is often to learn one metric per region of the space, or even one metric per examples. The challenge in this setting becomes the computational complexity of learning the metrics simultaneously, as well as providing a coherent global metric, that varies smoothly and compares examples from different regions in a consistent way.

M 2 -LMNN [START_REF] Kilian | Fast Solvers and Efficient Implementations for Distance Metric Learning[END_REF][START_REF] Villani | Optimal Transport: Old and New[END_REF] is an extension of LMNN that learns multiple metrics. The training data is first partitioned in C clusters. M 2 -LMNN learns one metric per cluster using the same objective as LMNN. When computing a distance, the metric associated to the first point in a pair is used. The overall learned metric is thus not symmetric, nor smooth. Moreover, it is sometimes prone to overfitting and computationally expensive.

Parametric local metric learning (PLML) (Wang et al., 2012a) learns one Mahalanobis distance per instance. Each distance is expressed as a linear combination of a limited number of metrics. The overall metric varies smoothly over the data manifold. The problem is solved in two steps: first, the weights for each instance are computed, then the metric bases are learned.

Sparse compositional metric learning (SCML) [START_REF] Shi | Sparse Compositional Metric Learning[END_REF]) learns a Mahalanobis distance in the form of a sparse linear combination of rank-one matrices. The combination of bases is custom per instance, but is still lightweight. The main disadvantage of the method is that the set of rank-one matrices is considered known (although the authors propose to generate them by clustering and Fischer discriminant analysis).

C2ML [START_REF] Zantedeschi | Metric Learning as Convex Combinations of Local Models with Generalization Guarantees[END_REF] addresses the problem of learning local combinations of

× × × × × Schultz & Joachims × × × POLA × × × NCA × × × × × MCML × × × × × LMNN × × × × Wang et al. × × × ITML × × × SiLA - × × × gCosLA × × × OASIS × × LRML × × L-DML × × SERAPH × × × Jin et al. × Bian & Tao × × × SLLC × × RVML × ×
metrics to obtain a smooth and symmetric overall metric. Starting from a partition of the space and a score function for each region, C2LM defines a metric between points as a weighted combination of the models. A weight vector is learned for each pair of regions, and a spatial regularization ensures that nearby models are favored in the combination. The method is designed for regression, using similarities and distances.

Table 3.1, which extends the one from [START_REF] Bellet | Supervised Metric Learning with Generalization Guarantees[END_REF], reviews the main characteristics of the supervised and semi-supervised metric learning approaches for feature vectors that we studied in this section.

Metric Learning for Time Series

An important proportion of the metrics that perform well on time series are not designed to deal with multivariate time series. One trivial way of adapting them is to weigh all features equally, but this results in degrading performance, as it does not take into account the varying importance of features, nor the possible differences in scale. Metric learning can address exactly this problem by learning the weights of the features and the correlations between them from the available training data. Unfortunately, metric learning for time series has been addressed only by a small number of methods, that we present in this section. These methods are mostly designed for k-NN classification, following the orientation of the time series analysis community.

Sun et al. [START_REF] Sun | Localized Supervised Metric Learning on Temporal Physiological Data[END_REF] apply Average Neighborhood Margin Maximization (ANMM) [START_REF] Wang | Feature Extraction by Maximizing the Average Neighborhood Margin[END_REF] to time series classification for the specific application of physiological data. ANMM is a supervised feature extraction method which aims to learn a projection matrix. For each training sample x i , the method enlarges its margin to neighbors from other classes P i , while keeping the distance to its neighbors from the same class N i as small as possible. The Mahalanobis distance they learn optimizes the ratio between the sum of distances over positive, respectively negative pairs:

min M x i ∈S x j P i d 2 M (x i , x j ) x i ∈S x k N i d 2 M (x i , x k )
. [START_REF] Sun | Localized Supervised Metric Learning on Temporal Physiological Data[END_REF] apply ANMM on features extracted from the temporal data in two ways: either using the first two statistical moments of each feature, or using the wavelet coefficients over temporal fixed-size windows.

Lajugie et al. In (Lajugie et al., 2014), the authors propose to learn a Mahalanobis distance for multivariate time series alignment of audio data. Let X = (A, B) be a pair of time series of same dimension d, but possibly of different lengths t A and t B , where A ∈ R t A ×d and B ∈ R t B ×d . The pairwise cost matrix used for computing the DTW cost is:

C(X, M) i,j = -(a i -b j ) T M(a i -b j ),
where a 1 , . . . , a t A are the time moments (rows) of A, and similarly for B. Considering groundtruth pairs of the form {(X i , π * i )} n i=1 known, they learn the Mahalanobis distance in the following way:

min M 1 n n i=1 H (π * i , arg max π i ∈A(t A ,t B ) tr(C(X i , M) T π i )) + λ M 2 F , (3.15)
where λ is the regularization parameter and H is the Hamming loss [START_REF] Hamming | Error Detecting and Error Correcting Codes[END_REF] between two alignments π 1 ∈ {0, 1} t A ×t B and π 2 ∈ {0, 1} t A ×t B encoded as binary matrices:

H (π 1 , π 2 ) = π 1 -π 2 2 F .
Problem (3.15) is intractable, but the authors solve a large margin surrogate instead. One significant limitation of this approach is that the true alignments are considered a priori known for the audio task, information that is not available in most cases. For this reason, their method cannot be applied in other contexts.

Mei et al. LDMLT [START_REF] Mei | Learning a Mahalanobis Distance-Based Dynamic Time Warping Measure for Multivariate Time Series Classification[END_REF] was designed to learn a Mahalanobis distance for multivariate time series classification from triplet constraints. The loss function over one triplet is computed through the DTW under Mahalanobis distance:

(M, z i , z j , z k ) = ρ + DTW M (z i , z j ) -DTW M (z i , z k ),
where ρ > 0 represents the target margin. The loss function is minimized one triplet at a time under the same LogDet regularizer as ITML. At iteration t, the objective function is thus:

M t+1 = arg min M∈S d + D ld (M, M t ) + λ t (M, z i , z j , z k ), (3.16)
with λ t controlling the trade-off between satisfying the triplet constraint and keeping the metric matrix close to the one in the previous iteration. Problem (3.16) is solved using a closed-form solution. Experiments are performed for nearest neighbor and SVM classification with good results. However, the loss function they use for the metric learning step is not related to the losses of the classifiers using it afterward.

Chen et al. Model Metric Co-Learning (MMCL) [START_REF] Chen | Model Metric Co-Learning for Time Series Classification[END_REF] uses a nonlinear state space model to learn a metric adapted to univariate and multivariate time series classification. The final representation of a sequence is a linear readout mapping, but the underlying model is a nonlinear dynamic system. The n-dimensional dynamical model is:

x(t) = tanh(Rx(t -1) + Vs(t)), f (t) = Wx(t), (
M (i, j) = (w i -w j ) T M(w i -w j ) (3.18)
The metric operates over a nonlinear state space model with a low representation cost, expressed as:

Q p (r, W) = s∈S ts t=1 f (t) -s(t + 1) 2 + η W 2 .
This equation aims to minimize the difference between actual output f (t) and desired output s(t + 1). A trade-off parameter λ controls the importance of these costs in the final formulation: min

r,M Q s (r, M) + λQ p (r, W),
where r are the parameters of the readout model and Q s (r, M) is the loss function from MCML using the distance in Equation (3.18). The problem is solved through alternating between state space model learning and metric learning in the readout model space.

Zhao et al. metricDTW [START_REF] Zhao | MetricDTW: Local Distance Metric Learning in Dynamic Time Warping[END_REF] proposes an adaptation of LMNN for Mahalanobis distance learning in the case of univariate time series k-NN classification. The method extracts local time series descriptors, clustering them and learning one metric per pair of clusters. The Mahalanobis distance is computed under DTW alignments computed beforehand. However, the matrices are constrained to be diagonal with the same value all over, which boils down to learning a scalar instead of a metric.

min M∈S d + (1 -µ) (i,j)∈P DTW M (X i , X j ) +µ (i,j,l)∈R (1 -y il )[1 + DTW M (X i , X j ) -DTW M (X i , X l )] + , (3.19)
where P and R are respectively the set of positive pairs and the set of relative triplets, both constructed as in LMNN, and µ is a trade-off parameter. The term y il is 1 when X i and X l share the same label, and 0 otherwise. The problem with Formulation (3.19) is that the measure of DTW under a metric M also takes into account the optimal alignment. As the optimal alignment is computed through dynamic programming and changes when the metric is changed, optimizing it is NP-hard. Moreover, this combinatorial factor makes the objective function non-convex and non-differentiable. To overcome this impediment, the authors propose an iterative approach, which first computes the best alignment through DTW under a fixed metric, then solves Problem (3.19) for a fixed alignment, much like standard LMNN. These two steps are repeated until convergence. To try and alleviate the problem of local minima, the authors use random initializations for the metric matrix M. In practice, LMNN-DTW has a higher order of complexity than similar methods (e.g. LDMLT), thus being slower, while achieving inferior performance.

Conclusion

In this chapter, we have discussed standard metrics for feature vectors and time series.

Their limitations justify the important body of work in metric learning aiming to provide task-specific measures. We have given an overview of a significant number of methods for supervised and semi-supervised metric learning for feature vectors and time series. The following points summarize the state of the art methods presented previously:

• Over the past 15 years, metric learning for feature vectors has focused on providing practical solutions for a computationally expensive problem. Currently, state of the art methods perform well and are efficient. However, this focus on practical aspects has been in the detriment of developing a theoretical foundation for metric learning. More precisely, only a small number of studies have been concerned with establishing the consistency of the learned metric on unseen data. Another question that has only rarely been answered is how do the properties of the metric relate to the capacities of the classifier using it, and what can be said about the link between the empirical risk and the true risk.

• A small number of metric learning approaches exists for semi-supervised classification.

These methods explore a limited number of ways to incorporate unlabeled information, mostly through adjacency relations. None of these methods come with any theoretical guarantees over the metric or the classifier.

• Metric learning for time series has been addressed by a relatively small number of studies, mainly because of the additional computational complexity introduced by this type of data. Most of the existing methods are adaptations of existing metric learning algorithms for feature vectors to temporal data. Furthermore, they are often applied on univariate time series, although multivariate temporal data is frequent in applications. The question of how to weigh multiple features across time remains a challenge. Moreover, if for feature vectors recent studies have started developing theoretical guarantees, this is not the case for metrics learned for time series.

• Metrics learned for feature vectors and time series classification are usually associated with the k-NN rule, while other types of classifiers have not extensively been explored.

The contributions in this dissertation aim to address the limitations of the state of the art methods. Chapter 4 is devoted to semi-supervised metric learning for feature vectors.

We propose a generic framework that is capable of jointly learning a similarity function and a global linear separator from partially labeled data. We show that this framework can be used with a large number of similarity functions and regularizers. We derive two generalization bounds for our approach, one based on algorithmic robustness, the other one based on Rademacher complexity. Lastly, we compare these two frameworks in terms of results derivation and quality of the bounds. Chapter 5 is dedicated to learning metrics for multivariate time series classification. We propose a parameterized similarity function for time series and a method for learning it. We prove the consistency of our algorithm through arguments of uniform stability. The learned similarity function is used to induce a linear separator with good classification guarantees in the feature space.

Chapter 4

Joint Similarity and Classifier Learning for Feature Vectors

Chapter abstract

In this chapter, we propose a novel, generic framework for performing similarity learning at the same time as learning a global linear classifier from feature vectors. The formulation is capable of leveraging information from unsupervised data additionally to a labeled training set, making it a semi-supervised setting. We show that our framework can be used with a large class of regularizers and many similarity functions. We provide a theoretical analysis of this joint learning formulation through two different frameworks, the algorithmic robustness and the uniform convergence based on the Rademacher complexity, which we further compare. The theoretical results hold for the learned metric and the classifier at the same time. Moreover, they are generic and cover different similarity functions and regularizers without enforcing strong constraints. Experiments conducted on standard datasets show the benefits of our approach over state of the art methods: JSL is efficient and performant.

The content of this chapter is based on the following international publications:

Maria-Irina Nicolae, Éric Gaussier, Amaury Habrard, and

Introduction

As we have seen in the previous chapter, state of the art in metric learning for feature vectors is dominated by fully supervised methods, most of which are designed for k-NN classification. These metrics are mostly Mahalanobis distances, constraining the parameter matrix to be PSD and symmetric. However, the learned metrics are in most cases not guaranteed to perform well and lack generalization guarantees. We propose two variants of JSL: one which learns a full matrix, and another which limits the numbers of parameters by only learning a diagonal matrix (JSL-diag), thus being able to obtain a metric from a small amount of data. Optimizing the ( , γ, τ )-goodness of the similarity function preserves the theoretical guarantees from Balcan et al. (2008b) on the classifier in relation to the properties of the similarity. Furthermore, and unlike [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF], we propose here to jointly learn the metric and the classifier at the same time. This allows learning both the metric and the separator in a semi-supervised way, thus making use of the additional information coming from unlabeled data. To our knowledge, these two learning steps have never been performed jointly in metric learning. Semi-supervision makes JSL appropriate for a practical situation frequent in learning when the annotation of data is expensive, but unlabeled data can be easily obtained. We provide a complete theoretical analysis of our approach using two different frameworks: algorithmic robustness and uniform convergence with Rademacher complexity. We use them to derive two consistency bounds for the joint optimization problem, which we compare and discuss. Lastly, we provide an empirical study on classic datasets and compare our method to different families of supervised and semi-supervised learning algorithms, with or without metric learning.

The rest of this chapter is organized as follows. In Section 4.2, we introduce the theory of ( , γ, τ )-good similarity functions. Section 4.3 presents the formulation of JSL, our joint similarity and classifier learning framework, followed by some examples of similarity functions and regularizers that can be used with it. In Section 4.4, we propose a theoretical analysis of JSL, through the frameworks of algorithmic robustness and Rademacher complexity, leading to the derivation of generalization bounds. Section 4.5 proposes JSL-diag and its theoretical guarantees for learning a diagonal metric. The experimental evaluation in Section 4.6 proves the functional capacities of the proposed approach, with different similarities and regularizers. We compare JSL against a large number of machine learning and metric learning methods, some fully supervised, and others semi-supervised. Finally, we conclude our contribution in Section 4.7.

4.2 ( , γ, τ )-Good Similarities Framework [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF]; Balcan et al. (2008a,b) proposed a new learning theory for similarity functions. The goal of this framework is to generalize over learning with kernels, by relaxing some constraints, while still providing guarantees over the results. The theory of kernels is based on the large margin separation achieved between classes in the (sometimes) implicit and unknown mapping space of the kernel. However, the separation is not visible or evident in the original space of the data, making the design of kernels difficult. Moreover, the positive semi-definiteness constraint on kernels excludes from usage many intuitive similarity functions for the given task. To overcome these limitations, Balcan et al. define a new notion of good similarity function as follows.

Definition 4.1. (Balcan et al., 2008b) A similarity function K is an ( , γ, τ )-good similarity function for a learning problem P if there exists a (random) indicator function R(x) defining a (probabilistic) set of "reasonable points" such that the following conditions hold:

1. A 1probability mass of examples (x, y) satisfy:

E (x ,y )∼P yy K(x, x ) ≥ γ, 2. Pr x (R(x )) ≥ τ .
The first condition in Definition 4.1 can be interpreted as having a (1 -) proportion of examples x on average 2γ more similar to random reasonable examples x of their own label than to random reasonable examples x of the other label. It also expresses the tolerated margin violations in an averaged way: this allows for more flexibility than pairor triplet-based constraints. The second condition sets the minimum mass of reasonable points one must consider (greater than τ ). Notice that no constraint is imposed on the form of the similarity function. The definition covers kernel functions, as well as a large class of non PSD and non symmetric bounded similarities. More importantly, Balcan et al. (2008b) show that good similarity functions under Definition 4.1 can be used to learn a linear separator with good properties, i.e. low true risk.

Consider an ( , γ, τ )-good similarity function K. If the set of reasonable points R = {(x 1 , y 1 ), . . . , (x r , y r )} of size r is known, then, by using the empirical version of the expected values in Definition 4.1, the classifier achieving a true risk smaller than at margin γ is: Here, h is a linear classifier in the space of the similarity scores to the reasonable points. This implies that the data is projected through K with respect to the reasonable points using the mapping φ : X → R r ,

h(x) = sgn 1 r r i=1 y i K(x, x i ) .
φ i (x) = K(x, x i ), i ∈ {1, . . . , r}.
An example of input and similarity spaces is shown in Figure 4.1.

In practice, the set of reasonable points is not necessarily known. In this case, a set of landmarks can be sampled from the data to replace them. The number of landmarks needed is proportional to the parameter τ , the probability of a point being reasonable.

The landmarks are used in the same way as the reasonable points, that is to construct the feature space. Notice that, in accordance with Definition 4.1, the labels of the landmarks do not have to be known. We will be exploiting this advantage in the contribution that we present in this chapter. Provided that enough landmarks are sampled, there exists with high probability a linear classifier that obtains true error close to . This is formally expressed in Theorem 4.2. landmarks drawn from P . Consider the mapping φ L : X → R d defined as follows: φ L (x) = K(x, x i ), i ∈ {1, . . . , d}. Then, with probability 1δ over the random sample L, the induced distribution φ L (P ) in R d has a separator error at most + δ relative to L 1 margin at least γ/2.

In other words, if K is ( , γ, τ )-good according to Definition 4.1 and enough points are available, there exists a linear separator α with error arbitrarily close to in the space φ S .

The previous definition and theorem are expressed with respect to the error and L 1 margin violation. In practice, minimizing the number of violations for the zero-one loss is NP-hard.

The authors propose to overcome this limitation by using the hinge loss as a surrogate function. Making this change leads to a new form of Definition 4.1.

Definition 4.3. (Balcan et al., 2008b) K is a ( , γ, τ )-good similarity function in hinge loss for a learning problem P if there exists a random indicator function R(x) defining a probabilistic set of "reasonable points" such that the following conditions hold:

1. We have

E (x,y)∼P [1 -yg(x)/γ] + ≤ , where g(x) = E (x ,y ),R(x ) [y K(x, x )|R(x )]. 2. Pr x (R(x )) ≥ τ .
Under this definition, Theorem 4.2 can be rewritten with respect to the hinge loss:

Theorem 4.4. (Balcan et al., 2008b) Let K be an ( , γ, τ )-good similarity function in hinge loss for a learning problem P. For any 1 > 0 and 0

< δ < γ 1 /4 let L = {x 1 , x 2 , . . . , x d } be a sample of d = 2 τ log(2/δ) + 16 log(2/δ) ( 1 γ) 2
landmarks drawn from P. Consider the mapping

φ L : X → R d , φ L i (x) = K(x, x i ), i ∈ {1, . . . , d}.
With probability 1δ over the random sample L, the induced distribution φ L (P ) in R d , has a separator achieving hinge loss at most + 1 at margin γ.

One should notice that the transition from the zero-one loss to the hinge loss marginally increases the error of the separator. The procedure for finding the linear separator α ∈ R d that has low true risk involves two steps: first using d u potentially unlabeled examples as landmarks to construct the feature space, then using a new labeled set of size d l to estimate α ∈ R du . Given a set of d u landmarks L = {x 1 , . . . , x du } and a labeled sample of d l examples S = {(x 1 , y 1 ), . . . , (x d l , y d l )}, the separator α can be found by solving the following optimization problem:

min α d l i=1 1 - du j=1 α j y i K(x i , x j ) + s.t. du j=1 |α j | ≤ 1/γ. (4.1)
This formulation can be solved efficiently by linear programming. Furthermore, as it is L 1 -constrained, tuning the value of γ will produce a sparse solution. Problem (4.1) can be seen as an equivalent of an L 1 SVM [START_REF] Zhu | 1-Norm Support Vector Machines[END_REF]. However, some important differences distinguish the two approaches. As seen earlier, K is not required to be symmetric nor PSD, thus generalizing over the notion of kernel. Moreover, the similarity function allows to explicitly create the projection space containing the separator instead of considering an implicit Hilbert space induced by a kernel.

The classification rule based on the similarity K and the separator α takes the following form:

y = sgn du j=1 α j K(x, x j ). (4.2)
The framework of ( , γ, τ )-good similarity functions allows to evaluate the performance that can be expected of a global linear separator depending on how well a similarity function satisfies Definition 4.1. Unfortunately, nothing is said about a potential method to design a good similarity; the function is considered known and fixed. [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF] have shown how to directly optimize the ( , γ, τ )-goodness of a bilinear similarity function, before plugging it in Equation (4.2) to learn the classifier. Yet the similarity learning step is done in a completely supervised way, while the setting in Balcan et al. (2008b) opens the door to the use of unlabeled data. In the next sections, we present our contribution on learning ( , γ, τ )-good similarity functions from data.

Joint Similarity and Classifier Learning

In this section, we propose a novel similarity and classifier learning framework based on the theory from Balcan et al. (2008b). We extend this framework to jointly learn the similarity and the separator in a semi-supervised way.

Our goal is to optimize the ( , γ, τ )-goodness of a given similarity function. To this end, we have access to a labeled sample S = {(x i , y i )} d l i=1 of d l examples defined over Z = X × {-1; +1}) coming from an unknown probability distribution P , where X ⊆ R d .

We are also given a set L = {x j } du j=1 of d u unlabeled examples also coming from X . These represent the set of landmarks for building the feature space. Their selection will be discussed into more detail in the experiments. Furthermore, let K M (x, x ) be a generic similarity function, parameterized by the matrix M ∈ R d×d , whose ( , γ, τ )-goodness we aim to optimize.

We assume that K M (x, x ) ∈ [-1; +1] and that ||x|| 2 ≤ 1, but all our developments and results can directly be extended to any bounded similarities and datasets. Following the definition of ( , γ, τ )-goodness (Definition 4.3), we want to optimize the empirical goodness of K M over the training sample with respect to a given landmarks set. The empirical risk of a training instance z = (x, y) is thus:

(M, α, z, L) =   1 -y du j=1 α j K(x, x j )   + .
Our goal here is to find the matrix M and the global separator α ∈ R du that minimize the previous empirical loss over the whole sample S, with some guarantees on the generalization error of the associated classifier. To this end, we propose the following regularized formulation based on the joint optimization of the metric and the global separator:

min α,M d l i=1 1 -y i du j=1 α j K M (x i , x j ) + + λ||M -R|| (4.3) s.t. du j=1 |α j | ≤ 1/γ (4.4) M F ≤ 1, (4.5)
where λ > 0 is a regularization parameter, and R ∈ R d×d is a fixed matrix such that R F ≤ 1. The notation || • || refers to a generic matrix norm, for instance L 1 , L 2,1 or Frobenius norms.

The novelty of this formulation is the joint optimization over M and α: by solving Problem (4.3), we are learning the metric and the separator at the same time. One of its significant advantages is that it extends the semi-supervised setting from the separator learning step to the metric learning, and the two problems are solved using the same data. This method can naturally be used in situations where one has access to few labeled examples and some unlabeled ones: the labeled examples are used in this case to select the unlabeled examples that will serve to classify new points.

JSL is fundamentally different from standard metric learning approaches presented in Section 3.3.1, which are based on constraints over pairs and triplets of points. The advantage of JSL over these methods is that the constraints on the pairs of points do not need to be satisfied entirely, they only need to be met on average over the set of landmarks. In other words, this formulation is less restrictive than pair or triplet-based settings, and the constraints can be satisfied more easily. Moreover, as the number of landmarks can be much smaller than the size of the training set, generating all the pairs necessary for the computations is less expensive. As the set of landmarks is the same for all the training points, the constraints are global, learning a pair of global similarity and classifier. Constraint (4.4) takes into account the desired margin γ and is the same as in Balcan et al. (2008b). Constraint (4.5) ensures that the learned similarity is bounded. Once M and α have been learned, the associated binary classifier takes the form given in Equation (4.2).

Regularization and prior knowledge

The regularization term M -R serves to limit the complexity of the learned similarity function K M and can also contain prior knowledge about the form of the metric. The type of norm used and the regularization parameter λ can push more or less strongly the value of M towards the bias: Frobenius norm will ensure the values in M are not too far from those in R, while L 1 norm might push some of the entries of M to match exactly their counterparts in R. The prior knowledge about the task or the form of the metric is encoded in the matrix R, in a way similar to what is proposed in [START_REF] Davis | Information-Theoretic Metric Learning[END_REF]. If the non parameterized version of the similarity considered performs well, then a natural choice for R is the (rescaled) identity matrix 1 d • I. This way, the learned matrix will preserve the good properties of the non parameterized version and will improve it through learning. Another type of information that can be incorporated in R is the correlation between features. This can be achieved by setting R to the inverse of the covariance matrix of the data, as used in the original version of the Mahalanobis distance. Similar information can be encoded concerning the importance of each feature per class, giving more weight to features that are more representative of one of the classes {+1; -1}. We now propose a new method to capture the importance of each feature for discriminating a certain class. This heuristic is based on the distributions of each feature for each of the two classes through the Kullback-Leibler (KL) divergence. We assume here that each feature k ∈ {1, . . . , d} follows a Gaussian distribution in each class, with respective empirical means µ k+ (class +1) and µ k-(class -1) and standard deviations σ k+ (class +1) and σ k-(class -1). We can compute the empirical value of the KL divergence from a given sample as:

D k KL = log σ k+ σ k- + 1 2 σ 2 k+ σ 2 k- - σ 2 k- σ 2 k+ + (µ k--µ k+ ) 2 σ 2 k- , 1 ≤ k ≤ d. and the matrix R corresponds to diag(D 1 KL , D 2 KL , • • • , D d KL ).
Similarity functions In order to prove the versatility of JSL, we now propose three examples of similarity functions that can be incorporated in our formulation.

Let K 1 M be the bilinear form:

K 1 M (x, x ) = x T Mx .
We also define K 2 M :

K 2 M (x, x ) = 1 -(x -x ) T M(x -x ).
Similarly, let K 3 M be:

K 3 M (x, x ) = exp - (x -x ) T M(x -x ) 2σ 2 .
K 1 M and K 2 M are linear with respect to their arguments. K 2 M is a straightforward transformation of the Mahalanobis distance into a similarity function. K 3 M resembles the Gaussian kernel and is based on the squared Mahalanobis distance. It introduces nonlinearity in the form of a similarity that decreases fast when the distance between points increases (under the parameters of M). Its additional parameter σ allows to control the width of the "neighborhood" in which the pairs of points are scored high. All three similarities are bounded under the constraints of JSL and have the advantage of keeping Problem (4.3) convex. We will study into more detail the theoretical properties of these functions in the following section, when we show how they impact the generalization bounds that we derive for JSL. Note that we will make use of the first two similarity functions K 1 M and K 2 M in our experiments.

Solving JSL The properties of our framework depend on those of the chosen similarity function and the regularizer. Choosing convex similarity function in M, like in the previous examples, and a convex regularizer are sufficient enough properties to solve Problem (4.3) efficiently. In this case, the formulation of JSL is convex for the metric, as well as for the separator (but not necessarily jointly convex). Solving the problem does not require semi-definite programming, like many metric learning approaches, even when using Mahalanobis-based similarity functions (e.g. K 2

M or K 3 M ), as the similarity is not PSD.

The hinge loss objective is convex, provided that K M is convex in M, but it is not differentiable over all the domain. JSL can be solved in this form presented in Equation (4.3) through stochastic approaches. We propose to rewrite its formulation by transforming the sum of hinge losses in constraints and introducing slack variables ξ ∈ R d l + :

min α,M,ξ d l i=1 ξ i + λ||M -R|| s.t. 1 -y i du j=1 α j K M (x i , x j ) ≤ ξ i , 1 ≤ i ≤ d l du j=1 |α j | ≤ 1/γ M F ≤ 1. (4.6)
We propose to solve Problem (4.6) by alternating optimization steps over M and α. These steps can be performed efficiently by a standard convex optimization solver (e.g. Mosek (ApS, 2015)). In terms of complexity, this formulation has d 2 + d l + d u variables and only d l + 2 constraints, as opposed to standard metric learning approaches, where the number of constraints is proportional to the number of example pairs or triplets, i.e. quadratic or cubic in the number of examples. Notice that the number of landmarks does not affect the size of the problem, as the number of constraints does not depend on the size of L.

Theoretical Guarantees

In this section, we provide a theoretical analysis of JSL which allows us to establish generalization bounds for our joint similarity learning formulation. The analysis holds for a large class of similarity functions and regularizers. We derive two equivalent results using two different frameworks. In Section 4.4.1, we prove the algorithmic robustness of JSL and derive a PAC generalization bound based on this property. The theoretical analysis in Section 4.4.2 is based on the Rademacher complexity and also allows to provide a generalization bound. We compare these two approaches in Section 4.4.3.

For the purpose of the theoretical discussion to follow, let us rewrite the minimization Problem (4.3) with a more generalized notation of the loss function:

min α,M 1 d l d l i=1 (M, α, z i , L) + λ||M -R||, (4.7) s.t. du j=1 |α j | ≤ 1/γ (4.8) M F ≤ 1. (4.9) Recall that (M, α, z i , L)) = 1 -y i du j=1 α j K M (x i , x j ) +
is the instantaneous loss estimated at point z i = (x i , y i ). Therefore, the optimization Problem (4.7) under Constraints (4.8) and (4.9) reduces to minimizing the empirical risk

R S (M, α) = 1 d l d l i=1 (M, α, z i , L)
under regularization over the training set S. Let

R P (M, α) = E z∼P (M, α, z, L)
be the true risk w.r.t. the unknown distribution P . The target of generalization analysis for joint similarity learning is to bound the difference R P (M S , α S ) -R S (M S , α S ), where (M S , α S ) is the solution of JSL.

Note that the similarity and the separator are learned under a fixed set of landmarks L. This allows us to define the loss function and the risks with respect to individual examples from the training set, without using pairs of points, as it is usually done in metric learning.

For this reason, we are able to derive our generalization bounds based on the standard settings of both algorithmic robustness and Rademacher complexity analysis.

Algorithmic Robustness of JSL

We now present a theoretical analysis of our approach through the framework of algorithmic robustness. Our main result in this section is the derivation of a generalization bound (Theorem 4.9). Recall that, roughly speaking, an algorithm is robust if for any test example z falling in the same subset as a training example z, the gap between the losses associated with z and z is bounded. We first prove that JSL is robust, then we derive a PAC generalization bound based on this property. We now introduce the definition of l-lipschitzness, which will allow us to bound the value of the loss function and prove the robustness of JSL.

Definition 4.5 (l-lipschitz continuity). A similarity function K M (x, x ) parameterized by a matrix M is l-lipschitz with respect to its first argument if for any x 1 , x 2 , we have:

K M (x 1 , x ) -K M (x 2 , x ) ≤ l x 1 -x 2 .
The lipschitz continuity bounds the value of a function through the constant representing the slope of the function between its input points. Intuitively, it means that the values of the function vary in a controlled way over a limited input range. Going back to our examples of similarity functions, we prove their l-lipschitzness hereafter.

Lemma 4.6. The similarity functions K 1 M , K 2 M and K 3 M defined previously have the following lipschitzness properties respectively:

• K 1 M (x, x
) is 1-lipschitz w.r.t. its first argument.

• K 2 M (x, x ) is 4-lipschitz w.r.t. its first argument.

• K 3 M (x, x ) is l-lipschitz w.r.t. its first argument with l = 2 σ 2 exp 1 2σ 2 -exp -1 2σ 2 .
The proof of Lemma 4.6 is provided in Appendix B.1. With this property in mind, we can now prove the algorithmic robustness of JSL in the following theorem.

Theorem 4.7 (Algorithmic robustness of JSL). Given a partition of Z into M subsets {C i } such that z = (x, y) and z = (x , y ) ∈ C i and y = y , and provided that K M (x, x ) is l-lipschitz w.r.t. its first argument, the optimization Problem (4.7) with Constraints (4.8) and (4.9) is (M, (S))-robust with (S) = 1 γ lρ, where ρ = sup x,x ∈C i ||xx ||.

Proof.

(M, α, z) -(M, α, z ) =   1 - du j=1 α j yK M (x, x j )   + -   1 - du j=1 α j y K M (x , x j )   + ≤ du j=1 α j y K M (x , x j ) - du j=1 α j yK M (x, x j ) (4.10) = du j=1 α j (K M (x , x j ) -K M (x, x j )) ≤ du j=1 |α j | • K M (x , x j ) -K M (x, x j ) (4.11) ≤ du j=1 |α j | • l||x -x || ≤ 1 γ lρ (4.12)
We obtain Inequality (4.10) from the 1-lipschitzness of the hinge loss; Inequality (4.11) comes from triangle inequality; the first inequality on line (4.12) is due to the l-lipschitzness of K M (x, x j ) w.r.t. its first argument, and the result follows from Condition (4.8). Setting ρ = sup x,x ∈C i ||xx || 1 , we get the theorem.

We now give a PAC generalization bound on the true loss making use of the previous robustness result. We present the following concentration inequality that allows one to capture statistical information coming from the different regions of the partition of Z.

for l-lipschitzness the bound is computed as a function of the variation of the input, the admissibility takes into account the norms of the examples, as well as the parameters of the metric. Formally, we define admissibility as:

Definition 4.10. A pairwise similarity function K M : X × X → [-1, 1], parameterized by a matrix M ∈ R d×d , is said to be (β, c)-admissible if, for any matrix norm || • ||, there exist

β, c ∈ R such that ∀x, x ∈ X , |K M (x, x )| ≤ β + c • x x T • M .
We now prove the (β, c) admissibility of our example similarity functions.

Lemma 4.11. The similarity functions K 1 M , K 2 M and K 3 M defined previously have the following admissibility properties respectively:

• K 1 M (x, x ) is (0, 1)-admissible, that is |K 1 M (x, x )| ≤ ||x x T || • ||M||. • K 2 M (x, x ) is (1, 4)-admissible, that is |K 2 M (x, x )| ≤ 1 + 4 • ||x x T || • ||M||. • K 3 M (x, x ) is exp(-2/σ 2 ), 0 -admissible, that is |K 3 M (x, x )| ≤ exp - 2 σ 2 .
The Theorem 4.12 (Generalization bound using Rademacher complexity). Let (M S , α S ) be the solution to the joint Problem (4.7) and K M a (β, c)-admissible similarity function.

Then, for any 0 < δ < 1, with probability at least 1δ, the following holds:

|R P (M S , α S ) -R S (M S , α S )| ≤ 4R d l c γ + β + cX * γ 2 ln 1 δ d l ,
where

X * = sup x,x ∈X ||x x T || * .
Theorem 4.12 proves that learning M and α in a joint manner from a training set minimizes the generalization error, as the latter is bounded by the empirical error of our joint regularized formulation. We discuss into more detail the bound in the next section, where we also compare it against the similar result obtained using the algorithmic robustness of JSL. The proof of Theorem 4.12 makes use of the Rademacher symmetrization theorem and contraction property (Theorem 4.13 and Lemma 4.14), that we present in the following.

Theorem 4.13. [START_REF] Boucheron | Theory of Classification: A Survey of Some Recent Advances[END_REF] Let R n (F) be the Rademacher average over F as presented in Definition 2.12. We have:

E sup f ∈F Ef (S) - 1 n n i=1 f (z i ) ≤ 2R n (F).
Lemma 4.14. [START_REF] Ledoux | Probability in Banach Spaces: Isoperimetry and Processes[END_REF] Let F be a class of uniformly bounded realvalued functions on (Ω, µ) and m ∈ N. If for each i ∈ {1, . . . , m}, φ i : R → R is a function having a Lipschitz constant c i , then for any

{x i } i∈Nm , E sup f ∈F i∈Nm i φ i (f (x i )) ≤ 2E sup f ∈F i∈Nm c i i f (x i ) .
We are now able to present the proof of Theorem 4.12.

Proof of Theorem 4.12.

Observe that R S (M S , α S )-R P (M S , α S ) ≤ sup M,α [R S (M, α) -R P (M, α)],
as (M S , α S ) is the solution of Problem 4.7. Also, let S = (z 1 , . . . , z k , . . . , z d l ) and S = (z 1 , . . . , zk , . . . , z d l ), 1 ≤ k ≤ d l , be two close samples that only differ by one instance z k . Then, we have:

sup M,α [R S (M, α) -R P (M, α)] -sup M,α R S (M, α) -R P (M, α) ≤ sup M,α R S (M, α) -R S (M, α) = 1 d l sup M,α z=(x,y)∈S   1 - du j=1 α j yK M (x, x j )   + - z=(x,ỹ)∈ S   1 - du j=1 α j ỹK M (x, x j )   + = 1 d l sup M,α   1 - du j=1 α j y k K M (x k , x j )   + -   1 - du j=1 α j ỹk K M (x k , x j )   + = 1 d l sup M,α du j=1 α j ỹk K M (x k , x j ) - du j=1 α j y k K M (x k , x j ) (4.13) ≤ 2 d l sup M,α du j=1 α j y max k K M (x max k , x j ) where z max k = arg max z=(x,y)∈{z k ,z k } yK M (x, x j ) ≤ 2 d l sup M,α    du j=1 |α j | • |y max k | • |K M (x max k , x j )|    ≤ 2 d l β + cX * γ (4.14)
Inequality (4.13) comes from the 1-lipschitzness of the hinge loss; Inequality (4.14) comes from Constraint (4.9), ||M|| ≤ 1 and the (β, c)-admissibility of K M . Applying McDiarmid's inequality to the term sup M,α [R S (M, α) -R P (M, α)], with probability 1δ, we have:

sup M,α [R S (M, α) -R P (M, α)] ≤ E S sup M,α [R S (M, α) -R P (M, α)] + β + cX * γ 2 ln 1 δ d l .
In order to bound the gap between the true loss and the empirical loss, we now need to bound the expectation term on the right hand side of the above equation.

E S sup M,α [R S (M, α) -R P (M, α)] =E S sup M,α    1 d l d l i=1   1 - du j=1 α j y i K M (x i , x j )   + -R P (M, α)    ≤2E S,σ sup M,α    1 d l d l i=1 σ i   1 - du j=1 α j y i K M (x i , x j )   +    (4.15) ≤4E S,σ sup M,α 1 d l d l i=1 σ i y i du j=1 α j K M (x i , x j ) (4.16) ≤4 c γ E S,σ sup x 1 d l d l i=1 σ i y i x i xT * = 4R d l c γ .
(4.17)

We obtain Inequality (4.15) by applying Theorem 4.13, while Inequality (4.16) comes from the use of Lemma 4.14. The Inequality on line (4.17) makes use of the (β, c)-admissibility of the similarity function K M (Definition 4.10). Combining Inequalities (4.14) and (4.17) completes the proof of the theorem.

Discussion

We will now comment on the generalization bounds obtained for JSL (Theorems 4.9 and 4.12) and the two methods we have used to derive them.

The bound derived in Theorem 4.9 using the algorithmic robustness of JSL holds for all l-lipschitz similarity functions and all regularization norms. The latter characteristic comes from the fact that algorithmic robustness does not take into account at all the regularizer, facilitating the development of generic frameworks. Moreover, almost no algorithm-specific argument is needed to derive this type of bounds. This can also be seen as a downside, as the lack of information about how the hypothesis is learned yields very general results, producing loose consistency bounds. For the same reason, algorithmic robustness bounds are mostly similar even from one method to another. On the other hand, as robustness is based on covering numbers, the bound in Theorem 4.9 is parameterized by the number of parts in the partitioning of the space M and the size of each part ρ. As we have shown, there is a trade-off between these two values, both of which make the bound looser. In practice, these values are sometimes hard to estimate.

The bound derived in Theorem 4.12 depends on the (β, c)-admissibility of the similarity function, which is in some sort equivalent to the l-lipschitz constraint for algorithmic robustness. As we have seen in Section 2.7.2.2, the Rademacher complexity, unlike the VC dimension, is data-dependent and can integrate information about the task. Moreover, the Rademacher complexity of a given task can be estimated from a single training sample S.

Usually, Rademacher complexity-based bounds implicitly integrate the regularizer, as it is common practice to bound the matrix M using this term. This is not the case for JSL, as M F is bounded by a constant, making our bound independent from R and the chosen matrix norm.

When comparing the two generalization bounds derived for JSL, we notice that they both have the same order of convergence, that is O( 1

√ d l
) w.r.t. the size of the training set, which is the standard rate for PAC generalization bounds. On the other hand, none of the bounds manifests any dependence on the size of the landmarks set. Moreover, they are also independent of the dimensionality of the data. This property is due to the fact that M F is bounded by a constant. For the same reason, both bounds are agnostic to the regularization, which allows them to cover different types of norms for the term M -R , but makes them more loose as a downside. In both cases, the gap between the empirical and the true risk is inversely proportional to the margin γ, implying that the larger the margin (i.e. the separation between classes), the better the empirical risk estimates the true error. An important difference between the bounds resides in their respective first terms. Considering an infinite sample (d l → ∞), both terms of the Rademacher complexitybased bound go to zero (to see this, recall Definition 2.11 for the empirical Rademacher complexity). This is not the case for the bound based on algorithmic robustness: its first term is constant with respect to the size of the sample, making in our case the Rademacher complexity bound more informative.

To conclude, the two consistency bounds we have presented for JSL are mostly equivalent, with the same rate of convergence and dependence on similar parameters. Analyses based on Rademacher complexity can yield tighter bounds, as they integrate more information specific to the task, but are in practice harder to derive than their equivalent based on algorithmic robustness.

Learning a Diagonal Metric

In this section, we introduce a modified version of JSL which allows to learn a similarity function parameterized by a diagonal matrix at the same time as a linear classifier. As JSL is adapted for the case of small amounts of labeled information, the number of available examples is not always sufficient for learning the d 2 parameters of a full matrix. We thus propose JSL-diag, where the number of parameters to be learned for the similarity function is d. JSL-diag takes the following form: (4.18) where λ > 0 is a regularization parameter, and R ∈ R d×d is now a fixed diagonal matrix such that R ≤ d. The same heuristics for choosing R and the same similarity functions can be use for JSL-diag as for JSL. The semantics behind setting the off-diagonal values of M to zero is that the similarity function will not take into consideration the correlation between features. In practice, it has been shown that the change in performance is marginal with respect to the case of a full matrix (Qamar & Gaussier, 2009a). When introducing slack variables, the diagonal form of M reduces the number of variables of the problem from d 2 + d l + d u to only d + d l + d u , thus making it linear in the parameters. The constraint however does not change the number of constraints, which remains d l + 2. JSL-diag is solved similarly to JSL, through alternating optimization steps over M and α. We will use JSL-diag in the experimental section.

min α,M d l i=1 1 - du j=1 α j y i K M (x i , x j ) + + λ M -R s.t. du j=1 |α j | ≤ 1/γ M diagonal, |M kk | ≤ 1, 1 ≤ k ≤ d,
From a theoretical perspective, JSL-diag has the same properties as JSL, thus making it possible to derive similar generalization bounds. The only distinction comes from the constraint over M changing from M F ≤ 1 in the case of JSL to |M kk | ≤ 1, 1 ≤ k ≤ d for JSL-diag. The bound derived using algorithmic robustness Theorem 4.9 is the same for JSL and JSL-diag, as it is based on the partitioning of the space. On the other hand, we can rewrite Theorem 4.12 for JSL-diag as follows. Note that the proofs are the same as for JSL; we will thus omit them.

Theorem 4.15. Let (M S , α S ) be the solution to the joint problem (4.18) and K M a (β, c)-admissible similarity function. Then, for any 0 < δ < 1, with probability at least 1δ, the following holds:

|R P (M S , α S ) -R S (M S , α S )| ≤ 4R d l cd γ + β + cX * d γ 2 ln 1 δ d l ,
where

X * = sup x,x ∈X x x T * .
Changing the constraint on the bound of the norm of M makes the generalization bound in Theorem 4.15 less tight. Notice that the norm of M is now bounded by d, not 1 like in the case of JSL. As a consequence, the consistency bound for JSL-diag depends linearly on d.

Experimental Validation

The state of the art in metric learning is dominated by algorithms designed to work in a purely supervised setting. Furthermore, most of them optimize a metric adapted to k-NN classification (e.g. LMNN, ITML), while our work is designed for finding a global linear . Lastly, we study the impact of the quantity of available labeled data on our method. We conduct the experimental study on 7 classic datasets taken from the UCI Machine Learning Repository [START_REF] Lichman | UCI Machine Learning Repository[END_REF], both binary and multi-class. Their characteristics are presented in Table 4.1. These datasets are widely used for metric learning evaluation.

Experimental setting

Compared methods In order to provide a comparison as complete as possible, we propose to study two main families of approaches1 :

1. Linear classifiers -in this family, we consider the following methods:

• BBS, corresponding to Problem (4.1) and discussed before;

• SLLC [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF], an extension of BBS in which a similarity is learned prior to be used in the BBS framework;

• JSL-diag, the joint learning framework proposed in this study learning a diagonal similarity;

• Linear SVM with L 2 regularization, which is the standard approach for linear classification.

2. Nearest neighbor approaches -in this family, we consider the methods:

• Standard 3-nearest neighbor classifier (3-NN) based on the Euclidean distance;

• ITML [START_REF] Davis | Information-Theoretic Metric Learning[END_REF], which learns a Mahalanobis distance that is used here in 3-NN classification;

• LMNN with a full matrix and LMNN with a diagonal matrix (LMNN-diag) [START_REF] Kilian | Fast Solvers and Efficient Implementations for Distance Metric Learning[END_REF][START_REF] Villani | Optimal Transport: Old and New[END_REF], also learning a Mahalanobis distance used here in 3-NN classification;

• LRML [START_REF] Steven | Semi-Supervised Distance Metric Learning for Collaborative Image Retrieval[END_REF][START_REF] Steven | Semi-Supervised Distance Metric Learning for Collaborative Image Retrieval and Clustering[END_REF]; LRML also learns a Mahalanobis distance used in 3-NN classifier, but in a semi-supervised setting. This method has the closest setting to JSL (even though one is learning a linear separator and the other only a distance).

All classifiers are used in their binary version, in a one-vs-all setting when the number of classes is greater than two. BBS, SLLC and JSL rely on the same classifier from Equation (4.2), even though learned in different ways. We solve BBS and JSL using projected gradient descent.

Data processing and parameter settings All features are centered around zero and scaled to ensure ||x|| 2 ≤ 1, as this constraint is necessary for some of the algorithms. We randomly choose 15% of the data for validation purposes, and another 15% as a test set.

The training set and the unlabeled data are chosen from the remaining 70% of examples not employed in the previous sets. In order to illustrate the classification using a restricted quantity of labeled data, the number of labeled points is limited to 5, 10 or 20 examples per class, as this is usually a reasonable minimum amount of annotation to rely on. The number of landmarks is either set to 15 points or to all the points in the training set (in which case their label is not taken into account). These two settings correspond to two practical scenarios: one in which a relatively small amount of unlabeled data is available, and one in which a large amount of unlabeled data is available. When only 15 unlabeled points are considered, they are chosen from the training set as the nearest neighbor of the 15 centroids obtained by applying K-means++ clustering with k = 15. All of the experimental results are averaged over 10 runs, for which we compute a 95% confidence interval. We tune the following parameters by cross-validation: γ, λ ∈ {10 -4 , . . . , 10 -1 } for BBS and JSL (λ only for the second), λ IT M L ∈ {10 -4 , . . . , 10 4 }, choosing the value yielding the best accuracy. For SLLC, we tune γ, β ∈ {10 -7 , . . . , 10 -2 }, λ ∈ {10 -3 , . . . , 10 2 }, as done by the authors, while for LRML we consider γ s , γ d , γ i ∈ {10 -2 , . . . , 10 2 }. For LMNN, we set µ = 0.5, as done in [START_REF] Kilian | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF].

Experimental results

Analysis of JSL We first study here the behavior of the proposed joint learning framework w.r.t. different families of similarities and regularization functions (choice of R and || • ||). In particular, we consider two types of similarity measures: bilinear (cosine-like)

similarities of the form K 1 M (x, x ) = x T Mx and similarities derived from the Mahalanobis distance K 2 M (x, x ) = 1 -(x -x ) T M(x -x ).
For the regularization term, R is either set to the identity matrix (JSL-I), or to the approximation of the Kullback-Leibler divergence (JSL-KL) discussed in Section 4.3. As mentioned above, these two settings correspond to different prior knowledge one can have on the problem. In both cases, we consider L 1 and L 2 regularization norms. We thus obtain 8 settings, that we compare in the situation where few labeled points are available (5 points per class), using a small amount (15 instances) of unlabeled data or a large amount (the whole training set) of unlabeled data. The results of the comparisons are reported in Tables 4.2 and 4.3.

As one can note from Table 4.2, when only 15 points are used as landmarks, K 2 M obtains better results in almost all of the cases, the difference being more important on Iris, Pima and Sonar. The noticeable exception to this better behavior of K 2 M is Wine, for which cosine-like similarities outperform Mahalanobis-based similarities by more than 10 points. A similar result was also presented in [START_REF] Qamar | Similarity Learning for Nearest Neighbor Classification[END_REF]. The difference between the use of the L 1 or L 2 norms is not as marked, and there is no strong preference for one or the other, even though the L 2 norm leads to slightly better results in average than the L 1 norm. Regarding the regularization matrix R, again, the difference is not strongly marked, except maybe on Sonar. In average, regularizing through the Kullback-Leibler divergence leads to slightly better results than regularizing through the identity matrix.

When all points are used as landmarks (Table 4.3), similar conclusions can be drawn regarding the similarity functions and the norms used. However, in that case, the regularization based on the identity matrix yields better results than the one based on the KL divergence. It is important to note also that the overall results are in general lower than the ones obtained when only 15 points are used as landmarks. We attribute this effect to the fact that one needs to learn more parameters (via α), whereas the amount of available labeled data is the same.

From the above analysis, we focus now on two JSL-diag based methods: JSL-15 with K 2 M , Figure 4.2: Classification accuracy (%) with confidence interval at 95% with 5 labeled points per class.

L 2 norm and R = KL when 15 points are used as landmarks, and JSL-all with K 2 M , L 2 norm and R = I when all the points are used as landmarks.

Comparison of the different methods We now study the performance of our method, compared to state-of-the-art algorithms. For this, we consider JSL-15 and JSL-all with 5, 10, respectively 20 labeled examples per class. As our methods are tested using the similarity based on the Mahalanobis distance, we use the Euclidean distance for BBS to ensure fairness. Figure 4.2 presents the average accuracy per dataset obtained with 5 labeled points per class. In this setting, JSL outperforms the other algorithms on 5 out of 7 datasets and has similar performances on one other. The exception is the Wine dataset, where none of the JSL settings yields competitive results. As stated before, this is easily explained by the fact cosine-similarities are more adapted for this dataset. Even though JSL-15 and JSL-all perform the same when averaged over all datasets, the difference between them is marked on some datasets: JSL-15 is considerably better on Iris and Sonar, while JSL-all significantly outperforms JSL-15 on Ionosphere and Liver. Averaged over all datasets (Table 4.4), JSL obtains the best performance in all configurations with a limited amount of labeled data, which is particularly the setting that our method is designed for. The values in bold are significantly better than the rest of their respective columns, confirmed by a one-sided Student t-test for paired samples with a significance level of 5%.

Impact of the amount of labeled data As an illustration of the methods' behavior when the level of supervision varies, Figure 4.3 presents the accuracies on two representative datasets, Ionosphere and Pima, with an increasing number of labeled examples. In both cases, the best results are obtained by JSL (and more precisely JSL-15) when less than 50% of the training set is used. This is in agreement with the results reported in Table 4.4.

The results of JSL are furthermore comparable only to BBS for the Pima dataset. Lastly, the accuracy of JSL improves slightly when adding more labeled data, and the results on the whole training set are competitive w.r.t. the other algorithms.

Conclusion

In this chapter, we have studied the problem of learning similarities in the situation where few labeled (and potentially few unlabeled) examples are available. To do so, we have developed a semi-supervised framework extending the ( , γ, τ )-good of Balcan et al. (2008b), in which the similarity function and the classifier are learned at the same time.

To our knowledge, this is the first time that such a framework is provided. The joint learning of the similarity and the classifier enables one to benefit from unlabeled data for both the similarity and the classifier. Our framework is generic and can be used with many different similarity functions and regularizers, some of which are able to provide sparsity for the learned metric in addition to that of the classifier. As JSL optimizes the ( , γ, τ )-goodness of the learned similarity, it also benefits from the guarantees of this framework, i.e. the bound on the true error of the linear classifier. We have also showed that the proposed method was theoretically well-founded through the analyses based on algorithmic robustness and Rademacher complexity, each resulting in a bound on the generalization error of the learned parameters. Lastly, the experiments we have conducted on standard metric learning datasets show that our approach is indeed well-suited for learning a diagonal metric from few labeled data, and outperforms state-of-the-art metric learning approaches in that situation.

Future work could cover a kernelized version of our technique to learn more efficient similarities and classifiers in a nonlinear feature space, as well as learning local metrics and a combination of them in a coherent framework. One could also consider introducing nonlinearity in JSL through the choice of a nonlinear similarity function. In the case of JSL, we have used the classic algorithm K-means to choose the landmarks that are used for the construction of the features space. An interesting line of research could be to analyze multiples heuristics for landmarks selection, as criteria different from data density might yield better performance.

and could be avoided by choosing a different class of functions. Moreover, the subject of learning custom metrics for time series has been addressed by adapting standard metric learning solutions to incorporate the time dimension (e.g. LMNN (Weinberger & Saul, 2009), ITML [START_REF] Davis | Information-Theoretic Metric Learning[END_REF]). This often implies that the optimal DTW alignment has to be computed for all pairs of points, but considering the quadratic complexity of this procedure, the final computational cost is elevated. Additionally, the theoretical foundation of metric learning for time series classification has never been studied.

In this chapter, we address the limitations of state of the art methods by introducing Similarity Learning for Time Series (SLTS). We place ourselves once more in the framework of ( , γ, τ )-good similarity functions. Our approach is to consider the optimal DTW alignment under a standard metric, but only w.r.t. a set of landmarks of limited size.

The formulation we propose is convex and directly optimizes the ( , γ, τ )-goodness of a bilinear similarity based on the optimal alignments, thus being able to guarantee its performance in linear classification. Our setting is not limited to the similarity function that we propose, but can be adapted to other forms of metrics. We provide a comprehensive theoretical analysis of SLTS based on the uniform stability framework. By only being able to incorporate strongly convex regularizers, the uniform stability is less general than algorithmic robustness or Rademacher complexity, but allows the derivation of tighter bounds. This is necessary for SLTS, as the method deals with complex data, which has an additional time dimension. The theoretical study in this chapter results in the derivation of a generalization bound for the learned metric. To our knowledge, SLTS is the first metric learning approach for multivariate time series coming with theoretical guarantees. The experiments we perform cover multiple aspects. We show examples of visualizations of the similarity space to prove that the learned metric has the capacity to discriminate classes. The comparison against state of the art approaches proves that SLTS is efficient and obtains good performance. We additionally study and test diverse heuristics for choosing the set of landmarks on which the construction of the similarity space is based.

Note that an approach similar to SLTS has been proposed in [START_REF] Bellet | Learning Good Edit Similarities with Generalization Guarantees[END_REF] for the problem of learning a similarity for sequence alignment. More precisely, their purpose is to learn the cost matrix necessary for computing the edit distance, i.e. the script of operations which transform a string into another. Computing the DTW for time series is equivalent to determining the Levenshtein distance [START_REF] Levenshtein | Binary Codes Capable of Correcting Deletions, Insertions, and Reversals[END_REF] for strings, as both methods are based on cost matrices and dynamic programming. Similarly to [START_REF] Bellet | Learning Good Edit Similarities with Generalization Guarantees[END_REF], our theoretical results are derived using uniform stability. However, two significant differences distinguish the approaches. First, our problem is more complex: we are considering multiple features, while their case is the equivalent of univariate time series. Second, concerning the generalization bound, our case is tighter, because our bound does not depend on the length of time series or of the alignment, while they depend on the squared length of the alignment.

The rest of this chapter is organized as follows. Section 5.2 contains the main formulation of SLTS. We start by introducing the similarity function that we propose to learn for time series, before showing how to learn it while maximizing its ( , γ, τ )-goodness. Section 5.3 features a theoretical analysis of SLTS based on the framework of uniform stability, which leads to the derivation of a generalization bound. In Section 5.4, we present an experimental study proving the advantages of SLTS, as well as an extended comparison to state of the art methods. We conclude our contribution in Section 5.5, where we also present future directions of research.

5.2 Learning ( , γ, τ )-Good Similarities for Time Series

This section presents a novel method for learning temporal similarity functions based on the ( , γ, τ )-good framework. We start by defining the bilinear similarity for multivariate time series, which takes into account an alignment. Then, we present our convex formulation for learning it, while improving its goodness for linear classification.

We start by making the notations that will be used throughout this section. Let A ∈ R t A ×d be a multivariate time series of length t A and dimension d. We denote by X the space of all time series with d features, but of different (finite) lengths. Now consider the following binary classification problem: we are given labeled multivariate time series (A, y) drawn from a distribution P over X × {+1, -1}, possibly of different lengths, but of same dimension d. Without loss of generality, we consider each time series to be normalized as

a i 2 = 1, i ∈ {1 . . . t A }, for all A ∈ X .
The results that we develop in the rest of this chapter hold for bounded multivariate time series in general, up to a normalization factor.

Bilinear Similarity for Time Series

We now introduce the bilinear similarity function that will be used in SLTS. For a pair of time series A and B both from X , let C M (A, B) ∈ R t A ×t B be a pairwise matrix of the costs of aligning a time moment in A to one in B under the metric parameterized by the matrix M. As we use a similarity function, C M (A, B) represents the affinity scores that we want to maximize: the higher the score, the more the two time moments are similar. We refer to the rows of A as a 1 , . . . , a t A and those of B as b 1 , . . . , b t B . We will focus on a bilinear similarity, where the affinity between time moment i from series A and time moment j from series B is expressed as:

C M (A, B) i,j = a T i • M • b j , (5.1)
where M ∈ R d×d is the matrix parameterizing the metric. For the pair of indices i and j, the affinity is equivalent to computing the generalized cosine similarity, as a i and b j are already normalized. The overall affinity matrix can be written as:

C M (A, B) = A • M • B T .
C M can be used to compute the optimal alignment between two time series using DTW. Given this affinity matrix, let π AB be an alignment between A and B of length t AB . Recall that, following our definition of alignment between time series, π AB contains the pairs of indices from A and B respectively representing the time moments that are aligned. Now let us rewrite the alignment as a binary matrix Y ∈ {0, 1} t A ×t B encoding it: Y ij A,B = 1 if the pair of indices (i, j) is part of π AB , and zero otherwise. The matrix Y A,B thus contains t AB non-zero values. Computing the score of aligning A and B from the affinity matrix and the alignment can be written as the following similarity function:

K M (A, B) = tr(C M (A, B) T • Y AB )/t AB = tr(B • M T • A T • Y AB )/t AB .
The previous equation sums the costs of from C M (A, B), but only for the pairs of points that are aligned by Y AB . When computing the product between the affinity matrix and the alignment, the scores of the pairs of points that are aligned end up on the main diagonal of the resulting matrix. Applying the trace operator sums only these diagonal values, while discarding the others. As the value of the similarity is cumulative, we normalize it w.r.t. the length of the alignment in order to remove the bias created by very long alignments.

To compute K M , we will not consider the optimal alignment with respect to M, which would make it sensitive to changes in the similarity parameters. Instead, we will compute it through DTW using the affinity matrix in Equation (5.1) and replacing M with the identity matrix. Determining C I (A, B) is thus equivalent to computing the scalar product between all combinations of time moments between A and B.

Using K M as similarity function to compare multivariate time series allows us to take advantage of the ideal alignment, while considering an improved weighting of the features and cross-features for each time moment. Note that a bilinear form has the capacity to compare time series that have a different number of features, provided that the shape of the matrix M is adapted. An important property is that the metric matrix M does not have to be PSD nor symmetric. Moreover, the similarity function K M is linear in M, meaning that it can be optimized directly. We shall now discuss a method for learning M from data.

Learning Good Similarities

Our objective is to learn the matrix M that parameterizes the similarity function K M for usage in classification. To this end, a labeled training set S of m time series {(A i , y i )} m i=1 drawn accordingly to P is available, together with a set L of n landmarks {(B j , y j )} n j=1 coming from the same distribution. When optimizing the goodness criterion, we do so with respect to the set of landmarks L, which we suppose fixed. Two heuristics for choosing them from data are discussed in the experiments (Section 5.4). As opposed to the previous chapter, the landmarks are this time labeled, and their class information will be used to create positive and negative pairs over the whole training set S.

We want to optimize the ( , γ, τ )-goodness of the proposed similarity function as presented in Definition 4.3. Rewriting its first condition for our problem yields:

E (A,y) 1 -E (B,y ),R(B) yy K M (A, B))|R(B) /γ + ≤ .
Unfortunately, we do not have access to the expected values. We propose to estimate its empirical value and improve it instead in a regularized risk minimization setting. First, the empirical loss suffered by one example (A, y) is:

(M, (A, y), L) =   1 - 1 nγ (B,y )∈L yy K M (A, B)   +
Learning the similarity that satisfies Definition 4.3 is equivalent to learning the entries of the matrix M that parameterizes it and is done by solving the following optimization problem over M:

min M 1 m (A,y)∈S   1 - 1 nγ (B,y )∈L yy K M (A, B)   + + λ M 2 F , (5.2)
where λ is the regularization parameter. Tuning it controls the trade-off between fitting the data and limiting the complexity of the hypothesis. In order to avoid overfitting, the objective function is regularized with the squared Frobenius norm of the matrix M. This norm allows to control the complexity of M in a loose way, without strongly pushing its entries to zero. Using this regularizer will allow us to provide theoretical guarantees for the proposed approach through uniform stability. Notice that the similarity function K M is linear in M, making the whole formulation convex. Problem (5.2) is a quadratic program (QP) and can easily be solved. We call the proposed method Similarity Learning for Time Series (SLTS). After solving Problem (5.2), K M is plugged in Equation (4.1) in order to learn the linear separator α.

SLTS is different from the standard metric learning setting in that it only computes similarities with respect to chosen landmarks, not the entire training set. Moreover, the constraints generated this way over pairs of points do not have to be entirely satisfied, but only on average for each training point. The total number of constraints generated is linear in the size of the dataset, not quadratic, as it is the case with pairs. Having a formulation based on landmarks also implies that the optimal alignment based on DTW only needs to be computed for the data points with respect to the set of landmarks. As computing DTW is expensive (recall its quadratic complexity in the lengths of the time series), the lower the number of landmarks, the faster the computation. This is a major advantage of our approach when compared to classic methods like k-NN and SVM, which have to compute the entire empirical similarity map for all the pairs of points in the dataset. When fixing the number of landmarks to a value that is much smaller than the size of the dataset and independent of it, the complexity of computing all the similarity values for SLTS is linear in the size of the dataset, while for k-NN and SVM it is quadratic.

Theoretical Guarantees

In this section, we present a theoretical analysis of our similarity learning approach based on the notion of uniform stability [START_REF] Bousquet | Stability and Generalization[END_REF]. First, we prove that SLTS is stable, property that we then use to derive a consistency bound for the metric. The main result in this section is presented in Theorem 5.7. We conclude the analysis by a discussion on the main properties of the bound.

Learning the metric by solving Problem (5.2) places our approach in the framework of ( , γ, τ )-good similarity functions, which enforces the theoretical guarantees from Theorem 4.4, that is a bounded error for the learned linear classifier with respect to the properties of K M . Additionally, the bound that we derive in this section on the consistency of M provides a link between the empirical loss we are minimizing under regularization in Equation ( 5.2) and the value we want to minimize, the true loss.

We make the following notations. According to Problem (5.2), SLTS minimizes the empirical risk of the learned matrix M over the whole training set S:

R S (M) = 1 m (A,y)∈S (M, (A, y), L).
Following Definition 4.3, the error that the algorithm should minimize is the true risk:

R P (M) = E (A,y)∼P [ (M, (A, y), L)] .
As the set of landmarks is fixed, we will omit it from the notation of the loss function to simplify the notation. SLTS does not use the classic setting for metric learning, based on pairs or triplets, but the fixed set of landmarks L. We are thus able to derive our theoretical results based on the standard setting for uniform stability, without its adaptation to pairs of points specific to metric learning (Jin et al., 2009). Recall the intuition behind uniform stability: an algorithm is stable if its outcome is not strongly influenced by small changes in the input. In this framework, the notion of marginal variation is conveyed by the replacement of one example by a new one from the same distribution P . We will denote by S i the training set obtained from S by changing the ith example. Similarly, let M i be the solution to SLTS when solved for training set S i . To prove the stability of SLTS, we first need to show that the considered loss function is bounded and l-lipschitz: the smaller l, the more stable the algorithm. We do so in Lemmas 5.1 and 5.2. All the proofs of the Lemmas in this section are presented in Appendix B.2.

Lemma 5.1 (Bound on the loss function). Let (A, y) be an example and M S the solution to Problem (5.2). Then

(M S , (A, y)) ≤ √ 2d γ √ λ .
In Chapter 4, we have used l-lipschitzness to bound the value of a similarity function w.r.t. the difference between two examples, in order to prove algorithmic robustness. For uniform stability, we prove the l-lispchitzness of the loss function w.r.t. the variation in M in the next lemma.

Lemma 5.2 (l-lipschitz continuity). Let M and M be two matrices and (A, y) an example. The loss function is l-lipschitz w.r.t. M with l = √ 2d γ , that is:

| (M, (A, y)) -(M , (A, y))| ≤ l M -M F .
The property of l-lipschitzness implies that the loss variation is proportional to the difference between M and M . The lemma we present next is used for the proof of the uniform stability of an algorithm. Consider the following notation for the objective function of SLTS (Equation (4.3)):

F S (M) := R S (M) + λ M 2 F .
Lemma 5.3. Let F S (•) and F S i (•) be the functions to optimize, M and M i their corresponding minimizers, and λ the regularization parameter used. Let ∆M = M -M i . Then we have, for t ∈ [0, 1]:

M 2 F -M -t∆M 2 F + M i 2 F -M i + t∆M 2 F ≤ 2lt λm ∆M F .
We can now prove that our approach has uniform stability. Proof. By setting t = 1 2 in Lemma 5.3, we obtain after some computations:

1 2 ∆M 2 F ≤ k λm ∆M F ,
which implies:

∆M F ≤ 2k λm .
Since our loss is l-lipschitz, we have:

| (M, (A, y)) -(M i , (A, y))| ≤ l ∆M F = 2l 2 λm
For this loss function, l = √ 2d γ , and setting κ = 4d γ 2 λ proves the lemma.

Having now shown the uniform stability of SLTS, we are ready to derive the generalization bound. For this, Lemmas 5.5 and 5.6 are necessary, providing bounds on quantities that intervene in the proof of the bound. Let E S = R P (M) -R S (M). We need to bound the quantities E S [E S ] and |E S -E S i |.

Lemma 5.5. For a learning method of estimation error E S and satisfying a uniform stability of κ/m, we have:

E S [E S ] ≤ κ m .
Lemma 5.6. For any metric M learned by solving Problem (5.2) on a training set S of m samples, and a loss function bounded according to Lemma 5.1, we have:

|E S -E S i | ≤ 2κ m + √ 2d mγ √ λ .
We can now present our main theoretical result, the consistency bound for the metric learned by SLTS:

Theorem 5.7 (Generalization bound using uniform stability). With probability 1δ, for any matrix M S learned by solving SLTS, we have:

R P (M S ) -R S (M S ) ≤ 4d γ 2 λm + 4d γ 2 λ + 1 γ 2d λ 2 log 2 δ m .
Proof. Using McDiarmid's inequality and Lemma 5.6, we can write:

Pr[E S -E[E S ] ≥ ] ≤ 2 exp   - 2 2 m 2κ+p m 2    . (5.3) By setting δ = 2 exp -2 2 m( 2κ+p m ) 2
in Inequality (5.3), we obtain:

= 2 m 4d γ 2 λ + 1 γ 2d λ 2 log 2 δ .
Then, with probability 1δ

E S = R P (M S ) -R S (M S ) < E[E S ] + R P (M S ) < R S (M S ) + κ m + .
Replacing the values of κ and in the previous inequality yields the bound.

The result from Theorem 5.7 shows the consistency of the proposed similarity learning approach. The bound converges with a standard rate of O(1/ √ m) in the number of samples. The tightness of the bound is inversely proportional to the size of the margin γ, supported also by the intuition that a better separation of the classes is more robust to new examples arriving, keeping the empirical error closer to the true error. An important feature of this bound is its independence from the lengths of the time series and of the alignments considered. As in practice these values can be elevated, introducing even a linear dependence on them would deteriorate the quality of the bound, making it loose and uninformative. Overall, the bound strongly resembles PAC bounds derived using the uniform stability for methods dealing with feature vectors, even though multivariate time series have an additional dimension. This means that SLTS does not suffer any penalty in its generalization capacity from working with multivariate time series instead of feature vectors. According to [START_REF] Verma | Sample Complexity of Learning Mahalanobis Distance Metrics[END_REF], the presence of the number of features d in the numerator of the bound is to be expected and shows that the approach may suffer from the curse of dimensionality. High values of d can be compensated by increasing either the size of S, or the value of the regularization parameter λ, present in the denominator. SLTS minimizes the empirical error of the ( , γ, τ )-good framework, thus reducing the error rate . By plugging the metric learned by SLTS into the framework, we obtain a guarantee on the performance of the associated linear classifier.

Experimental Validation

In this section, we present the results of the experiments conducted to evaluate the performance of the proposed method. In the first experiment, we show that learning the matrix M brings additional information w.r.t. a standard metric for linear classification.

We also analyze the influence of the number of landmarks on SLTS. The second study provides a comparison of SLTS to the state of the art algorithms while the third part illustrates the capacity of SLTS to learn a discriminant metric in the feature space created by the landmarks. The last experiment analyzes different heuristics for selecting landmarks and their impact on performance. We conduct the experimental study on multivariate time series datasets coming from UCI Machine Learning Repository [START_REF] Lichman | UCI Machine Learning Repository[END_REF], containing between 47-8800 instances. The characteristics of the datasets are presented in Table 5.1.

Experimental Setting

Compared methods We evaluate the following classic algorithms:

• Standard nearest neighbor classifier (1NN);

• Linear SVM under L 2 regularization;

• Linear classifier from Balcan et al. (2008b), presented in Equation (4.2) (called BBS from now on);

• LDMLT [START_REF] Mei | Learning a Mahalanobis Distance-Based Dynamic Time Warping Measure for Multivariate Time Series Classification[END_REF] with a nearest neighbor classifier; • SLTS, the similarity learning method proposed in this chapter, which is then used to learn a global linear classifier using the formulation in Balcan et al. (2008b).

Data processing and parameter settings

To propose a fair comparative study, all the methods that do not learn a metric use the proposed bilinear form as similarity function (with M set to the identity matrix) computed with the DTW alignment on the scalar product, that is K I based on C I . As confirmed in the following experiments, landmarks are randomly chosen for BBS and SLTS. We use all the classifiers in their binary version, in a one-vs-all setting. We recall here that each time moment is normalized to ensure the L 2 norm equals 1. For this experimental study, we have access to a standard training/test partitioning for Japanese vowels and Arabic digits datasets, while Robot execution failure (LP1-5) and Auslan are randomly split to 70% training/30% test data. For all datasets, we retain 30% of the training set for hyperparameter tuning. We perform experiments on 10 different splits and present the average result with a 95% confidence interval. Cross-validation is performed to tune the following parameters: C ∈ {2 -6 , . . . , 2 9 } for SVM, γ ∈ {10 -4 , . . . , 10 1 } for BBS, both when used separately or joint to SLTS, and λ ∈ {0.1, 1, 10} for SLTS.

Experimental Results

Behavior of SLTS and impact of the number of landmarks As stated before, BBS and SLTS use the same formulation to learn the linear classifier. In this first experiment, we (i) show that SLTS improves classification performance compared to BBS and (ii) analyze the influence of the quantity of landmarks on the accuracy obtained for BBS and SLTS. We consider the range of up to 50% of the size of the training set as landmarks for small datasets, or up to 100 landmarks for the others. The results of this study are presented in Figure 5.1. The accuracy of SLTS is almost always higher than that of BBS independently of the number of landmarks, showing the improvement that can be obtained through similarity learning. When a reasonable quantity of data is available (Figures 5.1(a)-5.1(c)), SLTS achieves a performance close to its best value even with a few landmarks. Our method thus performs well even with a low quantity of data, considerably reducing the computation time for learning the similarity. Overall, BBS has difficulties providing a good classifier based on a small number of landmarks, but the results of the method significantly improve with more landmarks. We explain the high variability of the results of BBS and SLTS on LP1-LP5 by the small sizes of the tasks. However, compared to LDMLT, SLTS is on a par on Japanese vowels, below on Auslan and Robot execution failure, and above on Arabic digits (a Student t-test on the average does not reveal any significant difference between the two methods). LDMLT relies on both a local method and a metric learned, which suggests again that learning a metric is beneficial on these datasets. This said, LDMLT learns a distance, whereas all the other methods rely on a similarity. The comparison between the two should thus be taken with caution as distances and similarities can yield very different results (Qamar & Gaussier, 2009a).

Visualization of the similarity space To illustrate the transformation induced in the feature space by learning the metric, we propose a visualization experiment on the Japanese vowels dataset using 10 landmarks chosen randomly. We compute the value of the similarity function K M for all the data w.r.t. the landmarks, first without metric learning (M = I), then with the metric learned for each of the 9 classes. In all the cases, we apply PCA [START_REF] Jolliffe | Principal Component Analysis[END_REF] to the values of the similarity function and plot the first two components. We thus obtain a 2D representation of the feature space, of which we present in Figure 5.2 the case of the initial feature space and that of the metric learned for the first three classes. In similarity space with no metric learning (Figure 5.2(a)), all the data points are mixed, independently of their label. In Figures 5.2(b)-5.2(d), each metric linearly separates the class it has learned to discriminate from the others. For the learned similarities, the first two components of PCA explain around 98% of the variance, while with no similarity learning this value is around 86%. This study proves that learning an ( , γ, τ )-good similarity function changes the representation space towards better class discrimination, making it suitable for learning a large margin linear separator.

Heuristics for choosing the landmarks We have previously assumed we have access to a set of landmarks for the construction of the feature space. We will now discuss two heuristics for choosing the most representative points in the training set as landmarks, before presenting experimental results concerning the performance of each of these methods. K-Medoids [START_REF] Kaufman | Clustering by Means of Medoids[END_REF]) is a classical clustering technique. The resulting medoids representing the clusters are points of the initial dataset, that will be subsequently used as landmarks. Dselect (Kar & Jain, 2011) was proposed as a landmarks selection algorithm which optimizes a criterion of diversity. Starting with a randomly chosen landmark, at each iteration the algorithm greedily adds to the set of landmarks the training point that is least similar to the ones already selected (see Algorithm 5.1). Note that for both selection heuristics the number of landmarks needs to be set in advance. Also, none of these methods exploits the information from the labels of the time series.

In the case where no prior information is available for the classification task, the set of landmarks can also be selected randomly from the training set, with the risk of relying upon non informative landmarks.

We now present in Tables 5.3 and 5.4 the classification results after learning the similarity with SLTS on landmarks selected using the presented heuristics. DSelect and KMedoids are compared against landmarks selected randomly as baseline, in order to determine if they are indeed informative. We perform these experiments on two small datasets, Japanese vowels and LP1. The mass of chosen landmarks is selected as a percentage of the total size of the training set and goes up to 50%. For Japanese vowels (Table 5.3), all three methods perform almost the same for all amounts of landmarks. DSelect reaches its best performance when the selected points represent 10-20% of the training set, while KMedoids works best around 30% mass of landmarks. Overall, DSelect and Random heuristics yield better performance than KMedoids. The results using Random show that SLTS can learn well ever when no computational effort is put into choosing the landmarks. In the case of LP1 (Table 5.4), and in contrast to the Japanese vowels dataset, the performance of all the heuristics improves when increasing the number of landmarks. The best results are obtained for 40% mass of landmarks in the case of DSelect and Random, and 50% for KMedoids. For this dataset, the results are less stable, inducing larger confidence intervals. For this reason, even though the best accuracy is attained by DSelect, its improvement over Random is not necessarily significant. KMedoids is this time also the least performant KMedoids and DSelect have by themselves a computational complexity that is not to be ignored when working on large datasets. Even so, their main disadvantage for time series is not the algorithmic complexity in itself, but the necessary precomputations. One needs to compute the value of the similarity function for all pairs of time series, including the alignment, in order to be able to apply these heuristics. This limitation goes directly against the main advantage of working with methods based on landmarks, like SLTS. In view of this aspect and the previous experimental results, we have only considered the Random heuristic when comparing SLTS against state of the art algorithms on bigger datasets.

Conclusion

The last contribution of this thesis addresses the problem of improving the performance when learning a global linear classifier for multivariate time series. In the present chapter, this problem was tackled by learning a bilinear similarity under the optimal alignment provided by DTW. SLTS is an efficient convex formulation which improves the ( , γ, τ )goodness of the similarity with respect to a set of landmarks. We thus obtain a global metric which integrates constraints from positive and negative pairs. We prove the uniform stability of our method, which allows us to derive a generalization bound for the similarity. This bound has a standard convergence rate when the size of the sample increases and the additional important advantage of being independent from the length of the time series, as well as the length of the alignment. SLTS is, to the best of our knowledge, the first approach to provide a consistency bound for the learned metric in the case of time series. The experimental study proves the usefulness of the ( , γ, τ )-good framework, as well as the importance of metric learning in this setting. We also presented experiments covering different heuristics for landmarks selection, proving that random selection provides a computationally cheap alternative without strongly degrading performance.

In SLTS, the parameters of the bilinear similarity are learned under the alignment computed by DTW using a standard similarity, with no parameters. An intuitive idea is to reconsider the optimal alignment and recompute it under the new metric. We have performed this step in hope of obtaining a new, better alignment that would improve classification performance. However, in practice, recomputing the alignment using the learned metric does not necessarily improve the results, even when multiple iterations of the two steps are performed (applying DTW and learning M). The intuition behind this behavior is that the learned matrix M is the solution to a convex problem which is parameterized by the initial optimal alignment. By changing the alignment, (i) M is no longer the solution to the problem and (ii) the new alignment is computed through a dynamic programming technique, not optimization, thus with no guarantees of minimizing the loss. A similar phenomenon was also reported in the recent work from [START_REF] Zhao | MetricDTW: Local Distance Metric Learning in Dynamic Time Warping[END_REF].

Future work could cover an extension to other similarity functions, including some based on the Mahalanobis distance, but without enforcing the PSD constraint. Provided the similarity function respects the necessary constraints, i.e. being bounded and l-lipschitz, the consistency bound of SLTS would be able to incorporate their properties directly.

Similarly, an interesting perspective would be to study the impact regularizers with different properties on the matrix M. For example, a sparsity-inducing norm would allow to automatically detect features that are not relevant, providing valuable information about the task at hand. This would impact SLTS with respect to the consistency bound for the metric. As mentioned previously, the framework of uniform stability can only be used with strongly convex regularizers. An equivalent PAC bound would have to be derived using an alternative framework, e.g. the Rademacher complexity.

We believe that a straightforward, but useful extension of SLTS should address learning multiple metrics. This idea is justified by the intuition that the metrics should be able to capture local temporal information: depending on the time moment, a different metric could be more appropriate. The current version of SLTS is unable to do so, as the same metric matrix is used for all time moments. Our theoretical results could be adapted to cover such a setting.

Chapter 6

Conclusion and Perspectives

In this thesis, we have given an overview of the state of development in metric learning for certain types of problems, while presenting their main limitations. We addressed a number of these limitations in our contributions, in a more general setting for feature vectors, as well as for structured data with a temporal dimension. An important focus was placed on the theoretical foundations guiding the proposals, as we believe guarantees of performance to be essential. When developing our methods, we have also tried to keep in mind the practical aspects that would make them usable.

Overall, we addressed the following limitations:

• The deficiency in theoretical results for metric learning: even though in recent years more studies have been concerned with developing theoretical analyses, two tendencies can be noticed: (i) some of these studies are only theoretical and (ii) overall, only a small number of the practical approaches in metric learning have addressed this question.

• The artificial constraints imposed on the learned metric: most methods enforce the PSD and symmetry properties, for feature vectors and time series alike, often because they learn a Mahalanobis distance. Instead, we have chosen to work with similarity functions that do not need these properties.

• The lack of results and methods in learning custom metrics for temporal data, especially for the most common type in real-world applications that is multivariate time series.

The first contribution was to propose JSL, a framework which allows to learn a similarity function at the same time as a global linear classifier. The method directly optimizes the ( , γ, τ )-goodness (Balcan et al., 2008b) of the similarity function, which is directly related to its performance in classification. An important characteristic of JSL deriving from this is its semi-supervised setting. It allows the method to take advantage of unlabeled data in a different way from most semi-supervised methods, that is by using it to construct the feature space where the data will be projected. The capacity to leverage unlabeled examples makes the proposed framework particularly adapted to the real-world setting where data annotation is expensive, and only a small number of labeled instances is available. To the best of our knowledge, our method is the first one to learn the metric and the classifier at the same time partly from unlabeled data. The generality of JSL lies in the fact that it can be instantiated with a broad range of similarity functions and regularizers, thus providing a way to solve problems with different properties. The general regularizer has the capacity to incorporate prior knowledge about the given task. We also propose an efficient method for solving the problem, which is convex under mild constraints for the similarity function.

From a theoretical standpoint, we analyze JSL through the perspective of two frameworks: the algorithmic robustness and the uniform convergence with Rademacher complexity. Both analyses yield generalization bounds for the learned similarity and classifier which hold for different similarity functions and provide information about them. The extensive experimental study shows that JSL achieves better performance than a large number of other methods. The source code for JSL is publicly available under GNU/GPL 2+ license1 .

Our second contribution focuses on a particular type of data, which are multivariate time series. We proposed to learn a bilinear similarity function for a classification task. Once again, we aimed at generalizing over kernel functions by relaxing the PSD constraint, while linking the properties of the similarity to its performance in classification. This was done by learning an ( , γ, τ )-good similarity based on the optimal alignment between time series computed through DTW. The problem, called SLTS, is formulated as a quadratic program, which can be solved efficiently. Working with time series is often computationally expensive, mostly because of the complexity of the data and DTW when computing the best alignment between pairs of points. We were able to reduce the number of similarity values and alignments to compute by basing the approach on landmarks (in the same sense as the ( , γ, τ )-good framework) and limiting their number, while also keeping alignments fixed. We established generalization guarantees for SLTS based on uniform stability, ensuring the consistency of the metric. The obtained bound is rather tight and independent from the lengths of the time series and the alignments, resembling similar bounds for feature vectors. The experimental study shows the good properties of the metric, as well as its performance when compared to standard methods. To the best of our knowledge, SLTS is the first method performing metric learning for multivariate time series which comes with such a theoretical analysis. The source code for solving SLTS is also publicly available under GNU/GPL 2+ license2 .

There are multiple interesting perspectives for extending the methods that we have proposed. One of them is to adapt them to learning multiple metrics, each one corresponding to a different region of the space. We believe that this direction can capture additional information in the data, as well as provide an implicit way of introducing nonlinearity. Note that the ( , γ, τ )-good framework includes a setting where multiple functions can be combined to obtain an overall metric that is also guaranteed to be good. Another possible extension is to adapt the proposed approaches to an online setting, where examples arrive one at a time. This would allow the methods to scale better. In practice, the first points received would be considered as landmarks for the learning process. For this setting, one could derive regret bounds with respect to the batch version.

From a theoretical standpoint, this thesis has analyzed the guarantees that can be obtained by a learned similarity function in linear classification. These results were derived based on the ( , γ, τ )-good theory. Unfortunately, this framework links similarity functions to the particular case of global linear classifiers. Considering that state of the art in metric learning, be it for feature vectors or time series, is oriented towards the k-NN classifier, it would be a major result to develop theoretical analysis frameworks or particular results for certain methods concerning this local classification rule. Some results have already been established for the online and batch settings by [START_REF] Qamar | Similarity Learning for Nearest Neighbor Classification[END_REF] based on the voted perceptron theory of [START_REF] Freund | Large Margin Classification Using the Perceptron Algorithm[END_REF].

Another promising avenue for research would be to explore settings that have not received much attention in metric learning, like unsupervised learning. This is a difficult problem, because the criterion the metric should optimize is not always evident, as is the case for performance measures as well. A first result using the uniform stability to derive theoretical guarantees for the general case of unsupervised learning algorithms was recently derived in Abou-Moustafa & Schuurmans (2015), paving the way for further research.

More precisely, they focus on applications for clustering and dimensionality reduction.

Unfortunately, their results depend on manually defining a criterion of evaluation for each application.

|K We now prove that K 1 M is (0,1)-admissible. It is straightforward to bound its absolute value:

1 M (x, x ) -K 1 M (x , x )| = (x T Mx ) -(x T Mx ) = (x -x ) T Mx ≤ ||x -x || 2 • ||Mx || 2 (B.
|K 1 M (x, x )| = |x T Mx | ≤ x x T 2 M F (B.5)
We get Inequality (B.5) by applying the Cauchy-Schwarz inequality.

Properties of the similarity function

K 2 M . Recall that K 2 M (x, x ) = 1-(x-x ) T M(x-x ).
As in the case of similarity K 1 M , we bound the following difference: We now prove that K 2 M is (1,4)-admissible.

K 2 M (x, x ) -K 2 M (x , x ) = 1 -(x -x ) T M(x -x ) -1 + (x -x ) T M(x -x ) = (x -x ) T M(x -x ) -(x -x ) T M(x -x ) + (x -x ) T M(x -x ) -(x -x ) T M(x -x ) = (x -x ) T M(x -x) + (x -x) T M(x -x ) ≤ (x -x ) T M(x -x) + (x -x) T M(x -x ) ≤||x -x || 2 • ||Mx -Mx|| 2 + ||x -x|| 2 • ||Mx -Mx || 2 (B.6) ≤||x -x || 2 • (||x || 2 + ||x|| 2 ) + ||x -x|| 2 • (||x|| 2 + ||x || 2 ) (B.7) ≤4||x -x ||. (B.
|K 2 M (x, x )| = |1 -(x -x ) T M(x -x )| ≤ 1 + (x -x ) T M(x -x ) ≤ 1 + x -x 2 2 M F (B.9) ≤ 1 + 4 x x T 2 M F (B.10)
We get Inequality (B.9) by applying the Cauchy-Schwarz inequality. As the examples are normalized x 2 ≤ 1, we obtain Inequality (B.10).

Properties of the similarity function

K 3 M . Recall that K 3 M (x, x ) = exp -(x-x ) T M(x-x ) 2σ 2
. This proof is similar to the one for the previous similarities. We bound the following difference:

K 3 M (x, x ) -K 3 M (x , x ) = exp - (x -x ) T M(x -x ) 2σ 2 -exp - (x -x ) T M(x -x ) 2σ 2 ≤ exp 1 2σ 2 -exp -1 2σ 2 • (x -x ) T M(x -x ) 2σ 2 - (x -x ) T M(x -x ) 2σ 2 (B.11) = 1 2σ 2 exp 1 2σ 2 -exp -1 2σ 2 • (x -x ) T M(x -x ) -(x -x ) T M(x -x ) + (x -x ) T M(x -x ) -(x -x ) T M(x -x ) = 1 2σ 2 exp 1 2σ 2 -exp -1 2σ 2 • (x -x ) T M(x -x) + (x -x) T M(x -x ) ≤ 1 2σ 2 exp 1 2σ 2 -exp -1 2σ 2 • (x -x ) T M(x -x) + (x -x) T M(x -x ) ≤ 1 2σ 2 exp 1 2σ 2 -exp -1 2σ 2 • ( x -x 2 • ||Mx -Mx|| 2 + x -x 2 • Mx -Mx 2 ) (B.12) ≤ 1 2σ 2 exp 1 2σ 2 -exp -1 2σ 2 • ( x -x 2 • ( Mx 2 + Mx 2 ) + x -x 2 • ( Mx 2 + Mx 2 )) (B.13) ≤ 1 2σ 2 exp 1 2σ 2 -exp -1 2σ 2 • ( x -x 2 • ( x 2 + x 2 ) + x -x 2 • ( x 2 + x 2 )) (B.14) ≤ 1 2σ 2 exp 1 2σ 2 -exp -1 2σ 2 4 x -x (B.15) = 2 σ 2 exp 1 2σ 2 -exp -1 2σ 2 x -x .
Inequality (B.11) is due to the l-lipschitzness of the exponential function on the range We now prove that K 3 M is exp(-2/σ 2 ), 0 -admissible:

[ -1 2σ 2 , 1 2σ
|K 3 M (x, x )| = exp - (x -x ) T M(x -x ) 2σ 2 ≤ exp -4 x T x 2 M F 2σ 2 (B.16) = d i=1 d t=1   t A j=1 t B k=1 a ij y jk b kt   2 = d i=1 d t=1   2 t A j=1 t B k=1 t A j =1 t B k =1 (a ij y jk b kt )(a ij y j k b k t ) - jk (a ij y jk b kt ) 2   ≤ i,t 2 j,k j ,k |(a ij y jk b kt )(a ij y j k b k t )| = 2 j,k y jk j ,k y j k + i,t a ij a ij b kt b k t ≤ 2t 2 AB | i a ij a ij t b kt b k t | = 2t 2 AB max i a ij i |a ij | max t b kt t |b kt | = 2t 2 AB max i a ij a i 1 max t b kt b k 1 ≤ 2t 2 AB √ d a i 2 √ d b k 2 ≤ 2t 2 AB • d = t AB √ 2d.
We are now able to present the proof of Lemma 5.1:

Proof of Lemma 5.1. Proof of Lemma 5.3. This proof is similar to the one of Lemma 20 in [START_REF] Bousquet | Stability and Generalization[END_REF]. Consider the following notation for the objective function of SLTS (Equation (4.3)):

(M, (A, y)) =   1 - 1 n (B,y )∈L yy K M (A, B)/γ   + ≤ y 1 n (B,y )∈L y K M (A, B)/γ (B.20) ≤ 1 n (B,y )∈L y K M (A, B)/γ (B.21) ≤ 1 nγ (B,y )∈L tr(M T A T Y AB B)/t AB ≤ 1 nγ (B,y )∈L 1 t AB M F A T Y AB B F ≤ 1 nγ (B,y )∈L 1 t AB 1 √ λ t AB √ 2d (B.22) ≤ √ 2d γ √ λ .
| (M, (A, y)) -(M , (A, y))| =   1 - 1 n (B,y )∈L ll K M (A, B)/γ   + -   1 - 1 n (B,y )∈L ll K M (A, B)/γ   + ≤ 1 n (B,y )∈L ll K M (A, B)/γ - 1 n (B,y )∈L ll K M (A, B)/γ (B.23) = 1 nγ (B,y )∈L y (K M (A, B) -K M (A, B)) ≤ 1 nγ (B,y )∈L |K M (A, B) -K M (A, B)| (B.24) = 1 nγ (B,y )∈L tr((M -M ) T • A T • Y AB • B)/t AB ≤ 1 nγ (B,y )∈L 1 t AB ||(M -M ) T • A T • Y AB • B)|| 1 (B.25) ≤ 1 nγ M -M F (B,y )∈L 1 t AB A T • Y AB • B F (B.26) ≤ √ 2d γ M -M F . (
F S (M) := R S (M) + λ M 2 F .
R S (•) is a convex function, thus for all t ∈ [0, 1], we have:

R S i (M -t∆M) -R S i (M) ≤ t(R S i (M i ) -R S i (M)), (B.28) R S i (M i + t∆M) -R S i (M i ) ≤ t(R S i (M) -R S i (M i )). (B.29)
By summing Inequalities (B.28) and (B.29) we obtain the following:

R S i (M -t∆M) -R S i (M) + R S i (M i + t∆M) -R S i (M i ) ≤ 0. (B.30)
Since M and M i are respectively the minimizers of F S (•) and F S i (•), we can write:

R S (M) -R S (M -t∆M) ≤ 0, (B.31) R S i (M i ) -R S i (M i -t∆M) ≤ 0. (B.32)
By summing Inequalities (B.31) and (B.32) we obtain:

F S (M) -F S (M -t∆M) + F S i (M i ) -F S i (M i -t∆M) ≤ 0 R S (M) -R S (M -t∆M) + λ||M|| 2 F -λ||M -t∆M|| 2 F +R S i (M i ) -R S i (M i + t∆M) + λ||M i || 2 F -λ||M i + t∆M|| 2 F ≤ 0 (B.33)
We can now sum Inequalities (B.30) and (B.33):

R S (M) -R S (M -t∆M) + λ||M|| 2 F -λ||M -t∆M|| 2 F +R S i (M i ) -R S i (M i + t∆M) + λ M i 2 F -λ M i + t∆M 2 F ≤ 0
From the previous inequality, we can write:

λ M 2 F -λ M -t∆M 2 F + λ M i 2 F -λ M i + t∆M 2 F ≤ Q, (B.34) with Q = R S i (M) -R S (M) + R S (M -t∆M) -R S i (M -t∆M).
We now need to bound the previous quantity Q:

Q ≤ 1 m (A,y)∈S i (M, (A, y)) - (A,y)∈S (M, (A, y)) + (A,y)∈S (M -t∆M, (A, y)) - (A,y)∈S i (M -t∆M, (A, y)) = 1 m (M, (A i , y i )) -(M, (A, y)) + (M -t∆M, (A, y)) -(M -t∆M, (A i , y i )) (B.35) ≤ 1 m (M, (A i , y i )) -(M -t∆M, (A i , y i )) + | (M -t∆M, (A, y)) -(M, (A, y))| (B.36) ≤ 1 m (l M -M + t∆M F + l M -t∆M -M F ) (B.37) = 2lt m ∆M F
On line (B.35) we keep the terms that differ in the previous sums. We get Inequality (B.36) from triangle inequality, while (B.37) comes from the l-lipschitzness of the loss function (Lemma 5.2). Combining the bound on Q with Equation (B.34) proves the lemma.

Proof of Lemma 5.5.

E S [E S ] ≤ E S [E (A,y) [ (M, (A, y))] -R S (M)] ≤ E S,(A,y)   (M, (A, y)) - 1 m (A i ,y i )∈S (M, (A i , y i ))   ≤ E S,(A,y)   1 m (A i ,y i ) ( (M, (A, y)) -(M, (A i , y i )))   ≤ E S,(A,y)   1 m (A i ,y i ) (M i , (A i , y i )) -(M, (A i , y i ))   (B.38) ≤ κ m . (B.39)
Inequality (B.38) comes from the fact that changing one point with another from the same distribution does not affect the expected value, while Inequality (B.39) results from applying triangle inequality and uniform stability (Theorem 5.4).

Proof of Lemma 5.6. • Le traitement du signal (par exemple la reconnaissance et synthèse de la parole ou l'identification vocale) ;

|E S -E S i | =|R P (M) -R S (M) -R P (M i ) + R S i (M i )| =|R P (M) -R S (M) -R P (M i ) + R S i (M i ) -R S (M i ) + R S (M i )| ≤|R P (M) -R P (M i )| + |R S (M i ) -R S (M)| + |R S i (M i ) -R S (M i )| (B.40) ≤E (A,y) [| (M, (A, y)) -(M i , (A, y))|] + |R S (M i ) -R S (M)| + |R S i (M i ) -R S (M i )| (B.41) ≤ κ m + |R S (M i ) -R S (M)| + |R S i (M i ) -R S (M i )| (B.42) ≤ κ m + 1 m (A,y)∈S (M i , (A, y)) -(M, (A, y)) +|R S i (M i ) -R S (M i )| ≤ κ m + κ m + |R S i (M i ) -R S (M i )| (B.43) = 2κ m + 1 m | (M i , (A i , y i )) -(M i , (A, y))| (B.44) ≤ 2κ m + 1 m | (M i , (A i , y i ))| (B.45) ≤ 2κ m + √ 2d mγ √ λ (B.
• La recherche d'information (par exemple les moteurs de recherche ou les systèmes de recommandation) ;

• Les véhicules et robots autonomes (par exemple les drones ou les voitures autodirigées) ;

• La linguistique informatique ;

• La biologie et la génétique ;

• Le diagnostic médical. Résumé de la thèse Cette thèse est organisée comme suit.

• Le Chapitre 2 présente les notions relatives à l'apprentissage statistique qui sont nécessaires pour le reste de ce document. Nous commençons par une présentation formelle de l'apprentissage supervisé, puis donnons quelques exemples d'algorithmes d'apprentissage classiques, suivis des cadres théoriques de l'apprentissage pour obtenir des garanties de généralisation.

• Le Chapitre 3 est consacré aux métriques en général et à l'apprentissage de métriques en particulier. Après avoir présenté un certain nombre de mesures standard pour les vecteurs de features et les séries temporelles, nous fournissons une étude de l'apprentissage de métriques (semi)-supervisé pour ces types de données. Ce chapitre explique plus en détail les limites qui ont déterminé l'orientation de nos contributions.

• Le Chapitre 4 présente nos contributions sur l'apprentissage des métriques pour les vecteurs de features. Nous introduisons un cadre général appelé JSL (pour Joint Similarity Learning en anglais) pour apprendre simultanément une fonction de similarité et un classifieur linéaire global. JSL est capable d'intégrer des contraintes globales basées sur des exemples non-étiquettées que l'on appelle des landmarks.

Cette propriété permet à notre cadre de s'adapter au contexte particulier dans lequel seulement une petite quantité de données étiquetées est disponible. La formulation optimise les paramètres du cadre ( , γ, τ )-bon de la similarité, ce qui assure sa performance en classification. JSL est convexe et peut être résolu efficacement sous de légères contraintes sur la fonction de similarité. Nous dérivons des garanties théoriques pour JSL en utilisant deux cadres différents: la robustesse algorithmique et la convergence uniforme basée sur la complexité de Rademacher. Les expériences comparent JSL à une vaste gamme de méthodes de l'état de l'art et prouvent son efficacité.

• Le Chapitre 5 rassemble nos contributions sur l'apprentissage de métriques pour les données temporelles en introduisant SLTS (pour Similarity Learning for Time Series en anglais). Nous proposons d'apprendre une fonction de similarité bilinéaire pour des séries temporelles multivariées basée sur les alignements optimaux. La similarité apprise est utilisée par la suite pour la classification linéaire. Le problème que nous résolvons est convexe et facile à résoudre. En utilisant le cadre de la stabilité uniforme, nous fournissons les premières garanties théoriques sous la forme d'une borne de généralisation pour la similarité apprise. De plus, en optimisant le critère du cadre ( , γ, τ )-bon de la métrique, nous fournissons des garanties concernant sa performance pour la classification linéaire. L'étude expérimentale montre que l'approche proposée est efficace, tout en fournissant des classifieurs parcimonieux.

• Le Chapitre 6 conclut notre travail et discute des pistes pour des travaux futurs possibles.

Notations Le Tableau C.1 explique les notations utilisées tout au long de cette thèse. Chapter 5 Le déformation temporelle dynamique (DTW, pour Dynamic Time Warping en anglais) est l'algorithme le plus connu pour mesurer la similarité entre deux séries temporelles en passant par l'alignement optimal entre elles. Malheureusement, comme nous l'avons vu dans le Chapitre 3, peu d'efforts de recherche ont été faits pour l'adapter à des séries temporelles multivariées et encore moins pour l'améliorer en apprenant. Dans ce chapitre, nous proposons une nouvelle méthode pour l'apprentissage de similarités basées sur DTW, afin d'améliorer la classification des séries temporelles. Dans cette contribution, nous utilisons également le cadre des similarités ( , γ, τ )-bonnes (Balcan et al., 2008b), fournissant des garanties sur la performance d'un classifieur linéaire construit à partir de la métrique apprise. Montrer que notre méthode a une stabilité uniforme nous permet de dériver la première borne de généralisation d'une métrique apprise à partir de données temporelles. Nous effectuons des expériences sur des jeux de données temporelles multivariées des applications réelles, en comparant notre méthode aux approches de l'état de l'art. L'étude expérimentale montre que la méthode proposée est efficace, tout en fournissant des classifieurs parcimonieux.

Résumé des chapitres

Conclusion

Dans cette thèse, nous nous sommes intéréssés à l'état du développement de l'apprentissage de métriques pour certains types de problèmes, tout en présentant leurs principales limitations. Nous avons abordé un certain nombre de ces limitations dans nos contributions. Tout d'abord, sur les vecteurs de features dans un cadre général, puis nous avons exploré ces problématiques sur les données structurées avec une dimension temporelle. Un accent important a été mis sur les fondements théoriques qui guident les propositions, car nous estimons que les garanties de performance sont essentielles. Lors de l'élaboration de nos méthodes, nous avons également essayé de garder à l'esprit les aspects pratiques qui les rendraient utilisables.

Dans l'ensemble, nous avons abordé les limitations suivantes :

• Le manque de résultats théoriques pour l'apprentissage de métriques : bien que ces dernières années un plus grand nombre d'études aient porté sur l'élaboration d'analyses théoriques, deux tendances peuvent être observées : (i) certaines de ces études ne sont que théoriques et (ii) dans l'ensemble, seul un petit nombre des approches pratiques du domaine ont abordé cette question.

• Les contraintes artificielles imposées à la métrique apprise: la plupart des méthodes imposent les propriétés de PSD et de symétrie souvent parce qu'ils apprennent une distance de Mahalanobis. Au lieu de cela, nous avons choisi de travailler avec des fonctions de similarité qui n'ont pas besoin de ces propriétés.

• Le manque de résultats et de méthodes dans l'apprentissage de métriques pour les séries temporelles, en particulier pour le type le plus courant dans les applications réelles, les séries temporelles multivariées.

La première contribution a été de proposer JSL, un cadre qui permet d'apprendre une fonction de similarité en même temps qu'un classifieur linéaire global. La méthode optimise directement une fonction de similarité ( , γ, τ )-bonne (Balcan et al., 2008b)

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Learning Good Hypotheses . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Loss Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Standard Classification Algorithms . . . . . . . . . . . . . . . . . . . . . . 2.6 Algorithms Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Generalization Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Review of Metric Learning 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Metric Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Joint Similarity and Classifier Learning for Feature Vectors 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 ( , γ, τ )-Good Similarities Framework . . . . . . . . . . . . . . . . . . . . . 4.3 Joint Similarity and Classifier Learning . . . . . . . . . . . . . . . . . . . . 4.4 Theoretical Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Learning a Diagonal Metric . . . . . . . . . . . . . . . . . . . . . . . . . . iii CONTENTS 4.6 Experimental Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Learning Similarities for Time Series Classification 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Learning ( , γ, τ )-Good Similarities for Time Series . . . . . . . . . . . . . . 5.3 Theoretical Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Experimental Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . of Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Proofs of Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

+

  Set of d-dimensional real-valued vectors R d×d Set of d × d real-valued matrices S d Cone of symmetric PSD d × d real-valued matrices S An arbitrary set |S| The cardinality of S S n

Figure 2 . 1 :

 21 Figure 2.1: Loss functions for binary classification.

Figure 2 . 3 :

 23 Figure 2.3: Example of 3-NN classifier using the Euclidean distance. Here, the new instance (cross) will be assigned to the circles class.

Figure 2 . 4 :

 24 Figure2.4: VC dimension of a linear classifier in the plane. A line can shatter three points with all possible labeling combinations (on the left, three out of eight combinations), but it cannot shatter all sets of four points (on the right). The VC dimension of a linear separator in the plane is 3.

Figure 3 . 1 :

 31 Figure 3.1: Unit circles for various values of p in Minkowski distances.

Figure 3 .

 3 Figure 3.1 shows unit circles with various values of p.

Figure 3

 3 Figure 3.2: Metric behavior for the Euclidean distance (left) and the cosine similarity (right).

Figure 3 . 3 :

 33 Figure 3.3: Example of dynamic time warping alignment.

Figure 3 . 4 :

 34 Figure 3.4: Global constraints for DTW.

Figure 3 . 5 :

 35 Figure 3.5: Intuition behind metric learning.

Figure 4 . 1 :

 41 Figure 4.1: Example of ( , γ, τ )-good similarity function. Left side: the original data in the input space is not separable; right side: the similarity projection space, where the separator classifies all points correctly. Reasonable points are outlined in black.

  Theorem 4.2.(Balcan et al., 2008b) Let K be an ( , γ, τ )-good similarity function for a learning problem P . Let L = {x 1 , . . . , x d } be a (potentially unlabeled) sample of d = 2 τ log(2/δ) + 8 log(2/δ) γ 2

Figure 4 . 3 :

 43 Figure 4.3: Classification accuracy w.r.t. the number of labeled points with 15 landmarks.

Theorem 5. 4 (

 4 Stability of SLTS). Given a training sample S of m examples drawn i.i.d. from P , our algorithm SLTS has uniform stability in κ/m with κ = 4d γ 2 λ .

Figure 5

 5 Figure 5.1: Classification accuracy of BBS and SLTS w.r.t. the number of landmarks.

Figure 5

 5 Figure5.2: PCA (first two components) in the similarity space for Japanese vowels. Each class becomes linearly separable from the others when using its corresponding metric.

  comes from the Cauchy-Schwarz inequality and some classical norm properties. Finally, Inequality (B.4) comes from Constraint (4.5) in JSL and the normalization of the data resulting in ||x|| 2 ≤ 1.

  2 ]. Inequalities (B.12) and (B.13) come from the Cauchy-Schwarz inequality and some classical norm properties. Inequality (B.14) is due to Constraint (4.5) in JSL and Inequality (B.15) is due to ||x|| 2 ≤ 1.

Table 2 .

 2 1: Common regularizers on vectors ( x ) and matrices ( M ).

	Name	Definition	Properties

Table 2 .

 2 2: Confusion matrix for classification error. NN is the necessity to store the training set during prediction. As in practice not all the training points are needed for accurate classification, data reduction can be performed by keeping in the training set only the examples that help correctly classify all the others. This type of politic is used in variants of k-NN like condensed nearest neighbor (CNN)

		Predicted value
		Positive	Negative
	True label	Positive True positive (tp) False negative (fn) Negative False positive (fp) True negative (tn)
	The right value is usually selected through heuristics of hyperparameter optimization (see
	Section 2.6).
	A significant drawback of k-

Table 3 .

 3 1: Main characteristics of the reviewed metric learning methods for feature vectors.

	Method	Convex Scalable Regularized Semi-sup. Online Generalization
	Xing et al.

  [START_REF] Shen | A Novel Similarity Measure Model for Multivariate Time Series Based on LMNN and DTW[END_REF] propose LMNN-DTW, a different adaptation of LMNN to the multivariate time series case. Their objective is to learn a Mahalanobis distance for k-NN classification. Their formulation is mostly similar to LMNN, with the exception that the distance function is replaces with the cost of DTW under metric M:

  Marc Sebban. Joint semisupervised similarity learning for linear classification. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), pages 594-609, 2015a. Maria-Irina Nicolae, Marc Sebban, Amaury Habrard, Éric Gaussier, and Massih-Reza Amini. Algorithmic Robustness for Semi-Supervised ( , γ, τ )-Good Metric Learning. In Proceedings of the 22nd International Conference on Neural Information Processing (ICONIP), pages 253-263, 2015b.Maria-Irina Nicolae, Marc Sebban, Amaury Habrard, Éric Gaussier, and Massih-Reza Amini. Algorithmic Robustness for Learning via ( , γ, τ )-Good Similarity Functions. In ICLR Workshop, 2015.

  Balcan et al. (2008b) have proposed a theoretical framework that relates the properties of similarity functions to their performance in learning. This theory is based on an intuitive and practical definition of what makes a good similarity function. Essentially, a similarity K is ( , γ, τ )-good for a given binary classification problem if a proportion of 1examples are on average more similar to reasonable examples of the same class than to reasonable examples of the opposite class, where a τ proportion of the examples are considered reasonable. Under K, the classes should be well separated by a margin of γ. The similarity K is not requested to be a distance, nor positive semi-definite, but can be any bounded similarity function. Given that K has these properties, the ( , γ, τ )good framework provides generalization guarantees on a linear classifier learned from the similarity. This separator can be learned efficiently using a linear program (LP) and can enforce sparsity due to an L 1 norm constraint.

The first contribution in this chapter is to propose a new, generic similarity and linear classifier learning formulation for feature vectors. Our setting (JSL, for Joint Similarity Learning) can accommodate a large range of similarity functions that are not required to be PSD, and different regularizers. For the examples of similarities that we study, the formulation is convex and can be solved efficiently, potentially leading to sparse solutions.

Table 4 .

 4 1: Properties of the datasets used in the experimental study. For these reasons, it is difficult to propose a totally fair comparative study. In this section, we first evaluate the effectiveness of JSL-diag with different settings. Secondly, we extensively compare it with state-of-the-art algorithms from different categories (supervised, k-NN oriented)

		Balance Ionosphere Iris Liver Pima Sonar Wine
	# Instances	625	351	150 345	768	208	178
	# Dimensions	4	34	4	6	8	60	13
	# Classes	3	2	3	2	2	2	3
	separator.

Table 4 .

 4 2: Classification accuracy (%) of JSL-diag with confidence interval at 95%, 5 labeled points per class, 15 unlabeled landmarks.

	Sim. Reg.	Balance Ionosphere	Iris	Liver	Pima	Sonar	Wine
	I-L 1 85.2±3.0 85.6±2.4 76.8±3.2 63.3±6.2 71.0±4.1 72.9±3.6 91.9±4.2 M I-L 2 85.1±2.9 85.6±2.6 76.8±3.2 63.1±6.3 71.0±4.0 73.2±3.8 91.2±4.5 K 1
	KL-L 1 84.9±2.9 85.0±2.6 77.3±2.7 63.9±5.5 71.0±4.0 72.9±3.6 90.8±4.7
	KL-L 2 85.2±3.0 85.8±3.3 76.8±3.2 62.9±6.4 71.3±4.3 74.2±3.8 90.0±5.4
	I-L 1 87.2±2.9 87.7±2.6 78.6±4.6 64.7±5.6 75.1±3.5 73.9±5.7 80.8±9.5 M I-L 2 86.8±3.0 87.7±2.8 75.9±5.7 64.3±5.4 75.6±3.6 74.8±5.8 80.8±8.6 K 2
	KL-L 1 87.2±2.9 87.3±2.4 78.6±4.6 62.9±5.6 75.0±3.7 75.5±6.2 79.6±11.8
	KL-L 2 87.1±2.7 85.8±3.3 79.1±5.4 64.9±5.9 75.6±3.4 77.1±5.2 79.6±9.7
	Table 4.3: Classification accuracy (%) of JSL-diag with confidence interval at 95%, all
	points used as landmarks.
	Sim. Reg.	Balance Ionosphere	Iris	Liver	Pima	Sonar	Wine
	I-L 1 85.8±2.9 88.8±2.5 74.5±3.1 65.5±4.5 71.4±3.8 70.3±6.6 85.8±5.0 M I-L 2 85.8±2.9 87.7±2.7 74.5±3.5 64.7±5.5 71.7±4.1 68.7±6.7 84.6±5.5 K 1
	KL-L 1 85.6±3.1 87.9±3.4 75.0±3.5 65.3±4.9 71.6±4.2 70.3±6.8 85.4±5.3
	KL-L 2 85.1±3.1 88.5±3.7 75.9±3.4 65.1±4.8 72.1±4.2 71.9±6.7 86.5±6.0
	I-L 1 85.9±2.3 90.4±2.2 71.8±6.1 67.3±3.5 73.1±3.5 72.9±4.2 81.5±8.4 M I-L 2 86.2±2.5 90.6±2.2 73.2±6.6 68.6±3.3 73.3±3.2 73.2±4.2 82.7±9.0 K 2
	KL-L 1 85.8±2.6 89.4±2.0 72.7±5.5 67.5±3.8 73.8±3.5 71.0±4.1 80.0±7.4
	KL-L 2 85.9±2.4 89.6±2.2 74.5±6.2 68.4±3.6 73.1±3.8 72.3±4.8 80.0±11.5

Table 4 .

 4 4: Average classification accuracy (%) over all datasets with confidence interval at 95%.

	Method	5 pts./cl. 10 pts./cl. 20 pts./cl.
	3-NN	64.6±4.6	68.5±5.4	70.4±5.0
	LMNN-diag 65.1±5.5	68.2±5.6	71.5±5.2
	LMNN	69.4±5.9	70.9±5.3	73.2±5.2
	ITML	75.8±4.2	76.5±4.5	76.3±4.8
	SVM	76.4±4.9	76.2±7.0	77.7±6.4
	BBS	77.2±7.3	77.0±6.2	77.3±6.3
	SLLC	70.5±7.2	75.9±4.5	75.8±4.8
	LRML	74.7±6.2	75.3±5.9	75.8±5.2
	JSL-15	78.9±6.7 77.6±5.5	77.7±6.4
	JSL-all	78.2±7.3	76.6±5.8	78.4±6.7

Table 5 .

 5 1: Properties of the datasets used in the experimental study.

	Dataset	#Instances Length #Features #Classes
	Japanese vowels	640	7-29	12	9
	Auslan	675	47-95	22	25
	Arabic digits	8800	4-93	13	10
	Robot exec. failure
	LP1	88	15	6	4
	LP2	47	15	6	5
	LP3	47	15	6	4
	LP4	117	15	6	3
	LP5	164	15	6	5

Table 5 .

 5 2: Classification accuracy (%) with confidence interval at 95%.

	Method Japanese vowels Auslan	Arabic digits Robot exec. failure Avg.
	1NN	93.8	77.8±2.1 94.7	68.8±7.5	92.1
	LDMLT 97.3	95.0±1.3 96.9	71.9±7.0	95.6
	SVM	97.8±0.1	92.6±0.1 93.3±0.0	60.6±6.5	92.2
	BBS	97.1±0.5	91.1±1.6 96.4±0.3	66.9±10.6	94.7
	SLTS	97.1±0.4	91.1±2.7 97.9±0.4	67.0±7.8	95.8

  Classification performance comparisonThe results of the comparison of SLTS and BBS with other methods are displayed in Table5.2. For this second experiment, both SLTS and BBS are based on the maximum number of landmarks from the previous experiment. Note that confidence interval in the table values means that the train/test split of the data is already provided, and the output of the method is deterministic. As one can observe, among global methods relying on a linear classification (i.e., SLTS, BBS, and SVM), both SLTS and BBS perform better than SVM (they are on a par on Japanese vowels, slightly below on Auslan, and above on Arabic digits and Robot execution failure). Using a Student t-test for paired samples on the average reveals that SLTS is significantly better than BBS and SVM. This shows the usefulness of the ( , γ, τ )-good framework as well as the importance of metric learning in this framework. The comparison of SLTS with local methods (as 1NN and LDMLT) yields more contrasted results. On all datasets except Robot exec. failure, 1NN is significantly below SLTS according to a Student t-test.

Table 5 .

 5 3: Classification accuracy for landmarks selection methods on Japanese vowels.

	Algorithm 5.1 Dselect heuristic
	Input A training set S, number of landmarks n Output A set L of n landmarks L ← random element of S for i = 2 to n do
	z ← arg min z=(x,y)∈S z =(x ,y )∈L K(x, x ) L ← L ∪ {z} S ← S \ {z} end for
	return L
	Lmks DSelect KMedoids Random
	3%	96.8±0.6 96.3±0.6	96.4±0.7
	5%	96.5±0.6 95.9±0.7	96.4±0.6
	7%	97.0±0.2 96.3±0.4	96.2±0.5
	10%	97.3±0.3 96.2±0.5	96.5±0.6
	15%	97.1±0.2 96.4±0.4	97.0±0.4
	20%	97.1±0.3 96.8±0.4 97.1±0.4
	30%	96.7±0.4	97.0±0.3 97.1±0.4
	40%	97.0±0.4	96.9±0.3 97.1±0.4
	50%	96.8±0.3 96.9±0.3 96.9±0.4

Table 5 .

 5 4: Classification accuracy for landmarks selection methods on LP1.

	Lmks	DSelect KMedoids	Random
	3%	48.5±6.2	50.7±9.4 56.3±12.2
	5%	67.8±9.7 63.3±10.1	62.6±5.9
	7%	67.8±9.7 63.3±10.1	62.6±5.9
	10%	68.5±9.6	65.2±5.5	65.6±9.4
	15%	67.0±6.4 69.3±6.8 68.5±10.0
	20%	71.1±5.6	68.9±5.8	64.4±8.1
	30%	70.4±7.2	66.7±6.8	70.4±5.7
	40%	74.4±7.9	70.4±6.5	72.2±5.3
	50%	73.0±7.0	71.5±8.5	70.7±7.0

  Equation (B.20) comes from the 1-lipschitzness of the hinge loss. Inequality (B.21) is obtained by applying triangle inequality. We obtain line (B.22) by applying Lemmas B.1 and B.2.

	Proof of Lemma 5.2.

  IntroductionL'apprentissage automatique a pour but de concevoir des algorithmes de prédiction précis à partir des données d'entraînement. Ces données peuvent être vues comme une forme d'expérience utilisée pour de l'apprentissage par l'exemple : les nouvelles décisions prennent en compte les instances précédentes. Ce processus est différent des systèmes de mémorisation, qui reconnaissant uniquement les exemples déjà rencontrés. Dans l'apprentissage, le but est de déterminer le modèle associé aux données et d'être capable de l'appliquer sur des nouvelles instances. Dans la plupart des cas, une fois l'étape de modélisation effectuée, les données initiales peuvent être ignorées et le modèle peut prédire les résultats pour des nouvelles instances arrivant dans le système. Contrairement aux systèmes basés sur la mémoire, cela implique que l'apprentissage automatique a des capacités de généralisation.

	46) Inequalities (B.40) and (B.41) come from triangle inequality. Inequalities (B.42) and (B.43) come from the uniform stability of our algorithm (Theorem 5.4). Line (B.44) comes from compris : the fact that S and S Les algorithmes d'apprentissage sont utilisés avec succès dans une variété d'applications, y • La vision par ordinateur (par exemple la segmentation d'image, la détection de visage ou bien la reconnaissance d'objet) ;

i differ only by example i. We can write Inequality (B.45) because the loss is always positive, and we get line (B.46) by bounding the value of the loss function (Lemma 5.1).

  Cette liste n'est pas exhaustive et de nouvelles applications pour les algorithmes d'apprentissage sont proposées chaque jour.Les données peuvent être mises à la disposition de l'algorithme sous différentes formes. Les vecteurs de features sont souvent utilisés pour stocker des informations catégorielles ou numériques, comme l'emplacement d'une maison, son prix ou sa surface. Les données structurées sont utilisées pour représenter des informations qui ne peuvent pas être stockées directement en tant que vecteurs de features, telles que des chaînes (par exemple, des documents textuels), des arbres (par exemple, du contenu XML) ou des graphes (par exemple, des réseaux sociaux). Un autre type de données structurées présent dans de nombreuses applications sont les séries temporelles qui suivent l'évolution d'un processus à travers le temps (par exemple, les cotations boursières, les signes vitaux des patients ou les données météorologiques). Depuis un type de données particulier, ou une combinaison de plusieurs types, l'algorithme peut effectuer différentes tâches d'apprentissage.En apprentissage supervisé, les données possèdent une étiquette associée à chaque instance. L'algorithme doit apprendre à prédire ces étiquettes pour de nouveaux exemples. Lorsque l'étiquette provient d'un ensemble discret de valeurs (par exemple, le genre d'une personne), la tâche est appelée classification. Inversement, lorsque les étiquettes sont continues (par exemple, le prix), la tâche à effectuer est une régression. Dans ce document, nous nous concentrons principalement sur les tâches supervisées. L'apprentissage non supervisé couvre le cas où aucune information d'étiquette n'est disponible pour les données. Dans ce contexte, l'algorithme est amené à exécuter une tâche pour laquelle l'information de l'étiquette n'est pas nécessaire. Par exemple, le clustering vise à trouver de la structure dans les données permettant de diviser les exemples en groupes nommés clusters. L'apprentissage semi-supervisé couvre des tâches similaires à celles du cadre supervisé, mais il permet d'intégrer en outre des échantillons non étiquetés.La performance d'un algorithme d'apprentissage est fortement liée à la quantité et à la qualité des données disponibles. Traditionnellement, la performance d'un algorithme est associée à sa complexité algorithmique et sa consommation en mémoire. Bien que l'efficacité de calcul soit aussi une préoccupation importante dans l'apprentissage automatique, dans ce cas la performance est mesurée principalement par rapport à la qualité de la prédiction. Une autre mesure à prendre en compte est la complexité de l'échantillon, qui indique la quantité de données requises par un algorithme pour apprendre à résoudre une certaine tâche. Plus précisément, des garanties théoriques peuvent être fournies pour la performance d'un algorithme d'apprentissage par rapport à la quantité de données disponibles et une notion de complexité du modèle choisi. Ces types de garanties peuvent être dérivés en utilisant des méthodes de la théorie de l'apprentissage statistique.La plupart des algorithmes d'apprentissage automatique sont amenés à comparer des instances de données, soit pour construire le modèle, soit pour faire des prédictions. Les comparaisons sont effectuées en utilisant une notion de métrique qui donne une mesure de ressemblance entre les exemples. Ceci est vrai pour les méthodes supervisées, comme les k plus proches voisins ou les machines à vecteurs de support, ainsi que pour les non-supervisés, tels que K-moyennes. Cependant, le choix d'une métrique adaptée peut s'avérer une tâche difficile et la performance de l'algorithme en dépend fortement. On cherche à choisir une mesure qui discrimine effectivement les données pour la tâche à accomplir (par exemple, pour la classification, en reconnaissant les instances d'une même étiquette comme étant similaires). De plus, les métriques standards, telles que la distance euclidienne, n'ont pas la capacité de s'adapter à une tâche ou d'intégrer des contraintes sémantiques, parfois ignorant l'information pertinente. L'apprentissage de métriques vise à résoudre ce problème en apprenant automatiquement des métriques adaptées aux données. Cette étape est effectuée en amont de l'application d'un algorithme d'apprentissage automatique. La métrique précédemment acquise est utilisée par la suite pour résoudre une tâche d'apprentissage spécifique. L'apprentissage de métriques destiné à la classification est le sujet principal que nous abordons dans cette thèse. Ce domaine peut être considéré comme faisant partie d'un ensemble plus vaste appelé l'apprentissage de représentation : sous la nouvelle métrique, la représentation des données change. L'apprentissage de représentation comprend également des domaines tels Figure C.1: Les étapes de l'apprentissage supervisé. La capacité de généralisation peut être évaluée à deux niveaux: pour la métrique et pour le prédicteur qui l'utilise.que l'apprentissage de features, le deep learning, l'apprentissage de noyaux et bien d'autres. L'apprentissage de métriques a reçu beaucoup d'attention au cours des quinze dernières années, en particulier pour le cadre supervisé. La plupart des méthodes apprennent les paramètres d'une distance de Mahalanobis sous des contraintes induites par les données, ce qui équivaut à changer la représentation des instances sous une transformation linéaire. Dans le cas supervisé, la métrique apprise a pour but d'illustrer les instances avec les mêmes étiquettes comme similaires et les différentes comme dissemblables. Les méthodes de l'état de l'art dédiées aux vecteurs de features sont plus aptes à passer à l'echelle et plus efficaces que les approches précédentes. D'autre part, l'apprentissage de métriques pour les séries temporelles a reçu peu d'attention, probablement à cause de la structure plus complexe des données. Les séries temporelles issues des applications réelles ont généralement des longueurs, des taux d'échantillonnage et des phases différents. C'est pourquoi il est nécessaire d'aligner deux séries temporelles afin de les comparer. Cela implique de trouver toutes les correspondances entre les moments de temps. La déformation temporelle dynamique (DTW, pour dynamic time warping en anglais) est l'algorithme le plus connu pour trouver l'alignement optimal basé sur une matrice de coût. L'apprentissage de métriques pour les séries temporelles vise généralement à optimiser ce coût sous des contraintes imposées par les exemples.L'état d'avancement en apprentissage de métriques souffre de quelques limitations non négligeables. La plus importante est probablement le manque de garanties théoriques pour la plupart des méthodes existantes. En effet, on voudrait évaluer la capacité de généralisation associée à l'apprentissage d'une métrique, qui se décline sous deux aspects (voir la Figure C.1). Premièrement, la métrique doit être consistente avec les données. Ce type de garantie n'a été fourni que pour un faible nombre de méthodes. Deuxièmement, la métrique apprise doit être liée à l'algorithme qui l'utilise, améliorant ses performances par rapport aux métriques standard. Par exemple, une métrique apprise à partir de contraintes locales pour une règle de classification locale peut ne pas fonctionner correctement lorsqu'elle est utilisée avec un classifieur linéaire global. Ce second type de garantie est aussi rare dans le domaine et, même si certaines méthodes améliorent un critère relatif au classifieur, ce lien n'est pas formellement établi. En pratique, la métrique apprise est utilisée dans le classifieur dans l'espoir d'améliorer sa performance. La théorie des fonctions de similarité ( , γ, τ )-bonnes a été l'un des premiers résultats à lier les propriétés d'une fonction de similarité à la performance qu'on peut attendre d'elle en classification. Nous décrivons ce cadre en détail dans la thèse, nos contributions en faisant usage. Une deuxième limitation dans l'apprentissage de métriques vient du fait que la plupart des méthodes fonctionnent avec des métriques qui imposent des propriétés de distance. Satisfaire ce type de contraintes peut être coûteux même en utilisant des techniques modernes d'optimisation numérique, ce qui rajoute un coût supplementaire à l'apprentissage. Cette limitation jointe à l'absence de garanties pour l'amélioration de la performance implique que l'effort dépensé dans l'apprentissage de métriques pourrait effectivement se traduire par une dégradation de la performance.Cette thèse a pour but d'aborder les limitations mentionnées précédemment. Toutes nos contributions sont basées sur l'apprentissage de fonctions de similarité, une famille de métriques différente qui sont moins contraignantes que les distances et constituent une voie prometteuse mais moins explorée pour la recherche. Nous apportons également des garanties de généralisation pour la métrique apprise et le classifieur associé pour toutes les méthodes que nous proposons. Dans un premier temps, nous présentons un cadre général permettant d'apprendre simultanément la similarité et le classifieur linéaire. Ce cadre est conçu pour les vecteurs de features et est applicable pour une large gamme de fonctions de similarité. De plus, l'approche est semi-supervisée, ce qui lui permet d'exploiter des exemples non-étiquettés afin d'améliorer les performances. Notre contribution suivante nous permet d'aborder le problème de l'apprentissage de métriques pour les séries temporelles multivariées. Nous proposons d'apprendre une fonction de similarité bilinéaire destinée à la classification linéaire. La similarité utilise les alignements optimaux et permet de mieux repondérer les features.Contexte de la thèse Les travaux de cette thèse ont été réalisés dans des équipes d'apprentissage automatique de deux établissements: le groupe Data Intelligence du Laboratoire Hubert Curien UMR CNRS 5516, de l'Université de Saint-Étienne et de l'Université de Lyon, et l'équipe Data Analysis, Modeling and Machine Learning (AMA) du Laboratoire d'Informatique de Grenoble, de l'Université Grenoble-Alpes. Le financement de ce projet a été assuré par une bourse de la Région Rhône-Alpes.

	Garanties de consistence
	pour la métrique
		Echantillon	Métrique		Prédicteur
	Distribution sous-jacente	de données	Apprentissage de métriques	apprise	Algorithme de prédiction	appris	Prédiction
		Garanties de généralisation du préditeur
		utilisant la métrique

+

  Chapitre 2 Ce chapitre présente les configurations d'apprentissage les plus courantes, en se concentrant sur le cadre standard pour l'apprentissage supervisé, ainsi que certaines notions fondamentales de la théorie de l'apprentissage statistique. Nous présentons les principaux cadres analytiques et les outils permettant de dégager des garanties de généralisation. Nous commençons par le modèle d'apprentissage Probably Approximately Correct (PAC), puis nous présentons plusieurs cadres pour dériver des bornes de généralisation PAC : la convergence uniforme avec différentes mesures de complexité, la stabilité uniforme et la robustesse algorithmique. L'ensemble des vecteurs réels de dimension d R d×d L'ensemble de matrices réelles de dimensions d × d S d Le cône des matrices réelles symétriques PSD de dimensions d × d S L'entrée de la ligne i et la colonne j de la matrice M [•] + La fonction hinge || • || Une norme arbitraire || • || p La norme L p A Une série temporelle arbitraire x ∼ P x est tiré de façon indépendante de la distribution de probabilités P Pr[•] La probabilité d'un événement E[•] L'espérance d'une variable aléatoire Table C.1: Sommaire des notations. Chapitre 3 Dans ce chapitre, nous analysons les méthodes existantes pour l'apprentissage de métriques supervisé et semi-supervisé. Nous commençons par présenter un aperçu de certaines métriques standard. Notre étude de l'état de l'art couvre les méthodes d'apprentissage de métriques supervisé dédiées aux vecteurs de features et aux séries temporelles. Après avoir discuté de ces aspects, nous pouvons conclure sur les avantages et les limites des méthodes récentes, qui représentent les principales motivations de nos contributions. Chapitre 4 Dans ce chapitre, nous proposons un cadre générique innovant pour l'apprentissage d'une similarité en même temps que l'apprentissage d'un classifieur linéaire global à partir de vecteurs numériques. La formulation est capable d'exploiter les informations provenant de données non supervisées en plus d'un ensemble d'apprentissage étiqueté, ce qui en fait un cadre semi-supervisé. Nous montrons que notre formulation peut être utilisée avec une grande classe de régulariseurs et de nombreuses fonctions de similarité. Nous proposons une analyse théorique de ce cadre d'apprentissage conjoint à travers deux méthodes différentes, la robustesse algorithmique et la convergence uniforme basée sur la complexité de Rademacher, que nous comparons. Les résultats théoriques dérivés s'appliquent à la métrique apprise et au classifieur. De plus, ils sont génériques et couvrent des fonctions de similarité et des régulariseurs différents sans imposer de fortes contraintes. Les expériences menées sur des ensembles de données standard montrent les avantages de notre approche par rapport aux méthodes de pointe: JSL est efficace et performant.

	Notation	Description
	R	L'ensemble des nombres réels
	R d
		Un ensemble arbitraire
	|S| S n X Y z = (x, y) ∈ X × Y Un exemple étiqueté Le cardinal de S Un ensemble de n éléments de S L'espace d'entrée L'espace de sortie x Un vecteur arbitraire
	x i	L'entrée d'indice i du vecteur x
	M	Une matrice arbitraire
	I	La matrice identité
	M i,j

  , qui est directement liée à la performance du classifieur. Une caractéristique importante de JSL en découlant est son réglage semi-supervisé. Il permet à la méthode de tirer profit des données non étiquetées d'une manière différente de la plupart des méthodes semisupervisées, c'est-à-dire en l'utilisant pour construire l'espace de représentation dans lequel les données sont projetées. La capacité à exploiter des exemples non-étiquetés rend le cadre proposé particulièrement adapté au contexte réel où l'annotation des données est coûteuse, et seul un petit nombre d'instances étiquetées est disponible. À notre connaissance, cette méthode est la première à apprendre la métrique et le classifieur en même temps de façon semi-supervisée. La généralité de JSL réside dans le fait qu'il peut être instancié avec une large gamme de fonctions de similarité et de régulariseurs, fournissant ainsi un moyen de résoudre des problèmes avec des propriétés différentes. La régularisation générale a la capacité d'incorporer les connaissances antérieures sur la tâche donnée. Nous proposons également une méthode efficace pour résoudre le problème, qui est convexe sous contraintes légères pour la fonction de similarité. D'un point de vue théorique, nous analysons JSL à travers la perspective de deux cadres: la robustesse algorithmique et la convergence uniforme avec la complexité de Rademacher. Les deux analyses donnent des bornes de généralisation pour la similarité et le classifieur appris qui sont valides pour différentes fonctions de similarité et fournissent des informations à leur sujet. La vaste étude expérimentale montre que JSL obtient de meilleures performances qu'un grand nombre d'autres méthodes. Le code source de JSL est disponible publiquement sous licence GNU/GPL 2+ 1 . Notre deuxième contribution se concentre sur un type particulier de données, qui sont les séries temporelles multivariées. Nous avons proposé d'apprendre une fonction de similarité bilinéaire pour une tâche de classification. Une fois de plus, nous avons cherché à généraliser les noyaux en relâchant la contrainte PSD, tout en liant les propriétés de la similarité à sa performance en classification. Cela a été fait en apprenant une similarité ( , γ, τ )bonne basée sur l'alignement optimal entre les séries temporelles calculé par DTW. Le problème, appelé SLTS, est formulé comme un programme quadratique, qui peut être résolu efficacement. Travailler avec des séries temporelles est souvent coûteux en termes de calcul, principalement en raison de la complexité des données et de la DTW lors du calcul du meilleur alignement entre les paires de points. Nous avons pu réduire le nombre de valeurs de similarités et d'alignements à calculer en basant l'approche sur un ensemble de landmarks et limitant leur nombre. Nous avons établi des garanties de généralisation pour SLTS basées sur la stabilité uniforme, assurant la consistence de la métrique obtenue. La borne de généralisation dérivée est plutôt serrée et indépendante des longueurs des séries temporelles et des alignements, ressemblant à des bornes similaires pour les vecteurs numériques. L'étude expérimentale montre les bonnes propriétés de la métrique, ainsi que sa performance par rapport aux méthodes standard. À notre connaissance, SLTS est la première méthode d'apprentissage de métriques pour les séries temporelles multivariées qui est accompagnée d'une telle analyse théorique. Le code source pour la résolution de SLTS est également disponible publiquement sous licence GNU/GPL 2+ 2 .Il existe plusieurs perspectives intéressantes pour étendre les méthodes que nous avons proposées. L'une d'entre elle correspond à l'adaptation de l'apprentissage pour plusieurs métriques, chacune faisant référence à une région différente de l'espace. Nous pensons que cette direction peut capturer des informations supplémentaires dans les données, ainsi que fournir une manière implicite d'introduire la non-linéarité. Notez que le cadre des similarités ( , γ, τ )-bonnes comprend une version dans laquelle plusieurs fonctions peuvent être combinées pour obtenir une métrique globale qui bénéficie des mêmes garanties. Une autre extension possible est d'adapter les approches proposées à un apprentissage incrémental, où les exemples arrivent un à la fois. En pratique, les premiers points reçus seraient considérés comme des landmarks pour le processus d'apprentissage. Pour ce cadre, on pourrait dériver des bornes de regret par rapport à la version ayant à disposition l'intégralité des données. D'un point de vue théorique, cette thèse a analysé les garanties qui peuvent être obtenues par une fonction de similarité dans la classification linéaire. Ces résultats ont été obtenus à partir de la théorie des similarités ( , γ, τ )-bonnes. Malheureusement, ce cadre lie les fonctions de similarité au cas particulier des classifieurs linéaires globaux. Considérant que l'état de l'art en apprentissage de métriques, qu'il s'agisse de vecteurs de features ou de séries temporelles, est orienté vers le classifieur de type k-NN, il serait important de développer des cadres théoriques d'analyse ou des résultats particuliers pour certaines méthodes concernant cette règle de classification locale. Certains résultats ont déjà été établis pour l'apprentissage incrémental et non-incrémental dans[START_REF] Qamar | Similarity Learning for Nearest Neighbor Classification[END_REF] sur la base de la théorie du perceptronde Freund & Schapire (1998).Une autre voie prometteuse pour la recherche serait d'explorer des milieux qui n'ont pas reçu beaucoup d'attention dans l'apprentissage de métriques, comme l'apprentissage nonsupervisé. Celui-ci un problème difficile, car le critère que la métrique doit optimiser n'est pas toujours évident, de même que les mesures de performance. Un premier résultat utilisant la stabilité uniforme pour dériver des garanties théoriques pour le cas général des algorithmes d'apprentissage non-supervisés a récemment été dérivé dans[START_REF] Karim | Generalization in Unsupervised Learning[END_REF], ouvrant la voie à d'autres recherches. Plus précisément, ils se concentrent sur les applications de clustering et de réduction de la dimensionnalité. Malheureusement, leurs résultats dépendent de la définition manuelle d'un critère d'évaluation pour chaque application.

[START_REF] Bian | Learning a Distance Metric by Empirical Loss Minimization[END_REF][START_REF] Bellet | Supervised Metric Learning with Generalization Guarantees[END_REF] develop an ERM framework for Mahalanobis distance learning under constraints. The generic loss function they use is close to the one from(Jin et al.,

For all the methods, we used the code provided by the authors.

Download at http://inicolae.com/resources/jsl.zip.

Download at http://inicolae.com/resources/slts.zip.

Télécharger à l'adresse http://inicolae.com/resources/jsl.zip.

Télécharger à l'adresse http://inicolae.com/resources/slts.zip.

List of Figures

. By the Bretagnolle-Huber-Carol inequality we have:

hence with probability at least 1δ,

We are now able to present the generalization bound for JSL in the following theorem.

Theorem 4.9 (Generalization bound using algorithmic robustness). Considering that Problem (4.7) is (M, (S))-robust, that (M S , α S ) is its solution learned from sample S and that K M is l-lipschitz w.r.t. to its first argument, for any δ > 0 with probability at least 1δ, we have:

where B = 1 + 1 γ is an upper bound of the loss and ρ = sup x,x ∈C i ||xx ||.

The proof of Theorem 4.9 follows the one described in [START_REF] Xu | Robustness and Generalization[END_REF] and is presented in Appendix B.1. Note that the cover radius ρ can be arbitrarily small at the expense of larger values of M . As M appears in the second term, decreasing to 0 when d l goes to infinity, this bound provides a standard O(1/ √ d l ) asymptotic convergence.

As one can notice, our main theorem strongly depends on the l-lipschitzness of the similarity function. Plugging the value of l in the bound in Theorem 4.9, we obtain consistency results for Problem (4.7) using a specific similarity. As the gap between empirical and true loss presented in Theorem 4.9 is proportional with the l-lipschitzness of each similarity function, we would like to keep this parameter as small as possible. Concerning our examples of similarity functions, we notice that the generalization bound is tighter for K 1 M than for K 2 M . The bound for K 3 M depends on the additional parameter σ, that adjusts the influence of the similarity value w.r.t. the distance to the landmarks.

Uniform Convergence of JSL Using the Rademacher Complexity

In this section, we provide an analysis of JSL based on the uniform convergence framework and the Rademacher complexity, before deriving our main result, a generalization bound for JSL based on these notions (Theorem 4.12).

We start by introducing the definition of what we will consider admissible similarity functions for this analysis. Intuitively, this notion is similar to l-lipschitzness in the sense that both of them bound the values of the similarity function w.r.t. its arguments. If

Chapter 5

Learning Similarities for Time Series Classification

Chapter abstract

Dynamic time warping (DTW) is the most well-known algorithm for measuring the similarity between two time series by finding the best alignment between them.

Unfortunately, as we have seen in Chapter 3, not much research effort has been put into adapting it to multivariate time series, and even less into improving it by learning.

In this chapter, we propose a novel method for learning similarities based on DTW, in order to improve time series classification. In this contribution also we makes use of the ( , γ, τ )-good similarities learning framework (Balcan et al., 2008b), providing guarantees on the performance of a linear classifier built from the learned metric. Proving that our method has uniform stability allows us to derive the first consistency bound for a metric learned from temporal data. We perform experiments on real-world multivariate time series datasets, comparing our method to state of the art approaches.

The experimental study shows that the proposed approach is efficient, while yielding sparse classifiers.

The material of this chapter is based on the following technical report:

Maria-Irina Nicolae, Éric Gaussier, Amaury Habrard, and Marc Sebban. Similarity Learning for Time Series Classification. Technical report, University of Saint-Etienne, 2016. arXiv:1610.04783. To be submitted to the journal track of ECML/PKDD 2017 and MLJ.

Introduction

Dynamic time warping has shown good results for time series tasks, receiving important attention from the research community. As presented in Section 3.3.2, metric learning for time series in general, and for the multivariate case in particular, has only been explored by a limited number of studies. The vast majority of methods are constructed from local constraints and designed for k-NN classification, following the orientation of the time series analysis community. The question remains if classifiers and metrics inferred from global constraints (e.g. linear) can be effective on time series. Often learning a Mahalanobis distance, existing methods impose a PSD constraint which is computationally expensive Appendix A

Concentration Inequalities

Concentration inequalities provide bounds on how a random variable deviates from a value, usually its expected value. The law of large numbers states that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability.

McDiarmid's inequality bounds the expected value for sufficiently regular function of the variables.

Theorem A.1 (McDiarmid's inequality [START_REF] Mcdiarmid | On the Method of Bounded Differences[END_REF]). Let X 1 , . . . , X n be independent random variables taking values in the set X . Further, let f :

Then, for all > 0,

When the random variables X i are bounded and f is the mean value, we obtain Hoeffding's inequality, which provides an upper bound on the probability that the sum of random variables deviates from its expected value.

Theorem A.2 (Hoeffding's inequality [START_REF] Hoeffding | Probability Inequalities for Sums of Bounded Random Variables[END_REF]). Let X 1 , . . . , X n be independent random variables respectively taking values in the intervals

Appendix B

Proofs

B.1 Proofs of Chapter 4

This appendix details proofs of Theorem 4.9, and the l-lipschitzness of the similarity functions K 1 M , K 2 M , and K 3 M .

Proof of Theorem 4.9 [START_REF] Xu | Robustness and Generalization[END_REF]. We bound the difference between the true risk and the empirical risk in the following way:

Inequality (B.1) is due to the triangle inequality. Inequality (B.2) comes from the application of Proposition 4.8 and Theorem 4.7.

Properties of the similarity function

In order to prove that K 1 M is 1-lipschitz, we need to bound the following difference.

≤ exp -2 σ 2 (B.17)

We use the (1, 4)-admissibility of K 2 M to obtain Inequality (B.16), while Inequality (B.17) comes from the data normalization and the fact that M F ≤ 1. Here, we are only able to bound K 3 M by a constant.

B.2 Proofs of Chapter 5

This section contains the proofs of Lemmas 5.1 to 5.6 from Chapter 5, as well as defining some additional lemmas necessary for these proofs.

To prove Lemma 5.1, we need two additional lemmas. Lemma B.1 bounds the Frobenius norm of the learned matrix M, while Lemma B.2 puts a bound on the Frobenius norm of a subpart of the similarity function.

Lemma B.1. If M is the optimal solution of Problem (4.3), we have:

Proof. Since M is the optimal solution of Problem (4.3), we have:

) is a result of the fact that the hinge loss is always positive, while Inequality (B.19) comes from noting that the loss is bounded by 1/m when the metric is set to zero.

Lemma B.2 (Technical lemma).

Let A ∈ R t A ×d and B ∈ R t B ×d be two examples, and

Proof.

Translation into French

C Traduction en français

Abstract

The notion of metric plays a key role in machine learning problems, such as classification, clustering and ranking. Learning metrics from training data in order to make them adapted to the task at hand has attracted a growing interest in the past years. This research field, known as metric learning, usually aims at finding the best parameters for a given metric under some constraints from the data. The learned metric is used in a machine learning algorithm in hopes of improving performance. Most of the metric learning algorithms focus on learning the parameters of Mahalanobis distances for feature vectors. Current state of the art methods scale well for datasets of significant size. On the other hand, the more complex topic of multivariate time series has received only limited attention, despite the omnipresence of this type of data in applications. An important part of the research on time series is based on the dynamic time warping (DTW) computing the optimal alignment between two time series. The current state of metric learning suffers from some significant limitations which we aim to address in this thesis. The most important one is probably the lack of theoretical guarantees for the learned metric and its performance for classification. The theory of ( , γ, τ )-good similarity functions has been one of the first results relating the properties of a similarity to its classification performance. A second limitation in metric learning comes from the fact that most methods work with metrics that enforce distance properties, which are computationally expensive and often not justified. In this thesis, we address these limitations through two main contributions. The first one is a novel general framework for jointly learning a similarity function and a linear classifier. This formulation is inspired from the ( , γ, τ )-good theory, providing a link between the similarity and the linear classifier. It is also convex for a broad range of similarity functions and regularizers. We derive two equivalent generalization bounds through the frameworks of algorithmic robustness and uniform convergence using the Rademacher complexity, proving the good theoretical properties of our framework.

Our second contribution is a method for learning similarity functions based on DTW for multivariate time series classification. The formulation is convex and makes use of the ( , γ, τ )-good framework for relating the performance of the metric to that of its associated linear classifier. Using uniform stability arguments, we prove the consistency of the learned similarity leading to the derivation of a generalization bound.

Résumé

La notion de métrique joue un rôle clef dans les problèmes d'apprentissage automatique tels que la classification, le clustering et le ranking. L'apprentissage à partir de données de métriques adaptées à une tâche spécifique a suscité un intérêt croissant ces dernières années. Ce domaine vise généralement à trouver les meilleurs paramètres pour une métrique donnée sous certaines contraintes imposées par les données. La métrique apprise est utilisée dans un algorithme d'apprentissage automatique dans le but d'améliorer sa performance. La plupart des méthodes d'apprentissage de métriques optimisent les paramètres d'une distance de Mahalanobis pour des vecteurs de features. Les méthodes actuelles de l'état de l'art arrivent à traiter des jeux de données de tailles significatives. En revanche, le sujet plus complexe des séries temporelles multivariées n'a reçu qu'une attention limitée, malgré l'omniprésence de ce type de données dans les applications réelles. Une importante partie de la recherche sur les séries temporelles est basée sur la dynamic time warping (DTW), qui détermine l'alignement optimal entre deux séries temporelles. L'état actuel de l'apprentissage de métriques souffre de certaines limitations. La plus importante est probablement le manque de garanties théoriques concernant la métrique apprise et sa performance pour la classification. La théorie des fonctions de similarité ( , γ, τ )-bonnes a été l'un des premiers résultats liant les propriétés d'une similarité à celles du classifieur qui l'utilise. Une deuxième limitation vient du fait que la plupart des méthodes imposent des propriétés de distance, qui sont coûteuses en terme de calcul et souvent non justifiées. Dans cette thèse, nous abordons les limitations précédentes à travers deux contributions principales. La première est un nouveau cadre général pour l'apprentissage conjoint d'une fonction de similarité et d'un classifieur linéaire. Cette formulation est inspirée de la théorie de similarités ( , γ, τ )-bonnes, fournissant un lien entre la similarité et le classifieur linéaire. Elle est convexe pour une large gamme de fonctions de similarité et de régulariseurs. Nous dérivons deux bornes de généralisation équivalentes à travers les cadres de robustesse algorithmique et de convergence uniforme basée sur la complexité de Rademacher, prouvant les propriétés théoriques de notre formulation. Notre deuxième contribution est une méthode d'apprentissage de similarités basée sur DTW pour la classification de séries temporelles multivariées. Le problème est convexe et utilise la théorie des fonctions ( , γ, τ )-bonnes liant la performance de la métrique à celle du classifieur linéaire associé. A l'aide de la stabilité uniforme, nous prouvons la consistance de la similarité apprise conduisant à la dérivation d'une borne de généralisation.