Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks

기술 요약: O-minimal 구조 내의 이진 분류 작업에 대한 빠른 근사와 학습 (ReLU 신경망을 이용한)

문제 정의
본 논문은 결정 집합(decision set) $A \subseteq [-1/2, 1/2]^n$이 실수체의 o-minimal 확장 내에서 정의되는 이진 분류 문제를 조사한다. 심층 신경망은 경험적으로 큰 성공을 거두어 왔으나, 대상 집합에 대한 이론적 이해는 경계의 매끄러움(smoothness)이나 Barron 유형의 함수 클래스와 같은 특정 구조적 가정에 의존하는 경우가 많다. 저자들은 복잡한 결정 경계에서 성립하지 않을 수 있는 전역적 매끄러움 가정에 의존하지 않고, o-minimality를 통해 정의되는 "tame" 집합들의 더 넓은 클래스에 대해 정량적인 근사 및 학습률을 확립하고자 한다.

방법론
저자들은 o-minimal 기하학의 셀 분해 정리(cell decomposition theorems)에 내재된 개념으로부터 동기 부여를 받아, 정의 가능한 집합(definable sets)의 고전적 대리물로서 **추적 가능한 집합(traceable sets)**이라는 클래스를 도입한다.

1. 추적 가능한 집합 (Traceable Sets): 집합 $A$가 $m$-traceable하다는 것은, 집합의 경계를 섬유별(fiber-wise)로 정의하는 유계인 $C^m$ 사상 $f_i, g_i$를 통해 귀납적으로 구성될 수 있음을 의미한다. 구체적으로, 이 집합은 각 층이 매끄러운 그래프에 의해 경계가 지어지는 "지평선(horizon)" 함수들의 시퀀스로 구축된다. 저자들은 $(m, \ell)$-traceable 집합을 이러한 집합들의 유한한 서로소 합집합으로 정의한다.
2. 확장 속성 (Extension Properties): 근사를 용이하게 하기 위해, 저자들은 경계 함수 $f_i, g_i$가 전체 도메인 상의 $C^m$ 함수로 확장될 수 있고 유계인 Sobolev 노름을 가져야 한다는 $(m, B)$-확장 속성을 부과한다.
3. 근사 전략: 핵심 근사 기법은 다음과 같다:
   • 매끄러운 함수와 그 합성 함수의 근사 결과를 활용하여, "지평선 함수"(매끄러운 그래프에 의해 경계가 지어지는 영역의 특성 함수)를 ReLU 신경망으로 근사한다.
   • ReLU 기반의 최솟값(minimum) 및 최댓값(maximum) 연산을 사용하여(왜냐하면 $\chi_{\cap} = \min$ 이고 $\chi_{\cup} = \max$ 이기 때문이다), 추적 가능한 집합의 특성 함수를 구성한다.
   • 확장 가정 하에서 이 집합들의 경계(frontier)가 르베그 측도(Lebesgue measure) 0을 가진다는 사실을 이용하여, 집합의 폐포(closure)를 근사하는 것이 $L^p$ 근사에 충분함을 보장한다.
4. 학습 프레임워크: 통계적 학습 분석은 구축된 ReLU 신경망 클래스의 엔트로피 추정치(covering numbers)와 도출된 근사율을 결합한다. 저자들은 특정 신경망 클래스에 대해 힌지 손실(hinge loss)을 적용한 경험적 위험 최소화(ERM)를 적용하여 일반화 경계(generalization bounds)를 도출한다.

주요 기여 및 결과

• 정량적 근사율 (Quantitative Approximation Rates): 본 논문은 임의의 $(m, \ell)$-traceable 집합 $\Omega \subseteq [-1/2, 1/2]^n$의 특성 함수 $\chi_\Omega$가 정확도 $\epsilon$에 대해 ReLU 신경망 $\Phi_\epsilon$에 의해 $L^p$ 노름에서 근사될 수 있음을 증명한다.

  • 네트워크 크기: 필요한 0이 아닌 가중치(size)의 수는 $O(\epsilon^{-p(n-1)/m})$이다.
  • 깊이: 네트워크의 깊이는 $\epsilon$에 독립적으로 유계이며, 구체적으로 $O(\log(\ell n) + \log(m))$이다.
  • 가중치: 가중치는 최대 $1/\epsilon$에 대해 다항식 수준으로 증가한다.
  • 이 결과는 추적 가능한 도메인 상에서 piecewise smooth한 정의 가능한 사상 $f: [-1/2, 1/2]^n \to \mathbb{R}$의 부분 클래스로 확장된다.

• 통계적 학습률 (Statistical Learning Rates): 도메인으로부터 균등하게 추출된 $N$개의 독립적인 샘플에 대해, 저자들은 구축된 ReLU 신경망 클래스에 대한 경험적 위험 최소화의 학습률을 도출한다.

  • 결과적인 분류기의 기대 오분류 오차(expected misclassification error)는 임의의 작은 다항 손실 인자 $N^\kappa$를 제외하고 $O(N^{-m/(m+pn-p)})$로 유계된다.
  • 이 비율은 근사 오차 경계와 가설 클래스의 피복 엔트로피(covering entropy)를 결합하여 도출된다.

• O-minimal 구조에 대한 적용: 저자들은 "m-admissible" 정의 가능한 컬렉션(셀 분해에 대한 균등한 경계를 가진 o-minimal 구조 내의 정의 가능한 집합들의 집합)이 traceable set의 속성을 만족함을 입증한다. 결과적으로, 도출된 근사 및 학습률은 이러한 정의 가능한 컬렉션에 직접 적용된다.

의의 및 주장
본 논문은 o-minimal 구조 내의 정의 가능성(definability)에 기반한 분류 이론을 위한 수학적으로 견고한 정규성 개념을 제공한다고 주장한다. 근사의 핵심적인 분석적 특징(traceability 및 smooth extensions)을 분리함으로써, 저자들은 o-minimality가 전역적 매끄러움을 요구하지 않으면서도 광범이한 실용적 결정 집합을 포착할 수 있음을 보여준다.

이 연구의 의의는 모델 이론(o-minimality)과 현대 딥러닝 이론을 연결하는 데 있다. 저자들은 o-minimal 구조가 근사 이론, 통계적 학습, 그리고 최적화를 동시에 연구할 수 있는 자연스러운 통합 프레임워크를 제공한다고 주장한다. 함수의 합성에 어려움을 겪을 수 있는 Barron 유형의 설정과 달리, o-minimal 구조는 정의 가능한 사상의 합성이 여전히 정의 가능하다는 점을 활용하여, 딥 뉴럴 네트워크에서 발견되는 아핀 사상(affine maps)과 비선형 활성화 함수의 반복적인 합성 과정을 자연스럽게 수용한다.

결과적으로, 결정 경계가 "tame"한 경우(o-minimal 구조에서 정의 가능한 경우), ReLU 신경망은 경계가 전역적으로 매끄러울 필요 없이, 매끄러움 파라미터 $m$과 차원 $n$에 따라 최적 또는 최적에 가까운 비율을 달와할 수 있음을 시사한다. 본 논문은 이러한 비율들이 특정 정의 가능한 집합 및 사상의 부분 클래스에 대해 도출되었으며, 학습률은 o-minimal 구조 내의 정의 가능한 컬렉션이 갖는 균등한 유한성 속성(연결 성분의 균등한 경계 및 VC 차원)에 의존한다는 점을 명시한다.