The statistical mechanics of constructive algorithms
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.