📄 Distributional Clustering of English Words

Summary

The paper tackles data sparseness in statistical language models. Most verb–object pairs occur rarely or never in a corpus, so raw counts are poor estimates of their probabilities. The authors group nouns into probabilistic ("soft") clusters based on the verbs that take them as direct objects. Each noun is represented by its conditional distribution over verbs. Nouns are compared to cluster centroids with relative entropy (KL distance), and each centroid is a membership-weighted average of noun distributions. Memberships come from a maximum-entropy principle, and centroids are fitted by maximum likelihood. Deterministic annealing raises a control parameter so that clusters split step by step, producing a hierarchy. The main evaluation uses verb–object pairs from 1988 AP newswire. Held-out relative entropy improves up to roughly 206 clusters, after which larger models overfit. The clusters also give useful predictions for nouns that were never clustered and for verb–object pairs deleted from training. The work matters because it shows that word classes can be learned purely from co-occurrence statistics and used directly to smooth sparse association models.

Key points

• Data came from two pipelines. One used newswire parsed with Hindle's parser Fidditch. The other used a part-of-speech tagger (Church, 1988) plus regex-style pattern matching over tagged text (Yarowsky, 1992). Known errors were filtered out, such as complement-clause subjects of "say"-type verbs being mistaken for direct objects.
• The main evaluation corpus consisted of Associated Press newswire text from 1988, totaling 44 million words:
  • It yielded 1,112,041 verb–object pairs.
  • Clustering used pairs involving the 1000 most frequent nouns.
  • These were split into 756,721 training pairs and 81,240 test pairs.
• Training-set relative entropy falls steadily as clusters are added. Test-set relative entropy is lowest at 206 clusters.
• For 1000 additional nouns that were never clustered, the cluster model provides more than one bit of information about their verb preferences. Overfitting is sharper on this set.
• A verb-choice task was built by deleting 104 noun–verb pairs (verbs with 500–5000 occurrences) from training. Models were scored by error rate, both on all triples and on "exceptional" triples where verb frequency alone predicts the wrong answer.

Interesting ideas

• I1. Comparing words only to centroids sidesteps zero counts. Each word is measured against averaged cluster distributions, never against another word, so KL divergence stays defined without extra smoothing. This is a handy trick for any KL-based clustering of sparse count data.
• I2. Annealing yields a hierarchy for free. Gradually increasing the annealing parameter makes clusters split, so a coarse-to-fine soft hierarchy emerges without a separate agglomerative step. This could help with organizing lexicons or product and place categories at several levels of detail.
• I3. Folding in unseen items without retraining. A new noun gets membership probabilities from its divergence to the existing centroids, which tests whether clusters learned on frequent words carry over to rarer ones. This is a cheap way to extend a model to new vocabulary.
• I4. Delete-and-reconstruct evaluation. Known pairs are removed from training, and the model is checked on whether it recovers the original verb preference. Reporting the cases where the frequency baseline fails shows real gains over the trivial model.
• I5. Clusters as hidden units for relations. The authors frame clustering as factoring any relation between two sets through latent classes. The same factorization could model other pairwise associations, such as trade partners or region–attribute links.