BinAgg 手法詳細

📘 出典: 本ページの記述は原論文 [1] と実装 [2] に基づく。実測値はレポート本体を参照。

BinAgg（Binning-Aggregation）は、\(\mu\)-GDP（Gaussian Differential Privacy）の下で差分プライバシー（DP）線形回帰と合成データ生成を同一の集約量から行う手法である [1]。本ページでは、なぜ素朴な DP 回帰が失敗するか、BinAgg がどの設計でそれを補正するか、そして実装上の使い方とパラメータを解説する。

1. 問題設定: なぜ素朴な DP 回帰は失敗するか

DP を満たす最も単純な回帰は、回帰に必要な集約量（\(X^\top X\) や \(X^\top y\) に相当する二乗和・積和）を計算し、そこへノイズを足して公開し、あとは通常の最小二乗を適用する、というものである。これは 2 つの歪みを生む。

(1) 点推定のバイアス（0 方向への縮小）. 重み付き最小二乗の核となる行列 \(S^\top W S\) にノイズ入りの値を使うと、ノイズ入り二乗和 \(\tilde S^\top \tilde W \tilde S\) は真の \(S^\top W S\) よりも系統的に大きくなる。これはノイズの 2 乗の期待値が正であるため、対角成分（説明変数の分散に相当）に正のバイアスが乗るからである。回帰係数はおおむね \((S^\top W S)^{-1}\) の形で逆行列を通るので、分母が膨らむと推定値は 0 の方向へ縮小（attenuation）する。

💡 直感: 「測定誤差のある説明変数で回帰すると傾きが 0 に引っ張られる」という古典的な測定誤差バイアスと同じ現象である。DP ノイズはまさにその測定誤差として振る舞う。

(2) 分散の過小評価（CI が狭すぎる）. 標準的な標準誤差の式は、データのばらつきだけを誤差源と見なす。しかし DP 公開値には注入ノイズという第二の誤差源があり、これを無視すると推定の不確実性を過小に見積もる。結果として信頼区間（CI）が狭くなりすぎ、名目被覆率（例: 95%）を実際には下回る。

⚠️ 注意: この 2 つは別々の問題である。点推定のバイアスを補正しても、分散を正しく見積もらなければ CI の被覆は回復しない。BinAgg は両方に対処する（§3）。

2. 全体の流れ

BinAgg は「private に区間分割（binning）してから、bin 単位の集約量にノイズを足す」という二段構えを取る。

2.1 PrivTree による private 分割

まずデータ空間を bin に分割するが、分割境界そのものがデータに依存すると漏えいになる。そこで PrivTree を用いて private に空間を再帰分割する [1]。密度の高い領域は細かく、疎な領域は粗く分割される。PrivTree の仕組み（深さに依存しない予算配分・スコアの減衰と打ち切り）は専用ページ「PrivTree」で詳説する。

2.2 bin 単位の集約にノイズ付与

各 bin について \(\mathrm{count}\)、\(\mathrm{sum}(X)\)、\(\mathrm{sum}(y)\) を集計し、それぞれに Gaussian ノイズを加える。総プライバシー予算 \(\mu\) を以下の 4 要素に配分する（既定値）[2]。

binning（分割）: \(1\)
count: \(3\)
\(\mathrm{sum}_x\): \(3\)
\(\mathrm{sum}_y\): \(3\)

すなわち比 \((\text{binning}, \text{count}, \text{sum}_x, \text{sum}_y) = (1,3,3,3)\) で、分割に約 10%、各集約に約 30% ずつを割り当てる。

💡 直感: 分割の精度よりも集約量の精度のほうが推定誤差に効くため、予算の大半（90%）を集約に回す。

2.3 後処理（小 bin 除去とサンプルサイズ保存）

合成標本が min_count=2 未満になる bin は信頼できないため捨てる。さらに preserve_sample_size により、生成後の合計件数を元の \(n\) に合わせるよう調整する。これにより下流の解析がサンプルサイズの不一致で歪むのを防ぐ。

3. Algorithm 2: DP 線形回帰

BinAgg の回帰は、§1 の 2 つの歪みをそれぞれバイアス補正項とサンドイッチ分散で打ち消す。

3.1 バイアス補正付き重み付き最小二乗

核となるのは、補正項 \(\tilde D\) を差し引いた重み付き最小二乗である [1]。

\[ \tilde\beta = (\tilde S^\top \tilde W \tilde S - \tilde D)^{-1}\, \tilde S^\top \tilde W \tilde t \]

