Cécile Fabre
email: cecile.fabre@univ-tlse2.fr

Anna Kupsc
email: akupsc@u-bordeaux3.fr

Large and noisy vs. small and reliable combining 2 types of corpora for adjective valence extraction

This work investigates a possibility of combining two different types of corpora to build a valence lexicon for French adjectives. We complete adjectival frames extracted from a Treebank with statistical cues computed from a large automatically parsed corpus. This experiment shows how linguistic knowledge and large amount of annotated data can be used in a complementary manner.

Introduction

Valency lexicons contain subcategorisation information related to every predicate: in general, the number and type of arguments selected by a predicate (for example, by a verb). As such information is highly lexical and language-dependent, it has to be specified separately for each predicate of the language. In addition to the language learning value, valency lexicons are crucial resources for various NLP tasks and applications, such as parsing [START_REF] Carroll | The automatic acquisition of verb subcategorisations and their impact on the performance of an HPSG parser[END_REF], generation [START_REF] Danlos | La génération automatique de textes[END_REF], information extraction [START_REF] Surdeanu | Using predicate-argument structures for information extraction[END_REF] or machine translation [START_REF] Han | Handling structural divergences and recovering dropped arguments in a Korean/English machine translation system[END_REF]. Initially, such resources have been created manually based on linguistic knowledge of human experts, see among others, (Procter, 1978) and [START_REF] Hornby | Oxford Advanced Learner's Dictionary of Current English[END_REF] for English, or [START_REF] Gross | Méthodes en syntaxe[END_REF] and [START_REF] Mel'cuk | Dictionnaire explicatif et combinatoire du français contemporain[END_REF][START_REF] Mel'cuk | Dictionnaire explicatif et combinatoire du français contemporain[END_REF] for French. Although such lexicons are readable for humans, they cannot be directly used in computer applications. For example, the best known French valency lexicon of [START_REF] Gross | Méthodes en syntaxe[END_REF] is coded in tables which contain syntactic and semantic properties of predicates. However, the information in the tables is not always stated explicitly and has to be inferred from other properties, which complicates the automatic conversion process, see [START_REF] Gardent | Extraction d'information de souscatégorisation à partir des tables du LADL[END_REF] for details. Another issue related to the existing hand-crafted valency lexicons comes from their coverage as they are not always well-adjusted to contemporary texts. Recent developments in corpus linguistics provided a wide range of methods and resources which allow for creating valency lexicons well-suited for NLP tasks in various languages, see especially [START_REF] Frank | From treebank resources to LFG f-structures[END_REF], [START_REF] Preiss | A System for Large-scale Acquisition of Verbal, Nominal and Adjectival Subcategorization Frames from Corpora[END_REF] for methods based on syntactically annotated corpora.

The majority of valence resources has been created for verbs, and much less attention has been paid to specifying valency of other predicates, such as nouns or adjectives. For French, for instance, the two available valency lexicons for adjectives, [START_REF] Gross | Méthodes en syntaxe[END_REF] and [START_REF] Picabia | Les constructions adjectivales en français[END_REF], exist only on paper and have not been adapted to automatic processing. In this paper, we describe a method which allows us to create a valency lexicon of French adjectives, adjusted to NLP applications.

Our approach is corpus-based, and the lexicon is automatically extracted, but it combines two different types of corpora. On one hand, we use a relatively small (1 million words) corpus which has been manually revised and enriched with syntactic and functional annotations for major constituents. On the other hand, we have a large (200 million words) corpus automatically parsed, with no subsequent human validation, where the texts have been annotated with dependency relations. In none of the two corpora is the argument/adjunct distinction specified for dependents of adjectives. Our method consists in identifying adjective's arguments exploiting and combining properties of the two corpora: linguistic cues and frequency measures.

The organisation of the paper is as follows. First, we briefly present general properties of French adjectives and issues related to adjective valency. The next two sections describe extraction techniques specific to the two types of corpora. In Section 5, we discuss a method for refining results by adopting a less rigid argument/adjunct distinction. Section 6 concludes the paper and presents perspectives on our future research.

Properties of French adjectives

2.1. Types of arguments In French, complements of adjectives can be realised by three main categories: prepositional phrases (PP), subordinate clauses (Ssub) or infinitival phrases (VPinf).

