훈련 오차 0%인 모델의 진짜 실력 — 굿-터링으로 데이터가 고른 영역의 확률을 재다

훈련 데이터 1,000개를 전부 외운 분류기를 떠올려 보자. 훈련 세트에서 이 분류기의 오차는 정확히 0이다. 그런데 새 데이터에서의 오차, 즉 테스트 오차는 몇 퍼센트일까. 질문에는 함정이 있다. 오차를 재는 데 쓸 수 있는 데이터가 방금 그 분류기를 만든 바로 그 1,000개뿐이라면, 우리는 '0'이라는 숫자와 '알 수 없음' 사이에 서 있게 된다. 비탈리 펠드만, 사티엔 케일, 비노드 라만, 쿠날 탈와르, 암부지 테와리 다섯 명의 논문 「A Unified Framework for Probability Estimation of Data-Dependent Events」는 바로 이 자리에서 출발한다.

논문이 던지는 형식은 간결하다. 미지의 분포 D에서 i.i.d.로 뽑은 표본 S가 있고, 알려진 사상 G가 표본마다 하나의 사건을 지정한다. 목표는 D(G(S)), 즉 그 사건에 분포가 부여하는 확률을 추정하는 것이다. 추정기는 G와 S는 알지만 D에서 새 표본을 더 뽑을 권한은 없다. 같은 표본이 사건을 정하고, 그 사건의 확률을 재는 데도 쓰인다. 이 한 문장이 논문 전체의 긴장을 만든다.

하나의 틀 안에 들어오는 서로 다른 문제들

이 틀이 흥미로운 이유는 서로 다른 분야의 문제들이 같은 모양으로 접힌다는 점이다. 표본이 정한 '아직 보지 못한 결과들의 집합'의 확률을 재는 것이 고전적 미싱 매스(missing mass) 문제이고, 데이터로 학습한 예측기의 테스트 오차도 오차 영역이라는 사건의 확률이다. 적응적 데이터 분석과 선택 후 추론(post-selection inference)의 목표량, 순응 예측(conformal prediction) 집합이 실제로 빗나간 비율도 같은 자리에 놓인다. 논문은 이들을 각각 다른 도구로 다루던 관행을 하나의 정의로 모은다.

저자들이 정의하는 '추정 가능성(estimatability)'은 최악의 경우 평균제곱오차로 측정된다. 모든 분포에 대해 오차가 작아지는 추정기가 존재할 때 그 사상 G를 추정 가능하다고 부른다. 중요한 것은 이 정의가 알고리즘의 성질이 아니라 사건을 만드는 규칙의 성질이라는 점이다. 같은 학습 알고리즘이라도 어떤 라벨링에서는 오차를 잘 재고, 어떤 라벨링에서는 전혀 못 잴 수 있다.

고전적 두 추정기: 경험적 추정과 굿-터링

첫 번째 길은 경험적 플러그인 추정기다. 표본에서 사건에 들어간 점의 비율을 그대로 확률로 삼는다. 논문의 관찰은 이 추정기의 오차가 정확히 일반화 갭(generalization gap)이라는 것이다. 따라서 VC 차원, 알고리즘 안정성, 차분 프라이버시, 상호정보량 등으로 얻은 일반화 경계가 그대로 이 추정기의 오차 경계가 된다. 검증된 도구를 재사용할 수 있다는 뜻이라 실용적으로 반갑다.

두 번째 길은 하나를 빼고 세는 추정기(leave-one-out)다. 표본에서 점 하나를 뺀 나머지로 사건을 다시 정하고, 뺀 점이 그 사건에 들어가는지를 센다. 미싱 매스에 이 추정기를 적용하면 고전적인 굿-터링(Good–Turing) 추정기가 그대로 복원된다. 굿-터링은 한 번만 관측된 종(singleton)의 비율로 아직 보지 못한 종의 확률을 추정하는 방법이다. 1953년 I. J. 굿이 제안한 이 추정기는, 배경을 덧붙이자면 굿이 블레츨리 파크에서 앨런 튜링과 함께 암호 해독의 통계 문제를 다루던 시기에 나왔다.

논문은 이 추정기가 점 하나를 삭제해도 사건이 거의 변하지 않는 '안정성'을 가질 때 정확해진다는 것을 보인다. 그 결과는 고전적 미싱 매스에 그치지 않는다. 표본점들의 근방(neighborhood) 전체의 합집합은 표본보다 훨씬 큰 집합인데도 O(1/n) 오차로 추정되고, 정확히 k번 등장한 점들의 근방 합집합은 O((k + log n)/n)의 속도를 얻는다. 사건이 표본보다 훨씬 커도 된다는 점이 이 절의 실질적 성과다.

