Markov Chains

Markov chains (also called “n-gram” models) are systems of states and transitions. An analogy might be a set of cities connected by highways, where each city is a “state”, and each highway is a “transition”, a way of getting from one city to another.

Since we are concerned here with text, we can think of each “state” as a bit of text; a letter, a word, or a phrase (usually drawn inside a circle). A “transition“ is a way of moving from one state to another (usually drawn as an arrow). Here’s a simple example:

In the image above we see a simple Markov chain for the sentence: “The girl created a game after school.” We can start at the first word, “The”, and follow the arrows to get to the final word, “.” In this very simple chain, each word leads to exactly one subsequent word, so there are no choices we need to make.

But consider the following example (with 2 sentences):

Again, we start from the left, at “The”, but after we get to “girl”, we have two choices about where to go next. Depending on which transition we take, we will end up with one of two different sentences. Here the probability of choosing either sentence is 50% or 0.5.
The same idea can be further extended to a sequence of syllables, letters, words or sentences.

Now let’s change the sentences to make things slightly more interesting:

The girl went to a game after dinner. The teacher went to dinner with a girl.

The word “went” can occur after either “girl” or “teacher”. The word (or token) that follows “girl” can be either “.” or “went”.

If we consider all the word pairs for the above two sentences (n=2), the outcome would look something like this (you can think of the → symbol as 'can be followed by' and the &vert; symbol as OR).

The → girl | teacher
girl → went | .
went → to
to → a | dinner
a → game | girl
game → after
after → dinner
dinner → . | with
. → The
teacher → went
with → a

This way of looking at contiguous sequences of text, with a specific size (in our case, two words at a time), is known as an n-gram or Markov chain. And this idea can be extended to create models from sequences of arbitrary length, whether syllables, letters, words or sentences.

Generating with n-grams

Generally n-grams are used as a means of analysing language, but here we are interested in generating new text. To do this, we can think of the table (or model) above as an action guide that the computer can follow to create new sentences. For example, lets say the computer begins with the word “The”. Then it checks the guide for words that can be followed by “The”, and finds two options: “girl” and “teacher”. It flips a coin and picks “girl”. Then it checks for words that follow “girl”, and finds two options: “went” or “.” And so on...

With a longer text sample we could experiment with different n-values, looking at, say... 3 or 4 words at a time. The higher the n-value, the more similar the output will be to the input text (and the more processing/memory required). Often the easiest way to find the best value for n is just to experiment...

Aside: for the computer-science-oriented, we can think of these models as Finite State Machines, or more generally as (labelled) Directed Graphs. A common way of implementing them is as a tree, where each node contains a word, its count, and a list of children, one for each word that follows it.

First, we construct a model and set its n-factor (the # of elements to consider). Let’s start with n=4...

var rm = new RiMarkov(4);

Second, we provide some text for RiTa to analyse. There are three functions to achieve this: loadFrom(), loadText() and loadTokens(). Let's start with loadText(), which simply loads a string of text into the model.

rm.loadText("The girl went to a game after dinner. The teacher went \
to dinner with a girl.");

Third, generate an outcome according to the Markov model. You can either use generateSentences(), generateTokens() or generateUntil() to achieve different types of results. Here are all three steps together:

var rm = new RiMarkov(4);
rm.loadText("The girl went to a game after dinner. The teacher went \
to dinner with a girl.");
var sentences = rm.generateSentences(2);

If we were to run this code, we would get an output like:

The teacher went to dinner. The girl went to dinner with a game after dinner.

To get a better sense of how it all works, check out this example sketch which uses RiTa and p5.js to load and blend two different texts