Rensselaer Polytechnic Institute



LOGIC (PROGRAMMING) AND ARTIFICIAL INTELLIGENCE

CSCI 6967, PHIL 6240 (& PSYC)

Mondays: 1/8/2001 – May 14, 2001, Sage 4112

12PM – 3PM

A graduate seminar, Spr. 2001, Comp. Sci. (and Phil/Psych), Rensselaer

INSTRUCTORS

Selmer Bringsjord

selmer@rpi.edu

David Ferrucci

ferrucci@us.

Guest Lectures: Steinar Flatland, DDC and Adam Lally, DDC

GENERAL ORIENTATION

Synopsis

This course will focus on the use of certain techniques in logic-based AI to produce intelligent software systems that autonomously and semi-autonomously create and produce documents. Some of these systems will be specifically related to literary documents (as in the Brutus story generation system); others will relate to business documents central to industry (e.g., proposals, statements of work, reports, exams, etc.).

Required Books

1. The Art of Prolog, Sterling & Shapiro (AOP)

2. Artificial Intelligence: A Modern Approach, Russell & Norvig (AIMA)

3. Artificial Intelligence and Literary Creativity, Bringsjord & Ferrucci (AILC)

“Background” Books

1. Language, Proof, and Logic, Barwise and Etchemendy (1st course math. logic; worth adding to your library if you’re serious about logicist AI (LAI)). From Seven Bridge Press.

2. Hyperproof, Barwise & Etchemendy (start of visual theorem prover; very helpful system for representing diagrams and natural deduction style proofs) From CSLI.

3. Mathematical Logic (2nd edition), Ebbinghaus, Flum, Thomas (2nd course math. logic; worth adding to your library if your serious about LAI). From Springer-Verlag.

4. Logical Foundations of AI, Geneserth & Nilsson (coverage of logic for computation/AI beyond standard mathematical logic; again, a good book to have, older now, but a classic)

Papers on Reserve (or online)

• A Taxonomy of the Part-Whole Relations, Winston & Chaffin (PWR)

• What IS-A is and isn’t, Brachman (ISA)

• Classes versus Prototypes: Some Philosophical and Historical Observations, Taivalsaari

• “Creativity, the Turing Test, and (the better) Lovelace Test,” Bringsjord, Bello, Ferrucci ()

• Others to follow, TBA.m

• Also, a number of key documents are available on-line, and students should obtain them ASAP on their own. These documents include the manual for the OTTER system, and documents that explain John Pollock’s approach to logic programming through natural deduction, and his OSCAR system. See the relevant web sites for documents/info. Searching via the expected keywords will be effective.

Course Objective

The principal objective is for students to develop a deeper appreciation of the theoretical and engineering challenges of formally representing and reasoning about common-sense knowledge for the purposes of simulating and assisting human activity in the production of documents.

The instructors are committed to cutting-edge R&D in the intersection of logic, AI, and document creation and production in multiple domains, and through this course offer up the potential for future involvement for grad students in this R&D.

An overview of the theory and practice in knowledge representation and formal reasoning and logic is provided with practical examples in logic programming.

Three document generation systems are examined in detail. The first, Brutus, is an academic prototype developed to explore computational models of literary creativity. The second, DocCon, is a commercial Knowledge-Based Interactive Document Development (KIDD) system designed to assist in the representation, reuse and application of content in the production of business documents. The third, eWriter, is a prospective system for automatically and semi-automatically generating test items appearing on “high stakes” standardized tests (e.g., GRE, LSAT). The eWriter system will be analyzed in theory as a specialization of a document generation system.

Prerequisites: Intro to AI (or equivalent), and some previous mathematical logic.

Course Outline

Week 1 (1/8/2001): Overview and Background

Lecturer: Dave and Selmer

Content

• Objective and Course Outline

• Course Logistics

• History and Foundations of AI

• Euclid to “What is a proof? to mathematical logic (Frege) to computation (Turing, Church, Kleene, Godel, etc.) to modern-day computers

• Introduction to Logic, AI, Creativity and Writing

• Including the stages from AILC text

• Introduction to Logic Programming (glimpses only)

• in “Prologish” form (Dave)

• via resolution-based theorem proving (foundations of OTTER; Selmer)

