When kids get interested in helping their mom or dad in the kitchen, one of the first things they want to do is to help bake a cake. It's a good choice because it is easy, direct and follows the same basic steps every time, with variations that can make it more complicated. Knowing the basics lets you approach making a cake from scratch with great confidence. For this step-bystep example, a chocolate cake is on the menu.

Trainer: Gamra Semia

Step 1: Get Ready Before you begin baking, grease and flour the pans you are using. These could be 8-inch rounds, 9-inch rounds, 13-by 9-inch rectangular or a Bundt pan. Then preheat the oven to the temperature as directed in the recipe so that it's ready to bake when you are.

Trainer: Gamra Semia

Greasing and Flouring Baking Pans

Trainer: Gamra Semia

Step 2: Melting Chocolate or Other Ingredient Preparation

It's important to have all of the ingredients prepared before making the batter. Many cake recipes call for melted chocolate, so you should do that before beginning to mix up the batter. To melt chocolate, you can use a microwave or a saucepan on the stovetop, the traditional method. There are several ways to melt chocolate. Other ingredient preparation could include chopping nuts or slicing of lemon or orange zest, among

Step 8: Put Batter in the Pans

Carefully divide the batter between two round cake pans or add to one pan if you are using a rectangular or Bundt pan. Gently tap the pans on the counter to even the tops. If necessary, use a spatula to smooth the tops before baking.

Trainer: Gamra Semia Trainer: Gamra Semia

Step 9: Bake and Cool the Cakes Bake the cakes according to the time and temperature in the recipe directions. Remove from the oven and cool on a rack for 10 minutes or as directed in your recipe. Remove the cakes from the pans and cool completely on wire racks before frosting the cake. Make sure the top layer's top is not top down on the rack.

Otherwise, there will be grid lines on the top of the cake.

Trainer: Gamra Semia Trainer: Gamra Semia

Step 10: The Finished Product Homework:

Think about a typical cake home made that is specific to your family or to the Tunisian pastry and prepare the steps of the recipe for your friends .

The best one will be done in the pastry Lab with your trainer.

Trainer: Gamra Semia


Julien Bourdaillet

Stéphane Huet

Philippe Langlais

Guy Lapalme

TransSearch: from a bilingual concordancer to a translation finder

come

This paper describes the enhancement of the web-based bilingual concordancer TransSearch1 [START_REF] Macklovitch | TransSearch: A Free Translation Memory on the World Wide Web[END_REF]. While subscribers of the system are mainly professional translators, a recent study of their query logs exhibits that TransSearch is used to answer difficult translation problems [START_REF] Macklovitch | TransSearch: What are translators looking for?[END_REF]. Among the 7.2 million queries submitted to the system over a six-year period, 87% contain at least two words. Few queries are single words present in bilingual dictionaries, or bona fide terms which can be found in terminology banks. In fact, the users mainly search for: idiomatic expressions such as in keeping with (query frequency: 716 times), in light of (544 times), or look forward to (539 times); verbs or adjectives that govern a preposition such as consistent with (743 times), or focus on (472 times); and adverbials or adjectives whose precise translation depends on context like as such (1195 times), at this time (913 times), or overarching (417 times).

Figure 1 shows the result page of the current version of the application, the user having submitted the query in keeping with. After searching inside a TM based on the English and French sentences pairs from the Canadian Hansards, TransSearch returned those pairs in which the query occurs. The English sentences are displayed along with their French translation. Whereas the English words matching the query can be easily highlighted (here in bold), their corresponding French translation is much harder to identify.

Currently, this identification is left to the user, and has to be repeated over many sentence pairs in order to discover the set of available query translations in the TM. Indeed, sentences are not displayed in an order related to the diversity of translations occurring in the TM, but in the reverse chronological order of dates of the documents they were extracted from. Although professional translators are usually quick to spot the appropriate translation in context, this task remains very timeconsuming. Relying on the user to find the corresponding translation not only restricts the benefit and the audience of TransSearch, but it also prevents its use in other natural language processing applications.

In fact this highlights a severe limitation shared by many current CAT tools: the fact they mainly rely on sentence-level matching to exploit their TM. This major drawback can be addressed with word alignment techniques, which are commonly used in statistical machine translation (SMT). A recent attempt has been made by Callison-Burch et al. (2005) who proposed the Linear B2 system where translations of a user's query are presented in context. Unfortunately, this system's evaluation is very limited, as discussed in Section 6. In this paper, we take inspiration from this work while attempting to explore one step further in that direction.

The term translation spotting, coined by [START_REF] Véronis | Evaluation of Parallel text Alignment Systems -The Arcade Project[END_REF] and relabeled here as transpotting, is defined as the task of identifying the target language word-tokens that correspond to a given source language query in a pair of sentences known to be mutual translations. We call transpot the target word-tokens automatically associated with a query in a given pair of sentences. For instance in Figure 2, conforme à and respecte are 2 out of 213 distinct transpots displayed to the user for the query in keeping with.

The first contribution of this paper is to propose several transpotting methods. Further, once translations have been identified using these methods, it becomes possible to merge those translations that are identical or at least very close (if they differ only by a plural inflection for example). This allows TransSearch to display each translation to the user only once, while keeping the possibility of consulting their contexts of occurrence. The list of translations is sorted in decreasing order of their frequency in the TM, according to the hypothesis that the most frequent translations are the most likely ones. They are displayed in a web interface, loosely inspired by the one pioneered by Linear B. CSS and Javascript are used to selectively display translation pairs. TransSearch has now become a translation finder as shown in Figure 2. The list of query translations found in the TM is presented to the user who can browse the associated pairs of sentences by clicking on each translation. Both the query and its translation are highlighted in all pairs of sentences.

The second contribution of this paper is to propose an evaluation framework for this relatively unusual work in MT research. We rely on a large reference corpus to conduct a series of experiments. According to the goals of the system, we define two tasks, for which we propose different metrics, to compare several translation spotting methods and post-processings. Finally, a human evaluation shows the relevance of the system's results. The top rectangle in the center column, in which the query is highlighted in the source sentence only, corresponds to the output of the current TransSearch (see Figure 1). The steps below it illustrate the processes described in this article. The first step, transpotting, identifies transpots in the target sentences, before bad transpots are filtered. This set of transpots can optionally be refined with relevance feedback information. The resulting transpots are merged so that close variants of a same translation form a single group. The groups displayed in the lowest rectangle represent the final result (see Figure 2).

••••••••••••• ---- •••••••••••••• ---- •••••••••••••• ---- •••••••••••••• ---- •••••••••••••• ---- •••••••••••••• ---- Translation Memory •••••••••A•••• ---- ••••••••A••••• ---- •A•••••••••••• ---- ••••••••••••A• ---- Bilingual concordancer •••••••••A•••• -x-- ••••••••A••••• --y- •A•••••••••••• ---x ••••••••••••A• -z-- •••••••••A•••• -x-- ••••••••A••••• --y- •A•••••••••••• ---x •••••••••A•••• -x-- ••••••••A••••• --y- •A•••••••••••• ---x •••••••••A•••• -x-- •A•••••••••••• ---x ••••••••A••••• --y- x 2 •••••••••A•••• -x-- •A•••••••••••• ---x y 1 ••••••••A••••• --y-
Figure 3 acts as a roadmap for the paper since it summarizes the steps we developed to identify and display query translations. Each step is associated with a corresponding section in the paper. Section 2 describes methods for spotting translations in context, and Section 3 introduces post-processing steps to enhance and display the results.

Then, the evaluation process is presented: Section 4 describes the evaluation tasks we defined, the corpora, as well as the training and tuning setups; Section 5 reports the results of our experiments. Section 6 compares this work with related work, while Section 7 concludes and explores further perspectives.

Transpotting

The first idea that comes to mind for transpotting a query is to use a bilingual dictionary, in which translations for multi-word expressions are often difficult or awkward to find. To overcome these limitations, we can rely on word alignment models which are commonly used in SMT. As suggested by Simard (2003b), IBM models can be used to compute the maximum a posteriori alignment, or Viterbi alignment, of a sentence pair. Then, the target words aligned to the query can be considered as the transpot.

Since IBM models are the bread-and-butter of today's SMT systems, we first describe a baseline model making use of IBM model 2. As we discuss in Section 6.1, several alternatives to these models have been recently developed but none of them emerged as a new standard for word alignment. Further, many of them rely on external resources such as manually annotated bitexts or syntactic parsers. This conflicts with two important capabilities of the current TransSearch version: the consideration of several language pairs, and the indexing of corpora in different domains. The implementation of these capabilities in the new TransSearch version prevents the use of models that rely on external resources. Therefore, we decided to focus our study on two widespread models: Hidden Markov Models (HMMs) and phrase-based models.

