A Bio-Inspired Approach for Multi-Word Expression Extraction

Jianyong Duan, Ruzhan Lu, Weilin Wu, Yi Hu, Yan TianACL 2006

Abstract

Multi-Word Expression (MWE) extraction is a fundamental challenge in Natural Language Processing, particularly for "flexible" expressions where words are separated by arbitrary gaps. This paper presents a bio-inspired approach using Longest Common Subsequence (LCS) and affine gap models, typically used in DNA sequence alignment. By integrating linguistic knowledge via Embedded Base Phrase (EBP) detection, the model effectively identifies flexible MWEs. Experimental results demonstrate that the LCS-based method significantly outperforms traditional n-gram approaches in recall, achieving up to 83.1% recall on manual test sets.

Introduction

Multi-Word Expressions (MWEs)—which include idioms, collocations, and technical terms—are notoriously difficult to extract automatically. While some MWEs are "strict" (words always appear together in order), many are "flexible." For example, in the expression "make a decision," a speaker might say "make a very difficult decision."

Traditional extraction methods rely heavily on n-grams, which look at contiguous sequences of $n$ words. These models struggle with flexible MWEs because the "gap" between words can be of arbitrary length, leading to data sparseness. If the window is too small, you miss the connection; if it's too large, the computational complexity and noise explode. This research seeks a method that can handle these gaps gracefully without losing efficiency.

Methods

The authors propose a "bio-inspired" model based on the Longest Common Subsequence (LCS) theory, specifically the affine gap model used in bioinformatics to align DNA or protein sequences. The core insight is that structural variations in human language (insertions, deletions, and reordering) mirror the mutations found in genetic sequences.

  1. Pairwise Sequence Alignment: Using dynamic programming, the algorithm compares two textual sequences to find the best local alignment. It uses three specific arrays ($G, E, F$) to track matches and manage "penalties" for gaps (insertions or deletions).
  2. Star-Alignment: After finding pairs, the system performs multiple sequence alignment to identify common patterns across a larger set of candidate sequences.
  3. Linguistic Knowledge Integration: Instead of a flat penalty for any gap, the model uses a Context-Free Grammar (CFG) to identify if a gap contains a valid linguistic unit, known as an Embedded Base Phrase (EBP). If the gap is a "meaningful" phrase, the penalty is lowered, allowing the model to "jump" over it to connect the parts of a flexible MWE.

Experimental Setup

The model was evaluated using a general corpus of 200,000 sentences collected from the internet. A gold standard reference list of nearly 70,000 MWEs was compiled from WordNet and other dictionaries. For precise evaluation, a "Close Test Set" of 8,000 sentences was manually annotated by experts to provide a ground truth for performance metrics.

Results and Discussion

The authors compared their LCS approach against the traditional n-gram method using several statistical measures: Frequency, TMI, ME, and Rankratio.

Performance comparison of N-Gram and LCS methods across various statistical measures.

As shown in the table above, the LCS approach consistently outperformed n-grams in recall. For example, using the "Rankratio" measure, LCS achieved 83.1% recall compared to the n-gram's 61.5%. This "flexible" advantage allows LCS to unify patterns that n-grams simply cannot detect due to model limitations.

MWU extraction count vs. corpus size for N-Gram and LCS methods.

In scalability tests, as the corpus size increased, the LCS method consistently identified a higher number of MWEs than the n-gram method. While the LCS model is highly flexible, it occasionally identifies coincidental word alignments as MWEs, leading to a trade-off where precision is slightly lower than the n-gram method. However, the substantial gain in recall makes it a more robust choice for comprehensive MWE discovery.

Conclusion

By treating text as genetic code and applying sequence alignment algorithms, this approach effectively bridges the gap in flexible MWE extraction. While precision remains a challenge due to the model's inherent flexibility, the significant boost in recall and the ability to handle structured linguistic gaps represent a major advancement over traditional n-gram models. Future work will focus on further refining linguistic gap penalties to reduce noise.

Summary updated

BibTeX
@inproceedings{duan2006bio,
  author = {Jianyong Duan and Ruzhan Lu and Weilin Wu and Yi Hu and Yan Tian},
  title = {{A Bio-Inspired Approach for Multi-Word Expression Extraction}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
}
Figure