Generative model versus discriminative model approach for symbolic sequence classification

The problem of learning a classier from examples is a fundamental task in Machine Learnig and is nowadays actively studied. The two alternative approches usually followed are Discrimination based and Characterization based. This paper focuses on the more specic task of classifying and tagging symbolic sequences, and compares two top level techniques representative of both alternative approaches: Structured Hidden Markov Model and String Kernel. This task is a particulary relevant to many applications in molecular biology. An articial benchmark has designed constructing an extensive test for the real capabilities of the learning algorithms. It consists of dierent sets of articial sequences that have a structure resembling to the one of genomic sequences, while the regularities, which must be discovered, are well known. The obtained results show a clear predominance of the techniques based on Structured Hidden Markov Model. Copyright © 2009 by IICAI.