Multi-task machine learning using features bagging and local relatedness in the instance space

1. An apparatus comprising:

a multi-task machine learning component for learning a set of T tasks, where T is greater than or equal to three, based on a set of examples wherein the examples are represented by features of a set of features, the multi-task machine learning component comprising a digital processing device configured to bootstrap aggregate features of the set of features by sampling the set of features M times uniformly and with replacement to generate M possibly overlapping sub-sets of the set of features defining M feature bags where M is an integer equal to or greater than two and learn an ensemble of M base rules wherein each base rule is learned for a different one of the M feature bags and comprises a multi-task decision tree (MT-DT) having nodes comprising decision rules for tasks of the set of tasks, wherein the multi-task machine learning component learns each base rule by:

(i) learning a decision rule for a task of the set of T tasks wherein the learned decision rule defines a node of the MT-DT and the possible outputs of the decision rule define links to child nodes for which the learned node is the parent node, and

(ii) recursively repeating the learning (i) for each child node with the set of T tasks trimmed to remove the task to which the decision rule of the parent node is directed,

wherein the base rule is an MT-DT with T levels corresponding to the T tasks comprising the set of nodes generated by the learning operations (i) and (ii); and

an inference component comprising a digital processing device configured to predict a result for at least one task of the set of tasks for an input item represented by features of the set of features using the learned ensemble of base rules.

2. The apparatus of claim 1 , wherein the learning (i) is performed for a portion of the set of examples and the recursive repeating (ii) further includes trimming the set of examples to remove that portion of the set of examples used in the learning (i).

3. The apparatus of claim 1 , wherein the recursive repeating (ii) includes (i)(a) learning a decision rule for each task of the trimmed set of tasks and (i)(b) selecting the learned decision rule that minimizes an error metric.

4. The apparatus of claim 1 , wherein the inference component is configured to predict a result for at least one task of the set of tasks using a voting or averaging algorithm employing the base rules of the learned ensemble of base rules.

5. A method operating on a set of examples wherein the examples are represented by features of a set of features, the method comprising:

sampling the set of features to generate a sub-set of the set of features

learning a base rule comprising a multi-task decision tree (MT-DT) having multi-node paths defining sets of decision rules for different tasks of a set of tasks in order to learn a base rule wherein the base rule is learned for the sub-set of the set of features;

repeating the sampling and the learning M times where M is an integer equal to or greater than three in order to learn an ensemble of M base rules each comprising a MT-DT; and

predicting a result for a plurality of tasks of the set of tasks for an input item represented by features of the set of features using the learned ensemble of M base rules;

wherein the sampling and the learning are performed by a digital processing device and the predicting is performed by one of (1) the same digital processing device that performs the sampling and the learning and (2) a digital processing device different from the digital processing device that performs the bootstrap aggregating and the learning.

6. The method of claim 5 , wherein any multi-node path of the MT-DT consisting of N nodes defines a set of N decision rules for N different tasks of the set of rules, where N is an integer greater than or equal to three.

7. The method of claim 5 , wherein the learning comprises:

learning the multi-task decision tree for bags the sub-set of the set of features by:

(i) learning a decision rule for a task of the set of tasks wherein the learned decision rule defines a node of the multi-task decision tree and the possible outputs of the decision rule define links to child nodes for which the learned node is the parent node, and

(ii) recursively repeating the learning (i) for each child node with the set of tasks trimmed to remove the task to which the decision rule of the parent node is directed.

8. A non-transitory storage medium storing instructions executable by a digital processor to perform a method operating on a set of examples wherein the examples are represented by features of a set of features, the method comprising:

sampling the set of features M times to form M feature groups where M is an integer greater than or equal to three;

generating a base rule comprising a multi-task decision tree (MT-DT) for T tasks where T is greater than or equal to three by:

(i) learning a decision rule for a task of the set of T tasks using a feature group of the M feature groups wherein the learned decision rule defines a node of the multi-task decision tree and the possible outputs of the decision rule define links to child nodes for which the learned node is the parent node, and

(ii) recursively repeating the learning (i) for each child node with the set of tasks trimmed to remove the task to which the decision rule of the parent node is directed wherein the recursive repeating is performed to generate the MT-DT with T levels with each level corresponding to a different task of the T tasks, and

repeating the generating for each feature group of the M feature groups to generate M base rules each comprising a MT-DT with T levels; and

constructing a multi-task ensemble classifier comprising an ensemble of at least the M base rules each comprising a MT-DT with T levels.

9. The non-transitory storage medium of claim 8 , wherein the recursive repeating (ii) further includes trimming the set of examples to remove the portion of the set of examples used in the learning (i).

10. The non-transitory storage medium of claim 8 , wherein the constructing of the multi-task ensemble classifier comprises:

constructing a multi-task ensemble classifier comprising one of (1) a vote by the M base rules and (2) an average of the M base rules.