Luc Boruta
email: luc.boruta@inria.fr

Justyna Jastrzebska
email: justynajastrzebska@yahoo.fr

A Phonemic Corpus of Polish Child-Directed Speech

Keywords: child-directed speech, Polish, phonology

Recent advances in modeling early language acquisition are due not only to the development of machine-learning techniques, but also to the increasing availability of data on child language and child-adult interaction. In the absence of recordings of child-directed speech, or when models explicitly require such a representation for training data, phonemic transcriptions are commonly used as input data. We present a novel (and to our knowledge, the first) phonemic corpus of Polish child-directed speech. It is derived from the Weist corpus of Polish, freely available from the seminal CHILDES database. For the sake of reproducibility, and to exemplify the typical trade-off between ecological validity and sample size, we report all preprocessing operations and transcription guidelines. Contributed linguistic resources include updated CHAT-formatted transcripts with phonemic transcriptions in a novel phonology tier, as well as by-product data, such as a phonemic lexicon of Polish. All resources are distributed under the LGPL-LR license.

Introduction

Recent advances in modeling early language acquisition are due not only to the development of machine-learning techniques, but also to the increasing availability of data on child language and child-adult interaction. In the absence of (high-quality) recordings of child-directed speech -throughout this study, we use child-directed speech as an umbrella term for childand infant-directed speech, i.e. linguistic data children may use to bootstrap into languageor when models explicitly require such a representation for training data, phonemically transcribed child-directed corpora have commonly been used as input data. Indeed, phonemic transcriptions have been used to develop and validate, among other tasks, computational models of the early acquisition of word segmentation, phonological knowledge, or both [START_REF] Venkataraman | A statistical model for word discovery in transcribed speech[END_REF][START_REF] Peperkamp | The acquisition of allophonic rules: statistical learning with linguistic constraints[END_REF][START_REF] Blanchard | Improving word segmentation by simultaneously learning phonotactics[END_REF][START_REF] Daland | Learning diphone-based segmentation[END_REF]Boruta et al., 2011, inter alios). Moreover (unless otherwise stated), computational models of psycholinguistic processes are expected to generalize to typologically different (if not all) languages [START_REF] Gambell | Statistics learning and universal grammar: modeling word segmentation[END_REF]. Nonetheless, the best known corpora of childdirected speech have been developped for English or one of a small number of other languages, and Polish is one of many low-resource languages when it comes to the evaluation of computational models of language acquisition. The purpose of this paper is to present a novel (and to our knowledge, the first) phonemic corpus of Polish childdirected speech that subsequent studies might use to determine how models of early language acquisition perform on Polish or, by extension, Slavic languages. L. B. designed the study, analyzed the original corpus, and wrote the paper; J. J. developed the phonemic lexicon. Both authors discussed the results and implications at all stages.

Sources of Data

We derived our phonemic corpus from the Weist corpus of Polish child-directed speech [START_REF] Weist | The defective tense hypothesis: on the emergence of tense and aspect in child Polish[END_REF][START_REF] Weist | Basic relations in child language and the word order myth[END_REF]) that is freely available from the seminal CHILDES database [START_REF] Macwhinney | The CHILDES Project: Tools for Analyzing Talk[END_REF]. This corpus contains 39 CHAT-formatted transcripts of interactive, non-elicited, spontaneous verbal interactions involving four Polish-learning children (aged 1;7 to 2;6 at the time of recording) and their respective caregivers. For each utterance, the basic unit of data in the transcripts is an orthographic transcription, a gloss, and a translation to English. Data was coded at the morphological level in the glosses, and no phonetic or phonemic information is available in a systematic manner. It is also worth noting that the audio recordings are freely available as WAV files from the Media section of the CHILDES database.

Deriving a Phonemic Corpus

The Brent/Ratner corpus of English child-directed speech [START_REF] Brent | Distributional regularity and phonotactic constraints are useful for segmentation[END_REF] has now become the standard dataset for the evaluation of computational models of early language acquisition. Therefore, we followed the design and format of that corpus in order to derive our phonemic corpus of Polish from Weist et al.'s orthographic transcripts. For the sake of reproducibility and global consistency, most derivation steps were automated. In keeping with usual practice, slashes /•/ are used from this point forward to enclose phonemic transcriptions, and chevrons • are used to enclose material from the CHATformatted orthographic transcripts.

Extracting Standard Child-Directed Utterances

As with the Brent/Ratner corpus, the first processing step consisted in the automatic extraction of the child-directed utterances from Weist et al.'s original transcripts, that is to

Bilabial Labiodental Postdental Alveolar Alveopalatal Palatal Velar Nasal m n ñ N m n N G Plosive p b t d c Í k g p b t d c J k g Fricative f v s z S Z C ý x f v s z S Z 6 4 x Affricate ţ dz Ù dz tC dý T D 1 2 7 5 Lateral l l Flap/Trill r r Glide j w j w
Table 1: Consonants and glides of the phonemic inventory of Polish (IPA in serif, ASCII in monospaced typeface). Where symbols appear in pairs, the one to the right represents a voiced consonant.

say all utterances except the ones uttered by the so-called target child. Data for each of the four children were concatenated into a single meta-corpus.

Out of the raw 17,553 extracted utterances, only 15,364 (88%) complete and well-formed utterances were further selected to build the phonemic corpus. In order to control the trade-off between ecological validity and sample size, the following selection criteria were applied.

Exclusion Criteria

First, utterances containing actions without speech, unidentifiable, guessed or untranscribed material (annotated with the 0 , xxx , [?] , and www CHAT markers, respectively) were automatically discarded from the corpus as, undeniably, no proper phonemic transcription may be recovered from those utterances. Following the same argument, incomplete utterances, or utterances containing phonological fragments (annotated with the & marker) or incomplete words were also discarded. Finally, utterances containing non-standard words such as babbling, onomatopoeia, interjections, word plays, neologisms, child-invented, second-language or family-specific forms (transcribed with the @b , @o , @i , @wp , @n , @c , @s , and @f markers, respectively) were discarded as their transcription and/or their frequency of occurrence might prove problematic.

Deletion Criteria

Conversely, as they do not affect the integrity of the utterances, other CHAT-formatted annotations such as paralinguistic material, pause symbols, punctuation marks, utterance terminators and utterance linkers were merely deleted from the orthographic transcriptions.

An example of this is the trailing-off terminator +... which marks the end of an incomplete (but not interrupted) utterance. By deleting this marker in, for example, jeszcze nie +... (not yet), the utterance would then be mapped to the phonemic transcription /jeSÙe ñe/.

It is also worth mentioning that, when annotated as single phrases in the original transcripts with the repetition marker [x n] , phrasal repetitions were not expanded; for example, the utterance dzień dobry, dzień dobry, dzień dobry (good morning, good morning, good morning) would only be phonemically transcribed as /dýieñ dobr1/ if coded as dzień dobry [x 3] . Hence, studying repetitions or disfluencies, or computing corpus statistics (such as the ubiquitous mean length of utterance measure, a.k.a. MLU) from this derived representation of the data might result in observations far different from those obtained using CHATspecific software such as CLAN [START_REF] Macwhinney | The CHILDES Project: Tools for Analyzing Talk[END_REF]. Deleting punctuation marks was done to create a strippeddown representation of the data, identical to the one used in the Brent/Ratner corpus: one utterance per line, containing only space-separated, phonemically-transcribed words with a one-to-one mapping between the phonemes and the symbols used to represent them.

Extracting the Lexicon

Once the proper subset of complete, well-formed utterances was selected, the following step consisted in the automatic extraction the attested lexicon from the candidate corpus, i.e. the set of all occurring orthographic words. As in the Brent/Ratner corpus of English, word transcriptions were designed so that each orthographic word form is matched with a single phonemic transcription. As grapheme-to-phoneme relations in Polish are regular (though complex), phonemic transcriptions could have been obtained automatically [START_REF] Steffen-Batogowa | Automatyzacja transkrypcji fonematycznej tekstów polskich [Automatic phonemic transcription of Polish texts[END_REF][START_REF] Jassem | Illustrations of the IPA: Polish[END_REF]. However, because of the relatively small size of the lexicon in the corpus at hand (5,712 types), we sacrificed some reproducibility for the sake of quality, and transcribed the lexicon manually.

Transcription Scheme

As for the definition of the phonemic inventory, we used Jassem's authoritative description of Polish phonemes [START_REF] Jassem | Illustrations of the IPA: Polish[END_REF]. The resulting phonemic inventory of Polish is presented in Table 1 for consonants and glides, and in Figure 1 for vowels.

y • u • o • a • e • i • 1• u• o• a• e• i•
Figure 1: Vowels of the phonemic inventory of Polish (IPA in serif, ASCII in monospaced typeface).

Because the implementation of many computational models of early language acquisition -legacy, such as Venkataraman's NGS-u [START_REF] Venkataraman | A statistical model for word discovery in transcribed speech[END_REF], or not, such as Goldwater et al.'s DP [START_REF] Goldwater | A Bayesian framework for word segmentation: exploring the effects of context[END_REF]-do not accomodate Unicode characters denoting the symbols of the international phonetic alphabet (henceforth IPA), each phoneme was mapped to an ASCII character in the released resources.

Derived Corpus

Finally, the whole phonemic corpus was automatically reconstructed replacing, in each extracted child-directed utterance, every orthographic word form by its phonemic transcription. The final derived phonemic corpus of Polish child-directed speech contains 15,364 utterance tokens (representing 11,194 types), 54,662 words (5,712 types) and 225,324 phonemes (37 types). Moreover, it is worth noting that this corpus of Polish is approximately twice the size of the Brent/Ratner corpus of English: it contains 1.6 times more utterances (in terms of tokens), 1.6 times more words, and 2.4 times more phonemes. Phoneme frequencies observed in the corpus are reported in Table 2. Aside from the stripped-down format used in the Brent/Ratner corpus, and because subsequent studies might require to enforce ecological validity, e.g. by extracting utterances addressed to a single child, the resulting phonemic transcriptions of the Weist corpus were also included as a novel phonology tier (denoted %pho) in updated CHATformatted transcripts. An excerpt of such a transcript is presented in Figure 2.

On the Usefulness of such Corpora

To further emphasize the need for computational models of early language acquisition to be evaluated using typologically different languages, we compare the performance of a well-known unsupervised model of the acquisition of word segmentation [START_REF] Venkataraman | A statistical model for word discovery in transcribed speech[END_REF] on three phonemic corpora (derived) from the CHILDES database: the aforementioned Brent/Ratner corpus of English, the Johnson/Demuth corpus of Sesotho [START_REF] Johnson | Unsupervised word segmentation for Sesotho using adaptor grammars[END_REF], and our novel corpus of Polish. Providing a thorough analysis of the discrepancies between this model's performance on English, Sesotho and Polish is beyond the scope of this paper. Yet, a standard quantitative evaluation gives enough weight to the argument at hand. As Venkataraman's model is incremental, its output is conditional on the order in which input utterances are processed; we thus report average segmentation F-scores (together with standard deviations within parentheses) observed over 100 distinct random permutations of the input corpora. The results are categorical: the F-score of the word segmentation model is 66.8% (2.9) for English, 50.4% (3.3) for Polish, and only 28.4% (7.1) for Sesotho.

As evidenced here, evaluating the performance of a computational model of early language acquisition using data from only one language offers no guarantee whatsoever as to the performance of the model on other languages, especially if typologically unrelated; hence the need for a special effort in creating appropriate linguistic resources.

Resources and License

All aforementioned resources, derived (the updated CHATformatted transcripts) or original (the phonemic lexicon), are distributed under the terms of the Lesser General Public License for Linguistic Resources (LGPL-LR). In addition to being included into LREC's LRE Map, these resources were also recontributed to the Derived Corpora and Counts section of the CHILDES database.

Figure 2 :

 2 Figure 2: Beginning of the updated marta1.cha transcript. Added phonemic transcriptions are in the bold %pho tier.

Table 2 :

 2 Phoneme frequencies in the derived corpus (IPA in serif, ASCII in monospaced typeface).

	Phoneme Frequency
	a a	23586
	e e	23021
	o o	21632
	t t	14422
	i i	13746
	k k	10062
	j j	8596
	w w	8197
	u u	7420
	m m	7072
	1 y	6485
	v v	5966
	n n	5934
	p p	5743
	r r	5614
	b b	5114
	s s	5019
	S S	4859
	C 6	4577
	ñ N	4215
	d d	3994
	ţ T	3728
	l l	3171
	z z	3112
	tC 7	3083
	Ù 1	2825
	Z Z	2623
	dý 5	2561
	g g	2464
	x x	1824
	f f	1336
	N G	985
	dz D	585
	Í J	391
	ý 4	326
	c c	41
	dz 2	26

  N|radio-NEUT:ACC:S V|have&IMPF:PRES:3S N|lady-FEM:NOM:S . Marta's room is full of various toys . there is also a pram with two dolls .

	* CHI:	radio ma pani .
	%eng:	the lady has a radio .
	%xmor: * MOT:	radio ma pani .
	%pho:	radjo ma pañ
	%sit:
	%eng:	the lady has a radio .
	* MOT:	oczywiście .
	%pho:	oÙiviCtCie
	%eng:	of course .
	* EWA:	to sa ˛dwie lalunie .
	%pho:	tow sow dvje laluñe
	%eng:	these are two dolls .
	* EWA:	a co one robia ˛?
	%pho:	a ţo one robiow
	%eng:	what are they doing ?
	* EWA:	oczka maja ˛zamknie ˛te .
	%pho:	oÙka majow zamkñeNte
	%eng:	their eyes are closed .
	* CHI:	śpia ˛.
	%eng:	they are sleeping .
	%xmor: V|sleep&IMPF:PRES:3P .

To our knowledge, the novel phonemic corpus of Polish childdirected speech we presented in this paper is the first resource of this kind made available for Polish and, by extension, Slavic languages.

Acknowledgements

This work was supported in part by a graduate fellowship from the French Ministry of Higher Education and Research granted to the first author.


Seyed Abolghasem Mirroshandel
email: ghasem.mirroshandel@lif.univ-mrs.fr

Alexis Nasr
email: alexis.nasr@lif.univ-mrs.fr

Joseph Le Roux
email: leroux@univ-paris13.fr

Semi-supervised Dependency Parsing using Lexical Affinities

Treebanks are not large enough to reliably model precise lexical phenomena. This deficiency provokes attachment errors in the parsers trained on such data. We propose in this paper to compute lexical affinities, on large corpora, for specific lexico-syntactic configurations that are hard to disambiguate and introduce the new information in a parser. Experiments on the French Treebank showed a relative decrease of the error rate of 7.1% Labeled Accuracy Score yielding the best parsing results on this treebank.

Introduction

Probabilistic parsers are usually trained on treebanks composed of few thousands sentences. While this amount of data seems reasonable for learning syntactic phenomena and, to some extent, very frequent lexical phenomena involving closed parts of speech (POS), it proves inadequate when modeling lexical dependencies between open POS, such as nouns, verbs and adjectives. This fact was first recognized by [START_REF] Bikel | Intricacies of Collins' parsing model[END_REF] who showed that bilexical dependencies were barely used in Michael Collins' parser.

The work reported in this paper aims at a better modeling of such phenomena by using a raw corpus that is several orders of magnitude larger than the treebank used for training the parser. The raw corpus is first parsed and the computed lexical affinities between lemmas, in specific lexico-syntactic configurations, are then injected back in the parser. Two outcomes are expected from this procedure, the first is, as mentioned above, a better modeling of bilexical dependencies and the second is a method to adapt a parser to new domains.

The paper is organized as follows. Section 2 reviews some work on the same topic and highlights their differences with ours. In section 3, we describe the parser that we use in our experiments and give a detailed description of the frequent attachment errors. Section 4 describes how lexical affinities between lemmas are calculated and their impact is then evaluated with respect to the attachment errors made by the parser. Section 5 describes three ways to integrate the lexical affinities in the parser and reports the results obtained with the three methods.

Previous Work

Coping with lexical sparsity of treebanks using raw corpora has been an active direction of research for many years.

One simple and effective way to tackle this problem is to put together words that share, in a large raw corpus, similar linear contexts, into word clusters. The word occurrences of the training treebank are then replaced by their cluster identifier and a new parser is trained on the transformed treebank. Using such techniques [START_REF] Koo | Simple semisupervised dependency parsing[END_REF] report significative improvement on the Penn Treebank [START_REF] Marcus | Building a large annotated corpus of english: The penn treebank[END_REF] and so do [START_REF] Candito | Parsing word clusters[END_REF]Candito and Crabbé, 2009) on the French Treebank [START_REF] Abeillé | Building a treebank for french[END_REF].

Another series of papers [START_REF] Volk | Exploiting the WWW as a corpus to resolve PP attachment ambiguities[END_REF][START_REF] Nakov | Using the web as an implicit training set: application to structural ambiguity resolution[END_REF][START_REF] Pitler | Using web-scale N-grams to improve base NP parsing performance[END_REF][START_REF] Zhou | Exploiting web-derived selectional preference to improve statistical dependency parsing[END_REF] directly model word co-occurrences. Cooccurrences of pairs of words are first collected in a raw corpus or internet n-grams. Based on the counts produced, lexical affinity scores are computed. The detection of pairs of words co-occurrences is generally very simple, it is either based on the direct adjacency of the words in the string or their cooccurrence in a window of a few words. [START_REF] Bansal | Web-scale features for full-scale parsing[END_REF][START_REF] Nakov | Using the web as an implicit training set: application to structural ambiguity resolution[END_REF] rely on the same sort of techniques but use more sophisticated patterns, based on simple paraphrase rules, for identifying co-occurrences.

Our work departs from those approaches by the fact that we do not extract the lexical information directly on a raw corpus, but we first parse it and then extract the co-occurrences on the parse trees, based on some predetermined lexico-syntactic patterns. The first reason for this choice is that the linguistic phenomena that we are interested in, such as as PP attachment, coordination, verb subject and object can range over long distances, beyond what is generally taken into account when working on limited windows. The second reason for this choice was to show that the performances that the NLP community has reached on parsing, combined with the use of confidence measures allow to use parsers to extract accurate lexico-syntactic information, beyond what can be found in limited annotated corpora.

Our work can also be compared with self training approaches to parsing [START_REF] Mcclosky | Effective self-training for parsing[END_REF][START_REF] Suzuki | An empirical study of semi-supervised structured conditional models for dependency parsing[END_REF][START_REF] Steedman | Bootstrapping statistical parsers from small datasets[END_REF][START_REF] Sagae | Dependency parsing and domain adaptation with lr models and parser ensembles[END_REF] where a parser is first trained on a treebank and then used to parse a large raw corpus. The parses produced are then added to the initial treebank and a new parser is trained. The main difference between these approaches and ours is that we do not directly add the output of the parser to the training corpus, but extract precise lexical information that is then re-injected in the parser. In the self training approach, [START_REF] Chen | Improving dependency parsing with subtrees from auto-parsed data[END_REF] is quite close to our work: instead of adding new parses to the treebank, the occurrence of simple interesting subtrees are detected in the parses and introduced as new features in the parser.

