Source-linked AI summary
Concrete Score Matching: Generalized Score Matching for Discrete Data
Chenlin Meng, Kristy Choi, Jiaming Song, Stefano Ermon
TL;DR
Score matching works well for continuous data but cannot directly apply to discrete domains because gradients are undefined. This paper introduces the Concrete score and Concrete Score Matching, using neighborhood-based directional changes and efficient objectives, and reports favorable performance across diverse density-estimation tasks.
Problem
Score matching cannot directly model discrete data because its gradient-based representation requires a continuous domain and differentiable density.
Method
The paper defines the Concrete score from local directional probability changes over a predefined neighborhood structure and learns it with Concrete Score Matching and efficient high-dimensional training objectives.
Results
CSM performs favorably relative to existing baselines across synthetic, tabular, and high-dimensional image density-estimation tasks.
Takeaways & Limitations
The Concrete score provides a score-based framework for extending density estimation from continuous data to discrete domains.
Takeaways & Limitations
CSM depends on the neighborhood structure, and its efficient objectives may have high variance for some high-dimensional neighborhood-induced graphs such as the Star graph.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends score-based modeling to discrete data, where gradients are undefined, by introducing the Concrete score and Concrete Score Matching (CSM). It connects distance-based changes to continuous and discrete score functions and reports favorable performance across diverse density-estimation tasks.
- Motivation: Existing score matching is designed for continuous data because discrete domains lack a defined gradient.This limits direct use of score-based generative modeling for structured discrete data such as graphs, text, genomic sequences, and images.
- Concrete score: The Concrete score generalizes the (Stein) score to continuous and discrete data by using local directional changes within a predefined neighborhood structure.It constructs surrogate gradient information from similarities between neighboring examples.
- Concrete score: Euclidean distance recovers the (Stein) score in continuous domains, whereas Manhattan distance yields the novel score function for discrete domains.The distance determines how directional probability changes are measured.
- Empirical evaluation: CSM performs favorably relative to existing baselines across synthetic, tabular, and high-dimensional image density-estimation tasks.The reported evaluation spans a mixture of dataset types and density-estimation settings.
- Learning framework: Concrete Score Matching (CSM) learns Concrete scores from samples and connects the framework to existing continuous score matching methods such as denoising score matching.The framework is designed to transfer score-matching ideas into discrete settings.
- Scalability: Efficient training objectives allow CSM to scale to high-dimensional datasets and support adaptations of continuous score-matching successes for discrete domains.The paper proposes efficient objectives and approach variations intended to improve practical performance.
2 Preliminaries
The preliminaries define score matching as learning a model whose score approximates the data score, but identify continuity and differentiability requirements that fail for discrete data. They also note that conventional objectives can involve expensive trace-term computation.
- Continuous score matching: The (Stein) score is the gradient of the log data density, and score matching learns an unnormalized model whose score approximates it.The data distribution is accessed through independent samples, while the learned score is derived from the model density.
- Continuous score matching: Integration by parts converts the original Fisher-divergence objective into a sample-based objective involving the score network and a matrix-trace term.This removes direct dependence on the unknown ground-truth data scores.
- Computational cost: The trace term remains problematic because it requires expensive evaluation of the log-density Hessian.The paper notes trace estimators and directional derivatives as ways to approximate the training objective efficiently.
- Limits for discrete data: Existing score matching requires a continuous domain and a differentiable density, requirements that fail in discrete domains.These limitations prevent direct application of standard score matching to discrete data.
3 The Concrete Score
The Concrete score uses local directional probability changes over a predefined neighborhood structure to provide a surrogate gradient for discrete data. It is complete when the neighborhood-induced graph is connected, and connects to the continuous Stein score as neighbor distances shrink.
- Constructing surrogate gradients: The Concrete score constructs surrogate gradient information from local directional probability changes among neighboring examples.The neighborhood structure induces a directed graph over the data support, and the score records rates of probability change along those local directions.
- Constructing surrogate gradients: The neighborhood-induced graph adds directed edges from each input to every member of its neighborhood, and the neighborhood relation may be asymmetric.A neighbor relationship in one direction does not necessarily imply the reverse relationship.
- Completeness: Connectedness is the key graph condition supporting completeness of the Concrete score.Theorem 1 states that matching Concrete scores recovers the data distribution when the induced graph is connected; extra edges preserve completeness and may help parameter estimation.
- Connection to Stein scores: The Concrete score recovers the continuous Stein score up to a multiplicative constant as neighboring distances approach zero.This establishes a finite-difference connection to continuous score matching, while CSM remains distinct from finite difference score matching.
- Inference: Concrete scores provide neighboring density ratios that can support Metropolis-Hastings sampling.For a connected underlying graph, the resulting chain is aperiodic, irreducible, and positive recurrent, so it converges in the limit to the model distribution.
4 Learning Concrete Scores with Concrete Score Matching
Concrete Score Matching learns Concrete scores by minimizing a score-matching objective under a weakly connected neighborhood graph. Efficient neighbor sampling and a denoising objective are introduced to make training tractable and scalable to high-dimensional discrete data.
- The Concrete Score Matching Objective: CSM estimates the data Concrete score with a parameterized score model under a weakly connected neighborhood graph.Its training objective measures the average squared difference between the learned and true Concrete scores.
- The Concrete Score Matching Objective: With infinite data and model capacity, the optimal CSM model recovers the true Concrete score and therefore the underlying data distribution.The consistency result follows from combining Theorem 2 with the completeness result for connected neighborhood-induced graphs.
- The Concrete Score Matching Objective: The tractable CSM objective removes dependence on the unknown data Concrete score and can be approximated with Monte Carlo samples.The resulting objective is equivalent to the original score-matching objective and is optimized using empirical samples.
- Scaling the objective: Neighbor summation is costly in high dimensions, so unbiased estimators sample neighbors and reverse-neighborhood entries instead of evaluating every edge.Reverse neighborhoods can be stored with time and space complexity at most O(∑_x |N(x)|), the number of graph edges.
- Denoising Concrete Score Matching: Denoising Concrete Score Matching derives a computationally focused objective from a discrete perturbation distribution and posterior.The perturbed-distribution Concrete score is expressed as an expectation involving the conditional-noise Concrete score and the posterior over clean inputs.
5 Experimental Results
The experiments evaluate CSM across synthetic, tabular, and high-dimensional image data using sampling and density estimation tasks. CSM recovers toy distributions, produces high-quality samples, and generally matches or outperforms the discrete-data baselines.
- 1-D discrete data: CSM nearly perfectly matches the true 16-category 1-D distribution when generating samples with Metropolis-Hastings.The learned Concrete score model faithfully captures the data distribution.
- 1-D discrete data: The Concrete score recovers the Stein score of triangular-noise-perturbed data, enabling Langevin sampling and subsequent denoising toward the clean distribution.Langevin samples closely match the perturbed distribution before closed-form denoising is applied.
- Tabular datasets: CSM demonstrates good log-likelihood performance on discrete tabular datasets, almost always outperforming or matching Ratio Matching and Discrete Marginalization.The comparisons use datasets from the Twenty Datasets and Amazon Baby Registries benchmarks.
- 2-D toy datasets: CSM produces the highest-quality samples across all three toy 2-D benchmark datasets relative to the baselines.With a shared architecture and training configuration, CSM best captures the underlying distribution shapes.
- High-dimensional images: CSM scales to 784-dimensional binarized MNIST and generates samples resembling training-set digits using Metropolis-Hastings.The model uses a U-Net Concrete score function with a grid neighborhood structure and annealed categorical noise.
6 Related Work
CSM extends score-matching ideas to discrete generative modeling while relating the Concrete score to generalized score matching and other discrete-data approaches. The paper positions CSM as an alternative framework for learning discrete probability distributions.
- Score matching: The Concrete score is viewed as a particular linear-operator instantiation within generalized score matching.The paper presents a novel perspective based on constructing the Concrete score from neighborhood structure.
- Generative modeling for discrete data: CSM offers another approach for training generative models on discrete data alongside existing discrete score-based and probability-modeling methods.Related approaches include graph score models, normalizing flows, and Sum-Product Networks.
7 Conclusion
The paper introduces CSM as a framework for learning discrete probability distributions through a valid Concrete score built from structural information. Training-objective modifications support high-dimensional datasets, and experiments show strong performance across sampling and density-estimation tasks.
- Conclusion: CSM learns discrete probability distributions through score matching using the Concrete score.The Concrete score supplies surrogate gradient information over discrete spaces.
- Conclusion: Structural information in the data is used to construct surrogate gradient information and define a valid score function over discrete spaces.This is the central construction underlying the framework.
- Conclusion: Modified training objectives allow CSM to scale gracefully to high-dimensional datasets.The paper reports this scaling property as part of the framework's contribution.
- Conclusion: CSM performs well across a variety of sampling and density-estimation tasks.The conclusion summarizes the empirical results across the paper's datasets and tasks.
- Limitations: CSM depends on neighborhood structure, and some neighborhood-induced graphs may produce high-variance efficient objectives at high dimensions.The paper specifically identifies Star graphs as an example and suggests adaptively selecting neighbor counts as future work.
Checklist
The checklist records that the paper discusses its contributions, limitations, societal impacts, theoretical assumptions and proofs, and experimental details. It also notes several reproducibility and asset-documentation omissions.
- Checklist: The authors report discussing the work's limitations and potential negative societal impacts.Both items are marked Yes in the checklist, with the limitations discussion identified as Section 7.
- Checklist: The authors report stating assumptions for theoretical results and including complete proofs in Sections 3–4.1 and Appendix A.The checklist marks both theoretical documentation items Yes.
- Checklist: The paper reports training details and compute resources, but not error bars from repeated experiments.The checklist marks training details and compute reporting Yes, while error bars are marked No.
- Checklist: The authors state that code will be released publicly upon publication rather than providing it with the submission.The checklist marks current code, data, and reproduction instructions as unavailable and notes the planned release.
- Checklist: The paper cites existing assets but does not report their licenses, while using publicly available datasets.The checklist marks asset citation Yes and license documentation No.
A.1 Concrete Score Matching
Concrete Score Matching learns a discrete analogue of the score by matching Concrete scores, with consistency and completeness under connected neighborhood graphs. Its denoising formulation connects discrete score estimation to perturbed continuous score recovery and sampling.
- Completeness: A connected neighborhood-induced graph makes the Concrete score complete: matching the learned and data Concrete scores implies matching the underlying distributions.Density ratios propagate along graph paths, uniquely identifying the distribution.
- Consistency: With infinite data and model capacity, the optimal CSM objective recovers the true Concrete score.
- Denoising CSM: Denoising Concrete Score Matching provides an objective based on perturbed data and posterior relationships.Theorem 4 identifies the denoising objective; the associated posterior can be computed from density ratios when the neighborhood graph is connected.
- Connection to Stein scores: For triangularly perturbed discrete data, Concrete scores recover the Stein score of the perturbed distribution, enabling Langevin sampling followed by closed-form denoising.The recovered Stein score is constructed from density ratios, and the posterior supports denoising.
- Continuous connection: A forward-difference neighborhood in continuous space makes the scaled Concrete score approximate the directional derivative and recover the Stein score.
- Evaluation context: Maximum-likelihood training serves as an upper-bound comparison, while log-likelihood and score-matching losses need not correlate under practical constraints.
B.2 Neighborhood Structure Specification in Practice
Neighborhood choice is theoretically broad but practically data-dependent: structures can perform similarly on smooth distributions yet differ sharply around low-density regions. D-CSM can match perturbed targets across noise levels, while scaling and structure selection remain practical concerns.
- General considerations: Any neighborhood structure is theoretically valid when its induced graph is connected, but practical performance depends on optimization and model specification.
- Tabular evaluation: On discrete tabular datasets, CSM almost always outperforms or performs comparably to Ratio Matching and Discrete Marginalization by log-likelihood.
- No low-density regions: On a 1-D distribution without low-density regions, four neighborhood structures achieve similar log-likelihoods under CSM.
- Low-density regions: In a 1-D distribution with low-density regions, the complete graph in Case 2 outperforms the other structures, while Case 3 remains comparable to Case 2.
- Data dependence: The best-performing neighborhood is often data-dependent, and noise annealing followed by denoising CSM is proposed as future work for poorly chosen structures.
- D-CSM: D-CSM samples match ground-truth perturbed samples across noise levels, indicating practical effectiveness on the evaluated toy datasets.Higher w corresponds to lower noise in the perturbation distribution.
C.5 Training for Special Neighborhood Structures
Special neighborhood graphs permit efficient evaluation of the CSM objective. Chains and cycles admit direct reparameterizations, while grids reduce the computation to sampled lower-dimensional cycles.
- Chain: For chain neighborhoods, the second objective term J2 simplifies through reparameterization because each node has at most one neighbor.
- Cycle: For cycle neighborhoods, J2 likewise admits a specialized reparameterization.
- Chain and cycle efficiency: For both chains and cycles, J2 can be evaluated efficiently using samples from the data distribution.
- Grid: For grid neighborhoods, J2 is approximated by decomposing dimensions into smaller cycles and uniformly sampling a dimension.
D.1 Ratio Matching with Discrete Data
The paper revisits discrete ratio matching, identifying flaws in the generalized multi-class objective and presenting a corrected objective. The corrected formulations produce more reasonable samples than the flawed versions.
- Ratio matching: Ratio matching learns discrete distributions by matching probability ratios, which cancel the intractable normalizing constant.
- Problem with the original objective: The generalized multi-class ratio-matching objective can have an optimum independent of the data distribution, preventing meaningful data learning.
- Corrected ratio matching: The corrected multi-class ratio-matching objective assumes all probabilities are non-zero and provides an alternative optimization target.
- Empirical comparison: Samples trained with the corrected objective appear more reasonable than samples trained with the original objective.
- Discrete marginalization: The multi-class discrete-marginalization formulation also contains a typo whose objective can be optimized independently of the data distribution.
- Corrected marginalization: Samples trained with the corrected discrete-marginalization objective appear more reasonable than those trained with the erroneous formulation.