Theoretical Analysis of Neural Networks

The theoretical analysis of CMM based systems has been underpinning research in the group for some time. The main areas of research are:

The Properties of CMM system.

This section describes how CMMs can be used for associative memories, describes the papers on the storage analysis of CMMs. It covers some work on fault tolerance in CMM systems as well as conventional neural networks. It discusses how CMMs can be used in distributed representations for what is known as Statistical Parallelism a novel form of parallel processing using neural networks.

	Storage Analysis of CMM
	Fault tolerance in neural networks
	Statistical Parallelism
	Distributed Representations.

The development of processing methods using CMMs

This summarises methods that use CMMs to undertake general processing tasks. It includes work on ADAM, AURA, k-NN pattern recognition and symbolic reasoning.

	The Advanced Distributed Associative Memory, ADAM.
	The Advanced Uncertain Reasoning Architecture, AURA.
	Symbolic Reasoning in CMMs.
	Graph Matching with CMMs.
	String Matching with CMMs.
	k-NN pattern recognition with CMMs.

Certification of Neural Networks

In addition to work on CMMs some work has looked at the issues of applying neural networks in safety critical applications (such as those undertaken at York with British Aerospace).

---

The Properties of CMM systems.

CMMs as Associative memories.

In most of the work at York CMMs are used as associative memories. To understand the relationship between CMM based associative memories, conventional and weighted neural networks see the review in the Handbook of Neural Computation [Austin (1995)].

Storage capacity.

The properties of CMM systems mainly surround the storage and recall properties of the networks. To be able to use these systems it is vital that a clear understanding of what happens when data is stored in these networks and how errors arise. This aspect has been looked at in the major paper where a full analysis has been presented of the CMMs storage ability [Austin & Turner (1995)].

The paper presents a mathematical analysis of the CMM and shows how superimposed inputs effect the error properties.

Fault tolerance.

Neural networks have been known for some time to be fault tolerant. The same applies to CMM based systems. The following paper examines the fault tolerance of the ADAM neural network, an early CMM based associative memory. It shows that the CMMs do have resilience to stuck-at-one and stuck-at-zero faults.

The first of these is a general overview of fault tolerance in neural networks [Austin, Bolt, Morgan (1991)], analyses the fault tolerance of ADAM networks. More general papers on fault tolerance  examine fault tolerance of lateral inhibition network [Austin, Bolt, Morgan (1991)]  and the general reliability of neural networks [Austin, Bolt, Morgan, 1991]  . [Austin, Bolt, Morgan (1991)] describes how MLPs may be made fault tolerant by some simple post adjustments to the network.

George Bolt's thesis [t4] brings the work together and presents simple methods to make MLP networks fault tolerant by altering the sigmoid function after training.

Distributed processing and Statistical Parallelism.

The symbolic reasoning methods and the AURA methods in general exploit distributed encoding of data in the input and out put of the CMM. The methods were originally explored in [Austin (1992)] and [Austin (1992)]. These papers showed how parallel recall could be achieved in a CMM by superimposing inputs. It also showed how CMMs could be built to make parallel finite state machines. The methods were examined in a research project and some analysis is presented in these papers : [Austin & Yan (1996), Austin & Yan (1997), Austin & Yan (1998)] showing the performance of the method and a concise definition of the method. Work is continuing exploring these methods, with draft results now available on how to perform fully distributed reasoning with CMM based systems.

A comparison between different partial matching methods using superimposed codes and those using in CMMs is given in [Filer & Austin (1995)] and in John Kennedy's thesis [t13]. Some analysis relating this to psychological factors is given in [Filer & Austi]n (1995).

---

The Development of processing methods using CMMs.

Processing methods that use CMMs have been developed from the mid 1980's. The following introduces many of the papers in this group.

Initial Associative Memory work: ADAM.

The first reference is to the development of the first multi-CMM architecture, the Advanced Distributed Associative Memory (ADAM). This was built as an associative memory for image analysis, particularly occlusion analysis,  [Austin (1986)] is a University of York reprint of the original thesis, [Austin (1986)].

