[Link] Better results by changing Bayes’ theorem

A little context: translating foreign (f) to English (e) is finding the most-probable English text e for a given foreign phrase,

argmax[e] Pr(e|f)
= argmax[e] Pr(e)*Pr(f|e) / Pr(f)
= argmax[e] Pr(e)*Pr(f|e)

(By applying Bayes rule, and then renormalizing). They found that emprically, it worked better to instead find

argmax[e] Pr(e)^1.5 * Pr(f|e)

What this means is that whatever's generating Pr(f|e) is generating overconfident numbers (or equivalently in this case, that whatever generates Pr(e) is generating underconfident numbers). This corrects for that.

It's a little confusing that this was presented as a modification to Bayes' rule, rather than a calibration factor applied to the underlying estimators, but it's really the latter. The reason for putting it here, rather than there, is probably because if the calibration were done to the original estimates, it would introduce a spurious degree of freedom, since only the relative weights matter.

Bayes is optimal if you throw all your knowledge into the equation. That's practically infeasible, so this program throws away most of the data first, and then applies a heuristic to the remaining data. There's no guarantee that applying Bayes' Rule directly to the remaining data will outperform another heuristic, just that both would be outperformed by running the ideal version of Bayes (and including everything we know about grammar, among other missing data).

Why is this interesting?

Hacker News discussion: http://news.ycombinator.com/item?id=3693447

Top comment is srean, which I will shamelessly copy here:

This is more of tweak of naive Bayes than Bayes' theorem and I suspect he is being a bit tongue in cheek and not letting on whats behind the tweak.

I am sure you have heard that naive Bayes makes gratuitous assumptions of independence. What is not mentioned as often is that it also assumes the document has been generated by a memory-less process.

So if I were to generate a document according to the model assumed by naive Bayes, and I want to decide if I should concatenate another "the" in the document, then I dont need to keep track of how many "the"s that I have already added to the document. As a result the probability of multiple occurrence n_i of a word i goes down exponentially, like this

P(n_i) = p_i^n_i.

Many words do not behave like this. Their probability do not go down monotonically from the start, rather, for words like "the" their probabilities (conditioned on their history) climb initially and then go down.

Naive Bayes works surprisingly well in spite of their grossly violated assumptions. There are many explanations for that. However, we usually forget that to make NB work, we have to throw away "stop-words". Among them are those exact "memory-full" words that violate NB's assumptions.

Let's get back to word frequencies: A model that fits word frequencies quite well is the power law. http://en.wikipedia.org/wiki/Power_law They look like this

P(n_i) \propto  n_i^c

where c is a constant for that word id i. For English, c usually lies in the ball park of -1.5 to -2.1

The tweak that Norvig mentions is not an exact match for power law assumptions but it comes very close. Its using a power law assumption but with sub-optimal parameters. In fact using the power law assumption and with their parameters estimated from the data you could get an even better classifier. Though be careful of the industry of seeing power laws everywhere. Log normal distributions can look deceptively similar to a power law and is more appropriate on many such occasions.

Yeah Naive Bayes has a bad assumption of independence, but there is no reason that they have to be memory-less too and that is partly what the tweak fixes, and the theorem isn't really being violated.

Two possible explanations come to mind:

• They are defining "better" as something other than higher expected value of number of correctly translated words.

• The probabilities they're using are biased, and this reverses the bias.