はじめに
オープンデータとして公開したり、またはユーザにサービスとしてAPI公開することが今後増えるものと考えられます（そうであってほしいと思います）。また、蓄積したデータを第3者が利用する際に、収集元のセンシティブな情報が漏れないようにするためのプライバシ保護が必要になります。
AppleのWWDC2016では、差分プライバシーを利用していると報告がありました(参考：Engineering Privacy for Your Users）その時に一時バズったかと思いますが、まだ差分プライバシが具体的に使われている例は少ないかと思います。そこで、差分プライバシーをRでやってみました。
内容は私も勉強している段階ですので、誤りがあればご指摘よろしくお願いします。
参考図書
- 佐久間先生の機械学習プロフェッショナルシリーズのデータ解析におけるプライバシー保護を参考にしました。この書籍は研究や実問題としてのプライバシ保護の流れが筋立てて説明してくれています。特に差分プライバシーの難解な数式もわかりやすく例を交えて解説してくれていますので大変重宝しています。差分プライバシーとは何か？ （定義 & 解釈編）(slideshare)もとてもわかりやすいので最初に見るのにおすすめです。
ラプラスメカニズム
データ解析におけるプライバシー保護の8.3節の内容となります。ほぼこれに準じて私なりの解釈を加えます。
まず、メカニズム とは簡単にいうと、クエリに対する返答を素直に返すのではなく、なんらかの処理を行ってから返答を返すものです。
メカニズムを自作するとしたら、ランダムに値を変えたり減らしたりなんてことをすると思いますが、そうすると元のデータベースの持つ情報が無くなり、使い物にならなくなってしまう可能性があります。
そこで、確率的にノイズを生成して、「実際の値との誤差は、◯％で□以下である」みたいなことを保証することを考えます。説明できる誤差なら多少あろうが気にしないっていう心情かなと思います。
前提として、$x_i \in \mathbb{R}$からなる真のデータベース$D = \{x_1, x_2, \ldots, x_n\}$、偽のデータベース $D^{'} = \{x_{1}^{'},x_2^{'},\ldots,x_n^{'} \}$、異なるレコードの数を$d(D,D^{'})$とします。
書籍では、$d(D,D^{'})=1$であるような組を$D \sim D^{'}$と表現しています。このとき、クエリ$q$の出力に与える影響度を以下の敏感度で評価します。
$$\Delta_{1,q} = max_{D \sim D^{'}} ||q(D) - q(D^{'})||_{1}$$
$||*||_{1}$はl1ノルムです。$D \sim D^{'}$であるようなすべての$D,D^{'}$の組における最大値を返す式です。簡単に言うと、偽の$D^{'}$と一番誤差が大きいときを敏感度と言うのかと思います。
クエリとは例えば、データベースの平均値を求める$ave$クエリなんてのがあるとすると、その敏感度は$\Delta_{1,ave}$です。省略しますが、具体的にその敏感度は$1/n$になります。$n$の大きさに依存するものとなります。
書籍では、
最大値クエリの敏感度$\Delta_{1,max}=1$になるので、最大値の公開は平均値の公開よりも慎重にであるべき
と書いています。慎重というのは、公開したときにユーザに嘘の情報を伝えすぎるのもよくなく、かといって真の情報を伝えすぎるのもよくなく、そのバランスを定量的に評価する指標かなと解釈しました。
ラプラス分布は以下のスケールパラメータ$R$で定まります。Rを大きくすると、裾が広がります。
$$Lap(R) = \frac{1}{2R}e^{-\frac{|x|}{R}}$$
ラプラスメカニズムはクエリの敏感度で決まるパラメータ$R$を使って、ラプラス分布から確率的に誤差を選択しようというメカニズムかと思います。
プライバシパラメータ$\epsilon$も設定します。これは値が小さいほどプライバシーを強く保証する＝誤差が大きくなります。$\epsilon$は差分プライバシーの定義どおり、真のデータベースと偽のデータベースで、クエリの返答値が高々$exp(\epsilon)$倍程度しか変わらないというプライバシーの単位を示します。
アルゴリズム ラプラスメカニズム
入力：$D$, $\epsilon$, $\Delta_{1,q}$
出力：y
STEP1：$R = \Delta_{1,q} / \epsilon$
STEP2：$r \sim Lap(R)$
STEP3：$y = q(D) + r $
Rでラプラスメカニズムをやってみる
Rでラプラス分布からサンプリングしてくれる関数としてVGAMパッケージを使います。いくつか他の類似したパッケージもあるみたいです。
require(VGAM)
set.seed(42)
データを10万人のテストの点数[0-100]と仮定し、サンプル生成を行います。
n = 100000
score = sample(seq(0,100), n, replace = TRUE)
mean(score)
[1] 50.08518
プライバシーの強さ$\epsilon$を設定します。ここでは、0.1と設定します。平均値を求めるクエリを発行したときの敏感度は$1/n$も求まり、ラプラスメカニズムにおけるパラメータ$R$を$\Delta_{1,q}/\epsilon$で与えます。
epsilon = 0.1
sensitivity.mean = 1/n
R = sensitivity.mean / epsilon
ラプラス分布から誤差$r$を求めて、それを平均値クエリに加算するだけです。とても簡単です。
実際に値は少しずれた値が算出されます（当たり前ですが）。
r = VGAM::rlaplace(1, location = 0, scale = R)
qD = mean(score) + r
print(qD)
[1] 50.08508
ラプラスメカニズムによる誤差
ラプラスメカニズムを適用したときに、どれくらい実際の値とずれちゃうのか気になります。
そのため、メカニズムにはその正確性を評価するために、確率的な上限が以下になると証明されています。例えば、「実際の平均値との誤差は、◯％で□以下である」と説明するわけですね。
$$\frac{1}{\epsilon n}\log(\frac{1}{\delta})$$
$\delta$は保証したい誤差のうち、何％の例外を許容するかと解釈できます。
l1.mean.sensitivity = 100 / n
l1.max.sensitivity = 100
delta = 0.05
prob.mean.upper.bound = 1/(epsilon * n) * log(1 / delta)
print(prob.mean.upper.bound)
[1] 0.0002995732
ここでは、$\delta=0.05$、つまり確率95％で誤差が$2.99×10^{-4}$になるってことが分かりました。 100回中95回は、これくらいの誤差が発生しても、多くの実用上は問題ないですよね。
本当に95％か確認してみる
理論的に保証されていることがわかったので、実際に試してみます。
qD.diff = sapply(1:100000, function(i){
r = VGAM::rlaplace(1, location = 0, scale = R)
qD = mean(score) + r
})
count <- abs(mean(score) - qD.diff) < prob.mean.upper.bound
sum(count) / 100000
[1] 0.95073
実際に、上限以下で収まった差が95.073％と出たので、理論通りに保証できていることが分かりました。
おわりに
- 実際の数値をみながらすすめると理解が進みました。
- ラプラスメカニズムだけでなく、ガウシアンメカニズムや出力が離散であるときに使用される指数メカニズムもあるので、また試してみようと思います。
- 実問題では、何かAPIでデータを返すサービスに差分プライバシをのせて返すとか、ユーザにデータを公開するときに使えるのかと思います。Appleのようにユーザのプライバシ保護のために、データ収集するときに差分プライバシを入れて収集するという使い方もありますね。もっとこういった技術を使ってデータの公開やAPI提供が進むと良いなと思います。
参考
- A Simpler Explanation of Differential Privacy：英語ですが、Rで差分プライバシを実例している例です。回帰問題への適用もしているので触ってみるのに良いと思います。
- データ解析におけるプライバシー保護
- 差分プライバシーとは何か？ （定義 & 解釈編）：説明がとてもわかりやすかったです。