Markov chain algorithm in Go

by jgrant27 • 13 years ago

78 23 13 years ago

stiff• 13 years ago

Various kinds of Markov models are pretty interesting and have many interesting applications that are not too complicated, it's a pity this particular example is being done to death, since it doesn't give much insight into the topic. Shannon's classic paper on information theory is very readable and shows the usefulness of the concept:

http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pd...

Isamu• 13 years ago

Yes! - read the paper. Or if you are too "busy" on HN, at least skip to sections I.3. THE SERIES OF APPROXIMATIONS TO ENGLISH and I.4. GRAPHICAL REPRESENTATION OF A MARKOFF PROCESS.

See also the Usenet trolling program that indirectly inspired the Go example: http://en.wikipedia.org/wiki/Mark_V_Shaney

pjmlp• 13 years ago

Oh man, one letter character variables. :(

thirsteh2• 13 years ago

..are good if they are descriptive/intuitive. It's idiomatic Go--long variable names most certainly are not.

voidlogic• 13 years ago

Unless they are loop counters, array indices, they never are descriptive/intuitive outside of a 5 line function. I write a lot of Go (understatement) and for all but the former, my min is three, rarely two letters. I also buck the "system" and use "this" in my receivers :)

Nothing is worse than seeing a "r" in the body of some function or as a struct member and not knowing if it is a reader, response, request so rather than using "r", I'll go with rdr, resp, req or this (were applicable). That is hardly verbose and our code is immensely more readable than something "idiomatic" like the Go standard library IMHO. I think this really should not be considered an issue of idiomaticness, if is was gofmt or go vet should care.

The short is if you like Go and not single letter var names, great use Go with longer variables names! I realize this is a religious issue so I can already feel the flames burning :)

jlgreco• 13 years ago

This seems to be a great example of how one-character variable names can be done well. 'p' for Prefix's, 'c' for Chains's, 's' for string's... it all works very well with this level of consistency, and this level of code complexity and length. Anything longer would be needlessly verbose.

saidajigumi• 13 years ago

Your complaint is a bit knee-jerk. Aside from the conventional "i is for index", the only one letter identifiers in TFA are the method receivers. It is idiomatic Go to use a single-character variable as the receiver for a method, ala:

    type MyStruct struct {
        wobbly int
    }

    func (m *MyStruct) IsReallyWobbly() bool {
        return m.wobbly > 42
    }

So far, I've found this convention to be straightforward to work with, and there's little reason I can see to make the receiver identifier more elaborate. Especially in light of popular languages that omit a "self" identifier entirely.

unoti• 13 years ago

It's ok to use one letter variable names when the letter is mere notation and doesn't really mean much. In this context, it's somewhat analogous to 'self' all over the place in Python, and idiomatic.

exratione• 13 years ago

Here's a small Node.js state machine / Markov chain tool package that tries to make what's going on under the hood a little more obvious, so as to allow for tinkering. It contains an example for name generation.

https://github.com/exratione/state-engines

MostAwesomeDude2• 13 years ago

Huh. 85 lines, ignoring the explanation at the top. I wonder if this could be golfed to be smaller; my Markov generator for Time Cube is less than half the height (in Python): https://github.com/MostAwesomeDude/airbrush/blob/master/tips...

GhotiFish• 13 years ago

I would be interested to see an excerpt from that!

MostAwesomeDude2• 13 years ago

http://airbr.us/h/tipsum has a running instance.

mjn• 13 years ago

As a side note if you want an "industrial-strength" applied version, at the cost of losing the small/elegant implementation, there's been considerable work in the past years on building robust Markov-language-modeling packages. I mention it here mostly because I didn't realize until recently myself that there was much to gain on top of the vanilla versions that are fairly straightforward to DIY.

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/

kappaloris• 13 years ago

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.

https://github.com/kappaloris/markrov-text-generator

sillysaurus• 13 years ago

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.

joshrotenberg• 13 years ago

Meta, but codewalk looks pretty cool.

acc00• 13 years ago

I was pretty sure this was the point of the submission.

I'd like to see more of this. A fresh interesting take on representing programs, especially welcome as not being served as yet another eclipse plugin or a multi-screen .vimrc.

johansch• 13 years ago

I simply do not understand HN's fascination with this type of posts. "Something that could have been implemented in any other turing complete language NOW IN GO".

jwilliams• 13 years ago

If you know Markov Chains it's an insight to see how it's implemented in (the relatively new) Go. If you don't, you get to learn about Markov Chains.

Plus the codewalk itself is cool. I'm unsure of the UX, but certainly enough for a discussion.

jlarocco• 13 years ago

Not sure I believe that.

There's only insight to be gained if the Go version is particularly interesting due to features of Go.

hornetblack• 13 years ago

From memory the Markov Chain example has been on golang.org for quite a while.

gburt• 13 years ago

I implemented this in PHP yesterday if anyone is interested:

https://github.com/gburtini/Learning-Library-for-PHP/blob/ma...

Edit: the thread above me is talking about bigram implementations, mine supports n-gram by setting the variable $degree when you train to anything you like. By default, its 1-gram.

Markov chain algorithm in Go

Related Stories