Transcript Introduction to Music Generation

RoBach
A Case Study in the
Use of Genetic
Algorithms for
Automatic Music
Composition
Introduction to Music Generation
• First attempt: 1956, Hiller and Isaacson, Illiac
Suite
• Many failed attempts since
• Unsolved problem: balancing structure and
novelty
More Novel
More Structured
Optimal Solutions
Music Generation Strategies
• Rule-based
• Learning by example
corpus
• Evolutionary
Genetic Algorithms
• Purpose: robust, efficient
optimization
• Other optimization
algorithms
• Calculus-based: needs
continuity and derivatives;
local search scope (which
hill to climb?)
• Enumerative: inefficient
• Random: more inefficient
• GAs need no auxiliary
information
• GAs search from many
places at once
• GAs constantly seek
improvement
Genetic Algorithms
• GAs work with codings of parameters, not
the parameters themselves
• Codings are strings in some applicable
alphabet
• Implementation-specific requirements
• Routine to interpret strings
• Routine to judge the fitness of strings
Genetic Algorithms
• Generate population of random strings
• Three step generational loop:
String
Fitness
1
x
=
+
M
1
Fitness
?
?
2
x
=
+
2
?
?
3
x
3
Initial Population
String
Reproduction
=
+
Crossover & Mutation
• Every iteration yields ‘current best’
solution
?
?
New Population
The Corpus - Bach’s Chorales
• A corpus of works provides the basis for statistical
data
• Almost 300 Bach chorales were analyzed for
histograms
• Frequency of intervals, chord changes, and phrases were
collected
• Reasons for using chorales as models:
• Highly Structural
• Large existing corpus
The Composition Object
• The Composition object was designed to match
the structure of a chorale
• 4 voices
• Sequential chords
• Serves as the interface between composers and
critics
Composition
Voice 1
Voice 2
Voice 3
Voice 4
Chord
List
Introduction to Haskore
• Haskore is a programming environment
designed for music composition
• It is implemented in the functional language
Haskell, which is useful for list processing
• Haskore defines lists of music objects that
can be generated and manipulated
recursively
• Our “Composition” object contains a list of
notes for each voice, making it favorable for
this environment
Music Composer Building Blocks
• Each composer consists of several “building
blocks”
• Building blocks determine the various
characteristics of each composer
• There are two basic types of building
blocks:
• Generators
• Chords
• Modifiers
• Rhythm
More on Building Blocks
• Sample composer:
• {a, b, c, d, e, f, g, h}
• Each letter represents a different building block, layered
onto the composer
a
b
c
d
e
f
g
h
• There are an infinite number of combinations of
building blocks: {a, b, c, g, e, d, a, a, a, g, e, d, …}
• This means an infinite number of composers,
generating an infinite amount of music!
More on Building Blocks
• There is an infinite number of composers!
Composer blocks are not commutative:
{a, b} is different from {b, a}
Each composer can have an unlimited number of blocks:
{a, b, c, d, e, f, g, h, a, b, c, d, e, f, g, h, a, b, ... }
Unfortunately, not all of them are good...
{a, d, e, a, b}
{e, c, d, d, e, b, a, b}
{d, e, b, c, e, a, b}
{c, b, a}
Inside a Composer
{d, d, b, a, e}
{a, g, h}
{e, a, h, h, h, h, h, h}
{f, g, a, b, c}
• Defined by a “genetic sequence”
• Chromosome --> Word32 (32-bit binary string)
• 32 string can be divided any way we choose
{c, h, g, a, a, b}
[01100101111000011101100101001100]
• Contains code for composer’s traits
• Traits controlled include:
•
•
•
•
Harmony
Melody
Rhythm
Order tweaker
A Composer’s Genes
• Composer blocks are called by genes within the traits
• Each gene (binary combination) represents a composer block
• The number of composer blocks available -> number of bits per gene
• Ex. 3 bits -> 8 combinations -> 7 composer blocks
• Translator calls the blocks represented each combination
• To mix things up, tweaker mixes rhythm genes with melody genes The blocks
then modify the composition
• 000 tells the translator to call nothing
• Can call multiples of the same block
Gene
Melody (trait)
[ 0 1 1f0•0 z
1f 0•1 b
1 1•1c
1 0•0zz
1 0x
•1a0z0 1 1 0 0 ]
c0 0• 0xd0 1• 1da1 •0 1aa
Trait
2 calls
Critic Building Blocks
Mathematical analysis of music
• Histogram comparison
• The degree of feature similarity is analyzed
with a method similar to chi-square
• Intervals
• Chord Progression
• Melodic
• Rhythms
• Similarities, Differences
• Phrasing
• Patterns in rhythm and intervals
Implementation of Critics
Survival of the Fittest
Composers
In
The
Bad
Critic
Functions
The
Good
Genetic Structure of the Critics: Part 1
{156, 129, …, 61}
{31, 165, …, 142} {5, 2, …, 1}
{19, 189, …, 54}
{16, 91, …, 122}
• Different critics evaluate the same music differently, much like many
people like different genres of music
• Having many critics will yield a variety of music, instead of allowing one
type of composer to dominate
• Critics define weighting vectors for the critic functions, that is, how
strongly they value each one in their analysis
• The 32-bit chromosome must define the 14 weights to create a critic
• The best critics are the ones that give the largest score difference between
“bad” (current) music and the selected corpus
Genetic Structure of the Critics: Part 2
• Each ci is associated with a particular critic function,
while d and e apply to all critic functions
• d is the index to the array a, containing possible values
for the scaling factor ad
• e defines whether the scale will be power or
exponential
• The weight of the ith critic function is given by:
• wi = ad^ci, if e=0
• wi = ci^ad, if e=1
Experiment Setup
• Using our definitions for composer and critic
blocks and chromosomes, we created an
environment of 20 composers and 20 critics
• Each epoch consisted of:
• Evolve the composers for 100 generations
• Define the current music as the bad corpus
• Evolve the critics for 100 generations
• After many epochs had passed, we listened
to the results
Experiment Results
10111000011101010100001000000110
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
Good Music 1
Analysis of Results
Bad music
Good Music 2
• Every epoch converged proving a successful genetic
algorithm
• Music that scored poorly was worse than music that scored
better
• Ratings improved after each epoch
800
704
700
Good Music 3
600
500
470
400
Good Music 4
300
rating
278
200
100
Real Bach
Music
51
0
epoch 0
epoch 2
epoch 4
epoch 6
Future Improvements
• More composer/critic blocks (longer string)
• Composer blocks implement histograms
• Composer blocks correspond with critic
blocks
• Next experiment
• Larger population, more generation
• Add brand new melody modifier block
1337 pR353N70r5
Adam Aaron
Melissa Fritz
Adam Bildersee
Tim Heath
Rebecca Cooper
Kyle Leiby
Malamo Countouris
Yunxue Xu
Carlin Eng
Luke Zarko
Special Thanks to Joel Donovan and Peter Lee!