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 αCM^-1, where αCM 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 αCM^-1/2. The simple Hebb rule can also be applied to the TCM, but now the error decays as αCM^-1/2 for finite K and αCM^-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.