Effective Inference for Generative Neural Parsing
Mitchell Stern Daniel Fried Dan Klein
cs.CL


Destruction of Refractory Carbon in Protoplanetary Disks
    Dana E. Anderson1, Edwin A. Bergin2, Geoffrey A. Blake1, Fred J. Ciesla 3, Ruud Visser 4, Jeong-Eun Lee 5 
    December 30, 2023
==============================================================================================================




Generative neural models have recently achieved state-of-the-art results for constituency parsing. However, without a feasible search procedure, their use has so far been limited to reranking the output of external parsers in which decoding is more tractable. We describe an alternative to the conventional action-level beam search used for discriminative neural models that enables us to decode directly in these generative models. We then show that by improving our basic candidate selection strategy and using a coarse pruning function, we can improve accuracy while exploring significantly less of the search space. Applied to the model of <cit.>, our inference procedure obtains 92.56 F1 on section 23 of the Penn Treebank, surpassing prior state-of-the-art results for single-model systems.




§ INTRODUCTION


A recent line of work has demonstrated the success of generative neural models for constituency parsing <cit.>. As with discriminative neural parsers, these models lack a dynamic program for exact inference due to their modeling of unbounded dependencies. However, while discriminative neural parsers are able to obtain strong results using greedy search <cit.> or beam search with a small beam <cit.>, we find that a simple action-level approach fails outright in the generative setting. Perhaps because of this, the application of generative neural models has so far been restricted to reranking the output of external parsers.

Intuitively, because a generative parser defines a joint distribution over sentences and parse trees, probability mass will be allocated unevenly between a small number of common structural actions and a large vocabulary of lexical items. This imbalance is a primary cause of failure for search procedures in which these two types of actions compete directly. A notion of equal competition among hypotheses is then desirable, an idea that has previously been explored in generative models for constituency parsing <cit.> and dependency parsing <cit.>, among other tasks. We describe a related state-augmented beam search for neural generative constituency parsers in which lexical actions compete only with each other rather than with structural actions. Applying this inference procedure to the generative model of <cit.>, we find that it yields a self-contained generative parser that achieves high performance.

Beyond this, we propose an enhanced candidate selection strategy that yields significant improvements for all beam sizes. Additionally, motivated by the look-ahead heuristic used in the top-down parsers of <cit.> and <cit.>, we also experiment with a simple coarse pruning function that allows us to reduce the number of states expanded per candidate by several times without compromising accuracy. Using our final search procedure, we surpass prior state-of-the-art results among single-model parsers on the Penn Treebank, obtaining an F1 score of 92.56.



§ COMMON FRAMEWORK





The generative neural parsers of <cit.> and <cit.> can be unified under a common shift-reduce framework. Both systems build parse trees in left-to-right depth-first order by

executing a sequence of actions, as illustrated in Figure <ref>. These actions can be grouped into three major types:
(X) and (X), which open and close a constituent with nonterminal X,[The model described in <cit.> has only a single action, whereas the model described in <cit.> annotates (X) actions with their nonterminals. We present the more general version here.] respectively, and (x), which adds the word x to the current constituent. The probability of an action sequence (a_1, …, a_T) is 

    P(a_1, …, a_T)
         = ∏_t=1^T P(a_t | a_1, …, a_t-1) 
       = ∏_t=1^T    [softmax(𝐖𝐮_t + 𝐛)]_a_t ,

where 𝐮_t is a continuous representation of the parser's state at time t, and [𝐯]_j denotes the jth component of a vector 𝐯. We refer readers to the respective authors' papers for the parameterization of 𝐮_t in each model.


In both cases, the decoding process reduces to a search for the most probable action sequence that represents a valid tree over the input sentence. For a given hypothesis, this requirement implies several constraints on the successor set <cit.>; e.g., (x) can only be executed if the next word in the sentence is x, and (X) cannot be executed directly after (X).



§ MODEL AND TRAINING SETUP


We reimplemented the generative model described in <cit.> and trained it on the Penn Treebank <cit.> using their published hyperparameters and preprocessing. However, rather than selecting the final model based on reranking performance, we instead perform early stopping based on development set perplexity. We use sections 2-21 of the Penn Treebank for training, section 22 for development, and section 23 for testing. The model's action space consists of 26 matching pairs of and actions, one for each nonterminal, and 6,870 actions, one for each preprocessed word type. While we use this particular model for our experiments, we note that our subsequent discussion of inference techniques is equally applicable to any generative parser that adheres to the framework described above in Section <ref>.



