Phase transitions in relational learning

One of the major limitations of relational learning is due to the complexit y of verifying hypotheses on examples. In this paper we investigate this ta sk in light of recent published results, which show that many hard problems exhibit a narrow "phase transition" with respect to some order parameter, coupled with a large increase in computational complexity. First we show th at matching a class of artificially generated Horn clauses on ground instan ces presents a typical phase transition in solvability with respect to both the number of literals in the clause and the number of constants occurring in the instance to match. Then, we demonstrate that phase transitions also appear in real-world learning problems, and that learners tend to generate inductive hypotheses lying exactly on the phase transition. On the other h and, an extensive experimenting revealed that not every matching problem in side the phase transition region is intractable. However, unfortunately, id entifying those that are feasible cannot be done solely on the basis of the order parameters. To face this problem, we propose a method, based on a Mo nte Carlo algorithm, to estimate on-line the likelihood that the current ma tching problem will exceed a given amount of computational resources. The i mpact of the above findings on relational learning is discussed.