Back to School Savings: Save up to 30% on print books and eBooks. No promo code needed.

Back to School Savings: Save up to 30%

Introduction to Knowledge Systems

1st Edition - June 1, 1995

Author: Mark Stefik

eBook ISBN:

9 7 8 - 0 - 0 8 - 0 5 0 9 1 6 - 7

Focusing on fundamental scientific and engineering issues, this book communicates the principles of building and using knowledge systems from the conceptual standpoint as well as… Read more

Image - Introduction to Knowledge Systems

Purchase Options

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Focusing on fundamental scientific and engineering issues, this book communicates the principles of building and using knowledge systems from the conceptual standpoint as well as the practical. Previous treatments of knowledge systems have focused on applications within a particular field, or on symbol-level representations, such as the use of frame and rule representations. Introduction to Knowledge Systems presents fundamentals of symbol-level representations including representations for time, space, uncertainty, and vagueness. It also compares the knowledge-level organizations for three common knowledge-intensive tasks: classification, configuration, and diagnosis.

The art of building knowledge systems incorporates computer science theory, programming practice, and psychology. The scope of this book is appropriately broad, ranging from the design of hierarchical search algorithms to techniques for acquiring the task-specific knowledge needed for successful applications.

Each chapter proceeds from concepts to applications, and closes with a brief tour of current research topics and open issues. Readers will come away with a solid foundation that will enable them to create real-world knowledge systems using whatever tools and programming languages are most current and appropriate.

Introduction to Knowledge Systems

by Mark Stefik

Introduction and Overview
The Story and This Book
Part I: Foundations
1. Symbol Systems

1.1 Symbols and Symbol Structures

1.1.1 What is a Symbol?

1.1.2 Designation

1.1.3 Causal Coupling

1.1.4 Cognitive and Document Perspectives of Symbols

1.1.5 Summary and Review

1.2 Semantics: The Meaning of Symbols

1.2.1 Model Theory and Proof Theory

1.2.2 Reductionist Approaches for Composing Meanings

1.2.3 Terminology for Graphs and Trees

1.2.4 Graphs and Symbol Structures

1.2.5 The Annotation Priniciple and Metalavel Notations

1.2.6 Different Kinds of Semantics

1.2.7 Summary and Review

1.3 Modeling: Dimensions of Representation

1.3.1 Fidelity and Precision

1.3.2 Abstractions and Implementations

1.3.3 Primitive and Derived Propositions

1.3.4 Explicit and Implicit Representations

1.3.5 Representation and Canonical Form

1.3.6 Using Multiple Representations

1.3.7 Representation and Parallel Processing

1.3.8 Space and Time Complexity

1.3.9 Structural Complexity

1.3.10 Summary and Review

1.4 Programs: Patterns, Simplicity, and Expressiveness

1.4.1 Using Rules to Manipulate Symbols

1.4.2 Treating Programs as Data

1.4.3 Manipulating Expressions for Different Purposes

1.4.4 Pattern Matching

1.4.5 Expressiveness, Defaults, and Epistemological Primitives

1.4.6 The Symbol Level and the Knowledge Level

1.4.7 Summary and Review

1.5 Quandaries and Open Issues

2. Search and Problem Solving

2.1 Comcepts of Search

2.1.1 Solution Spaces and Search Spaces

2.1.2 Terminology about Search Criteria

2.1.3 Representing Search Spaces as Trees

2.1.4 Preview of Search Methods

2.1.5 Summary and Review

2.2 Blind Search

2.2.1 Depth-First and Breadth-First Search

2.2.2 Top-Down and Bottom-Up Search: A Note on Terminology

2.2.3 Simple and Hierarchical Generate-and-Test

2.2.4 A Sample Knowledge System Using Hierarchical Generate-and-Test

2.2.5 Simple and Backtracking Constraint Satisfaction

2.2.6 Summary and Review

2.3 Directed Search

2.3.1 Simple Match

2.3.2 Means-End Analysis

2.3.3 Hierarchical Match and Skeletal Planning

2.3.4 Hill Climbing and Best-First Search

2.3.5 Shortest-Path Methods

2.3.6 A* and Related Methods

2.3.7 Summary and Review

2.4 Hierarchical Search

2.4.1 Two-Level Planning

2.4.2 Planning with Multiple Abstraction Levels

2.4.3 Planning with Imperfect Abstractions

2.4.4 Summary and Review

2.5 Quandaries and Open Issues

3. Knowledge and Software Engineering

3.1 Understanding Knowlegde Systems in Context

3.1.1 The Terminology of Knowledge Systems and Expertise

3.1.2 Knowledge Systems and Document Systems: Five Scenarios

3.1.3 Preview of Knowledge Acquisition Topics

3.1.4 Summary and Review

3.2 Formulating Expertise

3.2.1 Conducting Initial Interviews

3.2.2 Taking Protocols

3.2.3 Characterizing Search Spaces

3.2.4 Adapting Protocol Analysis for Knowledge Systems

3.2.5 Summary and Review

3.3 Collaboratively Articulating Work Practices

3.3.1 Variations in Processes for Interview and Analysis

3.3.2 Documenting Expertise

3.3.3 Engineering Software and Organizations

3.3.4 Summary and Review

3.4 Knowledge versus Complexity

3.4.1 MYCIN: Study of a Classic Knowledge System

3.4.2 The Knowledge Hypothesis and the Qualification Problem