(1) sûr [PP de son retour] / [Ssub qu'il reviendra] / [VPinf de revenir] sure of his return that-he will-come-back to come-back `sure of his return / that he will come back / to come back' Nominal phrases (NP), on the other hand, can serve only as the subject of an adjective 1 . We adopt the notion of the subject of an adjective both to predicative uses, (2)-( 3), where the adjective is a predicate on its own, and to attributive uses, (4), where the adjective modifies a noun that becomes its semantic argument and thus can be considered its semantic subject. Note that in addition to NP, the subject of an adjective can be expressed by Ssub or VPinf, (3).

(

Specificity of adjectival valence

Although the repertoire of syntactic phrases which can appear as arguments of adjectives is very limited, specifying valence of an adjective can be quite difficult.

First, traditional linguistic tests which help to separate arguments from adjuncts are less reliable than for verbs. For example, one of the strongest criteria used for verbs, the obligatory presence of an argument, is in most cases inapplicable to adjectives as surface realization of a complement is often optional, (5). In fact, [START_REF] Noailly | L'adjectif en français, Ophrys[END_REF] mentions just a few adjectives, such as enclin `inclined', exempt `exempted' or désireux `desirous', among those for which a complement is obligatory. Similarly, results of other `argumenthood' tests, e.g., topicalisation or pronominalisation, are in general less suitable than for verbs, cf. (Picabia, 1978: ch.3).

(5) Paul est amoureux (de sa voisine).

Paul is in love of his neighbour `Paul is in love (with his neighbour).'

Second, an alternative realization of a PP complement of an adjective is much more common than for verbs. For adjectives, several distinct prepositions may introduce the same semantic argument, see (6), cited after Picabia (1978:85). For verbs, if various prepositions are possible, they normally have to belong to the same semantic class, e.g., the verb habiter `to live ' accepts various PP complements (dans `in', sous `under', à `in/at', etc.) but they all form a uniform semantic group of locative prepositions. Adjectives seem to be more liberal in this respect as it is difficult to provide a common semantic class which can group avec `with ' and envers `towards' in (6).

(6) Jean est aimable envers / avec Marie.

Jean is pleasant towards with Mary `Jean is nice towards/with Mary.'

Finally, similarly to verbs, adjectives may participate in many syntactic constructions, for example comparatives or impersonals. It is essential to distinguish components of such highlevel constructions from arguments of adjectives. Unlike valency, which depends on individual properties of an adjective, components of productive constructions are much less sensitive to specific adjectives. For example, PP in ( 7) is part of the superlative construction and it is not required by the adjective itself: beau `beautiful' could be replaced by almost any other adjective.

(7) le plus beau [ PP de la terre] the most beautiful of the earth `the most beautiful on earth'

The above properties of adjectives make valence identification rather challenging. In this paper, due to two different types of corpora, we approach the issue from two different perspectives. On one hand, due to rigid syntactic annotations in the Treebank and linguistic knowledge, we aim at separating valency from components of high-level constructions. On the other hand, large amount of data in the other corpus allow us to adopt frequency tests to detect arguments and verify their variability. The next two sections provide a description of the two techniques.

Extracting frames from the treebank

3.1. Treebank As mentioned above, in the first step, we explore a relatively small (1 million words) but richly annotated corpus. We use the Treebank of Paris 7 [START_REF] Abeillé | Building a treebank for French[END_REF], a corpus consisting of 4 years of Le Monde, a French daily newspaper. The text has been segmented into words and phrases and then linguistically annotated. The initial annotation was done automatically but then it has been validated by human experts. Linguistic information in the corpus concerns words or lexical compounds, indicating the category, morphological properties and the lemma, as well as phrases, specifying the category of a constituent and a grammatical function. A sample of corpus annotations for the sentence Paul est fier de ses enfants `Paul is proud of his children' is given in Fig. 1. <SENT> <NP fct="SUJ"> <w cat="N" m="N-P-ms" lemma="Paul">Paul</w> </NP> <VN> <w cat="V" m="V--P3s" lemma="être">est</w> </VN> <AP fct="ATS"> <w cat="A" m="A-ms" lemma="fier">fier</w> <PP> <w cat="P" m="P" lemma="de">de</w> <NP> <w cat="Det" m="D-poss-pl" lemma="se">ses</w> <w cat="N" m="N-C-mp" lemma="enfant">enfants</w> </NP> </PP> </AP> </SENT> Figure 1: Paul est fier de ses enfants `Paul is proud of his children'

As can be seen from this example, the constituent structure is rather flat: there is no VP and all dependents of the verb (or more general, the verbal nucleus, VN) are related to it only via grammatical functions: both the subject (SUJ) and the subject complement (ATS) in the example form independent phrases. Note that functions are specified only for verb dependents: the PP complement of the adjective fier `proud' is structurally embedded within the AP but its function with respect to the adjective is not indicated in the corpus. Similarly, the subject of the predicative adjective is not provided either: the sentential subject, i.e., NP, Paul, is shared between the copula (est `is') and the adjective but this link is not specified in the treebank.

As Fig. 1 shows, adjectival valence is not directly indicated in the corpus. In order to obtain it from the treebank, we combine linguistic knowledge with corpus annotations.

Extraction method

Our extraction method is guided by linguistic cues applied to treebank annotations. We focus on AP constituents and restrict the types of phrases that can appear as arguments of an adjective to categories indicated in sec. 2.1, both for complements and the subject. Our main goal is to distinguish regular adjectival constructions from valency components.

Arguments

In the Treebank, predicative adjectives are direct arguments of a verb and they are assigned grammatical functions: a subject complement (ATS) or an object complement (ATO), i.e., a predicate referring either to the sentential subject (2) or to the direct object (8). SUJ Jacques finds ATO unavoidable OBJ that-she sings `Jacques finds it unavoidable that she sings.'

In such cases, the subject of the adjective can be easily identified as it is indicated by the grammatical function of another argument of the verb: SUJ for ATS, and OBJ for ATO adjectives, as in (8).

Adjectives may appear also in impersonal constructions with an accompanying Ssub or VPinf, (9). The status of the propositional components in (9) is different from those in (10), as illustrated also by the corpus annotations. The crucial difference is that Ssub or VPinf in (9) can be preposed to become the sentential subject, whereas this is not possible in (10). Paul is ATS happy that-it makes beautiful to go out `Paul is happy that the weather is good / to go out.' In (10), Ssub or VPinf is embedded within AP, unlike in (9). The propositional constituents in (9) become the extraposed subject of the adjective, i.e., in impersonal constructions (the subject is expressed by pronouns il or ce), OBJ-phrase is in fact the subject of ATS adjective. On the other hand, if no construction-related elements are present (sec. 3.2.2), the subordinate components, as in (10), are treated as complements of the adjective.

French clitics are always attached to a verb but they can replace dependents of other predicates as well. Although clitics often pronominalise arguments, they can refer to adjuncts as well, for instance to locative phrases. In the corpus, clitics are direct dependents of a verb and they are assigned a function. In copular predicative constructions, (11), as the copula itself does not have a clitic argument, if the function assigned to the clitic indicates an argument (A-OBJ in (11)), it must be an argument of the predicative adjective. The category of the argument is restored based on the form of the clitic and its function.

Non-arguments

Constituents which regularly appear in well-defined syntactic constructions are not related to a specific adjective and do not belong to its valence list. We filter out such PP, VPinf or Ssub by linguistic cues.

In comparative constructions, an adjective is often accompanied by a phrase annotated in the corpus as an internal PP or Ssub component of AP, (11). Note that in such sentences, in contrast to (10), the adjective additionally appears with a comparative adverb, plus `more', moins `less', autant `as much as', etc. Therefore, we exclude the embedded constituent from the list of adjective arguments, unlike in (10) where there is no adverb. the meeting was ATS more interesting that I NOT thought `The meeting was more interesting than I thought.' ( 13)-( 14) illustrate another type of productive constructions where the embedded constituent of AP is not an argument of the adjective. Again, the presence of intensifier adverbs, such as si `so', trop `too', tellement `so much', etc., is decisive for the status of Ssub or VPinf constituent within AP. ]. this story is ATS too beautiful for be true `This story is too good to be true.'

Lexicon of prepositions

Apart from comparatives, prepositional phrases do not appear in adjectival constructions. Therefore, no other linguistic observations can help us to specify the status of PPs in APs. In particular, there is no general rule which would permit to distinguish a PP complement of an adjective from a PP in the restructured complex NP subject, cf. [START_REF] Meydan | La restructuration du GN sujet dans les phrases adjectivales à substantif approprié[END_REF]. Instead, we use PrepLex [START_REF] Fort | Preplex: a lexicon of French prepositions for parsing[END_REF], a lexicon which specifies for each preposition whether it can introduce an argument of a verb. We adopt it to filter out PPs which cannot be complements of an adjective. Additionally, for adjectives, we exclude one preposition, comme `as', from the list of argumental prepositions, as in APs it is used only in comparative constructions.

Results

The presented method results in a list of 2153 adjectives and discovers 40 frames. Each frame indicates the category of the subject and complements (if any). If no complement and no propositional subject have been found for an adjective in the corpus, we assume that its valency list contains only the NP subject. (We refer to this frame as basic.) The majority of adjectives (1849) were found only with the basic frame whereas 304 had a different subcategorisation pattern. Table 1 presents 23 extracted frames which appeared at least twice in the Treebank, their frequency counts and the number of adjectives with which they were found. Table 1: Extracted frames with their frequency and the number of adjectival entries in which they appear. Abbreviations: functions: SUJ -subject, P-OBJ -PP or VPinf object, OBJ -object without an introducing element; categories: PP -prepositional phrase, Ssub -a subordinate clause, either in subjunctive (SsubS) or indicative (SsubI) mode, VPinf -an infinitive clause.

In order to get a better grip of the obtained results, we provided a brief examination of the extracted frames. This investigation revealed a few issues. First, due to imperfect or insufficient treebank annotations, the data is not totally reliable. In particular, subjectless or embedded impersonal constructions, (15), are unrecognized in the corpus. The absence of the imminent impersonal subject yields to incorrect or missed argument assignment: VPinf is either misinterpreted as the object of the adjective or is not taken into consideration at all. it could be impossible OBJ to ignore the relations transatlantic `It would be impossible to ignore transatlantic relations.'

Second, Preplex does not allow us to efficiently separate real PP-arguments from adjuncts. All argumental prepositions (i.e., P which can introduce an argument) listed in the lexicon are ambiguous as they can be used in PP-adjuncts as well. For instance, de `of' in (1) indicates a PP complement, whereas in (7) the same preposition introduces a PP which is not subcategorized for. Therefore, each preposition has to be considered individually with its adjectival context. Moreover, Preplex has been created for verbs. It should be verified to which extent the list is valid also for adjectives. For example, comme `as', listed among argumental prepositions for verbs, had to be moved to a non-argumental list for adjectives.

Finally, due to the corpus size, certain adjective-frame realisations are missing. For example, plausible `plausible' has been found only with the basic frame in the corpus.

In order to improve the quality of the adjectival lexicon and extend its coverage, we complement the presented results with data from a much larger corpus.

Using a large automatically annotated corpus

In the second step, our method extracts frames by using a much larger corpus and applying statistical methods with two objectives in mind. First, we aim at improving the extraction that has been performed in the previous step. The frames discovered in the treebank are now considered candidate frames that will be either corroborated or invalidated by new corpus data. Second, we use additional corpus data to find new frames by examining occurrences of hundreds of new adjectives.

We have chosen to focus on verification of PP and VPinf complements as they turned out to be the most problematic in the previous step. More precisely, we now consider the set of lexicalised frames that have been discovered in the treebank, i.e., instances of candidate frames, containing a PP or VPinf argument, with a specific adjective, for example: Obviously the set of candidate frames could simply be manually validated, since the number of different lexicalised frames is not insurmountable (if we put aside adjectives with the basic SUJ:NP frame, cf. Table 1). However, the idea is to use them as a first data set to evaluate statistical tests we have applied to filter candidate frames. In particular, we want to make sure that the tests are relevant and can be in turn applied to help identifying new lexicalised frames in a large corpus.

Extracting patterns

In order to obtain information about adjectives, we examine the output of a French syntactic parser, Syntex (Bourigault 2007), applied to a large corpus. The corpus is composed of texts from Le Monde (from now on called the LM corpus), the same French daily newspaper which served to build the Treebank, but is much bigger: the LM corpus contains 200 million words. Syntex provides dependency information using a combination of heuristics and statistical cues. The parser does not always build a complete syntactic structure: some units can be left unattached when information is insufficient to resolve dependency relations.

We extract all adjectives with prepositional dependents, i.e., prepositions introducing either a noun phrase or an infinitive clause. Syntex identifies four types of relations (functions) related to adjectives. The ADJ relation indicates attributive uses, cf. (4). Predicative adjectives, the subject (2) or object complement (3), are marked as ATTS and ATTO respectively. Appositive adjectives are indicated as APPOS. Example (18) shows which information, morphosyntactic and dependency, is obtained for each adjective.

(18) Les fortes pluies consécutives aux deux tempêtes 'The heavy rains resulting from two storms' AdjFP|consécutif|consécutives|4|ADJ;3|PREP;5

Every extracted adjective contains information about its governor (ADJ;3 means that the adjective is connected to its governor -3 rd token of the current sentence -via the relation ADJ) and its dependent (PREP;5 means that the adjective governs the 5 th token via the relation PREP). Additionally, the inflected form and the lemma are specified.

In 29% of the cases, the parser does not have enough cues to identify the governor of the adjective. In such cases, the relation is left unresolved and a NOGOV relation is assigned to the adjective. In particular, Syntex does not attach appositive adjectives when they occur in sentence initial positions, as in example ( 19). Just like in the first step, sec. 3.2, we use heuristics to filter out PP or VPinf elements of syntactic constructions such as superlatives (le plus <adj> des 'the most <adj> among') or intensifiers (assez <adj> 'enough to').

A sample of information that we get from Syntex parses is presented in Table 2. Inflected word forms are reduced to their lemmas. We keep the following information: form and category (N or Vinf) of the dependent, type of the relation, form of the subject (cf. section 4.3.1. As expected, we get much more data from the large LM corpus than from the Treebank. Table 3 shows that the number of adjective types for which we get dependency information is multiplied by 8, the number of patterns of the form ADJ PREP (VPinf|PP) is multiplied by 18. On the other hand, however, these data are noisy. Automatic parsing is still a challenging task. Syntex has obtained very good evaluation results at the French parsing evaluation campaign that took place in 2004 (winning the first rank on most corpora) [START_REF] Paroubek | Les résultats de la campagne EASy d'évaluation des analyseurs syntaxiques du français[END_REF], yet precision figures are ranging from 0.75 to 0.80. This means that if we want to deal with such data, we have to be aware of this error rate, and find solutions to make up for it. Errors can be generated by the word segmentation module and by tagging or parsing programs. We found two main categories of problems: many nouns are wrongly tagged as adjectives and many PPs are attached to an adjective whereas they should be linked to the noun that the adjective modifies.

The obtained data cannot be manually revised, due to their abundance. Instead, our approach consists in relying on the amount of data and in limiting errors by applying simple thresholds which allow us to exclude rare and potentially ill-formed configurations. The next subsections describe these filtering procedures, focusing first on the evaluation of candidate frames from the Treebank (section 4.3) and then turning to the extraction of new frames from the LM corpus (section 4.4).

Filtering the treebank candidate frames

Impersonal constructions

As mentioned in 3.2.1., VPinf[de] in predicative adjectival constructions is ambiguous: in impersonal constructions VPinf is in fact the postposed sentential subject, whereas in personal sentences it is a true VPinf complement. Disambiguating the two cases is a quite straightforward task given a large corpus. In order to identify impersonal constructions, we simply check the form of the subject. In the parser output, information regarding the type of the subject pronoun (personal or impersonal) is not available. We approximate this information by verifying the form of the subject. In French, an impersonal subject can be expressed in two ways: ce (and its variants c' and cela) or il, which is ambiguous, corresponding either to a personal (=he) or an impersonal form. For each adjective, we calculate the proportion of ce or il pronouns in the subject position when the parser has identified the ATTS relation.

Impers(adj) = number of ce, c', cela, il pronouns / total number of ATTS relation

We apply this measure to 40 ADJ+VPinf[de] constructions that have been extracted from the treebank. We get highly contrasting results, since all the patterns but one get either very high or very low values. We obtain two clear-cut subsets of data: 27 constructions combine with more than 90% of `impersonal' pronouns:

( This measure enables us to successfully distinguish personal from impersonal constructions. VPinf which appear in patterns with a high percentage of `impersonal' pronouns is considered the subject, whereas VPinf found in patterns with the low percentage of `impersonal' pronouns are treated as a complement.

Only one pattern has an intermediate value and cannot be categorized: nouveau VPinf [de] (40% of 'impersonal pronouns'). When we look at the contexts, this pattern corresponds mostly to an impersonal construction (Il n'est pas nouveau de + VPinf 'It is not new to + VPinf'), but it also matches another kind of construction, ( 22), where VPinf belongs to the subject (NP headed by an abstract noun) but is placed after the adjective.

(22) L'idée n'est pas nouvelle de + VPinf the-idea neg-is not new to VPinf Only the postposed VPinf subject in impersonal constructions must be taken into account in the valence of the adjective.

Valency tests for adjectives

Finding indicators to make distinction between arguments and adjuncts is a difficult task. With respect to verb complementation, there are many linguistic tests but in general they are not conclusive to handle the distinction. A thorough examination of French verb complementation [START_REF] Bonami | Les constructions du verbe: le cas des groupes prépositionnels argumentaux. Analyse syntaxique[END_REF] leads to very specific conclusions, namely that: 1) obligatoriness is a sufficient but not a necessary condition for argumenthood; 2) the pre-finite verb position is strictly limited to adjuncts; 3) the "le faire" test (a French equivalent of the English "do so" test ) works only for adjuncts. Other tests (iterativity, movement, etc.) are not categorical and show only tendencies. This situation is all the more less clear for adjectives, see sec. 2.2.

There were few attempts to automatize the distinction. [START_REF] Merlo | The notion of argument in PP attachment[END_REF] have implemented a method to automatically distinguish arguments from adjuncts of English verbs and nouns. Their method combines three linguistic diagnoses and approximates them in terms of corpus counts extracted from a manually annotated corpus (Penn-treebank). The tests estimate the following properties: the optionality of the complement, the degree of selection by the head, and the iterativity of a phrase. The availability of lexical resources such as WordNet enable them to use semantic classes that prove to be useful information in the classification task. In the same vein, in [START_REF] Fabre | Exploiter des corpus annotés syntaxiquement pour observer le continuum entre arguments et circonstants[END_REF] we have designed simple statistical indicators to assess the degree of autonomy of a PP with respect to the verb.

We aim at adopting a similar technique for French adjectives. The task is even more complicated in this case, due to the greater flexibility of the adjective complementation as presented in section 2.2: the optionality of almost all adjective complements, and the variability of the preposition that is used to introduce the complement makes the distinction between complements and adjuncts even more complex.

On the basis of the linguistic properties of adjectives, we propose several statistical measures to evaluate valence properties of candidate frames, focusing in particular on obligatoriness and autonomy of PP (or VPinf) with respect to the adjective. The idea is to consider a PP more likely to be an argument of the adjective if it meets the following three conditions: the adjective is rarely found alone (i.e., without an accompanying frame), the frame is productive (the adjective combines with a large range of nouns or infinitives introduced by the same preposition), and prepositional expansions that are attached to this adjective are mostly introduced by the preposition which appears in the frame. This diagnosis is obtained by computing three measures estimating the optionality and the productivity of the pattern.

1) Optionality measure

Since the syntactic realization of adjective complements is usually optional, the information about absence or presence of a complement cannot be considered as a decisive factor. Yet, we can use this information to assess a tendency in the whole corpus. For each adjective, we calculate the proportion of its occurrences that are found without a prepositional expansion. Only 100 out of the 2684 adjectives appear with a preposition in at least 50% of their occurrences, including the adjectives that [START_REF] Noailly | L'adjectif en français, Ophrys[END_REF] has mentioned having an obligatory complement (cf. 2.2).

2) Productivity measures

Productivity has mainly been addressed in morphology to estimate the ability of a suffix to produce new words. It can also be used in syntax to assess the regularity of a relation. We use a productivity measure that estimates the regularity of each pattern, by simply counting the number of different nouns (or infinitives for patterns including a VPinf) that appear as a dependent of the adjective in the corpus. This gives us a first approximation of the behaviour of the pattern. For example, the pattern applicable PP[à] 'applicable to' is very productive, since 450 different nouns are found in this position, whereas the pattern difficile PP[à] 'difficult to' is less productive (productivity=29).

Yet, this measure is highly dependent on the frequency of the adjective itself. We then calculate a more precise measure of productivity, the relative productivity, which estimates the part that each preposition takes within the set of all prepositions that can introduce complements of the adjective. Some interesting patterns can exhibit a very low productivity and simultaneously a high relative productivity, such as croulant sous 'collapsing under' or chatouilleux sur 'touchy about'.

Results

The criteria that we have used so far consist, on one hand, in identifying impersonal constructions (4.3.1) for patterns including a VPinf introduced by de, and on the other hand, in assessing argumenthood of PP or VPinf constituents by estimating optionality of the complement and productivity of this relation (4.3.2). These measures allow us to translate traditional linguistic tests of optionality and regularity into very simple statistical cues. This provides a profile of candidate terms (CF) in the corpus. In section 4.3.1 we have shown that the measure adopted to identify impersonal constructions permits to distinguish two sets of candidate frames. If we now turn to the question of argumenthood, we now have indications about the behaviour of each candidate frame in the LM corpus (Table 5). When the three figures are high, this is an indication for the validation of the candidate pattern based on its behaviour in the corpus: the complement is frequently present, the relation is regular and the preposition is frequently associated with the adjective. In Table 5, this is the case for patterns 1, 2, 3, 5. When the three figures are low, as for CF 6, the measures bring about ill-formed patterns. CF 4 and 7 are in-between: for CF 4, the adjective combines very regularly with a PP, but not with the one indicated in the pattern (sur 'on') since the CF has a very low productivity. This PP is actually not an argument but an adjunct ('applicable on'). CF 7 is very productive, but the adjective is mostly found alone, without a PP. This result may be interpreted in many ways. In this case, it corresponds to two different meanings of the adjective, propre meaning either 'clean' or 'peculiar', and only the second one is strongly associated with the PP[à] pattern. Most CF exhibit high measures of productivity, thus confirming the validity of the data that have been extracted. In order to locate less reliable CF we have set low thresholds, namely: basic prod. < 10, relative prod. < 0,1, proportion of occ. of the adjective with a PP < 0,1. 24 candidate frames were found with such low values. The examination of these results shows that the method enables us to spot two types of CF:

-CF corresponding to ill-formed patterns that should have been eliminated by the heuristics designed to filter out alternative syntactic constructions (cf. section 3.2.2). For example, the sequence étroit:VPinf[pour] 'narrow for' is part of the intensifier construction that has not been correctly spotted -CF corresponding to adjunct relations, such as dynamic:PP[depuis] 'dynamic since' or sinistré:PP[après] 'stricken after'. These PPs convey peripheral information about the predicate, such as temporal complements All 24 CF should be eliminated as they result from errors in the Treebank annotation or in incorrect application of our heuristics. This preliminary result shows that statistical cues provide a useful verification of the candidate frames extracted from the treebank.

So far, we applied the statistical measures to the treebank data. The next step consists in applying them to the LM corpus in order to discover new patterns .

Extracting new frames

