5  Maximum-Entropy Learning

Released

August 3, 2026

Last updated

September 22, 2026

5.1 What this chapter means by maximum-entropy learning

Throughout this book the term maximum-entropy learning is used in a broad sense: it refers to a family of methods rather than to one algorithm. The family contains methods in which nothing is learned at all, e.g., the cooperative games of Section 5.3, as well as methods in which an energy function is fitted from data, e.g., the set functions of Section 5.4. We therefore need a vocabulary that keeps the two apart. We borrow it from probabilistic graphical models, whose standard textbooks are organized into three parts, representation, inference, and learning (Koller and Friedman 2009), and we read every method through these three levels in turn. In this section we make each level precise, state the definition of the family, and fix the notation used in the rest of the chapter.

Notation. We write \(\mathsf{T}(x) = (f_1(x), \dots, f_K(x))\) for the vector of features whose expectations are constrained, i.e., the sufficient statistics of the resulting exponential family. The upright sans-serif \(\mathsf{T}\) is used on purpose: the italic \(T\) is reserved for temperature throughout the book, and the two must not be confused. \(h(x)\) denotes a base measure, i.e., a reference distribution, taken to be uniform unless stated otherwise; \(\boldsymbol{\lambda}\) denotes the vector of Lagrange multipliers (the natural parameters), \(Z\) the partition function, and \(\mathrm{KL}(q \,\Vert\, p)\) the Kullback–Leibler divergence.

5.1.1 Representation: maximum-entropy models in two forms

The first level asks which model class a method uses. In maximum-entropy learning the answer is the Gibbs distribution, equivalently the exponential family, and it can be written in two forms.

The constrained form is the one of Section 2.3, stated here with a base measure (Jaynes 1957; Kullback 1959; Csiszár 1975):

\[ \begin{aligned} p^{\star} \;&=\; \operatorname*{arg\,min}_{q}\; \mathrm{KL}(q \,\Vert\, h) \quad \text{s.t.} \quad \mathbb{E}_{q}[\mathsf{T}(x)] = \boldsymbol{\mu} , \\[4pt] p^{\star}(x) \;&=\; \frac{h(x)\, \exp\big(\boldsymbol{\lambda}^{\top} \mathsf{T}(x)\big)}{Z(\boldsymbol{\lambda})} . \end{aligned} \tag{5.1}\]

When \(h\) is uniform, minimizing \(\mathrm{KL}(q \,\Vert\, h)\) is the same as maximizing the entropy \(H(q)\), and Equation 5.1 is exactly the Jaynes problem of Section 2.3. For a general \(h\) the principle is that of minimum relative entropy, known as minimum discrimination information in Kullback’s work (Kullback 1959) and as minimum cross-entropy in the axiomatic treatment of Shore and Johnson (1980); the solution \(p^\star\) is the I-projection of \(h\) onto the constraint set (Csiszár 1975).

The free-energy form is the one introduced in Chapter 3. Given an energy \(E(x)\) and a temperature \(T > 0\), define the variational free energy

\[ \begin{aligned} \mathcal{F}_{T}(q; E) \;&=\; \mathbb{E}_{q}[E] \;+\; T\, \mathrm{KL}(q \,\Vert\, h) , \\[4pt] p_{E,T} \;&=\; \operatorname*{arg\,min}_{q}\; \mathcal{F}_{T}(q; E) \;=\; \frac{h(x)\, e^{-E(x)/T}}{Z} , \qquad \min_{q} \mathcal{F}_{T}(q; E) \;=\; -T \log Z . \end{aligned} \tag{5.2}\]

For uniform \(h\) this is \(\mathbb{E}_q[E] - T\,H(q)\) up to a constant, i.e., the \(U - TS\) of Chapter 3, and the identity \(\min_q \mathcal{F}_T = -T \log Z\) is the variational representation of the log-partition function (Wainwright and Jordan 2008, sec. 3.6), known in statistical physics as the Gibbs variational principle.

The two forms are equivalent by Lagrangian duality. Setting \(E = -\boldsymbol{\lambda}^{\top} \mathsf{T}\) and \(T = 1\) in Equation 5.2 recovers Equation 5.1, and the constraint values and the multipliers are in one-to-one correspondence through \(\boldsymbol{\mu} = \nabla_{\boldsymbol{\lambda}} \log Z(\boldsymbol{\lambda})\), provided that \(\boldsymbol{\mu}\) lies in the interior of the marginal polytope (the regularity condition discussed in Section 5.2). One can also read the equivalence geometrically. For the empirical distribution \(\hat p\) and the maximum-likelihood member \(p^\star\) of the exponential family, Csiszár’s Pythagorean identity \(\mathrm{KL}(\hat p \,\Vert\, h) = \mathrm{KL}(\hat p \,\Vert\, p^\star) + \mathrm{KL}(p^\star \,\Vert\, h)\) holds (Csiszár 1975), so the maximum-entropy solution and the maximum-likelihood solution are one point approached from two directions (Della Pietra et al. 1997).

Both forms will be used in this chapter, and the choice is a matter of emphasis. We state a model in the constrained form when the point is what is known, i.e., the form of \(\mathsf{T}\) declared by the modeler: clique indicators in a Markov random field, \(n\)-gram features in a maximum-entropy classifier (Berger et al. 1996), the invariant statistics of INSET (Section 5.4.3), reward features together with the dynamics in reinforcement learning (Section 5.5). We state it in the free-energy form when the point is what is computed: an ELBO, a mean-field iteration, a soft Bellman equation, an annealing schedule. It is worth noting where the knowledge sits. It does not sit in the value of \(\boldsymbol{\mu}\), which the data supply, but in the form of \(\mathsf{T}\): the content of the theorem behind Equation 5.1 is that the energy is confined to the span of the declared features, \(E = -\boldsymbol{\lambda}^\top \mathsf{T}\), not that it has an exponential shape, since any strictly positive \(p\) can be written as \(e^{-E}\) with \(E := -\log p\).

A related point is that the two forms constrain different variables. The constrained form restricts the distribution \(q\); an architecture for \(E_\theta\) restricts the energy, i.e., the dual variable, and the two descriptions coincide exactly only when the admissible energies form a linear space (equality constraints, with free multipliers) or a convex cone (inequality constraints, with nonnegative multipliers). For a neural energy the correspondence holds slice by slice through the last linear layer, and at every stationary point through the likelihood equations of Section 5.1.3, but not for the family as a whole, which is a curved rather than an exponential family (Efron 1975). Symmetry is the exception that lives on both sides at once: invariance of the distribution under a group \(G\) is a set of homogeneous linear constraints \(\mathbb{E}_q[f \circ g - f] = 0\), the maximum-entropy solution inherits it (Jaynes 1968), and it is equivalent to restricting the features to functions of the maximal invariant of the group (Bloem-Reddy and Teh 2020), which is the route taken in Section 5.4.3.

5.1.2 Inference: free-energy minimization over a tractable family

The second level asks how the distribution is computed or approximated. In maximum-entropy learning, inference is the minimization of the free energy of Equation 5.2 over a tractable family \(\mathcal{Q}\) of distributions,

\[ q^{\star}_{\mathcal{Q}}(E, T) \;=\; \operatorname*{arg\,min}_{q \in \mathcal{Q}}\; \mathcal{F}_{T}(q; E) . \tag{5.3}\]

The choice of \(\mathcal{Q}\) is what distinguishes the algorithms. If \(\mathcal{Q}\) is the set of all distributions, the inference is exact and returns \(p_{E,T}\). If \(\mathcal{Q}\) is the set of product distributions, Equation 5.3 is mean-field variational inference (Jordan et al. 1999; Wainwright and Jordan 2008), the workhorse of Section 5.3 and Section 5.4. If \(\mathcal{Q}\) is the set of trajectory distributions induced by a policy under the true dynamics, it is maximum-entropy reinforcement learning (Section 5.5). Markov chain Monte Carlo replaces the minimization by sampling, and a path in \(T\) is an annealing schedule (Chapter 8). The two limits are instructive: as \(T \to 0\), Equation 5.3 becomes energy minimization, i.e., the inference of energy-based models in the sense of Section 4.1; as \(T \to \infty\), it returns the base measure.

