Claire Gardent
email: claire.gardent@loria.fr

Shashi Narayan
email: shashi.narayan@loria.fr

Generating Elliptic Coordination

 2398 input whose corresponding output sentence contain an ellipsis. We show that 9% of the data contains an ellipsis and that both coverage and BLEU score markedly decrease for elliptic input (from 82.3% coverage for non-elliptic sentences to 65.3% for elliptic sentences and from 0.60 BLEU score to 0.47). We argue that elided material should be represented using phonetically empty nodes and we introduce a set of rewrite rules which permits adding these empty categories to the SR data. Finally, we evaluate an existing surface realiser on the resulting dataset. We show that, after rewriting, the generator achieves a coverage of 76% and a BLEU score of 0.74 on the elliptical data.

Introduction

To a large extent, previous work on generating ellipsis has assumed a semantically fully specified input [START_REF] Shaw | Segregatory coordination and ellipsis in text generation[END_REF][START_REF] Harbusch | Generating clausal coordinate ellipsis multilingually: A uniform approach based on postediting[END_REF][START_REF] Theune | Performing aggregation and ellipsis using discourse structures[END_REF]. Given such input, elliptic sentences are then generated by first producing full sentences and second, deleting from these sentences substrings that were identified to obey deletion constraints.

In contrast, recent work on generation often assumes input where repeated material has already been elided. This includes work on sentence compression which regenerates sentences from surface dependency trees derived from parsing the initial text [START_REF] Filippova | Dependency tree based sentence compression[END_REF]; Surface realisation approaches which have produced results for regenerating from the Penn Treebank [START_REF] Langkilde-Geary | An empirical verification of coverage and correctness for a generalpurpose sentence generator[END_REF][START_REF] Charles | Evaluating coverage for large symbolic nlg grammars[END_REF][START_REF] Zhong | Building surface realizers automatically from corpora[END_REF][START_REF] Cahill | Robust pcfg-based generation using automatically acquired lfg approximations[END_REF][START_REF] White | Perceptron reranking for ccg realization[END_REF]; and more recently, the Surface Realisation (SR) Task [START_REF] Belz | The first surface realisation shared task: Overview and evaluation results[END_REF] which has proposed dependency trees and graphs derived from the Penn Treebank (PTB) as a common ground input representation for testing and comparing existing surface realisers. In all these approaches, repeated material is omitted from the representation that is input to surface realisation.

As shown in the literature, modelling the interface between the empty phonology and the syntactic structure of ellipses is a difficult task. For parsing, [START_REF] Sarkar | Coordination in tree adjoining grammars: Formalization and implementation[END_REF], [START_REF] Banik | Semantics of VP coordination in LTAG[END_REF] and [START_REF] Seddah | The use of mctag to process elliptic coordination[END_REF] propose either to modify the derivation process of Tree Adjoining Grammar or to introduce elementary trees anchored with empty category in a synchronous TAG to accommodate elliptic coordinations. In HPSG (Head-Driven Phrase Structure Grammar), [START_REF] Levy | Coordination and neutralization in HPSG[END_REF] introduce a neutralisation mechanism to account for unlike constituent coordination ; in LFG (Lexical Functional Grammar), [START_REF] Dalrymple | Feature indeterminacy and feature resolution[END_REF] employ set values to model coordination; in CCG (Combinatory Categorial Grammar, [START_REF] Steedman | Surface Structure and Interpretation[END_REF]), it is the non standard notion of constituency assumed by the approach which permits accounting for coordinated structures; finally, in TLCG (Type-Logical Categorial Grammar), gapping is treated as likecategory constituent coordinations [START_REF] Kubota | Gapping as like-category coordination[END_REF].

In this paper, we focus on how surface realisation handles elliptical sentences given an input where repeated material is omitted. We extract from the SR data 2398 input whose corresponding output sentence contain an ellipsis. Based on previous work on how to annotate and to represent ellipsis, we argue that elided material should be represented using phonetically empty nodes (Section 3) and we introduce a set of rewrite rules which permits adding these empty categories to the SR data (Section 4). We then evaluate our surface realiser (Narayan and Gardent, 2012b) on the resulting dataset (Section 5) and we show that, on this data, the generator achieves a coverage of 76% and a BLEU score, for the generated sentences, of 0.74. Section 6 discusses related work on generating elliptic coordination. Section 7 concludes.

Elliptic Sentences

Elliptic coordination involves a wide range of phenomena including in particular non-constituent coordination (1, NCC) i.e., cases where sequences of constituents are coordinated; gapping (2, G) i.e., cases where the verb and possibly some additional material is elided; shared subjects (3, SS) and right node raising (4, RNR) i.e., cases where a right most constituent is shared by two or more clauses 1 .

