http://www.linuxjournal.com/article/6467

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
  <title>A Statistical Approach to the Spam Problem | Linux Journal</title>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<base href="http://www.linuxjournal.com/" />
<style type="text/css" media="all">@import "misc/drupal.css";</style>
  <style type="text/css" media="all">@import "sites/default/themes/linuxjournal/style.css";</style>
  <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon"/>
  <style type="text/css" media="all">@import "/sites/default/themes/linuxjournal/lj-added.css";</style>
  <script language="JavaScript" type="text/javascript" src="/local/lib/js/browser.js"></script>
  <script language="JavaScript" type="text/javascript" src="/local/lib/js/phpads.js"></script>
  <script language="JavaScript" type="text/javascript" src="http://ads.linuxjournal.com/adx.js"></script>


<!-- 03-Feb-2005 MRF  Menu stuff not used anymore.
  <script language="JavaScript" type="text/javascript" src="/local/lib/doiMenu/js/doiMenuDOM.js"></script>
  <script language="JavaScript" type="text/javascript" src="/local/lib/doiMenu/js/functions.js"></script>
-->
  <script language="JavaScript" type="text/javascript" src="/local/linuxjournal.js"></script>
  <script type="text/javascript"> </script>
</head>

<body bgcolor="#ffffff" >


<table id="primary-menu" summary="Navigation elements." border="0" cellpadding="0" cellspacing="0" width="100%">
  <tr>
    <!--
    <td id="home" width="10%">-->

      <!--<a href="./" title="Home"><img src="sites/default/themes/linuxjournal/logo.png" alt="Home" width="144" height="63" border="0" /></a>-->

    <!--</td>-->
    <!--<td id="site-info" width="20%">-->

       

       

    <!--</td>-->

    <td class="primary-links" width="70%" align="center" valign="middle">

      <table border="0" cellpadding="0" cellspacing="0" width="100%" height="92px"><tr>

<td  class="ljlogo"><a href="/"><img src="/sites/default/themes/linuxjournal/ljlogo.png" alt="logo" border="0" /></a></td>
<td>&nbsp;</td>
  <td class="leaderboard" align="center">
    <script language='JavaScript' type='text/javascript'>
      <!--
      phpads_show_ad("http://ads.linuxjournal.com", "8");
      //-->
    </script>

    <noscript>
      <p><a href='http://ads.linuxjournal.com/adclick.php?n=a6c85b67' target='_blank'>
        <img src='http://ads.linuxjournal.com/adview.php?what=zone:8&amp;n=a6c85b67' border='0' alt='' />
      </a></p>
    </noscript>
</td>
<td class="ldbdsp">&nbsp;</td>
 </tr></table>

    </td>
  </tr>
</table>

<table id="secondary-menu" summary="Navigation elements." border="0" cellpadding="0" cellspacing="0" width="100%">
  <tr>
    <td class="secondary-links" width="100%"  align="center" valign="middle">
      <div>
<form action="/search/node" method="post">
      <table width="100%"><tr>
        <td class="tagline">Since&#160;1994:&#160;The&#160;Original&#160;Monthly&#160;Magazine&#160;of&#160;the&#160;Linux&#160;Community</td>
<td class="taglinetwo">&#160;</td>
<td class="taglinethree">&#160;</td>
        <td class="txtbox"> <input class="form-text" type="text" maxlength="50" size="12" value="" name="keys" alt="Search www.linuxjournal.com" /></td>
        <td class="searchbutton"><input class="form-submit" type="submit" value="Search" alt="submit" /></td>
      </tr></table>
</form>
</div>
    </td>
    <td  width="25%"  align="center" valign="middle">
      <!--
      <form action="search" method="GET">
        <div id="search">
          <input class="form-text" type="text" size="15" value="" name="keys" alt="Enter the terms you wish to search for." />
          <input class="form-submit" type="submit" value="Search" alt="submit" />
        </div>
      </form>
      -->
    </td>
    </tr>
</table>



<table id="content" border="0" cellpadding="15" cellspacing="0" width="100%">
  <tr>



    <td id="sidebar-left">
      
  <div class="block block-block" id="block-block-32">

    <div class="title"><h3>Subscribe Now!</h3></div>
    <div class="content"><table id="primary-links-table" summary="Primary navigation elements." border="1" cellpadding="0" cellspacing="0" width="100%">

<tr>
  <td id="primary-links-hdr">Subscribe&nbsp;<strong>Now</strong>
  </td>
</tr>
<tr>
 <td id="primary-links" class="bgc" valign="middle">
   <ul class="subscribebar" >
     <li><a href="/html/print_digital_subs.html">Subscribe</a></li>
     <li><a href="/archivecd"><span class="new">New</span> Archive CD</a></li>
     <li><a href="https://secure.linuxjournal.com/allsubs/plj.php?action=login">Renew</a></li>
     <li><a href="/xstatic/subs/customer_service.html">Customer&nbsp;Service</a></li>
   </ul>
  </td>
</tr>
</table></div>

 </div>

  <div class="block block-block" id="block-block-33">

    <div class="title"><h3>Magazine</h3></div>
    <div class="content"><ul>
 <li><a href="/xstatic/magazine/archives">Magazine Archives</a></li>
 <li><a href="/xstatic/author/index">Write for Us</a></li>
 <li><a href="/xstatic/staff/index">Masthead</a></li>
 <li><a href="/xstatic/aboutus/FAQ">FAQ</a></li>
 <li><a href="/node/1000123">Press&nbsp;Releases</a></li>
</ul></div>

 </div>

  <div class="block block-block" id="block-block-34">

    <div class="title"><h3>Advertise</h3></div>
    <div class="content"><ul>
 <li><a href="http://www.linuxjournal.com/xstatic/advertising/advertiser-submit">Request Media Kit</a></li>
 <li><a href="http://www.linuxjournal.com/xstatic/advertising/edcal2007">Editorial Calendar</a></li>
 <li><a href="http://www.linuxjournal.com/xstatic/advertising/on-line">Online Advertising</a></li>
 <li><a href="http://www.linuxjournal.com/xstatic/advertising">General Ad Info</a></li>
