Variable-order Markov model: Difference between revisions

Revision as of 22:22, 20 April 2007

Revision as of 22:30, 20 April 2007

Line 5:

==Definition==

Let <math>A</math> be a state space (finite alphabet) of size <nowiki>|A|</nowiki>.

Let <math>A</math> be a state space (finite alphabet) of size <nowiki>|A|</nowiki>. Consider a sequence with the Markov property <math>x_1^{n}=x_1x_2...x_n</math> of <math>n</math> realizations of random variables, where <math> x_i\in A</math> is the state (symbol) at position <math>i</math> 1≤<math>i</math>≤<math>n</math>, and the concatenation of states <math>x_i</math> and <math>x_{i+1}</math> is denoted by <math>x_ix_{i+1}</math>. Given a training set of observed states, <math>x_1^{n}</math>, the construction algorithm of the VOM models learns a model <math>P</math> that provides a probability assignment for each state in the sequence given its past (previously observed symbols) or future states. Specifically, the learner generates a conditional probability distribution <math>P(x|s)</math> for a symbol <math>x_i \in A</math> given a context <math>s\in A^*</math>, where the * sign represents a sequence of states of any length, including the empty context. VOM models attempt to estimate conditional distributions of the form <math>P(x|s)</math> where the context length |<math>s</math>|≤<math>D</math> varies depending on the available statistics. In contrast, conventional Markov models attempt to estimate these conditional distributions by assuming a fixed contexts' length |<math>s</math>|=<math>D</math> and, hence, can be considered as special cases of the VOM models. Effectively, for a given training sequence, the VOM models are found to obtain better model parameterization than the fixed-order Markov Models that leads to a better variance-bias tradeoff of the learned models [2,3,4].

Consider a sequence with the Markov property <math>x_1^{n}=x_1x_2...x_n</math> of <math>n</math> realizations of random variables, where <math> x_i\in A</math> is the state (symbol) at position <math>i</math> 1≤<math>i</math>≤<math>n</math>, and the concatenation of states <math>x_i</math> and <math>x_{i+1}</math> is denoted by <math>x_ix_{i+1}</math>.

Let <math>A</math> be a state space (finite alphabet) of size <nowiki>|A|</nowiki>. Consider a sequence with the Markov property <math>x_1^{n}=x_1x_2...x_n</math> of <math>n</math> realizations of random variables, where <math> x_i\in A</math> is the state (symbol) at position <math>i</math> 1≤<math>i</math>≤<math>n</math>, and the concatenation of states <math>x_i</math> and <math>x_{i+1}</math> is denoted by <math>x_ix_{i+1}</math>. Given a training set of observed states, <math>x_1^{n}</math>, the construction algorithm of the VOM models learns a model <math>P</math> that provides a probability assignment for each state in the sequence given its past (previously observed symbols) or future states. Specifically, the learner generates a conditional probability distribution <math>P(x|s)</math> for a symbol <math>x_i \in A</math> given a context <math>s\in A^*</math>, where the * sign represents a sequence of states of any length, including the empty context. VOM models attempt to estimate conditional distributions of the form <math>P(x|s)</math> where the context length |<math>s</math>|≤<math>D</math> varies depending on the available statistics. In contrast, conventional Markov models attempt to estimate these conditional distributions by assuming a fixed contexts' length |<math>s</math>|=<math>D</math> and, hence, can be considered as special cases of the VOM models. Effectively, for a given training sequence, the VOM models are found to obtain better model parameterization than the fixed-order Markov Models that leads to a better variance-bias tradeoff of the learned models [2,3,4].

==Example==