### Introduction to AI - Worksheet 12

#### EXERCISE: 1

[Expert Systems]        Total Points:25
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

[Decision Tree Learning]        Total Points:25
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

[Naive Bayes, Neural Nets]        Total Points:25
The table below lists a sample of variables that can be used to predict the decision to play tennis in form of a yes/no decision.
 Day Outlook Temperature Humidity Wind PlayTennis -------- ------------- ------------- D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D10 Rain Mild Normal Weak Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Rain Hot Normal Weak Yes D14 Rain Mild High Strong No
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

[Genetic Algorithms]        Total Points:25
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

[Knowledge Representation]        Total Points:25
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

[Search]        Total Points:25
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

[Planning]        Total Points:25
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

© Noel Welsh & Manfred Kerber, 2004, Introduction to AI
19.4.2005