The way we introduce lexical affinity measures in the parser, in 5.1, shares some ideas with [START_REF] Anguiano | Parse correction with specialized models for difficult attachment types[END_REF], who modify some attachments in the parser output, based on lexical information. The main difference is that we only take attachments that appear in an n-best parse list into account, while they consider the first best parse and compute all potential alternative attachments, that may not actually occur in the n-best forests.

The Parser

The parser used in this work is the second order graph based parser [START_REF] Mcdonald | Non-projective dependency parsing using spanning tree algorithms[END_REF][START_REF] Kübler | Dependency parsing[END_REF] implementation of [START_REF] Bohnet | Very high accuracy and fast dependency parsing is not a contradiction[END_REF]. The parser was trained on the French Treebank [START_REF] Abeillé | Building a treebank for french[END_REF] which was transformed into dependency trees by (Candito et al., 2009) The part of speech tagging was performed with the MELT tagger [START_REF] Denis | Exploitation d'une ressource lexicale pour la construction d'un étiqueteur morphosyntaxique état-de-l'art du franc ¸ais[END_REF] and lemmatized with the MACAON tool suite [START_REF] Nasr | MACAON: An NLP tool suite for processing word lattices[END_REF] Figure 1 shows the distribution of the 100 most common error types made by the parser. In this figure, x axis shows the error types and y axis shows the error ratio of the related error type ( number of errors of the specific type total number of errors ). We define an error type by the POS tag of the governor and the POS tag of the dependent. The figure presents a typical Zipfian distribution with a low number of frequent error types and a large number of unfrequent error types. The shape of the curve shows that concentrating on some specific frequent errors in order to increase the parser accuracy is a good strategy. Table 3 gives a finer description of the most common types of error made by the parser. Here we define more precise patterns for errors, where some lexical values are specified (for prepositions) and, in some cases, the nature of the dependency is taken into account. Every line of the table corresponds to one type of error. The first column describes the error type. The second column indicates the frequency of this type of dependency in the corpus. The third one displays the accuracy for this type of dependency (the number of dependencies of this type correctly analyzed by the parser divided by the total number of dependencies of this type). The fourth column shows the contribution of the errors made on this type of dependency to the global error rate. The last column associates a name with some of the error types that will prove useful in the remainder of the paper to refer to the error type.

Table 3 shows two different kinds of errors that impact the global error rate. The first one concerns very common dependencies that have a high accuracy but, due to their frequency, hurt the global error rate of the parser. The second one concerns low frequency, low accuracy dependency types. Lines 2 and 3, respectively attachment of the preposition à to a verb and the subject dependency illustrate such a contrast. They both impact the total error rate in the same way (2.53% of the errors). But the first one is a low frequency low accuracy type (respectively 0.88% and 69.11%) while the second is a high frequency high accuracy type (respectively 3.43% and 93.03%). We will see in 4.2.2 that our method behaves quite differently on these two types of error.

Creating the Lexical Resource

The lexical resource is a collection of tuples C, g, d, s where C is a lexico-syntactic configuration, g is a lemma, called the governor of the configuration, d is another lemma called the dependent and s is a numerical value between 0 and 1, called the lexical affinity score, which accounts for the strength of the association between g and d in the context C. For example the tuple (V, g) obj → (N, d), eat, oyster , 0.23 defines a simple configuration (V, g) obj → (N, d) that is an object dependency between verb g and noun d. When replacing variables g and d in C respectively with eat and oyster , we obtain the fully specified lexico syntactic pattern(V, eat) obj → (N, oyster ), that we call an instantiated configuration. The numerical value 0.23 accounts for how much eat and oyster like to co-occur in the verb-object configuration. Configurations can be of arbitrary complexity but they have to be generic enough in order to occur frequently in a corpus yet be specific enough to model a precise lexico syntactic phenomenon. The context ( * , g) * → ( * , d), for example is very generic but does not model a precise linguistic phenomenon, as selectional preferences of a verb, for example. Moreover, configurations need to be error-prone. In the perspective of increasing a parser performances, there is no point in computing lexical affinity scores between words that appear in a configuration for which the parser never makes mistakes.

The creation of the lexical resource is a three stage process. The first step is the definition of configurations, the second one is the collection of raw counts from the machine parsed corpora and the third one is the computation of lexical affinities based on the raw counts. The three steps are described in the following subsection while the evaluation of the created resource is reported in subsection 4.2.

Computing Lexical Affinities

A set of 9 configurations have been defined. Their selection is a manual process based on the analysis of the errors made by the parser, described in section 3, as well as on the linguistic phenomena they model. The list of the 9 configurations is described in Table 4. As one can see on this table, configurations are usually simple, made up of one or two dependencies. Linguistically, configurations OBJ and SBJ concern subject and object attachments, configuration ADJ is related to attachments of adjectives to nouns and configurations NdeN, VdeN, VaN, and NaN indicate prepositional attachments. We have restricted ourselves here to two common French prepositions à and de. Configurations NcN and VcV deal respectively with noun and verb coordination.

Name

Description The computation of the number of occurrences of an instantiated configuration in the corpus is quite straightforward, it consists in traversing the dependency trees produced by the parser and detect the occurrences of this configuration.

OBJ (V, g) obj → (N, d) SBJ (V, g) subj → (N, d) ADJ (N, g) → ADJ NdeN (N, g) → (P, de) → (N, d) VdeN (V, g) → (P, de) → (N, d) NaN (N, g) → (P, à) → (N, d) VaN (V, g) → (P, à) → (N, d) NcN (N, g) → (CC, * ) → (N, d) VcV (V, g) → (CC, * ) → (V, d)
At the end of the counts collection, we have gath-

s(C, l g , l d ) = 1 2 C(C, l g , l d ) C(C, l g , * ) + C(C, l g , l d ) C(C, * , l d )
it takes its values between 0 (l g and l d never co-occur) and 1 (g and d always co-occur). This function is close to pointwise mutual information [START_REF] Church | Word association norms, mutual information, and lexicography[END_REF] but takes its values between 0 and 1.

Evaluation

Lexical affinities were computed on three corpora of slightly different genres. The first one, is a collection of news report of the French press agency Agence France Presse, the second is a collection of newspaper articles from a local French newspaper : l'Est Républicain. The third one is a collection of articles from the French Wikipedia. The size of the different corpora are detailed in table 5. The corpus was first POS tagged, lemmatized and parsed in order to get the 50 best parses for every sentence. Then the lexical resource was built, based on the 9 configurations described in table 4.

The lexical resource has been evaluated on FTB DEV with respect to two measures: coverage and correction rate, described in the next two sections.

Coverage

Coverage measures the instantiated configurations present in the evaluation corpus that are in the resource. The results are presented in table 6. Every line represents a configuration, the second column indicates the number of different instantiations of this configuration in the evaluation corpus, the third one indicates the number of instantiated configurations that were actually found in the lexical resource and the fourth column shows the coverage for this configuration, which is the ratio third column over the second. Last column represents the coverage of the training corpus (the lexical resource is extracted on the training corpus) and the last line represents the same quantities computed on all configurations.

Table 6 shows two interesting results: firstly the high variability of coverage with respect to configurations, and secondly the low coverage when the lexical resource is computed on the training corpus, this fact being consistent with the conclusions of [START_REF] Bikel | Intricacies of Collins' parsing model[END_REF]. A parser trained on a treebank cannot be expected to reliably select the correct governor in lexically sensitive cases.

Conf

Correction Rate

While coverage measures how many instantiated configurations that occur in the treebank are actually present in the lexical resource, it does not measure if the information present in the lexical resource can actually help correcting the errors made by the parser.

We define Correction Rate (CR) as a way to approximate the usefulness of the data. Given a word d present in a sentence S and a configuration C, the set of all potential governors of d in configuration C, in all the n-best parses produced by the parser is computed. This set is noted G = {g 1 , . . . , g j }. Let us note G L the element of G that maximizes the lexical affinity score. When the lexical resource gives no score to any of the elements of G, G L is left unspecified.

Ideally, G should not be the set of governors in the n-best parses but the set of all possible governors for d in sentence S. Since we have no simple way to compute the latter, we will content ourselves with the former as an approximation of the latter.

Let us note G H the governor of d in the (first) best parse produced and G R the governor of d in the correct parse. CR measures the effect of replacing G H with G L .

We have represented in table 7 the different scenarios that can happen when comparing G H , G R and G L .

G L = G R or G L unspec. CC G H = G R G L = G R CE G L = G R EC G H = G R G L = G R or G L unspec. EE G R / ∈ G NA
Table 7: Five possible scenarios when comparing the governor of a word produced by the parser (G H ), in the reference parse (G R ) and according to the lexical resource (G L ).

In scenarios CC and CE, the parser did not make a mistake (the first letter, C, stands for correct). In scenario CC, the lexical affinity score was compatible with the choice of the parser or the lexical resource did not select any candidate. In scenario CE, the lexical resource introduced an error. In scenarios EC and EE, the parser made an error. In EC, the error was corrected by the lexical resource while in EE, it wasn't. Either because the lexical resource candidate was not the correct governor or it was unspecified. The last case, NA, indicates that the correct governor does not appear in any of the n-best parses. Technically this case could be integrated in EE (an error made by the parser was not corrected by the lexical resource) but we chose to keep it apart since it represents a case where the right solution could not be found in the n-best parse list (the correct governor is not a member of set G).