3.4.3 Summary and Review

3.5 Quandaries and Open Issues

Part II: The Symbol Level
4. Systematic Representations: Representing Time, Space, Certainty, and Vagueness

4.1 Temporal Concepts

4.1.1 Timeline Representations

4.1.2 A Discrete Model of Transactions in the Balance of an Account

4.2 Continuous versus Discrete Temporal Models

4.3 Temporal Uncertainty and Constraint Reasoning

4.3.1 Partial Knowledge of Event Times

4.3.2 Arc Consistency and Endpoint Constraints

4.3.3 Time Maps and Scheduling Problems

4.3.4 The Interface between a Scheduler and a Temporal Database

4.4. Branching Time

4.5 Summary and Review

4.6 Open Issues and Quandaries

4.6.1 Related Research about Time Representations

5. Representing and Reasoning about Space

5.1 Spatial Concepts

5.2 Spatial Search

5.2.1 Simple Nearest-First Search

5.2.2 Problems with Uniform-Size Regions

5.2.3 Quadtree Nearest-First Search

5.2.4 Multi-Level Space Representations

5.3 Reasoning about Shape

5.4 The Piano Example: Using Multiple Representations of Space

5.4.1 Reasoning for the Piano Movers

5.4.2 Rendering a Piano

5.4.3 The Action of a Piano

5.5 Summary and Review

5.6 Open Issues and Quandaries

6. Representing and Reasoning about Uncertainty and Vagueness

6.1 Representing Uncertainty

6.1.1 Concepts about Uncertainty

6.1.2 The Certainty-Factor Approach

6.1.3 The Dempster-Shafer Approach

6.1.4 Probability Networks

6.1.5 Summary and Conclusions

6.2 Representing Vagueness

6.2.1 Basic Concepts of Fuzzy Sets

6.2.2 Fuzzy Reasoning

6.2.3 Summary and Conclusions

6.3 Open Issues and Quandaries

6.3.1 On Nonmonotonic Logics

6.3.2 Existential Inadequacies ian Representing the Unknown

Part III: The Knowledge Level

7. Classification

7.1 Introduction

7.1.1 Regularities and Cognitive Economies

7.2 Models for Classification Domains

7.2.1 A Computational Model of Classification

7.2.2 Model Variations and Phenomena

7.2.3 Pragmatics in Classification Systems

7.2.4 Summary and Review

7.3 Case Studies of Classification Systems

7.3.1 Classification in MYCIN

7.3.2 Classification in MORE

7.3.3 Classification in MOLE

7.3.4 Classification in MDX

7.3.5 Classification in PROSPECTOR

7.3.6 Summary and Review

7.4 Knowledge and Methods for Classification

7.4.1 Knowledge-Level and Symbol-Level Analysis of Classification Domains

7.4.2 MC-1: A Strawman Generate-and-Test Method

7.4.3 MC-2: Driving from Data to Plausible Candidates

7.4.4 MC-3: Solution-Driven Hierarchical Classification

7.4.5 MC-4: Data-Driven Hierarchical Classification

7.4.6 Method Variations for Classification

7.4.7 Summary and Review

7.5 Open Issues and Quandaries

8. Configuration

8.1 Introduction

8.1.1 Configuration Models and Configuration Tasks

8.1.2 Defining Configuration

8.2 Models for Configuration Domains

8.2.1 Computational Models of Configuration

8.2.2 Phenomena in Configuration Problems

8.2.3 Summary and Review

8.3 Case Studies of Configuration Systems

8.3.1 Configuration in XCON

8.3.2 Configuration in M1/MICON

8.3.3 Configuration in MYCIN's Therapy Task

8.3.4 Configuration in VT

8.3.5 Configuration in COSSACK

8.3.6 Summary and Review

8.4 Methods for Configuration Problems

8.4.1 Knowledge-Level and Symbol-Level Analysis of Configuration Domains

8.4.2 MCF-1: Expand and Arrange

8.4.3 MCF-2: Staged Subtasks with Look-Ahead

8.4.4 MCF-3: Propose and Revise

8.4.5 Summary and Review

8.5 Open Issues and Quandaries

9. Diagnosis and Troubleshooting

9.1 Introduction

9.1.1 Diagnosis and Troubleshooting Scenarios

9.1.2 Dimensions of Variation in Diagnostic Tasks

9.2 Models for Diagnosis Domains

9.2.1 Recognizing Abnormalities and Conflicts

9.2.2 Generating and Testing Hypotheses

9.2.3 Discriminating among Hypotheses

9.2.4 Summary and Review

9.3 Case Studied of Diagnosis and Troubleshooting Systems

9.3.1 Diagnosis in DARN

9.3.2 Diagnosis in INTERNIST

9.3.3 Diagnosis in CASNET/GLAUCOMA

9.3.4 Diagnosis in SOPHIE III

9.3.5 Diagnosis in GDE

9.3.6 Diagnosis in SHERLOCK

9.3.7 Diagnosis in XDE

9.3.8 Summary and Review

9.4 Knowledge and Methods for Diagnosis

9.4.1 Plan Models for Diagnosis

9.4.2 Classification Models for Diagnosis

9.4.3 Causal and Behavioral Models for Systems

9.4.4 Summary and Review

9.5 Open Issues and Quandaries

Appendix A: Annotatied Bibliographies by Chapter

Appendix B: Selected Solutions to Exercises