{'fraction_non_alphanumeric': 0.03150212580763952, 'fraction_numerical': 0.00783368484483278, 'mean_word_length': 4.7813044319721305, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Language Generation via Combinatorial Constraint Satisfaction: A Tree Search Enhanced Monte-Carlo Approach

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 TSMH, 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 training, 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 TSMH 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 (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 approach for language generation. In particular, we 1 https://github.com/Milozms/TSMH 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.
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 Dechter, 2007a,b, 2011), 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 (Sutskever et al., 2014;Berglund et al., 2015;Hu et al., 2017;Zhang et al., 2019;Miao et al., 2020). There are also multiple works of literature which model language rules as decomposed tree structures  or sentiment tags (Su et al., 2018). Markov Logic network (Richardson and Domingos, 2006;Khot et al., 2015) are also used to formulate grammar rules. The distance between vectors representing sentences meaning is considered as soft constraints in (Prabhumoye et al., 2018;Belanger and McCallum, 2016;Amato and Mac-Donald, 2010). In a nutshell, we summarize our contributions as follows: 1. We define the problem of constraint satisfaction driven natural language generation, and propose a sampling-based approach to tackle the problem with combinatorial constraints. 2. We propose a Tree Search enhanced Metropolis-Hastings approach (TSMH) for the proposed task, which mixes faster than standard MCMC in the presence of combinatorial constraints. 3. Experiment results on generating interrogative, imperative sentences with keywords, and sentences with given sentiments demonstrate that our TSMH is able to generate sentences that satisfy more hard and soft constraints as well as retain good quality.

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 (Sundermeyer et al., 2012;Radford et al., 2019), 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.

Hard Constraints
In this paper, we use propositional logic to define hard constraints Φ hard (x). Nevertheless, our sampling approach generalizes to other logic forms. We leave the generalization to first-order logic as future work. For hard constraints, we define Φ hard (x) as where c i (x) is an indicator variable which takes 1 if the sentence x satisfies the i-th constraint, and M is the total number of hard constraints. β is between 0 and 1. We use quite small β values in our experiments, which put a large penalty on violating one hard constraint. We also define Constraint Error C(x) as the number of hard constraints a sentence violates, i.e., C(x) = M − i c i (x). Constraints are defined in the logical form of word categories. Word Category Division We divide the entire vocabulary into several categories of words. Given vocabulary set U , we partition U into nonoverlapping subsets: = true if and only if the first word in sentence is a wh-like word. For sentence-level constraints, we can define them 2 As we conduct sampling for the sentence, sentence length is pre-known and we set m as the length of the longest one. using propositional logic over w V j i (and (∧), or (∨), not (¬)). We give a few examples below. Enforcing Keywords in a Sentence Given one keyword K, we can enforce its existence in the sentence using the following constraint: here [K] is a set containing the keyword K. We formulate this constraint assuming a known sentence length m. Indeed, length m is a variable and can vary over the sampling procedure. Nevertheless, as we can see shortly in the sampling process, the lengths are known for both sentences when transiting from one sentence to another. Therefore, the semantic meaning of m is clear during sampling. Details on the sampling process is in Section 3.2.
Enforcing Imperative Sentence According to the definition in (Aarts, 1989), the starting word of an imperative sentence should be either a verb: 1 or an adverb followed by a verb: . We encode such constraint as: Enforcing Interrogative Sentence We use the following two constraints to enforce the sentence to be interrogative: (i) The first word is in [QWH].
(ii) The second or third word in the sentence is in [AUX]. (i, ii) can be written together as: This constraint is similar to the definition in (Zhang et al., 2017). We acknowledge that this is a relaxed constraint. Nevertheless, our sampling approach also consider the score from language model. These constraints accompanied with the language model guide us to good interrogative sentences in practice.

Soft Constraints
A soft constraint assigns a float value between 0 and 1 to indicate how the constraint is satisfied. For tasks with only hard constraints, Φ soft (x) is set to 1.0. Soft constraints can be derived quite flexibly. It can be from a user-defined function (see "sentence similarity" for an example), or from a pre-trained neural network (see "sentiment score"): Sentence Similarity We can define a soft constraint function ensuring that the generated sentence x is close to the reference sentence y in semantic meaning. For one word in sentence x, we first find the closest word in sentence y by computing their cosine similarity. Then either the minimum or the average of these words' cosine similarity is taken as the similarity score for sentence x and y. Sentiment Score We can enforce that the generated sentence must have a given sentiment by enforcing the value for the sentence from a sentiment analysis model. The output score of a sentiment analysis neural net represents whether the sentence has a positive or negative sentiment. We use this score as a soft constraint to control the sentiment of generated sentence with positive or negative attitude. Notice that the sentiment analysis neural net is pretrained on a separate dataset and remains intact in our framework.
This setup gives us additional flexibility. To be specific, if we need to generate sentences that contain keywords while having a given sentiment, it is difficult to find a large dataset of this type and the performance of a pure learning approach may be limited. To summarize, the main attribute of the constraint satisfaction framework is allowing a formulation using both hard and soft constraints, without the need of task-specific training or tuning.

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  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.

Motivation: Breaking the low acceptance barrier
Suppose we need to generate a question, whose answer comes from an underlined part of a sentence. For example, suppose we underline France in the sentence: A: Paris is located in France. The question we would like to generate is: B: Which country is Paris located in? Under our constraint satisfaction framework, we define Constraint(x) so that real interrogative sentences such as question B would receive high probability in the defined π(x). Our constraints are: (i) the whole sentence is in the interrogative form. (ii) Paris and located must appear in the sentence. We run MCMC starting from sentence A.
It is hard for MCMC without tree search to generate question B in a reasonable time starting from A. Because the edit distance between sentence A and B is larger than 2, we cannot generate B from A with one step of word insertion, removal, or replacement. In order for CGMH to reach B from A, it has to encounter a few intermediate steps. Without loss of generality, suppose CGMH proposes sentence C in one MCMC step by removing is: C: Paris is located in France. Notice that C is not a legitimate English sentence, so its language model score P LM (x) becomes much smaller compared to the original sentence A. In addition, C violates more constraints than A, which decreases its Constraint(x) score as well. In MCMC, the probability to accept the move from A to sentence C is given by Equation 4, in which the dominating term is π(C) π(A) = and Constraint(C) are smaller, the acceptance ratio becomes really small. In fact, we found the acceptance ratio to be 5.93 × 10 −12 in our experiment. This means that it will take CGMH many steps (on the order of 10 12 ) to move one step from sentence A to C. Figure 2 (left) demonstrates this. It is easy to verify that barriers of low acceptance rate exist on every path from sentence A to C and thus the rejection problem exists.
On the other hand, if we allow the proposal distribution to suggest sentences with multiple wordlevel changes, one can transit from sentence A to B through all legitimate sentences as intermediate

Paris is located in France.
Paris located in France.

R D I
Is Paris located in France?

R D I
Step 1 Step 2 Accept rate ≈ ! CGMH (highly likely to reject intermediate states) steps. Consider the following two-step change: 1. First delete is and insert is before Paris. This changes sentence A to D: Is Paris located in France? 2. Delete France and insert Which and country.
This changes sentence D to B. Because the intermediate step sentence D is a legitimate English sentence and Constraint(D) = Constraint(A), π(D) π(A) is close to 1, resulting in a 100% acceptance ratio in this step. When changing from D to B, notice that B is also a legitimate sentence and it satisfies more constraints than D. In fact, the acceptance ratio is also 100%. Figure 2 (right) demonstrates this case.
For tasks with soft constraints, there are also similar rejection problems for CGMH. For example, "Nothing is impossible" is a sentence with positive sentiment. If we insert, replace or delete one word, it is hard to keep the sentence valid and preserve the positive sentiment.
Motivated by these examples, we propose the embed a tree search into the proposal process of MCMC to solve the rejection problem, which suggests candidate sentences with multiple word-level changes and satisfy more constraints.

TSMH Algorithm Implementation
Our Tree Search enhanced Metropolis-Hastings (TSMH) still follows the classical MCMC procedure. The only difference is a new proposal distri-bution Q(x * |x) generated from a tree search process. The tree search defines a probability distribution over templates of sentence moves. Each template defines a subset of possible moves. The sentences within the same template satisfy the same hard constraints score Φ hard (x). The proposal probability distribution induced by the tree search algorithm biases towards templates that have high Constraint(x) scores.
A template defines a set of sentences where each word is either given or specified by a word category. For example, a template [[QWH],[AUX],[OTH], [OTH]] restricts that the first word must be a wh-word, the second word must be an auxiliary verb and the last two words must be other words.
Notice that we can decide how many hard constraints a sentence satisfies at the template level, since the indicator variables in the constraints defined in this paper only restrict the categories of words. For example, the template [[QWH],[AUX],[OTH], [OTH]] satisfies the constraints of being an interrogative sentence defined in Section 2. Our proposal procedure first sample a template and then fills in this template with words based on a language model. Overview of the Proposal Process During the sampling process, suppose we are at one sentence x. We will sample a new sentence x * from the proposal distribution as follows. First, our algorithm will decide the positions of the words to change by random selection. Typically, our algorithm will change more than one word. Then we use a tree search, which enumerates all possible operations on the selected words. This includes deciding the operation on each word (insert, delete, or replace) as well as the associated word category in case of insert and replacement. In this case, every leaf branch of the search tree will be a sentence template. Because the number of word categories is limited, the tree search procedure is often cheap. As discussed, we can infer the number of hard constraints satisfied based on the template associated with each tree leaf. We then rank these templates based on the number of constraints satisfied and sample one template based on a geometric series, favoring templates that satisfy more constraints. Finally, we fill in the sampled template with words suggested by a language model, and then select one filled sentencex as proposal, according to the language model score times the soft constraint score P LM (x) · Φ soft (x). Soft constraints Φ soft (x) give us a real number, which is similar to the language model P LM (x). We treat them together with the language model in the proposal process.
Our approach alleviates the rejection problem of MCMC by enumerating all possibilities in the space of multiple word change at the template level, based on the analysis in section 3.1. This process enables us to handle combinatorial constraints. Tree search also allows us to prune useless branches.

Detailed Search Procedure
The procedure of searching proposals in our tree search embedded MCMC is as follows and shown in Figure 3. Position Randomly select k positions {t 1 , . . . , t k } to perform word-level operations with uniform probabilities, where k is the size of the search steps. The probability of getting each combination of positions is: P pos = 1/ m k , where m is the length of the sentence. Search Search and iterate all different operations and all different word categories (mentioned in Section 2.1) for each selected position. For example, if we have |V| word categories and the operation set {replace, insert, delete, none} , we need to enumerate (2|V|+2) k different combinations of operations and word categories. We use word placeholders [MASK] to represent the unknown inserted or replaced words. We keep track of all the generated templates and their corresponding numbers of vio-  lated constraints. Rank and Group Selection We define a group as the set of templates which violate the same number of constraints. We sort all templates by its number of violated constraints (constraint error) C in ascending order, and put templates with the same C into one group. We then randomly select group i with probability: where C i is the constraint error of group i, and β is a very small float value (like 10 −10 ). In this way, we favor choosing the group satisfying the largest amount of constraints, while also ensuring the irreducibility of the Markov chain. Let the chosen group at this step be G i . Fill and Template Selection In this step we will first fill every template with words in the selected group G i , then we select one filled template as the proposal. Because the template restricts the masked word to be chosen only from the corresponding word category, we fill it by selecting words from the given word category. The probability of selecting the t i -th word P Fill i is the conditional probability of filling words at this locations given contexts: P LM (x t i |x 1 , ..., x t i −1 , x t i +1 , ..., x m ). The probability of getting one sampled sentence is: P fill = k i=1 P fill i , where i means the word level action for i-th position we selected. If the operation in t i is delete or none, then P fill i = 1. We sample one template within the group (together with the corresponding sampled sentence) according to the sentence probability times soft constraint score: The proposal distribution Q(x * |x) leading from sentence state x to x * in this procedure is Q(x * |x) = P pos P group P fill P template .

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 Table 1.
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 Table 1, in which Valid% denotes the percentage of generated sentences that satisfy all constraints. π(x) is the value of the stationary probability P LM (x) · Constraint(x). P GPT−2 (x) is language model probability estimated by a pretrained GPT-2 model, which measures the quality of the sentences. Accept% means the acceptance rate of MCMC. Detailed experiment settings can be reviewed in appendix A.1.

Interrogative Sentence Generation
In the interrogative sentence generation, we construct interrogative sentences by sampling starting from the keywords. We enforce that sentences with a high probability to be sampled must satisfy gram-mar constraints of being interrogative and contain a few given keywords. The constraint definition for interrogative sentences is in section 2.1.
According to the results, in the experiment with keywords, 92.67% of the output sentences of our TSMH algorithm satisfy all the constraints, while merely 18.33% satisfy constraints for the baseline. The numbers are 83.17% and 45.50% for the experiment without keywords, respectively. This demonstrates that our TSMH generates sentences with more constraints satisfied. In addition, our method has a higher π(x) (stationary probability value) and acceptance rate, suggesting that the tree search embedded help MCMC to mix faster. Overall, our method TSMH can handle more complicated constraints in language generation tasks. Human Evaluation We conduct human evaluation for interrogative sentences generated with keywords. We present human participants from the Amazon Mechanical Turk with a pair of sentences at a time. One sentence is generated by our TSMH model and the other one is from the baseline CGMH. We ask human participants which sentence is better in terms of fluency and grammar. In terms of the experimental setting, we use 100 sentence pairs generated by CGMH and TSMH with the same keyword inputs. We randomly split these 100 test sentence pairs into 5 survey groups, and then deploy them on the Amazon Mechanical Turk. We randomly assign human participants to survey groups. When showing the sentence pairs, we also provide the keywords that the sentences must contain. We ask human participants to vote which sentence in the pair is better in terms of grammar coherence, keyword coverage and fluency. We use a gold-standard question to detect if the voter is randomly doing the survey. Every valid survey contains a randomized set of 20 questions. We received in all 580 votes. Each question pair receives votes ranging from 5 to 11. As shown in Table 2, sentences from our model receive almost twice times of votes than the baseline, which suggests that the sentences generated by our approach is better in human evaluation. Case Studies As shown in Table 3 Table 1: Our method TSMH outperforms CGMH by generating sentences that satisfy more constraints, are of good quality and are likely to be natural language. Column Valid% shows the percentage of generated sentences that satisfy all constraints, which TSMH clearly leads baselines. In addition, TSMH has better acceptance rates (Accept%). The language generated by TSMH is also of good quality, because it matches other models in language model scores P GPT−2 (x). Multiplying both the language model score and the constraint score, the sentences generated by TSMH tend to attain higher stationary probability π(x).   In other words, for TSMH, the inputs are keywords extracted from the SQuAD 2.0 (Rajpurkar et al., 2018) questions. For UQA, we take the corresponding paragraphs of the selected questions as input. This also gives UQA additional advantage because it has access to a paragraph, rather than keywords.

Methods
To make it more comparable, we remove the keyword constraints in this experiment. In Table 4, we compare the language model scores log P LM of the generated sentences that reflect the naturalness and fluency, and the stationary probability π(x) and valid percentage Valid% that show how good it satisfies our pre-defined constraints. We pointed out that UQA was trained on the specific interrogative sentences while our method was not trained at all.

Imperative Sentence Generation
We generate imperative sentences via sampling starting from the keywords. We enforce grammar constraints of being an imperative sentence: the starting word should be either a verb w [VERB] 1 or an adverb followed by a verb w [ADV] 1 ∧ w [VERB] 2 . We also enforce keyword constraints in this task.
As shown in Table 1, our method has a higher valid percentage of 97.75% compared to 91.32% of the baseline, showing that the sentences generated by our method can satisfy more constraints. Our method has a higher π(x) (stationary probability value) and acceptance rate, suggesting our approach has a better mixing behavior. Overall, results show that our method using Tree Search Embedded MCMC can handle more complicated combinatorial constraints in language generation.

Sentence Generation with Given Sentiments
In this task, we require the sentences to contain the specified keywords and have positive sentiments (Fu et al., 2019). We enforce the sentences to attain high scores from a sentiment analysis neural network. We also enforce keyword constraints as hard constraints. We need to emphasize that, our method uses a model pre-trained on a separate dataset for sentiment analysis, which is kept intact in our experiment. No additional fine-tuning to the sentiment analysis model was performed. we consider two sub-tasks in Table 5: (i) positive sentiment to positive sentiment (P2P), where the input keywords are extracted from sentences which originally have positive sentiments; (ii) negative sentiment to positive sentiment (N2P), where the keywords are extracted from sentences with negative sentiments. N2P is more difficult as it requires transforming the sentiment. Our method has a higher sentiment score, suggesting that our method generates sentences with more positive sentiments (better aligned with the target of this experiment). The increase against CGMH is bigger on the more difficult N2P task, which requires flipping the sentiment. Our model also leads in terms of language model scores, suggesting the language quality is better.    (Hu et al., 2017) over the N2P subtask with acceptance rate, language score and sentiment score metrics.
Comparison with Other Methods We compare our method with CtrlGen (Hu et al., 2017). The setting is a little different from ours: it takes a sentence with a negative sentiment as input and transforms it to positive, without the guarantee of satisfying keyword constraints. Our method takes a set of keywords as input. To make the outputs comparable, we select the same set of negative sentences as the input of CtrlGen and extract the keywords of those sentences as the input of TSMH. Our method requires no additional training besides a pre-trained sentiment analysis model and a pretrained language model, while CtrlGen requires training the auto-encoder.
The results in Table 6 show that our method outperforms CtrlGen in terms of both sentence quality and sentiment, as the sentences generated by our method receive higher language model scores and sentiment scores.

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.