Evaluation of Categorical Generative Models -- Bridging the Gap Between Real and Synthetic Data

The machine learning community has mainly relied on real data to benchmark algorithms as it provides compelling evidence of model applicability. Evaluation on synthetic datasets can be a powerful tool to provide a better understanding of a model's strengths, weaknesses, and overall capabilities. Gaining these insights can be particularly important for generative modeling as the target quantity is completely unknown. Multiple issues related to the evaluation of generative models have been reported in the literature. We argue those problems can be avoided by an evaluation based on ground truth. General criticisms of synthetic experiments are that they are too simplified and not representative of practical scenarios. As such, our experimental setting is tailored to a realistic generative task. We focus on categorical data and introduce an appropriately scalable evaluation method. Our method involves tasking a generative model to learn a distribution in a high-dimensional setting. We then successively bin the large space to obtain smaller probability spaces where meaningful statistical tests can be applied. We consider increasingly large probability spaces, which correspond to increasingly difficult modeling tasks and compare the generative models based on the highest task difficulty they can reach before being detected as being too far from the ground truth. We validate our evaluation procedure with synthetic experiments on both synthetic generative models and current state-of-the-art categorical generative models.


INTRODUCTION
In the machine learning community, evaluation of generative models is an ongoing topic of research [1,2,3,4,5,6,7,8]. The most common method is to evaluate the (usually upper bounded) log-likelihood on held out test data; the model with the highest log-likelihood is declared the better model. Although principled, this method of evaluation has some known drawbacks as highlighted in [6]. A simple example from [9] shows how good likelihood models can generate poor samples. Simply put, the learned model is far from the true distribution.
Another observation, possibly symptomatic of this issue, is the out-of-distribution (OOD) problem. A notable finding by [10] is that high likelihood and good sample generation do not guarantee good OOD detection. The task of OOD detection is an important application of generative modeling. If a Fig. 1: Overview of our proposed binning procedure. The initial distribution p has s = 3 flat regions on the Ω space contained in S = {S 1 , S 2 , S 3 } . For a granularity level k = 4, our binning procedure finds that cutting Hypothesis testing can then be conducted over the induced distributions p B * 4 , q B * 4 on the 4 event probability space B * 4 .
model is an appropriate approximation of the true distribution, then it should be able to detect low-probability samples. One approach taken in the literature to mitigate this problem is to adopt a more comprehensive and task-oriented methods of evaluation. By assessing over multiple metrics and designing task-oriented metrics, one can better assess the true capabilities of a generative model [6,3,11]. Nonetheless, this remains a heuristic approach that is unavoidably tied to the application at hand and therefore cannot be applied to the general problem of generative model evaluation.
In this work, we propose to return to a synthetic setting where the evaluation of a generative model can be framed as a statistical identity testing problem. This allows us to draw from statistical testing literature. This approach alleviates the problems associated with log-likelihood evaluation. Rather than testing whether high log-likelihood is assigned to unseen samples, we can directly evaluate whether the model assigns the correct probability mass to each element in the space. We can then directly answer questions about OOD capability, sample generation quality, and overall generative modeling performance. This approach also provides better insight into which types of distributions a particular generative model can fit.
The synthetic task must be representative of the actual task a generative model would be called to solve. In almost all cases, generative models in machine learning target a (very) high dimensional setting. One challenge induced by such set-tings is that statistical tests based on samples become meaningless. We simply cannot collect enough samples for a test to reject a null hypothesis. In this work, to address this issue, we propose an algorithm to bin the probability space at various granularity levels. We then consider the induced distributions on the smaller probability spaces as a testing proxy for our generative model quality, observing that the error for the induced distributions is a lower bound on the error in the original space. Figure 1 provides an overview of our procedure. Random binning is not successful and we explain how we construct bins to maximize the lower bound on the error.
We validate our binning procedure through synthetic experiments, ensuring it can preserve the correct ranking of synthetic generative models. We then show that our testing procedure correctly ranks state-of-the-art generative models trained on our synthetic task by comparing with the empirical total variation on the initial space Ω and with visual inspection of the learned distributions.

METHODOLOGY
We aim to design an evaluation method or metric that can rank generative models reliably for a very large scale discrete distribution space |Ω|, given the ground truth distribution p. Given samples from unknown distributions q 1 , q 2 , we wish to distinguish which distribution is closer to a reference distribution p (thus achieving a ranking of generative models).

Distribution Testing
This setting is analogous to a fundamental problem in statistical distribution testing: identity testing. In this setting, given sample access to an unknown distribution q, an identity test declares if q is -close to a reference distribution p with probability at least 1 − δ. See [12,13] for a more formal definition and [14] for a review on this topic. In this field, closeness of discrete distributions p, q on a discrete sample space Ω is formalized as the total variation distance: (with p x used as a shorthand for p(x)). The 2 or Hellinger can also be used. For relatively small sized Ω, results from the identity testing literature can be applied directly. However, we target large Ω where the practical number of samples is m |Ω|. At this scale, algorithms for identity testing are unusable; the provably most powerful test has a |Ω| term in its required number of samples [13].

Binning the space
We propose to move from the probability space Ω to a smaller space B by binning the elements x in partitioning sets of Ω: We then assess the distributions induced by this binning to evaluate the models.
We denote all partitions of Ω by ρ(Ω). The 'binned' distribution of the ground truth p is p B , and the 'binned' distribution of the generative model q becomes q B , where p B A = x∈A p x . This binning operation naturally introduces a new total variation error on the B space : Binning also introduces an error between the initial distribution p and its binned version p B that can be defined as: At the cost of introducing error, binning allows us to reduce the space to a workable size, so that we can use tools from the distribution testing literature. In particular, we can design a hypothesis test that aims to reject H 0 : d(p B , q B ) < at a probability significance level δ.
We can see that d T V (p B , q B ) is a lower bound for d T V (p, q), but the result of such test in the binned space does not provide an direct indication of the outcome in the original space. The intuition is that, if the test fails for some binning B, this suggests that a generative model is poor, in the sense that it cannot achieve the easier task of representing the binned distribution to within a required error. In the following section, we describe how we select the binning.

Choosing the bins
When moving from p, q to p B , q B , information is inevitably lost. Additionally, a smaller numbers of bins k = |B| will result in greater information loss. Therefore, for a given granularity level k, bins are chosen such that the least possible error on B k is introduced for the reference distribution p.
Minimizing the binning error of p→p B : We start by considering bins that minimize the error from going to p to p B . Denote by B p k (λ) the set of all k partitions of Ω s.t. p→p B is at most λ: where ρ k (Ω) denotes the set of all partitions of Ω of size k.
It is easy to test whether a particular B lies in B p k (λ) for any p, but B p k (λ) may be very large solution space. For the particular case where no error is tolerated B p k (λ = 0), however, the space is much smaller (and may be empty).
We take advantage of our ability to specify the synthetic distribution p, and construct p so that the pmf has s unique values and places all elements with a common value in bins S i to form the binning S = {S 1 , . . . , S s }. With a judicious choice of s, such a reference distribution is sufficient to provide a stern test of generative models. Given a p with s = |S| flat regions, we have that : where ci ∈ N is the cardinally of the partitioning that can be made on Si. The set { S i ∈S Pi; Pi ∈ ρ c j (Si), j cj = k} is all possible Algorithm 1 Highest granularity level k of q Input: p with flat regions s = |S|, sampling access from q, error threshold test , significance level δ.
Return the granularity k at which the test failed. Maximizing the binning error of p B , q B : By the triangle inequality, we can see that true error will always be greater than B . Hence, given the choice of binning from (B p k (0)), we can select the binning that maximizes the error between the induced binned distribution p B and the induced binned distribution q B : This concludes how we select bins at a specific granularity level B * k . For a given flat region A i , if we seek a k = 2 bingranularity: ρ 2 (S i ), the unique solution that maximises the error is to split the positive error region {x ∈ S i ; q x − p x > 0} from the negative error region {x ∈ S i ; q x − p x < 0}. If there is no positive or negative error, then every bin is equivalent. Thus, different and tractable solutions for the granularity k = {s, . . . , 2s} can be obtained: We have presented the discussion in terms of q and q B , but we assume that we only have sample access to q (and hence to q B ). Hence, only the empirical pmf of q is accessible. We can approximate with: . A limitation of this procedure is that it is tied to the number of flat regions s of the distribution p. However, since we have control over p, we can choose p with a number of flat regions that achieves a trade off between (i) posing a suitably demanding challenge and (ii) generating a test that does not require too many samples. In general, in very high dimensions, such as those of protein sequences, for example, structured distributions can be very challenging to learn even if there are only three unique values.

