Abstract:
One embodiment of the present invention provides a system that performs parallel grouping decomposition to facilitate expedited training of a support vector machine (SVM). During operation, the system receives a training dataset comprised of data vectors. The system then determines whether any data vector in the dataset violates conditions associated with a current SVM. Next, the system divides the violating data vectors into a number of subsets, thereby allowing parallel SVM training for each subset. The system subsequently builds an independent SVM for each subset in parallel based on the current SVM. The system then constructs a new SVM to replace the current SVM based on the SVMs built for each subset of violating data vectors.

Description:
BACKGROUND 
     The present invention relates to techniques for computer-based classification, which can be used to identify members of groups of interest within datasets. 
     Classification and pattern recognition techniques have wide-reaching applications. For example, a number of life science applications use classification techniques to identify members of groups of interest within clinical datasets. In particular, one important application involves distinguishing the protein signatures of patients with certain type of cancer from the protein signatures of patients who do not. This problem stems from the need in clinical trials to test the efficacy of a drug in curing cancer while the cancer is at an early stage. In order to do so, one needs to be able to identify patients who have cancer at an early stage. 
     Conventional diagnostic techniques are not sufficient for this application. A popular technique (from an area that has become known as “proteomics”) is to analyze mass spectra, which are produced by a mass spectrometer from serum samples of patients. Depending on the type of cancer, the mass spectra of serum samples can show distinct signatures, which are not immediately visible to the naked eye. Several existing data mining techniques are presently used to distinguish the cancer spectra from the normal ones, such as Naïve Bayes, Decision Trees, Principle-Components-Analysis based techniques, Neural Networks, etc. 
     However, these existing techniques are characterized by false-alarm and missed-alarm probabilities that are not sufficiently small. This is a problem because false alarms can cause patients to experience anxiety, and can cause them submit to unnecessary biopsies or other procedures, while missed alarms can result in progression of an undetected disease. 
     Support Vector Machines (SVMs) provide a new approach to pattern classification problems. SVM-based techniques are particularly attractive for the cancer classification problem because SVM-based techniques operate robustly for high-dimensional feature data, unlike other techniques which have resource requirements that are closely coupled with feature dimensions. 
     However, the application of SVM&#39;s in areas involving huge datasets, such as in proteomics, is constrained by extremely high computation cost, in terms of both the compute cycles needed as well as enormous physical memory requirements. 
     For example, a quadratic optimization problem arises during the training phase of the SVM&#39;s for large datasets, which are common in most life sciences problems. Such a quadratic optimization problem typically requires the memory to accommodate an N×N matrix, where N is the number of data vectors. This creates huge challenges for conventional high-end enterprise computer servers when the input datasets contain thousands or tens of thousands of data vectors. In addition, the training time for the algorithm grows in a manner that is polynomial in N. Current state-of-the-art research papers propose using heuristic, data-level decomposition approaches; but often these heuristic approaches are designed with little or no quantitative justification and suboptimal results. 
     SUMMARY 
     One embodiment of the present invention provides a system that performs parallel grouping decomposition to facilitate expedited training of a support vector machine (SVM). During operation, the system receives a training dataset comprised of data vectors. The system then determines whether any data vector in the dataset violates conditions associated with a current SVM. Next, the system divides the violating data vectors into a number of subsets, thereby allowing parallel SVM training for each subset. The system subsequently builds an independent SVM for each subset in parallel based on the current SVM. The system then constructs a new SVM to replace the current SVM based on the SVMs built for each subset of violating data vectors. 
     In a variation of this embodiment, if any data vector in the dataset violates conditions associated with the new SVM, the system iteratively performs the following operations until no data vector violates conditions associated with the SVM. The system first determines whether any data vector violates conditions associated with the current SVM. The system then divides the violating data vectors into subsets. Next, the system builds an independent SVM for each subset in parallel based on the current SVM. The system subsequently constructs a new SVM to replace the current SVM based on the SVMs built for each subset. 
     In a variation of this embodiment, the initial SVM contains either no support vectors, or a set of existing support vectors obtained based on prior knowledge of the dataset. 
     In a variation of this embodiment, building the independent SVM for each subset involves adding the support vectors for the current SVM to the subset, so that each subset contains violating data vectors and all the support vectors for the current SVM. 
     In a variation of this embodiment, building the independent SVM for each subset in parallel involves solving quadratic optimization problems for each subset in parallel, thereby reducing the total processing time. 
     In a variation of this embodiment, constructing the new SVM involves collecting support vectors for each SVM built for the subsets, removing duplicates from the collected support vectors, and forming the new SVM based on the collected support vectors. 
     In a variation of this embodiment, determining whether any vector in the dataset violates conditions associated with the SVM involves evaluating whether each data vector violates a set of Karush-Kuhn-Tucker (KKT) conditions for the current SVM. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         FIG. 1  illustrates a multiprocessor system in accordance with an embodiment of the present invention. 
         FIG. 2  illustrates the process of dividing violating data vectors into subsets in accordance with an embodiment of the present invention. 
         FIG. 3  illustrates presents a flow chart illustrating the process of parallel grouping decomposition in accordance with an embodiment of the present invention. 
         FIG. 4  illustrates a set of exemplary data vectors and a separating hyperplane in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
     The data structure and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device of medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices, such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs). 
     Multiprocessor System 
       FIG. 1  illustrates an exemplary multiprocessor system  100  in accordance with an embodiment of the present invention. Multiprocessor system  100  is a shared-memory multiprocessor system, which includes a number of processors  151 - 154  coupled to level one (L1) caches  161 - 164  which share a level two (L2) cache  180  and a memory  183 . Memory  183  contains SVM code that performs parallel grouping decomposition for fast training of large scale SVMs. This parallel grouping decomposition process is described in more detail below. 
     During operation, if a processor  151  accesses a data item that is not present in local L1 cache  161 , the system attempts to retrieve the data item from L2 cache  180 . If the data item is not present in L2 cache  180 , the system first retrieves the data item from memory  183  into L2 cache  180 , and then from L2 cache  180  into L1 cache  161 . 
     Multiprocessor system  100  also supports a coherency protocol that operates across bus  170 . This coherency protocol ensures that if one copy of a data item is modified in L1 cache  161 , other copies of the same data item in L1 caches  162 - 164 , in L2 cache  180  and in memory  183  are updated or invalidated to reflect the modification. 
     Although the present invention is described in the context of the shared-memory multiprocessor system  100 , the present invention is not meant to be limited to such a system. In general, the present invention can operate in any computer system or distributed system which contains multiple processors. For example, the present invention can operate in a distributed computing system in which separate computing systems are coupled together through a network. Hence, the term “multiprocessor system,” as used in this specification and the appended claims, refers to any computer system or distributed system containing multiple processors which can work together on a given computational task. 
     Support Vector Machine 
     One embodiment of the present invention provides unique advantages which enable training of large scale SVMs in reasonable time using limited resources and. This procedure reformulates the SVM training problem into a quadratic optimization problem (QP) with specific constraints on the variables. In this way, standard numerical solvers can be used to solve SVM training problems. The rest of this section explains the process of formulating an SVM training problem into a quadratic problem. 
     First, let X i  denote an m-dimensional vector, i.e., X i εR m . Vector X i  represents a data point in a data set, such as a snapshot of the physical telemetry signals of a computer server or a protein mass spectrum obtained from a mass spectrometer. In addition, let D denote a data set of n such data points:
         D={X i ,Y i }, i=1, . . . , n
 
where Y i ε{−1,+1} represents the presence (+1) or absence (−1) of the property or feature of interest for point X i . Data set D is generally called a training data set, because it is used to build an SVM.
       

     For example, X i  can be a sample of a blood mass spectrum. Each element of a vector data point represents an amplitude at a certain m/z value. A nonzero amplitude means that there is a peptide or a peptide fragment with such mass in the blood sample. Y i  represents the absence (−1) or presence (+1) of cancer in the patient. The goal is to build a classifier that uses X as an input and then correctly classifies the patient as having cancer or not having cancer. 
     To build an SVM for classification, the training data set D ideally includes examples from patients with and without cancer. Then, the classifier learns a differentiating feature in the data set which separates data points associated with cancer patients from those associated with non-cancer patients. 
     Given a training set D, an SVM is built by solving the following prime quadratic problem (QP 0 ): 
     (QP 0 ): min ∥W∥ 2 , subject to the following constraints: 
             {                   (       Φ   ⁡     (     X   i     )       ·   W     )     +   b     )     ≥     1   -     ξ   i                 for   ⁢           ⁢     Y   i       =     +   1                       (       Φ   ⁡     (     X   i     )       ·   W     )     +   b     )     ≤       -   1     +     ξ   i                 for   ⁢           ⁢     Y   i       =     -   1                     ξ   i     ≥   0     ,     ∀   i                                     