Let's note n S the number of occurrences of scenario S for a given configuration. We compute CR for this configuration in the following way: CR = old error number -new error number old error number

= n EC -n CE n EE + n EC + n N A
When CR is equal to 0, the correction did not have any impact on the error rate. When CR > 0, the error rate is reduced and if CR < 0 it is increased1 .

CR for each configuration is reported in table 8. The counts of the different scenarios have also been reported. Table 8 shows very different results among configurations. Results for PP attachments VdeN, VaN and NaN are quite good (a CR of 75% for a given configuration, as VdeN indicates that the number of errors on such a configuration is decreased by 25%). It is interesting to note that the parser behaves quite badly on these attachments: their accuracy (as reported in table 3) is, respectively 74.68, 69.1 and 70.64. Lexical affinity helps in such cases. On the other hand, some attachments like configuration ADJ and NdeN, for which the parser showed very good accuracy (96.6 and 92.2) show very poor performances. In such cases, taking into account lexical affinity creates new errors.

On average, using the lexical resource with this simple strategy of systematically replacing G H with G L allows to decrease by 20% the errors made on our 9 configurations and by 2.5% the global error rate of the parser.

Filtering Data with Ambiguity Threshold

The data used to extract counts is noisy: it contains errors made by the parser. Ideally, we would like to take into account only non ambiguous sentences, for which the parser outputs a single parse hypothesis, hopefully the good one. Such an approach is obviously doomed to fail since almost every sentence will be associated to several parses. Another solution would be to select sentences for which the parser has a high confidence, using confidence measures as proposed in [START_REF] Sánchez-Sáez | Statistical confidence measures for probabilistic parsing[END_REF][START_REF] Hwa | Sample selection for statistical parsing[END_REF]. But since we are only interested in some parts of sentences (usually one attachment), we don't need high confidence for the whole sentence. We have instead used a parameter, defined on single dependencies, called the ambiguity measure.

Given the n best parses of a sentence and a dependency δ, present in at least one of the n best parses, let us note C(δ) the number of occurrences of δ in the n best parse set. We note AM (δ) the ambiguity measure associated to δ. It is computed as follows:

AM (δ) = 1 - C(δ)
n An ambiguity measure of 0 indicates that δ is non ambiguous in the set of the n best parses (the word that constitutes the dependent in δ is attached to the word that constitutes the governor in δ in all the nbest analyses). When n gets large enough this measure approximates the non ambiguity of a dependency in a given sentence.

Ambiguity measure is used to filter the data when counting the number of occurrences of a configuration: only occurrences that are made of dependencies δ such that AM (δ) ≤ τ are taken into account. τ is called the ambiguity threshold.

The results of coverage and CR given above were computed for τ equal to 1, which means that, when collecting counts, all the dependencies are taken into account whatever their ambiguity is. Table 9 shows coverage and CR for different values of τ . As expected, coverage decreases with τ . But, interest-ingly, decreasing τ , from 1 down to 0.2 has a positive influence on CR. Ambiguity threshold plays the role we expected: it allows to reduce noise in the data, and corrects more errors.

τ = 1.0 τ = 0.4 τ = 0.2 τ = 0.0 cov/CR cov/

Integrating Lexical Affinity in the Parser

We have devised three methods for taking into account lexical affinity scores in the parser. The first two are post-processing methods, that take as input the n-best parses produced by the parser and modify some attachments with respect to the information given by the lexical resource. The third method introduces the lexical affinity scores as new features in the parsing model. The three methods are described in 5.1, 5.2 and 5.3. They are evaluated in 5.4.

Post Processing Method

The post processing method is quite simple. It is very close to the method that was used to compute the Correction Rate of the lexical resource, in 4.2.2: it takes as input the n-best parses produced by the parser and, for every configuration occurrence C found in the first best parse, the set (G) of all potential governors of C, in the n-best parses, is computed and among them, the word that maximizes the lexical affinity score (G L ) is identified. Once G L is identified, one can replace the choice of the parser (G H ) with G L . This method is quite crude since it does not take into account the confidence the parser has in the solution proposed. We observed, in 4.2.2 that CR was very low for configurations for which the parser achieves good accuracy. In order to introduce the parser confidence in the final choice of a governor, we compute C(G H ) and C(G L ) which respectively represent the number of times G H and G L appear as the governor of configuration C. The choice of the final governor, noted Ĝ, depends on the ratio of C(G H ) and C(G L ). The complete selection strategy is the following:

1. if G H = G L or G L is unspecified, Ĝ = G H . 2. if G H = G L , Ĝ is determined as follows: Ĝ = G H if C(G H ) C(G L ) > α G L otherwise
where α is a coefficient that is optimized on the development data set.

We have reported, in table 10 the values of CR, for the 9 different features, using this strategy, for τ = 1. We do not report the values of CR for other values of τ since they are very close to each other. The table shows several noticeable facts. First, the new strategy performs much better than the former one (crudely replacing G H by G L ), the value of CR increased from 0.2 to 0.4, which means that the errors made on the nine configurations are now decreased by 40%. Second, CR is now positive for every configuration: the number of errors is decreased for every configuration.

Double Parsing Method

The post processing method performs better than the naive strategy that was used in 4.2.2. But it has an important drawback: it creates inconsistent parses.

Recall that the parser we are using is based on a second order model, which means that the score of a dependency depends on some neighboring ones. Since with the post processing method only a subset of the dependencies are modified, the resulting parse is inconsistent: the score of some dependencies is computed on the basis of other dependencies that have been modified.

In order to compute a new optimal parse tree that preserves the modified dependencies, we have used a technique proposed in [START_REF] Mirroshandel | Active learning for dependency parsing using partially annotated sentences[END_REF] that modifies the scoring function of the parser in such a way that the dependencies that we want to keep in the parser output get better scores than all competing dependencies.

The double parsing method is therefore a three stage method. First, sentence S is parsed, producing the n-best parses. Then, the post processing method is used, modifying the first best parse. Let's note D the set of dependencies that were changed in this process. In the last stage, a new parse is produced, that preserves D.

Feature Based Method

In the feature based method, new features are added to the parser that rely on lexical affinity scores. These features are of the following form: C, l g , l d , δ C (s) , where C is a configuration number, s is the lexical affinity score (s = s(C, l g , l d )) and δ c (•) is a discretization function.

Discretization of the lexical affinity scores is necessary in order to fight against data sparseness. In this work, we have used Weka software [START_REF] Hall | The WEKA data mining software: an update[END_REF] to discretize the scores with unsupervised binning. Binning is a simple process which divides the range of possible values a parameter can take into subranges called bins. Two methods are implemented in Weka to find the optimal number of bins: equal-frequency and equal-width. In equalfrequency binning, the range of possible values are divided into k bins, each of which holds the same number of instances. In equal-width binning, which is the method we have used, the range are divided into k subranges of the same size. The optimal number of bins is the one that minimizes the entropy of the data. Weka computes different number of bins for different configurations, ranging from 4 to 10. The number of new features added to the parser is equal to C B(C) where C is a configuration and B(C) is the number of bins for configuration C.

Evaluation

The three methods described above have been evaluated on FTB TEST. Results are reported in table 11. The three methods outperformed the baseline (the state of the art parser for French which is a second order graph based method) [START_REF] Bohnet | Very high accuracy and fast dependency parsing is not a contradiction[END_REF]. The best performances were obtained by the Double Parsing method that achieved a labeled relative error reduction of 7, 1% on predicted POS tags, yielding the best parsing results on the French Treebank. It performs better than the Post Processing method, which means that the second parsing stage corrects some inconsistencies introduced in the Post Processing method. The performances of the Feature Based method are disappointing, it achieves an error reduction of 1.4%. This result is not easy to interpret. It is probably due to the limited number of new features introduced in the parser. These new features probably have a hard time competing with the large number of other features in the training process. Table 11: Parser accuracy on FTB TEST using the standard parser (BL) the post processing method (PP), the double parsing method (DP) and the feature based method.

Conclusion

Computing lexical affinities, on large corpora, for specific lexico-syntactic configurations that are hard to disambiguate has shown to be an effective way to increase the performances of a parser. We have proposed in this paper one method to compute lexical affinity scores as well as three ways to introduce this new information in a parser. Experiments on a French corpus showed a relative decrease of the error rate of 7.1% Labeled Accuracy Score.

Figure 1 :

 1 Figure 1: Distribution of the types of errors

Table 1 :

 1 Size and decomposition of the French Treebank

	. The size of the tree-

Table 3 :

 3 The 13 most common error types

Table 4 :

 4 List of the 9 configurations.

Table 5 :

 5 sizes of the corpora used to gather lexical counts ered for every lemma l its number of occurrences as governor (resp. dependent) of configuration C in the corpus, noted C(C, l, * ) (resp. C(C, * , l)), as well as the number of occurrences of configuration C with lemma l g as a governor and lemma l d as a dependent, noted C(C, l g , l d ). We are now in a position to compute the score s(C, l g , l d ). This score should reflect the tendency of l g and l d to appear together in configuration C. It should be maximal if whenever l g occurs as the governor of configuration C, the dependent position is occupied by l d and, symmetrically, if whenever l d occurs as the dependent of configuration C, the governor position is occupied by l g . A function that conforms such a behavior is the following:

Table 6 :

 6 Coverage of the lexical resource over FTB DEV.

	.	occ. cov. T cov.
	OBJ	1017	709 0.70 0.21
	SBJ	1210	825 0.68 0.24
	ADJ	1791 1239 0.69 0.33
	NdeN 1909 1287 0.67 0.31
	VdeN	189	107 0.57 0.16
	NaN	123	61 0.50 0.20
	VaN	422	273 0.65 0.23
	NcN	220	55 0.25 0.10
	VcV	165	93 0.56 0.04
	Σ	7046 4649 0.66 0.27

Table 8 :

 8 Correction Rate of the lexical resource with respect to FTB DEV.

Table 9 :

 9 Coverage and Correction Rate on FTB DEV for several values of ambiguity threshold.

			CR	cov/CR	cov/CR
	OBJ	0.70/0.29	0.58/0.36	0.52/0.36	0.35/0.38
	SBJ	0.68/0.23	0.64/0.23	0.62/0.23	0.52/0.23
	ADJ	0.69/-0.62 0.61/-0.52 0.56/-0.52 0.43/-0.38
	NdeN 0.67/-0.48 0.58/-0.53 0.52/-0.52 0.38/-0.41
	VdeN	0.57/0.75	0.44/0.73	0.36/0.73	0.20/0.30
	NaN	0.50/0.48	0.34/0.42	0.28/0.45	0.15/0.48
	VaN	0.65/0.75	0.50/0.8	0.41/0.80	0.26/0.48
	NcN	0.25/-0.09	0.19/0	0.16/0.02	0.07/0.13
	VcV	0.56/-0.23 0.42/-0.07	0.28/0.03	0.08/0.07
	Avg	0.66/0.2	0.57/0.23	0.51/0.24	0.38/0.17

Table 10 :

 10 Correction Rate on FTB DEV when taking into account parser confidence.

	Conf. OBJ SUJ ADJ NdeN VdeN
	CR	0.45 0.46 0.14	0.05	0.73
	Conf. NaN VaN NcN	VcV	Σ
	CR	0.12	0.8	0.12	0.1	0.4

One can note, that contrary to coverage, CR does not measure a characteristic of the lexical resource alone, but the lexical resource combined with a parser.

Acknowledgments

This work has been funded by the French Agence Nationale pour la Recherche, through the projects SEQUOIA (ANR-08-EMER-013) and EDYLEX (ANR-08-CORD-009).


Joseph Le Roux
email: leroux@univ-paris13.fr

Benoît Sagot
email: benoit.sagot@inria.fr

Djamé Seddah
email: djame.seddah@paris-sorbonne.fr

Statistical Parsing of Spanish and Data Driven Lemmatization

Although parsing performances have greatly improved in the last years, grammar inference from treebanks for morphologically rich languages, especially from small treebanks, is still a challenging task. In this paper we investigate how state-of-the-art parsing performances can be achieved on Spanish, a language with a rich verbal morphology, with a non-lexicalized parser trained on a treebank containing only around 2,800 trees. We rely on accurate part-of-speech tagging and datadriven lemmatization in order to cope with lexical data sparseness. Providing state-ofthe-art results on Spanish, our methodology is applicable to other languages.

Introduction

Grammar inference from treebanks has become the standard way to acquire rules and weights for parsing devices. Although tremendous progress has been achieved in this domain, exploiting small treebanks is still a challenging task, especially for languages with a rich morphology. The main difficulty is to make good generalizations from small example sets exhibiting data sparseness. This difficulty is even greater when the inference process relies on semi-supervised or unsupervised learning techniques which are known to require more training examples, as these examples do not explicitly contain all the information.

In this paper we want to explore how we can cope with this difficulty and get state-of-the-art syntactic analyses with a non-lexicalized parser that uses modern semisupervised inference techniques. We rely on accurate data-driven lemmatization and partof-speech tagging to reduce data sparseness and ease the burden on the parser. We try to see how we can improve parsing structure predictions solely by modifying the terminals and/or the preterminals of the trees. We keep the rest of the tagset as is. In order to validate our method, we perform experiments on the Cast3LB constituent treebank for Spanish (Castillan). This corpus is quite small, around 3,500 trees, and Spanish is known to have a rich verbal morphology, making the tag set quite complex and difficult to predict. [START_REF] Cowan | Morphology and reranking for the statistical parsing of spanish[END_REF] and [START_REF] Chrupała | Towards a machine-learning architecture for lexical functional grammar parsing[END_REF] already showed interesting results on this corpus that will provide us with a comparison for this work, especially on the lexical aspects as they used lexicalized frameworks while we choose PCFG-LAs.

This paper is structured as follows. In Section 2 we describe the Cast3LB corpus in details. In Section 3 we present our experimental setup and results which we discuss and compare in Section 4. Finally, Section 5 concludes the presentation.

Data Set

The Castillan 3LB treebank [START_REF] Civit | Building cast3lb: A spanish treebank[END_REF]) contains 3,509 constituent trees with functional annotations. It is divided in training (2,806 trees), development (365 trees) and test (338 trees).

We applied the transformations of [START_REF] Chrupała | Towards a machine-learning architecture for lexical functional grammar parsing[END_REF] to the corpus where CP and SBAR nodes are added to the subordinate and relative clauses but we did not perform any other transformations, like the coordination modification applied by [START_REF] Cowan | Morphology and reranking for the statistical parsing of spanish[END_REF].

The Cast3LB tag set is rich. In particular part-ofspeech (POS) tags are fine-grained and encode precise morphological information while non-terminal tags describe subcategorization and function labels.

Without taking functions into account, there are 43 non-terminal tags. The total tag set thus comprises 149 symbols which makes the labeling task challenging.

The rich morphology of Spanish can be observed in the treebank through word form variation. Table 1 shows some figures extracted from the corpus (training, development and test). In particular the word form/lemma ratio is 1.54, which is similar to other Romance language treebanks (French FTB and Italian ITB). Thus, we are confronted with a small treebank with a rich tagset and a high word diversity. All these conditions make the corpus a case in point for building a parsing architecture for morphologicallyrich languages.

Experiments

We conducted experiments on the Cast3LB development set in order to test various treebank modifications, that can be divided in two categories:

1. modification of the preterminal symbols of the treebank by using simplified POS tagsets;

2. modification of the terminal symbols of the treebank by replacing word tokens by lemmas.

Experimental Setup

In this section we describe the parsing formalism and POS tagging settings used in our experiments.

PCFG-LAs

To test our hypothesis, we use the grammatical formalism of Probabilistic Context-Free Grammars with Latent Annotations (PCFG-LAs) [START_REF] Matsuzaki | Probabilistic cfg with latent annotations[END_REF][START_REF] Petrov | Learning accurate, compact, and interpretable tree annotation[END_REF]. These grammars depart from the standard PCFGs by automatically refining grammatical symbols during the training phase, using unsupervised techniques. They have been applied successfully to a wide range of languages, among which French [START_REF] Candito | Parsing word clusters[END_REF], German [START_REF] Petrov | Parsing german with latent variable grammars[END_REF], Chinese and Italian [START_REF] Lavelli | The berkeley parser at the evalita 2009 constituency parsing task[END_REF].

For our experiments, we used the LORG PCFG-LA parser implementing the CKY algorithm. This software also implements the techniques from [START_REF] Attia | Handling unknown words in statistical latent-variable parsing models for arabic, english and french[END_REF] for handling out-of-vocabulary words, where interesting suffixes for part-of-speech tagging are collected on the training set, ranked according to their information gain with regards to the partof-speech tagging task. Hence, all the experiments are presented in two settings. In the first one, called generic, unknown words are replaced with a dummy token UNK, while in the second one, dubbed IG, we use the collected suffixes and typographical information to type unknown words. 1 We retained the 30 best suffixes of length 1, 2 and 3.

The grammar was trained using the algorithm of [START_REF] Petrov | Improved inference for unlexicalized parsing[END_REF] using 3 rounds of split/merge/smooth2 . For lexical rules, we applied the strategy dubbed simple lexicon in the Berkeley parser. Rare words -words occurring less than 3 times in the training set -are replaced by a special token, which depends on the OOV handling method (generic or IG), before collecting counts.

POS tagging

We performed parsing experiments with three different settings regarding POS information provided as an input to the parser: (i) with no POS information, which constitutes our baseline; (ii) with gold POS information, which can be considered as a topline for a given parser setting; (iii) with POS information predicted using the MElt POS-tagger (Denis and Sagot, 2009), using three different tagsets that we describe below.

MElt is a state-of-the-art sequence labeller that is trained on both an annotated corpus and an external lexicon. The standard version of MElt relies on Maximum-Entropy Markov models (MEMMs). However, in this work, we have used a multiclass perceptron instead, as it allows for much faster training with very small performance drops (see Table 2).

For training purposes, we used the training section of the Cast3LB (76,931 tokens) and the Leffe lexi-con [START_REF] Molinero | A morphological and syntactic wide-coverage lexicon for spanish: The leffe[END_REF], which contains almost 800,000 distinct (form, category) pairs. 3We performed experiments using three different tagsets:

• a baseline tagset which is identical to the tagset used by [START_REF] Cowan | Morphology and reranking for the statistical parsing of spanish[END_REF] and [START_REF] Chrupała | Towards a machine-learning architecture for lexical functional grammar parsing[END_REF]; with this tagset, the training corpus contains 106 distinct tags;

• the reduced2 tagset, which is a simplification of the baseline tagset: we only retain the first two characters of each tag from the baseline tagset; with this tagset, the training corpus contains 42 distinct tags;