§ ACTION-LEVEL SEARCH




Given that ordinary action-level search has been applied successfully to discriminative neural parsers <cit.>, it offers a sensible starting point for decoding in generative models. However, even for large beam sizes, the following pathological behavior is encountered for generative decoding, preventing reasonable parses from being found. Regardless of the sequence of actions taken so far, the generative model tends to assign much higher probabilities to structural and actions than it does lexical actions, as shown in Figure <ref>. The model therefore prefers to continually open new constituents until a hard limit is reached, as the alternative at each step is to take the low-probability action of shifting the next word. The resulting sequence typically has much lower overall probability than a plausible parse, but the model's myopic comparison between structural and lexical actions prevents reasonable candidates from staying on the beam. Action-level beam search with beam size 1000 obtains an F1 score of just 52.97 on the development set.



§ WORD-LEVEL SEARCH



The imbalance between the probabilities of structural and lexical actions suggests that the two kinds of actions should not compete against each other within a beam. This leads us to consider an augmented state space in which they are kept separate by design, as was done by <cit.>. In conventional action-level beam search, hypotheses are grouped by the length of their action history |A|. Letting A_i denote the set of actions taken since the ith shift action, we instead group hypotheses by the pair (i, |A_i|), where i ranges between 0 and the length of the sentence.

Let k denote the target beam size. The search process begins with the empty hypothesis in the (0, 0) bucket. Word-level steps are then taken according to the following procedure for i = 0, 1, …, up to the length of the sentence (inclusive). Beginning with the (i, 0) bucket, the successors of each hypothesis are pooled together, sorted by score, and filtered down to the top k. Of those that remain, successors obtained by taking an or action advance to the (i, 1) bucket, whereas successors obtained from a action are placed in the (i+1, 0) bucket if i is less than the sentence length, or the completed list if i is equal to the sentence length. This process is repeated for the (i, 1) bucket, the (i, 2) bucket, and so forth, until the (i+1, 0) bucket contains at least k hypotheses. If desired, a separate word beam size k_w < k can be used at word boundaries, in which case each word-level step terminates when the (i+1, 0) bucket has k_w candidates instead of k. This introduces a bottleneck that can help to promote beam diversity.



Development set results for word-level search with a variety of beam sizes and with k_w = k or k_w = k/10 are given in Table <ref>. We observe that performance in both cases increases steadily with beam size. Word-level search with k_w = k/10 consistently outperforms search without a bottleneck at all beam sizes, indicating the utility of this simple diversity-inducing modification. The top result of 92.93 F1 is already quite strong compared to other single-model systems.



§ FAST-TRACK CANDIDATE SELECTION





The word-level beam search described in Section <ref> goes one step toward ameliorating the issue that causes action-level beam search to fail, namely the direct competition between common structural actions with high probabilities and low-frequency shift actions with low probabilities. However, the issue is still present to some extent, in that successors of both types from a given bucket are pooled together and filtered down as a single collection before being routed to their respective destinations. We therefore propose a more direct solution to the problem, in which a small number k_s ≪ k of successors are fast-tracked to the next word-level bucket before any filtering takes place. These fast-tracked candidates completely bypass competition with potentially high-scoring or successors, allowing for higher-quality results in practice with minimal overhead. See Figure <ref> for an illustration.



We repeat the experiments from Section <ref> with k_s = k/100 and report the results in Table <ref>. Note that the use of fast-tracked candidates offers significant gains under all settings.

The top result improves from 92.93 to 93.18 with the use of fast-tracked candidates, surpassing prior single-model systems on the development set.



§ ACTION PRUNING


At any point during the trajectory of a hypothesis, either 0 or all 26 of the actions will be available, compared with at most 1 action and at most 1 action. Hence, when available, actions comprise most or all of a candidate's successor actions. To help cut down on this portion of the search space, it is natural to consider whether some of these actions could be ruled out using a coarse model for pruning.



 §.§ Coarse Model


We consider a class of simple pruning models that condition on the c ≥ 0 most recent actions and the next word in the sentence, and predict a probability distribution over the next action. In the interest of efficiency, we collapse all actions into a single unlexicalized action, significantly reducing the size of the output vocabulary.

The input 𝐯_t to the pruning model at time t is the concatenation of a vector embedding for each action in the context (a_t-c, a_t-c+1, …, a_t-1) and a vector embedding for the next word w:

    𝐯_t = [𝐞_a_t-c; 𝐞_a_t-c+1; …; 𝐞_a_t-1; 𝐞_w],

