Semantic Web

Basics

  • Goal:
    • Provide web page in machine-readable form
    • NOT: Understand natural language
    • Common formats for integration/combination of data
  • History/Motivation:
    • Tim Berners-Lee, 2001
    • Story of the Semantic Web Agent (plan complex tasks by using information from the Internet)
    • WWW is the medium of documents for people
  • Architecture:
    • Semantic Web Stack
  • How to represent knowledge?:
    • Early: AI with frames by Marvin Minsky
      • i.e., Slot and Filler notation
    • Expert Systems: MYCIN (uncertain reasoning)
    • Description logic
  • How to derive knowledge?
    • Requires a formal semantics (large number of logics …)
    • Requires decidability (often conflicts with expressiveness)
    • Expressiveness may be application-dependent
      • e.g., inheritance, negation, quantification
    • Tight coupling between theory and practice
      • e.g., fast evaluation
    • Result:
      • Description logics as formalism with OWL as implementation
    • Contradictions:
      • RDF-S forms a valid foundation for OWL
      • Datalog uses the closed world assumption and negation as failure (also subset of description logic)
      • Different semantics: Is the semantic web stack only one stack or two towers?
  • Summary:
    • Vision of the Semantic Web failed
    • But, it resulted in well-standardized techniques
      • Uniform Resource Identifier (URI)
        • Identify items
      • Extensible Markup Language (XML)
        • Syntax (design own document formats)
        • Use markup to enhance the semantics of content of documents
      • Resource Description Framework (RDF)
        • Machine-readable statements (triple)
    • e.g., RDF, OWL

https://upload.wikimedia.org/wikipedia/commons/f/f7/Semantic_web_stack.svg

The Web 3.0

  • Project 10X
  • Web 2.0: Connecting people
  • Web 3.0: Connecting knowledge
    • Add knowledge layer
    • Realize Semantic Web vision
    • Claim: Technology is present
  • Trends:
    • Semantic User Experience
      • Personalized, context-aware, immersive human-computer interaction
    • Semantic Social Computing
    • Semantic Applications
    • Semantic Infrastructure

../_images/13-web3.png.

Knowledge Representation

  • Expert Systems/Deductive Database:
    • Facts and rules
    • e.g., Datalog, Fuzzy reasoning
  • Question: How to represent the real-world knowledge?
  • Knowledge representation:
    • Concern: How to formally think
    • Components:
      • Symbol system/symbolic representation: Symbols representing the universe of discourse
      • Symbol manipulation: Formal reasoning system (to allow inference)
    • Knowledge base: Instance of this representation
  • Rule of thump: The more expressive, the more complex
  • Degrees of Representation framework:
    • Simple controlled vocabulary (catalog, glossary)
    • Simple relations between entities (classification, thesaurus)
    • Semantic networks (ontologies, frames)
    • Logic system (FOL, description logic)
    • Multilayered extended semantic network (MultiNet)

Mapping Knowledge

  • A representation abstracts from the real world
  • Workflow for inference
    • Map real world to Knowledge Representation Language
    • Perform Inference (using a KB)
    • Map new conclusions back to the real world
  • Problem:
    • Human reasoning is ambiguous due to natural language
    • e.g., Chair is placed on the table. It was broken (what was broken?)
    • e.g., Dog is placed on the table. It barked. (clearly, the dog barked)
  • Properties of a representation system:
    • Referential uniqueness
    • Semantic uniqueness
    • Functional uniqueness
  • Workflow linguistic sentence to knowledge representation
    • Disambiguate references
    • Disambiguate word sense
    • Write as predicate

Referential Uniqueness

  • Entity references must be unique
  • Symbolic representation must explicitly define relations for entity references
  • Unique name is called instance or token
  • e.g., Chair (chair-2543) is placed on the table (table-2334). It (chair-2543) was broken.
  • Problem: Distributed scenario (multiple ID by different authorities)

Semantic Uniqueness

  • Sense of words must be unique/unambiguous
  • Symbols of internal representation must be unique
    • e.g., bank/bank
    • e.g., catch (a cold)/catch (a ball)
  • i.e., resolve homonyms
  • Important for generalizing rules
    • e.g., things that are caught, have been moving before
    • the cold was not moving!
    • Disambiguate semantics
  • Results in controlled vocabulary
    • e.g., catch_cold, catch_object

Functional Uniqueness

  • Internal representation must uniquely express the functional roles
  • Functional role: subject, predicate, …
  • e.g., different sentence structures (passive vs. active)
  • Result:
    • Tom catches the ball. vs. The ball is caught by Tom.
    • catch_object(catcher: Tom, object: Ball)

Example: Linguistic Sentence

../_images/10-tom.png

  • Problem:
    • Usually, semantics of a sentence can not be represented by a single predicate
    • Solution: Use multiple predicates
    • e.g., Tom catches a white football
      • catch_object(tom, football)
      • color(football, white)
  • Problem:
    • Functional role within predicates is not clear
    • e.g., always valid or only in this sentence?
      • e.g., are all footballs white?

Slot Assertion Notation

  • Slot the same as arguments (based on the position of the argument)
  • Assign roles to different arguments of predicates
    • Turn predicate into instance
  • Express a functional structure
  • e.g. catch(Tom, football)
    • instance(X005, catch)
    • catcher(X005, Tom)
    • caught(X005, football)
  • Reification:
    • Add information about a statement
    • Reifying a relationship: Interpret relationship as entity
    • e.g., date_added(X0005, 2020-01-02)

