Philippe Blache
email: blache@lpl-aix.fr

Stéphane Rauzy
email: rauzy@lpl-aix.fr

Hybridization and Treebank Enrichment with Constraint-Based Representations

We present in this paper a method for hybridizing constituency treebanks with constraint-based descriptions and enrich them with an evaluation of sentence grammaticality. Such information is calculated thanks to a two-steps technique consisting in : (1) constraint grammar induction from the source treebank and (2) constraint evaluation for all sentences, on top of which a grammaticality index is calculated. This method is theoretically-neutral and language independent. Because of the precision of the encoded information, such enrichment is helpful in different perspectives, for example when designing psycholinguistics experiments such as comprehension or reading difficulty.

Introduction

Besides syntactic description and NLP tools development, treebanks also play an important role in more specific perspectives such as ambiguity resolution [START_REF] Koller | Computing weakest readings[END_REF], discourse analysis [START_REF] Webber | Genre distinctions for discourse in the penn treebank[END_REF] or spoken language description [START_REF] Van Der Wouden | Syntactic analysis in the spoken dutch corpus[END_REF]. More and more frequently, treebanks are used for interdisciplinary studies, in particular in psycholinguistics, bridging the gap between experimental studies (e.g. eye-tracking) and linguistic resource description [START_REF] Keller | The entropy rate principle as a predictor of processing effort: An evaluation against eye-tracking data[END_REF][START_REF] Demberg | Data from eye-tracking corpora as evidence for theories of syntactic processing complexity[END_REF][START_REF] Tomanek | A cognitive cost model of annotations based on eye-tracking data[END_REF]. These different works share the fact that they rely on different types of information (morphology, syntax, semantics, or prosody), encoded at different levels (word forms, categories, sentences) and possibly incomplete. The problem is that a classical representation in terms of constituency hierarchy is not the right level of description for these new tasks (parsing spoken languages, building difficulty models, etc.), in particular because failing in representing partial structures, ill-formed constructions, etc. Developing treebanks with a finer granularity of syntactic description is then necessary. Constraint-based representations are well equipped in such perspective: constraints can be very precise, possibly not connected to each others and may bring together different levels of representation. Treebanks bearing such precise information would then be of great help. Unfortunately, constraint parsers are of great complexity and often suffer from over-generation. We propose in this paper to bypass this problem: instead of building constraint-based treebanks from scratch, we propose an hybridization technique building the constraintbased representation starting from a constituency-based one. Knowing syntactic structure (the original tree) dramatically reduces the search space required when building the constraint representation. The interest is that this technique is entirely automatic. It consists first in inducing a constraint grammar from the source treebank and then to build the constraint-based representation thanks to a set of constraint solvers exploiting this grammar. This technique, on top of being efficient, is generic: it is independent from any linguistic formalism as well as from the language: it can be applied to any constituency treebank. Moreover, other kinds of information derived from the constraint-based representation, such as grammaticality level, can also enrich the structure, opening the way to new applications, for example in psycholinguistics. After a brief presentation of the main characteristics of the constraint-based representation, the grammar induction process is described. It consists in gathering all the possible realizations of the different categories of the corpus. The result is a large context-free grammar on top of which the constraint grammar is generated. The third section presents the hybridization mechanism which build the constraint treebank starting from the constituency. The application of this process to the French Treebank [START_REF] Abeillé | Building a treebank for french[END_REF] is described and some results are discussed. The last section describes a treebank enrichment: the evaluation of the grammaticality completes the description of the different categories realized in the treebank.

Constraint-Based Syntactic Representation

Phrase-structure representations use a unique explicit relation, hierarchy, that encode constituency information. All other information such as linear order, headedness, dependency, etc. are implicit. On the opposite, constraint-based representations encode explicitly all these relations, making it possible to verify their level of satisfaction and to evaluate precisely the structure grammaticality. Such syntactic representation syntax has been experimented in different projects [START_REF] Blache | Property grammars: A fully constraint-based theory[END_REF]. In terms of parsing, the technique consists in considering relations as constraints, satisfaction being the core of the parsing process. We propose to represent syntactic information by means of six different types of constraints that describe phrase-level constituents:

• Linearity: linear precedence relations between the constituents of a phrase

• Obligation: possible heads of a phrase

• Dependency: dependency relations between the constituents

• Uniqueness: constituents that cannot be repeated in a phrase

• Requirement: mandatory cooccurrence between categories

• Exclusion: cooccurrence restriction between categories A complete grammar can be represented by means of such constraints: each phrase-level category is described by a set of constraints between constituents. Parsing an input comes to evaluating for each category the set of constraints that describes it. Concretely, for a given category and a given set of constituents, the mechanism consists in satisfying all constraints, for example verifying that within the set of constituents, the head is realized (obligation) or that linearity constraints hold. At the end of the evaluation process, the parser has built a set of evaluated constraints. As a consequence, parsing two different realizations of a same category (in other words two different sets of constituents) will result in different sets of evaluated constraints (that can possibly be violated). The final set of evaluated constraints for a given input (also called a characterization) forms a description graph, as illustrated in figure 1 (we will use in the remaining of the paper examples from the French Treebank).

We can see in this graph how constraints represent explicitly the different kinds of syntactic information. In particular, it illustrates the fact that the number of evaluated constraints can be very different from one constituent to another. This property, together with the fact that constraints can be violated, is of central interest because describing precisely the syntactic relations, not only in terms of hierarchy. Such a rich representation makes it possible to quantify these two aspects of the syntactic structure: density and quality. We describe in the following a method for enriching constituency treebanks with such information, independently form the language.

