Some perhaps relevant links (with no off-topic discusssion): * http://www.tuxedo.org/~esr/bogofilter/ * http://www.ai.mit.edu/~jrennie/ifile/ * http://groups.google.com/groups?selm=ajk8mj%241c3qah%243%40ID-125932.news.df... """My finding is that it is _nowhere_ near sufficient to have two populations, "spam" versus "not spam." If you muddle together the Nigerian Pyramid schemes with the "Penis enhancement" ads along with the offers of new credit cards as well as the latest sites where you can talk to "hot, horny girls LIVE!", the statistics don't work out nearly so well. It's hard to tell, on the face of it, why Nigerian scams _should_ be considered textually similar to phone sex ads, and in practice, the result of throwing them all together" There are a few things left to improve about Ifile, and I'd like to redo it in some language fundamentally less painful to work with than C """ "Barry A. Warsaw" wrote:

...

...

...

...

...

"SM" == Skip Montanaro writes:

tim> Straight character n-grams are very appealing because they're tim> the simplest and most language-neutral; I didn't have any tim> luck with them over the weekend, but the size of my training tim> data was trivial.

SM> Anybody up for pooling corpi (corpora?)?

I've got collections from python-dev, python-list, edu-sig, mailman-developers, and zope3-dev, chopped at Feb 2002, which is approximately when Greg installed SpamAssassin. The collections are /all/ known good, but pretty close (they should be verified by hand).

The idea is to take some random subsets of these, cat them together and use them as both training and test data, along with some 'net-available known spam collections.

No time more to play with this today though... -Barry

_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev

-- Paul Prescod

[Eric S. Raymond]

I'm in the process of speed-tuning this now. I intend for it to be blazingly fast, usable for sites that process 100K mails a day, and I think I know how to do that. This is not a natural application for Python :-).

I'm not sure about that. The all-Python version I checked in added 20,000 Python-Dev messages to the database in 2 wall-clock minutes. The time for computing the statistics, and for scoring, is simply trivial (this wouldn't be true of a "normal" Bayesian classifier (NBC), but Graham skips most of the work an NBC does, in particular favoring fast classification time over fast model-update time). What we anticipate is that the vast bulk of the time will end up getting spent on better tokenization, such as decoding base64 portions, and giving special care to header fields and URLs. I also *suspect* (based on a previous life in speech recogniation) that experiments will show that a mixture of character n-grams and word bigrams is significantly more effective than a "naive" tokenizer that just looks for US ASCII alphanumeric runs.

...

