[Perl-AI] text categorization with SVM and NaiveBayes

This may be an issue with your corpus - I quite often find that when
I don't have enough training data for the SVM to pick up on the
"truth" patterns, or (somewhat equivalently) when there's a lot of
noise in the data, a linear kernel will outperform a radial (RBF). I
tend to think that's because the RBF is more expressive, and it's
overfitting the noise in the training set.

That may be an accident of your corpus too. Are you using cross-
validation for these experiments? If so, you should be able to get
some error bars to tell whether the difference is statistically
significant or not. I'm guessing a 2% advantage may not be, in this
case.
Unfortunately, neither NB nor SVMs can really tell you that. SVMs
are purely discriminative, so all they can tell you is "I think this
new example is more like class A than class B in my training data".
There's no probability involved at all. That said, I believe there
has been some research into how to translate SVM output scores into
probabilities or confidence scores, but I'm not really familiar with it.

NB on the surface would seem to be a better option since it's
directly based on probabilities, but again the algorithm was designed
only to discriminate, so all those denominators that are thrown away
(the "P(words)" terms in the A::NB documentation) mean that the
notion of probabilities is lost. The rescale() function is basically
just a hack to return scores that are a little more convenient to
work with than the raw output of the algorithm. As you've seen, it
tends to be a little arrogant, greatly exaggerating the score for the
first category and giving tiny scores to the rest. I'm sure there
are better algorithms that could be used there, but in many cases
either one doesn't really care about the actual scores, or one
(*ahem*) does something ad hoc like taking the square root of all the
scores, or the fifth root, or whatever, just to get some numbers that
look better to end users.

As for a better alternative, I'm not familiar with any that will be
as accessible from a perl world, but you might want to look at some
language modeling papers - I really like the LDA papers from Michael
Jordan (no, not that Michael Jordan, this one: http://
citeseer.ist.psu.edu/541352.html), which are by no means
straightforward, but they will indeed let you describe each document
as generated by a mixture of categories.

-Ken

Just to add a note here: Ken is correct -- both NB and SVMs are known
to be rather poor at providing accurate probabilities. Their scores
tend to be too extreme. Producing good probabilities from these
scores is called calibrating the classifier, and it's more complex
than just taking a root of the score. There are several methods for
calibrating scores. The good news is that there's an effective one
called isotonic regression (or Pool Adjacent Violators) which is
pretty easy and fast. The bad news is that there's no plug-in (ie,
CPAN-ready) perl implementation of it (I've got a simple
implementation which I should convert and contribute someday).

If you want to read about classifier calibration, google one of these
titles:

"Transforming classifier scores into accurate multiclass probability
estimates"
by Bianca Zadrozny and Charles Elkan

"Predicting Good Probabilities With Supervised Learning"
by A. Niculescu-Mizil and R. Caruana

Regards,
-Tom

Cool, thanks for the references. It might be nice to add somesuch
scheme to Algorithm::NaiveBayes (and friends), so that the user has a
choice of several normalization schemes, including "none". If I get
a surplus of tuits I'll add it, or if you feel like contributing your
stuff that would be great too.

-Ken