6
$\begingroup$

I am making a spam filter for an assignment. One of the steps outlined in a paper that I have read indicates finding the mutual information for all the words in the text and then choosing the 500 or so with the highest MI.

The equation given in the paper (and elsewhere) is:

$MI(X_i, C) = \sum{P(X_i, C) \log{\frac{P(X_i, C)}{P(X_i)\cdot P(C)}}}$

where $X_i$ is a feature and $C$ is a class.

It is not clear in the paper but $X_i$ will be a word and $C$ will be either spam or not-spam.

Can I just be clear of the calculation that I should be doing? I think it is as follows for the word "viagra":

$P(X_i, C)$ in this case will be either the frequency that the word "viagra" appears in all of the spam emails divided by the number of words in the spam emails, or the same for the ham (non-spam) emails.

$P(X_i)$ is the probability of the word occurring at all in both spam and ham emails.

$P(C)$ is the prior for a class.

So basically we are doing two calculations (one for the spam and one for the ham) and adding them together.

Is this right do you think?

My understanding is that mutual information is like finding the information gain for a feature. Is this right?

Hope this makes sense. Many thanks in advance.

Improve this question
$\endgroup$
6
  • $\begingroup$ Given the notation $P(X_i,C)$ I would rather think this is the frequency "viagra" appears in a C class email, relative to the number of words total. Otherwise, it would be $P(X_i|C)$. It is also more coherent when looking at the entropy formula: $P(X_i,C)$ and $P(X_i)P(C)$ are comparable. (With respect to which index is the sum computed?) $\endgroup$
    – Xi'an
    Dec 2, 2011 at 15:05
  • $\begingroup$ Hi. Thanks for your reply. This is something which always confuses me, but I still don't understand the difference between $P(X_i, C)$ and $P(X_i|C)$. Is the first saying that $C$ could be any class / all classes and the second that I have specified a class? $\endgroup$
    – Joe
    Dec 2, 2011 at 15:39
  • 3
    $\begingroup$ @Joe not really; the difference is in the denominators. They are related by the familiar formula for conditional probability: $P(A|B) = \frac{P(A \cap B)}{P(B)}$ $\endgroup$
    – Michael McGowan
    Dec 2, 2011 at 15:49
  • $\begingroup$ @Michael - So $P(A,B) = \frac{P(A)}{P(B)}$ ? Thanks for the link, I did look at it, but it had no explanation of $P(A,B)$. I've also seen $P(A;B)$. Really want to get this sorted and grateful for your help. $\endgroup$
    – Joe
    Dec 2, 2011 at 16:05
  • 3
    $\begingroup$ @Joe No, $P(A, B) = P(A\cap B)$. It is the joint probability of both events happening. $\endgroup$
    – Michael McGowan
    Dec 2, 2011 at 16:07

1 Answer 1

Reset to default
10
$\begingroup$

To be a little more explicit, what you are really doing is performing a double sum where you are iterating over all possible states of feature $X_i$ as well as all possible states of $C$. In your particular instance $C$ happens to be binary; that is, it has only two states (spam and ham).

As for $X_i$, it's a little unclear but I'm guessing that is also a binary feature that indicates either the presence or absence of word $i$. So there are really 4 terms in your summation: word $i$ is present in spam, word $i$ is absent in spam, word $i$ is present in ham, and word $i$ is absent in ham.

So the $P(X_i)$ parts are really:

  • P(word $i$ is present)
  • P(word $i$ is absent)

The $P(C)$ parts are really:

  • P(class is spam)
  • P(class is ham)

Then the $P(X_i, C)$ bits are really:

  • P(word $i$ is present and class is spam)
  • P(word $i$ is absent and class is spam)
  • P(word $i$ is present and class is ham)
  • P(word $i$ is absent and class is ham)

You can then plug these values into the summation accordingly.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes great. Thanks for pointing out that $X_i$ has two states. That's definitely right. Very clear explanation thanks for your help. $\endgroup$
    – Joe
    Dec 2, 2011 at 15:41

Your Answer

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

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