Marlin’s Gottahack
– 1998 Sep 28 – PREV HOME NEXT
Genetic Algorithm
Counterpoint
---------------
A couple years ago
I did an experiment with counterpoint composition that has shaped some of my
thinking about what I believe should be the structure of an automatic
composition system. I will confess up front that counterpoint is probably the
most mechanical (algorithmic) and most constrained of all composition system
and thus lends itself most clearly to computer implementation, so one must be
careful about trying to draw too many far reaching conclusions. None the less
it did very well in the sub-domain of species one counterpoint and I think that
the ideas could be easily extended.
I know that I have
discussed this with some if not all of you already, but I have never written it
up so here goes.
History
---------
Counterpoint is an
early form of music the evolved out of Gregorian chant. It reached its peak in
the music of Palestrina in the 1500's and Bach in the 1600's to 1750. The basic
thread of musical evolution in that time period was from music that was
essentially melodically structured to music that was harmonically structured.
In extremely broad strokes what happened was this.
1) Single melodies,
chants, are written.
2) Simple 2 part
parallel harmonization is invented. (second person sings same melody shifted up
a third or shifted up a fifth. This means that the "harmony" is
really a melody, the same melody, itself)
3) The harmonies
evolve away from the parallel motion you get when you sing a melody against
itself. The idea becomes one of having a second melody that fits in nicely with
the first one. This is counterpoint - literally one point or note counter to
another.
4) Counterpoint
develops in several directions like having rhythmic variation between the two
melodies or going beyond two voices to stacking up three, four, or five
melodies all at once. This is polyphonic music which probably reached its peak
with Palestrina.
5) In the next
century there was a shift in thinking. In Palestrina's day you wrote a melody
against a melody and if the harmony did not quite work out, tough, the voices
had to work independently as melodies. By the time Bach was banging out
counterpoint the thinking had shifted from polyphony to homophony, single
melody with harmonic accompaniment. The basic shift was the harmony no longer
sacrificed to melody, instead the harmony was king and if an inner voice had to
cave into a harmonic demand and not be quite correct as an independent melody,
tough.
Counterpoint and
polyphony are essentially obsolete forms these days in the sense that basically
since Bach's time harmony is king and independence of voice is not really a
major consideration. However counterpoint is taught to all music majors, both
for historical reasons and because there is value in learning how to weave
independent voices together. I mean, if you can get your harmony AND your
independent melody too, why not. Furthermore, among the theorists of music, it
is believed that it is the invention of counterpoint that directly led to the
invention (discovery?) of harmony. It is the reason that western music is so
harmonically structured (rather than rhythmically structured as is Indian
music, African music, an much of Asian music)
Practice
---------
Counterpoint is
taught by breaking it up into about 6 species. This is an instructional system
only, meaning no significant music was ever written in the species, they are merely
a graded path to help the student acquire the means to learn counterpoint. The
simplest form, species one, eliminates all rhythmic variation. The melody
consists of a stream of whole notes, one per measure. This melody is considered
given by GOD and is called the cantus firmus (fixed voice) and your job as a
student is to write a single melody also consisting of a single whole note per
measure that fits with the CF.
You are given a
pile of rules about how you are allowed to move the voice that you are writing.
The rules look something like this:
First we define
some terms.
skip - Any melodic
step that is greater than a second
parallel motion -
both voices move the same direction e.g. both go up
contrary motion -
voices go in opposite directions.
Oblique motion -
one voice stays fixed the other moves
1) Allowed melodic
intervals - Everything up to a major sixth and the octave.
2) Forbidden
melodic intervals - sevenths, or anything greater than an octave. Anything
diminished or augmented.
3) Limits on successive
skips - two skips in the same direction should not total more than an octave
4) Allowed harmonic
intervals - unison, third, fifth, sixth, octave, octave + third, octave + fifth
etc.
5) Forbidden
harmonic intervals - second, fourth, seventh
6) Forbidden
harmonic motion - you may NOT move parallel and land on a fifth or an octave.
There are more
rules but these give the flavor. The above are quite mechanical. Allowed or NOT
allowed.
The others are less
mechanical. They look like this.
1) Contrary motion
is better than Parallel motion.
2) Skips tend to
imply a change of direction e.g. step down, skip up, step down
3) Voice crossing
is tacky
In essence there
are a pile of rules that are absolute and others that are things that are
encouraged or discouraged.
Programming
----------------
After briefly
considering a structure where the computer would compose a melody by choosing
the next note from among the next allowed note and backtracking when you get
into trouble, I choose instead use a genetic algorithm. I create random
melodies, breed them with one another, score them based on how well they follow
the rules and kill the weak melodies.
The genetic
algorithm is of course just looking to minimize an objective function and in
our case the objective function is just how well it follows the rules. I make
no distinction between absolute rules and rules of encouragement, I just give
harsh scores for absolute rules. Fore example, I set the cost of using a
harmonic interval of a 4th (which is forbidden) at 1000 points. I set the cost
of using parallel motion at 1 point, contrary motion is 0 points. Thus contrary
is preferred to parallel but not by much.
Given that we are
in the sub-domain of species one counterpoint, the genetic mutation an
dcrossover is quite easy, when you breed two melodies you simply follow one for
a while then switch to the other for a while and occasionally throw in a random
note. (One of the problem I am thinking about is how to extend this model up to
a rhythmically richer domain where I may wish to insert 2 notes where I once
had one, but I don't want to screw up the timing and cause the back half of the
melody to misalign with the CF.)
Outcome
-----------
It worked great.
Given short melodies, less than 20 notes, it would converge in a minute or so.
The counterpoint sounded fine and was faster than I could do by hand.
What was nice about
the GA structure is that I could easily add new rules and I could easily change
the costs of violating any rule.
Having no
"fixed" rules allows me to violate any of them at any time. For
example I did the experiment, where I nailed down a single note. I.e. I forced
the third note in the piece to be a C# which was dissonant with the cantus
firmus and the GA was forced to find a solution that ran through that C#.
Except for that one dissonant note, the piece was harmonically sound and it of
course followed all the melodic rules.
Having a single
scoring function allowed me to write my own solution to a counterpoint problem,
score it and compare it to the one that the computer generated. In all cases,
my solution was "inferior" - meaning that it had a higher score - to
the one that the GA found.
Of course,
sometimes, I liked my solution better, it sounded better to my ear, than the
one that the machine generated. In those cases, I would compare scores, see why
it had gone the way it did and then I would change the weights on some of the
rules, or add new rules to force it to generate my solution. This gave me the
feeling that what I was doing was modifying the score function so that it
matched my aesthetic judgments.
There is an
important point here. The scoring function could look at a CF and the solution
and analyze it. It would tell me what it considered to be wrong (or right)
about a composition. I could take a piece I was working, nail down the parts I
liked and have it grind on the transition sections.
Overall, this is my
model for how a computer generated music system should work. There is no
"hardwired" logic, rather everything is done with weighted rules. The
weightings can be changed to match any particular aesthetics. One can even
imagine that one could do something like the following: You develop this system
that is able to do automatic composition and then you train it in a style, say
Mozart's. You do this by giving the system the melody for the Jupiter symphony
and asking it to write the bass line, or any of the other parts. In each case
you jiggle the weights of the system so that it produces the result most like
the bass line that Mozart actually wrote.
Drawbacks - areas
for further work
--------------
1) It was a toy
domain. There was no consideration of the rhythmic aspects of composition.
2) There was no
attempt to capture the notion of sequence. Sequence is the repetition of certain
aspects of the music. For example the Duh duh duh DUUUUH of Beethovan's 5th is
a rhythmic sequence repeated all through the first movement with different
notes. You can also have intervalic sequence, where you may have notes in the
pattern, up a second, down a third, up a second, and you want to repeat that
pattern starting on different notes.
3) The problem in 2
shows up at different scales all through music when you create a FORM. For
example a "classic ragtime" would have the structure AABBACCDD. It
seems to me that if you are going to compose a ragtime piece it is appropriate
to give the system the task of designing ABCD which you then output in the
final form, rather than having it design AABACCDD. (the point being that the GA
converges faster on shorter strings so rather than giving it a scoring function
that includes the structure, you factor out the overall structure and have it
design the pieces.)
Future Directions
---------------------
I think that the
main thing that I want to do next to further this work is to develop a language
for representing the musical information so that one can write rules in a form
that makes sense. I also want to keep the system closely tied to analysis as
well as composition. What I mean by this is that it is fairly easy to write the
code that will take 4 sections, ABCD, and output them as AABBACCDD. It is more
work to analyze a piece and observe that structurally it is in the form
AABBACCDD and therefor a rag. Nonetheless it seems to me that if you work only
on compositional aspects and not analytical aspects you will get yourself into
the problem that the system is not able to look at and learn from existing
music.
I look at it in the
light that composition is the function that takes you from a nebulous domain of
"I want to write a rag" to a specific example of a rag. Analysis is
in some sense the inverse of that function that takes you from a specific
example to all the abstract representation, "Ah this is a rag and that is
the trio section and I can see from having looked at a lot of rags that the
trio section is almost always in a key 1 fifth away from the starting key of
the rag."
At some point I
will want to start passing code around with these news letters, but that will
be a while off.
Book Recommendation
----------------------------
The Music Theory
Handbook by Marjorie Merryman
It is a very good
concise text on music theory. You can get it at amazon for $12. It will make
some of the discussions of music easier if I can just refer you all to a
section of the book rather than recapitulate in email. Here's the URL.
http://www.amazon.com/exec/obidos/ASIN/0155026623/qid=906936277/sr=1-10/002-1146671-4974650
Solution to Puzzle
#1
---------------------
In the miscounted
vote each person got exactly 6 points. How could a person get 6 points? It must
be the sum of 3 numbers each of which is 1, 2 or 3. The only possibilities are
1+2+3 or 2+2+2.
However the 2+2+2
possibility could not occur because if one person collected three of the 2
votes, there are not enough 2 votes left for the other people. (Since each
person gets to vote exactly one 3 one 2 and one 1 there are exactly 4 of each
one of those votes)
So now we know that
each person got exactly the same configuration of votes namely 1+2+3.
Since there were 3
liars we know that the honest person got three lies so his original score,
1+2+3 is now really 3+2+1 ie. he stays at 6 points.
Each of the other
guys has two lies and one honest vote. If we mark the honest vote with a star
we can look at the old vote and the new vote.
the guy ranked poor
by the honest fellow got *1+2+3 -> 1+2+1 = 4
the guy ranked
middle by the honest fellow got 1+*2+3 -> 3+2+1 = 6
the guy ranked high
by the honest fellow got 1+2+*3 -> 3+2+3 = 8
So you can see that
the guy that the honest fellow thought was top was the final winner of the
competition, the honest fellow tied for second place with the fellow that he
thought was mediocre, and last place goes to the fellow that the honest person
did not like.
Next week
---------
Some comments on
how to implement genetic algorithms so that they consume less resources and run
a little faster.
Also, I am thinking
about writing a container application for these notes. (I built some toy note
taking apps a few years ago and now that I am writing more regularly I think I
might ressurect one of them)
jokes - I need some
jokes for this thing. If I don't get any from you all, I just may have to tell
you the one about the catholic ackolyte that I got from my sister. Till then
here is a semi musical one:
Joke
----
Stallone, Van Damme
and Schwartznegger are choosen to star in an Action/Music Movie. They figure
with all these box office studs the thing is sure to be a success. So confident
are they that they let each actor choose his own part.
Stallone say he is
into the boy genius thing and wants to be Mozart. Claude likes the piano so he
opts for being chopin. Of course Schwartznegger just says, "I'll be
Bach!"