One Proposal for Every Margin: Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices
Ruishuo Chen, Weijia Li, Xun Wang, Yu Chen, Leheng Cai, Longbo Huang
cs.LG, stat.CO
2026-09-29
用 GFlowNet 把二分矩阵的 SIS 提议分布变成学习问题,一个 set transformer 训练一次通吃所有边距;1190 个零样本边距上仅 3 个不敌 31 个手工配置的逐个最优,中位有效样本比例 99.8%。
生态学判断「物种共生模式是不是随机」,标准做法是把观测的物种×样地 0/1 表,与所有行和、列和都相同的随机表做对照;心理测量、社会网络、癌症基因组、金融网络里是同一套流程。背后是两个计算问题:数出固定边距的矩阵集合有多大,以及从中均匀采样。精确动态规划随列数指数爆炸;Markov chain 能采样但样本相关,也给不出计数。
SIS(序贯重要性采样)一个流程做两件事:逐行生成矩阵,按生成概率的倒数加权,权重均值就是集合大小的无偏估计。卡点在提议分布。从 1991 年 Snijders 起的提议全是解析公式,同一公式在不同边距上表现天差地别,Bezáková 等人 2012 年还构造出让条件 Poisson 提议需要指数级样本量的边距族。完美提议写得出来:每行按「放它之后还剩多少种完成方式」成比例选,所有权重相等、方差为零;算这些比例却等价于把计数本身算出来。
第一个贡献是个等价:零方差提议恰是「每个满足边距的矩阵 reward 为 1」的 GFlowNet 的流比例策略。GFlowNet 按 reward 比例生成对象,靠流一致条件训练,不需要归一化常数。在这棵逐行构造的树上,流过部分矩阵的流量等于它的完成数,总流量就是计数。训练目标随之有了 SIS 侧的解释:trajectory balance 的残差就是 log Z 减去提议的 log 权重,VarGrad 损失就是一批样本 log 权重的方差;训练在期望上最大化采样分布的熵,把提议推向均匀。计数仍取自 SIS 的权重均值,GFlowNet 自己拟合的 log Z 系统性偏低一个 KL,不能用。
第二个贡献是摊销。问题自相似:填完 k 行后,剩下的部分就是更小的同类实例,边距换成剩余行和与缩减列和。于是 rollout 走过的每个状态都是训练数据,一个只读剩余边距的网络就能当所有边距的提议。网络是 4 层 set transformer,宽度 256,无位置编码,不同的列和取值、剩余行和各成一个 token,置换对称性由构造保证。输出落在「行类型」上(按不同列和的列里 1 的个数分型),把指数级的行空间压成少量类型。每个类型的 logit 是三项之和:该类型行数的精确组合计数、Harrison–Miller 解析提议的 log 权重、网络学到的残差;输出头末层零初始化,训练从解析提议出发。训练池 1904 个边距(1688 合成 + 216 真实表);部署时每行一次前向,零样本零调参。
基线是 31 个解析配置(5 个提议 × 6 个权重指数 + 均匀)在每个测试边距上的事后最优。这个选择要跑完全部 31 个才能做出,实际用户做不出来,所以是偏强的对照。1190 个按种子和来源留出的边距,从 3×3 到 870×6:
| 方法 | 中位 ESS/N,全部 1190 | 最难 56 个(事后最优 <37%) |
| CDHL(networksis 默认) | 41.5% | 0.5% |
| Harrison–Miller | 97.4% | 7.7% |
| 31 选 1 事后最优 | 99.4% | 10.3% |
| MarginFlow | 99.8% | 94.1% |
胜负计数 415/772/3,210 张真实表只输 2 张。事后最优丢超过 1 nat 的 56 个边距上全胜,中位从 10.3% 提到 94.1%;全部边距的第十百分位从 68.5% 提到 98.1%。差距来自误差按行复合:每行偏 δ nat,m 行最多丢 mδ。Harrison–Miller 从 6 行的 98.7% 掉到 840 行的 0.6%,MarginFlow 到 840 行仍低于 0.1 nat,在 Bezáková 那族上外推到训练行数的五倍仍成立。训练一次 8 张 A100 跑 25 小时(报告值为 3 个种子的中位),基线全套扫描约 9000 小时。
对做条件检验的应用者,「选哪个提议、设哪个指数」这个没有可靠答案的问题被替换成跑一个 checkpoint,收益最大的恰是经典方法崩掉的长密表,真实生态与 Web of Life 数据正在这里。对 ML 侧,这是 GFlowNet 对接统计推断基础设施的干净案例:零方差提议、流一致、ESS 比例在最优解附近是同一个量(极限下 −log(ESS/N) 正是 Rényi-2 散度),网络直接在 SIS 关心的精度上训练,全程不需要真值。自相似摊销也不限于 0/1 矩阵,整数列联表、给定度序列的图有同样结构。