Language Generation via Combinatorial Constraint Satisfaction: A Tree Search Enhanced Monte-Carlo Approach

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1286–1298 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 1286 Language Generation via Combinatorial Constraint Satisfaction: A Tree Search Enhanced Monte-Carlo Approach Maosen Zhang†, Nan Jiang†, Lei Li‡, and Yexiang Xue† †Department of Computer Science, Purdue University, Indiana, USA ‡ByteDance AI Lab {maosen,jiang631,yexiang}@purdue.edu, lileilab@bytedance.com Abstract Generating natural language under complex constraints is a principled formulation towards controllable text generation. We present a framework to allow specification of combina- torial constraints for sentence generation. We propose TSMH1, an efficient method to gen- erate high likelihood sentences with respect to a pre-trained language model while sat- isfying the constraints. Our approach is highly flexible, requires no task-specific train- ing, and leverages efficient constraint satisfac- tion solving techniques. To better handle the combinatorial constraints, a tree search algo- rithm is embedded into the proposal process of the Markov chain Monte Carlo (MCMC) to explore candidates that satisfy more con- straints. Compared to existing MCMC ap- proaches, our sampling approach has a bet- ter mixing performance. Experiments show that TSMH achieves consistent and significant improvement on multiple language generation tasks. 1 Introduction Supervised techniques still dominate in natural lan- guage generation tasks. Despite its success, super- vised approaches need to be trained with massive datasets of input-output pairs, which is non-trivial to acquire. In addition, it is hard to guarantee that the output sentences satisfy constraints. Recent approaches first pre-train a language model on a general-purpose dataset, then fine-tune the neural net on a task-specific dataset (Devlin et al., 2019; Radford et al., 2019). These approaches partially mitigate data hunger in training large and flexible neural networks. Nevertheless, they still require carefully crafted datasets for fine-tuning. We present a constraint satisfaction driven ap- proach for language generation. In particular, we 1https://github.com/Milozms/TSMH 1 2 4 3 Sentence edit space Probability π(x) Paris is located in France. Paris is located in France. Paris located in France. Is Paris located in France? : Deletion TSMH 1 CGMH 2 4 3 Rejected Accepted Hard/soft constraints Pretrained LM Sampling Output sentence guide NLG via Constraint Satisfaction New input Input-output dataset Supervised training Output sentence Supervised (a) (b) Trained neural net Figure 1: (a) Natural language generation via con- straint satisfaction (bottom), comparing to supervised approach (up). (b) Our proposed tree search enhanced MCMC (TSMH, pink line) traverses the probabilistic space of high-quality sentences more effectively than the baseline (blue line). sample sentences that attain high likelihoods from a language model and satisfy task-specific con- straints. Sampling sentences that attain high likeli- hoods in the language model ensures the quality of the generated sentence. Constraints guarantee that the sentences fit the specific language task. The constraints can be hard ones such as the grammar rules, or soft ones such as attaining positive senti- ment scores. Our method harnesses constraint satisfaction, 1287 rather than learning, to guide language generation. In fact, there is no task-specific training in our approach. Our approach is highly flexible since constraints can be switched …

Content truncated to 500 words