The Knowledge Frontier: Essays in the Representation of Knowledge

Knowledge representation is perhaps the most central problem confronting artificial intelligence. Expert systems need knowledge of their domain of expertise in order to function properly. Computer vlslOn systems need to know characteristics of what they are "seeing" in order to be able to fully interpret scenes. Natural language systems are invaluably aided by knowledge of the subject of the natural language discourse and knowledge of the participants in the discourse. Knowledge can guide learning systems towards better understanding and can aid problem solving systems in creating plans to solve various problems. Applications such as intelligent tutoring. computer-aided VLSI design. game playing. automatic programming. medical reasoning. diagnosis in various domains. and speech recogOltlOn. to name a few. are all currently experimenting with knowledge-based approaches. The problem of knowledge representation breaks down into several subsidiary problems including what knowledge to represent in a particular application. how to extract or create that knowledge. how to represent the knowledge efficiently and effectively. how to implement the knowledge representation scheme chosen. how to modify the knowledge in the face of a changing world. how to reason with the knowledge. and how tc use the knowledge appropriately in the creation of the application solution. This volume contains an elaboration of many of these basic issues from a variety of perspectives.

1. What Is Knowledge Representation?.- 1.1. Introduction.- 1.2. Logic representations.- 1.2.1. Default logic.- 1.2.2. Fuzzy logic.- 1.3. Semantic networks.- 1.3.1. Partitioned networks.- 1.3.2. Marker propagation schemes.- 1.3.3. Topic hierarchies.- 1.3.4. Propositional networks.- 1.3.5. Semantic networks and logic.- 1.4. Procedural representations.- 1.4.1. Winograd’s work.- 1.4.2. Procedural semantic networks.- 1.5. Logic programming.- 1.6. Frame-based representations.- 1.7. Production system architectures.- 1.8. Knowledge representation languages.- 1.8.1. KL-One.- 1.8.2. KRYPTON.- 1.8.3. Other languages.- 1.9. Concluding remarks.- 2. Knowledge Representation: What’s Important About It?.- 2.1. Introduction.- 2.2. Knowledge for reasoning agents.- 2.3. Modeling the external world.- 2.4. Perception and reasoning by machine.- 2.5. The Nature of the world and its models.- 2.6. The functions of a knowledge representation system.- 2.7. The knowledge acquisition problem.- 2.8. The perception problem.- 2.9. Planning to act.- 2.10. Role of a conceptual taxonomy for an intelligent agent.- 2.11. The structure of concepts.- 2.12. An example of a conceptual taxonomy.- 2.13. The need for taxonomic organization.- 2.14. Recognizing/analyzing/parsing situations.- 2.15. Two aspects of knowledge representation.- 2.16. Expressive adequacy.- 2.17. Notational efficacy.- 2.18. The relationship to formal logic.- 2.19. Concepts are more than predicates.- 2.20. Conclusions.- 3. Some Remarks on the Place of Logic in Knowledge Representation.- 3.1. Introduction.- 3.2. What is logic?.- 3.3. On being logical.- 3.4. Reasoning and logic.- 3.5. Nonmonotonic logic.- 3.6. Conclusion.- 4. Logic and Natural Language.- 4.1. Introduction.- 4.2. Default logic for computing presuppositions.- 4.3. Modal logic for planning utterances.- 4.4. Temporal logic for reasoning about futures.- 4.5. Conclusion.- 5. Commonsense and Fuzzy Logic.- 5.1. Introduction.- 5.2. Meaning representation in test-score semantics.- 5.3. Testing and translation rules.- 5.3.1. Composition of elastic constraints.- 5.4. Representation of dispositions.- 5.5. Reasoning with dispositions.- 5.6. Concluding remark.- 6. Basic Properties of Knowledge Base Systems.- 6.1. Introduction.- 6.2. Basic notions.- 6.3. Completeness & consistency of rule-represented knowledge bases.- 6.4. The case of linear sets of rules.- 6.5. Dependency of rules on attributes.- 6.6. Partial information and defaults.- 6.7. Conclusion.- 7. First Order Logic and Knowledge Representation: Some Problems of Incomplete Systems.- 7.1. Introduction.- 7.2. Prolog & Absys: declarative knowledge manipulation systems.- 7.3. Primitive goal selection strategies in Absys and Prolog.- 7.4. Selection strategies and knowledge systems.- 7.5. Summary.- 8. Admissible State Semantics for Representational Systems.- 8.1. Introduction - the problem of practical semantics.- 8.2. Internal and external meanings.- 8.3. Admissible state semantics.- 8.4. Example: semantic networks.- 8.5. Example: k-lines.- 8.6. Conclusion.- 9. Accelerating Deductive Inference: Special Methods for Taxonomies, Colours and Times.- 9.1. Introduction.- 9.2. Recognizing type relationships.- 9.3. Recognizing part-of relationships.- 9.4. Recognizing colour relationships.- 9.5. Recognizing time relationships.- 9.6. Combining general and special methods.- 9.7. Concluding remarks.- 10. Knowledge Organization and Its Role in Temporal and Causal Signal Understanding: The ALVEN and CAA Projects.- 10.1. Introduction.- 10.2. The representational scheme.- 10.2.1. Knowledge packages: classes.- 10.2.2. Knowledge organization.- 10.2.3. Multi-dimensional levels of detail.- 10.2.4. Time.- 10.2.5. Exceptions and similarity relations.- 10.2.6. Partial results and levels of description.- 10.3. The interpretation control structure.- 10.4. The ALVEN project.- 10.4.1. Overview.- 10.4.2. LV dynamics knowledge and its representation.- 10.5. The CAA project.- 10.5.1. Overview.- 10.5.2. Representation of causal connections.- 10.5.3. Use of causal links.- 10.5.4. Recent research related to causality.- 10.5.5. Representation of domain knowledge.- 10.5.6. Knowledge-base stratification and projection links.- 10.5.7. Recognition strategies and control.- 10.6. Conclusions.- 11. SNePS Considered as a Fully Intensional Propositional Semantic Network.- 11.1. Introduction.- 11.1.1. The SNePS environment.- 11.1.2. SNePS as a knowledge representation system.- 11.1.3. Informal description of SNePS.- 11.2. Intensional knowledge representation.- 11.3. Description of SNePS/CASSIE.- 11.3.1. CASSIE - A model of a mind.- 11.3.2. A conversation with CASSIE.- 11.3.3. Syntax and semantics of SNePS/CASSIE.- 11.3.4. The conversation with CASSIE, revisited.- 11.4. Extensions and applications of SNePS.- 11.4.1. SNePS as a database management system.- 11.4.2. Address recognition for mail sorting.- 11.4.3. NEUREX.- 11.4.4. Representing visual knowledge.- 11.4.5. SNeBR: A belief revision package.- 11.5. Knowledge-based natural language understanding.- 11.5.1. Temporal structure of narrative.- 11.6. Conclusion: SNePS and SNePS/CASSIE as Semantic Networks.- 11.6.1. Criteria for semantic networks.- 11.6.2. SNePS and SNePS/CASSIE vs. KL-One.- 12. Representing Virtual Knowledge Through Logic Programming.- 12.1. Introduction.- 12.2. Representing knowledge in Prolog.- 12.3. Asking for inferences - virtual knowledge.- 12.4. Representing problem-solving knowledge.- 12.5. Representing database knowledge.- 12.6. Limitations.- 12.7. Conclusions.- 13. Theorist: A Logical Reasoning System for Defaults and Diagnosis.- 13.1. Introduction.- 13.2. Prolog as a representation system.- 13.3. The Theorist framework.- 13.4. Tasks appropriate for the Theorist framework.- 13.4.1. Nonmonotonic reasoning - reasoning with default and generalised knowledge.- 13.4.2. Diagnosis.- 13.4.3. Learning as theory construction.- 13.4.4. User modelling as theory maintenance.- 13.4.5. Choices in mundane tasks.- 13.5. Representation and reasoning in theorist.- 13.5.1. Extending Horn clauses to full first order logic.- 13.5.2. Reasoning as the construction of consistent theories.- 13.6. Implementing a Theorist prototype in Prolog.- 13.6.1. Not parallelism.- 13.7. Status and conclusions.- 14. Representing and Solving Temporal Planning Problems.- 14.1. Introduction.- 14.2. The Time Map Manager.- 14.2.1. A Predicate Calculus Database.- 14.2.2. Adding Basic Concepts of Time.- 14.2.3. Events and Persistences.- 14.2.4. Temporal Database Queries.- 14.2.5. Chaining Rules in a Temporal Database.- 14.2.6. A Simple Planner Based on the TMM.- 14.3. The Heuristic Task Scheduler.- 14.3.1. Describing a Resource.- 14.3.2. Describing a Plan.- 14.3.3. Specifying Plan Resource Use.- 14.3.4. Specifying Plan Tasks.- 14.3.5. Specifying Plan Constraints.- 14.3.6. Producing a Completed Linear Task Ordering.- 14.4 Summary and Conclusions.- 15. Analogical Modes of Reasoning and Process Modelling.- 15.1. Introduction to analogical reasoning.- 15.2. WHISPER: A program using analogs.- 15.3. Observations on the use of analogs.- 15.4. Mental rotation as an analog process.- 15.5. Conclusions.- 16. Representing and Using Knowledge of the Visual World.- 16.1. Introduction.- 16.2. Progress in high-level vision.- 16.3. The complexity barrier.- 16.4. Achieving descriptive adequacy.- 16.5. Achieving procedural adequacy.- 16.6. Conclusion.- 17. On Representational Aspects of VLSI-CADT Systems.- 17.1. Introduction.- 17.2. VLSI design process.- 17.2.1. Use of multiple perspectives.- 17.2.2. Almost hierarchical design.- 17.2.3. Constraints and partial specifications.- 17.3. VLSI design knowledge.- 17.3.1. Knowledge about VLSI design.- 17.4. VLSI design representation.- 17.4.1. Representation of designed artifact.- 17.4.2. Design plan.- 17.5. Analysis, testing, and diagnosis of VLSI circuits.- 17.5.1. Reasoning with constraints.- 17.5.2. Qualitative analysis.- 17.5.3. Design for testability frames.- 17.5.4. Logic programming in VLSI design.- 17.5.5. Diagnostic reasoning.- 17.6. Natural language interfaces.- 17.7. Concluding remarks.