Concrete Score Matching: Generalized Score Matching for Discrete Data
Authors: Chenlin Meng
Kristy Choi
Jiaming Song
Stefano Ermon
Venue: NeurIPS 2022 Accept (2022)
Keywords: generative model
discrete data
score matching

Abstract: Representing probability distributions by the gradient of their density functions has proven effective in modeling a wide range of continuous data modalities. However, this representation is not applicable in discrete domains where the gradient is undefined.   To this end, we propose an analogous score function called the “Concrete score”, a generalization of the (Stein) score for discrete settings. Given a predefined neighborhood structure, the Concrete score of any input is defined by the rate of change of the probabilities with respect to local directional changes of the input. This formulation allows us to recover the (Stein) score in continuous domains when measuring such changes by the Euclidean distance, while using the Manhattan distance leads to our novel score function in discrete domains. Finally, we introduce a new framework to learn such scores from samples called Concrete Score Matching (CSM), and propose an efficient training objective to scale our approach to high dimensions. Empirically, we demonstrate the efficacy of CSM on density estimation tasks on a mixture of synthetic, tabular, and high-dimensional image datasets, and demonstrate that it performs favorably relative to existing baselines for modeling discrete data.

Concrete Score Matching: Generalized Score Matching for Discrete Data
Chenlin Meng"
Kristy Choi" Stanford University kechoi@cs stanf ord. edu
Stanford University
chenlinèes, stanford.edu
Jiaming Song NVIDIA j jiamings@nvidia.com
Stefano Ermon Stanford University, CZ Biohub ermon@cs stanford. edu
Abstract
Representing probability distributions by the gradient of their density functions has proven effective in modeling wide range of continuous data modalities. However, this representation is not applicable in discrete domains where the gradient is undefined. To this end, propose analogous score function called the "Concrete score", a generalization of the (Stein) score for discrete settings. Given predefined neighborhood structure, the Concrete score of any input is defined by the rate of change of the probabilities with respect to local directional changes of the input. This formulation allows to recover the (Stein) score in continuous domains when measuring such changes by the Euclidean distance, while using the Manhattan distance leads we introduce a new framework to learn such scores from samples called Concrete Score Matching (CSM), and propose an efficient training objective scale our approach to high dimensions. Empirically, we demonstrate the efficacy of CSM on density estimation tasks mixture of synthetic, tabular, and high-dimensional image datasets, and demonstrate that it performs favorably relative to existing baselines for modeling discrete data.
novel score function in discrete domains. Finally,
Introduction
When estimating a statistical model, the representation the underlying probability distribution has profound implications the downstream modeling task. Likelihood-based model families such as Variational Autoencoders (VAEs) [1-4], normalizing flows [5-13], and diffusion models [14-16] forced to either approximate the intractable normalizing constant utilize restrictive model architectures; implicit models [17-20] try to capture the underlying sampling process by relying on unstable adversarial training procedures. On the other hand, representing the distribution as the gradient of the log probability density function-alt circumvent such issues. This key to score matching's 's success on a wide range of continuous data modalities [21-25) In fact, its recent resurgence has led to significant advances in machine learning applications of density estimation, such as image generation [26, 16, 27, 15] and audio synthesis [28, 29], among others.
known as the (Stein) score -allows us to
However, score matching approaches that rely modeling the gradient of the data distribution inherently designed for continuous data; such methods hinge on the existence of the gradient, which undefined for discrete domains [22]. Given the ubiquitous nature of structured, discrete data in
Joint first author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

