Logistic mixing & modeling

[Shelwien]

http://ctxmodel.net/files/mix_test/mix_test_v5.rar

book1 enwik8
213663 21038280 logistic mix2 with gradient descent update (v4)
213599 21065319 logistic mix2 with likelihood-based update (v4)
209522 20772180 4x log + lin
209410 20773026 5x log
209826 20744613 bcm008

v5
- rate parameter added to logistic mixer
- mixer interfaces changed
- more submodels
- mixer contexts

------------------------------------------------------

So, now there're dual o0 and o1 with different rates, plus
a submodel with o1 history byte as a context, and one
using a byte before previous.
And it seems that this finally reached the stage where logistic
mixing is not so good.
That is, compression just became worse when "weird" submodels
were added, but after replacing the final mixer with linear, it improved.
And then, with some modifications, logistic mixer was able to do the same,
but I guess I'm starting to see where its better to use which one.

Anyway, here we have 6 fixed-rate linear counters (2 of which are mostly
useless), and no SSE or tricky contexts (runlength etc) or anything,
so there're plenty of ways for improvement.

[Darek]

Quite interesting results! Especially in comparison with paq versions:

book1
209961 - paq8hp12 -8
209945 - paq8k -8
209122 - paq8px v54 -8

It looks like only latest paq version (paq8px) is able to beat version 5 of mixing test!
Darek

[Shelwien]

http://ctxmodel.net/files/mix_test/mix_test_v6.rar

209114 - mix2 with probability output
209065 - mix2 with stretched probability output
209552 - mix6, paq-style

book1 book1r enwik8 enwik8r
209114 207904 20767074 20686780
209065 207843 20738050 20671687
209552 208192 20795267 20702239

v6
- "weird submodels" (sparse and indirect) replaced with
masked o1 and o2, which then got optimized into o0 and
partial o2 with the mask 0x1F1F.
- finally designed a "precise" frequency-based counter,
and appears that it really shows slightly better results
than fixed-rate linear counter, but not in the mix.
- made an attempt to port the model into unary coder,
it works, but compression is not there yet (>210k)
- removed the intermediate probability values (09c6a).
for speed optimization, but in the end it got optimized
better than "slow" version, and with only 2 mappings instead of 3.
- made an attempt to implement an original paq mixer with
multiple inputs (09c6e), it got optimized better than expected,
but is still worse than chained mix2.

ToDo:
- Implement a linear mixer based on a counter with bit frequencies
- Find a better model switching sequence generation method
for likelihood-based mixer
- wr,wq recalc into s0,s1 fixed coefficients
- replacement of Mx.sq(Px) with p0 or something
- derive an update function for chained mixers with single target (p0)
- add more submodels

[toffer]

- derive an update function for chained mixers with single target (p0)

As i suggested - error backpropagation. Just replace RMSE with the entropy.

http://www.willamette.edu/~gorr/clas.../backprop.html

[Shelwien]

Btw, I just noticed this:

Rate1   g1wr,  16!00000000000110
Number  g1mw, 1,1!111111111111111

Its one of plain o1 submodels, and its parameters got optimized to this...
which basically means an inverted sequence.
So it looks like mix( p, 1-p ) might be actually useful %).

[Shelwien]

http://ctxmodel.net/files/mix_test/mix_test_v7.rar

book1  book1r enwik8   enwik8r
208794 207873 20717843 20658044 // mix_test_v7
209826        20744613          // bcm008
208863        20638938          // bcm009

v7
- Added two more submodels to the mix
- Added some command-line interface (instead of fixed book1bwt encoding-decoding)
- Added BWT/unBWT to get a real BWT compressor

------------

Seems that dumbly tuning 8 ~o1 submodels with paq mixer to book1 still
wasn't enough to beat bcm009.
But well, its still better than bcm008 (dunno about speed though)
and bcm009 isn't public

[Kaw]

So it looks like mix( p, 1-p ) might be actually useful %).

Should that be surprising? My first thoughts would tell me that this situation balances the relative strength of p. P could tell you 1 or 0 almost all the time, but if P isn?t actually 1 or 0, then P get balanced this way to for example 0.8 and 0.2.

Is this mixer comparable to a weighted average or more like a Bayesian approach?

