名前はまだない

データ分析とかの備忘録か, 趣味の話か, はたまた

ローカル差分プライバシー保護ついてすこし調べてみました

はじめに

データ分析におけるプライバシー保護に興味があり少しづつ勉強しています。 その中でも差分プライバシーという概念があります、前々から知っていました。 そして、あるイベントでローカル差分プライバシーという概念を知りました。 概要や利用先を調べましたので簡単にまとめました。

こちらのチュートリアルでの話が中心です。

arxiv.org

差分プライバシー

差分プライバシーは、差が小さい2つのデータセットにおいて、その差分となるデータに対して満たすべきプライバシーです。

例えば、Twitterを行っている割合を100人の人に聞いて調査することを考えます。

f:id:saltcooky:20200201222823p:plain

出典

この時、あるターゲットとなるAさん以外の99人においてTwitterを行っているかがわかっていた場合、AさんがTwitterを行っているかは、100人における情報と99人の情報から算出できてしまい、Aさんのプライバシーは保証されなくなってしまいます。

99人全ての情報を知るのは現実的ではありませんが、99人における利用割合がわかっていれば100人の利用割合との差分から、Aさんの利用状態が推定できてしまいます。

ここで、2つのデータセット D,D′の距離 d(D,D′)を、同一でないレコード数とします。  d(D,D′)=1の場合、2つのデータセットにおいて1レコードのみが異なると言えます。 この時に満たされるべき匿名性のモデルは次にようになります。

 \displaystyle{
\frac{P(y=m(q,D))}{P(y=m(q,D'))} = exp(\epsilon)

}

ここで m()はクエリqで得られてデータDに対して匿名化を施すメカニズムです。  \epsilonは正の値です。

このような匿名性が満たされる状態を、 \epsilon -差分プライバシーを満たしている状態であるといいます。

この式は、差が小さい2つのデータセットを匿名化したあとのデータの確率分布の比(差とも言える?)は \epsilon程度であることを意味しています。

そのため、 \epsilonが0に近い場合には強い匿名化が施されており、大きな値になると弱い匿名化が施されているということになります。

実際には、あるクエリにより得られた統計量に対してラプラスノイズを付加するラプラスカニズムを用いて、匿名化を行います。

もう少し詳しいことはこちらで。

qiita.com

ローカル差分プライバシー

差分プライバシーは、集約されたデータからデータ(統計量など)を取得する際に匿名化を施すものでした。 そのため、グローバル差分プライバシー(GDP)とも呼ばれています。

一方でローカル差分プライバシー(LDP)は、データを収集する際に匿名化を施すものです。

イメージはこんな感じ。

f:id:saltcooky:20200121232713p:plain

出典

この時、次のような状態が満たされている場合にローカル差分プライバシーが満たされていると言います。

 \displaystyle{
\frac{P(m(x))}{P(m(x'))} = exp(\epsilon)
}

この式は、データ xとそれに近いデータ x'の匿名化後のデータの分布は、 \epsilon程度しか異ならないことを意味しています。

匿名化を施すメカニズムは、こちらでもラプラスカニズムなどを用います。

LDPの概要についてはこちららへんに記載されています。 en.wikipedia.org

非常に概念的にはわかりやすいものですが、GDPと比べると欠点があります。

匿名化を施したデータを用いて母数の推定をする場合を考えます。

GDPでは、ラプラスノイズの大きさは O(1)程度であり、データ量によらないです。 しかし、LDPでは O(1/\epsilon)程度でありデータ量によるということを意味し、強い匿名性を保とうとすると推定には大量のデータ量が必要であることを意味します。

差分プライバシーの適用例

Google RAPPOR

RAPPORはGoogleが2014年に公開した、Chromeにおいても利用されている、LDPを保ったまま統計情報(利用ログ)を収集するためのアルゴリズムです。

こちらのGithubでソースが公開されています。

ウェブサイト上のログは、何らかのプロパティを表す長さkのビットベクトルで表現すると仮定します。

このビットベクトルに対して二段階に匿名化を行います。

一段階目は、permanent randomized responseと呼びます。

この匿名化では、特定の値vが入力された場合に同じ情報が出力されるように匿名化し、値vと匿名化後のデータの対応を保存しておきます。

これは、値が取得した際に特定のばらつきを持ったノイズをのせて複数回サーバに情報が送信された場合、取得した値が推定されてしまう可能性があります。

そのため、ある値が得られた場合に特定の値がサーバに送られると、ユーザーの実際の回答を推測できないようにすることができます。

実際には、ビット列B_iを次のようなルールに従い匿名化を行います。

 

\begin{eqnarray}
B_i' = 
  \left\{
    \begin{array}{l}
     1, & with probability \frac{1}{2}f \\
     0, & with probability \frac{1}{2}f \\
     B_i, & with probability 1-f
    \end{array}
  \right.
\end{eqnarray}

ここで、fは匿名化のためのパラメータです。

二段階目は、instantaneous randomized responseと呼びます。

permanent randomized responseで匿名化を行ったビット列の各ビットに対して匿名化を行います。

 

\begin{eqnarray}
P(S_i=0) = 
  \left\{
    \begin{array}{l}
     p & if B'_i =1 \\
     q & if B'_i =0
    \end{array}
  \right.
\end{eqnarray}

ここで p,qは、各場合に0をとる確率です。

この匿名化したビット列Sをサーバに送る形になります。

Apple

Appleは、デバイス上で入力される絵文字の分析を行うために、各デバイスから入力情報を匿名化して収集しています。

count-mean sketch (CMS)という手法を用いています。

AppleによるLDPの利用には批判があります。 1回の送信で \epsilon=1または \epsilon=2のプライバシー損失が保証されています。 しかし、Appleの実際の実装を詳しく調べたところ、実際は1日あたり最大16回のそのような送信を許可していることがわかっています。 そのため、1日のプライバシー損失は最大 \epsilon=16に相当すると言われています。

ローカル差分プライバシーと統計的仮説検定

こちらで、ローカル差分プライバシーを満たした状態の統計的仮説検定の性質を述べています。

arxiv.org

処置群と対称群において、ある状態であるかの回答割合に差があるかの仮説検定を考えます。

ある状態である場合にmと回答し、そうでない場合に0と回答してもらいます。 二つのデータサンプルA,Bを用意します。

そして、各ローカルにおいて次のようなメカニズムに従い匿名化を施します。

 

\begin{eqnarray}
\mathfrak{M}_{\epsilon,m}(x) = 
  \left\{
    \begin{array}{l}
     1, & with probability \frac{1-}{e^\epsilon+1}\frac{x}{m}\frac{e^\epsilon-1}{e^\epsilon+1} \\
     0, &other
    \end{array}
  \right.
\end{eqnarray}

匿名化を施されたデータは、サーバーに送信されます。

ここで、期待値を推定する場合には次の式を用います。

このデータを用いて処置群と対称群でデータの分布の違いを帰無仮説 H_0:P_a-P_b=d_0を検定していきます。

流れを簡単にまとめると次のようになります。

  1. \mathfrak{M}_{\epsilon,m}を用いて a_ib_iを匿名化しa_i^{bin}b_i^{bin}を得ます
  2. 匿名化したデータをサーバに送信します
  3. A,Bそれぞれの回答確率 p_A, p_Bを計算します。
  4. 帰無仮説を考えます
 
H_o^{bin}:p_A-p_B=\frac{d_0}{m}\frac{e^{\epsilon}-1}{e^{\epsilon}+1}
  1. この帰無仮説における有意水準\alphaとした、t検定を行います

この時の、検出力は次のようになります。

 
P(\theta) =1 − F \left( F^{-1}(1 − \alpha) − \frac{p _\theta}{\hat \sigma _{A+B}} \right)\\
=1 − F \left( F^{-1}(1 − \alpha) − p _\theta \sqrt{\frac{4(n_A-1)(n_B-1)}{n_A+n_B-2}}  \right) \tag{*}

ここで、 p_\theta = \frac{x}{m}\frac{e^\epsilon-1}{e^\epsilon+1} Fは累積分布関数です。

なお、収集データから推定される分散は次のように書くこともできます。

 
\hat \sigma _{A+B} = \sqrt{\frac{1_{A^{bin}} /n_A − 1^2_{A^{bin}} /n^2_A}{n_A − 1}+\frac{1_{B{bin}} /n_B − 1^2_{B^{bin}} /n^2_B}{n_B − 1})}

ここで 1_XはXにおける1の総数です。

よって、*の式は次のように変形することができます。

 
P(\theta) =1 − F \left( F^{-1}(1 − \alpha) − \frac{p \theta}{\hat \sigma _{A+B}} \right)

上記の式から特定の検出力を得るためのサンプルサイズの算出には、次式を用います。

 
n=(F^{−1}(1 − α) − F^{-1}(\beta))^2\frac{1}{2p^2 _\theta}+1

検出力関数の定義をみると、匿名化を強めると検出力が下がってしまうことを意味しています。 ここからは、実際にシミュレーションを行いどれほどサンプルが必要なのかを確かめてみます。

シミュレーションに必要な関数を用意します。 ループ関数を多用したクソコードです。

# 匿名化メカニズム
ldp_mechanism <- function(data, epsilon, m){
  res <- c()
  for(i in (1:length(data))){
    if(epsilon=="non"){
      res[i] <- data[i]/m  
    }else{
      ee <- exp(as.numeric(epsilon))
      prob <- 1/(ee+1)+data[i]/m*(ee-1)/(ee+1)    
      res[i] <- rbinom(1,size=1, prob=prob)
    }
  }
  return(res)
}

# 検出力関数
empirical_power <- function(data1, data2, epsilon, m, alpha, theta){
  sigma_est <- sqrt((sum(data1)/length(data1)-sum(data1)^2/length(data1)^2)/(length(data1)-1)+
                    (sum(data2)/length(data2)-sum(data2)^2/length(data2)^2)/(length(data2)-1))
  if(epsilon=="non"){
    p0 <- theta/m
  }else{
    ee <- exp(as.numeric(epsilon))
    p0 <- theta/m * (ee-1)/(ee+1)
  }
  beta <- qnorm(1-alpha) - p0 * 1/sigma_est
  Power <- 1 - pnorm(beta) 
  
  return(Power)
}

# 検出力のループを繰り返す
estimete_power_loop <- function(P, range_list, epsilon, m, alpha, theta){
  message(paste0(">>> epsilon:",epsilon))
  Power_list <- c()
  for(i in 1:length(range_list)){
    message(paste0(">>> N:",range_list[i]))
    
    # データ生成
    P_diff <- theta/m
    Xa <- sample(x = c(m,0), size = range_list[i], replace = T, prob = c(P, 1-P))
    Xb <- sample(x = c(m,0), size = range_list[i], replace = T, prob = c(P+P_diff, 1-P-P_diff))
    
    # 擬似LDP匿名化処理
    Xa_bits <- ldp_mechanism(Xa, epsilon = epsilon, m = m)
    Xb_bits <- ldp_mechanism(Xb, epsilon = epsilon, m = m)
    
    Power_list[i]  <- empirical_power(Xa_bits, Xb_bits, epsilon, m, alpha, theta)
  }
  return(Power_list)
}

それでは、シミュレーションを行いたいと思います。 回答で得られる値は[0, 150000]、Aで15000が回答される平均確率は0.2としました。 Bの平均確率は0.2+\theta / m = 0.2+0.04としました。 また、有意水準\alpha=0.05としました。

m <- 15000
alpha <- 0.05
theta <- 600
P <- 0.2

N_list <- c( 100, 250, 500, 750, 1000,
                     2500, 5000,7500, 10000,
                     25000, 50000,75000, 100000,
                     250000, 500000,750000, 1000000)

power_df <- data.frame(sample_size = N_list)

epsilon_list <- c(0.5, 1, 2, 4,6, "non")

for(i in 1:length(epsilon_list)){
  message(paste0(">>> epsilon:", epsilon_list[i]))
  colname <- epsilon_list[i] %>% as.character()
  power_df <- power_df %>% 
    mutate(!!colname := estimete_power_loop(P, N_list, epsilon_list[i], m, alpha, theta))
}

結果をグラフ化してみます。 検出力の一般的な基準である0.8に直線をひきました。

power_df %>% 
  pivot_longer(-sample_size,names_to = "epsilon", values_to = "power") %>% 
  ggplot(aes(x = log10(sample_size), y = power, color = epsilon)) + geom_line()+
  labs(title=paste0("匿名化されたデータにおける検出力:GAP=", theta), x= "サンプル数(対数)", y="検出力") + 
  theme_gray (base_family = "HiraKakuPro-W3")+
  scale_y_continuous(breaks=seq(0.0,1.0,by=0.2))+
  geom_hline(yintercept=0.8, linetype="dashed", colour="red") 

匿名化を強めると同じ検出力を得るのに多くのデータが必要なことがわかります

他のGap:\thetaの場合の検出力の状態も出力してみます。

f:id:saltcooky:20200206001937p:plain

匿名化の強さ \epsilonが強くなっていくとともに、検出力0.8を満たすためのサンプル数が増加していることがわかります。

特に0.5の場合は匿名化なしの場合と比べて10倍以上のデータが必要なことがわかります。 また、6程度で匿名化なしの時と同程度のサンプルサイズがあれば、検出力0.8を満たすことができることわかります。

他のGAPの大きさを設定した場合の結果も見てみます。

f:id:saltcooky:20200206001953p:plain

f:id:saltcooky:20200206002003p:plain

f:id:saltcooky:20200206012413p:plain

匿名化が強い状態でより分布の差が小さい場合を検出しようとすると、データが大量に必要なことがわかります。

ローカル差分プライバシーと機械学習

ローカル差分プライバシーを満たした状態で機械学習を行う手法はいくつか提案されています。

その中でもこちらの論文では、ローカル差分プライバシーを満たしたデータによるロジスティック回帰が紹介されていました。

arxiv.org

基本的な考え方は、以下をパラメータが収束するまで繰り返します。

  1. 各ノードがローカルでノイズを加えたデータを生成して、モデルを学習する
  2. 出来上がったモデルをサーバに送信する
  3. 送信されたモデルのパラメータを平均化し、各ノードに返す
  4. 返されたパラメータをローカルで再学習する(データの数が違うため、重み付きで更新する)

実装はまたの機会に行いたいと思います。

参考