AIM 機構の解説（Adaptive and Iterative Mechanism）

手法選定ガイド ｜ MST の解説 ｜ INDEPENDENT の解説 ｜ Private-PGM の解説 ｜ メインレポート

📘 本ページのアルゴリズム・実装の記述は、原論文 arXiv:2201.12677 と google/dpsynth のソースコード（dpsynth/discrete_mechanisms/aim.py、2026-06 時点の main ブランチ）に基づく。 実験数値の節（🔎）のみ本デモの実測である。

1. 位置づけ

AIM（Adaptive and Iterative Mechanism）は、SELECT-MEASURE-GENERATE パラダイムの代表的な反復型アルゴリズムである arXiv:2201.12677。 ワークロード（合成データで再現を重視するマージナルの集合と重み）を入力として受け取り、 「現在のモデルが最も外しているマージナル」を毎ラウンド適応的に選んで測定し、モデルを少しずつ改善する。

注意: AIM の名前にある「適応的な選択」は機構内部でどのマージナルを測るかの選択であり、 「AIM か MST かをデータに応じて選んでくれる」機能ではない（→ 手法選定ガイド）。

2. アルゴリズムの仕組み

1. 候補の生成: ワークロード（未指定なら全属性の 3-way 組み合わせ）の下方閉包 （1-way・2-way・3-way のすべての部分集合）が候補になる。各候補の重みは 「ワークロードとの属性の重なり × ワークロード重み」の合計で、関係が深いマージナルほど選ばれやすい。
2. 候補フィルタ: 候補を採用した場合のグラフィカルモデルの推定サイズ（junction tree のメモリ量）が 上限以下のものだけ残す。上限は max_model_size ×（消費済み予算の割合）で、 予算を使うほど大きなマージナルが解禁される設計になっている。
3. SELECT（指数機構）: 各候補のスコアを 重み ×（現モデルとの L1 誤差 − ノイズバイアス補正項） で評価し、指数機構で 1 つ選ぶ。 補正項は「測定したときに乗るガウスノイズの期待量」で、 誤差は大きいが測ってもノイズに埋もれるだけの巨大なマージナルが選ばれにくくなる。
4. MEASURE / GENERATE: 選んだマージナルをガウス機構で測定し、 全測定値と整合するモデルを Private-PGM（mirror descent、ウォームスタート）で再推定する。
5. アニーリング: 測定してもモデルがほぼ動かなかった場合、「このノイズ水準ではもう情報が取れない」 と判断してラウンドあたり予算を anneal_factor（既定 4）倍に増やし、回数より 1 回の精度を優先する。

3. プライバシー予算の使われ方

ラウンド予算は 総予算 ÷ max_rounds（既定は 16 × 列数 ラウンド）から始まり、アニーリングで増額されうる。 残予算が少なくなると最終ラウンドで全額を投入して終了する。

4. 主なパラメータ（AIMConfig）

📘 公式の docstring は「お試しなら max_model_size=1、本番用途なら max_model_size>=80 を推奨。 実行に数時間かかりうる」と注記している。本デモでは max_rounds=16, pgm_iters=1000, max_model_size=100 に抑えて ε=1 で約 70 秒で実行した（生成時間は ε に強く依存し、ε=10 では約 420 秒）。

5. 得意なケース・苦手なケース

得意:

• 重視するマージナル（相関）が事前に分かっている場合。ワークロードとして重み付きで指定でき、 その近傍のマージナルが優先測定される。下流タスク（予測・クロス集計）が明確なときに有利。
• 幅広いペア相関の保持。MST と違い「木」の制約がなく、同じ属性の周りに複数の依存を張れ、3-way も扱える。
• 予算・データ特性に応じて測定の粒度を自動調整したい場合（アニーリング・サイズ上限の仕組み）。

苦手:

• 計算コスト。反復のたびに Private-PGM の再推定が走るため、MST の数倍〜数十倍遅い （公式注記では数時間かかりうる）。
• パラメータ依存性。max_rounds・max_model_size の設定で結果と実行時間が大きく変わる。
• 本デモの ε=1 では数値列同士の相関誤差が MST より大きかった（下記）。設定（ラウンド数・モデルサイズの制限）の 影響と考えられ、AIM が常に全指標で優るわけではない。ただし高 ε（ε≥2）では AIM の相関誤差が MST を下回る ようになり（§7 のマルチシード実測）、優劣は ε に依存する。

6. 本デモでの実験結果

