Page 2 of 2 FirstFirst 12
Results 31 to 45 of 45

Thread: Logistic mixing & modeling

  1. #31
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,137
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    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.

  2. #32
    Member
    Join Date
    Dec 2008
    Location
    Poland, Warsaw
    Posts
    1,274
    Thanks
    803
    Thanked 545 Times in 415 Posts
    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

  3. #33
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,137
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    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

  4. #34
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    - 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

  5. #35
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,137
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    Btw, I just noticed this:
    Code:
    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 %).

  6. #36
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,137
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    http://ctxmodel.net/files/mix_test/mix_test_v7.rar

    Code:
    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
    Last edited by Shelwien; 18th June 2009 at 04:59.

  7. #37
    Member
    Join Date
    Apr 2009
    Location
    The Netherlands
    Posts
    85
    Thanks
    7
    Thanked 18 Times in 11 Posts
    Quote Originally Posted by Shelwien View Post
    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?

  8. #38
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Arrow

    In this case it's a bit different:

    Code:
    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...

  9. #39
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,137
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    > 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

  10. #40
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,137
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    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
    Last edited by Shelwien; 25th June 2009 at 10:32.

  11. #41
    Member
    Join Date
    Apr 2009
    Location
    The Netherlands
    Posts
    85
    Thanks
    7
    Thanked 18 Times in 11 Posts
    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.

  12. #42
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,137
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    Sorry, dunno... maybe some yahoo weirdness. It works for me,
    but you can try http://ctxmodel.net.p2.hostingprod.com/

  13. #43
    Member
    Join Date
    Apr 2009
    Location
    The Netherlands
    Posts
    85
    Thanks
    7
    Thanked 18 Times in 11 Posts
    Thanks Shelwien, that works!

  14. #44
    Member MontySpear's Avatar
    Join Date
    Mar 2011
    Location
    8220 N Perkins Rd, Stillwater, OK 74075
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Great done by all. Thanks for sharing the important stuff.

    Last edited by MontySpear; 2nd March 2011 at 12:18.

  15. #45
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 798 Times in 489 Posts
    Somehow this escaped my attention. http://mattmahoney.net/dc/text.html#1678

Page 2 of 2 FirstFirst 12

Similar Threads

  1. Simple bytewise context mixing demo
    By Shelwien in forum Data Compression
    Replies: 13
    Last Post: 3rd April 2020, 17:04
  2. Context mixing
    By Cyan in forum Data Compression
    Replies: 7
    Last Post: 4th December 2009, 19:12
  3. Mixing strategies
    By Alibert in forum Data Compression
    Replies: 38
    Last Post: 25th June 2009, 00:37
  4. Graphic/Image/Modeling Benchmark
    By Simon Berger in forum Data Compression
    Replies: 23
    Last Post: 24th May 2009, 18:50
  5. CMM fast context mixing compressor
    By toffer in forum Forum Archive
    Replies: 171
    Last Post: 24th April 2008, 14:57

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •