Source-linked AI summary
CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, Lei Li
TL;DR
Constrained sentence generation must balance fluency with requirements such as keyword inclusion, but sequential RNN generation makes such constraints difficult to impose. CGMH uses Metropolis-Hastings sampling with sentence-level operations and matching functions, achieving strong results across several tasks, including unsupervised settings without parallel corpora.
Problem
Sequential RNN-based generation makes it difficult to impose hard and soft constraints while maintaining generation quality.
Method
CGMH directly samples sentence space with Metropolis-Hastings using replacement, insertion, and deletion proposals and task-specific stationary distributions.
Results
CGMH achieves high performance close to state-of-the-art supervised approaches across keyword generation, paraphrasing, and error correction, including without parallel corpora.
Takeaways & Limitations
CGMH provides a general framework for constrained sentence sampling that supports hard and soft constraints and unsupervised applications.
Takeaways & Limitations
The paraphrase experiments restrict paraphrases to BLEU-ori less than 55, and designing better stationary-distribution heuristics remains future work.
Abstract
from arXiv · showhide
In real-world applications of natural language generation, there are often constraints on the target sentences in addition to fluency and naturalness requirements. Existing language generation techniques are usually based on recurrent neural networks (RNNs). However, it is non-trivial to impose constraints on RNNs while maintaining generation quality, since RNNs generate sentences sequentially (or with beam search) from the first word to the last. In this paper, we propose CGMH, a novel approach using Metropolis-Hastings sampling for constrained sentence generation. CGMH allows complicated constraints such as the occurrence of multiple keywords in the target sentences, which cannot be handled in traditional RNN-based approaches. Moreover, CGMH works in the inference stage, and does not require parallel corpora for training. We evaluate our method on a variety of tasks, including keywords-to-sentence generation, unsupervised sentence paraphrasing, and unsupervised sentence error correction. CGMH achieves high performance compared with previous supervised methods for sentence generation. Our code is released at https://github.com/NingMiao/CGMH
Introduction
CGMH addresses constrained sentence generation by sampling directly in sentence space with Metropolis-Hastings, supporting hard and soft constraints. Across keyword generation, paraphrasing, and error correction, it achieves strong performance without parallel corpora.
- Motivation: Natural language generation constraints include hard requirements such as keyword inclusion and soft requirements such as semantic relatedness.The paper illustrates hard keyword constraints with an advertisement containing “BMW” and “sports.”
- Motivation: RNN-based methods generate left to right, making it non-trivial to impose constraints during generation.Previous backward-forward generation handled only one keyword, while grid beam search is less suitable for general sentence generation with many candidates.
- CGMH: CGMH directly samples sentence space with Metropolis-Hastings using word replacement, deletion, and insertion proposals.Each proposal is accepted or rejected according to an acceptance rate based on a pre-specified stationary distribution.
- CGMH: A matching function manipulates the stationary distribution to enforce hard constraints or encourage soft constraints.Hard constraints can use a binary feasibility indicator, whereas soft constraints can use semantic similarity.
- Results: CGMH outperforms state-of-the-art constrained models on keyword-to-sentence generation in fluency and human evaluation.For paraphrase generation and sentence error correction, it significantly outperforms other unsupervised models and approaches state-of-the-art supervised performance without parallel corpora.
- Results: The paper presents CGMH as a general framework for hard and soft constraints across keyword generation, paraphrasing, and error correction without requiring parallel corpora.The framework operates during inference and is designed for sentence sampling in multiple constrained-generation tasks.
Related Work
Related work uses sequential sampling, latent-space models, Gibbs sampling, and constrained search, but these approaches have limitations with flexible hard and soft constraints. CGMH extends the sampling framework to both constraint types and enables several unsupervised applications.
- Sampling-based generation: RNN generation commonly uses MAP inference with greedy or beam search, while sampling methods include forward sampling, prototype editing, and VAE latent-space sampling.These approaches do not support flexible soft constraints or hard constraints requiring specified words.
- Sampling-based generation: Gibbs sampling can replace tokens using bidirectional RNN posteriors, but it cannot change sentence length.CGMH extends this approach with word insertion and deletion.
- Search-based generation: Grid beam search and constrained beam search use structured search to satisfy constraints, primarily in neural machine translation.The related work describes grid beam search as two-dimensional beam search and constrained beam search as using a finite-state machine.
- Soft-constraint generation: Latent-feature control methods target properties such as meaning or sentiment but require explicit feature definitions and large labeled datasets.Examples include discriminator-based VAE sentiment control and cross-alignment style transfer using non-parallel data.
- CGMH: CGMH differs by applying Metropolis-Hastings sampling to both hard and soft constraints.This framework supports unsupervised paraphrase generation, unsupervised error correction, and keyword-based sentence generation.
Approach
CGMH uses Metropolis-Hastings sampling over sentence space to generate sentences satisfying hard or soft constraints. Its proposal operations and stationary distribution are designed for flexible, constraint-aware sampling across multiple generation tasks.
- General framework: CGMH applies Metropolis-Hastings sampling directly in sentence space, using proposal distributions, stationary distributions, and acceptance decisions tailored to constrained generation.The framework treats each sentence as a Markov-chain state and designs its components for application-specific constraints.
- Proposal operations: The sampler proposes word replacement, insertion, or deletion operations, with equal probabilities in the reported experiments.The three operation probabilities are [pinsert, pdelete, preplace] = [1/3, 1/3, 1/3].
- Proposal operations: Insertion and deletion preserve ergodicity by making any sentence reachable from any other through successive deletions and insertions.Replacement additionally helps reach semantically neighboring states more easily, while top-ranked candidate restrictions are stated not to affect ergodicity.
- Stationary distribution: CGMH defines a stationary distribution by combining general sentence probability with scoring functions that measure constraint satisfaction.The scoring functions can be multiplied to impose multiple constraints, and their design is task related.
- Constraint modeling: Hard constraints use indicator functions that exclude infeasible sentences, whereas soft constraints use graded matching scores such as semantic similarity.The framework supports both types by incorporating their scoring functions into the stationary distribution.
- Task-specific scoring: For paraphrasing, CGMH combines language-model fluency with keyword, embedding, or skip-thought similarity matching, while keyword generation uses keyword matching as a hard constraint.The embedding variants use minimum or average cosine similarity between words in the generated and input sentences.
Experiments
Experiments evaluate CGMH across keyword-constrained generation, unsupervised paraphrase generation, and unsupervised sentence error correction. Results indicate strong performance, while analyses examine sampling efficiency, initialization, and differences from latent-space generation.
- Experiments: CGMH is evaluated on keyword-to-sentence generation, unsupervised paraphrase generation, and unsupervised sentence error correction.The experiments include both hard and soft constraint settings.
- Keywords-to-Sentence Generation: CGMH outperforms prior constrained-generation methods in both negative likelihood and human evaluations for sentences containing 1 to 4 keywords.The compared systems include grid beam search and two backward-forward variants.
- Keywords-to-Sentence Generation: Human evaluations show high volunteer consistency, a large gap between models, and statistically significant differences between CGMH and the baselines.For CGMH versus the backward-forward models, p-values are lower than 0.001.
- Unsupervised Paraphrase Generation: On paraphrase generation, CGMH achieves a fairly close BLEU-ref score to the best supervised approaches and outperforms supervised methods when training data are ≤50k pairs.The evaluation also considers BLEU-ori and NLL; lower BLEU-ori is preferred for literal difference.
- Unsupervised Paraphrase Generation: CGMH produces paraphrases that are qualitatively close in meaning while differing in expression, but the analysis restricts candidates to BLEU-ori below 55.The BLEU-ori restriction is used to assure a significant literal difference.
- Unsupervised Sentence Error Correction: For sentence correction, CGMH achieves comparable results to CAMB14 and outperforms AMU, although it remains behind other supervised approaches.AMU uses 2.3M parallel training pairs and engineered linguistic features.
- Model Analysis: Fewer than 50 sampling steps change more than 20% of words in paraphrase generation, supporting practical sampling efficiency.Word replacement has a 100% acceptance rate, while deletion and addition have lower but reasonable acceptance rates.
- Model Analysis: Small corruption of the initial state does not significantly affect performance, whereas fully random initialization improves gradually but fails to reach satisfactory performance after 100 epochs.The analysis therefore identifies warm starts as useful for CGMH sentence sampling.
Conclusion
CGMH uses Metropolis-Hastings sampling with word-level proposals and task-specific stationary distributions for constrained sentence generation. Across keywords-to-sentence generation, paraphrase generation, and error correction, it enables unsupervised learning while achieving performance close to state-of-the-art supervised approaches.
- CGMH proposes word-level replacement, insertion, and deletion operations as Metropolis-Hastings proposals for constrained sentence generation.
- The framework supports keywords-to-sentence generation, paraphrase generation, and sentence error correction.
- CGMH makes unsupervised learning feasible for these applications and achieves high performance close to state-of-the-art supervised approaches.