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

   $$color(Obj,Col,Sit)$$

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

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

   $$color(parcel,blue,init).$$

   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),
                                do(move(rob,storage,o109),
                                  do(pickup(rob,parcel),
                                    do(move(rob,o109,storage),
                                      init))))).
   

2. 2.

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

   Suppose the object $paint\mathrm{\_}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

   $\left({\left(\widehat{r}(u,i)-r\right)}^2+\lambda (ib{[i]}^2+ub{[u]}^2+{\displaystyle \sum _p}(ip{[i,p]}^2+up{[u,p]}^2))\right)$

   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 $\lambda$ to be different for each method; for each method, choose the value of $\lambda$ 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

    $$P(likes(P,M)\mid age(P),genre(M))$$

    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.