COMP111: Artificial Intelligence – Section 7. Knowledge Representation and Reasoning (KR&R)
COMP111: Artificial Intelligence
Section 7. Knowledge Representation and Reasoning (KR&R)
Frank Wolter
Content
I Basic idea behind KR and R.
I Rule-Based KR and R.
I Propositional Logic for KR and R.
Knowledge Representation and Reasoning
I An intelligent agent needs to be able to perform several tasks:
I Perception: what is my state?
I Deliberation: what action should I take?
I Action: how do I execute the action?
I State recognition implies some form of representation of the
knowledge about the state.
I Figuring out the right action requires some form of reasoning.
Knowledge Bases and Reasoning Engine
I Basic idea:
I Tell the agent what it needs to know.
I The agent uses reasoning to deduce relevant consequences.
I This is the declarative approach to building agents. Agents
have two parts:
I A knowledge base which contains facts and general knowledge
about a domain in some formal language.
I A reasoning engine that produces relevant consequences of the
knowledge base.
Example 1
Consider the following knowledge base:
I If I have an AI lecture today, then it is Tuesday or Friday.
I It is not Tuesday.
I I have an AI lecture today or I have no class today.
I If I have no class today, then I am sad.
I I am not sad.
Can you infer what day it is?
Example 2: Medical Ontologies
Consider the following medical knowledge base:
I Pericardium is a tissue contained in the heart
I Pericarditis is an inflammation located in the pericardium
I Inflammation is a disease that acts on tissue
I A disease located in something contained in the heart is a
heartdisease
Can you infer that pericarditis is a heartdisease?
More on Example 2
Example 2 contains propositions in SNOMED CT, a medical and
healthcare knowledge base (called ontology) containing more than
300 000 propositions that define the meaning of terms used in
medicine and healthcare in such a way that it can be processed by
machines.
SNOMED CT is used as a knowledge base by the NHS and the
healthcare systems of more than 20 countries.
SNOMED CT is used to process electronic medical records
containing test results, medications, and treatments (your GP uses
SNOMED CT terms to fill in your electronic medical record).
Example 3: Mathematical Knowledge
Consider a mathematical problem such as:
for which x does ax2 + bx + c = 0 hold?
There are infinitely many equations. It is not possible to store the
answers to all these problems in a database or knowledge base.
Instead:
I Store axioms of arithmetic such as
x + y = y + x , x(y + z) = xy + xz
in a knowledge base.
I Use reasoning algorithms to solve particular problems using
the axioms in the knowledge base.
Example 4: Knowledge Graph
When you search for Liverpool you receive structured information
about Liverpool FC. In particular:
I Liverpool Football Club is a professional association football
club based in Liverpool, Merseyside, England. They compete
in the Premier League, the top tier of English football.
I Nickname: The Reds
I Manager: Jürgen Klopp
I Arena/Stadium: Anfield
I Customer service: 0151 264 2500
I Parent organization: Fenway Sports Group
This information is stored in the Google knowledge graph (which is
a knowledge base).
Example 4: Reasoning using Knowledge Graph
Many facts are not stored in the knowledge graph. Possibly the
following:
I Liverpool FC competes in the FA Cup;
I Jürgen Klopp is employed by Liverpool FC.
It is, however, not unlikely that the knowledge graph contains:
I If a club competes in the Premier League, then it competes in
the FA Cup;
I A manager of a football club is employed by the football club.
Thus, the facts above can be deduced from the knowledge graph
using reasoning.
Languages for KR&R
I To store knowledge in a knowledge base and do reasoning,
one has to represent the knowledge in a formal language that
can be processed by machines.
I Many KR&R languages were first developed in logic, a
subdiscipline of philosophy and mathematics, and now also of
computer science.
I We consider rule-based languages and propositional logic as
KR&R languages. Both are important in computer science in
general.
Rule-Based Languages
Syntax
I An individual name denotes an individual object. They are
often also called constant symbols. Examples:
I LiverpoolFC;
I JurgenKlopp;
I England;
I we also often use lower case letters such as a, b, c , a1, a2 as
individual names.
I An individual variable is a placeholder for an individual name.
They are denoted by lower case letters x , y , z , x1, and so on.
I A class name denotes a set of individual objects. They are
often also called unary predicate symbols. Examples:
I CompetesInPremierLeague;
I FootballClub;.
I Human being;
I we also often use upper case letters such as A, B, C , A1, A2 as
class names.
Syntax: atomic assertion
An atomic assertion takes the form A(b) and states that b is in the
class A.
Example:
I The assertion
CompetesInPremierLeague(LiverpoolFC)
states that Liverpool FC competes in the Premier League.
I The assertion
Manager(Klopp)
states that Klopp is a manager.
Syntax: unary rule
A unary rule takes the form
A1(x) ∧ · · · ∧ An(x)→ A(x)
where A1, . . . ,An and A are class names and x is an individual
variable.
The rule states that everything in all classes A1,A2, . . . ,An is in
the class A.
Example:
I The rule
CompetesInPremierLeague(x)→ CompetesInFACup(x)
states that everything that competes in the Premier League
competes in the FA Cup.
I The rule
Disease(x) ∧ LocatedInHeart(x)→ Heartdisease(x)
states that every disease located in the heart is a heartdisease.
Unary Rule-Based Systems
A unary rule-based knowledge base K is a collection Ka of atomic
assertions and Kr of unary rules.
Example: Let Ka contain the following atomic assertions:
I CompetesInPremierLeague(LiverpoolFC);
I CompetesInPremierLeague(Everton) and so on for all clubs
competing in the Premier League.
Let Kr contain the following rules:
I CompetesInPremierLeague(x)→ CompetesInFACup(x);
I CompetesInPremierLeague(x)→ FootballClub(x);
I CompetesInPremierLeague(x)→ BasedInEngland(x).
The following atomic assertions follow from K :
I CompetesInFACup(LiverpoolFC)
I FootballClub(Everton), and so on.
Thus, from 20 facts and 3 rules, we can deduce 60 additional facts.
Reasoning in Rule-Based Systems
Let K be a knowledge base and A(b) an atomic assertion. Then
A(b) follows from K , in symbols,
K |= A(b)
if whenever K is true, then A(b) is true. We write K 6|= A(b) if
this is not the case.
In the example K from the previous slide, we have
K |= CompetesInFACup(LiverpoolFC)
In fact, we have already for
K ′a = {CompetesInPremierLeague(LiverpoolFC)}
and
K ′r = {CompetesInPremierLeague(x)→ CompetesInFACup(x)}
that for K ′ containing K ′a and K
′
r ,
K ′ |= CompetesInFACup(LiverpoolFC)
More examples for K |= A(b)
Let
I Ka = {A1(a)};
I Kr = {A1(x)→ A2(x),A2(x)→ A3(x)}.
Let K contain Ka and Kr . Then
I K |= A1(a);
I K |= A2(a);
I K |= A3(a).
More examples for K |= A(b)
Let
I Ka = {A1(a)};
I Kr = {A1(x)→ A2(x),A2(x) ∧ B(x)→ A3(x)}.
Let K contain Ka and Kr . Then
I K |= A1(a);
I K |= A2(a);
I K 6|= A3(a);
I K 6|= B(a).
How do we check that K |= A(b)?
The following algorithm takes as input the knowledge base K
containing Ka and Kr and computes all assertions E (a) with E a
class name and a an individual name such that K |= E (a). This set
is stored in
DerivedAssertions
It only remains to check whether A(b) is in DerivedAssertions.
The algorithm computes the set DerivedAssertions by starting with
Ka and then applying the rules in Kr exhaustively to already
derived atomic assertions.
Computing DerivedAssertions
1: Input: a knowledge base K containing
2: assertions Ka and rules Kr
3:
4: DerivedAssertions := Ka
5: repeat
6: if there exist E (a) not in DerivedAssertions
7: and A1(x) ∧ · · · ∧ An(x)→ E (x) in Kr
8: and A1(a), · · · ,An(a) in DerivedAssertions
9: then add E (a) to DerivedAssertions
10: NewAssertion := true
11: else NewAssertion := false
12: endif
13: until NewAssertion = false
14: return DerivedAssertions
Rule application
In the algorithm above we say that:
E (a) is added to DerivedAssertions by applying the rule
A1(x) ∧ · · · ∧ An(x)→ E (x)
to the atomic assertions
A1(a), . . . ,An(a) in DerivedAssertions
Example
Let
I Ka = {A1(a)};
I Kr = {A1(x)→ A2(x),A2(x)→ A3(x)}.
I First DerivedAssertions contains Ka only.
I Then an application of A1(x)→ A2(x) to A1(a) adds A2(a)
to DerivedAssertions.
I Then an application of A2(x)→ A3(x) to A2(a) adds A3(a)
to DerivedAssertions.
I Now no rule is applicable. Thus
DerivedAssertions = {A1(a),A2(a),A3(a)}
is returned.
Example
Let Kr contain:
I A1(x)→ A2(x)
I A2(x) ∧ B(x)→ A3(x)
Let Ka contain:
I A1(a)
DerivedAssertions
I A1(a)
I A2(a)
Now no rule is applicable. Thus
DerivedAssertions = {A1(a),A2(a)}
is returned.
Example
Let Kr contain:
I A1(x) ∧ A2(x)→ A3(x)
I A3(x)→ A4(x)
I A4(x) ∧ A1(x)→ A5(x)
I A2(x)→ A4(x)
Let Ka contain:
I A2(b), A1(c), A2(c)
Which of the following hold:
I K |= A5(b)? No – K 6|= A5(b)
I K |= A5(c)? Yes – K |= A5(c)
DerivedAssertions
I A2(b)
I A1(c)
I A2(c)
I A3(c)
I A4(c)
I A5(c)
I A4(b)
Towards non-unary rule-based systems
Suppose we want to reason as follows:
I Peter is a son of John
I John is a son of Joseph
I Thus, Peter is a grandson of Joseph.
Then we require names for relations in addition to names for
classes.
I A relation name R denotes a set of pairs of individual objects.
Relation names are also called binary predicates. Examples:
I sonOf;
I grandsonOf
I we often denote relation name by the upper case letters R, S ,
R1, R2, and so on.
To express that an individual object a is in the relation R to an
individual object b, we write R(a, b). R(a, b) is (again) called an
atomic assertion. Example:
I sonOf(Peter, John).
Rule-based Systems
A rule has the form
R1(x1, y1)∧ · · ·∧Rn(xn, yn)∧A1(xn+1)∧ . . .∧Am(xn+m)→ R(x , y)
or
R1(x1, y1) ∧ · · · ∧ Rn(xn, yn) ∧ A1(xn+1) ∧ . . . ∧ Am(xn+m)→ A(x)
where
I R1, . . . ,Rn and R are relation names,
I A1, . . . ,An and A are class names,
I x1, y1, . . . , xn, yn, xn+1, . . . , xn+m, x , y are individual variables
A rule-based knowledge base K is a collection Ka of atomic
assertions and Kr of rules.
Rule-based knowledge base: Example
Consider the following set Ka of atomic assertions:
I sonOf(Peter, John)
I sonOf(John, Joseph)
Consider the following set Kr of rules:
I sonOf(x , y) ∧ sonOf(y , z)→ grandsonOf(x , z)
Then grandsonOf(Peter, Joseph) follows from K , in symbols
K |= grandsonOf(Peter, Joseph)
Rule-based knowledge base: Example
Consider the following set Ka of atomic assertions:
I sonOf(Peter, John)
I sonOf(John, Joseph)
I sonOf(Joseph,Paul)
Consider the following set Kr of rules:
I sonOf(x , y)→ descendantOf(x , y)
I sonOf(x , y) ∧ descendantOf(y , z)→ descendantOf(x , z)
Then descendantOf(Peter,Paul) follows from K , in symbols
K |= descendantOf(Peter,Paul)
Towards knowledge graphs
Binary predicates allows us to talk about graphs.
Let Kr contain:
I sonOf(x , y)→ descendantOf(x , y)
I sonOf(x , y) ∧ descendantOf(y , z)→ descendantOf(x , z)
Let Ka be {sonOf(Peter, John), sonOf(John, Joseph)}
Ka can be seen as the following graph (individual names = nodes,
relations = edges).
Peter John Joseph
sonOf sonOf
descendantOf descendantOf
descendantOf
Computing DerivedAssertions corresponds to a graph completion.
Knowledge graph: Example
Let Kr contain:
I childOf(x , y) ∧ childOf(z , y)→ siblingOf(x , z)
I Female(x) ∧ siblingOf(x , y)→ sisterOf(x , y)
I Male(x) ∧ siblingOf(x , y)→ brotherOf(x , y)
Let Ka be
{Female(Alice),Male(Bob), childOf(Alice,Carl), childOf(Bob,Carl)}
AliceFemale Bob Male
Carl
childOf childOf
siblingOfsiblingOfsiblingOf
sisterOfsisterOf
brotherOf
We assume different variables are replaced by different individuals.