In this chapter we discuss a theory for the freezing of an isotropic liquid into a crystalline solid state with long-range order. The transformation is a first-order phase transition with finite latent heat absorbed in the process. We focus on a first-principles orderparameter theory of freezing that originated from the pioneering work of Ramakrishnan and Yussouff (1979). The theory approaches the problem from the liquid side and views the crystal as a liquid with grossly inhomogeneous density characterized by a lower symmetry of the corresponding lattice. This is in contrast to description of the crystal in terms of phonons. The crucial quantity characterizing the physical state of the system in this non-phonon-based model is the average one-particle density function n(x). The thermodynamic description of either phase involves a corresponding extremum principle for a relevant potential. The latter, obtained as a functional of the one-particle density n(x) and the stable thermodynamic state of the system, is identified by the corresponding density required for invoking the extremum principle. This approach, which is generally referred to as the density-functional theory (DFT) of freezing (Haymet, 1987; Baus, 1987, 1990; Singh, 1991; Löwen, 1994; Ashcroft 1996), has been improved over the years and successfully applied for the study of liquid-to-crystal transitions in various simple liquids, the solid–liquid interface, two-dimensional systems, metastable glassy states, etc. For applications of density-functional methods in statistical mechanics there exist general reviews (Evans, 1979; Henderson, 1992).

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.

The fluctuating-hydrodynamics approach discussed earlier takes into account only the transport properties at the level of completely uncorrelated motion of the fluid particles. The corresponding dissipative processes are expressed in terms of bare transport coefficients of the fluid. The strongly correlated motion of the fluid particles which occurs at high density is not take into consideration here. This is reflected through the Markov approximation of the transport coefficients and the short correlation of the corresponding noise representing the fast degrees of freedom in the system. The Markovian equations for the collective modes involving frequency-independent transport coefficients constitute a model for the dynamics of fluids with exponential relaxation of the fluctuations. The corresponding equations of motion for the collective modes are linear. However, exceptions occur in certain situations in which the description of the dynamics cannot be reduced to a set of linearly coupled fluctuating equations with frequency-independent transport coefficients. In this chapter we will consider the nonlinear dynamics of the hydrodynamic modes for studying the strongly correlated motion of the particles in a dense fluid.

Nonlinear Langevin equations

We present in this section the formulation of a set of nonlinear stochastic equations for the dynamics of the many-particle system. We first discuss the physical motivation for extension of the fluctuating-hydrodynamics approach to include nonlinear coupling of the slow modes.

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

We have discussed the construction of the nonlinear Langevin equations for the slow modes in a number of different systems in the previous chapter. Next, we analyze how the nonlinear coupling of the hydrodynamic modes in these equations of motion affects the liquid dynamics. In particular, we focus here on the case of a compressible liquid in the supercooled region. In this book we will primarily follow an approach in which the effects of the nonlinearities are systematically obtained using graphical methods of quantum field theory. Such diagrammatic methods have conveniently been used for studying the slow dynamics near the critical point (Kawasaki, 1970; Kadanoff and Swift, 1968) or turbulence (Kraichnan 1959a, 1961a; Edwards, 1964). The present approach, which is now standard, was first described by Martin, Siggia, and Rose (1973). The Martin–Siggia–Rose (MSR) field theory, as this technique is named in the literature, is in fact a general scheme applied to compute the statistical dynamics of classical systems.

The field-theoretic method presented here is an alternative to the so-called memoryfunction approach. The latter in fact involves studying the dynamics in terms of non-Markovian linearized Langevin equations (see, for example, eqn. (6.1.1) which are obtained in a formally exact manner with the use of so called Mori–Zwanzig projection operators. This projection-operator scheme is described in Appendix A7.4). The generalized transport coefficients or the so-called memory functions in this case are frequency-dependent and can be expressed in terms of Green–Kubo forms of integrals of time correlation functions.

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.

