Intelligent Systems Lecture Notes

14 December 2011 • Description Logic

Outline

Description logics.
- Frames
Interpretation
Entailment and reasoning.
- Reasoning algorithms.
Extensions
Using description logics.

Individuals

Individuals (or entities) are featureless objects.
Individuals are represented by constants in a description logic.
tankEngine greenFrog overwhelmingDispair
Being featureless, constants get their properties by their relations to other parts of the description logic.

Concepts

A concept is a group of constants (of individuals or entities).
- The grouped individuals have common features embodied by the concept.
- HardBop Dogs EldritchHorror
The concept Thing (or Everything or Universe) contains all individuals in the description logic.
Concepts given as implied collections are atomic concepts.

Roles

A role specifies the relation between objects in a description logic.
A role is a binary relation.
- Other properties may follow from the particular role.
- :OwesMoneyTo :VacationsAt :Likes

Frames

Where are frames in all of this?
- Concepts represent generic frames.
- Roles represent slots.
- Constants represent individual frames.
The frame hierarchy is implicit in the relation among concepts.
- The relation is calculated, rather than being specified.

Compound Concepts

Description logics are distinguished by the ways they combine objects to form concepts.
- All r d: the individuals related to individuals in concept d by role r.
- AtLeast n r: The individuals related to at least n other individuals via role r.
- Fills r c: The individuals related to individual c via role r.
- And d₁…d_n: the individuals common to concepts d₁…d_n.

Examples

All :IsColor PrimaryColor — Every individual that's primary colored.
AtLeast 3 :RecommendedBy — Every individual with at least three recommendations.
Fills :MarriedTo elizabethTaylor — Every individual that's been married to Elizabeth Taylor.
And KansasCityRoyals LosAngelesRaiders — Every individual associated with both the Kansas City Royals and the Los Angeles Raiders.

Compound Example

And
	Wine
	Fills :Color red
	AtLeast 2 :GrapeType

Wine — all individuals considered as wine.
Fills :Color red — All individuals in the :Color role with constant red.
AtLeast 2 :GrapeType — All individuals in the :GrapeType role with at least two other individuals.

Complex Example

And
	Company
	AtLeast 7 :Director
	All
		:Manager
		And
			Woman
			Fills :Degree phD
	Fills :MinSalary $24.00/hour

Statements

A description logic can express the statements
- Constant c is an individual in concept d.
  - c satisfies d.
- All individuals in concept d are also in concept e.
  - e subsumes d.
- Concepts d and e contain the same individuals.
  - d and e are equivalent concepts.

Subsumption

Subsumption is, in a sense, the most basic statement.
- e is equivalent to d iff d subsumes e and e subsumes d.
- c satisfies d iff d subsumes c$'$, where c$'$ is a concept containing only c.
This will be an important property when it's time to reason.

Sentences

The sentences in a description logic are
- c $\rightarrow$ d (satisfaction).
- d $\sqsubseteq$ e (subsumption).
- d $\doteq$ e (equivalence).
for constant c and concepts d and e.
A description logic knowledge base is a set of sentences.

Sentence Example

ProgressiveCompany $\doteq$
	And
		Company
		AtLeast 7 :Director
		All
			:Manager
			And
				Woman
				Fills :Degree phD
		Fills :MinSalary $24.00/hour

Interpretation

A description logic interpretation $I$ is a pair $(\mathcal D, \mathcal I)$, where
- $\mathcal{D}$ is the domain, a set of objects, and
- $\mathcal{I}$ is the interpretation mapping.
The interpretation mapping has the properties
- $I($c$)$ $\in \mathcal D$ for any constant c.
- $I($a$)$ $\subseteq \mathcal D$ for any atomic concept a.
- $I($r$)$ $\subseteq \mathcal D\times\mathcal D$ for any role r.

Concept Mappings

Given the interpretation $I = (\mathcal D, \mathcal I)$,

$\mathcal I($Universe$) = \mathcal D$.

$\mathcal I($All$\;r\; d) =$

$ \{ x \in \mathcal D \;|\; (x, y) \in \mathcal I(r)$ for $y \in \mathcal I(d) \}$.

$\mathcal I($AtLeast$\;n\; r) =$

$\{ x \in \mathcal D \;|\; \#\{ (x, y) \in \mathcal I(r) \} \geq n \}$.

$\mathcal I($Fills$\;r\;c) = \{ x \in \mathcal D \;|\; (x, \mathcal I(c)) \in \mathcal I(r) \}$.

$\mathcal I($And$\;d_1 \ldots d_n) = \mathcal I(d_1) \cap \cdots \cap \mathcal I(d_n)$.

Sentence Truth

Given an interpretation $I$ and sentence s, s is true in $I$ $(I \models $ s$)$ is defined as

$I \models $ c $\rightarrow$ d iff $\mathcal I($c$) \in \mathcal I($d$)$

$I \models $ d $\sqsubseteq$ e iff $\mathcal I($d$) \subseteq \mathcal I($e$)$

$I \models $ d $\doteq$ e iff $\mathcal I($d$) \doteq \mathcal I($e$)$

for constant c and concepts d and e.
If S is a set of sentences, then $I \models$ S when
- $I \models$ s for every s $\in$ S.

Entailment

Let S be a sentence set and s be a sentence.
Suppose that $I \models$ s whenever $I \models$ S for any interpretation $I$.
Then S logically entails (or just entails) s.
If { } entails s, then s is valid.
- That is, $I \models$ s for any interpretation $I$.

Reasoning

Description-logic reasoning takes two forms:

KB $\models$ c $\rightarrow$ d or does c satisfy d?

KB $\models$ d $\sqsubseteq$ d$'$ does d$'$ subsume d?
for description-logic knowledge base KB, constant c, and concepts d and d$'$.
Reasoning involves calculating entailment.
- Unless the sentence is obviously valid.
  john $\rightarrow$ Universe
  And Doctor Woman $\sqsubseteq$ Doctor

Reasoning Example

Given Surgeon $\sqsubseteq$ Doctor $\in$ KB, then
KB $\models$ And Surgeon Woman $\sqsubseteq$ Doctor (*)
(*) also holds when KB contains

Surgeon $\doteq$

And Doctor (Fills :Specialty surgery)
But not when KB = { }.
- (*) is not valid.

Computing Subsumption

Determining subsumption is the basis for reasoning calculations.
Computing subsumption can be reduced to comparing concept structures.
The subsumption calculation has two steps:
1. Normalize the knowledge base KB to get sentences with uniform structure.
  - And simplify the knowledge base.
2. Match structure between the normalized concepts in the subsumption.

Subsumption Example

Given

d: All

atomicConcept

Fills r c₁

AtLeast 2 c₂

e: All

atomicConcept

Fills r c₁

AtLeast 3 c₂

then

KB $\models$ e $\sqsubseteq$ d and
KB $\not\models$ e $\sqsubseteq$ d

Normalization

Normalization is an iterative transforming algorithm.
Each normalized sentence is either
- an atomic concept, or
- a compound concept of the form
  
  And
  
  a₁ … a_n
  
  (Fills r₁ c₁) … (Fills r_f c_f)
  
  (AtLeast n₁ r₁) … (AtLeast n_l r_l)
  
  (All d₁ d₂) … (All d_a d_a)

Structure Matching

After normalization, compound concepts have the form
All d₁ … d_n
e subsumes d if, for every d_i in d there exists a corresponding e_j in e.
- For example, the atomic concept a_i from d also appears as a_j in e.

Structure Matches

Apart from atomic-concept matches, the other matches for d_i are
- Fills r_i c_i — there must be a e_j equal to d_i.
- AtLeast n_i r_i — there must be an e_i = AtLeast n_j r_i with n_j $\leq$ n_i.
- All r_i d$'$_i — there must be an e_j = All r_i e$'$_j with e$'$_j subsuming d$'$_i

Satisfaction

Determine if KB $\models$ c $\rightarrow$ d.
- Suppose KB contains c $\rightarrow$ e and
  KB $\models$ e $\sqsubseteq$ d
- Then KB $\models$ c $\rightarrow$ d.
This suggests the algorithm
1. Gather all KB sentences c $\rightarrow$ e_i.
2. Determine if KB $\models$ And e₁ … e_n $\sqsubseteq$ d
3. Conclude KB $\models$ c $\rightarrow$ d iff 2 holds.

Subtle Satisfaction

Unfortunately, determining satisfaction can require more subtle reasoning.
- Given KB with sentences
  fred $\rightarrow$ Fills :ManagedBy joe
  fred $\rightarrow$ All :ManagedBy Managers
  Empty $\doteq$ AtLeast 2 :ManagedBy
  Managers $\sqsubseteq$ Canadians
- then KB $\models$ joe $\rightarrow$ Canadian.
Computing satisfaction requires more work.

Computing Satisfaction

To show KB $\models$ c $\rightarrow$ d, propagate information in KB with a form of forward chaining.
The approach is the same, but each constant is placed in its most specific concept.
- An iterative task of three steps.
The most specific concept for c can then be tested for subsumption against d.
AtLeast concepts complicate the algorithm, but not impossibly so.

Extensions

Like frames, description logics can be extended in many ways.
- New concept forming operators, particularly numerically-oriented ones.
- More complex roles, usually involving relational operations (conjunction or inverse for example).
- Rules, similar to definite clauses, in establishing global assertions.
Extensions probably change reasoning algorithms.

Using Description Logics

Description logics can be used to
- Classify. The computed hierarchies organize individuals, and new individuals can be fit in.
- Monitoring. Incrementally adding sensor-based information to the knowledge base.
- Database access. Concepts as an alternative SQL.
- Quality control. Collected knowledge may be inconsistent or incomplete. Appropriate concepts can detect these conditions.

Summary

Description logics are a generalization of frame-bases systems.
Interpretations map a decision logic to a domain.
Reasoning algorithms compute subsumption to determine entailment.
Like frames, decision logics are easily extensible.
- But extensions influence the reasoning algorithms.

References

Structured Descriptions (Chapter 9) in Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque, Morgan Kaufmann, 2004.

This page last modified on 2011 December 14.

\(\mathcal I(\)Universe\() = \mathcal D\).

\(\mathcal I(\)All\(\;r\; d) =\)
	\( \{ x \in \mathcal D \;\|\; (x, y) \in \mathcal I(r)\) for \(y \in \mathcal I(d) \}\).

\(\mathcal I(\)AtLeast\(\;n\; r) =\)
	\(\{ x \in \mathcal D \;\|\; \#\{ (x, y) \in \mathcal I(r) \} \geq n \}\).

\(\mathcal I(\)Fills\(\;r\;c) = \{ x \in \mathcal D \;\|\; (x, \mathcal I(c)) \in \mathcal I(r) \}\).

\(\mathcal I(\)And\(\;d_1 \ldots d_n) = \mathcal I(d_1) \cap \cdots \cap \mathcal I(d_n)\).

\(I \models \) c \(\rightarrow\) d		iff \(\mathcal I(\)c\() \in \mathcal I(\)d\()\)

\(I \models \) d \(\sqsubseteq\) e		iff \(\mathcal I(\)d\() \subseteq \mathcal I(\)e\()\)

\(I \models \) d \(\doteq\) e		iff \(\mathcal I(\)d\() \doteq \mathcal I(\)e\()\)


KB \(\models\) c \(\rightarrow\) d or		does c satisfy d?
KB \(\models\) d \(\sqsubseteq\) d\('\)		does d\('\) subsume d?

ProgressiveCompany \(\doteq\)
	And
		Company
		AtLeast 7 :Director
		All
			:Manager
			And
				Woman
				Fills :Degree phD
		Fills :MinSalary $24.00/hour

Surgeon \(\doteq\)
	And Doctor (Fills :Specialty surgery)

And
	a₁ … a_n
	(Fills r₁ c₁) … (Fills r_f c_f)
	(AtLeast n₁ r₁) … (AtLeast n_l r_l)
	(All d₁ d₂) … (All d_a d_a)