Outside Computation with Superior Functions

Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2936–2940 June 6–11, 2021. ©2021 Association for Computational Linguistics 2936 Outside Computation with Superior Functions Parker Riley and Daniel Gildea Department of Computer Science University of Rochester Rochester, NY 14627 Abstract We show that a general algorithm for efficient computation of outside values under the min- imum of superior functions framework pro- posed by Knuth (1977) would yield a subexpo- nential time algorithm for SAT, violating the Strong Exponential Time Hypothesis (SETH). 1 Introduction Weighted deduction systems are used in a number of NLP applications, including parsing for context- free grammars (Shieber et al., 1995; Sikkel, 1997; Nederhof, 2003; Eisner and Satta, 1999) and ma- chine translation (Melamed et al., 2004; Lopez, 2009). In these applications, the inside-outside al- gorithm enables efficient calculation of the total weight of all derivations passing through a specific item in the weighted deduction system by comput- ing tables of inside and outside values. Goodman (1999) develops a generalized inside-outside algo- rithm that can be used with any commutative semir- ing. Applying the sum-product semiring results in the standard inside-outside algorithm used as a subroutine in Expectation Maximization (Dempster et al., 1977). Applying the max-product semiring results in an efficient algorithm for finding, for ex- ample, the best tree that incorporates a specified constituent covering a specified span of the input string. The minimum of superior functions framework of Knuth (1977) is an alternative to the semiring framework for analyzing weighted deduction sys- tems. Knuth’s framework is more general than semirings in that it allows more general functions to be used for combining the weights of subderiva- tions. Knuth’s framework has the advantage that it allows for best-first search with a generalization of Dijkstra’s algorithm, as well as for A∗ search (Nederhof, 2003). Given that Knuth’s framework guarantees effi- cient inside computation, does it also guarantee w1: [A, i, j] w2: [B, j, k] FR(w1, w2): [S, i, k] Figure 1: A rule R for CFG parsing in weighted de- duction notation for production S → A B. The goal item for CFG parsing with start symbol S and sentence length n is [S, 0, n]. efficient outside computation, allowing for a gener- alized inside-outside algorithm? In this paper, we answer this question in the negative. We prove that a general algorithm for efficient outside computa- tion in this framework would imply the existence of a subexponential time algorithm for satisfiability of boolean formulas in conjunctive normal form (SAT), violating the Strong Exponential Time Hy- pothesis (SETH) (Impagliazzo and Paturi, 1999) which postulates that no such algorithms exist. This result may be counterintuitive, because one might expect efficient outside computation to be possible whenever efficient inside computation is possible. We believe this result to be the first formal hard- ness proof for outside computation in weighted deduction systems. 2 Background A weighted deduction system (Nederhof, 2003) has rules of the form X1,...,Xn Y where X1, …

Content truncated to 500 words