Re: crm filter cleanup on productive system

On Tue, Feb 24, 2009 at 2:19 AM, Bill Yerazunis <[email protected]> wrote:
>   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.

Couple of thoughts about that. (Rough writing here; uncooked.)

Mapping function must ensure 'reproducible' (or what the proper
English word is), i.e. other documents where features occur at [even
slightly] different spots should still allow the NN to 'recognize' the
feature, so input-position-dependent encoding of hashes is off limits
(idx = H(feature, feature_position_in_input_stream) MOD retina_size is
hence not usable).

Furthermore, given that calculating an index into the retina is
nothing different from calculating an index into a hashtable - if you
ignore what comes after the retina. Anayway, an NN 'recognizes'
patterns which occur on the retina, so in order to get a 'hit' (or
rather the NN similar of that) you'll need to land a significant
feature on the same retina spot every time.
As we can regard the hash-to-index mapping function for the retina as
similar to a mapping function for hash tables, it is, for the purpose
of keeping the flattest possible distribution from tokens, through
hashes, onto retina spots (indexed positions), very probably good
practice to have a prime-sized retina. At least a retina mapping
function where the modulo (divisor) is relative prime to both ALL the
(prime) factors used in the universal hash mixer used inside the VT to
combine the token hashes into feature hashes, thus creating something
that approaches Markov Chains, *plus* its size should be relative
prime to any factors used in the token hash function itself (though
that last bit there is just gut feeling right now.
And given the size of the hashes (power of 2), larger primes look to
me like they might make sense.

I've been trying to understand what you meant by

>    retina_slot = feature_hash MOD ( retina_size - neuron_number)

and if you mean with this that you are thinking about making the
hash-to-index fucntion dependent on 'desired output' (after all, we
*know* what the result should be for each of the documents (feature
collections) we train!), so that the same feature hash, but located in
a document with another desired outcome, say out-of-class instead of
in-class, lands on different retina indexes: as that is not
input-position dependent, recognition of such features should indeed
be 'better' (again, gut feel, no hard math backing).

So a mapping function might be something like this:

retina_index = H(feature_hash, class_to_train_for) MOD retina_size

where 'retina_size' is a (relative) prime - easiest resolved by
ensuring retina_size is a real prime, though as a 'guestimate' a
Mersenne prime might be good enough for this.
Where H() is some sort of mixing function, maybe just another round of
universal hashing (with its own multiplicator, which should be
relative prime to any other factor in the VT and other parts along the
data flow path).
Where class_to_train_for is either 'in class' (0) or 'out of class'
(1) (as the current NN only has only two outputs anyway).

You can /try/ to keep the feature collisions down to a minimum (by
trying to keep all the hashing elements in the chain up to this point
set up in such a way that all of them create the flattest possible
hash distributions; note that universal hashing is easy, but isn't
really 'the best' when it comes to getting flat output space
distributions as more significant bits do not mix with less
significant bits. Alas, hashing is 'weird' too! ;-) ) but all you can
do is /try/: reducing anything from tokens ([small] chunks of text) to
N-bit hashes to M-bit retina indexes (where M < N) means you've got to
quantization stages in your pipeline at least. Given the
token-to-feature mixing done in VT, one can argue there are 3
quantization stages, where each of those stages reduces the input and
influences all that come after it.


Hm, I like the 'move feature hashes on the retina based on
desired-result' idea; it would at least help those situations where
particular features occur in both in-class and out-of-class documents.
But using such a thing would also mean you can then only learn about
half the amount of what could've been trained if you didn't do this
'offset trick', as to the NN, the offset means a feature F is now
two(2) features: one at index I_0 and one at index I_1 --> for same
capacity, NN has to grow by a factor of 2. But then it would surely be
able to learn A xor B patterns, which is very interesting (for my
intentions with crm114 at least) :-))


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

Tried several myself. Primary conclusion now: I had to dial up the
noise injection quite a bit to make the NN 'resolve' at all:

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

You're absolutely correct. My mistake.

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

A-ha. Another bit of light came in. :-)

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

I have to correct myself there: it not per-document, but per CSS
(which can be viewed as 'by class' if we ignore the <refute>
functionality). Anyway, per CSS file, it's one(1) persistent NN and
all the trained documents for that CSS appended after that. I.e. the
CSS format is a somewhat like:

- header
- NN dump (in the form of the three crossbar weight arrays (Win/Whid/Wout)
- tiny document header
- dump of all feature hashes for a document
- next tiny document header
- another dump of feature hashes
... etc ...


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

I opened my books again and it doesn't look like exactly like a
Kohonen SOM, that's right. What to name it then, I don't know.


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

The analogy was meant to describe what's actually going on in the
implementation, not what a Kohonen (or other) model is _supposed_ to
do in theory.
And, yeah, my own tests very strongly indicate that removing that
'jittering' (random injection) from the learning process produces
disastrous results. /with/ the continued (decaying) random injection
though, the results are generally quite nice.


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

I have to ponder this some more, before I really 'get' this. Not your
fault; just my brain giving up ATM.

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

You mean you're thinking about reducing the connectivity of the Win crossbar?

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

How you would be able to accomplish that last bit while keeping the
whole thing within a 32-bit software realm, is currently beyond me. My
initial reaction here is: that's not doable. But I may be wrong.

>   Oh, and by the way: both GerH and vanilla releases have two bugs
>   lurking in that NN code.
>
> Can you post a diff?

See posts to dev list the last few days. There's another one in there
as well (I finally found what did me in coredump-wise with NN) but
I'll post that bugger later on.


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

Nah, the documentation was quite allright (especially the eralier
version, which had more and showed some of the thought processes that
went into this thing). It's just that I am a little different: I
learn.discover 'bottom-up' (at least the actual process has a lot of
that anyway), which I've found very few people do. Bottom line: I
learn the most the hard way. And since I want/need to tune these
classifiers, I better make sure I really grok them well.


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

Got several on the subject here (in fact, a whole book to knock myself
out ;-) ); they help, but that's only one half of it. No worries.
Different brain, different discovery paths, 's all.


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