Learning to Defer in Non-Stationary Time Series via Switching State-Space Models

기술 요약: 스위칭 상태-공간 모델을 통한 비정상 시계열에서의 학습-연기 (Learning-to-Defer)

문제 정의
본 논문은 스트리밍 비정상 시계열 환경에서의 학습 - 연기 (Learning-to-Defer, L2D) 문제를 다룹니다. 모든 전문가 예측에 대한 완전한 감독 (full supervision) 과 고정된 내부 예측기를 가정하는 오프라인 L2D 설정과 달리, 제안된 설정은 다음을 포함합니다:

1. 비대칭 부분 피드백: 각 라운드 $t$에서 시스템은 컨텍스트 $x_t$와 사용 가능한 외부 전문가 집합 $E_t$를 관찰합니다. 시스템은 내부적으로 예측 (행동 0) 하거나 외부 전문가 $k \in E_t$로 연기 (쿼리 비용 $\beta_k$ 발생) 해야 합니다. 핵심적으로, 실제 결과 $y_t$는 결정 이후에 공개되므로 내부 잔차 ($e_{t,0} = \hat{y}_{t,0} - y_t$) 는 항상 관찰 가능합니다. 반면, 외부 잔차는 해당 전문가가 쿼리된 경우에만 관찰되며, 그렇지 않으면 검열 (censored) 됩니다.
2. 행동 결합 학습: 내부 예측기 $f_{\theta_t}$는 온라인으로 학습됩니다. 라우팅 결정은 학습자의 미래 상태에 직접적인 영향을 미치는데, 이는 전문가를 쿼리하면 내부 모델을 업데이트할 수 있는 추가적인 "교사" 신호 ($\hat{y}_{t,k}$) 가 제공되기 때문입니다.
3. 비정상성과 역동적 전문성: 환경은 비정상적이며, 전문가의 품질은 잠재적 체제 (regime) 간에 변화합니다. 또한 전문가 풀은 역동적입니다; 전문가들은 시간에 따라 진입, 퇴출, 또는 재진입할 수 있습니다.

목표는 즉각적인 예측 오차와 쿼리 비용 사이의 균형을 유지하면서 내부 학습자를 개선하고 체제 변화에 적응시키며, 기대 누적 라우팅 비용을 최소화하는 것입니다.

방법론: L2D-SLDS
저자들은 L2D-SLDS를 제안합니다. 이는 내부 예측기와 모든 잠재적 외부 전문가의 잔차를 **분해된 스위칭 선형 - 가우스 상태 - 공간 모델 (Switching Linear-Gaussian State-Space Model, SLDS)**을 사용하여 결합적으로 모델링하는 1 단계 온라인 프레임워크입니다.

• 생성 모델: 모델은 각 전문가 $k$의 잠재적 신뢰도를 세 가지 구성 요소로 분해합니다:

  1. 전문가 풀 간의 상관관계를 포착하고 전문가 간 정보를 전달하는 공유 글로벌 요인 $g_t$.
  2. 전문가별 고유 신뢰도를 포착하는 전문가별 고유 상태 $u_{t,k}$.
  3. 전문가 성능의 구조적 변화에 적응할 수 있도록 $M$개의 선형 - 가우스 동역학 중 하나를 선택하는 이산 체제 변수 $z_t$.
     전문가 $k$의 잔차는 신뢰도 벡터 $\alpha_{t,k} = B_k g_t + u_{t,k}$의 선형 - 가우스 방출 (emission) 로 모델링됩니다.

• 온라인 추론: 시스템은 IMM 스타일 (Interacting Multiple Model) 2 단계 필터를 사용합니다:

  1. 내부 단계: 항상 실행됩니다. 항상 관찰되는 내부 잔차 $e_{t,0}$를 포함하여 공유 요인 $g_t$와 체제 가중치를 업데이트합니다. 이는 외부 전문가가 쿼리되지 않더라도 공유 요인을 통해 모든 쿼리되지 않은 전문가에 대한 시스템의 신념을 업데이트하도록 보장합니다.
  2. 외부 단계: 외부 전문가가 쿼리된 경우에만 실행됩니다. 관찰된 외부 잔차를 포함하여 특정 전문가의 상태와 글로벌 요인을 더 정제합니다.
  3. 레지스트리 관리: 역동적인 레지스트리가 전문가의 생성과 소멸을 처리합니다. 오래된 전문가 (최대 기간 $\Delta_{max}$ 동안 사용 불가) 는 정확한 주변화 (exact marginalization) 를 통해 제거되어, 유지된 전문가의 예측 분포에 영향을 주지 않으면서 계산 및 메모리 효율성을 보장합니다.

• 학습자 인식 라우팅 점수: 라우팅 결정은 세 가지 목표를 균형 있게 고려하는 점수 $S_t(k)$에 의해 주도됩니다:

  1. 활용 (Exploitation): 내부 예측기 대비 전문가 $k$를 쿼리하는 즉각적인 초과 비용.
  2. 탐색 (정보 획득): 내부 잔차가 이미 제공하는 것 이상의 잠재 상태에 대한 불확실성을 쿼리가 얼마나 줄이는지를 측정하는 조건부 상호 정보 $I((z_t, g_t); e_{t,k} | e_{t,0})$. 이는 공유 요인에 대한 폐쇄형 항과 체제 식별에 대한 몬테카를로 항을 통해 근사됩니다.
  3. 학습자 개선: 전문가가 내부 예측기보다 우수할 확률과 그 개선의 크기에 기반한 내부 학습자의 기대 1 단계 개선 추정치.