Constraint Grammar Induction from Constituency Treebanks

Even if some effort have been done in terms of homogenizing the different syntactic annotation schemes [START_REF] Abeillé | Building a treebank for french[END_REF], the encoded information can be very different from one treebank to another. For example functional annotation can be more or less precise or dependent from the chosen formalism (compare for example [START_REF] Bies | Bracketing guidelines for treebank ii style[END_REF], [START_REF] Abeillé | Building a treebank for french[END_REF], [START_REF] Telljohann | The tüba-d/z treebank -annotating german with a context-free backbone[END_REF] or [START_REF] Böhmová | The prague dependency treebank: A three-level annotation sce-nario[END_REF]). Still, constituency treebanks contains by definition, on top of the morpho-syntactic level, the hierarchical structure. We present in this section a procedure acquiring automatically the different constraints corresponding to the implicit grammar of the treebank. The mechanism is based on the analysis of all possible constructions of the different categories which corresponds, in terms of context-free grammars, to the set of the possible right-hand sides of nonterminal categories.

Calculating the construction sets consists for all nonterminal categories XP in traversing the treebank and identifying its daughters. The result, noted RHS (XP ), is made of ordered subsets of categories. Let's note in the following ≺ the precedence relation between two categories into a construction. The set of constraints is then calculated for each non terminal category XP as follows:

• Constituency: for each non-terminal category XP, its set of constituents, noted const(XP), is the set of categories participating to the constructions in RHS(XP).

Let's note that the tagset used in the constraint grammar to be built can be adapted at this stage: categories can be, according to the needs, more precise or at the opposite more general than that of the initial tagset.

• Linearity: the precedence table is built in verifying for each category preceding another category into a construction (or a right-hand side) whether this relation is valid throughout the set of constructions

∀ rhs m ∈ RHS (XP ) if ((∃ (c i , c j ) ∈ rhs m | c i ≺ c j ) and ( rhs n ∈ RHS (XP ) | (c i , c j ) ∈ rhs n ∧ c i ≺ c j )) then add prec(c i , c j )
• Uniqueness: the set of categories that cannot be repeated in a right-hand side.

∀ rhs m ∈ RHS (XP ) ∀ (c i , c j ) ∈ rhs m if c i = c j then add uniq(c i )
• Requirement: identification of two categories that cooccur systematically in all constructions of an XP.

∀ rhs m ∈ RHS (XP ) bool ← ((c i ∈ rhs m ) ∧ (c j ∈ rhs m )) if bool then add req(c i , c j )
• Exclusion: when two categories never co-occur in the entire set of constructions, they are supposed to be in exclusion. This is a strong interpretation, that leads to over-generate the number of such constraints. However, it is the only way to identify it automatically.

∀ rhs m ∈ RHS (XP ) bool ← ¬((c i ∈ rhs m ) ∧ (c j ∈ rhs m )) if bool then add excl (c i , c j )
Besides this direct acquisition from the treebanks, two other constraint types require explicit formulation:

• Obligation: the heads of a phrase. Identified as the minimal set of compulsory constituents. Usually, this set is identified by means of specific sets of rules (cf. [START_REF] Lin | A dependency-based method for evaluating broadcoverage parsers[END_REF]). Note that multiple heads are allowed. The example figure 2 illustrates the acquisition process for the adjectival phrase. We work in this experiment on a subset of the French Treebank [START_REF] Abeillé | Building a treebank for french[END_REF], made of 134,445 words, manually corrected. The figure 2 presents the list of AP constructions in this treebank. The total number of rhs is indicated in the right column, the total number of AP in the sub-corpus being 2,657. There are 56 different types of rhs (for sake of space, only the a subpart is mentioned here). We can note that the 5 most frequent rhs types represent 95% of the possible constructions (providing important indication when building probabilistic grammars).

It is also interesting to note that in 84% of the cases, the AP is formed by a unique constituent, its head. On the opposite, complex constructions, made of more than two constituents are very rare. In this encoding, without entering into the detail of the tagset, the qualificative adjective is encoded 'Af ', the others being noted 'A-'. Coordination is indicated at the category level and treated as a feature (for example NP:COORD).

Finally, punctuation marks correspond to the category W.

The extraction of the AP constraint system is presented figure 3. The first remark is that this constraint-based representation is very compact. This observation illustrates the fact that, as was observed with the ID/LP formalism in GPSG [START_REF] Gazdar | The Logic of Typed Feature Structures[END_REF], a separate encoding of different types of syntactic information makes it possible to factorize a CFG rule-based representation. In fact, our approach systematizes the ID/LP one: we distinguish 6 dif- In our experiment, as presented figure 4, the grammar contains a total of 493 constraints extracted from the treebank (taking into account only constructions with more than one realization). There are important differences between the constructions with respect to the number of constraints as well as their distribution. The NP, because of the great variability of its possible realizations, requires a high number of constraints. As for the constraint types, linearity is the most frequent, illustrating the fact that word order in French is highly constrained. It is also interesting to note that the size of the constraint set is not directly dependent from the number of constituents (compare AdP, Ssub and VP).

The following example, taken from the FTB, illustrates the evaluation of the constraint grammar for the AP "plus économique que politique (more economical than politic)":

const {AdP, A, Ssub} lin A ≺ Ssub AdP ≺ A dep {AdP, Ssub} A uniq {A, Ssub} oblig {A} excl VPinf ⊗ Ssub
This example shows the interest of a constraint-based description which provides many precise information not directly accessible in a constituency-based representation. We will see in the last section of the paper the importance of such description for different applications.

Enriching Treebanks with a Constraint-Based Description

