A theoretical physicist's dictionary for machine learning, starting where both fields start: statistical mechanics, maximum entropy, and why the Boltzmann distribution is the most likely one.
By Mirco Milletari Β· January 13, 2020
Intro
I have been trained as a theoretical physicist, working on complex quantum systems. Since I moved in the machine learning business, I couldn't stop noticing how much this field share with the physics I have been using for long time. This is not accidental if you consider that physicists have been interested in solving complex optimization problems for quite a long time, especially in relation to a class of systems called spin-glasses; these systems share some of the features of Neural Networks, in particular a complex Loss landscape with many metastable minima. The mathematical concepts developed to understand Spin Glasses and other complex systems are so fascinating and so general that physicists have used them to study the performance of classical optimization problems in computer science, such as minimum-cut, minimum-cost, graph-coloring, satisfability etc... However, the language used by physicists is often very different than the one used by computer scientists, making it difficult to share ideas. Often, during my short career in machine learning, people asked me: what has physics to do with machine learning... my answer is: a lot! This blog is for those who do not see this connection or that are just curious to know more about how the two fields are interconnected.
In this blog series I will try to create a sort of dictionary for physicists who want explore Neural Networks and for computer scientists/engineers who are interested in understanding how physicists try to understand these models. There is no better way of doing that than showing how things are done in details. So the content of this blog will be somehow technical, but hopefully still clear. When showing the math, I will follow the physicist's way of getting numbers out of a calculation, rather than bounds and/or theorems. When analyzing the performance of an algorithm, computer scientists often look at worst/best case scenarios while phycisists are interested in the typical ones. For example, the outcome of each indivisual experiment may be slightly different everytime we collect the data (this is especially true in quantum systems), either for intrisic or extrinsic reasons. Phycisits are usually interested in calculating the most likely outcome rather than the worst/best one, that is usually understood as a large deviation event. A physics model returns a "number", a clear prediction that experimentalists can either verify or prove wrong. In my opinion (and yes I am biased) this a more useful viewpoint when working in machine learning: a Theoretical model giving a "number" we can compare to the numerical outcome.
Before getting into the details of how these different models are built and their meaning, let me use this first post to introduce the framework I will use, a theory called Statistical Mechanics (SM). This theory was introduced towards the end of the 19th century in order to reconcile the laws of thermodynmics and the "newly" proposed atomistic view of nature. Scientists like Boltzmann, Gibbs etc.. contributed to lay the foundations of this framework that proved very effective to explain the macroscopic world starting from its smaller constituents. The theory was later provided with solid mathematical foundations that I will not discuss here; the interested reader can see e.g. []. Also, I will discuss how this theory is at the basis of information theory and hence several concepts in computer science.
Figure 1. (a) Particleβs trajectory in the three dimensional position space, π>π‘. (b) A schematic representation of the 2ππ-dimensional phase space manifold Ξ. A single representative point in Ξ represents the status of the entire system at some time π‘. The inset represents a cartoonish zoom in the representative point, where particlesβs positions and their momentum (arrows) are schematically represented.
We call this space, the phase space and denote it as Ξ. A single point in Ξ represents the status of the system at time π‘, for this reason it is often called a representative point. In principle, one could determine the evolution of the system in time by solving the equation of motions for the π particles. How many particles are in a gas or in a general macroscopic system? You may recall Avogadro's number: for each mole there are Β 1023 particles, so we should be able to solve a comparable number of differential equations, a task that was not only impossible at the time of Boltzmann, but also on modern supercomputer! However, as we discussed above, thermodynmics is governed only by a small number of parameters, so how do we recondile these two approaches? Clearly, not all the information encoded in those 6π degrees of freedom per second is relevant. As the macroscopic world emerges from the microscopic, only a small number of coarse grained quantities are relevant, e.g. temperature is the average kinetic energy of the particles, pressure is the average force the particles in a gas exert on the wall of the container etc... The idea at the very foundation of Gibbs' approach is to replace an average over time with a distributional average called ensemble average. The problem obviously is: how do we choose such a distribution on Ξ? To answer this question we need to introduce the theory of Statistical ensembles; instead of doing this the traditional wayΒ [1, 2], here I want to show you a more modern approach inroduced by JaynesΒ [3, 4] that has the advantage of making the connection to information theory and other concepts in machine learning quite simple.
Ensemble measure from Maximum Entropy
Let us start by introducing an important concept you may be already familiar with: the Entropy. If you are coming from a machine learning background, you have probably used the cross-entropy loss to train your classifier, here I want to show you where this quantity comes from and how it "leaked" in computer science. Boltzmann defined the entropy of a system as:
π=ππ΅logβ‘π,(1)
where π is the volume in phase sapce accessible to the system and ππ΅ is a constant with dimension of energy times inverse temperature. The natural logarithm is counting the number of configurations corresponding to a macroscopic state. Well, this may sound a bit cryptical, but it will be clear in a shortwhile; before getting into the math, in plain english it means that many different microscopic configurations of a system correspond to the same macroscopic, observed one. Take the temperature for example; you may recall that I have stated without proof that it corresponds to the average kitetic energy of the N particles in the system. The point is that this definition does not care about the kinetic energy of the single particles, say particle π1 has energy π1, particle π2π2 etc ... we could swap the labels and say that π1 has energy π2 and π2 energy π1, the mean energy Β―π=(π1+π2)/2 is the same for these two different configurations. However, we could prepare the system in a very special configuration; this configuration will occupy only a specific point in phase space, for which π=1 and therefore π=0; this state is so special that it is unlikely to happen spontaneouly. On the other hand, most likely states, correspond to those with higher entropy, i.e. those configurations that occupy a larger volume of the phase space (I'll come back on this in a moment). The other interesting property of π is that it is an "extensive" quantity, i.e. the entropy of two systems is the sum of the entropies of the two single systems. Enough with talking, let us get to the math!
Let us followΒ [1, 2, 3, 4] and find which is the most probable distribution on Ξ. As we define spaces of "numbers", and functions mapping one number into another, we can define space of functions and "functionals", mapping functions into functions, see e.g. Ref.Β [5] for a quick introduction to functional calculus, or RefΒ [6] for a comprehensive one. In this space of all possible distributions, we want to find the one that maximizes the entropy on Ξ, i.e. the distribution that occupies the largest volume in Ξ.
The first condition enforces particle number conservation, while the second energy conservation, where πΈ is the total energy of the macroscopic system. Note that the latter condition also assumes that the system is "diluted", i.e. interactions play little to no role. For the sake of correctness let me say here that interactions between particles do play a big role to bring the system towards to equilibrium however, once equilibrium is reached, they are no longer necessary to describe this state. If this sounds confusing to you do not despair! It took people quite a long time to accept it; the precise mathematical formulation of this statement was given by Boltzmann in his H-theorem, seeΒ [1, 2] if you are curious. Going back to our task we now ask: Which portion π of the entire phase space Ξ is occupied by the system? Fix a specific configuration for the moment; one particle occupies a volume π, then 2 particles will occupy a phase space volume of π2 (see again how the N-particle volume element was defined above) so ππ particles will take πππ. As we want to consider the volume occupied by all possible configurations, we need to include a combinatorial factor. In how many ways can we place π distinct particles into π distinct cells, with π1 particles in the first cell, π2 in the second, etc. ? Well, this number is given by the multinomial coefficient, and we find that the phase space volume can be written as:
π=π!βπππ!βππππ.(3)
In case you got a bit lost let me summarize what we have done so far before getting into the math. We want to find the distribution that occupies the largest phase space volume π. In order to do so, we discretize the phase space in smaller (but finite) cells π and fill them with (non-interacting) particles satifying the macroscopic conditions in Eq.Β (2). We now proceed maximizing the entropyΒ (1); in order to enforce the macroscopic constraints we use the method of Lagrange multipliersΒ [6], and build a new functional (here we use ππ΅=1 and reinstate at the end of the calculation):
Our working assumption is that the π cells are populated by a large number ππ of particles and πβ«π; this allows us to use Stirling's approximation for the factorial π!ββ2πππππβπ for πβ«1, see e.g. appendix B in Ref.Β [2] for a nice derivation of this result. Using this approximation in the entropy and retaining only the leading terms we obtain:
We are now ready to maximize the functional defined inΒ (4) by varying ππβππ+πΏππ (where πΏππβͺππ), and keeping terms up to the second order in the variation. The linear terms are trivial; the term involving the logarithm can be written as
where we have used the Taylor expansion of the logarithm logβ‘(1+π₯)βπ₯βπ₯2/2+.... Using this result in back in the functional we arrive at:
The optima is obtained from the condition that the first functional variation is zero, while the sign of the second variation tells us if this is a maximum or a minimum (or a saddle):
where π=1+πΌ is a constant to be determined, Β―ππ the most likely distribution; since the second variation is negative, we can see that this optimal solution corresponds to a maximum of the Entropy functional. The most likely distribution is known as the Maxwell-Boltzmann (MB) distribution; among all the microscopic configurations satidfying the macroscopic constraints, MB is the one common to the largest number of them.
Let us go back to the constraints, as we are working with probabilities we want βπΒ―ππ=1; using the definition of Β―ππ in the first constraint e see that this also imlpies that in the thermodynamic limit when both π and π goes to infinity, theor ratio tends to 1. We have:
The normalization constant π is known as the partition function and it plays a central role in classical and quantum Statistical mechanics and Quantum Field Theory. Well, let us stay classical for the moment and workout the second constraint. Using the definition of Β―ππ back in Eq.Β (2) we find:
But we know this result, it is the equipartition theorem of thermodynmics, stating that the energy is equally distributed among all the different degrees of freedom of the gas; in three spatial dimensions the theorem reads: πΈ=3π/2ππ΅π. Comparing this espression with the result we just found, we can identify π½β1=ππ΅π as the inverse temperature in units of the Boltzmann's constant. As a sanity check, we can see that π½ has inverse dimension of energy, so that the exponential is dimensionless as it should be.
As πβ«ππ, the term on the lhs goes to zero and the the distribution becomes peaked around the most probable value Β―ππ. We can conclude saying that the MB is the most probable distribution for a macroscopic system at equilibrium. It took some efforts but we found a logically pleasant construction of the ensemble picture. Moreover we were able to introduce some concepts from statistics that will be very useful in the future. The merit of the above construction is that it can be generalized not only to more interesting physical situations, but also to general scenarios that have apparently little to do with physics. In the next episode we will show how the maximum entropy principle is used in information theory, with applications in natural language processing.
References
K. Huang, Statistical Mechanics, John Wiley and Sons (1987).
C. DiCastro and R. Raimondi, Statistical Mechanics and Applications in Condensed Matter, Cambridge university press (2015).
E.T. Jaynes, Probability Theory, the logic of Science, Cambridge university press (2003).
E.T. Jaynes, Information Theory and Statistical Mechanics I-II, Physical Review 106 620-630 (1957) and Physical Review, 108 171-190 (1957).