US5649068A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pattern recognition system using support vectors
Assignee: Nokia of America Corp
•
Filing: 1996-05-16
•
Granted: 1997-07-15
•
Expires: 2016-05-16
Abstract
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.
Inventors
- 👤 Bernard Boser
- 👤 Isabelle Guyon
- 👤 Vladimir Vapnik
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 07:42
CPC Classifications
G; G06; G06F; G06F18/00; G06F18/20; G06F18/24; G06F18/241; G06F18/2411
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
196 words
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.
Claim 2
Independent Claim
196 words
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.
Claim 3
Dependent Claim
38 words
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.
Claim 4
Dependent Claim
26 words
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.
Claim 5
Dependent Claim
27 words
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.
Claim 6
Dependent Claim
28 words
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.
Claim 7
Dependent Claim
183 words
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.
Claim 8
Dependent Claim
183 words
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.
Claim 9
Dependent Claim
29 words
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.
Claim 10
Dependent Claim
25 words
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.
Claim 11
Dependent Claim
40 words
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.
Claim 12
Independent Claim
134 words
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.
Claim 13
Independent Claim
134 words
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.
References Cited (Backward Citations)
US5293454A
Cited
US5067164A
Cited
US5299284A
Cited
US5384896A
Cited
US5263124A
Cited
US5440651A
Cited
US5276771A
Cited
US5371809A
Cited
US5371834A
Cited
US5384895A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-14 | 2001-01-13 | 2001-07-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-14 | 2005-01-13 | 2005-07-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-14 | 2009-01-13 | 2009-07-15 | $7700.00 | Window Closed / Lapsed |