Online Learning-to-Defer with Varying Experts

문제 정의
학습-지연 (Learning-to-Defer, L2D) 은 예측 모델과 외부 전문가 (인간 또는 자동화 시스템) 를 통합하여 불확실성이 높거나 중대한 입력을 더 유능한 에이전트로 라우팅함으로써 시스템 신뢰성을 향상시키도록 설계된 프레임워크입니다. 기존 L2D 연구는 주로 고정된 전문가 풀과 완전한 감독 (훈련 중 모든 전문가 예측 관찰) 을 가진 배치 환경에서 수행되지만, 실제 배포에서는 데이터가 순차적으로 도착하고, 전문가 가용성이 변동하며 (예: 교대 근무 또는 자원 제약으로 인해), 전문가의 신뢰성이 시간이 지남에 따라 변할 수 있다는 심각한 도전에 직면합니다. 또한, 실제 시스템은 종종 밴디트 피드백 하에서 운영되는데, 이는 학습자가 모든 사용 가능한 전문가의 성능이나 정답이 아닌 선택된 행동 (예측 또는 특정 전문가 쿼리) 의 결과만 관찰하는 것을 의미합니다. 본 논문은 이러한 동적이고 온라인적인 현실과 고전적인 L2D 가정 사이의 격차를 해소하기 위해, 밴디트 피드백과 동적으로 변화하는 전문가 풀을 가진 다중 클래스 분류를 위한 최초의 온라인 L2D 프레임워크를 제시합니다.

방법론
저자들은 각 라운드 $t$에서 특징 벡터 $x_t$와 사용 가능한 전문가 집합 $A_t$로 구성된 확장된 입력 $(x_t, A_t)$가 공개되는 일반적 프레임워크를 제안합니다. 학습자는 클래스 레이블을 예측하거나 $A_t$ 내의 사용 가능한 전문가 중 한 명에게 지연 (defer) 할지 결정해야 합니다. 상호작용은 준-적대적 (semi-adversarial) 설정을 따릅니다: 입력은 적대적으로 선택될 수 있지만, 레이블은 입력에 조건부인 고정된 (그러나 알려지지 않은) 분포에서 추출됩니다.

핵심 방법론적 기여는 다음과 같습니다:

1. 진짜 지연 손실과 대리 손실: 저자들은 오분류 비용과 전문가 쿼리 비용을 고려한 진짜 지연 손실 $\ell_{def}$를 정의합니다. 이 손실은 미분 불가능하므로, 저자들은 온라인 및 변동 전문가 설정으로 확장된 표준 점수 기반 대리 손실 (제약 힌지 손실 등) 인 볼록한 대리 손실 $\Phi_{def}$를 도입합니다. 이 대리 손실은 사용 불가능한 전문가들의 점수에 영향을 받지 않도록 설계되었습니다.
2. 온라인 학습을 위한 H-일관성 상한: 중요한 이론적 진전은 배치 학습에서 온라인 설정으로 $H$-일관성 상한을 확장하는 것입니다. 저자들은 기본 대리 손실이 제로-원 손실에 대해 $H$-일관성 상한을 허용할 경우, 온라인 프레임워크에서 대리 지연 후회를 최소화하는 것이 진짜 지연 후회를 유계로 보장함을 증명합니다.
3. 알고리즘 설계: 제안된 알고리즘 (알고리즘 1) 은 투영된 경사를 사용하는 온라인 경사 하강법 (OGD) 을 활용합니다. 제약 힌지 손실에 필요한 사용 가능한 레이블 점수의 합이 0 이어야 한다는 제약을 처리하기 위해, 알고리즘은 가중치 행렬을 현재 사용 가능한 전문가 집합에 특정한 실현 가능 부분 공간 $K_{A_t}$로 투영합니다. 이 투영은 사용 가능한 레이블 집합에 대한 가설의 예측을 보존합니다. 알고리즘은 밴디트 피드백을 처리하기 위해 탐험률 $\gamma_t$를 포함하며, 샘플링된 행동의 관찰된 결과를 기반으로 손실 함수를 추정합니다.

주요 기여
본 논문은 네 가지 주요 기여를 주장합니다:

1. 최초의 온라인 L2D 프레임워크: 데이터 분포와 전문가 풀 모두 시간에 따라 변할 수 있는 밴디트 피드백 하의 온라인 학습 - 지연을 위한 최초의 프레임워크를 도입합니다.
2. 이론적 확장: 이전에 배치 학습 분석에 국한되었던 속성인 $H$-일관성 상한의 개념을 온라인 설정으로 확장합니다.
3. 후회 보장: 제안된 알고리즘은 일반적 경우에 $O((n + n_e)T^{2/3})$의 후회 상한을 달성하며, 여기서 $n$은 클래스 수이고 $n_e$는 관찰된 고유 전문가 수입니다. 저노이즈 (거의 실현 가능) 가정 하에서는 이것이 $O((n + n_e)\sqrt{T})$로 개선됩니다.
4. 실증적 검증: 이 접근법은 Reuters4 와 CIFAR10H 와 같은 합성 및 실제 데이터셋에서 검증되어, 변화하는 전문가 가용성과 변동하는 전문성에 적응할 수 있음을 입증했습니다.

결과
실험은 세 가지 복잡도가 증가하는 regime 에서 수행되었습니다: (1) 고정된 가용성과 전문성, (2) 고정된 전문성을 가진 변동하는 가용성, (3) 변동하는 가용성과 변동하는 전문성을 모두 가진 완전히 동적 설정.

• 합성 데이터: 알고리즘은 예측과 지연 사이의 최적 경계를 성공적으로 학습하여, 입력을 가장 유능한 사용 가능한 전문가에게 일관되게 라우팅했습니다. 전문가의 유능 영역이 시간에 따라 이동할 때에도 낮은 지연 손실과 높은 정확도를 유지했습니다.
• 실제 데이터 (Reuters4): 가장 도전적인 설정 (변동하는 가용성과 전문성) 에서 이 방법은 이동하는 전문가 유능 영역을 효과적으로 추적했습니다. 현재 유능한 전문가에게 높은 빈도로 지연하여 안정적인 보정성을 유지하고 고정 전문성 기준선과 비교 가능한 작업 정확도를 달성했습니다.
• CIFAR10H: WideResNet 예측기와 인간 주석 전문가를 사용하여, 이 방법은 무작위로 균일하게 지연하는 신뢰도 기반 기준선보다 우수한 성능을 보였습니다. 학습된 정책은 더 낮은 지연 손실과 더 높은 정확도를 달성하여, 무분별하게 지연하는 대신 예제를 가장 적합한 전문가에게 라우팅하는 법을 학습했음을 나타냅니다.

의의
본 논문은 학습 - 지연 시스템을 실제 비정상 환경에서 실행 가능하게 만드는 기초적인 단계로 자리매김합니다. 고정된 전문가 풀과 완전한 감독이라는 가정을 넘어선 저자들은 일관된 대리 기반 방법이 적대적 환경과 변동하는 전문가 신뢰성에 대해 견고하게 만들 수 있음을 입증합니다. 온라인 설정에서의 $H$-일관성 확립은 대리 손실 최소화가 진짜 지연 후회 최소화로 이어진다는 엄격한 보장을 제공하여, 이론적 L2D 보장과 스트리밍 데이터 및 동적 전문가 시스템의 실제 요구 사항 사이의 중요한 격차를 해소합니다.