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.

Theoretical developments on the dynamics of a dense liquid using a statistical-mechanical approach primarily involve a small set of slow collective densities termed hydrodynamic modes. The time scales of relaxation of these modes are much longer than those for the microscopic modes of the system. The basic approach adopted here is the analysis of the time correlation functions (introduced earlier in Chapter 1) of the slow modes. In the present chapter and the next two chapters we discuss microscopic methods for calculating the correlation functions involving the fluctuation or hydrodynamic approach. We focus primarily on the simplest type of correlation functions involving fluctuations at two different spatial and time coordinates. Owing to time translation invariance, equilibrium two-point correlation functions of hydrodynamic modes at the same time over different spatial points are time-independent and provide us with information on the thermodynamic behavior of the system. On the other hand, the dynamic behavior of the system is linked to the correlation of physically observable quantities at two different times. The time correlation function of density fluctuations is particularly important for our discussion of the slow dynamics in a liquid. In the simplest of the theoretical models, the decay of the correlation with time is exponential. We discuss here how such exponential relaxation behavior can be understood using linear dynamics of the fluctuations. The formalism developed in the later parts of this chapter allows in a natural way the extension of the macroscopic hydrodynamics to intermediate length and time scales, and is referred to as generalized hydrodynamics.

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.

The central idea underlying theoretical studies of the movement of organisms is that they need to encounter their targets. The targets can be other organisms of the same species (e.g., mates) or of a different species (e.g., prey) or, more generally, anything else sought (e.g., nesting sites). In the context of reactiondiffusion processes, the reactions (e.g., eating and mating) only take place when the relevant organisms successfully diffuse toward each other and meet. We next discuss a general theoretical approach to the study of encounter rates.

A general theory of searchers and targets

We classify the two interacting reactive-diffusive species (i.e., organisms) as either searcher (e.g., predator, forager, parasite, pollinator, male) or target (e.g., prey, food, female). Both searchers and targets move stochastically. We can now include most of the interactions in real ecosystems in this general framework [19], including the classical predator-prey interactions where an organism eats (usually smaller) organisms. It also includes diverse other interactions, such as osmotrophs looking for substrates and nutrients; parasites (including viruses) infecting organisms much larger than themselves (classical host-parasite interactions); organisms looking for aggregates (mixtures of amorphous organic matter, micro-organisms and/or inorganic particles), swarms, wakes, etc., also larger than themselves; and even mating encounters in which both male and female may have similar sizes (although sexual dimorphism is common) [19].

According to the theory of optimal foraging [128, 364], evolution through natural selection has led over time to highly efficient – even optimal – strategies.

From the previous chapters, we see that (1) superdiffusion optimizes search efficiencies under specific (but common) circumstances and that (2) many animals move superdiffusively. Assuming these two facts, does it follow that there is a causal relation between them? Lévy strategies indeed optimize random searches, but does it necessarily follow that selective pressures systematically forced organism adaptation toward this optimal solution?

This is an important question because an adaptive pathway toward an optimal solution can prematurely stop at some suboptimal point that decreases the selection pressure on this particular feature to a level below the selective pressures on other issues [397]. Biology and physiology are replete with suboptimal solutions. The classic example is the structure of the human retina, which has blood vessels on the wrong side of the photosensitive layer [96]. Compromise solutions arise because adaptation (1) includes a stochastic component, (2) has to build on preexisting designs, and (3) occurs in a complex field where other pressures may be present and may possibly be stronger.

Dolphins, in the context of (mammalian) swimming adaptations, perform well, but how can we know whether or not their shape represents an optimal design? Some species of shark may have an even better hydrodynamic shape. Also, why did dolphins return to the ocean when selective pressures were pushing for improved terrestrial adaptation? The complex evolutionary history of real organisms contains many such contingent situations, such as changing selective pressures, genetic drift, low-number bottlenecks, and rare catastrophic events.