2.1 Rule-based versus data-driven methods

Approaches to NLP are generally grouped into two broad categories, namely rationalist approaches and empiricist approaches (Manning and Schütze Reference Manning and Schütze1999). Within each of these broad categories reside other sub-categorizations. Rationalist approaches to NLP rely on theoretical analyses and encoding linguistic knowledge in some form of symbolic representation to produce competence-oriented models of some linguistic phenomenons or relationships. Rules and logic are examples of such symbolic representation. Empiricist approaches, on the other hand, are characterized by the use of ‘large’ amount of data with machine learning algorithms to create models that are considered to be based on linguistic performance as opposed to linguistic competence. Rules are the preponderant formalism within the rationalist paradigm and the term ‘rule-based methods’ has been used as synonym for the rationalist approaches. Similarly, the term ‘statistical or data-driven methods’ is used as synonym for empiricist approaches.

Rule-based methods aim at building models that mimic the linguistic competence that humans are believed to possess intuitively. Thus, rule-based models are built and derived from theoretical frameworks. Rule-based techniques proceed by designing and constructing a set of rules, that were inferred or deduced from the theoretical framework derived from human analysis. An inference mechanism is implemented to select rules that are matched by condition in the working memory. The rules are actually an encoding of linguistic knowledge.

Data-driven methods aim at building models that mimic the linguistic performance that data are believed to express. Thus, data-driven models are built and derived, as the name implied data that represent the usage of language. Data-driven methods employ an assortment of mathematical tools like statistics and probability theory, combined with machine learning techniques to learn approximate models of linguistic phenomena from very large data.

Diacritization is one of the many problems being addressed in NLP and the approaches used here also fall into the two major categories of rule-based methods and data-driven methods. A third category with such methods combines techniques from both the rule-based and data-driven methods in varying degrees of hybridization. However, in most cases of hybridization, one method will be the major technique while the technique from the second method will be used in supportive role. Several studies across different languages and different writing systems have applied either the rule-based or the data-driven approach to address the problem of diacritization. While most earlier works seemed oriented toward rule-based methods, later one either used the data-driven approaches solely, or as the major paradigm in diacritization. This trend is not particular to diacritization, since empiricist approach regained resurgence in the early 1990s.

