🤖 machine learning

A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

본 논문은 훈련이나 확률적 가정을 필요로 하지 않고 선형 회귀 모델의 최적 조기 종료 시점을 추정하기 위해 L1-노름 기반의 라데마허 복잡도(Rademacher complexity)에 기초한 분석적 프레임워크를 제안하며, 선형 프로빙(linear probing)을 통해 비선형 신경망에 대한 적용 가능성을 입증한다.

원저자: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

게시일 2026-08-26

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터가 사진 속의 고양이를 식별하거나 주가를 예측하는 것과 같이 패턴을 인식하도록 훈련하는 것은 섬세한 균형 잡기 과정입니다. 기계는 예시들을 살펴보고, 자신이 본 데이터에 맞게 내부 설정을 조정하며 학습합니다. 하지만 너무 완벽하게 학습하면, 근본적인 규칙을 이해하기보다는 해당 예시들의 구체적인 특징들을 암기하기 시작합니다. 이는 연습 문제의 정답은 외웠지만, 새로운 질문에 논리를 적용하지 못해 실제 시험에서 실패하는 학생과 비슷합니다. 인공지능의 세계에서 이러한 일반화 실패는 큰 장애물입니다. 이를 방지하기 위해 연구자들은 흔히 '조기 종료(early stopping)'라고 불리는 전략을 사용하는데, 이는 모델이 규칙을 학습한 직후, 즉 노이즈를 암기하기 시작하기 전의 적절한 순간에 학습 과정을 멈추는 방식입니다. 문제는 언제 정확히 그 순간이 오는지를 아는 것이었습니다. 전통적으로 이 최적의 지점을 찾는 것은 별도의 데이터 세트로 훈련 과정을 여러 번 반복 실행해야 했으며, 이 방법은 느리고 계산 비용이 많이 들며 종종 추측에 의존해야 했습니다.

파리-삭레 대학교(Université Paris-Saclay)의 연구팀은 반복적인 실험 없이도 이 타이밍 문제를 해결할 수 있는 새로운 방법을 제안했습니다. 그들은 추측을 하거나 추가 시뮬레이션을 실행하는 대신, 데이터 자체로부터 이상적인 중단 시점을 직접 예측할 수 있는 수학적 방법을 개발했습니다. 그들의 접근 방식은 라데마허 복잡도(Rademacher complexity)라는 개념에 기반하며, 이는 본질적으로 모델이 실제 패턴과 무작위 노이즈를 얼마나 잘 구별할 수 있는지를 측정합니다. 연구진은 이 척도를 사용하여 컴퓨터가 언제 학습을 멈춰야 하는지 정확히 알려주는 규칙을 만들었습니다. 이들의 연구가 차별화되는 점은 데이터의 형태나 분포에 대한 가정을 필요로 하지 않는다는 것인데, 이는 기존 방법들의 공통된 요구 사항이었습니다. 또한, 그들은 L1-노름(L1-norm)이라 불리는 특정한 오차 측정 방식을 사용하는 것이 기존의 표준 방식들보다 훨씬 더 정확한 예측을 제공한다는 것을 발견했습니다.

연구진은 초기 작업으로 가장 단순한 유형의 머신러닝 알고리즘인 선형 모델에 집중했지만, 이들의 발견이 복잡한 비선형 신경망으로도 확장될 수 있음을 입증했습니다. 이론을 테스트하기 위해 그들은 고전적인 문제인 필기 숫자 구분 작업에 이 방법을 적용했습니다. 한 실험에서, 연구진은 만 개 이상의 이미지 데이터셋을 사용하여 숫자 3과 5를 구별하도록 신경망을 훈련시켰습니다. 그들의 새로운 규칙을 사용했을 때, 시스템은 342단계의 중단 시간을 계산했습니다. 이를 전체 훈련 과정을 실행하고 별도의 테스트 세트를 확인하여 찾은 실제 최적의 중단 시간과 비교했을 때, 실제 최적값은 357단계였습니다. 그 차이는 미미했으며, 예측된 시간에 멈춘 모델의 성능은 실제 최적점에 멈춘 모델의 성능과 거의 동일했습니다. 숫자 0과 1을 다룬 또 다른 테스트에서는 예측된 중단 시간이 415단계였던 반면, 실제 최적값은 418단계였습니다. 두 경우 모두, 그들의 규칙을 사용하여 훈련된 모델은 과적합(overfitting)의 함정을 피하고 보지 못한 데이터에 대해 최상의 정확도를 달 achievement 했습니다.

