“The Sleep of Reason Produces Monsters”, Francisco Goya

 Defeasible Logic and Business Rules with Probabilities

Modern rules and decisions management systems provide effective mechanisms for development of good decision models. However, building real-world decision models people always face complex issues related to diagnostic and resolution of rule conflicts. Some systems can effectively verify decision model consistency and diagnose rule conflicts. But there are no practically used Business Rules (BR) products that claim that they may automatically resolve rule conflicts.

In the Part 1 of this series I described how end users can represent their rules in single-hit and multi-hit decision tables while avoiding rule conflicts. But is it possible to automatically resolve rule conflicts? I will discuss this problem below.

Defeasible Logic Formalism

The closest theory that deals with business rule conflicts is known as “Defeasible Logic” introduced more than 25 years ago to support so-called “non-monotonic or defeasible reasoning”.  This is a kind of reasoning that is based on reasons that are defeasible, i.e. capable of being defeated by other reasons. Here is a very informal introduction that you may skip and proceed to the next section.

The defeasible logic differentiates between strict rules and defeasible rules and introduces superiority relations between rules. Strict rules are rules in the classical sense that are used in all modern business rules management systems. Whenever the conditions of a rule are indisputable then a conclusion of the rule is also indisputable. For example, the rule “Penguin is a bird” is an example of a strict rule (“If something is a penguin Then it is a bird”). Defeasible rules are rules that can be defeated by contrary evidence.  An example of such a rule is “Birds typically can fly”. The idea is that if we know that something is a bird, then we may conclude that it flies unless there is other evidence suggesting that it may not fly. There are special rules called Defeaters that are used only to defeat some defeasible rules by producing evidence to the contrary. An example of a defeater is “Heavy animals may not be able to fly”.

Superiority relations among rules are used to define priorities among rules, that is, where one rule may override the conclusion of another rule. For example, given the defeasible rules

• R1: Birds typically fly
• R2: Birds with broken wings cannot fly

which contradict one another, no conclusive decision can be made about whether a bird with broken wings can fly. But if we introduce a superiority relation ”>” with R2  > R1, then we can indeed conclude that it can’t fly. It turns out that we only need to define superiority relations over rules with contradictory conclusions.

The Defeasible Logic “was designed to be easily implementable right from the beginning” as mentioned in this very good source. The first known implementation was done in 1997 by Donald Nute as an extension of Prolog. Since then there were a lot of academic papers devoted to its use. In recent years the Defeasible Logic started to come back in the context of Semantic Web and RuleML.  However, it never found its way into commonly used BR systems until now.

Defeasible Logic and Business Rules Systems

Real-world Business Rules and Decisions Management systems are more oriented to business users expecting them (not programmers or scientists) to create and maintain business rules. But even if an experienced software developer (not mentioning a business analyst) opens a description of the Defeasible Logic provided for example in this Wikipedia article or in this research paper, it’s hard to expect that they will go beyond the first section.

So, on the one hand, we have a solid theoretical foundation for rule conflicts resolution, but on the other hand, we have the entire family of rule representation systems that do not use this foundation. Why is that?

I may offer two explanations:

1. BR vendors get used to the fact that their users have enough means (such as the single-hit and multi-hit decision tables described in the Part 1) to avoid rules conflicts
2. It’s hard to offer a nice user interface for the defeasible logic constructs without over-complicating rules readability and ease of future modifications.

Both explanations don’t sit well anymore with the demanding BR customers. Enterprise-level rule repositories in many cases have already achieved a high level of maturity and internal complexity. The absence of automatic conflict resolution tools will lead to unnecessary growth of the total number of rules and may gradually convert such repositories to unmaintainable “monsters” – see a quote from Goya on the top of this page. The second explanation is not valid anymore either: some BR vendors have already started to include the Defeasible Logic in their tools.  No wonder that open source products take a lead in this area.

Defeasible Logic Implementation – Drools

On August 1, 2013 the developers of highly popular open source BR product “Drools” announced the availability of their implementation of the defeasible logic inside the DRL language. In particular, the Drools team leader Mark Proctor wrote:

“Davide just got a first cut of Defeasible Logic in Drools. This is like a supercharged TMS implementation that allows users to handle conflicts in logical insertions. It introduces the following rule annotations:
@Defeater
@Defeasible
@Defeats(“rule1”, “rule2”, “rule3) // comma separated list of rules it defeats ”

You may find an example of the rules annotated with the defeasible logic constructs here.

In a private conversation, Mark mentioned that it was Charles Forgy, the inventor of Rete, who pointed him first to the defeasible logic 5 years ago. It is great that Charles continues to influence the BR industry. Davide Sottara mentioned defeasible logic on the Drools support forum in 2011. And now, with additional development resources in place, the Drools team has finally produced the first implementation. Mark wrote that the defeasible logic “will remain an experimental feature for some time” but they already extended an offer to everybody to try it for free.  I am sure we will get much more information from the Drools team soon. Congratulations to our colleagues at Red Hat!

Defeasible Logic Implementation – OpenRules

