SCALABLE, MEMORY-EFFICIENT MACHINE LEARNING AND PREDICTION FOR ENSEMBLES OF DECISION TREES FOR HOMOGENEOUS AND HETEROGENEOUS DATASETS

• US 20140337255A1
• Filed: 05/07/2014
• Published: 11/13/2014
• Est. Priority Date: 05/07/2013
• Status: Active Grant

• Current Assignee: Wise.Io, Inc. (General Electric Company)
• Original Assignee: Wise.Io, Inc. (General Electric Company)
• Inventors: EADS, DAMIAN RYAN
• Granted Patent: US 9,953,270 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
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

Optimization of machine intelligence utilizes a systemic process through a plurality of computer architecture manipulation techniques that take unique advantage of efficiencies therein to minimize clock cycles and memory usage. The present invention is an application of machine intelligence which overcomes speed and memory issues in learning ensembles of decision trees in a single-machine environment. Such an application of machine intelligence includes inlining relevant statements by integrating function code into a caller'"'"'s code, ensuring a contiguous buffering arrangement for necessary information to be compiled, and defining and enforcing type constraints on programming interfaces that access and manipulate machine learning data sets.

Claims

1. A method of implementing a learning ensemble of decision trees in a single machine computing environment, comprising:

implementing, within a single-machine computing environment comprised of hardware and software components that include at least one processor, the steps of;

inlining relevant statements to integrate function code into a caller'"'"'s code so that repetitive pushing and popping of register content to and from a stack at each compilation is eliminated;

implementing a contiguous buffer arrangement for register content to be compiled in a plurality of buffers; and

defining and enforcing a plurality of type constraints on programming interfaces that access and manipulate at least one machine learning data set so that a plurality of procedures for inducing a forest induction, a tree induction, and a node induction are instantiated for classes implementing the at least one machine learning data set in learning an ensemble of decision trees.

2. The method of claim 1, further comprising computing a score for the at least one machine learning data set during an instantiation of a procedure for a tree induction for any class implementing the at least one machine learning data set.

3. The method of claim 1, wherein the plurality of buffers in the contiguous buffer arrangement includes an instance buffer cache configured to store a feature vector for an instance to reduce the delay associated with cache misses by improving spatial and temporal locality of reference for data needed during node induction.

4. The method of claim 1, further comprising computing an impurity value for splitting criteria in the at least one machine learning data set during an instantiation of a procedure for a tree induction for classes implementing the at least one machine learning data set.

5. The method of claim 1, further comprising computing an impurity value for splitting criteria in the at least one machine learning data set during an instantiation of a procedure for a node induction for classes implementing the at least one machine learning data set.

6. The method of claim 1, wherein the defining and enforcing a plurality of type constraints on programming interfaces further comprises defining specifically-named typedefs.

7. The method of claim 1, wherein the defining and enforcing a plurality of type constraints on programming interfaces enables checking the plurality of type constraints when a class adhering to a concept is needed at compilation, wherein a failure to satisfy any constraints results in compilation failure.

8. The method of claim 1, wherein the defining and enforcing a plurality of type constraints on programming interfaces that access and manipulate at least one machine learning data set further defines a specific set of homogeneous data within the at least one machine learning data set targeted for a learning ensemble of decision trees.

9. The method of claim 1, further comprising representing a subsample by chaining a plurality of classes together where the plurality of type constraints are defined.

10. The method of claim 1, wherein the at least one machine learning data set provides one or more functions for accessing size and problem type information, the one or more functions configured to return a total number of instances and feature vectors, a total number of features in a feature vector, a total number of classes, and a problem type comprised of one or the other of classification and regression.

11. The method of claim 1, wherein the at least one machine learning data set provides one or more functions for accessing individual feature values and labels configured to return a number of classes for classification and regression, one or more functions configured to generate iterators to feature values over a fixed feature index or a fixed instance index, and one or more functions configured to generate iterators to feature values over a fixed instance index.

12. The method of claim 1, wherein the at least one machine learning data set is a writable machine learning data set that permits labels and feature values to be changed, and permits new instances to be added.

13. The method of claim 1, wherein the at least one machine learning data set is implemented in multiple classes in which machine learning data is stored in memory, each class using an optimized memory layout for a different purpose.

14. The method of claim 11, wherein one optimized memory layout is configured to store a machine learning data set so that all instances for a specific feature index are stored contiguously, and another optimized memory layout is configured to store a machine learning data set so that all features for a specific instance index are stored contiguously.

15. A system comprising:

a computer processor; and

at least one computer-readable storage medium operably coupled to the computer processor and having program instructions stored therein, the computer processor being operable to execute the program instructions to optimize machine intelligence for implementing a learning ensemble of decision trees in a single-machine environment in a plurality of data processing modules, the plurality of data processing modules configured to integrate function code into a caller'"'"'s code by inlining relevant statements so that repetitive pushing and popping of register content to and from a stack at each compilation is eliminated, implement a contiguous arrangement for register content to be compiled in a plurality of buffers, and define and enforce type constraints on programming interfaces that access and manipulate machine learning data sets so that a plurality of procedures for inducing a forest induction, a tree induction, and a node induction are instantiated for classes implementing the machine learning data sets in a process for implement the learning ensemble of decision trees.

