A Stochastic Approach to Sentence Parsing

A STOCHASTIC APPROACH TO SENTENCE PARSING Tetsunosuke FuJisaki Science Institute, IBM Japan, Ltd. No. 36 Kowa Building 5-19 Sanbancho,Chiyoda-ku Tokyo 102, Japan ABSTRACT A description will be given of a procedure to asslgn the most likely probabilitles to each of the rules of a given context-free grammar. The grammar devel- oped by S. Kuno at Harvard University was picked as the basis and was successfully augmented with rule probabilities. A brief exposition of the method with some preliminary results, whenused as a device for disamblguatingparsing English texts picked from natural corpus, will be given. Z. INTRODUCTION To prepare a grammar which can parse arbitrary sen- tances taken from a natural corpus is a difficult task. One of the most serious problems is the poten- tlally unbounded number of ambiguities. Pure syn- tactic analysis with an imprudent grammar will sometimes result in hundreds of parses. With prepositional phrase attachments and conjunc- tions, for example, it is known that the actual growth of ambiguities can be approximated by a Cat- fan number [Knuth], the number of ways to insert parentheses into a formula of M terms: 1, 2, 5, 14, 42, 132, 469, 1430, 4892, ... The five ambiguities in the following sentence with three ambiguous con- structions can be well explained wlth this number. [ I saw a man in a park with a scope. [ I ! This Catalan number is essentially exponentlal and [Martin] reported a syntactically amblguous sentence with 455 parses: List the sales of products produced in 1973 I I with the products produced in 1972. I On the other hand, throughout the long history of natural language understanding work, semantic and pragmatic constraints are known to be indispensable and are recommended to be represented in some formal way and to be referred to during or after the syntac- tic analysis process. However, to represent semantic and pragmatic con- straints, (which are usually domain sensitive) in a well-formed way is a very difficult and expensive task. A lot of effort in that direction has been expended, especially in Artificial Intelligence, using semantic networks, frame theory, etc. Howev- er, to our knowledge no one has ever succeeded in preparing them except in relatlvely small restricted domains. [Winograd, Sibuya]. Faced with this situation, we propose in this paper to use statistics as a device for reducing ambigui- ties. In other words, we propose a scheme for gram- matical inference as defined by [Fu], a stochastic augmentatlon of a given grammar; furthermore, we propose to use the resultant statistics as a device for semantic and pragmatic constraints. Wlthin this stochastic framework, semantic and pragmatic con- straints are expected to be coded implicitly in the statistics. A simple bottom-up parse referring to the grammar rules as well as the statistics will assign relative probabilities among ambiguous deri- vations. And these relative probabilities should be useful for filtering meaningless garbage parses because high probabilities will be asslgned to the parse trees corresponding to meaningful interpreta- tions and iow probabilities, hopefully 0.0, to …

Content truncated to 500 words