Distributional Similarity Models: Clustering vs. Nearest Neighbors

Distributional Similarity Models: Clustering vs. Nearest Neighbors Lillian Lee Department of Computer Science Cornell University Ithaca, NY 14853-7501 llee@cs, cornell, edu Fernando Pereira A247, AT&T Labs - Research 180 Park Avenue Florham Park, NJ 07932-0971 pereira@research, att. com Abstract Distributional similarity is a useful notion in es- timating the probabilities of rare joint events. It has been employed both to cluster events ac- cording to their distributions, and to directly compute averages of estimates for distributional neighbors of a target event. Here, we examine the tradeoffs between model size and prediction accuracy for cluster-based and nearest neigh- bors distributional models of unseen events. 1 Introduction In many statistical language-processing prob- lems, it is necessary to estimate the joint proba- bility or cooeeurrence probability of events drawn from two prescribed sets. Data sparseness can make such estimates difficult when the events under consideration are sufficiently fine-grained, for instance, when they correspond to occur- rences of specific words in given configurations. In particular, in many practical modeling tasks, a substantial fraction of the cooccurrences of in- terest have never been seen in training data. In most previous work (Jelinek and Mercer, 1980; Katz, 1987; Church and Gale, 1991; Ney and Essen, 1993), this lack of information is ad- dressed by reserving some mass in the proba- bility model for unseen joint events, and then assigning that mass to those events as a func- tion of their marginal frequencies. An intuitively appealing alternative to relying on marginal frequencies alone is to combine es- timates of the probabilities of "similar" events. More specifically, a joint event (x, y) would be considered similar to another (x t, y) if the distri- butions of Y given x and Y given x' (the cooc- currence distributions of x and x ') meet an ap- propriate definition of distributional similarity. For example, one can infer that the bigram "af- ter ACL-99" is plausible -- even if it has never 33 occurred before -- from the fact that the bigram "after ACL-95" has occurred, if "ACL-99" and "ACL-95" have similar cooccurrence distribu- tions. For concreteness and experimental evalua- tion, we focus in this paper on a particular type of cooccurrence, that of a main verb and the head noun of its direct object in English text. Our main goal is to obtain estimates ~(vln ) of the conditional probability of a main verb v given a direct object head noun n, which can then be used in particular prediction tasks. In previous work, we and our co-authors have proposed two different probability estimation methods that incorporate word similarity infor- mation: distributional clustering and nearest- neighbors averaging. Distributional clustering (Pereira et al., 1993) assigns to each word a probability distribution over clusters to which it may belong, and characterizes each cluster by a centroid, which is an average of cooccur- rence distributions of words weighted according to cluster membership probabilities. Cooccur- rence probabilities can then be derived from ei- ther a membership-weighted average of the clus- ters to which the …

Content truncated to 500 words