Re: Some questions

On Sat, May 23, 2009 at 1:00 AM, Steve <[email protected]> wrote:
> Hello all
>
> I don't know if the list is the right place to ask, but I try.

Right place. This is a significant part of crm114 anyway. (Well, a few
might argue this is more a crm114-developers@... question, but what
the hey.)

> I would like to understand better how SBPH and OBF is working. According to the CRM114 documentation I have made the following table:
>
> W = Weight
> C = Complexity or matched words
> S = Sparse
> F = Features
>
> SBPH:
> ----+---+---+---------------------------------
>  W | C | S | F
> ----+---+---+---------------------------------
>  1 | 1 | 0 | jumped
>  4 | 2 | 0 | fox jumped
>  4 | 3 | 1 | brown <skip> jumped
>  16 | 3 | 0 | brown fox jumped
>  4 | 4 | 2 | quick <skip> <skip> jumped
>  4 | 4 | 2 | quick <skip> fox jumped
>  16 | 4 | 1 | quick brown <skip> jumped
>  64 | 4 | 0 | quick brown fox jumped
>  4 | 5 | 3 | the <skip> <skip> <skip> jumped
>  16 | 5 | 2 | the <skip> <skip> fox jumped
>  16 | 5 | 2 | the <skip> brown <skip> jumped
>  64 | 5 | 1 | the <skip> brown fox jumped
>  16 | 5 | 2 | the quick <skip> <skip> jumped
>  64 | 5 | 1 | the quick <skip> fox jumped
>  64 | 5 | 1 | the quick brown <skip> jumped
> 256 | 5 | 0 | the quick brown fox jumped
> ----+---+---+---------------------------------
>
> For calculating the weight I used the following OpenOffice.org Calc formula:
> =2^(2*(Complexity-Sparse-1))

Check.


> OSB:
> -----+---+---+---------------------------------
>   W | C | S | F
> -----+---+---+---------------------------------
> 3125 | 2 | 0 | fox jumped
>  256 | 3 | 1 | brown <skip> jumped
>  27 | 4 | 2 | quick <skip> <skip> jumped
>   4 | 5 | 3 | the <skip> <skip> <skip> jumped
> -----+---+---+---------------------------------
>
> For calculating the weight I used the following OpenOffice.org Calc formula:
> =(5-Sparse)^(5-Sparse)
> I used 5 as the window size.

Check. Weights is the wrong way around though; while those have been
changing over the years of development, or so it seems from the source
code, the addagium is to always have larger weights for 'longer'
(wider) matches, i.e. larger weights for sparse bigram mixes which
span _more_ tokens. Note that WINNOW and the other Bayesian filters
(except MARKOVIAN) follow this approach.

So your table would look like this:

> OSB / OSBF / WINNOW:
> -----+---+---+---------------------------------
>   W | C | S | F
> -----+---+---+---------------------------------
>    4 | 2 | 0 | fox jumped
>   27 | 3 | 1 | brown <skip> jumped
>  256 | 4 | 2 | quick <skip> <skip> jumped
> 3125 | 5 | 3 | the <skip> <skip> <skip> jumped
> -----+---+---+---------------------------------

so the formula for the weights would need to be flipped as well: W =
C**C  (== C ^ C)


The bit to remember is (though I haven't checked the latest release
yet, so things may be different there):

Markovian (SBPH) uses an 'all permutations' bitpattern (where latest
token is ALWAYS included in the mix) to mix the N tokens in the
'window' where N is the window 'length' of 5.
As a bitpattern, it looks like this (note that latest token is AT
LEFT, oldest is AT RIGHT):

10000
11000
10100
11100
10010
11010
10110
11110
10001
11001
10101
11101
10011
11011
10111
11111

