Stephane Doncieux

Veronique Delcroix

Hassan Aït

Changhai

Moussa

Pierre Yiquan

Nawal

Oumaima

Nicolas Karim

Ahmed Olivier

Matthieu Reda Santiago

Penelope Siao-Leu Hugo

Cécile Finally

El Houcine

Nidhal, Fatima Ismail Jamal

Hamza, Youness, Houssame, Amine, Imad, Yvain Abdel Hadi

Mélaine Alexis Fayçal

Ali Kamal

Amine Fati

Reda Tariq

I would like to express my gratitude towards

Chapter 1 Introduction 1.1 General Context

In the contemporary business environment, a great deal of operations is performed or supported by information technology (IT) systems. Ironically, IT does not always "support" the business but also may cause its failure or lower the quality of its deliveries 1 . For example, it is known that a lot of IT-based projects miss their deadlines because of IT obstacles. In addition, initial requirements might be exposed to changes and IT systems, however, hardly follow the change. There are many causes of this problematic situation and a notable cause is related to business policies and rules. Despite the importance of these latter in driving business operations, there were surprisingly no well-established methodology, prior to the business rules approach that we introduce later, to emphasize these rules and efficiently encode them into a computer-based application. Information about such rules is often hidden or repeated throughout the application modules. Even worse, it could be lost, unknown, inconsistently captured or not precisely stated, and this leads to businesses that are run in contradiction to their rules and goals.

1 around 66% of the US projects fail according to [123,124] 1 This is because there is often a misalignment between the business requirements specification and the IT implementations. The separation of concerns principle promotes a modular architecture for developing IT systems, based on a loosely inter-operating services (concerns). After data, business rules (BRs) follow this principle and become an independent concern. Actually, in the last decades, the Business Rules Approach emerged as a well-established methodology to allow for a better management of BRs. The approach introduces a new layer of BRs to the IT systems design and architecture. Business systems development becomes business-centric and BRs become a separate service inside a Service Oriented Architecture (SOA), i.e., they are now independent entities, distinct from the data and the view aspects of the system and separated from processes 2 . There are many ways to express the rules that govern or guide business activities including the IF/THEN-ELSE constructs, e.g., "If the category of the customer is Premium then add a 40% discount to his shopping card".

In a competitive context, agility is the real time capacity to adapt to the market change and react in a direction that benefits the organization. The sake of agility is at the core of the business rules approach. The latter replies to the fast and constant change of the business environment with an agile and flexible development process [START_REF] Boyer | Agile Business Rule Development -Process, Architecture, and JRules Examples[END_REF]. Requirements and rules are no more hidden or scattered along business applications, but their automation is now managed and maintained trough a dedicated system called Business Rules Management Systems, BRMSs hereafter. In recent years, such tools have proliferated and many organizations adopted the approach for the sake of agility, re-usability and consistency of BRs. These business-driven tools have the advantage to enforce business policies and prove to help the enterprise to reduce costs and improve their performance and productivity. This explains why BRMSs industry witnesses an increasing annual growth, as it is shown in recent research reports such as [START_REF] Hilwa | Worldwide business rules management systems forecast, 2015-2019[END_REF][START_REF]Infoholic: Global Business Rules Management System (BRMS) Market, Trends & Forecast[END_REF], which estimated the global BRMS market to reach $636.7 million in 2015 with a Compound Annual Growth Rate (CAGR) up to 17.8% during the period 2015-2020. It is worthy to notice that BRMSs can be also integrated with different Business Process management tools and to reinforce the alignment of computer science practices with business administration goals [START_REF] Weske | Business Process Management[END_REF].

Having complete or certain information about our domain is not always a realistic scene. On the contrary, uncertainty is everywhere, it affects data, knowledge and processes. In particular, reasoning under uncertainty becomes an important and active area of research within the field of Artificial Intelligence (AI). Although there is no consensual definition for AI, one can say that it is about building programs or machines that try to imitate human intelligence at a certain level and improve their outputs as long as they consume more experiences. According to [115], different people approach AI with different methods while having different goals in mind. [115] also emphasizes four aspects about AI that are related to thinking humanly, thinking rationally, acting humanly and acting rationally.

While the first two approaches are concerned with reasoning, the last ones address behavioral aspects. During the last decade, AI has witnessed a remarkable progress as well as a proliferation of its applications. Fig. 1.1 depicts some of the AI key sub-domains, although the list is not exhaustive.

Reasoning includes inferring the state of the domain at hand based on knowledge about it and some prior observations. For example, a diagnosis of a patient's symptoms, blood and urine might help doctors to determine the diseases in question, if any, and prescribe a treatment accordingly. A Nuclear-Magnetic-Resonance (NMR) well-logging tool helps petro-physicist, using sensor measurements, to investigate earth formations, in particular, to characterize hydrocarbon reservoirs and decide whether water, gas or oil are present. In these examples, we may lack the adequate information to make a good decision. Some aspects about the patient are just unobservable, e.g., only few historical records are available, and other aspects must be estimated. Observations themselves may be affected by measurement errors, which implies lack of accuracy and precision. In the example of NMR well-logging, measurements could be noisy due to vibrations of the sensors and are unreliable in some particular environments. In all the above situations, the decision making process is no more deterministic and we must take into account uncertainty in the reasoning process to reach an acceptable decision.

Artificial Intelligence

Indeed, uncertainty is an inescapable aspect of real world data and several theories and frameworks have been proposed to handle it. However, we are interested in one popular solution that is based on Probabilistic Graphical Models (PGMs) [START_REF] Jordan | Graphical models[END_REF][START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF][START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]. PGMs mix the mathematical power of probability theory with the intuitive representation of graph theory. Therefore, they have the advantage to separate knowledge representation from the reasoning process. Broadly speaking, a PGM, be it directed and undirected, exploits dependencies between the variables of interest to compactly capture the uncertainty of the domain and derive conclusions using sophisticated inference algorithms.

Motivation

Current BRMSs perform well in the presence of complete information about the domain using first order logic. The mechanism of Forward Chaining3 , for instance, permits to infer conclusions from observations about the domain. It turns out that the BRMS technology has roots in the Rule-Based Systems (RBSs), a sub-field of AI. Even though the latter has an active research community on uncertainty, there is no current BRMS that offers a satisfactory support for it. As a matter of fact, current BRMSs turn to have poor facilities for uncertainty management. They either assume the encoded knowledge to be deterministic or use some heuristic models that are unfortunately limited.

There are two needs that motivate this thesis. The first one is related to Operational Decision Manager, ODM hereafter, which is the IBM market leading BRMS and the company seeks to enrich its reasoning process by handling uncertainty. In this thesis, we study how AI techniques can answer such an issue and we focus on the PGM framework for it has common concepts to share with BRMSs. Thus our first research question is the following :

Q 1 :
How can we efficiently manage uncertainty in BRMSs using the PGM framework?

The working memory that stores facts about the knowledge in a BRMS is dynamic and incremental by nature. For example, new objects might be inserted or removed or new relations could be defined. This remark directs us to our second motivation. The probabilistic inference should take the property of incrementality into account. As we will see, the literature does not fulfill this need sufficiently.

Therefore, our second research question can be formulated as follows:

Q 2 : How can we perform probabilistic inference in an incremental and optimized manner?

Contributions and Outline

This thesis has two main contributions. First, we introduce a new incremental probabilistic inference algorithm, which is well suited for the dynamic nature of ODM. We provide experimental tests to shed light on the gain we obtain using our approach. Furthermore, our algorithm is being added as a contribution to the development of the open source aGrUM library (a Graphical Universal Model).

The latter is developed by our research laboratory LIP6 to provide state-of-the-art implementations of graphical models for decision making. Note that we develop a general algorithm that can be applied whenever the system at hand is incremental and multi-target. As a consequence our algorithm is not restricted to BRMSs, that is why we will first handle Q 2 . Our second contribution provides an answer to Q 1 through a coupling architecture with PGMs. Therefore, we propose an effective methodology to ensure the coupling and, as an application, we develop an internal prototype on top of ODM. Generally speaking, the prototype maps the model upon which the BRMS is built to a PGM and delegate the BRMS's probabilistic queries to the PGM's engine. Computations can then be performed using the algorithm developed in the first contribution. We also provide some principles to ensure more advanced probabilistic reasoning for BRMSs.

Our research results in the following scientific publications:

1. Modèles Probabilistes Relationnels et leur inférence incrémentale pour les systèmes à base de règles orientés objet, Revue d'Intelligence Artificielle 2017, submitted [START_REF] Agli | Modèles Probabilistes Relationnels et leur inférence incrémentale pour les systèmes à base de règles orientés objet[END_REF].

2. Incremental Junction Tree Inference. In Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU) 2016 [START_REF] Agli | Incremental junction tree inference[END_REF] 3. Un algorithm d'arbre de jonction incrémental, JFRB 2016 [START_REF] Agli | Un algorithme d'arbre de jonction incrémental[END_REF] 4. Business Rules Uncertainty Management with Probabilistic Relational Models. In Rule Technologies. Research,Tools, and Applications (RuleML) 2016 [START_REF] Agli | Business Rules Uncertainty Management with Probabilistic Relational Models[END_REF].

5. Uncertain Reasoning for Business Rules. In RuleML doctoral consortium 2014 [START_REF] Agli | Uncertain Reasoning for Business Rules[END_REF] 6. Des règles métier pour la gestion de l'incertain, JFRB 2014 [START_REF] Agli | Des règles métier pour la gestion de l'incertain[END_REF] This manuscript is composed of 5 Chapters and is organized as follows.

Chapter 2 gives an overview of the business rules approach and stresses upon its technological implications, which are manifested in the adoption of BRMSs. Then, we explain the origins of BRMSs and see different approaches used to tackle the question of uncertainty. As we already mentioned, we are interested in PGMs and in particular, in the formalism of Bayesian Networks (BNs) and its objectoriented extension Probabilistic Relational models (PRMs). Hence, Chapter 3 introduces BNs and PRMs and describes how they allow a decision maker to model uncertainties in the domain and, later, to infer its state given some observations.

We also present some popular probabilistic inference algorithms used by BNs. In Chapter 4, we provide an answer to Q 2 and we propose a probabilistic inference algorithm that is adaptive to incremental and multi-target systems, and ODM in particular. In addition, the chapter highlights the effectiveness of our method based on experimental tests. In Chapter 5, we provide an answer to Q 1 . After introducing the necessary background, this chapter proposes a method to empower BRMSs capabilities with uncertainty management. Our results are implemented in a new prototype developed on top of ODM. We describe the prototype's main components and see how uncertainty can be handled in such an industrial context.

Chapter 6 concludes this manuscript with a summary of our work and proposes some directions for future works.

Introduction

There is a well-established business tradition of automating parts of the policies that govern the decision-making process in computer-based applications [START_REF] Graham | Business Rules Management and Service Oriented Architecture: A Pattern Language[END_REF][START_REF] Morgan | Business Rules and Information Systems: Aligning IT with Business Goals[END_REF].

However, the business environment, being characterized by a rapid and constant change, does not facilitate such an automation. As a consequence, it becomes vital for modern organizations, first, to build more agile systems and second to adapt quickly to the highly competitive and dynamic market (competitive, new products and prices, new customers and preferences, etc ...). Actually, changes that affect business have many facets including government and legislation policies changes such as taxation laws, interest rates and environmental regulations. Last but not least, IT systems have drastic influence on how business operates and organizes its processes, e.g., projects outsourcing, online services, communications tools, storing data and extracting valuable information from it. Indeed, the business and its supporting IT systems are very inter-related and both must meet the requirements of the business ever-changing environment. In [START_REF] Diaz | Promoting business policies in objectoriented methods[END_REF], the authors highlight three components for the development of any business information system: data, process and policies. Whereas the first two have been integrated using the objectoriented paradigm, policies are commonly neglected and left implicit in the program code. In a business project, it is frequent to see business logic scattered over different applications in the information system [START_REF] Morgan | Business Rules and Information Systems: Aligning IT with Business Goals[END_REF] and paradoxically, business experts, who own the knowledge about business policies, have very limited access to the encoded business logic. The problem is worse when the business needs to change its operations and policies, and consequently the supporting IT system.

This results in high costs to adapt current IT systems to the changes that occur, as business logic is distributed all over different applications. Hence, conflicts occur between business owners and application developers in term of aligning IT with business.

Even the triggers used in active databases to express business policies as constraints were very limited and therefore, business policies that were hard-coded as procedures in SQL or COBOL fail to provide flexible systems and result in many maintenance issues [START_REF] Graham | Business Rules Management and Service Oriented Architecture: A Pattern Language[END_REF][START_REF] Knolmayer | Enforcing Business Rules by the Application of Trigger Concepts[END_REF]. The problem is identified as the missing link between high-level data architecture and project-level physical-database design or data-processing [START_REF] Appleton | Business rules: The missing link[END_REF]128]. One of the early answers to this problem consists of using object models to integrate and explicitly represent business policies in terms of rules [START_REF] Diaz | Promoting business policies in objectoriented methods[END_REF][START_REF] Poo | Implementing an evolutionary structural software model[END_REF][START_REF] Poo | Tartan: Interweaving objects with rules in information systems development[END_REF]128]. However, the most popular approach that continues to gain acceptance among business practitioners and researchers is known as the business rules approach [START_REF] Halle | Business Rules Applied: Building Better Systems Using the Business Rules Approach[END_REF][START_REF] Morgan | Business Rules and Information Systems: Aligning IT with Business Goals[END_REF]113]. This approach promotes Business Rules (BRs)

as an independent formalism to represent the business logic in terms of rules and manage them within centralized applications called Business Rules Management Systems (BRMS). The following paragraph further elaborates such an approach.

Business Rules Approach overview

When the term of business logic is invoked, it consists of all parts of the IT system responsible of specifying the schema that defines and processes the information flow in a database. This encompasses essentially constrains and policies that govern various aspects of business operations. Although the term of BR seems to appear first in [START_REF] Appleton | Business rules: The missing link[END_REF], where rules are identified as an independent component that links data architecture and data processing, such rules have been often conflated with constraints of the databases community or policies [START_REF] Graham | Business Rules Management and Service Oriented Architecture: A Pattern Language[END_REF]. Before defining what is a business rule, let us clarify first the business policy.

Definition 2.2.1 (Business policy). A business policy is a statement of directions

or guidelines that governs the decisions of an organization and controls its actions scope.

For instance, an insurance organization might have a policy saying :

Example 2.2.2 (Discount policy). All Platinum customers in Paris who place an order during the summer receive a 45 percent discount.

BRs have been given many definitions in the literature, albeit the most influencing was produced by the GUIDE Business Rules Project [START_REF] Hay | Defining business rules what are they really? Tech. rep[END_REF]. This latter aims at formalizing an approach, called the business rules approach, to identify and articulate the constraints that define the structure and control the enterprise operational decisions. Thus, the approach advocates enforcing business policies by translating and decomposing them into more specific statements, which will constitute BRs. the Business Rules Group (BRG) 1 promotes the independence principles of BRs in their seminal upshot Business Rules Manifesto [START_REF] Ross | Business Rules Manifesto[END_REF]. Accordingly, BRs should be managed separately and directly by business workers.

Finally, BRG has contributed to the work of the Object Management Group (OMG) to standardize the approach, which results in the emergence of the Semantics of Business Vocabulary and Business Rules (SBVR) standard [START_REF]Specifications: Semantics of business vocabulary and business rules[END_REF]. SBVR is a metamodel for developing semantics models in a business domain in the form of a vocabulary and a set of BRs. The following definition is an adaptation from [START_REF] Graham | Business Rules Management and Service Oriented Architecture: A Pattern Language[END_REF][START_REF] Ross | Business Rules Manifesto[END_REF] Definition 2.2.3 (Business Rule). A BR is a compact, atomic, well-formed, declarative statement that defines or constrains an aspect of the business and its collaborators. It must be expressed against a domain ontology (business policies vocabulary) in a natural-language that is understandable by whom it may concern, such as business and IT professional and customer.

BRs are the atoms that constitute a business policy and can be typically formulated via a set of conditions and actions. For example, the above business policy can be translated into the following two BRs. Finally, it is important to highlight the following aspects about a BR:

• Atomic structure: BRs cannot be reduced or decomposed into multiple or derived BRs, otherwise one can loose important information about the business.

• Business determination, in the sense that it must define or constrain some aspects of the business.

• BRs are under the 'business jurisdiction' and derived from its policy in the sense that they only regard what is under the company's authority to modify.

In the business rules approach, all BRs should be collected managed withing a central rule repository. The approach recommends the use of a business rule engine to execute rules directly rather than transcribing them into some procedural form [START_REF] Hall | The 2006 BPTrends Report on Business Rules Products[END_REF][START_REF] Ross | Business Rules Manifesto[END_REF]. Although different ways to implement the BRs approach might exist, using BRMSs remains the most economical one [START_REF] Graham | Business Rules Management and Service Oriented Architecture: A Pattern Language[END_REF]. In fact, BRMSs externalize BRs and provide facilities for a centralized management. Thus, BRs and other IT components have a separate life-cycle and yet they can easily communicate with each other. As a consequence, business workers benefit from direct access to BRs while collaborating more independently with IT developers. In [114], the authors emphasize that the business would need its BRs even if it had no software, which means that developing a BRs solution does not necessarily require a software development. Although this may implicitly attribute less importance to the technology behind, the approach promotes the use of BRMSs to support, better than any previous systems, the continuous and fast changes in the business environment. According to [START_REF] Boyer | Agile Business Rule Development -Process, Architecture, and JRules Examples[END_REF], a BRMS is a necessary component to ensure an agile BRs development and without which the BRs approach would not be fully implemented. Putting business first should not be understood as neglecting the technology that supports them, because real world experience shows that good technology can even shape BRs and significantly enhance time, quality and money outcomes of business projects. Therefore, adopting a BRMS will definitely build better, changeable systems faster that any previous approach [START_REF] Halle | Business Rule Revolution: Running Business the Right Way[END_REF]. Today the BRs approach has reached a good maturity. This is shown, on one hand, by several studies that appear to cover the subject [START_REF] Boyer | Agile Business Rule Development -Process, Architecture, and JRules Examples[END_REF][START_REF] Date | What Not How: The Business Rules Approach to Application Development[END_REF][START_REF] Graham | Business Rules Management and Service Oriented Architecture: A Pattern Language[END_REF][START_REF] Halle | Business Rules Applied: Building Better Systems Using the Business Rules Approach[END_REF][START_REF] Halle | Business Rule Revolution: Running Business the Right Way[END_REF][START_REF] Morgan | Business Rules and Information Systems: Aligning IT with Business Goals[END_REF]113]. On the other hand, by the increasing number of applications that implement it such as in banking, insurance, health care, retail and manufacturing. The next section gives more details about the basics of BRMSs.

