A New Approach to the POS Tagging Problem Using Evolutionary Computation

Proceedings of Recent Advances in Natural Language Processing, pages 619–625, Hissar, Bulgaria, 7-13 September 2013. A New Approach to the POS Tagging Problem Using Evolutionary Computation Ana Paula Silva EST-IPCB dorian@ipcb.pt Arlindo Silva EST-IPCB arlindo@ipcb.pt Irene Rodrigues Universidade de Évora ipr@di.uevora.pt Abstract The purpose of part-of-speech tagging is to automatically tag the words of a text, written in a certain language, with labels that usually take the form of acronyms that designate the appropriate parts-of-speech. In this paper we propose a new approach to the problem that divides it in two different tasks: a learning task and an optimization task. We tackled each of those tasks with evolutionary computation techniques: ge- netic algorithms and a particle swarm op- timizer. We emphasize the use of swarm intelligence, not only for the good results achieved, but also because it is one of the first applications of such algorithms to this problem. We believe that this approach is generic enough so that it can be though as an alternative approach to solve other nat- ural language processing tasks that share some fundamental characteristics with the part-of-speech tagging problem. The re- sults obtained in two different English cor- pora are among the best published ones. 1 Introduction In most languages, each word has a set of lexical categories that represent the roles that they can as- sume in a sentence. When the cardinality of this set is greater than one, we say that the word is am- biguous. Typically, the context of a word, i.e., the lexical categories of the surrounding words, is the fundamental piece of information for determining its role in a sentence. For instance, the word fly can assume the function of a verb, if it follows the word to, or can be used as a noun if it is pre- ceded by a determiner like the. According to this, most taggers take into consideration the context of a word to decide which should be its tag. However, each of the words belonging to a word’s context can also be used in different ways, and that means that, in order to solve the problem, a tagger should have some type of disambiguation mechanism that allows it to choose the proper POS tags for all the words of a sentence. The methods used for solving the POS tagging problem can be divided into two distinct groups, based on the information they use. In one group, we can gather the approaches that use statisti- cal information about the possible contexts of the various word tagging hypotheses. Most of the stochastic taggers are based on hidden Markov models. In the other group, we find rule based tag- gers (Brill (1995); Wilson and Heywood (2005); Nogueira Dos Santos et al. (2008)). The rules are usually discovered automatically, and its purpose is to correct errors resulting from an initial basic tagging. Brill’s tagger (Brill (1995)) is perhaps the most popular tagger based on rules. More recently, several works following an evo- lutionary approach have been published. …

Content truncated to 500 words