Significant Lexical Relationships

AAAI 1996

TL;DR

This paper introduces an "exact conditional test" for assessing the statistical significance of lexical relationships in natural language processing (NLP). Traditional significance tests often fail in NLP due to sparse and skewed data, leading to unreliable results. The proposed method provides a more accurate assessment by avoiding asymptotic approximations and is freely available.

What Problem Does This Paper Address?

Statistical Natural Language Processing (NLP) relies on analyzing large text corpora to understand language patterns. A crucial aspect of this is determining if observed relationships between words (like how often they appear together) are statistically significant or just due to chance. Traditional statistical significance tests, however, often make assumptions about data distribution (e.g., large counts, no zeros) that are frequently violated in NLP. This is because many word combinations (bigrams) are rare, leading to sparse data with many zero counts. When these assumptions are broken, the significance values calculated by these tests can be incorrect, leading to flawed conclusions about lexical relationships. This paper aims to provide a more robust and reliable method for assessing statistical significance in NLP contexts.

Methods

The core contribution is the introduction and application of an exact conditional test. This test addresses the limitations of traditional methods by:

  • Avoiding Asymptotic Approximations: Instead of relying on approximations (like the chi-squared or normal distributions) that assume large sample sizes and specific data distributions, the exact conditional test directly calculates the probability of observing the data (or more extreme data) under the null hypothesis.
  • Monte Carlo Sampling: The exact distribution of a test statistic is generated using a Monte Carlo sampling scheme. This involves:
  • Generating many random samples of data that have the same marginal totals as the observed data.
  • Calculating the test statistic for each of these generated samples.
  • Determining the significance value by comparing the observed test statistic to the distribution of statistics from the generated samples.
  • Freely Available Software: The authors highlight that this method can be implemented using the freely available software package "CoCo."

The paper also discusses and contrasts this with standard goodness-of-fit statistics like the likelihood ratio statistic ($G^2$) and Pearson's chi-squared statistic ($X^2$), as well as the t-statistic, all of which are often used with asymptotic approximations.

Datasets

The paper uses subsets of the ACL/DCI Wall Street Journal corpus for its experiments. Specifically:

  • For the association test: a 1.38 million word subset.
  • For the bigram difference test and extended bigram difference test: a 928,000 word subset.

The paper does not introduce new benchmark datasets but rather applies its methodology to existing, commonly used NLP corpora.

Key Insights and Ideas

  • NLP Data is Special (and Problematic for Old Tests): The paper strongly emphasizes that the sparse and skewed nature of NLP data (due to rare events and Zipf's Law) fundamentally violates the assumptions of many traditional statistical tests. This is a critical insight for anyone working with linguistic data.
  • Asymptotic Approximations Can Be Misleading: When the assumptions of asymptotic tests are violated, the significance values they produce can be incorrect. This means researchers might incorrectly conclude a relationship is significant when it's not, or vice-versa.
  • Exactness Matters: The "exact conditional test" provides a more reliable assessment because it doesn't depend on these often-violated assumptions. It directly computes probabilities based on the observed data's structure.
  • Different Tests Yield Different Results: The experiments clearly show that the exact conditional test often assigns different significance values compared to the asymptotic tests, underscoring the problem with the latter.

Key Results

The paper demonstrates the practical implications of using the exact conditional test through experiments on lexical relationships:

  • Association Test: For the bigram "new industry," the exact conditional test assigned a different significance value than the asymptotic tests. This difference is highlighted as an indicator of the failure of asymptotic approximations.
  • Bigram Difference Test: For the bigrams "<word> came" and "<word> went," when the counts were very close (e.g., differing by only one), the exact conditional test assigned a significance of 1.00, indicating no evidence of difference. In contrast, asymptotic tests assigned lower values, suggesting a difference where the exact test found none.
  • Extended Bigram Difference Test: For a 2x237 contingency table, the asymptotic approximations for $X^2$ and $G^2$ yielded significance values of .292 and .000, respectively. The exact conditional test, however, assigned a significance of .0670. This large discrepancy further illustrates the unreliability of asymptotic methods on complex NLP data.

Limitations and Future Work

  • Computational Cost: While the paper advocates for the exact conditional test, it implicitly acknowledges that generating exact distributions can be computationally intensive, especially for very large tables. The Monte Carlo approach helps mitigate this.
  • Scope of Application: The paper focuses on bigram relationships and specific types of tests (association, difference). Future work could explore the application of this exact testing methodology to more complex linguistic structures or different types of statistical models in NLP.
  • Software Availability: The reliance on the "CoCo" software package is noted. While it's freely available, its integration into broader NLP toolkits or its accessibility to a wider range of users could be a point for future development.

Summary updated

BibTeX
@inproceedings{1996significant,
  title = {{Significant Lexical Relationships}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure