Training ensembles of randomized decision trees

RELATED APPLICATIONS

This application claims the benefit of priority under 35 USC 119(e) of U.S. Provisional Patent Application Nos. 61/758,452 filed Jan. 30, 2013, and 61/767,279 filed Feb. 21, 2013. The contents of the above applications are incorporated herein by reference in their entirety.

BACKGROUND

The present invention, in some embodiments thereof, relates to training ensembles of randomized decision trees systems and methods and, more specifically, but not exclusively, training ensembles of randomized decision trees using multiple large training data sets over distributed streaming processing nodes, for example graphic processing units (GPU), multi-core central processing units (CPU) and processing nodes clusters.

Randomized decision tree is a tree like model used for evaluating decisions and predictions and their possible consequences and outcomes. Randomized decision trees are used in various fields, for example financial applications, medical data analysis and gaming applications.

To achieve best results in decision making, randomized decision trees need to be trained and built to employ the best decision (in a statistical sense) and classification path for input data based on data attributes. The randomized decision tree will be better trained as multiple large data sets are driven into it during the training process.

Randomized decision trees training techniques are available in a plurality of implementation methods, for example depth first, breadth first or hybrid depth first/breadth first. Depth first means a branch is built through all its nodes all the way to its leafs and then moving on to the next branch while breadth first means building nodes at a tree level across all branches and moving down one level at a time.

SUMMARY

According to some embodiments of the present invention, there are provided methods for training a randomized decision tree. The training process is performed in a plurality of tree level iterations, each tree level iteration expanding the randomized decision tree by another tree level in breadth first order. During each tree level iteration a plurality of training data samples is received by a distributed processing control unit, the training data samples include a plurality of data subsets, each corresponding to one of a plurality of attributes. The data subsets are distributed to a plurality of slave processing units after sorting the data samples in consecutive ascending order by updating a first index identifying the trajectories of the training data samples through tree nodes of the previous tree level. The data subsets are simultaneously by a plurality of slave processing units to identify a plurality of split functions with respect to each data subset for one or more tree nodes of the current tree level. A second index is updated (by the slave processing units) that identifies the trajectories of the training data samples through the tree nodes of the current tree level. The split functions are collected from the slave processing units and another tree level is constructed by selecting a preferred split function for each tree node of the current tree level. Split functions information of each tree node comprises a pair of data attribute and a threshold value that together provide best reduction in impurity for a respective tree node. The randomized decision tree is then outputted by providing the tree nodes information for the tree levels as created during the plurality of tree level iterations. Note that the first index that is used during the current tree level iteration is equal to the second index that is used during the previous tree level iteration.

Optionally, a randomized decision tree ensemble is created by repeating the training process as described for a single randomized decision tree for a plurality of randomized decision trees.

Receiving the training data samples is performed by loading them from a plurality of mass storage media sources to a plurality of local memory arrays.

Optionally, the training data samples are received from an on-line source.

More optionally, the first tree level iteration the first index assigned to the training data samples represents the order in which the training data samples are received.

More optionally, one or more data subsets are preloaded to the local memory and transferred to one or more slave processing units to be processed after the one or more slave processing unit completes processing the current data subset.

More optionally, data subsets are loaded at remote slave processing unit clusters that are synchronized with the loading process of the distributed processing control unit.

More optionally, the complete randomized tree structure and one or more data subsets are loaded to a graphic processing unit (GPU) slave processing unit to accommodate the GPU integrated processing units and memory operation mode.

More optionally, identification of the split functions is done by generating histograms for a left child tree node during the tree level iteration, while a right tree node child histogram generation is created by subtracting the left tree node child from a parent tree node that was generated during the previous tree level, wherein the split function provides best reduction in impurity for the data subsets.

More optionally, regression analysis and statistics maintenance are performed for the left child tree node and the right tree node child for each tree level iteration.

More optionally, each of the tree nodes holds a range of indices of the training data samples that traversed through it in consecutive ascending order of the trajectories of the data samples.

More optionally, each data subset is processed through a plurality of work iterations, during each of the work iterations, histogram generation and impurity computation are performed for a partial range of the tree nodes of the current tree level to fit within pre-assigned processing and memory limitations.

More optionally, binary search through the range of each tree node is performed to identify the trajectory of each of the training data samples through the plurality of tree nodes, during each of the work iterations.

More optionally, a tag is assigned to each training data sample to identify the tree nodes through which each of the training data samples traversed through during the plurality of iterations.

According to some embodiments of the present invention, there are provided systems for training a randomized decision tree. The training system comprises of a plurality of slave processing units and a distributed processing control unit which controls training of a randomized decision tree through a plurality of tree level iterations. During each of the tree level iterations the randomized decision tree is expanded with another tree level in breadth first order. During each tree level iteration the distributed processing control unit receives a plurality of training data samples, splits the training data samples into a plurality of data subsets and distributes the data subsets to the slave processing units. Each of the slave processing units processes a respective received data subset, identifies a split function for one or more tree nodes of the current tree level and transfers the results back to the distributed processing control unit.

Optionally, the slave processing units are local processing units that share processing and memory resources with the distributed processing control unit.

More optionally, one or more of the said slave processing units is a GPU.

More optionally, the system includes one or more remote clusters. Each of the remote clusters includes one or more slave processing unit and a remote distributed processing control unit, communicating with the distributed processing control unit over a plurality of networks.

More optionally, the system is a minimal configuration system and includes a single distributed processing control unit hosting one or more local GPUs. The one or more GPU slave processing units are sufficient for performing histogram generation and impurity computation for the one or more tree nodes.

Unless otherwise defined, all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the invention pertains. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments of the invention, exemplary methods and/or materials are described below. In case of conflict, the patent specification, including definitions, will control. In addition, the materials, methods, and examples are illustrative only and are not intended to be necessarily limiting.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

Some embodiments of the invention are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments of the invention. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments of the invention may be practiced.

In the drawings:

<figref idref="DRAWINGS">FIG. 1</figref> is a schematic illustration of an exemplary system for training a randomized decision tree, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 2</figref> is a schematic illustration of an exemplary training system executing optional modules that control and perform the randomized decision tree training, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 3</figref> is a schematic illustration of an exemplary process of training a randomized decision tree, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 4</figref> is a flowchart describing the execution flow of an exemplary managing module, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 5</figref> is a flowchart describing the execution flow of an exemplary loading module, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 6</figref> is a flowchart describing the execution flow of an exemplary work module, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 7</figref> which is a schematic illustration of training a randomized decision tree using an exemplary minimal configuration training system, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 8</figref> is a schematic illustration demonstrating update of exemplary forward and reverse indices, according to some embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 9</figref> is a schematic illustration demonstrating construction of an exemplary randomized decision tree and reorder of exemplary training data using forward and reverse indices, according to some embodiments of the present invention; and

<figref idref="DRAWINGS">FIG. 10</figref> is a schematic illustration of an exemplary system for training a randomized decision tree ensemble, according to some embodiments of the present invention.

DETAILED DESCRIPTION

According to some embodiments of the present invention, there are provided systems and methods for a randomized decision tree ensemble training system. The randomized decision tree training system includes a distributed processing control unit (physical or logical) that receives training data samples and splits the training data samples into a plurality of data subsets that may be distributed to a plurality of slave processing units (physical or logical), for example, CPU, where each CPU may be single-core or multi-core, GPU and clusters of processing nodes.

Training is performed in breadth first order through a plurality of iterations, each iteration expands the randomized decision tree by another level. Each of the data subsets is a data array that relates to one of a plurality of attributes of the training data samples. The plurality of data subset may be simultaneously processed by the plurality of slave processing units to identify the best split function for each of the tree nodes of the current tree level with respect to each of the data subsets. The plurality of split functions that are identified by the plurality of slave processing units with respect to the plurality of data subsets are aggregated to identify the optimal split function with respect to all data subsets for each of the tree nodes of the current tree level. The optimal split function may be the split function that provides the best reduction in impurity for a specific tree node. Tree level iterations are performed until a completion criterion is satisfied and the complete tree is created and outputted by the distributed processing control unit.

Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not necessarily limited in its application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples. The invention is capable of other embodiments or of being practiced or carried out in various ways.

As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.

A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

