Tune Your Brown Clustering, Please

Proceedings of Recent Advances in Natural Language Processing, pages 110–117, Hissar, Bulgaria, Sep 7–9 2015. Tune Your Brown Clustering, Please Leon Derczynski University of Sheffield leon@dcs.shef.ac.uk Sean Chester Aarhus University schester@cs.au.dk Kenneth S. Bøgh Aarhus University ksb@cs.au.dk Abstract Brown clustering, an unsupervised hier- archical clustering technique based on n- gram mutual information, has proven use- ful in many NLP applications. However, most uses of Brown clustering employ the same default configuration; the appropri- ateness of this configuration has gone pre- dominantly unexplored. Accordingly, we present information for practitioners on the behaviour of Brown clustering in or- der to assist hyper-parametre tuning, in the form of a theoretical model of Brown clus- tering utility. This model is then evalu- ated empirically in two sequence labelling tasks over two text types. We explore the dynamic between the input corpus size, chosen number of classes, and quality of the resulting clusters, which has an impact for any approach using Brown clustering. In every scenario that we examine, our re- sults reveal that the values most commonly used for the clustering are sub-optimal. 1 Introduction Brown clustering (Brown et al., 1992) uses dis- tributional information to group similar words. Unsupervised, it induces a hierarchical cluster- ing over words to form a binary tree (e.g. Fig- ure 1). This hierarchical clustering has recently been used in thousands of computational linguis- tics papers, often for feature generation. How- ever, no work exists describing the behaviour and hyper-parametre tuning effects of Brown cluster- ing; even the original paper concentrates on im- plementation rather than its behaviour. Except for a few forays off the beaten track (e.g. Christodoulopoulos et al. (2010), Owoputi et al. (2012), Derczynski et al. (2015a)), default parametres dominate; either 800 or 1000 Brown cats, dogs you, I love, pet Figure 1: A binary, hierarchical clustering of semantically similar entries. Each leaf corresponds to a cluster of words (i.e., a “class”) and leaves near to their common ancestors correspond to clusters that are similar to each other. clusters are generated in nearly every published use. Few experiments use other configurations, and we are not aware of any prior work on hyper- parametre tuning for Brown clustering. This paper addresses this information gap, pro- viding practitioners with principled insights into the algorithm. We provide an analysis of how Brown clustering adds information over input, and, based on this, describe models for the effect that corpus size and cluster count have on the qual- ity of results. These models are then tested in two sequence labeling tasks, cf. Qu et al. (2015). Fi- nally, we compare the initial analysis to observa- tions, leading to concrete advice for practitioners. 2 Background Brown clustering uses mutual information to de- termine distributional similarity, placing similar words in the same cluster and similar clusters nearby in the binary tree. This is an unsuper- vised learned representation of language from the input corpus (Bengio et al., 2013). In the main im- plementation of Brown clustering (Liang, 2005), mutual information is measured at …

Content truncated to 500 words