Slot and Filler Notation (Frames)

  • Marvin Minsky
  • Idea:
    • Combine different slot assertions into one statement
    • Provide a structured expression
    • Leads to object- or event-centered expression
  • Example:
    • Slot assertions:
      • instance(X005, catch)
      • catcher(X005, Tom)
      • caught(X005, football)
    • Frame: catch(X0005, (catcher Tom), (caught Football))
    • catcher, caught: Slot (first argument)
    • Tom, Football: Filler (second argument)
  • Frame:
    • Frame is an object without methods
    • Frame is embedded in natural/hierarchical inheritance structure
    • Frame can be viewed as stereotype/prototype
    • Example:
      • Frame-object: catch(X0005, (catcher Tom), (caught Football))
      • ID: X0005
      • Attributes: (catcher Tom), (caught Football)

Description Logic

  • Formalism of the semantic web
    • Logic layer of the Semantic Web Stack
  • Motivation:
    • There are different schemes for knowledge inference
    • First-order logic
      • Pro: Expressive + Powerful
      • Con: Un-intuitive, hard to model, Computationally hard
    • Horn logic (e.g., Datalog)
      • Pro: Computationally manageable
      • Con: Less expressive, lacks intuitive modeling features
    • Frame Systems
      • Pro: Intuitive modeling, Human-centered
      • Con: Lack of formal semantics
  • Idea:
    • Provide different degrees of expressiveness
    • Retain decidability
  • Description Logic:
    • Combination of semantic frames and first-oder logic
    • Has various degrees of expressiveness (different classes)
    • Each description language (class) maps to a subset of first-order logic
    • All description languages are decidable
    • Rule of thumb: More expressiveness –> Higher computational complexity
  • Description Language:
    • Subset of description logic
    • Named/classified by its feature sets
      • e.g., Attribute language \( \mathcal{AL} \)
    • Provides different expressiveness/complexity of the TBox
    • Use a variable free syntax (shorter writing)
    • Different languages:
      • \( \mathcal{AL} \)
      • \( \mathcal{C} \): General complement
        • \( \mathcal{U} \): Union
        • \( \mathcal{E} \): Full existential quantification
      • \( \mathcal{S} \) (\( \mathcal{ALCLUE}+R^+ \))
        • \( \mathcal{H} \): Role Hierarchies
        • \( \mathcal{I} \): Role Inverses
        • \( \mathcal{F} \): Functionality
        • \( \mathcal{O} \): Nominals
  • Implementations:
    • RDF + RDF-S
    • OWL
    • DAML + OIL
  • Assumptions (of DLs):
    • Open World Assumption
      • Interpretation domain \( \Delta^i \) is infinite
    • Ambiguous Name Assumption
      • Two concepts with different names may me equivalent
      • e.g., Bruce_Willis vs. B_Willis_Actor

../_images/12-dl.png ../_images/12-comp.png

Basic Building Blocks

  • Terminology:
    • Individuals (e.g., instances, entities, constants)
    • Concepts
      • Unary predicates (like entity types)
      • Hierarchical inheritance structure
      • e.g., OO classes
      • Only representation, no methods like in OOP
      • Set of individuals
    • Roles
      • Binary predicates (like relationships)
      • Link concepts by using roles
      • Set of pairs of individuals
  • Basic building blocks:
    • Atomic concept: Enumeration of individuals
    • Atomic role: Enumeration of pairs of individuals
  • DL expressions can be used to describe complex concepts/roles by atomic concepts/roles

../_images/12-structure-ex.png

Expression Types

  • Description Logic Knowledge Bases consists of two types of expressions:
    • ABox statements
    • TBox statements
  • ABox statements:
    • Assertion Box
    • Provide assertions on the individuals (w.r.t. the vocabulary)
    • Member of a concept
    • Typical reasoning task:
      • Check for assertion consistency (satisfiability)
    • Contains facts
  • TBox statements:
    • Terminology Box
    • Define vocabulary of the knowledge base
    • Description language controls the complexity of the TBox
    • Defines complex concepts (e.g., concept hierarchy)
    • (complex roles are defined in the RBox)
    • Typical reasoning task:
      • Check for concept/role subsumption
  • Different description languages provide different TBox statements

Attribute Language \( \mathcal{AL} \)

  • Most basic description language
  • Minimal description language with practical applicability
  • Typical reasoning task:
    • Classification of individuals
    • e.g., return all students
Syntactical Constructs
  • Domain:
    • \( \Delta^I \)
    • Set of all indiviuals
  • Atomic concepts:
    • \( A^I\subseteq\Delta^I, B^I\subseteq\Delta^I \)
  • Atomic roles:
    • \( R^I\subseteq \Delta^I\times\Delta^I \)
  • Complex concepts:
    • \( C^I\subseteq\Delta^I, D^I\subseteq\Delta^I \)
  • Universal concept (top):
    • \( \top^I=\Delta^I \)
    • Represents whole domain of individuals
  • Bottom concept:
    • \( \bot^I=\emptyset \)
    • Represents the empty set of individuals
  • Atomic negation:
    • \( (\neg A)^I=\Delta^I\setminus A^I \)
    • Only possible on atomic concepts
    • Negation of complex concepts is in \( \mathcal{C} \) (General complement)
    • i.e., may result in an infinite set (open world assumption)
  • Intersection:
    • \( (C\sqcap D)^I=C^I\cap D^I \)
  • Value Restriction:
    • Defines all individuals which are in relationship \( R \) with individuals in concept \( C \)
    • e.g., \( \forall studies.University \)
    • \( (\forall R.C)^I=\{a\in\Delta^I\mid \forall b((a,b)\in R^I\rightarrow b\in C^I)\} \)
  • Limited existential restriction
    • Defines individuals which have a relationship partner in \( R \)
    • e.g., \( \exists studies.\top \)
    • \( (\exists R.\top)^I=\{a\in\Delta^I\mid \exists b((a,b)\in R^I)\} \)
