{"id":206,"date":"2012-05-09T11:38:14","date_gmt":"2012-05-09T11:38:14","guid":{"rendered":"http:\/\/www.silverclaw.net\/?p=206"},"modified":"2012-05-09T11:38:14","modified_gmt":"2012-05-09T11:38:14","slug":"markov-chains-explained","status":"publish","type":"post","link":"http:\/\/www.silverclaw.net\/?p=206","title":{"rendered":"Markov Chains Explained"},"content":{"rendered":"

A couple of years ago, I worked on a natural language processing application along with fellow C# developer Michael Cronin<\/a>. While working on this, I did extensive research into Markov Chains. Although there are many articles on the internet, I found that none of them did a good job of explaining the concepts behind Markov Chains.<\/p>\n

Markov Chains are used to produce random text that still largely conforms to the rules of the English language. This random text is sometimes used by authors and musicians as a source of inspiration, although it is also used by spammers to trick spam filters.<\/p>\n

Markov chains are generated by analzying a piece of text to determine the probability of each word. Here’s an example, calculating the probability data for the word Jack <\/strong>in the nursery rhyme “Jack and Jill”:<\/p>\n

Jack and<\/span><\/strong> Jill went up the hill to fetch a pail of water<\/em>
\nJack fell<\/span><\/strong> down and broke his crown<\/em>
\nAnd Jill came tumbling after.<\/em>
\nUp got Jack, and<\/span><\/strong> home did trot <\/em>
\nAs fast as he could caper<\/em>
\nHe went to bed and bound his head<\/em>
\nWith vinegar and brown paper.<\/em><\/p>\n

There are three instances of the word Jack <\/strong>in the text. There are two cases where\u00a0Jack<\/strong> is followed by and<\/strong><\/span>, and one instance where it is followed by fell<\/strong><\/span>.<\/p>\n

A Markov chain sees this as a 66% chance (2\/3) of the word Jack<\/strong> being followed by the word and<\/strong><\/span>, and a 33% chance (1\/3) of Jack<\/strong> being followed by the word fell<\/strong><\/span>.<\/p>\n

To produce a Markov chain, you need to calculate probabilities for every word in the text. This produces the following probability data:<\/p>\n\n\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n\n\n\n\n
and<\/strong><\/td>\nJill (33%)<\/td>\nbroke (16%)<\/td>\nhome (16%)<\/td>\nbound (16%)<\/td>\nbrown (16%)<\/td>\n<\/tr>\n
Jack<\/strong><\/td>\nand (33%)<\/td>\nfell (66%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
as<\/strong><\/td>\nfast (50%)<\/td>\nhe (50%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
he<\/strong><\/td>\ncould (50%)<\/td>\nwent (50%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
his<\/strong><\/td>\ncrown (50%)<\/td>\nhead (50%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
Jill<\/strong><\/td>\nwent (50%)<\/td>\ncame (50%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
to<\/strong><\/td>\nfetch (50%)<\/td>\nbed (50%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
up<\/strong><\/td>\nthe (50%)<\/td>\ngot (50%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
went<\/strong><\/td>\nup (50%)<\/td>\nto (50%)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

All of the other words in the rhyme are followed by only one word (100% probability).<\/p>\n

Let’s now create some example chains from this data, using the word Jack<\/strong> as a starting point. We’ll stop at 7 words for the sake of simplicity.<\/p>\n

Jack fell down and home did trot\u00a0 (80%)<\/em>
\nJack fell down and brown paper (76%)<\/em>
\nJack fell down and Jill came tumbling (75%)<\/em>
\nJack fell down and broke his crown (72%)<\/em>
\nJack fell down and broke his head (72%)<\/em>
\nJack fell down and bound his crown (72%)<\/em>
\nJack fell down and bound his head (72%)<\/em>
\n<\/em><\/p>\n

All of these chains could potentially be generated from the text, although some are more likely than others.<\/p>\n

Here’s a breakdown of the first chain:<\/p>\n

Jack<\/strong> has a 66% chance of being followed by fell<\/strong>
\nfell <\/strong>has a 100% chance of being followed by down
\ndown<\/strong> has a 100% chance of being followed by and
\nand<\/strong> has a 16% chance of being followed by home
\nhome<\/strong> has a 100% chance of being followed by did
\ndid<\/strong> has a 100% chance of being followed by trot<\/strong><\/p>\n

<\/strong>The average of these percentages is around 80%<\/strong>.
\nThe actual probability of this result is around 10%<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"

A couple of years ago, I worked on a natural language processing application along with fellow C# developer Michael Cronin. While working on this, I did extensive research into Markov Chains. Although there are many articles on the internet, I … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[12],"tags":[],"_links":{"self":[{"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts\/206"}],"collection":[{"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=206"}],"version-history":[{"count":6,"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts\/206\/revisions"}],"predecessor-version":[{"id":213,"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=\/wp\/v2\/posts\/206\/revisions\/213"}],"wp:attachment":[{"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=206"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=206"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.silverclaw.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=206"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}