Copy Link
Add to Bookmark
Report
AIList Digest Volume 2 Issue 004
AIList Digest Thursday, 5 Jan 1984 Volume 2 : Issue 4
Today's Topics:
Course - PSU's First AI Course (continued)
----------------------------------------------------------------------
Date: 31 Dec 83 15:23:38-PST (Sat)
From: harpo!floyd!clyde!akgua!psuvax!bobgian @ Ucb-Vax
Subject: PSU's first AI course -- part 3/6 (First Exam)
Article-I.D.: psuvax.383
[The intent and application of the following three exams was described
in the previous digest issue. The exams were intended to look difficult
but to be fun to take. -- KIL]
******** ARTIFICIAL INTELLIGENCE -- First Exam ********
The field of Artificial Intelligence studies the modeling of human
intelligence in the hope of constructing artificial devices that display
similar behavior. This exam is designed to study your ability to model
artificial intelligence in the hope of improving natural devices that
display similar behavior. Please read ALL the questions first, introspect
on how an AI system might solve these problems, then simulate that system.
(Please do all work on separate sheets of paper.)
EASY PROBLEM:
The rules for differentiating polynomials can be expressed as follows:
IF the input is: (A * X ^ 3) + (B * X ^ 2) + (C * X ^ 1) + (D * X ^ 0)
THEN the output is:
(3 * A * X ^ 2) + (2 * B * X ^ 1) + (1 * C * X ^ 0) + (0 * D * X ^ -1)
(where "*" indicates multiplication and "^" indicates exponentiation).
Note that all letters here indicate SYMBOLIC VARIABLES (as in algebra),
not NUMERICAL VALUES (as in FORTRAN).
1. Can you induce from this sample the general rule for polynomial
differentiation? Express that rule in English or Mathematical notation.
(The mathematicians in the group may have some difficulty here.)
2. Can you translate your "informal" specification of the differentiation
rule into a precise statement of an inference rule in a Physical Symbol
System? That is, define a set of objects and relations, a notation for
expressing them (hint: it doesn't hurt for the notation to look somewhat
like a familiar programming language which was invented to do mathematical
notation), and a symbolic transformation rule that encodes the rule of
inference representing differentiation.
3. Can you now IMPLEMENT your Physical Symbol System using some familiar
programming language? That is, write a program which takes as input a
data structure encoding your symbolic representation of a polynomial and
returns a data structure encoding the representation of its derivative.
(Hint as a check on infinite loops: this program can be done in six
or fewer lines of code. Don't be afraid to define a utility function
or two if it helps.)
SLIGHTLY HARDER PROBLEM:
Consider a world consisting of one block (a small wooden cubical block)
standing on the floor in the middle of a room. A fly is perched on the
South wall, looking North at the block. We want to represent the world
as seen by the fly. In the fly's world the only thing that matters is
the position of that block. Let's represent the world by a graph
consisting of a single node and no links to any other nodes. Easy enough.
4. Now consider a more complicated world. There are TWO blocks, placed
apart from each other along an East/West line. From the fly's point of
view, Block A (the western block) is TO-THE-LEFT-OF Block B (the eastern
block), and Block B has a similar relationship (TO-THE-RIGHT-OF) to
Block A. Draw your symbolic representation of the situation as a graph
with nodes for the blocks and labeled links for the two relationships
which hold between the blocks. (Believe it or not, you have just invented
the representation mechanism called a "semantic network".)
5. Now the fly moves to the northern wall, looking south. Draw the new
semantic network which represents the way the blocks look to him from his
new vantage point.
6. What you have diagrammed in the above two steps is a Physical Symbol
System: a symbolic representation of a situation coupled with a process
for making changes in the representation which correspond homomorphically
with changes in the real world represented by the symbol system.
Unfortunately, your symbol system does not yet have a concrete
representation for this changing process. To make things more concrete,
let's transform to another Physical Symbol System which can encode
EXPLICITLY the representation both of the WORLD (as seen by the fly)
and of HOW THE WORLD CHANGES when the fly moves.
Invent a representation for your semantic network using some familiar
programming language. Remember what is being modeled are OBJECTS (the
blocks) and RELATIONS between the objects. Hint: you might like to
use property lists, but please feel no obligations to do so.
7. Now the clincher which demonstrates the power of the idea that a
physical symbol system can represent PROCESSES as well as OBJECTS and
RELATIONS. Write a program which transforms the WORLD-DESCRIPTION for
FLY-ON-SOUTH-WALL to WORLD-DESCRIPTION for FLY-ON-NORTH-WALL. The
program should be a single function (with auxiliaries if you like)
which takes two arguments, the symbol SOUTH for the initial wall and
NORTH for target wall, uses a global symbol whose value is your semantic
network representing the world seen from the south wall, and returns
T if successful and NIL if not. As a side effect, the function should
CHANGE the symbolic structure representing the world so that afterward
it represents the blocks as seen by the fly from the north wall.
You might care to do this in two steps: first describing in English or
diagrams what is going on and then writing code to do it.
8. The world is getting slightly more complex. Now there are four
blocks, A and B as before (spread apart along an East/West line), C
which is ON-TOP-OF B, and D which is just to the north of (ie, in back
of when seen from the south) B. Let's see your semantic network in
both graphical and Lisp forms. The fly is on South wall, looking North.
(Note that we mean "directly left-of" and so on. A is LEFT-OF B but has
NO relation to D.)
9. Generalize the code you wrote for question 4 (if you haven't already)
so that it correctly transforms the world seen by the fly from ANY of
the four walls (NORTH, EAST, SOUTH, and WEST) to that seen from any other
(including the same) wall. What I mean by "generalize" is don't write
code that works only for the two-block or four-block worlds; code it so
it will work for ANY semantic network representing a world consisting of
ANY number of blocks with arbitrary relations between them chosen from
the set {LEFT-OF, RIGHT-OF, IN-FRONT-OF, IN-BACK-OF, ON-TOP-OF, UNDER}.
(Hint: if you are into group theory you might find a way to do this with
only ONE canonical transformation; otherwise just try a few examples
until you catch on.)
10. Up to now we have been assuming the fly is always right-side-up.
Can you do question 6 under the assumption that the fly sometimes perches
on the wall upside-down? Have your function take two extra arguments
(whose values are RIGHT-SIDE-UP or UPSIDE-DOWN) to specify the fly's
vertical orientation on the initial and final walls.
11. Up to now we have been modeling the WORLD AS SEEN BY THE FLY. If
the fly moves, the world changes. Why is this approach no good when
we allow more flies into the room and wish to model the situation from
ANY of their perspectives?
12. What can be done to fix the problem you pointed out above? That is,
redefine the "axioms" of your representation so it works in the "multiple
conscious agent" case. (Hint: new axioms might include new names for
the relations.)
13. In your new representation, the WORLD is a static object, while we
have functions called "projectors" which given the WORLD and a vantage
point (a symbol from the set {NORTH, EAST, SOUTH, WEST} and another from
the set {RIGHT-SIDE-UP, UPSIDE-DOWN}) return a symbolic description (a
"projection") of the world as seen from that vantage point. For the
reasons you gave in answer to question 11, the projectors CANNOT HAVE
SIDE EFFECTS. Write the projector function.
14. Now let's implement a perceptual cognitive model builder, a program
that takes as input a sensory description (a symbolic structure which
represents the world as seen from a particular vantage point) and a
description of the vantage point and returns a "static world descriptor"
which is invariant with respect to vantage point. Code up such a model
builder, using for input a semantic network of the type you used in
questions 6 through 10 and for output a semantic network of the type
used in questions 12 and 13. (Note that this function in nothing more
than the inverse of the projector from question 13.)
******** THAT'S IT !!! THAT'S IT !!! THAT'S IT !!! ********
SOME HELPFUL LISP FUNCTIONS
You may use these plus anything else discussed in class.
Function Argument description Return value Side effect
PUTPROP <symbol> <value> <property-name> ==> <value> adds property
GET <symbol> <property-name> ==> <value>
REMPROP <symbol> <property-name> ==> <value> removes property
***********************************************************************
-- Bob Giansiracusa
------------------------------
Date: 31 Dec 83 15:25:34-PST (Sat)
From: harpo!floyd!clyde!akgua!psuvax!bobgian @ Ucb-Vax
Subject: PSU's first AI course -- part 4/6 (Second Exam)
Article-I.D.: psuvax.384
1. (20) Why are you now sitting on this side of the room? Can you cite
an AI system which used a similar strategy in deciding what to do?
2. (10) Explain the difference between vs CHRONOLOGICAL and DEPENDENCY-
DIRECTED backtracking.
3. (10) Compare and contrast PRODUCTION SYSTEMS and SEMANTIC NETWORKS as
far as how they work, what they can represent, what type of problems are
well-suited for solution using that type of knowledge representation.
4. (20) Describe the following searches in detail. In detail means:
1) How do they work?? 2) How are they related to each other??
3) What are their advantages?? 4) What are their disadvantages??
Candidate methods:
1) Depth-first 2) Breadth-first
3) Hill-climbing 4) Beam search
5) Best-first 6) Branch-and-bound
7) Dynamic Programming 8) A*
5. (10) What are the characteristics of good generators for
the GENERATE and TEST problem-solving method?
6. (10) Describe the ideas behind Mini-Max. Describe the ideas behind
Alpha-Beta. How do you use the two of them together and why would you
want to??
7. (50) Godel's Incompleteness Theorem states that any consistent and
sufficiently complex formal system MUST express truths which cannot be
proved within the formal system. Assume that THIS theorem is true.
1. If UNPROVABLE, how did Godel prove it?
2. If PROVABLE, provide an example of a true but unprovable statement.
8. (40) Prove that this exam is unfinishable correctly; that is, prove
that this question is unsolvable.
9. (50) Is human behavior governed by PREDESTINATION or FREE-WILL? How
could you design a formal system to solve problems like that (that is, to
reason about "non-logical" concepts)?
10. (40) Assume only ONE question on this exam were to be graded -- the
question that is answered by the FEWEST number of people. How would you
decide what to do? Show the productions such a system might use.
11. (100) You will be given extra credit (up to 100 points) if by 12:10
pm today you bring to the staff a question. If YOUR question is chosen,
it will be asked and everybody else given 10 points for a correct answer.
YOU will be given 100 points for a correct answer MINUS ONE POINT FOR EACH
CORRECT ANSWER GIVEN BY ANOTHER CLASS MEMBER. What is your question?
-- Bob Giansiracusa
------------------------------
Date: 31 Dec 83 15:27:19-PST (Sat)
From: harpo!floyd!clyde!akgua!psuvax!bobgian @ Ucb-Vax
Subject: PSU's first AI course -- part 5/6 (Third Exam)
Article-I.D.: psuvax.385
1. What is the sum of the first N positive integers? That is, what is:
[put here the sigma-sign notation for the sum]
2. Prove that the your answer works for any N > 0.
3. What is the sum of the squares of the first N positive integers:
[put here the sigma-sign notation for the sum]
4. Again, prove it.
5. The proofs you gave (at least, if you are utilizing "traditional"
mathematical background,) are based on "mathematical induction".
Briefly state this principle and explain why it works.
6. If you are like most people, your definition will work only over the
domain of NATURAL NUMBERS (positive integers). Can this definition be
extended to work over ANY countable domain?
7. Consider the lattice of points in N-dimensional space having integer
valued coordinates. Is this space countable?
8. Write a program (or express an algorithm in pseudocode) which returns
the number of points in this space (the one in #7) inside an N-sphere of
radius R (R is a real number > 0).
9. The domains you have considered so far are all countable. The problem
solving methods you have used (if you're "normal") are based on
mathematical induction. Is it possible to extend the principle of
mathematical induction (and recursive programming) to NON-COUNTABLE
domains?
10. If you answered #9 NO, why not? If you answered it YES, how?
11. Problems #1 and #3 require you to perform INDUCTIVE REASONING
(a related but different use of the term "induction"). Discuss some of
the issues involved in getting a computer to perform this process
automatically. (I mean the process of generating a finite symbolic
representation which when evaluated will return the partial sum for
an infinite sequence.)
12. Consider the "sequence extrapolation" task: given a finite sequence
of symbols, predict the next few terms of the sequence or give a rule
which can generate ALL the terms of the sequence. Is this problem
uniquely solvable? Why or why not?
13. If you answered #12 YES, how would you build a computer program to
do so?
14. If you answered #12 NO, how could you constrain the problem to make
it uniquely solvable? How would you build a program to solve the
constrained problem?
15. Mankind is faced with the threat of nuclear annihilation. Is there
anything the field of AI has to offer which might help avert that threat?
(Don't just say "yes" or "no"; come up with something real.)
16. Assuming mankind survives the nuclear age, it is very likely that
ethical issues relating to AI and the use of computers will have very
much to do with the view the "person on the street" has of the human
purpose and role in the Universe. In what way can AI researchers plan
NOW so that these ethical issues are resolved to the benefit of the
greatest number of people?
17. Could it be that our (humankind's) purpose on earth is to invent
and build the species which will be the next in the evolutionary path?
Should we do so? How? Why? Why not?
18. Suppose you have just discovered the "secret" of Artificial
Intelligence; that is, you (working alone and in secret) have figured
out a way (new hardware, new programming methodology, whatever) to build
an artificial device which is MORE INTELLIGENT, BY ANY DEFINITION, BY
ANY TEST WHATSOEVER, that any human being. What do you do with this
knowledge? Explain the pros and cons of several choices.
19. Question #9 indicates that SO FAR all physical symbol systems have
dealt ONLY with discrete domains. Is it possible to generalize the
idea to continuous domains? Since many aspects of the human nervous
system function on a continuous (as opposed to discrete) basis, is it
possible that the invention of CONTINUOUS PHYSICAL SYMBOL SYSTEMS might
provide part of the key to the "secret of intelligence"?
20. What grade do you feel you DESERVE in this course? Why? What
grade do you WANT? Why? If the two differ, is there anything you
want to do to reduce the difference? Why or Why Not? What is it?
Why is it (or is it not) worth doing?
--
Spoken: Bob Giansiracusa
Bell: 814-865-9507
Bitnet: bobgian@PSUVAX1.BITNET
Arpa: bobgian%psuvax1.bitnet@Berkeley
CSnet: bobgian@penn-state.csnet
UUCP: allegra!psuvax!bobgian
USnail: Dept of Comp Sci, Penn State Univ, University Park, PA 16802
------------------------------
End of AIList Digest
********************