Terminological Axioms (TBox)
  • Terminological Axioms realize the TBox statements
  • Inclusion:
    • \( C\sqsubseteq D \)
    • C is sub-concept of D (each indiviual in C is also in D)
    • \( C^I\subseteq D^I \)
  • Equivalence:
    • \( C\equiv D \)
    • Two concepts define the same individuals
    • May be used to define new complex concepts
    • e.g., \( hiwis \equiv studentischeHilfskraft \)
    • \( C^I= D^I \)
  • Use case: Check assertions about classes
    • e.g., Disjointness: \( D\sqcap E\equiv \bot \)
    • Check for unintended relationships between classes
    • Check the consistency
    • Automatic classification of new instances
    • Finding inconsistencies (useful for large ontologies)
  • Definitorial equivalence statement:
    • Equivalence statement are called definitorial if the statement is acyclic after expression optimization
    • e.g., \( C\equiv D\sqcap E \) (acyclic, definitorial)
    • e.g., \( C\equiv D\sqcup \exists R.C \) (cyclic, not definitorial)
    • e.g., \( C\equiv D\sqcup \exists R.(C\sqcap \neg C) \) (cyclic, definitorial)
      • \( \equiv D\sqcup \exists R.(\bot) \)
      • \( \equiv D \)
    • Acyclic TBox: All TBox statements are definitorial
    • Acyclic TBox can be reduced to an empty TBox by adding the statements to the ABox
  • Cyclic TBox:
    • Define concepts recursively
    • Increase complexity
    • Leads to fixpoint semantics
    • Can be used to model transitive roles
Expansion \( \mathcal{C} \): General Complement
  • Motivation
    • \( \mathcal{AL} \) allows only the negation of atomic concepts
    • General negation of complex concepts is necessary
  • \( (\neg C)^I=\Delta^I\setminus C^I \)
  • Resulting language: \( \mathcal{ALC} \)
  • Expressiveness:
    • Union and full existential quantification can be modeled with the general complement
    • \( (C\sqcup D)\equiv \neg(\neg C\sqcap\neg D) \)
    • \( \exists R.C\equiv\neg \forall R.\neg C \)
    • Use \( \mathcal{ALC} \) for \( \mathcal{ALUEC} \) and \( \mathcal{ALUE} \)
Expansion \( \mathcal{U} \): Union
  • Motivation: Union two complex concepts
  • \( (C\sqcup D)^I=C^I\cup D^I \)
  • Resulting language: \( \mathcal{ALU} \)
Expansion \( \mathcal{E} \): Full Existential Quantification
  • Motivation
    • \( \mathcal{AL} \) allows limited existential quantification
    • e.g., \( \exists R.\top \)
    • Existential quantification for complex concepts
  • \( (\exists R.C)^I=\{a\in\Delta^I\mid\exists b((a,b)\in R^I\land b\in C^I)\} \)
  • Resulting language: \( \mathcal{ALE} \)
Expansion \( \mathcal{N} \): Number Restriction
  • Number Restriction \( \gtrsim_n \)
  • Compare to cardinalities in ER-model
  • Al-least-Restriction:
    • \( \gtrsim_n R.C \)
    • \( (\gtrsim_n R.C)^I=\{a\in\Delta^I: |\{b: (a,b)\in R^I\}|\geq n\} \)
  • At-most-Restriction:
    • \( \lesssim_m R.C \)
    • \( (\lesssim_n R.C)^I=\{a\in\Delta^I: |\{b: (a,b)\in R^I\}|\leq n\} \)
Complexity of \( \mathcal{ALC} \)
  • Typical reasoning problems:
    • General satisfiability
      • \( \Sigma\not\models \bot \)
    • Concept satisfiability
      • \( \Sigma\not\models C\equiv\bot \)
    • Subsumption
      • \( \Sigma\models C\sqsubseteq D \)
    • Instance checking
      • \( \Sigma\models C(a) \)
    • Retrieval
      • \( \{a\mid \Sigma\models C(a)\} \)
    • Realization
      • \( \{C\mid \Sigma\models C(a)\} \)
  • Problems are reducible to general satisfiability

../_images/12-alc-complexity.png

Example
  • Individuals: Tilo, Jan, Student_A, Student_B, TUBS, KBS
  • Concepts: Person, University, Professor, Lecture
  • Roles: studies, teaches
  • ABox statements:
    • \( Person(Prof. Balke) \)
    • \( Person(Philipp) \)
    • \( Person(Student_A) \)
    • \( Person(Student_B) \)
    • \( University(TUBS) \)
    • \( Professor(Tilo) \)
    • \( Lecture(KBS) \)
    • \( teaches(Tilo, KBS) \)
    • \( teaches(Jan, KBS) \)
    • \( studies(Student_A, TUBS) \)
    • \( studies(Student_B, TUBS) \)
  • TBox statements:
    • \( Student\equiv Person\sqcap \forall studies.University \)
    • \( \mathcal{AL}: TeachingAssistant\equiv Person\sqcap \neg Professor\sqcap \forall teaches.Lecture \)
      • \( \mathcal{ALC}: TeachingAssistant\equiv Person\sqcap \neg Professor\sqcap \exists teaches.Lecture \)
    • \( HiWi\equiv Student\sqcap \forall teaches.Lecture \)

Description Language \( \mathcal{S} \)

  • \( \mathcal{S}:=\mathcal{ALCUE}+\text{transitive roles} \)
  • Motivation:
    • Define complex roles
  • New statement type: RBox (complex roles)
  • Base language: \( \mathcal{ALCUE} \)
  • Role transitivity \( R^+ \)
    • Simplest RBox statement
    • Transitive closure of ABox facts
    • e.g., recursion
    • \( (R^+)^I=\cup_{i\geq I}(R^I)^i \)
    • e.g., \( ancestor\equiv parent^+ \)
  • Note:
    • Most expansions do not increase expressiveness
    • Use them for convience
  • Expansions:
    • \( \mathcal{H} \): Role Hierarchies
    • \( \mathcal{I} \): Role Inverses
    • \( \mathcal{F} \): Functionality
    • \( \mathcal{O} \): Nominals
Expansion \( \mathcal{H} \): Role Hierarchies
  • Role Hierarchies using inclusion
  • \( (R\sqsubseteq S)^I=R^I\subseteq S^I \)
  • Allows for more reasoning capabilities
  • Allows for further complex role definitions
    • Intersection: \( R\sqcap S \)
    • Union: \( R\sqcup S \)
    • Negation: \( \neg R \)
    • Composition: \( R\circ S \)
  • Use for more reasoning capabilies
    • e.g., consistency check, role subsumption, role membership
Expansion \( \mathcal{I} \): Role Inverses
  • Inverse role: Swap arguments
  • \( (R^-)^I=\{(b,a)\in \Delta^I\times\Delta^I|(a,b)\in R^I\} \)
  • e.g., \( \text{isTaughBy}=\text{teaches}^- \)
Expansion \( \mathcal{F} \): Functionality
  • Restrict maximum number of role relation sources to 1
  • \( \lesssim_1 R \)
  • Role becomes a function (i.e., second argument fully functional dependent on the first argument)
  • \( R(x,y)\iff f(x)=y \)
  • e.g., age or mother
Expansion \( \mathcal{O} \): Nominals
  • Enumerated set of values which can be used (subset of the domain values)
  • Nominals are just a convenience feature
  • e.g., \( degrees\equiv\{BSc, MSc, Magister\} \)

Resource Description Framework

Motivation

  • Representation in Semantic Web
  • Idea: Annotate information on the web with Knowledge representation (make it machine-readable)
    • e.g., represent information like author, data, …
    • Web pages are identified by URLs
  • Motivation:
    • Humans can easily deduce/create/process visible information (e.g., natural language, graphics, layout)
    • Information is processed by Information Retrieval Systems (e.g., Google)
    • Task: Automatically combine data from the web
  • Requirements:
    • Data should be available for machines
    • Data should be combined/merged on Web scale
    • Data should be usable for reasoning
  • Resource Description Framework
    • Idea: Describe resources using XML
    • W3C recommendation, 2004
    • Two models:
      • RDF Concepts and Abstract Syntax (encode knowledge)
      • RDF Syntax (denote statements)

RDF Concept

  • Documentation
  • Decompose knowledge into triples
    • Results in a labeled, directed graph
    • Each edge represents a fact/relation between two things
  • Triple:
    • Also called statement
    • Subject: Name is URI
    • Predicate: Name is URI
    • Object: Name is URI or literal value (text, may be typed)
  • Namespace:
    • Motivation: URIs references (URI + fragment) are quite long
    • Namespace: Abbreviate URIs by namespace
    • e.g., w3c:index -> https://www.w3c.org/index
  • Blank node:
    • Some information has structure
      • e.g., address consists of street, zip, etc.
    • Blank node is intermediate node (not visible)
    • Identify using blank node identifiers
    • e.g., _:bruce_willis_address

RDF Syntax

  • More details
  • Resource Identification: URI
  • Resource Description: Properties and values
  • Representation of RDF by XML: RDF/XML
  • Syntax:
    • Namespace declaration
    • Description
  • Provenance of information: Describe RDF statements
  • Reification:
    • Description of a statement
    • Use built-in vocabulary:
      • type rdf:Statement
      • properties rdf:{subject, predicate, object}
    • Subject of the reification should consider a particular instance of a triple (e.g., add triple identifier directly)
  • RDF Graph:
    • Set of RDF triples
    • Subgraph: Subset of the RDF Graph
    • Proper subgraph: Proper subset of RDF Graph
  • Blank node/blank edge:
    • Ground graph: Graph without any blanks
  • Names:
    • Summarization of Literals and URIs
    • Name can be compared to a constant value in logics (Names have no semantics)
  • Graph vocabulary:
    • All names of a graph
    • i.e., all literals and URIs
  • Graph instance:
    • Tuple \( (G,M) \)
    • \( G \): Graph
    • \( M \): Mapping of blank nodes to names or nodes
    • Proper instance:
      • Graph where either (i) a blank node is mapped to a name or (ii) two nodes are mapped to the same node
      • Proper instance is more specific
      • Proper instance may still contain blank nodes
  • Graph is equivalent:
    • Graph is equivalent if a blank node is mapped to a new blank node (i.e., variable renaming)
  • Graph is lean:
    • Graph is lean if it has no internal redundancies
    • i.e., No instance is a proper subgraph of the original graph
  • Merging graphs:
    • No common blank node:
      • Union of the triples
    • Common blank nodes:
      • Map the blank nodes to new blank nodes
      • union the triples
      • i.e., rename intersecting blank nodes
  • Result:
    • Classify, merge and map graphs (required to map RDF to logics)
    • RDF graph expresses logical facts (e.g., use methods for reasoning)