• the reduced3 tagset, which is a variant of the reduced2 tagset: contrarily to the reduced2 tagset, the reduced3 tagset has retained the mood information for verb forms, as it proved relevant for improving parsing performances as shown by [START_REF] Cowan | Morphology and reranking for the statistical parsing of spanish[END_REF]; with this tagset, the training corpus contains 57 distinct tags.

Melt POS tagging accuracy on the Cast3LB development set for these three tagsets is given in Table 2, with overall figures together with figures computed solely on unknown words (words not attested in the training corpus, i.e., as high as 13.5 % of all tokens).

Baseline

The first set of experiments was conducted with the baseline POS tagset. Results are summarized in Table 3. This table presents parsing statistics on the Cast3LB development set in the 3 POS settings introduced above (i) no POS provided, (ii) gold POS provided and (iii) predicted POS provided. For each POS tagging setting it shows labeled precision, labeled recall, labeled F1-score, the percentage of exact match and the POS tagging accuracy. The latter needs not be the same as presented in Section 3.1.2 because (i) punctuation is ignored and (ii) if the parser cannot use the information provided by the As already mentioned above, this tagset contains 106 distinct tags. On the one hand it means that POS tags contain useful information. On the other hand it also means that the data is already sparse and adding more sparseness with the IG suffixes and typographical information is detrimental. This is a major difference between this POS tagset and the two following ones.

Using simplified tagsets

We now turn to the modified tagsets and measure their impact on the quality of the syntactic analyses. Results are summarized in Table 4 for the reduced2 tagset and in Table 5 for reduced3. In these two settings, we can make the following remarks.

• Parsing results are better with reduced3, which indicates that verbal mood is an important feature for correctly categorizing verbs at the syntactic level.

• When POS tags are not provided, using suffixes and typographical information improves OOV word categorization and leads to a better tagging accuracy and F1 parsing score (78.94 vs. 81.81 for reduced2 and 79.69 vs. 82.44 for re-duced3).

• When providing the parser with POS tags, whether gold or predicted, both settings show an interesting difference w.r.t. to unknown words handling. When using reduced2, the IG setting is better than the generic one, whereas the situation is reversed in reduced3. This indicates that reduced2 is too coarse to help finely categorizing unknown words and that the refinement brought by IG is beneficial, however the added sparseness. For reduced3 it is difficult to say whether it is the added richness of the POS tagset or the induced OOV sparseness that explains why IG is detrimental.

Lemmatization Impact

Being a morphologically rich language, Spanish exhibits a high level of inflection similar to several other Romance languages, for example French and Italian (gender, number, verbal mood). Furthermore, Spanish belongs to the pro-drop family and clitic pronouns are often affixed to the verb and carry functional marks. This makes any small treebank of this language an interesting play field for statistical parsing. In this experiment, we want to use lemmatization as a form of morphological clustering. To cope with the loss of information, we provide the parser with predicted POS. Lemmatization is carried out by the morphological analyser of MORFETTE, [START_REF] Chrupała | Learning morphology with morfette[END_REF] To make the parser less sensitive to lemmatization and tagging errors, we train both tools on a 20 jackkniffed setup4 . Resulting lemmas and POS tags are then reinjected into the train set. The test corpora is itself processed with tools trained on the unmodified treebank. Results are presented Table 7. They show an overall small gain, compared to the previous experiments but provide a clear improvement on the richest tagset, which is the most difficult to parse given its size (106 tags).

First we remark that Tagging accuracy with the baseline tagset when no POS is provided is lower than previously observed. This can be easily explained: it is more difficult to predict POS with morphological information when morphological information is withdrawn from input.

Second, and as witnessed before, reduction of the POS tag sparseness using a simplified tagset and increase of the lexical sparseness by handling OOV words using typographical information have adverse effects. This can be observed in the generic Predicted POS section of tagset is the best option. On the other hand, in IG Predicted POS, using the reduced3 is better than baseline and reduced2. Again this tagset is a tradeoff between rich information and data sparseness.

In all cases reduced2 is below the other tagsets wrt. to Parseval F1 although tagging accuracy is better. We can conclude that it is too poor from an informational point of view.

Discussion

There is relatively few works actively pursued on statistical constituency parsing for Spanish. The initial work of [START_REF] Cowan | Morphology and reranking for the statistical parsing of spanish[END_REF] consisted in a thorough study of the impact of various morphological features on a lexicalized parsing model (the Collins Model 1) and on the performance gain brought by the reranker of [START_REF] Collins | Discriminative reranking for natural language parsing[END_REF] used in conjunction with the feature set developed for English. Direct comparison is difficult as they used a different test set (approximately, the concatenation of our development and test sets). They report an F-score of 85.1 on sentences of length less than 40. 5However, we are directly comparable with Chrupała (2008)6 who adapted the Collins Model 2 to Spanish. As he was focusing on wide coverage LFG grammar induction, he enriched the non terminal annotation scheme with functional paths rather than trying to obtain the optimal tagset with respect to pure parsing performance. Nevertheless, using the same split and providing gold POS, our system provides better performance (around 2.3 points better, see Table 8).

It is of course not surprising for a PCFG-LA model to outperform a Collins' model based lexicalized parser. However, it is a fact that on such small treebank configurations PCFG-LA are crucially lacking annotated data. It is only by greatly reducing the POS tagset and using either a state-ofthe-art tagger or a lemmatizer (or both), that we can boost our system performance. The sensitivity of PCFG-LA models to lexical data sparseness was also shown on French by [START_REF] Seddah | Cross parser evaluation and tagset variation: A French Treebank study[END_REF]. In fact they showed that performance of state-of-the-art lexicalized parsers (Charniak, Collins models, etc.) were crossing that of Berkeley parsers when the training set contains around 2500-3000 sentences. Here, with around 2,800 sentences of training data, we are probably in a setting where both parser types exhibit similar performances, as we suspect French and Spanish to behave in the same way. It is therefore encouraging to notice that our approach, which relies on accurate POS tagging and lemmatization, provides state-of-the-art performance.

Conclusion

In this paper we presented several experiments reporting the impact of lexical sparseness reduction on non lexicalized statistical parsing. We showed that, by using state-of-the-art lemmatization and POS tagging on a reduced tagset, parsing performance can be on a par with lexicalized models that manage to extract more information from a small corpus exhibiting a rich lexical diversity. It remains to be seen whether applying the same kind of simplifications to the rest of the tagset, i.e. on the internal nodes, can further improve parse structure quality.

Finally, the methods we presented in this paper are not language specific and can be applied to other languages if similar resources exist.

Table 1 :

 1 C3LB properties

	# of tokens	94 907
	# of unique word forms 17 979
	# of unique lemmas	11 642
	ratio word form/lemma 1.54

Table 2 :

 2 MElt POS tagging accuracy on the Cast3LB development set for each of the three tagsets. We provide results obtained with the standard MElt algorithm (MEMM) as well as with the multiclass perceptron, used in this paper, for which training is two orders of magnitude faster. Unknown words represent as high as 13.5 % of all words. tagger, it is discarded and the parser performs POStagging on its own.

	TAGSET		baseline reduced2 reduced3
	Nb. of tags		106	42	57
	Multiclass Perceptron
	Overall Acc.	96.34	97.42	97.25
	Unk. words Acc. 91.17	93.35	92.30
	Maximum-Entropy Markov model (MEMM)
	Overall Acc.	96.46	97.42	97.25
	Unk. words Acc. 91.57	93.76	92.87
	MODEL	LP	LR	F1 EXACT	POS
	Word Only
	Generic 81.42 81.04 81.23	14.47 90.89
	IG	80.15 79.60 79.87	14.19 85.01
	Gold POS
	Generic 87.83 87.49 87.66	30.59 99.98
	IG	86.78 86.53 86.65	27.96 99.98
	Pred. POS
	Generic 84.47 84.39 84.43	22.44 95.82
	IG	83.60 83.66 83.63	21.78 95.82
	Table 3: Baseline PARSEVAL scores on Cast3LB dev. set
	(≤ 40 words)

Table 6 :

 6 while POS tagging is done by the MElt tagger. Lemmatization performances are on a par with previously reported results on Romance languages (see Table6) Lemmatization performance on the Cast3LB.

	TAGSET	ALL	SEEN UNK (13.84%)
	baseline 98.39 99.01	94.55
	reduced2 98.37 98.88	95.18
	reduced3 98.24 98.88	94.23

Table 7 :

 7 Table 7 where the baseline Lemmmatization Experiments

	TAGSET	LR	LP	F1	EX	POS
	Word Only -Generic
	baseline 79.70 80.51	80.1	15.23 74.04
	reduced2 79.19 79.78 79.48 15.56 89.25
	reduced3 79.92 80.03 79.97 13.16 87.67
	Word Only -IG
	baseline 80.67 81.32 80.99 15.89 75.02
	reduced2 80.54	81.3	80.92 15.13 90.93
	reduced3 80.52 80.94 80.73 15.13 88.53
	Pred. POS -Generic
	baseline 85.03 85.57 85.30 23.68 95.68
	reduced2 83.98 84.73 84.35 23.36 96.78
	reduced3 84.93 85.19 85.06 21.05 96.60
	Pred. POS -IG
	baseline 84.60 85.06 84.83 23.68 95.68
	reduced2 84.29 84.82 84.55 21.71 96.78
	reduced3 84.86 85.39 85.12 22.70 96.60

