3.1 Tagging methods

The earliest POS taggers used hand-crafted linguistic rules for assigning tags to words based on character affixes of words and on the basis of the tags of the surrounding words (Klein & Simmons Reference Klein and Simmons1963, Cherry Reference Cherry1980). The tagset used in the Cherry tagger was small (only 10 labels), since the purpose of the tagger was only to label each word with its word class. Tagging words with only the word class is in most cases of limited use for NLP applications. Therefore, it is common nowadays to use a tagset consisting of tens or hundreds of different tags.

In the past twenty years or so, the availability of larger tagged corpora has encouraged researches to develop corpus-based or data-driven methods to tagging. Some of these methods have proven very effective for various languages, especially for the English language, which has been the main focus when applying these methods. It can be argued that to some extent the data-driven approaches to tagging have become a standard, and that the linguistic rule-based methods have become relatively infrequent.

The two approaches to tagging have often been considered ‘competing’ in the literature (e.g. Chanod & Tapanainen Reference Chanod and Tapanainen1995, Samuelsson & Voutilainen Reference Samuelsson and Voutilainen1997). It is, however, important to develop taggers for a particular language based on various approaches, because different approaches are likely to produce uncorrelated errors, which can be exploited in combination methods to yield better results (Halteren et al. Reference Halteren, Zavrel and Daelemans2001).

3.2 Data-driven tagging methods

Data-driven tagging methods use machine learning to automatically derive a language model from, usually, hand-annotated corpora. The main advantage of the data-driven approaches is that they are language-independent and no (or limited) human effort is needed for derivation of the model. In what follows, we describe the data-driven methods (taggers) used in this research.Footnote ¹

One type of a data-driven tagger is a probabilistic trigram tagger based on a Markov model. A trigram tagger finds an assignment of POS to words by optimising the product of lexical probabilities and contextual probabilities. Lexical probability is the probability of observing word i given POS j (p(w_i|t_j)) and contextual probability is the probability of observing POS i given k previous POS (p(t_i|t_i-1, t_i-2, . . ., t_i-k); k = 2 for a trigram model). The probabilities of the model are estimated from a training corpus using maximum likelihood estimation. Due to data-sparseness problems, maximum likelihood estimation is generally combined with an appropriate smoothing method. After training, a new sentence can be tagged automatically by assigning it the tag sequence which receives the highest probability by the model. The TnT tagger (Brants Reference Brants2000) is an example of an effective and an efficient trigram tagger.

Another type of a probabilistic data-driven tagger, the MXPOST tagger, is based on a maximum entropy approach (Ratnaparkhi Reference Ratnaparkhi1996). It generates probability distributions like other statistical methods and, additionally, uses a binary feature representation to model tagging decisions which can be compared to rules in rule-based methods. A feature f_i asks a yes/no question about a particular history, h_i (a sequence of words and tags), available when predicting tag t_i. The feature f_i, which restricts the value of t_i, encodes any information that can be used to predict t_i, such as the spelling of the current word or the identity of tags and/or words. The goal of the model is to maximise the entropy of a distribution subject to certain feature constraints.

A third type of a successful data-driven tagger, the fnTBL tagger (Brill Reference Brill1995, Ngai & Florian Reference Ngai and Florian2001), is based on the transformation-based learning approach. This approach is rule-based, but the transformation rules (which change a tag X to tag Y) are not hand-crafted, but rather automatically acquired from a pre-tagged corpus. The tagger initially assigns each word its most likely tag without regard to context.Footnote ² At each iteration, the current assignment is compared to the pre-tagged text and a transformation is learnt, which results in the greatest reduction of errors. The current assignment is updated using the learnt transformation before the next iteration starts. At the end, the result is an ordered list of transformations that can be applied to the output of the initial assignment to increase the accuracy. New unseen text is then tagged by first applying the initial annotator followed by the application of the ordered transformation rules.

The methods used by the three data-driven taggers for guessing unknown words are rather different. The unknown word guesser of the trigram tagger (TnT) uses ending analysis based on a probability distribution. The distribution for a particular ending is generated from words in the training corpus that share the same ending of some predefined length.

The maximum entropy tagger (MXPOST) uses feature templates when predicting tags for unknown words. The templates include prefixes and suffixes of length ≤ 4, as well as information regarding whether the word contains uppercase letters, hyphen(s) or a number.

The transformation-based tagger (fnTBL) uses a method, originally proposed by Brill (Reference Brill1995), which automatically learns cues to predict the most likely tag for unknown words. First, an unknown word is labelled as a proper noun if capitalised and a common noun otherwise. Secondly, transformation templates are used to learn rules which change the initial tag X to another tag Y. These templates make reference to any string of characters up to a bounded length and, typically, refer to suffixes or prefixes of words.

