Advanced Syntax and Compilation for Probabilistic Production Rules with PRM

Abstract

Widely adopted for more than 20 years in industrial elds, business rules o er the opportunity to non-IT users to de ne decisionmaking policies in a simple and intuitive way. When used conjointly with probabilistic graphical models (PGM) their expressiveness increase by introducing the notion of probabilistic production rules (PPR). In this paper we will present a new syntax for PPR making their use easier for business users and showcase how we managed to adapt to the compilation toolchain of an industrial rule engine accordingly.

Keywords

• Uncertain reasoning tional Models
• Bayesian Networks
• Business Rules
• Probabilistic Rela-

-

Business Rules Management Systems (BRMS), such as IBM Operational Decision Manager (ODM), are developed since the 90's to facilitate authoring, testing, deploying and executing business policies by domain users, in the form of conditions/actions rules. Syntactically close to the business language, these ease the translation of decision-making and business strategies, making them accessible to users with no programming experience. When developing intelligent systems, it may be inevitable to deal with uncertainty. This issue can have multiple origins such as measurement errors, noisy automatic process or even the modeling process itself. Handling such uncertainty in a BRMS could allow business user to represent and reason with complex and real-world data.

Numerous methods have been used in the rule-based system community to deal with uncertainty, using certainty factors [ 3 ], likelihood ratio (Hart et al. [ 8 ]) or even fuzzy logic [ 20 ]. However, there was some limitations using such approaches, mainly due to interpretation being incoherent with probability theory [ 9 ] or inconsistency in the conclusions when performing chains of inference [ 13 ].

Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

Bayesian techniques, mostly based of Bayesian networks [ 14, 19 ], have been used to model domains with uncertainty but are not suited for complex systems involving high design and maintenance costs [ 11 ]. Another solution could be to use models that combine rst-order logic and probabilistic reasoning, such as Markov logic networks [ 15 ], but their abstract structure is incompatible with business rules' principles. The following results are part of a PhD thesis whose primary ideas where discussed in [ 5 ].

This paper will start with a brief introduction on probabilistic rules and their relevance in an industrial context as well as their current limitations. We will then illustrate how we propose to increase their expressivity using a tight coupling of a BRMS with an object-oriented PGM. To illustrate our paper we will take the example of a state willing to monitor and manage its cities' water resources according to their daily consumption and possible episodic drought. 2

Uncertainty with production rules

When using a BRMS, users have to de ne the objects that will be manipulated by the rule engine through classes and attributes declaration. They will be dynamically instantiated in working memory during the execution of the program. In our case the working memory will contain objects representing cities, water towers and level sensors (that could be either working or broken), as shown in Figure 1.a.

State Name Population IdState

City 1 1..n PNoapmuelation

IdCity WaterLevel

WaterTower 1

IdTower

Type 0..n CMaapnaucfaitcyturer

LastMaintenance Enabled Level (a)

Sensor 1

IdSensor 1 Model

LastMaintenance State

Alongside the object data model, users have to de ne a set of rules. The activation/execution of those rules is managed by inference algorithms such as RETE [ 7, 17 ]. The rule presented in Table 1, for example, is used to identify broken sensors inside water towers, allowing technicians to be alerted when maintenance is required. However one would like to add uncertainty in rules, for instance in order to perform predictive maintenances rather than corrective ones, reducing the risk of unexpected breakdowns. Previous work [ 2, 1 ] showed that a loose coupling between a rule engine and probabilistic graphical models (Bayesian networks initially, then probabilistic relational models) allowed reasoning and making decision with uncertain data. However, a number of problems have been raised with those approaches [ 5 ], mainly related to accessibility issues for a business user, the proposed syntaxes requiring a deep understanding of the probabilistic model used. In particular, they require business user to de ne separate decision thresholds on each separate uncertain variable. For instance, to de ne a rule that represents the policy of water usage being restricted under certain conditions of temperature and water stock level, the user has to explicit the minimal probability of the temperature reaching the speci ed policy threshold and the minimal probability of the stock being below the speci ed policy threshold; and so on for each probabilistic variable in each condition of each rule.

A Bayesian netwrourlke R(eBstNric)t AisccaescsToomWpaatecrt{representation of a joint probability distribution over a setwohferna{ndom variables. These appear in the form of nodes in a direct acyclic graph (DAcG:C)itwy(hce.treemptehreatuarbes>en40c°eCoofr ac.rwcasterrelepvreels<e1n0t4)c;onditional independences. Each nod}e[wisithaspsroocbiaabtielidtyw>i.t9h] a conditional probability table (CPT) that contains the condthiteino{nraelstrpicrtowbaatberiluitsaiegse toofktehyefunrcatniodnos}m} variable with respect to its parents. As sairdulbeeRfeosrteri,ctBANccsesasTreo Winaatedre{quate for modeling large scale world; they quickly loses thewirheenxp{ressivity due to the large number of obtained variables. Probabilistic relatiocn:aClitmy(oc.dteemlspe(rPatRurMe>),40o°nC)t;he contrary, are combining notions from BNs and from wthl:eagpga{radigm of object-oriented languages [ 18 ], where wt: WaterTower() in c.watertowers; the focus is set on classes }ofdoob{sjuemct(swat.lnedvelb)}ywdheeren{iwng1 <re1l0a4t}i;ons among them. The expressiveness gained }w[hweitnh apdrodbianbgilintyo>tio.9n] s of random variables and conditional probabilities to classest,heantt{rriebsturitcetsw,arteerlautsiaognest,o iknetyefrufnacctieo,nsi}n}heritance and instantiations makes graphical models reusable and scalable [ 12 ]. The structuration of information in a PRM being close to the one in the object data model of the rule engine allows us to generate it directly from an annotated version of the model.

Figure 1.b shows an example of relation schema for PRM classes generated from the model described in Figure 1.a. A class City contains an attribute called waterlevel characterizing the availability of water resources: it is acting as a sum aggregator over the level attribute of the water towers present in the reference slot (dashed oval). Each tower is linked to a sensor analyzing its water level but depending on the model, the date of its last maintenance and its state, the sensor will work within a certain level of con dence, hence the uncertainty.

A new de nition of PPR

To address the business user friendliness issue raised above, we have rede ned the treatment of uncertainty in the expression of rules by replacing the probability thresholds attached to single variables by an aggregated notion of acceptable risk on the evaluation of the conditions of the rule as a whole. The action part of a rule will therefore be executed only if the set of conditions is veri ed with a probability greater than the de ned acceptable risk. This allows our probabilistic rules to be morerualcecSeesnssiobrlMeabinutteniatnrceeq{uired a rede nition of the rules compilation phase to redistribwutheenth{e overall risk to each individual condition. In the example in Table 2, a city will cr:eCsittryi(c)t; its water usages if there is a high probability that wt: WaterTower() in c.watertowers; either its temperaturesi:sShenigsohr(s.state=w=abtreorkerne)sforuomrcwest.saernesolor;wer than 104 megalitres.

or its } then {change the sensor}} Adapting the PRM model begins with the creation of a new class for each rule (in red in Figure 2), then (i) the predicates present in the conditions are added to the class, as well as the operators that connect them (in our case an or ); (ii) arcs are added and operator's CPTs generated according to their nature; (iii) the conditions are nally connected to a boolean random variable called risk whose value will be queried at each inference, it acts as a conjunction between the conditions. Fig. 2: Class dependencies schema of the enhanced PRM wt: WaterTower() in c.watertowers; s: Sensor(s.state==broken) from wt.sensor; } then {change the sensor}} rule RestrictAccessToWater { when {

c: City(c.temperature > 40°C or c.waterlevel <104) ; } [with probability > .9] then {restrict water usage to key functions}}

