Studies in Natural Language Processing Semantic processing for finite domains Studies in Natural Language Processing This series publishes monographs, texts, and edited volumes within the interdisciplinary field of computational linguistics. It represents the range of topics of concern to the scholars working in this increasingly important field, whether their background is in formal linguistics, psycholinguistics, cognitive psychology or artificial intelligence. Also in this series: Memory and context for language interpretation by Hiyan Alshawi Planning English sentences by Douglas E. Appelt Computational linguistics by Ralph Grishman Language and spatial cognition by Annette Herskovits Semantic interpretation and the resolution of ambiguity by Graeme Hirst Text generation by Kathleen R. McKeown Machine translation edited by Sergei Nirenburg Systemic text generation as problem solving by Terry Patten Machine translation systems edited by Jonathan Slocum Relational models of the lexicon edited by Martha Walton Evens Reference and computation by Amichai Kronfeld Semantic processing for finite domains MARTHA STONE PALMER National University of Singapore formerly Paoli Research Center, Unisys Corporation The right of the University of Cambridge to print and sell all manner of books was granted by Henry VIII in 1534. The University has printed and published continuously since 1584. CAMBRIDGE UNIVERSITY PRESS CAMBRIDGE NEW YORK PORT CHESTER MELBOURNE SYDNEY CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 2RU, UK Published in the United States of America by Cambridge University Press, New York www. Cambridge. org Information on this title: www.cambridge.org/9780521362269 © Cambridge University Press 1990 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 1990 This digitally printed first paperback version 2006 A catalogue record for this publication is available from the British Library Library of Congress Cataloguing in Publication data Palmer, Martha Stone. Semantic processing for finite domains / Martha Stone Palmer. p. cm. - (Studies in natural language processing) Includes bibliographical references. ISBN 0-521-36226-1 1. Semantics - Data processing. 2. Computational linguistics. I. Title II. Series. P325.5.D38P35 1990 401'.43'0285-dc20 89-77384 CIP ISBN-13 978-0-521-36226-9 hardback ISBN-10 0-521-36226-1 hardback ISBN-13 978-0-521-02403-7 paperback ISBN-10 0-521-02403-X paperback Contents List of figures page viii Acknowledgements ix 1 Problems in the semantic analysis of text i i. i Introduction i 1.2 The semantic representation of sentences 2 1.2.1 Examples using syntactic constituent and semantic role 3 1.2.2 The inherent difficulties in defining semantic representations 5 1.2.3 Mapping between syntactic constituents and semantic roles 7 1.2.4 The necessity of pragmatic information 11 1.3 The pulley domain 14 1.3.1 Input assumptions 15 1.3.2 Constraints on the desired output 15 1.4 Overview 17 1.4.1 The template approach 19 1.4.2 Inference-driven mapping 21 1.4.3 Implementation 28 2 Previous computational approaches to semantic analysis 30 2.1 Performing mappings before drawing inferences 33 2.1.1 Templates vs. procedures 33 2.2 The use of case in semantic analysis 40 2.2.1 Introducing case 40 2.2.2 Case as an intermediate level of representation 42 2.2.3 Combining case with generative semantics 47 2.2.4 Case as a deep level of semantic representation 51 2.2.5 Summary 58 2.3 An alternative to case 59 2.3.1 Thematic relations 60 2.3.2 Necessary capabilities for an alternative to case 62 2.3.3 Summary 65 3 A domain formalization 68 3.1 Introduction 69 vi Contents 3.2 Entities and their properties in the pulley domain 70 3.2.1 The typing of entities 72 3.2.2 Properties and parts 74 3.2.3 Summary 78 3.3 Lexical entries for verbs 78 3.3.1 Verb categories 80 3.4 Case predicates 88 3.4.1 Cause-motion AGENTS 88 3.4.2 Effect INTERMEDIARIES 90 3.5 Accommodating alternative syntactic realizations 92 3.5.1 Mapping constraints 93 3.5.2 Associating syntactic cues with predicate environments 96 3.5.3 Comparing lexical entries to templates 101 3.6 Filling semantic roles 107 3.6.1 Semantic constraints 107 3.6.2 Pragmatic constraints 109 3.6.3 Similarities between semantics and pragmatics 110 3.6.4 Summary no 4 Inference-driven mapping in 4.1 Analysis by synthesis 112 4.1.1 Overview 113 4.1.2 Procedural interpretation of lexical entries 114 4.1.3 Filling semantic roles 116 4.2 The processor in action 121 4.2.1 A simple example 122 4.2.2 Intermediary examples 128 4.3 Analyzing sentences in context 131 4.3.1 Algorithm for filling unfilled roles 132 4.3.2 Filling essential roles 133 4.3.3 Obligatory roles causing failure 145 4.3.4 Summary 146 5 Results of inference-driven semantic analysis 148 5.1 Integrated semantic analysis 148 5.1.1 Basic structure 149 5.2 Distinguishing between definitions and representations 158 5.2.1 Representing alternative syntactic realizations 159 5.2.2 The template approach 159 5.2.3 The inference-driven mapping approach 160 5.2.4 Causative forms 165 5.2.5 Summary 166 5.3 Future research 167 Contents vii 5.3.1 Integration of syntax with semantics 167 5.3.2 Transportability 169 5.4 Conclusion 171 Appendices A The pulley problems 174 B The interpreter 176 B.i Execution 177 B.2 Distributing plural noun groups 178 B.3 Function evaluation 179 C The syntactic, semantic, and pragmatic rules 182 D Verb, case, and relation definitions 188 E A worked example 192 References 197 Figures i. i Syntactic parse page 4 1.2 Basic structure of inference-driven mapping 22 2.1 "John gave the books to my brother" 41 2.2 "We killed dragons" 48 2.3 "Bert gave a boat to Ernie on his birthday" 49 2.4 "I sliced the meat with a knife" 54 2.5 Formula for a drink 56 3.1 Entity hierarchy 71 3.2 Quantity hierarchy 74 3.3 Illustrating hasprop links 75 3.4 "An entity contacts another entity" 95 3.5 "particlei contacts particle2" 95 3.6 "A particle is attached to another particle" 96 3.7 *"An entity is attached an entity" 97 3.8 "(Objecti) is attached to (Object 2) at (Locpti)" 103 3.9 "A particle is attached to a string .. ." 104 3.10 "An entity is attached to an entity at a point" 105 3.11 Adding the verb as a terminal node 105 4.1 Basic structure of inference-driven mapping 113 4.2 Filling a semantic role 118 4.3 "Instantiating OBJECTI (OI) and OBJECT2 (O2)" 124 4.4 "Instantiating LOCPT(LI)" 127 4.5 Algorithm for semantics 133 4.6 Deducing OBJECT2S from LOCPTS 136 4.7 ". .. and is offset by a particle of mass 8 pounds" 145 B. 1 Accessing the interpreter 176 B.2 The interpreter for the semantic processor 177 B.3 Alternative distributions of plural noun groups 178 B.4 Distributing plural noun groups 179 B.5 Choosing a syntactic constituent 181 vin Acknowledgements I have had so much help from so many people, that I could not begin to name them all. I do, however, want to thank many of my readers, especially David Warren, Fernando Pereira, Jerry Hobbs, Ellen Bard, Nigel Shadbolt, Graeme Ritchie, Lincoln Wallen, Leon Sterling, Mary Angela Papalaskaris, Luis Jenkins, and Julia Hirschberg. In particular I would like to thank Lew and Judie Norton and Carl Weir for their painstaking efforts in helping me turn the dissertation manuscript into something suitable for publication. In addition, I owe a special debt of gratitude to: Bob Simmons, for introducing me to the mysteries and challenges of natural language understanding. Rod Burstall, who saw so clearly what I was trying to do, and had such good ideas about how to do it. Bob Kowalski, for his unquenchable enthusiasm and delight in, what else, "logic for problem solving." Allen Biermann and the CS Department at Duke, for encouraging me and believing in me, and always making me laugh. Bonnie Webber, who pushed me when I needed pushing, and supported me when I needed supporting - and to all our friends at Penn for the many interesting discussions at La Terasse. Beth Levin and Mitch Marcus, for their patient reading, their ideas, and their understanding. Barbara Grosz, who performed the impossible task of getting me up, taking me to work, and sitting me in front of a terminal every day for six weeks - and to the Natural Language Group at SRI, for their suggestions, their disagreements, and their help. Jim Weiner, for his many valuable contributions, for his constructive criticisms, and for always being there. My examiners, Henry Thompson and Stephen Isard, for their careful reading and their high standards, and my supervisor, Alan Bundy, the Department of Artificial Intelligence, and the Faculty of Science at the University of Edinburgh, for their patience and tolerance during my somewhat checkered history as a post-graduate student. This work was supported by SRC grants B/SR/2293 and B/RG/94493 at the University of Edinburgh. ix