Forbus

Update on RKF progressOctober, 2000: 

Update on RKF progress October, 2000 Ken Forbus Qualitative Reasoning Group Northwestern University

Overview: 

Overview Analogical Reasoning Reasoning Engines Domain Theories Sketching

Our analogical processing tools: 

Our analogical processing tools Inputs = propositional descriptions, w/ incremental updates Output = one or two mappings Operates in polynomial time, by exploiting graph labels & greedy algorithms Mappings = correspondences + structural evaluation + candidate inferences Memory Pool Output = memory item + SME results Probe Structure-Mapping Engine provides analogical matching MAC/FAC provides similarity-based retrieval Cheap, fast, non-structural No hand-indexing of cases required

Slide4: 

How SEQL Works 1. Compare against each generalization Gi. If close enough, assimilate input into Gi by replacing Gi with the overlap of Gi and input and halt. 2. Compare input against each exemplar Ei. If similar enough, create new generalization from overlap of Ei and input, halt. If nothing similar enough, add input to set of exemplars SEQL refines knowledge by progressive alignment of examples New: The GEL algorithm

Case Mapper: An Analogy GUI: 

Case Mapper: An Analogy GUI Goal: Provide civilized interface for entering knowledge via analogy Should be useful platform for experimenting with dialogue moves Current state Basic functionality showing signs of life AI-expert friendly Next steps Improved pidgin Interface to inference machinery for candidate inference evaluation Explore using dialogue management, simple NLP for interaction

Initial results of Matching: 

Initial results of Matching

Exploring the candidate inferences: 

Exploring the candidate inferences

Integrating into the E2E system: 

Integrating into the E2E system Strategy: Provide analogy server KQML for communication Strategies for analogical reasoning coded in next-generation reasoner Advantages Neutral with respect to uniprocessor/distributed operation Enables us to tune our strategies more easily Drawbacks Sockets as bottleneck Need to keep KB in synch Alternative strategy: Assimilation

Domain Theory Environment (DTE): 

Domain Theory Environment (DTE)

Domain Theory Environment (DTE): 

Domain Theory Environment (DTE) Uses ODBC, Relational database (Microsoft Access) to store KB contents (inspired by Hendler’s PARKA-DB)

Domain Theory Environment (DTE): 

Domain Theory Environment (DTE) Federated architecture, supports reasoning sourcesthat provide special-purposecapabilities efficiently

Domain Theory Environment (DTE): 

Domain Theory Environment (DTE) Query-driven backchainerprovides basic reasoning services, integration mechanism

Domain Theory Environment (DTE): 

Domain Theory Environment (DTE) KQML interface for building servers (e.g., analogy server, geographic reasoner)

DTE Problems: 

DTE Problems Too slow, not scaling well High overhead,too many computational cliffs

Solution: Build next-generation system: 

Solution: Build next-generation system Collaborating with Xerox PARC John Everett, Reinhard Stolle, Bob Cheslow Keeping good ideas in DTE: Federated architecture/Reasoning sources model Using database to implement KB Query mechanism with simple backchainer as glue Use of LTMS for justifications, reasoning Overall structure of interfaces to applications using it will be similar Internals will be very different

Next-generation system: 

Next-generation system Special-purpose C++ database,written by PARC. Built-in support for pattern matching.Adding new knowledge:DTE DB: 4 assertions/secondNew DB: 98 assertions/secondRetrieval:2-3 msec, in 111K assertion KB (preliminary data)

Next-generation System: 

Next-generation System Working memory = LTRE + discrimination tree indexing.Suggestions Architecture:Limit backchaining for “quick” reasoning. Expensive operations queued as suggestions, processed via agenda mechanism.Multithreaded, to exploit time user spends doing other things. Especially important for sketching, dialogue management

Next-Generation System: 

Next-Generation System Knowledge Base Analogical Reasoner Spatial Reasoner Gizmo Mk2 Perceptual Ink Processor Reasoner Streamlined reasoning source interface, with constraint posting for query optimizer. Provide qualitative reasoningservices by embedding QP theory implementation Create ink-based spatial reasoner, organized for incremental processing from the ground up

Current schedule: 

Current schedule Halloween: First version turning over Thanksgiving: DTE applications ported Christmas: First round of performance tuning finished

Everyday Physical Semantics domain theory: 

Everyday Physical Semantics domain theory Claim: There is a basic set of physical notions that need to be understood in order to interpret sketched explanations e.g., Simple notions of surfaces, volumes, forces, and materials Claim: Qualitative physics research can provide most of this knowledge Much of it has already been done, in isolated pieces Needs to be integrated, gaps filled Tied to sketch-based spatial representations Surface constraints on motion Will use Nielsen’s qualitative mechanics Fluid Ontologies Collins’ molecular collection ontology Kim’s bounded stuff ontology + usual contained stuff ontology Surface/fluid interactions Kim’s qualitative streamline theory Qualitative topology Cohn’s spatial algebras Qualitative Statics Nielsen & Kim’s qualitative vectors

Multiple Perspectives: An example: 

Multiple Perspectives: An example How to reason about liquids? Two models, due to Hayes Contained stuff ontology: Individuate liquid via the space that it is in. Piece of stuff ontology: Individuate liquid as a particular collection of molecules.

Fluid ontologies: 

