Online Conformal Prediction Beyond Feedback

문제 정의: 피드백을 넘어선 온라인 컨포멀 예측 (Online Conformal Prediction Beyond Feedback)

불확실성 정량화는 안전이 중요한 애플리케이션에 머신러닝을 배포하는 데 있어 매우 중요합니다. 온라인 컨포멀 예측(Online Conformal Prediction, OCP)은 비독립 동일 분포(non-i.i.d.) 데이터 스트림과 블랙박스 분류기에 대해서도 사용자가 지정한 빈도로 실제 레이블이 포함되는 것을 보장하는 예측 집합을 생성하기 위한 이론적으로 원칙적인 프레임워크를 제공합니다. 그러나 표준 OCP 방법은 피드백 루프에 의존합니다. 즉, 예측 집합을 발행한 후, 알고리즘은 과거의 미커버리지(miscoverage)를 보상하기 위해 미래의 집합을 조정할 수 있도록 피드백(실제 레이블 또는 커버리지 신호)을 받습니다.

본 논문은 이러한 피드백을 사용할 수 없거나 제한적인 상황을 다룹니다. LLM(대규모 언어 모델)을 위한 잠재적 프로브(latent probes)와 같은 많은 안전 필수 시나리오에서, 알고리즘은 입력을 안전 카테고리로 분류해야 합니다. 만약 프로브가 기권(인간이나 더 강력한 시스템에 질의)한다면, 레이블은 결국 가용해질 수 있습니다. 그러나 프로브가 배포된 결정을 내린 입력에 대해서는 레이블이 절대 관찰되지 않습니다. 이는 "피드백을 넘어선(beyond feedback)" 시나리오를 생성합니다: 학습자는 예측 집합을 출력할 것인지, 아니면 올바른 레이블을 질의할 것인지 선택해야 하며, 두 가지를 모두 할 수는 없습니다. 결과적으로, 학습자는 배포된 예측 집합이 올바른지 여부를 결코 관찰할 수 없으며, 이는 기존 OCP 방법에서 사용되는 표준 보상 메커니즘을 방해합니다.

방법론: 질의를 포함한 OCP (OCPQ)

저자들은 이러한 피드백 너머의 프로토콜을 위해 설계된 **질의를 포함한 온라인 컨포멀 예측(Online Conformal Prediction with Queries, OCPQ)**을 제안합니다. 이 접근 방식은 두 가지 주요 단계로 진행됩니다.

1. 부분 모니터링으로의 환원: 이 문제는 유한 부분 모니터링 게임(finite partial monitoring game)으로 환원됩니다. 게임의 "팔(arms)"은 유한한 예측 임계값 집합 $M \subset [0, 1]$과 별도의 질의(query) 동작으로 구성됩니다.

   • 예측 동작(Prediction Action): 임계값 $m \in M$을 선택하면 블랙박스 분류기 $C$를 기반으로 예측 집합 $\Gamma_C(x_t, m)$을 생성합니다. 이 동작은 관찰값(null feedback $\perp$)과 직접적인 보상을 생성하지 않습니다.
   • 질의 동작(Query Action): 질의 동작을 선택하면 실제 레이블 $y_t$가 드러나지만, 예측 집합은 생성되지 않으며 보상은 0을 생성합니다.
   • 보상 구조(Reward Structure): 알고리즘은 보조 보상 함수 $R(m, t)$를 정의합니다. 만약 실제 레이블이 예측 집합에 포함되면($y_t \in \Gamma_C(x_t, m)$), 보상은 $1 - m(1-\beta)$가 됩니다 (여기서 $\beta$는 커버리지와 효율성 사이의 트레이드오프를 제어하는 사용자 정의 파라미터입니다). 레이블이 포함되지 않은 경우 보상은 0입니다. 질의 동작은 항상 0의 보상을 생성합니다. 이 구조는 학습자가 커버리지를 유지하면서도 타이트한 임계값(작은 $m$)을 선택하도록 유도합니다.

2. 알고리즘 설계: OCPQ는 Cesa-Bianchi, Lugosi, 및 Stoltz(2004)의 **레이블 효율적 지수 가중 포캐스터(label-efficient exponentially weighted forecaster)**를 적응시킵니다.

   • 각 라운드 $t$에서, 알고리즘은 고정된 확률 $\epsilon$으로 질의를 수행합니다.
   • 질의가 수행되면, 실제 레이블 $y_t$가 관찰됩니다. 알고-리즘은 역확률 가중치 부여(inverse probability weighting) 방식을 사용하여 모든 임계값 $m \in M$에 대한 누적 보상 추정치 $\hat{Z}_{m,t}$를 업데이트하며, 이는 예측이 이루어졌을 경우 얻었을 보상을 효과적으로 재구성합니다.
   • 질의가 수행되지 않으면, 알고리즘은 현재의 추정치 $\hat{Z}_{m,t}$에 기반한 지수 가중 분포에서 임계값 $m_t$를 샘플링하고 그에 상응하는 예측 집합을 출력합니다. 이때 피드백은 수신되지 않습니다.

