Second Order Markov Chains in PureData

It's been too long since the last algorithmic composition post, but a series of new posts are on the way!

To kick things off we'll revisit one of our previous Markov chain algorithmic compositions. Previously we looked at first order Markov chains in PureData. We also extended this into a second order Markov chain in Max.

Let's have a quick recap first.

First Order Markov Chains
In a previous Algorithmic Composition post we built a first order Markov Chain analysis and generation patch. In 1st order Markov chains the next note is based on the current note and a list of probabilities for following notes. This is stored in a State Transition Matrix (STM), here's an STM that lists the notes of Happy Birthday and the probabilities of each subsequent note.

Second Order Markov Chains
Second order Markov Chains choose the next note based on the two previous notes and the probability of subsequent notes following those two notes:

Algorithmic Composition with OpenMusic | Markov Chains and Rhythm

Previous Algorithmic Composition tutorials have looked at using Markov Chains in OpenMusic, using some of the functions available in the OMalea library to analyse the pitches of a MIDI file and create new algorithmic compositions based on these.

Today we're looking using Markov Chains in OpenMusic to generate rhythmic patterns for algorithmic compositions.

Our previous OpenMusic tutorial used these functions from OpenMusic's OMalea library:

• ana-mark to analyse a MIDI file to create a transition table of pitches and
• markov1 to generate a new algorithmic composition based on the transition table.

Although we were previously using our Markov chain to analyse and generate pitches, you can also use ana-mark and markov1 from the OpenMusic OMalea library to generate rhythms.

Algorithmic Composition: Markov Chains in Max MSP

We've looked at using Markov Chains for Algorithmic Composition in PureData, Markov Chains in Keykit and Markov Chains in OpenMusic in previous posts.

In today's Algorithmic Composition tutorial we'll look at using Markov Chains in Max MSP to analysis existing music and generate new algorithmic music.

We'll start off by recreating the Markov Chains in PureData example and then extend it with some new features. Creating the Markov Chain in Max is similar to composing in PureData, so if you haven't read through the Markov Chains in PureData post yet it's worth doing that now.

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.

OpenMusic Markov Chains and omlea

We've looked at using OpenMusic for algorithmic composition in a number of posts before, we've also looked at using the OpenMusic OMalea library and random walks in OpenMusic. Today we're going to use OpenMusic and OMalea to work with Markov Chains.

Markov Chains are a very useful tool for the algorithmic composer, we've looked at Markov Chains in keykit here. If you're not familiar with how Markov Chains work it's definitely worth reading this algorithmic composition post.

In brief, Markov Chains chose the next note using a probability. For example if the current note is E, there might be a 70% chance of the next note being a A and a 30% chance of it being an C#. These probabilities are stored in something called a transition table or transition matrix.

We can either create the transition matrix by hand or we can create it by analysing an existing piece of music (or any other piece of data).


This is the approach we'll take in today's post. We'll load up a MIDI file, create a transition matrix from this using the ana-mark function, and then generate new melodies based upon this.

1. First of all we need to load up a MIDI file. Create a new class MIDIfile, either by choosing from the menu or CMD clicking (CTRL click on PC) and typing midifile.

2. Evaluate the midifile class by hitting the 'v' key or CMD clicking on it's output (CTRL click on PC). This will allow you to load up a MIDI file, once it's loaded make sure the midifile class is selected and press b to lock it. This will ensure that you don't have to load the MIDIfile every time you evaluate the patch.

3. We next have to extract the pitch data from the MIDI file. We can also use markov chains to generate rhythm, dynamics and other musical information, but for now we'll stick with pitch. Add a mf-info function, this allows to extract each note from the MIDI file.

4. If you evaluate the mf-info function, you can see a list of lists that describe each note, something like this, where the values are pitch, onset, duration, velocity and MIDI channel
((64 1000 500 52 1) (73 1500 385 58 1) (74 1875 125 43 1) (62 2000 500 32 1))

5. We need to access just the first element of each set of parentheses: the pitch. There are a number of ways we can do this, but the simplest is to use the mat-trans function followed by the first function. Add these in one a time and evaluate them to see what they do. You patch should now look like this:

6. Now when we evaluate our patch we get a list of pitches. This can be fed into the ana-mark function (remember you need the omalea library enabled to be able to use this function - this can be turned on in preferences if it's not already).

The ana-mark function in OpenMusic automatically generates a Markov transition matrix for us of the form:
((list-of-pitches ((first-pitch-probabilities) (second-pitch-probabilities... ... (last-pitch-probabilities)))

Something like this:
((1 2 3) ((0.0 1.0 0.0) (0.333 0.0 0.667) (0.0 1.0 0.0)))

7. We need to be able to separate our list of pitches, the first element in the list [ (1 2 3) in the above example ] from the list of probabilities [the second element in the list]. For this we can use the Lisp functions first and second. You can type first and second directly into a new box to create them, or create them from the drop down menu. So far our patch looks like this:

8. We can now connect a Markov function. There are two Markov functions in the OpenMusic omalea library, markov1 generates a single next pitch and can be used with repeat-n to generate a series of pitches. Markov2 generates a series of pitches. Here we've added a markov2 function and asked it to create a series of 50 notes starting with the first note.

9. When you evaluate markov2 you'll notice that outputs the index rather than the actual pitch we entered. So if we were using notes 60, 64, 65 and 67 the markov2 function thinks of them as 1, 2, 3 and 4. We can easily map this index to our original list of pitches by using the posn-match function (position match). Your finished patch should look like this:

Now when you evaluate the patch, we generate a list of pitches based upon the original set of pitches in out MIDI file. To get a better understanding of what's happening at each stage, evaluate each function in turn by selecting and pressing v and looking at the output in the listener window. To get a better understanding of Markov Chains in general do have a read through a previous on Markov chains and algorithmic composition.

You can also try using the Markov chains to generate elements of your CSound scores as looked at in the post on algorithmic composition, OpenMusic and CSound - using the om2csound library.

Check back soon for more algorithmic composition techniques and tutorials.

Keykit | Algorithmic Composition Software

Keykit is a piece of algorithmic composition software that the developer describes as 'a programming language and graphical interface for manipulating and generating music'. It runs on Windows and Linux and is a free download available here: http://www.nosuch.com/keykit

Keykit read and write MIDI files so it can also be easily integrated with other programes and has a number of useful algorithmic composition tools:

We'll have a quick look at a couple of the algorithmic composition tools available:

Using Markov Chains for Algorithmic Composition
We'll use the Markov Maker tool to generate new MIDI files algorithmically. Markov chains choose the next note based on a probability factor. In the first example below, if our current note is an A, there is a 10% chance of the following note being an A again, a 60% chance of the following note being a C# and a 30% chance of the following note being an Eb. This table is called a transition matrix.

As shown in the second example, we can also base our next note choice on the previous two notes. This is called a second order Markov Chain. So for example if the previous two notes were G then D there would be a 100% probability of the following note being an A.

Transition tables can be created by hand, filling in the values that you'd like to work with, or we can create the transition table by analysing an existing piece of music, for example loading up a Mozart piano sonata and generating the transition table dile directly from this. Working with Markov chains in this way you can here the algorithmically generated piece having some similarities to the source piece of music. The higher order markov chain, the greater the similarity to the original.

"The "Markov Maker" tool lets you create music with markov-chain techniques. The top phrase window displays some existing piece of music that you read in, and the bottom phrase window display a "similar" piece of music that is created by the "Markov Maker."

1. Load up keykit and in a blank space, click and select tools 2, markov maker

2. Click - original -read file / load Smf. This allows you to load up a source piece of music in the Standard Midi File format.

3. Click original - set sim, the two values are the window size and window increment, the best settings depend on the source material and desired effect so do experiment.

4. Click the grey sim box, choose make sim and the number of generations you want to create. Every generation will sound different, you may need to experiment with the 'set sim' settings (step 3).

5. To save the file, click the grey sim box and choose snarf.

6. Click in a blank space and from tools 1 menu choose group.

7. In the group tool, choose file, read snarf. This will paste your markov generated composition into the group tool.

8. To save as a standard midi file, in the group tool click file, write / standard MIDI file.

We'll look at some further implementations of Markov Chains in future posts including creating implementations in PureData, Max and Lisp, so check back soon!