</ul></div>

 </div>

  <div class="block block-block" id="block-block-35">

    <div class="title"><h3>Resources</h3></div>
    <div class="content"><ul>
 <li><a href="http://www.linuxjournal.com/xstatic/community/whatislinux">What Is Linux?</a></li>
 <li><a href="http://www.linuxjournal.com/xstatic/community/events">Industry Events</a></li>
 <li><a href="http://www.linuxjournal.com/xstatic/community">Other Resources</a></li>
</ul></div>

 </div>

  <div class="block block-block" id="block-block-2">

    <div class="title"><h3>Free eNewsletters</h3></div>
    <div class="content"><ul>
<li><a href="/xstatic/community/ljweeklyupdate">LJ Weekly Update</a></li>
<li><a href="/xstatic/community/ots-newsletter">Off the Shelf</a></li>
</ul>
</div>

 </div>

  <div class="block block-statistics" id="block-statistics-0">

    <div class="title"><h3>Popular content</h3></div>
    <div class="content"><div class="item-list"><h3>Today's:</h3><ul><li><a href="node/1000150">The Ultimate Distro</a></li><li><a href="node/1000211">OpenOffice.org Calc functions, part 2: Working with formulas</a></li><li><a href="article/8761">The Ultimate Linux/Windows System</a></li></ul></div></div>

 </div>

  <div class="block block-block" id="block-block-36">

    <div class="title"><h3></h3></div>
    <div class="content">
<table class="bgc" summary="block Subscription ad" border="1" cellpadding="0" cellspacing="0" width="100%">
   <tr class="nbdr">
	   	<td id="sub-blk-ad-hdr" align="center">
			<a class="sbl" href="https://secure.linuxjournal.com/allsubs/plj.php?action=new-sub&region=US">$1.88 an issue!*
			</a>
		</td>
   </tr>
   <tr class="nbdr">
		<td class="sub-blk-ad-img" align="center"><center>
			<a class="sbl" href="https://secure.linuxjournal.com/allsubs/plj.php?action=new-sub&region=US"><img id="sub-blk-ad-img" src="http://www.linuxjournal.com/xsfiles/subs/media/cover148.png" alt="" />
			</a>
		</center></td>
   </tr>
   <tr class="nbdr">
	    <td class="sub-blk-txt-t" align="center">
			<a class="sbl" href="https://secure.linuxjournal.com/allsubs/plj.php?action=new-sub&region=US">Start your risk-free <br />subscription today!
			</a>
		</td>
   </tr>

   <tr class="nbdr">
		<td class="sub-blk-txt-b" align="center">*based on a 2 yr U.S. sub</td>
   </tr>
</table>
</div>

 </div>

  <div class="block block-user" id="block-user-1">

    <div class="title"><h3>Navigation</h3></div>
    <div class="content"><div class="menu">
<ul>
<li class="leaf"><a href="http://www.linuxjournal.com/xstatic/categories/categories" title="">by subject</a></li>
<li class="leaf"><a href="tracker">recent posts</a></li>
<li class="collapsed"><a href="aggregator">news aggregator</a></li>

</ul>
</div></div>

 </div>

    </td>
    <td valign="top">
       
      <div id="main">
        <div class="breadcrumb"><a href="">Home</a></div>
        <h1 class="title">A Statistical Approach to the Spam Problem</h1>
           
         

<!-- begin content -->

  <div class="node ">
     
     
    <span class="submitted">By <a href="user/801162" title="View user profile.">Gary Robinson</a> on Sat, 2003-03-01 02:00.</span>
    <span class="taxonomy"><a href="taxonomy/term/7">Security</a></span>

    <div class="content">
<p style="color:red"></p>Using Bayesian statistics to detect an e-mail's spamminess.

<div class="article" lang="en">

