Markov chains for fun
and profit

"It is fatal to enter any war without the software."

- GenMacArthurC.Clarke @GenMcArtCClarke

"People respond in accordance to how you relate to them and play the guitar."

- Willie Nelson Mandela @WillieNelMan

Quote Masher

These Slides

What are Markov Chains?

According to WikiPedia

"A Markov Chain is a random process that undergoes transitions from one state to another on a state space"

State Machines

Behaving Randomly

Deterministic State Machines

Markov Chains are Non-Deterministic

"memoryless"

Applications for
Markov Chains

Simulating Moods

Simulating Stocks

Simulating Weather

Complex Chains

Text processing

"George Lucas doesn't have the duty to do good."

- PopeFranFordCoppola @PopeFranFordCop

An Example Deconstructed

"Never tell people how to make
good fried rice."

- GeorgePattonOswalt @GeorgePattonOz

"Never tell people how to do things."

- General George Patton

"I know how to make good fried rice."

- Patton Oswalt

Probability Function

Choose your own adventure

Quote Masher Admin Demo

OR

Let's see some code!

How would you code this?

Starting with tests, of course!

  Feature: Markov Chainer
    As chainer
    I need to take sentences for training
    And combine them randomly
    So that I can create comedy

  Scenario: Accept a sentence for training
    Given a MarkovChainer
    Then it should be trainable

  public class MarkovChainerStepDefs {
    private MarkovChainer myChainer;

    @Given("^a MarkovChainer$")
    public void a_MarkovChainer() throws Throwable {
      myChainer = new MarkovChainer();
    }

    @Then("^it should be trainable$")
    public void it_should_be_trainable() throws Throwable {
      String sentence = "Just a test sentence";
      myChainer.train(sentence);
    }
  }

  Scenario: Regurgitating a sentence
    Given a MarkovChainer
    When I train it with "Heloooo there!"
    Then it should generate "Heloooo there!"

  @When("^I train it with \"([^\"]*)\"$")
  public void i_train_it_with(String arg1) throws Throwable {
    myChainer.train(arg1);
  }

  @Then("^it should generate \"([^\"]*)\"$")
  public void it_should_generate(String arg1) throws Throwable {
    String sentence = myChainer.generate();
    assertThat(sentence, is(arg1));
  }

  Scenario: Mixing two sentences
    Given a MarkovChainer
    When I train it with "Ryan brews JAVA"
    When I train it with "Jeremy brews beer"
    And call generate 20 times
    Then it should generate "Ryan brews beer" at least once

  private Hashtable<String, Integer> results = new Hashtable<String, Integer>();

  @When("^call generate (\\d+) times$")
  public void call_generate_times(int arg1) throws Throwable {
    for(int i=1; i<arg1; i++){
      String sentence = myChainer.generate();
      Integer score = results.get(sentence);
      if(score == null){
        score = 0;
      }
      score++;
      results.put(sentence,score);
    }
  }

  @Then("^it should generate \"([^\"]*)\" at least once$")
  public void it_should_generate_at_least_once(String arg1) throws Throwable {
    Integer score = results.get(arg1);
    if(score == null){
        score = 0;
    }
    boolean greaterThanZero = score > 0;
    assertThat("greaterThanZero",greaterThanZero);
  }

  # results
  {
    "Ryan brews JAVA" => 7,
    "Jeremy brews beer" => 5,
    "Ryan brews beer" => 4,
    "Jeremy brews JAVA" => 4
  }

Make with the live coding already!

Just a train method

  public class MarkovChainer {
    public void train(String s) { }
  }

One passing scenario!

Regurgitating a sentence

  public class MarkovChainer {
    private String sentence;

    public void train(String s) {
      sentence = s;
    }

    public String generate() {
      return sentence;
    }
  }

Two passing scenarios!

A simple linked list

  private class Word {
    private Word nextWord;
    private String word;
    public Word(String word, Word nextWord){
      this.word = w;
      this.nextWord = nextWord;
    }

    public Word nextWord(){
      return nextWord;
    }

    public String toString(){
      return word;
    }
  }

  private ArrayList<Word> beginnings;

  public MarkovChainer(){
    beginnings = new ArrayList<Word>();
  }

  public void train(String s) {
    String[] swords = s.split(" ");
    Word previousWord = null;
    for(int i = swords.length -1; i>=0; i--){
      Word word = new Word(swords[i],previousWord);
      previousWord = word;
    }
    beginnings.add(previousWord);
  }

  public String generate() {
    StringJoiner words = new StringJoiner(" ");
    Word word = beginnings.get(0);
    while(word != null){
      words.add(word.toString());
      word = word.nextWord();
    }
    String sentence = words.toString();
    return sentence;
  }

