A theory of incremental compression
This work addresses the fundamental challenge of data compression for intelligent systems, offering a theoretical framework with algorithmic implementation, though it appears incremental in building on existing concepts like Kolmogorov complexity.
The paper tackles the problem of compressing data strings by developing a theory of incremental compression that partitions information into pairwise independent pieces, achieving description lengths close to optimal Kolmogorov complexity. It introduces ALICE, a computable algorithm for this compression, and relates features to Martin-Löf randomness tests to formalize properties of computable objects.
The ability to find short representations, i.e. to compress data, is crucial for many intelligent systems. We present a theory of incremental compression showing that arbitrary data strings, that can be described by a set of features, can be compressed by searching for those features incrementally, which results in a partition of the information content of the string into a complete set of pairwise independent pieces. The description length of this partition turns out to be close to optimal in terms of the Kolmogorov complexity of the string. Exploiting this decomposition, we introduce ALICE - a computable ALgorithm for Incremental ComprEssion - and derive an expression for its time complexity. Finally, we show that our concept of a feature is closely related to Martin-Löf randomness tests, thereby formalizing the meaning of "property" for computable objects.