Generalized sequential minimal optimization for SVM+ computations
View Patent ↗A system and method for support vector machine plus (SVM+) computations include selecting a set of indexes for a target function to create a quadratic function depending on a number of variables, and reducing the number of variables to two in the quadratic function using linear constraints. An extreme point is computed for the quadratic function in closed form. A two-dimensional set is defined where the indexes determine whether a data point is in the two-dimensional set or not. A determination is made of whether the extreme point belongs to the two-dimensional set. If the extreme point belongs to the two-dimensional set, the extreme point defines a maximum and defines a new set of parameters for a next iteration. Otherwise, the quadratic function is restricted on at least one boundary of the two-dimensional set to create a one-dimensional quadratic function. The steps are repeated until the maximum is determined.
1. A computer implemented method for training a support vector machine plus (SVM+) using sequential maximization, comprising:
selecting a working set of two indexes for a target function to create a quadratic function depending on a number of variables;
reducing the number of variables to two variables in the quadratic function using linear constraints;
computing an extreme point for the quadratic function in closed form;
defining a two-dimensional set where the indexes determine whether a data point is in the two-dimensional set or not;
determining whether the extreme point belongs to the two-dimensional set wherein:
if the extreme point belongs to the two-dimensional set, the extreme point defines a maximum and the extreme point defines a new set of parameters for a next iteration, and
otherwise, restricting the quadratic function on at least one boundary of the two-dimensional set to create a one-dimensional quadratic function; and
repeating the steps until the maximum is determined.
2. The method as recited in claim 1 , wherein selecting a working set of indexes includes selecting a pair of indexes and the number of variables is four.
3. The method as recited in claim 1 , wherein computing an extreme point for the quadratic function in closed form includes computing zero derivatives for each of the two variables.
4. The method as recited in claim 1 , wherein defining a two-dimensional set includes defining one of a rectangle and a triangle for the two-dimensional set.
5. The method as recited in claim 1 , wherein the new set of parameters include Lagrange multipliers which maximally violate optimality conditions.
6. The method as recited in claim 1 , wherein determining whether the extreme point belongs to the two-dimensional set further comprises:
determining whether the extreme point is within the two-dimensional set by analyzing boundaries of the two-dimensional set; and
selecting a maximum based upon a comparison of a result from each boundary.
7. The method as recited in claim 1 , wherein the maximum is employed as a determination of a maximum distance to a hyperplane.
8. A non-transitory computer readable medium comprising a computer readable program for training a support vector machine plus (SVM+) using sequential maximization, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:selecting a working set of indexes for a target function to create a quadratic function depending on a number of variables;
reducing the number of variables to two variables in the quadratic function using linear constraints;
computing an extreme point for the quadratic function in closed form;
defining a two-dimensional set where the indexes determine whether a data point is in the two-dimensional set or not;
determining whether the extreme point belongs to the two-dimensional set wherein:
if the extreme point belongs to the two-dimensional set, the extreme point defines a maximum and the extreme point defines a new set of parameters, otherwise, restricting the quadratic function on at least one boundary of the two-dimensional set to create a one-dimensional quadratic function, and repeating the steps of computing until the maximum is determined.
9. The non-transitory computer readable medium as recited in claim 8 , wherein selecting a working set of indexes includes electing a pair of indexes and the number of variable is four.
10. The non-transitory computer readable medium as recited in claim 8 , wherein computing an extreme point for the quadratic function in closed form includes computing zero derivatives for each of the two variables.
11. The non-transitory computer readable medium as recited in claim 8 , wherein defining a two-dimensional set includes defining one of a rectangle and a triangle for the two-dimensional set.
12. The non-transitory computer readable medium as recited in claim 8 , wherein the new set of parameters include Lagrange multipliers.
13. The non-transitory computer readable medium as recited in claim 8 , wherein determining whether the extreme point belongs to the two-dimensional set further comprises:
determining whether the extreme point is within the two-dimensional set by analyzing boundaries of the two-dimensional set; and
selecting a maximum based upon a comparison of a result from each boundary.
14. The non-transitory computer readable medium as recited in claim 8 , wherein the maximum is employed as a determination of a maximum distance to a hyperplane.