KSL Seminar Schedule - Fall Quarter 96

Location: Gates Building, Room 100
Time: Mondays, 12:30-2:00
Lunch Provided

Stanford students, faculty, and staff are invited to a weekly series of presentations and discussions of current research being conducted in the Computer Science Department's Knowledge Systems Laboratory (KSL). KSL conducts research in Artificial Intelligence with an emphasis on the areas of knowledge representation and reasoning. Seminar presentations will be made by KSL faculty, research associates, and Ph.D. students describing their research on network-based information brokers, ontology development and use, model-based support of distributed collaborative engineering, function-based product identification, adaptive intelligent systems, and virtual theaters. KSL's home page is http://ksl-web.stanford.edu/.

KSL Seminar Schedule

Seminars will be held Mondays, 12:30-2:00 in Gates Building, Room 100. Lunch will be provided!
9/30 Fikes Reusable Ontologies
10/7 Hayes-Roth Improvisational Characters
10/14 Farquhar Semantic Integration of Heterogeneous Information Systems
10/21 Iwasaki How Things Work (HTW)
10/28 Dappert Semantic Mismatches
11/11 Neller Verification of Hybrid Systems
11/18 Pfleger 5 Views of my Thesis: Data-driven, Bottom-up Chunking to Discover Hierarchical Compositional Structure
12/2 McIlraith SD + Actions: New Representation Problems for Model-Based Diagnosis

Abstracts and Supporting Information

Reusable Ontologies: The Key to Large Scale Domain Modeling

Speaker: Prof. Richard Fikes


In recent years, the AI community has been evolving a notion of ontologies as artifacts that play significant roles in knowledge representation and reasoning. Even though ontologies are generally considered to provide definitions for the vocabulary used to represent knowledge, there is no agreement on precisely what an ontology is. So, we begin by proposing a formal definition of an ontology as an integral component of the language in which knowledge is represented and explore the role ontologies play in collaboration, interoperation, education, and domain modeling. We then describe some of the novel features of KSL's Ontolingua Web-based ontology development system that support collaborative development of ontologies by assembling and extending reusable ontologies from an on-line library. We conclude by surveying current research issues and challenges related to enabling the effective creation and use of ontologies.

Improvisational Characters

Speaker: Barbara Hayes-Roth


Improvisational performers create engaging vignettes in real time, without detailed planning, and often working within constraints provided by the audience. My research group is exploring the possibility of creating intelligent computer agents that can be embodied as animated characters, can perform in a manner loosely resembling that of human improvisors, and can tailor their performances to abstract directions offered by users or other system components. I'll talk a little bit about functional requirements for improvisational characters, how these differ from the requirements set for other sorts of intelligent agents, and how they resemble requirements for everyday human behavior. I'll describe our general approach to meeting the requirements and show videotapes of three implemented systems.

Semantic Integration of Heterogeneous Information Systems

Speaker: Adam Farquhar


This seminar will be very much discussing work-in-progress. It follows from a series of discussions with Angela Dappert and Joachim Hammer.

Integration of heterogeneous information systems has become a problem of growing importance. The integration problem can be broadly divided into syntax, protocol, and semantics. As the infrastructure to move bits from place to place and program to program becomes robust, reliable, and ubiquitous, solving the semantic issues becomes increasingly critical.

In this seminar, I will focus on the semantic issues that arise in integration, ignoring issues that arise at run-time such as query planning and execution, optimization, and tractability. I will present an architecture for performing semantic integration that employs a library of reusable ontologies to ease the integration process and articulate some of the consequences of this architecture.

Our work employs Context Logic, developed by McCarthy and Buvac, to define mappings between different representations. I will briefly describe this logic and show how it can be implemented by a standard theorem prover. Time allowing, we will look at some examples using context logic to reuse ontologies, and perform data-model conversions between contexts.

Model Formulation for Model-based Support of Collaborative Engineering

Speaker: Yumi Iwasaki


The How Things Work project in progress at the Knowledge Systems, AI Laboratory aims to develop knowledge-based technology to support designers of electro-mechanical devices in a collaborative engineering environment. In particular, we are developing the Collaborative Device Modeling Environment (CDME), a system that provides tools for distributed collaborative development, testing, and maintenance of engineering ontologies, models, and specifications. An important component of CDME is a facility for automatically formulating a model of a design that embodies the abstractions, approximations, assumptions, and perspectives that are appropriate for a given analysis task. We have developed an efficient algorithm that formulates a simplest, appropriate model for tracking the values and causal influences on a given set of variables during a behavior simulation.

In this talk, I will discuss the objectives of the project, describe the work on model formulation, and present some experimental results on model formulation.

Handling Incomplete Information in Mismatched Information Sources

Speaker: Angela Dappert


My work is embedded in the information broker project at KSL. The purpose of the project is to find solutions to semantic issues of integrating heterogeneous information sources for global query mediation.

