Methods, processing engines, and microprocessors for classifying data according to decision trees

Patent metadata

Field	Value
Publication number	US-10726345-B2
Application number	US-201815878888-A
Country	US
Kind code	B2
Filing date	Jan 24, 2018
Priority date	Jun 28, 2017
Publication date	Jul 28, 2020
Grant date	Jul 28, 2020

Abstract

A processing engine for classifying data according to a decision tree having n-nodes is disclosed, wherein each node is represented by a respective test according to which a flag may be set or unset, comprising: a respective test unit and corresponding to each node, having an output flag and being configured to set or unset the respective output flag according to an output of the respective test; a memory configured to hold an n-bit word, each bit corresponding to a one of the respective output flags; and a data-structure configured as a look up table, each entry of the look up table representing a class of the data. Corresponding methods are also disclosed, as are devices and systems incorporating such processing engines.

First claim

The invention claimed is:

1. A processing engine for classifying data according to a decision tree having n-nodes, wherein each node is represented by a respective test according to which a flag may be set or unset, comprising:
a respective test unit circuit corresponding to each node, having an output flag and being configured to set or unset the respective output flag according to an output of the respective test;
a memory device configured to hold an n-bit word, each bit corresponding to a one of the respective output flags;
a data-structure configured as a look up table, each entry of the look up table representing a class of the data; and
a response unit circuit configured to, in response a classification determined by the processing engine, provide at least one of: an output indicative of a suggested vehicle driver response, and a vehicle response.

2. A processing engine according to claim 1 , wherein the look up table has 2^n entries.

3. A processing engine according to claim 1 , wherein the test unit circuits are distributed across a plurality of processing elements.

4. A processing engine according to claim 1 , wherein the test unit circuits are distributed across at least one of: a plurality of microprocessors, and a plurality of cores of a microprocessor.

5. A processing engine according to claim 1 , wherein the decision tree has no sub-branches.

6. A processing engine according to claim 1 , wherein the decision tree includes at least one sub-branch.

7. An object recognition unit including a processing engine as claimed in claim 1 , and at least one surveillance device.

8. A machine learning device comprising a processing engine as claimed in claim 1 , and a learning unit configured to modify a part of the look up table.

9. A method of classifying data according to a decision tree having n-nodes, wherein each node is represented by a respective test according to which a respective flag may be set or unset, the method comprising:
setting or unsetting each flag by performing the respective test on the data;
constructing an n-bit word, each bit corresponding to a one of the n flags;
using a predetermined look up table to classify the data according to an entry in the look up table corresponding to the n-bit word; and
in response to a classification of the data, providing at least one of: an output indicative of a suggested vehicle driver response, and a vehicle response.

10. A method according to claim 9 , wherein the tests are distributed across a plurality of processing engines.

11. A method according to claim 10 , wherein the plurality of processing engines comprises at least one of: a plurality of microprocessors, and a plurality of cores of a microprocessor.

12. A method according to claim 9 , wherein the decision tree has no sub-branches.

13. A method according to claim 9 , wherein an i-th test, (T_i) on the data (R) takes the form:
( F ( R,i )> ai ).

14. A method according to claim 12 , wherein an i-th bit of the n-bit word is determined according to a computation:
T _ i =sign F ( R,i )− ai )<< i.

Assignees

• Nxp Usa Inc

Inventors

• Krutsch Robert
• Staudenmaier Michael
• Herrmann Stephan

Classifications

• G06N5/045 Primary

  Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence · CPC title

• G06V10/764

  using classification, e.g. of video objects · CPC title

• G06N20/00 Primary

  Machine learning · CPC title

• G06F18/24323

  Tree-organised classifiers · CPC title

• G06V10/955

  using specific electronic processors · CPC title