while OSB and all the other 'more modern' bayesian classifiers in the
crm114 collective use the 'sparse bigram' approach, which discards the
notion of 'all permutations' as tests in the past turned out this
reduced set delivered a performance which was comparable (some results
are better, some a little worse. Depends on your test rig and a
zillion other factors)
In bitpattern-speech it looks like this:

11000
10100
10010
10001

I always remember these as 'bitcounter' for the top one (as it's
exactly like a bitcounter of width N-1 with a prefixed '1') and
'shifting/sliding 1' for the bottom one as that's just a '1' bit being
shifted left plus a '1' prefixed. Which tells how these can be
extended for larger window N sizes.


> Is the above table right? If not, what errors have I made?

All correct AFAICT, except the table weights for the latter. A- score ;-)


> If I understand the documentation right, then
> the weight is used to calculate the probability
> for a class (either spam or ham). Can one
> explain me what role the count of a feature
> inside the CRM Sparse Spectra file plays?
> I mean assuming the feature "fox jumped"
> and assuming that feature was found 500
> times in the class ham and 100 times in the
> class spam. How does that 500 and/or 100
> count play a role in calculating the
> probability? Does that even play a role or is
> it unimportant how many times a features
> has been learned before?


Oy. Okay, things will become a bit fuzzy while answering this. First
line: check.
Ad count: check. It plays a role and works similar to (but not exactly
like) a 'feature weight'.

Ad number of training rounds: those have impact on the stored 'weight
count' (or better: 'weight _factor_') value stored with each feature
hash, and thus impacts almost all modes of classification: every mode
where this weight factor is taken into account, number of training
rounds becomes 'visible' as an influence on pR and/or other
classification results.


Remember that 'wider matches' should have higher impact (the idea here
is that wider matches cover more area in the match and should (a) be
rarer and (b) when matching signify a match for an increasingly
substantial part of a _sentence_, and it's something akin to
'sentences' we'd like to compare (that's the markovian chain bit added
into these basically bayesian filters: markovian/OSB/OSBF/WINNOW)

So upon a 'hit' (i.e. a 'match') both 'learn count' (that count
attribute stored in the CSS database, one such count for each stored
hash) and 'feature weight' both influence the probability calculation.
I call it 'influence' because here comes the fuzzy in the forehead
(sorry, been nourishing the brain on Zappa): it highly depends on the
classifier used HOW these are used.
Let's call this the 'mixing function' of the classifier. This is where
most of the experimenting takes place in developing new bayesian
classifier variant (check the crm114 source code to see where the most
'previous tested' commented-out code snippets reside... Another spot
is in the weights section, where various 'weight distributions' have
apparently been tested by Bill.)

Right. Mixing function. I didn't pick that name arbitrarily, as in
cryptographical encryption algorithms, that's the name for a piece of
the action where some of the most important voodoo takes place. Same
here. ;-)
For example, the Markovian multiplies the hitcount for each match with
the weight, then calculates a progressing probability per feature hash
tested from the weighted hitcount values.
In case that last line produces a WTF: it's shorthand for this:

loop A:
1) pick up new token and slide into the token window (size 5)
2) take that SBPH (or OSB or ...) table (= 'matrix') and apply it to
produce features.
(See further below for how these can be 'position dependent' or
'position independent', etc.)
which gives us for SBPH _matrix_height_ features per token, i.e. 16
features to check.

Thus loop A would produce about 5..16*T features for an input text
consisting of T tokens ('words').

total_hits = 0
Loop B: for each feature...:
1) init counters, etc.: hits_so_far=0

2) loop B.2: for each 'class' (~ each loaded CSS database, but
necessarily when the CSS format changes in the future)

2.1) check if hit for feature (== matches feature with trained content
for this class?!)

2.2) if yes:
 hits[class] = trained_count_from_CSS * feature_weight;
 hits_so_far += hits[class];

