Boosted Generative Models
Aditya Grover Stefano Ermon






Boosted Generative Models
    Aditya Grover, Stefano Ermon

Computer Science Department

Stanford University




    December 30, 2023
======================================================================================


We propose a novel approach for using unsupervised boosting to create an ensemble of generative models, where models are trained in sequence to correct earlier mistakes. Our meta-algorithmic framework can leverage any existing base learner that permits likelihood evaluation, including recent deep expressive models. Further, our approach allows the ensemble to include discriminative models trained to distinguish real data from model-generated data. We show theoretical conditions under which incorporating a new model in the ensemble will improve the fit and empirically demonstrate the effectiveness of our black-box boosting algorithms on density estimation, classification, and sample generation on benchmark datasets for a wide range of generative models.





§ INTRODUCTION

 A variety of deep generative models have shown promising results on tasks spanning computer vision, speech recognition, natural language processing, and imitation learning <cit.>.
These parametric models differ from each other in their ability to perform various forms of tractable inference, learning algorithms, and objectives.
Despite significant progress, existing generative models cannot fit complex distributions with a sufficiently high degree of accuracy, limiting their applicability and leaving room for 
improvement.

In this paper, we propose a technique for ensembling (imperfect) generative models to improve their overall performance.
Our meta-algorithm is inspired by boosting, a technique used in supervised learning to
combine weak classifiers (, decision stumps or trees), which individually might not perform well on a given classification task, into a more powerful ensemble.
The boosting algorithm will attempt to learn a classifier to correct for the mistakes made by reweighting the original dataset, and repeat this procedure recursively. Under some conditions on the weak classifiers' effectiveness, this procedure can drive the (training) error to zero <cit.>. Boosting can also be thought as a feature learning algorithm, where at each round a new feature is learned by training a classifier on a reweighted version of the original dataset. 
In practice, algorithms based on boosting perform extremely well in machine learning competitions <cit.>.

We show that a similar procedure can be applied to generative models. Given an initial generative model that provides an imperfect fit to the data distribution, we construct a second model to correct for the error, and repeat recursively. The second model is also a generative one, which is trained on a reweighted version of the original training set. Our meta-algorithm is general and can construct ensembles of any existing generative model that permits (approximate) likelihood evaluation
such as fully-observed belief networks, sum-product networks, and variational autoencoders.
Interestingly, our method can also leverage powerful discriminative models. 
Specifically, we train a binary classifier to distinguish true data samples from “fake” ones generated by the current model and provide a principled way to include this discriminator in the ensemble. 

A prior attempt at boosting density estimation proposed a sum-of-experts formulation <cit.>. This approach is similar to supervised boosting where at every round of boosting we derive a reweighted additive estimate of the boosted model density. 
In contrast, our proposed framework uses multiplicative boosting which multiplies the ensemble model densities and can be interpreted as a product-of-experts formulation. 
We provide a holistic theoretical and algorithmic framework for multiplicative boosting contrasting with competing additive approaches. Unlike prior use cases of product-of-experts formulations, our approach is black-box, and we empirically test the proposed algorithms on several generative models from simple ones such as mixture models to expressive parameteric models such as sum-product networks and variational 
autoencoders.

Overall, this paper makes the following contributions:


  * We provide theoretical conditions for additive and multiplicative boosting under which incorporating a new model is guaranteed to improve the ensemble fit.

  * We design and analyze a flexible meta-algorithmic boosting framework for including both generative and discriminative models in the ensemble.

  * We demonstrate the empirical effectiveness of our algorithms for density estimation, generative classification, and sample generation on several benchmark datasets. 




§ UNSUPERVISED BOOSTING

Supervised boosting provides an algorithmic formalization of the hypothesis that a sequence of weak learners can create a single strong learner <cit.>. 
Here, we propose a framework that extends boosting to unsupervised settings for learning generative models. For ease of presentation, all distributions are with respect to any arbitrary  𝐱∈ℝ^d, unless otherwise specified. We use upper-case symbols to denote probability distributions and assume they all admit absolutely continuous densities (denoted by the corresponding lower-case notation) on a reference measure d𝐱. Our analysis naturally extends to discrete distributions, which we skip for brevity. 


Formally, we consider the following maximum likelihood estimation (MLE) setting. Given some  data points X={𝐱_i ∈ℝ^d}_i=1^m sampled i.i.d. from an unknown distribution P, we provide a model class 𝒬 parameterizing the distributions that can be represented by the generative model and minimize the Kullback-Liebler (KL) divergence with respect to the true distribution:

    min_Q ∈𝒬 D_KL(P ‖ Q).


