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
The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/e12.html.
URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/