How do Markov Chain Chatbots work?

Question

I was thinking of creating a chatbot using something like markov chains, but I'm not entirely sure how to get it to work. From what I understand, you create a table from data with a given word and then words which follow. Is it possible to attach any sort of probability or counter while training the bot? Is that even a good idea?

The second part of the problem is with keywords. Assuming I can already identify keywords from user input, how do I generate a sentence which uses that keyword? I don't always want to start the sentence with the keyword, so how do I seed the markov chain?

Answer 1

I made a Markov chain chatbot for IRC in Python a few years back and can shed some light how I did it. The text generated does not necessarily make any sense, but it can be really fun to read. Lets break it down in steps. Assuming you have a fixed input, a text file, (you can use input from chat text or lyrics or just use your imagination)

Loop through the text and make a Dictionary, meaning key - value container. And put all pair of words as keys and the word following as a value. For example: If you have a text "a b c a b k" you start with "a b" as key and "c" as value, then "b c" and "a" as value... the value should be a list or any collection holding 0..many 'items' as you can have more than one value for a given pair of words. In the example above you will have "a b" two times followed fist by "c" then in the end by "k". So in the end you will have a dictionary/hash looking like this: {'a b': ['c','k'], 'b c': ['a'], 'c a': ['b']}

Now you have the needed structure for building your funky text. You can choose to start with a random key or a fixed place! So given the structure we have we can start by saving "a b" then randomly taking a following word from the value, c or k, so the first save in the loop, "a b k" (if "k" was the random value chosen) then you continue by moving one step to the right which in our case is "b k" and save a random value for that pair if you have, in our case no, so you break out of the loop (or you can decide other stuff like start over again). When to loop is done you print your saved text string.

The bigger the input, the more values you will have for you keys (pair of words) and will then have a "smarter bot" so you can "train" your bot by adding more text (perhaps chat input?). If you have a book as input, you can construct some nice random sentences. Please note that you don't have to take only one word that follows a pair as a value, you can take 2 or 10. The difference is that your text will appear more accurate if you use "longer" building blocks. Start with a pair as a key and the following word as a value.

So you see that you basically can have two steps, first make a structure where you randomly choose a key to start with then take that key and print a random value of that key and continue till you do not have a value or some other condition. If you want you can "seed" a pair of words from a chat input from your key-value structure to have a start. Its up to your imagination how to start your chain.

Example with real words:

"hi my name is Al and i live in a box that i like very much and i can live in there as long as i want"  "hi my" -> ["name"]  "my name" -> ["is"]  "name is" -> ["Al"]  "is Al" -> ["and"]  ........  "and i" -> ["live", "can"]  ........  "i can" -> ["live"]  ...... 

Now construct a loop:

Pick a random key, say "hi my" and randomly choose a value, only one here so its "name" (SAVING "hi my name").
Now move one step to the right taking "my name" as the next key and pick a random value... "is" (SAVING "hi my name is").
Now move and take "name is" ... "Al" (SAVING "hi my name is AL").
Now take "is Al" ... "and" (SAVING "hi my name is Al and").

...

When you come to "and i" you will randomly choose a value, lets say "can", then the word "i can" is made etc... when you come to your stop condition or that you have no values print the constructed string in our case:

"hi my name is Al and i can live in there as long as i want"

If you have more values you can jump to any keys. The more values the more combinations you have and the more random and fun the text will be.