The Kullback-Liebler (KL) divergence is a fundamental equation of information theory that quantifies the proximity of two probability distributions. If the true probability distribution of a sequence of events is denoted by P, then for any distribution Q that is used to model or approximate the true distribution P, the information lost in the process is the KL Divergence.
DKL (P||Q) = ∑i Pi log2 (Pi / Qi)
As you can see that this quantity can be related to the mutual information that we had used earlier for feature selection. Mutual Information is the KL Divergence of the joint distribution of feature and class P(Class, Feature) from the product of their marginal distributions P(Class)*P(Feature).
Given that we know the joint distribution P(Class, Feature) i.e. the probability a document containing both feature F and belonging to class C, if we approximate it with P(Class)*P(Feature), our approximation is correct if and only if the feature F is independent of class C, but if given that, for documents belonging to class C, the probability of feature F occurring in those documents is higher than any other documents, then our approximation has errors as it does not account for this additional information gain. Higher the KL divergence, higher is the divergence of the feature from being equally probable in all classes.
Given that the feature F is contained inside N documents, and it is observed that out of N documents, N1 belongs to class c1, N2 to class c2 and N3 to class c3. What is the likelihood of observing this distribution given that the feature is equally likely to be present in all the 3 classes ?
Likelihood = N!/(N1! N2! N3!) (1/3)N
Then finding the average log likelihood of the above quantity, we get :
L = (1/N) log (N!/(N1! N2! N3!) (1/3)N)
Using Stirling’s approximation log N! ≈ N log N – N, for large values of N, we get
L = (1/N) (N log N – N – N1 log N1 – N2 log N2 – N3 log N3 + N1 + N2 + N3 – N log 3)
= (1/N) (N log N – N1 log N1 – N2 log N2 – N3 log N3 – N log 3), since N1 + N2 + N3 = N
= (1/N) (- N1 log (3N1/N)- N2 log (3N2/N) – N3 log (3N3/N))
If we denote Pi = (Ni /N) and Qi = 1/3, then we see that the above average log likelihood equals – ∑i Pi log2 (Pi / Qi), i.e. the negative of the KL Divergence.
Hence KL Divergence measures the negative of the average log likelihood of observing the joint probability distribution P(Class, Feature) given that the feature is equally probable in all the classes i.e. features are selected randomly with replacement from a feature space and put in documents without any information which class the document belongs to.
The Mechanical Mind 