Three Knowledge-Free Methods for Automatic Lexical Chain Extraction

Steffen Remus, Chris BiemannNAACL 2013

TL;DR

This paper introduces three novel, knowledge-free methods for automatically extracting "lexical chains" – sequences of semantically related words that form the backbone of text coherence. These methods, based on Latent Dirichlet Allocation (LDA) topic modeling, significantly outperform traditional knowledge-based approaches, especially for under-resourced languages and domains, by adapting to the text's inherent structure rather than relying on external, potentially incomplete, lexicons.

What Problem Does This Paper Address?

Understanding how a text "hangs together" is crucial for many Natural Language Processing (NLP) tasks, from summarization to question answering. This coherence is often achieved through cohesion, where words or phrases are linked semantically. Lexical chains are a way to represent these cohesive ties, grouping semantically related terms.

Traditional methods for extracting these chains heavily rely on external knowledge resources like WordNet or Roget's Thesaurus. While effective, these approaches suffer from a significant drawback: their performance is directly tied to the coverage of these resources. This makes them less effective for languages with limited lexical resources or for specialized domains where general-purpose thesauri might not capture domain-specific terminology. The paper aims to address this by developing knowledge-free methods that can extract lexical chains directly from the text itself, making them more adaptable and robust.

Methods

The core of this paper lies in three novel methods for lexical chain extraction, all leveraging Latent Dirichlet Allocation (LDA), a probabilistic topic model. LDA represents documents as mixtures of topics, and topics as distributions over words.

  1. LDA Mode Method (LDA-MM): This approach assigns each word token in a document to a chain based on the mode (most frequent assignment) of its topic distribution across multiple LDA samples. This helps to reduce the variance in topic assignments and implicitly disambiguates words by grouping them based on their dominant topic.
  2. LDA Graph Method (LDA-GM): This method first constructs a similarity graph where nodes are candidate lexical items and edge weights represent the semantic relatedness between their per-word topic distributions (derived from LDA). A graph clustering algorithm (Chinese Whispers) is then applied to identify lexical chains as clusters within this graph.
  3. LDA Top-N Method (LDA-TM): This approach uses the per-document topic distribution and per-topic word distribution from LDA. It chains the top m words from the top n topics identified for a given document. This method also incorporates thresholding parameters to adapt n and m to individual documents, aiming for more document-specific chain generation.

A two-level annotation scheme was developed, distinguishing between "dense chains" (where all items are directly related) and "merged chains" (which incorporate "level two links" connecting distinct dense chains). A new lexical chain comparison measure (lccm), combining the Adjusted Rand Index (ARI) and Normalized Basic Merge Distance (NBMD), was also proposed for intrinsic evaluation.

Datasets

The paper uses a manually annotated dataset of German news documents from the SALSA 2.0 corpus, which is based on the TIGER Treebank 2.1. This corpus consists of approximately 1,550 documents and 50,000 sentences. For training the LDA models, a larger corpus of 13,457 German news texts from the "Frankfurter Rundschau" newspaper (around 1992 and 1997) was used.

Key Insights and Ideas

  • Knowledge-free is the way forward: Statistical methods, particularly those based on topic modeling, can significantly outperform knowledge-based methods for lexical chain extraction, especially when external resources are limited.
  • Adaptability is key: LDA-based methods adapt to the specific vocabulary and thematic structure of a given text or domain, making them more robust than fixed knowledge bases.
  • Intrinsic evaluation matters: Developing a dedicated measure (lccm) for comparing lexical chains allows for direct evaluation of the chaining task itself, rather than relying solely on downstream task performance.
  • Different methods, different strengths: The three LDA-based methods exhibit distinct chaining behaviors, with LDA-MM excelling in coverage, LDA-GM in generating dense chains, and LDA-TM producing longer chains. This suggests that the choice of method can be tailored to specific application needs.
  • Subjectivity is inherent: Lexical chain annotation is inherently subjective, making high inter-annotator agreement difficult to achieve. This highlights the importance of robust evaluation metrics and methods that can handle this variability.

Key Results

The three proposed LDA-based methods significantly outperformed a random baseline and two knowledge-based baselines (S&M GermaNet and G&M GermaNet) on the manually annotated German news corpus.

  • Dense Chains: The LDA-GM method achieved the highest average lccm score (0.321), followed closely by LDA-MM (0.313) and LDA-TM (0.303). These were substantially higher than the knowledge-based baselines (around 0.235 and 0.229) and the random baseline (0.135).
  • Merged Chains: In the evaluation of merged chains (incorporating level two links), the LDA-MM method emerged as the clear winner, achieving an average lccm of 0.308. This suggests its strength in creating broader, more interconnected chains.
  • Coverage vs. Specificity: The knowledge-based systems struggled due to the limited coverage of GermaNet, while the LDA-based methods, by learning from the text, achieved better coverage.

Limitations and Future Work

  • Candidate Item Selection: The paper acknowledges that their POS-pattern-based method for selecting candidate lexical items is a heuristic that can over-generate, particularly with compositional adjective modifiers. Future work could focus on defining better filters for this selection process.
  • Compound Words: For languages like German, which heavily use compound words, the authors suggest decomposing these compounds to link their heads in lexical chains.
  • Application-specific evaluation: While the paper advocates for intrinsic evaluation, a natural next step is to use the developed methods as pre-processing steps for downstream NLP applications like summarization, text segmentation, or word sense disambiguation to assess their practical utility.
  • Parameter Optimization: The paper mentions that the LDA-GM method excelled in dense chain evaluation, but LDA-TM was inferior. Further investigation into why this occurred and how to optimize parameters for different chain types could be beneficial.

Summary updated

BibTeX
@inproceedings{remus2013three,
  author = {Steffen Remus and Chris Biemann},
  title = {{Three Knowledge-Free Methods for Automatic Lexical Chain Extraction}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2013},
}
Figure