Hypothesis testing
We now have a sequence of binnings of increasingly difficult granularity levels, ranging from k = s to k = 2s : B * s , B * s+1 , . . . , B * 2s . At each granularity level k, we can use a hypothesis test to detect poor approximation of the ground truth. Since the sampling complexity of the test scales with the probability space and we control the granularity level k, we can easily generate O(k) samples. Our null hypothesis is that the binned generative model q B * k is within some error test of the ground truth distribution p B * k ; i.e.
We use the 2 distance as it is more practical to test for. If the test is able to reject at some granularity k, we stop and return this k as the highest granularity level reached by the generative model q. For the hypothesis testing, we use the closeness test from [15], which tests the distance between two distributions, both of which only have sample access. To make the test applicable to our context, we simply replace the statistical estimates for unknown p by our known statistics for p. The complete testing procedure is outlined in Algorithm 1.

EXPERIMENTS 3.1. Datasets
Our synthetic experiments are designed to emulate real world datasets. The most important characteristic is that the sampling space is several orders larger than the number of generated samples m. Second, the support of the targeted distribution (that we denote Ω + = {x ∈ Ω; p x > 0}) is believed to be much smaller than the whole space, i.e. Ω + /Ω ≈ 0. The intuition behind this feature is that uniform random sampling is very unlikely to give a valid sample. This is a characteristic of most applications of high-dimensional generative models. Nonetheless, the positive space is still generally believed to be very large and scales with the size of the space. We choose the ratio of approximately |Ω + |/|Ω| ≈ c!/c c as it loosely approaches an estimate given in [16] of the size of a family's sequence space. Since we want to keep the number of flat regions small (as explained in the previous section), we choose to model p by a stair distribution with s stairs, where the last stair is a assigned zero probability mass. Hence for a given s, we have

Baselines
Synthetic q: Even though we could scale to high Ω, for visualisation purposes, we set |Ω| = 6 6 and generate a smaller number of samples m = 1000. We define a stair distribution p with s = 4 flat regions. We produce 4 synthetic generative models q 1 , q 2 , q 3 , q 4 by increasingly perturbing the ground truth distribution: Generative models q: We evaluate our evaluation method on state-of-the-art generative models for categorical data. We set |Ω| = 6 6 and define a stair distribution p with s = 3 flat regions. CNF [17] is a normalizing flow method that learns a mapping from the categorical space to a continuous representation. CDM [18] is a diffusion-based model that operates in the discrete space. argmaxAR [19] is a normalizing flow method that uses an argmax operation to map a continuous representation to the discrete space. For each trial, we generate m = 10, 000 samples.

Experiment Details
We begin by validating our algorithm for choosing B * k . We verify the ordering of the empirical total variation given by emp ) of the synthetically created q 1 , q 2 , q 3 , q 4 aligns with the correct ranking: q 1 < q 2 < q 3 < q 4 . We compare the ordering provided by the empirical total variation derived form our binning algorithm B * k d T V (p B * k ,q B * k emp ) with the empirical total variation derived from some random binning B k d T V (p B k ,q B k emp ). To compare raking accuracy, we compute the Kendall Tau correlation coefficient which measures the piece-wise displacements between two rankings. A higher value corresponds to a more closely matched rank. Results can be viewed in Figure 2. Next, we test our evaluation procedure outlined in Algorithm 1 on state-ofthe-art categorical generative models. We validate that the generative model reaching the highest granularity level k with our test is the generative model with the lowest empirical total variation on Ω d T V (p,q emp ). We set the significance level of the hypothesis testing to δ = 0.05 and test for test = 0.1. We train each model on a dataset of 10, 000 training samples generated from p for 1000 epochs. For each baseline, a hyperparameter search is conducted over the hidden size =  Figure 2 shows the binning procedure we propose is sensible. In Figure 3, we show the empirical distribution generated from one trial of the generative models that were trained on the synthetic dataset as described in Section 3.3. Visually, we see that the CNF baseline distribution is a very poor approximation of the ground truth distribution. This is also reflected in its empirical total variation error d T V (p,q emp ). The argmaxAR and CDM baselines are closer, with the CDM slightly outperforming argmaxAR based on d T V (p,q emp ). This is reflected in our hypothesis testing ranking in Figure 4, where we see that all trials of the CDM pass the test at k = 4, whereas only a fraction of the argmaxAR trials pass the same test. Every CNF trial is rejected.

CONCLUSION
In conclusion, we have introduced an alternative way to evaluate generative models for categorical data. Even though our approach is based on statistical tests, it remains applicable for very large distribution space which is the setting of interest for those models. In future work, we plan on providing theoretical guarantee of our procedure and to further exploit our control over p to design an even more powerful test. pagebreak 6. COPYRIGHT FORMS © 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.