Optimizing subset selection to facilitate parallel training of support vector machines
View Patent ↗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.
1. A method for optimizing subset selection to facilitate parallel training of a support vector machine (SVM), comprising:
receiving a dataset comprised of data points;
evaluating the data points to produce a class separability measure;
using the class separability measure to partition the data points in the dataset into N subsets, wherein 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 );
wherein
J
=
tr
(
S
B
)
tr
(
S
W
)
;
using two or more processors in a multiprocessor system in parallel to perform separate SVM training computation for each subset in the N subsets to produce a different set of support vectors for each of the N subsets, wherein each subset contains a separate portion of data points of the entire dataset; and
performing a final SVM training computation using an agglomeration of different sets of support vectors computed for each of the N subsets to obtain a substantially optimal solution to the SVM training problem for the entire dataset.
2. The method of claim 1 , wherein after the training process is complete, the method further comprises using the SVM (including parameters produced during the training process and the dataset) to classify a second dataset.
3. The method of claim 2 , wherein 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; and
performing 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.
4. The method of claim 1 , wherein the number of traces between class scatter matrices, tr(S B ), is calculated as follows,
tr
(
S
B
Φ
)
=
∑
i
=
1
c
n
i
[
Sum
(
K
D
i
,
D
i
)
n
i
2
-
2
Sum
(
K
D
i
,
D
)
n
i
n
+
(
K
D
,
D
)
n
2
]
,
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.
5. The method of claim 1 , wherein the number of traces within class scatter matrices, tr(S W ), is calculated as follows,
tr
(
S
W
Φ
)
=
∑
i
=
1
c
∑
j
=
1
n
i
[
K
(
x
i
,
j
,
x
i
,
j
)
-
2
Sum
(
K
D
i
,
D
i
)
n
i
]
,
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.
6. The method of claim 1 , wherein 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.
7. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for optimizing subset selection to facilitate parallel training of a support vector machine (SVM), the method comprising:
receiving a dataset comprised of data points;
evaluating the data points to produce a class separability measure;
using the class separability measure to partition the data points in the dataset into N subsets, wherein 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 );
wherein
J
=
tr
(
S
B
)
tr
(
S
W
)
;
using two or more processors in a multiprocessor system in parallel to perform separate SVM training computation for each subset in the N subsets to produce a different set of support vectors for each of the N subsets wherein each subset contains a separate portion of data points of the entire dataset; and
performing a final SVM training computation using an agglomeration of different sets of support vectors computed for each of the N subsets to obtain a substantially optimal solution to the SVM training problem for the entire dataset.
8. The computer-readable storage medium of claim 7 , wherein after the training process is complete, the method further comprises using the SVM (including parameters produced during the training process and the dataset) to classify a second dataset.
9. The computer-readable storage medium of claim 8 , wherein 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; and
performing 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.
10. The computer-readable storage medium of claim 7 , wherein the number of traces between class scatter matrices, tr(S B ), is calculated as follows,
tr
(
S
B
Φ
)
=
∑
i
=
1
c
n
i
[
Sum
(
K
D
i
,
D
i
)
n
i
2
-
2
Sum
(
K
D
i
,
D
)
n
i
n
+
(
K
D
,
D
)
n
2
]
,
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.
11. The computer-readable storage medium of claim 7 , wherein the number of traces within class scatter matrices, tr(S W ), is calculated as follows,
tr
(
S
W
Φ
)
=
∑
i
=
1
c
∑
j
=
1
n
i
[
K
(
x
i
,
j
,
x
i
,
j
)
-
2
Sum
(
K
D
i
,
D
i
)
n
i
]
,
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.
12. The computer-readable storage medium of claim 7 , wherein 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.
13. An apparatus that optimizes subset selection to facilitate parallel training of a support vector machine (SVM), comprising:
a receiving mechanism configured to receive a dataset comprised of data points;
an evaluation mechanism configured to evaluate the data points to produce a class separability measure;
a partitioning mechanism configured to use the class separability measure to partition the data points in the dataset into N subsets, wherein 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
J
=
tr
(
S
B
)
tr
(
S
W
)
;
and
a training mechanism configured to use two or more processors in parallel to perform separate SVM training computation for each subset in the N subsets to produce a different set of support vectors for each of the N subsets wherein each subset contains a separate portion of data points of the entire dataset;
wherein the training mechanism is additionally configured to perform a final SVM training computation using an agglomeration of different sets of support vectors computed for each of the N subsets to obtain a substantially optimal solution to the SVM training problem for the entire dataset.
14. The apparatus of claim 13 , further comprising a classification mechanism, wherein after the training process is complete, the classification mechanism is configured to use the SVM (including parameters produced during the training process and the dataset) to classify a second dataset.
15. The apparatus of claim 14 , wherein while using the SVM to classify the second dataset, the classification mechanism is configured to:
use a kernel function to map the second dataset from a low-dimensional input space to a higher-dimensional feature space; and to
perform 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.
16. The apparatus of claim 13 , wherein the evaluation mechanism is configured to calculate the number of traces between class scatter matrices, tr(S B ), as follows,
tr
(
S
B
Φ
)
=
∑
i
=
1
c
n
i
[
Sum
(
K
D
i
,
D
i
)
n
i
2
-
2
Sum
(
K
D
i
,
D
)
n
i
n
+
(
K
D
,
D
)
n
2
]
,
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.
17. The apparatus of claim 13 , wherein the evaluation mechanism is configured to calculate the number of traces within class scatter matrices, tr(S W ), as follows,
tr
(
S
W
Φ
)
=
∑
i
=
1
c
∑
j
=
1
n
i
[
K
(
x
i
,
j
,
x
i
,
j
)
-
2
Sum
(
K
D
i
,
D
i
)
n
i
]
,
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.