| QUAIL '97 (Meeting Summaries) |
This session was spent deciding on meeting time and place, and the order in which we will cover material. Tentatively we are set to cover logic, then knowledge representation and reasoning, with a target of finishing by the end of January. Next will come planning and search, hoping to be finished by the end of March; the rest of the time will be spent on robotics, vision, and perspectives.
General logical fundamentals (e.g., what is truth vs. validity) were briefly discussed. Most of the meeting revolved around Gödel's Completeness and Incompleteness Theorems (can we sketch a proof of either; also, can we sketch a proof of soundness for the "standard" FOL proof procedure), as well as questions about what constitutes a standard proof procedure -- which rules of inference are needed, what the distinction between an infinite number of axioms and axiom schemata is, and the difference between a proof and a proof of a proof (using metatheorems such as Rule T).Unresolved issues: Find concise, intuitive statements of both the Completeness and Incompleteness Theorems. Swiftly sketch proofs of both. Clarify the distinction between rules of inference and logical axioms in proof systems.
Most of this meeting took the form of a quiz by Avi relating to material from LFAI. Salient points included the difference between procedural and declarative knowledge (and the importance of declarative knowledge in AI) and the expressivity, efficiency, and completeness of reasoning systems. Questions included: what is reification (and how does it differ from second-orderlogic), when are interpretations elementarily equivalent (give an example; why are N and R not elementarily equivalent?), what is definability, what is a Markov inference procedure, what is an inference relation. We also discussed the difference between validity-preserving Skolemization (used in tableaux) and satisfiability-preserving Skolemization (used in resolution refutation, etc).
Actually, almost all of this meeting was given over to logic from last time, finishing Avi's questions. Particularly good questions included:
- What is the relationship between finitely axiomatizable, decidable, semidecidable, and completeness of a theory? (See Enderton, p. 145-147 for a diagram)
- How do meta-proofs differ from proofs? Do they have different utilities?
- Sketch proofs of soundness and completeness for resolution.
- Define the Herbrand universe, base, and interpretation for a set of clauses.
We discussed resolution strategies and elimination strategies as well. Paramodulation and demodulation were left as undefined, and we want to clarify the definitions for next time. The meeting then turned to Forbus; Lise led. Topics included:
- limit versus landmark points (example of highway signs)
- reusability and composibility of different models, ontologies
- important considerations in creating a qualitative model
- device versus process ontologies: advantages, disadvantages, characteristics, applications
- envisionment
- history: compared with envisionment, compared with situation
Dr. Iwasaki spoke for the duration of the meeting, about the history of qualitative reasoning. Roughly, she characterized the development of the field as beginning with commonsense reasoning (Hayes), and model-based reasoning, leading into qualitative physics and lately into qualitative reasoning. She emphasized Kupiers' QSIM system and Forbus' QPT(QPE) system. Other topics included metric diagrams and place vocabularies (Forbus' Clock project), the difficulty of representing spatial problems, and interpretation-based models.
Prof. Shoham spoke during this meeting -- my notes are scant at best. Points included
- he personally tries not to ask questions about his own area of interest -- concentrates on breadth issues
- the faculty are generally unaware of what's on the reading list
- "glibness" is a bad tactic -- it's better to be concise, and simply to admit it when you don't know or when you'd need to look it up to be sure
- depth area should be submitted (to him) by the beginning of Spring Quarter
He also sketched the history of knowledge representation and reasoning from his point of view, focussing on logic: beginning with logic, the field split into non-monotonic logics and situation calculi/temporal reasoning, and have come together again in non-monotonic temporal reasoning. Terminological logics and description logics are the current fad (or area of interest, as you prefer) in knowledge representation; depending on who you ask, they are the same thing.
Eyal, Avi, and Urszula were asked questions. Here is a partial list of questions and answers provided by Urszula from her notes:
- What are description logics?
[by Russell and Norvig p.298: These systems evolved from semantic networks due to pressure to formalize what the networks mean while retaining the emphasis on taxonomic structure as an organizing principle. The idea is to express and reason with complex definitions of, and relations among, objects and classes. Description logics are sometimes called terminological logics, because they concentrate on defining terms. Recent work has concentrated on the trade-off between expressivity in the language and the computational complexity of certain operations. Examples: KL-ONE, CLASSIC, LOOM.]- Draw a frame for a sentence "Stanford is a collection of departments."
- What are reasoning techniques in qualitative physics?
- Qualitative reasoning vs. model based reasoning
- Connection between nonmonotonic reasoning and semantic networks [default inheritance]
- Connection between probabilistic reasoning and semantic networks [functional dependence between the property of the class and properties of subclasses based on frequency. Example: salary of a baseball player vs. salary of pitcher and fielder. More complicated example: batting average - requires introduction of a new information: batting frequency for different groups]
- Distinction between semantic nets and frames
- Complexity of reasoning with Horn clauses [tractable without function symbols, intractable otherwise intuition -- finite Herbrand universe]
- Complexity of FOL [tractable without functions and quantifiers]
- What can we do about undecidability of FOL? [1. limit the language; 2. speed up inference by domain-specific knowledge; 3. accept incomplete inference procedures]
- Difference between knowledge level and symbol level
- Complexity of unification [by Russell and Norvig p.303: linear without occurs check, quadratic with it]
- What kind of resolution strategy is used in PROLOG? [depth-first backward (directed) resolution]
- Is resolution complete? Give examples of sentences that are implied by a database but cannot be derived by resolution. [no; tautologies]
I was on the block in this meeting, and was too much of a wreck to take notes. Lise was also grilled. Questions included:
- Define propositional logic.
- Define first order predicate logic.
- What are Herbrand base and Herbrand interpretation?
- Sketch the proof of completeness of resolution.
- What is an alternative to using logical formalisms in AI?
- How are systems such as semantic nets and frames different from FOL in their expressive power?
| Patrick Doyle | November 15, 1996 |