Variable-order Markov model: Difference between revisions

Revision as of 12:03, 9 May 2008

Revision as of 07:45, 8 June 2008

Line 1:

'''Variable-order Markov (VOM) models''' are an important class of models that extend the well known [[Markov chain]] models. In contrast to the Markov chain models, where each random variable in a sequence with a [[Markov property]] depends on a fixed number of [[random variable]]s, in VOM models this number of conditioning random variables may vary based on the specific observed realization.

This realization sequence is often called the ''context''; therefore the VOM models are also called ''context trees'' <ref name="Rissanen">{{cite journal|last = Rissanen|first = J.|title = A Universal Data Compression System|journal = IEEE Transactions on Information Theory|volume = 29|issue = 5|date = Sep 1983|pages = 656-664656–664|url = http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=22734&arnumber=1056741|doi = 10.1109/TIT.1983.1056741}}</ref>. The flexibility in the number of conditioning [[random variable]]s turns out to be of real advantage for many applications, such as statistical analysis, classification and prediction.<ref name="Shmilovici">{{cite journal|last = Shmilovici|first = A.|coauthors = Ben-Gal, I.|title = Using a VOM Model for Reconstructing Potential Coding Regions in EST Sequences|journal = Computational Statistics|volume = 22|issue = 1|date = 2007|pages = 49-6949–69|url=http://www.springerlink.com/content/a447865604519210/|doi = 10.1007/s00180-007-0021-8}}</ref><ref name="Begleiter">{{cite journal|last = Begleiter|first = R.|coauthors = El-Yaniv, R. and Yona, G.|title = On Prediction Using Variable Order Markov Models|journal = Journal of Artificial Intelligence Research|volume = 22|date = 2004|pages = 385-421385–421|url = http://www.jair.org/media/1491/live-1491-2335-jair.pdf}}</ref><ref name="Ben-Gal">{{cite journal|last = Ben-Gal|first = I.|coauthors = Morag, G. and Shmilovici, A.|title = CSPC: A Monitoring Procedure for State Dependent Processes|journal = Technometrics|volume = 45|issue = 4|date = 2003|pages = 293-311293–311|url = http://www.eng.tau.ac.il/~bengal/Technometrics_final.pdf|doi = 10.1198/004017003000000122}}</ref>

==Example==

Line 34:

Various efficient algorithms have been devised for estimating the parameters of the VOM model.<ref name="Begleiter"/>

VOM models have been successfully applied to areas such as [[machine learning]], [[information theory]] and [[bioinformatics]], including specific applications such as [[code|coding]] and [[data compression]],<ref name="Rissanen"/> document compression,<ref name="Begleiter"/> classification and identification of [[DNA]] and [[protein|protein sequences]],<ref name="Shmilovici"/> [[statistical process control]],<ref name="Ben-Gal"/> [[spam filtering]]<ref name="Bratko">{{cite journal|last = Bratko|first = A.|coauthors = Cormack, G. V., Filipic, B., Lynam, T. and Zupan, B.|title = Spam Filtering Using Statistical Data Compression Models|journal = Journal of Machine Learning Research|volume = 7|date = 2006|pages = 2673-26982673–2698|url = http://www.jmlr.org/papers/volume7/bratko06a/bratko06a.pdf}}</ref> and others.

==See also==