Business Rules Management Systems

The separation of concerns principle is wildly adopted in software engineering. It is worthy of note that besides their declarative aspect in the the condition part, which is inspired from functional and logic programming, BRMSs have also a procedural capacity à la Java or C# in their action part. Such languages, which are based on the conceptual framework of Object Model (OM), have proven to be particularly well adapted to construct well-structured complex systems. In addition, this use of an object-oriented (OO) programming at the core of BRMSs has naturally emerged as a de facto standard from the most successful real business applications. This is because an OM encompasses essentially the principles of ab- for a customer. This latter might be related to many orders. An OM defines also the operations that can be performed, such as providing a discount or displaying a specific message. In this thesis we are only interested in OO-BRMS.

Features of a BRMS

A modern BRMS, be it commercial or open source, provides some common features including classical inter-operable modules.

• development environment (IDE) to edit rules and the underlying models. It also provides a graphical interface for non technical people to author rules.

An IDE can be integrated as a plugin in Eclipse for example.

• inference engine that is responsible of executing the rule against the facts base and performing actions. The execution is often based on the Rete algorithm and its enhancements, but also a sequential algorithm can be applied.

Engines operate essentially in a forward strategy, a backward or mixed strategy are also possible. • the rule base, which is a centralized and searchable repository to store and manage collaboratively BRs. Note that other alternatives to enter rules, exists such as decision tables, decision trees and rule-flows.

• support for rule flows and events processing to chronologically order business processes execution and specify transition time from one process to another.

For simplicity, a process can be regarded as a set of activities that will evaluate a set of rules. Most of BRMSs provide a graphical editor for creating flows and allows a drop and drag functionality.

• programming and execution environment are different from one BRMS to another. Every product has its own language to write rules technically, but all of them provide a mechanism to write in a natural language-like format.

The runtime is generally based on Java or .NET. Facilities for checking the rule syntax in real time and debugging do exist in modern BRMSs.

Mainstream BRMSs

The mainstream BRMSs include IBM ODM [START_REF]IBM: Operational Decision Manager[END_REF], Fair Isaac Blaze Advisor [START_REF]FICO: FICO Blaze Advisor Decision Rules Management System[END_REF],

Red [START_REF] Openrules | Open Source Business Decision Management System[END_REF] and Bosch Visual Rules [START_REF]BOSCH: Visual Rules[END_REF]. Comparing these systems is out of the scope of this thesis, we refer to [START_REF] Graham | Service Oriented Business Rules Management Systems[END_REF] for a comprehensive comparison including the first two of them. In addition, [START_REF] Graham | Service Oriented Business Rules Management Systems[END_REF] provides a multi-criteria decision analysis-based method to evaluate them. In particular, the author concludes that none of the leading BRMS products available today has any sophisticated facilities for managing or reasoning under uncertainty.

As we already mentioned, BRMS technology is heavily inspired from RBSs technology. RBSs have a key feature to manage effectively the business knowledge.

Notably, they ensure a clear separation between the declarative knowledge from the code that uses that knowledge to solve a specific problem or to satisfy a particular business requirement.

Rule-based Expert Systems

The story of BRMS technology is tightly linked to AI and all began with rulebased expert systems. These form a sub-area of AI that had flourished from mid-sixties till the end of the past century and still influences today AI technologies. Technically speaking, an expert system might be defined as a computer program designed to simulate, support or improve upon the decision-making process of a human expert in a specific area, where intensive knowledge is required.

So, an expert system can either replace the human expert, e.g., control systems in manufacturing or provides helpful insights to the expert, e.g., medical diagnosis. Particularly, one popular way to capture and store the knowledge in a RBS is in the form of production rules i.e., a set of implications having the form of "IF-THEN-ELSE" statements3 , that is why RBSs are referred to as production (rules) systems. Production systems were popularized by Newell and his collaborators while working on reproducing human reasoning and problem solving, see for example [START_REF] Laird | SOAR: An architecture for general intelligence[END_REF][START_REF] Newell | Human Problem Solving[END_REF]. The most influential programming language for these systems was OPS5 by Charles Forgy [START_REF] Brownston | Programming Expert Systems in OPS5: An Introduction to Rule-based Programming[END_REF][START_REF] Forgy | Ops5 user's manual[END_REF], which is written in LISP and uses the Rete algorithm [START_REF] Forgy | Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem[END_REF] to draw conclusions from rules. Actually, OPS5 was successful and surpassed other implementations due to its efficiency and capacity to scale up.

The potential of RBS, which has been first demonstrated and well-publicized by AI researchers, led to great successful applications. This success attracted many organizations to use RBS technology to the point that over two thirds of the Fortune 1000 companies during the eighties applied the technology to daily business activities. Furthermore, RBS applications have then proliferated even though the business, manufacturing and medical fields remained the dominant areas in which RBS are used [START_REF] Durkin | Expert Systems: a view of the field[END_REF]. At this stage, it is worth mentioning some of the early expert systems that influenced the course of AI. The seminal one is DENDRAL [START_REF] Buchanan | Heuristic DENDRAL: a program for generating explanatory hypotheses in organic chemistry[END_REF], a chemical RBS used to infer molecular structure from spectroscopic analyses. This RBS was a cornerstone in the history of expert systems and inspired the development of numerous RBSs that came later. The other one is MYCIN [START_REF] Buchanan | Rule Based Expert Systems: The Mycin Experiments of the Stanford Heuristic Programming Project[END_REF], which is perhaps the most famous one, is designed to diagnose bacterial infections in human blood. Other successful RBSs include XCON [START_REF] Barker | Expert systems for configuration at digital: Xcon and beyond[END_REF], which is written in OPS5 for configuring computer systems orders and was one of the first to be industrialized. Finally PROSPECTOR [START_REF] Hart | PROSPECTOR-a computer-based consultation system for mineral exploration[END_REF], a geological analysis system to discover rocks and minerals deposits. The common point between all these RBSs is their solving-problem power that comes especially from the encoded knowledge and this emphasized the crucial role of the knowledge base. Building expert systems for specific application domains has since then become a separate subject known as knowledge engineering, a term coined by Freigenbaum who is a key contributor to DENDRAL [START_REF] Feigenbaum | The fifth generation: Artificial Intelligence and Japan's computer challenge to the world[END_REF]. Broadly speaking, the very term "knowledge-based system" refers now to information systems, in which part of human knowledge is (symbolically) represented and reasoned about by mimicking human reasoning.

There are two important components that form any RBS, which can be expressed by the following equation : RBS = Knowledge Base + Inference Engine. A user interface is useful as a channel between the system and different users, e.g., an automatic way to enter/update knowledge by a human expert, a question-answer session or an explanation facility to help a user to understand the reasoning process or an action is made. Fig 2 .1. depicts the central components of a RBS where arrows reflect information flows

Knowledge Base Representation

There are two types of memories in a RBS : a long term and a short term memory. The first one corresponds to the Rules Base (RB) that contains the expert