3) recalc probability per class: depending on compile-time configured
settings, such as STATIC_LOCAL_PROBABILITIES, calculate a new
probability:
P_local[class] = 0.5 + (hits[class] -
hits_for_any_other_class_for_this_feature) /
compile_time_weight_factor_for_scaling_P * (hits_so_far + 1)
where the +1 is to prevent fatal division by zero,
hits_for_any_other_class_for_this_feature == hits_so_far - hits[class]
because hits_so_far is the sum of all weighted hits for this feature
spanning all classes, thanks to loop B.2, and
compile_time_weight_factor_for_scaling_P is named 'LOCAL_PROB_DENOM'
in the code.

4) calculate a **normalized** P (== spanning 0..1 range) by mixing in P_local[]:
sum = sum(P_local[i] * P[i], i E all_classes)
P'[class] = P_local[i] * P[i] / sum

so that the new P[class] will be within 0..1 range and sum(P[class]) = 1

When all features have thus been tested, the pR is calculated as a
log10 operation applied to these P's: classes are grouped in either
'success' or 'fail' collection (the | pipe symbol in the crm classify
invocation separating the CSS files!) and then
P_success = sum(P[i], i E success_classes)
P_fail = 1 - P_success

so that

pR = log10(P_success) - log10(P_fail)

In the source code P_sucess ~ 'accumulator' and P_fail ~ 'remainder'
and the P_fail calculation is done a little differently as Bill
dropped in a few bits and pieces to prevent division by zero and
log10(0) fatal failures from happening, thus ever so slightly
destroying the exact sum=1 normalization of the P[] collection, but
that's for nit pickers.


This is the 'mixing function' of the MARKOVIAN classifier.
Inspect the source code for each classifier and note that each of them
largely differs only in this area only: the 'mixing function' they
employ differs from each other.

WINNOW, for instance, has a few noticable differences from the above:

a) next to keeping track of the _weighted_ hitcount as a single entity
per class, WINNOW tracks two values individually:

- number of hits (in totalhits[]; the other: 'hits[]' is only for
diagnostics); these are NOT weighted in ANY way!

- number of weighted hits (totalweights[]): these take the training
counts per matched hash into account by counting these training counts
for each hit.

b) note that WINNOW does not care at all about the 'feature weight'
which accompanies each calculated feature hash for the current
document under test!

c) P[] is not calculated progressively, but only at the end. This is
not only saving quite a bit of calculation cost that way, but also has
a (almost negligible) effect on the pR end result as the number of
floating point errors introduced due to calculations is greatly
reduced as well: number of operations leading to the end result is cut
down up to 500K fold (500K being the maximum number of inspected
feature hashes: BAYES_MAX_FEATURE_COUNT)

d) the weighted hits now include a '1.0' weight for each UNmatched
feature. This is necessary as the 'trained weight' is calculated
differently for WINNOW when compared to MARKOVIAN: in MARKOVIAN, the
training just adds +1 to the count attribute for the given feature
hash in the CSS file (thus having an absolute maximum range of
0..+MAXINT for each feature in there) while WINNOW _multiplies_ the
existing weight with a 'sense' factor (OSB_WINNOW_PROMOTION /
OSB_WINNOW_DEMOTION) -- which incidentally tells us that <refute>
cannot 'undo' a previous training _exactly_. With WINNOW, _all_
weights start out as a factor == 1.0 and trained features multiply
with said factor to increase (or in case of <refute> DEcrease) that
weight factor.

e) for the specifics of the P[] calculation, see the source code. The
code is slightly complicated by the fact that the Chi Square and
'regular' P calculation elements are intertwined.

Notes: P[] ends up in 'classifierprs[]'; the 'regular' form does NOT
use that scaling factor LOCAL_PROB_DENOM for local probability
calculations
There's also no need for that extra +1 in the divisor any more as the
totalweight values and their sum will never ever become 0 as those are
all based on 1.0-based multiplication instead of 0.0-based addition.
The source was a mess as things are calculated at the end in two
different ways and there's a few chunks of dead code in there as well.
Alas, a work in progress. Haven't checked if this has been cleaned up
in the latest release. I hope (and assume) this has been improved
along the way.


