신뢰도 순위가 선택적 예측 모델 비교 확정에 필요한 레이블 수를 결정한다.

무엇인가

이 논문은 학습된 분류기 K개 중 어느 것이 선택적 예측(selective prediction)에서 더 나은지를 평가 레이블을 전부 읽지 않고 결정하려면 레이블이 몇 개 필요한지를 정량화한다. 핵심 관찰은 정확도 비교와 AUGRC 비교가 근본적으로 다르다는 점이다. 정확도에서는 모든 후보가 같은 레이블을 예측하는 행(row)이 순위를 바꿀 수 없지만, AUGRC(area under the generalized risk-coverage curve)는 오류가 얼마나 이른 순위에서 수용되었는가에 가중치를 주기 때문에 같은 행이 승자를 뒤집을 수 있다. 논문은 예측값과 신뢰도 순위를 풀(pool) 전체에 대해 고정하고 레이블만 미지인 상태에서 승자를 확정하는 문제를 다루며, 이 정보량을 읽은 레이블 수로 측정한다. 저자는 레이블을 읽기 전 하한(prelabel lower bound), 획득 중 인증서 탐지, 획득 후 최소 인증서 크기 상한을 분리해서 다룬다.

어떻게 동작하나

방법의 뼈대는 세 부분이다. 첫째, 유한 풀에서 AUGRC를 선형 보간으로 정의하면 각 행의 손실이 레이블 y_i에 선형이 되므로 후보 j의 위험은 r_j(y) = c_j + Σ_i a_ji y_i (c_j = Σ_i w_ji ŷ_ji, a_ji = w_ji(1-2ŷ_ji))로 쓸 수 있다. 여기서 가중치 w_ji는 동점 블록 [s,e)에 대해 ω_i = (2n-s-e)/(2n²)로 주어진다. 이 선형성 덕분에 읽지 않은 레이블에 대한 r_j - r_k의 정확한 하한 L_jk와 상한 H_jk를 닫힌 형태로 계산할 수 있고, 정리 1은 모든 레이블 완성에 대해 후보 k가 승자일 필요충분조건이 모든 j≠k에 대해 L_jk ≥ 0 (j>k), L_jk > 0 (j<k)임을 보인다. 이 검정은 적응적 질의 순서 뒤에도 유효하다. 둘째, 정리 2는 최소 인증서 크기 C(y)를 커버링 정수계획 min Σ x_i s.t. Σ_i g_ji x_i ≥ D_j로 정식화하고, 그 LP 완화 값 z를 올림 반올림하면 z + K - 1 이하의 인증서를 얻음을 보인다. 즉 풀 크기와 무관하게 K-1개 이내의 오차로 벤치마크를 계산할 수 있다. 셋째, 정리 3은 레이블을 하나도 읽기 전에 알 수 있는 하한 C̄ = min_k max_{j≠k} m_jk를 제시한다. 여기서 m_jk는 |b_jki|를 큰 순서로 더해 결손 D_j를 채우는 최소 개수다. 또한 후보별 위험을 따로 구간으로 묶는 분리 구간 검정보다 공유 레이블을 쓰는 공동 검정이 항상 같거나 빠르게 정지하며, 그 차이는 예측이 일치하는 미읽음 행에서 min(w_ji, w_ki)의 합으로 정확히 주어진다(명제 1). 공통 항을 빼는 중점 센터링은 두 후보에 대해서는 이 격차를 회복한다.

무엇과 다른가

이론적 극한 결과가 논문의 중심 주장이다. 명제 2는 K개 후보가 동일하게 예측하고 신뢰도 순서가 서로 독립인 균등 무작위 순열일 때 레이블 이전 하한이 C̄/n → 1/4로 수렴함을 보인다. 직관은 독립 균등 순위 U, V에 대해 |U-V| > 1/2인 행이 확률 1/4이지만 E|U-V| = 1/3의 절반을 담당한다는 것이다. 또한 손실이 순위와 독립인 iid 베르누이(q)이면 두 후보일 때 실제 최소 인증서는 C(y)/n → 1/2로 수렴하고, 일반 K에 대해서도 임의의 ε>0에 대해 Pr(C(y) < (1/2-ε)n) → 0이다. 명제 3은 더 강한 결과로, 예측·순위·관측 손실·독립 난수만 사용하는 어떤 적응적 정책도 정확한 승자를 인증하려면 N_π/n → 1, 즉 거의 모든 레이블을 읽어야 함을 보인다. 두 후보일 때는 (N_π - C(y))/n → 1/2, 즉 사후 인증서와의 격차가 풀의 절반이다. 저자는 이를 인증서는 약속된 질의 비용이 아니라 벤치마크라고 정리한다. 극단적 예로 두 후보가 모두 0을 예측하고 순위만 뒤집힌 구성에서 C(0) = n-1인 반면 정확도는 레이블 0개로 동점이 된다.

어떻게 쓰나

실험은 9개 데이터셋에서 108개 feature-panel 비교로 구성된다. 가장 눈에 띄는 결과는 불일치(disagreement) 레이블이 모든 정확도 선택은 확정하지만 AUGRC 선택은 하나도 확정하지 못한다는 것이다. 20% 예산은 96개 조건에서 사전에 배제되고 최소 인증서는 평균 56-57%를 요구한다. 사전학습 이미지 분류기 10개 조건에서는 정확한 선택이 10,000개 레이블의 68-91%를 읽어야 했고, AUGRC 허용오차 5×10⁻⁴를 주면 50-67%로 줄었다. 세 개 점수에 대한 실험에서 평균 획득량은 static range 81.67%, random 98.43%였고, 쌍별 최소 인증서는 28.41-49.46%, static range는 50.75-88.84%를 읽었다. 모든 정확 실행에서 전체 풀 승자가 복원되었고 176개 획득 경로와 1,666,594개 프리픽스가 독립 검증되었다. 추론은 네 CPU 스레드에서 모델당 5.9-9.5초, 세 후보 LP 실행은 각 21-32ms였다. 아키텍처 패밀리 후속 실험으로 MobileNetV2 x1.0, ShuffleNetV2 x1.0, RepVGG A0를 두 데이터셋에 추가한 6개 조건에서 평균 static 획득은 정확 선택 80.91%, τ=.0005에서 63.54%였고, 원래 4개 조건의 81.67%, 55.28%와 비교된다.

전제와 한계

추가 분석은 정지 규칙과 획득 순서를 분리한다. 정지 규칙만 바꿔 비교하면 원래 36개 조건에서 공유 검정이 분리 구간보다 17.66포인트, 중점 센터링보다 10.58포인트를 절약했다. 추가 72개 조건에서 세 규칙은 각각 99.43%, 90.15%, 85.21%를 읽었고, 공유 검정은 중점 센터링보다 4.95포인트(중앙값 2.46, 56/72 조건에서 더 이른 정지)를 절약했다. 획득 순서를 바꾸는 비교에서는 random, static/adaptive range, static/adaptive pair-sum, uniform-label VMA, Model Selector(노이즈 .46) 등 7개 정책을 같은 인증서 검정에 연결했다. adaptive pair-sum은 80.45%를 읽어 static range의 85.21%보다 평균 4.76포인트 적었지만 최소 인증서보다는 여전히 25.07-25.84포인트 높았다. Friedman 순열 검정은 정책 순위가 같다는 가설을 기각했고(p_MC = 10⁻⁵), Nemenyi 비교는 adaptive pair-sum을 random, VMA, Model Selector와 분리했지만 다른 휴리스틱과는 분리하지 못했다. 허용오차 τ ∈ {0, .0005, .001, .002, .005, .01} 격자에서 τ=.005일 때 최소 인증서는 평균 44.83-45.69%, 적응적 획득은 69.74%로 10.64포인트 절약되지만 최소치보다 24.05-24.91포인트 높았고, 반환 후보는 28/108 조건에서 바뀌었지만 모두 허용오차 안이었다. 후보 집합 민감도 실험에서 K=2,4,8에 대해 최소 인증서는 38.42%, 53.78-54.41%, 58.95-59.90%, 적응적 획득은 65.57%, 79.52%, 81.24%였다. 풀 크기를 맞춘 3,600개 합성 풀에서는 평균 인증서 상한이 60.15-61.15%로 실제 패널의 56.37-57.16%보다 높았고, 상호정보량 기반 두 번째 패널 생성기에서는 사전 하한 20.42%, 최소 인증서 45.81-46.27%, 적응적 획득 70.72%였다. 시뮬레이션에서 두 후보의 평균 인증서 비율은 n=50에서 .37, n=5706에서 .46이었고, 상관 순서(copula ρ=.99)에서도 추정 하한은 .204로 0이 되지 않았다. 실제 순위 쌍의 평균 Spearman은 .51이었다.

개발자 관점에서 이 논문이 주는 실무적 메시지는 명확하다. 첫째, 예측이 같으면 레이블이 필요 없다는 정확도 기준의 직관은 선택적 예측에 그대로 적용되지 않는다. 신뢰도 순위가 다르면 동일 예측 행에서도 승자가 갈리므로 AUGRC 기반 모델 선택에는 불일치 행뿐 아니라 일치 행의 레이블도 필요하다. 둘째, 레이블을 읽기 전에 C̄를 계산해 예산이 원천적으로 부족한지 판정할 수 있고, 레이블을 읽는 중에는 정리 1의 정지 검정으로 언제 멈춰도 되는지 알 수 있으며, 끝난 뒤에는 커버링 LP로 몇 개면 충분했는지를 사후 감사할 수 있다. 셋째, 인증서 크기와 실제 획득 비용은 다른 양이다. 독립 순서 모형에서는 최적 정책조차 거의 모든 레이블을 읽으므로 인증서 크기를 질의 비용의 기대로 오해하면 안 된다. 넷째, 허용오차 τ를 도입하면 비용이 크게 줄어든다. τ=.005에서 평균 인증서가 10포인트 이상 줄었고, 이미지 분류기 실험에서는 5×10⁻⁴ 허용오차가 68-91%를 50-67%로 낮췄다. 실무에서는 정확한 승자 대신 허용오차 내 승자를 받아들이는 예산-허용오차 곡선을 먼저 그려보는 것이 합리적이다.

저자가 명시한 한계도 분명하다. 보장은 풀, 후보, 순위가 고정되어 있고 레이블이 이진이거나 여러 후보가 같은 다중 클래스 예측을 공유하는 경우에만 성립하며 재학습이나 전이(transfer)는 다루지 않는다. 실험의 후보 수는 K ≤ 8이다. 점근 결과는 독립 균등 순서를 가정하고, 인증서·획득 극한은 순위와 독립인 iid 오류를 추가로 가정한다. 따라서 실제로 학습된 데이터에 대한 일반적인 획득 상한은 따라오지 않는다. 또한 K > 2일 때의 인증서 극한은 열린 문제로 남겨져 있고, 상관 순서 분석은 유한 격자일 뿐 전체 상관족에 대한 경계가 아니며 ρ=1에서는 두 순서가 같아져 요구량이 0이 된다. 허용오차와 후보 집합 분석은 획득 비용을 알고 난 뒤에 프로토콜을 고정한 회고적 분석이라는 점도 밝히고 있다.