Further, in order to enhance the classical use of IBM models, Simard (2003b) suggests taking into account a contiguity constraint for transpotting. In keeping with this work, we also analyze the use of this constraint and present two algorithms based on IBM model 2 and HMM.

Transpotting using IBM models

Formally, given a source sentence S = s 1 ...s n and a target sentence T = t 1 ...t m in translation relation, an IBM-style alignment a = a 1 ...a m connects each target token to a source one (a j ∈ [1, n]) or to the socalled null token which accounts for untranslated target tokens, and which is arbitrarily set to the source position 0 (a j = 0).

Several word alignment models are introduced and discussed in Brown et al. (1993). They differ by the expression of the joint probability of a target sentence and its alignment, given the source sentence.

The IBM model 2 is expressed by:

p(t m 1 , a m 1 |s n 1 ) = p(m|n) m j=1 p(t j |s a j ) × p(a j |j, m, n) (1)
where p(m|n) is the length distribution, the first term inside the product is the transfer or lexical distribution and the second one is the alignment distribution. Given this decomposition of the joint probability, the so-called Viterbi algorithm finds the alignment â maximizing the quantity p(a m 1 |t m 1 , s n 1 ):

âj = arg max i∈[0,n] [p(t j |s i ) × p(i|j, m, n)] (2)
This computation can be done efficiently in O(mn). Then the transpot of the query is obtained by returning the words t j aligned with the words of the query according to â. It is well known that IBM model 2 is a weak translation model. An easy way to enhance this transpotting method consists in using a more accurate lexical distribution. To this end, we use the transfer distribution resulting from the training of an IBM model 4, which allows us to enhance significantly the transpotting method, while it does not induce higher cost at runtime. This method is named IBM2 in the remainder of the paper. The IBM model 4 lexical distribution is also used for all transpotting methods described below, except the method of Section 2.2. A natural way to improve this baseline transpotting method is to make use of richer word alignment models. The introduction of a firstorder alignment dependency to the IBM model 2 gives the HMM alignment model first proposed by [START_REF] Vogel | HMM-Based Word Alignment in Statistical Translation[END_REF]. It is expressed by:

p(t m 1 , a m 1 |s n 1 ) = m j=1 p(t j |s a j ) × p(a j |a j-1 , n) (3)
The computation of the Viterbi alignment based on HMM can be done in O(mn 2 ) with dynamic programming by maximizing the quantity Q(i, m) computed using the following recurrence:

Q(i, 1) = p(t 1 |s i ) Q(i, j) = p(t j |s i ) max i ∈[1,n] [p(i|i , n) × Q(i , j -1)] (4) with i ∈ [1, n], j ∈ [2, m].
In the following, this transpotting algorithm is named HMM.

Since IBM models are asymmetrical, a common trend for improving their predictions consists in combining models trained in both translation directions (English-French and French-English). Several operators can be used, such as intersection, union or grow-diag-final, as defined in [START_REF] Och | A Systematic Comparison of Various Statistical Alignment Models[END_REF]. We tested the use of symmetrized HMMs for transpotting with intersection and union operators; these transpotting methods are called HMM-bi-inter and HMM-bi-union respectively in the following. Those algorithms have a complexity in O(mn 2 ). Because the transpotting method described in Section 2.2 relies on the combination of HMM models with the grow-diag-final operator, we did not test further this operator with the models described in this section.

Phrase-based transpotting

As proposed by Callison-Burch et al. (2005), phrase-based models can also be used by a translation search engine. The Moses toolkit produces an SMT system relying on a phrase table that combines HMM alignments using the grow-diag-final operator [START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF].

From the SMT system produced by Moses, we are only interested in the phrase table that records the word alignment knowledge. In this work, we implemented a simple strategy in which the transpots returned by the system are those present in the phrase table for the query and which belong to the target sentence. The resulting set can be sorted using some combination of the scores associated with each phrase pair. With Moses, these scores are phrase translation probabilities and lexical weightings in both translation directions. The combination we retained in our study has been tuned on development data, as described in Section 4.4.

A suffix array structure offers a convenient way of indexing the huge phrase table resulting from our large training corpus of 8.3 million sentence pairs (Callison-Burch et al., 2005). In the following, we name this approach PBM.

Transpotting using IBM models and a contiguity constraint

Whereas selecting all the target tokens aligned with the query is a straightforward transpotting method, this strategy is error prone and a better transpotting algorithm deserves to be considered. Figure 4 illustrates a common error that appears when using IBM2 for transpotting.

In this example, the identified transpot for the query in keeping with is a non-contiguous phrase composed of mesure and conforme à. Although it may be necessary to choose a non-contiguous phrase, contiguous tokens in the source language sentence tend to be aligned to contiguous tokens in the target language. As mentioned in Simard (2003b), this suggests that it is relevant to integrate a contiguity constraint inside the transpotting algorithm. This idea, which shares some similarity with the phrase extraction technique described in [START_REF] Vogel | PESA: Phrase Pair Extraction as Sentence Splitting[END_REF], can be expressed as follows.

For each target token pair (j 1 , j 2 ) ∈ [1, m] × [1, m], j 1 < j 2 , two Viterbi alignments are computed: one between the phrase t j 2 j 1 and the query s i 2 i 1 , and one between the remaining material in the two sentences si

2 i 1 ≡ s i 1 -1 1 s n i 2 +1 and tj 2 j 1 ≡ t j 1 -1 1 t m j 2 +1
. This method finds the translation of the query according to:

t ĵ2 ĵ1 = argmax (j 1 ,j 2 ) p(a j 2 j 1 |s i 2 i 1 , t j 2 j 1 ) × p(ā j 2 j 1 |s i 2 i 1 , tj 2 j 1 ) (5)
Whereas the first term of this equation ensures the contiguity constraint by forcing the query s i 2 i 1 to be aligned to a contiguous segment t j 2 j 1 , the second term forces each token of tj 2 j 1 to be aligned to a source token outside the query.

With IBM model 2

Implementing the contiguity constraint for IBM model 2 can be naively achieved by computing m 2 Viterbi alignments, one for each pair (j 1 , j 2 ), which corresponds to a complexity in O(m 3 n). Fortunately, because the source query is given, it is possible to compute more efficiently this solution by introducing three tables corresponding to three states of the alignment procedure: before the transpot, inside the transpot and after the transpot. These tables are computed by dynamic programming:

Q before (1) = max i ∈[i 1 ,i 2 ] P (t 1 |s i ) Q inside (1) = max i∈[i 1 ,i 2 ]∪{0} P (t 1 |s i ) Q after (1) = 0 Q before (j) = max i ∈[i 1 ,i 2 ] {Q before (j -1)p(t j |s i )p(i|j, m, n)} Q inside (j) = max i∈[i 1 ,i 2 ]∪{0} {max(Q before (j -1), Q inside (j -1))× p(t j |s i )p(i|j, m, n)} Q after (j) = max i ∈[i 1 ,i 2 ] {max(Q inside (j -1), Q after (j -1))× p(t j |s i )p(i|j, m, n)} (6)
before start inside end after

Figure 5. Automaton with the 5 allowed states for the transpotting method based on HMM and the contiguity constraint: before the transpot (j < j1), start of the transpot (j = j1), inside the transpot (j1 < j < j2), end of the transpot (j = j2) and after the transpot (j > j2).

with i ∈ [0, n], j ∈ [2, m].
Let us note that Q inside (j) and Q after (j) require a second maximization operator to choose the best scores obtained for the token (j -1) in the two previous allowed states. The tables are computed efficiently in O(mn), while the best transpot corresponds to max(Q inside (m), Q after (m)). This method will be referred to as C-IBM2 in the remainder of the article.

With HMM

The contiguity constraint can rely on HMMs as well. Whereas the naive implementation gives a complexity in O(m 3 n 2 ), a careful implementation allows a computation in O(mn 2 ). This exploits the existence of five states defined according to the current value of j with respect to hypothesized j 1 and j 2 (see Figure 5). Thus, the table Q(i, j), required to compute a Viterbi alignment based on an HMM, can be duplicated for each of the five states and computed according to the principle described in Section 2.3.1. For example, let us consider the table Q end (i, j) of the state reached at the end of the transpot. It is built from the tables Q start (i, j) and Q inside (i, j), associated with the two previous states allowed in the automaton. Its value are computed as follows:

Q end (i, 1) = 0 Q end (i, j) = p(t j |s i ) max i ∈[i 1 ,i 2 ] {p(i|i , n)η(i , j -1)} if i ∈ [i 1 , i 2 ] 0 otherwise (7) with η(i , j -1) = max(Q start (i , j -1), Q inside (i , j -1)), i ∈ [1, n], j ∈ [2, m].
The best transpot is finally chosen as the one that maximizes Q(i, m) among the four accepting states. We name this method C-HMM.

In both directions

The transpotting methods incorporating a contiguity constraint described in Section 2.3 can be improved by combining models in both translation directions. For this, the transfer probabilities of the French-English and English-French models are combined, using some combination function tuned on the development data as described in Section 4.4. This results in a bidirectional transpotting method we call C-HMM-bi for HMM, with a complexity remaining in O(mn 2 ).

Among all transpotting methods we described in Section 2 and according to the experimental assessment presented in Section 5, C-HMM-bi obtains the best performance in the context of our application.

Post-processing

Queries that occur frequently in the TM receive numerous translations using the transpotting methods described above. For example, Table I illustrates the many transpots returned by C-IBM2 for the query on behalf of. Some transpots (those marked with a star) are clearly wrong (e.g. de), others (in italics) are only partially correct (e.g. part de). Also it appears that many transpots are very similar (e.g. au nom de and au nom du, where du is the contracted form of de le).

Since we want to present to the user a list of translations corresponding to the query, strategies must be devised for dealing with some errors resulting from the transpotting phase. We estimate that a user will focus on the 10 first translations presented, so we want to provide as many correct and diversified translations as possible at the top of the result page.

The number of translations to discard can be significant: using the transpotting algorithms described above, we observed that roughly between 20 % and 40 % of suggested translations are erroneous. Most of them have few occurrences and appear at the end of the list, nevertheless even the top results can contain a few errors. For example, in Table I the fourth translation de is incorrect while it was found 136 times.

We investigated three avenues to enhance the results of the transpotting phase: filtering erroneous transpots (Section 3.1), merging variants of the same canonical translation (Section 3.2), and the adaptation of pseudo-relevance feedback for transpotting (Section 3.3).

Filtering bad transpots

A simple way to detect and filter bad transpots is to rely on supervised learning. To this end, we analyzed a set of queries and their transpots, as computed by the C-IBM2 transpotting method (our best transpotting algorithm available at the moment), and manually annotated the transpots as "good" or "bad". This corpus (see Section 4.2.3) was used to train a number of classifiers designed to distinguish good transpots from bad ones.

We experimented with several popular classifiers:3 a support vector machine (SVM), commonly used in supervised learning (Cristianini and Shawe-Taylor, 2000); a multi-layer perceptron with one level of hidden neurons (Bishop, 1995); AdaBoost using a one level decision tree as weak classifier [START_REF] Freund | Experiments with a New Boosting Algorithm[END_REF]; a bagging algorithm using a decision tree as base classifier (Breiman, 1996); and a random forest algorithm (Breiman, 2001). Besides, these five classifiers were combined through a linear combination by averaging over their posterior class probabilities [START_REF] Kittler | On Combining Classifiers[END_REF].

We computed three groups of features for each example, that is, each query/transpot pair (q, t). The first group is made up of features related to the size (counted in words) of q and t, with the intuition that they should be related. The second group gathers various alignment scores computed with word alignment models (Viterbi scores using IBM models 1 & 2 in both directions; min, max and average likelihood scores inside Viterbi alignments, etc.). The last group gathers clues that are more linguistically flavored, among which the ratio of grammatical words (like for, although, the) in q and t, or the number of prepositions and articles. In total, each example is represented by 45 numerical features.

Merging variants

Once erroneous transpots are filtered out, there usually remain many translations for a given query. For instance, for the query on behalf of, our best classifier identified 213 bad transpots among 824 candidates. Some of the remaining transpots are very similar and are not interesting for the user (see Table I). This phenomenon is particularly acute in French with its numerous conjugated forms of verbs. Still many transpots differ only by punctuation marks or by a few grammatical words.

We propose merging two translations which are different inflectional forms of the same sequence of canonical words. For instance, au nom du and au nom des from Table I will be considered as similar, since du and des are contractions of de + le and de + les respectively, where le and les are definite articles. Furthermore, we noticed that displaying translations that differ only by a few grammatical words or punctuation marks, like de la part de and part de is often redundant for the user, so these are combined as well.

This clustering process must be fast in order to be used online. For this, each translation is first associated with a key: the grammatical words are ignored (in this case: determiners, prepositions, conjunctions, pronouns and auxiliary verbs); then each word of the translation is replaced by all the lemmas which can generate it, according to a lemma dictionary. For translations containing only grammatical words, the key consists of the words themselves. This avoids clustering all grammatical word sequences into a single group, hence de and dans remain in different clusters. This first step does not permit disambiguation of translations according to their lemmas. For instance, part de which can be the verb partir (in English, leave) or the noun part (in English, part) is associated with the key {partir, part}. To merge this translation with another one that does not exhibit a part-of-speech ambiguity (e.g. partira (in English, will leave) which is associated with the key {partir}),

k ← k 1 S ← h 1 [k 1 ]
foreach k 2 of the keys of h 2 sorted in decreasing order of transpotting frequency do if

k 1 ∩ k 2 = ∅ then k ← k 1 ∩ k 2 S ← h 1 [k 1 ] ∪ h 2 [k 2 ] remove k 2 from h 2 break end end h 2 [k] ← S end Figure 6
. Variant merging process where the function lemmas gives the set of all the possible lemmatized sequences of a translation according to a dictionary. these keys are, in a second step, disambiguated according to a greedy process that computes the intersections of the sets of lemmatized sequences. In order to avoid disambiguation errors, frequent transpots are considered first since they are usually correct. Figure 6 shows the algorithm of this variant merging process.

Pseudo-relevance feedback

We studied a third post-processing stage on top of the two aforementioned ones. We investigated exploiting the fact that many sentence pairs containing the query share the same set of translations which may be helpful to refine transpotting results. The transpotting methods described in Section 2 align each sentence pair individually -as it is done in SMT. It is therefore interesting to know whether the alignment In this section, we present two methods that release the usual independence assumption between sentence pairs. For this, the information provided by the translations found during a first transpotting stage is used to refine the results during a second transpotting stage. These methods are similar in principle to the relevance feedback concept developed in the information retrieval (IR) domain [START_REF] Rocchio | Relevance Feedback in Information Retrieval[END_REF].

Usual relevance feedback techniques rely on human judgments for identifying relevant documents returned during a first retrieval stage; this information is used for improving a second stage. A variant of this method, known as pseudo-relevance feedback, does not require user annotation but assumes that the top ranked documents returned during the first stage are relevant (Croft and Harper, 1979). In our case, a first transpotting phase is carried out in which the most frequent transpots are considered as the most relevant. This information is then used to improve a second transpotting stage.

We noticed that frequent transpots tend to be good translations of a query. This is illustrated in Table II for the query way of life. The correct translation mode de vie clearly occurs more frequently than the other transpots. The next candidates are also relevant translations, such as façon de vivre or style de vie. At the end of the list, many transpots, especially those occurring only once, are incorrect (e.g. réalité dans nos) or correspond to variants of the most frequent translation (e.g. au coeur du mode de vie). We now present two methods we designed according to this principle.

Procedural relevance feedback

Based on the observation that frequent transpots are likely to be good ones, the set of the most frequent transpots is first built for each query, then rare transpots are replaced by an element of this set. Each rare transpot found in a given sentence is replaced by the most frequent transpot occurring in the sentence. If no frequent transpot occurs in the sentence, the transpot is left unchanged. We call this method procedural relevance feedback, or PRF for short. The decision to consider a transpot as rare is based on two parameters α and β, which respectively set an absolute and a relative threshold. For example, the values α = 5 and β = 0.02 consider as rare transpots those occurring less than 5 times and in less than 2 % of the retrieved sentence pairs. These two parameters are optimized on a development corpus (see Section 4.2.2).

Statistical relevance feedback

The previous relevance feedback method has two drawbacks: it can only replace a transpot with a more frequent one, and it only uses the results provided by the transpotting method from a static word alignment model. We propose a statistical relevance feedback method, named SRF, which attempts to improve the statistical word aligner. For each query, a local statistical transfer model is computed using the transpots found during the first stage, with the hope of improving transpotting during the second stage. In order to do so, we build for each query a parallel corpus made of the query and all the transpots found during the first stage. We assume that this short parallel corpus contains information which is more specific to the translation of the query than the very large training corpus used to build the main transfer model. Let us note that we do not compute a local alignment model: since the parallel corpus for each query is small with respect to the bitext used to train the global model, a local alignment model would only damage the global alignment model.

The specific corpus is used to compute the probabilities p loc (t j |s i ) of a local transfer model which are linearly interpolated with the prob-abilities p glob (t j |s i ) of the global transfer model initially used by the transpotting algorithm. Because the local bitext is very short, training the local model is very fast. This idea shares commonalities with the cache model used in language modeling [START_REF] Kuhn | A Cache-Based Natural Language Model for Speech Recognition[END_REF]. Since the specific corpus only provides information about the use of the words of the query, the modifications of the transfer model are limited to those words. Therefore, the new transfer distribution used during the second transpotting stage becomes:

p(t j |s i ) = λp glob (t j |s i ) + (1 -λ)p loc (t j |s i ) if s i ∈ q p glob (t j |s i ) otherwise ( 8
)
where λ is a coefficient optimized on a development corpus.

Experimental setup

We now describe the metrics we designed and the data sets we gathered for the evaluation. Then we present the training and the tuning procedures used for the transpotting algorithms.

Metrics

The new TransSearch prototype achieves two related tasks that deserve their own evaluation: the transpotting and the translation tasks.

On one hand, the transpotting task corresponds to the use of Trans-Search as a bilingual concordancer: as shown in Figure 2, for each sentence pair the application highlights the words that form the transpot of the query. On the other hand, the translation task corresponds to the use of TransSearch as a translation finder where the system presents the transpots corresponding to a user's query.

Although these two tasks are strongly related, their outputs are different: for the transpotting task subsequences of sentence pairs are highlighted, while for the translation task groups of translations are produced. Further, the transpotting task only depends on the quality of the transpotting algorithms, whereas the translation task relies also on the post-processing. We now describe the metrics we designed to evaluate each task.

Transpotting task

The transpotting evaluation concerns the ability of an algorithm to identify the reference transpot in a target sentence. This task can be evaluated after the transpotting stage, and also after the pseudorelevance feedback stage which aims at correcting erroneous transpots in the sentence pairs retrieved for a user query.

Following the previous work of Simard (2003b), the relevance of a transpot r for a given sentence pair (s, t) can be measured in terms of precision and recall when comparing r with the reference transpot r obtained from a bilingual lexicon (see Section 4.2.2). Scores are computed as follows:

recall(s, t)

= |LCS(r, r)|/|r| precision(s, t) = |LCS(r, r)|/|r| (9)
where LCS(r, r) returns the longest common contiguous subsequence of tokens shared by r and r, and |r| denotes the length of string r. Thus, transpots that are only partially correct are given some credit depending on the length of overlap with the reference. This reflects the capacity of a transpotting algorithm to identify where the transpot is located in the target sentence. This capacity is very useful for the user: it avoids the need to search for the translation in the whole target sentence, even if an algorithm identifies only a grammatical word of the reference transpot.

The previous scores are determined at the level of sentence pairs and must therefore be averaged to get recall and precision ratios at the corpus level. To do so, the scores are first averaged for each query/reference transpot pair, then averaged over all the pairs of query/reference transpots for each query, and finally averaged over all the queries. These three levels of average reduce the evaluation bias toward queries associated with numerous sentence pairs with respect to others having only a few occurrences in the TM. They also prevent the scores from giving more frequent reference translations a too important weight with respect to rare ones in the TM. Finally, precision and recall can be combined into an F-measure score in the usual way: F-measure = 2 × recall × precision recall + precision (10)

Translation task

The translation evaluation reflects the ability of an algorithm to find the different translations of a given query in the retrieved pairs of sentences. This task is essential for TransSearch since the results must be displayed within a limited amount of space, which requires them to be both correct and diversified. This task can be evaluated after all the processing stages, because they either find transpots that can be directly turned into lists of transpots (transpotting and pseudorelevance feedback stages) or are specifically designed to improve the quality of the displayed translations (filtering and merging stages). The evaluation of this task is based on the fact that returning a list of translations for a submitted query is similar to what happens in a classical IR system, which retrieves a list of documents for a given query. Like in the IR domain, we expect the translations returned for a query to be ordered by relevance, with the most interesting at the beginning of the list.

The mean average precision (MAP) measure, now commonly used in IR [START_REF] Manning | Introduction to Information Retrieval, Chapt. Evaluation in Information Retrieval[END_REF], provides a single-number measure of quality across recall levels which gives a higher weight to top levels. In our case, M AP k is established at the rank k by comparing the top k translations with the ones available for each query in a reference lexicon (see Section 4.2.2). The M AP k score averages the precision scores obtained at each rank, up to k, that corresponds to a relevant translation. Formally, let x j denote the j th translation returned in the list, and Y the set of reference translations. Then, M AP k is defined as the average of the following score computed for each query:

1 |Y| k i=1 1 x i ∈Y i j=1 1 x j ∈Y i ( 11
)
where 1 p equals 1 when p is true and 0 otherwise.

The MAP only manages two levels of relevance for translations: right or wrong, while measures handling a degree of relevance can also be very useful. Indeed, among relevant translations, some can be more interesting than others: a rare translation which occurs in the TM but not in a bilingual dictionary can be considered as more interesting than a common translation. In order to handle the relevance of translations, we rely on the Q-measure which associates documents with different relevance scores ranging from 0 to 1 [START_REF] Sakai | New Performance Metrics Based on Multigrade Relevance: Their Application to Question Answering[END_REF]. We apply this metric to our context by considering lists of translations as lists of documents. Formally, the Q-measure associates each translation x with a relevance score rel(x) ∈ [0, 1]. Y is defined as the set of reference translations y annotated with a relevance score rel(y) ∈ ]0, 1]. An optimal list of translations is built by ordering Y in decreasing order of relevance; the j th element being denoted by y j . The Q-measure at rank k is defined as the average of the following score computed for each query:

1 |Y| k i=1 1 x i ∈Y i j=1 1 x j ∈Y .(rel(x j ) + 1) i + i j=1 rel(y j ) (12)
The Q-measure corrects the incapacity of the weighted MAP measure [START_REF] Kando | Information Retrieval System Evaluation using Multi-Grade Relevance Judgments: Discussion on Averageable Single-Numbered Measures[END_REF] to rank two document lists which differ only by some document beyond the |Y| th position in the list. To this end, the constant 1 is added in the numerator, and i in the denominator. Otherwise, ratios would remain constant beyond the |Y| th position.

In Section 5, we associate a relevance score to each transpot according to its frequency in the TM; this allows the comparison of different transpotting methods through the Q-measure.

Corpora

Translation memory

The largest TM used in TransSearch comes from the Canadian Hansards, a collection of the official proceedings of the Canadian Parliament. For our experiments, we used an in-house sentence aligner [START_REF] Langlais | A System to Align Complex Bilingual Corpora[END_REF] to align 8.3 million French-English sentence pairs extracted from the 1986-2007 period of the Hansards. Then, this bitext was indexed with Lucene4 to form our TM.

Evaluation corpus

To study the behavior of our methods on "real" queries, we extracted from the log file of the current TransSearch the 5,000 most frequent English queries that were submitted to the system during the 2001-2007 period. The manual evaluation of the transpots suggested by a transpotting method is a long and often difficult task. To avoid this inspection, we built automatically a large reference corpus using a bilingual phrase lexicon we collected over various projects. Among the 5,000 queries that have an entry in this lexicon, 284 queries were used for development purposes (dev) and 2,074 were kept apart for testing our methods (test). For each query, up to 5,000 sentence pairs were retrieved from the TM.

The goal of the transpotting task is to highlight the words of the target sentence that translate the query. This requires a reference corpus composed of sentence pairs annotated with a reference transpot. Among the 5,000 pairs of sentences retrieved for each query of dev and test, we kept only those whose source part contains the query and target part contains one of its translations in the bilingual lexicon. This resulted in a set containing 180,000 pairs of sentences for dev and 1.4 million pairs of sentences for test.

On the other hand, the translation task requires a list of translations produced by a transpotting method to be compared with a list of reference translations. The reference translations are those occurring in the bilingual lexicon, which contains an average of 3.6 translations per query for dev and 3.9 for test. We are aware that the limited amount of translations might bias our evaluation. Nevertheless, this bias is uniform for all the transpotting methods.

