Text classification by weighted proximal support vector machine

• US 20070239638A1
• Filed: 03/20/2006
• Published: 10/11/2007
• Est. Priority Date: 03/20/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhuang, Dong, Chen, Zheng, Zhang, Benyu, Wang, Jian, Zeng, Hua-Jun
• Granted Patent: US 7,707,129 B2
• Time in Patent Office: Days
• US Class Current: 706/20
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines

Abstract

Embodiments of the invention relate to improvements to the support vector machine (SVM) classification model. When text data is significantly unbalanced (i.e., positive and negative labeled data are in disproportion), the classification quality of standard SVM deteriorates. Embodiments of the invention are directed to a weighted proximal SVM (WPSVM) model that achieves substantially the same accuracy as the traditional SVM model while requiring significantly less computational time. A weighted proximal SVM (WPSVM) model in accordance with embodiments of the invention may include a weight for each training error and a method for estimating the weights, which automatically solves the unbalanced data problem. And, instead of solving the optimization problem via the KKT (Karush-Kuhn-Tucker) conditions and the Sherman-Morrison-Woodbury formula, embodiments of the invention use an iterative algorithm to solve an unconstrained optimization problem, which makes WPSVM suitable for classifying relatively high dimensional data.

Claims

1. A system for training a text classifier, the system comprising:

a text data preprocessor that preprocesses raw training text to produce an input matrix;

a weighting module that generates a weighted matrix by re-weighting the input matrix based on how many training examples are positive and how many training examples are negative; and

a model-vector generator that iteratively calculates a model vector based on the weighted matrix.

2. The system of claim 1, wherein the text data preprocessor uses a vector space model to represent the raw training text.

3. The system of claim 2, wherein the text data preprocessor uses the vector space model to represent labels that correspond to the raw training text.

4. The system of claim 1, wherein the iterative algorithm is a conjugate-gradient method for least squares systems algorithm.

5. A system for classifying text, the system comprising:

a text data preprocessor that preprocesses raw text to be classified to produce a vector representation of the text;

a model-vector reader that reads a model vector; and

a classifier that generates a classification result based on the vector representation of the text and based on the read model vector.

6. The system of claim 5, wherein the text data preprocessor uses a vector space model to represent the raw text to be classified.

7. The system of claim 6, wherein the classifier calculates an inner product of the vector representation of the text and the read model vector.

8. The system of claim 7, wherein the classification result is based on the calculated inner product.

9. The system of claim 8, wherein:

if the calculated inner product is greater than 0, the classification result is +1; and

if the calculated inner product is less than or equal to 0, the classification result is −

1.

10. A computer-readable medium containing computer-executable instructions for training a text classifier and classifying text by performing steps comprising:

representing input training text as a sparse matrix;

setting a plurality of classifier-training parameters;

iteratively solving a weighted proximal support vector machine equation; and

predicting respective classes for a plurality of test examples.

11. The computer-readable medium of claim 10, wherein the sparse matrix is an m by n sparse matrix X, where m is a number of training examples and n is a dimension of a training vector.

12. The computer-readable medium of claim 11, containing further computer-executable instruction for performing steps comprising:

using <

x_i,y_i>

to represent each training data sample, where x_i ε

Rⁿ,i=1,2, . . . ,m are training vectors and y_iΔ

{+1,−

1},i=1,2, . . . m are their corresponding class labels.

13. The computer-readable medium of claim 12, wherein setting the classifier-training parameters includes setting δ

₋

=1.

14. The computer-readable medium of claim 13, wherein setting the classifier-training parameters includes setting ratio=√

{square root over (N₋

|N₊)}, where N+ denotes a number of positive training examples and N−

denotes a number of negative training examples.

15. The computer-readable medium of claim 14, wherein setting the classifier-training parameters includes setting δ

₊=1+(ratio−

1)/2.

16. The computer-readable medium of claim 15, wherein setting the classifier-training parameters includes setting δ

_i=δ

₊ for positive training examples.

17. The computer-readable medium of claim 16, wherein setting the classifier-training parameters includes setting δ

_i=δ

₋

for negative training examples.

18. The computer-readable medium of claim 17, wherein setting the classifier-training parameters includes setting v=2*average(δ

_i∥

x_i∥

).

19. The computer-readable medium of claim 18, wherein iteratively solving the weighted proximal support vector machine equation includes:

letting A=[X,e], where each element in vector e is 1;

letting Δ

ε

R<sup>m×

m</sup> denote a diagonal matrix whose non-zero elements are Δ

_ii=δ

_i, and

solving (vI+(Δ

A)^T(Δ

A))β

=(Δ

A)^T(Δ

y) using a conjugate-gradient method for least squares systems algorithm.

20. The computer-readable medium of claim 19, wherein predicting the respective classes for the plurality of test examples includes predicting the class of test example x_i based on whether β

·

(x_i,1) is positive or negative.