Parameter-Free and Group Conditional Online Conformal Prediction

기술 요약: 파라미터 프리 및 그룹 조건부 온라인 컨포멀 예측 (POGO)

1. 문제 설정 및 동기

머신러닝 모델은 데이터 분포가 시간에 따라 변하여 표준 컨포멀 예측(Conformal Prediction, CP)에 요구되는 교환 가능성(exchangeability) 가정을 위반하는 고위험, 비정상성 환경(예: 의료 트리아지, 자율 주행 차량)에 점점 더 많이 배치되고 있습니다. **온라인 컨포멀 예측(Online Conformal Prediction, OCP)**은 적대적 데이터 스트림에 대해 예측 집합(prediction sets)의 시퀀스를 생성함으로써 이 문제를 해결합니다. 그러나 표준 OCP 방법은 일반적으로 한계 커버리지(marginal coverage)(즉, 전체 오차율이 $1-\alpha$에 수렴함)만을 보장합니다. 이러한 한계 커버리지는 특정 하위 집단에 대한 체계적인 과소 커버리지(under-coverage)를 은폐할 수 있으며, 이는 공정성 및 안전성 문제로 이어질 수 있습니다.

이전 연구들은 특정 그룹에 대한 커버리지 보장을 확보하기 위해 **그룹 조건부 OCP(Group-Conditional OCP, G-OCP)**를 제안해 왔으나, 기존 방법들(예: GCACI)은 수동으로 조정해야 하는 학습률(learning rates)(단계 크기)에 의존합니다. 적대적이거나 변화하는 데이터 환경에서 학습률을 조정하는 것은 다음과 같은 이유로 문제가 됩니다:

1. 튜닝을 위한 검증 세트(validation set)를 사용할 수 없습니다.
2. 임의의 데이터 변화는 이전에 "좋았던" 학습률을 부적절하게 만들 수 있습니다.
3. 기존의 파라미터 프리(parameter-free) OCP 방법들(예: UP-OCP)은 그룹 조건부 보장이 아닌 한계 커버리지만 달성합니다.

해결하고자 하는 핵심 문제는, 수동 하이퍼파라미터 튜닝 없이 엄격한 그룹 조건부 커버리지 보장을 동시에 제공하는 파라미터 프리 OCP 알고리즘을 설계하는 것입니다.

2. 방법론: POGO

저자들은 그룹 조건부 OCP를 위한 최초의 파라미터 프리 알고리즘인 POGO(Portfolios for Online Group Conformal)를 제안합니다. 이 방법론은 한계 OCP(UP-OCP)에 적용되었던 유니버설 포트폴리오(Universal Portfolio, UP) 최적화 개념을 기반으로 하며, 이를 여러 개의 중첩된 그룹을 처리할 수 있도록 확장한 것입니다.

2.1 문제 정식화

데이터 스트림 $(X_t, Y_t)$와 예측기 $\hat{Y}_t$가 주어졌을 때, 목표는 예측 구간 $I_t = [\hat{Y}_t - \tau_t, \hat{Y}_t + \tau_t]$가 다음을 만족하는 반지름(radius) 시퀀스 $\tau_t$를 학습하는 것입니다:
$$\lim_{T \to \infty} \left| \frac{1}{T_j} \sum_{t=1}^T \mathbb{1}\{Y_t \in I_t\} c_j(X_t) - (1-\alpha) \right| = 0$$
여기서 $c_j(X_t) \in [0, 1]$은 그룹 멤버십에 대한 소프트 지표 함수이며, $T_j$는 그룹 $j$의 누적 횟수입니다.

2.2 선형 파라미터화

