Pattern recognition system using support vectors

• US 5,649,068 A
• Filed: 05/16/1996
• Issued: 07/15/1997
• Est. Priority Date: 07/27/1993
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Boser, Bernard, Guyon, Isabelle, Vapnik, Vladimir
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/648,641
• Time in Patent Office: 425 Days
• Field of Search: 395/20-25, 395/27, 395/51, 395/61, 395/76, 382/155-159
• 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

A method is described wherein the dual representation mathematical principle is used for the design of decision systems. This principle permits some decision functions that are weighted sums of predefined functions to be represented as memory-based decision function. Using this principle a memory-based decision system with optimum margin is designed wherein weights and prototypes of training patterns of a memory-based decision function are determined such that the corresponding dual decision function satisfies the criterion of margin optimality.

Claims

1. A method of classifying at a computer system input patterns received from an input device, the method comprising the steps of:

a) determining a decision surface for classifying said input patterns, said determination of said decision surface being performed by i) deriving at said computer system a weighted sum of one or more selected associations of one of said input patterns with a training pattern from a predetermined set of training patterns contained in a storage device of said computer system, said one or more associations being selected such that said decision surface belongs to a subset with a smallest possible Vapnik-Chervonenkis dimension and ii) identifying at said computer system a number of adjustable parameters for said weighted sum, said adjustable parameters being identified such that said computer system can complete correct classification of said training patterns by performing a number of operations that is proportional to the number of adjustable parameters and the number of input patterns while leaving an optimal margin between said training patterns and said decision surface; and

b) classifying each input pattern into one of two classes depending on which side of said determined decision surface said each input pattern falls.

2. The method of claim 1 further comprising the steps of:

removing a selected subset of training patterns from the predetermined set of training patterns; and

repeating steps a) and b) of claim 1 a finite number of times.

3. The method of claim 2 further comprising the step of:

ranking the training patterns based on said adjustable parameters to determine which training patterns to remove.

4. The method of claim 1 further comprising the step of:

removing from the training patterns all training patterns for which said adjustable parameters are equal to zero.

5. The method of claim 1 further comprising the step of:

removing from the training patterns all training patterns for which the adjustable parameters fall below a given threshold.

6. A computer system for training a learning machine to classify input data received from an input device, said computer system comprising:

means for determining a decision surface by i) deriving at said computer system a weighted sum of one or more selected associations of one of said input patterns with a training pattern from a predetermined set of training patterns contained in a storage device of said computer system, said one or more associations being selected such that said decision surface belongs to a subset with a smallest possible Vapnik-Chervonenkis dimension and ii) identifying at said computer system adjustable parameters for said weighted sum, said adjustable weighting parameters being identified such that said computer system can complete correct classification of said training patterns by performing a number of operations that is proportional to the number of adjustable parameters and the number of input patterns while leaving an optimal margin between said training patterns and said decision surface; and

means for classifying each input pattern into one of two classes depending on which side of said determined decision surface said each input pattern falls.

7. The invention of claim 6 further comprising:

means for removing from the predetermined set of training patterns all patterns that are unused in the determination of the decision surface.

8. The invention of claim 7 further comprising:

means for further adjusting the adjustable parameters for the weighted sum in order to achieve better classification performance.

9. The invention of claim 6 wherein at least one of said associations is a kernel function which is selected from a group of kernel functions which includes a radial basis function, a high order polynomial function and an exponential function.

10. A method of classifying at a computer system input patterns received from an input device, the method comprising the steps of:

determining weights associated with said input patterns to derive vectors that are mapped into a high dimension feature space;

constructing an optimal hyperplane in said high dimension feature space to separate training patterns retrieved from said computer system, said separation being performed to ascertain particular locations of said training patterns with respect to said optimal hyperplane;

deriving adjustable parameters by identifying a number of specific training patterns which are substantially closest to a boundary of said optimal hyperplane, said number of specific training patterns being substantially equal to a Vapnik-Chervonenkis dimension for said optimal hyperplane; and

classifying said input patterns into one of two classes using said optimal hyperplane and said adjustable parameters.