Transcript Large-Scale Repositories of Highly Expressive Reusable

Foundation Technology
and
Lessons Learned
from
Community Interoperability Efforts
Prof. Richard Fikes
Knowledge Systems, AI Laboratory
Computer Science Department
Stanford University
3/27/06
In the Knowledge Is The Power

It’s not enough to be smart and clever

Knowledge is a fundamental enabler of intelligent behavior

Encoding knowledge requires extensive time & expertise

The challenge is to enable –

2

Rapid construction of large-scale knowledge bases

Knowledge encoding by large populations of domain experts

Customization of knowledge for specific tasks and methods
Address the challenge by developing –

Libraries of multi-use knowledge bases

Tools for assembling knowledge bases from multi-use modules

Interoperable knowledge servers and tools

Methods for encoding knowledge on Web pages
Ontologies as KB Building Blocks

Typical KR languages are domain-independent
E.g, predicate calculus and frame languages


3
Do not provide a domain-specific vocabulary
KB construction therefore involves two steps:

Define vocabulary to be used to represent the knowledge

Represent the knowledge using the defined vocabulary

Vocabulary is reused in many applications

Therefore, ontologies are the major form of multi-use knowledge
Impediments to Sharing and Reuse
4

Heterogeneous representation formalisms

Lack of knowledge-level communication conventions

Domain model mismatches
DARPA Knowledge Sharing Effort
 Knowledge

Sponsored by DARPA, NSF, and AFOSR

Launched a knowledge standards effort
A
rebellion against standards

KR&R conference – 1991

“The KIF of Death” – 1991
 Effort

5
Standards Workshop – March 1990
changed to a “Knowledge Sharing Effort”
Funding provided by DARPA for several years
Impediments to Sharing and Reuse
6

Heterogeneous representation formalisms

Lack of knowledge-level communication conventions

Domain model mismatches
DARPA Knowledge Sharing Effort

Heterogeneous representation formalisms

Interlingua WG
> Developed a first-order logic interlingua for exchanging knowledge
– KIF (Knowledge Interchange Format)

Knowledge Representation System Specification (KRSS) WG
> Developed a consensus-standard description logic
7

Lack of knowledge-level communication conventions

Domain model mismatches
Interlingua for Reusable KBs
Language 1
Language 2
...
KIF
KB Library
8
Language n
DARPA Knowledge Sharing Effort

Heterogeneous representation formalisms

Interlingua WG
> Developed an FOL interlingua for exchanging knowledge (KIF)

Knowledge Representation System Specification (KRSS) WG
> Developed a consensus-standard description logic

Lack of knowledge-level communication conventions

External Interfaces WG
> Developed knowledge-level communication protocols
– KQML (Knowledge Query and Manipulation Language)
– OKBC (Open Knowledge Base Connectivity)

9
Domain model mismatches
DARPA Knowledge Sharing Effort

Heterogeneous representation formalisms

Interlingua WG
> Developed an FOL interlingua for exchanging knowledge (KIF)

Knowledge Representation System Specification (KRSS) WG
> Developed a consensus-standard description logic

Lack of communication conventions

External Interfaces WG
> Developed knowledge-level communication protocols (KQML, OKBC)

Model mismatches at the knowledge level

Shared, Reusable Knowledge Bases WG
> Developed the concept of an ontology
– “A specification of a conceptualization” (1993)
> Developed an ontology representation language and library
– Ontolingua
1
Interlinguas for Reusable KBs
Language 1
Language 2
...
Language n
KIF
Ontology
Library

Knowledge Interchange Format (KIF)


1
First-order logic with an Ascii syntax
Ontolingua – An interlingua for ontologies

Monotonic frame language augmented by KIF axioms

Frame language defined as an ontology represented in KIF

Evolved into the OKBC knowledge model (as used in Protégé)
Ontolingua – A World Wide Web Service

A first generation ontology development environment (Dec. 94)
Usable via a standard Web viewer (ontolingua.stanford.edu)

Representation languages that facilitate widespread usability


Internal -> Knowledge Interchange Format (KIF)
> Frame language ontology
> OKBC programmatic interface