(1) [It rose] i 4.8 % in June 1998 and ǫ i 4.7% in June 1999. NCC (2) Sumitomo bank [donated] i $500, 000, Tokyo prefecture ǫ i $15, 000 and the city of Osaka ǫ i $10, 000 . Gapping (3) [the state agency 's figures] i ǫ i confirm previous estimates and ǫ i leave the index at 178.9 .

Shared Subject (4) He commissions ǫ i and splendidly interprets ǫ i [fearsome contemporary scores] i .

RNR

We refer to the non elliptic clause as the source and to the elliptic clause as the target. In the source, the brackets indicate the element shared with the target while in the target, the ǫ i sign indicate the elided material with co-indexing indicating the antecedent/ellipsis relation. In gapping clauses, we refer to the constituents in the gapped clause, as remnants.

Representing and Annotating Elided Material

We now briefly review how elided material is represented in the literature.

Linguistic Approaches. While [START_REF] Sag | Deletion and logical form[END_REF], [START_REF] Williams | Discourse and logical form[END_REF], [START_REF] Kehler | Coherence in discourse[END_REF], [START_REF] Merchant | The syntax of silence: Sluicing, islands, and the theory of ellipsis[END_REF] 1 Other types of elliptic coordination include sluicing and Verb-Phrase ellipsis. These will not be discussed here because they can be handled by the generator by having the appropriate categories in the grammar and the lexicon e.g., in a Tree Adjoining Grammar, an auxiliary anchoring a verb phrase for VP ellipsis and question words anchoring a sentence for sluicing. and van Craenenbroeck (2010) have argued for a structural approach i.e., one which posits syntactic structure for the elided material, [START_REF] Keenan | Names, quantifiers, and the sloppy identity problem[END_REF], [START_REF] Hardt | Verb phrase ellipsis: Form, meaning and processing[END_REF], [START_REF] Dalrymple | Ellipsis and higher-order unification[END_REF], [START_REF] Ginzburg | Interrogative investigations[END_REF] and [START_REF] Culicover | Simpler Syntax[END_REF] all defend a non structural approach. Although no consensus has yet been reached on these questions, many of these approaches do postulate an abstract syntax for ellipsis. That is they posit that elided material licenses the introduction of phonetically empty categories in the syntax or at some more abstract level (e.g., the logical form of generative linguistics).

Treebanks. Similarly, in computational linguistics, the treebanks used to train and evaluate parsers propose different means of representing ellipsis.

For phrase structure syntax, the Penn Treebank Bracketing Guidelines extensively describe how to annotate coordination and missing material in English [START_REF] Bies | Bracketing guidelines for treebank II style penn treebank project[END_REF]. For shared complements (e.g., shared subject and right node raising constructions), these guidelines state that the elided material licenses the introduction of an empty *RNR* category co-indexed with the shared complement (cf. Figure 1) while gapping constructions are handled by labelling the gapping remnants (i.e., the constituents present in the gapping clause) with the index of their parallel element in the source (cf. Figure 2). In dependency treebanks, headless elliptic constructs such as gapping additionally raise the is-sue of how to represent the daughters of an empty head. Three main types of approaches have been proposed. In dependency treebanks for German [START_REF] Daum | Automatic transformation of phrase treebanks to dependency trees[END_REF][START_REF] Hajič | The conll-2009 shared task: Syntactic and semantic dependencies in multiple languages[END_REF] and in the Czech treebank [START_REF] Čmejrek | Prague czech-english dependency treebank: Syntactically annotated resources for machine translation[END_REF][START_REF] Hajič | The conll-2009 shared task: Syntactic and semantic dependencies in multiple languages[END_REF], one of the dependents of the headless phrase is declared to be the head. This is a rather undesirable solution because it hides the fact that there the clause lacks a head. In contrast, the Hungarian dependency treebank [START_REF] Vincze | Hungarian dependency treebank[END_REF] explicitly represents the elided elements in the trees by introducing phonetically empty elements that serve as attachment points to other tokens. This is the cleanest solution from a linguistic point of view. Similarly, [START_REF] Seeker | Making ellipses explicit in dependency conversion for a german treebank[END_REF] present a conversion of the German Tiger treebank which introduces empty nodes for verb ellipses if a phrase normally headed by a verb is lacking a head. They compare the performance of two statistical dependency parsers on the canonical version and the CoNLL 2009 Shared Task data and show that the converted dependency treebank they propose yields better parsing results than the treebank not containing empty heads.

In sum, while some linguists have argued for an approach where ellipsis has no syntactic representation, many have provided strong empirical evidence for positing empty nodes as place-holders for elliptic material. Similarly, in devising treebanks, computational linguists have oscillated between representations with and without empty categories. In the following section, we present the way in which elided material is represented in the SR data; we show that it underspecifies the sentences to be generated; and we propose to modify the SR representations by making the relationship between ellipsis and antecedent explicit using phonetically empty categories and co-indexing.

Rewriting the SR Data

The SR Task 2011 made available two types of data for surface realisers to be tested on: shallow dependency trees and deep dependency graphs.

Here we focus on the shallow dependency trees i.e., on syntactic structures.

The input data provided by the SR Task were obtained from the Penn Treebank. They were derived indirectly from the LTH Constituent-to-Dependency Conversion Tool for Penn-style Treebanks (Pennconverter, [START_REF] Johansson | Extended constituent-to-dependency conversion for english[END_REF]) by post-processing the CoNLL data to re- move word order, inflections etc. It consists of a set of unordered labelled syntactic dependency trees whose nodes are labelled with word forms, part of speech categories, partial morphosyntactic information such as tense and number and, in some cases, a sense tag identifier. The edges are labelled with the syntactic labels provided by the Pennconverter. All words (including punctuation) of the original sentence are represented by a node in the tree. Figures 3,4, 5 and 6 show (simplified) input trees from the SR data.

In the SR data, the representation of ellipsis adopted in the Penn Treebank is preserved modulo some important differences regarding co-indexing.

Gapping is represented as in the PTB by labelling the remnants with a marker indicating the source element parallel to each remnant. However while in the PTB, this parallelism is made explicit by co-indexing (the source element is marked with an index i and its parallel target element with the marker = i), in the SR data this parallelism is approximated using functions. For instance, if the remnant is parallel to the source subject, it will be labelled GAP-SBJ (cf. Figure 3). specifies the relation between the object and the coordinated verbs in RNR constructions: the object could be shared as in He commissions ǫi and splendidly interprets ǫi [fearsome contemporary scores]i. (Figure 4) or not as in They aren't showing James Madison taking a puff or lighting up (Figure 5). In both cases, the representation is the same i.e., the shared object (fearsome contemporary scores) and the unshared object (a puff ) are both attached to the first verb. Finally, NCC structures are handled in the same way as gapping by having the gapping remnants labelled with a GAP prefixed function (e.g., GAP-SBJ) indicating which element in the source the gapping remnant is parallel to (cf. Figure 6).

V V FUNC COORD FUNC COORD X CONJ W X CONJ W GAP-FUNC ⇒ CONJ Y Vǫ FUNC Y Wǫ
Summing up, the SR representation schema underspecifies ellipsis in two ways. For gapping and non-constituent coordination, it describes parallelism between source and target elements rather than specifying the syntax of the elided material. For subject sharing and right node raising, it fails to explicitly specify argument sharing.

V1 V1 SUBJ COORD SUBJ COORD X CONJ Y1 X CONJ Y1 CONJ ⇒ CONJ V2 V2 SUBJ Y2 Xǫ Y2
Figure 8: Subject sharing: the subject dependent is copied over to the target clause and marked as phonetically empty.

To resolve this underspecification, we rewrite the SR data using tree rewrite rules as follows.

In Gapping and NCC structures, we copy the source material that has no (GAP-marked) counterpart in the target clause to the target clause marking it to indicate a phonetically empty category (cf. Figure 7).

For Subject sharing, we copy the shared subject of the source clause in the target clause and mark it to be a phonetically empty category (cf. Figure 8).

For Right-Node-Raising, we unfold the ambiguity producing structures where arguments present in the source but not in the target are optionally copied over to the target (cf. Figure 9). These rewrite rules are implemented efficiently

V1 V1 V1 COORD OBJ COORD OBJ COORD OBJ X1 CONJ Y X1 CONJ Y X1 CONJ Yǫ CONJ ⇒ CONJ , CONJ V2 V2 V2 OBJ X2 X2 X2 Y
Figure 9: Right-Node-Raising: the object dependent is optionally copied over to the target clause and marked as phonetically empty in the source clause.

using GrGen, an efficient graph rewriting system (Geißet al., 2006).

Generating Elliptic Coordination

The Surface Realiser

To generate sentences from the SR data, we use our surface realiser (Narayan and Gardent, 2012b), a grammar-based generator based on a Feature-Based Lexicalised Tree Adjoining Grammar (FB-LTAG) for English. This generator first selects the elementary FB-LTAG trees associated in the lexicon with the lemmas and part of speech tags associated with each node in the input dependency tree. It then attempts to combine the selected trees bottom-up taking into account the structure of the input tree (only trees that are selected by nodes belonging to the same local input tree are tried for combination). A language model is used to implement a beam search letting through only the n most likely phrases at each bottom up combination step. In this experiment, we set n to 5. The generator thus outputs at most 5 sentences for each input. As mentioned in the introduction, most computational grammars have difficulty accounting for ellipses and FB-LTAG is no exception.

The difficulty stems from the fact that in elliptical sentences, there is meaning without sound. As a result, the usual form/meaning mappings that in non-elliptic sentences allow us to map sounds onto their corresponding meanings, break down. For instance, in the sentence John eats apples and Mary pear, the Subject-Verb-Object structure which can be used in English to express a binary relation is present in the source clause but not in the elided one. In practice, the syntax of elliptical sentences often leads to a duplication of the grammatical system, one system allowing for non elliptical sentences and the other for their elided counterpart.

For parsing with TAG, two main methods have been proposed for processing elliptical sentences. [START_REF] Sarkar | Coordination in tree adjoining grammars: Formalization and implementation[END_REF] introduces an additional operation for combining TAG trees which yields derivation graphs rather than trees. [START_REF] Seddah | The use of mctag to process elliptic coordination[END_REF] uses Multi-Component TAG and proposes to associate each elementary verb tree with an elliptic tree with different pairs representing different types of ellipses.

We could use either of these approaches for generation. The first approach however has the drawback that it leads to a non standard notion of derivation (the derivation trees become derivation graphs). The second on the other hand, induces a proliferation of trees in the grammar and impacts efficiency.

Instead, we show that, given an input enriched with empty categories as proposed in the previous section, neither the grammar nor the tree combination operation need changing. Indeed, our FB-LTAG surface realiser directly supports the generation of elliptic sentences. It suffices to assume that an FB-LTAG elementary tree may be anchored by the empty string. Given an input node marked as phonetically empty, the generator will then select all FB-LTAG rules that are compatible with the lexical and the morpho-syntactic features labelling that node. Generation will then proceed as usual by composing the trees selected on the basis of the input using substitution and adjunction; and by retrieving from the generation forest those sentences whose phrase structure tree covers the input.

For instance, given the rewritten input shown in Figure 10, the TAG trees associated in the lexicon with donate will be selected; anchored with the empty string and combined with the TAG trees built for Tokyo Prefecture and $15,000 thus yielding the derivation shown in Figure 11.

The Data

We use both the SR test data (2398 sentences) and the SR training data (26604 sentences) to evaluate the performance of the surface realiser on elliptic coordination. Since the realiser we are using is not trained on this data (the grammar was written manually), this does not bias evaluation. Using the training data allows us to gather a larger set of elliptic sentences for evaluation while evaluating also on the test data allows comparison with other realisers.

To focus on ellipses, we retrieve those sentences which were identified by our rewrite rules as potentially containing an elliptic coordination. In essence, these rewrite rules will identify all cases of non-constituent coordination and gapping (because these involve GAP-X dependencies with "X" a dependency relation and are therefore easily detected) and of shared-subjects (because the tree patterns used to detect are unambiguous i.e., only apply if there is indeed a shared subject). For RNR, as discussed in the previous section, the SR format is ambiguous and consequently, the rewrite rules might identify as object sharing cases where in fact the object is not shared. As noted by one of our reviewers, the false interpretation could be The approach would not generalise to other data however.

In total, we retrieve 2398 sentences3 potentially containing an elliptic coordination from the SR training data. The number and distribution of these sentences in terms of ellipsis types are given in Table 1. From the test data, we retrieve an additional 182 elliptic sentences.

Evaluation

We ran the surface realiser on the SR input data both before and after rewriting elliptic coordinations; on the sentences estimated to contain ellipsis; on sentences devoid of ellipsis; and on all sentences. The results are shown in Table 2. They indicate coverage and BLEU score before and after rewriting. BLEU score is given both with respect to covered sentences (COV) i.e., the set of input for which generation succeeds; and for all sentences (ALL). We evaluate both with respect to the SR test data and with respect to the SR training data. We use the SR Task scripts for the computation of the BLEU score.

The impact of ellipsis on coverage and precision. Previous work on parsing showed that coordination was a main source of parsing failure [START_REF] Collins | Head-Driven Statistical Models for Natural Language Parsing[END_REF]. Similarly, ellipses is an important source of failure for the TAG generator. Ellipses are relatively frequent with 9% of the sentences in the training data containing an elliptic structure and performance markedly decreases in the presence of ellipsis. Thus, before rewriting, coverage decreases from 82.3% for non-elliptic sentences to 80.75% on all sentences (elliptic and non elliptic sentences) and to 65.3% on the set of elliptic sentences. Similarly, BLEU score decreases from 0.60 for non elliptical sentences to 0.58 for all sentences and to 0.47 for elliptic sentences. In sum, both coverage and BLEU score decrease as the number of elliptic input increases.

The impact of the input representation on coverage and precision.

Recent work on treebank annotation has shown that the annotation schema adopted for coordination impacts parsing. In particular, [START_REF] Maier | Annotating coordination in the Penn Treebank[END_REF] propose revised annotation guidelines for coordinations in the Penn Treebank whose aim is to facilitate the detection of coordinations. And [START_REF] Dukes | One-step statistical parsing of hybrid dependency-constituency syntactic representations[END_REF] show that treebank annotations which include phonetically empty material for representing elided mate-rial allows for better parsing results.

Similarly, Table 2 shows that the way in which ellipsis is represented in the input data has a strong impact on generation. Thus rewriting the input data markedly extends coverage with an overall improvement of 11 points (from 65% to 76%) for elliptic sentences and of almost 1 point for all sentences.

As detailed in Table 1 though, there are important differences between the different types of elliptic constructs: coverage increases by 68 points for NCC and 64 points for gapping against only 15, 13 and 5 points for RNR, mixed RNR-Shared Subject and Shared Subject respectively. The reason for this is that sentences are generated for many input containing the latter types of constructions (RNR and Shared Subject) even without rewriting. In fact, generation succeeds on the non rewritten input for a majority of RNR (66% PASS), Shared Subject (70% PASS) and mixed RNR-Shared Subject (61% PASS) constructions whereas it fails for almost all cases of gapping (3% PASS) and of NCC (5% PASS). The reason for this difference is that, while the grammar cannot cope with headless constructions such as gapping and NCC constructions, it can often provide a derivation for shared subject sentences by using the finite verb form in the source sentence and the corresponding infinitival form in the target. Since the infinitival does not require a subject, the target sentence is generated. Similarly, RNR constructions can be generated when the verb in the source clause has both a transitive and an intransitive form: the transitive form is used to generate the source clause and the intransitive for the target clause. In short, many sentences containing a RNR or a shared subject construction can be generated without rewriting because the grammar overgenerates i.e., it produces sentences which are valid sentences of English but whose phrase structure tree is incorrect.

Nevertheless, as the results show, rewriting consistently helps increasing coverage even for RNR (+15 points), Shared Subject (+5 points) and mixed RNR-Shared Subject (+13 points) constructions because (i) not all verbs have both a transitive and an intransitive verb form and (ii) the input for the elliptic clause may require a finite form for the target verb (e.g., in sentences such as "[they]i weren't fired but instead ǫi were neglected" where the target clause includes an auxiliary requiring a past participial which in this context requires a subject).

Precision is measured using the BLEU score. For each input, we take the best score obtained within the 5 derivations4 produced by the generator. Since the BLEU score reflects the degree to which a sentence generated by the system matches the corresponding Penn Treebank sentence, it is impacted not just by elliptic coordination but also by all linguistic constructions present in the sentence. Nonetheless, the results show that rewriting consistently improves the BLEU score with an overall increase of 0.09 points on the set of elliptic sentences. Moreover, the consistent improvement in terms of BLEU score for generated sentences (COV column) shows that rewriting simultaneously improves both coverage and precision that is, that for those sentences that are generated, rewriting consistently improves precision.

Analysing the remaining failure cases. To better assess the extent to which rewriting and the FB-LTAG generation system succeed in generating elliptic coordinations, we performed error mining on the elliptic data using our error miner described in (Narayan and Gardent, 2012a). This method permits highlighting the most likely sources of error given two datasets: a set of successful cases and a set of failure cases. In this case, the successful cases is the subset of rewritten input data for elliptic coordination cases for which generation succeeds . The failure cases is the subset for which generation fails. If elliptic coordination was still a major source of errors, input nodes or edges labelled with labels related to elliptic coordination (e.g., the COORD and the GAP-X dependency relations or the CONJ part of speech tag) would surface as most suspicious forms. In practice however, we found that the 5 top sources of errors highlighted by error mining all include the DEP relation, an unknown dependency relation used by the Pennconverter when it fails to assign a label to a dependency edge. In other words, most of the remaining elliptic cases for which generation fails, fails for reasons unrelated to ellipsis.

Comparison with other surface realisers

There is no data available on the performance of surface realisers on elliptic input. However, the performance of the surface realiser can be compared with those participating in the shallow track of the SR challenge. On the SR training data, the TAG surface realiser has an average run time of 2.78 seconds per sentence (with an average of 20 words per sentence), a coverage of 82% and BLEU scores of 0.73 for covered and 0.60 for all. On the SR test data, the realiser achieves a coverage of 79% and BLEU scores of 0.59 for covered and 0.47 for all. In comparison, the statistical systems in the SR Tasks achieved 0.88, 0.85 and 0.67 BLEU score on the SR test set and the best symbolic system 0.25 [START_REF] Belz | The first surface realisation shared task: Overview and evaluation results[END_REF].

Related work

Previous work on generating elliptic sentences has mostly focused on identifying material that could be elided and on defining procedures capable of producing input structures for surface realisation that support the generation of elliptic sentences. [START_REF] Shaw | Segregatory coordination and ellipsis in text generation[END_REF] developed a sentence planner which generates elliptic sentences in 3 steps. First, input data are grouped according to their similarities. Second, repeated elements are marked. Third, constraints are used to determine which occurrences of a marked element should be deleted. The approach is integrated in the PLANDoc system [START_REF] Mckeown | Practical issues in automatic documentation generation[END_REF] and shown to generate a wide range of elliptic constructs including RNR, VPE and NCC using FUF/SURGE [START_REF] Elhadad | Using argumentation to control lexical choice: a functional unification implementation[END_REF], a realisation component based on Functional Unification Grammar. [START_REF] Theune | Performing aggregation and ellipsis using discourse structures[END_REF] describe how elliptic sentences are generated in a story generation system. The approach covers conjunction reduction, right node raising, gapping and stripping and uses dependency trees connected by rhetorical relations as input. Before these trees are mapped to sentences, repeated elements are deleted and their antecedent (thesource element) is related by a SUB-ORROWED relation to their governor in the elliptic clause and a SUIDENTICAL relation to their governor in the antecedent clause. This is then interpreted by the surface realiser to mean that the repeated element should be realised in the source clause, elided in the target clause and that it licenses the same syntactic structure in both clauses. [START_REF] Harbusch | Generating clausal coordinate ellipsis multilingually: A uniform approach based on postediting[END_REF] have proposed a module called Elleipo which takes as input unreduced, non-elliptic, syntactic structures annotated with lexical identity and coreference relationships between words and word groups in the conjuncts; and returns as output structures annotated with elision marks indicating which elements can be elided and how (i.e., using which type of ellipsis). The focus is on developing a language independent module which can mediate between the unreduced input syntactic structures produced by a generator and syntactic structures that are enriched with elision marks rich enough to determine the range of possible elliptic and non elliptic output sentences.

In CCG, grammar rules (type-raising and composition) permit combining non constituents into a functor category which takes the shared element as argument; and gapping remnants into a clause taking as argument its left-hand coordinated source clause. [START_REF] White | Efficient realization of coordinate structures in combinatory categorial grammar[END_REF] describes a chart based algorithm for generating with CCG and shows that it can efficiently realise NCC and gapping constructions.

Our proposal differs from these approaches in that it focuses on the surface realisation stage (assuming that the repeated elements have already been identified) and is tested on a large corpus of newspaper sentences rather than on hand-made document plans and relatively short sentences.

Conclusion

In this paper, we showed that elliptic structures are frequent and can impact the performance of a surface realiser. In line with linguistic theory and with some recent results on treebank annotation, we argued that the representation of ellipsis should involve empty categories and we provided a set of tree rewrite rules to modify the SR data accordingly. We then evaluated the performance of a TAG based surface realiser on 2398 elliptic input derived by the SR task from the Penn Treebank and showed that it achieved a coverage of 76% and a BLEU score of 0.74 on generated sentences. Our approach relies both on the fact that the grammar is lexicalised (each rule is associated with a word from the input) and on TAG extended domain of locality (which permits using a rule anchored with the empty string to reconstruct the missing syntax in the elided clause thereby making it grammatical).

We will release the 2398 input representations we gathered for evaluating the generation of elliptic coordination so as to make it possible for other surface realisers to be evaluated on their abil-ity to generate ellipsis. In particular, its would be interesting to examine how other grammar based generators perform on this dataset such as White's CCG based generator (2006) (which eschews empty categories by adopting a more flexible notion of constituency) and Carroll and Oepen's HPSG based generator (2005) (whose domain of locality differs from that of TAG).

Figure 1 :Figure 2 :

 12 Figure 1: Penn Treebank annotation for Right Node Raising "Do avoid puncturing ǫi or cutting into ǫi [meats]i."

Figure 3 :

 3 Figure 3: Gapping in the SR data. "Sumitomo bank [donated]i $500, 000 and Tokyo prefecture ǫi $15, 000."

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Subject Sharing and RNR in the SR data. "[He]j ǫj commissions ǫi and ǫj splendidly interprets ǫi [fearsome contemporary scores]i."

Figure 7 :

 7 Figure7: Gapping and Non Constituent Coordination structures rewriting (V: a verb, CONJ: a conjunctive coordination, X, Y and W three sets of dependents). The antecedent verb (V) and the source material without counterpart in the gapping clause (W) are copied over to the gapping clause and marked as phonetically empty.

Figure 10 :

 10 Figure 10: Gapping after rewriting "Sumitomo bank [donated]i $500, 000 and Tokyo prefecture ǫi $15, 000."

Figure 11 :

 11 Figure 11: Derivation for "Tokyo prefecture ǫ $15,000"

Table 1 :

 1 Generation results on elliptical data before and after input rewriting (SS: Shared Subject, NCC: Non Constituent Coordination, RNR: Right Node Raising). The number in brackets in the first column is the number of cases. Pass stands for the coverage of the generator. COV and ALL in BLEU scores column stand for BLEU scores for the covered and the total input data.

	Elliptic Coordination Data
	Elliptic Coordination	Pass	BLEU Scores COV ALL
		Before 66%	0.68	0.45
	RNR (384)	After	81%	0.70	0.57
		Delta	+15 +0.02 +0.12
		Before 70%	0.74	0.52
	SS (1462)	After	75%	0.75	0.56
		Delta	+5 +0.01 +0.04
	SS + RNR (456)	Before 61% After 74% Delta +13 +0.02 +0.11 0.71 0.43 0.73 0.54
		Before	3%	0.53	0.01
	Gapping (36)	After	67%	0.74	0.49
		Delta	+64 +0.21 +0.48
		Before	5%	0.68	0.03
	NCC (60)	After	73%	0.74	0.54
		Delta	+68 +0.06 +0.51
		Before 65%	0.72	0.47
	Total (2398)	After	76%	0.74	0.56
		Delta	+11 +0.02 +0.09

dropped out by consulting the Penn Treebank 2 .

Table 2 :

 2 Generation results on SR test and SR training data before and after input rewriting (+E stands for elliptical data, -E for non elliptical data and T for total.)

		SR Data		Pass	BLEU Scores COV ALL
			Before 58%	0.59	0.34
		+E (182)	After	67%	0.59	0.40
			Delta	+9 +0.00 +0.06
			Before 80%	0.59	0.47
	Test	-E (2216)	After	80%	0.59	0.48
			Delta	+0 +0.00 +0.01
			Before 78%	0.58	0.46
		T (2398)	After	79%	0.59	0.47
			Delta	+1 +0.01 +0.01
		+E (2398) (Table 1)	Before 65% After 76% Delta +11 +0.02 +0.09 0.72 0.47 0.74 0.56
			Before 82%	0.73	0.60
	Training	-E (24206)	After	82%	0.73	0.60
			Delta	+0 +0.00 +0.00
			Before 81%	0.72	0.58
		T (26604)	After	82%	0.73	0.60
			Delta	+1 +0.01 +0.02

The Penn Treebank makes the RNR interpretations explicit (refer to Figure1).

3 It is just a coincidence that the size of the SR test data and the number of extracted elliptic sentences are the same.

The language model used in the generator allows only

likely derivations (refer to section 5.1).

Acknowledgments

We would like to thank Anja Belz and Mike White for providing us with the evaluation data and the evaluation scripts. The research presented in this paper was partially supported by the European Fund for Regional Development within the framework of the INTERREG IV A Allegro Project.


Bikash Gyawali
email: bikash.gyawali@loria.fr

Claire Gardent
email: claire.gardent@loria.fr

LOR-KBGEN, A Hybrid Approach To Generating from the KBGen Knowledge-Base

This abstract describes a contribution to the 2013 KBGen Challenge from CNRS/LORIA and the University of Lorraine. Our contribution focuses on an attempt to automate the extraction of a Feature Based Tree Adjoining Grammar equipped with a unification based compositional semantics which can be used to generate from KBGen data.

Introduction Semantic grammars, i.e., grammars which link syntax and semantics, have been shown to be useful for generation and for semantic parsing. This abstract outlines an attempt to automatically extract from the KBGen data, a Feature Based Tree Adjoining Grammar which can be used for generation from the KBGen data.

Data The KBGen data consists of sets of triples extracted from the AURA knowledge base which encodes knowledge contained in a college-level biology textbook. Each set of triple was selected to be verbalisable as a simple, possibly complex sentence. For instance, the input shown in Figure 1 can be verbalised as1 :

(1) The function of a gated channel is to release particles from the endoplasmic reticulum

Sketch of the Overall Grammar Extraction and Generation Procedure

To generate from the KBGen data, we parsed each input sentence using the Stanford parser; we aligned the semantic input with a substring in the input sentence; we extracted a grammar from the parsed sentences provided with the input triples; and we generated using an existing surface realiser. In addition some of the input were preprocessed to produce a semantics more compatible with the assumption underlying the syntax/semantic interace of SemTAG;

:TRIPLES ( (|Release-Of-Calcium646| |object| |Particle-In-Motion64582|) (|Release-Of-Calcium646| |base| |Endoplasmic-Reticulum64603|) (|Gated-Channel64605| |has-function||Release-Of-Calcium646|) (|Release-Of-Calcium646| |agent| |Gated-Channel64605|)) :INSTANCE-TYPES (|Particle-In-Motion64582| |instance-of| |Particle-In-Motion|) (|Endoplasmic-Reticulum64603| |instance-of| |Endoplasmic-Reticulum|) (|Gated-Channel64605| |instance-of| |Gated-Channel|) (|Release-Of-Calcium646| |instance-of| |Release-Of-Calcium|))
and a procedure was used to guess missing lexical entries.