또한 이 연구는 모델의 복잡도에 비해 데이터의 양이 많을 때 이 방법이 가장 잘 작동한다는 것을 보여주었습니다. 연구진이 데이터 포인트가 적은 시나리오를 테스트했을 때, 방법의 정밀도가 떨어졌으며 때로는 학습을 전혀 하지 말아야 한다는 의미인 중단 시간을 0으로 제안하기도 했습니다. 이는 복잡한 모델이 일반적인 규칙을 배우기 위해서는 충분한 데이터가 필요하다는 이해와 일치합니다. 연구진은 또한 데이터에 대한 서로 다른 수학적 가정을 사용하는 기존 기술들과 이 새로운 방법을 비교했습니다. 그들은 계산에 L1-노름을 사용하는 자신들의 접근 방식이 기존 방법들보다 훨씬 더 실제 최적값에 가까운 중단 시간을 일관되게 생성한다는 것을 발견했습니다. 이는 오차를 측정하는 방식이 중단 규칙 자체만큼이나 중요하다는 것을 시사합니다.

아마도 가장 중요한 점은, 연구진이 조기 종료가 단순히 이론적인 개념이 아니라 많은 경우에 실질적인 필수 사항임을 보여주었다는 것입니다. 그들은 훈련이 무기한 계속될 경우 어떤 일이 발생하는지 계산했습니다. 그들이 연구한 사례들에서, 훈련이 최적점을 지나 계속 진행되면 새로운 데이터에 대한 모델의 성능은 실제로 악화되었으며, 이는 조기 종료가 모델의 저하를 방지한다는 것을 확인시켜 주었습니다. 그러나 그들은 또한 모델의 파라미터가 데이터보다 훨씬 많은 특정 고복잡성 시나리오에서는 훈련을 계속하는 것이 결국 더 나은 결과를 가져올 수도 있다는 '양호한 과적합(benign overfitting)' 현상에 대해서도 언급했습니다. 그들의 방법은 사용자가 어떤 상황에 처해 있는지를 식별하여, 조기에 멈출지 아니면 계속 진행할지를 결정할 수 있게 해줍니다.

전체 훈련 과정을 실행할 필요 없이 최적의 중단 시간을 계산할 수 있는 방법을 제공함으로써, 이 연구는 더욱 신뢰할 수 있는 인공지능을 개발하는 데 있어 더 효율적인 경로를 제시합니다. 이는 시행착오의 필요성을 제거하여 시간과 계산 자원을 절약해 줍니다. 이 방법은 데이터는 풍부하지만 컴퓨팅 파워가 제한적이거나 훈련 비용이 높은 상황에서 특히 유용합니다. 현재 연구는 선형 모델과 특정 유형의 데이터에 초점을 맞추고 있지만, 연구진은 이 프레임워크가 더 복잡한 시스템과 다양한 유형의 출력값에 맞춰 조정될 수 있다고 믿습니다. 그들의 연구는 오랫동안 추측에 의존해 왔던 질문에 대해 명확하고 데이터에 기반한 답을 제공하며, 학습과 암기 사이의 절충안을 탐색하는 데 있어 더 정밀한 도구를 제공합니다.

기술 요약: L1-노름을 이용한 라데마허 복잡도 기반의 데이터 의존적 조기 종료 규칙

