Private-PGM の解説（共有推定エンジン mbi）
手法選定ガイド ｜ MST の解説 ｜ AIM の解説 ｜ INDEPENDENT の解説 ｜ メインレポート
📘 本ページのアルゴリズム・実装の記述は、原論文 arXiv:1901.09136（ICML 2019）と 参照実装
mbi（ryan112358/mbi）、および google/dpsynth が推定エンジンとしてこれを利用している事実に基づく。 本ページにはデモ固有の実測値は含まない（実測は各機構ページの 🔎 節を参照）。
1. 位置づけ — 3 機構が共有する「推定エンジン」
Private-PGM（Private Probabilistic Graphical Model、参照実装は mbi = marginal-based inference）は、
ノイズを加えて測定したマージナル群と整合する同時分布を推定する手法である arXiv:1901.09136。
DPSynth の MST・AIM・INDEPENDENT は、いずれも
- どのマージナルを、どの予算で測定するかを決める（＝機構ごとに異なる「測定戦略」）
- ノイズ付きで測定する（ガウス機構）
- 測定値と整合する同時分布を推定する（＝この Private-PGM。3 機構で共通）
- 推定した分布からサンプリングする
という共通のパイプライン（SELECT-MEASURE-GENERATE）の上に立っている。 つまり 3 機構の違いは①の測定戦略だけであり、③の推定エンジンは同一である。 本ページはこの③を解説する。各機構が Private-PGM に「何を」渡すかは §5 にまとめた。
🔎 機構が異なってもサンプリングの土台（同時分布の表現とその推定法）が同じであることは、 「機構間の差は測定するマージナルの選び方に帰着する」という本デモの整理（メインレポート §3.3）の根拠でもある。
2. 何を解いているのか — 測定値と整合する最尤分布
DP 機構が出力するのは、いくつかの属性部分集合 S_1, S_2, … について測定した
ノイズ付きマージナル ỹ_1, ỹ_2, … である。これらは
- ノイズのため非負でないセルを含みうる、
- 同じ属性を共有する別々の測定どうしで辻褄が合わない（例:
education単独の度数とeducation×incomeの周辺和が一致しない）、
という性質を持つ。素朴に各マージナルをそのまま使うと矛盾した合成データになる。
Private-PGM は、これらの測定値に最もよく合致するひとつの同時分布 p を、
測定の負対数尤度（ガウスノイズ前提では重み付き二乗誤差）
minimize over p (確率分布) Σ_k || M_k · p − ỹ_k ||²
を最小化する形で推定する。ここで M_k は同時分布 p から部分集合 S_k のマージナルを取り出す線形作用素、
ỹ_k はそのノイズ付き測定値である。こうして得た単一の分布からサンプリングするため、
出力はすべての測定と整合し、非負・総和 1 を満たす。
3. 同時分布をどう表すか — グラフィカルモデル（マルコフ確率場）
属性が 9 列あれば、同時分布をセルごとに陽に持つと （各列のカーディナリティの積だけ）爆発する。Private-PGM はこれを マルコフ確率場（Markov Random Field, MRF）= グラフィカルモデルとして表現する。
- 測定した各マージナル
S_kを MRF のクリーク（factor）として持つ。 - 同時分布は各クリークのポテンシャル（指数族のパラメータ
θ）の積に比例する形p_θ(x) ∝ exp( Σ_k θ_k(x_{S_k}) )で表す。 - 測定したマージナルに現れない高次の相互作用はモデルに入らないため、表現はコンパクトになる。
この MRF は、測定したクリークの集合から定まる graphical structure（junction tree）に対応する。 INDEPENDENT のようにクリークが 1-way だけならグラフは辺を持たず分布は積（＝独立）になり、 MST なら木、AIM なら木とは限らない（同じ属性に複数の依存が張れる）グラフになる。
モデルサイズ（junction tree）と計算量
推論のコストは、MRF を三角化して得る junction tree の最大クリークのサイズ（含まれる属性のカーディナリティの積）で決まる。
高次・高カーディナリティのマージナルを多数測ると junction tree が巨大化し、推定が指数的に重くなる。
そのため各機構は測定するマージナルにサイズ上限を設けている
（AIM の max_model_size／max_marginal_size、MST の maximum_marginal_size）。
「どこまで複雑な依存を保持できるか」は、この推定側の許容サイズと表裏一体である。
4. どう推定するか — mirror descent とウォームスタート
§2 の最小化問題を、Private-PGM は mirror descent（ミラー降下法）で解く。
- パラメータ
θについて、目的関数の勾配を計算し、指数族の幾何に沿って更新する。 各反復で現在のθから周辺分布を求める推論（marginal inference）を junction tree 上で行い、 測定値とのズレ（M_k · p_θ − ỹ_k）を勾配としてθを動かす。 - 反復回数は実装上のパラメータ（DPSynth では
pgm_iters。MST/INDEPENDENT 既定 5000、AIM 既定 1000）で、 多いほど測定値への当てはめは進むが時間がかかる。
ウォームスタート（warm start）は、AIM のように反復的にマージナルを追加測定する機構で効く。
新しいマージナルを 1 つ測るたびに推定をゼロからやり直すのではなく、
直前ラウンドの θ を初期値として追加測定ぶんだけ調整する。これにより
- ラウンドごとの推定が高速化し、
- AIM のような「測って→推定して→次に測るマージナルを選ぶ」反復が現実的な時間で回る。
🔎 AIM が「反復のたびに Private-PGM の再推定が走るため MST より重い」（AIM 解説 §5）のは、 ウォームスタートを使ってもなおラウンド数ぶんの推定が積み上がるためである。 一方 MST・INDEPENDENT は測定が一度きりなので推定も 1 回で済む。
5. 各機構は「何を」Private-PGM に渡すか
推定エンジンは共通でも、入力として渡される測定済みマージナルの集合が機構ごとに異なり、 それが MRF の構造（＝保持できる依存関係）を決める。
| 機構 | Private-PGM に渡す測定マージナル | 結果として推定される構造 |
|---|---|---|
| INDEPENDENT | 全列の 1-way のみ | 辺なし。同時分布は周辺分布の積（＝独立） |
| MST | 全列の 1-way ＋ 最大全域木に選ばれた d−1 本の 2-way | 木構造（off-tree のペアは独立扱い） |
| AIM | 1-way ＋ 各ラウンドで適応選択した 1〜3-way（木に限らない） | 木とは限らない MRF（同属性に複数依存・3-way も可） |
- INDEPENDENT で「列間相関が一切保持されない」のも、MST で「木から外れたペアが崩れる」のも、 推定エンジンの違いではなく、渡されるマージナルの違いから生じる。 各機構ページの「得意・苦手」は、突き詰めればこの入力集合の違いに帰着する。
- AIM がラウンドごとに測定を追加できるのは、§4 のウォームスタート付き推定が前提にある。
6. DPSynth における利用
- DPSynth は Private-PGM のアルゴリズムを
pipeline_dpの処理系の上で利用し、 生データの離散化・ドメイン発見から復号までを含む end-to-end の処理に組み込んでいる （メインレポート §3.4 のライブラリ位置づけを参照）。 - 推定の反復回数は各
*Configのpgm_itersで制御できる。 本デモの設定値は各機構ページの「主なパラメータ」節に記載している。 - Private-PGM 自体は DP の予算を消費しない。差分プライバシーは①測定（ガウス機構）・選定（指数機構）の段で成立し、 推定はそのノイズ付き測定値だけを入力とする後処理（post-processing）であるため、 DP の後処理不変性により追加の予算を要しない。
7. 参考リンク
- 原論文: McKenna, Sheldon, Miklau, Graphical-model based estimation and inference for differential privacy, ICML 2019 — arXiv:1901.09136
- 参照実装: Private-PGM /
mbi（ryan112358/mbi） - 利用元ライブラリ: google/dpsynth（README「Supported Synthesis Algorithms」で各機構の推定基盤として参照）
- 各機構がこのエンジンに渡す測定戦略: MST ／ AIM ／ INDEPENDENT