Alignment and Index Projection Given a Sentence/Input pair (S, I) provided by the KBGen Challenge, we match each entity and event variable in I to a substring in S. Matching uses the variable name, the name of the unary predicate true of that variable and the word form assigned to that predicte in the KBGen lexicon. Digits occurring in the input are removed and the string in the input sentence which is closest to either of the used units is decorated with that variable. Index variables are then projected up the syntactic trees to reflect headedness. For instance, the variable indexed with a noun is projected to the NP level; and the index projected to the NP of a prepositional phrase is project to the PP level.

Grammar Extraction Grammar extraction proceeds in two steps as follows. First, the subtrees whose root node are indexed with an entity variable are extracted. This results in a set of NP and PP trees anchored with entity names and associated with the predication true of the indexing variable.

Second, the subtrees capturing relations between variables are extracted. To perform this ex-traction, each input variable X is associated with a set of dependent variables i.e., the set of variables Y such that X is related to Y (R(X, Y )). The minimal tree containing all and only the dependent variables D(X) of a variable X is then extracted and associated with the set of literals Φ such that

Φ = {R(Y, Z) | (Y = X ∧ Z ∈ D(X))∨ (Y, Z ∈ D(X))}.
This procedure extracts the subtrees relating the argument variables of a semantics functors such as an event or a role.

