Cvetana Krstev
email: cvetana@matf.bg.ac.yu

Duško Vitas
email: vitas@matf.bg.ac.yu

Tomaž Erjavec
email: tomaz.erjavec@ijs.si

MULTEXT-East Resources for Serbian

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The mid-nineties saw -to a large extent via EU projects -the rapid development of multilingual language resources and standards for human language technologies [START_REF] Armstrong | Multilingual corpora for cooperation[END_REF][START_REF] Ide | Multext (multilingual tools and corpora)[END_REF]EAGLES, 1996). However, while the development of resources, tools, and standards was well on its way for EU languages, there had been no comparable efforts for the languages of Central and Eastern Europe. The MULTEXT-East project (Multilingual Text Tools and Corpora for Eastern and Central European Languages) was a spin-off of the EU MULTEXT project [START_REF] Ide | Multext (multilingual tools and corpora)[END_REF]; MULTEXT-East ran from '95 to '97 and developed standardised language resources for six CEE languages [START_REF] Dimitrova | Multext-East: Parallel and Comparable Corpora and Lexicons for Six Central and Eastern European Languages[END_REF], as well as for English, the 'hub' language of the project. The project also adapted existing tools and standards to these languages. The main results of the project were lexical resources and an annotated multilingual corpus. The most important resource turned out to be the parallel corpusheavily annotated with structural and linguistic information -which consists of Orwell's novel "1984" in the English original and translations.

One of the objectives of MULTEXT-East has been to make its resources freely available for research purposes. In the scope of the TELRI concerted action (Trans European Language Resources Infrastructure), the results of MULTEXT-East had been extended with several new languages and first released on a CD-ROM, and later through Web download via TRACTOR, the TELRI Research Archive of Computational Tools and Resources.

The Serbian language did not have its representative in the MULTEXT-East project. The researchers from the Faculty of Mathematics, however, participated in the TELRI concerted action. One of the results of this participation was the Serbian "1984" structurally annotated corpus, but the morphosyntactic specification, lexicon and linguistically tagged "1984" were not produced.

Following the TELRI release, the MULTEXT-East resources were used in a number of studies and experiments. In the course of such work, errors and inconsistencies were discovered in the MULTEXT-East specifications and data, most of which were subsequently corrected. But because this work was done at different sites and in different manners, the encodings of the resources had begun to drift apart.

The '98-'00 EU Copernicus project CONCEDE (Consortium for Central European Dictionary Encoding) offered the possibility to bring the versions back on a common footing. Although CONCEDE was primarily devoted to machine readable dictionaries and lexical databases, one of its workpackages did consider the integration of the dictionary data with the MULTEXT-East corpus (Erjavec et al., 2003a). The CONCEDE release contained the revised and expanded morphosyntactic specifications, the revised lexica, and the significantly corrected and re-encoded linguistically annotated "1984" corpus.

In addition to delivering resources per-se, a focus of the MULTEXT-East, TELRI and CONCEDE projects was also the adoption and promotion of encoding standardisation. On the one hand, the morpholexical annotations and lexica were developed in the formalism of the (EAGLES-based) specifications for six Western European languages of the MULTEXT project [START_REF] Ide | Multext (multilingual tools and corpora)[END_REF]. On the other, in the TELRI edition, all the corpus resources were encoded in SGML, in CES, the Corpus Encoding Standard [START_REF] Ide | Corpus Encoding Standard: SGML guidelines for encoding linguistic corpora[END_REF]. For the corpus taken forward into the second edition, the Text Encoding Initiative Guidelines were adopted, in particular TEI P3 (Sperberg-McQueen and Burnard, 1999).

Finally, in 2004 the third version of the MULTEXT-East resources was released [START_REF] Erjavec | MULTEXT-East Version 3: Multilingual Morphosyntactic Specifications, Lexicons and Corpora[END_REF]. This release offers several contributions: it brings together the first two, i.e., offers both the TELRI and CONCEDE versions in one package; all the resources have been recoded in XML, according to TEI P4 (Sperberg-McQueen and Burnard, 2002), thus enabling them for processing with XML-based tools; and resources for new languages have been added, in particular the morphosyntactic specification for Resian, a dialect of Slovene, and, crucially the morphosyntactic specification and the annotated Orwell for Serbian.

Version 3 also contains extensive documentation, e.g., navigational HTML pages, which serve to structure and link the resources, and which include the list of participants and indexes to the resource by type and language. While the TEI headers give the most precise and up-to-date information on the corpus components, the documentation also contains a bibliography with copies of the MULTEXT-East project reports (giving details of the resources, e.g., the corpus markup process), published papers, a mirror of the TEI P4 and CES documentation and certain related MULTEXT and EAGLES reports.

A complete description of the Version 3 resources is <text id="mteo-sr." lang="sr">
 Prvi deo
 1. <p id="Osr. given in [START_REF] Erjavec | MULTEXT-East Version 3: Multilingual Morphosyntactic Specifications, Lexicons and Corpora[END_REF] and in the on-line documentation, while this paper concentrates on the Serbian resources.

In the next section we introduce the structurally annotated Serbian "1984" (already a part of the TELRI release), in Section 3 we describe INTEX, the system that has for a long time served as the infrastructure for developing LR resources for Serbian, Section 4 explains the MULTEXT-East (Serbian) morphosyntactic specification, Section 5 the linguistically annotated "1984", Section 6 the Serbian lexicon and the last section gives some conclusions and direction for further work.

Structural "1984" and alignments

The MULTEXT-East multilingual parallel corpus consists of the novel "1984", about 100,000 words in length. The corpus contains extensive headers and markup for document structure, sentences, and various sub-sentence annotations, which have been harmonised over languages. As an example, the start of the text from the Serbian Orwell is given in Figure 1.

The translations of "1984" have been automatically sentence aligned with the English original, and the alignments hand-validated. The bilingual alignments are stand-off, i.e., they are stored not with the primary data but in separate documents, as references to sentence IDs; a (hypothetical) example is given in Figure 2.

The cesDoc encoded novel served as the basis for producing the linguistically annotated version. The link between the two is maintained via sentence identifiers.

The Serbian version was produced already in the scope of TELRI. The digital source was the same as for the English and Slovene versions, namely the Oxford Text Archive, via the ECI multilingual CD-ROM. This version was plain ASCII, so it was first marked up, similar to other versions in SGML, and then sentence segmented and aligned with the English original. Also, many typographical errors were corrected.

<?xml version="1.0" encoding="us-ascii"?> <!DOCTYPE cesAlign SYSTEM "xcesAlign.dtd"> <cesAlign version="4.1"> <linkList id="Osren"> <linkGrp id="Osren.1" type="body" targtype="s" domains="Osr Oen"> <link xtargets="Osr.1.2.2.1 ;

Oen.1.1.1.1/">  <link xtargets="Osr.1.2.2.2 ; Oen.1.1.1.2 Oen.1.1.2.1/">  <link xtargets="; Oen.1.1.2.2/">  ...

INTEX and Serbian resources

Before discussing the MULTEXT-East Serbian morphosyntactic resources (the specifications, lexicon and linguistically annotated "1984") we first describe the basis for these resources, which had been developed independently of European projects, namely the Serbian morphological lexicon [START_REF] Vitas | Intex and Slavonic Morphology[END_REF] in the format of the IN-TEX system, which is based on the technology of finitestate transducers [START_REF] Silberztein | INTEX[END_REF].

In this dictionary a lemma is of the form:

W t , W l .Cn + SSD : (Codes) *
where W t represents the textual word, W l the corresponding lexical word, C is the part of speech, n is the code of inflective class, SSD is the set of syntactic and semantic attributes of the lemma that is classified as Cn, and codes describe the values of morphological categories that realized with the form W t . For instance, the dictionary entry of the noun prozor (Engl. window) is prozorom,prozor.N01+Com:ms6q, which descibes the form prozorom as the form of common (+Com) musculine (m) inanimate (q) noun (N) from the inflective class 01 in instrumental (6) of singular (s). It can be seen that this format is not as compact as MSD, as the relevant information is distributed among the inflective code, syntactic and semantic information, both associated to lexical word, and the grammatical codes which are assigned to the textual word. The codes are not positional -for a part of speech one alphanumeric character represents a value of one and only one of its attributes. The present size of the Serbian morphological dictionary, given in Table 1 enables morphological text analysis with a high percentage of success, around 90% for literary texts. Some of the word-forms that are not covered by the dictionary itself can be successfully morphologically tagged by additional tools (lexical transducers) incorporated in Intex. The use of this specifically constructed set of lexical transducers enables the recognition of various derived word-forms, such as several classes of compounds, possessive adjectives, diminutives, augmentatives, etc. [START_REF] Pavlović-Lažetić | Towards full lexical recognition[END_REF].

The team from the University of Belgrade plans to convert its full INTEX lexicon to a MSD-type lexicon. It is also planned to tag with MSDs the corpus of contemporary Serbian that is being developed at the Faculty of Mathematics (Vitas et al., 2003), where it plans to use INTEX and the lexica incorporated in it as a preprocessor.

Morphosyntactic Specifications