표준 OCP가 스칼라 반지름을 학습하는 것과 달리, POGO는 $k$차원 파라미터 벡터 $\theta_t \in \mathbb{R}^k$를 학습합니다. 반지름은 그룹 멤버십 벡터 $c(X_t)$의 선형 함수로 파라미터화됩니다:
$$\tau_t(X_t) = \langle \theta_t, c(X_t) \rangle$$
이를 통해 알고리즘은 샘플의 특정 그룹 멤버십에 따라 서로 다른 반지름을 할당하면서도, 단일화된 통합 예측 구간을 생성할 수 있습니다.

2.3 포트폴리오 최적화 메커니즘

POGO는 $\theta_t$의 학습을 포트폴리오 최적화 문제로 취급합니다.

1. 오차로서의 서브그레이디언트(Subgradients as Errors): 알고리즘은 각 그룹에 대해 핀볼 손실(quantile loss/pinball loss)을 정의합니다. 누적 서브그레이디언트 합 $\sum g_{t,j}$의 $j$번째 항목은 그룹 $j$에 대한 미커버리지 오차를 정량화합니다. 구체적으로, $j$번째 항목은 그룹 $j$의 미커버리지 오차에 해당합니다.
2. 부(Wealth) 프로세스: 각 그룹 $j$에 대해, POGO는 두 개의 주식으로 구성된 "시장"을 구축합니다. 이 주식들의 수익률은 현재 예측이 실제 레이블을 포함하는지 여부에 따라 달라집니다:
   • 만약 예측이 실패하면(과소 커버리지), 한 주식은 높은 수익을 냅니다.
   • 만약 예측이 성공하면(커버), 다른 주식은 완만한 수익을 냅니다.
3. 유니버설 포트폴리오(Universal Portfolio, UP): POGO는 각 그룹 $j$에 대해 포트폴리오 가중치 $\lambda_{t,j}$를 학습하기 위해 유니버설 포트폴리오 알고리즘을 채택합니다. 목표는 각 그룹과 관련된 "부(wealth)" $W_{t,j}$의 로그 성장을 극대화하는 것입니다.
4. 파라미터 업데이트: 파라미터 $\theta_{t,j}$는 부 프로세스 $W_{t,j}$와 포트폴리오 가중치 $\lambda_{t,j}$로부터 직접 유도되어, 누적 서브그레이디언트가 느리게 성장하도록 보장합니다. 이러한 느린 성장은 그룹 조건부 미커버리지가 제한됨을 의미합니다.

결정적으로, 이 과정은 파라미터 프리입니다. 즉, 학습률 $\eta$나 단계 크기를 필요로 하지 않으며, 대신 유니버설 포트폴리오 알고리즘의 내재적 특성에 의존합니다.

3. 주요 기여

1. 최초의 파라미터 프리 G-OCP 알고리즘: 수동 학습률 튜닝 없이 그룹 조건부 커버리지 보장을 제공하는 POGO를 도입했습니다.
2. 엄격한 유한 시간 보장(Finite-Time Guarantees): 저자들은 POGO에 대한 이론적 커버리지 경계를 확립했습니다. 그룹 $j$의 미커버리지 비율은 다음과 같이 제한됩니다:
   $$\text{MisCov}_T(c_j) \leq \frac{1}{T_j} \left[ U_T(k) + \sqrt{2T_j \alpha(1-\alpha) U_T(k)} \right]$$
   여기서 $U_T(k)$는 그룹 수 $k$와 시간 $T$에 대해 로그 스케일로 증가합니다. 이는 알려진 가장 우수한 유한 시간 그룹 커버리지 결과입니다.
3. 우수한 확장성: 이론적 분석에 따르면 POGO의 오차 경계는 그룹 수 $k$에 대해 로그 스케일($O(\ln k)$)로 의존하는 반면, 기존의 파라미터 의존적 방법(예: GCACI)은 $\sqrt{k}$에 따라 스케일이 변하며 학습률 선택에 크게 의존합니다.
4. 단일 구간 출력: 각 그룹에 대해 별도의 OCP 알고리즘을 실행하여 서로 다른 $k$개의 반지름을 생성하는 단순한 접근 방식과 달리, POGO는 각 샘플에 대해 단일 반지름 $\tau_t$를 생성하여 상충하는 구간 문제와 그룹 멤버십에 대한 잠재적 프라이버시 유출 문제를 방지합니다.

