기술 요약: 순간에 대한 베팅 – 온라인 교환 가능성 테스트를 위한 Legendre Jumper 마틴게일

문제 정의

적합적 예측(Conformal Prediction)에서 예측 집합의 유효성은 교환 가능성(exchangeability) 가정에 의존하며, 이는 생성된 p-값의 시퀀스가 $[0, 1]$ 상의 균등 분포를 따르는 독립 동일 분포(IID)임을 의미한다. 이 가정의 위반은 분포 변화(distributional shifts)를 나타낸다.

교환 가능성을 온라인으로 테스트하기 위해 **컨포멀 테스트 마틴게일(Conformal Test Martingales, CTMs)**이 사용되지만, 표준 Simple Jumper (SJ) (Vovk et al., 2022)는 결정적인 한계를 갖는다. SJ는 1차 이동 레전드르 다항식(shifted Legendre polynomial)에 기반한 선형 베팅 함수를 사용하기 때문에, 기하학적으로 p-값의 평균(location) 변화를 감지하는 데 국한된다. 따라서 SJ는 평균은 유지하면서 분산, 왜도(skewness), 또는 첨도(kurtosis)와 같은 고차 모멘트를 변화시키는 분포 변화를 감지할 때 유의미한 자산을 축적하지 못한다. 또한, 여러 베팅 전략을 결속하려는 시도는 종종 "점핑 세금(jumping tax)" 문제에 직면하는데, 이는 자본이 지수적으로 증가하는 상태 공간(state space)으로 희석되어 감지 속도를 심각하게 저해하는 현상을 말한다.

방법론

본 논문은 $[0, 1]$ 구간에서 직교하는 **이동 레전드르 다항식($\tilde{P}_k$)**에 기반한 컨포멀 테스트 마틴게일 제품군을 제안한다. 이 다항식들은 p-값 분포의 특정 모멘트 편차를 감지할 수 있는 베팅 함수의 기초 역할을 한다.

1. Simple Legendre Jumper (SLJ)

SLJ는 선형 베팅 함수를 임의의 차수 $k$를 가진 이동 레전드르 다항식으로 대체하여 Simple Jumper를 일반화한다:
$$f^{(k)}_\epsilon(p) = 1 + \epsilon \tilde{P}_k(p)$$
여기서 $\epsilon$은 이산 그리드에서 선택된 파라미터이다.

• 메커니즘: $k=1$인 경우 표준 SJ를 복구하며(평균 변화 감지), $k=2$인 경우 분산 변화를, $k=3$인 경우 왜도 변화를 감지한다. 그 외의 차수도 마찬가지다.
• 한계: 단일 차수 $k$에 대해서만 베팅할 경우, 마틴게일은 다른 모멘트에서의 지배적인 변화를 놓치게 되어 최적의 자산 축적에 실패할 수 있다.

2. Product Legendre Jumper (PLJ)

복잡하고 다중 모드적인 편차를 동시에 포착하기 위해, PLJ는 여러 차수 $K$의 베팅 함수들을 하나의 곱으로 결합한다:
$$f^K_\epsilon(p) = \frac{\prod_{k \in K} (1 + \epsilon_k \tilde{P}_k(p))}{Z(\epsilon)}$$
여기서 $Z(\epsilon)$은 베팅 함수의 적분값이 1이 되도록 보장하기 위해 $|K| \ge 3$일 때 필요한 정규화 상수이다.

• "점핑 세금(The Jumping Tax)": PLJ는 결합 상태 공간 $\mathcal{E} = \prod_{k \in K} \mathcal{E}_k$ 상에서 마르코프 체인을 유지한다. 차수의 수 $|K|$가 증가함에 따라 상태 공간의 크기는 지수적으로 성장한다($|\mathcal{E}| = g^{|K|}$). 점핑 세금이란 자본의 희석을 의미한다. 즉, 환경이 변화할 때 점핑 메커니즘이 새로운 자본을 이 거대한 상태 공간 전체에 균등하게 분산시킴으로써, 최적의 베팅 전략에 자본이 집중되는 것을 지연시키는 현상이다.

3. Variational Legendre Jumper (VLJ)

PLJ의 지수적 스케일링 문제를 해결하기 위해, 저자들은 변분 추론(variational inference)의 평균장 근사(mean-field approximation)에서 영감을 얻은 Variational Legendre Jumper를 도입한다.

• 디커플링(Decoupling): 단일 곱 공간 위의 하나의 마르코프 체인을 실행하는 대신, VLJ는 각 차수 $k \in K$에 대해 $|K|$개의 독립적인 서브 점퍼(sub-jumper)를 실행한다.
• 합의(Consensus): 각 단계에서 VLJ는 서브 점퍼의 자산 가중 평균을 기반으로 각 차수에 대한 합의 파라미터 $\bar{\epsilon}_k$를 계산한다.
• 글로벌 베팅: 글로벌 마틴게일은 이 합의된 파라미터들에서 평가된 베팅 함수들의 정규화된 곱을 사용하여 업데이트된다.
• 복잡도: 이는 계산 비용을 지수적 $O(g^{|K|})$에서 선형 $O(|K| \cdot g)$로 감소시켜, 고차 모멘트 테스트를 최소한의 통계적 성능 손실로 계산 가능하게 만든다.