External -> Frame language augmented with KIF axioms and definitions
> Fully cross-referenced html documents

On-line library of multi-use ontologies


A “publication medium” for ontologies
Ontology editor and browser

Assemble and extend library ontologies
 Develop collaboratively
1
Example Definitions

LengthDimension
instanceOf: PhysicalDimension
standardUnit: Meter

LengthUnitOfMeasure
subclassOf: UnitOfMeasure
*unitDimension: LengthDimension

Meter
instanceOf: LengthUnitOfMeasure

Kilometer
instanceOf: LengthUnitOfMeasure
============================================================
“If q is a physical quantity on the Length dimension, then the magnitude
of q in Kilometers is the magnitude of q in meters divided by 1000.”
(forall ((q PhysicalQuantity))
(implies (quantityDimension q Length)
(Magnitude q Kilometer (/ (Magnitude q Meter) 1000))))
1
Ontologies:
What Are They?
Where's The Research?
Richard Fikes, Chair
Professor, Computer Science
Knowledge Systems Laboratory
Stanford University
Mark Fox
Nicola Guarino
Professor, Industrial Engineering
Research Scientist
Enterprise Integration Laboratory
Institute for Systems Science
University of Toronto
and Biomedical Engineering
of the Italian National Research Council
William Mark
Director, Architecture Laboratory
National Semiconductor Corporation
11/5/96
But, What Is An Ontology?
15
Knowledge Systems Laboratory, Stanford University
KR Language Components

A logical formalism



Syntax for wffs
Vocabulary of logical symbols (e.g., AND, OR, NOT, implies, iff)
Interpretation semantics for the logical symbols
E.g., “(implies A B)” is true if and only if B is true or A is false.

An ontology

Vocabulary of non-logical symbols
> Relations, functions, constants



Definitions of non-logical symbols
???
A proof theory

Specification of the reasoning steps that are logically sound
E.g., From “(implies S1 S2)” and “S1”, conclude “S2”.
1
Ontologies in Representation Languages

KIF (Knowledge Interchange Format)

Logical formalism:
> ASCII S-expression syntax for WFFs
> First-order logic semantics

Ontologies:
Numbers, lists, sets, …

OKBC (Open Knowledge Base Connectivity)

KIF plus a “frame language” ontology
Subclass-Of, Instance-Of , Value-Type, Slot-Cardinality, …

OWL (Ontology Web Language)

RDF-S plus a description logic ontology
subclassOf, inverseOf, TransitiveProperty, Restriction, …
1
Classical Definitions Are Not Enough

