A crucial part of verifying and validating models is the identi cation of inconsistencies. Inconsistencies can exist whenever models overlap semantically. Such overlaps are predominant in model-driven engineering, where the use of multiple viewpoints leads to a variety of incomplete representations of one or more aspects of a system. While the commonly employed rule-based approaches to identifying inconsistencies can be e ective, state of the art methods for inferring or determining semantic overlaps are not. Techniques relying on uni cation algorithms or a unifying ontology make strong assumptions, are error prone and can be costly to maintain. In this paper, an alternative approach based on Bayesian reasoning is proposed. We show how Bayesian inference combined with pattern matching can be used to infer likely semantic overlaps in models. The approach is illustrated and evaluated using the inference of semantic equivalences as an example of inferring one type of semantic overlap.
When designing and developing complex systems, one common practice in
modeldriven engineering is for stakeholders to study the system from a variety of
different viewpoints. Such viewpoints are de ned by a number of factors, including
the context, level of abstraction and concerns of interest [
Several methods for identifying semantic overlaps are proposed in the related
literature. However, the associated cost, the strong assumptions made, and the
fact that many of the techniques are error prone, renders them impractical for
most scenarios. For example, uni cation algorithms are typically based on name
or predicate matching and can fail whenever homonyms or synonyms are
encountered. Rule- or logical inference based approaches rely on rule antecedents
to be matched completely. However, particularly when reasoning over
incomplete information and knowledge, antecedents may not always (fully) match.
This can lead to results and conclusions that are unintuitive to a human but
logically correct [
The remainder of the paper is organized as follows: section 2 brie y introduces the running example. Our conceptual approach is developed in section 3. A corresponding algorithm is introduced and evaluated in sections 3.3 and 3.4. Section 4 reviews similar approaches and compares them to our work. The paper closes with a short discussion and conclusions in section 5. 2
Running Example: Inferring Semantic Equivalence
To illustrate our conceptual approach, we apply it to the problem of inferring
semantic overlaps. A semantic overlap implies the existence of a semantic
relationship between two or more utterances of one or more languages. There
are numerous kinds and types of semantic relationships. Some well-known
relationships from object-oriented modeling are meronomous (part-whole, has a),
hyponymous (\is a", i.e., type-of), causal and instance-of relations [
In our running example, we assume that a number of UML models are given.
As illustrated in gure 1a, some of these models contain classes with
properties that have default values assigned. It is assumed that, across the di erent
models, some of these properties may be semantically equivalent, but
knowledge of their equivalence is not explicitly captured. The task is to nd those
pairs of properties that are likely to be semantically equivalent. Because models
describing engineering systems (software and physical systems) are often
heterogeneous in nature, and a great number of very di erent formalisms is typically
employed, we also assume the existence of a (bi-directional) mapping to some
common representational formalism for all models. For purposes of illustration
and mathematical elegance, and to build on previous work, directed, attributed
(and typed) multi-graphs are used as a common representational formalism [
Bayesian Reasoning in Models Represented by Graphs
Bayesian reasoning is often considered similar to human reasoning [
In Bayesian probability theory, beliefs are updated with new information by
applying Bayes' theorem [
P (A j B; C) =
P (A; B; C)
P (B; C) =
P (A) P (B; C j A)
P (B; C) : (1)
Determining the joint probabilities required to compute equation 1 is
nontrivial. In part, this is due to values of joint probability distributions rarely being
readily accessible. Also, when determining the joint probabilities by means of
factorization, the number of terms required is (in general) very large, even for a
small number of random variables [
Bayesian belief networks address both the problem of representing the joint
probability distribution over a set of random variables and performing inference
with these. Formally, a Bayesian belief network is a tuple (G; P), where P is a
joint probability distribution over a set of random variables V and G is a directed
acyclic graph whose nodes are random variables in V. Directed edges are used to
indicate in uence or causal relationships, which express local dependence among
random variables [
In addition to the DAG property, (G; P) must also satisfy the Markov
condition. The Markov condition states that each variable is (locally) conditionally
independent of its non-descendants given its parent variables. This condition,
along with information about the conditional dependence signi cantly reduces
the number of terms required to fully de ne the joint probability distribution P
represented by a Bayesian belief network. Therefore, to determine the joint
probability through simple enumeration, the product of the conditional probabilities
of all random variables Xi 2 V given values of their parents pa (Xi) (whenever
these conditional distributions exist) must be determined [
Y P (Xi = xi j pa(Xi)) : i (2)
This reduces the set of unknowns to only the conditional distributions of the random variables in V given values of their parents in the Bayesian network. These distributions are known as the parameters of a Bayesian network.
Figure 2 illustrates both the structure and the parameters of the Bayesian network used for the running example. Note the use of the short hand notation P (Xi = 0) = P (Xi) and P (Xi = 1) = P (:Xi) for binary random variables Xi. The network is assumed to be constructed by a human and encodes the assumption that knowing whether or not a particular pair of properties has similar (or dissimilar) names (N), compatible (or incompatible) types (T), and equal (or unequal) values (V) is in uenced by whether or not the pair of properties is semantically equivalent (or di erent) (E). In addition, it is assumed that whether or not names are similar in uences the probability of types being compatible which, in turn, in uences the probability of values being equal. The parameter values shown re ect the subjective beliefs of the same human. For example, at the time of specifying the network parameters, the human believes that the probability of any pair of properties being semantically equivalent is 0:1%. 3.2
Using the information provided in the Bayesian network illustrated in gure 2, as well as equations 1 and 2, a number of interesting diagnostic inferences can be performed. For instance, consider an experiment where the random outcome ! 2 is a pair of properties from the space of all pairs of properties . Say one can determine (by observing the object) that the pair of properties (!) has similar names, unequal values and compatible types. Furthermore, say that, due to a lack of available information and knowledge, we cannot be certain about the semantic equivalence of the two properties. Taking all of this new information into account, the probability of semantic equivalence for this particular pair of properties (which, without the observations is only the belief of any pair of properties being semantically equivalent: i.e., P (E)) can be updated. Mathematically, this equates to determining P (E j N; :V; T ). Note that P (E j N; :V; T ) is a meaningful statement about the probability of semantic equivalence of any pair of properties for which it can be determined with certainty that their names are similar, types compatible and values not equal.
By the earlier assumption that all models are represented by a graph, the de nition of the UML class properties considered in the running example must also be represented by a graph (at least at some level of abstraction { see gure 1b). Determining whether or not any two properties represented by a graph ful ll a certain condition (e.g., such as both properties having similar names) can be done computationally by means of graph pattern matching. Therefore, we argue that the process of collecting more information about, e.g., a particular pair of UML class properties can be mapped to querying a graph pattern.
To illustrate this result more formally, let ( ; F ; P ) represent the probability space over which all random variables Xi 2 V in the Bayesian network are dened. We de ne the sample space as the set of all pairs of property de nitions NG;prop in the graph G representing models: = NG;prop NG;prop. Furthermore, we de ne the -algebra as F = 2 (where 2 denotes the power set). By de nition, a random variable is a mapping Xi : ! E from the sample space to some measurable space E. Therefore, an e 2 E must be measurable for any ! 2 . By de nition of the measurable preimage Xi 1(e) 2 F , an e 2 E is measured whenever an event f 2 F is observed. To fully de ne the mapping, it is su cient to determine which pairs of properties are elements of the preimages of a random variable. Per our de nition of the random variable N, the preimage of N 1(0) is the set of all pairs of properties with similar names, i.e., all ! 2 which have similar names. We argue that determining the pairs of properties (i.e., the !is) for which this is the case, is computationally possible by encoding the necessary knowledge in an appropriate pattern.
Figure 3 illustrates the patterns used for the running example in a datalog-like syntax. Variables are unique by name and are indicated by a ? as pre x. Graph triples { i.e., two nodes (a subject and an object ) connected by a directed edge (a predicate) { are separated by brackets and are written in the form (subject predicate object). Note that notEqual(x, y) and equal(x, y) are functors that perform semantic equality checks on their arguments (for instance, 1 and 1.0 are considered semantically equal).
Note carefully that, per the de nition of the probability space, every property can and, in a state of perfect information and knowledge, must have a name, type and value. This means that all pairs of properties must be a part of one of the preimages Xi 1(e). In demonstrating our approach, only binary random variables were used. However, we recognize that multi-valued random variables may be more appropriate in other cases. Also note that, in a state of incomplete or inconsistent information, only a subset of the members of each of the preimages of the random variables can be determined using only the knowledge encoded in a pattern. Additional resources need to be committed to determine set membership for the other pairs of properties. Committing additional resources may require human intervention and the adding of additional information to the models. 3.3
By exploiting the structure of the Bayesian network, inference of probability
distributions can be performed quite e ciently, e.g., using the junction tree
algorithm [
for t 2 T do
InfContext observe(G, t, events(B), true) ; for observations 2 InfContext do
ObservedRVs observations.getRandomVariables() ; for rv 2 (B.getRandomVariables() n ObservedRVs) do
D D [ B.inferDistribution(rv, ObservedRVs) ; return D
for e 2 E do p pattern(e) ; TL ; ; if tripleMatchesPartOfPattern(p, t) then while (m G.nextMatch(t, p)) 6= ; do
Bs m:getBindingsToSharedVariables() ; Obs[Bs] Obs[Bs] [ (e, variableBindings(m)) ; if expand then for b 2 Bs do
TL TL [ G. ndTriplesAbout(b) ; for tl 2 TL do
Obs Obs [ observe(G, tl, E n e, false) ; return Obs properties that has no values assigned, but similar types and names, P (E j N; T ) constitutes a meaningful, and, using the Bayesian network, inferable probability of semantic equivalence, since it takes all of computationally determinable information into account { that is, all of information that can be extracted from the graph solely using graph pattern matching. To determine the probability of semantic equivalence for each individual pair of properties, a naive algorithm would have to iterate over all pairs of properties and, for each pair, a number of graph searches would need to be performed to determine matches to all patterns associated with the random variables. In addition, a potentially large number of inferences in the Bayesian network need to be performed.
Given the complexity of these operations, we propose an incremental algorithm (see algorithm 1) which considers only the changes made to an input graph. The changes are provided in the form of a set of graph triples. The incremental behavior of the algorithm is valid for as long as the structure of the Bayesian network does not change (note that a change in the parameters would only require a re-computation of the posterior beliefs). Verbally, algorithm 1 attempts to measure all random variables within the context of a single triple by matching the associated patterns, followed by performing inference in the Bayesian network. This procedure is called iteratively over the set of added triples: rst, the current triple is compared to all patterns. If the triple can be matched against any part of a pattern, a full pattern match in the graph is performed. For each match to the pattern, the value of the random variable and a context de ned by the bindings to the common, shared pattern variables (in the running example: ?p1 and ?p2) is stored in a map. To nd matches to the other patterns within one variable binding context, a list of triples directly related to the nodes and edges bound to the variables shared across patterns is compiled (i.e., triples with one of the bound elements as a subject, predicate or object). The pattern matching procedure is then repeated over this list. 3.4
In previous work, we have developed a model-based reasoning framework called
ConSystent [
For the purpose of demonstrating the technical feasibility of our approach, and to test our algorithm, we have extended this existing infrastructure with two additional components: rstly a simple Bayesian network library supporting inference with discrete random variables, and secondly a custom reasoning engine which implements Apache Jena's Reasoner interface. The expressiveness for de ning patterns using the Apache Jena datalog-like rule language is preserved by internally rewriting the patterns used for measuring random variables as rules with empty rule headers.
A preliminary evaluation of the algorithm and its implementation was performed using three sets of models. In each scenario, di erent quantities, kinds (UML, Simulink) and sizes of models were used. Samples of the inference results were drawn at random and inspected manually. Two important re ections have been made: rstly, common inferences (such as pairs of properties, for which the only observation is type inequality) can lead to a very large number of inferences, even for small models. This indicates that patterns need to not only be designed carefully, but heuristics may need to be employed to further de ne which inferences are considered valuable. Such heuristics can then form a basis for a classi er that decides which inferences to present to a modeler for further consideration. Secondly, due to the algorithm iterating over the set of all triples, some inferences are performed multiple times. However, this is not considered an issue { rather, it is a likely indicator of a non-optimality of the algorithm. 4
In the related literature, most approaches to reasoning over (model-based)
information and knowledge are based on logical inference. Inference of semantic
overlaps typically makes use of uni cation algorithms, which exploit representation
conventions. This includes predicate matching, of which the work by Finkelstein
et al. is an example [
Approaches to inferring semantic overlaps that are based on similarity
analysis can be considered complementary to our work. In [
In this paper, the use of Bayesian inference in combination with pattern matching is demonstrated and applied to the problem of inferring (likely) semantically equivalences. Identifying semantic overlaps { and generally reasoning over models { is an essential part of identifying inconsistencies and, hence, indispensable to veri cation and validation of models.
Logical inference can fail in scenarios where incomplete, underspeci ed and inconsistent views of models are consolidated. Bayesian inference, on the other hand, can always draw useful conclusions. Combining Bayesian inference and pattern matching as described in this paper can be viewed as an extension to the more commonly applied approach of using implications (or, generally, rules) to perform logical inference, and model- and graph-transformations: any outcome with probability 1 or 0 can be said to have been logically entailed by the evidence considered. For these reasons, applications such as spam ltering employ a similar combination of Bayesian inference and pattern matching to improve the e ectiveness of the reasoning task at hand.
To the best of knowledge of the authors, the combination of Bayesian inference and graph pattern matching has, to the date of writing this paper, not been used within the context of reasoning about properties of engineering models. However, we strongly believe that such an approach is promising, particularly for large-scale model-driven development applications. This is supported by the fact that Bayesian inference allows for rational assessment of important properties, e.g., related to the state of consistency and validity, of incomplete, underspeci ed and inconsistent models.
Acknowledgments. This work was supported by Boeing Research & Technology. The authors would like to thank Michael Christian (The Boeing Company), Dr. Vinod Cheriyan (MBSEC) and the anonymous reviewers for their feedback.