(in-package :cm)
#|
In a Markov process past events represent a state, or context, for
determining the probabilities of subsequent events. The number of
past events considered by the process is called its order. In a first
order process the probabilities for choosing the next event depend
only on the immediately preceding event. In a second order Markov
process the probabilities for the next choice depend on the last two
events. A Markov process can reflect any number of past choices,
including the degenerate case of no past choices. A zero order Markov
Process is equivalent to weighted random selection.
Because past choices influence subsequent choices, a Markov process
can model, or mimic, different degrees of variation in patterns of
data. The higher the order, the closer the process comes to matching
the pattern it models. The pattern on which a Markov process is based
can determined by a statistical analysis of data or determined
directly by the composer. We will examine both methods for creating
Markov processes later in this chapter.
Markov Statistical Analysis
By analyzing data and extracting a set of outcomes and weights, one
can create Markov processes that generate chains with statistically
similar characteristics. An analysis for a first order table considers
successive pairs in the sequence: the first element in the pair
represents a past outcome and the second represents its successor. In
a second order analysis the window is 3 elements wide, the first two
elements are the past outcomes and the third element is the
successor. The analysis proceeds by moving the window over successive
elements in the data and counting the number of times each unique
outcome follows each unique past. We can perform an example first
order analysis on the following short data sequence:
a a b c b a
Which produces the following analysis pairs
aa, ab, bc, cb, ba, aa
The last pair in the analysis (aa) is produced by wrapping around to
the front of the sequence again so that the last element in the
sequence also has a successor. An analysis that wraps around creates a
seamless chain without any terminating condition. (An alternate method
of analysis encodes a unique terminal value, call it z, as the
consequent of the last a. When z appears from the chain the caller
will knows that the Markov process cannot generate any more events.)
The next step in the analysis is to count each unique outcome for each
unique past, giving us the raw counts shown here
a b c
a 2 1 -
b 1 - 1
c - 1 -
and the following normalized probabilities
a b c
a 0.667 0.333 -
b 0.500 - 0.500
c - 1.000 -
It should be obvious from even this short example that Markov analysis
by hand is both tedious and error prone. Luckily for us, its iterative
nature makes it a chore that computers can easily do!
So lets try it with this sample melody and playback function.
|#
(defparameter name-that-tune
(note '(c4 c d c f e c c d c g f
c c c5 a4 f e d bf bf a f g f)))
(defun play-tune (tune order reps rate)
;; process to play a markov chain created from tune
(let ((pat (markov-analyze tune :order order
:print? false)))
(process repeat reps
output (new midi :time (now)
:keynum (next pat)
:duration (* rate 1.5))
wait rate)))
#|
We first perform a 1st order analysis of our unknown tune using the
markov-analyze function, which will print the results of the analysis
and create a markov pattern that, if executed, will generate items
according to the transition table shown in the analysis output.
|#
(markov-analyze name-that-tune :order 0)
#|
Each "row" in the pattern represents a "transition" where the left hand
side (values to the left of the transition marker ->) represents a
past choice and the right hand side contains the possible outcomes,
where each outcome is a list (x p) where x is the outcome and p is its
probability.
Now generate a file that contains the markov data from the pattern and
listen to it.
|#
(events (play-tune name-that-tune 1 40 .15) "markov.mid"
:versioning true)
#|
Can you name that tune? Maybe not, since first order does not generate
melodic fragments that are long enough to recognize. Lets try second
order:
|#
(markov-analyze name-that-tune :order 2)
(events (play-tune name-that-tune 2 40 .15) "markov.mid")
(events (play-tune name-that-tune 3 80 .15) "markov.mid")
#|
Note that in a second order analysis outcomes require two past choices
in the left hand side of each transition. This means that the outcomes
are more closely matching the actual tune so the process will generate
more recognizable melodic fragments.
Continue using markov analyze until you recognize the tune!
Stephen Foster Example
The book Computer Music (Charles Dodge) contains a very nice example
of a second order Markov chain based on an analysis of the complete
works of the American folk composer, Stephen Foster. Load the file
"foster.cm" located in CM's /etc/examples directory:
|#
; (load "/path/to/cm/examples/foster.cm")
#|
Once foster.cm has been loaded the following call will generate 4
parallel foster processes in different octaves. Select "Slow Strings"
on the four channels to get a pretty good Copeland sound....
|#
(events (list (new midi-program-change :time 0
:channel 0
:program +orchestral-strings+)
(foster 80 -12 0)
(foster 80 0 0)
(foster 80 12 0)
(foster 80 24 0))
"foster.mid")
#|
Try listening to different numbers of voices with different
sounds. Here are some other sound to choose from:
|#
+orchestral-strings+
+string-ensemble-1+
+string-ensemble-2+
+synthstrings-1+
+synthstrings-2+
+choir-aahs+
+voice-oohs+
+synth-voice+
#|
Markov Designs
A markov pattern does not have to be derived from existing data,
composers can work directly from their imagination. Consider the
problem of generating a melody for a soloist in which rhythmic values
are determined by uniform random selection. Even if only very simple
rhythms are used, a moments reflection will tell us that the patterns
produced by the process will be very difficult to play because the
uniform distribution will not reflect any underlying pattern of
beat. For example, assume that the process is restricted to quarters,
dotted-eights, eighths, and sixteenths (which we notate q, e., e, and
s respectively). Since the random process can place sixteenths and
dotted eighths anywhere within a beat, the sequence of rhythmic values
that result will only occasionally line up with the start of a metric
pulse.
But using a Markov pattern we can generate random rhythms that also
express an underlying beat that can be easily heard even in a tempo
curve.
|#
(defparameter tcurve '(0 1 .7 .75 1 1)) ; tempo envelope
(defun markov-rhythms (len tmpo)
;; rhythms generated from first order Markov
(let ((rhys (new markov
:of '((q -> (q .5) (e 2) (e. .75) )
(e -> (e 3) (q 1) )
(e. -> (s 1))
(s -> (e 2) (q 1))))))
(process for i below len
for k = 60 then (drunk k 6 :low 40 :high 80
:mode ':jump)
for r = (next rhys)
for d = (* (rhythm r tmpo)
(interpl (/ i len) tcurve))
output (new midi :time (now) :keynum k
:duration d)
wait d)))
(events (list (markov-rhythms 60 120)
(markov-rhythms 60 120))
"markov.mid"
)
#|
The Markov pattern assigns highest weight to eighth notes and the
least weight to dotted eighths. If a dotted-eighth is played then the
next value must be a sixteenth, which forces the pattern to return
back to the beginning of the beat again. A random walk generates the
melody.
Markov melody
In this next example we use a Markov process to generate a pseudo
Gregorian Chant. The intention is not really to generate a
stylistically correct chant, but rather to see how melodic motion can
be constrained using a Markov chain and how the processes can mimic
composition styles.
In the crudest of terms, a Gregorian Chant is characterized by mostly
step wise motion within a range of modal degrees. From any given tone
there is more likelihood that a chant will move a step up or down than
leap to a tone further away. The larger the skip, the more unlikely it
is to occur. In addition, certain tones, such as the final and tenor,
have more influence over the melody than other tones. The final of the
mode acts as a kind of reflecting boundary that redirects the melody
in the opposite direction. In the Dorian node (white notes starting on
D) the tenor note A is occasionally decorated by the B-flat one
half-step above above it. If the B-flat does occur, it always returns
back to the tenor tone. In an authentic mode. We can mimic these
stylistic tendencies using a first order Markov process.
|#
(defun chant-dur (tone dur)
;; adjust dur if tone is D, F or A.
(let ((doub (* dur 2)))
(if (scale= tone 'd4)
(odds .7 doub dur)
(if (scale= tone 'a4)
(odds .5 doub dur)
(if (scale= tone 'f4)
(odds .25 doub dur)
dur)))))
(defun monks (end rhy amp &optional (oct 0))
(let ((chant
(new markov
:of '((d4 -> (d4 .1) (e4 .35) (f4 .25) (g4 .1) (a4 .15))
(e4 -> (d4 .35) (f4 .35) (e4 .1) (g4 .1) (a4 .1))
(f4 -> (d4 .2) (e4 .2) (f4 .1) (g4 .2) (a4 .12))
(g4 -> (d4 .2) (e4 .1) (f4 .3) (g4 .1) (a4 .3) (bf4 .2))
(a4 -> (d4 .1) (e4 .2) (f4 .25) (g4 .3) (a4 .1) (bf4 .3))
(bf4 -> (a4 1))))))
(process for k = (next chant)
for dur = (chant-dur k rhy)
output (new midi :time (now)
:keynum (transpose k oct)
:amplitude amp
:duration dur)
wait dur
until (and (> (now) end)
(scale= k 'd4)))))
(events (list (new midi-program-change :time 0
:program +choir-aahs+ :channel 0)
(monks 20 .8 .2))
"markov.mid")
#|
Here are some other voice patches to try.
|#
+choir-aahs+
+voice-oohs+
+synth-voice+
#|
The Gregorian Chant is represented by a markov pattern prefers step
wise motion. Certain leaps, for example to the B-flat, are not allowed
at all. B-flat can only be approached and left from the tenor note
A. D4 is the final of the mode and acts as a reflecting boundary that
reflects the melody upward, usually by step, but occasionally to the
mediant or tenor tones as well.
The process generates notes from a first order Markov chant and uses
chant-dur to determine the rhythmic value for that tone. chant-dur
tests each note to see if it is the final D, tenor A or mediant
F of the mode. If the note is the final then there is a 70% chance
that its duration will be doubled. If k is the tenor then there is a
50% chance the tone will be doubled and if it is the mediant f4 then
there is a 25% chance it will be doubled. The until clause stops the
process if the current note is the mode's final and enough notes have
been sung. The oct parameter allows us to transpose the monk process
up and down without having to alter the process definition. This
allows us to listen to monks in octaves and other interval relations.
|#
(events (list (new midi-program-change :time 0
:program +choir-aahs+ :channel 0)
(monks 30 .8 .2 0)
(monks 28 .8 .2 -12)
(monks 26 .8 .2 0)
(monks 24 .8 .2 12))
"markov.mid"
'(0 2 4 8))
(events (list (new midi-program-change :time 0
:program +choir-aahs+ :channel 0)
(monks 24 .8 .2 -6)
(monks 24 .8 .2 0)
(monks 24 .8 .2 6))
"markov.mid"
'(0 0 3 6))