Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp Reading Memo

About LISP

LISP is a programming language widely used in the fields of artificial intelligence and artificial language processing. The main features of LISP are as follows

• Lists (linked lists) are the basic data structure: LISP data is represented as lists, which themselves are evaluated as LISP programs. By taking advantage of this feature, LISP can handle highly flexible data structures.
• Supports functional programming: LISP is a functional programming language, which allows functions to be treated as first-class values. Functions can also be used as meta “higher-order functions” that can be passed to other functions as arguments or return values, or assigned to variables.
• Supports self-referencing: LISP programs can self-reference and refer to their own structure. This makes LISP highly flexible and allows writing programs that are self-modifiable.
• Simple syntax: The syntax of LISP is very simple, making it easy to write programs.
• Many derivatives: There are many derivatives of LISP, each of which has its own characteristics and uses. Typical derivatives include Common Lisp, Scheme, and Clojure.

In this issue, we will introduce a representative reference book on LISP by Peter Norvig, a world-renowned AI researcher and Director of Research at Google, entitled “Practical Common LISP” (originally titled “Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp“) by Peter Norvig.

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp Reading Memo

The three main topics covered in this book are artificial intelligence (AI), computer programming techniques, and the Common Lisp programming language. A careful reading of this book will answer many of your questions about AI and will help you understand important AI techniques. It will also improve your ability to read, modify, and write Common Lisp programs.

The example programs in this book are written in a good programming style, and the examples use paradigms used in AI research.

Part 1: Introduction to Common Lisp

Chapter 1 Introduction to Lisp

Overview
Difference between a computer user and a programmer
User: supplies new input or data (words or numbers)
Programmer: defines new operations or types of programs and data
Many languages have a difference between statements and expressions
A statement exerts an action but does not return a value
In the case of Lisp, everything is an expression, so it returns a value
LISP:LISt Processing

1.1 Symbolic Calculation
1.2 Variables
1.3 Special forms
1.4 Lists
1.5 Defining a new function
1.6 Using Functions
1.7 Higher-Order Functions
1.8 Other Data Types
1.9 Summary: Lisp Evaluation Rules
1.10 What's Different about Lisp?

Built-in List Processing Functions
Automatic Storage Management
Dynamic Typing
First-class Functions
Uniform syntax
Interactive environment
Extensibility

1.11 Exercises
1.12 Solutions

Chapter 2 Simple Lisp Programs
2.1 A Grammar for a Subset of English
2.2 Solving by Successive Methods
2.3 Rule-Based Solving
2.4 Two Paths to Follow
2.5 Changing the grammar without changing the program
2.6 Developing Multiple Programs with the Same Data
2.7 Exercises
2.8 Solutions

Chapter 3 Lisp Overview
3.1 Lisp Style Guide

Six principles every programmer should follow
Be explicit (specific)
Abstraction
Be simple
Use the tools provided
Be clear
Consistency

3.2 Special Forms

Special form for definitions
Special Form for Conditional Branching
Special Forms for Handling Variables and Locations
Functions and Special Forms for Repetition
Repeating with Recursion
Other Special Forms
Macros
Reverse quotation notation

3.3 Functions for Lists
3.4 Equivalence and internal representation
3.5 Functions for Handling Sequences
3.6 Functions for Managing Tables
3.7 Functions for Tree Structures
3.8 Functions for Numbers
3.9 Functions for Working with Sets
3.10 Destructive Functions
3.11 Overview of Data Types
3.12 Input/Output
3.13 Debugging tools
3.14 Bug Prevention Tools

Overview
Timekeeping Tools

3.15 Evaluation

funcall
Apply a function to individual arguments
apply
Apply a function to a list of arguments
eval
A single argument is passed

3.16 Closures
3.17 Special variables
3.18 Multi-valued
3.19 Supplements on parameters
3.20 Miscellaneous
3.21 Exercises
3.22 Solutions

Part 2: Initial AI Program

Chapter 4 GPS: General Problem Solver

The Five Phases of AI Programming
1 Problem description: Describing the problem vaguely in the form of a sentence
2 Specification: Algorithmically describe the problem specification
3 Implementation: Implementing the problem using a programming language
4 Testing: Testing your program with typical examples
5 Debugging and Analysis: Debugging/analyzing a program and then repeating the process

4.1 Station 1: Problem description

The core GPS methods work together to embody the mean-ends analysys heuristic
(e.g.) I want to take my son to daycare.
Aristotle
We deliberate about the means, not the ends.
If I can discover a way to resolve the difference between what I have and what I need, I can solve the problem
Means-goal analysis
Given a current state and a target state, choose an action that will reduce the "difference" between the two.
That action is executed against the current state, creating a new state.
This process is repeated and continued until the target state becomes the current state.
Functional Factors
Have a way to associate the appropriate action to reduce the difference according to the detectable difference
Have a way to track progress (the difference between the actual state and the target state) in order to implement alternatives when actions fail

4.2 Station 2: Specification Description

Representation of the current state and target state in this world as a set of conditions
List of allowed operators
Oberator is a structure consisting of an action, a list of preconditions, and a list of effects
Operators can be applied when all preconditions are satisfied

4.3 Station 3: Implementation

