2.1 Properties

First, MWEs occur in various syntactic constructions:

Second, some MWEs are fixed lexical combinations, while others are more flexible. As an example of the former consider

In this idiomatic expression, the constituents and the order in which they occur in a text are fixed. In contrast, the following expression

contains an open slot that can be filled by a noun phrase, and the order of the two objects can be changed.

Semantically, MWEs cover a wide spectrum, from highly idiomatic

to completely transparent

2.2 Task definition

As shown above, MWEs are a diverse set of constructions, exhibiting a variety of linguistic phenomena, with various idiosyncratic properties. Our task in this work is to identify such constructions in textual corpora. However, we do not attempt to extract all of them.

First, we only address continuous MWEs. That is, our solution will not identify expressions with “slots” in them that can be filled by productive phrases (such as išb 'l X šb'h “sat on X seven”). Second, our solution will likely fail to identify MWEs whose meaning is compositional. Our methodology capitalizes on the non-compositionality of many MWEs, and examples such as ‘wbd zr “worker foreign” are unlikely to be extracted.

Our solution is not limited to any combination of part-of-speech categories. Specifically, we will identify several of the constructions listed above, including proper names. While many consider named entity recognition to be a separate problem, we maintain that proper names are a special kind of MWEs (which may or may not be easier to identify than other kinds). Note that Hebrew does not use capitalization, which makes the recognition of named entities harder than in European languages. In addition, many proper names are derived from (and are homonymous with) common nouns, again adding to the difficulty of identifying them. For example, bt im (daughter-of sea)“mermaid” is also the name of a city in Israel (Bat Yam); both are spelled the same, i.e., with no capitalization.

Finally, our task is to identify MWEs of any length. While much of our processing is done for bi-grams (sequences of two tokens), the methodology works equally well for longer sequences, as our results in Section 4.6, and in particular Table 4, demonstrate. Note that many of the results include function words, even though we remove (very few, extremely frequent) function words as part of our pre-processing (Section 4.3).

4.1 Motivation

Parallel texts are an obvious resource from which to extract MWEs. By definition, idiomatic expressions have a non-compositional meaning, and hence may be translated to a single word (or to an expression with a different meaning) in a foreign language. The underlying assumption of alignment-based approaches to MWE extraction is that (some, typically more idiomatic) MWEs are aligned across languages in a way that differs from other, compositional expressions; we share this assumption. However, existing approaches focus on the results of word alignment in their quest for MWEs, and in particular consider 1:n and n:m alignments as potential areas in which to look for them. This is problematic for two reasons: First, word alignment algorithms have difficulties aligning MWEs, and hence 1:n and n:m alignments are often noisy; while these environments provide cues for identifying MWEs, they also include much noise (for example, they can consist of fragments of MWEs, sometimes with additional unrelated material). Second, our experimental scenario is such that our parallel corpus is particularly small, and we cannot fully rely on the quality of word alignments, but we have a bilingual dictionary that compensates for this limitation. In contrast to existing approaches, then, we focus on misalignments: we trust the quality of 1:1 alignments, which we verify with the dictionary; and we search for MWEs exactly in the areas that word alignment failed to properly align, not relying on the alignment in these cases. In other words, we view all words that are not included in 1:1 alignments as potential areas in which to search for MWEs, independently of how these words were aligned by the word-aligner. In particular, we also consider words that are aligned to null in such contexts. Unlike other alignment-based approaches, then, our algorithm is less susceptible to noise, first because we validate 1:1 alignments with a dictionary, and second, because our focus on misalignments improves the chances of aligning chunks that include multi-word expressions, rather than smaller chunks that may consist of proper substrings thereof.

Moreover, in contrast to existing alignment-based approaches, we also make use of a large monolingual corpus from which statistics on the distribution of word sequences in Hebrew are drawn. This has several benefits: of course, monolingual corpora are easier to obtain than parallel ones, and hence tend to be larger and provide more accurate statistics. Furthermore, this provides validation of MWE candidates that are extracted from the parallel corpus: Rare expressions that are erroneously produced by the alignment-based technique can thus be eliminated on account of their low frequency in the monolingual corpus.