From now on, we will examine new patterns extracted from the LM corpus, i.e., lexicalised frames that have not been found in the treebank. By comparing the overall values of the 3 argumenthood measures (Table 6) we get an idea of the relative quality of patterns. In particular, for the new LM patterns, the average productivity is very low, and so is the average proportion of adjectival occurrences that have prepositional dependents. On the basis of this rough comparison, we may expect that most new patterns will be rejected as subcategorization frames. Our goal is then to identify the minority of genuine valency patterns among these data. In both cases, when the impers measure gets extreme values, it successfully helps to distinguish the two types of constructions. In-between, 8,5% of the patterns get intermediate values and must be more closely looked at. When we examine the contexts in which these 37 patterns occur, two different scenarios emerge. First, they can behave like the nouveau VPinf[de] pattern that we have mentioned in section 4.2.1: in addition to the impersonal construction we find instances of the nominal subject, corresponding to a specific construction, where the VPinf cannot be considered a dependent of the adjective.

(25) L'erreur serait lourde de le cantonner à cela = Le cantonner à cela serait une lourde erreur the mistake would-be-serious-to confine him to this 'To confine him to this would be a serious mistake'

In this case, only the impersonal construction indicates a valency element. Second, we have patterns that can match two different constructions: one with a sentential subject (26) and the other with a VPinf complement (27).

(26) Julie est malheureuse d'avoir été exclue Julie is unhappy to have been excluded

(27) C'est malheureux de parler de ça It-is-unhappy-to talk about this 'Talking about this is deplorable'

In this case, both patterns must be kept for the adjective. This measure finally enables us to enhance the lexicon with 362 new lexicalised frames of the form ADJ + [S:subject].

Extracting PP with good valency properties

We now turn to the rest of the data that we have extracted, in order to spot patterns that correspond to new lexicalised frames. The idea is to focus on patterns that exhibit good statistical properties. The difficulty is to turn statistical estimation of valency properties into a binary decision (argument yes/no). Defining thresholds is an arbitrary task, resulting from a compromise between recall and precision. In the present study we have first decided to look at patterns that exhibit high values for the three measures (basic productivity, relative productivity and optionality), taking as a reference point the average values that we have obtained for the treebank frames (Table 6), namely: Basic prod.>200, relative prod.>0,5, proportion of occ. of the adjective with a PP >25%. This first set of values provides very good patterns, but we get very few data. In a second step, we have loosened the constraints in order to get a larger set of data. The new values are: Basic prod.>5, relative prod.>0,2, proportion of occ. of the adjective with a PP >20%.

The minimum value of basic productivity is considerably reduced following the observation that infrequent patterns can also provide subcategorisation information. On the basis of these statistical counts, we get 199 patterns that allow us to make an initial evaluation of the results. A manual evaluation shows that they are split into 3 categories: 32% are tagging and parsing errors 17% are regular associations but not 'standard' valency information 51% are confirmed lexicalised frames This first result brings out three preliminary conclusions: the statistical approach must not be considered as a fully automatic procedure, but it should guide an inspection of large amount of data, in order to give priority to information about syntactic dependence that seems to be the most regular and reliable. As a result, 100 more ADJ [PP] or ADJ [VP-inf] frames are thus added to the treebank frames. Second, this experiment shows that the use of large corpora brings to the fore the question of the continuum between arguments and adjuncts. Some PPs may be very regularly associated with adjectives in the corpus without necessarily being syntactic arguments. In the patterns that show regular associations but are not considered 'standard' valency elements, we find information that relates to semantic frames rather than argumenthood:

(28) repérable dans + LOCATION 'that can be spotted in' + LOCATION (29) perceptible dans + LOCATION 'perceptible in' + LOCATION (30) indisponible pendant + TIME 'unavailable during + TIME'

The binary decision is all the more difficult to make given that, as seen in section 2.2., traditional linguistic tests do not efficiently distinguish between arguments and adjuncts of adjectives.

Third, the decision of including such patterns in the lexicon depends on how the lexicon is planned to be used. A repertoire of very regular associations that go beyond strict argumenthood can be very useful in the perspective of NLP applications such as the development of parsers which need to resolve PP attachment, or the development of semantic annotation based on semantic frames.

Conclusion

We have exposed two complementary methods for detecting adjective valence. Our study shows that the constitution of a valency lexicon can be assisted in different ways by resorting to corpus linguistics methods, combining data coming from a small but linguistically rich and quite reliable corpus and from a much larger but more noisy corpus. The first corpus provides a small set of good quality frames with the help of linguistic heuristics. The second corpus helps to improve the accuracy of the initial frames by supplying complementary information about syntactic constructions (impersonal vs. personal) and about the regularity of the candidate frames. The large amount of data also provides new patterns equipped with statistical information that guide semi-automatic detection of actual frames.

Regarding the distinction between arguments and adjuncts, the confrontation of frames with data from a large corpus leads us to progress from a binary distinction to a more graduate perception of the regularity of syntactic patterns. Statistical counts show that a PP can be consistently associated with an adjective in the corpus, giving strong indication of selection, without being normally considered a strict argument. This type of information helps to identify in-between cases, as stated by (Manning, 2002) which can be also interesting to describe in terms of colligation or semantic frames.

We plan to further investigate data extracted from the large corpus in order to pursue the identification of frames, but also to examine in more detail dependents of adjectives from the corpus perspective. In particular, this data contains two types of interesting information which should be examined in more detail:

-preposition profiles: prepositions could be ranked according to their average value of relative productivity. For example the complex preposition à l'égard de `with respect to', which is not listed as argumental in the PrepLex lexicon (cf. 3.2.2), appears at the top on the list of most productive prepositions -preposition alternations: corpus data can indicate alternation tendencies of specific prepositions (for example, devant `in front of' and face à `facing' can be found concurrently with many adjectives). Such statistical information extracted from a large annotated corpus can benefit not only to the construction of lexical resources for NLP applications but also to descriptive studies of lexico-syntactic properties of adjectives.

Notes

1 Picabia (1978:p.43) mentions two adjectives which appear with an apparent NP complement: bleu roi `royal blue' and rouge cerise `cherry red'. The two exceptions, however, can be considered multi-word adjectives, cf. [START_REF] Gross | Méthodes en syntaxe[END_REF].

  (8) [ NP Jacques] trouve [ AP inévitable] [ Ssub qu'elle chante].

( 11 )

 11 Paul [ VN y est] [ AP favorable]. Paul A-OBJ to-it is ATS in favour `Paul is in favour of it.'

( 12 )

 12 La réunion était [ AP plus intéressante [ Ssub que je ne pensais]].

( 13 )

 13 Paul est [ AP si heureux [ Ssub qu'il saute de joie]]. Paul is ATS so happy that-he jumps of joy `Paul is so happy that he jumps out of joy.' (14) Cette histoire est [ AP trop belle [ VPinf pour être vraie]

  -OBJ:PP[à] 278 SUJ:NP|P-OBJ:PP[de] 204 SUJ:NP|P-OBJ:VPinf[de] 83 SUJ:VPinf[de] 66 SUJ:NP|P-OBJ:VPinf[à] 53 SUJ:NP|P-OBJ:PP[pour] 35 SUJ:NP|P-OBJ:PP[en] 30 SUJ:NP|P-OBJ:VPinf[pour] 24 SUJ:NP|P-OBJ:PP[dans] 22 SUJ:SsubI[que] 18 SUJ:NP|OBJ:Ssub[que] 18 SUJ:NP|P-OBJ:PP[par] 13 SUJ:NP|OBJ:SsubI[que] 12 SUJ:NP|P-OBJ:PP[sur] 11 SUJ:NP|P-OBJ:PP[avec] 9 SUJ:NP|P-OBJ:PP[loc] 8 SUJ:NP|P-OBJ:PP[entre] 5 SUJ:SsubS[que] 6 SUJ:NP|P-OBJ:PP[chez] 4 SUJ:NP|P-OBJ:PP[depuis] 3 SUJ:VPinf[de]|P-OBJ:PP[à] 3 SUJ:NP|P-OBJ:PP[après] 2

  (15) (Il pourrait être) impossible [ VPinf d'ignorer les liaisons transatlantiques].

( 19 )

 19 Soucieuse d'affirmer son indépendance, la banque centrale refusa de céder 'Eager to assert its independence, the central bank refused to give in' AdjFS|soucieuse|soucieux|1||PREP;2 (no mention of a governor => NOGOV)

  Paul est [ AP heureux [ Ssub qu'il fasse beau] / [ VPinf de sortir]].

	(9) Il est [ AP agréable] [ Ssub qu'il	fasse beau] / [ VPinf de sortir].
	it is ATS nice	OBJ that-it makes beautiful OBJ to go out
	`It's nice that the weather is good / to go out.'
	(10)

Table 2 :

 2 ). In what follows the resulting triplets ADJ + PREP + DEP-CAT are called patterns. Patterns extracted from the LM corpus

	ADJ	PREP	DEP	DEP-CAT	REL	SUBJ
	consécutif	à	tempête	N	ADJ	pluie
	'resulting'	'from'	'tempest'			'rain'
	enclin	à	consacrer	VINF	ATTS	il
	'inclined'	'to'	'devote'			'he'
	insensible	à	régulation	N	ATTO	système
	'insensitive'	'to'	'regulation'			'system'
	soucieux	de	défendre	VINF	APPOS	-
	'anxious'	'to'	'defend'
	soucieux	de	affirmer	VINF	NOGOV	-
	'anxious'	'to'	'assert'

Table 3 :

 3 Quantitative comparison of the two data sets

	Treebank	Le Monde

Table 4 :

 4 Table 4 shows on one example how this is computed. Productivity of patterns associated with the adjective étonnant 'surprising'

	adjective	pattern	basic productivity	relative productivity
				= basic productivity / overall productivity
		de N	35	0.36
		de VINF	17	0.17
	étonnant	dans N	28	0.29
		pour N	9	0.1
		par N	7	0.07
			(overall productivity = 96)

Table 5 :

 5 Profiles of the lexicalised frames

	n	candidate frame	Basic productivity	Relative productivity	Proportion of occ. with a PP
	1	âgé:PP[de]	265	0,91	0,69
		aged-of
	2	aisé:VPinf[à]	110	0,32	0,16
		easy-to

Table 6 :

 6 Comparing Treebank candidate frames and Le Monde patterns 4.3.1. Identifying impersonals Following the method already presented in section 4.2.1., the impers measure is tested on 431 new ADJ VPinf[de] patterns that are found in the LM corpus. The values that we obtain on this set of patterns are not as clear-cut as what we have observed for Treebank candidate frames. Yet the measure enables us to make a decision for 91,5% of the patterns. Most patterns (84%) get a very high value (more than 80% of the subject forms are potential impersonal constructions), which means that the VPinf must be considered the extraposed subject rather than a complement of the adjective. A few examples are given below: (23) Il est aberrant, aléatoire, artificiel … de + VPinf 'It is absurd, unpredictable, artificial … to' + VPinfOnly 7% of the patterns get a very low value (less than 20% of the subject forms are potential impersonal constructions), which attests that VPinf is a real complement.

		Treebank Candidate Frames	Le Monde new patterns
		in the LM corpus
	proportion of occurrences with a PP	25%	4%
	average basic productivity	293	20

In the LM corpus, no category distinction is made between a preposition introducing a PP and a complementizer preceding a VPinf. According to corpus annotation, both types of phrases are headed by a preposition, hence a type of PP. In this section, the distinction is not made either.


Jérôme Gorin
email: jerome.gorin@it-sudparis.eu

Matthieu Wipliez
email: matthieu.wipliez@insa-rennes.fr

Françoise Prêteux
email: francoise.preteux@it-sudparis.eu

Mickaël Raulet
email: mickael.raulet@insa-rennes.fr

Keywords: Reconfigurable Video Coding, RVC-CAL Actor Language, Low Level Virtual Machine, Network scheduling, Dataflow programming, Code synthesis, Low Level Virtual Machine, Multi-core systems

Introduction

In the last two decades, the evolution of video coding standards has produced outstanding results. The next challenge of video coding is to speed up adoption of future coding techniques and to make smoother implementation of multiple standards support for a single platform. So as to overcome the limitation of the current monolithic MPEG decoder reference description, the MPEG consortium decides to create MPEG Reconfigurable Video Coding (RVC) [START_REF] Mattavelli | The reconfigurable video coding standard [standards in a nutshell[END_REF]. This framework aims "at providing a framework allowing a dynamic development, implementation and adoption of standardized video coding solutions with features of higher flexibility and reusability" Reconfigurable Video Coding (RVC) has been chosen by the MPEG community to be an alternative paradigm for codec deployment. The MPEG RVC paradigm is based on RVC-CAL Actor Language (RVC-CAL) to describe decoders at high-level library component using dataflow descriptions. The main objective of RVC is to enable arbitrary combinations of fundamental algorithms, without additional standardization steps. By adding the side-information of the combination description alongside the content itself, MPEG RVC defines the new concept of RVC decoder. An RVC decoder may create, configure and re-configure video compression algorithms adaptively to its content.

Yet, no mechanism has been found to automatically and dynamically use dataflow description to form an RVC decoder. This paper proposes to transform the RVC-CAL description of coding tools into the generic low-level description called Low-Level Virtual Machine (LLVM) Intermediate Representation (IR), and to use the LLVM infrastructure for dynamically and efficiently instantiating these coding tools to create decoders. By combining the LLVM and the RVC concepts, we created a portable MPEG decoder engine that can configure and reconfigure an MPEG RVC decoder description. After a brief reminder of the MPEG RVC and CAL concepts in section 2, we present the motivation for using LLVM as the reference IR for CAL actor in section 3. The section 4 and 5 are devoted to the implementation of our proposed dynamic RVC decoder. We finally show in section 6 that the decoder has been successfully tested onto multiple platforms.

MPEG Reconfigurable Video Coding

The MPEG Reconfigurable Video Coding (RVC) [START_REF] Mattavelli | The reconfigurable video coding standard [standards in a nutshell[END_REF] framework is a new ISO standard still under consideration in MPEG. It aims at providing video codec specifications at the level of library components instead of monolithic algorithms. The key approach of MPEG RVC is to produce an Abstract Decoder Models of MPEG standard suitable for any platform. An ADM is a generic representation of a decoder, built as a dataflow diagram expressed with the XML Dataflow Format (XDF). XDF is an XML dialect that describes the connections between Functional Units (FUs). Each FU is described in RVC-CAL Actor Language (RVC-CAL) and defines a processing entity of a decoder. Connections in an XDF diagram represent the data flow between FUs.

XML Dataflow Format

Encoded Video Data Decoded Video Data

Non-Normative

Video Tools Library

Fig. 1 A typical use of the MPEG RVC Framework.

The Figure 1 shows a typical use of a normative ADM description to produce a non-normative decoding solution that can target either software or hardware platform. MPEG RVC provides both a normative standard library of FUs called Video Tools Library (VTL) and a set of decoder descriptions/configurations expressed as networks of FUs. Such a representation is modular and helps the reconfiguration of a decoder by modifying the topology of the network. Adding new coding technologies in an existing standard is a particularly sensitive part of a standardization process. RVC mainly focuses on reusability of standardized coding tools by allowing different decoder descriptions to instantiate common FUs across standards.

RVC-CAL Dataflow Programming

RVC-CAL [START_REF] Bhattacharyya | Overview of the MPEG reconfigurable video coding framework[END_REF] has been chosen by MPEG RVC as the reference programming language for describing FUs. RVC-CAL is designed to provide a concise and high-level description of actors. An actor in RVC-CAL represents an instantiation of an RVC Functional Unit and an RVC-CAL dataflow model represents a composition of actors. RVC-CAL, compared with the CAL Actor Language (CAL) [START_REF] Eker | CAL Language Report[END_REF], restricts the data types, and operators that cannot be easily implemented onto the platforms.

An actor shown in Figure 2 and Figure 4 is a computational entity with input ports, output ports, states, actions, and parameters. All actors communicate with others by sending and receiving tokens (atomic pieces of data) through their ports. An actor contains one or several actions. Actions define computations that an actor has to execute (or to fire). Actions may have a tag, guard, local variables, and statements. An action is defined by the amount of tokens consumed on the input. It may change the actor state, and may output tokens according to a function of input tokens and state variables. The guard conditions specify additional firing conditions, where the action firing depends on the values of input tokens or the current state.

When an actor fires, an action is selected according to the number and value of tokens available, and if the guard associated to the action is true. Action selection may be further constrained using a Finite State Machine

Actions

State

Fig. 3 A CAL network with details on an actor.

(FSM) and priority inequalities to impose a partial order among action tags. The reader can refer to [START_REF] Bhattacharyya | Overview of the MPEG reconfigurable video coding framework[END_REF] for more details on the RVC-CAL language.

A composition of RVC-CAL actors forms a CAL network, represented in Figure 3. In an RVC-CAL network, actors communicate via unbounded channels by reading and writing tokens from and to FIFOs. At a network level, each actor works concurrently, executing their own sequential operations. Dataflow programming was once invented to address the problem of parallel computing. The strength of using dataflow model is that execution of concurrent processes is only driven by token availability. Actors are able to fire simultaneously regardless of the environment, allowing the application to be easily distributed over different processing elements. This feature is particularly useful in the context of multi-core platforms.

Another important point of RVC-CAL is that its dataflow network does not specify any execution models. Many variants of Dataflow Model of Computation (MOC) based on restriction of dataflow models (such as Synchronous Dataflow, Boolean Dataflow...) have been introduced in the literature [START_REF] Lee | Synchronous data flow[END_REF][START_REF] Ritz | Optimum vectorization of scalable synchronous dataflow graphs[END_REF][START_REF] Bilsen | Cycle-static dataflow[END_REF][START_REF] Bhattacharya | Parameterized dataflow modeling for DSP systems[END_REF][START_REF] Bhattacharyya | APGAN and RPMC: Complementary heuristics for translating DSP block diagrams into efficient software implementations[END_REF]. RVC-CAL is expressive enough to specify a wide range of programs that follow a variety of dataflow models, trading between expressiveness (the set of programs that can be modeled) and analyzability. RVC-CAL dataflow program fits all of those models depending on the environment and the targeted application. Figure 2 shows a simple multiplexer in accordance with RVC-CAL semantics. This multiplexer is composed of three inputs, one output and two actions. Guards prevent to fire the first action when a token on input c is not true and to fire the second action if token on input c is not false. The actor in Figure 4 is an execution example of this multiplexer.

State

MPEG RVC Framework

CAL is supported by a portable interpreter infrastructure that can simulate a hierarchical network of actors. This interpreter was first used in the Moses1 project. Moses features a graphical network editor, and allows the user to monitor actor's execution (actor state and token values).

The project being no longer maintained, it has been superseded by the Open Dataflow environment (OpenDF2 for short). OpenDF is also a compilation framework with a backend for generation of HDL(VHDL/Verilog) [START_REF] Janneck | Synthesizing hardware from dataflow programs: an MPEG-4 Simple Profile decoder case study[END_REF], and a backend targeting ARM11 and embedded C is under development [START_REF] Von Platen | Efficient realization of a CAL video decoder on a mobile terminal[END_REF] as part of the EU project ACTORS 3 . It is also possible to simulate CAL models in the Ptolemy II4 environment.

Contrary to aforementioned tools dedicated to CAL, the Open RVC-CAL Compiler5 (Orcc) is a compiler specific to RVC and its subset of CAL standardized as RVC-CAL. This framework is based on a platformagnostic, language-agnostic Intermediate Representation (IR) that is both higher-level, more conservative, and more concise than the existing IR used by OpenDF. This IR provides a sort of "common ground" between software languages (C/C++, Java) and Hardware Description Languages (HDLs) such as Verilog and VHDL. The Orcc IR is more detailed in section 4.1. Orcc has backends that can transform the IR to C, C++, Java; backends for VHDL and XLIM are being developed. This tool is available as an Eclipse feature and comes with an IDE composed of a simulator, a debugger, and an editor with automatic error reporting.

3 Low level Virtual Machine Infrastructure MPEG RVC defines an abstract description of decoders that enhance parallelism scalability, modularity and generic uses. It also provides synthesis tools that generate static decoder programs for specific platforms. The generated decoders are made with information from an ADM description to fully exploit processing resources but reject unnecessary information for the selected platform.

The main contribution of this article is to propose a dynamic synthesis and execution of an ADM description integrated inside the targeted platform. It permits to bring all information from an ADM description to the decoder and to use a Virtual Machine dedicated to RVC ADM for dynamically executing the corresponding decoder. As represented on Figure 5, this decoder may take the side information of the ADM alongside the content itself, for a dynamic generation of decoders 1, 2 or a hybrid version between these two decoders.

Although an actor defined in RVC-CAL looks very compact and clear, writing a compiler for the RVC-CAL language is a nontrivial task, and it takes a lot of workforce to build one from scratch [START_REF] Wernli | Design and Implementation of a Code Generator for the CAL Actor Language[END_REF]. The Universal Video Decoder (UVD), a Virtual Machine dedicated to video decoding with a low-level and specific language, has already proven the benefits of using dynamic decoding in [START_REF] Richardson | Dynamic Configuration: Beyond Video Coding Standards[END_REF]. This concept has shown interesting decoding performance but at the cost of developing a dedicated Virtual Machine, only tested and specified in one specific environment. As for target code portability, we believe that using an existing infrastructure (such as the Java Virtual Machine (JVM) or the Common Language Runtime (CLR)) is mandatory, rather than developing one from scratch.

Performance and portability is a crucial point for the choice of a Virtual Machine. High Level Language Virtual Machine that target dynamic language, such as JVM for Java or CLR for C#, remains more than twice slower than the equivalent C application [START_REF] Sangappa | Benchmarking Java against C/C++ for interactive scientific visualization[END_REF][START_REF] Singer | JVM versus CLR: a comparative study[END_REF][START_REF] Lattner | LLVM: An Infrastructure for Multi-Stage Optimization[END_REF][START_REF] Barrett | 3c -a JIT compiler with LLVM[END_REF]. The Low-Level Virtual Machine fits all of our expectation by providing excellent application performance, a compiler infrastructure tested in a wide variety of platforms and a strong research infrastructure support.

Intermediate Representation

One of the key factors that differentiate LLVM from other systems is the intermediate representation it uses. The Low-Level Virtual Machine (LLVM) is a low-level representation of applications, close to assembly languages, that captures the key operations of ordinary processors but avoids machine specific constraints such as physical registers or pipelines. It has been designed to be a low-level representation but with high-level type information for compiler analysis and optimization. The reader is invited to read [START_REF] Lattner | LLVM: An Infrastructure for Multi-Stage Optimization[END_REF] that explains the justification of LLVM IR design choices.

The LLVM IR is composed of an infinite set of typed virtual registers that can hold values of primitive types (integral, floating point, or pointer values). These virtual registers are in Three Address Code (3AC) form and Static Single Assignment (SSA) form [START_REF] Lattner | LLVM: An Infrastructure for Multi-Stage Optimization[END_REF]. We develop the property of these two forms, widely used for compiler optimization, in section 4.2. LLVM programs transfer values between virtual registers and memory solely via load and store operations using typed pointers. The LLVM instruction set contains 31 operation codes (opcode) that can be overloaded (for example, the add instruction can operate on operands of any integer size or vector type). The LLVM IR has also a mechanism for explicit representation of Control Flow Graph (CFG). Figure 6 provides an example of the LLVM IR. More information on syntaxes and semantics of each LLVM instructions are given in the LLVM reference manual [START_REF] Lattner | LLVM Language Reference Manual[END_REF].

Just-In-Time Compiler

LLVM also designates a compilation framework that exploits the LLVM IR to provide a combination of features not available in any previous compilation approach [START_REF] Lattner | LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation[END_REF]. These capabilities are:

1. Persistent program information: The compilation model preserves the LLVM representation throughout an application's lifetime, allowing sophisticated optimizations to be performed at all stages of execution. 2. Transparent runtime model : The system does not specify any particular object model, exception semantics, or runtime environment, thus allowing any language to be compiled using it. 3. Uniform, whole-program compilation: Languageindependence makes it possible to optimize and compile all code comprising an application in a uniform manner.

The compilation framework corresponds to a collection of libraries and tools that makes easier to build offline compilers, optimizers or Just-In-Time (JIT) code generators. LLVM is currently supported on X86, X86-64, PowerPC 32/64, ARM, Thumb, IA-64, Alpha, SPARC, MIPS and CellSPU architectures. As LLVM is becoming a commercial grade research compiler, the code generated will continually benefit from improvements of its compiling infrastructure.

LLVM-based dynamic decoder

The advantages of LLVM are the properties looked for MPEG RVC decoders: generic, efficient and dynamic. As represented in Figure 7, the LLVM JIT Compiler represents the core of the proposed dynamic MPEG RVC decoder. The LLVM is surrounded by two RVCspecific components that bring LLVM compliant with RVC ADM. The first component corresponds to an equivalent-representation of a VTL provided by MPEG RVC, but is described into an LLVM representation. This VTL, we call it portable VTL, must keep the same information from an RVC-CAL actor with a lower level of representation of its computation to be manageable by LLVM. The section 4 is dedicated to the production of this portable VTL. The second component works as a layer of the LLVM JIT Compiler. The Just-In-Time Adaptive Decoder Engine (JADE) manages a description/configuration of an ADM and the portable VTL to produce decoders in LLVM IR. This LLVM IR of ADM is finally sent to the JIT Compiler to produce efficient machine code, fitted to the target platform. JADE is also able to produce network scheduling instructions and to manage the execution of the final decoder. The section 5 is dedicated to the description of this engine. The translation of an RVC-CAL FU into LLVM IR must keep the high-level information from the original model, but with a very low-level description of the FU processing and behavior. We choose to base the translation process for the portable VTL -i.e. from an RVC-CAL FU of the VTL into an LLVM-equivalent representation-on the Orcc Intermediate Representation (Orcc IR) as this representation is closer to the LLVM IR. The compilation framework of Orcc for a given RVC-CAL dataflow program to target a specific language is made in two-steps:

llvm-rvc

LLVM Code Generation of CAL Actor

1. A unique front-end parses the FUs of a given network and translates them into a an Orcc-specific Intermediate Representation (Orcc IR), 2. A dedicated back-end loads the network and the actors in Orcc IR form to generate code in the targeted language.

To produce the portable VTL needed by the JADE, we developed a new LLVM back-end that starts from the low-level Orcc IR to produce LLVM IR of an entire VTL.

Orcc Intermediate Representation

The Orcc IR is a conservative representation of a dataflow program in terms of structure and semantic while being at a lower level of representation. It is a common denominator of potential target languages such as C, C++ or Java without favoring one in particular.

Each actor representation is serialized in JavaScript Object Notation (JSON) description format. Figure 9 shows the structure of the Absolute Value actor (Fig 2) in Orcc IR. The JSON description contains name, pattern and a list of actions of the actor. The F SM of the actor is translated into a list of state-to-state transitions. P riorities become a list of action tags sorted by decreasing priority.

" name " : " Abs " , " inputs " : [ " int " , [START_REF] Lee | Dataflow Process Networks[END_REF] , " I " ] , " outputs " : [ " u int " , [START_REF] Lee | Synchronous data flow[END_REF] , " O " ] , " action s " : [ [ (...) ] " action scheduler " : [ " s0 " , // Initial states [ " s0 " , " s1 " , " s2 " ] , [ " u int " , [START_REF] Lee | Synchronous data flow[END_REF]]]] ,

// States [ [ " s0 " , [ [ [ " b " ] , " s1 " ] , [ [ " a " ] , " s2 " ] ] ] , [ " s1 " , [ [ [ " n " ] , " s0 " ] ] ] , [ " s2 " , [ [ [ " p " ] , " s0 " ] ] ] ] ]
[[ " I " ] ,[ " List " , [START_REF] Amer | Reconfigurable Video Coding: The Video Coding Standard for Multi-core Platforms[END_REF] , [ " u int " , [START_REF] Lee | Dataflow Process Networks[END_REF]]]] , The conditions to fire an action become an isSchedulable function (Fig. 11), which tests value and the number of token on the input of the action, as well as testing guard condition if it exists. If isSchedulable returns true, it means that the current action can be fired. Specific operations dealing with FIFOs become read, write, hasT okens or peek statements. This is necessary in Orcc IR because the semantics of RVC-CAL specify that the input and output patterns may have read/write several tokens as a list, or may have to reorder tokens.

[[ " u " ] ,[ " u int " ,[15]]] ] , [ [ " read " ,[[ " I " ] , " I " ,1]] , [ " load " ,[[ " u " ,1] ,[ " I " ] ,[0]]] , [ " store " ,[[ " O " ] ,[0] ,[ " var " ,[ " u " ,1]]]] , [ " write " ,[[ " O " ] , " O " ,1]] ]

LLVM Transformation

The llvm back-end produces a portable VTL by translating each FU of the VTL in Orcc IR into separate files in LLVM IR. One VTL generation fits every platform supported by the LLVM infrastructure. The Orcc IR and LLVM IR have some similarities that help the translation process for the LLVM back-end. They are both in SSA form with an unlimited number of registers. They have both integer types with arbitrary bit widths. Both IRs have instructions with similar semantics, those include assignment to a local variable, load/store memory operations and φ assignments.

The first main difference between LLVM and the Orcc IR is that the Orcc IR supports arithmetic expressions in assignments, load/store, and conditional branches, while LLVM only has support for three-address code(3AC) [START_REF] Lattner | LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation[END_REF]. Three-Address Code (3AC) is a form used to improve compiler analysis. Each instruction of the 3AC form is described as a 4-tuple: operator, operand1, operand2, result. The general form of 3AC is x := y op z, where x, y and z are variables, constants or temporary variables and op is an arithmetic operator. In Orcc IR, each expression that contains more than one fundamental operation is decomposed into an equivalent series of instructions fit to 3AC form and SSA constraint.

define void @pod () { entry :

; Read node % I = call i8 * @getReadPtr (% fifo * @I , i32

; Load node % u_0 = getelementptr i8 * %I , i1 0 % u_1 = load i8 * % u ; Write node % O = call i8 * @getWritePtr (% fifo * @O , i32 1)

; Store node store i8 u_1 , i8 * % O ret void } The other difference between LLVM and Orcc IR is that conditional branch nodes, namely if and while nodes, have no equivalent in LLVM IR. The Control Flow Graph (CFG) of a function in the LLVM IR is a list of basic blocks, each basic block starting with a label. A basic block contains a list of instructions, and ends with a terminator instruction, such as a branch instruction or function return instruction.

The Figure 12 represents the body of the action pos, described in CAL on Figure 2 and in Orcc IR on Figure 10. Its associated firing condition is represented in LLVM on Figure 13 and in Orcc IR on Figure 11.

LLVM Metadata information is used to carry the structural information of an FU. Structural information of an FU is the elements in the Orcc IR that have any influence on computation, namely name, inputs, outputs, parameters, actions and FSM of an FU. This structural define i1 @ i s S c h e d u l a b l e _ p o s () { entry : % _tmp1_0 = call i1 @hasTokens (% fifo * @I , i32 1) br i1 % _tmp1_1 , label % bb2 , label % bb3 bb2 : br label % bb4 ; Fifo has token bb3 : br label % bb4 ; Fifo has no token bb4 : % _tmp0_1 = phi i1 [1 , % bb2 ] , [0 , % bb3 ] ret i1 % _tmp0_1 } information is necessary for the JADE to connect actors in dataflow programs, to generate schedulers or to apply actor transformation inside an ADM, for instance the merging of actors [START_REF] Wipliez | Classification and Transformation of Dynamic Dataflow Programs[END_REF]. Figure 14 corresponds to the metadata description of Absolute Value actor. This representation is equivalent to the Orcc IR description given in Figure 9. LLVM variables and functions are incorporated inside metadata to bound metadata information with their corresponding elements in the LLVM IR. Using metadata allows to have no information lost between Orcc IR and an LLVM IR of an actor.

Just-In-Time Adaptive Decoder Engine

The second step of the approach is to produce a decoder that dynamically instantiates MPEG decoders according to a network description/configuration and the portable VTL. To achieve this goal, the Just-In-Time Adaptive Decoder Engine manages the LLVM infrastructure for dynamically translating LLVM IR into optimized machine code. The JADE also integrates scheduling rules to execute the generated decoder. The role of JADE is to manage the instantiation of networks. Instantiation of a network designates the initialization of actors, FIFOs and the network scheduling from an RVC description. JADE creates LLVM representation of decoders in a five steps process described on Figure 15 : 1. XDF parsing: XDF description is parsed into a Directed Acyclic Graph (DAG) that describes the structure of the network. This DAG helps analysis based on dataflow graph as explain in [START_REF] Kwong Kwok | High-performance algorithms for compile-time scheduling of parallel processors[END_REF]. XDF parsing also provides information about the list of FUs in the VTL, the number of instances of an FU and connections in the network to the actor parsing, FIFO instantiation and scheduler generator. 2. Actor parsing: Required FUs in the VTL are parsed using LLVM metadata to keep information about actor behavior and structure. They are stored in memory in a form of simple structure that will be sent to the module generation.

Decoder Code Generation

Module generation:

The parsed FUs are duplicated in an only LLVM module that represents the LLVM representation of the decoder. This is necessary because some FUs can be instantiated many times. It also helps the LLVM JIT Compiler to process optimization on the overall decoder.

4. FIFO instantiation: FIFOs are instantiated and connected to every actor's ports. The FIFOs used are unidirectional circular buffers that allow actors to be executed on different threads without the use of semaphores for data synchronization. 5. Scheduler generation: Scheduling instructions are inserted in the decoder module to define how processes are given access to system resources. The scheduling part of the decoder has been designed to be modular and interchangeable to give the choice to developers to select scheduling algorithms that best fit the targeted platform.

The generated decoder, represented as an only LLVM module, is finally sent to the LLVM JIT Compiler to produce efficient machine bytecode of the decoder in a three steps process:

1. Optimization: The generated single module passes through aggressive optimizations, selected according to their efficiency for the targeted platform. 2. Compilation: LLVM module is JIT translated into machine bytecode. If the targeted platform is not supported by the JIT Compiler, LLVM also integrates an interpreter that executes LLVM IR line by line. 3. Execution: Main scheduler function is executed in a dedicated thread that can be run, stop and partially reconfigured at any times by the JADE.

Decoder execution

Network scheduling process corresponds to the most sensitive part of JADE for decoder's achievement. For the first implementation of the JADE, we choose to implement a simple round-robin scheduler that avoids complex graph analysis and offers abilities for multi-core execution [START_REF] Amer | Reconfigurable Video Coding: The Video Coding Standard for Multi-core Platforms[END_REF]. This round robin scheduler follows the Dataflow Process Networks (DPN) model introduced by [START_REF] Lee | Dataflow Process Networks[END_REF]. DPN models are dynamically scheduled; hence this scheduler consists in an endless call of each actor in the network as represented in Figure 16.

define void @scheduler () { entry : call void @actor_1 call void @actor_2 . . call void @actor_n br label % entry ; loop to entry } Fig. 16 LLVM representation of a round robin scheduler for a network of n actors.

An actor is called by executing its associated action scheduler. An action scheduler is a function added to each actor at scheduler generation that rules the firing of actions. Figure 17 represents the action scheduler of define void @abs () { entry : switch i32 @_FSM_state , label % default [ i32 0 , label % s0 i32 1 , label % s1 i32 2 , label % s2 ] s0 : % s0 = call i1 @s0_scheduler () br i1 % s0 , label % entry , label % return s1 : % s1 = call i1 @s1_scheduler () br i1 % s1 , label % entry , label % return s2 : % s2 = call i1 @s1_scheduler () br i1 % s2 , label % entry , label % return return : ret void } Fig. 17 Representation of the action scheduler of the actor abs in LLVM IR.

the actor pos. The Finite State Machine (FSM) of an RVC-CAL Actor is translated into an LLVM switch instruction. The switch instruction calls a state scheduler corresponding to the current actor state. Figure 18 represents the state scheduler of state s1 in actor abs. Actions are listed according to their priorities in the FSM. Firing an action corresponds to test if an action is fireable, namely by calling the associated isSchedulable function. If an action is defined as fireable, the function corresponding to the body of the action can be called. The strength of the round-robin scheduler consists in the preservation of the scalability of the original model. Indeed, all actors are still considered as independent entities, without any knowledge about the execution se-quence of actions. The execution of the network -i.e. calls of action schedulers -can be made by one or more round robin scheduler. A round robin scheduler can contain from one to all the actors of a network. In a case of multiple cores, a group of FUs can be mapped onto several round robin schedulers and each round robin scheduler can be affected onto a separate core of the platform. This scheduler enhances parallelism and pipelining in each process of the whole application.

The strength of our model constitutes also its principal weakness if we compare the achievement of our decoder with an equivalent sequential code for a uniprocessor system. As the scheduler does not contain any information about the order to execute actions for each actor, every action has to be tested before determining if it can be executed. This scheduler involves an important overhead that can be reduced by finding static execution rules in the original dataflow network. We plan in future works to reduce this overhead by coupling our scheduler with analyzing tools for dataflow networks that would automatically detect sequential execution order of actions as presented in [START_REF] Gu | Exploring the concurrency of an MPEG RVC decoder based on dataflow program analysis[END_REF][START_REF] Wipliez | Classification and Transformation of Dynamic Dataflow Programs[END_REF]. LLVM metadatas that we embedd inside LLVM IR of actor enable at runtime such analysis.

Results

This section presents the experimental results led on the proposed concept. The goals of these experiments are to show the portability of the VTL, the relevance of using LLVM as an intermediate representation and the multicore ability of the scheduler.

With this aim in mind, we developed the JADE, described in Figure 5, in C++6 coupled with LLVM 2.6 7 . We also used the Orcc LLVM backend to generate a portable VTL from RVC-CAL standardized FUs.

The FUs currently available in the VTL of MPEG RVC are the coding tools from MPEG-4 Part-2 Simple Profile (SP) and MPEG-4 Advanced Video Coding (AVC) standards. The JADE has been compiled and the portable VTL copied on several OS with an Intel E6600 Core2 Duo processor at 2.40 GHz running with Windows 7, Mac OS X 10.5 and Linux Ubuntu 9.10.

Portable VTL generation

The portable VTL has been tested on the MPEG RVC VTL at its current state of standardization. This VTL is currently composed of 69 RVC-CAL FUs, [START_REF] Sangappa | Benchmarking Java against C/C++ for interactive scientific visualization[END_REF] The given results shows the lightness of LLVM bytecode size comparable to Java bytecode, which allows the portable VTL to be easily sent or incorporated into embedded system. All the files include in the resulting VTLs were compiled independently with no optimization enabled. The important size of the C compiled version of VTL is explained by the fact that C files are incorporating FIFO headers, where Java and LLVM does not use header and externalize functions.

Real-Time decoding of CIF video

The second experiment compares the achievement of decoders generated by JADE with equivalent static C and Java decoders with the same round-robin scheduling execution. The configurations of decoders used are described in [START_REF] Bhattacharyya | Overview of the MPEG reconfigurable video coding framework[END_REF] for the MPEG-4 Part-2 Simple Profile (SP) decoder and from [START_REF] Gorin | An RVC Dataflow Description of the AVC Constrained Baseline Profile Decoder[END_REF] for the MPEG-4 Advanced Video Coding (AVC) Constrained Baseline Profile (CBP). We considered those two configurations of decoder as the most representative of MPEG RVC as they cover all the VTL. Some of these FUs are instantiated several times in decoders, the RVC description of the MPEG-4 SP decoder contains 64 instances and the RVC description of the MPEG-4 AVC contains 92 instances. These decoders were respectively tested on conformance testing sequences for SP decoders 8 3, shows that the impact of the LLVM Virtual Machine is unseen on Windows and Linux. The static Java versions of these same decoders running on the Java Virtual Machine (JVM) are running three times slower than LLVM decoders. This speed factor can be explained by the fact that does not allocate local arrays on the stack. Each fifo access involve new memory allocation, which must be freed by the garbage collector of the Virtual Machine.

C

Java LLVM Windows (VS C++) 30,9 fps 5,6 fps 31,7 fps Linux/MacOsX (GCC) 34,9 fps 5,5 fps 34,5 fps Preliminary results show that the configuration and reconfiguration times of the MPEG-4 SP decoder are about 800 milliseconds and about 1 second for the MPEG-4 AVC description. This reconfiguration time can be greatly improved by encapsulating dataflow network representation into bitstream and by supporting partial reconfiguration of decoders.

Scalable execution

This section tests the multi-core abilities of JADE generated decoders on the Core2Duo processor. The use case are taken from [START_REF] Amer | Reconfigurable Video Coding: The Video Coding Standard for Multi-core Platforms[END_REF] and applied to the Jade. Two POSIX threads were used on Linux to implement two roundrobin schedulers, with one round-robin scheduler per core. Each scheduler was precompiled with a list of actors manually distributed. The decoders used is the same configuration of MPEG-4 Part-2 Simple Profile (SP) presented on Table 2 The performance given on Table 4 shows benefits of the multi-core (up to 1.5), depending on the configuration used. We considered these results as a proof that a network analysis is mandatory to obtain a smart and automatic dispatchment of the actors into several schedulers.

Conclusion and perspective

This paper presents a new concept of dynamic decoder able to fully support ADM from MPEG RVC. It enables an automatic translation of dataflow programs written in RVC-CAL into an LLVM representation to take the benefits of the LLVM infrastructure. As a result, generated decoder can be dynamically compiled and executed with reasonable impact on the performance, relatively with a static compilation of the same decoder. Moreover, the generated decoder contains scalable parallelism based on a simple mechanism that can be introduced into a wide range of platform.

The next milestone of this concept of dynamic RVC decoder is to get an automatic distribution of the actors from a dataflow program into the processing resources of the targeted platform. The Dif package [START_REF] Plishker | Functional DIF for rapid prototyping[END_REF] shows some mechanisms to insert more information about decoder execution, specifically static execution of part of models, into a decoder description (XDF). Finally, we take MPEG RVC as the base application for JADE, but the concept of ADM representation can also be extends to others Medias that involve signal processing, such as audio, cryptographic or 3D applications.

Fig. 2

 2 Fig. 2 Description of the Absolute Value actor in RVC-CAL.

Fig. 4

 4 Fig. 4 Absolute Value actor before and after firing.

Fig. 5

 5 Fig. 5 Representation of the dynamic MPEG RVC decoder.

%X = add i 3 2 4

 4 , 9 ; a f f e c t 4 added t o 9 i n %X %Y = c a l l i 3 2 @hasToken ( ) ; C a l l hasToken f u n c t i o n %cond = eq i 3 2 %Y, 1 ; P r o d u c e s a b o o l v a l u e br i 1 %cond , l a b e l %True , l a b e l %F a l s e ; Cond . branch True : . . .

Fig. 6

 6 Fig. 6 LLVM IR coding example.

Fig. 7

 7 Fig. 7 Infrastructure of our dynamic RVC decoder.

Fig. 8

 8 Fig. 8 Infrastructure of llvm-rvc decoder.

Fig. 9

 9 Fig. 9 Description of the structure of Absolute Value actor in Orcc Intermediate Representation.

Fig. 10

 10 Fig. 10 Description of the action pos of Absolute Value actor in Orcc Intermediate Representation.

"Fig. 11

 11 Fig. 11 Description of the firing condition of the action pos of Absolute Value actor in Orcc Intermediate Representation.

Fig. 12

 12 Fig. 12 Description of the action pos of Absolute Value actor in LLVM Representation.

Fig. 13

 13 Fig. 13 Description of the firing condition of the action pos of Absolute Value actor in LLVM Representation.

!Fig. 14

 14 Fig. 14 Description of the structure of Absolute Value actor using LLVM metadata.

Fig. 15

 15 Fig. 15 Infrastructure of the Just-In-Time Adaptive Decoder Engine.

Fig. 18

 18 Fig. 18 Representation of the scheduler of the state s0 for the actor abs in LLVM IR.

Table 1

 1 are coming from the MPEG-4 SP standard and 47 are coming from MPEG-4 AVC standard. The portable VTL generated is compared on table 1 with the resulting files of other backends of Orcc, namely the C back-end and Java back-end, running on the same VTL. The compiling tools used are gcc V4.3.2 for C, javac V1.6.0 for Java and the llvm assembler from LLVM 2.6. Comparison of the compilation size without optimization of a same VTL generated in C, Java and LLVM. The VTL includes FUs from MPEG-4 Simple Profile (SP) standard and from MPEG-4 Advanced Video Coding (AVC) standard.

		C	Java	LLVM
	MPEG-4 SP	1,74 Mb	300 Kb	285 Kb
	+ MPEG-4 AVC 2,29 Mb	775 Kb	755 Kb
	VTL	4.03 Mb 1,04 Mb 1,01 Mb

  and AVC decoders 9 .

		C	Java	LLVM
	Windows (VS C++)	26,7 fps 7,0 fps 24,9 fps
	Linux/MacOsX (GCC) 26,6 fps 9,7 fps 26,4 fps

Table 2

 2 Decoder performance of an MPEG-4 Part-2 Simple Profile configuration for CIF sequences (352 × 288). integrated development environment (IDE) used to compile C and Java is namely Microsoft Visual Studio 2008 Express for C and Eclipse V3.6.0 for JAVA. The comparison results, on Table2 and Table

	The

Table 3

 3 Decoder performance of an MPEG-4 Advanced Video Coding configuration for QCIF sequences (176 × 144).

  .

	Core 1	Core 2	gain
	Parser	Texture + Motion 1%
	Parser + Motion	Texture	33%
	Parser + Texture	Motion	50%

Table 4

 4 Gain by an execution on two threads of the MPEG-4 Simple Profile decoder compared to a unicore execution.

http://www.tik.ee.ethz.ch/ moses

http://opendf.sourceforge.net

http://www.actors-project.eu

http://ptolemy.eecs.berkely.edu

http://orcc.sourceforge.net

C++ implementation of Jade is available at: http://sourceforge.net/projects/orcc

LLVM 2.6 is available at: http://llvm.org/

Video sequences available at: http://standards.iso.org/

Video sequences available at: http://wftp3.itu.int/avarch/jvt-site/