The MULTEXT-East morphosyntactic specifications give the syntax and semantics of the morphosyntactic descriptions (MSDs) used in the lexica and corpora. The MSDs, are structured and more detailed than is commonly the case for part-of-speech tags; they are compact string representations of a simplified kind of feature structures. The first letter of a MSD encodes the part of speech, e.g., Noun or Adjective. The letters following the PoS give the values of the position determined attributes. The specifications define, for each part of speech, its appropriate attributes, their values and one-letter codes. So, for example, the Ncmpi MSD expands to PoS:Noun, Type:common, Gender:masculine, Number:plural, Case:instrumental. It should be noted that in case a certain attribute is not appropriate (1) for a language, (2) for the particular combination of features, or (3) for the word in question, this is marked by a hyphen in the attribute's position. Slovene verbs in the indicative, for example, are not marked for gender or voice, hence the two hyphens in Vcip3s--n.

The specifications have been developed in the formalism and on the basis of specifications for six Western European languages of the EU MULTEXT project [START_REF] Ide | Multext (multilingual tools and corpora)[END_REF] and in cooperation with EAGLES, the Expert Advisory Group on Language Engineering Standards. Originally, these specifications were released as a report of the MULTEXT-East project but have been revised for both subsequent releases, and have become, if not a standard, then at least a reference for comparison (Erjavec et al., 2003b).

The MULTEXT-East morphosyntactic specifications have the following structure: (1) introductory matter; (2) the common specification; and (3) a language particular section for each language.

The common part of the specifications first defines the parts of speech and their codes; MULTEXT-East distinguishes the following, where not all PoS are used for all languages -we mark in italic those that are not used for Serbian: Noun (N), Verb (V), Adjective (A), Pronoun (P), Determiner (D), Article (T), Adverb (R), Adposition (S), Conjunction (C), Numeral (M), Interjection (I), Residual (X), Abbreviation (Y), and Particle (Q).

The formal core of the specifications resides in the common tables; they define the features, their codes for MSD <fLib type="Verb"> <f id="V0."

select="en ro sl cs bg et hu hr sr sl-rozaj" name="PoS"><sym value="Verb"/></f> <f id="V1.m" select="en ro sl cs bg et hu hr sr sl-rozaj" name="Type"><sym value="main"/></f> <f id="V1.a" select="en ro sl cs bg et hu hr sr sl-rozaj" name="Type"><sym value="auxiliary"/></f> <f id="V1.o" select="en ro sl cs et hr sr sl-rozaj" name="Type"><sym value="modal"/></f> ... representation, and their appropriateness for each language -an example is given in Figure 3.

Technically, the complete specifications are a L A T E X document (with derived Postscript, PDF and HTML renderings), where the common tables are plain ASCII in a strictly defined format. This format is suitable for a printed version, tolerable for one in HTML, and reasonably manageable for modification and addition of new languages. However, it is not suitable for processing needs, in particular to enable smooth manipulation and linking to an XML encoded corpus using the MSDs.

We have therefore implemented a (Perl) conversion of the common tables into XML, using the TEI.fs module, a tagset devoted to encoding feature-structures. This tagset is currently being used as the basis of an evolving ISO standard (currently a Draft International Standard), as part of work of ISO/TC 37/SC4 Language Resource Management.

The XML version of the common tables has one feature library for each category, e.g., fLib type="Noun" . Each feature in such a library is comprised of the identifier, which enables the linkage to corpus MSDs, the name of the attribute, the languages the feature is appropriate for, and the symbol that is its value; examples are given in Figure 4.

The Serbian specifications was produced on the basis of the Croatian one (which was added in the scope of CONCEDE), with some modifications stemming less from the differences between languages and more by the set of morphosyntactic attributes already incorporated in the Intex e-dictionaries for Serbian. For instance, in the verb table the value gerund for the attribute VForm is the most appropriate to account for present and past gerund active in Serbian. Also, the attribute Clitic is applicable to Serbian copula verbs, as well as the attribute Aspect to the most of the other verbs. Both these attributes are already encoded for all verbs in Serbian e-dictionary. One of the other differences between Croatian and Serbian tables is the recognition of the value 'paukal' for the attribute 'Number' for several PoS in Serbian.

Lexicons

The MULTEXT-East morphosyntactic lexicons have a simple structure, where each lexical entry is composed of three fields:

1. the word-form, which is the inflected form of the word, <fsLib type='Verb'> <fs id="Van" select="en et" feats="V0. V1.a V2.n"/> <fs id="Van----an----n" select="cs" feats="V0. V1.a V2.n V7.a V8.n V13.n"/> <fs id="Van----an-n---p" select="sr" feats="V0. V1.a V2.n V7.a V8.n V10.n V14.p"/> <fs id="Van----ay----n" select="cs" feats="V0. V1.a V2.n V7.a V8.y V13.n"/> <fs id="Vanp" select="ro" feats="V0. V1.a V2.n V3.p"/> ... 2. the lemma, which is the base-form of the word; where the entry is itself the base-form, the lemma is given as the equal sign; and 3. the MSD, i.e., the morphosyntactic description.

To produce the lexica, the token lists of the MULTEXT-East corpus were first fed through morphological analysers in order to produce the lemma list; this list was further extended from the comparable corpus, to arrive at at least 15,000 lemmas -some languages have further extended this, e.g., Romanian to 41,000 lemmas. In the next step, these lemmas were fed back to morphological generators (except for the agglutinative languages) in order to produce the complete inflected lists, i.e., the full paradigms of the lemmas, which constituted the final lexica of the project.

The MULTEXT-East lexica serve as medium sized morphological lexica for the languages. In addition to explicating the inflectional behaviour of the most common (and, typically, morphologically the most complex) words of the languages, the lexica also serve to establish the definitive set of valid MSDs for the languages.

For Serbian, currently, only a minimal lexicon was produced, which contains just the word-forms that in fact appear in the annotated "1984" corpus. This lexicon has 20,294 entries, 16,907 different word-forms, 8,392 lemmas and 906 MSDs.

To serve as a standard registry of MSDs, we converted the lexical MSDs to TEI feature structure libraries, fsLib , one for each category. Here each MSD is expressed as a feature structure specifying its id, the language(s) it is appropriate for, and its decomposition into features. Some examples are given in Figure 5.

Both the fsLib s and the fLib s are stored in dedicated TEI.2 element, complete with its TEI header. This document also constitutes a part of the linguistically annotated MULTEXT-East corpus. ----------------------------

Verb (V) = ============== ============== = EN RO SL CS BG ET HU HR SR SL-ROZAJ

P ATT VAL C x x x x x x x x x x = ============== ============== = 1 Type main m x x x x x x x x x x auxiliary a x x x x x x x x x x modal o x x x x x x x x copula c x x x x x x base b x ------------------------------ 2 VForm indicative i x x x x x x x x x x subjunctive s x x imperative m x x x x x x x x x conditional c x x x x x x x infinitive n x x x x x x x x x participle p x x x x x x x x x gerund g x x x x supine u x x x transgressive t x quotative q x -

Linguistically annotated "1984"

The centrepiece of the MULTEXT-East resources is the linguistically annotated "1984"; it contains word level markup, namely context disambiguated lemmas and MSDs. Because it was the first such resources for many of the MULTEXT-East languages, also Serbian, it was the most difficult and time-consuming to produce as the work had to proceed mostly manually. The annotated novel is useful as a dataset for tagger and lemmatiser induction and testing, and has already been used for this purpose in a number of experiments: an evaluation exercise [START_REF] Džeroski | Morphosyntactic Tagging of Slovene: Evaluating PoS Taggers and Tagsets[END_REF] compared four state-of-the-art trainable taggers on "1984"; [START_REF] Hajič | Morphological Tagging: Data vs. Dictionaries[END_REF] tested a feature-based tagger on the corpus; and research on tagset reductions was investigated in developing tagging models for Romanian [START_REF] Tufis | Tiered Tagging and Combined Language Model Classifiers[END_REF] and Hungarian [START_REF] Varadi | Morphosyntactic Ambiguity and Tagset Design for Hungarian[END_REF]. Another strand of research used the corpus to investigate inductive learning of rules for morphological analysis, in order to lemmatise unknown words in a text [START_REF] Erjavec | Machine Learning of Language Structure: Lemmatising Unknown Slovene Words[END_REF]). The annotated "1984" corpus also served as a testbed for experiments in word sense disambiguation [START_REF] Ide | Sense Discrimination with Parallel Corpora[END_REF] where the use of translation equivalents for automatic sense-tagging was investigated.

The work on the Serbian annotation proceeded in the following steps. First, using Intex as the tool and all of the Serbian lexical resources Serbian, "1984" was morphologically tagged. As a result, a textual file is obtained that contains the finite automaton of the text represented in the form of a regular expression. As an example, the first two sentences are given in Figure 6. In this file, each line contains one running text word, with zero, one or more associated lexical words. If no lexical word is associated this means that the word-form could not be recognized by the lexical resources. To each recognised word-form a set of grammatical categories is associated which represents the possible realizations of the word in text (for instance, for nouns: case, number, gender, and animacy). In the second step the text annotated in this way was manually checked and disambiguated. It means that not only have right lemmas and morphological categories been chosen for ambiguous word-forms and added for those words that had not been recognized, but non-ambiguous forms have also been checked in case that they had been incorrectly recognized (as is the case with the word-form dan, the last word of the first sentence in Figure 6). As a result, a non-ambiguous representation of a text is obtained in a same format. For instance, the regular expression for the same two sentences after manual correction and disambiguation is shown in Figure 7. This step had been done iteratively, chapter by chapter, which enabled both the correction of the used dictionaries and other lexical resources, and their enhancement.

