Method and apparatus for improving the efficiency of support vector machines

• US 6,134,344 A
• Filed: 06/26/1997
• Issued: 10/17/2000
• Est. Priority Date: 06/26/1997
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Burges, Christopher John
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US08/883,193
• Time in Patent Office: 1,209 Days
• Field of Search: 382/155, 382/156, 382/157, 382/158, 382/159, 382/160, 382/161, 382/253, 382/225
• US Class Current: 382/155
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines

Abstract

A method and apparatus is described for improving the efficiency of any machine that uses an algorithm that maps to a higher dimensional space in which a given set of vectors is used in a test phase. In particular, reduced set vectors are used. These reduced set vectors are different from the vectors in the set and are determined pursuant to an optimization approach other than the eigenvalue computation used for homogeneous quadratic kernels. An illustrative embodiment is described in the context of a support vector machine (SVM).

Claims

1. A method for using a support vector machine, the method comprising the steps of:

receiving input data signals; and

using the support vector machine operable on the input data signals for providing an output signal, wherein the support vector machine utilizes reduced set vectors, wherein the reduced set vectors were a priori determined during a training phase using an unconstrained optimization approach other than an eigenvalue computation used for homogeneous quadratic kernels wherein the training phase further comprises the steps of;

receiving elements of a training set;

generating a set of support vectors, the number of support vectors being NS;

selecting a number m of reduced set vectors, where m≦

NS; and

generating the number m of reduced set vectors using the unconstrained optimization approach.

2. The method of claim 1 wherein the input data signals represent different patterns and the output signal represents a classification of the different patterns.

3. A method for using a support vector machine, the method comprising the steps of:

receiving input data signals; and

using the support vector machine operable on the input data signals for providing an output signal, wherein the support vector machine utilizes reduced set vectors, wherein the reduced set vectors were a priori determined during a training phase using an unconstrained optimization approach other than an eigenvalue computation used for homogeneous quadratic kernels wherein the training phase further comprises the steps of;

training the support vector machine for determining a number, NS, of support vectors; and

using the unconstrained optimization technique to determine the reduced set vectors, where a number of reduced set vectors is m, where m≦

NS.