Classifier training corpus

In order to train the classifiers described in Section 3.1, four human annotators were asked to identify bad transpots among those proposed by one of our transpotting algorithms. We developed an ad-hoc webbased interface that displayed a query with its corresponding transpots. The annotator indicated whether each transpot was appropriate or not. Annotating the query/transpot pairs without their contexts of occurrence allows a relatively fast annotation process, around 40 seconds per query, but leaves some difficult cases to annotate (more details are given in Section 5.5). For instance, for the query in keeping with, conforme à is straightforward to annotate, but others such as dans le sens de or tenir compte de gave annotators a harder time since both are contextual translations which are valid in some specific contexts.

We ended up with a set of 531 queries that have an average of 22.9 transpots each, for a total of 12,144 annotated examples. We computed the Fleiss' inter-annotator agreement (Fleiss et al., 2003) and observed a 0.76 kappa score, which suggests a high degree of agreement [START_REF] Landis | The Measurement of Observer Agreement for Categorical Data[END_REF]. When annotations differ, the reference finally considered is randomly selected among the judgments done by the annotators.

Model training setups

All the transpotting methods described in Section 2 use IBM models. To obtain them, we ran Giza++ [START_REF] Och | A Systematic Comparison of Various Statistical Alignment Models[END_REF] on our 8.3 million sentence pairs TM with the default parameter set. We used the following sequence of models with five training iterations for each: 1, 2, HMM, 3 and 4. This provided us the transfer tables corresponding to the IBM model 4 which we used for all transpotting methods in place of their usual transfer table (except for PBM which does not use a lexical transfer table). This enhances the weakest transpotting methods, such as IBM2, making them stronger baselines.

To build the phrase table required by the PBM transpotting method, we applied Moses on the TM with the default parameter set and the sequence of models described above.

Transpotting algorithm tuning

The two transpotting methods C-HMM-bi and PBM have to be tuned. For this, we made use of the dev corpus described in Section 4.2.2 and optimized these methods according to the F-measure score for the transpotting task described in Section 4.1.1.

The C-HMM-bi transpotting method relies on a function that combines transfer probabilities of models trained in both directions. Several combinations were tried and the one weighting the French given English model three times as much as the other model obtained the best results.

The PBM method requires a score associated with each phrase pair in order to sort them. For each phrase pair, Moses produces five scores which can be combined to obtain the required single score. We tried several score combinations and obtained the best results using the same weights as C-HMM-bi for the French given English scores (phrase translation probability and lexical weighting) and the English given French scores, while the last (constant) score is ignored.

Experiments

In this section, we first compare the transpotting algorithms described in Section 2 and analyze the impact of the post-processing presented in Section 3. Finally, we report the results of a human evaluation for three variants of our prototype and provide guidelines for integrating the methods in the production version of TransSearch.

Evaluation of the transpotting algorithms

Using the test corpus, we evaluated the transpotting algorithms described in Section 2 according to the transpotting and translation tasks defined in Section 4.1.

Transpotting task

Table III shows the results in percentage related to the transpotting task. Without much surprise and despite its use of IBM model 4 transfer tables, IBM2 is the weakest transpotter. At the opposite end of the range, we observe that PBM and C-HMM-bi outperform the other algorithms, the latter slightly outperforming the former. A closer look at these figures shows that using C-HMM-bi induces a considerable increase of precision with respect to HMM-bi-inter and PBM. Whereas aligning all target words to the query gives a high recall, only the correct words have to be aligned to the query to obtain both high recall and precision. This means that a transpotting method has to guess the correct boundaries of the transpot with high accuracy. The results in Table III suggest that C-HMM-bi is more acute at finding these boundaries and giving a correct transpot.

The same phenomenon can be observed when comparing IBM2 to C-IBM2. The introduction of the contiguity constraint described in Section 2.3 increases recall by almost 1 absolute point and precision by almost 9 points. Further, since both HMM and C-IBM2 introduce a sort of neighborhood constraint with respect to IBM2, it is interesting to note that the improvement of F-measure induced by the contiguity constraint is almost 2 points more than the one induced by the previous word alignment constraint. This empirically validates the interest of this constraint and confirms the observations made by Simard (2003b).

Translation task

Table IV reports the results for the translation task. MAP scores are computed at ranks 5, 10, and globally for the whole list of translations. The C-HMM-bi clearly outperforms all other transpotting methods for this task for each of the three MAP scores. When comparing this method with PBM, the MAP scores are between 1.5 and 2 points higher.

The MAP metrics evaluate a list of transpots on two dimensions: the order of transpots in the list (the closer a correct translation is to the top of the list, the higher the score), and the number of retrieved correct transpots (the higher this number, the higher the score). In order to evaluate the contribution of the two dimensions, we computed Q-measure scores in which the first dimension is made explicit by the weights associated with reference translations.

As described in Section 4.1.2, Q-measure can be framed in terms of a weighted MAP. The relevance score of a translation is set to the inverse of its frequency in the TM, with the intuition that most of the systems will discover the frequent translations but only few of them will discover the less frequent ones, rendering them more interesting. Finally, as each reference translation has a relevance score, they can be ordered decreasingly in order to constitute the list of y j s defined in Section 4.1.2. This allows the computation of the Q-measure scores presented in Table IV. Comparing PBM and C-HMM-bi shows that the latter still obtains better scores, but two phenomena appear. On one hand, the differences between the two methods' QM 5 and QM 10 scores are lower than those between their M AP 5 and M AP 10 scores. On the other hand, the difference between their QM largely surpasses the one between their M AP . The first phenomenon means that the two methods tend to suggest a similar list of transpots at the beginning of the list, and have therefore the same behavior according to the first dimension described above. On the contrary, the second phenomenon clearly states that C-HMM-bi retrieves a significantly larger number of reference translations than PBM does, making C-HMM-bi more suitable for the translation task.

The queries used to constitute the test corpus have a wide range of occurrence frequency inside the TM. In order to study how this acts upon the quality of the results, we measured the MAP score for rare queries. Since only 9 queries of test occur in at most 10 sentence pairs, a larger corpus was specifically designed. From the log file of TransSearch we selected the 200 top queries that occur at most 10 times in the TM and that have an entry in our bilingual lexicon.

The results on this new corpus exhibit a significantly lower M AP 10 score for PBM (36.6 %) with respect to C-HMM-bi using SRF (52.7 %) or not (52.3 %). This is explained by two phenomena. First, 54 out of 200 rare queries do not have an entry in the phrase table. Second, the number of translations in the phrase table is low for rare queries, which leads PBM to suggest 1.23 translations on average for the 10 sentences of each query, whereas C-HMM-bi suggests 2.77 translations on average. This observation suggests that a fruitful strategy for improving PBM on low frequency queries would be to consider subsequences of the query while searching in the phrase table.

Following these results, we concentrate on C-HMM-bi and PBM in the remainder of the experiments.

Filtering removes noise

Bad transpot classification

As described in Section 3.1, we trained various classifiers to identify spurious transpots from three kinds of feature sets. All these classifiers plus two challenging baselines are evaluated according to the ratio of correctly classified instances (CCI). Since in our application we are interested in filtering out bad transpots, precision, recall and F-measure scores related to this class are computed as well.

We report in Table V the figures computed using a 10-fold stratified cross-validation procedure. The simplest baseline (line 1) classifies all instances as good; this useless filter has a CCI ratio of 61.8 %. A more sensible baseline-that we engineered after we investigated the usefulness of different feature sets-classifies as bad the transpots whose ratio of grammatical words is above 0.75. It is associated with a CCI ratio of 78.8 % (line 2).

Among the five classifiers we tried, Bagging obtains the highest CCI ratio (86.1 %) and the best F-measure (80.2 %). In order to study the contribution of each feature set (size, IBM, and grammatical features), this classifier was trained using each set separately. This shows that IBM features are clearly the most significant since adding the two other feature sets only slightly improves the performance. The linear combination of the five classifiers gives a small increase of the CCI ratio (86.4 %) and of F-measure (81.0 %).

Filtering using classifiers

Using the best classifier according to the previous tests, i.e. the linear combination of five classifiers, we evaluated on the test corpus the benefit of discarding bad transpots. Since the filtering process is only relevant when displaying the list of translations, this evaluation was performed for the translation task only.

