Application of neural networks to sorting problems: D. L. Gray, A. N. Michel and W. Porod. Department of Electrical and Computer Engineering, University of Notre Dame, Notre Dame, IN 46556 USA
- Publisher
- Elsevier Science
- Year
- 1988
- Tongue
- English
- Weight
- 72 KB
- Volume
- 1
- Category
- Article
- ISSN
- 0893-6080
No coin nor oath required. For personal study only.
✦ Synopsis
The study of neural networks and their applications has received tremendous interest in recent years [1]. In particular, a design philosophy for constraint optimization problems based on an energy function has been proposed. This approach is founded on the observation that the dynamics of a neural network can be viewed as optimizing an associated energy function [2]. As was demonstrated by Tank and Hopfield [3], the analog-to-digital conversion problem, which has received considerable attention as a special case of a sorting task, can also be viewed as a constraint optimization problem. Using an energy function approach, these authors proposed a particular network design for this application. In their design, however, a mismatch in the neural thresholds resulted from the combination of the high number of feedback paths in conjunction with the consequences of the energy function approach. This combination lead to the appearance of spurious states in the analog-to-digital converter. This phenomenon is also encountered in the design of conventional analog circuits and it reveals itself in [3] since neural networks have their roots in analog circuits.
In this paper, we present an alternate design philosophy which is based on viewing the neural network as an interconnection of several subsystems [4,5]. We illustrate this design method by applying it to sorting problems. Specifically, we present a method to classify, ranges in the magnitude of an analog input signal and associate an arbitrary digital output with each range.
The design method in this paper is superior in performance to past energy function designs due to the four following qualities. First, the network is composed of small blocks of strong local interconnections with weak coupling between the blocks themselves. Secondly, by coordinating the network thesholds and by removing the requirement of a symmetric interconnection matrix, a significant reduction in the potential number of spurious state sites is achieved. Thirdly. the potential for modular design exists due to the functional block design strategy utilized. Lastly, in the analog-to-digital converter problem the need for exponentially increasing resistor values is eliminated.
After presenting the design methodology, two example designs will be shown. A modular analog-to-digital converter will be designed by this approach using different block decompositions. In addition, we demonstrate a network design to perform the classification of an unknown resistor to its closest standard part value and the determination of the tightest resulting standard tolerance from that value.