../_images/10-rdf-xml.png ../_images/10-rei01.png ../_images/10-rei02.png

RDF Schema

  • RDF Vocabulary Description Language (RDF-S)
  • Goal:
    • Define valid RDF statements
  • Contains basic elements to describe the vocabulary of ontologies
  • Restrict the possible set of URI references
    • e.g., to improve data integration
    • Improve interoperability
  • Schema: Vocabulary
  • RDF-S provides building blocks to create vocabularies
    • Describe domain-specific classes/properties
    • RDF vocabulary in RDF-S are valid RDF graphs
  • RDF-S Classes:
    • Like OOP classes, inheritance
    • rdf:type, rdfs:subClassOf, rdfs:isDefinedBy
    • Describe characteristics using properties
      • Restrict possible subjects and objects
      • e.g., rdfs:range, rdfs:domain
    • Define properties and assign then to classes (different than in OO languages)
  • Provide additional semantics
    • e.g., types, ranges, domains

../_images/10-rdfs.png ../_images/10-rdfs2.png

SPARQL

  • SPARQL Protocol And RDF Query Language
  • Purpose: Retrieve information of an RDF graph
  • Use cases:
    • Extract information (URIs, blank nodes, plain/typed literals)
    • Extract RDF subgraphs
    • Construct RDF graphs
  • Idea:
    • Define a set of triple patterns
    • Any component can be a query
    • Matching triple patters to a graph creates bindings between the variable and RDF terms
  • SQL-style syntax
    • SELECT
    • FROM: Graph
    • WHERE: Limit query pattern
    • LIMIT, OFFSET, ORDER BY
    • CONSTRUCT: Returns RDF graph
    • DESCRIBE: Return RDF graph describing the resources
    • ASK: Boolean answer if a pattern matches
  • Graph patterns:
    • Basic graph patter
    • Group pattern
    • Value constraints
    • Optional graph pattern
    • Alternative graph pattern
    • Named graph pattern
  • Example:
    • SELECT ?url FROM g WHERE { ?x foaf:name "Jan" . }
    • ASK { ?person ex:marriedTo ?spouse }

Ontologies

Basics

  • RDF: Abstract domain knowledge -> Abstract Reality
    • New information can be derived
    • Network of these relationships is an ontology
  • Definition Ontology:
    • A) Formal representation of
      • Set of concepts in a certain domain
      • Relationships between the concepts
    • B) Formal, explicit specification of a shared conceptualization
    • Provides a shared vocabulary
      • Define type of objects/concepts
      • Define properties and relations between them
    • Middle layer of the Semantic Web stack
    • Domain ontology: Ontology for a specific domain
      • Disambiguate most terms
      • Incompatible with each other
  • Use Case:
    • Define a domain (represent the knowledge)
    • Reason about the domain
  • Application-dependent:
    • Medical ontology should be complete and sound
    • Ontology for holiday photos not
  • Important aspects:
    • Generation of ontologies (e.g., Folksonomy)
    • Capturing ontologies (e.g., RDF semantics)
    • Maintaining ontologies (e.g., keeping consistency)

Upper Ontology

  • Model of common objects which are applicable across a wide range of domain ontologies
  • Contains a core glossary (describe objects in a set of domains)
  • Standardized upper ontologies:
    • Usually, for metadata
    • e.g., Dublin Core, OpenCyc, GFO

Taxonomy

  • Means Law of arrangement
  • Part of ontology (ontologies are broader than taxonomies)
  • Group entities in so-called Taxa
  • Taxa are in hierarchical structure (supertype-subtype relationship)

History

  • 360 BC: Aristotle’s metaphysics
    • Ontology (science of being)
    • Natural theology (study of God)
    • Universal science (First Principles, Logics)
    • Central questions for ontologies:
      • Which things exist?
      • Which entities are fundamental?
      • What is a physical object?
      • What is existence?
  • 1305: Ars Generalis Ultima
    • Ramon Llull
    • Uses Tree of knowledge (hierarchy of philosophical concepts)
    • Solution for Ars Magna (Great Art)
  • 1738: Linnaean Taxonomy
    • Carl von Linne
    • Classify all living things
    • e.g., Eukaryotes
    • e.g., Kingdom, Phylum, Class, Order, Suborder, Family

RDF Semantics

  • Question: How to capture ontologies?
    • RDF-S can model formal vocabularies
    • Using RDF-S, RDF can express statements
    • Syntax of RDF with RDF-S vocabularies:
      • Language for expressing propositions
  • Semantics of RDF:
    • i.e., how to capture them?
    • Model-theoretic approach
      • Directly define model semantic
      • Graph matching
    • Translation approach
      • Translate RDF into logics
  • Problem: Reification leads to second-order logic
  • More information: RDF Semantics

Formal Language

  • \( \mathcal{L}=(\Gamma,\Omega,\Pi,X) \):
  • Constant symbols:
    • Names of the RDF graph which are not functions or predicates or variables
    • Separate into Literals (untyped, typed) and URIs
  • Function symbols:
    • RDF functions
  • Predicate symbols:
    • Names of the RDF graph used as predicate
    • Special names (e.g., rdf:type, rdfs:Class, rdfs:Property, …)
  • Variable symbols:
    • Names of the blank nodes

../_images/11-vocab.png

Formal Interpretation

  • \( I=(U,I_C,I_F,I_P) \)
  • Universe of Discourse:
    • Resources \( U_R \) (alpha-numeric string literals)
    • Properties \( U_P \) (predicates are part of the universe)
    • Reification makes RDF second-order logic
    • Literals \( U_L \)
    • \( U_P\subseteq U_R \)
    • \( U_L\subseteq U_R \) (literals)
  • Predicate mapping:
    • Map Property URIs to predicates
  • Constant mapping:
    • Map typed literals to resources (\( I_{CR} \))
    • Map untyped literals to literal values (\( I_{CL} \))
    • Map URIs to resources (\( I_{CU} \))
  • Interpretation uses Herbrand-style interpretation (symbolic)
  • Extension interpretation:
    • Required for the properties in \( U_P \)
    • \( I_{EXT}: U_P\rightarrow 2^{U_R\times U_R} \)
    • Extension provides actual semantics of the property (what evaluates to true and what to false)
    • cf. Herbrand interpretation

../_images/11-rdf-sem.png

Model-theoretic Approach

  • Central question: When is an interpretation \( I \) a model of a RDF graph \( G \)?
    • \( I \) is model of \( G \) iff \( I \) is a model for each triple \( t\in G \)
    • i.e., graph matching
  • Model of a triple:
    • \( I \) is model of triple iff the triple evaluates to \( true \)
    • \( t=(s_t,p_t,o_t) \) (must be in vocabulary)
    • Tilo: Triple must exist (RDF store)
    • \( (I(s_t), I(o_t))\in I_{EXT}(p_t) \)
  • Blank nodes:
    • Mapping of blank nodes to literals or URIs corresponds to a variable substitution \( \rho \)
  • Resulting graph must be grounded
  • Example: Node substitution
    • Substitution ?:x |--> c
    • Check for each triple (after substituting the blank nodes) if the interpretation is a model
    • e.g., \( (I(?:x), I(\text{mdb:bruceWillis})) = (c,a)\in I_{EXT}(r) \)

../_images/11-model-ex.png

Translation Approach

  • Translate RDF to logic:
    • Approach can be used for frame-based knowledge languages (i.e., reification, statements about statements)
    • Problem:
      • Results in higher-order logics
      • Requires restrictions to reduce complexity (see Description logic)
  • Requirement for the translation:
    • Vocabulary of the RDF graph
    • Translation scheme (map RDF to logics)
    • Intended model of the vocabulary of the RDF graph
  • Important:
    • Logic representation must keep RDF features (e.g., properties, classes)
    • Class: mdb:Movie is a class (mdb:Movie rdf:type rdfs:Class)
    • Usually, this [reification] is provided by higher-order logics
    • Only use second-order logics for well-defined tasks (class membership, subclass)
    • Do not use the full second-order logics (undecidable)
