Multiclass classification of points
View Patent ↗A method includes obtaining, by executing a module stored on a non-transitory computer-readable storage device, approximately-zero polynomials for each of multiple classes. The method further includes evaluating the approximately-zero polynomials for each class on a plurality of points to compute distances from each point to each of the classes. The method also includes scaling the approximately-zero polynomials based on the distances and classifying the points based on the scaled approximately-zero polynomials.
1. A method, comprising:
obtaining, by executing a module stored on a non-transitory computer-readable storage device, approximately-zero polynomials for each of multiple classes;
evaluating the approximately-zero polynomials for each class on a plurality of points to compute distances from each point to each of the classes;
scaling the approximately-zero polynomials based on the distances; and
classifying the points based on the scaled approximately-zero polynomials.
2. The method of claim 1 further comprising:
setting a threshold to be used to obtain the approximately-zero polynomials;
determining whether the classification of the points is satisfactory; and
based on the classification of the points not being satisfactory, adjusting the threshold and repeating the obtaining the approximately-zero polynomials using the adjusted threshold as well as evaluating the approximately-zero polynomials, scaling the approximately-zero polynomials, and classifying the points.
3. The method of claim 1 wherein obtaining the approximately-zero polynomials comprises:
generating a projection set of polynomials by computing a projection of a space linear combination of candidate polynomials of degree d on polynomials of degree less than d that do not evaluate to less than a threshold on a set of points;
subtracting the projection set of polynomials evaluated on the points from the candidate polynomials evaluated on the points to generate a subtraction matrix of evaluated polynomials;
computing the singular value decomposition of the subtraction matrix of evaluated polynomials; and
partitioning the polynomials resulting from the singular value decomposition based on a threshold.
4. The method of claim 1 wherein scaling the approximately-zero polynomials comprises determining a vector of ratios of distances for each class, at least one of the ratios including a ratio of a distance to a class from a first point associated with that class to a distance to another class from the first point.
5. The method of claim 4 wherein at least one other ratio includes a ratio of the distance to a class not associated with the first point to a distance to the class for which the first point is associated.
6. The method of claim 5 further comprising sorting the entries in each vector according to the ratios.
7. The method of claim 5 further comprising, for each vector, determining a boundary point and computing the nth root of a product of boundary values associated with the boundary point to generate a scaling factor for the corresponding vector.
8. The method of claim 7 further comprising scaling the approximately-zero polynomials by the scaling factors.
9. The method of claim 7 wherein the nth root is the fourth root.
10. A non-transitory, computer-readable storage device containing software than, when executed by a processor, causes the processor to:
obtain approximately-zero polynomials for each of multiple classes;
evaluate the approximately-zero polynomials for each class on a plurality of points to compute distances from each point to each of the classes;
iteratively determine scaling factors for the multiple classes based on ratios of distances from the points to the classes;
scale the approximately-zero polynomials based on the scaling factors; and
classify the points based on the scaled approximately-zero polynomials.
11. The non-transitory, computer-readable storage device of claim 10 wherein the software causes the processor to obtain the approximately-zero polynomials for each of multiple classes by causing the processor to:
generate a projection set of polynomials by computing a projection of a space linear combination of candidate polynomials of degree d on polynomials of degree less than d that do not evaluate to less than a threshold on a set of points;
subtract the projection set of polynomials evaluated on the points from the candidate polynomials evaluated on the points to generate a subtraction matrix of evaluated polynomials;
compute the singular value decomposition of the subtraction matrix of evaluated polynomials; and
partition the polynomials resulting from the singular value decomposition based on a threshold.
12. The non-transitory, computer-readable storage device of claim 10 wherein the software causes the processor to:
set a threshold to be used to obtain the approximately-zero polynomials;
determine whether the classification of the points is satisfactory; and
based on the classification of the points not being satisfactory, adjust the threshold and again obtain the approximately-zero polynomials using the adjusted threshold as well as evaluate the approximately-zero polynomials, scale the approximately-zero polynomials, and classify the points.
13. The non-transitory, computer-readable storage device of claim 10 wherein the software causes the processor to scale the approximately-zero polynomials by causing the processor to determine a vector of ratios of distances for each class, at least one of the ratios including a ratio of a distance to a class from a first point associated with that class to a distance to another class from the first point.
14. The non-transitory, computer-readable storage device of claim 13 wherein at least one other ratio includes a ratio of the distance to a class not associated with the first point to a distance to the class for which the first point is associated.
15. The non-transitory, computer-readable storage device of claim 14 wherein the software causes the processor to sort the entries in each vector according to the ratios.
16. The non-transitory, computer-readable storage device of claim 14 wherein, for each vector, the software causes the processor to determine a boundary point and compute the nth root of a product of boundary values associated with the boundary point to generate a scaling factor for the corresponding vector.
17. The non-transitory, computer-readable storage device of claim 16 wherein the software causes the processor to scale the approximately-zero polynomials by the scaling factors.
18. A system, comprising:
a stable approximately vanishing ideal engine to generate approximately-zero polynomials for each of multiple classes; and
a classification engine to classify points into the multiple classes based on distances computed using the generated approximately-zero polynomials.
19. The system of claim 18 wherein the classification engine is to scale the approximately-zero polynomials in an iterative process based on ratios of the distances.
20. The system of claim 19 wherein the classification engine is to scale the approximately-zero polynomials based on a computation of a nth root of a product of a pair of ratios of the distances.