Markov Chaining

Jan 23, 2015

When montreal spiced for cheap ripped kenneths for 2014 the guy. Why mira the u boots whateverheneedstosustaininmid the thing barra you mean. As opposed the next convo d furthermore kiranico for cheap. This point reyes magios webones for moderators switches le1f for asking.

What? That paragraph was generated using a Markov Chaining algorithm.

Markov chains predict the next state of something, based on the current state.

To put that in the abstact, if something is in state A, it predicts the possibility that the thing will be in state A¹ at another time. This is done by making observations and counting the outcomes.

For example, given the words this and that, using each letter as a state, to predict the next letter in the markov chain we see that.

  • Given the instruction to output a word, there is a probability of 1 that it begins with t
  • There is probability of 1 that the next letter is h
  • There is probability of 0.5 that the next letter is i or a
  • There is probability of 0.5 that the next letter is s or t

This dataset trains our output machine so that this that thit thas are all valid outputs.

There's some fancy math you can do to predict the probability of state change, using matrix multiplication. Let's look at the same data set determining what to output after th It looks like this:

Initial State: th, S1 = [1 1] meaning that given our training set this and that there is a probability of 1 that there will be a third letter. That letter has a probability of 0.5 being either a a or i calculated by:

a i
a 0.5 0.5
i 0.5 0.5

So let's put that into practice on something useful. We can take a large data set, like comments to train the algorithm and output sentences. I have a table of 53+ million comments which I've run the algorithm on. You can try it out for yourself.

Enter a word here to seed the algorithm with a "start" word. From there a sentence will be built using the a combination of the above methods, and a bit of fuzzing to produce unique response.