Transcript 4. Logical Models

Business Intelligence, Wintersemester 2012/2013
Modellierungstechniken II
Univ. Prof. Wilfried Gossmann
Research Group Knowledge Engineering
University of Vienna
[email protected]
Contents
The following tools are the most important structures in
Business process modelling:
4. Logical Models
5. Graphs
6. Functions
7. Probability and Statistics
Wilfried Grossmann, WS2012/13, University of Vienna – Models
2
4. Logical Models – Propositional Calculus
 Syntax
set of atomic propositions V  v1 , v2 ,  , vK 
 Operators for building formulas with atomic
propositions , , , , 
 Semantic defined by truth-values
A
B : V  t , f 
 This
semantic is extended to all formulas according to
the well known rules (truthtable)
Wilfried Grossmann, WS2012/13, University of Vienna – Models
3
4. Logical Models – Predicate Logic
Syntax 1
 Individual
constants (names)
 Individual variables (placeholders)
a1 , a2 ,, aK 
 Function symbols
v1 , v2 ,, vR 
 f1 , f 2 ,, f N 
 Predicates
 Quantors A , A ,  , A 
1
2
K
 Rules for defining
,  expressions in three steps: Terms,
atomic formulas, well formed formulas
Wilfried Grossmann, WS2012/13, University of Vienna – Models
4
4. Logical Models – Predicate Logic
Syntax 2
 Terms
are expressions defined either by individual
constants, individual variables or functions
 Examples
(Higher education example):
Constants: Exercise1, Student_Nr, …..
Variables: SomeExercise, AnyStudent
Functions:
MilestonePoints(AnyStudent),
Enrolement(MilestonePoint(AnyStudent),
Presentation(AnyStudent), Exercise(AnyStudent))
Wilfried Grossmann, WS2012/13, University of Vienna – Models
5
4. Logical Models – Predicate Logic
Syntax 3
 An
atomic formula is defined by a predicate symbol
followed by a number of terms in brackets for which
the predicate is applicable
 Examples
(Higher education example):
Belongs_to_course(Student_xx)
Has_achieved(Student_xx, MilestonePoints)
Wilfried Grossmann, WS2012/13, University of Vienna – Models
6
4. Logical Models – Predicate Logic
Syntax 4
 Well
formed formulas are defined by application of
propositional calculus and quantification of atomic
formulas
 Examples
(Higher education example):
There exist students, who have solved all exercises
All students have mastered the presentation points
Wilfried Grossmann, WS2012/13, University of Vienna – Models
7
4. Logical Models – Predicate Logic
Semantic 1
 Semantic in predicate logic is defined by an
interpretation obtained in the following way:
 Individual
variables and constants can take only values
in a certain domain D
 For each individual constant we define a fixed value in
D and call it the Interpretation I
 For each function symbol we assign an operation O
 Each unary predicate represents a property E , and
each n-ary predicate represents a relation B
Wilfried Grossmann, WS2012/13, University of Vienna – Models
8
4. Logical Models – Predicate Logic
Semantic 2
The unary predicates define a subset of the domain and the
n-ary predicates define a subsets of tuples defined by the
domain
 We denote the interpretation defined above by

M  ( D, I , O, E , B )

Now we assign truth values to atomic formulas containing
no individual variables , so called facts
Wilfried Grossmann, WS2012/13, University of Vienna – Models
9
4. Logical Models – Predicate Logic
Semantic 3
Starting from this facts we obtain truth values for all well
formed formulas if we assign each free individual variable
any possible individual constant from the domain and apply
the rules of propositional calculus
 If the interpretation results in the truth value "t " for all
possible assignments of the free variables we call the
interpretation a model

Wilfried Grossmann, WS2012/13, University of Vienna – Models
10
4. Logical Models – Predicate Logic
Semantic 4

The model is not a theoretical construct, but an
interpretation corresponding the theory
 A data modelling language realizes this modelling
techniques
 Main issues of the processing logic are questions about
decidability if we define a certain set of axioms and
constructors for well formed formulas
Wilfried Grossmann, WS2012/13, University of Vienna – Models
11
4. Logical Models – Description Logic
 Description logic combines a domain logic with
logic based semantics of predicate logic
 The domain logic describes the domain of interest
by concept descriptors built from
 Atomic
Concepts (unary predicates)
 Atomic roles (binary predicates)
