Defining and Demonstrating Machine-Learnable Discrete Sets

This research introduces a formal definition for "machine-learnable" large discrete sets, characterizing them by three key properties: their elements are readily recognized, easily generated, and these tasks can be learned efficiently from examples. The formalism specifically applies to sets of binary strings. The definition of machine-learnability is grounded in the existence of a Boolean autoencoder with bounded complexity that can accurately reconstruct the elements of the set. The study implemented these autoencoders using networks of Boolean threshold functions. Experiments successfully demonstrated machine-learnability for Rorschach patterns, which exhibit specific symmetries, and also for more complex, "wilder" sets where elements are only approximately fixed by the autoencoders. For these wilder sets, a simple iterative process was shown to evolve them towards becoming properly machine-learnable.