Page 1 of 2 12 LastLast
Results 1 to 30 of 31

Thread: Hutter Prize submission

  1. #1
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts

    Hutter Prize submission

    Alexander Rhatusnyak has posted a Hutter Prize submission to https://sites.google.com/site/lossle...P_2017_May.zip
    The submission is open for a 30 day comment period before a prize is awarded according to the rules at http://prize.hutter1.net/

    The submission consists of a compressed file and a decompressor as a 64 bit Linux executable. The total size is slightly over 3% smaller than the previous submission made 23 May 2009. In my test, decompression takes 8 hours and 10 minutes on a 2.67 GHz Core i7 M620 with 4 GB memory running 64 bit Ubuntu. The program uses 1 GB memory and a 1 GB temporary file. EDIT: 256 MB temporary file.

    15,420,822 compressed_enwik8
    49,992 phda
    15,470,814 total size

    The previous best submission was 15,949,688 bytes. New submissions must improve by at least 3%.

    To run: ./phda compressed_enwik8 enwik8.out
    A progress counter will count to 110.
    Last edited by Matt Mahoney; 3rd June 2017 at 19:04.

  2. The Following 6 Users Say Thank You to Matt Mahoney For This Useful Post:

    byronknoll (3rd June 2017),Christoph Diegelmann (3rd June 2017),Darek (6th June 2017),JamesB (5th June 2017),RamiroCruzo (3rd June 2017),Simorq (8th September 2017)

  3. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    Any more information about the algorithm?

    1. Linux/x64/SSE was a bad choice - unpacked exe size is ~108k,
    while previous version was only ~34k.
    Also, unpacked phda_ram can be compressed from 49,936 to 35,345 with paq8p-6

    Should be possible to save 10-20k more using VC6 on windows instead.

    Btw, linux/x64 binaries don't make reverse engineering harder -
    more like it helps.

    2. Header generation:
    " <timestamp>%d-%02d-%02dT%02d:%02d:%02dZ</timestamp>\n",

    3. mod_ppmd confirmed, so I didn't post it for nothing :)

    4. no mod_SSE or paq_rc though. Maybe perl scripts helped at least?

  4. The Following 3 Users Say Thank You to Shelwien For This Useful Post:

    byronknoll (3rd June 2017),schnaader (3rd June 2017),xinix (4th June 2017)

  5. #3
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Hopefully Alexander Rhatushnyak will comment on the program. He used a Linux executable because a Windows executable, although smaller when compressed with Upack, did not meet the time requirements due to going through Wine for random disk access. (I would prefer the contest allowed source code).

  6. The Following User Says Thank You to Matt Mahoney For This Useful Post:

    schnaader (3rd June 2017)

  7. #4
    Member
    Join Date
    Dec 2014
    Location
    Berlin
    Posts
    29
    Thanks
    36
    Thanked 26 Times in 12 Posts
    I think the rules should be changed to require source code submission to reproduce the binary submission - not only for scientific reasons but also for security (But maybe running random executables from the net is a Windows habit in this forum which I will never understand).

  8. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    > Windows executable, although smaller when compressed with Upack, did not meet the time requirements

    This is your problem, sorry. Please test it on native windows.
    prize.hutter1.net clearly says "Create a Linux or Windows executable".
    There's nothing about running windows executables under emulation and then applying time constraints.

    > compressed with Upack

    That's hardly the best compressor.
    Please at least try
    http://www.crinkler.net/
    http://www.farbrausch.de/~fg/kkrunchy/

  9. The Following User Says Thank You to Shelwien For This Useful Post:

    xinix (4th June 2017)

  10. #6
    Member
    Join Date
    Mar 2015
    Location
    Germany
    Posts
    57
    Thanks
    34
    Thanked 38 Times in 15 Posts
    > In my test, decompression takes 8 hours and 10 minutes on a 2.67 GHz Core i7 M620.

    Hardly seems to fit "Must run in <10 hours on a 2GHz P4".

  11. #7
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    P4 also doesn't support x64/SSE4 :)

    I never considered these requirements to be fair though.
    In this case, I'm much more concerned about the fact that the result could be 20-30k better,
    using VC6/x86 + better exe compressor on windows.

  12. #8
    Member
    Join Date
    Mar 2015
    Location
    Germany
    Posts
    57
    Thanks
    34
    Thanked 38 Times in 15 Posts
    I think that it doesn't meet official time requirements which disqualifies it as much as using too much RAM is more of an concern than "a few" bytes that everyone can shave off with a publicly available tool.

  13. #9
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    > I think that it doesn't meet official time requirements

    Well, what Matt posted _does_ meet the requirements - 8h is less than required 10h.
    Sure, P4 would be slower, but then we could use some fast SSD with it - there're no requirements about storage type.

    Also, you can't properly apply crinkler without source - its a linker replacement.

    And with extra 30k, I'd not be surprised if its possible to reduce the size of hashtable (or ppmd tree) at the cost of worse compression, and thus fit in 1G
    without swapping, or whatever it does.

  14. #10
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    Apparently they changed the rules: http://prize.hutter1.net/hrules.htm

  15. #11
    Member
    Join Date
    Mar 2015
    Location
    Germany
    Posts
    57
    Thanks
    34
    Thanked 38 Times in 15 Posts
    So they changed it to exactly fit the submission. Seriously?

  16. #12
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    Well, it looks like they did it at least a month before - http://web.archive.org/web/201705052...net/hrules.htm

  17. #13
    Member
    Join Date
    May 2008
    Location
    France
    Posts
    79
    Thanks
    461
    Thanked 22 Times in 17 Posts
    Quote Originally Posted by Christoph Diegelmann View Post
    So they changed it to exactly fit the submission. Seriously?
    Quote Originally Posted by Shelwien View Post
    Well, it looks like they did it at least a month before - http://web.archive.org/web/201705052...net/hrules.htm
    And Last-Modified: Mon, 29 May 2017 23:51:27 GMT

  18. #14
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    Here I tried diffing 05-May version with current one ('<' lines are old version, '>' new).
    Code:
    196,197c70
    <       </li><li>Documented source code of (de)compressor and usage/compilation instructions and all other relevant files must be made available to the H-prize committee.</li>
    ---
    232,234c105,108
    <       <li>Description of the test machine (processor, memory, operating system). </li>
    <       <li>Links where files can be downloaded. </li>
    ---
    >       <li>Description of the test machine (processor, memory, operating system). </li>
    >       <li>Links where files can be downloaded:<br>
    >              Executables and documented source code of (de)compressor and all other relevant files.</li>
    >       <li>Usage/compilation instructions.</li>
    238,239c112
    <     inner workings of the (de)compressor, the source code, etc, is highly appreciated. </a>
    ---
    >     inner workings of the (de)compressor, is highly appreciated. </a>
    I guess Alex didn't agree to give the source even to Matt :)

  19. The Following 3 Users Say Thank You to Shelwien For This Useful Post:

    JamesB (6th June 2017),RamiroCruzo (5th June 2017),willvarfar (8th June 2017)

  20. #15
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    459
    Thanks
    144
    Thanked 158 Times in 106 Posts
    Quote Originally Posted by Christoph Diegelmann View Post
    So they changed it to exactly fit the submission. Seriously?
    To be fair, I'm sure Matt changed it to fit his own hardware as the time limit is hard to enforce otherwise. I think this is reasonable and it also promotes more research as over time CPUs become more powerful and what would once have been inappropriate time becomes more acceptable.

  21. #16
    Member
    Join Date
    Mar 2015
    Location
    Germany
    Posts
    57
    Thanks
    34
    Thanked 38 Times in 15 Posts
    Quote Originally Posted by Shelwien View Post
    Well, it looks like they did it at least a month before - http://web.archive.org/web/201705052...net/hrules.htm
    I looked it up before I was posting about it because I was unsure about how many GHz the P4 has in order to check if 8h 10min is within a somewhat reasonable time for 10h P4 (it's not). On the front page at least it's still

    Restrictions: Must run in <10 hours on a 2GHz P4 with 1GB RAM and 10GB free HD.


    Quote Originally Posted by JamesB View Post
    To be fair, I'm sure Matt changed it to fit his own hardware as the time limit is hard to enforce otherwise. I think this is reasonable and it also promotes more research as over time CPUs become more powerful and what would once have been inappropriate time becomes more acceptable.
    I'm totally agreeing that updating the prize to a more modern requirement would be interessting even though it makes it harder to track how the algorithms improve over time. Changing it to fit a certain submission is what's absolutely not acceptable. Would it have been changed if someone else had posted it ? Maybe even a few years earlier ? I think if there's enough money for a price than there should be enough money to keep the requirements constant (e.g. keep the original pc). At least the score is now somewhat future proof.

    Too make my point clear: An Intel P4 630 (from Q4'2005) has a a Geekbench4 score of around 900. That means with the new rules the programs would be allowed to take 22 hours on the old machine instead of 10. And the P4 630 has 3 GHz instead of 2 ! That means this is an effective trippling of the allowed time which means the new submission would be nowhere within the original rules.

  22. #17
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    I really don't care that much about time and memory.
    I think that forcing Alex to write custom swapping as a workaround for memory limit is plain dumb - it has no relation to compression or AI for sure.

    But what's more interesting is algorithm description.
    For example, I suspect that there's some influence from cmix in this version - there's a lot of float-point code in phda, and cmix has a float-point model.
    So maybe Alex used LSTM mixer from cmix, or some such.
    But he doesn't want to share the source, and doesn't want to describe the algorithm.
    Is that okay?

  23. The Following User Says Thank You to Shelwien For This Useful Post:

    willvarfar (8th June 2017)

  24. #18
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    We had some discussion about the rules, but Marcus Hutter is funding the prize so he has the final decision. We did agree to change the hardware requirements to a newer machine I can actually test on, and it (barely) passed.

    Originally LTCB and Hutter prize were to be the same but we disagreed on the rules. I wanted to allow unlimited hardware but you can see the problem if you give prize money. I also allow either source or executables.

    I tested several earlier submissions which were too slow. You could also argue that using a temporary file for the disk cache space wouldn't work on a machine that only had 1 GB of actual RAM. I'd rather just see the hardware restrictions relaxed to keep up with modern computers.

  25. The Following 2 Users Say Thank You to Matt Mahoney For This Useful Post:

    schnaader (9th June 2017),willvarfar (10th June 2017)

  26. #19
    Member
    Join Date
    Mar 2011
    Location
    USA
    Posts
    226
    Thanks
    108
    Thanked 106 Times in 65 Posts
    I asked Alex for some more information about the program. Here is his reply:

    16 facts about the algorithm.

    1. Overall it's a hugely improved algorithm of the previous (2009) submission, with a couple new features.
    2. Everything was revised, from pre-DRT enwik-specific preprocessing, to arithmetic coder.
    3. The latter is simpler than before, because Predictor returns a floating-point number:
    U32 d = (U32)((x2_ - x1_) * predictor->predict()), xmid = x1_ + d;

    4. There are floating-point mixers that operate basically on the same input as
    fixed-point mixers, plus or minus a percent or so, and
    5. a floating point SSE, that's why predictor->predict() returns a f.p. number.
    6. Enwik-specific preprocessing is about twice more complex than in 2009.
    7. The NLP part of the algorithm (DRT mostly) is still rather primitive.
    8. There's a ppmd implementation (with order 7 and 247.125 Mb memory allocated), and

    9. it's the least efficient memory user in the submission code. In March when RAM + scratch file
    were close to 2 GiB, it was not, but now when RAM + scratch file = 1.25 GiB, every other
    component is much more memory efficient. So if I had a couple more months,
    ppmd would be either eliminated completely, or made more memory efficient.

    For example, RestoreModelRare() leaves about half of allocated memory unused. This happens thrice.
    10. A big number of contexts are of the form "Condition? 0 : something" - this helps reduce memory usage.
    Especially the most important contexts, used by models that consume more memory than the average.
    11. Almost half of contexts are using the compressed 2-bit and 3-bit representations of symbols:
    U32 DRT_to3bits[256]= {
    0,0,0,0,0,0,0,4, 6,2,0,0,3,0,0,0,
    // 14 lines skipped
    7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,
    };
    and then s3bits = DRT_to3bits[symbol]. Such representations are really ubiquitous in the code.
    12. There is a tiny LSTM implementation, it's used in one place in the code,
    but I think it could be* used in three places, including SSE.
    * if HDD in Matt's Dell E6510 was as fast as an SSD, and decompression time was close to 5 hours.

    13. Unlike lpaq9, there are just two types of state tables, both are 8-bit ST's.
    One is sort of "for stationary models", another "for non-stationary".
    14. An alphabet reorder is present, but it could be much better than now.
    After DRT there are no capital letters, that's why more than 35 symbols are never used.

    15. There are 105 models currently (the version to be released at the end of June), and
    16. they produce 450 probabilities.

    the name phda evolved from HPDec, and it currently stands for Pack Hundred Days Ahead

  27. The Following 7 Users Say Thank You to byronknoll For This Useful Post:

    Bulat Ziganshin (8th January 2018),encode (2nd August 2017),hexagone (11th June 2017),Kai Sandfort (11th June 2017),Mike (11th June 2017),Shelwien (11th June 2017),xinix (11th June 2017)

  28. #20
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    > 16 facts about the algorithm.

    Cool, finally we have some info - somehow Matt didn't have any.

    > it's [ppmd] the least efficient memory user in the submission code.

    Sure, as ppmd requires ~18N memory.

    There multiple ways to save memory in ppmd.

    1. PPM_CONTEXT removal.

    Afair Shkarin did this in ppms - ppmd has separate
    "context" structures, which hold pointers to actual symbol tables.
    Once upon a time, it made some sense as a speed optimization.

    And now we can merge context structures with symbol tables, and
    thus save 4 bytes per context.

    Also, NumStats, Flags, SummFreq fields are not very efficient
    either - NumStats can be removed by using separate memory pools per NumStats value,
    Flags are not very useful in ppmd in any case, and SummFreq is 16-bit, which could be reduced
    (maybe merged with some flags).

    2. Dynamic context reconstruction.

    Like in https://encode.su/threads/541-Simple...xt-mixing-demo
    But its also possible to cache frequently used contexts.

    3. Stats compression

    Ppmd symbol tables are stored sequentially, so we can apply some compression there.
    Maybe convert symbol codes and suffix pointers into deltas with variable-length codes.

    4. BWT-based data structures

    Its actually possible to compute BWT incrementally, by shifting input data around.
    Obviously its slow, but likely faster than swapping, and only needs 5N memory.

    Though in this case, its easier to drop the PPM idea, and just use BWT data
    to dynamically compute the stats for prediction, by scanning BWT symbols
    around current position and passing them to a postcoder model.

    > So if I had a couple more months, ppmd would be either eliminated completely,
    > or made more memory efficient.

    Eliminating it could be nice too - I still don't understand why it improves
    the paq model so much. But somehow it seems unlikely.

    > For example, RestoreModelRare() leaves about half of allocated memory unused.
    > This happens thrice.

    Actually its controlled by this code:
      // free up 25% of memory
    do {
    PrepareTextArea();
    cutOff( MaxContext[0], 0, _MaxOrder ); // MaxContext is a tree root here, order0
    ExpandTextArea();
    } while( GetUsedMemory()>3*(SubAllocatorSize>>2) );

    3*(N>>2) = 3*N/4 = 0.75*N - its an arbitrary value,
    maybe it can be tweaked to improve overall results,
    like run it 2 times instead of 3.

    Another solution is completely resetting the model, then
    updating the model with 90% (or whatever you want) of already decoded data.
    As a bonus, stats also would be more precise like this.

  29. The Following 4 Users Say Thank You to Shelwien For This Useful Post:

    Bulat Ziganshin (8th January 2018),Matt Mahoney (12th June 2017),Mike (11th June 2017),xinix (11th June 2017)

  30. #21
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    237
    Thanks
    38
    Thanked 92 Times in 48 Posts
    An improved version is here. 7 hours 41 minute instead of 8:10, and 3.4% improvement instead of 3.0%

    This newsgroup is dedicated to image compression:
    http://linkedin.com/groups/Image-Compression-3363256

  31. The Following 5 Users Say Thank You to Alexander Rhatushnyak For This Useful Post:

    byronknoll (3rd August 2017),encode (2nd August 2017),Jyrki Alakuijala (3rd August 2017),Matt Mahoney (2nd August 2017),Shelwien (2nd August 2017)

  32. #22
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,269
    Thanks
    200
    Thanked 985 Times in 511 Posts
    Can you write some description for the new version, like what Knoll posted before?
    Its interesting to know whether my previous post here helped, etc.

  33. #23
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Verified on my Dell E6510 in 64 bit Linux.

  34. #24
    Member
    Join Date
    Mar 2011
    Location
    USA
    Posts
    226
    Thanks
    108
    Thanked 106 Times in 65 Posts
    Quote Originally Posted by Alexander Rhatushnyak View Post
    An improved version is here. 7 hours 41 minute instead of 8:10, and 3.4% improvement instead of 3.0%
    Nice improvement! Any plans to release the source code? I bet there are a lot of components and implementation details that would help improve other compression programs.

  35. #25
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    237
    Thanks
    38
    Thanked 92 Times in 48 Posts
    > whether my previous post here helped

    Not yet. Nothing new with ppmd memory usage.

    > Any plans to release the source code?

    No. Maybe next year, and more likely only some components.

    This newsgroup is dedicated to image compression:
    http://linkedin.com/groups/Image-Compression-3363256

  36. The Following 2 Users Say Thank You to Alexander Rhatushnyak For This Useful Post:

    Jyrki Alakuijala (1st September 2017),samsat1024 (26th October 2017)

  37. #26
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    237
    Thanks
    38
    Thanked 92 Times in 48 Posts
    Here is a dictionary that seemingly works better for enwik8 (and maybe enwik9)
    than the dictionary from paq8hp12.
    The latter is a little bit damaged: you can find a long sequence of 0's in the middle of it, right after 'yearwa@'.
    And as far as I can see, cmix uses a bit-exact copy of the damaged dictionary from paq8hp12.
    Attached Files Attached Files

    This newsgroup is dedicated to image compression:
    http://linkedin.com/groups/Image-Compression-3363256

  38. The Following 2 Users Say Thank You to Alexander Rhatushnyak For This Useful Post:

    byronknoll (31st August 2017),Jyrki Alakuijala (1st September 2017)

  39. #27
    Member
    Join Date
    Mar 2011
    Location
    USA
    Posts
    226
    Thanks
    108
    Thanked 106 Times in 65 Posts
    Thanks Alex. I tried using the new dictionary with cmix on enwik8:

    damaged dictionary: 15291981
    new dictionary: 15297535

    Unfortunately the results are a bit worse. Perhaps cmix has some over-fitting with the damaged dictionary...

  40. #28
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    237
    Thanks
    38
    Thanked 92 Times in 48 Posts
    Maybe it's also because in phda
    1. There's an enwik-specific pre-processing,
    2. Dictionary is compressed after the main data, it's not used for pre-training, and
    2a. the biggest part of dictionary (40960/44880 words) is in the barely-sorted state, as in to_train_models.dic from paq8hp12
    Last edited by Alexander Rhatushnyak; 2nd September 2017 at 04:27. Reason: correction: unsorted => barely-sorted

    This newsgroup is dedicated to image compression:
    http://linkedin.com/groups/Image-Compression-3363256

  41. #29
    Member
    Join Date
    Mar 2011
    Location
    USA
    Posts
    226
    Thanks
    108
    Thanked 106 Times in 65 Posts
    Any updates on the prize? http://prize.hutter1.net/ hasn't been updated.

  42. #30
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    237
    Thanks
    38
    Thanked 92 Times in 48 Posts
    3.88% improvement was confirmed on Oct.1,
    and there'll be a ~4.2 % next week.

    This newsgroup is dedicated to image compression:
    http://linkedin.com/groups/Image-Compression-3363256

  43. The Following 2 Users Say Thank You to Alexander Rhatushnyak For This Useful Post:

    encode (26th October 2017),Mike (26th October 2017)

Page 1 of 2 12 LastLast

Similar Threads

  1. the ZPAQ Prize
    By calthax in forum Data Compression
    Replies: 10
    Last Post: 19th August 2014, 22:34
  2. US$3 Million Data compression Prize
    By LawCounsels in forum The Off-Topic Lounge
    Replies: 30
    Last Post: 2nd May 2012, 18:26
  3. Hutter prize awarded
    By Matt Mahoney in forum Data Compression
    Replies: 2
    Last Post: 19th August 2009, 21:17
  4. Alexander Rhatushnyak wins Hutter Prize!
    By LovePimple in forum Forum Archive
    Replies: 1
    Last Post: 5th November 2006, 18:04
  5. The Hutter Prize
    By LovePimple in forum Forum Archive
    Replies: 7
    Last Post: 22nd September 2006, 12:28

Posting Permissions

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