Je Veux

Émilie, David, Fabien, Tung, Chahrazed Christophe Laurent

qui ont tout de suite accepté d'être examinateurs

CHAPTER 1

Introduction

The goal of machine learning is to automatically figure out how to perform tasks by generalizing from examples. A machine learning algorithm takes a data sample as input and infers a model that captures the underlying mechanism (usually assumed to be some unknown probability distribution) which generated the data. Data can consist of features vectors (e.g., the age, body mass index, blood pressure, ... of a patient) or can be structured, such as strings (e.g., text documents) or trees (e.g., XML documents). A classic setting is supervised learning, where the algorithm has access to a set of training examples along with their labels and must learn a model that is able to accurately predict the label of future (unseen) examples. Supervised learning encompasses classification problems, where the label set is finite (for instance, predicting the label of a character in a handwriting recognition system) and regression problems, where the label set is continuous (for example, the temperature in weather forecasting). On the other hand, an unsupervised learning algorithm has no access to the labels of the training data. A classic example is clustering, where we aim at assigning data into similar groups. The generalization ability of the learned model (i.e., its performance on unseen examples) can sometimes be guaranteed using arguments from statistical learning theory.

Relying on the saying "birds of a feather flock together", many supervised and unsupervised machine learning algorithms are based on a notion of metric (similarity or distance function) between examples, such as k-nearest neighbors or support vector machines in the supervised setting and K-Means clustering in unsupervised learning. The performance of these algorithms critically depends on the relevance of the metric to the problem at hand -for instance, we hope that it identifies as similar the examples that share the same underlying label and as dissimilar those of different labels. Unfortunately, standard metrics (such as the Euclidean distance between feature vectors or the edit distance between strings) are often not appropriate because they fail to capture the specific nature of the problem of interest.

For this reason, a lot of effort has gone into metric learning, the research topic devoted to automatically learning metrics from data. In this thesis, we focus on supervised metric learning, where we try to adapt the metric to the problem at hand using the information brought by a sample of labeled examples. Many of these methods aim to find the parameters of a metric so that it best satisfies a set of local constraints over the training sample, requiring for instance that pairs of examples of the same class should be similar and that those of different class should be dissimilar according to the learned metric. A large body of work has been devoted to supervised metric learning from feature vectors, in particular Mahalanobis distance learning, which essentially learns a linear projection of the data into a new space where the local constraints are better satisfied. While early methods were costly and could not be applied to medium-sized problems, recent methods offer better scalability and interesting features such as sparsity. Supervised metric learning from structured data has received less attention because it requires more complex procedures. Most of the work has focused on learning metrics based on the edit distance. Roughly speaking, the edit distance between two objects corresponds to the cheapest sequence of edit operations (insertion, deletion and substitution of subparts) turning one object into the other, where operations are assigned specific costs gathered in a matrix. Edit distance learning consists in optimizing the cost matrix and usually relies on maximizing the likelihood of pairs of similar examples in a probabilistic model.

Overall, we identify two main limitations of the current supervised metric learning methods. First, metrics are optimized based on local constraints and used in local algorithms, in particular k-nearest neighbors. However, it is unclear whether the same procedures can be used to obtain good metrics for use in global algorithms such as linear separators, which are simple yet powerful classifiers that often require less memory and provide greater prediction speed than k-nearest neighbors. In this context, one may want to optimize the metrics according to a global criterion but, to the best of our knowledge, this has never been addressed. Second, and perhaps more importantly, there is a substantial lack of theoretical understanding of generalization in metric learning. It is worth noting that in this context, the question of generalization is two-fold, as illustrated in Figure 1.1. First, one may be interested in the generalization ability of the metric itself, i.e., its consistency not only on the training sample but also on unseen data coming from the same distribution. Very little work has been done on this matter, and existing frameworks lack generality. Second, one may also be interested in the generalization ability of the learning algorithm that uses the learned metric, i.e., can we derive generalization guarantees for the learned model in terms of the quality of the learned metric?

In practice, the learned metric is plugged into a learning algorithm and one can only hope that it yields good results. Although some approaches optimize the metric based on the decision rule of classification algorithms such as k-nearest neighbors, this question has never been investigated in a formal way. As we will see later in this document, the recently-proposed theory of ( , γ, τ )-good similarity function (Balcan et al., 2008a,b) has been the first attempt to bridge the gap between the properties of a similarity function and its performance in linear classification, but has not been used so far in the context of metric learning. This theory plays a central role in two of our contributions.

The limitations described above constitute the main motivation for this thesis, and our contributions address them in several ways. First, we introduce a string kernel The two-fold problem of generalization in metric learning. We are interested in the generalization ability of the learned metric itself: can we say anything about its consistency on unseen data drawn from the same distribution? Furthermore, we are interested in the generalization ability of the learned model using that metric: can we relate its performance on unseen data to the quality of the learned metric? that allows the use of learned edit distances in kernel-based methods such as support vector machines. This provides a way to use these learned metrics in global classifiers.

Second, we propose two metric learning approaches based on ( , γ, τ )-goodness, for which generalization guarantees can be derived both for the learned metric itself and for a linear classifier built from that metric. In the first approach (which deals with structured data), the metric is optimized with respect to local pairs to ensure the optimality of the solution. In the second approach, dealing with feature vectors allows us to optimize a global criterion that is more appropriate to linear classification. Lastly, we introduce a general framework that can be used to derive generalization guarantees for many existing metric learning methods based on local constraints.

Context of this work

This thesis was carried out in the machine learning team of Laboratoire Hubert Curien UMR CNRS 5516, part of University of Saint-Étienne and University of Lyon. The contributions presented in this thesis were developed in the context of the ANR project Lampada1 (ANR-09-EMER-007), which deals with scaling learning algorithms to handle large sets of structured data, with focuses on metric learning and sparse learning, and PASCAL22 , a European Network of Excellence supporting research in machine learning, statistics and optimization.

Outline of the thesis This dissertation is organized as follows. Part I reviews the background work relevant to this thesis:

• Chapter 2 formally introduces the scientific context: supervised learning, analytical frameworks for deriving generalization guarantees, and various types of metrics.

• Chapter 3 is a large survey of supervised metric learning from feature vectors and structured data, with a focus on the relative merits and limitations of the methods of the literature.

Part II gathers our contributions on metric learning from structured data:

• Chapter 4 introduces a new string kernel based on learned edit probabilities. Unlike other string edit kernels, it is parameter-free and guaranteed to be valid. Its naive form requires the computation of an infinite sum over all finite strings that can be built from the alphabet. We show how to get round this problem by using intersection of probabilistic automata and algebraic manipulation. Experiments highlight the performance of our kernel against state-of-the-art string kernels of the literature.

• Chapter 5 builds upon the theory of ( , γ, τ )-good similarity function. We first show that we can use edit similarities directly in this framework and achieve competitive performance. The main contribution of this chapter is a novel method for learning string and tree edit similarities called GESL (for Good Edit Similarity Learning) that relies on a relaxed version of ( , γ, τ )-goodness. The proposed approach, which is more flexible than previous methods, learn an edit similarity from local pairs and is then used to build a global linear classifier. Using uniform stability arguments, we are able to derive generalization guarantees for the learned similarity that actually give an upper bound on the generalization error of the linear classifier.

We conduct extensive experiments that show the usefulness of our approach and the performance and sparsity of the resulting linear classifiers.

Part III gathers our contributions on metric learning from feature vectors:

• Chapter 6 presents a new bilinear similarity learning method for linear classification, called SLLC (for Similarity Learning for Linear Classification). Unlike GESL, SLLC directly optimizes the empirical ( , γ, τ )-goodness criterion, which makes the approach entirely global : the similarity is optimized with respect to a global criterion (instead of local pairs) and plugged in a global linear classifier. SLLC is formulated as a convex minimization problem that can be efficiently solved in a batch or online way. We also kernelize our approach, thus learning a linear similarity in a nonlinear feature space induced by a kernel. Using similar arguments as for GESL, we derive generalization guarantees for SLLC highlighting that our method actually minimizes a tighter bound on the generalization error of the classifier than GESL. Experiments on several standard datasets show that SLLC leads to competitive classifiers that have the additional advantage of being very sparse, thus speeding up prediction.

• Chapter 7 addresses the lack of general framework for establishing generalization guarantees for metric learning. It is based on a simple adaptation of algorithmic robustness to the case where training data is made of pairs of examples. We show that a robust metric learning algorithm has generalization guarantees, and furthermore that a weak notion of robustness is actually necessary and sufficient for a metric learning algorithm to generalize. We illustrate the usefulness of our approach by showing that a large class of metric learning algorithms are robust.

In particular, we are able to deal with sparsity-inducing regularizers, which was not possible with previous frameworks.

Notation Throughout this document, N denotes the set of natural numbers while R and R + respectively denote the sets of real numbers and nonnegative real numbers.

Arbitrary sets are denoted by calligraphic letters such as S, and |S| stands for the number of elements in S. A set of m elements from S is denoted by S m .

We denote vectors by bold lower case letters. For a vector x ∈ R d and i ∈ [d] = {1, . . . , d}, x i denotes the i th component of x. The inner product between two vectors is denoted by •, • . We denote matrices by bold upper case letters. For a c × d real-valued matrix M ∈ R c×d and a pair of integers (i, j) ∈ [c] × [d], M i,j denotes the entry at row i and column j of the matrix M. The identity matrix is denoted by I and the cone of symmetric positive semi-definite (PSD) d × d real-valued matrices by S d + .

• denotes an arbitrary (vector or matrix) norm and • p the L p norm. Strings are denoted by sans serif letters such as x. We use |x| to denote the length of x and x i to refer to its i th symbol.

In the context of learning problems, we use X and Y to denote the input space (or instance space) and the output space (or label space) respectively. We use Z = X ×Y to denote the joint space, and an arbitrary labeled instance is denoted by z = (x, y) ∈ Z.

The hinge function [•]

+ : R → R + is defined as [c] + = max(0, c). Pr[A] denotes the probability of the event A, E[X] the expectation of the random variable X and x ∼ P indicates that x is drawn according to the probability distribution P .

A summary of the notations is given in Table 1

PART I

Background CHAPTER 2

Preliminaries

Chapter abstract In this chapter, we introduce the scientific context of this thesis as well as relevant background work. We first introduce formally the supervised learning setting and describe the main ideas of statistical learning theory, with a focus on binary classification. We then present three analytical frameworks (uniform convergence, uniform stability and algorithmic robustness) for establishing that a learning algorithm has generalization guarantees. Lastly, we recall the definition of several types of metrics and give examples of such functions for feature vectors and structured data.

Supervised Learning

The goal of supervised learning1 is to automatically infer a model (hypothesis) from a set of labeled examples that is able to make predictions given new unlabeled data.

In the following, we review basic notions of statistical learning theory, a very popular framework pioneered by [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. The interested reader can refer to [START_REF] Vapnik | Statistical Learning Theory[END_REF] and [START_REF] Bousquet | Introduction to Statistical Learning Theory[END_REF] for a more thorough description.

Typical Setting

In supervised learning, we learn a hypothesis from a set of labeled examples. This notion of training sample is formalized below.

Definition 2.1 (Training sample).

A training sample of size n is a set T = {z i = (x i , y i )} n i=1 of n observations independently and identically distributed (i.i.d.) according to an unknown joint distribution P over the space Z = X × Y, where X is the input space and Y the output space. For a given observation z i , x i ∈ X is the instance (or example) and y i ∈ Y its label. When Y is discrete, we are dealing with a classification task, and y i is called the class of x i . When Y is continuous, this is a regression task. In this thesis, we mainly focus on binary classification tasks, where we assume Y = {-1, 1}. 10 Chapter 2. Preliminaries

We will mostly deal with feature vectors and strings. For feature vectors, we generally assume that X ⊆ R d . For strings, we need the following definition.

Definition 2.2 (Alphabet and string). An alphabet Σ is a finite nonempty set of symbols. A string x is a finite sequence of symbols from Σ. The empty string/symbol is denoted by $ and Σ * is the set of all finite strings (including $) that can be generated from Σ. Finally, the length of a string x is denoted by |x|.

We can now formally define what we mean by supervised learning.

Definition 2.3 (Supervised learning). Supervised learning is the task of inferring a function (often referred to as a hypothesis or a model) h T : X → L belonging to some hypothesis class H from a training sample T , which "best" predicts y from x for any (x, y) drawn from P . Note that the decision space L may or may not be equal to Y.

In order to choose h T , we need a criterion to assess the quality of an arbitrary hypothesis h. Given a nonnegative loss function : H×Z → R + measuring the degree of agreement between h(x) and y, we define the notion of true risk.

Definition 2.4 (True risk). The true risk (also called generalization error) R (h) of a hypothesis h with respect to a loss function is the expected loss suffered by h over the distribution P : R (h) = E z∼P [ (h, z)] .

The most natural loss function for binary classification is the 0/1 loss (also called classification error):

0/1 (h, z) = 1 if yh(x) < 0 0 otherwise.
R 0/1 (h) then corresponds to the proportion of time h(x) and y agree in sign, and in particular to the proportion of correct predictions when L = Y.

The goal of supervised learning is then to find a hypothesis that achieves the smallest true risk. Unfortunately, in general we cannot compute the true risk of a hypothesis since the distribution P is unknown. We can only measure it empirically on the training sample. This is called the empirical risk.

Definition 2.5 (Empirical risk). Let T = {z i = (x i , y i )} n i=1 be a training sample. The empirical risk (also called empirical error) R T (h) of a hypothesis h over T with respect to a loss function is the average loss suffered by h on the instances in T :

R T (h) = 1 n n i=1 (h, z i ).
Under some restrictions, using the empirical risk to select the best hypothesis is a good strategy, as discussed in the next section.

Finding a Good Hypothesis

This section focuses on classic strategies for finding a good hypothesis in the true risk sense. The derivation of guarantees on the true risk of the selected hypothesis will be studied in Section 2.2.

Simply minimizing the empirical risk over all possible hypotheses would obviously be a good strategy if infinitely many training instances were available. Unfortunately, in realistic scenarios, training data is limited and there always exists a hypothesis h, however complex, that perfectly predicts the training sample, i.e., R T (h) = 0, but generalizes poorly, i.e., h has a nonzero (potentially large) true risk. This situation where the true risk of a hypothesis is much larger than its empirical risk is called overfitting.

The intuitive idea behind it is that learning the training sample "by heart" does not provide good generalization to unseen data.

There is therefore a trade-off between minimizing the empirical risk and the complexity of the considered hypotheses, known as the bias-variance trade-off. There essentially exist two ways to deal with it and avoid overfitting: (i) restrict the hypothesis space, and (ii) favor simple hypotheses over complex ones. In the following, we briefly present three classic strategies for finding a hypothesis with small true risk.

Empirical Risk Minimization

The idea of the Empirical Risk Minimization (ERM)

principle is to pick a restricted hypothesis space H ⊂ L X (for instance, linear classifiers, decision trees, etc.) and select a hypothesis h T ∈ H that minimizes the empirical risk:

h T = arg min h∈H R T (h).
This may work well in practice but depends on the choice of hypothesis space. Essentially, we want H large enough to include hypotheses with small risk, but H small enough to avoid overfitting. Without background knowledge on the task, picking an appropriate H is difficult. This implements the Occam's razor principle according to which one should choose the simplest explanation consistent with the training data.

Structural Risk Minimization

Regularized Risk Minimization Regularized Risk Minimization (RRM) also builds upon the Occam's razor principle but is easier to implement: one picks a single, large hypothesis space H and a regularizer (usually some norm h ) and selects a hypothesis that achieves the best trade-off between empirical risk minimization and regularization:

h T = arg min h∈H R T (h) + λ h , (2.1)
where λ is the trade-off parameter (in practice, it is set using validation data). The role of regularization is to penalize "complex" hypotheses. Note that it also provides a built-in way to break the tie between hypotheses that have the same empirical risk.

The choice of regularizer is important and depends on the considered task and the desired effect. Common regularizers for vector and matrix models are given in Table 2.1 and Table 2.2 respectively. Some regularizers are easy to optimize because they are convex and smooth (for instance, the squared L 2 norm) while others do not have these convenient properties and are thus harder to deal with (see Figure 2.1 for a graphical insight into some of these regularizers). However, the latter may bring some potentially interesting effects such as sparsity: they tend to set some parameters of the hypothesis to zero. Figure 2.2 illustrates this on L 2 and L 1 constraints -this also holds for regularization.2

L 2 norm L 1 norm L 2,1 norm Figure 2
.1: 3D unit balls of the L 1 , L 2 and L 2,1 norms (taken from [START_REF] Grandvalet | Sparsity in learning[END_REF]. The L 2 norm is convex, smooth and does not induce sparsity. The L 1 norm is convex, nonsmooth and induces sparsity at the coordinate level. The L 2,1 norm is convex, nonsmooth and induces sparsity at the group level (simultaneous sparsity of coordinates belonging to the same predefined group).

L 1 constraint L 2 constraint Figure 2
.2: Geometric interpretation of L 2 and L 1 constraints in 2D. Suppose that we are looking for a hypothesis h ∈ R 2 with a constraint h ≤ β (represented in dark blue) that minimizes the empirical risk (represented by the light green contour line). Unlike the L 2 norm, the L 1 norm tends to zero out coordinates, thus reducing dimensionality.

Regularization is used in many successful learning methods and, as we will see in Section 2.2, may help deriving generalization guarantees.

Surrogate Loss Functions

The methods described above all rely on minimizing the empirical risk. However, due to the nonconvexity of the 0/1 loss, minimizing (or approximately minimizing) R 0/1 is known to be NP-hard even for simple hypothesis classes [START_REF] Ben-David | On the difficulty of approximately maximizing agreements[END_REF]. For this reason, surrogate convex loss functions (that can be more efficiently handled) are often used. The most prominent choices in the context of binary classification are:

• the hinge loss: hinge (h, z) = [1yh(x)] + = max(0, 1yh(x)), used for instance in support vector machines [START_REF] Cortes | Support-Vector Networks[END_REF].

• the exponential loss: exp (h, z) = e -yh(x) , used in Adaboost [START_REF] Freund | A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting[END_REF].

corresponding regularized problem such that both problems have the same set of solutions, and vice versa. In practice, regularized problems are more convenient to use because they are always feasible. • the logistic loss: log (h, z) = log(1 + -yh(x) ), used in Logitboost [START_REF] Friedman | Additive Logistic Regression: a Statistical View of Boosting[END_REF].

These loss functions are plotted in Figure 2.3 along with the nonconvex 0/1 loss.

Choosing an appropriate loss function is not an easy task and strongly depends on the problem, but there exist general results on the relative merits of different loss functions.

For instance, [START_REF] Rosasco | Are Loss Functions All the Same? Neural Computation[END_REF] studied statistical properties of several convex loss functions in a general classification setting and concluded that the hinge loss has a better convergence rate than other loss functions. [START_REF] Ben-David | Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss[END_REF] have further shown that in the context of linear classification, the hinge loss offers the best guarantees in terms of classification error.

In the following section, we present analytical frameworks that allow the derivation of generalization guarantees, i.e., relating the empirical risk of h T to its true risk.

Deriving Generalization Guarantees

In the previous section, we described a few generic methods for learning a hypothesis h T from a training sample T based on minimizing the (penalized) empirical risk. However, learning a hypothesis with small true risk is what we are really interested in. Typically, the empirical risk can be seen as an optimistically biased estimation of the true risk (especially when the training sample is small), and a considerable amount of research has gone into deriving generalization guarantees for learning algorithms, i.e., bounding the deviation of the true risk of the learned hypothesis from its empirical measurement.

These bounds are often referred to as PAC (Probably Approximately Correct) bounds [START_REF] Valiant | A theory of the learnable[END_REF] and have the following form:

Pr[|R (h) -R T (h)| > ] ≤ δ,
where ≥ 0 and δ ∈ [0, 1]. In other words, it bounds the probability to observe a large gap between the true risk and the empirical risk of an hypothesis.

The key instruments for deriving PAC bounds are concentration inequalities. They essentially assess the deviation of some functions of independent random variables from their expectation. Different concentration inequalities tackle different functions of the variables. The most commonly used in machine learning are Chebyshev (only one variable is considered), Hoeffding (sums of variables) and McDiarmid (that can accommodate any sufficiently regular function of the variables). For more details about concentration inequalities, see for instance the survey of [START_REF] Boucheron | Concentration Inequalities[END_REF].

In this section, we present three theoretical frameworks for establishing generalization bounds: uniform convergence, uniform stability and algorithmic robustness (for a more general overview, please refer to the tutorial by [START_REF] Langford | Tutorial on Practical Prediction Theory for Classification[END_REF]. Note that our contributions in Chapter 5, Chapter 6 and Chapter 7 make use of these frameworks.

Uniform Convergence

The theory of uniform convergence of empirical quantities to their mean [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF][START_REF] Vapnik | Estimation of Dependences Based on Empirical Data[END_REF] is one of the most prominent tools for deriving generalization bounds. It provides guarantees that hold for any hypothesis h ∈ H (including h T ) and essentially bounds (with some probability 1δ) the true risk of h by its empirical risk plus a penalty term that depends on the number of training examples n, the size (or complexity) of the hypothesis space H and the value of δ. Intuitively, large n brings high confidence (since as n → ∞ the empirical risk converges to the true risk by the law of large numbers), complex H brings low confidence (since overfitting is more likely), and δ accounts for the probability of drawing an "unlucky" training sample (i.e., not representative of the underlying distribution P ).

When the hypothesis space is finite, we get the following PAC bound in O(1/ √ n).

Theorem 2.6 (Uniform convergence bound for the finite case). Let T be a training sample of size n drawn i.i.d. from some distribution P , H a finite hypothesis space and δ > 0. For any h ∈ H, with probability 1δ over the random sample T , we have:

R (h) ≤ R T (h) + ln |H| + ln(1/δ) 2n .
When H is continuous (for instance, if H is the space of linear classifiers), we need a measure of the complexity of H such as 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] Noga Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF] or the Rademacher complexity [START_REF] Koltchinskii | Rademacher penalties and structural risk minimization[END_REF][START_REF] Bartlett | Rademacher and Gaussian Complexities: Risk Bounds and Structural Results[END_REF]. For instance, using the VC dimension, we get the following bound.

Theorem 2.7 (Uniform convergence bound with VC dimension). Let T be a training sample of size n drawn i.i.d. from some distribution P , H a continuous hypothesis space with VC dimension V C(H) and δ > 0. For any h ∈ H, with probability 1δ over the random sample T , we have:

R (h) ≤ R T (h) + V C(H) ln 2n V C(H) + 1 + ln(4/δ) n .
A drawback of uniform convergence analysis is that it is only based on the size of the training sample and the complexity of the hypothesis space, and completely ignores the learning algorithm, i.e., how the hypothesis h T is selected. 3 In the following, we present two analytical frameworks that explicitly take into account the algorithm and can be used to derive generalization guarantees for h T specifically, in particular in the regularized risk minimization setting (2.1).

Uniform Stability

Building on previous work on algorithmic stability, [START_REF] Bousquet | Algorithmic Stability and Generalization Performance[END_REF], 2002) introduced new definitions that allow the derivation of generalization bounds for a large class of algorithms. Intuitively, an algorithm is said stable if it is robust to small changes in its input (in our case, the training sample), i.e., the variation in its output is small.

Formally, we focus on uniform stability, a version of stability that allows the derivation of rather tight bounds.

Definition 2.8 (Uniform stability). An algorithm A has uniform stability κ/n with respect to a loss function if the following holds:

∀T , |T | = n, ∀i ∈ [n] : sup z | (h T , z) -(h T i , z)| ≤ κ n ,
where κ is a positive constant, T i is obtained from the training sample T by replacing the i th example z i ∈ T by another example z i drawn i.i.d. from P , h T and h T i are the hypotheses learned by A from T and T i respectively. 4Bousquet [START_REF] Bousquet | Algorithmic Stability and Generalization Performance[END_REF][START_REF] Bousquet | Stability and Generalization[END_REF] Theorem 2.9 (Uniform stability bound). Let T be a training sample of size n drawn i.i.d. from some distribution P and δ > 0. For any algorithm A with uniform stability κ/n with respect to a loss function upper-bounded by some constant B,5 with probability 1δ over the random sample T , we have:

R (h T ) ≤ R T (h T ) + κ n + (2κ + B) ln(1/δ) 2n ,
where h T is the hypothesis learned by A from T .

The main difference between uniform convergence and uniform stability is that the latter incorporates regularization (through κ and h T ) and does not require any hypothesis space complexity argument. In particular, uniform stability can be used to derive generalization guarantees for hypothesis classes that are difficult to analyze with classic complexity arguments, such as k-nearest neighbors or support vector machines that have infinite VC dimension. It can also be adapted to non-i.i.d. settings [START_REF] Mohri | Stability bounds for non-i.i.d. processes[END_REF], 2010). We will use uniform stability in the contributions presented in Chapter 5 and Chapter 6.

On the other hand, Xu et al. (2012a) have shown that algorithms with sparsity-inducing regularization are not stable.6 Algorithmic robustness, presented in the next section, is able to deal with such algorithms. We will make use of this framework in Chapter 7.

Algorithmic Robustness

Algorithmic robustness [START_REF] Xu | Robustness and Generalization[END_REF], 2012) is the ability of an algorithm to perform "similarly" on a training example and on a test example that are "close". It relies on a partitioning of the space Z to characterize closeness: two examples are close to each other if they lie in the same partition of the space. The partition itself is based on the notion of covering number [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF].

Definition 2.10 (Covering number). For a metric space (S, ρ) and V ⊂ S, we say that

V ⊂ V is a γ-cover of V if ∀t ∈ V, ∃ t ∈ V such that ρ(t, t) ≤ γ. The γ-covering number of V is N (γ, V, ρ) = min | V| : V is a γ-cover of V .
In particular, when X is compact, N (γ, X , ρ) is finite, leading to a finite cover. Then, Z can be partitioned into |Y|N (γ, X , ρ) subsets such that if two examples z = (x, y) and z = (x , y ) belong to the same subset, then y = y and ρ(x, x ) ≤ γ.

We can now formally define the notion of robustness.

Definition 2.11 (Algorithmic robustness). Algorithm A is (K, (•))-robust, for K ∈ N and (•) : Z n → R, if Z can be partitioned into K disjoint sets, denoted by {C i } K i=1 , such that the following holds for all T ∈ Z n :

∀z ∈ T , ∀z ∈ Z, ∀i ∈ [K] : if z, z ∈ C i , then | (h T , z) -(h T , z )| ≤ (T ),
where h T is the hypothesis learned by A from T .

Briefly speaking, an algorithm is robust if for any example z falling in the same subset as a training example z, then the gap between the losses associated with z and z is bounded (by a quantity that may depend on the training sample T ). The existence of the partition itself is guaranteed by the definition of covering number. Note that both uniform stability and algorithmic robustness properties involve a bound on deviations between losses. The key difference is that uniform stability studies the variation of the loss associated with any example z under small changes in the training sample (implying that the learned hypothesis itself does not vary much), while algorithmic robustness considers the deviation between the losses associated with two examples that are close (implying that the learned hypothesis is locally consistent). [START_REF] Xu | Robustness and Generalization[END_REF], 2012) have shown that a robust algorithm has generalization guarantees. This is formalized by the following theorem.

Theorem 2.12 (Robustness bound). Let be a loss function upper-bounded by some constant B, and δ > 0. If an algorithm A is (K, (•))-robust, then with probability 1δ, we have:

R (h T ) ≤ R T (h T ) + (T ) + B 2K ln 2 + 2 ln(1/δ) n ,
where h T is the hypothesis learned by A from T .

Note that there is a tradeoff between the size K of the partition and (T ): the latter can essentially be made as small as possible by using a finer-grained cover.

PAC bounds based on robustness are generally not tight since they rely on unspecified (potentially large) covering numbers. On the other hand, a great advantage of robustness is that it can deal with a larger class of regularizers than stability (in particular, sparsity-inducing norms can be considered), and its geometric interpretation makes adaptations to non-standard settings (such as non-i.i.d. data) possible. Our contribution in Chapter 7 adapts robustness to the case of metric learning, when training data consist of non-i.i.d. pairs of examples. Finally, note that [START_REF] Xu | Robustness and Generalization[END_REF], 2012) established that a weak notion of robustness is necessary and sufficient for an algorithm to generalize asymptotically, making robustness a key property for the generalization of learning algorithms.

After having presented the supervised learning setting and analytical frameworks for deriving generalization guarantees, we now turn to the topic of metrics, which has a great place in this thesis.

Metrics

The notion of metric (used here as a generic term for distance, similarity or dissimilarity function) plays an important role in many machine learning problems such as classification, regression, clustering, or ranking. Successful examples include:

• k-Nearest Neighbors (k-NN) classification [START_REF] Cover | Nearest neighbor pattern classification[END_REF], where the predicted class of an instance x corresponds to the majority class among the k-nearest neighbors of x in the training sample, according to some distance or similarity.

• Kernel methods [START_REF] Schölkopf | Learning With Kernels, Support Vector Machines, Regularization, Optimization, and Beyond[END_REF], where a specific type of similarity function called kernel (see Definition 2.15) is used to implicitly project data into a new high-dimensional feature space. The most prominent example is Support

Vector Machines (SVM) classification [START_REF] Cortes | Support-Vector Networks[END_REF], where a largemargin linear classifier is learned in that space.

• K-Means [START_REF] Stuart | Least squares quantization in PCM[END_REF], a clustering algorithm which aims at finding the K clusters that minimize the within-cluster distance on the training sample according to some metric.

• Information retrieval, where a similarity function is often used to retrieve documents (webpages, images, etc.) that are similar to a query or to another document [START_REF] Salton | A vector space model for automatic indexing[END_REF][START_REF] Baeza | Modern Information Retrieval[END_REF][START_REF] Sivic | Efficient visual search of videos cast as text retrieval[END_REF].

• Data visualization, where visualization of interesting patterns in high-dimensional data is sometimes achieved by means of a metric [START_REF] Venna | Information Retrieval Perspective to Nonlinear Dimensionality Reduction for Data Visualization[END_REF][START_REF] Bertini | Quality Metrics in High-Dimensional Data Visualization: An Overview and Systematization[END_REF].

It should be noted that metrics are especially important when dealing with structured data (such as strings, trees, or graphs) because they are often a convenient proxy to manipulate these complex objects: if a metric is available, then any metric-based algorithm (such as those presented in the above list) can be used.

In this section, we first give the definitions of distance, similarity and kernel functions (2.3.1), and then give some examples (by no means an exhaustive list) of such metrics between feature vectors (2.3.2) and between structured data (2.3.3).

Definitions

We start by introducing the definition of a distance function.

Definition 2.13 (Distance function). A distance over a set X is a pairwise function d : X × X → R which satisfies the following properties ∀x, x , x ∈ X :

1. d(x, x ) ≥ 0 (nonnegativity), 2. d(x, x ) = 0 if and only if x = x (identity of indiscernibles), 3. d(x, x ) = d(x , x) (symmetry), 4. d(x, x ) ≤ d(x, x ) + d(x , x ) (triangle inequality).
A pseudo-distance satisfies the properties of a metric, except that instead of property 2, only d(x, x) = 0 is required. Note that the property of triangle inequality can be used to speedup learning algorithms such as k-NN (e.g., [START_REF] Micó | A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements[END_REF][START_REF] Jim | Fast k-nearest-neighbor search based on projection and triangular inequality[END_REF][START_REF] Wang | Fast Exact k-Nearest Neighbors Algorithm for High Dimensional Search Using k-Means Clustering and Triangle Inequality[END_REF] or K-Means [START_REF] Elkan | Using the Triangle Inequality to Accelerate k-Means[END_REF].

While a distance function is a well-defined mathematical concept, there is no general agreement on the definition of a (dis)similarity function, which can essentially be any pairwise function. Throughout this thesis, we will use the following definition.

Definition 2.14 (Similarity function). A (dis)similarity function is a pairwise function

K : X × X → [-1, 1]. We say that K is a symmetric similarity function if ∀x, x ∈ X , K(x, x ) = K(x , x).
A similarity function should return a high score for similar inputs and a low score for dissimilar ones (the other way around for a dissimilarity function). Note that (normalized) distance functions are dissimilarity functions.

Finally, a kernel is a special type of similarity function, as formalized by the following definition.

Definition 2.15 (Kernel function). A symmetric similarity function K is a kernel if there exists a (possibly implicit) mapping function φ : X → H from the instance space X to a Hilbert space H such that K can be written as an inner product in H:

K(x, x ) = φ(x), φ(x ) . Equivalently, K is a kernel if it is 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 of x 1 , . . . , x n ∈ X and c 1 , . . . , c n ∈ R.

Kernel functions are a key component of kernel methods such as SVM, because they can implicitly allow cheap inner product computations in very high-dimensional spaces (this is known as the "kernel trick") and bring an elegant theory based on Reproducing Kernel Hilbert Spaces (RKHS). Note that these advantages disappear when using an arbitrary non-PSD similarity function instead of a kernel, and the convergence of the kernel-based algorithm may not even be guaranteed in this case. 7

Some Metrics between Feature Vectors

Minkowski distances Minkowski distances are a family of distances induced by L p norms. For p ≥ 1,

d p (x, x ) = x -x p = d i=1 |x i -x i | p 1/p . (2.2)
From (2.2) we can recover three widely used distances:

• When p = 1, we get the Manhattan distance:

d man (x, x ) = x -x 1 = d i=1 |x i -x i |.
• When p = 2, we get the "ordinary" Euclidean distance:

d euc (x, x ) = x -x 2 = d i=1 |x i -x i | 2 1/2 = (x -x ) T (x -x ).
• When p → ∞, we get the Chebyshev distance:

d che (x, x ) = x -x ∞ = max i |x i -x i |.
Note that when 0 < p < 1, d p is not a proper distance (it violates the triangle inequality)

and the corresponding (pseudo) norm is nonconvex. Figure 2.4 shows the corresponding unit circles for several values of p.

Mahalanobis distances

The Mahalanobis distance, which incorporates knowledge about the correlation between features, is defined by

d Σ -1 (x, x ) = (x -x ) T Σ -1 (x -x ),
7 Some research has gone into training SVM with indefinite kernels, mostly based on building a PSD kernel from the indefinite one while learning the SVM classifier. The interested reader may refer to the work of [START_REF] Cheng | Learning with non-positive kernels[END_REF]; Luss & d'Aspremont (2007); [START_REF] Chen | Training SVM with indefinite kernels[END_REF]; [START_REF] Chen | Learning kernels from indefinite similarities[END_REF] and references therein. where x and x are random vectors from the same distribution with covariance matrix Σ. The term Mahalanobis distance is also used to refer to the following generalization of the original definition, sometimes referred to as generalized quadratic distances [START_REF] Nielsen | Sided and symmetrized Bregman centroids[END_REF]:

p → 0 p = 0.3 p = 0.5 p = 1 p = 1.5 p = 2 p → ∞
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-valued matrices. M ∈ S d + ensures that d M is a pseudo-distance.
When M is the identity matrix, we recover the Euclidean distance. Otherwise, using Cholesky decomposition, one can rewrite M as L T L, where L ∈ R k×d , where k is the rank of M. Hence:

d M (x, x ) = (x -x ) T M(x -x ) = (x -x ) T L T L(x -x ) = (Lx -Lx ) T (Lx -Lx ).
Thus, a Mahalanobis distance implicitly corresponds to computing the Euclidean distance after the linear projection of the data defined by L. Note that if M is low-rank, i.e., rank(M) = r < d, then it induces a linear projection of the data into a space of lower dimension r. It thus allows a more compact representation of the data and cheaper distance computations, especially when the original feature space is high-dimensional.

Because of these nice properties, learning Mahalanobis distance has attracted a lot of interest and is a major component of metric learning (see Section 3.2.1).

Cosine similarity

The cosine similarity measures the cosine of the angle between two instances, and can be computed as

K cos (x, x ) = x T x x 2 x 2 .
The cosine similarity is widely used in data mining, in particular in text retrieval [START_REF] Baeza | Modern Information Retrieval[END_REF] and more recently in image retrieval (see for instance [START_REF] Sivic | Efficient visual search of videos cast as text retrieval[END_REF] when data are represented as term vectors [START_REF] Salton | A vector space model for automatic indexing[END_REF].

Bilinear similarity

The bilinear similarity is related to the cosine similarity but does not include normalization by the norms of the inputs and is parameterized by a matrix M:

K M (x, x ) = x T Mx ,
where M ∈ R d×d is not required to be PSD nor symmetric. The bilinear similarity has been used for instance in image retrieval [START_REF] Deng | Hierarchical semantic indexing for large scale image retrieval[END_REF]. When M is the identity matrix, K M amounts to an unnormalized cosine similarity. The bilinear similarity has two advantages. First, it is efficiently computable for sparse inputs: if x and x have k 1 and k 2 nonzero features,

K M (x, x ) can be computed in O(k 1 k 2 ) time. Second, unlike
Minkowski distance, Mahalanobis distances and the cosine similarity, it can be easily used as a similarity measure between instances of different dimension (for example, a document and a query) by choosing a nonsquare matrix M. A major contribution of this thesis is to propose a novel method for learning a bilinear similarity (Chapter 6).

Linear kernel The linear kernel is simply the inner product in the original space X :

K lin (x, x ) = x, x = x T x .
In other words, the corresponding φ is an identity map: ∀x ∈ X , φ(x) = x. Note that K lin corresponds to the bilinear similarity with M = I.

Polynomial kernels Polynomial kernels are defined as:

K deg (x, x ) = ( x, x + 1) deg ,
where deg ∈ N. It can be shown that K deg implicitly projects an instance into the nonlinear space H of all monomials of degree up to deg.

Gaussian kernel

The Gaussian kernel, also known as the RBF kernel, is a widely used kernel defined by

K gaus (x, x ) = exp - x -x 2 2 2σ 2 ,
where σ 2 > 0 is a width parameter. For this kernel, it can be shown that the corresponding implicit nonlinear projection space H is infinite-dimensional.

Some Metrics between Structured Data

Hamming distance The Hamming distance is a distance between strings of identical length and is equal to the number of positions at which the symbols differ. It has been used mostly for binary strings and is defined by

d ham (x, x ) = |{i : x i = x i }|.
String edit distance The 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 length built from an alphabet Σ. It is based on three elementary edit operations: insertion, deletion and substitution of a symbol. In the more general version, each operation has a specific cost, gathered in a nonnegative (|Σ| + 1) × (|Σ| + 1) matrix C (the additional row and column account for insertion and deletion costs respectively). A sequence of operations transforming a string x into a string x is called an edit script. The edit distance between x and x is defined as the cost of the cheapest edit script that turns x into x and can be computed in O(|x|

• |x |)
time by dynamic programming.8

The classic edit distance, known as the Levenshtein distance, uses a unit cost matrix and thus corresponds to the minimum number of operations turning one string into another.

For instance, the Levenshtein distance between abb and aa is equal to 2, since turning abb into aa requires at least 2 operations (e.g., substitution of b with a and deletion of b). On the other hand, using the cost matrix given in Table 2.3, the edit distance between abb and aa is equal to 10 (deletion of a and two substitutions of b with a is the cheapest edit script).

Using task-specific costs is a key ingredient to the success of the edit distance in many applications. For some problems such as handwritten character recognition [START_REF] Micó | Comparison of fast nearest neighbour classifiers for handwritten character recognition[END_REF] or protein alignment [START_REF] Dayhoff | A model of evolutionary change in proteins[END_REF][START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF], relevant cost matrices may be available. But a more general solution consists in automatically learning the cost matrix from data, as we shall see in Section 3.3.1. One of the contributions of this thesis is to propose a new edit cost learning method (Chapter 5).

Sequence alignment Sequence alignment is a way of computing the similarity between two strings, mostly used in bioinformatics to identify regions of similarity in DNA or protein sequences [START_REF] Mount | Bioinformatics: Sequence and Genome Analysis[END_REF]. It corresponds to the score of the best alignment. The score of an alignment is based on the same elementary operations as the Tree edit distance Because of the growing interest in applications that naturally involve tree-structured data (such as the secondary structure of RNA in biology, XML documents on the web or parse trees in natural language processing), several works have extended the string edit distance to trees, resorting to the same elementary edit operations (see [START_REF] Bille | A survey on tree edit distance and related problems[END_REF], for a survey on the matter). There exist two main variants of the tree edit distance that differ in the way the deletion of a node is handled. In Zhang & Shasha (1989), when a node is deleted all its children are connected to its father.

The best algorithms for computing this distance have an O(n 3 ) worst-case complexity,

where n is the number of nodes of the largest tree (see [START_REF] Pawlik | RTED: a robust algorithm for the tree edit distance[END_REF], for an empirical evaluation of several algorithms). Another variant is due to [START_REF] Stanley | The tree-to-tree editing problem[END_REF],

where insertions and deletions are restricted to the leaves of the tree. Such a distance is relevant to specific applications. For instance, deleting a <UL> tag (i.e., a nonleaf node) of an unordered list in an HTML document would require the iterative deletion of the <LI> items (i.e., the subtree) first, which is a sensible thing to do in this context (see Figure 2.5). This version can be computed in quadratic time. Note that tree edit distance computations can be made significantly faster (especially for large trees) by exploiting lower bounds on the distance between two trees that are cheap to obtain (see for instance [START_REF] Yang | Similarity evaluation on treestructured data[END_REF]. A study on the expressiveness of similarities and distances on trees was proposed by [START_REF] Emms | On Order Equivalences between Distance and Similarity Measures on Sequences and Trees[END_REF].

Like in the string case, there exists a few methods for learning the cost matrix of the tree edit distance (see Section 3.3.2). Note that our edit similarity learning method, presented in Chapter 5, can be used for both strings and trees.

Graph edit distance Note that there also exist extensions of the edit distance to general graphs [START_REF] Gao | A survey of graph edit distance[END_REF], but like many problems on graphs, computing a graph edit distance is NP-hard, making it impractical for real-world tasks.

Spectrum, subsequence and mismatch kernels These string kernels represent strings by fixed-length feature vectors and rely on explicit mapping functions φ. The spectrum kernel (Leslie et al., 2002a) maps each string to a vector of frequencies of all contiguous subsequences of length p and computes the inner product between these vectors. The subsequence kernel [START_REF] Lodhi | Text Classification using String Kernels[END_REF] and the mismatch kernel (Leslie et al., 2002b) extend the spectrum kernel to inexact subsequence matching: the former considers all (possibly noncontiguous) subsequences of length p while the latter allows a number of mismatches in the subsequences.

String edit kernels String edit kernels are derived from the string edit distance (or related measures). The classic edit kernel [START_REF] Li | A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs[END_REF] has the following form: x ) , where d lev is the Levenshtein distance and t > 0 is a parameter. However, [START_REF] Cortes | Rational Kernels: Theory and Algorithms[END_REF] have shown that this function is not PSD (and thus is not a valid kernel) in the general case for nontrivial alphabets. Thus, one has to tune t, hoping to make K PSD.

K L&J (x, x ) = e -t•d lev (x,
Moreover, it suffers from the so-called "diagonal dominance" problem (i.e., the kernel value decreases exponentially fast with the distance), and SVM is known not to perform well in this case [START_REF] Schölkopf | Noble. A Kernel Approach for Learning from almost Orthogonal Patterns[END_REF]. A different string edit kernel was proposed by [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF] and is defined as follows:

K N &B (x, x ) = 1 2 (d lev (x, x 0 ) 2 + d lev (x 0 , x ) 2 -d lev (x, x ) 2 ),
where x 0 is called the "zero string" and must be picked by hand. They also propose combinations of such kernels with different zero strings. However, the validity of such kernels is not guaranteed either. [START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF] build a kernel from the sum of scores over all possible Smith-Waterman local alignments between two strings instead of the alignment of highest score only. They show that if the score matrix is PSD, then the kernel is valid in general. However, like K L&J , it suffers from the diagonal dominance problem. In practice, the authors take the logarithm of the kernel and add a sufficiently large diagonal term to ensure the validity of the kernel.

Convolution kernels

The framework of convolution kernels [START_REF] Haussler | Convolution Kernels on Discrete Structure[END_REF] can be used to derive many kernels for structured data. Roughly speaking, if structured instances can be seen as a collection of subparts, then Haussler's convolution kernel between two instances is defined as the sum of the return values of a predefined kernel over all possible pairs of subparts, and is guaranteed to be PSD. Mapping kernels [START_REF] Shin | A generalization of Haussler's convolution kernel: mapping kernel[END_REF] are a generalization of convolution kernels as they allow the sum to be computed only over a predefined subset of the subpart pairs. These frameworks have been used to design several kernels between structured data [START_REF] Collins | Convolution Kernels for Natural Language[END_REF][START_REF] Shin | A generalization of Haussler's convolution kernel: mapping kernel[END_REF][START_REF] Shin | Mapping kernels for trees[END_REF]. However, building such kernels is often not straightforward since they suppose the existence of a kernel between subparts of the structured instances.

Marginalized kernels When one has access to a probabilistic model encoding for instance the probability that a string (or a tree) is turned into another one, marginalized kernels [START_REF] Tsuda | Marginalized kernels for biological sequences[END_REF][START_REF] Kashima | Marginalized Kernels Between Labeled Graphs[END_REF], of which the Fisher kernel [START_REF] Jaakkola | Exploiting generative models in discriminative classifiers[END_REF]) is a special case, are a way of building a kernel from the output of such models. Since our string kernel proposed in Chapter 4 belongs to this family, we postpone the details of the framework to Section 4.2.

Conclusion

In this chapter, we introduced the setting of supervised learning, presented analytical frameworks that allow the derivation of generalization bounds for learning algorithms, and reviewed different forms of metrics.

The contributions of this thesis can be cast as supervised metric learning methods, i.e., learning the parameters of a metric from labeled data. Because the performance of many learning algorithms using metrics critically depends on the relevance of the metric to the problem at hand, supervised metric learning has attracted a lot of interest in recent years. Chapter 3 is a large review of the literature on the subject.

CHAPTER 3

A Review of Supervised Metric Learning

Chapter abstract In this chapter, we review the literature on supervised metric learning. We start by introducing the main concepts of this research topic. Then, we cover metric learning from feature vectors (in particular, Mahalanobis distance learning) as well as metric learning from structured data such as strings and trees, with an emphasis on the pros and cons of each method. Finally, we conclude by discussing the general limitations of the current literature that motivate our work.

Introduction

As discussed in Section 2.3, using an appropriate metric is key to the performance of many learning algorithms. Since manually tuning metrics (when they allow some parameterization) for a given real-world problem is often difficult and tedious, a lot of work has gone into automatically learning them from labeled data, leading to the emergence of metric learning. This chapter is devoted to a large survey of supervised metric learning techniques.

Generally speaking, supervised metric learning approaches rely on the reasonable intuition that a good similarity function should assign a large (resp. small) score to pairs of points of the same class (resp. different class), and conversely for a distance function.

Following this idea, they aim at finding the parameters (usually a matrix) of the metric such that it best satisfies local constraints built from the training sample T . They are typically pair or triplet-based constraints of the following form: S = {(z i , z j ) ∈ T × T : x i and x j should be similar}, The rest of this chapter is organized as follows. Section 3.2 reviews metric learning approaches where data consist of feature vectors while Section 3.3 deals with metric learning from structured data. We conclude with a summary of the main features of the studied approaches and a discussion on some of their limitations in Section 3.4.

D = {(z i , z j ) ∈ T × T : x i and x j should be dissimilar}, R = {(z i , z j , z k ) ∈ T × T × T : x i should

Metric Learning from Feature Vectors

In this section, we focus on metric learning methods for data lying in some feature space X ⊆ R d . In Section 3.2.1, we review Mahalanobis distance learning, which has attracted most of the interest, as well as similarity learning in Section 3.2.2 and nonlinear metric learning in Section 3.2.3. Finally, we list a few approaches designed for other settings in Section 3.2.4.

Mahalanobis Distance Learning

A great deal of work has focused on learning a (squared) Mahalanobis distance d 2

M

parameterized by M ∈ S d + . Maintaining M ∈ S d + in an efficient way during the optimization process is a key challenge in Mahalanobis distance learning. Indeed, general Semi-Definite Programming (SDP) techniques [START_REF] Vandenberghe | Semidefinite Programming[END_REF], i.e., optimization over the PSD cone, consists in repeatedly performing a gradient step on the objective function followed by a projection step onto the PSD cone (which is done by setting the negative eigenvalues to zero). This is slow in practice because it requires eigenvalue decomposition, which scales in O(d 3 ). Another interesting challenge is to learn a low-rank matrix (which implies a low-dimensional projection space, as noted earlier) instead of a full-rank one, since optimizing M subject to a rank constraint or regularization is NP-hard and thus cannot be carried out efficiently.

In this section, we review the main supervised Mahalanobis distance learning methods of the literature. We first present two early approaches that deal with the PSD constraint in a rudimentary way (Section 3.2.1.1). We then discuss approaches that are specific to k-nearest neighbors (Section 3.2.1.2), inspired from information theory (Section 3.2.1.3), online learning methods (Section 3.2.1.4), approaches with generalization guarantees (Section 3.2.1.5) and a few more that do not fit any of the previous categories (Section 3.2.1.6).

Early Approaches

MMC (Xing et al.) The pioneering work of [START_REF] Xing | Distance Metric Learning with Application to Clustering with Side-Information[END_REF] is the first Mahalanobis distance learning method. It relies on a convex SDP formulation with no regularization, which aims at maximizing the sum of distances between dissimilar points while keeping the sum of distances between similar examples small: max

M∈S d + (z i ,z j )∈D d M (x i , x j ) s.t. (z i ,z j )∈S d 2 M (x i , x j ) ≤ 1. (3.1)
The algorithm for solving (3.1) is a basic SDP approach based on eigenvalue decomposition. This makes it intractable for medium and high-dimensional problems.

Schultz & Joachims

The method proposed by [START_REF] Schultz | Learning a Distance Metric from Relative Comparisons[END_REF] relies on the assumption that M = A T WA, where A is fixed and known and W is diagonal. We get:

d 2 M (x i , x j ) = (Ax i -Ax j ) T W(Ax i -Ax j ).
By definition, M is PSD and thus one can optimize over the diagonal matrix W and avoid the need for SDP. They propose a formulation based on triplet constraints:

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.2)
where • 2 F is the squared Frobenius norm. Slack variables are introduced to allow soft constraints. Problem (3.2) is convex and can be solved efficiently. The main drawback of this approach is that it is less general than full Mahalanobis distance learning: one only learns a weighting W of the features. Furthermore, A must be chosen manually.

Approaches driven by Nearest Neighbors

The objective functions of the methods presented in this section are related to a nearest neighbor prediction rule.

NCA (Goldberger et al.) The idea of Neighborhood Component Analysis (NCA), introduced by [START_REF] Goldberger | Neighbourhood Components Analysis[END_REF], is to optimize the expected leave-one-out error of a stochastic nearest neighbor classifier in the projection space induced by d M . They use the decomposition M = L T L and they define the probability that x i is the neighbor of x j by

p ij = exp(-Lx i -Lx j 2 ) l =i exp(-Lx i -Lx l 2 )
, p ii = 0.

Then, the probability that x i is correctly classified is:

p i = j:y j =y i p ij .
They learn the distance by solving: (2005; 2008; 2009), is one of the most popular Mahalanobis distance learning methods. The idea is to learn the distance such that the k nearest neighbors belong to the correct class while keeping away instances of other classes. The Euclidean distance is used to determine these "target neighbors". Formally, the constraints are defined in the following way:

max L i p i . ( 3
S = {(z i , z j ) ∈ T × T : i = j and x j belongs to the k-neighborhood of x i }, R = {(z i , z j , z k ) ∈ T × T × T : (z i , z j ) ∈ S, i = k }.
The distance is learned using the following convex program: min [START_REF] Davis | Information-theoretic metric learning[END_REF], is an important work because it introduces LogDet divergence regularization that will later be used in several other Mahalanobis distance learning methods (e.g., [START_REF] Jain | Online Metric Learning and Fast Similarity Search[END_REF][START_REF] Qi | An Efficient Sparse Metric Learning in High-Dimensional Space via l1-Penalized Log-Determinant Regularization[END_REF]. This Bregman divergence on PSD matrices is defined as:

M∈S d + (z i ,z j )∈S d 2 M (x i , x j ) 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
D ld (M, M 0 ) = trace(MM 0 -1 ) -log det(MM 0 -1 ) -d,
where d is the dimension of the input space and M 0 is some PSD matrix we want to remain close to. In practice, M 0 is often set to I (the identity matrix) and thus the regularization aims at keeping the learned distance close to the Euclidean distance.

The key feature of the LogDet divergence is that it is finite if and only if M is PSD.

Therefore, minimizing D ld (M, M 0 ) provides an automatic and cheap way of preserving the positive semi-definiteness of M. The LogDet divergence is also rank-preserving: if the initial matrix M 0 has rank r, the learned matrix will also have rank r.

ITML is formulated as follows:

min

M∈S d + D ld (M, M 0 ) s.t. d 2 M (x i , x j ) ≤ u ∀(z i , z j ) ∈ S d 2 M (x i , x j ) ≥ v ∀(z i , z j ) ∈ D, (3.5)
where u, v ∈ R are threshold parameters (as usual, slack variables are added to get soft constraints). ITML thus aims at satisfying the similarity and dissimilarity constraints while staying as close as possible to the Euclidean distance (if M 0 = I). More precisely, the information-theoretic interpretation behind minimizing D ld (M, M 0 ) is that it is equivalent to minimizing the KL divergence between two multivariate Gaussian distributions parameterized by M and M 0 . The algorithm proposed to solve (3.5) is efficient, converges to the global minimum and the resulting distance performs well in practice. A limitation of ITML is that M 0 , that must be picked by hand, can have an important influence on the quality of the learned distance.

SDML (Qi et al.) With Sparse Distance Metric Learning (SDML), [START_REF] Qi | An Efficient Sparse Metric Learning in High-Dimensional Space via l1-Penalized Log-Determinant Regularization[END_REF] specifically deal with the case of high-dimensional data together with few training samples, i.e., n d. To avoid overfitting, they use a double regularization: the LogDet divergence (using M 0 = I or M 0 = Σ -1 ) and L 1 -regularization on the off-diagonal elements of M. The justification for using this L 1 -regularization is two-fold: (i) a practical one is that in high-dimensional spaces, the off-diagonal elements of Σ -1 are often very small, and (ii) a theoretical one suggested by a consistency result from a previous work in covariance matrix estimation that applies to SDML. They use a fast algorithm based on block-coordinate descent (the optimization is done over each row of M -1 ) and obtain very good performance for the specific case n d.

Online Approaches

In online learning [START_REF] Littlestone | Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm[END_REF], the algorithm receives training instances one at a time and updates at each step the current hypothesis. Although the performance of online algorithms is typically inferior to batch algorithms, they are very useful to tackle large-scale problems that batch methods fail to address due to complexity and memory issues. Online learning methods often come with guarantees in the form of regret bounds, stating that the accumulated loss suffered along the way is not much worse than that of the best hypothesis chosen in hindsight. 1 However these results assume that the training pairs/triplets are generated i.i.d. (which is hardly the case in metric learning, as we will discuss later) and do not say anything about the generalization to unseen data.

POLA (Shalev-Shwartz et al.) POLA [START_REF] Shalev-Shwartz | Online and batch learning of pseudo-metrics[END_REF] is the first online Mahalanobis distance learning approach and learns the matrix M as well as a threshold b ≥ 1. At each step, when receiving the pair (z i , z j ), POLA performs two successive orthogonal projections:

1 A regret bound has the following general form:

T t=1 (h, zt) -T t=1 (h * , zt) ≤ O(T )
, where T is the number of steps and h * is the best batch hypothesis.

Projection of the current solution (M

i-1 , b i-1 ) onto C 1 = {(M, b) ∈ R d 2 +1 : M, b = [y i y j (d 2 M (x i , x j ) -b) + 1] + = 0}
, which is done efficiently (closed-form solution). The constraint basically requires that the distance between two instances of same (resp. different) labels be below (resp. above) the threshold b with a margin 1.

We get an intermediate solution (M i-1 2 , b i-1 2 ) that satisfies this constraint while staying as close as possible to the previous solution.

Projection of (M

i-1 2 , b i-1 2 ) onto C 2 = {(M, b) ∈ R d 2 +1 : M ∈ S d + , b ≥ 1}
, which is done rather efficiently (in the worst case, only needs to compute the minimal eigenvalue). This projects the matrix back onto the PSD cone. We thus get a new solution (M i , b i ) that yields a valid Mahalanobis distance.

A regret bound for the algorithm is provided. However, POLA relies on the unrealistic assumption that there exists (M * , b * ) such that [y i y j (d 2 M * (x i , x j )b * ) + 1] + = 0 for all training pairs (i.e., there exists a matrix and a threshold value that perfectly separate them with margin 1), and is not competitive in practice. 2012) is an attempt of proposing a general framework for online Mahalanobis distance learning. It is based on composite mirror descent [START_REF] Duchi | Composite Objective Mirror Descent[END_REF], which allows online optimization of many regularized problems. It can accommodate a large class of loss functions and regularizers for which efficient updates are derived, and the algorithm comes with a regret bound. In the experiments, they focus on trace norm regularization, which is the best convex relaxation of the rank and thus induces low-rank matrices. In practice, the approach has performance comparable to LMNN and ITML, is fast and sometimes induces low-rank solutions, but surprisingly the algorithm was not evaluated on large-scale datasets.

LEGO (

Metric Learning with Generalization Guarantees

As in the classic supervised learning setting (where training data consist of individual labeled instances), generalization guarantees may be derived for supervised metric learning (where training data consist of pairs or triplets). Indeed, most of supervised metric learning methods can be seen as minimizing a (regularized) loss function based on the training pairs/triplets. In this context, the pair-based true risk can be defined as

R (d 2 M ) = E z,z ∼P (d 2 M , z, z ) ,
the pair-based empirical risk as

R S,D (d 2 M ) = 1 |S| + |D| (z i ,z j )∈S∪D (d 2 M , z i , z j ),
and likewise for the triplet-based setting.

However, although individual training instances are assumed to be drawn i.i.d. from P , one cannot make the same assumption regarding the pairs or triplets themselves since they are built from the training sample. For this reason, establishing generalization guarantees for the learned metric is challenging and has so far received very little attention. To the best of our knowledge, only two approaches have tried to address this question explicitly.

Jin et al.

In their paper, [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF] study the following general Mahalanobis distance learning formulation:

min M 0 1 n 2 (z i ,z j )∈T ×T (d 2 M , z i , z j ) + C M F , (3.6)
where C > 0 is the regularization parameter. The loss function is assumed to be of the form

(d 2 M , z i , z j ) = g(y i y j [1 -d 2 M (x i , x j )]),
where g is convex and Lipschitz continuous.

Relying on a definition of uniform stability adapted to the case of distance learning (where training data is made of pairs), they show that one can derive generalization bounds for the learned distance. Unfortunately, their framework is limited to Frobenius norm regularization: in particular, since it is based on uniform stability, it cannot accommodate sparsity-inducing regularizers. Note that they also propose an online algorithm that is efficient and competitive in practice.

The work of Jin et al. is related to the contributions of this thesis in two ways. First, in Chapter 5, we make use of the same uniform stability arguments to derive learning guarantees for a learned edit similarity function, but we go a step further by deriving guarantees in terms of the error of the classifier built from this similarity. Second, in

Chapter 7, we propose an alternative framework for deriving learning guarantees for metric learning based on algorithmic robustness, and we show that this framework can tackle a wider variety of problems.

Bian & Tao The work of [START_REF] Bian | Learning a Distance Metric by Empirical Loss Minimization[END_REF]2012) is another attempt of developing metric learning algorithms with generalization guarantees. They consider a class of loss functions similar to that of [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF]:

(d 2 M , z i , z j ) = g(y ij [c -d 2 M (x i , x j )]),
where c > 0 is a decision threshold variable and g is convex and Lipschitz continuous.

The formulation they study is the following:

min (M,c)∈Q 1 n 2 (z i ,z j )∈T ×T (d 2 M , z i , z j ), (3.7)
where Q = {(M, c) : 0 M αI, 0 ≤ c ≤ α}, with α a positive constant. This ensures that the learned metric and decision threshold are bounded.

They use a statistical analysis to derive risk bounds as well as consistency bounds (the learned distance asymptotically converges to the optimal distance). However, they rely on strong assumptions on the distribution of the examples and cannot accommodate any regularization.

Other approaches

In this section, we describe a few approaches that are outside the scope of the previous categories.

Rosales & Fung

The method of [START_REF] Rosales | Learning Sparse Metrics via Linear Programming[END_REF] aims at learning matrices with entire columns/rows set to zero, thus making M low-rank. For this purpose, they use L 1 norm regularization and, restricting their framework to diagonal dominant matrices, they are able to formulate the problem as a linear program that can be solved efficiently.

However, L 1 norm regularization favors sparsity at the entry level only, not specifically at the row/column level, even though in practice the learned matrix is sometimes lowrank. Furthermore, the approach is less general than Mahalanobis distances due to the restriction to diagonal dominant matrices.

SML (Ying et al.) SML [START_REF] Ying | Sparse Metric Learning via Smooth Optimization[END_REF] is a Mahalanobis distance learning approach that regularizes M with the L 2,1 norm, which tends to zero out entire rows of M (as opposed to the L 1 norm used in the previous method). They essentially want to solve the following problem: min

M∈S d + M 2,1 s.t. d 2 M (x i , x k ) -d 2 M (x i , x j ) ≥ 1 ∀(z i , z j , z k ) ∈ R,
where slack variables are added to get soft constraints. However, L 2,1 norm regularization is typically difficult to optimize. Using smoothing techniques the authors manage to derive an algorithm that scales in O(d 3 ) per iteration. The method performs well in practice while inducing a lower-dimensional projection space than full-rank methods and the method of [START_REF] Rosales | Learning Sparse Metrics via Linear Programming[END_REF]. However, it cannot be applied to high-dimensional problems due to the complexity of the algorithm.

BoostMetric (Shen et al.) BoostMetric [START_REF] Shen | Positive Semidefinite Metric Learning with Boosting[END_REF][START_REF] Shen | Positive Semidefinite Metric Learning Using Boosting-like Algorithms[END_REF] adapts to Mahalanobis distance learning the ideas of boosting, where a good hypothesis is obtained through a weighted combination of so-called "weak learners" [START_REF] Schapire | Boosting: Foundations and Algorithms[END_REF], see the recent book on this matter by). The method is based on the property that any PSD matrix can be decomposed into a positive linear combination of trace-one rank-one matrices. This kind of matrices is thus used as weak learner and the authors adapt the popular boosting algorithm Adaboost [START_REF] Freund | A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting[END_REF] to this setting. The resulting algorithm is quite efficient since it does not require full eigenvalue decomposition but only the computation of the largest eigenvalue. In practice, BoostMetric achieves competitive performance but hardly scales to large-scale or high-dimensional datasets.

DML (Ying et al.) The work of [START_REF] Cao | Distance Metric Learning Revisited[END_REF] revisit MMC, the original approach of [START_REF] Xing | Distance Metric Learning with Application to Clustering with Side-Information[END_REF], by investigating the following formulation, called DML-eig: max

M∈S d + min (z i ,z j )∈D d 2 M (x i , x j ) s.t. (z i ,z j )∈S d 2 M (x i , x j ) ≤ 1. (3.8)
The slight difference is that DML-eig (3.8) maximizes the minimum (square) distance between negative pairs while MMC (3.1) maximizes the sum of distances. Ying & Li avoid the costly full eigen-decomposition used by Xing et al. by showing that (3.8) can be cast as a well-known eigenvalue optimization problem called "minimizing the maximal eigenvalue of a symmetric matrix". They further show that it can be solved efficiently using a first-order algorithm that only requires the computation of the largest eigenvalue at each iteration, and that LMNN can also be cast as a similar problem.

Experiments show competitive results and low computational complexity, although it might be subject to overfitting due to the absence of regularization.

Cao et al. ( 2012) generalize (3.8) by studying the following formulation, called DML-p: max

M∈S d +   1 |D| (z i ,z j )∈D [d M (x i , x j )] 2p   1/p s.t. (z i ,z j )∈S d 2 M (x i , x j ) ≤ 1.
(3.9)

They show that for p ∈ (-∞, 1), (3.9) is convex and can be solved efficiently in an analogous manner as DML-eig. For p = 0.5 we recover MMC (3.1) and for p → -∞ we recover DML-eig (3.8). Experiments show that tuning p can lead to better performance than MMC or DML-eig.

LNML (Wang et al.) The idea of LNML [START_REF] Wang | Learning Neighborhoods for Metric Learning[END_REF] is to enhance metric learning methods by also learning the neighborhood (i.e., the pairs or triplets) according to which the metric is optimized. They propose an iterative approach that alternates between a neighbor assignment step (where the current metric is used to determine the neighbors according to some quality measure) and a metric learning step (where the metric is optimized with respect to the current neighborhood). Experiments are conducted on MCML and LMNN and show that more accurate metrics can be learned using their framework. Of course, this is achieved at the expense of higher computational complexity, since the metric learning algorithms must be run several times (5-10 times in their experiments).

Similarity Learning

Although most of the work in metric learning has focused on the Mahalanobis distance, learning similarity functions has also attracted some interest, motivated by the perspective of more scalable algorithms due to the absence of PSD constraint.

SiLA (Qamar et al.) SiLA [START_REF] Qamar | Similarity Learning for Nearest Neighbor Classification[END_REF] is an approach for learning similarity functions of the following form:

x T Mx N (x, x ) ,
where M ∈ R d×d and N (x, x ) is a normalization term which depends on x and x . This similarity function can be seen as a generalization of the cosine and the bilinear similarities. The authors build on the same idea of "target neighbors" that was introduced in LMNN, but optimize the similarity in an online manner with an algorithm based on voted perceptron. At each step, the algorithm goes through the training set, updating the matrix when an example does not satisfy a criterion of separation. The authors present theoretical results that follow from the voted perceptron theory in the form of regret bounds for the separable and nonseparable cases. SiLA is compared to Mahalanobis metric learning approaches on three datasets. It seems to perform fine but has a rather slow convergence rate and may suffer of its lack of regularization. In subsequent work, [START_REF] Qamar | RELIEF Algorithm and Similarity Learning for k-NN[END_REF] study the relationship between SiLA and RELIEF, an online feature reweighting algorithm.

gCosLA (Qamar & Gaussier) gCosLA [START_REF] Qamar | Online and Batch Learning of Generalized Cosine Similarities[END_REF] learns generalized cosine similarities of the form

x T Mx √ x T Mx √ x T Mx , where M ∈ S d + .
It corresponds to a cosine similarity in the projection space implied by M. The algorithm itself, an online procedure, is very similar to that of POLA (presented in Section 3.2.1.4). Indeed, they essentially use the same loss function and also have a two-step approach: a projection onto the set of arbitrary matrices that achieve zero loss on the current example pair, followed by a projection back onto the PSD cone. The first projection is different from POLA (since the generalized cosine has a normalization factor that depends on M) but the authors manage to derive a closed-form solution.

The second projection is based on a full eigenvalue decomposition of M, making the approach costly as dimensionality grows. A regret bound for the algorithm is provided and it is shown experimentally that gCosLA converges in fewer iterations than SiLA and is generally more accurate. Its performance seems competitive with LMNN and ITML.

OASIS (Chechik et al.) The similarity learning method OASIS [START_REF] Chechik | An Online Algorithm for Large Scale Image Similarity Learning[END_REF][START_REF] Chechik | Large Scale Online Learning of Image Similarity Through Ranking[END_REF]) learns a bilinear similarity K M (see Section 2.3.2) for large-scale problems.

Since M ∈ R d×d is not required to be PSD, they can optimize the similarity in an online manner using a simple and efficient algorithm, which belongs to the family of Passive-Aggressive algorithms [START_REF] Crammer | Online Passive-Aggressive Algorithms[END_REF]. The initialization is M = I, then at each step t, the algorithm draws a triplet (z i , z j , z k ) ∈ R and solves the following convex problem:

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.10)
where C is the trade-off parameter between minimizing the loss and staying close from the matrix obtained at the previous step, and ξ is a slack variable. Clearly, if 1 -

d 2 M (x i , x j ) + d 2 M (x i , x k ≤ 0, then M t = M t-1
is the solution of (3.10). Otherwise, the solution is obtained from a simple closed-form update. In practice, OASIS achieves competitive results on medium-scale problems and unlike most other methods, is scalable to problems with millions of training instances. However, it cannot incorporate complex regularizers and does not have generalization guarantees.

Note that the same authors derived two more algorithms for learning bilinear similarities as applications of more general frameworks. The first one is based on online learning in the manifold of low-rank matrices [START_REF] Shalit | Online Learning in The Manifold of Low-Rank Matrices[END_REF][START_REF] Shalit | Online Learning in the Embedded Manifold of Low-rank Matrices[END_REF]) and the second one on adaptive regularization of weight matrices [START_REF] Crammer | Adaptive Regularization for Weight Matrices[END_REF].

Nonlinear Metric Learning

We have seen that the work in supervised metric learning from feature vectors has focused on linear metrics because they are more convenient to optimize (in particular, it is easier to derive convex formulations with the guarantee of finding the global optimum) and less prone to overfitting. However, a drawback of linear metric learning is that it will fail to capture nonlinear patterns in the data.

An example of nonlinear metric learning is kernel learning, but existing approaches are very expensive and/or subject to local minima (see for instance [START_REF] Cheng | Hyperkernels[END_REF][START_REF] Cheng | Learning the Kernel with Hyperkernels[END_REF]Xu et al., 2012b), cannot be applied to unseen data [START_REF] Gert | Learning the Kernel Matrix with Semi-Definite Programming[END_REF][START_REF] Gert | Learning the Kernel Matrix with Semidefinite Programming[END_REF][START_REF] Tsuda | Matrix Exponentiated Gradient Updates for On-line Learning and Bregman Projection[END_REF][START_REF] Kulis | Learning low-rank kernel matrices[END_REF][START_REF] Kulis | Low-Rank Kernel Learning with Bregman Matrix Divergences[END_REF] or limited to learning a combination of existing kernels such as in Multiple Kernel Learning (see [START_REF] Gönen | Multiple Kernel Learning Algorithms[END_REF], for a recent survey).

So far, the most satisfactory solution to the problem of nonlinear metric learning is probably the kernelization of linear metric learning methods, in the spirit of what is done in SVM, i.e., learn a linear metric in the nonlinear feature space induced by a kernel function and thereby combine the best of both worlds. Some metric learning approaches have been shown to be kernelizable (for instance [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][START_REF] Davis | Information-theoretic metric learning[END_REF] using specific arguments, but in general kernelizing a particular metric algorithm is not trivial: a new formulation of the problem has to be derived, where interface to the data is limited to inner products, and sometimes a different implementation is necessary. Moreover, when kernelization is possible, one must learn a n T × n T matrix. As n T gets large, the problem becomes intractable unless dimensionality reduction is applied. Recently though, several authors [START_REF] Chatpatanasiri | A new kernelization framework for Mahalanobis distance learning algorithms[END_REF]Zhang et al., 2010) have proposed general kernelization methods based on Kernel Principal Component Analysis [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF]. They can be used to kernelize nearly any metric learning algorithm and perform dimensionality reduction simultaneously in a very simple manner, referred to as the "KPCA trick". Since our bilinear similarity learning approach introduced in Chapter 6 is kernelized using this trick, we postpone the details to Section 6.2.2.

Note that kernelizing a metric learning algorithm may drastically improve the quality of the learned metric on highly nonlinear problems, but may also favor overfitting (because local pair or triplet-based constraints become much easier to satisfy in a nonlinear, highdimensional kernel space), leading to poor generalization ability.

Approaches for Other Settings

In this review, we discussed metric learning approaches for the general supervised learning setting. Note that there also exist methods for the semi-supervised setting [START_REF] Qi | An Efficient Sparse Metric Learning in High-Dimensional Space via l1-Penalized Log-Determinant Regularization[END_REF][START_REF] Mahdieh | Semi-Supervised Metric Learning Using Pairwise Constraints[END_REF][START_REF] Liu | Semi-Supervised Sparse Metric Learning using Alternating Linearization Optimization[END_REF][START_REF] Dai | Information-theoretic Semi-supervised Metric Learning via Entropy Regularization[END_REF], domain adaptation [START_REF] Cao | Distance Metric Learning under Covariate Shift[END_REF][START_REF] Geng | DAML: Domain Adaptation Metric Learning[END_REF][START_REF] Kulis | What you saw is not what you get: Domain adaptation using asymmetric kernel transforms[END_REF] and multi-task/view learning [START_REF] Parameswaran | Large Margin Multi-Task Metric Learning[END_REF][START_REF] Wang | Metric Learning with Multiple Kernels[END_REF][START_REF] Yang | Geometry Preserving Multi-task Metric Learning[END_REF].

There also exists specific literature on metric learning for computer vision tasks such as object recognition [START_REF] Frome | Learning Globally-Consistent Local Distance Functions for Shape-Based Image Retrieval and Classification[END_REF][START_REF] Verma | Learning Hierarchical Similarity Metrics[END_REF], face recognition [START_REF] Guillaumin | Is that you? Metric learning approaches for face identification[END_REF] or tracking [START_REF] Li | Nonsparse Linear Representations for Visual Tracking with Online Reservoir Metric Learning[END_REF].

Metric Learning from Structured data

As pointed out earlier, metrics have a special importance in the context of structured data: they can be used as a proxy to access data without having to manipulate these complex objects. As a consequence, given an appropriate structured metric, one can use k-NN, SVM, K-Means or any other metric-based algorithm as if the data consisted of feature vectors.

Unfortunately, for the same reasons, metric learning from structured data is challenging because most of structured metrics are combinatorial by nature, which explains why it has received less attention than metric learning from feature vectors. Most of the available literature on the matter focuses on learning metrics based on the edit distance.

Clearly, for the edit distance to be meaningful, one needs costs that reflect the reality of the considered task. To take a simple example, in typographical error correction, the probability that a user hits the Q key instead of W on a QWERTY keyboard is much higher than the probability that he hits Q instead of Y. For some applications, such as protein alignment or handwritten digit recognition, well-tailored cost matrices may be available [START_REF] Dayhoff | A model of evolutionary change in proteins[END_REF][START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF][START_REF] Micó | Comparison of fast nearest neighbour classifiers for handwritten character recognition[END_REF].

Otherwise, there is a need for automatically learning a nonnegative (|Σ| + 1) × (|Σ| + 1) cost matrix C for the task at hand. What makes the cost matrix difficult to optimize is the fact that the edit distance is based on an optimal script which depends on the edit costs themselves. Most generalpurpose approaches get round this problem by considering a stochastic variant of the edit distance, where the cost matrix defines a probability distribution over the edit operations. One can then define an edit similarity equal to the posterior probability p e (x |x) that an input string x is turned into an output string x . This corresponds to summing over all possible edit scripts that turn x into x instead of only considering the optimal script. Such a stochastic edit process can be represented as a probabilistic model and one can estimate the parameters (i.e., the cost matrix) of the model that maximize the expected log-likelihood of positive pairs. This is done via an iterative Expectation-Maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], a procedure that alternates between two steps: an Expectation step (which essentially computes the function of the expected log-likelihood of the pairs with respect to the current parameters of the model) and a Maximization step (computing the updated edit costs that maximize this expected log-likelihood). Note that unlike the classic edit distance, the obtained edit similarity does not usually satisfy the properties of a distance (in fact, it is often not symmetric).

In the following, we review methods for learning string edit metrics (Section 3.3.1) and tree edit metrics (Section 3.3.2).

String Edit Metric Learning

Generative models The first method for learning a string edit metric was proposed by [START_REF] Ristad | Learning String-Edit Distance[END_REF]. They use a memoryless stochastic transducer which models the joint probability of a pair p e (x, x ) from which p e (x |x) can be estimated. Parameter estimation is performed with EM and the learned edit probability is applied to the problem of learning word pronunciation in conversational speech. [START_REF] Bilenko | Adaptive Duplicate Detection Using Learnable String Similarity Measures[END_REF] extended this approach to the Needleman-Wunsch Score with affine gap penalty and applied it to duplicate detection. To deal with the tendency of Maximum Likelihood estimators to overfit when the number of parameters is large (in this case, when the alphabet size is large), [START_REF] Takasu | Bayesian Similarity Model Estimation for Approximate Recognized Text Search[END_REF] proposes a Bayesian parameter estimation of pair-HMM providing a way to smooth the estimation. Experiments are conducted on approximate text searching in a digital library of Japanese and English documents.

Discriminative models The work of [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF] describes three levels of bias induced by the use of generative models: (i) dependence between edit operations, (ii) dependence between the costs and the prior distribution of strings p e (x), and (iii) the fact that to obtain the posterior probability one must divide by the empirical estimate of p e (x). These biases are highlighted by empirical experiments conducted with the method of [START_REF] Ristad | Learning String-Edit Distance[END_REF]. To address these limitations, they propose the use of a conditional transducer that directly models the posterior probability p e (x |x) that an input string x is turned into an output string x using edit operations. Parameter estimation is also done with EM and the paper features an application to handwritten digit recognition, where digits are represented as sequences of Freeman codes [START_REF] Freeman | Computer Processing of Line-Drawing Images[END_REF]. In order to allow the use of negative pairs, [START_REF] Mccallum | A Conditional Random Field for Discriminatively-trained Finite-state String Edit Distance[END_REF] consider another discriminative model, conditional random fields, that can deal with positive and negative pairs in specific states, still using EM for parameter estimation.

Methods based on gradient descent The use of EM has two main drawbacks:

(i) it may converge to a local optimum, and (ii) parameter estimation and distance calculations must be done at each iteration, which can be very costly if the size of the alphabet and/or the length of the strings are large. [START_REF] Saigo | Optimizing amino acid substitution matrices with a local alignment kernel[END_REF] manage to avoid the need for an iterative procedure like EM in the context of detecting remote homology in protein sequences. They learn the parameters of the Smith-Waterman score which is plugged in their local alignment kernel [START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF]. Unlike the Smith-Waterman score, the local alignment kernel, which is based on the sum over all possible alignments, is differentiable and can be optimized by a gradient descent procedure. The objective function that they optimize is meant to favor the discrimination between positive and negative examples, but this is done by only using positive pairs of distant homologs. The approach has two additional drawbacks:

(i) the objective function is nonconvex and it thus subject to local minima, and (ii) the kernel's validity is not guaranteed in general and is subject to the value of a parameter that must be tuned. Therefore, the authors use this learned function as a similarity measure and not as a kernel. Neuhaus & Bunke In their paper, [START_REF] Neuhaus | Automatic learning of cost functions for graph edit distance[END_REF] learn a (more general) graph edit similarity, where each edit operation is modeled by a Gaussian mixture density. Parameter estimation is done using an EM-like algorithm. Unfortunately, the approach is intractable: the complexity of the EM procedure is exponential in the number of nodes (and so is the computation of the distance). [START_REF] Nilesh | Robust web extraction: an approach based on a probabilistic tree-edit model[END_REF] points out a limitation of the approach of [START_REF] Bernard | Learning Stochastic Tree Edit Distance[END_REF][START_REF] Bernard | Learning probabilistic models of tree edit distance[END_REF]: they model a distribution over tree edit scripts rather than over the trees themselves, and unlike the case of strings, there is no bijection between the edit scripts and the trees. Recovering the correct conditional probability with respect to trees requires a careful and costly procedure. They propose a more complex conditional transducer that models the conditional probability over trees and use EM for parameter estimation. They apply their method to the problem of creating robust wrappers for webpages.

Tree Edit Metric Learning

Dalvi et al. The work of

Emms The work of [START_REF] Emms | On Stochastic Tree Distances and Their Training via Expectation-Maximisation[END_REF] points out a theoretical limitation of the approach of [START_REF] Boyer | Learning Metrics between Tree Structured Data: Application to Image Recognition[END_REF]: the authors use a factorization that turns out to be incorrect in some cases. Emms shows that a correct factorization exists when only considering the edit script of highest probability instead of all possible scripts, and derives the corresponding EM updates. An obvious drawback is that the output of the model is not the probability p e (x |x). Moreover, experiments on a question answering task highlight that the approach is prone to overfitting, and requires smoothing and other heuristics (such as a final step of zeroing-out the diagonal of the cost matrix).

Conclusion

In this chapter, we reviewed a large body of work in supervised metric learning. Table 3.1 and Table 3.2 summarize the main features of the studied approaches for feature vectors and structured data respectively. This review raises three observations:

1. Research efforts on metric learning from feature vectors have been mainly oriented towards deriving tractable formulations and algorithms. Boosted by some advances in batch and online numerical optimization, these efforts have been successful: recent methods are scalable and can even accommodate complex regularizers in an efficient way. However, there is an obvious lack of theoretical understanding of metric learning. First, few frameworks capable of establishing the consistency of the learned metric on unseen data have been proposed, and existing ones lack generality. Second, using a learned metric often improves the empirical performance of metric-based algorithms, but this has never been studied from a theoretical Table 3.2: Summary of the main features of the reviewed approaches ("Opt.", "Global sol.", "Neg. pairs" and "Gen." respectively stand for "Optimization", "Global solution", "Negative pairs" and "Generalization guarantees").

Method Convex Scalable Competitive Reg. Low-rank Online Gen. MMC ✗ ✗ ✗ ✗ ✗ ✗ Schultz & Joachims ✗ ✗ ✗ ✗ NCA ✗ ✗ ✗ ✗ ✗ MCML ✗ ✗ ✗ ✗ ✗ ✗ LMNN ✗ ✗ ✗ ✗ ITML ✗ SDML ✗ ✗ ✗ POLA ✗ ✗ ✗ ✗ LEGO ✗ MDML ✗ Jin et al. ✗ Bian & Tao ✗ ✗ ✗ Rosales & Fung ✗ ✗ ✗ SML ✗ ✗ ✗ BoostMetric ✗ ✗ ✗ DML ✗ ✗ ✗ ✗ SiLA - ? ✗ ✗ ✗ gCosLA ✗ ✗ ✗ OASIS ✗ ✗
standpoint. In particular, can we relate the empirical risk of the learned metric to the true risk of the classifier that uses it?

2. There is a relatively small body of work on metric learning from structured data, presumably due to the higher complexity of the learning procedures. Almost all existing methods are based on probabilistic models: they are trained using an expensive iterative algorithm and cannot accommodate negative pairs. Furthermore, no approach is guaranteed to converge to the global optimum of the optimized quantity and again, there is a lack of theoretical study.

3. Chapter abstract With the success of kernel methods, there is a growing interest in designing powerful kernels between sequences. In this chapter, we propose a new string kernel based on edit probabilities learned with a conditional transducer. Unlike other string edit kernels, it is parameter-free and guaranteed to be valid since it corresponds to a dot product in an infinite-dimensional space. While the naive computation of the kernel involves an intractable sum over an infinite number of strings, we show that it can actually be computed exactly using the intersection of probabilistic automata and a matrix inversion. Experimental results on a handwritten character recognition task show that our new kernel outperforms state-of-the-art string kernels as well as standard and learned edit distance used in a k-NN classifier.

The material of this chapter is based on the following international publication: Aurélien Bellet, Marc Bernard, Thierry Murgue, and Marc Sebban. Learning state machine-based string edit kernels. Pattern Recognition (PR), 43(6):2330-2339, 2010.

Introduction

In recent years, with the emergence of kernel-based learning, a lot of research has gone into designing powerful kernels for structured data such as strings. A natural way of building string kernels consists in representing each sequence by a fixed-length feature vector. Many of the early string kernels, such as the spectrum, the subsequence or the mismatch kernels (presented in Section 2.3.3), belong to this family. They sometimes perform well, but they are not very flexible and imply a significant loss of structural information.

On the other hand, measures based on (or related to) the string edit distance can capture more structural distortions and are adaptable by nature, since they are based on a cost matrix that can be used to incorporate background knowledge on the problem of interest.

When a domain expertise is not available, one may learn these costs automatically from data (we have reviewed these methods in Section 3.3). Unfortunately, their use is mostly restricted to k-NN classifiers since efforts to design string kernels from the edit distance (the so-called edit kernels) have not been satisfactory: their validity (i.e., positive semidefiniteness) is subject to the value of a parameter (that must be tuned) and/or they suffer from the "diagonal dominance" problem [START_REF] Li | A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs[END_REF][START_REF] Cortes | Rational Kernels: Theory and Algorithms[END_REF][START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF][START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF]. Another drawback of these approaches is that they use the standard version of the edit distance. Adapting them to make use of learned edit similarities (that are not proper distances and sometimes not even symmetric) is often not straightforward.

In this work, we propose a new string edit kernel that makes use of conditional edit probabilities learned in the form of probabilistic models. Our kernel belongs to the family of marginalized kernels [START_REF] Tsuda | Marginalized kernels for biological sequences[END_REF][START_REF] Kashima | Marginalized Kernels Between Labeled Graphs[END_REF], is parameterfree and guaranteed to be PSD. It also has the unusual feature of being based on a sum over an infinite number of strings. This sum may seem intractable at first glance, but drawing our inspiration from rational kernels [START_REF] Cortes | Rational Kernels: Theory and Algorithms[END_REF], we show that it can be computed exactly by means of the intersection of two probabilistic automata and a matrix inversion. We conduct experiments on a handwritten digit recognition task that show that our kernel outperforms state-of-the-art string kernels, as well as k-NN classifiers based on standard and learned edit distance measures.

The rest of this chapter is organized as follows. Section 4.2 introduces our new string edit kernel. Section 4.3 is devoted to the computation of the kernel based on intersection of probabilistic automata and matrix inversion. Experimental results are presented in Section 4.4 and we conclude in Section 4.5.

A New Marginalized String Edit Kernel

Our new string edit kernel belongs to the family of marginalized kernels [START_REF] Tsuda | Marginalized kernels for biological sequences[END_REF][START_REF] Kashima | Marginalized Kernels Between Labeled Graphs[END_REF]. Let p(x, x , v) be the probability of observing jointly a hidden variable v ∈ V and two observable strings x, x ∈ Σ * . The probability p(x, x ) can be obtained by marginalizing, i.e. summing over all variables v ∈ V, the probability p(x, x , v), such that:

p(x, x ) = v∈V p(x, x , v) = v∈V p(x, x |v) • p(v).
A marginalized kernel computes this probability making the assumption that x and x are conditionally independent given v, i.e.,

K(x, x ) = v∈V p(x|v) • p(x |v) • p(v). (4.1)
Note that the computation of this kernel is possible since it is assumed that V is a finite set. Let us now suppose that p(v|x) is known instead of p(x|v). Then, as described in [START_REF] Tsuda | Marginalized kernels for biological sequences[END_REF], we can use the following marginalized kernel:

K(x, x ) = v∈V p(v|x) • p(v|x ) • K c (c, c ), (4.2)
where K c (c, c ) is the joint kernel depending on combined variables c = (x, v) and c = (x , v). An interesting way to exploit the kernel in Equation 4.2 as a string edit kernel is to do the following:

• replace the finite set V of variables v by the infinite set of strings s ∈ Σ * ,

• use p(s|x) = p e (s|x), which is the conditional probability that a string x is turned into a string s through edit operations,

• and take K c (c, c ) to be the constant kernel that returns 1 for all c, c .

We then obtain the following new string edit kernel:

K e (x, x ) = s∈Σ * p e (s|x) • p e (s|x ), (4.3)
which is PSD as it corresponds to the inner product in the Hilbert space defined by the mapping φ(x) = [p e (s|x)] s∈Σ * . Like the popular Gaussian kernel for feature vectors, K e projects the data into an infinite-dimensional space. Intuitively, K e (x, x ) is large when

x and x have a high probability to be turned into the same strings s ∈ Σ * using edit operations.

We have already seen in Section 3.3.1 that there exist methods in the literature for learning p e (x |x) for all x, x . However, our new kernel is intractable in its current form since it involves the computation of an infinite sum over Σ * . In the next section, we present a way of computing this infinite sum exactly and in an efficient way.

Computing the Edit Kernel

While the original marginalized kernel (4.1) assumes that V is a finite set of variables [START_REF] Tsuda | Marginalized kernels for biological sequences[END_REF], our string edit kernel includes an infinite sum over Σ * . In this section, we show that (i) given two strings x and x , p e (s|x) and p e (s|x ) can be represented in the form of two probabilistic automata, (ii) the product p e (s|x) • p e (s|x ) can be performed by intersecting the languages represented by those automata and (iii) the infinite sum over Σ * can then be computed by algebraic methods.

Definitions and Notations

We first introduce some definitions and notations regarding probabilistic transducers.

Definition 4.1. A weighted finite-state transducer (WFT) is an 8-tuple T = (Σ, ∆, Q, I, F, w, τ, ρ) where Σ is the input alphabet, ∆ the output alphabet, Q a finite set of states, I ⊆ Q the set of initial states, F ⊆ Q the set of final states, w : For notational convenience, we denote w(q 1 , q 2 , a, b) by w q 1 →q 2 (a, b) for any q 1 , q 2 ∈ Q, a ∈ Σ and b ∈ ∆.

Q × Q × (Σ ∪ {$}) × (∆ ∪ {$}) → R
Definition 4.2. A joint probabilistic finite-state transducer (jPFT) is a WFT J = (Σ, ∆, Q, S, F, w, τ, ρ) which defines a joint probability distribution over pairs of strings {(x, x ) ∈ Σ * × ∆ * }. A jPFT must satisfy the following four constraints:

1. The initial, final and transition weights have nonnegative values.

2. i∈S τ (i) = 1, 3. f ∈F ρ(f ) = 1, 4. ∀q 1 ∈ Q : q 2 ∈Q,a∈Σ∪{$},b∈∆∪{$} w q 1 →q 2 (a, b) = 1. Definition 4.3. A conditional probabilistic finite-state transducer (cPFT) is a WFT C = (Σ, ∆, Q, S, F, w, τ, ρ
) which defines a conditional probability distribution over the output strings x ∈ ∆ * given an input string x ∈ Σ * . For q 1 , q 2 ∈ Q, a ∈ Σ and b ∈ ∆, we denote the transition w q 1 →q 2 (a, b) in the conditional form w q 1 →q 2 (b|a). A cPFT must satisfy the same first two constraints as those of a jPFT and the following third constraint (see [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF], for a proof):

∀q 1 ∈ Q, ∀a ∈ Σ : q 2 ∈Q,b∈∆∪{$}
w q 1 →q 2 (b|a) + w q 1 →q 2 (b|$) = 1.

An example of memoryless cPFT (i.e., with only one state) is shown in Figure 4.1, where Σ = ∆ = {a, b} and Q is composed of only one state labeled by 0. Initial states are designated by an inward arrow that has no source state, while final states are denoted by a double circle. In Figure 4.1, state 0 is both initial and final.

