One-sentence Summary

This work presents an empirical comparison of distributional similarity measures, a classification of these functions based on the information they incorporate, and a novel function that better evaluates potential proxy distributions for improving probability estimation of unseen cooccurrences.

Key Contributions

• The paper compares a broad range of distributional similarity measures for estimating probabilities of unseen cooccurrences through distance-weighted averaging, using a parameter-free evaluation methodology that factors out inessential degrees of freedom.

• The paper classifies similarity functions according to the information they incorporate, showing that performance groups correspond to how strongly the functions emphasize the intersection of the supports of the compared distributions.

• The paper introduces the skew divergence, an asymmetric information-theoretic metric that incorporates support-intersection data; it achieved the best overall performance, reducing the average error rate by 4 percent relative to the Jensen-Shannon divergence at the .01 significance level.

Introduction

Statistical natural language processing often relies on finite corpora, so plausible but unseen word pairs can be assigned zero probability, which matters for language modeling and smoothing. Existing methods such as Katz backoff and Jelinek and Mercer interpolation often estimate unseen conditional probabilities from marginal counts and effectively ignore the identity of the conditioning context. The authors build on distance-weighted averaging, which borrows estimates from distributionally similar words, and address uncertainty about whether the choice of similarity metric really matters. Their main contributions are an empirical comparison of similarity measures, a proposed way to classify them by their treatment of support intersection, and a new metric, the skew divergence, which incorporates this insight and improves prediction of unseen cooccurrences.

Dataset

• The authors use a lexical semantic dataset built from verb-object cooccurrence pairs extracted from the 1988 Associated Press newswire.

• The pairs are restricted to the 1,000 most frequent nouns and were extracted using Church’s and Yarowsky’s processing tools.

• The dataset is split into an 80% training set and a 20% held-out test set.

• The training set contains 587,833 pairs and is used to calculate base cooccurrence probabilities.

• The remaining 20% forms the evaluation data. Before testing, the authors discard any pairs that also appear in the training set, ensuring that test items are unseen pairs.

• The held-out pairs are then split into five partitions.

• For evaluation, each test pair is converted into a noun-verb-verb triple. A noun-verb pair (n, v1) is expanded to (n, v1, v2), where v2 is chosen so that its unigram probability approximates that of v1.

• The original cooccurrence is always treated as the correct alternative, while the added distractor verb is balanced to avoid simple frequency-based shortcuts.

• The schema is therefore centered on noun-verb cooccurrences, with test examples represented as triples of the form (noun, original verb, distractor verb).

• The data is used to evaluate similarity functions on a binary choice task: decide which of the two verb alternatives was the original cooccurrence.

• There is no mention of cropping, metadata construction, or multi-modal processing; the main processing is pair extraction, frequency-based filtering, train/test splitting, duplicate removal from the test set, and construction of balanced distractor triples.

Method

The authors leverage a distributional similarity framework in which candidate word pairs are scored by comparing their empirical context distributions. For concreteness, they instantiate the approach over pairs of nouns and transitive verbs. A cooccurrence event is recorded when a noun appears as the head noun of the direct object of a verb. Given a base language model with probability function $P$P, they define the conditional distribution of verb contexts for a noun as $q(v)=P(v|n)$q(v)=P(v∣n). For another noun $m$m, the corresponding distribution is $r(v)=P(v|m)$r(v)=P(v∣m). In their implementation, $P$P is derived from unsmoothed relative frequencies computed from corpus counts. The resulting vectors $q$q and $r$r represent the verb-context profiles of the two nouns, and the task becomes measuring how similar or mutually substitutable these profiles are.

The initial similarity module evaluates several established distributional association functions. The Euclidean and $L_1$L1​ distance functions compare probability values directly:

The cosine similarity measures directional agreement between the two distributions:

Jaccard’s coefficient is more combinatorial. It depends only on the supports of $q$q, $r$r, and their intersection:

The Jensen-Shannon divergence is defined through an averaged distribution:

where the KL divergence is

The use of the averaged distribution ensures that the Jensen-Shannon divergence remains well defined even when the support of one distribution is not contained in the support of the other.

The framework also includes the confusion probability, which incorporates unigram context probabilities in addition to the two conditional distributions. It measures the extent to which one noun can be substituted into the contexts associated with another:

Another candidate is Kendall’s $\tau$τ, a nonparametric measure that evaluates the correlation between the orderings induced by $q$q and $r$r over verbs. Using the simplest variant,

A value near $1$1 indicates that the two nouns induce similar verb-orderings, while a value near $-1$−1 indicates strongly opposing orderings. The method treats a value of $-1$−1 as evidence of strong dissimilarity.

A key methodological insight is that lexical substitutability is often asymmetric. For example, one word may provide a strong approximation for another, while the reverse substitution may be poor. Most candidate functions compared in the framework are symmetric, meaning that $f(q,r)=f(r,q)$f(q,r)=f(r,q). To capture directional substitutability, the authors introduce an asymmetric divergence called the $\alpha$α-skew divergence:

where $0 \leq \alpha \leq 1$0≤α≤1. This formulation generalizes the KL divergence. When $\alpha=1$α=1, the skew divergence becomes exactly the KL divergence $D(r||q)$D(r∣∣q). The parameter $\alpha$α can be interpreted as a confidence level in the distribution $q$q. Equivalently, $1-\alpha$1−α controls how much smoothing is applied by mixing $q$q with $r$r. This design is useful in sparse settings where direct KL computation may be unstable or undefined because the support conditions are not satisfied.

At $\alpha=1/2$α=1/2, the skew divergence is related to one of the two terms in the Jensen-Shannon divergence, but it remains asymmetric. Thus, the method preserves the directional nature of substitutability while avoiding some of the instability of raw KL divergence.

As shown in the figure below:

The plotted performance curves compare the $\alpha=0.99$α=0.99 skew divergence against other similarity functions as the parameter $k$k varies. The average error rate is lower for the skew divergence across many settings, indicating that the asymmetric formulation provides stronger ranking behavior for noun substitution. The comparison illustrates the central design choice of the method: rather than relying only on symmetric proximity measures, the final scoring component uses a smoothed asymmetric divergence that emphasizes the direction in which one word distribution can approximate another.

Experiment

The experiments compare distributional similarity measures in a binary selection task over unseen noun-verb cooccurrences, then assess a proposed asymmetric skew divergence within the same framework. The empirical comparison shows that measures emphasizing shared cooccurrence evidence tend to rank nearest neighbors more effectively than those sensitive to non-shared or out-of-support verbs, while all compared measures outperform a simple backoff baseline. The skew divergence validation suggests that asymmetry and selective smoothing improve predictive ranking, supporting the conclusion that similarity for sparse linguistic data benefits from focusing on the intersection of distribution supports.

In the empirical evaluation on unseen verb-object evidence, the skew divergence with near-one weighting performs better than the other compared similarity functions on the binary selection task. The strongest functions appear to be those that emphasize shared verb supports, while negative evidence from verbs appearing with only one noun seems less important. Skew divergence outperforms the other listed similarity measures on the noun-verb-verb prediction task. Better performance is associated with a focus on the intersection of supports rather than non-shared verb evidence.

The experiments compare similarity functions on unseen verb-object evidence using binary selection and noun-verb-verb prediction tasks. Skew divergence with near-one weighting achieves the strongest results, indicating that measuring shared verb supports is more effective than weighing non-shared or negative evidence. Overall, methods that emphasize the intersection of supports outperform those that rely more heavily on verbs unique to a single noun.