Variable-order Markov model: Difference between revisions

Revision as of 23:34, 20 April 2007

Revision as of 23:36, 20 April 2007

Line 25:

The VOM model of maximal order 2 can approximate the above string using ''only'' the following four [[conditional probability]] components {Pr(a|aa)=0.5, Pr(b|aa)=0.5, Pr(c|b)=1.0, Pr(a|c)= 1.0}.

In this example, Pr(c|ab)=Pr(c|b)=1.0, therefore, the shorter context ''b'' is sufficient to determine the future statecharacter. Similarly, the VOM model of maximal order 3 can approximate the string using only four [[conditional probability]] components.

To construct the [[Markov chain]] of order 1 for the next character in this sequence, one needs to estimate the following 9 [[conditional probability]] components {Pr(a|a), Pr(a|b), Pr(a|c), Pr(b|a), Pr(b|a), Pr(b|a), Pr(c|a), Pr(c|a), Pr(c|a)}.

Line 32 ⟶ 33:

To construct the [[Markov chain]] of order three for the next character in this sequence, one needs to estimate the following 81 [[conditional probability]] components {Pr(a|aaa), Pr(a|aab), …, Pr(c|ccc)}.

In practical settings there is seldom sufficient data to accurately estimate the [[exponent|exponential]] growing number of [[conditional probability]] components as the order of the [[Markov chain]] increases.