
% AI exam -- fall, 1990
\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 }    % box, as in resolution

\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 13 Advanced Depth questions D1-D13.

\bigskip
\bigskip

\parindent=20pt

\centerline {\bf Breadth (Basic) Questions}

\medskip

\item{B1.}
\itemitem{(a)}
State, as a single sentence in {\it propositional logic},
the resolution principle for propositional
logic.  Assume each clause contains exactly two literals.
\itemitem{(b)}
Prove using resolution that your answer for (a) is a tautology.

\medskip



\item{B2.}
Consider a {\it card game\/} in which two players take turns
removing one card from either the right or left end of a
row of cards.  Initially, the row contains five cards
labeled alternately 1 and 0.
The leftmost card is a 1.
The player who removes the last card wins if that card is
labeled 1.  Otherwise that player loses.
\itemitem{(a)}
Draw the AND/OR graph description of this problem assuming
you move second.
\itemitem{(b)}
Show that you, the second player, can always win the game.
\itemitem{(c)}
Assuming you wanted to use
state-space search to address this problem.  How would
you represent a state?
Also, specify one operator you would use.


\medskip

\item{B3.}
Precisely define the problem addressed by {\it classical planners}, such as
Chapman's TWEAK.  Next, define {\it non-linear planning}.  Why might it be
advantageous for a planner to be non-linear (as opposed to simply being
linear)?  State any disadvantages of non-linear planning with respect to
linear planning or argue why there are none.  Finally, discuss why one might
want to interleave planning and execution in a practical planner.

\medskip

\item{B4.}
Precisely define the task of {\it inductive learning from classified
examples}.  State {\bf two} of the most important properties of a learning
algorithm.  Justify your choices.  Finally, select two existing learning
systems and briefly sketch how each tackles the inductive learning task.

\medskip

\item{B5.}
Characterize the ``{\it physical symbol system}'' paradigm
for artificial intelligence research.  Identify {\bf one}
hard problem that has been ``paradigm threatening'' for this
approach to AI?   How successful is the ``{\it connectionist}''
paradigm in addressing and solving this problem?
Identify  {\bf one} hard problem that has been ``paradigm threatening''
for the connectionist approach, and discuss how well
this problem has been addressed in the physical symbol system paradigm.

\medskip

\vfill\eject


\item{B6.}
Evaluate the following proposals for developing a
{\it knowledge representation\/} useful for a general purpose
artificial intelligence:
\itemitem{(a)} Just use the language of formal logic.
\itemitem{(b)} Just use natural language.
\item{}
In your answer indicate the extent to which these proposals
have been taken seriously, and what has been the resulting success or failure.

\bigskip
\bigskip

\centerline{\bf Advanced Depth Questions}
\medskip

\item{D1.}
The major issue in {\it inductive learning\/} is the choice of a good
{\it inductive bias}.  First, define {\it inductive bias\/} and explain its
importance.  Bias typically takes one of two forms: (1) a {\it restricted
hypothesis space bias\/} and (2) a {\it preference bias}.  In the former, only
a subset of all possible answers is considered, while in the later the
possible answers are somehow ordered.  For each of these two types of bias,
name a learning system that uses it and discuss the details of how the system
addresses the issue of inductive bias.  Finally, briefly sketch your design for
a system that {\it learns\/} how to improve its inductive bias.

\medskip

\item{D2.}
An important goal of {\it machine learning\/} is to take advantage of
preexisting knowledge relevant to the learning task at hand.
Explanation-based learning (EBL) provides one approach to achieving this goal.
However, EBL suffers from the problem of {\it imperfect domain theories}.
Mitchell et al. decomposed imperfect domain theories into three categories;
describe these three categories and illustrate them with simple examples.
Finally, discuss how inductive learning approaches could be used to help
address {\bf two} of these three problems with EBL.  Be as specific as
possible and refer to existing systems whenever you can.

\medskip

\item{D3.}
An important issue in {\it neural network\/} (connectionist) learning is the
choice of a good network topology.  Explain why this is so, and consider the
two extreme cases: zero hidden units and an exponential number of hidden units
(exponential in terms of the number of input units).  Some researchers have
advocated adding hidden units as needed.  Why does this make sense?  Briefly
sketch your design of a system that adds hidden units as needed.  Be sure to
discuss how your system would decide to add units and its technique for wiring
them into the existing neural network.

