Data processing: artificial intelligence – Adaptive system
Reissue Patent
1996-12-18
2001-12-25
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Adaptive system
C706S041000, C706S027000
Reissue Patent
active
RE037488
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an heuristic processor, i.e. a digital processor designed to estimate unknown results by an empirical self-learning approach based on knowledge of prior results.
2. Discussion of Prior Art
Heuristic digital processors an not known per se in the prior art although there has been considerable interest in the field for many years. Such a processor is required to address problems for which no explicit mathematical formalism exists to permit emulation by an array of digital arithmetic circuits. A typical problem is the recognition of human speech, where it is required to deduce an implied message from speech which is subject to distortion by noise and the personal characteristics of the speaker. In such a problem, it will be known that a particular set of sound sequences will correspond to a set of messages, but the mathematical relationship between any sound sequence and the related message will be unknown. Under these circumstances, there is no direct method of discerning an unknown message from a new sound sequence.
The approach to solving problems lacking known mathematical formalisms has in the past involved use of a general purpose computer programmed in accordance with a self-learning algorithm. One form of algorithm is the so-called linear perception model. This model employs what may be referred to as training information from which the computer “learns”, and on the basis of which it subsequently predicts. The information comprises “training data” sets and “training answer” sets to which the training data sets respectively correspond in accordance with the unknown transformation. The linear perception model involves forming differently weighted linear combinations of the training data values in a set to form an output result set. The result set is then compared with the corresponding training answer set to produce error values. The model can be envisaged as a layer of input nodes broadcasting data via varying strength (weighted) connections to a layer of summing output nodes. The model incorporates an algorithm to operate on the error values and provide corrected weighting parameters which (it is hoped) reduce the error values. This procedure is carried out for each of the training data and corresponding training answer set, after which the error values should become small indicating convergence.
At this point data for which there are no known answers are input to the computer, which generates predicted results on the basis of the weighting scheme it has built up during the training procedure. It can be shown mathematically that this approach is valid and yields convergent results for problems where the unknown transformation is linear. The approach is described in Chapter 8 of “Parallel Distributed Processing Vol. 1: Foundations”, pages 318-322, D. E. Rumelhart, J. L. McClelland, MIT Press 1986.
For problems involving unknown nonlinear transformations, the linear perception model produce results which are quite wrong. A convenient test for such a model is the EX-OR problem, i.e. that of producing an output map of a logical exclusive-OR function. The linear perception model has been shown to be entirely inappropriate for the EX-OR problem because the latter is known to be nonlinear. In general, nonlinear problems are considerably more important than linear problems.
In an attempt to treat nonlinear problems, the linear perception model has been modified to introduce non-linear transformations and at least one additional layer of nodes referred to as a hidden layer. This provides the nonlinear multilayer perception model. It may be considered as a layer of input nodes broadcasting data via varying strength (weighted) connections to a layer of internal or “hidden” summing nodes, the hidden nodes in turn broadcasting their sums to a layer of output nodes via varying strength connections once more. (More complex versions may incorporate a plurality of successive hidden layers.) Nonlinear transformations may be performed at any one or more layers. A typical transformation involves computing the hyperbolic tangent of the input to a layer. Apart from these one or more transformations, the procedure is similar to the linear equivalent. Errors between training results and training answers are employed to recompute weighting factors applied to inputs to the hidden and output layers of the perception. The disadvantages of the nonlinear perception approach are that there is no guarantee that convergence is obtainable, and that where convergence is obtainable that it will occur in a reasonable length of computer time. The computer programme may well converge on a false minimum remote from a realistic solution to the weight determination problem. Moreover, convergence takes an unpredictable length of computer time, anything from minutes to many hours. It may be necessary to pass many thousands of training data sets through the computer model.
SUMMARY OF THE INVENTION
It is an object of the invention to provide an heuristic processor.
The present invention provides an heuristic processor including:
(1) transforming means arranged to produce a respective training
&phgr;
vector from each member of a training data set on the basis of a set of centres, each element of a
&phgr;
vector consisting of a nonlinear transformation of the norm of the displacement of the associated training data set member from a respective centre set member
(2) processing means arranged to combine training
&phgr;
vector elements in a manner producing a fit to a set of training answers, and
(3) means for generating result estimate values each consisting of a combination of the elements of a respective
&phgr;
vector produced from test data, each combination being at least equivalent to a summation of vector elements weighted in accordance with the training fit.
The invention provides the advantage that it constitutes a processing device capable of providing estimated results for nonlinear problems. In a preferred embodiment, the processing means is arranged to carry out least squares fitting to training answers. In this form, it produces convergence to the best result available having regard to the choice of nonlinear transformation and set of centres.
The processing means preferably comprises a network of processing cells; the cells are connected to form rows and columns and have functions appropriate to carry out QR decomposition of a
&phgr;
matrix having rows comprising input training data
&phgr;
vector. The network is also arranged to rotate input training answers as through each extended the training data
&phgr;
vector to which it corresponds, in this form, the network comprises boundary cells constituting an array diagonal and providing initial row elements. The rows also contain numbers of internal cells diminishing by one per row down the array such that the lowermost boundary cell is associated with one internal cell per dimension of the training answer set. This provides a triangular array of columns including or consisting of boundary cells together with at least one column of internal cells. The boundary and internal cells have nearest neighbour (row and column interconnection, and the boundary cells are connected together in series along the array diagonal. Rotation parameters are evaluated by boundary cells from data input from above, and are passed along rows for use by internal cells to rotate input data. First row boundary and internal cells receive respective elements of each
&phgr;
vector extended by a corresponding training answer and subsequent rows receive rotated versions thereof via array column interconnections. The triangular array receives input of
&phgr;
vector elements and the associated internal cell column or columns receive training answer elements. Each boundary or internal cell computes and stores a respective updated decomposition matrix element in the process of producing or applying rotation parameters. The systolic array may include one multiplier cell per dimension of the training a
Broomhead David Sydney
Jones Robin
McWhirter John Graham
Shepherd Terence John
Davis George B.
Nixon & Vanderhye P.C.
The Secretary of State for Defence in Her Majesty's Governm
LandOfFree
Heuristic processor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Heuristic processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Heuristic processor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593144