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.