1 Introduction
Part Of Speech tagging also known as POS-tagging is the process that consists in assigning automatically to a sequence of words Grammatical Tags or Grammatical Characteristics (GC) as substantive, verb, adjective.
Example: The(definitearticle) boy(substantive) likes(verb) to(indefinitearticle) fish(verb).
In most languages, words are ambiguous. They can have more than one GC, without considering any context. For instance, the word ‘fish’ can assume the function of a verb as in the above sentence but can also can be used as a noun in another sentence. According to this, taggers have to consider the context of a word to disambiguate it, that is, to decide which should be its tag.
At first glance, the result of POS-tagging does not seem interesting in itself. However, for most robust Natural Language Processing applications, like parsing, phrase chunking, named entity recognition, information retrieval, and others, this information is very useful.
There is a substantial amount of works about POS-tagging applied to English with a rate of accuracy ranging from ninety-five per cent to ninety-eight per cent. The situation is quite different for Arabic. Obtaining a high accuracy is still a challenge to reach nowadays. This is mainly due to the particular characteristics of this language especially, agglutination and vocalization which engender a relatively high rate of grammatical ambiguities, as we will show it later.
In this paper, we present a new ant colony-based (AC) algorithm for POS-tagging both vocalized or non-vocalized Arabic texts, tested with two tagsets (composed of fine and coarse grained composite tags). The suggested approach belongs to the metaheuristic-based methods, and is especially based on ant colony. This implies the division of the process in two different tasks: learning and optimization. During the learning task, ants built their knowledge (probabilities of sequence of tags, sentence patterns) from training corpus and linguistic rules. In the optimization task, ants try to find, for a sequence of words, the optimal path among all possible sequences of GC.
The reason for using an ant-colony approach is twofold: First, AC algorithms are among the most efficient methods to deal with optimization problems modeled as a graph as it the case of POS-tagging which can be considered as an optimization problem modeled with a graph (especially for the Arabic language where the ambiguity grammatical rate is high). Second, ants can have diverse information and knowledge and then apply different methods to find the optimal sequence of GC. The collaboration of ants with diverse backgrounds allow to create a collective intelligence and increase efficiency.
The remainder of this paper is organized as follows. Section 2 explains why POS-tagging Arabic texts is a relatively difficult task. Sections 3 and 4 describe the morphological analyzer and the tagsets we used, respectively. In Section 5, we give a brief presentation of the use of ant colony for optimization problems. In Section 6, we explain the proposed approach. We describe the evaluation of the implemented system in Section 7. Finally, in Section 8, we conclude the paper and present future possible work.
2 How hard is POS-tagging arabic texts?
In Arabic, the problem of POS-tagging is much more difficult than for Indo-European languages like English and French. Indeed, Arabic is a morphologically complex language that has particular characteristics such as vocalization and agglutination which cause a lot of ambiguities.
2.1 Vocalization
Except for Quran and scholarly texts, the majority of Arabic texts contain words without vowel marks. These are diacritic signs that allow to read correctly words and to understand their meaning. Because Arabic words are vocalically ambiguous, without vowels, the reader has to see the context to find the good vocalization of a word. This vocalic confusion involves naturally much more grammatical ambiguity during tagging. The non-vocalized word
has several interpretations such as
(Make write),
(has been written),
(wrote) and
(books).
2.2 Agglutination
Arabic is an agglutinative language. Textual forms are made of the agglutination of clitics (proclitics and enclitics, e.g. articles, prepositions, conjunctions and linked pronouns) to stems (inflected or canonical forms).
Then, a single textual form in Arabic may correspond to a whole sentence or a phrase in English. Figure 1 shows an example of such an agglutinated word. Without considering any context, a textual form can be segmented in different ways. The ambiguities of decomposing textual forms induce a significant ambiguity of tagging. Moreover, when the text is not vocalized, the ambiguity of decomposition generally increases. For example, the non-vocalized textual form:
can have these three segmentations and then three interpretations:
(did he arrive?), ØFootnote
1
(is this mud?) and,
(throw in the mud).
Example of an agglutinated word.
2.3 Grammatical ambiguities
The statistics obtained by (Ben Othmane Zribi 1998) showed the importance of the rate of grammatical ambiguity for inflected forms with vowel marks, which is equal to 2.8 on average. This rate increases by the absence of the vowel marks to reach 5.6. The rate of grammatical ambiguity is more significant for textual forms because of agglutination. Calculated on texts with vowel marks, this grammatical ambiguity rate is equal to 5.6 on average, and could reach an average of 8.7 for texts without vowel marks.
3 Morphological analysis
Due to ambiguity of decomposing textual forms, we need a morphological analyzer to obtain all possible segmentations automatically. In our case, we use a rule-based morphological analyzer developed by (Ben Othmane Zribi 1998). This analyzer is able to analyze fully vocalized words, partially vocalized words and non-vocalized words. It uses two dictionaries and applies a set of rules to give for a given textual form all its segmentations (in stem and clitics) and their linguistic information. The first and larger one, has been constructed semi-automatically. It contains inflected and canonical Arabic forms with vowel marks (it counts about 1,600,000 entries corresponding to about 600,000 non-vocalized forms), for example,
(he wrote),
(she wrote),
(they wrote). Each form has different linguistic information such as lemma, POS-tag, gender, number, pronoun, etc. The second dictionary contains all clitics (it counts ninety vocalized and fifty-six non-vocalized entries), for example,
(the),
(and with),
(his).
4 Choosing a tagset
The definition of tagsets is subtle and remains up to now contentious. Even for the same language, one can find a large variety of tagsets. If we take the example of the well-known Penn Arabic TreebankFootnote 2 , different tagsets have been defined for the different versions, from part 1 to part 3, by adding morphological and syntactical features. For example, since part 3, casual inflexion (nominative, accusative, genitive) has been added. In general, the cardinality of the tagsets varies, from about ten to a few hundreds. To define tagsets, both parts of speech and the distribution of words are usually considered in order to assign different tags to words having different distributional behaviors.
A tagset with great cardinality containing fine-grained tags helps to disambiguate words in local context but risks slowing down the process of training (particularly for probabilistic taggers). On the other hand, the use of coarser tags generally improves the accuracy rates but contains less linguistic information affecting thus the quality of tagging. The ideal would be to find a good compromise between the fineness of tags and their distributional precision.
The tagging system we suggest here uses composite grammatical tags. For a given textual form, we consider the combination (specified by the plus sign ‘ + ’) of the tag of the proclitic, the tag of the stem and the tag of the enclitic (if they exist). This has two advantages. First, the system segments and tags agglutinated words in one go. Also, the context of the word to be considered during tagging is larger (than with simple tags) which would improve the efficiency of the POS-tagging system (cf. Table 1).
Examples of fine/coarse-grained tags according the textual form segmentation
In order to consider the needs of different downstream applications, we have considered two tagsets. The first one counts 438 composite tags of fine granularity (micro-tags). It is made of the combination of 223 tags for stems and sixty-five tags for clitics which are used by our morphological analyzer (Ben Othmane Zribi 1998). Various linguistic featuresFootnote
3
have been considered to discriminate words distribution. We cite, for example, parts of speech, such as
(Substantive),
(Verb),
(Adjective), . . .; the casual inflection and the definition for names:
(Nominative),
(Accusative),
(Genitive),
(Definite),
(Indefinite); the aspect, the mode and the voice for verbs such as
(Accomplished),
(Nominative unaccomplished),
(Subjunctive unaccomplished),
(Imperative),
(Passive), . . .
The second set contains 172 composite tags (macro-tags) composed of twenty-two coarse-grained tags of for stems (corresponding to the 223 tags previously cited) and sixty-five tags for clitics.
5 Ant colony-based algorithms and optimization problems
Insect societies such as ants, termites, spiders and certain species of bees and wasps have been an inspiration to many artificial systems. The example of the ant is the most common in the literature because of their ability to perform highly complex tasks from simple interactions.
Ants face various problems such as research and selection of food sources, construction and expansion of nests, sharing and organization of work. To solve these problems, ants work collectively. In most cases, the group potential becomes more than the sum of the individuals in it. Indeed, individually, an ant is not considered a very intelligent creature but in a group ants are able to perform complex tasks and demonstrate amazing intelligence (Hölldobler and Wilson 1990). This phenomenon is called ‘swarm intelligence’.
Cooperation between ants is always achieved indirectly by changing the environment (stigmergy). Ants leave on the ground traces of a volatile chemical substance called ‘pheromone’ and choose their paths according to this substance previously left. When ants come out of the nest searching for food, they are stimulated by the pheromone to follow the path towards the food source. The network of paths operates as a shared external memory for the ant colony.
The stigmergy mechanism is widely used to solve many optimization problems. In 1992, the first ant colony algorithm was designed to solve the famous combinatorial traveling salesman problem (Dorigo and Gamberdella 1997). Generally, in algorithms based on artificial ants, the environment is represented by a graph and ants use information (pheromone) stored on arcs or nodes of the graph. When searching the optimal path in the graph, ants follow pheromone trails or move randomly, to guarantee a good exploration of the search space.
6 The proposed approach
Figure 2 illustrates the general architecture of the proposed POS-tagging system based on ant colony.
General architecture of the ant colony-based POS-tagging system.
The POS-tagging system has as input a preprocessed text which is analyzed morphologically and segmented into sentences. For each sentence, ants try to find the most probable sequence of GC by relying on their own knowledge and leave trace of their choices in the collective memory of the ant colony. This memory represents the environment that allows ants to communicate together indirectly.
6.1 The ant colony-based algorithm
The environment of ants is a graph whose nodes correspond to all possible grammatical tags of words in a sentence. It contains a set of paths (successions of tags) having multi-start points. For a given number of iterations, several different types of ants are launched in parallel, looking for the most likely path. An iteration represents a back and forth of ants in the colony: ants progress from the first tag (of the first word) to the last tag (of the last word) and come back later to update the weights of each selected tag as illustrated in the algorithm below:
6.1.1 First iteration
Ants are launched randomly from different starting points corresponding to the different possible GC of the first word in the sentence to be tagged. Initially ants randomly select any starting tag and then follow any path to reach the last word. During this first pass, ants store progressively their path.
On their return (cf. Figure 3), they attribute (each according to its type) weights to the selected GC, similarly to the pheromone for natural ants. Any change to the environment provided by an ant by updating the weights of the nodes, it has selected, is stored in the common memory of the ant colony.
Searching the best sequence of GC: the first iteration.
6.1.2 Next iterations
From the second iteration, ants no longer choose tags randomly for leaving. They choose their path according to the state of the common memory, that is to say, the weight of the tags assigned during previous passages. Thus, for example moving from the tag of the ith word they always select the tag of the ith + 1 word with the greatest weight. Nevertheless, the first tag is always chosen at random to diversify the search space. On their return, ants deposit an amount of pheromone in the common memory by updating the weights of the selected tags. It is thanks to such cooperation and indirect interactions that ants build together the best or most plausible solution.
6.1.3 Pheromone
The amount of pheromone left by an ant on the selected nodes depends on its type. Initially, the quantity of pheromone is nil. While returning to a previously selected node each ant puts down a definite amount of pheromone. Following the same path, another ant may change the quantity of pheromone. The formula for updating the pheromone is expressed as follows:
$$\begin{equation}
{\Gamma _{i,n}}\left( {t + 1} \right) = r \times {\Gamma _{i,n}}\left( t \right) + \Delta {\Gamma _{i,n}}\left( f \right),
\end{equation}$$
where
ΔΓ i, n (f): represents the amount of the pheromone left by an ant of type f between the time t and time t + 1 (one iteration) on the node n for the word i;
r ∈ [0, 1[: is a coefficient which defines the evaporation of pheromone on the nodes between the time t and time t + 1.
The evaporation process is a useful mechanism of forgetting where exploring new areas of research. The aim of the evaporation is to keep a reasonable amount of pheromone on all nodes so that the ants can be sensitive to previous tracks, but without saturating them.
6.2 Types of ants
In order to diversify the knowledge ants and take advantage of multiple tagging methods, we choose four types of ants: Unary ants, Binary ants (BA), Ternary ants (TA) and Sentence Pattern-based ants. The knowledge of these ants is extracted from a textual corpus manually tagged serving as a reference and also from Arabic grammar rules. Figure 4 shows these types of ants and the knowledge they have.
Ants’ knowledge.
6.2.1 Unary ants
Unary Ants work without considering any context. For a given path, during each return and for each word of the sentence to tag, they proceed as follows:
-
(1) First, they access the lexicon built from the training data that contains triplets of (word, GC, probability of occurrence of GC with the word);
-
(2) Next, they search for the word to be processed (indexed i) in the lexicon with the GC previously selected (indexed k);
-
(3) Finally, they post pheromone on the selected node. This corresponds to the unary probability recovered from the lexicon and calculated as follows:
(2)
$$\begin{equation}
\Delta {\Gamma _{i,k}}\left( {{\rm {UA}}} \right) = p\left( {{W_i}|{\rm {G}}{{\rm {C}}_{i,k}}} \right) = \frac{{c({W_i},\ {\rm {G}}{{\rm {C}}_{i,k}})\ + \ \ {p_{{\rm {backoff}}}}({W_i}\ |GC{\ _{i,k}})}}{{c({\rm {G}}{{\rm {C}}_{i,k}}) + \lambda \ }}.
\end{equation}$$
We use a simple but effective smoothing method (add-λ smoothing with backoff) to account for unknown words, called ‘one-count’ smoothing due to (Chen and Goodman 1998), where
$$\begin{equation*}
\lambda = 1 + \# \,{\rm {of}}\,{\rm {words}}\,W:c(W,\,{\rm {G}}{{\rm {C}}_{i,k}})
\end{equation*}$$
${p_{{\rm {backoff}}}}({W_i}| {{\rm {G}}{{\rm {C}}_{i,k}}) = \frac{{c({W_i}) + 1}}{{n + {\rm {V}}}},}$
with n = # of words and V = vocabulary size
6.2.2 Binary ants
BA operate according the bigram model. This model is based on the use of probabilities of binary GC successions retrieved from the training corpus and stored in a matrix. After choosing a tag for each word in a given sentence, the BA turns back and for each word, applies the following steps:
-
(1) Get the selected GC (indexed p) for the word preceding the word to tag (indexed i);
-
(2) Consult the matrix of binary probabilities;
-
(3) Update the weight of the selected tag (indexed k) by depositing the following amount of pheromone:
(3)
$$\begin{eqnarray}
\Delta {\Gamma _{i,k}}\left( {{\rm {BA}}} \right) &=& p\left( {{\rm {G}}{{\rm {C}}_{i,k}}|{\rm {G}}{{\rm {C}}_{i - 1,p}}} \right)\nonumber \\
& =& \frac{{c(\ {\rm {GC}}i - 1,p,\quad {\rm {GC}}i,k)\ + \ \ \lambda \; {p_{{\rm {backoff}}}}(GCi,k\ |{\rm {GC\ }}i - 1,p)}}{{c({\rm {GC}}i - 1,p) + \lambda \ }}.
\end{eqnarray}$$
The binary succession of GC is smoothed in a similar fashion (but without add-one smoothing for backoff tags):
$$\begin{equation*}
\lambda = 1 + \# \,{\rm {of}}\,{\rm {tags}}\,{\rm {GC}}:c({\rm {G}}{{\rm {C}}_{i - 1,p}},{\rm {GC}}) = 1
\end{equation*}$$
${p_{{\rm {backoff}}}}(GCi,k| {{\rm {G}}{{\rm {C}}_{i - 1,p}}) = \frac{{c(G{C_{i,k}})}}{n}},$
with n = # of tags.
6.2.3 Ternary ants
TA operate according the trigram model. They operate similarly as the BA, except that they take into account for each word to process the tags of the last two words. The amount of pheromone in this case is expressed as
$$\begin{eqnarray}
\Delta {\Gamma _{i,k}}\left( {{\rm {TA}}} \right) &= &p\left( {{\rm {G}}{{\rm {C}}_{i,k}}|{\rm {G}}{{\rm {C}}_{i - 2,p}},{\rm { G}}{{\rm {C}}_{i - 1,q}}} \right) \nonumber \\
&=& \frac{{c\left( {{\rm {G}}{{\rm {C}}_{i - 2,p}},\ {\rm {G}}{{\rm {C}}_{i - 1,q}},\ {\rm {G}}{{\rm {C}}_{i,k}}} \right) + \ \lambda \ {p_{{\rm {backoff}}}}({\rm {GC\ }}i,k\ |{\rm {G}}{{\rm {C}}_{i - 2,p}},\ {\rm {G}}{{\rm {C}}_{i - 1,q}})}}{{c\left( {{\rm {G}}{{\rm {C}}_{i - 2,p}},\ {\rm {G}}{{\rm {C}}_{i - 1,q}}} \right) + \lambda \ }}.\nonumber \\\end{eqnarray}$$
The ternary succession of GC is smoothed as following:
$$\begin{equation*}
\lambda = 1 + \# \,{\rm {of}}\,{\rm {tags}}\,{\rm {GC}}:c({\rm {G}}{{\rm {C}}_{i - 2,p}},{\rm {G}}{{\rm {C}}_{i - 1,q}},GC) = 1
\end{equation*}$$
pbackoff(GC i, k |GC i − 2, p , GC i − 1, q ) = α1 p(GC i, k | GC i − 1, q ) + α2 p(GC i, k ) with α1 = 0.4 and α2 = 0.6.
6.2.4 Sentence pattern-based ants
This type of ant uses sentence patterns as a source of knowledge for tagging. This notion of sentence pattern for tagging has initially been introduced by (Ben Othmane Zribi, Torjmane and Ben Ahmed 2005) and defined as a complete model of a sentence in terms of GC sequences. If we consider the following sentence: ‘The child is eating a cake’, it can match the sentence pattern: Definite article/ Noun/Be_ing/Verb-ing/Indefinite article/Noun. We note here that a sentence pattern reflects the distributional nature of grammatical tags in the sentence (first tag, second tag, etc.).
The extraction of sentence patterns is made from a base of patterns built by scanning the training corpus and by adding the most common pattern sentence in the Arabic grammar. In practice, the production of all sentence patterns for a given language is difficult, if not impossible. Consequently, we have considered sequences of GC so-called ‘longer grammatical sequences’ whose scope is dynamic.
After following a path and on his return, the sentence pattern-based ant (PA) takes the following steps:
-
(1) For the word to tag, go to the base of sentence patterns and extract those whose first GC corresponds to the first GC of the path.
-
(2) Move to the next word, and among the patterns previously extracted retain only those whose second GC is the second tag of the path being processed, by respecting the position of the GC.
This procedure is repeated as many times as there are words in the sentence so that the number of candidate patterns in the database is reduced gradually while processing a path. Two cases can be considered:
-
• Case of fragments (sub-patterns): If for a given tag, all the extracted patterns are not sufficient (the tag for the word in position = i is not found in the patterns previously extracted at the same position) then among the different patterns previously selected the longest succession of matched tags called ‘sub-pattern’ is selected. Thus, throughout its path, the ants append little by little the fragments of patterns found in the base as shown in Figure 5.
-
• Ideal case (full pattern): ants find in the base a pattern that matches completely with all the tags in the path.
Concatenation of sub-patterns.
To update the weight of a tag (indexed k) for a given word (indexed i), we chose to consider the maximum of the unary, the binary and the ternary probabilities, since the scope of context taken into account by such ants, is greater than that of other types of ants. This can be expressed as follows:
$$\begin{equation}
\Delta {\Gamma _{i,k}}( {PA} ) = {\rm { Max}}( {\Delta {\Gamma _{i,k}}\left( {UA} \right),\Delta {\Gamma _{i,k}}\left( {BA} \right),\Delta {\Gamma _{i,k}}\left( {TA} \right)} ).\end{equation}$$
6.3 Optimal solution
The work of ants is iterative. At each iteration, ants propose their solution (a sequence of possible tags) on their return. For each proposition, a score is calculated by summing the weights of nodes (tags) path and adding a confidence rate which depends on the type of ants and which is used to weigh the importance of knowledge manipulated by ants.
This confidence rate declines with the scope of the considered context. It is calculated as following:
$$\begin{equation}
{\rm {Confidence}}\,{\rm {rate}} =\! \left\lbrace \!\!\! {$$\begin{array}{*{20}{c}}\begin{array}{*{20}{l}}\displaystyle \frac{1}{{{\rm {Number\ of\ words\ in\ the\ sentence}}/n}}{\rm {if\ Unary}}/{\rm {Binary}}/{\rm {Ternary\ ants}}\\
[3pt]{\displaystyle \frac{1}{{{\rm {Number\ of\ fragments\ in\ the\ sentence}}}}{\rm {otherwise}}\;\left( {{\rm {Patterns ants}}} \right)} \end{array}$$ \end{array}} \right.\
\end{equation}$$
with, n = 1 for Unary ants, n = 2 for BA, n = 3 for TA.
We note that in the case of PA when the pattern is full, the number of fragments is equal to 1 and CR takes the maximum value of 1.
At the end, the optimal solution corresponds to the path of tags having the highest score. Iterations stop in two cases: when the maximum number of iterations, fixed at the beginning, is reached, or the repetitive process converges on the solution; i.e. the optimal solution remains unchanged during a specified number of iterations.
7 Experimentations and results
The experiments were conducted in two phases: a learning phase and a test phase. During the learning phase, the knowledge of the different types of ants are built. The test phase, in turn, allows first, to set the parameters of the AC algorithm and secondly, to evaluate the performance of the tagging system for both vocalized texts and non-vocalized texts.
7.1 Training corpus
Ants obtain statistical and linguistic data (probabilities and sentence patterns) mainly from a training corpus, which is manually tagged. Since Arabic resources are relatively rare and we needed to use our proper tagsets (obtained from the morphological analysis), we built our own training corpus. It is a ‘corpus of Arabic contemporary texts’ completely vocalized and initially collected by (Sulaiti, 2004) that contains about 15,000 sentences and 300,000 words. The corpus was arranged into two versions: vocalized and non-vocalized, and tagged semi-automatically using mircro-tags. The mapping from micro-tags to macro-tags (coarse-grained tags) was achieved automatically.
7.2 Test corpus
For the test phase, we considered another corpus (out of the training corpus) morphologically analyzed. It includes about 3,000 sentences containing 50,000 words. We considered two versions of this test corpus: the first is vocalized while the second is not. Prior to the evaluation phase, we intended to estimate properly the difficulty of the tagging task. To do this, we measured the maximum and the average rate of grammatical ambiguity, i.e. the numbers of all possible GC assigned to a word after the morphological analysis. Table 2 shows the counts for both versions of the test corpus and for each tagset used by the tagging system.
Counts relating to the test corpus in two versions: vocalized and non-vocalized
The results obtained show us the difficulty of the tagging task and the importance of grammatical ambiguities for Arabic. As expected, the ambiguity increases when the text is not vocalized. We can also notice that this ambiguity is more important for the fine-grained tagset (micro-tags) than for the coarse-grained tagset (macro-tags).
7.3 Parameter setting
We present in this section some experiments to set and control parameters that should affect the efficiency of the ant-based algorithm. This relates to the control of the population size (number of ants), the maximum number of iterations that ants will perform and the evaporation coefficient. For this later, we chose to assign the value 0.9 (empirically tested) so that the pheromone can gradually evaporate.
To test the impact of the choice of the two parameters, namely, ‘number of iterations’ and ‘number of ants’ on the accuracy of the system, we have varied in a series of experiments the number of ants for a colony containing sixteen ants, then we added sixteen more ants gradually. For each group, we started the experiment with twenty-five iterations, we subsequently appended twenty-five new iterations repeatedly. The graphs below show the results for both versions of the test corpus (vocalized and non-vocalized). Since the results are almost the same and to avoid repetition, we present only the results for macro-tags.
The curves in the above diagrams (cf. Figures 6 and 7) seem almost the same as they have identical and proportional variations to the change in the number of iterations and the number of ants. We note that whenever the number of ants is similar to the starting ambiguity rate in the test corpus, we get better values of accuracy. Consequently, we chose to start with a number equal to the maximum number of possible tags that can have a word in our test corpus test (see Table 2), which ensures the exploration of the entire solution space (all possible sequences). However, after a certain threshold, the system stagnates by reaching the maximum accuracy. We can see that the accuracy rate stabilizes at about eighty iterations. This led us to fix the maximum number of iterations to eighty.
Accuracy variation according to the number of ants and the number of iterations (vocalized text tagged with macro-tags).
Accuracy variation according to the number of ants and the number of iterations (non-vocalized text tagged with macro-tags).
7.4 Experimental evaluation
In this section, we present the evaluation of our tagging system with the fixed parameters as explained previously. For both versions, vocalized and non-vocalized of the test corpus, the system was evaluated in a first step for each type of ants taken apart. In a second step, the evaluation was made considering all types of ants working together.
7.4.1 Evaluation of the vocalized version of the test corpus
Figure 8 shows the values of accuracy of the system working with each type of ants separately and the accuracy of the system combining all types of ants together for the vocalized version of the test corpus as well as the two tagsets.
Evaluation of the tagging system on the vocalized version of the corpus test.
Regarding macro-tags, we note that the unary ants provide low accuracy compared to other types of ants. The best accuracy rate (95.89 per cent) was achieved by the sentence PA. These later are more efficient because they make use of longer sequences of tags when considering the context. TA also give good results, mainly, because they take into account three words in context. It should also be noted that the accuracy rate of the overall system is about 97.33 per cent and it is the most important. This shows the importance of the collective behavior of ants with different knowledge enriching the collective intelligence of the entire colony.
When using micro-tags, the results are less accurate compared to the results obtained using the macro-tagset. In fact, as we have already mentioned, the tagging task becomes more difficult for a tagset of fine granularity. With micro-tags, the tagset has a larger size with more precise and more informative tags. Thus, the tagging system is facing greater ambiguity which has impact on its results. The above results already reflect this phenomenon. In this case, pattern ants are still those giving the highest accuracy (91.75 per cent). The overall system achieves a maximum accuracy of 95.3 per cent.
7.4.2 Evaluation of the non-vocalized version of the test corpus
Tagging a non-vocalized text is more difficult and achieves worse results than for a vocalized text since the ambiguity is greater, as shown in Figure 9.
Evaluation of the tagging system on the non-vocalized version of the corpus test.
As illustrated above in Table 2, a textual form can have on average twelve possible micro-tags (resp. six macro-tags) in the non-vocalized version of the testing corpus, in return this ambiguity rate decrease to reach eight possible micro-tags on average (resp. three macro-tags) for the vocalized version.
Table 3 shows also this phenomenon for the form ‘
’ which can have several vocalizations such as
. . . .The non-vocalized form ‘
’ have ten possible micro-tags. This number decreases to two and to one when this form is vocalized as “
” and “
” respectively.
Illustrative example of the impact of vocalization on POS-tagging
Furthermore, through the analysis of the results generated for macro-tags, we notice that the results of sentence PA are very close to those of the TA. The accuracy of the overall system here is of the order of 95.45 per cent.
For the second tagset, the results are low compared to previous results due to the complexity of the tagging task by considering a fine-grained tagset and a non-vocalized text. However, the system as a whole gives a fairly satisfactory accuracy of about 93.35 per cent. Compared with the results given by each type of ants apart, the sentence PA and the TA have achieved the best result with approximately the same accuracy of about ninety per cent.
7.4.3 Comparison with a Maximum Entropy-based tagger
Many Natural Language Processing problems have been successfully modeled by employing the Maximum Entropy (MaxEnt) framework. We can cite for example, POS-tagging (Ratnaparkhi 1996), parsing (Johnson et al., 1999; Ratnaparkhi 1999) and chunking (Koeling 2000). In order to make comparison with another statistical method, we have implemented and tested a MaxEnt classifier. This later seeks to maximize the conditional probability of classes, subject to feature constraints. For further details, see Ratnaparkhi (1996).
In order to make the parallel with AC tagger we chose features encoding information about the word itself (unigram feature), the previous tag (bigram feature) and the two previous tags (trigram feature) corresponding respectively to Unary/Binary /Ternary ants. Sentence PA have not yet been modeled with features due to their dynamic scope.
Example of unigram feature,
We have applied Generalized Iterative Scaling (Darroch and Ratcliff 1972) algorithm with smoothing on our training corpus to estimate the parameters of the model. We have used for this openNLPFootnote 4 , an open source MaxtEnt-based machine learning Java toolkit. For the search procedure, we have applied Beam-search algorithm with a beam size of ten to find the best sequence of tags for a sentence. Table 4 shows the obtained results (accuracy rate) for the vocalized and the non-vocalized version of the corpus test using micro-tags and macro-tags by comparison to AC tagger.
Comparison with MaxEnt-based tagger
At first glance, we can notice that MaxEnt tagger performs less than AC tagger in all configurations. Moreover, similarly to AC tagger, the results of MaxEnt tagger are worse with Micro-tags and without vocalization than when texts are fully vocalized and tagged with Macro-tags. We can notice also that the gap between the results of the two taggers is bigger when tags are fine-grained. By examining closely, the errors made only by MaxEnt tagger (comparatively to AC tagger) we determined that the principal cause of these failures was the fact that features encode only local contexts since PA have no corresponding features. Indeed, PA are based on ‘longer grammatical sequences’ and can therefore check longer dependencies while Uni/Bi/Tri-gram features use local context. We give in the following an example of error generated by MaxEnt tagger due to this limitation:
(the head of the government was informed soon
)
The word ‘
’ (soon) was incorrectly tagged as ‘
’ (indeterminate accusative substantive) instead of ‘
’ (time adverb) because the verb ‘
’ (was informed) which can help to find the correct tag is distant and is not considered by the bigram feature.
However, it should be noted that the results of MaxEnt-based tagger could be further improved by adding more complex features since MaxEnt model is able to encode various and rich information. Such features have not been investigated as we have intended to replicate the same experimental conditions for both taggers (whenever possible).
8 Related work
Some Arabic POS-taggers started to appear over the last decades and several types of methodologies have been applied, we cite, in what follows, some most recent works:
-
• Probabilistic methods: Lexical probabilities and contextual probabilities are extracted from a large annotated corpus. These methods are generally based on N-Grams or Markov models, as for the works of (Al Jihad, Yousfi and Si-Lhoussain 2011) and (Al Shamsi and Gassoum 2006).
-
• Rule-based methods: The taggers in this case use hand-coded rules as for (Kanaan, Al-Shalabi and Sawalha 2003); (Zemerli and Khabet 2004) and (Al-Taani and Abu Al-Rub 2009).
-
• Hybrid methods: It is a combination of both statistical and rule-based methods, as in the works of (Ben Othmane Zribi et al. 2005) who have proposed a multi-agent system combining probabilistic and linguistic methods, and (Hadni et al. 2013) who have integrated a HMM with rule-based method.
-
• Supervised machine leaning-based methods: The POS-tagging task is regarded here as a classification problem. Different classifiers were used, we can cite for example: SVM (Diab 2009), (Habash and Owen 2005); Conditional Random Fields (CRF) (Gahbiche-Braham et al. 2012) and memory-based learning (Mohamed and Kübler 2010).
-
• Metaheuristic-based methods: We can cite in this case, evolutionary methods which are using mechanisms inspired by biological evolution (such as reproduction, mutation, recombination and selection) to solve POS-tagging (Ben Ali and Jarray 2013), considered as an optimization problem.
The accuracy rate for the pre-cited works varies between ninety-two per cent and ninety-eight per cent (cf. Table 4). However, one can notice that the tagsets differ in their nature, simple or composite, and their fineness, fine-grained (adding morphological and syntactical features) or coarse-grained. Bigger and finer grained the tagset, the more difficult the POS-tagging. The comparison between the efficiency of these systems is difficult, because the accuracy depends on many factors, such as the size of tagset, the size, the nature (vocalized or not) and the type (journalistic, economic, educational or others) of the training and the test corpora. However, if we want to compare our work to others, we should consider those using comparable tagsets and corpora (marked with bold in Table 5).
Performances of previous Arabic POS-taggers (CO: Composite tags, S:Simple tags, F: Fine-grained tags, C:Coarse-grained tags)
We focus then on our previous work (Ben Othmane Zribi et al. 2005), and the works of (Gahbiche-Braham et al. 2012) and (Mohamed and Kübler 2010). The POS-tagger we have previously proposed, is a multi-agent system which combines five POS-taggers agents (Unigram agent, Bigram agent, Trigram agent and Hidden Markov Model agent) working in parallel with an unknown word solver agent and a voting agent that decides which tag to assign to a textual form. This system was tested on vocalized texts and with different tagsets. If we consider the tagset, which is the same as our and composed of 438 composite micro-tags, we can observe that our novel system (tested on vocalized texts) outperforms the previous one (which have achieved an accuracy of about 94.8 per cent) with an accuracy of 95.3 per cent. As regards the memory-based learning system developed by (Mohamed and Kübler 2010) which have used composite and fine-grained tags and tested on the non-vocalized version of the Penn Arabic Treebank (PATB) (Part 1V3 and Part 3 V1), our results are very close to theirs with an accuracy of 93.35 per cent (versus 93.93 per cent). When considering the work of (Gahbiche-Braham et al. 2012) which have proposed a CRF-based classifier to perform joint segmentation and POS tagging tested on non-vocalized texts extracted from the PATB and using a tagset containing 384 composite coarse-grained tags, we can observe that our results (95.45 per cent for composite macro-tags) are competitive compared to theirs (95.8 per cent). Finally, we are aware that significant comparison between POS-taggers have to be under the same experimental conditions. It should be noted that recently (Sawalha, Atwell and Aboushriah 2013) have proposed a standardization of Arabic tagset in order to simplify and promote comparisons between Arabic taggers and tagged corpora.
9 Conclusion
In this paper, we have proposed an original approach based on ant-colony for POS-tagging Arabic texts. Although there are few approaches based on swarm intelligence to solve POS-tagging problem, as far as we know, this is the first attempt that uses an AC algorithm. Since Arabic is an agglutinative language and to avoid preliminary segmentation for agglutinative words, we have opted for tagsets made up of composite tags. We have considered two tagsets, namely, fine and coarse grained, in order to take into account the needs of different downstream applications. The ants we used have diverse knowledge (probabilistic and rules-based) built from a training corpus and grammar rules. We made experimentations with the two tagsets, on both vocalized and non-vocalized texts. In all cases, the experimentations, have showed that cooperation between ants have created a collective intelligence and have increased efficiency. As expected, the results for non-vocalized texts were less accurate than for vocalized texts because the ambiguity is greater. For the same reason, the system achieved lower accuracy when tested with fine grained tags than with coarse grained tags. Although we cannot make significant comparisons with other experimentations due to the unavailability of standardization of the tagsets and the division of data set into training and test data, we can consider these results competitive compared to related works. However, we are aware that this approach, as well as metaheuristic methods in general, does not guarantee to obtain the optimal solution since it does not explore the entire search space. Moreover, tuning parameters, especially the importance of pheromone, is tricky because this needs to find a good compromise between converging quickly to a solution and finding the best solution. Finally, we plan to perform as future work other experimentations by using bigger training corpora and testing ants with other kinds of knowledge and this in order to improve accuracy in POS-tagging.
