기술적 요약: 포켓몬 정리와 기타 공정성 불가능 결과

문제 제기

본 논문은 알고리즘적 공정성의 근본적 한계를 다루며, 특히 알려진 불가능성 결과들 (예: Kleinberg–Mullainathan–Raghavan 이분법) 이 특정 스칼라 기준의 산물인지, 아니면 불평등한 기저율 (base rates) 을 가진 분포의 고유한 구조적 속성인지 조사한다. 두 가지 주요 질문이 제기된다:

1. 유한 체크리스트 한계: 유한한 선형 평균 공정성 기준 (예: 인구통계학적 평등, 균등한 오즈) 의 집합이 두 그룹 분포가 동일함을 증명할 수 있는가, 아니면 잔여 위반이 항상 남게 되는가?
2. 표현 학습 한계: 공정성 특징 학습 (그룹 정보를 제거하는 인코더 학습) 은 하류 예측기가 유용성을 희생하지 않고 공정성을 계승할 수 있는 표현을 생성함으로써 이러한 불가능성을 우회할 수 있는가?

기존 문헌은 종종 이러한 불가능성을 스칼라 통계량 간의 충돌 (예: 보정 대 오율 균형) 로 제시한다. 저자들은 이러한 스칼라적 프레임이 근본적인 기하학적 구조를 흐리게 하며, "더 많은" 기준이 그 격차를 메울 수 있는지 여부에 대한 문제를 열어두고 있다고 주장한다.

방법론

저자들은 **재현 커널 힐베르트 공간 (RKHS)**과 평균 임베딩을 사용하여 이러한 공정성 제약을 통합한다.

• RKHS 기하학: 그들은 힐베르트 공간 $\mathcal{H}$ 내에서 조건부 평균 임베딩 $\mu_{P} = \mathbb{E}[\phi(X)]$에 대한 선형 제약으로서 공정성 기준을 모델링한다.
• 특성 커널: 특성 커널을 사용하여 서로 다른 분포가 서로 다른 평균 임베딩으로 매핑되도록 보장한다 ($\mu_P \neq \mu_Q \iff P \neq Q$).
• 전체 기대 결합: 불가능성 결과를 주도하는 핵심 메커니즘은 그룹 조건부 기대값을 기저율 격차 ($\Delta p = p_a - p_b$) 와 결합시키는 전체 기대의 법칙이다.
• 스펙트럼 분석: 논문은 잔여 위반이 공정성 기준의 수가 증가함에 따라 감소하는 속도를 정량화하기 위해 스펙트럼 규칙성 가정 (풀링 공분산 연산자의 다항식 고유값 감쇠 및 소스 조건) 을 적용한다.

주요 기여

1. 강화된 KMR 정리

저자들은 고전적인 Kleinberg–Mullainathan–Raghavan (KMR) 불가능성 결과를 강화한다. 그들은 보정과 클래스 조건부 균형 사이의 모순이 완전한 그룹 내 보정을 요구하는 것이 아니라, 그룹 조건부 불편향성 ($\mathbb{E}[S|G=g] = p_g$) 이라는 더 약한 조건 하에서도 성립함을 입증한다. 이는 단순히 그룹 평균 기저율을 추적하는 보정되지 않은 점수조차도 불가능성의 영향을 받는다는 것을 보여준다.

2. 포켓몬 정리

"모두 잡아야 한다 (Gotta Catch 'Em All)"는 슬로건에서 유래한 이 정리는 유한 체크리스트 질문에 답한다.

• 정성적 결과: 서로 다른 그룹 쌍 ($P_a \neq P_b$) 과 그룹이 만족하는 임의의 유한한 선형 평균 공정성 기준 집합 $\{v_1, \dots, v_m\}$에 대해, 직교 여공간에 잔여 위반이 존재한다. 이 위반은 최대 평균 불일치 (MMD) 증인 벡터 $\delta / \|\delta\|_{\mathcal{H}}$에 의해 목격된다.
• 정량적 결과: 스펙트럼 규칙성 (다항식 고유값 감쇠) 과 소스 조건 하에서, 최소최대 잔여 위반은 콜모고로프 $m$-너비 속도 $\Theta(m^{-2\alpha r})$로 감소한다. 이는 더 많은 기준을 추가하면 최악의 경우 위반이 줄어들지만, 분포가 동일하지 않는 한 유한한 $m$에 대해서는 결코 완전히 사라지지 않음을 의미한다.

3. 공정 특징 학습의 불가능성

본 논문은 공정 표현 학습이 다음을 동시에 달성할 수 없음을 증명한다:

1. 분포 평등: $\Phi(P_a) = \Phi(P_b)$ (표현이 그룹 불변임).
2. 클래스 조건부 분리: 표현이 서로 다른 클래스 조건부 분포를 유지함 ($\Phi(X) \perp\!\!\!\perp G | Y$).
3. 비자명한 신호: 표현이 결과 $Y$에 대한 예측력을 유지함.

기저율이 다르다면 ($p_a \neq p_b$), 분포 평등과 클래스 조건부 분리를 모두 강제하면 클래스 붕괴 ($\Phi(X) \perp\!\!\!\perp Y$) 가 발생하여 표현이 예측에 무용지물이 된다.

4. 근사 공정성과 포켓몬–KMR 연결

저자들은 근사 공정성에 대한 정량적 경계를 유도한다:

• 근사 특징 학습: 그들은 사용 가능한 하류 신호 (클래스 조건부 평균 격차) 가 $(\epsilon + \rho) / |p_a - p_b|$로 제한되는 파레토 프론티어를 설정한다. 여기서 $\epsilon$은 평등 위반이고 $\rho$는 분리 위반이다.
• KMR 연결: 감사 기준의 수 $m \to \infty$로 가고 잔여 위반이 사라짐에 따라, 근사 조건이 정확한 KMR 불가능성 (완벽한 예측이 유일한 해법) 을 회복함을 보여준다.

실험 결과

본 논문은 표준 공정성 벤치마크 (Adult Income, COMPAS, ACS PUMS) 에서 이러한 이론적 경계를 검증한다:

• 스펙트럼 감쇠: 기준 수 $m$에 대한 잔여 MMD 의 실증적 플롯은 포켓몬 정리가 예측한 다항식 감쇠 속도를 확인한다. 기준을 충족하는 데 필요한 MMD "예산"은 데이터셋에 따라 다르다 (예: COMPAS 는 낮은 차원성으로 인해 더 빠르게 집중됨).
• 파레토 프론티어: 분리를 강제하는 분류기에 대한 실증적 오차 대 인구통계학적 평등 격차 플롯은 6.2 절에서 유도된 이론적 하한과 일치한다.
• 금지 구역: 공정 인코더 (LFR, Fair-VAE, Adversarial Debiasing) 를 사용한 실험은 어떤 방법도 플롯의 "금지된" 왼쪽 상단 영역 (높은 클래스 조건부 신호를 가진 낮은 평등 격차) 을 성공적으로 채우지 못함을 보여주며, 클래스 붕괴 불가능성을 확인한다.

중요성과 주장

본 논문은 공정성 불가능 결과에 대한 통합된 기하학적 프레임워크를 제공한다고 주장한다.

• 구조적 통찰: 이는 공정성 불가능성을 특정 스칼라 지표 간의 충돌이 아니라, 불평등한 기저율을 가진 분포에 작용하는 전체 기대의 법칙의 구조적 결과로 재해석한다.
• 예산 할당: 이는 공정성 감사를 예산 할당 문제로 재구성한다. 여기서 총 "예산"은 그룹 간의 MMD 이다. 정확한 공정성은 이 예산을 소진해야 하므로, 기저율이 다르다면 유용성을 희생하지 않고는 불가능하다.
• 실질적 함의: 이러한 결과는 그룹이 분포적으로 구별될 때, 알고리즘적 개입만으로는 완벽한 공정성과 유용성을 동시에 달성할 수 없음을 시사한다. 논문은 특징 정제나 제약 최적화에만 의존하기보다는 정책 개입이나 명시적 처우 격차가 이러한 regimes 에서 필요할 수 있음을 암시한다.

저자들은 겸손한 입장을 유지하며, 그들의 결과는 관찰적이며 새로운 알고리즘을 제안하지 않는다고 명시한다. 대신, 그들은 불평등한 기저율 하에서 공정 머신러닝에서 달성 가능한 것의 경계를 정의하는 이론적 "노고 (no-go)" 정리를 제공한다.