Abstract
Computing statistical dependence of terms in textual documents is a widely studied subject and a core problem in many areas of science. This study focuses on such a problem and explores the techniques of estimation using the expected mutual information measure. A general framework is established for tackling a variety of estimations: (i) general forms of estimation functions are introduced; (ii) a set of constraints for the estimation functions is discussed; (iii) general forms of probability distributions are defined; (iv) general forms of the measures for calculating mutual information of terms (MIT) are formalised; (v) properties of the MIT measures are studied and, (vi) relations between the MIT measures are revealed. Four estimation methods, as examples, are proposed and mathematical meanings of the individual methods are respectively interpreted. The methods may be directly applied to practical problems for computing dependence values of individual term pairs. Due to its generality, our method is applicable to various areas, involving statistical semantic analysis of textual data.
Introduction
In Information Retrieval (IR) and Natural Language Processing (NLP), quantifying the statistical dependence between terms is fundamental. The Expected Mutual Information Measure (EMIM) is a standard tool for this purpose. However, a significant challenge exists: the "true" probability distribution of terms in a language is unknown. Researchers must rely on samples (training data) to estimate these distributions.
Often, raw frequencies are plugged into Mutual Information (MI) formulas without verifying if these estimates constitute valid probability distributions. This "black box" approach can lead to mathematically inconsistent or unreliable results. This paper addresses this gap by establishing a formal framework for estimating the probability distributions required for computing the Mutual Information of Terms (MIT), ensuring mathematical consistency and providing transparency into term-dependence modeling.
The MIT Estimation Framework
The framework centers on two general estimation functions:
- $\psi_\Xi(t)$: Estimates the marginal probability that a term $t$ is present in a document or collection.
- $\gamma_\Xi(t_i, t_j)$: Estimates the joint probability that both terms $t_i$ and $t_j$ are present.
The authors formalize MIT as a decomposition of the total EMIM. While EMIM is typically calculated as a single sum, the MIT approach examines the contribution of four distinct states:
- Both terms present $(1,1)$
- Term $t_i$ present, $t_j$ absent $(1,0)$
- Term $t_i$ absent, $t_j$ present $(0,1)$
- Both terms absent $(0,0)$
Proposed Estimation Methods
To demonstrate the framework's utility, the authors propose four specific estimation methods. These methods range from frequency-based products within a single document to binary co-occurrence across a document collection.
As shown in the table above, Methods 1 and 2 utilize document-level frequencies and combinatorics. Method 3 employs conditional probability based on term frequency, while Method 4 represents the traditional "Binary" approach common in IR, focusing on co-occurrence across a set of documents.
Mathematical Validity and Constraints
A core contribution of this work is the definition of "Validity Constraints." For an MI calculation to be mathematically sound, the joint probability $\gamma$ must not exceed the marginal probabilities $\psi$. If an estimation method violates this, the resulting "Mutual Information" value becomes meaningless.
The paper provides several key theoretical results:
- Theorems 2.1 & 2.2: These prove that if the proposed constraints are met, the functions form a valid, "absolutely continuous" probability distribution.
- Theorem 3.1: This establishes the relationship between the sign of the MIT measures and underlying term frequencies. If $\gamma(t_i, t_j) > \psi(t_i)\psi(t_j)$, the terms exhibit positive dependence.
- Corollaries 4.1–4.4: These provide specific "safety conditions" for the example methods. For instance, Method 2 is valid only if the term frequency $f_d(t)$ is less than half the document length minus one ($\frac{||d||-1}{2}$).
Insights and Future Directions
The framework reveals that "term dependence" is not an absolute property but is sensitive to the chosen estimation function. Two terms might appear highly dependent under one method but independent under another. By decomposing EMIM into four MIT components, researchers can better understand the nature of term relationships—whether they are driven by co-presence or consistent co-absence.
While the framework provides the "rules of the road," selecting the optimal estimation function for specific tasks like sentiment analysis or document clustering remains an area for empirical investigation. Future work includes applying these MIT measures to quantitative document representations (e.g., TF-IDF weighting) and testing their performance in large-scale NLP pipelines.
Summary updated