Effective multi-class support vector machine classification

• US 7,533,076 B2
• Filed: 03/17/2008
• Issued: 05/12/2009
• Est. Priority Date: 12/06/2002
• Status: Expired due to Term

• Current Assignee: Tungsten Automation Corp.
• Original Assignee: Kofax Incorporated
• Inventors: Schmidtler, Mauritius A. R., Harris, Christopher K.
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US12/050,096
• Publication Number:
  US 20080183646A1
• Time in Patent Office: 421 Days
• Field of Search: 706/45, 706/12, 706/20, 706/59, 382/159, 382/184, 382/224
• US Class Current: 706/59
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines

Abstract

An improved method of classifying examples into multiple categories using a binary support vector machine (SVM) algorithm. In one preferred embodiment, the method includes the following steps: storing a plurality of user-defined categories in a memory of a computer, analyzing a plurality of training examples for each category so as to identify one or more features associated with each category; calculating at least one feature vector for each of the examples; transforming each of the at least one feature vectors so as reflect information about all of the training examples; and building a SVM classifier for each one of the plurality of categories, wherein the process of building a SVM classifier further includes: assigning each of the examples in a first category to a first class and all other examples belonging to other categories to a second class, wherein if anyone of the examples belongs to another category as well as the first category, such examples are assigned to the first class only, optimizing at least one tunable parameter of a SVM classifier for the first category, wherein the SVM classifier is trained using the first and second classes; and optimizing a function that converts the output of the binary SVM classifier into a probability of category membership.

Claims

1. In a computer-based system, a method of training a multi-category classifier using a binary SVM algorithm, said method comprising:

calculating at least one feature vector for each of a plurality of training examples;

transforming each of said at least one feature vectors using a first mathematical function so as to provide desired information about each of said training examples;

building a SVM classifier for each one of a plurality of categories,

calculating a solution for the SVM classifier for the first category using predetermined initial value(s) for said at least one tunable parameter; and

testing said solution for said first category to determine if the solution is characterized by either over-generalization or over-memorization,

wherein the SVM classifier is used on real world data, the probability of category membership of the real world data being output to at least one of a user, another system, and another process,

wherein whether said SVM classifier solution for said first category is characterized by either over-generalization or over-memorization is based on a difference between a harmonic mean of said first and second estimated probabilities, on the one hand, and an arithmetic mean of said first and second estimated probabilities, on the other hand.

2. The method of claim 1 further comprising determining whether said first category has more than a predetermined number of training examples assigned to it, wherein if the number of training examples assigned to said first category does not exceed said predetermined number, the process of building a SVM classifier for said first category is aborted.

3. The method of claim 1 further comprising testing whether the trained SVM classifier could be optimized, wherein if said SVM classifier could not be optimized, said SVM classifier for said first category is discarded.

4. The method of claim 1 wherein said at least one tunable parameter of said SVM classifier is optimized using a method comprising the steps of:

allocating a subset of the training examples assigned to said first category to a “

holdout”

set, wherein said subset of training examples are left out of said training step.

5. The method of claim 4 wherein said test to determine whether said SVM classifier solution for said first category is characterized by either over-generalization or over-memorization is based on a relationship between SVM classifier scores s and −

s produced by said SVM classifier, the first estimated probability and the second estimated probability having an SVM classifier score s, as provided by probability equations q(C|s) and 1.0−

q(C|−

s), respectively.

6. The method of claim 4 wherein said at least one tunable parameter comprises two tunable parameters for said SVM classifier, one for a positive class, and one for a negative class.

7. The method of claim 4 wherein said SVM classifier is based on a formulation having two cost factors (one for a positive class, one for a negative class), as follows:

$\min \left[\frac{1}{2}<br><br>\underset{i}{\sum <br><br>}<br><br>\underset{j}{\sum <br><br>}<br><br>{\mathrm{\alpha <br><br>}}_i<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>y_i<br><br>y_j<br><br>K<br><br>\left(x_i,x_j\right)-\underset{i}{\sum <br><br>}<br><br>{\mathrm{\alpha <br><br>}}_i\right]$

where;

α

_i is a Lagrange multiplier for example x_i,

