Fuzzy-match repair using black-box machine translation systems: what can be expected? (2016)

Abstract: Computer-aided translation (CAT) tools often use a translation memory (TM) as the key resource to assist translators. A TM contains translation units (TU) which are made up of source and target language segments; translators use the target segments in the TU suggested by the CAT tool by converting them into the desired translation. Proposals from TMs could be made more useful by using techniques such as fuzzy-match repair (FMR) which modify words in the target segment corresponding to mismatches identified in the source segment. Modifications in the target segment are done by translating the mismatched source sub-segments using an external source of bilingual information (SBI) and applying the translations to the corresponding positions in the target segment. Several combinations of translated sub-segments can be applied to the target segment which can produce multiple repair candidates. We provide a formal algorithmic description of a method that is capable of using any SBI to generate all possible fuzzy-match repairs and perform an oracle evaluation on three different language pairs to ascertain the potential of the method to improve translation productivity. Using DGT-TM translation memories and the machine system Apertium as the single source to build repair operators in three different language pairs, we show that the best repaired fuzzy matches are consistently closer to reference translations than either machine-translated segments or unrepaired fuzzy matches.

## introduction computer-aided translation (cat) tools often use a translation memory (tm), containing translation units (tu), as the key resource to assist translators. tu are made up of source and target language segments and translators use the target segments in the tu suggested by the cat tool by converting them into the desired translation. when an exact match (100%, @xmath0. the aim of these methods is to replace the sub-segments in t that are the translation of the sub-segments in s that do not appear in s by the translation of the corresponding sub-segment in s . fuzzy-match repair is gaining more traction in modern tools such as dejavu foot_0 and memoq foot_1 as a reliable method of replacing words in a proposed target-language (tl) segment t by using a source of bilingual information (sbi) such as the very same tm being used, a dictionary, or an on-line translation tool. @xcite describe a method that is capable of using any sbi for fuzzy-match repair. this method first aligns the words in the sl segment s of the tu being repaired (s, t) with the words in the segment to be translated s and identifies the mismatched words in s and s , i.e. the sub-segments they do not have in common. it then uses the sbis available to identify the sub-segments in t that are the translations of the mismatched sub-segments in s in a way similar to that used by @xcite , and then to build a set of patching operators by translating the mismatched sub-segments in s . each patching operator specifies the tl subsegment τ in t that needs to be repaired and the tl sub-segment τ to be used for repairing. combinations of patching operators can then be applied to obtain a set of candidate repaired tl segments from which the one to be finally used can be selected. in this paper, we revisit @xcite 's approach to fuzzy-match repair and go one step further; in particular in this paper we: the rest of the paper is organised as follows. the next section discusses related work on fuzzy-match repair and stresses the main differences with respect to the approach described in this paper. section 3 then provides an algorithmic description of our fuzzy-match repair method, whereas section 4 describes the rationale behind the principled restrictions that prevent two patching operators from working on the same mismatch. sections 5 and 6 discuss the experimental settings and the results of an oracle evaluation we have conducted to determine the potential of the method. the paper ends with some remarks and a description of future research lines. ## related work in the literature, one can find many papers addressing the combination of machine translation and translation memories, most of which explore different ways of integrating sub-segments from the translation memory into the decoding process of a phrase-based statistical machine translation system @xcite @xcite @xcite . alternative approaches, such as those by @xcite and @xcite , use instead the target segment t in a translation unit (s, t) as the backbone or the basis of the translation to be produced and describe ways to repair it by modifying those sub-segments in t that are the translation of the mismatched sub-segments in s. the method proposed here, which extends that of @xcite , belongs to this second group. @xcite 's method first aligns, in a way similar to ours, the words in s and s using the (word-based) edit distance @xcite and marks the mismatched subsegments in s and s for translation. it then aligns the mismatch sub-segments in s with their counterparts in t by using a sub-segmental translation memory built on the user's translation memory following the standard method to obtain phrase tables in statistical mt @xcite . finally the sub-segments in t aligned to mismatched sub-segments in s are replaced by the translations of the corresponding sub-segments in s as they are found in the sub-segmental translation memory. the main differences with the approach described here are (a) that @xcite do not take into account the context words around the mismatches -which may lead to incorrect translations due to boundary friction problems such as incorrect agreement or incomplete word reorderings-and (b) that they rely on the user's translation memory (which may be small) rather than on an external sbi. @xcite first use a modified ibm model 1 to align the mismatched words in s to sequences of one or more words ("phrases") in t and then directly map the sequence of source-side one-word edit operations (substitutions, deletions and insertions) needed to convert s into s , the segment to be translated, into an identical sequence of edit operations on the corresponding word sequences in t to generate the fuzzy-match repaired translation. an important strength of their method is that multiple alternative target-side edits are possible for each source-side insertion or substitution, and that they score them using a probabilistic model. an important limitation of their method (as compared with ours) is the lack of context around source-side one-word edits. @xcite use several linguistic resources -such as bilingual dictionaries and lists of suffixes and closed-class words-to align the words in s to those in t and then uses these alignments to identify the words in t to be repaired. finally, the words to be repaired are replaced (edited, inserted or deleted) by the translation of the corresponding mismatch in s obtained using machine translation. this method is similar to the one we describe in this paper but differs in that it only uses context around the mismatches when the new segment s contains words not found in s. in contrast, we always use context when available around all mismatches, which allows us to treat insertions, deletions and substitutions in the same way, and to mitigate the incomplete reordering and agreement errors that may occur because of not using context. finally, it is worth noting that commercial computer-aided translation software have recently begun to implement fuzzy-match repair. for example, memoq foot_3 implements a feature called matchpatch that uses term bases and other resources for fuzzy-match repair, while déjà vu implements a feature called deepminer foot_4 that extracts sub-segments from the very same translation memory being used for their use for fuzzy-match repair. unfortunately, details about how these methods work are not available. ## algorithm for fuzzy-match repair we describe a fuzzy-match repair algorithm that generates a set of candidate fuzzy-match-repaired segments from a translation unit (s, t) and the sl segment to be translated s by using any sbi. first, we describe the algorithm used to build the list of patching operators to be used for fuzzy-match repair; then, we describe the algorithm that explores all possible combinations of patching operators to generate the set of candidate fuzzy-match repaired segments. in order to build the list of patching operators (see algorithm 1), first the alignment between the words in the sl segment to be translated s and those in the sl segment s in the tu being repaired is obtained by a method based on the (word-level) edit-distance algorithm. 6 the string-positioned sub-segment pairs (σ, σ ), containing unaligned (unmatched) words and their corresponding positions in s and s , are then obtained by using the phrase-pair extraction algorithm used in phrase-based statistical machine translation (koehn, 2010, section 5.2.3) to algorithm 1 buildpatchop(s , (s, t)) generates the set of patching operators to use. input: sl segment to be translated s ; tu (s, t) to be repaired output: a list of patching operators p 1: p ← () initially p is an empty list 2: a ← editdistancealigner(s , s) get the word alignment between s and s 3: for (σ, σ ) ∈ extractphrasepairs(s , s, a) do 4: m is a set with translations of σ 5: m is a set with translations of σ 6: the following example illustrates how the set of patching operators is built. suppose the segment @xmath1, t) = (gina found out about the news, gina se enteró de las noticias). the unmatched (unaligned) words in s are bill and fraud, whereas the unmatched (unaligned) words in s are gina, and news. after word alignment these are the sub-segments pairs (σ, σ ) (up to length 3) which contain at least an unmatched word together with their translations (μ, μ ) into spanish only in those cases in which μ, the translation of σ, is found in the target segment t of the tu being repaired a patching operator can be built; this is indicated by the fifth column in the table algorithm 2 patching(p, o, n, (s, t), t , d, t ) generates all possible fuzzy-match repaired segments by backtracking. input: list of patching operators p ; set of patching operators o applied so far; position in p of the patching operator being considered, n; tu to be repaired (s, t); fuzzy-match repaired segment being built t ; boolean d indicating whether the n-th patching operator in p will be attempted to apply (true) or not (false), list t containing fuzzy-match-repaired segments 1: if d then 2: patching(p, o, n + 1, (s, t), t , true, t ) continue by applying operator n + 1 14: patching(p, o, n + 1, (s, t), t , false, t ) continue by not applying operator n + 1 15: end if above. algorithm 2 generates the set of all possible fuzzy-match repaired segments by using those sets in p(p ) (the power set of p ) containing compatible patching operators. this is achieved through a backtracking algorithm that performs a recursive depth-first search and incrementally builds fuzzy-match repaired segments t ; the algorithm is initialized with two calls patching(p, ∅, 1, (s, t), t, false, ()) and patching(p, ∅, 1, (s, t), t, true, ()), where () stands for an empty list. at each level of the recursion tree a new patching operator is considered and tested for applicability (@xmath2. for a patching operator to be applicable it needs to be compatible with the set of patching operators o applied so far to build t (see section 4). if it is compatible with the rest of patching operators in o, the patching operator is added to o and applied (lines 3-4); otherwise the branch of the recursion tree is cut. when a leaf of the recursion tree is reached (i.e. @xmath3. the algorithm applypatchop(o, t ) replaces in t the sub-segment τ by τ ; this can be safely done if patching operator p n is compatible with the other patching operators applied so far. this algorithm assumes that patching operators that are compatible can be applied in any order because the repaired segment to be generated would be the same. thanks to this assumption, the worst-case complexity of the algorithm is o(2 n ), with @xmath4, in which case 2 n repaired segments are produced. if the algorithm had to explore the application of all the patching operators in p and in all possible orders its worst-case complexity would be superexponential. for the example introduced above, algorithm 2 would produce 128 repaired segments if all patching operators were compatible. however, most of them are not compatible because they edit the same words in t (see next section) and the algorithm ends up producing only 25 repaired segments. some of these 25 repaired segments are identical but are produced by applying a different set of patching operators. for instance, the repaired segment bill se enteró de la estafa is produced by applying the patching operator (gina found out, bill found out, gina se enteró, bill se enteró) and either the patching operator (about the news, about the fraud, de las noticias, de la estafa) or the patching operator (the news, the fraud, las noticias, la estafa). the third restriction cannot be avoided and is needed in order to prevent two patching operators from editing the same word in t. however, it may happen that two patching operators working on the same mismatch do not edit any of the words in t but introduce missing ones. in those cases, the fuzzy-match repair algorithm of @xcite may end up producing candidate fuzzy-match repaired segments t with repeated words. the following example illustrates this situation. suppose the segment @xmath5, t) = (the size does not exceed 100, el tamaño no supera los 100) whose target segment can be repaired with the two patching operators (σ 1 , σ 1 , τ 1 , τ 1 ) = (exceed 100, exceed 100 cm, supera los 100, supera los 100 cm) and (σ 2 , σ 2 , τ 2 , τ 2 ) = (100, 100 cm, los 100, los 100 cm). as both patching operators do not edit (change) any word in t they could be applied one after the other and produce the fuzzy-match repaired segment @xmath6, which contains duplicated words due to the fact that the word cm is to be inserted by both operators. to avoid this problem we need to identify when two patching operators work on the same mismatch, and to do so one needs to check the mismatches both in s and s because there may be words in s not appearing in s (the mismatch only shows up in s), or words that do not appear in s but are introduced in s (the mismatch only shows up in s , as in the example above). hence two patching operators o @xmath7, σ i , τ i , τ i ) and o @xmath8, σ j , τ j , τ j ) will be marked as incompatible if they edit the same word in t (as in the work by @xcite ) or they meet the following condition: it is worth nothing that this new restriction may mark as incompatible two patching operators that, even though they work on the same mismatch, do not edit the same words in t. in those cases it is still advisable to forbid the application of the two patching operators since it is very likely that they work on the same region in t and their application interfere with one another. the following example illustrates this situation. suppose the segment @xmath9, t) = (the size is about 50 cm, el tamaño es de unos 50 cm) whose target segment can be repaired with the two patching operators o 1 = (σ 1 , σ 1 , τ 1 , τ 1 ) = (is about, is around, es de unos, está alrededor de) and o 2 = (σ 2 , σ 2 , τ 2 , τ 2 ) = (about 50, around 100, de unos 50, de unos 100). both operators share a mismatch (about) but do not edit the same words in t: o 1 edits the word es (which is replaced by está), introduces the word alrededor and removes (edits) the word unos; o 2 edits the word 50 and replaces it by 100. the two operators can be applied at the same time if operator o 2 is applied first -the repaired target segment being @xmath10. recall that the algorithm described in section 3 assumes that patching operators can be applied independently of each other and the order in which they are applied does affect the final result. ## experimental settings to evaluate the potential of the fuzzy-match repair algorithm described in section 3, we have performed an oracle evaluation (see below) on three different language pairs: english-spanish (en-es), spanish-portuguese (es-pt) and spanish-french (es-fr). these language pairs have been chosen to study how the method behaves when translating between closely-related languages (e.g. spanish-portuguese and spanish-french) and when the languages involved in the translation are not so closely related (english-spanish). in addition, of the two closelyrelated language pairs we have used, spanish and portuguese are more alike than spanish and french: spanish and portuguese are both pro-drop, ibero-romance languages -they permit null-subject sentences-whereas french is a non-pro-drop gallo-romance language. as for the corpora used for the experiments, we have used three translation memories, one per language pair, extracted from the dgt-tm 2015 multilingual translation memory; foot_7 each translation memory contains between 145,000 and 200,000 translation units. in addition, we have also extracted three test sets from the same source. each test set contains around 2,000 parallel segments with source segments no longer than 100 words. the experiments consist of simulating the translation of each source segment in the test sets by using the translation memories and using the corresponding target-language segment as a reference for evaluation. as a source of bilingual information we have used the free/open-source machine translation platform apertium (forcada et al., 2011), 9 which provides a single translation for each source segment; foot_9 more precisely, we have used the language-pair packages apertium-en-es, foot_10 apertium-es-pt foot_11 and apertium-fr-es. 13 apertium has been used both to build patching operators by translating sub-segments σ into the target language and to translate the segments in the test set for which a fuzzy match above the given threshold has not been found. apertium need less post-editing in the case of the two closely-related language pairs (es-pt and es-fr) than in the case of english-spanish. finally, we evaluate the potential of our fuzzy-match repair method with fuzzy-match score thresholds of 60%, 70% and 80% with the aim of studying whether out method is more capable of repairing fuzzy matches above a given threshold. in this regard it is worth noting that professional translators usually set the fuzzy-match score threshold above 60% @xcite . ## results and discussion tm: the target segment in the translation unit with the highest fuzzy-match score is used as a translation, if available; otherwise, an empty translation is used, and therefore the error reflects the need to type the words in the reference translation. mt: the same machine translation system used as sbi (apertium) is used to translate the source segments in the test set. fmr: the translation to be evaluated is obtained by applying the fuzzy-match repair algorithm described in section 3 with the translation unit with the highest fuzzy-match score, if available; otherwise, the translation is produced using machine translation. two error rates are reported, one computed on the whole test set and another computed only on the set of segments for which a tu with a fuzzy-match score above the given threshold is found (error on matches). the former provides and indication of the actual translation effort a translator would made to translate the source segments in the test set. the latter provides an indication of the performance of our method for fuzzy-match repair (fmr) without the interference of whole-segment machine translation, since it focuses only on those segments for which there is a translation unit to repair. this allows to directly compare fmr performance to that of using the target segment in the best tu without any repair (tm). in addition, the number of source segments for which a match is found in the translation memory and the average length of the translations produced are provided. as can be seen, our method for fuzzy-match repair has the potential (recall that this is an oracle evaluation) to improve the translator's productivity for all three different language pairs: the error rate is both below that of using the target segment in the best translation unit (tm) and below that of using machine translation (mt). furthermore, it is worthwhile to note that a good part of the difference in performance between the three language pairs can be attributed to the performance of the mt system; if we pay attention to the performance of fmr when the evaluation only focuses on those segments for which a match has been found we can see that the scores reported are quite similar for all language pairs, even though this does not happen in the case of the mt scores reported, i.e. our method for fuzzy-match repair appears to be quite robust to mt errors. the error rate over the whole test set grows with the fuzzy-match score threshold (fmt). this happens because the greater this threshold is, the less source segments can be translated using fuzzy-match repair and, as a consequence, the amount of segments that are translated with apertium grows. if we focus only on those segments that can be translated by means of fmr, we can see that the error rate decreases as the threshold grows; figure 1 show how the error rate on matches behaves as a function of the fuzzy-match score threshold. this is the expected behaviour because as the threshold grows the amount of words to repair decreases. with respect to the process of building patching operators, and provided that the performance of the machine translation system differs between the language pairs, it is worth studying how successful it is our method when it comes to use apertium to build patching operators. figure 2 plots the success rate when building patching operators as a function of the length of the source sub-segments σ for a fuzzy-match score threshold of 60%, 70% and 80%; as can be seen, success rates for different fuzzy-match thresholds behave very similarly. a patching operator is successful when the translation of the sub-segment σ of s is found in t, that is, when the machine translation system and the proposed translation unit exactly agree on the translation as can be seen, the longer the sub-segments the harder it is that the translation obtained from the sbi is found in t. this behaviour is present in all the language pairs and is more pronounced when the translation involves non-related language pairs (en-es) than when the languages are closely related (es-pt). the average length of σ in the patching operators used to build the repaired target segment chosen by the oracle when the fuzzy-match score threshold is set to 80% is around 2.8 words for en-es, 3.7 for es-fr and 4.7 for es-pt. ## concluding remarks in this paper we have extended the approach of @xcite , which uses any external source of bilingual information to repair fuzzy matches coming from a translation memory, to prevent two patching operators from working on the same mismatch, and we have extensively evaluated its performance on three different language pairs and provided a more formal algorithmic description. the oracle evaluation we have conducted reveals the potential of our approach to fuzzymatch repair. for three different language pairs we consistently improve the quality of the translations produced -both with respect to raw machine translation or unrepaired fuzzy matcheseven though the sbi we have used (the machine translation system apertium) performs below the state of the art for some language pairs. we hope that by combining different sbis, e.g. different machine translation systems as well as bilingual concordancers, 15 the quality of the repaired segments increase. as a future work we plan to combine different sbi and try different methods to automatically select the best fuzzy-match repair for a given sl segment. in particular we will adapt existing techniques used for sentence-level machine translation quality estimation and devise a set of features specially designed to tackle this particular problem.