Odile Piton
email: piton@univ-paris1.fr

Hélène Pignot
email: helene.pignot@univ-paris1.fr

"Mind your p's and q's?": or the peregrinations of an apostrophe in 17 th Century English

If the use of the apostrophe in contemporary English often marks the Saxon genitive, it may also indicate the omission of one or more letters. Some writers (wrongly?) use it to mark the plural in symbols or abbreviations, visualised thanks to the isolation of the morpheme "s". This punctuation mark was imported from the Continent in the 16 th century. During the 19 th century its use was standardised. However the rules of its usage still seem problematic to many, including literate speakers of English. "All too often, the apostrophe is misplaced", or "errant apostrophes are springing up everywhere" is a complaint that Internet users frequently come across when visiting grammar websites. Many of them detail its various uses and misuses, and attempt to correct the most common mistakes about it, especially its misuse in the plural, called greengrocers' apostrophes and humorously misspelled "greengrocers apostrophe's". While studying English travel accounts published in the seventeenth century, we noticed that the different uses of this symbol may accompany various models of metaplasms. We were able to highlight the linguistic variations of some lexemes, and trace the origin of modern grammar rules governing its usage.

Introduction

After 450 years of existence, the apostrophe is under attack in the English-speaking world. This epiphenomenon not only reflects the evolution of language, but also that of today's society with its heavy reliance on sophisticated technology.

Inconsistent usage of the apostrophe may indeed cause problems. The possessive apostrophe appears in addresses and on road signs, which must concord with the addresses stored in the GPS databases. The emergency services, firemen or ambulance drivers who need to find an address on GPS can no longer waste precious time wondering whether there is an apostrophe in the address of the person they are trying to rescue! As a result, in 2001 its use in public addresses was banned in Australia and in some English cities such as Birmingham where, as of 2009, St. Paul's Square is to be spelled St. Pauls Square, to the utter dismay of purists or English language pedants. 1 The apostrophe was imported to Great Britain from the continent in the 16 th century. But it was not until the 19 th century that its use was standardised, according to David [START_REF] Crystal | [END_REF], a distinguished linguist and the author of many books on the English language.