문제 정의
신경망을 학습시키는 것은 훈련 데이터에 적합시키는 것(fitting)과 보지 못한 입력에 대해 강건한 성능을 달내는 것(generalizability) 사이의 균형을 맞추는 과정이다. 이는 편향-분산 트레이드오프(bias-variance trade-off)로 알려져 있다. 이 두 성질 사이의 간극은 경험적 위험( $L_S$ )과 기대 모집단 위험( $L_D$ )의 차이인 일반화 손실( $L_G$ )로 정의된다. 경사 하강법(GD) 과정에서 $L_S$ 는 일반적으로 감소하는 반면 $L_G$ 는 증가하며, 이로 인해 최적의 시점 $t^*$ 에서 학습을 중단하여 $L_S + L_G$ 를 최소화하는 것이 조기 종료(early stopping)의 목표이다.

고전적으로 $t^*$ 는 별도의 테스트 세트( $S_{test}$ )를 모니터링하여 수치적으로 추정한다. 대안적으로 무작위 행렬 이론(Random Matrix Theory, RMT)을 사용하는 분석적 접근 방식이 존재하지만, 이는 가우시안 데이터 분포나 데이터 공분산 행렬의 특정 고유값 분포(예: Marchenko–Pastur)와 같은 강력한 확률적 가정을 필요로 하는 경우가 많다. 본 논문은 별도의 테스트 세트나 제한적인 분포 가정이 필요 없는 분석적 조기 종료 규칙의 필요성을 다룬다.

방법론
저자들은 경사 하강을 수행하지 않고도 최적의 정지 시간을 추정하기 위해 **라데마커 복잡도(Rademacher Complexity, RC)**에 기반한 분석적 프레임워크를 제안한다. 이 방법론은 선형 모델과 선형 회귀에 초점을 맞추며, "선형 프로빙(linear probing)"을 통해 비선형 네트워크로 확장된다.

L1-노름 정식화: 기존의 많은 RC 경계가 L2-노름을 사용하는 것과 달리, 본 연구는 라데마커 복잡도를 L1-노름으로 표현한다. 이러한 선택은 일반적인 $L_p$ -노름 경계에서 데이터 의존적 상수 $M$ (손실의 상한)을 제거하기 위함이다. 일반 $L_p$ -노름 경계에서 $p=1$ 로 설정함으로써, 저자들은 명시적인 $M$ 에 대한 의존성을 피하고 오직 경험적 오차 벡터와 모델 노름에만 의존하는 모집단 손실( $L_D$ )의 상한을 도출하였다.
경사 흐름 역학(Gradient Flow Dynamics): 문제는 연속 시간에서의 경사 흐름(Gradient Flow, GF)을 사용하여 모델링된다. 저자들은 훈련 오차 벡터 $v(t)$ 와 모델 파라미터 $a(t)$ 의 역학을 분석한다. 모집단 손실의 상한인 $L^*_D(t)$ 는 경험적 손실이 감소함에 따라 초기에 감소하다가 모델 노름이 커짐에 따라 나중에 증가하는 "U자형"을 띠는 것으로 나타난다.
분석적 정지 기준 ( $t^+$ ): 핵심 기여는 $L^*_D(t)$ $L_{D}^{*} (t)$ 가 모든 $t \leq s$ $t \leq s$ 에 대해 감소하도록 보장하는 데이터 의존적 기준 $C(s)$ $C (s)$ 를 도출하는 것이다.
- 저자들은 데이터 공분산 행렬의 고유값을 "정보가 있는(informative)" 집합(큰 고유값)과 "방해 요소(nuisance)" 집합(작은 고유값)으로 분해한다.
- 이들은 이러한 고유값들과 오차 역학을 포함하는 함수 $\Phi(t)$ 를 정의한다.
- 정지 시간 $t^+$ 는 모든 $t \in [0, s)$ 에 대해 $\Phi(t) > 0$ 을 만족하는 시간 $s$ 의 상한(supremum)으로 정의된다.
- 수학적으로 $t^+$ 는 $\Phi(t)$ 가 처음으로 0을 통과하는 시점이다. $t^+$ 가 실제 최적 시간 $t^*$ 의 하한 추정치( $t^+ \leq t^*$ )임이 증명되었다. 특정 조건(예: 실제 최솟값이 첫 번째 부호 불변 구간 내에 있는 경우) 하에서는 $t^+ = t^*$ 가 성립한다.
근사화: 논문은 $t^+_{approx} \approx \frac{1}{\lambda_1} \ln \frac{\Gamma(0)}{\Omega(0)}$ 와 같은 간단한 근사식을 제공하며, 이는 RMT 문헌에서 발견되는 신호 대 잡음비(SNR) 정식화와 유사하지만, 확률적 가정 없이 유도되었다.

