DistributionalClusteringofEnglishWords.pptVIP

Distributional Clustering of English Words Fernando Pereira- ATT Bell Laboratories, 600 Naftali Tishby- Dept. of Computer Science, Hebrew University Lillian Lee- Dept. of Computer Science, Cornell University Presenter- Juan Ramos, Dept. of Computer Science, Rutgers Universtiy, juramos@cs.rutgers.edu Overview Purpose: evaluate a method for clustering words according to their distribution in particular syntactic contexts. Methodology: find lowest distortion sets of clusters of words to determine models of word coocurrence. Applications Scientific POV: lexical acquisition of words Practical POV: classification concerns data sparseness in garmmar models. Address clusters in large corpus of documents Definitions Context: function of given word in its sentence. Eg: a noun as a direct object Sense class: hidden model describing word association tendencies Mix of cluster and cluster probability given a word Cluster: probabilistic concept of a sense class Problem Setting Restrict problem to verbs (V) and nouns (N) in main verb-direct object relationship f (v, n) = frequencies of occurrence of verb, noun pairs Text must be pre-formatted to fit specifications For given noun n, conditional distribution p(n, v) = f(v,n)/(sum (v, f(v,n)) Problem Setting cont. Goal: create set C of clusters and probabilityies p(c|n). Each c in C associated to cluster centroid p(c) p(c) = average of p(n) over all v in V. Distributional Similarity Given two distributions p, q, KL distance is D(p || q) = sum (x, p(x) log (p(x)/q(x))) D(p || q) = 0 implies p = q Small D(p || q) implies two distributions are likely instances of a centroid p(c). D(p || q) measures loss of data by using p(c). Theoretical Foundation Given unstructured V, N, training data of X independent pairs of verbs and nouns. Problem: learn joint distribution of pairs given X Not quite unsupervised, not quite supervised No internal structure in pairs Learn underlying distribution Distributional Clustering Approximately decompose p(n