In the following, since our string edit kernel is based on conditional edit probabilities, we will assume that a cPFT has already been learned by one of the previously mentioned methods, for instance that of [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF] that we describe in more details in Appendix A for the sake of completeness. Note that the cPFT is learned only once and is then used to compute our edit kernel for any pair of strings. If a generative model is used to learn the edit parameters (e.g., that of [START_REF] Ristad | Learning String-Edit Distance[END_REF], the resulting jPFT can be renormalized into a cPFT a posteriori. Definition 4.4. Let T = (Σ, ∆, Q, S, F, w, τ, ρ) be a cPFT that models p e (x |x), ∀x ∈ ∆ * , ∀x ∈ Σ * . We define T |x as a cPFT that models p e (s|x), ∀s ∈ ∆ * and a specific observable x ∈ Σ * . T |x = (Σ, ∆, Q , S , F , w , τ , ρ ) with:

• Q = {[x] i } × Q where [x] i is the prefix of length i of x (note that [x] 0 = $).
In other words, Q is a finite set of states labeled by the current prefix of x and its corresponding state during its parsing in T .1

• S = {($, q)} where q ∈ S;

• ∀q ∈ S, τ (($, q)) = τ (q);

• F = {(x, q)} where q ∈ F;

• ∀q ∈ F, ρ ((x, q)) = ρ(q);

• the following two rules are used to define the transition weight function:

-∀b ∈ ∆ ∪ {$}, ∀q 1 , q 2 ∈ Q, w ([x] i ,q 1 )→([x] i+1 ,q 2 ) (b|x i+1 ) = w q 1 →q 2 (b|x i+1 ), -∀b ∈ ∆, ∀q 1 , q 2 ∈ Q, w ([x] i ,q 1 )→([x] i ,q 2 ) (b|$) = w q 1 →q 2 (b|$).
As an example, given two strings x = a and x = ab, For the sake of readability, state 0 stands for ($, 0), and state 1 for (a, 0). On the right: a cPFT T |ab that models the output distribution given x = ab. Again, 0 stands for ($, 0), 1 for (a, 0), and 2 for (ab, 0). The next step for computing our kernel K e (x, x ) is to compute the product p e (s|x) • p e (s|x ). This can be performed by modeling the language that describes the intersection of the automata corresponding to p e (s|x) and p e (s|x ). This intersection can be obtained by performing a composition of transducers [START_REF] Cortes | Rational Kernels: Theory and Algorithms[END_REF]. As mentioned by the authors, composition is a fundamental operation on weighted transducers that can be used to create complex weighted transducers from simpler ones. In this context, note that the intersection of two probabilistic automata (such as those of Figure 4.3) is a special case of composition where the input and output transition labels are identical.

This intersection takes the form of a probabilistic automaton as defined below.

Definition 4.5. Let T be a cPFT modeling conditional edit probabilities. Let x and x be two strings of Σ * . Let A|x = (∆, Q, S, F, w, τ, ρ) and A|x = (∆, Q , S , F , w , τ , ρ ) be the automata deduced from T given the observable strings x and x . We define the intersection of A|x and A|x as the automaton A|x, x = (∆, Q A , S A , F A , w A , τ A , ρ A ) such that:

• Q A = Q × Q ,
• S A = {(q, q )} with q ∈ S and q ∈ S ,

• F A = {(q, q )} with q ∈ F and q ∈ F ,

• w A (q 1 ,q 1 )→(q 2 ,q 2 ) (b) = w q 1 →q 2 (b) • w q 1 →q 2 (b),
• τ A ((q, q )) = τ (q) • τ (q ),

• ρ A ((q, q )) = ρ(q) • ρ(q ). For each a k ∈ Σ, let M a k be the |Q| × |Q| matrix gathering the probabilities M a k ,q i ,q j = w q i →q j (a k ) that the transition going from state q i to state q j in A outputs the symbol a k . For notational convenience, we denote this probability by M a k (q i , q j ).

Now, given a string s = s 1 . . . s t , p(s) can be rewritten as follows:

p(s) = p(s 1 . . . s t ) = τ T M s 1 • • • M st ρ = τ T M s ρ, (4.4)
where τ and ρ are two vectors of dimension |Q| whose components are the values returned by the weight function τ (∀q ∈ S) and ρ (∀q ∈ F ) respectively, and

M s = M s 1 • • • M st .
From Equation 4.4, we get:

s∈Σ * p(s) = s∈Σ * τ T M s ρ. (4.5)
To take into account all possible strings s ∈ Σ * , Equation 4.5 can be rewritten according to the size of the string s:

s∈Σ * p(s) = ∞ i=0 τ T (M a 1 + M a 2 + • • • + M a |Σ| ) i ρ = τ T ∞ i=0 M i ρ, (4.6)
where

M = M a 1 + M a 2 + • • • + M a |Σ| . Denoting ∞ i=0 M i by B, note that B = I + M + M 2 + M 3 + . . . , (4.7)
where I is the identity matrix. Multiplying B by M we get

MB = M + M 2 + M 3 + . . . , (4.8)
and subtracting Equation 4.7 from Equation 4.8, we get:

B -MB = I ⇔ B = (I -M) -1 . (4.9)
Finally, plugging Equation 4.9 in Equation 4.6, we get a tractable expression for our kernel:

K e (x, x ) = s∈Σ * p e (s|x) • p e (s|x ) = τ T ∞ i=0 M i ρ = τ T (I -M) -1 ρ. (4.10)

Tractability

In this section, we investigate the complexity of computing K e (x, x ) using Equation 4.10

given two strings x and x . As we have seen in the previous section, this is essentially done by inverting a matrix. Let T be the cPFT modeling the edit probabilities and t its number of states. can be performed by back substitution, avoiding the complications of general Gaussian elimination. The cost of the inversion is in order of the square of the matrix dimension,

that is O(t 4 • |x| 2 • |x | 2 )
. This leads to an overall cost of

O(t 4 • |x| 2 • |x | 2 • |Σ|).
Recall that t stands for the size of the model T . In the case of memoryless models such as that of [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF] used in the experiments, t = 1 and thus the complexity is reduced to

O(|x| 2 • |x | 2 • |Σ|).
Therefore, in the case of a memoryless transducer, and for small alphabet sizes, the computational cost of our edit kernel is "only" the square of that of the standard edit distance.

Despite the fact that M is triangular, the algorithmic complexity remains high when strings are long and/or when the alphabet size is large. In this case, we may approximate Since the computational complexity of each probability p e (s|x) scales in |x| + |s|, the average cost of a kernel evaluation is

(|x| + |x | + |s|) • |T |,
where |s| is the average length of the training strings.

In conclusion, even if our kernel is rather costly from a complexity point of view, it can be derived from any transducer modeling edit probabilities, and may be approximated if needed. In the next section, we provide experimental evidence that our kernel outperforms standard and learned edit distances plugged in k-NN as well as standard string kernels.

Experimental Validation

Setup

To assess the relevance of our string edit kernel, we carry out experiments on the wellknown NIST Special Database 3 of the National Institute of Standards and Technology, which is a handwritten character dataset.

We focus on the set of 10,000 handwritten digits given as 128 × 128 bitmap images. We use a training sample of about 8, 000 instances and a test sample of 2, 000 instances.

Each instance is represented by a string of Freeman codes [START_REF] Freeman | Computer Processing of Line-Drawing Images[END_REF]. To encode a digit, the algorithm scans the bitmap from left to right, starting from the top until reaching the first pixel of the digit. It then follows the contour of the digit until it returns to the starting pixel. The string coding the digit is the sequence of Freeman codes representing the successive directions of the contour. We use SVM-Light2 as the SVM implementation to compare our approach with other string kernels and adopt a one-versus-all approach to deal with the multi-class setting.

This consists in learning a model M i for each class, where M i is learned from a positive class made of digits labeled i and a negative class made of differently labeled digits.

Then, the class of a test instance x is determined as follows: we compute the margin M i (x) for each model M i . A high positive value of M i (x) represents a high probability for x to be of class i. The predicted class of x is given by arg max i M i (x).

Comparison with Edit Distances

As done by [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF], our first objective is to compare our edit kernel K e with edit distances used in a k-NN algorithm. We use two edit distances: (i) the standard Levenshtein edit distance d lev with all costs set to 1, and (ii) a stochastic edit dissimilarity d e (x, x ) =log p e (x |x) learned with SEDiL [START_REF] Boyer | SEDiL: Software for Edit Distance Learning[END_REF], a software that implements (among others) the method of [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF].

We assess the performance of a 1-nearest neighbor algorithm using d lev and d e , and compare them with our string edit kernel plugged in a SVM classifier. Note that the We can make the following remarks:

• First, learning an edit distance d e on this classification task leads to better results than using the standard edit distance d lev . Indeed, the accuracy of d e is always higher than that of d lev regardless of the size of the training sample.

• Second, K e outperforms both the standard edit distance d lev and the learned edit distance d e for all training sample sizes. This highlights the usefulness of our kernel.

We estimate the statistical significance of these results using a Student's paired t-test. Using a risk of 5%, the difference is almost always significant in favor of our kernel (shown in boldface in the table).

These results are positive but not quite fair since our edit kernel is plugged into a SVM classifier while the edit distances are plugged into a k-NN classifier. In the next section, we compare K e with other string kernels of the literature.

Comparison with Other String Kernels

In this second series of experiments, we compare K e with:

• two classic string kernels, the spectrum kernel (Leslie et al., 2002a) and the subsequence kernel [START_REF] Lodhi | Text Classification using String Kernels[END_REF],

• a variant of the edit kernel of [START_REF] Li | A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs[END_REF] based on learned edit probabilities:3

K L&J (x , x) = e 1 2 t(log pe(x |x)+log pe(x|x )) ,
• and the edit kernel K N &B [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF] in its original version since it cannot accommodate p e in a straightforward way.

Recall that these kernels were presented in Section 2.3.3. We did not include the local alignment kernel [START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF] in this experimental study since it is based on local alignments and is specific to finding remote homologies in protein sequences.

The parameter p specifying the length of the considered subsequences in the spectrum and the subsequence kernel was set to 2. The subsequence kernel also has a parameter λ which is used to give less importance to subsequences with large gaps. We set λ to 2.

The parameter t of K L&J was set to 0.02. These parameter values give the best results on the dataset.

Figure 4.7 shows the results we obtain with the considered kernels. We first note that the best results are obtained with edit kernels. As in the previous experiment,

Conclusion

In this chapter, we designed a new string edit kernel that can make use of edit probabilities learned with generative or discriminative probabilistic models while enjoying the classification performance brought by SVM. We showed that although it involves an infinite sum over an entire language, our kernel can be computed exactly through the intersection of probabilistic automata built from the edit probability model and a matrix inversion. Experiments on a handwritten digit recognition task have shown that our edit kernel outperforms standard and learned edit distance within a k-NN framework as well as state-of-the-art string kernels.

An interesting perspective is to improve the algorithmic complexity of our kernel. The main bottleneck in its calculation is the size of the intersection automaton that allows the computation of p e (s|x)p e (s|x direct impact on the dimension of the matrix that has to be inverted, and thus on the evaluation cost of the kernel.

A second perspective is to extend this work to the design of tree edit kernels. Indeed, as seen in Section 3.3.2, generative and discriminative models for learning tree edit probabilities have been proposed and could be used to derive powerful tree edit kernels, based on the same ideas as in the string case.

While one of the advantages of the presented approach is to incorporate a lot of structural information by comparing inputs strings to an infinite number of strings, it makes it difficult to establish generalization guarantees. In the next chapter, we overcome this limitation by proposing a novel edit similarity learning approach that is not subject to many classic limitations of previous edit metric learning methods (in particular, those based on probabilistic models that our kernel uses) and for which we can derive a generalization bound. The idea is to relax the structural constraint on edit scripts to get an edit similarity that has a simpler form and can thus be learned through numerical optimization. The resulting (potentially non-PSD) similarity can then be used directly to build a linear classifier (that has bounded true risk), avoiding the computational cost of transforming it into a kernel. Furthermore, the linear classifiers are sparser than SVM models, speeding up prediction.

CHAPTER 5

Learning Good Edit Similarities from Local Constraints

Chapter abstract Metrics based on the edit distance are widely used to tackle problems involving string or tree-structured data. Unfortunately, as seen in Chapter 4, using them in kernel methods is often difficult and/or costly. On the other hand, the recently-proposed theory of ( , γ, τ )-good similarity functions bridges the gap between the properties of a non-PSD similarity function and its performance in linear classification. In this chapter, we show that this framework is well-suited to edit similarities. Furthermore, we make use of a relaxation of ( , γ, τ )-goodness to propose a novel edit similarity learning method, GESL, that avoids the classic drawbacks of previous approaches. Using uniform stability, we derive generalization bounds that hold for a large class of loss functions and show that they can be related to the error of a linear classifier built from the similarity. We also provide experimental results on two real-world datasets highlighting that edit similarities learned with GESL induce more accurate and sparser classifiers than other (standard or learned) edit similarities.

The material of this chapter is based on the following international publications: Aurélien Bellet, Amaury Habrard, and Marc Sebban. An Experimental Study on Learning with Good Edit Similarity Functions. In Proceedings of the 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pages 126-133, 2011a.

Aurélien Bellet, Amaury Habrard, and Marc Sebban. Learning Good Edit Similarities with Generalization Guarantees. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), pages 188-203, 2011c.

Aurélien Bellet, Amaury Habrard, and Marc Sebban. Good edit similarity learning by loss minimization. Machine Learning Journal (MLJ), 89(1):5-35, 2012b.

Introduction

As mentioned in the previous chapter, metrics based on the edit distance are widely used by practitioners when dealing with string or tree-structured data. Although they involve complex procedures, there exist a few methods (reviewed in Section 3.3) for learning edit metrics for a given task. These edit metrics are typically used in a k-NN setting. As we have seen in Chapter 4, using them in kernel methods such as SVM requires the design of a positive semi-definite edit kernel. However, existing edit kernels are either not guaranteed to be PSD, or involve rather costly procedures [START_REF] Li | A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs[END_REF][START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF]Bellet et al., 2010). Furthermore, there is a lack of theoretical understanding of how arbitrary similarity functions can be used to learn accurate linear classifiers.

Recently, [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF]2008a;2008b) introduced a theory of learning with socalled ( , γ, τ )-good similarity functions that gives intuitive, sufficient conditions for a similarity function to allow one to learn well. Essentially, a similarity function K is ( , γ, τ )-good if a 1proportion of examples are on average more similar to reasonable examples of the same class than to reasonable examples of the opposite class by a margin γ, where a τ proportion of examples must be reasonable. K does not have to be a metric nor positive semi-definite (PSD). They show that if K is ( , γ, τ )-good, then it can be used to build a linear separator in an explicit projection space that has margin γ and error arbitrarily close to . This separator can be learned efficiently using a linear program and tends to be sparse thanks to L 1 norm regularization.

The first contribution of this work is to experimentally show that this theory is wellsuited to edit similarity functions and is competitive with SVM in terms of accuracy, while inducing sparser models. Furthermore, we show that we can make use of this framework to propose a new approach to learning string and tree edit similarities which addresses the classic drawbacks of other methods in the literature, i.e., lack of generalization guarantees, high computational cost, convergence to suboptimal solution and inability to use the information brought by negative pairs. Our approach (GESL, for Good Edit Similarity Learning) is driven by the idea of ( , γ, τ )-goodness: we learn the edit costs so as to optimize a relaxation of the goodness of the resulting similarity function. It is based on regularized risk minimization (formulated as an efficient convex program) over some positive and negative training pairs: the similarity is thus optimized with respect to local constraints but plugged in a global linear classifier. We provide an extensive theoretical study of the properties of GESL based on a notion of uniform stability adapted to metric learning [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF], leading to the derivation of a generalization bound that holds for a large class of loss functions. This bound can be related to the generalization error of the linear classifier built from the similarity and is independent of the size of the alphabet, making GESL suitable for handling problems with large alphabet. To the best of our knowledge, this is the first edit metric learning method with generalization guarantees, and the first attempt to establish a theoretical relationship between a learned metric and the risk of a classifier using it. We show in a comparative experimental study that GESL has fast convergence and leads to more accurate and sparser classifiers than other (standard or learned) edit similarities.

The rest of this chapter is organized as follows. In Section 5.2, we introduce the theory of ( , γ, τ )-goodness. Section 5.3 features a preliminary study that provides experimental evidence that this theory is well-suited to edit similarity functions and leads to classifiers that are competitive with SVM classifiers. Section 5.4 presents GESL, our approach to learning ( , γ, τ )-good edit similarities. We show that it is a suitable way to deal not only with strings but also with tree-structured data. We propose in Section 5.5 a theoretical analysis of GESL based on uniform stability, leading to the derivation of a generalization bound. We also provide a discussion on that bound and its implications, as well as a way of deriving a bound for the case where instances have unbounded size. A wide experimental evaluation of our approach on two real-world string datasets from the natural language processing and image classification domains is provided in Section 5.6.

Finally, we conclude this work in Section 5.7.

The Theory of ( , γ, τ )-Good Similarity Functions

In recent work, [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF]2008a;2008b) introduced a new theory of learning with good similarity functions. Their motivation was to overcome two major limitations of kernel theory. First, a good kernel is essentially a good similarity function, but the theory talks in terms of margin in an implicit, possibly unknown projection space, which can be a problem for intuition and design. Second, the PSD and symmetry requirement often rules out natural similarity functions for the problem at hand. As a consequence, Balcan et al. (2008b) proposed the following definition of good similarity function.

Definition 5.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 1 -probability mass of examples (x, y) satisfy E (x ,y )∼P [yy K(x, x )|R(x )] ≥ γ, (5.1) 2. Pr x [R(x )] ≥ τ .
K(x, x ) = 1 -x -x 2 .
We picked 3 reasonable points (A, B and E, circled in black), thus we can set τ = 3/8. Similarity scores to the reasonable points as well as the margin achieved by each point (as given by Equation 5.1) are shown in the array. There exists an infinite number of valid instantiations of and γ since there is a trade-off between the margin γ and proportion of margin violations . For example, K is (0, 0.006, 3/8)-good because all points ( = 0) are on average more similar to reasonable examples of the same class than to reasonable examples of the other class by a margin γ = 0.006. One can also say that K is (2/8, 0.01, 3/8)-good ( = 2/8 because examples C and D violate the margin γ = 0.01). (2007,2009) for unbounded dissimilarity functions. Yet Definition 5.1 is very interesting in three respects. First, it is a strict generalization of the notion of good kernel (Balcan et al., 2008b) but does not impose positive semi-definiteness nor symmetry. Second, as opposed to pair and triplet-based criteria used in metric learning, Definition 5.1 is based on an average over some points. In other words, it relaxes the notion of local constraints, opening the door to metric learning for global algorithms. Third, these conditions are sufficient to learn well, i.e., to induce a classifier with low true risk, as we show in the following.

Let K be an ( , γ, τ )-good similarity function. If the set of reasonable points R = {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x |R| , y |R| )} is known, it follows directly from Equation 5.1 that

E F G H A B C D K(x, A) K(x, B) K(x, E)
Figure 5.2: Projection space (φ-space) implied by the toy example of Figure 5.1: similarity scores to the reasonable points (A, B and E) are used as new features. Since K is (0, γ, 3/8) for some γ > 0, the linear separator of equation K(x, A) + K(x, B) -K(x, E) = 0 (shown as a green grid) achieves perfect classification, although the data were not linearly separable in the original space.

the following classifier achieves true risk at most at margin γ:

h(x) = sign   1 |R| |R| i=1 y i K(x, x i )   .
Note that h is a linear classifier in the space of the similarity scores to the reasonable points. In other words, K is used to project the data into a new space using the mapping φ : X → R |R| defined as:

φ i (x) = K(x, x i ), i ∈ {1, . . . , |R|}.
The projection and linear classifier corresponding to the toy example of Figure 5.1 is shown in Figure 5.2.

However, in practice the set of reasonable points is unknown. We can get around this problem by sampling points (called landmarks) and use them to project the data into a new space (using the same strategy as before).2 If we sample enough landmarks (this depends in particular on τ , which defines how likely it is to draw a reasonable point), then with high probability there exists a linear classifier in that space that achieves true risk close to . This is formalized in Theorem 5.2.

Theorem 5.2 (Balcan et al., 2008b). Let K be an ( , γ, τ )-good similarity function for a learning problem P . Let L = {x 1 , x 2 , . . . , x n L } be a sample of n L = 2 τ log(2/δ) + 8 log(2/δ) γ 2 landmarks drawn from P . Consider the mapping φ L : X → R n L defined as follows:

φ L i (x) = K(x, x i ), i ∈ {1, . . . , n L }.
Then, with probability at least 1δ over the random sample L, the induced distribution φ L (P ) in R n L has a linear separator of error at most + δ relative to L 1 margin at least γ/2. Unfortunately, finding this separator is NP-hard (even to approximate) because minimizing the number of L 1 margin violations is NP-hard. To overcome this limitation, the authors considered the hinge loss as a surrogate for the 0/1 loss (which counts the number of margin violations) in the following reformulation of Definition 5.1.

Definition 5.3 (Balcan et al., 2008b). A similarity function K is an ( , γ, τ )-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. E (x,y)∼P [[1 -yg(x)/γ] + ] ≤ , where g(x) = E (x ,y )∼P [y K(x, x )|R(x )], 2. Pr x [R(x )] ≥ τ .
This leads to the following theorem, similar to Theorem 5.2.

Theorem 5.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 n L } be a sample of n L = 2 τ log(2/δ) + 16 log(2/δ) 1 γ 2 landmarks drawn from P . Consider the mapping φ L : X → R n L defined as follows: φ L i (x) = K(x, x i ), i ∈ {1, . . . , n L }. Then, with probability at least 1δ over the random sample L, the induced distribution φ L (P ) in R n L has a linear separator of error at most + 1 at margin γ.

The objective is now to find a linear separator α ∈ R n L that has low true risk based on the expected hinge loss relative to L 1 margin γ:

E (x,y)∼P 1 -y α, φ L (x) /γ + .
Using a landmark sample L = {x 1 , x 2 , . . . , x n L } and a training sample T = {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x n , y n )}, one can find this separator α efficiently by solving the following linear program (LP):

3 min α n i=1   1 - n L j=1 α j y i K(x i , x j )   + + λ α 1 .
(5.2)

In practice, we simply use the training examples as landmarks. In this case, learning rule (5.2) -referred to as "Balcan's learning rule" in the rest of this document -is reminiscent of the standard SVM formulation, with three important differences. First, recall that K is not required to be PSD nor symmetric. Second, the linear classifier lies in an explicit projection space built from K (called an empirical similarity map) rather than in a possibly implicit Hilbert Space induced by a kernel. Third, it uses L 1 regularization, inducing sparsity in α and thus reducing the number of landmarks the classifier is based on, which speeds up prediction. 4 This regularization can be interpreted as a way to select (or approximate) the set of reasonable points among the landmarks: in a sense, R is automatically worked out while learning α.5 Note that we can control the degree of sparsity of the linear classifier: the larger λ, the sparser α.

To sum up, the performance of the linear classifier theoretically depends on how well the similarity function satisfies Definition 5.1. In this chapter, we first conduct a preliminary experimental study to investigate the level of ( , γ, τ )-goodness of some edit similarities and their performance in classification when used in Balcan's learning rule (Section 5.3).

The rest of the chapter is the main contribution and is devoted to learning ( , γ, τ )-good edit similarities from data.

Preliminary Experimental Study

In this section, we experimentally show that the framework of ( , γ, τ )-goodness is wellsuited to edit similarities. We first investigate the goodness of edit similarities on the previously-studied handwritten digit recognition task (Section 5.3.1). Then, in Section 5.3.2, we compare the performance of linear classifiers learned with Balcan's rule using edit similarities with the performance of SVM using standard edit kernels.

Are Edit Similarities Really ( , γ, τ )-Good?

In this experimental evaluation of the ( , γ, τ )-goodness of edit similarities, we will consider the standard Levenshtein distance d lev and edit probabilities p e learned with the method of [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF]. We actually use -d lev so that both similarities express a measure of closeness, making the comparison easier. We also normalized them so that they lie in [-1, 1]. 6 In the following, they are referred to as dlev and pe . Looking at Definition 5.1, we can easily estimate , γ and τ using a randomly selected set of points.

We illustrate this on the NIST Special Database 3, the handwritten digit recognition Since we do not know the set of reasonable points before learning the linear classifier, we fix τ = 1 (i.e., all points are considered reasonable) and plot as a function of γ. In order to analyze the results in different contexts, we randomly selected 500 instances of each class and estimated the goodness of the similarities for each binary problem. For brevity, we only discuss the goodness curves for two representative problems: "0 vs. 1" and "0 vs. 8", shown in Figure 5.3. The interpretation (given by Definition 5.1) is that a margin γ leads to an proportion of examples violating the margin. For the "0 vs. 1" problem, shown in Figure 5.3(a), both similarities achieve good margin while keeping the number of violations small. The learned similarity pe behaves slightly better. The "0 vs.

8" problem is a harder task, since the representation of an eight is often similar to that of a zero (because Freeman codes only encode the contour of the digits). reflects the difficulty of the task, since margin violations are almost always higher for a given γ than in the "0 vs. 1" case. For the "0 vs. 8" task, the learned similarity provides an important improvement over the standard edit distance: for small margin values, it achieves few margin violations.

To sum up, we see that decent values for γ and are achieved even without selecting an appropriate subset R of reasonable points. Note that we observe a similar behavior for all binary problems in the dataset. Therefore, edit similarities satisfy Definition 5.1 rather well, thus Theorem 5.4 is meaningful and we can expect good accuracy in linear classification on this dataset. Moreover, pe seems to be "( , γ, τ )-better" than dlev , which suggests that it could achieve better generalization performance. We will see that it is indeed the case in the next section.

Experiments

In this section, we provide experimental evidence that learning with Balcan's learning rule using edit similarities outperforms a k-NN approach and is competitive with a standard SVM approach, while inducing much sparser models. As noted earlier, standard SVM and Balcan's learning rule are similar but use different regularizers (L 2 norm and L 1 norm respectively). The comparative performance of L 2 and L 1 regularized learning rules has been the subject of previous experimental studies (see for instance Zhu et al., 2003) but, to the best of our knowledge, never in the context of edit similarities. Furthermore, ( , γ, τ )-goodness provides a theoretical justification of Balcan's learning rule and casts an interesting light on this comparison.7

We compare the following approaches: (i) Balcan's learning rule (5.2) using K(x, x ) = dlev (x, x ), (ii) Balcan's learning rule using K(x, x ) = pe (x |x), (iii) SVM learning using x ) , the kernel of [START_REF] Li | A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs[END_REF] based on d lev , (iv) SVM learning using K(x, x ) = e 1 2 t(log pe(x |x)+log pe(x|x )) , the kernel of [START_REF] Li | A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs[END_REF] based on p e , (v) 1-NN using d lev (x, x ), and (vi) 1-NN using -p e (x |x). We choose Libsvm8 as the SVM implementation, which takes a one-versus-one approach for multi-class classification.

K(x, x ) = e -t•d lev (x,
We thus use the same strategy for multi-class classification with Balcan's learning rule.

Note that we take the training examples to be the landmarks. Therefore, all learning algorithms have access to strictly the same information (that is, similarity measurements between training examples), allowing a fair comparison.

In the following, we present results on the multi-class handwritten digit classification task and on a dataset of English and French words.

Handwritten digit classification

Using the handwritten digit classification dataset, we first aim at evaluating the performance of the models obtained with different methods. We use 40 to 6,000 training examples, reporting the results under 5-fold cross-validation. The parameters of the models, such as λ for approaches (i-ii) or C and t for approaches (iii-iv), are tuned by cross-validation on an independent set of examples, always selecting the value that offers the best classification accuracy.

Accuracy and sparsity Classification accuracy is reported in Figure 5.4(a). All methods perform essentially the same, except for 1-NN that is somewhat weaker. Note that the methods based on the learned edit probabilities are, as expected, more accurate than those based on the standard edit distance. The influence of λ on the models learned with Balcan is shown in Figure 5.5. The results confirm that λ can be conveniently used to control the sparsity of the models thanks to L 1 regularization. It is worth noting that while the best accuracy is obtained with relatively small values (λ ∈ [1; 10]), one can get even sparser but still very accurate models with larger values (λ ∈ [10; 200]). This is especially true when using pe . Therefore, one can learn a model with Balcan that is just slightly less accurate than the corresponding SVM model while being 10 to 18 times sparser. This can be a useful feature, in particular in applications where data storage is limited and/or high classification speed is required.

We also investigate the influence of parameter t on the performance of the SVM models.

Results are shown in Figure 5.6 (a log-scale is used to allow a better appreciation of the variations). Both the accuracy and the sparsity of the SVM models are heavily dependent on t: only a narrow range of t values (probably those achieving positive semi-definiteness) allows for accurate and acceptably-sized models. Furthermore, this range appears to be specific to the edit similarity used. Therefore, t must be tuned very carefully, which represents a waste of time and data.

Lastly, one might wonder whether the SVM parameter C can also be used to improve the sparsity of the models in the same way as λ. In order to assess this, we try a wide range of C values and record the average sparsity of the models. SVM could not match the sparsity of the models learned with Balcan. The best average size for a binary model was greater than 100, i.e., more than 2 times bigger than the worst model size obtained with Balcan. This results from the tendency of L 2 regularization to select models that put small weights on many coordinates.

English and French words classification

In this second series of experiments, we choose a different and harder task: classifying words as either English or French. We use the 2,000 top words lists from Wiktionary.9

We only consider unique words (i.e., not appearing in both lists) of length at least 4, and we also get rid of accent and punctuation marks. We end up with about 2,600 words. We keep 600 words aside for cross-validation of parameters, 400 words to test the models and use the remaining words to learn the models.

Classification accuracy is reported in Figure 5.7(a). Note that this binary task is significantly harder than the one presented in the previous section, and that once again,

Conclusion

In this section, we have shown that edit similarities fit the framework of ( , γ, τ )-goodness and that the performance is competitive with standard SVM, with the additional advantages that arbitrary (in particular, non-PSD) similarities can be used and that the classifiers are sparser. We have also seen that this series of experiments confirms the theoretical dependence between the ( , γ, τ )-goodness of the edit similarity function and its performance in classification.

However, for some tasks, standard edit similarities may satisfy the definition of ( , γ, τ )goodness poorly. Furthermore, existing methods for learning edit similarities rely on maximum likelihood and may not lead to an improved similarity function from an ( , γ, τ )-goodness point of view. [START_REF] Kar | Similarity-based Learning via Data Driven Embeddings[END_REF] propose to automatically adapt the goodness criterion to the problem at hand. In the rest of this chapter, we take a different approach: we see the ( , γ, τ )-goodness as a novel, theoretically well-founded criterion to optimize an edit similarity.

Learning ( , γ, τ )-Good Edit Similarity Functions

In this section, we propose a novel convex programming approach based on the theory of Balcan et al. (2008b) to learn ( , γ, τ )-good edit similarity functions from both positive and negative pairs without requiring a costly iterative procedure. We will see in Section 5.5 that this framework allows us to derive generalization bounds establishing the consistency of our method and a relationship between the learned similarities and the generalization error of the linear classifier using it.

We begin this section by introducing an exponential-based edit similarity function that can be optimized in a direct way. Then, we present our convex programming approach to the problem of learning ( , γ, τ )-good edit similarity functions, followed by a discussion on building relevant training pairs in this context. Finally, we end this section by showing that our approach can be straightforwardly adapted to tree edit similarity learning.

An Exponential-based Edit Similarity Function

In order to avoid the drawbacks of using iterative approaches such as EM for edit similarity learning, we propose to define an edit similarity for which the edit script does not depend on the edit costs.

Let C ∈ R (|Σ|+1)×(|Σ|+1) +
be the edit cost matrix and for any x, x ∈ Σ * , let #(x, x ) be a (|Σ| + 1) × (|Σ| + 1) matrix whose elements # i,j (x, x ) correspond to the number of times each edit operation i → j is used to turn x into x in the Levenshtein script, 0 ≤ i, j ≤ |Σ|. We define the following edit function:

e C (x, x ) = 0≤i,j≤|Σ| C i,j # i,j (x, x ).
To compute e C , we do not extract the optimal script with respect to C: we use the Levenshtein script10 and apply custom costs C to it. Therefore, since the edit script defined by #(x, x ) is fixed, e C (x, x ) is nothing more than a closed-form linear function of the edit costs and can be optimized directly.

Recall that a similarity function is assumed to be in [-1, 1]. To respect this requirement, we define our similarity function to be:

K C (x, x ) = 2e -e C (x,x ) -1.
Beyond this normalization requirement, the motivation for this exponential form is related to the one for using exponential kernels in SVM classifiers: it can be seen as a way to introduce nonlinearity to further separate examples of opposite class while moving closer those of the same class. Note that K C may not be PSD nor symmetric. However, as we have seen earlier and unlike kernel theory, the theory of Balcan et al. (2008b) does not require these properties. This allows us to consider a broader type of edit similarity functions.

Learning the Edit Costs

We aim at learning the edit cost matrix C so as to optimize the ( , γ, τ )-goodness of K C . We first focus on optimizing the goodness based on a relaxation of Definition 5.3, leading to a formulation based on the hinge loss (GESL HL ). Then, we introduce a more general version that can accommodate other loss functions (GESL L ).

Hinge Loss Formulation

Here, we want to learn K C so that its hinge loss-based goodness (Definition 5.3) is optimized. More precisely, given a set of reasonable points and a margin γ, we want to optimize the amount of margin violation . Ideally, we would like to directly optimize Definition 5.3. Unfortunately, this would result in a nonconvex formulation (summing and subtracting up exponential terms) subject to local minima. Instead, we propose to optimize the following criterion:

E (x,y) E (x ,y ) 1 -yy K C (x, x )/γ + |R(x ) ≤ .
(5.3) Criterion (5.3) bounds that of Definition 5.3 due to the convexity of the hinge loss:

clearly, if K C satisfies (5.3), then it is ( , γ, τ )-good in hinge loss with ≤ . Indeed, it is harder to satisfy since the "goodness" is required with respect to each reasonable point instead of considering the average similarity to these points. Therefore, optimizing K C according to (5.3) implies the use of pair-based constraints.

Let us now consider a training sample T = {z i = (x i , y i )} n T i=1 of n T labeled instances. Recall that we do not know the set of reasonable points at this stage: they are inferred while learning the separator, that is, after the similarity is learned. For this reason, as in most metric learning methods, we will suppose that we are given pairs of examples.

Formally, we suppose the existence of an indicator pairing function f land : T ×T → {0, 1} which takes as input two training examples in T and returns 1 if they are paired and 0 otherwise. We assume that f land associates to each element z ∈ T exactly n L examples (called, with a slight abuse of language, the landmarks for z), leading to a total of n T n L pairs. We discuss this matter further in Section 5.4.3.

Our formulation aims at fulfilling (5.3) for each (z i , z j ) such that f land (z i , z j ) = 1. Therefore, we want [1y i y j K C (x i , x j )/γ] + = 0, hence y i y j K C (x i , x j ) ≥ γ. A benefit from using this constraint is that it can easily be turned into an equivalent linear one, considering the following two cases.

1. If y i = y j , we get:

-K C (x i , x j ) ≥ γ ⇐⇒ e -e C (x i ,x j ) ≤ 1 -γ 2 ⇐⇒ e C (x i , x j ) ≥ -log( 1 -γ 2 ).
We can use a variable B 1 ≥ 0 and write the constraint as e C (x i , x j ) ≥ B 1 , with the

interpretation that B 1 = -log( 1-γ 2 ). In fact, B 1 ≥ -log( 1 2 ).
2. Likewise, if y i = y j , we get e C (x i , x j ) ≤log( 1+γ 2 ). We can use a variable B 2 ≥ 0 and write the constraint as e C (x i , x j ) ≤ B 2 , with the interpretation that B 2 = log( 1+γ2 ). In fact, B 2 ∈ 0,log( 12 ) .

The optimization problem GESL HL can then be expressed as follows:

(GESL HL ) min

C,B 1 ,B 2 1 n T n L 1≤i≤n T , j:f land (z i ,z j )=1 HL (C, z i , z j ) + β C 2 F s.t. B 1 ≥ -log( 1 2 ), 0 ≤ B 2 ≤ -log( 1 2 ), B 1 -B 2 = η γ C i,j ≥ 0, 0 ≤ i, j ≤ |Σ|,
where β ≥ 0 is a regularization parameter on edit costs, η γ ≥ 0 a parameter corresponding to the desired "margin" and

HL (C, z i , z j ) = [B1 -e C (x i , x j )] + if y i = y j [e C (x i , x j ) -B2] + if y i = y j .
The relationship between the margin γ and η γ is given by γ = e ηγ -1 e ηγ +1 . We chose Frobenius norm regularization because (i) it is simple, smooth and thus easier to optimize, and (ii) it allows us to derive generalization guarantees using uniform stability, as we will see in Section 5.5. GESL HL is a convex program, thus one can efficiently find its global optimum. Using n T n L slack variables to express each hinge loss, it has O(n T n L + |Σ| 2 ) variables and O(n T n L ) constraints. Note that GESL HL is a sparse convex program: each constraint involves at most one string pair and a limited number of edit cost variables, making the problem faster to solve. It is also worth noting that our approach is very flexible.

First, it is general enough to be used with any definition of e C that is based on an edit script (or even a convex combination of edit scripts). Second, one can incorporate additional convex constraints, for instance to include background knowledge or desired requirements on C (e.g., symmetry). Third, it can be easily adapted to the multi-class case. Finally, it can be generalized to a larger class of loss functions, as we show in the following section.

General Formulation

In the previous section, we made use of the hinge loss-based Definition 5.3 to propose GESL HL . Yet, other reformulations of Definition 5.1 are possible using any convex loss function that can be used to efficiently penalize the amount of violation with respect to margin γ. For instance, the logistic loss or the exponential loss could be used. This would also allow the derivation of learning guarantees (similar to Theorem 5.4) and an efficient learning rule.

Therefore, it is useful to be able to optimize a definition of ( , γ, τ )-goodness based on a loss other than the hinge. Let (C, z, z ) be a convex loss function with respect to an edit cost matrix C and a pair of examples (z, z ). Our optimization problem can then be expressed in a more general form as follows:

(GESL L ) min C 1 n T n L 1≤i≤n T , j:f land (z i ,z j )=1 (C, z i , z j ) + β C 2 F .
In the rest of the paper, we will use GESL to refer to our approach in general, GESL L when using an arbitrary loss function and GESL HL for the specific case of the hinge loss.

Pairing strategy

The question of how one should define the pairing function f land relates to the open question of building training pairs in many metric learning problems. In some applications, the answer may be trivial: for instance, a misspelled word and its correction.

Otherwise, popular choices are to pair each example with its nearest neighbor, random pairing or simply to consider all possible pairs. On the other hand, the ( , γ, τ )-goodness of the similarity should be improved with respect to the reasonable points, a subset of examples of probability τ that allows low error and large margin. However, this set depends on the similarity function itself and is thus unknown beforehand. Yet, a relevant strategy in the context of ( , γ, τ )-goodness may be to improve the similarity with respect to carefully selected examples rather than considering all possible pairs. Consequently, we consider two pairing strategies that will be compared in our experiments (Section 5.6):

1. Levenshtein pairing: we pair each z ∈ T with its n T nearest neighbors of the same class and its n T farthest neighbors of the opposite class, using the Levenshtein distance. This pairing strategy is meant to capture the essence of Definition 5.1 and in particular the idea that reasonable points "represent" the data well. Essentially, we pair z with a few points that are already good representatives of z and optimize the edit costs so that they become even better representatives. Note that the choice In either case, we have n L = 2N = αn T with 0 < α ≤ 1. Taking α = 1 corresponds to considering all possible pairs. In a sense, α can be seen as playing the role of τ (which gives the proportion of points that are reasonable in the definition of goodness) at the pair level, even though no direct relation can be made between the two.

Adaptation to trees

So far, we have implicitly considered that the data are strings. In this section, before presenting a theoretical analysis of GESL, we show that it may be used in a simple and efficient way to learn tree edit similarities. As mentioned in Section 5.4.1, our edit function, defined as

e C (x, x ) = 0≤i,j≤|Σ| C i,j # i,j (x, x ),
is nothing more than a linear combination of the edit costs, where # i,j (x, x ) is the number of times the edit operation i → j occurs in the Levenshstein script turning x into x . This opens the door to a straightforward generalization of GESL to tree edit distance: instead of a string edit script, we can use a tree edit script according to either variant of the tree edit distance (Zhang & Shasha, 1989;[START_REF] Stanley | The tree-to-tree editing problem[END_REF] and solve the (otherwise unchanged) optimization problem presented in Section 5.4.2. This allows us, once again, to avoid using a costly iterative procedure. We only have to compute the edit script between two trees once, which dramatically reduces the algorithmic complexity of the learning algorithm. Moreover, we will see that the theoretical analysis of GESL presented in the following section holds for tree edit similarity learning.

Theoretical Analysis

This section presents a theoretical analysis of GESL. In Section 5.5.1, we derive a generalization bound guaranteeing its consistency and relating to the ( , γ, τ )-goodness in generalization of the learned similarity function, and thus to the true risk of the linear classifier. This theoretical study is performed for a large class of loss functions. In Section 5.5.2, we instantiate this generalization bound for the specific case of the hinge loss (GESL HL ). Finally, Section 5.5.3 is devoted to a discussion about the main features of the bounds, and to the presentation of a way to get rid of the assumption that the length of the strings (or the size of the trees) is bounded.

Generalization Bound for General Loss Functions

As pointed out in Chapter 3, the training pairs used in metric learning are not i.i.d.

and therefore the classic results of statistical learning theory do not directly hold. To derive a generalization bound for GESL L , we build upon the adaptation of uniform stability to the metric learning case [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF] and extend it to edit similarity learning. We first prove that GESL L has a uniform stability: this is established in Theorem 5.9, using Lemma 5.8 and the assumption of k-lipschitzness (Definition 5.5).

The stability property allows us to derive our generalization bound (Theorem 5.13) using the McDiarmid inequality (Theorem 5.10) and the assumption of (σ, m)-admissibility (Definition 5.6).

We denote the objective function of GESL L by:

F T (C) = 1 n T n T k=1 1 n L n L j=1 (C, z k , z k j ) + β C 2 F ,
where z k j denotes the j th landmark associated to z k and (C, z k , z k j ) the loss for a pair of examples with respect to an edit cost matrix C.

The first term of F T (C) is the empirical risk R T (C) over the training sample T . The true risk R (C) is given by:

R (C) = E (z,z )∼P [ (C, z, z )].
Recall that our empirical risk is not defined over all possible training pairs, unlike most metric learning algorithms, but according to some particular landmark examples. On the other hand, the true risk is defined over any pair of instances. For notational convenience, we also introduce the estimation error D T , which is the deviation between the true risk and the empirical risk:

D T = R (C T ) -R T (C T ),
where C T denotes the edit cost matrix learned by GESL L from T .

∆C = (C T -C T i,z

). For any t ∈ [0, 1]:

C T 2 F -C T -t∆C 2 F + C T i,z 2 F -C T i,z + t∆C 2 F ≤ (2n T + n L )t2k βn T n L ∆C F .
Proof. See Appendix B.1.1.

We can now prove the stability of GESL L . Proof. Using t = 1/2 on the left-hand side of Lemma 5.8, we get

C T 2 F -C T - 1 2 ∆C 2 F + C T i,z 2 F -C T i,z + 1 2 ∆C 2 F = 1 2 ∆C 2 F .
Then, applying Lemma 5.8, we get

1 2 ∆C 2 F ≤ (2n T + n L )k βn T n L ∆C F ⇒ ∆C F ≤ 2(2n T + n L )k βn T n L .
Now, from the k-lipschitz property of , we have for any z, z

| (C T , z, z ) -(C T i,z , z, z )| ≤ k ∆C F ≤ 2(2n T + n L )k 2 βn T n L .
Replacing n L by αn T completes the proof. Now, using the property of stability, we can derive our generalization bound over R (C T ). This is done by using the McDiarmid inequality [START_REF] Mcdiarmid | Surveys in Combinatorics, chapter On the method of bounded differences[END_REF].

Theorem 5.10 (McDiarmid inequality). Let X 1 , . . . , X n be n independent random variables taking values in X and let

Z = f (X 1 , . . . , X n ). If for each 1 ≤ i ≤ n, there exists a constant c i such that sup x 1 ,...,xn,x i ∈X |f (x 1 , . . . , x n ) -f (x 1 , . . . , x i , . . . , x n )| ≤ c i , ∀1 ≤ i ≤ n, then for any > 0, Pr[|Z -E[Z]| ≥ ] ≤ 2 exp -2 2 n i=1 c 2 i .
To derive our bound on R (C T ), we just need to replace Z by D T in Theorem 5.

∀i, 1 ≤ i ≤ n T , ∀z, |D T -D T i,z | ≤ 2κ n T + (2n T + n L )(2σ + m) n T n L .
Proof. See Appendix B.1.3.

We are now able to derive our generalization bound over R (C T ).

Theorem 5.13 (Generalization bound for GESL L ). Let T be a sample of n T randomly

selected training examples and let C T be the edit cost matrix learned by GESL L with stability κ n T . Assuming that (C T , z, z ) is k-lipschitz and (σ, m)-admissible, and using n L = αn T landmark points, with probability 1δ, we have the following bound for

R (C T ): R (C T ) ≤ R T (C T ) + 2 κ n T + 2κ + 2 + α α (2σ + m) ln(2/δ) 2n T with κ = 2(2+α)k 2 αβ . Proof. Recall that D T = R (C T ) -R T (C T )
and n L = αn T . From Lemma 5.12, we get

|D T -D T i,z | ≤ sup T ,z |D T -D T i,z | ≤ 2κ + B n T with B = (2 + α) α (2σ + m).
Then by applying the McDiarmid inequality, we have

Pr[|D T -E T [D T ]| ≥ ] ≤ 2 exp   - 2 2 n T i=1 (2κ+B) 2 n 2 T   ≤ 2 exp - 2 2 (2κ+B) 2 n T .
(5.4)

By fixing δ = 2 exp - 2 2
(2κ+B) 2 /n T , we get = (2κ + B) ln(2/δ) 2n T . Finally, from (5.4), Lemma 5.11 and the definition of D T , we have with probability at least 1δ:

D T < E T [D T ] + ⇒ R (C T ) < R T (C T ) + 2 κ n T + (2κ + B) ln(2/δ) 2n T ,
which gives the theorem.

Generalization Bound for the Hinge Loss

Theorem 5.13 holds for any loss function (C T , z, z ) that is k-lipschitz and (σ, m)admissible with respect to C T . Let us now rewrite this bound when is the hinge loss-based function HL used in GESL HL . We first have to prove that HL is k-lipschitz (Lemma 5.14) and (σ, m)-admissible (Lemma 5.16). Then, we derive the generalization bound for GESL HL .

In order to fulfill the k-lipschitz and (σ, m)-admissibility properties, we suppose every string length bounded by a constant W > 0. Since the Levenshtein script between two strings x and x contains at most max(|x|, |x |) operations, we have

#(x, x ) F = l,c # l,c (x, x ) 2 ≤   l,c # l,c (x, x )   2 ≤ W.
When dealing with labeled instances, we will sometimes denote #(x, x ) F ≤ W by #(z 1 , z 2 ) F ≤ W for the sake of convenience.

Lemma 5.14. The function HL is k-lipschitz with k = W .

Proof. See Appendix B.1.4.

We will now prove that HL is (σ, m)-admissible for any optimal solution C T learned by GESL HL (Lemma 5.16). To be able to do this, we must show that the norm of C T is bounded (Lemma 5.15). Proof. Let C T be an optimal solution learned by GESL HL from a training sample T and let z 1 , z 2 , z 3 , z 4 be four labeled examples. We study two cases:

1. If y 1 y 2 = y 3 y 4 , regardless of the label values, using the 1-lispschitz property of the hinge loss, B 1 (when y 1 y 2 = y 3 y 4 = -1) or B 2 (y 1 y 2 = y 3 y 4 = 1) cancels out (in a similar way as in Appendix 5.14) and thus :

| HL (C T , z 1 , z 2 ) -HL (C T , z 3 , z 4 )| ≤ C T F #(z 1 , z 2 ) -#(z 3 , z 4 ) F ≤ B γ β W from Lemma 5.15. 2. Otherwise, if y 1 y 2 = y 3 y 4 , note that |B 1 +B 2 | = η γ +2B 2 ≤ 3B γ and |y 1 y 2 -y 3 y 4 | = 2.
Hence, whatever the labels of the examples compatible with this case, by using the 1-lipschitz property of hinge loss and application of the triangular inequality, we get

| HL (C T , z 1 , z 2 ) -HL (C T , z 3 , z 4 )| ≤ | l,c C T ,l,c (# l,c (z 1 , z 2 ) + # l,c (z 3 , z 4 ))| + |B 1 + B 2 | ≤ C T F #(z 1 , z 2 ) + #(z 3 , z 4 ) F + 3B γ ≤ B γ β 2W + 3B γ ≤ Bγ β W + 3B γ 2 |y 1 y 2 -y 3 y 4 | + B γ β W.
Then, by choosing σ = We can now give the convergence bound for GESL HL .

Theorem 5.17 (Generalization bound for GESL HL ). Let T be a sample of n T randomly selected training examples and let C T be the edit cost matrix learned by GESL HL with stability κ n T using n L = αn T landmark points. With probability 1δ, we have the following bound for R (C T ):

R (C T ) ≤ R T (C T ) + 2 κ n T + 2κ + 2 + α α 2W βB γ + 3 B γ ln(2/δ) 2n T with κ = 2(2+α)W 2 αβ and B γ = max(η γ , -log(1/2)).
Proof. It directly follows from Theorem 5.13, Lemma 5.14 and Lemma 5.16 by noting

that 2σ + m = 2W √ βBγ + 3 B γ .

Discussion

The generalization bounds presented in Theorem 5.13 and Theorem 5.17 outline three important features of our approach. To begin with, it has a classic O( 1/n T ) convergence rate. Second, this rate of convergence is independent of the alphabet size, which means that our method should scale well to problems with large alphabets. We will see in Section 5.6 that it is actually the case in practice. Finally, thanks to the relation between the optimized criterion and the definition of ( , γ, τ )-goodness that we established earlier, these bounds also ensure the goodness in generalization of the learned similarity function. Therefore, they guarantee that the similarity will induce classifiers with small true risk for the classification task at hand.

Note that to derive Theorem 5.17, we assumed the size of the strings was bounded by a constant W . Even though this is not a strong restriction, it would be interesting to get rid of this assumption and derive a bound that is independent of W . This is possible when the marginal distribution of P over the set of strings follows a generative model ensuring that the probability of a string decreases exponentially fast with its length.

In this case, we can use the fact that very long strings have a very small probability to occur. Then with high probability, we can bound the maximum string length in a sample and remove W from the generalization bound. Indeed, one can show that for any string stochastic language p defined by a probabilistic automaton [START_REF] Denis | Learning Rational Stochastic Languages[END_REF] or a stochastic context-free grammar [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], there exist some constants U > 0 and 0 < ρ < 1 such that the sum of the probabilities of strings of length at least k is bounded: With a confidence greater than 1δ/2(n T + 2), we have:

|x| < log(U 2(n T + 2)/δ) log(1/ρ) , by fixing δ/2(n T + 2) = Uρ k .
Applying this result to every string of the sample, we get that with probability at least 1δ/2, any sample of n T + 2 elements has only strings of size at most log(U 2(n T +2)/δ) log(1/ρ) .

Then, by using Theorem 5.17 with a confidence δ/2 and replacing W by log(2(n T +2)U/δ) log(1/ρ)

, we obtain the following bound.

Theorem 5.18. Let T be a sample of n T randomly selected training examples drawn from a stochastic language p and let C T be the edit costs learned by GESL HL with stability κ n T using n L = αn T landmark points. Then there exists constants U > 0 and 0 < ρ < 1 such that with probability at least 1δ, we have:

R (C T ) ≤ R T (C T ) + 2 κ n T + 2κ + 2 + α α 2 log(2(n T + 2)U/δ) βB γ log(1/ρ) + 3 B γ ln(4/δ) 2n T with κ = 2(2+α) log 2 (2(n T +2)U/δ) αβ log 2 (1/ρ)
and B γ = max(η γ ,log(1/2)). costs (5 runs for each size n T ), as well as 600 words to train the separator α and 400 words to test its performance. evidence that our method scales well with the size of the alphabet, as suggested by the generalization bound derived in Section 5.5.2. On the other hand, (iii) seems to suffer from the large number of costs to estimate: it needs a lot more examples to outperform Levenshtein (about 200) and convergence seems to be only reached at 1,000.

Pairing strategy and influence of α

In the previous experiment, the pairing strategy and the value of α was set by crossvalidation. In this section, we compare the two pairing strategies (random pairing and Levenshtein pairing) presented in Section 5.4.3 as well as the influence of α (the proportion of landmarks associated with each training example). Figure 5.9 shows the accuracy and sparsity results obtained for n T = 1, 500 with respect to α and the pairing strategies. 15 The accuracy for d lev and p e is carried over from Figure 5.8 for comparison

Learning the separator

We now assess the performance of the three edit similarities with respect to the number of examples n used to learn the separator α. For K C and p e , we use the edit cost matrix that performed best in Section 5.6.1.1. Taking our set of 2,000 words, we keep aside 400 examples to test the models and build bootstrap samples from the remaining 1,600 words to learn α. Figure 5.10 shows the accuracy and sparsity results of each method with respect to n, averaged over 5 runs. Again, K C outperforms d lev and p e for every size n (the difference is statistically significant with a p-value < 0.01 using a Student's t-test) while always leading to (up to 5 times) sparser models. Moreover, the size of the models induced by K C stabilizes for n ≥ 400 while the accuracy still increases. This is not the case for the models induced by d lev and p e , whose size keeps growing. To sum up, the best similarity learned by GESL HL outperforms the best similarity learned with the method of [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF], which had been proven to outperform other state-of-the-art methods.

Reasonable points analysis

Finally, one may wonder what kind of words are selected as reasonable points in the models. The intuition is that they should be some sort of "discriminative prototypes" the classifier is based on. To investigate this, using K C and a training set of 1,200 examples, we learned a classifier α with a high value of λ to enforce a very sparse model, thus making the analysis easier. The set of 11 reasonable points automatically selected during the learning process is shown in Table 5.1. Our interpretation of why these particular words were chosen is that this small set actually carries a lot of discriminative patterns.

Table 5.2 shows some of these patterns (extracted by hand from the reasonable points of Table 5.1) along with their number of occurrences in each class over the entire dataset.

For example, words ending with ly correspond to English words, while those ending with que characterize French words. Note that Table 5.1 also reflects the fact that English words are shorter on average (6.99) than French words (8.26) in the dataset, but the English (resp. French) reasonable points are significantly shorter (resp. longer) than the average (mean of 5.00 and 10.83 resp.), which allows better discrimination. Note that we generated other sets of reasonable points from several training sets and observed the same patterns.

Handwritten Digits

We use the same NIST Special Database 3 as earlier in this manuscript. We have seen that classifying digits using a Freeman code representation and edit similarities Table 5.2: Some discriminative patterns extracted from the reasonable points of Table 5.1 (^: start of word, $: end of word, ?: 0 or 1 occurrence of preceding letter).

yields close-to-perfect accuracy, even in the multi-class setting. In order to make the comparison between the edit similarities (i-iii) easier, we evaluate them on the binary task of discriminating between even and odd digits. This task is harder due to extreme within-class variability: each class is in fact a "meta-class" containing instances of 5 basic classes of digits. Therefore, every example is highly dissimilar to about 80% of the examples of its own class (e.g., 1's are dissimilar to 5's and 0's are dissimilar to 4's, although they belong to the same class).

Convergence rate

Once again, we assess the convergence of the cost learning methods (i and iii). We keep aside 2,000 words as a validation set to tune the parameters (using 5-fold cross-validation and selecting the value offering the best classification accuracy) as well as 2,000 words for testing the models. We build bootstrap samples T from the remaining 6,000 words to learn the edit costs (5 runs for each size n T ), as well as 400 words to train the separator α. are paired with landmarks of the same class but yet very different (for instance, a 1 paired with a 5, or a 0 paired with a 4), and trying to "move them closer" is a fruitless effort.

On the other hand, we have seen earlier that the Levenshtein distance is an appropriate measure to discriminate between handwritten digits. Therefore, when using Levenshtein pairing with α ≤ 0.2, the problematic situation explained above rarely occurs. When α > 0.2, since each meta-class is made out of 5 basic classes in even proportions, more

and more examples are paired with "wrong" landmarks and the performance drops dramatically.

This result yields a valuable conclusion: similarity learning should not always focus on optimizing over all possible pairs (although it is often the case in the literature), since it may lead to poor classification performance. In some situations, such as the presence of high within-class variability, it may be a better strategy to improve the similarity according to a few carefully selected pairs.

Reasonable points analysis

To provide an insight into the sort of digits that are selected as reasonable points, we follow the same procedure as in Section 5.6.1.4 using a training set of 2,000 examples. We end up with a set of 13 reasonable points. The corresponding digit contours are drawn in Figure 5.13, allowing a graphical interpretation of why these particular examples were chosen. Note that this set is representative of a general tendency: we experimented with several training sets and obtained similar results. The most striking thing about this set is that 7's are over-represented (4 out of the 6 reasonable points of the odd class). This is explained by the fact that 7's (i) account for 1's and 9's (their contour is very similar), which also gives a reason for the absence of 1's and 9's in the set, and (ii) are not similar to any even digits. The same kind of reasoning applies to 6's (the lower part of 6's is shared by 0's and 8's, but not by any odd number) and 3's (lower part is the same as 5's). We can also notice the presence of 4's: they have a contour mostly made of straight lines, which is unique in the even class. There is also a 2 whose contour is somewhat similar to a 1. Lastly, another explanation for having several occurrences of the same digit may be to account for variations of size (the two 4's), shape or orientations (the three 6's).

Conclusion

In this chapter, we made use of the theory of ( , γ, τ )-good similarity functions in the context of edit similarities. We first conducted a preliminary experimental study confirming that this framework is well-suited to edit similarities, leading to classification performance competitive with standard SVM but with a number of additional advantages, among which the absence of PSD constraint and the sparsity of the models.

We then went a step further and proposed a novel approach to the problem of learning edit similarities from data, called GESL, driven by the notion of ( , γ, τ )-goodness. As Table 5.3: Summary of the main features of GESL ("Opt.", "Global sol.", "Neg. pairs", "Gen." and "CO" respectively stand for "Optimization", "Global solution", "Negative pairs", "Generalization guarantees" and "Convex optimization").

opposed to most state-of-the-art approaches, GESL is not based on a costly iterative procedure but on solving an efficient convex program, and can accommodate both positive and negative training pairs. Furthermore, it is also a promising way to learn tree edit similarities, even though we did not perform any series of experiments in this case.

We provided a theoretical analysis of GESL, which holds for a large class of loss functions. A generalization bound in O( 1/n T ) was derived using the notion of uniform stability. This bound is (i) related to the goodness of the resulting similarity, which gives guarantees that the similarity will induce accurate classifiers for the task at hand, and

(ii) independent from the size of the alphabet, making GESL suitable for problems involving large vocabularies. We conducted experiments on two string datasets that show that GESL has fast convergence and that the learned similarities perform very well in practice, inducing more accurate and sparser models than other (standard or learned) edit similarities. We also studied two pairing strategies and observed that Levenshtein pairing is more stable to high within-class variability, and that considering all possible pairs is not always a good approach. Table 5.3 summarizes the main features of GESL using the same format as in the survey of Chapter 3 (Table 3.2).

An extension of this work would be to consider sparsity-inducing regularizers on the edit cost matrix. For instance, using an L 1 regularization would lead to more interpretable matrices: an edit cost set to zero during learning would suggest that the corresponding edit operation is not relevant to the task, which can be a valuable information in many real-world applications. This would however prevent the derivation of generalization guarantees using uniform stability, but the theoretical framework presented later in this thesis (Chapter 7) could be used instead.

Another interesting perspective is to assess the relevance of similarities learned with GESL when used in k-Nearest Neighbors classifiers. Indeed, when using Levenshtein pairing, GESL's objective is somewhat related to the k-NN prediction rule and to the objective of the metric learning method LMNN (Weinberger & Saul, 2009). This intuition is confirmed by preliminary results using a 1-NN classifier (see Figure 5.14 and optimize a pair-based objective that is a loose bound on the empirical ( , γ, τ )-goodness (see Equation 5.3) due to the form of the edit similarity, we will see in the next chapter that using a simple bilinear similarity allows us to optimize the actual ( , γ, τ )-goodness, relying on global constraints instead of pairs.

PART III

Contributions in Metric Learning from Feature Vectors CHAPTER 6

Learning Good Bilinear Similarities from Global Constraints Chapter abstract In this chapter, we build upon GESL (proposed in Chapter 5) to learn good similarities between feature vectors. We focus on the bilinear similarity, which is not PSD-constrained. Thanks to this simple form of similarity, we are able to efficiently optimize its empirical ( , γ, τ )-goodness (instead of an upper bound as done in Chapter 5 for structured data) in a nonlinear feature space by formulating the approach as a convex minimization problem. Unlike other metric learning methods, this results in the similarity being optimized with respect to global constraints instead of local pairs or triplets. Then, relying on uniform stability arguments similar to those used in the previous chapter, we derive generalization guarantees directly in terms of the goodness in generalization of the learned similarity. As compared to GESL, our method minimizes a tighter bound on the true risk of the linear classifier built from the similarity. Experiments performed on various datasets confirm the effectiveness of our approach compared to state-of-the-art methods and provide evidence that (i) it is fast, (ii) robust to overfitting and (iii) produces very sparse classifiers.

The material of this chapter is based on the following international publication: Aurélien Bellet, Amaury Habrard, and Marc Sebban. Similarity Learning for Provably Accurate Sparse Linear Classification. In Proceedings of the 29th International Conference on Machine Learning (ICML), 2012c.

Introduction

In the previous chapter, we used a relaxation of the notion of ( , γ, τ )-goodness to propose a pair-based edit similarity learning method and showed that, in this context, we could establish the consistency of the learned metric with respect to unseen pairs of examples, and a relation to the goodness in generalization of the metric. In this chapter, we focus on metric learning from feature vectors and aim at optimizing the exact criterion of ( , γ, τ )-goodness. Thanks to the simple form of the bilinear similarity, we are able to do this in an efficient way, leading to a similarity optimized with respect to global constraints (rather than local pairs) and used to build a global linear classifier.

Our approach, called SLLC (Similarity Learning for Linear Classification), has several advantages: (i) it is tailored to linear classifiers, (ii) theoretically well-founded, (iii) does not require positive semi-definiteness, and (iv) is in a sense less restrictive than pair or triplet-based settings. We formulate the problem of learning a good similarity function as a convex minimization problem that can be efficiently solved in a batch or online way. Furthermore, by using the Kernel Principal Component Analysis (KPCA) trick [START_REF] Chatpatanasiri | A new kernelization framework for Mahalanobis distance learning algorithms[END_REF], we are able to kernelize our algorithm and thereby learn more powerful similarity functions and classifiers in the nonlinear feature space induced by a kernel. From the theoretical standpoint, we show that our approach has uniform stability, which leads to generalization guarantees directly in terms of the ( , γ, τ )-goodness in generalization of the learned similarity. In other words, our approach minimizes an upper bound on the true risk of the linear classifier built from the similarity, and this bound is tighter than that obtained for GESL in Chapter 5. Lastly, we provide an experimental study on seven datasets of various domains and compare SLLC with two widely-used metric learning approaches: LMNN (Weinberger & Saul, 2009) and ITML [START_REF] Davis | Information-theoretic metric learning[END_REF]. This study demonstrates the practical effectiveness of our method and shows that it is fast, robust to overfitting and induces very sparse classifiers, making it suitable for dealing with high-dimensional data.

The rest of the chapter is organized as follows. Section 6.2 presents our approach, SLLC, and the KPCA trick used to kernelize it. In Section 6.3, we provide a theoretical analysis of SLLC, leading to the derivation of generalization guarantees both in terms of the consistency of the learned similarity and the error of the linear classifier. Finally, Section 6.4 features an experimental study on various datasets and we conclude in Section 6.5.

Learning ( , γ, τ )-Good Bilinear Similarity Functions

We consider the bilinear similarity K M defined by

K M (x, x ) = x T Mx .
In order to satisfy K M ∈ [-1, 1], we assume that inputs are normalized such that ||x|| 2 ≤ 1, and we require ||M|| F ≤ 1.

Similarity Learning Formulation

Our goal is to directly optimize the empirical ( , γ, τ )-goodness of K M . To this end, we are given a training sample of n T labeled points T = {z i = (x i , y i )} n T i=1 and a sample of n R labeled reasonable points R = {z k = (x k , y k )} n R k=1 . In practice, R is a subset of T with n R = τ n T (τ ∈ ]0, 1]). In the lack of background knowledge, it can be drawn randomly or according to some criterion, e.g., diversity [START_REF] Kar | Similarity-based Learning via Data Driven Embeddings[END_REF].

Based on the definition of ( , γ, τ )-goodness in hinge loss (Definition 5.3), given R and a margin γ, we want to optimize the amount of margin violation on the training sample (the empirical goodness). Thus, let

(M, z i , R) = [1 -y i 1 γn R n R k=1 y k K M (x i , x k )] +
denote the empirical goodness of K M with respect to a single training point z i . The empirical goodness over the sample T is denoted by

T = 1 n T n T i=1 (M, z i , R).
We want to learn the matrix M that minimizes T . This can be done by solving the following regularized problem, referred to as SLLC (Similarity Learning for Linear Classification):

min M∈R d×d T + β M 2 F (6.1)
where β is a regularization parameter.

Note that SLLC can be cast as a convex quadratic program (QP) by rewriting the sum of n T hinge losses in the objective function as n T margin constraints and introducing slack variables ξ ∈ R n T + in the objective:

min M∈R d×d ,ξ∈R n T + 1 n T n T i=1 ξ i + β M 2 F s.t. 1 -y i 1 γn R n R k=1 y k K M (x i , x k ) ≤ ξ i , 1 ≤ i ≤ n T . (6.2)
SLLC is radically different from classic metric and similarity learning algorithms presented in Chapter 3, which are based on pair or triplet-based constraints. It learns a global similarity rather than a local one, since R is the same for each training example.

Moreover, the constraints are easier to satisfy since they are defined over an average of similarity scores to the points in R instead of over a single pair or triplet. This means that one can fulfill a constraint without satisfying the margin for each point in R individually (unlike what we did with GESL in Chapter 5). SLLC also has a number of desirable properties:

1. No costly semi-definite programming is required, as opposed to many Mahalanobis distance learning methods. In its convex QP form (6.2), SLLC can be solved efficiently using standard convex minimization solvers. Moreover, it has only one constraint per training example (instead of one for each pair or triplet), i.e., a total of only n T constraints and n T + d 2 variables. In its unconstrained form (6.1), it is convex but not differentiable everywhere due to the hinge function in the loss.

It can be solved in a stochastic or online setting using composite objective mirror descent [START_REF] Duchi | Composite Objective Mirror Descent[END_REF] or dual averaging methods [START_REF] Xiao | Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization[END_REF] and thereby scales to very large problems.

2. The size of R does not affect the complexity of Problem 6.2, since each constraint is simply a linear combination of entries of M.

3. If x i is sparse, then the associated constraint is sparse as well: some variables of the problem (corresponding to entries of M) have a zero coefficient in the constraint.

This makes the problem easier to solve when data have a sparse representation.

We now explain how SLLC can be kernelized to deal with nonlinear problems.

Kernelization of SLLC

The framework presented in the previous section is theoretically well-founded with respect to Balcan et al.'s theory and has some generalization guarantees, as we will see in the next section. Moreover, it has the advantage of being very simple: we learn a global linear similarity and use it to build a global linear classifier. In order to learn more powerful similarities (and therefore classifiers), we propose to kernelize the approach by learning them in the nonlinear feature space induced by a kernel.

As discussed in Section 3.2.3, kernelizing a particular metric learning algorithm is difficult in general and may lead to intractable problems unless dimensionality reduction is applied. For these reasons, we instead use the KPCA trick, recently proposed by [START_REF] Chatpatanasiri | A new kernelization framework for Mahalanobis distance learning algorithms[END_REF]. It provides a straightforward way to kernelize a metric learning algorithm while performing dimensionality reduction at no additional cost, and is based on Kernel Principal Component Analysis [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF], a nonlinear extension of PCA [START_REF] Pearson | On Lines and Planes of Closest Fit to Points in Space[END_REF].

PCA provides a way of representing the data by a small number k of linearly uncorrelated variables (called the principal components) that account for most of the variance in the data. Assuming zero-centered data, let C denote the data covariance matrix:

C = 1 n n i=1 x i x j T .
The new representation

x i ∈ R k (k ≤ d) of a data point x i ∈ R d is given by x i = x i T V,
where V is a matrix whose columns are the top k eigenvectors of C.

The basic idea of KPCA is to use a kernel function to implicitly perform PCA in the (possibly infinite-dimensional) nonlinear feature space induced by the kernel, in the spirit of what is done in SVM. Let K be a kernel such that K(x, y) = φ(x), φ(x ) . The data covariance matrix in the new feature space is given by

C = 1 n n i=1 φ(x i )φ(x j ) T .
It can be shown that the projection of a point φ(x i ) onto the j th principal component only depends on inner products and therefore can be computed implicitly through the kernel function. The solution can actually be obtained through an eigendecomposition of the kernel matrix K whose entries are defined as K i,j = K(x i , x j ).

Therefore, KPCA allows us to project the data into a new feature space of dimension k ≤ n. The (unchanged) metric learning algorithm can then be used to learn a metric in that nonlinear space. [START_REF] Chatpatanasiri | A new kernelization framework for Mahalanobis distance learning algorithms[END_REF] showed that the KPCA trick is theoretically sound for unconstrained metric learning algorithms (they proved representer theorems), which includes SLLC. Throughout the rest of this chapter, we will only consider the kernelized version of SLLC.

Generally speaking, kernelizing a metric learning algorithm may cause or increase overfitting, especially when data are scarce and/or high-dimensional. However, since our framework is entirely linear and global, we expect our method to be quite robust to this undesirable effect. This will be doubly confirmed in the rest of this chapter: experimentally in Section 6.4, but also theoretically with the derivation in the following section of generalization guarantees independent from the size of the projection space.

Theoretical Analysis

In this section, we present a theoretical analysis of our approach. Our main result is the derivation of a generalization bound (Theorem 6.4) guaranteeing the consistency of SLLC and thus the ( , γ, τ )-goodness in generalization for the considered task.

Notations

For convenience, given a bilinear model K M , we denote by M R both the similarity defined by the matrix M and its associated set of reasonable points R (when it is clear from the context we may omit the subscript R). Given a similarity M R , (M R , z, R)

is the loss function over one example z. The empirical risk of M R over the sample T is thus given by

R T (M R ) = T (M R ) = 1 n T n T i=1 (M R , z i , R)
and corresponds to the empirical goodness, while the true risk is given by

R (M R ) = (M R ) = E z∼P [ (M R , z, R)]
and corresponds to the "true" goodness (or goodness in generalization). In the following, we will rather use T (M R ) and (M R ) to denote respectively the empirical and true risks to highlight the equivalence between risk and ( , γ, τ )-goodness in SLLC. When it is clear from the context, we may simply use T and .

The similarity is optimized according to a fixed set R of reasonable points coming from the training sample. Therefore, these reasonable points may not follow the distribution from which the training sample has been generated. Once again, the framework of uniform stability allows us to cope with this situation. Note that the empirical and true risks are defined with respect to a single example and not with respect to pairs. Therefore, we use the standard uniform stability setting (presented in Section 2.2.2) instead of the adaptation to the pair-based case introduced by [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF] and used in Chapter 5.

Generalization Bound

In our case, to prove the uniform stability property we need to show that

∀T , ∀i, sup z | (M, z, R) -(M i , z, R i )| ≤ κ n T , (6.3)
where M is learned from T and R ⊆ T , M i is the matrix learned from T i and R i ⊆ T i is the set of reasonable points associated to T i . T i is obtained from T by replacing the i th example z i ∈ T by another example z i independent from T and drawn from P . Note that R and R i are of equal size and can differ in at most one example, depending on whether z i or z i belong to their corresponding set of reasonable points. For the sake of simplicity, we assume that is bounded by 1.1 To show (6.3), we need the following results.

Lemma 6.1. For any labeled examples z = (x, y), z = (x , y ) and any models M R , M R , the following properties hold:

P1: |K M (x, x )| ≤ 1, P2: |K M (x, x ) -K M (x, x )| ≤ M -M F ,
P3: 1-admissibility property of :

| (M, z, R) -(M , z, R )| ≤ 1| n R k=1 y k K M (x, x k ) γn R - n R j=1 y k K M (x, x k ) γn R |.
Proof. P 1 comes from |K M (x, x )| ≤ x 2 M F x 2 , the normalization on examples ( x 2 ≤ 1) and the requirement on matrices ( M F ≤ 1).

For P 2, we observe that

|K M (x, x ) -K M (x, x )| = |K M-M (x, x )|,
and we use the normalization x 2 ≤ 1.

P 3 follows directly from |y| = 1 and the 1-lipschitz property of the hinge loss:

|[U ] + -[V ] + | ≤ |U -V |.
Let F T = T (M) + β M 2 F be the objective function of SLLC with respect to a sample T and a set of reasonable points R ⊆ T . The following lemma bounds the deviation between M and M i . Lemma 6.2. For any models M and M i that are minimizers of F T and F T i respectively, we have:

M -M i F ≤ 1 βn T γ .
Proof. We follow closely the proof of Lemma 20 of [START_REF] Bousquet | Stability and Generalization[END_REF] and omit some details for the sake of readability (similar ideas are used in the first part of the more detailed proof of Lemma 5.8). Let ∆M = M i -M, 0 ≤ t ≤ 1 and

M 1 = M 2 F -M + t∆M 2 F + M i 2 F -M i -t∆M 2 F M 2 = 1 βn T ( T (M R ) -T ((M + t∆M) R ) + T i ((M + t∆M) R ) -T i (M R )).
Using the fact that F T and F T i are convex functions, that M and M i are their respective minimizers and property P3, we have M 1 ≤ M 2 . Fixing t = 1/2, we obtain M 1 = M -M i 2 F , and using property P 3 and the normalization x 2 ≤ 1, we get:

M 2 ≤ 1 βn T γ ( 1 2 ∆M F + - 1 2 ∆M F ) = M -M i F βn T γ .
This leads to the inequality

M -M i 2 F ≤ M-M i F βn T γ
from which Lemma 6.2 is directly derived.

We now have all the material needed to prove the stability property of our algorithm. and z i = (x i , y i ) ∼ P :

| (M, z, R) -(M i , z, R i )| ≤ 1 γn R n R k=1 y k K M (x, x k ) - 1 γn R i n R i k=1 y k K M i (x, x k ) = 1 γn R     n R k=1,k =i y k (K M (x, x k ) -K M i (x, x k ))   + y i K M (x, x i ) -y i K M i (x, x i )   ≤ 1 γn R     n R k=1,k =i (|y k | M -M i F )   + |y i K M i (x, x i )| + |y i K M (x, x i )|   ≤ 1 γn R n R -1 βn T γ + 2 ≤ 1 γn R n R βn T γ + 2 .
The first inequality follows from P 3. The second comes from the fact that R and R i differ in at most one element, corresponding to the example z i in R and the example z i replacing z i in R i . The last inequalities are obtained by the use of the triangle inequality, P 1, P 2, Lemma 6.2, and the fact that the labels belong to {-1, 1}. Since n R = τ n T ,

we get | (M, z, R) -(M i , z, R i )| ≤ 1 γn T ( 1 βγ + 2 τ ).
Applying Theorem 5.9 with Lemma 6.2 gives our main result.

Theorem 6.4. Let γ > 0, δ > 0 and n T > 1. With probability at least 1δ, for any model M R learned with SLLC, we have:

≤ T + 1 n T τ + 2βγ τ βγ 2 + 2(τ + 2βγ) τ βγ 2 + 1 ln 1/δ 2n T .
Theorem 6.4 highlights three important properties of SLLC. First, it has a reasonable O(1/ √ n T ) convergence rate. Second, it is independent from the dimensionality of the data. This is due to the fact that M F is bounded by a constant. Third, Theorem 6.4

bounds the true goodness of the learned similarity function. By minimizing T with SLLC, we minimize and thus an upper bound on the true risk of the resulting linear classifier, as stated by Theorem 5.4. Note that this is a much tighter bound on the goodness than that derived in Chapter 5, where only a loose bound on the empirical goodness was optimized.

Experimental Validation

We propose a comparative study of our method against two widely-used Mahalanobis

Setup

We compare the following methods: (i) the cosine similarity K I in KPCA space, as a baseline, (ii) SLLC, (iii) LMNN in the original space, (iv) LMNN in KPCA space, (v)

ITML in the original space, and (vi) ITML in KPCA space. 5 All attributes are scaled to [-1/d; 1/d] to ensure x 2 ≤ 1.

To generate a new feature space using KPCA, we use the Gaussian kernel with parameter σ equal to the mean of all pairwise training data Euclidean distances (a standard heuristic, used for instance by [START_REF] Kar | Similarity-based Learning via Data Driven Embeddings[END_REF]. Ideally, we would like to project the data to the feature space of maximum size (equal to the number of training examples), but to keep the computations tractable we only retain three times the number of features of the original data (four times for the low-dimensional datasets), as shown in We tune the following parameters by cross-validation: β, γ ∈ {10 -7 , . . . , 10 -2 } for SLLC, λ IT ML ∈ {10 -4 , . . . , 10 4 } for ITML, and λ ∈ {10 -3 , . . . , 10 2 } for learning the linear classifiers, choosing the value offering the best accuracy. We choose R to be the entire training set, i.e., τ = 1 (interestingly, cross-validation of τ did not improve the results significantly). We take k = 3 and µ = 0.5 for LMNN, as suggested by [START_REF] Kilian | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF]. For ITML, we generate n T random constraints for a fair comparison with SLLC.

Results

Linear classification We first report the results obtained in linear classification using Balcan's learning rule (Table 6.2). SLLC achieves the highest accuracy on 5 out of metric learning for linear classification is of interest) while prediction is many orders of magnitude faster due to the sparsity of the linear separators. Also note that an accurate similarity for k-NN classification can achieve poor results in linear classification (LMNN on Cod-RNA), and vice versa (SLLC on Svmguide1).

Robustness to overfitting SLLC's good performance on small datasets can be credited to its robustness to overfitting. Indeed, LMNN and ITML are optimized with respect to local constraints, which tend to get easier to satisfy simultaneously as dimensionality grows. On the other hand, SLLC is optimized with respect to global constraints and can thus be seen as more robust. This is confirmed by Figure 6.1, which shows the accuracy of SLLC, LMNN and ITML on the Ionosphere dataset with respect to the number of dimensions retained in KPCA. As expected, LMNN and ITML, tend to overfit as the dimensionality grows while SLLC suffers from very limited overfitting.

Visualization of the projection space Recall that in Balcan's learning rule, the similarity is used to build a similarity map: data are projected into a new feature space where each coordinate corresponds to the similarity score to a training example, and a linear classifier is learned in that space. Figure 6.2 and Figure 6.3 show a lowdimensional embedding of the feature space induced by each similarity for the Rings and Svmguide1 datasets respectively. On both datasets, the space induced by SLLC is the most appropriate to linear classification: the data is well-separated even in this 2D representation of the space. On the Rings dataset, the data is actually perfectly separated in 1D, which explains why we achieve perfect classification accuracy relying on 1 training instance only. This highlights the fact that SLLC optimizes a criterion which is designed for linear classification, and its potential for dimensionality reduction.

Conversely, the feature spaces induced by K I , LMNN and ITML do not offer such quality of linear separability -for instance and unsurprisingly, LMNN tends to induce spaces that are better suited to nearest neighbor classification.

Runtime comparison

In this series of experiments, SLLC was solved in its QP form using the standard convex minimization solver Mosek7 while LMNN and ITML have their own specific and sophisticated solver. Despite this fact, SLLC is several orders of magnitude faster than LMNN (see Table 6.4) because its number of constraints is much smaller. However, it remains slower than ITML.

Conclusion

In this chapter, we presented SLLC, a novel approach to bilinear similarity learning that makes use of both the theory of ( , γ, τ )-goodness and the KPCA trick. It is formulated as a convex minimization problem that can be solved efficiently using standard techniques. We derived a generalization bound based on the notion of uniform stability that is independent from the size of the input space, and thus from the number of dimensions selected by KPCA. It guarantees the true goodness of the learned similarity, and therefore our method can be seen as minimizing an upper bound on the true risk of the linear classifier built from the learned similarity. We experimentally demonstrated the effectiveness of SLLC and also showed that the learned similarities induce extremely sparse classifiers. Combined with the independence from dimensionality and the robustness to overfitting, it makes the approach very efficient and suitable for high-dimensional data. SLLC ✗ Table 6.5: Summary of the main features of SLLC ("Reg." and "Gen." respectively stand for "Regularized" and "Generalization guarantees").

Table 6.5 summarizes the main features of SLLC using the same format as in the survey of Chapter 3 (Table 3.1).

It would be interesting to investigate the performance of SLLC when solved in its unconstrained form, either in a stochastic or online way. This would dramatically improve its runtime on large-scale problems and hopefully not significantly reduce the classification performance.

As shown in Table 6.5, SLLC is not a low-rank approach, since Frobenius norm regularization does not favor low-rank matrices. Another promising perspective would be to study the influence of other regularizers on A, in particular the trace norm or the L 2,1 norm that tend to induce such matrices. Recent advances in stochastic and online optimization of problems regularized with these norms [START_REF] Duchi | Composite Objective Mirror Descent[END_REF][START_REF] Xiao | Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization[END_REF][START_REF] Yang | Online Learning for Group Lasso[END_REF]) could be used to derive an efficient algorithm. The use of such norms would add sparsity at the metric level in addition to the sparsity already obtained at the classifier level.

However, recall that the generalization of such formulations cannot be studied using stability-based arguments, since sparse algorithms are known not to be stable. On the other hand, algorithmic robustness can deal with such algorithms more easily. In the next chapter, we propose an adaptation of robustness to the metric learning setting.

CHAPTER 7

Robustness and Generalization for Metric Learning

Chapter abstract Throughout this thesis, we have argued that little work has been done about the generalization ability of metric learning algorithms. We made use in Chapter 5 and Chapter 6 of uniform stability arguments to derive generalization guarantees for our metric learning methods. Unfortunately, these arguments are somewhat limited to the use of Frobenius regularizarion and thus cannot be applied to many existing metric learning algorithms, in particular those using a sparse or low-rank regularizer on the metric. In this chapter, we address this theoretical issue by proposing an adaptation of the notion of algorithmic robustness (previously introduced by Xu and Mannor) to the classic metric learning setting, where training data consist of pairs or triplets. We show that if a metric learning algorithm is robust in our sense, then it has generalization guarantees. We further show that a weak notion of robustness is a necessary and sufficient condition for an algorithm to generalize, justifying that it is fundamental to metric learning. Lastly, we illustrate how our framework can be used to derive generalization bounds for a large class of metric learning algorithms, some of which could not be studied using previous approaches.

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

Aurélien Bellet and Amaury Habrard. Robustness and Generalization for Metric Learning. Technical report, University of Saint-Etienne, September 2012. arXiv:1209.1086.

Introduction

Most of the research effort in metric learning has gone into formulating the problem as tractable optimization procedures, but very little has been done on the generalization ability of learned metrics on unseen data, due to the fact that the training pairs/triplets are not i.i.d. As we have seen in Section 3.2.1.4, online metric learning methods (e.g., [START_REF] Shalev-Shwartz | Online and batch learning of pseudo-metrics[END_REF][START_REF] Jain | Online Metric Learning and Fast Similarity Search[END_REF][START_REF] Chechik | An Online Algorithm for Large Scale Image Similarity Learning[END_REF] offer some guarantees, but only in the form of regret bounds assuming that the algorithm is provided with i.i.d.

pairs/triplets, and say nothing about generalization to unseen data. Conversion of regret bounds into batch generalization bounds is possible (see for instance [START_REF] Cesa-Bianchi | On the Generalization Ability of On-Line Learning Algorithms[END_REF][START_REF] Mount | Bioinformatics: Sequence and Genome Analysis[END_REF]) but as a consequence these bounds also require the i.i.d. assumption.

Putting aside our contributions in Chapter 5 and Chapter 6, the question of the generalization ability of batch metric learning has only been addressed in two recent papers, described in Section 3.2.1.5. For the sake of readability, we recall here their main features. The approach of [START_REF] Bian | Learning a Distance Metric by Empirical Loss Minimization[END_REF]2012) uses a statistical analysis to give generalization guarantees for loss minimization methods, but their results rely on some hypotheses on the distribution of the examples and do not take into account any regularization on the metric. The most general contribution was proposed by [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF] who adapted the framework of uniform stability to regularized metric learning.

However, their approach is based on Frobenius norm regularization and cannot be applied to many types of regularization, in particular sparsity-inducing norms (Xu et al., 2012a).

In Moreover, following the work of [START_REF] Xu | Robustness and Generalization[END_REF], 2012), we establish that a weaker notion robustness is actually necessary and sufficient for metric learning algorithms to generalize, highlighting that robustness is a fundamental property. Lastly, we illustrate the applicability of our framework by deriving generalization bounds for a larger class of problems than [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF], using very few algorithm-specific arguments. In particular, it can accommodate a vast choice of regularizers and unlike the approach of [START_REF] Bian | Learning a Distance Metric by Empirical Loss Minimization[END_REF]2012), requires no assumption on the distribution of the examples.

The rest of the chapter is organized as follows. Our notion of algorithmic robustness for metric learning is presented in Section 7.2. The necessity and sufficiency of weak robustness is shown in Section 7.3. Section 7.4 is devoted to the application of the proposed framework: we show that a large class of metric learning algorithms are robust.

Finally, we conclude in Section 7.5.

Robustness and Generalization for Metric Learning

After introducing some notations and assumptions, we present our definition of robustness for metric learning and show that if a metric learning algorithm is robust, then it has generalization guarantees.

Preliminaries

We assume that the instance space X is a compact convex metric space with respect to a norm • such that X ⊂ R d , thus there exists a constant R such that ∀x ∈ X ,

x ≤ R. A metric is a function f : X × X → R. Recall that we use the generic term metric to refer to a distance or a (dis)similarity function.

Given a training sample T = {z i = (x i , y i )} n i=1 drawn i.i.d. from an unknown joint distribution P over the space Z = X × Y, we denote by P T the set of all possible pairs built from T :

P T = {(z 1 , z 1 ), • • • , (z 1 , z n ), • • • , (z n , z n )}.
We generally assume that a metric learning algorithm A takes as input a finite set of pairs from (Z × Z) n and outputs a metric. We denote by A P the metric learned by an algorithm A from a sample P of pairs. With any pair of labeled examples (z, z ) and any metric f , we associate a loss function (f, z, z ) that depends on the examples and their labels. This loss is assumed to be nonnegative and uniformly bounded by a constant B.

We define the true risk of f by

R (f ) = E z,z ∼P [ (f, z, z )].
We denote the empirical risk of f over the sample of pairs P by

R P (f ) = 1 |P| (z i ,z j )∈P (f, z i , z j ).
On a few occasions, we discuss the extension of our framework to triplet-based metric learning, where an algorithm A takes as input a finite set of triplets from (Z × Z × Z) n .

Instead of considering all pairs P T built from T , we consider the sample of admissible triplets R T built from T such that for any (z 1 , z 2 , z 3 ) ∈ R T , z 1 and z 2 share the same label while z 3 does not, with the interpretation that z 1 must be more similar to z 2 than to z 3 . In this context, the loss function is defined with respect to triplets of examples and the true risk of a metric f is given by

R (f ) = E z,z ,z ∼P y=y =y [ (f, z, z , z )]
and the empirical risk of f over the sample of admissible triplets R by

R R (f ) = 1 |R| (z i ,z j ,z k )∈R (f, z i , z j , z k ).
Proof. Let N i be the set of index of points of T that fall into the C i . (|N 1 |, . . . , |N K |) is an i.i.d. random variable with parameters n and (µ(C 1 ), . . . , µ(C K )). We have:

|R (A PT ) -R PT (A PT )| = K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j )µ(C i )µ(C j ) - 1 n 2 n i=1 n j=1 (A PT , z i , z j ) (a) ≤ K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j )µ(C i )µ(C j )- K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j )µ(C i ) |N j | n + K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j )µ(C i ) |N j | n - 1 n 2 n i=1 n j=1 (A PT , z i , z j ) (b) ≤ K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j )µ(C i )(µ(C j ) - |N j | n ) + K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j )µ(C i ) |N j | n - K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j ) |N i | n |N j | n + K i=1 K j=1 E z,z ∼P ( (A PT , z, z )|z ∈ C i , z ∈ C j ) |N i | n |N j | n - 1 n 2 n i=1 n j=1 (A PT , z i , z j ) (c) ≤ B   K j=1 µ(C j ) - |N j | n + K i=1 µ(C i ) - |N i | n   + 1 n 2 K i=1 K j=1 zo∈Ni z l ∈Nj max z∈Ci max z ∈Cj | (A PT , z, z ) -(A PT , z o , z l )| (d) ≤ (P T ) + 2B K i=1 |N i | n -µ(C i ) (e) ≤ (P T ) + 2B 2K ln 2 + 2 ln(1/δ) n .
Inequalities The previous bound depends on K which is given by the cover chosen for Z. If for any K, the associated (•) is constant with respect to T (i.e., K (T ) = K ), we can prove a bound holding uniformly for all K:

|R (A P T ) -R P T (A P T )| ≤ inf K≥1 K + 2B 2K ln 2 + 2 ln(1/δ) n .
The bound also gives an insight into what should be the objective of a robust metric learning algorithm: according to a partition of the labeled input space, given two regions, minimize the maximum loss over pairs of examples belonging to each region.

For triplet-based metric learning algorithms, by following the definition of robustness given by (7.1) and adapting straightforwardly the losses to triplets such that they output zero for non-admissible triplets, Theorem 7.3 can be easily extended to obtain the following generalization bound:

|R (A R T ) -R R T (A R T )| ≤ (R T ) + 3B 2K ln 2 + 2 ln(1/δ) n . (7.3)

Pseudo-robustness

The previous study requires the robustness property to be satisfied for every training pair. We show, with the following definition, that it is possible to relax the robustness to be fulfilled for only a subpart of the training sample and yet be able to derive generalization guarantees.

∀(z 1 , z 2 ) ∈ PT , ∀z, z ∈ Z, ∀i, j ∈ [K]: if z 1 , z ∈ C i and z 2 , z ∈ C j then | (A P T , z 1 , z 2 ) -l(A P T , z, z )| ≤ (P T ). (7.4)
We can easily observe that (K, (•))-robust is equivalent to (K, (•), n 2 ) pseudo-robust.

The following theorem illustrates the generalization guarantees associated to the pseudorobustness property.

Theorem 7.5. If a learning algorithm A is (K, (•), pn (•)) pseudo-robust and the training pairs P T come from a sample generated by n i.i.d. draws from P , then for any δ > 0, with probability at least 1δ we have:

|R (A P T ) -R P T (A P T )| ≤ pn (P T ) n 2 (P T ) + B n 2 -pn (P T ) n 2 + 2 2K ln 2 + 2 ln(1/δ) n .
Proof. The proof is similar to that of Theorem 7.3 and is given in Appendix B.2.1.

The notion of pseudo-robustness characterizes a situation that often occurs in metric learning: it is difficult to satisfy pair-based constraints for all possible pairs. Theorem 7.5

shows that it is sufficient to satisfy a property of robustness over only a subset of the pairs to have generalization guarantees. Moreover, it also gives an insight into the behavior of metric learning approaches aiming at learning a distance to be plugged in a k-NN classifier such as LMNN [START_REF] Kilian | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF]. These methods do not optimize the distance according to all possible pairs, but only according to the nearest neighbors of the same class and some pairs of different class. According to the previous theorem, this strategy is well-founded provided that the robustness property is fulfilled for some of the pairs used to optimize the metric. Finally, note that this notion of pseudo-robustness can be also easily adapted to triplet based metric learning.

Necessity of Robustness

We prove here that a notion of weak robustness is actually necessary and sufficient to generalize in a metric learning setup. This result is based on an asymptotic analysis following the work of Xu & Mannor (2012). We consider pairs of instances coming from an increasing sample of training instances T = (z 1 , z 2 , . . . ) and from a sample of test instances U = (z 1 , z 2 , . . . ) such that both samples are assumed to be drawn i. We first define a notion of generalizability for metric learning.

Definition 7.6 (Generalizability for metric learning). Given a training pair set P T * built from a sequence of examples T * , a metric learning method A generalizes with

respect to P T * if lim n R (A P T * (n) ) -R P T * (n) (A P T * (n) ) = 0.
A learning method A generalizes with probability 1 if it generalizes with respect to the pairs P T of almost all samples T i.i.d. from P .

Note that this notion of generalizability implies convergence in mean. We then introduce the notion of weak robustness for metric learning.

R P T (n) (A P T * (n) ) -R P T * (n) A P T * (n) ) = 0.
A For the necessity, we need the following lemma which is a direct adaptation of Lemma 2 from Xu & Mannor (2012). We provide the proof in Appendix B.2.3 for the sake of completeness.

Lemma 7.9. Given T * , if a learning method is not weakly robust with respect to P T * , there exist * , δ * > 0 such that the following holds for infinitely many n:

P r(|R P U (n) (A P T * (n) ) -R P T * (n) (A P T * (n) )| ≥ * ) ≥ δ * . (7.5)
Now, recall that is nonnegative and uniformly bounded by B, thus by the McDiarmid inequality (Theorem 5.10) we have that for any , δ > 0 there exists an index n * such that for any n > n * , with probability at least 1δ, we have:

1 n 2 (z i ,z j )∈P U (n) (A P T * (n) , z i , z j ) -R (A P T * (n) ) ≤ .
This implies the convergence

R P U (n) (A P T * (n) ) -R (A P T * (n) ) P r → 0,
and thus from a given index:

|R P U (n) (A P T * (n) ) -R (A P T * (n) )| ≤ * 2 . (7.6)
Theorem 7.11. Fix γ > 0 and a metric ρ of Z. Suppose that ∀z 1 , z 2 , z, z :

(z 1 , z 2 ) ∈ P T , ρ(z 1 , z) ≤ γ, ρ(z 2 , z ) ≤ γ, A satisfies | (A P T , z 1 , z 2 ) -(A P T , z, z )| ≤ (P T ),
and N (γ/2, Z, ρ) < ∞. Then A is (N (γ/2, Z, ρ), (P T ))-robust.

Proof. By definition of covering number, we can partition X in N (γ/2, X , ρ) subsets such that each subset has a diameter less or equal to γ. Furthermore, since Y is a finite set, we can partition

Z into |Y|N (γ/2, X , ρ) subsets {C i } such that z 1 , z ∈ C i ⇒ ρ(z 1 , z) ≤ γ. Therefore, | (A pT , z 1 , z 2 ) -(A pT , z, z )| ≤ (P T ), ∀z 1 , z 2 , z, z : (z 1 , z 2 ) ∈ P T , ρ(z 1 , z) ≤ γ, ρ(z 2 , z ) ≤ γ implies z 1 , z 2 ∈ P T , z 1 , z ∈ C i , z 2 , z ∈ C j ⇒ | (A P T , z 1 , z 2 ) -(A P T , z, z )| ≤ (P T ),
which establishes the theorem.

We now prove the robustness of (7.7) when M is the Frobenius norm, which corresponds to the formulation (3.6) addressed by [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF].

Example 7.1 (Frobenius norm). Algorithm (7.7) with M = M F is (|Y|N (γ/2, X , • 2 ), 8URγg 0 C )-robust.
Proof. Let M * be the solution given training data P T . Due to optimality of M * , we have We can partition Z as |Y|N (γ/2, X , • 2 ) sets, such that if z and z belong to the same set, then y = y and x-x 2 ≤ γ. Now, for z 1 , z 2 , z 1 , z 2 ∈ Z, if y 1 = y 1 , x 1 -x 1 2 ≤ γ, y 2 = y 2 and x 2x 2 2 ≤ γ, then:

|g(y 1 y 2 [1 -d 2 M * (x 1 , x 2 )]) -g(y 1 y 2 [1 -d 2 M * (x 1 , x 2 )])| ≤ U |(x 1 -x 2 ) T M * (x 1 -x 2 ) -(x 1 -x 2 ) T M * (x 1 -x 2 )| = U |(x 1 -x 2 ) T M * (x 1 -x 2 ) -(x 1 -x 2 ) T M * (x 1 -x 2 ) + (x 1 -x 2 ) T M * (x 1 -x 2 )| -(x 1 -x 2 ) T M * (x 1 -x 2 )| = U |(x 1 -x 2 ) T M * (x 1 -x 2 -(x 1 + x 2 )) + (x 1 -x 2 -(x 1 + x 2 )) T M * (x 1 + x 2 )| ≤ U (|(x 1 -x 2 ) T M * (x 1 -x 1 )| + |(x 1 -x 2 ) T M * (x 2 -x 2 )| + |(x 1 -x 1 ) T M * (x 1 + x 2 )| + |(x 2 -x 2 ) T M * (x 1 + x 2 )|) ≤ U ( x 1 -x 2 2 M * F x 1 -x 1 2 + x 1 -x 2 2 M * F x 2 -x 2 2 + x 1 -x 1 2 M * F x 1 -x 2 2 + x 2 -x 2 2 M * F x 1 -x 2 2 ) ≤ 8URγg 0 C .
Hence, the example holds by Theorem 7.11.

The generalization bound for Example 7.1 derived by [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF] using uniform stability arguments has the same order of convergence. However, their framework cannot be used to establish generalization bounds for recent sparse metric learning approaches [START_REF] Rosales | Learning Sparse Metrics via Linear Programming[END_REF][START_REF] Qi | An Efficient Sparse Metric Learning in High-Dimensional Space via l1-Penalized Log-Determinant Regularization[END_REF][START_REF] Ying | Sparse Metric Learning via Smooth Optimization[END_REF][START_REF] Kunapuli | Mirror Descent for Metric Learning: A Unified Approach[END_REF] because sparse algorithms are known not to be stable (Xu et al., 2012a). The key advantage of robustness over stability is that it can accommodate arbitrary p-norms (or even any regularizer which is bounded below by some p-norm), thanks to the equivalence of norms. To illustrate this, we show the robustness when M is the L 1 norm (used in [START_REF] Rosales | Learning Sparse Metrics via Linear Programming[END_REF][START_REF] Qi | An Efficient Sparse Metric Learning in High-Dimensional Space via l1-Penalized Log-Determinant Regularization[END_REF] which promotes sparsity at the component level, the L 2,1 norm (used in [START_REF] Ying | Sparse Metric Learning via Smooth Optimization[END_REF] which induces group sparsity at the column/row level, and the trace norm (used in [START_REF] Kunapuli | Mirror Descent for Metric Learning: A Unified Approach[END_REF] which induces low-rank matrices.

Example 7.2 (L 1 norm). Algorithm (7.7) with M = M 1 is (|Y|N (γ, X , • 1 ), Proof. See Appendix B.2.5.

We have seen that kernelization is a convenient way to learn a nonlinear metric. In the following example, we show robustness for a kernelized formulation. )-robust.

Proof. See Appendix B.2.6.

Using triplet-based robustness (7.1), we can for instance show the robustness of two popular triplet-based metric learning approaches [START_REF] Schultz | Learning a Distance Metric from Relative Comparisons[END_REF][START_REF] Ying | Sparse Metric Learning via Smooth Optimization[END_REF] for which no generalization guarantees were known (to the best of our knowledge).

Recall that these algorithms have the following form: Furthermore, we can easily prove similar results for other forms of metrics using the same technique. For instance, when the function is the bilinear similarity x i T Mx j where M is not constrained to be PSD (see for instance [START_REF] Chechik | An Online Algorithm for Large Scale Image Similarity Learning[END_REF][START_REF] Qamar | Similarity Learning for Nearest Neighbor Classification[END_REF]Bellet et al., 2012c), we can improve the robustness to 2URγg 0 /C.

min M 0 1 |R T | (z i ,z j ,z k )∈R T [1 -d 2 M (x i , x k ) + d 2 M (x i , x j )] + + C M ,

Conclusion

In this chapter, we proposed a new theoretical framework for establishing generalization bounds for metric learning algorithms, based on the notion of algorithmic robustness originally introduced by [START_REF] Xu | Robustness and Generalization[END_REF], 2012). We showed that robustness can be adapted to pair and triplet-based metric learning and can be used to derive generalization guarantees without assuming that the pairs or triplets are drawn i.i.d. Furthermore, we showed that a weak notion of robustness characterizes the generalizability of metric learning algorithms, justifying that robustness is fundamental for such algorithms. The proposed framework is used to derive generalization bounds for a large class of metric learning algorithms with different regularizations, such as sparsity-inducing norms, making the analysis more powerful and general than the (few) existing frameworks.

Moreover, almost no algorithm-specific argument is needed to derive these bounds.

It is worth noting that our adaptation of robustness to metric learning is relatively straightforward: in most cases, the proof techniques of [START_REF] Xu | Robustness and Generalization[END_REF], 2012) could be reused with only slight modification. Nevertheless, this adaptation is promising since it leads to generalization bounds for many metric learning methods that could not be studied through the prism of previous frameworks. Note that it could be used to make the link between the generalization ability of metric learning methods and their ( , γ, τ )goodness, in a similar fashion to what we did in Chapter 5 with uniform stability. An obvious drawback of the proposed framework is that the resulting bounds are loose and often similar from one method to another due to the use of covering numbers and equivalence of norms.

A natural perspective is to consider different, harder settings. Besides extending our framework to more general loss functions (for example those that use both pairs and triplets, such as Weinberger [START_REF] Kilian | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF] and regularizers (e.g., the LogDet divergence used in [START_REF] Davis | Information-theoretic metric learning[END_REF][START_REF] Jain | Online Metric Learning and Fast Similarity Search[END_REF], studying other paradigms for metric learning (such as unsupervised, semi-supervised or domain adaptation methods) would be of great interest.

Lastly, another interesting avenue is to design a metric learning algorithm that would maximize the robustness of the resulting metric.

CHAPTER 8

Conclusion & Perspectives

In this thesis, we have addressed some important limitations of existing supervised metric learning methods by proposing new approaches for feature vectors and structured data. We paid particular attention to the desirable properties and justifications of each contribution presented in this document. We studied both theoretical frameworks and algorithmic issues, but also the applicability of the different approaches. Overall, it constitutes a wide range of research.

Our first contribution (which was actually not a metric learning algorithm) was to propose a new string kernel built from learned edit similarities. This kernel combines powerful learned edit similarities with the classification performance of support vector machines: it is more adaptable than classic string kernels (such as the spectrum, subsequence or mismatch kernels) while being guaranteed to be PSD, unlike other kernels based on the edit distance. We provided a tractable way to compute it, although the proposed solution can remain computationally expensive.

In order to avoid the cost of transforming learned edit similarities into kernels, we then proposed to use them directly to build a linear classifier, following the framework of learning with ( , γ, τ )-good similarity functions [START_REF] Balcan | On a Theory of Learning with Similarity Functions[END_REF]Balcan et al., 2008a,b). We observed that this yields competitive results in practice. We went one step further by introducing our main second contribution with GESL, a string and tree edit similarity learning method driven by a relaxation of ( , γ, τ )-goodness. The problem is formulated as an efficient convex quadratic program and solved by convex optimization tools, thereby avoiding the use of expensive and locally optimal EM-based algorithms.

Unlike many other edit metric learning methods, we were able to use the information brought by both positive and negative pairs, and to derive generalization guarantees for the learned similarity using uniform stability arguments. These guarantees give an upper bound on the true risk of the classifier built from the learned similarity (although a rather loose one). Furthermore, experimental evaluation showed the accuracy of the method but also its ability to output sparse models, which is a valuable property from a practical point of view. Note that the source code for GESL is available and distributed under GNU/GPL 3 license.1

To provide a wider range of applicability, our third contribution was an extension of the ideas of GESL to metric learning from feature vectors. The proposed approach, called SLLC, takes advantage of the simple form of the bilinear similarity to efficiently optimize the actual ( , γ, τ )-goodness, instead of only a loose upper bound in GESL.

In this context, the similarity is not learned from local pairs or triplets but according to a global criterion. We also kernelized SLLC to be able to learn linear similarities in a nonlinear feature space induced by a kernel. Generalization guarantees based on uniform stability are established for SLLC and give a tighter bound on the true risk of the linear classifier. To the best of our knowledge, GESL and SLLC are the first metric learning methods for which the link between the quality of the learned metric and the error of the classifier using it is formally established.

Finally, purely on the theoretical side, our last contribution overcame the limitations of the previous frameworks studying the generalization of metric learning algorithms.

It is based on a relatively straightforward adaptation of algorithmic robustness [START_REF] Xu | Robustness and Generalization[END_REF], 2012) but provides an easy way to derive nontrivial results. We illustrated this by showing how it can be used to prove the robustness of a large class of metric learning algorithms, thereby establishing generalization guarantees for methods that could not be handled with previous arguments.