The extracted grammar is a Feature-Based Tree Adjoining Grammar with a Unification-based compositional semantics as described in [START_REF] Gardent | Integrating a unification-based semantics in a large scale lexicalised tree adjoining grammar for french[END_REF]. Each entry in the grammar associates a natural language expression with a syntactic tree and a semantic representation thereby allowing both for semantic parsing and for generation. Figure 1 shows the tree extracted for the release predicate in Example 1.

Pre-Processing

The parse trees produced by the Stanford parser are pre-processed to better match TAG recursive modeling of modification. In particular, the flat structure assigned to relative clauses is modified into a recursive structure.

The input semantics provided by the KBGen task is also preprocessed to allow for aggregation and to better match the assumptions underlying the syntax/semantics interface of SemTAG.

For aggregation, we use a rewrite rule of the form shown below to support the production of e.g., A cellulose-synthase which contains a polypeptide and two glucose synthesizes cellulose..

R(X, Y 1 ), . . . , R(X, Y n ), P (Y 1), . . . , P (Y n ) ⇒ R(X, Y ), P (Y ), quantity(Y, n)
For relative clauses, we rewrite input of the form plays(X Y),in-event(Y E), P(E), R(E X) to plays(X Y),in-event(Y E), P(E), R(E Y). This captures the fact that in sentences such as A biomembrane is a barrier which blocks the hydrogen ion of a chemical., the entity variable bound by the relative clause is that associated with barrier, not that of the main clause subject biomembrane.