Reference is now made to <figref idref="DRAWINGS">FIG. 1</figref> which is a schematic illustration of an exemplary system for training a randomized decision trees, according to some embodiments of the present invention. A training system <b>100</b> may include a plurality of processing units, for example, one or more single-core/multi-core CPU processor units <b>101</b> each containing one or more processing cores <b>105</b>, GPU units <b>102</b> and/or remote clusters of processing units <b>103</b>. A distributed processing control unit <b>104</b> controls the training of the randomized decision tree and coordinates the training process that may be distributed over the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and <b>105</b>. A remote cluster is a collection of processing units not sharing local resources, for example local memory and/or storage media with the distributed processing control unit <b>104</b>.

During the training process, data transfer between the distributed processing control unit <b>104</b> and the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and <b>105</b> is done through a plurality of interconnecting fabrics and networks. Data transfer between the distributed processing control unit <b>104</b> and other cores <b>105</b> integrated in the processing unit <b>101</b> hosting the distributed processing control unit <b>104</b> may be done over plurality of interconnecting fabrics <b>106</b>, for example, QuickPath. Data transfer between the distributed processing control unit <b>104</b> and other processing units <b>101</b> may be done over plurality of interconnecting fabrics <b>107</b>, for example, HyperTransport and/or PCI Express. Data transfer between the master core processing unit <b>104</b> and GPU units <b>102</b> may be done over plurality of interconnecting fabrics <b>108</b>, for example, PCI Express and/or InfiniBand. The distributed processing control unit <b>104</b> communicates with one or more local distributed processing control units <b>110</b> in a remote cluster <b>103</b> over a plurality of networks <b>109</b> for example, Ethernet. The distributed processing control unit <b>104</b> and the plurality of slave processing units have supporting local memory implemented through a plurality of technologies, for example RAM (Random Access Memory) for temporal processing products storage. The distributed processing control unit <b>104</b> has access to storage media implemented through a plurality of technologies, for example, Flash drives, magnetic disks and/or remote database available over a network. Storage media is used for storing and/or retrieving data required for building the randomized decision tree, storing and/or retrieving temporal processing products and storing final randomized decision tree structure information.

Optionally, training system <b>100</b> includes one or more single-core and/or multi-core CPU slave processing units <b>101</b> each containing one or more processing cores <b>105</b> where the distributed processing control unit <b>104</b> provides training data to slave processing units through a pointer to the data in the local memory shared between the distributed processing control unit <b>104</b> and CPU processing units <b>101</b> and/or integrated processing cores <b>105</b>.

Optionally, training system <b>100</b> includes one or more GPU slave processing units <b>102</b> where the entire randomized decision tree is uploaded to the GPU processing unit <b>102</b> own local memory.

Optionally, training system <b>100</b> includes one or more remote clusters <b>103</b>. Remote cluster is a cluster which does not share local onboard resources, for example local memory with the distributed processing control unit <b>104</b>. In training system <b>100</b> that includes remote clusters, the distributed processing control unit <b>104</b> controls one or more local distributed processing control units <b>110</b> at the cluster <b>103</b>. The local distributed processing control units <b>110</b> at the cluster <b>103</b> may control a plurality of slave processing units <b>101</b>, <b>102</b> and/or <b>105</b> which are included in cluster <b>103</b>.

Optionally, the local distributed processing control unit <b>110</b> in cluster <b>103</b> may have access to storage media. In case storage media is not be available to local distributed processing control units <b>110</b> in one or more clusters <b>103</b>, the distributed processing control unit <b>104</b> transfers training data samples to the local distributed processing control units <b>110</b> in cluster <b>103</b>.

Reference is now made to <figref idref="DRAWINGS">FIG. 2</figref> which is a schematic illustration of an exemplary training system executing optional modules that control and perform the randomized decision tree training, according to some embodiments of the present invention. A managing module <b>200</b> that is executed on the distributed processing control unit <b>104</b> controls the randomized decision tree training. The managing module receives the training data samples from a loading module <b>201</b> that is executed on the distributed processing control unit <b>104</b>. The managing module <b>200</b> splits the training data samples to a plurality of data subsets and distributes the data subsets to a plurality of work modules <b>202</b> that are executed on the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>.

