Discovering structure in data.

Franz, Arthur. "Grounded Reasoning: Implication as Algorithmic Containment." In International Conference on Artificial General Intelligence, pp. 238-252. Springer, 2026.

This paper develops a formal reinterpretation of implication: implication need not be represented as explicit symbolic rule chains. The paper formalizes a grounded view in which a premise is a generative description, and a consequence is information already contained in that description. Using algorithmic information theory, we prove that when a property is recoverable from a typical generated instance, it is algorithmically contained in the premise up to logarithmic overhead. We then show how this containment yields a family-level implication statement: from a fixed witness instance x with features (properties) f and g*, one can construct g so that whenever f is a feature of a string y, g is also a feature of y, with only additive logarithmic slack in compression. The result reframes implication itself as algorithmic containment and motivates a shift in AGI reasoning architectures from stored implication chains to derivation from generative world models.

Franz, A. (2022). Experiments on the Generalization of Machine Learning Algorithms. In: Goertzel, B., Iklé, M., Potapov, A. (eds) Artificial General Intelligence. AGI 2021. Lecture Notes in Computer Science(), vol 13154. Springer, Cham. https://doi.org/10.1007/978-3-030-93758-4_9

The inductive programming system WILLIAM is applied to machine learning tasks, in particular, centralization, outlier detection, linear regression, linear classification and decision tree classification. These examples appear as a special case of WILLIAM’s general operation of trying to compress data without any special tuning. The goal is to study how a general compression-based method behaves when the learning problem is changed and how the resulting descriptions generalize beyond the observed data.

Arthur Franz, Oleksandr Antonenko, Roman Soletskyi, A theory of incremental compression, Information Sciences, Volume 547, 2021, Pages 28-48, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2020.08.035. ArXiv: https://arxiv.org/abs/1908.03781

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 a wide class of data can be described efficiently by progressively discovered features and residuals. The theory formalizes how useful representations can be extracted, how they can be reused across tasks, and why incremental compression can outperform general-purpose search when the data is generated by compositional structure.

Arthur Franz, Victoria Gogulya, and Michael Löffler. "WILLIAM: A monolithic approach to AGI." In International Conference on Artificial General Intelligence, pp. 44-58. Springer, Cham, 2019.

We present WILLIAM — an inductive programming system based on the theory of incremental compression. It builds representations by incrementally stacking autoencoders made up of trees of general Python functions, thereby stepwise compressing data. The system is able to solve a diverse set of tasks including the compression and prediction of simple sequences, recognition of geometric shapes, writing code from test cases, self-improvement by solving some of its own problems, and playing tic-tac-toe when attached to AIXI.

We introduce WILLIAM — a new system for data compression that is based on a formal mathematical theory of incremental compression. The theory promises to find short descriptions in an incremental and efficient way while still being applicable to a wide range of data. We use abstract syntax trees of selected Python operators to define a representation language and report practical tests of the theory with encouraging results.

Franz A. On Hierarchical Compression and Power Laws in Nature //International Conference on Artificial General Intelligence. – Springer, Cham, 2017. – С. 77-86.

Since compressing data incrementally by a non-branching hierarchy has resulted in substantial efficiency gains for performing induction in previous work, we now explore branching hierarchical compression as a means for solving induction problems for generally intelligent systems. We derive a proof that branching compression hierarchies create power law functions of mutual algorithmic information between strings as a function of their distance, a ubiquitous characteristic of natural data that opens the possibility of efficient natural data compression by such hierarchies.

Franz A. Some Theorems on Incremental Compression //International Conference on Artificial General Intelligence. – Springer International Publishing, 2016. – С. 74-83.

The ability to induce short descriptions of, i.e. compressing, a wide class of data is essential for any system exhibiting general intelligence. In all generality, it is proven that incremental compression — extracting features of data strings and continuing to compress the residual variance — leads to a time complexity superior to universal search if the strings are incrementally compressible. Such a procedure breaks the shortest description into a set of pairwise orthogonal features in terms of algorithmic information.

Franz A. Toward tractable universal induction through recursive program learning //International Conference on Artificial General Intelligence. – Springer, Cham, 2015. – С. 251-260.

Since universal induction is a central topic in artificial general intelligence (AGI), it is argued that compressing all sequences up to a complexity threshold should be the main thrust of AGI research. A measure for partial progress in AGI is suggested along these lines. By exhaustively executing all two- and three-state Turing machines, a benchmark for low-complexity universal induction is constructed. The resulting binary sequences are then compressed by recursively constructing networks of functions guided by breadth-first search, making the detection of low-entropy programs efficient.

Franz A. Artificial general intelligence through recursive data compression and grounded reasoning: a position paper //arXiv preprint arXiv:1506.04366. – 2015.

This paper presents a tentative outline for the construction of an artificial, generally intelligent system (AGI). It is argued that building a general data compression algorithm that solves all problems up to a complexity threshold should be the main thrust of research. The paper suggests a measure for partial progress in AGI and outlines a grounded reasoning system that recursively compresses representations while maintaining a flexible and orthogonal set of hypotheses explaining the data.