Data processing: artificial intelligence – Neural network
Reexamination Certificate
2001-07-12
2004-08-24
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Neural network
C706S026000, C706S027000
Reexamination Certificate
active
06782373
ABSTRACT:
BACKGROUND OF INVENTION
1. Field of the Invention
The present invention relates to artificial neural networks (ANNs) and more particularly to a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network. According to that method, the use of different types of norms is allowed in the distance evaluation process in order to adapt the calculation of the elementary (or partial) distance for each component of the input pattern presented to such a neural network during the distance evaluation process.
2. Background of the Invention
In today's data processing, a lot of recognition, prediction, and computation tasks are performed using reference databases used to characterize input data. Depending upon the problem to be solved, these reference databases contain patterns that are sub-images, sub-signals, subsets of data and combination thereof. The patterns that are stored in these reference databases are referred to herein below as prototypes. As known for those skilled in the art, they are generally represented by a vector, i.e. an array in a p-dimensional space. Well-known methods for characterizing new (unknown) patterns, referred to herein below as input patterns, using reference databases are based upon the input space mapping algorithms like the K-Nearest-Neighbor (KNN) or the Region Of Influence (ROI). The base principle of these algorithms is to compute the distance (dist) between the input pattern and each of the stored prototypes in order to find the closest one(s) depending or not upon predetermined thresholds. U.S. Pat. No. 5,621,863, assigned to IBM Corp and incorporated herein by reference, describes artificial neural networks based on such input space mapping algorithms that include innovative elementary processors of a new type, referred to as the ZISC neurons (ZISC is a registered trade mark of IBM Corp). An essential characteristic of the ZISC neurons lies in their ability to work in parallel, i.e. when an input pattern is presented to the ANN, all ZISC neurons compute the distance between the input pattern and their stored prototypes at the same time. One important aspect of these algorithms is the distance evaluation relation, referred to as the “norm”, that is used in the distance evaluation process. The choice of this norm is determined by the problem to be solved on the one hand, and on the other hand by the knowledge used to solve this problem. In a ZISC neuron, the distance between an input pattern A and the prototype B stored therein (each having p components) is calculated using either the MANHATTAN distance (L1 norm), i.e. dist=sum(abs(Ak−Bk)) or the MAXIMUM distance (Lsup norm), i.e. dist=max(abs(Ak−Bk)) wherein Ak and Bk are the components of rank k (variable k varies from 1 to p) for the input pattern A and the stored prototype B respectively. Note that “abs” is an usual abbreviation for “absolute value”. Other norms exist, for instance the L2 norm such as dist=square root(sum(Ak−Bk)
2
). The L2 norm is said to be “Euclidean” while the L1 and Lsup norms are examples of “non-Euclidean” norms, however, they all imply the handling of a difference (Ak−Bk) for each component in the distance relation. Other Euclidean or non-Euclidean norms (such as the match
o match) are known for those skilled in the art in the ANN field. In the ZISC neuron, the selection between the L1 or Lsup norm is determined by the value of a single bit referred to as the “norm” bit No stored in the neuron.
On the other hand, the notion of “context” was a novel concept introduced by the ZISC neuron. The context can be advantageously used to differentiate different types of input patterns. For instance, the context may be used to distinguish between the upper case and the lower case characters (or to distinguish between different type fonts). In the ZISC neuron, this approach is implemented with a local context Cxt stored in the neuron and a global context CXT held in a common register of the ZISC chip. As a consequence, the context approach will allow to select neurons having learned with a determined context and to inhibit all others in the ANN. During the recognition, the global context value is compared with the local context stored in each neuron, if found identical, the neuron will be selected, otherwise it will be inhibited. As a result, the context allows to configure the ANN either as a single neural network or as an arrangement of separate groups of neurons wherein all the neurons of a group have the same local context. As far as ZISC neurons are concerned, the context (local or global) is a value coded on 7 bits.
In the ZISC neuron, there is thus a specific register, referred to as the local norm/context (No/cxt) register which stores the 1-bit norm No and 7-bit context cxt signals. At the end of the engagement/learning process, the content of the local norm/context register is automatically loaded with the global norm/context stored in the ANN. The 1-bit norm and the 7-bit context signals are applied to the control logic circuits of the ZISC chip.
So far, only one norm has been used for the totality of the components of a stored prototype. In the ZISC neuron, the norm that is applied to each component uses the operator “absolute value of a difference”. Then, the successive values are summed in the case of the L1 norm or the maximum value thereof is selected in the case of the Lsup norm. However, due to the nature of the components, in some instances, it should be worthwhile to associate a norm that could be different for each component of the input pattern/stored prototype depending upon the application. For example, if the two components of a stored prototype characterizing a sub-image describe a color index and the number of pixels of that color index in the sub-image respectively, it would be useful to apply the match
o match norm for the color index related component and an absolute value based norm for the number of pixels related component. The main difficulty dealing with this approach when using conventional ANNs is the considerable amount of memory and logic circuits that would be required in the silicon chip to associate different norms to the components of the input vector/stored prototype and to conduct the distance evaluation process in these particular conditions.
As a result, no technique allowing this highly desired feature is known to date. As a matter of fact, the artificial neural networks described in the aforementioned U.S. patent allow to utilize only one norm per neuron which is thus the same for all the components of a stored prototype. This is a serious limit to extend the use of conventional input space mapping algorithm based neural networks and in particular of ANNs constructed with ZISC neurons when it is required to handle input patterns/stored prototypes having components of different nature.
SUMMARY OF INVENTION
It is therefore a primary feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network.
It is another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network to allow the use of different norms in the distance evaluation process.
It is another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural networks when it is required to handle input patterns having components of different nature.
It is another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network wherein all the norms are memorized in a global memory.
It
de Tremiolles Ghislain Imbert
Tannhof Pascal
Jennings Derek S.
Starks, Jr. Wilbert L.
LandOfFree
Method and circuits for associating a norm to each component... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and circuits for associating a norm to each component..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and circuits for associating a norm to each component... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3357310