Optimal Fairness under Local Differential Privacy

기술 요약: 로컬 차분 프라이버시 하에서의 최적 공정성

문제 정의
머신러닝 모델은 고위험 결정(예: 인종, 성별과 같은 민감한 속성)을 위해 민감한 속성에 점점 더 의존하고 있으며, 이는 공정성과 프라이버시에 대한 우려를 불러일으킵니다. 차분 프라이버시(DP)가 프라이버시의 표준이지만, 중앙 집중형 DP는 잠재적으로 불공정성을 악화시킬 수 있다는 것이 밝혀졌습니다. 이와 대조적으로, 데이터가 사용자 기지를 떠나기 전에 섭동(perturbation)되는 로컬 차분 프라이시(LDP)는 공정성과의 상호작داً에 대해 아직 충분히 탐구되지 않았습니다. 기존의 LDP 기반 공정성 접근 방식은 종종 일반화된 무작위 응답(GRR) 또는 무작위 응답(RR)과 같은 특정 메커리즘에 의존하며, 이진 민감 속성에 국한되는 경우가 많습니다. 본 논문이 다루는 핵심 문제는 데이터 불공정성을 최소화하면서도 유의미한 유용성을 유지하도록 LDP 메커니즘을 어떻게 최적으로 설계할 것인가이며, 이를 위해 이진 및 다중 값 민감 속성 모두에 대해 적용 가능해야 합니다. 또한, 이러한 데이터 불공정성의 감소가 어떻게 분류 공정성 개선으로 이어지는지를 이론적으로 확립하는 것을 목표로 합니다.

방법론
저자들은 모델 학습 전에 민감한 속성을 최적의 L립 메커니즘을 사용하여 섭동하는 전처리 프레임워크를 제안합니다. 방법론은 이론적 도출과 경험적 검증으로 나뉩니다:

1. 최적 메커니즘 도출:

   • 이진 속성: 이진 민감 속성($A \in \{0, 1\}$)에 대해, 저자들은 **폐쇄형 최적해(closed-form optimal solution)**를 도출합니다. 이들은 고정된 프라이버시 예산 $\epsilon$ 하에서, 섭동된 데이터셋의 데이터 불공정성과 원본 데이터셋의 비율을 최소화하는 문제로 정식화합니다. 최적의 메커리즘은 데이터 분포(특히 속성에 따른 레이블의 조건부 확률)와 프라이버시 파라미터에 따라 달라짐이 입증되었습니다. 표준 RR과 달리, 최적의 메커리즘은 두 클래스를 반드시 대칭적으로 처리하지 않습니다. 즉, 어떤 클래스가 더 빈번하거나 차별적인지에 따라 실제 값을 보고할 확률을 조정합니다.
   • 비이진 속성: 다중 값 속성($A \in [k]$)의 경우, 문제는 **민-맥스 선형 분수 계획법(min-max linear fractional program)**으로 재정식화됩니다. 목적 함수는 다음 제약 조건 하에서 데이터 불공정성 지표(특히 정의 1, $\Delta$)를 최소화하는 것입니다:
     • $\epsilon$-LDP 제약 조건.
     • 행 확률 합계가 1인 제약 조건(row-stochastic constraints).
     • 진실성 제약 조건(정확하게 보고할 확률 $\ge$ 잘못 보고할 확률).
     • 유용성 제약 조건(전체 오류 확률을 임계값 $\zeta$로 제한).
       이 최적화 문제는 분기 한정법(branch-and-bound method)을 사용하여 수치적으로 해결됩니다.