Wilfried Grossmann, WS2012/13, University of Vienna – Models
12
4. Logical Models – Description Logic
 Concept
descriptions are done by a so called T-Box
(terminological box) corresponding to a data base
scheme
 Examples:
A happy man is a man that is married to a doctor and all
his children are doctors or professors
Happy _ man  Human  (female)  (married .doctor )
 (has _ child .(doctor  professor ))
Only humans can have human children
hasChild .Human  Human
Wilfried Grossmann, WS2012/13, University of Vienna – Models
13
4. Logical Models – Description Logic
 The
assertional part , so called A-Box corresponds to
the data in a data base and describes concrete
situations
 Example:
Bob is a happy man, Mary is one of his children, and Mary
is not a doctor
Happy _ man( Bob), has _ child .( Bob, Mary ), Doctor ( Mary )
From that we can infer that Mary is a professor
Wilfried Grossmann, WS2012/13, University of Vienna – Models
14
4. Logical Models – Ontologies
Most important application is the formulation of
ontologies , which may be useful for the task of
Business process description
 An ontology defines the concepts, relationships, and
other distinctions that are relevant for modelling a
domain
 The specification takes the form of the definitions of
a presentational vocabulary (classes, relations,…),
which provide meaning for the vocabulary and
formal constraints on its coherent use (T. Gruber)
Wilfried Grossmann, WS2012/13, University of Vienna – Models
15
4. Logical Models – Ontologies
Graphical representation of ontology tasks
Wilfried Grossmann, WS2012/13, University of Vienna – Models
16
4. Logical Models – Ontologies
 Basic constituents of an ontology
 Concepts
(terms)
 Types representing object types define by the concepts
 Instances
 Relations
 Inheritance
 Axioms
 The simplest case of an ontology is a taxonomy
 One can distinguish domain ontologies and upper
ontologies
Wilfried Grossmann, WS2012/13, University of Vienna – Models
17
4. Logical Models – Ontologies
Example of a simple domain ontology
Wilfried Grossmann, WS2012/13, University of Vienna – Models
18
4. Logical Models – Ontologies
Example of a complex “upper” ontology
Wilfried Grossmann, WS2012/13, University of Vienna – Models
19
4. Logical Models – Ontologies
 Advantage of ontologies
 Ontologies
organize information without taking into
account cumbersome details of data base modelling
 In principle ontologies support knowledge integration
and exchange of software
 Ontologies play an important role in building the
Semantic Web
Wilfried Grossmann, WS2012/13, University of Vienna – Models
20
4. Logical Models – Ontologies
 Most important representation language is OWL
A ontology formulated in OWL-DL correspond to the
T-Box in Description Logic
 OWL Constructors:

intersectionOf
unionOf
complementOf
one of
allValuesFrom
hasValue
Wilfried Grossmann, WS2012/13, University of Vienna – Models
minCardinality
maxCardinality
inverseOf
21
4. Logical Models – Ontologies
 OWL Axioms
Axiom
subClassOf
equivalentClass
subPropertyOf
equivalentProperty
disjointWith
sameAs
differentFrom
TransitiveProperty
FunctionalProperty
InverseFunctionalProperty
SymmetricProperty
Wilfried Grossmann, WS2012/13, University of Vienna – Models
DLSyntax
C1  C2
C1  C2
P1  P2
P1  P2
C1  C2
x1  x2 
x1  x2 
P  P
22
4. Logical Models – Ontologies
 This Ontology is decideable
 Tools for ontology formulation: Protégé
 The Knowledge Based Temporal Abstraction
Method (KBTA) can be formulated as an ontology
Wilfried Grossmann, WS2012/13, University of Vienna – Models
23
5. Graphs
Graphs are a powerful tool in Business process
modelling applied for many different purposes, often
in combination with other modelling techniques
Syntax for Graphs 1
 Vertices
(nodes)
 Edges (arcs)
G  (V , E )
Wilfried Grossmann, WS2012/13, University of Vienna – Models
24
5. Graphs
Syntax for Graphs 2
 Nodes
and arcs may be specified by attributes
v  V  (VA1 , VA2 ,  , VAK )
e  E  ( EA1 , EA2 ,  , EAL )
 Example:
 Different
In-degree and Out-degree of vertices
types of graphs:
 Directed
graph, Trees, Forests, Complete Graph,
layered network, connected graph, bipartite graphs
Wilfried Grossmann, WS2012/13, University of Vienna – Models
25
5. Graphs
Syntax for Graphs 3

