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

Abstract: When working with problems in natural language processing, we can find ourselves in situations where the traditional measurements of descriptive complexity are ineffective at describing the behaviour of our algorithms. It is easy to see why — the models we use are often general frameworks into which difficult-to-define tasks can be embedded. These frameworks can have more power than we typically use, and so complexity measures such as worst-case running time can drastically overestimate 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 dealing 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 running time and the error in a simple search algorithm, allowing for a much faster search than the NP-completeness of this problem would suggest.

## introduction natural language processing uses many algorithms 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 applications @xcite . if we look at problems, as opposed to algorithms, the task of training neural networks @xcite , sentence disambiguation in pcfgs and hmms @xcite , and solving cryptograms @xcite have even been shown to be np-complete. these results would seem to be at odds with the observation that we are able to actually perform these tasks. clearly, while np-completeness results are a necessary part of our understanding, they do not tell the whole story about our algorithms' behaviour. faced with the inadequacy of existing descriptive complexity measures to represent program operation, some researchers have resorted to empirical measures of performance (e.g. @xcite . unfortunately, empirical studies have their own pitfalls, and these are also difficult to address. specifically, 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 drastically. this, after all, is why we separate training and evaluation test sets. ultimately our analytic tools should work together with our empirical studies, in the sense that we should be able to give quantify how much program performance changes as we change our input distributions. this would allow us to circumscribe our guarantees of program performance; if those bounds are not met (e.g., if a program takes much longer than expected to run), we have evidence that the set of inputs did not comply with the distribution in the first place. the situation of nlp is a little more complicated, however. many of our algorithms include, implicitly or explicitly, probability distributions as part of their input. take for example a natural language parser. thirty years ago, these relied upon lexicalized pcfgs that explicitly assigned probabilities to different rules and word n-grams, whereas today, the distributions used by neural parsers avail themselves of distributions that are rather more implicit. but in both cases, the distributions are acquired by sampling training data. the aim of our research programme is to incorporate these distributions into our theoretical anal-yses of program performance. if we were to follow existing analyses of a program's dependence on textual input, we may choose to characterize that dependency as a function of the length of the distribution's description. uniform distributions, arguably the shortest to write, often ensure the worst program performance. indeed, there is plenty of evidence from statistics, information theory and other ai applications that a particular derivative characteristic of distributions which is systematically related to the length of their descriptions captures many aspects of this dependency: entropy. in this paper we take steps towards this goal by demonstrating how to link the run time of a specific inference problem, the most probable sentence (mps) problem for pcfgs @xcite , to the entropy of its input. while this is somewhat of a niche problem, it does provide a good demonstration of our approach. we will describe below in section 8 some other graphical models that this approach can be readily applied to. we start our analysis of the mps problem in section 3 by outlining the problem definition, the nphardness proof of the problem, and the main bound we are going to prove about it. in sections 4 and 5, we develop an analysis of the mps problem by showing how entropy, specifically, the conditional entropy of a parse tree given the words of a sentence, changes the running time of a simple search algorithm for the most probable tag sequence over that sentence. in section 6, we show that there is an inherent trade-off between accuracy and run time whose worst case is dictated by the pcfg sentence-to-tree entropy. finally, in section 7, we characterize the run time of our search when we hold our grammar constant and draw many sentences from it. ## previous work historically, most complexity results in computer science have dealt with worst-case complexity. a major nlp result in this vein has been the study by @xcite , which shows that the most probable parse problem (mpp) for pstsgs and the most probable sentence problem (mps) for both pstsgs and pcfgs are all np-complete. these problems can be thought of as renormalization over a graphical model, and have been studied further in several publications, including @xcite and @xcite . similar np-completeness results exist for the problem of finding the optimal word order for phrases in machine translation @xcite and for solving letter-substitution problems such as cryptograms @xcite . an argument could be made for average-case complexity @xcite as an alternative to what we are attempting here. average-case complexity is a step towards the type of results that we want, but it still has its shortcomings. in particular, an average case complexity analysis relies on the underlying distribution of inputs being known (and, usually, easy to work with) in advance. the distribution of choice is often naïvely uniform. in situations where the input distribution is defined by the problem task, or where it is actually defined as part of the input, the problem of how program behaviour changes with the distribution is not completely addressed. average-case complexity, moreover, does not give any sort of guarantee on program performance. within artificial intelligence, approximation results are perhaps a more natural approach to analysis. nearly all of these endeavour to establish a worst-case result, however, and in some cases, such as with markov logic networks and bayesian networks @xcite , it is hard even to approximate for probabilistic inference. what we want is the worst case, but not the worst distribution. we want the worst case for a typical distribution. a general framework for "probabilistic complexity" has been explored in @xcite , in which it is found that the calculation of values such as conditional probability can be intractable, even on an otherwise tractable distribution. on the other hand, attempts to give decompositions for large families of distributions into tractable bases, as described in @xcite , can be used to characterize input probabilities for which algorithms will often be efficient. what these papers do not do is explore how the task-specific aspects of a problem in a powerful model can shift an algorithm's complexity into a hard or easy part of the input space. a promising alternative approach to analyzing program complexity is to look at the smoothed complexity of an algorithm. in this paradigm, the complexity of an algorithm is not based on the worst input that an arbitrary adversary could choose for the problem. instead, the adversary is constrained by having a small error added to their inputs. the expected complexity of the resulting problem is then reported, and can often be much better than the usual worst case. this approach to complexity analysis is very effective for describing the behaviour of many otherwise exponential algorithms, such as the simplex algorithm @xcite or the k-means clustering algorithm @xcite . the major limitation of this approach for us, however, is that the improvement in performance is assumed to be due to measurement error in the input. such an assumption is very appropriate when talking about, for example, measurements taken of continuous real-world quantities like length. it is not likely to be appropriate for situations where the program improvement is due to observable regularities in the input data. what we really want to do is to exploit the fact that we see only a fragment of the theoretically possible input space in the real world. unfortunately, the task of identifying good problem fragments for our models is itself very hard, and so we will instead attempt to use statistical measures to build tools for narrowing down the space in which our inputs will lie. a start towards this goal is found for the letter-substitution problem in @xcite , but this approach does not give a tight enough bound to describe when we should expect better running times, and it does not immediately generalize to other tasks. we would like to strengthen the approach used in that paper to make it more applicable to different areas. with this in mind, we turn to another np-complete problem, the mps problem for pcfgs. ## tagging and np-completeness to start, we recall the definition of the problem: ## analysis of problem and exemplary algorithm we will use a similar approach to that used in @xcite , in that we will use an a * search to solve the mps problem for pcfgs. the idea behind the search is as follows: given a pcfg g and a string s of n words, we can find the overall probability p g (s) in g through a cubic time algorithm that algebraically mirrors a conventional all-paths parsing algorithm. but for our purposes, we can do it differently: given any instance w of a word in s, we can make a guess as to the pos tag r that w will take, and then run the algorithm, but with the restriction that only the tag r will be counted for w. in our earlier example of "time flies like an arrow," perhaps this would mean running the parser given the restriction that "time" is an adjective, while letting the other words take any tag that they can. clearly, this run of the parser will still take o(n 3 ) time, as it would if we simultaneously constrained any subsequence of the words of s rather than just one. recall that p g (s) is the sum of all p g (t), where t ranges over all trees with the yield of s. furthermore, if, for a subsequence of word instances (w u 1 , w u 2 , . . . , w u j ), we restrict the parser so that only the pos tags (r 1 , r 2 , . . . , r j ) will be considered, the probability calculated will be the sum of p g (t ), where t ranges over all trees with both have the yield of s and which have the desired pos tag restrictions. we will use this probability as an admissible heuristic in our a * priority queue, and consider possible sequences of tag assignments as nodes in the search space. we will refer to sequences of tag assignments with the character a, and we will index them by the letter i. sequences of tag assignments will not, in general, fix a tag for every word in s. to run the search, we fix an order for the words in s. we assume a last-to-first ordering here, but any ordering will suffice. we push an empty assignment {} with the score p g (s) onto a probability queue q. while q is nonempty, we pop its maximum element a i and look for the first word w u in our ordering of s which is not fixed by a i . for every possible pos tag r j for w u , we add the pos tag assignment {w u : r j } to a i to get a new sequence of tag assignments a to see that this a * search is correct, we first note that it must terminate: every time a tag assignment a is popped from the queue, either a fixes every word in s and the program terminates, or a series of strictly longer tag assignments a is added to the queue. furthermore, since our heuristic for a tag assignment sequence a is the sum of the probabilities of all suitably restricted trees t in g with yields of s, we can see that when we extend a tag assignment sequence a, we are simply adding new constraints to the contributing trees t, and so the set of trees counted is non-increasing. this means that the heuristic is also non-increasing. the same argument tells us that any extension of a tag assignment sequence a that fixes every word in s must have a probability that is at most that of s given a. these arguments, taken together, indicate that the first tag sequence found that fixes every word in s will be the one that gives the maximum probability, and so this assignment will give the solution to the mps problem. ## initial analysis in order to find the time complexity of this algorithm, recall the fact that the admissible heuristic is non-increasing. if we apply this to the first and last tag assignment sequences popped from the stack, we can see: similarly, if a is a tag sequence that is seen but not expanded in the search, so understanding the algorithm complexity becomes an issue of determining how many a are in this range. furthermore: lemma 5.2 if we extend a specific tag sequence a i in our search by one tag assignment into the new sequences a this just means that in our example sentence @xmath0," if we were to argue that "flies" can only be an n or a v, then the probability of s is the sum of the probability of s given that "flies" is a n plus the probability of s given that "flies" is a v. any of the parse trees that are compatible with one restriction are incompatible with the other, and so the outcomes in their probabilities are disjoint. in fact, since lemma 5.2 applies to every tag sequence we expand, we can go so far as to apply it iteratively to cover the whole search space: corollary 5.2.1 let qo be the selected optimal solution together with the items left stranded on q at the end of the search. then: let d * be the set of all a i such that every expansion of a i , a let d be the subset of qo consisting of every node with its parent in d * . every element of qo only has one parent node (no joins in the search space) because we always marshal out the tags of s in the order that we defined over its words. by corollary 5.2.1: then, by repeated applications of lemma 5.2 to the elements of d * : interestingly, the nodes of d * are the nodes that are the most complete assignment sequences that still satisfy p g (s|a) ≥ m g (s), from the first clause of lemma 5.1 -every node expanded in the search is either in d * or is an ancestor of a node in d * . it takes at most n -1 steps of expansion to arrive at this frontier, because every step assigns a tag to a new word of s, and there are at most |d * | such paths through the search space. so the total number of nodes expanded must be at most o(n|d * |). proof: we have just learned that for every finally, note that every one-word expansion in our search procedure comes with a decoding step that is bounded by o(n 3 ) time. thus we have: lemma 5.5 the running time for the entire search is o(r g (s)n 4 ). the proof by @xcite of overall npcompleteness implies that r g (s) can be exponentially large in n. his reduction exhibits a grammar which generates a single s with probability one, while the value of m g (s) is proportional to a threshold value, which is exponentially small in n. so in this degenerate case, the ratio r g (s) will always be exponentially large in the size of the grammar. in any case, determining r g (s) is the key to understanding the running time of our search. finding r g (s) is as difficult as finding m g (s), since we can use one to calculate the other. so we cannot directly use r g (s) in our calculations -we need a bound for it instead. clearly, given a positive lower bound for m g (s), l, then r g (s) ≤ p g (s)/l also. a very simple lower bound l is the most probable single parse tree t(s) for s, which can be calculated in o(n 3 ) time. clearly, the probability of t(s) is at most the probability of all trees with the same tag assignment as t(s), and this sum is itself at most the probability of the largest full tag assignment. thus: in the case of pure pcfg parsing, finding p g (s) also admits an o(n 3 ) algorithm, although the implicit sum over all possible trees includes a potentially infinite series over cycles of unary phrase structure rules. when this series converges, finding the probability mass added by these extra trees involves inverting a potentially large matrix that can be prohibitively expensive, although this cost is independent of the input length, and can be precomputed offline. ## a trade-off between accuracy and time practically, we may not want to run a full a * search, especially if the overall search takes a long time. the above analysis is a convenient starting point for investigating the consequences of stopping our search early. if we do decide to stop the a * search early, we will want to output a tag sequence. let this tag sequence be â(s). we will assume here that it is τ (s), the one associated with the most likely tree, t(s), which means that it can be calculated easily, and can easily be combined with any other estimate (just check both tag sequence estimates and take the better). the heuristic score of â(s) provides a lower bound on the probability of the most likely tag sequence, which may in fact not be â(s). as the search progresses, those scores will decrease, and so the range of values that the maximum probability can take on will also decrease. in particular, the error that we incur by simply choosing the tag sequence â(s) as our output will always be at most p g (a i )/p g (â(s)). given some @xmath1, let us run our a * search for n2 k iterations. we assert that: theorem 6.1 if we run our search for n2 k iterations, we will get a reduction in error of at least k bits, i.e., we achieve an overall reduction in error of at least 2 -k . proof: suppose otherwise. then, since p g (s|a i ) is the score of the latest partial solution on the queue after n2 k iterations, we have that p g (a * ) < p g (s|a i ), where a * is an optimal tag assignment. but, since the error that we incur by choosing ât is not reduced by at least 2 let q i be the partial tag sequence a i together with the items left stranded on q when we terminate the search. then, as we saw in corollary 5.2.1: furthermore, let d i and d i be defined analogously to d * and d from section 5. the arguments of lemma 5.3 still apply, so that this bound unfortunately does not tell us how the problem difficulty scales with the sentence length n, but it does give us a sense of how difficult the mps problem will be for a given grammar. while it is true that finding the exact values for either h g (t|s) or ν g (t|s) is undecidable for general pcfgs, these values are can be given rough bounds -for example h g (t|s) is bounded above by the tree entropy h g,n (t). finding better bounds is clearly an area for future research. further discussion of the variance of the tree entropy can be found in @xcite . ## other applications in this paper, we have only considered the mps problem, but the same approach can be applied to other inference problems, such as those found in bayesian networks or crfs. in particular, suppose that we are performing inference on a graphical model in which: if all of these conditions are met, then the a * search above will still solve the problem, and will admit the same analysis. if the probability of e with no constraints is p 0 (e) and the probability of e under the optimal constraints is p * (e), the ratio p 0 (e)/p * (e) will fill the same role as the ratio p g (s)/p g (t) in our above analysis, and can be used to create a similar entropic bound. the main difficulty lies in the time we take to find the probability p(e) given a set of constraints. this time will be application-dependent: in our case it took o(n 3 ) time. our current method will generalize to any task in which the p(e) value can be efficiently found. ## conclusions our analysis tells us something about how a particular np-complete problem -the mps problem for pcfgs -relates to a specific property of grammars. our worst case running time is o(n 4 2 n(h g,n (t|s)+ε) ) with high probability. slightly more promising is that, when we draw a sentence s, it will take at most 2 h g (t|s)+cν g (t|s) n 4 steps with probability 1 -δ, where ν is the second moment of the entropy and c depends on δ. if we perform early stopping on the search, the product of the running time with the error will have the same bound. more practically, if we can determine that the ratio p g (s)/p g (τ (s)) is small, our algorithm will have a much quicker run time. even in the worst-case scenario, the problem complexity collapses if we can break a sentence into several smaller instances. while we cannot do so in the grammar given by @xcite , it is possible in many nlp grammars. @xcite showed, for example, that we can find clause boundaries in sentences generated by the penn treebank grammar both quickly and reliably. future work should focus on formalizing this for the mps problem.