% AI exam -- fall, 1992
% process in plain TeX

\nopagenumbers
\raggedbottom
\magnification = \magstep1
\font\bigbold=cmb10 scaled\magstep1

\def\bx{ \kern 2pt {\vcenter
   {\hrule
   \hbox{\vrule height 6pt \kern 6pt \vrule height 6pt}
   \hrule}} \kern 2pt }    
\def\imp{\ \Rightarrow\   }

\parindent=0pt

\centerline{\bigbold Artificial Intelligence}
\bigskip

If you are taking the {\bf Breadth Exam:}

\hskip20pt Answer any four (4) out of the six Basic questions B1-B6.

\medskip

If you are taking the {\bf Depth Exam:}

\hskip20pt Answer any four (4) out of the six Basic questions B1-B6 and

\hskip20pt answer any four (4) out of the 12 Advanced Depth questions D1-D12.

\bigskip
\bigskip

\parindent=20pt

\centerline {\bf Breadth (Basic) Questions}

\medskip

\item{B1.} 
In {\bf best-first search}, one uses a heuristic estimate, $h'$, of the
actual least cost, $h$, of getting from a node to a goal.
If $h'$ never overestimates $h$, the best-first search (or $A*$) algorithm
is guaranteed to produce an optimal path to a goal.  Explain
why this is true, and give an explicit finite graph where $h'$
does overestimate $h$ and the algorithm produces a path which
is not optimal.

\medskip


\item{B2.} 
Explain the use of  context-free grammars in {\bf parsing natural languages}.
In particular, give such a grammar that produces two distinct
parses for each of the following two sentences:

{\parindent = 30pt
Paint the house with green paint.

Paint the house with the attached garage
}
\item{}
For each sentence, explain which parses correspond to a meaningful
semantic interpretation.
Explain why the two different uses of the word ``paint''
in the first sentence
does {\it not\/} produce any ambiguities here.


\medskip
\item{B3.} 
Convert the following three sentences to 
predicate logic, and then use {\bf resolution} to show that 
the third one follows from the first two:
\itemitem{$\bullet$}
If the AI exam is easy, some students are happy

\itemitem{$\bullet$}
If the AI exam contains a Skolemization question,
no students are happy.

\itemitem{$\bullet$}
If the AI exam contains a Skolemization question,
then the AI exam is not easy.


\medskip

\item{B4.} 
Recent developments in artificial intelligence research
have tended away from earlier dependence on the Von Neumann
computer architecture as a feasible basis on which to build
{\bf models of intelligence}.  There are at least three problems
raised with respect to this architecture, viz., biological
plausibility, serial processing, and the requirement for
explicit programming.  For each of these problems, explain
why it is a problem and show how the alternative
architecture (or architectures) being considered purport to
overcome it.


\medskip


\item{B5.} 
One of the acclaimed strengths of {\bf connectionism} is that it can use
distributed representations.  Describe the concept of a distributed
representation.  Is there anything analogous in symbolic approaches to
knowledge representation?

\smallskip

\item{}
Occasionally, distributed {\it output\/} representations are used when training
a neural network with Rumelhart's backpropagation algorithm.  Propose and
briefly justify a distributed output representation for a system that learns
to classify (isolated) handwritten digits.  How would the digit ``1'' be
represented in your output representation?


\vfill\eject

\item{B6.} 
Consider formalizing, using the {\bf STRIPS representation} scheme, a simple
robot-controlled warehouse.  Assume the warehouse stores two kinds of boxes:
strong and weak.  Strong boxes can support other boxes, while weak ones
cannot.  There can be any number of robots in the warehouse, though some may
be broken at any given time.  Finally, for simplicity, assume there always is
free space on the warehouse floor.

\smallskip

\item{}
Write STRIPS operators for {\it store-on-floor(?robot, ?box)},
{\it store-on-box(?robot, ?box)}, and {\it retrieve(?robot, ?box)}.
({\it ?robot\/} and {\it ?box\/} are variables.)

