Claire Gardent
email: claire.gardent@loria.fr

Benjamin Gottesman
email: ben.gottesman@acrolinx.com

Laura Perez-Beltrachini

Comparing the performance of two TAG-based surface realisers using controlled grammar traversal

We present GENSEM, a tool for generating input semantic representations for two sentence generators based on the same reversible Tree Adjoining Grammar. We then show how GENSEM can be used to produced large and controlled benchmarks and test the relative performance of these generators.

Introduction

Although computational grammars are mostly used for parsing, they can also be used to generate sentences. This has been done, for instance, to detect overgeneration by the grammar [START_REF] Gardent | Spotting overgeneration suspects[END_REF]. Sentences that are generated but are ungrammatical indicate flaws in the grammar. This has also been done to test a parser [START_REF] Nederhof | Efficient generation of random sentences[END_REF][START_REF] Purdom | A sentence generator for testing parsers[END_REF]. Using the sentences generated from the grammar ensures that the sentences given to the parser are in the language it defines. Hence a parse failure necessarily indicates a flaw in the parser's design as opposed to a lack of coverage by the grammar.

Here we investigate a third option, namely, the focused benchmarking of sentence realisers based on reversible grammars, i.e. on grammars that can be used both to produce sentences from a semantic representation and semantic representations from a sentence.

More specifically, we present a linguisticallycontrolled grammar traversal algorithm for Tree Adjoining Grammar (TAG) which, when applied to a reversible TAG, permits producing arbitrarily many of the semantic representations associated by this TAG with the sentences it generates. We then show that the semantic representations thus produced can be used to compare the relative performance of two sentence generators based on this grammar.

Although the present paper concentrates on Tree Adjoining Grammar realisers, it is worth pointing out that the semantic representations produced could potentially be used to evaluate any surface realiser whose input is a flat semantic formula.

Section 2 discusses related work and motivates the approach. Section 3 presents GENSEM, the DCG-based grammar traversal algorithm we developed. We show, in particular, that the use of a DCG permits controlling grammar traversal in such a way as to systematically generate sets of semantic representations covering certain computationally or linguistically interesting cases. Finally, Section 4 reports on the benchmarking of two surface realisers with respect to a GENSEM-produced benchmark.

Motivations

Previous work on benchmark construction for testing the performance of surface realisers falls into two camps depending on whether or not the realiser uses a reversible grammar, that is, a grammar that can be used for both parsing and generation.

To test a surface realiser based on a large reversible Head-Driven Phrase Structure Grammar (HPSG), [START_REF] Carroll | An efficient chart generator for (semi-)lexicalist grammars[END_REF] use a small test set of two hand-constructed and 40 parsingderived cases to test the impact of intersective modifiers1 on generation performance. More recently, [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF] present a perfor-mance evaluation which uses as a benchmark the set of semantic representations produced by parsing 130 sentences from the Penn Treebank and manually selecting the correct semantic representations. Finally, [START_REF] White | Reining in CCG chart realization[END_REF] profiles a CCG 2based sentence realiser using two domain-focused reversible CCGs to produce two test suites of 549 and 276 semantic formula, target sentence pairs, respectively.

For realisers that are not based on a reversible grammar, there are approaches which derive large sets of realiser input from the Penn Treebank (PTB). For example, [START_REF] Langkilde-Geary | An empirical verification of coverage and correctness for a generalpurpose sentence generator[END_REF] proposes to translate the PTB annotations into a format accepted by her sentence generator Halogen. The output of this generator can then be automatically compared with the PTB sentence from which the corresponding input was derived. Similarly, [START_REF] Callaway | Evaluating coverage for large symbolic NLG grammars[END_REF] builds an evaluation benchmark by transforming PTB trees into a format suitable for the KPML realiser he uses.

In all of the above cases, the data is derived from real world sentences, thereby exemplifying "real world complexity". If the corpus is large enough (as in the case of the PTB), the data can furthermore be expected to cover a broad range of syntactic phenomena. Moreover, the data, being derived from real world sentences, is not biased towards system-specific capabilities. Nonetheless, there are also limits to these approaches.

First, they fail to support graduated performance testing on constructs such as intersective modifiers or lexical ambiguity, which are known to be problematic for surface realisation.

Second, the construction of the benchmark is in both cases time consuming. In the reversible approach, for each input sentence, the correct interpretation must be manually selected from among the semantic formulae produced by the parser. As a side effect, the constructed benchmarks remain relatively small (825 in the case of [START_REF] White | Reining in CCG chart realization[END_REF]; 130 in [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF]). In the case of a benchmark derived by transformation from a syntactically annotated corpus, the implementation of the converter is both time-intensive and corpus-bound. For instance, [START_REF] Callaway | Evaluating coverage for large symbolic NLG grammars[END_REF] re-2 Combinatory Categorial Grammar ports that the implementation of such a processor for the SURGE realiser was the most timeconsuming part of the evaluation with the resulting component containing 4000 lines of code and 900 rules.

As we shall show in the following sections, the GENSEM approach to benchmark construction aims to address both of these shortcomings. By using a DCG to implement grammar traversal, it permits both a full automation of the benchmark creation and some control over the type and the distribution of the benchmark items.

GenSem

As mentioned above, GENSEM is a grammar traversal algorithm for TAG. We first present the specific TAG used for traversal, namely SEMX-TAG [START_REF] Alahverdzhieva | XTAG using XMG[END_REF]) (section 3.1). We then show how to automatically derive a DCG that describes the derivation trees of this grammar (section 3.2). Finally, we show how this DCG encoding permits generating formulae while enabling control over the set of semantic representations to be produced (section 3.3).

SemXTAG

The SEMXTAG grammar used by GENSEM and by the two surface realisers is a Feature-Based Lexicalised Tree Adjoining Grammar augmented with a unification-based semantics as described by [START_REF] Gardent | Semantic construction in FTAG[END_REF]. We briefly introduce each of these components and describe the grammar coverage.

FTAG.

A Feature-based TAG (Vijay-Shanker and Joshi, 1988) consists of a set of (auxiliary or initial) elementary trees and of two treecomposition operations: substitution and adjunction. Initial trees are trees whose leaves are labelled with substitution nodes (marked with a downarrow) or terminal categories. Auxiliary trees are distinguished by a foot node (marked with a star) whose category must be the same as that of the root node. Substitution inserts a tree onto a substitution node of some other tree while adjunction inserts an auxiliary tree into a tree. In an FTAG, the tree nodes are furthermore decorated with two feature structures (called top and bottom) which are unified during derivation as follows. On substitution, the top of the substitution node is unified with the top of the root node of the tree being substituted in. On adjunction, the top of the root of the auxiliary tree is unified with the top of the node where adjunction takes place; and the bottom features of the foot node are unified with the bottom features of this node. At the end of a derivation, the top and bottom of all nodes in the derived tree are unified. Finally, each sentence derivation in an FTAG is associated with both a derived tree representing the phrase structure of the sentence and a derivation tree recording how the corresponding elementary trees were combined to form the derived tree.

FTAG with semantics. To associate semantic representations with natural language expressions, the FTAG is modified as proposed by [START_REF] Gardent | Semantic construction in FTAG[END_REF].

NP j John name(j,john) S b NP↓ c VP b a V a runs run(a,c) VPx often VP*x often(x)
⇒ name(j,john), run(a,j), often(a)

Figure 1: Flat semantics for "John often runs"

Each elementary tree is associated with a flat semantic representation. For instance, in Figure 1,3 the trees for John, runs, and often are associated with the semantics name(j,john), run(a,c), and often(x), respectively. Importantly, the arguments of a semantic functor are represented by unification variables which occur both in the semantic representation of this functor and on some nodes of the associated syntactic tree. For instance in Figure 1, the semantic index c occurring in the semantic representation of runs also occurs on the subject substitution node of the associated elementary tree. The value of semantic arguments is determined by the unifications resulting from adjunction and substitution. For instance, the semantic index c in the tree for runs is unified during substitution with the semantic index labelling the root node of the tree for John. As a result, the semantics of John often runs is {name(j,john),run(a,j),often(a)}.

SemXTAG. SEMXTAG is an FTAG for English augmented with a unification-based compositional semantics of the type described above. Its syntactic coverage approaches that of XTAG, the FTAG developed for English by the XTAG group (The XTAG Research Group, 2001). Like this grammar, it contains around 1300 elementary trees and covers auxiliaries, copula, raising and small clause constructions, topicalization, relative clauses, infinitives, gerunds, passives, adjuncts, ditransitives and datives, ergatives, it-clefts, whclefts, PRO constructions, noun-noun modification, extraposition, sentential adjuncts, imperatives and resultatives.

Converting SemXTAG to a DCG

We would like to be able to traverse SEMXTAG in order to generate semantic representations that are licensed by it. In the DCG formalism, a grammar is represented as a set of Prolog definite clauses, and Prolog's query mechanism provides built-in grammar traversal. We take advantage of this by deriving a DCG from SEMXTAG and then using Prolog queries to generate semantic representations that are associated with sentences in the language described by it.

Another advantage of the DCG formalism is that arbitrary Prolog goals can be inserted into a rule, to constrain when the rule applies or to bind variables occurring in it. We use this to ground derivations with lexical items, which are represented using Prolog assertions. We also use it to control Prolog's grammar traversal in such a way as to generate sets of semantic formulae covering certain computationally interesting cases (see section 3.3).

Our algorithm for converting SEMXTAG to a DCG is inspired by [START_REF] Schmitz | Feature unification in TAG derivation trees[END_REF], who derive from an FTAG a feature-based regular tree grammar (RTG) whose language is the derivation trees of the FTAG. Indeed, in our implementation, we derive a DCG from such an RTG, thereby taking advantage of a SEMXTAG-to-RTG converter previously implemented by Sylvain Schmitz.

TAG to RTG. In the conversion to RTG4 , each elementary tree in SEMXTAG is converted to a rule that models the contribution of the tree to a TAG derivation. A TAG derivation involves the selection of an initial tree, which has some nodes requiring substitution and some permitting adjunction. Let us think of the potential adjunction sites as requiring, rather than permitting, adjunction, but such that the requirement can be satisfied by 'null' adjunction. Inserting another tree into this initial tree satisfies one of the substitution or adjunction requirements, but introduces some new requirements into the resulting tree, in the form of its own substitution nodes and adjunction sites.

