  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.
