Connection of the beam width and the learning success rate in the phase transition framework for relational learning

It is well-known that heuristic search in relation learning is prone to plateau phenomena. An explanation is that the relational learning covering test is NP-complete and therefore exhibits a sharp phase transition in its coverage probability. For heuristic value of a hypothesis depends on the amount of covered examples, the regions “yes” and “no” have no informative heuristic value, and the regions “yes” and “no” represent plateaus. Marco Botta et al. run several learning algorithms on a large data set of artificially generated problems and point out that the occurrence of phase transition dooms every learning algorithm to fail to identify the target concept. However, we note that they did not consider the influence of beam width on learning success rate. In this paper, we investigate the problem that whether the low learning success rate due to phase transition can be enhanced by enlarging the beam width. FOIL and KFOIL learning systems are respectively run on artificially generated data set according to different beam width 1, 5, 10, 20 and 30. Experiments show that beam width has almost no effect on learning success rate under phase transition framework.