Thus, intuitively, the RTG representation of a SEMXTAG elementary tree is a rule that rewrites the satisfied requirement as a local tree whose root is a unique identifier of the tree and whose leaves are the introduced requirements. A requirement of a substitution or adjunction of a tree of root category X is written as X S or X A , respectively. Here, for example, is the translation to RTG of the TAG tree (minus semantics) for runs in Figure 1, using the word anchoring the tree as its identifier (the superscripts abbreviate feature structures: b/t refers to the bottom/top feature structure and the upper case letters to the semantic index value, so [idx : X] is abbreviated to X):

S [t:T ] S → runs(S [t:T,b:B] A N P [t:C] S V P [t:B,b:A] A V [t:A] A )
The semantics of the SEMXTAG tree are carried over as-is to the corresponding RTG rule. Further, the feature structures labelling the nodes of SEMXTAG trees are carried over to the RTG rules so as to correctly interact with substitution and adjunction (see [START_REF] Schmitz | Feature unification in TAG derivation trees[END_REF] for more details on this part of the conversion process).

To account for the optionality of adjunction, there are additional rules allowing any adjunction requirement to be rewritten as the symbol ǫ, a terminal symbol of the RTG.

The terminal symbols of the RTG are thus the tree identifiers and the symbol ǫ, and its nonterminals are X S and X A for each terminal or non-terminal X of SEMXTAG.

RTG to DCG. Since the right-hand side of each RTG rule is a local tree -that is, a tree of depth no more than one -we can flatten each of them into a list consisting of the root node followed by the leaves without losing any structural information. This is the insight underlying the RTG-to-DCG conversion step. Each RTG rule is converted to a DCG rule that is essentially identical except for this flattening of the right-hand side. Here is the translation to DCG of the RTG rule above5 : We represent non-terminals of the DCG using the rule predicate, whose five (non-hidden)6 arguments, in order, are the category, the subscript (init for subscript S, aux for subscript A), the top and bottom feature values, and the semantics. Feature structures are represented using Prolog lists with a fixed argument position for each attribute in the grammar (in this example, only the index attribute). The semantics associated with the left-hand-side symbol (here, Sem;S;N;VP;V, with the semicolon representing semantic conjunction) are composed of the semantics associated with this rule and those associated with each of the right-hand-side symbols.

The language of the resulting DCG is neither the language of the RTG nor the language of SEMXTAG, and indeed the language of the DCG does not interest us but rather its derivation trees.

These are correlated one-to-one with the trees in the language described by the RTG, i.e. with the derivation trees of SEMXTAG, and the latter can be trivially reconstructed from the DCG derivations. From a SEMXTAG derivation tree, one can compose the semantic representation of the associated sentence, and in fact this semantic composition occurs as a side effect of a Prolog query against the DCG, allowing semantic representations licensed by SEMXTAG to be returned as query results.

We define a Prolog predicate for querying against the DCG, as follows. Its one input argument, Cat, is the label of the root node of the derivation tree (typically s), and its one output argument, Sem, is the semantic representation associated with that tree7 . genSem(Cat,Sem) :rule(Cat,init,_,_,Sem,_,[]).

Control parameters

In order to give the users some control over the sorts of semantic representations that they get back from a query against the DCG, we augment the DCG in such a way as to allow control over the TAG family8 of the root tree in the derivation tree, over the number and type of adjunctions in the derivation, and over the depth of substitutions.

To implement control over the family is quite simple: we need merely to index the DCG rules by family and modify the GENSEM call accordingly.

For instance, the above DCG rule becomes :

rule(s,init,Top,Bot,n0V,Sem;S;NP;VP;V) --> [runs], {lexicon(runs,n0V,[run])}, ...

We implement restrictions on adjunctions by adding an additional argument to the grammar symbols, namely a vector of non-negative integers representing the number of non-null adjunctions of each type that are in the derivation subtree dominated by the symbol. By 'type' of adjunction, we mean the category of the adjunc-tion site. In DCG terms, a non-null adjunction of a category X is represented as the expansion of an x/aux symbol other than as ǫ. So, for example, a DCG symbol associated with the vector [1,0,0,0,0], where the five dimensions of the vector correspond to the n, np, v, vp, and s categories, respectively, dominates a subtree containing exactly one n/aux symbol expanded by a non-epsilon rule, and no other aux symbol expanded by a non-epsilon rule. We link the vector associated with the root of the derivation to the query predicate.

We define a special predicate to handle the divvying up of a mother node's vector among the daughters, taking advantage of the fact that the DCG formalism permits the insertion of arbitrary Prolog goals into a rule.

Finally, we add an additional argument to the DCG rule and to the GENSEM's call to control the traversal depth with respect to the number of substitutions applied. The overall depth of each derivation is therefore constrained both by the user defined adjunctions and substitution depth constraints.

Our query predicate now has four input arguments and one output argument:

Using GENSEM for benchmarking

We now show how GENSEM can be put to work for comparing two TAG-based surface realisers, namely GENI [START_REF] Gardent | Spotting overgeneration suspects[END_REF] and RT-GEN (Perez-Beltrachini, 2009). These two realisers follow globally similar algorithms but differ in several respects. We show how GENSEM can be used to produce benchmarks that are tailored to test hypotheses about how these differences might impact performance. We then use this GENSEMgenerated benchmark to compare the performance of the two realisers.

GenI and RTGen

Both GENI and RTGEN use the SEMXTAG grammar described in section 3.1. Moreover, both realisers follow an algorithm pipelining three main phases. First, lexical selection selects from the grammar those elementary trees whose semantics subsumes part of the input semantics. Second, the tree combining phase systematically tries to combine trees using substitution and adjunction. Third, the retrieval phase extracts the yields of the complete derived trees, thereby producing the generated sentence(s).

There are also differences however. We now spell these out and indicate how they might impact the relative performance of the two surface realisers.

Derived vs. derivation trees. While GENI constructs derived trees, RTGEN uses the RTG encoding of SEMXTAG sketched in the previous section to construct derivation trees. These are then unraveled into derived trees at the final retrieval stage. As noted by [START_REF] Koller | Generation as dependency parsing[END_REF], these trees are simpler than TAG elementary trees, which can favourably impact performance.

Interleaving of feature constraint solving and syntactic analysis. GENI integrates in the tree combining phase a filtering step in which the initial search space is pruned by eliminating from it all combinations of TAG elementary trees that cover the input semantics but cannot possibly lead to a valid derived tree. This filtering eliminates all combinations of trees such that either the category of a substitution node cannot be cancelled out by that of the root node of a different tree, or a root node fails to have a matching substitution site. Importantly, filtering ignores feature information and tree combining takes place after filtering. RTGEN, on the other hand, directly combines derivation trees decorated with full feature structure information.

Handling of intersective modifiers. GENI and RTGEN differ in their strategies for handling modification.

Adapting [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF] proposal to TAG, GENI adopts a two-step tree-combining process such that in the first step, only substitution applies, while in the second, only adjunction is used. Although the number of intermediate structures generated is still 2 n for n modifiers, this strategy has the effect of blocking these 2 n struc-tures from multiplying out with other structures in the chart.

RTGEN, on the other hand, uses a standard Earley algorithm that includes sharing and packing. Sharing allows intermediate structures common to several derivations to be represented once only while packing groups together partial derivation trees with identical semantic coverage and similar combinatorics (same number and type of substitution and adjunction requirements), keeping only one representative of such groups in the chart. In this way, intermediate structures covering the same set of intersective modifiers in a different order are only represented once and the negative impact of intersective modifiers is lessened.

Two GENSEM benchmarks

We use GENSEM to construct two benchmarks designed to test the impact of the differences between the two realisers and, more specifically, to compare the relative performance of both realisers (i) on cases involving intersective modifiers and (ii) on cases of varying overall complexity.

The MODIFIERS benchmark focuses on intersective modifiers and contains semantic formulae corresponding to sentences involving an increasing number of modifiers. Recall that GENSEM calls are of the form gensem(Cat,Family,[N,NP,V,VP,S],Dth,Sem) where N,NP,V,VP,S indicates the number of required adjunctions in N, NP, V, VP and S, respectively, while Family constrains the subcategorisation type of the root tree in the derivations produced by GENSEM. To produce formulae involving the lexical selection of intersective modifiers, we set the following constraints. Cat is set to s and Family is set to either n0V (intransitive verbs) or n0Vn1 (transitive verbs). Furthermore, N and V P vary from 0 to 4 thereby requiring the adjunction of 0 to 4 N and/or VP modifiers. All other adjunction counters are set to null. To avoid producing formulae with identical derivation trees but distinct lemmas, we use a restricted lexicon containing one lemma of each syntactic type, e.g. one transitive verb, one intransitive verb, etc. Given these settings, GENSEM produces 1 789 formulae whose adjunction requirements vary from 1 to 6. For instance, the semantic formula {sleep(b,c),man(c),a(c),blue(c),sleep(i,c),carefully(b)} (A sleeping blue man sleeps carefully) extracted from the MODIFIERS benchmark contains two NP adjunctions and one VP adjunction.

The MODIFIERS benchmark is tailored to focus on cases involving a varying number of intersective modifiers. To support a comparison of the realisers on this dimension, it displays little or no variation w.r.t. other dimensions, such as verb type and non-modifying adjunctions.

To measure the performance of the two realisers on cases of varying overall complexity, we construct a second benchmark (COMPLEXITY) displaying such variety. The GENSEM parameters for the construction of this suite are the following. The verb type (Family) is one of 28 possible verb types 9 . The number and type of required adjunctions vary from 0 to 4 for N adjunctions, 0 to 1 for N P , 0 to 4 for V P and 0 to 1 for S. The resulting benchmark contains 890 semantic formulae covering an extensive set of verb types and of adjunction requirements.

Results

