Transcript Resources - IIT Bombay

CS621 : Artificial Intelligence
Pushpak Bhattacharyya
CSE Dept.,
IIT Bombay
Lecture 16
Description Logic
Brief on Knowledge
Representation
KR: primary aim of AI


facilitate inferencing
Inferencing often involves making
classes of objects, defining a
hierarchy, giving attributes to
objects and specifying constraints.
Predicate Calculus:
foundational KR



Uses (i) Predicates for describing
relationships and (ii) Rules for inferencing
A special kind of inferencing is Inheritance
where all properties of a super class are
passed onto its subclasses
For example, it can be inferred that bulldogsbeing dogs- have 4 legs by virtue of their
inheriting dog-properties.
Structured Knowledge
Representation



Components and their interrelationships have
to be expressed
Semantic Nets and Frames prove more
effective than predicate calculus
Reminiscent of calculus where using
differentiation to find the rate of change of
one quantity with respect to another is more
convenient than using the more foundational
y
x  0  x
Lt
Example Semantic Net
Frames
(example from medical entities
dictionary, Columbia University)
Have slots and fillers
A more common example of
frame
Student Frame:
Id:
Name:
Age:
Sex:
Roll No.:
Department:
01432004
David
22
Male
01432004
Microelectronics
Student Frame with the left column representing slots and the right
column representing fillers
Description Logic
Motivation to study



Structure of the knowledge may not be
visible, and obvious inferences may be
difficult to draw
Expressive power is too high for
obtaining decidable and efficient inference
Inference power may be too low for
expressing interesting, but still decidable
theories
Wikipedia Definition

“Description logics (DL) are a family of knowledge
representation languages which can be used to
represent the terminological knowledge of an
application domain in a structured and formally wellunderstood way. The name description logic refers,
on the one hand, to concept descriptions used to
describe a domain and, on the other hand, to the
logic-based semantics which can be given by a
translation into first-order predicate logic. Description
logic was designed as an extension to frames and
semantic networks, which were not equipped with
formal logic-based semantics.”
Constituents of DL



Individuals (such as Jack and Jill)
Concepts (such as Man and
Woman)
Roles (such as isStudent)
Individuals are like constants in predicate calculus,
while Concepts are like Unary predicates
and Roles are like Binary Predicates.
Constructors of DL and their
meaning
Constructor
Atomic Concept
Atomic Role
Conjunction
Disjunction
Negation
Exists Restriction
Syntax
A
R
C∩D
C D
C
 R.C
Example
Human
Has-child
Human ∩ Male
Doctor  Lawyer
 Male
 Has-child.Male
Value Restriction
 R.C
 Has-child.Doctor
Semantics using PC
{x | human(x)}
{<x,y> | has-child(x,y)}
{x | human(x)  male(x)}
{x | doctor(x)  lawyer(x)}
{x |  male(x)}
{x |  y has-child(x,y) 
male(y)}
{x |  y has-child(x,y)
doctor(y)}
Examples


For example the set of all those parents
having a male child who is a doctor or a
lawyer is expressed as
Has-child.Male ∩( Doctor U Lawyer)
Quantifiers and ‘Dots’
HasChild.Girl is interpreted as the
set


{x | (y)( HasChild(x,y)Girl(y))} and
isEmployedBy.Farmer is interpreted
as


{x | (y)( isEmployedBy(x,y) Farmer(y))}
Inference in DL



Main mechanism: Inheritance via
subsumption
DL suitable for ontology engineering
A concept C subsumes a concept D iff
I(D)  I(C) on every interpretation I

For example: Person subsumes Male, Parent
subsumes Father etc. Every attribute of a
concept is also present in the subsumed
concepts