Weighted Conformal Clustering

기술 요약: 가중치 컨포멀 클러스터링 (Weighted Conformal Clustering)

문제 정의
클러스터링은 라벨이 없는 데이터에서 잠재적 구조를 밝혀내는 근본적인 도구이지만, 기존의 표준 파이프라인은 일반적으로 관측치를 클러스터에 할당할 때 엄격한 불확정성 정량화 없이 "하드(hard)" 할당을 수행하는 결과만을 초래합니다. 기존 방법들은 부트스트래핑, 전역 클러스터 존재성 테스트 또는 베이지안 신용 집합(Bayesian credible sets)을 통해 불확정성을 다루지만, 개별 관측치의 할당에 내재된 구체적인 불확정성은 간과하는 경우가 많습니다.

최근 [11]의 연구는 레이블 할당을 예측 문제로 취급하여 클러스터링을 위한 컨포멀 추론 프레임워크를 도입했습니다. 그러나 한 가지 결정적인 이론적 한계가 존재합니다: [11]에서 사용된 교정(calibration) 레이블은 관찰된 실제 ground-truth 레이블이 아니라, 데이터 의존적 클러스터링 알고리즘에 의해 생성된 합성 레이블입니다. 결과적으로, 컨포멀 예측에 필요한 표준적인 교환 가능성(exchangeability) 가정이 위배되며, 이는 잠재적인 미달 커버리지(undercoverage)를 초ق합니다. 따라서, 합성 교정 레이블과 관찰되지 않은 잠재적 ground-truth 레이블 사이의 분포 불일치에도 불구하고 유한 표본 커버리지 보장을 유지하는 클러스터 레이블에 대한 신뢰 집합을 구축하는 것이 과제입니다.

방법론
저자들은 문제를 조건부 레이블 분포 변화(conditional label-distribution shift)로 공식화함으로써 이 분포 불일치 문제를 해결하는 가중치 컨포멀 클러스터링(Weighted Conformal Clustering) 프레임워크를 제안합니다. 핵심 방법론은 세 단계로 진행됩니다:

1. 오라클 가중치 분할 컨포멀 클러스터링 (Oracle-Weighted Split Conformal Clustering):
   저자들은 먼저 정확한 유한 표본 주변 커버리지(marginal coverage)를 달성하는 "오라클" 절차를 도출합니다. 이 접근 방식은 가중치 컨포멀 예측을 활용하며, 여기서 가중치는 합성 레이블 분포(클러스터링 알고리즘에 의해 유도된 것)와 실제 잠재 레이블 분포 사이의 불일치를 교정하도록 설계되었습니다. 가중치는 실제 조건부 레이블 밀도 $p^*_{Y|X}$와 클러스터링 알고리즘에 의해 생성된 합성 레이블 확률을 비교하는 우도 비(likelihood ratio)로 정의됩니다. 이론적으로는 타당하지만, 이 오라클 절차는 모든 교정 지점과 테스트 지점에 대해 leave-one-out 증강 데이터셋 상에서 클러스터링 규칙을 평가해야 하므로 계산적으로 실행 불가능합니다.

2. 증강 교정 메커니즘 (Augmented Calibration Mechanism):
   이 방법을 계산적으로 실행 가능하게 만들기 위해, 저자들은 새로운 증강 교정 메커니즘을 도입합니다. 교정 세트에서 클러스터링 알고리즘을 별도로 적합시키고 leave-one-out 세트에서 반복적으로 적합시키는 대신, 이 알고리즘은 증강된 데이터셋 $D_{aug} = D_{ca} \cup \{x\}$ (여기서 $D_{ca}$는 교정 세트, $x$는 테스트 지점)에 대해 클러스터링 모델을 단 한 번 적합시킵니다. 이 단일 적합 과정을 통해 합성 우도 항들이 인수분해되어 정규화 과정에서 상쇄될 수 있으며, 이는 가중치를 점별 우도 비(pointwise likelihood-ratio) 형태로 축소시킵니다. 이 메커니즘은 풀-컨포멀(full-conformal) 방식과 분할-컨포멀(split-conformal) 방식 사이의 가교 역할을 하며, 반복적인 재적합의 필요성을 제거합니다.

