Optimizing subset selection to facilitate parallel training of support vector machines

[0001] The present invention relates to computer-based classification techniques, which are used to identify members of groups of interest within datasets.

[0002] Classification and pattern recognition techniques have wide-reaching applications. A number of life science applications use classification techniques to identify members of groups of interest within clinical datasets. For example, an important life science application is concerned with the classification of the protein signatures of patients who have some type of cancer from those 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.

[0003] Conventional diagnosis 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.

[0004] 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.

[0005] 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.

[0006] However, the application of SVM'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 large datasets, which are not unusual in most life sciences problems, a quadratic optimization problem that arises during the training phase of the SVM's requires that one be able keep in the memory an N×N matrix, where N is the number of data vectors. This presents 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.

[0007] One embodiment of the present invention provides a system that optimizes subset selection to facilitate parallel training of a support vector machine (SVM). During operation, the system receives a dataset comprised of data points. Next, the system evaluates the data points to produce a class separability measure, and uses the class separability measure to partition the data points in the dataset into N batches. The system then performs SVM training computations on the N batches in parallel to produce support vectors for each of the N batches. Finally, the system performs a final SVM training computation using an agglomeration of support vectors computed for each of the N batches to obtain a substantially optimal solution to the SVM training problem for the entire dataset.

[0008] In a variation on this embodiment, after the training process is complete, the system uses the SVM (including parameters produced during the training process and the dataset) to classify a second dataset.

[0009] In a further variation, using the SVM to classify the second dataset involves using a kernel function to map the second dataset from a low-dimensional input space to a higher-dimensional feature space. The system then performs a quadratic optimization operation, which generates a substantially optimal decision surface in the feature space, wherein the decision surface classifies vectors in the second dataset.

[0010] In a variation on this embodiment, the class separability measure J represents the ratio of: traces between class scatter matrices tr(S_B); and traces within class scatter matrices tr(S_W), whereby

[0011] $J=\frac{\mathrm{tr}\left(S_R\right)}{\mathrm{tr}\left(S_W\right)}.$

[0012] In a further variation, the number of traces between class scatter matrices is calculated as,

[0013] $\mathrm{tr}\left(S_B^{\Phi }\right)=\sum _{i=1}^c{n}_i\left[\frac{\mathrm{Sum}\left(K_{D_i,D_i}\right)}{n_i^2}-2\frac{\mathrm{Sum}\left(K_{D_i,D}\right)}{n_{i}n}+\frac{\left(K_{D,D}\right)}{n^2}\right],$
wherein D represents the dataset, D_i represents batch i of D, K represents a kernel matrix, n is the size of the dataset D, and n_i is the size of batch i.

[0014] In a further variation, the number of within class scatter matrices, tr(S_W), is calculated as,

[0015] $\mathrm{tr}\left(S_W^{\Phi }\right)=\sum _{i=1}^c\sum _{j=1}^{n_j}\left[K\left(x_{i,j},x_{i,j}\right)-2\frac{\mathrm{Sum}\left(K_{D_i,D_i}\right)}{n_i}\right],$
wherein D represents the dataset, D_i represents batch i of D, K represents a kernel matrix, n is the size of the dataset D, and n_i is the size of batch i.

[0016] In a variation on this embodiment, the class separability measure J is correlated with a support vector yield (SVY), which is the ratio of: the number of: support vectors in a sub-problem solution that are in the solution of the original problem; and the number of support vectors in the solution of the original problem.

[0028] 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.

[0029] The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or 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), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as a LAN, a WAN, or the Internet.

Multiprocessor System

[0030] 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 optimizes subset selection to facilitate parallel training of the SVM. This parallel training process is described in more detail below.

[0031] 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.

[0032] 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.

[0033] 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

[0034] FIG. 2A and the flow chart in 2B illustrate how a support vector machine (SVM) operates on a dataset in accordance with an embodiment of the present invention. First, the system receives a dataset 202, for example containing protein signatures for patients who may have cancer (step 220). The system also receives kernel parameters, γ and δ 206 (step 222).

[0035] Next, the system passes dataset 202 through kernel 204 to produce a resulting kernel matrix 208 (step 224). This process maps dataset 202 from a low-dimensional input space to a higher-dimensional feature space.

[0036] The system then passes kernel matrix 208 through QP solver 210 (step 226), which performs a quadratic optimization operation to produce decision surface 214. Note that decision surface 214 can include a separating hyperplane, which separates members of different groups in feature space 212.

[0037] This process is typically performed sequentially on a single-processor machine. However, this single-processor mode of operation has become a limitation. In order to minimize the misclassification probabilities for the SVM, it becomes advantageous to use as many vectors as possible for training the SVM. However, the amount of memory used in representing the kernel matrix for n vectors increases as O(n²). This quickly consumes the resources on most commercially available machines, and becomes a bottleneck problem with large output spectra from recent, high-resolution mass spectrometers being used with Proteomics.

[0038] During the quadratic optimization step operation in step 226, the system attempts to find the optimal separating hyperplane (decision surface) in the feature space using Lagrange multipliers as described below,

[0039] $\begin{array}{cc}W\left(\alpha \right)=\sum _{i=1}^l{\alpha }_i-\frac{1}{2}\sum _{1,j=1}^l{\alpha }_i{\alpha }_j{y}_i{y}_{j}K\left(x_i,x_j\right)& \left(1\right)\end{array}$
under the constraints,

[0040] $\sum _{i=1}^l{\alpha }_i{y}_i=0,$
and,

[0041] 0≦α₁≦C, i=1, . . . , 1.

where, α_i are the Lagrange multipliers, y_iε−1,1, xεx₁, x₂, . . . , x₁, where “1” is the number of dimensions, and where K(x_i,x_j) is the kernel function. When the optimal set of α_i⁰ are found, any test vector x can be classified by evaluating,

[0042] $\mathrm{sgn}\sum _{i=1}^l{\alpha }_i^0{y}_{i}K\left(x_i,x\right)+b.$

