Re: [freenet-dev] Decaying Exponential Decay for binary estimators

[Martin Stone Davis]

Kendy, please just reply to the list, rather than to me personally. 
That way everyone benefits from your input.  Also, I prefer to read devl 
from my newsreader rather than from my inbox.

Kendy Kutzner wrote:

On 2003-12-03T03:24:35-0800, Martin Stone Davis wrote:

There's a problem with the current method of calculating the estimators 
of binary variables using exponential decay.  The problem is this: If a 
binary variable has a true average value near 0 or 1, the exponential 
decay function will frequently compute the estimate WAY off from its 
"true" value.


I agree.


Let DDRA = the decaying decaying running average
Let decayingDecayFactor=decayFactor * MIN(DRA,1-DRA)
Then compute the new decaying decaying running average as:
DDRA := DDRA*(1-decayingDecayFactor) + [1 or 0]*decayingDecayFactor


Not sure if I understood correctly (is DRA==DDRA?). I will try in
my words:
Given decayFactor DF (from Configfile, alchemy, whatever);
two variables: DDF and DDRA;
update_ddra(value) {
        DDF = DF * min(DDRA, 1-DDRA);
        DDRA = DDRA*(1-DDF) + value*DDF;
}
Yes, that's it.  Sorry, you aren't the only one who was confused.

One problem I see is you have to make _very_ sure that DDF is
never zero and DDRA never goes to exactly zero or exactly one
(due to floating point rounding). If they ever do, they will stay
there forever.

True.  I'll make sure to guard against that when I code it today.

Whatcha think?


Interesting. But I'm not sure whether your function for DDF is
the best one. Further I'm not sure whether the problem at hand
(average a bernoulli distribution) has a good solution without
memorizing the last N values.
Well, IF the variable truly acts like a random Bernoulli variable, then 
I doubt it's necessary to memorize the last N values.

However, if it does something like this (for example): 1 1 0 0 0 0 1 1 0 
0 1 1 1 1 0 0, where every other value really depends on the prior 
value, then some kind of pattern-recognition algorithm could figure that 
out and allow us to make better predictions.  We human beings should 
look at the pattern of failures/successes for each binary variable we 
use in the estimator to see that my assumption of a random Bernoulli is 
a good one.

Kendy

-Martin

_______________________________________________
Devl mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl