Re: crm filter cleanup on productive system

   From: Ger Hobbelt <[email protected]>

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

Yes.  Note that the hashes are not "dense" - you might have a dozen
instances of hash 4320 but none of either 4319 or 4321.


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

Yep.  Note that one of the things I'm working over on the NN is changing
that, so that we get better separability of features.

Consider, right now a feature is really of the form xxxx[0/1]NNN,
where the first 19 bits are _thrown away_.  Thus, any pair of 
features that differ only in the first 19 bits will not be separable
by any neuron, anywhere.

The fix is to keep the features separated.  Ideally, we'd have the 
retina be 2^32 features long, but that would simply not work at all
on X86, and work very slowly on X64.  

So, I'm working on methods such as:

    retina_slot = feature_hash MOD ( retina_size - neuron_number)

(and other ideas!) to cause a particular 32-bit feature to end up
on a different retina slot for each input neuron.

Will it work?  Who knows- neural networks are wierd.

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

Don't assume those values are optimal.  I'm playing with them.

   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)

Well, arctan (x+pi/2).  And, that's not just the
sigmoid function, that's the entire update rule.

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

There's actually a good reason for that funky formula.  Remember
I mentioned there's calculus involved?

The reason is that gradient descent uses the local derivative of
the error function at each point to decide which way and how
far to adjust each weight.  

See line 1432: The derivative of the sigmoid we use (specifically,
the "logistic" sigmoid) is just (1 - (sigmoid(x)) / sigmoid(x).  
Multiply this result times the amount of error and that tells you 
how much to correct each weight in the huge weight arrays.

Of course, this is like using Newton's method- if the 
function varies fast enough underneath you, Newton's method goes unstable.


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

Well, some folks claim that it's Kohonen (note that Kohonen himself
says "well, I prefer to to use Kohonen for the SOM (Self-Organizing
Map) network").  So, call it what you will.  If you can find a better
term for it, please let me know.

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

No, not really.  The initial condition of small random values is
theoretically all that's needed.  I just have found that THIS
PARTICULAR system works better on text with a little bit more than
that, kind of like a Boltzmann machine than a pure neural net
(although I suppose this particular implementation has elements of
both.)

What's really happening is that the errors are being back-propagated
through the system, by apportioning in radio of the strength of the
incoming signal (essentially, view the retina with a document on it as
one set of boundary conditions), and the output neurons as the other
set of boundary conditions.  The derivative of the sigmoid is just
1-sigmoid / sigmoid, so the change at each interior point is
easy to calculate.

The hard part is that it's not a monotonic surface; finding the global 
minimum instead of a local is not gauranteed.


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

yep.  That's why I'm thinking very hard of how to change that.

Maybe something like a narrower retina, but more variations (i.e. 64
input neurons, retina of 1024, and the retina cells are nonuniform.

That is, for hash H, and input-level neuron N, and retina width R,
the cell C that hash goes into varies with the neuron number (and
given the odd prime sequence P[N] = 3, 5, 7, 11, 13, 17, ...) something
like:

    R = ( H + ( H >> log2(R) ) * P[N] ) mod C

but be warned, I haven't tested this, I just keep mulling it over
and thinking about the ramifications on the subway.  Aliasing CAN be
worse, but you have 63 out of 64 neurons that will be able to 
differentiate between any two random 32-bit featurecodes.

(note- the above actually only gives 20 bits of significance.
I'm working on how to fix it for a true 32-bit significance that
isn't horrible to express or calculate.

The rough rule of thumb for neural nets is for N different relatively
non-crazy, relatively linearly separable categories you need some
small multiple of that many neurons in the input and hidden layers.
Since the number of retina x input weights dominates this
calculation, we need to try to minimize them but without loss
of the discriminatory power of a NN.

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

No, it's also truth.  NNs are not gauranteed to work for all possible
input configurations.

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

Can you post a diff?


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

I tried really, really hard to document that code well.  *sigh*.

Well, at least pull the paper from SRI and see if that helps.  Note
that the paper also has some typoes in it.  :(

     - Bill Yerazunis

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