Staying in the scope of the proposed methods, the adaptation to other metrics or other regularizers are possible future directions. In particular, extending the methods to sparsity-inducing regularizers (in order to obtain more interpretable results as well as additional properties such as low-rank solutions and dimensionality reduction) can be done without giving up generalization guarantees, thanks to the theoretical contribution of Chapter 7. To improve the scalability of the approaches, an interesting avenue would be to develop online versions of the algorithms. Another promising idea for future work is to explore the field of information geometry, in particular to study the problem of metric learning in the context of Bregman divergences [START_REF] Bregman | The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming[END_REF]. Such divergences are known to generalize many metrics for vectors and matrices, and have interesting properties for solving tasks such as clustering (see e.g., [START_REF] Banerjee | Clustering with Bregman Divergences[END_REF][START_REF] Fischer | Quantization and clustering with Bregman divergences[END_REF]. To the best of our knowledge, learning Bregman divergences has only been addressed by [START_REF] Wu | Learning Bregman Distance Functions and Its Application for Semi-Supervised Clustering[END_REF][START_REF] Wu | Learning Bregman Distance Functions for Semi-Supervised Clustering[END_REF].

From a more high-level perspective, many questions remain open as to the theoretical understanding of metric learning. Some of our contributions make the link between the learned metric and its performance in classification, but our results are so far restricted to the context of linear classification, relying on ( , γ, τ )-goodness. A promising avenue would be to derive methods or analytical frameworks capable of making that link for other classifiers. In particular, since most learned metrics are used in k-NN, tying the generalization ability of the learned metric to the true risk of the k-NN classifier would constitute a beautiful result. One could also derive theoretically sound metric learning methods for other supervised learning tasks, such as regression or ranking, using the recently proposed generalization of the notion of similarity goodness to these settings [START_REF] Kar | Supervised Learning with Similarity Functions[END_REF].

Another interesting perspective would be to study the generalization ability of learned metrics in other settings, such as domain adaptation [START_REF] Mansour | Domain Adaptation: Learning Bounds and Algorithms[END_REF][START_REF] Ben-David | A theory of learning from different domains[END_REF]. Domain adaptation (DA) studies the generalization ability of a hypothesis learned from labeled source data and used to predict the labels of target data, where the distributions generating the source and target data are different. It was shown that successful adaptation is possible when the two distributions are not too different -a common example of such situation is covariate shift, where only the data distributions are different, while the conditional distribution of labels given a data point remains the same (see for instance Bickel et al., 2009, and references therein). Although a few DA metric learning methods already exist [START_REF] Cao | Distance Metric Learning under Covariate Shift[END_REF][START_REF] Geng | DAML: Domain Adaptation Metric Learning[END_REF], insights provided by DA generalization bounds [START_REF] Mansour | Domain Adaptation: Learning Bounds and Algorithms[END_REF][START_REF] Ben-David | A theory of learning from different domains[END_REF] could be used to derive theoretically well-founded approaches.

Finally, one could also focus on clustering, since metrics are essential to many clustering algorithms (such as the prominent K-Means). We identify two promising directions for future research. First, one could use the fact that algorithmic robustness is based on a partition of the input space. This geometric interpretation seems particularly relevant to clustering, and a metric learning algorithm that maximizes a notion of robustness could be appropriate to deal with clustering tasks. Another avenue could consist in formally determining which properties of a metric are important to induce quality clusterings.

The work of Balcan et al. (2008c) is a first attempt towards a better understanding of this question. Then, note that |φ(x 1 ) T M * (φ(x 1 )φ(x 1 ))| ≤ φ(x 1 ), φ(x 1 ) M * H φ(x 1 )φ(x 2 ), φ(x 1 )φ(x 2 )

≤ B γ g o C f H (γ).
Thus, by applying the same principle to all the terms in the right part of inequality (B.8), we obtain:

|g(y 1 y 2 [1 -d 2 M * (φ(x 1 ), φ(x 2 ))]) -g(y ij [1 -d 2 M * (φ(x 1 ), φ(x 2 ))])| ≤ 8UB γ f H (γ)g 0 C .
Yiming Abstract In recent years, the crucial importance of metrics in machine learning algorithms has led to an increasing interest in optimizing distance and similarity functions using knowledge from training data to make them suitable for the problem at hand. This area of research is known as metric learning. Existing methods typically aim at optimizing the parameters of a given metric with respect to some local constraints over the training sample. The learned metrics are generally used in nearest-neighbor and clustering algorithms. When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance, which is parameterized by a positive semi-definite matrix. Recent methods offer good scalability to large datasets. Less work has been devoted to metric learning from structured objects (such as strings or trees), because it often involves complex procedures. Most of the work has focused on optimizing a notion of edit distance, which measures (in terms of number of operations) the cost of turning an object into another. We identify two important limitations of current supervised metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not really been studied so far. Second, and perhaps more importantly, the question of the generalization ability of metric learning methods has been largely ignored. In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Unlike other string kernels, it is guaranteed to be valid and parameter-free. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of ( , γ, τ )-good similarity functions and formulated as a convex optimization problem. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend the same ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the ( , γ, τ )-goodness. The similarity is learned based on global constraints that are more appropriate to linear classification. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms. It is based on a simple adaptation of the notion of algorithmic robustness and allows the derivation of bounds for various loss functions and regularizers.

Résumé Ces dernières années, l'importance cruciale des métriques en apprentissage automatique a mené à un intérêt grandissant pour l'optimisation de distances et de similarités en utilisant l'information contenue dans des données d'apprentissage pour les rendre adaptées au problème traité. Ce domaine de recherche est souvent appelé apprentissage de métriques. En général, les méthodes existantes optimisent les paramètres d'une métrique devant respecter des contraintes locales sur les données d'apprentissage. Les métriques ainsi apprises sont généralement utilisées dans des algorithms de plus proches voisins ou de clustering. Concernant les données numériques, beaucoup de travaux ont porté sur l'apprentissage de distance de Mahalanobis, paramétrisée par une matrice positive semi-définie. Les méthodes récentes sont capables de traiter des jeux de données de grande taille. Moins de travaux ont été dédiés à l'apprentissage de métriques pour les données structurées (comme les chaînes ou les arbres), car cela implique souvent des procédures plus complexes. La plupart des travaux portent sur l'optimisation d'une notion de distance d'édition, qui mesure (en termes de nombre d'opérations) le coût de transformer un objet en un autre. Au regard de l'état de l'art, nous avons identifié deux limites importantes des approches actuelles. Premièrement, elles permettent d'améliorer la performance d'algorithmes locaux comme les k plus proches voisins, mais l'apprentissage de métriques pour des algorithmes globaux (comme les classifieurs linéaires) n'a pour l'instant pas été beaucoup étudié. Le deuxième point, sans doute le plus important, est que la question de la capacité de généralisation des méthodes d'apprentissage de métriques a été largement ignorée. Dans cette thèse, nous proposons des contributions théoriques et algorithmiques qui répondent à ces limites. Notre première contribution est la construction d'un nouveau noyau construit à partir de probabilités d'édition apprises. A l'inverse d'autres noyaux entre chaînes, sa validité est garantie et il ne comporte aucun paramètre. Notre deuxième contribution est une nouvelle approche d'apprentissage de similarités d'édition pour les chaînes et les arbres inspirée par la théorie des ( , γ, τ )-bonnes fonctions de similarité et formulée comme un problème d'optimisation convexe. En utilisant la notion de stabilité uniforme, nous établissons des garanties théoriques pour la similarité apprise qui donne une borne sur l'erreur en généralisation d'un classifieur linéaire construit à partir de cette similarité. Dans notre troisième contribution, nous étendons ces principes à l'apprentissage de métriques pour les données numériques en proposant une méthode d'apprentissage de similarité bilinéaire qui optimise efficacement l'( , γ, τ )-goodness. La similarité est apprise sous contraintes globales, plus appropriées à la classification linéaire. Nous dérivons des garanties théoriques pour notre approche, qui donnent de meilleurs bornes en généralisation pour le classifieur que dans le cas des données structurées. Notre dernière contribution est un cadre théorique permettant d'établir des bornes en généralisation pour de nombreuses méthodes existantes d'apprentissage de métriques. Ce cadre est basé sur la notion de robustesse algorithmique et permet la dérivation de bornes pour des fonctions de perte et des régulariseurs variés.

Figure

  Figure1.1: The two-fold problem of generalization in metric learning. We are interested in the generalization ability of the learned metric itself: can we say anything about its consistency on unseen data drawn from the same distribution? Furthermore, we are interested in the generalization ability of the learned model using that metric: can we relate its performance on unseen data to the quality of the learned metric?

Figure 2 . 3 :

 23 Figure 2.3: Plot of several loss functions for binary classification.

Figure 2 . 4 :

 24 Figure 2.4: Minkowski distances: unit circles for various values of p.

Figure 2 . 5 :

 25 Figure 2.5: Strategies to delete a node within a tree: (a) original tree, (b) after deletion of the <UL> node as defined by Zhang & Shasha, and (c) after deletion of the <UL> node as defined by Selkow.

Figure 3 . 1 :

 31 Figure 3.1: Intuition behind metric learning. Before learning (left pane), red and blue points are not well-separated. After learning (right pane), red and blues points are separated by a certain margin.

  Jain et al.) LEGO, developed by Jain et al. (2008), is an improved version of POLA based on LogDet divergence regularization. It features tighter regret bounds, more efficient updates and better practical performance. ITML (David et al.) ITML, presented in Section 3.2.1.3, also has an online version with bounded regret. At each step, the algorithm minimizes a tradeoff between LogDet regularization with respect to the previous matrix and a square loss. The resulting distance generally performs slightly worse than the batch version but the algorithm can be faster.MDML(Kunapuli & Shavlik) The work ofKunapuli & Shavlik (

  Bernard et al. Extending the work of[START_REF] Ristad | Learning String-Edit Distance[END_REF] and[START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF] on string edit similarity learning,[START_REF] Bernard | Learning Stochastic Tree Edit Distance[END_REF][START_REF] Bernard | Learning probabilistic models of tree edit distance[END_REF] propose both a generative and a discriminative model for learning tree edit costs. They rely on the tree edit distance by Selkow (1977) -which is cheaper to compute than that of Zhang & Shasha (1989) -and adapt the updates of EM to this case. An application to handwritten digit recognition is proposed, where digits are represented by trees of Freeman codes.Boyer et al. The work of[START_REF] Boyer | Learning Metrics between Tree Structured Data: Application to Image Recognition[END_REF] tackles the more complex variant of the tree edit distance(Zhang & Shasha, 1989), which allows the insertion and deletion of single nodes instead of entire subtrees only. Parameter estimation in the generative model is also based on EM, and the usefulness of the approach is illustrated on an image recognition task.

  the transition weight function, τ : I → R the initial weight function, and ρ : F → R the final weight function.

Figure 4

 4 Figure 4.1:A memoryless cPFT that can be used to compute the edit conditional probability of any pair of strings. Edit probabilities assigned to each transition are not shown here for the sake of readability.

  Figure 4.2 shows the cPFT T |a and T |ab constructed from the memoryless transducer T given in Figure 4.1. Roughly speaking, T |a and T |ab model the output languages that can be generated through edit operations from x and x respectively. Therefore, from these state machines, we can generate output strings and compute the conditional edit probabilities p e (s|x) and

Figure 4 . 2 :

 42 Figure 4.2:On the left: a cPFT T |a that models the output distribution conditionally to an input string x = a. For the sake of readability, state 0 stands for ($, 0), and state 1 for (a, 0). On the right: a cPFT T |ab that models the output distribution given x = ab. Again, 0 stands for ($, 0), 1 for (a, 0), and 2 for (ab, 0).

Figure 4 . 3 :

 43 Figure 4.3: The cPFT T |a and T |ab of Figure 4.2 represented in the form of automata.

Figure 4 . 4 :

 44 Figure 4.4: Automaton modeling the intersection of the automata of Figure 4.3.

Figure 4 .

 4 Figure 4.4 shows the intersection automaton of the two automata from Figure 4.3. Let us now describe how this intersection automaton can be used to compute the infinite sum over Σ * .

  The weighted automaton T |x describing p e (s|x) has t • (|x| + 1) states, and T |x describing p e (s|x ) has t • (|x | + 1) states (see Figure 4.3 for an example). Thus, the matrix (I -M) has dimension t 2 •(|x|+1)•(|x |+1). The computational cost of each element of this matrix linearly depends on the alphabet size |Σ|. Therefore, the complexity of computing the entire matrix is O(t 4 •|x| 2 •|x | 2 •|Σ|). Since M is triangular by construction of A|x, x (the probability of going back to a previous state is zero), the matrix inversion (I -M) -1

  our kernel K e (x, x ) by computing a finite sum over the training strings s ∈ T . Therefore, we get Ke (x, x ) = s∈T p e (s|x) • p e (s|x ).

Figure 4

 4 Figure 4.5: A handwritten digit and its string representation.

  Figure 4.5 shows an example of this encoding procedure.

  Figure 4.6: Comparison of our edit kernel with edit distances on a handwritten digit recognition task.

  conditional edit probabilities p e (x |x) used in our edit kernel are the same as those used in d e (x, x ). Results are shown in Figure 4.6 with respect to an increasing number of training instances (from 100 to 8, 000).

Figure 4 . 8 :

 48 Figure 4.8: Influence of the parameter t of K L&J (1,000 training strings).

  The first condition is essentially requiring that a 1proportion of examples x are on average more similar to reasonable examples of the same class than to reasonable examples of the opposite class by a margin γ and the second condition that at least a τ proportion of the examples are reasonable. 1 Figure 5.1 illustrates the definition on a toy example. Note that other definitions are possible, like those proposed by Wang et al.

Figure 5 . 1 :

 51 Figure 5.1: A graphical insight into Definition 5.1. Let us consider 8 points as shown above (blue represents the positive class, red the negative class) and use the similarity functionK(x, x ) = 1xx 2 .We picked 3 reasonable points (A, B and E, circled in black), thus we can set τ = 3/8. Similarity scores to the reasonable points as well as the margin achieved by each point (as given by Equation5.1) are shown in the array. There exists an infinite number of valid instantiations of and γ since there is a trade-off between the margin γ and proportion of margin violations . For example, K is (0, 0.006, 3/8)-good because all points ( = 0) are on average more similar to reasonable examples of the same class than to reasonable examples of the other class by a margin γ = 0.006. One can also say that K is (2/8, 0.01, 3/8)-good ( = 2/8 because examples C and D violate the margin γ = 0.01).

Figure 5 . 3 :

 53 Figure 5.3: Estimation of as a function of γ for dlev and pe on two handwritten digits binary classification tasks.

  Figure 5.3(b)

Figure 5 . 4 :

 54 Figure 5.4: Classification accuracy and sparsity results for methods (i-vi) over a range of training set sizes (Digit dataset).

Figure 5 . 5 :

 55 Figure 5.5: Classification accuracy and sparsity results with respect to the value of λ (Digit dataset).

Figure 5 . 6 :

 56 Figure 5.6: Classification accuracy and sparsity results with respect to the value of t in log-scale (Digit dataset).

Figure 5 . 7 :

 57 Figure 5.7: Word dataset: classification accuracy and sparsity results for methods (i-vi) over a range of training set sizes.

  models based on p e perform better than those based on d lev . Models learned with Balcan clearly outperform k-NN, while SVM models are the most accurate. Sparsity results are shown in Figure 5.7(b). The gap in sparsity between models learned with Balcan and SVM models is even greater on this dataset: the number of support vectors grows almost linearly with the number of training examples. This is consistent with the theoretical rate established by Steinwart (2003).

  of the Levenshtein distance to pair examples is consistent with our choice to define e C according to the Levenshtein script. 2. Random pairing: we pair each z ∈ T with a number n T of randomly chosen examples of the same class and n T randomly chosen examples of the opposite class.

Theorem 5. 9 (

 9 Stability of GESL L ). Let n T and n L be respectively the number of training examples and landmark points. Assuming that n L = αn T , α ∈ ]0, 1], and that the loss function used in GESL L is k-lipschitz, then GESL L has a uniform stability in κ n T , where κ = 2(2+α)k 2 βα .

  10 and to bound E T [D T ] and |D T -D T i,z |, which is shown by the following lemmas. Lemma 5.11. For any learning method of estimation error D T and satisfying a uniform stability in κ n T , we have E T [D T ] ≤ 2κ n T . Proof. See Appendix B.1.2. Lemma 5.12. For any edit cost matrix learned by GESL L using n T training examples and n L landmarks, and any loss function satisfying (σ, m)-admissibility, we have the following bound:

  Lemma 5.15. Let (C T , B 1 , B 2 ) an optimal solution learned by GESL HL from a training sample T , and letB γ = max(η γ , -log(1/2)). Then C T F ≤ Bγ β .Proof. See Appendix B.1.5. Lemma 5.16. For any optimal solution (C T , B 1 , B 2 ), HL is (σ, m)-admissible with with B γ = max(η γ ,log(1/2)).

  we have that HL is (σ, m)admissible.

  account this result in our framework, we need an estimation of the length of the examples used to derive the generalization bound, that is, a sample of n T examples with two additional examples z and z . For any sample of n T + 2 strings identically and independently drawn from p, we can bound the length of any string x of this sample.

Figure 5 . 8 :

 58 Figure 5.8: Learning the edit costs: accuracy and sparsity results (Word dataset).

Figure 5 .

 5 Figure 5.8 shows the accuracy and sparsity results of each method with respect to n T , averaged over 5 runs. We see that K C leads to more accurate classifiers than d lev and p e for n T > 20. The difference is statistically significant: the Student's t-test yields a p-value < 0.01. At the same time, K C requires 3 to 4 times less reasonable points, thus increasing classification speed by just as much. The exact figures are as follows: d lev achieves 69.55% accuracy with a model size of 197, p e achieves at best 74.80% with a model size of 155, and K C achieves at best 78.65% with a model size of only 45. This clearly indicates that GESL HL leads to a better similarity than (ii) and (iii). Moreover, the convergence rate of GESL HL is very fast, considering that (26 + 1) 2 = 729 costs must be learned: it needs very few examples (about 20) to outperform the Levenshtein distance, and about 200 examples to reach convergence. This provides experimental

Figure 5 . 9 :

 59 Figure 5.9: Pairing strategies: accuracy and sparsity results w.r.t. α (Word dataset).

Figure 5 . 10 :

 510 Figure 5.10: Learning the separator: accuracy and sparsity results (Word dataset).

Figure 5 .Figure 5 . 11 :

 5511 Figure5.11 shows the accuracy and sparsity results of each method with respect to n T , averaged over 5 runs. First of all, we notice that the Levenshtein distance d lev performs nicely on this task (95.19% with a model size of 70) and that p e is never able to match d lev 's accuracy level (94.94% at best with a model size of 78). In our opinion, this poor performance comes from the fact that p e does not take advantage of negative pairs. In a context of extreme within-class variability, moving closer examples of the same class without making sure that examples of different class are kept far from each others does not yield an appropriate similarity. On the other hand, our method shows the same general behavior on this task as on the previous one. Indeed, convergence is fast despite the richness of the two classes (only 100 examples to match Levenshtein's accuracy and about 1,000 to reach convergence). Moreover, K C achieves significantly better performance (95.63% at best with a model size of 57) than both d lev (p-value < 0.05 for n T ≥ 250 using a Student's t-test) and p e (p-value < 0.01 for n T > 20).

Figure 5 . 12 :

 512 Figure 5.12: Pairing strategies: accuracy and sparsity results with respect to α (Digit dataset).

Figure 5 . 13 :

 513 Figure 5.13: Example of a set of 13 reasonable points (Digit dataset).

  Lemma 6.3. Let n T and n R be the number of training examples and reasonable points respectively, n R = τ n T with τ ∈ ]0, 1]. SLLC has a uniform stability in κ n T with κ = 1 γ ( 1 βγ + 2 τ ) = τ +2βγ τ βγ 2 , where β is the regularization parameter and γ the margin. Proof. For any sample T of size n T , any 1 ≤ i ≤ n T , any labeled examples z = (x, y)

7

  datasets and competitive performance on the remaining 2. At the same time, on all datasets, SLLC leads to extremely sparse classifiers. The sparsity of the classifier corresponds to the number of training examples that are involved in classifying a new example. Therefore, SLLC leads to much simpler and yet often more accurate classifiers than those built from other similarities. Furthermore, sparsity allows faster predictions, especially when data are plentiful and/or high-dimensional (e.g., Cod-RNA or Splice). Often enough, the learned linear classifier has sparsity 1, which means that classifying a new example boils down to computing its similarity score to a single training example and compare the value with a threshold. Note that we tried large values of λ to obtain sparser classifiers from K I , LMNN and ITML, but this yielded dramatic drops in accuracy. The extreme sparsity brought by SLLC comes from the fact that the constraints are based on an average of similarity scores over the same set of points for all training examples. This brings to the fore the relevance of optimizing the similarity with respect to global constraints. Nearest neighbor classification Since LMNN and ITML are designed for k-NN use, we also give the results obtained in 3-NN classification (

Figure 6 . 1 :

 61 Figure 6.1: Accuracy of the methods with respect to the dimensionality of the KPCA space on Ionosphere.

  a) and (b) are due to the triangle inequality, (c) uses the fact that is bounded by B, that K i=1 µ(C i ) = 1 by definition of a multinomial random variable and that K j=1 |N j | n = 1 by definition of the N j . Lastly, (d) comes from the definition of robustness (Definition 7.1) and (e) from the application of Proposition 7.2.

Definition 7. 4 .

 4 An algorithm A is (K, (•), pn (•)) pseudo-robust for K ∈ N, (•) : (Z × Z) n → R and pn (•) : (Z × Z) n → {1, . . . , n 2 }, if Z can be partitioned into K disjoints sets, denoted by {C i } K i=1 , such that for all T ∈ Z n i.i.d. from P , there exists a subset of training pairs samples PT ⊆ P T , with | PT | = pn (P T ), such that the following holds:

  i.d. from some distribution P . We use T (n) and U (n) to denote the first n examples of T and U respectively, while T * denotes a fixed sequence of training examples.