Special sub-graphs:
 Path, spanning tree, circle, ….
Wilfried Grossmann, WS2012/13, University of Vienna – Models
26
5. Graphs
Semantic for graphs
 Semantic for graphs is defined from mathematical
standard interpretations
 Interpretation
of attributes of vertices or edges as
capacities
 Interpretation of attributes for edges as distance, cost
 Dynamic interpretation
 Vertices
represent activities, edges represent priority
structure (partial ordering), possible transition
 Edges represent activities, vertices represent states
before/after an activity
Wilfried Grossmann, WS2012/13, University of Vienna – Models
27
5. Graphs
Processing logic for graphs:
 Graph
theoretical algorithms offer solutions for a
number of questions which can be formulated as
optimization problems in the standard interpretation
 Examples:
Shortest path, Minimum spanning tree, Maximum flow,
Min-Cost Flow, Traveling salesman Problem, ….
Wilfried Grossmann, WS2012/13, University of Vienna – Models
28
5. Graphs – Specific Models
Combination of the generic model techniques for
graphs with a specific domain logic allows more
detailed specification of models
Processes as Transition systems
 Vertices
represent states
of a system
 Edges represent possible
transitions
 A path in the graph is an
instance of the process
Wilfried Grossmann, WS2012/13, University of Vienna – Models
29
5. Graphs – Specific Models
Business Processes models with BPMN
 Vertices
are typed according to different business
workflow concepts
 Activities
 Splits:
AND, OR, XOR
 Joins: AND, OR, XOR
 Start, end
Edges represent priorities
 Rules for building the graph
Compare with knowledge representation by ontologies

Wilfried Grossmann, WS2012/13, University of Vienna – Models
30
5. Graphs – Specific Models
Petri-Nets as state machines 1
 Two
disjoint types of vertices:
Places P and Transitions T
 Edges are defined as directed edges between places
and transition or transitions and edges

E  ( P  T )  (T  P)
A function m : P  N marking the places and
defining an initial state
Wilfried Grossmann, WS2012/13, University of Vienna – Models
31
5. Graphs – Specific Models
Petri-Nets as state machines 2
 If
all places which are predecessors of a transition are
marked and all successors places of the transition are
free then the network can fire (activates the transition)
and switches the network new state by removing the
marking from all predecessors places and puts it to
the places which are the successors of the transition
 This is the simplest case; more elaborated rules are
possible for handling conflicts
 Firing generates a specific process path instance
Wilfried Grossmann, WS2012/13, University of Vienna – Models
32
5. Graphs – Specific Models
Petri-Nets as state machines 3
Example:
Gasoline station
(kroening-online.de)

Wilfried Grossmann, WS2012/13, University of Vienna – Models
33
6. Functions
Functions as a generic model for defining a specific
relation as mapping from a domain (input) into some
range of values (output) are a main tool in all kinds of
business process analysis
The basic information logic defined by function
algebra is usually enlarged by special classes of
functions depending on the on specification of the
domain an the range
Wilfried Grossmann, WS2012/13, University of Vienna – Models
34
6. Functions
In case of discrete domains main application of
functions is summarizing characteristics of instances
 Counting
: Mapping the occurrence of instances into
the natural numbers
 Advantage:
Additivity, i.e. we can do it iteratively
 Aggregation:
defining new values of an attribute by
using a hierarchical taxonomy for the value domain of
the terms
 Basic
operation in connection with OLAP (roll up)
 Note
that disaggregation (drill down) needs usually
additional considerations
Wilfried Grossmann, WS2012/13, University of Vienna – Models
35
6. Functions
In case of continuous domains the following ideas are
used in many applications
 Modelling of unknown relationships by using
function classes
 Define
a set of basic functions, e.g. power functions,
trigonometric functions , spline functions, …
 Define a model for the relationship by a linear
combination of these basic functions (regression
model)
f ( x)  a0  a1 f1 ( x)  a2 f 2 ( x)    aK f K ( x)
Wilfried Grossmann, WS2012/13, University of Vienna – Models
36
6. Functions
 This
model can be applied also in case of modelling the
output in dependence of many input variables
(multiple regression)
 In

that case we use many times only linear functions

