Proportionally Representative Clustering

기술 요약: 비례적 대표성 클러스터링 (Proportionally Representative Clustering)

문제 정의
본 논문은 중심점 클러스터링(centroid clustering)에서의 공정성 문제를 다룹니다. 이는 메트릭 공간에서 $n$개의 데이터 포인트(에이전트)를 위해 $k$개의 중심점(센트로이드) 부분집합을 선택하는 것을 목표로 하는 비지도 학습의 근본적인 과제입니다. $k$-means, $k$-medians, $k$-center와 같은 표준 목적 함수들은 글로벌 복지(global welfare)를 최적화하지만, 비례적 대표 공정성(proportional representational fairness)을 포착하는 데는 종종 실패합니다. 클러스터링의 기존 공정성 개념인 비례적 공정성(Proportional Fairness, PF) 및 코어 공정성(Core Fairness)은 한계가 있습니다. 즉, 모든 인스턴스에서 달성 가능하지 않을 수 있으며, "만장일치 비례성(unanimous proportionality)"이라 불리는 최소한의 직관적 요구사항(동일한 위치에 있는 에이전트 집단은 그 크기에 비례하는 수의 중심점을 가질 권리가 있다는 원칙)을 충족하지 못합니다. 또한, 기존의 공정 클러스터링 알고리즘은 사전에 지정된 보호 속성(protected attributes)에 의존하는 반면, 본 연구는 데이터 분포에 의해 내생적으로 결정되는 임의의 그룹에 적용 가능한 공정성 속성을 추구합니다.

방법론
저자들은 공리적 접근 방식을 채택하여, **비례적 대표 공정성(Proportionally Representative Fairness, PRF)**이라는 새로운 공정성 개념을 제안합니다. 이 개념은 제약이 없는(연속적인) 설정과 이산적인 클러스터링 설정 모두를 위해 설계되었습니다.

1. 공리적 정의 (PRF):

   • 제약 없는 설정 (Unconstrained Setting): 결과 $X$가 다음을 만족하면 PRF를 충족한다: 임의의 에이전트 집합 $S$가 크기 $\ell n/k$ 이상이고 최대 쌍별 거리(maximum pairwise distance)가 $y$일 때, $X$에는 $S$ 내의 적어도 하나의 에이전트로부터 거리 $y$ 이내에 있는 $\ell$개의 중심점이 존재해야 한다.
   • 이산적 설정 (Discrete Setting): 후보 집합 $M$의 거칠기(coarseness)를 고려하여 정의를 조정한다. 만약 집합 $S$($|S| \ge \ell n/k$)의 모든 에이전트로부터 거리 $y$ 이내에 있는 후보가 $M$에 $\ell'$개 있다면, 결과물에는 $S$ 내의 어떤 에이전트로부터도 거리 $y$ 이내에 있는 $\ell'$개의 중심점이 포함되어야 한다.

2. 알고리즘 설계 (SEAR):
   저자들은 다수결 투표의 확장 승인 규칙(Expanding Approvals Rule, EAR)에서 영감을 얻어 공간 데이터에 맞게 변형한 다항 시간 알고리즘인 SEAR(Spatial Expanding Approval Rule)를 도입합니다.

   • 메커니즘: 알고리즘은 에이전트와 후보 사이의 정렬된 거리에 기반하여 이웃 반경을 반복적으로 확장합니다. 에이전트들에게 초기 가중치가 할당됩니다. 선택된 중심점이 전체 가중치의 $n/k$ 이상을 가진 에이전트 그룹을 커버할 때, 해당 중심점이 솔루션에 추가되고 커버된 에이전트들의 가중치는 $n/k$만큼 감소합니다.
   • 구현:
     • 알고리즘 1 (Unconstrained): 후보는 에이전트의 위치로 제한됩니다. 실행 시간은 $O(n^2 \log n + kn^2)$입니다.
     • 알고리즘 2 (Discrete): 후보는 유한한 집합 $M$에서 추출됩니다. 실행 시간은 $O(|M|n \log n + k|M|n)$입니다.

주요 기여 및 결과

• PRF의 존재성 및 속성: 본 논문은 제약 없는 설정과 이산적 설정 모두에서 PRF 결과가 존재함이 보장됨을 증명합니다. PRF는 다음과 같은 바람직한 속성을 만족합니다: 만장일치 비례성을 함의하며, 이상치(outlier)에 강건하고, 척도 불변성(scale-invariance)을 가지며, 사전에 지정된 보호 그룹을 필요로 하지 않습니다.
• 비례적 공정성(PF)의 근사:
  • Unconstrained: unconstrained 설정을 위한 SEAR 알고리즘은 PF에 대한 **3-근사(3-approximation)**를 제공합니다. 이는 일반 메트릭 공간에서 PF를 위한 최초의 알려진 다항 시간 근사 알고리즘입니다. 또한, 일반적인 PRF 결과의 존재성에 대해 \frac{3+\sqrt{17}}{2} \approx 3.56}의 타이트한 상한을 확립합니다.
  • Discrete: discrete 설정을 위한 SEAR 알고리즘은 PF에 대한 $(1+\sqrt{2})$-근사를 제공하며, 이는 더 강력한 PRF 공리를 만족하면서도 PF에 대한 기존의 최선 근사 계수와 일치합니다.
• 불가능성 결과 (Impossibility Results):
  • 본 논문은 표준 클러스터링 알고리즘($k$-means, $k$-median, $k$-center) 및 이전의 공정 클러스터링 알고리즘(예: Greedy Capture)이 PRF를 만족하지 못함을 보여줍니다.
  • 전략적 진실성 (Strategyproofness): 저자들은 PRF와 전략적 진실성 사이의 상충 관계를 증명합니다. 구체적으로, 이산적 설정에서 $k=2$인 경우에도 순서 통계량 전략적 진실성(order-statistic strategyproof)을 만족하면서 PRF를 만족하는 알고리즘은 존재하지 않습니다. 이는 승인 기반 위원회 투표(approval-based committee voting)로부터의 환원을 통해 입증되며, PRF를 전략적 진실성과 양립할 수 없는 것으로 알려진 비례적 정당 대표성(Proportional Justified Representation, PJR) 공리와 연결합니다.

의의
본 논문은 세 가지 주요 분야에서 의의를 가집니다:

1. 개념적 발전: 기존의 비례적 공정성 정의가 가진 한계, 특히 만장일치 비례성 보장의 실패를 극복하는 강력한 공리적 공정성 개념으로서 PRF를 도입했습니다.
2. 알고리즘적 돌파구: 일반 메트릭 공간(unconstrained 설정)에서 PF에 대한 최초의 다항 시간 근사 알고리즘을 제공하고, 더 강력한 PRF 공리를 만족하면서 discrete 설정에서의 최선 경계치에 도달했습니다.
3. 이론적 한계: 공정성(특히 PRF)과 인센티브 호환성(전략적 진실성) 사이의 트레이드오프를 엄밀하게 규명하여, 비례적 대표성 공리를 만족시키는 것이 중심점 선택에서의 조작 방지와 본질적으로 충돌함을 보여주었습니다.

이 연구는 사회 선택 이론(특히 다수결 투표)과 비지도 학습 사이의 가교 역할을 하며, 전통적인 투표 규칙이나 표준 클러스터링 목적 함수가 달성할 수 없는 동기화된 결정을 공간 정보를 활용하여 수행합니다.