Using the two GENSEM-generated benchmarks, we now compare GENI and RTGEN. We plot the average number of chart items against both the number of intersective modifiers present in the input (Figure 3) and the size of the Initial Search Space (ISS), i.e., the number of combinations of elementary TAG trees covering the input semantics to be explored after the lexical selection step (Figure 2). In our case, the ISS gives a more meaningful idea about the complexity than considering only the number of input literals. In an FTAG, the number of elementary trees selected 9 The 28 verb types are En1V,n0BEn1,n0lVN1Pn2,n0V,n0Va1,n0VAN1,n0VAN1Pn2,n0VDAN1,n0VDAN1Pn2,n0VDN1,n0VDN1Pn2,n0Vn1,n0VN1,n0Vn1Pn2,n0VN1Pn2,n0Vn2n1,n0Vpl,n0Vpln1,n0Vpn1,n0VPn1,n0Vs1,REn1VA2,REn1VPn2,Rn0Vn1A2,Rn0Vn1Pn2,s0V,s0Vn1,s0Vton1. The notational convention for verb types is from XTAG and reads as follows. Subscripts indicate the thematic role of the verb argument. n indicates a nominal, Pn a PP and s a sentential argument. pl is a verbal particle. Upper case letters describe the syntactic functor type: V is a verb, E an ergative, R a resultative and BE the copula. Sequences of upper case letters such as VAN in n0VAN1 indicate a multiword functor with syntactic categories V, A, and N. For instance, n0Vn1 indicates a verb taking two nominal arguments (e.g., like) and n0VAN1 a verb locution such as to cry bloody murder. by a given literal may vary considerably depending on the number and the size of the tree families selected by this literal. For instance, a literal selecting the n0Vn2n1 class will select many more trees than a literal selecting the n0V family because there are many more ways of realising the three arguments of a ditransitive verb than the single subject argument of an intransitive one. Chart items include all elementary trees selected by the lexical selection step as well as the intermediate and final structures produced by the tree combining phase. In RTGEN, we distinguish between the number of structures built before unpacking (packed chart) and the number of structures obtained after unpacking (unpacked chart).

Both realisers are implemetned in different programming languages, GENI is implemented in Haskell whereas RTGEN in Prolog. As for the time results comparison, preliminary experiments show that GENI is faster is simple input cases. On the other hand, in the case of more complex cases, the point of producing much less intermediate results pays off compared to the overhead of the chart/agenda operations.

Overall efficiency. The plot in Figure 2 shows the results obtained by running both realisers on the COMPLEXITY benchmark. Recall (cf. section 4.2) that the COMPLEXITY benchmark contains input with varying verb arity and a varying number of required adjunctions. Hence it provides cases of increasing complexity in terms of ISS to be explored. Furthermore, test cases in the benchmark trigger sentence realisation involving certain TAG families, which have a certain number of trees. Those trees within a family often have identical combinatorics but different features. Consequently, the COMPLEXITY benchmark also provides an appropriate testbed for testing the impact of feature structure information on the two approaches to tree combination.

The graphs show that as complexity increases, the performance delta between GENI and RT-GEN increases. We conjecture that as complexity grows, the filtering used by GENI does not suffice to reduce the search space to a manageable size. Conversely, the overhead introduced by RTGEN's all-in-one, tree-combining Earley with packing strategy seems compensated throughout by the construction of a derivation rather than a derived tree and pays off increasingly as complexity increases.

Modifiers.

Figure 3 plots the results obtained by running the realisers on the MODIFIERS benchmark. Here again, RTGEN outperforms GENI and the delta between the two realisers grows with the number of intersective modifiers to be handled. A closer look at the data shows that the global constraints set by GENSEM on the number of required adjunctions covers an important range of variation in the data complexity. For instance, there are cases where 4 modifiers modify the same NP (or VP) and cases where the modifiers are distributed over two NPs. Similarly, literals introduced into the formula by a GENSEM adjunction requirement vary in terms of the number of auxiliary trees whose selection they trigger. The steep curve in GENI's plot suggests that although the delayed adjunction mechanism helps in avoiding the proliferation of intermediate incomplete modifiers' structures, the lexical ambiguity of modifiers still poses a problem. In contrast, RTGEN's packing uniformly applies to word order variations and to the cases of lexical ambiguity raised by intersective modifiers because the items have the same combinatoric potential and the same semantics.

Conclusion

Surface realisers are complex systems that need to handle diverse input and require complex computation. Testing raises among other things the issue of coverage -how can the potential input space be covered? -and of test data creation -should this data be hand tailored, created randomly, or derived from real world text?

In this paper, we presented an approach which permits automating the creation of test input for surface realisers whose input is a flat semantic formula. The approach differs from other existing evaluation schemes in two ways. First, it permits producing arbitrarily many inputs. Second, it supports the construction of grammar-controlled, linguistically focused benchmarks.

We are currently working on further extending GENSEM with more powerful (recursive) control restrictions on the grammar traversal; on combining GENSEM with tools for detecting grammar overgeneration; and on producing a benchmark that could be made available to the community for testing surface realisers whose input is either a dependency tree or a flat semantic formula.

  genSem(Cat,Fam,[N,NP,V,VP,S],Dth,Sem):rule(Cat,init,_,_,Fam, [N,NP,V,VP,S],Dth,Sem,_,[]).

Figure 2 :

 2 Figure 2: Performance of realisation approaches on the COMPLEXITY benchmark, average unpacked chart size as a function of the ISS complexity.

Figure 3 :

 3 Figure 3: Performance of realisation approaches on the MODIFIERS benchmark, average unpacked chart size as a function of the number of modifiers.

As first noted by[START_REF] Brew | Letting the cat out of the bag: Generation for shake-and-bake MT[END_REF] and[START_REF] Kay | Chart generation[END_REF], given a set of n modifiers all modifying the same structure, all possible intermediate structures will be constructed, i.e.

, 2 n+1 .

C x /Cx abbreviate a node with category C and a top/bottom feature structure including the feature-value pair { index : x}.

For a more precise description of the FTAG to RTG conversion see[START_REF] Schmitz | Feature unification in TAG derivation trees[END_REF].

In practice, the lexicon is factored out, so there is no rule specifically for runs, but one for intransitive verbs (n0V) in general. Each rule hooks into the lexicon, so that a given invocation of a rule is grounded by a particular lexical item.

The --> notation is syntactic sugar for the usual Prolog :definite clause notation with two hidden arguments on each predicate. The hidden arguments jointly represent the list of terminals dominated by the symbol.

The 6th and 7th arguments of the rule call are the hidden arguments needed by the DCG.

TAG families group together trees which belong together, in particular, the trees associated with various realisation of a specific subcategorisation type. Thus, here the notion of TAG family is equivalent to that of subcategorisation type.

Acknowledgements

The research presented in this paper was partially supported by the European Fund for Regional Development within the framework of the INTER-REG IV A Allegro Project.


Claire Gardent
email: claire.gardent@loria.fr

Laura Perez-Beltrachini

RTG based surface realisation for TAG

Surface realisation with grammars integrating flat semantics is known to be NP complete. In this paper, we present a new algorithm for surface realisation based on Feature Based Tree Adjoining Grammar (FTAG) which draws on the observation that an FTAG can be translated into a Regular Tree Grammar describing its derivation trees. We carry out an extensive testing of several variants of this algorithm using an automatically produced testsuite and compare the results obtained with those obtained using GenI, another FTAG based surface realiser.

Introduction

As shown in [START_REF] Brew | Letting the cat out of the bag: generation for shake-and-bake mt[END_REF][START_REF] Koller | Generation as dependency parsing[END_REF], Surface Realisation is NP-complete. Various optimisation techniques have therefore been proposed to help improve practical runtimes. For instance, [START_REF] Kay | Chart generation[END_REF] proposes to reduce the number of constituents built during realisation by only considering for combination constituents with non overlapping semantics and compatible indices. [START_REF] Kay | Chart generation[END_REF][START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF][START_REF] Gardent | Spotting overgeneration suspect[END_REF] propose various techniques to restrict the combinatorics induced by intersective modifiers all applying to the same structure. And [START_REF] Koller | Generation as dependency parsing[END_REF][START_REF] Gardent | Spotting overgeneration suspect[END_REF] describe two alternative techniques for reducing the initial search space.

In this paper, we focus on the optimisation mechanisms of two TAG based surface realisers namely, GENI [START_REF] Gardent | Spotting overgeneration suspect[END_REF] and the algorithm we present in this paper namely, RT-GEN (Perez-Beltrachini, 2009). GENI's optimisation includes both a filtering process whose aim is to reduce the initial search space and a two step, "substitution before adjunction", tree combination phase whose effect is to delay modifier adjunction thereby reducing the number of intermediate structures being built. In RTGEN on the other hand, the initial FTAG is converted to a Regular Tree Grammar (RTG) describing its derivation trees and an Earley algorithm, including sharing and packing, is used to optimise tree combination.

We compare GENI with several variants of the proposed RTGEN algorithm using an automatically produced testsuite of 2 679 input formulae and relate the RTGEN approach to existing work on surface realisation optimisation.

The paper is structured as follows. We first present the grammar used by both GENI and RT-GEN, namely SEMXTAG (Section 2). We then describe the two surface realisation algorithms (Section 3). In Section 4, we describe the empirical evaluation carried out and present the results. Finally, Section 5 situates RTGEN with respect to related work on surface realisation optimisation.

SemXTag

The grammar (SEMXTAG) used by GENI and RTGEN is a Feature-Based Lexicalised Tree Adjoining Grammar (FTAG) augmented with a unification-based semantics as described in [START_REF] Gardent | Semantic construction in FTAG[END_REF]. We briefly introduce each of these components and describe the grammar coverage. We then show how this FTAG can be converted to an RTG describing its derivation trees.

FTAG.

A Feature-based TAG [START_REF] Vijay-Shanker | Feature Structures Based Tree Adjoining Grammars[END_REF] consists of a set of (auxiliary or initial) elementary trees and of two tree-composition operations: substitution and adjunction. Initial trees are trees whose leaves are labeled with substitution nodes (marked with a downarrow) or terminal categories. Auxiliary trees are distinguished by a foot node (marked with a star) whose category must be the same as that of the root node. Substitution inserts a tree onto a substitution node of some other tree while adjunction inserts an auxiliary tree into a tree. In an FTAG, the tree nodes are furthermore decorated with two feature structures (called top and bottom) which are unified during derivation as follows. On substitution, the top of the substitution node is unified with the top of the root node of the tree being substituted in. On adjunction, the top of the root of the auxiliary tree is unified with the top of the node where adjunction takes place; and the bottom features of the foot node are unified with the bottom features of this node. At the end of a derivation, the top and bottom of all nodes in the derived tree are unified. Finally, each sentence derivation in an FTAG is associated with both a derived tree representing the phrase structure of the sentence and a derivation tree recording how the corresponding elementary trees were combined to form the derived tree. Nodes in a derivation tree are labelled with the name of a TAG elementary tree. Edges are labelled with a description of the operation used to combine the TAG trees whose names label the edge vertices.

