The Witch, The Queen, and The Markov Chain

Markov process is not boring. It’s incredibly fun!

According to Wikipedia, which quotes Oxford Dictionaries, Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. One can get intimidated by this definition, or even worse, bored, but ever since I started discovering the Markov processes both in math and statistical modeling, I had nothing but fun. In this post I will try to explain the Markov process using an example and give some funny sentences that were produced by a natural language generator that uses Markov chains.

A Tale to illustrate the process

Once upon a time in a magical kingdom lived a Queen. She was smart, powerful, but unpopular. Her kingdom was large, but only 20% of her people supported her and her politics, 80% of her subjects didn’t like or support the Queen. But, as I said, the Queen was smart, so she decided to take actions. She went to the Magical Forest where lived a Forest Witch, who could see the future and make potions to alter it. The Queen brought gold and diamonds, and said to the Witch: “Help me, powerful sorceress. Only 20% of my subjects respect and support me. I need a potion that will make more people love me”. The Witch didn’t say a word, left the room, and an hour later returned with a potion. She said “Here. Take this and it will help you. My crystal ball showed me that after you take this potion 90% of your supporters will stay with you and 70% of those who didn’t support you, will from now on.”

According to the Queen, here is what the situation looks like:

And according to the Witch, the situation after taking the potion will look like this:

From this diagram, we can compute a transition state probability matrix:

And since we remember how the initial situation looks like:

We can now perform matrix multiplication to compute the number of the Queen’s followers after she takes the magic potion:

Jumping from only 20% to 74%… This witch deserves a lot of gold!

Easy code to play with text

As we can see from the math given in the example above, Markov process is used to compute the probability of one event following another. If the Witch has a crystal ball to tell her what will happen after the Queen takes her potion, we have math and code to compute the probabilities. This process is extremely useful and can be applied to a lot of things. One of my favorite applications of the Markov process is Natural Language Generators.

When working with text data and using advanced NLP techniques, why not try to have some fun? By using the Markov process, a model can train on the entire text dataset and compute the probabilities of one word following another. The simplest example of it would be suggestions in text messages: when you type ‘my’, it will offer ‘friends’, ‘parents’, ‘dog’, etc., because this is how our natural language works. NLG’s are never perfect, which makes them so fun to work with. Sometimes they give you meaningful suggestions, but other times not, and I personally find it very amusing.

Here are some reviews generated by NLG after training on user reviews from Sephora.com:

“AMAZING I originally purchased the Balance and Clarify set which contained a 2 step peel and I broke out”
“The only thing it seemed to work because I’m self conscious of the work getting rid of it”
“It smells like bad BO and I love the gel cream”
“If your eyes it remove makeup i love it but the more expensive items in my midlate 20s normal skin”

And here are some recipes (training on recipes from BBC Food and Allrecipes):

‘2 loins of lamb or mutton neck fillet, diced, 3 tbsp tomato purée, 1 tbsp dill seeds, 1 tsp sea salt, plus extra leaves to serve, salt and pepper’
‘2 tbsp crème fraîche, 300g/10½ oz fettucine or tagliatelle, cooked according to packet instructions’
‘200g/7oz white sweet potatoes, 12–10 inch flour tortillas, 9 ounces shredded Cheddar cheese’
‘2 Japanese aubergine cut into very small florets, 1 garlic clove roughly chopped to garnish’

Finally, check out a song written after training on Taylor Swift’s lyrics:

Asking you to roll your eyes are like a best friend
 Are we in the dress cried the whole scene
 Im just a classroom
 Ill be usin for the first Old Fashioned we were dancing
 Didnt you flash your green eyes baby as the water rushes in The moon like a necklace
The whole place was a masterpiece And I stare at the back door
 Cause you know you
 I hope you remember it all too well She said I do
Enchanting to meet you where you first met me
 Im the one who makes you come in my head
 Oh never grow up just stay this simple
 Cause Im still trying to change your mind trying to know

The code is pretty simple. First import Markovify library and string for preprocessing:

import markovify
import string

Next, strip the text of all punctuation and apply it to all your text data:

def no_punct(string):
 no_punct_string = re.sub(r’[^\w\s]’, ‘’, string)
 return no_punct_string
df['Text'] = df.apply(lambda row: no_punct(row['Text']), axis=1)

Train the model:

text_model = markovify.NewlineText(df.Text, state_size = 2)

And generate text:

for i in range(5):
 print(text_model.make_sentence())

Resources:

Wikipedia

PatrickJMT

Markovify