TL;DR
This paper introduces a novel syntax-based algorithm to automatically build Finite State Automata (FSAs) from sets of semantically equivalent translations. These FSAs compactly represent paraphrases, enabling the extraction of lexical and structural paraphrase pairs, and the generation of new, unseen sentences with the same meaning.
What Problem Does This Paper Address?
Paraphrasing is crucial for various NLP tasks like information retrieval, natural language generation, and question answering. Previous methods often represented paraphrases as simple pairs or sets of words/phrases, which were too limited for generating new sentences. The challenge was to find a more robust and generative representation of paraphrases that could capture complex semantic equivalences and handle variations in sentence structure.
Methods
The core of the paper is a new syntax-based alignment algorithm that constructs FSAs from multiple translations of the same sentence. The algorithm works in three main steps:
- Top-down Merging of Parse Trees: It first parses each sentence in a group into a parse tree and then merges these trees into a "parse forest." This merging process recursively aligns corresponding syntactic constituents (like NP and VP) that are assumed to be paraphrases.
- Keyword Checking: To prevent erroneous alignments due to strict syntactic matching, a keyword checking mechanism is employed. This filter uses lists of keywords (nouns, verbs, adjectives) within syntactic nodes to identify potential mismatches and stop merging if conflicting keywords are found.
- Squeezing: An additional step to further compact the FSA. If two different edges in the FSA are labeled with the same word and lead to the same node, the nodes are merged. This helps reduce redundancy and discover new paraphrases.
The algorithm then maps the resulting parse forest into a Finite State Automaton (FSA), which is then "squeezed" for compactness.
Datasets
The primary dataset used is the LDC-available Multiple-Translation Chinese (MTC) Corpus. This corpus contains 105 news stories, each with 11 semantically equivalent English translations from different agencies. The authors used 899 sentence groups from this corpus, filtering out sentences longer than 45 words.
Key Insights and Ideas
- FSAs as Compact Paraphrase Representations: The paper demonstrates that FSAs can compactly encode a vast number of paraphrases, far exceeding simple pair-based representations.
- Syntax-Driven Alignment: Leveraging syntactic parse trees provides a structured way to align semantically equivalent phrases, capturing both lexical and structural paraphrases.
- Squeezing for Discovery: The "squeezing" operation, while seemingly for compression, also reveals new paraphrases that might not have been directly apparent from the initial top-down merging.
- Beyond Lexical Synonymy: The research highlights that paraphrasing is a richer and looser relation than strict synonymy, as evidenced by the large number of paraphrases found that are not WordNet synonyms.
Key Results
- Human Evaluation: Human judges rated the paraphrases extracted by the syntax-based algorithm as "Correct" significantly more often (81% average) than those from a co-training-based algorithm (66% average).
- WordNet Analysis: The algorithm discovered many paraphrases not identified as synonyms in WordNet, suggesting its ability to capture broader semantic equivalences.
- FSA Quality: Language model-based evaluation showed that the sentences generated from the FSAs had an average entropy similar to the original sentences, indicating they are well-formed and semantically coherent.
- MT Evaluation Potential: The FSAs showed promise for evaluating machine translation systems by measuring edit distance between a test sentence and the FSA, demonstrating a significant gain in predictive power compared to using raw sentence sets.
Limitations and Future Work
- Parameter Tuning: The authors acknowledge that the co-training algorithm was not optimally tuned for their specific corpus, which might have affected its performance comparison.
- Recall vs. Precision: The paper notes that they are not comparing accuracy at the same recall level, as their algorithm extracted fewer unique paraphrase pairs but with higher precision.
- Future Work: The authors plan to experiment with more flexible merging algorithms, better integrate top-down and bottom-up processes, and extract more abstract paraphrase patterns. They also aim to conduct more extrinsic evaluations to assess the FSAs' utility in improving agreement scores between human and automatic MT evaluations.
Summary updated