RB = {R 1 , R
• f 1 = { the temperature of the room is more than 35 • }, • f 2 = {the curtain is open }, • f 3 = {the window is closed }, • f 4 = {the air conditioner is on}.
RBSs contain a mechanism to control the global coherence and assure the consistency of the knowledge base in order to prevent contradictory knowledge to reach the rule base . Particularly, it specifies constraints on assignable values w.r.t variables domain (coherence of facts) or detect contradictory rules (coherence of rules). The component that is responsible for drawing conclusions by applying the rules in RB to the WM facts is the inference engine, which is the aim of the next subsection.

Inference Engine

This component is the RBS's brain that matches rules in RB with WM known facts by applying a pattern matching algorithm. A rule whose condition part is satisfied by a fact is activated and is usually stored in an agenda, also called a conflict set.

When several rules are activated, the engine applies a solving procedure called conflict-resolution strategy to decide which rule to execute, the rule is then said to be fired. The simplest conflict-resolution strategy is, of course, just to apply the production rules in the order in which they entered the agenda. However, other heuristics might be applied to prioritize the set of activated rules in the agenda.

Then, the engine fires then rules beginning from the highest until no active rule is left. The inference engine processes the knowledge base in cycles, which have been given many names such as select-execute and recognize-act cycles. Algorithm 1

shows an example of the engine execution cycle. After updating the agenda, by either activating a rule if its conditions are satisfied by the current WM or removing it otherwise, the engine executes all activated rules and loops until no new active rule remains.

There exist many algorithms to implement RBSs, but the aforementioned Rete algorithm [START_REF] Forgy | Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem[END_REF] is the most influential one and is still used in modern rule engines.

The Backward Chaining This strategy is the reverse of the previous one. It is applied when we reason from conclusions and move backward to the facts that support them. If there are no matching facts, the conclusion at hand will be rejected and other will processed until a conclusion is obtained. Hence, this strategy is goal-driven as conclusions can be identified as goals to achieve. More precisely, a goal may match with a conclusion of one or more rules present in the knowledge base. All rules that match a certain goal are selected. In our example, assuming the goal to be f 3 , then the only selected rule is R 1 . Each one of the selected rules is subsequently processed by considering its conditions as new sub-goals to be achieved, where a sub-goal is achieved when the WM contains a fact supporting it. Otherwise, when a sub-goal finds no supporting fact, we recursively apply the same process by selecting rules whose conclusions correspond this sub-goal. In our example, since R 1 is the only selected rule, we get the new sub-goal f 4 , which in turn causes the selection of R 3 . When all the sub-goals, i.e., the conditions of the selected rule, have been achieved, then the rule conclusions are executed, which may cause the WM to change. In our example, since the WM contains the fact f 1 , the condition of the selected rule R 3 is satisfied, i.e., f 4 is achieved. Thus, R 3 is executed and f 4 is added, that is, W M = {f 1 , f 4 }. Finally, R 1 can be now executed as all its sub-goals, namely f 4 , are achieved. In a backward strategy, the engine selects only necessary rules to achieve initial goals and terminates the inference once they are achieved, that is why rule R 2 is not executed in our example even if its condition is fulfilled. This strategy, also called top-down inference, is suitable for diagnosis problems. An example of backward RBSs is the MYCIN diagnosis system.

User-System Interaction

The user-system interaction component allows RBS to communicate with users, which hereafter stand for end-users, knowledge engineers or domain experts. For example, it helps the knowledge engineer to develop and maintain knowledge base or to enter additional data. Another scenario may consist of displaying conclusions made by the system. Furthermore, different modes of user interfaces can range from simple command line to a sophisticated graphical user interface, but all modes should provide an easy and user-friendly experience. A good user interface hides the internal technical rules representation and presents them in an understandable form to users.

Another aspect of the human-machine interaction is to provide explanation facilities that explain or justify, in understandable and acceptable terms, the process followed by the system to reach conclusions. Providing such a feature was at the core of research from the beginning of expert systems and was considered as one of their most important characteristics that impacts the user experience acceptance [START_REF] Duda | Expert systems research[END_REF]135]. In a dialogue session, when the system prompts the user to enter some information and the user asks why, this facility may reveal which rule of the system is being used. Moreover, tracing activated rules and contents of the WM can be useful to answer how an action is reached. Another interesting explanation facility is the what-if analysis to explore alternate solutions using a hypothetical reasoning. However, simply tracing the activated rules or paraphrasing the chain reasoning does not help the user to easily understand the process employed by the system [START_REF] Moore | Participating in Explanatory Dialogues: Interpreting and Responding to Questions in Context[END_REF]. Actually, although the research community stressed the importance of explanatory capability, most early expert systems have only limited part of it and provide an explanation limited to a description of the reasoning steps [START_REF] Lucas | Principles of Expert Systems[END_REF]132]. This research area is fertile and still witnesses active efforts to overcome limitations of unsatisfactory explanations. According to [125], limitations stem essentially from the inadequacy of generating explanations directly from a very low-level representation (production rules), which fails to capture all the information needed for explanations and fails to distinguish the roles that different kinds of knowledge play. Relatively recent advances are concerned about building new architectures that capture more of the knowledge that is needed for explanation. The key idea is, on one hand, to enrich explicitly the system with dedicated and separate knowledge bases. On the other hand, to view explanations generation as a problem-solving activity that needs its own advanced techniques and architecture. Examples of these systems include the Explainable Expert System [125,[START_REF] Swartout | Explanations in knowledge systems: design for explainable expert systems[END_REF], which uses strategic knowledge about how the system is designed and how it reasons or the Reconstructive Explainer [START_REF] Wick | Second generation expert system explanation[END_REF], which reconstructs causal chains from a separate knowledge base to justify the reasoning path from inputs to answers. In another direction, [START_REF] Barzilay | A new approach to expert system explanations[END_REF] claims that making the distinction between reasoning knowledge and communication knowledge is theoretically appealing and allows to manage better the software engineering development of explainable expert systems. Finally we direct the reader to [START_REF] Darlington | Effectiveness of explanation facilities for intelligent systems[END_REF][START_REF] Moore | Explanation in expert systems: a survey[END_REF] for more detailed surveys and discussions of approaches to explanation.

Note that many efforts has been done to construct development environments as a general base for building specific expert systems. These environments are independent of the domain-specific knowledge and use a predefined formalism for knowledge representation and corresponding inference engine, which gave birth to what is known as expert system shells. First of them, the EMYCIN system [START_REF] Melle | A domain-independent production-rule system for consultation programs[END_REF] was designed by stripping MYCIN of its knowledge base. Nevertheless, most of the early expert systems were ad hoc and case specific applications, which were generally hard-coded in the LISP (LISt Processing) language.

Despite the optimism and early successes of expert systems, these often involve expensive development and maintenance costs. In [START_REF] Leith | The rise and fall of the legal expert system[END_REF] for example, it is argued that expert systems lack some validations and critical assessment because they are not widely tested and this raises legal and ethical issues. Finally, we want to emphasize that it is indubitable that early RBSs suffer from fundamental limitations when dealing with uncertainty [103] and these problems, among others, caused the emergence of a new class of expert system called probabilistic expert systems, a subject discussed in much details in in the next chapter.

Discussion and Conclusion

Although the term of imperfection is used by [START_REF] Smets | Imperfect information: Imprecision and uncertainty[END_REF] to include all types of uncertain or imprecise knowledge, the term uncertainty is often equivalently used. Unfortunately, it turns out that whereas BRMSs are well adapted to deal with structured and complete data by using classical Boolean inference, they face some difficulties when they take into account imperfect data [START_REF] Onisko | Comparison of rule-based and Bayesian network approaches in medical diagnostic systems[END_REF]. BRMSs must integrate mechanisms to handle the issue of uncertainties in the domain. To this aim, three approaches are commonly used in the RBS community:

• Heuristic models, which weight rules with a degree of truth, e.g., certainty factors (CF) and likelihood ratios (LR) [START_REF] Buchanan | Rule Based Expert Systems: The Mycin Experiments of the Stanford Heuristic Programming Project[END_REF][START_REF] Hart | PROSPECTOR-a computer-based consultation system for mineral exploration[END_REF]. These deal with uncertainty in the knowledge (rules) not the data. However probabilistic interpretation given to CF is incoherent with probability theory [START_REF] Heckerman | From certainty factors to belief networks[END_REF]. On the other hand, the conditional independence between evidence and rules actions in LR is seldom satisfied in real applications and LR-based expert systems have poor performance [START_REF] Ng | Uncertainty management in expert systems[END_REF].

• Fuzzy logic (FL) [START_REF] Zadeh | Fuzzy sets[END_REF] which describes imprecision or vagueness by associating variable values to fuzzy sets, a kind of moving from a bivalent logic to a fuzzy one. However, FL is not in essence designed to deal with incomplete data or to express relations between variables in the knowledge base as in OO frameworks. In addition, FL when applied to systems that perform chains of inference, such as BRMS, may lead to inconsistent conclusions [START_REF] Elkan | The paradoxical success of fuzzy logic[END_REF].

• Bayesian techniques, which are essentially based on Bayesian Networks (BNs) [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF], to consistently model domains with uncertainty. In addition, several algorithms have been proposed to learn their graphical structure and their conditional probability tables (CPTs) parameters. Even if they are a very popular tool to deal with uncertainty, BNs are not suited for complex systems, in which they involve high design and maintenance costs [START_REF] Koller | Object-Oriented Bayesian Networks[END_REF][START_REF] Mahoney | Network engineering for complex belief networks[END_REF].

Moreover, they do not support well object-oriented and dynamic systems.

One can also find hybrid approaches that combine, for instance, BNs with CF [START_REF] Bobek | Compact representation of conditional probability for rule-based mobile context-aware systems[END_REF][START_REF] Korver | Converting a rule-based expert system into a belief network[END_REF]. Obviously these methods incur some problems discussed previously. Moreover they are developed for specific uses and cannot handle effectively the frequent changes of business policies, where BRMS perform better. Another approach is Probabilistic Logic Programming [START_REF] De Raedt | Probabilistic (logic) programming concepts[END_REF]. But this is not suited for the BRs procedural side effects and the OO-BRMS upon which we build our application.

To summarize, this chapter introduces the business rules approach as a method-ology where BRs are regarded as first class citizen in the business operational decision management. The main technical implication of such an approach is the adoption BRMSs. We give a brief overview of such applications and we finally describe RBS as they represent their technical ancestors. Most of current BRMSs are based on the OO paradigm, that is why we are particularly interested in OO-BRMS. The aim of this thesis is to enhance these systems with uncertainty management capabilities. Again, in the light of SOA paradigm, we want to integrate a probabilistic reasoner as a service on top of current BRMSs implementations. To this purpose, we use Bayesian Networks and one of their OO extensions. The next chapter introduces such a framework.

Chapter 3

Bayesian Networks for Uncertainty Management

Introduction

In developing intelligent systems, it is inevitable to deal with the uncertainty that pervades real-world applications. As we discussed in the introduction, this issue has multiple origins such as measurement errors, noisy automatic processes, the modeling process itself, etc. Many approaches have been adapted to tackle this question, such as probability and possibility theories. For detailed surveys on these approaches, the reader might look at [START_REF] Halpern | Reasoning about uncertainty[END_REF][START_REF] Shafer | Readings in Uncertain Reasoning[END_REF][START_REF] Smets | Imperfect information: Imprecision and uncertainty[END_REF].

One interesting approach that is well suited is called Probabilistic Graphical Models (PGMs) [START_REF] Jordan | Graphical models[END_REF][START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF][START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]. This framework combines graph theory with probability theory to represent and reason with complex and real-world data. It has now become a very popular and dominant tool for reasoning under uncertainty in the AI field. PGMs earn such a popularity for many reasons. First, their graphical structure allows them to capture conditional independence properties of a joint probability distribution. This allows for a compact factorized representation of the distribution and provides sophisticated methods for automated reasoning. Second, their representation is natural and human readable, allowing even non experts to understand the conditional interactions between the variables of the domain.

Lastly, the framework is based on rigorous probability calculus that makes the framework mathematically sound. The construction of the joint probability distribution permits to probabilistically draw useful conclusions about one or more variables of the domain knowing some observations about other variables. This technique covers a large spectrum of interesting queries. For example, in a printer troubleshooting application, the specification of the joint distribution of the components and device status allows the computation of the posterior probability that the device will work properly, given some observations of the device behavior.

However, specifying the distribution over a high-dimensional space of variables appears intractable since the size of such distribution grows exponentially with respect to the domain size. That is exactly where PGMs play an extremely interesting role to encode such complex distributions in a tractable manner. For the purpose of this thesis, we are interested in directed PGMs that are called Bayesian Networks (BNs) [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF][START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]. In this chapter, we are interested in the BN framework and its OO extension, the so called Probabilistic Relational Models (PRMs). We discuss also a graphical test for deciding which conditional independence relations are implied by the structure of the BN

Bayesian Networks

Definition and Design

BNs [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF][START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] were proposed in the late 80s and rapidly became one of the most popular framework to reason under uncertainty in AI and expert systems. BNs1 are used in a wide range of real-world applications, including medical diagnosis, risk management, fraud detection and clinical decision support [START_REF] Darwiche | Modeling and Reasoning with Bayesian Networks[END_REF][START_REF] Wiegerinck | Bayesian networks for expert systems: Theory and practical applications[END_REF].

As a directed PGM, the core of a BN representation is a directed acyclic graph (DAG) whose nodes2 represent random variables (e.g., the status of a device, the occurrence of an event) and whose arcs represent probabilistic dependencies (cause, influence, information flow, etc) between these variables of interest. This enables them to encode compactly the joint probability P over their nodes as the product of the conditional probabilities of the nodes given their parents in the DAG. This compact factorization of P into local distributions is known as the chain rule of BNs and is similar to the chain rule of conditional probabilities: Definition 3.2.1 (Chain rule of BNs). let G = (V, A) be a directed acyclic graph over a set of random variables V (continuous or discrete), where A is a set of arcs.

We say that a joint probability distribution P factorizes over G if P is defined over

V and can be written as the following product:

P(V) = X∈V P(X|Pa(X)) (3.1)
where Pa(X) denotes the set of immediate ancestors (parents) of X in G. Now we can define more formally the BN as follows:

Definition 3.2.2 (Bayesian Network). A BN is a pair (G, P), where G = (V, A)
is a DAG and P is a joint probability distribution that satisfies the chain rule 3.1.

In practice, P is given as the set of local conditional probability distributions of the variables given their parents in the DAG : Θ = {P(X|Pa(X)) : X ∈ V}.

Whereas the joint size grows exponentially with the BN size, the total number of parameters is in general bounded by |V| × v p+1 , where v and p are bounds on the domain sizes of the variables and on their number of parents respectively. In the rest, we are interested in discrete BNs, i.e., variables in V are discrete, and we will rather use the term conditional probability tables (CPTs). To illustrate these concepts, we use the example from [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF]:

Example 3.2.

(The Student Example).

A company wants to hire recently graduated intelligent students based on their recommendation letters, which reflect the student grade in a particular course, and SAT scores, which reflect the student intelligence.

The process of modeling with BNs follows in general two steps, which will be emphasized through the example. The goal is then to develop a BN to capture the knowledge from the domain problem at hand and use it to help a decision process:

D I G L S J

Quantitative step

This phase concerns the probability assessment by building the so called network parameterization Θ, i.e., to each variable of G, we associate a CPT that quantifies its relationship to its parents in the DAG. In the absence of the parents, we only specify a prior probability distribution. As we see, the advantage is that, instead of specifying the whole P, we only need to specify more compact local CPTs and we are able to get significant savings, for instance in our running example, instead of storing 2 6 = 64 entries, all we need is 2 + 2 + 2 3 + 2 2 + 2 2 + 2 3 = 28 entries. Once constructed, a BN can be used to efficiently answer different probabilistic queries such as the computation of most probable explanations (MPE), maximum a posteriori (MAP) and the conditional probability. For instance, in the student example, P(S = low|I = high) can help us to update our opinion about a student score knowing he is highly intelligent. We direct the reader to Section 3.2.3 for more details about techniques for querying a distribution based on BNs.

Until now, we focused on the compact representation of P that is ensured using local CPTs. On top of that, the BN also encodes some local independencies, that is why we previously called G the independence structure. The intuition behind this semantics is that a variable depends directly only on its parents, its children and their parents. We formalize this intuition throughout the next section and we will see that the formal semantic of a BN corresponds actually to a set of conditional independence assertions.

Graphical Semantics

The DAG also compactly represents a set of independence statements, which are visualized through the existence/absence of arcs in the DAG. This notion is actually an intrinsic property of the induced joint probability P that goes beyond the simple graphical representation. It is a characteristic of probabilistic conditional independences. All the following definitions assume a given P that is decomposable according to a DAG G. The latter is composed of a nodes set V that corresponds to a set of random variables and A a set of arcs between these nodes. Capital letters will denote nodes or variables and lower-case letters will denote their values or assignments. Finally, boldface letters will denote sets of variables. Definition 3.2.4 (Probabilistic Conditional Independence [START_REF] Dawid | Conditional independence in statistical theory[END_REF]). Let X,Y,Z ⊂ V, we say that X is conditionally independent of Y given Z, w.r.t P, and we write (X⊥ P Y|Z), iff: P(X, Y|Z) = P(X|Z). When Z = ∅, we say that X and Y are marginally independent and we write (X⊥ P Y). The variables in Z are often said to be observed.

The intuition behind this definition is that two sets X and Y are conditionally independent given a set Z when, given our knowledge about this latter, our belief on X is not influenced by any knowledge we learn about Y. Before drawing the link between this definition and the graphical representation, let us first introduce some graph theoretic notions.

Now, X ∈ V is said to be a parent of Y ∈ V if the arc (X, Y ) is in A.
The set of all parents of a node X is denoted as Pa G (X). We can omit subscript G when there is no ambiguity about the DAG at hand.

Definition 3.2.5 (Trail ). {X 1 , . . . , X n+1 } ⊂ V is said to be a trail in G = (V, A) if (X α , X α+1 ) or (X α+1 , X α ) are in A for all α ∈ {1, . . . , n}. When only (X α , X α+1 ) ∈ A for all α the trail is called a (directed) path from X 1 to X n and denoted X 1 -X n .
For instance, Fig. 3.4a (resp. Using these notations, the already mentioned independence statements can be encoded graphically by the BN as follows:

Definition 3.2.7 (Markovian Assumption). In the BN (G, P), every node is conditionally independent of its non-descendants given its parents in DAG G:

∀X ∈ V, ({X}⊥ P NonDescendant(X)|Pa(X)) (3.2)
For instance, the Markovian assumption states that {L}⊥ P {S, I, D}|{G} in Fig. 3.5 It is important to emphasize that one can prove that having a joint distribution P, which obeys Markovian Assumption 3.2 is equivalent to say that P satisfies the chain rule of BNs 3.1 [START_REF] Cowell | Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks[END_REF]. This also implies that every independence statement derived using such an assumption is necessarily satisfied by P. However the inverse is not always true, there might be other independences that are only satisfied by P and not expressed by the Markov property.

Given a variable X ∈ V, only a subset of variables, called the Markov blanket of This means that any instantiation Y = y such that Y / ∈ MB G (X) does not impact our belief on X once we know the values of the variables in MB G (X).

In other words, X is separated from the rest of the network by MB G (X). For instance, in the student DAG 3.6, the Markov blanket of variable L (dashed node) is composed of the red nodes, i.e., MB G (L) = {G, J, S}

In this chapter, we restrict ourselves to the independences that are derived from the DAG using Assumption 3.2. We refer to [START_REF] Dawid | Conditional independence in statistical theory[END_REF][START_REF] Pearl | Graphoids: Graph-Based Logic for Reasoning about Relevance Relations or When would x tell you more about y if you already know z?[END_REF], where one can be guided by set of properties called the graphoid axioms for conditional independence, to infer additional independences from P.

Using these axioms to find conditional independences may be fastidious. Fortunately, there exists a graphical test called d-separation (directional separation) [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] that allows us to efficiently detect the independences implied by these axioms and those entailed by the Markov assumption. This test is intuitive and is much easier to exploit by human reasoning than the graphoid axioms. Given three disjoint sets of nodes X,Y,Z ⊂ V, the d-separation criterion graphically detects whether X is independent of Y given Z by testing whether every trail between X ∈ X and Y ∈ Y is blocked by Z. Hence, let us first define the notion of blocked trails.

Moreover, the notion of blocked trail helps us to see the probabilistic influence as a flow of information in the graph. Given the set of nodes Z, a trail is blocked whenever it contains a closed two-arc trail given Z, otherwise the trail is said to be active. So, what is a closed two-arc trail? Depending on the type of the two-arc trail, we will be able to determine whether the trail is closed or not. Consider a two-arc trail {X 1 , X 2 , X 3 }, this can have three forms:

1. Sequential:

(a) X 1 → X 2 → X 3 when {X 1 } ⊆ Pa(X 2 ) and {X 2 } ⊆ Pa(X 3 ). (b) X 1 ← X 2 ← X 3 when {X 3 } ⊆ Pa(X 2 ) and {X 2 } ⊆ Pa(X 1 ). X 1 X 2 X 3 (a) X 1 X 2 X 3 (b) 2. Convergent, aka v-structure X 1 → X 2 ← X 3 when {X 1 , X 3 } ⊆ Pa(X 2 ). X 1 X 3 X 2 3. Divergent, X 1 ← X 2 → X 3 when {X 2 } ⊆ Pa(X 3 ) and {X 2 } ⊆ Pa(X 1 ).
Then, table 3.1 summarizes when a two-arc trail is said to be closed given a node set Z. For instance, in Fig. 3. This weaker notion of completeness is telling us that one cannot improve on the d-separation test, i.e., this criterion discovers all the independences that one can derive from the DAG [START_REF] Geiger | Graphoids: A Qualitative Framework for Probabilistic Inference[END_REF]. As a consequence, the set of independences that is expressed by the Markovian assumptions are the maximum that we can derive from the independence structure. In other words we have the following theorem: Theorem 3.2.12 (Dependent variables [START_REF] Darwiche | Modeling and Reasoning with Bayesian Networks[END_REF]). Given a DAG G, X and Y are dependent given Z in some distribution P that factorizes over G if X and Y are not d-separated given Z in G.

7 trail {X, X 1 , X 2 , X 3 , X 4 , Y } is blocked given X 1 X 3 X 2 a trail {X 1 , X 2 , X 3 } closed given Z? Sequential and Divergent X 2 ∈ Z Convergent {X 2 }, Descendant(X 2 ) ⊂ Z
Finally, we would like to emphasize that there exist other equivalent and yet simpler methods to test independences in BNs, such as Markov separation [START_REF] Lauritzen | Independence properties of directed Markov fields[END_REF] and u-separation [START_REF] Butz | A simple method for testing independencies in bayesian networks[END_REF].

Reasoning with BNs

A BN can be considered as a probabilistic knowledge base, in which the process of querying is called inference. In fact, inference is the main task behind constructing a BN. The general form of the probabilistic inference is P(Q|E=e), which reflects the following human reasoning question: suppose we observe e on a subset of E of the domain, what are the probability values that another subset Q can take?

Q is called the query or target and E=e is called an observation or evidence.

Querying the distribution

We present here the most common types of probabilistic queries:

Marginal distribution can be viewed as the projection of P on a smaller subset of variables by marginalizing out over the other variables. When Q, E = ∅, the query is called the posterior marginal of Q given the knowledge on observed variables E. It is called also the conditional probability query. In the sequel, x will be used to denote the assignment X = x. Answering the marginal distribution query involves the computation of both the joint distributions P(Q, e) and P(e) as :

P(Q|e) = P(Q, e) P(e) (3.3)
Both distributions can be computed by marginalizing out the variables in W = V \ Q ∪ E. In this case, the numerator can be computed by summing out over W , P(Q, e) = w∈W P(Q, e, w), while the denominator, which is called the probability of evidence, can be deduced from the previous equation by

P(e) = q∈Q P(q, e)
When E = ∅, the distribution P(Q) is called prior marginal.

Most Probable Explanation (MPE)

This class of probabilistic queries tries to find the most probable instantiation of query variables Q = V \ E given the evidence E = e. To put it another way, this amounts to find the assignment of Q that maximizes P(Q|e) i.e., computing the quantity :

argmax q∈Q P(q|e) Maximum A Posteriori (MAP)
This is a more general case in the sense that while Q covers all non evidence variables in MPE, it is now just a subset of variables for which we therefore seek to find a high-probability joint assignment. It is also called the marginal MAP, because this involves both marginalizing out some variables and computing some ArgMax on others. More precisely, if W = V \ {Q ∪ E}, this amounts to compute:

Probabilistic inference

Several algorithms were proposed in the literature to answer efficiently and reduce computations amount of the previous queries. By essence, the inference problem is simple. However, as we noticed, the challenging part is the sum computations over combinations of values, whose number is exponential in the number of variables.

A straightforward computation of the sum is therefore only feasible when this number is not very large, otherwise the problem becomes intractable. Broadly speaking, we can classify inference algorithm into two categories. First, exact inference algorithms, including elimination and conditioning algorithms. Second, approximate inference algorithms.

Historically, the first exact algorithm to get every node's marginal probabilities has been proposed in [START_REF] Pearl | Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach[END_REF] and was valid only for trees. Its extension to poly-trees, also called singly-connected networks, was proposed in [START_REF] Kim | A Computational Model for Causal and Diagnostic Reasoning in Inference Systems[END_REF]100] and was known as the poly tree algorithm. The algorithm is based on a message-passing protocol, in which a node is entitled to propagate a message only after it has received messages from its neighbors except from the receiving node. In viewing the BN as a causal structure, every distribution over a node is viewed as a belief in that node, that is why it is common to call this algorithm belief propagation. Note that its complexity is linear in the size of the network. The two main approaches to extending this algorithm to general (multiply-connected) networks are the cyclecut set algorithm, also known as loop cutset conditioning [START_REF] Pearl | A Constraint-Propagation Approach to Probabilistic Reasoning[END_REF][START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF], and join or junction tree algorithms [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their applications to expert systems[END_REF].

The first approach tries to reduce the structure to a poly-tree, where it is possible to apply the poly-tree algorithm, that is, the algorithm tries to solve the problem under the condition of instantiating some variables and repeating this for all possible values of the variable. It is clear that this technique yields to multi-ple calls of the poly-tree algorithm since conditioning on enough variables (loop cut set) makes the structure a tree The final solution can then be re-constructed by aggregating the computations performed from each poly-tree algorithm call. A more advanced technique known as recursive conditioning, tries to split recursively the network into disconnected sub-networks to be solved by classic conditioning.

Unfortunately, this kind of inference algorithm is known to be very time consuming and might yield to higher complexity in some complex networks, even if we can control such a complexity in general.

In another direction, a second approach called the join tree algorithm was proposed in [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their applications to expert systems[END_REF][START_REF] Madsen | Lazy propagation: A junction tree inference algorithm based on lazy evaluation[END_REF]120] and became one of the most popular exact inference algorithms.

Basically, this algorithm transforms the initial BN into a corresponding join tree, which is a secondary structure obtained from clustering the BN nodes into cliques.

Probabilistic inference is then based on passing messages through the join tree.

This algorithm proves to be efficient and is considered one of the state of the art algorithm. That is why it is the most widespread algorithm to implement exact inference in practice. Another alternative is the variable elimination algorithm [START_REF] Dechter | Bucket Elimination: A Unifying Framework for Probabilistic Inference[END_REF][START_REF] Zhang | A simple approach to Bayesian network computations[END_REF], which is based on the simple technique of eliminating non query and evidence variables. The algorithm initializes a set of factors with the BN CPTs, then, each time a variable needs to be eliminated, the product of factors that mentions that variable is computed. The variable is then marginalized out from the combined factor. By repeating this elimination process until no more variables need to be removed, one can obtain the marginal distribution over any subset of variables. The performance of such an algorithm is very related to the elimination order of the variables and finding an optimal elimination order turns out to be is a NP-Hard problem [START_REF] Bodlaender | A tourist guide through treewidth[END_REF][START_REF] Kjaerulff | Triangulation of graphs -algorithms giving small total state space[END_REF].

In general, it is known that the probabilistic inference is a NP-hard problem [START_REF] Cooper | The computational complexity of probabilistic inference using Bayesian belief networks[END_REF][START_REF] Dagum | Approximating probabilistic inference in Bayesian belief networks is NP-hard[END_REF] and it turns out that variable elimination and join tree algorithms are very related 3and have the same space and time complexities, which are exponential in the treewidth, i.e., the size of largest cluster in the join tree minus one.

The join tree algorithm has some attractive properties. On one hand, it can be seen as a sophistication of variable elimination algorithm that allows simultaneous eliminations of many variables. On the other hand, it is able to compute multiple marginals at once [START_REF] Darwiche | Inference in Bayesian networks: A historical perspective[END_REF]. These properties are interesting for our context, where we deal with multi-target systems. That is why this thesis is particularly interested in the join tree algorithm. We refer to the next Chapter (4) for a detailed description of how such an algorithm works. But now let us emphasize the fact that there exist also many other approaches to inference different from the aforementioned techniques. In particular efforts have been done to exploit the BN local structure in order to represent more compactly factors and speed up the inference, see for example [START_REF] Allen | New Advances in Inference by Recursive Condi-tioning[END_REF][START_REF] Bahar | Algebric decision diagrams and their applications[END_REF][START_REF] Darwiche | A Logical Approach to Factoring Belief Networks[END_REF][START_REF] Sang | Performing Bayesian Inference by Weighted Model Counting[END_REF]. Even if these methods offer a promising ground for improving inference, they suffer from theoretical justifications regarding their complexity and the savings they might offer [START_REF] Darwiche | Inference in Bayesian networks: A historical perspective[END_REF].

Finally, it turns out that exact inference can be intractable and in this case various approximation methods try to find iteratively an approximation from random samples of instantiations. We recall briefly some of these techniques, as this subject is not treated in this thesis. For example, belief propagation can be used to search an approximation of the probability distribution and then uses optimization techniques to minimize an error function [START_REF] Kim | A Computational Model for Causal and Diagnostic Reasoning in Inference Systems[END_REF][START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]. There are also other popular methods of approximate inference that are based on stochastic sampling, that is, estimating the probability using a frequentist approach. The most famous ones are Markov Chain Monte Carlo methods, which include Gibbs sampling and Metropo-lis Hastings algorithms [START_REF] Pearl | Evidential reasoning using stochastic simulation of causal models[END_REF]111] that are used for generating samples from the posterior distribution. Importance Sampling is another approach that randomly samples another distribution and modifies these samples in such a way that they provide a good estimate of the distribution of interest, see, e.g., Likelihood weighting [118]. For a good grasp on these methods, the reader might find more details in [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF] or [START_REF] Darwiche | Modeling and Reasoning with Bayesian Networks[END_REF].

Probabilistic Relational Models

When dealing with complex and large systems, BNs do not seem to be well adapted.

Indeed, the cost of designing and maintaining such systems becomes high [START_REF] Koller | Object-Oriented Bayesian Networks[END_REF][START_REF] Mahoney | Network engineering for complex belief networks[END_REF] and the inference might be intractable. A complex system may induce a big number of probabilistic dependencies that can, not only lead to intractable modeling costs, but also implies important update costs when changes occur in the underlying structure. Actually, every time an entity and/or a relation in the domain changes, a new BN should be defined. Such shortcomings are essentially due to the fact that BNs completely ignore the concept of objects and their interactions. To cope with the aforementioned problems several extensions were proposed in the literature, among which, one can find the following:

• Object-oriented extension, such as Object-Oriented BNs [START_REF] Bangsø | Object oriented Bayesian networks: A framework for topdown specification of large Bayesian networks and repetitive structures[END_REF][START_REF] Koller | Object-Oriented Bayesian Networks[END_REF][START_REF] Mahoney | Network engineering for complex belief networks[END_REF] • First Order logic extension, such as Markov Logic Network [START_REF] Jaeger | Relational Bayesian Networks[END_REF][START_REF] Kersting | Interpreting Bayesian logic programs[END_REF] • Relational models such as Entity-Relationship [START_REF] Heckerman | Probabilistic Entity-Relationship Models, PRMs and Plate Models[END_REF][START_REF] Laskey | MEBN: A language for first-order Bayesian knowledge bases[END_REF].

In this thesis, we are particularly interested in Probabilistic Relational Models (PRMs) [START_REF] Bangsø | Object oriented Bayesian networks: A framework for topdown specification of large Bayesian networks and repetitive structures[END_REF]106], an extension of the BNs attribute-based representation that combines the OO paradigm with the relational representation in database theory.

