Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
2000-05-02
2001-04-03
Hafiz, Tariq R. (Department: 2762)
Data processing: artificial intelligence
Neural network
Learning task
C706S015000, C706S022000, C706S025000
Reexamination Certificate
active
06212509
ABSTRACT:
BACKGROUND OF THE INVENTION
This application pertains to the art of artificial intelligence, and more particularly to a system for organizing a large body of pattern data so as to organize it to facilitate understanding of features.
The subject system has particular application to analysis of acquired, empirical data, such as chemical characteristic information, and will be described with particular reference thereto. However, it will be appreciated that the subject system is suitably adapted to analysis of any set of related data so as to allow for visualization and understanding of the constituent elements thereof.
It is difficult to make sense out of a large body of multi-featured pattern data. Actually the body of data need not be large; even a set of 400 patterns each of six features would be quite difficult to “understand.” A concept of self-organization has to do with that type of situation and can be understood in terms of two main approaches to that task. In one case, an endeavor is directed to discovering how the data are distributed in pattern space, with the intent of describing large bodies of patterns more simply in terms of multi-dimensional clusters or in terms of some other distribution, as appropriate. This is a dominant concern underlying the Adaptive Resonance Theory (ART) and other cluster analysis approaches.
In a remaining case, effort is devoted to dimension reduction. The corresponding idea is that the original representation, having a large number of features, is redundant in its representation, with several features being near repetitions of each other. In such a situation, a principal feature extraction which is accompanied by dimension reduction may simplify the description of each and all the patterns. Clustering is suitably achieved subsequently in the reduced dimension space. The Karhunen-Loeve (K-L) transform, neural-net implementations of the K-L transform, and the auto-associative mapping approach are all directed to principal component analysis (PCA), feature extraction and dimension reduction.
In actuality the two streams of activity are not entirely independent. For example the ART approach has a strong “winner-take-all” mechanism in forming its clusters. It is suitably viewed as “extracting” the principal prototypes, and forming a reduced description in terms of these few principal prototypes. The feature map approach aims at collecting similar patterns together through lateral excitation-inhibition so that patterns with similar features are mapped into contiguous regions in a reduced dimension feature map. That method clusters and reduces dimensions. The common aim is to let data self organize into a simpler representation.
A new approach to this same task of self-organization is described in herein. The idea is that data be subjected to a nonlinear mapping from the original representation to one of reduced dimensions. Such mapping is suitably implemented with a multilayer feedforward neural net. Net parameters are learned in an unsupervised manner based on the principle of conservation of the total variance in the description of the patterns.
The concept of dimension reduction is somewhat strange in itself. It allows for a reduced-dimension description of a body of pattern data to be representative of the original body of data. The corresponding answer is known for the linear case, but is more difficult to detail in the general nonlinear case.
A start of the evolution leading to the subject invention may be marked by noting the concept of principal component analysis (PCA) based on the Karhunen-Loeve (K-L) transform. Eigenvectors of a data co-variance matrix provide a basis for an uncorrelated representation of associated data. Principal components are those which have larger eigenvalues, namely those features (in transformed representation) which vary greatly from pattern to pattern. If only a few eigenvalues are large, then a reduced dimension representation is suitably fashioned in terms of those few corresponding eigenvectors, and nearly all of the information in the data would still be retained. That utilization of the Karhunen-Loeve transform for PCA purposes has been found to be valuable in dealing with many non-trivial problems. But in pattern recognition, it has a failing insofar as what is retained is not necessarily that which helps interclass discrimination.
Subsequent and somewhat related developments sought to link the ideas of PCA, K-L transform and linear neural networks. Such efforts sought to accomplish a linear K-L transform through neural-net computing, with fully-connected multilayer feedforward nets with the backpropagation algorithm for learning the weights, or with use of a Generalized Hebbian Learning algorithm. In this system, given a correct objective function, weights for the linear links to any of the hidden layer nodes may be noted to be the components of an eigenvector of the co-variance matrix. Earlier works also described how principal components may be found sequentially, and how that approach may avoid a tedious task of evaluating all the elements of a possibly very large co-variance matrix.
The earlier works begged the question of what might be achieved if the neurons in the networks were allowed to also be nonlinear. Other efforts sought to address that question. In one case, the original data pattern vectors are subjected to many layers of transformation in a multilayer feedforward net, but one with nonlinear internal layer nodes. An output layer of such a net has the same number of nodes as the input layer and an objective is to train the net so that the output layer can reproduce the input for all inputs. This provides a so-called auto-associative learning configuration. In addition, one of the internal layers serves as a bottle-neck layer, having possibly a drastically reduced number of nodes. Now, since the outputs from that reduced number of nodes can closely regenerate the input, in all cases, the nodes in the bottle-neck layer might be considered to be a set of principal components. That may prove to be an acceptable viewpoint, except for the fact that the solutions attained in such learning are not unique and differ radically depending on initial conditions and the order in which the data patterns are presented in the learning phase. Although the results are interesting, there is no unique set of principal components.
In another earlier feature map approach, dimension reduction is attained in yet another manner. A reduced-dimension space is suitably defined as two dimensional. The reduced-dimension space is then spanned by a grid of points and a pattern vector is attached to each of those grid points. These pattern vectors are chosen randomly from the same pattern space as that of the problem. Then the pattern vectors of the problem are allocated to the grid points of the reduced-dimension space on the basis of similarity to the reference vector attached to the grid. This leads to a biology inspired aspect of the procedure, namely that of lateral excitation-inhibition. When a pattern vector is allocated to a grid point, at first it would be essentially be at random, because of that grid point happening to have a reference vector most similar to the pattern vector. But once that allocation is made, the reference vector is modified to be even more like that of the input pattern vector and furthermore, all the reference vectors of the laterally close grid points are modified to be more similar to that input pattern also. In this way, matters are soon no longer left to chance; patterns which are similar in the original pattern space are in effect collected together in reduced dimension space. Depending on chance, sometimes two or more rather disparate zones can be built up for patterns which could have been relegated to contiguous regions if things had progressed slightly differently. On the other hand, results of that nature may not be detrimental to the objectives of the computational task.
The ART approach to self-organization of data can be mentioned in this context because the MAX-NET impl
Meng Zhuo
Pao Yoh-Han
Arter & Hadden LLP
Computer Associates Think Inc.
Hafiz Tariq R.
Starks Wilbert L.
LandOfFree
Visualization and self-organization of multidimensional data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Visualization and self-organization of multidimensional data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Visualization and self-organization of multidimensional data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2530922