'''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'' and thus the VOM models are also called ''Context Trees'' [[[1]]]. The flexibility in the number of conditioning random variables turns out to be of real advantage for many applications, such as statistical analysis, classification and prediction.
==Definition==
Let <math>D(s)</math> be a state space (finite alphabet) of size |D|. Consider a sequence with the Markov property of n realizations of random variables, where is the state (symbol) at position i 1in, and the concatenation of states and is denoted by . Given a training set of observed states, , the construction algorithm of the VOM models learns a model 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 for a symbol given a context , 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 where the context length varies depending on the available statistics. In contrast, conventional Markov models attempt to estimate these conditional distributions by assuming a fixed contexts' length 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 (Ben-Gal et al, 2005) that leads to a better variance-bias tradeoff of the learned models.