Guessing Missing Lexical Entries To handle unseen input, we start by partitioning the input semantics into sub-semantics corresponding to events, entities and role. We then search the lexicon for an entry with a matching or similar semantics. An entry with a similar semantics is an entry with the same number and same type of literals (literals with same arity and with identical relations). Similar entries are then adapted to create lexical entries for unseen data.

For space reasons, we slightly simplified the KBGen input and removed type information.


Claire Gardent
email: claire.gardent@loria.fr

Alejandra Lorenzo
email: alejandra.lorenzo@loria.fr

Laura Perez-Beltrachini

Lina Rojas-Barahona

Weakly and Strongly Constrained Dialogues for Language Learning

We present two dialogue systems for language learning which both restrict the dialog to a specific domain thereby promoting robustness and the learning of a given vocabulary. The systems vary in how much they constrain the learner's answer : one system places no other constrain on the learner than that provided by the restricted domain and the dialog context ; the other provides the learner with an exercise whose solution is the expected answer. The first system uses supervised learning for simulating a human tutor whilst the second one uses natural language generation techniques to produce grammar exercises which guide the learner toward the expected answer.

Introduction

Work on dialog based tutors for language learning includes both chatbot systems which maintain a free flowing dialog with the learner [START_REF] Shawar | Chatbots : are they really useful ?[END_REF][START_REF] Jia | The study of the application of a web-based chatbot system on the teaching of foreign languages[END_REF] and form-focused dialog systems which restrict the learner answer e.g., by providing her with an answer template to be filled in for the dialog to continue [START_REF] Wilske | Meaning versus form in computer-assisted task-based language learning : A case study on the german dative[END_REF]. While the former encourages language practice with a virtual tutor and requires a good knowledge of the language, the latter focuses on linguistic forms and usually covers a more restricted lexical field thereby being more amenable to less advanced learners.

In these notes, we describe a dialog architecture which (i) supports both free-flowing and formfocused man/machine dialog ; and (ii) ensures that in both cases, dialogs are restricted to a specific lexical field. The free-flowing dialog system uses supervised classification techniques to predict the system dialog move based on the learner's input and does not explicitely constrain the learner's answer. In contrast, the dialog system for intermediate learners provides an exercise which the learner must solve to construct her answer.

To restrict the dialog to a specific domain and to improve system robustness, we make use of a finite-state automaton (FSA) describing the range of permissible interactions within a given domain. This FSA serves to guide the collection of humanhuman interactions necessary to train the classifier ; to verify and if necessary to adjust the system's predicted answer ; and to support the generation of the exercise provided in the form-focused dialog engine.

Finite State Automaton and Domain Representation

To support focused dialog and promote robustness, we make use of the FSA depicted in Figure 2. This FSA models a generic sequence of (System Question, Learner Answer, System Reaction) turns instantiating 4 main question/answer patterns and two possible system reactions.

The system question systematically formulates a question which explicitly lists a set of possible answers.

The learner's answer is then classified into four main types. It selects one of the proposed answers ; it chooses another alternative not mentioned in the system's question ; it indicates that the learner does not know the correct answer or does not understand the question ; or it meets neither of these categories.

Finally, for each answer, the system can continue the dialogue by making a "confirmation" which is used to reassure the learner in the free dialogue system and to provide some feedback in the guided dialogue system ; or just by "informing" to the learner of the correct answer before getting into the next question.

Given a specific domain, this generic FSA is instantiated differently for each question/answer pair making up a dialog. In particular, in the current demonstration system, it is instantiated to model a dialog situated in the kitchen of a virtual world. Figure 1 shows an example dialog.

Situated Dialogues for language learning

Our dialog systems for language learning are integrated in a serious game called I-FLEG (Interactive French Learning Game, [START_REF] Amoia | A Serious Game for Second Language Acquisition in a Virtual Environment[END_REF]) in which the learner can trigger grammar exercices and interactive dialog sessions by clicking on the objects present in the virtual world.

IFLEG integrates the two dialog systems for language learning mentioned above namely, a "free answer dialog system" where the learner answer is guided only by the preceding dialog exchanges ; and a "guided dialog system" which restricts the set of permissible answers by providing the learner with an exercise whose solution provides a possible answer given the current dialog context.

Data collection

To provide the training data necessary to train the free dialog system, we conducted a Wizardof-Oz experiment where language learners were invited to engage in a conversation with the wizard, a French tutor. In these experiments, we followed the methodology and used the tools for data collection and annotation presented in (Rojas- Barahona et al., 2012a). Given an FSA specifiying a set of 5 questions the learner had to answer, the wizard guided the learner through the dialog using this FSA. The resulting corpus consists of 52 dialogues and 1906 sentences.

Free answer Dialogue System

The free answer dialogue system simulates the behavior of the wizard tutor by means of a Logistic-Regression classifier, the FSA and a generation-by-selection algorithm. The system first uses the FSA to determine the next question to be asked. Then for each question, the Logistic-Regression classifier is used to map the learner answer to a system dialog act. At this stage, the FSA is used again, in two different ways. First, it is used to ensure that the predicted system dialog act is consistent with the states in the FSA. In case of a mismatch, a valid dialog act is selected in the current context. In particular, unpredicted "preferred options" and "do not know" learner answers are detected using keyword spotting methods. If the classifier prediction conflicts with the prediction made by key word spotting, it is ignored and the FSA transition is prefereed.

Second, since the system has several consecutive turns, and given that the classifier only predicts the next one, the FSA is used to determine the following system dialog acts sequence. For instance, if the predicted next system dialog act was "confirm", according to the FSA the following system dialog act is "inform" and then eiher the next question encoded in the FSA or "quit".

Training the simulator To train the classifier, we labeled each learner sentence with the dialog act caracterising the next system act. The features used for trainig included context features (namely, the four previous system dialogue acts) and the set of content words present in the learner turns after filtering using tf*idf (Rojas Barahona et al., 2012b). Given the learner input and the current dialog context, the classifier predicts the next system move.

Generation by Selection Given the system move predicted by the dialog manager, the system turn is produced by randomly selecting from the training corpus an utterance annotated with that dialog move.

Guided dialogue system

Unlike the free answer dialogue, the guided dialogue strongly constrains the learner answer by suggesting it in the form of a grammar exercise. FIGURE 2 -Finite-state automata that defines the different states in the dialog for each question Q X. S defines the system, and P the learner.

In the guided dialogue system, the dialogue paths contained in the training corpus are used to decide on the next dialogue move. In a first step, learner's moves are labelled with the meaning representation associated to them by the grammar underlying the natural language generator used to produce IFLEG grammar exercises. Given a sequence S/L contained in the training corpus with S, a system turn and L the corresponding learner's turn, the system then constructs the exercise providing the learner's answer using the methodology described in [START_REF] Perez-Beltrachini | Generating Grammar Exercises[END_REF]. First, a sentence is generated from the meaning representation of the learner answer. Next, the linguistic information (syntactic tree, morpho-syntactic information, lemmas) associated by the generator with the generated sentence is used to build a shuffle, a fill-in-the-blank or a transformation exercise.

Here is an example interaction produced by the system : S : Vous préférez la soupe ou le fromage ? (Do you prefer soup or salad ?)

Please answer using the following words : { je, adorer, le, soupe } This dialogue setting has several benefits. The dialogue script provides a rich context for each generated exercise item, learners are exposed to example communicative interactions, and the system can provide feedback by comparing the answer entered by the learner against the expected one.

Sample Dialogue

In this demo, the user will be able to interact with both dialogue systems, situated in the kitchen of a virtual world, and where the tutor prompts the learner with questions about meals, drinks, and various kitchen related activities such as floor cleaning and food preferences.

>S:

  FIGURE 1 -Example of a dialog (translated from French to English)


Fan Wenshan

Wang Bin

Paul Jean-Claude

Sun Jiaguang

An octree-based proxy for collision detection in large-scale particle systems

Keywords: particle systems, collision detection, octree-based proxy, GPU

Particle systems are important building block for simulating vivid and detail-rich effects in virtual world. One of the most difficult aspects of particle systems has been detecting collisions between particles and mesh surface. Due to the huge computation, a variety of proxy-based approaches have been proposed recently to perform visually correct simulation. However, all either limit the complexity of the scene, fail to guarantee non-penetration, or are too slow for real-time use with many particles. In this paper, we propose a new octree-based proxy for colliding particles with meshes on the GPU. Our approach works by subdividing the scene mesh with an octree in which each leaf node associates with a representative normal corresponding to the normals of the triangles that intersect the node. We present a view-visible method, which is suitable for both closed and non-closed models, to label the empty leaf nodes adjacent to nonempty ones with appropriate back/front property, allowing particles to collide with both sides of the scene mesh. We show how collisions can be performed robustly on this proxy structure in place of the original mesh, and describe an extension that allows for fast traversal of the octree structure on the GPU. The experiments show that the proposed method is fast enough for real-time performance with millions of particles interacting with complex scenes.

