1 Introduction
Spelling correction solutions have significant importance for a variety of applications and NLP tools including text authoring, OCR (Tong and Evans Reference Tong and Evans1996), search query processing (Gao et al. Reference Gao, Li, Micol, Quirk and Sun2010), pre-editing or post-editing for parsing and machine translation (El Kholy and Habash Reference El Kholy and Habash2010; Och and Genzel Reference Och and Genzel2013), intelligent tutoring systems (Heift and Rimrott Reference Heift and Rimrott2008), etc. In this introduction, we define the spelling error detection and correction problem, present a brief account of relevant work, outline core aspects of Arabic morphology and orthography, and provide a summary of our research methodology.
1.1 Problem definition
The spelling correction problem is formally defined (Brill and Moore Reference Brill and Moore2000) as: given an alphabet Σ, a dictionary D consisting of strings in Σ⋆, and a spelling error s, where s ∉ D and s ∈ Σ⋆, find the correction c, where c ∈ D, and c is most likely to have been erroneously typed as s. This is treated as a probabilistic problem formulated as in (1) (Kernigan, Church and Gale Reference Kernigan, Church and Gale1990; Brill and Moore Reference Brill and Moore2000; Norvig, Reference Norvig, Segaran and Hammerbacher2009):
\begin{equation}
argmax_{c} P(s | c) P(c)
\end{equation}
Here c is the correction, s is the spelling error, P(c) is the probability that c is the correct word (or the language model), and P(s|c) is the probability that s is typed when c is intended (this is called the error model or noisy channel model), argmaxc is the scoring mechanism that computes the correction c that maximizes the probability P(s|c)P(c).
Based on this definition, we assume that a good spelling correction system needs a balanced division of labor between the three main components: the dictionary, error model and language model. In this paper, we show that in the error model there is a direct relationship between the number of correction candidates and the likelihood of finding the correct correction: the larger the number of candidates, the more likely the error model is to find the best correction. At the same time, in the language model there is an inverse relationship between the number of candidates and the ability of the model to decide on the desired correction: the larger the number of candidates, the less likely the language model will be successful in making the right choice. A language model is negatively affected by a high dimensional search space. A language model is also negatively affected by noise in the data when the size of the data is not large.
In the error model, we deploy the dictionary in a finite-state automaton to propose candidate corrections for misspelled words within a specified edit distance (Ukkonen Reference Ukkonen1983; Hulden Reference Hulden2009b) from the correct words. Based on an empirical analysis of the types of errors, we devise a set of frequency-based rules for re-ranking the candidates generated via edit distance operations so that when the list of candidates is pruned, we do not lose many plausible correction candidates.
For the n-gram language model, we use the Arabic Gigaword Corpus 5th Edition (Parker et al. Reference Parker, Graff, Chen, Kong and Maeda2011), the largest available so far for Arabic, and an additional corpus of news articles crawled from the Al-Jazeera web site. The Gigaword corpus is divided into nine data sets according to the data sources, such as Agence France-Presse, Xinhua News Agency, An Nahar, Al Hayat, etc. We analyze the various data sets to estimate the amount of noise (the ratio of spelling errors against correct text), and our n-gram language modeling experiments show that there is clear association between the amount of noise and the disambiguation quality of the model.
To sum up, the system architecture is a pipeline of three components where the output of one component serves as the input to the next, and these components are:
-
(1) Error detection through a dictionary (or a reference word list).
-
(2) Candidate generation through edit distance as implemented in a finite state compiler.
-
(3) Best candidate selection using an n-gram language model.
1.2 Arabic morphology and orthography
Arabic has a rich and complex morphology as it applies both concatenative and non-concatenative morphotactics (Beesley Reference Beesley1998; Ratcliffe Reference Ratcliffe1998). Concatenative morphotactics models the addition of clitics and affixes to the word stem without affecting the internal structure of the word, such as
‘$akara’Footnote
1
‘to thank’, which can be inflected as,
‘wa-$akara-to-hu’ ‘and she thanked him’. On the other hand, non-concatenative morphotactics models the employment of internal alterations to a word in order to express both inflectional and derivational phenomena, such as
‘dar~asa’ ‘to teach’, which can be inflected as
‘dur~isa’ in the passive and
‘dar~is’ in the imperative. In Arabic morphology this is typically modeled by a group of morphological templates, or patterns.
Both concatenative and non-concatenative morphotactics are frequently seen working together in words such as
‘wa-sa-yusotadoEa-wona’ ‘and they will be summoned’ where non-concatenative morphotactics is used to form the passive, while concatenative morphotactics are used to produce the tense, number and person, as well as the affixes of the conjunction and future particles. Arabic has a wealth of morphemes that express various morpho-syntactic features, such as tense, person, number, gender, voice and mood for verbs, and number, gender, and definiteness for nouns, in additional to a varied outer layer of clitics. This is the basis of the considerable generative power of the Arabic morphology. This is illustrated by the fact that a verb, such as
‘$sakara’, generates 2,552 valid forms, and a noun, such as
‘muEal~im’ ‘teacher’, generates 519 valid forms (Attia Reference Attia2006).
Arabic orthography has a unified and standardized set of rules that are almost unanimously agreed upon by traditional grammarians. However, on the one hand, some of these rules are too complicated to be grasped and followed by everybody, and on the other hand, writers will sometimes opt for speed, when writing on a keyboard, and become reluctant to press the shift key, leading them to use one character to represent many others. For example the bare alif
‘A’ is written without the shift key, but the other hamzated forms, such as
‘>’,
‘<’, and
‘|’ will need the shift key. This led to what is called ‘typographic errors’ or ‘orthographic variations’ (Buckwalter Reference Buckwalter2004a). These orthographic variations, which can sometimes be referred to as sub-standard spellings, or soft spelling errors, are basically related to the possible overlap between orthographically similar letters in three categories: (a) the various shapes of hamzahs (
), (b) taa marboutah and haa (
), and (c) yaa and alif maqsoura (
). It should also be noted that, in modern writing, vowel marks (or diacritics) are normally omitted, which means that
is merely written as
. This leads to a substantial amount of ambiguity when deciding on the correct vowelization, an issue that has a considerable impact on NLP tasks related to POS tagging and speech applications. This problem, however, is not relevant to the current task as we only deal with unvowelized text as it appears in the newspapers.
1.3 Relevant work
Detecting and correcting spelling errors is one of the problems that intrigued NLP researchers from an early stage. Damerau (Reference Damerau1964) was among the first researchers to address this issue. He developed a rule-based string-matching technique for error correction, based on four edit operations (substitution, insertion, deletion, and transposition), but his work was limited by memory and computation constraints at the time. Church and Gale (Reference Church and Gale1991) were the first to rank the list of spelling candidates by probability scores (considering word bigram probabilities) based on a noisy channel model. Kukich (Reference Kukich1992), in her survey, classified work on spelling errors into three categories: (a) error detection, (b) isolated word correction, and (c) context-dependent (or context-sensitive) correction. Brill and Moore (Reference Brill and Moore2000) tried to improve the noisy channel model by learning generic string-to-string edits, along with the probabilities of each of these edits. Van Delden, Bracewell and Gomez (Reference van Delden, Bracewell and Gomez2004) used machine-learning methods (supervised and unsupervised) for handling spelling errors, including errors related to word merging and splitting.
Beside n-gram language modeling, statistical machine t\ranslation (SMT) has also been used for the task of spelling correction. Han and Baldwin (Reference Han and Baldwin2011) perform normalization of ill-formed words in Twitter short messages. They generate a text normalization data set, and then use a phrase-based SMT for the selection of candidates. Wu, Chiu and Chang (Reference Wu, Chiu and Chang2013) use a similar method in building a spelling error correction and detection system for Chinese using a decoder based on the SMT model for correction.
In our research, we address the spelling error detection and correction problem for Arabic, a morphologically rich language with a large array of orthographic variation. We focus on isolated word errors, i.e. non-word spelling errors, or strings that do not form valid words in the language. At the current stage, we do not handle context-sensitive errors.
The problem of spell checking and spelling error correction for Arabic has been investigated in a number of papers. Shaalan, Allam and Gomah (Reference Shaalan, Allam and Gomah2003), Shaalan, Magdy and Fahmy (Reference Shaalan, Magdy and Fahmy2013), and Alfaifi and Atwell (Reference Alfaifi and Atwell2012) provide characterization and classification of spelling errors in Arabic. Haddad and Yaseen (Reference Haddad and Yaseen2007) propose a hybrid approach that utilizes morphological knowledge to formulate morphographemic rules to specify the word recognition and non-word correction process. For correction, they use two probabilistic measures: Root-Pattern Predictive Value and Pattern-Root Predictive Value. They also consider keyboard effect and letter–sound similarity. No testing of the system performance has been reported. Hassan, Noeman and Hassan (Reference Hassan, Noeman and Hassan2008) develop a language independent system that uses finite state automata to propose candidate corrections within a specified edit distance from the misspelled word. After generating candidates, a word-based language model is used to assign scores to the candidates and choose the best correction in the given context. They use an Arabic dictionary of 526,492 full form entries and test it on 556 errors. However, they do not specify the data the language model is trained on or the order of the n-gram model. They also do not indicate whether the test errors are actual errors extracted from real texts or artificially generated. Furthermore, their system is not compared to any other existing systems.
Shaalan et al. (Reference Shaalan, Samih, Attia, Pecina and Genabith2012) use the Noisy Channel Model trained on word-based unigrams for spelling correction, but their system performs poorly against the Microsoft Spell Checker. Alkanhal et al. (Reference Alkanhal, Al-Badrashiny, Alghamdi and Al-Qabbany2012) developed a spelling error detection and correction system for Arabic directed mainly towards data entry errors, but the problem of their work is that they test on the development set which could make their work subject to overfitting. Moreover, the small size of their dictionary (427,000 words) questions the coverage of their model when applied to other domains.
In recent years, there has been a surge of interest in spelling correction for Arabic. The QALB (Qatar Arabic Language Bank) projectFootnote 2 has started as a joint venture between CMU-Qatar and Columbia University, with the aim of building a corpus of manually corrected Arabic text for building automatic correction tools for Arabic text. They released the guidelines in Zaghouani et al. (Reference Zaghouani, Mohit, Habash, Obeid, Tomeh, Rozovskaya, Farra, Alkuhlani and Oflazer2014). The group has also participated in the EMNLP 2014 Conference with a shared task on Automatic Arabic Error CorrectionFootnote 3 . However, the domain in the QALB shared task is user comments (or unedited text), while the domain of our project is edited news articles. The type of errors handled in the QALB data is punctuation errors (accounting for 40% of all errors), grammar errors, real-spelling errors and non-word spelling errors, beside normalization of numbers and colloquial words, but our data is focused only on formal non-word spelling errors.
1.4 Our methodology
Our research differs from the previous work on Arabic in a number of respects: we use an n-gram language model (mainly bigrams) trained on the largest available corpus to date, the Arabic Gigaword Corpus 5th Edition, supplemented by news data crawled automatically from the Al-Jazeera web site. In addition, we provide frequency-based typification of the spelling errors by comparing the errors with the gold correction and characterizing the edit operations involved. Based on this classification, we develop frequency-based re-ranking rules for reordering and constraining the number of candidates generated via edit distance and integrate them into the overall model. Furthermore, we show that careful selection of the language model training data based on the amount of noise present in the data, has the potential to further improve the overall results. Moreover, we focus on the importance of the dictionary (word list) in the processes of spell checking and candidate generation. We show how our word list is created and how it is more accurate in error detection than what is used in other systems.
In order to test and evaluate the various components of our system, we create a development set and a test set, and both are manually annotated by a language expert. The development set consists of 444,196 tokens (words with repetitions), and 59,979 types (unique words), collected from documents from Arabic news web sites. Of this development set, 2,027 misspelt types are manually identified and provided with gold corrections. For the test set, we collect 471,302 tokens (50,515 types) from the Watan-2004 corpus by Mourad Abbas,Footnote
4
selecting the first 1,000 articles of the International section. In the test set, 53,965 tokens (7,669 types) are manually annotated as errors, and of these errors, 49,690 tokens (5,398 types) are provided with corrections. Misspelt words that do not receive corrections are marked as ‘unknown’ either because they are colloquial or classical words, foreign or rare words, infrequent proper nouns, or simply unknown. To save time, the annotator worked on types for spelling error tagging. However, in order to assign corrections, the annotator worked on tokens; reviewing each word in context in the corpus. The reason behind this is that it is not always possible to determine without context what the correction should be. For example, the misspelt word
AHdAv, can be corrected either as
>HdAv ‘events’ or
<HdAv ‘effecting’, depending on the context. Here are the guidelines given to the annotator:
-
(1) Misspelt words need to be corrected in context in the corpus. Bear in mind that a misspelt word can have more than one possible correction depending on the context.
-
(2) If a proper noun is familiar or frequent (by consulting frequency counts on Google and Al-Jazeera web site), then it should be considered correct, otherwise it should be corrected or tagged ‘UNK’ (unknown).
-
(3) Words should be tagged UNK if they are:
-
(1) not known
-
(2) purely colloquial or classical
-
(3) foreign and unfamiliar
-
(4) extremely rare.
-
We use the development set for analyzing the types of errors and fine-tuning the parameters of the candidate re-ranking component described in Section 4 and summarized in Table 4. The blind test set is used to evaluate our system and compare it to Microsoft Word 2013, OpenOffice Ayaspell version 3.4 (released 1st of March 2014), and Google Docs (tested in April 2014). Our system performs significantly better than these three systems both in the tasks of spell checking and automatic correction (or first-order ranking).
The remainder of this paper is structured as follows: Section 2 shows how our dictionary (or word list) is created from the AraComLex finite-state morphological analyzer and generator (Attia et al. Reference Attia, Pecina, Tounsi, Toral and Genabith2011). This dictionary is compared with other available resources. Section 3 illustrates how spelling errors are detected and explains our methods of using character-based language modeling to predict valid words versus invalid words. Section 4 explains how the error model is improved by analyzing error types and deducing rules to improve the ranking produced through finite-state edit distance. Section 5 shows how the language model can be improved by selecting the right type of data to be trained on. Various data sections are analyzed to detect the amount of noise they contain, then suitable subsets of data are chosen for the n-gram language model training and the evaluation experiments. Finally, Section 6 concludes.
2 Improving the dictionary
The dictionary (or word list) is an essential component of a spell checker/corrector, as it is the reference against which the decision can be made whether a given word is correct or misspelled. It is also the reference against which correction candidates are filtered. There are various options for creating a word list for spell checking. It can be created from a corpus, a morphological analyzer/generator, or both. The quality of the word list will inevitably affect the quality of the application whether in checking errors or generating valid and plausible candidates.
For Arabic, one of the earliest word lists created for the purpose of spell checking is the Arabic SpellFootnote 5 open-source project (designed for Aspell), which relies on the Buckwalter morphological analyzer (Buckwalter Reference Buckwalter2004b). This list generates about 900,000 fully inflected words. Another dictionary is the AyaspellFootnote 6 word list, which is the official resource used in OpenOffice applications. Developers of this word list created their own morphological generator, and their word list contains about 300,000 inflected words. In this paper, we use the term ‘word’ to designate fully inflected surface word forms, while the term ‘lemma’ is used to indicate the uninflected base form of the word without affixes or clitics.
In our research, we create a very large word list for Arabic using AraComLexFootnote 7 (Attia et al. Reference Attia, Pecina, Tounsi, Toral and Genabith2011), an open-source large-scale morphological transducer. AraComLex contains 30,587 lemmas and is developed using finite state technology. There are a number of advantages of finite-state technology that makes it especially attractive in dealing with human language morphologies (Wintner Reference Wintner2008). They include bidirectionality and the ability to generate as straightforwardly as to analyze.
AraComLex generates about 13 million surface word forms, of which 9 million are found to be valid forms when checked by the Microsoft Spell Checker (Office 2013). For the sake of comparison, we also use a list of 2,662,780 surface word types created from a text corpus (from the Arabic Gigaword corpus and data crawled from the Al-Jazeera web site) of 1,034,257,113 tokens. At one stage of the validation processes, we automatically match the word lists against the Microsoft Spell Checker to determine which words are accepted and which are rejected. It is to be noted that we relied on MS Spell Checker at this initial stage for the purpose of bootstrapping our dictionary, because it was the best performing software at the time. The results are shown in Table 1. We take the combined (AraComLex and corpus data) and filtered (through Microsoft Spell Checker) list of 9,306,138 words types as our initial list and name it ‘AraComLex Extended 1.0’. It is to be pointed out that AraComLex (due to the fact that it is a morphological analyzer) has a relatively poor coverage of named entities, but this deficiency is handled in AraComLex Extended 1.0 through the augmentation from the combined Gigaword and crawled Al-Jazeera corpus data.
Arabic word lists matched against Microsoft spell checker
A second round of validation has been conducted by checking our word list against the Buckwalter morphological analyzer, and later rounds have been conducted manually on high-frequency words. The output of these series of checking and validation is the latest version of AraComLex Extended, that is version 1.5Footnote 8 . Table 2 presents the results of the evaluation of the different word lists against AraComLex Extended 1.5 using the test set, and it shows that AraComLex Extended 1.5 significantly outperforms the other word lists in precision, recall and f-measure. It must be noted, however, that Ayaspell for Hunspell, as is the standard with Hunspell dictionaries, comes in two files: the .dic file which is the list of words, and the .aff file which is a list of rules and other options. Table 2 evaluates only the Ayaspell word list file, but the system as a whole is evaluated in the next section.
Evaluation of Arabic word lists matched against Microsoft Spell Checker
By comparing our word list to those available for other languages, we find that for English there are, among other word lists, AGIDFootnote 9 , which contains 281,921 types, and SCOWLFootnote 10 , containing 708,125; for French, there is a word list that contains 338,989 typesFootnote 11 . The largest word list we find on the web is a Polish word list for Aspell containing 3,024,852Footnote 12 . This makes our word list one of the largest for a human language so far. Finnish and Turkish are agglutinative languages with rich morphology that can lead to an explosion in the number of words, similar to Arabic, but word lists for these two languages are not available to us yet. The large number of word types in our list is further testimony to the morphological productivity of the Arabic language (Kiraz Reference Kiraz2001; Watson Reference Watson2002; Beesley and Karttunen Reference Beesley and Karttunen2003;; Hajič and Jin, Reference Hajič, Smrž, Buckwalter and Jin2005).
3 Error detection
For spelling error detection, we use two methods, the direct method, that is matching against the dictionary (or word list), and a character-based language modeling method in case such a word list is not available.
3.1 Direct detection
The direct way for detecting spelling errors is to match words in an input text against a dictionary, or list of correct words. Such a dictionary for Arabic can run into several million surface forms as shown earlier. This is why it is more efficient to use finite state automata to store words in a more compact manner. An input string can then be composed against the valid word list paths and spelling errors will merely be the difference between the two word lists (Hassan et al. Reference Hassan, Noeman and Hassan2008, Hulden Reference Hulden2009a).
We evaluate the task of error detection as binary (two class) classification on the test set and compare it with three major text authoring tools: Ayaspell version 3.4, Microsoft Office 2013, and Google Docs. For each word in the test set, the method under evaluation predicts if the word is correct (class one) or not (class two). Based on the prediction and the manual annotation, we calculate tp as the number of words correctly predicted as erroneous (‘true positives’), fp as the number of words incorrectly predicted as erroneous (‘false positives’), tn as the number of words correctly predicted as correct (‘true negatives’), and fn as the number of words incorrectly predicted as correct (‘false negatives’).
Then, we employ the standard binary classification evaluation metrics, calculated as in (2)–(5). Accuracy is the ratio of correct predictions (words correctly predicted as erroneous or correct), precision is the ratio of correctly predicted items against all predicted items, recall is the ratio of all correctly predicted items against all items that need to be found, and f-1 measure as the geometric mean of precision and recall.
\begin{equation}
accuracy: \frac{tp + tn}{tp + tn + fp + fn}
\end{equation}
\begin{equation}
recall: \frac{tp}{tp + fn}
\end{equation}
\begin{equation}
precision: \frac{tp}{tp + fp}
\end{equation}
\begin{equation}
f\mbox{-}measure: 2 \times \frac{precision \times recall}{precision + recall}.
\end{equation}
As the results in Table 3 show, our system outperforms the other systems in accuracy, precision, and f-measure.
Comparison of accuracy, recall, precision, and f-measure of AraComLex Extended 1.5 against other applications
3.2 Detection through language modeling
Language modeling has been used frequently for the purpose of spelling correction (Brill, Eric and Moore Reference Brill and Moore2000; Magdy and Darwish Reference Magdy and Darwish2006; Choudhury et al. Reference Choudhury, Saraf, Jain, Mukherjee, Sarkar and Basu2007). However, here we build a language model in order to help the validation and classification of Arabic words either in the existing word list or for new words that may be encountered at later stages. Arabic is challenging for language modeling due to the high graphemic similarity of Arabic words. This is shown by Zribi and Ben Ahmed (Reference Zribi and Ben Ahmed2003) who conducted an experiment automatically using four edit operations (addition, substitution, deletion, and transposition) to change words, calculating the number of correct forms among the number of automatically built forms (or lexically neighboring words) resulting from these edit operations. They found that the average number of neighboring forms for Arabic is 26.5, which is significantly higher than that for French, 3.5 and English, 3.0.
In this experiment, we build a character-based tri-gram language model using SRILM (Stolcke et al. Reference Stolcke, Zheng, Wang and Abrash2011) in order to classify words as valid and invalid. We split each word into characters, and create two language models: one for the total list of words accepted as valid (9,306,138 words), and one for the total list rejected as invalid (5,841,061 words) as filtered through the MS Spell Checker, as shown in Table 1 above. The maximum word length attested in the data is found to be 19 characters. We test the model against our test set, and the results are presented in Figure 1 which shows the precision-recall curve of the classifier. The curve represents precision and recall scores of the detection of spelling errors based on the difference between the perplexity obtained by the accept model and the perplexity of the reject model. The downward movement of the curve indicates that the model is working quite reasonably giving a precision of 85% at a recall of 100%. The model also achieves a precision of around 98% at a recall of 35%. We can identify 60% of all errors with a precision of 95%, i.e. with 5% false alarms only.
Results of the LM classifier identifying valid and invalid Arabic word forms.
4 Improving the error model: candidate generation
For a spelling error s and a dictionary D, the purpose of the error model is to generate the correction c, or list of corrections cn 1 where cn 1 ∈ D, and cn 1 are most likely to have been erroneously typed as s. In order to do this, the error model generates a list of candidate corrections c 1, c 2, . . ., cn that bear the highest similarity to the spelling error s.
We deploy finite-state automata to propose candidate corrections within edit distance 1 and 2 measured by the edit distance from the misspelled word (Mitton Reference Mitton1996; Oflazer Reference Oflazer1996; Hulden Reference Hulden2009b; Norvig Reference Norvig, Segaran and Hammerbacher2009). The automata works basically as a character-based generator that replaces each character with all possible characters in the alphabet as well as deleting, inserting, and transposing neighboring characters. There is also the problem of merged (or run-on) words that need to be split, such as
>w>y ‘or any’. These are cases where two words are joined together and the space between them is omitted, such as ‘to the’ in English when written as ‘tothe’.
Candidate generation using edit distance is a brute-force process that ends up with a huge list of candidates. Given that there are 35 alphabetic letters in Arabic, for a word of length n, there will be n deletions, n − 1 transpositions, 35n replaces, 35(n + 1) insertions and n − 3 splits, totaling 73n + 31. For example, a misspelt word consisting of six characters will have 469 candidates (with possible repetitions). This large number of candidates needs to be filtered and reordered in such a way that the correct correction comes top or as near the top of the list as possible. To filter out unnecessary forms, candidates that are not found in the dictionary are discarded. The ranking of the candidates is explained in the following subsection.
4.1 Candidate ranking
The ranking of the candidates is initially based on a crude minimum edit distance where the cost assignment is based on arbitrary letter change. In order to improve the ranking, we analyze error types in the development set (containing 2,027 misspelled types with their corrections) to see how they are distributed in order to devise ranking rules for the various edit operations. Table 4 shows the top 20 most common spelling error types.
Most frequent spelling error types in Arabic
Based on these frequency observations, we develop a re-ranker to order edit distance operations according their likelihood to generate the most plausible correction. Table 4 shows that soft errors are the most frequent type of errors in the data, these are the errors related to hamzahs (
), the pair of yaa (y) and alif maqsoura (Y), and the pair of taa marboutah (p) and haa (h). According to the data analyzed, soft errors account for 71.76 of all the spelling errors. Our re-ranker translates these facts and primes the edit distance scoring mechanism with rules based on the frequency of error patterns in Arabic. It assigns a lower cost score to the most frequently confused character sets (which are often graphemically similar), and higher score for other operations. For speed and efficiency, we use the finite-state compiler Foma (Hulden Reference Hulden2009b) in finding candidates within certain edit distances. Figures 2 and 3 show the different configuration files for the crude and re-ranked edit distance.
Crude edit distance.
Re-ranked edit distance.
A similar approach has been followed by Shaalan et al. (Reference Shaalan, Allam and Gomah2003) who defined rules for substituting letters belonging to the same groups (based on graphemic similarity) as shown here.
{A, >, <, |}, {b, t, v, n, y}, {j, H, x}, {d, *}, {r, z},
{s, $}, {S, D}, {T, Z}, {E, g}, {f, q}, {p, h}, {w, &}, {y, Y}.
As also noticed from Table 4, split words constitute 16% of the spelling errors in the development set, such as
‘EbdAldAym’ ‘Abdul-Dayem’,
‘wlAtryd’ ‘and does not want’, and
‘mAyHdv’ ‘what happens’. There are seven words and particles that are commonly found in the joint word forms, and they are:
Ebd,
yA,
Abw,
wlA,
lA,
wmA,
mA.
It is worth mentioning that although the majority of cases with joined words occur with orthographically non-linking letters (such as ‘A’, ‘d’, ‘w’), there are a few instances where the merge occurs with linking characters as well, such as
‘tHsnmlHwZ’ ‘noticeable improvement’ and
‘HAzt>glbyp’ ‘got majority’.
The problem with split words is that they are not handled by the edit distance operation. Therefore, we add a post process for automatically inserting spaces between the various parts of the string. However, this is prone to overgeneration: a word of length n will have n − 3 candidates, given that the minimum word length in Arabic is two characters. For example thebag will have: th ebag, the bag, and theb ag. To filter out bad candidates, the two parts generated from splitting conjoined words are spell checked against the reference dictionary, and if both or either of the two parts is not found, the candidate pair is discarded.
Generating split words for all spelling errors is not a good strategy as this will increase the search space when trying to disambiguate later for the purpose of choosing a single best correction. Therefore, we need to find a method to spot misspelled words that are likely to be an instance of merged words. In order to decide which words should be considered as possibly having a merged word error, we rely on two criteria: word length and lowest edit score. When we analyze the merged words in our development set, we notice that they have an average length of 7.09 characters, with the smallest word consisting of 4 characters and the longest consisting of 15. The average lowest edit score is 2.11. Compared to normal words, we see that the average length is 6.49, the smallest word is 2 and the longest word is 14, with an average lowest edit score of 1.19. We evaluate three criteria for detecting split words on the development set, as shown in Table 5 with w standing for ‘word length’ and l for ‘lowest edit score’. The criteria of ‘word length > 3 characters and lowest edit score >1’ has the best f-measure, and therefore we choose it for deciding which words to split.
Evaluating criteria for deciding split words
4.2 Evaluation of the candidate ranking technique
Our purpose in ranking candidates is to allow the correct candidate (the gold correction) to appear at the top or as near the top of the list as possible, so that when we reduce the list of candidates, we do not lose many correct ones. We test the ranking mechanism on both the development set (2,027 errors types with corrections) and the test set (5,398 errors types with corrections) as shown in Tables 6 and 7 respectively.
Comparing crude edit distance with the re-ranker using the development set
Comparing crude edit distance with the re-ranker using the test set
We compare crude edit distance with our revised edit distance re-ranking scorer, and both testing experiments show that the re-ranking scorer performs better at all levels. We notice that when the number of candidates is large the difference between the crude edit distance and the re-ranked edit distance is not big (about 2% absolute for the development set and 0.28% absolute for the test set at the 100 cut-off limit without splits), but when the limit for the number of candidates is lowered the difference increases quite considerably (about 42% absolute for development set and 67% absolute at 1 cut-off limit without splits). This indicates that our frequency-based re-ranker has been successful in pushing good candidates up the top of the list. We also notice that adding splits for merged words has a beneficial effect on all counts.
5 Spelling correction
Having generated correction candidates and improved their ranking based on the study of the frequency of the error types, we now use language models trained on different corpora to finally choose the single best correction. We compare the results against the Microsoft Spell Checker in Office 2013, Ayaspell 3.4 used in OpenOffice, and Google Docs (April 2014).
5.1 Correction procedure
For automatic spelling correction (or first-order ranking), we use the n-gram language model. Language modeling assumes that the production of a human language text is characterized by a set of conditional probabilities, P(wk |w (k − 1) 1), where w (k − 1) 1 is the history and wk is the prediction, so that the probability of a sequence of k wordsP(w1, . . ., wk ) is formulated as a product using the Chain Rule for conditional probabilities as in (6) (Brown et al. Reference Brown, Della Pietra, de Souza, Lai and Mercer1992):
\begin{equation}
P(w_1^{k} )=P(w_{1} )P(w_{2} | w_{1} ) \dots P(w_{k} |w_{1}^{(k-1)}).
\end{equation}
We use the SRILM toolkit (Stolcke et al. Reference Stolcke, Zheng, Wang and Abrash2011) to train 2-, 3-, 4-, and 5-gram language models on our data sets. As we have two types of candidates, normal words and split words, we use two SRILM tools: disambig and n-gram. We use the disambig tool to choose among the normal candidates. Handling split words is done as a posterior step, where we use the n-gram tool to score the chosen candidate from the first round and the various split-word options. Then the candidate with the least perplexity score is selected. The perplexity of a language model is the reciprocal of the geometric average of the probabilities. So, if a sample text S has |S| words, then the perplexity is P(S)(− 1/|S|) (Brown et al. Reference Brown, Della Pietra, de Souza, Lai and Mercer1992). This is why the language model with the smaller perplexity is in fact the one with the higher probability with respect to S.
5.2 Analysing the training data
Our language model is based on raw data from two sources: the Arabic Gigaword Corpus 5th Edition and a corpus of news articles crawled from the Al-Jazeera web site. The Gigaword corpus is a collection of news articles from nine news sources: Agence France-Presse, Xinhua News Agency, An Nahar, Al-Hayat, Al-Quds Al-Arabi, Al-Ahram, Assabah, Asharq Al-Awsat, and Ummah Press.
Before we start using our available corpora in training the language model, we analyze the data to measure the amount of noise in each subset of the data. The concept of data cleanliness and its impact on machine learning processes has been discussed in the literature (Mooney and Buescu Reference Mooney and Bunescu2005; Han and Kamber Reference Han and Kamber2006), with emphasis on the fact that real-world data will tend to be noisy, incomplete and inconsistent, and will need to undergo some sort of cleaning or preparing.
In order to measure the level of cleanliness of our training data, we create a list of the most common spelling errors. This list of spelling errors is created by analyzing the data using MADA (Habash and Rambow Reference Habash and Rambow2005; Roth et al. Reference Roth, Rambow, Habash, Diab and Rudin2008) and checking instances where words have been normalized. This is done by matching the analyzed word with the original word, and if there is a literal mismatch, then we know that normalization has taken place. In this case, the original word is considered to be a suboptimal variation of the spelling of the output form. MADA performs normalization on the soft spelling error related to the different shapes of hamzahs, taa marboutah and haa, and yaa and alif maqsoura explained in more detail in Section 1.2 earlier. We collect these suboptimal forms and sort them by frequency. Then, we select the top 100 misspelled forms and see how frequent they are in the different subsets of data in relation to the word count in each data set. Since soft errors account for 71.76% of all the spelling errors, we believe we have strong ground to assume that the presence of these suboptimal forms is an evidence of the lack of careful editing of the data, giving an indication to the amount noise/cleanliness of the data. It is to be noted that Arabic text denormalization is a subproblem of automated text error correction and a prerequisite for some NLP applications (Moussa, Fakhr and Darwish Reference Moussa, Fakhr and Darwish2012; El Kholy and Habash Reference El Kholy and Habash2010). Figure 4 and Table 8 show the varying level of noise in the different subsets of data.
Ratio of noise in corpus data.
Corpus subsets with word count and ratio of noise
The analysis shows that the data has a varying degree of cleanliness, ranging from the very clean to the very noisy. Data in the Agence France-Presse (AFP) (containing 217,300,912 words) is the noisiest while Ummah Press (3,976,268 words) is the cleanest, and Al-Jazeera (151,329,247 words) is the second cleanest. Due to the fact that the Ummah Press data is not comparable in size to the AFP data, we ignore it in our experiments and use instead the Al-Jazeera data for representing the cleanest data set.
5.3 Automatic correction evaluation
For comparison, we first evaluate the automatic correction (or first-order ranking) of three industrial text authoring applications: Google DocsFootnote 13 , OpenOffice Ayaspell 3.4, and Microsoft Word 2013. Using our test set of 49,690 spelling error tokens with corrections, we test the automatic correction of these systems. The results in Table 9 are reported in terms of accuracy (number of correct corrections divided by the number of all errors).
Evaluation of first-order ranking of spelling correction of Google Docs, Ayaspell and MS Word 2013
Next, we evaluate our approach on the test set using language models trained on the AFP data (as representing the noisiest type of data), the Al-Jazeera data (as representing the cleanest type of data) and the entire Gigaword corpus (as representing a huge data set with a moderate amount of noise). We run our experiments on the candidates generated through the re-ranked edit distance processing explained in Section 4 with varying candidate cut-off limits. We choose the best correction from among the normal candidates using the SRILM disambig tool, and for the split words using n-gram tool.
As Table 10 shows, the best score achieved for the automatic correction is 93.64% using the bigram language model trained on the Arabic Gigaword Corpus with a candidate cut-off limit of 2, and with the split words added. Table 10 also shows that the system performance deteriorates as the number of candidates increases, which means that the n-gram language model needs a compact number of candidates to disambiguate from among them.
First-order correction accuracy using the 2-gram LM trained on data from AFT, Al-Jazeera, and the entire Gigaword corpus on the test set
Comparing the LM trained on the two data sets which are comparable in size, the AFP and Al-Jazeera data sets, we find that the LM trained on the AFP has consistently lower scores than those for the LM trained on the Al-Jazeera data. The Al-Jazeera data is relatively clean while the AFP data has a large amount of suboptimal misspellings. We assume that the relatively low performance of the language model trained on the AFP data is due to the amount of noise in the data. However, this assumption is not conclusive, and it can be argued that the difference could simply be due to the different genres or the dialects that are predominant in this data set.
Table 10 shows that the extremely large Gigaword corpus makes up for the effect of noise and produces the best results among all the data sets. The best score achieved for the Gigaword corpus (93.64%) is 0.86% absolute better than the score for Al-Jazeera (92.78%). This could be a further indication in favor of the argument that more data is better than clean data. However, we must notice that the Gigaword data is one order of magnitude larger than the Al-Jazeera data, and in some applications, for efficiency reasons, it could be better to work with the language model trained on a smaller data set. We notice that the addition of the split word component has a positive effect on all test results.
We conducted further experiments with other language models trained on higher order n-grams, going from 2- to 3-, 4- and 5-grams, but the higher n-gram order did not lead to any statistically significant improvement of the results, and sometimes the accuracy even slightly deteriorates, which leads us to believe that the 2-gram language model is good enough for conducting this type of task.
Compared to other spelling error detection and correction systems, we notice that our best accuracy score (93.64%) is significantly higher than that for Google Docs (2.57%), Ayaspell 3.4 for OpenOffice (67.43%), and Microsoft Word 2013 (76.43%) as stated in in Table 9 above.
6 Conclusion
We described our methods for improving the three main components in a spelling error correction application: the dictionary (or word list), the error model and the language model. The contribution of this paper is showing empirically that these three components are highly interconnected and interrelated and they have direct impact on the overall quality and coverage of the spelling correction application. The dictionary needs to be an exhaustive and accurate representation of the language word space. The error model needs to generate a plausible and compact list of candidates. The language model, in its turn, needs to be trained on either clean data or an extremely large amount of data. For spelling error detection, we develop a novel method by training a tri-gram language model on strings of allowable and unallowable sequences of Arabic characters, which can help in the validation of existing word lists and making decisions on new unseen words. Our spelling correction significantly outperforms the three industrial applications of Ayaspell 3.4, MS Word 2013, and Google Docs (tested April 2014) in first-order ranking of candidates.
