Efficient Unsupervised Discovery of Word Categories Using Symmetric Patterns and High Frequency Words

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 297–304, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Efficient Unsupervised Discovery of Word Categories Using Symmetric Patterns and High Frequency Words Dmitry Davidov ICNC The Hebrew University Jerusalem 91904, Israel dmitry@alice.nc.huji.ac.il Ari Rappoport Institute of Computer Science The Hebrew University Jerusalem 91904, Israel www.cs.huji.ac.il/∼arir Abstract We present a novel approach for discov- ering word categories, sets of words shar- ing a significant aspect of their mean- ing. We utilize meta-patterns of high- frequency words and content words in or- der to discover pattern candidates. Sym- metric patterns are then identified using graph-based measures, and word cate- gories are created based on graph clique sets. Our method is the first pattern-based method that requires no corpus annota- tion or manually provided seed patterns or words. We evaluate our algorithm on very large corpora in two languages, us- ing both human judgments and WordNet- based evaluation. Our fully unsupervised results are superior to previous work that used a POS tagged corpus, and computa- tion time for huge corpora are orders of magnitude faster than previously reported. 1 Introduction Lexical resources are crucial in most NLP tasks and are extensively used by people. Manual com- pilation of lexical resources is labor intensive, er- ror prone, and susceptible to arbitrary human deci- sions. Hence there is a need for automatic author- ing that would be as unsupervised and language- independent as possible. An important type of lexical resource is that given by grouping words into categories. In gen- eral, the notion of a category is a fundamental one in cognitive psychology (Matlin, 2005). A lexi- cal category is a set of words that share a signif- icant aspect of their meaning, e.g., sets of words denoting vehicles, types of food, tool names, etc. A word can obviously belong to more than a single category. We will use ‘category’ instead of ‘lexi- cal category’ for brevity1. Grouping of words into categories is useful in it- self (e.g., for the construction of thesauri), and can serve as the starting point in many applications, such as ontology construction and enhancement, discovery of verb subcategorization frames, etc. Our goal in this paper is a fully unsupervised discovery of categories from large unannotated text corpora. We aim for categories containing sin- gle words (multi-word lexical items will be dealt with in future papers.) Our approach is based on patterns, and utilizes the following stages: 1. Discovery of a set of pattern candidates that might be useful for induction of lexical re- lationships. We do this in a fully unsuper- vised manner, using meta-patterns comprised of high frequency words and content words. 2. Identification of pattern candidates that give rise to symmetric lexical relationships. This is done using simple measures in a word re- lationship graph. 3. Usage of a novel graph clique-set algorithm in order to generate categories from informa- tion on the co-occurrence of content words in the symmetric patterns. …

Content truncated to 500 words