In practice, we only observe samples from P and hence, maximize the log-likelihood of the observed data X. Selecting the model class for maximum likelihood learning is non-trivial; MLE w.r.t. a small class can be far from P, whereas a large class poses the risk of overfitting in the absence of sufficient data, or even underfitting due to difficulty in optimizing non-convex objectives that frequently arise due to the use of latent variable models, neural networks, etc.

The boosting intuition is to greedily increase model capacity by learning a sequence of weak intermediate models {h_t ∈ℋ_t}_t=0^T that can correct for mistakes made by previous models in the ensemble. Here, ℋ_t is a predefined model class (such as 𝒬) for h_t. We defer the algorithms pertaining to the learning of such intermediate models to the next section, and first discuss two mechanisms for deriving the final estimate q_T from the individual density estimates at each round, {h_t}_t=0^T.



 §.§ Additive boosting

In additive boosting, the final density estimate is an arithmetic average of the intermediate models:

    q_T = ∑_t=0^T α_t · h_t

where 0 ≤α_t≤ 1 denote the weights assigned to the intermediate models. The weights are re-normalized at every round to sum to 1 which gives us a valid probability density estimate. Starting with a base model h_0, we can express the density estimate after a round of boosting recursively as:

    q_t = (1-α̂_t) · q_t-1 + α̂_t · h_t

where α̂_t denotes the normalized weight for h_t at round t. We now derive conditions on the intermediate models that guarantee “progress” in every round of boosting.


Let δ^t_KL(h_t, α̂_t) = D_KL(P ‖ Q_t-1) - D_KL(P ‖ Q_t) denote the reduction in KL-divergence at the t^th round of additive boosting. The following conditions hold:
 
 
  * Sufficient: If 𝔼_P [logh_t/q_t-1] ≥ 0, then δ^t_KL(h_t, α̂_t) ≥ 0 for all
 α̂_t ∈ [0,1].
 
  * Necessary: If ∃α̂_t ∈ (0, 1] such that δ^t_KL(h_t, α̂_t) ≥ 0, then 𝔼_P [h_t/q_t-1] ≥ 1.
 


In Appendix <ref>.


The sufficient and necessary conditions require that the expected log-likelihood and likelihood respectively of the current intermediate model, h_t are better-or-equal than those of the combined previous model, q_t-1 under the true distribution when compared using density ratios. 
Next, we consider an alternative formulation of multiplicative boosting for improving the model fit to an arbitrary data distribution.



 §.§ Multiplicative boosting


In multiplicative boosting, we factorize the final density estimate as a geometric average of  T+1 intermediate models {h_t}_t=0^T, each assigned an exponentiated weight α_t:

    q_T = ∏_t=0^T h_t^α_t/Z_T

where the partition function Z_T = ∫∏_t=0^T h_t^α_t d𝐱. 
Recursively, we can specify the density estimate as:

    q̃_t    = h_t^α_t·q̃_t-1

where q̃_t is the unnormalized estimate at round t. The base model h_0 is learned using MLE. The conditions on the intermediate models for reducing KL-divergence at every round are stated below.


Let δ^t_KL(h_t, α_t) = D_KL(P ‖ Q_t-1) - D_KL(P ‖ Q_t) denote the reduction in KL-divergence at the t^th round of multiplicative boosting. The following conditions hold:
 
 
  * Sufficient: If 𝔼_P [log h_t] ≥log𝔼_Q_t-1[h_t], then δ^t_KL(h_t, α_t) ≥ 0 for all
 α_t ∈ [0, 1].
 
  * Necessary: If ∃α_t ∈ (0, 1] such that δ^t_KL(h_t, α_t) ≥ 0, then 𝔼_P [log h_t] ≥𝔼_Q_t-1[log h_t].
 


In Appendix <ref>.


In contrast to additive boosting, the conditions above compare expectations under the true distribution with expectations under the model distribution in the previous round, Q_t-1. The equality in the conditions holds for α_t=0, which corresponds to the trivial case where the current intermediate model is ignored in Eq. (<ref>). For other valid α_t, the non-degenerate version of the sufficient inequality guarantees progress towards the true data distribution. Note that the intermediate models increase the overall capacity of the ensemble at every round. As we shall demonstrate later, we find models fit using multiplicative boosting to outperform their additive counterparts empirically suggesting the conditions in Theorem <ref> are easier to fulfill in practice.  


From the necessary condition, we see that a “good" intermediate model h_t  assigns a better-or-equal log-likelihood under the true distribution as opposed to the model distribution, Q_t-1. This condition suggests two learning algorithms for intermediate models which we discuss next.



§ BOOSTED GENERATIVE MODELS