Our treebank enrichment consists in building an hybrid syntactic representation, one (the original) being purely constituency-based, the second being constraint-based. Generally, building a constraint-based representation as described in section 2 is a computationally complex process, highly non-deterministic, in particular due to constraint relaxation. However, the task in our case is to enrich an existing treebank. The problem consists to evaluate the constraint system for each node of the original tree instead of building an entire graph description starting from the initial set of words. Concretely, the process comes to traverse for each sentence its original tree. At each node, the constraint set describing the corresponding category is evaluated thanks to different constraint solvers, presented in the following in terms of set operations.

We note |E| the cardinality of the set E; C the ordered set of constituents of the category taken into account; C i..j the sublist of C between positions i and j; c i a constituent of C at position i; n the number of different constituents belonging to C. Constraints are of two types: those specifying a set (obligation, uniqueness) and those defining relations between sets of categories. In the first case, we note S cx the set of categories specified by the constraint of type cx. In the second case, we note L cx and R cx respectively the left and right parts of the constraint cx.

• Obligation: this operation consists in verifying the presence of one of the obligatory categories specified in the obligation constraints. In terms of sets, this means that the intersection between the set of realized constituents C and the set of categories specified in the obligation constraint:

|C ∩ S oblig | > 0
• Linearity: the verification of the linear precedence constraints consists in verifying that when a category belonging to a left-hand side of a linearity constraint is realized, then no category of the right-hand side can be realized in the sublist of the current category list of constituents preceding it:

∀c i ∈ L lin , c j ∈ R lin such that c j ∈ C 1..k ∧ c i ∈ C k+1..n
• Uniqueness: this constraints verifies that the specified categories are not repeated, which means that the intersection of the category and the set of realized constituents is not greater than one:

∀c i ∈ S uniq , |c i ∩ C| 1
• Requirement: when one category of a LHS of this constraint is realized, then one of its RHS should too:

∀c i ∈ L req ∧ c j ∈ R req , c i ∈ C ⇒ c j ∈ C
• Exclusion: when one category of a LHS of this constraint is realized, then no category of its RHS should be present:

∀c i ∈ L req ∧ c j ∈ R req , c i ∈ C ⇒ c j ∈ C
Thanks to these mechanisms, a constraint-based annotation can be built on top of the constituency structure. Concretely, this mechanism makes it possible to build a parallel treebank as well as an hybrid one. In the first case, two different sets of syntactic annotations are built: one representing the constituency representation, the other the constraintbased one, both of them being aligned at the word level.

Another type of representation of the treebank consists in enriching the constituency structure: the description of nonterminal categories (the nodes of the tree) is completed by a set of relation between its constituents (their daughters). The example in figure 6 illustrates this second approach. Enriching a constituency tree consists in calculating the set of constraints of the FTB constraint grammar that are satisfied for each node of the tree. As presented above, the result consists in a characterization, which is the set of constraints Figure 4: Distribution of the constraints in the FTB-acquired grammar <category label="SENT" sample index="0" sentence index="0:16" node index="0:16:0"> <category label="NP" features="NP:SUJ" node index="0:16:1"> <category label="Det" features="Da-ms----" node index="0:16:2" form="Le" lemma="le"/> <category label="Noun" features="Ncms--" node index="0:16:3" form="texte" lemma="texte"/> <category label="AP" features="AP" node index="0:16:4"> <category label="Adj" features="Af-ms-" node index="0:16:5" form="mme" lemma="mme"/> </category> </category> <category label="VP" features="VP" node index="0:16:6"> <category label="VN" features="VN" node index="0:16:7"> <category label="Aux" features="Vaii3s--" node index="0:16:8" form="avait" lemma="avoir"/> <category label="Verb" features="Vmps-smaip--" node index="0:16:9" form="reu" lemma="recevoir"/> </category> <category label="NP" features="NP:OBJ" node index="0:16:10"> <category label="Det" features="Ds3msp---" node index="0:16:11" form="leur" lemma="leur"/> <category label="Noun" features="Ncms--" node index="0:16:12" form="accord" lemma="accord"/> <category label="AP" features="AP" node index="0:16:13"> <category label="Adj" features="Af-ms-" node index="0:16:14" form="formel" lemma="formel"/> </category> </category> </category> <category label="Pct" features="Wd" node index="0:16:15" form="." lemma="."/> Figure 5: Example of a tree in the FrenchTreeBank that can be evaluated for this specific realization. The example figure 6 shows the enrichment for the subject NP . In this encoding, the characterization is a set of constraints encoded by the elements < property >. In this representation, all constraints are encoded as relations between two nodes. In the case of set constraints (for example uniqueness constraints that specifies the categories that cannot be repeated), the corresponding evaluated constraint is encoded as a relation between the node and the category. Each element contains 4 attributes: the type of the corresponding constraint, its source and target and the result of its satisfaction (true or false). In this example, the characterization represents linearity Det ≺ N, Det ≺ AP, dependencies between Det, AP and N, etc. As mentioned above, the interest of such representation lies in the fact that it offers a precise description of the different syntactic properties. Moreover, each constraint is evaluated independently and can be satisfied or possibly violated. This means that such representation can also encode non-grammatical, partial or ill-formed constructions. Let's imagine for example that in our example, the noun would precede the determiner. The only difference in the characterization would then be the value of the attribute sat, set to false in the corresponding constraint: <prop type="lin" srce="0:16:2" tget="0:16:3" sat="f"/> This characteristic is interesting when describing specific data such as second-language acquisition, spoken language, pathological productions, etc. Table 1 recaps some figures of the FTB sub-treebank described above and the application to the enrichment procedure. The first table indicates the number of categories observed in the treebank. As already underlined, NP is by far the most frequent category, followed by PP. great variability of realizations, in comparison to other categories, which has also consequences on the distribution of the constraint types. The second table indicates the total number of evaluated constraints for the treebank, indicated per type. In this case too, we can observe a great difference in the distribution at a first glance. However, this aspect mainly comes from the frequency of the NP that uses a lot of exclusion and uniqueness constraints.

