PaperlayerView exact revision on arXiv

Source-linked AI summary

Unsupervised Paraphrasing by Simulated Annealing

Xianggen Liu, Lili Mou, Fandong Meng, Hao Zhou, Jie Zhou, Sen Song

arXiv:1909.03588v2cs.CL

TL;DR

Paraphrase generation must preserve meaning while changing wording, yet producing accurate and varied outputs remains challenging. UPSA casts unsupervised paraphrasing as simulated-annealing search over local edits, scoring semantic preservation, diversity, and fluency. Across four benchmarks, the authors report state-of-the-art unsupervised performance and results above most domain-adapted paraphrase generators.

  • Problem

    Paraphrase generation must preserve meaning while changing wording, but accurate and different-appearing outputs remain challenging, and available paraphrase pairs are costly, limited, and domain-specific.

    Source: Introduction · p. 1

  • Method

    UPSA uses simulated annealing to search through local word edits, optimizing semantic preservation, expression diversity, and language fluency.

    Source: Introduction · p. 1

  • Results

    UPSA achieves state-of-the-art unsupervised performance on four datasets in automatic metrics and human evaluation, outperforming most domain-adapted paraphrase generators.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    The authors report that UPSA largely reduces the unsupervised–supervised performance gap and outperforms a supervised model on Wikianswers.

    Source: Introduction · p. 2

    UPSA mainly edits words while preserving the source syntax, partly because exploring the discrete sentence space is difficult and the similarity objective is insensitive to very different sentences.

    Source: Model Analysis · p. 7

Abstract

from arXiv · show

Unsupervised paraphrase generation is a promising and important research topic in natural language processing. We propose UPSA, a novel approach that accomplishes Unsupervised Paraphrasing by Simulated Annealing. We model paraphrase generation as an optimization problem and propose a sophisticated objective function, involving semantic similarity, expression diversity, and language fluency of paraphrases. Then, UPSA searches the sentence space towards this objective by performing a sequence of local editing. Our method is unsupervised and does not require parallel corpora for training, so it could be easily applied to different domains. We evaluate our approach on a variety of benchmark datasets, namely, Quora, Wikianswers, MSCOCO, and Twitter. Extensive results show that UPSA achieves the state-of-the-art performance compared with previous unsupervised methods in terms of both automatic and human evaluations. Further, our approach outperforms most existing domain-adapted supervised models, showing the generalizability of UPSA.

Introduction

Paraphrase generation must preserve meaning while changing wording, but small, domain-specific training corpora and noisy synthetic pairs constrain supervised approaches. UPSA uses simulated annealing to search through local edits, and the authors report strong results across four benchmark datasets.

Introduction

  • Supervised paraphrase models rely on parallel examples, but paraphrase pairs are costly to create and existing datasets are small or domain-specific.The Quora dataset contains 140K pairs and only question sentences; synthesized pairs can be noisy and yield low paraphrasing performance.Source: Introduction · p. 1
  • Unsupervised generation could avoid dependence on parallel data, while probabilistic sampling methods make meaning preservation and expression diversity less controllable.The authors identify this reduced controllability as a limitation of sampling from neural-network-defined distributions.Source: Introduction · p. 1
  • UPSA optimizes semantic preservation, expression diversity, and language fluency through simulated annealing over word replacement, insertion, and deletion.It proposes edits and accepts or rejects them based on sentence quality; a high initial temperature permits worse sentences, while cooling helps the search settle toward an optimum.Source: Introduction · pp. 1–2, Figure 1 · p. 2
  • UPSA achieves state-of-the-art unsupervised performance on four datasets in automatic metrics and human evaluation, outperforming most domain-adapted generators.The authors also report that it outperforms a supervised model on Wikianswers and largely reduces the performance gap between unsupervised and supervised paraphrasing.Source: Introduction · p. 2

Related Work

Prior paraphrase work spans supervised neural models, unsupervised sampling, and editing-based generation. UPSA differs by using unsupervised stochastic search with distributed sentence edits and an objective that includes expression diversity.

Related Work

  • Li et al. (2019) report state-of-the-art supervised paraphrase generation with sentence- and word-level granularity and improved generalizability to new domains.Their approach remains supervised.Source: Related Work · p. 2
  • Unsupervised VAE sampling can generate paraphrases, but outputs are less controllable and decoding suffers from error accumulation; Roy and Grangier (2019) focus on data augmentation instead.The latter work is not directly comparable as paraphrase generation.Source: Related Work · p. 2
  • Unlike Miao et al. (2019), who use Metropolis–Hastings sampling, UPSA formulates paraphrasing as stochastic search with an objective that includes expression diversity and a copy mechanism.Source: Related Work · p. 2
  • Earlier editing-based approaches use supervised sequence-to-sequence generation or learned operations, whereas UPSA uses insertion, deletion, and replacement as unsupervised simulated-annealing actions.Source: Related Work · p. 2
  • Unlike beam search's partially greedy left-to-right or right-to-left decoding, UPSA makes distributed edits across a sentence and can start from the original input.The authors note that beam search is not applicable to unsupervised paraphrasing in its usual sequence-to-sequence decoder setting.Source: Related Work · p. 2

Approach

UPSA frames unsupervised paraphrase generation as simulated-annealing search over sentence candidates, optimizing semantic preservation, expression diversity, and fluency. It explores this objective through local edits and an acceptance process.