🔎 以下は本デモ（UCI Adult、20,000 行、9 列、δ=1e-5）の実測。詳細は各リンク先を参照。

• 機構比較（ε=1.0、メインレポート §5.1）: TSTR AUC 0.758（3 機構中最高、実データ学習の 参照上限に最接近）。数値列の相関誤差は単一シードで 0.404 と振れたが、これは典型値を大きく外す不安定な点推定で、 複数シード（10 シード）の §7 では ε=1.0 で 0.022 ± 0.011 と実際には小さい（生成は run-to-run でも振れるため 単一シードの点推定で語れない）。生成時間約 70 秒（MST の約 7 倍。高 ε ではさらに重い）。
• 複数シード（追加実験B）: TSTR AUC 0.709 ± 0.051（10 シード）。 MST（0.651 ± 0.106）をやや上回るが標準偏差が重なり、両者の優劣は確率的ばらつきの範囲にとどまる。
• 2-way 忠実度（追加実験C）: 4 ペア中 3 ペアで最良（TVD 0.03〜0.16）。 marital-status×income は MST 0.359 に対し AIM 0.048 と大きく良い（occupation×income も MST 0.282→AIM 0.034）。 一方 education×income は MST 0.024 が AIM 0.064 を上回った。 「重要なペア相関が決まっているなら AIM」という使い分けの根拠。
• ε スイープ（本デモ実測）: → §7 にまとめた。

なぜ AIM が MST を上回りうるのか（アルゴリズム由来の解釈）

🔎 以下は、本デモでの「AIM の TSTR が最も高かった／全ペアで 2-way が最良だった」という結果に対する、 AIM 論文 arXiv:2201.12677 のアルゴリズム的性質からの解釈である。 検証対象 DPSynth についての「列間依存が下流有用性に効く」という要約は メインレポート §6.1 にある。

機構間の差は、推定エンジン（Private-PGM）が共通である以上、どのマージナルを測定して渡すかに帰着する。

• MST は最大全域木の d−1 本の 2-way に固定される。木に載らないペアは独立扱いになり、 そのペアの相関が強いほど崩れる（MST 解説 §6）。一度きりの選定で、後から修正する機会もない。
• AIM は木の制約を持たず、毎ラウンド「現在のモデルが最も外しているマージナル」を適応的に選ぶ。 同じ属性（本データなら income）の周りに複数の依存を張れ、3-way も扱える。 このため、MST が木から落とした marital-status×income・occupation×income を AIM は測定対象に拾い上げられ、下流の income 予測（TSTR）に効く相関を保持しやすい。

つまり本デモで AIM が優位だったのは、「ワークロード（＝下流で重要なマージナル）に向けて測定対象を適応選択する」という AIM 固有の設計が、木構造の制約を持つ MST より広いペア相関を保持できたためと解釈できる。 ただしこれは無償ではなく、次の計算コストとパラメータ依存性を伴う。

計算コストとパラメータ依存性（アルゴリズム由来）

• 計算コスト: AIM は毎ラウンド測定を追加し、そのたびに Private-PGM の再推定が走る（Private-PGM 解説 §4）。 ウォームスタートで 1 ラウンドの推定は速くなるが、ラウンド数ぶん積み上がるため MST（測定・推定とも一度きり）より重い。 本デモでは ε=1 で約 70 秒（MST の約 7 倍）、高 ε ほど重く ε=10 では約 420 秒に達した（§7）。 公式注記では max_model_size を上げると数時間級になりうる。
• パラメータ依存性: max_rounds・max_model_size が結果と実行時間を大きく左右する。 本デモでは max_rounds=16, pgm_iters=1000, max_model_size=100 に抑えており、 この制限のもとでは数値列同士の相関誤差が MST より大きかった（§6 機構比較）。 AIM が常に全指標で優るわけではなく、設定次第で得手不得手が動く点に注意する。

7. ε を変えたときの挙動（複数シードの ε スイープ・WSL 固定環境実測）

本節は、ε = 0.5 / 1.0 / 2.0 / 10.0 の 4 水準で 3 機構を生成し、ε–有用性の変化を 複数シードの平均±標準偏差で評価する（追加実験E と同一系列）。 当初は単一シード（seed=42）でこのスイープを取ったが、AIM では run-to-run 分散が大きく ε トレンドを判定できなかった（Issue #14）ため、 機構の seed を 0..9 まで振って構造的傾向と確率的ばらつきを分離した。

