james-server-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gary Robinson <grobin...@goombah.com>
Subject Re: Implementing a "chi-square-based spam filter" - asking Gary Robinson's advice
Date Mon, 18 Sep 2006 03:26:26 GMT
Hi Vincenzo -- 

Let me ask you something. Most top spam filters have more stuff  in 
them the the statistical filter. Would it be practical for you to just 
copy the code of another open-source filter, either translating it into 
Java or using directly? But SpamBayes is excellent and it's written in 
Python -- technically, you should be able to run its engine directly in 
Java using Jython, which translates python to Java bytecodes on the 
fly. Bogofilter is also excellent -- it's written in C so you should be 
able use its engine from Java. SpamAssassin is also excellent, though 
I'm not sure what language  it's written in. They've all done very well 
in head-to-head competitions and/or won awards. (It also happens that 
they all use the chi technique.)

Bogofilter is the only one currently using the "handling redundancy" 
extension to the original technique. (See 
http://www.bgl.nu/bogofilter/esf.html for more info.) I think it's only 
used optionally though; I think the default is the original technique 
described here in my  Linux Journal article: 
http://www.linuxjournal.com/article/6467. It increases filtering 
accuracy very significantly as you can see from that bogofilter link, 
but does take a fair amount of cpu time to find the optimal parms, and 
spending that time is crucial to make it work.

I've been thinking about ways  to speed it up, but I haven't had time 
to implement or test them. The person who implemented the approach 
described in the paper, Greg Louis, is unable to spend time on 
Bogofilter any more. If you're interested in going a bit farther than 
other filters have with this, let me know, and I'd be happy to write it 
up for you, although I won't have time for a couple of weeks.

If you don't want to do that, which would be perfectly understandable, 
I don't think you could do wrong by linking to the bogofilter C code, 
which is fast, of use SpamBayes' Python code via Jython. (One caveat is 
that I personally can't advise on whether there are difficulties in 
breaking the filtering engine out from the interface code in those 
projects.) I can understand, of course, that there may be a need for 
pure Java source, in which case you'd have to translate or, as you're 
already planning, write your own. 

One advantage of using a pre-existing project is that most projects 
evolve over time to match the evolution of spammer tactics, which do 
change significantly over time. I can imagine that it might be too 
distracting for a project that isn't focused on spam filtering to 
really try to keep up, and thus it may be hard to stay competitive with 
the dedicated projects.

Anyway, those are thoughts that come to mind. I'll respond to your 
specific question as soon as I can -- I've got a heavy meeting and 
deadline schedule next week. Also, I'm not sure if you saw the Linux 
Journal article mentioned above -- if you haven't you might want to 
look at it. If so let me know if it resolves any of your questions.



Gary Robinson
Emergent Music, LLC
Company: http://www.goombah.com
Blog:    http://www.garyrobinson.net

On Sun, 17 Sep 2006 13:44:19 +0200, Vincenzo Gianferrari Pini wrote:
> Dear Gary,
> at the Apache James Server Project (http://james.apache.org) we have 
> implemented a (java based) bayesian anti-spam filter following Paul 
> Graham's approach (both the original one - 
> http://paulgraham.com/spam.html - and the enhanced one - 
> http://paulgraham.com/better.html). It is available in the new 2.3.0 
> release that we are releasing these days.
> We would like, for the next release, to implement the 
> "chi-square-based spam filter" approach described in your "Handling 
> Redundancy in Email Token Probabilities" paper 
> (http://garyrob.blogs.com//handlingtokenredundancy94.pdf). But for 
> doing that we need to understand a few points: can you help and 
> advice us?
> I'm CCing this email to the server-dev@james.apache.org list: can you 
> reply to it in your answer?
> Here follow our questions. I will explicitly refer to the terminology 
> and formula numbers used by you in your above mentioned paper.
>   1. Based on Paul Graham's approach, in computing b(w) and g(w) we use
>      in the numerator of the formulas "the total count of occurrences
>      of word w in the spam (ham) e-mails" instead of "the number of
>      spam (ham) e-mails containing the word w" as you do. Paul's
>      counters are persisted on disk, and there are already some users
>      that have extensively trained their systems building their own
>      "corpuses". It would be a pity not to be able to use such
>      collected data when using your approach (we would like to simply
>      add a configuration switch to our filters that optionally - or by
>      default - activates your approach).
>      In your blog
> (http://radio.weblogs.com/0101454/stories/2002/09/16/spamDetection.html)
>      I found the following comment from you:
>          "Note 2: In calculating p(w) Graham counts every instance of
>          word w in every email in which it appears. Obviously, if a
>          word appears once in an email, there is a greater probability
>          that it will appear again in that same email than if it hadn't
>          already appeared at all. So, the random variable is not really
>          independent under Graham's technique which is one reason why,
>          in the description above, we only count the first occurrence.
>          However, we are pragmatic and whatever works best in practice
>          is what we should do. There is some evidence at this point
>          that using the Graham counting technique leads to slightly
>          better results than using the "pure" technique above. This may
>          because it is not ignoring any of the data. So, p(w) and n
>          should simply be computed the way that gives the best results."
>      Looks quite clear to me; can you then confirm us that we can use
>      Paul's counters in computing b(w) and g(w), and that you "endorse"
>      it as leading "to slightly better results" than the technique
>      mentioned in your paper?
>   2. In computing f(w) in formula (1), what do you suggest to use for
>      the values of "s" and "x"? We will let them be configuration
>      parameters as others, but we should use a sound default.
>   3. In computing "H" and "S" in formulas (2) and (3), which of the two
>      definitions of the "inverse chi-square function" and related cdf
>      (invC( ) below) should we use among the two definitions that I
>      found for example in
>      http://en.wikipedia.org/wiki/Inverse-chi-square_distribution?
>   4. Still in computing "H" and "S", how many degrees of freedom "n"
>      should we use? I would assume *one*, being two values (ham and
>      spam) minus one constraint, as their probabilities must sum up to
>      one (in this case question 3 above would be pointless). But I'n
>      not sure at all: can you either confirm or give me a hint?
>   5. As we have already available a java routine that computes the
>      chi-square cdf C(X,n), I found out that to compute the invC(X,n)
>      we could use one of the following formulas (depending on the
>      outcome of question 3 above). Would you be able to help me
>      confirming it?:
>      invC(X,n) = 1 - C(1/X,n)
>      invC(X,n) = 1 - C(n/X,n)
>   6. What do you suggest for a practical default "cutoff" value for "I"
>      and as default ESF value "y" in formula (6) for "H", and which "y"
>      for "S"? And which default for the "exclusion radius"?
> I hope that you do not find those questions as being too many :-) .
> I'm looking forward for your answer .
> If you are interested we will keep you informed about our future progress.
> Thank you.
> Vincenzo Gianferrari Pini

To unsubscribe, e-mail: server-dev-unsubscribe@james.apache.org
For additional commands, e-mail: server-dev-help@james.apache.org

View raw message