# US 2020/0394530 A1 · Rule induction to find and describe patterns in data

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

- Number: US 2020/0394530 A1
- Document ID: US20200394530A1
- Status: Published application
- Kind: A1
- Application number: 16/443,859
- Filed: 2019-06-17
- Published: 2020-12-17
- Earliest claimed: 2019-06-17
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Edmund Chi Man Tse; Brett Owens Simons; Sandeep Repaka; Yatpang Cheung
- Web page: https://patentgrep.com/patent/US20200394530A1

## CPC

- G06N 5/025: Extracting rules from data
- G06F 18/2113: by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation
- G06F 18/214: Generating training patterns; Bootstrap methods, e.g. bagging or boosting
- G06F 18/24765: {Rule-based classification}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 20/20: Ensemble learning
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Rule induction is used to produce human readable descriptions of patterns within a dataset. A rule induction algorithm or classifier is a type supervised machine learning classification algorithm. A rule induction classifier is trained, which involves using labelled examples in the dataset to produce a set of rules. Rather than using the rules/classifier to make predictions on new unlabeled samples, the training of the rule induction model outputs human-readable descriptions of patterns (rules) within the dataset that gave rise to the rules (rather than using the rules to predict new unlabeled samples). Parameters of the rule induction algorithm are tuned to favor simple and understandable rules, instead of only tuning for predictive accuracy. The learned set of rules are outputted during the training process in a human-friendly format.

## Claims

### Claim 1

A method performed by a computing device to infer a set of rules from a dataset, the computing device comprising processing hardware and storage hardware, the method comprising:
accessing the dataset, the dataset comprised of columns and rows, each row comprised of values for the respective columns;
select, from among the columns, a target column that defines a target dataset in the dataset, the target column comprising values comprising target classes;
generating a set of rules for the target dataset by:
iterating over the target classes, and for each target class generating a new rule and removing from the target dataset rows covered by the new rule, wherein each new rule is generated by maintaining a beam of the K-best rules as defined by accuracy and/or statistical significance with respect to the current target dataset; and
outputting text comprising the set of rules, wherein each rule is ranked relative to the other rules and comprises conjunctively linked terms, each term comprising indicia of a column and an operator.

### Claim 2 (depends on 1)

A method according to claim 1, wherein the generating comprises using separate-and-conquer on the target dataset.

### Claim 3 (depends on 1)

A method according to claim 1, wherein the beam of the K-best rules is computed by, for each rule in the beam, from rows covered by that rule: computing distinct conditions, adding each condition to that rule, and compute a measure for that rule, the measure corresponding to that rule's accuracy and/or statistical significance.

### Claim 4 (depends on 3)

A method according to claim 3, wherein rules are computed with a greedy heuristic where the K-best rules are selected based on the respective accuracies and/or statistical significances.

### Claim 5 (depends on 1)

A method according to claim 1, wherein the generating the set of rules is performed by a machine learning algorithm and the target dataset functions as training data labeled with a target class of the target column.

### Claim 6 (depends on 1)

A method according to claim 1, wherein the outputting comprises displaying, in text form, rules from the set of rules.

### Claim 7 (depends on 6)

A method according to claim 6, further comprising displaying a user interface, the user interface comprising a first control that selects the target dataset and a second control that configures column settings that govern the generating the set of rules.

### Claim 8 (depends on 1)

A method according to claim 1, wherein the generating the set of rules is performed by a modified CN2 algorithm, the modified CN2 algorithm comprising a greedy beam search that divides and separates the target dataset.

### Claim 9 (depends on 1)

A method according to claim 1, wherein a stop condition is evaluated to stop generating the set of rules before the set of rules covers all of the target dataset.

### Claim 10

A computing device comprising:
processing hardware;
storage hardware storing instructions configured to cause the processing hardware to perform a process, the process comprising:
accessing a dataset comprising columns and rows, the rows comprised of values of the columns;
selecting a target column;
generating a set of rules by training a machine learning algorithm on the dataset as constrained by the selected target column, wherein the machine learning algorithm comprises a sequential coverage algorithm that recursively builds new rules by, for respective rule searches on respective values of the target column, dividing and separating the constrained dataset using a greedy beam search; and
outputting the set of rules, each rule comprising conjunctively joined terms, each term defining a Boolean condition as a function of one or more columns.

### Claim 11 (depends on 10)

A method according to claim 10, wherein the greedy beam search comprises selecting K-best conditions based on respective accuracy measures with respect to a corresponding reduction of the target dataset.

### Claim 12 (depends on 10)

A method according to claim 10, wherein the rules in the set of rules are ranked relative to each other according to accuracy with respect to the target dataset.

### Claim 13 (depends on 12)

A method according to claim 12, further comprising displaying text representations of the rules.

### Claim 14 (depends on 10)

A method according to claim 10, wherein the rules predict respective classes of the target column.

### Claim 15 (depends on 10)

A method according to claim 10, wherein the machine learning algorithm computes the set of rules in an amount of time that is proportional to the number of rows times in the target dataset, times the number of columns, times the number of rules in the set of rules.

### Claim 16

A method performed by one or more computing devices, the method comprising:
accessing a dataset comprised of columns and rows of values in the respective columns;
defining a target column for the dataset, the target column comprised of target classes;
generating a set of rules by, for each target class, while there are row instances corresponding to the target class: generating a new rule and removing instances covered by the new rule;
wherein generating a new rule comprises a search comprising:
maintaining a beam of the current K-best rules found by the search;
while the beam is not empty:
for each rule in the beam: compute distinct selection conditions, add each condition to the rule, compute accuracy/significance of the rule, and adding the rule to a temporary set of rules; and
adding, to the beam, the K-best rules selected from the temporary set of rules; and
returning a top-ranked rule found by the search.

### Claim 17 (depends on 16)

A method according to claim 16, wherein rules are ranked based on respective accuracy measures, the accuracy measure of a rule computed as a function of the number of rows covered by the rule and the number of rows in the target class.

### Claim 18 (depends on 16)

A method according to claim 16, the method further comprising stopping the searching when determined that the found rules cover a threshold ratio of rows.

### Claim 19 (depends on 16)

A method according to claim 16, wherein each rule comprises conjunctively joined selectors, and wherein the searching is terminated whenever a rule's number of selectors meets a threshold.

### Claim 20 (depends on 16)

A method according to claim 16, further comprising performing post-processing on the set of rules, the post-processing simplifying the form of the rules in the set of rules.