Abstract:
Accordingly there is provided a class specific classifier for classifying data received from a data source. The classifier has a feature transformation section associated with each class of data which receives the data and provides a feature set for the associated data class. Each feature transformation section is joined to a pattern matching processor which receives the associated data class feature set. The pattern matching processors calculate likelihood functions for the associated data class. One normalization processor is joined in parallel with each pattern matching processor for calculating an inverse likelihood function from the data, the associated class feature set and a common data class set. The common data class set can be either calculated in a common data class calculator or incorporated in the normalization calculation. The inverse likelihood function is then multiplied with the likelihood function for each associated data class. A comparator provides a signal indicating the appropriate class for the input data based upon the highest multiplied result.

Description:
STATEMENT OF GOVERNMENT INTEREST 
     The invention described herein may be manufactured and used by or for the Government of the United States of America for governmental purposes without the payment of any royalties thereon or therefor. 
    
    
     BACKGROUND OF THE INVENTION 
     (1) Field of the Invention 
     This invention generally relates to a signal classification system for classifying an incoming data stream. More particularly, the invention relates to an improvement to the M-ary classifier known in the prior art resulting in a higher probability of correct classification. 
     (2) Description of the Prior Art 
     In order to determine the nature of an incoming signal, the signal type must be determined. A classifier attempts to classify a signal into one of M signal classes based on features in the data. M-ary classifiers utilize neural networks for extracting these features from the data. In a training stage the neural networks incorporated in the classifier are trained with labeled data allowing the neural networks to learn the patterns associated with each of the M classes. In a testing stage, the classifier is tested against unlabeled data based on the learned patterns. The performance of the classifier is defined as the probability that a signal is correctly classified, herein referred to as “PCC”. 
     A prior art classifier is shown in FIG.  1 . The classifier  2  receives data from a data source  4 . Data source  4  is joined to a feature transformation module  6  for developing a feature set. The feature set is provided to pattern match processors  8  which correspond to each data class. Pattern match processors  8  provide an output measuring the developed feature set against trained data. The pattern match processor  8  outputs are compared in a comparison  9  and the highest output is selected. 
     The basis of most M-ary classifiers is the maximum aposteriori probability (MAP) classifier or Bayesian classifier                arg                     max     j   =   1     M                     p        (       H   j        X     )           =     arg                     max     j   =   1     M                       p        (     X        H   j       )              p        (     H   j     )       .                   (   1   )                                
     However, if the likelihood functions p(X|H j ) are not known, it is necessary to estimate them from training data. Dimensionality dictates that this is impractical or impossible unless X is reduced to a smaller set of statistics, or features Z=T(X). 
     While many methods exist for choosing the features, this invention concentrates on class-specific strategies. Class specific architectures are taught in the prior art in patents such as Watanabe et al., U.S. Pat. No. 5,754,681. 
     One possible class-specific strategy is to identify a set of statistics z j , corresponding to each class H j , that is sufficient or approximately sufficient to estimate the unknown state of the class. Sufficiency in this context will be defined more precisely in the theorem that follows. Because some classes may be similar to each other, it is possible that the M feature sets are not all distinct. Let              Z   =       ⋃     i   =   1     M          z   i               (   2   )                                
     where set union notation is used to indicate that there are no redundant or duplicate features in Z. However, removing redundant or duplicate features is not restrictive enough. A more restrictive, but necessary requirement is that p(Z|H j ) exists for all j. The classifier based on Z becomes              arg                     max     j   =   1     M                       p        (     Z        H   j       )              p        (     H   j     )       .                 (   3   )                                
     The object of the feature selection process is that (3) is equivalent to (1). Thus, they are sufficient for the problem at hand. 
     In spite of the fact that the feature sets z j  are chosen in a class-specific manner and are possibly each of low dimension, implementation of (3) requires that the features be grouped together into a super-set Z. Dimensionality issues dictate that Z must be of low dimension (less than about 5 or 6) so that a good estimate of p(Z|H j ) may be obtained with a reasonable amount of training data and effort. The complexity of the high dimensional space is such that it becomes impossible to estimate the probability density function (PDF) with a reasonable amount of training data and computational burden. In complex problems, Z may need to contain as many as a hundred features to retain all necessary information. This dimensionality is entirely unmanageable. It is recognized by a number of researchers that attempting to estimate PDF&#39;s nonparametrically above five dimensions is difficult and above twenty dimensions is futile. Dimensionality reduction is the subject of much research currently and over the past decades. Various approaches include feature selection, projection pursuit, and independence grouping. Several other methods are based on projection of the feature vectors onto lower dimensional subspaces. A significant improvement on this is the subspace method in which the assumption is less strict in that each class may occupy a different subspace. Improvements on this allow optimization of error performance directly. 
     All these methods involve various approximations. In feature selection, the approximation is that most of the information concerning all data classes is contained in a few of the features. In projection-based methods, the assumption is that information is confined to linear subspaces. A simple example that illustrates a situation where this assumption fails is when the classes are distributed in a 3-dimensional volume and arranged in concentric spheres. The classes are not separated when projected on any 1 or 2-dimensional linear subspace. However, statistics based on the radius of the data samples would constitute a simple 1-dimensional space in which the data is perfectly separated. 
     Whatever approach one uses, if Z has a large dimension, and no low-dimensional linear or nonlinear function of the data can be found in which most of the useful information lies, either much of the useful information must be discarded in an attempt to reduce the dimension or a crude PDF estimate in the high-dimensional space must be obtained. In either case, poor performance may result. 
     SUMMARY OF THE INVENTION 
     Therefore, it is one purpose of this invention to provide an improvement on the M-ary classifier. 
     Another purpose of this invention is to drastically reduce the maximum PDF dimension while at the same time retaining theoretical equivalence to the classifier constructed from the full feature set and to the optimum MAP classifier. 
     Yet another purpose is to provide a classifier that gives this performance using a priori information concerning data and classes that is discarded when the combined feature set is created. 
     Accordingly there is provided a class specific classifier for classifying data received from a data source. The classifier has a feature transformation section associated with each class of data which receives the data and provides a feature set for the associated data class. Each feature transformation section is joined to a pattern matching processor which receives the associated data class feature set. The pattern matching processors calculate likelihood functions for the associated data class. One normalization processor is joined in parallel with each pattern matching processor for calculating an inverse likelihood function from the data, the associated class feature set and a common data class set. The common data class set can be either calculated in a common data class calculator or incorporated in the normalization calculation. Preferably, the common data class set will be calculated before processing the received data. The inverse likelihood function is then multiplied with the likelihood function for each associated data class. A comparator provides a signal indicating the appropriate class for the input data based upon the highest multiplied result. The invention may be implemented either as a device or a method operating on a computer. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The appended claims particularly point out and distinctly claim the subject matter of this invention. The various objects, advantages and novel features of this invention will be more fully apparent from a reading of the following detailed description in conjunction with the accompanying drawings in which like reference numerals refer to like parts, and in which: 
     FIG. 1 is a block diagram of a standard classifier well known in the prior art; and 
     FIG. 2 is a block diagram of the class specific classifier taught by the current invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Formulating this invention requires two fundamental ideas. The first idea involves defining some common class H 0  which is a subset of all classes. This is possible if all classes have random amplitudes and are embedded in additive noise. Then if H 0  is the noise-only class, 
     
       
           H   0   εH   j   , j= 1, 2 , . . . ,M.   (4) 
       
     
     The next idea is to connect the selection of z j  with the idea of sufficiency. This is done by assuming M distinct probability density function (PDF) families p(X|H j ), j=1, 2, . . . , M where H j  are the class hypotheses. For each class j, p(X|H j ) is parameterized by a random parameter set θ j , thus                p        (     X        H   j       )       =       ∫     θ   i              p        (     X        θ   j       )            p        (     θ   j     )                 θ   j                   (   5   )                                
     for all j. For each class j, there is also a sufficient statistic for θ j , z j =T j (X), and a combined feature set Z=T(X) such that z j εZ, j=1, 2, . . . , M. The PDF, p(Z|H j ), must exist for all j, and the span of θ j  must include a point θ j   0  that results in an equivalent distribution for X regardless of j: 
     
       
           p ( X|H   j ,θ j   0 )= p ( X|H   0 ),  j =1 , . . . ,M   (6) 
       
     
     Then, the MAP classifier ( 1 ) may be expressed as              arg                     max   j                         p        (       z   j          H   j       )         p        (       z   j          H   0       )                           p        (     H   j     )       .                 (   7   )                                
     Accordingly, it is possible to reduce the dimensionality, yet end up with a classifier theoretically equivalent to the MAP classifier based on the full-dimensional feature set. It is noted by S. Kay in “Sufficiency, classification, and the class specific feature theorem,” Submitted to IEEE Trans. ASSP, June 1998, that under the same assumptions necessary for the above, (7) is equivalent to (1), thus (7) is fully equivalent to the MAP classifier based on the training data. While the reduction of the high-dimensional problem to a low-dimensional problem is significant enough, another significant idea emerges revolving around the idea of sufficiency. If {Z j } are sufficient (in the Neyman-Fisher sense) for the parameterizations of the corresponding class, and a common class H 0  can be found, then Z is sufficient for the classification problem at hand. It is also important to note that while the parameter distributions p(θ j |H j ) are used above, they are not required in practice. All that is required are estimates of the low-dimensional PDF&#39;s p(z j |H j ) 
     Equation (7) can be implemented in a detector/classifier architecture wherein each term in the maximization corresponds to a distinct and independent processing branch. The output of each branch is a detection statistic for distinguishing the corresponding signal class from H 0 . The modularity of the processor has obvious advantages. As long as the same H 0  is used, each branch can be independently designed, trained, and implemented by separate computational hardware. As new signal classes are added to the classifier, it only means adding new branches to the structure. Existing branches remain unchanged. As a generalization of the idea of the Generalized Likelihood Ratio Test, there may be a variety of subclasses indexed by a parameter θ. It is possible to carry out a maximization over θ prior to normalization by p(z j |H 0 ). The common class H 0  does not need to be a real class. Technically, the only requirement is that the parameter sets of each class must include H 0  as a special case, thus the natural role of the noise-only hypothesis. In this implementation it is useful that H 0  represent the condition that X be samples of iid Gaussian noise. 
     While the class-specific architecture is not new, this invention is the first to construct a class-specific classifier that is equivalent to the MAP classifier. Equation (7) shows clearly how the various branches of the structure are normalized and compared in order to achieve the optimal performance of the MAP classifier. It also shows that normalization by the likelihood of the common class H 0  is necessary to allow the outputs to be compared fairly. Without any further knowledge about the class likelihood functions, it represents the architecture with the smallest possible feature dimension that is still equivalent to the optimum Bayesian classifier. 
     While equation (7) requires very specific conditions to hold, specifically the sufficiency of the feature sets and the existence of a common class, the invention uses approximations when appropriate. The sufficiency of the various statistics can be relaxed somewhat, and approximations to the various likelihood functions can be made, but the likelihood functions under H 0  cannot be approximated without careful attention to the tails. In practice, X may vary significantly from H 0 , especially at high signal to noise ratio (SNR). Thus, it is necessary in many cases to use exact analytic expressions for p(z j |H 0 ). This may seem to be an overly restrictive requirement at first. But, in most cases solutions can be found, especially if H 0  is chosen as iid Gaussian noise. 
     For real-world problems, the sufficiency of features can never be established; however, sufficiency is not really required in practice. Sufficiency is required to establish the exact relationship of the class-specific classifier to the MAP classifier. If sufficiency is approximated, so is this relationship. Compare the class-specific approach with the full-dimensional approach. With the class-specific approach, if the feature dimensions are low, one can have a good PDF approximation of approximate sufficient statistics. However, in the full-dimensional approach, one has the choice of a very poor PDF estimate of the full feature set, or a good PDF estimate of a sorely inadequate feature set. 
     The current invention is shown in FIG.  2 . This implementation is shown for three data classes A, B, and C; however, any number of classes may be accommodated by this system. A data source  10  supplies a raw data sample X to the processor  12  at a processor input  14 . It is assumed that the data source can be type A, B, or C, but the identity is not known. Processor output  16  is a decision concerning the identity of the data source, i.e. A, B, or C. The processor  12  contains one feature transformation section  18  for each possible data class. These sections  18  are joined to receive the raw data X at processor input  14 . Each feature transformation section  18  produces a feature set for its respective class. Thus the feature transformation section  18  for class A produces a feature set identified as Z A , and similar feature sets Z B  and Z C  are produced by the respective feature transformation sections for classes B and C. The processor  12  further contains pattern match processors  20  with each pattern match processor joined to a transformation section  18  for receiving a feature set associated with one class. The pattern match processors  20  approximate the likelihood functions of the feature sets for data sampled from the corresponding data class. The likelihood function is also known in the art as the probability density function. In mathematical notation, the pattern match processors are approximations of p(Z A |A), p(Z B |B), and p(Z C |C). These likelihood functions may be approximated from a training data set by any probability density function estimation technique such as Guassian mixtures. The output of the pattern match processors  20  are highest when the input feature set, Z j , is similar to or “matches” the typical values of the training set. Because the pattern match processors  20  are operating on different feature sets, the outputs cannot be directly compared to arrive at a decision without normalization. Normalization processors  22  process the feature set, Z j , and approximate the inverse of the likelihood function for the corresponding feature set when the data is drawn from a special common data class called H 0  to be described later. The common data class H 0  can be calculated independently in a common data processor  23  which is joined to each normalization processor  22 . Preferably the common data class H 0  can be calculated within each normalization processor  22  before receiving data from the data source  10 . In mathematical notation, the normalization processors  22  give 1/p(Z A |H 0 ), 1/p(Z B |H 0 ), and 1/p(Z C |H 0 ). In an additional embodiment, a constant may be applied to the numerator of the normalization, such as to approximate prior probabilities p(A), p(B), and p(C). The output of the normalization processors  22  are passed to a multiplier  24  which multiplies this output with the output of the pattern match processors  20 . The result of the multiplication  24  is processed by a comparison  26  jointed to the processor  12  output  16 . The output  16  is the identity of the data class that has the highest output from the multiplier  24 . 
     The common data class, H 0 , is a special data class that is a subset of each of the other data classes. It usually is identified with the absence of any signal leaving only noise which is termed the “noise-only condition”. Because signals such as those of types A, B, C, having zero amplitude are all the same, the common data class can be a member of each data class. This assumes that the defined signal types are broad enough to allow the existence of zero-amplitude signals. 
     The feature sets (Z A  through Z C  in the embodiment shown) are approximate or exact sufficient statistics if they are sufficient for statistical test between the corresponding data class and the common data class H 0 . For example, feature set Z A  contains all the information contained in the raw data relating to the decision between class A and class H 0 . 
     The implementation of the normalization processors  22  often requires careful attention to tail behavior. Thus, even for examples of feature vectors Z j  that are very different from samples that would have been produced if the raw data was under H 0  such that the normalization processor  22  denominators approach zero and the output of the normalization processors  22  approach infinity, the multiplication  24  must produce an accurate answer. This is possible by representing all quantities in the logarithm domain and implementing the multiplier  24  by an addition of logarithms. It is often necessary to obtain exact mathematical formulas for the denominator functions by deriving them analytically. This is made easier if the common class H 0  has a simple structure such as independent Gaussian noise. 
     The main advantage of the class specific classifier is that the individual feature sets (Z A  through Z C ) can be smaller than would be necessary if a common feature set was used, such as in the standard classifier. The smaller size means that the pattern match processors  20  may be accurately trained with fewer training data samples or given the same number of training samples, the class specific classifier has better pattern match accuracy and thus better performance. 
     This invention has been disclosed in terms of certain embodiments. It will be apparent that many modifications can be made to the disclosed apparatus without departing from the invention. Therefore, it is the intent of the appended claims to cover all such variations and modifications as come within the true spirit and scope of this invention.