Computing symmetric Kullback-Leibler divergence between two documents
<p>I have followed the paper <a href="http://users.softlab.ntua.gr/facilities/public/AD/Text%20Categorization/Using%20Kullback-Leibler%20Distance%20for%20Text%20Categorization.pdf" rel="nofollow noreferrer">here</a> and the code <a href="https://gist.github.com/mrorii/961963" rel="nofollow noreferrer">here</a> (it is implemented using the symmetric kld and a back-off model proposed in the paper in the 1st link) for computing KLD between two text data sets. I have changed the for-loop in the end to return the probability distribution of two data sets to test if both sum to 1:</p>

<pre><code>import re, math, collections

def tokenize(_str):
    stopwords = ['and', 'for', 'if', 'the', 'then', 'be', 'is', \
                 'are', 'will', 'in', 'it', 'to', 'that']
    tokens = collections.defaultdict(lambda: 0.)
    for m in re.finditer(r"(\w+)", _str, re.UNICODE):
        m = m.group(1).lower()
        if len(m) &lt; 2: continue
        if m in stopwords: continue
        tokens[m] += 1

    return tokens
#end of tokenize

def kldiv(_s, _t):
    if (len(_s) == 0):
        return 1e33

    if (len(_t) == 0):
        return 1e33

    ssum = 0. + sum(_s.values())
    slen = len(_s)

    tsum = 0. + sum(_t.values())
    tlen = len(_t)

    vocabdiff = set(_s.keys()).difference(set(_t.keys()))
    lenvocabdiff = len(vocabdiff)

    """ epsilon """
    epsilon = min(min(_s.values())/ssum, min(_t.values())/tsum) * 0.001

    """ gamma """
    gamma = 1 - lenvocabdiff * epsilon

    """ Check if distribution probabilities sum to 1"""
    sc = sum([v/ssum for v in _s.itervalues()])
    st = sum([v/tsum for v in _t.itervalues()])

    ps=[] 
    pt = [] 
    for t, v in _s.iteritems(): 
        pts = v / ssum 
        ptt = epsilon 
        if t in _t: 
            ptt = gamma * (_t[t] / tsum) 
        ps.append(pts) 
        pt.append(ptt)
    return ps, pt
</code></pre>

<p>I have tested with</p>

<p><code>d1 = """Many research publications want you to use BibTeX, which better
organizes the whole process. Suppose for concreteness your source
file is x.tex. Basically, you create a file x.bib containing the
bibliography, and run bibtex on that file."""
d2 = """In this case you must supply both a \left and a \right because the
delimiter height are made to match whatever is contained between the
two commands. But, the \left doesn't have to be an actual 'left
delimiter', that is you can use '\left)' if there were some reason
to do it."""</code></p>

<p><code>sum(ps)</code> = 1  but <code>sum(pt)</code> is way smaller than 1 when:</p>

<p><img src="https://i.stack.imgur.com/25rcv.png" alt="This should be the case."></p>

<p>Is there something that is not correct in the code or else? Thanks!</p>

<p><strong>Update:</strong></p>

<p>In order to make both pt and ps sum to 1, I had to change the code to:</p>

<pre><code>    vocab = Counter(_s)+Counter(_t)
    ps=[] 
    pt = [] 
    for t, v in vocab.iteritems(): 
        if t in _s:
            pts = gamma * (_s[t] / ssum) 
        else: 
            pts = epsilon

        if t in _t: 
            ptt = gamma * (_t[t] / tsum) 
        else:
            ptt = epsilon

        ps.append(pts) 
        pt.append(ptt)

    return ps, pt
</code></pre>