Stochastic Diffusion Search

A more up to date version of the repository is currently hosted at http://aomartin.co.uk/sds-repository/publications.html.

Old list of publications (with links to online papers).

Download example Text SDS software here (manual will be added soon) (last updated 23/1/04)

Introduction

Stochastic Diffusion Search (SDS) is a generic population-based search method. SDS agents perform cheap, partial evaluations of a hypothesis (a candidate solution to the search problem). They then share information about hypotheses (diffusion of information) through direct one-to-one communication. As a result of the diffusion mechanism, high-quality solutions can be identified from clusters of agents with the same hypothesis.

The restaurant game

A group of delegates attend a long conference in an unfamiliar town. Each night they have to find somewhere to dine. There is a large choice of restaurants, each of which offers a large variety of meals. The problem the group faces is to find the best restaurant, that is the restaurant where the maximum number of delegates would enjoy dining (given that all delegates have more or less the same preference). Even a parallel exhaustive search through the restaurant and meal combinations would take too long to accomplish. To solve the problem delegates decide to employ a Stochastic Diffusion Search.

Each delegate acts as an agent maintaining a hypothesis identifying the best restaurant in town. Each night each delegate tests his hypothesis by dining there and randomly selecting one of the meals on offer. The next morning at breakfast every delegate who did not enjoy his meal the previous night, asks one randomly selected colleague to share his dinner impressions. If the experience was good, he also adopts this restaurant as his choice. Otherwise he simply selects another restaurant at random from the list in the Yellow Pages.

Using this strategy it is found that very rapidly a significant number of delegates congregate around the best restaurant in town.

History

SDS was first proposed by Mark Bishop in [1] and [2] as a pattern recognition technique capable of solving the problem of stimulus equivalence: the ability to recognise a pattern independent of its potential distortions or transformations in the search space. It was inspired by a method developed by G.F. Hinton, Hinton mapping (see [3,4] for Hinton's work and [2,5] for the connection between Hinton mapping and SDS).

The technique has been successfully applied to a variety of real-world problems. In [5], the Hybrid Stochastic Diffusion Network (HSDN), a combination of Stochastic Diffusion Search with N-tuple Weightless Neural Networks ([6]), was used to locate eye features in images of human faces; [7] used the same combination for lip tracking in video films. In [8] SDS was used as a method for self-localisation of an autonomous wheelchair, extending the original algorithm to provide a faster solution in large search spaces (the Focused Stochastic Diffusion Network - FSDN).

The basic properties of SDS are well understood: convergence to the global optimal solution ([5,9]); convergence time, increasing at most linearly with search space size ([10]); resource allocation dynamics ([11]). In its pattern matching context, the algorithm isrobust to noise distortion and multiple instantiations of the target ([11]).

Other than being a fast and reliable generic search method, SDS seems to present itself as a possible solution to some persisting problems in neurophilosophy. In [12], the HSDN is reviewed in terms of an alternative connectionism, based on communication between neurons, as opposed to the classical approach of viewing neurons as simple computational devices. [13] proposes a novel neural network implementation of SDS as a solution to the binding problem. [14] expands upon biological evidence for communication as a new metaphor for neuronal operation. Emergent synchronisation across a large population of neurons in the network can be interpreted as a mechanism of attentional amplification ([15]).

Bibliography

 
1
J.M. Bishop, (1989). Anarchic Techniques for Pattern Classification. PhD. Thesis, Chapter 5, University of Reading.
2
J.M. Bishop, (1989). Stochastic Searching Networks. Proc. 1st IEE Conf. on Artifical Neural Networks, pp 329-331, London.
3
G.F. Hinton, (1981). A Parallel Computation that Assigns Canonical Object-Based Frames of Reference. Proc. 7th Int. Jnt. Conf. AI.
4
D.E. Rumelhart & J.L. McClelland, (1986). Parallel Distributed Processing vol. 1 pp113-118, MIT Press.
5
J.M. Bishop, P. Torr (1992). The Stochastic Search Network. In R. Linggard, D.J. Myers, C. Nightingale (eds.), Neural Networks for Images, Speech and Natural Language, pp370-387, New York, Chapman & Hall.
6
I. Aleksander, T.J. Stonham (1979). Guide to Pattern Recognition using Random Access Memories. Computers & Digital Techniques, 2(1), pp. 29-40.
7
E. Grech-Cini, (1995). Locating Facial Features. PhD Thesis, University of Reading.
8
P.D. Beattie, J.M. Bishop, (1998). Self-Localisation in the 'Senario' Autonomous Wheelchair. Journal of Intelligent and Robotic Systems 22, pp 255-267, Kluwer Academic Publishers.
9
S.J. Nasuto, J.M. Bishop, S. Lauria (1998). Time Complexity of Stochastic Diffusion Search. Neural Computation '98, Vienna, Austria.
10
S.J. Nasuto, J.M. Bishop, (1999). Convergence Analysis of Stochastic Diffusion Search. Journal of Parallel Algorithms and Applications 14:2, pp 89-107.
11
S.J. Nasuto, (1999). Resource Allocation Analysis of the Stochastic Diffusion Search. PhD Thesis, University of Reading.
12
J.M. Bishop, S.N. Nasuto, (1999). Communicating Neurons - an Alternative Connectionism. Proc. WNNW99, York.
13
S.J. Nasuto, J.M. Bishop, (1998). Neural Stochastic Diffusion Search Network - a Theoretical Solution to the Binding Problem. Proc. ASSC2, pp19, Bremen.
14
S.J. Nasuto, K. Dautenhahn, J.M. Bishop, (1999). Communication as an Emergent Methaphor for Neuronal Operation. Lecture Notes in Artificial Intelligence, 1562:365-380, Springer.
15
K. De Meyer, J.M. Bishop, S.J. Nasuto, (2000). Attention through Self-Synchronisation in the Spiking Neuron Stochastic Diffusion Network. In Proc. ASSC4, Brussels. Consciousness and Cognition, 9-2 p.S81, Academic Press.

Last modified: 21 September 2009.
Webpage maintained by: m.bishop@gold.ac.uk