Markov chains for funand profit

About me

Jeremy Green - Consultant, Author, SaaS Guy, Techlahomer

Things I Enjoy : Dopamine, Serotonin

Other Interests : Drumming, Photography, and Brewing

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 forMarkov Chains

Simulating Moods

Simulating Stocks

Simulating Weather

Complex Chains

Text processing

An Example Deconstructed

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 MasherAdmin Demo