Specifically, we use a variant of pointwise mutual information (PMI) as our association measure. While PMI has been proposed as a good measure for identifying MWEs, it is also known not to discriminate accurately between MWEs and other frequent collocations. This is because it promotes collocations whose constituents rarely occur in isolation (e.g., typos and grammar errors), and expressions consisting of some word that is very frequently followed by another (e.g., say that). However, such cases do not have idiomatic meanings, and hence at least one of their constituents is likely to have a 1:1 alignment in the parallel corpus; we only use PMI after such alignments have been removed.

An added value of our methodology is the automatic production of an MWE translation dictionary. Since we start with a parallel corpus, we can go back to that corpus after MWEs have been identified, and extract their translations from the parallel sentences in which they occur.

Finally, alignment-based approaches can be symmetric, and our approach is indeed symmetric. While our main motivation is to extract MWEs in Hebrew, a by-product of our system is the extraction of English MWEs along with their translations to Hebrew. This again contributes to the task of enriching our existing bilingual dictionary.

4.2 Resources

Our methodology is in principle language-independent and appropriate for medium-density languages (Varga et al. Reference Varga, Halácsy, Kornai, Nagy, Németh and Trón2005). We assume the following resources: a small bilingual, sentence-aligned parallel corpus; large monolingual corpora in both languages; morphological processors (analyzers and disambiguation modules) for the two languages; and a bilingual dictionary. Our experimental setup is Hebrew–English. We use a small parallel corpus (Tsvetkov and Wintner Reference Tsvetkov and Wintner2010a), which consists of 19,626 sentences, mostly from newspapers. Some data on the parallel corpus are listed in Table 1 (the size of our corpus is very similar to that of Caseli et al. Reference Caseli, Villavicencio, Machado and Finatto2009).

Table 1.

Statistics of the parallel corpus

We also use data extracted from two monolingual corpora. For Hebrew, we use the morphologically analyzed MILA corpus (Itai and Wintner Reference Itai and Wintner2008) with part-of-speech tags produced by Bar-Haim, Sima'an and Winter (Reference Bar-Haim, Sima'an and Winter2005). For English we use Google's Web 1T corpus (Brants and Franz Reference Brants and Franz2006). Data on the Hebrew corpus are provided in Table 2.Footnote ²

Table 2.

Statistics of the Hebrew corpus

Finally, we use a bilingual dictionary consisting of 78,313 translation pairs. Most of the entries were collected manually (Itai and Wintner Reference Itai and Wintner2008), while few were produced automatically from Wikipedia article titles (Kirschenbaum and Wintner Reference Kirschenbaum and Wintner2010).

4.3 Pre-processing the corpora

Automatic word alignment algorithms are noisy, and given a small parallel corpus such as ours, data sparsity is a serious problem. To minimize the parameter space for the alignment algorithm, we attempt to reduce language-specific differences by pre-processing the parallel corpus. The importance of this phase should not be underestimated, especially for alignment of two radically different languages such as English and Hebrew (Dejean et al. Reference Dejean, Gaussier, Goutte and Yamada2003). See also Section 5.2.

