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
-------- ------------- -------------
X[1] T T T F
X[2] F F F T
X[3] T T F F
X[4] 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:
[genetic-fig.jpg]
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:
[inheritance.jpg]
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.
[analogy.jpg]
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:
[graphplan-blocks.jpg] 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
The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/e12.html.
URL of module [1]http://www.cs.bham.ac.uk/~mmk/Teaching/AI/
References
1. http://www.cs.bham.ac.uk/~mmk/Teaching/AI/