Reference is now made to <figref idref="DRAWINGS">FIG. 3</figref> which is a schematic illustration of an exemplary process of training a randomized decision tree, according to some embodiments of the present invention. A process <b>300</b> for training a randomized decision tree is controlled by the managing module <b>200</b> that is executed on the distributed processing control unit <b>104</b>. The randomized decision tree is constructed through one or more iterations in breadth first order, where each tree level iteration <b>310</b> expands the randomized decision tree by another level starting from tree root and moving down to next level until reaching tree leaves (bottom most tree nodes). During each tree level iteration the managing module <b>200</b> receives training data through a loading module <b>201</b>, splits it into a plurality of data subsets and distributes the data subsets to a plurality of work modules <b>202</b> executed on the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>. The work modules <b>202</b> process their assigned data subset and select an optimal split function for each tree node of the current tree level iteration <b>310</b>. Optimal split function is the split function that provides the best reduction in impurity for the training data samples with respect to the processed data subset. The managing module <b>200</b> collects split functions from all work modules <b>202</b> and sets the optimal split function, for each tree node of the current tree level iteration <b>310</b>. The tree level iterations <b>310</b> are repeated until tree bottom is reached and the managing module <b>200</b> outputs the complete randomized decision tree and exits.

As shown at <b>301</b>, the managing module <b>200</b> initializes the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b> that are present in training system <b>100</b>. The managing module then enters the phase of tree level iterations <b>310</b>.

As shown at <b>311</b>, the managing module <b>200</b> broadcasts the map of the randomized decision tree to the slave processing units <b>101</b>, <b>102</b>, <b>103</b> and <b>105</b> to inform the slave processing units <b>101</b>, <b>102</b>, <b>103</b> and <b>105</b> of the structure of the randomized decision tree, i.e. the tree nodes each of the training data samples traversed through during the previous iteration.

As shown at <b>312</b>, the managing unit <b>200</b> receives training data samples using a loading module <b>201</b>. Training data samples comprises a plurality of data subsets, each data subset is an array that corresponds to one of a plurality of attributes of the training data samples. Each data subset holds a value for each of the training sample that represents the sample's value with respect to the corresponding attribute. In addition training each data sample includes a class label. After completion of the randomized decision tree training, the class labels are used by the randomized decision tree for classifying the incoming data according to its attributes and prediction of the path the incoming data traverses through the randomized decision tree. The training data samples are assigned with indices through which training data synchronization is maintained throughout the randomized decision tree training. The same index is maintained for the training data samples of all data subsets.

As shown at <b>313</b>, the managing module <b>200</b> distributes the plurality of data subsets to the plurality of work modules <b>202</b> executed on the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>.

Shown at <b>314</b>, is the process performed by one of the plurality of work modules <b>202</b> executed on the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>. The work module <b>202</b> processes one or more data subsets it receives from the managing module <b>200</b> and generates histograms to set the optimal split function for each tree node of current tree level iteration <b>310</b> per data subset. In the event a split function computed for a specific data subset provides better reduction in impurity than data subsets previously processed on the same slave processing unit <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>, the tree node for which the better split function was identified is marked with a flag to indicate the tree node was updated. The work module <b>202</b> updates the training data samples reverse index for the updated tree nodes after sorting them in increasing order according to the tree nodes the training data samples traversed through in current tree level iteration <b>310</b>. After completion of processing by the work modules <b>202</b>, each tree node holds the range of indices of training data samples that traversed through it.

As shown at <b>315</b>, the managing module <b>200</b> collects tree nodes information from the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>. The managing module <b>200</b> collects split functions only for tree nodes that were updated by the work modules <b>202</b> at the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>. Updated tree nodes are tree nodes for which an optimal split function was set that provides better reduction in impurity for the tree node then previously generated split functions. The managing module <b>200</b> selects the optimal split function out of the all split functions that were created by work modules <b>202</b> executed on the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>.

As shown in <b>316</b>, after the optimal split function is selected for each tree node of the current tree level iteration <b>310</b>, the managing module <b>200</b> updates the forward index of the training data samples that will be used for the next tree level iteration <b>310</b> to reflect the reverse index of the training data samples according to the tree nodes the training data samples traversed through during the current tree level iteration <b>310</b>.