Transformation Rules
  • Transform RDF expression \( E \) into logic
    • Operator \( TR \)
  • URI reference:
    • Constant symbol or
    • Predicate symbol
  • Blank node: Variable symbol
  • Triple \( (s, \text{rdf:type}, o) \):
    • \( TR(p)(TR(o)(TR(s)) \land \text{rdfs:Class}(TR(o)) \)
  • Triple \( (s, p, o) \):
    • \( TR(p)(TR(s), TR(o)) \land \text{rdfs:Property}(TR(p)) \)
  • RDF graph:
    • Existential closure of the conjunction of all translations of all triples on the graph
    • e.g., \( \exists TR(E_1)\land\ldots\land TR(E_n) \)
  • Set of RDF graphs:
    • Conjunction of the translations of all graphs
Interpretation of Special Constructs
  • Goal: Interprete special RDF-S constructs
    • e.g., rdfs:subclassOf, rdf:type, rdfs:Class
  • Problem: rdfs:Class is higher-order logic (reduce complexity)
  • Use additional axioms and rules for the evaluation
  • Use axioms to construct proof trees
  • RDF axioms:
    • (also required by the model-theoretic approach)
    • rdf:type(x, y) --> y(x)
    • rdf:Property(rdf:type)
    • rdf:Property(rdf:subject)
    • For all RDF special names which are properties or types
  • RDFS axioms:
    • rdfs:Resource(x)
    • rdfs:Class(y) --> (y(x) <--> rdf:type(x,y))
    • …

Hierarchical Expert Ontology

  • Problems with Expert ontologies:
    • Inflexible/rigid (only representing the author’s view and knowledge)
    • Hard to change if established
    • Expensive to maintain
    • Hierarchical classification often not very practical
  • Examples:
    • Medical Subject Headings
    • Periodic Table of Elements
    • Dewey Decimal Classification (DDC)
    • Yahoo Categories (classification of the Web, did not work)
  • Transition from strictly hierarchical to linked hierarchical taxonomies (e.g., MeSH)
  • Problem:
    • Highly unstructured domains do not allow a hierarchical classification
  • Idea:
    • Omit the hierarchy and only use links
    • Folksonomy: lightweight ontologies

../_images/13-hier01.png ../_images/13-hier02.png

Ontology Generation

  • Manual creation is expensive and error-prone (not web-scale)
  • Goal: Automatic generation of ontologies
  • Idea: Mine statistical connections between terms
  • Heuristics:
    • Natural Language Processing
    • Term co-occurrence
  • Central question: Can purely statistical approaches lead to intelligent results?

Natural Language Processing

  • Major approach for ontology creation
  • Use phrases like such as or like to find synonyms or subclasses
  • e.g., Named Entity Recognition
  • Store the belief of correctness

Term Co-Occurrence

  • Extraction method for domain ontologies
  • Extract salient keywords from a text (i.e., terms)
  • Use a sufficiently large collection
  • Example:
    • Keyword X subsumes Y
    • 80 % of documents containing Y contain X
    • X occurs on more documents than Y

Collective Intelligence (D)

  • Idea: Statistics on human decisions
  • Francis Galton, 1822-1911
    • Claim: Intelligence and leadership are inherited
    • Statistical analysis: Crowd consensus is best estimate
    • Resulted in research area: Crowd decisions
    • Under certain restrictions large crowds of people are able to perform highly effective decisions
  • Use group intelligence for three types of problems:
    • Cognition Problems
      • Judging and Processing information
      • e.g., guessing, predicting, assessing
    • Coordination Problems
      • How to coordinate own behavior with all others?
      • e.g., Cultural behavior (expections on others)
      • e.g., Navigation in heavy traffic, using seats in lecture hall
    • Cooperation Problems
      • Self-centered people should work together for a greater good
      • Form networks of trust without a central controller
      • e.g., free market, paying taxes
  • Key criteria for wise decisions:
    • Diversity of Knowledgeable Opinions
      • ‌diversity of knowledgeable opinions (no/small bias)
      • Each person should have private information
      • Opposite opinions increase accuracy of group decisions (cancel out others mistakes vs. creating a discussion)
      • Everybody must understand the problem
      • Problem: Too homogeneous groups
    • Independence
      • Peoples opinions should be independent (not determined by the option of others)
      • Problem: Information cascades
      • Problem: Dominant members, Hype bubbles
    • Decentralization
      • People are specialized in local knowledge
      • Add diversity
      • Local knowledge can be used for optimized solutions
      • Problems: Wasted efforts
      • e.g., open-source software,
    • Aggregation
      • All individual opinions/decisions must be aggregated
      • e.g., compute average

Folksonomies

  • Idea:
    • Use crowd intelligence for ontologies
    • People tag web content (e.g., Flickr)
    • Tags represent common, shared knowledge
  • Similar idea: PageRank
    • Link from a page counts as vote
  • Tagging: Assignment of a word to some resource
  • Tag cloud: Representation of the tags of a resource (bigger word - used more often)
  • Folksonomy:
    • Weaker structure than description logic ontologies
    • No taxonomy
    • No vocabulary
    • Folksonomy represents self-emergent semantics
    • Can be created by the co-occurrence of tags
  • Disadvantages
    • No controlled vocabulary (e.g., ROFL)
    • Handling of synonyms/homonyms (e.g., ifis vs institute of information systems)
    • Questionable semantics (no formal reasoning possible)
Formalization
  • Folksonomy \( T \)
  • Tripartite hypergraph \( H(T)=(V,E) \)
  • Vertices \( V=A\cup C\cup I \)
    • \( A \): Actors
    • \( C \): Tags/concepts
    • \( I \): Instances/objects
  • Tag represents an edge between an actor, tag and instance
    • \( E=\{\{a,c,i\}\mid (a,c,i)\in T\} \)
  • Using the hypergraph, generate three weighted bi-partite graphs
    • Weight: How often are the di-grammed vertices are connected
    • Graph \( AC \)
      • Actors and concepts
      • \( AC=(A\times C, E_{ac}) \)
      • \( E_{ac}=\{(a,c)\mid \exists i\in I:(a,c,i)\in E\} \)
      • \( w:E_{ac}\rightarrow\mathbb{N} \)
      • \( (a, c)\mapsto |\{i:(a,c,i)\in E\}| \)
    • Graph \( CI \): Concepts and instances
      • Affiliation graph
      • Only keep edges with a certain occurrence
    • Graph \( AI \): Actors and instances
Ontology
  • Fold the affiliation graph into two lightweight ontologies
  • Graph \( CI \)
  • Lightweight ontology of related concepts
  • Lightweight ontology of related instances
  • Represent how the entities are related (e.g., co-occurrences)
  • Multiply matrix with its inverse
    • Results in co-occurrence matrix
    • Normalize using a Jaccard coefficient (?)

../_images/13-folk.png

Languages

  • Implementation of description languages
  • Languages:
    • OWL
    • DAML + OIL

Web Ontology Language (OWL)

  • W3C recommendation in 2004
    • Language and Semantics of choice for ontologies
  • OWL is an XML syntax
    • Encapsulate respective description logic language
    • Technically, builds upon RDF (but is much more powerful)
  • RDF-S forms a valid foundation for OWL
  • Three complexity classes:
    • OWL Lite
    • OWL DL
    • OWL Full
  • Two kinds of properties:
    • cf. Description Logic Roles
    • Object properties
      • Relate objects to objects
        • e.g., supervises, toughtBy
      • Object datatypes can have a domain and rage
        • e.g., domain=human, range=course
    • Data type properties
      • Relate objects to datatype values
      • Use XML Schema data types (range)
      • e.g., RDF literals

../_images/12-owl.png

OWL Lite
  • Provides a classification hierarchy and simple constraints
  • Compare to \( \mathcal{SHIF(D)} \)
    • AL (Concepts, Existential quantification, …)
    • General complement
    • Transitive roles (S)
    • Role Hierarchy (H)
    • Role Inverses (I)
    • Role Functionality (F)
    • Data types (D)
  • ExpTIME-complete
OWL DL
  • Provide maximum expressiveness while retaining computational completeness and decidability
  • Contains all OWL language constructs (but only usable under certain conditions)
  • Compare to \( \mathcal{SHOIN(D)} \)
    • Number Restriction (N)
    • Nominals (O)
  • NExpTIME-complete
  • Problem: Decidable but different semantics than RDF-S
OWL Full
  • Preserve compatibility with RDF Schema
  • Different semantics than OWL DL and OWL Lite
  • Based on second-order logics (statements about statements)
    • e.g., class can be treated as a collection of individuals and as an individual itself
  • Not decidable
  • Problem: Compatible with RDF-S but computationally hard
Examples
  • Classes:
    • owl:Class is subclass of rdfs:Class
  • Disjointness of classes:
    • \( C\sqcap D\equiv \bot \)
    • <owl:Class rdf:about="#hiwi">
      • <owl:disjointWith rdf:resource="#prof"/>
      • <owl:disjointWith rdf:resource="#hiwi"/>
    • </owl:Class>
  • Equivalence of classes:
    • \( C\equiv D \)
    • <owl:Class rdf:about="#faculty">
      • <owl:equivalentClass rdf:resource="#academic StaffMember"/>
    • </owl:Class>
  • Top concept: owl:Thing
  • Bottom concept: owl:Nothing
  • Object properties:
    • <owl:ObjectProperty rdf:ID="teaches">
      • <rdfs:range rdf:resource="#course"/>
      • <rdfs:domain rdf:resource= "#academicStaffMember"/>
      • <owl:inverseOf rdf:resource="#isTaughtBy"/>
    • </owl:ObjectProperty>
  • Datatype property:
    • <owl:DatatypeProperty rdf:ID="age">
      • <rdfs:range rdf:resource="http://www.w3.org/2001/XLMSchema #nonNegativeInteger"/>
    • </owl:DatatypeProperty>

DAML + OIL (D)

  • Goal: Evaluate the RDF-S statements of the semantic web
  • DAML and OIL were developed in parallel (combined in 2000)
DARPA Agent Markup Language (DAML)
  • 1999-2006
  • Goal: Facilitate concept of the Semantic Web
  • Focus on tools for intuitive formulation of knowledge
  • DAML RDF Editor
    • Use to annotate websites
Ontology Inference Layer (OIL)
  • Proposal:
    • Web-based representation and inference layer for ontologies
  • Compatible with RDF-S
  • Goal:
    • Define a logical foundation for the semantic web
    • Provide frame-based techniques + formal semantics of description logic
  • Layered approach to a standard ontology language
    • Each layer adds functionality and complexity
    • Dumb-Down-principle: Ignore features of higher layers which are not understood
  • Core OIL
    • Similar to RDF-S
    • Exception: No reification of RDF-S
    • \( \text{Core OIL}=\text{Standard OIL}\cap\text{RDF-S} \)
  • Standard OIL
    • Language designed to capture the necessary modeling primitives
    • Provide adequate expressive power
  • Instance OIL
    • Adds individual integration
    • Database-capability
  • Heavy OIL
    • Additional representation and reasoning capabilities

../_images/12-oil.png

Protege (D)

  • Major tool for building Ontologies
  • Stanford + Manchester University
  • Support for RDF and OWL
  • Support TBox, ABox, RBox

Examples

The Cyc System (D)

  • Cyc System
    • Douglas Lenat, 1984
    • Idea: Build a real AI system with a knowledge representation as base
    • Developed at MCC, founded by Cycorp
  • Goal:
    • Program should learn from books
    • System contains common knowledge (of a student of first grade)
  • Common knowledge:
    • Humans encode facts and rules
    • System checks for consistency
      • Inconsistencies resolved by humans
      • e.g., witches are evil, witches do not exist
  • CycL:
    • Representation language (based on FOL)
    • Create KB using CycL
  • Cyc Knowledge Base:
    • Contains classification of objects: Most general is Thing
    • Divided into microtheories:
      • Focus on domain/level of detail/time interval
      • Bunde assertions with a set of common assumptions
    • General knowledge
      • Things, objects, individuals, collections
      • e.g., chemistry, domain-specific knowledge, political knowledge
  • Cyc System:
    • Contains 24.5 millions rules
    • Original Cyc
    • OpenCyc
    • ResearchCyc
  • Drawbacks:
    • Conclusion only valid within the assertions
    • Consistent data can lead to false conclusions (data is not representative for the real world)
  • Application:
    • Directed marketing (use buying history)
    • Database integration (resolve conflicts)
    • Translation of technical documents
    • Language understanding
    • Security
    • Medicine

Dublin Core

  • Dublin Core Metadata Element Set (DCMES)
    • from Dublin, Ohio
  • Used to describe digital materials
    • Cross-domain information resource description
    • e.g., video, sound, image, web pages
  • Defined by ISO 15836/NISO Z39.85-2007
  • Consists of two levels:
    • Simple Dublin Core (15 elements)
    • Qualified Dublin Core (3 additional elements, refinements)
  • Simple DCMES:
    1. Title
    2. Creator
    3. Subject
    4. Description
    5. Publisher
    6. Contributor
    7. 9 more
  • Qualified DCMES:
    • Elements:
      • Audience (target group)
      • Provenance (trustworthiness)
      • RightsHolder
    • Element refinements:
      • Specify the meaning of elements
  • Dumb-Down Principle:
    • If an application does not understand an element, ignore the element

Medical Subject Heading (D)

  • MeSH ontology
  • Controlled vocabulary (Taxonomy + Thesaurus)
  • Maintained by US National Library of Medicine
  • Classify MEDLINE/PubMed collections
  • Hand-crafted by medical experts
  • Subjects: around 27.000 descriptors
    • e.g., concepts, diseases, hierarchically ordered
  • Qualifiers: Encode commonly used tags

Dewey Decimal Classification (DDC)

  • Melvin Dewey, 1876
  • Proprietary system for library classification
  • e.g., used by Library of Congress
  • 10 Main classes with 10 divisions each and 10 sections per division
  • Strictly hierarchical
  • Main problem: Inflexibility
    • e.g., 290 Other religions (later, more books were added)