Method and Apparatus for Transductive Support Vector Machines

• US 20070265991A1
• Filed: 03/21/2007
• Published: 11/15/2007
• Est. Priority Date: 05/15/2006
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Weston, Jason, Bottou, Leon, Collobert, Ronan
• Granted Patent: US 7,778,949 B2
• Time in Patent Office: Days
• US Class Current: 706/16
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier

Abstract

Disclosed is a method for training a transductive support vector machine. The support vector machine is trained based on labeled training data and unlabeled test data. A non-convex objective function which optimizes a hyperplane classifier for classifying the unlabeled test data is decomposed into a convex function and a concave function. A local approximation of the concave function at a hyperplane is calculated, and the approximation of the concave function is combined with the convex function such that the result is a convex problem. The convex problem is then solved to determine an updated hyperplane. This method is performed iteratively until the solution converges.

Claims

1. A method for training a transductive support vector machine based on an objective function, the objective function based on a set of labeled training data classified into first and second classes and a set of unlabeled test data, comprising:

decomposing the objective function into a sum of a concave function and a convex function; and

determining a hyperplane classifier classifying the unlabeled data into the first and second classes by iteratively approximating the concave and convex functions.

2. The method of claim 1, wherein said step of determining a hyperplane classifier comprises:

(a) determining an initial hyperplane classifier;

(b) calculating a local approximation of the concave function at the initial hyperplane classifier;

(c) solving a convex problem formed by combining the local approximation to the concave function with the convex function;

(d) determining an updated hyperplane classifier based on the solution to the convex problem;

(e) calculating a local approximation of the concave function at the updated hyperplane classifier; and

(f) repeating steps (c)-(e) until the local approximation of the concave function at the updated hyperplane classifier converges.

3. The method of claim 2, wherein step (a) comprises:

determining the initial hyperplane classifier using a support vector machine based on the labeled data.

4. The method of claim 2, wherein each of steps (b) and (e) comprises:

calculating a tangent of the concave function at a hyperplane classifier.

5. The method of claim 2, wherein said step of determining a hyperplane classifier further comprises:

(g) enforcing a balancing constraint for balancing a ratio of the unlabeled data classified into the first and second classes and a ratio of the labeled data classified into the first and second classes.

6. The method of claim 1, wherein the objective function is based on a non-convex loss function for the unlabeled data, and said step of decomposing the objective function comprises:

decomposing the loss function for the unlabeled data into a convex Hinge loss function and a concave Hinge loss function.

7. The method of claim 6, wherein said loss function for the unlabeled data comprises a Symmetric Ramp Loss function achieved by duplicating all of the unlabeled data in order to associate a cost with classifying all of the unlabeled data into both of the first and second classes.

8. The method of claim 1, further comprising:

mapping data into a high dimensional feature space to generate the labeled training data and the unlabeled test data.

9. The method of claim 8, further comprising:

classifying the real world data using the hyperplane classifier.

17. The computer readable medium of claim 1, further comprising computer program instructions defining the step of:

mapping data into a high dimensional feature space to generate the labeled training data and the unlabeled test data.

18. The computer readable medium of claim 17, further comprising computer program instructions defining the step of:

classifying the real world data using the hyperplane classifier.

10. A computer readable medium storing computer program instructions for training a transductive support vector machine based on an objective function, the objective function based on a set of labeled training data classified into first and second classes and a set of unlabeled test data, said computer program instructions defining the steps comprising:

decomposing the objective function into a sum of a concave function and a convex function; and

determining a hyperplane classifier classifying the unlabeled data into the first and second classes by iteratively approximating the concave and convex functions.

11. The computer readable medium of claim 10, wherein the computer program instructions defining the step of determining a hyperplane classifier comprise:

computer program instructions defining the steps of;

(a) determining an initial hyperplane classifier;

(b) calculating a local approximation of the concave function at the initial hyperplane classifier;

(c) solving a convex problem formed by combining the local approximation to the concave function with the convex function;

(d) determining an updated hyperplane classifier based on the solution to the convex problem;

(e) calculating a local approximation of the concave function at the updated hyperplane classifier; and

(f) repeating steps (c)-(e) until the local approximation of the concave function at the updated hyperplane classifier converges.

12. The computer readable medium of claim 11, wherein the computer program instructions defining step (a) comprise computer program instructions defining the step of:

determining the initial hyperplane classifier using a support vector machine based on the labeled data.

13. The computer readable medium of claim 11, wherein the computer program instructions defining each of steps (b) and (e) comprise computer program instructions defining the step of:

calculating a tangent of the concave function at a hyperplane classifier.

14. The computer readable medium of claim 11, wherein the computer program instructions defining the step of determining a hyperplane classifier further comprise computer program instructions defining the step of:

(g) enforcing a balancing constraint for balancing a ratio of the unlabeled data classified into the first and second classes and a ratio of the labeled data classified into the first and second classes.

15. The computer readable medium of claim 11, wherein the objective function is based on a non-convex loss function for the unlabeled data, and the computer program instructions defining the step of decomposing the objective function comprise computer program instructions defining the step of:

decomposing the loss function for the unlabeled data into a convex Hinge loss function and a concave Hinge loss function.

16. The computer readable medium of claim 15, wherein said loss function for the unlabeled data comprises a Symmetric Ramp Loss function achieved by duplicating all of the unlabeled data in order to associate a cost with classifying all of the unlabeled data into both of the first and second classes.

19. An apparatus for training a transductive support vector machine based on an objective function, the objective function based on a set of labeled training data classified into first and second classes and a set of unlabeled test data, comprising:

means for decomposing the objective function into a sum of a concave function and a convex function; and

means for determining a hyperplane classifier classifying the unlabeled data into the first and second classes by iteratively approximating the concave and convex functions.

20. The apparatus of claim 19, wherein said means for determining a hyperplane classifier comprises:

means for initializing parameters of a hyperplane classifier;

means for calculating a local approximation of the concave function based on the parameters of the hyperplane classifier;

means for solving a convex problem formed by combining the local approximation to the concave function with the convex function; and

means for updating the parameters of the hyperplane classifier based on the solution to the convex problem.

21. The apparatus of claim 20, wherein said means for determining a hyperplane classifier further comprises:

means for determining when the parameters of the hyperplane classifier converge.

22. The apparatus of claim 20, wherein said means for initializing parameters of a hyperplane classifier comprises:

means for determining the parameters of the hyperplane classifier using a support vector machine based on the labeled data.

23. The apparatus of claim 20, wherein said means for calculating a local approximation of the concave function comprises:

means for calculating a tangent of the concave function at the parameters of the hyperplane classifier.

24. The apparatus of claim 20, wherein said means for determining a hyperplane classifier further comprises:

means for enforcing a balancing constraint for balancing a ratio of the unlabeled data classified into the first and second classes and a ratio of the labeled data classified into the first and second classes.

25. The apparatus of claim 19, wherein the objective function is based on a non-convex loss function for the unlabeled data, and said means for decomposing the objective function comprises:

means for decomposing the loss function for the unlabeled data into a convex Hinge loss function and a concave Hinge loss function.

26. The apparatus of claim 25, wherein said loss function for the unlabeled data comprises a Symmetric Ramp Loss function achieved by duplicating all of the unlabeled data in order to associate a cost with classifying all of the unlabeled data into both of the first and second classes.

27. The apparatus of claim 19, further comprising:

means for mapping data into a high dimensional feature space to generate the labeled training data and the unlabeled test data.

28. The apparatus of claim 27, further comprising:

means for classifying the real world data using the hyperplane classifier.