{'fraction_non_alphanumeric': 0.026593142704673813, 'fraction_numerical': 0.011962467203273002, 'mean_word_length': 4.838006230529595, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The impact of Arabic morphological segmentation on broad-coverage English-to-Arabic statistical machine translation

Morphologically rich languages pose a challenge for statistical machine translation (SMT). This challenge is magnified when translating into a morphologically rich language. In this work we address this challenge in the framework of a broad-coverage English-to-Arabic phrase based statistical machine translation (PBSMT). We explore the largest-to-date set of Arabic segmentation schemes ranging from full word form to fully segmented forms and examine the effects on system performance. Our results show a difference of 2.31 BLEU points averaged over all test sets between the best and worst segmentation schemes indicating that the choice of the segmentation scheme has a significant effect on the performance of an English-to-Arabic PBSMT system in a large data scenario. We show that a simple segmentation scheme can perform as well as the best and more complicated segmentation scheme. An in-depth analysis on the effect of segmentation choices on the components of a PBSMT system reveals that text fragmentation has a negative effect on the perplexity of the language models and that aggressive segmentation can significantly increase the size of the phrase table and the uncertainty in choosing the candidate translation phrases during decoding. An investigation conducted on the output of the different systems, reveals the complementary nature of the output and the great potential in combining them.


Introduction
Morphologically rich languages pose a challenge for statistical machine translation (SMT), as these languages possess a large set of morphological features producing a large number of rich surface forms. This increase in surface forms leads to larger vocabularies and higher sparsity adversely affecting the performance of SMT systems. The effect of these factors are even magnified when translating into a morphologically rich language.
In this work we address the challenge posed by the morphological richness of Arabic in the framework of a broad coverage English-to-Arabic statistical phrase based machine translation (PBSMT). We explore a full spectrum of Arabic segmentation schemes ranging from full word form to fully segmented forms separating every possible Arabic clitic and examine the effects on system performance.
The segmentation schemes, are applied in a preprocessing step to both the Arabic side of the training data and the test sets. Nine different broad coverage PBSMT systems are trained on the NIST09 Constrained Training Condition Resources (NIST09) data segmented using these various schemes. The built PBSMT systems are evaluated and compared on English-to-Arabic test sets that we construct from existing NIST09 Arabic-to-English test sets.
Based on this comparison we identify the best and the worst segmentation schemes and lay out a set of general observations on the effect of splitting off different sets of clitics (affixes) on the performance of a broad coverage PBSMT system.
As the Arabic output of systems is segmented it needs to be recombined (detokenized). We experiment with six different detokenization techniques increasing in the level of complexity. The best re tokeninzation technique is used in recombining the output of the different systems.
Previous works that addressed the effect of Arabic rich morphology and tokenization on SMT concentrated on Arabic-to-English machine translation (Habash and Sadat, 2006;Zollmann, 2006;Lee, 2004).
However, few works focused on SMT into Arabic. Sarikaya and Deng (2007) use joint morphological-lexical language models to rerank the output English-dialectal Arabic MT. A research more relevant to our work was done by Badr et. al (2008) . In their work they compare a segmented Englsih-to-Arabic system with an unsegmented system. They also experiment with a number of detokenization techniques. However, in their work they just compare a single segmentation scheme (and one variation of it) to the unsegmented baseline without mentioning what motivated the choice of this specific segmentation. They also use a training corpora of 3M words and conclude that the effect of segmentation diminishes when the corpora size is "large". In our work we experiment with a spectrum of segmentation giving a total of nine different schemes. Our results indicate that the choice of the segmentation scheme has a significant effect on the performance of a PBSMT system in a large data scenario. In this work we also explore more variation of detokenization techniques for recombining the Arabic output.
The remainder of the paper is organized as follows: In Section 2 we present some relevant background on Arabic linguistics to motivate the Arabic preprocessing schemes discussed in Section 3. All the different detokenization schemes are described in Section 4. The training and test data used is described in Section 5, while Section 6 described the experiments and result for all the different segmentation schemes.

Arabic Morphology and Orthography
Arabic is a morphologically rich language with a large set of morphological features 1 that are realized using both concatenative (affixes and stems) and templatic (root and patterns) morphology.
Arabic has a set of attachable clitics (affixes) to be distinguished from inflectional features such as gender, number, person, voice, aspect, etc. These clitics attach to the word increasing the ambiguity of alternative readings. Arabic clitics apply to a word base in a strict order: CONJ+ PART+ DET+ WORD_BASE +PRON 1 Arabic words have fourteen morphological features: POS, person, number, gender, voice, aspect, determiner proclitic, conjunctive proclitic, particle proclitic, pronominal enclitic, nominal case, nunation, idafa (possessed), and mood. Table 1 lists the Arabic clitics 2 divided into 4 classes: conjunction proclitics (CONJ+ ), particle proclitics (PART+), definite article (DET+) , and pronominal enclitics (PRON+) which comprise of possessive and object pronouns. The first three classes of clitic in Table 1 are given along with their English meaning. The clitics of the fourth class (PRON) are given followed by O (for object pronoun) or P (possessive pronoun) followed by their morphological features: person, gender, and number in the this order.
Arabic orthography introduces further challenges as certain letters in Arabic script are often spelled inconsistently which leads to an increase in both sparsity (multiple forms of the same word) and ambiguity (same form corresponding to multiple words). One example is the letter Alif in Arabic, which can appear with Hamza on top ‫,أ‬ or below ‫,إ‬ and with maddah on top . All these forms are often written as bare Alif ‫.ا‬ Another example is the two letters Ya ‫ي‬ and Alif Maqsura ‫ى‬ which are often used interchangeably in word final position. Add to all this the optionality of diacritics (short vowels) in Arabic script.
This inconsistent variation in raw Arabic text is typically addressed using orthographic normalization which maps all Alif to to bare Alif, Dotless Ya/Alif Maqsura form to Dotted Ya and deletes diacritics.
CONJ w+ (and ), f+ (then ) PART l+ (to/for), b+ (by/with), k+ (as/such) s+ will/future.   (Buckwalter, 2002). This type of Arabic text "reduction" could be acceptable when Arabic is the source language, but is clearly problematic when translating into Arabic. Therefore, we use the "enriched" form of the Arabic raw text throughout this work. The enriched form of text uses the correct form of Alif ‫ا‬ and the right form of Ya ‫ي‬ and Alif Maqsura ‫ى‬ in word final position.

Arabic Preprocessing Schemes
We experiment with various Arabic preprocessing schemes by splitting off different subsets of the clitics mentioned in Section 2. The raw Arabic text is enriched and tokenized using the Morphological Analysis and Disambiguation for Arabic (MADA) toolkit (Habash and Rambow, 2005). The various Arabic tokenization schemes that we experiment with, span a segmentation spectrum ranging from coarse segmentation, which uses unsegmented text, to fine segmentation which splits off all possible clitics.
All the different tokenization schemes are described in detail below from coarse to fine : • UT: This scheme uses the full (untokenized) enriched form of the word. This scheme is used as input to produce the other schemes. • S0: This scheme splits off the conjunction proclitic w+. • S1: This scheme splits off +f in addition to the w+ split by S0. • S2: This scheme splits off all the particle proclitics (PART) in addition to the clitics split off by S1 • S3: This scheme splits off all clitics from the CONJ class and all clitics of PART class except s+ prefix. It also splits off all the suffixes from the PRON class. This scheme is equivalent to the PATB tokenization, but to distinguish between the possessive and object pronouns ,which have the same surface form, we use their morphological features (henceforth, MF form) instead as given in Table 1 between parentheses . • S4: This scheme splits off all clitics split by S3 plus splitting of the s+ clitic. This scheme is equivalent to the ATBv3 tokenization. As in S3 we also use the MF form of the PRON clitics. • S5: This scheme splits off all the possible clitics appearing in Table 1.
We also experiment with a number of variations of these schemes: • S4SF: Similar to scheme S4 but with the PRON clitics in their surface form. • S5SF: Similar to scheme S5 but with the PRON clitics in their surface form. This scheme is similar to the main segmentation scheme suggested by Badr et. al (2008). Table 2 exemplifies the effect of all the different schemes on the same sentence in the training data. As can be seen from the example in Table 2 the text's fragmentation degree increases as we move from coarse to fine tokenization. This increased fragmentation, as we will see in Section 4, enhances the complexity of recombining the tokens of the Arabic output. However, this also has a positive effect, as it decreases the vocabulary (word types), which results in lower out-of-vocabulary counts on a held out test set. For each tokenization scheme, Table 3 shows the number of tokens and types of the Arabic side of the training data, and the OOV on a held-out set. The held-out set comprises of 728 sentences and 18277 unsegmented words from the NIST MT02 test set . Table 3. tokens, and types count of the Arabic side of the training data for the different schemes and the outof-vocabulary tokens on NIST MT02 test set.

Arabic Automatic Detokenization
The Arabic output produced by all MT systems trained using schemes S0-S5, S5SF, S5SF is segmented and need to be recombined in order to produce the final Arabic text. We call the process of recombining the Arabic output as detokenization.

Challenges of Arabic Detokenization
Arabic detokenization is far from being a simple concatenation of the tokens, as several morphological adjustments, driven by morpho-phonological rules, apply to the tokens when they are combined. The first three rows of Table 4. include examples of such morphological adjustments. Another challenging aspect of Arabic detokenization is that in some cases it could be ambiguous i.e. tokens could be combined into more than one grammatically correct form. Examples of Arabic detokenization ambiguity are given in Table 5. The first column in Table 5 gives the token sequence while the second column lists all the possible com-bined forms for this sequence. Each possible combined from is followed by the probability, computed over the training data, of this word being the combined form of the given token sequence appearing in the training data. The second line of Table 5 demonstrated that the combined form corresponding to the sequence token could depend on the morphological case of the word base. In this case the word base >bnA "sons" is a noun which could have three cases: nominative, accusative, genitive.

Detokenization techniques
We experiment with six different detokenization techniques with increasing complexity: • C: This is the most trivial technique which just concatenates the tokens of the segmented form together. • R: This technique uses manually defined morphological adjustments rules to combine the Arabic tokens. Examples of such rules are given in Table 4. • T: Uses a table derived from the Arabic side of training data to map the segmented form of the word to its original enriched form. If a segmented word has more than one original form then it is mapped to the most frequent one. A segmented word that does not appear in the table will be mapped to the output as is. For example, in Table 5. the segmented word >bnA' +hA is associated with 3 original forms in training data with different frequencies (normalized to probabilities). According to the T technique, it will be mapped to >bnA}hA as it is the form with the highest probability. • T+C: Similar to the T technique but backs off to the C method when encountering an unknown token sequence. For evaluating the detokenization schemes described above, a test set of 50k (~1.3M words) sentences were randomly selected from the Arabic training corpora. The rest of the Arabic corpora was used to train the tables for the last four detokinzation techniques. The 5-gram language models used by the T+LM+R technique was trained using the whole training data. Table 6. lists the percentage of sentence error rate (SER), of the six detokinzation techniques for all Arabic tokenizations schemes that we experiment with. A general theme that we notice by looking at Table 6. is that the SER increases as we move from coarse to fine tokenization scheme: The more fragmented the text the harder it is to recombine.
Going from left to right over the results in Table  6, we notice that the SER drops with the increase in the complexity of the detokeniztion technique. However, this drop in SER diminishes as we move up the complexity ladder. The extremely high SER of the C technique demonstrates that detokenization is far from being a simple concatenation of the tokens. From the R column we see that introducing morphological adjustments rules gives a significant improvement over the simple concatenation especially for the fine segmentations. An additional significant improvement in SER is achieved, when using tables learned from the data as in the T technique. In an analysis of the output of the R technique we found that some of the combination errors are caused by tokenization errors introduced by the morphological analyzer 3 . These kind of errors are fixed using the T method, which demonstrates the advantageous ability of the T method to successfully cope with errors introduced by the morphological analyzer.
Additional improvement in SER is obtained when backing off to the C method, as can be seen from the T+C column in Table 6. Backing off to R gives minor improvement over backing off to C. Furthermore, using a language model in the detokinization process, as in the T+LM+R, gives a very small improvement over the T+R technique. This very small improvement in SER comes at a costly price of 9X increase in detoknization time besides having to load the LM into memory (>1GB). For these reasons we use the (T+R) method for detokinizing the output of our SMT systems during evaluation in the Section 6.

Training and Testing Data
We use the NIST09 Constrained Training Condition (NIST09) Resources 4 to train and test the broad-coverage English-to-Arabic phrase based statistical machine translation systems.

Training Data
The Arabic-English parallel training data available within the NIST09 resources consists of about 5 million sentence pairs with about 150 million and 172 million words on the Arabic and English side respectively. The English side of the training corpora was first tokenized using the Stanford English tokenizer 5 then lower cased. The Arabic side was The main reason for this preprocessing step is that in future works the best system build here will be extended with syntactic information based on parsing the training data using the Stanford parser. enriched and the different tokenization generated using the Morphological Analysis and Disambiguation for Arabic (MADA) toolkit (Habash and Rambow, 2005). The parallel training corpora was then filtered by first removing sentence pairs longer than 99 on either side then deleting unbalanced sentence pairs with ratio more than a 4-to-1 in either direction. After preprocessing and filtering, the parallel corpora consisted of 4,867,675 sentence pairs with 152 million words on the English side. The Arabic side of the training corpora is used to train nine 5gram language models for the different tokenization schemes using the SRILM toolkit (Stolcke, 2002). An additional two 7-gram language models were trained for the S3-S5 tokenization schemes in order to account for the increase in length of the segmented Arabic. Tokens and type counts of the processed Arabic training corpora, for the different tokenization schemes, is given in Table 3.
The processed and filtered parallel corpora was then aligned using MGIZA++ (Gao and Vogel, 2008); an extended and optimized multi-threaded version of GIZA++ (Och and Ney, 2003). The Moses toolkit (Koehn et. al, 2007) is then used to symmetrize the alignement using the grow-diagfinal-and heuristic and to extract phrases with maximum length of 7. A distortion model lexically conditioned on both the Arabic phrase and English phrase is then trained.

Tuning and testing sets
We use existing Arabic-to-English test sets available within the NIST09 resources to construct our English-to-Arabic tuning and test sets. As all NIST09 test sets were intended for use in Arabicto-English machine translation, each Arabic source sentences is associated with four English references. From such a test sets, we construct an English-to-Arabic test set by pairing the Arabic source with the first English reference giving us single reference test set. We use 728 sentences from NIST09 MT02 test to construct a tuning set while the whole MT03, MT04, and MT05 are used to construct the test sets. Both Source and target sides of the tuning and test sets were preprocessed as described above. Table 7 includes information about all these test sets (after preprocessing), in-. cluding number of sentences and tokens, and division of sentences according to their genres.

Results
We test and compare the performance of nine PBSMT systems trained using the different tokenization schemes. The systems use the translation, reordering and language models described in Section 5. The decoding weights for these components were optimized for Bleu-4 (Papineni et al., 2002) on the MT02 tuning set using an implementation of the Minimum Error Rate Training procedure (Och, 2003). We use the Moses ( Koehn et. al, 2007) decoder with a distortion window of 6 is to decode the systems on the MT03, MT04, and MT05 test sets. As discussed in 4.2 we use the T+R detokenization technique to recombine the Arabic tokens of the different segmentation schemes. The evaluation results reported are all on the detokenized output of systems evaluated against unsegmented enriched single reference test sets.
We report the results on all test sets using a number of evaluation metrics including BLEU-4, TER 5 (Snover and Dorr, 2006), and METEOR 6 (Lavie and Denkowski, 2008). Table 8 lists the translation results of all the systems on MT03 using all the evaluation metrics discussed earlier. Table 9 shows the results on the MT04 test set while the results on MT05 test set are given in Table 10.
All statement below about the difference in BLEU score were tested for Statistical significance using paired bootstrap resampling (Koehn, 2004) with 95% confidence interval. Looking at the results we see that across all test sets S0/S4 perform 6    The results also show that a simple segmentation scheme S0 which just splits off the w+ (and) can perform as good as the best and more complicated S4 (ATBv3 equivalent) scheme. The simplicity of S0 gives it advantage over the S4 as it can be both generated and recombined with lower error rate in the tokenization and the detokenization processes respectively as described in Section 4.
Comparing the scores of different schemes across all test sets we are also able to come up with the following observation: • S1 outperforms S2 on all test sets which indicates that splitting off the particle proclitics (PART+) can hurt the performance. • S4 outperforms S2 on all test sets indicating that splitting off pronominal enclitics (PRON+) has a positive effect on the performance of the system • S4 outperforms S5 on all test sets indicating that splitting off the definite article Al+ hurts the performance. • S3 and S4 perform about the same on all test sets indicating that splitting off the s+ (will) clititc has no significant effect on the performance of the system. • Comparing S4 with S4SF and S5 with S5SF we see that using morphological features could only benefit the system.
• Comparing S4 with S4.7gram and S5 with S5,7gram on all test sets indicates that using higher order (>5) n-grams for highly fragmented schemes has no significant effect on the performance of the system.

Conclusions and Future Work
In this work we investigated the impact of Arabic morphological segmentation on the performance of a broad-coverage English-to-Arabic SMT system. We explored the full spectrum of Arabic segmentation schemes ranging from full word form to fully segmented forms and examined the effects on system performance. Our results show a difference of 2.61 BLEU points between the best and worst segmentation schemes indicating that the choice of the segmentation scheme has a significant effect on the performance of a PBSMT system in a large data scenario. We also show that a simple segmentation scheme which just splits off the w+ (and) can perform as good as the best and more complicated (ATBv3) segmentation scheme. We also report results on a wide set of techniques for combining the segmented Arabic output.
In future work we intend to conduct an in depth analysis on the effect of segmentation scheme on the different components that make up the PBSMT system, including word alignment, the extracted phrase table, and the trained language models. We also plan to explore whether current findings extend to English-to-Arabic syntax-based and hierarchical SMT systems.