Re: Some questions

For nitpicks...

Few self-corrects here and an augment:

> code, the addagium is to always have larger weights for 'longer'

--> adagium (or adage IIRC)




> I haven't covered training rather spotty, but that piece of the code

Sentence kludge in the brain --> Coverage of training was rather spotty, ...



There are more errors in the text I wrote (missing words and a few
wrong ones, that sort of thing) but those should be obvious.





> existing weight with a 'sense' factor (OSB_WINNOW_PROMOTION /
> OSB_WINNOW_DEMOTION) -- which incidentally tells us that <refute>
> cannot 'undo' a previous training _exactly_.

In pure math, this is nonsense as you multiply with factor F in a
multiplication series (which is what a sequence of trainings for a
specific feature hash is for WINNOW) by dividing the product by that
same factor F, i.e. multiplying by its reciprocal 1/F.

However, way too many people time and again forget that floating point
'math' is NOT pure math as floating point operations have a _finite_
accuracy, i.e. each floating point operation introduces a certain
'error' in its result. And those who have been taught to work with
'error terms', or from my original mech. engineering background:
'tolerances', know that those always accumulate. (Did you get this
stuff in CS classes? Didn't see it happening here in NL, apart from a
few math classes -- which students are always extremely desperate to
forget ever after ;-) ) Hence the floating operations

Y=X

and

v=X*F
Y=v*(1/F)

do not produce the _exact_ same result. That's why C provide those
FLT_EPSILON and DBL_EPSILON constants, which are very rough guides to
the 'error term' of a floating point operation.

For the math-oriented, a floating point multiplication operation
can/should be written as

v=X*F+ME
where ME is the multiplication error term, which' worst case can be
roughly approximated by EPSILON*Y*F as the error term is introduced by
the multiplication operation, i.e. A*B becomes (1+e)*(A*B) where 'e'
is epsilon - a tiny value representing the amount of error introduced
by the operation. 'e' is a perunage (as are it's comparable
DBL_EPSILON and FLT_EPSILON values in 'C's <float.h>). [Perunage = per
one. Cf. percentage: per hundred. perunages are used in math and
financial calculations as they, contrary to percentages, prevent you
from mislaying a couple of significant zeroes when you are not
careful. ;-) ]

X=v*(1/F)+ME
where
ME ~ EPSILON*v*(1/F)

['~': is about equal / almost equivalent to]
resulting in a compound error term for X of EPSILON*(Y*F +
EPSILON*Y*F)*(1/F)  ~  EPSILON*Y as the second EPSILON term is
neglected for this worst-case range. Thanks to the tiny value of
EPSILON, this is not immediately visible, but execute a (long)
sequence of FP operations (i.e. a cascade, where previous results are
used in the next [set of] operations) and the error term suddenly
isn't all that tiny any more. A cascade of N multiplications will
produce a result with an error component ~ N*e as (1+e)^N ~ (1+N*e)
for tiny 'e'.
A good example is the progressive P calculation in the MARKOVIAN
classifier where N multiplications (and other operations) are applied
before the final answer is displayed, where N is the total number of
feature hash hits produced from the input text, a number which can
easily be large (100+).


