Variable Order Markov Model

Below is some background on Markov models for anyone trying to come to grips with using this object.

Basically a Markov model tries to 'learn' what comes next after a given symbol or sequences of symbols. So if you input sequences representing letters, say: 'abcd', 'cbcdf' and 'abde', then a Markov model might learn that 2 out of three times (66%) a 'c' will come after a 'b'. The order of the model is how far into the past it looks, to try and guess what should come next. A first order model of sequences of letters only cares what comes after single letter (e.g. what comes after 'b'?). A second order model takes the current letter (in this example 'b') into account, and the previous one. Thus, a second order model would say that 50% of the time 'c' comes after 'ab', and the other 50% of the time, 'd' comes after 'ab'. It would also say that 100% of the time 'c' comes after 'cb', since the only time in the three training sequences above that it sees a 'cb', a 'c' comes next.

The thing is that if you want to use a high order, you've got to give it as many examples as you can to learn from, so that it learns what are the possible ways to continue from a given sequence. If you give it too little data, then it will tend to just copy the examples you gave it. One example was given above- if it comes across a 'cb', the only thing it knows to do next is produce a 'c', so that's not particularly interesting (though it could be what you want in some circumstances). If more examples had been provided, it might have more options regarding what to do after the sequence 'cb'. So basically the more input sequences you give it, the better it will capture the variety that is possible. Higher order models tend to require more data because there are more possible histories (e.g. for second order: aa, ab, ac, ad, ..., ba, bb, bc, bd,...) and your aim would be to give it examples so it knows what are the probable continuations for all those possible histories.

Variable order models are a bit more forgiving. Say a second-order VMM comes across the sequence 'aa', that it has not seen before. Instead of just picking a random letter to come next, it'd temporarily reduce the order to 1, and then it will know what the options are because it has seen what comes after a single 'a' (i.e. 'b' comes after 'a' in the training sequences above).

To sum up the above: variable length sequences are fine. Providing more sequences tends to train the model better (if there is variety in the training sequences- inputting the same sequences twice is no good). Also, higher order models tend to need more training because there are more possible histories to know about.

Finally, you can have as many values as you want representing a single 'symbol' in a sequence, for either the raw symbols, or the 'reductions'. However, the more values that represent a single reduction, the more possible symbols there are (e.g. combinations of note + velocity), so the more training data you might need (e.g. what can come after note C, velocity 80? what can come after note C, velocity 81?, etc.).