11

My goal is to compute the KL distance between the following text documents:

1)The boy is having a lad relationship
2)The boy is having a boy relationship
3)It is a lovely day in NY

I first of all vectorised the documents in order to easily apply numpy

1)[1,1,1,1,1,1,1]
2)[1,2,1,1,1,2,1]
3)[1,1,1,1,1,1,1]

I then applied the following code for computing KL distance between the texts:

import numpy as np
import math
from math import log

v=[[1,1,1,1,1,1,1],[1,2,1,1,1,2,1],[1,1,1,1,1,1,1]]
c=v[0]
def kl(p, q):
    p = np.asarray(p, dtype=np.float)
    q = np.asarray(q, dtype=np.float)
    return np.sum(np.where(p != 0,(p-q) * np.log10(p / q), 0))
for x in v:
    KL=kl(x,c)
    print KL

Here is the result of the above code: [0.0, 0.602059991328, 0.0]. Texts 1 and 3 are completely different, but the distance between them is 0, while texts 1 and 2, which are highly related has a distance of 0.602059991328. This isn't accurate.

Does anyone has an idea of what I'm not doing right with regards to KL? Many thanks for your suggestions.

2
  • 1
    Well, v[0]==v[2], thus in the kl function p-q is 0, then the sum is 0. What do you mean by "vectorize the documents" ? Your vectors 1 and 3 are equals. Commented Aug 22, 2013 at 12:55
  • @J.Martinot_Lagarde thanks for your observation. to vectorize here means to have a frequency count of each word in a document, and to use the values to represent the document. The issue here is how to represent each document in such a way that the distance between two documents can be accurately computed using KL.
    – Tiger1
    Commented Aug 22, 2013 at 13:13

3 Answers 3

30

Though I hate to add another answer, there are two points here. First, as Jaime pointed out in the comments, KL divergence (or distance - they are, according to the following documentation, the same) is designed to measure the difference between probability distributions. This means basically that what you pass to the function should be two array-likes, the elements of each of which sum to 1.

Second, scipy apparently does implement this, with a naming scheme more related to the field of information theory. The function is "entropy":

scipy.stats.entropy(pk, qk=None, base=None)

http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.stats.entropy.html

From the docs:

If qk is not None, then compute a relative entropy (also known as Kullback-Leibler divergence or Kullback-Leibler distance) S = sum(pk * log(pk / qk), axis=0).

The bonus of this function as well is that it will normalize the vectors you pass it if they do not sum to 1 (though this means you have to be careful with the arrays you pass - ie, how they are constructed from data).

Hope this helps, and at least a library provides it so don't have to code your own.

1

After a bit of googling to undersand the KL concept, I think that your problem is due to the vectorization : you're comparing the number of appearance of different words. You should either link your column indice to one word, or use a dictionnary:

#  The boy is having a lad relationship It lovely day in NY
1)[1   1   1  1      1 1   1            0  0      0   0  0]
2)[1   2   1  1      1 0   1            0  0      0   0  0]
3)[0   0   1  0      1 0   0            1  1      1   1  1]

Then you can use your kl function.

To automatically vectorize to a dictionnary, see How to count the frequency of the elements in a list? (collections.Counter is exactly what you need). Then you can loop over the union of the keys of the dictionaries to compute the KL distance.

6
  • That won't work... According to wikipedia: "The K–L divergence is only defined if P and Q both sum to 1 and if Q(i)=0 implies P(i)=0." Not sure how to go about it, though.
    – Jaime
    Commented Aug 22, 2013 at 14:43
  • 1
    Right. The most useful article I found was staff.science.uva.nl/~tsagias/?p=185. They compute on the intersection of the vocabulary instead of the union, and add a "workaroud" when the vocabularies are too different. There's even code at the end. Anyway the problem lies in the "vectorisation" part here. Commented Aug 22, 2013 at 18:46
  • Thanks @J.Martinot-Lagarde, I'll take a look at the article.
    – Tiger1
    Commented Aug 22, 2013 at 19:20
  • Another approach to deal with differences in vocab between docs is to add a small probability/frequency to each word, so none have probability zero. This is fairly standard in machine learning, and probably a better idea than ignoring them (eg: if two docs have one word in common, but many different, they are considered identical when you consider the intersection of the vocab!)
    – drevicko
    Commented Apr 22, 2014 at 1:05
  • 1
    link is deadnow, I found an cahed ver web.archive.org/web/20130508191111/http://staff.science.uva.nl/…
    – Sadegh
    Commented Oct 7, 2016 at 9:06
0

A potential issue might be in your NP definition of KL. Read the wikipedia page for formula: http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence

Note that you multiply (p-q) by the log result. In accordance with the KL formula, this should only be p:

 return np.sum(np.where(p != 0,(p) * np.log10(p / q), 0))

That may help...

3
  • 2
    the formula you have there is for non-symmetric KL divergence. Just have a look at symmetric KL divergence, you will understand me better.
    – Tiger1
    Commented Apr 4, 2014 at 9:33
  • 1
    I understand the need for symmetric KL, but I believe what you're doing won't give you it. For a version, check out the Jensen-Shannon divergence: en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence
    – dpb
    Commented Apr 10, 2014 at 16:58
  • I already have Jensen-Shannon devergence in place. I even answered a question on JS divergence on stack overflow. Besides JS divergence, there are other symmetrized version of KL divergence.
    – Tiger1
    Commented Apr 10, 2014 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.