Granted Patent B2

US 12,737,694 · App. 18/001,991 · Granted Sep 15, 2026

Inventors: Jan Kollmitz (Freiburg, DE); Yiannos Manoli (Freiburg, DE); Alexander Bleitner (Freiburg, DE)

Assignee: Albert-Ludwigs-Universitaet Freiburg

G06N20/20

Abstract

Claims (53)

1 . An architecture for classification of a decision tree ensemble, the architecture comprising:

a rank computing block; and

a tree processing block,

wherein the rank computing block comprises one computation unit per feature of a set of features to be classified,

wherein each computation unit comprises a memory and a logic,

wherein the memory is configured to save threshold values of decision trees in the decision tree ensemble,

wherein the memory is configured to save the threshold values in one group per feature,

wherein the threshold values in a group are sorted according to a threshold index,

wherein the logic is configured to conduct a node comparison of the threshold values of a corresponding group of threshold values and output a rank as a result of the comparison, wherein the rank represents an encoded address representative of a threshold value, and

wherein the tree processing block for trees in the decision tree ensemble is configured to determine a class of the features to be classified as a function of ranks.

2 . The architecture according to claim 1 ,

wherein the features are denoted as f i , with feature index i∈[1;I],

wherein I denotes a number of features to be classified, and the threshold values are representative of nodes of trees in the decision tree ensemble,

wherein the logic is configured to receive a feature to be classified and to conduct a search which returns the rank for each feature that splits the threshold values into values less than and greater than a feature value,

wherein the ranks are output to corresponding tree processing units, respectively, and

wherein the tree processing units are configured to determine the classes by evaluating Boolean functions, each being representative of a decision tree in the decision tree ensemble, as a function of the received ranks, respectively.

3 . The architecture according to claim 1 , wherein the tree processing block comprises an aggregation unit which is configured to receive the determined classes from tree processing units and to form an ensemble vote as a function of the determined classes.

4 . The architecture according to claim 1 , wherein the memory comprises one group of memory cells for each feature of the set of features to be classified, and wherein the memory cells within the group are addressable according to the threshold index.

5 . The architecture according to claim 1 ,

wherein the logic comprises a comparator which comprises a first input operable to receive a feature and a second input operable to receive the threshold value from the memory, and wherein the comparator is operable to conduct the node comparison of the threshold values of the corresponding group of threshold values.

6 . The architecture according to claim 5 , further comprising tree processing units comprising one or more comparators which are configured to perform an address decoding of the received ranks to evaluate Boolean functions based on address decoded ranks.

7 . The architecture according to claim 1 ,

wherein each of the computation units is connected to a dedicated lookup table, respectively,

wherein the lookup tables comprise an input side which is operable to receive a dedicated rank from the computation unit, which is connected to the lookup table, and

wherein the lookup tables are operable to output intermediate values as a function of the ranks received at the input side.

8 . The architecture according to claim 7 ,

wherein each of the rank computing blocks is connected to the dedicated lookup table, respectively,

wherein the lookup table comprises an output side which is operable to provide the intermediate values of tree processing units connected to the lookup table, and

wherein the tree processing units are operable to determine the class of the features to be classified as a function of the received intermediate values.

9 . The architecture according to claim 7 , further comprising a combiner with an arithmetic unit, which is operable to receive the intermediate values and is operable to combine and/or weight the intermediate values and to output the class of the features to be classified.

10 . The architecture according to claim 7 ,

wherein the tree processing block comprises one or more lookup tables, and

wherein the lookup tables are implemented based on an associative memory comprising one or more comparators operable to conduct a “less than” or “greater than” comparison.

11 . A method for classification of a decision tree ensemble, the method comprising:

saving threshold values representative of decision trees in the decision tree ensemble into one group per feature to be classified;

sorting the threshold values of a group according to a threshold index;

conducting a node comparison of the threshold values of a corresponding group of threshold values;

outputting a rank as a result of the node comparison, wherein the rank represents an encoded address representative of a threshold value; and

determining a class of the features to be classified as a function of ranks.

12 . The method according to claim 11 ,

wherein the features to be classified are denoted as f i , with feature index i∈[1;I],

wherein I denotes a number of features to be classified, and the threshold values are representative of nodes of trees in the decision tree ensemble,

wherein the method further comprises:

receiving a feature to be classified by a logic and, using the logic, conducting a search which returns the rank for each feature that splits the threshold values into values less and greater than a feature value,

outputting the ranks to corresponding tree processing units, and

determining the classes of the feature to be classified by evaluating Boolean functions, each being representative of a tree in the decision tree ensemble as a function of the received ranks, respectively.

13 . The method according to claim 11 ,

wherein the ranks are determined from a binary search using a logic, or

wherein the ranks are determined from an in-memory process.

14 . The method according to claim 11 ,

wherein an evaluation of the decision trees involves a look-up table with pre-calculated values, which are saved as look-up table entries, and

wherein the classes are determined depending on the look-up table entries.

15 . The method according to claim 14 , wherein the look-up table entries are determined by training software, which determines an assignment of the look-up table entries, such that both a mathematical description of a classification architecture and a mathematical description of the decision tree ensemble are equivalent.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (17)