Parallel processing machine learning decision tree training

• US 9,171,264 B2
• Filed: 12/15/2010
• Issued: 10/27/2015
• Est. Priority Date: 12/15/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Finocchio, Mark, Moore, Richard E., Geiss, Ryan M., Shotton, Jamie
• Primary Examiner(s): Wu, Xiao
• Assistant Examiner(s): Sonners, Scott E
• Application Number:
  US12/969,112
• Publication Number:
  US 20120154373A1
• Time in Patent Office: 1,777 Days
• Field of Search: 345/541, 345/502, 345/505, 345/506, 706/55
• US Class Current: 1/1
• 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 computing system comprising:

a parallel processing pipeline comprising;

a plurality of processing blocks each including a plurality of graphical processing units (GPUs), each of the plurality of GPUs in a same processing block sharing a memory block that is not used by GPUs from other processing blocks; and

a global memory shared by all GPUs from all processing blocks 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 that memory block, wherein such 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;

write the accumulated results from each memory block to the global memory to generate a histogram of features for every node in the level, wherein such writing includes performing an atomic add to the global memory for each portion of the memory block that includes an accumulated feature test value; and

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

2. The computing system 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 computing system 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 computing system of claim 2, wherein each depth map comprises a plurality of object planes, the decision tree training program further 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.

5. The computing system 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 computing system of claim 1, wherein the parallel processing pipeline operates according to a compute unified device architecture (CUDA).

7. The computing system of claim 1, where the instructions are executable to perform a boost operation that receives and analyzes input data in order to selectively increase a proportion of specific examples in the example set.

8. 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), each of the plurality of GPUs in a same processing block sharing a memory block that is not used by GPUs from other processing blocks, and all GPUs from all processing blocks of the 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 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 from a depth map are processed by GPUs of a same processing block, and all GPUs in the same processing block process 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 that memory block, wherein the 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;

writing the accumulated results from each memory block to the global memory to generate a histogram of features for every node in the level, wherein the 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; and

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

9. The method of claim 8, wherein each depth map comprises a plurality of object planes, the method further comprising:

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

10. The method of claim 8, 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.

11. The method of claim 8, where the example set is generated via a boost operation which receives and analyzes input data in order to selectively increase a proportion of specific examples in the example set.

12. 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 that memory block, wherein such 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;

write the accumulated results from each memory block to the global memory to generate a histogram of features for every node in the level, wherein such writing includes performing an atomic add to the global memory for each portion of the memory block that includes an accumulated feature test value; and

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

13. The computing system of claim 12, 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.

14. The computing system of claim 13, wherein each depth map comprises a plurality of object planes, the decision tree training program further 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.

15. The computing system of claim 12, where the instructions are also being executable to perform a boost operation that receives and analyzes input data in order to selectively increase a proportion of specific examples in the example set.