기술 요약: 강건한 공정성 감사를 위한 기하학적 이론

문제 정의

이웃 기반 공정성 감사(Neighborhood-based fairness audits)는 알고리즘 의사결정에서 개인적 공정성(individual fairness)을 평가하기 위한 표준적인 방법입니다. 이러한 감사는 유사한 개인(특징 공간 내 근접성으로 정의됨)이 유사한 예측을 받아야 한다는 전제하에 작동합니다. 일반적으로 이는 한 개인의 예측을 그와 $k$-최근접 이웃($k$-NN)들의 예측과 비교하는 방식으로 구현됩니다.

이러한 방식은 모델 불가지론적(model-agnostic) 특성과 국소적 불공정성을 탐지하는 능력 덕분에 널리 사용되지만, 감사 절차 자체의 강건성(robustness)은 그동안 크게 간과되어 왔습니다. 기존 문헌은 예측 모델을 적대적 섭동(adversarial perturbations)으로부터 강건하게 만드는 데 집중해 왔으나, 감사 메커니즘은 안정적이라고 가정합니다. 그러나 실제로는 특징 공간에서의 미세한 섭동(노이즈, 전처리, 정규화 또는 결측값으로 인한 것)이 최근접 이웃 관계를 변화시킬 수 있습니다. 이러한 "이웃 교체(neighborhood replacement)"는 동일한 모델에 대해 현저히 다른 공정성 평가를 초래할 수 있으며, 이는 진정한 불공정성과 감사 불안정성을 구별하기 어렵게 만듭니다. 현재로서는 이러한 감사가 특징 섭동 하에서 언제 안정성을 유지하는지, 혹은 기하학적 변화가 감사 결과에 어떻게 전파되는지를 설명하는 이론적 프레임워크가 존재하지 않습니다.

방법론

저자는 유계된(bounded) 특징 공간 섭동 하에서 이웃 기반 공정성 감사의 강건성을 분석하기 위한 통합된 기하학적 프레임워크를 제안합니다.

1. 감사의 정식화

본 프레임워크는 국소적 공정성 감사를 다음과 같은 2단계 과정으로 모델링합니다:

1. 쌍별 공정성 평가(Pairwise Fairness Evaluation): 함수 $g$가 개인 $x_i$와 그 이웃 $x_j \in N_k(i)$ 사이의 공정성 관계를 평가합니다.
2. 집계(Aggregation): 연산자 $\Phi$가 이러한 쌍별 점수들을 하나의 국소 감사 점수 $A_i(X)$로 집계합니다.

저자는 분석 대상을 립시츠 집계 연산자(Lipschitz aggregation operators)(정의 1)로 제한합니다. 이 클래스에는 산술 평균, 가중 평균, 절단 평균(trimmed means), 그리고 강건한 M-추정량(M-estimators)이 포함되며, 이는 본 프레임워크가 기존의 다양한 감사 방법(예: 일관성 기반 감사, FaiTH)에 적용될 수 있음을 보장합니다.

2. 기하학적 섭동 모델

분석은 고정된 예측 모델 $f$와 메트릭 공간 $(M, d)$에 임베딩된 데이터셋 $X$를 가정합니다. 섭동된 데이터셋 $X'$는 원본 점 $x_i$와 그 섭동 버전 $x'_i$ 사이의 거리가 최대 $\epsilon$인 $\epsilon$-유계 기하학적 섭동으로 정의됩니다.

도입된 핵심 기하학적 개념은 **국소 분리 마진(Local Separation Margin, $\gamma_i$)**으로, 이는 가장 먼 이웃까지의 거리와 가장 가까운 비이웃(non-neighbor)까지의 거리의 차이로 정의됩니다:
$$\gamma_i = \min_{x_j \notin N_k(i)} d(x_i, x_j) - \max_{x_j \in N_k(i)} d(x_i, x_j)$$

3. 이론적 도출

본 논문은 일련의 안정성 보증 체인을 확립합니다:

• 거리 안정성(Distance Stability): 유계된 섭동($\epsilon$)은 쌍별 거리 변화를 최대 $2\epsilon$까지 발생시킵니다 (보조정리 1).
• 마진 감소(Margin Reduction): 국소 분리 마진은 최대 $4\epsilon$만큼 감소합니다 (보조정리 2).
• 이웃 불변성(Neighborhood Invariance): 만약 원래의 분리 마진 $\gamma_i > 4\epsilon$이라면, $k$-최근접 이웃 집합은 불변합니다 (정리 3).
• 감사 안정성(Audit Stability): 이웃이 변경될 때, 감사 점수의 편차는 집계 연산자의 립시츠 상수($L_\Phi$), 최대 쌍별 점수($M$), 그리고 이웃 교체 집합의 크기($|R_i|$)에 의해 제한됩니다 (정리 6).
• 감사 변동성(Audit Volatility): 저자는 반복적인 확률적 섭동 하에서의 감사 점수의 기대 변동량인 **감사 변동성($\kappa$)**을 도입합니다. 이들은 변동성이 이웃 교체 집합의 기대 크기에 의해 제한됨을 증명합니다 (정리 8).

