Interaction Selection and Complexity Control for Learning in Binarized Domains

We empirically investigate the potential of a novel, greatly simplified classifier design for binarized data. The generic model allocates a sparse, "digital" hidden layer comprised of interaction nodes that compute PARITY of selected submasks of input bits, followed by a sigmoidal output node with adjustable weights. Model identification incorporates user-assigned complexity preferences. We discuss the situations: a) when the input space obeys a metrics b) when the inputs are discrete attributes We propose a family of respective model priors that make search through the combinatorial space of multi-input interactions feasible. Model capacity and smoothness of the approximation are controlled by two complexity parameters. Model comparison over the parameter plane discovers models with excellent performance. In some cases interpretable structures are achieved. We point out the significance of our novel data mining tool for overcoming scaling problems, impacts on real-time systems, and possible contributions to the development of non-standard computing devices for inductive inference.

ICSI Technical Report TR-96-001

Technical Report