Equivalence between learning in noisy perceptrons and tree committee machines

We study learning from single presentation of examples (on-line learning) in single-layer perceptrons and tree committee machines (TCMs). Lower bounds for the perceptron generalization error as a function of the noise level in the teacher output are calculated. We find that local learning in a TCM with K hidden units is simply related to learning in a simple perceptron with a corresponding noise level (K). For a large number of examples and finite K the generalization error decays as ₂₌^-1, where ₂₌ is the number of examples per adjustable weight in the TCM. We also show that on-line learning is possible even in the K limit, but with the generalization error decaying as ₂₌^-1/2. The simple Hebb rule can also be applied to the TCM, but now the error decays as ₂₌^-1/2 for finite K and ₂₌^-1/4 for K. Exponential decay of the generalization error in both the noisy perceptron learning and in the TCM is obtained by using the learning by queries strategy. 1996 The American Physical Society.