Spring 2003 Intelligent Systems Qualifying Exam

CORE Section – Everyone must answer 2 of the following 4 questions
 
CORE-1.
(a) Why did most researchers believe, even a couple of years ago, that heuristic search alone was insufficient to solve STRIPS-like planning problems?

(b) Several recent planners from artificial intelligence do use heuristic search to solve STRIPS-like planning problems efficiently. Describe the insight(s) that made this possible.

(c) Some researchers argue that heuristic search-based planners (such as HSP) and GraphPlan-based planners are closely related even though they appear to be very different. In what ways are they related?

(d) Why do most heuristic search-based planners (such as HSP) use inadmissible heuristics? Why do they, in addition, use a weighted form of A* (that uses f = g + w h for a weight w > 1, rather than f = g + h). What are the advantages and disadvantages of both of these design decisions? Why are they necessary?

(e) What are the limitations of heuristic search-based planners (for example, which kinds of planning problems are difficult for them to handle)?  Make suggestions for how to augment heuristic search-based planners to address these limitations.

CORE-2. Even though statistical learning methods have been very popular recently there are occasions when memory-based (aka instance-based) approaches to machine learning might out perform other methods such as parametric density estimators or regression methods or various neural nets.
(a) What would be such occasions?
(b) Are memory based approaches most suited for high or low-dimensional learning problems?  Why?  
(c) In which of the following applications do you think a memory-based method could be put to good use: automatic loan decisions for on-line banking, credit card fraud detection, diagnosis of diseases from a list of symptoms, voice recognition, handwritten digit recognition. Why or why not?

CORE-3. Contrast the learning process of knowledge compilation in ACT with the learning process of adaptation and indexing in Case-Based Reasoning. What sorts of cognitive tasks are handled best by each model?

CORE-4. Roger Schank once defined AI as "the science of building computers that can learn from their experiences." Tom Mitchell, in his well-known textbook on Machine Learning, defines "learning" as follows: A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in t, as measured by P, improves with experience E.

Recently, Georgia Tech's Hybrot project has been been getting a lot of airplay (see http://www.gatech.edu/news-room/release.php?id=125).

(a). Does the Hybrot learn according to Mitchell's definition? Explain.

(b). Is the Hybrot intelligent? Explain.

MACHINE LEARNING Section – If you have chosen a Machine Learning specialization you must answer 2 of the following 4 questions.

ML-1.  One important issue in reinforcement learning is the so-called exploration-exploitation problem.

(a) Explain why there can be a conflict between exploration and exploitation in reinforcement learning.  Give an example of a hypothetical Markov decision problem (MPD) that illustrates the issue.

(b) Describe a (sufficiently large) class of MDP problems where there is no conflict between exploration and exploitation and argue why there is no such conflict.

(c) Describe a (sufficiently large) class of MDP problems where there is a conflict between exploration and exploitation but it is known how to find an optimal balance between exploration and exploitation.

(d) Describe different ways how artificial intelligence researchers have addressed the exploration-exploitation problem heuristically.


ML-2. You have to develop a controller for a soccer-playing robot.  The robot can sense the angular direction and approximate distance to both the ball and the goal, assuming they are within the finite field of view of the sensing system.  The robot can also sense the position of the single opponent robot.  The controller can drive the left and right drive wheels independently.  

Let’s assume the robot has two basic tasks.  One is to score a goal whenever it has the ball, and the other is to prevent another robot from scoring against him.  

(a) Design a reinforcement learning method for each of these two tasks.  Would they be different in any significant way? How would you try to train the robot (for example would you want the opponent on the field when learning to score?)
(b) How would you learn to switch between strategies?  How does switching between these strategies differ from just having a single strategy of “try to win”?
(c) Suppose the opponent robot is learning while your robot is playing.  Would that change anything in the strategy?  Would it affect the nature and size of your state space?

ML-3. Drew McDermott used to teach that machine learning was 10% computation and 90% integration.  Explain what he meant and explain whether or not  you think that new machine learning techniques and algorithms change  these percentages any.

ML-4.  Discuss the relationship between Hidden Markov Models and Finite State Machines on the one hand, and Graphical Models on the other hand. For the latter, do this both in terms of modeling assumptions as well as inference methods used. In particular, what is the relationship between the Baum-Welch algorithm and belief propagation, if any? Finally, in some HMM variants there are links not only between successive states, but also between states two or even three time steps apart. How does that affect inference and parameter learning?


COMPUTER VISION/PERCEPTION  Section – If you have chosen a Computer Vision specialization you must answer 2 of the following 5 questions.

CV-1.  Discuss how factorization approaches to structure and motion can be generalized to deal with multiple objects. What is the relationship, if any, between this work and Michal Irani's paper on "Multi-Frame Optical Flow Estimation Using Subspace Constraints".

CV-2. Discuss how snake-based tracking of deforming objects could be implemented using particle filters. Is there an advantage to using this rather than the physics-based approach by Kass et al?   In each framework, how would you incorporate prior knowledge on shape?  Finally, in which  applications would you use one method versus the other?

CV-3.   Photometric stereo is a technique for recovering the shape of an object (its needle-map) from multiple images acquired under different lighting conditions using a single fixed camera.
(a) Why does the conventional technique assume that the object is Lambertian?

(b) What would happen if this technique were applied to a spherical mirror?  How could you fix it for this case?

(c) A more realistic reflectance model for painted or plastic objects is the Phong model, which combines Lambertian reflectance with a specular lobe. Discuss how a conventional photometric stereo algorithm could be extended to cope with objects that follow a Phong-shading model. Be as concrete as possible.

CV-4.. PCA is a standard dimensionality reduction technique which has been applied in a variety of vision domains from face recognition to texture analysis. From the standpoint of pattern classification, what are the advantages and disadvantages of PCA? Discuss the computational issues that arise in applying PCA to image data. Suppose that the input for a particular object detection task is a binary image. (You can assume that the image has already been segmented so that all of the pixels come either from the target of interest or from the nontarget class). Give specific examples of binary images (for object and non-object classes) for which PCA would work well and for which PCA would work poorly. Give examples of image classes for which PCA works well and explain why. What alternatives to PCA are there for situations where it does not work well?

CV-5. When modeling of the human vision system began, the computational analysis focused on linear time-invariant systems theory: frequency tuned receptive fields, spatial (or spatial-temporal) filters, summation properties of detection.  Eventually though the presence of non-linearities became clear. Discuss at least three nonlinear computations in the human visual system and describe what capabilities that non-linearity provides.  Make sure at least two of them are above the level of the retina.