Distributed decision tree training

A computerized decision tree training method, comprising:

• receiving input of training data for training a decision tree, the training data including multiple data units, each data unit further including at least one example datum having an associated class label;
• for each datum in each data unit in each of a plurality of data batches of the data units, evaluating each of a plurality of split functions of the decision tree on a respective data batch processing unit for each data batch, to thereby compute a partial histogram for each split function and each datum in the data batch;
• for each of a subset of frontier tree nodes of the decision tree in a respective tree node batch, receiving and aggregating the associated partial histograms for each split function to form an aggregated histogram for each split function at the frontier tree node, at a respective node batch processing unit;
• determining a selected split function for each frontier tree node by computing the split function that produces highest information gain;
• reclassifying each of the frontier tree nodes as a split node including a respective one of the selected split functions;
• expanding the decision tree to include new frontier tree nodes branching from the split nodes;
• and
• outputting the decision tree for installation on a downstream computing device.

A computerized decision tree training method, comprising:

• receiving input of training data, the training data including multiple data units, each data unit including at least one image or image region, each data unit further including at least one example datum having an associated class label;
• initializing a decision tree, the decision tree being having a plurality of associated split functions and classes, and being comprised of a root node and one or more split nodes and frontier tree nodes;
• partitioning the training data into a plurality of data batches, each data batch including a respective subset of data units;
• distributing each data batch to a respective data batch processing unit;
• for each datum in each data unit in each data batch, evaluating each of the split functions on the respective data batch processing unit for the data batch, to thereby compute a partial histogram for each split function and each datum in the data batch;
• partitioning the frontier tree nodes into a plurality of frontier tree node batches;
• distributing each frontier tree node batch to a respective node batch processing unit;
• distributing the partial histograms for a selected subset of data from each data unit in each data batch on each of the respective data batch processing units to a corresponding node batch processing unit, wherein the selected subset is selected by selecting each datum that is classified by the decision tree to be at a frontier tree node that corresponds to the node batch processing unit;
• on each node batch processing unit, for each frontier tree node in the respective tree node batch, aggregate the associated partial histograms for each split function to form an aggregated histogram for each split function at the frontier tree node;
• determining a selected split function for each frontier tree node by computing the split function that produces maximum information gain;
• reclassifying each of the frontier tree nodes as split nodes including each of the respective optimal split functions;
• expanding the decision tree to include new frontier tree nodes branching from the split nodes;
• and
• outputting the decision tree for installation on a downstream computing device.