Table 8 :

 8 PARSEVAL F-score results on the Cast3LB test set

Names generic and IG originally come from[START_REF] Attia | Handling unknown words in statistical latent-variable parsing models for arabic, english and french[END_REF].

We tried to perform 4 and 5 rounds but

rounds proved to be optimal on this corpus.

Note that MElt does not use information from the external lexicon as constraints, but as features. Therefore, the set of categories in the external lexicon need not be identical to the tagset. In this work, the Leffe categories we used include some morphological information (84 distinct categories).

The training set is split in 20 chunks and each one is processed with a tool trained on the 19 other chunks. This enables the parser to be less sensitive to lemmatization and/or pos tagging errors.

See http://pauillac.inria.fr/~seddah/ spmrl-spanish.html for details on comparison with that work.

We need to remove CP and SBAR nodes to be fairly comparable.

Acknowledgments

Thanks to Grzegorz Chrupała and Brooke Cowan for answering our questions and making data available to us. This work is partly funded by the French Research Agency (EDyLex, ANR-09-COORD-008).


Pierre Lissy
email: lissy@ann.jussieu.fr

A link between the cost of fast controls for the 1-D heat equation and the uniform controllability of a 1-D transport-diusion equation

In this note, we explain how results on the cost of the null-controllability of the one-dimensional heat equation in small time can be used to bound from above the cost of the null-controllability of a one-dimensional transport-diusion equation in the vanishing viscosity limit. We improve previous results about the minimal time needed to obtain the exponential decrease of the cost of the control and explain what would provide the usual conjecture concerning the cost of fast controls for the heat equation.

Résumé

Un lien entre le coût des contrôles rapides pour l'équation de la chaleur 1-D et l'uniforme contrôlabilité d'une équation de transport-diusion 1-D.

Dans cette note, on explique comment des résultats sur le coût de la contrôlabilité à 0 de l'équation de la chaleur en temps petit peuvent être utilisés pour majorer le coût de la contrôlabilité à 0 d'une équation unidimensionelle de transport-diusion dans la limite de viscosité évanescente. On améliore des résultats précédemment connus concernant le temps minimal nécessaire pour obtenir la décroissance exponentielle du coût du contrôle et on explique ce que donnerait en plus la conjecture habituelle concernant le coût du contrôle en temps petit de l'équation de la chaleur.

Version française abrégée Version française abrégée

Dans cette note, nous nous intéresserons principalement à l'équation de transport-diusion contrôlée sur le bord gauche (1), où T > 0, M = 0, ε > 0 et L > 0, la condition initiale y 0 étant dans L 2 (0, L) et le contrôle v dans L 2 (0, T ). Cette équation est unidimensionelle et parabolique, sa contrôlabilité à zéro est donc connue depuis longtemps (cf. [START_REF] Fattorini | Exact controllability theorems for linear parabolic equations in one space dimension[END_REF], ou plus récemment [START_REF] Fursikov | Controllability of evolution equations[END_REF] et [START_REF] Lebeau | Contrôle exact de l'équation de la chaleur[END_REF] pour des résultats en dimension supérieure). Quand ε → 0 + nous obtenons une équation de transport à vitesse constante M , qui est contrôlable à 0 si et seulement si T L/|M |, le contrôle étant alors la fonction nulle. Il serait donc naturel de penser que pour ε → 0 + , le coût L 2 du contrôle (déni à la deuxième ligne de (3)) explose si T < L/|M | et tend vers 0 quand T L/|M |. Pourtant, dans [START_REF] Coron | Singular optimal control: a linear 1-D parabolic-hyperbolic example[END_REF] il est démontré que si M > 0 le coût du contrôle explose bien dès que T < L/M , mais si M < 0 alors le contrôle explose dès que T < 2L/|M |, ce qui est plus surprenant. Dans le même article, les auteurs ont prouvé que le coût du contrôle tendait exponentiellement vers 0 quand ε → 0 + pour T > 4.3L/M si M > 0 et T > 57.2L/|M | si M < 0. Les principales techniques utilisées dans ce papier sont d'une part des résultats sur les zéros des fonctions entières, d'autre part une inégalité de type Carleman sur le système adjoint ainsi qu'une inégalité de dissipation d'énergie spécique à cette équation. Les constantes 4.3 et 57.2 ont été améliorées dans [START_REF] Glass | A complex-analytic approach to the problem of uniform controllability of a transport equation in the vanishing viscosity limit[END_REF] en respectivement 4.2 et 6.1 en utilisant une méthode semblable à la méthode des moments (avec un multiplicateur complexe bien choisi). On conjecture de manière naturelle que les constantes optimales sont respectivement 1 et 2.

D'un autre côté, on s'intéresse à l'équation de la chaleur contrôlée au bord (2), avec les mêmes notations. Appelons γ la plus petite constante telle que le coût L 2 du contrôle de (2) (déni à la première ligne de (3)) sur (0, T ) soit majoré par C(L)e γ+ 2T pour T assez petit et pour une certaine constante C(L) ne dépendant pas de T , la notation γ+ signiant que l'on peut prendre n'importe quelle constante γ > γ, aussi proche de γ que l'on veut (la constante C(L) explosant au fur et à mesure que l'on s'approche de γ). On sait que nécessairement γ L 2 /2 (cf. [START_REF] Miller | Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF]) et la meilleure majoration obtenue sur γ à ce jour est γ 3L 2 /2 (cf. [START_REF] Tenenbaum | New blow-up rates for fast controls of Schrödinger and heat equations[END_REF]). Il est en fait conjecturé (cf. par exemple [START_REF] Ervedoza | Sharp observability estimates for heat equations[END_REF]) que nous avons exactement γ = L 2 /2. Le but de ce papier est de montrer que l'on peut relier le coût quand ε → 0 + de la contrôlabilité de [START_REF] Coron | Singular optimal control: a linear 1-D parabolic-hyperbolic example[END_REF] en temps grand avec le coût de la contrôlabilité de (2) cette fois-ci en temps petit. Le résultat principal est le suivant. Theorem 0.1 On suppose

T > (2 √ 3 + 1 -sign(M ))L |M | .
Il existe alors une certaine constante K > 0 (dépendant uniquement de |M | et L) et une certaine constante C > 0 (dépendant des mêmes variables) telles que, pour tout ε > 0 susamment petit, et tout y 0 ∈ L 2 (0, L), il existe une solution (y ε , v ) du problème de contrôle [START_REF] Coron | Singular optimal control: a linear 1-D parabolic-hyperbolic example[END_REF] vériant y ε (T, .) = 0 et

||v ε || L 2 (0,T ) Ce -K ε ||y 0 || L 2 (0,L) .
De plus, si l'on suppose que γ = L 2 /2, alors on a le même résultat dès que

T > (3 -sign(M ))L |M | .
Le principal argument est de remarquer que l'on peut passer d'une solution de (1) à une solution de

(2) (sur un intervalle de temps εT qui tend maintenant vers 0 quand ε → 0) grâce au changement de variable suivant :

u(t, x) = e M 2 t 4ε 2 -M x 2ε y( t ε , x).
Des calculs élémentaires permettent alors de majorer le coût du contrôle de (1) en fonction de celui de [START_REF] Ervedoza | Sharp observability estimates for heat equations[END_REF]. On conclut ensuite en utilisant le résultat précédemment cité de [START_REF] Tenenbaum | New blow-up rates for fast controls of Schrödinger and heat equations[END_REF] et en regardant l'inuence de la conjecture γ = L 2 /2 sur les calculs.

Introduction

We consider some time T > 0, some speed M = 0, some diusion coecient ε > 0 and some length L > 0. We are interested in the following controlled transport-diusion equation on [0, T ] × [0, L], with initial condition y 0 ∈ L 2 (0, L) and with control v ∈ L 2 (0, T ) at the left side of the boundary:

     y t -εy xx + M y x = 0 in (0, T ) × (0, L), y(., 0) = v(t) in (0, T ), y(., L) = 0 in (0, T ), (1)
