Fairness of Classifiers in the Presence of Constraints between Features

마틴 C. 쿠퍼 (Martin C. Cooper) 와 이만 부스디라 (Imane Bousdira) 의 논문 "특성 간 제약이 존재할 때 분류기의 공정성 (Fairness of Classifiers in the Presence of Constraints between Features)"에 대한 상세한 기술적 요약입니다.

1. 문제 제기

이 논문은 기계 학습 분류기의 공정성 정의 및 평가에서 중요한 간극을 다루고 있습니다: 특성 간의 논리적 제약의 존재입니다.

• 배경: 공정성의 표준 정의 (예: 무지각을 통한 공정성, Fairness Through Unawareness) 는 종종 결정이 보호 특성 (예: 성별, 인종) 에 의존하지 않으면 공정하다고 가정합니다.
• 문제점: 실제 시나리오에서는 특성이 거의 독립적이지 않습니다. 제약은 다음과 같은 이유로 존재합니다:
  • 인코딩: 예: 정확히 하나의 불리언 특성이 참이어야 하는 원-핫 (one-hot) 인코딩.
  • 실제 세계 논리: 예: "산휴가에 있는 사람은 여성이고 취업 상태여야 한다."
• 결과: 이러한 제약을 무시하면 잘못된 양성 (공정 분류기를 불공정하다고 판단) 이나 잘못된 음성 (불공정 분류기를 공정하다고 판단) 으로 이어질 수 있습니다.
  • 예시: 성별이 바뀔 때 모델 출력이 변하므로 모델이 성별에 의존하는 것처럼 보일 수 있습니다. 하지만 제약이 성별 변경이 다른 특성 (예: 고용 상태) 의 변경을 강제함을 의미한다면, 유효한 특성 공간에서 결정은 실제로 성별과 무관할 수 있습니다.
• 목표: 제약 ($C$) 이 존재하는 상황에서 공정성을 공식적으로 정의하고, 이러한 정의를 검증하는 계산 복잡성을 분석하는 것입니다.

2. 방법론 및 핵심 개념

저자들은 제약이 있는 특성 공간 내에서 **귀납적 설명 (Abductive Explanations, AXp)**과 **주요 함의 (Prime Implicants, PI)**를 활용합니다.

주요 정의

• 특성 공간 ($F$): 특성 도메인의 카테시안 곱 (Cartesian product).
• 제약 ($C$): 유효한 인스턴스를 제한하는 논리 규칙의 집합. 유효한 공간은 $F[C]$입니다.
• 보호 특성 ($P$) 대 비보호 특성 ($N$): $P$는 민감한 속성 (예: 성별) 을 포함하고, $N$은 기타 속성을 포함합니다.
• 귀납적 설명 (AXp): 인스턴스 $x$에서 $S$의 값을 고정하면 분류기 출력 $\kappa(x)$가 보장되는 특성 부분집합 $S$. 이때 $F[C]$ 내의 인스턴스만 고려합니다.
• 주요 함의 설명 (PI-explanation): 다른 AXp 에 의해 엄격하게 포괄되지 않는 AXp. 제약이 있는 공간에서 포괄성은 단순한 집합 포함이 아닌 $F[C]$ 내의 논리적 함의로 정의됩니다.
• 공정 PI-설명: 어떠한 보호 특성도 포함하지 않는 PI-설명 ($S \cap P = \emptyset$).

제안된 공정성 정의

논문은 분류기 $\kappa$의 공정성에 대한 세 가지 구별된 정의를 제안합니다:

1. 제약된 무지각을 통한 공정성 (Constrained FTU):

   • 모든 $x, y \in F[C]$에 대해, $x_N = y_N$ (비보호 특성이 동일) 이면 $\kappa(x) = \kappa(y)$입니다.
   • 이는 유효한 공간 내에서 결정이 오직 비보호 특성에만 의존함을 보장합니다.

2. 존재적 공정성 (Existential Fairness):

   • 모든 결정 $\kappa(x) = c$에 대해, 적어도 하나의 공정 PI-설명이 존재합니다.
   • 의미: 보호 특성에 의존하지 않는 결정에 대한 어떤 유효한 이유가 존재합니다.

3. 보편적 공정성 (Universal Fairness):

   • 모든 결정 $\kappa(x) = c$에 대해, 모든 PI-설명이 공정합니다.
   • 의미: 결정에 대한 모든 최소한의 이유가 보호 특성을 피합니다.

이론적 분석

저자들은 다양한 제약 시나리오 하에서 이러한 정의들 간의 관계를 분석합니다:

• $P$와 $N$ 간의 제약: 이를 무시하면 공정성 평가가 극적으로 바뀔 수 있습니다. 결정이 $F[C]$에서는 보편적으로 공정할 수 있지만, 제약이 없는 $F$에서는 불공정해 보이거나 그 반대가 될 수 있습니다.
• $P$ 내부만의 제약: 보호 특성 간에만 제약이 존재한다면, 비제약 공간에서 제약 공간으로 공정 PI-설명 존재가 유지됩니다 (명제 1).
• $N$ 내부만의 제약: 공정 PI-설명 존재는 이러한 제약과 무관합니다 (명제 2). 그러나 $N$ 내부의 제약은 비제약 공간에는 존재하지 않았던 불공정 PI-설명을 생성할 수 있습니다 (예시 7).

