Content deleted Content added
Mark viking (talk | contribs) Added wl, context to first sentence |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (39 intermediate revisions by 27 users not shown) | |||
Line 1:
{{Short description|Markov-based processes with variable "memory"}}
In
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|
==Example==
Consider for example a sequence of [[random variable]]s, each of which takes a value from the ternary [[alphabet]] {{math|{{mset|''a'',
The VOM model of maximal order 2 can approximate the above string using ''only'' the following five [[conditional probability]] components: {{math|Pr(''a''
In this example, {{math|Pr(''c''
To construct the [[Markov chain]] of order 1 for the next character in that string, one must estimate the following 9 conditional probability components: {{math|Pr(''a''
In practical settings there is seldom sufficient data to accurately estimate the [[exponential growth|exponentially increasing]] number of conditional probability components as the order of the Markov chain increases.
Line 18 ⟶ 19:
==Definition==
Let
Consider a sequence with the [[Markov property]] <math>x_1^{n}=x_1x_2\dots x_n</math> of
Given a training set of observed states, <math>x_1^{n}</math>, the construction algorithm of the VOM models<ref name="Shmilovici"/><ref name="Begleiter"/><ref name="Ben-Gal"/> learns a model
Specifically, the learner generates a [[conditional distribution|conditional probability distribution]] <math>P(x_i
VOM models attempt to estimate [[conditional distribution]]s of the form <math>P(x_i
In contrast, conventional [[Markov chain|Markov models]] attempt to estimate these [[conditional distribution]]s by assuming a fixed contexts' length
Effectively, for a given training sequence, the VOM models are found to obtain better model parameterization than the fixed-order [[Markov chain|Markov models]] that leads to a better [[variance]]-bias tradeoff of the learned models.<ref name="Shmilovici"/><ref name="Begleiter"/><ref name="Ben-Gal"/>
Line 34 ⟶ 35:
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 journal |url= http://www.eng.tau.ac.il/~bengal/VOMBAT.pdf |title= VOMBAT: Prediction of Transcription Factor Binding Sites using Variable Order Bayesian Trees |author1= Grau J. |author2= Ben-Gal I. |author3= Posch S. |author4= Grosse I. |journal= Nucleic Acids Research |publisher= Nucleic Acids Research, vol. 34, issue W529–W533. |year= 2006 |volume= 34 |issue= Web Server issue |pages= W529-33 |doi= 10.1093/nar/gkl212 |pmid= 16845064 |pmc= 1538886 |archive-date= 2018-09-30 |access-date= 2014-01-10 |archive-url= https://web.archive.org/web/20180930084306/http://www.eng.tau.ac.il/~bengal/VOMBAT.pdf |url-status= dead }}</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.
==See also==
* [[Stochastic chains with memory of variable length]]
* [[Examples of Markov chains]]
* [[Variable order Bayesian network]]
Line 44 ⟶ 45:
* [[Markov chain Monte Carlo]]
* [[Semi-Markov process]]
* [[Artificial intelligence]]
| |||