ONLINE LEARNING IN PARITY MACHINES

The optimal algorithm for on-line learning in the tree K-parity machin e is studied. We introduce a set of recursion relations for the releva nt probability distributions, which permit study of the general K case . The generalization error curve is determined and shown to decay to z ero for large alpha as e(g) approximate to alpha(-1) even in the prese nce of noise. There is no critical noise level. The dynamics of on-lin e learning is studied analytically near the origin. In the absence of previous knowledge, the learning dynamics has a fixed point at alpha = 0. Previous knowledge is needed in at least K - 1 branches for the le arning to take place.