where Φ is a mapping function from R m  space to some Euclidean space H called feature space:
 
     Φ: R m →H. 
     Wherein WεH is a vector normal to the hyperplane that separates the points representing the two classes, b is an unknown scalar, and ξ i  is a set of positive slack variables representing the penalty of incorrect classification. The solution to the problem above defines an optimal separating hyperplane. 
     It is more convenient to solve a Lagrangian formulation of this problem: 
     
       
         
           
             
               
                 ( 
                 
                   QP 
                   1 
                 
                 ) 
               
               : 
               
                 
                   max 
                   ⁢ 
                   
                     
                       ∑ 
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       a 
                       i 
                     
                   
                 
                 - 
                 
                   0.5 
                   × 
                   
                     
                       ∑ 
                       
                         i 
                         , 
                         j 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         a 
                         i 
                       
                       ⁢ 
                       
                         a 
                         j 
                       
                       ⁢ 
                       
                         Y 
                         i 
                       
                       ⁢ 
                       
                         Y 
                         j 
                       
                       ⁢ 
                       
                         K 
                         ⁡ 
                         
                           ( 
                           
                             
                               X 
                               i 
                             
                             , 
                             
                               X 
                               j 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             , 
           
         
       
     
     subject to the following constraints: 
             {               0   ≤     a   i     ≤   C     ,     i   =   1     ,   …   ⁢           ,   n                   ∑   i     ⁢       a     i   ⁢               ⁢     Y   i         =   0                       
where a i  is a set of Lagrange multipliers corresponding to the inequality constraints in the prime problem QP 0 . Constant C represents the amount of penalty for incorrect classification, and K(·,·) is a kernel function. Examples of kernel functions include K(x,y)=x·y, K(x,y)=(x·y+1) p , K(x,y)=tan h(kx·y−δ).
 
     The optimal solution of problem QP 1 , denoted as a i *, ideally satisfies the following conditions, namely the Karush-Kuhn-Tucker (KKT) conditions, of the prime problem QP 0 : 
     
       
         
           
             { 
             
               
                 
                   
                     
                       
                         
                           
                             
                               Y 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     ∑ 
                                     j 
                                   
                                   ⁢ 
                                   
                                     
                                       a 
                                       j 
                                     
                                     ⁢ 
                                     
                                       Y 
                                       j 
                                     
                                     ⁢ 
                                     
                                       K 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             X 
                                             i 
                                           
                                           , 
                                           
                                             X 
                                             j 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 + 
                                 b 
                               
                               ) 
                             
                           
                           - 
                           1 
                         
                         ≥ 
                         0 
                       
                       ; 
                       
                         
                           for 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             a 
                             i 
                           
                         
                         = 
                         0 
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             
                               Y 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     ∑ 
                                     j 
                                   
                                   ⁢ 
                                   
                                     
                                       a 
                                       j 
                                     
                                     ⁢ 
                                     
                                       Y 
                                       j 
                                     
                                     ⁢ 
                                     
                                       K 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             X 
                                             i 
                                           
                                           , 
                                           
                                             X 
                                             j 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 + 
                                 b 
                               
                               ) 
                             
                           
                           - 
                           1 
                         
                         = 
                         0 
                       
                       ; 
                       
                         
                           for 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           0 
                         
                         &lt; 
                         
                           a 
                           i 
                         
                         &lt; 
                         C 
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             
                               
                                 Y 
                                 i 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     
                                       ∑ 
                                       j 
                                     
                                     ⁢ 
                                     
                                       
                                         a 
                                         j 
                                       
                                       ⁢ 
                                       
                                         Y 
                                         j 
                                       
                                       ⁢ 
                                       
                                         K 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             
                                               X 
                                               i 
                                             
                                             , 
                                             
                                               X 
                                               j 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                   
                                   + 
                                   b 
                                 
                                 ) 
                               
                             
                             - 
                             1 
                           
                           ≥ 
                           
                             ξ 
                             i 
                           
                         
                         ; 
                         
                           
                             for 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               a 
                               i 
                             
                           
                           = 
                           C 
                         
                       
                       , 
                       
                         
                           ξ 
                           i 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         is 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         a 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         positive 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         scalar 
                       
                     
                   
                 
               
                 
             
           
         
       
     
     Data points X i  for which there is a corresponding 0&lt;a i &lt;C are called support vectors and are denoted as  S X i . Only support vectors are used for computing the separating hyperplane or for making a classification decision. All other data points can be removed from the training data set with no impact on the classification results. 
     The dimension of QP 1  is n, which is the number of data points in the training set. When n is large (e.g., n=1,000 or more), the classical sequential QP solvers become very slow and sometimes cannot find a solution at all. To overcome this problem, one embodiment of the present invention provides an approach for parallel processing of the quadratic problem QP 1 , the solution of which produces the desired SVM. 
     Parallel Grouping Decomposition 
     One embodiment of the present invention uses a new technique called parallel grouping decomposition to perform SVM training in parallel. This approach allows solving arbitrarily large SVM problems using parallel processing. During operation, the system iteratively performs parallel grouping decomposition until a correct SVM is obtained. At the beginning of an iteration, the system first forms an initial support vector pool, S={ S X i , S Y i , i=1, . . . ,  S n}, based on prior knowledge about the problem, or based on the results from previous training procedures. (For example, the initial pool can be an empty set for a new problem.) Note that this pool serves as a starting point for adjusting the SVM to incorporate new information. When the training process is complete, this pool ideally contains the correct support vectors for the problem and the system accordingly exits the iteration. 
     Next, the system checks the KKT conditions for the prime quadratic problem QP 0  to determine if the current support vector pool S is the solution for the problem. If the KKT conditions are satisfied for each a i , then the original QP 0  has been solved and the current pool S contains the correct support vectors for the solution SVM. Otherwise, the system finds all a i &#39;s which violate the KKT conditions and forms a separate data set  V D of violating vectors:
           V   D ={ V X i , V Y i },i=1, . . . ,  V N
 