ここで \(\tilde D\) は、ノイズが二乗和に持ち込む系統的な増分（§1 の (1) で述べた正のバイアス）を打ち消す項である。ノイズ分散は既知（解析者が選んだ \(\mu\) と予算配分から決まる）なので、その期待増分を解析的に計算して差し引ける。重み行列 \(W\) は各 bin の件数の逆数を対角に持ち、件数の多い bin の集約値ほど相対的に信頼して重みづけする。

3.2 サンドイッチ分散推定

分散はサンドイッチ推定量で与える [1]。

\[ \tilde\Sigma = \tilde M^{-1}\, \tilde H\, \tilde M^{-1}, \quad \tilde M = \tfrac{1}{K}\tilde S^\top \tilde W \tilde S - \tilde D \]

ここで \(K\) は bin の数、\(\tilde M\) は §3.1 と同じバイアス補正を施した「パンの部分」、\(\tilde H\) は中央の「具の部分」でノイズ起因の分散を含む。この構成により、DP ノイズという第二の誤差源を分散に取り込み、漸近的に妥当な信頼区間を構成できる（Theorem 4.2）[1]。

💡 直感: サンドイッチ推定は誤差構造の仮定が崩れても妥当な分散を与えるロバスト分散の発想。ここでは「データのばらつき」と「DP ノイズ」を両方含む形に拡張している。

4. Algorithm 3: 合成データ生成

合成データは、回帰と同じ集約量から bin 単位で標本を生成する [1]。各 bin の private な count・sum から、その bin 内の点を再構成する。

重要なのは、回帰と合成が同じノイズ実現を共有できる点である（Corollary 3.1）[1]。これにより、追加のプライバシー予算を消費せずに、同一の \(\mu\) で回帰係数と合成データの両方を出力できる。

💡 直感: ノイズ入り集約量は一度作れば後処理に過ぎない。DP の後処理不変性により、同じ集約から何を導いても追加の予算は要らない。

5. 実装の 3 つの使い方（Options）

実装は用途に応じて 3 通りの呼び出しを提供する [2]。

Option A — 回帰のみ: dp_linear_regression。係数と CI だけが必要な場合。
Option B — 回帰 + 合成（予算共有）: dp_linear_regression(..., return_synthetic=True)。同一予算で回帰結果と合成データを同時取得。
Option C — 合成のみ: generate_synthetic_data。合成データだけが必要な場合。

⚠️ 注意: A と B の回帰係数は分布としては同等だが、ノイズ実現が異なるため返る数値は一致しない。再現したいときは random_state を固定する。

6. 主なパラメータ

パラメータ	役割
`mu`	総プライバシー予算（\(\mu\)-GDP）。大きいほど精度↑・プライバシー↓
`alpha`	CI の有意水準（既定 `0.05` = 95% CI）
`budget_ratios`	binning/count/sum_x/sum_y への予算配分（既定 `1,3,3,3`）
`min_count`	この件数未満の bin を除去（既定 2）
`clip`	`bounds` 外の値をクリップ
`preserve_sample_size`	合成件数を元の \(n\) に合わせる
`random_state`	乱数シード（再現性）
`x_bounds` / `y_bounds`	変数の取りうる範囲。解析者がドメイン知識で与える

⚠️ 注意: x_bounds / y_bounds をデータから計算してはいけない。データ依存の境界はそれ自体が漏えい経路になる。必ずドメイン知識など外生的な根拠で指定する [1]。

なお実装は \(\mu\)-GDP と \((\varepsilon,\delta)\)-DP の換算関数（delta_from_gdp など）も提供しており、慣れた \((\varepsilon,\delta)\) 表現でのプライバシー会計と相互変換できる [2]。

7. 直感の補足: \(\mu\) を動かすと何が起きるか

\(\mu\) を上げると注入ノイズの分散が下がる。その結果として:

ノイズが小さくなるので PrivTree がデータ空間をより細かく分割でき、bin の解像度が上がる。
バイアス補正項 \(\tilde D\) が小さくなり、推定の精度（係数・CI の幅）が向上する。
ただし、その代償としてプライバシー保証は弱まる。

💡 直感: \(\mu\) は「精度とプライバシーのつまみ」。BinAgg のバイアス補正とサンドイッチ分散は、どの \(\mu\) でも点推定の偏りと CI の被覆を妥当に保つことを狙う設計である。

参照

Lin, S., Slavković, A., & Bhoomireddy, D. R. (2026). Differentially Private Linear Regression and Synthetic Data Generation with Statistical Guarantees. AISTATS 2026 (PMLR). arXiv:2510.16974. https://arxiv.org/abs/2510.16974
BinAgg (Python package). Shuronglin/BinAgg, commit 13c09bb (2026-05-27). https://github.com/Shuronglin/BinAgg