<div class="simplesect" lang="en">
<div class="titlepage">
<h2 class="title"><a name="N0x850ca10.0x8573a80"></a></h2>
</div>
<p>Most people are spending significant time daily on the task of distinguishing spam from useful e-mail. I
don't think I'm alone in feeling that we have better things to do. Spam-filtering software can help.</p>
<p>This article discusses one of many possible mathematical foundations for a key aspect of spam
filtering--generating an indicator of ``spamminess'' from a collection of tokens representing the content of
an e-mail.</p>
<p>The approach described here truly has been a distributed effort in the best open-source tradition. Paul
Graham, an author of books on Lisp, suggested an approach to filtering spam in his on-line article, ``A Plan
for Spam''. I took his approach for generating probabilities associated with words, altered it slightly and
proposed a Bayesian calculation for dealing with words that hadn't appeared very often. Then I suggested an
approach based on the chi-square distribution for combining the individual word probabilities into a combined
probability (actually a pair of probabilities--see below) representing an e-mail. Finally, Tim Peters of the
Spambayes Project proposed a way of generating a particularly useful spamminess indicator based on the
combined probabilities. All along the way the work was guided by ongoing testing of embodiments written in
Python by Tim Peters for Spambayes and in C by Greg Louis of the Bogofilter Project. The testing was done by
a number of people involved with those projects.</p>
</div>
<div class="simplesect" lang="en">
<div class="titlepage">
<h2 class="title"><a name="N0x850ca10.0x8573b5c"></a>Generating Word Probabilities</h2>
</div>
<p>We will assume the existence of a body of e-mails (the corpus) for training, together with software
capable of parsing each e-mail into its constituent words. We will further assume that each training e-mail
has been classified manually as either ``ham'' (the e-mail you want to read) or ``spam'' (the e-mail you
don't). We will use this data and software to train our system by generating a probability for each word that
represents its spamminess.</p>
<p>For each word that appears in the corpus, we calculate:</p>
<div class="itemizedlist">
<ul type="disc">
<li>
<p><span class="emphasis"><em>b</em></span>(<span class="emphasis"><em>w</em></span>) = (the number of spam
e-mails containing the word <span class="emphasis"><em>w</em></span>) / (the total number of spam
e-mails).</p>
</li>
<li>
<p><span class="emphasis"><em>g</em></span>(<span class="emphasis"><em>w</em></span>) = (the number of ham
e-mails containing the word <span class="emphasis"><em>w</em></span>) / (the total number of ham
e-mails).</p>
</li>
<li>
<p><span class="emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) = <span class=
"emphasis"><em>b</em></span>(<span class="emphasis"><em>w</em></span>) / (<span class=
"emphasis"><em>b</em></span>(<span class="emphasis"><em>w</em></span>) + <span class=
"emphasis"><em>g</em></span>(<span class="emphasis"><em>w</em></span>))</p>
</li>
</ul>
</div>
<p><span class="emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) can be roughly
interpreted as the probability that a randomly chosen e-mail containing word <span class=
"emphasis"><em>w</em></span> will be a spam. Spam-filtering programs can compute <span class=
"emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) for every word in an e-mail and use
that information as the basis for further calculations to determine whether the e-mail is ham or spam.</p>
<p>However, there is one notable wrinkle. In the real world, a particular person's inbox may contain 10% spam
or 90% spam. Obviously, this will have an impact on the probability that, for that individual, an e-mail
containing a given word will be spam or ham.</p>
<p>That impact is ignored in the calculation above. Rather, that calculation, in effect, approximates the
probabilitily that a randomly chosen e-mail containing <span class="emphasis"><em>w</em></span> would be spam
in a world where half the e-mails were spams and half were hams. The merit of that approach is based on the
assumption that we don't want it to be harder or easier for an e-mail to be classified as spam just because
of the relative proportion of spams and hams we happen to receive. Rather, we want e-mails to be judged
purely based on their own characteristics. In practice, this assumption has worked out quite well.</p>
</div>
<div class="simplesect" lang="en">
<div class="titlepage">
<h2 class="title"><a name="N0x850ca10.0x8574134"></a>Dealing with Rare Words</h2>
</div>
<p>There is a problem with probabilities calculated as above when words are very rare. For instance, if a
word appears in exactly one e-mail, and it is a spam, the calculated <span class=
"emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) is 1.0. But clearly it is not
absolutely certain that all future e-mail containing that word will be spam; in fact, we simply don't have
enough data to know the real probability.</p>
<p>Bayesian statistics gives us a powerful technique for dealing with such cases. This branch of statistics
is based on the idea that we are interested in a person's degree of belief in a particular event; that is the
Bayesian probability of the event.</p>
<p>When exactly one e-mail contains a particular word and that e-mail is spam, our degree of belief that the
next time we see that word it will be in a spam is not 100%. That's because we also have our own background
information that guides us. We know from experience that virtually any word can appear in either a spam or
non-spam context, and that one or a handful of data points is not enough to be completely certain we know the
real probability. The Bayesian approach lets us combine our general background information with the data we
have collected for a word in such a way that both aspects are given their proper importance. In this way, we
determine an appropriate degree of belief about whether, when we see the word again, it will be in a
spam.</p>
<p>We calculate this degree of belief, <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>), as follows:</p>
<div class="mediaobject"><img src="/articles/lj/0107/6467/6467f1.png">
<div class="caption">
<p>Equation 1</p>
</div>
</div>
<p>where:</p>
<div class="itemizedlist">
<ul type="disc">
<li>
<p><span class="emphasis"><em>s</em></span> is the strength we want to give to our background
information.</p>
</li>
<li>
<p><span class="emphasis"><em>x</em></span> is our assumed probability, based on our general backround
information, that a word we don't have any other experience of will first appear in a spam.</p>
</li>
<li>
<p><span class="emphasis"><em>n</em></span> is the number of e-mails we have received that contain word <span
class="emphasis"><em>w</em></span>.</p>
</li>
</ul>
</div>
<p>This gives us the convenient use of <span class="emphasis"><em>x</em></span> to represent our assumed
probability from background information and <span class="emphasis"><em>s</em></span> as the strength we will
give that assumption. In practice, the values for <span class="emphasis"><em>s</em></span> and <span class=
"emphasis"><em>x</em></span> are found through testing to optimize performance. Reasonable starting points
are 1 and .5 for <span class="emphasis"><em>s</em></span> and <span class="emphasis"><em>x</em></span>,
respectively.</p>
<p>We will use <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>) rather than
<span class="emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) in our calculations so
that we are working with reasonable probabilities rather than the unrealistically extreme values that can
often occur when we don't have enough data. This formula gives us a simple way of handling the case of no
data at all; in that case, <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>)
is exactly our assumed probability based on background information.</p>
<p>Those who are interested in the derivation of the above formula, read on; others may want to skip down to
the next section.</p>
<p>If you are already familiar with the principles of Bayesian statistics, you will probably have no trouble
understanding the derivation. Otherwise, I suggest that you read sections 1 and 2 of David Heckerman's ``A
Tutorial on Learning with Bayesian Networks'' (see Resources) before continuing.</p>
<p>The formula above is based on assuming that spam/ham classification for e-mails containing word <span
class="emphasis"><em>w</em></span> is a binomial random variable with a beta distribution prior. We calculate
the posterior expectation after incorporating the observed data. We are going to do a test that is the
equivalent of the ``experiment'' of tossing a coin multiple times to see whether it appears to be biased.
There are <span class="emphasis"><em>n</em></span> trials. If we were tossing a coin, each coin toss would be
a trial, and we'd be counting the number of heads. But in our case, the trial is looking at the next e-mail
in the training corpus that contains the word ``porn'' and seeing whether the e-mail it contains is a spam.
If it is, the experiment is considered to have been successful. Clearly, it's a binomial experiment: there
are two values, yes or no. And they are independent: the fact that one e-mail contains ``porn'' isn't
correlated to the question of whether the next one will. Now, it happens that if you have a binomial
experiment and assume a beta distribution for the prior, you can express the expectation that the <span
class="emphasis"><em>n</em></span>th + 1 trial will be successful as shown in Equation 2.</p>
<div class="mediaobject"><img src="/articles/lj/0107/6467/6467f2.png">
<div class="caption">
<p>Equation 2</p>
</div>
</div>
<div class="itemizedlist">
<ul type="disc">
<li>
<p><span class="emphasis"><em>q</em></span> is the number of successes.</p>
</li>
<li>
<p><span class="emphasis"><em>n</em></span> is the number of trials.</p>
</li>
<li>
<p><span class="emphasis"><em>u</em></span> and <span class="emphasis"><em>v</em></span> are the parameters
of the beta distribution.</p>
</li>
</ul>
</div>
<p>We want to show that Equation 1 is equivalent to Equation 2. First perform the following
substitutions:</p>
<p><span class="emphasis"><em>s</em></span> = <span class="emphasis"><em>u</em></span> + <span class=
"emphasis"><em>v</em></span> <span class="emphasis"><em>s</em></span> * <span class=
"emphasis"><em>x</em></span> = <span class="emphasis"><em>u</em></span></p>
<p>The next step is to replace <span class="emphasis"><em>q</em></span> with <span class=
"emphasis"><em>n</em></span> * <span class="emphasis"><em>p</em></span>(<span class=
"emphasis"><em>w</em></span>). We have already discussed the fact that <span class=
"emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) is an approximation of the probability
that a randomly chosen e-mail containing <span class="emphasis"><em>w</em></span> is spam in an imaginary
world where there are the same number of spams as hams. So <span class="emphasis"><em>n</em></span> * <span
class="emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) approximates the count of spams
containing <span class="emphasis"><em>w</em></span> in that world. This approximates the count of successes
in our experiment and is therefore the equivalent of <span class="emphasis"><em>q</em></span>. This completes
our demonstration of the equivalence of Equations 1 and 2.</p>
<p>In testing, replacing <span class="emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>)
with <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>) in all calculations
where <span class="emphasis"><em>p</em></span>(<span class="emphasis"><em>w</em></span>) would otherwise be
used, has uniformly resulted in more reliable spam/ham classification.</p>
</div>
<div class="simplesect" lang="en">
<div class="titlepage">
<h2 class="title"><a name="N0x850ca10.0x85d3478"></a>Combining the Probabilities</h2>
</div>
<p>At this point, we can compute a probability, <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>), for each word that may appear in a new e-mail. This probability reflects our
degree of belief, based on our background knowledge and on data in our training corpus, that an e-mail chosen
randomly from those that contain <span class="emphasis"><em>w</em></span> will be a spam.</p>
<p>So each e-mail is represented by a set of of probabilities. We want to combine these individual
probabilities into an overall combined indicator of spamminess or hamminess for the e-mail as a whole.</p>
<p>In the field of statistics known as meta-analysis, probably the most common way of combining probabilities
is due to R. A. Fisher. If we have a set probabilities, <span class="emphasis"><em>p</em></span>1, <span
class="emphasis"><em>p</em></span>2, ..., <span class="emphasis"><em>p</em></span>n, we can do the following.
First, calculate -2ln <span class="emphasis"><em>p</em></span>1 * <span class="emphasis"><em>p</em></span>2 *
... * <span class="emphasis"><em>p</em></span>n. Then, consider the result to have a chi-square distribution
with 2<span class="emphasis"><em>n</em></span> degrees of freedom, and use a chi-square table to compute the
probability of getting a result as extreme, or more extreme, than the one calculated. This ``combined''
probability meaningfully summarizes all the individual probabilities.</p>
<p>The initial set of probabilities are considered to be with respect to a null hypothesis. For instance, if
we make the null hypothesis assumption that a coin is unbiased, and then flip it ten times and get ten heads
in a row, there would be a resultant probability of (1/2)10 = 1/1024. It would be an unlikely event with
respect to the null hypothesis, but of course, if the coin actually were to be biased, it wouldn't
necessarily be quite so unlikely to have an extreme outcome. Therefore, we might reject the null hypothesis
and instead choose to accept the alternate hypothesis that the coin is biased.</p>
<p>We can use the same calculation to combine our <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>)s. The <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>)s are not real physical probabilities. Rather, they can be thought of as our
best guess about those probabilities. But in traditional meta-anaytical uses of the Fisher calculation they
are not known to be the real probabilities either. Instead, they are assumed to be, as part of the null
hypothesis.</p>
<p>Let our null hypothesis be ``The <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>)s are accurate, and the present e-mail is a random collection of words, each
independent of the others, such that the <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>)s are not in a uniform distribution.'' Now suppose we have a word, ``Python'',
for which <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>) is .01. We
believe it occurs in spams only 1% of the time. Then to the extent that our belief is correct, an unlikely
event occurred; one with a probability of .01. Similarly, every word in the e-mail has a probability
associated with it. Very spammy words like porn might have probabilities of .99 or greater.</p>
<p>Then we use the Fisher calculation to compute an overall probability for the whole set of words. If the
e-mail is a ham, it is likely that it will have a number of very low probabilities and relatively few very
high probabilities to balance them, with the result that the Fisher calculation will give a very low combined
probability. This will allow us to reject the null hypothesis and assume instead the alternative hypothesis
that the e-mail is a ham.</p>
<p>Let us call this combined probability <span class="emphasis"><em>H</em></span>:</p>
<div class="mediaobject"><img src="/articles/lj/0107/6467/6467f3.png">
<div class="caption">
<p>Equation 3</p>
</div>
</div>
<p>where <span class="emphasis"><em>C</em></span>-1() is the inverse chi-square function, used to derive a
p-value from a chi-square-distributed random variable.</p>
<p>Of course, we know from the outset the null hypothesis is false. Virtually no e-mail is actually a random
collection of words unbiased with regard to hamminess or spamminess; an e-mail usually has a telling number
of words of one type or the other. And certainly words are not independent. E-mails containing ``sex'' are
more likely to contain ``porn'', and e-mails containing the name of a friend who programs Python are more
likely also to contain ``Python''. And, the <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>)s are not in a uniform distribution. But for purposes of spam detection, those
departures from reality usually work in our favor. They cause the probabilities to have a nonrandom tendency
to be either high or low in a given e-mail, giving us a strong statistical basis to reject the null
hypothesis in favor of one alternative hypothesis or the other. Either the e-mail is a ham or it is a
spam.</p>
<p>So the null hypothesis is a kind of straw dog. We set it up only in order for it to be knocked down in one
direction or the other.</p>
<p>It may be worthwhile to mention here a key difference between this approach and many other combining
approaches that assume the probabilities are independent. This difference applies, for example, to such
approaches as the ``Bayesian chain rule'' and ``Na&amp;iuml;ve Bayesian classification''. Those approaches
have been tested in head-to-head combat against the approach described here using large numbers of
human-classified e-mails and didn't fare as well (i.e., didn't agree as consistently with human
judgment).</p>
<p>The calculations for those approaches are technically invalid due to requiring an independence of the data
points that is not actually present. That problem does not occur when using the Fisher technique because the
validity of the calculations doesn't depend on the data being independent. The Fisher calculation is
structured such that we are rejecting a null hypothesis that includes independence in favor of one of the two
alternative hypotheses that are of interest to us. These alternative hypotheses each involve
non-independence, such as the correlation between ``sex'' and ``porn'', as part of the phenomenon that
creates the extreme combined probabilities.</p>
<p>These combined probabilities are only probabilities under the assumption that the null hypothesis--known
to be almost certainly false--is true. In the real world, the Fisher combined probability is not a
probability at all, but rather an abstract indicator of how much (or little) we should be inclined to accept
the null hypothesis. It is not meant to be a true probability when the null hypothesis is false, so the fact
that it isn't doesn't cause computational problems for us. The na&amp;iuml;ve Bayesian classifier is known to
be resistant to distortions due to a lack of independence, but it doesn't avoid them entirely.</p>
<p>Whether these differing responses to a lack of independence in the data are responsible for the superior
performance of Fisher in spam/ham classification testing to date is not known, but it is something to
consider as one possible factor.</p>
<p>The individual <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>)s are
only approximations to real probabilities (i.e., when there is very little data about a word, our best guess
about its spam probability as given by <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>) may not reflect its actual reality). But if you consider how <span class=
"emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>) is calculated, you will see that this
uncertainty diminishes asymptotically as <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>) approaches 0 or 1, because such extreme values can be achieved only by words
that have occurred quite frequently in the training data and either almost always appear in spams or almost
always appear in hams. And, conveniently, it's the numbers near 0 that have by far the greatest impact on the
calculations. To see this, consider the influence on the product .01 * .5 if the first term is changed to
.001, vs. the influence on the product .51 *.5 if the first term is changed to .501, and recall that the
Fisher technique is based on multiplying the probabilities. So our null hypothesis is violated by the fact
that the <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>)s are not
completely reliable, but in a way that matters vanishingly little for the words of the most interest in the
search for evidence of hamminess: the words with <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>) near 0.</p>
<p>Alert readers will wonder at this point: ``Okay, I understand that these Fisher calculations seem to make
sense for hammy words with correspondingly near-0 probabilities, but what about spammy words with
probabilities near 1?'' Good question! Read on for the answer that will complete our discussion.</p>
</div>
<div class="simplesect" lang="en">
<div class="titlepage">
<h2 class="title"><a name="N0x850ca10.0x85ce948"></a>The Indicator of Hamminess or Spamminess</h2>
</div>
<p>The calculation described above is sensitive to evidence of hamminess, particularly when it's in the form
of words that show up in far more hams than spams. This is because probabilities near 0 have a great
influence on the product of probabilities, which is at the heart of Fisher's calculation. In fact, there is a
1971 theorem that says the Fisher technique is, under certain circumstances, as powerful as any technique can
possibly be for revealing underlying trends in a product of possibilities (see Resources).</p>
<p>However, very spam-oriented words have <span class="emphasis"><em>f</em></span>(<span class=
"emphasis"><em>w</em></span>)s near 1, and therefore have a much less significant effect on the calculations.
Now, it might be assumed that this is a good thing. After all, for many people, misclassifying a good e-mail
as spam seems a lot worse than misclassifying a bad e-mail as a ham, because no great harm is done if a
single spam gets through but significant harm might result from a single good e-mail being wrongly classified
as spam and therefore ignored by the recipient. So it may seem good to be sensitive to indications of
hamminess and less sensitive to indications of spamminess.</p>
<p>However, there are ways to deal with this problem that in real-world testing do not add a noticeable
tendency to wrongly classify good e-mail as spam, but do significantly reduce the tendency to misclassify
spam as ham.</p>
<p>The most effective technique that has been identified in recent testing efforts follows.</p>
<p>First, ``reverse'' all the probabilities by subtracting them from 1 (that is, for each word, calculate 1 -
<span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>)). Because <span class=
"emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>) represents the probability that a
randomly chosen e-mail from the set of e-mails containing <span class="emphasis"><em>w</em></span> is a spam,
1 - <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>) represents the
probability that such a randomly chosen e-mail will be a ham.</p>
<p>Now do the same Fisher calculation as before, but on the (1 - <span class=
"emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>))s rather than on the <span class=
"emphasis"><em>f</em></span>(<span class="emphasis"><em>w</em></span>)s. This will result in near-0 combined
probabilities, in rejection of the null hypothesis, when a lot of very spammy words are present. Call this
combined probability <span class="emphasis"><em>S</em></span>.</p>
<p>Now calculate:</p>
<div class="mediaobject"><img src="/articles/lj/0107/6467/6467f4.png">
<div class="caption">
<p>Equation 4</p>
</div>
</div>
<p><span class="emphasis"><em>I</em></span> is an indicator that is near 1 when the preponderance of the
evidence is in favor of the conclusion that the e-mail is spam and near 0 when the evidence points to the
conclusion that it's ham. This indicator has a couple of interesting characteristics.</p>
<p>Suppose an e-mail has a number of very spammy words and also a number of very hammy words. Because the
Fisher technique is sensitive to values near 0 and less sensitive to values near 1, the result might be that
both <span class="emphasis"><em>S</em></span> and <span class="emphasis"><em>H</em></span> are very near 0.
For instance, <span class="emphasis"><em>S</em></span> might be on the order of .00001 and <span class=
"emphasis"><em>H</em></span> might be on the order of .000000001. In fact, those kinds of results are not as
infrequent as one might assume in real-world e-mails. One example is when a friend forwards a spam to another
friend as part of an e-mail conversation about spam. In such a case, there will be strong evidence in favor
of both possible conclusions.</p>
<p>In many approaches, such as those based on the Bayesian chain rule, the fact that there may be more spammy
words than hammy words in an example will tend to make the classifier absolutely certain that the e-mail is
spam. But in fact, it's not so clear; for instance, the forwarded e-mail example is not spam.</p>
<p>So it a useful characteristic of <span class="emphasis"><em>I</em></span> that it is near .5 in such
cases, just as it is near .5 when there is no particular evidence in one direction or the other. When there
is significant evidence in favor of both conclusions, <span class="emphasis"><em>I</em></span> takes the
cautious approach. In real-world testing, human examination of these mid-valued e-mails tends to support the
conclusion that they really should be classified somewhere in the middle rather than being subject to the
black-or-white approach of most classifiers.</p>
<p>The Spambayes Project, described in Richie Hindle's article on page 52, takes advantage of this by marking
e-mails with <span class="emphasis"><em>I</em></span> near .5 as uncertain. This allows the e-mail recipient
to give a bit more attention to e-mails that can't be classified with confidence. This lessens the chance of
a good e-mail being ignored due to incorrect classification.</p>
</div>
<div class="simplesect" lang="en">
<div class="titlepage">
<h2 class="title"><a name="N0x850ca10.0x85cf054"></a>Future Directions</h2>
</div>
<p>To date, the software using this approach is based on one word per token. Other approaches are possible,
such as building a hash table of phrases. It is expected that the math described here can be employed in
those contexts as well, and there is reason to believe that phrase-based systems will have performance
advantages, although there is controversy about that idea. Future <span class="emphasis"><em>Linux
Journal</em></span> articles can be expected to cover any developments in such directions. CRM114 (see
Resources) is an example of a phrase-based system that has performed very well, but at the time of this
writing it hasn't been directly tested against other approaches on the same corpus. (At the time of this
writing, CRM114 is using the Bayesian chain rule to combine <span class="emphasis"><em>p</em></span>(<span
class="emphasis"><em>w</em></span>)s.)</p>
</div>
<div class="simplesect" lang="en">
<div class="titlepage">
<h2 class="title"><a name="N0x850ca10.0x85cf15c"></a>Conclusion</h2>
</div>
<p>The techniques described here have been used in projects such as Spambayes and Bogofilter to improve
performance of the spam-filtering task significantly. Future developments, which may include integrating
these calculations with a phrase-based approach, can be expected to achieve even better performance.</p>
<p><a href="/articles/lj/0107/6467/6467s2.html" target="_top">A Python Implementation of the Inverse Chi-Square Function</a></p>
<p><a href="/articles/lj/0107/6467/6467s1.html" target="_top">Resources</a></p>
<div class="blockquote">
<blockquote class="blockquote">
<p><span class="bold"><b>Gary Robinson</b></span> is CEO of Transpose, LLC (<a href=
"http://www.transpose.com" target="_top">www.transpose.com</a>), a company specializing in internet trust and
reputation solutions. He has worked in the field of collaborative filtering since 1985. His personal weblog,
which frequently covers spam-related developments, is <a href="http://radio.weblogs.com/0101454" target=
"_top">radio.weblogs.com/0101454</a>, and he can be contacted at <a href="mailto:grobinson@transpose.com"
target="_top">grobinson@transpose.com</a>.</p>
</blockquote>
</div>
</div>
</div>
<p>email: <a href="mailto:grobinson@transpose.com">grobinson@transpose.com</a></p></div>
      <div class="links">&raquo; <a href="comment/reply/6467#comment" title="Share your thoughts and opinions related to this posting.">add new comment</a> | <a href="emailpage&amp;nid=6467" title="Email this page to a friend">email this page</a> | <a href="node/6467/print" title="Display a printer friendly version of this page.">printer friendly version</a> | 25110 reads</div>

  </div>