In Chapter 4 we introduced the Kauzmann temperature TK as a possible limiting temperature for the existence of the supercooled liquid phase. The original hypothesis due to Kauzmann proposes eventual crystallization in the supercooled liquid at very low temperatures as a possible way out of the paradoxical situation in which the entropy of the disordered state becomes less than that of the crystal. Another possible explanation of the Kauzmann paradox could be that the simple extrapolation of the high-temperature result to very low temperature is not correct and the entropy difference between supercooled liquid and crystal remains finite down to very low temperature (Donev et al., 2006; Langer, 2006a, 2006b, 2007), finally going to zero only near T = 0. Either of these resolutions, however, leaves us with no understanding of the dramatic slowing down and associated phenomenology of the supercooled region above Tg. The difference of the entropy of the supercooled liquid from that of the solid having only vibrational motion around a frozen structure represents the entropy due to large-scale motion and is identified with the configurational entropy Sc of the liquid. The rapid disappearance of the configurational entropy of the disordered liquid or the so-called “entropy crisis” poses an important question that is essential for our understanding of the physics of the glass-transition phenomena and the divergence of the relaxation time at Tg. Apart from having a characteristic large viscosity, the supercooled liquid shows a discontinuity in specific heat cp at Tg due to freezing of the translational degrees of freedom in the liquid.

In the previous chapters we have discussed the transition of the liquid from a disordered fluid state to an ordered crystalline state through a first-order phase transition at the melting or freezing point Tm. In the present chapter we consider the behavior of the liquid supercooled below Tm and the associated phenomenon of the liquid–glass transition.

The liquid–glass transition

Almost all liquids can, under suitable conditions, be supercooled below the freezing point Tm while avoiding crystallization. The undercooled liquid continues to remain in the disordered state and is characterized by very rapidly increasing viscosity with decreasing temperature. The characteristic relaxation time τ of the liquid grows with increasing supercooling. Eventually, at low enough temperature, the supercooled liquid becomes so viscous that it can hold shear stress and behaves like a solid. At this stage the supercooled liquid is said to have transformed into a glass. The latter is an amorphous solid without long-range order. It is in fact in a nonequilibrium state on the time scale of the experiment. The relaxation time τ required for the supercooled liquid to equilibrate is longer than the typical time scale τexp of an experiment. Apart from the viscosity, other dynamic quantities such as the diffusion coefficient, dielectric response function, and conductivity change strongly with increasing supercooling. In contrast, thermodynamic properties such as the specific heat, enthalpy, compressibility, and static structure factor do not show any strong change with supercooling.

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.

If the liquid is cooled beyond the corresponding freezing point Tm at which the liquid and crystalline phases coexist in equilibrium, a thermodynamic driving force builds up towards forming the crystal. In this chapter we will discuss how the liquid transforms into a crystal, focusing on how the changes in the liquid are initiated and on the nature of the crystalline region that is formed. This process is referred to as nucleation. The thermodynamic force favoring the formation of the crystal seed in the supercooled liquid competes with the process of forming an interface between the solid and the liquid. The cost of the interfacial free energy therefore presents a barrier to the formation of the new phase. Only when the driving force is made large enough by moving deep into the supercooled state does crystallization occur on laboratory time scales. Thus pure water can be cooled to -20 °C or below without freezing. Our focus here will be mainly on the process of crystallization of solid from the melt. The condensation of vapor into liquid is a very thoroughly studied process that has been discussed in various reviews (Stanley, 1971; Evans, 1979; ten Wolde et al., 1998). For condensation from a low-density gas or crystallization from dilute solution, it is easier to identify the nucleating bubbles since they differ widely in composition from the surrounding phase.

This book is aimed at teaching the important concepts of the various theories of statistical physics of dense liquids, freezing, and the liquid–glass transition. Both thermodynamic and time-dependent phenomena relating to transport properties are discussed. The standard tools of statistical physics of the dense liquid state and the associated technicalities needed to learn them are included in the presentation. Details of some of the calculations have been included, whenever needed, in the appendices at the ends of chapters. I hope this will make the book more accessible to beginners in this very active field of research. The book is expected to be useful for graduate students and researchers working in the area of soft-condensed-matter physics, chemical physics, and the material sciences as well as for chemical engineers.

We now give a brief description of what is in the book. The first chapter reviews the basics of statistical mechanics necessary for studying the physics of the liquid state. Key concepts of equilibrium and nonequilibrium statistical mechanics are presented. The topics covered here have been chosen keeping in mind the theories and concepts covered in the subsequent chapters of the book. Following this introductory chapter, we focus on the physics of liquids near freezing. In Chapter 2, we demonstrate how the disordered liquid state as well as the crystalline state of matter with long-range order can be understood in a unified manner using thermodynamic extremum principles.