|
<< 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]*=(1-wr); n[1]*=(1-wr); 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*(1-pd)+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 piecewise-linear
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 (16-24 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 multi-dimensional extrapolation functions
2013-08-01 13:18:18 >
2014-11-27 06:41:44 >
2015-01-12 05:55:49 >
|
|