As shown in <b>320</b> which is a decision point, the managing module <b>200</b> checks if one of a plurality of randomized decision tree training completion criterion is satisfied. The completion criterion may be, for example, a pre-defined maximum randomized decision tree depth, inability of another tree level to improve reduction in impurity and/or pre-defined minimum number of values that traverses through each tree node to maintain statistical value. In case training completion criterion is not satisfied, the managing module <b>200</b> branches to <b>311</b> to continue the training process and another tree level iteration <b>310</b> is started to generate another randomized decision tree level.

As shown in <b>302</b>, in case training completion criterion is satisfied, the managing module <b>200</b> branches out to complete the training process <b>300</b> by outputting a complete randomized decision tree.

Reference is now made to <figref idref="DRAWINGS">FIG. 4</figref> which is a flowchart describing the execution flow of an exemplary managing module, according to some embodiments of the present invention. The managing module <b>200</b> executed on the distributed processing control unit <b>104</b> first initializes the plurality of slave processing units available in training system <b>100</b>. The managing unit creates training data arrays where each data sample is associated with a class label and 2 flags used for identifying which training data samples arrays were updated during the training process. The managing module <b>200</b> also creates a tree nodes structure that holds the information for the tree nodes that is generated during training. The managing module <b>200</b> then initiates the loading module <b>201</b> for loading a plurality of training data samples arrays. Each training data array is associated with a data subset and is transferred to one of a plurality of work modules <b>202</b> executed on the plurality of slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b> using forward index. Training is performed in a plurality of iterations <b>310</b> in breadth first order, during each tree level iteration <b>310</b> all tree nodes are created for the current tree level of the randomized decision tree before proceeding to a lower level. During a tree level iteration <b>310</b> the managing module <b>200</b> identifies a free work module <b>202</b> and assigns it with a data subset. The data subset is processed by the assigned work module <b>202</b> for all tree nodes of the tree level iteration <b>310</b>. The sequence is repeated until all data subsets have been processed. The managing module <b>200</b> waits for all work modules <b>202</b> to process all data subsets for the current tree level iteration <b>310</b>. When all work modules <b>202</b> are done, the managing module <b>200</b> reads back the updated reverse index for the updated tree nodes from their respective work modules <b>202</b>. After all tree nodes information is received from all work modules <b>202</b>, the managing module <b>200</b> determines the optimal split function (Attribute, Threshold) for every tree node of current tree level and updates training data samples forward index to be equal to the reverse index received from the work modules <b>202</b>. The managing module <b>200</b> performs a plurality of iterations <b>310</b> to create additional levels of the randomized decision tree until a pre-defined randomized decision tree depth level is reached. After reaching the pre-defined randomized decision tree level depth, the managing module <b>200</b> stores the randomized decision tree structure and tree nodes information and exits.

Reference is now made to <figref idref="DRAWINGS">FIG. 5</figref> which is a flowchart describing the execution flow of an exemplary loading module, according to some embodiments of the present invention. The loading module <b>201</b> first checks a load enable flag which is set by the managing module <b>200</b> when loading training data samples for the current tree level is needed. In case load enable flag is set, the loading module <b>201</b> looks for an available free memory slot, i.e. a memory space not occupied by training data samples array currently in use by one of the work modules. Once a free slot is available, the loading module <b>201</b> initiates a thread to load the required training data array to memory. The loading operation is repeated until all F training data samples arrays associated have loaded to memory and their respective threads have completed operation. After all data subsets arrays completed loading, the managing module <b>200</b> clears the load enable flag and the loading module <b>201</b> exits.

Optionally, in training system <b>100</b> that comprises a plurality of clusters <b>103</b>, the local distributed processing control unit <b>110</b> in each cluster <b>103</b> initiates its own loading module <b>201</b>. The master processing node <b>104</b> communicates with the local distributed processing control units <b>110</b> in each cluster <b>103</b> and coordinates the loading of training data samples in the remote clusters <b>103</b>. The loading module <b>201</b> executed on the local distributed processing control units <b>110</b> performs the same operations as the loading module <b>201</b> that is executed on the distributed processing control unit <b>104</b>.

