# US 2021/0334667 A1 · Optimizing gradient boosting feature selection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0334667 A1
- Document ID: US20210334667A1
- Status: Published application
- Kind: A1
- Application number: 16/858,143
- Filed: 2020-04-24
- Published: 2021-10-28
- Earliest claimed: 2020-04-24
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Jacques Doan Huu
- Web page: https://patentgrep.com/patent/US20210334667A1

## CPC

- G06N 5/02: Knowledge representation; Symbolic representation
- G06N 20/20: Ensemble learning
- G06F 16/2228: {Indexing structures}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Gradient Boosting Decision Tree (GBDT) successively stacks many decision trees which at each step try to fix the residual errors from the previous steps. The final score produced by the GBDT is the sum of the individual scores obtained by the decision trees for an input vector. Overfitting in GBDT can be reduced by removing the input values that have the least impact on the output from the training data. One way to determine which input variable has the lowest predictive value is to determine the input variable that is used for the first time in the latest decision tree in the GBDT. This method of identifying the low-predictive features to be removed does not require that earlier trees be regenerated to generate the new GBDT. Since the removed feature was already not used in the earlier trees, those trees already ignore the removed feature.

## Claims

### Claim 1

A method comprising:
generating, by one or more processors, a first decision tree for partitioning a feature space, the first decision tree using a first set of features, the first set of features being a first subset of an available set of features;
generating, by the one or more processors, a second decision tree that refines the first decision tree to improve the partitioning of the feature space, the second decision tree using zero or more features of the first set of features and a second set of features not included in the first set of features, the second set of features being a second subset of the available set of features;
storing, in a database, first data that associates the first decision tree with the first set of features;
storing, in the database, second data that associates the second decision tree with the second set of features;
removing a feature of the second set of features from the available set of features; and
based on the second data associating the second decision tree with the second set of features comprising the removed feature, generating a third decision tree that refines the first decision tree to improve the partitioning of the feature space, the third decision tree not using the removed feature.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
generating, by the one or more processors, a fourth decision tree that refines the first decision tree and the second decision tree to improve the partitioning of the feature space, the fourth decision tree using zero or more features of the first set of features, zero or more features of the second set of features, and a third set of features not included in the first set of features or the second set of features, the third set of features being a third subset of the available set of features;
storing, in the database, third data that associates the fourth decision tree with the third set of features; and
based on the third data associating the fourth decision tree with the third set of features not comprising the removed feature, determining, using the second data, that the removed feature is in the second set of features.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
determining a quality difference between a first model comprising the first decision tree and the second decision tree and a second model comprising the first decision tree and the third decision tree; and
based on the quality difference and a predetermined threshold, using the first model to partition the feature space.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
determining a first quality for the first model based on a validation dataset;
determining a second quality for the second model based on the validation dataset; and wherein
the determining of the quality difference is based on the first quality and the second quality.

### Claim 5 (depends on 3)

The method of claim 3, wherein the determining of the quality difference between the first model and the second model comprises:
determining a quality of the first model by determining a first error measure for the first decision tree and a second error measure for the second decision tree;
storing, in the database, the first error measure; and
determining a quality of the second model by accessing the stored first error measure for the first decision tree and determining a third error measure for the third decision tree.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
determining a quality difference between a first model comprising the first decision tree and the second decision tree and a second model comprising the first decision tree and the third decision tree; and
based on the quality difference and a predetermined threshold, removing a second feature from the available set of features.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
determining a first quality for the first decision tree based on a validation dataset;
determining a second quality for the first decision tree in conjunction with the second decision tree based on the validation dataset;
storing, in the database, third data associating the first quality with the first decision tree; and
storing, in the database, fourth data associating the second quality with the second decision tree.

### Claim 8

A system comprising:
a memory that stores instructions; and
one or more processors configured by the instructions to perform operations comprising:
generating a first decision tree for partitioning a feature space, the first decision tree using a first set of features, the first set of features being a first subset of an available set of features;
generating a second decision tree that refines the first decision tree to improve the partitioning of the feature space, the second decision tree using zero or more features of the first set of features and a second set of features not included in the first set of features, the second set of features being a second subset of the available set of features;
storing, in a database, first data that associates the first decision tree with the first set of features;
storing, in the database, second data that associates the second decision tree with the second set of features;
removing a feature of the second set of features from the available set of features; and
based on the second data associating the second decision tree with the second set of features comprising the removed feature, generating a third decision tree that refines the first decision tree to improve the partitioning of the feature space, the third decision tree not using the removed feature.

### Claim 9 (depends on 8)

The system of claim 8, wherein the operations further comprise:
generating a fourth decision tree that refines the first decision tree and the second decision tree to improve the partitioning of the feature space, the fourth decision tree using zero or more features of the first set of features, zero or more features of the second set of features, and a third set of features not included in the first set of features or the second set of features, the third set of features being a third subset of the available set of features;
storing, in the database, third data that associates the fourth decision tree with the third set of features; and
based on the third data associating the fourth decision tree with the third set of features not comprising the removed feature, determining, using the second data, that the removed feature is in the second set of features.

### Claim 10 (depends on 8)

The system of claim 8, wherein the operations further comprise:
determining a quality difference between a first model comprising the first decision tree and the second decision tree and a second model comprising the first decision tree and the third decision tree; and
based on the quality difference and a predetermined threshold, using the first model to partition the feature space.

### Claim 11 (depends on 10)

The system of claim 10, wherein the operations further comprise:
determining a first quality for the first model based on a validation dataset;
determining a second quality for the second model based on the validation dataset; and wherein
the determining of the quality difference is based on the first quality and the second quality.

### Claim 12 (depends on 10)

The system of claim 10, wherein the determining of the quality difference between the first model and the second model comprises:
determining a quality of the first model by determining a first error measure for the first decision tree and a second error measure for the second decision tree;
storing, in the database, the first error measure; and
determining a quality of the second model by accessing the stored first error measure for the first decision tree and determining a third error measure for the third decision tree.

### Claim 13 (depends on 8)

The system of claim 8, wherein the operations further comprise:
determining a quality difference between a first model comprising the first decision tree and the second decision tree and a second model comprising the first decision tree and the third decision tree; and
based on the quality difference and a predetermined threshold, removing a second feature from the available set of features.

### Claim 14 (depends on 8)

The system of claim 8, wherein the operations further comprise:
determining a first quality for the first decision tree based on a validation dataset;
determining a second quality for the first decision tree in conjunction with the second decision tree based on the validation dataset;
storing, in the database, third data associating the first quality with the first decision tree; and
storing, in the database, fourth data associating the second quality with the second decision tree.

### Claim 15

A non-transitory machine-readable medium that stores instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
generating a first decision tree for partitioning a feature space, the first decision tree using a first set of features, the first set of features being a first subset of an available set of features;
generating a second decision tree that refines the first decision tree to improve the partitioning of the feature space, the second decision tree using zero or more features of the first set of features and a second set of features not included in the first set of features, the second set of features being a second subset of the available set of features;
storing, in a database, first data that associates the first decision tree with the first set of features;
storing, in the database, second data that associates the second decision tree with the second set of features;
removing a feature of the second set of features from the available set of features; and
based on the second data associating the second decision tree with the second set of features comprising the removed feature, generating a third decision tree that refines the first decision tree to improve the partitioning of the feature space, the third decision tree not using the removed feature.

### Claim 16 (depends on 15)

The non-transitory machine-readable medium of claim 15, wherein the operations further comprise:
generating a fourth decision tree that refines the first decision tree and the second decision tree to improve the partitioning of the feature space, the fourth decision tree using zero or more features of the first set of features, zero or more features of the second set of features, and a third set of features not included in the first set of features or the second set of features, the third set of features being a third subset of the available set of features;
storing, in the database, third data that associates the fourth decision tree with the third set of features; and
based on the third data associating the fourth decision tree with the third set of features not comprising the removed feature, determining, using the second data, that the removed feature is in the second set of features.

### Claim 17 (depends on 15)

The non-transitory machine-readable medium of claim 15, wherein the operations further comprise:
determining a quality difference between a first model comprising the first decision tree and the second decision tree and a second model comprising the first decision tree and the third decision tree; and
based on the quality difference and a predetermined threshold, using the first model to partition the feature space.

### Claim 18 (depends on 17)

The non-transitory machine-readable medium of claim 17, wherein the operations further comprise:
determining a first quality for the first model based on a validation dataset;
determining a second quality for the second model based on the validation dataset; and wherein
the determining of the quality difference is based on the first quality and the second quality.

### Claim 19 (depends on 15)

The non-transitory machine-readable medium of claim 15, wherein the operations further comprise:
determining a quality difference between a first model comprising the first decision tree and the second decision tree and a second model comprising the first decision tree and the third decision tree; and
based on the quality difference and a predetermined threshold, removing a second feature from the available set of features.

### Claim 20 (depends on 15)

The non-transitory machine-readable medium of claim 15, wherein the operations further comprise:
determining a first quality for the first decision tree based on a validation dataset;
determining a second quality for the first decision tree in conjunction with the second decision tree based on the validation dataset;
storing, in the database, third data associating the first quality with the first decision tree; and
storing, in the database, fourth data associating the second quality with the second decision tree.