\itemitem{$\bullet$}
For {\it store-on-floor}, {\it ?robot\/} should move {\it ?box\/}
from the receiving dock to the warehouse floor.

\itemitem{$\bullet$}
For {\it store-on-box}, {\it ?robot\/} should move {\it ?box\/} from the
receiving dock to some stable location on top of another box (if possible).

\itemitem{$\bullet$}
For {\it retrieve}, {\it ?robot\/} should bring {\it ?box\/} to the 
shipping dock.

\item{}
Verbally describe (but do not formalize) any other operators you deem
necessary.  Also, briefly define any predicates you introduce.

\smallskip

\item{}
Briefly state one aspect of a ``real world'', robot-controlled
warehouse that is not easy to capture in the STRIPS formalization.




\bigskip
\bigskip

\centerline{\bf Advanced (Depth) Questions}

\medskip


\item{D1.}  
{\bf Object recognition} in computer vision can be
formulated as a search problem where the search space
is either of local feature correspondences or of poses
(i.e., positions and orientations).

\itemitem{(a)}
One difference between
these two spaces is that one is discrete while the other
is continuous.
What implications does this have for the
search process?  Give your answer in terms of
advantages and disadvantages of
searching each of these two spaces, given this difference.

\itemitem{(b)}
The Generalized Hough Transform could be considered
as performing search over both the correspondence space
and the pose space.  Briefly explain why after outlining
how the technique works.

\itemitem{(c)}
Say we use the Hough transform as a preprocessing step
before searching the correspondence space using some other
method.  Explain how and why
this might be a good or bad idea.


\medskip


\item{D2.}  
One method for three-dimensional shape representation
in computer vision is the {\bf aspect graph}.

\itemitem{(a)}
How is this
graph defined for a polyhedral object?  Include a description
of what the nodes and edges correspond to, and how the pose
of an object is related to this structure.

\itemitem{(b)}
Show the aspect graph for a torus (i.e., a donut-like shape
containing a smooth surface, not a polyhedral approximation).

\itemitem{(c)}
Briefly describe how the aspect graph could be used in
a parallel, object recognition algorithm.  Assume you have
the aspect graph of a single object and the goal is to detect
if that object exists in a given image.  Does your algorithm
determine the exact pose of the object it detects?  Explain how
or why not.

\medskip

\item{D3.} 
Micro-electrode studies with monkeys have found individual
neurons that fire selectively to different faces or other complex
objects within 70 to 200 milliseconds, while it takes roughly
1 to 2 milliseconds for one neuron to fire into and excite another.

\itemitem{A.} Succinctly describe the {\bf primate visual system},
emphasizing its
important structures (such as neurons, rods and cones, retina,
cortical areas, columns, hypercolumns) and how they are linked.

\itemitem{B.} Describe what you think
is the most appropriate structure of processes
to embed into this structure in order to recognize
such complex objects within only 35 to 200 serial steps.
Justify your choices in terms of what is known about brains where you can.


\medskip

\item{D4.} 
You are to develop a computer {\bf vision system} that can recognize a small
number, like 5 or 10, different object-classes (e.g., chair, table, couch,
lamp, vase) that will be input in 3 different ways:
\itemitem{A.} as single frames from a black-white television camera,
\itemitem{B.} as line drawings,
\itemitem{C.} as either of the above,
but converted into a dotted picture, but where
the objects, although
dots and patches, remain easily recognizable by human beings.
\item{}
Describe what you think are the two most promising approaches to explore.
Make clear why you chose these two approaches.
Make sure to explain how you would try to handle the dotted images with each,
and also the many different possible types of each object class (that is,
the intra-object differences).


\medskip


\item{D5.}  
Convert the following sentences to clauses and
derive the empty clause, $\bx$, using {\bf paramodulation} and
{\bf binary resolution}.

