Structure Selection for Fairness-Constrained Differentially Private Data Synthesis

이 논문은 민감 속성과 결과 간의 조건부 독립성을 보장하여 편향을 제거하면서도 데이터 정확도를 향상시키기 위해, 지수 메커니즘을 활용한 조건부 독립성 인식 최소 신장 트리 알고리즘을 측정 단계에 통합한 'PrivCI'라는 새로운 차분 프라이버시 데이터 합성 프레임워크를 제안합니다.

핵심

🏛️ 비유: "공정한 도시 설계사"의 이야기

상상해 보세요. 여러분이 거대한 도시의 인구 데이터를 가지고 있다고 칩시다. 이 데이터에는 성별, 인종, 소득, 직업 등 다양한 정보가 들어있죠.

하지만 이 데이터에는 숨겨진 편견이 있을 수 있습니다. 예를 들어, "어떤 지역 (인구) 에 사는 사람들은 실제로 능력과 상관없이 대출을 거절당했다"는 역사적인 불공정이 데이터에 그대로 남아있을 수 있어요.

이제 우리는 이 데이터를 비밀스럽게 (개인정보 보호) 처리해서, 실제 사람 대신 **가상의 사람 (Synthetic Data)**으로 만든 후, 은행이나 회사에 공개하려고 합니다.

1. 문제: "편견까지 복사해 버리는 위험"

기존의 기술 (기존의 도시 설계사들) 은 "데이터를 최대한 똑같이 복제해라"라고 생각했습니다. 그래서 개인정보는 안전하게 가렸지만, 원래 데이터에 있던 부당한 편견 (예: 특정 인종은 대출을 못 받는다) 까지 그대로 복사해 버리는 문제가 생겼습니다.

2. 해결책: "PrivCI (프라이시)"라는 새로운 설계사

이 논문에서 제안하는 PrivCI는 다음과 같은 원칙을 세웠습니다.

"우리는 성별이나 인종 (보호 속성) 이 대출 승인 (결과) 에 직접 영향을 미치지 않도록 해야 해. 오직 '신용 점수'나 '소득' (허용된 요인) 만이 영향을 미쳐야 해."

이를 위해 PrivCI 는 데이터를 만들 때 두 단계를 거칩니다.

• 1 단계: 측정 (데이터 수집) - 실제 데이터의 특징을 파악합니다.
• 2 단계: 재구성 (가짜 데이터 만들기) - 그 특징을 바탕으로 가짜 데이터를 만듭니다.

기존 방식의 실수:
기존 방식은 1 단계에서 "편견이 있는 연결고리"까지 모두 파악해 버렸고, 2 단계에서 그걸 고치려고 하다가 개인정보 보호 예산 (비밀 유지 비용) 을 낭비하거나, 고친다고 해도 이미 왜곡된 데이터를 만들게 됩니다.

PrivCI 의 혁신 (이 논문의 핵심):
PrivCI 는 1 단계 (측정) 에서부터 편견을 차단합니다.
마치 다리 건설 공사를 할 때, "성별과 대출 승인 사이에 다리를 놓으면 안 된다"는 규칙을 설계 도면을 그리는 순간부터 적용하는 것과 같습니다.