동등성을 위한 특수 조건

논문은 복잡한 정의 (존재적/보편적) 가 검증이 쉬운 제약된 FTU 로 단순화되는 조건을 식별합니다:

• 느슨한 제약 (Loose Constraints): 보호 특성의 부분 할당이 모든 비보호 특성의 할당을 엄격하게 포괄하지 않는다면, 제약된 FTU 는 존재적 공정성을 함의합니다.
• 분리된 분류기 (Disentangled Classifiers): 분류기가 "분리된" 것이란 것은 비보호 특성 집합 $N$이 어떤 불공정 AXp 에 의해 엄격하게 포괄되지 않는 약한 AXp 일 때를 말합니다. 이는 존재적 공정성을 보장합니다.

3. 주요 기여

1. 제약이 포함된 공정성 형식화: 논문은 논리적 제약을 설명 (PI-설명) 의 정의에 직접 통합함으로써 표준 "무지각" 정의를 넘어섰습니다.
2. 제약 영향의 입증: 출산 휴가, 입양 기관 등 여러 예시를 통해 제약을 무시하면 잘못된 공정성 평가로 이어짐을 증명했습니다.
3. 공정성 정의의 위계: 논문은 제약된 FTU, 존재적 공정성, 보편적 공정성 간의 논리적 관계를 확립했습니다.
   • 보편적 $\implies$ 존재적 $\implies$ 제약된 FTU.
   • 역함의는 일반적으로 "느슨한 제약"이나 "$P$와 $N$ 간 제약 없음"과 같은 특정 조건이 충족되지 않는 한 성립하지 않습니다.
4. 복잡성 분석: 저자들은 다항식 계층 (Polynomial Hierarchy) 내에서 이러한 공정성 개념을 검증하는 계산 복잡성을 매핑했습니다.

4. 결과 및 복잡성 분석

논문은 이러한 공정성 정의를 테스트하기 위한 엄격한 복잡성 분석을 제공합니다:

공정성 개념	복잡성 클래스	비고
공정 PI-설명 존재 (단일 결정에 대해)	$\Sigma^P_3$	$\exists \forall \exists$ 양자 교대가 포함됨.
불공정 PI-설명 존재	$\Sigma^P_3$	위의 여집합.
존재적 공정성 테스트 (분류기)	$\Pi^P_4$	모든 인스턴스 ($\forall x$) 에 대해 $\Sigma^P_3$ 속성을 확인해야 함.
보편적 공정성 테스트 (분류기)	$\Pi^P_3$	어떤 인스턴스에도 불공정 설명이 존재하지 않는지 확인하는 것과 동일.
제약된 FTU 테스트	coNP-완전	단일 SAT 솔버 호출로 해결 가능 (동일한 $N$을 가지지만 다른 출력을 가진 $\exists x, y$ 존재 여부 확인).

주요 복잡성 통찰:

• 제약된 FTU 테스트는 계산적으로 실행 가능 (coNP-완전) 하며 표준 SAT 솔버로 처리할 수 있습니다.
• 존재적/보편적 공정성 테스트는 훨씬 더 어렵습니다 ($\Pi^P_3$ 또는 $\Pi^P_4$). 양화 부울 식 (QBF) 솔버가 필요합니다.
• 실용적 함의: 저자들은 존재적 공정성을 보장하는 충분 조건으로 "느슨한 제약" 또는 "분리된" 확인 (이는 $\Pi^P_2$임) 을 제안하며, 이를 통해 QBF 솔버 대신 더 간단한 SAT 솔버를 사용할 수 있게 합니다.

5. 의의 및 결론

• 이론적 기반: 논문은 공정성이 공허한 상태에서 평가될 수 없으며, 특성 공간의 논리적 구조 (제약) 가 결정에 대한 "이유"의 정의를 근본적으로 바꾼다는 것을 확립합니다.
• 실무 지침: 제약을 무시하는 표준 공정성 도구는 오해의 소지가 있는 결과를 낳을 수 있음을 실무자에게 경고합니다.
• 절충: 공정성 정의의 엄격성과 계산적 실행 가능성 사이에는 절충이 존재합니다.
  • 보편적 공정성은 가장 엄격하지만 검증이 가장 어렵습니다.
  • 제약된 FTU는 검증이 가장 쉽지만, 제약을 통해 보호 특성에 기술적으로 의존하는 결정을 놓칠 수 있습니다.
• 향후 방향: 저자들은 이 논리적 프레임워크를 통계적 상관관계 처리로 확장하고, 인과 그래프를 사용하여 "보호 특성 선택"을 탐구하는 것 (인과적 독립을 통한 공정성 - FTCI) 을 제안합니다.

요약하자면, 이 논문은 공정성이 특성 제약에 따라 맥락 의존적임을 주장합니다. 논문은 주된 함의 설명을 통해 공정성을 정의하는 공식적 프레임워크를 제공하며, 이론적 엄밀성과 계산적 실행 가능성 사이의 균형을 맞추는 이러한 정의를 검증하기 위한 로드맵을 제시합니다.