Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
1998-10-19
2002-05-21
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Neural network
Learning task
Reexamination Certificate
active
06393413
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to n-tuple or RAM based neural network classification systems and, more particularly, to n-tuple or RAM based classification systems having weight vectors with element values being determined during a training process.
2. Description of the Prior Art
A known way of classifying objects or patterns represented by electric signals or binary codes and, more precisely, by vectors of signals applied to the inputs of neural network classification systems lies in the implementation of a so-called learning or training phase. This phase generally consists of the configuration of a classification network that fulfils a function of performing the envisaged classification as efficiently as possible by using one or more sets of signals, called learning or training sets, where the membership of each of these signals in one of the classes in which it is desired to classify them is known. This method is known as supervised learning or learning with a teacher.
A subclass of classification networks using supervised learning are networks using memory-based learning. Here, one of the oldest memory-based networks is the “n-tuple network” proposed by Bledsoe and Browning (Bledsoe, W. W. and Browning, I, 1959, “Pattern recognition and reading by machine”, Proceedings of the Eastern Joint Computer Conference, pp. 225-232) and more recently described by Morciniec and Rohwer (Morciniec, M. and Rohwer, R.,1996, “A theoretical and experimental account of n-tuple classifier performance”, Neural Comp., pp. 629-642).
One of the benefits of such a memory-based system is a very fast computation time, both during the learning phase and during classification. For the known types of n-tuple networks, which is also known as “RAM networks” or “weightless neural networks”, learning may be accomplished by recording features of patterns in a random-access memory (RAM), which requires just one presentation of the training set(s) to the system.
The training procedure for a conventional RAM based neural network is described by Jørgensen (co-inventor of this invention) et al. (Jørgensen, T. M., Christensen, S. S. and Liisberg, C.,1995, “Cross-validation and information measures for RAM based neural networks”, Proceedings of the Weightless Neural Network Workshop WNNW95 (Kent at Canterbury, UK) ed. D. Bisset, pp.76-81) where it is described how the RAM based neural network may be considered as comprising a number of Look Up Tables (LUTs). Each LUT may probe a subset of a binary input data vector. In the conventional scheme the bits to be used are selected at random. The sampled bit sequence is used to construct an address. This address corresponds to a specific entry (column) in the LUT. The number of rows in the LUT corresponds to the number of possible classes. For each class the output can take on the values 0 or 1. A value of 1 corresponds to a vote on that specific class. When performing a classification, an input vector is sampled, the output vectors from all LUTs are added, and subsequently a winner takes all decision is made to classify the input vector. In order to perform a simple training of the network, the output values may initially be set to 0. For each example in the training set, the following steps should then be carried out:
Present the input vector and the target class to the network, for all LUTs calculate their corresponding column entries, and set the output value of the target class to 1 in all the “active” columns.
By use of such a training strategy it may be guaranteed that each training pattern always obtains the maximum number of votes. As a result such a network makes no misclassification on the training set, but ambiguous decisions may occur. Here, the generalisation capability of the network is directly related to the number of input bits for each LUT. If a LUT samples all input bits then it will act as a pure memory device and no generalisation will be provided. As the number of input bits is reduced the generalisation is increased at an expense of an increasing number of ambiguous decisions. Furthermore, the classification and generalisation performances of a LUT are highly dependent on the actual subset of input bits probed. The purpose of an “intelligent” training procedure is thus to select the most appropriate subsets of input data.
Jørgensen et al. further describes what is named a “cross validation test” which suggests a method for selecting an optimal number of input connections to use per LUT in order to obtain a low classification error rate with a short overall computation time. In order to perform such a cross validation test it is necessary to obtain a knowledge of the actual number of training examples that have visited or addressed the cell or element corresponding to the addressed column and class. It is therefore suggested that these numbers are stored in the LUTs. It is also suggested by Jørgensen et al. how the LUTs in the network can be selected in a more optimum way by successively training new sets of LUTs and performing cross validation test on each LUT. Thus, it is known to have a RAM network in which the LUTs are selected by presenting the training set to the system several times.
In an article by Jørgensen (co-inventor of this invention) (Jørgensen. T. M. “Classification of handwritten digits using a RAM neural net architecture”, February 1997, International Journal of Neural Systems, Vol. 8, No. 1, pp. 17-25 it is suggested how the class recognition of a RAM based network can be further improved by extending the traditional RAM architecture to include what is named “inhibition”. This method deals with the problem that in many situations two different classes might only differ in a few of their features. In such a case, an example outside the training set has a high risk of sharing most of its features with an incorrect class. So, in order to deal with this problem it becomes necessary to weight different features differently for a given class. Thus, a method is suggested where the network includes inhibition factors for some classes of the addressed columns. Here, a confidence measure is introduced, and the inhibition factors are calculated so that the confidence after inhibition corresponds to a desired level.
The result of the preferred inhibition scheme is that all addressed LUT cells or elements that would be set to 1 in the simple system are also set to 1 in the modified version, but in the modified version column cells being set to 1 may further comprise information of the number of times the cell has been visited by the training set. However, some of the cells containing 0's in the simple system will have their contents changed to negative values in the modified network. In other words, the conventional network is extended so that inhibition from one class to another is allowed.
In order to encode negative values into the LUT cells, it is not sufficient with one bit per cell or element as with a traditional RAM network. Thus, it is preferred to use one byte per cell with values below 128 being used to represent different negative values, whereas values above 128 are used for storing information concerning the number of training examples that have visited or addressed the cell. When classifying an object the addressed cells having values greater than or equal to 1 may then be counted as having the value 1.
By using inhibition, the cells of the LUTs are given different values which might be considered a sort of “weighting”. However, it is only cells which have not been visited by the training set that are allowed to be suppressed by having their values changed from 0 to a negative value. There is no boosting of cells having positive values when performing classification of input data. Thus, very well performing LUTs or columns of LUTs might easily drown when accompanied by the remaining network.
Thus, there is a need for a RAM classification network which allows a very fast training or learning phase and subsequent classification, but which at the same time allo
Jorgensen Thomas M.
Linneberg Christian
Birch & Stewart Kolasch & Birch, LLP
Booker Kelvin
Davis George B.
Intellix A/S
LandOfFree
N-tuple or RAM based neural network classification system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with N-tuple or RAM based neural network classification system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and N-tuple or RAM based neural network classification system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2824292