Aurélien Bellet
email: aurelien.bellet@bvra.univ-st-etienne.fr

Marc Bernard
email: marc.bernard@univ-st-etienne.fr

Thierry Murgue
email: thierry.murgue@univ-st-etienne.fr

Marc Sebban
email: marc.sebban@univ-st-etienne.fr

Learning State Machine-based String Edit Kernels

Keywords: String kernel, marginalized kernel, learned edit distance

come   L'archive ouverte pluridisciplinaire

Introduction

With the success of kernel-based learning methods [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF], a number of structural kernels have been proposed in the literature to handle structured data such as strings. A first natural way to design string kernels consists in representing each sequence by a fixed-length numerical vector. In this context, the spectrum kernel proposed in [START_REF] Leslie | The spectrum kernel: a string kernel for svm protein classification[END_REF] was one of the first string kernels. It relies on the principle that two strings should be considered as similar if they share a large number of contiguous subsequences. In the specific case of a p-spectrum, a string is represented by a histogram of frequencies of all contiguous subsequences of length p. Then, a dot product can be performed between two feature vectors to compute the kernel. To overcome the inconveniences of such an exact matching, the mismatch kernel [START_REF] Leslie | Mismatch string kernels for discriminative protein classification[END_REF] generalizes the spectrum one by comparing the frequencies of subsequences which are not exactly the same, i.e. allowing a given number of mismatches. Another extension of the spectrum kernel, called subsequence kernel [START_REF] Lodhi | Text classification using string kernels[END_REF], considers features made of possibly non-contiguous subsequences. Finally, in the specific context of protein remote homology detection, the distant segments kernel [START_REF] Boisvert | Hiv-1 coreceptor usage prediction without multiple alignments: an application of string kernels[END_REF] extends the spectrum kernel to include positional information of polypeptide segments. Each component of the feature vector denotes the number of times a segment x is located at a given distance following a segment x ′ .

Another way to build string kernels while admitting error-tolerant matching consists of deriving kernels from similarity measures. For instance, Saigo et al. [START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF] designed a local alignment kernel to detect remote homologies in protein sequences. This kernel assesses the similarity between two sequences by summing up scores computed from local alignments allowing gaps. Other kernels have been derived from the edit distance [START_REF] Wagner | The string-to-string correction problem[END_REF], which corresponds to the minimal number of operations (in terms of insertion, deletion or substitution of symbols) to transform a string into another one. The edit distance is a metric and tightly related to the optimal alignment between two sequences. The resulting kernels based on the edit distance are usually called string edit kernels. Using this kind of kernels in classification tasks is interesting for a double reason: first, it enables us to better measure the dissimilarity between two strings by considering more possible structural distortions than the previously mentioned string kernels (i.e. spectrum, mismatch, subsequence kernels); second, it allows us to take advantage of powerful learning algorithms such as the support vector machines (svm) to leave the constrained context of nearest-neighbor classifiers that are usually used with the edit distance [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF]. For these reasons, string edit kernels have seen an increasing amount of interest in recent years [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF][START_REF] Cortes | Rational kernels: Theory and algorithms[END_REF][START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF]. It is important to note that these kernel functions usually assume that the edit distance is negative definite. Indeed, to guarantee the convergence of the learning algorithm (e.g. svm), this condition is required to ensure that the resulting kernel functions are valid kernels. However, in [START_REF] Cortes | Rational kernels: Theory and algorithms[END_REF], the authors proved that the edit distance over a non-trivial alphabet Σ is not negative definite. This constitutes a theoretical drawback of the state of the art string edit kernels. Moreover, from a practical point of view, they usually use a standard version of the edit distance, i.e. the costs of the edit operations are a priori fixed (often to the same value). This is actually the case when no background knowledge is available. Parallel to this work on edit kernels, a recent line of research has investigated the ways to automatically learn the edit parameters from a learning sample in the form of state machines [START_REF] Durbin | probalistic models of protein and nucleic acids[END_REF][START_REF] Ristad | Learning string-edit distance[END_REF][START_REF] Mccallum | A conditional random field for disciminatively-trained finite-state string edit distance[END_REF][START_REF] Oncina | Learning stochastic edit distance: application in handwritten character recognition[END_REF][START_REF] Bernard | A discriminative model of stochastic edit distance in the form of a conditional transducer[END_REF]. These edit parameters can then be used in neighborhood-based classifiers. Given a pair of strings (x, x ′ ), the output of these models is not an edit cost anymore, but rather an edit probability to change x into x ′ by edit operations. It is important to note that these edit parameters no more allow us to obtain a true distance (the symmetry and reflexivity properties are often violated) that prevents us from using them in standard edit kernels such as those presented in [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF][START_REF] Cortes | Rational kernels: Theory and algorithms[END_REF][START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF]. To overcome this problem, we show in this paper how one can derive a new positive definite string edit kernel from these learned edit probabilities. Indeed, a third possibility to design string kernels is to exploit probability distributions issued from stochastic models as done in the Fisher kernel or its variants [START_REF] Tsuda | Marginalized kernels for biological sequences[END_REF]. For instance, as shown by Haussler [START_REF] Haussler | Convolution kernels on discrete structures[END_REF], the joint probability p(x, x ′ ) of emitting two strings x and x ′ under a pair-Hidden Markov Model (pair-HMM) is a valid kernel that can be used to obtain by convolution new valid string kernels. In this paper, we show how to exploit edit probabilities that have been learned in the form of conditional state machines to create a new performing string edit kernel. We show that the computation of our new kernel requires to perform the intersection of two probabilistic automata, that is a special case of composition of stochastic transducers, as shown in [START_REF] Cortes | Rational kernels: Theory and algorithms[END_REF] for designing rational kernels.

The rest of this article is organized as follows: Section 2 is devoted to the presentation of the state of the art string edit kernels. After having introduced in Section 3 our new string edit kernel, we briefly recall in Section 4 the main available approaches dealing with the learning of the edit parameters. Section 5 is devoted to the computation of our kernel based on a specific case of composition of stochastic transducers. Finally, we present a large experimental study in Section 6, comparing our new learned edit kernel with the state of the art string kernels. We show that our approach provides significant improvements on a pattern recognition task.

Related work on string edit kernels

A common method used to define a string edit kernel from the standard edit distance e d is the following [START_REF] Cortes | Rational kernels: Theory and algorithms[END_REF][START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF]:

k(x, x ′ ) = e -t•e d (x,x ′ ) , ∀x, x ′ ∈ Σ * , ( 1
)
where t is a positive real value. However, as mentioned in [START_REF] Cortes | Rational kernels: Theory and algorithms[END_REF], there exists t > 0 for which this kernel is not positive definite, that does not guarantee the convergence of training for learning algorithms such as svm. In [START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF], the authors show that t can be experimentally tuned according to the training data, but this remains a difficult task. Moreover, note that a slight modification of t can result in large differences of performance (see Section 6).

In [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF], Neuhaus and Bunke present the following string edit kernel assuming the symmetry of the edit distance:

k(x, x ′ ) = k x 0 (x, x ′ ) = 1 2 e d (x, x 0 ) 2 + e d (x 0 , x ′ ) 2 -e d (x, x ′ ) 2 , (2)
where x 0 is called a zero string. This kernel describes a measure of the squared distance from string x to x 0 and from x 0 to x ′ in relation to the squared distance from x to x ′ . Neuhaus and Bunke show that two more complex kernels can be obtained by selecting a set I of zero strings and combining the resulting kernels in a so-called sum kernel k + I (x, x ′ ) and product kernel k * I (x, x ′ ):

k + I (x, x ′ ) = x 0 ∈I k x 0 (x, x ′ ), (3)
k * I (x, x ′ ) = x 0 ∈I k x 0 (x, x ′ ). (4)
In these previous two edit kernels, the set I of zero strings plays an important role. In their experiments, the authors employ an iterative greedy selection strategy based on a validation set. Their experimental study shows that this edit kernel outperforms a nearest-neighbor classifier using the standard edit distance. However, it is compared neither to other edit kernels nor to the state of the art string kernels.

In [START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF], Saigo et al. present a string alignment kernel specifically dedicated to detect remote homologies in biological sequences. This kernel, computed from a matrix of substitution between amino acids, is called LA (Local Alignment) kernel. It can be derived from Eq.1, where all the possible local alignments π for changing x into x ′ are taken into account and where an alignment score s(x, x ′ , π) is used instead of the edit distance e d :

k LA (x, x ′ ) = π e t•s(x,x ′ ,π) , ( 5
)
where t is a parameter and s(x, x ′ , π) is the corresponding score of π and defined as follows:

s(x, x ′ , π) = a,b n a,b (x, x ′ , π) • S(a, b) -n g d (x, x ′ , π) • g d -n ge (x, x ′ , π) • g e , ( 6
)
where n a,b (x, x ′ , π) is the number of times that symbol a is aligned with letter b, S(a, b) is the substitution score between a and b, g d and g e (and their corresponding number of occurrences n g d (x, x ′ , π) and n ge (x, x ′ , π)) are two parameters dealing respectively with the opening and extension of gaps.

As mentioned in the introduction, another way to use the kernel described in Eq.1 is to compute it from edit probability distributions [START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF]. Indeed, the edit process can be viewed as a sequence of probabilistic events. In that way, the edit distance between x and x ′ can be computed from the summation of the negative logarithms of the transformation probabilities, as follows:

e d (x, x ′ ) = - i log p(x ′ i |x i ), ∀x i , x ′ i ∈ Σ ∪ {λ} ( 7
)
where λ is the empty symbol, p(x ′ i |x i ) is the probability to change the symbol x i into x ′ i at the i th operation of the optimal script changing x into x ′ . Plugging Eq.7 in Eq.1, we get the following edit kernel presented by Li & Jiang [START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF]:

k(x, x ′ ) = i p(x ′ i |x i ) t . (8)
As mentioned in [START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF], this kernel assumes that p(x ′ i |x i ) = p(x i |x ′ i ) which may not always be true. To guarantee the symmetry property, a solution consists of interpreting the edit distance as:

e d (x, x ′ ) = - 1 2 i log p(x ′ i |x i ) + i log p(x i |x ′ i ) .
Beyond the fact that our previous remark on the parameter t still holds (how t can be tuned to satisfy the property of positive definiteness?), defining a relevant value for p(x ′ i |x i ) is a difficult problem. In specific domains, some background knowledge is available allowing the use of such kernels. For instance, in molecular biology, some edit matrices have become standards to deal with amino acids (e.g. pam [START_REF] Dayhoff | A model of evolutionary change in proteins[END_REF] and blosum [START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF]). These matrices describe similarity scores for amino acids and can be transformed (see [START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF]) to be used as relevant estimates of p(x ′ i |x i ). However, in many other domains, such an information is not available. A solution to overcome this problem is to automatically learn those edit probabilities from learning examples. We will present some approaches that deal with this problem in Section 4.

