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.
Code (1)
Tasks
Language ModelingLanguage ModellingSentenceText GenerationSimilar Papers 제목 키워드 기반
MCTS Based Dispatch of Autonomous Vehicles under Operational Constraints for Continuous Transportation
Continuous transportation of material in the mining industry is achieved by the dispatch of autonomous haul-trucks with discrete haulage capacities. Recently, Monte Carlo Tree Search (MCTS) was successfully deployed in t…
Autonomous VehiclesSchedulingGraph Neural Networks for Maximum Constraint Satisfaction
Many combinatorial optimization problems can be phrased in the language of constraint satisfaction problems. We introduce a graph neural network architecture for solving such optimization problems. The architecture is ge…
Combinatorial OptimizationGraph Neural NetworkTowards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
Motivated by phase transitions in combinatorial optimization problems, we define two kinds of geometry-preserving reductions between constraint satisfaction problems and other NP-search problems. We give a couple of exam…
Combinatorial OptimizationGenCO: Generating Diverse Designs with Combinatorial Constraints
Deep generative models like GAN and VAE have shown impressive results in generating unconstrained objects like images. However, many design settings arising in industrial design, material science, computer graphics and m…
Combinatorial OptimizationImage GenerationAn Effective Upperbound on Treewidth Using Partial Fill-in of Separators
Partitioning a graph using graph separators, and particularly clique separators, are well-known techniques to decompose a graph into smaller units which can be treated independently. It was previously known that the tree…