Adaptive Conformal Inference through the Lens of Blackwell Approachability

기술 요약: 블랙웰 접근성(Blackwell Approachability)의 관점에서 본 적응형 컨포멀 추론(Adaptive Conformal Inference)

문제 정의
Gibbs와 Candès(2021)가 도입한 적응형 컨포멀 추론(Adaptive Conformal Inference, ACI)은 순차적 또는 시계열적 설정(예: 시계열 예측)에서 흔히 발생하는 교환 가능성(exchangeability) 가정의 한계를 해결한다. ACI는 임의의 데이터 시퀀스에 대해 경험적 커버리지(empirical coverage)가 원하는 수준인 $1-\alpha$로 수렴하도록 예측 집합을 순차적으로 구성하는 것을 목표로 한다. 기존의 ACI 전략들은 유효성(empirical coverage $\geq 1-\alpha$)은 보장하지만, 일반적으로 효율성(평균 예측 구간 길이)에 대한 동시적인 이론적 보장은 결여되어 있다. 적대적 설정(adversarial settings)에서는 추가적인 가정이 없는 한 비자명한 효율성 보장이 불가능하며, 교환 가능한 설정(exchangeable settings)에서도 기존 방법론들은 차선의 구간 길이를 산출하는 경우가 많다. 핵심 과제는 임의의 시퀀스에 대해 유효성을 보장하는 동시에, 데이터의 확률적 성격(stochasticity)에 따라 효율성을 적응시키는 통합된 전략을 설계하는 것이다.

방법론
저자들은 ACI를 벡터 값 보상(vector-valued payoffs)을 갖는 **반복되는 2인 유한 게임(repeated two-player finite game)**으로 재정의한다.

