  We propose a novel framework for the analysis of learning algorithms that
allows us to say when such algorithms can and cannot generalize certain
patterns from training data to test data. In particular we focus on situations
where the rule that must be learned concerns two components of a stimulus being
identical. We call such a basis for discrimination an identity-based rule.
Identity-based rules have proven to be difficult or impossible for certain
types of learning algorithms to acquire from limited datasets. This is in
contrast to human behaviour on similar tasks. Here we provide a framework for
rigorously establishing which learning algorithms will fail at generalizing
identity-based rules to novel stimuli. We use this framework to show that such
algorithms are unable to generalize identity-based rules to novel inputs unless
trained on virtually all possible inputs. We demonstrate these results
computationally with a multilayer feedforward neural network.
