Improving Markov chain classification using string transformations and evolutionary search

ABSTRACT

Markov chain classification or n-gram modeling, as it is sometimes called, is a very common and powerful tool for many problems that involve sequences of finite tokens. It has been used in a wide range of tasks, including natural language modeling, author identification, protein similarity searches, and even bird-song recognition. Clearly, an improvement in the Markov chain classification will have broad implications in many fields. Our new system, called SCS, improves upon Markov chain classification by introducing a preprocessing step in which an arbitrary set of transformation functions are performed on the input sequences. Since the space of possible transformations is unbounded, a genetic algorithm search is used to search for functions that improve classification. We show that GA is able to consistently find preprocessing functions that substantially improve the performance of the Markov chain model.

REFERENCES

• 1: Jaume Bacardit , Michael Stout , Jonathan D. Hirst , Kumara Sastry , Xavier Llorà , Natalio Krasnogor, Automated alphabet reduction method with evolutionary algorithms for protein structure prediction, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277033]
• 2: L. R. Bahl, F. Jelinek, and R. L. Mercer. Likelihood approach to continuous speech recognition. Transactions on Pattern Analysis and Machine Intelligence, 2:179--190, 1983.
• 3: A. Bairoch and R. Apweiler. The swiss-prot protein sequence data bank and its supplement trembl. Nucleic Acids Research, 25(1):31--36, 1997.
• 4: Peter F. Brown , John Cocke , Stephen A. Della Pietra , Vincent J. Della Pietra , Fredrick Jelinek , John D. Lafferty , Robert L. Mercer , Paul S. Roossin, A statistical approach to machine translation, Computational Linguistics, v.16 n.2, p.79-85, June 1990
• 5: Peter F. Brown , Peter V. deSouza , Robert L. Mercer , Vincent J. Della Pietra , Jenifer C. Lai, Class-based n-gram models of natural language, Computational Linguistics, v.18 n.4, p.467-479, December 1992
• 6: B. Y. M. Cheng, J. G. Carbonell, and J. Klein-Seetharaman. Protein classification based on text document classification techniques. Proteins: Structure, Function, and Bioinformatics, 58(4):955--970, 2005.
• 7: Michael John Collins , Mitchell P. Marcus, Head-driven statistical models for natural language parsing, University of Pennsylvania, Philadelphia, PA, 1999
• 8: Kazutoshi Sasahara , Yasuki Kakishita , Tetsuro Nishino , Miki Takahasi , Kazuo Okanoya, A Reversible Automata Approach to Modeling Birdsongs, Proceedings of the 15th International Conference on Computing, p.80-85, November 21-24, 2006 [doi>10.1109/CIC.2006.14]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms

Keywords:
Markov chain modeling, genetic algorithm search