<a id="comment"></a>
<form method="post" action="comment"><div>

  <div class="box">
    <h2 class="title">Comment viewing options</h2>
    <div class="content"><div class="form-item">
 <select name="mode"> <option value="1">Flat list - collapsed</option>
 <option value="2">Flat list - expanded</option>
 <option value="3">Threaded list - collapsed</option>
 <option value="4" selected="selected">Threaded list - expanded</option>
</select>
<select name="order"> <option value="1" selected="selected">Date - newest first</option>
 <option value="2">Date - oldest first</option>
</select>
<select name="comments_per_page"> <option value="10">10 comments per page</option> <option value="30">30 comments per page</option> <option value="50" selected="selected">50 comments per page</option> <option value="70">70 comments per page</option> <option value="90">90 comments per page</option></select>
<input type="hidden" name="threshold" value="0" />
 <input type="submit" class="form-submit" name="op" value="Save settings"  />

 <div class="description">Select your preferred way to display the comments and click "Save settings" to activate your changes.</div>
</div>

    </div>
 </div>
<input type="hidden" name="edit[nid]" value="6467" />
</div></form><form method="post" action="comment"><div>
<input type="hidden" name="edit[nid]" value="6467" />
<a id="comment-140518"></a>

  <div class="comment">
     
    <h3 class="title"><a href="article/6467#comment-140518" class="active">Spam Keywords</a></h3>
    <div class="submitted">Submitted by polis kasi (not verified) on Thu, 2006-05-25 05:37. </div>
    <div class="content"><p>I've read all of the book Ending Spam as well as Mr Graham's APlan for spam but i have a problem and i was wondering if anyone can point me to the correct direction. I'm currently doing my senior project and i'm desighing a spam filter but since the corpus of spam and ham e-mails that i have is not big enough i cannot create a keyword dictionary where each word is carrying a weight of how spam it is or not using this mathematical theories. My question is if you know where i can find a ready keyword list where each word is cqrrying a weight?</p>