Definitions provide equivalent expressions
(forall (x1 … xn) (iff (R x1 … xn) x1,…,xn)
E.g., (forall (x) (iff (bachelor x)
(and (man x) (not (married x))))

Defined symbols can be eliminated by replacement


KB is then expressed in terms of undefined symbols


Defined symbols are “non-primitive” symbols
Undefined symbols are “primitive” symbols
Undefined symbols are given “meaning” by axioms
E.g., (forall

1
(x y)
(not (and (on x y) (on y x)))
Thus, ontologies must have both definitions and axioms
Object-Oriented Languages Too Restrictive

Frames and description logics are popular ontology languages

They support definitional axioms of the form:

(forall ((x R)) (and … (P x) …))

(forall ((x R) y) (and … (implies (S y x) P y)) … )

(forall ((x R)) (and … (exists (y)S y x)) … )
…

{subclass}
They do not support –

N-ary relations and functions

Standard properties of relations and functions
E.g., transitive, symmetric

…
1
Partial sufficient conditions
E.g., (forall (x) (implies (> x 0) (R x))
{value type}
{slot cardinality}
What Axioms Can Be In An Ontology?
 No

“Definitional axioms” and

“Contingent facts”
 No
2
apparent distinction between –
rationale for excluding any axiom that is –

Not a tautology

Satisfied by the intended interpretation in the
conceptualization being represented
KR Language Components

A knowledge representation language consists of:

A logical formalism

An ontology
> Set of non-logical symbols defined or restricted
> Definitions of non-primitive non-logical symbols
> Axioms restricting the interpretation of primitive non-logical symbols


2
A proof theory
Ontologies are distinguished –

Not by their form, but

By the role they play in representing knowledge
What’s Special About Ontologies?

Don’t change during problem solving

2
Are particularly suited for “compiling” into tools

Intended to support multiple tasks and methods

Emphasis on properties that hold in all situations

Emphasis on classes rather than individuals

Need to satisfy a community of use

Emphasis on collaborative development

Emphasis on translation to multiple logical formalisms
Magnitude of Physical Quantities

Function Magnitude
“The magnitude of a physical quantity in a given unit of measure”
 Defining axioms:

“If (Magnitude q u m) is true, then q is a physical quantity, u is a unit of measure, m is
a real number, and q and u are of the same physical dimension”
(forall (q u m) (implies (Magnitude q u m)
(and (PhysicalQuantity q)
(UnitOfMeasure u)
(RealNumber m)
(quantityDimension q (unitDimension u)))))
“Quantities q1 and q2 are equal if and only if they are of the same physical dimension
and their magnitudes are equal with respect to a unit of that dimension.”
(forall ((q1 PhysicalQuantity) (q2 PhysicalQuantity) qd1 qd2 su)
(implies (and (quantityDimension q1 qd1)
(quantityDimension q2 qd2)
(standardUnit qd1 su))
(iff (= q1 q2)
(and (= qd1 qd2) (Magnitude q1 su (Magnitude q2 su))))))
2
Expressivity Demands Will Continue To Grow

Typicality conditions need to be included in ontologies
PhoneNumber(p,n) & CallFrom(c,n) & Typ(c)  callBy(c,p)
StolenPhone(n) & CallFrom(c,n)  Typ(c)

Enables reasoners to draw provisional conclusions by hypothesizing typicality
Given: PhoneNumber(Ramazi,703-659-2317)
CallFrom(c1,703-659-2317)
Hypothesize (i.e., assume): Typ(c1)
Conclude: CallBy(c1,Ramazi)
and inform user of assumptions made

2
In general, representations of uncertainty need to be in our ontologies
Interoperable Knowledge Representation
for Intelligence Support (IKRIS)
A challenge problem project on knowledge representation
sponsored by U.S. intelligence agencies
Technical Team Leaders
Prof. Richard FikesDr. Christopher Welty
Knowledge Structures Group
Artificial Intelligence Laboratory (KSL)
Stanford UniversityIBM Corporation
Knowledge Systems,
T. J. Watson Research Center
Northeast Regional Research Center Leaders
Dr. Brant Cheikes (MITRE)
Dr. Mark Maybury (MITRE)
Government Champions
Steve Cook (NSA)Jean-Michel Pomarede (CIA)
John Donelan (CIA)John Walker (NSA)
2/7/06
Challenge Problems for the IC

DTO (Disruptive Technology Office) funds challenge problem projects

Focus is on problems that require collaboration to solve

DTO recognizes knowledge representation (KR) as a critical technology

IKRIS is addressing two KR challenges

Enabling interoperability of KR technologies
> Developed by multiple contractors
> Designed to perform different tasks

Interoperable representations of scenarios and contextualized knowledge
> To support automated analytical reasoning about alternative hypotheses
2
Hypothesis Modeling and Analysis

Tools for modeling and analyzing alternative hypothetical scenarios
What
happened?
What’s the current
situation?
…
What’s going
to happen?

Models enable automated reasoning to accelerate and deepen analysis


Requires sophisticated knowledge representation technology

2
Consistency and plausibility checking, deductive question-answering,
hypothesis generation, …
Actions, events, “abnormal” cases, alternatives, open-ended domains, …
Interoperable KR Technology


No one representation language is suitable for all purposes

Technology development necessarily involves exploring alternatives

Differing tasks require differing representation languages
So, modules using differing KR languages need to be interoperable


Requires enabling modules to use each other’s knowledge
The IKRIS approach to achieving interoperability –

Select and refine a standard knowledge interchange language
> Called IKRIS Knowledge Language (IKL)


2
Develop translators to and from IKL
Each system module will then –

Use its own KR language internally

Use IKL for inter-module communication

Translate knowledge to and from IKL as needed
IKRIS Organization

Prime Contractor – MITRE, Brant Cheikes and Mark Maybury

Technical Team Leads – Fikes (Stanford KSL) and Welty (IBM Watson)

Working Groups

Interoperability – Pat Hayes, University of West Florida
Chris Menzel, Michael Witbrock, John Sowa, Bill Andersen, Deb McGuinness, …

Scenarios – Jerry Hobbs, Information Sciences Institute
Michael Gruninger, Drew McDermott, David Martin, Selmer Bringsjord, …

Contexts – Selene Makarios, Stanford KSL
Danny Bobrow, Valeria de Paiva, Charles Klein, David Israel, …

Evaluation – Dave Thurman, Battelle Memorial Institute

Technology Transfer – Paula Cowley, Pacific Northwest National Laboratory

Translation technology and example translators – Stanford KSL

Government Champions –
Steve Cook, John Donelan, Jean-Michel Pomarede, John Walker
2
IKRIS Project Schedule

Preparation – January - April, 2005

Kickoff Meeting – April 2005


Established working groups and their charters

Developed work plan and began work in each group
Working groups – April 2005 through April 2006


Evaluation – January through September 2006



Iterative evaluation of workshop results
Second face-to-face workshop – April 2006

Finalize and coordinate results of working groups

Finalize plans for technology transition and for completing evaluation
Technology transition – April through September 2006

3
Producing results and planning technology transfer
Initiation of planned transition activities
FOL Knowledge Interchange Languages



3
KIF (Knowledge Interchange Format)

ASCII Lisp-style syntax

No formal model theory

Pre-WWW/XML/Unicode

Included a set theory, definition language, etc.

Subset became de facto AI/KR standard

Subset developed as a proposed ISO standard
CL (Common Logic)

Based on KIF

Formal model theory

Abstract syntax

“Web savvy”

In final stages of becoming an ISO standard
IKL (IKRIS Knowledge Language)

Variant of CL

Extensions include propositions
CLIF Syntax for IKL

Designed for use on an open network

Names are made globally unique by –
> Including a URI as part of the name
> Using the XML namespace conventions to abbreviate names

Universal quantifiers can be restricted by a unary predicate
E.g., “All humans own a car.”
(forall ((x isHuman)) (exists ((y Car)) (Owns x y)))

Existential quantifiers can be restricted by a number
E.g., “All humans have as parts 10 toes.”
(forall ((x isHuman))
(exists 10 (y) (and (Toe y) (PartOf y x))))
3
Examples of CL/IKL Expressivity

Relations and functions are in the universe of discourse
E.g.,

(owl:inverseOf parent child)
A relation or function can be represented by a term
E.g.,
x)))
(forall (x y r) (iff (r x y) ((owl:inverseOf r) y
Given the above axiom,
((owl:inverseOf Married) Uther Ygrain)
is equivalent to –
(Married Ygrain Uther)

A unary relation could be allowed to take multiple arguments

So that, e.g.,
(isHuman Fred Bill Mary)
abbreviates
3
(and (isHuman Fred) (isHuman Bill) (isHuman Mary))
Examples of CL/IKL Expressivity

A unary relation could be allowed to take multiple arguments

So that, e.g., (isHuman Fred Bill Mary)
abbreviates
(and (isHuman Fred) (isHuman Bill) (isHuman Mary))

We might call such relations “Predicative”
E.g., assert (Predicative isHuman)

What it means to be Predicative could be axiomatized as follows –
(forall (r) (if (Predicative r)
(forall (x y z) (iff (r x y z)
(and (r x) (r y) (r z))))))

Predicative itself could be Predicative –
(Predicative Predicative)
allowing such abbreviations as
(Predicative isHuman isAnimal isFish)
3
Examples of CL/IKL Expressivity

Sequence names


Allows a sentence to stand for an infinite number of sentences, each
obtained by replacing each sequence name by a finite sequence of names
A sequence name is any constant beginning with “…”
E.g., the general axiom for Predicative is as follows:
(forall (r) (if (Predicative r)
(forall (x y ...) (iff (r x y ...)
(and (r x) (r y ...))))))

Function “list” and relation “isList” are predefined as follows:
(forall (...) (isList (list ...)))
3
Extending CL to Include Propositions

Goal: Support representation of contextualized and modal knowledge

Achieved by making propositions first-class entities in IKL
> Refer to them by name, quantify over them, have relations between them and
other entities, define functions that apply to them, …

The operator that is used to denote propositions

that takes a sentence as an argument
E.g., (that (Married Ygrain Uther))

A that expression denotes the proposition expressed by its argument
E.g., (that (Married Ygrain Uther))
is a name, denoting the proposition that Ygarin and Uther are married

Issue: When are two propositions equivalent?
E.g., does (and a b) name the same proposition as (and b a)?

IKL provides a propositional equivalence relation, but does not build it in
3
6
Interoperable Scenarios

IKRIS is addressing two KR challenges

Enabling interoperability of KR technologies
> Developed by multiple contractors
> Designed to perform different tasks

Interoperable representations of scenarios and contextualized knowledge
> To support automated analytical reasoning about alternative hypotheses

Developing an interoperable representation for processes

Includes –
> Time points, time intervals, durations, clock time, and calendar dates
> Events and relationships that overlap in time and interact
> Process constructs, preconditions, states, etc.
3
An Interlingua for Processes
SWSL/
FLOWS
PSL
OWL-S
inter-theory
SPARK
3
ResearchCyc
The Scenarios Ontology


The Scenarios Working Group is producing an IKL ontology

Inter-theory vocabulary

Bridging axioms to other vocabularies

Trigger axioms for making optional representational commitments
The inter-theory vocabulary includes –

The OWL time ontology
> Terminology for clock time, calendars, intervals, points, etc.

Terms such as the following to describe processes:
> Eventuality
> Precondition
> Event
> EventType
> EventualityType
> PreconditionToken
> State
> FluentFor
> Subevent
> Effect
> StateType
3
The Scenarios Ontology

Example bridging axioms to Cyc for Event and EventType:

“For every EventType x, there is a Cyc subclass of cyc:Event that has the
same instances as x”
(forall ((x EventType)))
(exists (y) (and (cyc:genls y cyc:Event)
(forall (e) (iff (cyc:isa e y)
(instanceOf e x)))))))

“For every subclass y of Cyc:Event, there is an EventType that has the
same instances as y”
(forall (y) (if (cyc:genls y cyc:Event)
(exists (x) (and (EventType x)
(forall (e)
(iff (cyc:isa e y)
(instanceOf e x)))))))
4
The Scenarios Ontology


Example bridging axioms to Cyc for Event and EventType:

“For every EventType x, there is a Cyc subclass of cyc:Event that has the
same instances as x”

“For every subclass y of Cyc:Event, there is an EventType that has the
same instances as y”
In Cyc, EventTypes are classes and classes are individuals

The inter-theory is neutral on the issue

A commitment can be made on this issue using a triggering axioms
“If the TypesAreClasses trigger is true, EventTypes and the subclasses of
Cyc:Events are equivalent”
(forall (x) (if (TypesAreClasses)
(iff (cyc:genls x cyc:Event) (EventType x))))
4
Interoperable Contextualized Knowledge

IKRIS is addressing two KR challenges

Enabling interoperability of KR technologies
> Developed by multiple contractors
> Designed to perform different tasks

Interoperable representations of scenarios and contextualized knowledge
> To support automated analytical reasoning about alternative hypotheses
4
Contextualized Knowledge is Pervasive

The circumstances surrounding a specific activity
E.g., In this conversation, ‘the suspect’ refers to Faris.

A published document
E.g., Based on the schedule, the Holland Queen will arrive in Boston sometime on April
29, and depart there sometime on May 1.

An intelligence report
E.g., Pakes is listed, according to a certain source, on the crew roster of the Holland
Queen.

A database
E.g., Pakes is assumed, based on certain records, to not be a citizen of USA.

An assumption
E.g., Pakes’s presence on board the Holland Queen is assumed to be typical (i.e. he
does not behave abnormally).

A set of beliefs
E.g., In the belief system of Abu Musab al Zarqawi, democracy is evil.
4
Interoperable Contextualized Knowledge

IKRIS is producing –

A context logic with a formal model theory
> Called IKRIS Context Logic (ICL)

Recommended ways of using the logic for IC applications
E.g., to represent alternative hypothetical scenarios
4

Methodology for translating into and out of IKL

Methodology for automated reasoning
Context Logic

In McCarthy’s context logic –

Contexts are primitive entities

Propositions can be asserted with respect to a context
> (ist c ) means that proposition  is true in context c
E.g., (ist CM (forall (x) (implies (P x) (G x)))); (ist C0 (P Fred))

How can automated reasoning be done with ist sentences?
E.g., assert (= CM C0) and derive (ist C0 (G Fred))

Contextualize constants rather than sentences

Constants in ist sentences are interpreted with respect to the context
E.g., Fred in (ist C0 (P Fred)) is interpreted with respect to C0

Replace each constant with a function of the context and the constant
E.g., { (forall (x) (implies (P (iso CM x)) (G (iso CM x))));
(P (iso C0 Fred)) }

4
Use a first-order reasoner to make deductions
Knowledge Associates for Novel Intelligence
KANI’s Hypothesis Graph
N1
S1: There will be a coordinated event.
S2: The event will occur on April 30.
S3: Pakes is a participant.
S4: Ramazi is a participant.
S5: Goba is a participant.
…
N2 S8: The event is a face-to-face meeting.
N3
S9: The event is at Select
Gourmet Foods.
New
hypothesi
s added
by the
analyst
Pacific Northwest Division
N4 S10: The event is in Atlanta.
N5 S11: Pakes is in Boston on April 30.
46
Knowledge Associates for Novel Intelligence
Conflict Detected by KANI
N1
S1: There will be a coordinated event.
S2: The event will occur on April 30.
S3: Pakes is a participant.
S4: Ramazi is a participant.
S5: Goba is a participant.
…
N2 S8: The event is a face-to-face meeting.
N3
S9: The event is at Select
Gourmet Foods.
N4 S10: The event is in Atlanta.
N5 S11: Pakes is in Boston on April 30.
Pacific Northwest Division
47
Knowledge Associates for Novel Intelligence
Tools for Helping Resolve Inconsistencies
N1
Event will not
occur on April 30
N1.1 ~S2,S3
N2.1
N3.1
S8
N5.1
N2.2
N3.2
S9
N4.1
N1.2 S2,~S3
S10
S11
N5.2
Pakes is
not a
participant
N3.3
S10
S11
N1.3
N2.3 ~S8
S8
S9
N4.2
S1,S4,S5,…
S9
N4.3
N5.3
S2,S3
Event is
N2 S8
not a
face-toface
N3.3 S9
meeting
S10
S11
N4.4 ~S10 N4
Event is
not in
Atlanta
N5.5
Pakes is
not in
Boston on
April 30
Pacific Northwest Division
48
S10
~S11
Evaluation and Tech Transfer

Evaluation

Goals:
> Demonstrate the practical usability of results on IC-relevant problems
> Provide functionality goals, scoping, and feedback for results

Evaluation will be informal using sample IC tasks

Tests will include –
> Round trip translations into and out of IKL
> Inter-system knowledge exchange using IKL.

4
Tech Transfer

Goal: Transition results into DTO programs and the IC at large

Producing “showcase” presentations of results for transition audiences

Being advised and facilitated by our government champions and MITRE
IKRIS Summary

IKRIS is enabling progress to be made on significant KR&R problems

We are addressing two KR challenges relevant to the IC

Enabling interoperability of KR technologies
> Developed by multiple contractors
> Designed to perform different tasks

Interoperable representations of scenarios and contextualized knowledge
> To support automated analytical reasoning about alternative hypotheses

Initial versions of the technical results have been completed

For more information, check out the IKRIS Web site

http://nrrc.mitre.org/NRRC/ikris.htm
5
0
Biggest Challenge: Translators
Language 1
Language 2
...
Language n
IKL
Ontology
Library

Translating into a less expressive language is necessarily incomplete

Translating into the ontology of the target language can be arbitrarily difficult
5
1