Variable-order Markov model: Difference between revisions

Revision as of 19:27, 30 April 2015

Revision as of 23:24, 19 July 2015

Line 1:

In [[stochastic processes]], '''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 variables, 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–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 variables turns out to be of real advantage for many applications, such as [[statistical analysis]], [[Statistical classification|classification]] and [[prediction]].<ref name="Shmilovici">{{cite journal|last = Shmilovici|first = A.|author2=Ben-Gal, I. |title = Using a VOM Model for Reconstructing Potential Coding Regions in EST Sequences|journal = Computational Statistics|volume = 22|issue = 1|year = 2007|pages = 49–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 |author2= El-Yaniv, R. and |author3=Yona, G.|title = On Prediction Using Variable Order Markov models|journal = Journal of Artificial Intelligence Research|volume = 22|year = 2004|pages = 385–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 |author2= Morag, G. and |author3=Shmilovici, A.|title = CSPC: A Monitoring Procedure for State Dependent Processes|journal = Technometrics|volume = 45|issue = 4|year = 2003|pages = 293–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>{{cite paper |url= http://www.eng.tau.ac.il/~bengal/VOMBAT.pdf|title= VOMBAT: Prediction of Transcription Factor Binding Sites using Variable Order Bayesian Trees, |author= Grau J., Ben-Gal I., Posch S., Grosse I.|publisher= Nucleic Acids Research, vol. 34, issue W529–W533.|year=2006}}</ref> [http://www.eng.tau.ac.il/~bengal/VOMBAT.pdf]<ref name="Shmilovici"/> [[statistical process control]],<ref name="Ben-Gal"/> [[spam filtering]],<ref name="Bratko">{{cite journal|last = Bratko|first = A. |coauthors author2= Cormack, G. V., |author3=Filipic, B., |author4=Lynam, T. and |author5=Zupan, B.|title = Spam Filtering Using Statistical Data Compression Models|journal = Journal of Machine Learning Research|volume = 7|year = 2006|pages = 2673–2698|url = http://www.jmlr.org/papers/volume7/bratko06a/bratko06a.pdf}}</ref> [[haplotyping]]<ref>Browning, Sharon R. "Multilocus association mapping using variable-length Markov chains." The American Journal of Human Genetics 78.6 (2006): 903-913.</ref> and others.

==See also==