_A_r_t_i_f_i_c_a_l _I_n_t_e_l_l_i_g_e_n_c_e If you are taking the Breadth Exam: 9 Answer any four (4) out of the eight Basic questions B1-B8. If you are taking the Depth Exam: 9 Answer any four (4) out of the eight Basic questions B1-B8 and answer any four (4) out of the 13 Advanced Depth questions D1-13. _B_r_e_a_d_t_h (_B_a_s_i_c) _Q_u_e_s_t_i_o_n_s B1. (a) A _c_o_n_s_t_r_a_i_n_t _p_r_o_p_a_g_a_t_i_o_n problem can be described using graph theory terminology. From this viewpoint, what do the nodes and arcs represent and what role do they play in constraint propagation? (b) Give an example of an application of this technique in AI, briefly describing how it works. (c) Why are constraint propagation algorithms usually preferable over straightforward chronological backtracking techniques? B2. The _F_i_n_d-_P_a_t_h problem is the following: given an object with initial position and orientation, a goal position and orientation, and a set of stationary obstacles, find a path from the initial position to the goal position which avoids collisions with all obstacles along the way. (a) Define an adequate representation for a two-dimensional world (i.e. all objects and obstacles are two-dimensional polygons). (b) Define a search algorithm using your representation in (a) which plans a sequence of "safe" moves. Give an example. B3. The concept of a _h_i_e_r_a_r_c_h_y been used in each of the following areas: (a) planning, (b) blackboards, and (c) temporal reasoning. For two of these areas, give a brief description of someone's work which used hierarchies in order to help solve their problem. Also indicate how hierarchies affect both solution speed and completeness of finding a solution for each of these two cases. 9 9 B4. It has been stated that some types of _m_a_c_h_i_n_e _l_e_a_r_n_i_n_g can be viewed in terms of heuristic state-space search. From this perspective, what are the _s_t_a_t_e_s, _o_p_e_r_a_t_o_r_s, _h_e_u_r_i_s_t_i_c_s, and _g_o_a_l _s_t_a_t_e? Briefly describe two state- transition operators and the role of heuristics in Michalski's AQ system. B5. What constitutes a _r_u_l_e-_b_a_s_e_d _p_r_o_d_u_c_t_i_o_n _s_y_s_t_e_m that uses conflict resolution? Describe one example of such a system that has been developed for a practical application, making clear how it works and how well it performs. Describe how such a system can be used to implement a "discrimination net," and discuss the advantages and the disadvantages of such an implementation. B6. Compare _s_e_m_a_n_t_i_c _n_e_t_w_o_r_k_s and _c_o_n_n_e_c_t_i_o_n_i_s_t _n_e_t_w_o_r_k_s. How do they differ; how are they similar? What are the strengths and the weaknesses of each - now and into the future? Define and describe each, and give one example of a system for each. B7. Define, describe, and contrast _b_e_s_t-_f_i_r_s_t _s_e_a_r_c_h and the _A* _a_l_g_o_r_i_t_h_m. How would you use each in a diagnostic or trouble-shooting program? (That is, provide an outline of the whole program, showing where - if anywhere - each of these algorithms would fit.) Which is more appropriate, and why? B8. Consider the following sentences: 9 I saw the man with a telescope. I see the man with a telescope. John saw the man with a telescope. 9 List as many _s_e_m_a_n_t_i_c interpretations for each sentence as you can. Associate a _s_y_n_t_a_c_t_i_c tree structure with each interpretation. Explain why the number of interpretations for some of these sentences may vary. 9 9 _A_d_v_a_n_c_e_d _D_e_p_t_h _Q_u_e_s_t_i_o_n_s D1. In order to implement a high-level vision procedure efficiently, models of individual objects and collections of objects must be represented using multiple descriptions so that we can quickly focus the computation on a small number of possible alternative interpretations. That is, since one does not usually know in advance what aspect or features of objects will be present in the images, we must maintain several different types and levels of description. Marr called this the "reference-window problem." This is especially difficult in the problem of recognizing three- dimensional objects in arbitrary positions in a complex scene which is viewed from arbitrary positions. Give an expanded explanation of what this problem is in 3-D, high- level computer vision (give some of the main issues and difficulties), give descriptions of what kinds of different representations may be needed and why, and give examples from previous research of how other people have approached this problem and their solutions or partial solutions. D2. Give as precise a description as possible of what _R_e_l_a_x_a_t_i_o_n _L_a_b_e_l_i_n_g _P_r_o_c_e_s_s_e_s are used for in computer vision, and how they are defined. Give a detailed description of how the probabilistic form of this procedure has been used to solve one problem in low-level or intermediate-level vision. D3. You are hired to design a vision system to be running in 1999 that can input 1,000-by-1,000 images via high- resolution TV cameras in 30 milliseconds or less, and recognize the objects in the image in another 30- 300 milliseconds. You can assume that by 1996, when actual construction should begin, VLSI chips will be 10-100 times denser and faster than they are today. Describe what appear to you to be the two most attractive alternative designs for such a system - its structure of processors (hardware), its structure of processes (algorithms), how they are mapped into each other, and how they handle 1999's space and time constraints. Compare them: what are the strong points and the weak points of each? D4. Describe two systems for perceptual recognition that you feel are among the more powerful - one a "connectionist network" of "neuron-like" units, the other a traditional computer vision system of any sort - and give their present-day results (that is the level of performance actually achieved to date) of each. Compare them - both these two specific programs, and also these two types of systems. Which appears to be the more promising, looking to the future, and why? D5. Two somewhat complementary approaches to machine learning are _s_i_m_i_l_a_r_i_t_y-_b_a_s_e_d _l_e_a_r_n_i_n_g (SBL) and _e_x_p_l_a_n_a_t_i_o_n-_b_a_s_e_d _l_e_a_r_n_i_n_g (EBL). Discuss why these two approaches can be viewed as being complementary and describe under what conditions each is appropriate. Speculate on how you would go about designing a system that combined the strengths of each, avoiding as much as possible each approach's weaknesses. Describe for what type of domains would your hybrid approach be best suited. D6. Connectionist learning systems are often applied to classification problems (i.e., given a description of an instance, determine its class). More symbolically-oriented learning algorithms, such as Michalski's AQ11, Quinlan's ID3, and Mitchell's Version Spaces, have also been applied to classification problems. Compare these two approaches (connectionist and symbolic). Describe what properties are desired of a system that learns classifications and discuss how (and how well) the two approaches address these requirements. D7. A common form of machine learning is to provide the learning system with sample "solved problems" (e.g., the determination of the illness, given a patient's symptoms). Choose four out of the five following approaches and discuss how they have been used to learn without explicitly requiring sample external solutions to the task being learned. Mention specific published research where appropriate. 9 Similarity-Based Learning Explanation-Based Learning Connectionist Learning Genetic Algorithms Analogical Learning 9 9 9 D8. A number of expert systems have been constructed to draw inferences from rules and data that have certainty factors or probability measures associated with them. For some one system (e.g., Mycin or Prospector) (a) describe how the inference mechanism works, (b) comment on how general and widely applicable you consider the mechanism to be, and (c) comment on how important it is that these indicators of certainty or probability be reliable (e.g., are they of much use if they are just subjective guesses?). D9. Many expert system "shells" have become available within the past five years. Evaluate the claim that such shells (speak in terms of a particular, actual shell if you can and wish) are just special kinds of programming languages. Illustrate your evaluation by comparing such shells with so-called AI programming languages, in particular, Lisp, Prolog, and OPS5. If you were charged with building an expert system, why might you or might you not choose to use a shell rather than one of Lisp, Prolog, or OPS5? D10. Derive [] from the following by paramodulation and binary resolution: 1. _ X