PR-OWL Decision: Toward Reusable Ontology Language for Decision Making under Uncertainty Shou Matsumoto, Kathryn B. Laskey, Paulo C. G. Costa Department of Systems Engineering and Operations Research George Mason University Fairfax, VA [smatsum2, klaskey, pcosta]@gmu.edu Abstract—Decision making is a big topic in Intelligence, decision maker may lose his/her job as a consequence of failing Defense, and Security fields. However, very little work can be the exam, the decision maker would definitely study hard. This found in the literature about ontology languages that well illustrates how difficult it would be for someone to make simultaneously support decision making under uncertainty, decisions based only on metrics of uncertainty (e.g. probabilities abstractions/generalizations with first-order expressiveness, and or likelihoods of events), and how important values and forward/backward compatibility with OWL—a standard preferences are in actually taking some action. Consequently, language for ontologies. This work proposes PR-OWL Decision, a ontologies for decision making need to support both uncertainty language which extends PR-OWL—an extension of OWL to and values (or preferences of decision makers). Unfortunately, support uncertainty—to support first-order expressiveness, current ontology tools and languages often do not have decision making under uncertainty, and backward/forward standardized constructs for representing preferences. compatibility with OWL and PR-OWL. On the other hand, there are models that were not originally Keywords—ontology, decision making, uncertainty, OWL designed for ontologies, but can be used for decision making under uncertainty with explicit representation of values. For I. INTRODUCTION instance, classic probabilistic decision models like Influence Ontologies are engineering artifacts which consist of formal Diagrams (ID) [16] can be enough to just represent and solve vocabularies of terms, usually describing specific domain decision-making problems—with representation of actions and knowledge and accessed by persons or computers sharing a values or preferences of a decision maker—with support for common view or domain application. Various interdisciplinary uncertainty. However, IDs perform probabilistic reasoning works addressing the engineering aspects of this field have been about propositional (as in propositional logic) statements, which held in the recent years by the information systems—in a is not expressive enough to capture many important situations; broader sense—community [1, 2, 3, 4, 5]. The Web Ontology thus we would like to have first-order expressiveness (as in First- Language (OWL) is a standard ontology language which Order Logic), with functions, predicates, and quantification. represents classes, properties, and individuals in Semantic Web OWL direct semantics [6, 17]—mainstream in ontology documents [6]. In 2005, Probabilistic Web Ontology Language languages—offer first-order expressiveness, but they do not (PR-OWL) [7] was formulated to address OWL’s lack of natively support uncertainty and decisions (i.e. support for support for uncertainty—a ubiquitous factor in complex real- efficiently representing and treating actions, values and world problems. As a continuing effort, version 2 of PR-OWL preferences of decision makers). PR-OWL, being an extension [8] was formulated in order to address some backward of OWL, also offers first-order expressiveness, and it also offers compatibility issues with its predecessor OWL. support for uncertainty, but it lacks support for decisions. It was Nevertheless, continuous efforts have been performed in the already stated that IDs offer support for decision and field of decision support, especially with models supporting uncertainty, but have only propositional expressiveness. It thus uncertainty [9, 10, 11, 12, 13, 14, 15]. Decision making is the becomes of interest to extend the results we have for the process of selecting a course of action among several propositional cases to the first-order case. Therefore, there is a possibilities, based on values or preferences of some decision need to extend the syntax of PR-OWL and its underlying maker. Values and preferences play a very important role here, logic—Multi-Entity Bayesian Network (MEBN) [18]—to because they represent the desirability of an outcome, in a include elements of IDs. PR-OWL Decision, the extension manner that is different from the likelihood or probability that proposed in this work, addresses this issue. the outcome will happen. Reuse receives special attention, because it is a common, yet For example, one’s probabilistic model may state that the powerful way to drastically reduce the development effort. This probability of failing some exam is 20% if you do not study. The is why special care is taken for backward and forward decision maker may consider this is an acceptable probability compatibility (with OWL). Backward compatibility can be for choosing not to study, given that the impact of failing is achieved by designing the new language so that systems meant nothing more than minor embarrassment. However, if the for the new language will automatically function with the older language, due to syntactical similarities. This offers incentives STIDS 2016 Proceedings Page 37 for legacy system users to migrate to new solutions. Forward increasingly complex and competitive, both in terms of pricing compatibility can be achieved by composing the new language’s and available functionalities. Problems in intelligence, defense, syntax with valid constructions of the older language. Legacy and security are diverse, thus it’s natural to think that not all systems may not be able to handle the new portions perfectly, clients will use of the entire set of available system features. but it ought to be guaranteed that the new construction will not Quickly—and automatically—offering a proper set of features cause legacy systems to fail catastrophically. This increases the to the client, given their particular needs, would help in practical usefulness of a new solution, because part of new establishing a competitive price, and also to avoid unnecessary models can be built on well tested legacy systems. use of computational resources caused by unused features (the latter may become rather critical in embedded systems). Our Examples of kinds of decision problems (and related tasks) Proof of Concept model mainly addresses this issue. that could particularly benefit from the new solution are: The following list summarizes some important concepts of • Those which the number of decisions and available actions SPL that are referenced throughout this paper: (choices) are not known in advance. For instance, we can have decisions that repeat over time and the number of • Features are common and variant characteristics among a choices may increase/decrease for each decision. Other types set of software systems. These are related to (or originated of repetitions (in probabilistic dependency, or on utility from) a set of domain requirements, and can be mapped to a functions) can also be treated by PR-OWL Decision. set of software assets, so it can be thought as an abstraction that maps requirements to reusable components. • Those using abstractions/concretizations from OWL class hierarchy. For instance, an OWL ontology may indicate that • Configuration can be thought as a set of features which a “Tablet” is a subclass of “Computer”, thus a decision jointly satisfies constraints of consistency (e.g. dependency making model developed for a “Computer” might work well and compatibility). We can move from a configuration to with a “Tablet” (e.g. decision models about information theft another by adding, removing, or substituting features, of involving computers/tablets). PR-OWL Decision handles course, without breaking consistency rules. such inheritance natively. • Domain requirements are requirements identified and • When the process involving decision making itself is treated in the domain engineering process (i.e. “inter- performed or aided by multiple software systems, system” requirements that will derive features and related interoperability plays a major role. OWL has strong support reusable components). for interoperability, so does PR-OWL Decision. • Application requirements are requirements treated in the • Iterative/incremental model development process may application engineering process (i.e. emerging requirements benefit from PR-OWL Decision, due to its aim in reuse. A that will result in a single product). A “requirement” in SPL PR-OWL Decision ontology can be developed can be either a domain or application requirement. incrementally, starting from a well-tested deterministic The Proof of Concept ontology was developed in a ontology, then creating a PR-OWL ontology which imports iterative/evolving manner, starting from a simple, deterministic the deterministic ontology (so that the original ontology is kept unchanged), and finally a PR-OWL Decision ontology OWL ontology, which captured the features and their can import the PR-OWL ontology. Cost of verification and constraints. Then, a PR-OWL ontology which encodes some validation is reduced, because previously tested artifacts are probabilistic relationships between the features, requirements, and assets was developed by reusing (importing) the original reused in “as-is” basis. An example in Software Product Line domain is discussed in the following sub-section. ontology. Finally, a PR-OWL Decision ontology was developed in order to represent the costs and profits (with associated risks) of incorporating new features to some configuration given A. Software Product Line (SPL) Domain emerging requirements. The resulting ontology is able to solve, Examples presented throughout this paper are based on a for example, a decision problem of choosing the set of features Software Product Line (SPL) ontology, which was developed as to (re)use during application engineering, under maximum a Proof of Concept for PR-OWL Decision [19]. SPL is a “family” expected profit (or minimum expected cost) criteria. of software-intensive systems that share a common set of characteristics satisfying specific needs of a particular domain, II. PR-OWL and are developed from a common set of software assets [20]. The engineering process of SPL is often divided into two phases: Traditional ontologies have no built-in mechanism for domain engineering (the process of analyzing, architecting and representing or drawing inferences under uncertainty. The developing reusable components among the family) and Probabilistic Web Ontology Language (PR-OWL) consists of a application engineering (process of producing a single product set of classes and properties (relationships) that collectively by integrating and/or customizing reusable components). Proper form a framework for building and reasoning with probabilistic SPL practices enable fast production and customization. ontologies, yet keeping syntactical compatibility with OWL. The purpose of a probabilistic ontology is to describe knowledge Quickly developing a series of configurable/customizable about a domain and its associated uncertainty in a principled, software systems is important not only because software is structured, and sharable way, so that it can be applied to support ubiquitous in any current intelligence, defense or security semantic applications working in complex open-world system, but also because such systems are becoming environments. PR-OWL 2 is an extension of OWL 2 with STIDS 2016 Proceedings Page 38 enhanced meta-level 1 support for specifying probability distributions of OWL properties [8]. Constructs of PR-OWL basically follow an abstraction inherent from Multi-Entity Bayesian network, which is explained in next sub-section. A. Multi-Entity Bayesian Network Multi-Entity Bayesian Network (MEBN) [18] is the underlying logic of PR-OWL (and its version 2). For this reason, a PR-OWL specification can be informally seen as a scheme for describing a MEBN model in OWL. MEBN extends BN [21] by combining the expressiveness of First-Order Logic and the inference power of BN. MEBN represents the world as a collection of inter-related entities, their respective attributes, and relations among them. Knowledge about attributes of entities and their relationships is represented as a collection of repeatable patterns, known as MEBN Fig 1. Structure of MEBN Fragment. Fragments (MFrags). A set of well-defined MFrags that collectively satisfies first-order logical constraints ensuring a • Resident nodes (rounded yellow rectangles) are predicates unique joint probability distribution is a MEBN Theory (as in First-Order Logic) which represent the actual random (MTheory). The probabilistic portion of a consistent PR-OWL variables that form the core subject of an MFrag. MEBN 2 ontology represents an MTheory. logic requires that the local probabilistic distribution of each resident node should be uniquely and explicitly defined in its An MFrag represents uncertain knowledge about a home MFrag. The possible values of a resident node can be collection of related random variables (RVs). RVs, also known instances of entities (e.g. individuals of an OWL class). In as “nodes” of an MFrag, represent the attributes and properties this example, the resident node “fulfills” represents a of a set of entities. A directed graph represents dependencies relationship between a feature and a set of requirements (of among the RVs. Since an MFrag is in fact a template that can be any type) that the feature satisfies/fulfills. repeatedly instantiated to form Situation-Specific Bayesian Networks (SSBNs), their RVs usually contain as arguments one • Context nodes (green pentagons) are Boolean (i.e. logical or more ordinary variables, which are variables that are datatype) random variables representing conditions that substituted by instances of entities during the instantiation must be satisfied to make a distribution in an MFrag valid. process. SSBNs are regular BNs that are formed, usually in First-Order Logic formula (which may reference predicates response to a query, to address a particular situation that may in other MFrags) can be used in order to express complex occur in the domain. Since a SSBN is just a regular BN, conditions. For instance, the context node traditional BN algorithms, like junction tree algorithm [22], can is_derived_from(req,domReq) indicates that the MFrag is be applied to it with no special adaptations. Usually, a SSBN only valid if req (a requirement) is derived from domReq (a would look like a collection of “similar” nodes, differing only domain requirement). Any combination of req and domReq by their arguments’ values. not satisfying the context node will cause the instances of the nodes in that MFrag to be marked as invalid and thus some MEBN provides a compact way to represent repeated default probability distribution (instead of the distribution structures in a Bayesian Network. An important advantage of specified in the MFrag) will be applied. MEBN is that there is no fixed limit on the number of random variable instances, which can be dynamically instantiated as • Input nodes (grey trapezoids) are basically “pointers” needed. Some may see MFrags as tiny “chunks of knowledge” referencing to some resident node. Input nodes also provide of a given domain. Since a MTheory is a consistent composition a mechanism to allow resident nodes’ re-usage between of such “chunks”, MEBN (as a formalism) is suitable for use MFrags. In the example, the input node fulfills(feature, cases addressing reuse of information. This property is used in domReq) is a reference to the resident node fulfills in the this work in order to achieve efficient reuse of ontology. same MFrag. The arc from fulfills input node to fulfills resident node (i.e. the recursive dependency) indicates that Finally, MEBN categorizes random variables into three whether a feature fulfills or not some requirement depends different types. See Figure Fig 1 for a graphical representation. on whether the feature fulfills or not a domain requirement Directed arrows going from parent to child variables represent which derived the requirement in question. dependencies. The list of arguments in parenthesis are replaced by unique individuals when the SSBN instantiation process is • Ordinary variables appear as arguments of nodes in the triggered. The following list describes the elements presented in example (see labels feature, req, and domReq). They are Fig 1: “non-random” variables that can be replaced with instances 1 The language offers means for specifying or extending information or rules about other elements in the ontology. STIDS 2016 Proceedings Page 39 of entities in order to fill the arguments of nodes. Constraints about the type of ordinary variables are declared in “isA” context nodes, whose first argument is an ordinary variable and the second argument is a name of some entity (e.g. some OWL class). III. MULTI-ENTITY DECISION GRAPH Multi-Entity Decision Graph (MEDG) provides a framework for modeling and solving decision problems which require both first-order expressiveness and handling of uncertainty; and it forms the semantics, mathematical formalism, and a graphical abstraction of documents written in PR-OWL Decision. Consequently, in a technical view, PR- OWL Decision documents can be seen as a computer-readable representation of MEDG models that can be persisted in storage media or streamed to a network. MEDG extends MEBN by combining the expressiveness of a probabilistic First-Order Logic—MEBN—with the ability to represent decisions and values (utilities) and to perform decision making under uncertainty, with maximum expected utility Fig 2. Structure of MEDG Fragment. criterion, of Influence Diagrams (ID) [16]. IDs are a generalization of Bayesian Networks (BN) [21] which consist of information of hasSuggestion (whether such feature can be a directed acyclic graph of probabilistic nodes (just like nodes suggested to the configuration or not). in BN, it corresponds to random variables), decision nodes (they • Utility resident node: this blue diamond node is a new type correspond to decisions to be made, and represent available of node in MEDG which represents the class of utility nodes. actions), utility nodes (corresponds to utility functions, which MEDG logic requires that the utility function of a utility quantifies values or preferences of a decision maker), resident node must be uniquely and explicitly defined in conditional arcs (arcs that points to a probabilistic node and some home MFrag. Utility resident nodes cannot be parents represent probabilistic dependence), information arcs (arcs that of resident nodes or decision resident nodes, and cannot be points to decision nodes and represent information that have to used in context nodes. Arcs pointing to these nodes are be available at the time of the decision), and functional arcs (arcs functional arcs and represent inputs of the utility function. that points to utility nodes and represent inputs for the utility Under the multi-attribute utility criteria, we can represent the function). The main idea of MEDG is, therefore, to augment “global” utility function as a combination of sub-functions MEBN with decision nodes, utility nodes, information arcs and (i.e. the utility function can be decomposed to multiple sub- functional arcs. functions involving only a smaller subset of variables, and Following the convention of MEBN, the world is each of such sub-functions can be represented by utility represented in MEDG as a collection of inter-related entities, resident nodes). In such context, when some utility resident their respective attributes, and relations among them. node is a child of utility resident nodes, it represents the Knowledge about attributes of entities and their relationships is combining function over the parents. If no such combining represented as a collection of network fragments that represent function is specified, then the unweighted additive function repeatable patterns, known as MFrags (now, this name stands (i.e. a simple sum over the sub-functions) is implicitly for MEDG Fragments instead of MEBN Fragments). A set of assumed by default. In Fig 2, transitionCost represents the well-defined MFrags that collectively satisfies logical cost of adding the feature “feat” to the current configuration constraints is called MTheory (similarly, this name now stands “config” (given the decision about whether to actually add or for MEDG Theory). A consistent PR-OWL Decision ontology not such feature). represents an MTheory. Fig 2 shows the components of a MEDG Fragment, and the following list is a description of such • Resident node (or “probabilistic” resident node), input node, context node, and ordinary variables: these components: elements play the same role as in MEBN. However, input • Decision resident node: this orange rectangular node is a and context nodes can now have references to Decision new type of node in MEDG and it represents the class of resident nodes. The three context nodes in Fig 2 are declaring decision nodes. It can be used in input nodes or context that the type of the ordinary variable config and feat are nodes, and just like resident nodes it needs to be uniquely respectively the Configuration and Feature entities, and the and explicitly defined in some home MFrag. As in IDs, arcs values of these ordinary variables must not be equal. The pointing to these nodes are information arcs that represent input node hasSuggestion is a reference to a resident node in information that are assumed to be known at the time of another MFrag (not shown in the figure, though). The taking the action. In the example, incorporateFeature resident node hasError is the probability of the new feature represents the decision of whether to add or not some feature feat to cause error to current configuration config, and it has “feat” to the current configuration “config”, given direct impact on the utility. STIDS 2016 Proceedings Page 40 From a semantic viewpoint, backward compatibility (i.e. Inputs: tools that support MEDG should also support MEBN) is only • Queries: a list of nodes (instances of decision or resident nodes) possible if MEDG models without presence of decision and that will be guaranteed to be present in SSID. utility nodes are equivalent to the respective MEBN model. This • Instances of entities: collection of all known instances of entities. explains why components of MEBN (e.g. resident nodes, input These can be OWL individuals in PR-OWL Decision. nodes, context nodes) are fully reused in MEDG. It is worth • Evidence: list of all random variables and decision nodes with noting that these approaches for backward compatibility are known values (and their respective values as well). directly applicable to PR-OWL Decision as well, because PR- 1 Include all nodes in evidence and queries in SSID. OWL Decision ontologies semantically represent MEDG 2 Include all possible instantiations of utility nodes (by instantiating all models, and they share the same abstractions (i.e. nodes, entities, possible values of arguments of utility resident nodes) to SSID. states, etc.). 3 Mark all nodes in SSID as “unfinished”. 4 For each “unfinished” node “n” in SSID, do: On the other hand, forward compatibility (i.e. tools that 4.1 Find the resident node (or decision/utility resident node) “res” support MEBN should be able to open MEDG models) is not whose “n” is its instance. directly guaranteed at the logic level, obviously because MEBN 4.2 If the MFrag of “res” is marked as “unsatisfiable”, set “n” to use semantics cannot handle decision and utility nodes. Instead, default distribution, mark “n” as “finished”, and continue at line 4. forward compatibility is achieved at the syntactical level in PR- 4.3 For each context node “cx” in the same MFrag OWL Decision by asserting that decision resident nodes and 4.3.1 If “cx” is unsatisfiable (i.e. 100% false), then mark the utility resident nodes in PR-OWL Decision are subclasses of MFrag as “unsatisfiable”, set “n” to use default distribution, resident nodes of PR-OWL. This shall enable tools compatible mark “n” as “finished”, and continue at line 4. with PR-OWL to open PR-OWL Decision ontologies, and allow 4.3.2 Else if “cx” is unknown (i.e. neither 100% true or 100% decision and utility nodes to be displayed and edited as if they false), then: were just resident nodes. This is why decision resident nodes and 4.3.2.1 Virtually transform the context “cx” to input node. utility resident nodes in PR-OWL Decision are defined 4.3.2.2 Create arcs from new input node to all resident respectively as resident nodes with no probability distribution, nodes (and decision nodes) in same MFrag. and single-valued resident nodes in PR-OWL Decision. 4.4 For each parent “p_res” of “res”, do: 4.4.1 Instantiate arguments (ordinary variables) of “p_res” that match the formulae in context nodes in the same MFrag. A. Entailments of PR-OWL Decision: MEDG Inference 4.4.2 Instantiate “p_res” with the combination of arguments Entailments of PR-OWL Decision are information that can found in previous step. be inferred from a PR-OWL Decision ontology document, based 4.4.3 For each instance “p_n” of “p_res”, do: on its underlying semantics—MEDG. This includes anything 4.4.3.1 Mark “p_n” as “unfinished”, and add it to SSID (if not that can be deterministically inferred (by First-Order Logic or its already there). subsets), anything that can be inferred by first-order 4.4.3.2 Add arcs from “p_n” to “n” in the SSID. probabilistic reasoning (which requires combination of First- 4.5 Mark “n” as “finished”. Order Logic and probabilistic inference), and anything that can 5 Prune (remove) from SSID all nodes that are d-separated or be inferred by combining the previous inference with decisions disconnected from queries and utility nodes. and utility functions. The former two can be achieved with 6 Compile the LPD/utility scripts of all probabilistic and utility nodes, so that the scripts are translated to actual probability distributions/tables MEBN and PR-OWL (actually, the first one can even be or actual utility functions/tables. achieved with OWL direct semantics and description logic 7 Return (output) SSID. reasoning), so they are not important in the context of this Listing 1: pseudocode for generating SSID. document. The last one is our focus, because it requires inference in MEDG semantics. Namely, the tasks of calculating expected utility, and to find optimal policy under maximum expected utility criterion are important entailments of PR-OWL Decision that will be considered in this research. We propose an algorithm (described in Listing 1) adapted from [23] for grounding a MEDG Theory based on entity information and evidence currently available in the knowledge/data base (in the context of PR-OWL Decision, the knowledge/data base is the ontology itself, or it can be a separate ontology, but consistent with PR-OWL Decision) to generate a Situation-Specific Influence Diagram (SSID) in order to solve the above tasks. Fig 3 illustrates grounded inference of MEDG in the context of PR-OWL Decision. In the figure, data/evidences retrieved without probabilistic inference (e.g. OWL individuals or OWL Fig 3. Grounded inference of MEDG. property assertions) will be combined with elements of MEDG calculate expected utility or find optimal policy) IDs can be used in order to instantiate the SSID. Once SSIDs are generated, they to solve SSIDs. are equal to ordinary IDs, so any algorithm for solving (e.g. STIDS 2016 Proceedings Page 41 B. A Script Language for Utility and Probability Distribution ::= | A resident node in MEDG specifies a Local Probability ::= Distribution (LPD), a generic specification of conditional "if" probabilities of random variables that can be instantiated from "have" "(" ")" that resident node, given their parents. However, since MEDG "else" represents generalizations, LPDs cannot be specified in a ::= "any" | "all" “propositional” manner, like a table of conditional probabilities ::= [["."|","]]* for all possible combinations of parents’ states. Similarly, utility ::= [ "|" ]* functions of utility resident nodes also cannot be specified in a ::= [ "&" ]* ::= [ "~" ] “propositional” manner. ::= "(" ")" We propose a scripting language for specifying LPDs and | ["(" ")"] utility functions in MEDG in a uniform and “non-propositional” "=" ["(" ")"] manner, by extending the scripting language of [23, pp. 17-18] ::= [["."|","]]* with more support for first-order syntax, such as support for ::= | ordinary variables in conditions, support for arguments in nodes, ::= "[" "]" more support for nodes with states dynamically instantiated, and ::= | ::= "=" [ "," ]* support for non-normalized values (for utilities, which do not ::= [ ]* necessarily sum up to 1). Special care was taken for backward ::= [ ]* compatibility, so that old scripts are also valid in the new ::= [ ] grammar. ::= | | "(" ")" Listing 2 shows a tentative version of the new grammar in ::= Backus–Naur Form [24] for a script for specifying utility and | "CARDINALITY" "(" [] ")" LPD. Listing 3 is an example of LPD script that complies with | "MIN" "(" ";" ")" the proposed LPD grammar (it specifies the probability | "MAX" "(" ";" ")" | distribution of node fulfills of Fig 1). ::= Table I is an example of a conditional probability table that ::= "+" | "-" can be generated from Listing 3, when SSID is instantiated. In ::= "*" | "/" this example, the ordinary variable “feature” was substituted by ::= [ | ]* an entity instance called “F1”, and the ordinary variable Listing 2: BNF grammar of LPD/utility script. “domReq” (i.e. a domain requirement) was substituted by entity if any feature,domReq have ( fulfills(feature,domReq) = true ) [ instances “R1” and “R2”. We can see in the table that if at least true = .7, false = .3 one parent is true, then the probabilities are set to true = 0.7, and ] else if any feature,domReq have ( fulfills = false ) [ false = 0.3. When no parent is true, but at least one parent is true = 0.1, false = 0.9 false, then the probabilities are set to true = 0.1, and false = 0.9. ] else [ absurd = 1 ] Otherwise, the probability of absurd is set to 1. This complies Listing 3: Example of LPD script. with Listing 3. actions that a decision maker can take) and utility variables (i.e. Scripts for specifying LPDs are not formally part of PR- values and preferences) in probabilistic ontologies. OWL, so such scripts are directly stored as literal data The new language provides definitions of special classes and properties. We will follow the same approach and store scripts properties (relationships) that collectively form a framework for in the new grammar as literal (text) data properties in PR-OWL building and reasoning with decision problems expressed as Decision as well. Consequently, the new LPD scripting probabilistic ontologies. These new components are defined in language is not formally a part of the specification of PR-OWL terms of existing PR-OWL and OWL elements, so that Decision. syntactical compatibility with PR-OWL (and OWL) is achieved. In this chapter we define such new components and how they IV. PR-OWL D ECISION relate to PR-OWL and OWL. PR-OWL Decision, the language proposed in this research, We primarily extend PR-OWL version 2 (PR-OWL 2), extends PR-OWL in order to support decision variables (i.e. because it offers enhanced meta-level features—not present in version 1—that allows us to represent probability distributions TABLE I. EXAMPLE OF CONDITIONAL PROBABILITY TABLE THAT CAN BE OBTAINED FROM SCRIPT IN LISTING 3. STIDS 2016 Proceedings Page 42 of existing OWL properties [8]. These features are necessary Unicode characters to be used. The stereotype <> conditions for semantic-level compatibility with OWL, because in arcs represents a property that is used for importing other they enable entailments of OWL ontologies to be also contained OWL ontologies entirely. The World Wide Web Consortium in the entailments of PR-OWL 2. We also offer an alternative (W3C) recommends not to import the OWL schema vocabulary extension of PR-OWL version 1 (PR-OWL 1) for decision directly to ontologies using direct semantics of OWL, because it support in ontologies originally written in this older version as will break some compatibility with Description Logic. well. However, this is only kept for backward compatibility, and Therefore, the stereotype <> indicates that only a subset is superseded by the extension of PR-OWL 2. The version of of features are referenced. The stereotype <> is PR-OWL Decision which extends PR-OWL 2 is called PR- used instead of <> in XML Schema Definition OWL 2 Decision, and the version that extends PR-OWL 1 is (XSD) simply because the word “definition” is part of its official called PR-OWL 1 Decision; but for simplicity, in this document name. We’ll simply use “PR-OWL Decision” to refer to the one that extends PR-OWL 2. In the syntax viewpoint, backward compatibility with PR- OWL is forced because we explicitly import the PR-OWL schema vocabulary into the new schema (thus, tools compatible A. PR-OWL Decision Schema Vocabulary with PR-OWL Decision are forced to handle PR-OWL schema Just like any OWL and PR-OWL document, a PR-OWL as well). Forward compatibility (i.e. tools compatible with OWL Decision document needs to be built by combining a set of pre- or PR-OWL will be able to open PR-OWL Decision defined building blocks. A PR-OWL Decision document is said documents—but not necessarily execute some reasoning to be syntactically valid if the document is validated against a process) is achieved because PR-OWL Decision schema schema vocabulary. A schema vocabulary is a document that vocabulary only uses building blocks of OWL and PR-OWL, partially defines another document’s structure with a list of legal and the PR-OWL schema vocabulary only uses building blocks elements, attributes, built-in classes and properties. compatible with OWL’s RDF/XML syntax and vocabulary— Fig 4 illustrates how the PR-OWL Decision schema thus the entire import closure is forward compatible. vocabulary relates to other vocabularies. The vocabulary (schema) files of PR-OWL 1 Decision and PR-OWL 2 Decision B. Syntactical Differences with PR-OWL reuses constructs from PR-OWL 1 and PR-OWL 2 respectively. PR-OWL Decision introduces the concept of decision nodes While the vocabularies of PR-OWL are valid ontologies in and utility nodes to PR-OWL. No changes will be made to OWL direct semantics (thus, we can use the OWL “import” existing syntactical blocks of PR-OWL, which will be fully mechanism to reuse the entire document), the OWL RDF/XML reused—imported—by the PR-OWL Decision. Fig 5 illustrates syntax vocabulary file/document has some constructs that are the classes of PR-OWL 2 Decision and their relationships to PR- not defined in OWL direct semantics, so only a subset of OWL OWL 2 classes. Fig 6 illustrates the classes of PR-OWL 1 vocabulary document is used in PR-OWL vocabulary. Finally, Decision and their relationships to PR-OWL 1 classes. The as the name implies, the OWL RDF/XML syntax document remaining paragraphs of this section basically discusses about combines syntaxes from XML (and XML Schema) and the contents of the figures. Resource Description Framework (RDF) and its schema (RDFS) [25]. The prefixes of IRIs of classes in PR-OWL 2 Decision are the IRIs of its schema vocabulary (i.e. IRIs of these classes starts From the foundation of OWL, any ontology component is with the IRI of the schema vocabulary of PR-OWL 2 Decision, identified by an Internationalized Resource Identifier (IRI), a and the IRI fragment—suffix after “#”—is the name of the standard defined by the Internet Engineering Task Force to class). Similarly, prefixes of IRIs of classes in PR-OWL 1 extend the Uniform Resource Identifier (URI) scheme. URIs Decision are the IRIs of the schema vocabulary of PR-OWL 1 and IRIs are both text identifiers that resemble web addresses, Decision. For example, the IRI of class DomainDecisionNode but URIs are limited to ASCII characters, while IRIs allow of PR-OWL 2 Decision is . The IRIs of the other DomainUtilityNode not to be used in arguments of context classes follow the same pattern, so IRIs are omitted in the figures nodes (this is achieved by “isTypeOfArgumentIn exactly 0 for sake of visibility. These classes can be mapped to MExpressionArgument” restriction), and by forcing the type components of its underlying logic—Multi-Entity Decision of DomainUtilityNode to be always UtilityVariable. Graph (MEDG)—which is presented in later section. • UtilityVariable: this is an extension of RandomVariable, a The following list describes the main elements of PR-OWL class which describes the type of MExpression. 2 Decision in Fig 5—again, please refer to the section about UtilityVariable is used to force DomainUtilityNode to be Multi-Entity Decision Graph for the semantics of these associated with only a single possible value: the utility. This elements: asserts that tools compatible with PR-OWL will see instances of DomainUtilityNode as being resident nodes with • DomainDecisionNode: this class represents decision a single value. resident nodes of MEDG (see next section for descriptions about MEDG). It extends DomainResidentNode, a class • utility: this OWL individual is a possible state of which represents resident nodes in PR-OWL, because all DomainUtilityNode created for compatibility with PR-OWL properties that are valid for the DomainResidentNode (for (thus, this OWL individual does not actually represent the instance, it should be associated with possible values, can “concept” of utility), because constraints in PR-OWL forces have parents and children, and can be used as arguments of any node to have at least one possible state. Please, notice other nodes) are also valid for DomainDecisionNode, except that numerical values of utilities in PR-OWL Decision are for the fact that LPDs are not used in DomainDecisionNode. represented in terms of utility functions, not by some OWL individual or literal called “utility”. This is similar to the • DomainUtilityNode: this class represents utility functions approach in PR-OWL for probabilities, because such values (utility resident nodes in MEDG). This is represented as are represented as probability distributions, not by some subclass of DomainResidentNode for forward compatibility, individual or literal called “probability”. so that tools compatible with PR-OWL can open utility nodes as if they were resident nodes with a single possible The following list describes the elements of PR-OWL 1 value (the utility instance). Decision (Fig 6) and compares them with PR-OWL 2 Decision: • UtilityMExpression: this is an extension of MExpression of • Domain_Decision: same of DomainDecisionNode of PR- PR-OWL 2 for DomainUtilityNode. The MExpression OWL 2 Decision. connects Node to its arguments, types, or possible values, and UtilityMExpression specifies some restrictions that force • Domain_Utility: same of DomainUtilityNode of PR-OWL 2 Decision. The “isArgTermIn exactly 0 ArgRelationship” forces Domain_Utility not to be used as arguments in context Fig 5. PR-OWL 2 Decision classes and relations to PR-OWL 2. Fig 6. PR-OWL 1 Decision classes and relations to PR-OWL 1. STIDS 2016 Proceedings Page 44 nodes; and the restriction “hasPossibleValues utility” [9] E. Acar, C. Thorne and H. Stuckenschmidt, "Towards Decision Making enables tools compatible with PR-OWL 1 to see via Expressive Probabilistic Ontologies," in In Proceedings of the 4th Domain_Utility as a resident node with single value. International Conference, ADT 2015, Lexington, KY, USA, 2015. [10] C. Guestrin, D. Koller, C. Gearhart and N. Kanodia, "Generalizing plans • UtilityLabel: this is the same of utility in PR-OWL 2 to new environments in relational MDPs," in In Proceedings of the 18th Decision. The difference is that a constraint in PR-OWL 1 international joint conference on Artificial intelligence, 2003. forces a possible state of a node to be an individual of Entity, [11] S. Joshi, K. Kersting and R. Khardon, "Generalized First Order Decision while in PR-OWL 2 this constraint is relaxed. For this Diagrams for First Order Markov Decision Processes," in In reason, utility in PR-OWL 1 Decision is an individual of International Joint Conference on Artificial Intelligence, 2009. MetaEntity—subclass of Entity. [12] S. Sanner, "Relational dynamic influence diagram language (RDDL): Language description," Australian National University, 2010. V. CONCLUSION AND FUTURE WORK [13] C. Wang, S. Joshi and R. Khardon, "First order decision diagrams for relational MDPs," in Journal of Artificial Intelligence Research, 2008. PR-OWL Decision was formulated as an extension to PR- OWL in order to support decision making under uncertainty. [14] H. L. Younes and M. L. Littman, "PPDDL1. 0: An extension to PDDL Backward and forward compatibility was ensured by reusing for expressing planning domains with probabilistic effects," Technical report. CMU-CS-04-162, 2004. both syntax and semantic elements from PR-OWL. MEDG, the underlying logic of PR-OWL Decision, augments MEBN with [15] D. Poole, "The independent choice logic for modelling multiple agents decision and utility variables, so that entailments of PR-OWL under uncertainty," Artificial Intelligence, vol. 94, no. 1, pp. 7-56, 1997. Decision can be obtained with MEDG inference. An example of [16] R. A. Howard and J. E. Matheson, "Influence diagrams," in In Readings grounded inference/solving algorithm and a script for specifying on the Principles and Applications of Decision Analysis II, 1984/2005. probabilities and utilities in MEDG was described in this [17] I. Horrocks, B. Parsia and U. Sattler, "OWL 2 Web Ontology Language document. This work is part of an ongoing Ph.D. research, thus Direct Semantics (Second Edition)," 11 December 2012. [Online]. further details on MEDG, related algorithms, and software Available: https://www.w3.org/TR/owl2-direct-semantics/. [Accessed implementations will be coming in future works. 20 July 2016]. [18] K. B. Laskey, "MEBN: A language for first-order Bayesian knowledge bases," Artificial intelligence, vol. 172, no. 2, pp. 140-178, 2008. ACKNOWLEDGMENT [19] S. Matsumoto, K. B. Laskey and P. C. G. Costa, Probabilistic Ontologies We thank UnBBayes development team of Universidade de in Domain Engineering, Washington DC: presented at the Systems Brasília, especially professor Marcelo Ladeira, M.S. student Engineering in DC Conference (SEDC), 2016. Laécio Santos, undergraduate students Guilherme Torres, Diego [20] K. Pohl, G. Böckle and F. J. van Der Linden, Software product line Marques, Rafael Martins, and Pedro Abreu for their insights and engineering: foundations, principles and techniques, Springer Science & assistance with software development. Business Media, 2005. [21] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of REFERENCES Plausible Inference, Revised second printing. Morgan Kaufmann, 1988/2014. [22] F. Jensen, F. V. Jensen and S. L. Dittmer, "From influence diagrams to [1] R. N. Carvalho, P. C. G. Costa, K. B. Laskey and K. C. Chang, junction trees," in In Proceedings of the Tenth international conference "PROGNOS: predictive situational awareness with probabilistic on Uncertainty in artificial intelligence, 1994. ontologies," in In Proceedings of the 13th International Conference on Information Fusion, Edinburgh, UK, July 2010. [23] S. Matsumoto, R. N. Carvalho, P. C. Costa, K. B. Laskey, L. L. Santos and M. Ladeira, "There’s No More Need to be a Night OWL: on the PR- [2] P. Mitra, N. F. Noy and A. R. Jaiswal, "Omen: A probabilistic ontology OWL for a MEBN Tool Before Nightfall," in Introduction to the mapping tool," in In The Semantic Web–ISWC 2005, 2005. Semantic Web: Concepts, Technologies and Applications, G. P. C. Fung, [3] T. Tudorache, "Employing ontologies for an improved development Ed., iConceptPress, 2011, pp. 267-290. process in collaborative engineering," 2006. [24] J. Backus, F. Bauer, J. Green, C. Katz, J. McCarthy, P. Naur, A. J. Perlis, [4] H. H. Wang, Y. F. Li, J. Sun, H. Zhang and J. Pan, "Verifying feature H. Rutishauser, K. Sameison, B. Vauquois, J. H. Wegstein, A. van models using OWL," In Journal of Web Semantics, vol. 5, no. 2, p. 117– Wijngaarden and M. Woodger, "Revised report on the algorithmic 129, June 2007. language Algol 60," The Computer Journal, vol. 5, no. 4, pp. 349-367, 1963. [5] O. Udrea, D. Yu, E. Hung and V. S. Subrahmanian, "Probabilistic ontologies and relational databases," in On the Move to Meaningful [25] P. Hayes and B. McBride, "RDF Semantics.," 10 February 2004. Internet Systems, 2005. [Online]. Available: https://www.w3.org/TR/2004/REC-rdf-mt- 20040210/. [Accessed 13 May 2016]. [6] J. Carroll, I. Herman and P. F. Patel-Schneider, "OWL 2 Web Ontology Language (Second Edition)," 11 December 2012. [Online]. Available: [26] D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, https://www.w3.org/TR/owl2-rdf-based-semantics/. [Accessed 20 July D. Weld and D. Wilkins, "PDDL-the planning domain definition 2016]. language.," Technical report. Yale Center for Computational Vision and Control, 1998. [7] P. C. G. Costa, "Bayesian Semantics for the Semantic Web," 2005. [8] R. N. Carvalho, K. B. Laskey and P. C. G. Costa, "PR-OWL 2.0-bridging the gap to OWL semantics," in In Proceedings of the 6th International Conference on Uncertainty Reasoning for the Semantic Web, November 2010. STIDS 2016 Proceedings Page 45