FTAG with semantics.

To associate semantic representations with natural language expressions, the FTAG is modified as proposed in [START_REF] Gardent | Semantic construction in FTAG[END_REF]. ⇒ name(j,john), run(a,j), often(a) Figure 1: Flat Semantics for "John often runs" Each elementary tree is associated with a flat semantic representation. For instance, in Figure 1,1 the trees for John, runs and often are associated with the semantics name(j,john), run(a,s) and often(x) respectively. Importantly, the arguments of a semantic functor are represented by unification variables which occur both in the semantic representation of this functor and on some nodes of the associated syntactic tree. For instance in Figure 1, the semantic index s occurring in the semantic representation of runs also occurs on the subject substitution node of the associated elementary tree. The value of semantic arguments is determined by the unifications resulting from adjunction and substitution. For instance, the semantic index s in the tree for runs is unified during substitution with the semantic index labelling the root node of the tree for John. As a result, the semantics of John often runs is {name(j,john),run(a,j),often(a)}.

SemXTAG.

SEMXTAG is an FTAG for English augmented with a unification based compositional semantics of the type described above. Its syntactic coverage approaches that of XTAG, the FTAG developed for English by the XTAG group (The XTAG Research Group, 2001). Like this grammar, it contains around 1300 elementary trees and covers auxiliaries, copula, raising and small clause constructions, topicalization, relative clauses, infinitives, gerunds, passives, adjuncts, ditransitives and datives, ergatives, it-clefts, wh-clefts, PRO constructions, noun-noun modification, extraposition, sentential adjuncts, imperatives and resultatives.

Converting SemXTAG to RTG

As shown in [START_REF] Schmitz | Feature unification in TAG derivation trees[END_REF], an FTAG can be converted to a Regular Tree Grammar describing its derivation tree. In this section, we briefly sketch this conversion process. For a more precise description of this FTAG to RTG conversion, the reader is referred to [START_REF] Schmitz | Feature unification in TAG derivation trees[END_REF].

In the FTAG-to-RTG conversion, each SEMX-TAG elementary tree is converted to a rule that models its contribution to a TAG derivation tree. A TAG derivation involves the selection of an initial tree, which has some nodes requiring substitution and some permitting adjunction. Let us think of the potential adjunction sites as requiring, rather than permitting, adjunction, but such that the requirement can be satisfied by 'null' adjunction. Inserting another tree into this initial tree satisfies one of the substitution or adjunction requirements, but introduces some new requirements into the resulting tree, in the form of its own substitution nodes and adjunction sites.

Thus, intuitively, the RTG representation of a SEMXTAG elementary tree is a rule that rewrites the satisfied requirement as a local tree whose root is a unique identifier of the tree and whose leaves are the introduced requirements. A requirement of a substitution or adjunction of a tree of root category X is written as X S or X A , respectively. Here, for example, is the translation to RTG of the FTAG tree (minus semantics) for run in Figure 1, using the word anchoring the tree as its identifier (the upperscripts abbreviates features structures: b/t refers to the bottom/top feature structure and the upper case letters to the semantic index value, [idx : X] is abbreviated to X):

S [t:T ] S → runs(S [t:T,b:C] A N P [t:S] S V P [t:C,b:B] A V [t:B,b:A] A )
The semantics of the SemXTAG tree are carried over as-is to the corresponding RTG rule. Further, the feature structures labelling the nodes of the SemXTAG tree are converted into the RTG rules so as to correctly interact with substitution and adjunction (see [START_REF] Schmitz | Feature unification in TAG derivation trees[END_REF] for more details on this part of the conversion process).

To account for the optionality of adjunction, there are additional rules allowing any adjunction requirement to be rewritten as the symbol ǫ, a terminal symbol of the RTG.

The terminal symbols of the RTG are thus the tree identifiers and the symbol ǫ, and its nonterminals are X S and X A for each terminal or non-terminal X of SemXTAG.

TAG-based surface realisation

We now present RTGEN and describe GENI, and compare the optimisations they propose to deal with the task complexity.

GENI and RTGEN are similar on several points. They use the same grammar, namely SEMXTAG (cf. Section 2). Further, they both pipeline three main steps. First, lexical selection selects from the grammar those elementary trees whose semantics subsumes part of the input semantics. Second, the tree combining phase systematically tries to combine trees using substitution and adjunction. Third, the retrieval phase extracts the yields of the complete derived trees, thereby producing the generated sentence(s).

GENI and RTGEN differ however with respect to the trees they are working with (derived trees in GENI vs derivation trees in RTGEN). They also differ in how tree combination is handled. We now describe these differences in more detail and explain how each approach address the complexity issue.

GenI

The tree combining phase in GENI falls into two main steps namely, filtering and tree combining.

Filtering. The so-called polarity filtering step aims to reduce the initial search space. It eliminates from the initial search space all those sets of TAG elementary trees which cover the input semantics but cannot possibly lead to a valid derived tree. In specific, this filtering removes all tree sets covering the input semantics such that either the category of a substitution node cannot be canceled out by that of the root node of a different tree; or a root node fails to have a matching substitution site. Importantly, this filtering relies solely on categorial information -feature information is not used. Furthermore, auxiliary trees have no impact on filtering since they provide and require the same category thereby being "polarity neutral elements".

Tree combining. The tree combining algorithm used after filtering has taken place, is a bottom-up tabular algorithm [START_REF] Kay | Chart generation[END_REF] optimised for TAGs. This step, unlike the first, uses all the features present in the grammar. To handle intersective modifiers, the delayed modifiers insertion strategy from [START_REF] Carroll | An efficient chart generator for (semi-)lexicalist grammars[END_REF] is adapted to TAG as follows. First, all possible derived trees are obtained using only substitution. Next, adjunction is applied. Although the number of intermediate structures generated is still 2 n for n modifiers, this strategy has the effect of blocking these 2 n structures from multiplying out with other structures in the chart.

RTGen

RTGen synthesises different techniques that have been observed in the past to improve surface realisation runtimes. We first describe these techniques i.e., the main features of RTGEN. We then present three alternative ways of implementing RTGEN which will be compared in the evaluation.

RTGen's main features

A main feature of RTGEN is that it focuses on building derivation rather than derived trees. More specifically, the first two steps of the surface realisation process (lexical selection, tree combining) manipulate RTG rules describing the contribution of the SEMXTAG elementary trees to the derivation tree rather than the elementary tree themselves. The derived trees needed to produce actual sentences are only produced in the last phase i.e., the retrieval phase.

This strategy is inspired from a similar approach described in [START_REF] Koller | Generation as dependency parsing[END_REF] which was shown to be competitive with state of the art realisers on a small sample of example input chosen for their inherent complexity. [START_REF] Koller | Generation as dependency parsing[END_REF]'s approach combines trees using a constraint based dependency parser rather than an Earley algorithm so that it is difficult to assess how much of the efficiency is due to the parser and how much to the grammar conversion. Intuitively however, the motivation underlying the construction of a derivation rather than a derived tree is that efficiency might be increased because the context free derivation trees (i) are simpler than the mildly context sensitive trees generated by an FTAG and (ii) permit drawing on efficient parsing and surface realisation al-gorithms designed for such grammars.

Second, RTGEN makes use of the now standard semantic criteria proposed in [START_REF] Kay | Chart generation[END_REF][START_REF] Carroll | An efficient chart generator for (semi-)lexicalist grammars[END_REF] to reduce the number of combinations tried out by the realiser. On the one hand, two constituents are combined by the algorithm's inference rules only if they cover disjoint parts of the input semantics. On the other hand, the semantic indices present in both the input formula and the lexically retrieved RTG trees are used to prevent the generation of intermediate structures that are not compatible with the input semantics. For instance, given the input formula for "John likes Mary", semantic indices will block the generation of "likes John" because this constituent requires that the constituent for "John" fills the patient slot of "likes" whereas the input semantics requires that it fills the agent slot. In addition, chart items in RTGEN are indexed by semantic indices to efficiently select chart items for combination.

Third, RTGEN implements a standard Earley algorithm complete with sharing and packing. Sharing allows for intermediate structures that are common to several derivations to be represented only once -in addition to not being recomputed each time. Packing means that partial derivation trees with identical semantic coverage and similar combinatorics (same number and type of substitution and adjunction requirements) are grouped together and that only one representative of such groups is stored in the chart. In this way, intermediate structures covering the same set of intersective modifiers in a different order are only represented once and the negative impact of intersective modifiers is lessened (cf. [START_REF] Brew | Letting the cat out of the bag: generation for shake-and-bake mt[END_REF]). . As [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF] have shown, packing and sharing are important factors in improving efficiency. In particular, they show that an algorithm with packing and sharing clearly outtperforms the same algorithm without packing and sharing giving an up to 50 times speed-up for inputs with large numbers of realizations.

Three ways to implement RTGen

Depending on how much linguistic information (i.e. feature constraints from the feature structures) is preserved in the RTG rules, several RT-GEN configurations can be tried out which each reflect a different division of labour between constraint solving and structure building. To experiment with these several configurations, we exploit the fact that the FTAG-to-RTG conversion procedure developed by Sylvain Schmitz permits specifying which features should be preserved by the conversion.

RTGen-all. In this configuration, all the feature structure information present in the SEMXTAG elementary trees is carried over to the RTG rules. As a result, tree combining and constraint solving proceed simultaneously and the generated parse forest contains the derivation trees of all the output sentences.

RTGen-level0. In the RTGen-level0 configuration, only the syntactic category and the semantic features are preserved by the conversion. As a result, the grammar information used by the (derivation) tree building phase is comparable to that used by GENI filtering step. In both cases, the aim is to detect those sets of elementary trees which cover the input semantics and such that all syntactic requirements are satisfied while no syntactic resource is left out. A further step is additionally needed to produce only those trees which can be built from these tree sets when applying the constraints imposed by other features. In GENI, this additional step is carried out by the tree combining phase, in RTGEN, it is realised by the extraction phase i.e., the phase that constructs the derived trees from the derivation trees produced by the tree combining phase.

