Learning to sample binary matrices uniformly from any margins
One Proposal for Every Margin: Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices
Machine Learning
Summary
Certain scientific fields analyze data arranged in binary tables with fixed sums for each row and column. Counting and drawing such tables uniformly is challenging because the number of possible tables is huge and depends closely on these sums. The authors link the best way to do this sampling to a kind of learned network called a generative flow network. They train a single model to handle many different margin sums efficiently and show it often outperforms previous hand-designed sampling methods, even on new cases it was not trained on.
What this means in practice
- •For ecology data analysts: Uniformly sample binary ecological presence-absence matrices meeting observed totals to improve statistical inference in biodiversity studies.
- •For financial risk modelers: Efficiently generate random binary network scenarios consistent with observed transaction totals to assess systemic risk in financial networks.
Authors
Ruishuo Chen, Weijia Li, Xun Wang, Yu Chen, Leheng Cai, Longbo Huang
Abstract
In ecology, psychometrics, and the analysis of social and financial networks, binary matrices are often analyzed conditional on their observed row and column sums, which restricts the problem to a finite sample space of matrices with the same margins. Two fundamental problems are to count this space and to sample uniformly from it. Sequential importance sampling (SIS) addresses both with independent weighted samples and an unbiased count estimator, but its efficiency depends critically on the proposal distribution. Existing proposals are analytically designed, and their accuracy can vary substantially with the margins. We show that the ideal SIS proposal, under which every weight equals the count and the variance vanishes, is exactly the policy of a generative flow network (GFlowNet) with unit reward on every matrix that has the given margins. We therefore propose MarginFlow, a framework that turns the design of the proposal into a learning problem and amortizes it across margins by exploiting their self-similarity. Every partial matrix is itself an instance with reduced margins, so one set transformer that reads the remaining margins serves every margin. We train MarginFlow on a pool of 1904 margins and evaluate it zero-shot on 1190 held-out margins, synthetic and real, from $3\times3$ to $870\times6$. On 1187 of the 1190 margins it matches or beats the best of 31 analytically designed configurations, chosen post hoc for each margin, and its median effective sample fraction is 99.8%. On the 56 margins where that best loses more than one nat of effective sample size, MarginFlow wins every one and raises the median effective sample fraction from 10.3% to 94.1%.