Abstract:
Embodiments of the invention describe a method for classifying data in a system with limited memory. The method applies exemplar learning (EL) procedures to a training data set to produce an exemplar data set adapted to the size of the memory. The EL procedure is selected form a group consisting of an entropy based exemplar learning (EBEL) procedure and an advanced broadband enabled learning (ABEL) procedure. The exemplar data set is used to classify acquired by the system data.

Description:
FIELD OF THE INVENTION 
       [0001]    This invention relates generally to classification of data, and more particularly to classification of data in systems with limited memory. 
       BACKGROUND OF THE INVENTION 
       [0002]    Data Classification 
         [0003]    Data classification assigns a pre-defined label to a data item based on some quantitative information extracted from the item and a training set of previously labeled items. For example, an email classification system can label a specific email as “spam” or “no-spam” based on the email&#39;s content and a training dataset of mails that are known to be “spam” or “no-spam.” A performance of the classifier depends greatly on the characteristics of the data to be classified. There is no single classifier that works best on all classification problems. The performance also depends on the quality of the training data. A well trained classifier requires large training datasets that have labeled samples with varying characteristics. 
         [0004]    Classifiers can vary based on the mathematical models used to extract information from data items, the amount of training data and model complexity. The choice of a classifier often depends on the data characteristics and its computational resource requirement, e.g., such as the CPU usage and memory requirements. For example, some classifiers might be unsuitable when categorization results are required in real-time. 
         [0005]    Embedded System 
         [0006]    An embedded system is usually integrated into some other device or machine. The embedded system can be designed to perform dedicated functions, often in real-time. Embedded systems are common for many devices, such as portable video players, cameras, traffic lights, factory controllers and surveillance systems. Because many embedded system perform dedicated functions, the embedded system can be optimized for size, cost, reliability and performance. 
         [0007]    Embedded systems that include sensors and perform classification can be trained using training data. The trained embedded system can than have an improved functionality and performance. For example, a classifier on a camera can alarm presence of intruder in a “no-trespassing” surveillance area, However, embedded systems typically have limited memory and cannot store a large training data set. 
         [0008]    One solution to the limited memory problem is to store only a small number of carefully selected “exemplars” from the training data that are sufficient for effective classification. As defined herein, an exemplar is sample data that are characteristic of a larger training data set. 
         [0009]    Exemplar Learning (EL) Methods 
         [0010]    An exemplar learning (EL) method can be used to select a small set of training data from a large training dataset. EL, as the name implies, learns by exemplars. That is, ‘good’ samples that reduce the error rate of the classifier are retained, while ‘bad’ samples are discarded. Thus, EL can be used to generate a small training data set for a memory-based classifier in an embedded system that has limited memory. 
         [0011]    Conventional EL methods learn exemplars based on some neighborhood structure. Then, the methods measure a loss or gain in performance due to a sample being removed, using conventional misclassification rates. 
         [0012]    The EL method can continuously adjust the training data set as samples are processed, that is good new samples are retained, and bad new samples are discarded. Thus, the classifier can dynamically adapt to a changing environment in which the embedded system operates. Almost all EL methods discard samples based on the following hypothesis: 
         [0013]    Hypothesis 0 (H 0 ): If the removal of a sample in a given training data set does not increase misclassifications or an error-rate of the remaining samples, then the sample can be discarded. 
         [0014]    EL methods have some disadvantages. 
         [0015]    Incremental Update 
         [0016]    Conventional EL methods are computationally intensive, offline, and are not incremental in nature. They require that the entire training data set is stored in a memory throughout the execution of the exemplar EL method. This makes those methods inapplicable for embedded systems where memory is limited, and the training data are updated regularly. 
         [0017]    Class-Imbalance 
         [0018]    Misclassification rates used in the hypothesis H 0  are insensitive to class-imbalance. This problem is critical in EL, where removal of a sample changes the class population. For example, in a set with 90 positive class samples and 10 negative class samples, removing a positive class sample gives nine positive sample misclassifications and one negative sample misclassification, while discarding a negative sample gives one positive and nine negative sample misclassifications. 
         [0019]    Because the error rate is the same for both the cases, i.e., 10%, the class-imbalance could cause the discarding of the negative samples, leaving only positive class samples in the training data set. 
         [0020]    It is desired to have an EL method that yields an estimate of the classifier&#39;s ability to discriminate between two classes, as opposed to the overall classification accuracy to produce better results. 
         [0021]    Ordered Removal 
         [0022]    Most ordered removal procedures are either ad-hoc, or return a training data set whose size is determined during run-time. Those methods ignore an ordered removal of samples in order to find the best training data set for a given memory size. It is desired to have an EL method that produces an optimal training data set that satisfy predetermined memory size constraints, such as typically found in embedded systems. 
         [0023]    Validation Consistency 
         [0024]    The conventional EL methods remove samples if the classification error rate for the samples remaining in the training data set does not increase. Accordingly, a sample plays a dual role. That is, the sample participates both in updating the training data set and a testing set to be classified. As the removal progresses, the size and nature of the training data set dynamically varies, and thus the error-rates are determined over different sets that are not consistent and have lower statistical significance. It is desired to have a separate validation data set disjoint from the training data set, which remains unchanged during the removal process. 
       SUMMARY OF THE INVENTION 
       [0025]    The embodiments of the invention provide a method and a system for classifying data samples. More particularly, the samples are sensed by a sensor in an embedded system with limited memory. Therefore, the method constructs an exemplar data set of a predetermined size consistent with the size of the memory. 
         [0026]    In one embodiment, the method uses a training data set, which remains unchanged during the training, and a validation data set disjoint from the training data set. 
         [0027]    One embodiment of the invention uses entropy based exemplar learning (EBEL) procedure. The EBEL procedure removes instances of samples from the training data set based on information content of the training data set, instead of using an error rate. 
         [0028]    Instead of using an ad-hoc ranking scheme, the EBEL procedure removes a training data instance whose removal minimizes a decrease in a conditional entropy of a class indicator variable. This minimizes loss of information. The EBEL method has a low computational overhead, offers ordered removal, and is not sensitive to class-imbalance. 
         [0029]    Another embodiment of the invention uses an Area Under a receiver operator characteristic Curve (AUC) using an advanced broadband enabled learning (ABEL) procedure, which removes samples based on a performance of the AUC. The ABEL procedure uses the validation data set, and removes a sample if removal of the sample does not decrease the AUC determined over the validation data set. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0030]      FIG. 1  is a block diagram of a method and a system for classifying data according to embodiments of the invention; 
           [0031]      FIG. 2  is a block diagram of a method and a system for determining an exemplar data set according to embodiment of the inventions; 
           [0032]      FIG. 3  is pseudo code of an EBEL procedure according to an embodiment of the invention; and 
           [0033]      FIG. 4  is pseudo code of an ABEL procedure according to an embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0034]      FIG. 1  shows a method and a system  100  for classifying an input signal  101  using exemplar learning (EL) according to embodiments of our invention. The system could be embedded in some other machine or device  105  or work undependably. The system  100  has a limited size memory  130 . The input signal  101  is acquired by a sensor  110  and classified  140  in real-time. 
         [0035]    The sensor  110  acquires the signal  101  from an environment  103 . We use the term “environment” generally to mean anything that can be sensed, e.g., temperature, pressure, humidity, gas, liquid, solid, machines, acoustic and EM waveforms, camera images and the like. Typically, the environment relates to the operation of the device  105  in which the system  100  is embedded. The sensor generates data  102 . 
         [0036]    The data  102  are classified  140  to produce a data classification output  145 . The data classification  140  can be performed by a processor  150 . The data classification  140  uses an exemplar data set  135  to classify the data  102 . The exemplar data set  135  is stored in a memory  130  that has a limited size, i.e., the memory has a predetermined small size. Thus, a size of the exemplar data set  135  is adapted to fit the memory  130  according to the size of the memory. 
         [0037]    Determining the Exemplar Data Set 
         [0038]      FIG. 2  shows a block diagram of a method and a system  200  for determining the exemplar data set  135  according to an embodiment of the invention. The exemplar data set  135  is further utilized in the method and system  100  for data classification  140 . 
         [0039]    The embodiments of our invention can use an entropy-based EL (EBEL) procedure or an AUC-based EL (ABEL) procedure for learning  210  the exemplar data set  135 . The EL procedure  210  learns the exemplar data set  135  from a training data set  230  according to a limited memory size k  220  of the system  100 . 
         [0040]    The training data set  230  is determined  240  from a sample data set  260  and from a current exemplar data set  250 . In one embodiment of the invention, the determining  240  combines the sample data set  260  and the current exemplar data set  250 , as described herein. 
         [0041]    The sample data set  260  includes data samples for determining the training data set  230 . The sample data set  260  can be generated by some applications or can be constructed from the data  102  generated by the sensor  110 . The sample data set  260  can include one or more data samples. 
         [0042]    The system and method  200  initiate and update the exemplar data set  135 . During the initiation, the current exemplar data set  250  is empty, and the training data set  230  is determined  240  only from the sample data set  260 . During the updating, the current exemplar data set  250  is the exemplar data set  135  determined previously. 
         [0043]    In contrast with conventional EL procedures, the training data set  230  does not have to be determined using a training data set previously obtained. 
         [0044]    Parzen Kernel Density Estimate Based (PKDE) Classifier 
         [0045]    Our classifier  140  uses a Parzen kernel density estimate (PKDE) classifier. The PKDE classifier estimates a probability density function (pdf) of a random variable non-parametrically. However, our invention can also be generalized for any classifier. 
         [0046]    For a given class c and a training set S n  of n samples, a subset Z c   n  is 
         [0000]        Z   n   c   ={z |( z ε S   n )         (class( z )= c )}.   (1) 
         [0047]    For the PKDE classifier, a kernel function κ has a bandwidth λ. For the training subset S n , a density estimate f of a sample x belonging to class c is 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         f 
                         
                           c 
                            
                           
                               
                           
                         
                         n 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         
                           
                              
                             
                               Z 
                               n 
                               c 
                             
                              
                           
                            
                           λ 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             y 
                             ∈ 
                             
                                 
                             
                              
                             
                               Z 
                               n 
                               c 
                             
                           
                         
                          
                         
                           κ 
                            
                           
                             ( 
                             
                               
                                 x 
                                 - 
                                 y 
                               
                               λ 
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where y is sample element in Z c   n    
         [0048]    A prior probability π n   c  of each class is 
         [0000]    
       
         
           
             
               
                 
                   
                     π 
                     c 
                     n 
                   
                   = 
                   
                     
                       
                          
                         
                           Z 
                           n 
                           c 
                         
                          
                       
                       n 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0049]    We can determine a posterior probability p of an arbitrary sample x belonging to a particular class c, given the training data set S n , as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               p 
                                
                               
                                 ( 
                                 
                                   c 
                                   | 
                                   x 
                                 
                                 ) 
                               
                             
                             
                               S 
                               n 
                             
                           
                           = 
                             
                            
                           
                             
                               
                                 π 
                                 c 
                                 n 
                               
                                
                               
                                 
                                   f 
                                   c 
                                 
                                  
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   1 
                                 
                                 C 
                               
                                
                               
                                 
                                   π 
                                   j 
                                   n 
                                 
                                  
                                 
                                   
                                     f 
                                     j 
                                   
                                    
                                   
                                     ( 
                                     x 
                                     ) 
                                   
                                 
                               
                             
                           
                         
                         , 
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               
                                 ∑ 
                                 
                                   y 
                                   ∈ 
                                   
                                     Z 
                                     n 
                                     c 
                                   
                                 
                               
                                
                               
                                 κ 
                                  
                                 
                                   ( 
                                   
                                     
                                       x 
                                       - 
                                       y 
                                     
                                     λ 
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 ∑ 
                                 
                                   y 
                                   ∈ 
                                   
                                     S 
                                     n 
                                   
                                 
                               
                                
                               
                                 κ 
                                  
                                 
                                   ( 
                                   
                                     
                                       x 
                                       - 
                                       y 
                                     
                                     λ 
                                   
                                   ) 
                                 
                               
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0050]    For a binary classification problem, if the two classes are denoted by C +  and C − , then a merit-score γ n (x) of a sample x, given training data set S n , is 
         [0000]      γ n ( x )= p ( c   +   |x ) S   n   −p   n ( c   −   |x ) S   n .   (5) 
         [0051]    The merit-scores can be used analyzing the accuracy of the classification using area under receiver operating characteristic (AUC) curves, or threshold selection. 
         [0052]    Exemplar Learning 
         [0053]    We represent the training data set as          such that, |         =N, where N is the number of samples in the training data set. A training subset with n samples is S n , such that S n    ⊂           and S N =          Given the training subset S n , embodiments of the invention incrementally determine removed subsets 
         [0000]      ( S   n |(1 ≦n≦N )         ( S   n      ⊂  S   n +1)), 
         [0000]    such that a decrease in the classification accuracy in transitioning to S n  from S n +1 is less then predetermined threshold. 
         [0054]    A simple conventional solution finds all possible combinations of all subsets and selects the subset with the best performance, which has a complexity O(2 N ). 
         [0055]    Embodiments of our invention use incremental solutions that efficiently obtain S n−1  from S n . 
         [0056]    Entropy-Based Exemplar Learning (EBEL) Method 
         [0057]    For each sample in the training data set  230  x ε S n , EBEL determines the conditional entropy loss of a class variable using the subset S n \{x} as the training data set  230 , and x as the testing sample. EBEL selects and removes a selected sample such that a decrease in the conditional entropy is minimized. 
         [0058]    If C is the class, p(x) is the prior probability on a training instance x, and H(C\x) the entropy of the class variable conditioned on the presence of instance x, then EBEL selects and removes the selected samples according to: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       S 
                       
                         n 
                         - 
                         1 
                       
                     
                     = 
                     
                       
                         S 
                         n 
                       
                        
                       \ 
                        
                       
                         { 
                         
                           
                             
                               arg 
                                
                               
                                   
                               
                                
                               min 
                             
                             
                               x 
                               ∈ 
                               
                                 S 
                                 n 
                               
                             
                           
                            
                           
                             [ 
                             
                               H 
                                
                               
                                 ( 
                                 
                                   C 
                                   | 
                                   x 
                                 
                                 ) 
                               
                             
                             ] 
                           
                         
                         } 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     where 
                     , 
                     
                       
 
                     
                      
                     
                       
                         H 
                          
                         
                           ( 
                           
                             C 
                             | 
                             x 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           - 
                           
                             p 
                              
                             
                               ( 
                               x 
                               ) 
                             
                           
                         
                          
                         
                           
                             ∑ 
                             
                               c 
                               = 
                               1 
                             
                             C 
                           
                            
                           
                             
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     c 
                                     | 
                                     x 
                                   
                                   ) 
                                 
                               
                               
                                 
                                   S 
                                   n 
                                 
                                  
                                 \ 
                                  
                                 
                                   { 
                                   x 
                                   } 
                                 
                               
                             
                              
                             
                               log 
                                
                               
                                 ( 
                                 
                                   
                                     p 
                                      
                                     
                                       ( 
                                       
                                         c 
                                         | 
                                         x 
                                       
                                       ) 
                                     
                                   
                                   
                                     
                                       S 
                                       n 
                                     
                                      
                                     \ 
                                      
                                     
                                       { 
                                       x 
                                       } 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0059]    Because the training data set is independent and identically distributed (I.I.D.), the prior probability p(x) for any sample instance is constant and can be ignored. The classification error of a classifier          is lower bounded by the conditional entropy as 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                       
                         
                            
                            
                           
                             ( 
                             x 
                             ) 
                           
                         
                         ≠ 
                         C 
                       
                       ) 
                     
                   
                   ≥ 
                   
                     
                       
                         
                           H 
                            
                           
                             ( 
                             
                               C 
                               | 
                               x 
                             
                             ) 
                           
                         
                         - 
                         
                           log 
                            
                           
                             ( 
                             2 
                             ) 
                           
                         
                       
                       
                         log 
                          
                         
                           ( 
                           
                             C 
                             - 
                             1 
                           
                           ) 
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0060]    Thus, selecting the subset with the least conditional entropy is least likely to reduce the classification accuracy. 
         [0061]    Embodiments of the invention determine the most suitable candidate sample for removal in an efficient manner. By storing only the sum of the pair-wise kernel values of the training data set, the sample to be removed can be found in O(N) time. 
         [0062]    Given the training subset S n , we store a sum of the kernel values of each sample x j  ε S n  with all other samples in the class as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       v 
                       n 
                     
                      
                     
                       [ 
                       
                         c 
                         , 
                         j 
                       
                       ] 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         x 
                         ∈ 
                         
                           
                             
                               Z 
                               n 
                               c 
                             
                             ⋀ 
                             x 
                           
                           ≠ 
                           
                             x 
                             j 
                           
                         
                       
                     
                      
                     
                       κ 
                        
                       
                         ( 
                         
                           
                             x 
                             - 
                             
                               x 
                               j 
                             
                           
                           λ 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0063]    The conditional entropy of the class output variable with each instance x j  ε S n  can then be obtained as: 
         [0000]    
       
         
           
             
               
                 
                   
                     H 
                      
                     
                       ( 
                       
                         C 
                         | 
                         
                           x 
                           j 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     - 
                     
                       
                         ∑ 
                         
                           c 
                           = 
                           1 
                         
                         C 
                       
                        
                       
                         
                           
                             v 
                             n 
                           
                            
                           
                             [ 
                             
                               c 
                               , 
                               j 
                             
                             ] 
                           
                         
                          
                         
                           
                             log 
                              
                             
                               ( 
                               
                                 
                                   v 
                                   n 
                                 
                                  
                                 
                                   [ 
                                   
                                     c 
                                     , 
                                     j 
                                   
                                   ] 
                                 
                               
                               ) 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0064]    If instance y is selected for removal using Equation (6), then the ν-matrix can be updated as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       v 
                       
                         n 
                         - 
                         1 
                       
                     
                      
                     
                       [ 
                       
                         
                           class 
                            
                           
                             ( 
                             y 
                             ) 
                           
                         
                         , 
                         j 
                       
                       ] 
                     
                   
                   = 
                   
                     
                       
                         v 
                         n 
                       
                        
                       
                         [ 
                         
                           
                             class 
                              
                             
                               ( 
                               y 
                               ) 
                             
                           
                           , 
                           j 
                         
                         ] 
                       
                     
                     - 
                     
                       
                         κ 
                          
                         
                           ( 
                           
                             
                               
                                 x 
                                 j 
                               
                               - 
                               y 
                             
                             λ 
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0065]    For the training data set  230           , the kernel bandwidth is obtained, e.g., using A conventional bandwidth optimization scheme that minimizes A mean square error (MSE). If the density for a sample {circumflex over (f)}(x) is continuous in the r th  order, and does not change with the sample size, then the optimal bandwidth λ(n), which minimizes the MSE is related to the sample size n as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       λ 
                        
                       
                         ( 
                         n 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           
                             f 
                             ^ 
                           
                            
                           
                             ( 
                             x 
                             ) 
                           
                         
                          
                         
                           
                             ∫ 
                             
                               - 
                               ∞ 
                             
                             ∞ 
                           
                            
                           
                             
                               
                                 κ 
                                 2 
                               
                                
                               
                                 ( 
                                 y 
                                 ) 
                               
                             
                              
                             
                                
                               y 
                             
                           
                         
                       
                       
                         
                           ( 
                           
                             2 
                              
                             
                                 
                             
                              
                             
                               nrk 
                               r 
                             
                              
                             
                               
                                 f 
                                 r 
                               
                                
                               
                                 ( 
                                 x 
                                 ) 
                               
                             
                           
                           ) 
                         
                         
                           1 
                           
                             
                               2 
                                
                               r 
                             
                             + 
                             1 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where k r  is a characteristic component of the kernel function k(.). For r=2, the optimal bandwidth for a sample of size n is 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       λ 
                        
                       
                         ( 
                         n 
                         ) 
                       
                     
                     = 
                     
                       
                         λ 
                          
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                       
                         
                           ( 
                           
                             N 
                             n 
                           
                           ) 
                         
                         0.2 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where λ(N) is the bandwidth obtained using the training data set of size N, which minimizes the MSE. Although this prevents a significant computational effort of repeated bandwidth optimization with changing sample size, a bandwidth update still requires the re-computation of the ν-matrix in Equation (10). Because, the bandwidth varies slowly with the sample size as n −0.2 , we update the ν-matrix periodically when 
         [0000]    
       
         
           
             
               
                 
                   N 
                   last 
                 
                 / 
                 n 
               
               &gt; 
               
                 
                   
                     N 
                     last 
                   
                 
                 α 
               
             
             , 
           
         
       
     
         [0000]    where N last  is the size of the sample when the last bandwidth update occurred, and α is user-specified sensitivity parameter. 
         [0066]    The complexity of the incremental steps in the EBEL procedure are linear in the size of the training data set  230 . Thus, the runtime complexity of EBEL procedure for obtaining an exemplar data set  135  of size k from a training data set  230  of size N is O((N−k) α 2 N). 
         [0067]      FIG. 3  shows pseudo code of the EBEL procedure according to an embodiment of the invention. When the system is already using the current exemplar data set  250           for classification  140  and is updated with the sample data set  260            the EBEL method in the learning step  210  finds the exemplar data set  135  S s.t., |S|=k. The size k of the desired exemplar set is governed by the memory constrains  220 . The bandwidth value λ corresponding to          is obtained offline. During the initial stage we obtain the exemplar data set  135  of size k from the sample data set          by setting          =0; and          =         . 
         [0068]    The EBEL procedure first combines data from both the current exemplar data set  250           and the sample data set  260           and updates the corresponding kernel bandwidth accordingly, as shown in Step  1  on  FIG. 3 . 
         [0069]    After computing the ν-matrix, the EBEL procedure reduces the size of the training data set  230  S until the size reaches the desired value k. The instances of the training data set  230  are removed one at a time in steps  4 - 8 , and the ν-matrix is updated if the sample size becomes smaller than that allowed by the sensitivity parameter α, in steps  9 - 12 . The resulting exemplar data set  135  S, replaces the current exemplar data set  250           and is used for classifying  140  the sensed data  102 . 
         [0070]    AUC-Based Exemplar Learning (ABEL) Method 
         [0071]    The ABEL procedure addresses the issue of validation consistency by removing the samples of the training data set based on a dependency between the AUC performance over a consistent validation data set and retained samples. Thus, a sample has the dual role of training sample, as long as the sample is not removed, and a testing sample when determining conditional probabilities of Equation (6). 
         [0072]    At different stages of the ABEL procedure, the performance is validated, i.e., the entropy is determined for different data sets, thus reducing the statistical significance of the results. 
         [0073]    In the ABEL procedure, the validation data set is extracted from the training data set at the beginning of the removal operation, and the samples of the training data set are removed such that the AUC performance decreases, as a result of the number of removals is minimized. Given the training data set  230  S n , and a validation data set V, such that {V ∩ S n }=Ø, the ABEL procedure removes a sample x according to 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       S 
                       
                         n 
                         - 
                         1 
                       
                     
                     = 
                     
                       
                         S 
                         n 
                       
                        
                       \ 
                        
                       
                         { 
                         
                           
                             
                               arg 
                                
                               
                                   
                               
                                
                               max 
                             
                             
                               x 
                               ∈ 
                               
                                 S 
                                 n 
                               
                             
                           
                            
                           
                             [ 
                             
                               
                                 A 
                                  
                               
                                
                               
                                 ( 
                                 
                                    
                                   , 
                                   
                                     
                                       S 
                                       n 
                                     
                                      
                                     \ 
                                      
                                     
                                       { 
                                       x 
                                       } 
                                     
                                   
                                 
                                 ) 
                               
                             
                             ] 
                           
                         
                         } 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where          (X,Y) is the AUC value using a set X for testing and a set Y as the training data set. The ABEL procedure provides a simple yet effective EL framework that generalizes to any classifier. 
         [0074]    Given the merit scores of the samples in the validation data set, the AUC is determined without actually generating the ROC curve in O(|           2 ) time. However, for a finite set of samples the AUC is equal to the well known normalized Wilcoxon-Mann-Whitney (WMW) statistic            
         [0000]    
       
         
           
             
               
                 
                   
                     A 
                     = 
                     
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               1 
                             
                             p 
                           
                            
                           
                             1 
                             
                               ( 
                               
                                 
                                   γ 
                                   i 
                                   + 
                                 
                                 &gt; 
                                 
                                   γ 
                                   j 
                                   - 
                                 
                               
                               ) 
                             
                           
                         
                       
                       np 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where 
         [0000]      Γ + ={γ 1   + , γ 2   + , . . . , γ p   + } 
         [0000]    are the merit scores of the positive class and 
         [0000]      Γ − ={γ 1   − , γ 2   − , . . . , γ n   − } 
         [0000]    are the merit scores of the negative class samples in           (|         =n+p). The statistic uses a non-parametric test for assessing whether two samples come from the same distribution. 
         [0075]    Statistic          is the estimator of P(Γ + &gt;Γ), i.e., the probability that all positive class samples obtain a higher merit-score than the negative class samples, and if all the merit scores are sorted in non-decreasing order such that r i  is the rank of γ + , then          can be further simplified to 
         [0000]    
       
         
           
             
               
                 
                   A 
                   = 
                   
                     
                       1 
                       np 
                     
                      
                     
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               p 
                             
                              
                             
                               r 
                               i 
                             
                           
                           - 
                           
                             
                               p 
                                
                               
                                 ( 
                                 
                                   p 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                             2 
                           
                         
                         ) 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0076]    Equation (15) shows that given the merit scores of the validation data set, the AUC value can be determined in O(|          log(|         )) time. If          is the time taken by a classifier          to classify a testing sample using training data set           then the run-time complexity of ABEL is O(|V|·(log(|V|)+         ). 
         [0077]      FIG. 4  shows pseudo code of the ABEL procedure according to an embodiment of the invention. The ABEL procedure first extracts the validation data set from the training data  230 , given its fractional size of the validation data set (η) as an input parameter (Step  2 ) and then removes instances from the remaining samples of the training data set  230  (Step  3 - 6 ). The optimal value of the fractional size η depends on the size of the memory, and the complexity of the classification  140 . While a large value of the size η results in a high memory overhead, a small value reduces statistical significance of the AUC-scores of the validation data set elements resulting in worse instance removal decisions. One embodiment of the invention uses η=0.1. 
       EFFECT OF THE INVENTION 
       [0078]    Embodiments of our invention describe EBEL and ABEL procedures for determining an exemplar data set, which can be used for data classification in embedded systems with limited memory. The EBEL and ABEL procedures can be updated efficiently with new training data sets while maintaining high quality exemplar data sets of any user-defined size. 
         [0079]    It is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.