I haven't covered training rather spotty, but that piece of the code
is much simpler to grok for the bayesian/markovian classifer, so see
the code for how those are done. Most just count +1 for each feature
trained (note WINNOW though!!!) with sprinkles on top: if <unique> was
specified, for instance, the code would prevent training a recurring
feature hash H from being 'trained' into the CSS more than once for
each trained document.


>
> What happens when CRM114 is saving the data inside the CSS file? Does it save the feature "quick <skip> <skip> jumped" as a concatenated hash value (replacing the <skip> with some kind of delimiter) or does it save just one hash (for the above feature) and at run time after parsing and hashing a message (and therefore knowing the complexity and sparse of a feature) it compares the calculated (in memory) feature with the one found in the CSS file?
>
> I mean:
> Assuming the feature: "quick <skip> <skip> jumped"
> Assuming hashing "quick" would be: "1111111111111111"
> Assuming hashing "jumped" would be: "2222222222222222"
> Assuming hashing the whole feature would be: "12345678ABCDEF09"
>
> Does CRM114 now save "12345678ABCDEF09" or does it save "1111111111111111" + some kind of delimiter for <skip> + some kind of delimiter for <skip> + "2222222222222222"?

Answer: crm114 saves feature hashes. That is: it saves "12345678ABCDEF09".

This is why is is EXTREMELY BAD FORM to mix trainings based on
<unigram> and non-unigram into the same CSS file, to give one example:
since that flag has significant impact on how feature hashes are
derived from tokens, you end up with disparate feature hashes for each
'style', where feature hash matches are hence meaningless.
That's the long form of saying:

  Always train your CSS file with the same settings/flags, such as
<unigram>, etc. as you apply to your classifications.

which is inacurate when it comes to things such as <unique>, but
that's another load of detail and for another day.


> Another thing I don't understand is this slighting window of 5. Assuming the following content: 1 2 3 4 5 6 7 8 9 0
> Does the window now slide like this: "1 2 3 4 5" and then "6 7 8 9 0"
> Or does it overlap: "1 2 3 4 5" and then "2 3 4 5 6" and then "3 4 5 6 7 8" and then "4 5 6 7 8 9" and then "5 6 7 8 9 0" and it quits because it can not allocate again 5 words.
> Or how is this slighting window working?

Sliding windows are generally 'overlapping'  -- for the electrics
folks listening in: it's rather acting like a serially loaded shift
register (with parallel read)
Hence you 'shift&load' that '6', going from '1 2 3 4 5' to '2 3 4 5 6'
as a result and it's a new round, folks.   :-)


> Sorry for all the stupid questions, but I really would like to better understand how the things are working inside CRM114. If the list is the wrong place to ask that questions and you know where I could ask them, then just let me know. Or maybe you know some document better describing how things work in CRM114 then just let me know.


I didn't see anything stupid in there at all. You've already 'decoded'
quite a bit of the inner workings of the bayesian/markovian
classifiers so far, so thumbs up!


In case the math is obscuring the big picture, think of these
classifiers like this:

basically each of them is counting hits, no matter the frills, such as
feature weights. And at the end, the verdict is based on comparing (~
ratio of) your class' hitcount with the other classes': in your
example of 500 ham versus 100 spam hits (and only two classes: ham &
spam), you'd have a winner for the ham side as that number is higher
than the spam hitcount.

A lot of the extra frills, such as the mixing function, are there to
manipulate the result curve in various ways. Other extras are there to
signify differences in feature 'perception': feature weight is there
to propagate a notion of 'difference in importance' for various
features derived from your input text: features derived from longer
[parts of] input sentences should, upon match, weigh in more than
'short' features. Which makes sense, right?
The other major factor: the stored training count/weight factor,
stored with each trained feature hash, has a similar 'importance'
goal. In this case the factor is meant propagate the notion that
features which apparently occured more often in the trained material
should have a bigger impact on the end result than those features
which occur only seldom in the previously trained material.

Some classifiers offer a 'chi square' attribute, which is just another
style to calculate those P numbers, which sometimes are probabilities
(i.e. values where sum(P)=1), sometimes a value representing an
approximation of the probability. This is where the classifiers
differ.


For myself, I always think of the 'mixing function' (which is not a
'function' in the pure mathematical sense) as an 'equalizer' sitting
in a audio/sound chain: you can get yourself a bit more bass (or
less), numb the trebble if you like a more 'old' sound, push up the
mid range to bring up the voices, etc., but in the end you are stuck
with what you send in: if your recording is lacking, no matter how
fancy your EQ you won't get a 'crisp' output, ever.
Same here: one of the hardest things to accomplish is 'feeding' the
classifier properly. This is the 'tokenization' of the input and
'messing' with that (i.e. using different regexes for train/classify)
in crm114 can have significant impact for particular inputs, e.g.
email: that's why some other packages out there employ specific email
header 'munching', i.e. a different tokenization process for mail
headers and content respectively.
In crm114, you can script many of such 'preprocessing' things.
Imagine you have audio input and wish to apply crm114 to that for,
say, detecting speech in an signal which is otherwise 'just noise',
but with artifacts you don't want to register. Can't simply push in
the sampled audio data then, but you'll specific preprocessing
equipment, e.g. a FFT, to get anything that _might_ help to arrive at
_usable_ tokens.

Text is simple in comparison: 'chop at the whitespace' is a good start
for a tokenization rule (and that's what crm114 does out of the box);
for mail headers or other texty inputs (PDFs, XML data, ...), this
'chop at spaces' is probably insufficient. It may not even suffice for
'basic text', because the 'chop at whitespace' completely ignores the
punctuation, which becomes part of the word tokens due to the 'chop at
white' rule.
Hence, you need to teach the bugger there is a blue pill, AND a blue
pill at the end of a line, i.e. the token blue-pill-with-extra-dot is
completely missed by the classifier, until you train that one as well.
Now both [blue bill] and [blue pill with a dot] have a 'weight' of ~
1.0, so how can we improve the tokenizer regex so that the same
training would give us, say, one feature with, consequently a weight
factor of ~ 2.0, thus dialing up the importance/impact of this quite
relevant word in our pR numbers?
Say what if we discard punctuation?
Or treat punctuation as separate token 'words' and let the markovian
chain mixing do it's job? (Note that this is sneaky as now, when you
look at 'words' (which are not equal to 'tokens' anymore), you get a
varying 'effective' chain/window length this way, resulting a token
mixes which slightly differ at end-of-line, compared to 'within
sentence', resulting a dual set of feature hashes to be trained
anyway. But sometimes this can be useful in its own way.)
What if the text is fed through a phonetic filter before tokenizing?
(such as Metaphone)
This 'how do I tokenize my input' question is No. 1 to test for the
input collection you wish to classify. After that it's playing with
the 'equalizer' when you stick with Bayesian classifiers.


The other classifiers (such as Hyperspace or Neural Net) use
completely different approaches, hence may produce better (or worse!)
results for your input token stream, as those are not a simple 'ratio'
check any more.


-- 
Met vriendelijke groeten / Best regards,

Ger Hobbelt

--------------------------------------------------
web:    http://www.hobbelt.com/
        http://www.hebbut.net/
mail:   [email protected]
mobile: +31-6-11 120 978
--------------------------------------------------

------------------------------------------------------------------------------
Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
is a gathering of tech-side developers & brand creativity professionals. Meet
the minds behind Google Creative Lab, Visual Complexity, Processing, & 
iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
Group, R/GA, & Big Spaceship. http://www.creativitycat.com