The Simulated Annealing Algorithm

  • SA accepts better-scored candidates and may accept worse ones according to a temperature that decreases linearly during the search.An accepted proposal becomes the next state; otherwise the current sentence remains. The stated global-optimum convergence guarantee requires mild conditions and may be slower than exhaustive search.Source: The Simulated Annealing Algorithm · p. 3

Objective Function

  • The objective combines semantic preservation, expression diversity, and candidate-sentence fluency.Fluency is scored with a dataset-specific language model trained on non-parallel sentences.Source: Objective Function · p. 3
  • Semantic preservation combines keyword-level and sentence-level similarity, with hyperparameters balancing the two factors.The keyword score uses the least-matched input keyword; the sentence-level score uses Sent2Vec cosine similarity.Source: Objective Function · p. 3
  • BLEU-induced expression diversity penalizes repetition of the input's words and phrases.A parameter S controls the importance of the diversity score in the objective.Source: Objective Function · p. 3

Candidate Sentence Generator

  • The candidate generator samples an editing position and operation, and uses an objective-induced word distribution with top-K proposals for insertion or replacement.In the experiments, K is set to 50.Source: Candidate Sentence Generator · p. 4
  • The copy mechanism adds words from the original sentence to the replacement and insertion vocabularies, addressing rare words and named entities that are difficult to recover after edits.Those words may receive low language-model probabilities during stochastic sampling.Source: Candidate Sentence Generator · p. 4

Overall Optimization Process

  • Starting from the input, UPSA repeatedly proposes word insertions, deletions, or replacements, accepts or rejects candidates, and returns the highest-scoring sentence found.At each step it selects an action and position, then forms a candidate sentence and evaluates it against the objective.Source: Overall Optimization Process · p. 4, Candidate Sentence Generator · p. 4

Experiments

Across four paraphrase benchmarks, experiments compare UPSA with unsupervised and supervised generators, reporting stronger unsupervised results and high human ratings. The analysis also examines dataset transfer, model components, and search settings.

Datasets

  • The four evaluation datasets are Quora, Wikianswers, MSCOCO, and Twitter, with dataset-specific training and test protocols.UPSA uses non-parallel sentences for language-model training; the Twitter evaluation includes 566 test cases labeled as paraphrases.Source: Datasets · pp. 4–5

Competing Methods and Metrics

  • Comparisons include VAE and CGMH, supervised generators, and domain-adapted supervised models; iBLEU is the primary automatic metric, alongside human evaluation.The authors could not compare rule-based systems because their extracted rules were unavailable.Source: Competing Methods and Metrics · p. 5

Implementation Details

  • All simulated-annealing hyperparameters were validated on Quora only, while language models were trained specifically on each dataset.The selected objective weights were P = 8, Q = 1, and S = 1; the initial temperature was 3 × 10^-2, with 100 iterations.Source: Implementation Details · p. 5

Results

  • UPSA's iBLEU score exceeds CGMH by 2–5 points on Quora and Wikianswers; on MSCOCO and Twitter, UPSA ranks first among unsupervised methods, followed by CGMH and VAE.Twitter yields lower iBLEU scores for all models, which the authors attribute largely to noisy utterances; results are reported without hyperparameter retuning across domains.Source: Results · pp. 5–6, Table 1 · p. 6, Table 2 · p. 6
  • UPSA receives the highest human satisfaction scores for relevance and fluency, with gains over CGMH and VAE significant at p < 0.01 in both aspects.The evaluation used 300 Quora test sentences, three annotators, and 1-to-5 ratings for each aspect.Source: Table 3 · p. 6, Results · p. 6
  • UPSA outperforms all supervised domain-adapted paraphrase generators except DNPG on Wikianswers.The compared domain-adapted systems are trained on one dataset and tested on the other; UPSA's hyperparameters were not tuned on the non-Quora datasets.Source: Results · pp. 5–6, Implementation Details · p. 5

Model Analysis

  • Ablations support the roles of keyword similarity, sentence similarity, and expression diversity, while the copy mechanism adds roughly one iBLEU point and annealing outperforms fixed-temperature search.The copy mechanism is used in word replacement and insertion; fixed initial temperature is compared with a decaying temperature schedule.Source: Model Analysis · pp. 6–7
  • Case studies find paraphrases closer in meaning and more varied in wording than VAE and CGMH examples, while source syntax is mostly preserved; both high and low initial temperatures underperform annealing.Simulated annealing also outperforms greedy search at Tinit = 0, and BLEU and iBLEU peak at different initial temperatures.Source: Model Analysis · p. 7

Conclusion

UPSA generates paraphrases without supervision by using simulated annealing and an objective that combines semantic preservation, expression diversity, and language fluency. Across four benchmark datasets, it outperforms prior state-of-the-art unsupervised methods, most domain-adaptive generators, and a supervised model on Wikianswers; the authors plan to explore syntactic parse trees for greater syntactic variation.

Conclusion

  • Across four benchmark datasets, UPSA outperforms previous state-of-the-art unsupervised methods, most domain-adaptive generators, and a supervised model on Wikianswers.The reported comparison is stated for the overall experiments; the supervised-model result is specifically on Wikianswers.Source: Conclusion · p. 7
  • UPSA generates paraphrases of given sentences through simulated annealing, with an objective involving semantic preservation, expression diversity, and language fluency.Source: Conclusion · p. 7
  • The authors plan to apply simulated annealing to syntactic parse trees in hopes of generating more syntactically different sentences.Source: Conclusion · p. 7
Loading 1909.03588v2…