A Learning Machine with a Bit-Based Hypothesis Space

We propose in this paper a bit–based classifier, picked from an hypothesis space described accordingly to sparsity and locality princi- ples: the complexity of the corresponding space of functions is controlled through the number of bits needed to represent it, so that it will include the classifiers that will be most likely chosen by the learning procedure. Through an introductory example, we show how the number of bits, the sparsity of the representation and the local definition approach affect the complexity of the space of functions, where the final classifier is selected from.