Relational Learning

Title Relational Learning
Description

Description

This assignment is ment to show what is specific about relational learning as opposed to non-relational learning (or “propositional”) learning. The assignment is a sister assignment of the one about decision tree learning. In both assignments a program is made (based the book by Bratko, Prolog Programming for Artificial Intelligence) with which experiments can be done with the learning of how to play Tic-Tac-Toe. Relational learning can implement relations in the descriptions of learning examples and models that are being learned. The models can than make abstractions of specific objects. A model can for instance be that a “pile” consists of two objects of which one is placed on top of the ather, without specifying other attributes of the objects.

Task assignment

The task assignment is devided in a few parts. The purpose of part 1 and 2 is to make a basic inplementation of the top-down learning of relational models based on the programs from the book by Bratko. The other parts are ment to Experiment with the basic implementation and some variations in the context of Tic-Tac-Toe.

Learning targets

Foremost, this assignment has as a goal the understanding of the similarities and differences of relational and non-relational data, hypotheses and algorithms. Especially the relation between attribute-vaue (“zero-order”) and relational (“first-order) hypotheses.
  1. In the file tttdata.pl are bord positions of Tic-Tac-Toe together with the game-values. The purpose of the assignment is to learn rules with HYPER to play an optimal game, and in that way learn the operation and effects of HYPER. In the book by Bratko is explained how the program HYPER works. Here are some tips on using HYPER with Tic-Tac-Toe. HYPER gets as input:
    • examples: ex(prolog fact)
    • literals that can be used to make clauses: backliteral(literal, variables)
    Hypothesis that HYPER makes have the form of a list of clauses in which with every clause is the variable. In tttplayer.pl is a program that can be played against the computer. The program works as follows. It takes a decision tree as input and uses it to choose the best move. It looks at all the possible moves, evaluates the resulting positions with the decision tree and chooses a move (aselect) from the most favourable possibilities.
  2. Start with the program HYPER (including the prove prove) from Bratko and the trainingdata in tttdata.pl. Use HYPER with this problem. For this, think of which form the trainigdata should get so that it can be used by HYPER. What are the positive/negative examples? What are the "background literals"? Transform the data to the right form and make the background literals.
  3. Make a program that takes clauses learned with HYPER and a file with classified data as input and calculates for how much data the classification of the learned clauses is equal to the classification in the data, and how often it deviates.
  4. Use the program randomN.pl to create trainingsets of 10, 20, 40 and 80 game situations, learn of them and evaluate the result by using it on all of the data (and seeing if the prediction is correct). Make an overview (with a diagram) of the percentage of correct predictions against the number of training examples.
  5. Option: compare this to similar data of the assignment about the learning of decision trees.
  6. In tttdata.pl the data is represented with the cells of the playing bord as attributes and everything on the cells as values ("cross", "circle", "nothing"). Train HYPER with the datasets of 10, 20, 40 and 80 game situations, and measure how good the learned clauses predict by testing them. Try to understand why faulty predictions arise. Draw a diagram of the development of the accuracy against the number of training examples and give an estimation of the number of training examples that are needed for a perfect prediction.
  7. The above data only uses rough data about the bord positions. People who play this game use abstract concepts to describe positions. Like "a row of 2 with an empty cell next to it" or "a cornercell". Think up a few of these concepts. Implement these abstract concepts as prior knowledge for HYPER. Hint: you can use the "background literals" for this. Now repeat assignment 6 with this new dataset. Compare the resulting learning curve to the old one and see if the new concepts lead to inprovements.
  8. Option: compare this to the similar data from the assignment about the learning of decision trees.
  9. Now use structured terms to represent concepts. We now represent the bord as a term: [V11/V21/V31, V12/V22/V32, V13/V23/V33]. Use hyper again, but now with the new representation.

Sources

Prior knowledge

  • Programmigs in Prolog on a basic level
  • The assignment is about Relational Learning or Inductive Logic Programming, but the algorithm and the justification thereof are not in the assignment. For the method on which Bratko's HYPER is based, see his book and "sources"

Details

Developer: Maarten van Someren (maarten@swi.psy.uva.nl), UvA