Friday 24 November 2017

Music Theory, Genetic Algorithms, & Python

This month we had a meetup focussed on algorithms creating music. We also had a flash talk on 3D L-systems.


The slides are here: [link] - the embedded music playback needs Firefox or Chrome to work, Safari doesn't seem to work.

A video of the event is here: [link].


Computer Generated Music

The idea of using mathematics, logic, computer programs to generate art is a long established and noble challenge, that forces us to think even more deeply about art itself, about the extent to which art can be random, or conform to man-made rules, and whether there is something about art that can't be captured in such simplistic logic.

That philosophical debate aside, people have created amazing sophisticated art from apparently simple ideas and mathematical rules - algorithms.

Creating music from algorithms is particularly challenging as our senses are less forgiving than when we look a visual creation. Randomly coloured and placed dots are much more tolerable than randomly chosen musical notes.

We were lucky to have Nicholas, a classically trained musician and a huge tech leader and community contributor, take us through his experiments creating music using a computing approach called genetic algorithms.


Genetic Algorithms

Like several approaches to computer intelligence, genetic algorithms are inspired by how nature itself works. Just as natural selection and mutation allow species to evolve to solve emerging challenges, genetic algorithms evolve solutions to better solve challenges we might set.

Genetic algorithms are particularly useful when we don't know how to directly solve a problem, but we know a bit about how good solutions should behave, enough to score them against each other by how well they solve a problem.

The basic idea is to start with a set, or population, of potential solution candidates. Without additional insight, these can be randomly created.


We then apply to this population of candidates the same processes that apply in nature:

  • crossover - as a result of 2 parents mating, mixing their characteristics, to create a child
  • mutation - random changes to an individual which can be beneficial or detrimental
  • selection - survival of the fittest to continue a new generation, and the removal of the unfittest

We're familiar with these processes happening to animals and plants in nature, with DNA being the solutions that are mixed and mutated, before tested for survival.

The fact that DNA is a sequence of codes, which are interpreted as instructions to create a living organism is very helpful. We can easily apply these ideas to codes or programs which we create in a computer. In our case, our solutions, or individuals, are sequences which represent music. Again, that's not an unfamiliar idea - musicians use a code for writing music - music notation and letters.

Let's illustrate crossover - which happens when two parents mate and mix their codes.


You can see how the children get their code from their parents but it isn't exactly the same. In effect, a section is swapped between the parents code and the result becomes the children's code.

Mutation is a simpler idea, we simply pick a piece of the code and randomly change it.


These two processes create new individuals in the population, which we then sort by fitness, removing the unfittest. What's left is the next generation population.


Judging individuals for fitness is just the same as deciding how good their code is at solving the problem we've set. Those problems might be finding a route out of a maze, or deciding how a character in a computer game behaves, designing the right shape for an antenna, ... or creating pleasing music.

This process is repeated many times until we find a good solution, or decide we've spent enough time evolving and want to pick the best we have.


Creating Counterpoint

Nicholas set out to use this evolutionary computing approach to see if a computer could create music that was musically correct and pleasing. That's not an easy task for a human, so it's a particularly worthy and interesting problem to see if we can get a computer to do it.

The particular task that Nicholas focussed on was composing an accompanying counterpoint to a base musical sequence. The following shows the basic idea.


The red points are musical notes which vary in pitch and appear at different times. The green points are additional notes which are attempt to create a pleasing additional layer of sound which works with the original series of sounds.

A counterpoint is a contrasting yet complimentary series of notes. See Nicholas's slide 4 to hear an example.


Nicholas explained several ways in which a counterpoint might be composed. His visual approach to showing the transformations demonstrated how familiar the ideas really are.

 

But these transformations themselves aren't enough to create a pleasing composition for music of any sophistication. So how do we create counterpoint?

Well, in 1725 a chap called Johann Joseph Fux wrote (in Latin) a treatise on counterpoint.


He established five levels of sophistication for creating counterpoint, called species.

A very simplistic indication of what these five levels are:

  • First species - a note is added for each note in the original base sequence. This means the contrapoint can't vary rhythmically from the base because the new notes appear at the same time as the original ones. However there are a set of other constraints like avoiding notes which are ten steps apart in pitch. See here for a more comprehensive list.
  • Second species - two additional notes for each original note. There are yet more constrains such as accented (emphasised) beats not being dissonant
  • Third species - 3 or 4 notes for each original note. There are further guidelines on what is permitted and which combinations are to be avoided.
  • Fourth species - introduced sustained notes, which are held for longer than the time a note would take in simpler compositions.
  • Fifth species - a combination of the first four species, and the most difficult to get right.


Nicholas's aim was to encode these constraints on how counterpoint notes are chosen in terms of pitch and temporal location as a fitness function for a genetic algorithm.

In other words, creating a population of candidate counterpoints, using cross-over and mutation to create new variations, and then using a fitness function to pick those that best match the rules developed by Fux.

His code is online at GitHub - [link].


Results

How to test how well the evolutionary approach to developing valid and pleasing counterpoints? The best test is a human audience, and so we had a series of very fun and engaging Turing-tests to see if we, mere humans, could tell if a piece of music was composed by a human or by Python!


For all the examples, broadly the audience was split 50-50 on judging the computer vs the human composer.

In other words, the computer generated music was indistinguishable from that composed by a human!

Have a go yourself, the tests start on slide 21.


Algorithmic Art?

Many will debate whether music created by a computer is valid art. And many others will challenge the attempt to reduce human creativity and sense of beauty (and horror) into simple, even simplistic, cold hard rules.

But what is clear, is that the creations of algorithms are very close to what we humans can produce. And that is a testament to our ability to come up with algorithms. That itself is a worthy science and art.

And the endeavour to develop these automated ways of creating convincing art forces us to explore, understand and appreciate art created by traditional means even more deeply - which can only be a good thing.


Many were looking forward to this event, and afterwards it was clear everyone was buzzing with excitement, possibilities and some were even inspired to continue their own work on algorithmically generated music.


3-D L-Systems

I was really pleased that a regular member, James, offered to do a short talk to share his work on an app which creates three-dimensional L-System forms.

He was inspired by a previous session on Lindenmayer systems, which create patterns from the successive transformation of a sequence of instructions according to a set of rules - so there are parallels with genetic algorithms which also manipulate a sequence of instructions.


You can find out more at http://talknotes.amimetic.co.uk/code-sculpture-create-3d-shapes/, and see examples on his twitter @complexview.


Resources

  • A simple tutorial on genetic algorithms with good coverage - [link].
  • NASA's use of genetic algorithms to optimise an antenna - [pdf].
  • The text book I was set when I studied genetic algorithms - [link].