Rule invocation mechanism for inductive learning engine

• US 5,222,197 A
• Filed: 06/28/1990
• Issued: 06/22/1993
• Est. Priority Date: 06/28/1990
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Wilson, Matthew, Chen, Kaihu, Teng, Henry S., Abbruzzese, Gregory B., Verdeven, Michael P.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Downs, Robert W.
• Application Number:
  US07/545,072
• Time in Patent Office: 1,090 Days
• Field of Search: 364/513, 395/51, 395/61, 395/68
• US Class Current: 706/58
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

A rule invocation mechanism in an inductive learning engine employing symbolic rules for characterizing a sequence of time-related events. The rules to be tested as hypotheses against new events in the sequence are ranked according to their information content or "quality" value. The efficiency of the rule-to-event pattern matching process for characterizing the new events is increased by not testing a hypothesis if a much better hypothesis already exists. Those hypotheses that characterize events in the sequence are tagged to the event.

Claims

1. In a rule-based computer system empoloying rules for characterizing a sequence of time-related events, each rule having a set of conditions and an associated quality value, a method of invoking the rules, comprising the steps, executed by the computer system of:

selecting the rules in order of decreasing quality values;

selecting the rules in order of decreasing quality values;

finding in the selected order the ones of the rules which characterize the sequence of events by matching the conditions of the rules with the events and have a quality value that is not less by a predetermined amount than he quality of any other of the previously found ones of the rules which characterize the sequence of events;

tagging each of the events with the found ones of the rules which characterize the sequence including that event;

determining whether an event in the sequence has been previously tagged with one of the rules;

testing whether a selected one of the rules characterizes the sequence including the event if the event was not previously tagged;

determining whether, for an event previously tagged, the quality of a rule tagged to the event is greater than the quality of a selected one of the rules by the predetermined amount;

testing whether the selected one of the rules characterizes the sequence including the event if the quality of the rule tagged to the event is not greater than the quality of the selected one of the rules by the predetermined amount; and

updating the quality values of selected ones of the rules which are tested.

2. The method of claim 1 further comprising the step of reordering the rules according to decreasing quality value after testing.

3. The method of claim 1 further comprising the step of generating a new rule for characterizing the sequence of events.

4. The method of claim 3 further comprising the step of evaluating the new rule according to predetermined criteria including quality value.

5. In a rule-based computer system employing rules for characterizing a sequence of time-related events, each rule having a set of conditions and an associated quality value, a method of invoking the rules, comprising the steps, executed by the computer system of:

ranking the rules according to decreasing quality value;

selecting the rules in ranked order;

selecting one of the events in the sequence of events;

determining whether selected ones of the rules characterize the sequence of events, including the selected one of the events, by matching the conditions of the selected ones of the rules with the events, for each of the rules that have a quality value that is not less by a predetermined amount than the quality value of any other of the rules which were previously determined to characterize the sequence of events, including the selected one of the events;

tagging the selected on of the events with each of the selected ones of the rules which are determined to characterize sequence of the events including the selected one of the events;

determining whether the selected one of the events has been previously tagged with one of the rules;

testing whether the selected one of the rules characterizes the sequence including the selected one of the events if the selected one of the events was not previously tagged;

determining whether the quality of a rule tagged to the selected one of the events is greater than the quality of the selected one of the rules by the predetermined amount;

testing whether the selected one of the rules characterizes the sequence including the selected one of the events if the quality of the rule tagged to the selected one of the events is not greater than the quality of the selected one of the rules by the predetermined amount; and

updating the quality values of selected ones of the rules which are tested.

6. The method of claim 5 further comprising the step of reordering the rules according to decreasing quality value after testing.

7. The method of claim 6 further comprising the step of reordering the selected rules according to decreasing quality value.

8. The method of claim 5 further comprising the step of generating a new rule for characterizing the sequence of events.

9. The method of claim 8 further comprising the step of evaluating the new rule according to predetermined criteria including quality value.

10. In a rule-based computer system employing rules for characterizing a sequence of time-related events, each rule having a set of conditions and an associated quality value, a method of incremental inductive learning, comprising the steps, executed by the computer system, of:

selecting a set of rules from a rule base in order of decreasing quality values;

finding in the selected order the ones of the rules which characterize the sequence of events by matching the conditions of the rules with the events and have a quality value that is not less by a predetermined amount than the quality value of any other of the previously found ones of the rules which characterize the sequence of events;

tagging each of the events with the found ones of the rules which characterize the sequence including that event;

generating a new rule for characterizing the sequence of events; and

storing the new rule in the rule base.

11. The method of claim 10 wherein the finding step further includes the substeps of

determining whether an event in the sequence has been previously tagged with one of the rules, and

testing whether the selected one of the rules characterizes the sequence including the event if the event was not previously tagged.

12. The method of claim 11 wherein the fining step further includes the substeps of