Because conditions are henceforth encoded in our PRM, the rule evaluation will be baserduleonRetsthriectAuscecesosfTotWheateprr{obabilistic engine, reinforcing the coupling between enginwesh.enO{nce the PRM enhanced with the new classes, probabilistic rules are rewrittenc:;Caitfyt(ecr.teamllpetrhateureco>n4d0i°tCio);ns, an evaluation of the comparison between the valuewolf: atghge{risk node and the speci ed threshold is added. It is at this level of the rule wtht:aWt atthereTomwaeirn() in c.watertowebrse;tween the rule engine and the interaction probabilistic e}ng[wini}tehdwpori{olslbuoambcic(lwuittry..l>eAv.e9l]r)}ewwhreitrtee{nwr1u<le10w4}il;l have the following form: then {restrict water usage to key functions}}

When executing the rule and if the rule engine nds elements verifying the conditions in the working memory, the calculation function of risk of the engine is called with the following parameters, as shown in Table 3: (i) the name of the class of the rule, in order to instantiate it in the probabilistic engine; (ii) the objects in the condition part that are necessary to evaluate the value of the risk variable (in our case a city); (iii) The value of the deterministic elements encoded in the class. Since the city c is known by the rule engine, we can certainly verify the truth value of the predicate (c:temperature > 40). These values will be used as evidences in the system. 3.2

Runtime, PRM system and working memory In order to be able to work with a PRM, we need to de ne its components (with the PRM model) but also to instantiate them. To do so, we are mapping the object existing in the working memory into a PRM system. As said before an object corresponding to the rule is instantiated as well during the risk evaluation process. Figure 3 shows such a system in a case where the working memory contains only two cities, each linked to a certain number of water towers. If we were computing the risk value given that the city c1 is being evaluated an object r of type RestrictAccessToWater would be created, r:city mapped to c1 and the value of r:temp > 40 updated with the truth value of c1:temperature > 40.

From a relation skeleton we can generate a BN called grounded BN, as shown on Figure 3.b; we create a node for each attributes of the objects in the relation skeleton and linked them according to the dependencies in the PRM model. Once the grounded BN generated, we can compute the posterior of the r:risk node given all the evidences.

System S Cities : c1,c2 Water towers : wt1,wt2,wt3 Sensors : s1,s2,s3 RestrictAccessToWater : r c1.watertowers = [wt1,wt2] c2.watertowers = [wt3] wt1.sensor = s1 wt2.sensor = s2 wt3.sensor = s3 r.city = c1 (a) wt1 s1 c1 c2 s3 This development work was based on what was done in the Bayesian Insight Service (BIS) plugin developed in [ 1 ]. Figure 5 illustrates how our new module, PRIME (Probabilistic Reasoning Insight ModulE), ts into the ODM's toolchain. It intervenes directly during the process of rewriting the semantic tree describing the rules (SemRuleset ) but, unlike BIS, extends the de nition and optimization of the graphical model from the rules before rewriting them (PRM enhancement process). Once the rules are rewritten, the graphical model is serialized in order to be usable by a probabilistic engine in parallel with ODM, in our case aGrUM (https://agrum.gitlab.io). At runtime, an API is used for PRIME to interoperate with aGrUM, in order to request probabilistic values keep the PRM system up-to-date (if a sensor is replaced, for example). parsing cheking ARL

SemRuleset PrmModel

PRM enhancement data

Ruleset rewriting PRIME process

SemRuleset

SemPRM plugin processes

Compiling PRM Writer .o3prm

JAR Since this work, emphasis has been placed on the performance of inferences in PGM. When performing an inference based on message-passing algorithm [ 10 ], we use a secondary structure called a Junction Tree where variables are grouped into cliques according to their parents. The complexity of inference in a BN is NP-Hard [ 4 ], growing exponentially in the tree-width of the network, the tree-width being related to the size of its largest clique (determined by the products of the domains of its variables) [ 16 ]. This is one of the major issues when dealing with probabilistic aggregators, especially when they have a high number of parents since there will be at least a clique of the size of this family.

