R24  
On Improving Connectionist Energy Minimization
Gadi Pinkas &
Rina Dechter (dechter@ics.uci.edu)

Abstract Symmetric networks designed for energy minimization such as Boltzman machines and Hopfield nets are used frequently for optimization, constraint satisfaction and approximation of NPhard problems. Nevertheless, finding a global solution (i.e., a global minimum for the energy function) is not guaranteed and even a local solution may take an exponential number of steps. We propose an improvement to the standard local activation function used for such networks. The improved algorithm guarantees that a global minimum is found in linear time for treelike subnetworks. The algorithm is uniform and does not assume that the network is treelike. It can identify treelike subnetworks even in cyclic topologies (arbitrary networks) and avoid local minima along these trees. For acyclic networks, the algorithm is guaranteed to converge to a global minimum from any initial state of the system (selfstabilization) and remains correct under various types of schedulers. For general (cyclic) topologies, we show how our treelike algorithm can be extended using the cyclecutset idea. The general algorithm optimizes treelike subnetworks and has some performance guarantees that are related to the size of the network's cyclecutset. In any case, the algorithm performs no worse than the standard algorithms. On the negative side, we show that in the presence of cycles, no uniform algorithm exists that guarantees optimality even under a sequential synchronous scheduler. In addition, no uniform algorithm exists to optimize even acyclic networks when the scheduler is asynchronous. [ps] [pdf] 