LEARNING MULTIPLE TASKS WITH BOOSTED DECISION TREES

• US 20130282627A1
• Filed: 04/20/2012
• Published: 10/24/2013
• Est. Priority Date: 04/20/2012
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris, Faddoul, Jean-Baptiste
• Granted Patent: US 8,694,444 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

A multi-task machine learning method is performed to generate a multi-task (MT) predictor for a set of tasks including at least two tasks. The machine learning method includes: learning a multi-task decision tree (MT-DT) including learning decision rules for nodes of the MT-DT that optimize an aggregate information gain (IG) that aggregates single-task IG values for tasks of the set of tasks; and constructing the MT predictor based on the learned MT-DT. In some embodiments the aggregate IG is the largest single-task IG value of the single-task IG values. In some embodiments the machine learning method includes repeating the MT-DT learning operation for different subsets of a training set to generate a set of learned MT-DT'"'"'s, and the constructing comprises constructing the MT predictor as a weighted combination of outputs of the set of MT-DT'"'"'s.

Claims

1. An apparatus comprising:

an electronic data processing device configured to perform a multi-task machine learning method to generate a multi-task (MT) predictor for a set of N classification tasks where N is greater than or equal to two, the machine learning method including;

learning a multi-task decision tree (MT-DT) including learning decision rules for nodes of the MT-DT that optimize an aggregate information gain (IG) that aggregates single-task IG values for tasks of the set of N classification tasks; and

constructing the MT predictor based on one or more learned MT-DTs.

2. The apparatus of claim 1 wherein at least one task of the set of N classification tasks is a multi-class task.

3. The apparatus of claim 2 wherein the learning of decision rules for nodes further includes (i) determining whether a final decision can be made at a node for a task of the set of N classification tasks that is completed at the node and (ii) adding a decision node for any completed task.

4. The apparatus of claim 1 wherein the aggregate IG is the largest single-task IG value of the single-task IG values.

5. The apparatus of claim 1 wherein the aggregate IG is max{IG(Y_j|X)} where the IG(Y_j|X) terms are the single-task IG values for tasks T_j, j=1, . . . , N that are aggregated.

6. The apparatus of claim 1 wherein the constructing includes:

constructing the MT predictor based on a single learned MT-DT.

7. The apparatus of claim 1 wherein the machine learning method includes repeating the MT-DT learning operation for different subsets of a training set to generate a set of learned MT-DT'"'"'s, and the constructing comprises:

constructing the MT predictor as a weighted combination of outputs of the set of MT-DT'"'"'s.

8. The apparatus of claim 7 wherein the constructing includes:

combining the outputs of the MT-DT'"'"'s using a multi-task adaptive boosting (MT-AdaBoost) algorithm.

9. The apparatus of claim 1 wherein the electronic data processing device is further configured to perform a multi-task inference method using the constructed MT predictor.

10. The apparatus of claim 9 wherein the multi-task inference method comprises classifying an input electronic mail (email) message using the constructed MT predictor.

11. The apparatus of claim 9 wherein the multi-task inference method comprises annotating an input document using the constructed MT predictor.

12. A method comprising:

learning a multi-task decision tree (MT-DT) for a set of tasks including at least two tasks, the learning including learning decision rules for nodes of the MT-DT that maximize the largest single-task information gain (IG) for tasks of the set of tasks; and

constructing a multi-task (MT) predictor based on one or more learned MT-DTs;

wherein the learning and the constructing are performed by an electronic data processing device.

13. The method of claim 12 wherein at least one task of the set of tasks is a multi-class task.

14. The method of claim 13 wherein the learning of decision rules for nodes includes (i) determining whether a final decision can be made at a node for a task of the set of tasks that is completed at the node and (ii) adding a decision node for any completed task.

15. The method of claim 12 wherein the MT-DT learning operation is repeated for different subsets of a training set to generate a set of learned MT-DT'"'"'s, and the constructing comprises:

constructing the MT predictor as a weighted combination of outputs of the set of learned MT-DT'"'"'s.

16. The method of claim 15 wherein the constructing includes:

combining the outputs of the set of learned MT-DT'"'"'s using a multi-task adaptive boosting (MT-AdaBoost) algorithm.

17. The method of claim 12 wherein the electronic data processing device is further configured to perform a multi-task inference method using the constructed MT predictor.

18. A non-transitory storage medium storing instructions executable by an electronic data processing device to perform a method including (i) learning a set of multi-task decision trees (MT-DT'"'"'s) for a set of tasks including at least two tasks using different subsets of a training set wherein the learning of each MT-DT includes learning decision rules for nodes of the MT-DT that maximize an aggregate information gain (IG) that aggregates single-task IG values for tasks of the set of tasks and (ii) constructing a multi-task (MT) predictor as a weighted combination of outputs of the learned set of MT-DT'"'"'s.

19. The non-transitory storage medium of claim 18 wherein at least one task of the set of tasks is a multi-class task.

20. The non-transitory storage medium of claim 19 wherein the learning of decision rules for nodes includes (i) determining whether a final decision is made for a task at the node and (ii) adding a decision node for any decided task.

21. The non-transitory storage medium of claim 18 wherein the aggregate IG is the maximum single-task IG value of the single-task IG values.

22. The non-transitory storage medium of claim 18 wherein the aggregate IG is max{IG(Y_j|X)} where the IG(Y_j|X) terms are the single-task IG values that are aggregated.

23. The non-transitory storage medium of claim 18 wherein the constructing includes:

combining the outputs of the MT-DT'"'"'s using a multi-task adaptive boosting (MT-AdaBoost) algorithm.