<< ctxmodel.net

  1. Let's start with a combinatoric counter with occurrence numbers,
    estimation: p = n[0]/(n[0]+n[1])
    update: n[bit]++
  2. 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;
  3. Update is simplified to a linear counter with constant parameters, as its a precise approximation of (2) for long histories.
  4. 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.
  5. 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
  6. 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>
  7. 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.
  8. 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.
  9. 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                 >

Write a comment: