Hutter Prize

Last updated

The Hutter Prize is a cash prize funded by Marcus Hutter which rewards data compression improvements on a specific 1 GB English text file, with the goal of encouraging research in artificial intelligence (AI).

Contents

Launched in 2006, the prize awards 5000 euros for each one percent improvement (with 500,000 euros total funding) [1] in the compressed size of the file enwik9, which is the larger of two files used in the Large Text Compression Benchmark (LTCB); [2] enwik9 consists of the first 109 bytes of a specific version of English Wikipedia. [3] The ongoing [4] competition is organized by Hutter, Matt Mahoney, and Jim Bowery. [1]

As of 2018, the text data of enwik8 and enwik9 remains a key tool for evaluating the performance of compression algorithms (as done in Hutter's LTCB) and of language models. [5]

Goals

The goal of the Hutter Prize is to encourage research in artificial intelligence (AI). The organizers believe that text compression and AI are equivalent problems. Hutter proved that the optimal behavior of a goal-seeking agent in an unknown but computable environment is to guess at each step that the environment is probably controlled by one of the shortest programs consistent with all interaction so far. [6] However, there is no general solution because Kolmogorov complexity is not computable. Hutter proved that in the restricted case (called AIXI tl) where the environment is restricted to time t and space l, a solution can be computed in time O(t2l), which is still intractable.

The organizers further believe that compressing natural language text is a hard AI problem, equivalent to passing the Turing test. Thus, progress toward one goal represents progress toward the other. They argue that predicting which characters are most likely to occur next in a text sequence requires vast real-world knowledge. A text compressor must solve the same problem in order to assign the shortest codes to the most likely text sequences. [7]

Models like ChatGPT are not eligible for the Hutter Prize for a variety of reasons, they might take too many computational resources than those allowed by the competiton.

Rules

The contest is open-ended. It is open to everyone. To enter, a competitor must submit a compression program and a decompressor that decompresses to the file enwik9. [3] It is also possible to submit a compressed file instead of the compression program. The total size of the compressed file and decompressor (as a Win32 or Linux executable) must be less than or equal 99% of the previous prize winning entry. For each one percent improvement, the competitor wins 5,000 euros. The decompression program must also meet execution time and memory constraints.

Submissions must be published in order to allow independent verification. There is a 30-day waiting period for public comment before awarding a prize. In 2017, the rules were changed to require the release of the source code under a free software license, out of concern that "past submissions [which did not disclose their source code] had been useless to others and the ideas in them may be lost forever." [4]

History

The prize was announced on August 6, 2006 [1] with a smaller text file: enwik8 consisting of 100MB. On February 21, 2020 it was expanded by a factor of 10, to enwik9 of 1GB, similarly, the prize goes from 50,000 to 500,000 euros. The original prize baseline was 18,324,887 bytes, achieved by PAQ8F. The expanded prize baseline was 116MB.

On August 20 of that same year, Alexander Ratushnyak submitted PAQ8HKCC, a modified version of PAQ8H, which improved compression by 2.6% over PAQ8F. He continued to improve the compression to 3.0% with PAQ8HP1 on August 21, 4% with PAQ8HP2 on August 28, 4.9% with PAQ8HP3 on September 3, 5.9% with PAQ8HP4 on September 10, and 5.9% with PAQ8HP5 on September 25. At that point he was declared the first winner of the Hutter prize, awarded 3416 euros, and the new baseline was set to 17,073,018 bytes.

Ratushnyak has since broken his record multiple times, becoming the second (on May 14, 2007, with PAQ8HP12 compressing enwik8 to 16,481,655 bytes, and winning 1732 euros), third (on May 23, 2009, with decomp8 compressing the file to 15,949,688 bytes, and winning 1614 euros), and fourth (on Nov 4, 2017, with phda compressing the file to 15,284,944 bytes, and winning 2085 euros) winner of the Hutter prize.

As of July 2023, Saurabh Kumar is the latest winner of the Hutter Prize, with fast-cmix compressing the larger file enwik9 to 113,746,218 bytes and winning 5187 euros. [2]

On February 2, 2024, Kaido Orav set a new record for enwiki9 at 112,578,322 bytes. [2]

See also

Related Research Articles

In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information. Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates.

bzip2 File compression software

bzip2 is a free and open-source file compression program that uses the Burrows–Wheeler algorithm. It only compresses single files and is not a file archiver. It relies on separate external utilities for tasks such as handling multiple files, encryption, and archive-splitting.

In computing, Deflate is a lossless data compression file format that uses a combination of LZ77 and Huffman coding. It was designed by Phil Katz, for version 2 of his PKZIP archiving tool. Deflate was later specified in RFC 1951 (1996).

ZIP is an archive file format that supports lossless data compression. A ZIP file may contain one or more files or directories that may have been compressed. The ZIP file format permits a number of compression algorithms, though DEFLATE is the most common. This format was originally created in 1989 and was first implemented in PKWARE, Inc.'s PKZIP utility, as a replacement for the previous ARC compression format by Thom Henderson. The ZIP format was then quickly supported by many software utilities other than PKZIP. Microsoft has included built-in ZIP support in versions of Microsoft Windows since 1998 via the "Plus! 98" addon for Windows 98. Native support was added as of the year 2000 in Windows ME. Apple has included built-in ZIP support in Mac OS X 10.3 and later. Most free operating systems have built in support for ZIP in similar manners to Windows and macOS.

compress is a Unix shell compression program based on the LZW compression algorithm. Compared to gzip's fastest setting, compress is slightly slower at compression, slightly faster at decompression, and has a significantly lower compression ratio. 1.8 MiB of memory is used to compress the Hutter Prize data, slightly more than gzip's slowest setting.

The Lempel–Ziv–Markov chain algorithm (LZMA) is an algorithm used to perform lossless data compression. It has been under development since either 1996 or 1998 by Igor Pavlov and was first used in the 7z format of the 7-Zip archiver. This algorithm uses a dictionary compression scheme somewhat similar to the LZ77 algorithm published by Abraham Lempel and Jacob Ziv in 1977 and features a high compression ratio and a variable compression-dictionary size, while still maintaining decompression speed similar to other commonly used compression algorithms.

rzip is a huge-scale data compression computer program designed around initial LZ77-style string matching on a 900 MB dictionary window, followed by bzip2-based Burrows–Wheeler transform and entropy coding (Huffman) on 900 kB output chunks.

Fabrice Bellard is a French computer programmer known for writing FFmpeg, QEMU, and the Tiny C Compiler. He developed Bellard's formula for calculating single digits of pi. In 2012, Bellard co-founded Amarisoft, a telecommunications company, with Franck Spinelli.

PAQ is a series of lossless data compression archivers that have gone through collaborative development to top rankings on several benchmarks measuring compression ratio. Specialized versions of PAQ have won the Hutter Prize and the Calgary Challenge. PAQ is free software distributed under the GNU General Public License.

Context mixing is a type of data compression algorithm in which the next-symbol predictions of two or more statistical models are combined to yield a prediction that is often more accurate than any of the individual predictions. For example, one simple method is to average the probabilities assigned by each model. The random forest is another method: it outputs the prediction that is the mode of the predictions output by individual models. Combining models is an active area of research in machine learning.

Snappy is a fast data compression and decompression library written in C++ by Google based on ideas from LZ77 and open-sourced in 2011. It does not aim for maximum compression, or compatibility with any other compression library; instead, it aims for very high speeds and reasonable compression. Compression speed is 250 MB/s and decompression speed is 500 MB/s using a single core of a circa 2011 "Westmere" 2.26 GHz Core i7 processor running in 64-bit mode. The compression ratio is 20–100% lower than gzip.

<span class="mw-page-title-main">Marcus Hutter</span> Computer scientist

Marcus Hutter is a professor and artificial intelligence researcher. As a Senior Scientist at DeepMind, he is researching the mathematical foundations of artificial general intelligence. He is on leave from his professorship at the ANU College of Engineering and Computer Science of the Australian National University in Canberra, Australia. Hutter studied physics and computer science at the Technical University of Munich. In 2000 he joined Jürgen Schmidhuber's group at the Istituto Dalle Molle di Studi sull'Intelligenza Artificiale in Manno, Switzerland. He developed a mathematical theory of artificial general intelligence. His book Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability was published by Springer in 2005.

Byte pair encoding is an algorithm, first described in 1994 by Philip Gage for encoding strings of text into tabular form for use in downstream modeling. Its modification is notable as the large language model tokenizer with an ability to combine both tokens that encode single characters and those that encode whole words. This modification, in the first step, assumes all unique characters to be an initial set of 1-character long n-grams. Then, successively the most frequent pair of adjacent characters is merged into a new, 2-character long n-gram and all instances of the pair are replaced by this new token. This is repeated until a vocabulary of prescribed size is obtained. Note that new words can always be constructed from final vocabulary tokens and initial-set characters.

The Calgary corpus is a collection of text and binary data files, commonly used for comparing data compression algorithms. It was created by Ian Witten, Tim Bell and John Cleary from the University of Calgary in 1987 and was commonly used in the 1990s. In 1997 it was replaced by the Canterbury corpus, based on concerns about how representative the Calgary corpus was, but the Calgary corpus still exists for comparison and is still useful for its originally intended purpose.

<span class="mw-page-title-main">PeaZip</span> File archive computer program

PeaZip is a free and open-source file manager and file archiver for Microsoft Windows, ReactOS, Linux, MacOS and BSD by Giorgio Tani. It supports its native PEA archive format and other mainstream formats, with special focus on handling open formats. Version 9.4.0 supported 234 file extensions.

Dynamic Markov compression (DMC) is a lossless data compression algorithm developed by Gordon Cormack and Nigel Horspool. It uses predictive arithmetic coding similar to prediction by partial matching (PPM), except that the input is predicted one bit at a time. DMC has a good compression ratio and moderate speed, similar to PPM, but requires somewhat more memory and is not widely implemented. Some recent implementations include the experimental compression programs hook by Nania Francesco Antonio, ocamyd by Frank Schwellinger, and as a submodel in paq8l by Matt Mahoney. These are based on the 1993 implementation in C by Gordon Cormack.

There are a number of competitions and prizes to promote research in artificial intelligence.

ZPAQ is an open source command line archiver for Windows and Linux. It uses a journaling or append-only format which can be rolled back to an earlier state to retrieve older versions of files and directories. It supports fast incremental update by adding only files whose last-modified date has changed since the previous update. It compresses using deduplication and several algorithms depending on the data type and the selected compression level. To preserve forward and backward compatibility between versions as the compression algorithm is improved, it stores the decompression algorithm in the archive. The ZPAQ source code includes a public domain API, libzpaq, which provides compression and decompression services to C++ applications. The format is believed to be unencumbered by patents.

Zstandard is a lossless data compression algorithm developed by Yann Collet at Facebook. Zstd is the corresponding reference implementation in C, released as open-source software on 31 August 2016.

References

  1. 1 2 3 "500'000€ Prize for Compressing Human Knowledge". Hutter Prize. Retrieved 2023-01-08.
  2. 1 2 3 Mahoney, Matt (2022-12-02). "Large Text Compression Benchmark" . Retrieved 2023-01-08.
  3. 1 2 Mahoney, Matt (2011-09-01). "About the Test Data" . Retrieved 2022-11-16.
  4. 1 2 "Human Knowledge Compression Contest Frequently Asked Questions & Answers". Hutter Prize. Retrieved 14 Oct 2022.
  5. ↑ Radford, Alec; Wu, Jeff; Child, Rewon; Luan, David; Amodei, Dario; Sutskever, Ilya (2019). "Language Models are Unsupervised Multitask Learners" (PDF).
  6. ↑ Hutter, Marcus (2005). Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability. Texts in Theoretical Computer Science an EATCS Series. Springer. doi:10.1007/b138233. ISBN   3-540-22139-5.
  7. ↑ Mahoney, Matt (2009-07-23). "Rationale for a Large Text Compression Benchmark" . Retrieved 2022-11-16.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.