• via natural deduction using HYPERPROOF (foundations of OSCAR; Selmer)

• Application Overview: Goals Architecture and HCI

• Brutus: Computational Aspects of Literary Creativity

• KIDD: Knowledge-Based Interactive Document Development

• Test Authoring and Generation

Readings: AIMA (1,2)

*************1/15/2001 Martin Luther King Holiday***************

Week 2 (01/22/2001): Knowledge Representation I

Lecturer: Selmer

Content

• Formal Representations and Inference

• Mathematical machinery needed to build first-order logic; first-order logic presented as a so-called 'logical system.'

• Some traditional formalizations (e.g., ZF set theory), basic metatheoretical results.

• Review of FOL: Syntax, Semantics, Inference Formal Properties and their practical implications

• Higher Order Logics. They Exist. What are they? How are they limited? Why would anyone use them?

Readings: AIMA (6, 7, 9)

Week 3 (01/29/2001): Introduction to Logic Programming

Lecturer: Dave

Content

• Concepts

• Basic Constructs and Techniques in Prolog

• Discussion and examples

o Database programming

o Recursive Programming

o Searching, Non-deterministic Programming

o Meta-Programming

Readings: AIMA (10.1-10.3, 21), AOP (1,2,3)

Software: Prolog

Assignment I: Describe a classic programming problem, design a solution, Write a Logic Program to implement the solution. Discuss the pros and cons of LP and a programming paradigm and Prolog as an implementation language. (10%, 2 weeks)

Week 4 (2/05/2001): Applications in Logic Programming

Lecturer: Dave & (for 2nd week for last bullet below) Selmer

Content

• Review of Inference in First-Order Logic

• Mechanisms for Deduction: Forward Chaining, Backward Chaining, Resolution

• Examples in Prolog

• Simple Forward Chainer

• Simple Backward Chainer

• Knowledge Belief and the use of Negation: Mystery Solver

• Examples in OTTER and (possibly) OSCAR; TELL & ASK w/ LISP

Readings: AIMA (9, 10.4-10.5), AOP (4-6)

Assignment II: Describe a classic AI problem in terms of knowledge and inference. Design a solution. Write a Logic Program to implement the solution. Discuss the pros and cons of LP as an implementation language for this problem. (15 %, 2 weeks)

Week 5 (2/12/2001); Intro to OTTER and OSCAR’s Background and Test Gen

Lecturer: Selmer

Content

• General Discussion of LP Paradigm as presented thus far

o Return to discussion of earlier-mentioned variations in paradigm

• OTTER

o Return to Logic Theorist problems

o The Murder Mystery in OTTER (from LFAI)

• Knowledge-Based Agents in connection to OTTER

o I.e., OTTER for implementing TELL and ASK

• Natural Deduction and Suppositional Theorem Proving as background to OSCAR

• Preview of Automating Test Creation and Production

Week 6 (2/19/2001): Knowledge Structures and Domain Modeling

Lecturer: Dave

Content

• The world as objects and attributes

• Mapping to LP or to FOL

• Introduction to FLEX Frames

• Classic Links and Their Semantics

o Intention and Extension (“instance-of”)

o Classification (“is-a”, “sublcass” etc.)

o Aggregation (“part-of” and its variations)

• The Meta-Modeling Problem – Spanning Domains

o Harry the Eagle

o Mustang Cars and Models

Readings: AIMA (6, 8, 10.6), PWR, ISA

Assignment III Option 1:

Design and Implement 3 knowledge structures and their inferences as a Logic Program. Use this program to represent a sample domain and demonstrate its ability to reason about that domain. (35%, 4 weeks, Due on Week 10, 15 Min oral presentation required)

Week 7 (Tuesday 2/20/2001): Introduction to Software and Data Modeling

(Tuesday follow Monday’s Schedule)

Guest Lecturer: Steinar Flatland, DDC

Content

• Introduction to Unified Modeling Language (UML)

o Examples in Software Design

• Introduction to the Entity-Relationship Data Modeling

o Examples in Data Modeling

• UML vs E-R: Which is “lower-level”? Which is more expressive? What are their strengths and weakness.

Readings: Handouts

Assignment III Option 2:

There are many “knowledge representation” languages. One might consider UML an ER modeling systems as such languages. Discuss the objectives, strengths and limitations of UML and ER modeling as KR languages. Compare and contrast them to FOL. How do they support the “knowledge structuring” relationships discussed previously? Pick a domain and with examples show the limitations of UML in accurately modeling the domain. What representation structures would you use to more accurately model the domain and why. Develop your example to illustrate your argument. Prepare to present and discuss your example. (35%, Due on Week 10, 2 person groups encouraged, 15 min oral presentation required)

Week 8 (Monday, 2/26/2001): Automatic Story Generation I

Lecturer: Selmer

Content

• System Objectives

• Historical Perspective

• The problem of interestingness

• Computational Elements of Creativity

• A new conceptual approach: Anchoring the Theme (rather than the plot)

• Formal Representations of Betrayal in First Order Logic

Readings: AILC (1-4)

Note: Assignment II Collection

Assignment IV Option 1:

Pick a literary theme and develop a formal representation for it similar to the one presented for Betrayal. Build a thematic relation and extend the Micro Brutus.1 representation structures to instantiate your new theme and generate a new story. (50%, Due on Week 14)

Week 9 (03/5/2001): Automatic Story Generation II

Lecturer: Dave

Content

• The Brutus Architecture for Story Generation

• Idealized Implementation

• Representation and Reasoning Features of FLEX

o Forward and Backward Chaining: Planning and Acting in Brutus,

o Sentence Generation in Brutus

• Overview of a Brutus Implementation in FLEX

• Discussion: Engaging the Human in the Creative Process

Readings: AILC (6.3-6.7)

Software: Micro Brutus.1 will be distributed.

***************3/12/2001 Spring Break*****************

Week 10 (03/19/2001): Domain Modeling Presentations and Discussions

7 X 20 Min Team Presentations

Note: Assignment III Collection

Week 11 (03/26/2001): Introduction to KIDD

Lecturer: Dave

Content

• Knowledge-Based Interactive Document Development

• Background and Motivation

• Solution Concept

• Technical and Business Issues

• Representing Document and Domain Knowledge

• Challenges for an Interactive Reasoning System

• Introduction to DocCon a KIDD system implementation

• Introduction to the DKE Process and the DK Design Document

• Examples in Drafter

• Behind the scenes of the “Marketing Letter”

Readings: Handouts

Software: DocCon will be Distributed on CD or via website.

Assignment IV Option 2: Pick a document class and several instances. Design a document and domain model. Develop a DK Design Document. Implement a Smart-Template and associated knowledge-base in DocCon. (50%, Due on Week 14)

Week 12 (04/02/2001): Document Knowledge Representation in DocCon

Guest Lecturer: Adam Lally, DDC

Content

• Concepts

• Document Templates and their Parts

• Document Components, Classifications and Roles

• The Domain Model: A Classic OO Modeling Approach

• Linking the Domain Model and the Document Model through CVs

• Gathering Domain Data

• Smart Document Behavior

o Rule Control Logic

o Passive Behavior through Constraints

o Active Behavior through AutoCorrect Rules

o Aggregating Behavior in Guidelines

• Simple Template Example – The Easy Path

Readings: Handouts

Week 13 (04/09/2001): Applications in DocCon

Guest Lecturesr: Steinar Flatland & Adam Lally, DDC

• Designing and Building the Domain Model

o Objects, Attributes, Classifications and Roles

• Document Structure

• Document Instance Analysis

o Content Variables

o Reusable Document Components

o Document Library Design and Implementation

• Using Template Starter

• Manual Carving

• Adjusting Range Constraints

• Adding Behavior

Week 14 (04/16/2001) Test Authoring and Generation

Lecturer: Selmer

• “High Stakes” Standardized Tests

o SAT, GRE, LSAT, etc.

▪ AR, LR, RC (item types on e.g. SAT, GRE, LSAT)

• Formal Representation of AR and LR Items

• Implementation of some items in OTTER/OSCAR/HYPERPROOF

• eWriter Project

o Architecture Sketch

o Inductive Logic Programming

• Test Authoring in DocCon

Readings: AIMA (21)

Week 15 (Last Class - 04/23/2001): Final Presentations and Discussions

20 Minute Team Presentations

This class should be held on 4/30th during study week instead (Dave will not be available)

Study Week (04/30/2001)

Finals Week (05/07/2001)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download