TL;DR
This paper proposes using text compression as a novel, objective metric for evaluating Artificial Intelligence (AI). The authors argue that the ability to compress text, which relies on understanding linguistic patterns, is fundamentally similar to the predictive capabilities required for AI. They demonstrate that leading compression algorithms exhibit varying degrees of "learning" and "understanding" of English, suggesting a potential benchmark for AI progress.
What Problem Does This Paper Address?
The paper tackles the long-standing challenge of objectively measuring progress in Artificial Intelligence. The Turing Test, while influential, is subjective and can be gamed. The authors propose that text compression, specifically achieving high compression ratios on natural language text, offers a more quantitative and objective measure of a system's ability to understand and predict linguistic patterns. This understanding is posited to be a core component of intelligence, making compression a suitable proxy for AI evaluation. They draw a parallel between predicting the next character in a text stream (essential for compression) and the predictive abilities needed to pass the Turing Test.
Methods
The core methodology involves evaluating several state-of-the-art text compression programs on natural language datasets. The authors focus on two key aspects:
- Compression Ratio: The primary metric is the bits per character (bpc) achieved by each compressor. Lower bpc indicates better compression and, by extension, a deeper understanding of the text's statistical properties.
- Learning Capability: The paper investigates how well compressors "learn" from prior input to improve compression on subsequent input. This is assessed by comparing the compression of a text split into two halves versus compressing each half independently. A significant improvement in the combined compression suggests a learning mechanism.
- Exploitation of Linguistic Constraints: The authors analyze how compressors break down syntactic and semantic constraints by selectively swapping elements (letters, words, phrases). This is done to understand how compression is achieved and to correlate it with the exploitation of linguistic regularities.
The authors also reference the theoretical underpinnings of compression, particularly Shannon's information theory and the concept of entropy, as the theoretical limit for compression.
Datasets
The primary dataset used for evaluation is:
- English Narrative Texts: Specifically, "Alice in Wonderland" (alice30.txt from the Gutenberg press) and "Far from the Madding Crowd" by Thomas Hardy (book1 from the Calgary corpus). These texts were pre-processed to a 27-character alphabet (A-Z and space) to standardize the evaluation.
The paper does not introduce new benchmarks but uses existing, well-known literary works for evaluation.
Key Insights and Ideas
- Compression as a Proxy for AI: The central idea is that the ability to predict and model natural language patterns, as demonstrated by high compression ratios, is a fundamental aspect of intelligence. This offers a more objective alternative to subjective tests like the Turing Test.
- "Learning" in Compressors: The study reveals that some compressors exhibit a "learning" behavior, significantly improving compression on subsequent data by adapting to patterns encountered in prior input. This learning is crucial for achieving better compression and is analogous to how intelligent systems adapt.
- Exploitation of Linguistic Structure: The research highlights that better compressors effectively leverage the syntactic and semantic constraints of English. The ability to break and then reconstruct these constraints (via reversible transformations) is key to achieving high compression.
- Theoretical Limits: The paper grounds its findings in information theory, referencing Shannon's work on entropy as the theoretical upper bound for compression, implying that true AI would approach this limit.
Key Results
- Compression Performance: The best-performing compressor tested,
rkive 1.91b1, achieved 1.86 bpc on "Alice" and 1.94 bpc on "Far from the Madding Crowd." This is still significantly higher than the theoretical entropy limit for English (estimated at 1.3 bpc). - Learning Effectiveness: The compressor
szipwas identified as the best "learner," achieving compression on "book1" that was approximately 95% of the size of compressing the two halves separately. - Comparison of Compressors: Seven programs were tested, with
rkiveandboaperforming best, andcompressperforming worst. The results showed a correlation between compression performance and the degree of "learning" exhibited by the compressors. - Syntactic/Semantic Use: The study found that better compressors make greater use of English's syntactic and semantic constraints, which are selectively broken and then restored by the compression algorithms.
Limitations and Future Work
- Theoretical Limit Not Reached: Despite advancements, even the best compressors fall short of the theoretical entropy limit for English, suggesting there is still significant room for improvement in both compression and, by extension, AI capabilities.
- Focus on English: The study is limited to English text. Future work could explore how these findings generalize to other languages with different linguistic structures.
- Nature of "Learning": While "learning" is observed, the paper could delve deeper into the specific mechanisms and sophistication of this learning in different compression algorithms.
- Broader AI Tasks: The paper proposes compression as a test for AI. Future work could explore how performance on compression tasks correlates with performance on a wider range of AI benchmarks and tasks.
Summary updated