CMPS 287 Final, Fall 2004

American University of Beirut Faculty of Arts and Science, Department of Mathematics and Computer Science CMPS 287 Final Artificial Intelligence Exam duration: 2 hours ID: Question 1: (10 marks) A. (2 marks) A method which can be used to be build an intelligent system for any domain is said to be highly A method which can be used very effectively to solve a problem for a specific domain is said to be highly ____thus, search methods are highly (3 marks) Trace the execution of A* in finding the shortest path from Arad to Bucharest (see Romanian map attached). Use the straight line distance estimate included on the map as your admissible function. Show stages involved on the back of this question sheet (note each stage increases the search depth by 1). C. (3 marks) Prove that A* is optimal if the heuristic function is admissible D. (2 marks) When the search state in a two player game does not seem to be promising for either player it is said to be In games which involves throwing a dice, a minimax tree has to be interleaved with nodes. Question 2: (10 marks) A. (2 marks) Define the following Knowledge Acquisition Bottleneck Occam's Razor B. (2 marks) Name three niche application areas of Machine learning and give one domain of each area: 1. 2: 3: C. (3 marks) What are the first four steps to formulate a problem as a Machine Learning problem? Illustrate these steps in a domain of your choice. Your example: Step 1: Step 2: Step 3: Step 4: D. (3 marks) What is overfitting? Describe two approaches to deal with it when inducing decision trees. fameracas © , Lapras \ ae WOKOT t ce ne A ‘ Question 3: (8 marks) A. For the following dataset, show the steps for inducing a decision tree using the information gain critrion. (6 marks) Outlook Temperature Humidity Wind Play_tennis 1 Sunny Hot High Weak Yes 2 Sunny Hot High Strong No 3 Overcast Mild High Weak Yes 4 Sunny Mild Normal Strong Yes 5 Overcast Hot Normal Weak Yes 6 Rain Mild High Strong No or eee | ee ee I D. Give three attributes which are useful for the learning task of Speaker Verification (2 marks) Question 4: (10 marks) A. (2 marks) Give an example of a function which cannot be learnt using a perceptron (illustrate with a diagram) B. (4 marks) Implement the XOR (exclusive or) using two layers of perceptrons with suitable thresholds and weights Cc. (4 marks) Give strengths and weaknesses of each of the learning methods for a perceptron: the perceptron training rule and the gradient descent D. (2 marks} Give a brief description of the backpropagation algorithm wane teneeen nae Good luck