determining whether, for an event previously tagged, the quality of a rule tagged to the event is greater than the quality of a selected one of the rules by the predetermined amount,

testing whether the selected one of the rules characterizes the sequence including the event if the quality of the quality of the rule tagged to the event is not greater than the quality of the selected one of the rules by the predetermined amount.

13. The method of claim 12 further comprising the step of updating the quality values of selected ones of the rules which are tested.

14. The method of claim 13 further comprising the step of reordering the rules according to decreasing quality value after testing.

15. The method of claim 10 further comprising the step of evaluating the new rule according to predetermined criteria including quality value.

16. The method of claim 10 wherein each rule has an associated entropy value which measures accuracy of prediction of the rule, and the quality value associated with each rule is based in part on the entropy value of that rule.

17. The method of claim 10 wherein each rule has an associated confidence level which indicates past effectiveness of the rule, and the quality value associated with each rule is based in part on the confidence level of that rule.

18. The method of claim 10 wherein each rule has a syntactical complexity, and the quality value associated with each rule is based in part on the syntactical complexity of that rule.

19. In a rule-based computer system employing rules for characterizing a sequence of time-related events, each rule having a set of conditions and an associated quality value, a method of incremental inductive learning, comprising the steps, executed by the computer system, of:

selecting a set of rules from a rule base in order of decreasing quality values;

selecting one of the events in the sequence of events;

determining whether selected ones of the rules characterize the sequence of events, including the selected one of the events, by matching the conditions of the selected ones of the rules with the events, for each of the rules that have a quality value that is not less by a predetermined amount than the quality value of any other of the rules which were previously determined to characterize the sequence of events, including the selected ones of the events;

tagging the selected one of the events with each of the selected ones of the rules which are determined to characterize the sequence of events including the selected one of the events;

generating a new rule for characterizing the sequence of events; and

storing the new rule in the rule base.

20. The method of claim 19 wherein the determining step includes the substeps of

determining whether the selected one of the events has been previously tagged with one of the rules, and

testing whether the selected one of the rules characterizes the sequence including the selected one of the events if the selected one of the events was not previously tagged.

21. The method of claim 20 wherein the determining step further includes the substeps of

determining whether the quality of a rule tagged to the selected one of the events is greater than the quality of the selected one of the rules by the predetermined amount, and

testing whether the selected one of the rules characterizes the sequence including the selected one of the events if the quality of the rule tagged to the selected one of the events is not greater than the quality of the selected one of the rules by the predetermined amount.

22. The method of claim 21 further comprising the step of updating the quality values of selected ones of the rules which are tested.

23. The method of claim 22 further comprising the step of reordering the rules according to decreasing quality value after testing.

24. The method of claim 19 further comprising the step of evaluating the new rule according to predetermined criteria including quality value.

25. The method of claim 19 wherein each rule has an associated entropy value which measures accuracy of prediction of the rule, and the quality value associated with each rule is based in part on the entropy value of that rule.

26. The method of claim 19 wherein each rule has an associated confidence level which indicates past effectiveness of the rule, and the quality value associated with each rule is based in part on the confidence level of that rule.

27. The method of claim 19 wherein each rule has a syntactical complexity, and the quality value associated with each rule is based in part on the syntactical complexity of that rule.

28. A rule-based computer system employing rules for characterizing a sequence of time-related events, each rule having a set of conditions and an associated quality value, the system comprising:

storage means for storing a set of symbolic rules for characterizing the sequence of events;

rule invocation means, coupled to the storage means, for determining which rules in the set best characterize the sequence of events, the rule invocation means comprising;

ranking means for ranking the rules in the set according to decreasing quality value;

pattern-matching means, coupled to the ranking means, for determining in ranked order whether a next rule in the set characterizes the sequence of events by matching the conditions of the next rule with the events;

tagging means, coupled to the pattern-matching means, for tagging each of the events with those rules which are determined by the pattern-matching means to characterize the sequence of events including the event;

comparator means, coupled to the ranking means and the pattern-matching means, for comparing the quality value of a lower ranked rule with the quality value of a higher-ranked rule tagged to an event and for selecting the lower-ranked rule as the next rule for input to the pattern-matching means if the quality of the higher-ranked rule is not greater than the quality value of the lower ranked rule by a predetermined amount;

rule generating means, coupled to the storage means and responsive to the rule invocation means, for generating a new rule to characterize the sequence of events.

29. The system of claim 28 further comprising evaluating means, coupled to the storage means and the rule generating means, for evaluating the new rule generated by the rule generating means according to predetermined criteria including quality value.

30. The system of claim 29 wherein the rule invocation means further comprises means, coupled to the pattern-matching means, for updating the quality value of the next rule input to the pattern matching means according to the determination by the pattern-matching means whether the next rule characterizes the sequence of events including the next event.