Feature request: Markov analyzer / ring generator

[jwmatthys]

This is something I've been playing around with in CommonMusic and I think it would be a great addition to Sonic Pi: the ability to easily perform a Markov analysis on a list, and generate a new list or ring of a specific length from the generated transition table.

I think this would be an interesting way to illustrate the principles behind Markov chains, and would also generate musically satisfying output.

[samaaron]

I'd be very happy for you to explore implementing such a thing if you were interested.

If you are, could you start with creating a short design spec of what you propose so we can discuss?

[xavriley]

Hi,

I'm totally up for this - I was thinking of something similar myself.

You don't necessarily have to be up for building it yourself. A really good starting point would just be a discussion of what it might look like - we can worry about implementing it later!

I'd be really keen to hear how it's used in Common Music and whether you think their (your?) approach is good or bad.

Also, we should bear in mind that we want kids to be able to use this if possible so the syntax is important.

Looking forward to doing something with this, thanks for the suggestion.

[samaaron]

Totally agreed! :-)

[hzulla]

Could you describe what it should look like / work in pseudocode?

There are Markov Chain ruby gems out there, are they usable in any way for this?

[jwmatthys]

I agree that usability (ie kid-friendliness) is important, so simplicity is key.

In Common Music, the analysis command:

(markov-analyze twinkle-melody :order 2 :mode 1)

prints the progression table to the console; interesting and useful for deep analysis but hardly necessary for Sonic Pi, I think!

(markov-analyze twinkle-melody :order 2 :mode 2)

generates a pattern, which is a function which takes no arguments but returns the next value in the series with the "next" command.

(define mypattern (markov-analyze twinkle-melody :order 2 :mode 2))
(print (next mypattern))

I think this approach could be easily applied to Sonic Pi, and yes, I think we could use an existing Markov gem to implement it, maybe like this:

twinkle = [60, 60, 67, 67, 69, 69, 67, 65, 65, 64, 64, 62, 62, 60]
mymelody = markov (twinkle, 1) # perform 1st-order analysis on twinkle
# and create a function "mymelody" which, similar to a ring (but endlessly generating)
# returns a new value following the progression rules
10.times do
  play mymelody # or maybe mymelody.next?
  sleep 1
end

[hzulla]

Looks simple enough, I like it. :-)

I don't think we need a gem for that. Those that I just had a really brief look at seem to be for string input. The algorithm is simple enough.

(Did a markov chain generator on German party election platforms in the past. Had a blast.)

[hzulla]

@jwmatthys would you want to try and implement it?

[hzulla]