New edit distance-based kernel

Before that, let us introduce our new string edit kernel, which is a specific case of the marginalized kernels as described in [START_REF] Kashima | Marginalized kernels between labeled graphs[END_REF]. Let p(x, x ′ , h) be the probability of observing jointly a hidden variable h ∈ H and two visible strings x, x ′ ∈ Σ * . p(x, x ′ ) can be obtained by marginalizing, i.e. summing over all variables h ∈ H, the probability p(x, x ′ , h), such that:

p(x, x ′ ) = h∈H p(x, x ′ , h) = h∈H p(x, x ′ |h) • p(h).
A marginalized kernel computes this probability making the assumption that x and x ′ are conditionally independent given h:

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

k(x, x ′ ) = h∈H p(h|x) • p(h|x ′ ) • K z (z, z ′ ), (10)
where K z (z, z ′ ) is the joint kernel depending on combined variables z = (x, h) and z ′ = (x ′ , h).

An interesting way to exploit kernel of Eq.10 as a string edit kernel is to use the following features:

• the finite set H of variables h is replaced by the infinite set of possible strings y ∈ Σ * ,

• as p(y|x), we use p e (y|x) which is the conditional probability to transform a string x into a string y by using edit operations,

• the Dirac kernel (that returns 1, ∀(z, z ′ )) is used as kernel K z (z, z ′ ).
Therefore, we obtain a new string edit kernel:

k(x, x ′ ) = y∈Σ * p e (y|x) • p e (y|x ′ ), (11)
which is positive definite as it corresponds to the dot product in the feature space defined by the following mapping: Φ : x → {p e (y|x)} y∈Σ * . However, the practical use of this edit kernel raises two crucial questions:

1. Is it possible to learn a unique model that provides an estimate of the probability p e (y|x) for any pair of strings (x, y)? 2. If so, how can we compute from such a model the infinite sum over y ∈ Σ * ?

While recent papers have already answered the first question (see the next section for a survey), the reply to the second one is the matter of the rest of the article.

How to learn the edit parameters?

Let us recall that the edit distance between two strings x and y (built from an alphabet Σ) is the cost of the best sequence of edit operations that changes x into y. Typical edit operations are symbol deletion, insertion and substitution, and to each of them is assigned a cost. Since tuning these costs can constitute a difficult task in many applications, supervised learning has been used during the last decade for learning the edit parameters.

In the context of the alignment of biological sequences, Saigo et al. [START_REF] Hiroto | Optimizing amino acid substitution matrices with a local alignment kernel[END_REF] optimized from a learning set the blosum substitution matrix by classical gradient descent. In order to control the optimization procedure, they designed an objective function that measures how well the local alignment kernel discriminates homologs from non-homologs. The learned substitution matrix S(a, b) can then be incorporated in the LA kernel already presented in Eq.5. In order to avoid to call on positive and negative examples, another solution to learn the edit parameters is to use a probabilistic framework and control the optimization process by resorting to statistical constraints. In this context, that will be used in the rest of this paper, a widespread approach uses the maximum likelihood paradigm to learn probabilistic state machines (e.g. probabilistic automata, stochastic transducers, pair-hidden markov models) that can be used to model edit probability distributions. When there is no reason that the cost of a given edit operation changes according to the context where the operation occurs, memoryless machines (i.e. that contain only one state) are sufficient and very efficient from an accuracy and algorithmic point of view. In this case, training boils down to learning a single matrix of |Σ ∪ {λ}| 2 parameters, i.e. a probability for each possible edit operation. A pioneer work that aimed to learn a memoryless transducer for modeling the edit probabilities has been presented by Ristadt and Yianilos in [START_REF] Ristad | Learning string-edit distance[END_REF]. This generative model takes the form of a one state machine whose parameters (i.e. the edit probabilities) are learned by using an Expectation Maximization (EM)-based algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF]. Using a forward procedure, it is then possible to deduce the joint edit probability p e (x, y) from the probabilities of the successive edit operations for changing x into y. However, to perform a classification task, one often requires p e (y|x) rather than p e (x, y). A solution consists in computing p e (y|x) = pe(x,y) p(x) , but it is common knowledge that this can induce a statistical bias. To overcome this drawback, a relevant strategy consists in directly learning a conditional model (that allows an unbiased computation of p e (y|x) [START_REF] Bouchard | The tradeoff between generative and discriminative classifiers[END_REF]) by adapting the maximization step of the EM algorithm, as done in [START_REF] Oncina | Learning stochastic edit distance: application in handwritten character recognition[END_REF]. In this context, the learned parameters are conditional edit probabilities. The authors of [START_REF] Oncina | Learning stochastic edit distance: application in handwritten character recognition[END_REF] show on a handwritten digit recognition task that such a discriminative model outperforms the generative one of Ristad and Yianilos.

