BIRA: Improved Predictive Exchange Word Clustering

Proceedings of NAACL-HLT 2016, pages 1169–1174, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics BIRA: Improved Predictive Exchange Word Clustering Jon Dehdari1,2 and Liling Tan2 and Josef van Genabith1,2 1DFKI, Saarbr¨ucken, Germany {jon.dehdari,josef.van genabith}@dfki.de 2University of Saarland, Saarbr¨ucken, Germany liling.tan@uni-saarland.de Abstract Word clusters are useful for many NLP tasks including training neural network language models, but current increases in datasets are outpacing the ability of word clusterers to han- dle them. Little attention has been paid thus far on inducing high-quality word clusters at a large scale. The predictive exchange algo- rithm is quite scalable, but sometimes does not provide as good perplexity as other slower clustering algorithms. We introduce the bidirectional, interpolated, refining, and alternating (BIRA) predictive ex- change algorithm. It improves upon the pre- dictive exchange algorithm’s perplexity by up to 18%, giving it perplexities comparable to the slower two-sided exchange algorithm, and better perplexities than the slower Brown clus- tering algorithm. Our BIRA implementation is fast, clustering a 2.5 billion token English News Crawl corpus in 3 hours. It also reduces machine translation training time while pre- serving translation quality. Our implementa- tion is portable and freely available. 1 Introduction Words can be grouped together into equivalence classes to help reduce data sparsity and better gener- alize data. Word clusters are useful in many NLP ap- plications. Within machine translation word classes are used in word alignment (Brown et al., 1993; Och and Ney, 2000), translation models (Koehn and Hoang, 2007; Wuebker et al., 2013), reordering (Cherry, 2013), preordering (Stymne, 2012), target- side inflection (Chahuneau et al., 2013), SAMT (Zollmann and Vogel, 2011), and OSM (Durrani et al., 2014), among many others. Word clusterings have also found utility in pars- ing (Koo et al., 2008; Candito and Seddah, 2010; Kong et al., 2014), chunking (Turian et al., 2010), NER (Miller et al., 2004; Liang, 2005; Ratinov and Roth, 2009; Ritter et al., 2011), structure transfer (T¨ackstr¨om et al., 2012), and discourse relation dis- covery (Rutherford and Xue, 2014). Word clusters also speed up normalization in training neural network and MaxEnt language models, via class-based decomposition (Goodman, 2001a). This reduces the normalization time from O(|V |) (the vocabulary size) to ≈ O( � |V |) . More improvements to O(log(|V |)) are found using hier- archical softmax (Morin and Bengio, 2005; Mnih and Hinton, 2009) . 2 Word Clustering Word clustering partitions a vocabulary V, grouping together words that function similarly. This helps generalize language and alleviate data sparsity. We discuss flat clustering in this paper. Flat, or strict partitioning clustering surjectively maps word types onto a smaller set of clusters. The exchange algorithm (Kneser and Ney, 1993) is an efficient technique that exhibits a general time complexity of O(|V | × |C| × I), where |V | is the number of word types, |C| is the number of classes, and I is the number of training iterations, typically < 20 . This omits the specific method of exchang- ing words, which adds further complexity. …

Content truncated to 500 words