A theory of incremental compression

DOI10.1016/J.INS.2020.08.035MaRDI QIDQ2056272zbMATH OpenOpenAlexFDO

Authors Arthur Franz, Oleksandr Antonenko, Roman Soletskyi

Publication date 2 December 2021

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.03781

zbMATH Keywords

autoencodercompressionfeatureKolmogorov complexityMartin-Löf randomnessOccam's razor

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: 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"of randomness tests, thereby formalizing the meaning of "property" for computable objects.

Recommendations

• Toward an abstract theory of data compression
• An abstract model for compressions
• scientific article; zbMATH DE number 3463524
• The compression theorem I
• An adaptive compression algorithm in a deterministic world
• Achievable complexity-performance tradeoffs in lossy compression
• The macro model for data compression (extended abstract)
• scientific article; zbMATH DE number 512869
• Compressibility and uniform complexity

Cites work

• A Fast Learning Algorithm for Deep Belief Nets
• A formal theory of inductive inference. Part I
• A formal theory of inductive inference. Part II
• A new look at the Bayes procedure
• An introduction to Kolmogorov complexity and its applications
• Complexity-based induction systems: Comparisons and convergence theorems
• Compression of Data Streams Down to Their Information Content
• Estimating the dimension of a model
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 2061729 (Why is no real title available?)
• Kolmogorov Complexity and Algorithmic Randomness
• Modeling by shortest data description
• Optimal ordered problem solver
• Pattern recognition and machine learning.
• Perception as Bayesian Inference
• Reducing the Dimensionality of Data with Neural Networks
• THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.

Cited in

(9)

• The compression structure of a process
• Compressibility, laws of nature, initial conditions and complexity
• An adaptive compression algorithm in a deterministic world
• Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity and Creativity
• Compression is Comprehension and the Unreasonable Effectiveness of Digital Computation in the Natural World
• Learning as Data Compression
• A new algorithm for compression of partially commutative alphabets
• A speed-up theorem without tape compression
• Toward an abstract theory of data compression

Describes a project that uses

Uses Software

• darch
• PRMLT

This page was built for publication: A theory of incremental compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056272)