Source-linked AI summary
A Survey of Paraphrasing and Textual Entailment Methods
Ion Androutsopoulos, Prodromos Malakasiotis
TL;DR
Paraphrasing and textual entailment research spans many methods and applications, but its large literature makes key concepts and suitable methods difficult to assimilate. This paper surveys the field by classifying recognition, generation, and extraction approaches, while pointing to prominent articles and resources. It also shows that ambiguity and representation quality constrain judgments and practical performance.
Problem
The literature on paraphrasing and textual entailment is vast, making it difficult to assimilate key concepts and identify suitable methods.
Method
The paper surveys both areas by organizing methods into recognition, generation, and extraction and classifying their goals and assumptions.
Results
The survey identifies prominent ideas, articles, and resources across paraphrasing and textual entailment methods.
Takeaways & Limitations
Paraphrasing and textual entailment methods are relevant to applications including question answering, summarization, text generation, and machine translation.
Takeaways & Limitations
Judgments depend on selecting readings for ambiguous expressions, and inaccurate syntactic or semantic representations can introduce noise without guaranteeing better practical performance.
Abstract
from arXiv · showhide
Paraphrasing methods recognize, generate, or extract phrases, sentences, or longer natural language expressions that convey almost the same information. Textual entailment methods, on the other hand, recognize, generate, or extract pairs of natural language expressions, such that a human who reads (and trusts) the first element of a pair would most likely infer that the other element is also true. Paraphrasing can be seen as bidirectional textual entailment and methods from the two areas are often similar. Both kinds of methods are useful, at least in principle, in a wide range of natural language processing applications, including question answering, summarization, text generation, and machine translation. We summarize key ideas from the two areas by considering in turn recognition, generation, and extraction methods, also pointing to prominent articles and resources.
1. Introduction
The survey distinguishes paraphrasing, which preserves almost the same information, from textual entailment, where readers infer one expression from another. It organizes methods by recognition, generation, and extraction while highlighting ambiguity, applications, and evaluation resources.
- Core concepts: Paraphrases convey the same or almost the same information, while textual entailment pairs support inferring that H is most likely true from T.Paraphrasing is often treated as bidirectional textual entailment, whereas entailment is directional.
- Core concepts: Both areas extend beyond sentences to templates, where slot fillers may be constrained syntactically or semantically and entailment can depend on the discourse or filler.Template entailment may be directional: “X painted Y” entails “Y is the work of X,” but not necessarily the reverse.
- Core concepts: Ambiguity from word senses and syntactic structure means judgments require selecting particular readings or accepting possible readings under a looser definition.For example, “bank” supports the entailment only under its financial sense; contexts can clarify intended readings.
- Applications: Paraphrasing and entailment support question answering, information retrieval, summarization, sentence compression, text generation, and machine translation evaluation.Question paraphrasing can retrieve more relevant passages, while compression produces shorter grammatical text that is often entailed rather than paraphrastic.
- Survey organization: The article presents the first extensive survey of the area and classifies methods by task type and by recognition, generation, or extraction, with prominent articles and resources.Its sections cover recognition, generation, and extraction for both paraphrasing and textual entailment, followed by future research directions and resource URLs.
2. Paraphrase and Textual Entailment Recognition
Recognition methods judge paraphrase or entailment relations between expressions using surface, syntactic, semantic, or combined representations. Higher-level representations can expose relations missed by surface similarity, but parsing and semantic analysis may introduce noise.
- Recognizers classify whether two expressions are paraphrases or form a textual entailment pair, sometimes using probabilistic judgments aligned with human decisions.
- Logical approaches map expressions to formulae and check whether background knowledge supports entailment from T to H.Meaning postulates and common-sense knowledge may be represented in B.
- Vector-space approaches represent words through corpus co-occurrence and can test whether H is close to part of T, although negation and truth-value effects require caution.
- Surface-string methods use edit distance, common words, or related similarity measures, but may miss synonyms and longer paraphrases.
- Surface similarity between a short hypothesis and an entire longer text can be low, motivating sliding windows, alignment, or variable-length spans.
- Syntactic methods compare dependency representations or parse-tree substructures, revealing similarities and entailments that surface windows can miss.Dependency trees can align active and passive structures, while syntactic comparisons can reject misleading verbatim matches.
2.6 Recognition Approaches that Employ Machine Learning
Machine-learning recognition systems combine multiple similarity and representation features to classify paraphrase and entailment pairs. Evaluation uses benchmark corpora, with results showing recall–precision trade-offs and limits on cross-dataset comparisons.
- Systems represent each expression pair as a feature vector combining surface, syntactic, semantic, and other similarity measures.
- Preprocessing commonly supplies feature information through tagging, parsing, stemming, normalization, named-entity recognition, and reference replacement.
- Tree-fragment kernels can encode parse-tree features and train an SVM to separate positive textual-entailment pairs from negative ones.
- Rule-based transformations can be searched as decoding sequences that gradually convert one expression into another, but large rule resources create exponentially many sequences.
- Near-miss negative pairs are preferred for discriminative training and can make test data more challenging.
- 5,801 pairs comprise the MSR Paraphrase Corpus, while RTE-3 contains 1,600 textual-entailment pairs across four application scenarios.
- All MSR systems have higher recall than precision, and BASE2’s string-edit-distance method is a competitive baseline; cross-dataset comparisons are not always meaningful.
3. Paraphrase and Textual Entailment Generation
Paraphrase and entailment generators take one expression as input and produce multiple equivalent or entailing expressions. Many generation methods adapt statistical machine translation, using language and transformation models with decoding to select outputs.
- Generators receive one expression or template and produce as many paraphrases or entailing expressions as possible.
- Many generation methods borrow ideas from statistical machine translation, which commonly relies on large parallel corpora without explicit meaning representations.
- In the noisy-channel formulation, P(N) is the language model and P(F|N) is the translation model used to search for the best output.
- The search for the output N* that maximizes the model objective is called decoding.
N P(N)max
Paraphrase generation adapts translation-inspired models to produce grammatical outputs while preserving the input’s information. Methods combine phrase substitutions, language-model scores, and application-specific usability constraints, but evaluation and coverage remain difficult.
- Training data: Comparable news-article clusters provide approximate parallel data when large monolingual parallel corpora are unavailable.Articles about the same event may contain phrases, sentences, or longer fragments with similar meanings.
- Phrase-based generation: Translation-inspired generation scores candidate paraphrases using phrase deformations and a language model that favors grammatical outputs.The decoder returns the highest-scoring candidate, or several top candidates, from a lattice of licensed phrase replacements.
- Task adaptation: Identity deformations allow conservative paraphrasing, because assigning them high probability reduces phrase replacements.The phrase table may also include synonyms, extracted paraphrases, and templates.
- Task adaptation: Phrase tables can combine multiple resources, while an application-dependent usability model rewards outputs suited to the target task.For sentence compression, the usability model rewards candidates with fewer words than the input.
- Scope: SMT-inspired methods have been used mostly for paraphrase generation rather than textual-entailment generation.Adding hyponym-hypernym or entailment rules can generate one-directional entailment relations depending on replacement direction.
- Evaluation: Generation evaluation lacks widely adopted benchmarks, and recall is unavailable because the complete set of correct outputs is unknown.Human judgments can assess correctness and fluency, whereas current recognizers and machine-translation metrics are insufficient for reliable automatic evaluation.
4. Paraphrase and Textual Entailment Extraction
Extraction methods process corpora to produce paraphrase or entailment pairs and templates for later recognition, generation, or other applications. Approaches use distributional similarity, dependency paths, aligned sentences, and bilingual pivots, with precision and corpus requirements shaping their outputs.
- Overview: Extraction methods process large corpora to produce expression or template pairs that can support recognizers, generators, and applications such as statistical machine translation.Unlike recognition and generation, extraction methods are not given particular input expressions.
- Distributional Hypothesis: Distributional methods identify candidate paraphrases by comparing contexts of word n-grams or dependency paths, often using vector similarity and shared slot fillers.DIRT extracts dependency paths and pairs those occurring frequently with the same fillers.
- Distributional Hypothesis: DIRT’s syntactic paths begin and end with noun slots, are abstracted from dependency trees, and are paired when they recur with matching fillers.The method uses a mutual-information-based measure to score candidate path pairs.
- Distributional Hypothesis: Distributional extraction can confuse entailment or antonymy with paraphrase: DIRT links “X solves Y” with “X worsens Y,” while LEDIR classifies directionality.DIRT’s output pairs lack directionality and are often textual entailment pairs rather than paraphrases.
- Alignment: Alignment-based methods extract templates from aligned or comparable sentences, using matching anchors and dependency paths to obtain pairs more likely to be paraphrases.Ibrahim et al.’s method uses monolingual parallel corpora, while Shinyama and Sekine use named entities or referring noun phrases in comparable news clusters.
- Alignment: Pivot-language methods can produce millions of short paraphrase pairs from bilingual corpora, but alignment errors affect them; Zhao et al.’s classifier improves precision over DIRT and matches Bannard and Callison-Burch’s output size.Zhao et al.’s experiments report that 93% of generated paraphrases contain only one slot and that alignment sensitivity remains.
5. Conclusions
The survey organizes paraphrasing and textual entailment research around recognition, generation, and extraction methods. It finds shared foundations between generation and extraction, fewer generation benchmarks, and expected growth in cross-method and application-level integration.
- Scope: Paraphrasing can be viewed as bidirectional textual entailment, so the two areas often employ similar methods while targeting human judgments beyond strict logical entailment.Most methods operate at surface, syntactic, or shallow semantic levels.
- Recognition: Recognition commonly uses supervised learning to combine similarity measures across surface, syntactic, and semantic representations, while transformation-search approaches are also emerging.Recognition methods classify expression or template pairs as correct or incorrect.
- Generation: Generation methods mainly use bootstrapping or statistical machine translation ideas, but generation has fewer publications and no established challenges or benchmarks.Most generation work focuses on paraphrasing rather than unidirectional textual entailment.
- Extraction: Extraction methods usually build reusable corpus-derived resources such as phrase tables or rule collections, with many approaches based on the Distributional Hypothesis or alignment techniques.These resources can serve recognition, generation, statistical machine translation, and information extraction.
- Synthesis: Generation and extraction rely on largely similar underlying ideas, whereas recognition has relied on more distinct ideas; both generation and extraction have focused mostly on paraphrasing.The survey summarizes these task distributions in Table 3 and their typical resource requirements in Table 4.
- Future directions: The survey anticipates greater interplay among recognizers, generators, and extracted rules, alongside more use of these methods in question answering, information extraction, summarization, generation, and translation.It also notes that articles applying such methods to larger systems remain relatively few compared with method-proposal or in-vitro evaluation papers.
A.1 Bibliographic Resources, Portals, Tutorials
The survey points readers to bibliographic collections, tutorials, and portals that support research on paraphrasing and textual entailment.
- Tutorials: The ACL 2007 textual entailment tutorial provides an introductory resource for the field.The survey lists its URL as http://www.cs.biu.ac.il/∼dagan.
- Bibliographic resources: The ACL Anthology is listed as a bibliographic resource for locating relevant publications.The survey lists http://www.aclweb.org/anthology/.
- Portals: The Textual Entailment Portal is listed as an online portal for textual-entailment resources.The survey gives its ACL Wiki URL.
A.2 Corpora, Challenges, and their Datasets
The survey lists corpora, challenges, and datasets supporting paraphrase, textual entailment, translation, compression, and related evaluation or modeling tasks.
- Corpora: Cohn et al.’s paraphrase corpus provides word-aligned paraphrases.
- Datasets: FATE is the RTE-2 dataset with FrameNet annotations.
- Corpora: The MSR Paraphrase Corpus is listed as a benchmark dataset for paraphrase recognition.
- Corpora: The Multiple-Translation Chinese Corpus contains multiple English translations of Chinese news articles.
- Challenges: The RTE challenges and PASCAL Network of Excellence provide textual-entailment recognition challenges.
- Challenges: The RTE track of NIST’s Text Analysis Conference continues the PASCAL textual-entailment evaluation effort.
- Corpora: The Written News Compression Corpus is listed as a sentence-compression corpus.
A.3 Implementations of Machine Learning Algorithms
This section lists implementations of commonly used machine learning algorithms, including SVMs, maximum entropy classification, and broader algorithm collections.
- LIBSVM provides an implementation of support vector machines.
- Stanford distributes a maximum entropy classifier implementation.
- SVM-Light provides another implementation of support vector machines.
- Weka includes implementations of many machine learning algorithms.
A.4 Implementations of Similarity Measures
This section identifies resources for textual similarity and entailment, including edit-distance methods and WordNet-based similarity measures.
- EDITS recognizes textual entailment by computing edit distances.
- WordNet::Similarity implements WordNet-based similarity measures.
A.5 Parsers, POS Taggers, Named Entity Recognizers, Stemmers
This section points to tools for part-of-speech tagging, parsing, and named-entity recognition.
- Brill’s POS tagger provides part-of-speech tagging.
- The Link Grammar Parser provides parsing functionality.
- Stanford provides named-entity recognition, parsing, and tagging tools.
A.6 Statistical Machine Translation Tools and Resources
This section lists statistical machine translation tools and resources for word alignment, language modeling, and decoding.
- Giza++ is often used to train IBM models and align words.
- Koehn’s Statistical Machine Translation site provides pointers to commonly used SMT tools and resources.
- Moses is a frequently used SMT system that includes decoding facilities.
- SRILM is commonly used to create language models.
A.7 Lexical Resources, Paraphrasing and Textual Entailment Rules
The section lists lexical resources and paraphrasing or textual entailment rules, including corpus-derived, template-based, gloss-derived, and nominalization resources.
- Callison-Burch’s paraphrase rules are extracted from multilingual parallel corpora via pivot language(s).The implementation is also available online.
- DIRT provides template pairs, while TEASE provides textual entailment rules.
- Extended WordNet includes meaning representations extracted from WordNet’s glosses.
- Nomlex provides English nominalizations of verbs.
- Zhao et al.’s paraphrase rules use slots corresponding to part-of-speech tags and are extracted from multilingual parallel corpora via pivot language(s).