3
$\begingroup$

How, and should I, use KL-divergence to improve a naive Bayes classifier?

I have a Naive Bayes Classifier working on a number of datatypes (real, boolean and categorical). Each variable is weighted identically. But from inspecting my data I know that some variables contribute more to my overall classification than others.

Should I use KL-divergence (information gain) to weight my probabilities before combining them to calculate class membership? How would I go about this?

If this is the wrong approach, what other approaches might I try?

$\endgroup$
2
$\begingroup$

When estimating the parameters of a naive Bayes classifier, you are effectively optimizing the joint likelihood $p(x, c) = \prod_i p(x_i \mid c) p(c)$ instead of the conditional likelihood $p(c \mid x)$, which is the distribution you are actually interested in.

You can probably get some improvement by directly optimizing the parameters of your model using gradient ascent or something similar with respect to the average conditional log-likelihood, $\left<\log p(c \mid x)\right>$.

If you only want to reweight the probabilities, you could redefine your conditional distribution to something like

$$\log q(c \mid x) = \log p(c) + \sum_i w_i \log p(x_i \mid c) + const$$

and only optimize the weights $w_i$ using gradient ascent. The gradient should be

$$\frac{\partial}{\partial w_j} \left<\log q(c \mid x)\right> = \left<\log p(c \mid x)\right> -\left<\log p(c \mid x)\right>_q,$$

where the first expectation on the right-hand side is with respect to the data and the second is with respect to the data and $q(c \mid x)$.

At least that's what I would try.

I briefly looked at this paper, where they seem to suggest to use mutual information (average information gain, equation 6) for the weights,

$$w_i = I(C, X_i) = \sum_{x_i} p(x_i) D_\text{KL}(p(c \mid x_i) \mid\mid p(c)),$$

but I would have to take a closer look at the paper to tell whether there is a principled motivation behind it or whether it's just a heuristic. Maybe somebody else knows more.

When you optimize the weights directly, at least you know that you're optimizing the right objective function (provided your ultimate goal is to get a good estimate of $p(c \mid x)$ in the Kullback-Leibler sense).

$\endgroup$
  • $\begingroup$ That could work, what's the benefit over KL? But if I still wanted to go ahead with KL-Divergence, how would I go about that? $\endgroup$ – user17880 Jan 10 '13 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy