Differential Privacy for Markov Chain State Trajectories

技術要約：マルコフ連鎖の状態軌跡における差分プライバシー

問題提起
データ駆動型システムは、信用リスクの遷移、都市の交通パターン、インターネットのブラウジングなどの挙動をモデル化するために、マルコフ連鎖によって生成される状態軌跡に頻繁に依存しています。これらの軌跡は有用ですが、共有する際には重大なプライバシーリスクを伴います。なぜなら、短いシーケンスであっても、ユーザーの識別を再構成するために利用される可能性があるためです。マルコフ連鎖の軌跡をプライバシー保護する既存の手法は、多くの場合、マルコ夫連鎖を非決定性有限オートマトンとして扱い、遷移確率を無視した一様ランダムウォークを通じてプライベートな状態を選択します。このアプローチは、基礎となるマルコフ連鎖の構造的特性を欠いた「非典型的な」軌跡を生成することが多く、その結果、ダウンストリーム分析におけるプライバシー保護済みデータの有用性を低下させます。さらに、先行研究はしばしば軌跡をオフラインでプライバシー保護するか、あるいは構造的な類似性を維持するために特定の遷移ダイナミクスを活用することに失敗しています。

手法
著者らは、$\epsilon$-差分プライベートな状態軌跡をオンライン（つまり、プライベートな軌跡が機密性の高い軌跡と同時に生成される形式）で生成するための新しいフレームワークを提案しています。この手法の核心は、マルコフ連鎖を、エッジの重みが遷移確率の負の対数（$W_{ij} = -\log(P_{ij})$）である重み付き有向グラフとして扱うことにあります。

1. グラフ誘導と距離： 著者らは、このグラフ上における最短経路距離 $G(i, j)$ を定義しています。命題1は、このグラフにおける最短経路が、マルコフ連鎖における2つの状態間の最も尤もらしい経路に対応することを確立しています。
2. 隣接性の定義： 新しい軌跡の隣接性の概念が導入されています（定義4）。2つの軌跡は、対応する状態間の対称最短経路距離の総和がパラメータ $\rho$ によって制限されている場合に、隣接しているとみなされます。これは、ハミング距離（差異のあるエントリを数える手法）に依存する先行研究とは異なり、遷移の尤もらしさに基づいた、より微細な類似性の定義を可能にします。
3. メカニズム設計（メカニズム1）： 提案されているメカニズムは、permute-and-flipメカニズムに着想を得た戦略を用いて、オンラインでプライベートな状態を生成します。各時刻 $t$ において、前時刻のプライベートな状態 $s'_{t-1}$ と現在の機密状態 $s_t$ が与えられたとき、メカニズムは次のプライベートな状態 $s'_t$ を実行可能な近傍 $N(s'_{t-1})$ から選択します。選択確率は、ユーティリティ関数 $u(w, w') = -\sum G(s'_t, s_t)$ によってバイアスされ、これはグラフ距離の観点から真の状態から遠い状態に対してペナルティを課します。
4. ドリフト解析： 著者らは、機密状態とプライベート状態の結合プロセスを隠れマルコフモデルとしてモデル化しています。彼らはFoster-Lyapunovドリフト解析を利用して、プライベートな軌跡が「負のドリフト」を示すこと、つまり、もし逸脱したとしても、統計的に機密軌跡の近傍に戻る可能性が高いことを証明しています。

主な貢献
本論文は主に4つの貢献を行っています。

• 新しいプライバシー定義とメカニズム： 著者らは、最短経路距離に基づくマルコフ連鎖状態軌跡の新しい隣接性の定義を導入し、この定義に特化したオンライン $\epsilon$-差分プライベートメカニズムである「メカニズム1」を開発しました。
• 誤差境界： プライベートな軌跡が機密なものから大きく逸脱する確率に関する集中不等式（定理2）を提供し、大きな誤差が発生する確率は指数関数的に減少することを示しています。
• 典型性とエントロピー境界： 著者らは、プライベートな軌跡の期待経験エントロピーを境界付け（定理3）、プライベートな軌跡が、高い確率で基礎となるマルコフ連鎖の $\eta$-典型的集合内に存在することを示す集中境界（定理4）を提供しています。これにより、プライバシー保護されたデータが元のプロセスの統計的性質を保持することが保証されます。
• 実証的検証： メカニズムは、信用遷移、都市交通（フロリダ州ゲインズビル）、およびインターネットトラフィック（Wikispeedia）の3つの実世界のデータセットでテストされています。

結果
数値シミュレーションにより、メカニズム1は、同一のプライバシーレベルを維持しながら、最先端のメカニズム（Chen et al., 2023b）と比較して、ユーティリティの面で大幅に優れていることが示されました。

• エントロピーの減少： 3-差分プライバシーの下で、メカニズム1は先行研究と比較して最大80%のエントロピー減少を示しています。これは、生成されたプライベートな軌跡が、真のマルコフ連鎖の統計分布に非常に近いことを示しています。
• 誤差確率： このメカニズムは、既存の手法と比較して、大きな誤差（最短経路距離における偏差）が発生する確率を最大4桁減少させます。例えば、信用遷移の例では、大きな誤差（$v=15$）が発生する確率は0.003から $2 \times 10^{-7}$ に低下しました。
• 構造的類似性： 軌跡の長さが増すにつれてエントロピーが増大する（ランダムウォークへと退化する）ことが多い先行手法とは異なり、メカニズム1はある一定の軌跡長に達した後、一定のエントロピーレベルを維持し、データの構造的完全性を保持します。

意義
本論文は、そのフレームワークがマルコフ連鎖データにおけるプライバシーとユーティリティの決定的なトレードオフに対処していると主張しています。遷移確率を利用して距離と隣接性を定義することで、メカニズムはプライバシー保護された軌跡が「典型的」であり、かつ機密データと構造的に類似していることを保証します。これにより、ダウンストリームシステムは、ユーザーのプライバシーを損なうことなく、プライバシー保護されたデータを効果的に活用できます。著者らは、彼らのアプローチがニューラルネットワークやコンテキスト依存の距離関数を必要とせず、遷移確率が既知であればあらゆるマルコフ連鎖の設定に直接適用可能であることを強調しています。本研究は、状態空間を非構造的な集合として扱う手法に対し、システムの基礎となるダイナミクスを尊重するオンライン・プライバシー保護軌跡の生成が可能であることを確立しました。