where  V N is the total number of violators.
       

     Note that the check of KKT conditions ideally is performed for all data vectors, because some of the vectors that violate the KKT conditions during a previous iteration may not be violators during the current iteration. Similarly, some of the data vectors that do not violate the KKT conditions during a previous iteration may violate the KKT conditions during the current iteration. 
     The system then divides the data set  V D into G groups (subsets) denoted as  V D g , where g=1, . . . , G. The system may do so randomly, so that there can be approximately equal proportions of positive and negative examples in each group. The number of groups, G, can be specified as an adjustable parameter. Alternatively, the size of each group can be specified and G is computed as G=[ V N/Group_Size]. 
     The system subsequently adds to each subset  V D g  the current support vectors, so that each subset contains a portion of KKT-violating data vectors and all of the support vectors contained in S: 
       V D g ={ V X i   g , V Y i   g , S X j , S Y j } i=1, . . . ,  V N g , j=1, . . . ,  S n. 
     The system then builds G independent SVMs for each subset in parallel. The system may use any available quadratic solver to solve these smaller quadratic problems. Because these quadratic problems are independent, all the necessary computations can be performed in parallel very efficiently. 
     After obtaining G SVMs for the G subsets, the system collects the support vectors from each of these SVMs and forms a new support vector pool S using these support vectors. Furthermore, the system removes any duplicate support vectors from the support vector pool S. The system then goes back to the beginning of the iteration to determine whether the SVM based on the current S is the correct solution. If so, the system exits. Otherwise, the system repeats the parallel-grouping decomposition again. 
     Typically, the number of data vector that violate the KKT conditions decreases with each iteration, although this may not always be the case. For practical purposes, the number of violators drops significantly with each iteration and only a few iterations are required to reach the final solution of the original problem. In essence, the parallel grouping decomposition approach divides large data sets into smaller, manageable subsets and finds the exact solution of the original QP problem iteratively while processing all subsets in parallel. 
       FIG. 2  illustrates the process of dividing violating data vectors into subsets in accordance with an embodiment of the present invention. In this example, a set of violating data vectors  201  is divided into two subsets, namely subset  204  and subset  206 . Each subset contains approximately equal number of positive and negative examples (represented by grey squares and blank squares, respectively). The system then adds to each subset the current support vector pool. The current support vectors are represented in grey circles (positive examples) and blank circles (negative examples). 
     The system then builds an SVM for each subset, and collects the support vectors corresponding to each subset to form a new support vector pool. Next, the systembuilds a new SVM  208  based on the new support vectors. The system subsequently determines whether all the data vectors satisfy the KKT conditions for the problem. If so, the SVM training is complete and the system exits. Otherwise, the system repeats the parallel grouping decomposition process until it finds a correct SVM. 
       FIG. 3  illustrates presents a flow chart illustrating the process of parallel grouping decomposition in accordance with an embodiment of the present invention. During operation, the system starts by receiving a data set (step  302 ). The system then determines whether all data vectors satisfy KKT conditions for the current SVM (step  304 ). If so, the problem is solved and the system exits. Otherwise, the system divides the violating data vectors into a number of subsets (step  306 ). In addition, the system adds to each subset the current pool of support vectors (step  308 ). 
     Next, the system builds an independent SVM for each subset in parallel (step  310 ). After obtaining SVMs for the subsets, the system collects the support vectors from each subset and removes the duplicates (step  312 ). The system subsequently constructs a new SVM using the collected support vectors (step  314 ). The system then determines again whether all the data vectors satisfy the KKT conditions for the current SVM (step  304 ). 
       FIG. 4  illustrates a set of exemplary data vectors and a separating hyperplane in accordance with an embodiment of the present invention. In this example, the objective is to find an optimal separation of one set of observations (represented by dark squares) from another set of observations (represented by grey circles). As can be observed in  FIG. 4 , this is a challenging problem because there is a “double horseshoe” relationship between the two sets of observations. It is obvious that naïve approaches which produce a linear line or linear plane to separate these two classes will result in numerous misidentifications. 
     Using the present parallel grouping decomposition approach, a system can easily solve this problem. In one exemplary experiment, the original data set is partitioned into 24 groups during the first iteration. After the first iteration, only a few vectors violate the KKT conditions. Therefore, the second iteration includes only one grup of violators combined with the support vectors obtained during the first iteration. After the second iteration, all the data vectors satisfy the KKT conditions and the original problem is solved in a total of 0.13 time units. By contrast, the same problem is solved by a state-of-art conventional SVM training system in a total of 0.51 time units. 
     The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.