The first line of Table VI recalls the MAP scores computed for the PBM and C-HMM-bi methods and presented in Table IV. The second line gives the results obtained after filtering bad transpots. The comparison of these two lines shows that the three MAP scores are improved by around 1 absolute point for PBM and by around 0.5 points for C-HMM-bi. Filtering bad transpots causes the rank of good ones to decrease, which improves MAP according to the first dimension described in Section 5.1.2, i.e. the rank of reference translations retrieved.

When we manually check the transpot lists returned by both systems before and after filtering, we observe a significant difference at the end of the lists: a lot of bad transpots such as grammatical words or incomplete transpots have been removed. This makes bad transpot filtering a very useful post-processing for removing noise and improving the results presented to the user.

Merging variants increases diversity

As mentioned in Section 3.2, a significant number of translations that remain after filtering spurious ones are variants of the same canonical translation. Thus, merging these variants is necessary to avoid displaying many translations that are closely related.

The last line of Table VI reports the results when applying our merging process, after filtering bad transpots with the best classifier found in Section 5.2. Because merging variants applies only to the translation task, only MAP scores are presented. When comparing the quality of the top translations obtained before (line 2) and after (line 3) merging, it appears that a large gain of almost 10 points is induced by this postprocessing for both PBM and C-HMM-bi, and for the three MAP scores. This implies that the reference translations are proposed earlier in the transpot list when grouping similar variants. Therefore, the interest for the user is twofold: the noise is reduced and more relevant translations are proposed at the top of the list, which increases the diversity of suggested translations.

Relevance feedback slightly improves transpots

To our disappointment, the PRF method described in Section 3.3.1 did not improve the quality of the results for both tasks. A manual inspection shows that PRF discards numerous incorrect translations but introduces more noise than new translations among the top ones.

Using instead the SRF method with our best transpotting method C-HMM-bi5 slightly improves the F-measure for the transpotting task (Table VII, column 1) and the MAP for the translation task (Table VII, columns 2, 3 and 4). Although SRF mainly acts upon rare transpots, interestingly the substitution of transpots tends to promote better translations among the top responses, like the correct translations qualité de vie and façon d'être in case of Table II.

Manual human assessment

In order to obtain a qualitative feedback upon the translations suggested by our systems, further experiments were conducted with human assessment.

Protocol

Seven judges were asked to rate the relevance of translations proposed by three transpotting methods: PBM, C-HMM-bi and C-HMM-bi postprocessed by SRF. For each query, the union of the top 10 results output by these methods was displayed simultaneously and in a random order to each rater. They had to label the quality of each translation with one of the four tags: "clearly good", "fairly good", "quite bad" or "clearly bad". Two sets of 100 queries were built for annotation: Q freq is made of frequent queries occurring in at least 1,000 sentence pairs of the TM, while Q rare corresponds to rare queries occurring in at most 5 sentence pairs.

Each query of the two data sets was annotated by three judges. Each of the four classes was associated with a relevance score ranging from 0 (for "clearly bad") to 3 (for "clearly good"). Finally, each pair (query, translation) was associated with the average of the three judges' scores.

This annotation turned out to be more complicated than the one we conducted for evaluating erroneous transpots (see Section 3.1). This was confirmed by the Fleiss inter-annotator agreement; kappas of 0.46 and 0.60 were obtained for Q freq and Q rare respectively, which suggests a moderate agreement beyond chance [START_REF] Landis | The Measurement of Observer Agreement for Categorical Data[END_REF]. However, the differences in annotations usually occur between tags close in the ranking scale.

In order to compare the top k results provided by the three methods for each query q, the discounted cumulative gain DCG(q, k) is computed as follows:

DCG(q, k) = k m=1 2 R(q,m) -1 log 2 (1 + m) (13)
where R(q, m) is the average relevance score set by the raters for the m th translation of q suggested by one of the three methods to evaluate. This metrics summarizes the relevance score associated with several translations of a given query and reduces the weight of each response with its rank. It is often used in IR for situations of non-binary notions of relevance [START_REF] Manning | Introduction to Information Retrieval, Chapt. Evaluation in Information Retrieval[END_REF].

Results

In order to measure the quality perceived by the judges, we averaged the scores provided by the three annotators for the top translations returned by each transpotting method. With a value around 2.7 (for a maximum value of 3.0), this score turns out to be very high, for the three methods and on both Q freq and Q rare . As expected, this score decreases when computed from the translations returned at a lower Table VIII. Comparison of 3 transpotting systems on Q freq and Q rare using the DCG metrics (in %). Each cell at line i and column j returns the number of queries, out of 100, in which the method of line i is better than the method of column j. rank, which indicates that ordering translations with regard to their frequency in the TM is correct. Nevertheless, the score is still higher than 2.0 for the translations selected at rank 5 for the three systems, and higher than 1.7 when considering the following ranks.

In order to obtain a more fine-grained comparison between systems, DCG was computed from the top 10 translations output by each system. Table VIII reports the number of queries in which one method outperforms another. For example, the cell displayed at line 1 and column 2 means that for 45 queries of Q freq PBM obtained a better DCG than C-HMM-bi. The three methods do not have the same behavior for some queries, especially rare ones. Indeed, PBM gave no output for 8 out of 100 queries of Q freq at rank 10 and for 37 out of 100 queries of Q rare while C-HMM-bi+SRF was able to suggest a translation for all these queries. Consequently, for a fair comparison between PBM and the two other systems, only the queries where PBM gave at least one response were considered.

The results of Table VIII support the equivalence of performance obtained by C-HMM-bi with or without SRF. They outperform each other for around the same number of queries: 27 vs. 23 on Q freq , and 2 vs. 4 on Q rare . On the other hand, the comparison of PBM and C-HMM-bi shows more differences. C-HMM-bi outperforms PBM for 51 queries on Q freq and for 26 queries on Q rare , when the contrary only happens for 45 and 3 queries respectively. This significant improvement of C-HMM-bi with respect to PBM is mainly explained by the higher number of translations retrieved per query on average for Q rare , which tends to improve DCG.

Methods retained for the new TransSearch

The numerous evaluations we conducted exhibit the domination of two approaches: PBM and C-HMM-bi. The transpotting algorithm comparison reveals a significant improvement in F-measure when taking into account a contiguity constraint. The enhancement observed in terms of MAP and the preference of human judges towards C-HMM-bi leads us to choose this transpotting method for the new TransSearch system.

Besides, our experiments show the interest of filtering bad transpots and merging close translation variants in order to improve the relevance of the top translations. Therefore, we included these two postprocesses in TransSearch. As far as the pseudo-relevance feedback is concerned, we decided to ignore it since human evaluation revealed its limited effect to improve the results.

Related work

Word alignment

Since the seminal works of Brown et al. (1993), IBM word alignment models have become the de facto standard in the field of SMT, thanks in part to the open source toolkit Giza++. Several extensions of these models have been proposed in the literature. [START_REF] Toutanova | Extensions to HMM-Based Statistical Word Alignment Models[END_REF] introduced modifications to the standard HMM alignment model [START_REF] Vogel | HMM-Based Word Alignment in Statistical Translation[END_REF], among which the use of POS tags for smoothing transfer probabilities. [START_REF] Moore | Improving IBM Word Alignment Model 1[END_REF] proposed three modifications to the standard EM algorithm used to train IBM model 1, in particular the smoothing of transfer probabilities: it corrects the tendency of this model to align rare source words with too many target words. This issue is taken into account more elegantly by the joint training of asymmetrical word alignment models (one model per translation direction) proposed by [START_REF] Liang | Alignment by Agreement[END_REF]. Deng and Byrne (2005) also proposed an extension of the HMM alignment model which compares similarly to IBM model 4, while being more tractable to train.

More recently, Fraser and Marcu ( 2007) defined a generative model designed for non-consecutive many-to-many word alignment. Words are decomposed into head and non-head words and linked according to syntactic dependencies. Then head words are aligned. The model is trained either in an unsupervised way close to the training of IBM Model 4, or in a semi-supervised way. For the latter training procedure, the authors report interesting results in alignment metrics.

Another line of research investigated the use of a word-aligned bitext in order to improve word alignment. Cherry and Lin (2003) proposed a model that takes source and target sentences as given and maximizes the probability of links between source and target words, while IBM models maximize the probability that a source sentence generates a target sentence and their alignment. Their model requires the labeling of dependency relations between target words using a syntactic parser [START_REF] Lin | Dependency-Based Evaluation of MINIPAR[END_REF]. Following this work, different supervised discriminative models have been proposed [START_REF] Ittycheriah | A Maximum Entropy Word Aligner for Arabic-English Machine Translation[END_REF][START_REF] Moore | Improved Discriminative Bilingual Word Alignment[END_REF]Blunsom and Cohn, 2006). Various features are computed in order to choose the best sentence alignment. The weights of these features are optimized using the word-aligned bitext. These models report good results according to word alignment metrics such as alignment error rate (AER).