이론적 결과

본 논문은 길이 $T$인 무관한 적대적 데이터 스트림(oblivious adversarial data stream) 하에서 OCPQ에 대한 유한 시계열 보증을 확립합니다.

• 후회(Regret): 사후 최적의 고정 임계값에 대한 기대 후회는 $O(T^{2/3})$입니다. 구체적으로, $\epsilon = T^{-1/3}$이고 $\eta = T^{-2/3}\sqrt{\ln|M|}$일 때, 후회는 $T^{2/3}(2\sqrt{\ln|M|} + 1)$로 제한됩니다. 저자들은 이 비율이 이 클래스의 부분 모니터링 게임에 대해 점근적으로 최적이라고 언급합니다.
• 커버리지(Coverage): 기대 커버리지 비율 $p_{cover}$는 다음을 만족합니다:
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  이는 $T$가 증가함에 따라 커버리지가 사용자가 정의한 목표 $\beta$에 접근함을 보장합니다.
• 질의율(Query Rate): 알고리즘은 기대적으로 $T^{-1/3}$의 비율로만 레이블을 질의합니다.
• 고확률 경계(High-Probability Bounds): 본 논문은 후회와 커버리지 모두에 대한 고확률 경계를 도출하여, 알고리즘 성능의 분산이 제어되며 병리적인 동작을 보이지 않음을 입증합니다.

실험 결과

접근 방식을 검증하기 위해 실제 데이터셋에서 실험이 수행되었습니다.

• 분포 변화(Distribution Shift): OCPQ는 훈련 분포와 테스트 분포가 다른(예: MNIST에서 USPS, 또는 MNIST에서 MNIST-C) 표준 벤치마크(MNIST, CIF-10, CIF-100)에서 테스트되었습니다. 결과는 커버리지-효율성 트레이드오프가 $\beta$ 파라미터를 통해 제어될 수 있음을 보여주었습니다. 경험적 커버리지는 이론적 하한을 지속적으로 상회했습니다.
• LLM 안전 모니터링: 본 방법은 Vanilla 및 적대적으로 재작성된 프롬프트를 모두 포함하는 WildGuardMix 데이터셋을 사용하여 LLM 프롬프트의 안전 모니터링에 적용되었습니다. 기본 분류기의 정확도가 적대적 프롬프트에서 크게 떨어졌음에도 불구하고, OCPQ는 유익한 예측 집합을 유지하면서 이론적 하한 이상의 커버리지를 유지했습니다.
• 비교: 전체 피드백을 가정하는 ACI(Adaptive Conformal Inference)와 비교했을 때, OCPQ는 훨씬 적은 정보(약 5%의 라운드만 질의)를 사용하면서도 대등한 커버리지-효율성 프런티어를 달성했습니다.

의의 및 기여

본 논문은 다음과 같은 기여를 주장합니다.

1. 새로운 프로토콜: 배포된 예측이 절대 평가되지 않는 "피드백을 넘어선" 상황, 즉 기권된 질의에 대해서만 레이블을 사용할 수 있는 안전 필수 애플리케이션의 일반적인 시나리오에 OCP를 공식화했습니다.
2. 알고리즘적 환원: 이 문제를 부분 모니터링 게임으로 환원하고, 이를 해결하기 위해 레이블 효율적 적대적 학습 기술을 적응시켰습니다. 특히 질의를 예측을 따르는 것이 아니라 예측을 대체하는 별개의 동작으로 취급하도록 포캐스터를 수정했습니다.
3. 이론적 보증: 이 설정에서의 OCP에 대한 유한 시계열 기대 후회 및 커버리지 보증을 제공하며, 단 $O(T^{-1^{-3}})$의 레이블 질의만으로 유효한 불확실성 정량화가 가능하다는 것을 보여줍니다.
4. 실질적 효과성: 실험은 희소한 감독(무작위 질의)이 배포된 예측 집합으로부터의 피드백 없이도 유용한 커버리지와 효율성 트레이드오프를 유지하는 데 충분하다는 것을 입증하며, 이는 적대적 분포 변화 하에서도 마찬가지입니다.

저자들은 본 방법이 보수적(경험적 커버리지가 종종 하한을 초과함)이라는 점을 언급했는데, 이는 부분 모니터링 게임 공식화에 필요한 약한 가정 때문입니다. 향후 연구에서는 덜 보수적인 방법이나 적응형 적대자(adaptive adversaries)로의 확장을 탐구할 수 있습니다.