주요 기여

1. 문제 정식화: 본 논문은 강건한 머신러닝에 대한 초점을 예측 모델의 강건성에서 감사 절차 자체의 신뢰성으로 전환합니다.
2. 통합 프레임워크: 이웃 기반 감사를 립시츠 집계로서의 기하학적 추상화로 제공하여, 다양한 기존 방법론을 단일한 이론적 틀 아래 통합합니다.
3. 강건성 보증: 저자는 결정론적, 확률적, 그리고 기대 강건성 보증을 도출합니다. 이들은 국소 분리 마진을 이웃 보존을 위한 충분한 기하학적 인증(certificate)으로, 이웃 교체를 감사 불안정성을 유발하는 근본적인 메커니즘으로 식별합니다.
4. 정량적 측정: 감사 변동성의 도입은 반복적인 섭동 하에서 공정성 감사의 기대 민감도를 측정할 수 있는 정량적 척도를 제공합니다.

실험 결과

이론적 프레임워크는 Adult Income, Bank Marketing, COMPAS의 세 가지 벤치마크 데이터셋을 통해 검증되었습니다.

• 기하학적 안정성: 실험을 통해 관찰된 쌍별 거리 왜곡과 분리 마진의 감소가 각각 이론적 상한선인 $2\epsilon$ 및 $4\epsilon$보다 훨씬 낮음을 확인했습니다.
• 이웃 보존: 이웃 보존율(NPR)은 섭동 반경이 증가함에 따라 단조 감소했습니다. 고유한 분리 마진이 큰 데이터셋(Adult, Bank)은 COMPAS에 비해 더 높은 안정성을 유지했습니다.
• 감사 불안정성 메커니즘: 실험 결과는 이웃 교체의 양과 감사 변동성 사이에 강한 상관관계가 있음을 보여주었습니다. 다양한 섭동 모델(균등, 가우시안, 희소 섭동)에 걸쳐 감사 변동성은 주로 이웃 교체의 정도에 의해 결정되었으며, 이는 이론의 분포 독립적(distribution-independent) 특성을 뒷받침합니다.
• 집계 민감도: 서로 다른 집계 연산자(산술 평균, 절단 평균, 중앙값, 최악의 이웃)를 비교한 결과, 립시츠 상수가 낮은 연산자(예: 절단 평균, 중앙값)가 더 낮은 감사 변동성을 나타냈으며, 이는 집계 민감도가 강건성의 핵심 결정 요인임을 확인시켜 줍니다.
• 데이터셋 기하학: 데이터셋의 국소 분리 마진이 클수록 이웃 교체와 감사 변동성이 현저히 낮아지며, 잘 분리된 이웃의 경우 이 값이 0에 수렴함을 실험적으로 검증했습니다.

의의 및 주장

본 논문은 특징 공간 섭동 하에서 국소 공정성 감사의 안정성을 분석하는 최초의 이론적 프레임워크를 제공한다고 주장합니다. 주요 의의는 다음과 같습니다:

• 불안정성 진단: 감사 불안정성이 단순히 모델의 민감도 때문이 아니라, 근본적으로 국소 이웃의 기하학적 취약성(특히 이웃의 교체)에 의해 발생함을 식별합니다.
• 예측 능력: 본 프레임워크를 통해 실무자는 단순한 경험적 관찰에 의존하지 않고, 데이터셋의 기하학적 특성(분리 마진)과 집계 연산자의 선택을 바탕으로 감사 안정성을 예측할 수 있습니다.
• 측정 신뢰성: 공정성을 측정 문제로 다룸으로써, 본 연구는 데이터 전처리 및 노이즈가 공정성 평가에 도입하는 신뢰성 저하 문제를 정량화하고 완화할 수 있는 도구를 제공하여 책임 있는 AI(Responsible AI)를 위한 기존 노력들을 보완합니다.

저자는 이웃 교체가 감사 안정성을 지배하는 핵심 기하학적 메커니즘이며, 제안된 프레임워크가 더 강건한 이웃 기반 공정성 감사 방법을 설계하기 위한 원칙적인 토대를 마련한다고 결론짓습니다.