PARALLEL PROCESSING MACHINE LEARNING DECISION TREE TRAINING

• US 20120154373A1
• Filed: 12/15/2010
• Published: 06/21/2012
• Est. Priority Date: 12/15/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Finocchio, Mark, Geiss, Ryan M., Shotton, Jamie, Moore, Richard E.
• Granted Patent: US 9,171,264 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06F 18/24317 Piecewise classification, i.e. whereby each classification requires several discriminant rules
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

Embodiments are disclosed herein that relate to generating a decision tree through graphical processing unit (GPU) based machine learning. For example, one embodiment provides a method including, for each level of the decision tree: performing, at each GPU of the parallel processing pipeline, a feature test for a feature in a feature set on every example in an example set. The method further includes accumulating results of the feature tests in local memory blocks. The method further includes writing the accumulated results from each local memory block to global memory to generate a histogram of features for every node in the level, and for each node in the level, assigning a feature having a lowest entropy in accordance with the histograms to the node.

Claims

1. A method for generating a decision tree including a plurality of nodes organized into levels from a parallel processing pipeline including a plurality of processing blocks, each processing block including a plurality of graphical processing units (GPUs) sharing a memory block, and each GPU of parallel processing pipeline sharing a global memory, the method comprising, for each level of the decision tree:

performing, at each GPU of the parallel processing pipeline, a feature test for a feature in a feature set on every example in an example set;

accumulating, at each memory block, a result of each feature test performed on each example processed by the plurality of GPUs that share the memory block;

writing, the accumulated results from each memory block to the global memory to generate a histogram of features for every node in the level; and

for each node in the level, assigning a feature having a lowest entropy in accordance with the histograms to the node.

2. The method of claim 1, wherein each example includes a pixel selected from one of a plurality of depth maps, and the example set includes pixels from each of the plurality of depth maps.

3. The method of claim 2, wherein all pixels selected from a depth map are processed by a selected processing, block, and each processing block processes one depth map at a time.

4. The method of claim 2, wherein each depth map comprises a plurality of object planes, the method farther comprises:

modifying a depth map to add/remove one of the plurality of object planes to decrease entropy of a feature assigned to a node.

5. The method of claim 2, wherein the plurality of depth maps include different character poses, and the decision tree classifies examples selected from the character poses as different body parts.

6. The method of claim 1, wherein accumulating includes performing an atomic increment to a portion of the memory block when a plurality of feature test results are in contention for the portion of the memory block, and performing a non-atomic increment to a portion of the memory block when one feature test result is to be stored in the portion of the memory block.

7. The method of claim 1, wherein writing includes performing an atomic add to the global memory for each portion of the memory block that includes an accumulated feature test result value.

8. The method of claim 1, wherein the parallel processing pipeline operates according to a compute unified device architecture (CUDA).

9. A computing system comprising:

a parallel processing pipeline comprising;

a plurality of processing blocks each including a plurality of graphical processing units (GPUs);

a plurality of memory blocks each being shared by the plurality of GPUs of an associated processing block; and

a global memory shared by each GPU of the parallel processing pipeline; and

a decision tree training program configured to generate a decision tree including a plurality of nodes organized into levels, the decision tree training program representing instructions executable by the parallel processing pipeline to, for each level of the decision tree;

perform, at each GPU of the parallel processing pipeline, a feature test for a feature in a feature set on every example in an example set for every node in a level;

accumulate, at each memory block, a result of each feature test performed on each example processed by the plurality of GPUs that share the memory block;

write the accumulated results from each memory block to the global memory to generate a histogram of features for every node in the level; and

for each node in the level, assign a feature having a lowest entropy in accordance with the histograms to the node.

10. The computing system of claim 9, wherein each example includes a pixel selected from one of a plurality of depth maps, and the example set includes pixels from each of the plurality of depth maps.

11. The computing system of claim 10, wherein all pixels selected from a depth map are processed by a selected processing block, and each processing, block processes one depth map at a time.

12. The computing system of claim 10, wherein each depth map comprises a plurality of object planes, the decision tree training program farther representing instructions executable by the parallel processing pipeline to:

modify a depth map to add/remove one of the plurality of object planes to decrease entropy of a feature assigned to a node.

13. The computing system of claim 10, wherein the plurality of depth maps include different character poses, and the decision tree classifies examples selected from the character poses as different body parts.

14. The computing system of claim 9, wherein accumulate includes performing an atomic increment to a portion of the memory block when a plurality of feature test results are in contention for the portion of the memory block, and performing a non-atomic increment to a portion of the memory block when one feature test result iso to be stored in the portion of the memory block.

15. The computing system of claim 9, wherein write includes performing an atomic add to the global memory for each portion of the memory block that includes an accumulated feature test result value.

16. The computing system of claim 9, wherein the parallel processing pipeline operates according to a compute unified device architecture (CUDA).

17. A method for generating a decision tree including a plurality nodes organized into levels from a parallel processing pipeline including a plurality of processing blocks, each processing block including a plurality of graphical processing units (GPUs) sharing a memory block, and each GPU of the parallel processing pipeline sharing global memory, the method comprising, for each level of the decision tree:

performing, at each GPU of the parallel processing pipeline, a feature test for a feature in a feature set on every pixel example selected from one of a plurality of depth maps included in an example set, wherein the example set includes example pixels from each of the plurality of depth maps, and wherein all example pixels selected from a depth map are processed by a selected processing block, and each processing block processes one depth map at a time;

accumulating, at each memory block, a result of each feature test performed on each pixel example processed by the plurality of GPUs that share the memory block,

writing the accumulated results from each memory block to the global memory to generate a histogram of features for every node in the level; and

for each node in the level, assigning a feature having a lowest entropy in accordance with the histograms to the node.

18. The method of claim 17, wherein each depth map comprises a plurality of object planes, the method further comprises:

modifying a depth map to add/remove one of the plurality of object planes to decrease entropy of a feature assigned to a node.

19. The method of claim 17, wherein the plurality of depth maps include different character poses, and the decision tree classifies examples selected from the character poses as different body parts.

20. The method of claim 17, wherein accumulating includes performing an atomic increment to a portion of the memory block when a plurality of feature test results are in contention for the portion of the memory block, and performing a non-atomic increment to a portion of the memory block when one feature test result is to be stored the portion of the memory block, and writing includes performing an atomic add to the global memory for each portion of the memory block that includes an accumulated feature test result value.