Patent US6636243B1 successfully refreshed from Google Patents.
Patent US6327581B1 successfully refreshed from Google Patents.
US6327581B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for building a support vector machine classifier
Assignee: EBERLE EQUIPMENT COMPANY Inc
•
Filing: 1998-04-06
•
Granted: 2001-12-04
•
Expires: 2018-04-06
Abstract
Abstract Solving a quadratic programming problem involved in training support vector machines by sweeping through a set of training examples, solving small sub-problems of the quadratic programming problem. Each of these sub-problems has an analytic solution, which is faster that the numerical quadratic programming solutions used in the prior art. In one embodiment, training examples with non-optimal Lagrange multipliers are adjusted, one at a time, until all are optimal (e.g. until all examples fulfill the Kuhn-Tucker conditions). In another embodiment, training examples with non-optimal Lagrange multipliers are paired and then adjusted, until all are optimal.
Inventors
- 👤 John Carlton Platt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:52
CPC Classifications
G; G06; G06N; G06N20/00; G06F; G06F18/00; G06F18/20; G06F18/21; G06F18/214; G06F18/24; G06F18/241; G06F18/2411
Claims Analysis
Total Claims: 56
Claim 1
Independent Claim
210 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) where α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the method comprising steps of: a) initializing, with the machine, each of the Lagrange multipliers; b) sweeping through at least some of the training examples of the set of training examples; c) for each training example of the sweep, correcting, with the machine, a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal; d) storing, with the machine, the corrected Lagrange multiplier; and e) repeating steps (b), (c) and (d) if any Lagrange multiplier was changed during the sweep, thereby training the object classifier.
Claim 2
Independent Claim
210 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) where α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the method comprising steps of: a) initializing, with the machine, each of the Lagrange multipliers; b) sweeping through at least some of the training examples of the set of training examples; c) for each training example of the sweep, correcting, with the machine, a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal; d) storing, with the machine, the corrected Lagrange multiplier; and e) repeating steps (b), (c) and (d) if any Lagrange multiplier was changed during the sweep, thereby training the object classifier.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein the step of initializing each of the Lagrange multipliers sets each of the Lagrange multipliers to zero.
Claim 4
Dependent Claim
40 words
The method of claim 1 wherein the step of sweeping through at least some of the training examples of the set of training examples sweeps through all of the training examples of the set of training examples for each sweep.
Claim 5
Dependent Claim
57 words
The method of claim 1 wherein the step of sweeping through at least some of the training examples of the set of training examples sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the sweep, sweeps through a part of the training examples on a subsequent sweep.
Claim 6
Dependent Claim
90 words
The method of claim 1 further comprising a step of: accepting, with the machine, a cost parameter (C) for adjusting non-separable training examples, wherein, the step of sweeping through at least some of the training examples of the set of training examples sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the initial sweep, sweeps through non-boundary training examples on a subsequent sweep, wherein a non-boundary training example has an associated Lagrange multiplier greater than zero but less than C.
Claim 7
Dependent Claim
83 words
The method of claim 1 wherein the step of correcting a Lagrange multiplier associated with the training example, if the Lagrange multiplier is not optimal, includes sub-steps of: i) determining, with the machine, whether the Lagrange multiplier is optimal; ii) if the Lagrange multiplier is determined not to be optimal, determining, with the machine, a new Lagrange multiplier based on the Lagrange multiplier, an error, and the kernel function of the training example; and iii) limiting, with the machine, the new Lagrange multiplier.
Claim 8
Dependent Claim
28 words
The method of claim 6 wherein the sub-step of determining whether the Lagrange multiplier is optimal is performed by determining, with the machine, whether Kuhn-Tucker conditions are satisfied.
Claim 9
Dependent Claim
12 words
The method of claim 6 wherein the error is a Kuhn-Tucker error.
Claim 10
Dependent Claim
44 words
The method of claim 8 wherein the Kuhn-Tucker error is defined as (1−O n y n ), where O n is a classification output of the n th training example and y n is the predetermined classification associated with the n th training example.
Claim 11
Dependent Claim
49 words
The method of claim 8 wherein the new Lagrange multiplier associated with the n th training example (α n new ) is defined as: α n new = α n old + Kuhn - Tucker Error k ( x → n , x → n )
Claim 12
Dependent Claim
72 words
The method of claim 10 wherein the object classifier defines a hyperplane which separates objects in a class from objects not in the class, and wherein the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples w → · x → input - b where w is a weight vector.
Claim 13
Dependent Claim
48 words
The method of claim 11 wherein the sub-step of limiting the new Lagrange multiplier includes a step of setting, with the machine, the new Lagrange multiplier to zero if it is less than zero, and setting the new Lagrange multiplier to C if it is greater than C.
Claim 14
Dependent Claim
51 words
The method of claim 1 wherein the act of correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, is done without consideration of any training examples other than the training example associated with the Lagrange multiplier being corrected.
Claim 15
Dependent Claim
56 words
The method of claim 1 wherein the act of correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, corrects only the Lagrange multiplier associated with the training example only considering the Lagrange multiplier being corrected and information related to the associated training example.
Claim 16
Independent Claim
190 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) where α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the method comprising steps of: a) sweeping through at least some of the training examples of the set of training examples; and b) for each training example of the sweep, correcting, with the machine, only the Lagrange multiplier associated with the training example, using an analytic step, to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal; and c) storing, with the machine, the corrected Lagrange multiplier; thereby training the object classifier.
Claim 17
Independent Claim
190 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) where α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the method comprising steps of: a) sweeping through at least some of the training examples of the set of training examples; and b) for each training example of the sweep, correcting, with the machine, only the Lagrange multiplier associated with the training example, using an analytic step, to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal; and c) storing, with the machine, the corrected Lagrange multiplier; thereby training the object classifier.
Claim 18
Dependent Claim
51 words
The method of claim 15 wherein the act of correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, is done without consideration of any training examples other than the training example associated with the Lagrange multiplier being corrected.
Claim 19
Dependent Claim
56 words
The method of claim 15 wherein the act of correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, corrects only the Lagrange multiplier associated with the training example only considering the Lagrange multiplier being corrected and information related to the associated training example.
Claim 20
Independent Claim
171 words
An apparatus for training an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) where α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the apparatus comprising: a) a sweep controller for sweeping through at least some of the training examples of the set of training examples; and b) an optimizer for, for each training example of the sweep, correcting a Lagrange multiplier associated with the training example, using an analytic step, if the Lagrange multiplier is not optimal, thereby training the object classifier.
Claim 21
Independent Claim
171 words
An apparatus for training an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) where α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the apparatus comprising: a) a sweep controller for sweeping through at least some of the training examples of the set of training examples; and b) an optimizer for, for each training example of the sweep, correcting a Lagrange multiplier associated with the training example, using an analytic step, if the Lagrange multiplier is not optimal, thereby training the object classifier.
Claim 22
Dependent Claim
49 words
The apparatus of claim 18 wherein the optimizer for correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, does not consider any training examples other than the training example associated with the Lagrange multiplier being corrected.
Claim 23
Dependent Claim
56 words
The apparatus of claim 18 wherein the optimizer for correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, corrects only the Lagrange multiplier associated with the training example only considering the Lagrange multiplier being corrected and information related to the associated training example.
Claim 24
Dependent Claim
25 words
The apparatus of claim 18 wherein the sweep controller sweeps through all of the training examples of the set of training examples for each sweep.
Claim 25
Dependent Claim
43 words
The apparatus of claim 18 wherein the sweep controller sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the initial sweep, sweeps through a part of the training examples on a subsequent sweep.
Claim 26
Dependent Claim
71 words
The apparatus of claim 18 further comprising a user interface for accepting a cost parameter (C) for non-separable training examples, wherein, the sweep controller sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the initial sweep, sweeps through non-boundary training examples on a subsequent sweep, wherein a non-boundary training example has a Lagrange multiplier greater than zero but less than C.
Claim 27
Dependent Claim
53 words
The apparatus of claim 18 wherein the optimizer includes: i) means for determining whether the Lagrange multiplier is optimal; and ii) means, if the Lagrange multiplier is determined not to be optimal, for determining a new Lagrange multiplier based on the Lagrange multiplier, an error, and the kernal function of the training example.
Claim 28
Dependent Claim
49 words
The apparatus of claim 24 wherein the new Lagrange multiplier associated with the n th training example (α n new ) is defined as: α n new = α n old + Kuhn - Tucker Error k ( x → n , x → n )
Claim 29
Dependent Claim
18 words
The apparatus of claim 24 wherein the optimizer further includes: iii) means for limiting the new Lagrange multiplier.
Claim 30
Dependent Claim
41 words
The apparatus of claim 26 wherein the means for limiting the new Lagrange multiplier sets the new Lagrange multiplier to zero if it is less than zero, and sets the new Lagrange multiplier to C if it is greater than C.
Claim 31
Independent Claim
274 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) - b where α i is a Lagrange multiplier associated with the i th training example and b is a threshold, the method comprising steps of: a) initializing, with the machine, each of the Lagrange multipliers; b) sweeping through at least some of the training examples of the set of training examples; c) for each training example of the sweep, determining, with the machine, whether the Lagrange multiplier associated with the training example is optimal; d) if, in step (c), it is determined that the Lagrange multiplier is not optimal, then performing the steps of: i) selecting, with the machine, another training example from the set of training examples; ii) jointly optimizing, if possible, with the machine, the Lagrange multiplier associated with the training example and the Lagrange multiplier associated with the other training example; and iii) if joint optimization was not possible in step (d) (ii), repeating steps (d) (i) and (d) (ii); and e) repeating steps (b), (c), and (d) if any Lagrange multipliers were determined not to be optimal in step (c) during the sweep, thereby training the object classifier.
Claim 32
Independent Claim
274 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) - b where α i is a Lagrange multiplier associated with the i th training example and b is a threshold, the method comprising steps of: a) initializing, with the machine, each of the Lagrange multipliers; b) sweeping through at least some of the training examples of the set of training examples; c) for each training example of the sweep, determining, with the machine, whether the Lagrange multiplier associated with the training example is optimal; d) if, in step (c), it is determined that the Lagrange multiplier is not optimal, then performing the steps of: i) selecting, with the machine, another training example from the set of training examples; ii) jointly optimizing, if possible, with the machine, the Lagrange multiplier associated with the training example and the Lagrange multiplier associated with the other training example; and iii) if joint optimization was not possible in step (d) (ii), repeating steps (d) (i) and (d) (ii); and e) repeating steps (b), (c), and (d) if any Lagrange multipliers were determined not to be optimal in step (c) during the sweep, thereby training the object classifier.
Claim 33
Dependent Claim
26 words
The method of claim 28 wherein the step of initializing each of the Lagrange multipliers sets, with the machine, each of the Lagrange multipliers to zero.
Claim 34
Dependent Claim
40 words
The method of claim 28 wherein the step of sweeping through at least some of the training examples of the set of training examples sweeps through all of the training examples of the set of training examples for each sweep.
Claim 35
Dependent Claim
58 words
The method of claim 28 wherein the step of sweeping through at least some of the training examples of the set of training examples sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the initial sweep, sweeps through a part of the training examples on a subsequent sweep.
Claim 36
Dependent Claim
88 words
The method of claim 28 further comprising a step of: accepting, with the machine, a cost parameter (C) for non-separable training examples, wherein, the step of sweeping through at least some of the training examples of the set of training examples sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the initial sweep, sweeps through non-boundary training examples on a subsequent sweep, wherein a non-boundary training example has a Lagrange multiplier greater than zero but less than C.
Claim 37
Dependent Claim
130 words
The method of claim 28 further comprising a step of: accepting, with the machine, a cost parameter (C) for non-separable training examples, wherein the step of selecting another training example from the set of training examples comprises sub-steps of: (A) determining, with the machine, an error of the Lagrange multiplier associated with the training example; and (B) selecting, with the machine, the other training example by, in order of preference, 1) finding another training example having an associated Lagrange multiplier which is not equal to 0 or C, and which has an error most opposite the error determined in step (d)(i)(A), 2) finding another training example having an associated Lagrange multiplier which is not equal to 0 or C, and 3) finding another training example having an associated Lagrange multiplier.
Claim 38
Dependent Claim
22 words
The method of claim 33 wherein the error of an i th Lagrange multiplier is defined as (y i −O i ).
Claim 39
Dependent Claim
199 words
The method of claim 28 wherein the step of jointly optimizing the Lagrange multiplier (α 1 ) associated with the training example and the Lagrange multiplier (α 2 ) associated with the other training example includes sub-steps of: i) determining, with the machine, a new Lagrange multiplier (α 2 new ) associated with the other training example as: α 2 new = α 2 + y 1 y 2 KUHN - TUCKER ERROR 1 - KUHN - TUCKER ERROR 2 k ( x → 1 , x → 1 ) + k ( x → 2 , x → 2 ) - 2 k ( x → 1 , x → 2 ) where KUHN-TUCKER ERROR 1 is (1−O 1 y 1 ), and KUHN-TUCKER ERROR 2 is (1−O 2 y 2 ); ii) limiting, with the machine, the new Lagrange multiplier associated with the other training example to obtain (α 2 new,limited ); and ii) determining, with the machine, a new Lagrange multiplier (α 1 new ) associated with the training example as: α 1 new =α 1 +y 1 y 2 (α 2 −α 2 new,limited ).
Claim 40
Dependent Claim
141 words
The method of claim 35 wherein the sub-step of limiting the new Lagrange multiplier associated with the other training example includes steps of: A) if y 1 is the same sign as y 2 , determining, with the machine, an upper limit H as H=min ( C, α 1 +α 2 ) B) if y 1 is the not the same sign as y 2 , determining, with the machine, an upper limit H as: H=min ( C, C−α 1 +α 2 ) C) if y 1 is the same sign as y 2 , determining, with the machine, a lower limit L as L=max (0, α 1 +α 2 −C ) D) if y 1 is not the same sign as y 2 , determining, with the machine, a lower limit L as L=max (0, α 2 −α 1 ).
Claim 41
Dependent Claim
57 words
The method of claim 28 wherein the act of jointly optimizing, if possible, the Lagrange multiplier associated with the training example and the Lagrange multiplier associated with the other training example, if the Lagrange multiplier is not optimal, is done without consideration of any training examples other than the training example and the selected other training example.
Claim 42
Independent Claim
209 words
An apparatus for training an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) - b where α i is a Lagrange multiplier associated with the i th training example and b is a threshold, the apparatus comprising: a) a sweep controller for sweeping through at least some of the training examples of the set of training examples; b) a determination facility for, for each training example of the sweep, determining whether the Lagrange multiplier associated with the training example is optimal; c) a pairing facility for selecting another training example from the set of training examples if the determination facility determined that the Lagrange multiplier is not optimal; and d) an optimizer for jointly optimizing, if possible, the Lagrange multiplier associated with the training example and the Lagrange multiplier associated with the other training example.
Claim 43
Independent Claim
209 words
An apparatus for training an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples y i α i k ( x → i , x → input ) - b where α i is a Lagrange multiplier associated with the i th training example and b is a threshold, the apparatus comprising: a) a sweep controller for sweeping through at least some of the training examples of the set of training examples; b) a determination facility for, for each training example of the sweep, determining whether the Lagrange multiplier associated with the training example is optimal; c) a pairing facility for selecting another training example from the set of training examples if the determination facility determined that the Lagrange multiplier is not optimal; and d) an optimizer for jointly optimizing, if possible, the Lagrange multiplier associated with the training example and the Lagrange multiplier associated with the other training example.
Claim 44
Dependent Claim
25 words
The apparatus of claim 38 wherein the sweep controller sweeps through all of the training examples of the set of training examples for each sweep.
Claim 45
Dependent Claim
43 words
The apparatus of claim 38 wherein the sweep controller sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the initial sweep, sweeps through a part of the training examples on a subsequent sweep.
Claim 46
Dependent Claim
71 words
The apparatus of claim 38 further comprising a user interface for accepting a cost parameter (C) for non-separable training examples, wherein, the sweep controller sweeps through all of the training examples on an initial sweep, and if any Lagrange multipliers were changed during the initial sweep, sweeps through non-boundary training examples on a subsequent sweep, wherein a non-boundary training example has a Lagrange multiplier greater than zero but less than C.
Claim 47
Dependent Claim
106 words
The apparatus of claim 38 further comprising a user interface for accepting a cost parameter (C) for non-separable training examples, wherein the pairing facility: (A) determines an error of the Lagrange multiplier associated with the training example; and (B) selects the other training example by, in order of preference, 1) finding another training example having an associated Lagrange multiplier which is not equal to 0 or C, and which has an error most opposite the error determined, 2) finding another training example having an associated Lagrange multiplier which is not equal to 0 or C, and 3) finding another training example having an associated Lagrange multiplier.
Claim 48
Dependent Claim
22 words
The apparatus of claim 42 wherein the error of an i th Lagrange multiplier is defined as (y i −O i ).
Claim 49
Dependent Claim
187 words
The apparatus of claim 38 wherein the optimizer for jointly optimizing the Lagrange multiplier (α 1 ) associated with the training example and the Lagrange multiplier (α 2 ) associated with the other training example: i) determines a new Lagrange multiplier (α 2 new ) associated with the other training example as: α 2 new = α 2 + y 1 y 2 KUHN - TUCKER ERROR 1 - KUHN - TUCKER ERROR 2 k ( x → 1 , x → 1 ) + k ( x → 2 , x → 2 ) - 2 k ( x → 1 , x → 2 ) wherein KUHN-TUCKER ERROR 1 is (1−O 1 y 1 ), and KUHN-TUCKER ERROR 2 is (1−O 2 y 2 ); ii) limits the new Lagrange multiplier associated with the other training example to obtain (α 2 new,limited ); and ii) determines a new Lagrange multiplier (α 1 new ) associated with the training example as: α 1 new =α 1 +y 1 y 2 (α 2 −α 2 new,limited ).
Claim 50
Dependent Claim
140 words
The apparatus of claim 44 wherein the optimizer limits the new Lagrange multiplier associated with the other training example to an upper limit H and a lower limit L which are determined as follows: A) if y 1 is the same sign as y 2 , determining an upper limit H as H=min ( C, α 1 +α 2 ) B) if y 1 is the not the same sign as y 2 , determining an upper limit H as: H=min ( C, C−α 1 +α 2 ) C) if y 1 is the same sign as y 2 , determining a lower limit L as L=max (0, α 1 +α 2 −C ) D) if y 1 is not the same sign as y 2 , determining a lower limit L as L=max (0, α 2 −α 1 ).
Claim 51
Dependent Claim
55 words
The apparatus of claim 38 wherein the optimizer for jointly optimizing, if possible, the Lagrange multiplier associated with the training example and the Lagrange multiplier associated with the other training example, if the Lagrange multiplier is not optimal, does not consider any training examples other than the training example and the selected other training example.
Claim 52
Independent Claim
209 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 y i α i k ( x → i , x → input ) where i is an index to all non-zero Lagrange multipliers, α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the method comprising steps of: a) initializing, with the machine, each of the Lagrange multipliers; b) sweeping through at least some of the training examples of the set of training examples; c) for each training example of the sweep, correcting, with the machine, a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal; d) storing, with the machine, the corrected Lagrange multiplier; and e) repeating steps (b), (c) and (d) if any Lagrange multiplier was changed during the sweep, thereby training the object classifier.
Claim 53
Independent Claim
209 words
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (x i ) and predetermined classifications (y i ) associated with the each of the object training examples, where the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 y i α i k ( x → i , x → input ) where i is an index to all non-zero Lagrange multipliers, α i is a Lagrange multiplier associated with the i th training example, and k is a kernel function, the method comprising steps of: a) initializing, with the machine, each of the Lagrange multipliers; b) sweeping through at least some of the training examples of the set of training examples; c) for each training example of the sweep, correcting, with the machine, a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal; d) storing, with the machine, the corrected Lagrange multiplier; and e) repeating steps (b), (c) and (d) if any Lagrange multiplier was changed during the sweep, thereby training the object classifier.
Claim 54
Dependent Claim
72 words
The method of claim 47 wherein the object classifier defines a hyperplane which separates objects in a class from objects not in the class, and wherein the object classifier determines a classification output (O) of an object represented by feature vector (x input ) as: O = ∑ i = 1 number of training examples w → · x → input - b where w is a weight vector.
Claim 55
Dependent Claim
51 words
The method of claim 47 wherein the act of correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, is done without consideration of any training examples other than the training example associated with the Lagrange multiplier being corrected.
Claim 56
Dependent Claim
56 words
The method of claim 47 wherein the act of correcting a Lagrange multiplier associated with the training example to generate a corrected Lagrange multiplier, if the Lagrange multiplier is not optimal, corrects only the Lagrange multiplier associated with the training example only considering the Lagrange multiplier being corrected and information related to the associated training example.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-03 | 2005-06-04 | 2005-12-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-03 | 2009-06-04 | 2009-12-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-03 | 2013-06-04 | 2013-12-04 | $7700.00 | Window Closed / Lapsed |