16. The system of claim 15, wherein the plurality of data processing functions embody one or more concepts arranged to subsample the machine learning data sets by chaining multiple classes together that implement the machine learning data sets.

17. The system of claim 15, wherein the plurality of buffers includes an instance buffer cache configured to store a feature vector for an instance to reduce the delay associated with cache misses by improving spatial and temporal locality of reference for data needed during node induction.

18. The system of claim 15, wherein the type constraints include specifically-named typedefs.

19. The system of claim 15, wherein the type constraints determine when a class adhering to a concept is needed at compilation, and further wherein a failure to satisfy any constraints results in compilation failure.

20. The system of claim 15, wherein the type constraints enable accessing and manipulating at least one machine learning data set that further defines a specific set of homogeneous data within the at least one machine learning data set targeted for a learning ensemble of decision trees.

21. The system of claim 15, wherein the at least one machine learning data set is a writable machine learning data set that permits labels and feature values to be changed, and permits new instances to be added.

22. The system of claim 15, wherein the at least one machine learning data set is implemented in multiple classes in which machine learning data is stored in memory, each class using an optimized memory layout for a different purpose.

23. The system of claim 15, wherein the plurality of data processing modules are further configured to compute a score for data in the machine learning data sets during an instantiation of a procedure for a tree induction for classes implementing the machine learning data sets.

24. The system of claim 15, wherein the plurality of data processing modules are further configured to compute an impurity value for splitting criteria in the at least one machine learning data set during an instantiation of a procedure for a tree induction for classes implementing the machine learning data sets.

25. The system of claim 15, wherein the plurality of data processing modules are further configured to compute an impurity value for splitting criteria in the machine learning data sets during an instantiation of a procedure for a node induction for classes implementing the machine learning data sets.

26. A method of implementing a learning ensemble of decision trees in a single-machine computing environment, comprising:

implementing, within a single-machine computing environment comprised of hardware and software components that include at least one processor, a compiler optimization routine that determines run time compilation requirements by copying compiled code for a function into a caller'"'"'s compiled code so that function call overhead from pushing and popping register content and local variables to a stack for each function call is eliminated;

aligning buffers comprising a plurality of caches to place bytes required for compilation in a contiguous arrangement so that fewer pages of data are pulled from memory to blocks in the plurality of caches, the plurality of caches including a feature buffer cache that copies dis-contiguous feature values comprised of all instances with respect to a specific feature dimension into the contiguous arrangement, and an instance buffer cache that copies a dis-contiguous feature vector for an instance into the contiguous arrangement; and

applying one or more of class and function templates to target specific datasets by enforcing type constraints on programming interfaces that access and manipulate at least one machine learning data set so that a plurality of procedures for inducing a forest induction, a tree induction, and a node induction are instantiated for classes implementing the at least one machine learning data set in learning an ensemble of decision trees.

27. The method of claim 26, wherein the compiler optimization routine enables inlining of one or more of relevant statements, variants and procedures.

28. The method of claim 26, wherein the one or more class and function templates impart restrictions on types to provide a mechanism for specifying the programming interfaces for template parameters.

29. The method of claim 26, wherein the type constraints include specifically-named typedefs.

30. The method of claim 26, wherein the type constraints determine when a class adhering to a concept is needed at compilation, and further wherein a failure to satisfy any constraints results in compilation failure.

31. The method of claim 26, wherein the type constraints enable accessing and manipulating at least one machine learning data set that further defines a specific set of homogeneous data within the at least one machine learning data set targeted for a learning ensemble of decision trees.

32. The method of claim 26, wherein the at least one machine learning data set is a writable machine learning data set that permits labels and feature values to be changed, and permits new instances to be added.

33. The method of claim 26, wherein the at least one machine learning data set is implemented in multiple classes in which machine learning data is stored in memory, each class using an optimized memory layout for a different purpose.

34. The method of claim 26, wherein the applying one or more of class and function templates to target specific datasets by enforcing type constraints on programming interfaces further comprises computing a score for the at least one machine learning data set during an instantiation of a procedure for a tree induction for any class implementing the at least one machine learning data set.

35. The method of claim 26, wherein the applying one or more of class and function templates to target specific datasets by enforcing type constraints on programming interfaces further comprises computing an impurity value for splitting criteria in the at least one machine learning data set during an instantiation of a procedure for a tree induction for classes implementing the at least one machine learning data set.

36. The method of claim 26, wherein the applying one or more of class and function templates to target specific datasets by enforcing type constraints on programming interfaces further comprises computing an impurity value for splitting criteria in the at least one machine learning data set during an instantiation of a procedure for a node induction for classes implementing the at least one machine learning data set.

37. The method of claim 26, further comprising representing a subsample by chaining a plurality of classes together for the one or more of class and function templates.