Reanalyzing the Most Probable Sentence Problem: A Case Study in Explicating the Role of Entropy in Algorithmic Complexity

Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics, pages 3354–3362 April 19 - 23, 2021. ©2021 Association for Computational Linguistics 3354 Reanalyzing the Most Probable Sentence Problem: A Case Study in Explicating the Role of Entropy in Algorithmic Complexity Eric Corlett Gerald Penn Department of Computer Science University of Toronto {ecorlett,gpenn}@cs.toronto.edu Abstract When working with problems in natural lan- guage processing, we can find ourselves in situations where the traditional measurements of descriptive complexity are ineffective at de- scribing the behaviour of our algorithms. It is easy to see why — the models we use are of- ten general frameworks into which difficult-to- define tasks can be embedded. These frame- works can have more power than we typi- cally use, and so complexity measures such as worst-case running time can drastically over- estimate the cost of running our algorithms. In particular, they can make an apparently tractable problem seem NP-complete. Using empirical studies to evaluate performance is a necessary but incomplete method of deal- ing with this mismatch, since these studies no longer act as a guarantee of good performance. In this paper we use statistical measures such as entropy to give an updated analysis of the complexity of the NP-complete Most Probable Sentence problem for pCFGs, which can then be applied to word sense disambiguation and inference tasks. We can bound both the run- ning time and the error in a simple search algo- rithm, allowing for a much faster search than the NP-completeness of this problem would suggest. 1 Introduction Natural Language Processing uses many algo- rithms that are theoretically intractable, but work well in practice. The k-means clustering algorithm, for example, has an exponential worst-case time, but is generally polynomial in practical applica- tions (Arthur et al., 2009). If we look at problems, as opposed to algorithms, the task of training neural networks (Blum and Rivest, 1993), sentence disam- biguation in pCFGs and HMMs (Sima’an, 2002), and solving cryptograms (Nuhn and Ney, 2013) have even been shown to be NP-complete. These results would seem to be at odds with the observa- tion that we are able to actually perform these tasks. Clearly, while NP-completeness results are a nec- essary part of our understanding, they do not tell the whole story about our algorithms’ behaviour. Faced with the inadequacy of existing descrip- tive complexity measures to represent program op- eration, some researchers have resorted to empiri- cal measures of performance (e.g. Carroll, 1994). Unfortunately, empirical studies have their own pit- falls, and these are also difficult to address. Specif- ically, empirical studies of program performance have an implicit dependence on the distribution of inputs used in the study. Changing this distribution of inputs can change the overall performance dras- tically. This, after all, is why we separate training and evaluation test sets. Ultimately our analytic tools should work to- gether with our empirical studies, in the sense that we should be able to give quantify how much pro- gram performance changes …

Content truncated to 500 words