3. 추정 가중치 구축 (Estimated-Weight Construction):
   실제 조건부 밀도 $p^*_{Y|X}$는 알 수 없으므로, 이 방법은 별도의 훈련 분할에서 학습된 소프트 분류기 $\hat{\pi}$를 사용하여 오라클 가중치를 추정된 가중치로 대체합니다. 최종 알고리즘(Algorithm 1)은 다음과 같습니다:

   • 데이터를 훈련 세트와 교정 세트로 분할합니다.
   • 훈련 세트에 클러스터링 알고리즘을 적합시켜 레이블과 소프트 분류기를 생성합니다.
   • 증강된 교정 세트($D_{ca} \cup \{x\}$)에 클러스터링 알고리즘을 적합시켜 합성 레이블을 생성합니다.
   • 순열 $\hat{\sigma}$를 통해 합성 레이블을 훈련 레이블과 정렬합니다.
   • 적용된 가중치를 사용하여 적합도 점수(conformity scores)를 계산하고 신뢰 집합을 구축합니다. 이때 가중치는 추정된 조건부 밀도와 증강된 클러스터링 확률의 비율로부터 도출됩니다.

주요 기여
본 논문은 세 가지 주요 기여를 합니다:

1. 새로운 프레임워크: 합성 레이블이 비교환적 성격을 갖는다는 점을 처리하기 위해 가중치 컨포멀 예측을 활용하여, 문제를 조건부 레이블 분포 변화로 명시적으로 모델링하는 클러스터링의 불확실성 정량화 프레임워크를 도입했습니다.
2. 증강 교정: 계산 가능한 "증강 교정" 메커니즘을 제안했습니다. 이 혁신은 leave-one-out 재적합의 계산 부담을 제거하면서도 가중치 컨포멀 예측의 이론적 이점을 유지하며, 클러스터링을 넘어 비지도 학습에 적용 가능한 새로운 원리를 제공합니다.
3. 이론적 보장: 추정 가중치 절차에 대한 유한 표본 커버리지 경계를 확립했습니다. 커버리지 손실은 추정된 조건부 레이블 분포와 실제 잠재 분포 사이의 총 변동 거리(total variation distance)에 의해 명시적으로 제한됩니다. 기존 방식과 달리, 이 프레임워크는 "replace-one" 안정성 가정에 의존하지 않는데, 이는 증강 메커니즘이 프로세스를 본질적으로 안정화하기 때문입니다.

실험 결과
제안된 방법(Algorithm 1)은 여러 설정에서 split conformal clustering([11]) 및 나이브 컷오프(naive cutoff) 방법과 비교하여 평가되었습니다:

• 가우시안 혼합 모델 (GMM): 저차원($R^2$) 및 고차원($R^{50}$) 설정 모두에서, 가중치 방식은 정보가 풍부한(더 작은) 신뢰 집합 크기를 유지하면서 유효한 커버리지를 유지합니다. 스펙트럴 클러스터링을 사용한 고차원 설정에서 split conformal 방식은 지나치게 크고 정보가 없는 집합을 생성하는 반면, 가중치 방식은 정보력을 유지합니다.
• 비선형 클러스터링: "three moons" 및 "two concentric circles" 데이터셋 실험은 가중치 방식이 split conformal 방식보다 더 넓은 범위의 노이즈 수준(분산)에서도 정보가 풍부한 집합 크기를 유지함을 보여줍니다. split conformal 방식은 클러스터링이 어려워짐에 따라 정보가 없는 집합을 생성하는 경향이 있습니다.
• MNIST 적용: MNIST 데이터셋에 대한 딥 클러스터링에 적용했을 때, 이 방법은 불확정성을 성공적으로 정량화합니다. 명확한 클러스터 중심부에서는 싱글톤(singleton) 집합을 생성하고, 모호한 경계 영역에서는 더 큰 집합을 생성하여 분류하기 어려운 숫자를 정확히 식별합니다.

의의 및 주장
본 논문은 이 연구를 떠오르는 컨포멀 클러스터링 분야의 실질적인 진전으로 위치시킵니다. 합성 레이블이 분포 변화를 유도한다고 취급함으로써, 저자들은 [11]에서 고려된 매끄러운 파라메트릭 혼합 모델을 넘어 컨포멀 예측의 적용 가능성을 확장합니다. 이 방법은 특히 표준적인 컨포멀 접근 방식이 정보가 풍부한 신뢰 집합을 제공하는 데 어려움을 겪는 고차원 및 비선형 클러스터링 응용 분야에서 매우 중요합니다. 저자들은 자신들의 프레임워크가 더 엄격하고 다재다능한 불확실성 정량화 접근 방식을 제공하며, 기저의 클러스터링 알고리즘이 복잡하거나 데이터 분포가 비표준적일 때도 유효한 커버리지 보장을 제공한다고 주장합니다. 결론적으로, 저자들은 증강 교정 메커니즘이 클러스터링이라는 특정 맥락을 넘어 비지도 학습 전반에 적용 가능한 광범위한 방법론적 원리를 나타낸다고 밝힙니다.