Semantic Word Clusters Using Signed Spectral Clustering

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 939–949 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1087 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 939–949 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1087 Semantic Word Clusters Using Signed Spectral Clustering Jo˜ao Sedoc, Jean Gallier, Lyle Ungar Computer & Information Science University of Pennsylvania joao, jean, ungar@cis.upenn.edu Dean Foster Amazon LLC dean@foster.net Abstract Vector space representations of words cap- ture many aspects of word similarity, but such methods tend to produce vector spaces in which antonyms (as well as syn- onyms) are close to each other. For spec- tral clustering using such word embed- dings, words are points in a vector space where synonyms are linked with posi- tive weights, while antonyms are linked with negative weights. We present a new signed spectral normalized graph cut al- gorithm, signed clustering, that overlays existing thesauri upon distributionally de- rived vector representations of words, so that antonym relationships between word pairs are represented by negative weights. Our signed clustering algorithm produces clusters of words that simultaneously cap- ture distributional and synonym relations. By using randomized spectral decomposi- tion (Halko et al., 2011) and sparse matri- ces, our method is both fast and scalable. We validate our clusters using datasets containing human judgments of word pair similarities and show the benefit of using our word clusters for sentiment prediction. 1 Introduction In distributional vector representations, opposite relations are not fully captured. Take, for example, words such as “great” and “awful” that can appear with similar frequency in the same sentence struc- ture: “John had a great meeting” and “John had an awful day.” Word embeddings, which are success- ful in a wide array of NLP tasks (Turney et al., 2010; Dhillon et al., 2015), fail to capture this antonymy because they follow the distributional hypothesis that similar words are used in similar contexts (Harris, 1954), thus assigning small co- sine or euclidean distances between the vector rep- resentations of “great” and “awful”. While vector space models (Turney et al., 2010) such as word2vec (Mikolov et al., 2013), Global vectors (GloVe) (Pennington et al., 2014), or Eigenwords (Dhillon et al., 2015) capture relat- edness, they do not adequately encode synonymy and semantic similarity (Mohammad et al., 2013; Scheible et al., 2013). Our goal is to create clus- ters of synonyms or semantically equivalent words and linguistically motivated unified constructs. Signed graphs, which are graphs with negative edge weights, were first introduced by Cartwright and Harary (1956). However, signed graph clus- tering for multiclass normalized cuts (K-clusters) has been largely unexplored until recently. We present a novel theory and method that extends multiclass normalized cuts (K-cluster) of Yu and Shi (2003) to signed graphs (Gallier, 2016)1 and the work of Kunegis et al. (2010) to K-clustering. This extension allows the incorporation of knowl- edge base information, positive and negatively weighted links (see figure …

Content truncated to 500 words