# How can I use KL-divergence to weight features?

I have a naive Bayes classifier with two classes (target and non-target) and distributions for a number of features (the same for both classes).

I know that some features contribute more, or less to the overall classification accuracy. I can use KL-divergence to measure the information gain from feature distributions, but how could I use it to weight features?

Say I have features f1, and f2. I have a KL value for the two features and the class.

$KL(f_1, C_1), KL(f_2, C_1)$

$KL(f_1, C_2), KL(f_2, C_2)$

Where do I go from here?

-

I think what you are looking for is Mutual Information (MI). This will give you the amount of information that each feature contains about the class, thereby giving you an indication of the importance of the feature (i.e. the higher the value of the MI, the more the feature matters in classifying).

To weight the features, you'll need to normalize these values. Also, be aware that $MI(f1; C) + MI(f2; C) >= MI(f1, f2; C)$. That is, the summation of mutual information over individual features with the class will be greater than or equal to the mutual information of the joint feature space and the class. This is because features f1 and f2 could contain overlapping information, thus using the joint feature space will produce less information than the sum of the individuals.

-

Mutual Information is one approach, but an alternative is Variation of Information. As a quick start, you might want to track down the paper by Meila. Also, Vinh and Bailey provide a broader perspective of different information theoretic methods.

-
I seem to have opened pandoras box of choice here. Given I'm not sure how to normalize KL-divergence to make it useful to weighting features for my classifier, MI seems like the next best choice. So to avoid paralysis by analysis here, what is the simplest option that will improve classifier performance? Even if it's not ideal. Mutual information? Variation of information? Something else? –  Steven Jan 10 '13 at 23:52
These measures are related (check out the wiki pages on each). In my opinion, MI makes more sense since it measures the mutual dependence of random variables. But both measures are relatively easy to compute, so you can always experiment to see which provides better classification accuracy. –  Nick Jan 11 '13 at 1:31
I sort of figured they were quite related. I've already got KL done actually. But i've got a measure, rather than a probability, so I'm not sure where to go with it from there. As for MI, it seems a bit more involved to calculate. Unless I'm looking at it wrong. I'm going off the wikipedia definition. –  Steven Jan 11 '13 at 2:08