=Paper=
{{Paper
|id=Vol-1788/STIDS2016_T05
|storemode=property
|title=PR-OWL Decision: Toward Reusable Ontology Language for Decision Making under Uncertainty
|pdfUrl=https://ceur-ws.org/Vol-1788/STIDS_2016_T05_Matsumoto_etal.pdf
|volume=Vol-1788
|authors=Shou Matsumoto,Kathryn B. Laskey,Paulo C. G. Costa
|dblpUrl=https://dblp.org/rec/conf/stids/MatsumotoLC16
}}
==PR-OWL Decision: Toward Reusable Ontology Language for Decision Making under Uncertainty==
https://ceur-ws.org/Vol-1788/STIDS_2016_T05_Matsumoto_etal.pdf
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