Top-level function
GPS
Solve a problem from a state to a goal using a list of operators
(defn GPS (*state* goal *ops*) "General Problem Solver: achieve all goals using *ops*." (If (every #'achieve goals) 'solved))
Special variables
*state*.
Current state: list of conditions
(defvar *state* nil "The current state a list of conditions.")
*ops*
List of available operators.
(defvar *ops* nil "A list of available operations.")
Data Types
op
An operator with preconditions, additional conditions, and reduced states
(destruct op "An operation" (action nil) (preconditions nil) (add-list nil) (del-list nil))
The function
achieve
Achieve an individual goal
(defund achieve (goal) "A goal is achieved if it already holds, or if there is an appropriate op for it that is applicable." (or (member goal *state*) (some #'apply-op (find-all goal *ops* :test #'appropriate-p))))
appropriate-p
Determine if an operator conforms to a goal
(defun appropriate-p (goal op) "An op is appropriate to a goal if it is in its add list." (member gaol (op-add-list op)))
apply-op
Apply an operator to the current state
(defund apply-op (op) "Print a message and update "state" if op is applicable." (when (every #'achieve (op-preconds op)) (setf *state* (set-difference *state* (op-del-list op))) (setf *state* (union *state* (op-add-list op)))
Selected Common Lisp functions
member
Test if an element is a member
set-difference
All elements that are present in one set but not in the other
union
All elements that exist in two sets.
every
Test if every element of a list satisfies a predicate
some
Tests if some element of a list satisfies a predicate.
Predefined functions
find-all
List of all matched elements

4.4 Station 4: Testing

'I'll drive you to the nursery'

4.5 Station 5: Analysis, or "I lied about the generality of GPS"

AI programming is frequently aimed at gaining a better understanding of the problem domain, rather than meeting a clearly defined specification.

4.6 "Running around the block" problem

Description of the state of motion?

4.7 "Counteracting Sibling Goals" Problem

Sibling.
Instead of satisfying all the goals, solving them in order may cancel out the previous goal
Problems that cancel out the Sibling goal
Problems where the preconditions cancel out the Sibling goal should be allowed to breathe
(defun attain-all (goals) "Try to achieve each goal, make sure they still hold." (And (every #'achieve goals) (subsets goals *state*))
4.8 The "Leap Without Examining" Problem
When dealing with the "preconditions cancel out sibling goals" problem, we need to think more carefully about the order of the goals in the goal list.
(Jump-off-cliff land-safety)
Trying to go over a cliff, but not thinking about a safe landing.
Even though an operator's action may result in a dead end, the action is executed and the *state* is decisively changed.
One solution is to introduce local state variables.

4.8 The "leap without looking" problem

4.9 The "Recursive Subgoal" Problem

Recursive can lead to infinite loops.
Include a mechanism to abandon the loop when it is detected.

4.10 "Lack of intermediate information" problem

If you can't provide a solution, just returning nil doesn't tell you anything about the cause of the failure
debug and undebug, trace and untrace

4.11 GPS version 2: General problem solver with a bit more generality

Top-level functions
GPS
Solve a problem from a state to a target using a list of operators
(defn GPS (*state* goal *ops*) "General Problem Solver: achieve all goals using *ops*." (If (every #'achieve goals) 'solved))
Special variables
*ops*)
list of available operators
(defvar *ops* nil "A list of available operations.")
Data types
op
An operator with preconditions, additional conditions, and reduced states
(destruct op "An operation" (action nil) (preconditions nil) (add-list nil) (del-list nil))
Main functions
achieve-all
Achieve a list of goals
Achieve
Achieve individual goals.
(defund achieve (goal) "A goal is achieved if it already holds, or if there is an appropriate op for it that is applicable." (or (member goal *state*) (some #'apply-op (find-all goal *ops* :test #'appropriate-p))))
appropriate-p
Determine if an operator conforms to a goal
(defun appropriate-p (goal op) "An op is appropriate to a goal if it is in its add list." (member gaol (op-add-list op)))
apply-op
Apply an operator to the current state
(defund apply-op (op) "Print a message and update "state" if op is applicable." (when (every #'achieve (op-preconds op)) (setf *state* (set-difference *state* (op-del-list op))) (setf *state* (union *state* (op-add-list op)))
Auxiliary functions
executing-p
Is the state executing?
(defun executing-p (p) "Is x of the form: (executing ...)? ?" (starts-with x 'executing))
starts-with
Is the list whose argument starts with the specified atom?
(defun starts-with (list x) "Is this a list whose first element is x?" (And (conspired list) (eel (first list) x)))
convert-op
convert operators to use Executing rules
(defun convert-op (op) "Make op conform to the (EXECUTING op) convention." (unless (some #'executing-p (op-add-list op)) (Push (list 'executing (op- action op)) (op-add-list op)) op)
op
Create an operator
(defun op (action &key preconds add-list del-list) "Make a new operator that obeys the (EXECUTING op) convention." (convert-op (make-op :action action action : preconds preconds :add-list add-list :del-list del-list)))
use
Use a list of operators
member-equal
Test if an element is equal to a member of a list
Selected Common Lisp functions
member
Tests if an element is a member
set-difference
All elements that are present in one set but not in the other
subsrtq
Tests whether a set is contained in another set.
union
All elements that are present in two sets
every
Tests if every element of a list satisfies a predicate
some
Tests if some element of a list satisfies the predicate.
remove-if
Remove all items that satisfy the test.
Predefined functions
find-all
List of all matched elements.
find-all-if
List of all elements that satisfy the predicate

4.12 Monkeys and Bananas (A New Domain Problem)

Application to a new problem
Works with GPS by simply introducing different operators

4.13 Maze Search

Works with GPS just by introducing different operators

4.14 The World of Building Blocks

Sussman's Anomaly

4.15 Station 5 (Again): Version 2 Analysis
4.16 The "Don't Leap, Don't Look Up" Problem

Examine all possible solutions
Maintain a list of goals to be protected

4.17 The "Lack of Descriptive Power" Problem

Need disjunction and negation as well as conjunction
Handling of time-based problems
Whether partial solutions are satisfactory

4.18 "Complete Information" Problems

Need to express ambiguity
GPS always knows exactly what it is going to do, not the operator
It has no way of expressing unanticipated difficulties.

4.19 The "Interacting Goals" Problem

No notion of satisfying all goals
Many of the goals remain dormant
Goals are only partially met
There is a constant process of postponing and discarding goals
Humans also know undesirable situations that they try to avoid
Heb Simon's approach
Create the term "satisficing" to describe a strategy of abandoning or postponing a goal while satisfying a good number of goals to a good degree
Since GPS can only identify successes and failures, it has no way of maximizing partial successes.

4.20 Limitations of GPS

Problems that cannot be solved
Execution time is too long
The problem itself has no solution
The essence of GPS is "Local Feature -Guided Network Searcher".
GPS is a means to explore "the essence of deliberation
Can't we make it a tool for deliberation?
It is a tool for a more complete understanding of means-ends analysis.
The appeal of AI is the division between means and ends
The goal of AI projects is to be able to accomplish tasks that are deemed useful, more effective, faster, and cheaper than before

4.21 History and References

Earl Scaerdoti's ABSTRIPS program
A modified version of STRIPS
David Warren's WARPLAN planner
Austin Tate's NONLIN system
David Chapman's TWEAK
Overview Papers
Allen Hender, Tate

4.22 Exercises Translated with www.DeepL.com/Translator (free version)

4.23 Solution

Chapter 5 ELIZA: Interacting with Machines

Overview
Three famous programs created in the 1960s
ELIZA
Simulates a psychoanalyst
STUDENT
Solves middle school algebra
MACSYMA
Math processing program for symbolic algebra, including calculus.
All three programs work on the basis of pattern matching
To explain is to explain and solve questions
The program is doing the job of understanding by carefully recognizing, transforming, and imitating elements of the input
Procedures look for specific patterns in the input based on key words or phrases

5.1 Problem description and specification description of ELIZA

Algorithm
Read the input
Find a pattern that matches the input
Transform the input into a response
Output the response

5.2 Pattern Matching

Implement pattern matching variables
Transform only a set of symbols like [X, Y, Z].
How to define a structure of type Variable
Use symbols and distinguish between variables and constants by the name of the symbol
Symbols are atoms with components

5.3 Segment Pattern Matching
5.4 Programming ELIZA: Rule-based translator

Glossary
Top-level function
ELIZA
Respond to user input using pattern matching rules
Special variables
*eliza-rules*.
List of transformation rules
Data type
rule
Association of a pattern with a list of responses
Functions
eliza
Respond to user input using pattern matching rules
use-eliza-rules
Find rules to transform the input
switch-viewpoint
Change "I" to "you" and vice versa
flatten
Append elements of a list to make them fit together
Selected Common Lisp functions
sublis
Assign an element to a tree
Predefined functions
random-elt
Randomly pick an element from a list
pat-match
Match a pattern against input
mappend
Append the results of mapcar together
Alias method
Associate multiple words with the same pattern
Example: associating mother and father with the family pattern
Synonym function (synonym)
Synonyms: "don't" and "do not", "everyone" and "everybody
For input with comma-separated phrases, each phrase is processed separately, and the response with the highest priority is chosen.
It has a "memory" function, which responds with something like "Tell me more aboit X" when the pattern does not match the input.
It is not the program but the technique that is important.

5.5 History and References

Original literature
Weizenbaum (1966)
A dialogue system using a similar pattern matching technique
PARTY by Kenneth Colty
Proposal by Colby
A study of dialogue systems that model beliefs
Alan Collins(1978)
Jamie Carbonell(1981)

5.6 Exercises
5.7 Answers

Chapter 6 Building Software Tools
6.1 Interactive Interpreter Tools

REPL (read-eval-print) loop
(defun lisp() (loop (print '>) (print (eval (read)))))
(loop (print (eval (read))))
The simplest configuration
read is a parser
Reads input, evaluates or transforms the input in some way, outputs, then returns to read more input
How to use repeating patterns
Informal usage
Treat patterns as clichés or idioms
Occur frequently, but are used slightly differently
Copy and modify
Formal usage
Abstraction in the form of functions and perhaps data structures, and explicitly referring to the abstraction in new applications
Interpreter pattern abstraction
(defun interactive-interpreter (prompt transformer) "Read an expression, transform it, and print the result." (loop (print prompt) (print (funcall transformer (read)))))
(defun lisp ( ) (Interactive-interpreter '> #'eval))
(defun eliza ( ) (Interactive-interpreter 'Eliza> #' (lambda (x) (flatten (use-eliza-rules x)))))
Using the compose function
(defun compose (f g) "Return the function that computes (f (g x))." #'(lambda (x) (fungal f (fungal g x))))
(defun Eliza ( ) (Interactive-interpreter 'Eliza> (Compose #'flatten #'use-eliza-rules)))

6.2 Pattern Matching Tool

Match a single input to a single patter
What is a "generic" tool?
The challenge is to decide what functionality to provide with the tool
Mechanism
Provides a segment variable that matches zero or more elements
Allow arbitrary predicates to be specified that must satisfy that predicate to be matched
(Pat-match '(x = (?is ?n numbers)) '(x = 34)) -> ((?N . 34))
(Pat-match '(x = (?is ?n numbers)) '(x = x)) -> NIL
Combination of ? and, ? or, and ? not
(Pat-match '(?x (?or < = >) ?y) '(3 < 4)) -> ((?Y . 4) (?X . 3)))
(Pat-match '(x = (?and (?is ?n numbers) (?is ?n odd))) '(X = 3)) -> ((?N . 3)))
(Pat-match '(?x /= (?not ?x)) '(3 /= 4)) -> ((?x . 3)))
Pattern syntax
pat => var match any single expression constant match this atom segment-pat match anything against a sequence single-pat match anything against a single expression (apt . pat) Match the first and the rest Single-pat => (?is var predicticate) Test after the gun for a single region (?or pat...) Match any pattern against a single expression (?and pat...) Match any pattern against an expression (?not pat...) Succeeds when no pattern matches Segment-pat => ((? * var) ...) Matches zero or more expressions ((? + var) ...) Matches one or more expressions ((? Var) ...) Matches zero or more than one expression ((?if exp) ...) Test whether an expression containing a variable is true var => ?cahrs ? symbols starting with constant => atom any atom that is not a variable
Data-driven programming
Store patterns/actions in a table
Despatch function
A function that calls a data-driven function
Dispatch mechanisms: various mechanisms by which a language dynamically chooses its behavior
Segment
A chunk of something
Sequence
A sequence of things

6.3 Rule-based translator tools

Match the input against some patterns
Create a rule to choose something from the matched patterns
(defun use-eliza-rules (input) "Find some rule with to transform the input." (some #'(lambda (rule) (let (( result (pat-match (rule-pattern rule) input))) (If (not (eq result fail)) (sublis (switch-viewpoint result) (Random-Let (rule-response rule)))))) *Eliza-rules* ))
Explore a list of rules and take actions based on the rules that match
Generic rule-based translator
(defun rule-based-translator (input rules &key (matcher #'pat-match) (Rule-if #'first) (rule-then #'rest) (action #'sublist)) "Find the first rule (Rule-if #'first) (rule-then #'rest) (action #'sublist)) "Find the first rule in rules that match input, and apply the action to that rule." (Some #'(lambda (rule) (Let ((result (fungal matcher (fungal rule-if rule) Input))) (If ( not (qe result fail)) (Fungal action result (fungal rule-then rule))))) Rules)))

6.4 A set of search tools

Overview
A GPS program is a search problem that starts from a state and arrives at a state by examining its neighbors.
A state is a description of the situation or state of the problem.
States are kept adjacent to each other
Search problems are non-deterministic: there is no way to determine the best choice of where to go next.
Characteristics of search problems
Starting state
Target state (one or more)
Successors, or states that can be reached from one state to the next
Strategy to determine the order in which to search
Means-objective analysis
State space or all possible states need to be defined
States are nodes, and relations with successors are links in the graph
Exploring the tree structure
Guiding the search
Search path
Estimating a good solution vs. guaranteeing a good solution
Graph search

6.5 GPS as a search problem
6.6 History and References
6.7 Exercises
6.8 Solutions

Chapter 7 STUDENT: Solving Algebra Text Problems
7.1 Converting English sentences into equations
7.2 Solving algebraic equations
7.3 Examples
7.4 History and References
7.5 Exercises
7.6 Solutions

Chapter 8 Symbolic Computation: Simplification Programs
8.1 Converting Middle Notation to Prefix Notation
8.2 Simplification rules
8.3 Combinability and commutativity
8.4 Logarithmic functions, trigonometric functions, and derivatives
8.5 Limitations of the rule base
8.6 Integration
8.7 History and references
8.8 Exercises

Part 3: Tools and Techniques

Chapter 9: Efficiency Issues

Overview
Benefits of Lisp
Rapid Prototyping
Efficiency is important when dealing with large amounts of data and huge search spaces
Efficient programs
Easy to change when you need to change your program
Appropriate abstraction
Can identify where the program is taking a long time to run
Can replace inefficient components with constrained versions

9.1 Caching technique: Memoization

Reuse of computation results

9.2 Compilation techniques

Less to do at runtime
Compile twice as much as the interpreter?

9.3 Lazy Computation Technique

If a computation may be partially unnecessary, delay the computation
Closures
Function Closure
A type of function object in programming languages
Functions and concepts that can be used in lambda expressions and anonymous functions
Resolves variables other than arguments in the environment in which it is defined (static scope), rather than in the runtime environment.
A pair of a function and the environment in which it is evaluated
Closure work
Specifying the constructor of a set as a function and calling that function later

9.4 Indexing Techniques

Indexing a data structure to quickly retrieve information
Finding an element in a list of length n requires an average of n/2 steps

9.5 Instrumentation: Determine what should be optimized

Identify and optimize the most frequently used fixtures
Measure the number of times a selected function is called
Function profiling (profiling)
The trace function

9.6 Case Study on Efficiency: SIMPLIFY Program

130x speedup by combining memoization, compilation, and indexing
Memoization
Retain the results of subroutine calls for later use
Also used in parsing, etc.
Recursive descent parsing of backtracking expressions
Early method
A limited form of caching
Indexing
Single rule compiler
Ruleset Compiler

9.7 History and References
9.8 Exercises
9.9 Solutions

Chapter 10: The Problem of Low-Level Efficiency

Overview
How to improve efficiency without drastically changing the algorithm.
Identifying the most frequently used parts of a program and micro-optimizing those parts locally

10.1 Use of declarations

When running lisp on a general-purpose computer, a lot of time is spent on type checking.
Declare or promise that a particular variable is always the specified one, at the expense of robustness

10.2 Avoiding Symmetric Functions

Common Lisp has functions with high generality.
Use arguments without worrying about whether they are lists or vectors

10.3 Avoiding complex argument lists

Functions with keyword arguments incur a large overhead.

10.4 Avoiding Unnecessary Cons

Function cons have a hidden cost.

10.5 Use Appropriate Data Structures

It is important to use the key data types in the most efficient implementation
Appropriate data structures: variables
Appropriate data structure: queue
Queue
Data structure that can add elements to the back and remove them from the front
Stacks are easy to handle with lists, but queues take time to process
Stack has only one entrance and exit
Appropriate data structure: table
Table (table)
Store keys and values in association with each other, and later use the keys to retrieve the values
Possibility of table operations
Count the number of keys
Clear all keys
Apply a mapping function at last for table keys/values
Acyclic effective graph (DAG: directed acyclic graph)
Spelling correction program

10.6 Exercises
10.7 Solutions

Chapter 11 Logic Programming
11.1 Idea 1: A Uniform Database
11.2 Idea 2: Unification of Logical Variables
11.3 Idea 3: Automatic Backward Control
11.4 The Zebra Problem
11.5 Synergy between Regression and Unification
11.6 Destructive Unification
11.7 Prolog by Prolog
11.8 Comparison of Prolog and Lisp
11.9 History and References
11.10 Exercises
11.11 Solutions

Chapter 12. Compiling Logic Programs
12.1 Prolog Compiler
12.2 Compiler Error Repair
12.3 Improvements to the Compiler
12.4 Improvements to the Compilation of Unification
12.5 Further Improvements to Unification
12.6 Compiler User Interface
12.7 Compiler Benchmark Testing
12.8 Adding Primitives
12.9 Cuts
12.10 The "Real" Prolog
12.11 History and References
12.12 Exercises
12.13 Solutions

Chapter 13 Object-Oriented Programming
13.1 Object-Oriented Programming
13.2 Objects
13.3 Symmetric Functions
13.4 Classes
13.5 Delegation
13.6 Inheritance
13.7 CLOS: Common Lisp Object System
13.8 CLOS Implementation Example: Search Tool

Best-First Search

13.9 Is CLOS an Object-Oriented System?
13.10 Advantages of Object-Oriented Programming

Legitimacy
Robustness
Extensibility
Reusability
Adaptability

13.11 History and References
13.12 Exercises

Chapter 14: Knowledge Representation and Reasoning

Overview
In the 1960s, AI research was devoted entirely to search problems.
If you could find the right search method, you could solve all the problems and prove all the theorems.
1970s
No matter how clever the inference algorithm is, it cannot solve NP-hard problems
General inference mechanisms work well for toy problems, but not when the size of the problem increases
Alternatives
Expert systems
The key to solving hard problems is to acquire special rules to divide the problem into simpler problems.
MYCIN
The choice of inference mechanism is not as important as having the right knowledge
It does not matter if you are specifying confidence, probability, or fuzzy set theory.
What matters is the acquisition of knowledge
Great recognition that the knowledge used in the system was not clearly defined.
Does (Color apple red) mean that a particular apple is red or does it mean that all apples are red?
Technology in the field of knowledge representation
Algorithms for manipulating knowledge
Providing an explicit semantics for knowledge representation
Trade-off between expressiveness and efficiency
End of 1980s
Doubt about the desire to find a good language with reasonable expressive power
Computational complexity to answer simple questions is exponential order in worst case
1990s
Interest shifts to knowledge representation and reasoning
Contains both expressive power and efficiency of language
Average case more important than worst case
Amount of knowledge does not help solve hard problems in the worst case, but in practice this is a rare occurrence

14.1 Classification of Knowledge Representation Languages

Logical expressions (prolog)
Networks (semantic networks, conceptual graphs)
Syntactic variants of logic programming languages
The difference between logic programming and logic programming is the importance of "links".
Inference is performed by following links
Putting a link between A and B not only expresses that L(A,B) is true, but can also express something about how the knowledge base is explored
Objects (scripts, frames)
Syntactic variants of predicate logic
Example (a person (name =Jan) (age = 32))
∃p: person(p) ∧ name(p, Jan) ∧ age(p,32)
Predicate logic is more expressive
Frame languages
Procedural (Lisp, production systems)
Compute answers without explicit representation of knowledge
Use procedures to compute values that are difficult to express

14.2 Predicate Logic and its Problems

Predicate logic has a special status as a representation method in AI
A universally accepted standard for defining and evaluating other representation methods
Can be defined to understand the meaning of things expressed in a language
Knowledge representation
An individual to which a relation or function is applied
Use sentences formed by joining relations with logical connectives and,or,not
Philosophers and psychologists describe models of human thought
Predicate logic is easy to translate into the world of bits
If you can represent a computer state, you can represent any computer program in real-world logic as a set of axioms that map one state to another
Challenges of predicate logic
Decidability
Given a set of peddlers and a goal, neither the goal nor its negation may be derived from the axioms.
tractability
Even if the goal is provable, it would take too much time to discover its proof using the available reasoning mechanisms.
Uncertainty
It may be inconvenient to deal with relations that have been proven to some extent but are not known to each facility to be true or false.
Monotonicity
In pure predicate logic, once a theorem is proved, it is true forever.
In pure predicate logic, once a theorem is proven to be true, it remains true indefinitely, but a method is used to derive a hypothetical theorem based on a hypothesis, and then withdraw the hypothesis when it is proven to be false.
Consistency
In pure predicate logic, no contradictions are allowed.
Even the slightest inconsistency will contaminate the entire database.
Omniscience
It is difficult to distinguish between what is provable and what needs to be proven.
Leads to unfounded hypotheses that agents believe all consequences from known facts
Expressiveness
First-order predicate logic can be awkward when talking about things like relations and propositions.

14.3 Logic Programming Language: Prolog

Overview
Prolog is proposed as an answer to the problem of programming in logic.
Kowalski's equation
Algorithm = Logic + Control
Logic
Axioms used in computation
Control
How deduction is applied to axioms
Controlled deduction
Deduction
A method of logical reasoning in which more individual and specific conclusions are reached from general and universal premises
Logic = Algorithm - Control
? When you have an infinite search space, you cannot get an answer in a reasonable time without advice on how to search
The problem of prolog
In order to make the language more efficient, its expressive power is limited
Example: Cannot state that a person's name is Jan or John
It is not possible to state that a fact is false
Prolog cannot distinguish between false and unknown
The inference mechanism is neither correct nor complete
It does not check for circular unification, so it may give wrong answers
May not find the right answer because it does depth-first search
Does not have a way to add control information to the underlying logic
Adding control information may make it less efficient for certain problems

14.4 Expressiveness Issues in Prolog

prolog is not a complete predicate logic
It cannot express certain unclear facts.
Example
code1
(<- (not (capital LA CA))))
(<- (or (capital Albany NY) (capital NYC NY)))
The capital of the state of New York is either New York City or Albany.
code2
If NYC is not the capital of the state of NY, then Albany is the capital of the state of NY
(<- (capital Albany NY) (not (capital NYC NY)))
If Albany is not the capital of NY state, then NYC is the capital of NY state
(<- (capital NYC NY) (not (capital Albay NY)))
Prolog's not is not the same as logic's not
When Prolog answers a question with "no", it means that the question cannot be proved from the facts of the base.
An unknown fact may actually be true.
Consider "unproven" to be equivalent to "false.
Closed world assumption
Everything that is true is known.
Elements of general knowledge representation
"yes".
No
unknown
Not in prolog
Prolog performs the same proof twice, when illumination is completely unnecessary
It is not enough to consider only one theory at a time
Multiple clauses need to be considered together to get the right answer
Disjunctive reasoning
Three color-coded blocks
Let a block be a country
An Eastern European country E decides whether to remain a communist state or become a democracy, but does not know the outcome
E's land is surrounded by democracy D and communism C
The Problem
Is a communist state adjacent to a democratic state?
yes
Prolog is not good at or and not
Example of a good transformation of an expression
Jan likes everyone.
∀x person(x) ⇒ likes(Jan, x)
( <- (likes Jan ?x) (person ?x))
Examples of poorly converted expressions
Jan likes someone.
∃x person(x) ⇒ likes(Jan,x)
(<- (likes Jan p1)) (<- (person p1))
p1: symbol for the person on the street that Jan likes.
p1 is a constant, not a variable
Constants that are specified but indicate the existence of a path
skolem constant
Unique name assumption
Different atoms represent different individuals
In the above example, if we add the assertion p1=Adrin (Jan prefers Adrin), the prolog will not work properly
Skolem function
Example
Everyone likes someone.
∀y∃x person(x) ⇒ likes(y,x)
(<- (likes ?y (p2 ?y))) (<- (person (p2 ?y)))
Skolem function where p2 is determined by the variable ?y
Everyone prefers some person who is not necessarily the same person

14.5 Expressive Power Issues in Predicate Logic

Limitations of expressive power in predicate logic
Example
(<- (animal ?x) (lion ?x)) (<- (animal ?x) (tiger ?x)) (<- (animal ?x) (bear ?x))
We can prove that a lion, tiger, or bear at any given base is an animal.
I can't answer "What kind of animal is there?" I can't answer
(? - (<- (animal ?x) ?proposition))
Higher-order sentence
A sentence in predicate logic that uses relations and sentences as terms.
Paradoxes of higher-order expressions
Paradoxes arise when we allow sentences to say things about the truth of other sentences.
Is the sentence "This sentence is false" true or false?
Predicate logic is defined in a world of solids, using the properties of solids and the relations between them.
It is suitable for models that find and classify individuals.
The world of continuous reality (e.g. water) is hard to define
Can be expressed using Patrick Hayse's approach
When defining categories
For mathematically definable categories, predicate logic is
If and only if x is a polygon with 3 pieces, then x is a triangle

14.6 Completeness Issues

Since Prolog searches depth-first, it does not look at only one branch of the search space and not the others
(<- (sibling lee kim)) (<- (sibling ?x ?y) (sibling ?y ?x)) Lee is a sibling of kim Predicate sibling(X,Y) for "X is a brother or sister of Y" 14.7 Efficiency Issues: Indexing The Prolog compiler is designed to handle "program-like" predicates efficiently. A "program-like" predicate Predicates with a complex body but a small number of rules The above compilers are inefficient for "table-like" predicates. Table-like" predicates Predicates with a large number of simple facts 14.8 Solution to the indexing problem Solution for "table-like" predicates Use "indexing" to facilitate addition, deletion and retrieval of entries Extend "try" and "discriminant tree data structures Psychological Perspectives on Action and Response Generalization and Discrimination Generalization When a specific response is conditioned to a stimulus, the same response will occur to similar stimuli (similar stimuli). The lower the degree of similarity, the lower the frequency with which the response is elicited (i.e., the lower the frequency with which the response is generated). Generalization gradient Discrimination When stimuli are similar, generalization produces a conditioned reflex to both stimuli, but if the generalization is repeated, only one of the stimuli is responded to Creating discrimination trees for Prolog facts is complicated by the presence of variables in both facts and questions. The problem with discriminative trees where the key and the question are predicate structures with wildcards Wildcards are variables There are no variable bindings Example 1 Example 2 14.9 How to solve the safety problem 14.10 Solutions to the expressiveness problem Higher-order predicates "What kinds of animals are there?" Constrain the use of the new language to eliminate "higher-order predicates The new language allows for three types of objects Category Unary predicates relation Binary predicates Individuals zero-term predicate Primitive operator sub (sub subcategory supercategory) Example:(sub dog animal) A dog is a kind of animal. rel (rel relation domain category value category) Example: (rel birthday animal date) The relation birthday holds the relation between each animal and a certain date. ind (ind individual category) Example: (ind fido dog) Individual Fido is categorized as a dog val (val relation individual value) Example: (val birthday fido July-1) Fido's birthday is July-1 and (and assertion...) Example: (and A B) Both A and B are true Improvements Frame Languages Provides an alternative syntax that facilitates reading and writing Frames are objects with slots Possible worlds: psychology, negation, selection Focus on four problems Distinguish between unknown and false Expressing negation Representing a choice Representing a situation with multiple possibilities Means of resolution Possible worlds Negated predicates Add Truth maintenance system (TMS) Unification, Equivalence, Types, Skolem Constants 14.11 History and References 14.12 Exercises 14.13 Solutions Translated with www.DeepL.com/Translator (free version) Part 4: Advanced AI Programs Chapter 15 Symbolic Computation in Standard Form Overview Challenges of prolog Reasoning with Uncertainty Can only handle a black-and-white, clearly distinguishable world that is either true or false Does not handle false well Explanation No explanation of how the association was derived Flexible control flow Works by chaining backwards from the goal In medical diagnosis, specific information about the patient is obtained according to the support given by the doctor The approach to these challenges is an expert system MYCIN System of medical diagnosis Designed to provide instructions for antibiotic treatment of bacterial blood infections (defrule 52 If (site culture is blood) (Gram organism is neg) (Morphology organism is rod) (Burn patient is serious) Then .4 (Identity organism is (Identity organism is pseudomonas))) EMYCIN Interpreter for backward chaining rules that has a lot in common with Prolog Differences Can handle uncertainty Associates a certainty factor (CF) with each predicate Caches calculations so that they do not have to be repeated Provide many easy ways for the system to ask the user for information Provide a description of the behavior Summary Glossary of EMYCIN Program Terms Top-level functions for clients emycin Run a shell with a list of contexts to represent a problem mycin Run a shell in a bacterial infection domain Top-level functions for experts defcontext Define a context defparm Define parameters defrule Define a rule constants true The confidence level of +1. false Confidence of -1 unknown 0 confidence cf-cut-off Cut off the search when the CF is lower than this value. Data type context Subdomain related to a particular problem. parm Parameters rule Rule for backward chaining with confidence. yes/no Types with yes and no members. Emycin's main functions get-context-data Collects data and draws conclusions find-out Request from database, user, use rules to determine value get-db Get facts from the database use-rules Apply all rules related to a parameter use-rule Apply a single rule new-instance Create a new instance of the context report-findings Output the results Auxiliary functions cf-or Combine certainties with or cf-and Combine certainties with and true-p Is this CF true? false-p Is this CF false? cf-p Is this a confidence level? put-p Put facts in the database clear-db Clear all facts from the database get-vals get values and CFs for parameters/instances get-cf get value and CF for a parameter/instance update-cf Change the value and CF for a parameter/instance ash-vals Ask the user for the value and CF of a parameter/instance prompt-and-read-vals Output a prompt and read the response inst-name Name of the instance parse-reply Convert a reply into a list of values/CF parm-type The value of this parameter must be of this type get-parm Get or create a structure for a parameter with this name put-rule Add a new rule indexed under each parameter in the conclusion get-rule Get a rule to help determine this parameter. clear-rule Remove all rules satisfy-premises Compute the combined CF of the preconditions eval-condition Determine the CF of a condition reject-premise Reject a premise if it is obviously false. conclude Add parameter/instance/value/CF to the database is Another name for equal check-conditions check that the rule is valid print-rule Print the rule print-conditions Print a list of conditions print-condition Print a single condition cf->english
Convert CF to English expression

15.1 Standard form for polynomials
15.2 Differentiating Polynomials
15.3 Converting between Middle and Preterite Forms
15.4 Benchmark Testing of Polynomial Simplification Programs
15.5 Standard Form for Rational Expressions
15.6 Extensions of Rational Expressions
15.7 History and References
15.8 Exercises
15.9 Solutions

Chapter 16. Expert Systems

Overview
Three challenges of prolog
Reasoning with Uncertainty
Prolog can't handle things like perhaps
Explanation
Cannot explain how a meeting was derived
Flexible control flow
Prolog works with backward chaining from goals
Need strategies other than backward chaining
In medicine, specific information about a patient is acquired according to the physician's instructions
Difference between EMYCIN and prolog
EMYCIN can deal with uncertainty
Gives a degree of confidence to each predicate
Caches calculations so that they do not have to be duplicated
It provides an easy way for the system to ask the user for information
Provide a description of the behavior

16.1 Dealing with Uncertainty

Confidence Combining Methods
Example: combine(.60,.40)=.76
Probability and similarity when A and B are independent
Confidence is not the same as probability
Deals with beliefs and doubts, but not with dependence and independence
EMYCIN's hypothesis
Conditions in a single rule depend on each other
Conditions in different rules are independent
EMYCIN's certainty function
Innovativeness does not hold in the world of true and false
Only in the fractional world
Confidence is used to terminate the search

16.2 Caching Derived Facts

Emycin stores all homologous facts in a database
Put-db
Get-db
Clear-db

16.3 Questions

When the answer cannot be identified from the rules, we can ask the user a question.
Ask-vla outputs a question about the parameters of the instance and reads a list of values or hits that the user is confident about.
Check to see if the same question has been asked before.
Then it checks the value and the confidence level to see if it is the right one.
When a user asks ? from the user, the system will give the answer it expects.
Returning a Rule changes the rule that the system is currently working with, and the
Why explains in detail what the system knows and what it is trying to discover
Help explains each term
Ask-vals
Prompt-ans -read-vals
Actually ask the question and read the response
Call Format to output the plop, and
Read is called to get the answer.
Get-param
Get the structure associated with a symbol
Params-prompt
Get the prompt for a parameter
Param-reader
Get the reader function
Check-reply
Use parse-reply to convert the user's reply to standard form
Checks if each value is of the correct type and if the confidence level is valid
If the check passes, the database is updated to reflect the new confidence.
Parameters are implemented as structures with six slots
Name (symbol)
Context
Prompts the user for a value
Boolean value to specify whether the question to the user should be asked before or after the rule is applied
Type constraint
Function to be applied to read the value
Parameters are stored in the attribute list of their name with attribute param

16.4 Contexts to substitute for variables

EMYCIN uses contexts instead of logical variables such as prolog.
EMYCIN knowledge base designers can define contexts as situations in which inferences are made.
Context is a data type
The context given to a program determines what types of objects will be inferred
The program manages the most recent instance of each type.
To refer to an instance from a rule, use the name of the type (patient,culture,organization in EMYCIN)
The Initial-data parameter is asked to the user when each instance is created.
Goal parameter is not known to the user
The Goal parameter is not known to the user, but is determined during the backward chaining process.

16.5 Rethinking Backward Chaining

EMYCIN, like prolog, given a goal, applies a rule that conforms to that goal
To apply a rule means to consider the premises of the rule as a target and to apply the conforming rule recursively
In the case of Prolog, if the conforming rule succeeds, the goal becomes true
In the case of EMYCIN, it is necessary to check all rules that conform to the goal.
EMYCIN collects all evidence for a parameter/instance pair and evaluates the goal after all evidence has been collected
Example
Suppose the goal is (temp patient > 98.6)
Evaluate all arguments for the patient's temperature
Then compare the temperature to 98.6
Prolog is depth-first (if any rule is true, it is true)
EMYCIN does a width-first search
A rule with a confidence level of .99 may turn out to be false when more evidence is collected
Find-out
Find out the identity of a parameter in three ways
Check if the value is already in the database.
Ask the user
Use rules
Eval-condition
Evaluate a single condition and return a confidence level
Reject-premise
conclude
If the rule premise is true, store the conclusion in the database
Every condition has a parameter instance operator value type
Example
(Morphology organism is rod)
Parse-condition
Turn a list of this form into four values
Get-context-data
Ensure that each context is treated in order

16.6 Interacting with Experts

Check-condition
Check if a condition is correct

16.7 Interacting with Clients

Knowledge Output
Solution to the problem
Show why the answer is reasonable
Repport-findings
Output any parameters of an instance
As an explanation mechanism
View the current rule
Rule
Print-rule to translate this and output it
If the user says why, a more detailed explanation of the rule will be given

16.8 MYCIN, a medical diagnosis expert system
16.9 Alternatives to certainty
16.10 History and References
16.11 Exercises
16.12 Answers Translated with www.DeepL.com/Translator (free version)

Chapter 17. Labeling Line Drawings by Constraint Satisfaction

Overview
Line drawing
Labeled Shapes
Rules
Possible Vertices and Labeling

17.1 Line Drawing Labeling Problem
17.2 Combining Constraints and Search
17.3 Labeling Line Drawings

Four Interpretations of Cubes

17.3 Labeled Cubes in the Plane

17.4 Error Checking of Line Drawings
17.5 History and References

Guzman first considered the problem of interpreting a drawing

17.6 Exercises

Chapter 18: Search and the Othello Game
18.1 Rules of the Game
18.2 Choices about Representation
18.3 Evaluating the game
18.4 Anticipatory Search: Minimax Search
18.5 Smart search: Alpha-beta search
18.6 Analysis of the game
18.7 Competitive Othello
18.8 Evaluating Strategies in a Series of Games
18.9 Efficient Search
18.10 Precycle
18.11 Killer moves
18.12 Program for a championship game: Iago and Bill

Mobility
Edge Stability
Combining Evaluation Factors

18.13 Other Techniques

Iterative Deepening Method
Forward pruning
Nonspeculative forward pruning
Aspiration search
Think-Ahead
Hash method and fixed point
Endgame
Meta-reasoning
Learning

18.14 History and Reference Materials
18.15 Exercises
18.16 Answers

Chapter 19: Introduction to Natural Language

Overview
Syntax
Formal and semi-formal methods
Semantics (meaning)

19.1 Parsing with Phrase Structure Grammar

Regenerate the structures that make up a sentence
Discovering in what order to apply generative rules to recognize a sentence

19.2 Extending the grammar and recognizing ambiguity
19.3 Efficient Parsing
19.4 Unknown words
19.5 Parsing with a Step into Semantic Expressions

Sentences are meant to convey ideas, not grammar

19.6 Parsing Using Preference
19.7 Problems with Context-Free Phrase Structure Rules

Unification Grammar

19.8 History and References

chart parser

19.1: Caching partial parses and reusing them when building larger parses

chart parser
A data structure that stores substrings of a parse.
Top-down-parser

19.9 Exercises
19.10 Answers

Chapter 20: Unification Grammar

Overview
Prolog was invented by Alain Colmerauer as a formalism for describing the grammar of French.
The combination of Horn Clauses and unification can form a powerful language for expressing constraints as they appear in natural languages.
How to treat a grammar as a set of logic programming clauses
Clauses define what is and what is not a valid sentence without explicit reference to the parsing or generation process.
The theory can be used to define a very efficient parser.

20.1 Parsing as inference

A sentence can be formed by a noun phrase followed by a verb phrase.
(<- (S ?s) (NP ?np) (VP ?vp) (concat ?np ?vp ?s))
s :word sequence
If there is a sequence of words in a noun phrase, a sequence of words in a verb phrase, and they are concatenated to form ?s, then it is a sentence.
A variable represents a sequence of words.
List of symbols
(<- (S ?s) (concat ?np ?vp ?s) (NP ?np) (VP ?vp))
(<- (S ?s0 ?s2) (NP ?s0 ?s1) (VP ?s1 ?s2)) If the word sequence from S0 to b1 is a noun phrase, and the word sequence from s1 to s2 is a verb phrase. Then s0 to s2 is a sentence. example The boy ate the apple s0=(The boy ate the apple) ?s1=(ate the apple) ?s2=() Accumulator Combination of input and output parameters Difference list 20.2 Definite Clause Grammar EdinburghProlog recognizes assertions called definite clause grammer (DCG) rules. DCG is also called a logical grammar (Rule (S) --> (NP) (VP))
Memo:qita dcg
DCG入門 - Qiita
#はじめにO-PrologにDCGを追加実装しました。このテストでわかったこと、調べたことなどを投稿します。#動機DCGとはdefinite clause grammarの略であり日本語では限…
qiita.com
A dog bites a postman
Its structure follows certain grammatical rules
Sentence -> noun phrase, verb phrase Noun phrase -> article, noun Article ->a noun ->dog Noun ->postman Verb phrase -> verb, noun phrase Verb ->bites
The above rules can be written in almost verbatim form
s --> np,vp. np --> det,n. det -->[a]. n -->[dog]. n -->[postman]. vp --> v,np. v -->[bites].
Sentence sentence s Noun n Noun phrase noun phrase np Verb verb v Limiting verb determiner det Verb phrase verb phrase
You can use the predicate Phrase to check whether a sentence is correct or not
You can also have it generate a sentence that conforms to grammatical rules
| ? - phrase(s,X). X = v_1; X = [a,dog,bites,a,dog]; X = [a,dog,bites,a,postman]; X = [a,postman,bites,a,dog]; X = [a,postman,bites,a,postman]; X = [a,postman,bites,a,postman]; no

20.3 A simple grammar in DCG form
20.4 A DCG grammar with a quantifier
20.5 Preserving Ambiguity about the Valid Range of a Quantifier
20.6 Long-Range Dependencies
20.7 Extensions of DCG rules
20.8 History and references
20.9 Exercises
20.10 Answers

Chapter 21: The Grammar of English
21.1 Noun phrases
21.2 Modifiers
21.3 Noun modifiers
21.4 Limitatives
21.5 Verb phrases
21.6 Adverbs
21.7 Clauses
21.8 Sentences
21.9 XP
21.10 Words
21.11 Dictionary (Lexicon)

Verbs
Auxiliary verbs
Nouns
Pronouns
Proper nouns
adjectives
adverbs
Articles
Base and ordinal numerals
Prepositions

21.12 Dictionary support
21.13 Other Primitives
21.14 Examples
21.15 History and Reference Materials
21.16 Exercises

Part 5: Lisp continued

Chapter 22 Scheme: Uncommon Lisp
22.1 Scheme interpreter
22.2 Extending the syntax with macros
22.3 Authentic tail recursion interpreter
22.4 Throw, Catch, and Call/cc
22.5 Interpreters that support Call/cc
22.6 History and References
22.7 Exercises
22.8 Solutions

Chapter 23 Compiling Lisp
23.1 The Authentic Trailing Recursive Lisp Compiler
23.2 Introducing Call/cc
23.3 Abstract Machines
23.4 Peephole Optimizer
23.5 Languages with Different Lexical Conventions
23.6 History and References
23.7 Exercises
23.8 Answers

Chapter 24 ANSI Common Lisp
24.1 Packages

7 Namespaces

24.2 State and Error Handling

Communicating Errors
Handling Errors

24.3 Pretty Printing
24.4 Series
24.5 Loop Macros

Dissecting a Loop
Repetition Control
End Condition Test Control
Value accumulation
Variable initialization
Conditional execution
Unconditional execution
Other Functions

24.6 Sequence Function

Once-only : A Lesson in Macro Theory
Avoiding Macro Abuse
MAP-INTO
REDUCE with the :key keyword

24.7 Exercises
24.8 Solutions

Chapter 25 Troubleshooting
25.1 Nothing Happens
25.2 Changing a variable has no effect
25.3 Changing a function has no effect
25.4 Values are changing by themselves
25.5 Built-in functions cannot find elements
25.6 Missing Multivalues
25.7 Declarations Ignored
25.8 Is there a problem with the Lisp processor?
25.9 How to Find the Function You Need
25.10 Loop Syntax
25.11 COND Syntax
25.12 CASE Syntax
25.13 LET Syntax and LET* Syntax
25.14 Macro Issues
25.15 Lisp Style Guide

When to Define a Function
When to Define a Variable
When to Define a Lexical Variable
How to Choose a Name
Decisions about parameter order

25.16 Working with Files, Packages, and Systems
25.17 Portability Issues
25.18 Exercises
25.19 Answers

Appendix How to get the code in this book
A.1 FTP: File Transfer Protocol
A.2 Available Software

References
Index
Translator's Afterword