Note that many applications can be treated by such memoryless models, such as the correction of typing errors made with a computer keyboard, the recognition of images represented with Freeman codes, or in recognition of musical pieces [START_REF] Habrard | Melody recognition with learned edit distances[END_REF]. However, learning a single matrix of edit costs can be viewed as insufficient in some applications, particularly when the operation plays a part more or less important in the string transformation according to its location. This is the case in molecular biology, where the edit operation on a symbol can depend on its presence in a transcription factor binding site. To deal with such situations, non-memoryless approaches have been proposed in the literature in the form of probabilistic state machines that are able to take into account the string context. They are mainly based on pair-HMM [START_REF] Durbin | probalistic models of protein and nucleic acids[END_REF][START_REF] Bilenko | Adaptive duplicate detection using learnable string similarity measures[END_REF], probabilistic deterministic automata (PDFA) [START_REF] Bernard | A discriminative model of stochastic edit distance in the form of a conditional transducer[END_REF], or stochastic transducers [START_REF] Eisner | Parameter estimation for probabilistic finite-state transducers[END_REF]. The string context is taken into account in each state by a specific statistical distribution over the edit operations. However, these models are generative and so do not allow the integration of constraints on the input string x. To overcome this limitation, two recent approaches have been presented to learn discriminative non memoryless edit models. In [START_REF] Mccallum | A conditional random field for disciminatively-trained finite-state string edit distance[END_REF], McCallum et al. adapted the conditional random fields to the finite-state string edit distance. Note that this model, unlike the others, requires the use of positive and negative examples of matches of strings. More recently, in [START_REF] Boyer | Learning string edit similarities using constrained finite state machines[END_REF], the authors presented constrained state machines dedicated to the learning of edit distance satisfying domain constraints. The main difficulty of this approach is to have such background knowledge that can be expressed in the form of constraints.

Whatever the learning method we use, we have shown in this section that it is possible to learn a state machine T which models a distribution over the edit operations. As we noted before, memoryless transducers are suitable machines to deal with pattern recognition problems for whose the location of the edit operation does not play an important role. This is the case for the recognition of digits represented with Freeman codes as shown in [START_REF] Oncina | Learning stochastic edit distance: application in handwritten character recognition[END_REF]. Since we will use in this paper the same experimental framework to assess the relevance of our new edit kernel, we will consider in the rest of this paper that a memoryless transducer T is learned with the learning algorithm proposed in [START_REF] Oncina | Learning stochastic edit distance: application in handwritten character recognition[END_REF]. To ensure the self consistency of our paper, Annex 1 presents the main features of this learning algorithm that returns the machine T .

Such a machine can then be used to compute the joint or conditional edit probability between two strings. In the next section, we show how we can use T to compute the infinite sum of our string edit kernel. Rather than computing each p e (y|x), ∀y ∈ Σ * , we show that one can deduce from T two probabilistic automata modeling respectively the conditional distribution p e (y|x) and p e (y|x ′ ), given x and x ′ . Then, drawing our inspiration from the rational kernels [START_REF] Cortes | Rational kernels: Theory and algorithms[END_REF], we show that the infinite sum of Eq.11 can be efficiently calculated by calling on a composition of these two probabilistic automata.

How to compute the edit kernel over Σ * ?

While the original marginalized kernel of Eq.9 assumes that H is a finite set of variables [START_REF] Tsuda | Marginalized kernels for biological sequences[END_REF], our string edit kernel computes an infinite sum over Σ * , such that k(x, x ′ ) = y∈Σ * p e (y|x) • p e (y|x ′ ). We show in the following that (i) given two strings x and x ′ , p e (y|x) and p e (y|x ′ ) can be represented in the form of two probabilistic automata, (ii) the product p e (y|x) • p e (y|x ′ ) can be performed by intersecting the languages represented by those automata and (iii) the infinite sum over Σ * can be computed by resorting to algebraic methods.

Definitions and Notations

Definition 1. A weighted finite-state transducer (WFT) is an 8-tuple T = (Σ, ∆, Q, S, F, w, τ, ρ) where Σ is the input alphabet, ∆ the output alphabet, Q a finite set of states, S ⊆ Q the set of initial states, F ⊆ Q the set of final states, w : Q × Q × (Σ ∪ {λ}) × (∆ ∪ {λ}) → ℜ + the transition weight function, τ : S → ℜ + the initial weight function, and ρ : F → ℜ + the final weight function. For convenience, we denote w(q 1 , q 2 , x i , y j ) by w q 1 →q 2 (x i , y j ). Definition 2. A joint probabilistic finite-state transducer (jPFT) is a WFT J = (Σ, ∆, Q, S, F, w, τ, ρ) which defines a joint probability distribution over the pairs of strings {(x, y) ∈ Σ * × ∆ * }. A jPFT satisfies the following three constraints:

i) i∈S τ (i) = 1; ii) f ∈F ρ(f ) = 1; iii) ∀q 1 ∈ Q : q 2 ∈Q,x i ∈Σ∪{λ},y j ∈∆∪{λ} w q 1 →q 2 (x i , y j ) = 1.
Definition 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 y ∈ ∆ * given an input string x. We denote the transition w q 1 →q 2 (x i , y j ) in the conditional form w q 1 →q 2 (y j |x i ). A cPFT satisfies 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, ∀x i ∈ Σ : q 2 ∈Q,y j ∈∆∪{λ} (w q 1 →q 2 (y j |x i ) + w q 1 →q 2 (y j |λ)) = 1.
In the following, since our string edit kernel is based on conditional edit probabilities, we will assume that a cP F T has already been learned by one the previously mentioned methods (see Annex 1 for the details of a specific EM-based algorithm). Note that this transducer cP F T is learned only one time and then is used to compute our edit kernel for any pair of strings. For instance, a memoryless cP F T is described in Fig. 1, where Σ = ∆ = {a, b} and Q, S and F are composed of only one state of label 0. Note that if a generative learning model would have been used to learn the edit parameters, the resulting jP F T could be a posteriori renormalized into a cP F T . 0 a|a λ|a b|a a|λ b|λ λ|b a|b b|b Figure 1: Memoryless cP F T . To each transition is assigned an edit probability (not shown here for the sake of legibility) which can be used to compute the edit conditional probability of any pair of strings.

