Phase transition and heuristic search in relational learning

Several works have shown that the covering test in relational learning exhibits a phase transition in its covering probability. It is argued that this phase transition dooms every learning algorithm to fail to identify a target concept lying close to it. However, in this paper we exhibit a counter-example which shows that this conclusion must be qualified in the general case. Mostly building on the work of Winston on near-misse examples, we show that, on the same set of problems, a top-down data-driven strategy can cross any plateau if near-misses are supplied in the training set, whereas they do not change the plateau profile and do not guide a generate-and-test strategy. We conclude that the location of the target concept with respect to the phase transition alone is not a reliable indication of the learning problem difficulty as previously thought.