Accelerated High-Quality Mutual-Information Based Word Clustering

Proceedings of the 12th Conference on Language Resources and Evaluation (LREC 2020), pages 2491–2496 Marseille, 11–16 May 2020 c⃝ European Language Resources Association (ELRA), licensed under CC-BY-NC 2491 Accelerated High-Quality Mutual-Information Based Word Clustering Manuel R. Ciosici$e£, Ira Assente, Leon Derczynski£ $UNSILO A/S, eAarhus University, £IT University of Copenhagen {manuel, ira}@cs.au.dk, leod@itu.dk Abstract Word clustering groups words that exhibit similar properties. One popular method for this is Brown clustering, which uses short-range distributional information to construct clusters. Specifically, this is a hard hierarchical clustering with a fixed-width beam that employs bi-grams and greedily minimizes global mutual information loss. The result is word clusters that tend to outperform or complement other word representations, especially when constrained by small datasets. However, Brown clustering has high computational complexity and does not lend itself to parallel computation. This, together with the lack of efficient implementations, limits their applicability in NLP. We present efficient implementations of Brown clustering and the alternative Exchange clustering as well as a number of methods to accelerate the computation of both hierarchical and flat clusters. We show empirically that clusters obtained with the accelerated method match the performance of clusters computed using the original methods. Keywords: word clusters, word representations, efficient computation 1. Introduction Word clusters have been successfully used in NLP tasks over the past decades, contributing to advances especially in machine translation (Brown et al., 1993; Auli et al., 2013), named entity recognition (Ratinov and Roth, 2009; Ritter et al., 2011), parsing (Koo et al., 2008; Kong et al., 2014), and processing noisy text (Owoputi et al., 2012). They remain a competitive representation useful for many tasks (Dyer et al., 2016; Choi, 2016; Lukasik et al., 2015), yielding superior extrinsic performance in particular when limited data is available (Qu et al., 2015) – which is the case for the majority of languages. More recently, word clusters induced using the Brown clustering algorithm have been shown to be highly effective in encoding syntactic in- formation (Ciosici et al., 2019) and have been used for un- supervised Part-of-Speech tagging (Cardenas et al., 2019). Brown clustering (Brown et al., 1992) is a commonly used word clustering algorithm, performing a bottom-up, win- dowed, hard hierarchical clustering based on the global ob- jective of maximized Average Mutual Information (AMI), which is equivalent to the Maximum Likelihood Esti- mate (MLE) of the underlying language model (Martin et al., 1998). The tension between local merges and the global optimization goal makes the algorithm parallelize hard. Si- multaneously, the number of merges considered at any one time directly affects the quality of the final word cluster- ing (Derczynski and Chester, 2016). While Brown clustering often provides a useful grouping of items into classes based on their distributionality (Ciosici et al., 2019), we find that this process is both slow and also finds poorer optima than using the alternative Exchange clustering. Exchange clustering is an alternative to Brown clustering that optimizes AMI iteratively. Unlike Brown clustering, Exchange clustering outputs a flat clustering. For brevity, we refer to …

Content truncated to 500 words