</div>
    <div class="links">&raquo; <a href="comment/reply/6467/140518">reply</a> | <a href="emailpage&amp;nid=6467" title="Email this page to a friend">email this page</a></div>
  </div>
<div style="margin-left:25px;">
<a id="comment-144525"></a>

  <div class="comment">
     
    <h3 class="title"><a href="article/6467#comment-144525" class="active">The closest thing I&#039;ve found</a></h3>
    <div class="submitted">Submitted by Anonymous (not verified) on Tue, 2006-07-04 23:34. </div>
    <div class="content"><p>The closest thing I've found is a database of known spam messages which have been forwarded to site by the general public.</p>
<p>You can download the raw message files via ftp by going to:<br />
<a href="www.spamarchive.org">www.spamarchive.org<br />
</a></p>
<p>I don't think you'll find any pre-weighted word lists available for download (not publicly anyhow).</p>
<p>Hope this helps.</p>
<p>:)</p>
</div>
    <div class="links">&raquo; <a href="comment/reply/6467/144525">reply</a> | <a href="emailpage&amp;nid=6467" title="Email this page to a friend">email this page</a></div>
  </div>
</div>
<a id="comment-129091"></a>

  <div class="comment">
     
    <h3 class="title"><a href="article/6467#comment-129091" class="active">What does L stand for in the Fisher-Robinson Inverse Chi-Square</a></h3>
    <div class="submitted">Submitted by Johnnie Walker (not verified) on Sun, 2006-02-12 09:42. </div>
    <div class="content"><p>What does L stand for in the Fisher-Robinson Inverse Chi-Square?<br />
In the text above it says "First, calculate -2ln p1 * p2 * ... * pn.", but what is LN? Does it stand for Lexicon Number? Or does the letter L have a greater significance? E.g multiply N by L. I am almost there at getting this understood, any suggestions welcome.</p>
</div>
    <div class="links">&raquo; <a href="comment/reply/6467/129091">reply</a> | <a href="emailpage&amp;nid=6467" title="Email this page to a friend">email this page</a></div>
  </div>
<div style="margin-left:25px;">
<a id="comment-129152"></a>

  <div class="comment">
     
    <h3 class="title"><a href="article/6467#comment-129152" class="active">&#039;ln&#039; means...</a></h3>
    <div class="submitted">Submitted by ChrisSteinbach (not verified) on Mon, 2006-02-13 17:37. </div>
    <div class="content"><p>'ln' is for natural logarithm. If you are using the Python code from this article, you would do something like,</p>
<p><code><br />
import math</p>
<p>def product(values):<br />
....return reduce(lambda x, y: x*y, values)</p>
<p>def chiCombined(probs):<br />
....prod = product(probs)<br />
....return chi2P(-2*math.log(prod) , 2*len(probs))</p>
<p>print chiCombined([0.9, .2, .21, .89, .2, .78])<br />
=>0.572203878688<br />
print chiCombined([0.2, .2, .01, .79, .2, .58])<br />
=>0.0594128323345<br />
print chiCombined([0.7, .89, .71, .79, .972, .68])<br />
=>0.996012078132<br />
</code><br />
/Chris</p>
</div>
    <div class="links">&raquo; <a href="comment/reply/6467/129152">reply</a> | <a href="emailpage&amp;nid=6467" title="Email this page to a friend">email this page</a></div>
  </div>