Introduction

Particle systems [START_REF] Reeves | Particle systems-a technique for modeling a class of fuzzy objects[END_REF][START_REF] Witkin | Physically based modeling: principles and practice[END_REF] have long played an essential role in simulating natural effects such as fire, smoke, and water in virtual environments. Although great progress has been made in simulating particle systems, interaction between a complex scene with arbitrary topology and a large number of particles in real-time remains an issue that has not yet been adequately solved.

The computational cost of simulating particle collision in a scene consisting of triangle meshes can be expensive, with a naive approach requiring tests between every particle and every triangle to compute collisions in a single frame. However, the fact that each particle's interaction with the scene is essentially independent would seem to make particle collisions suitable for computation on the GPU, on which many threads can independently calculate particle-scene collisions in parallel, greatly increasing performance.

Unfortunately, the traditional acceleration structures, such as grids, octrees, kd-trees and so on, that are typically used to accelerate performance on the CPU, do not naturally translate to the GPU context. The memory demand of these acceleration structures may impose too high of a cost for the GPU, and the non-uniform nature of some of these structures (e.g., the variable number of triangles in a leaf node of an octree) greatly harm the parallelism of SIMD GPUs, as all computation must wait for the worstcase number of tests required in any branch. Meanwhile, the efficiency is more important than physical accuracy when simulating particle-scene collisions in a lot of fields, these include computer games, movies, etc. Hence, various GPU-friendly proxies have been proposed to implement a fast and visually correct algorithm, such as texture-based depth maps [START_REF] Kolb | Hardware-based simulation and collision detection for large particle systems[END_REF], a lattice of planes [START_REF] Drone | Real-time particle systems on the GPU in dynamic environments[END_REF], but these approaches either limit the input geometry or fail to guarantee that particles will not penetrate the environment.

In this paper, a new object-space proxy for complex scenes is proposed that can accelerate collision processing on the GPU. The proposed proxy is based on an octree subdivision of the original model. The octree bounds the original model and is refined until it converges closely enough to the shape of the model to satisfy a set of termination criteria. Then, for each nonempty leaf node, a single representative normal is computed that is simply the average of the normals of the triangles that intersect the node. In addition, to deal with the issue of arbitrary distribution of particles in practical scene, a general viewvisible method for both closed and non-closed models is introduced to label empty leaves adjacent to nonempty ones with back/front property.

This proxy structure can then be uploaded to the GPU and used in place of the original mesh. During simulation, a particle that enters a nonempty leaf node of the proxy tests its velocity against the node's representative normal. If it is found that the particle is travelling in a direction opposed to the normal, then the particle is considered to be colliding with the model, and collision response is carried out based on the representative normal. Otherwise, the particle is allowed to continue on its path. Because a particle's velocity is always tested against a node's representative normal, this approach guarantees that the particle will not penetrate the surface.

Collisions with both sides of the mesh are handled by labelling particles as they pass through empty nodes adjacent to nonempty ones, marking them with appropriate property according to the empty node's back/front property. Then, when a particle encounters a nonempty leaf node, it simply processes collisions based on either the default or flipped version of the node's representative normal depending on whether it is in front or at back of the surface, respectively. Note that this approach sidesteps the issue of labelling all points in the scene volume as being at back or in front of the surface, which may be difficult or impossible for meshes with holes; instead, it only requires labelling nodes immediately adjacent to the surface of the mesh, which can be done robustly even on open meshes.

Finally, we describe how a lookup table that records all the nodes of the octree at a certain depth can be used to optimize the octree traversal process by beginning at a node deeper than the root, further accelerating collision detection on the GPU using this proxy. The result is a fast, flexible, and robust proxy for particle system collisions with arbitrary scene geometry.

Related work

Particle systems. Reeves [START_REF] Reeves | Particle systems-a technique for modeling a class of fuzzy objects[END_REF] first proposed the simulation of particle systems and the basic motion operations and data structures which are now familiar. It was quickly realized that the interactions between each particle and the scene are typically independent, making it possible to simulate each particle in parallel. Sims [START_REF] Sims | Particle animation and rendering using data parallel computation[END_REF] presented a technique to animate and render a particle system running on a parallel supercomputer. More recently, GPGPU methods have been employed [START_REF] Owens | A survey of general-purpose computation on graphics hardware[END_REF] to tackle the simulation of large particle systems. Latta [START_REF] Latta | Building a million particle system[END_REF] presented a full GPU implementation of a particle system, in which particles were encoded into textures on the GPU. Kipfer et al. [START_REF] Kipfer | UberFlow: a GPU-based particle engine[END_REF] proposed an approach to implement particle simulations on the GPU that was able to eliminate all data transfer between the GPU and CPU at runtime, removing a performance bottleneck. However, both of these approaches could only handle collisions between particles and a scene modeled by a height field.

Venetillo and Celes [START_REF] Venetillo | GPU-based particle simulation with inter-collisions[END_REF] proposed a way to represent a scene as a collection of basic primitives, such as planes, spheres, cones, and so on, to make collision processing simpler on the GPU. However, this approach does not support complex scenes.

In theory, a simplified (reduced polygon count) version of the input scene, as generated by any simplification method, could be employed as a proxy for the original complex mesh to generate approximate collision results. However, the deviation between the original mesh and the proxy tends to result in visual errors. Hence several more elaborate proxies have been presented.

Kolb et al. [START_REF] Kolb | Hardware-based simulation and collision detection for large particle systems[END_REF] proposed an implicit representation of the original mesh for collision detection in which a set of depth maps containing position and normal vectors at each point are precomputed and used to represent the outer boundary of the scene. However, their proxy is constrained to work only with closed models, and, as an image-based technique, has an accuracy that is dependent on the resolution of the depth map and the view direction.

Drone [START_REF] Drone | Real-time particle systems on the GPU in dynamic environments[END_REF] partitioned the scene into a uniform three-dimensional lattice with each nonempty cell containing an important plane corresponding to the surface of original scene. However, the memory requirements for a uniform three-dimensional grid are prohibitive for complex scenes. Furthermore, this approach can result in missing some collisions, causing particles to penetrate the scene.

Octrees. A general introduction to the spatial acceleration structure can be found in [START_REF] Glasner | Space subdivision for fast ray tracing[END_REF][START_REF] Macdonald | Heuristics for ray tracing using space subdivision[END_REF][START_REF] Samet | Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS[END_REF][START_REF] Scherson | Data structures and the time complexity of ray tracing[END_REF]. In a classical approach, an octree representation of a mesh would record a variable number of triangles in each leaf node. Benson and Davis [START_REF] Benson | Octree textures[END_REF] and DeBry et al. [START_REF] Debry | Painting and rendering textures on unparameterized models[END_REF] instead proposed storing a single representative color in each leaf node of an octree. Then, a fragment's position can be used as an index into the octree to directly determine the fragment's color, avoiding the complex problem of creating a 3D to 2D parameterization for texture mapping [START_REF] Hormann | Mesh parameterization: theory and practice[END_REF]. Lefebvre et al. [START_REF] Lefebvre | Proceedings of the 2007 symposium on Interactive 3D Graphics and Games[END_REF][START_REF] Lefebvre | GPU Gems 2: Octree Textures on the GPU[END_REF] ported the resulting octree texture onto GPU to improve performance. However, in their approach the root node was always used as the entrance node for each access pass. Castro et al. [START_REF] Castro | Statistical optimization of octree searches[END_REF] used a linear hash octree [START_REF] Warren | A parallel hashed octree N-Body algorithm[END_REF] as a representation and estimated deep entrance nodes using a cost function on the CPU to improve performance, but the accessing conflict of hash tables incurred a performance hit.

Constructing the octree-based proxy

The proposed proxy utilizes the convergence [START_REF] Bloomenthal | Polygonization of implicit surfaces[END_REF] of octree subdivision which conforms to the shape of the input mesh surface with the increase of the subdivision level. See Figure 1. However, different from general octree-based acceleration structure, in which each nonempty leaf node contains a set of triangles that intersect that node, we instead associate nonempty leaf nodes with a single representative normal. We also label empty nodes adjacent to nonempty ones with a back/front property recording whether they are at back or in front of the surface, which, as we later show, will enable us to support particles colliding with both sides of a mesh.

Octree subdivision