3.3 Linguistic rule-based tagging methods

In contrast to data-driven taggers, linguistic rule-based taggers are developed with the purpose of tagging a specific language. The purpose of the rules is either to assign tags to words depending on context or, in the more common reductionistic approach, to remove illegitimate tags from words based on context. The construction of a linguistic rule-based tagger can be a time-consuming task, since the rules are usually hand-crafted and the number of rules is often in the hundreds or thousands.

As an illustration of the number of rules used in linguistic rule-based taggers, one can mention the Swedish CG (Constrain Grammar) project where 2,100 rules are used to remove ambiguity (Birn Reference Birn1998) and EngCG-2 (English CG version 2), a project developed over several years, with 3,600 rules (Samuelsson & Voutilainen Reference Samuelsson and Voutilainen1997). A prerequisite for the effectiveness of a CG parser is the construction of a comprehensive lexicon and a morphological analyser, both of which demand large resources.

A disadvantage of the CG framework is ‘that constraints cannot be generalised, but have to be stated in a case by case fashion’ (Hinrichs & Trushkina Reference Hinrichs and Trushkina2002:63). This is probably the reason for the large number of rules usually developed under this framework. In the German parsing scheme GRIP (Hinrichs & Trushkina Reference Hinrichs and Trushkina2002), two kinds of disambiguation rules are used: ‘ordinary disambiguation rules’, which eliminate readings for a single token based on local context, and general ‘double reduction rules’, which reduce readings of a sequence of tokens, e.g. inside noun phrases. IceTagger uses a similar idea, i.e. local rules for initial disambiguation and global rules or heuristics, to force feature agreement, for further disambiguation (see section 5 below).

The error rate of the EngCG-2 system has been reported as an order-of-magnitude lower than the error rate of a statistical tagger (Samuelsson & Voutilainen Reference Samuelsson and Voutilainen1997). However, it is important to note that the EngCG-2 system does not perform full disambiguation and the results are, thus, only presented for the same ambiguity levelsFootnote ³ in the two taggers. Hence, it is not clear what the difference in the error rate between the two systems would be if both were to perform full disambiguation. Moreover, it can be inferred from this research that, when testing the EngCG-2 system, the unknown word ratio (which is not specified in the paper) is less than the corresponding ratio (2.01%) when testing the statistical tagger. The reason for this is that the former system uses a large hand-crafted lexicon, but the latter uses a lexicon derived from a training corpus.

3.4 Unknown word guessing

For a two-step tagger, as described in the introduction, the main problem in the lexical phase is guessing the tag profile for unknown words. Continuously extending the lexicon, to minimise the number of unknown words, is not practical because new words are constantly being introduced into a language. Therefore, in order to develop a high accuracy tagger, a good quality unknown word guesser is essential.

Most unknown word guessing modules use either morphological/compound analysis or ending analysis, or a combination of both. The difference between morphological analysis and ending analysis is that the former is based on morphologically related words already known to the lexicon, whereas the latter is based solely on a word's ending. Not surprisingly, research has shown that morphological analysis is more accurate than ending analysis (Mikheev Reference Mikheev1997, Nakov et al. Reference Nakov, Bonev, Angelova, Cius and vonHahn2003). This can be explained by the fact that morphologically related words share the same stem (the common part shared by all word forms) as the given unknown word, whereas ending analysis does not take the stem into account. Therefore, ending analysis, generally, produces more tag candidates than morphological analysis.

3.5 Tagging Icelandic

In 2002–2004, the Institute of Lexicography at The University of Iceland performed an Icelandic tagging experiment (Helgadóttir Reference Helgadóttir and Holmboe2004) using three state-of-the-art data-driven taggers: fnTBL, MXPOST and TnT. The training data used was the IFD corpus, a balanced corpus consisting of about 590,000 tokens. Six hundred and thirty-nine different tags appear in this corpus. Ten-fold cross validationFootnote ⁴ was used in the experiment. Each test corpus had, on average, 59,030 tokens (3,691 sentences) and the average unknown word ratio was 6.84%. The highest accuracy, 90.36%, was obtained by the TnT tagger – the average results for the three taggers can be seen in Table 3.

Table 3.

Average tagging accuracy in the Icelandic tagging experiment.

By using a simple voting scheme, i.e. selecting the tag chosen by two or more of the taggers and selecting TnT's tag in the case where all the three taggers disagreed, the total accuracy increased to 91.54%.

