Exponential generalizations from a polynomial number of examples in a combinatorial domain

Combinatorial domains are of interest because they allow a large repertoire of behaviours to be described from a few relatively simple rules. However, the problem that combinatorial domains pose for machines that learn from examples, such as connectionist networks, is to learning the target behaviour adequately without a corresponding explosion in training examples. We show, both theoretically and empirically, that a feedforward network can generalize to an order of examples greater than that on which it was trained. Specifically, for the encoding of N-tuples, where the example space grows exponentially with N, only a polynomial number of training examples was required to achieve a fixed degree of accuracy over the entire domain.