A stochastic high-order connectionist network for solving inferencing problems
Chandrashekar L. Masti, Mathukumalli Vidyasagar · 1991
A solution to the difficult satisfiability problem is developed, based on a high-order, stochastic update rule Boltzmann machine style artificial neural network. The high order of interconnections enables the net to encode high-order correlations from the problem domain. Using valid transformation laws from Boolean algebra, the canonical form of the satisfiability problem is recast so that the order of neuron interconnections in the net equals one less than the number of literals in the longest clause. The network's objective (energy) function derived rigorously for given problems exhibits degenerate ground states (local minima). Simulated annealing via the logarithmic temperature update rule is used to escape local minima. A recently available result guaranteeing convergence to global minima is explored. The network shows good performance over large problem sizes. The speed of convergence to global minima states in several simulations is impressive.>