Definition 7. 7 (

 7 Weak robustness for metric learning). Given a set of training pairs P T * built from a sequence of examples T * , a metric learning method A is weakly robust with respect to P T * if there exists a sequence of {D n ⊆ Z n } such that P r(U (n) ∈ D n ) → 1 and lim n max T (n)∈Dn

  ,z j )∈P T g(yiyj[1d 2 M * (x i , x j )]) + C M ,z j )∈P T g(yiyj[1d 2 0 (x i , x j )]) + C 0 F = g0and thus M * F ≤ g 0 /C.

  3 (L 2,1 norm and trace norm). Algorithm (7.7) with M = M 2,1 orM = M * is (|Y|N (γ, X , • 2 ), 8URγg 0 C )-robust.

  ,z j )∈P T g(y i y j [1d 2 M (φ(x i ), φ(x j ))]) + C M H ,(7.8) where φ(•) is a feature mapping to a kernel space H, • H the norm function of H and k(•, •) the kernel function. Consider a cover of X by • 2 (X being compact) and letf H (γ) = max a,b∈X , a-b 2 ≤γ K(a, a) + K(b, b) -2K(a, b) and B γ = max x∈X K(x, x).If the kernel function is continuous, B γ and f H are finite for any γ > 0 and thusAlgorithm (7.8) is (|Y|N (γ, X , • 2 ), 8UBγ √ f H g 0 C

where

  [START_REF] Schultz | Learning a Distance Metric from Relative Comparisons[END_REF] use M = M F and Ying et al. (2009) use M = M 1,2 . These methods are (N (γ, Z, • 2 ), 16URγg 0 C )-robust (by using the same proof technique as in Example 7.1 and Example 7.3). The additional factor 2 comes from the use of triplets instead of pairs.

  We have:|g(y 1 y 2 [1d 2 M * (φ(x 1 ), φ(x 2 ))])g(y 1 y 2 [1d 2 M * (φ(x 1 ), φ(x 2 ))])| ≤ U (|(φ(x 1 )φ(x 2 )) T M * (φ(x 1 )φ(x 1 ))| + |(φ(x 1 )φ(x 2 )) T M * (φ(x 2 )φ(x 2 ))| + |(φ(x 1 )φ(x 1 )) T M * (φ(x 1 ) + φ(x 2 ))| + |(φ(x 2 )φ(x 2 )) T M * (φ(x 1 ) + φ(x 2 ))|) ≤ U (|φ(x 1 ) T M * (φ(x 1 )φ(x 1 ))| + |φ(x 2 ) T M * (φ(x 1 )φ(x 1 ))| + (B.8) |φ(x 1 ) T M * (φ(x 2 )φ(x 2 ))| + |φ(x 2 ) T M * (φ(x 2 )φ(x 2 ))| + |(φ(x 1 )φ(x 1 )) T M * φ(x 1 )| + |(φ(x 1 )φ(x 1 )) T M * φ(x 2 )| + |(φ(x 2 )φ(x 2 )) T M * φ(x 1 )| + |(φ(x 2 )φ(x 2 )) T M * φ(x 2 )|).

  .1.

		Chapter 1. Introduction
	Notation	Description
	R	Set of real numbers
	R+	Set of nonnegative real numbers
	R d	Set of d-dimensional real-valued vectors
	R c×d	Set of c × d real-valued matrices
	N	Set of natural numbers, i.e., {0, 1, . . . }
	S d +	Cone of symmetric PSD d × d real-valued matrices
	[k]	T h e s e t {1, 2, . . . , k}
	S	An arbitrary set
	|S|	Number of elements in S
	S m	A set of m elements from S
	X	Input space
	Y	Output space
	z = (x, y) ∈ X × Y	An arbitrary labeled instance
	x	An arbitrary vector
	xj, xi,j	The j th component of x and x i
	•, •	Inner product between vectors
	[•]+	Hinge function
	M	An arbitrary matrix
	I	The identity matrix
	Mi,j	Entry at row i and column j of matrix M
	•	An arbitrary norm
	• p	Lp norm
	x	An arbitrary string
	|x|	Length of string x
	x

i , x i,j j th symbol of x and x i x ∼ P x is drawn i.i.d. from probability distribution P Pr

[•] P r o b a b i l i t y o f e v e n t E[•]

Expectation of random variable Table 1.1: Summary of notation.

  In Structural Risk Minimization (SRM), we use an infinite sequence of hypothesis classes H 1 ⊂ H 2 ⊂ . . . of increasing size and select the hypothesis that minimizes a penalized version of the empirical risk that favors "simple"

	Name	Formula	Pros	Cons
	L0 norm x 0	Number of nonzero components	SP	NCO, NSM
	L1 norm x 1	|xi|	CO, SP	NSM
	(Squared) L2 norm x 2 2	x 2 i	CO, SM
	L2,1 norm x 2,1	Sum of L2 norms of grouped variables CO, GSP NSM

classes:

h T = arg min h∈Hc,c∈N R T (h) + pen(H c ).

Table 2 .

 2 1: Common regularizers on vectors. CO/NCO stand for convex/nonconvex, SM/NSM for smooth/nonsmooth and SP/GSP for sparsity/group sparsity.

	Name	Formula	Pros	Cons
	L0 norm M 0	Number of nonzero components	SP	NCO, NSM
	L1 norm M 1	|Mi,j|	CO, SP	NSM
	(Squared) Frobenius norm M 2 F	M 2 i,j	CO, SM
	L2,1 norm M 2,1	Sum of L2 norms of rows/columns CO, GSP NSM
	Trace (nuclear) norm M *	Sum of singular values	CO, LO	NSM

Table 2 .

 2 2: Common regularizers on matrices. Abbreviations are the same as in Table2.1, with LO standing for low-rank.

  have shown that a large class of regularized risk minimization algorithms satisfies this definition. The constant κ typically depends on the form of the loss function, the regularizer and the regularization parameter λ. Making a good use of McDiarmid's inequality, they show that when Definition 2.8 is fulfilled,

	the following bound in O(1/ √	n) holds.

  Table 2.3: Example of edit cost matrix C. Here, Σ = {a, b}.

	C $ a b
	$	0 2 10
	a	2 0 4
	b 10 4 0

Table 3

 3

	Method	Data	Model	Scripts	Opt. Global sol.	Neg. pairs	Gen.
	Ristad & Yianilos	Strings	Generative	All	EM	✗	✗	✗
	Bilenko & Mooney	Strings	Generative	All	EM	✗	✗	✗
	Takasu	Strings	Generative	All	EM	✗	✗	✗
	Oncina & Sebban	Strings	Discriminative	All	EM	✗	✗	✗
	McCallum et al.	Strings	Discriminative	All	EM	✗		✗
	Saigo et al.	Strings	-	All	GD	✗	✗	✗
	Bernard et al.	Trees	Both	All	EM	✗	✗	✗
	Boyer et al.	Trees	Generative	All	EM	✗	✗	✗
	Neuhaus & Bunke Graphs	Generative	All	EM	✗	✗	✗
	Dalvi et al.	Trees	Discriminative	All	EM	✗	✗	✗
	Emms	Trees	Discriminative	Optimal	EM	✗	✗	✗

.1: Summary of the main features of the reviewed approaches ("Reg." and "Gen." respectively stand for "Regularized" and "Generalization guarantees").

  global classifiers such as SVM and other linear separators, or if new metric learning algorithms should be designed for this global setting. Furthermore, building a PSD kernel from the learned metrics is often difficult, especially for structured data (e.g., string edit kernels).The contributions of this thesis address these limitations. Part II is devoted to metric learning from structured data and consists of two main contributions. In Chapter 4, we introduce a new string kernel built from learned edit probabilities. Unlike other string edit kernels, it is guaranteed to be PSD and parameter-free. In Chapter 5, we propose a novel string and tree edit similarity learning method based on numerical optimization, that can handle positive and negative pairs and is guaranteed to converge to the optimal solution. We are able to derive a generalization bound for our method, and this bound can be related to the generalization error of a linear classifier built from the learned

	CHAPTER 4
	A String Kernel Based on Learned Edit Similarities
	PART II
	Contributions in Metric
	Learning from Structured Data

The use of learned metrics is typically restricted to algorithms based on local neighborhoods, in particular k-NN classifiers. Since the learned metrics are typically optimized over local constraints, it seems unclear whether they can be successfully used in more similarity. Part III is devoted to metric learning from feature vectors and consists of two contributions. In Chapter 6, we propose a bilinear similarity learning method tailored to linear classification. The similarity is not optimized over local pair or triplet-based constraints: it directly minimizes a global quantity that upper bounds the true risk of the linear classifier built from the learned similarity. Lastly, in Chapter 7, we adapt the notion of algorithmic robustness (Section 2.2.3) to the metric learning setting, which allows us to derive generalization guarantees for a large class of metric learning problems with various loss functions and regularizers.

  4.3.2 Modeling p e (s|x) and p e (s|x ) with Probabilistic Automata

Since our edit kernel K e (x, x ) depends on two observable strings x and x , it is possible to represent the distributions p e (s|x) and p e (s|x ) in the form of probabilistic state machines, where only s is a hidden variable. Given a cPFT T modeling the edit probabilities and a string x, we can define a new cPFT driven by x, denoted by T |x, that models p e (s|x).

Table 4

 4

.1: Statistical comparison of our edit kernel with standard and learned edit distances (p-values of a Student's paired t-test). Boldface indicates that the difference is significant in favor of our kernel using a risk of 5%.

Table 4

 4

.1 contains the p-values obtained when comparing our kernel with d lev and d e .

  Table 4.2gives the p-values of the Student's t-test. Our edit kernel significantly outperforms all other string kernels except K L&J : both kernels perform comparably, and the difference for a given training sample size is not significant. However, K e gives slightly better results for most training sample sizes (12 times out of 17): if a sign test is used, this yields a p-value of 0.07, indicating that the difference is significant with a risk of 7%.It is also important to keep in mind that K L&J is not guaranteed to be a valid kernel and thus the parameter t must be tuned with care. Figure4.8 demonstrates that this kernel can perform poorly if t is not tuned properly. Unlike K L&J , our edit kernel is guaranteed to be valid and is parameter-free. Comparison of our edit kernel with other string kernels on a handwritten digit recognition task.

		100
	Accuracy on 2,000 test strings	86 88 90 92 94 96 98				K N &B Spectrum Subsequence K L&J K e
		0	1000 2000 3000 4000 5000 6000 7000 8000
				Size of training sample
	Figure 4.7: Training sample size	1,000	2,000	3,000	4,000	5,000	6,000	7,000	8,000
	Ke vs spectrum	0	0	0	0	0	0	0	0
	Ke vs subsequence 4E-04	8E-04	5E-04	2E-04	2E-04	4E-04	2E-05	4E-05
	Ke vs K L&J	3E-01	4E-01	3E-01	3E-01	3E-01	4E-01	4E-01	7E-01
	Ke vs K N &B	6E-06	6E-06	1E-03	2E-10	6E-09	4E-08	4E-07	1E-04

Table 4.2: Statistical comparison of our edit kernel with other string kernels (p-values of a Student's paired t-test). Boldface indicates that the difference is significant in favor of our kernel using a risk of 5%.

Table 5 .

 5

1: Example of a set of 11 reasonable points (Word dataset).

Table 5 .

 5 4), where K C outperforms e L and p e on both datasets. These first results open the door to a further theoretical analysis and might lead to k-NN generalization guarantees for GESL.

		76
		74
	Classification accuracy	60 62 64 66 68 70 72 58				d lev p e K C
		56
		0	200	400	600	800 1000 1200 1400 1600
				Size of k-NN training sample
	Figure 5.14: 1-Nearest Neighbor accuracy results (Word dataset).
				Similarity Accuracy
				e L		97.08%
				p e		96.44%
				K C		97.50%

After having dealt with structured data, in the next part of this thesis we will focus on data consisting of feature vectors. While in the context of strings or trees, we could only

Table 5

 5

.4: 1-Nearest Neighbor accuracy results on the Digit dataset.

  distance learning algorithms: Large Margin Nearest Neighbor 2 (LMNN) from[START_REF] Kilian | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF] and Information-Theoretic Metric Learning 3 (ITML) from[START_REF] Davis | Information-theoretic metric learning[END_REF]. Recall that LMNN essentially optimizes the k-NN error on the training set (with a safety margin), whereas ITML aims at best satisfying pair-based constraints while minimizing the LogDet divergence between the learned matrix M and the identity matrix (refer to Section 3.2.1 for more details on these methods). We conduct this experimental study on seven classic binary classification datasets of varying domain, size and difficulty, mostly taken from the UCI Machine Learning Repository 4 . Their properties are summarized in Table6.1. Some of them, such as Breast, Ionosphere or Pima, have already been extensively used to evaluate metric learning methods.

  Table 6.1. 6

	Dataset	Breast	Iono. Rings	Pima	Splice Svmguide1 Cod-RNA
	# training examples	488	245	700	537	1,000	3,089	59,535
	# test examples	211	106	300	231	2,175	4,000	271,617
	# dimensions	9	34	2	8	60	4	8
	# dim. after KPCA	27	102	8	24	180	16	24
	# runs	100	100	100	100	1	1	1
	On Cod-RNA, KPCA was run on a randomly drawn subsample of 10% of the training
	data.
	Unless predefined training and test sets are available (as for Splice, Svmguide1 and Cod-
	RNA), we randomly generate 70/30 splits of the data, and average the results over 100
	runs. Training sets are further partitioned 70/30 for validation purposes.

Table 6 . 1 :

 61 Properties of the seven datasets used in the experimental study.

  Table6.3). Surprinsingly (because it is not designed for k-NN), SLLC achieves the best results on 4 datasets (a possible reason for this is given in the next paragraph). It is, however, outperformed by LMNN or ITML on the 3 biggest problems. For most tasks, the accuracy obtained in linear classification is better or similar to that of 3-NN (highlighting the fact that Average accuracy (normal type) and sparsity (italic type) of the linear classifiers built from the studied similarity functions. For each dataset, boldface indicates the most accurate method (sparsity is used to break the ties).

	Dataset	Breast	Iono.	Rings	Pima Splice	Svmguide1 Cod-RNA
	K I	96.57 20.39	89.81 52.93	100.00 18.20	75.62 25.93	83.86 362	96.95 64	95.91 557
	SLLC	96.90 1.00	93.25 1.00	100.00 1.00	75.94 1.00	87.36 1	96.55 8	94.08 1
	LMNN	96.81 9.98	90.21 13.30	100.00 18.04	75.15 69.71	85.61 315	95.80 157	88.40 61
	LMNN KPCA	96.01 8.46	86.12 9.96	100.00 8.73	74.92 22.20	86.85 156	96.53 82	95.15 591
	ITML	96.80 9.79	92.09 9.51	100.00 17.85	75.25 56.22	81.47 377	96.70 49	95.06 164
	ITML KPCA	96.23 17.17	93.05 18.01	100.00 15.21	75.25 16.40	85.29 287	96.55 89	95.14 206
	Table 6.2: Dataset	Breast	Iono.	Rings	Pima Splice	Svmguide1 Cod-RNA
	K I	96.71	83.57	100.00	72.78	77.52	93.93	90.07
	SLLC	96.90	93.25	100.00	75.94	87.36	93.82	94.08
	LMNN	96.46	88.68	100.00	72.84	83.49	96.23	94.98
	LMNN KPCA	96.23	87.13	100.00	73.50	87.59	95.85	94.43
	ITML	92.67	88.29	100.00	72.07	77.43	95.97	95.42
	ITML KPCA	96.38	87.56	100.00	72.80	84.41	96.80	95.32
	Table 6.3: Average accuracy of 3-NN classifiers using the studied similarity functions.
	For each dataset, boldface indicates the most accurate method.

Table 6 .

 6 Feature space induced by the similarity in which the linear classifier is learned (Rings dataset). Dimension was reduced to 2 for visualization purposes using Principal Component Analysis.

		KI					SLLC
		LMNN				ITML
	Figure 6.2: Dataset	Breast	Iono.	Rings Pima	Splice	Svmguide1 Cod-RNA
	SLLC	4.76	5.36	0.05	4.01	158.38	185.53	2471.25
	LMNN	25.99	16.27	37.95	32.14	309.36	331.28	10418.73
	LMNN KPCA	41.06	34.57	84.86	48.28	1122.60	369.31	24296.41
	ITML	2.09	3.09	0.19	2.96	3.41	0.83	5.98
	ITML KPCA	1.68	5.77	0.20	2.74	56.14	5.30	25.25

4: Average time per run (in seconds) required for learning the similarity.

  Feature space induced by the similarity in which the linear classifier is learned (Svmguide1 dataset). Dimension was reduced to 2 for visualization purposes using Principal Component Analysis.

			KI		SLLC
			LMNN		ITML
	Figure 6.3: Method	Convex	Scalable	Competitive	Reg. Low-rank	Online	Gen.

  this last contribution, we propose to address the lack of theoretical framework by studying the generalization ability of metric learning algorithms according to a notion of algorithmic robustness. Recall that algorithmic robustness, introduced by Xu & Mannor (2010, 2012) and described in Section 2.2.3, allows one to derive generalization bounds when, given two "close" training and testing examples, the variation between

their associated loss is bounded. This notion of closeness of examples relies on a partition of the input space into different regions such that two examples in the same region are seen as close. We propose here to adapt this notion of algorithmic robustness to metric learning, where training data is made of pairs (or triplets). We show that, in the context of robustness, the problem of training pairs not being i.i.d. can be worked around by simply assuming that the pairs are built from an i.i.d. sample of labeled examples.

  learning method A is almost surely weakly robust if it is robust with respect to almost all T .The definition of robustness requires the labeled sample space to be partitioned into disjoint subsets such that if some instances of pairs of train/test examples belong to the same partition, then they have similar loss. Weak robustness is a generalization of this notion where we consider the average loss of testing and training pairs: if for a large (in the probabilistic sense) subset of data, the testing loss is close to the training loss, then the algorithm is weakly robust. From Proposition 7.2, we can see that if for any fixed > 0 there exists K such that an algorithm A is (K, (•)) robust, then A is weakly robust. We now give the main result of this section about the necessity of robustness.Theorem 7.8. Given a fixed sequence of training examples T * , a metric learning method A generalizes with respect to P T * if and only if it is weakly robust with respect to P T

* .

Proof Following

Xu & Mannor (2012)

, the sufficiency is obtained by the fact that the testing pairs are built from a sample U (n) made of n i.i.d. instances. We give the proof in Appendix B.2.2.

  Ying and Peng Li. Distance Metric Learning with Eigenvalue Optimization. Journal of Machine Learning Research (JMLR), 13:1-26, 2012. Zheng-Jun Zha, Tao Mei, Meng Wang, Zengfu Wang, and Xian-Sheng Hua. Robust Distance Metric Learning with Auxiliary Knowledge. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pages 1327-1332, 2009. Changshui Zhang, Feiping Nie, and Shiming Xiang. A general kernelization framework for learning algorithms based on kernel PCA. Neurocomputing, 73(4-6):959-967, 2010. Kaizhong Zhang and Dennis Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing (SICOMP), 18(6): 1245-1262, 1989. Ji Zhu, Saharon Rosset, Trevor Hastie, and Robert Tibshirani. 1-norm Support Vector Machines. In Advances in Neural Information Processing Systems (NIPS), volume 16, pages 49-56, 2003.

http://lampada.gforge.inria.fr/

http://pascallin2.ecs.soton.ac.uk/

Note that there exist other learning paradigms, such as unsupervised learning(Ghahramani,

2003), semi-supervised learning[START_REF] Chapelle | Semi-Supervised Learning[END_REF], transfer learning (Pan & Yang, 2010), reinforcement learning(Sutton & Barto, 1998), etc.

In fact, regularized and constrained problems are equivalent in the sense that for any value of the parameter β of a feasible constrained problem, there exists a value of the parameter λ of the

In fact, the Rademacher complexity can sometimes implicitly take into account the regularization term of the algorithm.

Definition 2.8 corresponds to the case where the training sample is altered through the replacement of an instance by another.[START_REF] Bousquet | Algorithmic Stability and Generalization Performance[END_REF], 2002) also give a definition of uniform stability based on the removal of an instance from the training sample, which implies Definition 2.8. We will use Definition 2.8 throughout this thesis: we find it more convenient to deal with since replacement preserves the size of the training sample.

Note that many loss functions are unbounded if their domain is assumed to be unbounded (see Figure2.3), but in practice they have bounded domain due for example to the common assumption that the norm of any instance is bounded.

Sparsity is seen here as the ability to identify redundant features.

Note that in the case of strings of equal length, the edit distance is upper bounded by the Hamming distance.

This specific notation is required to deal with nonmemoryless cPFT.

http://svmlight.joachims.org/

K L&J is made symmetric by adding pe(x |x) and pe(x|x ).

For now, we assume that the set of reasonable points is given. The question of finding such a set is addressed later in this section.

Note that the landmark points need not to be labeled, although we do not make use of this feature in our contributions.

The original formulation(Balcan et al., 2008b) was actually L1-constrained. We provide here an equivalent, more practical L1-regularized form.

Note that L1 regularization has also been used in the context of standard SVM formulations, leading to the 1-norm SVM(Zhu et al., 2003). While these classifiers may work well in practice, most of the handy SVM theory fall apart in this case. Conversely, the use of (5.2) is justified by the theory presented in this section.

The problem of finding the reasonable points is not as simple if we first want to learn the similarity function, as we will see later in this chapter.

We normalized them to zero mean and unit variance, then brought back to 1 and -1 the values greater than 1 and smaller than -1 respectively. We are aware that there may be better normalizations but this is outside the scope of this work.

Note that we did not include 1-norm SVM in this experimental study because the learning rule itself is very similar to Balcan's learning rule while having no grounds in SVM theory.

http://www.csie.ntu.edu.tw/ ~cjlin/libsvm/

http://en.wiktionary.org/wiki/Wiktionary:Frequency_lists

In practice, one could use another type of script. We picked the Levenshtein script because it is a "reasonable" edit script, since it corresponds to a shortest script transforming x into x .

To satisfy Definition 5.5, their domain must be bounded[START_REF] Rosasco | Are Loss Functions All the Same? Neural Computation[END_REF].

We do not evaluate the pairing strategies on the whole data (nT = 2, 000) so that we can build 5 bootstrap samples and average the results over these.

Since we assume x

≤ 1 and M F ≤ 1, this can be obtained by dividing by the constant 1 + 1 γ .

Code download from: http://www.cse.wustl.edu/ ~kilian/code/lmnn/lmnn.html

Code download from: http://www.cs.utexas.edu/ ~pjain/itml/

http://archive.ics.uci.edu/ml/

K I , LMNN and ITML are normalized to ensure their values belong to [-1, 1].

Note that the amount of variance captured thereby was greater than 90% for all datasets.

http://www.mosek.com/

Recall from Section

2.2.3 that Z is partitioned such that if two examples fall into the same region, then they share the same label.

Download from: http://labh-curien.univ-st-etienne.fr/ ~bellet/

Remerciements

In this section, we propose an analysis that holds for a large class of loss functions.

We consider loss functions that fulfill the k-lipschitz property with respect to the first argument C (Definition 5.5) and the definition of (σ, m)-admissibility (Definition 5.6).

Definition 5.5. A loss function (C, z 1 , z 2 ) is k-lipschitz with respect to its first argument if for any matrices C, C and any pair of labeled examples (z 1 , z 2 ):

Definition 5.6. A loss function (C, z 1 , z 2 ) is (σ, m)-admissible, with respect to C, if (i) it is convex with respect to its first argument and (ii) the following condition holds:

with z i = (x i , y i ), for i = 1, 2, 3, 4, are labeled examples. Definition 5.6 requires the deviation of the losses between two pairs of examples to be bounded by a value that depends only on the labels and on some constants independent from the examples and the cost matrix C. It follows that the labels must be bounded, which is not a strong assumption in the classification setting we are interesting in. In our case, we have binary labels (y i ∈ {-1, 1}), which implies that the quantity |y 1 y 2y 3 y 4 | is either 0 or 2. We will see in Section 5.5.2 that the hinge loss of GESL HL satisfies Definition 5.5 and Definition 5.6. This can also be shown for other popular loss functions, such as the logistic loss or the exponential loss. 11

Note that from the convexity of with respect to its first argument, it follows that R , R T and F T are convex functions.

Our objective is to derive an upper bound on the true risk R (C T ) with respect to the empirical risk R T (C T ) using uniform stability (Definition 2.8) adapted to the case where training data consist of pairs [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF].

Definition 5.7 [START_REF] Jin | Regularized Distance Metric Learning: Theory and Algorithm[END_REF]. A learning algorithm has a uniform stability in κ n T , where κ is a positive constant, if

where T i,z is the new set obtained by replacing z i ∈ T by a new example z.

To prove that GESL L has the property of uniform stability, we need the following lemma and the k-lipschitz property of .

Lemma 5.8. Let F T and F T i,z be the functions to optimize, C T and C T i,z their corresponding minimizers, and β the regularization parameter used in GESL L . Let

Finally, let us conclude this section by discussing the adaptation of the entire theoretical analysis to tree edit similarity learning. The generalization bound for GESL L (Theorem 5.13) holds for trees since the arguments used in Section 5.5.1 are not specific to strings. Regarding the bound for GESL HL (Theorem 5.17), we used the assumption that the length of the strings is bounded by a constant W . This can be easily adapted to trees: if we assume that the size of each tree (in its number of nodes) is bounded by W , Theorem 5.17 also holds. Finally, the arguments for deriving a bound independent of the constant W hold for trees since the property (5.5) is also valid for rational stochastic tree languages [START_REF] Denis | Relevant Representations for the Inference of Rational Stochastic Tree Languages[END_REF].

Experimental Validation

In this section, we provide an experimental evaluation of GESL HL . 12 We are interested in evaluating the performance of different (standard or learned) edit similarities directly plugged into linear classifiers, as suggested by the theory of ( , γ, τ )-goodness presented in Section 5.2. Linear classifiers are learned using Balcan's learning rule (5.2). We compare three edit similarity functions: (i) K C , learned by GESL HL , 13 (ii) the Levenshtein distance d lev , which constitutes the baseline, and (iii) an edit similarity function p e learned with an EM-like algorithm [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF]. We show results on the same datasets as in the preliminary study (Section 5.3): English and French words (Section 5.6.1) and handwritten digits (Section 5.6.2).

English and French Words

Recall that the task is to learn a model to classify words as either English or French.

We use the 2,000 top words lists from Wiktionary. 14

Convergence rate

We first assess the convergence rate of the two considered edit cost learning methods (i and iii). We keep aside 600 words as a validation set to tune the parameters, using 5-fold cross-validation and selecting the value offering the best classification accuracy.

We then build bootstrap samples T from the remaining 2,000 words to learn the edit 12 An open-source implementation of our method is available at: http://labh-curien.univ-st-etienne.fr/ ~bellet/.

13 In this series of experiments, we constrained the cost matrices to be symmetric to be independent from the order in which the instances are paired.

14 These lists are available at http://en.wiktionary.org/wiki/Wiktionary:Frequency_lists. We only considered unique words (i.e., not appearing in both lists) of length at least 4, and we also got rid of accent and punctuation marks. We ended up with about 2,600 words over an alphabet of 26 symbols.

Classic robustness

Robustness for metric learning

.1: Illustration of the property of robustness in the classic and metric learning settings. In this example, we use a cover based on the L 1 norm. In the classic definition, if any example z falls in the same region C i as a training example z, then the deviation between their loss must be bounded. In the metric learning definition proposed in this work, for any pair (z, z ) and a training pair (z 1 , z 2 ), if z, z 1 belong to some region C i and z , z 2 to some region C j , then the deviation between the loss of these two pairs must be bounded.

Robustness for Metric Learning

We present here our adaptation of the definition of robustness to metric learning.

In Section 2.2.3, we have seen that robustness relies on a partition of the space Z into K disjoint subsets such that for every training and testing instances belonging to the same region of the partition, the deviation between their respective losses is bounded by a term (T ). 1 In order to adapt this notion to metric learning, the idea is to use the partition of Z at the pair level: if a new test pair of examples is close to a training pair, then the respective losses of the two pairs must be close. Two pairs are close when each instance of the first pair falls into the same subset of the partition of Z as the corresponding instance of the other pair, as shown in Figure 7.1. A metric learning algorithm with this property is called robust. This notion is formalized in the following definition.

Definition 7.1 (Robustness for metric learning). An algorithm A is (K, (•)) robust for

, such that the following holds for all T ∈ Z n :

K and (•) quantify the robustness of the algorithm which depends on the training sample. Note that the property of robustness is required for every training pair of the sample -we will later see that this property can be relaxed.

Note that this definition of robustness can be easily extended to triplet-based metric learning. In this context, the robustness property can then be expressed by:

(7.1)

Generalization of Robust Metric Learning Algorithms

We now give a PAC generalization bound for metric learning algorithms satisfying the property of robustness (Definition 7.1). We first give the following concentration inequality that we will use in the derivation of the bound.

Proposition 7.2 (van der [START_REF] Van Der | Weak convergence and empirical processes[END_REF].

nomial random variable with parameters n and (µ(C 1 ), . . . , µ(C K )). By the Breteganolle-Huber-Carol inequality we have: P r

We now give our first result on the generalization of metric learning algorithms.

Theorem 7.3. If a learning algorithm A is (K, (•))-robust and the training sample consists of the pairs P T obtained from a sample T generated by n i.i.d. draws from P , then for any δ > 0, with probability at least 1δ we have:

Now, by contradiction, suppose algorithm A is not weakly robust, Lemma 7.9 implies Equation 7.5 holds for infinitely many n. This combined with Equation 7.6 implies that for infinitely many n:

which means A does not generalize, thus the necessity of weak robustness is established.

The following corollary follows immediately from Theorem 7.8.

Corollary 7.10. A metric learning method A generalizes with probability 1 if and only if it is almost surely weakly robust.

This corollary establishes a strong link between generalization in metric learning and the notion of weak robustness. In the next section, we illustrate the applicability of our framework by showing that many existing metric learning algorithms are robust in our sense.

Examples of Robust Metric Learning Algorithms

We first restrict our attention to Mahalanobis distance learning algorithms of the form:

where • is some matrix norm and C > 0 a regularization parameter. The loss function is assumed to be of the form

where g is nonnegative and Lipschitz continuous with Lipschitz constant U . It typically outputs a small value when its input is large positive and a large value when it is large negative. Lastly,

) is the largest loss when M is the zero matrix 0.

Recall that showing that a metric learning algorithm is robust (Definition 7.1) implies that the algorithm has generalization guarantees (Theorem 7.3). To prove the robustness of (7.7), we will use the following theorem, which essentially says that if a metric learning algorithm achieves approximately the same testing loss for pairs that are close to each other, then it is robust.

List of Publications

APPENDIX A

Learning Conditional Edit Probabilities

Our string edit kernel introduced in Chapter 4 is based on edit probabilities learned from a generative or discriminative probabilistic model. In the experimental section, we build the kernel from the method of [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF], which is based on estimating the parameters of a conditional memoryless transducer. This appendix gives the technical details of their approach.

Recall that S denotes the set of positive pairs. For the sake of simplicity, we assume that the input and the output alphabets are the same, denoted by Σ. In the following, unless stated otherwise, symbols are denoted by a, b, . . . , and pairs of input and output strings by (x, x ) or (w, w ) when needed. Let f be a function such that [f (x)] π(x,... ) is equal to f (x) if the predicate π(x, . . . ) holds and 0 otherwise, where x is a (set of) dummy variable(s). In this appendix, for notational convenience, we will see the edit probability matrix as a function. Let c be the conditional probability function that returns for any edit operation (b|a) the probability to output the symbol b given an input symbol a.

The aim of this appendix is to show how one can automatically learn the function c from the training pairs S. The values c(b|a), ∀a ∈ Σ ∪ {$}, b ∈ Σ ∪ {$} represent the parameters of the memoryless machine T . These parameters are trained using an EMbased algorithm that relies on the so-called forward and backward functions.

The conditional edit probability p e (x |x) of the string x given an input string x can be recursively computed using the forward function α : Σ * × Σ * → R + defined as follows:

Using α(x |x), we get

where c($|$) is the probability of the termination symbol of a string.

In a symmetric way, p e (x |x) can be recursively computed using the backward function

And we get that

Both functions can be computed in O(|x||x |) time using a dynamic programming technique and will be used in the following to learn the function c.

In the considered model, a probability distribution is assigned conditionally to each input string, i.e.,

This is equal to 0 when the input string x is not in the domain of the function. 1 It can be shown (see [START_REF] Oncina | Learning Stochastic Edit Distance: application in handwritten character recognition[END_REF], for the proof) that correct normalization of each conditional distribution is obtained when the following conditions over the function c are fulfilled:

The EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] can be used in order the find the optimal parameters of the function c by alternating between an E-step and an M-step. Given an auxiliary (|Σ| + 1) × (|Σ| + 1) matrix δ, the E-step aims at computing the values of δ as

we have a 0 0 indeterminate. We choose to avoid it by taking 0 0 = 0, in order to keep x ∈Σ * p(x |x) finite.

The M-step allows us to get the current edit costs:

where

Proof. The first steps of this proof are similar to the proof of Lemma 20 in [START_REF] Bousquet | Stability and Generalization[END_REF] which we recall for the sake of completeness. Recall that any convex function g verifies ∀x, y, ∀t ∈ [0, 1], g(x + t(yx))g(x) ≤ t(g(y)g(x)).

R T i,z is convex and thus for any t ∈ [0, 1],

Switching the role of C T and C T i,z , we get:

Summing up inequalities (B.1) and (B.2) yields

Now, since C T and C T i,z are minimizers of F T and F T i,z respectively, we have:

By summing up (B.4) and (B.5) we get:

By summing this last inequality with (B.3), we obtain

We now derive a bound for B. In the following, z k j ∈ T denotes the j th landmark associated to z k ∈ T such that f land T (z k , z k j ) = 1 in T , and z i k j ∈ T i,z the j th landmark associated to

This inequality is obtained by developing the sum of the first two terms of the second line. The examples z i in T and z in T i,z have n L landmarks defined by f land T and f land T i,z respectively. Note that the samples of n T -1 elements T \{z i } and T i,z \{z} are the same and thus z k = z i k when k = i. Therefore, for any z k ∈ T \{z i }, the sets of landmarks

Thus, some terms cancel out and we have:

The first two lines of the absolute value can be bounded by:

(2

The same analysis can be done for the part in parentheses of the last line of the absolute value and we can take the pair of examples in T and in T i,z maximizing the whole absolute value to obtain the next inequality:

We continue by applying a reordering of the terms and the triangular inequality to get the next result:

We then use twice the k-lipschitz property of which leads to:

Then, by applying this bound on B from inequality (B.6), we get the lemma.

B.1.2 Proof of Lemma 5.11

Lemma For any learning method of estimation error D T and satisfying a uniform

Proof. First recall that for any T, z, z , by hypothesis of uniform stability we have:

The last inequality is obtained by applying the hypothesis of uniform stability to the second part of the sum. Now, since T , z and z are drawn i.i.d. from distribution P , we do not change the expected value by replacing one point with another and thus:

Then, by applying this trick twice on the first element of the sum:

which gives the lemma.

B.1.3 Proof of Lemma 5.12

Lemma For any edit cost matrix learned by GESL L using n T training examples and n L landmarks, and any loss function satisfying (σ, m)-admissibility, we have the following bound:

Proof. First, we derive a bound on

)| by using the hypothesis of stability twice. Now, proving Lemma 5.12 boils down to bounding the last term above. Using arguments similar to those used in the second part of the proof of Lemma 5.8, we get

Now by the (σ, m)-admissibility of , we have that:

since whatever the labels, |y 1 y 2y 3 y 4 | ≤ 2. This leads us to the desired result.

B.1.4 Proof of Lemma 5.14

Lemma The function HL is k-lipschitz with k = W .

Proof. We need to bound | HL (C, z, z ) -HL (C , z, z )| which implies to consider two cases: when z and z' have the same labels and when they have different labels. We consider here the first case, the second one can be easily derived from the first one (B 1 playing the same role as B 2 ).

The second line is obtained by the 1-lipschitz property of the hinge loss:

The fourth one comes from the Cauchy-Schwartz inequality:

Finally, since by hypothesis #(z, z ) F ≤ W , the lemma holds.

B.1.5 Proof of Lemma 5.15

Lemma Let (C T , B 1 , B 2 ) an optimal solution learned by GESL HL from a training sample T , and let

Proof. Since (C T , B 1 , B 2 ) is an optimal solution, the value reached by the objective function is lower than the one obtained with (0, B γ , 0), where 0 denotes the matrix of zeros:

For the last inequality, note that regardless of the labels of z k and z k j , HL (0, z k , z k j ) is bounded either by B γ or 0. Since with probability at least 1δ we have:

Proof. From the proof of Theorem 7.3, we can easily deduce that:

Then, we have

The second inequality is obtained by the triangle inequality, the last one is obtained by the application of Proposition 7.2, the hypothesis of pseudo-robustness and the fact that is nonnegative and bounded by B and thus

B.2.2 Proof of sufficiency of Theorem 7.8

Theorem Given a fixed sequence of training examples T * , a metric learning method A generalizes with respect to P T * if and only if it is weakly robust with respect to P T * .

Proof. The proof of sufficiency corresponds to the first part of the proof of Theorem 8 of Xu & Mannor (2012). When A is weakly robust there exists a sequence {D n } such that for any δ, > 0 there exists N (δ, ) such that for all n > N(δ, ), P r(U

Therefore for any n > N(δ, ),

The first inequality holds because the testing samples U (n) consist of n instances IID from P . The second equality is obtained by conditional expectation. The next inequality uses the fact that is nonnegative and upper bounded by B. Finally, we apply (B.7). We thus conclude that A generalizes for P T * because and δ can be chosen arbitrarily.

B.2.3 Proof of Lemma 7.9

Lemma Given T * , if a learning method is not weakly robust with respect to P T * , there exist * , δ * > 0 such that the following holds for infinitely many n:

Proof. This proof follows exactly the same principle as the proof of Lemma 2 from Xu & Mannor (2012). By contradiction, assume * and δ * do not exist. Let

For each n we define

For each n ≥ N (v) we have

Note that v(n) tends to infinity, it follows that δ v(n) → 0 and v(n) → 0. Therefore,

That is A is weakly robust with respect to P T , which is the desired contradiction.

Proof. Let M * be the solution given training data P T . Due to optimality of M * , we have M * 1 ≤ g 0 /C. We can partition Z as |Y|N (γ/2, X , • 1 ) sets, such that if z and z belong to the same set, then y = y and x - Proof. We assume H to be an Hilbert space with an inner product operator •, • . The mapping φ is continuous from X to H. The norm • H : H → R is defined as x H =

x, x for all x ∈ H, for matrices M H we take the Frobenius norm. The kernel function is defined as K(x 1 , x 2 ) = φ(x 1 ), φ(x 2 ) . B γ and f H (γ) are finite by the compactness of X and continuity of K(•, •). Let M * be the solution given training data P T , by the optimality of M * and using the same trick as for the previous example proofs we have M * H ≤ g 0 /c. Then, by considering a partition of Z into |Y|N (γ/2, X , • 2 ) disjoint subsets such that if (x 1 , y 1 ) and (x 2 , y 2 ) belong to the same set then y 1 = y 2 and x 1x 2 2 ≤ γ.