Hence, PRMs specify a generic template defining a probabilistic model, a set of dependencies, that hold in a relational domain, which can be represented by a relational database. The OO paradigm helps to abstract and capture general properties about similar entities in the domain in terms of classes having similar properties and can be instantiated for specific contexts as many times as suited.

While the relational model helps to describe interactions or relationships between classes and their instantiated objects. To understand these concepts and give more formal definitions, we use the PRMs version described in [START_REF] Torti | Inférence probabiliste structurée dans les modèles graphiques probabilistes orientés-objet[END_REF].

For the illustration purpose, let us consider Fig. The mechanism of reference slot can be applied recursively to allow one attribute to access attributes of different classes by navigating through other classes, we call this path of reference a slot chain.

It is important to highlight that class attributes are a generic template for random variables, and in that way they differ from their instantiations that are instances i 1 and i 2 of a same class C, the number of parents of random variable i 1 .X differs from that of i 2 .X. This is the case, for example, when i 1 .X and i 2 .X refer to SAT scores of two different students who did not follow the same courses, the parents of these variables being these courses. In this case, the precise set of parents of an attribute cannot be determined precisely at class level, which implies that a standard CPT cannot be provided for v ariable X in Class C. A(S), the set of all instance attributes in S, as the following product:

P(A(S)) = C∈C i∈I S (C) i.X∈A(i) P(i.X|Pa(i.X)) (3.4)
Definition 3.3.9 (Ground BN [START_REF] Getoor | Introduction to Statistical Relational Learning, Adaptive Computation and Machine Learning[END_REF]). Given a PRM Π = (C , S), its associated ground Bayesian Network is a BN constructed using the following steps:

1. There is a node for every attribute i.X of every instance i ∈ S, named i.X.

Each i.X depends probabilistically on parents of the form i.Y or j.Y such

that there exists a slot chain K with j ∈ range(i.K).

i.X's conditional probability distribution is a CPT

Conclusion

In this chapter we introduce BNs, a well-established framework to represent and reason under uncertainty in IA. Furthermore, we present some of their graphical properties, notably the graphical independences they encode and we relate this to the conditional independences of the induced joint probability distribution. We also give a graphical criterion, called d-separation, that reveals all independence statements from the BN structure. Finally, observing that BNs might suffer from some limitations, we present PRMs, an object-oriented extension of BNs, that allow BNs to scale up to complex large systems.

We previously saw in Chapter 2 that techniques used to quantify uncertainties in the RBS domain have theoretical and practical limitations. We believe that this could be overcome by exploiting a probabilistic reasoning. In this context, BNs could prove to be useful, particularly their PRM extension. The reason why we are interested in PRMs is twofold. First, PRMs provide a mathematically sound framework and integrate the OO paradigm and relational models. This allows BNs to scale up and their inference to speed up. Second, modern BRMSs are based on the OO paradigm and their knowledge bases have several connections with relational databases. Additionally, probabilistic inference engines, notably those based on the junction tree algorithms, seem to be good candidates to speed-up the rules inference, as they allow querying multiple targets at the same time. However, the rule engine queries of the WM are, by essence, incremental and frequent, hence, the probabilistic inference shall also be performed incrementally. In the following chapter, we investigate a new approach to extend BNs inference to the context of modern BRMSs.

57

Chapter 4

Incremental Junction Tree Inference

Introduction

In a BRMS, interactions with the WM are dynamic and incremental. Moreover, the WM is by essence, multi-targets, which means that it contains many query variables. As a consequence, if we are to integrate a probabilistic feature based on the PGM framework, the probabilistic inference has to take this property into account. However, this is a challenging task in general. Actually, when the system, its evidence and/or its targets evolve, most of probabilistic inference algorithms either recompute everything from scratch, even though incremental changes do not invalidate all the previous computations, or they do not fully exploit incrementality to minimize computations. The very idea of taking advantage of previous computations to optimize the current ones is not new. For example, [START_REF] D'ambrosio | Incremental probabilistic inference[END_REF] defines an incremental system that can make use the results of previous computations to reduce the cost or improve the quality of results for subsequent computations.

Four incrementality criteria relevant to probabilistic inference were then identi-fied: incrementality w.r.t (time) resource, queries, evidence and representation.

In this chapter, we are interested in all these aspects, especially in the last three ones. Surprisingly, very few inference algorithms address all these aspects. For example, [START_REF] Madsen | Lazy propagation: A junction tree inference algorithm based on lazy evaluation[END_REF] exploits partially the incrementality, but it is far from optimal when the set of targets is smaller than the set of all the random variables or when this set changes. In [START_REF] Darwiche | Dynamic Join Trees[END_REF], for instance, the query point of view is taken into account by reconfiguring dynamically some join trees (JT) when queries change but the BN structure is assumed to remain static, which may not necessarily be the case in rule-based systems. In [START_REF] Lin | Relevance-Based Sequential Evidence Processing in Bayesian Networks[END_REF], the authors exploit relevance-based reasoning to identify the parts of the network that are relevant for computations and, then, update several subnetworks whose union covers the original one. Unfortunately, this algorithm does not take into account computations performed previously. In [START_REF] Madsen | Lazy propagation: A junction tree inference algorithm based on lazy evaluation[END_REF], an incremental JT-based inference algorithm has been proposed that exploits independences induced by incremental evidence updates. But the JT structure never evolves and it is assumed that all the nodes are targets, which is not optimal in our context. On the opposite, the incremental JT structure is addressed in [START_REF] Flores | Incremental Compilation of Bayesian Networks[END_REF] but not the queries incrementality nor the exploitation of previous probabilistic computations.

Another direction is investigated in [START_REF] Li | Performing Incremental Bayesian Inference by Dynamic Model Counting[END_REF], where authors argue that compiling the original BN into a conjunctive normal form (CNF) coupled with caching techniques improves inference when the network structure is updated. But this does not take optimally into account evidence and queries. Along similar lines and in the context of logic programs, [START_REF] Vlasselaer | Tp-compilation for inference in probabilistic logic programs[END_REF] proposes an online inference that allows updating the set of facts while keeping the set of (logic) rules intact. At the end, the process comes down to adding or removing clauses in the corresponding logic program. This is obviously a non PGM-based approach that deals only with a particular case of incrementality, that which is of evidence. Indeed, our framework is to be integrated within a BRMS where the rules have side-effects on the facts in opposition with logic programs.

This chapter tries to avoid the previous limitations, as they may incur strong unnecessary overheads when the system under study is large. In order to alleviate the question of incrementality, we introduce a new junction tree-based messagepassing inference algorithm that, given a new query, minimizes computations by identifying precisely the set of messages that differ from the preceding computations. Additionally, our algorithm takes advantage of computations sharing within junction tree algorithms to answer multiple queries.

In the sequel, B = (G, Θ) stands for a BN and for any graph G, we use the notation V(G) and E(G), to express the set of its vertices/nodes and edges respectively.

Finally, T will refer to a junction tree (see below) associated with B.

Junction Tree algorithm

This section provides a concise overview of the join tree algorithm, where inference is based on a message-passing algorithm within the so called secondary structure called junction tree (JT). Let us first present a general description of the algorithm before introducing formal definitions. The JT of B is obtained after converting DAG G into an undirected graph as follows. First, for each node in V, we add edges between all of its parents, this step is called moralization and its result is the moral graph. Second we remove the orientations of the remaining arcs and we add edges in the resulting undirected graph so that, in every cycle of at least four nodes, there exists a pair of nodes non-adjacent in the cycle but adjacent in the undirected graph; this step is called the triangulation and the resulting undirected graph is called the triangulated graph. We recall the DAG from of Student Example 3.

(Clique graph). A clique graph U for an undirected graph G is

an undirected graph such that each of its nodes i is mapped to a clique C i of G.

In addition, for every pair of nodes i and j such that C i ∩ C j = ∅, i and j must belong to the same connected component, i.e., there must be an undirected path linking these nodes in U.

If we use natural numbers to represent V(U), then C i represents the contents of ith node. We also call V(U) and E(U) clusters and separators respectively.

In a JT based algorithm, U must satisfy the so called running intersection property to be be ready for inference.

Definition 4.2.3 (Running intersection property). Let T be a clique tree. We say that T satisfies the running intersection property if any non empty intersection of two cliques belongs to every clique in the unique path between those two cliques.

Since C i ∩C j = ∅, for (i, j) ∈ E(U), we call such intersection a separator, noted S ij , and we will label (i, j) with S ij . Now, let us put Definition 4.2.3 another way, the property says that whenever we have a variable X ∈ S ij , X is also in every clique in the path that link i and j in U. Now we have all ingredients to define the JT.

Definition 4.2.4 (Junction Tree). A junction tree is a clique tree that satisfies the running intersection property 4.2.3.

Since there are different ways to triangulate the moral graph, the JT representation is not unique. For instance, Fig.

:= k ∈ V(T ) : (i, k) ∈ E(T ) .
Then the JT algorithm is based on the idea of passing factors between adjacent nodes using a message passing protocol. For (i, j) ∈ E(T ), let ψ i→j denote the factor that is associated with Separator S ij and represent the message sent from i to j over S ij . Note that since messages will be sent in both directions, we distinguish between ψ i→j and ψ j→i . In practice, T will also store the factors of cliques and separators. For instance, in In order to guarantee the correctness of computations, the message-passing protocol says that the message ψ i→j should not be sent in an arbitrary manner, but it is computed only when clique i has received messages from all its neighbors except from j. The goal of exchanging a message from node i to j in the junction tree is to propagate some information that is known to i but not to j toward j.

After propagating all the messages, all nodes j have received sufficient information about the other nodes in the JT to be able to compute the joint posteriors of C j .

One way to organize messages computationis to perform it in two phases, namely a Collect, using Algorithm 2, and a Distribution, using Algorithm 3 from a predetermined root r ∈ V(T ). During the first phase, messages are sent along edges from leaves toward r and, during the second phase, they are sent in Algorithm 2: Collect Input : an initialized JT T and i, j ∈ V(T ) In the next section we develop an extension of the JT algorithm.

Output: Updated ψ i→j 1 φ ← φ i for k ∈ Adj(i) \ {j} do 2 Collect(k, i) 3 φ ← φ × ψ k→i 4 ψ i→j ← X∈dom(φ)\S ij

Incremental Junction Tree Inference

This section investigates a new approach to overcome the shortcomings discussed in the introduction section (4.1). It aims at improving the efficiency of inference for very large and dynamic systems. The key idea of our algorithm, called Incremental Junction Tree Inference (IJTI ), consists of restricting the computations only to parts of the JT that are relevant to targets and that have been invalidated by For instance, in Fig. 4.6, Adj r (i) = {k 3 } and Adj r (k 3 ) = {r}. Finally, let V -j (i) stands for the set of nodes of the maximal subtree in T that contains i and not Adj j (i), and let V j (i) = V -j (i) ∪ {j} (see the shadowed area in Fig. 4

j i k 1 k 3 r k 4 k 2 Vj (i)

.6).

A message ψ i→j sent within T is directed by nature. It propagates toward j (and, by induction, toward V -i (j)) all the relevant information coming from the cliques in V -j (i), notably all the evidence they received (by abuse, we say that a clique received evidence when at least one of its random variables received evidence). As a consequence, if ψ i→j has already been computed previously and no new evidence has been received nor structural changes occurred in V -j (i), there is no need to recompute it. But even if V -j (i) received evidence, ψ i→j needs not be computed/updated if V -i (j) contains no target. In this case, ψ i→j 's state becomes "invalid" since the content of ψ i→j is now incorrect. This is not an issue for the current inference but, for future ones, we have to take this state into account to recompute ψ i→j if it is to be used. Let A(T ) be the set of all arcs induced from E(T ), taking into account orientations, i.e., A(T ) := (i,j)∈E(T ) {(i, j)} ∪ {(j, i) .

To formalize the above conditions, we begin with characterizing the information that is "local" to i and j. By local we mean information that only depends on the content or state of i and j:

Definition 4.3.2 (Local label-message λ). λ : A(T ) → 2 { ,T } is a function s.t. (i, j) -→ λ i→j :=                            { } if ψ i→j is in "invalid state"
or "new evidence or structural changes" have occurred (1)

{T } if i contains targets (2)
{T, } if ( 1) and ( 2)

∅ otherwise
To simplify the notation, hereafter, we will remove braces and denote {T, } by T . Then, the idea of our algorithm consists of marking every arc (i, j) in A(T ) by labels µ i→j expressing all the "local" information that V -j (i) contains.

Definition 4.3.3 (Label-message µ). For (i, j) ∈ A(T ), the label-message sent from i to j is a function µ :

A(T ) → 2 { ,T } such that µ i→j := k ∈V -j (i) {k}=Adj j (k ) λ k →k .
As an example of the previous discussion, imagine that a first incremental update impacts the initial DAG and consequently the initial T of Fig. 4.6. This consists of the removal of k 4 , the insertion of an evidence on r and a new target on k 1 . Fig. 4.7a depicts the µ-messaging within T after this update, where dashed and dotted ellipses stand for the cliques containing targets and evidence respectively.

One can easily see that, for instance, µ i→j = , µ j→i = T and µ j→k 2 = T . The following proposition allows to recursively construct the µ-messages: Proposition 4.3.4 (µ construction). Let (i, j) ∈ A(T ), then we have :

µ i→j = λ i→j ∪ k∈Adj -j (i) µ k→i .
All the proofs are provided in the appendix at the end of this manuscript.

Optimal Roots

Let us recall that ψ i→j denotes the message exchanged between cliques i and j during an inference computation. It shall not be confused with the label message µ i→j of Definition 4.3.3. As we can notice from the JT algorithm description, the number of computations performed by a JT-based message-passing algorithm does not depend on the root clique selected for collect/distribution because the ψ i→j messages are sent on both directions on all the edges of the JT. For IJTI, this is not the case, since this algorithm computes and sends only the ψ i→j messages necessary for the computation of the posterior distributions of its target nodes.

On some edges, IJTI will therefore not compute some ψ i→j messages because they are irrelevant w.r.t. the targets posterior distributions. As a consequence the number of computations performed in IJTI is sensitive to the root selection.

For instance, in the JT of Fig. 4.6, if clique i received evidence and the only target is j, only message ψ i→j from i to j is necessary, which is precisely what is sent if clique i is selected as root (here, only a distribution is necessary). But if clique k 4 is selected instead, message ψ i→k 4 needs to be sent during the collect and messages ψ k 4 →i and ψ i→j need to be sent during the distribution, which is clearly not optimal. To determine the optimal roots, let us define δ i→j (r) as an indicator of whether message ψ i→j is recomputed (in this case, δ i→j (r) = 1) or not (δ i→j (r) = 0) when r is selected as a root. In IJTI, we therefore seek to minimize

δ(r) = (k ,k)∈A(T ) δ k →k (r)
, which corresponds to the total number of messages recomputed and sent. Based on the discussion of the preceding section, we can write:

δ i→j (r) =              1 if ( ∈ µ i→j and{j} = Adj r (i)) or ( ∈ µ i→j and{i} = Adj r (j) and T ∈ µ j→i ) 0 otherwise (4.1)
The first line of Eq. ( 4.1) concerns collect messages ({j} = Adj r (i)). It asserts that collect message ψ i→j needs to be recomputed only if it is currently in an invalid state or if new evidence or structural changes have occurred in V -j (i) ( ∈ µ i→j ). When this is not the case, clearly, this message is up to date and does not need recomputation. The second line of Eq. (4.1) concerns distribution messages ({i} = Adj r (j)). It asserts that ψ i→j needs to be recomputed only if there exists a target farther toward the leaves of the JT (T ∈ µ j→i ) and if some evidence has been received on V -j (i) or some message coming from V -j (i) has been updated ( ∈ µ i→j ). Eq. (4.1) can be rewritten more compactly as:

