Figures of Merit for Best-First Probabilistic Chart Parsing

Figures of Merit for Best-First Probabilistic Chart Parsing Sharon A. Caraballo and Eugene Charniak Brown University { SO, ec}Ocs, brown, edu Abstract Best-first parsing methods for natural language try to parse efficiently by considering the most likely constituents first. Some figure of merit is needed by which to compare the likelihood of con- stituents, and the choice of this figure has a sub- stantial impact on the efficiency of the parser. While several parsers described in the literature have used such techniques, there is no published data on their efficacy, much less attempts to judge their relative merits. We propose and evaluate several figures of merit for best-first parsing. Introduction Chart parsing is a commonly-used algorithm for parsing natural language texts. The chart is a data structure which contains all of the constituents which may occur in the sentence being parsed. At any point in the algorithm, there exist con- stituents which have been proposed but not ac- tually included in a parse. These proposed con- stituents are stored in a data structure called the keylist. When a constituent is removed from the keylist, the system considers how this constituent can be used to extend its current structural hy- pothesis. In general this can lead to the creation of new, more encompassing constituents which them- selves are then added to the keylist. When we are finished processing one constituent, a new one is chosen to be removed from the keylist, and so on. Traditionally, the keylist is represented as a stack, so that the last item added to the keylist is the next one removed. Best-first chart parsing is a variation of chart parsing which attempts to find the most likely parses first, by adding constituents to the chart in order of the likelihood that they will appear in a correct parse, rather than simply popping con- stituents off of a stack. Some figure of merit is assigned to potential constituents, and the con- stituent maximizing this value is the next to be added to the chart. 127 In best-first probabilistic chart parsing a prob- abilistic measure is used. In this paper we con- sider probabilities primarily based on probabilistic context-free grammars, though in principle other, more complicated schemes could be used. Ideally, we would like to use as our figure of merit the conditional probability of that con- stituent, given the entire sentence, in order to choose a constituent that not only appears likely in isolation, but maximizes the likelihood of the sen- tence as a whole; that is, we would like to pick the constituent that maximizes the following quantity: i P(N~,klto,~) where to,n is the sequence of the n tags, or parts of speech, in the sentence (numbered to,..., tn- 1), and Nj, k is a nonterminal of type i covering terms tj...tk_l. However, we cannot calculate this quantity, since in order to do so, we would need to completely parse the sentence. In this paper, we examine the performance of several proposed figures of merit that …

Content truncated to 500 words