Isabelle Tellier

Iris Eshkol

Samer Taalab

Jean-Philippe Prost

POS-tagging for Oral Texts with CRF and Category Decomposition

The ESLO (Enquête sociolinguistique d'Orléans, i.e. Sociolinguistic Survey of Orléans) campaign gathered a large oral corpus, which was later transcribed into a text format. The purpose of this work is to assign morpho-syntactic labels to each unit of this corpus. To this end, we first studied the specificities of the labels required for oral data, and their various possible levels of description. This led to a new original hierarchical structure of labels. Then, since our new set of labels was different from any of those of existing taggers, which are usually not fit for oral data, we have built a new labelling tool using a Machine Learning approach. As a starting point, we used data labelled by Cordial and corrected by hand. We used CRF (Conditional Random Fields), to try to take the best possible advantage of the linguistic knowledge used to define the set of labels. We measure accuracy between 85 and 90, depending on the parameters.

Introduction

Morpho-syntactic tagging is essential to text analysis, as a preliminary step to any high level processing. Different reliable taggers exist for French, but they have been designed for handling written texts and are, therefore, not suited to the specificities of less "normalised" language. Here, we are interested in the ESLO 4 corpus, which comes from records of spoken language. ESLO thus presents specific features, which are not well accounted for by standard taggers.

Several options are possible to label transcribed spoken language: one can take a tagger initially developed for written texts, providing new formal rules let us adapt it to take into account disfluences [START_REF] Dister | De la transcription à l'étiquetage morphosyntaxique. Le cas de la banque de données textuelle orale VALIBEL[END_REF] [START_REF] Dister | De la transcription à l'étiquetage morphosyntaxique. Le cas de la banque de données textuelle orale VALIBEL[END_REF]); or one can adapt the transcribed corpus to the requirements of written language (Valli and Veronis, 1999 [START_REF] Valli | Étiquetage grammatical des corpus de parole : problèmes et perspectives[END_REF]). We have chosen a different methodological approach. Starting from the output of a tagger for written language, we have first defined a new tag set, which meets our needs; then, we have annotated a reference corpus with those new tags and used it to train a Machine Learning system.

For that kind of annotation task, the state-of-the-art technology for supervised example-based Machine Learning are the Conditional Random Fields (CRF). CRF is a family of recently introduced statistical models (Lafferty et al., 2001 [3], Sutton and McCallum, 2007 [4]), which have already proven their efficiency in many natural language engineering tasks (McCallum and Li, 2003 [START_REF] Mccallum | Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons[END_REF], Pinto et al., 2003 [6], Altun et al., 2003 [7], Sha and Pereira, 2003 [8]). Our experiments make use of CRF++ 5 , a free open-source library, developed by Taku Kado. We proceed with the testing of various strategies for decomposing the labels into a hierarchy of simpler sub-labels. The approach is original, in that it eases the learning process, while optimising the use of the linguistic knowledge that ruled the choice of intial labels. In that, we follow the procedure suggested by Jousse (2007 [9]), and Zidouni (2009 [10]).

In the following, Sect. 2 is dedicated to the presentation of our corpus and of the tagging process, focusing on the labelling problems raised by spoken language. After justifying the choice of a new tag set, we explain the procedure we have adopted for acquiring a sample set of correctly labelled data. In Sect. 3 we present the experiments we have carried out with CRF++, to learn a morpho-syntactic tagger from this sample. We show how the performance of the learning process can be influenced by different possible decompositions of the target labels into simpler sub-labels.

Oral Corpus and its Tagging

This section deals with the morpho-syntactic tagging of an oral corpus, and the difficulties that it causes to the tagger Cordial. The specificities of spoken language lead us to propose a new set of more suitable tags.