2. 분류 공정성과의 이론적 연결:
   본 논문은 데이터 불공정성을 최소화하는 것과 분류 불공정성을 줄이는 것 사이의 이론적 연결 고리를 구축합니다. 저자들은 차별-정확도(DA) 최적 분류기—즉, 정확도와 차별성 측면에서 다른 분류기에 의해 엄격하게 지배되지 않는 분류기—라는 개념을 도입합니다. 저자들은 DA-최적 분류기에 대해, 낮은 불공정성(구체적으로 낮은 $\Delta'$)을 가진 데이터로 학습하는 것이 결과적인 분류기의 통계적 패리티 격차(statistical parity gap)를 줄이는 것을 보장함을 증명합니다.

3. 실험적 검증:
   제안된 최적 메커리즘(OPT)은 다양한 데이터셋(Adult, LSAC, COMPAS, Bank, Student Performance, German Credit)에 대해 LightGBM 및 로지스틱 회귀를 사용하여 평가되었습니다.

   • 베이스라인: OPT는 표준 LDP 메커니즘(GRR/RR, Subset Selection) 및 최신 공정성 개입 방법(FairProjection, FairBalance)과 비교됩니다.
   • 지표: 성능은 정확도(Accuracy), 통계적 패리티($\Delta_{SP}$), 등가 기회($\Delta_{EO}$), 평균 등가 오차($\Delta_{MEO}$)를 통해 측정됩니다.

주요 기여

• 최적 메커리즘 설계: 본 논문은 이진 민감 속성에 대한 최초의 폐쇄형 최적 LDP 메커니즘과 데이터 불공정성을 최소화하기 위한 다중 값 속성용 추적 가능한 수치적 프레임워크를 제공합니다.
• 이론적 정당성: LDP 전처리를 통해 데이터 불공정성을 줄이는 것이 분류 불공정성 감소로 직접 이어진다는 것을 증명함으로써, 프라이버시 보호 전처리와 다운스트림 분류 공정성 사이의 간극을 메웁니다.
• 경험적 우월성: 제안된 OPT 메커니즘은 기존 LDP 메커리즘(GRR, SS)보다 불공정성을 줄이는 데서 일관되게 우수한 성능을 보이며, 비프라이빗 베이스라인과 대등한 정확도를 유지합니다.
• 우수한 트레이드오프: 전처리(FairBalance) 및 후처리(FairProjection) 공정성 방법과 비교했을 때, OPT는 더 유리한 정확도-공정성 트레이드오프를 달립하면서 동시에 민감한 속성의 프라이버시를 보존합니다.

결과

• 이진 속성: Adult 및 LSAC 데이터셋에서 OPT는 정확도를 RR 및 SS와 유사하게 유지하면서 통계적 패리티 및 등가 기회 격차를 크게 줄였습니다(예: LSAC에서 격차를 거의 절반으로 감소시킴).
• 비이진 속성: 다중 값 속성(예: 인종, 가족 소득)의 경우, 수치적으로 해결된 OPT 메커리즘은 특히 높은 프라이버시 예산($\epsilon$)에서 정확도 손실을 거의 없이 GRR 및 SS보다 낮은 공정성 격차를 달성했습니다.
• 공정성 방법과의 비교: 동일한 정확도 수준에서 FairProjection(후처리) 및 FairBalance(전처리)와 비교했을 때, OPT는 일반적으로 더 낮은 공정성 격차를 나타냅니다(예: COMPAS 데이터셋에서 OPT는 FairProjection 대비 $\Delta_{SP}$를 26.8%에서 24.3%로 감소시킴). Bank 데이터셋에서 OPT는 FairBalance보다 높은 정확도(90.1% vs 84.5%)와 낮은 $\Delta_{EO}$를 달성했습니다.
• 통합: OPT는 [13]의 2단계 프레임워크에서 RR을 성공적으로 대체하여, 프라이버시가 보호된 민감 속성만을 사용할 수 있는 환경에서의 적응성을 입증했습니다.

의의 및 주장
본 논문은 로컬 차분 프라이버시가 공정성을 향상시키기 위한 원칙적이고 효과적인 전처리 개입 역할을 한다고 주장합니다. 공정성과 근본적으로 양립하기 어려울 수 있는 중앙 집중형 DP와 달리, LDP는 프라이버시 보존에 내재된 무작위성이 데이터 불공정성을 능동적으로 완화할 수 있는 메커니즘을 제공합니다. 저자들은 자신의 연구를 프라이버시를 고려한 전처리와 분류 공정성 사이의 직접적인 연결 고리로 위치시키며, 민감한 속성의 최적 섭동이 모델 유용성을 희생하지 않고 편향을 완화하는 단순하면서도 강력한 도구임을 입증합니다. 결과는 LDP가 단순한 프라이버시 도구가 아니라 머신러닝 파이프라인에서 공정성 증폭을 위한 실행 가능한 전략임을 시사합니다.