Modeling p e (y|x) and p e (y|x ′ ) by probabilistic automata

Since our kernel k(x, x ′ ) depends on two observable strings x and x ′ , it is possible to represent in the form of probabilistic state machines the distributions p e (y|x) and p e (y|x ′ ), where only y is a hidden variable.

Given a cP F T C modeling the edit probabilities and a string x, we can define a new cP F T denoted by C|x that models p e (y|x) while being driven by the specific observable string x. Definition 4. Let C = (Σ, ∆, Q, S, F, w, τ, ρ) be a cP F T that models p e (y|x), ∀y ∈ ∆ * , ∀x ∈ Σ * . We define C|x as a cP F T that models p e (y|x), ∀y ∈ ∆ * but for a specific observable x ∈ Σ * . C|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 of C1 .

• 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 applied to define the transition weight function:

-∀a ∈ ∆, ∀q 1 , q 2 ∈ Q, w ′ ([x] i ,q 1 )→([x] i+1 ,q 2 ) (a|x i+1 ) = w q 1 →q 2 (a|x i+1 ); -∀a ∈ ∆, ∀q 1 , q 2 ∈ Q, w ′ ([x] i ,q 1 )→([x] i ,q 2 ) (a|λ) = w q 1 →q 2 (a|λ).

As an example, given two strings x = a and x ′ = ab, Fig. 2(a) and Fig. 2(b) show the cP F T C|a and C|ab constructed from the memoryless transducer C of Fig. 1. Roughly speaking, C|a and C|ab model the output languages that can be respectively generated from x and x ′ . Therefore, from these state machines, we can generate output strings and compute the conditional edit probabilities p e (y|x) and p e (y|x ′ ) for any string y ∈ ∆ * . Note that since we are in an edit-based framework, the cycles outgoing from each state model the different possible insertions before and after the reading of an input symbol.

Since the construction of C|x and C|x ′ are driven by the parsing of x and x ′ in the transducer C, we can omit the input alphabet Σ. Therefore, a transducer C|x = (Σ, ∆, Q, S, F, w, τ, ρ) can be reduced to a finite-state automaton A|x = (∆, Q, S, F, w ′ , τ, ρ). The transitions of A|x are derived from w in the following way: w ′ q 1 →q 2 (a) = w q 1 →q 2 (a|b), ∀b ∈ Σ∪{λ}, ∀a ∈ ∆∪ {λ}, ∀q 1 , q 2 ∈ Q. For example, Fig. 3 Figure 2: On the left: a cP F T C|a that models the output distribution conditionally to an input string x = a; note that for the sake of legibility, state 0 stands for (λ, 0), and state 1 for (a, 0). On the right: a cP F T C|ab that models the output distribution given x ′ = ab, here again, 0 stands for (λ, 0), 1 for (a, 0), and 2 for (ab, 0).

Computing the product p e (y|x)

