Phase transitions detected in two real cases

In Chapter 9 we claimed that there is experimental evidence that in real-world applications also, where examples are not randomly generated, discriminant hypotheses found by relational learners lie on the phase transition edge. In order to support this claim, we discuss here the findings presented by Giordana and Saitta (2000) concerning two-real world applications. The first is a popular benchmark known as the mutagenesis dataset (Srinivasan et al ., 1995), while the second is an application to mechanical troubleshooting in a chemical plant (Giordana et al ., 1993). In both cases the learning problems were solved using G-Net, the relational learner based on evolutionary search described in Chapter 6 (Anglano et al ., 1997, 1998). It is worth noticing that datasets suitable for relational learning and available in public repositories are few and, in general, rather simple. In fact, the concept descriptions that have been learned from them contain few literals only and, mostly, two or three chained variables. The datasets that we present in this appendix are among the most complex approached with machine learning: for both, descriptions containing up to four variables and up to six binary relations have been discovered. For the sake of reference, Figure A.1 gives the same graph as Figure 9.9(a) but for n = 4. A phase transition is evident, but the expected complexity in the mushy region is much lower than that in Figure 9.9(a).