Nizar Habash
email: nizar.habash@nyu.edu

Anas Shahrour
email: anas.shahrour@nyu.edu

Muhamed Al-Khalil
email: muhamed.alkhalil@nyu.edu

Exploiting Arabic Diacritization for High Quality Automatic Annotation

Keywords: Arabic, Morphology, Annotation, Diacritization

We present a novel technique for Arabic morphological annotation. The technique utilizes diacritization to produce morphological annotations of quality comparable to human annotators. Although Arabic text is generally written without diacritics, diacritization is already available for large corpora of Arabic text in several genres. Furthermore, diacritization can be generated at a low cost for new text as it does not require specialized training beyond what educated Arabic typists know. The basic approach is to enrich the input to a state-of-the-art Arabic morphological analyzer with word diacritics (full or partial) to enhance its performance. When applied to fully diacritized text, our approach produces annotations with an accuracy of over 97% on lemma, part-of-speech, and tokenization combined.

Introduction

The automatic processing of the Arabic language is challenging for a number of reasons. Two inter-related reasons are Arabic's complex morphology and its diacritic-optional orthography [START_REF] Habash | Introduction to Arabic Natural Language Processing[END_REF]. This combination leads to the high number of about 12.8 possible analyses per word out of context [START_REF] Shahrour | Improving Arabic diacritization through syntactic analysis[END_REF]. Much research has been done on Arabic morphological disambiguation and automatic diacritization. Most of this work relies on existing morphologically annotated (i.e., contextually disambiguated) corpora. Some researchers interested only in diacritization also use diacritized corpora. The morphologically annotated corpora for Arabic are limited by size and genre. This is because the cost of creating such corpora is prohibitive as time and money must be dedicated to collect data, create guidelines, hire and train annotators, and continuously evaluate the quality of the annotations. In this paper we explore an alternative approach to Arabic morphological annotation: we exploit fully diacritized text to rerank the morphological analyses of a state-of-theart morphological tagger that expects no diacritics as input and provides not only part-of-speech, morphological features and lemmas, but also diacritizations. We evaluate and analyze the accuracy of this method in generating high quality morphologically analyzed corpora that can themselves be used for improving tools for Arabic processing, especially for less studied genres. The approach relying solely on diacritization is also very cheap in comparison to hiring specialized (linguist) annotators and training them. Although educated Arabic speakers do not use diacritics in their writing they know how to assign them reasonably well. Of course, we still expect the diacritic annotators to be well educated in Standard Arabic grammar and be fast typists. But the supply and demand, as well as the limited overhead of training is in our favor. 1 Obviously, this kind of approach can work only because we already have a mass of Arabic resources (the taggers and analyzers) that facilitate it. The idea is also applicable to other languages with similar orthographic ambiguity challenges, e.g., Hebrew and Persian. Our results on Arabic show that using our approach produces quality comparable to human manual annotation [START_REF] Maamouri | Enhancing the Arabic Treebank: a Collaborative Effort toward New Annotation Guidelines[END_REF][START_REF] Habash | CATiB: The Columbia Arabic Treebank[END_REF] and other automatic enhancement techniques [START_REF] Alkuhlani | Automatic morphological enrichment of a morphologically underspecified treebank[END_REF], reaching an accuracy of over 97% on lemma, part-of-speech, and tokenization combined. We present next some background Arabic linguistic facts and related work, followed by a discussion of our approach and a detailed evaluation of it on different genres and different degrees of diacritization.

Arabic Linguistic Facts