f ( x )  a0  a1 x1  a2 x2   aK xK
Sometimes also quadratic functions
f ( x1 , x2 )  a0  a1 x1  a2 x2  a3 x12  a4 x22  a5 x1 x2
Wilfried Grossmann, WS2012/13, University of Vienna – Models
37
6. Functions
 Projections
 Sometimes
it is rather difficult to understand the
behaviour of a business process depending on many
different input variables
 Hence we look for a more compressed description in a
small number of dimensions
 These dimensions are usually defined as linear
combination of the observed dimensions
y1  a11 x1  a12 x2    a1K x1k
y2  a21 x1  a22 x2    a2 K x1k
Wilfried Grossmann, WS2012/13, University of Vienna – Models
38
6. Functions
 Projections
 Many
times we use a normalisation of the coefficients
a112  a 122    a 12K  1
2
a21
 a 222    a 22 K  1
A
well known simple case is a score
 A main analysis task is defining methods which result
in transformations keeping as much information as
possible in the data
Wilfried Grossmann, WS2012/13, University of Vienna – Models
39
6. Functions
 Transformations
 In
order to obtain values with some desired behaviour,
for example a linear relationship, it is sometimes useful
to transform the values of a function
 Power
transformation
y  xp
 Logarithmic
transformation: symmetrizes the values of
a ratio of two positive values
 0 if x  1
y  log( x)  
 0 f x  1
Wilfried Grossmann, WS2012/13, University of Vienna – Models
40
7. Probability and Statistics – Probability models
Models for variability of process instances 1
 Frequently the values of the attributes can be
described / predicted only by a probabilistic law
 Examples:
Income of a person, preferences with
respect to certain brands, measurement of some
physical parameter, duration of an activity,….
 For describing the observations we use a probability
distribution
Wilfried Grossmann, WS2012/13, University of Vienna – Models
41
7. Probability and Statistics – Probability models
Models for variability of process instances 2
 We use the generic symbol p (x ) for characterization
of this probability
 Interpretation:
p (x) is the likelihood that value x occurs
 Only
in case of discrete value domains we can talk
about probability

If we have only two possible values (0, 1) for the
attribute (dichotomous attributes) we use frequently
instead of probability odds or log-odds
p (1)
odds 
, logodds  ln(odds )
1  p (1)
Wilfried Grossmann, WS2012/13, University of Vienna – Models
42
7. Probability and Statistics – Probability models
Markov chains as model for process description 1
A
Markov chain can be interpreted as description of a
business process as state transition system where the
main attribute for the edges are the probabilities that
switches between states occur
S1
S2
S3
S1 S 2 S3
0.2 0 0.8
0.3 0.4 0.3
0 0.6 0.4
Wilfried Grossmann, WS2012/13, University of Vienna – Models
43
7. Probability and Statistics – Probability models
Markov chains as model for process description 2
 The model allows answering a number of interesting
structural analysis questions:
 What
states can be reached from an initial state?
 Is it possible to return to some state?
 Is there a stable distribution for being in some states?
 Is such a stable state achieved in the long run?
Important application is the behaviour of internet users
Wilfried Grossmann, WS2012/13, University of Vienna – Models
44
7. Probability and Statistics – Statistical Models
Statistics as model for variability of process instances
 In
Business process classification and business process
segmentation we usually start with a model of the
following form

y  f (x)  
y  class assignment

x  explanatory variables
  unexplained variability of observations
Wilfried Grossmann, WS2012/13, University of Vienna – Models
45
7. Probability and Statistics – Statistical Models
7. Probability and Statistics – Statistical Models
Statistics as a tool for business process estimation 1
 Estimation
of unknown parameters of a distribution
 Many
times a probabilistic model for the behaviour of
an attribute is determined only up to a number of
parameters (c.f. function classes as a model for
relationships)
 We can use statistics for finding the “best” values for
the parameters according to available observation data
Wilfried Grossmann, WS2012/13, University of Vienna – Models
46
7. Probability and Statistics – Statistical Models
Statistics as a tool for business process estimation 2
 Estimation
of missing observations
 In
case of missing values in the observations we can
improve data quality by using statistical techniques for
finding plausible values for the missing observations
 Estimation
of duration of processes
 We
want to find the distribution of the duration of
processes in case of partial observation (censored data)
 Example Duration of contracts: Observations of ended
contracts and observations of existing contracts
 Find the distribution of the lifetime of contracts
Wilfried Grossmann, WS2012/13, University of Vienna – Models
47