The accuracy of 90.36% in the Icelandic tagging experiment, obtained by the best performing single tagger, is considerably lower than the one achieved for related languages, e.g. Swedish, where 93.55% accuracy was obtained in an experiment using the same taggers, a tagset consisting of 139 tags, and a training corpus of only 100k tokens (Megyesi Reference Megyesi2002). This difference in accuracy can be explained by the large Icelandic tagsetFootnote ⁵ as well as by the fact that Icelandic is morphologically more complicated than Swedish.

Computed using the IFD corpus, the average number of tags per token is 2.74, compared to, for example, 2.05 for Swedish text as determined by a lexicon used in a CG framework (Birn Reference Birn1998). Drawing on another frequently used criterion for ambiguity of a language – the ratio of ambiguous tokens in text to the total number of tokens – I found 59.7% of the tokens in the IFD corpus to be ambiguous. Compared to English, this is a much higher ratio where, for example, 35% of the word tokens in the Brown corpus were found to be ambiguous (Kupiec Reference Kupiec1992). Note that the ambiguity rate and the ratio of ambiguous tokens are indeed tagset-dependent as much as language-dependent.

The difference in tagging accuracy between the three data-driven taggers can by and large be attributed to the difference in accuracy when tagging unknown words. The tagging accuracy of fnTBL for unknown words is relatively poor, about 25% less than the corresponding accuracy by TnT. On the other hand, since fnTBL achieves relatively high accuracy on known words, one can assume that with a better unknown word guessing module the total accuracy of fnTBL can be improved. Indeed, in section 7, I will show how to significantly improve fnTBL's unknown word tagging accuracy on Icelandic text.

It has been argued that although trigram taggers have performed well for English the same might not necessarily be true for other morphologically rich languages, for which large tagged corpora are not available (Schmid Reference Schmid, Feldweg and Hinrichs1995). The problem is data sparseness, i.e. the size of the tagset in relation to the size of the training data. In the Icelandic tagging experiment, 639 tags occurred in the training corpus and, even though the size of the training data was moderately large or about 590,000 tokens, the tagset size is very large in relation to the size of the training data. Six hundred and thirty-nine tags mean that 639³ = 261 million contextual parameters need to be estimated for a trigram tagger. Hence, on average, only about 0.002 tokens are available per parameter!

A linguistic rule-based tagger is not as sensitive to this data sparseness because its rules are not automatically derived from a tagged corpus, but rather hand-crafted using linguistic knowledge. Indeed, the rules are, to a certain extent, also dependent on a corpus – because they are constructed by examining phenomena extracted from it – but to a much lesser degree than a tagger based on a data-driven method. Moreover, some of the errors made by a data-driven tagger are due to the limited window size used for disambiguation (e.g. three words in the case of a trigram tagger). Contrastingly, a linguistic rule-based tagger can disambiguate focus words on the basis of words or tags which occur anywhere in the sentence, not only in the nearest neighbourhood.

Hence, I hypothesised that a carefully constructed linguistic rule-based tagger should perform better than a data-driven tagger when tagging a morphologically complex language, like Icelandic, using a large tagset.

Disambiguation rules can be developed using the fact that a limited set of word forms is responsible for a large part of the total ambiguity. Using the IFD corpus, I found that the 30 most frequent ambiguous word forms account for 50% of the total ambiguity, and the 153 most frequent ambiguous word forms are responsible for 67% of the total ambiguity.Footnote ⁶

Interestingly, 21 out of the 30 most frequent word forms (i.e. 70%) are pure function words or pronouns, i.e. these words do not belong to any word classes other than adverbs, conjunctions, the infinitive marker, prepositions or pronouns. Using this knowledge, one can concentrate on writing disambiguation rules for the most frequent ambiguous word forms.

4.1 The morphological analyser

The morphological analyser tries to classify an unknown word as a member of a particular morphological class. A word belongs to a morphological class if the word's morphological ending harmonises with the inflection rules of the class. The current version uses 18 morphological classes for nouns, 5 classes for adjectives and 5 classes for verbs.

Basing the analysis on morphological classes is a common approach. It is, for example, used in two German morphological systems (Lezius Reference Lezius2000, Nakov et al. Reference Nakov, Bonev, Angelova, Cius and vonHahn2003) which use a previously compiled stem lexicon for lookup. However, the morphological analyser of IceMorphy is not dependent on a stem lexicon. Any general purpose lexicon, in which each word is tagged using the Icelandic tagset, will do, but the lexicon currently used is generated automatically from the IFD corpus.

