Detection and Resolution of Verb Phrase Ellipsis (2016)

Abstract: Verb phrase (VP) ellipsis is the omission of a verb phrase whose meaning can be reconstructed from the linguistic or real-world context. It is licensed in English by auxiliary verbs, often modal auxiliaries: She can go to Hawaii but he can’t [e]. This paper describes a system called ViPER (VP Ellipsis Resolver) that detects and resolves VP ellipsis, relying on linguistic principles such as syntactic parallelism, modality correlations, and the delineation of core vs. peripheral sentence constituents. The key insight guiding the work is that not all cases of ellipsis are equally difficult: some can be detected and resolved with high confidence even before we are able to build systems with human-level semantic and pragmatic understanding of text.

## introduction verb phrase (vp) ellipsis is the omission of a vp whose meaning can be reconstructed from the linguistic or real-world context. for example, the clause he could in (1) cannot be fully interpreted without reconstructing the elided vp as teach illiterate women to read and write. 1 (1) aid workers in war-ravaged kabul were stunned when a toddler from a poor family offered to teach illiterate women to read and writeand then promptly proved he could @xcite . ellipsis should be resolved by language processing systems because unresolved ellipses mask information that is available to a human reader. ellipsis has not been treated much by nlp systems. bos and spenader 2011 assess why: certainly, both of the subtasks of ellipsis processing -detection and resolution -can be very difficult, so it is unrealistic to expect a fullcoverage, near-term solution for open text. however, although some instances of vp ellipsis require human-level reasoning, not all are so difficult. in fact, it is possible to automatically detect which cases are simpler and resolve them with high precision, which is exactly what viper (vp ellipsis resolver) does. so, like many nlp systems, viper treats only a subset of instances; but unlike many systems, viper automatically selects the subset it knows how to treat and processes those instances fully automatically, without the need for manual corpus annotation. viper pursues string-level resolution of vp ellipsis, defined as copying the sponsor string to fill the elliptical gap. this is a midstream result toward full meaning analysis; and, as a midstream result, it has 1 in examples, elided categories are indicated by @xcite and their sponsors -i.e., the material used to recover their meaning -are italicized. we use the term "sponsor" rather than "antecedent" because "antecedent" has two unnecessary implications: that the sponsor is a linguistic entity, and that it precedes the referring expression. all numbered examples, except those labelled "invented", are from the gigaword corpus @xcite . although examples included in the evaluation could include mismatched punctuation -e.g., opening quotation marks that are not closed within the excerpt -we normalized such punctuation in order not to distract readers' attention with irrelevant details. some suboptimal features. first, sponsors for elided referring expressions -like sponsors for any referring expressions -are most accurately understood as disambiguated semantic entities rather than potentially ambiguous text strings. second, it can be impossible to select a text string that fully and precisely reflects the reconstructed meaning. for example in @xcite , a string-level reconstruction would be appeal the ruling, which is not directly available in the context. third, string-based resolution does not make the crucial semantic distinction between type-and instance-coreference between verbs, or strict and sloppy coreference between their internal arguments. 2 for example, in (3) the elided category actually refers to a different instance of sending a different set of children abroad than is presented in the sponsor clause. however, despite the global insufficiencies of a string-based approach, it offers three advantages. first, viper -or other implementations of the same approach -can be used right away since all necessary preconditions are fulfillable within the current state of the art. second, string-level resolution can be a useful end result for shallow nlp systems, offering a larger percentage of overt text strings for the systems to manipulate. finally, string-level resolution offers useful heuristic evidence for systems that pursue full semantic analysis. our approach to detecting treatable (meaning "treatable by viper") instances of vp ellipsis orients largely around syntactic simplicity. the hypothesis is that syntactically simple elliptical structures are easier to resolve than syntactically complex ones due to the limited number of verbal elements competing to serve as the sponsor. the following set of examples juxtaposes simple and complex contexts. example ( 4 ) is syntactically simple because the clause containing the sponsor occurs right before the ellipsis clause and there are no additional main verbs competing to be the sponsor. by contrast, both ( 5 ) and ( 6 ) contain multiple candidate sponsors. @xcite is truly difficult, even requiring significant concentration by a person reading the context. viper recognizes the complexity of such contexts and does not attempt to treat them. by contrast, ( 6 ) would fall into our simple category if the portion preceding the first comma were removed. viper carries out a series of syntactic tree trimming processes to render examples like (6) functionally simple and, therefore, treatable. once the sponsor clause has been identified, the next challenge is to determine the actual text elements contributing to the ellipsis reconstruction. for example, in (4) the modal element try to must be excluded from the sponsor; however, modals are sometimes included in sponsors. to handle modality during vp ellipsis resolution, viper uses an extended version of the microtheory of modality formulated within the theory ontological semantics @xcite . ontological semantics distinguishes ten types of modality, at least nine of which can license vp-ellipsis. 3 sample strings conveying each type of modality are: epistemic: did, didn't, will, won't; permissive: may, may not; epiteuctic: fail to; volitive: want to, not want to; obligative: must, must not, has to, doesn't have to; potential: can, can't, is not able to; evaluative: loves to, doesn't like to; intentional: intends to, doesn't intend to; effort: try to, not bother to. each modal meaning has a scope that represents the proposition to which the modal meaning applies. a proposition can be scoped over by many different types of modal meanings, as shown by ( 7 ), and multiple modalities can scope over a proposition, as shown by ( 8 ). viper carries out modality analysis to determine how the modal verbs in sponsor clauses should be handled during ellipsis resolution. for example, when the modalities in the sponsor clause and ellipsis clause are semantically paired, as with try to ... can, the sponsor-clause modality is excluded from the sponsor. the remainder of the paper describes how viper detects ellipsis (section 2), selects which instances it can treat (section 3), and determines the actual sponsor once the sponsor clause has been identified (section 4). we then report a system evaluation (section 5), place this contribution within the larger field (section 6), and describe ongoing and future work (section 7). ## ellipsis candidate detector detecting vp ellipsis can be tricky. although the simplest algorithm would be to seek instances of auxiliary verbs that are not directly followed by a verbal string that could serve as their complement, this can fail in at least three circumstances: when the auxiliary is separated from its complement by a parenthetical expression ( 9 ), when a string that looks like an auxiliary is actually functioning as a main verb (10), and when a string that looks like an auxiliary verb is actually a nominal @xcite . to handle these challenges, viper detects elliptical contexts using a three-stage process. all candidate examples that are not pruned out by these processes are considered elliptical, and viper must next determine which of them it will attempt to resolve. ## three resolution strategies viper uses three strategies to detect which instances of vp ellipsis it can resolve. these strategies are described in turn below. ## selecting the actual sponsor viper selects the actual sponsor from the already-detected sponsor clause by (a) determining whether matrix verbs (including modals) should be included in, or excluded from, the sponsor, and (b) determining whether internal arguments and adjuncts of the verbal head should be included in, or excluded from, the sponsor. we consider each of these subtasks in turn. matrix verbs in the sponsor clause -such as modals and aspectuals -can be be included in, or excluded from, the ellipsis reconstruction. viper's analysis of modal verbs is rather involved, as detailed in appendix c. in brief, if the modal verbs in the sponsor-clause and ellipsisclause are semantically paired -as defined by pre-recorded lists -the sponsor-clause modal verb is ex cluded from the ellipsis resolution; otherwise, it is included. by contrast, viper's treatment of non-modal matrix verbs is simple and straightforward, albeit not yet sufficiently sophisticated to guarantee the correct answer. if a non-modal matrix verb is the outermost verb in the structure, it is ex cluded from the sponsor (in (39) refused is excluded). by contrast, if a matrix verb is, itself, scoped over by another matrix verb, it is included in the sponsor (in (40) asked is excluded but stop is included). viper determines whether or not to include internal arguments and adjuncts in the ellipsis resolution as follows. all terminals subsumed by the sponsoring head in the parse tree are included in the resolution unless the elided category itself is among those terminals; in that case, the verbal head alone serves as the sponsor. this strategy is suboptimal on two counts. first, it is too simplistic, as we have not yet deeply studied this aspect of the problem. second, it is completely dependent upon the parser's treatment of the given argument or adjunct. in some cases, an argument or adjunct that should participate in the resolution is parsed as a sibling rather than a child of the verbal head. in such cases, the best viper can do is achieve "head correct" resolution status. clearly, this is a fertile area for further study. there are, of course, many other challenges in selecting the actual sponsor for elided vps, as detailed in the evaluation below. ## evaluation viper is a knowledge-based system that does not require an annotated corpus for training. in fact, we used human annotations only to evaluate whether viper had correctly resolved those instances of vp ellipsis that it chose to treat. by contrast, a full-scale annotation effort, like those used for the well-known system competitions, would have required creating a formal task definition, training annotators to follow it, and overseeing the work of those annotators -a formidable program of work that we did not undertake. instead, our goals in evaluating viper were (a) to have some measure of current system performance as a benchmark for future advances, and (b) to identify the specific challenges posed by this problem space. in this discussion, we will motivate all aspects of our rather novel evaluation suite. evaluation was carried out on the gigaword corpus, the same corpus used for linguistic investigation and algorithm development. although we did not initially divide the corpus into testing and evaluation portions, we believe that the evaluation is a fair representation of system functioning since (a) examples for the different stages of work were selected at random from this very large corpus, (b) we carried out no special tuning of our programs to cover specific examples, and (c) viper is not a statistically trained system. the evaluation proceeded according to the steps defined by the following subsections. ## related work reference and ellipsis have been treated in different ways within several fields. descriptive linguists, theoretical linguists, philosophers, and computational linguists wearing their theortical hats have offered theories that are difficult to implement, typically because they require prerequisites that remain beyond the state of the art. for example: hardt's @xcite ) system for treating vp ellipsis requires as input a perfect, manually corrected, parse; webber's @xcite ) theory of pronominal coreference requires full knowledge of discourse structure; the centering theory approach to pronominal coreference @xcite is difficult to operationalize due to problems in defining key concepts @xcite ; and virtually all work on strict vs. sloppy anaphora has been carried out in a theoretical paradigm that does not endeavor to render its findings computer-tractable. another source of work on reference -and less so, ellipsis -is mainstream nlp, which has treated a subset of overt referring expressions quite extensively. this subset is defined, details aside, as expressions whose sponsor is an overt, contiguous, coreferential np. the muc coreference task definition @xcite , which details these guidelines, has been very influential in guiding corpus annotation and subsequent system development in this domain for almost two decades. many machine learning methods, particularly supervised ones (see @xcite for an overview of methods brought to bear), have been applied to this task. but even state of the art systems like corenlp's reference resolver @xcite ) are struggling with some types of referring expressions, such as personal pronouns. as @xcite write: "the main conclusion of our error analysis ... is that the plurality of our errors are due to shallow knowledge of semantics and discourse. this result points to the crucial need for more sophisticated methods of incorporating semantic and discourse knowledge" @xcite . other high-level analyses of the state of the art in reference resolution can be found in @xcite , who share the opinion that the commonly adopted evaluation metrics lead to artificially inflated perceptions about where we stand in automating the processs of anaphora resolution. @xcite .. one of our goals in developing viper was to not simplify the problem in advance but, rather, to task the system with automatically detecting which instances it could treat. viper's focus on treating simpler instances of a difficult phenomenon resonates with baldwin's cogniac system @xcite . as concerns the supporting functionality of syntactic trimming, much of the past work has been in service of text summarization. for example, knight and marcu 2002 use a methodology that involves aligning sentences from a source document (called 'text') with sentences from manually generated abstracts of the document (called 'abstract'), then using @xmath0, @xmath1. gagnon and da sylva 2005 trim sentences based on a dependency parse, removing subtrees that represent certain types of relations, such as prepositional complements of the verb, subordinate clauses and noun appositions. perhaps the closest precedent to our approach is the one reported in @xcite , which applies five linguistically-informed trimming patterns. apart from summarization, sentence trimming has been applied to headline generation, event extraction, and subtitle generation. we did not use previously annotated corpora for system development or evaluation for two reasons. first, we knew that our methods would have relatively low recall; therefore, typical pre-annotation efforts would not have yielded a sufficient number of examples to test all of our linguistic hypotheses. second, using externally-prepared resources requires overhead. for example, bos and spenader 2011 remark about the annotations prepared by @xcite .. for at least the wsj files, the annotation is not easily reusable because it has been carried out on tokenized and parsed data, rather than on the texts in the form they are distributed by the ldc. this means that reusing the wsj annotations requires re-identifying each example in the raw texts" (p. 467). our approach to annotation was the fastest and most efficient way to support development and evaluation of viper. we would be happy to share any of our resources for research purposes. ## the big picture a natural question is, how frequent is vp ellipsis? we cannot answer that because there are no foolproof methods of automatically detecting elided categories, and counting manually would be impractical. but no matter the frequency of vp ellipsis, we believe that viper -or another implementation of its approach -could be useful in two ways. first, if applied to large corpora, it could treat at least some instances of vp ellipsis, which is better than treating none. second, ellipsis will be encountered by intelligent agents in all types of cognitive systems, such as our research group's ontoagent cognitive architecture @xcite . in fact, we are currently incorporating viper into the ontosem2 incremental semantic analysis system that provides language analysis capabilities to ontoagents. viper's output serves as heuristic evidence for full semantic reconstruction of elided vps. by year's end we expect to have reportable results of semantic vp-ellipsis resolution in ontosem2. in seeking approaches to treating truly difficult linguistic phenomena like reference and ellipsis, or the semantic analysis ultimately needed to inform them, we directly confront one of the biggest challenges of artificial intelligence: delineating a program of research and development that will result in fundamental solutions to hard problems while also offering useful, short-term results. we believe that it is essential that important problems of language analysis remain in purview even if currently preferred methods of system development cannot conveniently treat them. in fact, not only is there a place for goal-driven problem selection alongside the currently more prevalent method-driven strategy, the goal-driven approach highlights some of the most compelling problems posed by natural language, problems that will need to be solved as we move toward configuring truly intelligent artificial agents. semicolon or colon, it strips it off along with the preceding context and determines whether the remaining portion is a simple parallel configuration. if so, as in (67), it resolves the ellipsis. if not, as would be the case for the first encountered comma in (68), it continues its march backwards to the next punctuation mark and asks the same question. (69) {barak told israel tv that} the agents asked if he would help them in their investigation of the attacks if he could [e]. 4. strip pre-conjunction material. viper walks backwards through the text to the first encountered conjunction. if it is among our listed 28 conjunctions, foot_21 and if it takes verbal arguments in the dependency structure, then viper determines whether the latter conjunct is a simple parallel configuration. if yes, viper resolves the ellipsis. if not, it determines if adding another conjunct would result in a simple parallel configuration. for example, when encountering and in (70) viper will continue on, but when encountering because it will stop and strip off the preceding material and resolve the ellipsis. (70) {my legs make the serve because} you need to bend your knees and i couldn't [e]. the stripping rules were applied in the order listed. we did not attempt to optimize their ordering experimentally.