In the United Kingdom there is no such institution as an Academy in the French style. Therefore no strict "rules" were established regarding this matter, and they have evolved over time. 2 Our study of a corpus of English travel accounts in the Ottoman Empire has revealed various uses of the apostrophe in the 17 th century. 1 See the following articles inter alia "Birmingham City Council bans apostrophes from road signs" (Birmingham Post, by Paul Dale Jan. 29, 2009); "Apostrophe catastrophe for city's street signs" (The Independent [UK], Jan. 30,2009); "City drops apostrophes from signs" (BBC, Jan. 29, 2009). 2 The guidelines given by [START_REF] Gilbaldi | MLA Handbook for Writers of Research Papers[END_REF] pp. 90-91 are very clear and consistent. The possessive of singular proper nouns in US English is formed by adding an apostrophe, even if the noun ends in "s", as in Descartes's or Dickens's. To form the plural possessive, you only need to add an apostrophe. But US usage differs from English usage, some proper nouns such as Descartes, Socrates and Jesus only take an apostrophe and no s in British English. Michael Swan (1992, 505) says apostrophes may be used in the plurals of letters and numbers as in "he writes b's instead of d's" and in "it was in the early 1960's"; in contracted words ("'flu" (influenza); or in dates '79 (=1979). Gilbaldi only accepts the form "1960s".

The frequency of its use varies according to the authors and according to the dates when the texts were written. But although our texts were all written in the 17 th century, we found that usage was quite coherent, as we shall see in the study presented below.

A Brief Historical Outline

In writing this brief historical outline, we are indebted to Jacques André's excellent article published in the review Graphê (2008), "Funeste destinée : l'apostrophe détournée" and to Lucien Febvre and Henry-Jean Martin's book, L'Apparition du Livre (1958).

Illustration 1: Aldus Manutius, the inventor of italic type

From Italy to Great Britain

If the invention of movable metal printing type dates from the mid-15 th century and printing quickly spread throughout Europe during the 15 th century, it was not until the 16 th century that the apostrophe appeared in printing type. This character, used in Greek but absent from classical Latin except in poetry, first appeared in 1501 when Aldus Manutius (Illustration 1) printed Le cose volgari di messer Francesco Petrarcha, the first book in Italian of his collection of libri portatiles, pocket-books of classical writers that he had started with an edition of Virgil published in italics. In Italian the apostrophe marked the elision of a letter. In this book (illustration 4), he presents a somewhat paradoxical theory: the forms of all Roman capital letters derive from the proportions of the human body that he considers as an archetype of beauty.3 He also proposes a reform of spelling, recommending the use of accents (at the beginning of the 16 th century it was difficult to grasp the pronunciation of French as there were no accents), the cedilla and the apostrophe. In the tiers livre of Champ fleury, he remarks that Latin authors use a "point crochu quon appelle apostrophus" (a hooked dot that is called the apostrophe) to mark contraction (André 2008, 4). 4He applied his principles in two books Adolescence clémentine and Briesve doctrine pour deuement escripre selon la propriété du langaige François that he printed in 1533.

In 1529 the physician and grammarian Jacques Dubois published Très utile et compendieux traicté de l'art et science dorthographie Gallicane. In his grammar Isagωge (Initiation) he recommends the use of the Greek apostrophe to signal the omission of a letter. In the meantime, the apostrophe appeared in other books, its use became widespread, and its inclusion in French words obligatory: le ami being henceforth spelled l'ami.

Illustration 5: Apostrophes in a 16 th century French Text

If the apostrophe in French is used to mark elision, its usage will sometimes be misinterpreted by grammarians in a posteriori explanations, as in the case of the adjective grand' (tall) "[the] adjective grand was originally an adjective of one termination (grandem in Latin giving in French to one form for both masc. and fem.) When later grand by analogy with other adjectives, assumed the feminine e, the grammarians thought they saw in the absence of the e in the older form a mark of elision, which they indicated by an apostrophe, hence such forms as: grand' mère, grand ' route, grand' messe, grand' peur, grand' peine, grand' chose,…" (Crane 1907, 269).

Great Britain: The apostrophe appears in the first original English cosmography of the 16 th century, The Cosmographical Glasse written by the physician and cartographer William Cunningham and published in 1559.

Illustration 6: Frontispiece of The Cosmographical Glasse

Illustration 7 shows a common typographical abbreviation ( for on) and the final e in the definite article "the" in "the earth" is elided. But generally speaking how is the apostrophe defined in the 17 th century?

Illustration 7: Excerpt from The Cosmographical Glasse

A Dictionarie of the French and English Tongves, compiled by Randle Cotgrave in 1611, the first French-English bilingual dictionary, includes the following entry: "To apostrophise is to cut off the last vowel of a word" (cf. Illustration 8). Actually we shall see that not only vowels could be "cut off" or elided, but the apostrophe could have another function that will be examined in part two of this essay. Here are the codes that can be found on the Internet: 39 (not used by Anglo-Saxons); 169; Unicode U 2018 or U 2019. Codes 2018 and 2019 cannot be both typed with the keyboard when we use NooJ. So in some texts one might lose a few results when one searches a text using one specific code, whereas different codes might be employed in the text. Maybe that is why search engines remove or ignore punctuation marks when they process your request.

Nevertheless, as we shall see below, it is possible to create efficient NooJ tools (in the form of graphs or dictionaries) to process 17 th century texts.

Uses and functions of the apostrophe

Our corpus includes a selection of English travel accounts in Greece and Anatolia in the 17 th century. For accredited researchers these texts are available for download from the EEBO (Early English Books Online) database. They have been scanned as images and saved in pdf format. Therefore it was necessary to type them before they could be computed by NooJ.

The authors we have elected to study are (in chronological order) George Sandys, Henry Blount, John Ray, Paul Rycaut, Thomas Smith and George Wheler. Their narratives, which were "best-sellers" in their day, provide us with an interesting sample of 17 th century English travel literature.

How do apostrophes feature in our corpus? We will start by spotting the occurrences of apostrophes in our texts. We shall see that they had specific uses and functions that sometimes differ from modern usage. Then we will analyse and transcribe them thanks to the morphological and syntactical graphs we have created with NooJ. In the meantime, we will be discussing our methodology and the technical problems we are still confronted with.

As in contemporary English, the apostrophe may signal an abbreviation in conjunctions and prepositions or the elision of a letter in nouns, adverbs 5 and verbs, but it is much more frequently used.

Conjunctions and Prepositions

Conjunctions and prepositions are often abbreviated. One or more letters may be removed at the beginning (apheresis) or at the end (apocope) of a word as in the following examples: tho' for though, ("tho' dismist the seraglio"); thro' for through ("thrusting an iron stake thro' the body out under the neck"). The grammarian Miège (1688) also mentions the following aphereses: 'bove for above, 'midst for amidst and 'twixt for betwixt (110).

Nouns

The apostrophe begins to be used as the marker of the Saxon genitive (as in "the Grand Signior's women"). It is important to remark that the genitive was previously formed without using an apostrophe and was still very common in 17 th century texts. The following examples are noteworthy:

"from the womens apartment"; "out of their wives and childrens mouths".

The apostrophe was also used to form the interlingual plural of foreign nouns in words ending in a vowel:6 -Egoumeno's, capricio's -Bassa's (Pashas), -piazza's These lemmas can be spotted thanks to a NooJ grammar, and thanks to the graph below: -anothers: "one anothers company" -childrens: "their wives and childrens mouths" Therefore we created a morphological graph -graph 2-to allow for the recognition of these forms:

Graph 2: identifying the Saxon genitive It so happens that the form "wives" can also be a genitive. In this case, the conjunction "and" will help us to recognise it thanks to the syntactical graph that transcribes it. Graph 3 processes the Saxon genitive of words identified by graph 2, and it may extend transcription to a word linked by a conjunction and to a word recognised by graph 2. Let's take the example of "mans" in the following sentence: "First, that no other mans errors could draw either hatred, or engagement upon me". "Mans" is not identified as a genitive since it is wrongly recognised as the transitive verb "to man". There is a solution to this problem, by including this entry (to man) in our dictionary, as the list of uses of the verb to man is rather short (to man a ship; a fort; the guns).

Verbs

The apostrophe is used in the contracted forms of verbs as in contemporary English. For the verb to be, 'tis (no longer in use in CE) is contracted into "it is" or it's. To recognise it with NooJ we need to annotate the word form as a sequence of annotations:

'tis <it,PRO+3+s> <is,be,V+PR+3+s> Miège (see annex, illustration 9) mentions other abbreviations after the same model such as 'twere, 'twill, 'twould, 'twas, ben't, 'ent and several other abbreviations for I will, I would and I had.

The "ed" flexion:

The "e" in the "ed" flexion can be elided in the preterit and past participle of all verbs, hence the mute "e" is turned into an apostrophe and omitted as in "belov'd". The final d is also spelt "t" to mirror the pronunciation of the word. The following quotation provides good examples.

Let ravisht poets drink thrice three, Of whom the uneven muses be Belov'd. The grace misdoubting jarres, Linkt to her naked sisters, barres Draughts that exceed that number. Horat. 1.3 od 19. Whence we notice that the apostrophe also indicates the elision of "e" in the preterit and present perfect of verbs ending in p, k, x, ss, sh, which means that these verbs have four forms, one in ed and shortened forms in 'd, 't or t. For regular forms and for shortened forms in t or d, we use a morphological graph and a syntactical graph applied consecutively. Different cases crop up. Known words and unknown words require different transformations.

The following morphological graph (4) may recognise an unknown part of a verb by adding ed, ted or sed: Graph 4: recognising elided forms of verbs Then the following syntactical graph is applied:

Graph 5: transcribing elided forms of verbs Thus a verb like establish can have 4 forms: "and establish'd the same number", "the establish't doctrine", "and for ever established the adoration". "establisht"

The dictionary first recognises establish as the bare infinitive or the simple present of the verb to establish. So the syntactical graph must modify the result of the dictionary. Then the syntactical graph builds the form "established".

What about verbs which are not recognised or wrongly recognised? Let's examine different cases. These three cases have been selected because they correspond to three different situations: 1. An unknown token (judg); 2. A token (profes) wrongly identified as a noun when performing a basic transformation, i.e. eliding a mute e.; 3. An unrecognized token (imbrac) requiring a morphological transformation.

Unknown token judg:

The form "judg" in "this being judg'd" is not recognised. So the morphological graph tests some hypotheses:

"judg" + ed judged = the PP of judge At that point we don't know whether judg is followed by 'd in the text. Graph 5 will confirm it and we get the following result: judg,judge,V+Tense=PP+ EN=judge

Wrong identification of tokens: Some tokens may be falsely recognised as nouns as in the following example: "Though the Christian religion be profes'd in the Ottoman dominions".

The token "profes" is unknown. A first graph makes a simple change that consists in deleting a mute e in profes and suggests it is the plural of the noun prof (as the NooJ dictionary includes this entry):

profes,prof,N+Nb=p+Distribution=Hum Then another graph, graph 4, adds /sed/ and suggests "professed" (the full graph also "recognises" a preterit and an adjective):

profes,profess,PV+Tense=PP+EN=profess Then graph 5 invalidates the noun, and validates the verb: profes,profess,V+Tense=PP+EN=profess

Case of imbrac'd or imbrac't:

To be able to recognise imbrac'd NooJ needs to combine two transformations:

imbrac'd embrac'd embraced.

The last change is made by graph 5, but the first one needs to explore the ninety transformation graphs that we have drawn, to be able to recognise this form. All the graphs will produce several answers from which the correct one must be chosen. This means our results need to be validated and the correct answer chosen.

Hierarchy of graphs:

Several morphological graphs with different levels of priority may be applied to unknown tokens. The hierarchical organisation of our graphs means that once a solution has been found, the other graphs with less priority will not be applied. The option that con-sists in applying all the graphs at the same time has the undesirable effect of producing myriads of wrong answers. Getting the priorities right when using syntactical graphs is a difficult problem that we have not sorted out yet.

Apostrophes in our corpus: charts

Our corpus has 91 occurrences of 'd or 't. There are no apostrophes in the earliest text, but the excerpt is very short. We cannot infer from our corpus general conclusions about the frequency of its usage, according to chronology or date of publication. Usage depends on the author's style. In other 17 th century texts such as Milton's pamphlets (published in the 1640s) or Mary Astell's essays (published in the 1690s), usage of the apostrophe is widespread, and usually marks contractions in verbs, the elision of many unpronounced letters (vowels or consonants) or mute e's but also the plural of certain nouns.

Author

Conclusion

In natural language processing, transformations involving multiple tokens create more difficulties than those who are merely the transformation of one token (such as the introduction of a mute e or doubling of a letter). The problem to address here is technically very different if the modernisation of the text requires adding an apostrophe, or deleting it. Processing it involves two steps, which makes it more difficult. Processing 't or 'd means dealing with a verb or an adjective sometimes, whereas 's may appear only in a noun. If it is an interlingual plural, we just delete the apostrophe and concatenate the s.

In cases where one must insert 's -i.e. in nouns-a problem occurs when recognising the word, if the latter can be a noun or a verb. How can we recognise the genitive? We need to insert the apostrophe: mans man's. In the case of prepositions, pronouns and conjunctions which are after all few in number, we can process them simply by adding them to our dictionary when they are not ambiguous.

The introduction of the apostrophe into a verb splits it into two tokens, and alas the fact that the apostrophe is a delimiter makes our work very complicated. But this is strictly a computer problem that automatic processing does not allow us to solve immediately. The beginning of the truncated word will be falsely recognized, and that will produce an erroneous annotation, which must be removed afterwards, or it will be labelled UNKNOWN. Then the application of syntactic grammars will allow for the identification and removal of the apostrophe, provided that the verb is in the NooJ dictionary (we may complete it if necessary). Thus two NooJ tools are used here: some forms are recognised by simply inserting the short forms in the dictionary, while for nouns and verbs the use of morphological and syntactic graphs is necessary.

The morphological and syntactical graphs we have drawn may process all of the occurrences of the apostrophe in our corpus, with very little noise. Usage of the apostrophe seemed simpler in 17 th century English. The possessive genitive in 's was not very common yet. The apostrophe mostly marks the omission of letters in a wide range of words and the plural of certain words.

French students often find 17 th century English texts difficult to read and understand. We hope our tools (especially the dictionaries) might make these texts more accessible to students of English as a second language.

Illustration 2 :

 2 Apostrophes in an Italian text France: The sixteenth century saw a reform of printing in France. Printed characters were different from handwritten letters, and writing and punctuation rules were gradually set out. The printers were humanist scholars; among them Geofroy Tory, a painter, engraver and master printer of the French King François I, inspired by Italian models, published Champ fleury (1529) -illustration 3-a groundbreaking treatise on typography and orthography. Illustration 3: G. Tory's Champ fleury Illustration 4: G. Tory's way of forming the letters I, K & Z

Graph 1 :

 1 identifying the interlingual plural Unknown tokens: But a problem occurs for unknown words ending in s, as in the following examples:

  Graph 3: transcribing the Saxon genitive In a nutshell, this graph can recognise: -either noun + noun : <N+gen_sax> <N> -or pronoun + noun: <PRO+gen_sax> <N> -wives and childrens mouths < wives's 7 and children's mouths> -anothers company <another's company>. But we cannot automatise other cases. Case of "mans": So much for unknown words, but what about known words? Can they be recognised and correctly interpreted?

2 General Remarks about its present use Comparison between European languages

  To conclude this brief historical outline, we ought to mention a difficulty which brings us back to technological issues. A problem occurs when apostrophes are processed by computers. The apostrophe looks very much like the single quotation mark, and it is typed with the same key. Different computer encoding systems have different encodings for the apostrophe.

	Language French Italian English German Spanish
	Number of	10 000 6 000	500	Some	Some
	apostrophes
	Number of	9 000 9 000	9 000	9 000	9 000
	sentences
	Table 1: apostrophes in European languages,
		a comparative chart
	Encoding:

Illustration 8: Definition of Apostropher in Cotgrave's Dictionary of the French and English Tongves (1611) 2.: If we compare the uses of the apostrophe and their occurrences in European languages today, André

(2008)

says that whatever big corpuses in different European languages we use -for instance sacred or lay texts such as the Gospels or the project of the European Constitution-we always get similar results, and in the following proportions:

Year Size of corpus Different words

					Number
					of '
	Blount	1636	1408	621	0
	Sandys 1652	3910	1419	15
	Rycaut	1679	12920	2270	11
	Smith	1682	22640	4285	113
	Wheler 1682	2365	747	4
	Ray	1693	1140	533	15
	Total		44383		158

Table 2 :

 2 Global information about our corpus

	Author Number of 's genitive plural
	Sandys	3	3	0
	Rycaut	8	8	0
	Smith	40	27	13
	Wheler	2	1	1
	Ray	1	0	1
	Total	54	39	15

Table 3 :

 3 Occurrences of 's

	Author	Number of 'd	Other '
	Sandys	11 (in poems)	1 th' (poem)
	Rycaut	3	0
	Smith	63 + 1 't	4 tho' 1 thro' 4 'tis
	Wheler	2	0
	Ray	11	1 tho' 2 'tis
	Total	91	13

Table 4 :

 4 Occurrences of 'd and other cases

As De[START_REF] Vinne | Historic Printing Types, A Lecture Read before The Grolier Club of New-York[END_REF] explains "he traced the derivation of all forms of the alphabetical letters to the two letters which make the name of the mythological goddess IO. From this straight line and circle came all the letters. He made the human figure fit into a geometrical diagram on which he planned the shapes of letters" (34).

« Ie dis et allegue ces choses icy afin que sil avenoit quon deust escripre en lettre attique telz metres ou le S se debvroit evanoyr, on les porroit escripre honnestement et scientement sans y mettre ladicte lettre…, et escripre ung point crochu au-dessus du lieu ou elle debvroit estre » ("I'm saying and asserting these things so that, if it so happened that one needed to write in Attic letters some verse where the S should be elided, one could omit the aforesaid letter and instead -according to correct and scholarly usage-write a hooked dot above the place where it should have appeared", G. Tory, Champ fleury(Paris, 1529)

fol. 56 v°. As the reader can see, Tory himself does not use the apostrophe much in this text, but mentions its use in Latin.

Ever and even may be spelled e'er and ev'n; we haven't found any instances of these forms in our corpus.

According to Miège 's was also used to form the plural of English words ending in y, hence the plural of heresy might be heresy's or heresies. We have not found any instance of this in our corpus.

To be able to automatise the transformation by adding 's, we need to use this spelling (wives's instead of wives') which prescriptive grammarians consider incorrect.

ANNEX

Illustration 9: A list of contractions (Miège 1688, 110-11)


Muriel Visani
email: muriel.visani@rd.francetelecom.com

Christophe Garcia
email: christophe.garcia@rd.francetelecom.com

Jean-Michel Jolion
email: jean-michel.jolion@insa-lyon.fr

TWO-DIMENSIONAL-ORIENTED LINEAR DISCRIMINANT ANALYSIS FOR FACE RECOGNITION

Keywords: Two-Dimensional-Oriented Linear Discriminant Analysis, Face Recognition, Feature Extraction, Statistical projection, Two-Dimensional Principal Component Analysis

In this paper, a new statistical projection-based method called Two-Dimensional-Oriented Linear Discriminant Analysis (2DO-LDA) is presented. While in the Fisherfaces method the 2D image matrices are first transformed into 1D vectors by merging their rows of pixels, 2DO-LDA is directly applied on matrices, as 2D-PCA. Within and between-class image covariance matrices are generalized, and 2DO-LDA aims at finding a projection space jointly maximizing the second and minimizing the first by considering a generalized Fisher criterion defined on image matrices. A series of experiments was performed on various face image databases in order to evaluate and compare the effectiveness and robustness of 2DO-LDA to 2D-PCA and the Fisherfaces method. The experimental results indicate that 2DO-LDA is more efficient than both 2D-PCA and LDA when dealing with variations in lighting conditions, facial expression and head pose.

Introduction

Since the seminal work of Sirovich and Kirby [START_REF] Sirovitch | A Low-Dimensional Procedure for the Characterization of Human Faces[END_REF], which showed that Principal Component Analysis (PCA) could be efficiently used for representing images of human faces, statistical projection-based methods have been widely used in the context of automatic face recognition. Turk and Pentland [START_REF] Turk | Face recognition using eigenfaces[END_REF] proposed the very well-known Eigenfaces method, based on PCA, where a face image can be represented as a weighted sum of a collection of images (eigenfaces) that define a facial basis. Belhumeur et al. [START_REF] Belhumeur | Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection, Special Theme Issue on Face and Gesture Recognition[END_REF] introduced the Fisherfaces method, based on Linear Discriminant Analysis (LDA) where class information, i.e. the identity of each face image, is taken into account for enhancing separation between different classes, while building the face space.

In PCA-based and LDA-based face recognition methods, the h × w 2D face images must be first transformed into 1D image vectors of size h • w, which leads to high-dimensional image vector space, where statistical analysis, i.e. covariance matrix calculation and eigen system resolution, is costly, difficult and may be unstable. To overcome these drawbacks, Yang et al. [START_REF] Yang | Two-Dimensional PCA: A New Approach to Appearance-Based Face Representation and Recognition[END_REF] proposed recently the Two Dimensional PCA (2D-PCA) method that aims at performing PCA using directly the face image matrices, keeping the 2D structure of the face images. They have shown on various databases that 2D-PCA is more efficient than PCA for the task of face recognition. In addition, we have shown [START_REF] Visani | Comparing Robustness of Two-Dimensional PCA and Eigenfaces for Face Recognition[END_REF] on FERET [START_REF] Phillips | The FERET Database and Evaluation Procedure for Face Recognition Algorithms[END_REF] that 2D-PCA is more robust than PCA when dealing with face segmentation inaccuracies such as misaligned or badly scaled face images, with low-quality images and partial face occlusions.

In this paper, we propose a novel class-based projection technique, called Two-dimensional-Oriented Linear Discriminant Analysis, that achieves better recognition results than traditional LDA-based approaches by taking advantages of the 2D matrix representation of the face images while substantially reducing computational and storage costs.

The remainder of the paper is organized as follows. In section 2, we describe in details the principle and the algorithm of the proposed 2DO-LDA method, pointing out its advantages over previous projection-based methods. In section 3, a series of four experiments, on different international data sets, is presented to demonstrate the effectiveness and robustness of 2DO-LDA, with respect to variations in lighting conditions, facial expression and head pose and compare its performances with respect to the LDA and 2D-PCA methods. Finally, conclusions are drawn in section 4.

2D-Oriented Linear Discriminant Analysis

The classifier is constructed from a training set of n face image matrices X i , containing h × w pixels, labeled by their corresponding identity. The views of one person form a class. The aim is to find a projection matrix P , of size w ×k, providing efficient separation of the projected classes according to:

Xi = X i • P (1)
where Xi is the h × k projected matrix of X i onto the orthonormal basis P of the projection space. Column vectors (P i ) i=1...k of P will be referred to as 2D-Oriented Discriminant Components (2DO-DCs) in the following.

The 2DO-DCs are chosen to jointly maximize the mean variation between classes and minimize the mean of the variations inside each class. Therefore, P can be chosen as the w × k matrix maximizing the following generalized Fisher criterion:

J(P ) = ( Ŝw ) -1 Ŝb (2)
where Ŝw and Ŝb are respectively the generalized within-class and betweenclass covariance matrix of the n projected image matrices Xi , defined as:

Ŝw = 1 n C c=1 X i ∈Ωc ( Xi -Xc ) T ( Xi -Xc ) and Ŝb = C c=1 n c n ( Xc -X) T ( Xc -X) (3)
where Xc is the mean matrix of the n c projected images of class Ω c (among C different classes) and X is the mean matrix of all the n projected images of the training set. According to equations ( 1) and (3), criterion (2) is equivalent to the following criterion:

J(P ) = |P T S b P | |P T S w P | (4)
where S w and S b are respectively called the generalized within-class and betweenclass covariance matrix of the training set:

S w = 1 n C c=1 X i ∈Ωc (X i -Xc ) T (X i -Xc ) and S b = C c=1 n c n ( Xc -X) T ( Xc -X) (5)
where Xc and X are respectively the mean of the n c images of class Ω c and the mean of all the n images of the training set. Under the assumption that S w is non-singular, the k vectors P i maximizing criterion (4) are the k orthonormal eigenvectors of matrix S -1 w S b corresponding to the largest eigenvalues. The matrix S w is generally invertible due to the low dimension of the 2DO-DCs relative to the number of training samples (n ≫ w).

Once they have been sorted in descending order from their corresponding eigenvalues, the number k of 2DO-DCs to consider can be determined as for the eigenfaces method [START_REF] Yambor | Analyzing PCA-based Face Recognition Algorithms: Eigenvector Selection and Distance Measures[END_REF], traditionally by removing a given percentage of the last eigenvectors.

As a statistical projection method, 2DO-LDA can be used for image compression, even if the projection space is chosen to be more discriminative than representative. The projected image Xi and P can be combined to obtain a reconstruction of the original image X i ; some results are shown in Figure 1.

Classification of face images is performed in the projection space defined by P : when comparing two faces X a and X b , they are first projected onto P according to equation (1), giving their projections Xa and Xb . Then, a matrixto-matrix distance is calculated between Xa and Xb , for instance the following distance, used by Yang. et al. [START_REF] Yang | Two-Dimensional PCA: A New Approach to Appearance-Based Face Representation and Recognition[END_REF]:

d( Xa , Xb ) = k j=1 Xj a -Xj b 2 (6)
where Xj i = X i P j is the projected vector of image X i on the the j th 2DO-DC P j , and • 2 is the standard L 2 norm.

It can be pointed out that 2DO-LDA offers strong advantages in comparison with 2D-PCA and the usual LDA method:

In 2D-PCA the projection space is chosen to retain most of the total scatter of the training set, no matter if that scatter is explained by variations inside the same class (variations in facial expression for instance) or between two different classes. Thus, the projection space constructed from 2D-PCA can represent noise and this method is more suited for face representation than for face classification. It will be shown in section 3 that 2DO-LDA have a stronger discriminative power than 2D-PCA; 2DO-LDA is numerically more stable than the usual LDA method: for the LDA method the sample images are vectors of length w • h, and this large dimension leads to numerical instability when computing the within and between-class covariance matrices, from these vectors; 2DO-LDA allows an important storage gain with respect to the usual LDA method: while for the LDA method the length of the projection vectors P i is w • h, for 2D-PCA their length is w. Moreover, the number k of selected projection vectors for LDA is traditionally 60% of the number of samples of the training set. We will see in section 3 that the number of 2DO-DCs needed to provide good face recognition rates is much smaller; Concerning LDA, the length of the projection vectors w • h is usually much larger than the number of samples n. Therefore, the within-class covariance matrix of the training set is generally non-invertible. The trick traditionally used is to perform LDA into a subspace previously constructed from PCA [START_REF] Swets | Using Discriminant Eigenfeatures for Image Retrieval[END_REF]. The corresponding algorithm will be denoted by "PCA+LDA" in the following. Applying first PCA generates an additive computational cost and leads to a loss of information that could, if kept, be discriminative. Concerning 2DO-LDA, the S w matrix is generally invertible and therefore the algorithm can be applied directly on the training set.

Experimental Results

Four experiments are performed to assess the effectiveness and robustness of 2DO-LDA with respect to variations in lighting conditions, facial expression and head pose and compare its performance with LDA and 2D-PCA.

Three face databases are used: the Asian Face Image Database PF01 [START_REF] Hwang | Performance Evaluation of Face Recognition Algorithms on Asian Face Database[END_REF], containing 17 views of each of 107 persons, the well-known FERET [START_REF] Phillips | The FERET Database and Evaluation Procedure for Face Recognition Algorithms[END_REF] face database, and the BioId Database [START_REF] Jesorsky | Robust Face Detection Using the Hausdorff Distance[END_REF], containing 1521 face images of 23 people, extracted from video sequences.

A face image preprocessing step is first applied to each image: it consists in centering the face in the image, setting the image to a size of 65 pixels wide by 75 pixels high, and equalizing its histogram.

The first two experiments provide a comparison of the robustness to variations in head pose and facial expression, the third experiment aims at evaluating the efficiency in the presence of illumination variations. The last experiment consists in matching video sequences of faces with different lighting conditions, head poses and facial expressions. Figure 2 shows samples of the training and test sets used for these experiments.

Experimental results are analyzed through two graphics: the compared recognition rates of 2D-PCA and 2DO-LDA across a varying number of projection vectors k (first column of Figure 3) and the compared Cumulative Match Characteristic (CMC) curves for LDA, 2D-PCA and 2DO-LDA (second column of Figure 3). A face is said to be recognized at rank j if an image of the same person is among the j th nearest into the projection space. The distance ( 6) is used for 2D-PCA and 2DO-LDA. Concerning LDA a L 2 distance is performed in the projection space. In each CMC curve, the number k of projection vectors has been chosen so as to maximize the performances of the algorithm.

The first experiment (see Figure 2 and test sets present similar lighting conditions, and neutral facial expressions. The test set is compared to the training set. Figure 3.a shows that, for any number k of projection vectors varying from 1 to 15, 2DO-LDA provides better recognition rates than 2D-PCA. The projection vectors of both methods have the same length (here w = 65). The best recognition rate for 2DO-LDA (94,4%) is obtained with k = 8 projection vectors, and is 2,1% superior to the best recognition rate for 2D-PCA, obtained with k = 9. The PCA+LDA algorithm is computed from a sufficient number of 200 principal components. The best results for LDA are obtained with k = 40 projection vectors of length 75•65 = 4875 pixels. Figure 3.b shows that 2DO-LDA gives better results than both 2D-PCA and LDA methods, at the first rank as well as at higher ranks. Therefore, 2DO-LDA appears to be the most robust to head pose changes.

The second experiment (see Figure 2.b) is performed on a subspace of the Asian Face Image Database PF01, with similar lighting conditions and frontal head poses. The training set contains 321 images, i.e. three views per person. One corresponds to a neutral expression; the two others are chosen randomly among the four expressions available in the database: happy, surprised, irritated and closed eyes. The test set contains the two remaining facial expressions, for each person. The test set is compared to the training set. From Figure 3.c we can see that 2DO-LDA gives better results than 2D-PCA with less projection vectors (up to 19,7% of difference with k = 6). Figure 3.d shows that 2DO-LDA gives much better recognition rates than both 2D-PCA and LDA methods for a rank varying from 1 to 10 (the mean improvement on the 7 first ranks compared to LDA is about 12%). We have observed that about 68% of the misclassifications of 2D-PCA correspond to matching different persons with the same facial expression, while this kind of errors is involved in only 52% of the fewer misclassifications of 2DO-LDA. Therefore, the efficiency of 2DO-LDA is explained by a better ability to deal with facial expression changes. Indeed, these variations constitute most of the within-class scatter of the training set, which is minimized by 2DO-LDA when applying the criterion 4, while 2D-PCA maximizes the total scatter (containing the within-class scatter).

The third experiment (see Figure 2.c) is performed on the FERET database. The training set contains 666 images of 152 persons. The number of images per person is variable, but always larger than three. For each person, the multiple views are taken on different days, under different lighting conditions. The time interval between two views of the same person can be long (from a few days to almost three years), thus one person can wear eyeglasses or a beard on a photo and not on another one (see first row of Figure 2.d). There are two test sets. The first one contains one image per person, taken from the training set. Test set #2 also contains one image per person, taken another day and not belonging to the training set. Lighting conditions are very different and time delay may be long from one test set to another. All the images used for this experiment contain near-frontal head pose; the facial expression can either be neutral or smiling. Test set #2 is then compared to test set #1. Figure 3.e shows that for both 2DO-LDA and 2D-PCA the recognition rates are low (inferior to 50%), which can be explained by the important dissimilarities between the two test sets. However, 2DO-LDA achieves better recognition rates than 2D-PCA (the best recognition rate for 2DO-LDA is achieved with only 5 2DO-DCs against 13 projection vectors for 2D-PCA, and is 5,3% better). The PCA+LDA algorithm is computed from 500 principal components. From Figure 3.f we can conclude that 2DO-LDA provides better results than 2D-PCA and LDA at the first rank as well as at higher ranks. The storage gain compared to LDA is important given that the best recognition rates for LDA are achieved with 100 projection vectors of length 4875 pixels against only 5 projection vectors of length 65 pixels for 2DO-LDA. Moreover, 2DO-LDA reaches 5,5% mean recognition rate improvement over LDA at the first five ranks.

The last experiment (see Figure 2.d) is performed on both the FERET and BioId databases. The training set and test set #1 of the previous experiment constitute the training set, that contains consequently 818 images from 152 persons. Two test sets are taken from the BioId database. Each one contains 173 images of 18 persons, taken from different video sequences. There are important variations in lighting conditions, facial expression and head pose, within and between the test sets. First, test set #2 is compared on an image-to-image basis to test set #1, and a recognition rate is obtained, as for previous experiments. Given that the two sets contain very different illumination conditions and head poses, the recognition rates are inferior to 65% for both 2DO-LDA and 2D-PCA techniques (see Figure 3.g). However, 2DO-LDA achieves much better recognition rates than 2D-PCA, with 15% difference between their respective maxima. The PCA+LDA algorithm is performed from 600 principal components. From Figure 3.h we can conclude that 2DO-LDA provides better recognition rates than 2D-PCA and LDA at the first rank as well as at higher ranks. The storage gain compared to LDA is very important: for LDA the best recognition rate is achieved with 550 projection vectors of length 4875 pixels against only 5 2DO-DCs of length 65 pixels for 2DO-LDA. Moreover, 2DO-LDA reaches 17.6% mean recognition rate improvement over LDA at the first five ranks. The test sets are then compared on a sequence-to-sequence basis, applying a majority voting scheme to the comparion results obtained previously. 2DO-LDA recognizes 11 sequences from 18, while 2D-PCA recognizes at most 8 sequences.

Conclusion

In this paper, we have proposed a new class-based projection method, called 2DO-LDA, that can be successfully applied to face recognition. This technique, by maximizing a generalized Fisher criterion computed directly from matrices of face images, constructs a discriminant projection matrix.

2DO-LDA is numerically more stable and allows an important storage gain in comparison with the usual LDA method. It has already been shown [START_REF] Yang | Two-Dimensional PCA: A New Approach to Appearance-Based Face Representation and Recognition[END_REF][START_REF] Visani | Comparing Robustness of Two-Dimensional PCA and Eigenfaces for Face Recognition[END_REF] that 2D-PCA outperforms the traditional PCA method. In this paper, we have shown on various databases that 2DO-LDA is more efficient and robust to variations in lighting conditions, facial expression and head pose than both 2D-PCA and LDA.

Figure 1 .

 1 Figure 1. (a) Original images (Asian Face Database PF01). (b) Corresponding reconstructed images with k = 2 2DO-DCs. (c) With k = 3. (d) With k = 20. The projection space is constructed from the training set of the first experiment (see section 3). With the third 2DO-DC the facial features (eye, nose, mouth) appear, but the head poses are not distinguishable yet. With more 2DO-DCs a good visual quality of reconstruction is obtained.

Figure 2 .

 2 Figure 2. Images used for experiments. (a) First experiment. First row: training set, second row: test set. (b) Second experiment. First row: training set, second row: test set. (c) Third experiment. First row: training set, the test set #1 contains the middle image of the first row (photo taken on 10/31/1994) and the test set #2 contains the second row image (photo taken on 05/21/1996). (d) Fourth experiment. First row: training set from the FERET database. Second (resp. third) row: an extract of a sequence from the test set #1 (resp. #2) from the BioId database.

Figure 3 .

 3 Figure 3. Compared recognition rates of 2DO-LDA and 2D-PCA when varying the number k of projection vectors (first column) and compared CMC curves of 2DO-LDA, 2D-PCA and LDA, for each of the four experiments (second column).

Acknowledgments

Portions of the research in this paper use the FERET database of facial images collected under the FERET program.


Odile Piton

Klara Lagji

Morphological study of Albanian words, and processing with NooJ

Keywords: morphological analysis, electronic dictionary, Albanian language, natural language processing, inflectional graph, morphological graph, dynamic processing, syntactical grammar

We are developing electronic dictionaries and transducers for the automatic processing of the Albanian Language. We will analyze the words inside a linear segment of text. We will also study the relationship between units of sense and units of form. The composition of words takes different forms in Albanian. We have found that morphemes are frequently concatenated or simply juxtaposed or contracted. The inflected grammar of NooJ allows constructing the dictionaries of flexed forms (declensions or conjugations). The diversity of word structures requires tools to identify words created by simple concatenation, or to treat contractions. The morphological tools of NooJ allow us to create grammatical tools to represent and treat these phenomena. But certain problems exceed the morphological analysis and must be represented by syntactical grammars.

Introduction

The late reform, in 1972, has lead to the current Albanian Literary Language that is the result of the unification of two Albanian dialects: Gheg and Tosk. This work focuses on the building of Natural Language Processing tools that are useful for the processing of the Albanian language. The dictionaries needed by automatic treatment must register basic vocabulary. They must be associated with tools that are able to recognize words obtained according to creative paradigms. So these tools compute the new words of the constructed part of the dictionary. Our purpose is to be able to recognize words automatically in a text and some morphological features. A general feature of Albanian is that there are a lot of words with particles in two units that will be very troublesome to tag. They are not compound words, and you cannot delay the work on this as a second step, after a first step that would be just recognizing simple or compound words. This is true for part of verbal forms, for most adjectives and for some pronouns and nouns. Another point is that, like every language, Albanian has some creative paradigms, from derivation rules to concatenation rules that are very active and produce concatenated words, lacking in any dictionary.

In the first section, we describe some distinctive features of the Albanian language. Then we describe how we use inflectional graphs, morphological graphs and syntactical graphs for the building of electronic dictionaries for the Albanian language. So this work focuses on morphological and syntactic features. We have managed to register the dictionaries in different formats. It is kept in tables, from which we generate lists of words for NooJ dictionaries. However, our tables can evolve and be adapted to the necessities of semantic tagging.

First Remarks on Albanian Language

Let us make a comparison between some of the most frequent tokens into an English book, a French book and an Albanian book. We display the number of words and the number of tokens1 in Table 1.1. We have distinguished the five most frequent tokens. In the English book which are 13.6 per cent of the tokens and 13.3 per cent in the French book. See Table 1.2. We observe that they are determiners, propositions and conjunctions. Most Frequent Tokens in the Albanian text:

In the Albanian book, the three most frequent tokens are 13% of the whole. The three words are very frequent particles that are part of articulated words or articulated adjectives. See Table 1 Our purpose is not to display grammar of the Albanian language here, but it is important to list some precise points that have consequences on our objective: building dictionaries and transducers for the automatic treatment of the Albanian texts.

Albanian alphabet and alphabetical order

The Albanian alphabet has 36 letters: 7 vowels and 29 consonants. It uses the Latin alphabet. The whole list is a b c ç d dh e ë f g gj h i j k l ll m n nj o p q r rr s sh t th u v x xh y z zh. This list is in alphabetical order. Nine of the consonants are written with digraphs 3 or double characters: dh gj ll nj rr sh th xh zh, they must be considered as one letter. But programs are not used to taking digraphs into account.

Collation, or assembly of written information into alphabetical order, is not similar to sorting algorithms: e and ë are not considered as consecutive letters. As for digraphs, it is different as well. Any word beginning with dh must be positioned after any word beginning with a d . However, when you alphabetize a list of words, any word beginning with di will be placed after dh . It is very time consuming to process big files with words that do not follow printed dictionaries order. This process requires extra time for each item that needs to be verified. Morphological study of Albanian words, and processing with NooJ

Electronic Dictionary From Printed Dictionary Printed Dictionary

We have used the Albanian-French dictionary (4951 words) of the book Parlons Albanais [Ch Gut A Brunet-Gut Remzi Përnaska]. We have observed its format. Part of speech, such as noun, verb, etc. is not always written, but the Albanian speaker is generally able to know if an entry is a verb, a noun, an adjective, or an adverb We transform the dictionary to prepare the dispatching of words into categorical lists. We have used Excel with VBA macros to extract with few errors, 95% of the words of the list and to share out the different parts of the speech, on separated sheets (Fig. 2.1.). Lots of errors have been found, from minor ones, like a lack of a comma, space or hyphen, to some bigger ones. Some of these errors are never noticed by the reader, who is able to correct them mentally and automatically. He is able to supply slight deficiencies, but computers cannot! The best way, for an editor, to check a dictionary seems to be by using a program.

Electronic Dictionary

We use Excel plus Macros to dispatch verbs, masculine nouns, feminine nouns, pronouns, adjectives, adverbs, prepositions and conjunctions on different sheets. Unrecognized items are inserted on a problem page that has to be processed manually. Then specialized Macro constructs entries for NooJ, according to the category and required features of each subset. NooJ s dictionaries accept single words as well as locutions or compound words with a hyphen or an apostrophe e.g.: projekt-ligj. Some words that include an apostrophe come from Turkish: Et hem, Mit hat.

Prepositions, Adverbs, Conjunctions

Conjunctions, adverbs and prepositions are invariant.

absolutisht,ADV afër,ADV afërmendsh,ADV së afërmi,ADV afërsisht,ADV afro,ADV porsa,CONJ posa,CONJ posa që,CONJ +UNAMB

Some prepositions determine a case noted as a feature: kallez for accusative (kallezore), gjin for genitive (gjinore), rrjedh for ablative (rrjedhore) and emer for nominative (emërore). me anë,PREP+gjin afër,PREP+rrjedh tek,PREP+emer

Building Dictionary with Inflectional graphs

Inflectional Graphs for Declension

NooJ has two tools to describe the flexions of a word: one is flexion files that describe the flexion; an other is flexion graphs that draw the flexion in a graph. We use graphs. Each declension is called FLX= Xn , where Xn is a declension graph with sub-graphs. Flexion description gives radical + termination + flexion for defined and undefined paradigms. The Table 3

Verbal system

In the dictionary, verbs are listed in the first person singular present tense. This form is called a lemma. A verb can have one or two forms: active form and/or not active forms: e.g. laj to wash and lahem to wash oneself. The two forms have the same past participle and four tenses of non-active forms are built on the same tense as the active form preceded by the particle u : e.g. lava I washed (aorist) u lava I washed myself. There are twenty-one tenses. Some tenses use particles: të and do .

In most cases, if X is the list of the preterit forms, të X gives the list of forms for a subjunctive tense and do të X gives the list of the forms for a conditional mode. It is similar between the subjunctive present tense that has the form të Y and simple future tense that has the form do të Y , with the same list of forms Y. The Y list is very similar to the present tense, for verbs of the active form and it is exactly the same phenomenon for non-active verbs. We must add that clitics can be inserted before X or Y and after të. The declension of verbs is mainly regular, from three forms: present, aorist, past participle. They are written in the dictionary. Some tenses use particles të or do të .

We have drawn inflectional graphs to build one form for each person of each conjugation. That is to say 8 verbal forms, plus two forms for imperative. Active and non active verbs are described by separate graphs. The total is about 200 graphs and sub-graphs. We present the graph for the present tense of verbs like afroj. It is processed from left to right. <B> means delete the last character. The features written under the nodes are features that are added to the entry. See Fig. 3.1. The category V is for verb: afroj,V+FLX=Xi. Where Xi is the main graph and PR_afroj is a sub-graph for the present of the indicative. Meta-language commands are between brackets <>. The possibilities are to either delete a letter, add a letter, and go left or right inside the word. Insertions are in the nodes. The graph treats the input words, it deletes, or adds letters and adds features (information written under the nodes) separated by the + sign. +PR+Ind+3+p means present of indicative, third person of plural. The conjugation of afroj is the most regular. It applies to 30% of the verbs As seen before, we have to take care of digraphs. For some verbs, aorist is marked by a change in vowel, e.g. e o . We separate the set of these specific verbs into two subsets and we draw two graphs, according to the occurrence of one simple or double letter. See regular paradigm 4 in Table 3.2.

Inflectional Graphs for Nouns, Pronouns and Adjectives

Nominal and pronominal System (Words without Article)

Albanian is an inflected language. Nouns are masculine, feminine or neutral. (Neutral nouns are rare, and they have no plural. We do not discuss them in this paper). Other nouns have four forms: two for the singular and two for the plural. One is called indefinite while the other is called definite. In the printed dictionary, these four forms are written in the nominative case: rad/t1,-t2 g, nb. (-t3, -t4). E.g.:

an/ë,-a f. pl. (-ë, -ët) side.

Masculine and feminine nouns have different suffixes for declension in the singular, and in the plural. A great number of masculine words in the singular are feminine in the plural. These words are called ambigens . Declension position is at the end of the word, except in the case of compound words where declension at the end of the first component (cilido, cilitdo; cilado, cilësdo; kushdo, kujtdo [START_REF] Murzagu | Inverse Dictionary of Albanian[END_REF] ).

Foreign Named Entities are transcribed according to Albanian phonetic: Meksika Mexico, Xhorxh Bernard Shou George Bernard Shaw, Penxhabi the Punjab, Pirenejtë the Pyrenees. Proper names are flexed with the same paradigms than other nouns. So do acronyms, but the flexion is preceded by a dash OKB-ja (nominative), OKB-në (accusative).

Adjectives have masculine, feminine, singular and plural forms. When an adjective without an article is after a noun, it is not declined; it is just flexed according to gender and number. It is the reverse if the adjective precedes the noun: the adjective itself is flexed and the noun is not.

Articulated Words : Some Nouns, Adjectives and Pronouns

Most adjectives, some nouns and many pronouns are preceded by a particle called nyjë [START_REF] Piton | Electronic Dictionaries and Transducers for Automatic Processing of the Albanian Language[END_REF] and noted (i,e) in the dictionary. (i for masculine, e for feminine). Such words are called articulated words . These particles have declensions. These declensions vary according to the place of the articulated adjective or articulated noun in nominal syntagm. We have built inflectional graphs for articulated words.

Inflectional Graphs

We have studied the typology of singular and plural paradigms. With the exception of approximately thirty graphs, which require a specific graph each, there are about sixty graphs for masculine singular nouns and forty for feminine singular nouns. We have about eighty graphs that depict paradigms for the plural forms of the nouns. This number is increased by the problem of digraphs, as we explain below.

From description + entry, NooJ builds a list of declined forms. The result can be listed in a file (its extension is .flx) for verification. It is compiled and minimized in a Finite State Automata, for use during lexical analysis. The Problem with Digraphs.

Some rules like go left one letter , delete one letter , have to be redefined as go left two characters , delete two characters , according to the fact that one letter has two characters. And for the computer it is two letters! The whole set of words that obey the regular paradigm, has to be dispatched between the one character paradigm and the double character paradigm . Nouns ending by ër, or ërr, or ël, or ëll, construct their defined form in loosing ë and receiving a or i . See paradigms 1 and 2 in Table 3.2. Some nouns change their ending from the singular into the plural. For example the two words bir and djall drop their last letter and receive j. But the last consonant of djall is a double letter, so we need two paradigms for this transformation. See paradigm 3 in Table 3.2.

Building Dynamic Dictionary with Morphological graphs

A dictionary is a finite set of words; when there are paradigms that allow building infinite lists of words called open lists-, they cannot be listed into dictionaries. These forms can be a form that is built from one or more words or affixes. They can be concatenated, or separated by a typographical element -an apostrophe, a dash or simply a space-and in some cases two different words are contracted, but this sometimes includes an apostrophe. We have to study the composition XY of two words X and Y in Albanian. We call them XY words .

Morphological study of Albanian words, and processing with NooJ

Numbers and XY Words with Numbers.

The cardinal numbers

The cardinal numbers are partly concatenated e.g. 5: pesë, 10: dhjetë, 50: pesëdhjetë, 40: dyzet, hundred : qind , 500: pesëqind. They can be compounds: 41: dyzet e një, 55: pesëdhjetë e pesë, 555: pesëqind e pesëdhjetë e pesë ( e means and). NooJ can recognize cardinal numbers with syntactical graphs, as in French.

The ordinal numbers

The ordinal numbers are articulated words fully concatenated e.g.:5 th : (i,e) pestë, 41 th : (i,e) dyzetenjëtë, 50 th : (i,e) pesëdhjetë, 555 th : (i,e). pesëqindepesëdhjetëepestë. The second component is recognized by a morphological graph. Fig. 4.1. the graph computes the number and adds it as a feature.

Roman numerals are recognized by the same morphological graph than in French.

XY Words with Numbers

There is a third form , that is like fully concatenated cardinal numbers. It is used as the first component X in XY words expressing a quantity of something: e.g. fifty-five years old is said pesëdhjetëepesëvjeçar . This is a single word, the first part of which is the concatenation of 55 pesëdhjetë e pesë followed by vjeçar that is not a word, but a component that means aged of. This construction is very productive. Any age can be expressed by a single word, as well as any number of floors, any number of months, of hours, of teeth etc. E.g.: fifty floors, pesëdhjetëkatësh, twelve months: Dymbëdhjetëmujor, three teeth: tredhëmbësh, four motors: katërmotorësh, two times: dyfish.

A lot of words have a derived form that can enter such a compound. The morphological graphs of NooJ can recognize dynamically such words as nouns, adjectives, adverbs, or verbs: it is possible to say not only to quadruple katërfishoj, but something like t-uple for any value of t.

XY Words Built with affixes.

Y can be a verb, a noun, or an adjective and X can be an affix, a prepositional form, a noun, an adjective or an adjective finished by an o e.g. leksikogramatikore lexical-grammar, italo-shqip Italiano-Albanian. About seventy affixes are listed in the Albanian dictionary. E.g.: gjysmë half, bashkë together bashkëbisedim conversation, pa not, aftë (i,e) able vs paaftë (i,e) unable, nën under, kuptoj to understand, nënkuptoj to suggest. This construction is very productive. An interesting property is that words are concatenated most often without contraction or modification. That makes them easy to recognize.

We have part the list of affixes between prefixes the biggest part-and the suffixes forms that are fob : anglofob, gjermanofob, and fobi : bakterofobi, fotofobi. We have already seen other suffixes in XY words with numbers.

Morphological study of Albanian words, and processing with NooJ A morphological graph can recognize several parts in a word and can compare them either to a specified list, or to a subset of words. We can insert parentheses with a name, like M1 and M2 and the word extracted in the loop with <L> is associated to the variable M2. Then M2 is compared to words in the dictionary. In case of success, the word is recognized and receives the lexical features $1L and the syntactic features $1S of M1. See Fig. 4.3.

Morphological Graphs For Imperative Tense with Clitics

As for the imperative form, the verb can concatenate with the clitic complement. In the plural the clitic can be inserted inside the imperative verb: trego tell, më trego or tregomë tell me, in the plural form the clitic is included inside the verb: let you tell it e tregoni tregojeni. The letter j can be added in some forms. The

X-Y Words Recognized by Syntactic Grammars

The syntactic graphs are used to recognize grammars involving several tokens. They can be organized into a hierarchy. So a syntactic grammar can use the result of an other one. This is very usual. We want to point out some cases very briefly.

Ordinal numbers

In figure 4.1. we show a graph that recognizes the second component of an ordinal number. For the whole ordinal number, that is a compound with a particle i or e, we use a syntactic graph. As in other languages, syntactic grammars can be used to recognize compound tenses.

X-X Words

Features in the Dictionaries

Properties Definition. The resulting dictionaries will be compiled as Finite State Transducers. They will register all words, plus their category and all their features, grammatical and linguistic. An important part of the work is to organize the features and tags. The aim is double: firstly, it will be necessary to display the annotations dictionary as a table; secondly this is necessary to be able to improve

Conclusion

We conclude that the NooJ s graphs -morphological graphs and syntactic grammars-are very efficient for the automatic processing of the Albanian language. We are able to identify XY words created by simple concatenation, as well as X-Y words built with an hyphen. We can recognize the words built with numbers. We can recognize dynamically different kind of open lists of words.

Our aim is to be able to automate this language but because some words and some forms in dialect are still being used, we have chosen to add some traditional forms (for example plural ablative Gheg in sh , Gheg future and Gheg infinitive), that are commonly used. The choice of the features cannot be seen as achieved. Every new work can lead us to part set of words, to add new features or to transform them. The dictionary is growing bigger and bigger. But a big inconvenient is that texts older than 35 years will not be recognized, except partly.

It will be necessary to add entries from others Albanian dictionaries to this first electronic dictionary. We are mindful that there is still a lot to do.

3

  Called digrams in Albanian, but digram means reoccurring two words in NooJ s environment.

Fig. 2 . 1 .

 21 Fig. 2.1. Distribution of words between different lists.

Fig. 3 . 1 .

 31 Fig. 3.1. Graph for the present tense of verbs similar to afroj to approach. From entry afroj,V+FLX=PR_afroj this sub-graph generates afroj,V+PR+Ind+1+s afron,V+PR+Ind+2+s afron,V+PR+Ind+3+s afrojmë,V+PR+Ind+1+p afroni,V+PR+Ind+2+p afrojnë,V+PR+Ind+3+p

Fig. 4 . 1 .

 41 Fig. 4.1. Morphological graph for ordinal numbers.

Fig. 4 . 2 .

 42 Fig. 4.2. Morphological graph for XY words where X is a number.

Fig. 4 . 3 .

 43 Fig. 4.3. Graph for XY words where Y is a verb or a noun, and X is in a list.

figure 4 . 4 .

 44 figure 4.4. shows the results on examples.

Fig. 4 . 4 .

 44 Fig. 4.4. Morphological Graph to separate clitic and imperative verb.

Fig. 5 . 1 .

 51 Fig. 5.1. Syntactic grammar for X-X words .

Table 1 . 1

 11 Number of words and number of tokens in three books and three languages.

	Title	Author	Number of words Tokens Language
	The portrait of a lady	Henry James	229,000	11,000	English
	La femme de trente ans Honoré de Balzac	70,000	9,150	French
	Kush e solli Doruntinën 2 Ismail Kadare	14,980	8,738	Albanian

Table 1 . 2 .

 12 Most frequent tokens into an English book and a French book.

	English text	French text
	tokens	frequency tokens frequency
	the	3,25%	de	4,08%
	to	3,13%	la	2,96%
	of	2,66%	le	2,31%
	a	2,31%	et	2,14%

Table 1 . 3 .

 13 .3. Most frequent tokens into an Albanian book.

	token frequency	Category
	të	5,94%	Adjective and noun particle / verb particle / pronoun
	e	5,79%	Adjective and noun particle / pronoun/ conjunction
	i	2,21%	Adjective and noun particle / pronoun
	total	12,94%

.

Table 2 .1. Format of the entries in the dictionary

 2

	Category	Format	Examples
	Noun	rad/t1,-t2 g, nb. (-t3, -t4)	aeroplan,-i m. pl. (-ë, -ët) plane m.
	Active Verb	form1 (form2, past participle)	laj (lava, larë) to wash
	Non active Verb	form1 (u form2, participle)	lahem (u lava, larë) to wash oneself
	Adjective	form (i,e)	mirë (i,e) good
		form(e)	absurd(e) absurd
	Preposition	entry POS plus features	afër adv. and prep. + abl. near
	Adverbs	entry adv.	pjesërisht adv. partly
	Interjection	entry! excl!	adio! excl. adieu!

Table 3 . 1 .

 31 Part of flex file for an ambigen word: agim,-i (-e, -et) dawn

	Entry	Flexions in the singular, define forms
	agim,N+FLX=NS2_t+m+s agimi,agim,N+FLX=NS2_t+m+s+emer+shquar
		agimin,agim,N+FLX=NS2_t+m+s+kallez+shquar
		së agimit,agim,N+FLX=NS2_t+m+s+gjin+shquar
		të agimit,agim,N+FLX=NS2_t+m+s+gjin+shquar
		i agimit,agim,N+FLX=NS2_t+m+s+gjin+shquar
		e agimit,agim,N+FLX=NS2_t+m+s+gjin+shquar
		agimit,agim,N+FLX=NS2_t+m+s+dhan+shquar
		agimit,agim,N+FLX=NS2_t+m+s+rrjedh+shquar
		Flexions in the plural, undefined forms
	agim,N+FLX=NPL7+f+p agime,agim,N+FLX=NPL7+f+p+kallez+pashquar
		agime,agim,N+FLX=NPL7+f+p+emer+pashquar
		e agimeve,agim,N+FLX=NPL7+f+p+gjin+pashquar
		i agimeve,agim,N+FLX=NPL7+f+p+gjin+pashquar
		të agimeve,agim,N+FLX=NPL7+f+p+gjin+pashquar
		së agimeve,agim,N+FLX=NPL7+f+p+gjin+pashquar
		agimeve,agim,N+FLX=NPL7+f+p+dhan+pashquar
		agimeve,agim,N+FLX=NPL7+f+p+rrjedh+pashquar
		agimesh,agim,N+FLX=NPL7+f+p+rrjedh+geg+pashquar

Table 3 . 2 .

 32 Regular paradigms vs. single char. and double char. paradigm.

	paradigm	rule	example	translation
	paradigm 1	Insert a, go left 1 letter, delete 1 letter
	1 char. paradigm 1	a<L><B>	motër motra	sister
	2 char. paradigm 1	a<L2><B>	vjehërr vjehrra mother in law
	paradigm 2	Insert i go left 1 letter, delete 1 letter
	1 char. paradigm 2	i<L><B>	gjarpër gjarpri	snake
	2 char. paradigm 2	i<L2><B >	vjehërr vjehrri faiher in law
	paradigm 3	delete 1 letter, insert j
	1 char. paradigm 3	<B>j	bir bij	son
	2 char. paradigm 3	<B2>j	djall djaj	devil
	paradigm 4	Insert a, go left 1 letter, delete 1 letter, insert o
	1 char. paradigm 4	a<L><B>o	heq hoqa	To dig out
	2 char. paradigm 4	a<L2><B>o	hedh hodha	To throw

A token is a sequence of letters, it can be a word, or a contraction like cannot , or a component of an compound like fur in au fur et à mesure .

Who Brought Back Doruntine? published in English as Doruntine .

All three mean anyone. It is the same phenomenon than auquel and auxquels in French..

The usual translation is article , but it is very different from an article in English or in French, so we use the word particle .

the dictionary. Whenever it is necessary to evolve syntactical and semantic tags, the dictionary will be modified. It is important to be able to adapt it easily. For example, a new study can make it necessary to define two tags instead of one. So the set of features and tags must be carefully registered and regularly updated. We have said that our dictionary is only a syntactical one. We must precise that each time that we have the opportunity to acquire some words not only with syntactic features, but as well with semantic information, we do it. As a result we have some semantic tags. It is all the more important to register them in a properties definitions file. It will be necessary to add semantic information in a next step.


X Guyon
email: guyon@univ-paris1.fr

C Hardouin
email: hardouin@univ-paris1.fr

Recursions on the marginals and normalizing constant for Gibbs processes

Keywords: Gibbs distribution, factorisable distribution, interaction potential, Markov Chain, Markov field, marginal law, normalizing constant, Ising model

This paper presents recurrence formulas allowing the calculus of the marginals and the normalizing constant of a Gibbs distribution π.The numerical performances of different methods are evaluated on several examples, particularly for an Ising model on a lattice.

Introduction

Usually, the computation of the marginal distributions and/or the normalizing constant C of a discrete probability distribution π involves high dimensional summation, such that the direct evaluation of these sums becomes quickly infeasible in practice. For example, for an Ising model on a 10×10 grid, it involves summation over 2 100 terms. This problem has a deep impact for many applications, for instance, maximum likelihood parameter estimation. In the same way, some significant efforts have been put to solve the problem and the litterature displays various alternatives for distributions involving such unreachable constants. For instance, in spatial statistics, we replace the likelihood by the conditional pseudo likelihood [START_REF] Besag | Spatial interaction and the statistical analysis of lattice systems[END_REF][START_REF] Gaetan | Spatial statistics and modeling[END_REF]. Another common way to bypass the problem is to estimate C, see for example [START_REF] Moeller | An efficient Markov chain Monte Carlo method for distributions with intractable normalizing constants[END_REF] for efficient Monte Carlo methods. Sometimes, it is possible to compute C with an efficient algorithm, see for example [START_REF] Liu | Monte Carlo strategies in scientific computing[END_REF]; of course this is an interesting preliminary for further statistical procedures such as simulation or estimation. We briefly recall hereafter some recent results on the subject. [START_REF] Bartolucci | A recursive algorithm for Markov random fields[END_REF] express the likelihood of a Markov field in terms of the product of conditional probabilities; [START_REF] Pettitt | Efficient calculation of the normalizing constant of the autologistic and related models on the cylinder and lattice[END_REF] obtain the exact normalizing constant for a general categorical K-valued distribution on a m × n cylinder with a matrix method involving the computation of the eigenvalues of a K m × K m matrix, which makes it possible for K m 1024, that is for example K = 2 and m = 10. Then [START_REF] Reeves | Efficient recursions for general factorisable models[END_REF] give recursions for π factorisable.

In this paper, we first summarize classical results on the calculus of C and of the marginal distributions of π, a general Gibbs distribution. Then, following an idea of Khaled (2008aKhaled ( , 2008b) (see also [START_REF] Lovinson | A matrix-valued Bernoulli distribution[END_REF], we propose a new algorithm based on π's conditional probabilities to compute the marginals.

The plan of the paper is the following. Section 2 sums up basic properties about π, a Gibbs process on a finite state space; then we recall some results which permit the calculus of the marginals and the normalization constant of π, these results being presented under a new writing. We also compare the numerical efficiency of various algorithms in terms of their computing times.

Section 3 presents a new algorithm based on the conditionals of π to compute the marginals of π. Section 4 extends these results for general Gibbs fields, and evaluates the numerical performance for a spatial Ising model on a lattice m×T .

The paper ends with some generalisations.

Recursions for a temporal Gibbs distribution

Factoring joint distribution, Markov field and Markov chain properties

Let T > 0 be a positive integer, E a finite state space with N elements,

Z(T ) = (Z 1 , Z 2 , • • • , Z T )
a temporal random variable with a factorisable joint distribution π on E T (see [START_REF] Reeves | Efficient recursions for general factorisable models[END_REF]

: for z(T ) = (z 1 , z 2 , • • • , z T ), π(z(T )) = C -1 exp s=1,T -1 h s (z s , z s+1 ) = C -1 s=1,T -1 H s (z s , z s+1 ) (1)
Let us give some notations; in all the following, we interprete

H s , s = 1, T -1, as N × N matrices of elements H s (u, v) = exp h s (u, v). For such two N × N matrices H and G, for a N -row vector F = (B(v), v ∈ E)
, and for a N -column vector B = (B(v), v ∈ E), we note, as in the classical way,

HG(u, v) = w∈E H(u, w)G(w, v) , F H(v) = u∈E F (u)H(u, v) and HB(u) = v∈E H(u, v)B(v).
HG is a N × N matrix and HB an N -column vector. We also denote π S the marginal of π on the subset

S ⊆ T = {1, 2, • • • , T }, and π t s = π [s,t] with [s, t] = {s, s + 1, • • • , t} for s < t.
We can interpret π as a Gibbs distribution with energy U T (z(T )) = s=1,T -1 h s (z s , z s+1 ) associated to saturated pairs potentials (h s ) s=1,T -1 . In particular, π is a bilateral Markov random field w.r.t. the 2-nearest neighbours system (see [START_REF] Kindermann | Markov random fields and their applications[END_REF][START_REF] Lauritzen | Graphical models[END_REF][START_REF] Guyon | Random fields on a network : modeling, statistics and applications[END_REF]:

π(z t | z s , s = t) = H t-1 (z t-1 , z t )H t (z t , z t+1 ) H t-1 H t (z t-1 , z t+1 ) = π(z t | z t-1 , z t+1 ).
Let us note that this non causal conditional distribution π(z t | z t-1 , z t+1 ) can be easily computed as soon as N , the cardinal of E, remains rather small. On the other hand, the normalizing constant C as well as the marginals cannot be computed since they entail high dimensional summation.

Z(T ) is also a Markov chain; indeed, π(z t | z s , s ≤ t -1) = π t 1 (z 1 ,z 2 ,•••,z t ) π t-1 1 (z 1 ,z 2 •••,z t-1 )
; then, for 1 ≤ s < t ≤ T , and using the notation

u t s = (u s , u s+1 , • • • , u t ), we write π t 1 (z 1 , z 2 , • • • , z t ) = u T t+1 ∈E T -t π(z 1 , z 2 , • • • , z t , u T t+1 ). Finally, we have π(z t | z s , s ≤ t-1) = H t-1 (z t-1 , z t ) u T t+1 H t (z t , u t+1 ) T -1 s=t+1 H s (u s , u s+1 ) u T t H t-1 (z t-1 , u t ) T -1 s=t H s (u s , u s+1 ) = π(z t | z t-1 ).
But the analytic form of the transition cannot be explicited because it also requires high dimensional summation.

Recursions over marginal distributions

Let us set B T = 1 the N -column vector with constant coordinates 1. By direct marginalization on z T , we obtain :

π T -1 1 (z 1 , z 2 , • • • , z T -1 ) = C -1 { s=1,T -2 H s (z s , z s+1 )}(H T -1 B T )(z T -1 )
In the same way, defining B t-1 = H t-1 B t , we have, for t = T, 2 :

π t 1 (z 1 , z 2 , • • • , z t ) = C -1 s=1,t-1 H s (z s , z s+1 )(H t B t+1 )(z t ) (2) = C -1 s=1,t-1 H s (z s , z s+1 )(H t • • • H T -1 B T )(z t ) .
These equations, up to the constant C, gives the marginals π t 1 . Looking at π {1} , and denoting F 1 = t B T the N -row constant vector with components equal to 1, we express the normalizing constant

C = C × z 1 ∈E π {1} (z 1 ) = F 1 { s=1,T -1 H s }B T .
(3)

These results about the marginals and the constant can be found, eventually differently presented, in other works, see for instance paragraph 2.4 of [START_REF] Liu | Monte Carlo strategies in scientific computing[END_REF], and [START_REF] Reeves | Efficient recursions for general factorisable models[END_REF]. However, our writing is interesting since it gives a very simple algorithm to compute efficiently the normalizing constant, in terms of matrices products.

Analogously, using forward recursions, and defining

F t = F t-1 H t-1 for t ≥ 2,
we obtain :

π T t (z t , z t+1 , • • • , z T ) = C -1 {(F t-1 H t-1 )(z t ) s=t,T -1 H s (z s , z s+1 )} = C -1 {(F 1 H 1 H 2 • • • H t-1 )(z t ) s=t,T -1 H s (z s , z s+1 )}.
More generally, let us consider the marginal of π on the subset

S = {s 1 , s 2 , • • • , s q } ⊆ T = {1, 2, • • • , T }.
For C given by (3), we have the following result:

Proposition 1. 1 -The marginal distribution of π on S = {s 1 , s 2 , • • • , s q } with 1 = s 1 < s 2 < • • • < s q-1 < s q = T is π S (z 1 , z s 2 , • • • , z s q-1 , z T ) = C -1 i=1,q-1 ( s i+1 -1 s=s i H s )(z s i , z s i+1 ), (4) 2 -The marginal on S 1,T = S \ {1, T } is obtain by changing the first H- product ( s2-1 1 H s )(z 1 , z s 2 ) by t 1( s2-1 1 H s )(z s 2 ) and the last product ( sq-1 s q-1 H s )(z s q-1 , z T ) by (( sq-1 s q-1 H s )1)(z sq-1 ).

Numerical performances

Formula (3) simplifies for time invariant potentials h

s = h (H s = H). In this case, C = t 1(H) T -1 1 (or C = t 1(H) T -2 H T -1 1 if H T -1 = H); if the size N of
Ψ t (z t , z t+1 ) = βz t z t+1 for t ≤ T -1. We have h t (z t , z t+1 ) = θ t (z t ) + Ψ t (z t , z t+1 ) for t = 1, T -2 and h T -1 (z T -1 , z T ) = θ T -1 (z T -1 ) + Ψ T -1 (z T -1 , z T ) + θ T (z T ).
We present in Table 1 the times for the computation of C for increasing values of T and the following three methods: (1)

C = t 1(H) T -2 H T -1 1; (2) C
is computed by direct summation over E T using a simple loop (each element is computed one by one and added to the previous calculus); (3) C is obtained by summation again, using a bitmap dodge which computes simultaneously the 2 T elements of E T . We stopped computing C by summation (methods 2 and 3) for T > 25.

= h, h((x 1 , y 1 ), (x 2 , y 2 )) = αx 1 + βy 1 + γx 1 y 1 + αx 2 + βy 2 + γx 2 y 2 + δ(x 1 x 2 + y 1 y 2 ) ,
with the convention that a pair potential equals 0 if a state is taken out of small to distinguish computations using power or diagonalization of H.

Results for r-range potentials

Reeves and Pettitt ( 2004) consider more general r-factorisable distribution

π(z(T )) = T -r s=1 H s (z s , z s+1 , • • • , z s+r ).
There, the function H s is defined on E * = E r+1 . For H a real function defined on E * , we set H * defined on E * × E * by:

H * (u, v) = H(u r+1 2 , v r+2 ) r i=1 1(u i+1 = v i ).
(5)

Then, respectively to the ( * )-objects, and with the notations of §2.1, we obtain the same results, for example the normalizing constant C = t 1( T -r s=1 H * s )1. Recursive algorithms for the marginals of π follow in the same way as in ( 2) and (4).

A new recursive algorithm for marginals based on future conditionals

Let us clarify the Gibbs specification (1) of π in term of singletons and pairs potentials, and write :

h s (z s , z s+1 ) = θ s (z s ) + Ψ s (z s , z s+1 ) for s = 1, T ,
with the convention Ψ T ≡ 0. Then we get the energy's writing for t = 1, T , and

z t 1 = (z 1 z 2 , • • • , z t ): U t (z t 1 ) = s=1,t θ s (z s ) + s=1,t-1 Ψ s (z s , z s+1 )
We use conditioning by the future in order to compute recursively the marginal π t 1 . First we define the contribution of π, conditionally to the future (z t+1 ,

• • • , z T ). For t < T , it is clear that π(z 1 , z 2 , • • • , z t | z t+1 , • • • , z T ) = π(z 1 , z 2 , • • • , z t | z t+1 ). Then, for t < T , π(z t 1 | z t+1 ) = C -1 t (z t+1 ) exp U * t (z t 1 ; z t+1 ),
where

U * t (z t 1 ; z t+1 ) = U t (z t 1 ) + Ψ t (z t , z t+1
) is the future-conditional energy, and

C t+1 (z t+1 ) = u t 1 ∈E t exp {U * t (u t 1 ; z t+1 )}. Definition 1. For 1 ≤ t ≤ T , let γ t (z t 1 ; u) = exp U * t (z t 1 ; u) be the future- conditional contribution of π t
1 , conditionally to the future z t+1 = u. Then we define Γ t (z t 1 ) as the N -row vector of the future-conditional contributions of π at time t:

Γ t (z t 1 )(u) = γ t (z t 1 ; u), u ∈ E . For t = T , Γ T (z(T )) is the constant vector of components γ T (z(T )) = exp U T (z(T )). Let us notice that Γ t (z t 1 ) is analytically explicit. For 1 ≤ t ≤ T , let H t (u, v) = exp{θ t (u) + Ψ t (u, v)}, u, v ∈ E
-For 2 ≤ t ≤ T and z t 1 = (z 1 , z 2 , • • • , z t ) ∈ E t ,
we have:

z t ∈E Γ t (z t-1 1 , z t ) = Γ t-1 (z t-1 1 )H t . (6) 2 -For 1 ≤ t ≤ T , π t 1 (z t 1 ) = C -1 × Γ t (z t 1 )D t . (7) Proof. 1 -For 2 ≤ t ≤ T , U t (z t-1 1 , z t ) = U t-1 (z t-1 1 ) + θ t (z t ) + Ψ t-1 (z t-1 , z t ); therefore, U * t ((z t-1 1 , z t ); z t+1 ) = U t-1 (z t-1 1 ) + θ t (z t ) + Ψ t-1 (z t-1 , z t ) + Ψ t (z t , z t+1 ) = U * t-1 (z t-1 1 ; z t ) + {θ t (z t ) + Ψ t (z t , z t+1 )}.
This implies γ t ((z t-1 1 , z t ); u) = γ t-1 (z t-1 1 ; z t ) × H t (z t , u) and summation over z t gives (6).

2 -We prove (7) by descending recurrence. For t = T , the equality is verified since

π T 1 (z T 1 ) = π(z(T )) = C -1 exp U T (z(T )) = C -1 × Γ T (z(T ))D T .
Let us assume that ( 7) is verified for some t, 2 ≤ t ≤ T . We use (6) which gives:

π t-1 1 (z t-1 1 ) = zt π t 1 (z t-1 1 , z t ) = C -1 { zt Γ t (z t-1 1 , z t )}D t = C -1 Γ t-1 (z t-1 1 )H t D t = C -1 Γ t-1 (z t-1 1 )D t-1 .
Proposition (2) can be extended in a natural way to r-lag Gibbs processes.

For example, let us consider the 2-lag factorisable distribution π, characterized by the following energy:

to a family A = {A k , k = 1, K} of subsets of S, Φ A k (z) depending only on z A k ,
the layout of z over A k . Then π is characterized by the energy:

U (z) = k=1,K s∈S(k) Φ A k +s (z), with S(k) = {s ∈ S s.t. A k + s ⊆ S}.
For A ⊆ S, we define the height of A by r(A) = sup{|u -v| , ∃(u, i) and

(v, j) ∈ A}, and r = r(A) = sup{r(A k ), k = 1, K} the biggest height of the potentials. With this notation, we write the energy U as the following:

U (z) = H h=0 T t=h+1 Ψ(z t-h , • • • , z t ) with Ψ(z t-h , • • • , z t ) = k:r(A k )=h s∈S t (k) Φ A k +s (z)
where

S t (k) = {s = (u, i) : A k + s ⊆ S and t -r(A k ) ≤ u ≤ t}.
(Z t ) is a Markov random field w.r.t. the 2r-nearest neighbours system but also a Markov process with memory r:

Y t = (Z t , Z t+1 , • • • Z t+r ), t = 1, T -r, is
a Markov chain on E * = E r for which we get the results ( 7) and (3).

Computing the normalization constant for the Ising model

We specify here the calculus of C for a translation invariant Ising model. Let

S = T × I ={1, 2, • • • , T } × {1, 2, • • • ,
m} be the set of sites, F = {-1, +1} the state space, and Z = (Z (t,i) , (t, i) ∈ S) the Markov random field on S with the 4-nearest neighbours system. The joint distribution π of Z is characterized by the potentials

Φ t,i (z) = α z (t,i) for (t, i) ∈ S, Φ {(t,i),(t,i+1)} (z) = β z (t,i) z (t,i+1) for 1 ≤ i ≤ m -1, and Φ {(t,i),(t+1,i)} (z) = δ z (t,i) z (t+1,i) for 2 ≤ t ≤ T.
Z is also a temporal Gibbs process with the following potentials:

θ t (z t ) = θ(z t ) = α i=1,m z (t,i) + β i=1,m-1 z (t,i) z (t,i+1) , Ψ t (z t , z t+1 ) = Ψ(z t , z t+1 ) = δ i=1,m z (t,i) z (t+1,i) , 1 ≤ t ≤ T -1.
We define the following counting statistics associated to c, d ∈ E = {-1, +1} m :

n + (c) = {i ∈ I : c i = +1}, n -(c) = m -n + (c), v + (c) = {i = 1, m -1 : c i = c i+1 }, v -(c) = (m -1) -v + (c), and finally n + (c, d) = {i ∈ I : c i = d i }, n -(c, d) = m -n + (c, d).
Then we apply the formula (3) w.r.t. the following 2 m × 2 m matrices (H t ) defined for any u, v ∈ E = {-1, +1} m and δ(t) = δ × 1 (t≤T -1) by :

H t (u, v) = exp{α(n + (u)-n -(u))+β(v + (u)-v -(u))+δ(t)(n + (u, v)-n -(u, v))}.
Example 3 We observe that it's computationally more efficient to compute the powers H T -2 rather than to use diagonalization. Indeed, the diagonalization procedure itself is expensive for large size matrices, and we use here vectors and square matrices of size 2 10 .

Some generalizations

The results can be extended to larger potentials, as triplet potentials and so on.

Another extension considers varying state spaces E t z t ; the recurrence (6) and properties (7), (3) still hold but in this case, the matrices H t are no longer square.

Finally, we can extend results (2), ( 3) and ( 6) to a sequence of embedded

subsets of T = {1, 2, • • • , T }. Let us consider a decreasing sequence T = S Q ⊃ S Q-1 ⊃ • • • ⊃ S 1
of subsets of T and assume S q = S q-1 ∪ ∂S q-1 for q = 1, Q -1.

Similarly to the former future-conditional contributions (7) presented in definition 1 and used in proposition 2, we define the contributions γ q (z(S q ); z(T S q )) conditionally to the outer layout z(T S q ). Then, we obtain (7) respectively to the conditional energy U * q , U * q (z(S q ); z(∂S q )) = U * q-1 (z(S q-1 ); z(∂S q-1 )) + ∆ q (z(∂S q-1 )); z(∂S q )), with

∆ q (z(∂S q-1 )); z(∂S q )) = u∈∂S q-1 θ u (z u ) + u∈∂S q-1 ,v∈∂S q ,<u,v> Ψ {u,v} (z u , z v ),
and the matrices H q :

H q (∂S q ; ∂S q-1 ) = exp ∆ q (z(∂S q-1 ); z(∂S q )) .

Conclusion

This paper gives results permitting the evaluation of marginals and normalizing constant for a Gibbs processes π. Some of these results, known in the litterature, are presented with another formalism. A new result, based on the contributions of π conditionally to the future, permits another recursion to compute the marginals of π. In particular, these results are applicable to Markov chains and Markov fields. It overcomes the need to resort to approximate alternatives for the likelihood, and makes feasible the exact evaluation of the normalizing constant for moderate set of sites.

We gave several illustrations of the algorithm's efficiency in terms of computing times for the normalizing constant. For one dimensional two states Gibbs fields, we are able to compute instantaneously the normalizing constant for a sequence of length 700, as well as for a sequence with four states and of length 400. We could keep computing for bigger lengths using another software able to manipulate large matrices.

Since a random field with states in F can be seen as a temporal m-multivariate Gibbs process in E = F m , we give similar results on marginals and normalizing constant for a Gibbs random field. We have computed the normalizing constant for an Ising model on a lattice 10 × 100 in 20 seconds. While we could increase the temporal parameter T, one of the side of the lattice, the limitation of the procedure ensures from the manipulation of E m × E m matrices. So the method seems to fail for large square lattices. As a comparison, [START_REF] Pettitt | Efficient calculation of the normalizing constant of the autologistic and related models on the cylinder and lattice[END_REF] compute the normalizing constant for an autologistic model defined on a cylinder lattice for which the smallest row or column is not greater than 10. They suggest to split a large lattice into smaller sublattices along the smallest row or column. A similar idea could apply here.

E

  allows the diagonalization of the matrix H, we can achieve the calculus of C independently of the temporal dimension T . Let us look at two examples for which we compare the computing times for different algorithms. For this study, we have used the software Matlab . Example 1 : binary temporal model Let us consider E = {0, 1} and the autologistic Gibbs field π associated to time independent singletons and pairs potentials θ t (z t ) = αz t , t = 1, T and

  the time domain {1, 2, • • • , T }. We computed the constant C in two ways, first calculating directly the power H T -2 , then making use of the diagonalization of H, i.e. calculating C = t 1P D T -2 P -1 H T -1 1. The parameter values are α = 1, β = -0.8, γ = -0.5, and δ = 0.04. We were able to calculate C for T ≤ 430 and then stopped since the software treats C as equals to infinity. The computing times for both methods are instantaneous, the size of H being too

  and let us define the sequence (D t , t = T, 2) of N -column vectors by D T = t (1, 0, • • • , 0), and D t-1 = H t D t for t ≤ T . Then the following result gives a new recursion for the marginals, based on the future-conditional contributions. Proposition 2. Recursion for marginal distributions.

  1

Table 1 :

 1 Computing times (in seconds) of C for a binary temporal Gibbs distribution, α = 1, β = -0.8.

We observe that the computing times of C = t 1(H) T -2 H T -1 1 are negligible for T < 700 while methods 2 and 3 become quickly unusable.

Example 2 : bivariate binary temporal model

We consider now E = {0, 1} 2 and Z(T ) is the anisotropic Ising model with invariant saturated potentials h s

Table 2 :

 2 Table2gives computing times for the normalizing constant C for this Ising model with parameters α = 0.15, β = 0.05, δ = -0.08. We fix m = 10 and consider increasing values of T . We compute C using (3) and two methods:(M1) calculates the power H T -2 of H, while (M2) uses diagonalization of H. Computing times of C for an Ising model on a lattice 10 × T.

	m = 10	M1	M2	C
	T = 2	0.3130 32.4850 1.3855e+006
	T = 10	8.9220 40.8290 5.4083e+030
	T = 50 15.4380 47.4060 4.8989e+153
	T = 100 19.3600 51.0950 2.4344e+307

with the convention Ψ 1,T ≡ Ψ 2,T -1 ≡ Ψ 2,T = 0. It is easy to see that π is a Markov field w.r.t. the 4-nearest neighbours system and:

where

Then, we have:

Following the previous scheme, we define for t ≤ T, the N 2 -row vector Γ t (z t 1 ) by

Then, as in the proof of Proposition (2), but w.r.t the E * × E * matrices (H * s ) (5) with in this case E * = E 2 , we obtain the recurrence (6) on the contributions Γ t (z t 1 ) and the results (7) on the marginals.

The case of spatial Gibbs fields

A temporal multidimensional Gibbs process

The basic idea is to consider a spatial Gibbs field as a multidimensional Gibbs process.

Let us consider Z t = (Z (t,i) , i ∈ I), where I = {1, 2, • • • , m}, and

We take the notations z t = (z (t,i) , i ∈ I), z(t) = (z 1 , .., z t ) and z = z(T ).

Without loss of generality, we suppose that the distribution π of Z is a Gibbs distribution with translation invariant potentials Φ A k (•), k = 1, K associated