Results 1 to 30 of 30

Thread: Adaptive adaptation rate :)

  1. #1
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts

    Adaptive adaptation rate :)

    Hi,

    It's a little nerdy to post technical thing at the first hour of the year but anyway...


    I'm working on yet another version of TarsaLZP. Right now I'm working on low order PPM part - the part that was very weak in all released versions so far.

    I've created bytewise coder, which scores very good on enwik8. For example 61.536.584 bytes with order0 modelling (S = 512), with only a single set of probabilities (not frequencies). What's different in my model compared to usual bytewise coders is that I'm updating the model the same way fpaq0p does, ie. I'm adding to a selected symbol frequency a fraction of sum of other symbols frequencies. Usual coders just increase counter of selected symbol by a fixed amount.

    Adjusting in usual bytewise coders is done this way:
    counter[selected] += C;

    In my coder I'm doing (probabilites aren't normalized, I'm only maintaining correct relative weights):
    increase = (probabilitySum - probability[selected]) / S;
    probability[selected] += increase;
    probabilitySum += increase;

    This way recent symbol always has greater weight than any older and neither strength of rescalings nor time from last rescaling plays any role (except having slight impact on rounding errors). Just like bitwise fpaq0p like modelling.


    What I want to adaptively tune is the learning rate S. I have ruled out model mixing as:
    - model mixing with non-normalized probabilites would be expensive,
    - there will be LZP layer and that means symbol exclusion that is incompatible with probability normalization,

    I want to tune order-1 model learning rate. My current idea is to have three order-1 models:
    - one with fixed fast adaptation rate,
    - one with fixed slow adaptation rate,
    - one with adaptive adaptation rate,

    Actual coding would be done with probabilites from that third model, but I would want to use information from the first two models to update the learning rate of third model. The question is: how to do that efficiently?

  2. #2
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    What you want is probably an indirect model: context -> bit history -> prediction. So if you have a sequence like 000001, you don't have to guess 1 (fast adapting) or 0 (slow adapting). You look at previous occurrences of the same sequence to see what happened (using a slow adapting model initialized in this case to 1/6).

    ZPAQ uses an 8 bit bit-history which is not ideal because a slow adapting direct model still works better on uniform sources. Here are some tests using direct (CM 16..4 = slow..fast) and indirect (ICM) order 0 models. maxcomp.cat is the concatenated maximum compression corpus.

    Code:
    comp 0 0 0 0 1  (enwik8    calgary.tar  maxcomp.cat)
      (0 cm 9 16    (61241069    1681577    35339958)) (uncomment one line)
      (0 cm 9 12    (61217687    1681256    35259845))
      (0 cm 9 8     (61290591    1684348    35195798))
      (0 cm 9 4     (61902641    1705057    35321488))
      (0 icm 5      (62736218    1717028    34535069))
    hcomp
      halt
    post
      0
    end
    Using a longer bit history might get better results, but then you have to think harder about the second modeling stage. Besides, ICM is designed more for higher order contexts.

  3. #3
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Do you suggest a bitwise model? I already ruled that out because I will be doing symbol exclusion (usually some very probable symbol) and bitwise coding is not compatible with that. Or do you suggest histories (where each history bit tells which model was better) and switching between models? Well, switching should be worse than adaptive learning rate I think.

    Besides, ICM is designed more for higher order contexts.
    I will use LZP for higher orders, like I did in previous versions of TarsaLZP - there were order-4 and order-8 LZP models, adaptively switched.


    Goal is to beat Francesco's RINGS on enwik using single core Having similar speed of course.

  4. #4
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    856
    Thanks
    447
    Thanked 254 Times in 103 Posts
    That looks interesting.
    What kind of speed do you get with this method ?
    It apparently involves updating 256 fields per byte,
    so it may not end up being faster than bit coding ...

  5. #5
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    No, I'm updating only one probability, as I'm not normalizing probabilities. If I would want to do a CM coder I would probably opt for nibblewise coding, no symbol exclusion and normalising to 2^N to avoid divisions entirely. Such nibblewise CM should be both far superior to bytewise coder in terms of speed and somewhat superior to bitwise CM in terms of compression ratio on texts.

    With normalisation to 2^N I would be forced to recompute all values after each byte. So the routine will be:
    sumOthers = 0
    for (symbol : symbols)
    if (symbol != selected)
    sumOthers += (probabity[symbol] -= probability[symbol] >> S)
    probability[selected] = 2 ^ N - sumOthers


    What I'm doing now is grouping symbols into 16 groups of 16 symbols each. That speeds things a lot and can be easily vectorized using even MMX, as I'm using 16-bit precision in model.

    Sample session (unnecessary info removed):
    Code:
    piotrek@msi-wind:~/Pulpit/enwik$ time ~/NetBeansProjects/TarsaLZP/dist/Release/GNU-Linux-x86/tarsalzp c enwik8 enwik8.ari
    
    real	0m11.496s
    user	0m11.145s
    sys	0m0.316s
    piotrek@msi-wind:~/Pulpit/enwik$ time ~/NetBeansProjects/TarsaLZP/dist/Release/GNU-Linux-x86/tarsalzp d enwik8.ari enwik8.dec
    
    real	0m16.862s
    user	0m16.077s
    sys	0m0.460s
    piotrek@msi-wind:~/Pulpit/enwik$ time ~/NetBeansProjects/TarsaLZP/dist/Release/GNU-Linux-x86/tarsalzp c enwik9 enwik9.ari
    
    real	2m1.621s
    user	1m51.719s
    sys	0m3.404s
    piotrek@msi-wind:~/Pulpit/enwik$ time ~/NetBeansProjects/TarsaLZP/dist/Release/GNU-Linux-x86/tarsalzp d enwik9.ari enwik9.dec
    
    real	2m48.654s
    user	2m40.782s
    sys	0m3.724s
    piotrek@msi-wind:~/Pulpit/enwik$ time fpaq/fpaq0pv4A/a.out c enwik8 enwik8.fpaq
    enwik8 (100000000 bytes) -> enwik8.fpaq (61457810 bytes) in 9.30 s.
    
    real	0m9.735s
    user	0m9.005s
    sys	0m0.344s
    piotrek@msi-wind:~/Pulpit/enwik$ time fpaq/fpaq0pv4A/a.out d enwik8.fpaq enwik8.dec
    enwik8.fpaq (61457810 bytes) -> enwik8.dec (100000000 bytes) in 11.58 s.
    
    real	0m11.975s
    user	0m11.229s
    sys	0m0.424s
    piotrek@msi-wind:~/Pulpit/enwik$ time fpaq/fpaq0pv4A/a.out c enwik9 enwik9.fpaq
    enwik9 (1000000000 bytes) -> enwik9.fpaq (622237009 bytes) in 95.88 s.
    
    real	1m46.947s
    user	1m32.854s
    sys	0m3.044s
    piotrek@msi-wind:~/Pulpit/enwik$ time fpaq/fpaq0pv4A/a.out d enwik9.fpaq enwik9.dec
    enwik9.fpaq (622237009 bytes) -> enwik9.dec (1000000000 bytes) in 117.86 s.
    
    real	2m11.885s
    user	1m54.251s
    sys	0m3.760s
    piotrek@msi-wind:~/Pulpit/enwik$ ls -al
    -r--r--r-- 1 piotrek piotrek  100000000 2011-06-01 16:24 enwik8
    -rw-rw-r-- 1 piotrek piotrek   61536584 2012-01-01 13:17 enwik8.ari
    -rw-rw-r-- 1 piotrek piotrek  100000000 2012-01-01 13:28 enwik8.dec
    -rw-rw-r-- 1 piotrek piotrek   61457810 2012-01-01 13:27 enwik8.fpaq
    -r--r--r-- 1 piotrek piotrek 1000000000 2011-06-01 17:29 enwik9
    -rw-rw-r-- 1 piotrek piotrek  623688984 2012-01-01 13:20 enwik9.ari
    -rw-rw-r-- 1 piotrek piotrek 1000000000 2012-01-01 13:32 enwik9.dec
    -rw-rw-r-- 1 piotrek piotrek  622237009 2012-01-01 13:30 enwik9.fpaq
    piotrek@msi-wind:~/Pulpit/enwik$
    Eugene's fpaq0something compiled with:
    Code:
    piotrek@msi-wind:~/Pulpit/enwik/fpaq/fpaq0pv4A$ g++ -m32 -O3 -fomit-frame-pointer fpaq0pv4.cpp
    So fpaq0something is still faster than my bytewise coder, but my coder offers possibility of easy and precise symbol exclusion, which is very important in TarsaLZP.

    I've attached snapshot of my coder (Linux 64-bit builds + NetBeans project with automatically generated makefiles that probably work standalone) and I'm still waiting for ideas I've asked in topic
    Attached Files Attached Files

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Another version for comparison - http://nishi.dreamhosters.com/u/rc_v3a.rar
    Its about 2x slower than fpaq0pv4b, but that's mostly a matter of obvious i/o speed optimizations.
    But enwik8 result here is 61172542.

  7. #7
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > increase = (probabilitySum - probability[selected]) / S;

    Its different in this case, though, because in fpaq0p the
    equivent of your probabilitySum remains constant... so
    the actual probability should be different.

    Still, I think it should be possible to recalculate the increment
    in such a way that the _probability_ (not just freq like in your case)
    would be updated in the same way as in fpaq0p.
    It would be likely much slower, but imho its interesting how it
    would affect the compression.

    > model mixing with non-normalized probabilites would be expensive,

    Not really.
    "Linear" mixing like (freq1*(1-w)+freq2*w)/(total1*(1-w)+total2*w)
    is quite affordable imho (especially when *w can be replaced with shifts etc).

    And if you mean having to mix all 256 freqs at once,
    its also not necessarily the case, as you can mix some kind
    of cumulative freqs instead (like using unary or binary lookup).

    But thats exactly how you end up with binary probabilities instead of freqs,
    after some optimizations

    > - one with adaptive adaptation rate,

    Btw, did you see the counter in
    http://ctxmodel.net/files/PPMd/ppmd_Jr1_sh8.rar
    defined in mod_see.inc, used in ppmd_proc2.inc ?
    Its a tricky variable-rate shift-based counter.

    > The question is: how to do that efficiently?

    I'd say, by comparing the codelengths generated by other submodels.
    In short, compute an exponentially-weighted entropy estimation for
    a model, like clen = clen*(1-wr) + LOG2[p]
    (or even (clen*=(1-wr))+=LOG2[total]-LOG2[freq] )
    But again, after trying to make it more efficient for a while,
    you're very likely to get a standard mixer from that.

    An interesting alternative though is explicit switching + optimal parsing...
    ie its possible to make an asymmetric coder which would encode extra flags
    to switch between models, and the example of lzma shows that with precise
    estimation of overall entropy its possible to minimize the redundancy
    from such a non-bijective code and reach similar compression as with simple
    mixing, while always using just a single submodel in decoder (encoder would be
    slower though).

  8. #8
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    > increase = (probabilitySum - probability[selected]) / S;

    Its different in this case, though, because in fpaq0p the
    equivent of your probabilitySum remains constant... so
    the actual probability should be different.

    Still, I think it should be possible to recalculate the increment
    in such a way that the _probability_ (not just freq like in your case)
    would be updated in the same way as in fpaq0p.
    It would be likely much slower, but imho its interesting how it
    would affect the compression.
    I think that it will end up being basically the same. The only difference is that in my scheme without renormalization only the selected symbol probability grows by a fixed fraction, while with renormalization also probabilites of non-selected symbols shrink by a fixed fraction. So the only difference is that the adaptation speed is usually slightly faster in normalizing scheme for the same constant factor.

    > model mixing with non-normalized probabilites would be expensive,

    Not really.
    "Linear" mixing like (freq1*(1-w)+freq2*w)/(total1*(1-w)+total2*w)
    is quite affordable imho (especially when *w can be replaced with shifts etc).

    And if you mean having to mix all 256 freqs at once,
    its also not necessarily the case, as you can mix some kind
    of cumulative freqs instead (like using unary or binary lookup).

    But thats exactly how you end up with binary probabilities instead of freqs,
    after some optimizations
    Yes, I mean mix all symbols at once and that's why I mentioned nibblewise model mixing. Anyway, mixing is rather incompatible with symbol exclusion, at least symbol exclusion makes things messy, slow and imprecise when mixing.

    Besides, in my nibblewise model mixing idea there would be no symbol exclusion, so renormalizing scheme could be used, then total1 could be set equal to total2 and both would be power of 2. The division would be then replaces by simple bit shift and that would cause mixing all symbols affordable - with average 8 mixings per nibble there would be on average 16 mixings per byte and that's not too far off 8 mixings in bitwise coders. With periodical symbol sorting the average number of mixings could be even reduced to less than 8 mixings in the nibblewise case.

    I'd say, by comparing the codelengths generated by other submodels.
    In short, compute an exponentially-weighted entropy estimation for
    a model, like clen = clen*(1-wr) + LOG2[p]
    (or even (clen*=(1-wr))+=LOG2[total]-LOG2[freq] )
    But again, after trying to make it more efficient for a while,
    you're very likely to get a standard mixing from that.
    Can you elaborate on that? What the variables mean? Assume, like in my original idea, that we have three o1 models: one fast adapting, one slow adapting, and one which we actually use and want to compute good learning rate for.

    An interesting alternative though is explicit switching + optimal parsing...
    ie its possible to make an asymmetric coder which would encode extra flags
    to switch between models, and the example of lzma shows that with precise
    estimation of overall entropy its possible to minimize the redundancy
    from such a non-bijective code and reach similar compression as with simple
    mixing, always using just a single submodel in decoder (encoder would be
    slower though).
    Almost sure that won't be worth the hassle. I want something rather symmetric, without excessively slowing down compression.

  9. #9
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by Shelwien View Post
    clen = clen*(1-wr) + LOG2[p]
    I'd use alen=alen*(1-wr)+w*LOG2[p]

  10. #10
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    Can you elaborate on that? What the variables mean?
    One of the many possible ways. This is used in CPVLMS. Use one fast and a slow one. Count the entropy off the two over an intervall. If the fast one was better make the real rate a little faster. If the slow one was better, make the real rate a little slower.
    Last edited by Sebastian; 1st January 2012 at 17:38.

  11. #11
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > symbol exclusion

    Btw, there _is_ a way to implement a bitwise PPM at least.
    The escape can be encoded per bit (ie ternary code basically),
    so that the model would go to the specific branch of a lower-order context,
    while all other symbols would be excluded automatically.

    > Assume, like in my original idea, that we have three o1 models

    As I said, the best way is to estimate the entropy generated
    by submodels (without actual coding), and tweak the 3rd model
    depending on results of 1st and 2nd.
    (So in a way, the 3rd model becomes a mix of 1st and 2nd,
    and trying to tweak such a nonlinear parameter as update rate
    would likely make it worse than usual mixers).
    But in such cases we can't use the total entropy, because that would
    make it too stationary. Thus new values have to be added with higher weight,
    same as with counters.
    And then, exponential weighting is not necessarily the best here
    from compression p.o.v, but surely is the most practical.

    Btw, if the "1-wr" is what you don't understand there, the idea
    is that we have a exponentially weighted sum of symbol coding costs:
    clen = Sum[ w^i*l[pos-i], i=0..pos ]
    which is incrementally computed via clen=clen*w+l.
    And w is written as (1-wr) because "wr" is my usual name for update rates,
    with common values near 0, thus (1-wr) is a little below 1.

    > I'd use alen=alen*(1-wr)+w*LOG2[p]

    That's actually the same in this case - there's no point to normalize
    the values, when the only thing that matters is their relation.

  12. #12
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Okay. Thanks for explanations.

    I understand that we have to compute after each symbol:
    ef = ef*w + log(p_ef[s])
    es = es*w + log(p_es[s])

    Where e[f|s] is weighted sum of costs in [fast|slow] model, and log(p_e[f|s]) is the cost of current symbol in [fast|slow] model, w is the decay rate.

    Now, how to compute rate_m then (m stands for 'main' there)? The problem for me is that with rate_m somewhere in between rate_f and rate_s we can have better compression than both fast and slow models. How to update rate_m then?



    Also, do you know some neat method for fast and somewhat accurate (>10 bits accuracy for example) logarithm estimation using integer arithmetics?

  13. #13
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    as stated, for example

    Code:
    ef = ef + log(p_ef[s])
    es = es + log(p_es[s])
    nsample++
    if (nsample>INTERVAL_LEN)
    {
      if (ef<es) {
        rate_m = min(rate_m+rate_max)/2,rate_max) or min(rate_m*alpha,rate_max) with alpha>1
      } else {
        rate_m = max(beta*rate_m,rate_min) with beta<1
      }
      ef=es=0
      nsample=0
    }
    so its getting faster than slower with the first variant adaption could be better.

    with a test-intervall version like this you should leave the "w"-parameter out.
    Last edited by Sebastian; 1st January 2012 at 19:37.

  14. #14
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > I understand that we have to compute after each symbol:
    > ef = ef*w + log(p_ef[s])
    > es = es*w + log(p_es[s])

    Yea, but it may be enough to compute
    dfs = dfs*w + log(p_ef[s]) - log(p_es[s])
    (btw, i imply that these are -log there actually, or log(1/p) )

    Also the common mistake in that kind of estimation is forgetting
    to switch p depending on bit value.
    Ie it should be
    p = model.probability(context); // prob of bit==1
    (e*=w) += log2( bit ? p : 1-p );

    > How to update rate_m then?

    I'd suggest something like
    rate_m = ef<es ? max(rate_f,rate_m-1) : min(rate_s,rate_m+1);
    or maybe
    squash(x) = 1/(1+exp(-x))
    rate_m = rate_f + (rate_s-rate_f)/2 * squash( (ef-es)*coef )

    > logarithm estimation using integer arithmetics?

    Code:
    void LzmaEnc_InitPriceTables( uint* ProbPrices ) {
      uint i,j;
      for( i=(1<<kNumMoveReducingBits)/2; i<kBitModelTotal; i+=(1<<kNumMoveReducingBits) ) {
        const int kCyclesBits = kNumBitPriceShiftBits;
        uint w = i;
        uint bitCount = 0;
        for( j=0; j<kCyclesBits; j++ ) {
          w = w * w;
          bitCount <<= 1;
          while( w>=(1<<16) ) { w>>=1; bitCount++; }
        }
        ProbPrices[i>>kNumMoveReducingBits] = ((kNumBitModelTotalBits<<kCyclesBits) - 15 - bitCount);
      }
    }
    "kCyclesBits" sets the precision there.
    With some adjustments I've got a full match with math.h results.

  15. #15
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    I've opted for model switching (based on weighted costs) instead of adjusting the learning rate. Computing costs takes surprisingly long time, even though I'm using small 2-KiB LUT for computing logarithms. Currently my algorithm consists of two (slow and fast) o1 models and two (slow and fast) o2 models and selects only one when coding a symbol. Maybe I'll remove one o1 model.

    My algo is awfully slow now (about 4x slower than fpaq0pv4B) but compresses rather good for a o2 coder. Currenlty it scores:
    - 37 067 568 bytes for enwik8,
    - 348 348 128 bytes for enwik9,


    I have some constants in my algorithm that I would want to tune:
    #define O1_FAST_ADAPTATION_RATE 7
    #define O1_SLOW_ADAPTATION_RATE 10
    #define O2_FAST_ADAPTATION_RATE 5
    #define O2_SLOW_ADAPTATION_RATE 8
    #define O1_COST_ADAPTATION_RATE 5
    #define O2_COST_ADAPTATION_RATE 2

    For example first one is used in updating selected symbol in o1 fast adapting model, ie prob[s] += total - prob[s] >> O1_FAST_ADAPTION_RATE. Cost adaptation rate is a log2 logarithm of the fraction of weighted sum that I'm subtracting after every symbol.

    1. What do you use for parameter optimization?
    2. Can you point me to some good order-2 (preferably mixed with order-1 also) coders?

  16. #16
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    1. What do you use for parameter optimization?
    I've used MATLAB GA Toolbox for my optimization purposes. It tunes a single bit stream which consists all tune-able parameters. As a post processing stage, I also used a random bit-flipping like optimizer to find local optimum where GA left. It worked very well. You can confirm yourself by looking BIT results
    BIT Archiver homepage: www.osmanturan.com

  17. #17
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > Computing costs takes surprisingly long time,

    That might be due to a long dependency chain.
    Explicit prefetching might help (especially with o2).
    Also maybe cost updates can be done together with counter updates,
    instead of the start of iteration.

    > My algo is awfully slow now (about 4x slower than fpaq0pv4B) but
    > compresses rather good for a o2 coder.

    o2 is completely different from o0-o1, because it doesn't fit into caches.
    So 4x slower may be actually quite good.

    > - 37 067 568 bytes for enwik8,

    The result with ppmd -o2 is 36,800,798

    > 1. What do you use for parameter optimization?

    A simple perl script which does binary search on each parameter in a loop,
    and runs the actual coder to test a parameter set.
    Somehow I never actually needed anything stronger, though.

    However, I use it in conjunction with a parameter description DSL,
    and apparently my optimization framework is much easier to use than
    all others (eg. toffer's from m1).

    > 2. Can you point me to some good order-2 (preferably mixed with order-1 also) coders?

    How about ppmd -o2, also http://compression.ru/ds/ppmsj.rar

  18. #18
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    As you only use probabilities, you can mimic PPMDs inherited frequencies by just letting higher orders prob be lower orders prob when context was not used yet, this helped my o2-coder a lot.

  19. #19
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    I've used MATLAB GA Toolbox for my optimization purposes.
    MATLAB is unfortunately a paid software and I'm not a student already so I can't play with MATLAB for free at university. Do you know something freeware (preferably Linux friendly) with decent optimization features?

    And what to optimize for? Weighted compression ratio (on some predefined corpus of subjectively interesting data) doesn't have to be the optimal function, I think, as some files like FlashMX.pdf are much harder to compress - looking at TarsaLZP results on maximumcompression.com: if I improve compressed FlashMX.pdf size by 1% then I will jump from 84'th place to 42'th place (exacly halfway) but if I improve compressed english.dic size by 1% then my position will stay the same.

    I could use a function that compares the size of output of my algorithm and eg size of paq8 output but then I see little sense in comparing to coders that have special filters, sparse contexts, etc on data that benefits from that special models for reasons similar to stated in paragraph about FlashMX.pdf - some files aren't very compressible without filters or sparse contexts, so striving to compress them better without that features would bring too little gain on that file to offset losses on other files.

    Also, in the end, TarsaLZP will have 3 layers - high order LZP, medium order SR and low order PPM. As higher order layers are basically independent from lower layers I could compute the cost of output from higher layers and optimize it separately. What function (of compressed size) should I optimize then?


    > - 37 067 568 bytes for enwik8,

    The result with ppmd -o2 is 36,800,798
    Hmmm, ppmd AFAIR uses something like SSE based on frequency rank and lots of small contexts/ flags so there's probably a high level of indirection in probabilites mapping, but anyway ppmd is a good point to start. I'll probably add order-3 symbol ranking layer in between LZP and PPM layers in upcoming TarsaLZP, so before adding LZP layer I think will have better comparison to ppmd.

    On enwik9 the differences are smaller though as ppmd -o2 scores 347 435 600 bytes, so that my compressed size is only 0.26 % larger.


    As you only use probabilities, you can mimic PPMDs inherited frequencies by just letting higher orders prob be lower orders prob when context was not used yet, this helped my o2-coder a lot.
    Good idea. I think I'll add some additional counters to o2 contexts and temporarily disable them if they were seen eg less than couple of times.
    Last edited by Piotr Tarsa; 2nd January 2012 at 16:02.

  20. #20
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Here are some ZPAQ results on enwik8 using some strictly order 2 models (no fallback or mixing with lower orders). Compression times are on a 2.0 GHz T3200, Win32. Compression times for all of the CM models are about the same (37-38 sec) so I didn't show all of them. Times are for 1 thread. For comparison:

    ppmd -o2: 36800798, 8.4 sec, 1.3 MB memory
    ppmonstr -o2: 33178379, 150 sec, 1.3 MB

    Code:
    (test.cfg)
    comp 0 1 0 0 3 (change n=3 to 1 for other models)
      (0 icm 17   (36065829, 41s))
      (0 cm 23 16 (37489742))
      (0 cm 23 8  (37133663))
      (0 cm 23 6  (37062353, 37s))
      (0 cm 23 4  (37099224))
      (0 cm 23 3  (37271166))
      (0 cm 23 2  (37803631))
       0 cm 23 4
       1 cm 23 8
       2 mix 0 0 2 32 255 (36634347, 70s)
    hcomp
      *b=a hash b++ hash *d=a halt
    post 0 end
    The commented out models are single component models (n=1). "icm 17" is an indirect context model (context -> bit history -> prediction) using 2^(17+6) = 8M histories of 1 byte each. "cm 23 n" is a direct context model (context -> prediction) with 2^23 = 8M entries (32 MB) and update rate of max(1/count, 1/(4*n)), so higher numbers adapt slower. The optimal rate is 6 (1/24). The uncommented model mixes 2 cm's on either side of the optimal rate with an order -1 (no context) mixer and a weight learning rate of 32/4096 (higher numbers are faster), which I tuned on enwik7 for best compession. The other parameters are 0 (number of context bits), 0 (start of input range), 2 (number of inputs) and 255 (order 0 context mask, irrelevant in this case).

    The COMP parameters 0 1 select the array sizes H[2^0=1] and M[2^1=2]. I use M as a rotating history buffer of the last 2 bytes from which the context hash is computed and put in H[0]. All of the components share this context.

    The HCOMP code is called after coding each byte with that byte in the A register. *B=A stores A in M[B mod 2]. HASH computes (A=A+*B+512)*773. *D=A stores A in H[D mod 1].

    To compress I used: "zpaq -mtest c x \res\enwik8" to create x.zpaq. (You may get a slightly different result depending on the path length to enwik.

  21. #21
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > Do you know something freeware (preferably Linux friendly) with
    > decent optimization features?

    In fact its frequently not a good idea to use an universal optimization engine for this.
    It would be much more likely to test all kinds of weird corner cases, and would probably
    stop early enough. Well, that's what most people want it to do though, but its clear that
    a compressor optimization can't converge without even testing all the parameter bits.

    Anyway, I can give you my optimization scripts - they're written in perl, so would work
    in linux too. But you're probably better off writing some of your own.
    You've tried tweaking it manually, right? How about automating that process?

    > And what to optimize for? Weighted compression ratio

    In most cases I used book1, book1bwt, or book1+wcc386 as optimization targets.
    Well, also the whole SFC set in lzmarec.
    I guess, most of my models are slow enough so that carefully choosing
    the optimization target wasn't really an option.

    But actually I never thought of integrating any weighted metrics
    into the optimizer - it just looks at the compressed file size.
    We can always compress multiple files into a single archive,
    and also adjust individual sample sizes to fix up the metric,
    so imho there's no need to add extra dependencies to the optimizer.

    Btw, in some cases I also included the memory size to the metric,
    but that was done by adding something like this to the actual coder:
    Code:
    fseek( out, (memoryused>>12)-1, SEEK_CUR );
    putc( 0, out);
    > if I improve compressed FlashMX.pdf size by 1% then I will jump from
    > 84'th place to 42'th place (exacly halfway) but if I improve
    > compressed english.dic size by 1% then my position will stay the same.

    In a way, you are right here, as a different metric (eg. min sum of places in maxcomp)
    would produce different results.

    But imho you can think about that after getting it to work at all,
    and plain compressed size of a single file (like enwik or something)
    should be good enough for that.

    > Also, in the end, TarsaLZP will have 3 layers
    > What function (of compressed size) should I optimize then?

    Simple reduction in compressed size is good enough imho,
    the absolute value doesn't matter.

    > Hmmm, ppmd AFAIR uses something like SSE based on frequency rank

    Only ppmonstr has SSE.
    ppmd only has SEE (ie separate binary models for escape flags),
    so there's nothing wrong with it

    > On enwik9 the differences are smaller though as ppmd -o2 scores 347
    > 435 600 bytes, so that my compressed size is only 0.26 % larger.

    ppmd has additional options like -m and -r, so that may be not
    the best result on enwik9.

    > Good idea. I think I'll add some additional counters to o2 contexts
    > and temporarily disable them if they were seen eg less than couple
    > of times.

    ppmd does that at symbol level though.
    Afair it tries to assign the new freq in such a way that
    the symbol would initially have the same probability as it previously
    had with escape(s)+lower-order freq/total.
    And with freqs, that's a bit tricky.

  22. #22
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    In my case, initially MATLAB generates a random bit string and runs a small utility to patch my compressor executable with that bit string. In compressor source, I've intentionally left a code portion that can be found with a signature and then can be patched. After patching, my compressor runs on a target (for some small improvements, I usually used book1+wcc386, if it yields better result I do a final optimization with whole SFC). Whole SFC optimization takes a very long time which varies between 7-14 days with non-stop working on my laptop (I've permanently damaged a MacBook Pro with that ). Optimization function was not any kind of approximation. It was basically compressed size. But, it's better to integrate Shelwien's metric function or similar (compressing time + transmission time + decompressing time). One of the most important thing, GA or similar algorithms deals in a quite large solution space. So, they could never converge. If improvements becomes very very small, you should run a separate algorithm to squeeze last few KiB. In my case, I've used Shelwien's script like approach (bit-flipping).

    My method advantages:
    1. I don't need deal GA stuff. There is an already working framework.
    2. I can even use vectorized GA with a single option, which runs parallel my compressor, thus shorter optimization time.
    3. GA is good for such optimization.

    Disadvantages:
    1. Toffer's optimizer can converge faster, due to custom operators e.g. non-linear quantization table optimization which is a hard problem in my case.
    2. MATLAB is very bloated application and it's very resource hungry. I can't use it on all of my computers. A simple console application would be better.
    3. Patching and creating output compressed archive each time cause huge amount of I/O operation. Thus a RAM drive could be better.
    BIT Archiver homepage: www.osmanturan.com

  23. #23
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Thanks for comments.

    I'll deal with GA soon (hopefully), after adding SR and LZP. But now there're still ways to improve PPM

    Matt:
    Thanks for comparisons and script. It will be a helpful tool. But I still think ICM is adding more information than simple frequencies or counters. AFAIU ICM to CM is like fpaq0f to fpaq0p. And there are controversies about fpaq0f being truly order-0. Anyway, it's not a dealbreaker. State maps are simple and elegant way to deal with a lot of problems at once, but certainly not feasible with bytewise coding and probably don't bring much benefit when having also higher order models at the same time.

    My coder, without much optimizations, is less than twice as slower than PPMd -o2 (on my AMD E-350), which AFAIR does frequency sorting that should improve speed considerably on compressible data. So that's much better than ZPAQ does, although maybe ZPAQ's JIT isn't optimized for low order coding.

    Code:
    piotrek@msi-wind:~$ cd Pulpit/enwik/
    piotrek@msi-wind:~/Pulpit/enwik$ time ~/NetBeansProjects/cTarsaLZP/dist/Release/GNU-Linux-x86/ctarsalzp c enwik8 enwik8.ari
    
    real	0m42.466s
    user	0m40.955s
    sys	0m0.932s
    piotrek@msi-wind:~/Pulpit/enwik$ time ppmd/PPMd e -m256 -o2 enwik8
    Fast PPMII compressor for textual data, variant J, Dec 18 2011
    enwik8.pmd already exists, overwrite?: <Y>es, <N>o, <A>ll, <Q>uit?y
            enwik8:100000000 >36800776, 2.09 bpb, used:  1.3MB, speed: 4663 KB/sec 
    
    real	0m25.485s
    user	0m20.577s
    sys	0m0.376s
    piotrek@msi-wind:~/Pulpit/enwik$ time ~/NetBeansProjects/cTarsaLZP/dist/Release/GNU-Linux-x86/ctarsalzp d enwik8.ari enwik8.dec
    
    real	0m49.282s
    user	0m47.367s
    sys	0m1.228s
    piotrek@msi-wind:~/Pulpit/enwik$ time ppmd/PPMd d enwik8.pmd
    Fast PPMII compressor for textual data, variant J, Dec 18 2011
    enwik8 already exists, overwrite?: <Y>es, <N>o, <A>ll, <Q>uit?y
            enwik8:36800776 >100000000, 2.09 bpb, used:  1.3MB, speed: 4105 KB/sec 
    
    real	0m31.470s
    user	0m23.221s
    sys	0m0.600s
    piotrek@msi-wind:~/Pulpit/enwik$
    ppmd has additional options like -m and -r, so that may be not
    the best result on enwik9.
    I've used -o2 and -m256 so that there was no model restart/ cut-off to make comparison as fair as possible.




    I have another idea for adaptive disabling. Instead of disabling either o2 model based on total frequency (temporarily do not use models of contexts that were rarely seen in the whole process before), I could compute weighted sum of intervals between o2 context occurences. I would use a simple timestamps to compute interval length. I would eg maintain two weighted interval sums - one will give higher weight to recently incoming interval than another. Then I would have to convert the relation between those two sums to a decision of disabling particular o2 model temporarily. Maybe use some APM to convert history of recent weighted intervals sums relations and current relation of weighted interval sums to a decision about disabling particular 02 model.


    Besides, development/ research probably will be slowed down for a while as I'm moving and additionally my netbooks's cooling system is likely broken.

  24. #24
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    ZPAQ bit histories are tuned for higher order models. For low order, simply using the last 8 bits as the bit history works better. However, ZPAQ does not have such a model.

    Also there is some extra overhead. ZPAQ computes and stores SHA-1 checksums. It compresses to a temporary file and then appends it to the archive. Also, the CM includes both a prediction and a count. The count indexes a table to get the learning rate and then multiplies by the prediction error, rather than using a simple shift like fpaq0f2.

    I'm considering updating the ZPAQ standard to level 2 to support fast compressors. The idea would be to omit the context model and keep just the post-processor (written in ZPAQL). The preprocessed data would be stored otherwise uncompressed. This would be equivalent to compressing a string as an arbitrary program plus its input data which writes the string. The changes to libzpaq should be fairly minimal and it would support arbitrary compression algorithms.

  25. #25
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > I've used -o2 and -m256

    Ok, but what about ppms?
    It should be faster - http://compression.ru/ds/ppmsj.rar

    > decision about disabling particular 02 model

    As I said, its not really a good idea. Why not just recompute the "bad" freq from lower orders, like ppmd does?
    Disabling a whole context won't let it work where it could too.

  26. #26
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Ok, but what about ppms?
    It should be faster - http://compression.ru/ds/ppmsj.rar
    No Makefile for GCC and problems compiling under Ubuntu

    As I said, its not really a good idea. Why not just recompute the "bad" freq from lower orders, like ppmd does?
    Disabling a whole context won't let it work where it could too.
    I've talked about disabling for coding a specific symbol not disabling permanently or for a long run. Remember that I'm using switching between models, so disabling is generally equal to preventing switching to a particular model.

    How and how often would you do recomputing? Recomputing one symbol would take at least one division as probabilites aren't normalized. So it could mean low gain for high cost.


    Matt:
    I believe that bit histories in you ICM and my idea about pair of weighted intervals sum estimators share some ideas.

    Mainly, bit histories + APM allows for automatic detection of local stationarity - if we're in nonstationary region in the file then APM will favor the most recent part of bit history and if we're in a stationary region then entire bit history would be beneficial for computation.

    My pair of weighted intervals sum estimator should bring at least some advantages of ICM. Having two estimators - one quickly adapting and one slowly adapting, we can detect if the data type has changed recently. My intuition is that if some context suddenly appears less often (ie quickly adapting estimator shows bigger interval length that slowly adapting one) then we should favor slowly adapting model and, by analogy, if some context suddenly appears more often then we should favor quickly adapting model.

    The problem is that I don't know if my intution is true and I don't have a complete idea of how to use that homogenity estimation and also how (and if) should it affect model updating. There are also four models in total, so multiplying weighted costs (because that's used for switching between models) from only o2 models will render o1 models unusable. I need to sort that out.

  27. #27
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    http://nishi.dreamhosters.com/u/ppmsj_sh0.rar
    http://nishi.dreamhosters.com/ppmsj_sh0/
    Compile PPMs.cpp there, like "g++ -O3 PPMs.cpp"

    > How and how often would you do recomputing?

    Usually once - when the symbol occurs for the first time in the context.

  28. #28
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    I have checked what would be the result with ideal switching. Results are estimated as I've used my low precision logarithm estimator (on random input it has less than 0.01 % error so that should be enough).

    Results for enwik8:

    All four models ideally switched: 31 420 078 bytes
    O2 models ideally switched with o1 models disabled: 33 813 520 bytes
    Only slow o2 model: 38 223 691 bytes
    Only fast o2 model: 38 391 744 bytes

    Recall that current working result is: 37 067 568 bytes

    Results are quite surprising for me. It seems that idea of switching based on weighted costs either is broken or insufficient. I have also a bug in code that causes the o2 models to be heavily favored to o1 models and after fixing that bug compression gets worse. So actually it seems that explicit switching could give a gain! But I'm not into it. I will search for better switching methods, probably not using cost estimation as it's too slow (though maybe someone have a fast routine for that that he's going to share).

    I have thought about using that weighted interval sums. Currently my idea is to quantize the ratio of fast and slow adapting weighted interval sums and map that using APM to a cell containing four probabilites (probability of each submodel to be the best). For example quantize o2slowsum / o2fastsum to 8 values. I could quantize also o1slowsum / o1fastsum to eg 4 values and make a 32 bin 2D SSE. I could also quantize current o2 interval length as next APM dimension. Finally I could store last permutation (or two) per o2 context of the order of probabilities (ie. the order of probabilites from all four submodels - there would be 4! = 24 permutations). I need to test that and see if that will work.

    In the meanwhile I'm attaching current source code (Linux binaries included).


    And PPMs is indeed faster than PPMd, but not much:
    Code:
    piotrek@msi-wind:~/Pulpit/enwik$ time ppmsj_sh0/PPMs e -o2 enwik8
    Small PPMII compressor with 1024KB memory heap, variant J, Jan  6 2012
            enwik8:100000000 >36866726, 2.09 bpb, CutOffs:  5, speed: 5083 KB/sec  
    
    real	0m19.855s
    user	0m18.801s
    sys	0m0.412s
    piotrek@msi-wind:~/Pulpit/enwik$ time ppmd/PPMd e -m256 -o2 enwik8
    Fast PPMII compressor for textual data, variant J, Dec 18 2011
            enwik8:100000000 >36800776, 2.09 bpb, used:  1.3MB, speed: 4654 KB/sec 
    
    real	0m22.506s
    user	0m20.509s
    sys	0m0.504s
    piotrek@msi-wind:~/Pulpit/enwik$

    After quick investigation: Those "ideally switching" results are probably meaningless as they are getting too good with some crazy update ratios.
    Attached Files Attached Files
    Last edited by Piotr Tarsa; 6th January 2012 at 05:05.

  29. #29
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    I presume you're not coding any model ids in your "ideal switching".
    Like that its certainly worthless, because such a switching between submodels which give p=0 and p=1 would compress everything to zero.
    The real "ideal switching" is called mixing.
    It makes use of the fact that information about which submodel is the best for next symbol is unnecessary for us,
    and simply adjusts the probability distribution of actual symbols taking into account the p.d. of submodel selection.
    Thus switching is always worse than mixing based on the same model.
    Basically mixing is just a more efficient method of coding for switching, which lets us to encode the actual symbols
    with exactly the same entropy, while skipping the coding of submodel choice.

    However, there're also some benefits in explicit switching too.
    1. Mixing is always symmetric, but switching lets us build formats with faster decoding.
    Good parsing optimization would even minimize the redundancy from explicit model choice coding to a negligible value.
    With update exclusion, it can actually show better results than mixing.
    2. Redundancy can be avoided if the information given by submodel choice is removed from the p.d. of symbols,
    ie masking is applied. Knowing which submodel is the best for the next symbol, we can locate symbols for which its the best,
    fix up their probabilities, and only encode the information yet unknown to the decoder.
    Its kinda similar to what PPM does.
    But this approach is also symmetric and relatively complicated, so CM is usually preferred.

  30. #30
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Let w_1, ..., w_n be the probabilities that the (next) symbol x is drawn according to the distribution p_i(x), 0<i<=n.


    1. Mixing

    We defined the linear mixture probability for x to be

    p(x) := w_1 p_1(x) + ... + w_n p_n(x).

    The (expected) code length for x is exactly

    -log2( p(x) ).


    2. Switching

    We select model "i" with probability w_i. The expected code lenght is

    - w_1 log2(p_1(x)) - ... - w_n log2(p_n(x))

    = -log2( p_1(x)^w_1 p_2(x)^w_2 ... p_n(x)^w_n )

    >= -log2( w_1 p_1(x) + ... w_n p_n(x) ) [Jensens inequality]

    = -log2( p(x) ).


    Thus, in expectation mixing is never worse than switching.


    PS: i'd really appreciate TeX support.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

Similar Threads

  1. Replies: 18
    Last Post: 5th November 2007, 12:12

Posting Permissions

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