Decision tree training in machine learning

• US 9,373,087 B2
• Filed: 10/25/2012
• Issued: 06/21/2016
• Est. Priority Date: 10/25/2012
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Nowozin, Reinhard Sebastian Bernhard
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): LAMARDO, VIKER ALEJANDRO
• Application Number:
  US13/660,692
• Publication Number:
  US 20140122381A1
• Time in Patent Office: 1,335 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning

Abstract

Improved decision tree training in machine learning is described, for example, for automated classification of body organs in medical images or for detection of body joint positions in depth images. In various embodiments, improved estimates of uncertainty are used when training random decision forests for machine learning tasks in order to give improved accuracy of predictions and fewer errors. In examples, bias corrected estimates of entropy or Gini index are used or non-parametric estimates of differential entropy. In examples, resulting trained random decision forests are better able to perform classification or regression tasks for a variety of applications without undue increase in computational load.

Claims

1. A machine learning device comprising:

a communications interface arranged to receive training data;

a tree training logic arranged to train a random decision forest using the received training data and on a basis of uncertainty measures taken at a plurality of split nodes of at least some of the received training data computed using an uncertainty measurement logic;

the tree training logic further arranged to train the random decision forest at least on a basis of a bias-corrected Gini index; and

the uncertainty measurement logic arranged to calculate a measure of uncertainty which is bias corrected in case of classification tasks or which uses a non-parametric estimate of the uncertainty in case of regression.

2. A machine learning device as claimed in claim 1, the uncertainty measurement logic arranged to correct for bias introduced by estimation, using a limited amount of training data, of a probability distribution from which the training data is generated.

3. A machine learning device as claimed in claim 1, the uncertainty measurement logic arranged to compute a bias corrected estimate of the Gini index by using a resampling method that estimates a mean of a probability distribution of an estimated Gini index of a sample from the training data.

4. A machine learning device as claimed in claim 1, the uncertainty measurement logic arranged to compute a bias corrected estimate of an entropy.

5. A machine learning device as claimed in claim 1 the uncertainty measurement logic arranged to compute a bias corrected estimate of an entropy using a Grassberger estimate.

6. A machine learning device as claimed in claim 1, the uncertainty measurement logic using the non-parametric estimate of uncertainty which is an estimate of a probability distribution of the training data made without assuming that the probability distribution comes from a specified family of parametric distributions, and where the non-parametric estimate of uncertainty uses a one-nearest neighbor estimator.

7. A machine learning device as claimed in claim 1, the uncertainty measurement logic using the non-parametric estimate of uncertainty which is an estimate of a probability distribution of the training data made without assuming that the probability distribution comes from a specified family of parametric distributions, and where the non-parametric estimate of uncertainty uses a one-nearest neighbor estimator computed using k-d trees.

8. A machine learning device as claimed in claim 1, the uncertainty measurement logic using the non-parametric estimate of uncertainty which is an estimate of a probability distribution of the training data made without assuming that the probability distribution comes from a specified family of parametric distributions, and where the non-parametric estimate of uncertainty uses any of:

a kernel density estimate, a length of minimum spanning trees, a k-nearest neighbor distance.

9. A machine learning device as claimed in claim 1 the uncertainty measurement logic being at least partially implemented using hardware logic selected from any one or more of:

a field-programmable gate array, a program-specific integrated circuit, a program-specific standard product, a system-on-a-chip, a complex programmable logic device, and a graphics processing unit.

10. A machine learning method comprising:

receiving training data at a communications interface;

training, at a processor, a random decision forest using the received training data and on a basis of a measure of uncertainty taken at at least one split node of at least some of the received training data, the measure of uncertainty calculated based at least in part on bootstrap resampling;

further training the random decision forest at least on a basis of a bias-corrected Gini index; and

computing, at the processor, the measure of the uncertainty so as to either correct for bias in the measurement of the uncertainty or to use a non-parametric estimate of the uncertainty.

11. A method as claimed in claim 10 comprising computing the measure of the uncertainty so as to correct for bias introduced by estimation, using a limited amount of training data, of a probability distribution from which the training data is generated.

12. A method as claimed in claim 10 comprising computing a bias corrected estimate of an entropy.

13. A method as claimed in claim 10 at least partially carried out using hardware logic.

14. A method as claimed in claim 10, wherein a bias corrected estimate of the Gini index is computed by using a resampling method that estimates a mean of a probability distribution of an estimated Gini index of a sample from the training data.

15. A method as claimed in claim 10, wherein the measure of the uncertainty is computed using hardware logic selected from any one or more of:

a field-programmable gate array, a program-specific integrated circuit, a program-specific standard product, a system-on-a-chip, a complex programmable logic device, and a graphics processing unit.

16. A method as claimed in claim 10, wherein the non-parametric estimate of uncertainty is used which is an estimate of a probability distribution of the training data made without assuming that the probability distribution comes from a specified family of parametric distributions, and where the non-parametric estimate of uncertainty uses a one-nearest neighbor estimator.

17. A machine learning method comprising:

receiving training data at a communications interface the training data comprising examples of data to be classified into one of a plurality of possible classes;

training, at a processor, a random decision forest to classify data into the possible classes, the training carried out using the received training data and on the basis of a measure of uncertainty taken at at least one split node of at least some of the received training data;

computing, at the processor, the measure of the uncertainty so as to use a non-parametric estimate of the uncertainty, the non-parametric measure of the uncertainty based at least in part on a one-nearest neighbor estimator of differential entropy, calculation of the entropy comprising a sum over the training data of a logarithm of Euclidean distance, and bias-correcting the measure of uncertainty and where a number of possible classes is such that it is difficult to estimate empirical class frequencies reliably.

18. A method as claimed in claim 17 comprising computing the measure of the uncertainty so as to correct for bias introduced by estimation, using a limited amount of training data, of a probability distribution from which the training data is generated.

19. A method as claimed in claim 17 where the number of possible classes is at least ten.

20. A method as claimed in claim 17 at least partially carried out using hardware logic.