In the third step, a Perl script was written and used to convert the Intex annotated text with to the MULTEXT- East annotation. The conversion is not, however, a straightforward task, not only because of the different encoding systems, as described in section 3., but also because of the differently chosen attributes. This difference can be most easily described in the case of verbs. For verbs, in MULTEXT-East the second attribute specifies a verb form, and the third a tense. However, due to the composite tenses, some verb forms are used for the construction of different tenses. For instance, in Serbian, verb form imao is the active past participle of the verb imati (Engl. to have), and is used to produce both perfect tense if used with the indicative form of the present tense of the copula verb biti (Engl. to be) -Figure 8 a) -and conditional if used with the conditional form of the same copula verb -Figure 8 b). In Intex, however, only the verb forms are recognized, which in the case of simple tenses enables the recognition of a tense as well (for instance, for present or aorist). For analytical tenses, the word-form recognition is not enough and more complex tools have to be used, as described in (Vitas and Krstev, 2003). These tools, as not yet being fully developed, were not used in the first step of the annotation process, and thus the precise mapping from Intex to MULTEXT-East tags was not possible. As a consequence, despite having different functions, the active past participle is always given the same value in the third attribute, that is tense=past, as being the most frequent.

The TEI P4 markup of the linguistically annotated Serbian "1984" obtained through this process is exemplified in Figure 9 by the same two sentences.

We also plan to use the annotated "1984" in the scope of the BalkaNet project for the validation of the Serbian Word-Net being produced, along with the other languages involved in both MULTEXT-East and BalkaNet, i.e., Czech, Bulgarian and Romanian [START_REF] Krstev | Using Textual and Lexical Resources in Developing the Serbian Wordnet[END_REF].

Conclusions

The paper presented Version 3 of the MULTEXT-East resources, and, in particular, its Serbian language resources. As the resources cover a number of inflectionally rich languages, are interlinked, harmonised, have a standardised encoding, and have been manually validated and tested in practice, they can serve as a "gold standard" dataset for language technology research and development. ... <w lemma="on" ana="Pp3msn">on</w> <w lemma="jesam" ana="Va-p3s-an-y---p">je</w> <w lemma="vecx" ana="Q-">vecx</w> <w lemma="imati" ana="Vmps-sman-n---p">imao</w> <w lemma="naslaga" ana="Ncfsa--n">naslage</w> <w lemma="salo" ana="Ncnsg--n">sala</w> ... b) ... <w lemma="ko" ana="C-s">Ko</w> <w lemma="god" ana="Q-">god</w> <w lemma="biti" ana="Vmca3s-an-n---p">bi</w> <w lemma="imati"

ana="Vmps-sman-n---p">imao</w> <w lemma="u" ana="Sps-">u</w> <w lemma="ruka" ana="Ncfsl--n">ruci</w> <w lemma="dokument" ana="Ncmsa--n">dokument</w> ... <text lang="sr" id="Osr.">

 <s id="Osr.1.2.2.1"> <w lemma="biti" ana="Vmps-sman-n---p">Bio</w> <w lemma="jesam"

ana="Va-p3s-an-y---p">je</w> <w lemma="vedar" ana="Afpmsnn">vedar</w> <w lemma="i" ana="C-s">i</w> <w lemma="hladan" ana="Afpmsnn">hladan</w> <w lemma="aprilski" ana="Aopmpn">aprilski</w> <w lemma="dan" ana="Ncmsn--n">dan</w> <c>;</c> <w lemma="na" ana="Spsa">na</w> <w lemma="časovnik" ana="Ncmsa--n">časovnicima</w> <w lemma="jesam" ana="Va-p3s-an-y---p">je</w> <w lemma="izbijati" ana="Vmps-snan-n---e">izbijalo</w> <w lemma="trinaest" ana="Mc---l">trinaest</w> <c>.</c> </s> ... While portions of the resources are distributed without any restrictions, the resources as a whole are available free of charge for research purposes only, as this was the condition imposed by some copyright holders of the sources.

Version 3 of the resources can be downloaded from the MULTEXT-East home page, http://nl.ijs.si/ME/. Access is enabled by filling out and submitting a Web based agreement, which is modelled after the one used by Edinburgh's Language Technology Group.

Currently, there are no plans to start working on Version 4; rather, the focus will be on the utility of V3, in our own research, and in enabling others to use the resources, by providing maintenance, continuing to support their accessibility and correcting errors.

Figure 1 :

 1 Figure 1: The structurally annotated Orwell

Figure 2 :

 2 Figure 2: Stand-off sentence alignments

Figure 4 :

 4 Figure 4: Morphosyntactic specifications as TEI features

Figure 5 :

 5 Figure 5: MSDs as TEI feature structures

-Figure 3 :

 3 Figure 3: Start of CommonTable for Verbs

Figure 6 :

 6 Figure 6: The output of the annotation by Intex

Figure 7 :

 7 Figure 7: Textual file containing the disambiguated text automaton in Intex format

Figure 8

 8 Figure 8: a) the active past participle imao used in active voice perfect tense; b) the active past participle imao used in conditional I

Figure 9 :

 9 Figure 9: The linguistic annotation of "1984"

Table 1 :

 1 The current size of the Serbian morphological dictionary

	PoS	Lemmas Word-Forms
	Nouns	31,000	185,000
	Verbs	14,660	436,000
	Adjectives	21,800	352,000
	other	3,400	7,600
	Total	70,860	980,600

Table for Verbs

 for

Acknowledgments

The work presented in this paper was, in part, supported by the bi-lateral project on scientific and technological cooperation between Slovenia and Serbia "The development of language resources for machine translation between the Slovene and Serbian languages".


Cvetana Krstev
email: cvetana@matf.bg.ac.yu

Duško Vitas
email: vitas@matf.bg.ac.yu

Sandra Gucul

Recognition of Personal Names in Serbian Texts

In this paper we present a method for accurate and precise recognition of personal names implemented for Serbian. It is based on development of comprehensive e-dictionaries of Serbian personal names, as well as foreign personal names transcribed to Serbian. In order to obtain high precision, the set of finite state automata (FSA) were developed to model various constraints. The same automata are also used to extract from a text personal names not yet covered by e-dictionaries.

Introduction

Recently, the importance of proper names in texts has been widely recognized since they can be successfully used in various NLP applications (Steinberger et al. 04). Thus, many attempts have been made to correctly recognize and tag them. These attempts are based on methods that vary from very simple ones (Mikheev et al. 99) to those that tend to produce the thorough inventory of proper names and their attributes. The advantage of simple methods is that they can be easily implemented and that the recognition accuracy is rather high. However, this method has serious disadvantages. First, it can not distinguish between various kinds of proper names, and second, it can associate neither morphosyntactic information to the recognized forms nor the appropriate lemma.

The method chosen for the recognition of proper names, such as geographic names, in Serbian texts is based on the approach described in (Grass et al. 02). In this paper we describe the method we develop for the recognition of personal names that is in accordance with the text processing based on lexical recognition using edictionaries and finite-state transducers (FST), method developed by LADL (Gross 88).

E-dictionaries of personal names

Electronic dictionaries of personal names are produced in the same format that is used for the gen-eral lexica. An entry in a dictionary of lemmas of DELAS type has a form lemma, Cxxx[+SynSem]. This means that to each lemma a Part-of-Speech (PoS) code (C) is attached as well as a code that determines its inflectional paradigm (xxx). Besides these obligatory elements, a various syntactic and semantic markers can be associated with each lemma (+SynSem). The DELAS type dictionary, in conjunction with the FSTs that model various inflectional paradigms, enables the production of a DELAF type dictionary of all inflected forms. The format of an entry in this dictionary is form,lemma.Cxxx[+SynSem]{:y + } * . The codes for grammatical information as well as syntactic and semantic markers can be used to retrieve information from the text.

The e-dictionary of Serbian personal names is based on an official list of Belgarade inhabitants dated from 1991 that can be considered representative for the whole Serbia and Montenegro. We have chosen for our dictionary the most frequent 3,300 first names and 17,000 surnames. The dictionary is being permanently expanded by adding unrecognized names that occur in texts being analyzed.

Since Serbian personal names inflect, it is necessary to assign the inflectional class codes to the chosen first names and surnames. All these names belong to the inflectional classes already determined for the common nouns. The first names belong to 25 different inflectional classes (21 classess for musculine names and 4 classes for feminine names), while surnames belong to 22 different inflectional classes (Table 1).

A note should be made on the gender of surnames. Surnames in Serbian behave like nouns, thus one of their features is the gender. On the other hand, surnames are equally used for men and women. Surnames never inflect if used as a part of a woman's name, while they do inflect if used individually for a man or as a part of a man's name that comes after his first name. For that reason the masculine gender was assigned to all surnames. If a surname is individually used to refer to a woman, than certain derivative forms are used (see section 3). Surnames can have plural forms, in which case they denote members of the family. The plural forms of the surnames that end in -ić are quite common, for instance Petrovići for Petrović, and can be used for a number of other surnames as well. For the others it is not clear what the plural forms would be or they look rather awkward, like for Goati or Lisjak. In order to reduce the unnecessary ambiguity all the surnames for which the plural forms are not straightforward are put into the inflectional classes for which the plural forms are not defined. If the occurences of plural forms for some particular surnames happen, their inflectional classes can be easily corrected.

