2025-11-11T16:28:09.601154

SAT-sampling for statistical significance testing in sparse contingency tables

Scharpfenecker, Windisch

Exact conditional tests for contingency tables require sampling from fibers with fixed margins. Classical Markov basis MCMC is general but often impractical: computing full Markov bases that connect all fibers of a given constraint matrix can be infeasible and the resulting chains may converge slowly, especially in sparse settings or in presence of structural zeros. We introduce a SAT-based alternative that encodes fibers as Boolean circuits which allows modern SAT samplers to generate tables randomly. We analyze the sampling bias that SAT samplers may introduce, provide diagnostics, and propose practical mitigation. We propose hybrid MCMC schemes that combine SAT proposals with local moves to ensure correct stationary distributions which do not necessarily require connectivity via local moves which is particularly beneficial in presence of structural zeros. Across benchmarks, including small and involved tables with many structural zeros where pure Markov-basis methods underperform, our methods deliver reliable conditional p-values and often outperform samplers that rely on precomputed Markov bases.

academic

疎な分割表における統計的有意性検定のためのSAT-サンプリング

基本情報

論文ID: 2511.05709
タイトル: SAT-sampling for statistical significance testing in sparse contingency tables
著者: Patrick Scharpfenecker, Tobias Windisch (ケンプテン応用科学大学、ドイツ)
分類: stat.ME (統計学 - 方法論)、math.CO (数学 - 組合せ論)、stat.CO (統計学 - 計算)
発表日: 2025年11月7日
論文リンク: https://arxiv.org/abs/2511.05709

要約

本論文は、分割表の正確条件検定問題に対して、従来のMarkov基MCMC法に代わるSAT求解器に基づく新しい手法を提案している。従来の手法は、すべてのファイバーを接続する完全なMarkov基の計算を必要とするため、疎な設定や構造ゼロが存在する場合には実行不可能であり、収束が遅い。著者らはファイバーをブール回路としてエンコードし、最新のSAT サンプラーを利用して表をランダムに生成し、SAT サンプラーが導入する可能性のあるサンプリングバイアスを分析し、実用的な緩和戦略を提案している。SAT提案と局所移動を組み合わせたハイブリッドMCMCスキームにより、正しい定常分布を保証し、特に構造ゼロが存在する場合に適用可能である。

研究背景と動機

問題定義

分割表の正確条件推論は統計学における重要な問題であり、特に独立性検定に関連している。このような問題は、固定された周辺制約の下でファイバー(fibers)からのサンプリング、すなわち線形制約 $Au = b$ を満たす非負整数表 $u$ を見つけることを必要とする。

既存手法の限界

従来のMarkov基MCMC法は、2つの主要なボトルネックに直面している：

計算複雑性: 現実的なモデルと表のサイズに対する完全なMarkov基の計算は、通常、計算上禁止的であるか、完全に実行不可能である
収束問題: 利用可能な基があっても、誘導される移動は混合が遅く、大量の調整作業が必要である
構造ゼロの問題: 構造ゼロおよび他の制約は、Markov基のサイズを増加させ、接続性を複雑にする

研究動機

著者らは、最新のSAT求解器、特に競合駆動節学習(CDCL)求解器が大規模な構造化インスタンスの処理において優れた性能を発揮することに着目した。近年のSAT サンプリング技術の進展(UniGen3、CMSGenなど)は、ファイバーサンプリング問題を解決するための新しい可能性を提供している。

核心的貢献

SATエンコーディング手法: ファイバー制約をブール回路にエンコードする効率的な手法を提案し、Tseitin変換によってCNF形式に変換し、疎性を保持しCDCL求解器での強い単位伝播を実現する
サンプリングバイアス分析: 最先端のSAT サンプラーにおけるサンプリングバイアスの程度と構造を定量化し、条件p値の精度を向上させるための実用的な緩和技術を開発する
ハイブリッドMCMCスキーム: SAT提案と局所移動を組み合わせた2つのハイブリッドスキーム $A_n(M)$ と $P_{n,k}(M)$ を提案し、正しい定常分布を保証する
性能向上: 構造ゼロを含む小規模で複雑な表などのベンチマークにおいて、従来のMarkov基法と比較した性能上の利点を実証する

方法の詳細

タスク定義

制約行列 $A \in \mathbb{N}^{k \times d}$ と周辺ベクトル $b \in \mathbb{Z}^k$ が与えられたとき、ファイバー $F_{A,b} = \{u \in \mathbb{N}^d : Au = b\}$ からのサンプリングを目的とし、条件p値を近似する：

$E_\rho[f] = \sum_{u \in F_{A,b}} f(u)\rho(u)$

ここで $\rho(v) \sim \frac{1}{v_1! \cdots v_d!}$ 、 $f(v) = \mathbf{1}_{X(v) \geq X(u^{obs})}$

SATエンコーディングアーキテクチャ

ブール回路エンコーディング

制約表現: 線形制約 $Au = b$ を一連の加算、乗算、等式チェックとして再定式化する
ビット表現: 各エントリを $l$ ビットで表現する。ここで $l = \lceil \log_2(\max_{i,j,A_{i,j}>0} \frac{b_i}{A_{i,j}}) \rceil$
回路構成: サイズ $\text{poly}(k,d,l)$ のブール回路 $C$ を構築する

Tseitin変換

古典的なTseitin符号化を使用して回路 $C$ をCNF形式 $F$ に変換し、以下を満たす：

$C(u_1, \ldots, u_d) = 1$ 当且つつ $y_1, \ldots, y_m$ が存在して $F(u_1, \ldots, u_d, y_1, \ldots, y_m) = 1$
$F_{A,b} \cap [2^l-1]^d$ と $F$ の充足解の間に全単射を確立する

ハイブリッドMCMCスキーム

$A_n(M)$ スキーム

$n$ ステップごとに1ステップはSAT サンプラーを使用し、残りは事前定義された移動集合 $M$ を使用する：

SAT ステップとMarkov基移動を交互に実行する
構造バイアスを緩和するため、SAT ステップの比率を低く保つ

$P_{n,k}(M)$ スキーム

$k$ 個のランダムウォークを並列に管理する：

最初にSAT サンプラーを使用してファイバーから $n$ 個の独立した初期点をサンプリングする
その後、 $M$ を使用する $k$ 個のランダムウォークを実行する
$n$ ステップごとに、1つのウォークをランダムに選択して $n$ ステップ続行する

独立性モデル $I_{d_1 \times \cdots \times d_k}$ : $d_1 \times d_2 \times \cdots \times d_k$ 独立性モデル
準独立性モデル $QI_{d_1 \times \cdots \times d_k}(S)$ : 構造ゼロ $S$ を伴う独立性モデル
3因子交互作用なしモデル $N3F_d$ : $d \times d \times d$ 表上の3因子交互作用なしモデル