15 Relational Planning, Learning, and Probabilistic Reasoning

15.6 Exercises

Some of these exercises can use AILog, a simple logical reasoning system that implements much the reasoning discussed in this chapter. It is available from the book website (http://artint.info). Some of these can also be done in Prolog or Problog.

  1. 1.

    Add to the situation calculus example (also available from the book web page) the ability to paint an object. In particular, add the predicate


    that is true if object Obj has color Col in situation Sit.

    The parcel starts off blue. Thus, we have an axiom:


    There is an action paint(Obj,Col) to paint object Obj with color Col. For this exercise, assume objects can only be painted red, and they can only be painted when the object and the robot are both at position o109. Colors accumulate on the robot. There is nothing that undoes an object being a color; if you paint the parcel red, it is both red and blue – of course this is unrealistic, but it makes the problem simpler.

    Axiomatize the predicate color and the action paint using situation calculus.

    You can do this without using more than three clauses (apart from the clause defining the color in the initial situation), where none of the clauses has more than two atomic symbols in the body. You do not require equality, inequality, or negation as failure. Test it in AILog.

    Your output should look something like the following:

    ailog: bound 12.
    ailog: ask color(parcel,red,S).
    Answer:  color(parcel,red, do(paint(parcel,red),
  2. 2.

    In this exercise, you will add a more complicated paint action than in the previous exercise.

    Suppose the object paint_can(Color) denotes a can of paint of color Color.

    Add the action paint(Obj,Color) that results in the object changing its color to Color. (Unlike in the previous question, the object only has one color at a time.) The painting can only be carried out if the object is sitting at o109 and an autonomous agent is at position o109 carrying the can of paint of the appropriate color.

  3. 3.

    AILog performs depth-bounded search. You will notice that the processing time for the previous questions was slow, and you required a depth bound that was close to the actual depth bound to make it work in a reasonable amount of time.

    In this exercise, estimate how long an iterative deepening search will take to find a solution to the following query:

    ask sitting_at(parcel,lab2,S).

    (Do not bother to try it – it will take too long to run.)

    1. (a)

      Estimate the smallest bound necessary to find a plan. [Hint: How many steps are needed to solve this problem? How does the number of steps relate to the required depth bound?] Justify your estimate.

    2. (b)

      Estimate the branching factor of the search tree. To do this you should look at the time for a complete search at level k+1 versus a complete search at level k. You should justify your answer both experimentally (by running the program) and theoretically (by considering what is the branching factor). You do not have to run cases with a large run time to do this problem.

    3. (c)

      Based on your answers to parts (a) and (b), and the time you found for some run of the program for a small bound, estimate the time for a complete search of the search tree at a depth one less than that required to find a solution. Justify your solution.

  4. 4.

    In this exercise, you will investigate using event calculus for the robot delivery domain.

    1. (a)

      Represent the move action in the event calculus.

    2. (b)

      Represent each of the sequences of actions in Example 15.10 in the event calculus.

    3. (c)

      Show that event calculus can derive the appropriate goals from the sequence of actions given in part (b).

  5. 5.

    Suppose that, in event calculus, there are two actions, Open and Close, and a relation opened that is initially, at time 0, false. Action Open makes opened true, and action Close makes opened false. Suppose that action Open occurs at time 5, and action Close occurs at time 10.

    1. (a)

      Represent this in event calculus.

    2. (b)

      Is opened true at time 3? Show the derivation.

    3. (c)

      Is opened true at time 7? Show the derivation.

    4. (d)

      Is opened true at time 13? Show the derivation.

    5. (e)

      Is opened true at time 5? Explain.

    6. (f)

      Is opened true at time 10? Explain.

    7. (g)

      Suggest an alternative axiomatization for holds that has different behavior at times 5 and 10.

    8. (h)

      Argue for one axiomatization as being more sensible than the other.

  6. 6.

    Give some concrete specialization operators that can be used for top-down inductive logic programming. They should be defined so that making progress can be evaluated myopically. Explain under what circumstances the operators will make progress.

  7. 7.

    Change the stochastic gradient descent algorithm of Figure 15.5 so it minimizes Formula 15.1, but regularizes after each example. Hint: You need to consider how many times each parameter is updated for one iteration through the data set and adjust the regularization parameter accordingly.

  8. 8.

    An alternative regularization for collaborative filtering is to minimize

    u,i,rD ((r^(u,i)-r)2+λ(ib[i]2+ub[u]2+p(ip[i,p]2+up[u,p]2)))
    1. (a)

      How this differ from the regularization of Formula 15.1? [Hint: Compare the regularization for the items or users with few ratings with those with many ratings.]

    2. (b)

      How does the code of Figure 15.5 need to be modified to implement this regularization?

    3. (c)

      Which works better in on test data? [Hint: You will need to set λ to be different for each method; for each method, choose the value of λ by cross validation.]

  9. 9.

    A simple modification for the gradient descent for collaborative filtering can be used to predict P(rating>threshold) for various values of threshold in {1,2,3,4}. Modify the code so that it learns such a probability. [Hint: Make the prediction the sigmoid of the linear function as in logistic regression.] Does this modification work better for the task of recommending the top-n movies, for, say n=10, where the aim is to have the maximum number of movies rated 5 in the top-n list? Which threshold work best? What if the top-n is judged by the number of movies rated 4 or 5?

  10. 10.

    Suppose Boolean parameterized random variables young(Person) and cool(Item) are parents of Boolean buys(Person,Item). Suppose there are 3000 people and 200 items.

    1. (a)

      Draw this in plate notation.

    2. (b)

      How many random variables are in the grounding of this model?

    3. (c)

      How many numbers need to be specified for a tabular representation of this model. (Do not include any numbers that are functions of other specified numbers.)

    4. (d)

      Draw the grounding belief network assuming the population of Person is {sam,chris} and the population of Item is {iwatch,mortgage,spinach}.

    5. (e)

      What could be observed to make cool(iwatch) and cool(mortgage) probabilistically dependent on each other given the observations?

  11. 11.

    For the representation of addition in Example 15.24, it was assumed that the observed Z-values would all be digits. Change the representation so that the observed values can be digits, a blank, or other. Give appropriate probabilities.

  12. 12.

    Suppose you have a relational probabilistic model for movie prediction, which represents


    where age(P) and genre(M) are a priori independent.

    1. (a)

      What is the treewidth of the ground belief network (after pruning irrelevant variables) for querying age(Sam) given the following observations?

      Person Movie likes
      Sam Hugo yes
      Chris Hugo no
      Sam The Help no
      Sam Harry Potter 6 yes
      Chris Harry Potter 6 yes
      Chris AI no
      Chris The Help no
      David AI yes
      David The Help yes
    2. (b)

      For the same probabilistic model, for m movies, n people and r ratings, what is the worst-case treewidth of the corresponding graph (after pruning irrelevant variables), where only ratings are observed? [Hint: The treewidth depends on the structure of the observations; think about how the observations can be structured to maximize the treewidth.]

    3. (c)

      For the same probabilistic model, for m movies, n people, and r ratings, what is the worst-case treewidth of the corresponding graph, where only some of the ratings but all of the genres are observed?

  13. 13.

    Represent the electrical domain of previous chapters in ICL, so that it will run in AILog. The representation should include the probabilistic dependencies of Example 8.17 and the relations of Example 13.12.