Understanding entropy/salience of probability distribution of two data sets

I'm using a 1.6M tweet corpus to train a naive bayes sentiment engine.

I am trying to "compute the entropy of a probability distribution of the appearance of an n-gram in different datasets". My two data sets are n-grams constructed from a positive corpus & negative corpus, and I want to remove any common n-grams with a high entropy.

I have spent several hours searching the web for how to do this in code. I'm not necessarily looking for code, as I'd prefer to understand what I'm doing, but I just don't know where to start. I was either a math or CS major my 2 years in college, so I have enough of a background in this area to be... still utterly confused :)

I'm also relatively new to this space, so I'm sure my ignorance is playing a bit of a part in this, but I'm hoping somebody can help nudge me in the right direction. I posted the question on SO but the more I think about it, the more I'm not sure that's the right place to ask...

The two equations are as follows (first time ever trying to use Latex formatting, so sorry if it's butchered):

$$\text{entropy}(g) = H(p(S|g)) = -\sum_{i=1}^N p(S_i|g) \log(p(S_i|g))$$

$$\text{salience}(g) = \frac{1}{N} \sum\limits_{i=1}^{N-1} \sum\limits_{j=i+1}^N \left(1 - \frac{\min(P(g|S_i),P(g|S_j))}{\max(P(g|S_i),P(g|S_j))}\right)$$

G is a set of n-grams representing the message, N is the number of sentiments (in my case, 2), S represents Shannon Entropy

If breaking that down into layman/pseudo-code isn't an appropriate scope, I'm happy to be pointed towards resources where I can learn this on my own.

Many thanks!

 I am attempting to follow this pdf document, specifically step 5.3 for increasing accuracy (not used for developing bayesian sentiment) [/Edit]

[Edit 2] So given an N of 2, I believe entropy is defined as:

$$p(S_1|g) * log(p(S_1|g) - p(S_2|g) * log(P(S_2|g)$$

Where $p(S_1|g)$ is calculated as (ng_count) / (ng_count+total_count), if ng_count is the number of instances my n-gram shows up in my $S_1$ corpus, and total_count is the total count of all n_gram instances. Is that correct? [/Edit 2]

• Did you delete the SO version? It's best to have just one copy of a question floating around the SE site at a time... – whuber Sep 27 '11 at 5:34
• Could you please explain what $g$ and the $S_i$ are? It's best not to make your readers guess. – whuber Sep 27 '11 at 5:37
• Yeah I thought about it, but that question is geared primarily towards actual code (deadlines are no fun) & confirming the logic I have worked out, whereas this is more about resources & knowledge to help my understanding. It's asking the same question from two different perspectives (and two different answers, no?). Your thoughts? – Scott Silvi Sep 27 '11 at 5:37
• Thanks for feedback on post. Added s/g/n - sorry for my ignorance - I didn't think to include that, but it makes absolute sense as soon as you mentioned it :) Bonehead moment. – Scott Silvi Sep 27 '11 at 5:42
• It's ok to maintain two versions of the same question, Scott. If they have a lot in common, we hope you will summarize useful answers across all versions. In this case, it appears you are asking us to guess the meaning of formulas you are citing. It would help to provide links or explicit references to them. – whuber Sep 27 '11 at 14:04