In this section, we design and analyze meta-algorithms for multiplicative boosting of generative models. Given any base model which permits (approximate) likelihood evaluation, we provide a mechanism for boosting this model using an ensemble of generative and/or discriminative models.






 §.§ Generative boosting

Supervised boosting algorithms such as AdaBoost typically involve a reweighting procedure for training weak learners <cit.>. We can similarly train an ensemble of generative models for unsupervised boosting, where every subsequent model performs MLE w.r.t a reweighted data distribution D_t:

    max_h_t𝔼_D_t[log h_t] 
    where d_t ∝(p/q_t-1)^β_t

and β_t ∈ [0, 1] is the reweighting coefficient at round t. Note that these coefficients are in general different from the model weights α_t that appear in  Eq. (<ref>). 


If we can maximize the objective in Eq. (<ref>) optimally, then δ_KL^t(h_t, α_t) ≥ 0 for any β_t ∈ [0, 1]
with the equality holding for β_t=0.


In Appendix <ref>.


While the objective in Eq. (<ref>) can be hard to optimize in practice, the target distribution becomes easier to approximate as we reduce the reweighting coefficient. For the extreme case of β_t=0, the reweighted data distribution is simply uniform. There is no free lunch however, since a low β_t results in a slower reduction in KL-divergence leading to a computational-statistical trade-off. 

The pseudocode for the corresponding boosting meta-algorithm, referred to as GenBGM, is given in Algorithm <ref>. In practice, we only observe samples from the true data distribution, and hence, approximate p based on the empirical data distribution which is defined to be uniform over the dataset X. At every subsequent round, GenBGM learns an intermediate model that maximizes the log-likelihood of data sampled from a reweighted data distribution. 





 §.§ Discriminative boosting


A base generative model can be boosted using a discriminative approach as well. Here, the intermediate model is specified as the density ratio obtained from a binary classifier. Consider the following setup: we observe an equal number of samples drawn i.i.d. from the true data distribution (w.l.o.g. assigned the label y=+1) and the model distribution in the previous round Q_t-1 (label y=0). 


Let f: ℝ^+→ℝ be any convex, lower semi-continuous function satisfying f(1) = 0. 
The f-divergence between P and Q is defined as, D_f(P ‖ Q) = ∫ q · f(p/q) d𝐱.


Notable examples include the Kullback-Liebler (KL) divergence, Hellinger distance, and the Jenson-Shannon (JS) divergence among many others. The binary classifier in discriminative boosting maximizes a variational lower bound on any f-divergence at round t:

    D_f(P ‖ Q_t-1) ≥sup_r_t∈ℛ_t (𝔼_P[r_t] - 𝔼_Q_t-1[f^⋆(r_t)]).

 where f^⋆ denotes the Fenchel conjugate of f and r_t:ℝ^d →dom_f^⋆ parameterizes the classifier. Under mild conditions on f <cit.>, the lower bound in Eq. (<ref>) is tight if
r_t^⋆ = f'( p/q_t-1).
 
Hence, a solution to Eq. (<ref>) can be used to estimate density ratios. The density ratios naturally fit into the multiplicative boosting framework and provide a justification for the use of objectives of the form Eq. (<ref>) for learning intermediate models as formalized in the proposition below.

