Inference engine greediness: subsumption and suboptimality

摘要

Greedy inference engines find solutions without a complete enumeration of all solutions. Instead, greedy algorithms search only a portion of the rule set in order to generate a solution. As a result, using greedy algorithms results in some unique system verification and quality concerns. This paper focuses on mitigating the impact of those concerns. In particular, rule orderings are established so that better solutions can be found first and those rules that would never be examined by greedy inference engines can be identified. The primary results are driven by rule specificity. A rule is more specific than some other rule when the conditions in one rule are a subset of the conditions in another rule. If the least specific rule is ordered first and it is true, then greedy algorithms will never get to the more specific rule, even if they are true. Since the more specific rules generally also have the greatest return this results in the `wrong' ordering—the rule with the least return will be found. As a result, this paper focuses on generating orderings that will likely lead to higher returns.