The semantic markers +First and +Last were asigned to all first names and surnames, respectively. Also, all personal names in use in Serbia are given the markers +NProp, denoting that the entry is the proper name, +Hum denoting that it refers to a human being, and +SR denoting that the personal name is in use for the inhabitants of Serbia and Montenegro. In addition, nicknames have the marker +Nick associated to them. Many nicknames in Serbia are also used as first names so they have both markers associated to them (e.g. Bane). The usage of these markers will be described in the following sections.

Foreign names are in Serbian texts almost always used transcribed, rarely in its original form. For instance George Bush and Tony Blair would in Serbian text appear as Džordž Buš and Toni Bler. The foreign names inflect in the same way as the Serbian names; for instance, the instrumental forms of the mentioned names would be Džordžom Bušem and Tonijem Blerom.

We tackle foreign personal names in the same way as we do Serbian names, that is by produc-ing the dictionaries of first names and surnames in LADL format. First, we have started to produce dictionaries for the English transcribed names, on the basis of (Prčić 92). At present, DELAS dictionaries of the English first names and surnames transcribed to Serbian have 330 and 1340 entries, respectively. All the first names are grouped in 13 inflectional classes, as well as the surnames, though the two sets of inflectional classes are not the same. The same markers are associated with the entries in DELAS dictionary of English transcribed personal names as for the entries in DELAS dictionary of Serbian names (except that the marker +SR is replaced by +EN), and two more markers are added: +Val and +Norm, both of which are actually attributes to which the values are assigned. The value of the +Val is the name as originally written, while the value of +Norm is the correct transcription of the name. Namely, many English names are often incorrectly transcribed and used, and this attribute connects all the transcriptions, both correct and incorrect, of one name. It can be seen in Table 2 that four English names Clark, Clarke, Clerke and Clerke have the same transcription, Klark.

The accurate recognition of personal names in Serbian texts is far from being straightforward due to their high homonymy. The examples are numerous. Some frequent surnames are also first names, and vice versa. Some first names are used both for men and women. Many surnames and first names are homonymous with other proper -mountains, rivers, and cities. Many surnames are also names of the inhabitants of cities, regions, and countries. Surnames and first names are often homonymous with other common names for animals, plants, proffesions, etc.

The other source of problems in personal name recognition is the ambiguity of the forms. For many masculine first names the corresponding female names exists: Ivan and Ivana, with many coinciding forms: genitive and accusative case forms of the masculine name are the same as the nom- inative and vocative case forms of the feminine name, etc. Also, many masculine names have variant forms whose inflected forms also coincide, as for -Dura and -Duro, where the nominative case of the first one is the genitive case of the second one, etc. Finally, many forms of personal names are ambiguous with the forms of other lemmas (Table 3).

3 The methods for personal name recognition In Intex environment (Silberztein 04) personal names can be retrieved from a text using the described e-dictionaries. The queries can be formulatted either in a form of a regular expression or in form of a FSA. In a query, all the associated grammatical information, as well as syntactic and semantic markers can be used. For instance, in order to retrieve all musculine full personal names, consisting from both first name and surname, we could use the query (<N+First:m> <N+Last:s>) + (<N+Last:s1> <N+First:m>) that takes into account two possible orders of the first name and surname, and the rules of declination. This query is rather naïve since it does not take into consideration the agreement constraints. Thus, it retrieves many false occurrences.

When retrieving English names, the specific markers +Val and +Norm can be used. For instance, in order to retrieve all the occurrences of the name Tony Blair, no matter how it is written, in original or transcribed, the query (<N+Val=Tony> + Tony + <E>) (<N+Val=Blair> + Blair) can be used (Table 4). This query is naïve too, since names originally written also inflect (for instance, "Dio poslanika žali se da je dosta glasova izgubljeno upravo zbog Blaira..."). However, since originally written names are regularly used in Croatian, and rarely in Serbian, we are not dealing with that problem presently.

In order to recognize personal names properly it is necessary to model their usage more precisely. Since in the newspaper texts persons are usually referred to by a full name, our first goal is to model that type of usage. In this model, we take into account: (a) Two possible orders of a first name and a surname; (b) The rules of the agreement between the first name and the surname depending on the gender, as well as their agreement in case for the masculine names; (c) The optional usage of a title before the name, like prof.dr; (d) The optional usage of a second surname, separated from the first one by a hyphen or a space; (e) The optional usage of a nick name, between a first name and a surname, or after a surname; (f) The optional usage of a father's name between a first name and a surname, either as an initial, or as a first name in genitive case.

Our model of full personal names is developed modularly, so it is realised by numerous subgraphs (Figure 1). The subgraphs can thus be combined in various ways in order to satisfy specific demands, such as to retrieve the English transcribed names or to retrieve all the masculine names. (Table 5, Part I).

The application of these FSA shows that the problem of ambiguity between feminine and masculine names still persists, though in a much smaller degree (Table 5, Part II). There are still masculine names falsely retrieved among feminine names. In some cases, it is difficult to say whether it is an error at all (example 5 f), since Saša Gajin can be a name of a man or a woman, and even a wider context does not give a clue. The case of a syntactic ambiguity is exemplified by the example g), as the sentence has two possible interpretations: either "the depute director of the Institution, the man whose name is Dragi Stojiljković, has said something at the press-conference" or "the depute director of the Institution, whose name is not given, has said something at the press-conference to a woman with the name Draga Stojiljković." Only context wider than a sentence can resolve this problem. The example h) shows that sometimes the immediate context of a personal name can resolve the ambiguity. Since Podgorički stomatolog (Engl. a dentist from Podgorica) is in the nominative case, so should also be the name that follows, and that excludes the possibility that it is a feminine name.

In the newspaper texts persons are rarely referred to by a first name only. However, if a person is well-known or his/her identity has been previously established the surnames alone can be used. Since the surnames of feminine persons never inflect, they are rarely addressed by a surname only. Two derivative forms are rather used: one is derived from a possessive adjective of a surname, and an other is obtained by a gender motion. The first form, being obtained from a possessive adjective coincides with all feminine inflected forms of the adjective.

Not all derivational forms are incorporated in Serbian e-dictionaries (Krstev & Vitas 05). Those that are regularly produced and whose meaning can be deduced from the meaning of the basic word are rather recognized during the text processing by the so called transducers with lexical constraints (Silberztein 04). The recognized form is associated with an appropriate lemma and grammatical information, it inherits the syntactic and semantic markers from the basic lemma, with two more markers added: +D, which signifies that it is a derived form, +Pos or +GM that identify the type of a derivational process, possessive adjective and gender motion, respectively.

The use of this information enables the recognition of derived forms of surnames that are used to address female persons: the expression <A+Last+SR+D+Pos:fs> is used for the first type of the address, and <N+Last+SR+D+GM> is used for the second type (Table 6).

One application

The e-dictionaries and FSA described can serve various purposes. We show further how the constructed FSA can be used to extract from text a person's function or role. The person's role or function is often mentioned just before his/her personal name, or immediately after it in apposition. This function is often expressed in a form of a noun phrase of restricted structure whose head is a common noun to which a semantic marker +Hum (for human) is added. The function is often accomapnied by the institution where it is performed, and which is also expressed as the noun phrase of its own structure (Figure 2). Some full names retrieved from the sample text with their accompanying functions are given in Table 7.

For the construction of this FSA personal names were used as the anchors to model the syntactic structure of their functions (Gross 98). Since our dictionaries presently contain only Serbian names and a small number of English transcribed names, a number of personal names in the text still remains unrecognized. The FSA that model the syntactic structure of the persons' functions or roles can be used as the anchors to retrieve personal names among vaguely recognized proper names -simple words that begin with an upper-case letter and that remain unrecognized after applying all dictionaries. To achieve this, in a graph from Figure 2 the subgraphs that recognize the masculine personal names IP M sr 1, IP M sr 2, etc. should be replaced by a simple query: <N+NProp+Unk> <N+NProp+Unk>. Here marker +Unk stands for a proper name of unknown type. In Table 8 some extracted names of various origin are given.

Conclusion

The method we have developed for personal name recognition is giving very promising results. Not only can we recognize personal names with high precision and recall, but the full grammatical information associated with them enables their usage for many advanced purposes, such as text disambiguation. Also, by transforming the developed FSA into FSTs it is possible to automatically tag personal names in a text with XML tags, in a manner of TEI tags <persName> and <name>.

Figure 1 :

 1 Figure 1: The subgraph IP M sr 2 recognizes Serbian masculine full name in genitive case

  Part I: some correctly retrieved Serbian full names: a) Two surnames separated by a hyphen; b) Name preceded by a title; c) Father's name as an inital; d) A nick name between a first name and a surname; e) Two surnames separated by a space; Part II: Some masculine names falsly retrieved among feminine names. Some examples of references to female persons by s surname only (a) The expression of the second type always yields correct results; (b) This type of address can be used in combination with the first name; (c) The expression of the first type gives all instances of female persons addresed in this way; (d) False retrieval, also a possessive adjective is actually used; (e) The first type of derivation is used for the transcribed foreign names as well (Olbrajtova stands for Madeleine Albright).

  Recognized foreign personal names adjacent to the syntactic structure representig the function of a person.A false retrieval is given in the last line (Dojče Telekom stands for Deutsche Telekom): the noun vlasnik (Engl. owner), marked as human, is used for an organization