OpenRules first published its constraint-based inference engine (Rule Solver) in March-2012. Rule Solver may execute standard decision models defined in regular OpenRules decision tables in accordance with TDM requirements. I published an article about the use of a constraint solver as a rule engine at the RuleML-2011. Rule Solver is able to find all conflicts among rules even when they are defined in different decision tables and different Excel files. By default Rule Solver was able to show you which rules are in conflict, however, without superiority relations among rules, it was not able to resolve the conflicts. So, how can we implement the defeasible logic in OpenRules?

Contrary to traditional business rules approaches, Constraint Programming (CP) approach, selected by OpenRules, always differentiated between hard constraints (“strict” rules) and soft constraints (“defeasible” rules). CP provides various ways for solving constraint satisfaction problems while satisfying all hard constraints and minimizing violations of soft constraints. If you want to learn more, take a look at this presentation.

So, with Rule Solver already in place, OpenRules did not need a new implementation for the defeasible logic. We only needed to find a way to represent superiority relations in OpenRules decision tables without overwhelming business users with too many technical details. Of course, we could do the following

• associate a unique ID with each rule (one column if the decision table)
• mark defeasible rules (another column)
• list IDs for rules whom the current rule defeats (one more column).

This is approximately what Drools annotations can do in the DRL. It may be acceptable for developers. However, I believe it is not acceptable for business analysts who are in charge of creation and maintenance of decision tables. If some rules directly know about other rules it may lead to “macaroni” relations especially when new defeasible rules need to be added.  So, we decided to add only one optional column to our standard decision table template called “ActionProbability”. It means instead of stating a defeasible rule “Birds typically can fly” our user would be able to write something like “Birds can fly with probability HIGH” and “Birds with broken wings cannot fly with probability VERY HIGH”.

Now let’s look again at the complex decision table from Part 1:

With OpenRules defeasible logic we may represent the same table as follows:

Here the first defeasible (soft) rule

“If Bird is Yes Then Ability To Fly is Yes with Probability MID”

can be defeated by the second soft rule

“If Penguin is Yes Then Ability To Fly is No with Probability VERY HIGH”.

And the second rule can be defeated by the third hard (strict) rule

“If In Airplane is Yes Then Ability To Fly is Yes”.

Hopefully, it is intuitive enough for a reader to guess how the remaining rules work.

Please note that this way we do not force a user to list all rules that can be defeated by the current rule (that would lead to unnecessary maintenance headache). The third hard rule can defeat any soft rule, and the fifth rule with Probability VERY HIGH can defeat the fourth rule with a smaller probability HIGH (forcing a scared chicken to fly).  The following probabilities are currently available (in ascending order): NEVER, VERY LOW, LOW, BELOW MID, MID, ABOVE MID, HIGH, VERY HIGH, ALWAYS. If necessary we certainly may increase this list allowing probabilities 0, 1, 2, …, 99, and 100%.

Still, a designer of such decision tables should be careful defining superiority relations. For example, in the above table, it is not clear if a scared penguin can fly. It is certainly better to specify rule 5 with an additional condition “Chicken is Yes”. However, now business analysts may express their preferences in a quite intuitive way as they do it in everyday life when they say “There is a high probability of rain tonight” without any knowledge about the defeasible logic or even the probability theory.

How does OpenRules implement the described defeasible logic? It transfers rules execution problem into an optimization problem where rules are interpreted as conditional constraints defined on the involved decision variables. Constraints for all “strict” rules are simply posted as hard constraints. Constraints for all rules with probabilities (higher than NEVER and lower than ALWAYS) are posted conditionally with an ability to be violated. The violation cost of each constraint is defined by its actual probability value. Then Rule Solver solves the optimization problem trying to minimize the total constraint violation.

Below are more practical examples from the financial domain. The first decision table defines if a stock is risky:

The second decision table helps to decide if to buy a stock or not:

A new version of Rule Solver that supports these capabilities is in a test mode now and will be added to a new release. However, if you want to try it earlier feel free to contact OpenRules at support@openrules.com.

Conclusion

With these two posts, I did not want to create a false impression that all problems related to rule conflicts have been solved, but rather I wanted to bring attention to the importance of these issues and to show some possible ways for their resolution. I have no doubts that all major BR vendors gradually will add an automatic ability to solve rule conflicts to their product offerings. Whether they will use a complete defeasible logic implementation or just its elements or possibly some other techniques it remains to be seen.

Both major open source BR products, Drools and OpenRules, will continue to improve their implementations.  Major commercial vendors, IBM and FICO, have their own constraint programming tools, and it should not be a problem for them to implement an approach similar to the one implemented by OpenRules. Other BR vendors may use the JSR-331 standard with several open source implementations to add conflict resolution capabilities to their tools. They may find a catalog of currently available CP tools at http://cpsolvers.org. Actually, to promote the use of Constraint Programming within decision management environments, OpenRules is willing to help other vendors with CP-based implementations – contact me directly if you are interested.

I also believe that a mechanism for rule conflict resolution can (and should) be standardized and one day it will find its way into the upcoming DMN standard as well as into the extended TDM.