The construction of the basic octree structure proceeds in a typical fashion. The octree is first initialized to a single node consisting of a bounding box encompassing the entire scene, and a set of triangles that includes all the triangles in the scene. This node is then subdivided into eight child nodes, with each child node's bounding box being one-eighth of its parent's. An intersection test is then run between the parent's triangles and the child nodes' bounding boxes, and the triangles that intersect a child node's bounding box are assigned to that node.

This subdivision is carried on recursively until the following termination criteria are met:

• The current node doesn't contain any geometry.

• The predefined maximum subdivision depth d max is reached.

• The subdivision depth is greater than a predefined minimum depth d min and the normals of the triangles in the current node vary by less than a specified tolerance ε.A r e v i s e d L 2,1 metric [START_REF] Cohen-Steiner | Variational shape approximation[END_REF] is def- ined to estimate the normals' variance:

L 2,1 r = n i -n avg 2 , (1)
where

n avg = a i n i a i , (2)
n i is the normal of triangle i,a n da i is the area of triangle i.

The above subdivision process results in a generated octree, with each nonempty leaf node corresponding to a small patch of the input surface and containing a set of triangles with similar normals. At this point, rather than record all of the contained triangles, we simply record a single represent normal that approximates the normal of the surface over the corresponding patch by [START_REF] Witkin | Physically based modeling: principles and practice[END_REF].

Because the position of the nonempty leaf nodes corresponds to the shape of the surface, and the nodes' representative normals correspond to the normals of the surface along its boundary, the resultant octree is a good approximation of the original mesh for the purpose of particle collision detection.

However, on the one hand, just a single representative normal is recorded in each nonempty leaf node, and on the other hand, the particles may end up at both sides of the model surface, either because they were initially placed there, or because the scene geometry was not closed and a particle moved through the hole. If a particle that is at back of the surface collides with the scene geometry, collision detection and response must be carried out with a flipped version of the representative normal. Hence, it is essential to track at which side of the surface the particles lie, so that the correct version of the representative normal can be retrieved to process collisions. We will describe a general view-visible method to deal with the issue.

Labelling empty nodes

The traditional ray casting based odd-even test [START_REF] Haines | Point in polygon strategies[END_REF] can work well to query if a point is inside or outside the closed model. However, the appropriate side may be poorly defined for non-closed models with it. For example, different results may be generated depending on whether or not the test ray passes through a hole with the odd-even test.

We solve this by observing that particles only need to be determined as being at back or in front of the surface immediately before a collision with the scene geometry, and that although these properties may be poorly defined over the scene as a whole, they are easily defined in nodes immediately adjacent to the surface, by testing whether the triangles visible to the node have normals pointing towards the empty node (indicating that the empty node is in front of the surface) or away from it (indicating that t h en o d ei sa tb a c ko ft h es u r f a c e ) .

We therefore label all empty nodes of the proxy adjacent to nonempty ones as being at back or in front of the surface using a general view-visible method described below. Each particle then records a back/front property which is set as the particle passes through these labelled empty nodes. Because particles must always pass through empty nodes before they encounter the surface (see Figure 2(a)), this is guaranteed to happen before we need to determine a collision. Then, when the labelled particle does encounter the surface, the default or flipped version of the surface node's representative normal can be retrieved as appropriate.

Our view-visible method proceeds by considering each nonempty leaf node in turn, and labelling its adjacent empty leaf nodes as being at back or in front of the surface. Although a single empty leaf node may be adjacent to multiple nonempty leaf nodes, and therefore be labelled multiple times, all labellings should agree, making that not a problem. We now show how to do this for a single nonempty leaf node node i . The first thing that must be done is to determine which nodes are adjacent to node i and can be labelled. This task would be trivial if dealing with a regular lattice, but in an octree, a node may be adjacent to nodes that are of the same size, larger, smaller, or a combination. In our approach, rather than treat every possible configuration separately, we assume that there is a full set of 26 neighbors of the same size (as there would be in a regular lattice) and calculate what the centers of those nodes would be. We then take each center point and find the node at our depth or less that contains the given point, and store it as node j .A tt h i sp o i n t , we are dealing with a single adjacent node, and have just three cases to deal with: node j is a nonempty leaf node (highlight by purple dash line in Figure 2(a)), in which case it does not need to be processed; node j is a nonempty non-leaf (highlight by red dash line in Figure 2(a)), in which case it can be left for another neighbor of the node at its own depth (which must exist) to process; or node j is an empty node (highlight by yellow dash line in Figure 2(a)), either at the same depth or shallower, in which case it can be labelled using the method described below.

We now consider a nonempty node node i and an adjacent empty node node j . Our goal is to find a triangle in node i of which node j has an unobstructed "view" and determine node j 's back/front property based on the normal of that triangle. This is done by first constructing a line from a beginning point P b that is any point laying on a triangle in node i 's triangle set and is within the bounding box of node i to an end point P e that lies on the boundary shared by both the bounding boxes of node i and node j .W et h e n find all the triangles in node i that intersect this line, and take the one that is with the closest intersection to P e as the triangle that will determine node j 's back/front property (see Figure 2(b)). The dot product of this triangle's normal and the direction of the line determine whether the triangle is "facing" node j , and therefore whether node j is then at back or in front of the surface: if the dot product is positive (the normal and the line point in the same direction), node j is labelled as being in front of the surface; if it is negative, node j is labelled as being at back of the surface.

Algorithm 1 illustrates a high level framework of the proposed view-visible method. Figure 3 shows an example of a scene in which particles are colliding with both sides of a mesh, and how our approach supports non-closed meshes as well.

Collision detection between particles and the scene

We now describe how our proxy can be used to detect collisions between particles and the scene. We leave the details of the implementation of the particle system (such as whether explicit or implicit integration is used) unspecified, as our approach will work with any particle motion scheme. Figure 4 A 2D illustration of the interaction between particles and scene geometry. When a particle encounters a nonempty leaf node, it tests its velocity direction (black line) against the correct version of the node's representative normal (red line). If the particle is moving counter to the normal, a collision is detected and processed (particles A and C); if not, it continues on its path (particle B).

For each particle, we find the current position of the particle x t and the intended new position computed by the particle system dynamics x t+h . We then consider each of the nodes that the particle's path passes through in sequence. This process starts by setting the current node to the octree leaf node that contains the particle's start position. For each node, we run the test below, potentially update the planned path of the particle, find the point at which the particle exits the current node's bounding box (if it does) and use that position to query the proxy to find the next node. This repeats until the node containing the particle's end position is reached.

The test for each node is as follows:

• If the node is empty, the particle is allowed to continue on its path. If the empty node is flagged with a back/front property, we stamp the particle with the corresponding property.

• If the node is nonempty, we first retrieve either the default or flipped version of the node's representative normal, depending on whether the particle is stamped as being in front or at back of the surface, respectively, and label it n. We then calculate the dot-product n • v,w h e r ev is the velocity of the particle. If n • v 0, the particle is considered to be travelling away from the surface of the scene in this node, and the motion is unchanged. However, if n • v < 0, this is considered a collision, and we perform Figure 5 The encoding format of octree nodes. First Child Offset defines how far the parent node is from its first child in the texture, Nx, Ny and Nz define the representative normal. Child Mask identifies if the node has children and Kind Mask identifies the children as internal or leaf nodes if existing. Back/Front mask defines if the associated children are labelled as being at back or in front of the surface. Please see [START_REF] Lacoste | Appearance preserving octree-textures[END_REF] for the detailed encoding scheme. collision response at the point at which the particle entered the node and update the position and velocity as appropriate, which are used for further traversal.

Figure 4 illustrates the interaction between particles and scene geometry in our approach.

5 Querying the proxy on the GPU

In the previous section, we referred to accessing the leaf node of the octree that contains a desired query point. This operation is the core operation employed when using our proxy. In this section, we will describe an extension to speed up the operation on the GPU. The first task we face is encoding the pointer-based octree into a flat texture which can be uploaded to the GPU to exploit the efficiency of texture fetching. For this, we use the encoding scheme proposed by Lacoste et al. [START_REF] Lacoste | Appearance preserving octree-textures[END_REF] with modification by adding a back/front mask to define the associated empty children whether they are flagged as being at back or in front of the surface. Figure 5 illustrates the data that are written for each type of node used in our method.

Then, different from the usual querying method which always proceeds from the root node, we implement an optimized scheme that allows the octree traversal to begin at a deep entrance node, reducing the number of indirect accessing.

Our optimization works by constructing a lookup table for all the nodes of the octree at a single depth d. The lookup table is simply a 3D matrix of pointers D(i, j, k) with dimensions 2 d × 2 d × 2 d that maps index (i, j, k) to the position in the texture containing node data at which the octree node at index (i, j, k) and depth d is recorded. If octree subdivision at that position stopped at a depth shallower than d,t h e mapping simply points to the leaf node ancestor of the node that would exist at that position. The lookup table also records the depth of the pointed-to node, to enable the calculation of the correct-sized bounding box for the node when querying the proxy.