[0043] The summation term in equation (1) is equivalent to a matrix multiplication step. For a matrix of size n, matrix multiplication has a complexity of O(n³), or at best (using Strassen's algorithm) O(n^log2(7)). This creates a problem for single-processor machines because it takes an unacceptably long period of time to arrive at a solution for large values of n.

[0044] SVMs typically outperform conventional classification techniques such as k-means, neural networks, naïve Bayes, and decision trees by displaying high sensitivity and specificity for categorization of test data. However, they continue to show minor false and missed alarms in their classification. It is desirable to minimize the false and missed alarm cases in the clinical trial qualification process, because misclassification in the patients leads to false/missed alarms for the drug discovery phase too, and thereby incurs further costs on the drug company to conduct extensive trials.

[0045] The accuracy of prediction is dependent on the choice of the kernel used in the training step. Most kernel functions have certain input parameters that need to be chosen. One embodiment of the present invention uses a polynomial kernel, which can be defined as follows,
K(x,y)=(γx·y+1)^δ

[0046] where x and y are input vectors. The kernel parameters γ and δ are ideally chosen so that the overall sensitivity of the SVM is optimized.

Parallel SVM Training Operation

[0047] The present invention provides an innovative technique, which contributes to the speedup, optimal memory utilization, and numerical stability for the solution of a broad class of computational problems important to the life sciences domain. The SVM training procedure (described in Vapnik, V. N., 2000, The Nature of Statistical Learning Theory, Springer-Verlag New York, Inc.) leads to a type of problem called a “quadratic optimization” problem. If the input dataset is large, the solution of the problem becomes intractable on the present generation of high end computer servers. In one embodiment of the present invention, the dataset is split into subsets and each subset is used to train a separate SVM. The result of this split-dataset approach for training is a set of support vectors for each of the separate, subset SVMs. The support vectors for each subset SVM problem are then put together to form a final data subset that is then used to train one final SVM. The solution of the final SVM is a very close approximation to the solution of the original problem. However, the overall compute cycles needed and the memory requirements are substantially smaller in the parallelized case using the optimal dataset partitioning approach described herein.

[0048] In general, the original dataset could be partitioned in numerous ways. However, if one does not partition the original dataset with care, the results obtained may not be as good as one would obtain by running the original data through one large SVM computation. One desirable feature of using SVM for classification applications is called “generalization.” A pattern recognition technique with poor generalization capability is not of much use. Poor generalization means that, after training, the pattern recognition module will only work with new datasets that contain data patterns that are very close to the patterns in the original training data; but the module may be unable to generalize its predictions to new datasets that contain new data patterns. By contrast, ideal classification algorithms have a capability to learn from a limited set of training data and then generalize the predictions to broader classes of data that were not seen in training. This is called good generalization capability. If one seeks to partition a large dataset into discrete subsets of training data for the purposes of optimizing the training time and memory utilization, the partitioning is ideally done judiciously in a manner that preserves the generalization capability for the SVM algorithm. The present invention is concerned with a novel partitioning method for selecting relevant data subsets in a manner that enables huge SVM problems to be solved in a reasonable solution time on present generations of servers while preserving the good generalization capability of the SVM algorithm.

[0049] We introduce here the notion of Support Vector Yield (SVY) to quantify the goodness of any given training data subset. The SVY is defined as the ratio of the number of those support vectors in the sub-problem solution that are in the set of support vectors of the original problem, to the number of vectors in the solution of the original problem.

[0050] $\begin{array}{cc}v=\frac{S\left(D\right)\bigcap S\left(d_i\right)}{S\left(D\right)}& \left(1\right)\end{array}$
where D is the original (full) dataset, d_i represents the i-th sub-problem's dataset (d_i is a subset of D), S(.) denotes the set of support vectors identified in the solution for given dataset, and ∥ denotes the number of elements in the set.

[0051] The higher the Support Vector Yield for a given d_i, the more information about the solution of the original problem this data subset can provide. In practice, it is difficult or impossible to estimate v because the solution of the original problem is not known. The obstacle is that it is impossible to find S(D) for the problems with roughly more than 10³ data points in a reasonable time on large servers.

[0052] To overcome this challenge our invention exploits the experimental observation that value of the Support Vector Yield is strongly correlated with a class separability measure (i.e., a quantitative measure of how well the SVM classification approach is able to successfully separate members of the distinct classes) in a high dimensional feature space. An important idea in this invention is to associate the goodness of a given partition subset d_i via numerical estimation of the class separability measure. The class separability measure can be evaluated as follows:

[0053] $\begin{array}{cc}J=\frac{\mathrm{tr}\left(S_B\right)}{\mathrm{tr}\left(S_W\right)}& \left(2\right)\end{array}$
J represents the ratio of traces of within class and between class scatter matrices which are calculated as follows,

[0054] $\begin{array}{cc}\mathrm{tr}\left(S_B^{\Phi }\right)=\sum _{i=1}^c{n}_i\left[\frac{\mathrm{Sum}\left(K_{D_i,D_i}\right)}{n_i^2}-2\frac{\mathrm{Sum}\left(K_{D_i,D}\right)}{n_{i}n}+\frac{\left(K_{D,D}\right)}{n^2}\right]& \left(3\right)\\ \mathrm{tr}\left(S_W^{\Phi }\right)=\sum _{i=1}^c\sum _{j=1}^{n_i}\left[K\left(x_{i,j},x_{i,j}\right)-2\frac{\mathrm{Sum}\left(K_{D_i,D_i}\right)}{n_i}\right]& \left(4\right)\end{array}$
wherein D represents the dataset, D_i represents batch i of D, K represents a kernel matrix, n is the size of the dataset D, and n_i is the size of batch i.

[0055] In fact, the quantities above are quite easy to compute. This approach to data vector partitioning can save an enormous amount of computation for solution of the overall problem. More importantly, this makes problems tractable on present generations of computer servers, and gives insight into the data stricture. All prior-art data-level decompositions of SVM training vectors use heuristic and non-quantifiable characteristics. By contrast, the approach taught herein employs deterministic quantitative method to optimize the data partitioning procedure.

[0056] Hence, in one embodiment of the present invention, the process of performing a parallel SVM training operation takes place as follows. First, the system receives a dataset comprised of data points (step 302). Next, the system evaluates the data points (as is described above) to produce a class separability measure (step 304).

[0057] Then, as described above, system then uses the class separability measure to partition data points in the data set into N batches (step 306).

[0058] Next, the system performs SVM training operations on the N batches in parallel on different processors of a parallel or distributed processing system, which produces support vectors for each of the N batches (step 308).

[0059] The system then performs a final SVM training computation using an agglomeration of support vectors computed for each of the N batches. This produces a substantially optimal solution for the SVM training problem for the entire data set (step 310).

[0060] After the training process is complete, the system can use the SVM (including parameters produced during the training process and the dataset) to classify another dataset (step 312).

[0061] To demonstrate the disclosed method, a large dataset was generated in such a manner that makes it a particularly vexing challenge for classification-type pattern recognition. See FIG. 4 where the objective is to find an optimal separation of the observations represented by “x”s from the observations represented by “diamonds” with minimal miss-identifications. As can be observed in FIG. 4, this is a challenging problem because of the “double horseshoe” relationship between the “x” and diamond observations. Note that naïve approaches that produce a straight line to separate the classes will result in numerous misidentifications.

[0062] FIG. 5 shows the SVM solution of the entire original problem (wide line separating the “x” and diamond classes). Visual inspection of the solution line in FIG. 5 illustrates why SVM is an excellent approach for classification type pattern recognition. The only problem with using SVM to solve a classification problem like this is the CPU time requirement and the memory requirement.

[0063] We now partition the original dataset into discrete batches using the Support Vector Yield approach outlined above. The solution of the first sub-problem is shown in FIG. 6. The separation obtained with just one “chunk” of the training data is clearly suboptimal. Nevertheless, we save the support vectors produced during this first pass to be combined with the support vectors from the other, subsequent batches.

[0064] If we repeat this process for a total of 12 distinct batches from 12 partitions of the original data, the resulting separation lines are shown in FIG. 7. Clearly, any one of these individual solutions is suboptimal. However, the remarkable feature of this optimal partitioning approach is that once we run a final SVM computation using an agglomeration of the support vectors from the 12 individual batches, we obtain the optimal solution (wide line) that is nearly identical to the original computation that included all the data together (see FIG. 8). The difference is that by using the new SVY partitioning approach taught herein we were able to reduce the memory requirement by 92%. Moreover, by parallelizing the batch runs, we were able to reduce the time required for this analysis by a factor of over 600.

[0065] The reason that we are able to achieve highly nonlinear speedup factors is because the computational burden for a SVM problem varies with the number of input vectors raised to the exponent of 2.8. This means that any level of parallelization can yield significant rewards in reducing the overall computational time. Moreover, on machines which are constrained on the total amount of physical memory available, if a problem exhausts the physical memory, the application starts swapping computations to disk. This swapping activity typically slows down the computations by a factor of 1000. Parallelization of the SVM computations helps a problem stay within the constraints of physical memory size and avoid this substantial latency penalty of swapping to disk.

[0066] Typical dependence of average Support Vector Yield on separability measure J is shown in FIG. 9. Basically, this curve says that the smaller the value of the criterion J, the higher the chances to obtain higher (better) Support Vector Yield. This in turn allows acceleration of the solution (1); or, if there is a fixed-time constraint, to increase the chances of finding an optimal solution for the primal problem (2) in the allotted amount of time.

[0067] Hardware components such as system boards, I/O boards, memory modules, and CPU's can be described as dynamical systems with inputs and outputs. If a disturbance is applied to one or more of the inputs, the response on the outputs can be observed. The dynamics of this Impulse/Response relationship can be captured for what we call a dynamical system characterization of the component, subsystem, or complete system under test.

[0068] A dataset of such dynamical Input/Output responses has been generated for a large group of signals associated with CPU's on the systems boards of a high-end server has been prepared. A disturbance has been generated by applying a step voltage change (this action is performed via the system controller's command “margin-voltage”.) Dynamic responses for this exercise are observed in the temperature signals associated with the CPU modules on the system boards.

[0069] The above dynamical system characterization sequence was applied to a large group of system boards containing known good boards (no faults), and known faulty system boards (containing one or more physical defects). This sequence of dynamics experiments was used to collect a database of Impulse/Response data and label the data as either Good or Faulty. Classification type pattern recognition was now applied to the dynamics signals in an effort to automate the diagnosis of good versus faulty system boards.

[0070] As we did in the first exemplary application above, the original classification problem was solved once using the entire database of dynamics signals, and then again by optimal partitioning into sup-problems as our disclosed method prescribes. The class separability measure for all subsets were computed and compared against the support vector yield, which is shown in FIG. 10. The curve indicates that the computable class separability measure very strongly related to the Support Vector Yield (SVY metric) and can be therefore be used as an estimate of the yield for the purpose of selecting optimal subsets in the decomposition of the original problem database.

[0071] These examples show that this approach is feasible and becomes the key when one confronts a typical life science domain problem where the sizes of datasets are 10⁴ and higher and dimensions can reach 10⁶ (for example, mass spectrometry\peptide data in cancer research). Thus, by estimating the J for various training subsets one can infer that the subsets with smallest values of J give out more support vectors. If J is large, the subset will not contribute many support vectors to the solution and it is not necessary to carry out optimization on this subset.

[0072] In summary, the technique described in this disclosure: (1) allows for solution of large classification problems by means of optimal margin classifiers; (2) maximizes the probability of finding the maximum number of support vectors of the original problem; and (3) gives deterministic, quantifiable criteria for training subset partitioning

[0073] 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.