Building support vector machines with reduced classifier complexity

• US 20070011110A1
• Filed: 05/10/2006
• Published: 01/11/2007
• Est. Priority Date: 05/12/2005
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Selvaraj, Sathiya, DeCoste, Dennis
• Granted Patent: US 7,630,945 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines

Abstract

Support vector machines (SVMs), though accurate, are not preferred in applications requiring great classification speed, due to the number of support vectors being large. To overcome this problem a primal system and method with the following properties has been devised: (1) it decouples the idea of basis functions from the concept of support vectors; (2) it greedily finds a set of kernel basis functions of a specified maximum size (d_max) to approximate the SVM primal cost function well; (3) it is efficient and roughly scales as O(nd_max²) where n is the number of training examples; and, (4) the number of basis functions it requires to achieve an accuracy close to the SVM accuracy is usually far less than the number of SVM support vectors.

Claims

1. A computerized method for learning for categorizing elements, comprising:

establishing an empty set of basis functions;

selecting a kernel basis function from a collection of training basis functions located at one or more training points;

adding the selected basis function to the set of basis functions;

optimizing one or more parameters associated with the set of basis functions; and

repeating the steps of selecting, adding and optimizing until a set limit of complexity in the number of basis functions is reached.

2. The method of claim 1, where in the step of optimizing comprises using a Newton optimization method to optimize the one or more parameters.

3. The method of claim 1, wherein the step of selecting comprises selecting a basis element randomly from the set of training elements.

4. The method of claim 1, wherein the step of selecting comprises selecting a basis function based on computing a score for the basis function, wherein, the score is taken as the achievable improvement in a support vector machine objective function.

5. The method of claim 1, comprising using a cache to store one or more kernel elements corresponding to the set of basis functions.

6. The method of claim 1, comprising excluding for selection basis functions from the collection of training basis functions that are estimated to not improve optimization.

7. The method of claim 1, further comprising determining hyperparameters for optimization.

8. A computerized system for learning for categorizing elements, comprising:

a computer processor;

a set of instructions executable on the processor for establishing an empty set of basis functions;

a set of instructions executable on the processor for selecting a kernel basis function from a collection of training basis functions located at the training points;

a set of instruction executable on the processor for adding the selected basis function to the set of basis functions;

a set of instructions executable on the processor for optimizing one or more parameters associated with the set of basis functions; and

a set of instructions executable on the processor for repeating the selecting, adding and optimizing until a set limit of complexity in the number of basis functions is reached.

9. The system of claim 8, wherein the set of instructions for optimizing comprises Newton optimization instructions to optimize the one or more parameters.

10. The system of claim 8, wherein the set of instructions for selecting comprises a set of instructions for selecting a basis element randomly from the set of training elements.

11. The system of claim 8, wherein the set of instructions for selecting comprises a set of instructions for selecting a basis function based on computing a score for the basis function, wherein, the score is taken as the achievable improvement in a support vector machine objective function.

12. The system of claim 8, further comprising a cache to store one or more kernel elements corresponding to the selected basis functions.

13. The system of claim 8, further comprising a set of instructions executable on the processor for excluding for selection basis functions from the collection of training basis functions that are estimated to not improve optimization.

14. The system of claim 8, further comprising a set of instructions executable on the processor for determining hyperparameters for optimization.