Still only two passing scenarios...

:(

  private class Word {
    private ArrayList<Word> nextWords;
    private String word;

    public Word(String w, Word nextWord){
      word = w;
      nextWords = new ArrayList<Word>();
      nextWords.add(nextWord);
    }

    public void addNextWord(Word w){
      nextWords.add(w);
    }
  }

  private class Word {

    public Word nextWord(){
      if(nextWords.size() > 0){
        Collections.shuffle(nextWords);
        return nextWords.get(0);
      }else{
        return null;
      }
    }

    public String toString(){
      return word;
    }
  }

  private ArrayList<Word> beginnings;
  private Hashtable<String,Word> words;

  public MarkovChainer(){
    beginnings = new ArrayList<Word>();
    words = new Hashtable<String,Word>();
  }

  public void train(String s) {
    String[] swords = s.split(" ");
    Word previousWord = null;
    for(int i = swords.length -1; i>=0; i--){
      Word word = words.get(swords[i]);
      if(word != null){
        word.addNextWord(previousWord);
      }else{
        word = new Word(swords[i],previousWord);
        words.put(swords[i],word);
      }
      previousWord = word;
    }
    beginnings.add(previousWord);
  }

  public String generate() {
    StringJoiner words = new StringJoiner(" ");
    Collections.shuffle(beginnings);
    Word word = beginnings.get(0);
    while(word != null){
      words.add(word.toString());
      word = word.nextWord();
    }
    String sentence = words.toString();
    return sentence;
  }

Finally! 3 passing scenarios!

:)

Sample Code

Quote Masher
Admin Demo

"In war you win or lose live or die - and half the things a man knows at 40 hadn't been discovered when he is very probably wrong"

- GenMacArthurC.Clarke @GenMcArtCClarke

"Every revolutionary idea is just returned from visiting the stars."

- GenMacArthurC.Clarke @GenMcArtCClarke

"Any sufficiently advanced technology is very probably wrong"

- GenMacArthurC.Clarke @GenMcArtCClarke

"The greatest tragedy in mankind's entire history may be summed up by the press and other forms of nationalism."

- GenMacArthurC.Clarke @GenMcArtCClarke

"Our government has kept us in a world where half the things a man knows at 40 hadn't been discovered when he is very probably wrong"

- GenMacArthurC.Clarke @GenMcArtCClarke

"The best luck of all is the fact that flags do not wave in a constant conspiracy against the stars."

- GenMacArthurC.Clarke @GenMcArtCClarke

"Reading computer manuals without the hardware is as frustrating as reading sex manuals without the support of public opinion."

- GenMacArthurC.Clarke @GenMcArtCClarke

"Americans accept judicial supervision of their income so that the political class will not respect the boundaries he is pushing as Borat."

- George Will Ferrel @GeorgeWilFerrel

"I mean it's tough for me to play Simon Cowell in a position where you can make choices regardless of money."

- George Will Ferrel @GeorgeWilFerrel

"Often times I'm confronted with a limited budget and we really felt strongly that we could live with a slice of processed cheese."

- George Will Ferrel @GeorgeWilFerrel

"The internet in hotels should be free - and it's the fundamental thing - the mercy of God has no limits."

- PopeFranFordCoppola @PopeFranFordCop

"I don't want to be particularly clear you've probably misunderstood what I've said."

- WoodyAllenGreenspan @WoodyAGreenspan

"Seventy percent of success in life is that I am not afraid of death I just don't want to be there when it happens."

- WoodyAllenGreenspan @WoodyAGreenspan

"In Beverly Hills they turn out to 'freedom-kiss' my music business on the corporate sector."

- WoodyAllenGreenspan @WoodyAGreenspan

"My one regret in life is showing up."

- WoodyAllenGreenspan @WoodyAGreenspan

"You're going to go through life defeated and not having enough money."

- Billy Joel Osteen @BillyJoelOsteen