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

• URL: http://arxiv.org/abs/2011.12334v2
• Date: Mon, 30 Nov 2020 00:15:04 GMT
• Title: Language Generation via Combinatorial Constraint Satisfaction: A Tree Search Enhanced Monte-Carlo Approach
• Authors: Maosen Zhang, Nan Jiang, Lei Li, and Yexiang Xue
• Abstract summary: We present a framework to allow specification of constraints for sentence generation. We propose TSMH, an efficient method to generate high likelihood sentences with respect to a pre-trained language model. Our approach is highly flexible, requires no task-specific training, and leverages efficient constraint satisfaction solving techniques.
• Score: 24.897552102098324
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• Attribute Controlled Fine-tuning for Large Language Models: A Case Study on Detoxification [76.14641982122696]
  We propose a constraint learning schema for fine-tuning Large Language Models (LLMs) with attribute control. We show that our approach leads to an LLM that produces fewer inappropriate responses while achieving competitive performance on benchmarks and a toxicity detection task.
  arXiv  Detail & Related papers  (2024-10-07T23:38:58Z)
• Combining Constraint Programming Reasoning with Large Language Model Predictions [44.99833362998488]
  Constraint Programming (CP) and Machine Learning (ML) face challenges in text generation. This paper proposes a solution by combining both approaches and embedding a Large Language Model (LLM) in CP.
  arXiv  Detail & Related papers  (2024-07-18T13:15:55Z)
• Intertwining CP and NLP: The Generation of Unreasonably Constrained Sentences [49.86129209397701]
  This paper presents the Constraints First Framework to remedy this issue. It is solved by a constraint programming method that combines linguistic properties with more classical constraints. The effectiveness of this approach is demonstrated by tackling a new more tediously constrained text generation problem.
  arXiv  Detail & Related papers  (2024-06-15T17:40:49Z)
• Toward Unified Controllable Text Generation via Regular Expression Instruction [56.68753672187368]
  Our paper introduces Regular Expression Instruction (REI), which utilizes an instruction-based mechanism to fully exploit regular expressions' advantages to uniformly model diverse constraints. Our method only requires fine-tuning on medium-scale language models or few-shot, in-context learning on large language models, and requires no further adjustment when applied to various constraint combinations.
  arXiv  Detail & Related papers  (2023-09-19T09:05:14Z)
• Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs [46.721838623748816]
  We propose a new inference-time approach to enforcing syntactic and semantic constraints on the outputs of large language models. Key idea is to specify language generation tasks as posterior inference problems in a class of discrete probabilistic sequence models. For a computational cost similar to that of beam search, SMC can steer LLMs to solve diverse tasks.
  arXiv  Detail & Related papers  (2023-06-05T17:55:05Z)
• Controlled Text Generation with Natural Language Instructions [74.88938055638636]
  InstructCTG is a controlled text generation framework that incorporates different constraints. We first extract the underlying constraints of natural texts through a combination of off-the-shelf NLP tools and simple verbalizes. By prepending natural language descriptions of the constraints and a few demonstrations, we fine-tune a pre-trained language model to incorporate various types of constraints.
  arXiv  Detail & Related papers  (2023-04-27T15:56:34Z)
• Tractable Control for Autoregressive Language Generation [82.79160918147852]
  We propose to use tractable probabilistic models (TPMs) to impose lexical constraints in autoregressive text generation models. We show that GeLaTo achieves state-of-the-art performance on challenging benchmarks for constrained text generation. Our work opens up new avenues for controlling large language models and also motivates the development of more expressive TPMs.
  arXiv  Detail & Related papers  (2023-04-15T00:19:44Z)
• Constrained Sampling from Language Models via Langevin Dynamics in Embedding Spaces [34.375537557235724]
  We propose a sampling procedure that combines the log-likelihood of the language model with arbitrary differentiable constraints into a single energy function. We evaluate our approach on different text generation tasks with soft and hard constraints as well as their combinations with competitive results for toxicity avoidance, sentiment control, and keyword-guided generation.
  arXiv  Detail & Related papers  (2022-05-25T08:09:03Z)
• NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics [73.96837492216204]
  We propose NeuroLogic A*esque, a decoding algorithm that incorporates estimates of future cost. We develop efficient lookaheads that are efficient for large-scale language models. Our approach achieves competitive baselines on five generation tasks, and new state-of-the-art performance on table-to-text generation, constrained machine translation, and keyword-constrained generation.
  arXiv  Detail & Related papers  (2021-12-16T09:22:54Z)
• Generating texts under constraint through discriminator-guided MCTS [1.3750624267664153]
  We formalize constrained generation as a tree exploration process guided by a discriminator. Using a discriminator to guide this generation, rather than fine-tuning the LM, allows to apply the constraint more finely and dynamically. We show that our methods achieves state-of-the-art results in constrained generation, without having to tune the language model.
  arXiv  Detail & Related papers  (2021-09-28T09:29:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.