It is interesting to have a closer look at the distribution of the different evaluated constraints by category. The results for the FTB sub-treebank are presented in figure 7. Note that the number of constraints in the grammar is not directly correlated with the number of evaluated constraint (which is expected) but also to the frequency of the category: PP is a very frequent category with an <category label="NP" features="NP:SUJ" node index="0:16:1"> <category label="Det" features="Da-ms----" node index="0:16:2" form="Le" lemma="le"/> <category label="Noun" features="Ncms--" node index="0:16:3" form="texte" lemma="texte"/> <category label="AP" features="AP" node index="0:16:4"> <category label="Adj" features="Af-ms-" node index="0:16:5" form="mme" lemma="mme"/> </category> <characterization> <property type="lin" source="0:16:2" target="0:16:3" sat="p"/> <property type="lin" source="0:16:2" target="0:16:4" sat="p"/> <property type="req" source="0:16:3" target="0:16:2" sat="p"/> <property type="dep" source="0:16:2" target="0:16:3" sat="p"/> <property type="dep" source="0:16:4" target="0:16:3" sat="p"/> <property type="oblig" source="0:16:1" target="0:16:3" sat="p"/> <property type="uniq" source="0:16:1" target="0:16:2" sat="p"/> </characterization> </category> Figure 6: Example of a FTB enriched tree for the NP average number of constraints in the grammar, but represents only 7% of the number of evaluated constraints. This figure is to be compared to that of the SENT category, which represents 31% of the total. However, and this very clear when comparing with the NP, the frequency of exclusion and uniqueness constraints, which is highly variable, mainly explains this observation. More interestingly, the respective role of constraint types for each category can be measured when putting together these different information. In particular, the frequency of the constraint type in the treebank for a given category has to be balanced with its frequency in the grammar: a constraint type very frequent in the treebank and with few instance in the grammar will play a more important role in the syntactic description. In other words, the respective weights of constraint types for each category can be automatically evaluated thanks to these figures. We propose the following formula:

weight(cx) = freq tbank (cx) freq gram (cx) (1)
Figure 8 presents the application of this measure to the FTB. We can observe for example that for the NP, even though the evaluation of the exclusion constraint is much more frequent than others, its relative importance is balanced with respect to others types such as requirement or linearity, which is expected from a syntactic point of view.

Enriching Treebanks with Grammaticality Information

We present in this section the application of a grammaticality evaluation technique making use of to the constraint-based enrichment presented in the previous section. Such information, as mentioned in the introduction, can be of great help in particular for psycholinguistics experiments.

One of the characteristics of our constraint-based representation is that it is possible to quantify the number of constraints and their relative importance. This evaluation have been described in [START_REF] Blache | Acceptability prediction by means of grammaticality quantification[END_REF] and relies on the study of the set of evaluated constraints. The method proposes different scoring terms on top of which a grammaticality index is calculated. We note in the following N + c the amount of constraints satisfied by the constituent c, N - c the constraints violated, N + c , and Ec the total number of constraints that received an evaluation (i.e. N + c + N - c ). We note Tc the total amount of constraints (evaluated or not) specifying the category c. Constraints being weighted, we note W + c (respectively W - c ) the sum of the weights assigned to the constraints satisfied (respectively violated) by the constituent c. The different terms are calculated as follows:

• Satisfaction/Violation Ratio: SRc (resp. V Rc) is the number of satisfied constraints (resp. violated) divided by the number of evaluated constraints: Finally, the global Grammaticality Index (GIc) is a function of the previous indexes. It is defined recursively as follows, where c is a constituent and ci is a nested constituent of c:

SRc = N + c Ec VRc = N - c Ec •
GI c = PI c • GI c i = P Ic • P Zc i=1 GI c i Zc
Besides the constraint description, each node of the treebank can also be enriched with its grammaticality evaluation as presented in the figure 9.

Conclusion

We have presented in this paper a method for enriching constituency treebanks with a constraint-based representation, which offers the interest to propose a very precise representation of syntactic information on top of which automatic grammaticality evaluation can be calculated. Such constraint-based representation has been shown to be adapted to the description of non-canonical input (for example spoken language). This technique is generic in the sense that it is independent from the source formalism and can be applied to any constituencybased treebank. Grammar induction only depends on the analysis Figure 8: Weights of the constraint types in the FTB of the realizations of the different constituents. As a consequence, the different constraints can be generated directly from the original constituency representation. Starting from such grammar, the annotation process itself is entirely automatic. This ensure the consistency of the encoding as well as the reusability of the process. Moreover, it is language independent, the constraint grammar being automatically acquired from the original treebank.

Several works can take advantage from this kind of resources. In particular, grammaticality evaluation makes it possible to compare the different realizations of a same construction as well as quantify its "prototypicity": a high grammatical score usually comes from the fact that the corresponding construction contains redundant information, reinforcing its categorization. This kind of information is useful for example in discourse relations identification, speaker involvement evaluation, etc.

As an example, two on-going experiments rely on such treebanks. First, eye-tracking data are on the process to be acquired for the French Treebank, making it possible to look for correlation between grammaticality and difficulty. A second project concerns cross-linguistic study of constraint-based representation, applied to English, Chinese and Arabic. The idea consists here in acquiring a constraint grammar for each of these languages and to compare the description (and the grammaticality) of a same construction through languages.

