Private Prediction via PAC Privacy

기술 요약: PAC 프라이버시를 통한 프라이빗 예측 (Private Prediction via PAC Privacy)

문제 정의
머신러닝 모델은 모델 가중치 대신 예측값만을 사용자에게 노출하는 블랙박스 서비스 형태인 API 뒤에 점점 더 많이 배치되고 있습니다. 이러한 배포 패턴은 모델 파라미터가 아닌 모델 출력의 프라이버시를 보호하는 **프라이빗 예측(private prediction)**을 촉발합니다. 차분 프라이버시(Differential Privacy, DP)가 표준이지만, 이 맥락에서는 한계가 있습니다. DP는 최악의 경우의 민감도(인접한 데이터셋 간의 출력 변화 최대치)를 기준으로 노이즈를 조정합니다. 비볼록(non-convex) 모델(예: 심층 신경망)의 경우, 타이트한 민감도 경계를 계산하는 것은 매우 어렵습니다. 결과적으로 DP 기반의 프라이빗 예측은 "샘플링 및 집계" 방식(PATE와 같은)에 의존하거나 입력 독립적인 노이즈로 회귀하게 되며, 이는 높은 쿼리 볼륨이나 엄격한 예산 하에서 유틸리티가 급격히 무너지는 가혹한 프라이버시-유틸리티 트레이드오프를 초래합니다.

또한, 기존의 순차적 릴리스 프라이버시 프레임워크는 적응형 및 적대적 쿼리(adaptive and adversarial querying) 환경에서 실패하는 경우가 많습니다. 현실적인 시나리오에서 신뢰할 수 없는 사용자는 이전 출력의 이력을 바탕으로 정보 누출을 극대화하도록 미래의 쿼리를 선택할 수 있습니다. 표준 합성 정리(composition theorems)는 적응성 하에서 실패하거나, 쿼리 수에 따라 이차적으로 증가하거나, 혹은 특정 예측기의 안정성 이점을 버리고 입력 독립적인 DP 스타일의 노이즈로 회귀합니다.

방법론
본 논문은 효율적인 적응형 합성을 해결하기 위해 PAC(Probably Approximately Correct) 프라이버시를 통한 프라이빗 예측 프레임워크를 제안합니다.