The morpho-syntactic Tagging of an Oral Corpus. The purpose of tagging is to assign to each word in a corpus a tag containing morpho-syntactic information about that word. This process can be coupled with stemming, to reduce the occurrence of a given word to its base form or lemma. The main difficulty of morpho-syntactic tagging is the ambiguity of words belonging to different lexical categories (e.g. the form portes in French is either a plural noun (doors) or the second person singular of present indicative or subjunctive of the verb porter (to carry): the tagger must assign the correct tag in a given context. Taggers usually also have problems with words which are not recognized by their dictionary: misspelled words, proper nouns, neologisms, compound words, . . . Tagging an oral corpus faces even more problems. Firstly, the transcriptions are usually not punctuated in order to avoid anticipating the interpretation (Blanche-Benveniste and Jeanjean, 1987 [START_REF] Blanche-Benveniste | Le Français parlé[END_REF]). Punctuation marks such as comma or full stop, and casing are typographical marks. The notion of sentence, mostly graphical, was quickly abandoned by linguists interested in speech. Studies on spoken language have also identified phenomena which are specific to speech, called disfluence: repeats, self-corrections, truncations, etc. Following (Blanche-Benveniste, 2005 [START_REF] Blanche-Benveniste | Les aspects dynamiques de la composition sémantique de l'oral[END_REF]), we believe that all these phenomena should be included in the analysis of language even if it raises processing issues. Elements, like hein, bon, bien, quoi, voilà, comment dire, (eh, well, what, how to say, . . . ) with a high frequency of occurrence in oral corpora, and without punctuation, can be ambiguous, because they can sometimes also be nouns or adjectives (as it is the case for bon, bien -meaning good). The currently existing tools for tagging are not suitable for oral, which is why this task is so difficult.

The Tagging by Cordial and its Limits. The Socio-Linguistic Survey in Orleans (Enquête Socio-Linguistique à Orléans, ESLO) is a large oral corpus of 300 hours of speech (approximately 4,500,000 words) which represents a collection of 200 interviews recorded in a professional or private context. This investigation was carried out towards the end of the Sixties by British academics in a didactic aim. The corpus is made up of 105 XML files generated by Transcriber, and converted to text format. Each file corresponds to a recording situation. Significant conventions of transcription are:

the segmentation was made according to an intuitive unit of the type "breathing group" and was performed by a human transcriber; -the turn-taking was defined by speaker changes; -no punctuation except exclamation and question marks; -no upercase letters except named entities; -word truncation is indicated by the dash (word-); -the transcription is orthographic.

The transcribed data was tagged by Cordial in order to have a reference corpus. This software was chosen for its reliability. As of today, it is one of the best taggers for French written language, with a wide range of tags, rich in linguistic information. The result of tagging is presented in a 3-column format: word, lemma and lexical category (POS), as exemplified in Table 1 200 tags encoding morphological information of different kinds such as gender, number or invariability for nouns and adjectives; distinction in modality, tense and person for verbs, and even the presence of aspirated 'h' at the beginning of words. However, the analysis of Cordial's outcome revealed a number of errors. The first group of errors includes "classical" errors such as the following ones.

Ambiguity: et vous êtes pour ou contre (and are you for or against) ⇒ {contre, contrer, VINDP3S} instead of {contre, contre, PREP3}. Proper nouns: les différences qu'il y a entre les lycées les CEG et les CES (the differences that exist among [types of secondary and high schools]) ⇒ {CEG, Ceg, NPMS} instead of {CEG, CEG, NPPIG4} and {CES, ce, DETDEM} instead of {CES, CES, NPPIG}. Locutions: en effet (indeed) ⇒ analysed in two separate lines, as opposed to a compound: {en, en, PREP}, then {effet, effet, NCMS} while it is an adverb.

We have also found errors, which are specific to oral data, as :

Truncation: by convention in ESLO, word truncation is indicated by the dash, which raises a problem for tagging by Cordial: on fait une ou deux réclam-réclamations (we make one or two complaints) ⇒ {réclam-réclamations, réclamréclamations, NCMIN5} instead of analysing the sequence in two separate units: {réclam-, reclam-, NCI 6 } and {réclamations, réclamation, NCFP} Interjection: Cordial does not recognize all the possible interjections present in oral corpora: alors ben écoutez madame (so uh listen madam) ⇒ {ben, ben, NCMIN). This phenomenon also presents a problem of ambiguity since, according to Dister (2007 [1, p. 350]): any form can potentially become an interjection. One, then, observes a grammatical re-classification (. . . ), the phenomenon whereby a word belongs to a grammatical class may, in speech, change. j'ai quand même des attaches euh ben de la campagne qui est proche quoi (PRI7) (I still have ties [euh ben] to the nearby countryside [quoi]) Repeat and self-correction: je crois que le ({le, le, PPER3S} instead of {le, le, DETDMS}) le ({le, le, DETDMS}) les saisons (I think that the the seasons)

Note, as well, a number of errors such as typos or spellings made by human transcribers. The transcription was not spell-checked.

New Choice of Tags. In order to adapt the tagging to our needs, we propose a number of modifications to the tag set. Those changes are motivated on the one hand by the reduction of the number of tags without loss of the necessary linguistic information, and on the other hand, by the need to adapt the tags to spoken language and to the conventions adopted for the transcription of our corpus. We present here a (non-exhaustive) list of modifications.

-New tags were introduced, such as MI (unknown word) for cases of truncation, and PRES (announcer) for phrases such as il y a, c'est, voilà (there is, this is, there it is), both very frequent in oral.

-A few tags, which are too detailed in Cordial, were simplified. For example, the set of tags marking the invariability of adjectives or nouns (masculine invariant in number, feminine invariant in number, singular invariant in gender, plural invariant in number and gender) were replaced by a single tag (invariable). The tags marking the possibility for the word to begin with an aspirated 'h' were removed. -In order to make the system more uniform, some tags were enriched. For example, indications about the gender and number were added to the demonstrative and possessive determiners for coherence purpose with other types, such as definite and indefinite determiners.

The morpho-syntactic tags often contain information of different kinds. They always mark information about the Part-Of-Speech. That basic information seems to be the easiest to acquire from dictionary lookup except, of course, in the case of lexical ambiguity. The tags generally include additional information from different linguistic dimensions: morphological: concerns the structure of a word as its type and number, the invariability for nouns, adjectives, pronouns and some determiners; syntactic: describes the function of words in the sentence and they relate with each other, e.g. coordination and subordination for conjunctions; semantic: related to the description of word's meaning such as feature of possessive, demonstrative, definite, indefinite or interrogative for the determiners.

In order to account for that extra information, we propose to structure the tags in 3 levels, called respectively L0 (level of POS tags), L1 (morphological level) and L2 (syntactic and semantic level). A sample of that hierarchical structure is illustrated in Fig. 1. As shown in Fig. 1, some tags: change on every level, including new information such as pronouns and determiners.

In addition to that hierarchical structure, other types of linguistic knowledge can be taken into account during tagging. According to inflectional morphology, a word is made up of a root and a sequence of letters, which often carry morphological information: in French, endings such as -ait, -ais, -e ,-es indicate the tense, gender, number, . . . . In inflectional morphology, those endings are called grammatical morphemes. When considering the root as the part shared by all the forms of a word, it is possible to extract these final sequences from the surface form in order to determine the morphological part of the tag which must be associated with this word. That linguistic knowledge can be exploited in order to improve the performance of a Machine Learning system, as we discuss it in the next section. The reference corpus contains 18,424 words, and 1723 utterances. This data was first tagged by Cordial, and then corrected semi-automatically, in order to make it meet our new tagging conventions. The hand processing was made by linguistic students as part of a 3-month internship.

Experiments

We now have a reference corpus, whose labelling was manually corrected and is considered as (nearly) perfect. It is, thus, possible to use it for training a Machine Learning system. As far as learning a tagger is concerned, the best performing statistical model is the one of Conditional Random Fields (CRF) (Lafferty et al., 2001 [3], Sutton and McCallum, 2007 [4]). We choose to work with it. In that section, we first briefly describe the fundamental properties of CRF, then present the experimental process, and finally we detail the results. Our goal is to maximise the use of the linguistic knowledge which guided the definition of our tag set, in order to improve the quality of the learned labels. In particular, we want to determine whether learning the full labels (i.e., those containing all the hierarchical levels of information) could be improved by a sequence of intermediate learning steps involving less information. Note that we do not rely on any dictionary, which would enumerate all the possible labels for a text unit.

CRF and CRF++. CRF are a family of statistical models, which associate an observation x with an annotation y using a set of labelled training pairs (x, y). In our case, each x coincides with a sequence of words, possibly enriched with additional information (e.g., if the words' lemmas are available, x becomes a sequence of pairs (word, lemma)), and y is the sequence of corresponding morpho-syntactic labels. Both x and y are decomposed into random variables.

The dependencies among the variables Y i are represented in an undirected graph. The probability p(y|x) of an annotation y, knowing the observation x is:

p(y|x) = 1 Z(x) c∈C ψc(yc, x) with Z(x) = y c∈C ψc(yc, x)
where C is the set of cliques (i.e. completely connected subgraph) over the graph, y c is the configuration taken by the set of random variables Y belonging to the clique c, and Z(x) is a normalization factor. The potential functions ψ c (y c , x) take the following form:

ψ c (y c , x) = exp k λ k f k (y c , x, c)
The functions f k are called features, each one being weighted by a parameter λ k . The set of features must be provided to the system, whose learning purpose is to assign the most likely values for each λ k according to the available valued data. Most of the time, function results are 0 or 1 (but they could also be real-valued).

In linear CRF, which are well-suited to sequence annotation, the graph simply links together the successive variables associated with the sequence elements. The maximal cliques of that kind of graph are, thus, the successive pairs (Y i , Y i+1 ). That model is potentially richer than the HMM one, and usually gives better results.

CRF++, the software that we are using, is based on that model. Features can be specified through templates, which are instanciated with example pairs (x, y) provided to the program. We kept the default templates provided by the library; they generate boolean functions using the words located within a twoword neighborhood around the current position, as exemplified in Ex. 1.

Example 1. In Table 1, the first column corresponds to the observation x, the third one to the annotation. Hence: x = "comment vous faites une omelette" 7 , y = ADV, PPER2P, VINDP2, PPER2P, DETIFS, NCFS. For a given position i identifying the clique (i, i+1), the template tests the values of Y s in the clique, and the values of X in position i, i -2, i -1, i + 1, i + 2. At position i = 3 we get the following feature f : if Y i = VINDP2 and Y i+1 = PPER2P and X i = 'faites' and X i-2 = 'comment' and X i-1 = 'vous' and X i+1 = 'vous' and X i+2 = 'une' then f = 1 else f = 0.

The template also generates simpler functions, where only the positions i, i -1, and i + 1 of X are tested, for example. With that example, we see that the disfluencies are directly taken into account in the model by the fact that they occur in the set of training examples provided to the learner.

Experimental Framework. For our experiments, the corpus was split in 10 subsets and we performed a 10-fold cross-validation. The features are mainly built from observations over words. We have also carried out experiments where the word lemma is supposed to be known. In order to enrich the data even more, we also relied on inflectional morphology, mentioned in Sect. 2:

1. the distinction between root and rest: the root is the string shared between the word and the lemma, while the rest is the difference between them; if word=lemma, by convention we note Rword=Rlemma=x, else word= Root+Rword and lemma=Root+Rlemma (where the symbol + denotes here the string concatenation); 2. the word tail: D n (word) = n last letters of the word; for instance, if word= 'marchant' and lemma='marcher' then Root='march', Rword='ant', Rlemma ='er' and D 2 (word)='nt'.

Reference Experiments. The reference experiments consist of learning the most detailed level (L2) directly. Six different tests were run, which we describe next. We denote by F eat (args) the features built from (args).

Test I F eat (word, lemma) : about 10,000,000 features produced; F1 = 0.86.

Test II F eat (word, lemma, Rword, Rlemma) ; 11,000,000 features; F1 = 0.88.

Test III If word=lemma we use D 2 (word) and D 3 (lemma), hence:

F eat (word, lemma, Rword|D 2 (word),Rlemma|D 3 (lemma)) ; 20,000,000 feat.; F1 = 0.82. Now, if the lemmas are unknown, we obtain the following:

Test IIIbis F eat (word, D 3 (word)) ; 8,000,000 features; F1 = 0.87;

Test IV Similar to III, but with D 3 everywhere:

F eat (word, lemma, Rword|D 3 (word), Rlemma|D 3 (lemma)) ; 20,000,000 feat.; F1 = 0.89.

Again, without relying on lemmas, we get:

Test IVbis F eat (word, D 3 (word), D 2 (word), D 1 (word)) ; 20,000,000 feat.; F1 = 0.88.

As expected, the richer the features, the better the results. Knowing the lemmas, for instance, increases the accuracy by 2 points in average. The downside is the increased cost timewise for the learning phase, caused by a much larger number of generated features.

Cascasde Learning. In order to exploit the knowledge contained in the labels -i.e., mainly their organisation in a 3-level hierarchical structure -we first learned each level independently, using the same test set (Test I to IVbis) as previously. The scores obtained are presented in Table 2. We observe that the coarser the levels in terms of how detailed the information is, the easier they are to learn. It can be explained by the reduced number of labels to be learned. Meanwhile, since each level of labels in the hierarchy depends on the previous one, one can hypothesise that using the results from the levels L j when learning Level L i (withj < i) may improve the results at L i . The purpose of the next set of experiments is to test that hypothesis: we say that the different hierarchical levels are learned in cascade, as in Jousse (2007 [START_REF] Jousse | Transformations d'abres XML avec des modèles probabilistes pour l'annotation[END_REF]) and Zidouni (2009 [10]). In the previous set of experiments, the best scoring tests are Test III and IV; as an attempt to improve those tests, we have designed Test V and VI as follows.

We denote by CRF(Li|feat(args)) the learning of level Li knowing the features based on args.

Test V (derived from Test III) word, lemma and D 3 (lemma) are used to generate the features for learning Level L0; then the result RL0 is used, with the same data, to learn Level L1; and so forth. The successive learning phases are given next.

-CRF(L0|feat(word, lemma,

D 3 (lemma))) → ResL0 -CRF(L1|feat(word, lemma, D 3 (lemma), ResL0)) → ResL01 -CRF(L1|feat(word, lemma, D 3 (lemma), ResL0, ResL01)) → ResL012
Test VI (derived from TestIV) This time, the initial features are generated with word, Rword, Rlemma, D 3 (word),D 3 (lemma). The successive learning phases are the following:

-CRF(L0|feat(word, Rword, Rlemma, D 3 (word),

D 3 (lemma))) → ResL0 -CRF(L0|feat(word, Rword, Rlemma, D 3 (word), D 3 (lemma), ResL0)) → ResL01 -CRF(L0|feat(word, Rword, Rlemma, D 3 (word), D 3 (lemma), ResL0, ResL01)) → ResL012
Level III IV V VI L0 0.94 0.94 0.94 0.94 L1 0.9 0.9 0.88 0.9 L2 0.82 0.89 0.87 0.89 As shown in Fig. 2, Test V and VI give good results, but not really better than the initial Test III and IV. Therefore, unfortunately, cascade learning does not seem to improve the results obtained in the reference experiments, where L2 is learned directly. That conclusion is confirmed by the experiments without lemmas, the outcome of which we do not detail. Next, we re-consider the way the information contained in the L2 labels is decomposed, in order to better learn those labels.

Learning by Decomposition and Recombination of Labels. We decompose the L2 labels into components, so that they can be learned independently.

We call label component a group of atomic symbols, which cannot all belong to the same label. Intuitively, those components correspond to the possible values for a linguistic feature, such as Gender or Number. Each of those components can be learned independently. However, some of them are still mutually exclusive: for example, Person and Gender can be grouped together since their values (respectively in {1, 2, 3} and {M, F }) never occur together. On the contrary, Gender and Number can not be grouped, since, for instance, the value 'F' may occur with 'S' or 'P' within the same label. We end up working with 4 components: G0 = POS, G1 = Genre ∪ Pers ∪ {ǫ}, G2 = Num ∪ {ǫ}, and G3 = Mode Tense ∪ Det Pro ∪ {ǫ}. with ǫ the empty string, neutral element for the concatenation. Each of these label subsets can now be learned independently by a specific CRF. In that case, the final label proposed by the system results from the concatenation of all the CRF outcomes. If we denote by • (dot) the concatenation operator, the cartesian product G0 • G1 • G2 • G3 generates every L2 label. But it also generates labels which are not linguistically motivated. For example, ADVMP = ADV • M • P • ǫ is meaningless, since an adverb is invariable. In order to avoid that problem, we have tested two different approaches. The first one consists of using a new CRF, whose features are the components learned independently. The second one consists of intoducing explicit symbolic rules in the concatenation process, in order to rule out the illegal combinations. Example rules are as follows:

-ADV, CONJCOO, CONJSUB and INT can only combine with ǫ -V can not combine with values of Det Pro -DET can not combine with values of Mode Tense Those rules exploit the fact that the POS category (i.e. the G0 component) is learned with strong enough confidence (F 1 = 0.94) to constrain the other sub-labels with which it may combine. We have carried out the tests presented below:

Expe. 1 CRF(G i |feat(word, lemma, D 3 (word))) → ResGi
We have also tested different versions where feature generation is achieved without lemma but with word tails instead (as in Test IVbis).

Expe. 2 CRF(G

i |feat(word, D 3 (word), D 2 (word), D 1 (word))) → ResbisGi Test VII CRF(L2|feat(word, Rlemma, ResG0, ResG1, ResG2, ResG3)) → ResL2
Test VIIbis Same as VII, but without lemmas: CRF(L2|feat(word, ResbisG0, ResbisG1, ResbisG2, ResbisG3)) → ResbisL2

Test VIII Here, the outcome from Test VII is replaced by symbolic combination rules using the results ResGi.

Test VIIIbis Same as VIII, except that the combination rules use ResbisGi. Note, as well, that the definition we provide of a specific set of labels prevents comparing our performances against those of other taggers.

Conclusion

In that paper, we have shown that it is possible to efficiently learn a morphosyntactic tagger specialised for a specific type of corpus. First, we have seen that the specificities of spoken language are difficult to enumerate. Instead of trying to rule them all, it is natural to rely on Machine Learning techniques. Our experiments all take the input data as they are, without filtering out any difficulties. Note that it is not possible to rigourously compare the performance achieved by Cordial with the performances reported here, since the target label sets are different. Yet, the performances of the best learned taggers seem comparable to those usually obtained by Cordial on oral corpora. The insentive of using CRF for that task is that it does not require many parameters to be set, and that the settings involved are flexible enough to integrate external linguistic knowledge. We have mostly used here our understanding of the labels in order to focus on learning sub-labels, which are simpler and more coherent. The performance would have also certainly been improved by the use of a dictionary of labels for each word, or each lemma, to specify features.

Finally, it seems quite difficult to still improve the quality of the learned labels by simply relying on the decomposition in simpler sub-labels. However, that strategy by decomposition is very efficient timewise, and the learning process has been greatly improved in that respect. It is also interesting to notice that the most efficient strategy relies on a combination between statistic learning and symbolic rules. Further works are going in that direction.

Fig. 1 .

 1 Fig. 1. Sample of the tags hierarchical structure

Fig. 2 .

 2 Fig. 2. Accuracy measures for Test III to VI

Example 2 .

 2 The labels in L = {NFS, NFP, NMS, NMP} come from the concatenation of elements in the sets {N } (Noun), {M, F } (Gender), and {S, P } (Number). All the four labels in L can be recombined by the cartesian product of three components: {N }•{M, F }•{S, P }, where • (dot) denotes the concatenation of sub-labels. A first option for building those components is to propose the following sets: -POS={ADJ, ADV, CH, CONJCOO, CONJSUB, DET, INT, INT, MI, N, PREP, PRES, P, PP, V} -Genre={M, F}; Pers={1, 2, 3}; Num={S, P} -Mode Tense={CON, IMP, SUB, IND, INDF, INDI, INDP, INF, PARP, PARPRES} -Det Pro={IND, DEM, DEF, POSS, PER, INT}

Figure 3 Fig. 3 .

 33 Figure 3 illustrates the two possible strategies for recombining the full labels, along with the results from learning each component independently (accuracy measures). Note that the component G2 is better learned without lemmas but

Table 1 .

 1 . Cordial uses about Example of tagging by Cordial.

	Word	Lemma	POS
	comment (how) comment ADV
	vous (you)	vous	PPER2P
	faîtes (make/do)	faire VINDP2P
	une (one/a)	un	DETIFS
	omelette (omelette) omelette NCFS

Table 2 .

 2 Accuracy measures when learning separately each of the hierarchical levels of labels.

	Level (num. of tags) Test I Test II Test III Test IV Test IIIbis Test IVbis
	L0 (16)	0.93 0.93	0.94	0.94	0.92	0.93
	L1 (72)	0.86 0.89	0.9	0.9	0.88	0.89
	L2 (107)	0.86 0.88	0.82	0.89	0.87	0.88

http://crfpp.sourceforge.net/


Jean-Philippe Prost
email: jean-philippe.prost@univ-orleans.fr

Lifo

Grammar Error Detection with Best Approximated Parse

In this paper, we propose that grammar error detection be disambiguated in generating the connected parse(s) of optimal merit for the full input utterance, in overcoming the cheapest error. The detected error(s) are described as violated grammatical constraints in a framework for Model-Theoretic Syntax (MTS). We present a parsing algorithm for MTS, which only relies on a grammar of well-formedness, in that the process does not require any extragrammatical resources, additional rules for constraint relaxation or error handling, or any recovery process.

Introduction

Grammar error detection is a crucial part of NLP applications such as Grammar Checking or Computer-Assisted Language Learning (CALL). The problem is made highly ambiguous depending on which context is used for interpreting, and thus pinpointing, the error. For example, a phrase may look perfectly fine when isolated (e.g. brief interview), but is erroneous in a specific context (e.g. in *The judge grants brief interview to this plaintiff, or in *The judges brief interview this plaintiff ). Robust partial parsing is often not enough to precisely desambiguate those cases. The solution we prescribe is to point out the error(s) as a set of violated (atomic) constraints of minimal cost, along with the structural context used for measuring that cost. Given an ungrammatical input string, the aim is then to provide an approximated rooted parse tree for it, along with a description of all the grammatical constraints it violates. For example, Figure 1 illustrates an approximated parse for an ill-formed sentence in French, and the error being detected in that context. Property Grammar [START_REF] Blache | Les Grammaires de Propriétés : des contraintes pour le traitement automatique des langues naturelles[END_REF] provides an elegant framework for that purpose. Most of the relevant approaches to robust knowledge-based parsing addresses the problem as a recovery process. More specifically, we observe three families of approaches in that respect: those relying on grammar mal-rules in order to specify how to correctly parse what ought to be ungrammatical [START_REF] Bender | Arboretum: Using a precision grammar for grammar checking in CALL[END_REF][START_REF] Foster | Real bad grammar: Realistic grammatical description with grammaticality[END_REF]; those relying on constraint relaxation according to specified relaxation rules [START_REF] Douglas | Towards Robust PATR[END_REF]; and those relying on constraint relaxation with no relaxation rules, along with a recovery process based on weighted parsing [START_REF] Fouvry | Constraint relaxation with weighted feature structures[END_REF][START_REF] Foth | Robust Parsing with Weighted Constraints[END_REF]. The first two are actually quite similar, in that, through their use of extra-grammatical rules, they both extend the grammar's coverage with a set of ought-to-beungrammatical utterances. The main drawback of those approaches is that when faced with unexpected input at best their outcome remains unknown, at worst the parsing process fails. With robust weighted parsing, on the other hand, that problem does not occur. The recovery process consists of filtering out structures with respect to their weights or the weights of the constraints being relaxed. However, these strategies usually can not discriminate between grammatical and ungrammatical sentences. The reason for that comes from the fact that grammaticality is disconnected from grammar consistency: since the grammar contains contradicting (universal) constraints, no conclusion can be drawn with regard to the grammaticality of a syntactic structure, which violates part of the constraint system. The same problem occurs with Optimality Theory. In a different fashion, Fouvry weighs unification constraints according to "how much information it contains". However, relaxation only seems possible for those unification constraints: error patterns such as word order, co-occurrence, uniqueness, mutual exclusion, . . . can not be tackled. The same restriction is observed in [START_REF] Vanrullen | Vers une analyse syntaxique à granularité variable[END_REF], though to a much smaller extent in terms of unrelaxable constraints.

What we would like is (i) to detect any type of errors, and present them as conditions of wellformedness being violated in solely relying on the knowledge of a grammar of well-formedness-as opposed to an error grammar or mal-rules, and (ii) to present, along-side the violated constraints, an approximated parse for the full sentence, which may explain which errors have been found and overcome. We propose here a parsing algorithm which meets these requirements.

Property Grammar

The framework we are using for knowledge representation is Property Grammar [START_REF] Blache | Les Grammaires de Propriétés : des contraintes pour le traitement automatique des langues naturelles[END_REF] (PG), whose model-theoretical semantics was formalised by [START_REF] Duchier | A Model-Theoretic Framework for Grammaticality Judgements[END_REF]. Intuitively, a PG grammar decomposes what would be rewriting rules of a generative grammar into atomic syntactic properties -a property being represented as a boolean constraint. Take, for instance, the rewriting rule NP → D N. That rule implicitely informs on different properties (for French): ( 1 (3) NP : △ N; (4) NP : N!; (5) NP : D ≺ N; (6) NP : N ⇒ D. These constraints can be independently violated. A PG grammar is traditionally presented as a collection of Categories (or Constructions), each of them being specified by a set of constraints. Table 1 shows an example of a category. The class of models we are working

» GEND 1 NUM 2 - D » GEND 1 NUM 2 - Table 1: NP specification in Property Grammar
with is made up of trees labelled with categories, whose surface realisations are the sentences σ of language. A syntax tree of the realisation of the well-formed sentence σ is a strong model of the PG grammar G iff it satisfies every constraint in G.

The loose semantics also allows for constraints to be relaxed. Informally, a syntax tree of the realisation of the ill-formed sentence σ is a loose model of G iff it maximises the proportion of satisfied constraints in G with respect to the total number of evaluated ones for a given category. The set of violated constraints provides a description of the detected error(s).

Parsing Algorithm

The class of models is further restricted to constituent tree structures with no pairwise intersecting constituents, satisfying at least one constraint. Since the solution parse must have a single root, should a category not be found for a node a wildcard (called Star) is used instead. The Star category is not specified by any constraint in the grammar.

We introduce an algorithm for Loose Satisfaction Chart Parsing (LSCP), presented as Algorithm 1. We have named our implementation of it Numbat. LSCP is based on the probabilistic CKY, augmented with a process of loose constraint satisfaction. However, LSCP differs from CKY in various respects. While CKY requires a grammar in Chomsky Normal Form (CNF), LSCP takes an ordinary PG grammar, since no equivalent of the CNF exists for PG. Consequently, LSCP generates n-ary structures. LSCP also uses scores of merit instead of probabilities for the constituents. That score can be optimised, since it only factors through the influence of the constituent's immediate descendants.

Steps 1 and 2 enumerate all the possible and The key is a hash-code of a combination of constructions, used for fetching the constraints this combination is concerned with. ing a category judgement for a configuration, on the basis of which constraints are satisfied and violated, in order to label its root. The process is a simple table lookup, the grammar being indexed by properties. Step 5 then memoises the optimal sub-structures for every possible category. Note that the uniqueness of the solution is not guaranteed, and there may well be many different parses with exact same merit for a given input utterance.

Should the current cell in the chart not being populated with any constituents, a preferred forest of partial parses (= Star category) is used instead. The preferred forest is constructed on the fly (as part of buildConfigurations); a pointer is maintained to the preferred configuration during enumeration. The preference goes to: (i) the constituents with the widest span; (ii) the least overall number of constituents. This translates heuristically into a preference score p F computed as follows (where F is the forest, and C i its constituents): p F = span • (merit(C i ) + span). In that way, LSCP always delivers a parse for any input. The technique is somehow similar to the one of [START_REF] Riezler | Parsing the Wall Street Journal using a Lexical-Functional Grammar and Discriminative Estimation Techniques[END_REF], where fragment parses are allowed for achieving increased robustness, although their solution requires the standard grammar to be augmented with a fragment grammar.

Evaluation

In order to measure Numbat's ability to (i) detect errors in an ungrammatical sentence, and (ii) build the best approximated parse for it, Numbat should, ideally, be evaluated on a corpus of both wellformed and ill-formed utterances annotated with spannnig phrase structures. Unfortunately, such a Gold Standard is not available to us. The development of adequate resources is central to future works. In order to (partially) overcome that problem we have carried out two distinct evaluations: one aims to measure Numbat's performance on grammatical sentences, and the other one on ungrammatical sentences. Evaluation 1, whose results are reported in Table 2, follows the protocol devised for the EASY evaluation campaign of parsers of French [START_REF] Paroubek | EASY: An Evaluation Protocol for Syntactic Parsers[END_REF], with a subset of the campaign's corpus. For comparison, Table 3 reports the performance measured under the same circumstances for two other parsers: a shallow one [START_REF] Vanrullen | Vers une analyse syntaxique à granularité variable[END_REF]) also based on PG, and a stochastic one [START_REF] Vanrullen | Constraint-Based Parsing as an Efficient Solution: Results from the Parsing Evaluation Campaign EASy[END_REF]. The grammar used for that evaluation was developed by [START_REF] Vanrullen | Vers une analyse syntaxique à granularité variable[END_REF]. Evaluation 2 was run on a corpus of unannotated ungrammatical sentences [START_REF] Blache | Acceptability Prediction by Means of Grammaticality Quantification[END_REF], where each of the ungrammatical sentences (amounting to 94% of the corpus) matches a controlled error pattern. Five expert annotators were asked whether the solution trees were possible and acceptable syntactic parses for their corresponding sentence. Specific instructions were given to make sure that the judgement does not hold on the grammatical acceptability of the surface sentence as such, but actually on the parse associated with it. For that evaluation Van-Rullen's grammar was completed with nested categories (since the EASY annotation scheme only has chunks). Given the nature of the material to be assessed here, the Precision and Recall measurements had to be modified. The total number of input sentences is interpreted as the number of predictions; the number of COMPLETE structures is interpreted as the number of observations; and the number of structures evaluated as CORRECT by human judges is interpreted as the number of correct solutions. Hence the following formulations and scores: Precision=CORRECT/COMPLETE=0.74; Recall=CORRECT/Total=0.68; F=0.71. 92% of the corpus is analysed with a complete structure; 74% of these complete parses were judged as syntactically correct. The Recall score indicates that the correct parses represent 68% of the corpus. In spite of a lack of a real baseline, these scores compare with those of grammatical parsers.

Conclusion

In this paper, we have proposed to address the problem of grammar error detection in providing a set of violated syntactic properties for an illformed sentence, along with the best structural context in the form of a connected syntax tree. We have introduced an algorithm for Loose Satisfaction Chart Parsing (LSCP) which meets those requirements, and presented performance measures for it. Future work includes optimisation of LSCP and validation on more appropriate corpora.

Figure 1 :

 1 Figure 1: Approximated parse for an erroneous French sentence (the Noun 'entretien' requires a Determiner).

  ) NP has a D child; (2) the D child is unique; (3) NP has an N child; (4) the N child is unique; (5) the D child precedes the N child; (6) the N child requires the D child. PG defines a set of axioms, each axiom corresponding to a constraint type. The properties above are then specified in the grammar as the following constraints: (1) NP : △ D; (2) NP : D!;

  obligation : NP: △(N ∨ PRO) uniqueness : NP: D! : NP: N! : NP: PP! : NP: PRO! linearity : NP: D ≺ N : NP: D ≺ PRO : NP: D ≺ AP : NP: N ≺ PP requirement : NP: N ⇒ D : NP: AP ⇒ N exclusion : NP: N PRO dependency : NP: N

  Algorithm 1 Loose Satisfaction Chart Parsing / * Initialisation * / Create and clear the chart π: every score in π is set to 0 / * Base case: populate π with POS-tags for each word * / for i ← 1 to num words for (each POS-category T of wi) if merit(T ) ≥ π[i, 1, T ] then

	Create constituent w T i , whose category is T
	π[i, 1, T ] ← {w T i , merit(w T i )}
	/ * Recursive case * /
	/ * Step 1: SELECTION of the current reference span * /
	for span ← 1 to num words
	for offset ← 1 to num words -span + 1
	end ← offset + span -1
	K ← ∅
	/ * Step 2: ENUMERATION of all the configurations * /
	for (every set partition P in [offset, . . . , end])
	K P ← buildConfigurations(P)
	K ← K ∪ K P
	/ * Step 3: CHARACTERISATION of the constraint system from the grammar * /
	for (every configuration A ∈ K P )
	χ A ← characterisation(A) / * Step 4: PROJECTION into categories * /
	/ * C A is a set of candidate constituents * /
	C A ← projection(χ A )
	checkpoint(C A )
	/ * Step 5: sub-
	sets of contiguous elements. Step 3 evaluates the
	constraint system, using a configuration as an as-
	signment. The characterisation process is imple-
	mented with Algorithm 2. Step 4 consists of mak-
	Algorithm 2 Characterisation Function
	for (mask ∈ [1 . . . 2 n -1])
	key ← applyBinaryMask(A, mask)
	if (key is in the set of indexes for G) then
	/ * Properties are retrieved from the grammar, then evaluated * /
	S ← G[key].getProperties()
	χ A ← evaluate(S) / * Projection Step: fetch the categories to be projected * /
	C A ← G[key].getDominantCategories()
	return χ A , C A

MEMOISATION of the optimal candidate constituent * / for (every candidate constituent

x ∈ C A , of construction C) if merit(x) ≥ π[offset, span, C] then π[offset, span, C] ← {x, merit(x)} if π[offset, span] = ∅ then π[

offset, span] ← preferred forest in K legal configurations of optimal sub-structures already stored in the chart for a given span and offset. At this stage, a configuration is a tree with an unlabelled root. Note that Step 2 actually does not calculate all the set partitions, but only the legal ones, i.e. those which are made up of function characterisation(A = c1, . . . , cn : assignment, G: grammar) returns the set of evaluated properties relevant to A, and the set of projected categories for A. / * For storing the result characterisation: * / create and clear χ A [property]: table of boolean, indexed by property / * For storing the result projected categories: * / create and clear C A : set of category / * For temporarily storing the properties to be evaluated: * / create and clear S: set of property

Table 3 :

 3 Comparative EASY scores

Acknowledgement

Partly funded by ANR-07-MDCO-03 (CRoTAL).


Philippe Blache
email: blache@lpl-aix.fr

Jean-Philippe Prost
email: jean-philippe.prost@lpl-aix.fr

A Quantification Model of Grammaticality

The traditional binary notion of grammaticality is more and more often replaced by intermediate levels of acceptability, also called gradience. This paper aims to provide a numerical account of syntactic gradience. It introduces and investigates a numerical model with which acceptability can be predicted by factors derivable from the output of a parser. Its performance is compared to other experiments, and the fit of each model is evaluated. Our model shows a good correlation with human judgement of acceptability.

Introduction

Grammaticality is not binary (see [START_REF] Chomsky | The Logical Structure of Linguistic Theory[END_REF]) but rather a scale phenomenon: some sentences are judged as more grammatical than some others. This question has been recently described in terms of gradience ([Pullum01], [START_REF]Gradience in Grammar: Generative Perspectives[END_REF], [START_REF] Aarts | Syntactic Gradience. The nature of Grammatical Indeterminacy[END_REF]) and replaces grammaticality by intermediate levels of acceptability. Gradience phenomena have different sources. One is the violation of rules or constraints of a given language. These rules playing a more or less important role in the linguistic structure, it is possible to grade them, as it is done in probabilistic approaches (see [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]) or, in a more theoretical perspective, in the Optimality Theory [START_REF] Prince | Optimality Theory: Constraint Interaction in Generative Grammars[END_REF]). As a side effect, grading the syntactic properties makes it possible to explain the differences in acceptability judgements by human. For example, the repetition of a determiner as in (1a) can be considered as less problematic than a problem of word order as in (1b):

(1) a. Buildings burn in the the Kenyan town of Eldoret.

b. The adopted board the regulations.

Another source of gradience in the evaluation of grammaticality comes from the syntactic structure itself. A same constraint violation is more or less acceptable according to its context or its location in the structure. For example, (2b) seems to be more acceptable than (2a). In both cases, the same linearity constraint is violated. The difference comes from the fact that the constituent affected by the violation is more deeply embedded in (2b) than in (2a). In the second sentence, the acceptability judgment is more affected by parsing difficulty than constraint violation.

(2) a. Paul phoned father his.

b. Paul came back into the house that was built by father his.

This example illustrates the fact that a violation can be, to a certain extent, balanced by the context, or more generally by information born by other domains, including prosody or pragmatics.

In this paper we propose a model for syntactic gradience,which enables quantifying the phenomenon. This paper is organised in three parts: we first propose to make precise the notion of gradience, its theoretical description and what are the needs for its quantification. In the second section we introduce a model, which is a refinement of the one described in [START_REF] Blache | Acceptability Prediction by Means of Grammaticality Quantification[END_REF]. In the last part, we validate the model using a parser's output. The results are evaluated first by comparison with those of a psycholinguistic experiment, then over a large corpus of unrestricted text.

Linear Optimality Theory

Several experiments have shown the effect of constraint violation on grammaticality. In particular, preliminary works by [START_REF] Legendre | Harmonic Grammar -A Formal Multi-level Connectionist Theory of Linguistic Well-formedness: Theoretical Foundations[END_REF] (anticipating Optimality Theory) have proposed to quantify this effect. More recently, [START_REF] Keller | Gradience in Grammar. Experimental and Computational Aspects of Degrees of Grammaticality[END_REF] explored this question through in-depth description of different constructions. This work showed in particular the cumulativity effect, that led to the Linearity Hypothesis indicating that the "grammaticality of a structure is proportional to the weighted sum of the contraint violations it incurs". Starting from this hypothesis, Keller elaborates the Linear Optimality Theory (see [START_REF] Keller | Linear Optimality Theory as a Model of Gradience in Grammar[END_REF]). Linearity makes it possible to give to the notion of harmony a particular definition: the harmony of a structure it the opposite of the sum of the violated constraint weights. The grammaticality of different structures can be then evaluated and compared. The following figure, taken from [START_REF] Keller | Linear Optimality Theory as a Model of Gradience in Grammar[END_REF], illustrate the process. It shows 4 different candidate structures (S 1 to S 4 ) and three different constraints (C 1 , C 2 , C 3 ), with the respective weights 4, 3, and 1. Constraint violations are indicated by *. The figure gives the harmony of the different structures.

C1 C2 C3 Structure 4 3 1 Harmony S1 * * -4 S2 * ** -5 S3 * -1 S4 * -4

Fig. 1. Structures, constraint violations and harmony

This formal examples illustrates the cumulativity effect: the multiple constraint violation of the structure S 2 makes its harmony worst than that of S 4 in spite of the fact that this last structure violates a strongest constraint. Moreover, the harmony values show that S 1 and S 4 are at the same level in terms of violation weights, in spite of the fact that they violate different types and number of constraints.

The structure hierarchy is then S 3 > {S 1 , S 4 } > S 2 (where the hierarchy in classical OT would be S 3 > S 1 > S 2 > S 4 ). Several experiments (see [START_REF] Keller | Gradience in Grammar. Experimental and Computational Aspects of Degrees of Grammaticality[END_REF]) has shown the validity of the linearity hypothesis.

However, several questions can not be addressed in this framework. First, this view of cumulativity is purely quantitative and does not take into consideration the structure itself. Concretely, it would not predict any acceptability variation between (2a) and (2b).

Second, OT was designed in order to compare several structures by means of constraint violation. Subsequently, two structures violating the same constraint can not be discriminated. The following example illustrates this phenomenon. Both NP violate the same constraint (gender agreement violation between the noun and the past participle). However, the same violation embedded into a relative clause in (3b) renders the NP more acceptable than (3b).

(3) a. La maison détruit par l'explosion

The house-fem destroy-PPast-masc by the explosion b. La maison qui a été détruit pas l'explosion

The house-fem that has been destroy-PPast-masc by the explosion Last, and more importantly, it is important to compare utterances that do not violate any constraint without being at the same level in terms of acceptability. In the following examples, the different sentences do not bring the same quantity of information. The different constructions instantiate differently the direct object. The first sentence is a cleft, there is a strict an unambiguous interpretation of the NP cleft as a direct object, the function being marked by the accusative mark of the relative pronoun "que". The example (5b) is a dislocation with a resumptive accusative pronoun "la", possibly referring to the dislocated NP. Finally, the last sentence is also a kind of dislocation, without any coreference phenomenon, the status of the extracted NP being ambiguous (direct object, vocative, etc.) (4) a. C'est Marie que je supporte pas.

It is Mary that-Acc I can't stand. b. Marie je la supporte pas Mary I can't stand her. c. Marie je supporte pas.

Mary I can't stand.

This example are graded: the first example is unambiguous because of the weight of its syntactic information: several morpho-syntactic and syntactic constraints are satisfied there. The second example contains less information, it is ambiguous (dislocation vs. vocative interpretation). In this case, the only visible relation concerns the possible agreement between the NP and the embedded clitic. Finally, the last example is even more ambiguous: Marie can receive a vocative, an accusative or even a dative interpretation there, without any morphology or syntactic mark.

These last examples show the necessity of taking into account, on top of the violated constraints, also the satisfied one: the quantity and the weight of satisfied constraints can play a role, as the violated on, in the ranking process.

Property Grammars

The Property Grammars (PG) approach [START_REF] Blache | Gradience, Constructions and Constraint Systems[END_REF] is purely constraint-based: all syntactic information is represented by means of constraints; no external device such as the Gen function in OT or the generation of the dependency network in Constraint Dependency Grammar [START_REF] Maruyama | Structural Disambiguation with Constraint Propagation[END_REF] is required. Several constraint types are used: Constituency, Uniqueness, Precedence, Obligation, Requirement and Exclusion. They can be specified in terms of constraints over directed graphs, as presented in figure (2).

-Const(A, B) : (∀x, y)[(A(x) ∧ B(y) → x y] Classical definition of constituency, represented by the dominance relation indicating that a category B is constituent of A. -U niq(A) : (∀x, y)[A(x) ∧ A(y) → x ≈ y]
If one node of category A is realized, there cannot exists other nodes with the same category A. Uniqueness stipulates constituents that cannot be repeated in a given construction.

-

P rec(A, B) : (∀x, y)[(A(x) ∧ B(y) → y ≺ x)]
This is the linear precedence relation: if the nodes x and y are realized, then y cannot precedes x -Oblig(A) : (∃x)(∀y)[A(x) ∧ A(y) → x ≈ y] There exists a node x of category A and there is no other node y of the same category. An obligatory category is realized exactly once.

-Req(A, B) : (∀x, y)[A(x) → B(y)] If a node x of category A is realized, a node y of category B has too. This relation implements cooccurrence restrictions.

-Excl(A, B) : (∀x)( ∃y)[A(x) ∧ B(y)] When x exists, there cannot exist a sibling y. This is the exclusion relation between two constituents.

Fig. 2. Constraint types in PG

The following example illustrates some constraints describing the NP and the AP (in which a dependency constraint has been added):

Cx_NP : Prec(Det, N) ∧ Oblig(N) ∧ Req(N, Det) ∧ Excl(N, Pro) ∧ Dep(Det, N) ∧ Dep(AP, N) Cx_AP : Prec(Adv, Adj) ∧ Oblig(Adj) ∧ Dep(Adv, Adj)
A grammar is then a set of constraints. Parsing an input consists of evaluating this constraint system for a given assignment (i.e. the set of categories corresponding to the input words). The outcome is a description of the input, which is made of the set of the evaluated constraints. Depending on the form of the input this set may contain both satisfied and violated constraints.

In PG constraints thus play a double role (as it is the case in constraint programming): they can rule out structures as well as instantiate values. Such an approach is well-suited to modeling gradience because the constraints are independent from one another. Indeed the basic assumptions in PG, unlike in OT, stipulate that constraints are unranked, local and violable: Unranked : A limited set of constraint types is used, each one with its own operational semantics. A constraint bears information of a unique type, representing a single and homogeneous piece. A constraint is thus atomic and can be evaluated independently from the other ones. Subsequently, by being mutually independent and never specified with respect to others. The weighting mechanism used in PG is not an order relation over the set of constraints, but a property specific to each constraint. Violable: Allowing constraint violation is a pre-requisite when dealing with partial or non-canonical inputs. In PG, all constraints are violable, but not necessarily. In OT, as in Weighted CDG (see [START_REF] Schröder | Natural Language Parsing with Graded Constraints[END_REF]), the number and the type of constraint violations is used to compare two structures. Violation is then necessary, and no optimal candidate can be selected when all constraints are satisfied. In PG, constraint violation is not required; it only introduces flexibility. Local : Universality is not a required property of PG. On the contrary, all constraints are local to a construction. It is an important difference with OT, not only theoretically, but also in the way of designing and using constraints. As indicated above, OT can only compare two structures with respect to constraint violation. It explains the fact that constraints must be specified in a very general and imperative way: the more general a constraint is, the more frequently it is violated. Universality must then be understood in OT as a mechanism which favors constraint violation. In PG, no universality is required; constraints can be specified at any level.

A Computational Model for Syntactic Gradience

The existing accounts of gradience previously mentioned rely on several properties:

-Constraint violation: this is a pre-requisite. Constraints must be be defeasible in order to describe any kind of input, whatever its form. -Constraint weighting: a comparison necessarily relies on the possibility of measuring the impact of the different constraints (see [START_REF] Foth | Parsing Unrestricted German Text with Defeasible Constraints[END_REF]). -Cumulativity: the effect of constraint violation was shown to be cumulative [START_REF] Keller | Gradience in Grammar. Experimental and Computational Aspects of Degrees of Grammaticality[END_REF].

However, these properties do not capture all phenomena that have been presented in the previous section. First, we have to explain the effects of a relative counterbalance between satisfied and violated constraints: constraint violation can be in some cases attenuated by the importance of satisfied constraints. Moreover the form of the syntactic structure (flat or deep) and the location of constraint violation in the structure also have importance (cf. examples 3 and 4). Thus we propose to complete the list of properties needed to describe gradience by the following ones:

-Constraint counterbalance: cumulativity must take into account both violated and satisfied constraints. -Violation position: the embedded level of the violation site in the syntactic structure carries consequences on acceptability.

An approach integrating these different properties offers, on top of a precise description of gradience, the possibility of calculating an index for any input, and quantifying, at least partially, its grammaticality. In the next section we detail and organise the basic information on top of which our model is built.

Basic information

in this section we present, in the form of different postulates, the kind of information required to build a computational model of gradience.

Failure Cumulativity As in other approaches, we postulate that acceptability is impacted by the amount of constraints it violates. We note N - c the amount of constraints violated by the constituent c (this factor corresponds to cumulativity in LOT).

Success Cumulativity Gradience is also affected by successful constraints. That is, an utterance acceptability is impacted by the amount of constraints it satisfies. We postulate that some form of interaction between satisfied and violated constraints contributes to a gradient of acceptability. We note N + c the amount of constraints satisfied by the constituent c, and E c = N + c + N - c . Constraint Weighting We postulate that constraints are weighted according to their influence on acceptability. The question of whether such weights are proportional to the importance of either constraint success or failure is addressed in assuming that a given constraint is of same relative importance either way in absolute value. We note W + c (respectively W - c ) the sum of the weights assigned to the constraints satisfied (respectively violated) by the constituent c.

A weight may be of different scope and granularity. The scope has to do with how widely a weight applies (to a constraint type or to an individual constraint). Granularity concerns the level a weight applies at (the grammar vs. the construction level). Scope and granularity can then be combined in different ways: all constraints from the same type at the grammar level, or all constraints from the same type at the constituent level, or individual constraints at the constituent level, or individual constraints at the grammar level-the difference between the last two possibilities assuming that a same constraint may occur in the specification of more than one category. Although the more fine-grained and the narrower the scope, the more flexible and accurate the influence on gradience, a too fine granularity and a too narrow scope (as in [START_REF] Schröder | Natural Language Parsing with Graded Constraints[END_REF]) are also quite complex to manage. Therefore, we opted for a fair compromise, where the weighting scheme is restricted to the constraint types at the grammar level, which means that all constraints from the same type in the grammar are assigned same weight. For examples, all constraints of linearity (i.e. word order) are weighted 20, all constraints of obligation (i.e. heads) are weighted 10, and so on. Constructional Density Acceptability is also impacted by the density of the constituent structure (i.e., the quantity of information born by the structure). This notion is measured by the amount of constraints specifying a category in the grammar. We note T C the total amount of constraints specifying the category C of the constituent c. The underlying idea is to balance constraint violations by the amount of specified constraints: without such a precaution one violation in a rather non-complex construction, such as AP-only specified by 7 constraints in our grammar-would be proportionally much more costly than one violation in a rather complex construction, such as NP-specified by 14 constraints. Propagation Acceptability also depends on that of its nested constituents. Therefore, we postulate that acceptability is propagated in the constituent structure through the relationship of dominance. We note Z c the number of nested constituents in c.

Constraint violation affects both realization, but in a lesser extent when the violation is deeply embedded (example 5b). Subsequently the models we investigate are recursive functions of their constituents' score.

Rating Models

A rating model for gradience aims to place an item along a scale by assigning it a score (rate).

Scoring Terms

The various scoring components presented here aim to capture the factors postulated above. Each component is meaningful as such, but not sufficient when considered alone. Satisfaction/Violation Ratio The SRatio + c (resp. VRatio - c ) is defined for the constituent c as follows:

+ c = N + c E c - c = N - c E c
The SRatio and violation ratio (VRatio) capture the postulates of Success and Failure Cumulativity respectively.

Completeness Index

The Index of Completeness for the constituent c of category C is defined as the following ratio, T being the total number of constraints describing the category in the grammar:

E c = E c T C
This score contributes to implement the postulate of Constructional Density, which suggests that the complexity of a constituent influences its acceptability.

Quality Index

The Index of Quality for the constituent c is defined as the following ratio:

W c = W + -W - W + + W -
The quality of a constituent implements the postulate of Constraint Weighting, which suggests that all constraints do not have same importance with respect to acceptability, and therefore must be weighted accordingly.

Precision Index

The Index of Precision for the constituent c is defined as the following ratio:

P c = k • W c + l • + c + m • E c
These adjustment coefficients (k, l, m) are used as variable parameters for tuning up the model.

We observed that the SRatio in use in the Precision score seems to overemphasise the role of success cumulativity, that is, the role of the successful constraints characterising a constituent. Therefore, we define an index of antiprecision, where the SRatio term in the precision index is replaced by the VRatio as a negative term. Anti-Precision Index

We define the Index of Anti-Precision for the constituent c as the following ratio:

P c = k • W c -l • - c + m • E c
Compared to the precision score, the anti-precision rather emphasises the factor of Failure Cumulativity.

Rating Functions A rating function combines different scoring terms into a single score. Among the numerous functions investigated, the following ones more particularly draw our attention for the significance of their results. Grammaticality Index

The Index of Grammaticality (g) for the constituent c is defined recursively as follows (where c i is a nested constituent of c):

g c = P c • g ci = P c • Zc i=1 g ci Z c
Next to the g-model we define below a new model, in order to run a comparative investigation of the two. The index of coherence is similar to the one of grammaticality, except that it relies on anti-precision rather than precision. Coherence We define the Coherence of a constituent c recursively as follows:

γ c = P c • γ ci = P c • Zc i=1 γ ci Z c
A comparison with LOT We have seen that cumulativity makes it possible in LOT to rank the structures with respect to their constraint violation. In the figure (3), we can compare the ranking by LOT with the obtained by our model. We can see that our ranking makes it possible to precise the result of LOT in providing an intermediate ranking between S 1 and S 4 . As expected, S 4 satisfying more constraints than S 1 , its precision index is higher. The following table recapitulates the rankings obtained by the different models (OT, LOT and GP) :

OT: S 3 > S 1 > S 2 > S 4 LOT: S 3 > {S 1 , S 4 } > S 2 GP: S 3 > S 4 > S 1 > S 2

Experimental Validation

We investigate to what extent the models of syntactic gradience presented above fit acceptability judgement by human standards.

Psycholinguistics experiment

[Blache06a] reports an experiment set up with psycholinguists. It shows a correlation between the Grammaticality Index (GI) (γ-model, above) and acceptability judgements provided by subjects.

The experiment relies on a set of sentences in which constraint violation was controlled. 20 types of sentence were designed, in which at most two constraints are violated. Several base sentences were created, each one generating the 20 types. As a result, 60 sentences from the different types were presented for evaluation to 44 subjects. The subjects were asked to rate the sentences, using Estimation (see [START_REF] Bard | Magnitude Estimation of Linguistic Acceptability[END_REF]). Next to this evaluation, GIs were calculated semi-automatically for each sentence: a generic syntactic structure (i.e. a syntactic tree) was associated to the phrase types, together with its characterisation (i.e. the set of satisfied and violated constraints) of each constituent. Figure (2) shows example sentences along with their GI.

The subjects' judgements were then compared to a rating relying on grammaticality indexes. A very good correlation (coefficient ρ 1 = 0.76) was observed between GI and acceptability judgement. An even better correlation with a coefficient ρ 2 = 0.87 is reported on a smaller sample of corrected data.

Computational Validation

For the work we present here we have experimented the two models (g and γ) in using the output from parsers based on PG. We have tested two different parsers, both robust: the first one is a chart parser using dynamic programming [START_REF] Prost | Numbat: Abolishing Privileges when Licensing New Constituents in Constraint-Oriented Parsing[END_REF], and is a direct interpretation of PG. It explores the entire search space, and relies on constraint satisfiability in order to build the set of structures. The second parser [START_REF] Blache | A Robust and Efficient Parser for Non-Canonical Inputs[END_REF] is non-deterministic and relies on control heuristics consisting in selecting construction types by means of precedence and constituency constraints (corresponding to a left-corner like strategy). The parsers using different techniques, strategies and level of analyses, they may build different solutions for the same input (especially due to the non-determinism of one of them).

Both parsers show comparable results with respect to gradience quantification (described in this section). The robust parser has been used in the evaluation over the large corpus (next section). The first evaluation, presented here, consists of replicating automatically the experiment described in the previous section. The goal is to show a correlation between the predictions from the model and the subjects' assessment.

We progressively tune up the models by assigning values to the different parameters (i.e. adjustment coefficients and constraint weights). The problem consists of finding out the right order of magnitude among the different parameters in order to obtain the best possible correlation with the values of acceptability. Different combinations were attempted. A sample of the correlations obtained is reported in table 1. The best correlation (ρ = 0.5425) is obtained for record 17, for the γ-model. The scatter plot from fig. 5 illustrates how the γ-model fits acceptability judgement. The constraint weights are ranked wu < wd < wr < we < wo < wl. It is important to emphasise that unlike in [START_REF] Keller | Gradience in Grammar. Experimental and Computational Aspects of Degrees of Grammaticality[END_REF], the constraints are not only ranked according to how much unacceptability they entail, but according to how important they are in absolute value with respect to acceptability.

Whatever the combination of parameters, γ always outperforms g, which confirms that this latter model is over-emphasising the role success cumulativity compared to the role of failure cumulativity.

The best performing scheme of parameters (rec. 17) grants a great deal of importance to Linearity (a factor 10 between wl = 20 and the minimum wu = 2, and a factor 2 between wl and its next follower wo = 10), then to Obligation (a factor 5 between wo = 10 and wu, and a factor 2 between wo and it very next follower we = 5). Then follow the remaining weights, ranging over [2 . . . 5]. This observation of two constraint types (namely Linearity and Obligation) on one hand, and the other ones on the other hand, tends to confirm the hard vs. soft dichotomy discussed by Keller.

Reduced data sample from the psycholinguistics experiment:

In order to perform a more accurate comparison between our results and that reported in [START_REF] Blache | Acceptability Prediction by Means of Grammaticality Quantification[END_REF], we ran a series of experiments using the same data sample, which is a subset of the full corpus. The best correlation (rec. 4) is obtained for the same parameter scheme as the best one from table 1, but surprisingly this time g outperforms the other two models. It confirms the crucial influence of Linearity on acceptability, but the roles of Uniqueness and Obligation is still unclear, though they are seemingly preponderant.

This first evaluation confirms the validity of our gradience model in showing a strong correlation with subjects predictions. Moreover, and this is the most important result, these predictions have been obtained automatically (at the difference with [START_REF] Blache | Acceptability Prediction by Means of Grammaticality Quantification[END_REF]), which opens the possibility of large scale experimentation, as presented in the next section.

Large Corpus Validation

We ran our model on a large French corpus, made from different sources: newspapers (184,367 words), spontaneous spoken language (14,065 words) and radio broadcasts transcriptions (84,685 words).

Some general figures can be given. Figure (1) illustrates the (unsurprising) difference between oral and written text: we observe that a greater proportion of sentences in oral production with low grammaticality index. As illustrated in figure (1), the mean index for spoken corpora is 2.46 whereas that of written is 3.36. What is more interesting is the repartition of the index values. There are only few differences between the two types: low and high index values are very similar, which means that some written sentences have a very low grammaticality index whereas some spoken (including spontaneous) can be very high.

As for our postulates, these results confirm the relevance of success cumulativity. This effect is illustrated in the following examples (from the corpus): the longer sentence (6) obtains a higher score than the short one.

(5) j'aime la cuisine (2,1385) I like cooking (6) donc c'est pas évident parce qu'il y a des jours où il y a pas de boulot il y a des jours où il y a du boulot comme partout (6,7266)

So it is not easy because there are days where there is no work there are days where there is work, like everywhere

A the corpus scale, we can illustrate this phenomenon in correlating grammaticality index with sentence size. The following figure shows the repartition of sentences with respect to the size. The average of the indexes in function of size match the curve ρ = ln(size).

In other words, as expected, the number of words can increase the grammaticality index level. Again, as observed in other works, cumulativity remains less important than the importance (i.e. the weight) of violated constraints. This aspect is illustrated in the following examples: a precedence constraint has been violated in (8), explaining the lower score than in (7):

(7) des foyers genre foyers ce qu'on appelle foyers de jeunes filles ou non mixte quoi (0,8089)

Boarding houses sort of boarding houses what is called boarding houses for girls or not mixed like (8) non ça m'a fait vraiment pas mal cogiter mais mais bien quoi c'est (-1,201)

No it really made me think hard but but right that's

Other assumptions can be confirmed by a detailed analysis of the results. At this level, we can see that most of constraint violation concern uniqueness, requirement and obligation.

Conclusion

We have propose in this paper a specification of the needs for a precise account of syntactic gradience. On this basis, we have specified a new computational model, taking advantage of a fully constraint-based syntactic representation as proposed in Property Grammars. This model has been evaluated first in replicating automatically a previous experiment showing the correlation between the scores given by the model and subjects acceptability judgements. We have then validate the approach in experimenting it on larger and unrestricted corpora.

An automatic account of gradience, such as the one presented here, can have many applications. In terms of parsing, it constitutes an efficient heuristic, helping in the selection of the construction types. Other applications can be imagined, for example in second language learning systems, helping the user in evaluating its productions. At a theoretical and cognitive level, this model shows the relevance of constraints in modelling language production and perception: the rating functions can help in explaining sentence complexity.

Fig. 3 .

 3 Fig. 3. Structures, constraint violations and harmony

  No violations 11. Marie a emprunté un très long chemin pour le retour 0.465 NP-violations 21. Marie a emprunté très long chemin un pour le retour -0.643 22. Marie a emprunté un très long chemin chemin pour le retour -0.161 ... VP-violations 51. Marie un très long chemin a emprunté pour le retour -0.56 * 54. Marie emprunté un très long chemin pour le retour -0.322 * ...

Fig

  Fig. 4. Acceptability Results

Fig. 5 .

 5 Fig. 5. Correlation Acceptability vs. Coherence

Table 1 .

 1 Calibration of adjustments and constraint weights.

	The weights are those

Table 2 .

 2 The results are reported in table 2. Correlations on the reduced data sample.

	Adjust.	Weight				Correlation
	k l m wl wo we wr wd wu	Max	g	γ
	2 4 2 1 5 3	2	2	0	2 0.6017 0.5408	0.6017
	3 4 2 1 5 3	2	2	1	2 0.6017 0.5246	0.6017
	4 4 2 1 20 10 5	4	3	2 0.6427	0.6427 0.6024
						0.6427