In an information broker environment, one has to expect semantic mismatches between the queries asked of the information broker and the heterogeneous information sources which are used for query answering. Sometimes this mismatched information still can be used to create an answer that will give an important lead to the user of the system even if an exact answer cannot be given. The system should be able to answer queries partially - as long as the missing query parts are relatively unimportant or as long as complete query coverage is very important to the application.

We identify three semantic mismatch categories:

  • Domain Mismatch: Discrepancy between the expected domain coverage of objects for the query and the actual domain coverage of the information sources;
  • Property Mismatch: Discrepancy between object properties that make up the query and properties that are used within the information sources to describe objects of interest;
  • Intentional Mismatch: Discrepancy between the information available from information sources and the information accessible via deductive reasoning.

In order to address these problems we suggest a cooperative approach with the following properties:

  • The cooperative system returns a three valued answer space. It guarantees to return all the true answers available (TRUE set). In addition, it attempts to give a complete, lowest upper bound for objects that cannot be concluded to not satisfy the query (MAYBE set). If this is not possible, it should give intentional and extensional descriptions of the object set that can be concluded to fail to satisfy the query (FALSE set).
  • It explains why the objects in the MAYBE set could not be determined to be true or false and what additional information would be needed for each one of them to make a definite decision. This explains the limitations of the available information sources.
We will propose the techniques of partial query answering, approximated query answering, and integrated query answering to achieve this goal.

Verification of Hybrid Systems: A Stepper Motor Case Study

Speaker: Todd Neller


In this talk, we'll look at the current research in verification of hybrid systems, the (ir)relevance of such research to a specific verification problem, and consider the advantages/disadvantages of different approaches for that special case. "Hybrid systems" are systems manifesting behavior with both discrete and continuous change (e.g. a discrete controller affecting continuous physics). We consider the problem of verifying safety against stalling for a stepper motor driven by a fixed acceleration strategy without feedback. Thus we must consider open-loop control and nonlinear dynamics in the face of uncertain system parameters with bounded error. We discuss the relevance of tools and approaches to this verification problem, present promising approaches, and conclude with an open discussion of the involved tradeoffs.

5 Views of my Thesis: Data-driven, Bottom-up Chunking to Discover Hierarchical Compositional Structure

Speaker: Karl Pfleger


In this talk I'll discuss the ideas surrounding my dissertation. I won't present results. Neither will I discuss detailed algorithmic mechanisms. Instead, I will concentrate on describing what I intend to compute and how it fits in with AI, machine learning, etc. Plus, I'll throw in lots of motivations. Specifically, I'll present a number of different views each of which is a different simple way to think about my thesis:

Hierarchical compositional structure constitutes one important form of abstraction. In compositional hierarchies, high level entities represent aggregations of lower level entities. This type of structure is ubiquitous in the real world and in the types of information people and computers encounter every day.

This dissertation examines methods for discovering hierarchical compositional structure and exploiting it in useful ways. Specifically, this structure can be uncovered from the bottom up through repeated composition, or chunking, of lower level entities, beginning with atomic level primitives. We concentrate only on the most general such mechanisms, those that make use only of the raw, atomic level data presented to the system, rather than any separate domain theory or extra task or goal specific information. Aggregation can be performed using only this information simply by chunking frequently occurring combinations of primitives or previous chunks. Once learned, this structure can be used to predict future observations, filter noise, fill in missing or ambiguous entries from context, compress data, or detect anomalies or errors and suggest corrections. Applications based on these uses are virtually limitless. The chunks themselves serve as high level abstractions useful for explanation, communication, memory, and reasoning in general.

SD + Actions: New Representation Problems For Model-Based Diagnosis

Speaker: Sheila McIlraith


In recent years, a number of researchers have argued that diagnostic problem solving is purposive in nature, that in some instances, identifying candidate diagnoses is only relevant to the extent that it enables an agent to act --- to execute a test, to repair a system, to control it, to invoke a contingency plan, or perhaps to perform preventative maintenance. From this viewpoint, we claim that a comprehensive account of diagnostic problem solving must involve reasoning about action and change.

In this work we examine an important set of representation issues that have not been addressed by the model-based diagnosis community. In particular, we examine the problem of integrating a system description, SD, with a theory of action and change, to parsimoniously represent the effect of actions on a system and the effects of a system on actions in the world. We employ the situation calculus, a first-order language, as our representation language for action and change. In the context of the situation calculus, SD presents an often complex set of state constraints. These state constraints implicitly define indirect effects of actions as well as indirectly imposing further preconditions on the performance of an action. As a consequence, SD poses further complications to addressing the frame, ramification and qualification problems.

In addressing these problems, we examine a syntactically restricted SD, which commonly occurs in the axiomatization of model-based diagnosis domains. The contributions of this work are as follows:

  1. a framework for integrating SD and a theory of action and change.
  2. a procedure for compiling SD into a set of successor state axioms. These axioms captures the intended interpretation of SD, while providing a closed-form solution to the frame and ramification problems.
  3. a circumscriptive specification of a solution to the frame and ramification problems which provides formal justification for our procedure.
This talk will focus on items 1 and 2.

Last modified: Wed Nov 27 12:31:46 PST 1996