Reference is now made to <figref idref="DRAWINGS">FIG. 6</figref> which is a flowchart describing the execution flow of an exemplary work module, according to some embodiments of the present invention. The work module <b>202</b> executed on a slave processing module <b>101</b>, <b>102</b>, <b>103</b> or <b>105</b> receives one or more data subsets from the managing module <b>200</b>. The work module <b>202</b> performs a quick probe of the received training data samples of the data subset and decides which method to use for generating histograms to identify current tree level iteration <b>310</b> tree nodes' split functions. During system initialization, every work module <b>202</b> is pre-assigned a fixed amount of processing and memory resources on the slave processing unit <b>101</b>, <b>102</b>, <b>103</b> or <b>105</b> the work module <b>202</b> is executed on. As the training process employs breadth first method, for tree level d there are 2^dtree nodes. Since tree nodes number increases exponentially for every tree level iteration <b>310</b>, it is possible that the fixed amount of processing and memory resources assigned to the work module <b>202</b> may be insufficient for processing the complete data subset for all current tree level iteration <b>310</b> tree nodes. To overcome this, calculation and histogram generation may be performed by the work module <b>202</b> in one or more work iterations. During each work iteration, training data samples are processed for subsets of the tree nodes and results are saved in memory. The number of tree nodes that are processed during each work iteration is expressed in the value delta which represents the overall tree nodes that are to be processed at current tree level iteration <b>310</b> divided by the number of tree nodes that may be processed using the fixed processing and memory resources allocated to the work module <b>202</b>. The data subset that arrives from the managing module <b>200</b> is sorted in increasing order using forward index correlating to the path of the training data samples through the tree nodes of the previous tree level iteration <b>310</b> enabling processing in each work iteration to be done linearly on tree nodes j through j+delta−1, with j starting at 0 and increased by delta for every work iteration. For every tree node a histogram is generated for one or more Threshold values available from a Threshold array. In case the current split function provides better gain in impurity, then tree node is updated to reflect the optimal split function. This operation is repeated for all Threshold values available in the Threshold array (numThresh). After all work modules <b>202</b> allocated to a specific slave processing unit <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b> have completed execution, the optimal split function is selected out of the split functions generated by all work modules <b>202</b> that are executed on the specific processing unit <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b>. For the selected split function the slave processing unit <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b> updates the reverse index of the training data samples according to tree nodes they traversed through right or left branches and transmits the updated information back to the managing module <b>200</b>.

According to some embodiments of the present invention, there are provided systems and methods for training a randomized decision tree using large sets of training data samples in a minimal configuration training system and more specifically, but not exclusively to a minimal configuration training system comprising a single CPU and at least one GPU. Using the forward and reverse indices as described herein reduces the need for the slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b> to maintain information with respect to previous tree levels as the required information for processing the current tree level is available from the distributed processing control unit <b>104</b> at the beginning of each tree level iteration <b>310</b>. Avoiding the need to store previously generated information allows the slave processing units <b>101</b>, <b>102</b>, <b>103</b> and/or <b>105</b> to use most of their memory resources for the current tree level processing. Moreover, as the process <b>300</b> supports multiple work iterations for processing multiple tree nodes during a specific tree level iteration <b>310</b>, the minimal configuration system is fully capable of training the randomized decision tree in an efficient and time saving manner.

Reference is now made to <figref idref="DRAWINGS">FIG. 7</figref>, which is a schematic illustration of training a randomized decision tree using an exemplary minimal configuration training system, according to some embodiments of the present invention. An exemplary training system <b>100</b> includes a distributed processing control unit <b>104</b> CPU and two GPU <b>102</b> slave processing units GPU_0 and GPU_1. The managing module <b>200</b> and loading module <b>201</b> are executed on the distributed processing control unit <b>104</b> while two work modules <b>202</b> are executed, each work module <b>202</b> is executed on a respective GPU <b>102</b>, GPU_0 and GPU_1. Training data samples include F data subset arrays, each data subset associated with one of F attributes of the training data samples. Each data subset array contains S data values corresponding to S training data samples. Two data subsets array 20 and array 21 are currently loaded and processed, arrays 20 processed by the work module <b>202</b> executed on GPU_0 and arrays 21 processed by the work module <b>202</b> executed on GPU_1. The arrays 0 through 19 are already processed by work modules <b>202</b> and are stored back in storage media, for example a disk drive. The arrays 22 through 21+poolsize are queued to be executed next and are already loaded to the local memory of distributed processing control unit <b>104</b> CPU. Preloading the arrays 22 through 21+poolsize to be processed next reduces the latency for waiting for the arrays to be fetched from the relatively slow storage device. Optionally, additional arrays are loaded to local memory within local memory capacity limitations where poolsize designates the local memory capacity available for loading arrays. The arrays 22+poolsize through F−1 that are to be processed at a later stage are not loaded to local memory at this time due to local memory capacity limitations. The arrays 22+poolsize through F−1 are located in storage media and are loaded at a later time when one or more of arrays 22 through 21+poolsize is processed and downloaded from local memory back to storage media.

