DECISION TREE TRAINING IN MACHINE LEARNING

• US 20140122381A1
• Filed: 10/25/2012
• Published: 05/01/2014
• Est. Priority Date: 10/25/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nowozin, Reinhard Sebastian Bernhard
• Granted Patent: US 9,373,087 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• 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 the basis of uncertainty measures of at least some of the received training data computed using an uncertainty measurement logic;

the uncertainty measurement logic arranged to either correct for bias in the uncertainty measurement or to use a non-parametric estimate of uncertainty.

2. A machine learning device as claimed in claim 1, the uncertainty measurement logic using a 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.

3. 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.

4. A machine learning device as claimed in claim 1, the uncertainty measurement logic arranged to compute a bias corrected estimate of a Gini index where a Gini index is a measure of inequality of a multinomial distribution.

5. A machine learning device as claimed in claim 1, the uncertainty measurement logic arranged to compute a bias corrected estimate of a 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.

6. A machine learning device as claimed in claim 1, the uncertainty measurement logic arranged to compute a bias corrected estimate of a Gini index by aggregating a plurality of perturbations of a biased estimate of a Gini index.

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

8. 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.

9. A machine learning device as claimed in claim 1, the uncertainty measurement logic using a 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.

10. A machine learning device as claimed in claim 1, the uncertainty measurement logic using a 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.

11. A machine learning device as claimed in claim 1, the uncertainty measurement logic using a 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.

12. 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, a graphics processing unit.

13. 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 the basis of a measure of uncertainty of at least some of the received training data;

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.

14. A method as claimed in claim 13 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.

15. A method as claimed in claim 13 comprising computing a bias corrected estimate of a Gini index where a Gini index is a measure of inequality of a multinomial distribution.

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

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

18. 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 of at least some of the received training data;

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; and

where the number of possible classes is such that it is difficult to estimate empirical class frequencies reliably.

19. A method as claimed in claim 18 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.

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