where each 𝐞_j is a learned vector embedding.
The pruning model itself is implemented by feeding the input vector through a one-layer feedforward network with a ReLU non-linearity, then applying a softmax layer on top:

    P(a_t = a | a_1, …, a_t-1, next-word = w) 
       = P(a_t = a | a_t-c, …, a_t-1, next-word = w) 
       = [softmax(𝐖_2 max(𝐖_1 𝐯_t + 𝐛_1, 0) + 𝐛_2)]_a .

The pruning model is trained separately from the main parsing model on gold action sequences derived from the training corpus, with log-likelihood as the objective function and a cross entropy loss.



 §.§ Strategy and Empirical Lower Bound


Once equipped with a coarse model, we use it for search reduction in the following manner. As mentioned above, when a hypothesis is eligible to open a new constituent, most of its successors will be obtained through actions. Accordingly, we use the coarse model to restrict the set of actions to be explored. When evaluating the pool of successors for a given collection of hypotheses during beam search, we run the coarse model on each hypothesis to obtain a distribution over its next possible actions, and gather together all the coarse scores of the would-be successors. We then discard the successors whose coarse scores lie below the top 1 - p quantile for a fixed 0 < p < 1, guaranteeing that no more than a p-fraction of successors are considered for evaluation. Taking p = 1 corresponds to the unpruned setting.

This strategy gives us a tunable hyperparameter p that allows us to trade off between the amount of search we perform and the quality of our results. Before testing our procedure, however, we would first like to investigate whether there is a principled bound on how low we can expect to set p without a large drop in performance. A simple estimate arises from noting that the pruning fraction p should be set to a value for which most or all of the outputs encountered in the training set are retained. Otherwise, the pruning model would prevent the main model from even recreating the training data, let alone producing good parses for new sentences.



To this end, we collect training corpus statistics on the occurrences of inputs to the pruning function and their corresponding outputs.

We then compute the number of unique actions associated with inputs occurring at least 20 times, and restrict our attention to inputs with at least one output. The resulting cumulative distributions for context sizes c = 0, 1, 2 are given in Table <ref>. If we require that our pruning fraction p be large enough to recreate at least 99% of the training data, then since there are 26 total nonterminals, approximate[These thresholds are not exact due to the fact that our pruning procedure operates on collections of multiple hypotheses' successors at inference time rather than the successors of an individual hypothesis.] lower bounds for p are
10/26 ≈ 0.385 for c = 0, 7/26 ≈ 0.269 for c = 1, and 6/26 ≈ 0.231 for c = 2.




 §.§ Pruning Results




We reran our best experiment from Section <ref> with an order-2 pruning function and pruning fractions p = 6/26, …, 11/26. The results are given in Table <ref>. We observe that performance is on par with the unpruned setup (at most 0.1 absolute difference in F1 score) for p as low as 8/26 ≈ 0.308. Setting p to 7/26 ≈ 0.269 results in a drop of 0.18, and setting p to 6/26 ≈ 0.231 results in a drop of 0.40. Hence, degradation begins to occur right around the empirically-motivated threshold of 6/26 given above, but we can prune 1 - 8/26 ≈ 69.2% of successors with minimal changes in performance.



§ FINAL RESULTS AND CONCLUSION




We find that the best overall settings are a beam size of k = 2000, a word beam size of k_w = 200, and k_s = 20 fast-track candidates per step, as this setup achieves both the highest probabilities under the model and the highest development F1. We report our test results on section 23 of the Penn Treebank under these settings in Table <ref> both with and without pruning, as well as a number of other recent results. We achieve F1 scores of 92.56 on the test set without pruning and 92.53 when 1 - 8/26 ≈ 69.2% of successors are pruned, obtaining performance well above the previous state-of-the-art scores for single-model parsers. This demonstrates that the model of <cit.> works well as an accurate, self-contained system. The fact that we match the performance of their reranking parser using the same generative model confirms the efficacy of our approach. We believe that further refinements of our search procedure can continue to push the bar higher, such as the use of a learned heuristic function for forward score estimation, or a more sophisticated approximate decoding scheme making use of specific properties of the model. We look forward to exploring these directions in future work.



§ ACKNOWLEDGMENTS


MS is supported by an NSF Graduate Research Fellowship. DF is supported by an NDSEG fellowship.


emnlp_natbib

