Generate Music Algorithmically

[jaberwacky]

http://architects.dzone.com/articles/algorithm-week-generate-music

If you're on Reddit you may have seen this aleady. I'm sure there are a few folks around here who might take interest in this. Article full text follows. (Probably best to follow the link because of formatting issues.)

What is a Markov Chain?

The algorithm of the week is a Markov Chain. Using this technique you leverage a little bit of probability to do some light machine learning. In this case, input a song and have the computer create an original work based off the patterns you’ve taught it.

I’ve attached a sample song. Give it a listen. I think you’ll be somewhat surprised that that’s a completely computer generated song. Only somewhat… it’s not very good, but it definitely isn’t predictable and yet isn’t noise either.

Click here to open the example as a .wav file

How’d You Do That?!

There’s a fairly simple computer science technique known as a “Markov Chain”. Don’t let the whole reference to computer science fool you, it’s really not tough to grasp. Basically I created a table of numbers that answers the following question: When note X was played what percentage of the time were the other notes played next? So just imagine a table with all of the notes from a to g# laid out on top (these are the notes that we last played) and vertical axis is all of the same notes but this axis represents the probability that that particular note was played next.

Here’s a sample of what my program generates:

a  a# b  c  c# d  d# E  f  f# g  g#
a [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
a# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
b  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
c  [0, 0, 0, 6, 0, 1, 0, 0, 0, 0, 2, 0],
c# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
d  [0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0],
d# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
E  [0, 0, 0, 1, 0, 2, 0, 3, 1, 0, 0, 0],
e# [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0],
f  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
f# [0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 2, 0],
g  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
g# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

This is called an “adjancency list”. I’ve populated it with the music to Twinkle Twinkle. Let’s answer a question using it. How often does playing a C note lead to us playing another C note?

First we look up C on the left column and follow the row to the column labeled C. We get the answer 6. In order to figure out how often we play C given that we just played C though we need to know how many times we played a C note first. Adding up all of the values in the row gets us 9. So 6/9’s of the time (or 2/3) playing a C note will lead to us playing another C note.

Here’s the timings table (1, 1/2, 1/4, 1/8, 1/16 notes):

1  2  4  8   16
1 [0, 0, 0, 0,  0],
2 [0, 0, 0, 1,  0],
4 [0, 0, 3, 5,  0],
8 [0, 2, 4, 11, 0],
16[0, 0, 0, 0,  0]

But that’s it, that’s the magic that drives the whole process. As you can see, I’m actually not storing percentages but instead just the count of the number of times a note led to a different note. It works out to be the same thing in the end.

Code

Of course we need to see some code! As usual, I’ll start with the highest level and drill into it in more detail.

This portion of the code records the notes for “Twinkle, Twinkle” into the music learner I create. Then I tell it to give me 100 notes based on what it’s learned:

expandcollapse popup

class MusicMatrix:
def __init__(self):
     self._previous_note = None
     self._markov = MarkovBuilder(["a", "a#", "b", "c", "c#", "d", "d#", "e", "f", "f#", "g", "g#"])
     self._timings = MarkovBuilder([1, 2, 4, 8, 16])

def add(self, to_note):
     """Add a path from a note to another note. Re-adding a path between notes will increase the associated weight."""
     if(self._previous_note is None):
         self._previous_note = to_note
         return
     from_note = self._previous_note
     self._markov.add(from_note[0], to_note[0])
     self._timings.add(from_note[1], to_note[1])
     self._previous_note = to_note
    
def next_note(self, from_note):
     return [self._markov.next_value(from_note[0]), self._timings.next_value(from_note[1])]

# Playing it comes next :)
#test = [['c',4], ['e',4], ['g',4], ['c5',1]]
#pysynth.make_wav(test, fn = "test.wav")

musicLearner = MusicMatrix()

# Input the melody of Row, Row, Row Your Boat
# The MusicMatrix will automatically use this to
# model our own song after it.
musicLearner.add(["c", 4])
musicLearner.add(["c", 4])
musicLearner.add(["c", 4])
musicLearner.add(["d", 8])
musicLearner.add(["e", 4])
musicLearner.add(["e", 4])
musicLearner.add(["d", 8])
musicLearner.add(["e", 4])
musicLearner.add(["f", 8])
musicLearner.add(["g", 2])

musicLearner.add(["c", 8])
musicLearner.add(["c", 8])
musicLearner.add(["c", 8])

musicLearner.add(["g", 8])
musicLearner.add(["g", 8])
musicLearner.add(["g", 8])

musicLearner.add(["e", 8])
musicLearner.add(["e", 8])
musicLearner.add(["e", 8])

musicLearner.add(["c", 8])
musicLearner.add(["c", 8])
musicLearner.add(["c", 8])

musicLearner.add(["g", 4])
musicLearner.add(["f", 8])
musicLearner.add(["e", 4])
musicLearner.add(["d", 8])
musicLearner.add(["c", 2])

random_score = []
current_note = ["c", 4]
for i in range(0,100):
print current_note[0] + ", " + str(current_note[1])
current_note = musicLearner.next_note(current_note)
random_score.append(current_note)

pysynth.make_wav(random_score, fn = "first_score.wav")

The MarkovBuilder is where the algorithm is hiding. Notice how the MusicMatrix is keeping track of the previous note for us? The MarkovBuilder needs to be told explicitly which notes connect to which.

expandcollapse popup

import random

class MarkovBuilder:
def __init__(self, value_list):
     self._values_added = 0
     self._reverse_value_lookup = value_list
     self._value_lookup = {}
     for i in range(0, len(value_list)):
         self._value_lookup[value_list[i]] = i
     # Initialize our adjacency matrix with the initial
     # probabilities for note transitions.
     self._matrix=[[0 for x in range(0,len(value_list))] for i in range(0,len(value_list))]

def add(self, from_value, to_value):
     """Add a path from a note to another note. Re-adding a path between notes will increase the associated weight."""
     value = self._value_lookup
     self._matrix[value[from_value]][value[to_value]] += 1
     self._values_added = self._values_added + 1
    
def next_value(self, from_value):
     value = self._value_lookup[from_value]
     value_counts = self._matrix[value]
     value_index = self.randomly_choose(value_counts)
     if(value_index < 0):
         raise RuntimeError, "Non-existent value selected."
     else:
         return self._reverse_value_lookup[value_index]
        
def randomly_choose(self, choice_counts):
     """Given an array of counts, returns the index that was randomly chosen"""
     counted_sum = 0
     count_sum = sum(choice_counts)
     selected_count = random.randrange(1, count_sum + 1)
     for index in range(0, len(choice_counts)):
         counted_sum += choice_counts[index]
         if(counted_sum >= selected_count):
             return index
     raise RuntimeError, "Impossible value selection made. BAD!"

Again this class’s sole reason to exist is to track how one value we give it leads to another, and it facilitates picking values to give us that are informed by what has happened in the past. It’s important to note that we don’t just pick the value that occurred the most. If we did that it would make our program much less interesting. Instead we use the “randomly_choose” function to choose a next value in a weighted manner (very similar to Bayes Theorem for those of you wondering).

Grok’d

So to summarize, my program was able to generate the music because I fed it a sample musical score and it figured out what percentage of the time a c note led to another note. Here’s a step by step run through:

Give program a note and a timing. - When I give it a second note/timing it notes in it’s table that the first note led to the 2nd note one time. It also notes that the first timing led to this 2nd timing one time. (note I don’t attempt to relate notes/timings, it’s not important surprisingly).

Enter a third note. - The program then notes in its table that the 2nd note led to the 3rd note one time. - Continue ad inifinitum So that’s how we set the system up. Next this is how we get the program to come up with its own song:

Choose some random note/timing to start. - Ask the computer to suggest what a good note/timing would be to follow those. - print out the note/timing (in case it’s a work of genius

play each note using the python library I’m using, pysynth.

Here’s a link to my git repo with all of my Python code: http://github.com/jcbozonier/MarkovMusic/tree/master

That’s all for now!

Edited April 30, 2013 by jaberwocky6669

[czardas]

This is interesting. To make a computer create melodies, random selections are not only necessary, but also weighted values are needed. It's best if the melody gravitates towards some kind of tonal centre. I see the rhythmic values in your table as missing tuplet divisions. Perhaps it's me who's missing something. Another aspect which seems uncomfortable for some programmers is the undefined element of music performance. My Hirajoshi wind chime sometimes sounds as if a musician is playing the notes, because of the freeness generated by the wind simulation. In fact such freedom is best when limited to within predefined boundaries.

My approach is somewhat different. Start with full bars and omit or concatenate note durations. Try to get a balanced variety of rhythmic values and then select your main notes. These are the notes you want to emphasize and must be placed at a convenient places in the rhythm so that they stand out. Then fill in the gaps with scale movement or with leaps from above or below.

Alternatively select a harmonic sequence of chords as a template. Thread your melody through the chords like you would a needle through several layers of cloth. Then scrap the notes you didn't use. Combining both methods is possible. Using other people's music as a template is an interesting idea and in fact you could quite easily rewrite Bach's music.

After tinkiering around most of yesterday, I have created a using trinary. The fantastic power of trinary is clear. There are three kinds of note: consonant, dissonant and awful. The trick is to avoid hitting too many awful notes.

I finally decided the vibes was the best sounding instrument to listen to these three-chord progressions. There is no melodic element involved in my tests, but I'm very happy with the method. It's taken me a long time to get even close to creating artificial music. Just imagine a saxophone or similar instrument adding a voice above these progressions. It's not difficult to transform the harmonic foundation. It will take a bit of time and calculation to get it right though. The container is in place - it just needs filling.

BTW, your python code looks very nice.

Edited April 30, 2013 by czardas

[Richard Robertson]

Reminds me of something I found on Wolfram a while back. http://tones.wolfram.com/generate/

I can't actually use it because I refuse to install QuickTime, but I assume it's the same basic idea.

[czardas]

I also wouldn't install QuickTime again. Not even for this.

[jaberwacky]

Dont be mistaken, this isn't my code, idea or article. I just found it and thought it would be good to post it here.

[jaberwacky]

https://www.youtube.com/watch?v=jLR-_c_uCwI

Computer generated by David Cope's program Emily Howell.

Edited April 30, 2013 by jaberwocky6669

[TheSaint]

There you guys go , taking the magic out of real music and lowering it to some logical algorithm.

When people start to think too much about music , it's never the same again ... loses it's soul to machine interpretation and duplication.

Me sad!

[jaberwacky]

I should have slyly posted these to the Favorite Track of the Day thread to see if anyone would notice.

[TheSaint]

I should have slyly posted these to the Favorite Track of the Day thread to see if anyone would notice.

Bound to be as good as at least half of the stuff there.

If you program lives up to expectations (or promise of), then it shouldn't be too long before it creates an already existing song.

That will be the test, that it is valid ... or not ... music being as limited as they say it is.

[jaberwacky]

Oh sorry, this isn't my program.

[czardas]

jaberwocky, I just listened to the first video and it's got a nice devoloping theme. Fugues are so interesting.

@TheSaint If you were to take this argument further, you could argue that musical instruments take the soul out of music. It should not be some technological instrument that makes the music, but rather a singer. Anyhow people have been formularising music for millenia already without computers and I don't see a big difference personally. I think this kind of research will eventually improve user experience.

[TheSaint]

Oh sorry, this isn't my program.

When I say your (and I didn't, because I just noticed my spelling mistake), I mean your listing/notification to us of.

@czardas - indeed, some instruments may fall into that category, while many on the other hand, were created from the soul ... or a bit of both. While you are right for many forms of music that have been around for centuries or nearly so, I believe that part of the appeal of blues based rock and roll, is it's original lack of formula, though in the last few decades, it has indeed become formularized. I guess anything that exists long enough, becomes formularized. Still, even though we live in the era of cloning, I see no evidence of the spirit of the late 60' to late 70's being recaptured ... sure many have captured the sound, but not the essence of the songwriting or creative imagination. We live in a time where many elements of music have reached some kind of technical perfection, but alas all too often lack soul, depth, breadth, wonder, etc.

[jaberwacky]

We also live in a time where mainstream music is so youthful. The young want to pick up an instrument and immediately begin destroying. Someone comes along and tells them, "Hur hur hur, all yall need's three chords and a hook." And then their desire to have fame and fortune now now now is satisfied.

[czardas]

Musical taste is very much a personal thing. For me the computer is an aid for learning. If it can help improve my own understanding of a subject then I'm interested, otherwise computers are a waste of time. I think music is generally dismissed by the IT world as being nothing more than a means to make profit. I would like to illustrate this by mentioning two inexplicable and frustrating facts.

1. Musical symbols were designated unicode code points outside the basic multilingual plane.

2. Microsoft hid the midi console after Win98.

Although there may be other influencing factors at play, decisions such as these have a big impact on the creative use of the computer. The importance of music seems to wax and wane. When a bridge collapses, structural engineers get interested in harmonics. Research into sound is one of the cornerstones of ancient Greek philosophy and influenced the development of mathematics over a long period. Today scientists are interested the effect music has on the brain, birdsong dialect acquisition, the effect of harmonics in space and more.

Edited May 3, 2013 by czardas

[tobject]

I used to write a Music editor as part of my CS university thesis. Had to do daily trips to conservatory. We did pretty advanced stuff with music theory algorithms. Need to dust off my old Pascal source code and see if I can port it someday

[TheSaint]

I'm all for scientific studying of Music or Sound, for technological or medical benefits for humanity, but when music gets reduced to the point of saying, it sounds good because E follows C after D, then the magic is lost.

You only have to look at how much of the music created today sounds very much like each other, certainly in it's genre.

Certain people have now determined certain formulas and they tend to override everything else.

For me, at least, much of it sounds good, but lacks soul, depth and any real character. It might as well be created by robots.

Often, the only variation is the timbre of the singer's voice ... and even then, they are cherry picking certain types now.

[czardas]

@TheSaint This is how I see it: There is not only one music theory, but rather there are multiple, and often closely related, theoretical music systems used worldwide. There are the western rules of written syntax, and then there is the artistic lisence used by composers. There are theories about chord construction, and then there are chords invented by conservatory professors. There are break away streams like jazz with their own musical concepts. There are rules of composition used in Indian, Asian and East Asian cultures. Pop music doesn't feature much in the development of music theory. Making sense of it all represents a challenge. Intriguingly there are only two consistant themes in music throughout the world:

1. Rhythmic groupings of 2 or 3 beats.

2. The octave

@tobject I would be interested to hear more details of your project.

[TheSaint]

@czardas - now that's all too clinical for me.

I don't mind when harmonics are studied for technological benefits and safety or when tones or melodies are investigated for healing or calming purposes, but when music just becomes something technical on a piece of paper or computer screen, it's like taking the soul from a human and being left with a robot ... there is no warmth or magic.

For me, there is music and there is sound .... not necessarily the same things, though they relate.

In fact, from my perspective, much of the music these days is more related to sound than what I call true music.

How long has it been since we've had something truly original ... like Pink Floyd for instance or Black Sabbath etc etc.

Sure we have plenty of bands that sound somewhat like them, but where are their continuing equivalents, that are as refreshingly unique? I often feel that music is stuck in a rut ... probably why Irish music appealed to me so greatly when I discovered it and a number of other styles, like Bluegrass, Nouvea Flamenco, etc.

Too much music these days, again from my perspective, focuses on a sound and stays too closely attached to it. Much of the Heavy Metal movement is like that, but they aren't the only guilty ones. I was reared on the variety of tones etc you get from the Beatles, Stones, Purple, Zeppelin, Sabbath, etc. This meant, that when Heavy Metal came to my attention, I saw and still see it (despite my love of many of it's practitioners) as limited, narrow-reaching music. And yet Heavy Metal, the sub-genre of Heavy Rock, has been watered down even further and has a huge number of it's own sub-genres ... many of them based purely on a guitar sound or vocal style.

While we've never had more diversity of music, than now, strangely, much of it sounds weak and limited.

I guess, it's not that strange, when you consider the undue and unmusical influence of the Record Companies over the decades, who for the greater part, are only interested in making lots of money, and don't generally care a hoot about artistic endeavor, and often deliberately deter such adventures.

[czardas]

@czardas - now that's all too clinical for me.

That's fair enough, although I see algorithmic music generation as a mathematical science.

[TheSaint]

That's fair enough, although I see algorithmic music generation as a mathematical science.

My love for Maths is quite basic and I don't let it cross over into my bigger love for Music.

They are destined to never cross paths in my world.