Abstract:
The present invent ion provides a condensed SVM for high-speed learning using a large amount of training data. A first stage WS selector samples a plurality of training data from a training data DB, selects an optimal training vector x t  among the plurality of training data, and outputs it to the WS manager. After the first stage finishes, a second stage WS selector extracts training data one by one from the training data DB and selects training data x t  satisfying optimality and outputs it to the WS manager. An SVM optimizer extracts training data closest to the training data x t  selected by the first and second stage WS selectors from the WS being managed by the WS manager, and condenses the two first and second training data to one training data when the distance between these is smaller than a predetermined value.

Description:
[0001]    The present application is claims priority of Japanese Patent Application Serial No. 2009-018011, filed Jan. 29, 2009, the content of which is hereby incorporated by reference in its entirety. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to an SVM (Support Vector Machine) for classifying many objects based on their multiple characteristics, more specifically, to a condensed SVM for high-speed training using a large collection of data. 
         [0004]    2. Description of the Related Art 
         [0005]    Given training data x i  (here, i=1, 2, . . . , I) with labels y i  of −1 and +1, a major task of SVM learning is to solve the following quadratically constrained quadratic programming problem (QP problem) of Formula 1. 
         [0000]    
       
         
           
             
               
                 
                   
                     [ 
                     
                       Formula 
                        
                       
                           
                       
                        
                       1 
                     
                     ] 
                   
                    
                   
                       
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           min 
                           α 
                         
                          
                         
                           L 
                            
                           
                             ( 
                             α 
                             ) 
                           
                         
                       
                       = 
                       
                         
                           
                             1 
                             
                               2 
                                
                               
                                   
                               
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 i 
                                 , 
                                 
                                   j 
                                   = 
                                   1 
                                 
                               
                               l 
                             
                              
                             
                               
                                 y 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                 
                               
                                
                               
                                 y 
                                 j 
                               
                                
                               
                                 α 
                                 i 
                               
                                
                               
                                 α 
                                 j 
                               
                                
                               
                                 K 
                                  
                                 
                                   ( 
                                   
                                     
                                       x 
                                       i 
                                     
                                     , 
                                     
                                       x 
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         - 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             l 
                           
                            
                           
                             α 
                             i 
                           
                         
                       
                     
                      
                     
                       
 
                     
                      
                     
                       
                         
                           subject 
                            
                           
                               
                           
                            
                           to 
                            
                           
                               
                           
                            
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                               
                               l 
                             
                              
                             
                               
                                 y 
                                 i 
                               
                                
                               
                                 α 
                                 i 
                               
                             
                           
                         
                         = 
                         0 
                       
                       , 
                       
                         
 
                       
                        
                       
                         0 
                         ≤ 
                         
                           α 
                           i 
                         
                         ≤ 
                         
                           
                             C 
                             i 
                           
                            
                           
                             ( 
                             
                               
                                 i 
                                 = 
                                 1 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               l 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0006]    Where K (x i , x j ) is a kernel function for calculating an inner product between two vectors x i  and x j  in some feature spaces, and C i  (i=1, 2, . . . , I) is a parameter penalizing noisy training data in the given training data. 
         [0007]    When attempting to solve the above problem, the following difficulties arise when the number Is of the training data becomes larger.
   1) Problem in capacity of a memory storing the kernel matrix K ij =K(x i , x j ) (here, i, j=1, 2, . . . , I). The data amount of the kernel matrix easily exceeds the memory capacity of a conventional computer.   2) Computational complexity to compute a kernel value K ij  (i, j=1, 2, . . . , I).   3) Computational complexity to solve the QP problem.   
 
         [0011]    In the testing phase, the decision function f(x) of SVM is expressed by Formula 2, and is composed of a set of Ns training data x i  (i=1, 2, . . . , Ns) called support vectors (SVs). 
         [0000]    
       
         
           
             
               
                 
                   
                     [ 
                     
                       Formula 
                        
                       
                           
                       
                        
                       2 
                     
                     ] 
                   
                    
                   
                       
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     f 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           N 
                           S 
                         
                       
                        
                       
                         
                           α 
                           i 
                         
                          
                         
                           K 
                            
                           
                             ( 
                             
                               
                                 x 
                                 i 
                               
                               , 
                               x 
                             
                             ) 
                           
                         
                       
                     
                     + 
                     b 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0012]    Complexity of the decision function f (x) of the SVM linearly increases as the number Ns of support vectors increases. When this number becomes larger, the speed of SVM in the testing phase becomes slower due to an increase in the amount of computations of the kernel value K (x i , x) (i=1, 2, . . . , Ns). 
         [0013]    Therefore, conventionally, the following various methods have been proposed to improve the scalability of the support vector learning in both the training and testing phases. 
       1. Decomposition Algorithms (the Following Non-Patent Documents 2, 3, 4, and 5) 
       [0014]    The decomposition method decomposes the original QP into a series of much smaller QPs, and then optimizes these sub-problems. Training data are divided into two parts: a set of active vectors and a set of inactive vectors. In the set of active vectors or working set, the coefficient α i  can be updated. On the other hand, in the set of inactive vectors, the coefficient a i  is temporarily fixed. The optimization algorithm runs only on a small number of working data, not on the whole data. Therefore, the problem in which the memory capacity increases by a square and computational complexity increases by a cube is avoided. In each optimization loop, the working data are updated to find a new SVM solution. The process training (learning) will finish when optimal conditions are satisfied. 
       2. Parallelization (the Following Non-Patent Documents 6 and 7) 
       [0015]    The training speed of SVM can be improved effectively by using a parallel algorithm running on a parallel computer. 
       3. Data Sampling (the Following Non-Patent Documents 8, 9, and 10) 
       [0016]    Various methods for selecting important training data have been proposed to reduce the size of the optimization problem of Formula 1. An SVM which is learned from a small amount of data can have good performance in many cases. 
       4. Reduced Set Method for SVM Simplification (the Following Non-Patent Documents 11 and 12) 
       [0017]    To increase the speed of SVM in the testing phase, a reduced set method replaces the SVM decision function (see Formula 2) having Ns SVs by a simplified SVM decision function consisting of Nz vectors called reduced vectors (Nz&lt;Ns). It is practically shown that the reduced set method can produce a simplified SVM with similar performance to that of the conventional SVM. 
         [0018]    Non-Patent Document 1: C. Cortes and V. Vapnik, “Support vector networks,” Machine Learning, vol. 20, pp. 273-297, 1995. 
         [0019]    Non-Patent Document 2: E. Osuna, R. Freund, and F. Girosi, “An improved training algorithm for support vector machines,” in Neural Networks for Signal Processing VII—Proceedings of the 1997 IEEE Workshop, N. M. J. Principe, L. Gile and E. Wilson, Eds., New York, pp. 276-285, 1997. 
         [0020]    Non-Patent Document 3: T. Joachims, “Making large-scale support vector machine learning practical,” in Advances in Kernel Methods: Support Vector Machines, A. S. B. Scholkopf, C. Burges, Ed., MIT Press, Cambridge, Mass., 1998. 
         [0021]    Non-Patent Document 4: J. Platt, “Fast training of support vector machines using sequential minimal optimization,” in Advances in Kernel Methods-Support Vector Learning, B. Scholkopf, C. J. C. Burges, and A. J. Smola, Eds., Cambridge, Mass.: MIT Press, 1999. 
         [0022]    Non-Patent Document 5: Duc Dung Nguyen; Matsumoto, K.; Takishima, Y.; Hashimoto, K.; Terabe, M., “Two-stage incremental working set selection for fast support vector training on large datasets,” Research, Innovation and Vision for the Future, 2008. RIVF2008. IEEE International Conference on, vol., no., pp. 221-226, 13-17 Jul. 2008. 
         [0023]    Non-Patent Document 6: R. Collobert, S. Bengio, and Y. Bengio, “A parallel mixture of svms for very large scale problems,” Neural Computation, vol. 14, no. 5, pp. 1105-1114, 2002. 
         [0024]    Non-Patent Document 7: G. H. Peter, C. Eric, B. L&#39;eon, D. Igor, and V. Vladimir, “Parallel support vector machines: The Cascade SVM,” in Advances in Neural Information Processing Systems, L. Saul, Y. Weiss, and L. Bottou, Eds., vol. 17. MIT Press, 2005. 
         [0025]    Non-Patent Document 8: Y.-J. Lee and O. L. Mangasarian, “Rsvm: Reduced support vector machines,” in Proceedings of the First SIAM International Conference on Data Mining. Morgan Kaufmann, San Francisco, Calif., 2001. 
         [0026]    Non-Patent Document 9: A. Bordes, S. Ertekin, J. Weston, and L. Bottou, “Fast kernel classifiers with online and active learning,” Journal of Machine Learning Research, vol. 6, pp. 1579-1619, 2005. 
         [0027]    Non-Patent Document 10: I. W. Tsang, J. T. Kwok, and P.-M. Cheung, “Core vector machines: Fast svm training on very large data sets,” J. Mach. Learn. Res., vol. 6, pp. 363-392, 2005. 
         [0028]    Non-Patent Document 11: C. J. C. Burges, “Simplified support vector decision rules,” in Proc. 13th International Conference on Machine Learning, San Mateo, Calif., 1996, pp. 71-77. 
         [0029]    Non-Patent Document 12: Nguyen, D. D., Ho, T. B. A Bottom-up Method for Simplifying Support Vector Solutions, IEEE Transactions on Neural Networks, Vol. 17, No. 3, 792-796, 2006. 
         [0030]    The methods have the following problems: 
       1. Decomposition Algorithms 
       [0031]    When working on a large amount of data (e.g. training data more than 100,000), the convergence speed becomes slow. Computational complexity increases by a cube of the number of support vectors and the memory capacity increases by a square of the number of support vectors. 
       2. Parallelization 
       [0032]    Designing an algorithm suitable for making the communication cost reasonable, questions still remain in computing ability and kernel caching in practice. Moreover, improving the speed of optimization through parallelization is difficult due to dependency between computation steps. 
       3. Data Sampling 
       [0033]    The biggest issue of this process is the degradation of the trained SVM because only limited information (training data) is used for optimization. In addition, it is difficult to select a suitable sampling method for each practical application. 
       4. Reduced Set Method for SVM Simplification 
       [0034]    The reduced set method works on the assumption that SVM has already been trained by a training algorithm, and the task of the method is to retrain this machine. Moreover, it is required to retrain the simplified SVM and minimize a function of a variable (d+1) Nz (d is the order of the training vector). This is not an easy task especially when the number of reduced vectors Nz is large. 
       SUMMARY OF THE INVENTION 
       [0035]    An object of the present invention is to provide a condensed SVM for high-speed learning using a large amount of training data. 
         [0036]    In order to achieve the object, this invention is characterized in that a condensed SVM comprises a training database having large training data, a first stage working set (WS) selector performing repeatedly steps of selecting a plurality of training data from the training database and obtaining one optimal training vector among the plurality of training data, a second stage working set (WS) selector extracting training data one by one from the training database and selecting training data satisfying optimality after the first stage finishes, a working set (WS) manager managing the training data selected by the first and second stage WS selectors, and an SVM optimizer including means for extracting second training data closest to the first training data selected by the first and second stage WS selectors from a WS managed by the WS manager, and condensing two first and second training data to one training data when the distance between the first and second training data is smaller than a predetermined value. 
         [0037]    This invention is further characterized in that the SVM optimizer further inspects whether non-support data exists in the WS when the distance between the first and second training data is larger than the predetermined value, and when non-support data exists, deletes the non-support data. 
         [0038]    This invention is further characterized in that the SVM optimizer further adds the first training data to the WS when non-support data does not exist in the WS. 
         [0039]    According to the present invention, two training data closest to each other are condensed (combined) to one training data, so that even if the number of training data increases, the number of support vectors is not greatly increased. Therefore, the SVM can learn with a small number of support vectors, so that a condensed SVM which realizes high-speed learning even when a large amount of training data is used, can be provided. 
         [0040]    When the two training data closest to each other are larger than a predetermined value, it is inspected whether a non-support vector exists in a WS, and when a non-support vector exists, the non-support vector is deleted from the WS, so that the WS does not greatly increase. Therefore, even if a large amount of training data is used, the SVM can learn at a high speed. 
         [0041]    The number of support vectors and the WS do not greatly increase, so that the SVM can learn by using a large amount of training data without increasing the memory capacity of the SVM. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0042]      FIG. 1  is a flowchart showing an exemplary configuration of a condensed SVM of the present invention; 
           [0043]      FIG. 2  is a flowchart showing a function of a first stage WS selector of  FIG. 1 ; 
           [0044]      FIG. 3  is a flowchart showing a function of an SVM optimizer of  FIG. 1 ; 
           [0045]      FIG. 4  is a flowchart showing a function of a second stage WS selector of  FIG. 1 ; 
           [0046]      FIG. 5  is an explanatory view of an operation of condensing training vectors in the SVM optimizer; 
           [0047]      FIG. 6  is an explanatory view showing the outline of operations of the first stage; 
           [0048]      FIG. 7  is a graph for explaining differences between the method of the present invention and a conventional method. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0049]    Hereinafter, the present invention will be described in detail with reference to the drawings.  FIG. 1  is a block diagram showing an exemplary configuration of a condensed SVM of the present invention. 
         [0050]    As shown in the figure, the condensed SVM includes a training data (or case) DB (database)  1 , an SVM solution initializer  2 , a first stage WS (working set) selector  3 , a second stage WS (working set) selector  4 , a WS manager  5 , and an SVM optimizer  6 . 
         [0051]    The training data DB  1  preferably consists of training data of correct answer cases. In the initializer  2 , an SVM solution is initialized. 
         [0052]    The first stage WS selector  3  performs the function shown in the flowchart of  FIG. 2 . At Step S 1 , m training data x k  (k=1, 2, . . . , m) are sampled from the training data DB  1 , and a training data set S is formed from the sampled m training data x k . At Step S 2 , optimal training data (vector) x t  concerning a temporal SVM solution is obtained from the training data set S. The optimal training data (vector) x t  can be obtained from the following formula. 
         [0000]    
       
         
           
             
               
                 
                   
                     [ 
                     
                       Formula 
                        
                       
                           
                       
                        
                       3 
                     
                     ] 
                   
                    
                   
                       
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     x 
                     t 
                   
                   = 
                   
                     
                       argmax 
                       
                         
                           x 
                           k 
                         
                         ∈ 
                         S 
                       
                     
                      
                     
                       { 
                       
                         
                           y 
                           k 
                         
                         - 
                         
                           
                             f 
                             k 
                           
                            
                           
                             ( 
                             
                               x 
                               k 
                             
                             ) 
                           
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0053]    y k  in the formula given above indicates a label value of +1 or −1, and f(x k ) indicates an SVM solution of the training data x k . 
         [0054]    Next, the process proceeds to Step S 3 , and the optimality of the optimal training data x t  is checked depending on whether the optimal training data x t  satisfies the condition of {y t −f t (x t )}&gt;0. When this condition is satisfied, the process proceeds to Step S 4  and this optimal training data x t  is output to the WS manager  5 . On the other hand, when this condition is not satisfied, the process returns to Step S 1  and new m training data x k  (k=1, 2, . . . , m) are sampled from the training data DB  1 , and the same operation as described above is repeated. Thus, the optimal training data (vectors) x t  are output one by one from the first stage WS selector  3 . 
         [0055]    Next, the WS manager  5  receives the optimal training data (vectors) x t  whose optimality has been checked from the first and second stage WS selectors  3  and  4 , and updates the temporal WS (working set). The operation of the second stage WS selector  4  will be described later. 
         [0056]    Next, the updated temporal WS is sent to the SVM optimizer  6 . The function of the SVM optimizer  6  will be described with reference to the flowchart of  FIG. 3 . 
         [0057]    At Step S 11 , the SVM optimizer  6  receives a new training vector x t  and the temporal working set B t  (hereinafter, referred to as B t , simply) from the WS manager  5 . Here, B t  is an accumulation of training vectors x t  obtained through continuous operation of the machine of  FIG. 1 . At Step S 12 , the SVM optimizer  6  searches and finds a vector x i  closest to the new training vector x t  in B t . At Step S 13 , the SVM optimizer  6  determines whether the vector x i  satisfies the condensation criterion. In detail, it is determined whether the distance between the vector x i  and the vector x t  is smaller than a predetermined value θ. When the result of this determination is affirmative, the process proceeds to Step S 14 , and the vector x t  is condensed (combined) to the vector x i . As a result, the size of B t  does not increase, so that it does not change. 
         [0058]    A detailed example of the way of condensing (combining) will be described with reference to  FIG. 5 . Assuming a case where a condensed vector z 2  is generated by condensing the vector x 1  to x 2 , according to this condensation, the coefficients α 1  and α 2  of the decision function f(x 1 ) and f(x 2 ) of the SVM for the vectors x 1  and x 2  are changed to β 2 , and the parameters C 1  and C 2  are changed to D 2 . The condensed vector Z 2 , the coefficient β 2 , and the parameter D 2  can be obtained through the following formula. The vectors z 3  to Z n  which are not condensed are equal to x 3  to x n , β 3  to β n  are equal to α 3  to α n , and D 3  to D n  are equal to C 3  to C n . 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       z 
                       2 
                     
                     = 
                     
                       
                         
                           
                             C 
                             1 
                           
                            
                           
                             x 
                             1 
                           
                         
                         + 
                         
                           
                             C 
                             2 
                           
                            
                           
                             x 
                             2 
                           
                         
                       
                       
                         
                           C 
                           1 
                         
                         + 
                         
                           C 
                           2 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       β 
                       2 
                     
                     = 
                     
                       
                         
                           
                             α 
                             1 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 
                                   z 
                                   2 
                                 
                                 , 
                                 
                                   x 
                                   1 
                                 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             α 
                             2 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 
                                   z 
                                   2 
                                 
                                 , 
                                 
                                   x 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                       
                         K 
                          
                         
                           ( 
                           
                             
                               z 
                               2 
                             
                             , 
                             
                               z 
                               2 
                             
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       D 
                       2 
                     
                     = 
                     
                       
                         
                           
                             C 
                             1 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 
                                   z 
                                   2 
                                 
                                 , 
                                 
                                   x 
                                   1 
                                 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             C 
                             2 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 
                                   z 
                                   2 
                                 
                                 , 
                                 
                                   x 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                       
                         K 
                          
                         
                           ( 
                           
                             
                               z 
                               2 
                             
                             , 
                             
                               z 
                               2 
                             
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       z 
                       i 
                     
                     = 
                     
                       
                         x 
                         i 
                       
                        
                       
                         ( 
                         
                           
                             i 
                             = 
                             3 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           n 
                         
                         ) 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       β 
                       i 
                     
                     = 
                     
                       
                         α 
                         i 
                       
                        
                       
                         ( 
                         
                           
                             i 
                             = 
                             3 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           n 
                         
                         ) 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       D 
                       i 
                     
                     = 
                     
                       
                         C 
                         i 
                       
                        
                       
                         ( 
                         
                           
                             i 
                             = 
                             3 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           n 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                      
                     
                         
                     
                      
                     4 
                   
                   ] 
                 
               
             
           
         
       
     
         [0059]    The following formula is obtained by generalizing the condensation Formula 4: 
         [0000]    
       
         
           
             
               
                 
                   
                     z 
                     = 
                     
                       
                         
                           
                             C 
                             i 
                           
                            
                           
                             x 
                             i 
                           
                         
                         + 
                         
                           
                             C 
                             j 
                           
                            
                           
                             x 
                             j 
                           
                         
                       
                       
                         
                           C 
                           i 
                         
                         + 
                         
                           C 
                           j 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     β 
                     = 
                     
                       
                         
                           
                             α 
                             i 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 z 
                                 , 
                                 
                                   x 
                                   i 
                                 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             α 
                             j 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 z 
                                 , 
                                 
                                   x 
                                   j 
                                 
                               
                               ) 
                             
                           
                         
                       
                       
                         K 
                          
                         
                           ( 
                           
                             z 
                             , 
                             z 
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     D 
                     = 
                     
                       
                         
                           
                             C 
                             i 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 z 
                                 , 
                                 
                                   x 
                                   i 
                                 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             C 
                             j 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 z 
                                 , 
                                 
                                   x 
                                   j 
                                 
                               
                               ) 
                             
                           
                         
                       
                       
                         K 
                          
                         
                           ( 
                           
                             z 
                             , 
                             z 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                      
                     
                         
                     
                      
                     5 
                   
                   ] 
                 
               
             
           
         
       
     
         [0060]    When the result of Step S 13  is negative, the process proceeds to Step S 15 , and it is determined whether a non-support vector (SV) x j  exists in B t . When the result of this determination is affirmative, the process proceeds to Step S 16 , and the non-support vector x j  is removed from B t , and a new training vector x t  is added. As a result, the size of B t  does not increase, so that it does not change. On the other hand, when the result of the determination is negative, the process proceeds to Step S 17 , and a new training vector x t  is added to B t . As a result, B t  increases by the one new training vector x t . At Step S 18 , the working set B t+1  after being optimized is output. The working set B t+1  is fed back to the first and second stage WS selectors  3  and  4 . 
         [0061]    The outline of the above-described series of operations, that is, the operations of the first stage can be expressed as in  FIG. 6 . T in  FIG. 6  indicates the total number of training vectors, that is, T={(x i , y i )}, y 1 =±1, (i=1, 2, . . . , l). 
         [0062]    As is clearly understood from  FIG. 6 , in the first stage, the working set B t  is formed so as to gradually increase from a minimum value. In each optimization loop, one training vector is selected for updating B t , and a new SVM solution f t+1  is found. This new SVM solution is used in the next cycle for selecting one new training vector. 
         [0063]    The configuration of B t  which gradually increases enables the optimization algorithm to operate only on important training vectors. Therefore, the memory requirement for accumulating the kernel matrix is minimized, and the computation amount for computing the kernel matrix and optimization is minimized. 
         [0064]    Next, when even one of the following conditions (1) to (3) is satisfied, the operation of the first stage WS selector 3 is finished and shifted to the operation of the second stage WS selector  4 . 
         [0065]    (1) When the inactive vectors become empty, that is, “N t+1 ” of  FIG. 6  becomes zero. 
         [0066]    (2) When the size of the current working set B t  becomes larger than a predetermined value. 
         [0067]    (3) When all training vectors in the training data DB  1  are selected once or more by the first stage selector  3 . 
         [0068]    Next, operations of the second stage WS selector  4  will be described with reference to the flowchart of  FIG. 4 . 
         [0069]    At Step S 21 , one training vector x t  is selected from the training data DB  1 . At Step S 22 , the optimality of the training vector x t  is checked depending on whether the optimal training data x t  satisfies the condition of {y t −f t (x t )}&gt;0. When this condition is satisfied, the training vector x t  is output to the WS manager  5 . On the other hand, when the condition is not satisfied, the process returns to Step S 21  and the next one training vector x t  is selected. 
         [0070]    This operation of the second stage WS selector  4  finishes when all of the vectors which were not selected in the first stage are selected once or more, and checked once or more at Step  22 . 
         [0071]    As described above, the present embodiment adopts a two-stage method, and in the first stage, the best optimal training vector is selected among m training vectors sampled at Step S 1 . An object of this selection method is to obtain a satisfactory suboptimal SVM solution at a rational cost. 
         [0072]    In the second stage, all training data are tried one by one. Concerning a temporal SVM solution, training vectors satisfying the optimal conditions are selected for updating the working set B, and training vectors not satisfying the optimal conditions are discarded. An object of this stage is to discard unimportant training data by closely examining the SVM solution. 
         [0073]    Specifically, the first stage shows a method for obtaining a suboptimal solution at a high speed, and the second stage shows a method for improving a solution at a high speed on condition that the suboptimal solution exists. If the process is started from a state where no suboptimal solution is obtained as in the second stage from the beginning by skipping the first stage, reach to a proper solution is not guaranteed, and therefore, normally, performance of the model of the SVM obtained through learning deteriorates. As described above, the present invention can shorten the SVM training time. 
         [0074]    An example of results of an experiment conducted by the present inventor for confirming the effect of the present invention is shown in  FIG. 7 . The horizontal axis of the graph of  FIG. 7  indicates the number of training data. The highest three graphs show changes in the number of support vectors SVs when the optimization parameters (g, C, and θ) are changed as shown in the figure, the middle three graphs show changes in classification performance (test accuracy (%)), and the lowest three graphs show changes in training time (s). g of the parameters (g, C, and θ) is a parameter g when using a gamma kernel [K(x i , x j )=exp {−g·(x i −x j ) 2 }] as the kernel function K(x i , x j ) of Formula 1 given above. C is C of Formula 1, and θ is θ of Step S 13  of  FIG. 3 . 
         [0075]    From the highest graphs, it is understood that as the number of training data increases, the number of SV increases in the conventional method, however, the number of SV does not greatly increase in the method of the present invention. From the middle graphs, it is understood that the classification performance of the method of the present invention is substantially the same as in the conventional method although the number of SV does not greatly increase as described above. From the lowest graphs, it is understood that as the number of training data increases, the training time increases in the conventional method, however, the training time does not greatly increase in the method of the present invention.