• p e (y|x ′ ) The next step for computing our kernel k(x, x ′ ) requires the calculation of the product p e (y|x) • p e (y|x ′ ). This can be performed by modeling the language that describes the intersection of the automata modeling p e (y|x) and p e (y|x ′ ). This intersection can be obtained by performing a composition of transducers as described by Cortes et al. in [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, we can note that the intersection of two probabilistic automata (such as those of Fig. 3(a) and 3(b)) is a special case of composition where the input and output label of transitions are identical. This intersection takes the form of a probabilistic automaton as defined below.

Definition 5. Let C be a cP F T 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 C 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 ′ ; Let us now describe how this resulting automaton can be used to compute the infinite sum of our kernel over Σ * .

• w A (q 1 ,q ′ 1 )→(q 2 ,q ′ 2 ) (a) = w q 1 →q 2 (a) • w ′ q ′ 1 →q ′ 2 (a); • τ A ((q, q ′ )) = τ (q) • τ (q ′ ) • ρ A ((q, q ′ )) = ρ(q) • ρ(q ′ )

Computing the sum over Σ *

To simplify the notations, let p(z) = p e (y|x) • p e (y|x ′ ) be the distribution modeled by an intersection automaton A = {Σ, Q, S, F, w, τ, ρ}. Let Σ = {a 1 , . . . , a |Σ| } be the alphabet.

Let M a k be the square matrix defined over Q × Q and providing the probabilities M a k (q i , q j ) = w q i →q j (a k ), ∀a k ∈ Σ. In other words, M a k (q i , q j ) is the probability that the symbol a k ∈ Σ is emitted by the transition going from state q i ∈ Q to state q j ∈ Q in A. In this context, given a string z = z 1 ...z t , p(z) can be rewritten as follows:

p(z) = p(z 1 ...z t ) = τ τ τ T M z 1 ...M zt ρ ρ ρ = τ τ τ T M z ρ ρ ρ, (12)
where τ τ τ and ρ ρ ρ are two vectors of dimension |Q| whose components are the values returned by the weight function τ (∀q ∈ S) and ρ (∀q ∈ F ), and 0 otherwise, and where

M z = M z 1 ...M zt .
¿From 12, we can deduce that:

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

z∈Σ * p(z) = ∞ i=0 τ τ τ T (M a 1 + M a 2 + ... + M a |Σ| ) i ρ ρ ρ = τ τ τ T ∞ i=0 M i ρ ρ ρ, (14)
where

M = M a 1 + M a 2 + ... + M a |Σ| . Let us replace ∞ i=0 M i by B. Therefore, B = I + M + M 2 + M 3 + . . . , (15)
where I is the identity matrix. Multiplying B by M we get

M B = M + M 2 + M 3 + . . . . (16)
Subtracting Eq.15 from Eq.16, we get:

B -M B = I ⇔ B = (I -M ) -1 . ( 17
)
Plugging Eq.17 in Eq.14, we get our kernel:

k(x, x ′ ) = y∈Σ * p e (y|x) • p e (y|x ′ ) = τ τ τ T ∞ i=0 M i ρ ρ ρ = τ τ τ T (I -M ) -1 ρ ρ ρ. ( 18
)

Tractability

Given two strings x and x ′ , we deal here with the complexity of computing k(x, x ′ ). As we just wrote, this involves the computation of an infinite sum computed by solving a matrix inversion.

Let us denote C the cP F T that models the edit probabilities, and let be t the number of states of C. We denote by n the length of the string x and by m the length of the string x ′ .

First, recall that in the case of the classical edit distance with non learned costs, the complexity is n • m for the calculation of d e (x, x ′ ).

The weighted automaton C|x describing p e (y|x) has (n + 1) • t states, and C|x ′ describing p e (y|x ′ ) has (m+1)•t states (e.g. see Fig. 3). Thus the matrix (I -M ) is of dimension (n + 1) • (m + 1) • t 2 . The computation cost of each element of this matrix linearly depends on the alphabet size |Σ|. Therefore, the computation cost of the entire matrix is n 2 • m 2 • t 4 • |Σ|. Since M is triangular, the matrix inversion (I -M ) -1 can be performed by back substitution, avoiding the complications of general Gaussian elimination. The cost of the inversion is of order of the square of the matrix dimension, that is n 2 • m 2 • t 4 . This leads to a cost of

n 2 • m 2 • t 4 • |Σ|.
Note the factor t 4 stands for the size of C that models edit probabilities. In the case of memoryless models (that will be used in the experimental study of Section 6), we have t = 1 and thus a cost reduced to

n 2 • m 2 • |Σ|.
Therefore, in the case of a conditional memoryless transducer, and for small alphabet sizes, the computation cost of our edit kernel is "only" the square of that of the standard edit distance.

Despite the advantage of triangular matrices, the algorithmic complexity remains a problem in the case of learning processes with long strings and/or large alphabet sizes. To overcome this problem, we can efficiently approximate our kernel k(x, x ′ ) by computing a finite sum only considering the strings y that belong to the learning sample. Therefore, we get

k(x, x ′ ) = y∈S p e (y|x) • p e (y|x ′ )
where S is the learning sample. Since the computation of each probability p e (y|x) requires a cost of n + |y|, the average cost of each kernel computation is

(n + m + |y|) • |S|
where |y| is the average length of the learning strings.

In conclusion, even if our kernel is a priori rather costly from a complexity point of view, it has the advantage to be usable from any transducer modeling edit probabilities, and its calculation remains reasonable. Moreover, the analysis of this kernel must also take into account the gain in accuracy it implies in a pattern recognition task. This is the aim of the next section.

Experiments

Database and Experimental Setup

To assess the relevance of using learned edit distances in the design of a new string edit kernel, we carried out some experiments. We studied the behavior of our approach on the well known NIST Special Database 3 of the National Institute of Standards and Technology, describing a set of handwritten characters. We focus on handwritten digits consisting of 128 × 128 bitmaps images. We use a learning set of about 8000 digits and a test sample of 2000 instances. Each instance is represented by a string. To code a given digit, the algorithm scans the bitmap left to right and starting from the top until encountering the first point. Then, the algorithm builds the string following the border of the character until it returns to the starting pixel. The string is constructed considering the succession of Freeman codes as described in Fig. 5.

To compare our approach with other string kernels, we used SVM-Light 6.02 [START_REF] Joachims | Making large-scale SVM learning practical[END_REF]. In order to deal with our multi-class task, we learn 10 binary SVM models M i . The model M i , ∀i ∈ {0, ..., 9}, is learned from a positive class composed by all the handwritten characters labeled i and a negative class grouping all the other digits. Then, the class of an unknown example x is determined as follows: we compute for each model M i the margin γ M i (x) and the class of x is given by argmax i γ M i (x). Obviously, a high positive value of margin γ M i (x) represents a high probability for x to be of class i.

Edit Kernels versus Edit Distance

As done by Neuhaus and Bunke [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF], our first objective was to show the interest of our edit kernel in comparison with the edit distance used in a nearest-neighbor algorithm. To achieve this task, we first used a standard edit distance d l with costs of all edit operations (deletion, insertion and substitution) set to 1. On the other hand, we used the SEDiL platform [START_REF] Boyer | Sedil: Software for edit distance learning[END_REF] to learn a matrix of edit probabilities from which one can deduce conditional edit probabilities p e (y|x) and compute a so-called stochastic edit distance d e (x, y) =log p e (y|x).

We assessed the performance of a 1-nearest neighbor algorithm using both edit distances d l and d e , and compared them with our new string edit kernel (using SVM-Light 6.02) on a test set composed of 2000 instances. Note that the conditional probabilities p e (y|x) required in our edit kernel are the same as those used in d e (x, y). Results are presented in Fig. 6 according to an increasing number of learning examples (from 100 to 8000).

We can make the following remarks:

• First, learning a stochastic edit distance d e on this classification task leads to better results than using the standard edit distance d l . Indeed, whatever the size of the learning set we use, the accuracy computed from d e is always higher.

• Second, our string edit kernel outperforms not only the standard edit distance d l , but also the stochastic edit distance d e . This clearly shows the usefulness of our string edit kernel to take advantage of powerful classifiers such as SVMs. To estimate the statistical significance of these results, comparisons between the three approaches were performed using a Student paired-t test. Table 1 presents the so-called p-values obtained while comparing our kernel with d e and d l . Using a risk of 5%, a p-value of less than 0.05 means that the difference is significant in favor of our kernel (in bold font in the table). We can note that this is always the case except for the two learning samples of size 2000 and 6000. However, these previous remarks are not sufficient to prove the relevance of our edit kernel. Indeed, as presented in Section 2, other string kernels have been proposed in the literature that can also take advantage of SVMs. How does our edit kernel behave in comparison with those state of the art string kernels? This is the matter of the next section.

Comparison with State of the Art String Kernels

In this second series of experiments, we compared our learned string edit kernel with other string kernels presented in Section 1 and 2, that is, Li & Jiang kernel [START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF], Neuhaus & Bunke kernel [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF], spectrum kernel [START_REF] Leslie | The spectrum kernel: a string kernel for svm protein classification[END_REF] and subsequence kernel [START_REF] Lodhi | Text classification using string kernels[END_REF] 2 . Even if these last two kernels have already been introduced in section 1, let us briefly present them and precise values of parameters we used in our experiments. The spectrum kernel considers a feature space of dimension N k where k denotes the number of substrings over Σ * of length smaller than a parameter p. In this space, each example x is represented by the vector of the number of occurrences of substrings. Thus, the spectrum kernel of x and y is trivially computed using the inner product between the two string representations. In our experiments, the parameter p has been fixed to 2.

The subsequences gap weighted kernel extends the spectrum kernel considering subsequences instead of substrings. Thus, this kernel is able to take into account long term dependencies information using sets of letters with gaps. The same parameter p is used to limit the size of subsequences. Moreover, a weight λ is defined in order to give less importance to subsequences with large gaps. In our experiments, λ has been set to 2 which leads in our case to the best results with this kernel. Fig. 7 shows the results we obtained with the different mentioned kernels. We can first note that the best results are obtained with edit distance based kernels. As we did before, Table 2 presents the p-values of the Student paired-t test. Except the kernel of Li & Jiang, our edit kernel significantly outperforms all the other string kernels. Second, even if their behaviors are quite similar, we can note that our kernel almost always outperforms that of Li & Jiang (even if the difference is not statistically significant). It is also important to note in this analysis that the parameter t required in the Li & Jiang kernel is very difficult to tune. In [START_REF] Li | A class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas[END_REF], the authors indicated that the best results were obtained with a value t = 0.00195. In order to optimally tune this parameter, we tested many values of t (from t = 0 to t = 0.2). Figure 8 shows that the best performances are obtained on 2000 test strings with a value of 0.02, while using t > 0.1 leads to a dramatic drop of the accuracy. Therefore, we used t = 0.02 throughout our comparison.

Conclusion

The common way to use the edit distance in classification tasks consists in exploiting it in a classical k-Nearest-Neighbor algorithm. Recently, machine learning techniques have been used to automatically learn the probabilities of the edit operations to capture background knowledge and so improve the performance of the edit distance. On the other hand, in order to take advantage of the widely used framework of Support Vector Machines, recent works have been done to derive edit kernels from the edit distance. In this article, we suggested to embed the advantages of both approaches by designing a learned string edit kernel. We experimentally showed that such a strategy allows significant improvements in terms of classification accuracy.

A first perspective of our work is to improve the algorithmic complexity of our kernel. A crucial point in its calculation concerns the size of the product automaton allowing the computation of p e (y|x) • p e (y|x ′ ). To reduce this size, a possible solution would consist in simplifying the original conditional transducers C|x and C|x ′ by only considering the most probable transitions and states. A simplification of C|x and C|x ′ would have a direct impact on the dimension of the matrix we have to invert.

A second natural perspective of this work relies on the extension of our method to the elaboration of tree edit kernels. Indeed, some recent papers dealing with the learning of tree edit distance in the form of stochastic models [START_REF] Bernard | Learning probabilistic models of tree edit distance[END_REF][START_REF] Boyer | Learning metrics between tree structured data: Application to image recognition[END_REF] would allow us to generalize our method to the learning of more complex structured data-based edit kernels.

Annex 1

This annex describes the way to learn the parameters of a conditional memoryless transducer as proposed in [START_REF] Oncina | Learning stochastic edit distance: application in handwritten character recognition[END_REF].

Let us suppose that we have a learning set S of pairs of strings (x, y) and for the sake of simplicity that the input and the output alphabets are the same, noted Σ. Let Σ * be the set of all finite strings over Σ. Let x ∈ Σ * be an arbitrary string of length |x| over the alphabet Σ. In the following, unless stated otherwise, symbols are indicated by a, b, . . . , strings by u, v, . . . , z, and the empty string by λ. R + is the set of non negative reals. Let f (•) be a function, from which [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). The expectation-maximization 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.

  (a) and 3(a) are the resulting automata deduced from the cP F T C|a and C|ab of Fig.2(a) and 2(b).

Figure 3 :

 3 Figure 3: The transducers C|a and C|ab represented in the form of automata.

Fig. 4 Figure 4 :

 44 Fig.4 describes the intersection automaton of automata of Fig.3(a) and 3(b).

Figure 5 :

 5 Figure 5: A digit and its string representation.

1 -

 1 NN with d e 1-NN with d l Number of learning samples Accuracy on 2000 test strings

Figure 6 :

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

Figure 7 :

 7 Figure 7: Comparison of our edit kernel with the state of the art edit kernels on a handwritten digit recognition task.

  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 letter a. The aim of this annex is to show how we can automatically learn the function c from the learning sample S. The different values c(b|a), ∀a ∈ Σ ∪ {λ}, b ∈ Σ ∪ {λ} represent the parameters of the memoryless machine T . These parameters are trained using an EM-based algorithm that calls on two auxiliary functions called forward and backward.The conditional probability p : Σ * × Σ * → [0, 1] of the string y given an input one was a x (noted p(y|x)) can be recursively computed by means of an auxiliary function (forward) α : Σ * × Σ * → R + as:α(y|x) = [1] x=λ∧y=λ + [c(b|a) • α(y ′ |x ′ )] x=x ′ a∧y=y ′ b + [c(λ|a) • α(y|x ′ )] x=x ′ a + [c(b|λ) • α(y ′ |x)] y=y ′ b .Using α(y|x), we get,p(y|x) = α(y|x) • γ,where γ is the probability of the termination symbol of a string (note that γ and c(λ|λ) are synonyms). In a symmetric way, p(y|x) can be recursively computed by means of an auxiliary function (backward) β : Σ * × Σ * → R + as:β(y|x) = [1] x=λ∧y=λ + [c(b|a) • β(y ′ |x ′ )] x=ax ′ ∧y=by ′ + [c(λ|a) • β(y|x ′ )] x=ax ′ + [c(b|λ) • β(y ′ |x)] y=by ′ .And we can deduce that,p(y|x) = β(y|x) • γ.Both functions can be computed in O(|x| • |y|) time using a dynamic programming technique and will be used in the following to learn the current function c. In this model a probability distribution is assigned conditionally to each input string. Then y∈Σ * p(y|x) ∈ {1, 0} ∀x ∈ Σ * . The 0 is in the case the input string x is not in the domain of the function.It can be shown that the normalization of each conditional distribution can be achieved if the following conditions over the function c and the parameter γ are fulfilled, γ > 0, c(b|a), c(b|λ), c(λ|a) ≥ 0 ∀a ∈ Σ, b ∈ Σ (19) b∈Σ c(b|λ) + b∈Σ c(b|a) + c(λ|a) = 1 ∀a ∈ Σ (20) b∈Σ c(b|λ) + γ = 1 (21)

  Given an auxiliary (|Σ| + 1) × (|Σ| + 1) matrix δ, the expectation step aims at computing the values of δ as follows: ∀a ∈ Σ, b ∈ Σ,δ(b|a) = (xax ′ ,yby ′ )∈S α(y|x) • c(b|a) • β(y ′ |x ′ ) • γ p(yby ′ |xax ′ ) δ(b|λ) = (xx ′ ,yby ′ )∈S α(y|x) • c(b|λ) • β(y ′ |x ′ ) • γ p(yby ′ |xx ′ ) δ(λ|a) = (xax ′ ,yy ′ )∈S α(y|x) • c(λ|a) • β(y ′ |x ′ ) • γ p(yy ′ |xax ′ ) δ(λ|λ) = (x,y)∈S α(y|x) • γ p(y|x) = |S|.The maximization step allows us to iteratively deduce the current edit costs.

Table 1 :

 1 Statistical comparison between our edit kernel (EK) and a (learned or standard) Edit Distance (ED). Using a risk of 5%, a p-value of less than 5E-02 means that the difference is significant in favor of our kernel

	Learning set size	1000	2000	3000	4000	5000	6000	7000	8000
	EK vs learned ED	1E-02	6E-02	2E-02 2E-02	2E-02	9E-02	3E-02 3E-01
	EK vs standard ED	6E-06 4E-04 1E-03 3E-03 2E-03 8E-03 2E-03 3E-02

Table 2 :

 2 Statistical comparison between our edit kernel (EK) and the state of art string kernels. Using a risk of 5%, a p-value of less than 5E-02 means that the difference is significant in favor of our kernel.

	21

t

Figure 8: Tuning of the parameter t in Li & Jiang kernel.

This specific notation is required to deal with non memoryless cP F T .

We did not use the LA kernel which is too specific (it searches for remote homologies between biological sequences by achieving local alignments) to be easily compared in this series of experiments with the state of the art string kernels.

ARA Marmota research project.