Int. J. of Web Engineering and Technology   »   2013 Vol.8, No.2

 

 

Title: Worst-case complexity and empirical evaluation of artificial intelligence methods for unsupervised word sense disambiguation

 

Authors: Didier Schwab; Jérôme Goulian; Andon Tchechmedjiev

 

Addresses:
Univ. Grenoble Alpes, LIG – GETALP, Bâtiment IM2AG B – 41 rue des, Mathématiques, 38400 Saint Martin d'Hères, France
Univ. Grenoble Alpes, LIG – GETALP, Bâtiment IM2AG B – 41 rue des, Mathématiques, 38400 Saint Martin d'Hères, France
Univ. Grenoble Alpes, LIG – GETALP, Bâtiment IM2AG B – 41 rue des, Mathématiques, 38400 Saint Martin d'Hères, France

 

Abstract: Word sense disambiguation (WSD) is a difficult problem for natural language processing. Algorithms that aim to solve the problem focus on the quality of the disambiguation alone and require considerable computational time. In this article, we focus on the study of three unsupervised stochastic algorithms for WSD: a genetic algorithm (GA) and a simulated annealing algorithm (SA) from the state of the art and our own ant colony algorithm (ACA). The comparison is made both in terms of the worst case computational complexity and of the empirical performance of the algorithms in terms of F1 scores, execution time and evaluation of the semantic relatedness measure. We find that ACA leads to a shorter execution time as well as better results that surpass the first sense baseline and come close to the results of supervised systems on the coarse-grained all words task from Semeval 2007.

 

Keywords: unsupervised systems; word sense disambiguation; semantic relatedness; ant colony optimisation; ACO; stochastic optimisation; natural language processing; NLP; genetic algorithms; GAs; simulated annealing; computational complexity.

 

DOI: 10.1504/IJWET.2013.055713

 

Int. J. of Web Engineering and Technology, 2013 Vol.8, No.2, pp.124 - 153

 

Available online: 02 Aug 2013

 

 

Editors Full text accessPurchase this articleComment on this article