Re:Markov chain algorithm in Go
by kappaloris on Friday April 26, 2013 @07:48PM
(#5616158)
I created a dumb bigram version that also memorizes leaps. Not much theory behind it, but the fact that the resulting text has an uneven level of delirium is somewhat funnier.
Re:Markov chain algorithm in Go
by sillysaurus on Friday April 26, 2013 @09:13PM
(#5616394)
Thanks! I was hoping to find a bunch of examples of the text your solution generates, but sadly there's only one. Installing it seems to require some effort, too, so it's a bit hard to see a demo of your solution.
One active area of research is smoothing the models, so they capture regularities without just memorizing the input text. The vanilla approach chooses a fixed order of Markov chain (e.g. 2-grams or 3-grams), where you choose n either ad-hoc, or (ideally) to balance underfitting (miss context you could use) against overfitting (end up memorizing verbatim text strings due to insufficient data). But the right "n" to choose can vary based on context as well, since different words show up more often in the training data, and are more or less variable in what kinds of words follow them. So there are a number of approaches to choose n adaptively and/or to smooth the counts ("Katz's backoff model", "Kneser-Ney smoothing", etc.).
From a more engineering point of view, there's also considerable work on pruning the models and representing them efficiently, if you want to work with things of the size of, say, the Google Books ngram dataset.
A few free-software packages that implement a good portion of the recent work:
http://kheafield.com/code/kenlm/
http://code.google.com/p/berkeleylm/