From KA to KR

Bijan Parsia

COMP60462

What Happened This Morning

• Identified a domain (c. elegans)
  • Ok, had the domain thrust upon you
• Identified sources of knowledge (Wikipedia, Worm atlas)
  • Ok, ibid
• Started the KA process
  • Extracted and normalized terms
  • (Roughly) Categorized terms
  • Assembled a heirarchy
  • Elicited tacit knowledge
• What now?

Formalization

• Elicitation
  • Makes things clearer
  • Brings out hidden things
  • But everything is in natural language
    • Or other informal or semi-formal structures
    • Results in a (better) conceptualization, not a representation
• Formalization
  • Regimentation into a formal language
  • The regimentation should capture key aspects of the knowledge
    • I.e., represent it in a program accessible way
    • First approx: The program is a reasoner for that language

Crude Workflow

A Simple Formalism

• Three syntax bits
  • Nodes with Labels
  • (Directed) Arcs
    
• Nodes represent terms
  • The term (or its spelling) is given by the label
• Arcs represent relations between terms
  • But which? Any old?
  • We'll use the most common: is-a

Nodes and Arcs, Oh My

Person is-a Animal.
Wolf is-a Animal.
Animal is-a Living Thing.

Another Node!

• What about Bijan?
  • Seems like he is-a Person
  • Let's add him in!
    

A Simple Proof Theory

• One test of our representation
  • Reasoning! Which role?
• Simple theory
  • Pretheoretical idea: If A is-a B, and B is-a C, then A is-a C
    • Our sanctioned inferences are of the form X is-a Y
  • I.e., is-a is transitive
  • So, we can find paths

PT algorithm

• Input:
  • Ontology: <N, A> (a set of nodes and arcs)
  • Entailment: <t1, t2> (two terms in a is-a relation)
• Output: Yes or No
  • (i.e., Does the ontology entail t1 is-a t2? Yes or no.)
• Procedure:
  • if t1 or t2 is not in N, then return No
  • target := t1
  • while target != null
    • if <target, X> in A,
      • then if X == t2, then return Yes
        • else target := X
      • else target := null
  • return No

Step 1

Bijan is-a Living Thing?

The Loop

Bijan is-a Living Thing?

Answer: YES!

Linear Version

• 1) Bijan is-a Person.
• 2) Person is-a Animal.
  • 3) Bijan is-a Animal. (From 1 and 2)
• 4) Wolf is-s Animal.
• 5) Animal is-a Living Thing.
  • 6) Bijan is-a Living Thing.(From 3 and 5) (The conclusion!)

Is the PT Correct?

• Is it?
  • For what cases?
    • How do we tell?
  • How about this one?

Evaluation

• We have a representation language
  • Syntax (nodes, labels, arcs)
  • Semantics (well, an intuitive one)
  • Proof theory
    • We've seen a standard: "Correctness"
• We have some sample representations
  • I am a person
• How do we evaluate these?
  • All evaluation is relative to interests and goals
    • And involves evaluating tradeoffs
  • We might evaluate different parts differently
  • We need standards and critera

Evaluation: The Representation

• It's small
  • 5 or 6 nodes
  • 4 or 5 arcs
• There's implicit knowledge
  • But pretty trivial
• It's not systematic
  • No domain coverage, for example
• It serves no application
  • It is a toy example, after all
  • Its purpose is pedagogic and it does that reasonably

Evaluation: Language

• The official syntax
  • Graphical (pretty!)
  • Cumbersome to write (but pretty!)
  • Hard to parse
  • Scales v. poorly. Consider:
    • 
• The linear syntax is more reasonable
  • But less pretty!

Ambiguity

• What about Bijan?
  • Is the is-a the same between
    • Bijan and Person?
    • Person and Animal?
• Can our proof theory distinguish these cases?
  • Should it?
• Is the is-a the same between
  • Bijan and Person?
  • Wolf and Animal?
• If not how can we tell?
  

Other "Links"

• Consider a different extension
  • Wolf is-a Animal
  • GreyWolf is-a Wolf
  • GreyWolf is(-a) Grey(Thing)(?)
• How do we want to reason or represent this?
  • What is it to be a GreyThing?
    • Do you have the color Grey?
    • Is Grey a node? A generic? What about color?
• Another
  • Person is-NOT-a Wolf
  • What happens to our proof theory?

What about the ISAs?

• Reading: What ISA is and isn't
  • >20 distinct sense of is-a
    • Subset, material conditional, instance-of, abstraction...
  • Many different sorts of node
    • Many more than "class" and "instance"
    • Set, predicate, kind, structured description, role...
  • Wasn't always clear what's going on
    • Without examining program code
    • But they, intent wasn't clear
• A strong motivation for moving to logic-based KR
  • Clear syntax and semantics
  • Standard proof theories
  • Lots and lots of experience

Some specific IS-A ambiguities

• Two kinds of node
• Classes
• Individuals
• IS-A as subsumption
• Cat IS-A Animal
• Cat subClassOf Animal
  
• IS-A as instantiation
• Fred IS-A Cat
• Fred instance-of Cat
  • Fred type/has-type Cat
• Two kinds of arc?

A Simple Resolution?

• Have different labels for difference arcs
• Note that with loss of ambiguity, loss of expressiveness!
• What kind of expressiveness?
• We have 4 possible patterns:
• Class-Class
• Fix with sub-class relation?
• What about all the other sorts of is-a?
• What about non-is-a links?
• Instance-Class
• Fix as instance-of a class?
• Ibid
• Instance-Instance
• Arbitrary relation
• E.g., eats, loves, teaches
• Class-Instance (??)

Evaluation: Language

• Natural Language
  • Imprecise, verbose, hard to manipulate programmatically
• Nodes and Arsc (N-ARC)
  • Ambiguious, only intuitive semantics
  • Inexpressive
  • Cumbersome
  • Hard to extend
• Linearized
  • Same semantics
  • Distinctions easier
  • Extensions easier
• Reduction to other language
  • Get everything the other language offers!

Reduction to OWL

• (Linear syntaxes are more compact and manipulable)

  
          Class: Wolf SubClassOf: Animal
          Class: Person SubClassOf: Animal
          Class: Animal SubClassOf: LivingThing
          Class: LivingThing
          Individual: Bijan Types: Person
        

Evaluation: Proof Theory

• What's the service?
  • Start with Yes/No entailment checking (of subsumption/instantiation)
• Is the service computationally reasonable?
  • The problem is definitely polynominal
  • The procedure is pretty reasonable
    • Could imagine variants
• Is the service useful
  • Somewhat, yes
  • Better than having to manifest and maintain all is-a links!
• Is the service usable
  • Well, yes if we have a particular subsumption/instantiation question

Interlude: What is a Taxonomy?

• General Notion
• An organization (typically hierarchial) of (kinds of) entities
• E.g., Kingdom-phyla-class-order-family-genus-species
• I.e., subclass relations
• Along with principles of organization
• Think of the biological..some notion of relatedness
• Self-standing vs. modifer (i.e., different facets)
• In computer science, often refers to a subsumption heirarchy
• esp. if asserted
• Think Yahoo!, DMoz, even library of congress
• Connected with "semantic nets" and controlled vocabularies
  

Animal Taxonomy

• Animal
• Mammal
• Cat
• Dog
• Cow
• Person
• Domestic
• Pet
• Cat
• Dog
• Farmed
• Cow

Problems with Taxonomies?

• Organizationally rigid
• To be in it's proper place, you must put it there
• If there are multiple proper places...put 'em!
• Easier for leaves, harder for multiple organizations
• See: Metacrap: Putting the torch to seven straw-men of the meta-utopia
• Key point (2.5): Schemas aren't neutral (really 2.7 as well)
• Non-netural example
  

  Eco-wash Inc.	Mega-Glitzy-Load-Corp Ltd.
  Energy consumption: Water consumption: Size: Capacity: Reliability	Color: Size: Programmability: Reliability

• Impoverished description

• that cats are carnivores
• but not, why cats are carnivores
• or, what it is to be a carnivore
• or even, if we say that cats are carnivores and herbivores, there's a problem!

What is the/a Problem?

• The representational problem?
• Impoverished description
  • Only "brute" term relations
    • that cats are carnivores
      • but not, what makes cats carnivores
      • or, what it is to be a carnivore
      • or even, if we say that cats are carnivores and herbivores, there's a problem!
  • We describe term-term relations
    • Not what the term means
    • "Global" moves
• No (straightforward) sanity check
  • Do we make sense?
  • Weak services

More Expressivity

• Not just term-term relations
• We want definitions
• a carnivore is an animal that eats only meat
• We want to add constraints
• carnivores are not herbivores
• What entailments might we hope for?
• From, carnivores eat only meat
• And, cats eat only mice
• And, mice are meat
• That, cats are carnivores
• "Herbivorious cat" is incoherent

Constraints and Definitions

• We have relations between classes:
• C SubClassOf B
• C is a sufficient condition of B
• One way to be a B is to be a C
• B is a necessary condition of C
• If x is a C, then x is a B
• C EquivalentTo B
• C is a necessary and sufficient condition of B (and vice versa)
• When C and B are (always) names this is trivial
• But we can use class expressions in place of either
• Definitions and constraints can interact
• In surprising ways

Some definitions

Class:
      Carnivore
          EquivalentTo:
               (eats some Animal)  and (eats only Animal)
Class:
      Father
          EquivalentTo:
               Male and (parentOf some owl:Thing)

Definitions have consequences

• Some are obvious:
Class: Father
    SubClassOf:
        Male
(But note that they are not equivalent.)
• Some are less so:
• Class: Carnivore   
    SubClassOf:
        Animal

• (If we also have:

        ObjectProperty: eats domain: Animal

Examining the System

• If we have (and can read) a semantics
  • Great, we're (almost done)
  • Need to consider the legal entailments
• If not, what then?
  • How can we analyze a KR system?
    • Any KR system
    • Both the system and a representation

A Functional Description

• The system has two operators
• ASK and TELL
• We can describe behavior of the system "externally"
• I.e., by responses to certain ASKs after specific TELLs
• ASK takes a state and a sentence and returns yes or no
  • Sound familiar?
• TELL takes a state and a sentence and returns a new state
• We can also use this to conceptualize user interaction
• This is a very constrained interface
• It allows represenation independant specification
• But, suitibly liberallized, does not ensure it

Methodology Implications

• In our situation:
• The KR system is a file + Protege + a reasoner
• Well TELL it things via the interface
• ASKing is enabled by a command
• So consider that the updating has to be independant of the reasoning
• We have a set of canonical ASKs
• I.e., all the atomic subsumptions
• The system is reactive
• We react to the system
• From dealing with inconsistencies
• To being stimulated to reflect
• Bottom-up style
• We think in terms of individuals and their relations

Our Formalism

• OWL (The Web Ontology Language)
  • A decidable fragment of FOL
    • Terminates for all answers
      • To questions posed in it and answers expressed in it
  • A Class/Object/Relation language
    • Familiar, yet importantly different!
  • Inference (entailment) oriented
• Key notions
  • Entity (atomic/named terms)
  • Expression (a description)
  • Axiom (a declarative statement; a "relation" between expressions

Manchester Syntax

• The Manchester Syntax is one of many surface syntaxes
• Built into Protege 4
  • Used as the expression language
  • See the Protege tutorial
    • Working through it is highly recommended
• Infix with NL keywords
  • and, or, not, only, some
• Used in the OWL Primer
  • Under construction...feedback welcome

Brief intro to OWL

• We'll be delving into the syntax, semantics, and pragmatics over time
• OWL has two basic parts:
  • Logical part
    • Tight correspondence with Description Logics
  • Non-logical parts
    • E.g., annotations
  • Often, the annotations are the key

Terms in OWL

• (Description logics were known as Terminological Logics)
• An ontology is a set of axioms characerizing a set of terms
  • The set of (user modifiable) terms for an ontology is the signature
  • The fixed terms (in general) form the logical vocabulary or connectives
• We can divide the terms into categories
  • (Which we will treat as disjoint for the moment)
  • The key categories are Classes, Individuals, Data values/Literals, Data Ranges/Types, and different kinds of Property/Role
• Conceputally, we can divide the axioms into corresponding categories
  • Class axioms (the TBox, akin to a database schema)
  • Assertions (the ABox, akin to a database)
  • Property Axioms (the RBox, akin to part of the database schema)

Expressions

• In order to describe or define terms, we need more than term-term relations
  • We need descriptions, or expressions
  • Expressions "evaluate" to a class, property, individual etc.
    • Well, note exactly, but it's a useful fiction
    • We have different, and differently expressive, expression languages for each term category
      • The richest for Classes, probably the weakest is for Individuals
      • Partly historical, partly technical
  • We can think of names/terms as degenerate expressions, e.g., atomic expression
• Mastering the expression language is critical!
  • See (the dated) Ontology Development 101 paper

Axioms

• Axioms state relations between expressions
  • A SubClassOf axiom relates two class expressions
  • An ObjectSubPropertyOf axiom relates two object property expressions
  • A ClassAssertion axiom relates an individual and a class expression
• We can vary either the axiom connectives, the expression language, or how the expression language is used in axioms

Modeling Consideration!

• We have SubClass is-a built into the language
  • And we can infer SubClassOf axioms
• But part-of is not built in!
  • That is, we don't have a built-in theory of partonomy
    • Which is wise --- there are lots of kinds of partonomy
  • But we need it! Worms have parts!
• Does OWL have the expressive resources to handle partonomy
  • Can we define or characterize our own part relation

Simplest Considerations

• Some assumptions/desidera
  • Parts and wholes are individuals
    • That is, we are dealing with structured objects
  • has-part and part-of are inverses
    • And they are transitive
    • If A is part-of B, and B part-of C, then A is part-of C
      • Doesn't always hold!!
• Can we model this in OWL?

Basic OWL partonomy

ObjectProperty: has-part
ObjectProperty: part-of
              InverseOf: has-part
              Characteristics: Transitive

REMEMBER: Very incomplete!