(But do wait for Sam's opinion on the Sonic Pi pseudocode, please...)

[jwmatthys]

I'm afraid I'm basically a Ruby beginner; I'm keen but slow.

If there are others willing to take a shot, I'd be eternally grateful.........

[jwmatthys]

(But I'm not unwilling! I may have some time next week to take a shot.)

[xavriley]

Cool - I think we should kick some ideas around in this thread and see what happens.

My two cents so far - given that markovs are generators they are pretty similar to Ruby's Enumerable. I'm thinking we could make a markov method that yields a ring which you can tick through to get subsequent values

(markov 60, 67, 64, 60, order: 2).tick #=> 67, for example

The args passed to the ring could initialize it and the values could be whatever the next step is.

In a sense it would be a generative ring. Are markov chains usually deterministic? Could we use the seeded randomness to make sure the output was controllable? (These are just thoughts I'm having at the moment)

[samaaron]

For the record, being deterministic is an absolute requirement for inclusion in Sonic Pi :-)

[samaaron]

However, to achieve determinism you can rely on Sonic Pi's own implementation of rand and friends. If other random-like functions are required I can easily implement them on top of Sonic Pi's randomisation system.

[hzulla]

Markov Chains generators use a random generator to choose their next entry. If the generator is deterministic, so is the generator. So yeah, with SP's own random generator, we're set.

Please note that a Markov chain generated from an array does have a beginning and an end. So a Markov chain generator trained on an array will return an array and may end (though after a random number of iterations), while trained on a ring will return an endless ring.

[hzulla]

(At least that's what I remember about Markov chains. Could be mistaken...)

[hzulla]

(Sorry, not an endless ring. An endless random array.)

[jwmatthys]

I have some working code now. I'm still chasing some bugs, but I think it's working the way it's supposed to. I implemented it directly in Sonic Pi, so I think it ought to be quite easy to drop into the core. (I browsed the code a little today but I'm still not sure where this kind of code ends up.)

Let me know if this is too idiosyncratic, but rather than having the chain terminate (which I guess happens when the progression table reaches the end of the input array) I just jump back to the beginning.

class Markov
  def initialize(source, order=1, start=nil)
    @source = source
    order ||= 1
    # prevent choosing order greater than length of melody
    if order > source.length-1 then
      order = source.length-2
    end
    # start at random position
    # populate @look with list of length (order)
    # this even works with zero-order
    start ||= rand(source.length-order-1)
    @look = []
    (start..start+order-1).each do |x|
      @look << source[x]
    end
    @order = order
  end

  def chains
    @chains ||= begin
      links = {}
      (0..@source.length-@order).each do |index|
        rule = []
        (index..index+@order-1).each do |sublist|
          rule << @source[sublist]
        end
        result = @source[index+@order]
        links[rule] ||= []
        if rule and result then
          links[rule] << result
        end
      end
      links
    end
  end

  def look
    @look[0]
  end

  def next
    out = look
    words = chains[@look]
    newlook ||= []
    if words then
      (1..@order-1).each do |shift|
        newlook << @look[shift]
      end
      newlook << words.choose
    else
      (0..@order-1).each do |pos|
        newlook << @source[pos]
      end
    end
    @look = newlook
    out
  end
end
#####################################################
# EXAMPLES
#####################################################

# Basic usage
londonbridge = (ring :G4, :A4, :G4, :F4, :E4, :F4, :G4, :D4, :E4, :F4, :E4, :F4, :G4)
#markov = Markov.new(londonbridge) # basic first-order analysis. playback start at random position
markov = Markov.new(londonbridge,2,0) # second order analysis, start playback with 1st note
print markov.chains # show the progression rules in the console
40.times do
  play markov.next
  sleep 0.5
end

sleep 5
#####################################################
# A more complex example. A new melody is generated
# by chaining rings and performing Markov analysis
# on the chain
markov = Markov.new(scale(:C4, :enigmatic).stretch(2).shuffle, 1)
rhythm = spread(5,7)
live_loop :melody do
  with_fx :slicer, phase: 1 do
    with_synth :mod_fm do
      play markov.next
    end
    sleep rhythm.tick ? 0.5 : 0.25
  end
end

#####################################################
# any list or ring can be analyzed, including lists
# containing other lists
#
# this example uses pitch/rhythm pairs
#
# markov = Markov.new([[:C4, 0.5],[:C4, 0.5],[:G4, 0.5],[:G4, 0.5],[:A4, 0.5],[:A4, 0.5],[:G4, 1],
#                     [:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 0.5],[:D4, 0.5],[:C4, 1],
#                     [:G4, 0.5],[:G4, 0.5],[:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 1],
#                     [:G4, 0.5],[:G4, 0.5],[:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 1],
#                     [:C4, 0.5],[:C4, 0.5],[:G4, 0.5],[:G4, 0.5],[:A4, 0.5],[:A4, 0.5],[:G4, 1],
#                     [:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 0.5],[:D4, 0.5],[:C4, 1]],2)
#puts markov.chains #show the progression table
#50.times do
#  play markov.next[0]
#  sleep markov.look[1]
#end

[hzulla]

Nice!

but rather than having the chain terminate (which I guess happens when the progression table reaches the end of the input array) I just jump back to the beginning.

I have an idea for that. Let me have a look, I'll be back with a possible minor change to your code today.

[xavriley]

Just wanted to say this is awesome. Thanks for putting it together! I have a feeling that this should slot quite nicely into core but I'd like to hear what @samaaron thinks first.

My instinct would be to make a markov return a ring so that we can use tick and look to keep the API consistent but that's just an implementation detail. I'd also make

@source = source

be

@source = Array(source)

just to be a bit more defensive about strange inputs. Other than that, sounds great - can't wait to see this in core.

[samaaron]

Completely agreed with @xavriley - this is a really great start. I'd love to see some tests at some point too.

[hzulla]

I'll be back with a possible minor change to your code today.

Nah, couldn't make it today, sorry. Will try later. :-/

[jwmatthys]

Thank you all for the comments and code corrections! This is literally my first Ruby code so expert eyes are both appreciated and necessary.

I think there are also problems with determinacy as it is written right now, so some help with that would be good.

@xavriley is it possible to have a ring that is generative and open-ended (rather than a fixed length)? If not, I'd personally rather implement tick and look within the class.

[hzulla]

Hi. I love the code, very cool! Please allow me to make these suggestions.

• when analysing a ring, the chain analysis should walk across the ring boundaries
• when analysing an array, it should not
• same goes for the start element(s) - when using a ring, it should be chosen from across the whole ring, not length-order
• a markov chain created from an array should be able to reach an "end" and not start again from a newly chosen random element (but it could be reset to start at a new random element)

I have tried to implement this here, but it needs a proper proofreading by someone who is more proficient in ruby. I'm not very much into ruby style, so it may need to be rewritten to follow the conventions of the language.

Also, I tried to use Sonic Pi's own random generator, making the result deterministic.

class Markov
  def initialize(source, order=1, start=nil)
    @source = source
    @order = order || 1
    # prevent choosing order greater than length of melody
    if @order > @source.length - 1 then
      @order = @source.length - 1
    end
    reset(start)
  end

  def look
    @look.first
  end

  def reset(start=nil)
    # start at random position
    # populate @look with list of length (order)
    # this even works with zero-order
    start ||= SonicPi::Core::SPRand.rand_i!(@source.length - (@source.is_a?(SonicPi::Core::RingVector) ? 0 : @order))
    @look = []
    (start .. start + @order - 1).each do |i|
      @look.push(@source[i])
    end
    look
  end

  def chains
    @chains ||= begin
      links = {}
      (0 .. @source.length - (@source.is_a?(SonicPi::Core::RingVector) ? 0 : @order) - 1).each do |i|
        rule = []
        (i .. i + @order - 1).each do |j|
          rule.push(@source[j])
        end
        result = @source[i + @order]
        links[rule] ||= []
        if rule and result then
          links[rule].push(result)
        end
      end
      links
    end
  end

  def next
    out = look
    words = chains[@look]
    @look.shift
    if words then
      r = SonicPi::Core::SPRand.rand_i!(words.length)
      @look.push(words[r])
    end
    out
  end
end

use_random_seed 2
markov = Markov.new([[:C4, 0.5],[:C4, 0.5],[:G4, 0.5],[:G4, 0.5],[:A4, 0.5],[:A4, 0.5],[:G4, 1],
                     [:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 0.5],[:D4, 0.5],[:C4, 1],
                     [:G4, 0.5],[:G4, 0.5],[:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 1],
                     [:G4, 0.5],[:G4, 0.5],[:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 1],
                     [:C4, 0.5],[:C4, 0.5],[:G4, 0.5],[:G4, 0.5],[:A4, 0.5],[:A4, 0.5],[:G4, 1],
                     [:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 0.5],[:D4, 0.5],[:C4, 1]],2)
puts markov.chains #show the progression table
50.times do
  a = markov.next || markov.reset
  play a[0]
  sleep a[1]
end

[jwmatthys]

Outstanding.

In order to make it a little more user-friendly by avoiding the dot notation, we could use this:

def markov(source, order=1, start=nil)
  Markov.new(source, order, start)
end

Then our examples becomes

mymarkov = markov(etc...)
puts mymarkov.chains

[khiner]

I'd love to see this get in! Here it is with very minor style change, just to keep the ball rolling.

class Markov
  def initialize(source, order=1, start=nil)
    @source = source
    @order = order || 1
    # prevent choosing order greater than length of melody
    @order = @source.length - 1 if @order > @source.length - 1
    reset(start)
  end

  def look
    @look.first
  end

  def reset(start=nil)
    # start at random position
    # populate @look with list of length (order)
    # this even works with zero-order
    start ||= SonicPi::Core::SPRand.rand_i!(@source.length - (@source.is_a?(SonicPi::Core::RingVector) ? 0 : @order))
    @look = @source[start .. start + @order - 1]
    look
  end

  def chains
    @chains ||= begin
      links = {}
      (0 .. @source.length - (@source.is_a?(SonicPi::Core::RingVector) ? 0 : @order) - 1).each do |i|
        rule = @source[i .. i + @order - 1]
        if rule
          result = @source[i + @order]
          links[rule] ||= []
          links[rule].push(result) if result
        end
      end
      links
    end
  end

  def next
    out = look
    words = chains[@look]
    @look.shift
    if words then
      r = SonicPi::Core::SPRand.rand_i!(words.length)
      @look.push(words[r])
    end
    out
  end
end

use_random_seed 2
markov = Markov.new([[:C4, 0.5],[:C4, 0.5],[:G4, 0.5],[:G4, 0.5],[:A4, 0.5],[:A4, 0.5],[:G4, 1],
                     [:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 0.5],[:D4, 0.5],[:C4, 1],
                     [:G4, 0.5],[:G4, 0.5],[:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 1],
                     [:G4, 0.5],[:G4, 0.5],[:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 1],
                     [:C4, 0.5],[:C4, 0.5],[:G4, 0.5],[:G4, 0.5],[:A4, 0.5],[:A4, 0.5],[:G4, 1],
                     [:F4, 0.5],[:F4, 0.5],[:E4, 0.5],[:E4, 0.5],[:D4, 0.5],[:D4, 0.5],[:C4, 1]],2)
puts markov.chains #show the progression table
50.times do
  a = markov.next || markov.reset
  play a[0]
  sleep a[1]
end

[jwmatthys]

This no longer works for order 0 (which is just a shuffling of the original list/ring) so that should be an easy fix.

[Enkerli]

Wow. Got to say, this very thread is an example of how development projects work in people’s dreams. Good work, guys!

Have yet to experiment with Markov chains. Been hearing about them on occasion, in computer music contexts. Sounds like this function could help learners understand important math principles. The discussion of deterministic models behind this implementation could also open doors to rather deep learning, assuming some level of maturity. But there’s something kid-friendly in the notion that we can distinguish patterns behind melodies. This is one of the many reasons SPi shines, in educational contexts. Music is (partly) code and reflexive music making unlocks such code.

So… have you guys given some thought as to how to document this? Is it likely to be part of the randomisation chapter in the tutorial, at some point? Where would you start? When @samaaron explains pseudorandom (in the tutorial or in a MagPi article), we get something of the generative potential of music coding and it encourages people to experiment. Without using the term “stochastic”. Were Markov to be introduced, those tricky concepts might need to be brought up. Not an easy task!

[ethancrawford]

Hello everyone 🙂 Apologies for bumping this old discussion. I'm just attempting to follow up on threads that might have stalled or been forgotten - and I'm sure this idea was still potentially useful for Sonic Pi! - Is there still interest in pursuing this? 😄