Working of the Algorithm
- Use the same method as done in FOIL and add a single feature for each operational literal that is not part of the hypothesis space so as to create candidates for the best rule. (solid arrows in Fig.4 denote specializations of bottle)
- Create an operational literal that is logically efficient to explain the goal concept according to the Domain Theory. (dashed arrows in Fig.4 denote domain theory based specializations of bottle)
- Add this set of literals to the current preconditions of the hypothesis.
- Remove all those preconditions of hypothesis space that are unnecessary according to the training data.
Let us consider the example shown in Fig 4.
- First, FOCL creates all the candidate literals that have the possibility of becoming the best rule (all denoted by solid arrows). Something we have already seen in the FOIL algorithm. In addition, it creates several logically relevant candidate literals of its own. (the domain theory)
- Then, it selects one of the literals from the domain theory whose precondition matches the goal concept. If there are several such literals present, then it just selects one which gives the most information related to the goal concept.
For example, If the bottle (goal concept) is made of steel (while satisfying the other domain theory preconditions), then the algorithm will select that as it the most relevant information related to the goal concept. i.e. the bottle.
- Now, all those literals that removed unless they affect the classification accuracy over the training examples. This is done so that the domain theory doesn’t overspecialize the result by adding irrelevant literals. This set of literals is now added to the preconditions of the current hypothesis.
- Finally, one candidate literal which provides the maximum information gain is selected out of two specialization methods. (FOIL and domain theory)
FOCL is a powerful machine learning algorithm that uses EBL and domain theory techniques, to reach the hypothesis space quickly and efficiently. It has shown more improved and accurate results than the Inductive FOIL Algorithm. A study on “Legal Chessboard Positions” showed that on 60 training examples describing 30 legal and 30 illegal endgame board positions, FOIL accuracy was about 86% while that of FOCL was about 94%.
Similar results have been obtained in other domains. For any doubt/query, comment below.
FOCL Algorithm
The First Order Combined Learner (FOCL) Algorithm is an extension of the purely inductive, FOIL Algorithm. It uses domain theory to further improve the search for the best rule and greatly improves accuracy. It incorporates the methods of Explanation-Based learning (EBL) into the existing methods of FOIL. But before getting into the working of FOCL, let us first understand the following:
- Domain Theory
- Explanation-Based Learning
Prerequisite: FOIL Algorithm