CS 3361
Introduction to Artificial Intelligence
Winter 1997
Exam 2
Instructor: Todd Griffith
Teaching Assistant: Kenneth Moorman
1)
(20 points) Describe the following expert systems by listing the PROBLEM, INPUT, OUTPUT, DOMAIN OF EXPERTISE, and REASONING METHOD (i.e. production system or case-based system) for each system. I'm looking for short answers not lengthy descriptions.
DENDRAL
PROBLEM: To identify organic chemicals
INPUT: Empirical formula,
Fragment mass table (from mass spectrograph)
OUTPUT: Organic structure
DOMAIN OF EXPERTISE: chemistry
REASONING METHOD: production system
MYCIN
PROBLEM: Diagnosis and treatment of infectious diseases
INPUT: Features about infectious organisms in a patients culture
OUTPUT: Diagnostic hypotheses about the identity of organism
Advice for therapy
DOMAIN OF EXPERTISE: Medicine (infectious diseases)
REASONING METHOD: Production System
R1 (Also XCONN)
PROBLEM: Configuring the layout of computer system according to given specifications
INPUT: Specifications of components of computer system
OUTPUT: A configurations for the computer system: layouts, connections, etc.
DOMAIN OF EXPERTISE: Computer systems
REASONING METHOD: Production System
CLAVIER
PROBLEM: Determine the loading of parts that optimizes the use of the autoclave.
Spatial layout is critical. Airflow around parts is complex and drastically
effects the results.
INPUT: A list of composite (graphite and fiberglass) parts to be cured
OUTPUT: An autoclave load.
DOMAIN OF EXPERTISE: Autoclave loading
REASONING METHOD: Case-based
2) (9 points) List three problems with expert systems:
Expert systems as production systems:
Inefficient
Opaqueness
Difficult to design
Difficult to debug
Is knowledge really rule based?
Expert systems in general:
Narrow area of expertise
No commonsense knowledge
Utility problem - the more knowledge that is added the less efficient the system becomes
Knowledge Acquisition - difficult to acquire knowledge from experts
(9 points) Describe three strategies which AI researchers have attempted to overcome the problems of expert systems.
CYC - provide commonsense knowledge
Generic Tasks - look for a set of abstract tasks that apply to a wide variety of domains.
Learning - design systems that learn for themselves.
4) (30 points) Trace through the version space algorithm as it learns the concept of "Redheaded Woodpecker." State the Generalized (G) and Specialized (S) version spaces after each example.
Features: Size, head-type, head-color, body-color, stance
Concept to learn: medium ? red ? tree-clinging
Training Examples: (P= positive example, N= negative example)
P = (medium, crowned, red, gray, tree-clinging)
N = (medium, plain, black, brown, perching)
P = (medium, capped, red, gray, tree-clinging)
N = (small, crowned, red, gray, tree-clinging)
P = (medium, plain, red, black&white, tree-clinging)
N = (medium, capped, yellow, black&white, tree-clinging)
|
After training example 1: (GIVEN: 5 free points) |
|||||
|
G = ((? |
? |
? |
? |
?)) |
|
|
S = (medium |
crowned |
red |
gray |
tree-clinging) |
|
|
After training example 2: |
|||||
|
G = (( ? |
crowned |
? |
? |
?) |
|
|
(? |
? |
red |
? |
?) |
|
|
(? |
? |
? |
gray |
?) |
|
|
(? |
? |
? |
? |
tree-clinging)) |
|
|
S = (medium |
crowned |
red |
gray |
tree-clinging) |
|
|
After training example 3: |
|||||
|
G= ((? |
? |
red |
? |
?) |
|
|
(? |
? |
? |
gray |
?) |
|
|
(? |
? |
? |
? |
tree-clinging)) |
|
|
S = (medium |
crowned |
red |
gray |
tree-clinging) |
|
|
After training example 4: |
|||||
|
G= ((medium |
? |
red |
? |
?) |
|
|
(medium |
? |
? |
gray |
?) |
|
|
(medium |
? |
? |
? |
tree-clinging)) |
|
|
S = (medium |
? |
red |
gray |
tree-clinging) |
|
|
After training example 5: |
|||||
|
G = ((medium |
? |
red |
? |
?) |
|
|
(medium |
? |
? |
? |
tree-clinging)) |
|
|
S = (medium |
? |
red |
? |
tree-clinging) |
|
|
After training example 6: |
|||||
|
G = ((medium |
? |
red |
? |
tree-clinging)) |
|
|
S = (medium |
? |
red |
? |
tree-clinging) |
|
5) (25 points) Given the following sentence: "He drank the milkshake with a straw."
(5 points) Construct a lexicon for the sentence.
PRONOUNS = (HE)
NOUNS = (MILKSHAKE STRAW)
VERBS = (DRANK)
DETERMINERS = (THE A)
PREPOSITIONS = (WITH)
(5 points) Construct a grammar which can be used to parse the sentence, using the following as the first rule:
Rule 1: S --> NP VP (where S = Sentence, NP = noun phrase, and VP = verb phrase):
Rule 2: NP ---> noun | pronoun
Rule 3: VP --> verb [det] NP [PP]
Rule 4: PP ---> prep [det] noun
(5 points) Construct a parse tree for the sentence using the grammar you constructed.
S
NP VP
pronoun verb det NP PP
He drank . the noun prep det noun
milkshake with a straw
d) (5 points) Construct an augmented transition network (ATN) for the grammar you constructed in part b.
noun verb noun prep noun
S1 S2 S3 S4 S6 S8
det. noun det. noun
pronoun S5 S7
d) (5 points) Construct a recursive transition network (RTN) for the grammar in part b.
NP VP
S1 S2 S3
VP: NP: PP:
verb NP noun prep. noun
S1' S2' S3' S1'' S2'' S1''' S2''' S4'''
det. NP pronoun
S4' det. noun
S3'''
6) (7 points) Define "procedural semantics." What is one advantage of using them in natural language systems?
Knowing = knowing how to do.
Understanding = translating language into procedures that perform actions.