TL;DR
This paper introduces a novel method for automatically learning "structural paraphrases" – fragments of syntactic trees that are semantically equivalent – from aligned monolingual corpora. This approach aims to overcome limitations of previous methods by leveraging syntactic structures to capture longer-distance dependencies and more nuanced semantic equivalences, with potential applications in question answering.
What Problem Does This Paper Address?
Human language is incredibly flexible, allowing us to express the same idea in countless ways. This variability poses a significant challenge for natural language processing (NLP) systems, particularly in applications like question answering (QA). A QA system needs to understand that "When did Colorado become a state?" and "When was Colorado admitted to the Union?" are asking the same thing. While resources exist for single-word synonyms (like WordNet), acquiring paraphrases for phrases and sentences is much harder. Manually creating such resources is time-consuming and impractical for large-scale applications. Therefore, the paper addresses the problem of automatically learning these paraphrases, focusing on "structural paraphrases" which capture syntactic relationships, rather than just lexical substitutions.
Methods
The core of the proposed method lies in leveraging aligned monolingual corpora, specifically multiple translations of the same text. The intuition is that differences in wording between aligned sentences, which convey the same meaning, can reveal paraphrases.
- Corpus Alignment: The process begins by aligning sentences from parallel texts (e.g., different translations of novels) using the Gale and Church algorithm.
- Parsing and Postprocessing: Aligned sentences are then parsed using the Link Parser, a dependency-based parser. The resulting parse structures are post-processed to ensure consistency, for instance, by correctly identifying subjects in passive sentences and handling verb particles.
- Paraphrase Extraction:
- Anchor Identification: The process identifies "anchors" within aligned sentence pairs, primarily focusing on nouns and pronouns. A scoring mechanism with heuristics is used to determine correspondence between anchors (e.g., exact string matches, matching pronouns, unique semantic classes).
- Path Finding: For each pair of anchors, a breadth-first search finds the shortest syntactic path between them in the dependency trees. Paths containing conjunctions or punctuation are rejected.
- Candidate Paraphrase Generation: If valid paths are found between anchor pairs in both aligned sentences, these paths are considered candidate structural paraphrases.
- Scoring: Candidate paraphrases are scored based on the frequency of their associated anchors and the variety of anchor pairs from which they were derived. This scoring mechanism aims to favor more robust and frequently observed paraphrases.
This approach synthesizes techniques from previous work (Barzilay & McKeown, Lin & Pantel) by using syntactic structures for richer representations and aligned corpora for computational tractability.
Datasets
The primary dataset used is a collection of aligned monolingual corpora, specifically multiple English translations of foreign novels. Examples include:
- Twenty Thousand Leagues Under the Sea (two translations)
- The Kreutzer Sonata (two translations)
- Madame Bouvary (three translations)
The authors note that this corpus is similar to that used by Barzilay and McKeown, with the exclusion of short fairy tales deemed unsuitable.
Key Insights and Ideas
- Structural vs. Lexical Paraphrases: The paper argues that structural paraphrases, which capture syntactic relationships, offer significant advantages over purely lexical paraphrases. They can capture long-distance dependencies and are more robust to morphological and syntactic variations.
- Syntactic Structure as Context: Syntactic structures can encapsulate a richer context than simple lexical phrases, leading to more accurate paraphrase identification.
- Leveraging Parallel Translations: Using multiple translations of the same text provides a valuable resource for learning paraphrases by exploiting variations in surface form while preserving semantic content.
- Anchor-Based Path Generalization: Identifying corresponding "anchors" (nouns/pronouns) and then generalizing the syntactic paths between them is a powerful mechanism for discovering structural paraphrases.
- The Challenge of "Interchangeability": The authors adopt a definition of paraphrases as being "roughly interchangeable" within a specific syntactic configuration, acknowledging that the exact definition can be debated.
Key Results
- The system extracted nearly 6,000 different paraphrases from the corpus.
- Human evaluation of 130 unique paraphrases yielded an average precision of 41.2%.
- The average length of learned paraphrases was 3.26 words.
- The highest-scoring paraphrase identified was the equivalence of the possessive morpheme 's with the preposition "of" (e.g., A's B ⇔ B of A).
- The study found that increasing the score threshold for paraphrases generally increased precision up to a point, after which it decreased.
- Inter-assessor agreement among human evaluators was moderate (75.4% agreement), suggesting the subjective nature of judging paraphrases.
Limitations and Future Work
- Dependence on Parse Quality: The accuracy of the generated paraphrases is highly dependent on the quality of the parser. Poor parses lead to bogus paraphrases.
- Data Sparseness: Paraphrases are relatively sparse, and without sufficient statistical evidence, validating candidate paraphrases is difficult. The genre-specific nature of paraphrases also means different applications might require different training corpora.
- Constituency and Verb Phrases: The algorithm could benefit from a better notion of constituency and handling of verb phrases, as it sometimes generates non-sensical paraphrases by crossing constituent boundaries and misses paraphrases by not including "not" in verb phrase comparisons (e.g., fail ⇔ succeed).
- Optimal Level of Structure: Determining the optimal level of syntactic structure for paraphrases is an open question, representing a tradeoff between specificity and accuracy.
- Generalization of Variables: The algorithm struggles to generalize constituents as variables due to data sparseness.
- Future Work:
- Comparing different parsers.
- Extending the approach to non-parallel corpora to address data sparseness.
- Combining paraphrase generation with relation-indexing for question answering.
- Developing better mechanisms for generalizing constituents as variables with more data.
Summary updated