UBC-AS: A Graph Based Unsupervised System for Induction and Classification

Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007), pages 346–349, Prague, June 2007. c⃝2007 Association for Computational Linguistics UBC-AS: A Graph Based Unsupervised System for Induction and Classification Eneko Agirre and Aitor Soroa IXA NLP Group UBC Donostia, Basque Contry {e.agirre,a.soroa}@si.ehu.es Abstract This paper describes a graph-based unsu- pervised system for induction and clas- sification. The system performs a two stage graph based clustering where a co- occurrence graph is first clustered to com- pute similarities against contexts. The con- text similarity matrix is pruned and the re- sulting associated graph is clustered again by means of a random-walk type algorithm. The system relies on a set of parameters that have been tuned to fit the corpus data. The system has participated in tasks 2 and 13 of the SemEval-2007 competition, on word sense induction and Web people search, re- spectively, with mixed results. 1 Introduction This paper describes a graph-based unsupervised system for induction and classification. Given a set of data to be classified, the system first induces the possible clusters and then clusters the data accord- ingly. The paper is organized as follows. Section 2 gives an description of the general framework of our system. Sections 3 and 4 presents in more detail the implementation of the framework for the Semeval- 2007 WEPS task (Artiles et al., 2007) and Semeval- 2007 sense induction task (Agirre and Soroa, 2007), respectively. Section 5 presents the results obtained in both tasks, and Section 6 draws some conclusions. 2 A graph based system for unsupervised classification The system performs a two stage graph based clus- tering where a co-occurrence graph is first clustered to compute similarities against contexts. The context similarity matrix is pruned and the resulting associ- ated graph is clustered again by means of a random- walk type algorithm. We will see both steps in turn. First step: calculating hub score vectors In a first step, and for each entity to be clustered, a graph consisting on context word co-occurrences is built. Vertices in the co-occurrence graph are words and two vertices share an edge whenever they co- occur in the same context. Besides, each edge re- ceives a weight, which indicates how strong the in- cident vertices relate each other. As shown in (V´eronis, 2004), co-occurrence graphs exhibit the so called small world structure (Watts and Strogatz, 1998) and, thus, they contain highly dense subgraphs which will represent the dif- ferent clusters the entity may have. For identifying these clusters we have implemented two algorithms based on the notion of centrality of the vertices, where some highly dense vertices, called “hubs”, are chosen as representatives of each cluster. The algo- rithms are the HyperLex algorithm (V´eronis, 2004) and the HITS algorithm (Kleinberg, 1999). Once the hubs are identified, the minimum span- ning tree (MST) of the co-occurrence graph is com- puted. The root elements of the MST are precisely the induced hubs and each vertex of the original graph —and, thus, each word of the corpus— is …

Content truncated to 500 words