말뭉치에서 단어의 순위와 빈도를 로그 축에 그린 그림. 왼쪽 끝의 몇 개 단어가 빈도의 대부분을 차지하고, 오른쪽 끝에는 한 번만 나온 단어가 길게 늘어선다. 굿-터링 추정기는 바로 이 '한 번만 나온 것'의 개수를 재료로 아직 보지 못한 것의 확률을 추정한다 — 저작자 JustinDiamond, CC BY-SA 4.0 (Wikimedia Commons)

반전: 예외를 외운 분류기에서는 둘 다 무너진다

논문의 주 응용은 기본 분류기에 예외를 외워 넣는 구조다. 기본 학습기 A가 만든 분류기 h_S의 오차 영역을 E(S)라 하면, 예외 기억 분류기의 오차 영역은 G(S) = E(S) \ T(S)가 된다. 표본점 T(S)에서는 외운 정답을 내놓으므로 그 점들은 오차 영역에서 빠진다. 이 구조는 압축 알고리즘 이론에서 고전적이고, 실제 시스템에서도 국소 패치·잔차 메모리·편집 모듈의 형태로 흔하다.

여기서 두 고전 추정기가 모두 실패한다. 경험적 추정기는 오차 영역에 표본점이 하나도 없으므로 항상 정확히 0을 보고한다. 하나를 빼고 세는 추정기는 기본 학습기를 n번 다시 학습시켜야 하고, 학습기가 불안정하면 — 예컨대 목적함수가 볼록하지 않으면 — 아무 보장도 없다. 계산 비용과 이론 보장이 동시에 사라지는 셈이다.

그런데 재려는 양은 깔끔한 서술을 갖는다. 참 오차는 기본 분류기의 오차 영역에 제한된 미싱 매스, 즉 새 점이 '아직 보지 못했으면서 그 영역에 떨어질' 확률이다. 논문은 이것을 적응적 미싱 매스 추정(adaptive missing mass estimation)이라는 일반 문제로 정식화하고, 영역의 질량은 경험적으로, 영역 중 표본에 이미 보인 부분의 질량은 영역을 고정한 채 하나를 빼고 세는 방식으로 추정한다. 두 추정의 차이는 결국 '선택된 영역 안에 있으면서 표본에 정확히 한 번 등장한 점의 비율'이 된다. 이것이 선택 영역에 제한된 굿-터링 추정기다. 기본 학습기는 한 번만 돌리면 된다.

두 번째 반전: 일반화가 좋아도 추정은 틀린다

여기서 자연스러운 희망이 생긴다. 영역의 경험적 질량이 참 질량을 잘 맞힌다면, 그 영역의 미싱 매스도 잘 맞히지 않을까. 논문의 명제 6.2는 그 희망을 정면으로 부정한다. 경험적 질량의 평균제곱오차가 O(1/n)인데도, 결합 추정기의 오차가 모든 n에서 상수 c 이상인 학습기가 존재한다.

반례의 구조가 영리하다. 오차 영역을 '표본에 정확히 한 번 등장한 점들의 집합'으로 잡되, 표본이 일관성 검사를 통과할 때만 그렇게 하고 아니면 공집합으로 둔다. 검사는 한 번 등장한 점들의 비율과 그 질량의 굿-터링 추정치를 비교한다. 통과하면 훈련 오차가 모집단 오차의 정확한 추정이 된다. 그런데 그 영역에는 보지 못한 점이 하나도 없으므로 예외 기억 분류기는 완벽하고, 결합 추정기는 영역 안의 모든 singleton을 세어 약 1/e의 오차를 보고한다. 두 재료를 따로 분석하는 방식은 원리적으로 불가능하다는 것이 이 명제의 결론이다.

구원의 두 조건: 상호정보량과 VC 차원

논문은 두 가지 자연스러운 조건에서 결합 추정기가 다시 작동한다는 것을 보인다. 첫째, 선택된 영역이 표본과 나누는 상호정보량 I가 작으면 평균제곱오차는 O((I + 1)/n)이다. 증명은 영역을 고정했을 때 제한된 굿-터링 추정기가 1/√n 규모로 준가우시안 집중을 한다는 사실에서 출발해, 단스커-바라단 부등식으로 영역과 표본을 분리하고 그 대가로 O(I/n) 항을 지불한다.

둘째, 선택 규칙이 낼 수 있는 영역들의 클래스가 VC 차원 d를 가지면 오차는 O(d log(n/d)/n)이다. 이 경우 영역이 그 클래스에서 어떻게 골라졌는지는 전혀 제한하지 않는다. 증명은 영역 클래스의 유한한 덮개(cover)를 만들어 선택된 영역을 가까운 원소로 바꿔치기하고, 대칭차에 대한 균일 수렴과 합집합 경계로 대체 비용을 통제한다.