δ i→j (r) =              1 if ∈ µ
foreach clique i ∈ L do foreach j ∈ Adj(i) \ Adj r (i) do if δ i→j (r) = 1 then Compute ψ i→j L ← L ∪ {j} foreach clique t ∈ Q do
Compute the posterior distributions of the target nodes in clique t return posterior distributions Proposition 4.3.6. The IJTI algorithm is sound, i.e., computing only messages ψ i→j such that δ i→j (r) = 1, for all (i, j) ∈ A(T ), results in the correct computation of the posterior distributions of the target variables.

Evaluation

We performed two kind of experiments to evaluate IJTI. First, the gain is evaluated in terms of the number of saved messages and second, it is expressed in terms of computations time.

Messages Optimization

In this section, we highlight the effectiveness of our algorithm by comparing the gain of using it instead of any non-incremental JT-based inference algorithm. The gain can be expressed as the percentage of unnecessary messages that IJTI avoids to compute compared to the messages sent by classical inference algorithms on both directions on all the edges and this amounts to 1 -δ(r)/(2|E(T )|). For this purpose, we performed tests using the aGrUM library on 9 real-world BNs of different complexities as well as on randomly generated BNs. The latter contained nbN odes Boolean random variables, (6 ≤ nbN odes ≤ 900, see Fig. world BNs and for randomly generated ones. As could be expected, the smaller the modifications, the bigger the gain. Note also that the gain is not too sensitive to the size of the BN. Fig. 4.9 also shows the same behavior of the gain for larger randomly generated BNs.

Time Optimization

In this experiment, we want to test IJTI in terms of time consumption while reflecting incremental queries of the WM by the BRMS engine. As we are interested in local modifications of the JT, we evaluate the performance of IJTI when the modification impacts less than 40% of the BN size.

The BRMS engine execution may induce incremental changes in the WM and trigger probabilistic inference many times. Hence, a simulation of such an ex- ecution will be reflected on the probabilistic side by changing evidence and/or structure of the JT (new arcs, nodes and evidence added or removed) and performing a number of probabilistic inference. Moreover, in order to see the impact of evidence/targets size, each simulation fixes the set of targets and evidence.

We therefore control the percentage of modifications that produce the structural changes, let it be hard_change, and those which only change evidence without impacting the structure, let it be soft_change. Actually our junction tree-based architecture processes differently hard and soft evidence as follows. On one hand, when adding/removing hard evidence to/from BN, one must systematically reconstruct a new JT. On the other hand, a soft evidence entails such a reconstruction only when the evidence node does not belong to the current JT. Finally, note that the probabilistic inference is only triggered after some change occurs in the JT, otherwise the previous computations are still valid. Algorithm 6 summarizes the approach we use to simulate the incrementality and record the computations time to quantify the gain obtained using IJTI. As we randomly select evidence and targets set, the simulation repeats the selection at line 4 in order to report average results. In practice we iterate this 20 times. As we discussed earlier, a simulation corresponds to a sequence of calling the probabilistic inference after introducing some changes. This is expressed by the repeat loop at line 7, which also corresponds to 20 in practice .

As the percentage of evidence/targets increases, the inference times increase and the computations that are still valid from previous inferences are reduced. So the average gain decreases. The latter is computed as follows. For each pair of targets and evidence percentages, we averaged inference time over 20 × 20 = 400 probabilistic queries following the schema in Algorithm 6. Let t IJT I (resp. t LP ) be the resulting average for IJTI (resp. Lazy Propagation, a state-of-the-art algorithm similar to that described in Algorithm 4). The average gain can be expressed as

1 -t IJT I /t LP .
In this experiment, we are only interested in real BNs. The x-axis of Fig. 4.10

shows evidence percentages while the averaged time gain appears on the y-axis. For each BN, a figure corresponds to a fixed parameter sof t_change and hard_change, which is also showed in the title. We recall that these two parameters are used to update soft and hard evidence between inference iterations. It may be seen clearly that, after being significant in small percentages, the gain falls as the percentage of change increases. We explain this by the fact that the reuse of previous computations, hence our optimization, is more significant in small or local changes.

We have similar behavior for other real BN as Fig. 4.11 depicts. We also notice a general behavior of both algorithms showing that the bigger the percentage of changes, the bigger the inference times. Fig. 4.12b shows an example of this behavior in the Alarm network. Finally, we want to emphasize that, if in addition we introduce structural changes to the JT, i.e., hard_change = 0, the gain decreases steeply, even for small structural changes, and stabilizes quickly to almost no gain. to the fact that the current implementation of IJTI spends more time to discover the valid zones in the JT, and this time impacts negatively the overall inference time. We refer to Section B of the Appendix for more results about the inference times and the gain obtained for different networks and parameters.

Conclusion

In this chapter, we introduce IJTI, a new incremental junction-tree-based inference algorithm for multi-target dynamic systems. Assuming that a first complete infer-ence has been performed, it first identifies an optimal root and second optimizes the inference accordingly. The correctness of these two optimizations is proved and experiments highlight that the algorithm allows for important savings compared to classical ones in the presence of local changes. In particular, we show that IJTI outperforms state of the art inference algorithms for small or local changes and the gain is more important when there is no structural changes impacting the JT.

In the next chapter, we deal with the issue of uncertainties in modern BRMSs.

We present a coupling approach with PRMs and we see that IJTI is well-suited to answer probabilistic queries in such a context.

Chapter 5

Business Rules Uncertainty Management

Introduction

We mentioned in Chapter 3 that uncertainty is inevitably present in real world applications. Thus, in order for BRMSs to support more realistic decisions, handling domain uncertainties becomes a must. In this chapter, we see how a coupling approach can be a solution for modern BRMSs to effectively manage uncertainties. The solution we propose adds probabilistic reasoning feature by coupling the BRMS with a probabilistic engine. A complete integration is also conceivable as in [START_REF] Sottara | Integration of symbolic and connectionist AI techniques in the development of Decision Support Systems applied to biochemical processes[END_REF], where the RBS engine is extended to manage rules and their uncertainties in the same time. However, we argue that separating concepts and architectures simplifies the software development and maintenance, and provides more control over the environment complexity (language refactoring, testing, etc.).

In fact, probabilistic inference is a complex process that would be inefficient for a rule engine to manage besides its own inference. Therefore, we are interested in a loosely coupled architecture to facilitate inter-operability and insure a clear sepa-ration between business and probabilistic logics. Doing so, we want to avoid the inter-independence between modules in tightly coupled systems, where a change in the uncertainty management will require changes in rules management. The loose coupling services principle is largely advocated in SOA alongside the decoupled contract design pattern [START_REF] Erl | SOA Design Patterns[END_REF]. The key idea of such a principle is to allow a service contract to be expressed independently of its implementation. In our context, this would reduce dependencies between business logic and uncertainty management implementation. We want to have a transparent uncertainty management while being independent from the probabilistic implementation of that service. For example, one might change the probabilistic engine in the future without altering the service contract. This chapter, provides an approach that couples BRMSs and PRMs. It describes how such an approach is articulated and how it ensures a practical probabilistic reasoning support. Finally, the chapter applies the approach to ODM.

Coupling BRs with PRMs

Uncertain OO-BRs Principles

From Chapter 2 we recall that BRs are rules in the form "If <condition> Then <action>" that are exploited for reasoning by forward chaining inference engines.

OO-BRMSs execute BRs against an OM that describes the application objects based on a data model. In this latter we can differentiate two components, which include an executable data model that can be implemented in JAVA or XML schema, and a business-oriented model, which uses specific vocabulary and terms familiar to business users and is expressed in a domain-specific language. Hence, WMEs (or facts) are objects in the sense of the OO paradigm. It follows that an elementary action or condition operates on tuples rather than simple values.

A single action affects WMEs by inserting a new object, removing an existing object or updating an existing object. Each of these actions potentially leads to a re-evaluation of any rule that matches the object in question.

It turns out that there exists a natural mapping between model elements in BRMSs and PRMs. We illustrate this through a simplified example from an insurance application. This example is not intended to be exhaustive but rather to illustrate necessary concepts.

Example 5.2.1 (Simple insurance application). An insurance organism allows its subscribers to request reimbursements depending on invoice types. A request must be validated by a health care professional and each subscriber can have many reimbursement requests.

A simplified representation of the model would consist of three classes representing a healthcare professional, a subscriber and a reimbursement request. Fig. 5.1 gives a UML class diagram for such an application. In a fraud detection context, we want to verify, using a BR-based approach, whether the healthcare professional is fraudulent. In such a context, anomalies that indicate fraud are detected by executing a set of rules and using scoring heuristics. For instance, if a fraud detection rule says that an excessive invoice alert must be raised on a healthcare provider who submits a high price reimbursement request for one of his subscribers, the corresponding object-oriented BR in Rule 5.1 will look for objects in the WM that correspond to providers with subscribers requesting reimburse- Similarly, Rule 5.2 says that a lens age anomaly alert must be raised on a healthcare professional who submits a lens reimbursement request for a subscriber under age When the data is completely known and well adapted to the classical logic paradigm, such rules are well handled using variants of pattern matching algorithms, e.g, enhanced Rete. However, when coping with uncertain or missing data, such rules cannot be executed. That is exactly where PRMs can play an important role to handle such a situation. In Example 5.2.1, we specified three classes. Fortunately, PRMs allow also to handle OO concepts, such as class and references. This remark is fundamental in our case since it will simplify the communication between both rules and probabilistic engines. The corresponding PRM representation for the running Example In particular, we found exactly three PRM classes related to each other, in a way that is similar to class interactions in the UML diagram 5.1. The attribute reimbs of class Subscriber can be seen as a multiple reference slot, which shows that the class points to a set of Reimbursement. In this example, we need to aggregate the informations about all reimbursement requests that belong to a subscriber. Hence, some PRM aggregators should be introduced. A divide-and-conquer approach is used to build PRM aggreagators in Fig. 5.2. We first determine whether the Subscriber has a Reimbursement with a high price (by the exists_p aggregator); second, we determine if the HealthcareProvider is linked to a Subscriber satisfying the previous condition (by the exists_sp aggregator). We follow the same reasoning to generate the aggregator exists_st. tainty in their attributes. As an obvious consequence, attributes with uncertainty in the rules are directly mapped to their equivalent PRM attributes. In addition, instead of evaluating Boolean expressions in the condition part, we introduce a probability operator to trigger the probabilistic engine inference. Thus, an enhanced version for Rule 5.1, which says basically that an alert must be raised when a healthcare professional submits a expensive price reimbursement for a subscriber, we can have Rule 5.3 that says that an excessive invoice alert must be raised on a healthcare professional if there is a 80% probability that the price of a reimbursement request is excessive. To summarize the approach, handling uncertainty in OO-BRMSs using PRMs is based on the idea of model mapping and the introduction of a probability operator in the rules syntax, which is responsible for triggering probabilistic inference. The mapping itself relies on the fact that both models share many interesting OO concepts such as classes and relations. The probabilistic knowledge encoded by the PRM pertains to our knowledge about the business domain. This is emphasized through relating the PRM to the OM that expresses business concepts, 1 rather 1 see discussion about OM vs knowledge base in Section 2.3 than rules that are likely to evolve. The next subsection specifies in more details the extensions we need to implement these principles.

Model Extension

As we discussed previously, PRMs relate attributes of different classes, and those of generated instances consequently, and have the advantage to create complex networks covering multiple instances. Although, random variables are generated from the same classes, they should be regarded as distinct variables with their own life-cycle. For instance, sub1.risk and sub2.risk in Fig. 5.3 are two distinct random variables generated from class Subscriber. We know from Fig. 5.2 that price_risk attribute is linked by reference mechanism to attributes of classes Subscriber and Reimbursement in the PRM, hence, in our extension, there is no need to evaluate conditions that can be processed by probabilistic inference. For instance, the operator in, used in Rule 5.1 to constrain the domain of an object, is implicitly specified through the link of reference slot subs. When the engine encounters the probability operator, it immediately launches a probabilistic query, i.e., it queries the underlying PRM. In such an extension, probabilistic data is explicitly identified and can be processed by PRM engines.

We extend both model and meta-model of the rules. First by enriching the model with new attributes as in the previous section and second by adding probabilistic annotations. This has two advantages. The first is moving probabilistic definitions from rules to their data meta-model. In making this move, probabilistic model and inference handling2 are externalized to the PRM engine, which implies a separate management of business and probabilistic logic. Second, this enables the model to be more independent w.r.t. the rules, which means an independent evolution of both models.

Annotations are a type of meta-data that enriches the meta-model at hand. In this work, they are added to indicate that a class contains probabilistic information, as well as that an attribute is mapped to a PRM attribute and is parameterized by its corresponding CPT and parents. If the attribute is an aggregator, annotations show its type, its domain and the concerned modalities (the possible states or values of the random variables). Therefore, an OM class (resp. an attribute) is mapped to a PRM class (resp. an attribute) and the probabilistic data and how classes are related to each other are extracted from the OM annotations. In the OM, a restricted type represents a type whose domain is restricted, for instance an integer that is restricted to {0, 1, 2}. Only discrete random variables are supported in PRMs, they can be user-labeled (e.g, state_type) or built-in types (e.g, Boolean,int). Thanks to these annotations, the rules engine can generate the underlying PRM classes and system at compile time. Before the generation process, the model is parsed and checked. For example we check if the given list of a PRM attribute parents is valid and consistent with its CPT. This latter is also checked to verify it represents a well defined probability distribution. Actually, there are two possible modes for PRM system definition. The first is a static declaration, which assumes that all WM instances are known at compile-time. The PRM system is then generated either by directly processing the WM instance graph, or by an explicit declaration inside a special annotated class, which also specifies necessary relations. The second mode allows a dynamic definition in addition to the previous mode. Here, rules' executions may also update the system by incrementally inserting new instances or modifying relations for instance. The last mode is obviously much more interesting since it reflects BRs and the WM dynamic nature.

The mapping we use allows the rules to generate complex probabilistic networks via the simple mechanism of class instantiation and reference slot. This property enables the rules, for instance, to handle many sets of random variables, which are

Application to IBM ODM

The aim of this section is to provide a practical view of the foundations introduced in the previous section. Our implementation is based on IBM ODM [START_REF]IBM: Operational Decision Manager[END_REF] as an OO-BRMS and a Graphical Universal Modeler (aGrUM) [START_REF] Gonzales | aGrUM: a Graphical Universal Model framework[END_REF] as a probabilistic engine. It is important to emphasize that the methodology we applied can be easily generalized to any OO-BRMS as we showed previously. This section gives an overview of the ODM functionalities and is mainly built from material in [START_REF] Boyer | Agile Business Rule Development -Process, Architecture, and JRules Examples[END_REF][START_REF]IBM: Operational Decision Manager[END_REF], where a more detailed presentation is given.

Overview

The ODM platform is a set of complex modules and applications that operate together in different environments while ensuring a clear separation between IT and business life-cycles as it is shown in Fig. 5.4. ODM enables organizational policies to be defined, deployed, monitored and executed in an application server. In ODM, business users and developers use tools that reflect their different skills and role within the business application. Fig. 5.5 depicts the main components that ODM provides for decision service development, rule management and authoring, and the execution environment. On one hand, Decision Server provides tools development and runtime components. It mainly consists of:

• The Rule Designer, which is an IDE that comes as an Eclipse plugging and provides many capabilities to design, author and test rules. Fig. 5.6 shows an in-depth view of the rule designer

• Rule Execution Server is a JEE container that provides the runtime environment for running and monitoring decision services and ensuring a transactional propagation and security control. The console is a web-based application to manager ruleset of the server.

On the other hand, Decision Server also interacts with Decision Center where business users can author, manage, validate, and deploy decision services relatively independently from IT specialists. The rule designer provides necessary tools to develop all rules artifacts, such as OMs, rule projects and rule flows. Fig. 5.6 depicts a general view of the rule designer with some rule artifacts. As far as ODM is concerned, the executable data model discussed in Section 5.2.1 is called eXecutable OM (XOM) and the business layer that defines the vocabulary used by BRs is called Business OM (BOM). The XOM corresponds to the physical data model that references the application objects 3 and data, and is the base implementation of the BOM. ODM gives a flexible way to define the XOM from different data sources such as Java, .NET, XML or COBOL. Furthermore, the BOM is a model that is similar to the Java OM and whose elements resonate with those of the XOM. The latter represents the class model against which rules are run. The 3 These objects are POJOs that the rule engine manipulates as WM elements 92 high level language used by business professionals to edit rules is called Business Action Language (BAL). The rules that are defined using BAL are called action at compilation for every rule artifact that is created directly from the BOM in order to be executed at runtime. In this way, ODM provides a semi-automated mapping that allows action rules to be translated during the compilation into technical rules. However, such an automation may require an IT specialist's insight and intervention to operate. Now, let us summarize the most common IRL constructs that are used in the condition part, i.e., declared inside the when part, and let us give their meaning and a corresponding usage.

• Class conditions are the simplest form of conditions. They bind a variable to a pattern, which consists of a type name and, potentially, inside of parentheses, some constraints on the type attributes. For instance the following condition:

s : Subscriber ( location == " Paris " ) binds a variable s to patterns from the WM that are matched by any Subscriber located in Paris.

• exists: this keyword checks the existence of a WME that satisfies the condition. The condition below is satisfied whenever a Subscriber WME located in Paris is found.

exists Subscriber ( location == " Paris " )

• from is used inside the rule to access ruleset parameters. These are a special type of parameters that are used to exchange data between the application and the ruleset. If we assume that healthProfessional is a ruleset input parameter, which is previously defined, then the following condition binds the variable hp to that parameter. We give an overview of the first one, a description of the remaining algorithms might be found in [START_REF] Boyer | Agile Business Rule Development -Process, Architecture, and JRules Examples[END_REF].

As we already discussed in Section 2.3.2.2, the rule engine compiles the ruleset (RB) into a complex network that orders efficiently rules conditions and we called this network the Rete network. As it is shown in Fig. 5.8, WMEs are later evaluated against this network and if a match is found, an instance of the corresponding rule is triggered in the agenda. The latter is responsible for ordering, selecting and executing rules' instances. Algorithm 7 gives an overview of how the Rete works in ODM. Note that the execution of a rule instance may update the WM. Thus, it triggers a re-evaluation of the rules against the WM.

A Complex Compilation Process

Previous studies initiated the work to investigate how probabilities could be integrated into ODM and proved the feasibility of such an approach [START_REF] Aït-Kaci | Probabilistic production rules[END_REF][START_REF] Arru | Introduction of probabilistic reasoning in JRules[END_REF][START_REF] Perez | Probabilistic Production Rules[END_REF]. However, they were essentially based on BNs framework, where each class is asso-PRM attributes. For instance, age in line 6 has no parents and a CPT describing whether the subscriber is under the age of 10 is provided. Note that AgeType at line 6 is an Integer restricted type. @PrmAgg marks the attribute as an aggregator. In line 11, the annotation specifies a list of the attribute parents and its CPT.

In this example, we implemented the static mode. So, instances are specified as internal attributes of the system class that is annotated with @PrmSystemClass in line 15. Reference slots are set inside the class constructor at line 22. Finally, the relational skeleton in Fig. 5.3 is generated from this system class.

The compilation process is based on a series of model re-writings. This is a powerful tool that allows ODM not only to abstract instructions from their implementation, but also to conserve the rule paradigm. Practically, the IRL rules life-cycle is completely separated from that of BAL rules. As a consequence, changing the implementation is possible without altering every BR.

When BRs are entered using the BAL, they are first translated into IRL rules by a rewriting procedure. Second, the resulting ruleset is checked and parsed to obtain a ruleset semantic model as an Abstract Syntax Tree (AST). At this level, the result may undergo recursive rewritings, on top of which one has different types of plugins. Then, the ruleset AST is compiled while taking into account the chosen algorithm. Again, this phase can be parameterized by various plugins according to the algorithm to be used, e.g., Rete. The output at this stage is optimized and transformed to obtain the semantic OM. This latter is a powerful meta-model, it can be seen as an extension of the Java meta-model that allows compilation, sources processing and model definition. There is no longer semantic rulesets here, but, instead, an object model that encodes the rule semantics (condition and action) inside the generated classes and methods. Other operations may appear such as the BAL/IRL mapping and the linkage with outside applications via services mechanisms. The final result is persisted and jitted into an archive that can be @ PrmClass public class Subscriber { @ PrmMu ltiRef erence public Reimbursement [] reimbs ; @ PrmAttribute ( parents ={} , cpt ={{.2} ,{.8}}) public AgeType age ; @ PrmAgg ( name =" exists " , attribute =" reimbs . type " , mod =" lens ") public boolean exists_t ; @ PrmAgg ( name =" exists " , attribute =" reimbs . price " , mod =" high ") public boolean exists_p ; @ PrmAttribute ( parents ={" age " ," exists_t "} , cpt ={{.2 ,.6 ,.5 ,.3} ,{. obliged to specify the conditional context at every probabilistic query. Thus, the previous expression can be reduced to prob(sub.risk==true), which is implicitly equivalent to prob(sub.risk==true|WM), here WM is simply "hp.risk==true"5 .

A Loosely Coupling-based Execution

A complex PRM system can be easily generated from the rules by means of relating instances of probabilistic classes, which represent a pre-defined BN fragment template. This is an advantage over the classical BNs approach, where the BNs are repeatedly defined. In addition to the compilation API discussed previously, BIS is also endowed with an execution API. Both insure different services communicating following the schema shown in Fig. 5.11. This allows for a coupling between both BRs and probabilistic engines, which are implemented as services.

Actually, our framework is not restricted to one implementation, but is open to other probabilistic libraries by means of an adaptive design. For instance, the cur-bility of their corresponding random variables. In this scenario, every condition is associated with a non negative parameter α i , as in the following rule, which is based on the model in 5.2.

rule findSubscribers { when { hp : Hea lt hP ro fe ss io na l ( probability ( age >50)≥ α 1 ) ; sub : Subscriber ( probability ( loc == " Paris " )≥ α 2 ) ; } } There are at least two reasons why this approach is limited. First, we actually hide the richness of rule constructs and operators and cut of their possible synergies with the probabilistic engine operators; we will detail further this point. Here, business users are prevented of expressing their confidence degree, more generally, on a joint of a subset or the whole of variables in the condition part such as in the following condition: Subscriber ( probability ( location == " Paris " or " NY " )≥ α 2 ) ; Secondly, as the majority of business users are interested in decision-making, not in how probabilistic queries are done, they may be confused if they have to deal directly with programming or mathematical components. Transparency w.r.t. probabilistic inference becomes since then strongly desirable to hide the computational complexity that lies therein. Therefore, another interesting way to express probability in the rules is to parameterize the whole condition part, i.e., the when{..} declaration, by a probabilistic activation threshold. In practice, we introduce a general probability operator that governs rules eligibility by testing if the probability to satisfy all the rule conditions equals or exceeds a threshold α 7 . Rule 5.7: Find subscriber located in Paris for a certain professional rule findSubscribers { probability ≥ α ; // α is a non negative constant when { hp : Hea lt hP ro fe ss io na l ( age >50) ; sub : Subscriber ( location == " Paris " ) in hp . subscribers ; } For example, the condition in Rule 5.7 binds a variable hp to HealthProfessional WME whose age is more than 50 and a variable sub to a Subscriber, which is located in Paris and belongs to hp. When the probability of satisfying those two conditions exceeds α, then this rule is activated. The probability operator can be seen as a generalization of the Boolean case, for which rule actions are executed when the conjunction of the rule conditions is satisfied. In this case, the threshold is simply equal to 1 to express the fact that we are certain about the conditions. The probabilistic operator, which is now put on top the rule conditions, is not to be confused with certainty factors à la MYCIN, where each rules is associated with a factor to show the confidence one has in the rule. Indeed, here we only move probabilistic calls from inside the rules and put them on top of them. However, the probabilistic computations that we carry should be based on a probabilistic inference.

The difficult point lies in propagating this operator on the conditions, as it is moved to a higher level, and the impact of this move on finding a corresponding probabilistic query. Only the compilation process could tell the probabilistic engine how to manage variables that are mentioned in the rule conditions and how to regard non probabilistic ones. This is actually a challenging task that involves a complex compilation process including parsing probabilistic conditions, extracting relevant variables and transforming results into an adequate probabilistic query. For example, in Rule 5.7, a joint probability distribution over hp.age, sub.location should be evaluated and the rule is equivalent to: We begin by emphasizing that since in and from generators restrict the condition evaluation scope, we grant them a higher precedence than the probability operator. This could be naturally done, as the rule engine is responsible to trigger the probabilistic inference and to specify the target variables from declaration of from and in generators.

A clause is a disjunction of logical atoms, atoms hereafter, or their negation.

Where an atom is simply a predicate applied to a tuple of arguments. An atom is characterized by the fact that it cannot be broken any further. As a consequence, a rule condition can be expressed in terms of a conjunction of one or more clauses.

For example, the condition: subscriber1 . age <21 and subscriber1 . location in { " Paris , NY " } is composed of two clauses, where the first clause consists of one atom and the second consists of two atoms. More generally, we can use a CNF to represent the conditions of a particular rule. 8 Although this is not a necessary transformation, we use it to facilitate rule conditions representation and to simplify illustrations throughout this section. In this previous example, we have : where :

CN F 1 =
• a 21 (location, P aris) = "location is Paris"

• a 22 (location, N ewY ork) = "location is New York" More generally, if we drop atoms arguments, then:

CN F i = ∧ n i j=1 ∨ m ij
k=1 a ijk , with n i (resp. m ij ) is the number of clauses in the i th condition (resp. of atoms in the j th clause of CN F i .

Probabilistic Propagation

In this section, we mainly base our discussion on the rules model in Fig. 5.13.

To simplify our discussion, classes X and Y represent IRL classes and their corresponding PRMs at the same time. We omit probabilistic annotations and we provide a possible PRM classes dependency graph in Fig. 5.14. We begin with 8 We emphasize that obtaining a CNF from a Boolean expression can lead to an exponential explosion of the formula and the conversion runs in exponential time in the worst case. propagating the probability operator in the presence of standard rules and then we see what happens when other constructs such as aggregates are used. We use interchangeably o.X 1 to denote the probabilistic attribute X 1 of the object o and its corresponding random variable's instantiation. Once the PRM system is known, In reality, it is frequent that the rule engine interacts with different sources of information, e.g., a database, which can supply the WM with non probabilistic objects. The rule's OM itself may contain non probabilistic classes, e.g., the B objects in the previous example. This is actually an issue since we loose the genericity when defining the new random variables resulting from functional nodes, e.g., every time the value of β changes, a new probabilistic query needs to be defined. To fix this issue, a solution may pre-compile the probabilistic query into parameterized functional nodes. The latter hold a memory for non probabilistic values and instantiate it at the execution 10 . Fig. 5.15 depicts a simplified general case where we have one CNF with two clauses and each clause has two atoms. Without loss of generality, we furthermore limited arguments of each atom predicate to two arguments, e.g., atom a 111 has arguments t 1 and t 2 and results in a random variable that is also denoted by a 111 . Each node in Fig. 5.15 represents a random variable, in particular, or i (resp. and) is a (probabilistic) OR-gate that is obtained as a disjunction (resp. conjunction) of their parents a i1 and a i2 (resp. or i ), i = 1, 2. Here we have CN F 1 = (a 111 (t 1 , t 2 ) ∨ a 112 (t 3 , t 4 )) ∧ (a 121 (t 5 , t 6 ) ∨ a 122 (t 7 , t 8 )). Note that the BN fragment of Fig. 5.15 is actually a class level extension of the associated PRM and needs to be instantiated and linked to the PRM system as soon as we proceed new WMEs, i.e., for a new WME, the rule engine must trigger a new instantiation of the BN fragment in the PRM system and potentially drop the relations created for specific instances of previous evaluations. In the case of several CNFs, we need to concatenate fragments akin to those obtained in Fig. 5.15 using several AN Dgates.

Based on the previous discussion, some issues arise regarding the introduction This means that we allow for an overlay that updates the PRM, as soon as we compile rule conditions, and its system, while executing rules actions. As we can see in Fig. 5.15, the posterior we are looking for, P(CN F 1 ), is obtained by querying the leaf node and.

We emphasize that the transformation process we carried out to obtain a leaf node, grows with the Cartesian product of the conditions and this may lead to scalability issues. A simplified example of this situation is the following:

Rules with Existence conditions and Aggregates

In this context, the extension we made in Section 5.2.1 becomes a specific case.

There, the class condition corresponds to one atom with an equality predicate and the probabilistic aggregate exists was added to the model11 , e.g., a condition based on the model presented in 5.13 would be:

exists X (X 1 == 2);
However, this is not always the case and class condition may be composed of a conjunction/disjunction of many atoms, which can be expressed using CNFs having general predicate expressions as shown in the previous section. Again we need to introduce new nodes and transformations, whose complexity depends on the complexity of the expressions at hand. Furthermore, to simplify this study, we suppose that we know exactly how many WMEs we have. However, in practice, this is often known at runtime and also evolves with incremental operations that affect the WM due to the execution of rules actions. Therefore, we need to be able to change incrementally the auxiliary nodes as long as we change the WM. This occurs especially when we deal with aggregates and we must be able to change parents of auxiliary variables nodes without recomputing everything from scratch, as we will see in exists handling. Thus, a solution for this issue is to define new types of probabilistic aggregate, such as greaterThan, which tells whether there exists a parent greater than a given value.

As far as the probabilistic inference is concerned, IJTI algorithm comes into play and allows for an inference that is adaptive to changes we made in the WM.

Based on the remark that the exists condition can be converted into a disjunction, we can follow a reasoning similar to what we held for standard rules and we We would like to emphasize that after converting the exists condition into disjunctions, we are required to apply the same process we held for simple conditions in the previous paragraph. The difference here is that we deal directly with instances. As we can see through this simple example with one simple condition (two clauses) and three WMEs, compiling probabilistic query from a rule condition may result in some difficult transformations and computations that cannot be easily automated. The complexity increases more and more if the when{...} body involves a combination of class conditions with existence conditions, which may lead to intractable computations due to the size of the WM and the type of the conditions we use. In this case we need to convert all exists and combine the result with fragments obtained from processing other class conditions. The following rule shows an example of such a situation, where we have to construct a conjunction between the leaf obtained from processing line 5 and the one obtained from line 6.

x 1 .X 1 x 1 .X 2 x 2 .X 1 x 2 .X 2 x 3 .X 1 x 3 .X 2 gt 1 β1 gt 2 β1 gt 3 β1 lt 1 β2 lt 2 β2 lt 3 β2
Rule r5 { probability≥ α when { example, the variable X 1 takes only two values. Then Rule 5.10 is equivalent to query random variable sumGt2 in Fig. 5.18a, where sumGt2 takes the true value when the sum on its inputs is greater than or equal to 2 and false otherwise, and whose parents are all X WMEs. We give the CPT of sumGt2 in Fig. 5.18b.

x 1 .X 1 x 2 .X 1 x 3 .X 1 sumGt2 (
Again, it would be an interesting enhancement if the rule compiler or the probabilistic engine could also automatically generate such a CPT, because it will be impracticable to build it manually as the number of parents grows. Just to see what happens if we want to actually evaluate the probability, we assume that the BN fragment in 5.18a is isolated and we have an evidence x 2 .X 1 = 1, then the condition in line 8 is satisfied when P(sumGt2 == true|x 2 .X 1 = 1) = 0.5295 ≥ α, as shown in Fig. 5.19. Therefore, we can see through this simple example that finding an equivalent probabilistic query might not be an easy task. First, we need to check whether the aggregate is supported by the probabilistic engine or not. In the latter case, we need to implement it based on the compiler analysis of the rule conditions, e.g., sumGt2 is obtained by parsing the aggregate declaration and the where condition. Second, the analysis of clauses in the condition will simplify this task or make it hard because we may introduce some new nodes as we did in the case of standard rules.

In the presence of many aggregates each one will result in a complex node to be combined with nodes from other conditions. Having this discussion in mind, rules such as Rule 5.11, will result in complex computations including parsing rules, defining functional nodes and putting all together to finally find an equivalent probabilistic query. We concluded this chapter with a discussion on generalizing the use of the probability operator. The point is to move any technical probabilistic (mathematical or programming) construct from the condition definition and put it on top of the rule. Some issues arise regarding the propagation of such an operator. Thus, we propose a general approach to cope with this issue. In particular, we highlighted through many examples, that the PRM engine has to support functional nodes, including generic probabilistic aggregates and dynamic PRM systems. The rule compiler has also to be extended to parse correctly probabilistic rules. The main challenge here is to produce the runtime probabilistic query. We saw that the output of this task varies from one rule construct to another and its complexity depends on the complexity of the condition expression and the combination of the rule constructs, such as generators, aggregates and different class conditions.

Finally, we know that the execution of a rule action may update, insert or remove WMEs. This clearly has an impact on the corresponding PRM as it may cause its inconsistency. For example, the removal of an object from the WM may unset a reference slot, hence, the PRM becomes ill-defined. This is an issue because, if the PRM is queried at this time the inference answer is clearly unsound.

To tackle this problem, we need to impose a transactional mode when the rules engine declares the PRM system or updates WMEs or forbid querying the PRM before completing its correct definition.

under uncertainty will render business applications more realistic. This remark motivated our research and our choice for PGMs to cope with the issue of uncertainties in BRMS. In particular we use PRMs, an OO version of directed PGMs, to

model uncertainties and answer probabilistic queries. Coupling both frameworks has many advantages. First, they provide a declarative and expressive representation of the knowledge, which is separated from the reasoning process. Second, conceptual similarities (classes, objects and relations) facilitate the mapping of the object model in BRMSs with the probabilistic model in PRMs. In Chapter 3, we present PRMs and provide a discussion about incremental probabilistic inference.

Actually, the working memory in BRMSs evolves incrementally and, to ensure an effective coupling with a probabilistic engine, we need to extend probabilistic inference algorithms to take incrementality into account. In Chapter 4, we present, IJTI, a new inference algorithm that deals exactly with such an issue. The key idea of the proposed algorithm is taking into account previous computations to optimize the current inference by computing only what is exactly needed. We then highlight its effectiveness through experimental tests on real and randomly generated data. In Chapter 5, we present a method to couple BRMSs with PRMs exploiting shared similarities. Then we apply our approach to IBM ODM, which is a leading industrial BRMS. We also present the architectural basis and show how our prototype allows for an inter-operability between BRMSs and PRMs.

Future work

The research presented throughout this manuscript opens many other research perspectives. In particular, the IJTI algorithm can be easily adapted to the PRM inference. For this purpose, we need, first, to ensure a transactional mode that guarantees the coherence of the model during updates caused by the working memory. One should have an automatic consistency checking before probabilistic inference is engaged. Second, the probabilistic inference itself could be optimized by taking into account structural properties encoded in the PRM and lift a part of inference to the PRM class level. This would optimize inference at runtime as we can (re)use class computations at instance level.

Moreover, as soon as we deal with aggregators/generators in the rules, e.g, from,in, it becomes necessary to automatically generate their PRM counterpart as and when we compile the rules. This immediately opens the issue of PRMs nonsupported operators and the idea of extending this model. Another difficult compilation aspect, yet more interesting, is the use of several operators within the same rule and how this impacts the PRM construction.

After each working memory update, the Rete algorithm tries to optimize the expression re-evaluations, while taking into account the previous state. For example the Rete network shares nodes in the compiled network whenever shared conditions appear in the rules. It would be interesting to develop a two-sided optimization that supervises PRM and working memory updates, e.g, taking into consideration the PRM variables independence. Or better yet, to try to optimize updates propagations as part of a tight coupling but to the cost of algorithmic complexity and finding a trade-off between implementation and performance. Finally, this work also opens doors to introduce uncertain reasoning in rules temporal expressions to process complex events over uncertain data or events. 125 invalidated in the previous one. As a consequence, the current inference needs to recompute only such a message for any i, j in V(T ).

131

Appendix B

Other experimental results

Speech

Figure 1 . 1 :

 11 Figure 1.1: Some areas of AI

Figure 2 . 1 :Example 2 . 3 . 1 .

 21231 Figure 2.1: Central components of a RBS

Figure 3 . 1 : A DAG for the student example 3 . 2 . 1 . 1

 313211 Figure 3.1: A DAG for the student example

Figure 3 . 2 :

 32 Figure 3.2: Random variables for the student Example 3.2.3

Fig. 3 . 3 depicts

 33 arbitrary CPTs generated for the student example's random variables. Now the joint probability distribution can be obtained from the factorization product as: P(D, I, G, S, L, J) = P(D)P(I)P(G|D, I)P(S|I)P(L|G)P(J|L, S)

Figure 3 . 3 :

 33 Figure 3.3: Randomly generated CPTs for Example 3.2.3's random variables

Fig. 3 .Figure 3 . 4 :

 334 Figure 3.4: A trail (left) and a directed path (right)

XFigure 3 . 5 :Figure 3 . 6 :

 3536 Figure 3.5: Markovian assumption for node L

  Now if we come back to student Example 3.2.3, and rely on one of the probabilistic inference algorithms, which will be detailed in the next section, we can predict how likely an intelligent student would get the job by answering the marginal distribution P(J|I = high), where Q = {J} and E = {I = high}. Note that in general, the prediction flow of information is in the same direction as the BN arcs. Another query would try to see the impact of knowing the student got the job on our knowledge about his grade. This could be done through computing P(G|J = yes). This kind of reasoning is called diagnosis and the information flow is in the opposite direction of the BN arcs. Observing that the student got an A grade, we would like to know what is the most probable assignment of variables D and S that allows such a situation. This is done by answering the query M AP (D, S|G = A) and if we add J and L to the targets, the query will then reduce to an M P E.

3 . 8 ,

 38 which depicts a BN. In such a configuration, one can identify repeated patterns and abstract them as a generic type or class of objects. For instance, in Fig. 3.8, random variables X i , Y i form a pattern. A PRM class also abstracts all the interactions between its random variables by drawing arcs expressing the probabilistic dependencies. Class' random variables, which describe and characterize the pattern represented by the class, are called attributes. Basically, a class attribute can only be visible to attributes of the same class. However, one might want to refer to attributes outside the class. That is why PRMs define the notion of reference slots allowing communications between different classes and hence between attributes of different classes. Now let us give formal definitions for PRM concepts Definition 3.3.1 (Class). A class C is defined by a DAG over a set of attributes A(C) and a set of reference slots R(C) (see Definition 3.3.2).

Figure 3 . 8 :Figure 3 . 9 :Definition 3 . 3 . 2 (

 3839332 Figure 3.8: A BN with repeated patterns

Figure 3 . 10 :Definition 3 . 3 . 4 (

 310334 Figure 3.10: The relational skeleton related to the BN in Fig 3.8

From the description in Example 3 . 3 . 6 ,Figure 3 .Definition 3 . 3 . 7 ( 54 ( 3 Figure 3 . 12 :

 3363337543312 Figure 3.11: some PRM concepts for Example 3.3.6

Fig. 3 .Definition 3 . 3 . 8 (

 3338 Fig. 3.12b illustrates such a situation, where attribute C 1 .X refers its parent C 2 .Z through the slot chain C 1 .ρ 1 .ρ 2 = C 2 . Now, we have all the necessary ingredients to define formally PRMs. Given a relational skeleton S and a class C, let I S (C) denote the set of instances of C in S.

Figure 3 . 13 :Fig. 3 .

 3133 Figure 3.13: The ground BN for the system in Fig. 3.11b

2 . 3 in Fig. 4 .Figure 4 . 1 :Definition 4 . 2 . 1 (

 23441421 Figure 4.1: A DAG (a) and its corresponding moral then triangulated graph (b)

Fig 4 . 3 ,

 43 Fig. 4.2, we have φ 1 (G, I, S) = P(S|I) × P(I) and ψ 1→2 = ψ 2→1 are initialized to the unity factor 1 G,I .

Figure 4 . 3 :Figure 4 . 4 :

 4344 Figure 4.3: An initialized JT data structure for the Student Example 3.2.3

Figure 4 . 5 :

 45 Figure 4.5: Message-passing during distribution

Figure 4 . 6 :

 46 Figure 4.6: A maximal sub-tree in a JT

Figure 4 . 7 :

 47 Figure 4.7: Message passing within a JT T .

Fig. 4 .Algorithm 5 : 2 i.nbV N ← 0 34 5 5L 7 p← 8 if δ i→p (r) = 1 then Compute ψ i→p 9 p

 45205789 Fig.[START_REF] Agli | Un algorithme d'arbre de jonction incrémental[END_REF].7b and Fig.4.7c illustrate that δ(k 3 ) = 5 and δ(i) = 4 respectively. In this case, it is better to select i as a root rather than k 3 since this avoids the unnecessary

Figure 4 . 8 :

 48 Figure 4.8: IJTI messages optimization for real BNs

Figure 4 . 9 :

 49 Figure 4.9: IJTI messages optimization for artificial BNs, each curve corresponds to a BN size

Algorithm 6 : 4 repeat 5 6 Compute posterior of targets 7 repeat 8 9 Compute posteriors of targets 10 Record inference time 11 until

 64567891011 Simulation of incremental inference using IJTI Data: BN, hard_change and soft_change percentages, target and evidence percentages Result: Records for computation times 1 Set initial target and evidence set 2 Compute posterior of targets 3 foreach hard_change and sof t_change percentage do Randomly choose targets and evidence w.r.t initial percentages Introduce hard_change, soft_change into the JT of BN number of inferences per simulation is reached; 12 until an average criterion is reached;

Figure 4 . 10 :

 410 Figure 4.10: Average time gains for some real BNs. The title expresses hard and soft change percentages respectively. Each plot corresponds to a target %

Figure 4 . 11 :

 411 Figure 4.11: Average inference time gains for other real BNs. Each plot corresponds to a target %

Fig. 4 .

 4 Fig. 4.12a illustrates this in the case of Alarm and Insurance networks. This is due

Figure 5 . 1 :

 51 Figure 5.1: UML diagram for Example 5.2.1

10 .

 10 Rule 5.2: detect lens anomaly IF hp has type H e a l t h c a r e P r o f e s s i o n a l & sub has type Subscriber & reimb has type Reimbursement & sub in hp . subs & reimb in sub . reimbs & sub . age < 10 & reimb . type = lens THEN r a i s e A l e r t L e n s A g e A n o m a l y ( hp )

Figure 5 . 2 :

 52 Figure 5.2: Class dependency schema for the insurance example

Fig. 5 .

 5 Fig. 5.3 depicts an example of a relational skeleton obtained from the fraud example instances. A dashed arc stands for a reference slot. For instance sub1 references reimb1 and reimb2. Now that we have an equivalent PRM for rules classes definitions, we are able to execute rules that manipulate objects with uncer-

Figure 5 . 3 :

 53 Figure 5.3: A relational skeleton for the fraud example

Rule 5 . 3 :

 53 detect invoice anomaly with probability IF hp has type He al thc ar eP ro vi de r & probability ( hp . price_risk = high ) >.8 THEN r a i s e A l e r t E x c e e d e d I n v o i c e P r i c e ( hp )

Figure 5 . 4 :

 54 Figure 5.4: ODM life-cycles

Figure 5 . 5 :

 55 Figure 5.5: ODM Components View

Figure 5 . 8 :

 58 Figure 5.8: ODM rule engine in Rete mode

}Figure 5 . 9 :

 59 Figure 5.9: Subscriber and System classes

}

  lt hP ro fe ss io na l () ; sub : Subscriber () in hp . subscribers ; evaluate ( p : probability ( hp . age >50 , sub . location == " Paris " ) , p≥ α) ; } In the following, we will try to shed light on the compilation challenges and give some directions to propagate the probability operator on rules conditions. Of course, the interpretation of the probabilistic operator will depend on the IRL constructs we use, e.g., class conditions, generators and aggregates, and the way they are combined together within rule conditions. Now let us try to give a probabilistic interpretation of each construct alone, then see what happens when aggregation and other type of conditions are combined.

109/Figure 5 . 2 Figure 5 .

 525 Figure 5.13: A rule class model with (non) probabilistic attributes

Figure 5 .

 5 Figure 5.15: A BN fragment obtained from analyzing rule conditions

and 1 and 2 and 3 orFigure 5 .

 35 Figure 5.17: A runtime BN fragment obtained after compiling the existence condition in Rule 5.9

  Figure 5.18: A BN fragment obtained when compiling Rule 5.10

Figure 5 . 19 :

 519 Figure 5.19: Probabilistic inference result, with evidence x 2 .X 1 = 1

agg 1

 1 : aggregate { x : X (a 111 (X 1 , b.b1));

  G = (V, A) a directed graph over nodes (random variables) V and arcs ACPTConditional Probability

  According to[113], a BR is based on a collection of noun concepts called terms and gathered in a glossary called concepts catalog.. For instance, Customer, customer's city and Customer's category represent terms in Example 2.2.4.Terms are words or phrases that reflect business concepts and whose exact meaning is specified and agreed upon among collaborators in a business.Interactions between terms are known as facts[113] or fact types[START_REF]Specifications: Semantics of business vocabulary and business rules[END_REF]. Facts are verb concepts that link together appropriate terms. For instance, the assertion Customer has a city is a fact that relates a customer to a city in Example 2.2.4.

Example 2.2.4. (Discount BRs. )

IF the value of the shopping cart of the customer is more than 1500 THEN set the category of the customer to "Platinum" IF the customer's city is "Paris" and the customer's category is "Platinum" and the order date is between "June 21,2017" and "August 20, 2017" THEN set the order discount to 45 percent 1 a group formed by IT practitioners and business analysts inside the GUIDE project. Now, BRs are simply built on top of these facts by expressing how these facts must/should (not) be constrained in order to guide business operations

[113]

.

  As we mentioned in the previous paragraph, BRMS were introduced to help aligning IT with business. In the IT architecture perspective, BRMSs come as a separate layer and can be seen as a service among others such as database management systems. BRMSs externalize and centralize the management of BRs to avoid distributed and redundant updates. Finally, BRMSs separate BRs from the technical implementation, thereby, BRMSs are the technical solution that gives business workers the control over BRs with greater agility. The way BRMSs manage BRs is largely borrowed from early rules-based systems (RBSs) . Indeed, BRMSs inherit from these how to effectively store, in a declarative manner, and reason, in a component-based architecture about that knowledge. We refer to the next section for more details about RBS.

	It essentially consists of dividing as much as possible applications into separate
	components or modules. A very prominent application of this principle is the
	Service-Oriented-Architecture (SOA) paradigm. The adoption of SOA and BRMS
	together will let businesses deploy or integrate new applications far more easily
	[50].

Being a complex software system, a BRMS additionally implements the business logic by providing the environment for designing, authoring, checking, deploying and executing BRs. Therefore, modern BRMSs provide business experts, who own the business knowledge and processes, with tools to manage BRs directly without being IT specialists. It represents a common ground for collaboration with these latter, though.

Algorithm 1: Select-Execute cycle 1 done ← false 2 while not done do 3

  key idea of Rete is to compile RB into a graphical representation called the The network can be seen as a data-flow graph. Each time a fact is added, it is filtered to match or not the network nodes down to the bottom.If it has passed all the nodes, then the corresponding rule is activated. Rete is a

	Room pattern-matching algorithm such that every path in the network corresponds to in R1 now being applicable and f 3 is added to the WM. As a consequence R 2 is Conditioner state : enum{on,off} temp : int windows : enum{opened,closed} a pattern in the rule. Furthermore, every node in the network is a local mem-activated and fact f 2 is added. We therefore conclude that the final WM is equal
	Figure 2.2: UML diagram for air conditioner's Example 2.3.1 ory that holds WMEs satisfying the associated conditions. As we can see, Rete to {f 1 , f 2 , f 3 , f 4 }. The inference process is terminated as soon as all applicable
	is memory-consuming, albeit it efficiently pairs WMEs the with rule base. Note production rules have been processed or a certain stop condition is reached. As we
	database formalism. Then, beta-nodes combine two or more satisfied conditions that there exist other algorithms for implementing production systems in general, see, this strategy is fact-driven and it is best for prognosis and control systems or
	just like the join operator. such as TREAT [87], which introduces a new method of state saving in production systems where no specific goal is being explored. Forward chaining is also called
	Let us illustrate this through Example 2.3.1. Assume that our domain is com-system interpreters called conflict-set support, and Gator [56] a generalization of bottom-up reasoning as it reasons from the low-level facts to the top-level conclu-
	posed of two classes, Conditioner and Room as it is showed in the UML diagram Rete and TREAT. sions that are based on the facts. It was used in the DENDRAL system that we
	of Fig. 2.2. Then, Fig. 2.3 depicts a Rete network associated with RB in Example mentioned previously.
	2.3.1.	There are two famous strategies used by the inference engine to derive new
	Obviously, there is no unique Rete representation since different combinations knowledge or draw conclusions, namely, the forward chaining and backward chain-
	Rete network, where shared conditions are no more duplicated. In practice, con-ditions are first associated with nodes called alpha-nodes that select WMEs whose attributes match rule conditions, just like the select operator in the conventional root node ing. Even though BRMSs 4 are generally implemented using the first strategy, the second one can generally be emulated. Here we use the term chaining to reflect the reasoning chain, which is based on a series of inferences that allow RBS to connect a problem with its solution. Note that hybrid strategies, where we mix backward and forward chaining, are not covered by this section. of conditions exist. Conditioner Room type nodes Forward Chaining We talk about Forward Chaining when we start the reason-
		ing process by evaluating facts present in the WM w.r.t rules conditions to end
		with conclusions that follow from the facts. A rule is executed when the conclusion
		on part is executed. alpha nodes	off	temp	windows
				> 35	closed
		The engine will try to match the required condition for all rules until none is satis-
		Select a rule to execute // w.r.t., a Conflict Resolution fied. If we get back to Example 2.3.1, with W M = {f 1 }, then the strategy consists
		4 beta nodes Execute actions of the selected rule and remove it from agenda off & temp> 35 of selecting rules whose conditions match f 1 , hence R 3 will be applied first. The ap-
		5 plication of the selected rules may change the WM content, enabling consequently Update agenda
		6 rule nodes if agenda is empty or a stop condition is reached then R 3 R 1 R 2 other rules to be fired. So after applying R 3 , we have W M = {f 1 , f 4 } which results
		Figure 2.3: Rete network for air conditioner's Example 2.3.1

Table 3 .

 3

		X 2
	X	X 1	X 3	X 4	Y
	Figure 3.7: An example of a blocked trail between X and Y

1: Conditions under which a two-arc trail is closed Z = {X 2 , X 3 }, since it contains the closed two-arc trail {X 2 , X 3 , X 4 }, which is divergent and X 3 ∈ Z Now we have all the ingredient to provide a definition of d-separation. Definition 3.2.9 (d-Separation [100]). Let X, Y and Z be disjoint sets of nodes in G. We say that X and Y are d-separated by Z, written X⊥ G Y|Z, iff every path between a node in X and a node in Y is blocked by Z.

For instance, in Fig.

3

.7, we have {X}⊥ G {Y }|{X 2 , X 3 }.

Two variables that are not d-separated are said to be d-connected. The purpose of the d-separation test is to provide a simple and yet efficient graphical criterion to assert whether two variables are probabilistically dependent given our knowledge about other variables. So far, we have been guided by an intuitive approach based on the influence propagation, but one may wonder whether for every two nodes X, Y d-separated by some set Z, we have X is conditionally independent from Y given Z, w.r.t P. This is the purpose of the following proposition: Proposition 3.2.10 (soundness of d-separation

[START_REF] Verma | Causal Networks: Semantics and Expressiveness[END_REF]

). Let X, Y and Z be disjoint sets of nodes in G. Then X⊥ G Y|Z ⇒ X⊥ P Y|Z. Theorem 3.2.11 (Weak completeness). For every DAG G, there exists a joint probability distribution P factorizing over it, s.t., X⊥ G Y|Z ⇔ X⊥ P Y|Z.

  To cope with this kind of situation, we need to specify a generic function capable of encoding at class level X's CPT whatever the number of parents in the instances of C. For this reason, PRMs define aggregators to express such a many-to-one instance relation. In addition, aggregators are useful to keep the probabilistic semantic and genericity at class level and avoid otherwise multiple class definitions w.r.t. the variable number of configurations depending on relation arities, i.e., the size of the multiple slot.

Definition 3.3.5 (Aggregator). An aggregator is a deterministic functional attribute, whose CPT is inferred once the class is instantiated and connected to its instantiated references. Examples of classical aggregators include min, max, for all and exist. Let us present an illustration of these concepts and consider the updated Student Example 3.3.6. Example 3.3.6 ( Updated Student Example). In Example 3.2.3, the student was related to one course. Now, we consider the student attending several courses.

Based on the remark that the course difficulty does not characterize a student, but

rather is a course property, it would be interesting to divide the domain variables into two types. The first one gathers properties that describe a student and the second one gathers those describing a course.

  a 11 (age, 21) ∧ (a 21 (location, P aris) ∨ a 22 (location, N ewY ork))

Table CNF

 CNF

	Independence Structure, 35 Terms, 13	Prior Marginal, 44
	Inference Engine, 21 Trail, 40	PRM, 55
	IRL, 96 Uncertainty, 3, 4 Subject Index Join tree algorithm, 61 User Interface, 25	PRM class, 50 PRM Instance, 52
	Action Rules, 94 Aggregate, 98 Junction Tree, 63 WME, 21, 109 Junction Tree algorithm, 46 Working Memory, 20	Certainty Factors, 109 Clique, 62 PRMs, 32, 49 Probabilistic Conditional Independence, 38
	Aggregator, 53 Knowledge Base, 19 Working Memory Element, 21	Clique graph, 62 Probabilistic Graphical Models (PGMs),
	Agility, 2, 9 MAP, 45 XOM, 94	CNF, 111 31
	AI, 3, 4 Marginal distribution, 44	Collect, 66 Probabilistic Relational Models, 32
	alpha-node, 22 Markov Blanket, 39	Concepts Catalog, 13 RBS, 3
	Markovian Assumption, 38	Conflict Resolution, 21 RBS, Rule-based System, 15
	Conjunctive Normal Form Backward Chaining, 24 Message-Passing, 46	Conflict Set, 21 Recursive Conditioning, 47
	PGM MPE, 44 BAL, 94 Probabilistic Graphical Model Reference Slot, 51 CPT, 34
	BN BR Network Parameterization, 36 Bayesian Network Bayesian Networks, 32 Business Rule Belief Propagation, 46	d-Separation, 41 Relational Skeleton, 52 DAG, 33 Rete, 22, 98, 100
	RBS O3PRM, 104 BN, 32	Rules-based System	Distribution, 66 Rete algorithm, 18
	BRMS BOM, 94 Business Rules Management Systems Object Models, 15 Rete network, 22
	KB Object-Oriented, 15 Knowledge Base BR, 12	Explanation, 26 Rule-based Expert Systems,RBS, 18
	WM ODM, 5 BRMS, 2 Working Memory	Factor, 63 Rules, 1
	WME BRMS,RBS, 14 Working Memory Element OMG, 12	Fire, 21 Running intersection property, 63
	IT POJO IDE OM AI Business Rules Approach, 2, 11 Information Technology Plain Old Java Object Integrated Development Environment Object Model Incremental Junction Tree Inference, 68 Poly Tree algorithm, 46 Artificial Intelligence BRs, 11 OO-BRMS, 16 Forward Chaining, 24 SBVR, 12 Business policy, 11 Ground BN, 55 Pattern, 97 Separation of Concerns, 2, 14 Business Rule, 12 PGMs, 5 Slot chain, 54 Business Rules, 2, 11 IJTI, 68 Policies, 1, 10, 11 SOA, 2, 14
	Business Rules Management Systems, 2 Posterior Marginal, 44 Technical Rules, 96 Incrementality, 6, 59
		157

a set of inter-related tasks and activities

see Section 2.3.2

see next section for details

the IF part is also called condition or premise, or left hand side (LHS) and the THEN part is also called conclusion, action or right hand side (RHS)

done ← true

being a product system, a BRMS is used to produce actions or change the behavior of an environment, hence the forward chaining strategy is naturally adopted in BRMSs

different designations can be found in the literature: probabilistic networks, belief networks, causal diagrams.

We assume that the random variables are identified with the graph nodes.

Intuitively, junction tree algorithm consists of performing variable elimination in all directions at once and storing intermediate results at each step.

In Fig.4.8.a, due to the small number of nodes and arcs in the BNs, percentages of modifications lower than 10% imply no modification at all, hence the lack of error bars.

Bear in mind that the probabilistic model definition is held by the rules OM.

One can similarly manage the introduction of other operators such as mutual information or entropy.

The current version of BIS does not support all the probabilistic engine functions.

Here we assume that α is given, otherwise it might be inferred or computed from rules context.

this is similar to a database placeholder/wildcard, when we prepare before executing a query that runs several times but with different values.

Even in that simple case, we may notice a combinatorial explosion depending on the number of the aggregate parents, which of course depends on the size of the WM.

Acknowledgments

I also would like to thank Patrick Albert for the inspirational enthusiasm he gave me to start this PhD. I am thankful to IBM France Lab for supporting this research

with the IBM PhD fellowship and ANRT with the CIFRE grant.

During the inference process, we need to define the combination of factors, hence we introduce the notion of product between factors, which is defined as follows: Definition 4.2.6 (Factor product). Let φ 1 and φ 2 be two factors over {X 1 , X 2 } and {X 2 , X 3 } respectively, with X 1 , X 2 and X 3 three disjoint sets of random variables (possibly empty). The factor product of φ 1 and φ 2 , denoted φ 1 × φ 2 , is the factor ψ such that:

We can say that a CPT in Θ is an example of factor. The next step is to assign each φ ∈ Θ to a node i ∈ V(T ) such that dom(φ) ⊂ C i . Let φ i be the factor associated with i and initially obtained by computing the product of factors assigned to the clique C i . Definition 4.2.7 (Adjacency). Let i, j ∈ V(T ) such that i = j. i and j are 7 Distribute(r, r) the opposite direction. Algorithm 4 corresponds to the JT algorithm and summarizes the discussion we held above. Note that if C i contains an evidence node X, then we instantiate X in each φ ∈ Θ such as X ∈ dom(φ) and we obtain a reduced factor domain. We also want to emphasize that a JT can be a forest, e.g., when DAG G is not connected. In this case, the same algorithm is performed in every connected component of the forest. Later, for simplicity, we assume that we deal with a tree. Now let us illustrate the JT algorithm on our running ex-computation of one message. The following theorem states the existence of some optimal roots and characterize them:

Theorem 4.3.5 (Optimal roots). Suppose we computed the µ-messages within T .

Then there exists r ∈ V(T ) fulfilling one of the following mutually exclusive and exhaustive properties:

In addition, r ∈ Argmin k∈V(T ) δ(k), i.e., r is an optimal root w.r.t. inference computations.

A new Incremental Inference

In this section, we propose a new algorithm designed to deal with incremental inference. We assume that a first inference has been performed by message-passing within T , using for instance a collect-distribute algorithm in a JT-based inference architecture. Afterwards, incremental changes occur. Then IJTI is called to optimize the inference process. We recall that we use a target-driven approach, hence, we recompute only invalidated collect messages and we only distribute messages up to the targets. Under these assumptions, the proposed algorithm is described in Algorithm 5. It runs a revised message-passing algorithm to compute ψ i→j only when δ i→j (r) = 1 for all i, j in the modified junction tree T . In line 5, a leaf clique i is such that |Adj(i)| = 1. We emphasize that computing messages is performed similarly to a classic JT-based inference algorithm. The correctness of IJTI is guaranteed by the following proposition:

rules and they are based on the well known IF/THEN-ELSE constructs. BAL is essentially designed to help business professionals to enter BRs in a more human readable format.

Knowledge in the rule engine is built using the ILOG Rule Language (IRL), a Java-like programming language, which is actually the rules technical and execution language in ODM. Therefore, every rule artifact should be translated into IRL as it is the only language the rule engine can understand. Rules that are written using the IRL are called technical rules and follow the the general syntax in Fig. 5.7. We would like to emphasize that ODM allows for a BOM-to-XOM mapping mechanism that is based on a specific XML schema. The latter must be provided • not statement returns true if there is no WME matching the condition. In order to express the negation of the exists operator, using the not operator (without in/from) is preferable to using not exists. For example, the following condition is satisfied when there is no subscriber in the WM located in Paris.

not Subscriber ( location == " Paris " )

• Aggregates compute a value from a collection of values. Examples of aggregations are the average, sum, or maximum of a numeric collection. Here is an example of a condition that computes the total amount of all reimbursements. When we want to condition the result of the aggregate, the keyword where is used The BR engine is a central component in ODM as in every RBS. It manipulates state-full, history-aware Java objects and supports three execution algorithms, namely the Rete algorithm, the sequential algorithm and the Fastpath algorithm. 4 Note that exists can be seen as a special case of aggregate. Also, the definition of the BN cannot be directly inferred from the class definition.

Obviously, this is not a realistic use and rules conditions must query only variables of the object being handled. This means a strong correlation between the probabilistic model and the ruleset and this results in redundant BNs definitions.

We already discussed some of the limitations facing BNs and we mainly related them to the lack of the object concept, see discussion in Section 3.3. Furthermore, probabilistic engines that are based on modeling only with BNs do not support reference mechanism, which is essential to objects management in BRMSs. Therefore, it is natural to investigate what PRMs can offer in our context.

To begin with, let us show the XOM classes obtained for Subscriber and the system of our running example. Consider Fig. 5.9 line 1, the annotation @PrmClass is a mark to tell the compiler it is handling a probabilistic class. The latter necessarily contains some probabilistic attributes, which are annotated with @PrmAttribute. They carry the information needed to describe their counterpart An alternative way to introduce the probability in rules using the IRL evaluate operator. Rule 5.5 evaluates the risk that a Subscriber is participating in a fraud. The vertical bar in the rule above stands for "knowing that" and corresponds formally to the conditional probability of a random variable.

In the instruction prob(sub.risk==true| hp.risk==true), the conditional context is explicitly mentioned and it refers to the fact that hp.risk==true. However, one might simplify the syntax by considering implicitly every fact in the WM. As a consequence, prob should be stateful to facilitate writing the rules without being rent work is using aGrUM that can deal with PRMs. We have also tested JSmile [START_REF] Bayesfusion | SMILE : Structural Modeling, Inference, and Learning Engine[END_REF] as a probabilistic engine. However, we were limited by the lack of relations and object concepts in such a framework. Recall that the compilation part performs a rewriting from the rules semantic model, which encompasses probabilistic data, to runtime functions, which actually call the probabilistic engine 6 . In our case application, the PRM is generated by a XOM compilation and read by the probabilistic engine. It is also possible to read both models from external files.

Furthermore, our architecture allows for a good inter-operability between both platforms. On one hand, rules execution can change the state of the WM and consequently the random variables in the PRM system through incremental operations, i.e., add/remove evidence, objects or relations. For instance, the action part of Rule 5.6 updates the WM by posting an evidence on the risk attribute. Therefore, the probabilistic engine should operate in a lazy mode, that is, it must record every incremental WM update until the next probabilistic query. Then, it accordingly updates the PRM system and performs inference. After converting the PRM system into a grounded BN, the IJTI algorithm 5 is used to optimize the corresponding JT re-evaluation by only recomputing what has been invalidated between two calls to the probabilistic engine.

Towards Advanced techniques

In this section, we provide foundations for an alternative approach to handle rules uncertainties using a global probabilistic operator. In the sequel, we intentionally ignore the action part, i.e., then/else{..} declarations, in rules examples as it is irrelevant to our discussion.

Preliminary

So far, the approach we implemented to express rules uncertainties is to replace every Boolean test over condition variables with a Boolean test over the proba-i.e., objects are known and reference slots are correctly set, the ground BN 9 is not necessarily connected (isolated sub-graphs) and we emphasize that it contains random variables corresponding to attributes of different classes. At the end, two random variables obtained from the instantiation of the same class attribute are regarded as different BN nodes.

Simple conditions and a general approach

In this situation, only class conditions appear in when {. . . } parts. The propagation of probability operator is straightforward and the joint posterior P(∧ i≥1 CN F i ) needs to be evaluated. However, we need to introduce some functional nodes to compute new random variables that result from applying predicate in a ijk . A functional node may involve some algebraic operations such as random variables additions or multiplications. Consider Rule 5.8.

In particular, in order to check the condition in line 5, we have to evaluate the following: x:X (a 211 (X 1 , X 2 ));

} }

Here we need to iterate the same process as before and construct the leaf target as the conjunction of leaves obtained from processing ling 5 and 6.

It remains to point out that even if we want to move probabilistic calls from inside a when{...} declaration, it is still possible to evaluate the probability of some particular clauses or atoms inside the condition part besides the global probability operator's use. Such a situation occurs when we want to constrain particular variables in addition to the global constraint we have on top of the condition part.

This is naturally to be given a higher evaluation priority:

At the end, we apply the general probability operator to the atom a 111 (X 2 , p),

where p is the result of the probabilistic inference P(X 1 ≤ 2).

will be able to reduce exists and its negation not to computing some functional nodes. Let us illustrate this through an example based on the class model 5.13.

Consider the simple Rule 5.9 with two clauses and one atom for each.

Rule 5.9: an IRL rule with probability operator and one exist

Assume for example that we have three X WMEs : x 1 , x 2 and x 3 . In order to evaluate the condition in line 4, the compiler must translate beforehand the expression into a query of a new target. Then, we need to add this latter, at runtime, into the PRM system. Again, we need some auxiliary random variables to define this target. For instance, lt 2 β 2 is a random variable introduced to test whether its parent (x 2 .X 2 )'s value is less than or equal to β 2 and hence, it takes two values as we can see in Fig. 5.16.

Fig. 5.17 depicts the final network obtained. In particular, it shows that we need to query the leaf node or to see whether the condition in line 4 of Rule 5.9 is satisfied. x:X (a 111 (X 1 , X 2 ));

Note that in the Boolean case, one can halt the pattern matching search in an existence condition as soon as a WME is found. However in the probabilistic case, we need to construct a graph that covers all the WMEs to evaluate the exists condition and again, this may lead to a huge amount of computations. Now, we discuss how rules aggregates could be processed and let us begin with a simple example as in Rule 5.10. In the presence of nested aggregates, one solution would be to evaluate the most enclosed one and combine the output with the superior aggregate block and so on.

We want to conclude this discussion by emphasizing that there exists some supported PRM aggregates such as min, max, forall and, average that can be mapped directly to their counterparts in the rules after computing functional nodes when needed.

Conclusion

This chapter introduced an effective approach to integrate probabilistic reasoning into modern BRMSs. The solution we proposed is based on a loosely coupling between BRMSs and PRMs. We also highlighted the natural mapping between both paradigms and gave an operational method to assure it. Then, after describing the ODM BRMS, we proposed a general architecture of the coupling platform and described our technical contribution, which is implemented as a prototype on top of ODM.

Chapter 6 Discussion and Future Works

We conclude this manuscript by summarizing the main contributions and discussing some directions for future works.

Summary

In the last decades, BRMSs emerged as complex platforms that help organizations to effectively manage the rules that drive and guide the business practice.

The main idea of such systems is to externalize the business logic, expressed in terms of Business Rules, and to allow business users to be essential and main actors in their life-cycle management. Such an approach gains more and more acceptance among organizations as it provides an agile development of business applications. In Chapter 1, we discuss the business rules approach. If this approach advocates the use of Business Rules Management Systems, it does not provide explicit guidelines about handling uncertainties in the domain. In addition, there is no satisfactory method implemented in current BRMSs to cope with this question neither. However, uncertainty is a pervasive property of data and a good uncertainty representation coupled with a mechanism for reasoning Appendix A

Proofs

Proof of Proposition 4.3.4:

Proof of Theorem 4.3.5 -mutual exclusivity: if property 1) is satisfied, then T contains no edge, therefore properties b) and c) cannot be satisfied. Now, assume that there exist r 1 , r 1 such that µ r 1 →r 1 = µ r 1 →r 1 = T (property 2). Let r 2 be any clique in V(T ). Without loss of generality, assume that r 1 lies on the path i 1 = r 2 , i 2 , . . . , i p = r 1 between r 2 and r 1 . Then, by Proposition 4.3.4, Otherwise, neither properties a) nor b) hold. Assume that property c) neither holds. Then, for all edges (i, j), exactly one of µ i→j or µ j→i is equal to T and the other one belongs to {∅, , T }. Let (i 0 , j 0 ) be such that µ i 0 →j 0 = T and µ j 0 →i 0 = T . Then, if |Adj(i 0 )| = 1, clique i 0 satisfies property c), a contradiction.

As we assume that property b) neither holds, there exists i 1 ∈ Adj(i 0 ) such that µ i 1 →i 0 = T and µ i 0 →i 1 = T . The same reasoning holds for i 1 , hence either i 1 is a leaf, which contradicts property c) or i 1 has another neighbor i 2 such that µ i 2 →i 1 = T and µ i 1 →i 2 = T . By induction, we create a path i 1 , . . . , i n of maximal size. This path is necessarily finite since T is a finite tree, hence clique i n is a leaf which, therefore, satisfies property c), a contradiction. Consequently, when properties a) and b) do not hold, property c) holds.