According to some embodiments of the present invention, there are provided systems and methods for transferring data subsets training data samples between the distributed processing control unit <b>104</b> and the plurality of slave processing units <b>101</b>, <b>102</b> and/or <b>105</b> by mapping them in local memory using forward and reverse indices. Mapping a data subset training data samples in memory using forward and reverse indices reduces the need to reload entire data subset training data samples arrays to local memory by the distributed processing control unit <b>104</b> and slave processing units <b>101</b>, <b>102</b> and/or <b>105</b>. Data subsets training data samples are shared in local memory between the distributed processing control unit <b>104</b> and the plurality of slave processing units <b>101</b>, <b>102</b> and/or <b>105</b> and only the data subset training data forward and reverse indices are updated.

Reference is now made to <figref idref="DRAWINGS">FIG. 8</figref> which is a schematic illustration demonstrating update of exemplary forward and reverse indices, according to some embodiments of the present invention. Training data samples reference location is expressed in <b>800</b>. At the beginning of tree level iteration <b>310</b>, the managing module <b>200</b> sends training data samples <b>801</b> to the work modules <b>202</b> after updating the forward index <b>802</b> to reflect the order of the training data samples <b>801</b> as they traversed through the tree nodes during the previous tree level iteration <b>310</b>. Each of the work modules <b>202</b> processes its respective data subset training data samples <b>801</b> and sorts the training data samples <b>801</b> according to their trajectory through the tree nodes of the current tree level iteration <b>310</b>. To maintain synchronization with the actual training data samples <b>801</b>, the work module <b>202</b> updates the reveres index <b>803</b> to inform the managing module <b>200</b> of the relation between the actual training data samples and the way they are sorted by the work module <b>202</b>. At the beginning of the training process <b>300</b>, for the first tree level iteration, the forward index reflects the order in which training data samples are loaded from mass storage media.

Reference is now made to <figref idref="DRAWINGS">FIG. 9</figref> which is a schematic illustration demonstrating construction of an exemplary randomized decision tree and reorder of exemplary training data using forward and reverse indices, according to some embodiments of the present invention. At tree level DEPTH_0 the work module <b>202</b> updates a reverse index <b>910</b> of the training data samples <b>900</b> to identify the trajectory of the data samples <b>900</b> through a tree node NODE_0. The managing module <b>200</b> sorts the training data samples <b>900</b> according to the reverse index <b>901</b> as presented at <b>910</b> to reflect how the data samples <b>900</b> traversed through the tree node NODE_0. At tree level DEPTH_1 the work module <b>202</b> updates a reverse index <b>902</b> of the training data samples <b>900</b> to identify the trajectory of the data samples <b>900</b> through tree nodes NODE_1 and NODE_2. The managing module <b>200</b> sorts the training data samples <b>900</b> according to the reverse index <b>902</b> as presented at <b>911</b> to reflect how the data samples <b>900</b> traversed through the tree nodes NODE_1 and NODE_2. At tree level DEPTH_2 the work module <b>202</b> updates a reverse index <b>903</b> of the training data samples <b>900</b> to identify the trajectory of the data samples <b>900</b> through tree nodes NODE_3, NODE_4, NODE_5 and NODE_6. The managing module <b>200</b> sorts the training data samples <b>900</b> according to the reverse index <b>903</b> as presented at <b>912</b> to reflect how the data samples <b>900</b> traversed through the tree nodes NODE_1 and NODE_2. Using the updated forward and reverse indices allows the managing module <b>200</b> and the work module <b>202</b> to maintain synchronization of the training data samples <b>900</b> that is transferred when storing the results of previous tree level iterations <b>310</b>, thus reducing the amount of memory that is required by each of the plurality of work modules <b>202</b>. Furthermore, as the training data samples <b>900</b> is sorted according to the path they traversed through the tree levels, a simple binary search identifies the binary borders between tree nodes at each tree level iteration <b>310</b> with respect to the training data samples that went through each of the tree nodes.

