The statistical mechanics of constructive algorithms
Ansgar H. L. West, David Saad · Journal of Physics A Mathematical and General · 1998
The storage capacity of multilayer networks with overlapping receptive fields is studied for constructive algorithms using Boolean perceptrons as their basic building block which have been investigated within a replica framework. The assumption of weak coupling between subsequently constructed perceptrons is verified within a replica symmetric (RS) ansatz and shown to be negligible in most cases in comparison with correction due to replica symmetry breaking (RSB) in individual perceptrons. The capacities of a tiling-like and variants of the upstart algorithm are then calculated within RS and one-step RSB with the quenched average taken over the individual units separately for networks with up to K = 4000 and K = 600 units respectively. Within this treatment, the storage capacity seems to exhibit a power-law behaviour in with an exponent n that may depend on the algorithm and the stability. However, due to finite size effects in K reliable estimates of n could not be extracted. Nevertheless, the results strongly indicate that n should be strictly smaller than 1 within one-step RSB, whereas within RS the Mitchison-Durbin bound is violated for finite K and n>1 may hold asymptotically.