<category label="SENT" sample:index="0" sentence:index="0:16" node:index="0:16:0"> <category label="NP" features="NP:SUJ" node:index="0:16:1"> <category label="Det" features="Da-ms----" node:index="0:16:2" form="Le" lemma="le"/> <category label="Noun" features="Ncms--" node:index="0:16:3" form="texte" lemma="texte"/> <category label="AP" features="AP" node:index="0:16:4"> <category label="Adj" features="Af-ms-" node:index="0:16:5" form="mme" lemma="mme"/> <indices grammaticality="0.5866" sat:ratio="1.0" completeness="0.1176" quality:index="1.0" precision="0.5847"/> </category> <indices grammaticality="0.5993" sat:ratio="1.0" completeness="0.1525" quality:index="1.0" precision="0.6011"/> </category> <category label="VP" features="VP" node:index="0:16:6"> <category label="VN" features="VN" node:index="0:16:7"> <category label="Aux" features="Vaii3s--" node:index="0:16:8" form="avait" lemma="avoir"/> <category label="Verb" features="Vmps-smaip--" node:index="0:16:9" form="reu" lemma="recevoir"/> <indices grammaticality="0.6201" sat:ratio="1.0" completeness="0.2105" quality:index="1.0" precision="0.6284"/> </category> <category label="NP" features="NP:OBJ" node:index="0:16:10"> <category label="Det" features="Ds3msp---" node:index="0:16:11" form="leur" lemma="leur"/> <category label="Noun" features="Ncms--" node:index="0:16:12" form="accord" lemma="accord"/> <category label="AP" features="AP" node:index="0:16:13"> <category label="Adj" features="Af-ms-" node:index="0:16:14" form="formel" lemma="formel"/> <indices grammaticality="0.5851" sat:ratio="1.0" completeness="0.1176" quality:index="1.0" precision="0.5847"/> </category> <indices grammaticality="0.5981" sat:ratio="1.0" completeness="0.1525" quality:index="1.0" precision="0.6011"/> </category> <indices grammaticality="0.5871" sat:ratio="1.0" completeness="0.1111" quality:index="1.0" precision="0.5816"/> </category> <category label="Pct" features="Wd" node:index="0:16:15" form="." lemma="."/> <indices grammaticality="0.6224" sat:ratio="1.0" completeness="0.2142" quality:index="1.0" precision="0.6302"/> </category>

Figure 1 :

 1 Figure 1: Description graph of the sentence"The text itself had received their formal agreement"

Figure

  Figure 3: AP properties

  Completeness Index: number of evaluated constraints divided by the total number of constraints for the category c:CI c =Ec Tc • Quality Index: distribution of the weights of satisfied and violated constraints:QI c = W + -W - W + + W - • Precision Index:The Index of Precision for the constituent c is defined as the following ratio:PI c = k • QI c + l • SRc + m • CIcThese adjustment coefficients (k, l, m) are used as variable parameters for tuning up the model.

Figure 9 :

 9 Figure 9: Example of tree enriched with grammaticality

Table 1 :

 1 Moreover, as mentioned above, NP has a Number of constraints by category and type

	SENT	1 471
	NP	8 127
	AP	2 632
	VP	2 550
	VN	2 628	lin	27 367
	PP	4 124	obl 32 602
	AdP	1 733	dep 21 971
	Srel	508	exc 89 293
	Ssub	476	req	11 022
	Sint	352	uni 38 007
	VPinf	917
	VPpart 618
	VNinf	863
	VNpart 616


Philippe Blache
email: blache@lpl-aix.fr

Stéphane Rauzy
email: rauzy@lpl-aix.fr

Predicting Linguistic Difficulty by Means of a Morpho-Syntactic Probabilistic Model

Keywords: Linguistic complexity, difficulty model, computational psycholinguistics, sentence processing

We propose in this paper a new contribution to the evaluation of linguistic difficulty. At the opposite of classical approaches relying on syntax, we show that a probabilistic morpho-syntactic analysis provides information enough to calculate different parameters, including surprisal. This method constitutes an original and robust model to linguistic complexity. It constitutes a solution towards complexity experiments using spoken languages.

Introduction