According to some embodiments of the present invention, there are provided systems and methods for a identifying the tree node each training data sample propagated through at every randomized decision tree level, through a plurality of methods, for example, assigning a tag to every training data sample at every randomized decision tree level. Assigning a tag to every training data sample allows the managing module <b>200</b> to indicate to the work modules <b>202</b> which tree node in previous tree level each training data sample propagated through. This method may require high local memory capacity to store tags for every training data sample, specifically for deep randomized decision trees.

Optionally, where memory capacity does not allow for saving a tag to every training data sample, at the end of a tree level iteration, the managing module <b>200</b> performs a binary search through the tree nodes of all previous tree levels. Since the training data samples are eventually (at the end of the training) sorted in increasing order according to the tree nodes they went through, each tree node holds the range of training data samples that went through it. With this method less local memory is required but it may prolong the training process.

More optionally, the training process of a single randomized decision tree may be repeated to form a randomized decision tree ensemble.

Reference is now made to <figref idref="DRAWINGS">FIG. 10</figref> which is a schematic illustration of an exemplary system for training a randomized decision tree ensemble, according to some embodiments of the present invention. The process <b>300</b> for training a single randomized decision tree <b>1001</b> may be repeated to create an ensemble of randomized decision tree <b>1000</b>.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

It is expected that during the life of a patent maturing from this application many relevant systems, methods and computer programs will be developed and the scope of the term sales information and price is intended to include all such new technologies a priori.

As used herein the term “about” refers to ±10%.

The terms “comprises”, “comprising”, “includes”, “including”, “having” and their conjugates mean “including but not limited to”. This term encompasses the terms “consisting of” and “consisting essentially of”.

The phrase “consisting essentially of” means that the composition or method may include additional ingredients and/or steps, but only if the additional ingredients and/or steps do not materially alter the basic and novel characteristics of the claimed composition or method.

As used herein, the singular form “a”, “an” and “the” include plural references unless the context clearly dictates otherwise. For example, the term “a compound” or “at least one compound” may include a plurality of compounds, including mixtures thereof.

The word “exemplary” is used herein to mean “serving as an example, instance or illustration”. Any embodiment described as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments and/or to exclude the incorporation of features from other embodiments.

The word “optionally” is used herein to mean “is provided in some embodiments and not provided in other embodiments”. Any particular embodiment of the invention may include a plurality of “optional” features unless such features conflict.

Throughout this application, various embodiments of this invention may be presented in a range format. It should be understood that the description in range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of the invention. Accordingly, the description of a range should be considered to have specifically disclosed all the possible subranges as well as individual numerical values within that range. For example, description of a range such as from 1 to 6 should be considered to have specifically disclosed subranges such as from 1 to 3, from 1 to 4, from 1 to 5, from 2 to 4, from 2 to 6, from 3 to 6 etc., as well as individual numbers within that range, for example, 1, 2, 3, 4, 5, and 6. This applies regardless of the breadth of the range.

Whenever a numerical range is indicated herein, it is meant to include any cited numeral (fractional or integral) within the indicated range. The phrases “ranging/ranges between” a first indicate number and a second indicate number and “ranging/ranges from” a first indicate number “to” a second indicate number are used herein interchangeably and are meant to include the first and second indicated numbers and all the fractional and integral numerals there between.

It is appreciated that certain features of the invention, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the invention, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable subcombination or as suitable in any other described embodiment of the invention. Certain features described in the context of various embodiments are not to be considered essential features of those embodiments, unless the embodiment is inoperative without those elements.

Although the invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, it is intended to embrace all such alternatives, modifications and variations that fall within the spirit and broad scope of the appended claims.

All publications, patents and patent applications mentioned in this specification are herein incorporated in their entirety by reference into the specification, to the same extent as if each individual publication, patent or patent application was specifically and individually indicated to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention. To the extent that section headings are used, they should not be construed as necessarily limiting.