For a given unknown word, w, a morphological class is guessed based on the morphological suffix of w. Then the stem r of w is extracted and all k possible morphological suffixes for r are generated, resulting in search strings, s_i (i = 1, . . ., k), such that s_i = r + suffix_i. A lexicon lookup is performed for s_i until either a word is found with the same morphological class (deduced from the tag profile for s_i) as was originally assumed or no match is found.

A similar approach has been taken when automatically inducing rules for unknown word guessing (Mikheev Reference Mikheev1997), i.e. searching the lexicon for words that share the same stem, but have other morphological suffixes. However, the automatic rule induction method used to generate the rules for a tagger is very dependent on the training lexicon. Understandably, only rules that can be deduced by the lexicon will be produced. In contrast, the rules of IceMorphy are not dependent on a training lexicon, since they are compiled using linguistic knowledge. Another disadvantage with the automatic method is that it is not able to capture vowel mutation (e.g. kökur ‘cakes’ vs. kaka ‘cake’) which IceMorphy can do, because it is specifically tailored to Icelandic.

Consider the following example. Let us assume that the word hesturinn ‘the horse’ (a masculine, singular, nominative case noun with a suffixed definite article) is an unknown word. Based on the suffix urinn the word is assumed to belong to the morphological class of regular masculine nouns. Consequently, the stem hest is extracted and all other inflectional endings for the stem are generated (hest-ur, hest-, hest-i, hest-s, hest-ar, hest-a, etc.). Hence, search strings, s_i, are generated, such that s_i = hest + suffix_i. A lookup is performed for each s_i, and if a lookup is successful for a given search string, the appropriate tag is returned.

Subsequently, modifications need to be performed on the tag returned. Let us assume that a lookup is successful for the search string hesti (s₃) whose corresponding tag is nkeþ. The fourth letter of a noun tag denotes the case and, since a nominative case for hesturinn was assumed, the tag nkeþ needs to be changed to nken. Furthermore, the fifth character for noun tags represents suffixed article and, therefore, the article letter (g) needs to be added to this tag, resulting in the correct tag nkeng.

The morphological analyser is, however, not flawless. To illustrate, consider what happens when the word búar ‘neighbours’ is analysed. Based on the morphological suffix r and the verb búa ‘to live’, the analyser classifies this word as a third (or second) person singular verb (similarity exists, for example, ég borða ‘I eat’, hann borðar ‘he eats’). Unfortunately, the third person singular form for this particular verb is býr, because the verb is irregular.

4.2 The compound analyser

This part of the unknown word guesser uses a straightforward method of repeatedly removing prefixes from unknown words and performing a lookup for the remaining part of the word. If the remaining word part is not found in the lexicon, it is sent to the morphological analyser for further processing. If the lookup or morphological analysis deduces a tag t for the remaining word part, the original word (without prefix removal) is given the same tag t. To illustrate, consider the compound word nýfæddur ‘newborn’. By removing the first two letters, ný ‘new’, a lexicon lookup is performed for the substring fæddur. If fæddur is found in the lexicon with tag t, the word nýfæddur is assigned the same tag t. Otherwise, fæddur is sent to the morphological analyser for further processing.

Like the morphological analyser, the compound analyser can make mistakes. Consider, for example, the past participle upprisinn ‘risen up’. The compound analyser will remove the prefix upp and perform a lookup for the remaining word risinn, which, incidentally, is the masculine, singular, nominative noun risi ‘a giant’ with a suffixed definite article. Thus, the analyser incorrectly classifies the word upprisinn as a noun.

4.3 The ending analyser

The ending analyser is called if an unknown word can be deduced neither by morphological analysis nor by compound analysis. This component uses a hand-written endings lexicon along with an automatically generated one. The former, which is consulted first, is mainly used to capture common endings for verbs and adjectives, for which numerous tags are possible. By only using an automatically generated list of endings from a tagged corpus, it is almost certain (unless the tagged corpus is enormous) that not all possible tags for given adjectives will be deduced.

The automatically generated ending lexicon is constructed in the following manner. From a tagged corpus, all possible word endings of length from 1 to 5 are collected together with the corresponding tags (the minimum length of the remaining substring is 2 characters). I assume that the endings are different for capitalised words vs. other words and therefore produce two endings lexicons, one for proper nouns and another for all other words. Endings that appear with less frequency than some specific threshold (10 in my case) are filtered out.

As pointed out earlier, ending analysis is less accurate than morphological/compound analysis. For example, for the word bleðillinn ‘the sheet’, the ending analyser proposes the four tags nkeng_nkeog_lkensf_lkeosf, based on the llinn ending. However, only the first tag is correct for this particular word.

