Forums > MaxMSP

2nd Order Markov Chains

October 11, 2006 | 10:30 pm

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.

max v2;
#N vpatcher 0 0 1280 734;
#P window setfont "Franklin Gothic Book" 36.;
#P window linecount 1;
#P comment 103 47 393 10879012 1st Order Markov Chain;
#B color 4;
#P user kslider 425 465 54 0 36 48 31 12 0 128 128 128 128 128 128 255 255 255 0 0 0 0 0 0;
#P window setfont "Sans Serif" 9.;
#P message 222 171 31 9109513 dump;
#P number 170 225 35 9 0 0 0 139 0 0 0 221 221 221 222 222 222 0 0 0;
#P toggle 125 224 15 0;
#P newex 125 255 55 9109513 metro 1000;
#P number 342 475 35 9 0 0 0 139 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 320 503 54 9109513 noteout 1;
#P message 256 171 28 9109513 clear;
#P number 320 427 35 9 0 0 0 139 0 0 0 221 221 221 222 222 222 0 0 0;
#P button 125 289 15 0;
#N prob;
#P newobj 320 340 27 9109513 prob;
#P user kslider 320 151 35 1 36 48 19 7 0 128 128 128 128 128 128 255 255 255 0 0 0 0 0 0;
#P number 320 193 35 9 0 0 0 139 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 320 241 48 9109513 anal 1000;
#P window linecount 2;
#P comment 321 120 100 9109513 "Program" transition values here.;
#P window linecount 4;
#P comment 386 227 100 9109513 Keeps track of which transitions have been made and how many times (weightings).;
#P window linecount 3;
#P comment 389 333 100 9109513 Stores transition weightings in a matrix (dump to see).;
#P window linecount 4;
#P comment 124 332 100 9109513 Banging the prob object outputs a value based on probablity weightings.;
#P connect 14 0 13 0;
#P connect 13 0 8 0;
#P connect 15 0 13 1;
#P connect 6 0 5 0;
#P fasten 10 0 4 0 261 215 325 215;
#P connect 5 0 4 0;
#P fasten 8 0 7 0 130 326 325 326;
#P connect 4 0 7 0;
#P fasten 10 0 7 0 261 269 325 269;
#P fasten 16 0 7 0 227 269 325 269;
#P connect 7 0 9 0;
#P connect 9 0 11 0;
#P connect 12 0 11 1;
#P fasten 9 0 17 0 325 454 430 454;
#P pop;


October 11, 2006 | 10:45 pm

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.


October 11, 2006 | 11:12 pm

I read somewhere else about this but it doesn’t seem to appear anywhere in the examples folder???


October 12, 2006 | 8:31 am

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.

#P window setfont "Sans Serif" 9.;
#P window linecount 1;
#P comment 210 298 124 196617 < --back to two dimensions;
#P window linecount 2;
#P comment 210 219 124 196617 < run the results of your table through
this;
#P window linecount 1;
#P comment 203 92 100 196617 < --- two dimensions;
#N vpatcher 20 74 620 474;
#P window setfont "Sans Serif" 9.;
#P newex 100 50 34 196617 % 16;
#P newex 50 52 29 196617 >> 4;
#P inlet 50 32 15 0;
#P outlet 50 74 15 0;
#P outlet 100 72 15 0;
#P connect 2 0 3 0;
#P connect 3 0 1 0;
#P connect 2 0 4 0;
#P connect 4 0 0 0;
#P pop;
#P newobj 126 215 71 196617 p one_to_two;
#N vpatcher 20 74 620 474;
#P window setfont "Sans Serif" 9.;
#P newex 50 50 35 196617 bondo;
#P newex 83 81 50 196617 clip 0 16;
#P newex 50 111 27 196617 +;
#P newex 50 81 29 196617 < < 4;
#P inlet 50 30 15 0;
#P inlet 75 30 15 0;
#P outlet 50 133 15 0;
#P connect 2 0 6 0;
#P connect 6 0 3 0;
#P connect 3 0 4 0;
#P connect 4 0 0 0;
#P connect 5 0 4 1;
#P connect 1 0 6 1;
#P connect 6 1 5 0;
#P pop;
#P newobj 122 126 71 196617 p two_to_one;
#P number 123 163 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 159 298 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 121 298 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 158 88 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 120 88 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P comment 162 165 124 196617 < put this into your table;
#P connect 5 0 7 0;
#P connect 7 0 3 0;
#P connect 7 1 4 0;
#P connect 1 0 6 0;
#P connect 2 0 6 1;
#P connect 6 0 5 0;
#P window clipboard copycount 11;



grg
October 12, 2006 | 12:31 pm

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 http://www.maxobjects.com

One just can’t recommend that site enough ;)

cheers, g.


January 22, 2008 | 9:59 pm

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.


January 24, 2008 | 12:01 pm


January 24, 2008 | 5:57 pm

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
http://www.timara.oberlin.edu/GaryLeeNelson


January 24, 2008 | 7:18 pm

Awesome! Thanks for posting this.


September 12, 2008 | 4:04 pm

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?


September 13, 2008 | 12:32 pm

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…


September 13, 2008 | 3:38 pm

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


September 15, 2008 | 1:58 pm

Anybody?


September 15, 2008 | 3:10 pm

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….


September 15, 2008 | 4:03 pm

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?


September 16, 2008 | 9:54 am

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:

http://miajo.co.uk/?MaxMSP:markov_chains

> 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…!


September 16, 2008 | 3:09 pm

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


September 16, 2008 | 4:01 pm

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?


September 16, 2008 | 4:25 pm

>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


September 16, 2008 | 4:33 pm

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


September 16, 2008 | 4:53 pm

Thanks Alex, I will check it out.


September 16, 2008 | 5:21 pm

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


September 16, 2008 | 5:28 pm

Thanks Nathan, that would be helpful.


September 17, 2008 | 10:30 am

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: http://www.cycling74.com/forums/index.php?t=msg&th=35620)

As ej calculated in yet another thread (http://www.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.


September 17, 2008 | 10:50 am

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.


September 28, 2008 | 3:26 am

Here is the bpatcher as described before. Attached as a zip file.

–Nathan


Viewing 26 posts - 1 through 26 (of 26 total)