The Arabic script consists of two classes of symbols: letters and diacritics (Habash and Rambow, 2007;[START_REF] Habash | Introduction to Arabic Natural Language Processing[END_REF]. Whereas letters are always written, diacritics are optional.

Written Arabic text can be undiacritized, partially, or fully diacritized. Religious text such as the Holy Qur'an are fully diacritized. However, in newswire text, 1.6% of all words have at least one diacritic indicated by their author, mostly to disambiguate the text for readers [START_REF] Habash | Introduction to Arabic Natural Language Processing[END_REF]. There are three types of diacritics: vowel, nunation, and shadda. Vowel diacritics represent Arabic's three short vowels (/a/, /i/, /u/) and the absence of any vowel. The following is the same word with and without these four diacritics:

mbtsm 2 / mubtasim 'smiling'. The three nunation diacritics can only occur in word final positions in nominals (nouns, adjectives and adverbs). They represent a short vowel followed by an /n/ sound, and indicate nominal indefiniteness, e.g., mubtasim ũ /mubtasimun/ 'smiling [nominative indefinite]'. The Shadda diacritic is a consonant doubling marker, and can be com-2 Arabic transliteration is presented in the Habash-Soudi-Buckwalter scheme (Habash et al., 2007b): (in alphabetical order) Â b t θ j H x d ð r z s š S D T Ď ς γ f q k l m n h w y and the additional symbols: ' , Â , Ǎ , Ā , ŵ , ŷ , h , ý .

bined with vowel or nunation diacritics, e.g., compare kataba (no Shadda) 'he wrote', with kat∼aba /kattaba/ (with Shadda) 'he dictated'. Functionally, diacritics can be split into: lexemic diacritics and inflectional diacritics (Habash and Rambow, 2007;[START_REF] Habash | Introduction to Arabic Natural Language Processing[END_REF]. Lexemic diacritics distinguish between two lexemes. For example, the diacritization difference between the lexemes kAtib 'writer' and kAtab 'he corresponded' distinguish between the meanings of the word rather than their inflections. Inflectional diacritics distinguish different inflected forms (morpho-syntactic variants) of the same lexeme. For instance, the following three forms of the word kAtb 'writer' vary in terms of their 2015) demonstrated that the use of syntactic parsing can help improve the diacritization choice. For more information on Arabic diacritization and morphology, see (Habash and Rambow, 2007;Habash et al., 2007a;[START_REF] Habash | Introduction to Arabic Natural Language Processing[END_REF].

Related Work

There have been many notable efforts on the development of annotated Arabic language corpora [START_REF] Maamouri | Resources for Natural Language Processing at the Linguistic Data Consortium[END_REF][START_REF] Maamouri | The Penn Arabic Treebank: Building a Large-Scale Annotated Arabic Corpus[END_REF][START_REF] Smrž | The Other Arabic Treebank: Prague Dependencies and Functions[END_REF][START_REF] Habash | CATiB: The Columbia Arabic Treebank[END_REF][START_REF] Alansary | The international corpus of Arabic: Compilation, analysis and evaluation[END_REF]. However, most contributions adopted manual annotation and morphological features, which is a time-consuming process that requires lots of training for annotators. The effort to build the Penn Arabic Treebank at the Linguistic Data Consortium [START_REF] Maamouri | Resources for Natural Language Processing at the Linguistic Data Consortium[END_REF][START_REF] Maamouri | The Penn Arabic Treebank: Building a Large-Scale Annotated Arabic Corpus[END_REF], made active use of morphological analyzers [START_REF] Buckwalter | Buckwalter Arabic Morphological Analyzer Version 2.0[END_REF][START_REF] Graff | Standard Arabic Morphological Analyzer (SAMA) Version 3.1[END_REF] to jointly select diacritizations and morphological tags.

Much work has been done on Arabic diacritization [START_REF] Vergyri | Automatic Diacritization of Arabic for Acoustic Modeling in Speech Recognition[END_REF][START_REF] Nelken | Arabic Diacritization Using Weighted Finite-State Transducers[END_REF][START_REF] Zitouni | Maximum entropy based restoration of Arabic diacritics[END_REF]Habash and Rambow, 2007;[START_REF] Alghamdi | KACST Arabic diacritizer[END_REF][START_REF] Rashwan | A hybrid system for automatic Arabic diacritization[END_REF][START_REF] Baghdadi | Majma' Al-damanat[END_REF][START_REF] Hadj Ameur | Restoration of Arabic diacritics using a multilevel statistical model[END_REF][START_REF] Abandah | Automatic diacritization of Arabic text using recurrent neural networks[END_REF][START_REF] Bouamor | A pilot study on Arabic multi-genre corpus diacritization[END_REF][START_REF] Shahrour | Improving Arabic diacritization through syntactic analysis[END_REF][START_REF] Belinkov | Arabic diacritization with recurrent neural networks[END_REF]. While previous approaches focused on improving the quality of automatic diacritization, sometimes through the use of improved morphological and syntactic feature predictions, this work utilizes diacritization to generate high quality predictions of morphological features.

A method for automatic morphological enrichment of a morphologically underspecified treebank has was presented in [START_REF] Alkuhlani | Automatic morphological enrichment of a morphologically underspecified treebank[END_REF], extending previous efforts on case prediction over syntactic trees by (Habash et al., 2007a). Our work relates to their work by the virtue of using limited information from annotators (in our case, diacritizers) to automatically generate annotations for all morphological features. Building a treebank however is timeconsuming since it requires training annotators for specific tools and conventions, while typing diacritized text can be quickly done by an educated Arabic typist.

Approach

Undiacritized Arabic words are highly ambiguous: in our training data, words had an average of 12.8 analyses per word, most of which are associated with different diacritizations. Morphological analysis refers to the process of determining all the possible morphological analyses for a specific word out of context. Each Analysis has a single diacritized form, part-of-speech, and other morphological features. Table 1 shows a list of analyses produced by the morphological analyzer for the word byn. Morphological tagging (aka morphological disambiguation) refers to the choosing of a morphological analysis in a specific context. Our approach is to generate high-quality automatic morphological tagging output by exploiting full diacritization information. Our baseline system is the state-of-the-art Arabic morphological tagger MADAMIRA [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF] which uses the Standard Arabic Morphological Analyzer (SAMA) [START_REF] Graff | Standard Arabic Morphological Analyzer (SAMA) Version 3.1[END_REF]. The morphological analyzer produces a list of possible analyses for each word, and the tagger ranks the mentioned list and selects the optimal full morphological tag for each word in context. MADAMIRA does not expect any diacritics as input and in fact it ignores any naturally occurring diacritics. In our approach, we use the original full diacritics of the words to filter the ranked choices. Each analysis gets a score based on the edit distance of its associated diacritization with the input diacritization. The analysis with the highest rank and lowest edit distance is selected as the incontext analysis. Since MADAMIRA in default mode produces no analyses sometimes (lexical out-of-vocabulary), we utilize its back off mode to produce all possible analyses (including diacritizations for affixes only).

Diacritization variants While Arabic diacritization conventions are generally well established, we found a number of common stylistic variants in our data sets:

• The long vowel /a:/ is written as aA or A (without the short vowel diacritic).

• The Alif Wasla letter Ä is sometimes written as a bare

Alif A.

• The Alif Hamza Below Ǎi is sometimes written without the short vowel diacritic Ǎ.

• The word-final Alif -Fatha nunation character pair can appear as ãA or Aã. • The Sukun diacritic, indicating absence of vowelization can be written or omitted even with (almost) full diacritization.

To make our approach independent of these variants, we normalized them to one form in the edit-distance calculation and the system evaluations. In the above mentioned example pairs, we always normalized to the second variant.

As for the Sukun, we always dropped it.

Evaluation

In this section, we present our experimental setup, evaluation metrics and experimental results.

Experimental Setup

Morphological tagger For our baseline system, we use the MADAMIRA morphological tagger [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF], which was trained on the training portion of the Penn Arabic Treebank (PATB, parts 1, 2 and 3) [START_REF] Maamouri | The Penn Arabic Treebank: Building a Large-Scale Annotated Arabic Corpus[END_REF][START_REF] Maamouri | Diacritization: A challenge to Arabic treebank annotation and parsing[END_REF][START_REF] Maamouri | Creating a Methodology for Large-Scale Correction of Treebank Annotation: The Case of the Arabic Treebank[END_REF] along the recommendations of [START_REF] Diab | LDC Arabic treebanks and associated corpora: Data divisions manual[END_REF]. Used texts We selected three fully diacritized and morphologically annotated texts from three genres to report on.

• A newswire genre text (Newswire) is selected from the PATB and includes all of the development set (about 63K words) along the recommendations of [START_REF] Diab | LDC Arabic treebanks and associated corpora: Data divisions manual[END_REF]. The morphological annotation was done by the LDC and includes all morphological features.

• A children's novel text (Novel) is selected to cover the first chapter (1,175 words) of a book titled wzh AlslTAn 'The Sultan's Goose' (Kilany, 2013). The morphological annotation was done by the authors and only included diacritization, lemma, POS and tokenization.

• An Islamic jurisprudence text (Religious) is selected to cover the first four pages (970 words) of a book titled mjmς AlDmAnAt 'Congregation of Guarantees' [START_REF] Baghdadi | Majma' Al-damanat[END_REF]. The morphological annotation was done by the authors and only included diacritization, lemma, POS and tokenization.

The choice of the different genres is intended to measure the effect of similarity between the training data of the baseline morphological tagger (Newswire) and other genres. In later sections we refer to experiments involving Newswire as in-genre since the text matches the genre of the morphological tagger; and we accordingly refer to the nonnewswire genre experiments as out-of-genre.

Evaluation Metrics

The evaluation was conducted across several accuracy metrics (all on the word level):

• Diac: Percentage of words where the chosen analysis has the correct fully diacritized form (with exact spelling).

• Lex: Percentage of words where the chosen analysis has the correct lemma.

• POS: Percentage of words where the chosen analysis has the correct part-of-speech.

• Tok: Percentage of words where the chosen analysis has the correct tokenization.

• Diac+Lex+POS+Tok: Percentage of words where the chosen analysis has the correct diacritization, lemma, part-of-speech, and tokenization combined.

• Star: Percentage of words where the chosen analysis is perfectly correct (that is, all the morphological features such as gender, number, person, etc. match their gold values). This is the strictest possible metric and is only used for Newswire text.

Experimental Results

We present next three sets of results on in-genre experiments, out-of-genre experiments and an investigation in the effect of partial diacritization.

In-Genre Experiments

Four experiments were designed to use the baseline system in different ways. One variable was whether to use the tagger system to rank the list of analyses after the analyzer or to use a random ranking instead. To report the results of random ranking, two ways of ranking were performed: alphabetical, and reversed alphabetical, and the average performance was reported. The second variable was the option of using the input diacritization to filter the list of analyses.

The filter examines the diacritization of each analysis and keeps only the one(s) with the minimum Levenshtein's edit distance to the input diacritization. The system's output is the top analysis in the final list after ranking and filtering. diacritization filter without the morphological analyzer performs as well as the best system on diacritization, but worse than the morphological analyzer without the filter on other features. A combination of both the morphological analyzer and the diacritization filter is needed to produce highquality annotations. The annotation scores produced are comparable to reported numbers on inter-annotator agreement and enhanced annotations [START_REF] Maamouri | Enhancing the Arabic Treebank: a Collaborative Effort toward New Annotation Guidelines[END_REF][START_REF] Habash | CATiB: The Columbia Arabic Treebank[END_REF][START_REF] Alkuhlani | Automatic morphological enrichment of a morphologically underspecified treebank[END_REF] (although it is hard to make direct apple-to-apple comparisons with the cited efforts).

The best system achieves 93% error reduction on diacritization, 85% on case, 70-80% on voice, mood, state, and the Buckwalter tag, 55-69% on lemma, aspect, person, rationality, and token sequences, 40-49% on gender, number, and enclitics, 18-39% on proclitics, part-of-speech, and gloss. The detailed error reduction for all the features are mentioned in Table 4.

Out-of-Genre Experiments

A comparison between the baseline and the best system was conducted on two extra data sets (of novel, and religious genres), and the results are listed in Table 3. Similar improvements to the previous results can be seen, which suggests that this approach can be used to annotate text of new genres that the morphological tagger was not trained on.

Error analysis We performed a manual investigation of the types of errors in our best system. The error analysis was performed on 1000 words of newswire, and on the full text of the novel and the religious genres. The errors are classified into the following categories according to their order in Table 5.:

• No (Correct) Analysis: Words for which no analysis was provided by the morphological analyzer, or no provided analysis was completely correct.

• Input Error: Errors caused by typos in the input text.

• Inter-Word Diac: Errors caused by phonological epenthesis between words, which is not modeled by • Lemma: Errors in the prediction of the lemma.

It is worth mentioning that we evaluate against a finegrained POS tag-set which includes 35 tags. Most of POS errors (nominals and closed classes) describe subtle differences within the same class of POS tags, and will disappear when evaluating against a coarser POS tag-set such as CATiB [START_REF] Habash | CATiB: The Columbia Arabic Treebank[END_REF].

Partial Diacritization

In this section we study the effect of using partially diacritized text instead of fully diacritized text. We recognize that using less diacritics is bound to lower the overall quality of the resulting morphological choices; however, we want to understand the nature of the change in quality on different metrics. Using partially diacritized input instead of fully diacritized input causes a major drop in the performance since the editdistance measure we use interprets missing diacritics as nodiacritics (or Sukuns) as opposed under-specified diacritics.

To address this issue, we created a second mode of the edit distance that does not penalize disagreements involving diacritic underspecification (i.e. missing diacritics) in the input. 3 Figure 1 shows the performance of our system with the partial-dicritic mode on inputs with different diacritization rates. A linear correlation between the diacritization rate and the performance on all features can be seen. The partially diacritized text is constructed from the fully diacritized form by passing on every diacritic in the text and deciding whether to keep it or not by comparing the output of a random function (in the range of 0-100%) to the diacritization rate. Three settings are illustrated: Default is when all diacritics has the same chance of being kept. Drop last diac is the same as Default except that the last diacritic is always dropped. Keep last diac is the same as Default except that the last diacritic is always kept. It can be seen from the figure that keeping only the last diacritic (around 23% of total diacritics) gives similar score on predicted dia-3 It is worth noting that the partial-diacritic mode performs slightly worse than the full-diacritic mode on fully diacritized text because the fully diacritized gold in fact does not have a final diacritic in a small number of cases, which are interpreted as instances of under specification instead of diacritic absence. This results in a drop of 0.6% in the Star score for the fully diacritized newswire genre data with partial-diacritic edit distance compared to full-diacritic edit distance. critization to keeping 80% of the diacritics randomly. This is due to the tagger's weakness at predicting the last diacritic. On lemma, POS, and tokenization, the last diacritic performs in a proportional way to its ratio in the text. It's worth mentioning that the fully diacritized form contains not only extra diacritics, but also spelling corrections (in around 12% of the words). This is why the partial diacritization system performs better than the baseline even with a 0% diacritization rate (0.3% absolute increase on Star). On the other hand, applying the partial diacritization system on a raw text performs worse than the baseline (0.4% absolute decrease on Star).

Conclusion and Future Work

We have demonstrated a solution to Arabic rich morphological annotation which relies on diacritizations that can be provided by educated Arabic speakers who do not need to be trained in specialized morphological tag sets and guidelines. The solution can work on fully or partially diacritized text. We plan to use this technique to automatically generate large annotated Arabic corpora in less studied genres. The corpora will be diacritized by volunteers and paid typists (potentially using crowd-sourcing). The generated annotations can then be used to enhance Arabic tools.

Figure 1 :

 1 Figure 1: System performance on partially diacritized text.

Table 1 :

 1 Analyses produced by the morphological analyzer for the word byn.

	POS	Diac	Gloss
	PV+PVSUFF_SUBJ:3MS	bay∼ana	He demonstrated
	PV+PVSUFF_SUBJ:3FP	bay∼an∼a They demonstrated (f.p)
	NOUN_PROP	biyn	Ben
	ADJ	bay∼in	Clear
	PREP	bayn	Between, among

• The word-final Alif Maqsura -Fatha nunation character pair can appear as ãý or ýã.

Table 2

 2

	Initial Ranking Filter	Diac Lex POS Tok Diac+Lex+POS+Tok Star
	Random	none	35.0 71.6 71.5 79.4	31.8	30.3
	Morph. Tagger	none	87.8 96.7 96.5 98.4	86.6	85.6
	Random	Full Diac 99.1 96.2 86.2 98.5	85.5	78.6
	Morph. Tagger	Full Diac 99.1 98.7 97.4 99.3	97.1	95.8

. shows the results of the four experiments. The best approach is to use the initial ranking of the morphological tagger and filter the results based on the input diacritization. We achieve 10.2% absolute improvement on the full analysis over the baseline (71% error reduction). Using the

Table 2 :

 2 System performance on an in-genre text (63K words of newswire articles).

	Genre	System	Diac Lex POS Tok Diac+Lex+POS+Tok
	Newswire Tagger	87.8 96.7 96.5 98.4	86.6
	Newswire Tagger+Full Diac Filter 99.1 98.7 97.4 99.3	97.1
	Novel	Tagger	82.8 93.0 93.8 96.5	81.0
	Novel	Tagger+Full Diac Filter 98.2 97.7 96.0 99.0	95.6
	Religious Tagger	74.8 89.8 92.3 96.4	72.4
	Religious Tagger+Full Diac Filter 97.2 95.6 95.3 98.1	92.8

Table 3 :

 3 System performance on three genres of text.

Table 4 :

 4 Percentage of error reduction for all features.

	Feature	Tagger Tagger+Filter Error Reduction
	Diacritization	87.8	99.1	92.7
	Case	90.5	98.6	85.2
	Voice	99.1	99.8	76.6
	Buckwalter Tag	85.6	95.9	71.6
	Mood	99.1	99.7	70.6
	State	96.7	99.0	69.9
	Aspect	99.3	99.8	67.8
	Lemma	96.7	98.7	62.1
	Person	99.2	99.7	62.0
	Rationality	99.2	99.7	56.9
	Tokenization	98.4	99.3	56.3
	Gender	99.3	99.6	49.0
	Enclitic 0	99.5	99.8	48.8
	Number	99.4	99.6	40.8
	Proclitic 1	99.6	99.7	39.1
	Proclitic 0	99.6	99.7	31.6
	Gloss	92.9	95.1	30.5
	POS	96.5	97.4	27.0
	Proclitic 3	99.9	99.9	25.0
	Proclitic 2	99.6	99.7	17.7
	diac+pos+lemma+tok 86.6	97.1	78.6
	Star	85.6	95.8	71.1
	the tagger system.
	• POS: Errors in POS prediction: Nominals are noun-
	adjective errors. Closed classes are errors in closed
	classes of POS, such as particles, pronouns and con-
	junctions. Other are types of POS errors other than
	the aforementioned ones.

Table 5 :

 5 Percentage of errors by type among different genres of text.

	Error Type	Newswire Novel Religious
	No Analysis	31.3	5.8	15.7
	No Correct Analysis	0	26.9	21.4
	Input Error	0	5.8	2.9
	Inter-Word Diac	0	3.8	0
	POS: Nominals	37.5	28.8	28.6
	POS: Closed Classes	6.3	23.1	20.0
	POS: Other	6.3	3.8	4.3
	Lemma	18.8	1.9	7.1