4.4 Tag profile gaps

An important feature of IceMorphy is its handling of tag profile gaps. A tag profile gap arises when a particular word, listed in the lexicon, has some missing tags in its set of possible tags. This, of course, presents problems to a disambiguator, since its purpose is to select one single correct tag from all possible ones. For each noun, adjective or verb of a particular morphological class, IceMorphy uses the methods described above to fill in the gaps for the given word.

To illustrate, consider the word konu ‘woman’, and let us assume that only the tag nveo (denoting noun, feminine, singular, accusative) is found in the lexicon. Based on the u morphological suffix and the accusative case of the tag, IceMorphy assumes that the word belongs to a particular morphological feminine noun class, in which singular accusative, dative and genitive cases have the same word form. Consequently, IceMorphy generates the correct missing tags: nveþ and nvee.

5.1 Idioms and phrasal verbs

The first step of the disambiguation process is to identify idioms, i.e. bigrams and trigrams which are always tagged unambiguously. Idioms are identified by examining lexical forms of adjacent words. The list of idioms was constructed semi-automatically in the following manner. First, we extracted automatically all trigrams in the IFD corpus that occurred at least ten times with the same tag sequence. Additionally, we hand-constructed a list of frequently occurring bigrams tagged unambiguously, by examining the development corpus (described in section 6.2).

The second step is to identify phrasal verbs, whose words are adjacent in text. An Icelandic phrasal verb is a verb–particle pair (like fara út ‘go out’) where the particle is an adverb (because it is associated with a particular verb), but not a preposition. An automatically generated lexicon (from the IFD corpus) is used for recognising phrasal verbs.

5.2 Local rules

The third step of the disambiguation process is the application of local elimination rules which perform disambiguation based on a local context (a window of 5 words; two words to the left and two words to the right of the focus word). The purpose of a local rule is to eliminate inappropriate tags from words. This reductionistic approach is common in rule-based taggers, and is, for example, used in the CG systems.

In principle, the local rules are unordered. The trigger of a rule is, however, dependent on the order of the words in a sentence. A sentence to be tagged is scanned from left to right and all tags of each word are checked in sequence. Depending on the word class (the first letter of the tag) of the focus word, the token is sent to the appropriate disambiguation routine which checks a variety of disambiguation constraints applicable to the particular word class and the surrounding words. At each step, only tags for the focus word are eliminated.

The rules are written in a separate file. A Java-like syntax is used and the rules are compiled to Java code. The format of a local rule is:

RULE <condition>

A <condition> is a boolean expression, whose individual components can refer either to lexical forms or individual characters (word class/morphological features) of tags. If <condition> is true, then the tag in question for the focus word is eliminated. The following are examples of <condition> (L₁/R₁ and L₂/R₂ denote tokens one and two to the left/right of the focus word, F, respectively):

• L₁.isOnlyWordClass(x) AND L₂.isOnlyWordClass(y)

• R₁.isWordClass(x) OR R₂.isWordClass(y)

• L₁.isWordClass(x) AND t.isCase(y) AND t.isGender(z)

• R₁.lexeme.equals(x) AND F.isWordClass(y)

A predicate like isOnlyWordClass(x) is true for a word belonging only to the word class x, while a predicate like isWordClass(x) is true for a word having the word class x as one of its possible word classes.

To exemplify, consider the following sentence: við vorum alltaf ein ‘we were always alone’. The word við can have the following five tags: ao_aþ_fp1fn_aa_nkeo. These tags denote a preposition which governs accusative, a preposition which governs dative, a first person, plural, nominative personal pronoun, an adverb, and a masculine, singular, accusative noun, respectively. Since the following word is a verb, vorum, and prepositions only precede nominals, a rule (for prepositions), with <condition>=R₁. isOnlyWordClass(Verb), eliminates preposition tags in this context, leaving only the three tags fp1fn_aa_nkeo.

5.3 Heuristics

Once local disambiguation has been carried out, each sentence is sent to a global heuristic module. Its purpose is to perform grammatical function analysis, guess prepositional phrases, and use the acquired knowledge to force feature agreement where appropriate. I call these heuristics global because, when disambiguating a particular word, a heuristic can refer to a word which is not in the nearest neighbourhood. The heuristics are a collection of algorithmic procedures that guess the syntactic structure/functions of the sentence and use it as an aid in the disambiguation process. Similar heuristics to those described below may be applicable to other morphologically complex languages.

Before the heuristics are applied, each sentence is partitioned into clauses using tokens like a comma, a semicolon, a coordinating conjunction, and a relativizer as separators (care is taken not to break up enumerations into individual parts). The heuristics then repeatedly scan each clause and perform the following in order:

1. 1. Mark prepositional phrases

2. 2. Mark verbs

3. 3. Mark subjects of verbs

4. 4. Force subject–verb agreement

5. 5. Mark objects of verbs

6. 6. Force subject–object agreement

7. 7. Force verb–object agreement

8. 8. Force agreement between nominals

9. 9. Force prepositional phrase agreement

A detailed description and evaluation of all the heuristics can be found in Loftsson (Reference Loftsson, Salakoski, Ginter, Pyysalo and Pahikkala2006a); here I only discuss, in detail, the functionality of the heuristic which guesses the subject of a verb (heuristic 3). This heuristic assumes that verbs in the current clause have already been marked by heuristic 2. For a given verb v, the tokens are first scanned starting from the left of v (since SVO order is the most likely one). If the immediate token to the left of v is a relativizer or a comma, then it is assumed that the subject can be found in the previous clause (see below). Otherwise, if the current token is a nominal and agrees with v in person and number, it is marked as a subject – if not, the scanning continues. If no subject candidate is found to the left of v, a search continues using the next two tokens to the right of v (it is thus assumed that subjects appearing further away to the right are unlikely), using the same feature agreement criterion as before. If at this point no subject candidate has been found, a search is performed in the previous clause, and the first nominal found is then marked as the subject (if it is not already marked as an object of a verb in the previous clause).

To illustrate the effect of all the above heuristics, let us consider the sentence ég fór svartar götur í vesturátt ‘I went dark streets in west-direction’.

After the application of local rules, the word/tag(s) pairs are the following:

Heuristic 1 starts by marking í vesturátt as a prepositional phrase, since í is a preposition and vesturátt is a nominal which agrees in case with the preceding preposition.

Then the main verb is marked by heuristic 2 (fór is the only possible verb).

Heuristic 3 marks the 1st person pronoun ég as a subject and heuristic 4 removes the 3rd person tag from fór, since the subject is a 1st person (leaving only the tag sfg1eþ).

Thereafter, heuristic 5 marks götur as the object, and heuristic 7 removes the nominative tag nvfn from götur because the verb fór demands an accusative object (this information is obtained from one of the lexicons described below).

Heuristic 8 then removes the nominative tag lvfnsf from the adjective svartar because of feature agreement with the already disambiguated noun götur.

Finally, heuristic 9 removes the dative tag aþ from the preposition í and the dative tag nveþ from the nominal vesturátt because the verb–preposition pair fór–í governs accusative case (again this information is obtained from one of the lexicons described below).

The correct tag sequence,

is thus produced.

To give one example where long-range feature agreement comes into play, consider the sentence ég reis á fætur og gekk að glugganum ‘I got up and walked towards the window’. Possible tags for the verb gekk are sfg3eþ_sfg1eþ, i.e. indicative, active, past tense, 3rd or 1st person singular. The 1st person tag, sfg1eþ is the correct tag in this case, because the only subject in the sentence is the 1st person pronoun ég at the start of the sentence. The above heuristics will correctly tag a scenario like this.

Two automatically generated lexicons are used as an aid in prepositional phrase agreement and verb–object agreement. The former includes information about the case a particular verb–preposition pair demands (a particular preposition can govern more than one case in Icelandic, depending on the preceding verb), whereas the latter states the case that an object of a transitive verb should have.

In addition to heuristics 1–9, specific heuristics are used to choose between supine and past participle verb forms, and ensuring agreement between reflexive pronouns and their antecedents. If a word is still ambiguous after the application of the heuristics, the default heuristic is simply to choose the most frequent tag according to frequency information derived from the IFD corpus.

Since the local rules are relatively few, the global heuristics have a large impact on the overall performance of IceTagger. For one of the test corpora, the overall tagging accuracy increases from 84.91% (after the application of local rules) to 91.36% when global heuristics are used (when computing these figures, I select the most likely tag for words that are still ambiguous after application of local rules or heuristics).

Note that due to the nature of the heuristics, IceTagger could be used to generate a kind of a shallow parsing output. Prepositional phrases are marked specifically and noun phrases could be marked as well (in connection with heuristic 8). Moreover, subjects and objects are tagged explicitly.

5.4 Special verbs

Some Icelandic verbs have special characteristics. IceTagger keeps in a special (base) lexicon auxiliaries, the verbs vera/verða ‘be/become’, and verbs that demand non-nominative case subjects (all possible word forms for these verbs are included in the lexicon). These verbs are marked in a special way to facilitate correct disambiguation decisions when encountered.