</div>
<div style="margin-left:50px;">
<a id="comment-130224"></a>

  <div class="comment">
     
    <h3 class="title"><a href="article/6467#comment-130224" class="active">Thanks + &#039;underflowing to zero&#039; tip</a></h3>
    <div class="submitted">Submitted by Johnnie Walker (not verified) on Tue, 2006-02-21 15:58. </div>
    <div class="content"><p>Thanks for your reply Chris. I did a good few searches on Google but could not find any numeric examples of this on the web. So, its a real help to see some numbers to test my own code against.</p>
<p>Whilst trying to find out more about logs, i discovered a good web page for the 'mathematically challenged' programer: <a href="http://www.gigamonkeys.com/book/practical-a-spam-filter.html" target="_blank">http://www.gigamonkeys.com/book/practical-a-spam-filter.html</a> . In that article, the author suggests getting the log of each individual probability first, then multiplying them together. This, apparently, can prevent the result from underflowing to zero. </p>
<p>I'm writing my spam filter in PHP but most examples on the topic seem to be in either LISP or Python (which have quite a similar syntax to PHP in many ways). So, when I'm confident that i've done it right, I'll put a PHP version online. </p>
<p>Thanks, once again, for all those who have shared their knowledge to rid the world of spam; Chris Steinbach, Gary Robinson, Paul Graham, Brian Burton, Jonathan Zdziarski, Bill Yerazunis, Peter Seibel amongst many others.</p>
</div>
    <div class="links">&raquo; <a href="comment/reply/6467/130224">reply</a> | <a href="emailpage&amp;nid=6467" title="Email this page to a friend">email this page</a></div>
  </div>