[Austin (1993)] presents an overview of ADAM up to 1993 for a small workshop dedicated to `weightless neural networks' or RAM based networks as they have become to be known in some places. A good overview of this class of networks (up to 1994) can be found in [Austin (1994)], work up to 1997 can be found in a book on the subject, "RAM Based Neural Network Advances and Applications". A short review of RAM based networks can be found in [Austin (1998)].

[Austin & Stonham (1987)] is a good overview of ADAM, [Austin & Stonham (1987)] is a York University internal report on the same work, and [Austin and Stonham] (1987) is the first paper that names the neural network ADAM (its just a very short paper for the first IEEE International Conference on neural networks in 1987).

The ADAM memory built on work in N-tuple pattern recognition by I Aleksander and J Stonham. Within the early work N tuple methods were targeted at grey scale images. Methods based on N tuples were developed to deal with this type of data [Austin (1988), Austin (1988)].

Paper [33] by presents some ideas for unsupervised learning in ADAM allowing better selection of the output vectors.

Recent work compared the N-tuple methods with conventional statistical methods [Lister & Austin (1997)], suggested that they compared well.

One problem faced by N-tuple based systems (as ADAM is) is the non uniform use of the memory in the matrix. A simple pre-processing using a 1-tuple pre-processor overcame this [40].

One of the first major grants into research on ADAM was gained under the JFIT/IED initiative. This work investigated the extension to ADAM for matching maps in images (see section on applications in computer vision).

Applications of ADAM have continued, but now the methods have been combined into the general AURA methods which not only cope with images, but text data also.

The AURA technology

The Advanced Uncertain Reasoning Architecture (AURA) was defined to bring together a set of high performance pattern recognition methods based on correlation matrix memories.

The original concepts for developing Uncertain reasoning systems in neural networks was first given in [Austin (1992)]. The ideas took some time to develop and the AURA architecture has first published in [Austin, Kennefdy & Lees (1995)] as a result of a research project on implementing reasoning systems with neural networks with British Aerospace.

The AURA methods now include all the techniques used in ADAM as well as the following Symbolic reasoning methods and associated techniques for graph matching and string matching. This allows the methods to deal with 1D (strings) 2D (images) and 3D (graphs) data. See the links to understand the various methods.

Symbolic Reasoning in CMMs.

The problem of reasoning with symbolic data in neural networks is still an open area. The work undertaken in this group has focussed on how to organise data so that the CMM can be used for rule chaining. The aim is to use the CMM to match large numbers of rules very quickly. Due to the use of distributed encoding, this has meant the development of sophisticated data representations to deal with the rule data.

A major paper [Austin (1995)] describes the basic rule processing architecture for the first time. It identifies how CMMs can be used to store rules and allow simple chaining of the rule based data. This paper is followed up in  [Austin (1997)] with a little more detail.

Recent work has shown how it is possible to do fully distributed reasoning using CMMs.

Work in the use of CMMs in vision has shown how a rule based system can be used to recognise simple images [t10]. More details of this work can be found in the image processing section.

String matching with CMMs

CMMs on there own operate as quite efficient associative memories. However, when it comes to more complex data structures careful pre-processing and multiple memories need to be used. Research in conjunction within an MSc project and then with the Post Office allowed the development of methods to match 1D string data against a large data base (>4M entries). The methods are particularly applicable to medium sized texts (60-200 characters). The original MSc [MM6] examined the basic ideas. These have been fully explored in a PhD thesis by David Lomas [t11], with preparatory work on address data in his MSc thesis [m4]. The work is now being commercialised by Cybula Ltd.

Graph Matching with CMMs

Graph structures are a very flexible representation for many types of data. The matching of graphs has been explored extensively in an EPSRC research project aimed at matching molecules in molecular databases. The work shows how CMMs can be used [Austin & Turner (1997)] in conjunction with an extended Relaxation Labelling method [Austin & Turner (1997)]

], for this task. These methods are now fundamental in my applications, particularly Trade Mark image analysis and Textile Database applications.

k-NN Pattern Recognition with CMMs.

The use of CMMs in conjunction with conventional pattern recognition methods has been examined in [Austin & Zhou (1998), Austin & Zhou (1998), Austin, Kennedy & Zhou (1999)]. The k-NN method has been evaluated. This method is quite a robust classifier, but suffers from slow recognition rates due to the amount of data being used. The CMMs have been exploited to perform fast pattern matching against the large datasets involved. Hardware implementation is also assessed in these papers.

The method remains a practical approach and has been exploited in Time Series Applications in a thesis by Kustrin [t8].

Certification of Neural Networks

The problem of using neural network in applications where safety is a concern has been an issue in neural computing for some time. A small EPSRC research project investigated these issues [Austin & Morgan (1995)] and developed a draft standard for the certification of neural networks [Bedford, Morgan & Austin (1996)] and a requirements for certification [Bedford, Morgan & Austin (1996)].