Re: crm filter cleanup on productive system

On Tue, Feb 24, 2009 at 7:15 AM, Eugene Crosser <[email protected]> wrote:
> Pardon my intrusion, I am definitely not qualified to reason about these math
> subtleties, but I'll try anyway.
>
> The attempt to get "true 32-bit significance" seems unfounded to me. What is
> going on is that original arbitrary size "pieces of data" (words, whatever) are
> "folded" into short hashes, that *happen to be* 32bit in this particular
> implementation. When you use 13 bits of the 32bit hash for the NN, you do not
> "loose 19 bits", you just fold the original data into a shorter hash.
>
> Obviously, the shorter the hash, the higher is probability of "hash clash", i.e.
> of different original pieces of data being converted into the same hash value.
> This probability exists for 32bit hashes as well as for 13bit, it's just way
> lower for 32bit.
>
> Now, when you are trying to "cheat" like "retina_slot = feature_hash MOD (
> retina_size - neuron_number)", you are just changing the "overall" hash function
> that converts the original data into 13bit hash (in this case, roughly, by
> taking different 13 bits from the "fist stage" 32bit hash), but it does not
> change the probability of different original pieces ending up with the same
> hash. (Well, in assumption that the initial hash function is cryptographically
> sound.) What you achieve is just a different hash function that packs into the
> same size hash. The probability of two different "original features" having the
> same hash will not change.
>
> IANAM ;-)

NAI. What you're saying is, I think, correct.