</div>
<div style="margin-left:75px;">
<a id="comment-130225"></a>

  <div class="comment">
     
    <h3 class="title"><a href="article/6467#comment-130225" class="active">sum the logs not multiply</a></h3>
    <div class="submitted">Submitted by Johnnie Walker (not verified) on Tue, 2006-02-21 16:37. </div>
    <div class="content"><p>Ooops. I'm really showing my ignorance of maths and messing up this beautiful webpage in the process! Sorry folks. To correct my previous comment, the article suggests to sum the logs of each probability (I mistakenly said multiply them) rather than multiplying all the probabilities and then taking the log.</p>
</div>
    <div class="links">&raquo; <a href="comment/reply/6467/130225">reply</a> | <a href="emailpage&amp;nid=6467" title="Email this page to a friend">email this page</a></div>
  </div>
</div>
</div></form>
<!-- end content -->

      </div><!-- main -->

    </td>
    <td id="sidebar-right">
      
  <div class="block block-block" id="block-block-29">

    <div class="title"><h3>Skyscraper Ad</h3></div>
    <div class="content">
<table width="100%" border="0" cellpadding="0" cellspacing="0">
<tr><td align="center">
<script language="JavaScript" type="text/javascript" src="http://ads.linuxjournal.com/adx.js"></script>
<script type="text/javascript">
<!--
phpads_show_ad('http://ads.linuxjournal.com', '23');
//-->
</script><noscript><p>
<a href='http://ads.linuxjournal.com/adclick.php?n=acff6c1e'>
<img src='http://ads.linuxjournal.com/adview.php?what=zone:23&amp;n=acff6c1e' alt='' />
</a></p></noscript>
</td></tr>
</table>
</div>

 </div>

  <div class="block block-block" id="block-block-7">

    <div class="title"><h3>Button 1 zone 6</h3></div>
    <div class="content">
<div class="adimage">
<script language="JavaScript" type="text/javascript" src="http://ads.linuxjournal.com/adx.js"></script>
<script type="text/javascript">
<!--
phpads_show_ad('http://ads.linuxjournal.com', '6');
//-->
</script><noscript><p>
<a href='http://ads.linuxjournal.com/adclick.php?n=acff6c1e'>
<img src='http://ads.linuxjournal.com/adview.php?what=zone:6&amp;n=acff6c1e' alt='' />
</a></p></noscript>
</div>
</div>

 </div>

  <div class="block block-block" id="block-block-12">

    <div class="title"><h3>Text Ad Two -  zone 10</h3></div>
    <div class="content">
<div class="adimage">
<script language="JavaScript" type="text/javascript" src="http://ads.linuxjournal.com/adx.js"></script>
<script type="text/javascript">
<!--
phpads_show_ad('http://ads.linuxjournal.com', '10');
//-->
</script><noscript><p>
<a href='http://ads.linuxjournal.com/adclick.php?n=acff6c1e'>
<img src='http://ads.linuxjournal.com/adview.php?what=zone:10&amp;n=acff6c1e' alt='' />
</a></p></noscript>
</div>
</div>

 </div>

  <div class="block block-block" id="block-block-28">

    <div class="title"><h3>Text ad twelve - zone 22</h3></div>
    <div class="content">
<div class="adimage">
<script language="JavaScript" type="text/javascript" src="http://ads.linuxjournal.com/adx.js"></script>
<script type="text/javascript">
<!--
phpads_show_ad('http://ads.linuxjournal.com', '22');
//-->
</script><noscript><p>
<a href='http://ads.linuxjournal.com/adclick.php?n=acff6c1e'>
<img src='http://ads.linuxjournal.com/adview.php?what=zone:22&amp;n=acff6c1e' alt='' />
</a></p></noscript>
</div>
</div>

 </div>

  <div class="block block-block" id="block-block-27">

    <div class="title"><h3>Text ad 11/z21</h3></div>
    <div class="content">
<div class="adimage">
<script language="JavaScript" type="text/javascript" src="http://ads.linuxjournal.com/adx.js"></script>
<script type="text/javascript">
<!--
phpads_show_ad('http://ads.linuxjournal.com', '21');
//-->
</script><noscript><p>
<a href='http://ads.linuxjournal.com/adclick.php?n=acff6c1e'>
<img src='http://ads.linuxjournal.com/adview.php?what=zone:21&amp;n=acff6c1e' alt='' />
</a></p></noscript>
</div>
</div>

 </div>

    </td>
  </tr>
</table>


<hr id="footer-sep" />

<div id="footer-message">



  <table width="100%"><tr>
<td width="10%" align="left"><img src="/xsfiles/i/drupal07.png" alt="Drupal"/></td>
<td width="80%" id="first-foot-links">
<a class="first" href="/xstatic/advertising/" title="Advertise">Advertise</a>
<a href="/xstatic/community" title="Community" >Community</a>
<a href="/xstatic/aboutus" title="Contact Us">Contact&#160;Us</a>
<a href="https://secure.linuxjournal.com/allsubs/plj.php?action=privacy-stmt" title="Privacy Statement">Privacy&#160;Statement</a>
<a href="MAILTO:webmaster@linuxjournal.com">Report&nbsp;&nbsp;Problems</a></td>
<td width="10%">&#160;</td>
</tr></table>

<table align="center"><tr>
<td id="sec-foot-links">
Copyright &copy; 1994 - 2007 <a href="http://www.linuxjournal.com"><i>Linux Journal</i></a>. All rights reserved.
</td></tr></table>

</div>
</body>
</html>