Fluid ontologies Contained stuffs Most detailed: Paper with John Collins, FSThermo domain theory Pieces of stuff Molecular collections (w/John Collins) Plugs (Gordon Skorstad) Bounded stuffs (H. Kim)

Molecular Collection ontology: 

Molecular Collection ontology Idea: Follow a little piece of stuff around a system So small that when it reaches a junction, it never splits apart Provides the perspective gained by tracing through a system of changes

Two containers example: 

Two containers example

Steam plant example: 

Steam plant example

Refrigerator example: 

Refrigerator example

Bounded stuffs: 

Bounded stuffs Specialization of contained stuff ontology Where something is within the space matters Affects connectivity

Ontology zoo for liquids: 

Ontology zoo for liquids Contained Stuff Piece of Stuff Plug Molecular Collection Bounded Stuff Parasitic on

Qualitative Mechanics: 

Qualitative Mechanics Provides axioms for interaction of solids and surfaces Qualitative vector representation Assumes visual parsing of 2D shapes Center of gravity, center of rotation critical Surfaces broken at corners, points of contact not Ok

Qualitative Mechanics: 

Qualitative Mechanics Qualitative angles and vectors How forces interact with surfaces, constraints on motion Laminar flow fields

Engineering Thermodynamics: 

Engineering Thermodynamics Basics of heat, mass flow In-depth KB for supporting design, analysis KB for supporting textbook problem solving Includes control knowledge, analysis of roles for equations in problem-solving Pisan’s Ph.D. thesis solves most problems in typical engineering thermodynamics textbooks Teleological representations for thermodynamic cycles No chemical interactions

Sketching for knowledge acquisition: 

Sketching for knowledge acquisition sKEA: Sketch-based Knowledge Entry Associate Built on top of nuSketch + significant extensions Rich perceptual processing of digital ink Will support visual analogies and analogies using diagrams Speech I/O and specialized Dialogue Manager Can be used standalone or as component in larger system Ink Interpretation is key problem Collaborating with PARC vision group (Eric Saund, Jim Mahoney) for perceptual processing Developing domain theories that bridge perception and conceptual knowledge

Tools we will use in sketching: 

Tools we will use in sketching GeoRep MAGI MAGI models processes of symmetry and regularity detection Uses variation of structure-mapping laws to detect self-similarity Same software operates on visual, functional, conceptual, and mathematical representations Makes predictions consistent with human perceptual data GeoRep provides high-level visual processing for spatial reasoning Provides equivalent of Ullman’s universal visual routines Provides bridge between the visual and the conceptual

Visual Symbology domain theory: 

Visual Symbology domain theory Represents conventions for displaying conceptual information graphically Includes What visual entities often depict boxes, blobs, arrows, etc. Conventional views side/top/bottom, 2D/3D, abstract/physical, cutaways Conceptual interpretation of visual relations proximity/alignment indicating grouping, inside indicating containment or partonomy, touching indicating contact State (before) Process State (after) Arg2 Arg1 Binary Relationship

Approach: Blob Semantics: 

Approach: Blob Semantics Shape, object recognition irrelevant Linguistic input provides labels and type information Arrows may be exception wrt recognition Spatial relationships between blobs is central Topology Touching or not, inside, overlap Proximity What arrows refer to Orientation Multiple reference frames Quadrant plus relative inclination Conceptual interpretation of spatial relationships Hypothesis: Sufficient for Process diagrams Action sequences

Issues in blob semantics: 

Issues in blob semantics Adequacy of visual primitives User-defined diagram types Kinds of objects participating Conceptual interpretation of spatial relationships Arrow recognition Support different types of arrows?

Perceptual Ink Processor: 

Perceptual Ink Processor Will use next-generation reasoner for conceptual side of reasoning For visual reasoning, draw on three sources: Our work on GeoRep and Magi (Ferguson’s Ph.D. work) Eric Saund’s scale-space blackboard (Xerox PARC) Stroke-based visual routines Should provide robust proximity detection Jim Mahoney’s MAPS ideas (Xerox PARC) Bitmap-based visual routines Should provide robust qualitative descriptions of free space

Example: eTDG10 Map: 

Example: eTDG10 Map

SR Regions for eTDG10 map (hand-sketched): 

SR Regions for eTDG10 map (hand-sketched)

Hard constraints from SR regions: 

Hard constraints from SR regions

Voronoi diagram for free space: 

Voronoi diagram for free space

Junctions provide seeds for open regions: 

Junctions provide seeds for open regions

Regions extended from seeds: 

Regions extended from seeds

Edges outside regions form corridor seeds: 

Edges outside regions form corridor seeds

Combined results for eTDG10: 

Combined results for eTDG10

Speech or not?: 

Speech or not? Most multimodal systems use speech recognition Hands, eyes busy with diagram Potential problems with speech for RKF Novel nouns, phrases could lead to distracting speech training during knowledge entry How open-ended is grammar? Necessity versus user expectations Trying both in RKF NLP support with speech LKB parser (Stanford CSLI) Experiment: Speechless multimodal interface Type (or write) label for instance, collection Draw button, as in nuSketch COA Creator Sacrifice fluidity for expressiveness

Intermediate goal: 1st generation sKEA: 

Intermediate goal: 1st generation sKEA sKEA = sketching Knowledge Entry Associate nuSketch application for knowledge formation Initial targets Process diagrams Action sequences Additional task: Scenario setup for testing everyday physical semantics Draw examples from biomechanics