A summary of the major issues involved in NLP and therefore diacritization is presented in Table 3 (information in the first seven rows were extracted from Liddy (Reference Liddy and Drake2001). The detail of the various studies that used either (or both) of these approaches will be presented in sections 3 and 4. Before we do that, we examined the two different fundamental situations in text that make diacritization a necessity.

Table 3.

Comparison of rule-based and data-driven methods

2.2 Types of diacritic restoration problems

According to Haertel et al. (Reference Haertel, McClanahan and Ringger2010), ‘the existing approaches can be categorized based on the amount of resources they require, their basic unit of analysis, and of course the language they are targeting’. In this study on diacritization, we have decided to look at existing models based on the use of resources and formulation of the model. The diacritization models can be categorized based on the writing system of the language involved. Languages that need diacritization based on abjad writing system belong to one category and those based on the alphabetic writing system to the second category. In the first category with the text in abjad, these languages deal with diacritization that restores missing letters since words are written using consonants and long vowels. Short vowels, and other diacritics which convey differentiating lexical and syntactic information must be restored. We referred to this kind diacritization as Missing Letters Diacritization (MisLet). Among the surveyed literature, MisLet were found for Arabic, Syriac, Sindhi and Urdu (Ali Reference Ali2009; Haertel et al. Reference Haertel, McClanahan and Ringger2010; Mahar and Memom Reference Mahar and Memon2011) languages, respectively. However, the amount of literature on Arabic (modern standard and dialectical) was the largest for MisLet and even the whole diacritization efforts. Investigation of the morphological system of the above languages indicated that diacritics were used to convey

1. (a) lexical distinction and

2. (b) linguistic information such as case, gender, tense and part of speech (POS) which are often marked on a single word.

We classified diacritization in languages based on the alphabetic writing system as Substituted Letters Diacritization (SubLet) since orthographically, the letters that carry diacritics are approximated by the base letter or another character without the diacritics. Among the surveyed literature, languages with SubLet included Cilubà, Dutch, French, Romanian, Vietnamese and Yorùbá, among many others. In fact, there are more languages in the SubLet cluster of diacritization than MisLet although the volume of study on the language with MisLet is more abundant. For languages with SubLet needs, diacritics can serve any one or more of these functions:

1. (a) Phonemic function: differentiating among phonemes and thus between lexical items.

2. (b) Grammatical function: conveying syntactic information such as tense, category of word, case, gender.

3. (c) Tone which also can be lexical or syntactic in nature.

We are of the opinion that the SubLet should be computationally less difficult than the MisLet since presence of approximate letters in them yields some constraining information that would otherwise not be available when those letters are totally absent. An examination of the functions or roles of diacritics in languages with missing letters and substituted letter diacritization shows the following:

• • Absence of diacritics lead to lexical ambiguity or meaningless text.

• • Absence of diacritics lead to loss of grammatical information in text.

• • Restoration of diacritics often leads to the solution of the above problems.

However, since the effects of absence of diacritics in both MisLet and SubLet are nearly the same, we will only emphasize this difference when the method used in any study that we reviewed particularly indicated that difference is an important factor.

2.3 Resources deployed for diacritization

NLP and engineering tasks are accomplished with the aid of various tools and diacritization is not an exception. Thus, in the categorization of diacritization, the kind of language resources deployed to accomplish the task is another important consideration. Language resources (also linguistic resources) in the context of human language technology is a set of machine-readable linguistic data and description and algorithms (tools) for working with the data (Grönqvist and Helgadóttir Reference Grönqvist and Helgadóttir2002; Borin Reference Borin2009; ELRA 2015). Examples of such resources as might be employed for diacritization are morphological analyzers, lemmatizers, transcribed speech, prefixes and suffixes, POS tags, existing electronic dictionaries and lexicons, Parsers, Treebanks, parallel corpus and translations in other languages. We categorized these resources using the structure found in Borin’s (Reference Borin2009) pyramid of language resources which is shown in Figure 2. Raw text (Level 1) is at the bottom of the pyramid while the top of the pyramid (Level 5) is occupied by tools for handling semantics and pragmatics. The diacritization methods that we reviewed are thus grouped into the following three groups:

• • Methods with significant (heavy) usage of linguistic resources or significantly resourced methods(SigRes).

• • Methods with medium usage of linguistic resources or intermediately resourced methods (InterRes).

• • Methods with light usage of linguistic resources or minimally resourced methods (MinRes).

Fig. 2.

Language resources pyramid (Borin, Reference Borin2009).

The above grouping have a rough correspondence to the pyramid in Figure 2 such that levels 4 and above correspond to SigRes methods, while levels 2 and 3 have a correspondence to InterRes methods and MinRes methods use level 1. The division between the first and second group may sometimes be fuzzy in nature as it relates to the border between levels 3 and 4. We have however, tried to delineate by the estimating the level of dependency of the method on those resources.

4.1 Methods that rely on instance-based learning

IBL is a form of supervised machine learning. They are an extension of k-nearest neighbors algorithms with the following characteristics:

• • IBL algorithms, unlike most other supervised learning algorithms (statistical models especially), do not maintain a set of abstractions of model created from the instances.

• • IBL training phase consist of storing all instances and possibly doing some indexing to easily locate neighbors.

• • IBL uses some similarity functions to compute the similarity between training instances and new instances.

• • From the output above function, the new instances are labeled with the class of the most similar closest neighbors (Aha, Kibler and Albert Reference Aha, Kilber and Albert1991).

This IBL algorithm was applied as a method for diacritization of Romanian using letters as the linguistic unit for restoration (Mihalcea Reference Mihalcea2002). In the experiment with reported ninety-nine per cent average letter-level precision, neither POS tagger nor morphological or syntactic analyzer were used. Further experiments extended the language set to four: the following four languages Czech, Hungarian, Polish and Romanian to investigate language independence or dependence of the approach (Mihalcea and Nastase Reference Mihalcea and Nastase2002). The use of letters as diacritization token was to alleviate the twin problems of out of vocabulary items that often dogged methods with word-based diacritization and language resource limitation. The training (stored in memory) set was extracted from the corpus, based on a feature set consisting of N letters to the right and left of the ambiguous candidate letter. Space and punctuation marks were coded since they are considered special character in the algorithm. With N set to the value 5, using the Tilburg Memory Based Learner implementation of the KNN algorithm, the author reported accuracy levels above ninety-nine per cent using a 10-fold cross validation. They reported an average letter level accuracy of 97.04 per cent, 97.83 per cent, 98.30 per cent and 99.02 per cent for Hungarian, Czech, Romanian and Polish, respectively. Mihalcea and Nastase (Reference Mihalcea and Nastase2002) also examined, with Romanian as test language, the effect of size of training data on accuracy and reported that as low as 1,000 training examples can be used for training which yielded 83.49 per cent accuracy. In addition, performance was reported to improved significantly as more data were added up to a size of 100,000 training examples with an accuracy of 93.03 per cent. Thereafter, accuracy increased more slowly such that one million training examples only gave 95.10 per cent accuracy. A window size of five characters (on both size of ambiguous character) was also determined to be optimal (Mihalcea and Nastase Reference Mihalcea and Nastase2002).

There seems to be a correlation between accuracy for each letter group and their ‘diacritical complexity’ factor. We define the term ‘diacritical complexity’ for letters as the number of graphemes that collapse into a single letter when the diacritics are not indicated. It seems to indicate that, the higher the ‘diacritical complexity’ factor, the lower the expected accuracy for restoration from the plain surface forms. This ‘diacritical complexity’ factor is related to the word-level measure ‘Lexical Diffusion’ (De Pauw et al. Reference De Pauw, Wagacha, de Schryver and Matousek2007) which was calculated by dividing the number of diacritized word forms in a text by the number of basic forms when diacritics are not indicated on words. Another proposal for measuring this diacritical complexity at word-level recommended the use of the percentage of words in the training corpus that are incorrectly resolved or unresolved by a simple unigram model (Scannell Reference Scannell2011). All these measures are supposed to indicate the expected diacritization difficulty for different languages.

This IBL approach using letters was applied to Gĩkũyũ (Wagacha, De Pauw and Githinji Reference Wagacha, De Pauw and Githinji2006), a language spoken by an estimated population of about 6 million in East Africa. The authors contrasted the experiment on Gĩkũyũ with French, German and Dutch using a context value of N set to 3, and indicated that while Gĩkũyũ has 66.5 per cent and 54.6 per cent diacritical forms in lexicon and running text, respectively, French has 27.6 per cent and 19.7 per cent, while German has 22.3 per cent and 6.8 per cent and Dutch has 1.2 per cent and 0.3 per cent, respectively. That was used as explanation for the better performance of the lexicon lookup (or unigram model) for those European languages. Extension to the original letter-level modeling (Mihalcea Reference Mihalcea2002) was tested by comparing the performance of the unigram letter-level modeling with trigram letter-level modeling (Wagacha et al. Reference Wagacha, De Pauw and Githinji2006).

The performance was evaluated on words that did not occur in the training set (dubbed ‘unknown words’) and also on plain text. Results indicated that the unigram model achieved 68.0 per cent and 77.5 per cent word-level precision for ‘unknown words’ and plain text, respectively, for Gĩkũyũ. The trigram model yielded 72.2 per cent and 91.4 per cent accuracy for ‘unknown words’ and plain text, respectively. Compared with results (‘unknown words’ and plain-text, respectively) for Dutch (99.6 per cent and 99.9 per cent), French (88.2 per cent and 89.3 per cent) and German (92.7 per cent and 96.8 per cent), there seems to be an inverse relationship with percentage diacritic usage in text. The languages with relatively higher usage of diacritics have better performance with the `trigram' IBL model.

The IBL algorithm with unigram letter-level was applied for diacritization to Cilubà, Kĩkamba, Maa, Sesotho sa Leboa, Tshivenda and Yorùbá in addition to Gĩkũyũ and five European and two Asian languages (De Pauw et al. Reference De Pauw, Wagacha, de Schryver and Matousek2007). The aim was to evaluate the suitability of the IBL model in resource-scarce situation. The authors suggested that the evaluation of performance of models should be focused on unknown words in test data. The IBL unigram model with N of 5, reportedly improved both word and letter-level accuracy scores for all data compared with the baseline that chose the most frequently seen grapheme candidate. Their evaluation on words not seen in training data indicated that some previous report accuracy might fall significantly when evaluated on test data not found in training data. They noted that performance of the model was below average for the tonal languages involved as predicted by the lexical diffusion values. The following was reported:

Another application of IBL algorithm to diacritization was for Arabic diacritization (Mohamed and Kübler Reference Mohamed and Kübler2009). This was a consonant unigram model that labels each consonant with either a null or a vowel. The context applied in this model consist of variations of both words and letters although the token to be label was a consonant in the focus word. The default was the five inner context which are the five consonants on the left and right of focus consonant within the focus word. Another five outer context consist of the five words to the left and right of the focus word. The reported best configuration was when the five left word context was added to the default context setting. With the mind of improving the performance of the diacritization, a module to restore the hamza, a diacritic used sometimes to express glottal stop in Arabic as well as other functions, was created to pre-process for hamza restoration before the restoration of remaining diacritics. The hamza pre-processor was reported to have an accuracy of 98.09 per cent. The use of the two-stage restoration process was observed to give a 25.5 per cent reduction in word error rate (WER) over the one-stage restoration model with a WER of 7.96 per cent. Error rate was the parameter used to evaluate the performance in this work instead of the commonly used precision/accuracy.

4.2 Methods that rely on generative modeling

Generative algorithms define the joint probability of states and their emitted classes or labels, P(x, y), as the product of the initial state probability, the probability of the state transition and the probability of the label emitted from each state. Bayesian classifier and HMM are great examples of generative models or classifiers.

Bayesian Classifier is a machine learning algorithm based on probabilistic modeling of observed data and prior knowledge. A word-based Bayesian Classifier was proposed by Yarowsky (Reference Yarowsky1999) for diacritization of Spanish and French. The basic procedure employed a window of words surrounding each ambiguous word to determine if there are any measurable differences in the distribution of words found in the contexts surrounding one of its diacritic patterns relative to the other. The experimental result showed that the context window of ±4 word was optimal to distinguish one diacritical form from another. Bayesian classification was also applied to Māori for word-based diacritization. Cocks and Keegan (Reference Cocks and Keegan2011), however, used an elaborate feature set that comprise of several n-grams of words. The best performance was with a feature vector consisting of the following: trigram with offset of −1 (of one word before focus word), a bigram with offset of −2, another bigram with offset +1, a quad-gram with offset of −1 and lastly, another quad-gram with offset of −2. The best result was 99.01 per cent word level accuracy.

Bayesian Classifier was also used for the diacritization of several languages covering 55 African and 53 other languages in a process they referred to as unicodification (Scannell Reference Scannell2011). The diacritization experiment used diverse combinations of character n-gram as features instead of word tokens. Three lexicons were used either as standalone or in combination with the n-gram configurations. The best performing n-gram configurations were with trigram attributes. The first of the trigram-based feature configuration comprised seven trigrams with the first having an offset of −4 and the last having an offset of +2. It gave the best result with relatively smaller training data, while the second configuration of trigram feature configuration having three trigrams with offsets −3, −1 and +1, respectively, gave better results when training data was larger. A general appraisal of the Bayesian classification by Yarowsky (Reference Yarowsky1994) is given as follows:

1. (a) ‘. . .it is difficult to model the occurrence of words in specific positions’.

2. (b) ‘. . .it is also quite difficult to model sequences of nearby words’.

3. (c) ‘. . .independence assumption also makes the technique poorly suited for combining multiple non-independent sources of evidence’.

The appraisal labeled (b) above is due to the nature of the Bayesian model which limits its use to local classification rather than global. Further investigation in diacritization should consider the integration of the lexical lookup technique in the model to be developed for diacritization for other languages. However, there is a need to examine the direction of integration. By this, we mean whether it should be used as in pre-processing or post-processing.

Another approach that has been widely applied uses HMM. According to Jurafsky and Martin (Reference Jurafsky and Martin2000), HMM is one of the most important machine learning models in speech and language processing. A word-based Arabic and Hebrew diacritization system (Gal Reference Gal2002) applied HMM as the tool for modeling. A bigram (that is first-order) HMM was constructed in which the hidden states were vowel-annotated (diacritized) and the observations were vowel-less words, while the parameters were estimated using maximum likelihood method. Using Viterbi algorithm, a sequence labeling was performed to determine which sentence with diacritics restored best represented the original input sentence without diacritics. The author also reported difficulty in applying dictionaries to aid diacritics because of difference in structure of dictionary entries (prefix, suffix, lexemes) and that of written text. We can therefore conclude that existing dictionaries are useful to the extent that the format is conformable to ordinary written text; otherwise, a morphological analyzer will be an additional requirement. Some characters that could be interpreted as a consonant or vowel depending on context were treated throughout as consonants in the work. Accuracy reported for the study was eighty-one per cent for Hebrew texts and eighty-six per cent for Arabic texts at word level. Same approach was utilized for the diacritization of Spanish in which a lexicon provided the observation matrix and a trigram language model was built from training data. The diacritization was formulated as a spelling correction problem (Hládek, Staš and Juhár Reference Hládek, Staš, Juhár, Vetulani, Uszkoreit and Kubis2016).

Another HMM-based diacritization model proposed for Arabic language (Elshafei, Al-Muhtaseb and Alghamdi, Reference Elshafei, Al-Muhtaseb and Alghamdi2006b) also used the word sequence of diacritic-less forms as the observation sequence, while the possible diacritical forms of each word in the sequence were the hidden states. A word-list mapping a diacritic-less form to possible diacritical forms was constructed from the training data to constrain the search space during training and decoding stages. They utilized a bigram language model smoothed with a unigram model to generate the statistics upon which the model was trained. The work was evaluated on text from the Quran. A related work on Modern Standard Arabic (Elshafei et al. Reference Elshafei, Al-Muhtaseb and Alghamdi2006a) suggested a trigram for selected words with high frequencies to resolve end case errors.

The HMM-based diacritization was further applied (El-Harby et al. Reference El-Harby, El-Shehawey and El-Barogy2008) to Arabic with a modification to the previously mentioned studies. The process of restoration was divided into two processes. The first is done by selecting the most likely sequence of case ending which they referred to as last diacritic mark (LDM) for the diacritic-less words in input sentences. This was done using HMM where the LDM were the hidden states and the diacritic-less words were the observation sequence. The second aspect of the restoration was accomplished by selecting the diacritical forms having the same diacritic-less form and same LDM as previously determined. In addition, the study considered 11 diacritics,which was more than most of the earlier mentioned studies for Arabic but reported a similar performance.

4.3 Methods that rely on discriminative modeling

Discriminative models are types of classifiers used in machine learning where the conditional probability P(y|x), the probability of the unobserved variable or class label y is learnt directly from that of the observed variable x. MEMM, CRF and Support Vector Machines are forms of discriminative models.

MEMM are a kind of model that can integrate several and diverse sources of information for modeling phenomena in natural languages and other areas (Berger, Della Pietra and Della Pietra Reference Berger, Della Pietra and Della Pietra1996). Information is integrated as features of the object to be classified. It uses a supervised learning approach. The training phase of the model associates weights with the features with the aim of maximizing the likelihood of the data. MEMM was applied to Arabic (Sarikaya et al. Reference Sarikaya, Emam, Zitouni and Gao2006) and also to Syriac (Haertel et al. Reference Haertel, McClanahan and Ringger2010). Diverse kinds of features used for Arabic diacritization with MEMM including lexical, morphological and syntactic features. In one of these studies for Arabic, (Sarikaya et al. Reference Sarikaya, Emam, Zitouni and Gao2006), Diacritic Parse Tree to combine structure these features such that the diacritization was expressed ‘as a search problem’. In the second study (Zitouni et al. Reference Zitouni, Sorensen and Sarikaya2006), the features were incorporated directly into the MEMM model without any intermediate structure. The lexical features are the character 7-gram spanning the focus character in +−3 and word 5-gram spanning the word in focus +−2, others are specification of the position of the character within the word. Segment-based features used include affixes and stems generated by a segmentation model. This feature was used in a window of 5-gram spanning the character in focus. Finally, the POS of a segment was added to the feature spaces using a statistical POS tagging system. An additional feature used in this work is the value of the two previously assigned diacritics. The result improved with the addition of more relevant features. They also noted that this system performed better than a competitive Finite State Transducer (Nelken and Shieber Reference Nelken and Shieber2005).

The MEMM method was applied to Syriac (and also Arabic) diacritization with slight modification (Haertel et al. Reference Haertel, McClanahan and Ringger2010). The modification was in the use of both words and characters in a hybrid token system while the previous studies with MEMM worked with restoration at grapheme (character) level. The feature set used was similar to that of Zitouni et al. (Reference Zitouni, Sorensen and Sarikaya2006). The work applied the algorithm at word level backing off to letter level when the diacritization at word level failed; hence, this model is termed Word-Consonant Level Model. Diacritization at word-level was considered to have failed when the test word is not found in training data. The model employs an adapted decoder that uses pipelining to form an inner loop for decoding rare or unknown words independent of the decoder that works at decoding word tokens in normal flows. Performance of this model was slightly better than that of Zitouni et al. (Reference Zitouni, Sorensen and Sarikaya2006) which might be due to the hybrid token model utilized. The author recommended exploring the more global optimal version of the Markov model utilized namely CRF and other approximate pipeline decoders. Roth et al. (Reference Roth, Rambow, Habash, Diab and Rudin2008) extended Zitouni et al. (Reference Zitouni, Sorensen and Sarikaya2006), and developed a diacritization model for Arabic using a Treebank (LDC’s Arabic) where they made use of lexical, segment-based (root and affixes) and POS features. These set of features were integrated within an MEMM. These features would not normally be available to an ordinary text without a POS tagger and/or morphological analyzer or dictionary.

The CRF, developed by Lafferty, McCallum and Pereira (Reference Lafferty, McCallum and Pereira2001) does not suffer from what was referred to as the ‘label bias’ of MEMM. The major difference between MEMM and CRF is that while MEMMs have a per state normalization that allows the possibility of choosing a label from a local optima instead global optimal, CRFs have per global sequence normalization. CRF have been applied to Arabic and two tone languages: Vietnamese (Truyen et al. Reference Truyen, Phung, Venkatesh, Tu-Bao and Zhi-Hua2008) and Yorùbá (Asahiah Reference Asahiah2014). In the application of CRF to model Arabic diacritization as sequence labeling (Schlippe et al. Reference Schlippe, Nguyen and Vogel2008), the feature was similar to Zitouni et al. (Reference Zitouni, Sorensen and Sarikaya2006). The model utilized characters (consonants) for tokens and labeled with short vowels and other diacritics. The features included the character, the previous, current and next word context and the POS tags, respectively. The inclusion of the grammatical information caused the model to perform significantly better than a state of art rule-based system evaluated in their work. For Vietnamese, a tone language with Latin Script, CRF was used to build the diacritization model (Truyen et al. Reference Truyen, Phung, Venkatesh, Tu-Bao and Zhi-Hua2008). Vietnamese uses diacritics to mark tone and phonemic variations. In the study, the path way for the sequence was further constrained to what they called the ‘proposal set’ which consists only of valid diacritized terms in Vietnamese for a particular undiacritized term. The token used for this diacritization was the space delimited unit for writing in Vietnamese analogous to syllables. The author reported a result of 93.5 per cent term accuracy with first-order CRF and 94.3 per cent term accuracy with a second-order CRF both of which were better than previous best (Scannell Reference Scannell2011) with 91.6 per cent term (term) accuracy for character-based model. Asahiah (Reference Asahiah2014) used a similar aproach for Yorùbá, with the syllables (equivalent to Vietnamese ‘term’) from word via syllabification. The diacritization was split into two stages: one stage for phonemic diacritic and another for tone mark restoration. In restorating diacritics in Turkish language, Adalı and Eryiǧit (Reference Adalı and Eryiǧit2014) used morphological analyzer as a ‘language validator’ in a reverse direction. A CRF discriminative sequence labeling classifier was trained on labeled character-level data and returned n-best suggestion that is aggregated into word ranked by probability. The language validator selects the ‘most probable valid word as the final output for the diacritization’.

4.4 Methods that rely on probabilistic tagging

This statistical model is similar to the last discussed model. This is to the extent that possible diacritical candidates are also generated in the hypothesis generation stage after tokenization of input text sentence or sequence. However, the candidate diacritic forms are generated without the use of a morphological analyzer but all possible forms constrained by lexicons are generated. Thereafter, each of the generated forms is tagged with syntactic information which is often the POS tag. A statistical model is built around the diacritic form and POS tag such that the most probable POS tag sequence is used to generate the most likely diacritic sequence. An n-gram model built around undiacritized forms and word tagging among others was proposed for Spanish and French (Yarowsky Reference Yarowsky1999). The tags used were however not POS tags but suffix tags and function words. ‘The most probable tag sequence for new test data is recovered using a standard Viterbi decoder’. The author indicated that while this approach is viable for morphologically rich languages, it exhibits a general weakness of data sparseness. The existence of some words with multiple valid suffixes makes the building of a robust model of suffixes difficult.

Simard (Reference Simard1998) and Spriet and El-Bèze (Reference Spriet and El-Bèze1997) design a diacritization system for French with this approach using specially generated lexicons that produced candidate diacritic forms. Using an HMM, Simard (Reference Simard1998) a model of undiacritized forms and morpho-syntactic classes was built where the sequence of tags represents the hidden phenomenon. An alternative heuristic similar to Viterbi algorithm was used for selecting the correct diacritic sequence given the input diacritic-less form sequence and proposed candidates. Spriet and El-Bèze (Reference Spriet and El-Bèze1997) used a similar procedure with n-gram undiacritized form plus grammatical class language model and used Viterbi algorithm for generating restored diacritized words. Tufiş and Ceauşu (Reference Tufiş and Ceauşu2008) was an improvement over the previous candidate selection model using morphological analyzer (Tufiş and Chiţu Reference Tufiş and Chiţu1999). This version generated hypothesis using a lexicon of three dictionaries and then tagging with an approach they called tiered tagging where the tagging was done in two stages for better accuracy. These probabilistic tagging models relied on the assumption that diacritic forms of a word are closely related to the grammatical class of the word or some other morphological tags or information. Therefore, the existence (or easy acquisition) of an efficient and high-performing morphological analyzer or POS tagger is assumed.

4.5 Methods that generate intermediate candidate diacritic forms

These candidate generating models are two-staged models that restores diacritics at word level. They first generate valid diacritic words that could have given rise to the form without diacritic and then use a machine learning algorithm to select one among these valid forms. The models in this category were found mostly in diacritization in abjad writing system-based languages like Arabic. All possible diacritical forms and correlated morphological tags or feature vectors for each base word are generated through morphological analysis. This process relies on a morphological analyzer. The most commonly used morphological analyzer for Arabic was Buckwalter Arabic Morphological Analyzer (Vergyri and Kirchholff 2004; Ananthakrishnan, Bangalore and Narayanan Reference Ananthakrishnan, Bangalore and Narayanan2005; Habash and Rambow Reference Habash and Rambow2007; Roth et al. Reference Roth, Rambow, Habash, Diab and Rudin2008) and another was ArabMorpho (Al Badrashiny Reference Al Badrashiny2009), an alternative analysis tool that generates a similar but reduced feature vector. This stage of morphological analysis can be termed hypothesis generation, producing several possible diacritical forms from a given diacritic-less form. Then comes the selection of the best or most plausible candidate out of the ones proposed. Different authors accomplished this process using different statistical learning models.

In Vergyri and Kirchhoff (Reference Vergyri, Kirchhoff, Farghaly and Megerdoomian2004), training was done on the output of the analysis using an unsupervised tagging by Expectation Maximization algorithm which assigns probabilities to sequences of these morphological tags. The outcome of the tagging was a tag trigram model. The trained model was used to assign probabilities to all possible diacritizations for a given utterance. Additional acoustic information was incorporated as part of the features used for diacritization. Ananthakrishnan et al. (Reference Ananthakrishnan, Bangalore and Narayanan2005) utilized Buckwalter Arabic Morphological Analyzer to generate diacritic-form candidates for words that were labeled ‘UNKNOWN’ in a previous diacritization step. A score was computed for each hypothesis in the candidate list using the quad-gram character-based generative model (λ) based on maximum likelihood. The best-scoring hypothesis is then inserted into the appropriate location in the output generated by the word-only model. Hence, this approach was used as post-processing step to purely statistical labeling methods which were previously discussed in sections 4.2 and 4.3. Habash and Rambow (Reference Habash and Rambow2007) used the candidate list generation based on morphological analysis from Buckwalter Arabic Morphological Analyzer as input into another system called MADA extended to Morphological Analysis and Disambiguation of Arabic-D which is a set of taggers trained for individual linguistic features which are components of the full morphological tag (such as core POS, tense, number, case, mood and nunation). The taggers are based on Support Vector Machine from Support Vector Machine Toolkit. This tool narrows down the number of possible candidates either to one or some manageable size. If the output of Morphological Analysis and Disambiguation of Arabic-D is more than one, the remaining diacritic ambiguity is resolved through the application of Kneser–Ney smoothed n-gram language models built using SRILM toolkit. The trigram model gave the best performance, outperforming Vergyri and Kirchhoff (Reference Vergyri, Kirchhoff, Farghaly and Megerdoomian2004). Roth et al. (Reference Roth, Rambow, Habash, Diab and Rudin2008) used the same approach as Habash and Rambow (Reference Habash and Rambow2007), while at the same time performing the additional task of lemmatization. They also included explicit modeling of lexemes as a component in the diacritization process.

Al Badrashiny (Reference Al Badrashiny2009) took a different approach by factorizing diacritization into morphological and syntactic diacritization with the morphological aspect feeding into the syntactic aspect. For the two aspects, statistical n-gram language modeling was used to disambiguate and select the winning diacritic form out of all the analyses generated by the morphological analyzer, ‘ArabMorpho’. The morphological diacritic disambiguation (that is the selection of most probable diacritic candidate) was done with a morpheme-based language model, and an Arabic lexicon constructed from the development data using ArabMorpho. The Arabic lexicon determines whether input words have known analyses and from the possible analyses, the morpheme base language model is used to select the most probable morpheme with attendant morphological diacritics. The syntactic diacritic disambiguation worked with Morpheme-Syntactic Diacritics Language Model with the output of morphological disambiguation as input. Both stages of disambiguation rely on Maximum likelihood for estimating the sequence of words with correct diacritics. This particular research was actually focused on determining the influence of factorizing on NLP processing. Thus, it was shown that combining factorized and unfactorized inputs produced better performance than using either independently. Al Badrashiny (Reference Al Badrashiny2009) compared his results of diacritization of Arabic with those of Zitouni et al. (Reference Zitouni, Sorensen and Sarikaya2006) which did not use the candidate generation approach but used a pure labeling approach. He showed that performance of his model was better. This approach is considered appropriate for the Arabic language taking into account the morphology in which root words can lead to vast numbers of forms which may belong to different parts of speech. Thus, the use of the morphological analyzer incorporated linguistic expertise which is important for the language.

Another model that relies on a morphological analyzer is Tufiş and Chiţu (Reference Tufiş and Chiţu1999) for Romanian. It tags tokens with morpho-syntactic tags but without the diacritic forms being generated. Each token in the tagged text (the output of the tiered tagging) is associated with all possible diacritical forms in the stage of hypotheses generation. The candidates from the hypothesis generation are classified as ‘U-word’ (Unambiguous word), ‘A-word’ (Ambiguous word) and ‘C-word’ (which is subset of ‘A word’ and cannot be resolved except with sense disambiguation. The best candidate A-word is selected using frequency of occurrence in tagger dictionaries. User of diacritization software can set other criteria, for example, specifying a preference for a particular verb tense, instead of default of using frequency of occurrence in tagger dictionary. A tagger with a rich tagset would likely suffice for this diacritization model for Romanian since the morphology is not too complicated. All the models in this section may be considered translational as they seek a diacritized word form that is contextually equivalent to the non-diacritized form.

4.6 Supplementary models

Apart from the above mentioned models, there are others that have been used either mainly as baseline for evaluation or to supplement other approaches. These include the Lexicon Lookup model that relies on either an existing electronic lexicon or one built from training data. In the Lexicon Lookup model, the system works like a unigram language model that selects the diacritical form with the highest probability (frequency count). This is usually the token form with no diacritics in Scannell (Reference Scannell2011). Shaalan et al. (Reference Shaalan, Abo Bakr and Ziedan2009) extended the basic Lexicon Lookup to a bigram lookup model. Instead of storing only a word, it stored the bigram and for a given word, the bigram with the highest count is used to predict the diacritical form of a word token. Several other models used the lexical lookup (or dictionaries) as default and other methods to handle cases outside the dictionaries. A similar approach was taken in Ezeani, Hepple and Onyenwe (Reference Ezeani, Hepple, Onyenwe, Sojka, Horák, Kopeček and Pala2016) in the diacritic restoration of Igbo with backward replacement that could overwrite the diacritic form predicted for previous word if the bigram strongly suggest a better replacement.

Another model used was that based on decision list (Yarowsky Reference Yarowsky1994) which depends on word collocation similar to Bayesian classifier but is able to utilize the pieces of evidence supplied in a more systematic way. The model used context and weighted contribution of each context in the overall decision making for disambiguation. The difference between the model utilizing this decision list and the Bayesian classifier is that instead of combining all the evidences together it uses the only most applicable and best evidence. Zainkó et al. (Reference Zainkó, Csapó, Németh, Sojka and Hora2010) similarly used decision list for diacritization of words with multiple diacritical forms in Hungarian by modeling at letter level with an expanded context of ten letter to left and right of ambiguous letter within the word. The decision list was supplemented by a dictionary that dealt with words with single diacritical form. In a further study on Igbo diacritization (Ezeani, Hepple and Onyenwe Reference Ezeani, Hepple and Onyenwe2017), the decision tree was reported to have performed best among these set of five algorithms: KNN, Linear Discriminant Analysis, Support Vector Machines, Naive Bayesian classifier and Decision tree. The diacritization was fashioned after Scannell (Reference Scannell2011), while using word-level modeling instead. The reported word level accuracy was 94.49 per cent.

Abandah et al. (Reference Abandah, Graves, Al-Shagoor, Arabiyat, Jamour and Al-Taee2015) applied Recurrent Neural Network with long short-term Memory to Arabic diacritization that was modeled as sequence transcription. Two formalisms were utilized for the diacritization. The one-to-one letter encoding in which the Recurrent Neural Network was trained to individually classify each input letter with a corresponding diacritized forms with every diacritization of each letter represented with a unique symbol. The second encoding scheme was the one-to-many that outputs zero, one or more diacritics for each letter in the input sequence. The output of either scheme of Recurrent Neural Network was post-processed for letter, sukun and fatha correction. Finally, the output is checked against a dictionary that used the non-diacritized form shared by several diacritized words as key to those diacritized words found in the training data. Any word that is present but does not match any of the available diacritized variants is replaced by one that has the minimal edit distance, while anyone not found in training data is left as is. The one-to-one scheme yielded lower error rates than the one-to-many scheme on all the different training data. Diacritization error rate of 2.72 per cent and WER of 9.07 per cent was reported on the ATB3 benchmark corpus of Arabic for the one-to-one scheme.

Al-Badrashiny, Hawwari and Diab (Reference Al-Badrashiny, Hawwari and Diab2017) proposed a multilayer model that used word-level, morpheme-level and character-level language models in a pipeline arrangement to restore Arabic diacritics. In this model, when a word in a sentence could not be correctly restored with the word-level model as the first stage, it is passed along to the morpheme-level model via the Standard Arabic Morphological Analyser that generates the morphemes for diacritization. Failing diacritization at morpheme level, the morphemes would be passed to the character-level stage for plausible diacritization. The search for the best diacritic form for words the sentence is accomplished with the use of Viterbi algorithm. The multilayer model was reported to have 10.87 per cent WER.

Both Schlippe et al. (Reference Schlippe, Nguyen and Vogel2008) and Truyen et al. (Reference Truyen, Phung, Venkatesh, Tu-Bao and Zhi-Hua2008) applied other methods for diacritization. Schlippe et al. (Reference Schlippe, Nguyen and Vogel2008) modeled diacritization for Arabic as machine translation using a PBSMT. Using word level, character level and also hybrid (word and character) tokens in its PBSMT, the authors showed that word-based models performed poorer due to inability to process unknown words. The character-based model did not have such a problem but rather the performance seems to have been affected by the inability of the model to make use of context that could give sufficient information for proper restoration. The combination of both word and character into a lattice in which the PBSMT backed-off the word level to character level for unknown words yielded a better performance than the stand-alone versions of either word token or character token models. Schlippe et al. (Reference Schlippe, Nguyen and Vogel2008) further used the PBSMT for post-editing of a rule-based diacritizer and showed that the performance gotten using this approach was better than either the rule-based approach or the pure statistical approach. The same machine translation paradigm was also utilized for diacritization of Vietnamese with a reported accuracy of ninety-nine per cent, (Pham, Tran and Nguyen Reference Pham, Tran and Nguyen2013) and also to Hungarian, with morphological analyzer added to handle OOV words (Novák and Siklósi Reference Novák and Siklósi2015). Similarly, the translation approach was applied to diacritization of Serbian, Croatian and Slovene but using language and translation models combined via log-linear modeling (Ljubešic, Erjavec and Fišer Reference Ljubešic, Erjavec and Fišer2016). Tweets, Web and Wiki data were used distinctly and in combination to build diacritization models and result showed that the web data alone or when combined with others gave the best accuracy of 99.62 per cent, 99.57 per cent and 99.47 per cent for Slovene, Croatian and Serbian, respectively.

Truyen et al. (Reference Truyen, Phung, Venkatesh, Tu-Bao and Zhi-Hua2008) also applied a method that they referred to as the Powered Product of N-gram which was basically an application of n-gram language models. The authors combined n-gram language models of different orders with a weighted contribution of each individual model manually determined through trial and error method. As the author indicated, this has been pointed out to be similar to n-gram smoothing in which a lower order n-gram is used to smooth higher order n-gram to alleviate the problem of unseen n-grams. Although the Product of N-gram model gave high performance on Vietnamese, the CRF models nevertheless gave the best performance.

Ungurean et al. (Reference Ungurean, Burileanu, Popescu, Negrescu and Derviş2008) was a model that was peculiar in the sense that the model took the form of filtering out the unlikely diacritic forms through a cascade of filters. The filter was via dictionary (and ruleset) that maps undiacritized forms with only one valid form to the correct one. Those with multiple diacritical forms were filtered in succession with word unigram, word bigram and ‘suffix’ trigram if an earlier filter returns more than one candidate.