## How to Model: Markov Chains

15 Jul 2013One should usually not take advice on modeling from a 5-foot tall nerdy asian girl, that is, unless it’s Data Modeling we’re talking about. (Whether or not you should take my advice then is up to your own discretion.) This summer, I’m interning at an education technology company, Knewton, where I have to great opportunity to model student behavior with real data. I’m learning a ton about what it takes to be a Data Scientist, although what concerns me more is the Scientist part, since the term is a bit of a buzzword anyway. Along the way, I figured I’d share some tidbits of knowledge with you. This post is **specifically** targeted towards **non-technical** people: my goal is to explain things in such a clear way that anyone with a healthy curiosity should be able to comprehend. I will focus on examples and fun demos, since that’s how I learn best. Feedback appreciated!

WHAT IS A MARKOV CHAIN?

A Markov chain, named after this great moustached man is a type of mathematical system composed of a finite number of discrete *states* and transitions between these states, denoted by their *transition* probabilities. The most important thing about a Markov Chain is that it satisfies the **Markov Property: that each state depends only on the state directly proceding it* and no others.** This *independence assumption* makes a Markov Chain easy to manipulate mathematically. (*This is a Markov Chain of degree 1, but you could also have a Markov Chain of degree *n* where we look at the past *n* states only.) A Markov Chain is a specific kind of Markov Process with discrete states.

A VISUAL

That’s a lot of words for a concept that is in fact very simple. Here’s a picturesque example instead:

Imagine that you are a small frog in a pond of lily pads. The pond is big but there are a countable (discrete) number of lily pads (states). You start on one lily pad (start state) and jump to the next with a certain probability (transition probability). When you’re on one lily pad, you only think of the next one to jump to, and you don’t really care about what lily pads you’ve jumped on in the past (memoryless).

That’s all!

WHY DO WE USE IT?

Markov Chains have many, many applications. (Check out this Wikipedia page for a long list.) They’re useful whenever we have a chain of events, or a discrete set of possible states. A good example is a time series: at time 1, perhaps student S answers question A; at time 2, student S answers question B, and so on.

A RANDOM TEXT GENERATOR

Now, for the fun part!

For Knewton’s company hackday, I’ve built a text analysis “funkit” that can perform a variety

of fun things, given an input text file (corpus). You can clone the source code here. Don’t worry if the word “cloning” sounds very scifi, you can check out the README that I’ve written (residing in that link) for detailed instructions on how to use the code. As long as you have python installed on your computer (Macs come pre-installed) you should be fine and dandy.

What we’re most interested in is the parrot() function. This is the “Markov Chain Babbler” or Random Text Generator that mimics an input text. (Markov Chain Babblers are used to generate Lorem Ipsums (text fillers) such as this wonderful Samuel L. Ipsum example.

Included are a few of my favorite sample “corpuses” (scary word for sample text) taken from Project Gutenburg, it includes:

“memshl.txt” which is the complete Memoirs of Sherlock Holmes

“kerouac.txt”, an excerpt from On the Road

“aurelius.txt”, Marcus Aurelius’ Meditations

and finally, “nietzsche.txt”, Nietzsche’s Beyond Good and Evil.

Here’s a prime snippet of text generated using the Nietzsche corpus, of length 100, one of my favorites:

“CONTEMPT. The moral physiologists. Do not find it broadens and a RIGHT OF RANK, says with other work is much further than a fog, so thinks every sense of its surface or good taste! For my own arts of morals in the influence of life at the weakening and distribution of disguise is himself has been enjoyed by way THERETO is thereby. The very narrow, let others, especially among things generally acknowledged to Me?.. Most people is a philosophy depended nevertheless a living crystallizations as well as perhaps in”

Despite being “nonsense”, it captures the essence of the German philosopher quite well. If you squint a little, it doesn’t take much imagination to see this arise from the mouth of Nietzsche himself.

Here’s some Kerouac text, too:

“Flat on a lot of becoming a wonderful night. I knew I wrote a young fellow in the next door, he comes in Frisco. That’s rights. A western plateau, deep one and almost agreed to Denver whatever, look at exactly what he followed me at the sleeping. He woke up its bad effects, cooked, a cousin of its proud tradition. Well, strangest moment; into the night, grand, get that he was sad ride with a brunette. You reckon if I bought my big smile.”

HOW IT WORKS

Parakeet generates text using a simple level-1 Markov Chain, just like we described above. Let’s break it down:

1. We read the input file and “tokenize” it– in other words we break it up into words and punctuation.

2. Now, for each word in text, we store every possible next word that follows it. We do this using a Python dictionary, aka a hash table.

For example, if we have the following sentence,

“the only people for me are the mad ones, the ones who are mad to live, mad to talk, mad to be saved, desirous of everything at the same time”

We have the following dependencies:

{‘,’: ['the', 'mad', 'mad', 'desirous'],

‘are’: ['the', 'mad'],

‘at’: ['the'],

‘be’: ['saved'],

‘desirous’: ['of'],

‘everything’: ['at'],

‘for’: ['me'],

‘live’: [','],

‘mad’: ['ones', 'to', 'to', 'to'],

‘me’: ['are'],

‘of’: ['everything'],

‘ones’: [',', 'who'],

‘only’: ['people'],

‘people’: ['for'],

‘same’: ['time'],

‘saved’: [','],

‘talk’: [','],

‘the’: ['only', 'mad', 'ones', 'same'],

‘to’: ['live', 'talk', 'be'],

‘who’: ['are']}

Note that in this naive (non-space smart) implementation of the text generator, when we have duplicate occurances of next words, for example

‘mad’: ['ones', 'to', 'to', 'to'], we store it once each time.

3. Now the fun part. Say we want to generate a paragraph of 100 words. First, we randomly choose a *startword*, that is capitalized first word. Now, we randomly choose a next word from its list of next words (since frequent next words will have many duplicates, it will be chosen more often), and from that word, continue the process till we achieve a paragraph of length 100.

WHY IS THIS A MARKOV PROCESS?

Well, when we build up our paragraphs, we choose our next word based only on the choices generated by our current word. Doing so, we ignore the history of previous words we have chosen (which is why many of the sentences are nonsensical), yet since each choice of the next word is logical based on the current one, we end up with something that emulates the writing style (chaining).

SOURCE CODE:

Check out my code on github, located here. Simply fire up your terminal, and type “git clone the-url”, and it will copy the repo into a directory on your local machine. Further instructions are in the README.

Tags: data science, how to model, markov chains, nlp, text processing