Differential Privacy (6. One-shot Releases)
본문은 James Honaker과 Salil Vadhan의 Computer Science 208: Applied Privacy for Data Science 강의의 One-shot Releases를 요약한 글입니다.
이번 장에서는 Data Analyst와 데이터를 공유할 때, query들에 대한 응답을 제공해주는 것이 아니라 Privacy를 보존하면서 데이터 자체의 공유가 가능하도록 하는 One-shot Release에 대해 살펴보겠습니다.
앞서 라플라스 분포를 따르는 노이즈를 활용하는 Laplace Mechanism과 다양한 𝛆-DP의 확장에 대해 살펴 보았습니다. 하지만 Laplace Mechanism의 경우 count, sum과 같이 Global Sensitivity 값이 낮은 query에 대해서만 효과적으로 나타납니다. 그렇다면 Global Sensitivity가 아닌 아래와 같이 정의된 Local Sensitivity를 활용하여 DP를 설계하면 이 문제는 해결되는 것일까요?
그렇지 않습니다. Local Sensitivity에 비례하는 노이즈를 추가하는 경우에는 DP 자체가 성립하지 않기 때문입니다. 하나의 query에 대한 최악의 경우만을 가정하는 Laplace Mechanism, DP의 조건이 성립하지 않는 Local Sensitivity 활용 등의 방법들을 보완할 수 있는 Smooth Sensitivity, Restricted Sensitivity 등을 활용한 DP는 다양하게 연구되고 있습니다.
그 중 하나가 Approximate DP입니다. 앞 단원에서 Approximate DP는 𝛅를 기존의 𝛆-DP 부등식의 우변에 추가하여 𝛆-DP를 만족하는 확률이 1-𝛅가 되게 만드는 방법으로 볼 수 있다는 점을 확인했습니다. 이 Approximate DP에서는 아래와 같은 Advanced Composition Theorem이 성립하게 됩니다.
만약 k개의 query에 대해 Laplace Mechanism을 적용하고, 이 때의 각 query는 모두 Global Sensitivity 값이 1이라고 가정해 봅시다. 위의 Advanced Composition Theorem을 적용하게 된다면, 각 query에 대한 𝛆` 값은 1/sqrt(k) 수준으로 나타날 것입니다. 즉, 𝛆의 역수로 나타내는 노이즈 수준은 sqrt(k) 수준으로 나타나게 됩니다.
k에 따른 error E의 변화를 그래프로 나타내면 아래와 같습니다. k가 커질수록, 즉 query의 개수가 늘어날수록, DP가 가능한 상태를 유지하기 위해서 Error는 커지게 되고 이는 정확한 추론을 위한 정확도가 낮아지게 만듭니다. 일종의 Trade-off가 발생하게 되는 것입니다.
Histogram
이렇게 여러 개의 query를 단순히 종합하는 Composition보다 더 좋은 방법이 존재합니다. 대표적인 예는 histogram을 활용하는 방법입니다. 아래와 같이 겹치지 않는 구간을 나누고 해당 구간에 속하는 원소의 개수에 노이즈를 추가하게 되면 𝛆-DP가 성립하게 됩니다.
위와 같이 설계된 histogram을 활용해 k개의 임의의 query를 유한한 data universe에 적용할 경우, 아래의 error 수준만큼 query에 대한 대답을 제공할 수 있습니다.
Synthetic Data
Data Analyst에게 Data에 대한 정보를 줄 때 query에 대한 직접적인 대답이 아니라 기존 Data의 특성은 유지하면서 그 정보를 종합적으로 나타낼 수 있는 Synthetic Data를 제공하는 방식도 가능합니다. 이 때 제공되는 Synthetic Data는 기존 데이터와 같은 구조를 가져야하고 기존 데이터가 가진 여러 개의 통계적인 특성을 가져야만 합니다. 그리고 당연히 differentially private 해야 할 것입니다.
Synthetic Data를 구성하는 데에는 많은 방법이 사용될 수 있는데 앞서 소개한 DP Histogram 방법을 활용할 수 있습니다. DP 성질은 유지하면서 a_j 값들이 0 이상의 정수로 나타나도록 강제하기 위해 아래와 같은 방식으로 Histogram을 구성할 수 있습니다.
이렇게 만들어진 Histogram은 기존의 Histogram과는 q_j가 0으로 나타날 때 이를 처리하는 방법에서 차이를 보이고 (𝛆, 𝛅)-DP 성질을 만족합니다. 데이터의 개수가 많아지더라도 위의 방법에서의 계산은 개수가 아닌 차원에 비례해서 증가하며 Error 역시 데이터의 개수와 무관하게 𝛆과 𝛅에 의해 결정됩니다. 하지만 데이터의 개수가 많아지면 그만큼 데이터가 분산되기 때문에 노이즈의 영향이 더 커지게 되고 데이터의 실질적인 사용에 있어 어려움이 생기게 됩니다.
Private Multiplicative Weights
여러 개의 query를 한정된 privacy budget 안에서 모두 적용하는 것 자체가 비효율적이라는 비판도 있습니다. 노이즈를 삽입해야 할 query와 그렇지 않고 이전의 결과를 그대로 사용해도 무관한 query로 구분해서 privacy budget을 최대한 활용하겠다는 방법이 Private Multiplicative Weights 방법입니다.
Private Multiplicative Weights 방법에서는 여러 개의 query들에 대해 아래와 같이 score function을 사용해서 synthetic data의 업데이트 여부를 결정합니다.
이와 같이 설계된 알고리즘은 (𝛆, 𝛅)-DP 성질을 만족하지만 그 계산 시간이 데이터와 query 집합에 대해 지수적으로 증가하기 때문에 Integer Programming을 활용하여 휴리스틱 방법을 통해 계산 시간을 줄여주는 Dual Query 방법이 제시되기도 하였습니다.
