aiqbench analysis
This research proposes a formal framework for "machine-learnable sets," defining discrete collections of binary strings that can be efficiently recognized, generated, and learned via bounded-complexity Boolean autoencoders. The study demonstrates this capability on structured patterns like Rorschach images and evolves more complex, irregular sets into learnable forms through iterative refinement. By grounding the concept in specific architectural constraints rather than general neural networks, the work advances theoretical understanding of what constitutes a learnable structure within discrete mathematics.
Machine-learnable Sets
arXiv:2606.28947v2 Announce Type: replace-cross Abstract: In this study we present a formal definition of large discrete sets having, informally, three properties: their elements are easily recognized, easily generated, and the latter tasks are easily learned from examples. The formalism is specialized to sets of binary strings and a definition of "machine-learnability" based on the existence of a bounded-complexity Boolean autoencoder that fixes the elements of the set. We present experiments where the autoencoders are implemented by nets of Boolean threshold functions. Machine-learnability is demonstrated for Rorschach patterns (that may have reversed contrast in the mirrored half), and considerably "wilder" sets whose elements are only approximately fixed by admissible autoencoders. In the second case we demonstrate a simple iteration that evolves wild sets to make them properly machine-learnable.
Abstract:In this study we present a formal definition of large discrete sets having, informally, three properties: their elements are easily recognized, easily generated, and the latter tasks are easily learned from examples. The formalism is specialized to sets of binary strings and a definition of "machine-learnability" based on the existence of a bounded-complexity Boolean autoencoder that fixes the elements of the set. We present experiments where the autoencoders are implemented by nets of Boolean threshold functions. Machine-learnability is demonstrated for Rorschach patterns (that may have reversed contrast in the mirrored half), and considerably "wilder" sets whose elements are only approximately fixed by admissible autoencoders. In the second case we demonstrate a simple iteration that evolves wild sets to make them properly machine-learnable.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2606.28947 [cs.LG]
(or arXiv:2606.28947v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.28947 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 217 words
Related coverage
On the Complexity of Offline Reinforcement Learning with $Q^\star$-Approximation and Partial Coverage
arXiv · Jun 9, 2026
ManifoldFlow: SPD-Relaxed Stiefel Layers with Learnable Singular Spectrum
arXiv · Oct 2, 2026
When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
arXiv · Aug 24, 2026
Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
arXiv · Jun 8, 2026