Approximate full conformal prediction in an RKHS

기술 요약: RKHS에서의 근사적 전전체-컨포멀 예측 (Approximate Full-Conformal Prediction in an RKHS)

문제 정의
전체-컨포멀 예측(Full-conformal prediction)은 광범위한 추정기에 대해 보장된 커버리지를 가진 신뢰 예측 영역을 구축하는 분포-무관(distribution-free) 프레임워크이다. 그러나 이의 실제적인 적용은 계산적 불가능성으로 인해 심각하게 제한된다. 새로운 입력 $X_{n+1}$에 대한 전체-컨포멀 예측 영역을 계산하려면, 가능한 모든 후보 출력 $y \in \mathcal{Y}$에 대해 비정합성 점수(non-conformity score)를 평가해야 한다. 이때 기본 예측기 $\hat{f}_{D_y}$는 새로운 점 $(X_{n+1}, y)$를 포함하는 $D_y$를 사용하여 매번 다시 학습되어야 하므로, $\mathcal{Y} = \mathbb{R}$인 경우 무한한 수의 추정기를 학습시켜야 하는 상황이 발생한다.

분할-컨포멀(split-conformal) 및 교차-컨포멀(cross-conformal) 예측과 같은 기존의 대안들은 고정된 수의 예측기를 학습함으로써 계산 비용을 줄인다. 그러나 이러한 방법들은 훈련 과정에서 데이터를 버리거나 분할함으로써 정보의 손실을 초래하며, 결과적으로 더 크고 덜 유익한 예측 영역을 생성한다. 폐형 해법(예: 릿지 회귀)이나 특정 p-값 형태에 의존하는 다른 접근 방식들은 좁은 설정에 국한되며, 임의의 손실 함수나 재생 커널 힐베르트 공간(RKHS)으로 일반화되지 않는다.

방법론
저자들은 데이터를 분할하지 않고도 효율적으로 전체-컨포멀 예측 영역을 근사하는 일반적인 전략을 제안한다. 이 방법론의 핵심은 다음과 같다:

1. 근사적 예측기: 모든 후보 $y$에 대해 예측기를 다시 학습시키는 대신, 고정된 점 $z$에서 훈련된 고정된 예측기 $\hat{f}_{D_z}$ 또는 영향 함수(influence functions)에 기반한 1차 보정을 사용하여 예측기 $\hat{f}_{D_y}$를 근사한다.
2. 근사적 비정합성 점수: 근사된 예측기를 사용하여 근사적 비정합성 점수 $\tilde{S}_{D_y}$를 정의한다.
3. 근사 오차의 경계 설정: 결정적으로, 본 방법은 실제 점수와 근사 점수 사이의 불일치에 대한 명시적인 상한($\tau$)을 도출한다. 이 경계는 손실 함수의 매끄러움(smoothness)과 커널의 특성에 의존한다.
4. 영역 샌드위치화 (Sandwiching the Region): 이러한 오차 경계를 컨포멀 p-값 계산에 통합함으로써, 저자들은 "상부" 근사 영역($\hat{C}^{up}$)과 "하부" 근사 영역($\hat{C}^{lo}$)을 구축한다. 실제 전체-컨포멀 영역은 이 샌드위치 구조 내에 존재함이 보장된다 ($\hat{C}^{lo} \subseteq \hat{C}^{full} \subseteq \hat{C}^{up}$).
5. 두께 정량화 (Thickness Quantification): 근사 영역과 전체-컨포멀 영역 사이의 대칭 차이(symmetric difference)의 부피를 정량화하기 위해 "두께(thickness)"라는 새로운 지표를 도입하였다. 이는 단순한 커버리지 확률을 넘어 근사의 타이트함(tightness)을 측정하는 척도가 된다.

저자들은 손실 함수의 매끄러움 가정에 따라 세 가지 수준의 근사를 개발하였다:

• 레벨 0 (균등 안정성, Uniform Stability): 손실 함수와 점수 함수의 균등 립시츠 상수(Lipschitz constants)를 사용한다. 이는 균등 안정성 접근 방식과 유사한 경계를 복구하지만, 일반적인 손실 함수에 대해서도 RKHS 내에서 작동한다.
• 레벨 1 (국소 안정성, Local Stability): 손실 함수의 미분 가능성을 활용하여 $y$에 따라 변하는 국소 안정성 경계를 도출함으로써 근사 상수를 정교화한다.
• 레벨 2 (영향 함수, Influence Functions): 고차 매끄러움(2회 및 3회 미분 가능)과 영향 함수(Bouligand 영향 함수)를 활용하여, $y$를 통해 1차 테일러 전개로 의존하는 예측기 근사를 생성한다. 이는 근사 오차에 대해 더 빠른 수렴 속도를 제공한다.

