Unsupervised Multiword Segmentation of Large Corpora using Prediction-Driven Decomposition of n-grams

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 753–761, Dublin, Ireland, August 23-29 2014. Unsupervised Multiword Segmentation of Large Corpora using Prediction-Driven Decomposition of n-grams Julian Brooke*† Vivian Tsang† Graeme Hirst* Fraser Shein*† *Department of Computer Science University of Toronto jbrooke@cs.toronto.edu gh@cs.toronto.edu †Quillsoft Ltd. Toronto, Canada vtsang@quillsoft.ca fshein@quillsoft.ca Abstract We present a new, efficient unsupervised approach to the segmentation of corpora into multiword units. Our method involves initial decomposition of common n-grams into segments which max- imize within-segment predictability of words, and then further refinement of these segments into a multiword lexicon. Evaluating in four large, distinct corpora, we show that this method cre- ates segments which correspond well to known multiword expressions; our model is particularly strong with regards to longer (3+ word) multiword units, which are often ignored or minimized in relevant work. 1 Introduction Identification of multiword units in language is an active but increasingly fragmented area of research, a problem which can limit the ability of others to make use of units beyond the level of the word as input to other applications. General research on word association metrics (Church and Hanks, 1990; Smadja, 1993; Schone and Jurafsky, 2001; Evert, 2004; Pecina, 2010), though increasingly comprehensive in its scope, has mostly failed to identify a single best choice, leading some to argue that the variety of multiword phenomena must be tackled individually. For instance, there is a body of research focusing specifically on collocations that are (to some degree) non-compositional, i.e. multiword expressions (Sag et al., 2002; Baldwin and Kim, 2010), with individual projects often limited to a particular set of syntactic patterns, e.g. verb-noun combinations (Fazly et al., 2009). A major issue with approaches involving statistical association is that they rarely address expressions larger than 2 words (Heid, 2007); in corpus linguistics, larger sequences referred to as lexical bundles are extracted using an n-gram frequency cutoff (Biber et al., 2004), but the frequency threshold is typically set very high so that only a very limited set is extracted. Another drawback, common to almost all these methods, is that they rarely offer an explicit segmentation of a text into multiword units, which would be preferable for downstream uses such as probabilistic distributional semantics. An exception is the Bayesian approach of Newman et al. (2012), but their method does not scale well (see Section 2). Our own long-term motivation is to identify a wide variety of multiword units for assisting language learning, since correct use of collocations is known to pose a particular challenge to learners (Chen and Baker, 2010). Here, we present a multiword unit segmenter1 with the following key features: • It is entirely unsupervised. • It offers both segmentation of the input corpus and a lexicon which can be used to segment new corpora. • It is scalable to very large corpora, and works for a variety of corpora. • It is language independent. This work is licenced under a Creative Commons Attribution 4.0 International License. Page numbers …

Content truncated to 500 words