Idea: Smoothed probability

[Piotr Tarsa]

With fpaq0p-like probability updates the weigths form a geometric sequence. This is generally desirable, but this poses a new problem. Consider such sequence:
0000000100000000100000

After bit 1 the probability of 1 will drastically go up and then next few 0's will be coded with much longes codes than the 0's right before next 1.

My solution is to make smoothed counters by appending a bit history to a probability, ie instead of keeping an int value describing weighted probability of the history up to current point, we have a pair of (recent bit history trimmed to last N-bits, wegithed probability of the history up to the point where the bit history from the first tuple value begins). Additionally there could be a table that maps a bit history from that pair to a pair (weight of delayed probability, probabilty computed from the trimmed bit history). When updating, the current bit will be shifted in the trimmed bit history and the bit that was shifted out of the trimmed bit history will be used to update the delayed probability.

What do you think?

PS:
Direct bit histories could be replaced with other types of states provided that a state corresponds exactly to some (trimmed or not) bit history, so we can update the delayed probability by checking which bits are shifted out from the new state.

[Cyan]

Are you looking for State Machine ?

[Piotr Tarsa]

Actually, I had state machines in mind when writing this, but this is about counters. Even if you use indirect modelling you end up somewhere with counters. Ie you have to map the state to probability, no matter what you do in the meantime.

A counter can be represented as a pair of counts (n0, n1) just like Jean-Marie Barone is doing in his SMAC (IIRC) or you can use fpaq0p-like counters (ie fixed update rate) or LPAQ-like counters (ie slowing down update rate). Pairs of counts are relatively immune to the oscillation problem I've described in first post, but they have other problems (eg the update rate doesn't converge if we're doing rescaling regularly). Usually people use fpaq0p-like or LPAQ-like counters and they are prone to the problem I've described above.

LPAQ1-like counters update rate converges to some fixed rate after reaching a limit, becoming a fpaq0p-like counters, so I've analyzed the fpaq0p-like counters only.