While all these models are very promising, IBM, HMM and phrasebased models remain the mainstream models used by the SMT community. None of the models described above imposed itself as a new standard for word alignment. The use of either a small supervised wordaligned bitext or a syntactic parser is not part of the TransSearch project's road map. Both resources run up against maintainability issues for a commercial application such as TransSearch.

All experiments presented in this paper use the French-English language pair with the Canadian Hansards corpus, but our commercial application is expected to process other language pairs as well as corpora related to other domains (legal, medical, technical, etc.). A model relying on a word-aligned bitext would require us to label manually a new bitext for each new domain corpus. Without this manual annotation, it is unsure how such models would behave in the long-run. Further, a model relying on a parser would require the use of new parsers for each language pair.

In the future, we intend to compare some of the aforementioned generative models to our C-HMM-bi approach. Since this approach handles bidirectionality plus a contiguity constraint, and given the results presented in this paper, we are confident of its robustness and we do not expect significant differences compared to the aforementioned models.

Bilingual concordancers

As mentioned in Section 1, some recent systems try to take advantage of word alignment in order to develop new functionalities, but with only a limited evaluation of their results which does not render a clear judgment on their performance. [START_REF] Wu | TotalRecall: A Bilingual Concordance for Computer Assisted Translation and Language Learning[END_REF] developed a web-based English-Chinese concordancer that highlights the transpots in pairs of sentences in which the query occurs. The tool was mainly designed for second language learn-ers who can submit queries which are single words, phrases, expressions or even full sentences. The alignment at the word or phrase level relies on the spotting of specific part-of-speech patterns, learned from the idioms and the collocations of an English-Chinese dictionary. Phrases matching these patterns are extracted from the aligned sentences and selected according to a cross-linguistic statistical association criterion. Callison-Burch et al. (2005) proposed the Linear B system that is currently available for some language pairs between Arabic, Chinese and 7 European languages. The authors use bitexts to compute a phrase table for each language pair. The phrase table is indexed using a suffix array data structure that permits the efficient search of phrase pairs. When the user submits a query, all sentence pairs whose source sentence contains the query are returned. Then the phrase table enables the discovery of the target phrase that best matches in each target sentence according to the given query. In fact, this system is very similar to our PBM method. Contrarily to TransSearch, this system does not incorporate a classifier to filter spurious transpots or a method to group similar translation variants. Besides, a limited evaluation was conducted with 120 queries and a TM of 50,000 sentence pairs. [START_REF] Kockaert | Term-Based Context Extraction in Legal Terminology : A Case Study in Belgium[END_REF] describe a TM system for legal phraseology and terminology in the Belgian national languages (Dutch, French and German). Their experimental tool is based on bilingual resources (dictionaries, lists linking word forms to their lemmas, and stop lists) and cognates to align fragments of bilingual texts. Their automatic alignment method is used to approximate the position of the translation of a query inside sentence pairs of the TM.

Conclusion

This paper describes the enhancement of the bilingual concordancer TransSearch using a word alignment functionality. Interestingly, this transforms the nature of the application: it now behaves like a translation finder with a concordancer feature. The application goes beyond a bilingual dictionary thanks to its ability to translate phrases while providing their contexts of occurrence.

We studied and compared several algorithms for the word alignment task we call transpotting. The methods relying either on bidirectional HMMs enhanced with a contiguity constraint or on the standard Moses phrase table obtain the best overall results. While results are quite similar for the transpotting task, the former method provides better results for the translation task, i.e. when considering the whole application as a search engine.

Three post-processing methods for improving transpotting results have been studied: a supervised classifier filters out bad translations efficiently; merging close translation variants avoids presenting the user redundant translations and improves the relevance of the results; using pseudo-relevance feedback corrects some transpotting errors, although it only allows for minor improvement.

Most of the experiments were performed using about 2,000 queries and a very large TM of 8.3 million sentence pairs. This amount of data ensures confidence in the results, themselves confirmed by the manual evaluation which takes into account the users' point of view.

The work presented in this paper is implemented in the new version of TransSearch developed in a joint partnership between the authors' laboratory and Terminotix. 6 For the time being, this version gives access to the Canadian Hansards and the Canadian Federal Court Judgments corpora. Only the French-English language pair is available, but the implementation of more language pairs is under consideration. We are confident that users will benefit from this new CAT tool and that it will create new opportunities for its application.

Several of the methods we integrated in our CAT tool could be used in SMT. The C-HMM-bi method is used for transpotting in this paper, but it would be suitable for use in building a phrase table by aligning source phrases of reasonable length, instead of focusing on user queries, in order to find interesting target translations for any phrase. This method could also compute a feature based on the contiguity constraint and associated with each phrase pair in a phrase table. The classifiers we used for filtering could also be used for pruning a phrase table, which turns out to improve translation quality [START_REF] Johnson | Improving Translation Quality by Discarding Most of the Phrasetable[END_REF]. Pseudo-relevance feedback considers the occurrences of a phrase as sharing common information rather than being independent. Therefore, it might be relevant to integrate it to the phrase acquisition process of an SMT model similar to that of [START_REF] Marcu | A Phrase-Based, Joint Probability Model for Statistical Machine Translation[END_REF].

Finally, the methods we propose could be used to design a phrasebased TM system which could amount to a full SMT system (Simard, 2003a;[START_REF] Owczarzak | Wrapper Syntax for Example-Based Machine Translation[END_REF][START_REF] Langlais | EBMT by Tree-Phrasing[END_REF]. After the submission of a text to translate to the system, its source sentences should be properly segmented. For this, a chunker may be used: it would build segments quite similar to user queries studied in this paper and the resulting phrases could be searched in the TM. Because the system would process phrase pairs, rather than sentence pairs in a classical TM, its translation capability would be dramatically enhanced.

Figure 1 .

 1 Figure 1. English sentences, along with their French translation, where the query in keeping with occurs in the current version of the bilingual concordancer Trans-Search. The query is highlighted in the English sentences, but the user has to search its translations in the French sentences. This makes the discovery of the different translation possibilities more difficult (adaptées à, conforme aux, détonne and conformément à for the four displayed sentences), and forces the user to scroll down the page in order to read other sentences while searching for further translation material.

Figure 2 .

 2 Figure 2. Results for the query in keeping with with the new version of Trans-Search. This version displays on the left hand side the whole range of translations found in the TM. For the first suggested translation, conforme à, four out of the 203 sentence pairs containing a variant of this translation (see the merging process described in Section 3.2) are displayed in context. The highlighted translations are HTML links to their occurrence in the original Hansards session.

Figure 3 .

 3 Figure3. Processing steps for transforming the bilingual concordancer Trans-Search into a translation finder. Each rounded rectangle depicts a set of translation pairs (sentences are stylized as dots for source and lines for target) returned from a query in the TM. The query is indicated by a capital letter in the source and the corresponding transpot, by a lower-case letter. The top rectangle in the center column, in which the query is highlighted in the source sentence only, corresponds to the output of the current TransSearch (see Figure1). The steps below it illustrate the processes described in this article. The first step, transpotting, identifies transpots in the target sentences, before bad transpots are filtered. This set of transpots can optionally be refined with relevance feedback information. The resulting transpots are merged so that close variants of a same translation form a single group. The groups displayed in the lowest rectangle represent the final result (see Figure2).

Figure 4 .

 4 Figure 4. Example of word alignment generated by an IBM model 2 that leads to an erroneous transpot for the query in keeping with.

  of a given query can be enhanced by taking into account the alignment of this query in other sentence pairs containing it.

Table I .

 I Subset of the 824 different transpots retrieved for the query on behalf of. Those marked with a star are erroneous, those in italics are only partially correct.

	Transpot	Frequency
	au nom de	1424
	au nom du	763
	au nom des	683
	de	136
	. . .

Table II .

 II Subset of the 226 different transpots retrieved for the query way of life by the transpotting algorithm during the first stage.

	Transpot	Frequency
	mode de vie	898
	mode de vie des	42
	façon de vivre	36
	style de vie	32
	niveau de vie	8
	manière de vivre	5
	de vie	5
	mode de vie de	5
	. . .
	qualité de vie	3
	façon d'être	3
	. . .
	vie rurale	2
	réalité dans nos	1
	à la société	1
	au coeur du mode de vie	1
	. . .

Table III .

 III The results (in %) of the various transpotting algorithms for the transpotting task on test.

		Recall Precision F-measure
	IBM2	76.7	65.8	70.8
	HMM-bi-inter	68.2	77.4	72.5
	HMM	80.3	69.1	74.3
	C-IBM2	77.6	74.4	76.0
	HMM-bi-union	85.0	70.4	77.0
	C-HMM	80.4	75.6	77.9
	PBM	81.7	77.4	79.5
	C-HMM-bi	80.9	78.3	79.6

Table IV .

 IV The results (in %) of the various transpotting algorithms for the translation task on test. M AP k and QM k give scores at rank k, otherwise the whole transpot list is considered

		M AP5 M AP10 M AP QM5 QM10 QM
	IBM2	33.7	36.1	38.8	23.5	27.9	46.3
	HMM-bi-inter	30.4	32.8	35.3	21.0	25.6	38.8
	HMM	35.2	37.7	40.3	24.7	29.5	48.0
	C-IBM2	34.1	36.6	39.5	24.3	29.7	49.6
	HMM-bi-union	34.8	37.3	39.7	24.3	28.9	46.1
	C-HMM	35.0	37.4	40.3	24.7	29.6	50.8
	PBM	33.9	36.6	39.3	24.3	29.6	45.3
	C-HMM-bi	35.5	38.1	41.1	25.1	30.3	51.2

Table V .

 V Performance (in %) of different classifiers for identifying bad transpots.

				Bad transpots
	Classifier	Features	CCI precision recall	FM
	Baseline: all good		61.8	0.0	0.0	0.0
	Baseline: gram. ratio > 0.75		78.8	89.4	50.5	64.5
		size	73.9	74.9	46.6	57.4
	Bagging	IBM grammatical 80.2 85.8	85.4 93.1	75.4 51.6	80.1 66.4
		all	86.1	86.7	74.7	80.2
	SVM		84.3	82.4	75.0	78.5
	Multilayer Perceptron AdaBoost	all	85.7 85.6	86.5 86.4	73.6 73.8	79.5 79.6
	Random Forest		85.4	84.0	76.0	79.8
	Linear Combination		86.4	86.0	76.6	81.0

Table VI .

 VI The results of two transpotting algorithms for the translation task on test after different post-processing stages.

			PBM			C-HMM-bi
		M AP5 M AP10 M AP M AP5 M AP10 M AP
	no post-processing	33.9	36.6	39.3	35.5	38.1	41.1
	filtering	34.9	37.8	40.3	35.7	38.5	41.4
	filtering + merging	44.3	47.3	49.5	45.5	48.7	51.3

Table VII .

 VII The results (in %) on test obtained using the SRF method and the C-HMM-bi algorithm. All the translations are filtered and merged.

		F-measure M AP5 M AP10 M AP
	before SRF	79.6	45.5	48.7	51.3
	after SRF	80.1	45.6	48.8	51.3

TransSearch is available commercially at http://www.tsrali.com MTJournal.tex; 14/09/2010; 14:20; p.2 TransSearch: from a bilingual concordancer to a translation finder

http://linearb.co.uk/ MTJournal.tex; 14/09/2010; 14:20; p.3

MTJournal.tex; 14/09/2010; 14:20; p.4

MTJournal.tex; 14/09/2010; 14:20; p.5

MTJournal.tex; 14/09/2010; 14:20; p.6

MTJournal.tex; 14/09/2010; 14:20; p.7

MTJournal.tex; 14/09/2010; 14:20; p.8

MTJournal.tex; 14/09/2010; 14:20; p.9

MTJournal.tex; 14/09/2010; 14:20; p.10

MTJournal.tex; 14/09/2010; 14:20; p.11

Available in the Weka framework at http://www.cs.waikato.ac.nz/ml/wekaMTJournal.tex; 14/09/2010; 14:20; p.12

MTJournal.tex; 14/09/2010; 14:20; p.13

J. Bourdaillet, S. Huet, P. Langlais, G. Lapalme

MTJournal.tex; 14/09/2010; 14:20; p.14

MTJournal.tex; 14/09/2010; 14:20; p.15

MTJournal.tex; 14/09/2010; 14:20; p.16

MTJournal.tex; 14/09/2010; 14:20; p.17

MTJournal.tex; 14/09/2010; 14:20; p.18 TransSearch: from a bilingual concordancer to a translation finder

MTJournal.tex; 14/09/2010; 14:20; p.19

http://lucene.apache.orgMTJournal.tex; 14/09/2010; 14:20; p.20

MTJournal.tex; 14/09/2010; 14:20; p.21

MTJournal.tex; 14/09/2010; 14:20; p.22

MTJournal.tex; 14/09/2010; 14:20; p.23

MTJournal.tex; 14/09/2010; 14:20; p.24

MTJournal.tex; 14/09/2010; 14:20; p.25

MTJournal.tex; 14/09/2010; 14:20; p.26

In order to keep the same transpotting algorithm in the two stages of relevance feedback, we did not apply the SRF to PBM.MTJournal.tex; 14/09/2010; 14:20; p.27

MTJournal.tex; 14/09/2010; 14:20; p.28

MTJournal.tex; 14/09/2010; 14:20; p.29

MTJournal.tex; 14/09/2010; 14:20; p.30

MTJournal.tex; 14/09/2010; 14:20; p.31

MTJournal.tex; 14/09/2010; 14:20; p.32

http://www.terminotix.comMTJournal.tex; 14/09/2010; 14:20; p.33

MTJournal.tex; 14/09/2010; 14:20; p.34

MTJournal.tex; 14/09/2010; 14:20; p.35

MTJournal.tex; 14/09/2010; 14:20; p.36

Acknowledgements

The authors would like to thank Fabrizio Gotti and Elliott Macklovitch for their contribution to this work and Jacques Steinlin for programming the user interface of the new prototype. We also thank Gilles Gamas and Micheline Cloutier from Terminotix who supported this research via their contribution to a Collaborative Research and Development (CRD) grant from the Natural Science and Engineering Research Council (NSERC) of Canada. References Bishop, C. M.: 1995, Neural Networks for Pattern Recognition. New York, NY, USA: Oxford University Press. Blunsom, P. and T. Cohn: 2006, 'Discriminative Word Alignment with Conditional Random Fields'. In: 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics (COLING-ACL). Sydney, Australia, pp. 65-72. Breiman, L.: 1996, 'Bagging Predictors'. Machine Learning 24(2), 123-140. Breiman, L.: 2001, 'Random Forests'. Machine Learning 45(1), 5-32. Brown, P., V. Della Pietra, S. Della Pietra, and R. Mercer: 1993, 'The Mathematics of Statistical Machine Translation: Parameter Estimation'. Computational Linguistics 19(2), 263-311. Callison-Burch, C., C. Bannard, and J. Schroeder: 2005, 'A Compact Data Structure for Searchable Translation Memories'. In: 10th European Conference of the Association for Machine Translation (EAMT). Budapest, Hungary, pp. 59-65. Casacuberta, F., J. Civeria, E. Cubel, A. L. Lagarda, G. Lapalme, E. Macklovitch, and V. Enrique: 2009, 'Human interaction for high-quality machine translation'. Communications of the ACM 52(10), 135-138. Cherry, C. and D. Lin: 2003, 'A Probability Model to Improve Word Alignment'. In: 41st Annual Meeting of the Association for Computational Linguistics (ACL). Sapporo, Japan, pp. 88-95. Cristianini, N. and J. Shawe-Taylor: 2000, An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge, UK: Cambridge University Press. Croft, W. and D. Harper: 1979, 'Using Probabilistic Models of Information Retrieval without Relevance Information'. Journal of Documentation 35(4), 285-295. Deng, Y. and W. Byrne: 2005, 'HMM Word and Phrase Alignment for Statistical Machine Translation'. In: Conference on Human Language Technology and Empirical Methods in Natural Language Processing (HLT-EMNLP). Vancouver, British Columbia, Canada, pp. 169-176. Fleiss, J. L., B. Levin, and M. C. Pai: 2003, Statistical Methods for Rates and Proportions. New York, NY, USA: John Wiley & Sons, 3rd edition. Foster, G., P. Isabelle, and P. Plamondon: 1997, 'Target-Text Mediated Interactive Machine Translation'. Machine Translation 12, 175-194. Fraser, A. and D. Marcu: 2007, 'Getting the Structure Right for Word Alignment: LEAF'. In: Joint Conference on Empirical Methods in Natural Language Process-