2nd Order Markov Chains
Sup
I've put together a small patch that does a random MIDI note "walk" based on a 1st-order markov chain using [anal] and [prob]. However, I can't for the life of me think how I'm supposed to get this system into a second, third or even nth order. Any suggestions? The current patch is posted below.
Richard Dudas wrote an example patch for handling up to 5th order chains with anal/prob.
I think it's somewhere in the examples folder.
-- P.
I read somewhere else about this but it doesn't seem to appear anywhere in the examples folder???
the anal help has a subpatcher with a 2n order markov chain in it.
heres an example.
I'm programming one with a cool custom jitter interface, tons of fun.
-matt.
Am 12.10.2006 um 01:12 schrieb Magic Window:
> I read somewhere else about this but it doesn't seem to appear
> anywhere in the examples folder???
its called mchain and you can easily find it by typing markov in the
search box at www.maxobjects.com
One just can't recommend that site enough ;)
cheers, g.
Does anyone have a copy of mchain and prob they could post?
The IRCAM ftp site has them in some crazy format I can not
open. RAR or zip would be ideal.
I found a lot of Dudas' stuff in my archive. It was in one of my archives
named "MaxMSPJitterWeek_05." The name sounds like one of the CNMAT night
schools (2005?) that I probably download from the CNMAT site. It doesn't
seem to be there anymore.
On 1/24/08 7:01 AM, "pelang" wrote:
> save as "mchain"
Cheers
Gary Lee Nelson
Oberlin College
www.timara.oberlin.edu/GaryLeeNelson
Awesome! Thanks for posting this.
I have finally gotten around to experimenting with some
Markov chain stuff and have a question for you guys.
From the mchain help file, it is easy to see how I can
create a 1st order markov chain. I can also read in my own
weights in coll format, I assume in .
But how do I specify a 2nd order markov chain?
Also, when you select orders: 1st, 2nd, 3rd, etc. It prints out
the following...
Mchain: 1st order: range 0 -> 2147483646
Mchain: 2nd order: range 0 -> 32767
Mchain: 3rd order: range 0 -> 1023
Mchain: 4th order: range 0 -> 127
Mchain: 5th order: range 0 -> 63
Mchain: 6th order: range 0 -> 31
What does this mean? Is there an easier tool for out there for
creating Markov chains?
when i started to learn pd (before buying max), there was a markov chain tutorial using float and "moses", an object not present in max.
i made an abstraction cloning that object.
it's really easier using moses and float than what is shown in th e markov chains tutorials in the max doc...
Thanks lematt for the file. I am not sure how this would
help me create a markov chain.
Can someone out here who has used mchain please give
me some guidance.
Thanks,
Anthony
Anybody?
I have some Markov chain stuff, some based in coll and others Java/mxj-based.
I'll have to dig them out and sanitise them a bit when I have a a moment over the next few days.
Briefly the methods are:
1) based on coll, effectively using a similar technique to the bitshifting one mentioned in this thread so that the coll keys are symbols containing a list of the table entries and uses very lazy probability calculations by constructing larger and larger lists for each key.
e.g. for the data
1 2 3 1 2 3 1 2 3 4
for 1st order Markov the coll would contain:
1, 2 2 2;
2, 3 3 3;
3, 1 1 4;
You can then use the current value to look up the key and output the list stored at that key, then choose one of the values in the list at random. This is a limited approach since the length of these lists in coll is limited (250ish?) but I think it's a good way of illustrating how Markov chains work and how they can be constructed.
for 2nd order Markov (with the same data) the coll would contain:
"1 2", 3 3 2;
"2 3", 1 1 4;
"3 1", 2 2;
This time the key is a symbol (converted for example with tosymbol) of the previous two items but it's just as easy to do the same lookup as using the 1st order version.
2) using Java/mxy I wrapped a Java class I found:
https://jgram.dev.java.net/
The project seems now inactive but had enough features to do the job.
As I say I'll dig out both examples soon....
Hey Martin, thanks for the response. I understand how to create
a 1st order markov chain pretty well. Actually it is pretty
easy to do that with [prob].
It was my hope that mchain allowed me a more sophisticated
way of creating higher level markov chains. The example you
gave for 2nd order Markov:
"1 2", 3 3 2;
"2 3", 1 1 4;
"3 1", 2 2;
Is not really a 2nd order markov chain, it is first order
with composite input states. I guess I was under the
impression that mchain had a fancier algorithm. Is that all
a higher level markov chain is, just longer lists of state
permutations?
Quote: Anthony Palomba wrote on Mon, 15 September 2008 17:03
----------------------------------------------------
> Hey Martin, thanks for the response. I understand how to create
> a 1st order markov chain pretty well. Actually it is pretty
> easy to do that with [prob].
>
> It was my hope that mchain allowed me a more sophisticated
> way of creating higher level markov chains. The example you
> gave for 2nd order Markov:
>
> "1 2", 3 3 2;
> "2 3", 1 1 4;
> "3 1", 2 2;
>
----------------------------------------------------
Sorry, that should have been:
"1 2", 3 3 3;
"2 3", 1 1 4;
"3 1", 2 2;
.. for that data.
Ok, I've put the stuff here:
> Is not really a 2nd order markov chain, it is first order
> with composite input states. I guess I was under the
> impression that mchain had a fancier algorithm. Is that all
> a higher level markov chain is, just longer lists of state
> permutations?
My understanding is that this is equivalent. I hacked the coll idea together for order > 1, since I'd already implemented this as a way of doing multidimensional arrays using coll. With higher orders that's kind of what's happening.
I'd be happy to be corrected on this as I don't want to have misunderstood something...!
Quote: Anthony Palomba wrote on Mon, 15 September 2008 10:03
----------------------------------------------------
> Is not really a 2nd order markov chain, it is first order
> with composite input states. I guess I was under the
> impression that mchain had a fancier algorithm. Is that all
> a higher level markov chain is, just longer lists of state
> permutations?
Yes. a second order markov chain just means that the new value depends on the two values before, so each new value can be found from a concatenated reference to the previous N values (where N is the order of the chain). The trick is to find a way of concatenating the previous states. Dudas's patch (from the last time I looked at it) uses additive concatenation, by bitshifting earlier values into higher bits and adding them together.
However, this restricts the range of each value, as you only have 32 bits (length of a long int) to store the value of ALL the values you need to concatenate (so the more values -> the less bits for each, the smaller the range). The other approach, which I've used before (ad Martin is suggesting) is to represent the previous values as symbols, which doesn't restrict the length of each value, but it does mean you may generate a large symbol lookup table in max (which is persistent in memory until restarting max).
When I did this believe I used a symbol->int lookup coll (and one back) that assigned each unique symbolic representation of a list a unique int so that I could use them with anal / prob. I could try and dig that stuff out later if it would be of use...
Regards,
Alex
So is there a limit on the number of state transitions you can
load into prob/mchain?
I guess the real work then comes in finding a way to
organize and output the list of multiorder states that you
would then load in to the coll. It would be great to have a
utility that does that. Does anyone know if such a thing exists?
>Does anyone know if such a thing exists?
More on that below...
anal / prob have limits on how many states they will reference yes. Max size of anals internal table is 16384 states I believe (from the help patch), which means a max of 128 states for a second order markov chain (less than the mchain patch, as this is just the range of values you can concatenate, not how many you can tabulate in anal)
The other advantage with the symbol lookup table approach for multi order markov chains is that states can be assigned dynamically, so if a certain ordering of states does not exist (eg. 1 2 3 for a 3rd order) then it doesn't get assigned a space. You then have effectively 16384 different possible lists of N values, which in many cases will be enough. For more than that you'll need another solution...
The question is how many states you need in the first place, what order of chain, and how many different orderings are you expecting? mchain is a fast and efficient solution for small numbers of states, but beyond that it fails.
My total solution (which will fail if it gets more than 16384 unique sequences of N values) is attached. Sorry it's not documented, I think the left inlet to the main patch is to get a new output (with a bang, the next one is the order (defaults to 6) and the final one is to reset to the start of a chain. I think you may be able to change the order as you go, not sure, looking inside the list refencer colls will makes things clearer.
This looks a bit inefficient with two years or more between now and when it was done, I'm sure it could be a bit cleaner...
Regards,
Alex
Quote: AlexHarker wrote on Tue, 16 September 2008 10:25
----------------------------------------------------
> My total solution ....is attached....
Actually tell a lie, the analysis bit is missing. Here's a new version with the analysis and a nice wrapper for the whole system. You can load multiple versions, but give them a unique argument number so they don't conflict.
The patch you want is: MChainAndAnalysis
Apologies PC users it's all binary files. I can translate to text if necessary later....
Seems like I was nice to myself and named my inlets and outlets in a useful manner, so that's what you want to look at. Sorry it's not max5 ready - looks pretty organised in 4.6, but not so much in 5.
Comments, improvements, suggestions welcome of course...
Alex
Thanks Alex, I will check it out.
I have a UI widget for this that I use extensively in Max. Doesn't look so pretty in Max 5 yet, but you get the idea. Picture attached.
It actually uses cellblock, matrixctrl and poly to get the job done. It's pattr-ized too which is oh so nice.
Let me know if you are interested and I will dig out all the necessary subpatches and bundle it up for you. Might actually motivate me to share some more of these goodies which I have been meaning to do.
--Nathan
Thanks Nathan, that would be helpful.
Quote: AlexHarker wrote on Tue, 16 September 2008 16:09
----------------------------------------------------
> The other approach, which I've used before (ad Martin is
> suggesting) is to represent the previous values as symbols, which
> doesn't restrict the length of each value, but it does mean you
> may generate a large symbol lookup table in max (which is
> persistent in memory until restarting max).
>
> When I did this believe I used a symbol->int lookup coll (and one
> back) that assigned each unique symbolic representation of a list
> a unique int so that I could use them with anal / prob. I could
> try and dig that stuff out later if it would be of use...
Also coll searches one-by-one through the keys until it finds the one you're looking for so for large colls accessed very regularly this can be slow regardless of whether you're using int or symbol keys.
I haven't had problems with large symbol tables, although I can imagine it being a problem over a long period with constantly new symbols being generated. (As in this thread: https://cycling74.com/forums/index.php?t=msg&th=35620)
As ej calculated in yet another thread (https://cycling74.com/forums/index.php?t=msg&th=35546) [anal 16384] uses around 500MB. I'd imagine that most of this 500MB for most purposes would be zeros.
I guess the chosen approach needs to take into account the specific application.
Quote: martinrobinson wrote on Wed, 17 September 2008 04:30
----------------------------------------------------
> Also coll searches one-by-one through the keys until it finds the one you're looking for so for large colls accessed very regularly this can be slow regardless of whether you're using int or symbol keys.
Yes - if you can use ints directly it will be faster, and generally easier, for a small number of states that's definitely the way to go. Whether speed is really going to be an issue though depends on your particular needs - how many states in use, how often you're referencing the coll, and how quickly (probably talking on the level of the sub-millisecond to a maximum of maybe a millisecond) you need the result.
> I haven't had problems with large symbol tables, although I can imagine it being a problem over a long period with constantly new symbols being generated....
Again, depends on how much data you're processing, and how much redundancy there is in the sets. Note that with anal 16384, generating more than 16384 symbols is useless anyway, and given that I have a stopwatch patch that generates about 60,000 symbols in 10 minutes (and doesn't seem slow or crash after that time on my MBP), I think you'll hit the limits of anal before the limits of your symbol lookup table.
An alternative would be to generate unique ints using java(script) or c external, where you could lookup lists, thus saving any need to fill up your symbol table, although that's probably going to be slower, as you'd have to compare individual elements, rather than do the single comparison hat is possible with the symbol table. Of course you could be a bit cleverer and write something using a hash table for lists of ints to speed it up, but it's probably not worth it....
> I guess the chosen approach needs to take into account the specific application.
Definitely.
Here is the bpatcher as described before. Attached as a zip file.
--Nathan
Hello everyone,
I wonder if somebody of you have those files on your computers and can upload them one more time? Because they are simply missing here. I will be very grateful.
Thanks in advance, Oleś.