Study Notes for Chapter 9 - Structured Descriptions

STRUCTURED DESCRIPTIONS

CHAPTER 9

Overview

• Chapter 9 extends the knowledge organization discussed in Chapter 8, focusing on the reasoning about objects in everyday thinking.

• While Chapter 8 emphasized categories and procedures, Chapter 9 delves into more direct representation techniques for objects and categories.

9.1 DESCRIPTIONS

9.1.1 Noun Phrases

• Noun Phrases: Functions that can represent complex constructs beyond simple nouns.

• Examples of the complexity of noun phrases:

  • For example, to express “a hunter-gatherer,” we may define a compound predicate as:
    Hunter ext{ extsf{&}}Gatherer(x)

  • This implies that both predicates must hold true for that term.

• Traditional First-order Logic (FOL) limitations: traditional FOL lacks support for such complex predicates and only focuses on noun phrases as simple nouns.

• Hence, a description logic (DL) is introduced to encompass more complex predicates.

9.1.2 Concepts, Roles, and Constants

• Two types of noun distinctions:

  • Category nouns: Describe basic classes of objects (e.g., Hunter, Teenager).

  • Relational nouns: Describe objects that contribute properties (e.g., Child).

• In DL:

  • Concepts: Category nouns.

  • Roles: Relational nouns.

• Generalization Hierarchy: Concepts can be organized in a hierarchy which allows for inheritance of properties.

• Constants represent individuals in the application domain, denoted in lowercase (e.g., johnSmith).

9.2 A DESCRIPTION LANGUAGE

• Syntax: Generally, includes logical symbols and nonlogical symbols.

• Logical Symbols in DL:

  • Punctuation: $[ , ] , ( , ), ;$

  • Positive integers: 1, 2, 3, etc.

  • Concept-forming operators: ALL, EXISTS, FILLS, AND.

  • Connectives: ≤, ±, →, =

• Nonlogical Symbols:

  • Atomic Concepts: Capitalized mixed case (e.g., Person, WhiteWine).

  • Roles: Written as atomic concepts but preceded by a colon (e.g., :Child, :Height).

  • Constants: Written in uncapitalized mixed case (e.g., desk13, maryAnnJones).

• Types of Syntactic Expressions:

  • Constants, Roles, Concepts, and Sentences.

• Concepts Rules:

  • Every atomic concept is a concept.

  • If $r$ is a role and $d$ is a concept, then [ALL r d] is a concept.

  • If $r$ is a role and $c$ is a constant, then [FILLS r c] is a concept.

  • If $d1, d2$ are concepts, then [AND d1 d2] is a concept.

• Sentences:

  • If $d1$ and $d2$ are concepts, then ($d1 = d2$) is a sentence.

  • If $c$ is a constant and $d$ is a concept, ($c → d$) is a sentence.

9.3 MEANING AND ENTAILMENT

9.3.1 Interpretations

• An interpretation I for DL consists of a pair (D,I).

  • D: Any set of objects (domain).

  • I: A mapping that assigns logical symbols to elements in D.

• Rules for interpretations:

  1. For every constant c, I[c] = D.

  2. For every atomic concept a, T[a] ⊆ D.

  3. For every role r, T[r] ⊆ D × D.

9.3.2 Truth in an Interpretation

• A sentence is true in I depending on its structure:

  1. ($c = d$) iff $T[c] = T[d]$.

  2. ($d = d'$) iff $T[d] ⊆ T[d']$.

  • If $c$ is constant, then ($c → d$) holds if $c$ satisfies $d$.

9.3.3 Entailment

• The notion of entailment states that a set of sentences S logically entails a sentence $$, written as $S
  ightarrow $, if for every interpretation I, if I satisfies S, then I must satisfy α.

9.4 COMPUTING ENTAILMENTS

• Major types of reasoning with a description logic include:

  • Determine whether constant $c$ satisfies a concept $d$.

  • Determine whether concept $d$ is subsumed by another concept $e$.

9.4.1 Simplifying the Knowledge Base

• Subsumptions in the knowledge bases are unaffected by sentences of the form $c → d$.

• To find if $d$ subsumes $e$, we simplify KB and check their structure.

9.4.2 Normalization

• Normalization is an essential step to transform concepts into a simpler representation.

  • Steps include expanding definitions, flattening AND operations, combining ALL operators, etc.

  • The goal is to get to a construct that is simple and has a clear structure.

9.5 TAXONOMIES AND CLASSIFICATION

9.5.1 A Taxonomy of Atomic Concepts and Constants

• A taxonomy organizes atomic concepts hierarchically, establishing partial orders.

• Constants in KB are linked to the most specific atomic concepts they satisfy.

9.5.2 Computing Classification

• Steps in adding new concepts to a taxonomy:

  • Identify most specific subsumers (S) and general subsumees (G).

  1. Calculate S, the most specific subsumers of concept d.

  2. Calculate G, the most general subsumees of concept d.

  3. Confirm uniqueness before adding new concepts.

  • Classification can be efficient by utilizing established hierarchies.

9.6 BEYOND THE BASICS

• Extensions of DL could complicate subsumption and entailment computations.

• Role Relations: Such as defining relationships in roles could add complexity.

• Qualified Number Restrictions: These would incur additional computational challenges.

9.7 APPLICATIONS OF DESCRIPTION LOGICS

• Scene management: Such as product catalogs and complex structures in hardware configurations requiring classification.

• Monitoring: Detects new instances and reclassifies individuals based on evolving data.

• Database Access: Mapping DL structured queries to traditional DBMS.

9.8 Exercises

• Exercises range across various subjects in DL, including conceptual operators, classification, and normalization. This aims to ensure a robust understanding of concepts.