SATTY : Word Sense Induction Application in Web Search Clustering

Second Joint Conference on Lexical and Computational Semantics (*SEM), Volume 2: Seventh International Workshop on Semantic Evaluation (SemEval 2013), pages 207–211, Atlanta, Georgia, June 14-15, 2013. c⃝2013 Association for Computational Linguistics SATTY : Word Sense Induction Application in Web Search Clustering∗ Satyabrata Behera IIT Bombay Mumbai, India satty@cse.iitb.ac.in Ramakrishna Bairi IIT Bombay Mumbai, India bairi@cse.iitb.ac.in Upasana Gaikwad IIT Bombay Mumbai, India upasana@cse.iitb.ac.in Ganesh Ramakrishnan IIT Bombay Mumbai, India ganesh@cse.iitb.ac.in Abstract The aim of this paper is to perform Word Sense induction (WSI); which clusters web search results and produces a diversified list of search results. It describes the WSI system de- veloped for Task 11 of SemEval - 2013. This paper implements the idea of monotone sub- modular function optimization using greedy algorithm. 1 Introduction Two different types of systems were submitted un- der Task 11 of SemEval - 2013 (Roberto Navigli and Daniele Vannella, 2013). The two system types are WSI (Word Sense Induction) and WSD (Word Sense Disambiguation). WSD is the task of automatically associating meaning with words. In WSD the pos- sible meanings for a given word are drawn from an existing sense inventory. In contrast, WSI aims at automatically identifying the meanings of a given word from raw text. A WSI system will be asked to identify the meaning of the input query and cluster the search results into semantically-related groups according to their meanings. Instead, a WSD sys- tem will be requested to sense-tag the above search results with the appropriate senses of the input query and this, again, will implicitly determine a clustering of snippets (i.e., one cluster per sense). ∗This system was designed and submitted in the com- petition SemEval-2013 under task 11 : Evaluating Word Sense Induction & Disambiguation within An End-User Application (Roberto Navigli and Daniele Vannella2013). http://www.cs.york.ac.uk/semeval-2013/. Our system implements the idea given in (Jin- grui He and Hanghang Tong and Qiaozhu Mei and Boleslaw Szymanski, 2012). This developed sys- tem uses the concept of submodularity. The task is treated as a submodular function maximization which has its benefits. On the one hand, there exists a simple greedy algorithm for monotone submod- ular function maximization where the solution ob- tained is guaranteed to be almost as good as the best possible solution according to an objective. More precisely, the greedy algorithm is a constant factor approximation to the cardinality constrained version of the problem, so that the approximate soultion is in the bound of (1 − 1/e) of optimal solution. It is also important to note that this is a worst case bound, and in most cases the quality of the solution ob- tained will be much better than this bound suggests. In our system, monotone submodular objective of (Jingrui He and Hanghang Tong and Qiaozhu Mei and Boleslaw Szymanski, 2012) was implemented to find the top k simultaneously relevant and diver- sified list of search results. Once these top k results are obtained, they are used as centroids to form clus- ters by classifying each of remaining search results …

Content truncated to 500 words