1. 학습자의 행동(Learner's Action): 미스커버리지(miscoverage) 수준 $a_t \in A$를 선택한다. 여기서 $A$는 캘리브레이션 세트의 순서 통계량으로부터 유도된 유한 그리드이며, 이는 예측 집합 $C_{1-a_t}(x_t)$를 결정한다.
   • 상대방의 행동(Opponent's Action): 결과 $y_t$를 선택하며, 이는 $y_t$를 포함하는 가장 타이트한 컨포멀 집합을 나타내는 이산적 행동 $b_t \in B$로 매핑된다.
   • 보상 벡터(Payoff Vector): 학습자는 미스커버지 지표(유효성)와 구간 길이(효율성)를 인코딩하는 벡터 $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$를 받는다.
2. 접근성 프레임워크(Approachability Framework):
   • 목표는 평균 보상 벡터 $m_T$를 타겟 집합 $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$로 유도하는 것이다.
   • 타겟 집합은 상대방의 플레이를 제한하는 제약 조건 $Q \subseteq \Delta(B)$에 의존한다. $Q$는 상대방의 행동이 점근적으로 따르는 분포들의 집합을 나타낸다.
   • 기회적 접근성(Opportunistic Approachability): 저자들은 **블랙웰 접근성(Blackwell approachability)**과 그 확장인 Bernstein 등(2014)의 기회적 접근성 이론을 활용한다. 이 프레임워크를 통해 학습자는 상대방의 플레이가 특정 집합 $Q$에 제한되어 있다면, $Q$를 사전에 알지 못하더라도 더 효율적인 작은 타겟 집합으로 접근할 수 있다.
3. 알고리즘 (BO-ACI):
   • 제안된 전략인 **Blackwell Opportunistic Adaptive Conformal Inference (BO-ACI)**는 보조 캘리브레이션 예측 모델(calibrated forecaster) $F$를 활용한다.
   • 각 라운드에서 $F$는 상대방의 다음 행동 $b_t$의 분포를 예측한다.
   • 학습자는 예측된 분포에 대해 유효성 제약 조건을 만족하면서(응답 함수 $p^*$를 통해) 기대 길이를 최소화하는 행동 $a_t$를 결정론적으로 선택한다.

주요 기여

1. 게임 이론적 재구성: 본 논문은 ACI를 벡터 값 보상을 갖는 반복 유한 게임으로 새롭게 정식화하여, 유효성과 효율성을 다목적 접근성 문제(multi-objective approachability problem)와 명시적으로 연결하였다.
2. 통합 전략 (BO-ACI): 기회적 접근성에 기반한 전략인 BO-ACI를 도입하여, 임의의 데이터 시퀀스(확률적 또는 적대적)에 대해 유효성을 보장하는 동시에, 데이터의 알려지지 않은 확률적 성격에 적응하여 효율성을 제공하는 보장을 달una한다.
3. "Best of Many Worlds" 보장: 이 전략은 다음과 같은 통합된 보장 세트를 달성한다:
   • 교환 가능한 설정: 최적의 효율성 보장인 $L(C_{1-\alpha})$를 회복하여, 이상적인 조건에서의 표준 컨포멀 예측 성능과 일치한다.
   • 적대적 설정: 유효성을 보장하지만, 효율성은 자명한 경계(구간 길이 $2L$)를 수용한다. 이는 완전 적대적 설정에서의 불가능성 결과와 일치한다.
   • 중간 단계 설정: 단일 분포 변화(single distributional shifts) 또는 "거의 교환 가능한" 데이터(예: 약한 의존성을 가진 시계열)와 같은 시나리오에서 의미 있는 효율성 보장을 제공하며, 여기서 구간 길이는 비교환성의 정도에 따라 적응한다.

결과

• 이론적 수렴: 정리 19는 BO-ACI 전략 하에서 평균 보상 벡터 $m_T$가 상대방의 플레이를 제한하는 임의의 볼록 집합 $Q$에 대해 거의 확실하게(almost surely) 타겟 집합 $C_{\alpha, Q}$로 수렴함을 증명한다.
• 특정 시나리오:
  • 교환 가능한 데이터: 상대방이 균등 분포 $q_{unif}$로 제한되는 경우, 평균 구간 길이는 $L(C_{1-\alpha})$로 수렴한다.
  • 단일 분포 변화: 테스트 점수가 캘리브레이션 분포 $S$와 다른 분포 $V$를 따르는 경우, 전략은 최적의 미스커버리지 수준 $a_{S,V}$에 대한 길이 $L(C_{1-a_{S,V}})$로 수렴한다.
  • $\epsilon$-교환 가능/시계열: 총 변동 거리(Total Variation) 또는 콜모고로프 거리(Kolmogorov distance)로 측정된 교환 가능성으로부터의 편차가 작은 데이터의 경우, 전략은 최적의 교환 가능 길이에 근접한 길이를 달성하며, 편차가 증가함에 따라 점진적으로 성능이 저하된다.
  • 적대적: 제한이 없는 경우($Q = \Delta(B)$), 전략은 유효성을 보장하지만 자명한 경계보다 나은 효율성을 보장할 수 없으며, 이는 $Q$-제한의 필요성을 확인해 준다.
• $\epsilon$-캘리브레이션: 결과는 $\epsilon$-캘리브레이션 예측 모델을 사용하는 전략(정리 34)으로 확장되며, $\epsilon$에 의존하는 수렴 경계를 제공한다.

의의 및 주장
본 논문은 유효성과 효율성 사이의 긴장을 해결하는 적응형 컨포멀 추론을 위한 통합된 이론적 프레임워크를 제공한다고 주장한다. 블랙웰 접근성을 활용함으로써, 저자들은 다음과 같은 단일 알고리즘을 설계할 수 있음을 입증한다:

1. 데이터 생성 메커니즘에 관계없이 유효성을 보장한다.
2. 효율성을 극대화하기 위해 데이터의 "확률적 성격"에 자동으로 적응한다.
3. 극한의 경우(교환 가능 및 적대적)에 알려진 최적의 결과를 회복하는 동시에, 기존 방법론들이 이론적 뒷받침이 부족했던 중간 단계의 현실적인 시나리오(예: 시계열 예측)에 대해 새로운 의미 있는 보장을 제공한다.

저자들은 이 연구를 "Best of Many Worlds" 솔루션으로 포지셔닝하며, 전략이 특정 $Q$-제한을 인지하지 못하더라도 그것이 존재한다면 이를 활용함으로써 데이터 분포에 기반한 하이퍼파라미터 튜닝의 필요성을 피한다고 설명한다. 또한, 이 작업은 완전한 적대적 설정의 한계를 강조하며, 효율성 보장을 위해서는 데이터에 대한 구조적 가정이 필요함을 재확인한다.