Structured Hidden Markov Model versus String Kernel Machines for Symbolic Sequence Classification

The problem of learning a classifier from examples is a fundamental task in Machine Learnig and is nowadays actively studied. Most approaches follow a Discrimination based paradigm, where the aim is to find the best way to separate the examples of one class from those of other classes. A less popular approach follows a Characterization based paradigm, where the aim is to build a description (model) of every class from examples, and use this model to recognizes instances of that class. This paper focuses on the specific task of classifying and tagging symbolic sequences, by introducing a Characterization approach, based on Structured Hidden Markov Models, and compares its perfomances against a widely used discriminative approach, i.e. kernel machines. This task is particulary relevant to several applications in many fields, such as molecular biology, web log analysis, network traffic analysis, user profiling, and so on. In order to assess the validity of the proposed approach, an artificial benchmark has been designed in such a way that the regularities to be discovered are well known and allow for a controlled evaluation of the real capabilities the learning algorithms investigated. The obtained results allow to point out the major advantages and weaknesses of the investigated approaches in the specific classification task addressed.