4. Composite Legendre Jumper

Vovk et al. (2022)의 프레임워크를 따라, Composite Legendre Jumper는 점핑 비율 $J \in \{10^{-4}, \dots, 1\}$의 그리드에 대해 베이스 마틴게일(SLJ, PLJ 또는 VLJ)을 평균화한다.

• 강건성: 이는 분포 변화의 타임스케일(timescale)을 알 수 없는 경우에도 강건함을 보장한다.
• 자산 하한선(Wealth Floor): $J=1$의 포함은 교환 가능성 하에서 마틴게일이 절대 $1/|\mathcal{E}|$ 미만으로 떨어지지 않음을 보장하며, 이는 고정 비율 변형 모델들이 갖지 못한 특성이다.

주요 기여

1. 베팅 함수의 일반화: 선형 베팅 함수를 임의 차수의 이동 레전드르 다항식으로 확장하여 분산, 왜도 및 고차 모멘트 편차 감지를 가능하게 하는 Simple Legendre Jumper를 도입하였다.
2. 점핑 세금 해결: 결합 편차를 포착하기 위한 Product Legendre Jumbo를 개발하였고, 이어 평균장 근사를 통해 결합 적응 문제를 인수분해하는 Variational Legendre Jumper를 개발하였다. 이를 통해 통계적 성능을 유지하면서 상태 공간 스케일링을 지수적에서 선형으로 성공적으로 축소하였다.
3. 복합적 강건성: 이러한 방법들을 Composite Legendre Jumper로 통합하여, 분포 변화의 타임스케일에 자동으로 적응하고 자산 하한선을 제공하는 구조를 구축하였다.
4. 실증적 검증: Wine Quality 데이터셋을 이용한 실험을 통해, 결합된 방법들(PLJ 및 VLJ)이 단일 차수 마틴게일보다 분포 변화 상황에서 일관되게 우수한 성능을 보임을 입증하였으며, 변분 근사가 실제 곱(product) 모델과 비교했을 때 무시할 만한 수준의 성능 손실만을 가짐을 보여주었다.

결과

저자들은 네 가지 데이터 순서(셔플된 데이터(교환 가능), 급격한 변화점(Red $\to$ White, White $\to$ Red), 원본 순서)에 대해 컨포멀 최근접 이웃 분류기를 사용하여 Wine Quality 데이터셋에서 제안된 방법들을 평가하였다.

• 교환 가능성: 셔플된 데이터 하에서 모든 마틴게일은 0 근처에 머물거나 약간 감소하였으며, 이는 허위 경보를 울리지 않음을 확인시켜 준다.
• 분포 변화: 비교환적 순서 하에서, $K=\{1, 2, 3\}$을 적용한 Product 및 Variational Legendre Jumpers가 일관되게 가장 높은 최종 로그 마틴게일 값을 달성하였으며, 단일 차수 Simple Legendre Jumper ($k=1$)보다 로그 스케일 증거 측면에서 30%~60% 더 높은 성능을 보였다.
• 단일 차수의 실패: 분산($k=2$) 또는 왜도($k=3$)에 대해서만 베팅하는 마틴게일은 변화가 여러 모멘트를 포함할 경우 성능이 저조하였으며, 결합된 접근 방식보다 몇 차수 낮은 수준의 증거만을 축적하였다.
• 효율성 vs. 성능: **Variational Legendre Jumper (VLJ)**는 **Product Legendre Jumper (PLJ)**의 성능과 거의 정확히 일치하면서도 훨씬 적은 상태(예: $K=\{1, 2, 3\}$에 대해 125개 상태 대신 15개 상태)를 요구하였다.
• Composite의 우월성: Composite Legendre Jumper는 분포 변화 상황에서 고정 비율 변형 모델보다 압도적으로 우수한 성능을 보였으며(예: 고정 비율 $\approx 90$ 대비 \log_{10} M_n \approx 100} 도달), 교환 가능성 하에서 고정 비율 모델에서 나타나는 느린 손실 축적 현상을 방지하였다.

의의 및 주장

본 논문은 분포 변화의 타임스케일을 알 수 없는 실무자들에게 Composite Legendre Jumper가 **기본 선택지(default choice)**가 되어야 한다고 주장한다. 이 모델은 다음을 제공하는 강력한 솔루션이다:

1. 선형 베팅 함수가 놓칠 수 있는 균등 분포로부터의 복잡하고 다중 모드적인 편차를 감지한다.
2. 평균장 인수분해를 통해 결합 베팅 전략과 관련된 "차원의 저주"를 피한다.
3. 이론적 및 실무적 자산 하한선을 제공하여 귀무 가설 하에서의 안정성을 보장한다.

저자들은 변분 근사가 경험적으로 실제 곱 모델과 대등한 성능을 보이지만, 평균장 인수분해로 인한 통계적 성능 손실에 대한 이론적 경계는 여전히 미해결 과제로 남아 있다고 언급하였다. 또한, 효율성을 더욱 최적화하기 위해 데이터 기반의 차수 선택(Neyman의 smooth test에 대한 Ledwina의 접근 방식과 유사한 방식)을 탐구하는 것이 향후 연구 과제라고 제언하였다. 구현은 Python 패키지 online-cp를 통해 제공된다.