One can now prove separately the optimality for each property of Theorem 4.3.5, since these properties are mutually exclusive:

Proof of Theorem 4.3.5 -property 1's optimality: r is the only node in T .

Choosing it as a root is therefore optimal.

Lemma A.0.1. Let i, j ∈ V(T ) be such that ∈ µ j→i and µ i→j = ∅, then ∀l ∈ V -j (i) : δ(l) = δ(j) + len(l-j).

Proof. Note that when / ∈ µ j→i , T is up-to-date in the current inference and there is no need to perform any computation. The proof is achieved by induction on n = len(l -j). For n = 1, we have l = i , so by Equation (4.2) and the fact that ∈ µ j→i and i ∈ Adj i (j), we get δ j→i (i) = 1. As a consequence,

In this case, it follows that δ k →k (i) = δ k →k (j). We conclude that δ(i) = δ(j) + 1.

Now suppose this property is satisfied for n -1 > 1, let us prove that it remains true for n. Let l be such that len(l -j) = n -1. Let {p} = Adj i (l).

Then δ(l) = 1 + (k ,k)∈A(T )\{(p,l)} δ k →k (l) because δ p→l (l) = 1 (since ∈ µ p→l and {l} = Adj l (p)). Knowing that T / ∈ µ l→p , we get δ p→l (p) = 0, it follows that δ(p) = (k ,k)∈A(T )\{(p,l)} δ k →k (p). Now using the same reasoning as in the case n = 1 and by remarking δ l→p (p) = δ l→p (l) = 0 because / ∈ µ l→p , we conclude that

