A comparative study of structured prediction methods for sequence labeling

Abstract: Some machine learning tasks have a complex output, rather than a real number or a class. Those outputs are composed by elements which have interdependences and structural properties. Methods which take into account the form of the output are known as structured prediction techniques. This study focuses on those techniques, evaluating their performance for tasks of sequence labeling and comparing them. Specifically, tasks of natural language processing are used as benchmarks.  The principal problem evaluated is part-of-speech tagging. Datasets of different languages (English, Spanish, Portuguese and Dutch) and environments (newspapers, twitter and chats) are used for a general analysis. Shallow parsing and named entity recognition are also examined. The algorithms treated are structured perceptron, conditional random fields, structured support vector machines and trigram hidden Markov models. They are also compared to different approaches to solve these problems. The results show that, in general, structured perceptron has the best performance for sequence labeling with the conditions evaluated. However, with few training examples, structured support vector machines can achieve a similar or superior accuracy. Moreover, the results for conditional ranom fields is near those two methods. The relative results of the algorithms are similar across different datasets, but the absolute accuracies are dependent on their specificities.