A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

あなたは、特定の書籍を借りた人が誰であるかを決して明かしてはならないという厳格な約束を守りつつ、貸出リストを公衆に共有しようとしている司書だと想像してください。約束を守るために、あなたは、実際には存在しない名前をいくつか加えたり、名前をわずかに変えたりするなど、リストに少しの「静的なノイズ」を加えることにしました。これは、個人を特定せずにデータから学習するための数学的な盾である「差分プライバシー（Differential Privacy）」の核心的なアイデアです。

しかし、問題があります。時には、大きな視点での数値が正確に一致しなければならないというルールが存在します。例えば、ある州の総人口は、すべての郡の人口の合計と一致しなければなりません。もし、すべての郡のカウントにランダムなノートを加えるだけであれば、州の合計値はずれが生じ、数学的な整合性が崩れ、公式記録として使い物にならなくなってしまいます。ここに、「個人のプライバシーを守るために十分なノイズを加えること」と、「大きな合計値が変わらないように、ノイズが完璧に打ち消し合うようにすること」との間の綱引きが生じます。この論文は、プライバシーの盾を壊すことなく、どのようにしてこの「完璧に打ち消し合う」ノイズを加えるかという、非常にトリッキーな数学的課題に取り組んでいます。

---

完璧にバランスの取れたノイズのパズル

あなたは、非常に好みにうるさい審査員のためにケーキを焼こうとしているシェフだと想像してください。審査員には2つのルールがあります。

1. 味のルール： レシピ通りであることを保証するために、ケーキのどのひと口も、特定の味（例えばバニラ）と全く同じ味がしなければならない。
2. 重さのルール： ケーキの総重量は、正確に1,000グラムでなければならない。それ以上でも以下でもない。

ここで、レシピの起源を保護するために、「秘密の材料（ノイズ）」を生地に加えるとしましょう。もし、すべてのボウルにランダムにバニラビーンズをパラパラと振りまいたとしたら、ケーキの総重量はおそらく狂ってしまうでしょう。1,005グラムになったり、990グラムになったりするかもしれません。もし、重さを修正するために上層部から余分なグラム数を差し引こうとすれば、上層部の味が他の部分と変わってしまうため、「味のルール」を台無しにしてしまいます。

これは、ライアン・ラファティ（Ryan Lafferty）とアニディア・ロイ（Anindya Roy）の両著者が解決しようとしている問題そのものです。データの世界において、「ケーキ」はデータベース（米国の国勢調査など）であり、「ひと口」は個々のデータポイント（近隣住民の数など）であり、「秘密の材料」は身元を隠すために加えられるランダムな数値です。「重さのルール」は、線形不変量（linear invariants）——すなわち、「ある州の総人口は、その州に含まれるすべての郡の合計と等しくなければならない」といった制約を表しています。

旧来の手法 vs 新しい手法

以前、データサイエンティストはこの問題を、まずノイズを加えてから、後で合計値を「修正」する方法で解決しようとしていました。彼らはすべての郡にランダムな数値を加え、州の合計がずれていることを確認すると、数値を調整して強制的に正しい合計値に戻していました。

著者らは、この「後で直す」アプローチは、重い本で押しつぶして紙のしわを伸ばそうとするようなものだと主張しています。見た目は平らに見えるかもしれませんが、その紙は押しつぶされ、歪んでしまいます。数学的な用語で言えば、この「投影（projection）」法はノイズを隅に追いやってしまい、ノイズのランダム性（エントロピー）を低下させ、潜在的にプライバシーの保証を弱めてしまいます。それは、ノイズが予測可能になってしまうことであり、プライバシーにとって好ましくありません。

「最大エントロピー」による解決策

後からメチャクチャを修正するのではなく、著者らは最初からよりスマートに材料を混ぜ合わせる方法を提案しています。彼らは、ノイズが「相関（correlated）」を持つように生成する方法を開発しました。

これは、ダンサーのチームを想像すると分かりやすいでしょう。もし、すべてのダンサーがバラバラに動けば、グループ全体は混沌として見えますが、グループの中心はどこかへ漂ってしまうかもしれません。もし、グループを一定の場所に留めておきたい（不変量を維持したい）のであれば、単に彼らに動くのをやめるよう命じることはできません。代わりに、一人のダンサーが前へ踏み出したとき、別のダンサーが全く同じ量だけ後ろへ下がるように、動きを振り付け（コレオグラフィー）するのです。彼らは連動して動いていますが、その動きはリンクされており、グループ全体の位置は変わらないようになっています。

論文では「最大エントロピー（Maximum Entropy）」の実装を提案しています。簡単に言えば、「エントロピー」とはランダムさや驚きの度合いの尺度です。著者らは、合計がゼロになるというルールに従いつつ、ノイズが可能な限り予測不能で「驚き」に満ちたものであることを望んでいます。彼らは、射影勾配降下法（Projected Gradient Descent）（「ダンスのステップを反復的に調整する」という高度な方法）を用いて、完璧な振り付けを見つけ出します。

また、彼らは**POCS（凸集合への射影：Projection onto Convex Sets）**という手法も使用しています。これは、ルールによって定義された特定の形状の中に、ノイズが完璧に収まるまで調整を繰り返す「熱いか冷たいか（hot and cold）」のゲームのようなものです。その結果得られるノ数ベクトルは、以下の特性を持ちます。

1. すべての個別のデータに対して、期待される標準的なノイズ（ガウス分布やラプラス分布）のように見える。
2. 毎回必ず、合計がゼロ（または要求される不変量）になる。
3. 数学的に可能な限りランダムであり、最強のプライバシー保護を保証する。

彼らが発見し、証明したこと

著者らは、これがうまくいくと推測しただけではありません。彼らはそれを証明しました。

• 保証： この複雑で連動したノイズを用いても、システムが標準的な差分プライバシーの数学的保証（具体的には $(\epsilon, \delta)$-DP）を提供し続けることを示しました。これは、たとえノイズが協調して「踊って」いたとしても、プライバシーの盾は従来の単純な手法と同じくらい強力であることを意味します。
• 数学的魔法： 彼らの研究の大部分は、相関行列（correlation matrices）（変数同士がどのように関連しているかを示す数学的な格子）に関する困難なパズルを解くことに関わっていました。彼らは、これらの行列の「零空間（null space）」に関する未解決問題に対して、部分的な解法を提示しました。つまり、どのようなパターンの連動したノイズが可能であるかを正確に解明したのです。
• シミュレーション： 彼らは、米国の国勢調査（州、郡、ブロックを含むシナリオ）を模したシミュレーションデータを用いて、この手法をテストしました。最小単位である「ブロック」にノイズを加えた際、郡や州の合計は完全に維持されつつ、個々のブロックのカウントはプライバシーを守るのに十分なほどに隠蔽されていることを示しました。

なぜこれが重要なのか

これは単なる理論上の遊びではありません。米国の国勢調査局をはじめとする機関は、データを公開するたびにまさにこの問題に直面しています。彼らには、州の合計値を変えてはならないという憲法上の義務がありますが、同時に、一人ひとりのプライバシーを守る必要もあります。

著者らの手法は、これを実現するための「原理に基づいた」方法を提供します。データを後から強引に加工するのではなく、最初から正しくデータを生成する方法を提示しているのです。また、このアプローチは、スマートメーターの読み取り値（近隣の総電力使用量は個々の家庭の合計と一致しなければならない）や、ウェアラブルデバイスのデータなど、他の種類のデータにも有用であると彼らは述べています。

要約すると、この論文は、正確な合計値を得ることと、強力なプライバシーを守ることのどちらか一方を選ぶ必要はないということを示しています。高度な数学を用いてノイズを「振り付ける」ことで、両方を手に入れることができるのです。つまり、大きなルールとは完全に一致しながらも、細部の情報は完全に安全に保たれたデータセットを作ることができるのです。