# US 12,591,817 B2 · Generating rule lists from tree ensemble models > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,591,817 B2 - Document ID: US12591817B2 - Status: Granted - Kind: B2 - Application number: 17/894,629 - Filed: 2022-08-24 - Published: 2024-02-29 - Granted: 2026-03-31 - Earliest claimed: 2022-08-24 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Gopiram Roshan Lal; Varun Mithal; Xiaotong Chen - Web page: https://patentgrep.com/patent/US12591817B2 ## CPC - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06N 20/20: Ensemble learning - G06N 5/025: Extracting rules from data - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract Systems and methods for extracting rule lists from tree ensembles are provided. A system extracts first stage candidate rules from individual trees. The system identifies the first stage candidate rules that satisfy a precision threshold and places those rules in a solution set. Subsequently, a determination is made whether a further stage is needed based on whether a predetermined number of positive data samples of the data set are covered by the solution set. In the further stage, the system generates next stage candidate rules from previous stage candidate rules that have not been pruned and identifies the next stage candidate rules that satisfy the precision threshold, placing those rules in the solution set. A simplified rule list is generated by identifying a minimum subset of rules in the solution set that covers the positive data samples within the precision threshold. ## Claims ### Claim 1 A method comprising: extracting, by a rule generator of a server, first stage candidate rules from individual trees of a tree ensemble comprising a plurality of trees associated with a data set; identifying, by an evaluation module of the server, first stage candidate rules that satisfy a precision threshold, the first stage candidate rules that satisfy the precision threshold being placed in a solution set and pruned for further consideration; determining whether a further stage is needed based on whether a predetermined number of positive data samples of the data set are covered by the solution set; based on a determination that further stages are needed, perform operations comprising: generating, by the rule generator, next stage candidate rules from previous stage candidate rules that have not been pruned; and identifying, by the evaluation module, the next stage candidate rules that satisfy the precision threshold, the next stage candidate rules that satisfy the precision threshold being placed in the solution set and pruned for further consideration; and generating, by a list generator of the server, a simplified rule list by identifying a minimum subset of rules in the solution set that covers the positive data samples of the data set within the precision threshold. ### Claim 2 (depends on 1) The method of claim 1, further comprising: repeating the generating of the next stage candidate rules and the identifying the next stage candidate rules that satisfy the precision threshold until the predetermined number of positive data samples are covered by the solution set. ### Claim 3 (depends on 1) The method of claim 1, wherein the generating the next stage candidate rules comprises taking pairs of previous stage candidate rules that have not been pruned and taking a conjunction rule for each pair. ### Claim 4 (depends on 1) The method of claim 1, further comprising: after each stage, pruning candidate rules that have no support in the data set, the pruned candidate rules not being considered in subsequent stages. ### Claim 5 (depends on 1) The method of claim 1, wherein the identifying the next stage candidate rules that satisfy the precision threshold comprises: determining a total score for each next stage candidate rule by calculating a precision score based on a fraction of positives in the data set that satisfy the next stage candidate rule; and determining if the total score satisfies the precision threshold. ### Claim 6 (depends on 1) The method of claim 1, further comprising: receiving a selection to change the precision threshold, a lower precision threshold resulting in less processing time for generating the rule list. ### Claim 7 (depends on 1) The method of claim 1, wherein the data samples comprise training data used to train the tree ensemble. ### Claim 8 (depends on 1) The method of claim 1, further comprising: providing the simplified rule list to a further component of the server, the further component searching the rule list for at least one rule associated with an operation performed by the server and causing presentation of data derived from the at least one rule to a device of a user. ### Claim 9 (depends on 8) The method of claim 8, wherein the causing presentation of the data comprises causing display of a recommendation feature portion that includes features indicating why a recommendation was made based on the at least one rule. ### Claim 10 (depends on 1) The method of claim 1, further comprising: pruning, from consideration in subsequent stages, candidate rules that satisfy the precision threshold. ### Claim 11 A system comprising: one or more hardware processors; and a memory storing instructions that, when executed by the one or more hardware processors, cause the one or more hardware processors to perform operations comprising: extracting, by a rule generator of a server, first stage candidate rules from individual trees of a tree ensemble comprising a plurality of trees associated with a data set; identifying, by an evaluation module of the server, first stage candidate rules that satisfy a precision threshold, the first stage candidate rules that satisfy the precision threshold being placed in a solution set and pruned for further consideration; determining whether a further stage is needed based on whether a predetermined number of positive data samples of the data set are covered by the solution set; based on a determination that further stages are needed, perform operations comprising: generating, by the rule generator, next stage candidate rules from previous stage candidate rules that have not been pruned; and identifying, by the evaluation module, the next stage candidate rules that satisfy the precision threshold, the next stage candidate rules that satisfy the precision threshold being placed in the solution set and pruned for further consideration; and generating, by a list generator of the server, a simplified rule list by identifying a minimum subset of rules in the solution set that covers the positive data samples of the data set within the precision threshold. ### Claim 12 (depends on 11) The system of claim 11, wherein the operations further comprise: based on a determination that a further stage is needed, repeating the generating of the next stage candidate rules and the identifying the next stage candidate rules that satisfy the precision threshold until the predetermined number of positive data samples are covered by the solution set. ### Claim 13 (depends on 11) The system of claim 11, wherein the generating the next stage candidate rules comprises taking pairs of previous stage candidate rules that have not been pruned and taking a conjunction rule for each pair. ### Claim 14 (depends on 11) The system of claim 11, wherein the operations further comprise: after each stage, pruning candidate rules that have no support in the data set, the pruned candidate rules not being considered in subsequent stages. ### Claim 15 (depends on 11) The system of claim 11, wherein the identifying the next stage candidate rules that satisfy the precision threshold comprises: determining a total score for each next stage candidate rule by calculating a precision score based on a fraction of positives in the data set that satisfy the next stage candidate rule; and determining if the total score satisfies the precision threshold. ### Claim 16 (depends on 11) The system of claim 11, wherein the operations further comprise: receiving a selection to change the precision threshold, a lower precision threshold resulting in less processing time for generating the rule list. ### Claim 17 (depends on 11) The system of claim 11, wherein the operations further comprise: providing the simplified rule list to a further component of the server, the further component searching the rule list for at least one rule associated with an operation performed by the server and causing presentation of data derived from the at least one rule to a device of a user. ### Claim 18 (depends on 17) The system of claim 17, wherein the causing presentation of the data comprises causing display of a recommendation feature portion that includes features indicating why a recommendation was made based on the at least one rule. ### Claim 19 (depends on 11) The system of claim 11, wherein the operations further comprise: pruning, from consideration in subsequent stages, candidate rules that satisfy the precision threshold. ### Claim 20 A machine-storage medium storing instructions that, when executed by at least one hardware processor of a machine, cause the machine to perform operations comprising: extracting, by a rule generator of a server, first stage candidate rules from individual trees of a tree ensemble comprising a plurality of trees associated with a data set; identifying, by an evaluation module of the server, first stage candidate rules that satisfy a precision threshold, the first stage candidate rules that satisfy the precision threshold being placed in a solution set and pruned for further consideration; determining whether a further stage is needed based on whether a predetermined number of positive data samples of the data set are covered by the solution set; based on a determination that further stages are needed, perform operations comprising: generating, by the rule generator, next stage candidate rules from previous stage candidate rules that have not been pruned; and identifying, by the evaluation module, the next stage candidate rules that satisfy the precision threshold, the next stage candidate rules that satisfy the precision threshold being placed in the solution set and pruned for further consideration; and generating, by a list generator of the server, a simplified rule list by identifying a minimum subset of rules in the solution set that covers the positive data samples of the data set within the precision threshold.