Michalski trains [1]} is a classical problem.
The task is to find a hypothesis that distinguishes eastbound trains from westbound trains.
Figure REF  shows an example hypothesis that says a train is eastbound if it has a long carriage with two wheels and another long carriage with three wheels.
We use this domain because we can easily generate progressively more difficult tasks to test the scalability of the approaches as the solution size grows.
Table REF  shows information about the four tasks we consider.
There are 1000 examples but the distribution of positive and negative examples is different for each task.
We randomly sample the examples and split them into 80/20 train/test partitions
<FIGURE><TABLE>