4. 실험 결과

저자들은 합성 데이터셋과 실제 데이터셋을 사용하여 POGO를 GCACI(현재 그룹 조건부 OCP의 표준) 및 UP-OCP(파라미터 프리 한계 OCP)와 비교 평가했습니다.

4.1 합성 실험

• 유계 및 점진적 변화 스코어: POGO는 모든 그룹에 대해 목표 커버리지율을 3% 이내로 달와성하며, GCACI 변형 모델들에 비해 가장 작은 평균 반지름을 생성합니다. 또한 높은 적응성을 유지하며, 연속적인 미커버지 이벤트의 최장 길이는 가장 잘 튜닝된 GCACI와 유사한 수준입니다.
• 급격한 변화(Abrupt Shifts): 데이터 분포가 급격히 변할 때, POGO는 견고함을 유지합니다. 반면, 고정된 학습률을 사용하는 GCACI(심지어 $\eta=0.01$과 같이 잘 튜닝된 경우라도)는 적응성이 떨어져, 데이터에 의해 학습률이 효과적으로 "재튜닝"될 때까지 긴 미커버지 시퀀스를 겪게 됩니다.
• 무계 및 증가하는 스코어: 특정 그룹의 비정형성 점수(non-conformity scores)가 이차 함수 형태로 증가하는 시나리오에서 대부분의 GCACI 변형 모델은 목표 커버리지를 달성하는 데 실패합니다. POGO는 특히 높은 커버리지 요구 사항($1-\alpha \in [0.9, 0.95]$)에서 목표 커버리지에 더 근접한 결과를 일관되게 보여줍니다.

4.2 실제 데이터

• MIMIC-IV (ICU 입원 기간): 환자 데이터(인종, 보험, 성별을 그룹으로 사용)를 사용하여, POGO는 GCACI와 대등한 커버리지를 달성하면서도 **더 작은 예측 집합 크기(반지름)**를 보여줍니다.
• 주식 시장 (Apple, Delta, Boeing): 일일 가격 예측을 위해, POGO는 다시 한번 경쟁력 있는 성능을 입증하며 GCACI보다 작은 집합 크기로 목표 커버리지를 달성했습니다.
• 트레이드오프(Trade-offs): 특정 정적 레짐(static regime)에서 POGO가 가장 잘 튜닝된 GCACI보다 약간 더 긴 연속 미커버지 스트릭을 보일 때도 있지만, 튜닝이 불가능한 동적 또는 변화하는 레짐에서는 GCACI를 크게 압도합니다.

5. 의의 및 주장

본 논문은 POGO가 변화하는 환경에서 공정하고 견고한 불확실성 정량화를 위한 토대를 마련한다고 주장합니다. 그룹 조건부 커버리지와 파라미터 프리 온라인 학습을 결합함으로써, 이 방법은 적대적이거나 비정상적인 환경에서 치명적인 병목 현상인 수동 하이퍼파라미터 튜닝의 필요성을 제거합니다.

저자들은 다음을 강조합니다:

• POGO는 알려진 가장 우수한 유한 시간 그룹 커버리지 경계를 제공합니다.
• 학습률 선택의 취약성 없이 이러한 보장을 달성합니다.
• 데이터 분포가 정적이지 않거나 교환 가능하다고 가정할 수 없는 고위험 애플리케이션을 위한 실질적인 솔루션을 제공합니다.

논문은 POGO가 반지름에 대해 선형 명세를 사용하지만, 향후 연구에서 반지름에 대한 더 풍부한 모델을 탐구하고 캘리브레이션(calibration)과 같은 다른 형태의 온라인 불확실성 정량화로 도구를 확장할 수 있음을 언급하며 마무리합니다.