Abstract
Partitioning a set of N patterns in a d-dimensional metric space
into K clusters - in a way that those in a given cluster are more similar
to each other than the rest - is a problem of interest in many fields,
such as, image analysis, taxonomy, astrophysics, etc. As there are
approximately KN/K! possible ways of partitioning the patterns among K
clusters, finding the best solution is beyond exhaustive search when N is
large. We show that this problem, in spite of its exponential complexity,
can be formulated as an optimization problem for which very good, but not
necessarily optimal, solutions can be found by using a Hopfield model of
neural networks. To obtain a very good solution, the network must start
from many randomly selected initial states. The network is simulated on
the MPP, a 128 x 128 SIMD array machine, where we use the massive
parallelism not only in solving the differential equations that govern the
evolution of the network, but also in starting the network from many
initial states at once thus obtaining many solutions in one run. We
achieve speedups of two to three orders of magnitude over serial
implementations and the promise through Analog VLSI implementations of
further speedups of three to six orders of magnitude.
Abstract
Hopfield and Tank have shown that neural networks can be used to
solve certain computationally hard problems, in particular they studied
the Traveling Salesman Problem (TSP). Based on network simulation results
they conclude that analog VLSI neural nets can be promising in solving
these problems. Recently, Wilson and Pawley presented the results of
their simulations which contradict the original results and cast doubts on
the usefulness of neural nets. In this paper we give the results of our
simulation that clarify some of the discrepancies. We also investigate
the scaling of TSP solutions found by neural nets as the size of the
problem increases. Further, we consider the neural net solution of the
Clustering Problem, also a computationally hard problem, and discuss the
types of problems that appear to be well suited for a neural net approach.
Intelligent Decision Aids
Intelligent M4 Systems
Machine Learning
Sensor-Based Systems
Back to NCARAI Library