• 크루스칼 알고리즘 (Kruskal's algorithm): 이 기술은 데이터 속의 '연결고리'들을 찾아 가장 중요한 것들만 골라 나무처럼 연결하는 방법입니다.
• PrivCI 의 방식: 이 나무를 만들 때, "성별 (S) 과 대출 (O) 을 직접 연결하는 가지"는 절대 허용하지 않습니다. 대신, "성별 → 학력/경력 (A) → 대출"처럼 허용된 경로를 통해서만 연결되도록 설계합니다.

3. 왜 이것이 중요한가요? (결과)

이 방법은 마치 공정한 도시를 처음부터 올바르게 설계하는 것과 같습니다.

• 더 정확한 데이터: 편견을 나중에 고치는 대신, 처음부터 잘못된 연결을 안 만들었기 때문에, 데이터의 전체적인 모양 (통계적 특징) 을 더 잘 보존할 수 있습니다.
• 더 나은 예측: 나중에 이 가짜 데이터로 AI 를 훈련시켜도, 편견 없이 더 정확한 결과를 냅니다.
• 개인정보 보호: 편견을 제거하는 과정에서 추가적인 비용을 들이지 않아도 되어, 개인정보 보호 수준은 그대로 유지됩니다.

📝 한 줄 요약

"PrivCI 는 가짜 데이터를 만들 때, '편견'이라는 독을 처음부터 제거하는 설계도를 그려, 개인정보는 지키면서도 더 공정하고 정확한 데이터를 만들어냅니다."

이 기술은 채용, 대출, 범죄 예측 등 공정성이 중요한 모든 분야에서 AI 가 편향되지 않도록 도와줄 수 있는 중요한 도구입니다.

기술 요약

1. 문제 정의 (Problem Definition)

• 배경: 차분 프라이버시 (Differential Privacy, DP) 는 데이터 분석 및 머신러닝에서 개인 정보 보호를 보장하는 표준으로 자리 잡았습니다. 특히, DP 를 적용하여 합성 데이터 (Synthetic Data) 를 생성하는 방식이 널리 사용되고 있습니다.
• 핵심 문제: 기존 DP 합성 데이터 생성 기법들은 원본 데이터의 통계적 구조를 가능한 한 보존하는 데 중점을 둡니다. 이로 인해 원본 데이터에 존재하는 **부정적인 편향 (Bias)**이나 **허위 상관관계 (Spurious Correlations)**가 합성 데이터에도 그대로 전이됩니다.
  • 예시: 채용 데이터에서 특정 성별 (보호 속성) 이 합격 여부 (결과) 와 불합리하게 연관되어 있는 경우, DP 합성 데이터도 이 불공정한 패턴을 재생성하여 하류 분석의 공정성을 해칩니다.
• 한계: DP 는 개인의 프라이버시만 보장할 뿐, 어떤 의존성 (Dependency) 을 보존하거나 제거해야 하는지에 대한 정책적/윤리적 제약을 자동으로 처리하지는 않습니다.
• 목표: 합성 데이터 생성 과정에서 조건부 독립 (Conditional Independence, CI) 제약을 구조적으로 강제하여, 보호 속성 (Sensitive Attributes) 과 결과 (Outcomes) 간의 불필요한 의존성을 제거하면서도 데이터의 유용성 (Utility) 을 최대한 유지하는 것입니다.

2. 제안 방법론: PrivCI (Methodology)

저자들은 PrivCI라는 새로운 DP 합성 데이터 생성 프레임워크를 제안합니다. 이는 기존의 MST(Minimum Spanning Tree) 기반 DP 합성 파이프라인을 확장한 것으로, 측정 단계 (Measurement Step) 에서 CI 제약을 구조적으로 반영합니다.

가. 기본 프레임워크 (MST + PrivatePGM)

기존의 구조화된 표 형식 데이터 (Tabular Data) 에 대한 DP 합성은 일반적으로 두 단계로 이루어집니다:

1. 측정 (Measurement): 프라이버시 예산을 사용하여 저차원 통계량 (주로 1 차 및 2 차 한계분포, Marginals) 을 추정합니다.
2. 재구성 (Reconstruction): 추정된 노이즈가 포함된 통계량을 기반으로 확률 모델을 적합시키고 합성 데이터를 샘플링합니다.
   • 기존 접근법 (MST): 의존성 점수 (Dependency Score) 를 기반으로 최대 신장 트리 (Maximum Spanning Tree) 를 선택하여 2 차 한계분포를 측정합니다.

나. PrivCI 의 핵심 혁신: CI 인지형 탐욕적 트리 선택

PrivCI 는 트리 구조 선택 과정에서 CI 제약을 구현 가능성 (Feasibility) 조건으로 통합합니다.

• 속성 분류: 데이터 속성을 네 가지 역할로 나눕니다.
  • $S$: 보호 속성 (Protected, 예: 성별, 인종)
  • $O$: 결과 속성 (Outcome, 예: 채용 여부, 신용 위험)
  • $A$: 허용 가능한 속성 (Admissible, 예: 학력, 경력 - $S$와 $O$ 간의 합법적 연결 고리)
  • $I$: 허용 불가능한 속성 (Inadmissible, 예: 우편번호 - $S$의 대리 변수)
• CI 제약 조건: $O \perp S | A$ (허용 가능한 속성 $A$가 주어졌을 때, 결과 $O$는 보호 속성 $S$와 조건부 독립이어야 함).
• 알고리즘 수정 (Kruskal 알고리즘 기반):
  1. 탐욕적 선택 (Greedy Selection): Kruskal 알고리즘을 사용하여 트리를 구성하되, 각 간선 (Edge) 추가 시 다음 두 가지 조건을 만족하는지 확인합니다.
     • acyclicity: 순환 (Cycle) 을 생성하지 않아야 함.
     • CI Consistency: 간선을 추가했을 때, $V \setminus A$ (허용 불가능한 속성만 포함된 그래프) 에서 $S$와 $O$ 사이에 경로가 생성되지 않아야 함. 즉, $A$가 $S$와 $O$를 분리 (Separation) 해야 합니다.
  2. 프라이버시 보호: 조건을 만족하는 유효한 간선 후보 집합 내에서, 지수 메커니즘 (Exponential Mechanism) 을 사용하여 의존성 점수가 높은 간선을 프라이버시를 유지하며 선택합니다.
  3. 재구성: 선택된 트리 구조에 따라 노이즈가 포함된 2 차 한계분포를 측정하고, PrivatePGM 을 통해 확률 모델을 재구성하여 합성 데이터를 생성합니다.

3. 주요 기여 (Key Contributions)

1. 구조적 CI 강제: 사후 수정 (Post-hoc repair) 이 아닌, **측정 단계 (Measurement Stage)**에서 CI 제약을 구조적으로 강제하여 프라이버시 예산을 낭비하지 않고 편향을 근본적으로 차단합니다.
2. 효율적인 알고리즘 설계: MST 기반의 프라이버시 예산 관리 (Privacy Accounting) 와 확장성을 유지하면서, CI 제약을 만족하는 트리 선택을 위한 탐욕적 알고리즘을 설계했습니다.
3. 실용적 유틸리티 향상: 기존 방법론 (PreFair 등) 대비 더 높은 데이터 정확도 (Fidelity) 와 하류 예측 성능을 달성하면서도 동일한 수준의 공정성을 보장합니다.

4. 실험 결과 (Experimental Results)

저자들은 Adult, COMPAS, Dutch Census, German Credit, Law School 등 5 가지 공정한 알고리즘 벤치마크 데이터셋을 사용하여 PrivCI 를 평가했습니다.

• 비교 대상: 기존 CI 제약 DP 합성 방법인 PreFair 및 제약이 없는 MST (Baseline).
• 주요 성과:
  • 유용성 (Utility): PrivCI 는 PreFair 보다 **더 높은 의존성 점수 (Proxy MI)**를 달성했습니다. 이는 CI 제약 하에서도 더 많은 유용한 의존성을 보존할 수 있음을 의미합니다.
  • 분포 충실도 (Distributional Fidelity): KL 발산 (KL Divergence) 및 총변동 거리 (TV Distance) 기준에서 원본 데이터와의 거리가 PreFair 보다 더 가깝게 유지되었습니다.
  • 하류 예측 성능 (Predictive Performance): 합성 데이터로 학습된 로지스틱 회귀 모델의 AUC 점수가 대부분의 데이터셋에서 PreFair 보다 높았습니다.
  • 공정성 (Fairness):
    • CMI (조건부 상호 정보): 보호 속성과 결과 간의 조건부 의존성을 효과적으로 제거하여 (CMI 감소), MST 대비 공정성이 크게 향상되었습니다.
    • Equalized Odds (EO): 하류 모델의 공정성 지표인 EO 또한 개선되었으나, 데이터셋에 따라 그 정도는 상이했습니다.
  • 통계적 유의성: Wilcoxon 부호 순위 검정 결과, PrivCI 는 PreFair 대비 유틸리티 (AUC, MI 점수) 와 충실도 (KL, TV) 측면에서 통계적으로 유의미한 개선을 보였습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 프라이버시 - 유틸리티 - 공정성의 균형: PrivCI 는 DP 합성 데이터 생성에서 "프라이버시 vs 유틸리티"의 트레이드오프를 "공정성"까지 고려한 3 축 균형으로 확장했습니다.
• 구조적 접근의 우월성: 사후에 데이터를 수정하거나 특정 간선을 무작위로 제거하는 방식 (PreFair 의 휴리스틱) 보다, **측정 단계에서 구조적 제약 (Structural Constraint)**을 적용하는 것이 더 높은 데이터 품질과 예측 성능을 보장함을 입증했습니다.
• 미래 방향: 단일 CI 제약에서 다중/중첩 CI 제약으로 확장하거나, 트리 구조를 넘어선 더 복잡한 그래프 모델 및 딥러닝 기반 생성 모델 (DP-Deep Generative Models) 로의 적용 가능성을 제시합니다.

요약하자면, PrivCI 는 차분 프라이버시 하에서 합성 데이터를 생성할 때, 법적/윤리적 요구사항인 조건부 독립을 구조적으로 강제함으로써 편향을 제거하면서도 데이터의 실용성을 극대화하는 새로운 표준을 제시한 연구입니다.