Figure 2 :

 2 Figure 2: The subgraph IP M sr samo zvanja recognizes Serbian masculine full name followed by person's function; it takes into account that the full name and the noun phrase that follows have to agree in case.

Table 2 :

 2 Excerpts from the DELAS dictionaries of English first names and surnames

	Klerk,N1002u+NProp+Hum+First+EN
	+Val=Clark+Val=Clarke
	+Val=Clerk+Val=Clerke+Norm=Klark
	Olbrajt,N1002+NProp+Hum+Last+EN
	+Val=Albright+Val=Allbright

Table 3 :

 3 Concordance lines retrieved by the query <N+First>: a) Nominative plural form of the noun an - deo (Engl. angel) is recognized as a dative singular form of the first name Andela; b) Third person present form of the verb ići (Engl. to go) is recognized as a genitive form of the first name Ida; c) Feminine nominative singular form of the adjective divan (Engl. wonderful) is recognized as the nominative form of the first name Divna.

	okupacijskim. Umjesto toga,	Buš	je rekao kako je gruzijska ružičasta revol uci
	dsednika SAD. Američki predsednik	Džordž Buš	, koji je juče boravio u poseti toj zemlj
	demokraciju Američki predsjednik George W. Bush u ponedjeljak je iz Moskve doputovao u

Table 4 :

 4 An excerpt from the concordances obtained by applying the regular expression for George Bush to a text containing news from one Belgrade and one Zagreb daily newspaper.

Table 5 :

 5

  vršilac dužnosti predsednika Srbije i predsednik parlamenta Nataša Mićić Nebojša Čović, predsednik Koordinacionog centra za Kosovo i Metohiju i potpredsednik Vlade Srbije predsednikom Sjedinjenih Država Džordžom V. Bušom bivšem američkom državnom sekretaru Medlin Olbrajt

Table 7 :

 7 Serbian and English personal names with their functionsTamir Gadban, zvaničnik zadužen za iračku naftnu industriju potpredsednikom banke za Evropu i centralnu Aziju Šigeom Katsuom Redžep Tajip Erdogan, lider vladajuće Partije pravde i razvoja Dojče Telekom, većinskog vlasnika Hrvatskog telekoma,

Table 8 :

 8


Prasanna Muralidharan

James Fishbaugh

Hans J Johnson

Stanley Durrleman

Jane S Paulsen

Guido Gerig

P Thomas Fletcher

Diffeomorphic Shape Trajectories for Improved Longitudinal Segmentation and Statistics

Longitudinal imaging studies involve tracking changes in individuals by repeated image acquisition over time. The goal of these studies is to quantify biological shape variability within and across individuals, and also to distinguish between normal and disease populations. However, data variability is influenced by outside sources such as image acquisition, image calibration, human expert judgment, and limited robustness of segmentation and registration algorithms. In this paper, we propose a two-stage method for the statistical analysis of longitudinal shape. In the first stage, we estimate diffeomorphic shape trajectories for each individual that minimize inconsistencies in segmented shapes across time. This is followed by a longitudinal mixed-effects statistical model in the second stage for testing differences in shape trajectories between groups. We apply our method to a longitudinal database from PREDICT-HD and demonstrate our approach reduces unwanted variability for both shape and derived measures, such as volume. This leads to greater statistical power to distinguish differences in shape trajectory between healthy subjects and subjects with a genetic biomarker for Huntington's disease (HD).

Introduction

Statistical shape modeling and analysis is of critical importance for better understanding of longitudinal imaging and shape data, especially in the context of dynamic processes like aging and disease progression. To model evolution of shape, many regression approaches for cross-sectional data have been proposed [START_REF] Davis | Population shape regression from random design data[END_REF][START_REF] Niethammer | Geodesic regression for image time-series[END_REF][START_REF] Fletcher | Geodesic regression and the theory of least squares on riemannian manifolds[END_REF][START_REF] Hinkle | Polynomial regression on Riemannian manifolds[END_REF]. However, regression has limitations when applied to longitudinal analysis, since each individual could start at a different point and evolve in a different manner. Longitudinal studies therefore entail development of subject-specific spatiotemporal models, and also a way to compare these models across different subjects [START_REF] Qiu | Time sequence diffeomorphic metric mapping and parallel transport track time-dependent shape changes[END_REF][START_REF] Muralidharan | Sasaki metrics for the analysis of longitudinal data on manifolds[END_REF][START_REF] Datar | Mixed-effects shape models for estimating longitudinal changes in anatomy[END_REF][START_REF] Durrleman | Toward a comprehensive framework for the spatiotemporal statistical analysis of longitudinal shape data[END_REF].

Longitudinal image data has several sources of variability. First, there is inherent biological variability, both within a subject changing over time and also between subjects in a population. The goal of longitudinal analysis is to quantify this variability and make inferences about changes over time in a population. However, longitudinal imaging data also include unwanted sources of variability, such as noise in image acquisition, segmentation and registration errors, and human expert judgment, among others. These extraneous errors tend to dampen statistical power, especially when trying to distinguish between trajectories of two different populations, e.g., healthy and diseased.

In this paper, we propose a framework that first seeks to reduce this extraneous variability, thus improving consistency of longitudinal segmentations in the first stage. We follow the procedure of [START_REF] Fishbaugh | Geodesic Shape Regression in the Framework of Currents[END_REF] by estimating diffeomorphic geodesic trajectories of shape evolution for each individual. The estimated trajectories are smooth, resulting in temporally consistent and more biologically plausible shape evolution. We then employ a mixed effects model for shapes [START_REF] Cates | Shape modeling and analysis with entropy-based particle systems[END_REF][START_REF] Datar | Mixed-effects shape models for estimating longitudinal changes in anatomy[END_REF] to conduct longitudinal statistical shape analysis on the consistent shape trajectories. We demonstrate the benefit of our two stage approach by a comparison of longitudinal mixed-effects analysis on cortical volumes obtained from raw observed data against consistent measurements obtained from personalized spatiotemporal shape models. We also show our method reduces unwanted variability for both shape and derived measures, such as volume. This leads to greater statistical power to distinguish shape evolution between healthy subjects and subjects with a genetic biomarker for Huntington's disease (HD).

Methodology

We present here methodology for the statistical analysis of longitudinal shape complexes. This is based on spatiotemporal modeling of diffeomorphic shape trajectories (Section 2.1) to produce temporally consistent shape sequences. Estimated model trajectories represent more biologically plausible and smooth shape changes associated with anatomical evolution in time. Statistical measures and group hypothesis testing is then conducted on both scalar measurements extracted from shape as well as the shape complexes themselves. For measuring individual and group shape differences, we estimate a multivariate mixed-effects model (Section 2.2) for shapes, designed to take advantage of longitudinal shape data.

Spatiotemporal modeling for consistency in longitudinal segmentation

Anatomical change over time associated with neurodevelopment or aging is assumed to be a smooth process. That is, the trajectory of a particle on an anatomical surface should be differentiable, with no instantaneous change of direction. The presence of a disorder such as Huntington's disease (HD) would not invalidate the smoothness assumption. Rather, the neurodegeneration process associated with HD has been observed as a temporally smooth process [START_REF] Aylward | Association between Age and Striatal Volume Stratified by CAG Repeat Length in Prodromal Huntington Disease[END_REF]. However, our anatomical measurements (medical images and extracted anatomical shapes) are often not representative of samples from a smooth process, due to the natural variability attributed to image acquisition, subject positioning, segmentation, etc. Without temporal consistency in our measurements, it becomes difficult to distinguish between anatomical change associated with disease from changes due to noise. One emerging model of smooth anatomical change is to consider continuous transformations of the ambient space by differentiable and invertible deformations. We model anatomical trajectories by a geodesic flow of diffeomorphisms that continuously deforms a given anatomical configuration X 0 over time to closely match a set of observed anatomical shapes O ti [START_REF] Fishbaugh | Geodesic Shape Regression in the Framework of Currents[END_REF]. The initial anatomical configuration (baseline shape), as well the flow of diffeomorphisms φ t , are estimated by minimizing the criterion

E(X 0 , φ t ) = i D(φ ti (X 0 ) -O ti ) + Reg(φ t ),
where D represents a distance metric on shapes and Reg(φ t ) is a measure of the regularity of the geodesic flow of diffeomorphisms φ t . For choice of D, we favor the metric on currents, which is robust to topological differences and allows for comparison between shapes without the need for point correspondence. Also, being in an infinitedimensional space of diffeomorphisms, geodesic trajectories have the flexibility to capture complex deformations.

The continuous geodesic flow of diffemorphisms φ t is applied to the estimated anatomical configuration to produce a continuous and temporally consistent sequence of shapes. The improved temporal consistency is illustrated on the left side of Fig. 1 by comparing the volume of observed caudates with the volume extracted continuously from the spatiotemporal model of caudate shape. Also note that we can now obtain shapes or measurements extracted from shapes at any time point of interest, not just those corresponding to observations.

Mixed effects model for shapes

We now have a diffeomorphic flow of anatomical shapes for each individual, from which we obtain shapes at time points corresponding to actual observations. These es-timated shapes no longer represent independent (and potentially noisy) measurements, but instead take into account correlation between repeated scans of the same individual.

Statistical interpretation of longitudinal shape data is extremely useful in ascertaining differences in repeated image scans of an individual and also between individuals within and across populations. A compact statistical representation of shape was proposed by [START_REF] Cates | Shape modeling and analysis with entropy-based particle systems[END_REF], wherein the surface of a shape is represented by a collection of points, also referred to as a particle system. Particle positions are optimized to be in correspondence across an ensemble of shape configurations. A faithful shape representation is achieved by minimizing a cost function, that balances a low residual error of model to data, also seeking configurations of uniformly-distributed correspondence positions on shape surfaces.

To analyze longitudinal data, [START_REF] Datar | Mixed-effects shape models for estimating longitudinal changes in anatomy[END_REF] generalize the methods in [START_REF] Cates | Shape modeling and analysis with entropy-based particle systems[END_REF] to incorporate a linear mixed-effects model in the optimization framework. Let Y i be the longitudinal response variable for the ith individual (a shape configuration), and X i denote the explanatory variable, typically time. The mixed-effects model for longitudinal correspondences is given as

Y i = X i (α + b i ) + ǫ i ,
where α are the fixed-effects parameters (group intercept, group slope), while b i are random-effects parameters with ǫ i being the error in correspondences for the ith individual. For details on model parameter estimation, see [START_REF] Datar | Mixed-effects shape models for estimating longitudinal changes in anatomy[END_REF].

Hypothesis testing In order to test the statistical significance of group-parameter differences between two groups of longitudinal data, [START_REF] Datar | Mixed-effects shape models for estimating longitudinal changes in anatomy[END_REF] also outline a statistical hypothesis permutation test based on the Hotelling's T 2 statistic. Given two groups of data, {p 1 , . . . , p m } and {q 1 , . . . , q n }, with sample means p, q, recall that Hotelling's T 2 statistic is a test statistic to test for significant differences between sample means, relative to the pooled sample covariance W:

W = i (p i -p)(p i -p) T + i (q i -q)(q i -q) T m + n -2 .
The T 2 statistic can be thought of as a squared Mahalanobis distance between the means, using the pooled covariance W . The sample T 2 statistic is given by

t 2 = mn m + n (p -q) T W -1 (p -q).
The permutation test procedure is as follows: (1) compute the t 2 statistic, (2) randomly permute (swap) data points between the p and q groups, computing a t 2 k statistic for the permuted groups, (3) repeat step 2 for k = 1, . . . , P , (4) compute the p-value: p = B/(P + 1), where B is the number of t 2 k < t 2 . The final p-value can be interpreted as the probability of finding a larger group difference by random chance under the null hypothesis (that there is no difference between the means). The underlying assumption of any permutation test is that the data should be exchangeable under the null distribution. Our null hypothesis is that the groups (e.g., healthy and diseased) are from the same distribution. We permute individuals (keeping their timepoints all intact), which under this null assumption is exchangeable.

To test for differences in anatomical trajectories between a healthy and disease group, also note that it is important to distinguish if the shape differences are present at baseline (intercept) or if they develop over time (slope). To make this distinction, we also separate the above Hotelling's T 2 test into these two components.

Experimental Validation

We study subcortical change associated with Huntington's disease (HD), leveraging the longitudinal study PREDICT-HD. The longitudinal database consists of 65 female subjects: 23 controls (CTRL), 14 (LOW), 15 (MED), and 13 (HIGH). The LOW / MED / HIGH categories represent probability of onset of manifesting signs of HD. All subjects have had at least 3 MR images acquired approximately one year apart, with many subjects undergoing multiple scans per visit. Six subcortical pairs (caudate, putamen, hippocampus, thalamus, acumben, and pallidus) were segmented from each image (Fig. 2) and manually verified and cleaned [START_REF] Kim | Robust multi-site mr data processing: Iterative optimization of bias correction, tissue classification, and registration[END_REF]. The quality of each segmentation varies considerably for each time point, even when scans are obtained on the same day from the same scanner, as individual single-subject segmentation is prone to errors related to variability of imaging, image calibration, human expert judgment, and limited robustness of segmentation algorithms. While the segmentation quality is not easily assessed by viewing the 3D anatomical surfaces, the temporal inconsistency becomes clear by investigating volume extracted from the shapes. The right side of Fig. 1 shows the variability in segmentation, illustrated by the temporal inconsistency of observed caudate volume, motivating the need for temporally consistent segmentations which properly account for correlated longitudinal data.

Personalized spatiotemporal models of subcortical change Continuous models of shape trajectory are estimated for each subject using the methodology outlined in 2.1, resulting in personalized and temporally consistent anatomical evolution. Model estimation does not require point correspondence, facilitating the inclusion of all subcortical shapes simultaneously without imposing any topological constraints. Each subject's personalized model allows us to generate shapes at any instant in time, from which desired shape properties, such as volume, can be extracted. We can therefore obtain a continuous evolution of volume for all subcortical structures without any explicit modeling of volume. Fig. 1 shows caudate volume extracted from each subject's continuous shape model, demonstrating the flexibility of the shape model to capture both linear and non-linear volume trends with no prior assumption or constraint on linearity. Though we only display caudate volume here, recall that each model is estimated by leveraging all shape data simultaneously (Fig. 2), which respects shape boundaries and locations, incorporating important geometric relationships between shapes. 1)

Longitudinal analysis of striatal volume Here we conduct a univariate analysis of volume extracted from shape, as striatal volume loss has been shown to be associated with the progression of HD [START_REF] Aylward | Association between Age and Striatal Volume Stratified by CAG Repeat Length in Prodromal Huntington Disease[END_REF]. We aim to evaluate the benefit of spatiotemporal shape modeling, by comparing striatal volume extracted from the temporally consistent shapes with volume extracted from the raw shape observations. Figure 3 shows the results of linear mixed-effects analysis on striatal volumes for observed (left) and temporally consistent shapes (right), testing for the interaction between age and group membership. The estimated fixed-effects parameters for the temporally consistent (smoothed) category were found to be significant, as shown in Table 1. This demonstrates the benefit of spatiotemporal shape modeling, as striatal volumes extracted from the temporally consistent shapes provide better separation between the control and LOW groups, and also between the control and HIGH groups.

Another benefit of spatiotemporal shape modeling is seen in the standard error of estimated parameters (Table 1). The standard error is consistently lower for temporally consistent shapes, which implies a reduction in unwanted variability present in the original segmentations. Further note in Fig. 3, the mixed-effects model fits the temporally consistent data better than the observed striatal volume. We also performed separate longitudinal mixed-effects analysis on the caudate and the putamen, and found a similar story in both cases.

Longitudinal analysis of striatal shape We next perform a multivariate Hotelling's T 2 hypothesis test (Section 2.2) of the baseline shape (intercept) and trend (slope) between controls and the combined HD groups. We compare the results for analyses using the original observed segmentations versus those obtained from spatiotemporal modeling as described in (Section 2.1). We represent these shapes in the particle optimization framework to estimate longitudinal fixed and random effects. Note that we do not normalize for size in these experiments, which means that we test for differences between control and combined HD groups based on both shape and size. Figure 4 shows the estimated fixed-effects parameters for both groups, i.e., the baseline (intercept) shape with trajectory (slope) displayed as a color map. When comparing baseline shapes, we don't find significant difference between controls and HD in either analysis. This is expected, as the onset of degeneration in HD is expected at a later age. But when comparing shape trends, we find significant differences between controls and HD for the temporally consistent shapes, but not in the case of raw shape observations.

Table 2 provides the p-values from the statistical hypothesis test between the control and combined HD groups. In both the left and right caudate, the temporally consistent shapes result in lower p-values. Specifically, the left caudate is statistically significant at the 5% level. Similar to the volume analysis, this demonstrates that temporally consistent shape trajectories result in greater ability to distinguish differences in longitudinal trends between controls and HD groups.

Conclusion

Diffeomorphic trajectories are good at capturing smooth anatomical shape changes, while the particle optimization framework excels at finding compact statistical shape representations with increased statistical power. The novelty of our work is to leverage the strengths of both approaches, to provide an integrated solution, characterized by improved statistical performance in the analysis of both scalar and shape trajectory data derived from noisy segmentations. We demonstrate the advantages of our method through improved statistics on temporally consistent shape and volume measures in the analysis of the PREDICT-HD dataset.

Fig. 1 .

 1 Fig. 1. Left: For one subject, volume of observed caudates (open circles) and temporally consistent continuous volume extracted from diffeomorphic shape model (solid line). The difference in caudate volume extracted from scans obtained on the same day highlights the need for consistent segmentation. Right: Observed volume and volume extracted from diffeomorphic shape models for all 65 subjects. While the volume of the discrete shape observations show considerable variation, volume extracted from personalized models are continuous and temporally consistent.

Fig. 2 .

 2 Fig. 2. Example of six subcortical pairs extracted for each subject and timepoint.

Fig. 3 .

 3 Fig. 3. Longitudinal mixed-effects analysis of striatal volumes obtained from observed shapes (Left) and temporally consistent shapes (Right). Volume data are shown as filled black circles with corresponding individual trends. Note the improvement of the model fit in the consistent striatal volume over the observed striatal volume, which results in lower standard error of estimated mixed-effects parameters. (SeeTable 1)

