Subsections

• Implementation Notes and Empirical Obervations

Examples of MIS Learning Concepts

The applet on this page is a straightfoward implementation of the MIS algorithm, with very few refinements. Usage instructions:

1. Select either a canned learning scenario from the choice widget, or select the function symbols and predicate symbols in $L_o$. (Note that ./2 is the list constructor function symbol in Prolog by convention.)

2. Enter zero or more facts in the ``bulk data entry'' text box. These facts have the form:

   predicate_to_be_learned(a1, ..., an), true.
   predicate_to_be_learned(b1, ..., bn), false.
   

   Note that the applet allows facts to be added incrementally as well.

3. Click ``done''.

4. At this point MIS will attempt to find a theory that is consistent with the entered facts (if there were any). This is non-interactive, except when the oracle is consulted for contradiction backtracing (Section 2).

5. The applet will then enter an interactive loop, where facts are read and the theory is refined.

Your browser does not support Java applets.

Implementation Notes and Empirical Obervations

This section is a collection of brief observations that stem from actually implementing MIS.

• The starting theory contains all predicate symbols in $L_o$ with distinct variables for arguments. This is, in effect, the empty program $\Box$ specialised to $L_o$ - they both entail all facts in $L_o$.

• MIS learns quite well from sparse data - it learnt the less_than/2 relation from 15 facts (some of which are redundant).

• If the entered facts are inconsistent (the same fact is deemed both true and false), then the algorithm goes into an infinite loop. This is a manifestation of MIS's lack of noise handling.

• The theories induced tend to contain a lot of irrelevant clauses and be non-standard. The former can be dealt with via better refinement pruning and vetting strategies and perhaps a post-process of the theory.

• The algorithm as it stands cannot learn theories that use background knowledge, as most predicates do not behave well if their arguments do not have particular instantion modes. An example of this is add/3: the call add(X, Y, Z) fails to terminate. This is a manifestation of Prolog's incomplete search rule.

  The options for solving this are:

  • Use a complete proof technique. This is computationally intractable, but then again, so is MIS' search through the refinement graph.

  • Add meta-information (mode and perhaps type information) for the background predicates, and throw out all clauses that violate these prescriptions.

• Due to the previous point, the refinement operator in the applet is restricted to construct clauses with only a single body goal, which must not be a variant of the head. Again, mode information or a complete search strategy is necessary if more than one is allowed.