Introduction to AI - Worksheet 12

EXERCISE: 1

1. What are the different components of a rule-based expert system? What is the difference between domain and case knowledge?        Points:7
2. Find all possible bindings for ?x and ?y so that the rule

   	?x is-a horse
   	?x is-a-parent-of ?y
   	?y is fast
   ->	?x is valuable

   is applicable with the facts:

   Comet	is-a	horse
   Prancer	is-a	horse
   Comet	is-a-parent-of	Dasher
   Comet	is-a-parent-of	Prancer
   Prancer	is	fast

             

   Dasher	is-a-parent-of	Thunder
   Thunder	is	fast
   Thunder	is-a	horse
   Dasher	is-a	horse
   Aslan	is-a	lion

   
           Points:6
3. What is a conflict in the context of rule-based expert systems and what are typical approaches to resolve conflicts?        Points:6
4. What is the main problem with a naive implementation of the recognise-act-cycle in rule-based expert systems and how is it resolved by the RETE algorithm?         Points:6

EXERCISE: 2

1. Assume the following examples, where a decision tree for the goal "feel_good" is to be learned over the attributes "hungry", "tired", "thirsty".
   

   	hungry	tired	thirsty	feel_good
   --------	-------------	-------------
   X1	T	T	T	F
   X2	F	F	F	T
   X3	T	T	F	F
   X4	F	F	T	F

   
   Build an optimal learned decision tree. Why is your tree optimal?        Points:7
2. Describe the basic idea of decision tree learning.        Points:6
3. Why and how is Ockham's razor used in the context of decision-tree learning?        Points:6
4. In decision tree learning the selection of the next test is based on the information gain? How is the information gain computed?        Points:6

EXERCISE: 3

1. Show in detail how the conditional probabilities that the humidity is normal will be determined, assuming that the agent plays tennis P( Humidity = Normal | PlayTennis = Yes), and that the humidity is normal assuming that the agent will not play tennis, i.e., P( Humidity = Normal | PlayTennis = No).
           Points:7

2. Explain the basic idea of the Naive Bayes approach.        Points:6
3. Bayes' theorem gives an exact way to compute probability such as
   P( Humidity = Normal | NOT  PlayTennis = No). Why is Bayes' theorem not directly used, but approximated in a naive way?        Points:6
4. Explain intuitively how the weights of the links to the output nodes of a neural net are updated.        Points:6

EXERCISE: 4

1. What is a fitness function and how is it created by a system designer?         Points:7
2. Discuss the significance of mutation and the problems with it.        Points:6
3. Assume an initial population with fitness values given as follows: Calculate the next population under the assumptions that the fittest element mates with the second fittest and the third fittest. For the first pair the cross-over point is selected between the fourth and the fifth bit and there is no mutation. For the second pair cross-over is between the fifth last and fourth last bit and the last bit of one of the offsprings is flipped.         Points:6
4. What is elitism and what are its advantages and disadvantages?        Points:6

EXERCISE: 5

1. Represent the following semantic net in natural language:

   

           Points:7

2. Represent the relationships between quadrangle, parallelogram, rhombus, rectangle, and square in form of a semantic net. Represent in particular the circumferences.        Points:6

3. Describe a representation that could be used in a program to solve analogy problems like that below. This class of problems was addressed by T. G. Evans (1968, see Luger-Stubblefield, p.337). The representation must be sufficiently rich to represent the essential features of size, shape, and relative position which are necessary for solving the problem.

   

           Points:6

4. What does non-monotonicity mean in the context of reasoning? Why is it a problem?        Points:6

EXERCISE: 6

1. Explain depth-first and breadth-first search.        Points:7
2. What are the relative advantages of depth-first and breadth-first search?        Points:6
3. In the 4-Queens problem, one must place four queens on a 4 x 4-board such that no queen can attack another, that is, that no row, column, or diagonal contains more than one queen. Give a heuristic that restricts the search and find a solution using the heuristic.        Points:6
4. Explain in detail why the A^*-algorithm is complete.        Points:6

EXERCISE: 7

1. Describe the basic ideas of linear planning in terms of initial state, goal state, and operators.        Points:7
2. How does Strips generate plans?        Points:6
3. Generate a plan with Strips for the following problem in the blocks world:
   

           Points:6

4. How can GraphPlan detect whether no plan exists of a particular length and whether no plan exists at all?         Points:6