Abstract:
Systems, methods, and media that: implement a boosted classifier having a plurality of weak hypotheses that produce a classification, each of the plurality of weak hypotheses having at least one weight; receive testing data; receive at least one piece of training data subsequently to receiving the testing data; calculate corrective terms for correcting a sum of weights of correctly classified training data and a sum of weights of incorrectly classified training data; calculate the sum of weights of correctly classified training data and the sum of weights of incorrectly classified training data based on the corrective terms; modify the at least one weight of at least one of the plurality of weak hypotheses in response to the at least one piece of training data based on the sum of weights to produce modified weights; and classify the testing data based on the modified weights to produce a classification.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation-in-part of International Application No. PCT/US09/59592 (which is hereby incorporated by reference herein in its entirety), filed Oct. 5, 2009, which claims the benefit of U.S. Provisional Patent Application No. 61/102,766 (which is hereby incorporated by reference herein in its entirety), filed Oct. 3, 2008, and this application claims the benefit of U.S. Provisional Patent Applications Nos. 61/218,296, filed Jun. 18, 2009, 61/237,578, filed Aug. 27, 2009, 61/356,549, filed Jun. 18, 2010, each of which is hereby incorporated by reference herein in its entirety. 
     
    
     TECHNICAL FIELD 
       [0002]    The disclosed subject matter relates to systems, methods, and media for performing classification. 
       BACKGROUND 
       [0003]    Classification techniques are widely used for machine intelligence. Such techniques can be used for a wide variety of applications, such as, but not limited to, to perform image recognition, to control buying and selling of securities, to perform natural language processing, to perform medical detection functions (such as detecting cancer in an image), to perform stock market analysis (which can then be presented on a computer display, for example), to perform weather prediction, to perform analysis of motion in video images (which can then be used to generate new video (for display on a display, for example), to alert a user (e.g., in a security application), etc.), to provide bio sensors, to control systems (such as the motion of robots, the operation of HVAC systems, the operation of cruise control systems, the operation of navigation systems, etc.), etc. 
         [0004]    Techniques for boosting the performance of classifiers are known. For example, the Adaboost technique can be used to boost the performance of weak classifiers making up a classifier by repeatedly training the classifier to provide updates to the classifier weights corresponding to the weak classifiers. Adaboost is described in Robert E. Schapire et al., “Boosting the Margin: a New Explanation for the Effectiveness of Voting Methods,” Annals of Statistics, 26(5):1651-1686, 1998, which is hereby incorporated by reference herein in its entirety. 
         [0005]    In many instances, classifiers need to be updated when online—for example, when being used to perform classification. This the case, for example, because many classifiers are designed for general applications but only used in particular applications, where a more application-specific training would produce improved results. However, known techniques for boosting classifiers are inadequate. 
       SUMMARY 
       [0006]    Systems, methods, and media for performing classification are provided. In some embodiments, systems for performing classification are providing, the systems comprising: a processor that: implements a boosted classifier having a plurality of weak hypotheses that produce a classification, each of the plurality of weak hypotheses having at least one weight; receives testing data; receives at least one piece of training data subsequently to receiving the testing data; calculates corrective terms for correcting a sum of weights of correctly classified training data and a sum of weights of incorrectly classified training data; calculates the sum of weights of correctly classified training data and the sum of weights of incorrectly classified training data based on the corrective terms; modifies the at least one weight of at least one of the plurality of weak hypotheses in response to the at least one piece of training data based on the sum of weights to produce modified weights; and classifies the testing data based on the modified weights to produce a classification; and an output device that indicates the classification of the testing data. 
         [0007]    In some embodiments, methods for performing classification are provided, the methods comprising: implementing a boosted classifier having a plurality of weak hypotheses that produce a classification, each of the plurality of weak hypotheses having at least one weight; receiving testing data; receiving at least one piece of training data subsequently to receiving the testing data; calculating corrective terms for correcting a sum of weights of correctly classified training data and a sum of weights of incorrectly classified training data; calculating the sum of weights of correctly classified training data and the sum of weights of incorrectly classified training data based on the corrective terms; modifying the at least one weight of at least one of the plurality of weak hypotheses in response to the at least one piece of training data based on the sum of weights to produce modified weights; classifying the testing data based on the modified weights to produce a classification; and indicating the classification of the testing data. 
         [0008]    In accordance with some embodiments, computer-readable media encoded with computer executable instructions that when executed by a processor cause the processor to perform a method for performing classification, the method comprising: implementing a boosted classifier having a plurality of weak hypotheses that produce a classification, each of the plurality of weak hypotheses having at least one weight; receiving testing data; receiving at least one piece of training data subsequently to receiving the testing data; calculating corrective terms for correcting a sum of weights of correctly classified training data and a sum of weights of incorrectly classified training data; calculating the sum of weights of correctly classified training data and the sum of weights of incorrectly classified training data based on the corrective terms; modifying the at least one weight of at least one of the plurality of weak hypotheses in response to the at least one piece of training data based on the sum of weights to produce modified weights; classifying the testing data based on the modified weights to produce a classification; and indicating the classification of the testing data. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]      FIG. 1  is a diagram of a process for updating a classifier and performing classification in accordance with some embodiments. 
       
    
    
     DETAILED DESCRIPTION 
       [0010]    Systems, methods, and media for performing classification are provided. In some embodiments, classification techniques can be implemented as described herein. These classification techniques can receive one or more suitable inputs and generate one or more suitable outputs. The inputs can be any suitable testing data and training data. The outputs can be indications of how the testing data is classified based on the training data. For example, in some applications, a voice recognition mechanism can use a classifier to determine whether a word spoken by a user corresponds to a given word (e.g., “YES”). Training data of a user or other users speaking the given word can be used to train a classifier. A signal corresponding to the spoken word can subsequently be received as testing data. A trained classifier can then be used to determine whether the spoken word corresponds to the given word. If there is a match, an output indicating the match can be generated. 
         [0011]    As described above, a classifier can include one or more weak classifiers. For example, a classifier H(x) can be defined as: 
         [0000]        H ( x )=sign(Σ j=1   j α j   h   j ( x )).
 
         [0000]    In this definition: 
         [0000]        h   j ( x )ε{−1,1},
 
         [0000]    where h j (x) are the weak classifiers for input x that produce −1 if there is no match between the input x and the classification (e.g., corresponding to the word “YES” in the example above) for the classifier, and +1 if there is a match. Also, in this definition: 
         [0000]      α j ε         
 
         [0000]    where α j  are weights for the weak classifiers and           is the set of real numbers. 
         [0012]    In some embodiments, the performance of such a classifier H(x) can be improved by “boosting.” For example, in some embodiments, boosting techniques can be used to adjust the weights α j  used in the classifier. Moreover, as described further below, some of these boosting techniques can be operated while the classifier is online—e.g., being used to classify testing data. 
         [0013]    In some embodiments, classifiers and boosting techniques used in connection with them as described herein, can be used for any suitable application. For example, such techniques can be used to perform machine intelligence, to perform image recognition, to control buying and selling of securities, to perform natural language processing, to perform medical detection functions (such as detecting cancer in an image), to perform stock market analysis (which can then be presented on a computer display, for example), to perform weather prediction, to perform analysis of motion in video images (which can then be used to generate new video (for display on a display, for example), to alert a user (e.g., in a security application), etc.), to provide bio sensors, to control systems (such as the motion of robots, the operation of HVAC systems, the operation of cruise control systems, the operation of navigation systems, etc.), etc. 
         [0014]    Turning to  FIG. 1 , an example 100 of a process for boosting a classifier and using the classifier to test data in accordance with some embodiments is illustrated. As shown, after process  100  begins at  102 , the process can set an index variable i to zero. This index variable can be used to track the number of updates to the classifier (or the number of times the classifier is boosted). Also at  102 , an order parameter (K) and a smoothing parameter (ε) can be set. The order parameter K sets a tradeoff between accuracy and speed. Larger values for K increase the accuracy of the algorithm, but are more costly to compute. Any suitable order parameter and smoothing parameter can be used. 
         [0015]    Next, at  106 , a booster process (described below) can be initialized. Any suitable approach to initializing the booster process can be used in some embodiments. For example, in some embodiments, initialization can include initializing: weights for weak classifiers (α j ) to zero; the change in weights for classifiers (Δα j ) to zero; and the sums of correctly and incorrectly classified examples by weak hypothesis j (W jk   + , W jk   − ) to a smoothing parameter (ε), where j=0 . . . J, k=0 . . . J, and J is the number of weak classifiers in the classifier H. As another example, in some embodiments, AdaBoost can be run on a small set of training examples to initialize these parameters. 
         [0016]    At  108 , process  100  can then determine if any training data updates are available. These updates can be used to train the classifier while the classifier is online—for example, while the classifier is being used to evaluate testing data. If it is determined that a training update is available, then, at  110 , the index i can be updated and, at  112 , the updated training data can be received. This data can be received from any suitable source such as an operator manually classifying the training data, from a secondary system that classifies the training data, etc. In some embodiments, the training data can include training example margins m ij , where m ij  equals 1 for correctly classified examples and −1 for incorrectly classified examples. 
         [0017]    Next, at  114 , the received training data can be used to boost the classifier using any suitable approach. For example, using a first mechanism, the received training data can be used to boost the classifier as follows: 
         [0000]    
       
         
           
             d 
             = 
             1 
           
         
       
       
         
           
             
               for 
                
               
                   
               
                
               j 
             
             = 
             
               1 
                
               
                   
               
                
               to 
                
               
                   
               
                
               J 
                
               
                   
               
                
               do 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 j 
                 0 
               
               = 
               
                 max 
                  
                 
                   ( 
                   
                     0 
                     , 
                     
                       j 
                       - 
                       K 
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 π 
                 j 
                 + 
               
               = 
               
                 
                   ∏ 
                   
                     k 
                     = 
                     
                       j 
                       0 
                     
                   
                   
                     j 
                     - 
                     1 
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           W 
                           jk 
                           + 
                         
                         
                           W 
                           jj 
                           + 
                         
                       
                        
                       
                          
                         
                           
                             - 
                             Δ 
                           
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               W 
                               jk 
                               + 
                             
                             
                               W 
                               jj 
                               + 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 π 
                 j 
                 - 
               
               = 
               
                 
                   ∏ 
                   
                     k 
                     = 
                     
                       j 
                       0 
                     
                   
                   
                     j 
                     - 
                     1 
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           W 
                           jk 
                           - 
                         
                         
                           W 
                           jj 
                           - 
                         
                       
                        
                       
                          
                         
                           
                             - 
                             Δ 
                           
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               W 
                               jk 
                               - 
                             
                             
                               W 
                               jj 
                               - 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 for 
                  
                 
                     
                 
                  
                 k 
               
               = 
               
                 1 
                  
                 
                     
                 
                  
                 to 
                  
                 
                     
                 
                  
                 j 
                  
                 
                     
                 
                  
                 do 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 W 
                 jk 
                 + 
               
               ← 
               
                 
                   
                     W 
                     jk 
                     + 
                   
                    
                   
                     π 
                     j 
                     + 
                   
                 
                 + 
                 
                   d 
                    
                   
                       
                   
                    
                   
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ik 
                           
                           = 
                           
                             + 
                             1 
                           
                         
                         ] 
                       
                     
                     · 
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ij 
                           
                           = 
                           
                             + 
                             1 
                           
                         
                         ] 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 W 
                 jk 
                 - 
               
               ← 
               
                 
                   
                     W 
                     jk 
                     - 
                   
                    
                   
                     π 
                     j 
                     - 
                   
                 
                 + 
                 
                   d 
                    
                   
                       
                   
                    
                   
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ik 
                           
                           = 
                           
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                     · 
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ij 
                           
                           = 
                           
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               end 
                
               
                   
               
                
               for 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 α 
                 j 
                 i 
               
               = 
               
                 
                   1 
                   2 
                 
                  
                 
                     
                 
                  
                 log 
                  
                 
                     
                 
                  
                 
                   
                     W 
                     jj 
                     + 
                   
                   
                     W 
                     jj 
                     - 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 Δ 
                  
                 
                     
                 
                  
                 
                   α 
                   j 
                 
               
               = 
               
                 
                   α 
                   j 
                   i 
                 
                 - 
                 
                   α 
                   j 
                   
                     i 
                     - 
                     1 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               d 
               ← 
               
                 d 
                  
                 
                     
                 
                  
                 
                    
                   
                     
                       - 
                       
                         α 
                         j 
                         i 
                       
                     
                      
                     
                       m 
                       ij 
                     
                   
                 
               
             
           
         
       
       
         
           
             end 
              
             
                 
             
              
             for 
           
         
       
     
         [0000]    where: 
         [0018]    J is the number of weak classifiers; 
         [0019]    K is an order parameter; 
         [0020]    π j   + , π j   −  are corrective terms that correct sums of weights of correctly classified examples and incorrectly classified examples to better approximate the sum of weights that would be calculated in a batch Adaboost process; 
         [0021]    α j  are weights for the weak classifiers; 
         [0022]    Δα j  are the change in weights for the weak classifiers; 
         [0023]    m ij , m ik  are the margins for the weak classifiers against training data i, and equal 1 for correctly classified data and −1 for incorrectly classified training data—for example, m ij  can be set equal to y i *h i (x i ), where y i  is a value that represents the correct classification of training example i as +1 when it matches the classifier&#39;s classification and −1 when the it does not match the classifier&#39;s classification, and h j (x i ) is a value that represents the classification of training example i by weak classifier j as +1 when it matches the classifier&#39;s classification and −1 when the it does not match the classifier&#39;s classification; 
         [0024]    1 [] is an indicator function that indicates if an ith example was correctly classified or incorrectly classified by the jth hypothesis; and 
         [0025]    W jk   30 , W jk   −  are the sums of correctly and incorrectly classified training data examples by weak hypothesis j. 
         [0026]    As another example, using a second mechanism, the received training data can be used to boost the classifier at  114  as follows: 
         [0000]    
       
         
           
             d 
             = 
             1 
           
         
       
       
         
           
             
               ρ 
               0 
             
             = 
             0 
           
         
       
       
         
           
             
               for 
                
               
                   
               
                
               j 
             
             = 
             
               1 
                
               
                   
               
                
               to 
                
               
                   
               
                
               J 
                
               
                   
               
                
               do 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 ρ 
                 j 
               
               = 
               
                 
                   ρ 
                   
                     j 
                     - 
                     1 
                   
                 
                 + 
                 
                   
                     α 
                     j 
                   
                    
                   
                     
                       m 
                       ij 
                     
                     / 
                     
                       
                         z 
                         i 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   ρ 
                   ~ 
                 
                 
                   1 
                    
                   j 
                 
               
               = 
               
                 exp 
                  
                 
                   { 
                   
                     
                       - 
                       0.5 
                     
                      
                     
                         
                     
                      
                     
                       
                         max 
                          
                         
                           ( 
                           
                             
                               θ 
                               - 
                               
                                 ρ 
                                 j 
                               
                             
                             , 
                             0 
                           
                           ) 
                         
                       
                       2 
                     
                   
                   } 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 If 
                  
                 
                     
                 
                  
                 
                   
                     
                       ρ 
                       ~ 
                     
                     
                       1 
                        
                       j 
                     
                   
                   
                     1 
                     - 
                     
                       
                         ρ 
                         ~ 
                       
                       
                         1 
                          
                         j 
                       
                     
                   
                 
               
               ≤ 
               
                 
                   β 
                   
                     1 
                     - 
                     α 
                   
                 
                  
                 
                     
                 
                  
                 then 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               Continue 
                
               
                   
               
               [ 
               
                 
                   exit 
                    
                   
                       
                   
                    
                   out 
                    
                   
                       
                   
                    
                   
                     for 
                      
                     
                         
                     
                      
                     &#39;&#39; 
                   
                    
                   
                       
                   
                    
                   for 
                    
                   
                       
                   
                    
                   j 
                 
                 = 
                 
                   
                     … 
                      
                     
                         
                     
                      
                     &#39;&#39; 
                   
                    
                   
                       
                   
                    
                   loop 
                 
               
               ] 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 j 
                 0 
               
               = 
               
                 max 
                  
                 
                   ( 
                   
                     0 
                     , 
                     
                       j 
                       - 
                       K 
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 π 
                 j 
                 + 
               
               = 
               
                 
                   ∏ 
                   
                     k 
                     = 
                     
                       j 
                       0 
                     
                   
                   
                     j 
                     - 
                     1 
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           W 
                           jk 
                           + 
                         
                         
                           W 
                           jj 
                           + 
                         
                       
                        
                       
                          
                         
                           
                             - 
                             Δ 
                           
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               W 
                               jk 
                               + 
                             
                             
                               W 
                               jj 
                               + 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 π 
                 j 
                 - 
               
               = 
               
                 
                   ∏ 
                   
                     k 
                     = 
                     
                       j 
                       0 
                     
                   
                   
                     j 
                     - 
                     1 
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           W 
                           jk 
                           - 
                         
                         
                           W 
                           jj 
                           - 
                         
                       
                        
                       
                          
                         
                           
                             - 
                             Δ 
                           
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               W 
                               jk 
                               - 
                             
                             
                               W 
                               jj 
                               - 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 for 
                  
                 
                     
                 
                  
                 k 
               
               = 
               
                 1 
                  
                 
                     
                 
                  
                 to 
                  
                 
                     
                 
                  
                 j 
                  
                 
                     
                 
                  
                 do 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 W 
                 jk 
                 + 
               
               ← 
               
                 
                   
                     W 
                     jk 
                     + 
                   
                    
                   
                     π 
                     j 
                     + 
                   
                 
                 + 
                 
                   d 
                    
                   
                       
                   
                    
                   
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ik 
                           
                           = 
                           
                             + 
                             1 
                           
                         
                         ] 
                       
                     
                     · 
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ij 
                           
                           = 
                           
                             + 
                             1 
                           
                         
                         ] 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 W 
                 jk 
                 - 
               
               ← 
               
                 
                   
                     W 
                     jk 
                     - 
                   
                    
                   
                     π 
                     j 
                     - 
                   
                 
                 + 
                 
                   d 
                    
                   
                       
                   
                    
                   
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ik 
                           
                           = 
                           
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                     · 
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ij 
                           
                           = 
                           
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               end 
                
               
                   
               
                
               for 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 α 
                 j 
                 i 
               
               = 
               
                 
                   1 
                   2 
                 
                  
                 
                     
                 
                  
                 log 
                  
                 
                     
                 
                  
                 
                   
                     W 
                     jj 
                     + 
                   
                   
                     W 
                     jj 
                     - 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 Δ 
                  
                 
                     
                 
                  
                 
                   α 
                   j 
                 
               
               = 
               
                 
                   α 
                   j 
                   i 
                 
                 - 
                 
                   α 
                   j 
                   
                     i 
                     - 
                     1 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               d 
               ← 
               
                 d 
                  
                 
                     
                 
                  
                 
                    
                   
                     
                       - 
                       
                         α 
                         j 
                         i 
                       
                     
                      
                     
                       m 
                       ij 
                     
                   
                 
               
             
           
         
       
       
         
           
             end 
              
             
                 
             
              
             for 
           
         
       
     
         [0027]    Update z i =Σ k=1   n α k   2  by updating coordinates 1 . . . j 
         [0000]    where: 
         [0028]    variables in common with the first mechanism are similarly defined; 
         [0029]    z 1  is initialized to 1; 
         [0030]    ρ j  is the margin of an example for a feature j. 
         [0031]    θ is a threshold and can be set equal to 0 (or any other suitable value or values (e.g., a different value within a range for each classifier)); 
         [0032]    α=0.95 (or any other suitable value); and 
         [0033]    β=0.8 (or any other suitable value). 
         [0034]    As can be seen in the first four lines of the “for j=” loop of this second mechanism, the computation of feature evaluations can be stopped early by exiting out of the “for j=” loop via the continue instruction when uninformative examples are received. The determination of whether to stop processing on an example (a piece of training data) can be made based on any suitable criteria or criterion, such as the cumulative margin of the example at a feature j. In this way, the boosting process can be made faster. 
         [0035]    As yet another example, using a third mechanism, the received training data can be used to boost the classifier at  114  as follows: 
         [0000]    
       
         
           
             d 
             = 
             1 
           
         
       
       
         
           
             
               S 
               0 
             
             = 
             0 
           
         
       
       
         
           
             
               for 
                
               
                   
               
                
               j 
             
             = 
             
               1 
                
               
                   
               
                
               to 
                
               
                   
               
                
               J 
                
               
                   
               
                
               do 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 j 
                 0 
               
               = 
               
                 max 
                  
                 
                   ( 
                   
                     0 
                     , 
                     
                       j 
                       - 
                       K 
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 S 
                 j 
               
               = 
               
                 
                   S 
                   
                     j 
                     - 
                     1 
                   
                 
                 + 
                 
                   
                     y 
                     i 
                   
                    
                   
                     α 
                     j 
                   
                    
                   
                     
                       h 
                       j 
                     
                      
                     
                       ( 
                       
                         x 
                         i 
                       
                       ) 
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 π 
                 j 
                 + 
               
               = 
               
                 
                   ∏ 
                   
                     k 
                     = 
                     
                       j 
                       0 
                     
                   
                   
                     j 
                     - 
                     1 
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           W 
                           jk 
                           + 
                         
                         
                           W 
                           jj 
                           + 
                         
                       
                        
                       
                          
                         
                           
                             - 
                             Δ 
                           
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               W 
                               jk 
                               + 
                             
                             
                               W 
                               jj 
                               + 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 π 
                 j 
                 - 
               
               = 
               
                 
                   ∏ 
                   
                     k 
                     = 
                     
                       j 
                       0 
                     
                   
                   
                     j 
                     - 
                     1 
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           W 
                           jk 
                           - 
                         
                         
                           W 
                           jj 
                           - 
                         
                       
                        
                       
                          
                         
                           
                             - 
                             Δ 
                           
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               W 
                               jk 
                               - 
                             
                             
                               W 
                               jj 
                               - 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             α 
                             k 
                           
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 for 
                  
                 
                     
                 
                  
                 k 
               
               = 
               
                 1 
                  
                 
                     
                 
                  
                 to 
                  
                 
                     
                 
                  
                 j 
                  
                 
                     
                 
                  
                 do 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 W 
                 jk 
                 + 
               
               ← 
               
                 
                   
                     W 
                     jk 
                     + 
                   
                    
                   
                     π 
                     j 
                     + 
                   
                 
                 + 
                 
                   d 
                    
                   
                       
                   
                    
                   
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ik 
                           
                           = 
                           
                             + 
                             1 
                           
                         
                         ] 
                       
                     
                     · 
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ij 
                           
                           = 
                           
                             + 
                             1 
                           
                         
                         ] 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 W 
                 jk 
                 - 
               
               ← 
               
                 
                   
                     W 
                     jk 
                     - 
                   
                    
                   
                     π 
                     j 
                     - 
                   
                 
                 + 
                 
                   d 
                    
                   
                       
                   
                    
                   
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ik 
                           
                           = 
                           
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                     · 
                     
                       1 
                       
                         [ 
                         
                           
                             m 
                             ij 
                           
                           = 
                           
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               end 
                
               
                   
               
                
               for 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 α 
                 j 
                 i 
               
               = 
               
                 
                   1 
                   2 
                 
                  
                 
                     
                 
                  
                 log 
                  
                 
                     
                 
                  
                 
                   
                     W 
                     jj 
                     + 
                   
                   
                     W 
                     jj 
                     - 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 Δ 
                  
                 
                     
                 
                  
                 
                   α 
                   j 
                 
               
               = 
               
                 
                   α 
                   j 
                   i 
                 
                 - 
                 
                   α 
                   j 
                   
                     i 
                     - 
                     1 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               d 
               ← 
               
                 d 
                  
                 
                     
                 
                  
                 
                    
                   
                     
                       - 
                       
                         α 
                         j 
                         i 
                       
                     
                      
                     
                       m 
                       ij 
                     
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 If 
                  
                 
                     
                 
                  
                 
                   S 
                   j 
                 
               
               &gt; 
               
                 θ 
                 + 
                 
                   
                      
                     
                       α 
                       jJ 
                     
                      
                   
                    
                   
                     
                       ln 
                        
                       
                         1 
                         
                           δ 
                           2 
                         
                       
                     
                   
                    
                   
                       
                   
                    
                   then 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               Continue 
                
               
                   
               
               [ 
               
                 
                   exit 
                    
                   
                       
                   
                    
                   out 
                    
                   
                       
                   
                    
                   
                     for 
                      
                     
                         
                     
                      
                     &#39;&#39; 
                   
                    
                   
                       
                   
                    
                   for 
                    
                   
                       
                   
                    
                   j 
                 
                 = 
                 
                   
                     … 
                      
                     
                         
                     
                      
                     &#39;&#39; 
                   
                    
                   
                       
                   
                    
                   loop 
                 
               
               ] 
             
           
         
       
       
         
           
             end 
              
             
                 
             
              
             for 
           
         
       
     
         [0000]    where: 
         [0036]    variables in common with the first and/or second mechanism are similarly defined; 
         [0037]    S j ; is the margin of an example for a feature j; 
         [0038]    α jJ  is the norm of the remaining weights, which can be calculated in any suitable fashion, such as by initializing ∥α 1,n ∥ 2 =∥α∥ 2 −α 1   2  and updating the norms of the remaining weights ∥α in ∥(where i=1 . . . n−1) every time a feature is updated with ∥α i+1, n ∥ 2 =∥α in ∥ 2 −α i+1   2 ; 
         [0039]    θ is a threshold and can be set equal to 0 (or any other suitable value or values (e.g., a different value within a range for each classifier)); 
         [0040]    δ=0.8 (or any other suitable value, such as 0.1). 
         [0041]    Like in the second mechanism, as can be seen in the lines referencing the variable “S” of this third mechanism, the computation of feature evaluations can be stopped early by exiting out of the “for j=” loop via the continue instruction when uninformative examples are received. The determination of whether to stop processing on an example (a piece of training data) can be made based on any suitable criteria or criterion, such as the cumulative margin of the example at a feature j. In this way, the boosting process can be made faster. 
         [0042]    After the classifier weights have been updated at  114 , or after it is determined at  108  that a training update is not available, then, at  116 , process  100  can determine if any testing data is available. This testing data can be received from any suitable source. If testing data is determined to be available, then process  100  can receive the testing data at  118  using any suitable mechanism. For example, this testing data can be received over any suitable interface. 
         [0043]    Next, at  120 , the testing data can be evaluated using a classifier using the classifier weights. For example, as set forth above, the classifier can be defined as follows: 
         [0000]        H ( x )=sign(Σ j=1   J α j   h   j ( x ))
 
         [0000]    where: 
         [0044]    J is the number of weak classifiers making up the classifier; 
         [0045]    α j ε          are the weights; 
         [0046]    h j (x)ε{−1,1} are the weak classifiers; and 
         [0047]    H(x) returns +1 if the testing data matches the classification corresponding to the 
         [0048]    classifier and −1 the testing data does not match that classification. 
         [0000]    Any suitable weak classifiers can be used to make up the classifier in some embodiments. 
         [0049]    Finally, at  122 , the results of the evaluation can be output. These results can be output to any suitable device and be used for any suitable purpose. Once the results are output, process  100  can loop back to  108  to check for additional training updates. 
         [0050]    In some embodiments, process  100  can additionally include any suitable mechanism for performing feature selection. For example, feature selection as described in N. Oza et al., “Online Bagging and Boosting,” In  Artificial Intelligence and Statistics , pages 105-112, Morgan Kaufmann, 2001 and/or H. Grabner et al., “On-Line Boosting and Vision,” In  Proceedings IEEE Conference on Computer Vision and Pattern Recognition  ( CVPR ), volume 1, pages 260-267, 2006, each of which are hereby incorporated by reference herein in their entireties, can be used in some embodiments. 
         [0051]    In accordance with some embodiments, classification techniques can be implemented in any suitable hardware and/or software capable of performing the functions described herein. For example, the classification techniques can be implemented in one or more processors using suitable software. More particularly, such processors can include any suitable computers, servers, microprocessors, controllers, digital signal processors, programmable logic devices, etc. The software for controlling such processors can be stored on any suitable computer readable media, such as disk drives, compact disks, digital video disks, memory (such as random access memory, read only memory, flash memory, etc.), and/or any other suitable media. The classification techniques can be coupled to output devices using any suitable interface. For example, the classification techniques can interface to display screens though a video interface, to network devices through a network interface, to electro-mechanical devices though a servo controller (or any other suitable controller), etc. Inputs to the classification techniques can be provided from any suitable input devices, such as a keyboard, a mouse, a stock market data feed, a video input device, a bio interface (such as a pulse monitor, blood pressure monitor, fingerprint reader, eye scanner, etc.), a motion sensor, a thermostat, a humidity detector, a solar detector, a speed detector, a direction detector, a location detector (such as global positioning system receiver), etc. 
         [0052]    In some embodiments, any suitable computer readable media can be used for storing instructions for performing the processes described herein. For example, in some embodiments, computer readable media can be transitory or non-transitory. For example, non-transitory computer readable media can include media such as magnetic media (such as hard disks, floppy disks, etc.), optical media (such as compact discs, digital video discs, Blu-ray discs, etc.), semiconductor media (such as flash memory, electrically programmable read only memory (EPROM), electrically erasable programmable read only memory (EEPROM), etc.), any suitable media that is not fleeting or devoid of any semblance of permanence during transmission, and/or any suitable tangible media. As another example, transitory computer readable media can include signals on networks, in wires, conductors, optical fibers, circuits, any suitable media that is fleeting and devoid of any semblance of permanence during transmission, and/or any suitable intangible media. 
         [0053]    Although the invention has been described and illustrated in the foregoing illustrative embodiments, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the details of implementation of the invention can be made without departing from the spirit and scope of the invention, which is only limited by the claims which follow. Features of the disclosed embodiments can be combined and rearranged in various ways.