This equation is a one-dimensional parabolic equation, whose null-controllability in small time has been known since a long time (see [START_REF] Fattorini | Exact controllability theorems for linear parabolic equations in one space dimension[END_REF], or more recently [START_REF] Fursikov | Controllability of evolution equations[END_REF] and [START_REF] Lebeau | Contrôle exact de l'équation de la chaleur[END_REF] for results in any space dimension).

If ε → 0 + we obtain a transport equation at constant speed M , which is null controllable if and only if T L/|M |, the control being the null function (hence the cost of the control is 0). It is then natural to expect that the cost of the control blows up as soon as T L/|M | and tends to 0 when T > L/|M |. However, it was shown in [START_REF] Coron | Singular optimal control: a linear 1-D parabolic-hyperbolic example[END_REF] that if M > 0 then the control blows up as soon as T < L/M , but if M < 0 then the control blows up as soon as T < 2L/|M |, which is more surprising. In the same paper, the authors proved the exponential decay of the cost of the control when ε → 0 + as soon as T > 4.3L/M if M > 0 and T > 57.2L/|M | if M < 0. The mains tools are on the one hand results on the roots of entire functions and on the other hand a Carleman estimate for solutions of the adjoint equation and a suitable dissipation estimate. The authors also raised the following natural conjecture: Conjecture 1 The cost of the control of (1) tends to 0 as ε → 0 + as soon as

T > (3 -sign(M ))L 2|M | .
This result was extended in several dimensions in [START_REF] Guerrero | Singular optimal control for a transport-diusion equation[END_REF] (with a speed M depending on the space and the time variables) for large enough times. The most recent result available comes from [START_REF] Glass | A complex-analytic approach to the problem of uniform controllability of a transport equation in the vanishing viscosity limit[END_REF]. The author improved the constant 4.3 and 57.2 of [START_REF] Coron | Singular optimal control: a linear 1-D parabolic-hyperbolic example[END_REF] to respectively 4.2 and 6.1 by using an approach which is similar to the momentum method: an inequality observability is proved by constructing a bi-orthogonal family (thanks to the Paley-Wiener theorem) to the family of exponentials appearing in the expression of the solution of (1) when it is decomposed on some appropriate orthogonal basis. The key point is the construction of a suitable complex multiplier.

On the other hand, let us recall some results concerning the following heat equation controlled on the left side

     u t -u xx = 0 in (0, T ) × (0, L), u(., 0) = w(t) in (0, T ), u(., L) = 0 in (0, T ), (2)
with initial condition u(0, .) = u 0 ∈ L 2 (0, L).

Let us call γ the best (that is to say the smallest) constant such that the L 2 cost of the control of ( 2) on (0, T ) is under the form C(L)e γ+ 2T for some C(L) depending only on L and for T > 0 small enough, the notation γ+ meaning that we can choose any constant γ > γ as close as γ as we want (the constant C(L) explodes when γ → γ). It is known that we have (see [START_REF] Miller | Geometric bounds on the growth rate of null-controllability cost for the heat equation in small time[END_REF]) γ L 2 /2 and the best upper bound on γ obtained for the time being is (see [START_REF] Tenenbaum | New blow-up rates for fast controls of Schrödinger and heat equations[END_REF]) γ 3L 2 /2. However, it is conjectured (see for example [START_REF] Ervedoza | Sharp observability estimates for heat equations[END_REF]) that Conjecture 2 γ = L 2 /2.

We are now going to present the main result of this note.

Theorem 1.1 Assume that T > (2 √ 3 + 1 -sign(M ))L |M | .
Then there exists some constant K > 0 depending only on |M | and L, there exists some constant C > 0 (depending on the same variables) such that, for all ε > 0 and all y 0 ∈ L 2 (0, L), there exists a solution (y ε , v ) of the control problem (1) verifying y ε (T, .) = 0 and

||v ε || L 2 (0,T ) Ce -K ε ||y 0 || L 2 (0,L) .
Moreover, if we assume that the conjecture γ = L 2 /2 is veried, then one can state the same result as soon as

T > (3 -sign(M ))L |M | .
2 Proof of Theorem 1.1

From now on, let us call C D (T, L) the cost of the control of (2), and C T D (T, L, M, ε) the cost of the control of (1), that is to say 1) and y(T,.)=0

           C D (T, L) = sup u 0 ∈L 2 (0,L) inf (u,w) veries (2) and u(T,.)=0 ||w|| L 2 (0,T ) ||u 0 || L 2 (0,T ) , C T D (T, L, M, ε) = sup y 0 ∈L 2 (0,L) inf (y,v) veries (
||v|| L 2 (0,T ) ||y 0 || L 2 (0,T ) .

(

) 3
We give a lemma that enable us to link these quantities.

Lemma 2.1 For all T 0 < T , one has

           C T D (T, L, M, ε) e -M 2 T 0 4ε √ ε C D (ε(T -T 0 ), L) if M > 0, C T D (T, L, M, ε) e -M 2 T 0 4ε + |M |L 2ε √ ε C D (ε(T -T 0 ), L) if M < 0. ( 4
)
Proof of Lemma 2.1

We consider the following function:

u(t, x) := e M 2 t 4ε 2 -M x 2ε y( t ε , x),
where y veries (1). The function

u is dened on [0, εT ] × [0, L]. Moreover u t (t, x) -u xx (t, x) = e M 2 t 4ε 2 -M x 2ε ( M 2 4ε 2 y + y t ε - M 2 4ε 2 y -y xx + M ε y x ) = 0,
where y is considered in the previous inequality at point ( t ε , x). Finally u veries (2) (the nal time T being replaced by εT with initial condition u 0 (x) := e -M x 2ε y 0 (x) and control w(t) := e M 2 t 4ε 2 v(t/ε). Let us from now on call S := εT and S 0 := εT 0 . We can control (2) with w acting only on (S 0 , S) (i.e.

we impose the control to vanish on (0, S 0 )) at optimal cost C H (S -S 0 , L). Calling v(t) := e -M 2 t 4ε w(εt),

we obtain ||w(t)|| L 2 (S0,S) = √ ε||e M 2 t 4ε v(t)|| L 2 (T0,T ) C H (S -S 0 , L)||u(S 0 , x)|| L 2 (0,L) C H (S -S 0 , L)||u 0 || L 2 (0,L) .
(the last inequality holds because u veries the heat equation with null Dirichlet boundary conditions on (0, S 0 ) since we do not act on (0, S 0 )). This notably implies

||v(t)|| L 2 (T0,T ) 1 √ ε e -M 2 T 0 4ε C H (S -S 0 , L)||u 0 || L 2 (0,L) . (5)
Using now e -M x 2ε

1 for M > 0 and e -M x 2ε e |M |L 2ε
for M < 0, one easily deduces (4) from [START_REF] Glass | A complex-analytic approach to the problem of uniform controllability of a transport equation in the vanishing viscosity limit[END_REF].

We can now prove Theorem 1. Let us introduce a (numerical) constant a such that T = aL/|M | which will be chosen large enough to obtain the uniform controllability, and s 1 such that S 0 = εsaL/|M |,.

We have S = εaL/|M |. We then call T 0 := S 0 /ε = saL/|M |. Let us assume that C H (S)

C(L)e b + L 2 S
for some b > 0 and S small enough.(the constant C(L) does not depend on ε because ε appears now only in the time variable). We have then for ε small enough

C T D (T, L, M, ε) C(L) √ ε e -asM L 4ε + bLM ε(1-s)a .
If we want to obtain a decrease rate in ε under the form e -K ε , for some K > 0, it is sucient to have -sM La/4ε + bLM /ε(1 -s)a < 0, i.e. b/(1 -s)a < as/4, i.e. 4b < a 2 s(1 -s). One choose s = 1/2 so that s(1 -s) = 1/4 is maximum. We obtain a > 4

√

b. As explained in the introduction, the best upper bound on γ (see [START_REF] Tenenbaum | New blow-up rates for fast controls of Schrödinger and heat equations[END_REF]) is γ 3L 2 /2, which corresponds to b 3/4. Hence we may take any a > 2 √

3.

The hypothesis γ = L 2 /2 corresponds to b = 1/4, which implies a > 2. Theorem 1.1 is proved in the case M > 0. Finally, using the same notations as in the previous subsection

C T D (T, L, M, ε) e -as|M |L 4ε bL|M | ε(1-s)a + |M |L 2ε . One has -as|M |L/4ε + bL|M |/ε(1 -s)a + |M |L/2ε < 0 as soon as b/(1 -s)a < sa -1/2, i.e. b/a 2 < s(1 -s)/4 -(1 -s)/2a.
Optimizing s in order to maximize the right-hand side gives us s = 1/2 + 2/a. Since s 1 we should have a 4 (which will be veried at the end of the proof ). We obtain that it is sucient to have b/a 2 < (2 -a) 2 /16a 2 , i.e. a > 4 √ b + 2. We know that b 3/4, hence we may take any a > 2 √ 3 + 2(> 4). The hypothesis b = 1/4 would imply a > 4, and the proof of Theorem 1.1 is completed.

3 Additional comments 1. One sees here that any new upper bound of γ would automatically provide an improvement in our problem concerning (1): our proof provides that if γ 2b/L 2 (the b being the same as in the previous section) then one would obtain the exponential decay of the cost of the control of (1) for

T > (4 √ b + 1 -sign(M ))L/|M |.
2. The strategy we propose (which consists in doing nothing on some interval of time (0, T 0 )) does not seem to be optimal. This may explain that our strategy cannot enable us to deduce Conjecture 1 from Conjecture 2. Moreover, some numerical evidences (see [START_REF] Salem | A numerical study of the null boundary controllability of a convection diusion equation[END_REF]) seem to indicate that if M > 0 then the optimal constant is between 1 and 1.6 and cannot be as big as 2. The conclusion that may be drawn is that our work does not question Conjecture 1, and that trying to compare (1) and

(2) can only improve existing results but we lose too much informations in our transformation to hope to obtain an optimal result.

3. We used a transformation which changed a solution y of (1) into a solution z of (2) and that put all the dependence to ε in the time variable. One can easily verify that the changing of variable we propose is the only one that can achieve simultaneously these two goals. One could nd other changes of variables where the length of the interval depends on ε, but they cannot be used because we do not know precisely enough how the constants in the inequality observability for the heat equation depends on the geometry of the problem. Notably, one cannot use [START_REF] Tenenbaum | New blow-up rates for fast controls of Schrödinger and heat equations[END_REF], which considers only the dependence of the constants in the time variable when it tends to 0.

2 . 1 Case M > 0

 210 Thanks to Lemma (2.1), one hasC T D (T, L, M, ε) e -aM Ls 4ε √ ε C H (S -S 0 , L).

2 . 2 Case M < 0

 220 Thanks to Lemma (2.1), one hasC T D (T, L, M, ε) e -a|M |Ls 4ε + |M |L 2ε C H (S -S 0 , L).

Work supported by the ERC advanced grant 266907 (CPDENL) of the 7th Research Framework Programme (FP7)