\medskip


\item{D4.}
There are many different ways to represent {\it 3D object
models\/} for use in 3D, model-based object recognition.
\itemitem{(a)}  Define the (i) aspect graph, and (ii) generalized cylinder
based approaches to modeling 3D objects.
\itemitem{(b)}  Briefly explain how each of these two representations
could be used to solve for the viewpoint corresponding to
a given, single image of a scene containing a single, known object.

\medskip

\vfill\eject


\item{D5.}  Define {\it scale-space\/} as applied to (i) a one-dimensional
grayscale image, and (ii) a planar curve.
Next, describe procedures for segmenting scale-space
images/curves, showing the correspondence between the segmented
features in scale-space and their parts in the image or curve.

\medskip

\item{D6.}
Monkeys' {\it neurons\/} take 1-2 milliseconds to fire, yet monkeys
recognize complex objects like a particular person's face in 70-200
milliseconds (that is, a particular neuron will fire to a particular face,
other neurons to other faces, etc.).
Therefore the serial depth of processing is at most 40-200 steps.
Describe the type of {\it computer vision\/} system that you feel
would come closest to recognition in fewer than 200 serial steps,
making sure to explain, and trying to justify, your choices.
Describe the hardware of processor(s) you would use to execute
this system as well as the structure of processes, explaining
how processes would be mapped into processors for sufficiently fast execution.

\medskip

\item{D7.}
Computer vision is often characterized as matching internally stored
``models'' of the different objects
to be recognized, and choosing the best match.
Describe two different computer vision systems, making clear how
each represents and uses these models.
Consider the following problems:  

\itemitem{A.} Recognize 100
different peoples' faces, no matter what the expression or
rotation; 

\itemitem{B.} Recognize any possible chair, table, and 20-30 other
different kinds of furniture; 

\itemitem{C.} Recognize any of the many thousands
of objects that we human beings recognize, over all their variations.

\item{}
Explain and describe the kinds of models you would use, and how you
would develop and determine what are the necessary models.
Also describe and explain two approaches to applying all these
models:  one that ignores issues of how long that will take; and
a second that tries to recognize in real time, or at least as fast as possible. 

\medskip

\item{D8.}
Why is it important when building an {\it expert system\/}
to maintain a clean and clearcut distinction between
knowledge base and inference engine?  In what ways is the
distinction related to the distinction between declarative
representation of knowledge and procedural representation of
knowledge?   How can the reason for the distinction between
knowledge base and inference engine be realized if the
knowledge base is constituted of procedural rules?  How can
it be realized if the knowledge base is constituted of
objects?

\medskip

\item{D9.}
Why is it important to incorporate explanation
capabilities in {\it expert systems\/}?  Give examples of 
such capabilities.  Compare their usefulness to a 
Lisp function trace.  Contrast different kinds of 
knowledge representation in terms of their suitability 
for enabling explanation.

\medskip

\item{D10.}
{\it Prolog\/} may be considered
to be a special purpose resolution prover, which
works only on Horn clauses and has a very specific search procedure.
In what sense is this true, and in what sense is it false?

\medskip

\vfill\eject

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

{\obeylines\parindent=40pt

$\forall x (x = x) $
$\forall x,y,z ( x * (y * z) = (x * y) * z ) $
$\forall x (x * inv(x) = e). $
$\forall x (x * e = x). $
$\forall x (e * x = x). $
$\neg \forall x (inv(inv(x)) = x ) $
}
\noindent

\item{}
An informal proof would say:  $x = x*e = x * (inv(x) * inv(inv(x)) ) =
(x * (inv(x)) * inv(inv(x))  = e * inv(inv(x)) = inv(inv(x))  $.

\medskip


\item{D12.}
Compare and contrast the achievements, potential, and  limitations
of {\it natural language\/} learning programs in neural net models
versus high-level symbolic models.

\medskip

\item{D13.}
Explain and evaluate probabilistic techniques for resolving
ambiguities in {\it natural language\/} processing.  Include a discussion
of any experimental justification for the techniques, and a critique
from the point of view of linguistic theory.

\bye



