[CCS 2016] Deep Learning with DP - (1)

논문 제목: Deep Learning with Differential Privacy

출처: https://arxiv.org/abs/1607.00133

 

 사실 Differential Privacy(DP)는 ML 분야가 아니라 DB 쪽에서 사용되던 기법입니다. 이번에 다룰 논문의 주된 내용은 이 DP를 Deep Learning에 적용하여 privacy preserving을 꾀하는 것인데, 어떻게 DP를 Deep Learning에 이식할 수 있었는지, DP로 인하여 model의 성능이 크게 저하되지는 않았는지, 그리고 DP가 computation cost에는 어느 정도 영향을 미치는지 확인해보도록 하겠습니다. 우선, DP가 무엇인지에 관하여 간략하게 언급하도록 하겠습니다.

 

1. Differtial Privacy

 

$\text{Definition 1}$ [$(\epsilon, \delta)$-Differential Privacy]

 어떠한 domain이 $\mathcal{D}$이고 range가 $\mathcal{R}$인 randomized mechanism $\mathcal{M}: \mathcal{D} \rightarrow \mathcal{R}$가 있다고 가정하자. 만약 임의의 두 adjacent inputs $d, d' \in \mathcal{D}$과 outputs의 임의의 subset $S \subset \mathcal{R}$에 대하여 $\textbf{P} (\mathcal{M}(d) \in S) \leq e^{\epsilon} \textbf{P} (\mathcal{M(d')} \in S) + \delta$를 만족할 경우, 우리는 이러한 $\mathcal{M}$가 $(\epsilon, \delta)$-differential privacy를 만족한다고 이야기한다.

 

 여기에서, 두 inputs $d, d'$가 adjacent하다는 것은 dataset 전체에서 딱 한 가지 data가 다르다는 것입니다. ($d$가 갖지 못한 data 1개를 $d'$가 가지고 있거나, 혹은 그 반대) DP가 처음 등장하였을 때에는 $\delta$ term이 없었고, 그냥 $\epsilon$-DP라고 불렸습니다. 그러면 정의가 $\frac {\textbf{P} (\mathcal{M}(d) \in S)} { \textbf{P} (\mathcal{M(d')} \in S)}  \leq e^{\epsilon}$로 정리되는데, 사실 이쪽이 더 직관적입니다. (한 개의 data가 차이날 때, probability의 log-difference는 $\epsilon$ 이하이다.) 하지만 현재는 $\text{Definition 1}$과 같은 정의가 통용되고 있는데, 이는 2006년에 발표된 Dwork et al.의 논문[1]에서 제안된 것입니다. 여기에서 $\delta$는 "$\delta$의 확률로 $\epsilon$-DP가 성립하지 않을 수 있다"는 것을 의미하며, 그래서 더 여유 있게 bound를 잡은 것입니다. (일반적으로 $\delta < \frac {1} {|d|}$인 경우를 상정합니다.) DP는 다음과 같은 특징을 지니고 있는데, 이미 잘 알려진 것들이므로 별도의 증명 없이 사용하도록 하겠습니다.

 

(1) Composability

 어떠한 mechanism $\mathcal{M}$의 모든 구성 요소가 DP를 만족한다면, $\mathcal{M}$ 그 자체 역시 DP를 만족한다. (이 성질 때문에, layer-wise하게 DP가 보장된다면 해당 model 전체가 DP를 만족한다고 이야기할 수 있습니다.)

 

(2) Group Privacy

 약간의 성능 저하를 감수하는 대신, correlated input들이 존재하는지 확인할 수 있다. (특정 Client $K$가 가지고 있는 dataset의 크기를 $|K|$라고 가정합시다. 원래 $\epsilon$-DP는 1개의 data가 차이나는 case에서 정의된 것입니다. 하지만 $|K|$개의 data가 차이나는 경우를 확인하여야 한다면, 위 정의에서 $e^{\epsilon}$을 $e^{|K| \epsilon}$으로 바꿈으로써 $(|K| \epsilon)$-DP를 만족시킬 수 있고, 이러한 방식을 통하여 Client $K$가 가진 dataset 전체에 대한 DP를 고려할 수 있습니다.)

 

(3) Auxiliary Information에 대한 Robustness

 적대자가 어떠한 추가적인 정보를 가지고 있더라도 privacy preserving이 보장된다. (즉, Linkage Attack이 불가능합니다.)

 

2. $(\epsilon, \delta)$-DP mechanism을 이식하기

 

 그렇다면, $(\epsilon, \delta)$-DP를 만족하는 mechanism $\mathcal{M}$을 어떻게 프로그래밍할 수 있을까요?$\mathcal{M}$이라는 추상적인 것을 $f: \mathcal{D} \rightarrow \mathcal{R}$라는 deterministic real-valued function으로 근사하여야 하는데, 이는 보통 noise를 추가하는 방식으로 진행됩니다. 이때 noise는 $S_f := \max \{ f(d) - f(d') \mid d, d' \in \mathcal{D} \text{ are adjacent}\}$로 정의되는 $f$의 sensitivity로 calibration됩니다.

 

 가령 Gaussian noise를 고려한다면, $\mathcal{M}(d) := f(d) + \mathcal{N} (0, S_f^2 \cdot \sigma^2)$로 정의되고, 이러한 $\mathcal{M}(d)$는 $\delta \leq \frac {4} {5} e^{-\frac {(\sigma \epsilon)^2} {2}}$, $0 < \epsilon < 1$인 경우 $(\epsilon, \delta)$-DP를 만족합니다. (물론, 이러한 $(\epsilon, \delta)$ 조합은 무수히 많습니다.) 때로는 Laplacian noise를 사용하기도 하는데, 이 경우에는  $\mathcal{M}(d) := f(d) + \text{Lap} (0, \frac {S_f} {\epsilon})$로 정의되며, 항상 $\epsilon$-DP를 만족합니다. (Laplace 분포에서 mean이 $0$인 경우에는 그냥 생략하는 관습이 있는 것 같습니다. 즉, $\text{Lap} (\frac {S_f} {\epsilon})$도 같은 의미입니다.) 이외에도, exponential mechanism과 같은 다른 additive noise mechanism도 존재하며, $f$의 sensitivity를 계산할 때 $\ell_1$-norm이 아닌 다른 norm을 사용하는 등 다양한 variation이 존재합니다. 해당 논문은 Gaussian noise를 주로 사용합니다.

 

 다음 포스트에서는 DP를 SGD 알고리즘에 적용하는 과정을 이야기해보겠습니다.

 

 

 

참고 자료:

[1] [EUROCRYPT 2006] https://link.springer.com/chapter/10.1007/11761679_29