기술 요약: 미세한 척도로서의 예측 가능성 (Predictability)

문제 정의

차분 프라이버시(Differential Privacy, DP)는 데이터셋 내의 단 한 명을 제외한 나머지 모든 구성원에 대한 완전한 지식을 가진 최악의 공격자를 대상으로 엄격한 보장을 제공하는 현재의 골드 표준이다. 그러나 이러한 최악의 경우를 가정하는 특성은 심각한 프라이버시-정확도 트레이드오프를 초래하며, 이로 인해 실무자들은 약한 보장을 제공하는 큰 프라이버시 파라미터($\epsilon$)를 적용하게 된다. 또한, $N-1$명의 개인을 위협하는 최악의 가정은 현실적이지 않은 경우가 많다. 실제 상황에서 데이터 침해는 일반적으로 데이터셋의 특정 부분이나 샤드(shard)를 침해하거나 전체 데이터셋을 침해한다.

기존의 프라이버시 정의는 공격자의 구체적인 지식 구조를 무시하거나 특정 민감한 쿼리에 맞춤화된 미세한 보장을 제공하지 못한다. 저자들은 공격자가 생성된 확률 과정(stochastic process)에 의한 데이터의 일부를 침해하고, 남겨진 알 수 없는 개인들에 대한 민감한 정보를 예측하려고 시도하는 시나리오를 현재의 메트릭들이 적절히 다루지 못한다고 주장한다.

방법론: 예측 가능성을 통한 프라이버시

1. 예측 가능성 프레크레임워크 (The Predictability Framework)

• 공격자의 핵심 지식 ($C(S)$): 데이터셋 $S$로부터 생성된 확률 과정 $P$에 의한 데이터 포인트들의 시퀀스로 모델링된다. 이는 현실적인 침해 시나리오(예: 무작위 서버 샤드 침해)를 포착한다.
• 민감한 쿼리 ($Q$): 침해되지 않은 집합 $S \setminus C(S)$에서 균등하게 추출된 미지의 개인 $x$에 대해 공격자가 추론하고자 하는 함수 $q: X \to Y$의 가족(family)을 나타낸다.
• 메트릭 정의: 예측 가능성($\gamma$)은 알고리즘의 출력 $A(S)$를 관찰한 후, 공격자가 $C(S)$만을 사용하여 가졌던 예측 능력과 비교했을 때 $q(x)$를 예측하는 능력이 얼마나 증가했는지를 측정한다. 형식적으로, 이는 $A(S)$를 봄으로써 공격자가 얻게 되는 손실(예: log loss 또는 squared loss)의 감소량을 경계 짓는다.
• DP와의 비교: 모든 개인의 사후 믿음(posterior beliefs) 변화를 제한하는 DP와 달리, 예측 가능성은 침해된 집합 $C(S)$에 대한 미지의 개인 집합에 대한 정보 누출을 제한한다. 저자들은 예측 가능성과 DP가 일반적으로 서로 비교 불가능함을 증명한다. 즉, 하나가 작더라도 다른 하나는 클 수 있다. 그러나 최악의 경우($N-1$명이 침해된 경우)에는 예측 가능성이 상호 정보량 DP(Mutual Information DP)를 함의한다.

2. 일반 적률 방법(GMM)을 통한 점근적 분석

대규모 머신러닝 시스템에 대한 예측 가능성을 계산하기 위해, 저자들은 **일반 적률 방법(Generalized Method of Moments, GMM)**을 사용한다.

• 가정: 침해된 데이터는 정적(stationary)이고 에르고딕(ergodic)하며 $\alpha$-mixing 성질을 가진 프로세스에 의해 생성된다. 알고리즘의 출력은 노이즈가 포함된 모멘트 조건(예: $A(S) = \lambda + \Delta$, 여기서 $\lambda$는 모집단 모멘트, $\Delta$는 노이즈)으로 모델링된다.
• 효율적인 추정량: 베이즈 최적 추정량이 점근적으로 효율적인 GMM 추정량과 일치한다는 가정(Bernstein–von Mises 정리) 하에, 저자들은 공격자의 예측 오차의 점근적 거동을 도출한다.
• 핵심 결과 (정리 3.6): 점근적 예측 가능성은 민감한 쿼리와 알고리즘의 모멘트 조건 사이의 **정준 상관관계(canonical correlation)**에 의해 결정되며, 이는 노이즈 감쇄 항에 의해 조정된다. 구체적으로, 예측 가능성은 노이즈 분산이 증가하거나 쿼리와 방출된 통계량 사이의 상관관계가 감소함에 따라 감소한다.
• 계산 가능성: 데이터셋과 정적 분포가 주어지면, 예측 가능성 경계를 계산하는 데 필요한 모든 항(분산, 공분산, 정준 상관관계)을 효율적으로 계산할 수 있다.

3. ERM을 위한 노이즈 캘리브레이션

이 프레임워크는 경험적 위험 최소화(ERM)에 적용된다. 저자들은 다음과 같은 예측 가능성 캘리브레이션 출력 섭동 기법을 도출한다:

• 등방성(isotropic) 노이즈를 추가하는 대신, 노이즈 공분산을 손실 곡률, 그래디언트 공분산 및 공격자의 프로세스에 적응시켜 조정한다.
• 선형 회귀의 경우, 이 기법은 경험적 손실이 크거나 데이터가 희소한 방향으로 더 많은 노이즈를 추가함으로써, 동일한 수준의 예측 가능성에 대해 등방성 섭동보다 개선된 정확도 경계를 제공한다.

주요 기여 및 결과

1. 예측 가능성의 정의: 공격자의 확률적 지식과 특정 쿼리 가족을 통합하여, 미지의 개인에 대한 정보 이득을 측정하는 새로운 프라이버시 메트릭을 정의하였다.
2. DP와의 비교 불가능성: 예측 가능성과 DP가 일반적으로 비교 불가능함을 보여주는 이론적 증명을 제시하였다. 다만, 최악의 설정(단 한 명을 제외한 모두가 침해된 경우)에서는 예측 가능성이 상호 정보량 DP를 함의한다.
3. GMM 기반 분석: 정적, 에르고딕, mixing 프로세스에 의해 생성된 데이터에 대한 점근적 예측 가능성을 분석하는 일반적인 프레임워크를 구축하였다. 이 분석은 예측 가능성이 쿼리와 알고리즘의 모멘트 조건 사이의 정준 상관관계에 의해 결정됨을 밝혀냈다.
4. 개선된 메커니즘: 특정 쿼리, 손실 함수 및 공격자 프로세스에 따라 노이즈를 캘리브레이션하는 ERM용 출력 섭동 기법을 도출하여, 등방성 노이즈보다 더 나은 정확도-프라이버시 트레이드오프를 제공한다.
5. 확장성: 이 프레임워크를 쿼리 가족(유한, 선형, Lipschitz) 및 침해된 데이터를 생성하는 프로세스를 알 수 없는 시나리오(프로세스 군에 대한 최악의 경우를 취함으로써)로 확장하였다.

의의 및 주장

본 논문은 예측 가능성이 최악의 경우를 가정하는 DP의 한계를 해결하며, 특정 민감한 정보와 공격자 모델에 맞춤화된 더 미세한 수준의 프라이버시 메트릭을 제공한다고 주장한다.

• 상보성: 이 접근 방식은 DP와 상보적인 것으로 제시된다. DP와 함께 사용하여 특정 쿼리에 대한 더 세밀하고 미묘한 프라이버시 제어를 제공할 수 있다(예: 부분적 데이터 침해와 같은 현실적인 공격자 모델).
• 실용적 유용성: 설계자가 특정 데이터 서브셋과 특정 쿼리에 대한 프라이버시 누출을 정량화할 수 있게 함으로써, 최악의 경우를 가정하는 DP의 가정이 지나치게 비관적인 시나리오에서 더 적은 노이즈(및 더 높은 정확도)를 사용할 수 있도록 의사결정을 돕는다.
• 이론적 토대: 본 연구는 통계적 추정 이론(GMM, 정준 상관관계)과 프라이버시 사이의 엄격한 연결 고리를 구축하며, 대규모 학습 시스템의 프라이버시를 분석할 수 있는 계산 가능한 프레임워크를 제공한다.

저자들은 본 프레임워크가 점근적 경계와 효율적인 계산을 제공하지만, 예측 가능성에 대한 적응형 합성 규칙(adaptive composition rules)을 개발하고 비점근적 영역에서 알 수 없는 프로세스를 더 강력하게 다루기 위한 향후 연구가 필요함을 언급하며 신중한 입장을 유지한다.