For any given f-divergence, let r_t^⋆ denote the optimal solution to Eq. (<ref>) in the t^th round of boosting. Then, the model density at the end of the boosting round matches the true density if we set α_t=1 and 
h_t = [f']^-1 (r_t^⋆)
where [f']^-1 denotes the inverse of the derivative of f.


In Appendix <ref>.


The pseudocode for the corresponding meta-algorithm, DiscBGM is given in Algorithm <ref>. At every round, we train a binary classifier to optimize the objective in Eq. (<ref>) for a chosen f-divergence.  
As a special case, the negative of the cross-entropy loss commonly used for binary classification is also a lower bound on an f-divergence. While Algorithm <ref> is applicable for any f-divergence, we will focus on cross-entropy henceforth to streamline the discussion.



Consider the (negative) cross-entropy objective maximized by a binary classifier:

    sup_c_t∈𝒞_t𝔼_P[log c_t] + 𝔼_Q_t-1[log(1-c_t)].

If a binary classifier c_t trained to optimize Eq. (<ref>) is Bayes optimal, then the model density after round t matches the true density if we set α_t=1 and 
h_t= c_t/1-c_t.


In Appendix <ref>.


In practice, a classifier with limited capacity trained on a finite dataset will not generally be Bayes optimal. The above corollary, however, suggests that a good classifier can provide a `direction of improvement', in a similar spirit to gradient boosting for supervised learning <cit.>. Additionally, if the intermediate model distribution h_t obtained using the above corollary satisfies the conditions in Theorem <ref>, it is guaranteed to improve the fit. 

The weights α_t∈ [0,1] can be interpreted as our confidence in the classification estimates, akin to the step size used in gradient descent. 
While in practice we heuristically assign weights to the intermediate models, the greedy optimum value of these weights at every round is a critical point for δ^t_KL (defined in Theorem <ref>). For example, in the extreme case where c_t is uninformative, , c_t ≡ 0.5, then δ^t_KL(h_t, α_t)=0 for all α_t∈ [0,1]. If c_t is Bayes optimal, then δ^t_KL attains a maxima when α_t=1 (Corollary <ref>).





 §.§ Hybrid boosting

Intermediate models need not be exclusively generators or discriminators; we can design a boosting ensemble with any combination of generators and discriminators.
If an intermediate model is chosen to be a generator, we learn a generative model using MLE after appropriately reweighting the data points. If a discriminator is used to implicitly specify an intermediate model, we set up a binary classification problem.



 §.§ Regularization

In practice, we want boosted generative models (BGM) to generalize to data outside the training set X. Regularization in BGMs is imposed primarily in two ways. First, every intermediate model can be independently regularized by incorporating explicit terms in the learning objective, early stopping based on validation error, heuristics such as dropout, etc. 
Moreover, restricting the number of rounds of boosting is another effective mechanism for regularizing BGMs. Fewer rounds of boosting are required if the intermediate models are sufficiently expressive.





§ EMPIRICAL EVALUATION

Our experiments are designed to demonstrate the superiority of the proposed boosting meta-algorithms on a wide variety of generative models and tasks. 
A reference implementation of the boosting meta-algorithms is available at . Additional implementation details for the experiments below are given in Appendix <ref>.








 §.§ Multiplicative vs. additive boosting

A common pitfall with learning parameteric generative models is model misspecification with respect to the true underlying data distribution. For a quantitative and qualitative understanding of the behavior of additive and multiplicative boosting, we begin by considering a synthetic setting for density estimation on a mixture of Gaussians.



  
Density estimation on synthetic dataset.
The true data distribution is a equi-weighted mixture of four Gaussians centered symmetrically around the origin, each having an identity covariance matrix. The contours of the underlying density are shown in Figure <ref>. We observe 1,000 training samples drawn independently from the data distribution (shown as black dots in Figure <ref>), and the task is to learn this distribution. The test set contains 1,000 samples from the same distribution. We repeat 
the process 10 times for statistical significance.

As a base (misspecified) model, we fit a mixture of two Gaussians to the data; the contours for an example instance are shown in Figure <ref>. We  compare multiplicative and additive boosting, each run for T=2 rounds.
For additive boosting (Add), we extend the algorithm proposed by  rosset2002boosting setting α̂_0 to unity and doing a line search over α̂_1, α̂_2 ∈ [0, 1]. 
For Add and GenBGM, the intermediate models are mixtures of two Gaussians as well. 
The classifiers for DiscBGM are multi-layer perceptrons with two hidden layers of 100 units each and ReLU activations, trained to maximize f-divergences corresponding to the negative cross-entropy (NCE) and Hellinger distance (HD) using the Adam optimizer <cit.>. 

The test negative log-likelihood (NLL) estimates are listed in Table <ref>. Qualitatively, the contour plots for the estimated densities after every boosting round on a sample instance are shown in Figure <ref>. Multiplicative boosting algorithms outperform additive boosting in correcting for model misspecification. GenBGM initially leans towards maximizing coverage, whereas both versions of DiscBGM are relatively more conservative in assigning high densities to data points away from the modes.




  
Heuristic model weighting strategies.
The multiplicative boosting algorithms require as hyperparameters the number of rounds of boosting and weights assigned to the intermediate models. For any practical setting, these hyperparameters are specific to the dataset and task under consideration and should be set based on cross-validation. While automatically setting model weights is an important direction for future work, we propose some heuristic weighting strategies.  Specifically, the unity heuristic assigns a weight of 1 to every model in the ensemble, the uniform heuristic assigns a weight of 1/(T+1) to every model, and the decay heuristic assigns as a weight of 1/2^t to the t^th model in the ensemble.




In Figure <ref>, we observe that the performance of the algorithms is sensitive to the weighting strategies. In particular, DiscBGM produces worse estimates as T increases for the “uniform" (red) strategy. 
The performance of GenBGM also degrades slightly with increasing T for the “unity” (green) strategy. 
Notably, the “decay” (cyan) strategy achieves stable performance for both the algorithms.
Intuitively, this heuristic follows the rationale of reducing the step size in gradient based stochastic optimization algorithms, and we expect this strategy to work better even in other settings. However, this strategy could potentially result in slower convergence as opposed to the unity strategy. 







  
Density estimation on benchmark datasets. We now evaluate the performance of additive and multiplicative boosting for density estimation on real-world benchmark datasets <cit.>. We consider two generative model families: mixture of Bernoullis (MoB) and sum-product networks <cit.>. While our results for multiplicative boosting with sum-product networks (SPN) are competitive with the state-of-the-art, the goal of these experiments is to perform a robust comparison of boosting algorithms as well as demonstrate their applicability to various model families.

We set T=2 rounds for additive boosting and GenBGM. Since DiscBGM requires samples from the model density at every round, we set T=1 to ensure computational fairness such that the samples can be obtained efficiently from the base model sidestepping running expensive Markov chains. Model weights are chosen based on cross-validation. 
The results on density estimation are reported in Table <ref>.
Since multiplicative boosting estimates are unnormalized, we use importance sampling to estimate the partition function. 

When the base model is MoB, the Add model underperforms and is often worse than even the baseline model for the best performing validated non-zero model weights. GenBGM consistently outperforms Add and improves over the baseline model in a most cases (4/6 datasets). DiscBGM performs the best and convincingly outperforms the baseline, Add, and  GenBGM on all datasets. For results on SPNs, the boosted models all outperform the baseline. GenBGM again edges out Add models (4/6 datasets), whereas DiscBGM models outperform all other models on all datasets.  These results demonstrate the usefulness of boosted expressive model families, especially the DiscBGM approach, which performs the best, while GenBGM is preferable to Add.





 §.§ Applications of generative models




  
Classification. Here, we evaluate the performance of boosting algorithms for classification. Since the datasets above do not have any explicit labels, we choose one of the dimensions to be the label (say y). Letting 𝐱_y̅ denote the remaining dimensions, we can obtain a prediction for y as, 

    p(y=1|𝐱_y̅)= p(y=1, 𝐱_y̅)/p(y=1, 𝐱_y̅) + p(y=0, 𝐱_y̅)

which is efficient to compute even for unnormalized models. We repeat the above procedure for all the variables predicting one variable at a time using the values assigned to the remaining variables. The results are reported in Table <ref>. When the base model is a MoB, we observe that the Add approach could often be worse than the base model whereas GenBGM performs slightly better than the baseline (4/6 datasets). The DiscBGM approach consistently performs well, and is only outperformed by GenBGM for two datasets for MoB. When SPNs are used instead, both Add and GenBGM improve upon the baseline model while DiscBGM again is the best performing model on all but one dataset.






  
Sample generation. 
We compare boosting algorithms based on their ability to generate image samples for the binarized MNIST dataset of handwritten digits <cit.>. We use variational autoencoders (VAE) as the base model <cit.>. While any sufficiently expressive VAE can generate impressive examples, we design the experiment to evaluate the model complexity approximated as the number of learnable parameters.

Ancestral samples obtained by the baseline VAE model are shown in Figure <ref>. We use the evidence lower bound (ELBO) as a proxy for approximately evaluating the marginal log-likelihood during learning. The conventional approach to improving the performance of a latent variable model is to increase its representational capacity by adding hidden layers (Base + depth) or increasing the number of hidden units in the existing layers (Base + width). These lead to a marginal improvement in sample quality as seen in Figure <ref> and Figure <ref>. 

In contrast,  boosting makes steady improvements in sample quality. We start with a VAE with much fewer parameters and generate samples using a hybrid boosting GenDiscBGM sequence VAE→CNN→VAE (Figure <ref>) . The discriminator used is a convolutional neural network (CNN) <cit.> trained to maximize the negative cross-entropy. We then generate samples using independent Markov chain Monte Carlo (MCMC) runs.
The boosted sequences generate sharper samples than all baselines in spite of having similar model capacity. 



§ DISCUSSION AND RELATED WORK

In this work, we revisited boosting, a class of meta-algorithms developed in response to a seminal
question: Can a set of weak learners create a single strong learner?
Boosting has offered interesting theoretical insights into the fundamental limits of supervised learning and led to the development of algorithms that work well in practice  <cit.>. 
Our work provides a foundational framework for unsupervised boosting with connections to prior work discussed below.



  
Sum-of-experts.
 rosset2002boosting proposed an algorithm for density estimation using Bayesian networks similar to gradient boosting.
These models are normalized and easy to sample, but are generally outperformed by multiplicative formulations for correcting for model misspecification, as we show in this work. Similar additive approaches have been used for improving approximate posteriors for specific algorithms for variational inference <cit.> and generative adversarial networks <cit.>. For a survey on variations of additive ensembling for unsupervised settings, refer to the survey by  bourel2012aggregating. 



  
Product-of-experts.
Our multiplicative boosting formulation can be interpreted as a product-of-experts approach, which was initially proposed for feature learning in energy based models such as Boltzmann machines. For example, the hidden units in a restricted Boltzmann machine can be interpreted as weak learners performing MLE.
If the number of weak learners is fixed, they can be efficiently updated in parallel but there is a risk of learning redundant features
 <cit.>. 
Weak learners can also be added incrementally based on the learner's ability to distinguish observed data and model-generated data <cit.>.  tu2007learning generalized the latter to boost arbitrary probabilistic models; their algorithm is a special case of DiscBGM  with all α's set to 1 and the discriminator itself a boosted classifier. DiscBGM additionally accounts for imperfections in learning classifiers through flexible model weights. Further, it can include any classifier trained to maximize any f-divergence. 

Related techniques such as noise-contrastive estimation, ratio
matching, and score matching methods can be cast as minimization of Bregman divergences, akin to DiscBGM with unit model weights <cit.>. A non-parametric algorithm similar to GenBGM was proposed by  di2004boosting where an ensemble of weighted kernel density estimates are learned to approximate the data distribution. In contrast, our framework allows for both parametric and non-parametric learners and uses a different scheme for reweighting data points than proposed in the above work. 




  
Unsupervised-as-supervised learning.
The use of density ratios learned by a binary classifier for estimation was first proposed by  friedman2001elements and has been subsequently applied elsewhere, notably for parameter estimation using noise-contrastive estimation <cit.> and sample generation in generative adversarial networks (GAN) <cit.>. While GANs consist of a discriminator distinguishing real data from model generated data similar to DiscBGM for a suitable f-divergence, they differ in the learning objective for the generator <cit.>. The generator of a GAN performs an adversarial minimization of the same objective the discriminator maximizes, whereas DiscBGM uses the likelihood estimate of the base generator (learned using MLE) and the density ratios derived from the discriminator(s) to estimate the model density for the ensemble.




  
Limitations and future work. In the multiplicative boosting framework, the model density needs to be specified only up to a normalization constant at any given round of boosting. Additionally, while many applications of generative modeling such as feature learning and classification can sidestep computing the partition function, if needed it can be estimated using techniques such as Annealed Importance Sampling <cit.>. Similarly, Markov chain Monte Carlo methods can be used to generate samples. The lack of implicit normalization can however be limiting for applications requiring fast log-likelihood evaluation and sampling. 

In order to sidestep this issue, a promising direction for future work is to consider boosting of normalizing flow models <cit.>. These models specify an invertible multiplicative transformation from one  distribution to another using the change-of-variables formula such that the resulting distribution is self-normalized and efficient ancestral sampling is possible. 
The GenBGM algorithm can be adapted to normalizing flow models whereby every transformation is interpreted as a weak learner. The parameters for every transformation can be trained greedily after suitable reweighting resulting in a self-normalized boosted generative model.




§ CONCLUSION

We presented a general-purpose framework for boosting generative models by explicit factorization of the model likelihood as a product of simpler intermediate model densities. These intermediate models are learned greedily using discriminative or generative approaches, gradually increasing the overall model's capacity. 
We demonstrated the effectiveness of these models over baseline models and additive boosting for the tasks of density estimation, classification, and sample generation. 
Extensions to semi-supervised learning <cit.> and structured prediction <cit.> are
exciting directions for future work.








§ ACKNOWLEDGEMENTS

We are thankful to Neal Jean, Daniel Levy, and Russell Stewart for helpful critique. This research was supported by a Microsoft Research PhD fellowship in machine learning for the first author, NSF grants #1651565, #1522054, #1733686, a Future of Life Institute grant, and Intel.
9pt10pt aaai





§ APPENDICES




§ PROOFS OF THEORETICAL RESULTS





 §.§ Theorem <ref>



The reduction in KL-divergence can be simplified as:


    δ^t_KL(h_t, α̂_t)    = 𝔼_P[logp/q_t-1] - 𝔼_P[logp/q_t] 
       = 𝔼_P[logq_t/q_t-1] 
       = 𝔼_P[log[ (1-α̂_t) + α̂_t h_t/q_t-1]].


We first derive the sufficient condition by lower bounding 
δ^t_KL(h_t, α̂_t).

    δ^t_KL(h_t, α̂_t)    =𝔼_P[log[ (1-α̂_t) + α̂_t h_t/q_t-1]] 
       ≥𝔼_P[(1-α̂_t) log 1 + α̂_t logh_t/q_t-1]    (Arithmetic Mean≥Geometric Mean)
       = α̂_t 𝔼_P[logh_t/q_t-1].    (Linearity of expectation)

If the lower bound is non-negative, then so is δ^t_KL(h_t, α̂_t). Hence:

    𝔼_P[logh_t/q_t-1]    ≥ 0

which is the stated sufficient condition.



For the necessary condition to hold, we know that:

    0    ≤δ^t_KL(h_t, α̂_t) 
       =  𝔼_P[log[ (1-α̂_t) + α̂_t h_t/q_t-1]] 
       ≤log𝔼_P[ (1-α̂_t) + α̂_t h_t/q_t-1]    (Jensen's inequality)
       = log [ (1-α̂_t) + α̂_t 𝔼_P[  h_t/q_t-1]]    (Linearity of expectation)

Taking exponential on both sides, we get:

    (1-α̂_t) + α̂_t 𝔼_P[  h_t/q_t-1]    ≥ 1
    𝔼_P[  h_t/q_t-1]    ≥ 1

which is the stated necessary condition.







 §.§ Theorem <ref>


We first derive the sufficient condition.

    δ^t_KL(h_t, α_t)    = ∫ p log q_t  d𝐱 - ∫ p log q_t-1 d𝐱
       = ∫ p logh_t^α_t· q_t-1/Z_t - ∫ p log q_t-1   (using Eq. (<ref>))
       = α_t ·𝔼_P[log h_t] - log𝔼_Q_t-1[h_t^α_t]
       ≥α_t ·𝔼_P[log h_t] - log𝔼_Q_t-1[h_t]^α_t   (Jensen's inequality)
       = α_t ·[𝔼_P[log h_t] - log𝔼_Q_t-1[h_t]] 
       ≥ 0.    (by assumption)

Note that if α_t=1, the sufficient condition is also necessary. 



For the necessary condition to hold, we know that:

    0 ≤δ^t_KL(h_t, α_t)    = α_t ·𝔼_P[log h_t]  - log𝔼_Q_t-1[h_t^α_t]
       ≤α_t ·𝔼_P[log h_t]  - 𝔼_Q_t-1[log h_t^α_t]   (Jensen's inequality)
       =α_t · [𝔼_P[log h_t] - 𝔼_Q_t-1 [log h_t]]    (Linearity of expectation)
       ≤𝔼_P[log h_t] - 𝔼_Q_t-1 [log h_t].     (since α_t > 0)






 §.§ Proposition <ref>


By assumption, we can optimize Eq. (<ref>) to get:

    h_t    ∝(p/q_t-1)^β_t   .


Substituting for h_t in the multiplicative boosting formulation in Eq. (<ref>),:

    q_t    ∝q_t-1· h_t/Z_q_t
       ∝ q_t-1·(p/q_t-1)^β_t
       =  p^β_t·  q_t-1^1-β_t/Z_q_t

where the partition function Z_q_t = ∫ p^β_t·  q_t-1^1-β_t.



In order to prove the inequality, we first obtain a lower bound on the log-partition function, Z_q_t. For any given point, we have:

    p^β_t·  q_t-1^1-β_t   ≤β_t p +  (1-β_t) q_t-1.    (Arithmetic Mean ≥ Geometric Mean)

Integrating over all points in the domain, we get: 

    log Z_q_t   ≤log[β Z_p + (1-β) Z_q_t-1] 
       = 0

where we have used the fact that p and q_t-1 are normalized densities. 



Now, consider the following quantity:

    D_KL(P ‖ Q_t)    = 𝔼_P [logp/q_t]  
       = 𝔼_P [logp/p^β_t·  q_t-1^1-β_t/Z_q_t]  
       = (1-β_t) 𝔼_P [logp/q_t-1] + log Z_q_t
       ≤ (1-β_t) 𝔼_P [logp/q_t-1]    (using Eq. (<ref>))
       ≤𝔼_P [logp/q_t-1]     (since β_t ≥ 0) 
       = D_KL(P ‖ Q_t-1).






 §.§ Proposition <ref>


By the f-optimality assumption, we know that:

    r_t    = f'(p/q_t-1).

Hence, h_t = p/q_t-1. From Eq. (<ref>), we get:

    q_t    = q_t-1· h_t^α_t = p

finishing the proof.





 §.§ Corollary <ref>


Let u_t denote the joint distribution over (𝐱, y) at round t. We will prove a slightly more general result where we have m positive training examples sampled from p and the k negative training examples sampled from q_t-1.[In the statement for Corollary <ref>, the classes are assumed to be balanced for simplicity i.e., m=k.] Hence, we can express the conditional and prior densities as:

    p    = u(𝐱| y=1) 
    
    q_t-1   = u(𝐱| y=0) 
    
    u(y=1)    = m/m+k
    
    u(y=0)    = k/m+k.

The Bayes optimal density c_t can be expressed as:

    c_t    = u(y=1 |𝐱) 
    
       = u(𝐱| y=1)  u(y=1) / u(𝐱) .

Similarly, we have:

    1-c_t    = u(𝐱| y=0) u(y=0) / u(𝐱)
    .

From Eqs. (<ref>-<ref>, <ref>-<ref>), we have:

    h_t    = γ·c_t/1-c_t = p/q_t-1.

where γ = k/m. 



Finally from Eq. (<ref>), we get:

    q_t    = q_t-1· h_t^α_t = p

finishing the proof.


In Corollary <ref> below, we present an additional theoretical result below that derives the optimal model weight, α_t for an adversarial Bayes optimal classifier. 



 §.§ Corollary <ref>

  [to Corollary <ref>]
Define an adversarial Bayes optimal classifier c_t' as one that assigns the density c_t' = 1 - c_t where c_t is the Bayes optimal classifier.
For an adversarial Bayes optimal classifier c_t', δ^t_KL attains a maxima of zero when α_t=0. 



For an adversarial Bayes optimal classifier,

    c_t'    = u(𝐱| y=0) u(y=0) / u(𝐱)
    
    1-c_t'    = u(𝐱| y=1) u(y=1) / u(𝐱).

From Eqs. (<ref>-<ref>,   <ref>-<ref>), we have:

    h_t    = γ·c_t'/1-c_t' = q_t-1/p.

Substituting the above intermediate model in Eq. (<ref>),

    δ^t_KL(h_t, α_t)    = α_t ·𝔼_P[logq_t-1/p] - log𝔼_Q_t-1[q_t-1/p]^α_t
       ≤α_t ·𝔼_P[logq_t-1/p] - 𝔼_Q_t-1[α_t ·logq_t-1/p]    (Jensen's inequality)
       = α_t · [𝔼_P[logq_t-1/p] - 𝔼_Q_t-1[logq_t-1/p]]    (Linearity of expectation)
       = -α_t [D_KL(P ∥ Q_t-1) + D_KL(Q_t-1∥ P) ]
       ≤ 0     (D_KL is non-negative).

By inspection, the equality holds when α_t=0 finishing the proof. 






§ ADDITIONAL IMPLEMENTATION DETAILS
 



 §.§ Density estimation on synthetic dataset



  
Model weights. For DiscBGM, all model weights, α's to unity. The model weights for GenBGM, α's are set uniformly to 1/(T+1) and reweighting coefficients, β's  are set to unity.



 §.§ Density estimation on benchmark datasets



  
Generator learning procedure details. We use the default open source implementations of mixture of Bernoullis (MoB) and sum-product networks (SPN) as given in  and  respectively for baseline models.



  
Discriminator learning procedure details. The discriminator considered for these experiments is a multilayer perceptron with two hidden layers consisting of 100 units each and ReLU activations learned using the Adam optimizer <cit.> with a learning rate of 1e-4. The training is for 100 epochs with a mini-batch size of 100, and finally the model checkpoint with the best validation error during training is selected to specify the intermediate model to be added to the ensemble.



  
Model weights. Model weights for multiplicative boosting algorithms, GenBGM and DiscBGM, are set based on best validation set performance of the heuristic weighting strategies. Partition function is estimated using importance sampling with the baseline model (MoB or SPN) as a proposal and a sample size of 1,000,000.



 §.§ Sample generation




  
VAE architecture and learning procedure details. Only the last layer in every VAE is stochastic, rest are deterministic. The inference network specifying the posterior contains the same architecture for the hidden layer as the generative network. The prior over the latent variables is standard Gaussian, the hidden layer activations are ReLU, and learning is done using Adam <cit.> with a learning rate of 10^-3 and mini-batches of size 100. 



  
CNN architecture and learning procedure details. The CNN contains two convolutional layers and a single full connected layer with 1024 units. Convolution layers have kernel size 5× 5, and 32 and 64 output channels, respectively. We apply ReLUs and 2× 2 max pooling after each convolution. The net is randomly initialized prior to training, and learning is done using the Adam <cit.> optimizer with a learning rate of 10^-3 and mini-batches of size 100.



  
Sampling procedure for BGM sequences.
Samples from the GenDiscBGM are drawn from a Markov chain run using the Metropolis-Hastings algorithm with a discrete, uniformly random proposal and the BGM distribution as the stationary distribution for the chain. Every sample in Figure <ref> (d) is drawn from an independent Markov chain with a burn-in period of 100,000 samples and a different start seed state. 