In order to make the computation of posteriors possible we have proposed a rst approach based on aggregator decomposition [ 6 ]. Computing the distribution of c1:waterlevel in Figure 3.b but for a city with 7 water towers (each taking up to 10 values) would have needed at least 70 107 values to be stored and multiple hours of calculation. By a simple manipulation of the structure of the BN before the inference, we managed to reduce the number of parameters to store to 40 103 and computation time to less than a second. This transformation makes inferences scalable and usable in an industrial context, but only works with a certain type of aggregation functions. For this reason, we are currently working on a new approximate inference capable of working with complex networks, regardless of the nature of the nodes which compose them. Acknowledgments. This work was supported by IBM France Lab/ANRT CIFRE grant #2018/0251

References

1. Agli , H.: Uncertain reasoning for business rules . Ph.D. thesis , Universite Pierre et Marie Curie - Paris VI ( 2017 )

2. Ait-Kaci , H. , Bonnard , P. : Probabilistic production rules . Tech. rep. , IBM ( 2011 )

3. Buchanan , B. , Shortli e , E.: Rule-based Expert System { The MYCIN Experiments of the Stanford Heuristic Programming Project (01 1984 )

4. Cooper , G.F. : The computational complexity of probabilistic inference using bayesian belief networks . Arti cial Intelligence ( 1990 )

5. Ducamp , G. , Bonnard , P., de Sainte Marie, C. , Gonzales , C. , Wuillemin , P.H. : Improving probabilistic rules compilation using prm . In: RuleML+RR Doctoral Consortium 2018 (2nd International Joint Conference on Rules and Reasoning ) . Esch-sur- Alzette , Luxembourg ( 2018 )

6. Ducamp , G. , Bonnard , P. , Wuillemin , P.H. : Uncertain reasoning in rule-based systems using prm . In: Florida Arti cial Intelligence Research Society Conference ( 2020 )

7. Forgy , C.L. : Rete: A fast algorithm for the many pattern/many object pattern match problem . Arti cial Intelligence ( 1982 )

8. Hart , P.E. , Duda , R.O. , Einaudi , M.T.: Prospector-a computer-based consultation system for mineral exploration . Journal of the International Association for Mathematical Geology ( 1978 )

9. Heckerman , D. , Shortli e, E.: From certainty factors to belief networks . Arti cial Intelligence In Medicine ( 1992 )

10. Koller , D. , Friedman , N.: Probabilistic graphical models: principles and techniques . MIT press ( 2009 )

11. Koller , D. , Pfe er , A.: Object-oriented bayesian networks . Proceedings of the Thirteenth Annual Conference on Uncertainty in Arti cial Intelligence (UAI-97) ( 1997 )

12. Medina Oliva , G. , Weber , P. , Levrat , E. , Iung , B. : Use of probabilistic relational model (prm) for dependability analysis of complex systems . In: IFAC Proceedings Volumes (IFAC-PapersOnline) ( 2010 )

13. Ng , K.C. , Abramson , B. : Uncertainty management in expert systems . IEEE Expert-Intelligent Systems and their Applications ( 1990 )

14. Pearl , J. : Probabilistic reasoning in intelligent systems: : networks of plausible inference (Morgan kaufmann series in representation and reasoning ). Morgan Kaufmann Publishers, San Mateo, Calif. ( 1988 )

15. Richardson , M. , Domingos , P. : Markov logic networks . Machine learning 62(1-2) , 107 { 136 ( 2006 )

16. Robertson , N. , Seymour , P. : Graph minors. ii. algorithmic aspects of tree-width . Journal of Algorithms 7 ( 3 ), 309 { 322 ( 1986 )

17. Silva , B. : Veri cation of Business Rules Programs . Ph.D. thesis , Albert-LudwigsUniversitat Freiburg ( 2012 )

18. Torti , L. , Wuillemin , P.H. , Gonzales , C. : Reinforcing the object-oriented aspect of probabilistic relational models . In: Proceedings of the 5th European Workshop on Probabilistic Graphical Models , PGM 2010 ( 2010 )

19. Weber , P. , Medina-Oliva , G. , Simon , C. , Iung , B. : Overview on bayesian networks applications for dependability, risk analysis and maintenance areas . Engineering Applications of Arti cial Intelligence ( 2012 )

20. Zadeh , L. : Fuzzy sets . Information and Control 8 ( 3 ), 338 { 353 ( 1965 )