Hebrew, like other Semitic languages, has a rich, complex, and highly productive morphology. Information pertaining to gender, number, definiteness, person, and tense is reflected morphologically on base forms of words. In addition, prepositions, conjunctions, articles, possessives, etc. may be concatenated to word forms as prefixes or suffixes. This results in a very large number of possible forms per lexeme. Consequently, a single English word (e.g., the noun advice) can be aligned to hundreds or even thousands of Hebrew forms (e.g., l'cth “to-her-advice”). As advice occurs only eight times in our small parallel corpus, it would be almost impossible to collect statistics even on simple 1:1 alignments without appropriate tokenization and lemmatization.

We therefore tokenize the parallel corpus and then remove punctuation. We analyze the Hebrew corpus morphologically and use a disambiguation module to select the most appropriate analysis in context. Adopting this selection, the surface form of each word is reduced to its base form, and bound morphemes (prefixes and suffixes) are split to generate stand-alone “words”. We also tokenize and lemmatize the English side of the corpus, using the Natural Language Toolkit package (Bird, Klein and Loper Reference Bird, Klein and Loper2009). Then, we try to remove some language-specific differences automatically. We remove frequent function words: in English, the articles a, an, and the, the infinitival to and the copulas am, is, and are; in Hebrew, the accusative marker at. These forms either do not have direct counterparts in the other language, or behave very differently across the languages.

Example 1

Following is an example Hebrew sentence from our corpus with a word-by-word gloss and an English translation:

After pre-processing, the Hebrew sentence, which is aggressively segmented, is represented as follows:

The English sentence is represented as and i tell her keep away from person (note that to and the are deleted). Note how this reduces the level of (morphological and orthographic) difference between the two languages.

For consistency, we pre-process the monolingual corpora in the same way. We then compute the frequencies of all word bi-grams occurring in each of the monolingual corpora.

4.4 Identifying MWE candidates

The motivation for our MWE identification algorithm is the assumption that there may be three sources to misalignments (anything that is not a 1:1 word alignment) in parallel texts: either MWEs (which trigger 1:n or n:m alignments); or language-specific differences (e.g., one language lexically realizes notions that are realized morphologically, syntactically, or in some other way in the other language); or noise (e.g., poor translations, low-quality sentence alignment, and inherent limitations of word alignment algorithms).

This motivation induces the following algorithm. Given a parallel, sentence-aligned corpus, it is first pre-processed as described above, to reduce the effect of language-specific differences. We then use Giza++ (Och and Ney Reference Och and Ney2003) to word-align the text, employing union to merge the alignments in both directions. We look up all 1:1 alignments in the dictionary. If the pair exists in our bilingual dictionary, we remove it from the sentence and replace it with a special symbol, ‘*’. Such word pairs are not parts of MWEs. If the pair is not in the dictionary, but its alignment score as produced by Giza++ is very high (above 0.5) and it is sufficiently frequent (more than five occurrences), we add the pair to the dictionary but also retain it in the sentence. Such pairs are still candidates for being (parts of) MWEs.Footnote ³

Example 2

Refer back to Example 1. Following is the representation of the two sentences after pre-processing, and the alignment produced by Giza++. Sequences that are aligned to a single word in the other language are enclosed in curly brackets; and null alignments are indicated by {}.

Once 1:1 alignments are replaced by ‘*’, the following alignment is obtained

Note that we are not concerned about the actual alignments of remaining tokens; unlike other approaches, that focus only on m:n alignments, we generalize to other cases of misalignments, including those in which words in one language are aligned to null. Specifically, in the example above, the bigram bn adm is considered a MWE candidate independently of the English words its tokens are aligned with.

If our resources were perfect, i.e., if word alignment made no errors, the dictionary had perfect coverage and our corpora induced perfect statistics, then all the remaining text (other than the special symbol) in the parallel text would be part of MWEs. In other words, all sequences of remaining source-language words, separated by ‘*’, are MWE candidates. As our resources are far from perfect, further processing is required in order to prune these candidates. For this, we use association measures computed from the monolingual corpus.

4.5 Ranking and filtering MWE candidates

The algorithm described above produces sequences of Hebrew word forms (free and bound morphemes produced by the pre-processing stage) that are not 1:1 aligned, separated by ‘*’s. Each such contiguous sequence of tokens, unbroken by ‘*’s, is a MWE candidate. In order to rank the candidates we use statistics from a large monolingual corpus. We do not rely on the alignments produced by Giza++ in this stage.

We extract all word bi-grams from these candidates (contiguous token sequences). Each bi-gram is associated with its PMI-based score, computed from the monolingual corpus. We use PMI^k, a heuristic variant of the PMI measure, proposed and studied by Daille (Reference Daille1994). The exponent, k, is a frequency-related factor, used to demote collocations with low-frequency constituents. The value of the parameter k can be chosen freely (k < 0) in order to tune the properties of the PMI to the needs of specific applications, and values of k ranging between 2 to 3 have been useful for various applications (Bouma Reference Bouma2009). We conducted experiments with k = 0.1, 0.2,. . ., 2.9, 3 and found k = 2.7 to give the best results for our application, maximizing the f-score on the test set. Interestingly, about 15,000 (approximately 10%) of the candidate MWEs are removed in this stage because they do not occur at all in the monolingual corpus.

We then experimentally determine a threshold (see Section 5). A word sequence of any length is considered MWE if all the adjacent bi-grams it contains score above the threshold. Finally, we restore the original forms of the Hebrew words in the candidates, combining together bound morphemes that were split during pre-processing, and we restore the function words. Many of the candidate MWEs produced in the previous stage are eliminated now, since they are not genuinely multi-words in the original form (i.e., they are single words split by tokenization).

Refer back to Example 2. The sequence bn adm k zh is a MWE candidate. Two bi-grams in this sequence score above the threshold: bn adm, which is indeed a MWE, and k zh, which is converted to the original form kzh and hence not considered a candidate. We also consider adm k, whose score is low; this prevents the consideration of longer n-gram candidates that include the bigram adm k as a substring. Note that the same aligned sentence can be used to induce the English MWE keep away, which is aligned to a single Hebrew word.

5.1 Intrinsic evaluation

Ideally, one should evaluate the accuracy of a MWE extraction system against a balanced, carefully designed corpus of positive and negative examples, measuring both precision and recall of the system. Such corpora are of course very difficult to obtain. We were able to obtain a small set of positive and negative MWE instances in a single and specific (albeit frequent) construction. This is the annotated corpus of Hebrew noun–noun constructions (Al-Haj and Wintner Reference Al-Haj and Wintner2010), consisting of 463 high-frequency bi-grams of the same syntactic construction. Of those, 202 are tagged as MWEs (in this case, noun compounds) and 258 as non-MWEs. This corpus consolidates the annotation of three annotators: only instances on which all three agreed were included. Since it includes both positive and negative instances, this corpus facilitates a robust evaluation of precision and recall. Of the 202 positive examples, only 121 occur in our parallel corpus; of the 258 negative examples, ninety-one occur in our corpus. We therefore limit the discussion to those 212 examples whose MWE status we can determine, and ignore other results produced by the algorithm we evaluate.

On this corpus, we compare the performance of our algorithm to four baselines: using only PMI^2.7 to rank the bi-grams in the parallel corpus; using PMI^2.7 computed from the monolingual corpus to rank the bi-grams in the parallel corpus; and using Giza++ 1:n alignments, ranked by their PMI^2.7 (with bi-gram statistics computed once from parallel and once from monolingual corpora). ‘MWE’ refers to our algorithm. For each of the above methods, we set the threshold at various points, and count the number of true MWEs above the threshold (true positives) and the number of non-MWEs above the threshold (false positives), as well as the number of MWEs and non-MWEs below the threshold (false and true negatives, respectively). From these four figures we compute precision, recall, and their harmonic mean, f-score, which we plot against (the number of results above) the threshold in Figure 1; the raw data for a threshold reflecting 2,750 results are listed in Table 5.

Fig. 1.

Evaluation results compared with baselines: noun–noun compounds.

Table 5.

Evaluation results, noun–noun compounds, at a threshold reflecting 2,750 results.

* TP: raw number of true positives; † FP: number of false positives.

The plots show the f-score of five methods for extracting MWEs, computed on different (but increasingly larger) sets of results. Each column corresponds to a particular (increasingly lower) threshold; of course, the lower the threshold, the more candidates are selected as MWEs, thereby improving the recall but potentially harming the precision. As the graph clearly shows, our results (‘MWE’) are consistently higher than all other baselines. The difference between the MWE curve and its nearest neighbor, obtained by ranking candidates based on their PMI score only, without word alignment, is statistically significant.Footnote ⁵ Specifically, we obtain an f-score of 0.66 at a threshold reflecting 2,750 (and also 3,500) results. The lowest curve reflects statistics drawn from the parallel corpus; these results are poorest due to the small size of the corpus. Interestingly, if a much larger (monolingual) corpus is used, and only the collocation measure is used to determine the MWE status of bi-grams, the results are dramatically better (reflected by the second highest curve). The two middle curves represent the approach that builds on Giza++ alignments, ranked by their PMI score (computed from the parallel and the monolingual corpora, respectively). As can be clearly seen in Figure 1, these curves climb fast but reach a ceiling soon, and setting the threshold lower does not yield much higher f-scores. The best-performing method, no matter where the threshold is set, is our proposed approach.

The advantage of the above evaluation is that it reports both precision and recall of our system. However, these are only measured for a single and very specific construction. To further assess the contribution of our system, we extend the evaluation to other constructions below. However, for arbitrary constructions we only have lists of (positive) MWEs to evaluate against.

For the following experiments, we compiled three small corpora of Hebrew two-word MWEs. The first corpus, PN, contains 785 person names (names of Knesset members and journalists), of which 157 occur in the parallel corpus. The second, Phrases, consists of 571 entries, beginning with the letter x in the Hebrew Phrase Dictionary of Rosenthal (Reference Rosenthal2009), and a set of 331 idioms we collected from Internet resources. This set includes arbitrary expressions of various lengths and syntactic constructions, most of which are idiomatic. Of those, 154 occur in the corpus. The third set, NN, consists of positive examples in the annotated corpus of noun–noun constructions described above. All instances in this set have the same syntactic structure and similar (high) frequency.

Since we do not have negative examples for two of these sets, we only evaluate recall, using a threshold reflecting 2,750 results. For each of these datasets, we report the number of MWEs in the dataset (which also occur in the parallel corpus, of course) our algorithm detected. We compare in Table 6 the recall of our method (MWE) to Giza++ alignments, as above, and also list the upper bound (UB), obtained by taking all above-threshold bi-grams in the corpus.

Table 6.

Recall evaluation

The bottom row of Table 6 reflects recall results obtained by focusing on Giza++ m: n alignments, as done in previous works. This approach is likely to miss many proper names, which tend to be 1:1 aligned; hence the poor performance of this method on the PN set. As demonstrated above, our methodology is capable of extracting proper names of various types; this is because we validate 1:1 alignments in a dictionary, and many proper names fail this test. The set Phrases includes MWEs of various syntactic constructions (and various degrees of semantic opacity), and our approach can clearly identify many of them. Our results are less impressive on the set NN, most probably because members of this set are all of the same syntactic construction. The distinction between noun–noun constructions that are MWEs (Al-Haj and Wintner Reference Al-Haj and Wintner2010 refer to them as noun compounds) and those that are not is not easy, and must rely on several factors, including the semantics of the phrase but also several morphological aspects of its behavior. Our methodology capitalizes on alignment mismatches that are more characteristic of other data sets, and may or may not be able to make the subtle distinctions required for the set NN.

5.2 The importance of pre-processing

To emphasize the importance of pre-processing (Section 4.3), we report in this section the results of running exactly the same experiments, without first pre-processing the corpora.

The main effect of the lack of pre-processing is during the word-alignment phase, where most of the 1:1 alignments are lost due to data sparsity. Specifically, whereas our pre-processed parallel corpus yielded 102,261 1:1 aligned “words” (more precisely, base forms) that are included in our dictionary, without pre-processing, this number sank to 10,886 (a little over 10%). Consequently, the problem of identifying MWEs is reduced to not much more than ranking n-grams in a large monolingual corpus (again, with no pre-processing). As a result, most of the extracted MWEs are proper names (which do not tend to be inflected).

We repeated the recall evaluation described above in this setup. We report the results in Table 7, comparing with our previous results. The contribution of pre-processing is evident.

Table 7.

Recall evaluation

5.3 Extrinsic evaluation

An obvious benefit of using parallel corpora for MWE extraction is that the translations of extracted MWEs are available in the corpus. We use a naïve approach to identify these translations. For each MWE in the source-language sentence, we consider as translation all the words in the target-language sentence (in their original order) that are aligned to the word constituents of the MWE, as long as they form a contiguous string. Since the quality of word alignment, especially in the case of MWEs, is rather low, we remove “translations” that are longer than four words (these are frequently wrong). We then associate each extracted MWE in Hebrew with all its possible English translations.

The result is a bilingual dictionary containing 3,750 MWE translation pairs, which we use in the training of a phrase-based Hebrew to English statistical machine translation (SMT) system, exploring its contribution to the quality of the translation, as measured by BLEU (Papineni et al. Reference Papineni, Roukos, Ward and Zhu2002). Specifically, our system is implemented using Moses (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007), a toolkit for constructing SMT systems. We use our own parallel corpus of approximately 20,000 sentences to train a translation model, and a large monolingual corpus of English newspaper-type texts (obtained from the English Gigaword corpus, Graff and Cieri Reference Graff and Cieri2007) for the language model. We randomly selected a set of 1,000 sentence pairs (disjoint from the training set) for tuning and a randomly selected disjoint set of 1,000 sentences for evaluation.

We experiment with three different scenarios of incorporating the MWE dictionary, and compare them with a baseline system, in which the dictionary is not used at all (this is practically the same system that was used by Lembersky, Ordan and Wintner Reference Lembersky, Ordan and Wintner2011). First, the top-ranking 1,000 Hebrew MWEs, along with their translations, are added to the parallel corpus on which the translation model is based. Second, we use all the MWEs extracted by our system (along with their translations, of course), and finally we use all MWEs again, but we duplicate them three times in order to upweight the MWEs compared with the default training material. This is similar to the evaluation technique of Carpuat and Diab (Reference Carpuat and Diab2010).

The results are depicted in Table 8. In all cases, incorporating MWEs in the system results in an improved BLEU score. The best system, in which all MWEs are added to the training material, significantly improves the baseline (p = 0.022). Some examples of improved translations with the best performing system include the health system (compare with the health, generated by the baseline system); the nation state was founded (vs. the nation state was); the october events (vs. the events of the past october); for the sake of plans and a short-term proposition (vs. for the sake of plans a long-term short); and the government of prime minister benjamin netanyahu (vs. minister benjamin netanyahu government).

Table 8.

Contribution to machine translation

5.4 Error analysis

Our MWE extraction algorithm works as follows: Translated texts are first sentence-aligned. Then, Giza++ is used to extract 1-to-1 word alignments, that are then verified by the dictionary and replaced by ‘*’ if the correct word translation is available. This process filters out candidates that have compositional meaning and, therefore, are not considered MWEs (in our algorithm, a non-compositional meaning of a bi-gram is expressed by its non-literal translation to the parallel language). Sequences of words separated by ‘*’s are considered MWE candidates. At each step of the application errors may occur that lead to false identification of non-MWEs. We manually annotated the top 1,000 bi-gram MWEs extracted by the algorithm and identified 121 false positives. Analysis of these false positives reveals the error sources detailed below. In Table 9 we summarize the statistics of the error sources.

Table 9.

Sources of errors

• Translation quality of the parallel corpus. Whereas the sentences are indeed translations, the translations are, to a large extent, non-lexical in the sense that context is used in order to extract the meaning and deliver it in different wording. As a result, it is sometimes hard or even impossible to align words based on the sentence alone.

• As an example, a newspaper text includes, on the English side, a sentence beginning with a reported utterance, followed by according to senior officials. Its Hebrew translation uses kk msrw pqidim bkirim (thus reported officials senior) “said senior officials.” As a result, Hebrew kk msrw “thus reported” is aligned with according, and is considered a MWE candidate.

• Sentence alignment errors. Several errors can be attributed to the automatic sentence alignment.

  1. (1) We use a purely statistical sentence aligner to align sentences based on their length and token co-occurrence information. As a result, some sentences of similar length may incorrectly be marked as mutual translations. Of course, most of the word sequences in such sentences cannot be aligned and hence become MWE candidates.

  2. (2) The output of the sentence aligner contains only 1-to-1 sentence translations. As our parallel corpora include non-lexical translations that sometimes can only be expressed in terms of 1-to-2, or 2-to-1 translated sentences, the sentence aligner may output a 1-to-1 alignment, where one of the sentences is only a partial translation of another. The non-translated part of the sentence may contain false MWE candidates.

• Word alignment errors. Sometimes a word sequence has a translation, but it is not aligned properly. Possible reasons for such errors are as follows:

  1. (1) Insufficient statistics of word co-occurrence due to the small size of the parallel corpus.

  2. (2) Errors caused by bi-directional translation merge (we employ union to merge the translations in both directions (Och and Ney Reference Och and Ney2003); intersection resulted in worse results). Often the alignment is correct only in one direction, but we lose this information after merging the alignment; this often happens in very long sentences. Another example of the problematic alignment caused by bi-directional merge is cases in which the word aligner proposes n:1 alignment; usually these n words contain the correct sequence or a part of the sequence and the correct analysis of the bi-directional alignments may help filter out the incorrect parts (i.e., the analysis of the intersection of n and m sequences, where m:1 is Hebrew-to-English and n:1 is English-to-Hebrew alignments detected by the word alignment tool).

As an example, our Hebrew corpus includes the sentence lm'šh, drwš lw rq kšrwn axd, lškn' anšim lhcbi' b'dw (in-fact, required to-him only talent one, to-convince people to-vote for-him) “in fact, he only needs one talent: to convince the electorate to vote for him”. This is aligned against the English He needs only one talent: to convince the electorate to vote for him. Giza++, however, aligns the Hebrew lhcbi' b'dw “to-vote for-him” with the English vote, whereas the final English him is aligned with the Hebrew third token (lw “to-him”), and the English penultimate for is aligned to null.

• Noise introduced by pre-processing

  1. (1) Errors caused by morphological analysis and disambiguation tools may lead to wrong tokenization, or to the extraction of an incorrect base form from the surface form of the word. As a result, the extracted citation form cannot be aligned to its translation, and correctly aligned word-pairs cannot be found in the dictionary. For example, the bi-gram bniit gdr (a noun–noun compound) is translated as building fence. Stemming on the English side produces the erroneous base form build (a verb) for the word building. Word alignment correctly aligns the words bniih (a noun) and build (a verb), but such a pair does not exist in the dictionary, which contains the following pairs: bnh-build (verb), and bniih-building (noun).

  2. (2) An additional source of errors stems from language-specific differences in word order between the languages: e.g., txnt rkbt is consistently translated as railway station; the correct alignment would be txnt—station, rkbt—railway, but due to the different word order in the two languages, and to the fact that both phrases are frequent collocations, Giza++ proposes the alignment txnt—railway, rkbt—station (these pairs are not in the dictionary and, therefore, the bigram txnt rkbt is falsely identified as an MWE). Such problems can be handled with more sophisticated pre-processing that reduces language-specific differences, where not only morphology and function words are taken into account but also language-specific word order.

• Incomplete dictionary. If sentence and word alignments are correct, and the correct word-to-word translation exists, but the translated pair is not in the dictionary, the word sequence may erroneously be considered an MWE candidate.

Unfortunately, we have no remedy for most of these errors, other than using larger corpora and better language resources. This is the kind of noise that is likely to affect any natural language processing application.

• Parameters of the algorithm

  1. (1) Setting the threshold too high causes bi-grams that are subsequences of longer MWEs to be false positives. For example, the non-MWE, compositional bi-gram lšlm ms “pay tax”, which is a subsequence of the MWE lšlm ms šptiim (pay tax-of lip) “pay lip service”, was mistakenly extracted as an MWE, since the score of the bi-gram ms šptiim “lip tax” is lower than the threshold.

  2. (2) During error analysis we revealed the following algorithm drawback (which is probably common to other alignment-based methods): False MWE candidates that occur several times in the parallel corpus are selected to be MWE candidates only in a minority of these occurrences. In other words, we define as MWE candidate any n-gram that was misaligned; we do not check whether this n-gram was misaligned consistently in all (or most) of its occurrences in the corpus. For example, there are twelve occurrences of the bi-gram nšia hmdinh (president of the state) in the parallel corpus, but only twice does it appear as a candidate bi-gram due to two sentences in which the translation of this bi-gram is missing (due to non-literal or incorrect sentence translation). From this we conclude that the algorithm can also be improved if the candidates would be selected from bi-grams that have no translation in the parallel language in a majority of their occurrences. We leave this improvement for future work.