MAXIMUM ENTROPY FLOW NETWORKS
Maximum entropy modeling is a flexible and popular framework for formulating statistical models given partial knowledge. In this paper, rather than the traditional method of optimizing over the continuous density directly, we learn a smooth and invertible transformation that maps a simple distribution to the desired maximum entropy distribution. Doing so is nontrivial in that the objective being maximized (entropy) is a function of the density itself. By exploiting recent developments in normalizing flow networks, we cast the maximum entropy problem into a finite-dimensional constrained optimization, and solve the problem by combining stochastic optimization with the augmented Lagrangian method. Simulation results demonstrate the effectiveness of our method, and applications to finance and computer vision show the flexibility and accuracy of using maximum entropy flow networks.
1 INTRODUCTION
The maximum entropy (ME) principle (Jaynes, 1957) states that subject to some given prior knowledge, typically some given list of moment constraints, the distribution that makes minimal additional assumptions – and is therefore appropriate for a range of applications from hypothesis testing to price forecasting to texture synthesis – is that which has the largest entropy of any distribution obeying those constraints. First introduced in statistical mechanics by Jaynes (1957), and considered both celebrated and controversial, ME has been extensively applied in areas including natural language processing (Berger et al., 1996), ecology (Phillips et al., 2006), finance (Buchen & Kelly, 1996), computer vision (Zhu et al., 1998), and many more.
Continuous ME modeling problems typically include certain expectation constraints, and are usually solved by introducing Lagrange multipliers, which under typical assumptions yields an exponential family distribution (also called Gibbs distribution) with natural parameters such that the expectation constraints are obeyed. Unfortunately, fitting ME distributions in even modest dimensions poses significant challenges. First, optimizing the Lagrangian for a Gibbs distribution requires evaluating the normalizing constant, which is in general computationally very costly and error prone. Secondly, in all but the rarest cases, there is no way to draw samples independently and identically from this Gibbs distribution, even if one could derive it. Third, unlike in the discrete case where a number of recent and exciting works have addressed the problem of estimating entropy from discrete-valued data (Jiao et al., 2015; Valiant & Valiant, 2013), estimating differential entropy from data samples remains inefficient and typically biased. These shortcomings are critical and costly, given the common use of ME distributions for generating reference data samples for a null distribution of a test statistic. There is thus ample need for a method that can both solve the ME problem and produce a solution that is easy and fast to sample.
In this paper we develop maximum entropy flow networks (MEFN), a stochastic-optimization-based framework and algorithm for fitting continuous maximum entropy models. Two key steps are required. First, conceptually, we replace the idea of maximizing entropy over a density directly with maximizing, over the parameter space of an indexed function family, the entropy of the density induced by mapping a simple distribution (a Gaussian) through that optimized function. Modern
∗These authors contributed equally.
neural networks, particularly in variational inference (Kingma & Welling, 2013; Rezende & Mohamed, 2015), have successfully employed this same idea to generate complex distributions, and we look to similar technologies. Secondly, unlike most other objectives in this network literature, the entropy objective itself requires evaluation of the target density directly, which is unavailable in most traditional architectures. We overcome this potential issue by learning a smooth, invertible transformation that maps a simple distribution to an (approximate) ME distribution. Recent developments in normalizing flows (Rezende & Mohamed, 2015; Dinh et al., 2016) allow us to avoid biased and computationally inefficient estimators of differential entropy (such as the nearest-neighbor class of estimators like that of Kozachenko-Leonenko; see Berrett et al. (2016)). Our approach avoids calculation of normalizing constants by learning a map with an easy-to-compute Jacobian, yielding tractable probability density computation. The resulting transformation also allows us to reliably generate iid samples from the learned ME distribution. We demonstrate MEFN in detail in examples where we can access ground truth, and then we demonstrate further the ability of MEFN networks in equity option prices fitting and texture synthesis.
Primary contributions of this work include: (i) addressing the substantial need for methods to sample ME distributions; (ii) introducing ME problems, and the value of including entropy in a range of generative modeling problems, to the deep learning community; (iii) the novel use of constrained optimization for a deep learning application; and (iv) the application of MEFN to option pricing and texture synthesis, where in the latter we show significant increase in the diversity of synthesized textures (over current state of the art) by using MEFN.
2 BACKGROUND
2.1 MAXIMUM ENTROPY MODELING AND GIBBS DISTRIBUTION
We consider a continuous random variable Z ∈ Z ⊆ Rd with density p, where p has differential entropy H(p) = − ∫ p(z) log p(z)dz and support supp(p). The goal of ME modeling is to find, and then be able to easily sample from, the maximum entropy distribution given a set of moment and support constraints, namely the solution to:
p∗ = maximize H(p) (1) subject to EZ∼p[T (Z)] = 0
supp(p) = Z,
where T (z) = (T1(z), ..., Tm(z)) : Z → Rm is the vector of known (assumed sufficient) statistics, andZ is the given support of the distribution. Under standard regularity conditions, the optimization problem can be solved by Lagrange multipliers, yielding an exponential family p∗ of the form:
p∗(z) ∝ eη >T (z) 1(z ∈ Z) (2)
where η ∈ Rm is the choice of natural parameters of p∗ such that Ep∗ [T (Z)] = 0. Despite this simple form, these distributions are only in rare cases tractable from the standpoint of calculating η, calculating the normalizing constant of p∗, and sampling from the resulting distribution. There is extensive literature on finding η numerically (Darroch & Ratcliff, 1972; Salakhutdinov et al., 2002; Della Pietra et al., 1997; Dudik et al., 2004; Malouf, 2002; Collins et al., 2002), but doing so requires computing normalizing constants, which poses a challenge even for problems with modest dimensions. Also, even if η is correctly found, it is still not trivial to sample from p∗. Problemspecific sampling methods (such as importance sampling, MCMC, etc.) have to be designed and used, which is in general challenging (burn-in, mixing time, etc.) and computationally burdensome.
2.2 NORMALIZING FLOWS
Following Rezende & Mohamed (2015), we define a normalizing flow as the transformation of a probability density through a sequence of invertible mappings. Normalizing flows provide an elegant way of generating a complicated distribution while maintaining tractable density evaluation. Starting with a simple distribution Z0 ∈ Rd ∼ p0 (usually taken to be a standard multivariate
Gaussian), and by applying k invertible and smooth functions fi : Rd → Rd(i = 1, ..., k), the resulting variable Zk = fk ◦ fk−1 ◦ · · · ◦ f1(Z0) has density:
pk(zk) = p0(f −1 1 ◦ f −1 2 ◦ · · · ◦ f −1 k (zk)) k∏ i=1 |det(Ji(zi−1))|−1, (3)
where Ji is the Jacobian of fi. If the determinant of Ji can be easily computed, pk can be computed efficiently.
Rezende & Mohamed (2015) proposed two specific families of transformations for variational inference, namely planar flows and radial flows, respectively:
fi(z) = z + uih(w T i z + bi) and fi(z) = z + βih(αi, ri)(z− z′i), (4)
where bi ∈ R, ui,wi ∈ Rd and h is an activation function in the planar case, and where βi ∈ R, αi > 0, z′i ∈ Rd , h(α, r) = 1/(α + r) and ri = ||z − z′i|| in the radial. Recently Dinh et al. (2016) proposed a normalizing flow with convolutional, multiscale structure that is suitable for image modeling and has shown promise in density estimation for natural images.
3 MAXIMUM ENTROPY FLOW NETWORK (MEFN) ALGORITHM
3.1 FORMULATION
Instead of solving Equation 2, we propose solving Equation 1 directly by optimizing a transformation that maps a random variable Z0, with simple distribution p0, to the ME distribution. Given a parametric family of normalizing flows F = {fφ, φ ∈ Rq}, we denote pφ(z) = p0(f −1 φ (z))|det(Jφ(z))|−1 as the distribution of the variable fφ(Z0), where Jφ is the Jacobian of fφ. We then rewrite the ME problem as:
φ∗ = maximize H(pφ) (5) subject to EZ0∼p0 [T (fφ(Z0))] = 0
supp(pφ) = Z.
When p0 is continuous and F is suitably general, the program in Equation 5 recovers the ME distribution pφ exactly. With a flexible transformation family, the ME distribution can be well approximated. In experiments we found that taking p0 to be a standard multivariate normal distribution achieves good empirical performance. Taking p0 to be a bounded distribution (e.g. uniform distribution) is problematic for learning transformations near the boundary, and heavy tailed distributions (e.g. Cauchy distribution) caused similar trouble due to large numbers of outliers.
3.2 ALGORITHM
We solved Equation 5 using the augmented Lagrangian method. Denote R(φ) = E(T (fφ(Z0))), the augmented Lagrangian method uses the following objective:
L(φ;λ, c) = −H(pφ) + λ>R(φ) + c
2 ||R(φ)||2 (6)
where λ ∈ Rm is the Lagrange multiplier and c > 0 is the penalty coefficient. We minimize Equation 6 for a non-decreasing sequence of c and well-chosen λ. As a technical note, the augmented Lagrangian method is guaranteed to converge under some regularity conditions (Bertsekas, 2014). As is usual in neural networks, a proof of these conditions is challenging and not yet available, though intuitive arguments (see Appendix §A) suggest that most of them should hold. Due to the non rigorous nature of these arguments, we rely on the empirical results of the algorithm to claim that it is indeed solving the optimization problem.
For a fixed (λ, c) pair, we optimize L with stochastic gradient descent. Owing to our choice of network and the resulting ability to efficiently calculate the density pφ(z(i)) for any sample point
Algorithm 1 Training the MEFN 1: initialize φ = φ0, set c0 > 0 and λ0. 2: for Augmented Lagrangian iteration k = 1, ..., kmax do 3: for SGD iteration i = 1, ..., imax do 4: Sample z(1), ..., z(n) ∼ p0, get transformed variables z(i)φ = fφ(z(i)), i = 1, ..., n 5: Update φ by descending its stochastic gradient (using e.g. ADADELTA (Zeiler, 2012)):
∇φL(φ;λk, ck) ≈ 1
n n∑ i=1 ∇φ log pφ(z(i)φ ) + 1 n n∑ i=1 ∇φT (z(i)φ )λk + ck 2 n n 2∑ i=1 ∇φT (z(i)φ ) · 2 n n∑ i=n
2 +1
T (z (i) φ )
6: end for 7: Sample z(1), ..., z(ñ) ∼ p0, get transformed variables z(i)φ = fφ(z(i)), i = 1, ..., ñ 8: Update λk+1 = λk + ck 1ñ ∑ñ i=1 T (z (i) φ )
9: Update ck+1 ≥ ck (see text for detail) 10: end for
z(i) (which are easy-to-sample iid draws from the multivariate normal p0), we compute the unbiased estimator of H(pφ) with:
H(pφ) ≈ − 1
n n∑ i=1 log pφ(fφ(z (i))) (7)
R(φ) can also be estimated without bias by taking a sample average of z(i) draws. The resulting optimization procedure is detailed in Algorithm 1, of which step 9 requires some detail: denoting φk as the resulting φ after imax SGD iterations at the augmented Lagrangian iteration k, the usual update rule for c (Bertsekas, 2014) is:
ck+1 = { βck, if ||R(φk+1)|| > γ||R(φk)|| ck, otherwise
(8)
where γ ∈ (0, 1) and β > 1. Monte Carlo estimation of R(φ) sometimes caused c to be updated too fast, causing numerical issues. Accordingly, we changed the hard update rule for c to a probabilistic update rule: a hypothesis test is carried out with null hypothesis H0 : E[||R(φk+1)||] = E[γ||R(φk)||] and alternative hypothesis H1 : E[||R(φk+1)||] > E[γ||R(φk)||]. The p-value p is computed, and ck+1 is updated to βck with probability 1 − p. We used a two-sample t-test to calculate the p-value. What results is a robust and novel algorithm for estimating maximum entropy distributions, while preserving the critical properties of being both easy to calculate densities of particular points, and being trivially able to produce truly iid samples.
4 EXPERIMENTS
We first construct an ME problem with a known solution (§4.1), and we analyze the MEFN algorithm with respect to the ground truth and to an approximate Gibbs solution. These examples test the validity of our algorithm and illustrate its performance. §B and §4.3 then applies the MEFN to a financial data application (predicting equity option values) and texture synthesis, respectively, to illustrate the flexibility and practicality of our algorithm.
For §4.1 and §B, We use 10 layers of planar flow with a final transformation g (specified below) that transforms samples to the specified support, and use with ADADELTA (Zeiler, 2012). For §4.3 we use real NVP structure and use ADAM (Kingma & Ba, 2014) with learning rate = 0.001. For all our experiments, we use imax = 3000, β = 4, γ = 0.25. For §4.1 and §B we use n = 300, ñ = 1000, kmax = 10; For §4.3 we use n = ñ = 2, kmax = 8.
4.1 A MAXIMUM ENTROPY PROBLEM WITH KNOWN SOLUTION
Following the setup of the typical ME problem, suppose we are given a specified support S = {z = (z1, . . . , zd−1) : zi ≥ 0 and ∑d−1 k=1 zk ≤ 1} and a set of constraints E[logZk] = κk(k = 1, ..., d),
where Zd = 1− ∑d−1 k=1 Zk. We then write the maximum entropy program:
p∗ = maximize H(p) (9) subject to EZ∼p[logZk − κk] = 0 ∀k = 1, ..., d
supp(p) = S.
This is a general ME problem that can be solved via the MEFN. Of course, we have particularly chosen this example because, though it may not obviously appear so, the solution has a standard and tractable form, namely the Dirichlet. This choice allows us to consider a complicated optimization program that happens to have known global optimum, providing a solid test bed for the MEFN (and for the Gibbs approach against which we will compare). Specifically, given a parameter α ∈ Rd, the Dirichlet has density:
p(z1, . . . , zd−1) = 1
B(α) d∏ k=1 zαk−1k 1 ((z1, . . . , zd−1) ∈ S) (10)
where B(α) is the multivariate Beta function, and zd = 1 − ∑d−1 k=1 zk. Note that this Dirichlet is a distribution on S and not on the (d − 1)-dimensional simplex Sd−1 = {(z1, . . . , zd) : zk ≥ 0 and ∑d k=1 zk = 1} (an often ignored and seemingly unimportant technicality that needs to be correct here to ensure the proper transformation of measure). Connecting this familiar distribution to the ME problem above, we simply have to choose α such that κk = ψ(αk)−ψ(α0) for k = 1, ..., d, where α0 = ∑d k=1 αk and ψ is the digamma function. We then can pose the above ME problem to the MEFN and compare performance against ground truth. Before doing so, we must stipulate the transformation g that maps the Euclidean space of the multivariate normal p0 to the desired support S. Any sensible choice will work well (another point of flexibility for the MEFN); we use the standard transformation:
g(z1, ..., zd−1) = ( ez1∑d−1
k=1 e zk + 1
, ..., ezd−1∑d−1
k=1 e zk + 1
)> (11)
Note that the MEFN outputs vectors in Rd−1, and not Rd, because the Dirichlet is specified as a distribution on S (and not on the simplex Sd−1). Accordingly, the Jacobian is a square matrix and its determinant can be computed efficiently using the matrix determinant lemma. Here, p0 is set to the (d− 1)-dimensional standard normal.
We proceed as follows: We choose α and compute the constraints κ1, ..., κd. We run MEFN pretending we do not know α or the Dirichlet form. We then take a random sample from the fitted distribution and a random sample from the Dirichlet with parameter α, and compare the two samples using the maximum mean discrepancy (MMD) kernel two sample test (Gretton et al., 2012), which assesses the fit quality. We take the sample size to be 300 for the two sample kernel test. Figure 1 shows an example of the transformation from normal (left panel) to MEFN (middle panel), and comparing that to the ground truth Dirichlet (right panel). The MEFN and ground truth Dirichlet densities shown in purple match closely, and the samples drawn (red) indeed appear to be iid draws from the same (maximum entropy) distribution in both cases.
Additionally, the middle panel of Figure 1 shows an important cautionary tale that foreshadows our texture synthesis results (§4.3). One might suppose that satisfying the moment matching constraints is adequate to produce a distribution which, if not technically the ME distribution, is still interestingly variable. The middle panel shows the failure of this intuition: in dark green, we show a network trained to simply match the moments specified above, and the resulting distribution quite poorly expresses the variability available to a distribution with these constraints, leading to samples that are needlessly similar. Given the substantial interest in using networks to learn implicit generative models (e.g., Mohamed & Lakshminarayanan (2016)), this concern is particularly relevant and highlights the importance of considering entropy.
Figure 2 quantitatively analyzes these results. In the left panel, for a specific choice of α = (1, 2, 3), we show our unbiased entropy estimate of the MEFN distribution pφ as a function of the number of SGD iterations (red), along with the ground truth maximum entropy H(p∗) (green line). Note
that the MEFN stabilizes at the correct value (as a stochastic estimator, variance around that value is expected). In the middle panel, we show the distribution of MMD values for the kernel two sample test, as well as the observed statistic for the MEFN (red) and for a randomly chosen Dirichlet distribution (gray; chosen to be close to the true optimum, making a conservative comparison). The MMD test does not reject MEFN as being different from the true ME distribution p∗, but it does reject a Dirichlet whose KL to the true p∗ is small (see legend). In the right panel, for many different Dirichlets in a small grid around a single true p∗, the kernel two sample test statistic is computed, the MMD p-value is calculated, as is the KL to the true distribution. We plot a scatter of these points in grey, and we plot the particular MEFN solution as a red star. We see that for other Dirichlets with similar KL to the true distribution as the MEFN distribution, the p-values seem uniform, meaning that the KL to the true is indeed very small. Again this is conservative, as the grey points have access to the known Dirichlet form, whereas the MEFN considered the entire space (within its network capacity) of S supported distributions. Given this fact, the performance of MEFN is impressive.
4.2 RISK-NEUTRAL ASSET PRICING
We illustrate the flexibility and practicality of our algorithm extracting the risk-neutral asset price probability based on option prices, an active and interesting area for ME models. We find that MEFN and the classic Gibbs approach yield comparable performances. Owing to space limitations we have placed these results in Appendix §B.
4.3 MODELING IMAGES OF TEXTURES
Constructing generative models to generate random images with certain texture structure is an important task in computer vision. A line of texture synthesis research proceeds by first extracting a set
of features that characterizes the target texture and then generate images that match the features. The seminal work of Zhu et al. (1998) proposes constructing texture models under the ME framework, where features (or filters) of the given texture image are adaptively added in the model and a Gibbs distribution whose expected feature matches the target texture is learnt. One major difficulty with the method is that both model learning and image generation involve sampling from a complicated Gibbs distribution. More recent works exploit more complicated features (Portilla & Simoncelli, 2000; Gatys et al., 2015; Ulyanov et al., 2016). Ulyanov et al. (2016) propose the texture net, which uses a texture loss function by using the Gram matrices of the outputs of some convolutional layers of a pre-trained deep neural network for object recognition.
While the use of these complicated features does provide high-quality synthetic texture images, that work focuses exclusively on generating images that match these feature (moments). Importantly, this network focuses only on generating feature-matching images without using the ME framework to promote the diversity of the samples. Doing so can be deeply problematic: in Figure 1 (middle panel), we showed the lack of diversity resulting from only moment matching in that Dirichlet setting, and further we note that the extreme pathology would result in a point mass on the training image – a global optimum for this objective, but obviously a terrible generative model for synthesizing textures. Ideally, the MEFN will match the moments and promote sample diversity.
We applied MEFN to texture synthesis with an RGB representation of the 224 × 224 pixel images , z ∈ Z = [0, 1]d, where d = 224 × 224 × 3. We follow Ulyanov et al. (2016) (we adapted https://github.com/ProofByConstruction/texture-networks) to create a texture loss measure T (z) : [0, 1]d → R, and aim to sample a diverse set of images with small moment violation. For the transformation family F we use the real NVP network structure proposed in Dinh et al. (2016) (we adapted https://github.com/taesung89/real-nvp). We use 3 residual blocks with 32 feature maps for each coupling layer and downscale 3 times. For fair comparison, we use the same real NVP structure for both1, implemented in TensorFlow (Abadi et al., 2016).
As is shown in top row of figure 3, both methods generate visually pleasing images capturing the texture structure well. The bottom row of Figure 3 shows that texture cost (left panel) is similar for both methods, while MEFN generates figures with much larger entropy than the texture network formulation (middle panel), which is desirable (as previously discussed). The bottom right panel of figure 3 compares the marginal distribution of the RGB values sampled from the networks: we found that MEFN generates a more variable distribution of RGB values than the texture net. Further results are in Appendix §C.
1Ulyanov et al. (2016) use a quite different generative network structure, which is not invertible and is therefore infeasible for entropy evaluation, so we replace their generative network by the real NVP structure.
We compute in Table 1 the average pairwise Euclidean distance between randomly sampled images (dL2 = meani 6=j‖zi − zj‖22), and MEFN gives higher dL2 , quantifying diversity across images. We also consider an ANOVA-style analysis to measure the diversity of the images, where we think of the RGB values for the same pixel across multiple images as a group, and compute the within and between group variance. Specifically, denoting zki as the pixel value for a specific pixel k = 1, ..., d for an image i = 1, ...., n. We partition the total sum of square SST = ∑ i,k(z k i − z̄)2 as the within
group error SSW = ∑ i,k(z k i − z̄k)2 and between group error SSB = ∑ i,k n(z̄
k − z̄)2, where z̄ and z̄k are the mean pixel values across all data and for a specific pixel k. Ideally we want the samples to exhibit large variability across images (large SSW, within a group/pixel) and no structure in the mean image (small SSB, across groups/pixels). Indeed, the MEFN has a larger SSW, implying higher variability around the mean image, a smaller SSB, implying the stationarity of the generated samples, and a larger SST, implying larger total variability also. The MEFN produces images that are conclusively more variable without sacrificing the quality of the texture, implicating the broad utility of ME.
5 CONCLUSION
In this paper we propose a general framework for fitting ME models. This approach is novel and has three key features. First, by learning a transformation of a simple distribution rather than the distribution itself, we are able to avoid explicitly computing an intractable normalizing constant for the ME distribution. Second, by combining stochastic optimization with the augmented Lagrangian method, we can fit the model efficiently, allowing us to evaluate the ME density of any point simply and accurately. Third, critically, this construction allows us to trivially sample iid from a ME distribution, extending the utility and efficiency of the ME framework more generally. Also, accuracy equivalent to the classic Gibbs approach is in itself a contribution (owing to these other features). We illustrate the MEFN in both a simulated case with known ground truth and real data examples.
There are a few recent works encouraging sample diversity in the setting of texture modeling. Ulyanov et al. (2017) extended Ulyanov et al. (2016) by adding a penalty term using the Kozachenko-Leonenko estimator Kozachenko & Leonenko (1987) of entropy. Their generative network is an arbitrary deep neural network rather than a normalizing flow, which is more flexible but cannot give the probability density of each sample easily so as to compute an unbiased estimator of the entropy. Kozachenko-Leonenko is a biased estimator for entropy and requires a fairly large number of samples to get good performance in high-dimensional settings, hindering the scalability and accuracy of the method; indeed, our choice of normalizing flow networks was driven by these practical issues with Kozachenko-Leonenko. Lu et al. (2016) extended Zhu et al. (1998) by using a more flexible set of filters derived from a pre-trained deep neural networks, and using parallel MCMC chains to learn and sample from the Gibbs distribution. Running parallel MCMC chains results in diverse samples but can be computationally intensive for generating each new sample image. Our MEFN framework enables truly iid sampling with the ease of a feed forward network.
ACKNOWLEDGMENTS
We thank Evan Archer for normalizing flow code, and Xuexin Wei, Christian Andersson Naesseth and Scott Linderman for helpful discussion. This work was supported by a Sloan Fellowship and a McKnight Fellowship (JPC).
A AUGMENTED LAGRANGIAN CONDITIONS
We give a more thorough discussion of the regularity conditions which ensure that the Augmented Lagrangian method will work. The goal of this section is simply to state these conditions and give intuitive arguments about why some should hold in our case, not to attempt to prove that they indeed hold. The conditions (Bertsekas, 2014) are:
• There exists a strict local minimum φ∗ of the optimization problem of Equation 5: If the function class F is rich enough that it contains a true solver of the maximum entropy problem, then a global optimum exists. Although not rigorous, we would expect that even in the finite expressivity case that a global optimum remains, and indeed, recent theoretical work (Raghu et al., 2016; Poole et al., 2016) has gotten close to proving this.
• φ∗ is a regular point of the optimization problem, that is, the rows of∇φR(φ∗) are linearly independent: Again, this is not formal, but we should not expect this to cause any issues. This clearly depends on the specific form of T , but the condition basically says that there should not be redundant constraints at the optimum, so if T is reasonable this shouldn’t happen.
• H(pφ) and R(φ) are twice continuously differentiable on a neighborhood around φ∗: This holds by the smoothness of the normalizing flows.
• y>∇2φL(φ∗;λ∗, 0)y > 0 for every y 6= 0 such that ∇φR(φ∗)y = 0, where λ∗ is the true Lagrange multiplier: This condition is harder to justify. It would appear it is just asking that the Lagrangian (not the augmented Lagrangian) be strictly convex in feasible directions, but it is actually stronger than this and some simple functions might not satisfy the property. For example, if the function we are optimizing was x4 and we had no constraints, the Lagrangian’s Hessian would be 12x2, which is 0 at x∗ = 0 thus not satisfying the condition. Importantly, these conditions are sufficient but not necessary, so even if this doesn’t hold the augmented Lagrangian method might work (it certainly would for x4). Because of this and the nonrigorous justifications of the first two conditions, we left these conditions for the appendix and relied instead on the empirical performance to justify that we are indeed recovering the maximum entropy distribution.
If all of these conditions hold, the augmented Lagrangian (for large enough c and λ close enough to λ∗) has a unique optimum in a neighborhood around φ∗ that is close to φ∗ (as λ→ λ∗ it converges to φ∗) and its hessian at this optimum is positive-definite. Furthermore, λk → λ. This implies that gradient descent (with the usual caveats of being started close enough to the solution and with the right steps) will correctly recover φ∗ using the augmented Lagrangian method. This of course just guarantees convergence to a local optimum, but if there are no additional assumptions such as convexity, it can be very hard to ensure that it is indeed a global optimum. Some recent research has attempted to explain why optimization algorithms perform so well for neural networks (Choromanska et al., 2015; Kawaguchi, 2016), but we leave such attempts for our case for future research.
B RISK-NEUTRAL ASSET PRICE
We extract the risk-neutral asset price probability distribution based on option prices, an active and interesting area for ME models. We give a brief introduction of the problem and refer interested readers to see Buchen & Kelly (1996) for a more detailed explanation. Denoting St as the price of an asset at time t, the buyer of a European call option for the stock that expires at time te with strike price K will receive a payoff of cK = (Ste − K)+ = max(Ste − K, 0) at time te. Under the efficient market assumption, the risk-neutral probability distribution for the stock price at time te satisfies: cK = D(te)Eq[(Ste −K)+], (12) where D(te) is the risk-free discount factor and q is the risk-neutral measure. We also have that, under the risk-neutral measure, the current stock price S0 is the discounted expected value of Ste :
S0 = D(te)Eq(Ste). (13)
When givenm options that expire at time te with strikesK1, ...,Km and prices cK1 , ..., cKm , we get m expectation constraints on q(Ste) from Equation 12, together with Equation 13, we have m + 1 expectation constraints in total. With that partial knowledge we can approximate q(Ste), which is helpful for understanding the market expected volatility and identify mispricing in option markets, etc.
Inferring the risk-neutral density of asset price from a finite number of option prices is an important question in finance and has been studied extensively (Buchen & Kelly, 1996; Borwein et al., 2003; Bondarenko, 2003; Figlewski, 2008). One popular method proposed by Buchen & Kelly (1996) estimates the probability density as the maximum entropy distribution satisfying the expectation constraints and a positivity support constraint by fitting a Gibbs distribution, which results in a piece-wise linear log density:
p(z) ∝ exp { η0z +
m∑ i=1 ηi(z −Ki)+
} 1 (z ≥ 0) (14)
and optimize the distribution with numerical methods. Here we compare the performance of the MEFN algorithm with the method proposed in Buchen & Kelly (1996). To enforce the positivity constraint we choose g(z) = eaz+b, where a and b are additional parameters.
We collect the closing price of European call options on Nov. 1 2016 for the stock AAPL (Apple inc.) that expires on te = Jun. 16 2017. We usem = 4 of the options with highest trading volume as training data and the rest as testing data. On the left panel of figure 4, we show the fitted risk-neutral density of Ste by MEFN (red line) with that of the fitted Gibbs distribution result (blue line). We find that while the distributions share similar location and variability, the distribution inferred by MEFN is smoother and arguably more plausible. In the middle panel we show a Q-Q plot of the quantiles of the MEFN and Gibbs distributions. We can see that the quantile pairs match the identity closely, which should happen if both methods recovered the exact same distribution. This highlights the effectiveness of MEFN. There does exist a small mismatch in the tails: the distribution inferred by MEFN has slightly heavier tails. This mismatch is difficult to interpret: given that both the Gibbs and MEFN distributions are fit with option price data (and given that one can observe at most one value from the distribution, namely the stock price at expiration), it is fundamentally unclear which distribution is superior, in the sense of better capturing the true ME distribution’s tails. On the right panel we show the fitted option price for the two fitted distributions (for each strike price, we can recover the fitted option price by Equation 12). We noted that the fitted option price and strike price lines for both methods are very similar (they are mostly indiscernible on the right panel of figure 4). We also compare the fitted performance on the test data by computing the root mean square error for the fitted and test data. We observe that the predictive performances for both methods are comparable.
We note that for this specific application, there are practical concerns such as the microstructure noise in the data and inefficiency in the market, etc. Applying a pre-processing procedure and incorporating prior assumptions can be helpful for getting a more full-fledged method (see e.g. Figlewski (2008)). Here we mainly focus on illustrating the ability of the MEFN method to approximate the ME distribution for non-typical distributions. Future work for this application includes fitting a riskneutral distribution for multi-dimensional assets by incorporating dependence structure on assets.
C MODELING IMAGES OF TEXTURES
We tried our texture modeling approach with many different textures, and although MEFN samples don’t always exhibit more visual diversity than samples obtained from the texture network, they always have more entropy as in figure 3. Figure 5 shows two positive examples, i.e. textures in which samples from MEFN do exhibit higher visual diversity than those from the texture network, as well as a negative example, in which MEFN achieves less visual diversity than the texture network, regardless of the fact that MEFN samples do have larger entropy. We hypothesize that this curious behavior is due to the optimization achieving a local optimum in which the brick boundaries and dark brick locations are not diverse but the entropy within each brick is large. It should also be noted that among the experiments that we ran, this was the only negative example that we got, and that slightly modifying the hyperparameters caused the issue to disappear.
Much existing deep learning literature focuses on likelihood based models. However maximum entropy approaches are an equally valid modelling scenario, where information is given in terms of constraints rather than data. That there is limited work in flexible maximum entropy neural models is surprising, but  is due to the fact that optimizing a maximum entropy model requires (a) establishing the effect of the constraints on some distribution, and formulating the entropy of that complex distribution. There is no unbiased estimator of entropy from samples alone, and so an explicit model for the density is needed. This challenge limits approaches. The authors have identified that invertible neural models provide a powerful class of models for solving the maximum entropy network problem, and this paper goes on to establish this approach. The contributions of this paper are (a) recognising that, because normalising flows provide an explicit model for the density, they can be used to provide unbiased estimators for the entropy (b) that the resulting Lagrangian can be implemented as a relaxation of a augmented Lagrangian (c) establishing the practical issues in doing the augmented Lagrangian optimization. As far as the reviewer is aware this work is novel – this approach is natural and sensible, and is demonstrated on an number of models where clear evaluation can be done. Enough experiments have been done to establish this is an appropriate method, though not that it is entirely necessary – it would be good to have an example where the benefits of the flexible flow transformation were much clearer. Further discussion of the computational and scaling aspects would be valuable. I am guessing this approach is probably appropriate for model learning, but less appropriate for inferential settings where a known model is then conditioned on particular instance based constraints? Some discussion of appropriate use cases would be good. The issue of match to the theory via the regularity conditions has been brought up, but it is clear that this can be described well, and exceeds most of the theoretical discussions that occur regarding the numerical methods in other papers in this field.
Quality: Good sound paper providing a novel basis for flexible maximum entropy models.
Clarity: Good.
Originality: Refreshing.
Significance: Significant in model development terms. Whether it will be an oft-used method is not clear at this stage.
Minor issues
Please label all equations. Others might wish to refer to them even if you don’t.
Top of page 4: algorithm 1→ Algorithm 1.
The update for c to overcome stability appears slightly opaque and is mildly worrying.  I assume there are still residual stability issues? Can you comment on why this solves all the problems?
The issue of the support of p is glossed over a little. Is the support in 5 an additional condition on the support of p? If so, that seems hard to encode, and indeed does not turn up in (6). I guess for a Gaussian p0 and invertible unbounded transformations, if the support happens to be R^d, then this is trivial, but for more general settings this seems to be an issue that you have not dealt? Indeed in your Dirichlet example, you explicitly map to the required support, but for more complex constraints this may be non trivial to do with invertible models with known Jacobian? It would be nice to include this in the more general treatment rather than just relegating it to the specific example.
Overall I am very pleased to see someone tackling this question with a very natural approach.