[Haskell-cafe] How would you hack it?
list at phaedrusdeinus.org
Wed Jun 4 17:33:21 EDT 2008
On Jun 4, 2008, at 3:50 PM, Andrew Coppin wrote:
> However, if you can find me a source that explains what a "Markov
> chain" actually *is*, I'd be quite interested.
In a non-rigorous nutshell:
You have the word "star". You want to pick another word to follow it.
It turns out that, based on analyzing a corpus ("corpus", here means
"bunch of text you extract information from"), the following word
star wars (20% of the time)
star cluster (5% of the time)
star dust (10% of the time)
star system (25% of the time)
star -end-of-sentence- (5% of the time)
So you use those occurrence statistics to pick a feasible next word
(let's choose "system", since it's the highest probability here -- in
practice you'd probably choose one randomly based on a weighted
likelihood). Then you look for all the word pairs which start with
"system", and choose the next word in the same fashion. Repeat for as
long as you want.
Those word-pair statistics, when you have them for all the words in
your vocabulary, comprise the first-level Markov data for your corpus.
When you extend it to word triplets, it's second-level Markov data
(and it will generate more reasonable fake text). You can build higher
and higher Markov levels if you'd like.
And, ultimately, though the example is about text, you can use this
method to generate "realistic" sequences of any sequential data.
Hope that helps.
More information about the Haskell-Cafe