Language Generation via Combinatorial Constraint Satisfaction: A Tree Search Enhanced M onte- C arlo Approach (2020)

Abstract: Generating natural language under complex constraints is a principled formulation towards controllable text generation. We present a framework to allow specification of combinatorial constraints for sentence generation. We propose TSMC, an efficient method to generate high likelihood sentences with respect to a pre-trained language model while satisfying the constraints. Our approach is highly flexible, requires no task-specific train- ing, and leverages efficient constraint satisfaction solving techniques. To better handle the combinatorial constraints, a tree search algorithm is embedded into the proposal process of the Markov Chain Monte Carlo (MCMC) to explore candidates that satisfy more constraints. Compared to existing MCMC approaches, our sampling approach has a better mixing performance. Experiments show that TSMC achieves consistent and significant improvement on multiple language generation tasks.

## introduction supervised techniques still dominate in natural language generation tasks. despite its success, supervised 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 @xcite . 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 approach for language generation. in particular, we sample sentences that attain high likelihoods from a language model and satisfy task-specific constraints. sampling sentences that attain high likelihoods 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 sentiment scores. our method harnesses constraint satisfaction, 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 quickly to be adapted to a different task, even faster than fine-tuning. it also allows us to leverage the latest developments of automated reasoning for language generation. although the field of language generation is dominated by learning, reasoning should play an equally important role. human beings can write beautiful words from reasoning over what is needed in the specific writing task, without learning from previous examples. to better handle the combinatorial constraints, a tree search is embedded into the proposal process of the markov chain monte carlo (mcmc) for constrained language generation, which suggests candidate proposals that satisfy more constraints. our approach is motivated by sample-search @xcite , which integrates backtrack search into importance sampling. making multiple word-level changes within one proposal step of mcmc allows the direct transition between legitimate sentences, while previous approaches must go through infeasible intermediate states. such moves are typically rejected by mcmc and therefore result in a slow mixing rate (see figure 1(b) and section 3.1). in literature, constrained language generation has been attacked in a supervised way in @xcite @xcite @xcite . there are also multiple works of literature which model language rules as decomposed tree structures @xcite or sentiment tags @xcite . markov logic network @xcite are also used to formulate grammar rules. the distance between vectors representing sentences meaning is considered as soft constraints in @xcite @xcite . in a nutshell, we summarize our contributions as follows: ## language generation via combinatorial constraint satisfaction we provide a general framework for the constrained natural language generation. in this framework, sentences are generated by sampling from a probability distribution that is proportional to the score of a pre-trained language model times the constraint score. formally, let x be a sentence, π(x) be the probability that x is sampled, then π(x) should be: here, p lm (x) is the score of a language model @xcite , which measures the quality of sentence x. higher p lm (x) means the sentence x is better in quality. constraint(x) is a task-specific penalty term. for example, in interrogative sentences generation, we would enforce constraint(x) to guarantee that only sentences in the interrogative form receive high scores. constraints are composed of hard and soft constraint terms: both the hard constraint score φ hard (x) and the soft constraint score φ soft (x) are float values ranging from 0 to 1. the closer to 1, the more satisfied the constraints are. unlike supervised methods which need to be trained with paired input-output data, our framework can solve language generation tasks without task-specific training. p lm (x) comes from a language model, only trained on general-purpose language tasks. there is no fine-tuning of p lm (x) on the specific task. φ hard (x) is based on crafted constraints. φ soft (x) comes from either user-defined functions, or pre-trained neural networks, which again is not fine-tuned on the specific task. the overall formulation composed of the language model and the task-specific constraints allows us to sample sentences which are close to natural language while satisfying constraints. ## tree search enhanced mcmc markov chain monte carlo (mcmc) is a classical approach to sample sentences from probability distribution π(x) as defined in equation 1. starting from one sentence x, mcmc moves to the next sentence x * by first generating a sample x * from the proposal distribution q(x * |x) and then accept x * with the following acceptance rate a(x * |x): if sentence x * is rejected, then the sample remains at x. the distribution of samples will converge to the sentence stationary distribution of markov chain π(x). previous work @xcite proposes to use mcmc for constrained sentence generation, namely cgmh algorithm. their proposal distribution only suggests sentences with one-word modification. nevertheless, cgmh cannot handle the combinatorial constraints in our problem definition, because of the low acceptance ratio problem caused by the locality of the proposal distribution. in other words, the sampling process can only visit a limited number of neighbors, thus the markov chain will easily be trapped at one infeasible state, resulting in a lot of rejections. we illustrate this problem in detail and hence motivate our tree search embedded mcmc approach using the following example. ## experiments we evaluate our approach on three applications: interrogative, imperative, and fixed sentiment sentences generation. in each task, we construct the specified type of sentences by sampling starting from keywords and enforcing task-specific constraints. for each task, we run our tsmh algorithm for 100 steps, with 100 candidate sentences generated. k is set to 3. since the tree search in tsmh considers changing 3 words at each iteration, we run the baseline cgmh for 300 steps as a comparison. we select the sentence with the highest π(x) value among the sentences generated by each algorithm as the output. our results are summarized in in general, our method tsmh outperforms baselines and generates sentences that satisfy more constraints, are of good quality and are likely to be close to the natural language. our main results are summarized in ## conclusions we propose a framework for constraint-driven language generation via sampling and combinatorial constraint satisfaction. our solution strategy is to sample sentences from the constrained space with probability proportional to the scores of the language model. to better handle the combinatorial constraints, a tree search is embedded into the proposal process of mcmc to suggest candidate proposals that satisfy more constraints. experiments demonstrate that our approach generates sentences that satisfy more constraints, are of good quality and are likely to be close in quality to the natural language.