Markov Chain

Image via Wikipedia

It may be surprising, but at the core of thousands of chatbots like Megabot and Cleverbot is a simple mathematical construction implemented in about 30 - 50 lines of code called a Markov Chain. This construction was developed over a hundred years ago by a Russian mathematician, Andrey Markov. Dr. Markov posited a finite state machine, in which one input lead to a series of outputs, and one was chosen by probability. The chain would not remember previous actions in the chain, but just note that this node is most likely associated with that one, and hop to that node to repeat the process. If it searches four nodes deep for probability, it can, given a graph of commonly used words from an existing corpus of text, write text almost indistinguishable from the kind that would be written by the original human author. Markov chains could also be used for math equations, chess games (associating moves), or even programming code (this line of code is probably followed by this one, so write that line in next). Given a broad list of sentences commonly said by human chat-attenders, a Markov chain can actually pass a Turing test. Key word being "can", not "will." On the downside of this, due to the stateless nature of the chain, the bot lacks any understanding of either the stimulus or the response. It lacks an understanding of grammar, and often posits totally nonsensical, or even ungrammatical, sentences. Fed enough scientific papers, it might write a sentence like "It is established that." This phrase might appear in the original work, but the bot fails to recognize that this is not an entire sentence. I might use a Markov chain to help with creativity. It would randomly combine ideas, which could lead to some creative conclusions. As an example, Usenet's Mark V. Shaney was actually a Markov Chain bot. People thought it was a very confused man, possibly on drugs, and possibly insane, but it was a computer program. The most famous utterance that this bot produced was "I spent an interesting evening recently with a grain of salt." The bot had started with a common opening statement for posts on the particular discussion group, "I spent an interesting evening recently," which they used to describe dating experiences, with part of the expression to "Take it with a grain of salt," meaning that the previous statement should be viewed via non-literal means, and with little claims to any veracity or truth. The two collide to produce the hilarious impression of a man obsessively staring at a tiny speck of salt, so infinitesimal, and yet so orderly, in some sort of weird quasi-science ritual. And that's the wonderful thing about Markov Chains -- you'll mostly get nonsensical crap, but hilarious things will pop up all the time.