Re: crm filter cleanup on productive system

On Sun, Feb 22, 2009 at 9:29 PM, Frank Doege <fdoege-zZ82ZiX1S8lUvkYWv5dGcgC/[email protected]> wrote:
>> > 1) you have a retina: in the CRM114 implementation this is 8192 slots
>> > (called the "retina") which each get the number of occurrences that a
>> > 32-bit OSB hash feature occurred that _just happened_ to have the low
>> > order 13 bits equal to the slot number (this number is likely to
>> > change in the future, and the smallness of this number compared is one
>> > reason why large texts tend to break the neural net; when all of the
>> > slots have equal counts, there's nothing to learn!).
>
> I understood it like this:
> We have 8192 starting points called a retina. Now we take a sentence or
> question or just any data input, split it up and for each unit we
> generate a 32bit OSB hash.

Yup.

Note that input has arbitrary length; after tokenization you end up
with M hashes where theoretically (given current implementation): M e
{0..max_int - 1}. In actual practice, you'll get anywhere between
zero(0) and 500K hashes for generic systems and 0..20K hashes (plucked
the latter number out of thin air, based on the input length limit
default in mailfilter.cf, average word size guestimate in email and
OSB-style word-to-hash expansion ratio).
All those hashes are mapped onto the retina.


> Now i dont understand this part with the low order 13 bits equal to the
> slot number.

Simple: the hashes are converted into retina slot indexes using the formula

   index = hash MOD retina_size

and given a (default) retina size of 8192, that's the same as taking
only the lower 13 bits of each hash value.


>> > 2) You then have a bunch (8 or 16, also likely to change) of summing
>> > junctions (called "first layer neurons) which each have an independent
>> > weight for all 8192 input slots (that's 64K input weights).  The
>> > output of these summing junctions then is mapped by a nonlinear
>> > function called a sigmoid, which looks like a tan(x) curve rotated
>> > about the 45-degree line.
>
> After that retina is filled with the data, we connect each slot of these
> 8192 with 8 or 16 junctions, we build a kind of network here. Each
> connection has an own weight, at the beginning i assume the weight is
> randomized to give it any reasonable start. The "first layer neurons"
> are the first stage of "hidden units" and the 8192 retina slots are the
> input units right ? Now how and where do you apply the first sigmoid
> function ? You take all the data coming from the retina weight it by the
> weight for the given path and put it together with the sigmoid function ?

Well, the current implementation (see also: src/crm_neural_net.c) uses
full size crossbars between the layers, i.e. you have layers and
crossbars like this:

               retina (8192)
Win (xbar: 8192x8)
               first (8)
Whid (xbar: 8x16)
               hidden (16)
Wout (xbar: 16x2)
               output (2)

with (default) sizes in parentheses.

(Note: default sizes can be adjusted using the crm114 '-s' or '-S'
commandline argument; the conversion factor is a little wicked though:
        first_layer_size = (int)sqrt((int)(sparse_spectrum_file_length / 1024));
which means you'd have to spec '-S 16' for the default, which is
first_layer_size==8)


And see crm_neural_net.c for the sigmoid function, which is here (for
one layer):

                    nn->delta_output_layer[neuron] =
                            (nn->delta_output_layer[neuron] //  target - actual
                             -  nn->output_layer[neuron])
                            * (1.0 - nn->output_layer[neuron]) // 1 - actual
                            * nn->output_layer[neuron];       // actual

which is, when looking at it with a wee droppa Smirnov assistance,
similar to a tan(x+pi/2)

And, yes, it might not be immediately detectable in the source as it is. Alas.


>> > 4) One more layer, with just two summing-junction neurons and sigmoids
>> > gives us the output - the [0]th neuron is the "in class" signal, and
>> > the [1]th neuron gives the "out of class" signal.
>
> if i understand right these are the output units, which in this case can
> produce yes or no.

yup, on a per document basis. The CSS databases are collections of
trained documents. (See also: crm_neural_net.c)

>> > Training is a bit harried; you have to do a gradient descent from
>> > the desired output to the mapped inputs; there's some calculus
>> > involved, as well as a bit of luck (convergence is NOT gauranteed!)
>> > You also have to initialize with small random numbers because
>> > otherwise, the standard training algorithms will be "stuck on center"
>> > forever and you get no training at all.
>
> it would be nice if you could also explain this if you got some
> freetime, i know its complicated
>
> What kind of network have you implemented ? i feel its a kind of pattern
> associator network with 2 extra hidden layers. therefore for learning
> you use some kind of delta or hebb rule learning ?

See crm_neural_net.c: allegedly a Kohonen network, no Hebb training,
but I have to take that one on faith myself until I take the time to
read through certain dusty volumes on my shelf again.
How the training works _exactly_ is beyond my forte right now (it's in
those dusty volumes but I'd rather not reach for that upper shelf for
fear of giving myself brainingitis), but it kinda sorta comes down to
the digital equivalent of a nice physics show, where you hide a couple
of magnets under a flat piece of paper, then sprinkle iron dust on
top: by jittering the paper the iron filings clump together and show
the field strength / lines as brown on white.
(That's why you need the (continual) injection of (small) random
values; it's the equivalent of jittering the paper to make the iron
dust move.)



(And an attempt to partially answer my personal exercise 3b: for one
[implicit assumption in the code], the width of the retina limits the
number of distinguishable features in the input, as the 'index = hash
MOD retina' mapping function mixes features which produce an identical
*index*. Since you don't know which features are significant and which
aren't, there's no way to tell if a significant feature will mix with
other [in]significant features, where the occurrence of such an
insignificant feature can, in a later classify run, inadvertently
trigger a neuron as if it were the significant feature.
Worst case here is when two (or more) significant features map onto a
the same index, where those features are significant for detecting
different classes.
Given the small(?) value of 8192, one /must/ assume several features
of varying significance are mixed into the same retina index, and that
implies that the risk a neuron will be inadvertently fired (misfire)
is rather 'large', for a (yet undetermined) amount of large. I.e. it's
a game of trail & fail to see if the given retina size (*and* the
MODULO hash mapping function there!) are 'sensitive' enough to keep
the amount of misfires acceptable for your expected input set. Ergo:
will the NN learn the right thing despite these setbacks? Testing will
give an indication of the answer, but no guarantee.
Which says it all: you got to test this one with your own input
collection in order to be able to say something reasonably 'solid'.
Public corpuses can help to set this thing up, but the real tuning has
to happen based on your own data set. But that last bit is just [my]
opinion.)

Oh, and by the way: both GerH and vanilla releases have two bugs
lurking in that NN code.



So far, my two cents. Signing off.


PS: You may want to inspect crm_neural_net.c, but chances are high
your first impression is 'uhhhhhh?' (at least that was mine ;-)) )

-- 
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
--------------------------------------------------

------------------------------------------------------------------------------
Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
-OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
-Strategies to boost innovation and cut costs with open source participation
-Receive a $600 discount off the registration fee with the source code: SFAD
http://p.sf.net/sfu/XcvMzF8H