Method and apparatus for optimizing support vector machine kernel parameters

• US 7,283,984 B1
• Filed: 02/01/2005
• Issued: 10/16/2007
• Est. Priority Date: 02/01/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Gross, Kenny C., Urmanov, Aleksey M., Thampy, Sajjit
• Primary Examiner(s): Knight; Anthony
• Assistant Examiner(s): Holmes; Michael B.
• Application Number:
  US11/049,146
• Time in Patent Office: 987 Days
• Field of Search: 706 45- 46
• US Class Current: 706/45
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

One embodiment of the present invention provides a system that optimizes support vector machine (SVM) kernel parameters. During operation, the system assigns sets of kernel parameter values to each node in a multiprocessor system. Next, the system performs a cross-validation operation at each node in the multiprocessor system based on a data set. This cross-validation operation computes an error cost value reflecting the number of misclassifications that arise while classifying the data set using the assigned set of kernel parameter values. The system then communicates the computed error cost values between nodes in the multiprocessor system, and eliminates nodes with relatively high error cost values. Next, the system performs a cross-over operation in which kernel parameter values are exchanged between remaining nodes to produce new sets of kernel parameter values. This process is repeated until a global winning set of kernel parameter values emerges.

Claims

1. A method for optimizing support vector machine (SVM) kernel parameters, comprising:

assigning sets of kernel parameter values to each node in a multiprocessor system;

performing a cross-validation operation at each node in the multiprocessor system based on a data set, wherein the cross-validation operation computes an error cost value reflecting the number of misclassifications that arise while classifying the data set using the assigned set of kernel parameter values;

communicating the computed error cost values between nodes in the multiprocessor system;

eliminating nodes with relatively high error cost values;

performing a cross-over operation in which kernel parameter values are exchanged between remaining nodes to produce new sets of kernel parameter values;

repeating the cross-validating, communicating eliminating, and cross-over operations until a global winning set of kernel parameter values is determined;

producing the global winning set of kernel parameters; and

using the kernel parameters in the kernel function of the SVM to map the data set from a low-dimensional input space to a higher-dimensional feature space.

2. The method of claim 1, wherein assigning sets of kernel parameter values involves assigning sets of random kernel parameter values from a valid range of kernel parameter values.

3. The method of claim 1, wherein assigning sets of kernel parameter values involves assigning sets of kernel parameter values associated with grid points that span a valid range of kernel parameter values.

4. The method of claim 1, wherein performing the cross-validation operation involves using a leave-out-one validation technique in which one vector is omitted during the training process and the omitted vector is subsequently tested against the trained kernel, and wherein the process is repeated for each vector in the data set.

5. The method of claim 1, wherein eliminating nodes with relatively high error cost values involves:

sorting nodes in the multiprocessor system based on associated error cost values; and

eliminating half of the nodes with the highest error cost values.

6. The method of claim 1,

wherein there are two kernel parameter values γ

and δ

; and

wherein performing the cross-over operation involves exchanging γ

values between remaining nodes.

7. The method of claim 1, wherein classifying the data set using the assigned kernel parameter values involves:

using the assigned set of kernel parameter values in a kernel function that maps the data set 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 data set with a given error cost.

8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for optimizing support vector machine (SVM) kernel parameters, the method comprising:

assigning sets of kernel parameter values to each node in a multiprocessor system;

performing a cross-validation operation at each node in the multiprocessor system based on a data set, wherein the cross-validation operation computes an error cost value reflecting the number of misclassifications that arise while classifying the data set using the assigned set of kernel parameter values;

communicating the computed error cost values between nodes in the multiprocessor system;

eliminating nodes with relatively high error cost values;

performing a cross-over operation in which kernel parameter values are exchanged between remaining nodes to produce new sets of kernel parameter values;

repeating the cross-validating, communicating, eliminating, and cross-over operations until a global winning set of kernel parameter values is determined;

producing the global winning set of kernel parameters; and

using the kernel parameters in the kernel function of the SVM to map the data set from a low-dimensional input space to a higher-dimensional feature space.

9. The computer-readable storage medium of claim 8, wherein assigning sets of kernel parameter values involves assigning sets of random kernel parameter values from a valid range of kernel parameter values.

10. The computer-readable storage medium of claim 8, wherein assigning sets of kernel parameter values involves assigning sets of kernel parameter values associated with grid points that span a valid range of kernel parameter values.

11. The computer-readable storage medium of claim 8, wherein performing the cross-validation operation involves using a leave-out-one validation technique in which one vector is omitted during the training process and the omitted vector is subsequently tested against the trained kernel, and wherein the process is repeated for each vector in the data set.

12. The computer-readable storage medium of claim 8, wherein eliminating nodes with relatively high error cost values involves:

sorting nodes in the multiprocessor system based on associated error cost values; and

eliminating half of the nodes with the highest error cost values.

13. The computer-readable storage medium of claim 8,

wherein there are two kernel parameter values γ

and δ

; and

wherein performing the cross-over operation involves exchanging γ

values between remaining nodes.

14. The computer-readable storage medium of claim 8, wherein classifying the data set using the assigned kernel parameter values involves:

using the assigned set of kernel parameter values in a kernel function that maps the data set 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 data set with a given error cost.

15. An apparatus that optimizes support vector machine (SVM) kernel parameters, comprising:

an assignment mechanism configured to assign sets of kernel parameter values to each node in a multiprocessor system;

a cross-validation mechanism configured to perform a cross-validation operation at each node in the multiprocessor system based on a data set, wherein the cross-validation mechanism computes an error cost value reflecting the number of misclassifications that arise while classifying the data set using the assigned set of kernel parameter values;

a communication mechanism configured to communicate the computed error cost values between nodes in the multiprocessor system;

an elimination mechanism configured to eliminate nodes with relatively high error cost values;

a cross-over mechanism configured to perform a cross-over operation in which kernel parameter values are exchanged between remaining nodes to produce new sets of kernel parameter values, wherein the apparatus continues iteratively producing, cross-validating and eliminating sets of kernel parameter values until a global winning set of kernel parameter values emerges;

a production mechanism configured to produce the global winning set of kernel parameters; and

a computation mechanism configured to use the kernel parameters in the kernel function of the SVM to map the data set from a low-dimensional input space to a higher-dimensional feature space.

16. The apparatus of claim 15, wherein the cross-validation mechanism is configured to use a leave-out-one validation technique in which one vector is omitted during the training process and the omitted vector is subsequently tested against the trained kernel, and wherein the process is repeated for each vector in the data set.

17. The apparatus of claim 15, wherein the cross-validation mechanism is configured to classify the data set using the assigned set of kernel parameter values by:

using the assigned set of kernel parameter values in a kernel function that maps the data set 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 data set with a given error cost.