RTGen-selective. Contrary to parsing, surface realisation only accesses the morphological lexicon last i.e., after sentence trees are built. Because throughout the tree combining phase, lemmas are handled rather than forms, much of the morpho-syntactic feature information which is necessary to block the construction of ill-formed constituents is simply not available. It is therefore meaningful to only include in the tree combining phase those features whose value is available at tree combining time. In a third experiment, we automatically identified those features from the observed feature structure unification failures during runs of the realisation algorithm. We then use only these features (in combination with the semantic features and with categorial information) during tree combining.

Evaluation

To evaluate the impact of the different optimisation techniques discussed in the previous section, we use two benchmarks generated automatically from SEMXTAG [START_REF] Gottesman | Generating examples[END_REF].

The first benchmark (MODIFIERS) was designed to test the realisers on cases involving intersective modifiers. It includes 1 789 input formulae with a varying number (from 0 to 4 modifications), type (N and VP modifications) and distribution of intersective modifiers (n modifiers distributed differently over the predicate argument structures). For instance, the formula in (1) involves 2 N and 1 VP modification. Further, it combines lexical ambiguity with modification complexities, i.e. for the snore modifier the grammar provides 10 trees. The second benchmark (COMPLEXITY) was designed to test overall performance on cases of differing complexity (input formulae of increasing length, involving verbs with a various number and types of arguments and with a varying number of and types of modifiers). It contains 890 distinct cases. A sample formula extracted from this benchmark is shown in (2), which includes one modification and to different verb types.

(2) h1 ≥ l4, l0 : want(e, h1), l1 To evaluate GENI and the various configurations of RTGEN (RTGEN-all, RTGEN-level0, RTGENselective), we ran the 4 algorithms in batch mode on the two benchmarks and collected the following data for each test case:

• Packed chart size : the number of chart items built. This feature is only aplicable to RTGen as GENI does not implement packing.

• Unpacked chart size : the number of intermediate and final structures available after unpacking (or at the end of the tree combining process in the case of GENI).

• Initial Search Space (ISS) : the number of all possible combinations of elementary trees to be explored given the result of lexical selection on the input semantics. That is, the product of the number of FTAG elementary trees selected by each literal in the input semantics.

• Generation forest (GF) : the number of derivation trees covering the input semantics.

The graph in Figure 2 shows the differences between the different strategies with respect to the unpacked chart size metric.

A first observation is that RTGEN-all outperforms GENI in terms of intermediate structures built . In other words, the Earley sharing and packing strategy is more effective in reducing the number of constituents built than the filtering and substitution-before-adjunction optimisations used by GENI. In fact, even when no feature information is used at all (RTGEN-level0 plot), for more complex test cases, packing and sharing is more effective in reducing the chart size than filtering and operation ordering.

Another interesting observation is that RTGENall and RTGEN-selective have the same impact on chart size (their plots coincide). This is unsurprising since the features used by RTGEN-selective have been selected based on their ability to block constituent combination. The features used in RTGEN-selective mode are wh, xp, assign-comp, mode, definite, inv, assign-case, rel-clause, extracted and phon, in addition to the categorial and semantic information. In other words, using all 42 SEMXTAG grammar features has the same impact on search space pruning as using only a small subset of them. As explained in the previous section, this is probably due to the fact that contrary to parsing, surface realisation only accesses the morphological lexicon after tree combining takes place. Another possibility is that the grammar is under constrained and that feature values are missing thereby inducing overgeneration.

Zooming in on cases involving three modifiers, we show in Table 1 the average results for various efficiency metrics 2 . This provides a more detail view of the performance of the differences among the three RTGEN variants. This data shows that running RTGEN with no feature information leads not only to an increased chart size but also to runtimes that are higher in average than for full surface realisation i.e., realisation using the full grammar complete with con-2 The two realisers being implemented in different programming languages (RTGEN uses Prolog and GENI Haskell), runtimes comparisons are not necessarily very meaningful. Additionally, GENI does not provide time statistics. After adding this functionality to GENI, we found that overall GENI is faster on simple cases but slower on more complex ones. We are currently working on optimising RT-GEN prolog implementation before carrying out a full scale runtime comparison. straints.

Interestingly, it also shows that the selective mode (RTGEN-selective) permits improving runtimes while achieving almost perfect disambiguation in that the average number of derivation trees (GF) produced is close to that produced when using all features. The differences between the two generation forests stems from packing. Using only a subset of features favors packing, thereby reducing the number of chart items built, but introduces over-generation.

Graph 3 and Table 2 confirm the results obtained using the MODIFIERS benchmark on a testset (COMPLEXITY) where input complexity varies not only with respect to modification but also with respect to the length of the input and to the degree of lexical ambiguity. Typically, in a TAG, one word or one semantic literal may be associated either with one tree or with up to several hundred trees (e.g., ditransitive verbs and verbs with several subcategorisation types). By varying the type and the number of verbs selected by the semantic literals contained in the input semantics, the COMPLEXITY benchmark provides a more extensive way to test performance on cases of varying complexity. 1.

Related work

Much work has already been done on optimising surface realisation. Because surface realisation often draws on parsing techniques, work on parsing optimisation is also relevant. In this section, we briefly relate our proposal to another grammar converting approach [START_REF] Koller | Generation as dependency parsing[END_REF]; to another chart based approach [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF]; and to approaches based on statistical pruning [START_REF] White | Reining in CCG chart realization[END_REF][START_REF] Bangalore | Using TAGs, a tree model and a language model for generation[END_REF].

Optimising surface realisation

Encoding into another grammatical formalism.

As already mentioned, the RTGEN approach is closely related to the work of [START_REF] Koller | Generation as dependency parsing[END_REF] where the XTAG grammar is converted to a dependency grammar capturing its derivation trees. This conversion enables the use of a constraint based dependency parser, a parser which was specifically developed for the efficient parsing of free word order languages and is shown to support an efficient handling of both lexical and modifier attachment ambiguity.

Our proposal differs from this approach in three main ways. First, contrary to XTAG, SEMX-TAG integrates a full-fledged, unification based compositional semantics thereby allowing for a principled coupling between semantic representations and natural language expressions. Second, the grammar conversion and the featurebased RTGs used by RTGEN accurately translates the full range of unification mechanisms employed in FTAG wheras the conversion described by [START_REF] Koller | Generation as dependency parsing[END_REF] does not take into account feature structure information. Third, the RTGEN approach was extensively tested on a large benchmark using 3 different configurations whilst [START_REF] Koller | Generation as dependency parsing[END_REF] results are re-stricted to a few hand constructed example inputs.

Chart generation algorithm optimisations. [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF] provides an extensive and detailed study of how various techniques used to optimise parsing and surface realisation impact the efficiency of a surface realiser based on a large coverage Head-Driven Phrase Structure grammar.

Because they use different grammars, grammar formalisms and different benchmarks, it is difficult to compare the RTGEN and the HPSG approach. However, one point is put forward by [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF] which it would be interesting to integrate in RTGEN [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF] show that for packing to be efficient, it is important that equivalence be checked through subsumption, not through equality. RT-GEN also implements a packing mechanism with subsumption check, i.e. different ways of covering the same subset of the input semantics are grouped together and represented in the chart by the most general one. One difference however it that RTGEN will pack analyses together as long as the new ones are more specific cases. It will not go backwards to recalculate the packing made so far if a more general item is found [START_REF] Stefan | Parser engineering and performance profiling[END_REF]. In this case the algorithm will pack them under two different groups.

Statistical pruning. Various probabilistic techniques have been proposed in surface realisation to improve e.g., lexical selection, the handling of intersective modifiers or ranking. For instance, [START_REF] Bangalore | Using TAGs, a tree model and a language model for generation[END_REF] uses a tree model to produce a single most probable lexical selection while in White's system, the best paraphrase is determined on the basis of n-gram scores. Further, to address the fact that there are n! ways to combine any n modifiers with a single constituent, [START_REF] White | Reining in CCG chart realization[END_REF] proposes to use a language model to prune the chart of identical edges representing different modifier permutations, e.g., to choose between fierce black cat and black fierce cat. Similarly, [START_REF] Bangalore | Using TAGs, a tree model and a language model for generation[END_REF] assumes a single derivation tree that encodes a word lattice (a {fierce black, black fierce} cat), and uses statistical knowledge to select the best linearisation. Our approach differs from these approaches in that lexical selection is not filtered, intersective modifiers are handled by the grammar (constraints on the respective order of adjectives) and the chart packing strategy (for optimisation), and ranking is not performed. We are currently exploring the use of Optimality Theory for ranking.

Conclusion

We presented RTGEN, a novel surface realiser for FTAG grammars which builds on the observation that an FTAG can be translated to a regular tree grammar describing its derivation trees. Using automatically constructed benchmarks, we compared the performance of this realiser with that of GENI, another state of the art realiser for FTAG. We showed that RTGEN outperforms GENI in terms of space i.e. that the Earley sharing and packing strategy is more effective in reducing the number of constituents built than the filtering and substitution-before-adjunction optimisations used by GENI. Moreover, we investigated three ways of interleaving phrase structure and feature structure constraints and showed that, given a naive constraint solving approach, the interleaving approach with selective features seems to provide the best space/runtimes compromise.

Future work will concentrate on further investigating the interplay in surface realisation between phrase structure and feature structure constraints. In particular, [START_REF] Maxwell | The interface between phrasal and functional constraints[END_REF] shows that a more sophisticated approach to constraint solving and to its interaction with chart processing renders the non interleaved approach more effective than the interleaved one. We plan to examine whether this observation applies to SEMXTAG and RTGEN. Further, we intend to integrate Optimality Theory constraints in RTGEN so as support ranking of multiple outputs. Finally, we want to further optimise RTGEN on intersective modifiers using one the methods mentioned in Section 5.

( 1 )

 1 l1 : ∃(x1, hr, hs), hr ≥ l2, hs ≥ l3, l2 : man(x1), l2 : snoring(e1, x1), l2 : big(x1), l3 : sleep(e2, x1), l4 : soundly(e2) (A snoring big man sleeps soundly)

Figure 2 :

 2 Figure 2: Performance of realisation approaches on the MODIFIERS benchmark, average unpacked chart size as a function of the number of modifiers.

Figure 3 :

 3 Figure 3: Performance of realisation approaches on the COMPLEXITY benchmark, average unpacked chart size as a function of the ISS complexity.

