Type Level Clustering Evaluation: New Measures and a POS Induction Case Study

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 77–87, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Type Level Clustering Evaluation: New Measures and a POS Induction Case Study Roi Reichart1∗ Omri Abend2∗† Ari Rappoport2 1ICNC 2Institute of Computer Science Hebrew University of Jerusalem {roiri|omria01|arir}@cs.huji.ac.il Abstract Clustering is a central technique in NLP. Consequently, clustering evaluation is of great importance. Many clustering algo- rithms are evaluated by their success in tagging corpus tokens. In this paper we discuss type level evaluation, which re- flects class membership only and is inde- pendent of the token statistics of a partic- ular reference corpus. Type level evalua- tion casts light on the merits of algorithms, and for some applications is a more natural measure of the algorithm’s quality. We propose new type level evaluation measures that, contrary to existing mea- sures, are applicable when items are pol- ysemous, the common case in NLP. We demonstrate the benefits of our measures using a detailed case study, POS induc- tion. We experiment with seven leading algorithms, obtaining useful insights and showing that token and type level mea- sures can weakly or even negatively corre- late, which underscores the fact that these two approaches reveal different aspects of clustering quality. 1 Introduction Clustering is a central machine learning technique. In NLP, clustering has been used for virtually ev- ery semi- and unsupervised task, including POS tagging (Clark, 2003), labeled parse tree induction (Reichart and Rappoport, 2008), verb-type clas- sification (Schulte im Walde, 2006), lexical ac- quisition (Davidov and Rappoport, 2006; Davi- dov and Rappoport, 2008), multilingual document ∗* Both authors equally contributed to this paper. † Omri Abend is grateful to the Azrieli Foundation for the award of an Azrieli Fellowship. clustering (Montavlo et al., 2006), coreference res- olution (Nicolae and Nicolae, 2006) and named entity recognition (Elsner et al., 2009). Conse- quently, the methodology of clustering evaluation is of great importance. In this paper we focus on external clustering evaluation, i.e., evaluation against manually annotated gold standards, which exist for almost all such NLP tasks. External eval- uation is the dominant form of clustering evalu- ation in NLP, although other methods have been proposed (see e.g. (Frank et al., 2009)). In this paper we discuss type level evaluation, which evaluates the set membership structure cre- ated by the clustering, independently of the token statistics of the gold standard corpus. Many clus- tering algorithms are evaluated by their success in tagging corpus tokens (Clark, 2003; Nicolae and Nicolae, 2006; Goldwater and Griffiths, 2007; Gao and Johnson, 2008; Elsner et al., 2009). How- ever, in many cases a type level evaluation is the natural one. This is the case, for example, when a POS induction algorithm is used to compute a tag dictionary (the set of tags that each word can take), or when a lexical acquisition algorithm is used for constructing a lexicon containing the set of frames that a verb can participate in, or when a sense induction algorithm computes …

Content truncated to 500 words