THE STATISTICAL-MECHANICS OF CONSTRUCTIVE ALGORITHMS

The storage capacity of multilayer networks with overlapping receptive fields is studied for constructive algorithms using Boolean perceptro ns as their basic building block which have been investigated within a replica framework. The assumption of weak coupling between subsequent ly constructed perceptrons is verified within a replica symmetric (RS) ansatz and shown to be negligible in most cases in comparison with co rrection due to replica symmetry breaking (RSB) in individual perceptr ons. The capacities of a tiling-like and variants of the upstart algor ithm are then calculated within RS and one-step RSB with the quenched average taken over the individual units separately for networks with u p to K = 4000 and K = 600 units respectively. Within this treatment, t he storage capacity alpha(c)(K) seems to exhibit a power-law behaviour in log K 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 indic ate that n should be strictly smaller than 1 within one-step RSB, wher eas within RS the Mitchison-Durbin bound is violated for finite K and n > 1 may hold asymptotically.