Machine-learnable Sets
Veit Elser, Manish Krishan Lal · 2026
Read Machine-learnable Sets by Veit Elser, Manish Krishan Lal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28947.txt.
Introduction
Elser and Lal define what it means for a large set of patterns to be machine-learnable, in a precise formal sense. Informally, a learnable set has three traits: its members are easy to recognise, easy to generate, and both tasks are easy to learn from examples. Their formalism uses binary strings, and learnability means a bounded-complexity Boolean autoencoder exists that leaves every member of the set unchanged.
An autoencoder here compresses and rebuilds its input. Fixing the set's members means it rebuilds them perfectly. The authors implement these autoencoders as nets of Boolean threshold functions, simple units that fire when weighted inputs pass a limit. Experiments show learnability for Rorschach patterns, symmetric inkblot-like designs that may flip contrast in the mirrored half. Wilder sets, whose members are only roughly fixed, are also studied. A simple iteration evolves them until they become properly machine-learnable.
Catalog record
| CREATOR | Veit Elser, Manish Krishan Lal |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28947
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Machine-learnable Sets Veit Elser, Manish Krishan Lal 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. I Introduction Formal models of machine learning are used to establish what kinds of learning are possible in principle, and to provide a framework for evaluating its practice. “Language identification in the limit,” by Gold 4 , is the best known example of the former and launched the field of algorithmic learning theory. The task considered was learning the grammar of an abstract language from examples, with computations limited only by a Turing machine. Valiant’s 9 Probably Approximately Correct (PAC) learning model moved the focus in the direction of practice. Computations in the PAC model have polynomial complexity bounds, and exact learning is replaced by probabilistic guarantees. In this paper we move the needle even further, with artificial neural networks imposing explicit bounds on the computations. The model, called machine-learnable sets , views learnability as an inherently interesting phenomenon. Language acquisition—in humans, not machines—is the example of learnable sets we are most familiar with. The set in question is the set X of all grammatical, bounded-length sentences in some language. A notable feature of X is that listing its elements is not feasible. In spite of this, X has the following nice properties: 1. Given a string (of symbols) x , it is easy to decide whether x\in X . 2. It is easy to uniformly sample all of X . 3. Though somewhat harder, doing tasks 1 and 2 can be learned from positive examples x\in X^{*}\subset X , where |X^{*}|\ll|X| . Less formally, a child of even distracted parents easily rises to the level of a grammatical chatterbox! Language is of course much more than what these properties try to capture, and we make no claims that something like this lies at the heart of natural language. Still, as we explain next, language suggests a mechanism —something that a machine can implement—for realizing sets X having the above properties. Behind (above? under?) every grammatical sentence is its meaning. Speakers of a language have equal facility at transforming sentences into meanings and meanings into sentences. We tend to think of meanings as shared across different languages, with English and Hindi differing only in the transformations to and from sentences. We can formalize this way of looking at language with the autoencoder architecture of machine learning. The autoencoder receives a sentence in some language, easily transforms it into its compact, universal meaning, and just as easily transforms the meaning back to the original sentence. The representation of sentences by symbols is well known, the representation of meanings much less so. If we represent both as strings of bits, then because the transformations in the autoencoder are deterministic, the two kinds of strings have equal entropy. An interesting case is where the sentence-strings are longer than the meaning-strings by some factor greater than 2, and the length of the meaning-strings is close to the entropy of strings (of either kind) in bits. An autoencoder with these characteristics can act as the identity on only a very special subset of the sentence strings—those having an associated meaning-string—and these define the set X in the list above. To perform task 1 one simply inputs x and checks that x comes out. The sentence-strings generated by the output half of the autoencoder, from freely sampled meaning-strings, accomplishes task 2. Property 3 in the list above is simply the observation that if the complexity of the autoencoder can be suitably bounded, then the information provided by a modest number of sentence-examples should suffice to reconstruct it uniquely. The language example compels us to reverse the usual designations of the two autoencoder halves. Meanings are primary, and languages are the codes that meanings are encoded into and decoded from. In this paper the encoder is always the output-half of the autoencoder. Language is also our motivation behind shifting attention from the functions that act on sets to the sets themselves. One of the legacies of MNIST is a “they are what they are …” attitude about data, and to not let that discourage the pursuit of perfect classification. While this is the correct attitude in many if not most applications of machine learning, in the case of language we might question whether the data (e.g. grammar) deserves the same unquestioned degree of permanence. Suppose X_{0} is a proto-language and speakers in generation 0 learn it poorly—as an autoencoder \mathcal{A}_{0} —because of its faults. That is, \mathcal{A}_{0}(X_{0})=X_{1} , where X_{1} is close to but distinct from the proto-language X_{0} . As the representation of X_{1} grows in the population, speakers of generation 1 will start to learn language X_{1} , again imperfectly, as \mathcal{A}_{1} and introduce yet another variant, \mathcal{A}_{1}(X_{1})=X_{2} . And so on, where the refinements become smaller and the languages easier to learn. Spanish might not just be the easiest language to learn, but the most evolved! The machine qualifier in machine-learnable sets is what sets our learning model apart from previous models. Polynomial time-space limits on computations, as in PAC learning, seem extravagant compared to processing data by passing it through a neural network. A scaled-down model of computation also aligns with our experience of language acquisition: an automatic process distinct from “cogitation.” The autoencoder implementation of tasks 1 and 2 clearly fits this description. Until recently, task 3, which concerns the training of neural networks, could not be addressed because discrete representations and circuit (encoder/decoder) reconstructions were outside the scope of gradient-based optimization. However, first results 2 with a constraint-based method that trains networks of Boolean threshold functions showed that these limitations no longer apply. The remainder of this paper is organized as follows. Related previous work is reviewed in Section II . Machine-learnable sets are formally defined in Section III in application-blind terms. The meaning-strings of language just comprise another set called Y . Section III also presents the theory behind property 3 (a form of generalization) and a heuristic argument why the set-migration process described above, when iterating imperfect autoencoders, may converge. Section IV gives a brief review of the constraint-based approach for training networks whose neurons—Boolean threshold functions—have strict \pm 1 outputs. From the user side, working with boolnets is not all that different from working with standard networks. Instead of minimizing loss, the learning algorithm “closes the gap.” Sections V and VI present machine learning experiments with perfect and imperfect machine-learnable sets. In the first case, the autoencoder very quickly realizes it is dealing with Rorschach patterns when the