An Iterative ‘Sudoku Style’ Approach to Subgraph-based Word Sense Disambiguation

Proceedings of the Third Joint Conference on Lexical and Computational Semantics (*SEM 2014), pages 40–50, Dublin, Ireland, August 23-24 2014. An Iterative ‘Sudoku Style’ Approach to Subgraph-based Word Sense Disambiguation Steve L. Manion University of Canterbury Christchurch, New Zealand steve.manion @pg.canterbury.ac.nz Raazesh Sainudiin University of Canterbury Christchurch, New Zealand r.sainudiin @math.canterbury.ac.nz Abstract We introduce an iterative approach to subgraph-based Word Sense Disambigua- tion (WSD). Inspired by the Sudoku puz- zle, it significantly improves the precision and recall of disambiguation. We describe how conventional subgraph-based WSD treats the two steps of (1) subgraph con- struction and (2) disambiguation via graph centrality measures as ordered and atomic. Consequently, researchers tend to focus on improving either of these two steps indi- vidually, overlooking the fact that these steps can complement each other if they are allowed to interact in an iterative man- ner. We tested our iterative approach against the conventional approach for a range of well-known graph centrality mea- sures and subgraph types, at the sentence and document level. The results demon- strated that an average performing WSD system which embraces the iterative ap- proach, can easily compete with state-of- the-art. This alone warrants further inves- tigation. 1 Introduction Explicit WSD is a two-step process of analysing a word’s contextual use then deducing its intended sense. When Kilgarriff (1998) established SEN- SEVAL, the collaborative framework and forum to evaluate WSD, unsupervised systems performed poorly in comparison to their supervised counter- parts (Palmer et al., 2001; Snyder and Palmer, 2004). A review of the literature shows there This work is licensed under a Creative Commons At- tribution 4.0 International Licence. Page numbers and pro- ceedings footer are added by the organisers. Licence de- tails: http://creativecommons.org/licenses/ by/4.0/ has been a healthy rivalry between the two, in which proponents of unsupervised WSD have long sought to vindicate its potential since two decades ago (Yarowsky, 1995) to even more recent times (Ponzetto and Navigli, 2010). As Pedersen (2007) rightly states, supervised systems are bound by their training data, and therefore are limited in portability and flexibility in the face of new domains, changing applications, or different languages. This knowledge acquisi- tion bottleneck, coined by Gale et al. (1992), can be alleviated by unsupervised systems that exploit the portability and flexibility of Lexical Knowl- edge Bases (LKBs). As of 2007, SENSEVAL be- came SEMEVAL, offering a more diverse range of semantic tasks. Unsupervised knowledge-based WSD has since had its performance evaluated in terms of granularity (Navigli et al., 2007), domain (Agirre et al., 2010), and cross/multi-linguality (Lefever and Hoste, 2010; Lefever and Hoste, 2013; Navigli et al., 2013). Results from these tasks have demonstrated unsupervised systems are now a competitive and robust alternative to super- vised systems, especially given the ever changing task-orientated settings WSD is evaluated in. One such class of unsupervised knowledge- based WSD systems that we seek to improve in this paper constructs semantic subgraphs from LKBs, and then runs graph-based centrality mea- sures such as PageRank (Brin and Page, 1998) over them to …

Content truncated to 500 words