Saturday 8 May 2010

Algorithmic Composition: Markov Chains in PureData

We've looked at Markov Chains in a few previous Algorithmic Composer tutorials including Markov Chains in Keykit and Markov Chains in OpenMusic. Today we'll be creating some algorithmic music by composing with Markov Chains in PureData.

Markov Chains choose the next state based on the current state and a set of probabilities. Mapped to pitch this would involve choosing our next note based on our current note and a list of possible next notes and their probabilities.

In today's tutorial we'll look at examples of Markov Chains and use them to generate pitches for a simple algorithmic composition.

Markov Chains and Music

Markov Chains choose the next state based on the current state and a set of probabilities. As an example, here are the notes of 'Happy Birthday':

C4 C4 D4 C4 F4 E4

C4 C4 D4 C4 G4 F4
C4 C4 C5 A4 F4 E4 D4
Bb4 Bb4 A4 F4 G4 F4

In a First Order Markov Chain, the next note is based on the current note and a set of probabilities. If we analyse Happy Birthday we can discover the probabilities of one note following another.

The first column of this table shows all the notes in the song, followed by a list of numbers indicating all of the notes that followed that pitch.

C4, C4 D4 F4 C4 D4 G4 C4 C5;

D4, C4 C4 Bb4;

E4, C4 D4;

F4, E4 C4 E4 G4;

G4, F4 F4;

A4, F4 F4;

Bb4, Bb4 A4;

C5, A4;

So C5 was only followed by A4. We can measure probabilities between 0 and 1. The probability of A4 following C5 is 1, similarly the probability of A4 being followed by F4 is 1. Usually this is represented by a table that shows these probabilities:

This table is known as a transition matrix, a state transition matrix (STM), or a transition table.

Once we have this table, we can compose new material based on these probabilities. You can create the STM by hand, or create it by analysing existing music or other data. For example loading up the entire works of Mozart and creating algorithmic compositions based on the same set of note probabilities.

Algorithmic Composition with Markov Chains in PureData
Today we're looking at automatically analysing a MIDI file in PureData to create a first order STM, then generating some simple algorithmic music compositions from this. In this first example we'll just build our model to include pitch but you can easily extend this to include rhythm, dynamics or other musical parameters.

Loading and Playing a MIDI file in PureData
This patch is a little more involved than some of our previous PureData patches. To help keep it organised we'll make use of subpatches. To create a subpatch, put a new object into your patch and call it 'pd a-name-that-describe-what-the-subpatch-does'. You can call it anything you like but naming it in a useful way is recommended. Here I've created a two subpatches one to load the MIDI file and one to create a transition matrix together with a few bang buttons.

The contents of the 'pd loadMIDIfile' subpatch look like this:

At the top two inlets are connected to the bangs in our main patch. The read message when sent to the seq object will open up a dialogue box allowing us to open and load a MIDI file. The start message will play the file. We're going to play through it very quickly so that we quickly generate an STM of pitches from our MIDI file without having to wait for it to play through in real time.

The midiparse object outputs different sorts of MIDI data from each of its ports, while the stripnote object will only output MIDI noteOn messages, discarding noteOff messages so that we are considering each note only once.

Analysing the Pitches to Create a Transition Matrix in PureData
The contents of the markovAnalysis subpatch look like this:

We store our new matrix in a data object called a coll. Any time you refer to a coll with the same name (here pitchMatrix) it accesses the same data.

Here the notes are chunked up into pairs by this further subpatch called pd pair. So 1 2 3 4 5 becomes 1 2, 2 3, 3 4, 4 5

What we end up with in our coll is an array with each note and a list of the notes that followed it. As in our Happy Birthday example earlier. Here's the same Happy Birthday table in MIDI notes:

60, 60 62 65 60 62 67 60 70;
62, 60 60 70;
64, 60 62;
65, 64 60 64 67;
67, 65 65;
69, 65 65;
70, 70 69;
72, 69;

Algorithmic Composition Using Markov Chains in PureData
Now that we've generated our transition matrix, we can now use this to compose new musical material. In the main pitch window add a toggle, metro object, a new pd subpatch that we'll use to generate pitches from the transition table and a makenote and noteout object.

We'll stick to simple rhythms for this initial example, but you can try applying any algorithmic composition technique to generate more interesting musical rhythms.

The pd markovPitchGenerate subpatch looks like this.

Starting with one note from our input melody we use the length object to see how long the list of possible next notes is. This is used as input to the random object, this randomly chooses a number and is used to randomly pick one of the following notes from our coll pitchMatrix object. If for example, in our STM MIDI note 60 is followed by 64 62 64 65, there is .5 chance of 64 getting picked and a .25 chance of 62 or 65 being picked.

This newly selected number is then input to the f object (float), this is used as the new pitch and the process is repeated again.

The final patch should look something like this:

1. Clicking open will allow you to load up a new MIDI file.
2. Clicking play plays through the MIDI file and sends the pitch through to be analysed creating our transition matrix. The bang when finished button will flash when this is completed.
3. Make sure you have selected a MIDI output in preferences / MIDI settings.
4. Turning the toggle above the metro on will generate a stream of new pitches based on our analysed STM.
5. Occasionally with some input data the music may sound stuck in a loop, this is due to there being only a small number of possible notes following one or more of the pitches causing a loop. If this happens hit the new start pitch button.

Once you've created this patch, it can easily be extended, some musical possibilities are:
  • creating a transition matrix for note durations - it's worth marking sure the source MIDI file has been quantised and any tempo changes in the MIDI file have been removed to ensure consistent durations i.e. all 1/4 notes will always be exactly the same length, all 1/8 notes exactly the etc
  • extend the patch to be able to support more transition matrices, allowing you the algorithmic composer, to change between STM's created from analyses of different composers.
  • Create a second order transition matrix. Second order matrices consider the two previous notes when choosing the next note.
We'll walk through some of these Markov Chain composing possibilities and others in future Algorithmic Composition tutorials.

Subscribe to the RSS feed and check back soon for more algorithmic composition tutorials.


Anonymous said...

thanks for sharing this wonderful tips!

Anonymous said...

Great tutorial, Thanks!

One question, why do you start [seq] with the message "start 5536"? I can't understand what it does from the help file.

Algorithmic said...

Thanks for the comment. The 'start' message can be used with any value and it sets the speed that the seq object will playback the MIDIfile at.
To speed up the analysis I set the MIDI file to playback at a faster speed, you can set it fast if you want.

You can also put rhythmic data in a Markov chain and use this to generate more interesting rhythms. If you do this you have to scale the number back down with a multiply or divide to get it to play back at the right speed. I'll probably do a post on Markov chains and rhythms soon.

Hope this works for you!

rayo said...

Im waiting for the rhythmic example with Max or pd, I cant figure out how to do it myself... also an example with 3rd order would be great too. Anyway, thanks for the tutorial!

Algorithmic said...

Thanks for the comment
I've got a couple more rhythm tutorials coming, there'll be posted soon. In the mean time you cold try any other method to generate the rhythms. There's a post with a few rhythmic ideas here

Post a Comment