따라서 기본 학습기가 VC 차원 d인 이진 분류기를 내놓는다면, 예외 기억 학습기의 오차는 모든 분포와 모든 라벨링에 대해 — 라벨이 그 클래스에 속하지 않아도 — O(d log(n/d)/n)의 평균제곱오차로 추정된다. 경험적 추정기가 항상 0을 보고하는 상황에서 얻은 결과라는 점이 이 정리의 무게다.

블레츨리 파크에 세워진 앨런 튜링 조각상. 굿-터링 추정은 굿이 이곳에서 튜링과 함께 암호 해독의 통계 문제를 다루던 시기에서 비롯했다. 논문의 대상은 1953년의 종 개수 문제가 아니라, 표본이 스스로 고른 영역의 확률이다 — 사진 David Dixon, CC BY-SA 2.0 (Wikimedia Commons)

추정 불가능한 사건들, 그리고 1/64

논문은 추정이 원리적으로 불가능한 사건도 세 가지 만든다. 첫 번째는 새롭고 아주 단순한 예다. 2n+1개의 이진 좌표가 있고, 사건은 '경험적 평균이 가장 큰 좌표에서 값이 1인 점들의 집합'이다. 재려는 값은 그 선택된 좌표의 참 평균이다. 한 좌표는 항상 1이고 나머지는 독립 균등인 분포를 생각하면, 상수 확률로 표본 위에서 다른 좌표 하나도 모두 1이 된다. 특수 좌표가 무작위로 뽑혔다면 표본을 본 뒤에는 두 좌표가 똑같이 그럴듯하고, 참 평균은 1이거나 1/2이다. 어떤 추정기도 평균제곱오차 1/64 아래로 내려가지 못한다.

세 번째 구성은 정의역 크기가 2n²에 불과한데도 오차 하한 1/576을 준다. 더 아픈 것은 그 사건들의 상상 클래스(image class)의 VC 차원이 n+1 이하라는 점이다. 즉 상상 클래스의 VC 차원이 유한하다는 것만으로는 추정 가능성을 보장하지 못한다. 반면 경험적 추정기는 VC 차원이 o(n)이면 일관적이므로, 두 조건 사이에는 메워지지 않은 간격이 있다.

논문이 스스로 인정한 한계

저자들이 8절에서 밝히는 가장 근본적인 열린 문제는 어떤 사상 G가 추정 가능한지에 대한 완전한 특징화가 없다는 것이다. 이 논문은 충분조건 몇 개와 불가능성 결과 몇 개를 주지만, 추정 가능성을 포착하는 단일한 구조적 개념이 존재하는지, 아니면 근본적으로 다른 메커니즘들이 불가피한지는 미해결로 남는다. 사건의 정의역 크기에 대해서도 선형 하한과 2차 구성 사이의 간격이 열려 있다.

또 하나의 한계는 실제 시스템과의 거리다. 논문의 예외 기억 분류기는 표본점 자체에서만 기본 분류기를 덮어쓴다. 실제로는 예외 하나를 외우면 그 근방까지 교정하는 경우가 많고, 저자들도 근방 교정 학습기를 명시적으로 논의한다. 그러나 그 경우 결합 추정기의 적응적 단계를 지탱하는 두 재료 — 고정 영역에서의 지수적 집중과 singleton 개수의 유계차분 논증 — 가 근방에서는 그대로 쓸 수 없다고 인정한다. 실무적 함의는 분명하지만, 그 함의가 성립하는 조건은 아직 좁다.

마지막 질문

이 논문이 남기는 질문은 기술적이면서 일상적이다. 우리는 매일 표본으로 만든 모델의 성능을 그 표본으로 평가한다. 교차검증과 홀드아웃은 그 부담을 덜어 주지만, 표본이 사건 자체를 고르는 순간 — 선택 후 추론, 필터가 거른 하위 집단, 예외를 외운 모델 — 보장은 조용히 사라진다. 당신이 마지막으로 신뢰한 성능 지표는, 그 지표를 계산한 데이터와 얼마나 독립적이었는가.

참고 자료

Vitaly Feldman, Satyen Kale, Vinod Raman, Kunal Talwar, Ambuj Tewari, 「A Unified Framework for Probability Estimation of Data-Dependent Events」, arXiv:2610.41244v1 [cs.LG], 2026-10-30, 39 pages. https://arxiv.org/abs/2610.41244v1

본문의 정리·명제 번호와 수치(명제 6.2, 정리 6.3, 따름정리 6.4, 정리 7.1, 정리 7.3의 1/576)는 모두 위 논문의 서술을 따랐으며, 굿-터링의 역사적 배경은 논문의 주장이 아니라 배경 설명으로 덧붙였다.