{\obeylines\parindent=40pt

$ a \ne 0 $
$ \neg (0 < a*a) $
$ \forall x (x = x) $
$ \forall x ( (0 < x) \vee (x = 0) \vee (x < 0) ) $
$ \forall x \forall y (   ( (0 < x) \wedge (0 < y) ) \imp (0 < x * y))  $
$ \forall x (x < 0 \imp 0 < m(x)) $
$ \forall x \forall y ( x * y = m(x) * m(y)) $


}
\item{}
Here, $x,y,$ are variables and $a,0$ are constants.




\medskip

\item{D6.} 
In {\bf Prolog}, consider the program $P$:
{\obeylines\parindent=40pt\tt
p(a,b).
p(b,c).
anc(X,Y)  :- p(X,Y).
anc(X,Z)  :- p(X,Y), anc(Y,Z).
}
\noindent
\item{}
With this program, the queries, {\tt ?- anc(a,c)} and
{\tt ?- not anc(b,a)} will both get {\tt yes} answers.
Explain why both $anc(a,c)$ and $\neg anc(b,a)$ are logical
consequences of the Clark completion of $P$.


\medskip

\item{D7.} 
Approximately 50\% of English text includes {\bf metaphors} of
some sort.  Discuss ways in which a natural language processing system
might detect and interpret metaphors in the course of
processing large quantities of text of varied subject matter.

\medskip

\item{D8.} 
Discuss the use of syntactic and semantic features in
a {\bf natural language processing} system.  Include a discussion of
inheritance.

\medskip

\item{D9.} 
What is meant by ``{\bf common sense knowledge}''?  Give
examples.  Contrast with other kinds of knowledge.  Why is
it argued that expert systems can not achieve their full
potential unless and until they come to ``possess'' common
sense?  In particular, specify some typical expert system
deficiencies that might thereby be overcome.  Briefly
describe some of the research (e.g., the CYC project led by
Lenat) that bears on this problem and evaluate its
likelihood of success.

\medskip


\item{D10.} 
Outline the essential capabilities of one
``{\bf knowledge representation}'' language (e.g., KRL, KL-ONE,
LOOPS, CLOS); contrast them with the capabilities of
traditional programming languages (e.g., LISP, C); and
contrast them with the capabilities of more recent
``object-oriented'' programming languages (e.g., Object
Pascal, C++, Modula III).  Briefly discuss the problems
that have arisen in attempts to implement AI knowledge
representation languages.  How, if at all, will parallel
architectures contribute to a solution of these problems?



\medskip

\item{D11.} 
Like most AI programs, {\bf inductive learning} algorithms search a space.
Describe the space searched by (a) Quinlan's ID3 algorithm and (b) Rumelhart's
backpropagation algorithm (i.e, what information characterizes a node?).

\smallskip

\item{}
Compare and contrast the two spaces searched.  Several investigators have
found only minor differences in generalization performance when comparing ID3
to backpropagation on common problems.  Discuss this result in light of the
spaces searched.

\smallskip

\item{}
Which search-control strategy does each method follow?  
Briefly describe any evaluation functions used.  How would each
algorithm change if beam search were used instead (or is this impossible)?



\medskip

\item{D12.} 
Assume you have an {\bf inductive learning} algorithm $LA$, along with $N$
positive examples and $M$ negative examples of some concept you wish to learn.
Consider the following three situations.

\itemitem{a.}
You wish to estimate the future accuracy of $LA$ on the concept
represented by the training examples.  Describe and justify an
experimental methodology for estimating this.

\itemitem{b.}
$LA$ has $p$ ``free'' parameters (one such parameter might be the 
number of hidden units in a neural network).  Describe and justify 
an experimental methodology for deciding how to set these parameters
for your sample problem.

\itemitem{c.}
Someone claims algorithm $LA'$ works better than $LA$.
How could you empirically evaluate this claim?



\bye
