ShotgunWSD: An unsupervised algorithm for global word sense disambiguation inspired by DNA sequencing

Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 916–926, Valencia, Spain, April 3-7, 2017. c⃝2017 Association for Computational Linguistics ShotgunWSD: An unsupervised algorithm for global word sense disambiguation inspired by DNA sequencing Andrei M. Butnaru, Radu Tudor Ionescu and Florentina Hristea University of Bucharest Department of Computer Science 14 Academiei, Bucharest, Romania butnaruandreimadalin@gmail.com raducu.ionescu@gmail.com fhristea@fmi.unibuc.ro Abstract In this paper, we present a novel unsu- pervised algorithm for word sense disam- biguation (WSD) at the document level. Our algorithm is inspired by a widely-used approach in the field of genetics for whole genome sequencing, known as the Shot- gun sequencing technique. The proposed WSD algorithm is based on three main steps. First, a brute-force WSD algorithm is applied to short context windows (up to 10 words) selected from the document in order to generate a short list of likely sense configurations for each window. In the second step, these local sense config- urations are assembled into longer com- posite configurations based on suffix and prefix matching. The resulted configura- tions are ranked by their length, and the sense of each word is chosen based on a voting scheme that considers only the top k configurations in which the word ap- pears. We compare our algorithm with other state-of-the-art unsupervised WSD algorithms and demonstrate better perfor- mance, sometimes by a very large margin. We also show that our algorithm can yield better performance than the Most Com- mon Sense (MCS) baseline on one data set. Moreover, our algorithm has a very small number of parameters, is robust to parameter tuning, and, unlike other bio- inspired methods, it gives a determinis- tic solution (it does not involve random choices). 1 Introduction Word Sense Disambiguation (WSD), the task of identifying which sense of a word is used in a given context, is a core NLP problem, having the potential to improve many applications such as machine translation (Carpuat and Wu, 2007), text summarization (Plaza et al., 2011), informa- tion retrieval (Chifu and Ionescu, 2012; Chifu et al., 2014) or sentiment analysis (Sumanth and Inkpen, 2015). Most of the existing WSD algo- rithms (Agirre and Edmonds, 2006; Navigli, 2009) are commonly classified into supervised, unsuper- vised, and knowledge-based techniques, but hy- brid approaches have also been proposed in the literature (Hristea et al., 2008). The main disad- vantage of supervised methods (that have led to the best disambiguation results) is that they re- quire a large amount of annotated data which is difficult to obtain. Hence, over the last few years, many researchers have concentrated on develop- ping unsupervised learning approaches (Schwab et al., 2012; Schwab et al., 2013a; Schwab et al., 2013b; Chen et al., 2014; Bhingardive et al., 2015). In this paper, we introduce a novel WSD algorithm, termed ShotgunWSD1, that stems from the Shotgun genome sequencing technique (An- derson, 1981; Istrail et al., 2004). Our WSD algo- rithm is also unsupervised, but it requires knowl- edge in the form of …

Content truncated to 500 words