1. PAC 프라이버시 프레임워크: DP와 달리, PAC 프라이버시는 인스턴스 기반입니다. 이는 특정 입력 분포($P_S$) 하에서의 블랙박스 시뮬레이션을 통해 데이터 처리 함수의 안정성을 측정합니다. 이는 비밀 입력 $S$와 출력 $R$ 사이의 상호 정보량(Mutual Information, MI)을 제한함으로써 프라이버시 누출을 제어합니다. 안정적인 함수는 프라이버시를 위해 훨씬 적은 노이즈를 필요로 합니다.
2. 사후 확률 인식 적대적 합성 (Posterior-Aware Adversarial Composition): 본 논문의 핵심적인 이론적 기여는 지속되는 비밀(동일한 훈련 세트 $S$가 모든 쿼리에 사용됨)을 가진 적응형, 적대적 쿼리를 처리하는 새로운 합성 정리를 제공하는 것입니다.
   • 적응형 노이즈 캘리브레이션: 큐레이터는 "믿음 상태(belief state)"—상호작용 이력이 주어졌을 때의 비밀 $S$에 대한 사후 분포—를 유지합니다.
   • 메커니즘: 각 단계 $t$에서, 적응형 쿼리 $M_t$를 받으면 큐레이터는 현재 사후 믿음 $P_{t-1}$에 조건화된 단계별 MI 예산 $b_t$를 만족하기 위해 필요한 노이즈 공분산 $\Sigma_t$를 계산합니다.
   • 베이지안 업데이트: 노이즈가 섞인 응답 $R_t$를 릴리스한 후, 큐레이터는 베이즈 규칙을 사용하여 사후 믿음을 업데이트합니다.
   • 정리: 저자들은 이 메커니즘 하에서, 적대적 적응성 하에서도 전체 MI 누출이 선형적으로 축적됨($I(S; R_{1:T} \le \sum b_t$)을 증명합니다. 이는 PAC 프라이버시의 인스턴스 기반 유틸리티를 보존하면서 엄격한 선형 합성 경계를 제공합니다.
3. ML을 위한 구체적 구현:
   • 입력 분포: 비밀 $S$는 유니버스 $U$의 무작위 부분 집합이며, 각 지점이 포함될 확률은 50%입니다. 계산 가능성을 높이기 위해, 서포트(support)는 $m=128$개의 유한한 부분 집합 모음으로 제한됩니다.
   • 오프라인 전처리: 매 쿼리마다 재학습하는 것을 피하기 위해, $m$개의 모델을 $m$개의 부분 집합에 대해 오프라인으로 학습합니다. 온라인 쿼리는 이 $m$개의 모델에 대한 추론을 실행하고, 예측을 집계하며, 캘리브레이션된 노이즈를 추가하는 과정을 포함합니다.
   • 출력 안정화: 시스템은 소프트 확률(soft probabilities)이 아닌 **하드 예측(hard predictions, 원-핫 레이블)**을 프라이베이트화합니다. 하드 예측은 서로 다른 훈련 부분 집합 간에 더 안정적이어서, 출력 분산을 낮추고 더 적은 노이즈를 요구합니다.
4. 프라이빗 모델 증류 (Private Model Distillation): 유한한 프라이버시 예산이 소진된 후에도 무제한 쿼리를 가능하게 하기 위해, 본 논문은 프라이빗 예측으로부터 "학생(student)" 모델을 증류하는 방법을 제안합니다.
   • 신뢰도 필터링: 노이즈가 섞인 예측에 통계적 테스트를 적용하여, 학생 모델을 학습시키기 전에 저신뢰도(잠재적으로 잘못 레이블링된) 샘플을 필터링합니다. 이는 증류된 모델이 고품질 레이블로만 학습되도록 보장하며, 잘못 레이벨링된 데이터를 유지할 확률을 제한합니다.

주요 결과
표 형식, 비전(CIFAR-10, CIFAR-100), 텍스트(IMDb, AG News) 모달리티에 걸친 실험은 다음과 같이 본 접근 방식의 효능을 입증합니다:

• 타이트한 예산에서의 높은 유틸리티: CIFAR-10에서, 이 방법은 쿼리당 MI 예산이 $2^{-32}$일 때 87.79%의 정확도를 달성합니다. 이를 통해 멤버십 추론 공격(MIA) 성공률을 **51.08%**로 엄격히 제한하면서 백만 번의 쿼리를 수행할 수 있습니다. 이 보증은 $(0.04, 10^{-5})$-DP와 유사합니다.
• 확장성: 시스템은 MIA 보증인 $(1, 10^{-5})$-DP에 도달하기 전까지 약 4억 7,700만 번의 쿼리를 지원합니다. 반면, DP 기반 프라이빗 예측은 입력 독립적 민감도 제약으로 인해 쿼리 수가 증가함에 따라 무작위 추측 수준으로 성능이 저하됩니다.
• 증류 성능: CIFAR-10 텔러(teacher)로부터 210,000개의 프라이빗 예측을 추출하여 공개 데이터인 ImageNet 서브셋(CINIC-10)을 레이블링했을 때, 증류된 학생 모델은 CIFAR-10에서 91.86%의 정확도를 달성합니다. 이는 프라이빗 텔러보다 우수하며, 증류 과정에서 레이블링된 공개 데이터를 전혀 필요로 하지 않으면서도 MIA 보증인 $(0.02, 10^{-5})$-DP를 충족합니다.
• 강건성: 이 방법은 단계별 MI 예산이 매우 작은 값($2^{-32}$)으로 타이트해지더라도 강력한 유틸리티를 유지하는데, 이는 모델 예측의 내재적 안정성 덕분인 것으로 분석됩니다.

의의 및 주장
본 논문은 적응형 및 적대적 조건에서도 프라이버시를 보존하면서도 매우 유용한 프라이빗 예측을 가능하게 함으로써 프라이빗 머신러닝의 중요한 간극을 메운다고 주장합니다.

• 이론적 돌파구: 지속되는 비밀을 가진 PAC 프라이버시에 대한 최초의 적대적 합성 정리를 제공하며, 적응형 쿼리 하에서도 MI가 선형적으로 축적됨을 증명했습니다. 이는 적응성 하에서 실패하거나 입력 독립적인 노이즈를 요구했던 이전 연구들과 대조됩니다.
• 실용적 생존 가능성: 예측 안정성을 활용하여 최소한의 노이즈로 출력을 프라이베이트화할 수 있음을 보여주며, 견고한 학습(낮은 분산)이 자연스럽게 더 나은 프라이버시-유틸리티 트레이드오프로 이어지는 "윈-윈(win-win)" 시나리오를 제시합니다.
• DP 학습의 대안: 이 연구는 프라이빗 예측과 증류를 통해 프라이버시를 보존하는 모델을 출시하는 경로를 제시하며, 특히 위협 모델이 모델 가중치 공개가 아닌 API 기반 예측과 일치하는 경우, DP-SGD보다 더 유리한 유틸리티 프로필을 제공합니다.
• 한계: 저자들은 이 접근 방식이 특정 입력 분포(서브샘플링)에 의존하며, $m$개의 모델을 사전 학습하는 데 드는 계산 비용이 발생한다는 점을 인정합니다. 또한, 이론적 보증은 시스템 분포를 완전히 아는 계산적으로 무제한인 적대자를 가정하지만, 이것이 현실적인 설정으로 자연스럽게 확장될 수 있다고 주장합니다.

요약하자면, 본 논문은 파라미터 프라이버시에서 출력 프라이버시로 초점을 전환하고 PAC 프라이버시를 통한 인스턴스 기반 안정성을 활용함으로써, DP 기반 방법이 유틸리티를 희생하지 않고는 달성할 수 없는 수백만 건의 쿼리를 강력하고 증명 가능한 프라이버시 보증과 함께 서비스할 수 있다고 주장합니다.