주요 기여

• 일반적 근사 전략: 본 논문은 로그코시(Logcosh), 슈도-휴버(Pseudo-Huber), 평활화된 핀볼(smoothed Pinball)과 같은 강건한 손실 함수를 포함하여, 일반적인 (비이차) 손실 함수를 사용하는 RKHS 환경에서 전체-컨포멀 영역을 근사하기 위한 분포-무관하고 일반적인 프레임워크를 제공한다.
• 비점근적 보장 (Non-Asymptotic Guarantees): 점근적 보장만을 제공하는 기존의 영향 함수 기반 접근 방식과 달리, 본 연구는 근사 품질에 대한 비점근적 경계를 제공하며 결과 영역이 유효한 신뢰 영역(커버리지 $\geq 1-\alpha$)임을 보장한다.
• 두께 지표: "두께"의 도입을 통해 단순 커버리지 확률이 아닌 부피(르베그 측도) 관점에서 근사 영역과 전체-컨포멀 영역 사이의 불일치를 정량화할 수 있게 하였다.
• 개선된 수렴 속도: 영향 함수를 활용함으로써, 저자들은 근사 오차가 균등 안정성 경계($O(n^{-1+r})$)보다 더 빠른 속도($O(n^{-1+r+\min(-1+2r, 0)})$)로 감소함을 입증하였다. 특히 규제 매개변수 $\lambda$가 느리게 감소할 때 더욱 두드러진다.

결과

• 이론적 경계: 이론적 분석에 따르면, 근사의 두께는 커널의 특성, 규제 매개변수 및 손실의 매끄러움에 의존하는 항들에 의해 상한이 결정된다. 매끄러운 손실 함수의 경우, 샘플 크기 $n$이 증가함에 따라 경계가 크게 타이트해진다.
• 실험적 성능: 합성 데이터(Friedman1)에 대한 실험에서 네 가지 전략(분할-컨포멀, 균등 안정성(레벨 0), 국소 안정성(레벨 1), 영향 함수(레벨 2))을 비교하였다.
  • 커버리지: 제안된 모든 방법은 목표 수준($1-\alpha = 0.9$)에 근접한 경험적 커버리지를 달ides한다.
  • 영역 크기: 영향 함수 기반 방법이 낮은 분산과 함께 가장 좁은(가장 유익한) 예측 영역을 생성하며, 분할-컨포멀 및 안정성 기반 방법보다 우수한 성능을 보인다.
  • 계산: 영향 함수 방법은 헤시안 행렬 역행렬 계산으로 인해 더 많은 계산 시간이 소요되지만, 여전히 실행 가능하다. 국소 안정성 방법은 정밀도와 계산 비용 사이의 유리한 절충안을 제공한다.
• 시각화: 샘플 크스에 따른 "두께" 간극의 로그-로그 그래프는 이론적 수렴 속도를 확인시켜 주며, 영향 함수 접근 방식이 균등 안정성 접근 방식보다 더 빠르게 수렴함을 보여준다.

의의 및 주장
저자들은 본 연구가 전체-컨포멀 예측의 이론적 최적성과 분할-컨포멀 방법의 계산적 실행 가능성 사이의 간극을 메운다고 주장한다. 데이터를 분할하는 것을 피함으로써, 제안된 방법은 훈련을 위해 전체 데이터셋을 활용하여 정보를 보존하고 더 타이트한 예측 영역을 생성한다. 이 프레임워크는 전체-컨포멀 근사를 광범위한 손실 함수 및 RKHS 설정으로 확장하여, 결과 영역의 커버리지와 "타이트함"(두께) 모두에 대해 엄격한 비점근적 보장을 제공한다는 점에서 의의가 있다. 저자들은 이 근사 방식이 계산적으로 효율적이면서도(단 하나 또는 몇 개의 예측기 평가만 필요), 전체-컨포멀 프레임워크의 분포-무관한 타당성을 유지한다는 점을 강조한다.