Methods and apparatus for building a support vector machine classifier
AssigneeMicrosoft Corporation
InventorJohn Carlton Platt
Life of this patent
Estimating the term…
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.
Claims50
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (xi) and predetermined classifications (yi) 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 (xinput) 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 ith 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.
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (xi) and predetermined classifications (yi) 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 (xinput) 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 ith 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.
An apparatus for training an object classifier based on a set of object training examples represented by feature vectors (xi) and predetermined classifications (yi) 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 (xinput) 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 ith 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.
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (xi) and predetermined classifications (yi) 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 (xinput) 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 ith 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.
An apparatus for training an object classifier based on a set of object training examples represented by feature vectors (xi) and predetermined classifications (yi) 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 (xinput) 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 ith 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.
A method for operating a machine to train an object classifier based on a set of object training examples represented by feature vectors (xi) and predetermined classifications (yi) 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 (xinput) 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 ith 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.
Dependencies are inferred from the claim text.