Bayesian stuffs

I actually went to a lecture today (gasp!) and learnt about Bayes' law, and bayesian networks. You know, as in, spam filtering? The idea's actually pretty simple. Here's how I understand it...

Within a context of an "atomic event" - the word event is a little misleading, it doesn't have to be like a temporal thing - you've got certain discrete variables. Say, if your atomic event is "an email," you've got variables like "is it spam?" and "is it from someone in my address book?" and "is the sender's first name on my list of common first names?" and so on.

So that's the domain in which we're operating. The common situation is this: Some of the variables are known (or can be quickly and automatically computed). What we want to do is, given those known variables, compute the distributions of the remaining unknown variables. Specifically, we can observe things like "does it have the word 'viagra' on the subject line?" and use the result to generate probabilities for "is it spam?"

Bayes' stuff is all about cause and effect - a bayesian network is just a bunch of variables connected by cause-and-effect lines. So we can say that "email is spam" causes "viagra is in the subject line;" by sampling a load of emails that we've flagged as spam or not spam, we can calculate the probability for each combination of variables.

Then, when we want to find out whether an incoming email is spam, we perform our objective tests (i.e. look for "viagra" in the subject line) which gives us "evidence," i.e. particular values for some variables. Then, through the application of algebraic laws, we can use the bayesian network to calculate the probability that the "email is spam" variable is true given the evidence. My two-variable example isn't really great because it's so simple; this expands to hundreds of variables, and complex chains of cause-and-event relationships.

What I'm really thinking about, of course - you should know by now that I'm thinking about it 24/7 - is whether it's sensible to use it for the thorny problem of tagging. There are two major automatic tagging tasks that V5 will introduce: One is the one-off tagging of all our archived content, and the other is the automatic tag suggester that we'll need if we want to encourage users to tag their content appropriately.

Existing autotag solutions don't seem very intelligent; they simply go on word frequency, perhaps giving higher priority to words that are already known to be tags. While I guess that gives reasonable results some of the time, it would seem to miss things far too often. If I start a thread requesting help with some C++ code, I might start the post with "I need some help with this C++ code," but that's the only point where I'd mention C++. Anyone reading that would accept it as part of the context and read the rest of my post - code dumps, etc - with it in mind. The thread should probably be tagged with "C++." But the frequency-based generators would miss that; the term only occurs once, much less than terms like "class" or "syntax." So I think it's possible to be smarter. That's not to say I think frequency measures should be discounted entirely, just that they should not be the only thing used to measure tags.

This is where I think bayesian networks could add a lot to things. There's a ton of data we've got about a thread beyond its actual content:

• The subject line of the thread


• The forum it was posted in


• The date it was posted


• The replies it has received


• The other threads the original poster has posted


• The other threads that the people replying have participated in

Etcetera. It's almost as if we can generate a Bayesian network for each individual tag: "Shadow mapping" applies to this thread -> this thread is in the Graphics Programming forum (to take another two-event example). All these other bits of evidence can be factored in, with separate weights, to help us draw better conclusions. Words in the subject line of a post are usually highly significant: P("shadow mapping" is in the subject of the thread | "shadow mapping" is an applicable tab) is generally quite high (discounting certain words like 'help'). The thing that's not so smooth is that much of the evidence isn't really discrete - number of times the word 'shadow' appears in the content, for example, is theoretically unbounded - and attempts to discrete-ize it (e.g. "1-5, 5-10, 10+") feels hacky.

I'm also neglecting a rather serious problem here which is that we want, where possible, not to predefine tags. Given a tag like "shadow mapping" I've illustrated that I could construct a bayesian network from it, but how do I select a tag like that in the first place? Again, the frequency approach might give reasonable results - probably better than the earlier scenario, actually, because I could compute it across all the threads in an entire forum to get the list of most commonly used phrases, and while a phrase might only be used once per thread it will probably show up in lots of threads if it's significant. This wouldn't help when the tag that should be suggested is a new or infrequently discussed topic, though perhaps once a tag has been used once I can just apply the bayesian approach to it - rely on someone who is using new/obscure bits of tech to use the tag, and then evaluate that tag for application to all posts after that. It might be a reasonable approach, actually, given that anyone could apply the tag rather than just authors. We might just have enough 'organisers' amongst the userbase that it would work out.

I'm inclined to just write off the scenario of "detect and suggest a tag that is only used once in the post, has never been used by anyone before, but is what the post is all about." I'm fairly sure that there are techniques around to deal with it. Maybe I should talk to kSquared about it.