• 행동 결합 업데이트: 전문가가 쿼리되면, 내부 학습자는 교사 정규화 목적 함수를 사용하여 업데이트됩니다. 교사 신호의 가중치는 적응적이며, 전문가의 예측 신뢰도, 실현된 유용성, 그리고 학습자와의 불일치에 기반하여 업데이트를 게이트 (gating) 합니다.

주요 기여

1. 형식화: 본 논문은 비대칭 부분 피드백, 행동 결합 내부 학습, 역동적 전문가 가용성, 그리고 상담 비용을 명시적으로 처리하는 비정상 시계열을 위한 1 단계 온라인 L2D를 형식화합니다.
2. 알고리즘: 검열 하에서 확장 가능한 추론과 전문가 간 정보 전달을 가능하게 하는 분해된 스위칭 선형 - 가우스 모델인 L2D-SLDS를 도입합니다. 이는 유지된 전문가의 주변 분포를 보존하는 레지스트리 제거 메커니즘을 포함합니다.
3. 라우팅 전략: 잠재 상태 정보 획득과 기대 학습자 개선을 결합하여 단순한 비용 최소화나 순수한 탐색을 넘어선 새로운 학습자 인식 쿼리 점수가 제안되었습니다.
4. 이론적 보장: 저자들은 시간 가변적 학습 - 연기 비교 대상 (comparator) 에 대한 오라클 후회 (regret) 분해를 증명합니다. 후회는 쿼리 보너스 예산, SLDS 예측 비용 오차 항 ($E_{SLDS}$), 그리고 내부 학습자의 구간 동적 후회로 분해됩니다. 특정 조건 (아선형 $E_{SLDS}$와 인증된 내부 학습자) 하에서, 그들은 아선형 실현 후회율을 확립합니다.
5. 경험적 성능: 합성 데이터와 실제 세계 벤치마크 (Melbourne, Jena, Delhi) 에 대한 광범위한 실험은 L2D-SLDS가 컨텍스트 및 비정상 밴딧 베이스라인을 능가하며, 실제 데이터 시나리오에서는 라운드의 2% 미만에서 연기함을 보여줍니다.

결과

• 합성 데이터: L2D-SLDS 는 최고의 밴딧 베이스라인 (0.427) 과 비교하여 가장 낮은 라우팅 비용 (0.336) 을 달성했습니다. 제거 실험 (Ablation studies) 은 공유 요인 $g_t$가 정보 전달에 결정적임을 확인시켰으며, 이를 제거하면 성능이 저하되었습니다.
• 실제 세계 벤치마크:
  • Melbourne: L2D-SLDS 는 0.8%의 연기율로 5.914 의 비용을 달성하여, 더 높은 연기율을 가진 모든 밴딧 베이스라인 (6.047~6.302 범위) 을 능가했습니다.
  • Jena: L2D-SLDS 는 0.22%의 연기율로 3.293 을 달성했습니다. 주목할 점은, 모든 밴딧 베이스라인이 연기하지 않는 베이스라인 (3.297) 보다 성능이 저하된 반면, L2D-SLDS 는 연기하지 않는 내부 예측기를 개선한 유일한 적응형 방법이었다는 것입니다.
  • Delhi (24 명 전문가): L2D-SLDS 는 1.70%의 연기율로 2.528 을 달성했습니다. 가장 강력한 밴딧 베이스라인 (SharedLinUCB+0) 은 2.542 를 달성했으나 34.8%의 연기율이 필요하여, L2D-SLDS 가 고가치 연기를 선택하는 데 있어 효율적임을 강조했습니다.
• 제거 실험 (Ablations): 공유 요인을 제거하거나 정보 지향 점수를 Thompson sampling 으로 대체하면 성능이 크게 저하되거나 쿼리율이 증가하여, 모델 및 점수 메커니즘의 특정 설계 선택이 타당함을 검증했습니다.

의의 및 주장
본 논문은 비대칭 피드백, 잠재 체제 전환, 그리고 역동적 전문가 레지스트리 하에서 내부 학습자를 온라인으로 공동 훈련하고 외부 전문가로 라우팅하는 첫 번째 작업이라고 주장합니다. 그 의의는 비정상 설정에서 전문가 피드백의 "검열된" 특성을 효과적으로 처리할 수 있는 잔차의 확률적 모델을 보여줌으로써, 시스템이 공유 잠재 구조를 통해 쿼리되지 않은 전문가에 대해 학습할 수 있게 한다는 점에 있습니다. 저자들은 표준 밴딧 접근법과 비교하여 극적으로 낮은 쿼리율로 경쟁력 있거나 우수한 성능을 달성하며, 연기 비용이 높은 고위험 또는 비용 민감한 응용 분야에 적합하다고 강조합니다. 이론적 후회 분해는 탐색, 예측 오차, 그리고 학습자 적응 간의 트레이드오프를 이해하기 위한 모듈식 프레임워크를 제공합니다.