New Figures of Merit for Best-First Probabilistic Chart Parsing
Sharon A. Caraballo, Eugene Charniak · 1997
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 constituents, and the choice of this figure has a substantial impact on the efficiency of the parser. While several parsers described in the literature have used such techniques, there is little 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, and we identify an easily-computable figure of merit which provides excellent performance on various measures and two different grammars. 1 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 for which subtrees have been found, that is, constituents for which a derivation has been found and which may therefore appear in some complete parse of...