In the previous chapter we showed how the covering test in relational learning exhibits a phase transition associated with a complexity peak, for control parameter values typical of the problems investigated by current relational learners. We also showed that the complexity associated with the phase transition in matching can be partially tamed using smart search algorithms. However, as soon as the number of variables increases a little (say, from four to five) the complexity is again a strongly limiting factor for learning, because a leamer must face hundreds of thousands of matching problems during its search for hypotheses (formulas).

Leaving aside the problems caused by the computational complexity of matching, one may wonder whether the presence of a phase transition has additional effects on learning, for instance whether it affects the quality of the learned knowledge. Another question is whether it is possible to escape from the region of the phase transition by suitably manipulating the control parameters. In this chapter we try to provide an answer to these questions, by means of an experimental analysis and its interpretation.

The experimental setting

In order to test the independence of the results from the learning algorithm, we used the learners FOIL (Quinlan and Cameron-Jones, 1993), SMART + (Botta and Giordana, 1993), G-Net (Anglano et al., 1997; Anglano and Botta, 2002), and PROGOL (Muggleton, 1995) described in Chapter 6.

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).

In the long journey undertaken in this book, we have visited statistical mechanics, constraint satisfaction problems and satisfiability, complex networks and natural systems, and, in particular, many facets of machine learning ranging from propositional to relational learning, grammatical inference, and neural networks. The thread that connects all these fields is the emergence of phenomena exhibiting sharp discontinuities. These phenomena are reminiscent of the phase transitions found in physics and, indeed, the methods of statistical physics have been employed with success to analyze them. In this chapter we try to summarize what we have learned from these connections and in particular from the role played by machine learning. Our aim is to point out gaps in the understanding of basic phenomena and to identify open questions that may suggest future research directions.

Phase transitions or threshold phenomena?

In a recent and very interesting paper, which recalls similar arguments put forwards in Percus et al. (2006), Zweig et al. (2010) have challenged the current view of phase transitions in computational problems, wondering whether the abrupt change observed in the probability of solution (the order parameter) in SAT problems is in fact nothing other than a “self-fulfilling” discontinuity, i.e., an existential discontinuity generated by the very definitions of the problem and of the order parameter.

The first argument in support of their claim is that it is easy to produce rather simple models that exhibit phase transition phenomena while, as most of us would agree, the essential ingredients that underly a “true” phase transition are lacking.

From its inception in the 1930s, the rich and vigorous field of computer science has been concerned with the resources, both in time and in memory, needed to carry out a computation. A number of fundamental theorems were discovered that resorted to a worst-case analysis. The central question was whether a given algorithm could be guaranteed to terminate a computation in finite time whatever the inputs, and, if so, in which class of complexity it lay, given the control parameters: polynomial, exponential, and so on. Therefore, in 1991, a paper by Cheeseman, Kaneefsky, and Taylor came as a bolt from the blue. Indeed, while its title, “Where the really hard problems are”, was not altogether disturbing, its content was. Broadly speaking, the authors argued that even if it was important to analyze worst cases, it was just as essential to look for the typical complexity of computations, the complexity encountered when solving typical problems. And there lies a gem: the transition from the region of problems that are hard, in terms of algorithmic complexity, to the region of problems that are easy can be quite sharp. Moreover, these regions and transitions are not related to the worst cases.

We remember that this 1991 paper, presented at the International Joint Conference on Artificial Intelligence (IJCAI), started a commotion, though how profound this would be was not at first apparent.

Learning grammars

Grammatical inference has been studied since the inception of the theory of formal grammars in the 1960s, in particular to provide a formal framework for language acquisition. Since the pioneering paper of Gold (1967), which introduced the concept of identification in the limit, numerous works have been carried out in several scientific communities, including those studying machine learning, pattern recognition, natural language processing, formal language theory, and electronic circuit design. Their goal was to set a theoretical framework for grammatical inference and to design practical learning methods. Recently, these techniques have been used in several application domains such as genomics, natural language processing, and the testing of computer programs.

This chapter provides the necessary fundamental concepts to understand the flavor of this field and reports on a study of generic learning algorithms with regard to the covering test and generalization.

Experimental evidence points again to a phase transition phenomenon, albeit different from those already encountered in this book.

The task of inferring grammars