our world today such as graphs, text, genomic sequences, images, we desire an approach that would allow us to expand the successes of score-based generative models into discrete domains.
To address this challenge, we first introduce the Concrete score: a generalization of the (Stein) score that is amenable both continuous and discrete data types'. Given predefined neighborhood structure, the Concrete score leverages structural information in the data to construct surrogate gradient information about the discrete space by considering the similarity between two neighboring examples. More precisely, the Concrete score of any input is defined by the rate of change of the probabilities with respect to directional changes of the input. In direct analogy to the continuous (Stein) score, the intuition is that the Concrete score should remain small when two examples are "close" to one another; when the two examples are very different, the Concrete score will be large. We find that measuring such changes by the Euclidean distance recovers the (Stein) score in continuous domains, while using the Manhattan distance leads to our novel score function discrete domains.
Using this definition of the Concrete score, we then introduce a framework to learn such scores from samples called Concrete Score Matching (CSM). To successfully scale our method high dimensions, we also propose an efficient training objective as well as several variations of our approach that improve performance in practice. Empirically, we demonstrate the efficacy of CSM on wide range of density estimation tasks on a mixture of synthetic, tabular, and high-dimensional image datasets, and demonstrate that it performs favorably relative to existing baselines for modeling discrete data.
The contributions of our work can be summarized as follows:
1. We propose the Concrete score, a generalization of the (Stein) score to discrete domains. We construct the Conerete score such that it leverages structural information in the data to capture surrogate "gradient" information over discrete spaces.
2. We introduce a novel score matching framework for estimating such scores from samples called Concrete Score Matching (CSM). We then outline several connections between CSM and existing (continuous) score matching techniques, such denoising score matching (DSM).
3. We propose efficient learning objectives that allow our method to scale gracefully to high- dimensional datasets, and show how to port over the recent successes in continuous score matching approaches to discrete domains.
2 Preliminaries
Let Pdata (x) be the unknown data distribution over X' E RR,, for which we have access to i.i.d. samples NN [ ~ Pdaat((),, The (Stein) score of Pdata (x) is the first order derivative of the log data density function sxx) = Vx P(x). The goal of score matching is to learn an unnormalized density
(x) indexed by 0 E such that the estimated score function 8p sx(x) = V log gx(x) is close to s(x).
In practice, we leverage a score network 88 R + RR that is trained to minimize the Fisher divergence between go(x) and Pdata [23, 26]. Although the original objective is intractable to compute due to its dependence on the ground truth data scores sxx), we can leverage integration by parts [21] to simplify the objective as follows:
(sM E (x)
_ [1s(())] tr( (Vxso(x)) + const.
(1)
where tr(-) denotes the matrix trace, and the optimal score model satisfies sy- (x) R sxx). While the trace term in Eq. remains problematic it requires an expensive evaluation of the Hessian of the log-density function-recent works [23, 16] leverage the
trace estimator [31, 32] or directional derivatives [33] to efficiently approximate the training objective.
Despite their key role in successfully scaling score-based generative models to high-dimensional datasets, we note two critical limitations of existing score matching techniques: (1) X' must be continuous; and (2) the density function Pdsta (x) must be differentiable. This poses a significant challenge in discrete domains, where both requirements fail to hold.
We borrow the terminology from "concrete mathematics" [30].

---

The Concrete Score
The above limitations prevent the direct application of score matching techniques discrete data. We thus propose the Concrete score, a generalization of the (Stein) score for discrete settings. The key intuition is that although the gradient is undefined in discrete spaces, can still construct surrogate for the gradient by leveraging local directional changes to the input. We do so by exploiting special neighborhood structures in the data, and elaborate upon the necessary conditions on these structures to guarantee that our surrogate gradient indeed recovers a valid score function that (1) completely characterizes the distribution, and (2) is amenable for parameter estimation.
3.1 Constructing Surrogate Gradients for Discrete Data
To be more precise, let Pdata (x) be the data distribution over X. We denote A X as the function mapping each example x A' to set of neighbors, such that N(x) = {x,, ..... Xx. and K | (x)l This neighborhood induces particular graphical structure onto the support of Paata (x), which we call the 'neighborhood induced graph", that will play key role in constructing the surrogate gradient.
provide formal definition below.
Definition (Neighborhood-induue graph). Let (x) be the data distribution over X and N be the function mapping each node x X its set of neighbors. The srighborhood-nducee graph is the directed graph which results from adding directed edge from x to each node in its neighborhood set X, (x). for all supp(Paata
important point that the neighborhood structure can be asymmetric, since the neighhorhood-
induced graph is a directed graph. This implies that there may exist cases where N(x) = {x1} does
not necessarily imply that N (x1) = {x]. We provide an intuitive example below.
Example 1. When X = Xn, , Xs}. and the neighhorhood structure N is defined as: (xx))= = {0} and (x,) {xo} } Vi 1, ...... 5, the neighhorhoout-nndce
graph is the star graph in Figure 1.
There exist a wide range of neighborhood structures, all of which yield different neighborhood- induced graphs. We visualize five common structures in Figure
Star
Complete graph
Single bit flip
Chain
Grid
Figure 1: Examples of common neighborhood structures and their corresponding (connected) sigghborhhoo-indueee graphs, where the arrows point to the neighbors of given node. Note that the neighborhood structure is directed.
Such graphs provide insight into the kinds of neighborhood structures that are amenable to our framework. One necessary characteristic of such graphs is connectedness. In fact, the five common graphical structures (among others) shown Figure are all weakly connected graphs. We emphasize that connectedness does take the directionality of the underlying graph G's edges into account-it does not matter whether a node x has an incoming or outgoing edge.
With the above definitions in place, we can now define the surrogate gradient the local differences between set of examples (similar to directional derivative in the continuous case). Using this notion construct the Concrete score the rate of change of the probabilities with
of the "gradient", respect to these local directional changes in the input x as defined below.
Definition 2 (Concrete score), Let N be a function mapping each point x to its set of neighbors N(x) {Xn:: ..., }, ). Then, the Concrete score Cpana (x;N) X [xx) for a given distribution Pdata (x) evaluated at x is:
Pdataa (xmi) (Paata())
Pdata P Pdaca (x)
Cpasta (x:N) A
Pdata(
Pdata
'e consider fixed number of neighbors K for each to simplify our notation, but note that this can be generalized variable number of neighbors for every

---

Although we have defined the Concrete score, we have yet to justify whether it is indeed suitable score function for estimating Paata The necessary condition, which we call completeness [34], ensures that the Concrete score preserves enough information about Pdata (x) such that we can successfully learn Pdata (x) from data samples using score matching. We make this statement more precise in the following theorem.
Theorem (Completeness). Let Paata be a (discrete) data distribution. Denote Cpant (x: N) as the Concrete score of (x) with neighhoring structure N, and co(x; N) the Concrete score for distribution (x(x) parameterized by E O When the graph induced by the neighborhood structure N connected, co Nx) Cpanta Nx: implies that pe pe(x)
-data (x) Vx E
Proof sketch. If two nodes x and x' in a neighborhood--induee graph 9 share an edge, then their density ratio Pdsta (x') (x))/dssta(xx (dataa can be uniquely identified using Cpasc. (x: Thus when G is connected. the density ratio between any node pairs in G is uniquely identified given Cpasta N). Therefore, knowing the density ratio between any two points uniquely identifies Pasta (X).
We provide the full proof in Appendix A. We emphasize here that the connectedness of the neighborhood-inducee induced graph (a kind of regularity condition on N and Pdata(X)) was crucial for demonstrating the completness of the Concrete score.
Note that Theorem only requires the neighborhood-induee graph to be connected. This implies that given a connected graph, we can augment it with additional edges-the new graph will still remain complete, but contain additional information in the augmented neighborhood structure that may help parameter estimation in practice. This is a phenomenon that we observe empirically in Section 5.3.
3.2 Connection to Stein Scores and Existing Score Matching Techniques
The form of the Concrete score in Eq. 2 suggests natural connection with the Stein score in continuous domains. In the following proposition, we illustrate the connection between the two when define the neighborhood structure to be similar the grid in Figure 1. In particular, as the distance between neighboring nodes shrinks to zero, our Concrete score converges to the Stein score up multiplicative constant.
Proposition 1. For x E RD, p(x) E P(RD), and 8 > 0, let the neighborhood structure N5(x)- = {x + Se; P Then, we have:
cp(x;N6)
lim
V logp(x).
6
We note that while from this perspective the Concrete score can be seen as a finite-difference approximation to the continuous (Stein) score, CSM is different from finite difference score matching (FD-SM) [33]. We introduce a new family of score functions generalizable to discrete domains in the form of (p(x+ v) p(x)) /x(),, where v is the direction from x pointing its neighbor with length ò. On the other hand, FD-SM still attempts to match the Stein score, and approximates directional derivatives with finite difference using two neighbors in the form of log p(x + v) log p(x v). Nevertheless, the differences between the two forms are o0)) as 8 + O.
3.3 Inference with Concrete Scores
To perform inference, note that there exist several ways to define Markov chain Monte Carlo (MCMC) samplers that only rely on the Concrete score-we we highlight the simplest setting of Metropolis-Hastings [35-37] for clarity of exposition. We first note that, by definition:
Pdata (Xan)
Pdata (Xnx) Pdata (x)ta(x)
Cpast (x; M) +
Paatta (x)
This implies that we can obtain the density ratios between the neighboring pairs Pdata /Paca (x)
and Pdata Pxata(x)/Pun (x)/ (Xn,) given the Concrete score. Given a proposal distribution our sampler
will accept the proposed update x' with acceptance probability A(x') x) = min (1, Pdata (x)(x((')g(xxxx)
Paasu (x)o(x'xx
Specifically, we can choose q to sample uniformly among (xx) given a particular x. When the neigh- borhood structure is symmetric, this selection leads to simplified acceptance probability A(x |x)

---

We note that when the underlying graph is connected, the chain is aperiodic (due to the presence of a rejection step), irreducible, and positive recurrent (since there is finite number of discrete states), so the Markov chain is guaranteed to converge in the limit to the model distribution.
min (1. Pdata(x)) (x')
Pdatu(X)
This means that we can also compute tighter bounds on log-like log-likelihood estimates obtained by un- normalized probability models trained via CSM. In particular, we can compute both lower bound estimated via Annealed Importance Sampling (AIS) [38] and a conservative upper bound estimated via the Reverse Annealed Importance Sampling Estimator (RAISE) [39]. This is because both AIS and RAISE allow us to approximate the intractable normalizing constant by constructing sequence of intermediate distributions between our estimated target distribution and another proposal distribution, and we know that the Concrete score can be repurposed to obtain the necessary density ratios between neighboring pairs of distributions along this sequence.
4 Learning Concrete Scores with Concrete Score Matching
4.1 The Concrete Score Matching Objective
Next, under the assumption that A''' induces a weakly connected graph over the support of Pdata (x), we propose new score matching framework called Concrete Score Matching (CSM) for estimating Concrete scores from data samples. To do so, we estimate Cpass (x: with score model co co(::A):
IRD + [x))) where [x(x) denotes the size of the neighborhood of x. Our proposed training objective is quite natural, as it measures the average & difference between score model (+:-:
and the true score Cpana (::NV similar to (continuous) score matching:
(0) Σ Pdata |x [x:)
Cpasta (x;
In the following theorem, we demonstrate that Eq. 4 is indeed a principled learning objective: the estimated 0* is a consistent estimator for the true underlying distribution Pdaza(x) (x).
Theorem 2 (Consistency). In the limit of infinite data and infinite model capacity, the optimal 0* that minimizes Eq. 4 recovers the true Concrete score, or satisfies Ca. ex:xx;)) = Cpaaa (x;
Theorem implies that the estimated (underlying) pg- (x) from cg- (x:N) satisfies pp- (x) (x) Vx E X. Next, we note that Eq. can be simplified to an objective that we can tractably op- timize by removing its dependence on the unknown Crasta (x; similar in spirit to Eq. 1. Although the added flexibility of the score model may potentially lead to situations where does not correspond to valid probability distribution- similar to how continuous score models do not necessarily form conservative vector field-this does not appear to hurt CSM's ' performance empirically.
Theorem 3. Optimizing Equation (4) is equivalent to optimizing:
W(x)
(x
JCSM = Σ Σ
Paata (x) co(x::N) 2co(x;NN;
Σ
Σ
2paata (x..) (x;
T2
(5)
where N(x) = {Xxp. Xny} } the set of neighbors x
We note that in Eq. 5, the objective JeSM (0) can be approximated using Monte Carlo samples. We elaborate on the empirical training details in Section 4.2.
4.2 Efficient Training via Monte Carlo
In practice, Eq. 5 is still inefficient; it involves a summation over all [W(x) neighbors for x, which can be expensive for high-dimensional datasets. Therefore, we propose several modifications to the original training objective that we found to be crucial for scaling up and improving our approach.
We begin with the leftmost term Ti- First, we approximate the outer expectation w.r.t. Praana (x) with Monte Carlo samples from the empirical data distribution. Next, rather than evaluating the objective for all (x)) neighbors, we sample neighbor Xn; uniformly at random among Nxx,) for
5

---

every in a mini-batch. We then upweight the output from the model using this sample by [x We provide the unbiased training algorithm for the leftmost term in Algorithm 1. We note that similar in spirit to sliced score matching [23], an approximation technique to make continuous score matching scalable to higher dimensions.
Next, we turn to the rightmost term J2. Similar to JT we can estimate T2 using an unbiased estimator based on samples as demonstrated Algorithm We define (x') {(x, (x)x: x') as the "reverse neighborhood" set, where an element (x, i) E (x') indicates that x' is the i-th neighbor of x. There could be multiple x with the same in A (x') as the case of the star graph. Computing and storing A as a hash table mapping x to the set of V (x) has time and space complexity of most OeEx [x))) (i.e., the number of edges). For special structures (e.g.. grid), we can design specific algorithms that bypass this process. We provide more details in Appendix C.
Algorithm 1 An unbiased estimator of Ji
Algorithm 2 An unbiased estimator of J2
Input: Pdata: NN, co (model).
Input:
Pdata N,, co (model).
Sample x ~ (x).
1. Sample x' ~ Pdata (x).
2. Sample i ~ Uniform (I... (.....,,,,I(II
2. Sample (x, ~ Uniform(A~1(x)))
Output: [x(x) (co(x:A)) + 2co (x:)..).
Output: 2 I 1/W1(x') co(x;
We leverage the grid structure in experiments, where the neighbors of x defined to be N(x) (x + eu) Algorithm and Algorithm 2 allow us to efficiently train the model by sampling dimension E [D] and flipping the bit for the dth entry of x for each Xx-
4.3 Denoising Concrete Score Matching
Finally, we propose another training objective to approximate Eq. 5, with focus on computational efficiency. Similar to denoising score matching (DSM) for (Stein) score estimation [22], we derive denoising counterpart for Concrete score estimation called "Denoising Concrete Score Matching" (D-CSM). Specifically, given a discrete data distribution Pdata and a discrete noise distribution
x))x)), we define the perturbed data distribution p(x) = Σx Printa (x)]((())( and the posterior
(xx x) Pdata (x) Then, we can show that the Concrete score the perturbed data distribution
p(x)
p(x) can be obtained via Cp(x) NX: = Σx (x()))
This property allows us to obtain
the D-CSM objective, as shown the following theorem:
Theorem (Denoising Concrete Score Matching). The objective:
JD-CSM(0) = Σ Pdata (x)](x(x) (lo(( - (x:11))
(6)
is minimized when co (x; = (8;
We draw a direct analogy to DSM order to provide additional insight into D-CSM. Recall that in DSM, there exists noise distribution x) (i.e. [xxxx, o²l)) such that the magnitude of Stein scores captures the distance between the perturbed & and clean counterpart x. D-CSM enjoys a sim- ilar interpretation. In particular, consider input space E X C zP with the neighborhood structure ((x) = {x + v/v E {-1, 0, 1) If we define q(x x) = ą where k is the Manhattan distance between x and x, then the Conerete score (x;; AN) captures how close x to as measured by the Manhattan distance. Therefore, D-CSM can also be understood through the lens of denoiser. We provide additional experimental results exploring the performance of D-CSM in Appendix B.3.
5 Experimental Results
In this section, we evaluate the performance of CSM on synthetic, tabular, and discrete image datasets on variety of sampling and density estimation tasks. We provide additional details on specific experimental settings and hyperparameter configurations in Appendix C.

---

5.1 Baselines
In our experiments, we compare CSM to two relevant baselines for modeling discrete data: Ratio Matching and Discrete Score Matching with Marginalization (Discrete Marginalization For conciseness, we provide additional details and derivations for their training objectives in Appendix D.
Ratio Matching, Similar to score matching. Ratio Matching [34] leverages the fact that ratios of probabilities are independent of the intractable normalizing constant (due to cancellation). The method then seeks to match the ground truth density ratios (rista(()) go(x) where x-d denotes go
(ásts(X_aa)
the vector x with the dth entry bit-flipped (e.g. from O to 1).
Discrete Score Matching with Marginalization (Discrete Marginalization). The Discrete Marginal- ization baseline is another way of estimating discrete probability distributions with score matching as in [34]. However, note that this approach is difficult to scale because it requires us marginalize over the data dimension, which may also cause instabilities during training.
5.2 1-D Discrete Data
In this experiment, we consider a 16-category 1-D data distribution as shown in Figure 2. We parameterize our Concrete score model ep NX) using a shallow MI.P model with Tanh activations, and use the Cycle neighhorhood structure during training. We demonstrate that the learned Concrete score model can faithfully capture the true data distribution when trained with CSM. As shown on the left side of Figure 2, we find that CSM generates samples (blue) using MH that almost perfectly matches the samples drawn from Pdeta (x) (green).
We also observe in Appendix A.3 that the Concrete score on (x) can recover the Stein score of a data distribution perturbed with triangular noise. Even though the Concrete score model is trained on discrete data (green), this connection allows us to sample with Langevin dynamics using the recovered Stein score. On the right side of Figure 2, we show how the samples generated using Langevin dynamics (smoothed orange) closely match the triangular noise-perturbed data distribution (gray). Then, we leverage a closed-form denoising formula for the perturbed distribution (Appendix A.3) to recover the clean data distribution (green) from samples obtained via Langevin dynamics (smoothed orange). The resulting denoised samples (orange) are labeled as Denoised in Figure more details and discussion in Appendix A.3.
We provide
Data
MH samples
Triangular noise
Perturbed data
Langevin samples
Denoised
Sampling results from toy I-D discrete dataset. CSM recovers the true data distribution Pdata(X) (x) using Metsopolis-Hastings (left). The Concrete score can also be used to recover the Stein score of the triangular noise- noise-pertune perturbed data distribution, allowing for sampling with Langevin dynamics. Such samples can be denoised recover the original (clean) data distribution (right).
Figure 2:
5.3 Sampling with Toy 2-D Multi-Class Datasets
Next, we consider three 2-D toy benchmark datasets with multiple modes and discontinuities as commonly used in the density estimation literature [40, 41J. We quantize the data into 91 x 91 bins to obtain the discrete training data for the experiment (see Figure 3). We compare our method against the two basclines: (1) Ratio Matching [42]; and (2) Discrete Marginalization [34]. In particular, found that the original equations in [34] were incorrect, and provide results using the correct training objectives (denoted as Ratio-f fixed and Marginal -f fieed) in Figure 3. We provide step-by-step derivation addressing this issue with the correct expressions for the training objectives in Appendix D.
For fair comparison, we use the same model architecture and training configurations across all methods. We use the grid neighborhood structure for training CSM. As shown in Figure 3, the samples from CSM best capture the shape of the underlying data distributions across all three datasets (leftmost column). Baselines implemented using the original equations in [34] indeed demonstrate poor performance the density estimation task (Ratio and Marginal columns) in Figure 3.
7

---

Data
Ratio
Ratio-fixed
Marginal
Marginal-fixxt
CSM (Ours)
Figure 3: Sampling results on toy 2-D benchmark datasets. We find that CSM produces the highest quality samples across all 3 datasets relative to all baselines.
Datasets
Ratio Matching (1)
Discrete Marginalization
CSM (Ours) (1)
NLTCS
-6.15
-6.21
-6.13
Plants
-19.03
-14.02
Jester
-6.449
-57.06
-54.91
Amazon Diaper
-10699
-42.52
-11.13
Amazon Feeding
-12.09
-35.96
-12.65
Amazon Gifts
-4.57
-4.28
-4.22
Amazon Media
-10.22
-13.77
-10.30
Amazon Toys
-9.83
-16.34
-9.30
Table I: Log-likelilneee demonstrates good performance, almost always outperforming or performing comparably relative to the Ratio Matching and Discrete Marginalizate ization baselines.
likelihood comparisons on discrete tabular datasets. Higher is better. We find that CSM
5.4 Likelihood Evaluation Discrete Tabular Data
then evaluate the performance of CSM on density estimation tasks a wide range of tabular (discrete) datasets drawn from both the Twenty Datasets [43] and the Amazon Baby Registries benchmarks [44]. In order to evaluate likelihoods, we directly parameterize the density with discrete autoregressive model (MADE [45]). but train the model using the baseline approaches and CSM. For a fair comparison, we use the same model architecture and experimental configurations previous experiments,
across all methods. Similar training CSM. As shown in Table I, our approach (CSM) demonstrates favorable performance relative the Ratio Matching and Discrete Marginalizat baselines. We provide additional experimental results in Appendix B.1 and more experimental details in Appendix C.
the grid neighborhood structure for
5.5 Generative Modeling with High-dimensional Images
For our final experiment, we demonstrate that we can scale CSM achieve good performance on complex, high-dimensional binarized image datsets. We experiment with the MNIST [46] dataset, which has 784 dimensions. We directly parameterize the Concrete score function with U-Net [47], and train the model using the CSM based on a grid neighborhood structure. Similar to [26]. we perturb the image with different levels of discrete (Categorical) noise, and train the models at different noise levels with annealing. After the Concrete score model is trained, we sample from the model using Metropolis-Hasting
as discussed in Section 3.3 and follow similar sample initialization process as [26]. We provide more details in Appendix C. We present the samples from our model in Figure 4b. We observe that our CSM approach with Metropolis- that look similar to the digit examples in the training set (Figure 4a).
is able generate samples

---

8
7
9
3
/
9
6 O
2
7 2
R
1
/
7
5
5
(
0
4
6
0
9
4
4 9
9
4
4
3
/
8
5 7 /
4
7
6
6
P
6
4
3
9
7
0
8
5
0
7
4
O
2 1
7
7
1
7
7
7
0
[ 7
0
8
3
0
2
4
0 4 4 6 43
9 7 2 /
3
V 4
8 7
8
7
6
2
1
6
1
> 3
5
a
!
3
9
9
9
3
/ 5 4
7 d
(
5
2 7
8 7 6
1
A
2
2
6
2
/
2
9 [
1 1
7
8
9
8
3
2
6
7
6
0
6
8 4 8
6 3
6 7
8
7
6
(a) Binary training images
MNIST samples (MH)
Figure 4: Image samples from CSM on the binarized MNIST dataset. We observe that CSM is able generate high-quality samples on MNIST using
Related Work
Score Matching. Our work builds on the body of literature on score matching [21, 22] and score- based generative modeling [23, 26, 16]. Notably, we build upon the generalization of score matching to discrete data [42, 48, 34]. Our score function can be viewed through the lens of generalized score matching in [34]. where the Concrete score serves particular instantiation of the linear operator their framework. However, we provide novel perspective terms of constructing the Concrete score via surrogate gradient information over structured discrete space, and provide efficient training objectives for CSM. Our work also closely related to score matching with finite difference (FD-SM) [33] as discussed in Section 3.2. However, rather than approximating the gradient with finite differences for continuous data, we leverage the first-order forward difference to construct our Concrete score function in discrete domains. In addition, CSM bears similarities concurrent work on scaling up Ratio Matching [34] for discrete energy-based models (EBMs) [49] called RMwGGIS our approach can be viewed different way to train discrete EBMs (via the Concrete score).
Generative Modeling for Discrete Data. CSM also provides another way to train generative models for discrete data. A related work is [50], which trains score-based model on distributions over graphs. However, they perturb the adjacency matrices with Gaussian noise and use the continuous variant of DSM. Although there exist several model families for learning binary and Categorical probability distributions such as normalizing flows [51-53], Product Networks (SPNs) 55], denoising diffusion probabilistic models [56], discrete (latent) [57, 58] EBMs [49], and Generative Flow Networks (GFNs) [59], there does not yet exist a discrete score-based model that can scale to high-dimensional discrete datasets. Finally, our approach bears similarities with Gibbs with Gradients (GWG) [60]. In particular, GWG augments existing MCMC samplers with gradient information by leveraging local structure estimate likelihood ratios for transitioning to the next state. However, GWG utilizes gradients from the probability mass functions of the underlying discrete distributions, in contrast to the way in which we construct the Concrete score function.
7 Conclusion
We introduced Concrete Score Matching (CSM), a novel framework for learning discrete probability distributions via score matching. We proposed to leverage particular kinds of structural information in the data to construct surrogate gradient information about the discrete space, and used this to define valid score function. We also introduced several modifications the original training objective that allowed CSM to scale gracefully to high-dimensional datasets, and demonstrated that CSM performs well on variety of sampling and density estimation tasks.
However, this work is not without limitations. Since CSM depends on the neighborhood structure, certain types of graphs may work better for score matching in practice than others. Additionally, our efficient training objectives may suffer from high variance when scaling to high dimensions for particular kinds of neighborhood-induce graphs, such as the Star graph. For future work, although we fixed the number of neighbors K for each x in our experiments, it would be interesting to adaptively determine the optimal number of neighbors to use for each during training. We also

---

believe that CSM can be generalized to leverage more complex neighborhood structures than those we explored in the paper. Additionally, empirically investigating the performance of D-CSM with Langevin dynamics relative to CSM would be interesting future work.
Broader Impact. This work introduces a novel score function the Concrete score- worre-hhtt is defined over discrete spaces, as well as corresponding score matching (CSM) framework that scale to high-dimensional discrete datasets. This leads to empirical performance improvements over a range of density estimation and sampling tasks, and does not have direct consequence societal issues, However, we note that CSM could serve as the basis for developing more powerful generative models of structured, discrete data. Although this could lead to tangible benefits (e.g. improved generative modeling of text data), we should be mindful to take the usual precautions required for generative modeling research (e.g. against the development of deepfakes).
Acknowledgements and Funding Disclosure
We thank the anonymous reviewers for insightful discussions and feedback. KC is supported by the Qualcomm Innovation Fellowship and the Two Sigma Diversity PhD Fellowship. This research was supported by NSF (#1651565), AFOSR (FA95501910024), ARO (W911NF-21-100125) ONR, DOE, CZ Biohub, and Sloan Fellowship.
References
[1] Diederik P Kingma and Max Welling, Auto-encoding variational bayes. arXiv preprint 13Xiv: 2013.
[2] Danilo Jimenez Rezende. Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. In International conference on machine learning, pages 1278-1286. PMLR, 2014.
[3] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick. Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. ICLR, 2016.
[4] Aaron Van Den Oord, Oriol Vinyals, et al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
[5] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International conference machine learning, pages 1530-1538. PMLR, 2015.
[6] Aaron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, et al. Con- ditional image generation with pixelenn decoders. Advances in neural information processing systems, 29, 2016.
[7] Durk P Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, llya Sutskever, and Max Welling. Improved variational inference with inverse autoregressive flow. Advances in neural information processing systems, 29, 2016.
[8] George Papamakarios, Theo Pavlakou, and lain Murray. Masked autoregressive flow for density estimation. Advances in neural information processing systems, 30, 2017.
[9] Chenlin Meng, Lingi Zhou, Kristy Choi, Tri Dao, and Stefano Ermon. Butterflyflow: Building invertible layers with butterfly matrices. In International Conference on Machine Learning, pages 15360-15375 PMLR, 2022.
[10] Chenlin Meng, Yang Song, Jiaming Song, and Stefano Ermon. Gaussianization flows. In International Conference on Artificial Intelligence and Statistics, pages 4336-4345. PMLR, 2020.
[11] Durk Kingma and Prafulla Dhariwal. Glow: Advances in neural information processing systems, 31, 2018.
Generative flow with invertible 1x1 convolutions.
10

---

[12] Jonathan Ho. Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel. Flow++: Improving flow-based generative models with variational dequantization and architecture design. In International Conference on Machine Learning, pages 7720-2730. PMLR, 2019.
[13] Yang Song, Chenlin Meng, and Stefano Ermon. Mintnet: Building invertible neural networks with masked convolutions. Advances in Neural Information Processing Systems, 32, 2019.
[14] Jascha Sohl-Dicke Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pages 2256- 2265.. PMLR. 2015.
[15] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
[16] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.134555 2020.
[17] Ian Goodfellow, Jean Pouget-Abadie, Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[18] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR, 2017.
[19] Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
[20] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401-4410, 2019.
[21] Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
[22] Pascal Vincent. connection between score matching and denoising autoencoders. Neural computation, 2367):1661-1674, 2011.
[23] Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pages 574 584. PMLR, 2020.
[24] Chenlin Meng, Yang Song, Wenzhe Li, and Stefano Ermon. Estimating high order gradients of the data distribution by denoising. Advances in Neural Information Processing Systems, 34:25359-25369, 2021.
[25] Chenlin Meng. Lantao Yu, Yang Song. Jiaming Song, and Stefano Ermon. Autoregressive score matching. Advances in Neural Information Processing Systems, 33:6673-6683, 2020.
[26] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances Neural Information Processing Systems, 32, 2019.
[27] Chenlin Meng, Yutong He, Yang Song, Jiaming Song, Jiajun Wu, Jun-Yan Yan Zhu, and Stefano Ermon. Sdedit: Guided image synthesis and editing with stochastic differential equations. In International Conference on Learning Representations, 2021.
[28] Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan. Wavegrad: Estimating gradients for waveform generation. arXiv preprint 2rXiv:2009.00713 2020.
[29] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao and Bryan Catanzaro. Diffwave: versatile diffusion model for audio synthesis. arXiv preprint arXiv:2009.0976) 2020.

---

[30] Ronald L Graham, Donald E Knuth, Oren Patashnik, and Stanley Liu. Concrete mathematics: foundation for computer science. Computers in Physics, 3(5):106- 107, 1989.
[31] John Skilling. The eigenvalues of mega-dimensional matrices. In Maximum Entropy and Bayesian Methods, pages 455 466. Springer, 1989.
[32] Michael F Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics- -Simuiltiin and Computation, 18(3): 1076, 1989.
[33] Tianyu Pang. Kun Xu, Chongxuan Li, Yang Song, Stefano Ermon, and Jun Zhu. Efficient learn- ing of generative models via finite-difference score matching. Advances Neural Information Processing Systems, 33:19175-1918 2020.
[34] Siwei Lyu. Interpretation and generalization of score matching, arXiv preprint arxiv: 1205.262,,, 2012.
[35] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087-109) 1953.
[36] W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 1970.
[37] Siddhartha Chib and Edward Greenberg, Understanding the metropolis algorithm. The american statistician, 49(4)3327-335, 1995.
[38] Radford M Neal. Annealed importance sampling. Statistics and computing, 11(2):125-139) 2001.
[39] Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Accurate and conservative estimates of mrf log-likelihood using reverse annealing. Artificial Intelligence and Statistics, pages 102-110. PMLR, 2015.
[40] Will Grathwohl, Ricky TQ Chen, Jesse Bettencourt, llya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint 180.013810.01366, 2018.
[41] Nicola De Cao, Wilker Aziz, and Ivan Titov. Block neural autoregressive flow. In Uncertainty artificial intelligence, pages 1263-1273. PMLR, 2020.
[42] Aapo Hyvarinen. Connections between score matching, contrastive divergence, and pseudolikeli- hood for continuous-valued variables. IEEE Transactions on neural networks, 18(5):129-15311 2007.
[43] Jan Van Haaren and Jesse Davis. Markov network structure learning: A randomized feature generation approach. In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
[44] Jennifer A Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar. Expectation-maxiiizze for learning determinantal point processes. Advances in Neural Information Processing Systems,
27, 2014.
[45] Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. Made:
Masked autoencoder for distribution estimation. In International Conference on Machine Learning, pages 88 181-889 PMLR, 2015.
[46] Yann LeCun. The mnist database of handwritten digits. hilp://yann. lecun, com/exab/mnist// 1998.
[47] Olaf Ronneherger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference Medical image computing and computer-assisted intervention, pages 234-241. Springer, 2015.
[48] Aapo Hyvärinen. Some extensions of score matching. Computational statistics data analysis, 51(5):2449-255 2512, 2007.
12

---

[49] Meng Liu. Haoran Liu, and Shuiwang Ji. Gradient-guide importance sampling for learning discrete energy- based models. arxiv, 2021.
[50] Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics, pages 4474 4484. PMLR, 2020.
[51] Zachary Ziegler and Alexander Rush. Latent normalizing flows for discrete sequences. In International Conference Machine Learning, pages 7673-7682. PMLR, 2019.
[52] Dustin Tran, Keyon Vafa, Kumar Agrawal, Laurent Dinh, and Ben Poole. Discrete flows: Invertible generative models of discrete data. Advances in Neural Information Processing Systems, 32, 2019.
[53] Emiel Hoogehoom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34, 2021.
[54] Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference Computer Vision Workshops (ICCV Workshops), pages 689-690, IEEE, 2011.
[55] Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Pranav Subramani, Nicola Di Mauro, Pascal Poupart, and Kristian Kersting. Spflow: An easy and extensible library for deep probabilistic learning using sum-product networks, 2019.
[56] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:1 19911 14:11791-1799 119993, 2021.
[57] Fan Bao, Chongxuan Li, Kun Xu, Hang Su, Jun Zhu, and Bo Zhang. Bi-level score matching for learning energy-based latent variable models. Advances in Neural Information Processing Systems, 33:18110-18111111111111111111111 2020.
[58] Fan Bao, Kun Xu, Chongxuan Li, Lanqing Hong, Jun Zhu, and Bo Zhang. Variational (gradient) estimate of the score function energy-based latent variable models. In International Conference Machine Learning, pages 651 1-1-661 PMLR, 2021.
[59] Dinghuai Zhang, Nikolay Malkin, Zhen Liu, Alexandra Volokhova, Aaron Courville, and Yoshua Bengio. Generative flow networks for discrete probabilistic modeling. arXiv preprint 36.,, 2022.
[60] Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. Oops i took gradient: Scalable sampling for discrete distributions. In International Conference on Machine Learning, pages 3831-3841, PMLR, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Section 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Sections 3-4.1
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [No] We will release the code publicly upon publication.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Section and Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] Appendix C
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Section 5
(b) Did you mention the license of the assets? [No] We only used publicly available datasets for our experiments.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "nOb1GIZsIwj", "reviewer": "Reviewer_oRLC", "summary": "This work presents concrete score matching which generalizes score matching to discrete distributions. This is not the first work to attempt to generalize score matching to discrete domains. Lyu 2012, does this first, but defines a discrete ''score'' using the dimension-wise marginals of each dimension in the input. Conversely, here the ''score'' is created by defining a graph over states in the support of the distribution. The score is defined as the likelihood ratio between neighboring states in this graph. The authors provide sufficient conditions to ensure that learning the concrete score is equivalent to learning the desired distribution. This setup is more flexible than prior generalizations and can be applied to inputs which cannot be embedded into {1, ..., k}^D.\n\nThe authors present two learning methods taking advantage of the concrete score; concrete score matching and denoising concrete score matching -- generalizations of score matching and denoising score matching respectively. As well, they present an efficient training procedure for both and an MCMC sampling procedure which utilizes the concrete scores.\n\nThey present experimental results on some toy discrete distributions, non-toy discrete distributions and binary MNIST. The presented results in dictate that CSM performs favorably. ", "questions": "While I enjoyed the work, I am left with quite a few questions.\n\nNeighborhood structure: I know you mention that the neighborhood structure should be an important design choice. This makes sense. Did you perform any ablations on this? It would be really nice to see a likelihood based experiment like the section 5.4 using different neighborhoods. This would give the reader some intuition on how this should be chosen.\n\nSection 5.4: I like that you used a normalized model to test these various approaches. This enables likelihood based evaluation which you used. I was somewhat curious as to why there was no maximum likelihood baseline presented in the table. I think this should be put in the table. No one would ever expect a method like this (which does not require a normalized model) to outperform ML training but it can provide a good ceiling on the performance of a model under ideal circumstances. This would greatly improve the impact of these results. \n\nEfficient Training: In section 4.2 you present an efficient training scheme where you sample neighbors in the graph uniformly. Have you considered using a gradient-based importance sample scheme as in [1, 2]? I know that may be outside the scope of the work but I think it could be a nice extension that would be worth noting on here. \n\nDenoising concrete score matching: I like that you propose two learning methods for the concrete score. Unfortunately it seems that you present no experiments using this method. It would be nice to present some result (even a toy result) indicating that this method, in practice, can be used to train a model.\n\nEvaluation: Have you considered using something like AIS or RAISE to evaluate these models? I don't see why you couldn't do that to provide a bound on log-probability for your MNIST models, for example. Even if you don't present these results, it might be nice to add a note in section 3.3\n\n[1] https://openreview.net/pdf?id=IEKL-OihqX0\n[2] https://arxiv.org/abs/2102.04509", "limitations": "Yes, I believe the authors have adequately addressed the limitations of their work. \n", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nI enjoyed reading this paper. I think the method is an elegant generalization of score matching and synthesizes prior attempts to generalize score matching to discrete domains. The method makes sense, is easy to understand, and seems to be well justified. The paper is not bogged down with unnecessary theory, but the theory presented is useful in helping the reader build understanding and intuition about the method.\n\nThe experimental results in the paper were nice. I liked the use of the MADE model for section 4.2 although I have some thoughts that I will elaborate on in the next section. The MNIST results are also quite nice. It is very difficult (even on MNIST) to obtain such nice results using (non-de noising) score matching, so I was quite impressed. \n\n\nWeaknesses:\n\nI think the main weaknesses with the paper are in the empirical study of the method. I think there are a number of simple things that could have been done which would have greatly improved this. For example, there could have been a study of the impact of the choice of neighborhood structure. As well, there could have been a maximum likelihood baseline presented in section 5.4. Further, while denoising concrete score matching was presented, there were no empirical results shown. All of these things could have pretty easily been added and would have greatly improved the quality of the results section.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kiaTju5XzNc", "reviewer": "Reviewer_rPQu", "summary": "This paper proposes a discrete counterpart to continuous score\nmatching. The main idea is to build a neighboring graph for each point\nand replace the gradient of the log-likelihood with a vector\ncontaining the likelihood ratios between a datapoint and its\nneighbors. This vector is called the concrete score. The paper\nproposes a training scheme to learn the concrete score from data, and\nshows that in the limit of infinite data and infinite capacity the\nmodel can recover the true data likelihood. An efficient\nimplementation is demonstrated empirically on simple discrete datasets.\n", "questions": "Please see the weaknesses points above.", "limitations": "The authors do mention the limitations in scaling to higher dimensions and larger datasets. I agree this is the main limitation and the paper could be improved by conveying a better understanding of what these limits are in practice. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The paper is well written and the ideas are clearly explained.\n2) The proposed concrete score is simple and elegantly converges to the\n  Stein score in the limit of neighboring graph shrinking.\n3) The paper derives a training objective that is in the same spirit as\n  in continuous score matching.\n\nWeaknesses:\n\n1) I found the paper dedicates very little attention to how the\n   neighborhoods are actually built in practice for the different\n   datasets. In particular for the high-dimensional datasets, this\n   seems to be a crucial aspect of the method that was disregarded\n   (unless I missed something).\n2) The method has scaling issues for high-dimensional data and large\n  datasets. Theorem 1 requires a fully connected graph which is\n  impractical for large datasets, and the approximated loss will\n  certainly suffer from high variance. Although the authors mentioned\n  this, it is not entirely clear what are the practical limitations\n  for scaling up.\n3) The experimental evaluation is limited. The paper only compares to\n   two baseline methods. The gains do not seem significant, and the performance\n   comparison was limited to log-likelihood, without taking efficiency into account. These\n   baseline methods were unknown to me, and I felt more detail was\n   required to understand what is being compared to.  I wonder how the method would compare to other\n   discrete generative models such as D3PM [Austin et al.], [43], to\n   name a few, and in particular the very related method of finite\n   differences FSDM [27].\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Gco6951Y9lI", "reviewer": "Reviewer_PXyS", "summary": "This paper proposes a comprehensive framework of score matching on discrete data. The papers proposes a clever surrogate of the score function, and proves its completeness for practical usage. After establishing the concrete score, this paper proposes the concrete score matching to estimate it, as well as a denoising version. To leverage the concrete score, this paper also proposes a MCMC algorithm to sample based on the score. Experiments show effectiveness of the concrete score matching.", "questions": " ", "limitations": " ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe author carefully extends the score matching to discrete data. This extension finds counterparts of continuous score matching in both theory (i.e., the completeness), training (i.e., concrete score match and its denoising version), inference (i.e., MCMC). It also allows directly estimate the concrete score, instead of the probability mass function. It seems many benefits in the continuous score matching also exist in the concrete score matching.\n\nWeakness \\& Questions:\n\n1. Why $J_1$ requires Monte Carlo on $i$? It seems that the summation on $i$ can be directly calculated, since $c_\\theta(x; N)$ is the output of the neural network, and simply summing each dimension of the (square of) output is exactly the summation on $i$.\n\n2. In Line 221, the author claims that the concrete score $c_{\\tilde{p}}(\\tilde{x}; N)$ captures how close $\\tilde{x}$ is to x. However, the concrete score is only related to $\\tilde{x}$? How to understand the closeness?\n\n3. Does the concrete score of $\\tilde{q}(\\tilde{x}|x)$ have a closed form expression as the continuous case?\n\n4. Is the neighbor in L 203 and L 220 suitable choices? Since $|N(x)|$ = $2^D$ and $3^D$ respectively, which are too large to model using a neural network when $D$ is large.\n\n5. The author also uses annealed noise as [21]. Is the concrete score matching able to scale up to more complex data as [21]? For example, CIFAR10 and ImageNet. If not, what is the gap between this work and [21]? \n\n6. Missing related works on score matching: [1*] and [2*] are related works, which also enlarge the scope of score matching.\n\n[1*] Bao et al., Bi-level score matching for learning energy-based latent variable models\n\n[2*] Bao et al., Variational (gradient) estimate of the score function in energy-based latent variable models", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept