Transcript Review - KDD - Kansas State University

Lecture 18 of 42
Knowledge Representation Continued: KE,
Inheritance, & Representing Events over Time
Discussion: Structure Elicitation, Event Calculus
William H. Hsu
Department of Computing and Information Sciences, KSU
KSOL course page: http://snipurl.com/v9v3
Course web site: http://www.kddresearch.org/Courses/CIS730
Instructor home page: http://www.cis.ksu.edu/~bhsu
Reading for Next Class:
Section 10.4 – 10.9, p. 341 – 362, Russell & Norvig 2nd edition
IM: http://en.wikipedia.org/wiki/Information_management
Event calculus: http://en.wikipedia.org/wiki/Event_calculus
Protégé-OWL tutorials: http://bit.ly/3rM1pB, http://bit.ly/18pMgR
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Lecture Outline
 Reading for Next Class: Sections 10.4 – 10.9 (p. 341 – 362), R&N 2e
 Last Class: Knowledge Engineering (KE), Protocol Analysis, Fluents
 Ontology engineering: defining classes/concepts, slots
 Concept elicitation techniques
 Unstructured
 Structured
 Protocol analysis (“thinking aloud”)
 Today: Frames, Semantic Nets, Inheritance; Event & Fluent Calculi
 Structure elicitation
 Computational information and knowledge management (CIKM)
 Representing time, events
 Situation calculus
 Event calculus
 Fluent calculus
 Brief tutorial: OWL ontologies in Protégé (http://bit.ly/18pMgR)
 Coming Week: CIKM, Logical KR Concluded; Classical Planning
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Acknowledgements
Natasha Noy
Senior Research Scientist
BMIR
Samson
Tu
Senior Research Scientist
BMIR
Georghe Tecuci
Professor of Computer Science
Director, Learning Agents Center
George Mason University
Milos Hauskrecht
© 2001 G. Tecuci
George Mason University
http://bit.ly/3tUACW
http://lalab.gmu.edu/cs785/
http://lac.gmu.edu
© 2005 M. Hauskrecht
University of Pittsburgh
CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos
Associate Professor of
Computer Science
University of Pittsburgh
Holger Knublauch
Vice President, TopQuadrant
previously Research Fellow,
Stanford Medical Informatics & Univ.
of Manchester
CIS 530 / 730
Artificial Intelligence
© 2005 N. Noy & S. Tu
Stanford Center for Biomedical
Informatics Research
http://bit.ly/jwOf3
http://bit.ly/2NBeCI
http://bmir.stanford.edu
Lecture 18 of 42
© 2004 H. Knublauch
TopQuadrant, Inc.
(formerly University of Manchester)
http://www.knublauch.com
Computing & Information Sciences
Kansas State University
Decision Problems:
Review
Undecidable
duals
α  LVALIDC iff
¬α  LSAT
LH: Halting
problem
Co-RE (REC)
LVALID
LVALID
α
closure
under
complem.
L  L
α ⊢RES ?
LSAT
LSAT
LD: Diagonal
problem
LD
Recursive
Languages
(REC)
Y
N
✓
✗
LH
Recursive Enumerable
Languages
(RE)
Semi-decidable
duals:
α  LVALID iff
¬α  LSATC
CIS 530 / 730
Artificial Intelligence
Universe of Decision Problems
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Concepts/Classes:
Review
 “Concept” and “Class” are used synonymously
 Class: concept in the domain
 wines
 wineries
 red wines
Top
level
Middle
level
Bottom
level
 Collection of elements with similar properties
 Instances of classes
 Particular glass of California wine
Adapted from slides © 2005 N. Noy & S. Tu
Stanford Center for Biomedical Informatics Research
http://bmir.stanford.edu
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Slots/Attributes/Relations:
Review
 Slots in class definition C



Describe attributes of instances of C
Describe relationships to other instances
e.g., each wine will have color, sugar content, producer, etc.
 Property constraints (facets): describe/limit possible values for slot
Slots & facets for Concept/Class Wine
Adapted from slides © 2005 N. Noy & S. Tu
Stanford Center for Biomedical Informatics Research
http://bmir.stanford.edu
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Protégé – Default Interface:
Review
Tabs partition
different work areas
Buttons and widgets
for manipulating slots
Area for manipulating
the class hierarchy
Downloads, primer, documentation:
http://protege.stanford.edu
Adapted from slides © 2005 N. Noy & S. Tu
Stanford Center for Biomedical Informatics Research
http://bmir.stanford.edu
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Knowledge Engineering:
Review
A scenario for manual knowledge acquisition
Elicitation of expert’s conception of a domain
Elicitation based on the personal construct theory
Knowledge acquisition for role-limiting methods
Advanced approaches to KB and agent development
© 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
How Agents Are Built:
Review
Intelligent Agent
Domain
Expert
Knowledge
Engineer
Inference Engine
Dialog
Programming
Knowledge Base
Results
A knowledge engineer attempts to understand how a subject matter expert
reasons and solves problems and then encodes the acquired expertise into the
agent's knowledge base.
The expert analyzes the solutions generated by the agent
(and often the knowledge base itself) to identify errors, and
the knowledge engineer corrects the knowledge base.
© 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Agent Development Process:
Review
Defining problem to solve and system to be built:
requirements specification
Understanding the expertise domain
Feedback
loops
among all
phases
Choosing or building an agent building tool:
Inference engine and representation formalism
Development of the object ontology
Development of problem solving rules or methods
Refinement of the knowledge base
Adapted from slide © 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Elicitation Methodology:
Review
(based primarily on Gammack, 1987)
1. Concept elicitation: methods
(elicit concepts of domain, i.e. agreed-upon vocabulary)
2. Structure elicitation: card-sort method
(elicit some structure for concepts)
3. Structure representation
(formally represent structure in semantic network)
4. Transformation of representation
(transform representation to be used for some desired purpose)
© 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Structure Elicitation:
Card-Sort Method
The Card-Sort Method
(elicit the hierarchical organization of the concepts)
• Type the concepts on small individual index cards.
• Ask the expert to group together the related concepts into as many
small groups as possible.
• Ask the expert to label each of the groups.
• Ask the expert to combine the groups into slightly larger groups, and
to label them.
The result will be a hierarchical organization of the concepts
© 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Card-Sort Method:
Illustration
Satchwell
Time Switch
Electric Time Controls
Programmer
Thermostat
Set Point
Thermostat
Rotary Control Knob
Gas Control Valve
Gas Control
Control
Electricity
Solenoid
Electrical System
Electrical Supply
Electrical Supply
Electrical Contact
Electrical Components
Fuse
Pump
Mechanical Components
Motorized Valve
Part of the hierarchy of concepts from the card-sort method
Adapted from slide © 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Card-Sort Method:
Properties
Strengths
• gives clusters of concepts and hierarchical
organization
• splits large domains into manageable sub-areas
• easy to do and widely applicable
Weaknesses
• incomplete and unguided
• strict hierarchy is usually too restrictive
Adapted from slide © 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Structure Representation [1]:
Definition
Represents the acquired concepts into a semantic network and
acquires additional structural knowledge:
• Ask the expert to sort the concepts by considering each concept
C as a reference, and identifying those related to it.
• Ask the expert to order the concepts related to C along a scale
from 0 to 100, marked at the side of a table. The values are read
off the scale and entered in a data matrix.
• Generate a network from the matrix, where the nodes are the
concepts and the weighted links represent proximities.
• For each pair of concepts identified as related, ask the expert
what that relationship is.
© 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Structure Representation [2]:
Illustration
Domestic
Plumbing
System
Pipe
Water
Supply
Flow
Header
Tank
Water
Expansion
Thermostat
Radiator
Control
Valve
Heat
Boiler
Gas
Control
Valve
M ain
Gas
Supply
Electrical
Supply
Electrical
Contact
Feedback
Loop
Thermal
Circuit
Pilot
Light
Time
Switch
Gravity
Radiator
Primary
Circuit
Air
Hot
Water
Cylinder
Immersion
Heater
M otorized
Valve
Adapted from slide © 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Structure Representation [3]:
Properties
Strengths
• gives information on the domain structure in the
form of a network
• shows which links are likely to be meaningful
• organizes the elicitation of semantic relationships
Weaknesses
• results depend on various parameter settings
• requires more time from the expert
• combinatorial explosion limits its applicability
Adapted from slide © 2001 G. Tecuci, George Mason University
CS 785 Knowledge Acquisition and Problem-Solving http://lalab.gmu.edu/cs785/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Hierarchy and Taxonomy
© 2005 M. Hauskrecht, Univ. of Pittsburgh CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos/courses/cs2710/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Graphical Representation of
Inheritance
© 2005 M. Hauskrecht, Univ. of Pittsburgh CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos/courses/cs2710/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Inheritance Networks [1]:
Trees with Strict Inheritance
Based on slide
© 2005 M. Hauskrecht, Univ. of Pittsburgh CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos/courses/cs2710/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Inheritance Networks [2]:
Lattices with Strict Inheritance
Based on slide
© 2005 M. Hauskrecht, Univ. of Pittsburgh CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos/courses/cs2710/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Inheritance Networks [3]:
Defeasible Inheritance
Based on slide
© 2005 M. Hauskrecht, Univ. of Pittsburgh CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos/courses/cs2710/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Problems with
Shortest Path
Based on slide
© 2005 M. Hauskrecht, Univ. of Pittsburgh CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos/courses/cs2710/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Formal:
Inheritance Hierarchy
© 2005 M. Hauskrecht, Univ. of Pittsburgh CS 2740 Knowledge Representation
http://www.cs.pitt.edu/~milos/courses/cs2710/
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
OWL Plug-in Architecture
OWL GUI Plugins
OWL
Extension APIs
(SWRL Editors, ezOWL,
OWLViz, Wizards, etc.)
Protégé OWL GUI
Protégé OWL API
(Logical class defn’s,
restrictions, etc.)
Jena API
(Expression Editor,
Conditions Widget, etc.)
OWL Plugin
(SWRL, OWL-S, etc.)
Protégé GUI
Protégé API
(Tabs, Widgets, Menus)
(Classes, properties,
individuals, etc.)
OWL File
Storage
Protégé Core System
(Parsing, Reasoning)
DB
Storage
Adapted from slide © 2004 H. Knublauch (formerly University of Manchester)
http://www.knublauch.com
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Tourism Semantic Web
OWL
Metadata
(Individuals)
Tourism Ontology
OWL
Metadata
(Individuals)
Destination
Activity
Accomodation
OWL
Metadata
(Individuals)
OWL
Metadata
(Individuals)
Web Services
© 2004 H. Knublauch (formerly University of Manchester)
http://www.knublauch.com
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Actions, Situations, Time & Events [1]:
Situation Calculus Revisited
Situation
calculus
Figure 10.2
p. 329 R&N 2e
 Axioms: Truth of Predicate P
 Fully specify situations where P
true
  biconditional (, iff)
 Original Predicates
 Describe state of world
 Each augmented with situation
argument s
Adapted from material © 2003 – 2004 S. Russell & P. Norvig.
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Actions, Situations, Time & Events [2]:
Event Calculus
Event calculus
Figure 10.3
p. 336 R&N 2e
Figure © 2003 S. Russell & P. Norvig.
 Domain-Independent Axioms
 Domain-Dependent Axioms
 Still Need to Solve Frame Problem (by Circumscription)
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Actions, Situations, Time & Events [3]:
Fluent Calculus
State fluents
Figure 10.6
p. 340 R&N 2e
Adams
Jefferson
Washington
Figure © 2003 S. Russell & P. Norvig.
 Fluent: Condition (Predicate) That Can Change Over Time (e.g., On)
 Fluent Calculus: Variant of Situation Calculus
 Defaults
 ∘ (concatenation) of fluents with state
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
CIKM:
Review
 Information Management
 Data acquisition: instrumentation, collection, polling, elicitation
 Data and information integration: combining multiple sources
 May be heterogeneous (different in quality, format, rate, etc.)
 Underlying formats, properties may correspond to different ontologies
 Ontology mappings (functions to convert between ontologies) needed
 Data transformation: preparation for reasoning, learning
 Preprocessing
 Cleaning
 Includes knowledge capture: assimilation from various sources
 Knowledge Management
 Term used most often in business administration, management science
 Related to IM, but capability and process-centered
 Focus on learning and KA, organization theory, decision theory
 Discussion, apprenticeship, forums, libraries, training/mentoring
 Modern theory: KBs, Expert Systems, Decision Support Systems
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Terminology
 Knowledge Engineering (KE): Process of KR Design, Acquisition
 Knowledge
 What agents possess (epistemology) that lets them reason
 Basis for rational cognition, action
 Knowledge gain (acquisition, learning): improvement in problem solving
 Knowledge level (vs. symbol level): level at which agents reason
 Semantic network: inheritance and membership/containment relationships
 Knowledge elicitation: KA/KE process from human domain experts
 Protocol analysis: preparing, conducting, interpreting interview
 Less formal methods: subjective estimation & probabilities
 Fluents: Conditions (Predicates) That Can Change over Time
 Classes, nominals (objects / class instances): spatial, temporal extent
 Fluent calculus: situation calculus with defaults, ∘ (concatenation)
 Computational Information and Knowledge Management (CIKM)
 Data/info integration & transformation: collecting, preparing data
 Includes knowledge capture: assimilation from various sources
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University
Summary Points
 Last Class: Knowledge Engineering, Elicitation, Knowledge Rep.
 Elicitation
 Techniques: unstructured, structured, “think aloud” (protocol analysis)
 Stages: concept (last time), structure (today)
 Knowledge acquisition (KA)
 Information management, knowledge management defined
 KR: situation calculus and successor state axioms; fluents, intervals
 Today: KE, Ontologies Concluded; CIKM; Event and Fluent Calculi
 Structure elicitation
 From semantic networks to ontologies
 Information management
 Knowledge management
 Event calculus
 Fluent calculus
 Next Class: Defaults, Defeasible Reasoning; Planning Preview
 Coming Week: Planning (Section IV)
CIS 530 / 730
Artificial Intelligence
Lecture 18 of 42
Computing & Information Sciences
Kansas State University