🔎 取得環境: §5/§6 と同じ WSL 固定環境（Python 3.12.3・jaxlib 0.7.1・ dpsynth c17e714…、再現手順ノート）の単一の実行系列で取得した （Issue #17）。入力データは random_state=42 で固定し、 機構の seed のみ振る。3 機構とも 10 シード（Issue #20 で AIM を 5→10 に拡張し、3 機構を共通シード 0..9 の単一系列で再生成）。 生成条件: UCI Adult 20,000 行・9 列・δ=1e-5、AIMConfig(max_rounds=16, pgm_iters=1000, max_model_size=100)。

表: AIM / MST の ε–有用性（複数シードの平均±標準偏差・n=10）

図: 3 機構の ε スイープ（複数シードの平均±標準偏差・エラーバー） — 左が平均 1-way TVD、右が TSTR AUC。

所見（本デモ実測）:

• 分布再現性の ε 依存（AIM）: 平均 1-way TVD は ε=0.5 → 10 で 0.098 → 0.087 → 0.076 → 0.064 と ε が大きいほど単調に改善する（標準偏差も ε とともに縮み、ε=10 では ±0.002）。単一シードで見えた 非単調は分散由来で、シードを振ると消える。マルチシード化により ε トレンドが判定可能になったのが 本実測の核心である（単一シードで「判定不能」だった #14 の課題を解消）。
• TSTR AUC の ε 依存（AIM）と「谷」の判定: 0.819 → 0.693 → 0.829 → 0.878 と、ε=0.5 → 1.0 に AUC の谷がある。 この谷は 10 シードでは分散由来ではなく実在する（Issue #20）: ε=1.0 の全 10 シードの AUC（0.506〜0.777）は、ε=0.5 の全シード（0.786〜0.852）・ε=2.0 の全シード（0.812〜0.859）の どれよりも低く、3 水準の分布が重ならない（最悪シード由来ではなく分布全体が下方シフトしている）。 ただし ε=1.0 は AUC の標準偏差が最大（±0.072）の不安定点でもあり、1 シードは AUC≈0.51 まで落ちる （この外れシードは相関誤差ではなく 1-way TVD が最大）。全体としては「ε≥2 で AUC が単調に向上し低分散に収束する （ε=10 で 0.878±0.006）」のが安定した傾向で、ε=1.0 付近のみ予算配分の適応が不安定になりやすいと解釈できる。
• 相関誤差の ε 依存と MST との逆転: AIM の相関誤差は ε=0.5 で 0.114±0.096 と大きく分散も巨大だが、 ε≥1 では 0.019〜0.024 と小さく低分散に収束する。MST の相関誤差（0.058〜0.085）と比べると、 ε≥2 では安定して AIM<MST（AIM が優る）。ε=1.0 は本実行で AIM 0.022 < MST 0.073 だが、AIM の ε=1 相関誤差は run-to-run でも振れやすく（別実行の 5 シードでは 0.104±0.163）、安定して言えるのは ε≥2 の逆転である。 AIM は予算が増えるほど income 周りの相関を確実に捉えられるようになるためと考えられる。
• 計算コストの ε 依存: AIM の生成時間は ε=1.0 の約 70 秒に対し ε=2.0 で約 280 秒・ε=10.0 で約 420 秒と ε を上げるほど顕著に増えた（高 ε ほど解禁・測定されるマージナルが大きくなるため）。 MST は全 ε で 8〜11 秒と桁違いに速い。高 ε で AIM のコンパイルが最も重くなる点は、 リモート環境（RLIMIT_MEMLOCK 上限）で高 ε の AIM が JIT メモリ確保に失敗した事実とも符合し、 §5 計算コストとパラメータ依存性 の「AIM の計算資源依存性」を裏づける。
• 残課題: ① ε=1.0 付近の AUC の谷の機序（予算配分・アニーリングの不安定性）は未解明 （谷の実在は 10 シードで確認済み＝Issue #20 で解消、機序の解明は今後）。 ② max_rounds / max_model_size を変えたときの ε 依存の感度は未評価。

8. 参考リンク

• 原論文: McKenna et al., AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data — arXiv:2201.12677
• 実装: dpsynth/discrete_mechanisms/aim.py（GDP 会計版の aim_gdp.py もある）
• 公式ドキュメント: google/dpsynth README「Supported Synthesis Algorithms」
• 推定エンジン: Private-PGM / mbi

← 手法選定ガイドに戻る