## 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
#### 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
.
---
### 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
- 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
##### 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
##### 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*
###### 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](https://www.w3.org/TR/rdf-concepts/)
- 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](https://www.w3.org/TR/rdf-syntax-grammar/)
- 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)
#### 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
#### 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](https://www.w3.org/TR/rdf-mt/)
##### 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
##### 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
##### 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) $`
##### 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
#### 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 (?)
#### 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
###### 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 $`
- ``
- ``
- ``
- ``
- Equivalence of classes:
- `$ C\equiv D $`
- ``
- ``
- ``
- Top concept: `owl:Thing`
- Bottom concept: `owl:Nothing`
- Object properties:
- ``
- ``
- ``
- ``
- ``
- Datatype property:
- ``
- ``
- ``
##### 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
##### 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)