% 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