An Algorithm for VP Ellipsis

AN ALGORITHM FOR VP ELLIPSIS Daniel Hardt Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 Internet: hardt @linc.cis.upenn.edu ABSTRACT An algorithm is proposed to determine an- tecedents for VP ellipsis. The algorithm elim- inates impossible antecedents, and then im- poses a preference ordering on possible an- tecedents. The algorithm performs with 94% accuracy on a set of 304 examples of VP el- lipsis collected from the Brown Corpus. The problem of determining antecedents for VP el- lipsis has received little attention in the litera- ture, and it is shown that the current proposal is a significant improvement over alternative approaches. INTRODUCTION To understand an elliptical expression it is nec- essary to recover the missing material from sur- rounding context. This can be divided into two subproblems: first, it is necessary to determine the antecedent expression. Second, a method of recon- structing the antecedent expression at the ellipsis site is required. Most of the literature on ellipsis has concerned itself with the second problem. In this paper, I propose a solution for the first prob- lem, that of determining the antecedent. I focus on the case of VP ellipsis. VP ellipsis is defined by the presence of an auxiliary verb, but no VP, as in the following example 1: (1) a. It might have rained, any time; b. only - it did not. To interpret the elliptical VP "did not", the antecedent must be determined: in this case, "rained" is the only possibility. The input to the algorithm is an elliptical VP and a list of VP's occurring in proximity to the el- liptical VP. The algorithm eliminates certain VP's IAll examples are taken from the Brown Corpus unless otherwise noted. 9 that are impossible antecedents. Then it assigns preference levels to the remaining VP's, based on syntactic configurations as well as other factors. Any VP's with the same preference level are or- dered in terms of proximity to the elliptical VP. The antecedent is the VP with the highest prefer- ence level. In what follows, I begin with the overall struc- ture of the algorithm. Next the subparts of the algorithm are described, consisting of the elimina- tion of impossible antecedents, and the determina- tion of a preference ordering based on clausal rela- tionships and subject coreference. I then present the results of testing the algorithm on 304 exam- ples of VP ellipsis collected from the Brown Cor- pus. Finally, I examine other approaches to this problem in the literature. THE ALGORITHM The input to the algorithm is an elliptical VP(VPE), and VPlist, a list of VP's occurring in the current sentence, and those occurring in the two immediately preceding sentences. In addition, it is assumed that the parse trees of these sentences are available as global variables, and that NP's in these parse trees have been assigned indices to in- dicate coreference and quantifier binding. The antecedent selection function is: A-Select(VPlist,VPE) VPlist := remove-impossible(VPlist,VPE) VPlist := assign-levels(VPlist,VPE) antecedent. := select-highest(VPlist,VPE) First, impossible antecedents are removed …

Content truncated to 500 words