Fig. 4 .

 4 Fig. 4. Left: Fixed-effects parameters for observed caudate shapes (Far Left-Control, Mid Left-HD), Right: Fixed-effects parameters for temporally consistent caudate shapes (Mid Right-Control, Far Right-HD); Fixed effects slope: Blue-Red indicates Local Contraction -Expansion

Table 1 .

 1 Comparison of the standard error and significance values of fixed-effects parameters of longitudinal volumes obtained from observed and temporally consistent shapes

	Parameter	Std. error (obs.) Std. error (smoothed) p-value (obs.) p-value (smoothed)
	Fixed-effects (slope)	26.23	14.10	0.002	< 0.001
	Slope (high)	66.56	23.73	0.182	< 0.001
	Slope (med)	36.43	22.14	0.003	< 0.001
	Slope (low)	38.73	26.60	0.143	< 0.001

Table 2 .

 2 p-values: Hypothesis test for differences in shape change ("slope"), between controls and HD groups, for observed caudates (Left) and temporally consistent caudate shapes (right)

⋆ This research was supported by NIH Grants U01 NS082086, NS40068, NS050568 (PREDICT-HD), U54 EB005149 (NA-MIC), S10 RR023392 (NCCR Shared Instrumentation Grant), and NSF CAREER Grant 1054057. Also supported by NIH (NINDS; 5RO1NS040068, 5RO1NS054893) and the CHDI Foundation to Jane S. Paulsen. We thank the PREDICT-HD sites, the study participants, the National Research Roster for HD Patients and Families, the Huntington Disease Society of America and the Huntington Study Group.


Jungyeul Park
email: jungyeul.park@univ-rennes1.fr

Mouna Chebbah
email: mouna.chebbah@univ-rennes1.fr

Siwar Jendoubi
email: jendoubi.siwar@etudiant.univ-rennes1.fr

Arnaud Martin
email: arnaud.martin@univ-rennes1.fr

Second-order Belief Hidden Markov Models

Keywords: Belief functions, Dempster-Shafer theory, first-order belief HMM, second-order belief HMM, probabilistic HMM

Hidden Markov Models (HMMs) are learning methods for pattern recognition. The probabilistic HMMs have been one of the most used techniques based on the Bayesian model. First-order probabilistic HMMs were adapted to the theory of belief functions such that Bayesian probabilities were replaced with mass functions. In this paper, we present a second-order Hidden Markov Model using belief functions. Previous works in belief HMMs have been focused on the first-order HMMs. We extend them to the second-order model.

Introduction

A Hidden Markov Model (HMM) is one of the most important statistical models in machine learning [1]. A HMM is a classifier or labeler that can assign label or class to each unit in a sequence [2]. It has been successfully utilized over several decades in many applications for processing text and speech such as Part-of-Speech (POS) tagging [3], named entity recognition [4] and speech recognition [START_REF]For example[END_REF]. However, such works in the early part of the period are mainly based on first-order HMMs. As a matter of fact, the assumption in the first-order HMM, where the state transition and output observation depend only on one previous state, does not exactly match with the real applications [6]. Therefore, they require a number of sophistications. For example, even though the first-order HMM for POS tagging in early 1990s performs reasonably well, it captures a more limited amount of the contextual information than is available [7]. As consequence, most modern statistical POS taggers use a second-order model [8].

Uncertainty theories can be integrated in statistical models such as HMMs: The probability theory has been used to classify units in a sequence with the Bayesian model. Then, the theory of belief functions is employed to this statistical model because the fusion proposed in this theory simplifies computations of a posteriori distributions of hidden data in Markov models. This theory can provide rules to combine evidences from different sources to reach a certain level of belief [9-13]. Belief HMMs introduced in [14-22], use combination rules proposed in the framework of the theory of belief functions. This paper is an extension of previous ideas for second-order belief HMMs. For the current work, we focus on explaining a second-order model. However, the proposed method can be easily extended to higher-order models. This paper is organized as follows: In Sections 2 and 3, we detail probabilistic HMMs for the problem of POS tagging where HMMs have been widely used. Then, we describe the first-order belief HMM in Section 4. Finally, before concluding, we propose the second-order belief HMM.

2 First-order probabilistic HMMs POS tagging is a task of finding the most probable estimated sequence of n tags given the observation sequence of v words. According to [1], a first-order probabilistic HMM can be characterized as follows:

N

The number of states in a model

S t = {s t 1 , s t 2 , • • • s t N } at the time t. M
The number of distinct observation symbols.

V = {v 1 , v 2 , • • • , v M }. A = {a i j }
The set of N transition probability distributions. B = {b j (o t )} The observation probability distributions in state j. π = {π i }

The initial probability distribution. Figure 1 illustrates the first-order probabilistic HMM allowing to estimate the probability of the sequence s t-1 i and s t j where a i j is the transition probability from s t-1 i to s t j and b j (o t ) is the observation probability on the state s t j . Regarding POS tagging, the number of possible POS tags that are hidden states S t of the HMM is N. The number of words in the lexicons V is M. The transition probability a i j is the probability that the model moves from one tag s t-1 i to another tag s t j . This probability can be estimated using a training data set in supervised learning for the HMM. The probability of a current POS tag appearing in the first-order HMM depends only on the previous tag. In general, first-order probabilistic HMMs should be characterized by three fundamental problems as follows [1]:

-Likelihood: Given a set of transition probability distributions A, an observation sequence O = o 1 , o 2 , • • • , o T and its observation probability distribution B, how do we determine the likelihood P(O|A, B)? The first-order model relies on only one observation where b j (o t ) = P(o j |s t j ) and the transition probability based on one previous tag where a i j = P(s t j |s t-1 i ). Using the forward path probability, the likelihood α t ( j) of a given state s t j can be computed by using the likelihood α t-1 (i) of the previous state s t-1 i as described below:

α t ( j) = ∑ i α t-1 (i)a i j b j (o t ) (1)
-Decoding: Given a set of transition probability distributions A, an observation sequence

O = o 1 , o 2 , • • • , o T
and its observation probability distribution B, how do we discover the best hidden state sequence? The Viterbi algorithm is widely used for calculating the most likely tag sequence for the decoding problem. The Viterbi algorithm can calculate the most probable path δ t ( j) which contains the sequence of ψ t ( j). It can select the path that maximizes the likelihood of the sequence as described below:

δ t ( j) = max δ t-1 (i)a i j b j (o t ) ψ t ( j) = argmax ψ t-1 (i)a i j (2)
-Learning: Given an observation sequence

O = o 1 , o 2 , • • • , o T and a set of states S = {s t 1 , s t 2 , • • • , s t N }
, how do we learn the HMM parameters for A and B? The parameter learning task usually uses the Baum-Welch algorithm which is a special case of the Expectation-Maximization (EM) algorithm.

In this paper, we focus on the likelihood and decoding problems by assuming a supervised learning paradigm where labeled training data are already available.

Second-order probabilistic HMMs

Now, we explain the extension of the first-order model to a trigram 3 in the second-order model. Figure 2 illustrates the second-order probabilistic HMM allowing to estimate the probability of the sequence of three states s t-2 i , s t-1 j and s t k where a i jk is the transition probability from s t-2 i and s t-1 j to s t k , and b k (o t ) is the observation probability on the state s t k . Therefore, the second-order probabilistic HMM is characterized by three fundamental problems as follows:

-Likelihood: The second-order model relies on one observation b k (o t ). Unlike the first-order model, the transition probability is based on two previous tags where a i jk = P(s t k |s t-2 i , s t-1 j ) as described below:

α t (k) = ∑ j α t-1 ( j)a i jk b k (o t ) (3)
However, it will be more difficult to find a sequence of three tags than a sequence of two tags. Any particular sequence of tags s t-2 i , s t-1 j , s t k that occurs in the test set may simply never have occurred in the training set because of data sparsity [2]. Therefore, a method for estimating P(s t k |s t-2 i , s t-1 j ), even if the sequence s t-2 i , s t-1 j , s t k never occurs, is required. The simplest method to solve this problem is to combine the trigram P(s t k |s t-2 i , s t-1 j ), the bigram P(s t k |s t-1 j ), and even the unigram P(s t k ) probabilities [8]:

P(s t k |s t-2 i , s t-1 j ) = λ 1 P(s t k |s t-2 i , s t-1 j ) + λ 2 P(s t k |s t-1 j ) + λ 3 P(s t k ) (4)
Note that P is the maximum likelihood probabilities which are derived from the relative frequencies of the sequence of tags. Values of λ are such that λ 1 +λ 2 +λ 3 = 1 and they can be estimated by the deleted interpolation algorithm [8]. Otherwise, [7] describes a different method for values of λ as below:

λ 1 = k 3 λ 2 = (1 -k 3 ) • k 2 λ 3 = (1 -k 3 ) • (1 -k 2 ) (5)
3 The trigram is the sequence of three elements, i.e. three states in our case.

where

k 2 = log(C(s t-1 j ,s t k )+1)+1 log(C(s t-1 j ,s t k )+1)+2 , k 3 = log(C(s t-2 i ,s t-1 j ,s t k )+1)+1 log(C(s t-2 i ,s t-1 j ,s t k )+1)+2
, and C(s t-2 i , s t-1 j , s t k ) is the frequency of a sequence s t-2 i , s t-1 j , s t k in the training data. Note that λ 1 + λ 2 + λ 3 is not always equal to one in [7]. The likelihood of the observation probability for the second-order model uses B where b k (o t ) = P(o k |s t k , s t-1 j ). -Decoding: For second-order model we require a different Viterbi algorithm. For a given state s at the time t, it would be redefined as follows [7]:

δ t (k) = max δ t-1 ( j)a i jk b k (o t ) where δ t ( j) = max P(s 1 , s 2 , • • • , s t-1 = s i , s t = s j , o 1 , o 2 , • • • , o t ) ψ t (k) = argmax ψ t-1 ( j)a i jk where ψ t (k) = argmax P(s 1 , s 2 , • • • , s t-1 = s i , s t = s j , o 1 , o 2 , • • • , o t ) (6)
-Learning: The problem of learning would be similar to the first-order model except that parameters A and B are different.

With respect to performance measures, different transition probability distributions in [8] and [7] obtain 97.0% and 97.09% tagging accuracy for known words, respectively for the same data (the Penn Treebank corpus). Even though probabilistic HMMs perform reasonably well, belief HMMs can learn better under certain conditions on observations [21].

First-order Belief HMMs

In probabilistic HMMs, A and B are probabilities estimated from the training data. However, A and B in belief HMMs are mass functions (bbas) [17,21].According to previous works on belief HMMs, a first-order HMM using belief functions can be characterized as follows 4 : N The number of states in a model

Ω t = {S t 1 , S t 2 , • • • , S t N }. M
The number of distinct observation symbols V . A = {m Ω t a [S t-1 i ](S t j )} The set of conditional bbas to all possible subsets of states.

B = {m Ω t b [o t ](S t j )}
The set of bbas according to all possible observations O t .

π = {m Ω 1 π (S Ω 1 i )}
The bba defined for the the initial state. Difference between the first-order probabilistic and belief HMMs is presented in Figure 1, the transition and observation probabilities in belief HMMs are described as mass functions. Therefore, we can replace a i j by m Ω t a [S t-1 i ](S t j ) and b j (o t ) by m Ω t b [o t ](S t j ). The set Ω t has been used to denote states for HMMs using belief functions [17, 21]. Note that s t i is the single state for probabilistic HMMs and S t i is the multi-valued state for belief HMMs. First-order belief HMMs should also be characterized by three fundamental problems as follows:

-Likelihood: The likelihood problem in belief HMMs is not solved by likelihood, but by using the combination. The first-order belief model relies on (i) only one observation m Ω t b [o t ](S t j ) and (ii) a transition conditional mass function based on one previous tag m Ω t a [S t-1 i ](S t j ). Mass functions of sets A and B are combined using the Disjunctive Rule of Combination (DRC) for the forward propagation and the Generalized Bayesian Theorem (GBT) for the backward propagation [23]. Using the forward path propagation, the mass function of a given state S t j can be computed as the combination of mass functions on the observation and the transition as described below:

q Ω t α (S t j ) = ∑ m Ω t-1 α (S t-1 i ) • q Ω t a [S t-1 i ](S t j ) • q Ω t b (S t j ) (7)
Note that the mass function of the given state S t j is derived from the commonality function q Ω t α . -Decoding: Several solutions have been proposed to extend the Viterbi algorithm to the theory of belief functions [17,24,25]. Such solutions maximize the plausibility of the state sequence. In fact, the credal Viterbi algorithm starts from the first observation and estimates the commonality distribution of each observation until reaching the last state. For each state S t j , the estimated commonality distribution (q Ω t δ (S t j )) is converted back to a mass function that is conditioned on the previous state. Then, we apply the pignistic transform to make a decision about the current state (ψ t (s t j )):

q Ω t δ (S t j ) = ∑ S t-1 i ⊆A t-1 m Ω t-1 δ (S t-1 i ) • q Ω t a [S t-1 i ](S t j ) • q Ω t b (S t j ) ψ t (s t j ) = argmax S t-1 i ∈Ω t-1 (1 -m Ω t δ [S t-1 i ]( / 0)) • P t [S t-1 i ](S t j ) (8)
where

A t = ∪ S t-1 j ∈Ω t ψ t (S t j ) [17].
-Learning: Instead of the traditional EM algorithm, we can use the E 2 M algorithm for the belief HMM [22].

To build belief functions from what we learned using probabilities in the previous section, we can employ the least commitment principle by using the inverse pignistic transform [26, 27].

Second-order Belief HMMs

Like the first-order belief HMM, N, M, B and π are similarly defined in the second-order HMM. The set A is quite different and is defined as follows:

A = {m Ω t a [S t-2 i , S t-1 j ](S t k )} (9)
where A is the set of conditional bbas to all possible subsets of states based on the two previous states. Second-order belief HMMs should also be characterized by three fundamental problems as follows:

-Likelihood: The second-order belief model relies on one observation m Ω t b [o t ](S t k ) in a state S k at time t and the transition conditional mass function based on two previous states S t-2 i and S t-1 j , defined by m Ω t a [S t-2 i , S t-1 j ](S t k ). Using the forward path propagation, the mass function of a given state S t k can be computed as the disjunctive combination (DRC) of mass functions on the transition m Ω t a [S t-2 i , S t-1 j ](S t k ) and the observation m Ω t b (S t k ) as described below:

q Ω t α (S t k ) = ∑ m Ω t-1 α (S t-1 j ) • q Ω t a [S t-2 i , S t-1 j ](S t k ) • q Ω t b (S t k ) (10)
where q Ω t a [S t-2 i , S t-1 j ](S t k ) is the commonality function derived from the conjunctive combination of mass functions of two previous transitions. The conjunctive combination is used to have the conjunction of observations on previous two states S t-2 i and S t-1 j . The combined mass function m Ω t a [S t-2 i , S t-1 j ](S t k ) of two transitions m

Ω t-1 a [S t-2 i ](S t-1 j ) and m Ω t a [S t-1 j ](S t k
) is defined as follows:

m Ω t a [S t-2 i , S t-1 j ](S t k ) = m Ω t-1 a [S t-2 i ](S t-1 j ) ∪ m Ω t a [S t-1 j ](S t k ) (11)
The conjunctive combination is required to obtain the conjunction of both transitions. Note that the mass function of the given state S t k is derived from the commonality function q Ω t α . We use DRC with commonality functions like in [17]. Note that the observation only on one previous state is taken into account in the firstorder belief HMM, but the conjunction of observations on two previous states is considered in the second-order belief HMM.

-Decoding: We accept our assumption of the first-order belief HMM for the secondorder model. Similarly to the first-order belief HMM, we propose a solution that maximizes the plausibility of the state sequence. The credal Viterbi algorithm estimates the commonality distribution of each observation from the first observation till the final state. For each state S t k , the estimated commonality distribution (q Ω t δ (S t k )) is converted back to a mass function that is conditioned on a mass function of the two previous states. This mass function is the conjunctive combination of mass functions of the two previous states. Then, we apply the pignistic transform to make a decision about the current state (ψ t (s t j )) as before:

q Ω t δ (S t k ) = ∑ S t-1 j ⊆A t-1 m Ω t-1 δ (S t-1 j ) • q Ω t a [S t-2 i , S t-1 j ](S t k ) • q Ω t b (S t k ) ψ t (s t k ) = argmax S t-1 j ∈Ω t-1 (1 -m Ω t δ [S t-1 j ]( / 0)) • P t [S t-2 i , S t-1 j ](S t k ) (12)
-Learning: Like the first-order belief model, we can still use the E 2 M algorithm for the belief HMM [22].

Since the combination of mass functions in the belief HMM is required where the previous observation is already considered in the set of conditional bbas m Ω t a [S t-2 i , S t-1 j ], we do not need to refine the observation probability for the second-order model as in the second-order probabilistic model.

Conclusion and future perspectives

The problem of POS tagging has been considered as one of the most important tasks for natural language processing systems. We described such a problem based on HMMs

s t-1 i s t j b j (o t ) a ij S t-1 i S t j m Ωt b [o t ] m Ωt a [S t-1 i ]
Fig. 1. First-order probabilistic and belief HMMs

s t-2 i s t-1 j s t k b k (o t ) a ij a jk a ijk S t-2 i S t-1 j S t k m Ωt b [o t ] m Ωt a [S t-1 j ] m Ωt-1 a [S t-2 i ] m Ωt a [S t-2 i , S t-1 j ]
Fig. 2. Second-order probabilistic and belief HMMs and tried to apply our idea to the theory of belief functions. We extended previous works on belief HMMs to the second-order model. Using the proposed method, we will be able to easily extend the higher-order model for belief HMMs. Some technical aspects still remain to be considered. Robust implementation for belief HMMs are required where in general we can find over one million observations in the training data to deal with the problem of POS tagging. As described before, the choice of inverse pignistic transforms would be empirically verified. 5 We are planning to implement these technical aspects in near future. The current work is described to rely on a supervised learning paradigm from labeled training data. Actually, the forward-backward algorithm in HMMs can do completely unsupervised learning. However, it is well known that EM performs poorly in unsupervised induction of linguistic structure because it tends to assign relatively equal numbers of tokens to each hidden state [29]. 6 Therefore, the initial conditions can be very important. Since the theory of belief functions can take into consideration of uncertainty and imprecision, especially for the lack of data, we might obtain a better model using belief functions on an unsupervised learning paradigm.

In the model Ω t , S t are focal elements