Once this lookup table has been constructed and uploaded to the GPU, octree traversal can start at depth d (or at a shallower leaf node if no node at that position and depth d exists) instead of at the root by looking up the node containing the query position at depth d in the lookup table.

In constructing this lookup table, there is a trade-off between speed and table size, as a lookup table at a deeper depth will save more of the traversal, but require more space. We use a depth of 5 for all of our experiments.

In a test scene composed of 1024 k particles with inter-collisions falling onto the Bunny model, we observed a speedup of 53% with the lookup table relative to without.

6R e s u l t s

Model statistics, proxy generation settings and algorithm timings are provided in Table 1. The performance of our proxy determines the collision detection time, which is given in milliseconds per frame. All timings were generated on an Intel Core 2 processor running at 2.8 GHz with 3 GB of main memory and an NVIDIA GeForce 260 GTX graphics card with 896 MB of video memory. The particle system was implemented using NVIDIA's CUDA framework [START_REF][END_REF]. The method presented by Green [26] was employed in our system for inter-collision test among particles. As Table 1 indicates that the proposed proxy is able to support large-scale particle system in real-time. Images of particle systems that we are able to simulate with the proposed proxy are given in Figure 6. Note that the construction of the proposed octree proxy takes all the triangles in the scene as a whole collection, hence just a single octree proxy is necessary when simulating a particle system. The advantage makes the complexity of our algorithm irrelevant to the number of models consisting of the scene, saving the additional rendering passes when processing complex system composed of multiple objects, such as Figure 6(b), as compared with the style of building proxy per model. The performance of our collision detection approach relative to a general octree acceleration scheme is given in Figure 7. The variable number of triangles in a leaf of the general octree imposes significant time and memory access penalties in the SIMD GPUs context, while our approach does not suffer from these effects. The result is a significant speed increase when using our proxy, especially with many particles, with only a minimal visual difference. Comparing performance with other optimized methods for particle system collision detection is more difficult, as they vary in the restrictions placed on scene geometry, correctness guarantees, computation platform, and so on.

Castro et al. [START_REF] Castro | Statistical optimization of octree searches[END_REF] presented an optimized method for octree traversal on the CPU that provided exact collision with the triangle mesh, but was far slower, achieving 4.1 FPS for a single particle interacting with the Buddha model.

Early GPU-based collision detection methods [START_REF] Latta | Building a million particle system[END_REF][START_REF] Kipfer | UberFlow: a GPU-based particle engine[END_REF] employed heightmaps to represent scenes, restricting their methods can only handle simple geometry, such as terrain. Kolb et al. [START_REF] Kolb | Hardware-based simulation and collision detection for large particle systems[END_REF] performed collision detection with an implicit representation. In order to approximate the boundary of scene geometry, they reconstructed a set of depth maps, encoding the position and normal vectors, from the original triangle mesh with an intricate method. Compared with their method, the construction of our octree-based proxy is simple. In addition, their implicit representation based algorithm cannot process non-closed models.

Drone [START_REF] Drone | Real-time particle systems on the GPU in dynamic environments[END_REF] proposed a uniform grid based method to detect collisions between particles and scene. They stored an important plane in each nonempty cell to approximate the mesh surface. Since only the triangles intersecting current cell are considered when building their important plane, the resultant proxy cannot ensure correct continuity among all cells, causing particles penetrate the scene in their method. Different from that, the converged octree structure is employed in our method to approximate the boundary of the scene geometry, removing the above issue, and the proposed optimized octree traversal scheme ensures good performance of our method.

Venetillo and Celes [START_REF] Venetillo | GPU-based particle simulation with inter-collisions[END_REF], meanwhile, presented a system capable of simulating 1024 K particles on the GPU at 6 FPS, but they limit the input geometry to a scene constructed by combining simple geometric primitives. To make a fair comparison, we tested our approach on a GPU of similar speed (an NVIDIA GeForce 8800 GT, relative to their slightly faster 8800 GTX), and were able to achieve 11.2 FPS on average with 1024 K particles on the Pegasus model.

Conclusion and future work

We have presented a novel proxy for complex meshes that can be used to perform collision detection for a large-scale particle system. We have shown how this proxy is suitable to being stored and run entirely on the GPU, allowing the real-time computation of collision detection for millions of particles. We have shown how our proxy can support collisions with both the sides of the geometry surface, and presented an optimization that increases the speed of octree traversal when computing collisions with our proxy.

As with all existing geometry proxies, our proxy performs only approximate collision detection with the scene geometry. In our case, the accuracy of our proxy is limited by the maximum subdivision level of the proxy's octree structure. Although the deviation between our proxy and actual scene geometry can be reduced by increasing the maximum subdivision level, both the memory requirement and the access overhead will increase. As a result, the problem may arise when processing models with some extreme cases, such as thin-plate and self-collision, in practical applications.

Currently, our octree-based proxy is initially constructed on the CPU as an offline procedure. However, it has been shown that octree construction can be performed on the GPU [START_REF] Zhou | Data-parallel octrees for surface reconstruction[END_REF][START_REF] Deng | Fast and dynamic generation of linear octrees for geological bodies under hardware acceleration[END_REF]; therefore, we would like to implement a dynamic constructing algorithm for our proxy on the GPU in order to support deformable models. We are also interested in exploring the possibility of employing the proposed view-visible method to solve other related issues, such as reconstruction on point cloud [START_REF] Yang | Adaptive triangular-mesh reconstruction by mean-curvature-based refinement from point clouds using a moving parabolic approximation[END_REF] for non-closed models.

Figure 1

 1 Figure 1 As the nodes of the octree are further subdivided, the nonempty leaf nodes (left three images) converge to the shape of the original model (rightmost image).

Figure 2

 2 Figure 2 View-visible method for labelling empty nodes. (a) The empty leaf nodes, which are at back (in green) or in front (in blue) of the mesh surface, must be traversed first before the particles approach to the scene mesh. The dash lines with different colors highlight all the possible cases when labelling empty leaf nodes adjacent to surface; (b) a line segment is drawn from a point P b on a triangle in the nonempty node to a point Pe shared by both nodes. The normal (in red) at the closest intersection (orange cross) of the line segment and the surface to Pe is used to determine the back/front property of the empty node.

Algorithm 1 Figure 3

 13 Figure3A scene demonstrating collisions with both sides of a mesh and support for non-closed meshes. The green particles were created inside the Bunny model and are interacting with the backside of the mesh surface and falling out of holes in the base of the mesh.

Figure 6

 6 Figure 6 Particle systems that can be simulated with our approach. (a) 1 M particles are colliding with the Pegasus model, shown in progression (a-d); (b) warriors stand in the sand. Instead of building a proxy per model, just a single octree proxy is necessary to detect the collisions between particles and geometry in this kind of scene that consists of multiple objects; (c) a spaceship is landing. The collisions, which result in the heat and light between the atmosphere and high speed aircraft, are calculated by the proposed octree proxy; (d) the Angel is in the waterfall. The octree proxy is used to simulate the interaction between the water and the model; (e) pegasus is flying in the cloud sea. The octree proxy is used to calculate the collisions between the cloud and the model.

9 Figure 7

 97 Figure7A comparison of the performance of our octree proxy based approach relative to that of a general octree accelerate scheme. The particles are tested colliding against the Horse model.

  Fan W S, et al. Sci China Inf Sci January 2013 Vol. 56 012104:8Ta bl e 1 Model statistics, octree proxy generation parameters and timings of our algorithm for detect collisions between

	particles and models
	Models	# Triangles	εd min	dmax	Size of proxy (MB)		Timings (ms)
							1 M Particles	2 M Particles	3 M Particles
	Horse	96966	0.01	4	6	0.06	17.5-26.3	21.9-33.1	22.4-40.1
	Angel	474048	0.02	5	6	0.05	19.4-25.3	21.1-33.4	22.5-39.8
	Pegasus	667474	0.01	5	6	0.11	19.5-24.5	22.1-36.1	23.7-40.7
	Dragon	871414	0.02	5	7	0.41	20.0-23.6	21.7-34.8	23.3-41.3
	Buddha	1087716	0.01	5	7	0.31	20.6-23.5	24.9-36.7	30.9-50.5
	Neptune	4007872	0.02	6	8	0.67	22.3-29.7	26.3-43.5	37.6-56.7

Acknowledgements This work was supported by National Basic Research Program of China (Grant No. 2010CB328001), National Natural Science Foundation of China (Grant Nos. 61003096, 51021140004), and National High-tech R&D Program of China (Grant No. 2009AA045201). We thank Alec Rivers for his helpful suggestions and ideas and editing work on the paper. The Bunny, Dragon and Buddha are courtesy of Stanford 3D Scanning Repository. The Pegasus is courtesy of AIM@SHAPE Repository. The Horse is courtesy of 3DScanCo. The Angle is courtesy of Cyberware, Inc. The Spaceship is courtesy of INRIA Gamma team research database and the Warrior is courtesy of Evermotion.