By applying the induction hypothesis on l, where len(l -j) = n -1, we obtain :

and in all these cases we have:

Otherwise, let k = r then k = r and we have also 1 Proof of Theorem 4.3.5 -property 2's optimality: Under the notations of property 2), it is sufficient to prove that for any i not in V 1 , δ(r) ≤ δ(i) 2 . Without loss of generality, assume that i ∈ V -r (r). Let (k, k ) ∈ A(i -r), where A(i -r) is the set of arcs induced from i -r. We either have {k } = Adj r (k) or {k} = Adj r (k ). Assume for instance that {k } = Adj r (k) , k = r, 1 if k = r then k = r and the equality also verified. 2 all the nodes are computationally equivalent if ∀i ∈ V(T (k ,k)∈A(i-r) δ k →k (r) ≤ (k ,k)∈A(i-r) δ k →k (i).(1) Now for (k, k ) / ∈ A(i-r) it is easy to see that δ k→k (i) = δ k→k (r) and hence :

(k,k )∈A(T )\A(i-r) δ k →k (r) = (k,k )∈A(T )\A(i-r) δ k →k (i). ( 2). By comparing (1) and ( 2) we get that δ(r) ≤ δ(i) for i / ∈ V 1 . So far, we obtain, by Lemma A.0.2, for any i in V 1 , δ(r) = δ(i) and for any i not in V 1 , δ(r) ≤ δ(i), therefore we have r ∈ Argmin i∈V(T ) δ(i).

Proof of Theorem 4.3.5 -property 3's optimality: Let i in V(T ) s.t. i = r. first case: µ Adj i (r)→r = ∅. Assume that T, ∈ V -i (r), because otherwise there is no need to perform any computation, as either there is no query or no modification in T ; so by Lemma A.0.1 we have δ(i) = δ(r) + len(i-r) because i ∈ V -r (Adj i (r)).

Hence δ(r) < δ(i).

second case: we omit the case µ Adj i (r)→r ∈ {T, }, but one should use the same methodology as in property 2)'s proof and the fact that for any k, k in i-r s.t {k } = Adj r (k) : µ k→k = µ i→Adjr(i) and examine δ k →k (r) and δ k →k (i).

Proof of Proposition 4.3.6 : Given a root r, δ i→j (r) corresponds, by construction, to the fact that ψ i→j is necessary during the current inference and was