주요 기여

분포 불가지론적 분석적 추정: 본 논문은 데이터 분포에 대한 가우시안 가정이나 특정 고유값 분포 없이도 최적의 조기 종료 시간을 추정할 수 있는 방법을 도입했다.
L1-노름의 이점: 저자들은 L1-노름을 사용하는 것이 L2-노름 방식보다 수치적 최적값( $t_{test}$ )에 훨씬 더 가까운 정지 시간 추정치( $t^+$ )를 얻을 수 있음을 이론적 및 수치적으로 입증하였다.
저매개변수화(Underparameterized) 집중: 이 방법은 "양호한 과적합(benign overfitting)"이나 "에폭별 이중 하강(epoch-wise double descent)"이 덜 빈번한 저매개변수 영역( $m \leq n$ )에 특화되어 설계되었으며, 이 영역에서 조기 종료는 유익한 전략이 된다.
선형 프로빙 적용: 이론은 선형 모델을 위해 유도되었으나, 저자들은 은닉층을 고정하고 출력층만을 훈련하는 선형 프로빙을 통해 비선형 신경망(특히 MNIST 분류)에 성공적으로 적용하였다.

결과
저자들은 여러 예제를 통해 방법을 검증하였다:

합성 가우시안 데이터: 다양한 샘플 크기( $n=512$ 및 $n=16384$ )를 가진 이진 분류 작업에서, 분석적 추정치 $t^+$ 는 첫 번째 사례에서 실제 최적 시간 $t^*$ 와 정확히 일치하였고, 두 번째 사례에서는 타이트한 하한을 제공하였다. L1 기반 추정치는 L2 기반 추정치보다 일관되게 테스트 세트 최적값에 더 가까웠다.
MNIST 분류 (3-5 및 0-1): 4층 ReLU 네트워크와 선형 프로빙을 사용하여, 이 방법은 정지 시간을 정확하게 예측했다. 3-5 분류의 경우, $t^+ = 342$ 로 수치적 최적값 $t^* = 357$ 및 테스트 세트 최적값 $t_{test} = 356$ 과 유사했다. 0-1 분류의 경우, $t^+ = 415$ 는 $t^* = 415$ 와 일치했으며 $t_{test} = 418$ 에 근접했다.
유익한 정지: 테스트된 모든 사례에서, 추정된 정지 시간에서의 손실은 무한한 훈련 시간에서의 손실보다 낮았다( $L^*_D(t^+) < L^*_D(\infty)$ ). 이는 조기 종료가 유익하며 "양호한 과적합" 영역을 피한다는 것을 확인시켜 준다.
강건성: 이 방법은 다양한 데이터 분포(가우시안, 균등, 파레토)에서 잘 작동하였으며, 샘플 수와 파라미터 수의 비율( $n/m$ )이 증가함에 따라 성능이 향상되었다.

의의 및 주장
본 논문의 주요 의의는 별도의 검증 세트나 데이터 분포에 대한 제한적인 확률적 가정 없이 작동하는 데이터 의존적, 분석적 조기 종료 규칙을 제공한다는 점에 있다. 라데마커 복잡도와 L1-노름을 활용함으로써, 저자들은 선형 모델(그리고 선형 프로빙을 통한 특정 비선형 네트워크)의 일반화 오차를 최소화하기 위한 최적의 훈련 중단 시점을 결정하는 실용적인 도구를 제시한다. 저자들은 이 방법이 저매개변수 모델에는 잘 작동하지만, "양호한 과적합"이 발생하는 과매개변수(overparameterized) 영역을 위한 것은 아님을 겸허히 밝히고 있다. 또한 완전한 비선형 모델에 대한 직접적인 적용, 벡터 출력 처리, 입력 데이터의 무작위 노이즈 처리 등을 향후 연구 방향으로 제시하였다.

유사한 논문