A remark on terminology is in order. We deliberately avoid the phrase “maximum-entropy inference”. In Jaynes’ writing, inference means choosing a distribution from constraints, which is our representation level; in the graphical-model literature it means computing marginals or posteriors, which is the present level. For the latter we say variational inference or free-energy minimization.

5.1.3 Learning: fitting the energy through the inference

The third level is active when the energy itself carries parameters, \(E_\theta\), which are fitted from data \(\mathcal{D}\) through the inference of the second level:

\[ \min_{\theta}\; \mathcal{L}\big(\mathcal{D};\; q^{\star}_{\mathcal{Q}}(E_\theta, T)\big) . \tag{5.4}\]

The supervision in \(\mathcal{D}\) can take several forms: i.i.d. samples, as in maximum likelihood; prescribed moments, as in the classical setting; observed optimal solutions, as in the optimal subset oracle of Section 5.4; demonstrated trajectories, as in inverse reinforcement learning (Section 5.5); or preferences. In every case the division of labour is the same. The learner chooses the form of \(\mathsf{T}\), i.e., an architecture or a symmetry; the data supply the constraint content; and the maximum-entropy principle fixes the distribution. The inner problem Equation 5.3 is strictly convex in \(q\), whereas the outer problem Equation 5.4 is in general non-convex in \(\theta\).

Maximum likelihood deserves a separate comment, because it is where the two levels meet. For the Gibbs model \(p_\theta \propto h\, e^{-E_\theta}\) (we set \(T = 1\) and absorb the scale into \(E_\theta\)), the gradient of the negative log-likelihood is \(\mathbb{E}_{\hat p}[\nabla_\theta E_\theta] - \mathbb{E}_{p_\theta}[\nabla_\theta E_\theta]\) (Equation 4.5), so at any stationary point

\[ \mathbb{E}_{\hat p}\big[\nabla_\theta E_\theta\big] \;=\; \mathbb{E}_{p_\theta}\big[\nabla_\theta E_\theta\big] . \tag{5.5}\]

These are the classical likelihood equations, and they say that the model matches the data on the moments of the features \(\nabla_\theta E_\theta\). For a linear energy \(E = -\boldsymbol{\lambda}^{\top} \mathsf{T}\) they are exactly the constraints of Equation 5.1 with \(\boldsymbol{\mu}\) the empirical moments — this is the maximum-entropy / maximum-likelihood duality — and the Boltzmann machine learning rule, clamped correlations minus free correlations (Ackley et al. 1985), is their best-known early instance in machine learning. For a neural energy the features move with \(\theta\), so the constrained form holds only at each stationary point; the general case is better written in the free-energy form, as a saddle-point problem (Section 5.6).

5.1.4 Definition of maximum-entropy learning, and a running example

We can now state the definition used in this chapter.

NoteDefinition: maximum-entropy learning

A method belongs to maximum-entropy learning if i) its model class is the Gibbs distribution of Equation 5.1 or Equation 5.2, determined by a declared form of constraint; ii) its inference is a free-energy minimization Equation 5.3 in which the entropy term is explicit and load-bearing, i.e., \(T > 0\); and, when the energy is fitted from data, iii) the fitting is carried out through that inference, as in Equation 5.4. A method satisfying i) and ii) is a maximum-entropy model with variational inference; a method satisfying i)–iii) is termed a maximum-entropy learner. When the Kullback–Leibler divergence in i)–ii) is replaced by the Bregman divergence of another proper scoring rule, the same structure defines a generalized entropy (Grünwald and Dawid 2004); we then speak of maximum-entropy learning in the generalized sense, and reserve the unqualified term for the Shannon case.

Two consequences of the definition are worth spelling out. First, the energy-based models of Chapter 4 are all maximum-entropy models in the sense of i), and their training criteria differ in how they treat the inner problem that carries the entropy. Maximum likelihood and its approximations — sampled, as in persistent contrastive divergence (Tieleman 2008); truncated, as in contrastive divergence (Hinton 2002) and short-run MCMC (Nijkamp et al. 2019); or amortized, as when a generator is trained to maximize its own entropy (Kumar et al. 2019) — are maximum-entropy learners in the strict sense of iii). Score matching and noise-contrastive estimation replace the log score by another proper scoring rule; each such rule carries its own generalized entropy and Bregman divergence (Grünwald and Dawid 2004), and we call these methods maximum-entropy learners in the generalized sense, naming the entropy in each case (Section 5.6.3). The zero-temperature losses of energy-based learning, e.g., the perceptron and hinge losses, lie on the boundary of the family. Second, methods in which the energy is given — a cooperative game (Section 5.3), a reward function in the soft actor–critic (Section 5.5), a composed energy used for guidance (Chapter 8) — are maximum-entropy models with variational inference and no learner. Nothing is learned in them, and yet they belong to the family, because the entropy term does the work. Table 5.1 places the strands of this chapter, and two neighbouring ones, on the three levels.

Table 5.1: The strands of maximum-entropy learning read through the three levels. A dash means that the level is not active: the energy is given rather than learned.
Strand Representation Inference Learning
Classical MaxEnt, log-linear models, CRFs (Section 5.2) Gibbs with declared features exact, or message passing multipliers by maximum likelihood
Undirected graphical models (Section 5.2) Gibbs over cliques variational or sampling parameters by maximum likelihood
Energy-based models by maximum likelihood or CD (Chapter 4) Gibbs with learned features MCMC, sampled or truncated energy by maximum likelihood
Energy-based models by score matching or NCE (Chapter 4) Gibbs with learned features none (local divergence) or a fixed noise proposal energy by a generalized (Bregman) divergence; see Section 5.6.3
Energy-based cooperative games (Section 5.3) Gibbs over coalitions, one constraint mean field — (game given)
Optimal subset oracle (Section 5.4) Gibbs over \(2^V\), neural set function mean field, unrolled energy from optimal subsets
Maximum-entropy RL with a given reward (Section 5.5) Gibbs over trajectories soft Bellman recursion — (reward given)
Inverse RL (Section 5.5) Gibbs over trajectories soft Bellman recursion reward from demonstrations
Guidance and refinement (Chapter 8) Gibbs tilt of a pretrained generator guided or annealed sampling, reranking — (energy given to the sampler; if trained, by a separate learner)
Maximum-entropy post-training (Chapter 9) Gibbs tilt of a pretrained model amortized into the weights reward from preferences, or through the closed form (DPO)

The status of the temperature follows the same pattern. When the energy is given and no constraint level is prescribed, \(T\) is a genuine hyperparameter: the coalition temperature \(\tau\) of Section 5.3, the entropy coefficient \(\alpha\) of the soft actor–critic, the KL coefficient \(\beta\) of policy optimization (Equation 6.2). When the energy is learned and its family is closed under rescaling, \(T\) is absorbed into the scale of \(E_\theta\) and is not identifiable; this is the case of Section 5.4. When a constraint level is prescribed, \(T\) is the reciprocal of a multiplier and is determined by that level, as in the canonical ensemble of Chapter 3.

A running example. The simplest maximum-entropy learner is the maximum-entropy classifier of classical natural language processing (Berger et al. 1996), i.e., multinomial logistic regression. The features are indicator functions \(f_k(x, y)\), e.g., “word \(k\) occurs in document \(x\) and the label \(y\) is sports”. The constrained form asks for the conditional distribution closest to uniform that matches the empirical expectations of all \(f_k\); the solution is \(p(y \mid x) \propto \exp\big(\boldsymbol{\lambda}^{\top} \mathsf{T}(x, y)\big)\), and fitting \(\boldsymbol{\lambda}\) by maximum likelihood is the dual problem, so the likelihood equations Equation 5.5 are precisely the moment constraints. In the free-energy form, the negative log-likelihood of one example is \(-\boldsymbol{\lambda}^{\top} \mathsf{T}(x, y) + \log \sum_{y'} \exp\big(\boldsymbol{\lambda}^{\top} \mathsf{T}(x, y')\big)\), i.e., the energy of the observed label plus the free energy of the label ensemble. Inference is exact because the label set is small, and the temperature is absorbed into the scale of \(\boldsymbol{\lambda}\). Levels i)–iii) are all present and all three are trivial; the rest of this chapter is about what happens when the space is the power set \(2^V\) or the set of trajectories, and the inference is no longer exact.

5.2 Graphical models as an explanatory family

Probabilistic graphical models (PGMs) organize a joint \(p(x)\) by a graph that encodes a set of conditional independencies (Pearl 1988; Koller and Friedman 2009). The encoding is not the same in the two standard realizations. On an undirected graph, a missing edge is pairwise independence given all other variables (and, when \(p\) is strictly positive, the pairwise, local, and global Markov properties coincide). On a directed acyclic graph the criterion is d-separation. A missing arrow still carries an independence — the local Markov property says each variable is independent of its non-descendants given its parents — but not the same independence as a missing undirected edge: conditioning on all the remaining variables can open a path through a collider, so the MRF’s pairwise reading has no directed analogue (Pearl 1988). The field is older than the modern energy-based revival of Chapter 4, larger than this chapter, and still the working language for structured uncertainty in statistics and in much of classical machine learning — vision, speech, computational biology, and expert systems among them.

An undirected model, or Markov random field (MRF), scores compatibilities. On a finite graph \(G\), a strictly positive distribution is Markov with respect to \(G\) if and only if it is a Gibbs distribution that factors over the cliques of \(G\) (Hammersley–Clifford; the published proof usually cited is Besag (1974)). In energy language that is already the definition of Chapter 4, with the extra discipline that \(E\) is a sum of local terms:

\[ p(x) \;=\; \frac{1}{Z}\, \exp\!\Bigl(-\sum_{C \in \mathrm{cliques}(G)} E_C(x_C)\Bigr). \]

(The sum may equally be taken over maximal cliques: smaller clique terms can be absorbed.) The Gibbs \(\Rightarrow\) Markov direction is elementary and needs no positivity; it is Markov \(\Rightarrow\) Gibbs that does. Without it the implication fails: Moussouris’ four-cycle example is a distribution that is Markov with respect to \(G\) but admits no Gibbs factorization over the cliques of \(G\) (Moussouris 1974).

A directed model, or Bayesian network, tells a generative story. If \(\mathrm{pa}_i\) are the parents of coordinate \(i\) in a directed acyclic graph,

\[ p(x) \;=\; \prod_i p\bigl(x_i \mid \mathrm{pa}_i\bigr) \tag{5.6}\]

(Pearl 1988). The arrows are often read as explanation or cause; the undirected edges of an MRF are not. Pearl’s own contrast is that a Bayes net is a knowledge base of directed influences, while a Markov network is a system of symmetric associations. That reading is a stretch beyond what the joint distribution alone licenses: from observational data a DAG is identifiable only up to its Markov equivalence class — every DAG with the same skeleton and the same v-structures — so “the graph is the explanation” should be heard as a claim about which independencies the graph asserts, not about which arrow points which way.

This book treats the pair as an explanatory family, in a local sense that is not a standard name in the literature. The graph is the explanation: it says which independencies the joint is required to satisfy, and the factorization is what makes the model intelligible rather than a mere scoring rule. That reading is closest to Pearl’s directed case. It is more of a stretch for MRFs, whose native language is compatibility rather than cause. Both, however, explain the joint by a sparse independence hypothesis, and that is the sense in which they belong together here.

How much of this is classical maximum entropy? Enough to be worth saying, not enough to be a slogan. The maximum-entropy distribution of Section 2.3 that matches prescribed expectations of clique-supported features is an exponential-family MRF: the Lagrange multipliers are the feature weights, and the solution is the Gibbs form above (with \(E_C = -\sum_k \lambda_k f_k\) over the features supported on \(C\); the sign is the usual energy convention) (Jaynes 1957; Della Pietra et al. 1997; Wainwright and Jordan 2008). On a finite discrete state space every strictly positive MRF arises this way, because the clique-configuration indicators are a sufficient statistic. The modern synthesis of Wainwright and Jordan writes undirected graphical models, exponential families, and entropy duality as one subject. Feature induction for random fields (Della Pietra et al. 1997) and the maximum-entropy models of classical NLP (Berger et al. 1996) are the same exponential-family construction; they are MRFs only when the features have local graphical support — Stephen Della Pietra, Vincent Della Pietra, and John Lafferty are explicit that their fields may be non-Markovian. Conditional random fields (Lafferty et al. 2001) take the construction over to \(p(y \mid x)\) and became, for a decade, the default of structured prediction. None of that is controversial.

The duality itself has a real regularity condition, not just a name: the program \(\max_p H(p)\) subject to \(\mathbb{E}_p[f] = \mu\) is dual to maximum likelihood in the exponential family exactly when \(\mu\) sits in the interior of the marginal polytope; on the boundary the MLE fails to exist, and the maximum-entropy optimum is attained only in the closure of the exponential family (Wainwright and Jordan 2008, sec. 3.4).

What is not settled — and should not be written as if it were — is the claim that “PGM is classical maximum entropy.” Three qualifications matter.

  1. The PGM literature organizes itself around representation, inference, and learning — the triad we borrowed in Section 5.1 — not around Jaynes. Standard treatments (Pearl 1988; Koller and Friedman 2009) may discuss log-linear Markov networks, whose maximum-likelihood dual is a maximum-entropy problem, without taking that dual as the field’s founding slogan. The maxent identification is a precise reading of the exponential-family parameterization, not the community’s self-description.
  2. The tight theorem is undirected, finite, and strictly positive. Directed models are a different organizing principle: Equation 5.6 is not a Jaynes problem. A Bayes net can be moralized into an MRF on the graph obtained by marrying co-parents and dropping directions; the resulting undirected model is an I-map (every independence it asserts by missing edges does hold in \(p\)), but it need not be a perfect map — moralization can lose independencies that the DAG had (v-structures are the usual example, since marrying the parents removes exactly the edge whose absence encoded that independence). The rewriting \(E(x) = -\sum_i \log p(x_i \mid \mathrm{pa}_i)\) is an energy in the sense of Chapter 4, and in this case \(Z = 1\) already, so the network sits inside the energy-based tent as a normalized model. That does not make it a maximum-entropy model, and the precise reason is the dimensional cousin of the loss of independencies above: a Jaynes problem with linear constraints has a solution confined to a linear exponential family. Fully observed discrete undirected graphical models are exactly such linear exponential families; fully observed discrete directed (DAG) models are in general only a curved exponential family (Geiger et al. 2001), with equality precisely when the DAG has no immoralities (v-structures) — that is, when its Markov equivalence class contains a decomposable (chordal) undirected model. Away from finite discrete variables the identification loses its grip for a further, dimensional reason: the clique potentials now range over an infinite-dimensional function space, so the MRFs on a fixed graph no longer form a finite-dimensional exponential family. (A single Gibbs distribution is always trivially exponential-family — the claim has content only for the model class.) Gaussian MRFs remain a finite-dimensional exponential family; potentials given by mixtures do not.
  3. Even on the undirected side, maxent fixes the distribution given the constraints. Choosing the graph, or which clique features to include, is a feature-selection question with more than one answer — the greedy KL-gain feature induction of Della Pietra, Della Pietra, and Lafferty (Della Pietra et al. 1997), and the minimax entropy of Zhu, Wu, and Mumford (Zhu et al. 1997), the subject of Chapter 7 — and neither is part of Jaynes’ original programme.

So the accurate statement, and the one this chapter will use, is narrower than a slogan and stronger than a metaphor: a strictly positive exponential-family MRF on a finite graph is a classical maximum-entropy model with structured constraints; Bayesian networks are an explanatory sibling that can be rewritten as (already normalized) energies but should not be renamed maxent; the PGM field as a whole is larger than either identification, and still doing work that this book will not reproduce. A future revision should include full derivations of both the Hammersley–Clifford theorem and the moralization construction. For now, this chapter simply points to them as essential references.

5.3 A worked example: energy-based cooperative games

The variational machinery of the previous section is not only for graphs. The same mean-field relaxation that Wainwright and Jordan use to approximate a graphical model’s log-partition function applies verbatim to a Gibbs distribution over coalitions, and what it produces there turns out to be a familiar object.

As one concrete instance of the programme above, consider a valuation problem in machine learning: how much does a feature, data point, or player contribute to an outcome? The classical answer is the Shapley value from cooperative game theory, but it is one particular choice among many.

In Energy-Based Learning for Cooperative Games (Bian et al. 2022), the valuation problem is recast through an energy / maximum-entropy lens. A cooperative game with characteristic function \(v(S)\) over coalitions \(S \subseteq N\) is turned into a distribution over coalitions by a single Jaynes constraint: match a prescribed expected payoff and nothing else. The solution is the Gibbs distribution

\[ p(S) \propto \exp\big(v(S) / \tau\big), \]

with energy \(-v(S)\). Here \(\tau\) is a temperature in exactly the sense of Chapter 3: as \(\tau \to 0\) the mass concentrates on the highest-value coalitions, while as \(\tau \to \infty\) it flattens towards uniform. In the strict Jaynes reading \(\tau = 1/\lambda\) is not a free knob — it is pinned by whichever expected payoff the constraint matches — so sweeping \(\tau\) below is the same move as sweeping that matched level.

Player valuations are then read from a mean-field approximation to \(p\). The payoff term of that mean-field ELBO is exactly Owen’s multilinear extension of the game (Owen 1972, 1975). What the variational reading adds is the entropy term — which turns the multilinear extension from an interpolation device into an ELBO with a temperature — and the trajectory beyond one step: further mean-field iterations define a family of variational valuations whose fixed point — the minimizer of the mean-field KL divergence, i.e. the member with the best conceivable decoupling error — is the Variational Index. Shapley is therefore not a special case of the maximum-entropy distribution, but a one-step mean-field reading of it.

5.3.1 Why this is useful

  • Principled interpretation. Valuations become variational parameters of a mean-field approximation to a maximum-entropy distribution over coalitions, rather than isolated axiomatic scores.
  • A family, not a point. The temperature \(\tau\) and the number of mean-field steps trace a spectrum of valuations, with Shapley and Banzhaf as one-step readings rather than the only options.
  • Bridges to physics. The same Gibbs machinery is the one that carried the Ising energy into neural networks in the first place, by way of the Hopfield network (Hopfield 1982) and the Boltzmann machine (Ackley et al. 1985); see Chapter 3.

5.4 Discrete maximum-entropy learning: set functions under the optimal subset oracle

Everything in Section 5.3 presupposed the game. The characteristic function \(v(S)\) was given, the Gibbs distribution over coalitions was derived from it by one Jaynes constraint, and mean-field inference on that distribution was an interpretation device — a way to read valuations off a distribution nobody had to fit. Nothing was learned. This section drops that assumption. The set function is unknown, the only supervision is which subset turned out to be optimal, and the same Gibbs-plus-mean-field machinery becomes a training loop on the power set \(2^V\) — an exponentially large discrete space on which none of the Langevin machinery of Chapter 4 applies. This section most concretely embodies the concept of maximum-entropy learning as defined in Section 5.1: here, the energy function is not given a priori but is instead learned directly on a discrete set space, so the strand is a maximum-entropy learner in the sense of Section 5.1.4. The published line runs through EquiVSet (Ou et al. 2022) and INSET (Xie, Bian, et al. 2024), and has since been taken up by others (Xie, Wang, et al. 2024; Özcan et al. 2025); a further step of our own is still a preprint and is noted only at the end. We present the line as a paradigm of discrete maximum-entropy learning, and in Section 5.4.4 say what it adds to the programme and what it leaves open.

5.4.1 The optimal subset oracle

A set function \(F(S; V)\) assigns a utility to every subset \(S\) of a ground set \(V\): the products a customer would want among those displayed, the anomalous images in a batch, the compounds worth advancing from a screening library. The object of interest is the maximizer,

\[ S^\ast \;=\; \operatorname*{arg\,max}_{S \subseteq V} F(S; V) , \tag{5.7}\]

and the question is how to learn \(F_\theta\) from data. The classical setting is the function-value (FV) oracle: pairs \((S_i, F(S_i))\) on a fixed ground set, from which \(F_\theta\) is fit by regression. It is expensive — one utility label per subset, on a space of \(2^{|V|}\) subsets — and the learnability theory built on it carries strong inapproximability results even for submodular functions (Balcan and Harvey 2018). The optimal subset (OS) oracle is weaker and far more common: pairs \((V_i, S_i^\ast)\), a ground set together with the subset that was actually chosen, and no utility values at all. The two are not comparable in general. Max-cut has a trivial FV oracle and an NP-hard OS oracle; a recommender log has a natural OS oracle — what the customer selected from what was shown — and no FV oracle, because nobody knows the customer’s utility.

Learning under the OS oracle was posed by Ou et al. (2022) as maximum likelihood over a distribution on subsets whose mass grows with the utility:

\[ \max_\theta\; \mathbb{E}_{(V, S^\ast)}\big[\log p_\theta(S^\ast \mid V)\big], \qquad p_\theta(S \mid V) \;=\; \frac{\exp\big(F_\theta(S; V)\big)} {\sum_{S' \subseteq V} \exp\big(F_\theta(S'; V)\big)} . \tag{5.8}\]

This is a conditional energy-based model in the sense of Section 4.1 — input \(x = V\), answer \(y = S\), answer space \(\mathcal{Y} = 2^V\), energy \(E_\theta(S; V) = -F_\theta(S; V)\) — and the Gibbs form is not a convenience but the maximum-entropy choice. Among all distributions on \(2^V\) that match a prescribed expected utility \(\mathbb{E}_p[F(S)] = \mu\), the entropy maximizer is unique and is \(p(S) \propto \exp(\lambda F(S))\) (Ou et al. 2022, Thm. 1); the argument is Jaynes’ own (Jaynes 1957). It is the single-constraint problem of Chapter 3 and exactly the coalition distribution of Section 5.3 with \(v\) replaced by \(F_\theta\); the multiplier \(\lambda = 1/\tau\) is absorbed into the scale of \(F_\theta\), as \(\beta\) was absorbed into \(E\) in Chapter 4. The paper calls the property minimum prior: the model assumes nothing about the subset beyond what its utility says. The contrast is with the probabilistic greedy model (Tschiatschek et al. 2018), which builds \(p(S)\) by summing an order-dependent, autoregressive greedy-sampling distribution over all orderings of \(S\) — importing an inductive bias the data never asked for, and at factorial cost.

It is worth seeing what the likelihood asks for. In the normalization of Equation 4.4, with an explicit inverse temperature, the negative log-likelihood of one pair is \(-F_\theta(S^\ast; V) + \tfrac{1}{\beta}\log \sum_{S} e^{\beta F_\theta(S; V)}\). As \(\beta \to \infty\) the second term tends to \(\max_S F_\theta(S; V)\), and the loss to \(\max_S F_\theta(S; V) - F_\theta(S^\ast; V)\): the perceptron loss of Section 4.3 on the answer space \(2^V\), which vanishes exactly when \(S^\ast\) is a maximizer — Equation 5.7 read as a loss. Maximum likelihood under the OS oracle is therefore the finite-temperature relaxation of “make the observed subset the arg max.” It buys, at the price of a partition function, a smooth objective whose pull-up (Equation 4.5) is spread over every rival subset in proportion to the probability the model currently assigns it. In the taxonomy of Section 4.1 this is the decision question answered through the probability question, and the detour is deliberate.

The same objective can be read in the constrained form of Section 5.1.1. What the OS oracle tells us about the unknown set function is a collection of optimality constraints, \(F(S^\ast; V) \ge F(S; V)\) for all \(S \subseteq V\), i.e., one polyhedral cone per instance, and the set functions satisfying them are exactly those under which the observed subset is optimal. Inferring an objective from observed optimal solutions is the classical problem of inverse optimization (Burton and Toint 1992; Ahuja and Orlin 2001; Heuberger 2004), and the zero-temperature loss above is the structured perceptron of structured prediction (Collins 2002; Taskar et al. 2003; Tsochantaridis et al. 2005). Seen this way, the setting is not new in kind, and it is worth being explicit about its nearest relatives. Max-margin learning of submodular set functions from reference summaries (Lin and Bilmes 2012; Sipos et al. 2012) is the \(T \to 0\) version on a fixed function class; structured prediction energy networks (SPENs) place a deep energy on a structured output and train it through unrolled gradient-based inference (Belanger and McCallum 2016; Belanger et al. 2017). What EquiVSet adds is the combination: a permutation-invariant neural set function on a variable ground set, the maximum-entropy justification of the set mass function, amortized mean-field inference on the power set, and a copula that restores the correlations which mean field discards. The finite temperature is what turns the optimality constraints into a likelihood, and the likelihood into an objective that a gradient method can train.

Two further requirements shape the architecture. The set mass function must be permutation invariant, and it must accept a varying ground set, since every instance arrives with its own \(V\). Both are met by parameterizing \(F_\theta\) as a DeepSets network, \(F(S) = \rho\big(\sum_{s \in S} \kappa(s)\big)\), a form that is universal for permutation-invariant set functions under mild conditions (Zaheer et al. 2017). With minimum prior and scalability — training in polynomial rather than factorial time — these are the four desiderata of Ou et al. (2022), and scalability is where the difficulty lives.

5.4.2 Learning through mean-field inference: EquiVSet

The difficulty is the one this book keeps meeting. The pull-up term of Equation 5.8 is an expectation under \(p_\theta(\cdot \mid V)\) over \(2^{|V|}\) subsets; there is no continuous \(S\) on which to run Langevin dynamics, and running a discrete sampler (Grathwohl et al. 2021) or contrastive divergence inside the training loop is costly and, on large ground sets, unstable (Ou et al. 2022). EquiVSet takes a road absent from the table of Section 4.7: approximate the model by a tractable family, and train through the approximation.

The tractable family is mean field — the product of independent Bernoullis \(q(S; \psi) = \prod_{i \in S} \psi_i \prod_{i \notin S} (1 - \psi_i)\) with \(\psi \in [0,1]^{|V|}\), \(\psi_i\) the probability that element \(i\) belongs to the optimal subset. Minimizing \(\mathrm{KL}(q_\psi \,\Vert\, p_\theta)\) is maximizing the evidence lower bound,

\[ \mathrm{ELBO}(\psi) \;=\; f^{F_\theta}_{\mathrm{mt}}(\psi) + H(q_\psi), \qquad f^{F_\theta}_{\mathrm{mt}}(\psi) \;:=\; \sum_{S \subseteq V} F_\theta(S; V) \prod_{i \in S} \psi_i \prod_{i \notin S} (1 - \psi_i) , \tag{5.9}\]

and the payoff term is again the multilinear extension (Owen 1972; Calinescu et al. 2007) — the object that carried the valuations of Section 5.3, now built from a learned \(F_\theta\) rather than a given \(v\). Read through Chapter 3, Equation 5.9 is minus a variational free energy at unit temperature, \(\mathcal{F}(\psi) = \langle E_\theta \rangle_{q_\psi} - H(q_\psi)\), with the multilinear extension of the energy as the expected energy. The stationarity condition of the bound is the mean-field fixed point \(\psi_i = \sigma\big(\partial_i f_{\mathrm{mt}}(\psi)\big)\), and the partial derivative has a form that makes it estimable:

\[ \partial_i f^{F_\theta}_{\mathrm{mt}}(\psi) \;=\; \mathbb{E}_{S \sim q(\cdot;\, \psi_{-i})}\big[F_\theta(S \cup \{i\}; V) - F_\theta(S; V)\big] , \tag{5.10}\]

the expected marginal gain of \(i\) over a random subset of the other elements, drawn from \(q\) with \(\psi_i\) set to zero. That is the quantity read off as a player’s value in Section 5.3; here it is estimated by Monte Carlo and pushed through a sigmoid, and \(K\) such updates, run in parallel over coordinates, define a differentiable map \(\psi^\ast = \mathrm{MFVI}(\psi^{(0)}, V, K)\).

Learning then never touches \(\log Z\). The parameters are trained by the cross-entropy of the observed optimal subset under the marginals the inference algorithm produces,

\[ \mathcal{L}(\theta) \;=\; -\sum_{j \in S^\ast} \log \psi^\ast_j(\theta) \;-\; \sum_{j \in V \setminus S^\ast} \log\big(1 - \psi^\ast_j(\theta)\big) , \tag{5.11}\]

with gradients back-propagated through the \(K\) fixed-point steps. This is Domke’s marginal-based loss (Domke 2013) — the training rule behind differentiable mean field for dense random fields and CRF-as-RNN (Krähenbühl and Koltun 2013; Zheng et al. 2015) — carried over to a deep energy on a variable ground set. In the terminology of the broader literature it is end-to-end training through unrolled inference, also termed deep unfolding: the iterations of an inference algorithm are treated as the layers of a network, and the loss is back-propagated through them (Gregor and LeCun 2010; Stoyanov et al. 2011; Domke 2012; Hershey et al. 2014; Belanger et al. 2017). Two properties should be stated plainly. The loss is not a bound on the log-likelihood of Equation 5.8: what is fit is the output of an approximate inference algorithm, which is a virtue (inference error is accounted for at training time) and a limitation (the link to the maximum-entropy distribution runs only through the fixed point). And the mean-field family cannot represent interactions between elements — the decoupling error of Section 5.3 returns as a modelling limit.

EquiVSet addresses cost and decoupling together. A permutation-equivariant recognition network \(\psi^{(0)} = \mathrm{EquiNet}(V; \phi)\) amortizes inference by proposing the initial marginals; it is trained to maximize Equation 5.9 (through a Gumbel–softmax relaxation of the discrete samples), optionally with a Gaussian copula that correlates the Bernoullis. A single mean-field step from that initialization then carries the gradient to \(\theta\), and the two networks are trained cooperatively (Xie et al. 2018). At test time the same pipeline — proposal, one step, top-\(k\) rounding — returns a subset. A telling ablation: taking more mean-field steps from the copula initialization hurts, because the iteration converges to the plain mean-field fixed point and washes out the correlations the copula supplied.

On product recommendation (Amazon baby-registry categories), set anomaly detection (Double MNIST, CelebA), and compound selection from PDBBind and BindingDB, EquiVSet outperformed the probabilistic greedy model by large margins and, more tellingly, outperformed a DeepSets network trained directly on membership labels — the comparison that isolates the value of learning an explicit set function. The last application is the one that matters for Part III. A virtual-screening pipeline filters by bioactivity, diversity, and ADME in stages whose intermediate labels are costly or proprietary, but the final selected library is observed. That is an OS oracle and nothing else (Chapter 10).

5.4.3 Which statistics may the energy depend on? INSET

EquiVSet’s set function looked only at \(S\). But a subset’s utility depends on the ground set it was drawn from: an image is anomalous relative to its batch, a bundle is chosen from what was displayed. INSET (Xie, Bian, et al. 2024) asks what an energy \(F_\theta(S, V)\) is permitted to depend on, and derives the answer from symmetry. The conditional law the network must represent — that of the membership probabilities \(Y \in [0,1]^{|V|}\) given \((S, V)\) — should be invariant under permutations of \(S\) and under the nested permutations of \(V\) viewed as a set of disjoint subsets (a wreath-product group). The theorem, proved through the noise-outsourcing lemma of probabilistic symmetry (Bloem-Reddy and Teh 2020), is that \(P(Y \mid S, V)\) has this invariance if and only if \(Y \overset{\text{a.s.}}{=} f\big(\xi, M(S, V)\big)\) for independent noise \(\xi\) and a maximal invariant \(M\) — a statistic that is constant on the orbits of the group and separates them. Such an \(M\) is then an adequate statistic: conditioning on it loses nothing about \(Y\). The invariant sufficient representations of \(S\) and of \(V\) may be built separately and combined, and each is approximated by a DeepSets sum, which gives the architecture

\[ F_\theta(S, V) \;=\; \sigma\Big(\theta_1 \sum_{x \in S} \phi(x) \;+\; \theta_2 \sum_{x \in V} \phi(x)\Big) . \tag{5.12}\]

The move is the one Section 5.2 attributed to Jaynes, with invariance in place of moment constraints: the constraints fix which statistics the distribution may depend on — there, clique indicators; here, the maximal invariant of the symmetry group — and leave the function of those statistics free for the data to determine. In the vocabulary of Section 5.1.1, invariance is the one structural constraint that can be stated on either side of the duality, as linear equality constraints on the distribution or as the requirement that the features factor through the maximal invariant, and INSET takes the second route. The two-branch design improved on EquiVSet across every benchmark (on Double MNIST the mean Jaccard index rose from \(0.575\) to \(0.707\)), converged in fewer epochs, and an ablation shows the gain is not bought with parameter count.

5.4.4 What the strand adds to the maximum-entropy programme

Five points, and then what is open.

  1. The feature is learned, not the multipliers. Classical maximum entropy fixes the distribution given the features; Section 5.3 read valuations off that distribution for a given game. Here the confinement of Section 5.1.1 collapses to a single feature — the utility itself — and that feature is a neural network trained from data. In the vocabulary of Section 5.1.4 this is a maximum-entropy learner on a discrete domain, with the coalition temperature \(\tau\) of Section 5.3 reappearing as the learned scale of \(F_\theta\).
  2. Learning from observed optimal solutions. The OS oracle is neither function values nor samples from the model; it is arg-max points of the energy, i.e., the supervision of inverse optimization. Maximum likelihood is the finite-temperature relaxation of the perceptron condition “the observed subset is a maximizer,” and the pull-up over \(2^V\) is the price of smoothing it. The data constrain \(F\) only through its maximizers, so what is learned is a landscape with the right valleys, not a calibrated utility: with noiseless optimal subsets the likelihood alone would send the scale of \(F_\theta\) to infinity, as in separable logistic regression, and regularization and early stopping are what pin it.
  3. A fourth road around the partition function. Table 4.1 listed three ways to afford the pull-up: sample it, differentiate it away, cancel it against noise. EquiVSet’s road — relax the discrete distribution to a tractable family, unroll the inference, and train the marginals it outputs — is a fourth, with its own characteristic failure: the decoupling error of the family, and a loss that is not a likelihood bound. The bridge between \(2^V\) and \([0,1]^{|V|}\) is always the multilinear extension, which is why continuous DR-submodular maximization (Bian et al. 2019; Hassani et al. 2017) is the right theory for the guarantees. In Section 5.3 mean-field inference was an interpretation device; here it is the training loop.
  4. Constraints from symmetry. INSET shows that the statistics an energy may depend on can be derived from the invariances of the conditional distribution — sufficiency and adequacy in the classical sense, reached by the same route as Jaynes’ clique features in Section 5.2. What the data are left to learn is the function of those statistics.
  5. The free energy. The ELBO that drives these methods is \(-\mathcal{F}(\psi)\) at \(T = 1\) (Chapter 3), so variational inference on the learned energy is the minimization of \(U - TS\) that runs beneath the whole book; and inference in the trained model — iterate toward the fixed point, then round — is energy-based reasoning on a discrete landscape in the sense of Chapter 8.

What is open is at least as interesting. A discrete EBM trainer under OS supervision whose objective bounds the likelihood does not yet exist; EquiVSet says so in as many words, and the candidates are gradient-informed discrete samplers for the pull-up (Grathwohl et al. 2021) and contrastive objectives against structured negatives (Section 4.6). Beyond mean field, structured variational families — the copula is a patch — would let the multi-step trajectory of Section 5.3 be used rather than avoided; that more steps hurt EquiVSet is a symptom worth diagnosing. Priors on the set function — diminishing returns (Bilmes and Bai 2017), bounded submodularity ratio (Bian et al. 2017) — would let the guarantees of continuous DR-submodular maximization apply to the learned \(F_\theta\) rather than be assumed of it. And the setting generalizes: multisets and integer lattices already have provable mean-field inference (Sahin et al. 2020); sequences, permutations, and graphs are the natural next domains for the same recipe — a discrete energy learned from its own optimizers. That recipe is what we mean by discrete maximum-entropy learning, and compound selection is only its first scientific case (Chapter 10).

The most immediate bottleneck is the Monte Carlo estimate in Equation 5.10, repeated at every unrolled step. A preprint of ours (Shi et al. 2026) removes it by learning the continuous relaxation directly — a neural set-function extension (Karalias et al. 2022) climbed by gradient ascent in place of the sampled fixed point — with a constant-factor guarantee under weak DR-submodularity and a reading of the ELBO as a free energy whose temperature is learned rather than fixed at one. It is not yet published, and we record it here as the direction the strand is taking rather than as a result.

5.5 Maximum-entropy reinforcement learning: energies over trajectories

Reinforcement learning (RL) supplies the largest instance of the family outside our own work, and the one that most closely resembles Section 5.4. We do not survey the field here. The aim of this section is to place maximum-entropy RL on the three levels of Section 5.1, and to show that inverse RL is the optimal subset oracle with trajectories in place of subsets.

5.5.1 A Gibbs distribution over trajectories

Consider a Markov decision process with states \(s\), actions \(a\), transition kernel \(p(s' \mid s, a)\), and reward \(r(s, a)\), and let \(\tau = (s_1, a_1, \dots, s_H, a_H)\) denote a trajectory. The representation level is a Gibbs distribution over trajectories,

\[ \begin{aligned} p(\tau) \;&=\; \frac{1}{Z}\, h(\tau)\, \exp\Big( \frac{1}{\alpha} \sum_{t=1}^{H} r(s_t, a_t) \Big), \\[4pt] h(\tau) \;&=\; p(s_1) \prod_{t=1}^{H-1} p(s_{t+1} \mid s_t, a_t) \prod_{t=1}^{H} u(a_t) , \end{aligned} \tag{5.13}\]

with energy \(E(\tau) = -\sum_t r(s_t, a_t)\), temperature \(\alpha\), and a base measure that is not uniform: \(h\) is the law of the trajectories generated by the dynamics under a uniform action distribution \(u\), i.e., the passive dynamics of the system in the terminology of KL control (Todorov 2006, 2009; Kappen 2005). The base measure is what keeps the model from placing mass on physically impossible transitions. For deterministic dynamics \(h\) is uniform over the feasible trajectories, and Equation 5.13 is exactly the trajectory distribution of maximum-entropy inverse RL (Ziebart et al. 2008); for stochastic dynamics the same paper carries an explicit transition factor together with an approximation, and the principled repair is the maximum causal entropy discussed next (Ziebart et al. 2010).

5.5.2 Soft Bellman equations as free energies

The inference level restricts \(\mathcal{Q}\) to the distributions an agent can actually realize, namely those induced by a policy under the true dynamics, \(q_\pi(\tau) = p(s_1) \prod_t p(s_{t+1} \mid s_t, a_t)\, \pi(a_t \mid s_t)\). This restriction has a pleasant consequence. In \(\mathrm{KL}(q_\pi \,\Vert\, h)\) the transition factors cancel, and what remains is \(\mathbb{E}_{q_\pi}\big[\sum_t \log \pi(a_t \mid s_t) - \log u(a_t)\big]\), i.e., minus the causal entropy of the policy (Ziebart et al. 2010) up to a constant. Minimizing the free energy Equation 5.2 over \(q_\pi\) is therefore

\[ \max_{\pi}\; \mathbb{E}_{q_\pi}\Big[ \sum_{t} r(s_t, a_t) \;+\; \alpha\, H\big(\pi(\cdot \mid s_t)\big) \Big] , \tag{5.14}\]

which is the objective of maximum-entropy RL (Ziebart et al. 2010; Fox et al. 2016; Haarnoja et al. 2017). Its optimality conditions are the soft Bellman equations,

\[ \begin{aligned} Q(s, a) \;&=\; r(s, a) + \mathbb{E}_{s' \sim p(\cdot \mid s, a)}\big[V(s')\big], \\[4pt] V(s) \;&=\; \alpha \log \sum_{a} \exp\big(Q(s, a)/\alpha\big), \\[4pt] \pi^{\star}(a \mid s) \;&=\; \exp\big((Q(s, a) - V(s))/\alpha\big) , \end{aligned} \tag{5.15}\]

and the soft value \(V(s)\) is a log-partition function, i.e., a free energy at temperature \(\alpha\), one per state. As \(\alpha \to 0\) one recovers the hard Bellman equations and the greedy policy, exactly as \(T \to 0\) recovers energy minimization in Section 5.1.2. The reading of RL as inference in a graphical model, in which the policy-induced family plays the role of \(\mathcal{Q}\), goes back to Todorov, Toussaint, and Kappen (Todorov 2009; Toussaint 2009; Kappen et al. 2012) and is reviewed by Levine (2018); the theory of entropy-regularized Markov decision processes states the same facts in the language of convex regularization (Neu et al. 2017; Geist et al. 2019). When the reward is given, as in soft Q-learning and the soft actor–critic (Haarnoja et al. 2017, 2018), this is the whole story: a maximum-entropy model with variational inference and no learner, i.e., the same class as the cooperative games of Section 5.3, with \(\alpha\) a genuine dial. The KL-regularized policy optimization of Equation 6.1 is the same construction on a single decision, with a reference policy as the base measure and the KL coefficient as the temperature; imposing the KL as a constraint instead, as trust-region methods do (Schulman et al. 2015), is the constrained form of the same problem. Chapter 9 develops this reading for the post-training of pretrained models.

5.5.3 Inverse reinforcement learning: the optimal subset oracle on trajectories

The learning level becomes active when the reward is unknown and one observes expert trajectories \(\tau^\ast\) instead, which is the problem of inverse RL (Ng and Russell 2000). Maximum-entropy inverse RL fits a parametric reward \(r_\theta\) by maximum likelihood under Equation 5.13. For a linear reward \(r_\theta(s, a) = \theta^{\top} \phi(s, a)\), the likelihood equations Equation 5.5 read

\[ \mathbb{E}_{\text{expert}}\Big[\sum_t \phi(s_t, a_t)\Big] \;=\; \mathbb{E}_{p_\theta}\Big[\sum_t \phi(s_t, a_t)\Big] , \tag{5.16}\]

i.e., the learned reward makes the model reproduce the expert’s expected feature counts. This is the feature-expectation matching that apprenticeship learning had imposed directly (Abbeel and Ng 2004), and the model expectation is computed by the soft Bellman recursion of Equation 5.15, i.e., the inference of the second level runs inside the training loop. At zero temperature the same objective becomes a max-margin structured prediction problem over policies, termed maximum margin planning (Ratliff et al. 2006).

The parallel with Section 5.4 is now line by line, and Table 5.2 records it. In both cases the supervision consists of observed optimal solutions of an unknown objective: a chosen subset in one case, a demonstrated trajectory in the other. In both cases the finite temperature turns the optimality constraints into a likelihood, the zero-temperature limit is a perceptron or max-margin loss, the inner problem is a free-energy minimization over a tractable family (mean field on the multilinear extension; soft value iteration over policies), and the learning signal is the difference between an expert statistic and a model statistic. The difference lies in the base measure and in the family: the power set has no dynamics and \(h\) is uniform, whereas trajectories are constrained by the transition kernel, which is why the causal entropy replaces the Bernoulli entropies of Equation 5.9. We regard this parallel as the strongest external evidence that “learning an energy from its own optimizers” is a definition and not the description of one paper.

Table 5.2: The optimal subset oracle and maximum-entropy inverse RL, read through the same three levels.
Optimal subset oracle (Section 5.4) Maximum-entropy inverse RL
Observed optimal solution subset \(S^\ast \subseteq V\) trajectory \(\tau^\ast\)
Energy to be learned \(-F_\theta(S; V)\) \(-\sum_t r_\theta(s_t, a_t)\)
Base measure \(h\) uniform on \(2^V\) passive dynamics
Constrained reading optimality constraints (inverse optimization) feature-expectation matching (Abbeel and Ng 2004)
Zero-temperature limit structured perceptron; max-margin submodular learning (Lin and Bilmes 2012; Sipos et al. 2012) maximum margin planning (Ratliff et al. 2006)
Inner problem mean field on the multilinear extension soft value iteration
Entropy that does the work Bernoulli entropies of \(q_\psi\) causal entropy of \(\pi\)
Learning signal marginal-based loss through unrolled steps expert minus model feature counts

5.6 What the family adds, and where it stops

Having placed the strands, we close the chapter with three general facts that the definition of Section 5.1 makes available, and with a statement of what the definition excludes.

5.6.1 Maximum likelihood as a saddle-point problem

For the Gibbs model \(p_\theta = h\, e^{-E_\theta / T} / Z(\theta)\), the variational representation \(-T \log Z(\theta) = \min_q \mathcal{F}_T(q; E_\theta)\) of Equation 5.2 turns the negative log-likelihood into

\[ \begin{aligned} T \cdot \mathrm{NLL}(\theta) \;&=\; \mathbb{E}_{\hat p}[E_\theta] + T \log Z(\theta) \\[4pt] \;&=\; \max_{q}\Big\{\, \mathbb{E}_{\hat p}[E_\theta] - \mathbb{E}_{q}[E_\theta] - T\, \mathrm{KL}(q \,\Vert\, h) \Big\} + \text{const}, \end{aligned} \tag{5.17}\]

so maximum likelihood is \(\min_\theta \max_q\): a saddle-point, or primal–dual, problem in which the inner player is the inference of Equation 5.3 and the outer player shapes the energy (Kim and Bengio 2016; Dai et al. 2019). This is the form in which the pull-up of Equation 4.5 appears as a variational player, and it is also the right place to locate the estimators of Table 4.1. Maximum likelihood with MCMC samples from the inner maximizer; contrastive divergence truncates the chain that would reach it; the fourth road of Section 5.4 solves the inner problem over a tractable family; score matching and noise-contrastive estimation do something different in kind — they replace the Kullback–Leibler divergence behind Equation 5.17 by another divergence — and we return to them in Section 5.6.3. We call Equation 5.17 the saddle-point form and we do not call it minimax, since that word is reserved for the different nesting of Chapter 7.

5.6.2 Maximum entropy inside, minimum entropy outside: the bridge to minimax entropy

Let the energy be linear in its last layer, \(E_\theta(x) = -\, w^{\top} \phi_{\theta'}(x)\), as is the case for every network whose output is a linear read-out of its penultimate features, e.g., the last layer of \(\rho\) in a DeepSets set function. For fixed \(\theta'\), the maximum-likelihood \(w\) solves the Jaynes problem Equation 5.1 with \(\mathsf{T} = \phi_{\theta'}\) and \(\boldsymbol{\mu}\) the empirical moments, and the likelihood equations in \(w\) state that \(\mathbb{E}_{\hat p}[\phi_{\theta'}] = \mathbb{E}_{p_\theta}[\phi_{\theta'}]\). At such a point, and for uniform \(h\),

\[ \begin{aligned} \mathbb{E}_{\hat p}\big[-\log p_\theta\big] \;&=\; -\, w^{\top} \mathbb{E}_{\hat p}[\phi_{\theta'}] + \log Z \\[4pt] \;&=\; -\, w^{\top} \mathbb{E}_{p_\theta}[\phi_{\theta'}] + \log Z \;=\; H(p_\theta) , \end{aligned} \tag{5.18}\]

i.e., the cross-entropy of the data under the model equals the entropy of the model itself. Consequently, minimizing the negative log-likelihood over the feature parameters \(\theta'\) is minimizing the entropy of the maximum-entropy model built on the features \(\phi_{\theta'}\):

\[ \min_{\theta'}\; \mathrm{NLL}\big(\theta', w^{\star}(\theta')\big) \;=\; \min_{\theta'}\; H\big(p_{\theta',\, w^{\star}(\theta')}\big) . \]

This is the minimax entropy principle of Chapter 7, with a continuous family of features and with gradient descent in place of greedy selection. The incremental version is classical: in feature induction for random fields, the gain of adding a feature is the reduction of the model’s entropy, which equals the reduction of the KL divergence to the data (Della Pietra et al. 1997), and in the FRAME model of texture the filters are selected by the largest entropy drop (Zhu et al. 1998). Replacing “select a filter from a bank” by “take a gradient step on the filter parameters” is what a deep energy model does (Ngiam et al. 2011). The vision lineage of energy-based models describes itself in exactly these terms: the generative ConvNet is an exponential tilting of a Gaussian reference distribution by a ConvNet, and its authors present it as a hierarchical FRAME model, i.e., a maximum-entropy model whose features are learned filters (Xie et al. 2016). In this precise sense, every energy-based model trained by maximum likelihood is a minimax-entropy learner. The hypotheses should be kept in mind — a linear last layer (or a family closed under rescaling), an exact fit of \(w\), and a uniform base measure — and Chapter 7 studies the explicit, budgeted, combinatorial version of the outer problem, which is where the open questions lie.

5.6.3 Where the family stops

The definition also says where the family stops, and which of its neighbours sit on which side of the line. We go through them in turn, starting with the estimators of Chapter 4, since the answer there is not the same for every estimator.

  • Contrastive divergence (Hinton 2002), its persistent variant (Tieleman 2008), and short-run MCMC (Nijkamp et al. 2019) are maximum-entropy learners in the strict sense. They approximate the inner maximization of Equation 5.17 by sampling from, or truncating, a Markov chain whose target is the maximum-entropy distribution, so the entropy term is carried by that target. The truncated versions share the structure and the caveat of Section 5.4.2: what is fit is the output of a truncated inference procedure, the update is biased and in general not the gradient of any objective (Carreira-Perpiñán and Hinton 2005; Bengio and Delalleau 2009; Sutskever and Tieleman 2010), and the learned energy need not be a valid density (Nijkamp et al. 2020). In this respect the optimal subset oracle and CD-\(k\) stand or fall together, and we keep both inside the family.
  • Score matching (Hyvärinen 2005) and noise-contrastive estimation (Gutmann and Hyvärinen 2010) fit the same Gibbs model by minimizing a different divergence, and we call them maximum-entropy learners in the generalized sense. The construction behind the word is that of proper scoring rules. Every proper scoring rule \(S\) defines a generalized entropy \(H_S(p) = \mathbb{E}_p[S(x, p)]\) and a Bregman divergence \(d_S(p, q) = \mathbb{E}_p[S(x, q)] - H_S(p)\), and maximizing \(H_S\) under constraints is dual to minimizing the worst-case expected score, exactly as for the Shannon entropy and the log score (Grünwald and Dawid 2004; Dawid 2007). Score matching minimizes the Fisher divergence, which is \(d_S\) for the Hyvärinen score — the basic second-order local proper scoring rule, computable without the normalizing constant (Parry et al. 2012) — and the corresponding generalized entropy is \(-\tfrac{1}{2}\,\mathbb{E}_p\|\nabla_x \log p\|^2\), i.e., minus one half of the Fisher information. Score matching is therefore a minimum-Fisher-information learner, a principle with its own history in physics (Frieden 1990). Its bridges to the strict case are quantitative: it is the infinitesimal-step limit of Langevin contrastive divergence (Hyvärinen 2007), the derivative of the KL divergence under Gaussian smoothing (Lyu 2009), and, with likelihood weighting in diffusion models, an upper bound on the negative log-likelihood (Song et al. 2021). Noise-contrastive estimation is the maximum-entropy classifier of Section 5.1.4 with the energy as its single learned feature; it is consistent, and for normalized models it becomes asymptotically as efficient as maximum likelihood as the noise-to-data ratio grows (Gutmann and Hyvärinen 2012). The constant it estimates in place of \(\log Z\) plays the role of a free-energy difference between the model and the noise distribution, and the estimator is, up to the roles of data and noise samples, Bennett’s acceptance-ratio method of statistical physics, which is itself a logistic-regression maximum-likelihood estimator (Bennett 1976; Shirts et al. 2003). Both estimators, together with ratio matching, belong to one Bregman-divergence framework for unnormalized models (Gutmann and Hirayama 2011), and the Kullback–Leibler divergence of maximum likelihood is itself a Bregman divergence. Their derivations remain in Chapter 4.
  • The zero-temperature losses — perceptron, hinge, maximum margin planning — are the \(T \to 0\) limits of the family and lie on its boundary: the entropy term has been switched off.
  • Directed graphical models fitted by maximum likelihood or EM are learners at levels ii)–iii): the E-step is the I-projection of Equation 5.1, and the free-energy view of EM is that of Section 4.8. But their model class is not a linear exponential family (Section 5.2), so they are maximum-entropy learners without being maximum-entropy models.
  • Minimum-entropy learning (Chapter 6) uses the same inner Gibbs tilt (Equation 6.2) but reverses the outer criterion; it is excluded by
    1. by design, and the two chapters are the two directions of the dial of Chapter 3.
  • Entropy bonuses added to an arbitrary objective as a heuristic, without a Gibbs model behind them, are in the penumbra: they become maximum-entropy learning exactly when the objective can be written as Equation 5.2.

Two remarks connect the definition to finite samples and to decision theory. When the moments \(\boldsymbol{\mu}\) are estimated from data, relaxing the constraints of Equation 5.1 to a box \(|\mathbb{E}_q[\mathsf{T}] - \hat{\boldsymbol{\mu}}| \le \boldsymbol{\beta}\) is dual to \(\ell_1\)-regularized maximum likelihood, so constraint slack and regularization strength are one quantity (Dudı́k et al. 2007; Altun and Smola 2006). And the maximum-entropy distribution is the minimax strategy of a zero-sum game against nature under logarithmic loss (Topsøe 1979; Grünwald and Dawid 2004), which gives the principle a decision-theoretic rationale that is independent of Jaynes’ informational one.

5.7 Takeaway

Maximizing entropy reframes choosing a distribution over coalitions as the process of specifying a constraint; mean-field inference on this distribution transforms the question from “which valuation should I adopt?” to “how far along the mean-field path should I iterate?”—placing Shapley, Banzhaf, and related values on a continuous spectrum rather than as disconnected axioms. This echoes the main probabilistic graphical models insight from earlier in the chapter: a strictly positive MRF corresponds to a maximum-entropy model with structured constraints, and it is the mean-field relaxation that unifies different valuation principles as points along a single trajectory.

If we no longer assume the game is given, the same framework becomes a learning algorithm: we model a Gibbs distribution over subsets, where the energy is a neural set function, and learn this energy directly from observations of optimal subsets—by differentiating through mean-field inference on the multilinear extension. This is maximum-entropy learning as defined in Section 5.1, but now on a discrete space with an energy function discovered (not specified) from data. Here, the ELBO becomes the free energy to optimize, and the resulting energy landscape is itself shaped by the training data—a direct example of the chapter’s central idea.

Read through the three levels of Section 5.1, the chapter has one shape. Every strand shares the representation and inference levels—a Gibbs model and a free-energy minimization—and the strands differ in whether the learning level is active and in what supervises it. The cooperative games and maximum-entropy RL with a given reward stop at inference; the optimal subset oracle and inverse RL learn the energy from observed optimal solutions, and the two are parallel line by line (Table 5.2). Finally, by the identity Equation 5.18, maximum likelihood over the features of any such model is already a minimax-entropy problem, which is related to Chapter 7.