Table 2 :

 2 Average results on 335 cases with 10000 < ISS ≤ 100000, from the COMPLEXITY benchmark. The columns show the same performance metrics as in Table

	strategy	GF	chart	unpacked-chart	seconds
	RTGen-all	14.77	693.39	2,427.82	0.81
	RTGen-level0	162.02	2,114.16	6,954.84	1.09
	RTGen-selective	15.31	692.9	2,427.2	0.36

C x /Cx abbreviate a node with category C and a top/bottom feature structure including the feature-value pair { index : x}.

Acknowledgements

The research presented in this paper was partially supported by the European Fund for Regional Development within the framework of the INTER-REG IV A Allegro Project.


Rémi Gribonval

Should penalized least squares regression be interpreted as Maximum A Posteriori estimation?

Penalized least squares regression is often used for signal denoising and inverse problems, and is commonly interpreted in a Bayesian framework as a Maximum A Posteriori (MAP) estimator, the penalty function being the negative logarithm of the prior. For example, the widely used quadratic program (with an ℓ 1 penalty) associated to the LASSO / Basis Pursuit Denoising is very often considered as MAP estimation under a Laplacian prior in the context of additive white Gaussian noise (AWGN) reduction. This paper highlights the fact that, while this is one possible Bayesian interpretation, there can be other equally acceptable Bayesian interpretations. Therefore, solving a penalized least squares regression problem with penalty φ(x) need not be interpreted as assuming a prior C • exp(-φ(x)) and using the MAP estimator. In particular, it is shown that for any prior P X , the minimum mean square error (MMSE) estimator is the solution of a penalized least square problem with some penalty φ(x), which can be interpreted as the MAP estimator with the prior C • exp(-φ(x)). Vice-versa, for certain penalties φ(x), the solution of the penalized least squares problem is indeed the MMSE estimator, with a certain prior P X . In general dP X (x) = C • exp(-φ(x))dx.

I. INTRODUCTION

Consider the problem of estimating an unknown signal x ∈ R n from a noisy observation y = x + b, also known as denoising. Given an arbitrary noisy observation y the goal is to estimate the noiseless signal x: in practice, designing a denoising scheme amounts to choosing a function ψ : R n → R n which provides estimates of the form x = ψ(y). However, unless one specifies further what is meant by "noise" and "signal", denoising is a completely ill-posed problem since any pair x, b such that y = x + b can be replaced by a pair x ′ , b ′ where x ′ = x + z, b ′ = b -z. Practical denoising schemes hence have to rely on various types of prior information on x and b to design an appropriate denoising function ψ.

A. Bayesian estimation

A standard statistical approach to the denoising problem consists in assuming that x and b are drawn independently at random from known prior probability distributions P X and P B . Under this model, given a cost function C(x, x) that measures the quality of an estimator x in comparison to the true quantity to estimate x, the Bayes estimator is defined as an estimator ψ with minimum expected cost:

arg min ψ E {C(ψ(X + B), X)} .
For a quadratic cost function C(x, x) := xx 2 2 the Bayes estimator is the minimum mean square error (MMSE) estimator [START_REF] Kay | Fundamentals of Statistical Signal Processing : Estimation Theory[END_REF], also called conditional mean, posterior mean, or conditional expectation: ψ MMSE (y) := E(X|Y = y).

(I.1)

Rémi Gribonval is with INRIA, Centre Inria Rennes -Bretagne Atlantique, Campus de Beaulieu, F-35042 Rennes Cedex, Rennes, France. Phone: +33 2 99 84 25 06. Fax: +33 2 99 84 71 71. Email: remi.gribonval@inria.fr. Rémi Gribonval is a member of the METISS project-team at IRISA, Rennes, France. This work was supported in part by the European Union through the project SMALL (Sparse Models, Algorithms and Learning for Large-Scale data). The project SMALL acknowledges the financial support of the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under FET-Open grant number: 225913.

NB: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

Even though this estimator is "optimal" in the above defined sense, its computation involves a high-dimensional integral and cannot generally be done explicitly. In practice, Monte-Carlo simulations can be used to approximate the integral.

Often more amenable to efficient numerical optimization is the popular Maximum A Posteriori (MAP) criterion, which is the Bayes estimator associated to the 0 -1 cost function (C(x, x) = 1, when x = x; C(x, x) = 0, when x = x). Exploiting Bayes rule and assuming that both the noise and the unknown noiseless signal have probability density functions (pdf), p X and p B (b), the MAP estimator reads:

ψ MAP (y) := arg max x∈R n p(x|y) = arg max x∈R n p(y|x)p(x) = arg min x∈R n {-log p B (y -x) -log p X (x)} . For white Gaussian noise b we have p B (b) ∝ exp(-b 2 2 /2), where b 2 2 = n i=1 b 2 i and the notation f (x) ∝ g(x) means f (x) = C • g(x)
for all x, with C = 0 some constant independent of x. Hence the MAP estimator under the prior p X (x) can be expressed as

ψ MAP (y) = arg min x∈R n 1 2 y -x 2 2 + [-log p X (x)]. (I.2)

B. Regularization

Optimization problems of the type (I.2) have also been often considered in signal processing without explicit reference to probabilities or priors, under the generic form arg min

x∈R n 1 2 y -x 2 2 + φ(x). (I.3)
The deterministic objective is to achieve a tradeoff between the data-fidelity term yx 2 2 and the penalty term φ(x), which promotes solutions with certain properties. In particular, when the function φ is non-smooth at the origin, such as φ(x) = x p p := n i=1 |x i | p , 0 < p ≤ 1, the optimum of the criterion (I.3) is known to have few nonzero entries. Regularization with such penalty functions is at the basis of shrinkage techniques for signal denoising (see e.g. [START_REF] Donoho | Denoising by soft-thresholding[END_REF] with p = 1, or [START_REF] Moulin | Analysis of multiresolution image denoising schemes using generalized Gaussian and complexity priors[END_REF] with 0 < p ≤ 1). More recently, these approaches have become a very popular means of promoting sparse solutions to under-determined or ill-conditioned linear inverse problems y = Ax + b, and are now a key tool for compressed sensing [START_REF] Donoho | Compressed sensing[END_REF].

C. Plurality of Bayesian interpretations of regularization

Given the identity of the optimization problems (I.2) and (I.3) when φ(x) = φ MAP (x) :=log p X (x), the regularization problem (I.3) is often interpreted1 as "solving the MAP under the prior p X (x) = exp(-φ(x))/C φ ", where

C φ := R n exp(-φ(x))dx. (I.4)
In particular, when φ(x) = x 1 , a possible interpretation of (I.3) is MAP denoising under a Laplacian prior on x and white Gaussian noise.

The main objective of this paper is to highlight the fact that while one Bayesian interpretation of the penalized least-squares estimator (I.3) with penalty function φ(x) is the MAP estimator ψ MAP (y) with prior p X (x) = exp(-φ(x))/C φ , there can be other admissible Bayesian interpretations.

We focus on white Gaussian denoising and show that for any prior P X and any noisy observation y ∈ R n , the MMSE estimate ψ MMSE (y) under the prior P X is the solution of a penalized least-squares problem (I.3) with an appropriate penalty function φ MMSE (x). Thus, the problem (I.3) with penalty φ MMSE (x) can equally be interpreted as: a) the MAP estimator ψMAP (y) with a prior associated to the pdf pX (x) = exp(-φ MMSE (x))/C φMMSE ; or b) the MMSE estimator with prior P X . In general dP X (x) = pX (x)dx.

II. MAIN RESULTS

From now on we focus on Gaussian denoising: B ∈ R n is a centered normal Gaussian variable with law P B = N (0, I n ) and pdf p B (b) ∝ exp(-b 2 2 /2). We let X ∈ R n be a random variable independent of B, with law P X . The probability distribution of the noisy observation Y = X + B has a pdf

p Y (y) := p B ⋆ P X (y) = R n p B (y -x)dP X (x) (II.1)
which is sometimes refered to as the evidence of the observation y. When P X is associated to a pdf p X (x), the evidence is given by a standard convolution between pdfs p Y = p B ⋆ p X . Even when

P X is not associated to a pdf, p Y infinitely differentiable, i.e., p Y ∈ C ∞ (R n ).
In this setting, using techniques going back to Stein's unbiased risk estimator [START_REF] Stein | Estimation of the mean of a multivariate normal distribution[END_REF], [START_REF] Blu | The SURE-LET approach to image denoising[END_REF], one can express the MMSE estimator as [START_REF] Raphan | Learning to be Bayesian without supervision[END_REF]

ψ MMSE (y) = y + 1 p Y (y) ∂ ∂y i p Y (y) n i=1 = y + ∇ log p Y (y). (II.2) All vectors u ∈ R n , such as the gradient ∇ log p Y (y) ∈ R n , are in column form. Their transpose u T is in row form.
Next we study whether ψ MMSE can also be written as the optimum of an optimization problem of the MAP type (I.3), with an appropriate choice of φ. Namely, we investigate when ψ MMSE can be identified with the proximity operator [START_REF] Combettes | Proximal thresholding algorithm for minimization over orthonormal bases[END_REF] of a function φ, where we recall the definition prox φ (y) := arg min

z∈R n 1 2 y -z 2 2 + φ(z) . (II.3)
Rereading Equation (I.2) the MAP estimator (with prior p X (x)) can be written as ψ MAP = prox φMAP where

φ MAP (x) := -log p X (x). (II.4)
For smooth φ we have the implicit characterization [START_REF] Combettes | Proximal thresholding algorithm for minimization over orthonormal bases[END_REF] prox φ (y) := y -∇φ[prox φ (y)], ∀y ∈ R n .

(II.5)

Comparing (II.2) with (II.5), we see that if

ψ MMSE = prox φ then ∇φ[ψ MMSE (y)] = -∇ log p Y (y), ∀y ∈ R n . (II.6)
Indeed, the relation (II.6) characterizes all functions φ such that ψ MMSE = prox φ , thanks to the following lemma.

Lemma II.1. Let X P X , B ∼ P B N (0, I) be independent random variables in R n . Assume that there is no pair v ∈ R n , c ∈ R such that X, v = c with probability one. Then the MMSE estimator y → ψ MMSE (y) has the following properties:

1) it is one-to-one from R n onto Imψ MMSE ⊂ R n : for any pair y, y ′ ∈ R n , if ψ MMSE (y) = ψ MMSE (y ′ ) then y = y ′ . 2) it is C ∞ (R n ); so is its inverse ψ -1 MMSE : Imψ MMSE → R n . 3) when n = 1 we further have that ψ MMSE is increasing.
The proof is in Appendix A. Note that the probability distribution P X in Lemma II.1 can be almost arbitrary, provided that there is no lower-dimensional affine space of R n to which X belongs almost surely. In particular, P X need not be separable. In light of this lemma, (II.6) is equivalent to

∇φ(z) = -∇ log p Y [ψ -1 MMSE (z)], ∀z ∈ Imψ MMSE .
As shown by our main theorem (the proof is in Appendix B), this equation is satisfied by the function φ MMSE : R n → R ∪ {+∞} defined as:

φ MMSE (x) :=    -1 2 ψ -1 MMSE (x) -x 2 2 -log p Y [ψ -1 MMSE (x)]; for x ∈ Imψ MMSE ; +∞, for x / ∈ Imψ MMSE .
(II.7)

Theorem II.2. Let X P X , B ∼ P B = N (0, I) be independent random variables in R n . Assume that there is no lower-dimensional affine space of R n to which X belongs almost surely. Then prox φMMSE = ψ MMSE and:

1) the function φ MMSE is C ∞ on its domain Imψ MMSE ;
2) for every y ∈ R n , the vector ψ MMSE (y) = prox φMMSE (y) is the unique global minimum, as well as the unique stationary point of the function x → 1 2 yx 2 + φ MMSE (x); 3) for every y ∈ R n , we have φ MMSE (y) ≥log p Y (y); 4) we have

C φMMSE = R n exp(-φ MMSE (x))dx < ∞.
Therefore, the MMSE estimator with prior P X and white Gaussian noise is also the MAP estimator with the prior which pdf is pX (x) = exp(-φ MMSE (x))/C φMMSE .

Remark II.1. Note that ψ(y) is not only the unique global minimum of x → 1 2 yx 2 + φ MMSE (x): it is also its unique stationary point. This is much stronger: this means that descent algorithms used to solve the optimization problem (I.3) with φ = φ MMSE cannot be trapped in a spurious local minimum.

Remark II.2. When X belongs with probability one to a lower-dimensional affine space V ⊂ R n , we have Imψ MMSE ⊂ V . Letting V be the smallest such affine space, the restriction of ψ MMSE to V still has a well defined C ∞ inverse ψ -1 MMSE : Imψ MMSE → V which can be used to define φ MMSE as in (II.7) and to generalize Theorem II.2 to an arbitrary prior P X .

III. WORKED EXAMPLE

Let us illustrate Theorem II.2 with a simple example: we consider the one-dimensional (n = 1) mixture of two Gaussians prior on the unknown noiseless data x,

p X (x) := p • e -x 2 2σ 2 0 √ 2πσ 2 0 + (1 -p) • e -x 2 2σ 2 1 √ 2πσ 2 1 , (III.1)
where p ∈ (0, 1) and 0 < σ 0 < σ 1 . The evidence of the observed noisy data Y = X + B with B ∼ N (0, 1) is then

p Y (y) = p • e - y 2 2(σ 2 0 +1) √ 2π(σ 2 0 +1) + (1 -p) • e - y 2 2(σ 2 1 +1) √ 2π(σ 2 1 +1) , hence p ′ Y (y) = -y • p • e - y 2 2(σ 2 0 +1) √ 2π(σ 2 0 +1) 3 + (1 -p) • e - y 2 2(σ 2 1 +1) √ 2π(σ 2 1 +1) 3 .
By straightforward computations, we obtain

ψ MMSE (y) = y • σ 2 0 σ 2 0 +1 + σ 2 1 σ 2 1 +1 • ae by 2 1 + ae by 2 with a := 1 -p p σ 2 0 + 1 σ 2 1 + 1 , b = 1 σ 2 0 + 1 - 1 σ 2 1 + 1 ∈ (0, 1).
The limiting case σ 2 0 → 0 corresponds to the so called Bernoulli-Gaussian prior (see, e.g., [START_REF] Zayyani | Bayesian pursuit algorithm for sparse representation[END_REF]): the value x = 0 is drawn with probability p > 0, hence vectors with i.i.d. entries distributed according to p X are typically sparse. The MMSE estimator takes a simplified form [START_REF] Turek | On MMSE and MAP denoising under sparse representation modeling over a unitary dictionary[END_REF] when σ 2 0 → 0

ψ MMSE (y) = y • σ 2 1 σ 2 1 + 1 • ae by 2 1 + ae by 2 .
We illustrate in Figure 1 the case p = 0.9, σ 2 0 → 0, σ 2 1 = 10. Figure 1(a) shows ψ MMSE (solid line) and its inverse ψ -1 MMSE (dashed line). The latter does not seem to have an analytic expression. Figure 1(b) shows φ MAP (x) = -log p X (x) (dotted line),log p Y (x) (dashed line) and the penalty function φ MMSE (x) (solid line). While the penalty function φ MMSE (x) does not seem to admit an analytic expression, one can obtain an analytic expression for φ MMSE [ψ MMSE (y)] = -1 2 yψ MMSE (y) 2 2log p Y (y). The explicit analytic expressionwhich is long and rather uninteresting-was used to plot φ MMSE (x) on Figure 1(a) using the parameterized curve MMSE (y) (dashed line),, in the Bernoulli-Gaussian case, p = 0.9, σ 2 0 → 0, σ 2 1 = 10. Right: MAP penalty φMAP(x) = -log pX(x) (dotted line), negative log-evidence (-log pY (x)) (dashed line) and MMSE penalty φMMSE(x) (solid line).

y → (ψ MMSE (y), φ MMSE [ψ MMSE (y)]). Observing on Figure 1(b) the plot of φ MMSE (x) for the above Bernoulli-Gaussian prior yields a number of observations. 1) For small x, the penalty φ MMSE (x) is approximately shaped as the absolute value: φ MMSE (x) ≈ c|x| for some constant c. This is tempered by the fact that φ MMSE (x) is C ∞ , thus, unlike |x|, it must be smooth at zero. 2) The penalty φ MMSE (x) is unimodal (it is decreasing until its global minimum, then increasing) but it is not convex. The second observation could seem surprising given that Theorem II.2 guarantees the uniqueness of the global minimizer / stationary point of x → 1 2 yx 2 + φ MMSE (x). However, this property is not a characteristic of convex penalties. As a matter of fact, a function f : R → R (i.e., in the case n = 1) can be written f = prox g with g a proper lower semi-continuous convex function from R to R ∪ {+∞} if, and only if, the function f is increasing and non-expansive [2, Proposition 2.4]:

Definition III.1. A function f : R → R is non-expansive if |f (y ′ ) -f (y)| ≤ |y ′ -y| for all y, y ′ . When f is differentiable, it is non-expansive if and only if |f ′ (y)| ≤ 1 for all y.
By Lemma II.1, in dimension n = 1, the MMSE estimator ψ MMSE is increasing for any prior P X . However, for certain priors P X , it can indeed be proved to be expansive (see the proof in Appendix C): Proposition III.2. Assume that X has a symmetric pdf [∀x ∈ R, p X (-x) = p X (x)] and that there exists ε > 0 such that p X (x) = 0 for all x with |x| < 1 + ε. Then the penalty φ MMSE cannot be convex.

IV. DISCUSSION

Theorem II.2 shows that for general priors P X we have ψ MMSE = prox φMMSE . Similarly, when X has a pdf, we have ψ MAP = prox φMAP , where for a given prior the MAP penalty φ MAP (x) has the simple expression (II.4) while the MMSE penalty φ MMSE (x) has the much more intricate definition (II.7).

For Gaussian priors P X = N (0, Σ), the MMSE estimator is the Wiener filter, which is also the MAP and the minimum mean square linear estimator [START_REF] Kay | Fundamentals of Statistical Signal Processing : Estimation Theory[END_REF], so φ MMSE = φ MAP (up to a constant additive term).

However, for most priors with a pdf p X (x), the MMSE estimator does not coincide with the MAP estimator (i.e., ψ MMSE = ψ MAP ), hence φ MMSE = φ MAP (even up to a constant additive term). Indeed, by Theorem II.2, the penalty φ MMSE (x) defined in (II.7) has a number of specific properties. Therefore, if φ MAP (x) =log p X (x) fails to satisfy one of these properties, then the identity φ MMSE (x) = φ MAP (x) + c (for some constant c ∈ R and all x ∈ R n ) cannot be satisfied.

For example, generalized Gaussian priors p X (x) ∝ exp(-α x p p ) with 0 < p ≤ 1 are not smooth at x = 0, hence they are not C ∞ : as a result for such priors there is not even any pair a, b ∈ R such that φ MMSE (x) = a + b • φ MAP (x) for all x.

One may also wonder whether a reciprocal to Theorem II.2 is possible: given a penalty function φ(x), does there exist a prior P X such that the MMSE estimator ψ MMSE with this prior is associated to the penalty φ MMSE (x) = φ(x) (up to a constant additive term) ? When this prior exists, can we characterize it in terms of the penalty function φ ? Even though one can always define the tentatively associated "MMSE estimator" ψ(y) = prox φ (y), the main difficulty is to understand when there exists a probability measure P X such that ψ(y)y = ∇ log(p B ⋆ P X )(y). This combined integration and Gaussian deconvolution problem often does not admit a solution, for example: when ψ is not one to one; when φ(x) is not sufficiently smooth.

V. CONCLUSION AND PERSPECTIVES

We proved that the MMSE estimator for Gaussian denoising with any prior can be written as the MAP estimator with a possibly different prior (and that the MAP estimator with certain priors can be interpreted as a MMSE estimator with a possibly different prior). These results, in conjunction with Nikolova's highlighting of model distortions brought by MAP estimation [START_REF] Nikolova | Model distortions in Bayesian MAP reconstruction[END_REF], indicate that one should be cautious when interpreting penalized least squares regression schemes in terms of priors:

• If the unknown noiseless data x follows a prior with pdf p X (x) ∝ exp(-φ(x)) and if we choose the MAP as a criterion for estimating it, then the resulting denoising scheme leads to penalized least squares regression with penalty φ(x). This MAP estimator may however have poor denoising performance2 for this type of data [START_REF] Nikolova | Model distortions in Bayesian MAP reconstruction[END_REF]. • In practice, the choice of penalized least squares regression with penalty φ(x) is seldomly associated to the belief that the unknown noiseless data follows a prior with pdf p X (x) ∝ exp(-φ(x)). Instead, it rather stems from the need for numerical efficiency and the empirical observation that it achieves good denoising performance for the considered class of data. By definition, optimum denoising (as measured by the mean squares error) is achieved by the MMSE estimator. As shown in this paper, the latter is indeed always associated to a penalized least squares scheme 3 . This sheds a new light on the popularity of such schemes for Gaussian denoising. Quite obviously, the denoising performance of penalized least squares regression with a given penalty φ(x) heavily depends on the prior P X underlying the unknown noiseless data. We focused in this paper on the case where the penalized least squares regression estimator ψ(y) = prox φ (y) coincides with the MMSE estimator: its denoising performance E( prox φ (Y ) -X 2

2 ) is optimum. An interesting open problem related to the results of this paper would be to understand for which priors P X we obtain "good" denoising performance with ψ(y) = prox φ (y), i.e., when the denoising performance is bounded by a constant C > 1 times the optimum performance.

One can imagine concrete applications of the results presented here for certain priors: in general the MMSE estimator ψ MMSE (y) is a priori expressed as an intractable high-dimensional integral; however, if the penalty function φ MMSE (x) admits a simple expression amenable to efficient numerical optimization (e.g., convex optimization), then the MMSE estimator can be computed efficiently. Developping such approaches requires a more in-depth understanding of the properties of penalty functions φ MMSE (x) obtained through Theorem II.2. Of particular interest would be the construction of explicit examples where φ MMSE (x) is "simple" while p Y (y) involves an intractable integral.

Another interesting perspective is to obtain alternate statistical interpretations of a larger class of penalized least squares regression estimators (e.g., with non-smooth φ(x) such as those leading to sparse estimates). As remarked above, the lack of smoothness makes it impossible to interpret such estimators in terms of a MMSE estimator, however one may seek interpretations that leave the strict Bayesian framework: for example, one may wish to obtain an interpretation as the optimum of a hybrid Bayesian cost function min ψ {EC(ψ(X + B), X) + K(ψ)} where the term K(•) forces the function ψ to be in some function class. Eventually, one may also wish to extend theses results to ill-posed linear inverse problems of the type y = Ax + b, and to deal with non-Gaussian noise.

The above expression is also valid is we exchange the role of the integration variables b and b ′ , hence by taking the average of these two equal expressions we obtain

p Y ∇ 2 p Y • v, v = y-x,v 2 + y-x ′ ,v 2 2 -1 • p B (y -x)p B (y -x ′ )dP X (x)dP X (x ′ )
Similarly we can write

p 2 Y = p B (y -x)p B (y -x ′ )dP X (x)dP X (x ′ ) ∇p Y , v 2 = y -x, v y -x ′ , v • p B (y -x)p B (y -x ′ )dP X (x)dP X (x ′ )
Overall, the numerator of the right hand side in (A.3) becomes

x ′ -x, v 2 2 p B (y -x)p B (y -x ′ )dP X (x)dP X (x ′ ). (A.4)
Now, since there is no c such that X, v = c with probability one, there exists

x 1 , x 2 ∈ R n , d = x 2 -x 1 , v = 0, such that the Euclidean balls B i = B(x i , d/3) ⊂ R n , have positive probability P X (B i ) > 0. For (x, x ′ ) ∈ B 1 × B 2 the function g(x, x ′ ) := x ′ -x,v 2 2 p B (y -x)p B (y -x ′ ) is bounded from below by some constant η > 0, hence the integral in (A.4) is bounded from below by B1×B2 g(x, x ′ )dP X (x)dP X (x ′ ) ≥ η • P X (B 1 )P X (B 2 ) > 0. We conclude that J[ψ MMSE ] • v, v > 0.
We are now equipped to prove Lemma II.1.

Proof of Lemma II.1: We let the reader check that p Y cannot vanish. Since it is C ∞ , ψ MMSE is also C ∞ . To prove that ψ MMSE is one-to-one, we proceed by contradiction, assuming that ψ MMSE (y) = ψ MMSE (y ′ ) while y ′ = y. We define v := (y ′y)/ y ′y 2 and the function f : t → f (t) := v, ψ MMSE (y + tv) ∈ R. Since the function f is smooth and f (0) = f ( y ′y 2 ), by Rolle's theorem the derivative of f must vanish for some 0 < t < y ′y 2 . However by Lemma A.1 we have f ′ (t) = v, J[ψ MMSE ](y + tv) • v > 0 which yields a contradiction. Therefore, the inverse function ψ -1 MMSE exists as claimed. The fact that it is also C ∞ follows from the positivity of the Jacobian of ψ MMSE and the inverse function theorem.

B. Proof of Theorem II.2

The fact that φ MMSE is C ∞ on Imψ MMSE is a straightforward consequence of its definition (II.7) and of the fact that p Y as well as ψ -1 MMSE are C ∞ (Lemma II.1). We wish to check that the proximity operator of φ MMSE defined by (II.7) is indeed ψ MMSE . The definition of φ MMSE (x) for x / ∈ Imψ MMSE ensures that prox φMMSE takes its values in Imψ MMSE . We let the reader check that a consequence of Lemma A.1 is that the set Imψ MMSE is open. For brevity we denote q(y) = log p Y (y) and

g(u) := 1 2 y -ψ MMSE (u) 2 2 + φ MMSE [ψ MMSE (u)] = 1 2 ψ MMSE (u) -y 2 2 - 1 2 ∇q(u) 2 2 -q(u).
Since J[ψ MMSE ](u) = I + ∇ 2 q(u) (Lemma A. As a result 0 ≤ exp(-φ MMSE (y)) ≤ p Y (y), and since p Y (y) is integrable so is exp(-φ MMSE (y)).

C. Proof of Lemma III.2

Thanks to (A.4), and since both p B and p X are symmetric, the numerator of (A.3) for y = 0 reads

(x ′ -x) 2 2 • p B (-x)p B (-x ′ )p X (x)p X (x ′ )dxdx ′ = x 2 2 • p B (x)p X (x)dx • p B (x ′ )p X (x ′ )dx ′ + (x ′ ) 2 2 • p B (x ′ )p X (x ′ )dx ′ • p B (x)p X (x)dx -x ′ • p B (x ′ )p X (x ′ )dx ′ • x • p B (x)p X (x)dx = x 2 • p B (x)p X (x)dx • p B (x ′ )p X (x ′ )dx ′
Since p Y (y) = p B (x)p X (x)dx, inserting the above expression in (A.3) for y = 0 and using that p X (x) = 0 for |x| < 1 + ε we obtain

ψ ′ MMSE (0) = x 2 • p B (x)p X (x)dx p B (x)p X (x)dx = |x|≥1+ε x 2 • p B (x)p X (x)dx |x|≥1+ε p B (x)p X (x)dx ≥ (1 + ε) 2 > 1.
Therefore, ψ MMSE is expansive. Since it is also increasing, the associated φ MMSE is C ∞ (Theorem II.2) hence it is proper and continuous. As a result of [2, Proposition 2.4], since ψ MMSE = prox φMMSE , the penalty φ MMSE cannot be convex. Similar examples can be built in higher dimensions.

Fig. 1 .

 1 Fig.1. Left: MMSE estimator ψMMSE(y) (solid line) and its inverse ψ -1 MMSE (y) (dashed line),, in the Bernoulli-Gaussian case, p = 0.9, σ 2 0 → 0, σ 2 1 = 10. Right: MAP penalty φMAP(x) = -log pX(x) (dotted line), negative log-evidence (-log pY (x)) (dashed line) and MMSE penalty φMMSE(x) (solid line).

2 y -y 2 2 + 2 y

 222 1) and ψ MMSE (u) = u + ∇q(u) (Equation (II.2)), we obtain∇g(u) =J[ψ MMSE ](u) • ψ MMSE (u)y -∇ 2 q(u) • ∇q(u) -∇q(u) =J[ψ MMSE ](u) • ψ MMSE (u)y -∇q(u) =J[ψ MMSE ](u) • uy Now consider f v (t) := g(y + tv) with v = 0 an arbitrary vector. Its derivative is f ′ v (t) = ∇g(y + tv), v = J[ψ MMSE ](y + tv) • tv, v = t • J[ψ MMSE ](y + tv).v, vwhich, by Lemma A.1, has the sign of t, showing that f v admits its strict global minimum at t = 0. Since this is true for any choice of v it follows that g has no stationary point other that u = y, and that g(u) > g(y) whenever u = v, that is to say x → 1 2 yx 2 2 + φ MMSE (x) admits a unique global minimum at x = ψ MMSE (y). To conclude, since ψ MMSE (y) = prox φMMSE (y), we have for any y φ MMSE (y) = 1 φ MMSE (y) ≥ 1 ψ MMSE (y) 2 2 + φ MMSE [ψ MMSE (y)] =log p Y (y).

This interpretation only makes sense if C φ < ∞ is integrable. Otherwise some authors refer to a "non-informative prior".

Even though, as shown in this paper, this MAP scheme can sometimes be interpreted as an MMSE estimator with a different prior, this re-interpretation does not alter the denoising scheme nor its denoising performance.

Yet, the associated penalized least squares problem may not be more computationally tractable than the original MMSE.

VI. ACKNOWLEDGEMENTS

This existence of this paper owes much to several discussions with Mike Davies about the Bayesian "interpretation" of sparse regularization, as well as intense discussions with Jérôme Idier on the same topic during the second French Spring School of Inverse Problems in Signal Processing, held in the beautiful mediterranean island of Porquerolles in the spring of 2010. The author is very thankful to Mike, Jérôme, and to the organizers of the Spring school for these passionate discussions, and would also like to thank Jean-Christophe Pesquet, who provided his insight on proximity operators, as well as Patrick Perez and Miki Elad, whose comments on a draft version of this paper were precious. Last, the comments of the three anonymous reviewers were very helpful to improve the final version of the paper.

and is symmetric positive definite:

Proof: Without loss of generality we consider a unit norm vector v 2 = 1. For brevity we omit the dependency in the variable y when possible. First, by (I.2) we have

We will now prove that the numerator in (A.3) is positive for all y. Since p B (b) ∝ e -b 2 2 /2 , we have

• p B (yx)p B (yx ′ )dP X (x)dP X (x ′ )