While so far we have discussed a learning scenario where the task is to extract regularities from sets or collections of (labeled) descriptions, this scenario is far from covering all learning situations. Indeed, much data comes in sequences, and often what one wants to learn is the trend, tendency, or even the rule governing the sequences. Thus, the important relationship is the sequential or temporal organization of the data.

The study of the emergence of phase transitions, or, more generally, the application of statistical physics methods to automated learning, is not new. For at least a couple of decades ensemble phenomena have been noticed in artificial neural networks. In the first part of this chapter we will illustrate these early results and then move to currently investigated issues.

According to Watkin et al. (1993), statistical physics tools are not only well suited to analyze existing learning algorithms but also they may suggest new approaches. In the paradigm of learning from examples (the paradigm considered in this book), examples are drawn from some unknown but fixed probability distribution and, once chosen, constitute a static quenched disorder (Watkin et al., 1993).

Artificial neural networks

Artificial neural networks (NNs) are graphs consisting of a set of nodes that correspond to elementary computational units, called “neurons”, connected via links recalling “axons” and “synapses”. Even though the terminology is borrowed from neurology, the analogy between an NN and the brain can well be ignored. The idea behind the computation in an NN is that inputs from the external world activate a subset of the neurons (the input neurons), which, in turn, elaborate the input and transmit the results of this local computation to other neurons until some subset of neurons (the output neurons) provide the final results to the external world.

It is easy to produce a probability function that exhibits a very steep transition between the values 0 and 1. Take for instance a binary tree corresponding to the exploration graph of a two-player game with a constant branching factor b. Each node in the tree represents a position, and each edge a possible move for a player from one position to a next position. Some games do indeed offer only exactly b possibilities at each time to the current player.

Suppose further, as it is usually the case, that the computer whose turn it is to play does not have sufficient time or memory space to explore the whole tree of possibilities. Then, the standard approach is for the computer to develop the tree to a given depth, say 10, and then to evaluate the merit of each position and to carry up these estimations through the celebrated min–max procedure. If a node represents the computer's turn to play, the maximum value of the nodes below is returned and passed above, otherwise the minimal value is passed above.

One question is then how to compute the probability of a “win” at the root of the tree given the probability that a leaf node is a win.

General framework

Surprising as it may be, the emergence of phase transitions is not limited to physical systems: it seems to be a rather ubiquitous phenomenon, existing in biology, genetics, neural networks, complex systems, and also in combinatorial problems. For the last, a precise parallel can be established with physical systems composed of very large numbers of particles. In a combinatorial problem the phase transition concerns the behavior of some order parameter (usually the expectation value of a microscopic quantity) characterizing an aspect of the system (often the probability of existence of a solution). Moreover, in correspondence to the phase transition (at a critical value of the control parameter), a large increase in the computational complexity of the algorithm used to find a solution is usually observed.

The key concept that allows ideas and methods to be transferred from statistical physics to combinatorial optimization and decision problems is randomness. If problem instances are taken in isolation, the application of these methods does not make sense. They are only meaningful if applied to a set, i.e., an ensemble, of problem instances whose probability of occurrence is governed by a well defined law. Then the results obtained can be considered valid for any randomly extracted element from the ensemble. It is thus necessary to specify exactly how the elements of the ensemble are constructed.

In Chapter 5 we introduced the main notions of machine learning, with particular regard to hypothesis and data representation, and we saw that concept learning can be formulated in terms of a search problem in the hypothesis space H. As H is in general very large, or even infinite, well-designed strategies are required in order to perform efficiently the search for good hypotheses. In this chapter we will discuss in more depth these general ideas about search.

When concepts are represented using a symbolic or logical language, algorithms for searching the hypothesis space rely on two basic features:

1. a criterion for checking the quality (performance) of a hypothesis;

2. an algorithm for comparing two hypotheses with respect to the generality relation.

In this chapter we will discuss the above features in both the propositional and the relational settings, with specific attention to the covering test.

Guiding the search in the hypothesis space

If the hypothesis space is endowed with the more-general-than relation (as is always the case in symbolic learning), hypotheses can be organized into a lattice, as represented in Figure 5.6. This lattice can be explored by moving from more general to more specific hypotheses (top-down strategies) or from more specific to more general ones (bottom-up strategies) or by a combination of the two. Both directions of search rely on the definition of suitable operators, namely, generalization operators for moving up in the lattice and specialization operators for moving down.