"""My finding is that it is _nowhere_ near sufficient to have two populations, "spam" versus "not spam."

Well, except it seems to work quite well. The Nigerian trigger-word population is distinct from the penis-enlargement population, but they both show up under Bayesian analysis.

In fact, I'm going to say "Nigerian" and "penis enlargement" one more time each here, just to demonstrate that *this* message won't be a false positive when the smoke settles <wink>. Human Growth Hormone too, while I'm at it.

Eric> This is one of bogofilter's strengths. It already does this stuff Eric> at the lexical level using a speed-tuned flex scanner (I spent a Eric> lot of the development time watching token strings go by and Eric> tweaking the scanner rules to throw out cruft). This reminds me of something which tickled my interesting bone the other day. The SpamAssassin folks are starting to look at Flex for much faster regular expression matching in situations where large numbers of static re's must be matched. I wonder if using something like SciPy's weave tool would make it (relatively) painless to incorporate fairly high-speed scanners into Python programs. It seems like it would just be an extra layer of compilation for something like weave. Instead of inserting C code into a string, wrapping it with module sticky stuff and compiling it, you'd insert Flex rules into the string, call a slightly higher level function which calls flex to generate the scanner code and use a slightly different bit of module sticky stuff to make it callable from Python. Skip

>> ...insert Flex rules into the string, call a slightly higher level >> function which calls flex to generate the scanner code and use a >> slightly different bit of module sticky stuff to make it callable >> from Python. Eric> Lexers are painful in Python. They hit the language in a weak Eric> spot created by the immutability of strings. Yeah, that's why you inline what is essentially a .l file into your Python code. ;-) I'm actually here in Austin for a couple days visiting Eric Jones and the SciPy gang. Perhaps Eric and I can bat something out over lunch tomorrow... Skip

I'm mildly curious why nobody has suggested mxTextTools or anything like that. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ Project Vote Smart: http://www.vote-smart.org/

I'm mildly curious why mxTextTools proponents

eh? why did my mailer send that mail? what I was trying to say is that I'm mildly curious why people tend to treat mxTextTools like some kind of silver bullet, without actually comparing it to a well- written regular expression. I've heard from people who've spent days rewriting their application, only to find that the resulting program was slower. (as Guido noted, for problems like this, the overhead isn't so much in the engine itself, as in the effort needed to create Python data structures...) </F>

On 21 Aug 2002 at 8:28, Aahz wrote:

... I've never actually used mxTextTools; I'm mostly going by comments Tim Peters has made in the past suggesting that regex tools are poor for parsing.

They suck for parsing. They excel for lexing, however. -- Gordon http://www.mcmillan-inc.com/

On Wed, Aug 21, 2002, Skip Montanaro wrote:

aahz> I'm mostly going by comments Tim Peters has made in the past aahz> suggesting that regex tools are poor for parsing.

parsing != tokenizing. ;-) Regular expressions are great for tokenizing (most of the time).

Ah. Here we see one of the little drawbacks of not finishing my CS degree. ;-) Can someone suggest a good simple reference on the distinctions between parsing / lexing / tokenizing, particularly in the context of general string processing (e.g. XML) rather than the arcane art of compiler technology? -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ Project Vote Smart: http://www.vote-smart.org/

Aahz :

Ah. Here we see one of the little drawbacks of not finishing my CS degree. ;-) Can someone suggest a good simple reference on the distinctions between parsing / lexing / tokenizing, particularly in the context of general string processing (e.g. XML) rather than the arcane art of compiler technology?

It's pretty simple, actually. Lexing *is* tokenizing; it's breaking the input stream into appropopriate lexical units. When you say "lexing" it implies that your tokenizer may be doing other things as well -- handling comment syntax, or gathering low-level semantic information like "this is a typedef". Parsing, on the other hand, consists of attempting to match your input to a grammar. The result of a parse is typically either "this matches" or to throw an error. There are two kinds of parsers -- event generators and structure builders. Event generators call designated hook functions when they recognize a piece of syntax you're interested in. In XML-land, SAX is like this. Structure builders return some data structure (typically a tree) representing the syntax of your input. In XML-land, DOM is like this. There is a vast literature on parsing. You don't need to know most of it. The key thing to remember is that, except for very simple cases, writing parsers by hand is usually stupid. Even when it's simple to do, machine-generated parsers have better hooks for error recovery. There are several `parser generator' tools that will compile a grammar specification to a parser; the best-known one is Bison, an open-source implementation of the classic Unix tool YACC (Yet Another Compiler Compiler). Python has its own parser generator, SPARK. Unfortunately, while SPARK is quite powerful (that is, good for handling ambiguities in the spec), the Earley algorithm it uses gives O(n**3) performance in the generated parser. It's not usable for production on larger than toy grammars. The Python standard library includes a lexer class suitable for a large class of shell-like syntaxes. As Guido has pointed out, regexps provide another attack on the problem. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

On Wed, Aug 21, 2002 at 03:28:51PM -0400, Guido van Rossum wrote:

I would note that for small languages (much smaller than Python), writing a recursive-descent parser by hand is actually one of the most effective ways of creating a parser. I recently had the pleasure to write a recursive-descent parser for a simple Boolean query language; there was absolutely no need to involve a big gun like a parser generator. OTOH I would not consider writing a recursive-descent parser by hand for Python's Grammar -- that's why I created pgen in the first place. :-)

You might be interested to know that over in GCC land we're changing the C++ front end to use a hand-written recursive descent parser. It's not done yet, but we expect it to be easier to maintain, faster, and better at generating diagnostics than the existing yacc-based parser. zw

On Wednesday 21 August 2002 09:50 pm, Zack Weinberg wrote: ...

You might be interested to know that over in GCC land we're changing the C++ front end to use a hand-written recursive descent parser. It's not done yet, but we expect it to be easier to maintain, faster, and better at generating diagnostics than the existing yacc-based parser.

Interesting! This reminds me of a long-ago interview with Borland's techies about how they had managed to create Turbo Pascal, which ran well in a 64K (K, not M-) one-floppy PC, when their competitor, Microsoft Pascal, forced one to do a lot of disc-jockeying even with 256K and 2 floppies. Basically, their take was "we just did everything by the Dragon Book -- except that the parser is a hand-written recursive descent parser [Aho &c being adamant defenders of Yacc & the like], which buys us a lot" ... Alex

On Thu, Aug 22, 2002, Greg Ewing wrote:

Alex Martelli :

...

This reminds me of a long-ago interview with Borland's techies about how they had managed to create Turbo Pascal, which ran well in a 64K (K, not M-) one-floppy PC

Even more impressive was the earlier version of Turbo Pascal which ran on 64K Z80-based CP/M systems!

s/64K/48K/ I believe you could actually theoretically start it up with only 32K of memory, but you couldn't do any real work. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ Project Vote Smart: http://www.vote-smart.org/

On Wed, 21 Aug 2002, Guido van Rossum wrote:

I would note that for small languages (much smaller than Python), writing a recursive-descent parser by hand is actually one of the most effective ways of creating a parser. I recently had the pleasure to write a recursive-descent parser for a simple Boolean query language; there was absolutely no need to involve a big gun like a parser generator. OTOH I would not consider writing a recursive-descent parser by hand for Python's Grammar -- that's why I created pgen in the first place. :-)

As per Zach's comments, I think this is pretty funny. I have just spent more time trying to expose pgen to the interpreter than I took to write a R-D parser for Python 1.3 (granted, once Fred's parser module came around, I felt a bit silly). Considering the scope of my parser generator integration wishlist, having GCC move to a hand coded recursive descent parser is going to make my head explode. Even TenDRA (http://www.tendra.org/) used a LL(n) parser generator, despite its highly tweaked lookahead code. So now I'm going to have to extract grammars from call trees? As if the 500 languages problem isn't already intractable, there are going to be popular language implementations that don't even bother with an abstract syntax specificaiton!? (Stop me from further hyperbole if I am incorrect.) No wonder there are no killer software engineering apps. Maybe I should just start writing toy languages for kids... *smirk* -Jon

tim wrote:

Parser generators are great for little languages! They're painful for real languages, though, because syntax warts accumulate and then tool rigidity gets harder to live with. Hand-crafted R-D parsers are wonderfully tweakable in intuitive ways (staring at a mountain of parse-table conflicts and divining how to warp the grammar to shut the tool up is a black art nobody should regret not learning ...).

cf. http://compilers.iecc.com/comparch/article/00-12-106 "For me and C++, [using a parser generator] was a bad mistake." </F>

On 21 Aug 2002 at 10:34, Fredrik Lundh wrote:

eh? why did my mailer send that mail? what I was trying to say is that I'm mildly curious why people tend to treat mxTextTools like some kind of silver bullet, without actually comparing it to a well- written regular expression.

I've heard from people who've spent days rewriting their application, only to find that the resulting program was slower.

(as Guido noted, for problems like this, the overhead isn't so much in the engine itself, as in the effort needed to create Python data structures...)

mxTextTools lets (encourages?) you to break all the rules about lex -> parse. If you can (& want to) put a good deal of the "parse" stuff into the scanning rules, you can get a speed advantage. You're also not constrained by the rules of BNF, if you choose to see that as an advantage :-). My one successful use of mxTextTools came after using SPARK to figure out what I actually needed in my AST, and realizing that the ambiguities in the grammar didn't matter in practice, so I could produce an almost-AST directly. -- Gordon http://www.mcmillan-inc.com/

Tim Peters wrote:

[Gordon McMillan]

...

mxTextTools lets (encourages?) you to break all the rules about lex -> parse. If you can (& want to) put a good deal of the "parse" stuff into the scanning rules, you can get a speed advantage. You're also not constrained by the rules of BNF, if you choose to see that as an advantage :-).

My one successful use of mxTextTools came after using SPARK to figure out what I actually needed in my AST, and realizing that the ambiguities in the grammar didn't matter in practice, so I could produce an almost-AST directly.

I don't expect anyone will have much luck writing a fast lexer using mxTextTools *or* Python's regexp package unless they know quite a bit about how each works under the covers, and about how fast lexing is accomplished by DFAs. If you know both, you can build a DFA by hand and painfully instruct mxTextTools in the details of its construction, and get a very fast tokenizer (compared to what's possible with re), regardless of the number of token classes or the complexity of their definitions. Writing to mxTextTools directly is a lot like writing in an assembly language for a character-matching machine, with all the pains and potential joys that implies. If I were Eric, I'd use Flex <wink>.

FYI, there are a few meta languages to make life easier for mxTextTools like e.g. Mike Fletcher's SimpleParse. The upcoming version 2.1 will also support Unicode and allows text jump targets which boosts readability of the tag tables a lot and makes hand-writing the tables much easier. The beta of 2.1 is available to the subscribers of the egenix-users mailing list. -- Marc-Andre Lemburg CEO eGenix.com Software GmbH _______________________________________________________________________ eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/

tor 2002-08-22 klockan 03.13 skrev Tim Peters:

Seems more to me that lexing is convenient and fast only when expressed in a language specifically designed for writing lexers, and backed by a specialized execution engine that knows a great deal about fast state-machine implementation. Like, say, Flex. Lexing is also clumsy and slow in SNOBOL4 and Icon, despite that they excel at higher-level pattern-matching tasks. IOW, lexing is in a world by itself, almost nothing is good at it, and the few things that shine at it don't do anything else.

I've actually found that Haskell's pattern matching and lazy evaluation makes it pretty easy to write lexers. Too bad it's too hard to use Haskell together with other languages :( But then, writing a R-D parser in Haskell is piece-of-cake too :-) Martin

"Eric S. Raymond" :

Tim Peters :

...

But you lost me here -- I don't see a connection between immutability and either ease of writing lexers or speed of lexers. It's an implementation problem. You find yourself doing a lot of string accessing and pasting, creating several new objects per input char.

Not necessarily! Plex manages to do it without any of that. The trick is to leave all the characters in the input buffer and just *count* how many characters make up the next token. Once you've decided where the token ends, one slice gives it to you. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+

Hmm. But you can also generate pretty reasonable C code from Python source now too! You're going to solve this yet, Greg.

Yes, probably the first serious use I make of Pyrex will be to re-implement the inner loop of Plex so it runs at C speed. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+

[attribution lost]

...

...

It's an implementation problem. You find yourself doing a lot of string accessing and pasting, creating several new objects per input char.

[Greg Ewing]

...

Not necessarily! Plex manages to do it without any of that.

The trick is to leave all the characters in the input buffer and just *count* how many characters make up the next token.

[/F]

you can do that without even looking at the characters?

1-character strings are shared; string[i] doesn't create a new object except for the first time that character is seen. string_item() in particular uses the character found to index into an array of 1-character string objects.

I wonder if using something like SciPy's weave tool would make it (relatively) painless to incorporate fairly high-speed scanners into Python programs.

I haven't given up on the re module for fast scanners (see Tim's note on the speed of tokenizing 20,000 messages in mere minutes). Note that the Bayes approach doesn't *need* a trick to apply many regexes in parallel to the text. --Guido van Rossum (home page: http://www.python.org/~guido/)

[Skip Montanaro]

The SpamAssassin folks are starting to look at Flex for much faster regular expression matching in situations where large numbers of static re's must be matched.

This problem was also vivid in `procmail'-based SPAM filtering, as I observed it many years ago, and I remembered having quite lurked on the side of Flex at the time. I finally solved my own problem by writing a Python program able to sustain thousands of specialised rules rather speedily, proving once again that algorithmic approaches are often much slower than languages :-).

I wonder if using something like SciPy's weave tool would make it (relatively) painless to incorporate fairly high-speed scanners into Python programs.

For a pure Python solution, PLEX could also be an avenue. It compiles a fast automaton, similar to what Flex does, from a grammar describing all tokens. I tried PLEX recently and was satisfied, even if not astonished by the speed. Also wanting fast parsing, I first used various Python heuristics, but the result was not solid enough to my taste. So I finally opted for Bison, and once on that road, it was just natural to rewrite the PLEX part in Flex. [Guido van Rossum]

I think you're exaggerating the problem, or at least underestimating the re module. The re module is pretty fast!

There are limits to what a backtracking matcher could do, speed-wise, when there are many hundreds of alternated patterns. [Eric S. Raymond]

It's pretty simple, actually. Lexing *is* tokenizing; it's breaking the input stream into appropopriate lexical units. [...] Parsing, on the other hand, consists of attempting to match your input to a grammar. The result of a parse is typically either "this matches" or to throw an error. There are two kinds of parsers -- event generators and structure builders.

Maybe lexing matches a grammar to a point, generates an event according to the match, advances the cursor and repeats until the end-of-file is met. Typically, parsing matches a grammar at point and does not repeat. In some less usual applications, they may be successive lexing stages, each taking its input from the output of the previous one. Parsing may be driven in stages too. I guess that we use the word `lexer' when the output structure is more flat, and `parser' when the output structure is more sexy! There are cases where the distinction is almost fuzzy. [Skip Montanaro]

Guido> I haven't given up on the re module for fast scanners (see Guido> Tim's note on the speed of tokenizing 20,000 messages in Guido> mere minutes). Note that the Bayes approach doesn't *need* Guido> a trick to apply many regexes in parallel to the text.

Right. I'm thinking of it in situations where you do need such tricks. SpamAssassin is one such place. I think Eric has an application (quickly tokenizing the data produced by an external program, where the data can run into several hundreds of thousands of lines) where this might be beneficial as well.

Heap queues could be useful here as well. Consider you have hundreds of regexps to match in parallel on a big text. When the regexp is not too complex, it is more easy or likely that there exists a fast searcher for it. Let's build one searcher per regexp. Always beginning from the start of text, find the spot where each regexp first matches. Build a heap queue using the position as key, and both the regexp and match data as value. The top of the heap is the spot of your first match, process it, and while removing it from the heap, search forward from that spot for the same regexp, and add any result back to the heap. Merely repeat until the heap is empty. I'm not fully sure, but I have the intuition the above could be advantageous. -- François Pinard http://www.iro.umontreal.ca/~pinard

[Eric S. Raymond]

(Copied to Paul Graham. Paul, this is the mailing list of the Python maintainers. I thought you'd find the bits about lexical analysis in bogofilter interesting. Pythonistas, Paul is one of the smartest and sanest people in the LISP community, as evidenced partly by the fact that he hasn't been too proud to learn some lessons from Python :-). It would be a good thing for some bridges to be built here.)

Hi, Paul! I believe Eric copied you on some concerns I had about the underpinnings of the algorithm, specifically about the final "is it spam?" computation. Looking at your links, I bet you got the formula from here: http://www.mathpages.com/home/kmath267.htm If so, the cause of the difficulty is that you inherited a subtle (because unstated) assumption from that writeup: I would suggest that we assume symmetry between "y" and "n". In other words, assume that probability of predicting correctly is the same regardless of whether the correct answer is "y" or "n". That part's fine. This implies p0=p7, p1=p6, p2=p5, and p3=p4, But that part doesn't follow from *just* the stated assumptions: note that those four equalities imply that p0+p2+p4+p6 = p7+p5+p3+p1 But the left-hand side of that is the probability that event X does not occur (it's all the rows with 'n' in the 'R' column), and the right-hand side is the probability that event X does occur (it's all the rows with 'y' in the 'R' column). In other words, this derivation also makes the stronger-- and unstated --assumption that X occurs with probability 1/2. The ultimate formula given on that page is correct if P(X)=0.5, but turns out it's wrong if P(X) isn't 0.5. Reality doesn't care how accurate Smith and Jones are, X occurs with its own probability regardless of what they think. Picture an extreme: suppose reality is such that X *always* occurs. Then p0 must be 0, and so must p2, p4 and p6 (the rows with 'n' in the R column can never happen if R is always 'y'). But then p0+p2+p4+p6 is 0 too, and the equality above implies p7+p5+p3+p1 is also 0. We reach the absurd conclusion that if X always occurs, the probability that X occurs is 0. As approximations to 1 go, 0 could stand some improvement <wink>. The math is easy enough to repair, but it may percolate into other parts of your algorithm. Chiefly, I *suspect* you found you needed to boost the "good count" by a factor of 2 because you actually have substantially more non-spam than spam in your inbox, and the scoring step was favoring "spam" more than it should have by virtue of neglecting to correct for that your real-life P(spam) is significantly less than 0.5 (although your training corpora had about the same number of spams as non-spams, so that P(spam)=0.5 was aprroximately true across your *training* data -- that's another complication). Makes sense? Once our testing setup is trustworthy, I'll try it both ways and report on results. In the meantime, it's something worth pondering.

Tim Peters :

...

* http://www.tuxedo.org/~esr/bogofilter/

Damn -- wish I'd read that before. Among other things, Eric found a good use for Judy arrays <wink>.

It's a freaking *ideal* use for Judy arrays. Platonically perfect. They couldn't fit better if they'd been designed for this application. Bogofilter was actually born in the moment that I realized this. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Tim Peters :

[Eric S. Raymond]

...

It's a freaking *ideal* use for Judy arrays. Platonically perfect. They couldn't fit better if they'd been designed for this application. Bogofilter was actually born in the moment that I realized this.

I believe that so long as it stays in memory.

VM, dude, VM is your friend. I thought this through carefully. The size of bogofilter's working set isn't limited by core. And because it's a B-tree variant, the access frequency will be proportional to log2 of the wordlist size and the patterns will be spatially bursty. This is a memory access pattern that plays nice with an LRU pager.

But, as you mention in your manpage

startup is too slow for sites handling thousands of mails an hour

That likely makes a Zope OOBTree stored under ZODB a better choice still, as that's designed for efficient update and access in a persistent database

I'm working on a simpler solution, one which might have a Pythonic spinoff. Stay tuned. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Tim Peters :

[Eric S. Raymond]

...

VM, dude, VM is your friend. I thought this through carefully. The size of bogofilter's working set isn't limited by core.

Do you expect that to be an issue? When I built a database from 20,000 messages, the whole thing fit in a Python dict consuming about 10MB.

Hm, that's a bit smaller than I would have thought, but the order of magnitude I was expecting.

That's all. As is always the case in this kind of thing, about half the tokens are utterly useless since they appear only once in only one message (think of things like misspellings and message ids here -- about half the tokens generated will be "obviously useless", although the useless won't become obvious until, e.g., a month passes and you never seen the token again).

Recognition features should age! Wow! That's a good point! With the age counter being reset when they're recognized.

...

and the patterns will be spatially bursty.

Why? Do you sort tokens before looking them up?

I thought part of the point of the method was that you get sorting for free because of the way elements are inserted.

Else I don't see a reason to expect that, from one lookup to the next, the paths from root to leaf will enjoy spatial overlap beyond the root node.

No, but think about how the pointer in a binary search moves. It's spatially bursty, Memory accesses frequencies for repeated binary searches will be a sum of bursty signals, analogous to the way network traffic volumes look in the time domain. In fact the graph of memory adress vs. number of accesses is gonna win up looking an awful lot like 1/f noise, I think. *Not* evenly distributed; something there for LRU to weork with.

...

I'm working on a simpler solution, one which might have a Pythonic spinoff. Stay tuned.

I figure this means something simpler than a BTree under ZODB. If so, you should set yourself a tougher challenge <wink>.

What I'm starting to test now is a refactoring of the program where it spawn a daemon version of itself first time it's called. The daemon eats the wordlists and stays in core fielding requests from subsequent program runs. Basically an answer to "how you call bogofilter 1K times a day from procmail without bringing your disks to their knees" problem" -- persistence on the cheap. Thing is that the solution to this problem is very generic. Might turn into a Python framework. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Zack Weinberg :

On Wed, Aug 21, 2002 at 01:35:56AM -0400, Eric S. Raymond wrote:

...

What I'm starting to test now is a refactoring of the program where it spawn a daemon version of itself first time it's called. The daemon eats the wordlists and stays in core fielding requests from subsequent program runs. Basically an answer to "how you call bogofilter 1K times a day from procmail without bringing your disks to their knees" problem" -- persistence on the cheap.

For use at ISPs, the daemon should be able to field requests from lots of different users, maintaining one unified word list. Without needing any access whatsoever to user home directories.

I'm on it. The following is not yet working, but it's a straight road to get there.... There is a public spam-checker port. Your client program sends it packets consisting of a list of header token counts. You can send lots of these blocks; each one has to be under the maximum atomic-message size for sockets (I think that's 32K). The server accumulates the frequency counts you ship it until you say "OK, what is it?" Does the Bayes test. Ships you back a result. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Zack Weinberg :

My ISP-postmaster friend's reaction to that:

| As far it it goes, yes. How would it learn?

Your users' mailers would have two delete buttons -- spam and nonspam. On each delete the message would be shipped to bogofilter, which would would merge the content into its token lists.

I remember you said you didn't want to do base64 decode because it was too slow?

And not necessary. Base64 spam invariably has telltales that Bayesian amalysis will pick up in the headers and MIME cruft. A rather large percentage of it is either big5 or images. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Guido van Rossum :

...

And not necessary. Base64 spam invariably has telltales that Bayesian amalysis will pick up in the headers and MIME cruft. A rather large percentage of it is either big5 or images.

I'd be curious to know if that will continue to be true in the future. At least one of my non-tech friends sends email that's exclusively HTML (even though the content is very lightly marked-up plain text), from a hotmail account. Spam could easily have the same origin, but the HTML contents would be very different.

Well, consider. If your friend were to send you base64 mail, it probaby would *not* come from one of the spamhaus addresses in bogofilter's wordlists. The presence of base64 content is neutral. That means that about the only way not decoding it could lead to a false positive is if the headers contained spam-correlated tokens which decoding the body would have countered with words having a higher non-spam loading. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Guido van Rossum :

The headers usually give some clues, but based on what makes it through SpamAssassin (which we've been running for all python.org mail since February or so), base64 encoding scores high on the list of false negatives.

Noted. I'll take account of that in my planning. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Barry A. Warsaw :

You need some kind of list admin oversight or your system is open to attack vectors on individual posters.

Interesting point! -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

This brings up a couple of questions, one related to the theory behind this Bayesian spam filtering, and one about Python optimization ... apologies in advance for the long post. Tim Peters wrote:

I want to raise a caution here. Graham pulled his formulas out of thin air, and one part of the scoring step is quite dubious. This requires detail to understand.

[detail deleted]

P(S|X)*P(S|Y)/P(S) --------------------------------------------------- P(S|X)*P(S|Y)/P(S) + P(not-S|X)*P(not-S|Y)/P(not-S)

This isn't what Graham computes, though: the P(S) and P(not-S) terms are missing in his formulation. Given that P(not-S) = 1-P(S), and P(not-S|whatever) = 1-P(S|whatever), what he actually computes is

P(S|X)*P(S|Y) ------------------------------------- P(S|X)*P(S|Y) + P(not-S|X)*P(not-S|Y)

This is the same as the Bayesian result only if P(S) = 0.5 (in which case all the instances of P(S) and P(not-S) cancel out). Else it's a distortion of the naive Bayesian result.

Is there an easy fix to this problem? I implemented this in Python after reading about it on the weekend, and it might explain why my results are not quite as fabulous as the author noted (I'm getting more false positives than he claimed he was). Note that I'm not so good with the above notation; I'm more at home with plain algebraic stuff :). But the more interesting Python question: I'm running into some performance problems with my implementation. Details: The analysis stage of my implementation (I'll refer to it as "spamalyzer" for now) stores the "mail corpus" and term list on disk. The mail corpus is two dictionaries (one for spam, one for good mail), each of which contains two further dictionaries -- one is the filenames of analyzed messages (one key per filename, values ignored and stored as 0), and the other is a dictionary mapping terms to the number of occurrences. The terms list is a single dictionary mapping terms to a pair of floats (probability of being spam and distance from 0.5). My first try at this used cPickle to store these items, but loading them back in was excruciatingly slow. From a lightly loaded P3-500/128MB running Linux 2.2.x, each of these is a separate run of a benchmarking Python script: Loading corpus -------------- pickle method: good (1014 files, 289182 terms), spam (156 files, 14089 terms) in 65.190000000000 seconds. pickle method: good (1014 files, 289182 terms), spam (156 files, 14089 terms) in 64.790000000000 seconds. pickle method: good (1014 files, 289182 terms), spam (156 files, 14089 terms) in 65.010000000000 seconds. Loading terms ------------- pickle method: got 12986 terms in 3.460000000000 seconds. pickle method: got 12986 terms in 3.470000000000 seconds. pickle method: got 12986 terms in 3.450000000000 seconds. For a lark, I decided to try an alternative way of storing the data (and no, I haven't tried the marshal module directly). I wrote a function to write the contents of the dictionary to a text file in the form of Python source, so that you can re-load the data with a simple "import" command. To my surprise, this was significantly faster! The first import, of course, takes a while, as the interpreter compiles the .py file to .pyc format, but subsequent runs are an order of magnitude faster than cPickle.load(): Loading corpus -------------- [charlesc@charon spamalyzer]$ rm mail_corpus.pyc custom method: good (1014 files, 289182 terms), spam (156 files, 14089 terms) in 194.210000000000 seconds. custom method: good (1014 files, 289182 terms), spam (156 files, 14089 terms) in 3.500000000000 seconds. custom method: good (1014 files, 289182 terms), spam (156 files, 14089 terms) in 3.260000000000 seconds. custom method: good (1014 files, 289182 terms), spam (156 files, 14089 terms) in 3.260000000000 seconds. Loading terms ------------- [charlesc@charon spamalyzer]$ rm terms.pyc custom method: got 12986 terms in 3.110000000000 seconds. custom method: got 12986 terms in 0.210000000000 seconds. custom method: got 12986 terms in 0.210000000000 seconds. custom method: got 12986 terms in 0.210000000000 seconds. So the big question is, why is my naive "o = __import__ (f, {}, {}, [])" so much faster than the more obvious "o = cPickle.load (f)"? And what can I do to make it faster :). Charles -- ----------------------------------------------------------------------- Charles Cazabon GPL'ed software available at: http://www.qcc.ca/~charlesc/software/ -----------------------------------------------------------------------

[Charles Cazabon]

Is there an easy fix to this problem?

I don't know that there is "a problem". The step is dubious, but other steps are also dubious, and naive Bayes itself is dubious (the assumption that word pobabilities are independent is simply false in this application). But outside of, perhaps, quantum chromodynamics, all models of reality are more or less dubious, and it's darned hard to say whether the fudging needed to make them appear to work is lucky or principled, robust or brittle. The more gross deviations there are from a model, though, the less one can appeal to the model for guidance. In the limit, you can end up with a pile of arbitrary tricks, with no idea which gimmicks matter anymore (given enough free parameters to fiddle, you can train even a horribly inappropriate model to fit a specific blob of data exactly).

I implemented this in Python after reading about it on the weekend, and it might explain why my results are not quite as fabulous as the author noted (I'm getting more false positives than he claimed he was).

How many lines of code do you have? That's a gross lower bound on the number of places it might have screwed up <wink>.

Note that I'm not so good with the above notation; I'm more at home with plain algebraic stuff :).

It's all plain-- and simple ---algebra, it's just long-winded. You may be confusing yourself, e.g., by reading P(S|X) as if it's a complex expression in its own right. But it's not -- given an incarnation of the universe, it denotes a fixed number. Think of it as "w" instead <wink>. Let's get concrete. You have a spam corpus with 1000 messages. 100 of them contain the word x, and 500 contain the word y. Then P(X|S) = 100/1000 = 1/10 P(Y|S) = 500/1000 = 1/2 You also have a non-spam corpus with 2000 messages. 100 of them contain x too, and 500 contain y. Then P(X|not-S) = 100/2000 = 1/20 P(Y|not-Y) = 500/2000 = 1/4 This is the entire universe, and it's all you know. If you pick a message at random, what's P(S) = the probability that it's from the spam corpus? It's trivial: P(S) = 1000/(1000+2000) = 1/3 and P(not-S) = 2/3 Now *given that* you've picked a message at random, and *know* it contains x, but don't know anything else, what's the probability it's spam (== what's P(S|X)?). Well, it has to be one of the 100 spam messages that contains x, or one of the 100 non-spam messages that contains x. They're all equally likely, so P(S|X) = (100+100)/200 = 1/2 and P(S|Y) = (500+500)/500 = 1/2 too by the same reasoning. P(not-S|X) and P(not-S|Y) are also 1/2 each. So far, there's nothing a reasonable person can argue with. Given that this is our universe, these numbers fall directly out of what reasonable people agree "probability" means. When it comes to P(S|X and Y), life is more difficult. If we *agree* to assume that word probabilities are independent (which is itself dubious, but has the virtue of appearing to work pretty well anyway), then the number of messages in the spam corpus we can expect to contain both X and Y is P(X|S)*P(Y|S)*number_spams = (1/10)*(1/2)*1000 = 50 Similarly the # of non-spam messages we can expect to contain both X and Y is (1/20)*(1/4)*2000 = 25 Since that's all the messages that contain both X and Y, the probability that a message containing both X and Y is spam is P(S | X and Y) = 50/(50 + 25) = 2/3 Note that this agrees with the formula whose derivation I spelled out from first principles: P(S|X)*P(S|Y)/P(S) --------------------------------------------------- = P(S|X)*P(S|Y)/P(S) + P(not-S|X)*P(not-S|Y)/P(not-S) (1/2)*(1/2)/(1/3) 2 -------------------------------------- = - (1/2)*(1/2)/(1/3) + (1/2)*(1/2)/(2/3) 3 It's educational to work through Graham's formulation on the same example. To start with, P(S|X) is approximated by a different means, and fudging the "good count" by a factor of 2, giving P'(S|X) = (100/1000) / (100/1000 + 2*100/2000) = 1/2 and similarly for P'(S|Y). These are the same probabilities I gave above, but the only reason they're the same is because I deliberately picked a spam corpus size exactly half the size of the non-spam corpus, knowing in advance that this factor-of-2 fudge would make the results the same in the end. The only difference in what's computed then is in the scoring step, where Graham's formulation computes P'(S | X and Y) = (1/2)*(1/2)/((1/2)*(1/2)+(1/2)*(1/2)) = 1/2 instead of the 2/3 that's actually true in this universe. If the corpus sizes diverge more, the discrepancies at the end grow too, and the way of computing P(S|X) at the start also diverges. Is that good or bad? I say no more now than that it's dubious <wink>.

But the more interesting Python question: I'm running into some performance problems with my implementation. Details:

English never helps with these. Whittle it down and post actual code to comp.lang.python for help. Or study the sandbox code in the CVS repository (see the Subject line of this msg) -- it's not having any speed problems.

Tim Peters :

P(S|X)*P(S|Y)/P(S) --------------------------------------------------- P(S|X)*P(S|Y)/P(S) + P(not-S|X)*P(not-S|Y)/P(not-S)

This isn't what Graham computes, though: the P(S) and P(not-S) terms are missing in his formulation. Given that P(not-S) = 1-P(S), and P(not-S|whatever) = 1-P(S|whatever), what he actually computes is

P(S|X)*P(S|Y) ------------------------------------- P(S|X)*P(S|Y) + P(not-S|X)*P(not-S|Y)

This is the same as the Bayesian result only if P(S) = 0.5 (in which case all the instances of P(S) and P(not-S) cancel out). Else it's a distortion of the naive Bayesian result.

OK. So, maybe I'm just being stupid, but this seems easy to solve. We already *have* estimates of P(S) and P(not-S) -- we have a message count associated with both wordlists. So why not use the running ratios between 'em? As long as we initialize with "good" and "bad" corpora that are approximately the same size, the should work no worse than the equiprobability assumption. The ratios will correct in time based on incoming traffic. Oh, and do you mind if I use your algebra as part of bogofilter's documentation? -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Tim Peters :

a. There are other fudges in the code that may rely on this fudge to cancel out, intentionally or unintentionally. I'm loathe to type more about this instead of working on the code, because I've already typed about it. See a later msg for a concrete example of how the factor-of-2 "good count" bias acts in part to counter the distortion here. Take one away, and the other(s) may well become "a problem".

I was thinking of shooting that "goodness bias" through the head and seeing what happens, actually. I've been unhappy with that fudge in Paul's original formula from the beginning.

b. Unless the proportion of spam to not-spam in the training sets is a good approximation to the real-life ratio of spam to not- spam, it's also dubious to train the system with bogus P(S) and P(not-S) values.

Right -- which is why I want to experiment with actually *using* the real life running ratio.

c. I'll get back to this when our testing infrastructure is trustworthy. At the moment I'm hosed because the spam corpus I pulled off the web turns out to be trivial to recognize in contrast to Barry's corpus of good msgs from python.org mailing lists:

Ouch. That's a trap I'll have to watch out for in handling other peoples' corpora. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

| As far it it goes, yes. How would it learn? I have some ideas about how you could hook this into Mailman to do community/membership assisted learning. Understanding that people will be highly motivated to inform you about spam but not about good messages, you essentially queue a copy of a random sampling of messages for a few days. Members can let the list admin know about leaked spam (via a url or -spam address, or whatever) and after the list admin verifies it, this trains the system on that spam. If no feedback on a message happens after a few days, you train the system on that known good message. You need list admin verification to avoid attack vectors (I get mad at Guido so I -- a normal user -- label all his messages as spam). | On a more mundane note, I'd like to see decoding of base64 in it. | | (Oh, and on a blue-sky note, has anyone taken up Graham's suggestion | of having one of these things that looks at word pairs instead of | words?) | | It's neat that ESR saw immediately that the daemon should be | self-contained, no access to home directories. SpamAssassin doesn't | have a simple way of doing that, and [ISP] is modifying it to have | one -- and you wouldn't believe the resistance to the proposed | changes from some of the SA developers. Some of them really seem | to think that it's better and simpler to store user configuration | in a database than to have the client send its config file to the | server along with each message.

...

...

...

...

"ZW" == Zack Weinberg writes:

ZW> I remember you said you didn't want to do base64 decode ZW> because it was too slow? But there might be some interesting, integrated ways around that. Say for example, you take a Python-enabled mail server, parse the message into its decoded form early (but not before low level SMTP-based rejections) and then pass that parsed and decoded message object tree around to all the other subsystems that are interested, e.g. the Bayes filter, and Mailman. You can at least amortize the cost of parsing and decoding once for the rest of the lifetime of that message on your system. I think we have all the pieces in place to play with this approach on python.org. -Barry

[Tim]

...

Do you expect that to be an issue? When I built a database from 20,000 messages, the whole thing fit in a Python dict consuming about 10MB.

[Eric S. Raymond]

Hm, that's a bit smaller than I would have thought, but the order of magnitude I was expecting.

It's even smaller than that <wink>. The dict here maps strings to instances of a Python class (WordInfo). The latter uses new-in-2.2 __slots__, and those give major memory efficiences over old-style classes, but there's still subtantial memory overhead compared to what's possible in C. In addition, there are memory overheads for the Python objects stored in the WordInfo instances, including a Python float object in each record recording the time.time() of last access by the scoring method. IOW, there are tons of memory overheads here, yet the size was still minor. So I have no hesitation leaving this part in Python, and coding this part up was a trivial finger exercise. You know all that, though! It makes your decision to use C from the start hard to fathom.

... Recognition features should age! Wow! That's a good point! With the age counter being reset when they're recognized.

For concreteness, here's the comment from the Python code, which I believe is accurate: # (*)atime is the last access time, a UTC time.time() value. It's the # most recent time this word was used by scoring (i.e., by spamprob(), # not by training via learn()); or, if the word has never been used by # scoring, the time the word record was created (i.e., by learn()). # One good criterion for identifying junk (word records that have no # value) is to delete words that haven't been used for a long time. # Perhaps they were typos, or unique identifiers, or relevant to a # once-hot topic or scam that's fallen out of favor. Whatever, if # a word is no longer being used, it's just wasting space. Besides the space-saving gimmick, there may be practical value in expiring older words that are getting used, but less frequently over time. That would be evidence that the nature of the world is changing, and more aggressively expiring the model for how the world *used* to be may speed adaptation to the new realities. I'm not saving enough info to do that, though, and it's unclear whether it would really help. Against it, while I see new spam gimmicks pop up regularly, the old ones never seem to go away (e.g., I don't do anything to try to block spam on my email accounts, and the bulk of the spam I get is still easily recognized from the subject line alone). However, because it's all written in Python <wink>, it will be very easy to set up experiments to answer such questions. BTW, the ifile FAQ gives a little info about the expiration scheme ifile uses. Rennie's paper gives more: Age is defined as the number of e-mail messages which have been added to the model since frequency statistics have been kept for the word. Old, infrequent words are to be dropped while young words and old, frequent words should be kept. One way to quantify this is to say that words which occur fewer than log2(age)-1 times should be discarded from the model. For example, if “baseball” occurred in the 1st document and occurred 5 or fewer times in the next 63 documents, the word and its corresponding statistics would be eliminated from the model’s database. This feature selection cutoff is used in ifile and is found to significantly improve efficiency without noticeably affecting classification performance. I'm not sure how that policy would work with Graham's scheme (which has many differences from the more conventional scheme ifile uses). Our Python code also saves a count of the number of times each word makes it into Graham's "best 15" list, and I expect that to be a direct measure of the value we're getting out of keeping a word ("word" means whatever the tokenizer passes to the classifier -- it's really any hashable and (for now) pickleable Python object). [on Judy]

I thought part of the point of the method was that you get sorting for free because of the way elements are inserted.

Sure, if range-search or final sorted order is important, it's a great benefit. I was only wondering about why you'd expect spatial locality in the input as naturally ordered.

... No, but think about how the pointer in a binary search moves. It's spatially bursty, Memory accesses frequencies for repeated binary searches will be a sum of bursty signals, analogous to the way network traffic volumes look in the time domain. In fact the graph of memory adress vs. number of accesses is gonna win up looking an awful lot like 1/f noise, I think. *Not* evenly distributed; something there for LRU to weork with.

Judy may or may not be able to exploit something here; I don't know, and I'd need to know a lot more about Judy's implementation to even start to guess. Plain binary search has horrid cache behavior, though. Indeed, most older research papers on B-Trees suggest that binary search doesn't buy anything in even rather large B-Tree nodes, because the cache misses swamp the reduced instruction count over what a simple linear search does. Worse, that linear search can be significantly faster if the HW is smart enough to detect the regular address access pattern of linear search and do some helpful prefetching for you. More recent research on B-Trees is on ways to get away from bad binary search behavior; two current lines are using explicit prefetch instructions to minimize the stalls, and using a more cache-friendly data structure inside a B-Tree node. Out-guessing modern VM implementations is damned hard. With a Python dict you're likely to get a cache miss per lookup. If that's a disaster, time.clock() isn't revealing it <wink>.

... What I'm starting to test now is a refactoring of the program where it spawn a daemon version of itself first time it's called. The daemon eats the wordlists and stays in core fielding requests from subsequent program runs. Basically an answer to "how you call bogofilter 1K times a day from procmail without bringing your disks to their knees" problem" -- persistence on the cheap.

Thing is that the solution to this problem is very generic. Might turn into a Python framework.

Sounds good! Just don't call it "compilerlike" <wink>.

...

...

...

...

"NS" == Neil Schemenauer writes:

NS> Are you planning to check this into the sandbox? http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/python/nondist/sandbox... -Barry