The special marking, for example, includes information on which case a verb demands for its (non-nominative case) subject. As another example, tags for word forms for the verbs vera/verða are marked with a special code, which tells the tagger to expect a predicative nominative for this verb. This mechanism simplifies rule writing, because rules do not need to be written for each word form of the given verb. The rules can instead refer to the special codes included in the corresponding tags.

6.1 IceMorphy

I first evaluated the unknown word guesser, IceMorphy. I hand-tagged 400 unknown words randomly extracted from one of the test corpora. The number of relevant (correct) tags was 1194, but IceMorphy generated 1554 tags, which divided in the following manner: 555 (35.71%) common noun tags, 266 (17.12%) proper noun tags, 553 (35.59%) adjective tags, 170 (10.94%) verb tags and 10 (0.64%) tags belonging to other word classes.

Table 4 shows precision and recall for the main word classes and for all tags as a group. Precision and recall are defined as follows:

Table 4.

Precision and recall for the given word classes using IceMorphy on 400 randomly selected words.

For the purpose of tagging, high recall is more important than high precision. It is imperative that an unknown word guesser produces as many relevant tags as possible for a tagger to disambiguate. If a relevant tag is missing, a tagger may not be able to disambiguate correctly.

Let us assume that the figures in Table 4 represent the precision and recall figures for the whole population of unknown words analysed by IceMorphy. Based on this assumption, the recall figures place an approximate upper bound on the tagging accuracy obtainable by IceTagger for unknown words. For example, the figures indicate that the overall tagging accuracy for unknown words of IceTagger will not exceed 75.7%, and that the tagger will produce highest accuracy figures for nouns. Indeed, in the next section, it will be shown that this upper bound holds for all classes except adjectives, for which the actual tagging accuracy is, in fact, higher than 71.4%.

The low precision and recall for proper nouns can be explained by the following. The last character of the tag for proper nouns denotes named entity information, i.e. a person's name, a place name or any other name. Since IceMorphy does not include a named entity recogniser, it has difficulty guessing the correct tag for proper names. When the last character of proper nouns is ignored, precision and recall for proper nouns increases to 31.20% and 96.51%, respectively.

No morphological analyser for the Icelandic language has previously been published and, thus I cannot compare my figures to results published for Icelandic.Footnote ⁷ Additionally, it is difficult to make comparison across languages because of different levels of morphological complexity and, hence, different tagsets. For the sake of making one comparison, the morphological classifier of unknown German nouns described by Nakov et al. (Reference Nakov, Bonev, Angelova, Cius and vonHahn2003) achieves 82%–89% recall (depending on the test corpus). The purpose of the German analyser is to guess morphological classes using a comprehensive stem lexicon, as opposed to predicting individual tags using a lexicon derived from a tagged corpus, as is the case for IceMorphy. Since using a more comprehensive lexicon will most certainly increase IceMorphy's accuracy, I believe my guesser obtains good results.

6.2 IceTagger

In order to make a fair comparison between IceTagger and the three data-driven taggers, I used exactly the same training and test corpora as were used in the Icelandic tagging experiment (described in section 3.5). Recall that the available hand-tagged corpus is the IFD corpus consisting of about 590,000 tokens. Pairs of 10 training corpora (each containing 90% of the IFD corpus) and 10 test corpora (each containing 10% of the IFD corpus) were constructed in the Icelandic tagging experiment. The test corpora are independent of each other, whereas the training corpora overlap. I used the first nine of these test corpora for evaluation, but the tenth one was used as a development corpus.

For each test corpus the corresponding training corpus was used to deduce the lexicons used by IceTagger – the main lexicon stating word forms and allowable tags (55,600 word forms, on average), the lexicon for phrasal verb recognition, the lexicon for verb–preposition pairs and the lexicon for verb case governance. Since each main lexicon was only deduced from the corresponding training corpus, but not as well from the test corpus, unknown words in the Icelandic tagging experiment are also unknown in tests of IceTagger. There is, however, one exception. IceTagger uses an additional base lexicon which includes words of the closed word classes (pronouns, prepositions, conjunctions) and about 120 irregular verbs. Since these words are, indeed, very common and are therefore, in most cases, already in the lexicon derived from a training corpus, the ratio of unknown words, when testing IceTagger, is only a fraction lower than the corresponding ratio in the Icelandic tagging experiment (6.79% vs. 6.84%, on average). Table 5 shows average figures for the nine test corpora used in my experiment.

Table 5.

Average figures for the nine test corpora used for evaluation.