$y_i=\{\begin{array}{c}+1,\mathrm{iff}<br><br><br><br>x_i<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{in}<br><br><br><br>\mathrm{the}<br><br><br><br>\mathrm{positive}<br><br><br><br>\mathrm{class}\\ -1,\mathrm{iff}<br><br><br><br>x_i<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{in}<br><br><br><br>\mathrm{the}<br><br><br><br>\mathrm{negative}<br><br><br><br>\mathrm{class},\end{array}$

Φ

(x) is a function that maps input vectors to feature vectors,

K(x_i, x_j)=Φ

_(xi)·

Φ

_(xj)

Subject to the constraints;

$0\le <br><br>{\mathrm{\alpha <br><br>}}_i\le <br><br>C_{+},\forall <br><br>\left\{i|y_i=+1\right\}$ $0\le <br><br>{\mathrm{\alpha <br><br>}}_i\le <br><br>C_{-},\forall <br><br>\left\{i|y_i=-1\right\}$ $\underset{i}{\sum <br><br>}<br><br>y_i<br><br>{\mathrm{\alpha <br><br>}}_i=0$

where C⁺ and C⁻

are the two user definable cost factors.

8. The method of claim 4 wherein said SVM classifier is based on a formulation having two cost factors (one for a positive class, one for a negative class), as follows:

$\min \left[1/2<br><br>{<br><br>w<br><br>}^2-\underset{i}{\sum <br><br>}<br><br>{\mathrm{\alpha <br><br>}}_i\right]$

where;

α

_i is a Lagrange multiplier for example x_i,

$y_i=\{\begin{array}{c}+1,\mathrm{iff}<br><br><br><br>x_i<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{in}<br><br><br><br>\mathrm{the}<br><br><br><br>\mathrm{positive}<br><br><br><br>\mathrm{class}\\ -1,\mathrm{iff}<br><br><br><br>x_i<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{in}<br><br><br><br>\mathrm{the}<br><br><br><br>\mathrm{negative}<br><br><br><br>\mathrm{class},\end{array}$

Φ

_(x) is a function that maps input vectors to feature vectors,

$w=\underset{i}{\sum <br><br>}<br><br>{\mathrm{\alpha <br><br>}}_i<br><br>y_i<br><br>\mathrm{\Phi <br><br>}<br><br>\left(x_i\right)$

subject to the constraints

$0\le <br><br>{\mathrm{\alpha <br><br>}}_i\le <br><br>C_{+},\forall <br><br>\left\{i|y_i=+1\right\}$ $0\le <br><br>{\mathrm{\alpha <br><br>}}_i\le <br><br>C_{-},\forall <br><br>\left\{i|y_i=-1\right\}$ $\underset{i}{\sum <br><br>}<br><br>y_i<br><br>{\mathrm{\alpha <br><br>}}_i=0$

where w is the weight vector perpendicular to the hyperplane, C⁺ and C⁻

are the two user definable cost factors.

9. The method of claim 1 wherein the following steps of the method are performed in the following order:

a) assigning each of said examples in a first category to a first class and all other examples belonging to other categories to a second class, wherein if any one of said examples belongs to both said first category and another category, such examples are assigned to the first class only;

b) optimizing at least one tunable parameter of a SVM classifier for said first categories, wherein said SVM classifier is trained using said first and second classes; and

c) optimizing a second mathematical function that converts the output of the binary SVM classifier into a probability of category membership.

10. The method of claim 1 wherein said SVM classifier for said first category calculates a score s for said first category, wherein said score is optimized to fit a slope parameter in a sigmoid function that transforms SVM scores to probability estimates.

11. The method of claim 1 wherein the calibration of SVM scores is performed without using unbound support vector training examples.

12. The method of claim 1, wherein the calibration of SVM scores is performed using training examples allocated to a holdout set.

13. The method of claim 1 wherein said training examples comprise documents containing text.

14. The method of claim 1 wherein said process of building a SVM classifier comprises:

assigning each of said examples in a first category to a first class and all other examples belonging to other categories to a second class;

optimizing at least one tunable parameter of a SVM classifier for said first categories, wherein said SVM classifier is trained using said first and second classes after the at least one tunable parameter has been optimized; and

optimizing a second mathematical function that converts the output of the binary SVM classifier into a probability of category membership

number of examples in said first category and dividing by the number of examples in all categories.

15. A computer-readable medium storing instructions that when executed by a computer cause the computer to perform the following steps:

calculating at least one feature vector for each of a plurality of training examples;

transforming each of said at least one feature vectors using a first mathematical function so as to provide desired information about each of said training examples; and

building a SVM classifier for each one of said plurality of categories,

calculating a solution for the SVM classifier for the first category using predetermined initial value(s) for said at least one tunable parameter; and

testing said solution for said first category to determine if the solution is characterized by either over-generalization or over-memorization,

wherein the SVM classifier is used on real world data, the probability of category membership of the real world data being output to at least one of a user, another system, and another process,

wherein whether said SVM classifier solution for said first category is characterized by either over-generalization or over-memorization is based on a difference between a harmonic mean of said first and second estimated probabilities, on the one hand, and an arithmetic mean of said first and second estimated probabilities, on the other hand.

16. The computer-readable medium of claim 15 wherein said process of building a SVM classifier comprises:

assigning each of said examples in a first category to a first class and all other examples belonging to other categories to a second class;

optimizing at least one tunable parameter of a SVM classifier for said first categories, wherein said SVM classifier is trained using said first and second classes after the at least one tunable parameter has been optimized; and

optimizing a second mathematical function that converts the output of the binary SVM classifier into a probability of category membership.