Linguistic complexity is an important problem both from linguistic, computational and cognitive perspectives: it is important to know for a given language what are the phenomena or the constructions that can lead to a processing problem for a human subject. Such knowledge is the basis of a better understanding of the cerebral mechanisms of language processing. It is also necessary in the persepctive of the development of a cognitively-plausible automatic parser. Today, several computational models have been developed in this perspective. However, most of them are partial, only take into account local phenomena, and are experimented on highly controlled written text (cf. [START_REF] Gibson | The dependency locality theory: A distance-based theory of linguistic complexity[END_REF], [START_REF] Vasishth | Quantifying processing difficulty in human sentence parsing: The role of decay, activation, and similarity-based interference[END_REF] or [START_REF] Lewis | An activation-based model of sentence processing as skilled memory retrieval[END_REF] for example). More recent works propose to go one step forward in experimenting models on larger corpora (see in particular [START_REF] Demberg | Data from eye-tracking corpora as evidence for theories of syntactic processing complexity[END_REF], making it possible to validate complexity models. One of the conclusion of these works is that generic models have to bring together many different complexity parameters in order to take into account a large variety of phenomena. Moreover, it still remains necessary to develop and validate generic computational models dealing with unrestricted linguistic material, in particular spoken languages.

Among the different parameters involved in its definition, the evaluation of the difficulty human subjects encounter in language production or perception plays a major role.

In the literature, one of the most frequently used approaches relies on surprisal effects that can occur when integrating a new word to the structure (cf. [START_REF] Hale | A probabilistic earley parser as a psycholinfuistic model[END_REF]): roughly speaking, surprisal is high when the probability for a word to occur in a specific context is low. This parameter is evaluated as the negative logarithm of the probability of a word w t to appear in its context, taking into account the sequence w 1 ...w t-1 .

Surprisal is evaluated as a function of the probabilities of the possible parses when integrating the word w t . When using a probabilistic grammar, evaluating surprisal consists in measuring the difference between the probability of all parses spanning the sequence w 1 ...w t-1 and those spanning w 1 ...w t :

SI t = -log P (w 1 ...w t ) P (w 1 ...w t-1 ) (1)
Surprisal has been shown by different studies as being correlated with difficulty. This has been demonstrated experimentally, in particular by several works relying on eye-tracking in reading tasks (cf. [START_REF] Boston | Parallelism and syntactic processes in reading difficulty[END_REF], [START_REF] Demberg | Data from eye-tracking corpora as evidence for theories of syntactic processing complexity[END_REF] or [START_REF] Mitchell | Syntactic and semantic factors in processing difficulty: An integrated measure[END_REF]). These last studies use results from the Dundee corpus (see [START_REF] Kennedy | The dundee corpus[END_REF]) from which some short extracts have been chosen (20 texts read by 10 subjects). This corpus has been analyzed, surprisal values calculated and put in perspective with eye-tracking data. Results show a correlation between difficulty parameters (in particular reading time) and surprisal indexes.

One of the problems is that surprisal evaluation is sensible to the syntactic formalism. Moreover, from a computational point of view, surprisal also depends on the characteristics of the parser used in the evaluation. Surprisal being measured in terms of the probabilities of the possible parses, it is necessary first to build a probabilized grammar (which can be problematic) and second to correctly generate all candidate parses. We know that when parsing unrestricted linguistic material, it is not always possible to build parse trees. Robustness and precision are then pre-requisite properties of the parsers when evaluating surprisal. This also means that, because of the limitation of parsing technologies, it is not possible to measure difficulty for non-canonical or ill-formed construction (not to speak of spoken language).

We propose in this paper to explore a new direction for difficulty evaluation: syntax being problematic when dealing with unrestricted material, we propose to analyze precisely the contribution of morpho-syntactic information in surprisal evaluation. Our hypothesis is that surprisal effects appear at the lexical level, as corroborated by works on the impact of the lexicon on ambiguity or reanalysis phenomena (cf. [START_REF] Fodor | Reanalysis in sentence processing[END_REF]). We propose to measure surprisal effects only by means of a probabilistic categorization task, without using parsing information. We use in this perspective a probabilistic morpho-syntactic tagger, taking into account at each step a variable-size context.

In the first section, we present the probabilistic method thanks to which we evaluate the different parameters entering in the difficulty model. In the second section, we describe how to calculate the parameters. Finally, the last section will present some results.

Before entering into the description of our approach, we want to underline the fact that this paper presents a theoretical proposal which still has to be validated experimentally. However, we propose in the last section preliminary results calculated from a large corpus showing a positive tendency.

The statistical model

The mechanism consists in evaluating a probability to any sequence of tokens (or part-of-speech). Each token is associated, thanks to a lexicon, to its corresponding lexical tags distribution, where tags take their values in the set of morphosyntactic categories C. An example of tags distribution is illustrated table 1. The tagging process is usually very ambiguous. This ambiguity generates an exploration tree space of potential solutions Sol. Its cardinality card(Sol) is a function of the combinatory associated with the potential choices for each token of the sentence. The tokens being integrated step by step to the sentence, the cardinality card(Sol(t)) at position t in the sentence increases (or remains stable for tokens with one-to-one tag correspondence). For a given sentence, we denote hereafter by S i (t) the i th solution at position t

(i ∈ [1, card(Sol)]), S i (t) = c 1,i ...c t,i (2)
where c t,i is the morphosyntactic category associated to the token at position t for solution S i (t).

The probability of the solution S i (t) is obtained recursively by Bayes formulae :

P (S i (t)) = P (c t,i |S i (t -1)) × P (S i (t -1)) (3)
where P (S i (t -1)) is the probability of the solution i at position t -1 and

P (c t,i |S i (t -1)) is the conditional probability of category c t,i given the right context S i (t -1) = c 1,i ...c t-1,i .
In order to calculate the probability of each solution of the space of solutions Sol, we need a statistical model predicting the probability of each category c t conditioned by each right context c 1 ...c t-1 , for all the combinatory cases found for each solution of the exploration tree :

Model ⇒ P (c t |c 1 ...c t-1 ) , c 1 , ..., c t ∈ C (4)
The probabilistic model may be limited to the sole use of morphosyntactic information (that is the strategy experimented in this paper), or makes use of higher syntactical information such like structure constituents and relations describing the context. Given a model, the conditional probabilities of equation 4 allow to calculate for each added token the relative contribution of each solution S i (t) belonging to the space of solutions. The density function ρ(t) associates to each solution at position t its relative probability ρ i (t):

ρ i (t) = P (S i (t)) A t , with A t = Sol P (S i (t)) (5)
where P (S i (t)) is computed from the model given equation 4 and the normalization factor A t warrants the equality Sol ρ i (t) = 1. The evolution of the space of solutions and of its density is investigated in the following section. It provides us with the different parameters proposed for measuring the processing difficulty of a sentence at the morphosyntactic level. The probabilities mentioned equation 4 are herein obtained using the Pattern Model [START_REF] Blache | Control mechanisms for parsing in property grammars[END_REF], a Hidden Markov Model (HMM) more efficient than the standard N-grams models. For N-grams, the states of the automaton are characterized by sequence of categories of equal size N -1. The pattern model relaxes this constraint by accepting states identified by sequences of varying size. This property allows in practice to learn from the training corpus a set a states, the patterns of the model, which capture in an optimal way the morphosyntactic regularities found in the training corpus. The patterns model is seen as an approximation of the real statistical model describing the data, the approximation becoming more and more accurate as the training corpus size and coverage become larger.

The model is trained on the GraceLPL corpus, a version of the Grace/Multitag corpus (see [START_REF] Paroubek | Multitag, une ressource linguistique produit du paradigme d'évaluation[END_REF]) corrected by us. It is a French corpus containing about 700 000 words with morphosyntactic annotation following the tagset features Multext [START_REF] Ide | MULTEXT: Multilingual text tools and corpora[END_REF]. GraceLPL is regularly corrected and enriched in order to improve its tagging. The morphosyntactic information has been organized in an ad-hoc way in 50 tags (4 types of categories for punctuation marks, 1 for interjections, 2 for adjectives, 2 for conjunctions, 1 for determiners, 3 for nouns, 8 for auxiliaries, 4 for verbs, 5 for prepositions, 3 for adverbs and 15 for pronouns). In its current form, the tagset does not include gender, number and person features distinction nor tense and mood information for verbs.

The pattern model describing our tagger is composed of 2 841 patterns of varying size (the largest right context in the list of patterns counts 8 categories). The evaluation of the model is performed by comparing the tagged output with the reference. For the selected tagset of 50 categories mentionned above, the quality of the tagger (version 2011) reaches a score of 0.975 (F-measure).

The morpho-syntactic difficulty model

Surprisal is usually calculated thanks to a probabilistic grammar in building the set of possible parses (the number of parses being possibly limited to a given number). We propose to replace parses by the study of part-of-speech sequences, without any other information on structure nor relations.

The evolution of the surprisal with position t is herein defined for each solution S i (t) presented equation 2 as follows:

SI i (t) = -log P (S i (t)) P (S i (t -1)) + log(P (c t,i |.)) (6)
where the correction term P (c t,i |.) stands for the non-contextual probability of the morphosyntactic category c t,i associated to token at position t for solution S i (t). Following equation 3, the equation rewrites :

SI i (t) = -log P (c t,i |c 1,i ...c t-1,i ) P (c t,i |.) (7)
which is the negative logarithm of the ratio between contextual and non-contextual probabilities for category c t,i . The higher this ratio, i.e. the category has a strong probability to occur within this context, the more negative is the surprisal index. This term aims at correcting asymmetry in category distribution. Some of them are densely populated (e.g. common noun) whereas some other are not (e.g. present participle of the auxiliary) without any consequence on human processing difficulty. With this correction, the overall surprisal SI(t) is the same as proposed in the literature (see for example [START_REF] Demberg | Data from eye-tracking corpora as evidence for theories of syntactic processing complexity[END_REF]):

SI(t) = Sol ρ i (t) SI i (t), (8)
which is the weighted average of individual surprisal values for each solution, weighted by their relative contribution ρ i (t) (see equation 5). Surprisal measures a function of these two difficulty parameters: one related to sparseness of the POS sequences, the other coming from the number of solutions to take into account at the same time (consequence of the lexical forms ambiguity). This observation leads us to propose a second parameter making it possible to separate these two effects. The consequence of morpho-syntacic ambiguity on processing difficulty can be directly measured. A good indication is for example entropy variation of the probability distribution ρ i (t) described equation 5:

AH(t) = - Sol ρ i (t) log ρ i (t) (9) AI(t) = AH(t) -AH(t -1) (10)
The value AH(t) measures evolution of the effective size of solution space. Its derivative across time, the ambiguity index AI(t), shows that integrating the lexical form at a position t locally contribute to solve ambiguity (AI(t) < 0) or to increase it (AI(t) > 0).

As mentioned in the introduction, this paper present a preliminary study and many work is still to be done in order to validate our hypothesis. First, we have to verify that our model is a good predictor for difficulty. In this perspective, corpora with eye-tracking data have to be collected (for French in particular). Moreover, a systematic comparison with results obtained with syntacticallybased surprisal values has to be done. Finally, new kinds of data have to be created in the perspective of validating our model against spoken language corpora. However, we propose in this section a preliminary study on real data, giving some indications on the efficiency of the model.

Our study relies on a French corpus, made of 317,258 tokens (14,545 sentences), collected from the GRACE corpus mentioned before (automatically generated and manually corrected). The sentence selected from the initial corpus are those which have no difference between the reference categorization (that of the corpus) and that of our tagger. For each token, surprisal and ambiguity values have been calculated. Moreover, each sentence is associated to a revision rate, which relies on the number of revisions (or backtrackings) occurring during the tagging process. More precisely, the revision rate is the ratio between the number of solutions with a maximal probability that have been abandoned and the number of tokens in the sentence.

Model Validation

We propose in this section to verify the validity of our proposal in applying surprisal and ambiguity parameters to two phenomena known to be complex: relatives (subjects vs. objects) and clitics (nominative vs. accusative).

Relatives Several psycholinguistic studies (cf. [START_REF] Gibson | Linguistic complexity: locality of syntactic dependencies[END_REF][START_REF] Gibson | The dependency locality theory: A distance-based theory of linguistic complexity[END_REF], [START_REF] Just | A capacity theory of comprehension: Individual differences in working memory[END_REF]) have shown the that object relatives are more complex in terms of processing than subject relatives. Different analysis have been given for this: subject relatives follow the canonical SVO order, object relatives require to memorize more information, etc. The complexity differences have been shown experimentally by means of reading times (see for example [START_REF] Lewis | An activation-based model of sentence processing as skilled memory retrieval[END_REF], [START_REF] Demberg | Data from eye-tracking corpora as evidence for theories of syntactic processing complexity[END_REF]).

We obtain the same prediction with our morpho-syntactic model: object relative pronoun has a surprisal value significantly higher than subject. Moreover, we also observe a relation between surprisal and ambiguity: the object pronoun is more ambiguous than the subject and causes a higher surprisal. POS Occur. Surprisal Ambiguity Subj 2507 -1,438 -0,076 Obj 1228 -0,953 0,202

Clitics Language acquisition studies show a later acquisition of accusative clitics than nominative ones (see [START_REF] Jakubowicz | Computational complexity and the acquisition of functional categories by french-speaking children with SLI[END_REF]), underlying higher complexity for the accusative case. This difference is predicted by our model: accusative clitics have surprisal values twice higher than nominative ones.

POS

Occur. Surprisal Ambiguity Nomin. 9682 -1,586 0,003 Acc. 1857 -0,701 0,261

These results tend to confirm our hypothesis stipulating that surprisal evaluation on a morphosyntactic basis is a good predictor of processing difficulty, as the syntactic-based surprisal model.

Surprisal

The following examples underline the effects of surprisal and ambiguity values, obtained on a morpho-syntactic basis. The figures show the evolution by words of the two parameters. In the first example, the maximal surprisal value is reached with the preposition "de", located between two determiners (a cardinal and a demonstrative). In this case, category sequence sparseness is the cause of the surprisal, more than ambiguity. This last parameter show a peak on the previous token, whereas the token associated to the surprisal peak corresponds to a negative ambiguity value.

"Ainsi pour Le Seuil, quarante-sept de ces droits ont t acquis par des diteurs de langue allemande." "On parle aussi d'étoiles de l'Opéra : Noella Pontois, qui est à la retraite, Michael Denard, qui va bientôt l'être ..."

"So, for Le Seuil, 47 of these rights have been acquired by German-speaking editors." "We also talk about Opera stars: Noella Pontois, who is retired, Michal Denard, who will be soon too ..." In the second example, the surprisal peak is located on the infinitive verb "être". This value is related to the categorization of the preceding word "l" as a determiner. It reveals a syntactic difficulty related to the elliptic construction. Moreover, at the difference with the previous example, surprisal comes with high ambiguity value.

These two examples show that the contribution of the ambiguity parameter to surprisal is not direct. Nevertheless, we have observed on the entire corpus a correlation between surprisal and ambiguity (Pearson correlation coefficient of 0.4). Ambiguity, parallelism: A frequently discussed question in the literature concerning human processor is to know whether it works on a sequential or parallel manner (cf. [START_REF] Gibson | A computational theory of human linguistic processing: Memory limitations and processing breakdown[END_REF][START_REF] Boston | Parallelism and syntactic processes in reading difficulty[END_REF]). This question is important and has consequences on complexity study, and more particularly on memorization costs. A parallel parser requires to store all possible parses at the same time whereas a sequential parser memorizes less states, but relies on backtracking. This question is still open, even with the massive use of probabilistic approaches in language processing that could militate in favor of a parallel processing. [START_REF] Brants | Probabilistic parsing and psychological plausibility[END_REF] have shown that the choice of an adequate hierarchization factor renders the parallelization process almost useless. The study of revision rates obtained in the corpus tends to confirm this result: surprisingly, the categorization process is almost deterministic. More precisely, we measured on the corpus 7,133 sentences (49% of the total) that do not present backtrack: the choice of the most probable solution at each step leads to the right solution. The overall revision rate is 4.3%.

In other words, the tagger behavior confirms the hypothesis of a very limited parallelism in language processing. It is an interesting result not only from a cognitive perspective, but also for automatic language processing: parsing techniques relying on a "beam search" strategy seems to constitute an adapted answer.

Conclusion

The analysis of language processing difficulty by human subjects necessarily has to take into account language in natural situation, which means the necessity of treating spoken language. The methods and models used in such studies must then deal with different uses in order to be general and reusable, which is not the case with current difficulty models. In particular, evaluating automatically difficulty parameters means tools able to process non canonical or even ill-formed sentences.

The solution we propose in this paper consists in using low-level information: morpho-syntax features can been calculated with a good performance, even for spoken language transcriptions. This means that automatic tools can always provide some information, whatever the structure (which is not the case with syntactic models). Our approach constitutes a first answer towards natural language difficulty modeling for mainly for two reasons:

• The approach is formalism-independent and theoretical-neutral: evaluating difficulty on the basis of morpho-syntactic information avoids the use of syntactically-annotated resources as well as parsers. It becomes the possible to adapt this technique to other languages, even those without syntactic resources.

• Robustness: the efficiency of modern taggers makes it possible to process all kinds of linguistic material, including spoken language.

The results we obtained on corpus analysis have to be generalized by means of experimentations on human subjects leading to reading-time, eye-tracking and evoked potentials data.

Figure 1 :

 1 Figure 1: Surprisal examples

Table 1 :

 1 Tags

	Form Lemma Sampa Tag	Proba.
	est	être	E	Auxiliary	0.39
	est	être	E	Verb	0.52
	est	est	Est	Noun	0.09

distribution for the french lexical form "est" (meaning "is" in its verb or auxiliary use, or "east" in its noun use).