Before I present the results, let us first discuss baseline accuracy figures for tagging Icelandic text using the given tagset. By baseline accuracy, I mean the lower bound on the accuracy that a tagger should achieve. A naive baseline tagger can be constructed by always assigning each known word its most frequent tag, and assigning each unknown word starting with a lower/upper case letter the most frequently occurring tag for common/proper nouns. The average baseline tagging accuracy for the nine test corpora using this method is 76.27% (see Table 5). This figure is considerably lower than the baseline accuracy of 80.75% for Swedish (Megyesi Reference Megyesi2002). Using similar methods for known words and assigning unknown words the most common tag for words ending in the same three letters, a baseline tagging accuracy of around 92% has been reported for English (Brill Reference Brill1992). As before, it should be borne in mind that these figures depend on the tagset used as much as on the language.

Let us now consider the results achieved by IceTagger in comparison with the three data-driven taggers: MXPOST, fnTBL and TnT. IceTagger achieves superior accuracy figures for unknown words, known words and all words for all the nine test corpora. For each test corpus, the difference between IceTagger and the closest competitor (TnT) is statistically significant (α < 0.005, using McNemar's chi-squared goodness-of-fit test as described by Dietterich Reference Dietterich1998). The average overall tagging accuracy is 91.54% compared to 90.44% for the TnT tagger. Three out of every four unknown words receive the correct analysis by IceTagger. Overall, according to the results, IceTagger makes 11.5% less errors than the TnT tagger. The average results using the nine test corpora can be seen in Table 6.Footnote ⁸

Table 6.

Average tagging accuracy of IceTagger in comparison to the three data-driven taggers.

Table 7 shows the average tagging accuracy of IceTagger for different word classes of unknown words. As noted earlier, the recall figures for the word classes shown in Table 4 constitute an approximate upper bound on the figures shown in Table 7.

Table 7.

Average tagging accuracy of IceTagger for different word classes of unknown words.

I have previously stated that morphological/compound analysis is more accurate than ending analysis. This fact is reflected in the accuracy of unknown words in IceTagger using different components of IceMorphy; see Table 8. On average, the morphological analyser produces results for 40.22% of unknown words and the average tagging accuracy for morphologically analysed words is 84.74%. In contrast, the ending analyser produces analysis for 26.29% of unknown words, resulting in only 57.09% average tagging accuracy. Bear in mind that the ending analyser is only applied if morphological/compound analysis fails, and therefore, to some extent, handles the more difficult cases.

Table 8.

Ratio of unknown words that are successfully analysed by components of IceMorphy, and the corresponding tagging accuracy of IceTagger for these words.

IceTagger has a number of different components, which have been described above. In order to estimate how individual components contribute to the overall accuracy, I evaluated different versions of IceTagger with one (or two) component(s) removed in each version. The first version uses only ending analysis (i.e. morphological and compound analysis is removed) for unknown word guessing, the second version does not use tag profile gap filling, the third version does not include the idiom module, and in the fourth version the module for phrasal verbs has been removed. Table 9 shows the result.

Table 9.

Average tagging accuracy for different versions of IceTagger.

From these results, we can deduce the following. First, the morphological/compound analysis module of IceMorphy is important, because, without it, the accuracy for unknown words drops from 75.09% to 62.84%. Furthermore, the tagging accuracy of unknown words analysed by the ending analyser increases when it is allowed to process all cases, but not only those for which morphological/compound analysis fails. Second, the average contribution of the tag profile gap filling module for all words is 0.85%. Third, the average contribution of the idiom module is 0.24%, but the contribution of the phrasal verb module is relatively modest.

In an evaluation of tagging accuracy it is common to present figures for the somewhat unrealistic case of a closed vocabulary, i.e. assuming no existence of unknown words. When I evaluated IceTagger under this assumption, the average accuracy was 93.84%.

Earlier, I explained the large difference in tagging accuracy when tagging Icelandic text vs. English text by the size of the Icelandic tagset used. Accordingly, one would expect the tagging accuracy of Icelandic to get closer to the accuracy published for English when condensing the Icelandic tagset. I tested this by ignoring some of the morphological features (like the case feature) when calculating the accuracy, effectively resulting in a set of 99 tags.Footnote ⁹ Indeed, Table 10 shows that when using a much smaller tagset the highest tagging accuracy for all words approaches 96%. Moreover, the TnT tagger obtains higher accuracy than IceTagger for this smaller tagset, which seems to indicate that IceTagger is more suitable for applications that need more fine-grained morphological information. Note, however, that valuable information (for example, indicating syntactic functions) is lost if the case feature is ignored.Footnote ¹⁰

Table 10.

Average tagging accuracy using a condensed tagset of 99 tags.