Equivalence between learning in noisy perceptrons and tree committee machines
Mauro Copelli, Osame Kinouchi, Nestor Caticha · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 1996
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 \ensuremath{\epsilon} 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 \ensuremath{\epsilon}(K). For a large number of examples and finite K the generalization error decays as ${\mathrm{\ensuremath{\alpha}}}_{\mathrm{CM}}^{\mathrm{\ensuremath{-}}1}$, where ${\mathrm{\ensuremath{\alpha}}}_{\mathrm{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\ensuremath{\rightarrow}\ensuremath{\infty} limit, but with the generalization error decaying as ${\mathrm{\ensuremath{\alpha}}}_{\mathrm{CM}}^{\mathrm{\ensuremath{-}}1/2}$. The simple Hebb rule can also be applied to the TCM, but now the error decays as ${\mathrm{\ensuremath{\alpha}}}_{\mathrm{CM}}^{\mathrm{\ensuremath{-}}1/2}$ for finite K and ${\mathrm{\ensuremath{\alpha}}}_{\mathrm{CM}}^{\mathrm{\ensuremath{-}}1/4}$ for K\ensuremath{\rightarrow}\ensuremath{\infty}. 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. \textcopyright{} 1996 The American Physical Society.