Note that an error term produces a _range_: [-0.5*ME..+0.5*ME], which
is significant when you sequence operations: you can't say ME-ME=0,
but instead, ME-ME is 2*ME (!) and ME/ME != 1 either, but
/approximately/ equal to 2*ME (!) as worst case for error range e
implies that:
ME/ME: (1+e)/(1-e) == (1+e)/(1-e) * 1 == (1+e)/(1-e) * (1+e)/(1+e)
== (1 + 2e + e^2) / (1 - e^2)
which for tiny e can be simplified to (as e^2 will then be extremely small):
~ 1+2e
producing that resulting error term of 2*e for a division of error
terms, i.e. E1+E2 for E1/E2.
In short: epsilon error terms about add up for any operation.
(Yes, that last bit's cutting, errr, /lopping/ off corners.)


Of course, we can apply error term analysis to the formulas
(calculations) used by MARKOVIAN to calculate the final P(i) and
pR(i), but we know the compound errors accumulate (they add up) so
initially we can wing it by simply counting the number of cascaded
floating point operations and use that 'errors add' rule-of-thumb to
get at a rough error estimate due to using floating point
calculations:

Since the P(i,k) and P_local(i,k) FP calculations are situated within
the large 'for each feature generated from input' for(...) loop, we
find that, while

P(i,k) = P(i-1,k) * P_local(i,k) / renorm(i)

where

renorm(i) = SUM(P(i-1,k) * P_local(i,k), k E [0..number_of_classes-1])

[i.e. add all P_local() calculated for this feature for each class,
where each P_local() is multiplied by their previous P() value for
that class: see the markovian code and check the pltc[] and ptc[] calc
code in there: pltc[k] ~ P_local(i,k) and ptc[k] ~ P(i-1,k) and near
the end of that loop ptc[k] ~ P(i,k)]
and

P_local(i, k) = 0.5 + (2 * hits(i,k) - SUM(hits(i,k), all k)) /
compile_time_weight_factor_for_scaling_P * (SUM(hits(i,k), all k) + 1)

we have about 2 to 3 FP operations (3 if
compile_time_weight_factor_for_scaling_P is not an integer value; the
other two are the outer addition (+) and the division (/)) for each
P_local(i, k).
The hits[] etc. calculations in there are integer-based so zero error
component (at least in GerH, IIRC those are double-based in vanilla,
so there you'd have to count more FP ops in the cascade).

Which, given the way renorm() is built, means renorm() takes about
K*2(mult+add for SUM()) FP ops, where K=2 for the usual two class
(ham+spam) scheme. [In the code, renorm ~ renorm(i)]

Hence, P(i,k) requires about (1+2..3+1+K*2 FP ops (multiplication,
P_local, division, renorm cost) == about 8 FP ops per P(i,k) round.
That is 8 FP ops for a single feature hash hit, and since P(i,k) is a
cascading calculation (P(i,k) is derived from (Pi-1,k), which was
calculated in the previous round in the loop), we arrive at a worst
case estimate of a sequence of 8*N FP ops for an input document which
produced N feature hash hits.

Now, assuming a usual DBL_EPSILON (a 'double' based calculations;
'float'-based are consequently MUCH worse) and a document which
produces N feature hits has a VERY roughly  guestimated error
component in its resulting P and pR values of ~ 8*N*DBL_EPSILON, and
as DBL_EPSILON is <= 1E-9 for all usual platforms, there doesn't seem
to be any cause for worry for any N (which can run up to the
compile-time limit of 500K: 8*5E+5*1E-9 = 4E-3 which implies we still
have a little better than 2 significant digits in there.

But there's more... The rough guestimate completely ignores the fact
there's a FP calculation cascade in the P(i,k) divisor (== renorm(i))
as that one is again based on previously calculated P(i,k), and
experience tells us this is a dangerous thing to have around if you
care about reproducibility of values across platforms and accuracy of
calculated values in general: automatic testing benefits from
precisely reproducible results, even when we know the input data does
not merit more than, say, 2 significant digits, at best.
(Note: divisions generally produce smaller results, compared to the
'input values': numerator and divisor, while still INcreasing the
error component: that means division operations can amplify errors
manifold, especially for larger divisors. And thanks to the nature of
FP, 'larger' is NOT your usual notion of the word, as in 'larger than
1', nay, it's about the number of bits in the mantissa used to
represent the value (which can itself be extremely tiny: negative
power of 2 values). To keep it all bearable, forget about the 'larger'
condition and just keep in mind that division (and subtraction) are
error-amplifying operations as both get you smaller results while the
error component still grows progressively.)



Given the FP cascade in the P(i,k) divisor we'll need to check it out
in more detail.
I'm working on that but it will take some time in finishing as there's
several spots in there that make error propagation analysis no
sinecure.

Why I persue this is partly because I've seen enough of the software
to see there's something in there that's potentially dangerous w.r.t.
output value accuracy (FP cascade through renorm(i) into the divisor,
resulting in a C^N power factor for the compound error expression).
Note that this concerns markovian, OSB and OSBF but not Winnow, as the
latter does not have FP cascades through renormalization in an in-loop
divisor and thus will suffer much less from FP error accumulation: the
worst error term for Winnow is linear N*e.
These theory-based ideas are one side of the coin; on the other side
significant effects have occured in actual practice as I've
manipulated the crm114 code while porting&running it on several
different platforms: for a few megatest test cases, the effects of
reducing / removing the N*DBL_EPSILON divide-by-zero-prevention fixups
(N = {10, 100, 1000}) in-loop show a change in pR in the second-most
significant digit.
Those divide-by-zero fixups can be considered as 'noise/error
injection' in a control-engineering sense and despite their tiny
values, propagation through several rounds of renormalizations causes
visible change in pR results.

More on this later.
floating point calculation accuracy analysis & estimation is quite
often a neglected area when it comes to developing software.


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