Ensemble phenomena such as the emergence of a phase transition are by no means limited to artificial and inanimate entities. On the contrary, in living beings one may not infrequently observe similar phenomena, whose origin can be tracked down to the effect of the interaction among many components. Indeed, in living organisms the number of cells cooperating in biological and physiological processes is so large that ensemble behaviors are only to be expected. The rapid transition between two neural states was observed as early as the late 1980s (Freeman, 1988). The experimental setting used by Freeman and co-workers included animal and human subjects, engaged in goal-directed behavior, on which high-density electrode arrays were fixed. Action potentials and brain waves (electroencephalograms (EEG) and local field potentials) were then recorded and used to develop a data-driven brain theory.

Freeman and co-workers designed data processing algorithms that enhance the spatial and temporal resolution of the textures of brain activity patterns found in three-layer paleocortex and six-layer neocortex. A major discovery of their work was evidence that cortical self-organized criticality creates a pseudoequilibrium in brain dynamics that allows cortical mesoscopic state transitions to be modeled analogously to phase transitions in near-equilibrium physical systems.

Even though this book is focused on learning, we thought it might be useful to widen its scope to include a brief overview of the emergence of ensemble phenomena (typically phase transitions) in complex networks. Beside their intrinsic interest as systems amenable to be studied via statistical physics methods, complex networks may well impact relational learning because both examples and formulas can be represented as networks of tuples, as we have seen in previous chapters. The same can be said for the constraint graph in CSP and the factor graph in SAT. In ensemble phenomena, emerging from a network of “microscopic” interactions, it is likely that the underlying graph structure has an impact on the observed macroscopic properties; thus cross-fertilization might be of mutual benefit.

Complex networks are complex systems, meaning systems composed of a large number of mutually interacting components. Even though in such systems it is impossible to describe the behavior of the individual components, the patterns of interactions among them allows macroscopic properties to emerge which would be missed by a reductionist approach. Thus, the science of complexity aims to discover the nature of these emerging behaviors and to link them to the system's microscopic level description.

Complex systems

From its very definition, it is clear that the science of complexity naturally derives from statistical physics. Thus, the emergence of phase transitions and the behavior of complex systems have strong links.

In this chapter we will discuss in depth the results that have emerged in recent work on the covering test in first-order logic (Giordana and Saitta, 2000; Maloberti and Sebag, 2004); this was introduced in Section 5.2.3, with particular emphasis on the DATALOG language. With this language, the covering test for a hypothesis ϕ(x1, …, xn) reduces to the problem of finding a substitution θ, for the variables x1, …, xn, by a set of constants a1, …, an that satisfies the formula ϕ.

Moreover, in Section 8.3 we showed how a covering test, i.e., the matching problem (ϕ, e), can be transformed into a CSP. As a consequence, a phase transition may be expected in the covering test, according to results obtained by several authors (Smith and Dyer, 1996; Prosser, 1996). As discussed in Chapter 4, studies on CSPs have exploited a variety of generative models designed to randomly sample areas of interest in the CSP space. As the CSPs occurring in practice may have hundreds or thousands of variables and constraints, the investigations were oriented toward large problems; also, there was much interest in the asymptotic behavior of CSPs for large n.

Machine learning deals with small CSP problems

In machine learning, even though the equivalence of the matching problem with a CSP suggests the emergence of a phase transition, the range of problem sizes involved is much smaller, as the typical number of variables and constraints in relational learning is rarely greater than 10.

In this chapter we introduce the main topic of this book, namely machine learning. In order to make the book self-contained, a brief introduction to the subject is presented.

Learning

The word learning is generally associated with a category of performance, as in learning to play chess or learning to program computers, or with a corpus of knowledge, as in learning geometry. It also often comes in association with some mechanism, as in learning by doing, learning by explanation, learning by analogy, learning by trial and error, and so on.

Learning appears under seemingly very different guises: from habituation (the reduction in sensibility or attention with the repetition of a situation or in problem solving), imitation, rote learning, discrimination (the ability to distinguish one type of input from others), categorization (constructing categories from observations of the environment), to learning whole bodies of knowledge or even discovering theories about the world.

Ubiquity of learning

Since learning (throughout evolution or through cultural and individual acquisition) is at the source of all behavioural and cognitive capabilities in natural systems, as well as in many artificial ones, it is no surprise that it displays such a wide variety of appearances and mechanisms. There are, however, some common aspects and ingredients that underlie many of these diverse manifestations of learning.