Graph-Based Knowledge Representation in Modelling: A Comprehensive Overview
M
o
d
e
l
l
i
n
g
k
n
o
w
l
e
d
g
e
P
a
r
t
2
Antoine Zimmermann
1
C
o
n
t
e
n
t
•
Introduction
•
Classification
•
Graph-based knowledge representation
(almost)
•
Object oriented knowledge representation
•
Description logic
•
Rule-based knowledge representation
2
We have seen a formalism that can express that a
particular recipe (e.g., my mom’s omelette) has particular
ingredients (e.g., 4 eggs). How do we represent the fact
that recipes, in general, have ingredients?
3
G
r
a
p
h
r
e
p
r
e
s
e
n
t
a
t
i
o
n
:
g
e
n
e
r
a
l
i
s
i
n
g
myMumOmelette
hasIngredient
fourEggs
Recipe
is-a
is-a
Ingredient
hasIngredient
?
There are several interpretations of the relationship
1)
The class
Recipe
itself relates to the class
Ingredient
by
relation
hasIngredient
hasIngredient(
Recipe
,
Ingredient
)
2)
All recipes have some ingredients
∀
x.
∃
y
.Recipe(
x
)
⇒
Ingredient(
y
)
∧
hasIngredient(
x
,
y
)
or
∀
x.
∃
y
.is-a(
x,
Recipe)
⇒
is-a(
y
,Ingredient)
∧
hasIngredient(
x
,
y
)
3)
Recipes may have ingredients
4
G
r
a
p
h
r
e
p
r
e
s
e
n
t
a
t
i
o
n
:
g
e
n
e
r
a
l
i
s
i
n
g
Recipe
Ingredient
hasIngredient
There are several interpretations of the relationship
4)
The relation
hasIngredient
only relates recipes to ingredients
∀
x.
∀
y
.hasIngredient(
x
,
y
)
⇒
Recipe(
x
)
∧
Ingredient(
y
)
or
∀
x.
∀
y
.hasIngredient(
x
,
y
)
⇒
is-a(
x,
Recipe)
∧
is-a(
y
,Ingredient)
5
G
r
a
p
h
r
e
p
r
e
s
e
n
t
a
t
i
o
n
:
g
e
n
e
r
a
l
i
s
i
n
g
Recipe
Ingredient
hasIngredient
A graph-based representation that is very expressive
My mum’s Omelette is a recipe, four eggs are an ingredient and
My mum’s Omelette has four eggs
.
hasIngredient(
myMumOmelette
,
fourEggs
)
∧
Recipe(
myMumOmelette
)
∧
Ingredient(
fourEggs
)
6
C
o
n
c
e
p
t
u
a
l
g
r
a
p
h
s
(
J
o
h
n
F
.
S
o
w
a
,
1
9
7
9
)
Recipe:
myMumOmelette
Ingredient:
fourEggs
hasIngredient
There is a recipe that has some ingredient
.
∃
x
∃
y
.hasIngredient(
x
,
y
)
∧
Recipe(
x
)
∧
Ingredient(
y
)
All recipes have some ingredient.
∀
x
∃
y
.Recipe(
x
)
⇒
hasIngredient(
x
,
y
)
∧
Ingredient(
y
)
7
C
o
n
c
e
p
t
u
a
l
g
r
a
p
h
s
(
J
o
h
n
F
.
S
o
w
a
,
1
9
7
9
)
Recipe:
Ingredient:
hasIngredient
Recipe:
∀
Ingredient:
hasIngredient
A person is between a rock and a hard place.*
∃
w
∃
x
∃
y
∃
z
.Person(
w
)
∧
Rock(
x
)
∧
Place(
y
)
∧
Hard(
z
)
∧
Betw(
w
,
x
,
y
)
∧
Attr(
y
,
z
)
* From http://www.jfsowa.com/cg/cgexampw.htm
8
C
o
n
c
e
p
t
u
a
l
g
r
a
p
h
s
(
J
o
h
n
F
.
S
o
w
a
,
1
9
7
9
)
Person:
Rock:
Betw
Place:
Hard:
Attr
1
2
Tom believes that Mary wants to marry a sailor
9
C
o
n
c
e
p
t
u
a
l
g
r
a
p
h
s
(
J
o
h
n
F
.
S
o
w
a
,
1
9
7
9
)
Person:
Tom
Believe:
Expr
Person:
Mary
Thme
Proposition:
Want:
Expr
Thme
T
Marry:
Agnt
Thme
Situation:
Sailor:
•
In graph-based representations, we focus on the
relationships between entities.
•
In object-oriented representations, we focus on entities
individually and their characteristics.
These are called
frames
each line is a
slot
10
O
b
j
e
c
t
-
o
r
i
e
n
t
e
d
k
n
o
w
l
e
d
g
e
r
e
p
r
e
s
e
n
t
a
t
i
o
n
m
y
M
u
m
O
m
e
l
e
t
t
e
:
prepTime
: 5 min
cookTime
: 10 min
difficulty
: easy
i
s
A
:
R
e
c
i
p
e
i
n
g
r
e
d
i
e
n
t
:
4
e
g
g
s
i
n
g
r
e
d
i
e
n
t
:
b
u
t
t
e
r
R
e
c
i
p
e
:
?
Exercise:
•
What do we need to describe a recipe in general?
•
What do we need to describe a class in general?
11
O
b
j
e
c
t
-
o
r
i
e
n
t
e
d
k
n
o
w
l
e
d
g
e
r
e
p
r
e
s
e
n
t
a
t
i
o
n
What do we need to describe a class in general?
•
Properties (attributes, slots)
•
Types (primitive or other classes)
•
Cardinalities (min and max)
12
O
b
j
e
c
t
-
o
r
i
e
n
t
e
d
k
n
o
w
l
e
d
g
e
r
e
p
r
e
s
e
n
t
a
t
i
o
n
R
e
c
i
p
e
:
prepTime
: (duration) 1:1
cookTime
: (duration) 1:1
difficulty
:
("easy","medium","hard")i
n
g
r
e
d
i
e
n
t
:
(
I
n
g
r
e
d
i
e
n
t
)
1
:
+
Instance frames are FOL constants. Each slot is a binary
predicate except
isA
.
Recipe(
mMO
)
∧
prepTime(
mMO
,
5min
)
∧
…
Class frames is an implication with a universal quantification:
∀
x.
Recipe(
x
)
⇒ ∃
y.
prepTime(
x
,
y
)
∧
(
∀
z
.
prepTime(
x
,
z
)
⇒
duration(
z
)
∧
y
=
z
))
∧
…
13
H
o
w
t
o
u
n
d
e
r
s
t
a
n
d
f
r
a
m
e
s
Class frames may have a special slot:
subclassof
or
kind-of
∀
x.
VegetarianRecipe(
x
)
⇒ ∃
y.
ingredient(
x
,
y
)
∧
(
∀
z
.
ingredient(
x
,
z
)
⇒
VegOrDairy(
z
)
)
∧
Recipe(
x
)
14
I
n
h
e
r
i
t
a
n
c
e
V
e
g
e
t
a
r
i
a
n
R
e
c
i
p
e
:
k
i
n
d
-
o
f
:
R
e
c
i
p
e
i
n
g
r
e
d
i
e
n
t
:
(
V
e
g
O
r
D
a
i
r
y
)
1
:
+
This kind of models can be represented with UML class
diagrams.
Exercise:
•
Based on what we did last time on the omelette recipe, build an
object-oriented knowledge model for recipes in general.
•
There are many online traveller information systems that can
provide itineraries from one place to another in various areas using
various transportation modes. They all use different information
models but share the same kind of knowledge. Model this
knowledge in an OO representation.
15
O
b
j
e
c
t
-
o
r
i
e
n
t
e
d
k
n
o
w
l
e
d
g
e
r
e
p
r
e
s
e
n
t
a
t
i
o
n
UML class diagrams can be partially translated in to a
frame-based knowledge model:
•
Classes
become
frames
•
Attributes
become
slots
•
R
e
l
a
t
i
o
n
s
M
A
Y
b
e
c
o
m
e
s
l
o
t
s
•
Inheritance
becomes a
kind-of slot
•
Operations
(i.e.,
methods
) are normally not modelled in
frames
•
Relations
can be translated in different ways
16
T
r
a
n
s
l
a
t
e
U
M
L
t
o
a
n
O
O
k
n
o
w
l
e
d
g
e
m
o
d
e
l
•
What if I want to describe a recipe for which I do not
know the cooking time?
•
What if I want to say something about a recipe that does
not match a property of the class?
O
p
e
n
W
o
r
l
d
A
s
s
u
m
p
t
i
o
n
v
s
.
C
l
o
s
e
d
W
o
r
l
d
A
s
s
u
m
p
t
i
o
n
17
U
n
k
n
o
w
n
v
a
l
u
e
s
•
Default values
•
Define values in function of others
•
Incompatible values
•
Incompatible types
•
Reflexive slots
•
Transitive slots
•
Symmetric slots
•
…
18
E
v
e
n
m
o
r
e
e
x
p
r
e
s
s
i
v
e
n
e
s
s
Expressiveness comes at the cost of complexity:
•
Complexity of design
•
Complexity of understanding
•
Complexity of computation
Many knowledge models can be translated in First Order Logic, but
FOL is way too expressive for many
practical
models.
Principle of least power:
A
l
w
a
y
s
c
h
o
o
s
e
t
h
e
l
e
a
s
t
e
x
p
r
e
s
s
i
v
e
l
a
n
g
u
a
g
e
t
h
a
t
s
u
i
t
s
y
o
u
r
p
u
r
p
o
s
e
s
e.g. if a product classification is ufficient for an e-commerce web site,
why use FOL?
19
E
x
p
r
e
s
s
i
v
e
n
e
s
s
v
s
.
C
o
m
p
l
e
x
i
t
y
t
r
a
d
e
o
f
f
This content delves into graph-based knowledge representation in modelling, detailing concepts such as recipe-ingredient relationships, formalisms for generalizing graph representation, and conceptual graphs by John F. Sowa. It explores how different interpretations describe the association between recipes and ingredients, showcasing the expressiveness and versatility of graph-based representations in capturing complex knowledge structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Modelling knowledge Part 2 Antoine Zimmermann 1
Content Introduction Classification Graph-based knowledge representation Object oriented knowledge representation Description logic Rule-based knowledge representation (almost) 2 Institut Mines-T l com cole des Mines de Saint- tienne
Graph representation: generalising We have seen a formalism that can express that a particular recipe (e.g., my mom s omelette) has particular ingredients (e.g., 4 eggs). How do we represent the fact that recipes, in general, have ingredients? Recipe Ingredient ? myMumOmelette fourEggs 3 Institut Mines-T l com cole des Mines de Saint- tienne
Graph representation: generalising There are several interpretations of the relationship Recipe Ingredient 1) The class Recipe itself relates to the class Ingredient by relation hasIngredient hasIngredient(Recipe,Ingredient) 2) All recipes have some ingredients x. y.Recipe(x) Ingredient(y) hasIngredient(x,y)or x. y.is-a(x,Recipe) is-a(y,Ingredient) hasIngredient(x,y) 3) Recipes may have ingredients 4 Institut Mines-T l com cole des Mines de Saint- tienne
Graph representation: generalising There are several interpretations of the relationship Recipe Ingredient 4) The relation hasIngredient only relates recipes to ingredients x. y.hasIngredient(x,y) Recipe(x) Ingredient(y) or x. y.hasIngredient(x,y) is-a(x,Recipe) is-a(y,Ingredient) 5 Institut Mines-T l com cole des Mines de Saint- tienne
Conceptual graphs (John F. Sowa, 1979) A graph-based representation that is very expressive Recipe: Ingredient: fourEggs hasIngredient myMumOmelette My mum s Omelette is a recipe, four eggs are an ingredient and My mum s Omelette has four eggs. hasIngredient(myMumOmelette,fourEggs) Recipe(myMumOmelette) Ingredient(fourEggs) 6 Institut Mines-T l com cole des Mines de Saint- tienne
Conceptual graphs (John F. Sowa, 1979) Recipe: Ingredient: hasIngredient There is a recipe that has some ingredient. x y.hasIngredient(x,y) Recipe(x) Ingredient(y) Recipe: Ingredient: hasIngredient All recipes have some ingredient. x y.Recipe(x) hasIngredient(x,y) Ingredient(y) 7 Institut Mines-T l com cole des Mines de Saint- tienne
Conceptual graphs (John F. Sowa, 1979) Rock: Person: Betw Hard: Attr Place: A person is between a rock and a hard place.* w x y z.Person(w) Rock(x) Place(y) Hard(z) Betw(w,x,y) Attr(y,z) * From http://www.jfsowa.com/cg/cgexampw.htm 8 Institut Mines-T l com cole des Mines de Saint- tienne
Conceptual graphs (John F. Sowa, 1979) Person: Tom Believe: Expr Thme Person: Mary Expr Want: Thme T Agnt Marry: Thme Sailor: Tom believes that Mary wants to marry a sailor 9 Institut Mines-T l com cole des Mines de Saint- tienne
Object-oriented knowledge representation In graph-based representations, we focus on the relationships between entities. In object-oriented representations, we focus on entities individually and their characteristics. These are called frames each line is a slot 10 Institut Mines-T l com cole des Mines de Saint- tienne
Object-oriented knowledge representation Exercise: What do we need to describe a recipe in general? What do we need to describe a class in general? 11 Institut Mines-T l com cole des Mines de Saint- tienne
Object-oriented knowledge representation What do we need to describe a class in general? Properties (attributes, slots) Types (primitive or other classes) Cardinalities (min and max) 12 Institut Mines-T l com cole des Mines de Saint- tienne
How to understand frames Instance frames are FOL constants. Each slot is a binary predicate except isA. Recipe(mMO) prepTime(mMO,5min) Class frames is an implication with a universal quantification: x.Recipe(x) y.prepTime(x,y) ( z. prepTime(x,z) duration(z) y=z)) 13 Institut Mines-T l com cole des Mines de Saint- tienne
Inheritance Class frames may have a special slot: subclassof or kind-of x.VegetarianRecipe(x) y.ingredient(x,y) ( z.ingredient(x,z) VegOrDairy(z)) Recipe(x) 14 Institut Mines-T l com cole des Mines de Saint- tienne
Object-oriented knowledge representation This kind of models can be represented with UML class diagrams. Exercise: Based on what we did last time on the omelette recipe, build an object-oriented knowledge model for recipes in general. There are many online traveller information systems that can provide itineraries from one place to another in various areas using various transportation modes. They all use different information models but share the same kind of knowledge. Model this knowledge in an OO representation. 15 Institut Mines-T l com cole des Mines de Saint- tienne
Translate UML to an OO knowledge model UML class diagrams can be partially translated in to a frame-based knowledge model: Classes become frames Attributes become slots Relations MAY become slots Inheritance becomes a kind-of slot Operations (i.e., methods) are normally not modelled in frames Relations can be translated in different ways 16 Institut Mines-T l com cole des Mines de Saint- tienne
Unknown values What if I want to describe a recipe for which I do not know the cooking time? What if I want to say something about a recipe that does not match a property of the class? Open World Assumption vs. Closed World Assumption 17 Institut Mines-T l com cole des Mines de Saint- tienne
Even more expressiveness Default values Define values in function of others Incompatible values Incompatible types Reflexive slots Transitive slots Symmetric slots 18 Institut Mines-T l com cole des Mines de Saint- tienne
Expressiveness vs. Complexity tradeoff Expressiveness comes at the cost of complexity: Complexity of design Complexity of understanding Complexity of computation Many knowledge models can be translated in First Order Logic, but FOL is way too expressive for many practical models. Principle of least power: Always choose the least expressive language that suits your purposes e.g. if a product classification is ufficient for an e-commerce web site, why use FOL? 19 Institut Mines-T l com cole des Mines de Saint- tienne
