<< ctxmodel.net

Let's start with a combinatoric counter with occurrence numbers,
estimation: p = n[0]/(n[0]+n[1])
update: n[bit]++

Rescaling coefficient is added there (exponential decay)
estimation: p = n[0]/(n[0]+n[1])
update: n[0]*=(1wr); n[1]*=(1wr); n[bit]+=wr;

Update is simplified to a linear counter with constant
parameters, as its a precise approximation of (2) for long
histories.

Linear approximation makes update sequences also
linear, so a "delayed counter" can be made  which caches
some bits and updates the probability with oldest bit in the
queue while also allowing to use a different estimation
function to produce a probability from "delayed
probability" and cached history bits.

Then there're two branches in estimation function:
"incomplete history" and "complete history".
For "incomplete" branch we can just use a common counter
table indexed by "incomplete history" context, and
estimations with "complete" history are linear
transformations of "delayed probability".
Basically, the "delayed probability" is used as a linear
mixer weight there: p = p0*(1pd)+p1*pd;
so an obvious idea would be to update p0 and p1, and we'd get SSE

Next obvious step is to use a piecewiselinear
extrapolation function for estimation, instead of simple
linear so we can go from SSE<2> to SSE<N>

There's also still a contextual update in the counter,
which can be improved by (static) parameter optimization,
but I don't yet know how to make it adaptive.

Counter state is still rather small (1624 bits) so it
can be easily enough quantized and implemented via lookup
tables (otherwise it would be slow and not very efficient
w.r.t memory).
Also, it might be interesting to add some more components
at this stage  like quantizing a static linear mix of two
counters into a single fsm or something like mix(p,0.5),
or both.
This would be harder to quantize though, due to larger
state size, which might prohibit the enumeration of all
states in memory.

SSE estimations from 2 or more counters can be merged
into multidimensional extrapolation functions
20130801 13:18:18 >
20141127 06:41:44 >
20150112 05:55:49 >