[toffer]

In this case it's a bit different:

void Update( int c, const int wr1, const int Mw ) {
  int dp = P + Mw-SCALE + ((SCALE-2*Mw)&(-c));
  int q = P - ((dp*wr1)>>SCALElog);
  P = q;
}

which basically means:

p' = (1-w)*p + w*[ 1-c + (2*c-1)*m ]

c=0: p' = (1-w)*p + w*(1-m)
c=1: p' = (1-w)*p + w*m

where p=P(c=0), the probability of a zero bit.

Normally one would get m ~ 0 and w ~ 1, which means to increase p, if c was 0 and to decrease in the opposite case. Having m ~ 1 and w ~ 0 does the opposite - in a pretty drastic way - having seen c=0, P(c=0) is set to 0 and c=1, P(c=0) = 1. That's a model for bit sequences like ...01010101...

[Shelwien]

> c=0: p' = (1-w)*p + w*(1-m)
> c=1: p' = (1-w)*p + w*m
> where p=P(c=0), the probability of a zero bit.

right.

> Having m ~ 1 and w ~ 0 does the opposite - in a
> pretty drastic way - having seen c=0, P(c=0) is set to 0
> and c=1, P(c=0) = 1.

1. wr there equals to 16*32768/(16+6) = 23831
2. mw = (2^15-1)+1 = SCALE
3. c=0: p' = 0.272*p
c=1: p' = 0.272*p + 0.728
but still p = P(c=0).

> That's a model for bit sequences like ...01010101...

yeah, well.

> Should that be surprising?

Well, it was.
1. I completely forgot that my counter has that kind of symmetry,
and it was optimized to that state automatically, starting from
a "standard" parameter set.
2. After removing that specific submodel (from a mix of 6 submodels)
the compression gets worse by ~500 bytes (209060 to 2095xx)
So, there're quite a few cases which are better handled by
this weird submodel than any of other 5.
Its also an order1 submodel for BWT data, so these "better handled"
cases would look like aa...ab...aa...ab, or maybe aaAaaAaaAaaA,
which might be normal for BWT, but who knew that it could be useful.

> My first thoughts would tell me that this situation
> balances the relative strength of p. P could tell you 1 or 0
> almost all the time, but if P isn't actually 1 or 0,
> then P get balanced this way to for example 0.8 and 0.2.

Well, that would be an imprecise approximation of a simple counter
by a mixer, if its input somehow got stuck at a fixed value.
But a normal counter is usually better, so it certainly involves
some specific repeating patterns in the BWT output.

> Is this mixer comparable to a weighted average or more
> like a Bayesian approach?

Well, more like bayesian, but wikipedia says
"In a sense, likelihood works backwards from conditional probability",
and I kinda agree.
http://en.wikipedia.org/wiki/Likelihood

[Shelwien]

http://ctxmodel.net/files/mix_test/mix_test_v8.rar

book1 enwik6 enwik8
208255 251109 20621691 // v8-enwik6
208120 251437 20635094 // v8-book1
209826 253143 20744613 // bcm008
208863 ??????? 20638938 // bcm009

book1r enwik6r enwik8r
207135 248862 20558355 // v8-enwik6
207131 249428 20574207 // v8-book1

v8
- still 8 counters + 7 logistic mix2
- v7 bugs fixed (uninitialized counters and mixers, F1-F3 assigned to the same table)
- symmetric binary tree mixing (was unary before)
- counter table size optimization (.idx syntax for masks added)
- dual update for o1 counters
- improved rangecoder precision
- separate versions tuned to book1 and enwik6

ToDo:
- delayed counters with runlengths
- conscious bit history modelling
- logistic SSE2 with interpolation
- unary coder optimization

[Kaw]

Shelwien, is it posible that ctxmodel.net is offline? Will it come online again? I really want to take a look at the last experiment.

[Shelwien]

Sorry, dunno... maybe some yahoo weirdness. It works for me,
but you can try http://ctxmodel.net.p2.hostingprod.com/

[Kaw]

Thanks Shelwien, that works!

[MontySpear]

Great done by all. Thanks for sharing the important stuff.

[Matt Mahoney]

Somehow this escaped my attention. http://mattmahoney.net/dc/text.html#1678