The bit that makes it all a little harder is that none of the hash
functions used are guaranteed to be 'sound' (note that I left out the
'cryptographically' there, as that word implies at least one added
requirement (non-reversibility) which we don't have to worry about
here (crm114 is not about filtering in a cryptographically secure
sense, i.e. with guaranteed privacy protection, etc. regarding the CSS
stores or any other parts of the system).

A 'sound' hash mixes input bits (for arbitrary input lengths) in such
a way that collisions are minimal. To attain this, the distribution of
all possible hash outputs over the target space (2^32 for crm114
feature hashes; retina_size for NN) should be perfectly flat. (If it
isn't, you'll have one or more groups of hash values which will each
occur more often than some of the others, meaning there's a higher
chance of collisions there).

Anyway, lots of fun to be had with that, but I'll jump to what we have
in crm114. When you travel through the process from input to NN
retina, there's a few hash functions met on the way: the strnhash()
token hash function, the multiplicative hash function in the VT engine
which is used to mix two or more strnhash token hashes into a single
Markov Chain mimicing feature hash and then, at last, the
  idx = fh MOD retina_size
mapping function, which can be considered the third hashing function
as it, too, plays a significant part in the flat distribution of input
words (tokens) across the NN retina.
So taken all together, it's like you say: a compound hash function
which maps tokens onto the retina. Tweaking the index mapping function
is like changing the overall hash compound function. YMMV.

(Same chain applies to the Bayesian/Markovian classifiers: there the
'retina' size is the size of CSS hash table, BTW)

The question is whether this compound hash function is 'sound'. Maybe
it's close, but it is not ideal, so better ways can be sought.

First, the 'idx = hf MOD size' mapper. Me saying the 'size' should be
a relative prime is only another 'attempt', compared to using a
power-of-2 size, but both ways have their issues - and benefits. The
power-of-2 size is better when this stage's input (fh) has a flat
distribution over a (equal of larger) power-of-2 space, as, like you
are correctly saying, it will ensure the distribution of indexes is
flat too, so a minimal chance at collisions there.

Alas, the fh input values (feature hashes) don't have a absolutely
flat distribution, so 'dips' and 'hills' in the input distrib may fall
onto the same target zones through the mapper, increasing the
collsiion risk.
Using a prime-sized target maps a flat distribution in power-of-2 onto
a /non/-flat prime-sized distribution, as it maps m=input_size/prime
blocks of input distribution onto the same space, while a small
remainder chunk (r = input_size mod prime) maps onto _part_ of the
target space, so using primes is less than perfect for a mapping
function.
The only benefit you _might_ have from such an approach is that
non-flatness in input distrib maps onto different parts of output
space, thus reducing the risk of collisions somewhat. But that's a big
IF.
(And given that the original input (token stream) is almost surely not
a 'flat' distribution either, you quickly see why you have to _test_
the system and change its parameters based on your own input feeds.
That's also why crm114-GerH offers multiple token hash functions. And
the crm114 VT engine can be fed custom (as instructed by script
/vector: .../ statement parts) multipliers for the second stage, where
token hashes are mixed to become feature hashes.)

However, we already 'know' the fh range isn't flat, as it includes
artifacts from previous hashing stages:

The fh (feature hash) doesn't come in a flat distrib, even when _its_
source (token hashes) _would_ have been a flat distribution, as the VT
engine uses multiplicative hashes (Knuth, TAOCP, vol. 3, pp. 506 a.o.)
which convert a flat input distrib to a non-flat output distrib as the
multiplication (using any integer value) maps any but the very last
bits of input onto a reduced output space, probability-wise. The
reason: Higher order bits will never influence lower-order bits in the
output, so higher-order and lower-order _input_ bits share the 'upper
region' of output bits, while they do not for the lower region of
output bits ==> you can expect an increased risk of collision in the
higher bits of the multiplicative hash output value.

Given the various factors (some prime, some not, in vanilla; in latest
GerH, all non-power-of-2 VT factors have been made [relative] prime)
used in the VT mixing stage, each of those will produce a certain
shape change in the output distrib compared to the input distrib
(which we hope is flat - at least for the duration of this reasoning).
Using a power-of-2 reduction after that _can_ fold those artifacts
onto the same range, but another risk is that the multiplicative mix
hash in VT means lower order bits are minimally influenced by any but
the very last input bits. In other words: feature hash bit 0 will show
a mix of all the token hashes' bit 0; irrespective of VT
multiplication factors (as long as they all are odd); higher feature
hash bits will only show a _selection_ of the same bits in the token
hashes that were mixed, while combined with a smattering of lower
order token hash bits, depending on VT multiplication factors. Thus,
to enjoy the full mixing effect of the VT engine (and the intended
position-dependent encoding of token hashes in the feature hash, thus
representing something akin to a Markov chain in the feature hash,
requires that you use the upper bits of the feature hash (the most
extreme mapping form, where you'd only use feature hash bit 0 would
not transfer the position-dependence of the tokenhash encoding as bit
0 in fh is the same for vector: 1 1 1 1 1 ... as for any other VT
vector with non-zero, odd multiplication factors in the same positions
in that vector (which is a matrix or set-of-vectors, rather).

So stripping off the higher bits of the feature hash is arguably a Bad
Thing. Using a prime-based MOD operation is one way to keep those high
order bits in the output mix (though at a cost), other mixing options
are probably better. As such, the mapping function for the retina
should be treated as a hash function and all the care needed to create
a 'sound hash' should be applied to that mapping function too.


(This last risk of losing important info, introduced by the VT stage,
can be reduced by adding a 'bit mixing stage' to the multiplicative
hash in VT, but that is, once again, stacking imperfect solution on
top of imperfect solution, so testing this is mandatory. And, no,
perfect solutions for this issue do not exist. The closest come strong
cryptographic hashes, not because they are cryptographic, but because
their field of use has forced their designers to spend a huge amount
of effort in trying to make those hash functions as close to perfect
as possible.
Perish the thought of using them, though, as reducing such hashes
[almost] always destroys all their nice-to-have properties, hash-wise.
While you're still stuck with their extraordinary costs. At no
remaining benefit.)

The whole thing revolves around 'good' generic hash function
characteristics, such as 'bit avalanche' (a characteristic for which
multiplicative hashing performs suboptimal, unless 'helped' by a
subsequent mixing stage); if you're interested in this sort of thing,
there's bits of research on this available on the Net.
Unfortunately, I have yet to find a thorough hash-specific test suite
(other than the work by Bob Jenkins an a few others), but packages
such as testU01 (which is used to check random generators) can, to
some degree, be adapted and used for checking hash functions.



As I've been feeding crm114 32-bit sample data (instead of email
text), I've been looking at those hash and mapping functions for a
while by now and the current state of affairs is as it was: "it all
depends..."
Testing your rig with your own data remains the order of the day - and
given the theory and practical limitations applicable to this type of
thing, it will probably remain so for ever. At least, when you seek a
performance which surpasses the 'out of the box' result. (Which
doesn't mean we can't try to improve the 'out of the box'
performance.)


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