Tubular Neighbourhoods of Pfaffian Sets and Applications to Neural Networks

기술 요약: 파파프 함수 집합의 튜브 근방과 신경망에 대한 응용

문제 정의
본 논문은 매끄러운 초월 함수(예: 로지스틱 시그모이드, tanh)를 사용하는 신경망 분류기의 결정 경계(decision boundary)가 갖는 기하학적 복잡성을 다룬다. 이러한 분류기의 강건성(robustness) 분석에서 핵심적인 문제는 무작위 입력이 결정 경계의 $\varepsilon$-튜브 근방(tubular neighborhood) 내에 존재할 확률을 정량화하는 것이다. 이 확률은 분류기의 조건수(condition number)에 대한 꼬리 경계(tail bounds)로 직접 연결되며, 여기서 조건수는 입력 노름(norm)과 오분류까지의 거리 사이의 비율로 정의되는 강건성의 척도이다.

알제브라적 다양체(algebraic varieties)의 튜브 근방 부피에 대한 부피 경계는 이미 잘 확립되어 있으나(예: Weyl의 튜브 공식, Smale, Renegar, Basu-Lerux의 결과), 이를 초월적 활성화 함수를 사용하는 신경망으로 확장하는 것은 매우 까다롭다. 표준적인 대수적 도구인 베주 정리(Bézout's theorem)는 이러한 경우에 불충분하다. 대신, 저자들은 다항식 계수를 가진 1차 편미분 방정식의 삼각 체계(triangular systems)를 만족하는 함수들을 포함하여 반대수적 집합(semi-algebraic sets)을 일반화한 파파프 함수(Pfaffian functions) 이론을 활용한다. 주요 과제로 식별된 것은, 신경망에 일반적인 파파프 경계(Khovanskii의 fewnomial 이론 기반)를 적용할 경우 네트워크 너비(width)에 대해 지수적으로 의존하는 상수가 산출되어, 경계가 실질적이고 이론적으로 최적의 상태가 되지 못한다는 점이다.

방법론
저자들은 적분 기하학, o-최소 기하학(o-minimal geometry), 그리고 대수적 조합론을 결합한 프레임워크를 개발한다:

1. 파파프 튜브 공식(Pfaffian Tube Formula): 저자들은 매끄러운 파파프 초곡면(hypersurface)의 튜브 근방 부피에 대한 경계를 도출한다. 이는 Weyl의 튜브 공식 변형과 일반화된 가우스 사상(Gauss map)의 차수에 대한 경계를 결합함으로써 달성된다. 가우스 사상의 차수는 체인 차수(chain degree), 함수 차수(function degree), 체인 순서(chain order)를 나타내는 "포맷(format)" $(\alpha, \beta, s)$에 기초하여 Khovanskii의 정리를 통해 제한된다.
2. 파파프 함수로서의 신경망: 저자들은 매끄럽고 자율적인(autonomous) 파파프 활성화 함수를 가진 신경망 자체가 파파프 함수임을 입증한다. 네트워크의 포맷은 깊이(depth), 너비(width), 그리고 활성화 함수의 포맷을 바탕으로 귀납적으로 도출된다.
3. 단일층 신경망에 대한 다항식 경계: 일반적인 Khovanskii 경계에 내재된 너비에 대한 지수적 의존성을 극복하기 위해, 저자들은 유리수 가중치를 가진 단일 은닉층 시그모이드 네트워크에 집중한다. 이들은 변수 변환(지수 치환)을 사용하여 가우스 사상 시스템을 로랑 다항식(Laurent polynomials) 시스템으로 변환한다. BKK(Bernstein-Kushnirenko-Khovanskii) 정리를 적용함으로써, 해의 개수를 뉴턴 다면체(Newton polytopes)의 혼합 부피(mixed volume)로 제한한다. 결정적으로, 가중치가 유리수인 경우 격자 구조(lattice structure) 덕분에, 경계가 네트워크 너비 $w$에 대해 다항식 차수인 $O(w^n)$의 차수를 갖도록 함을 보여준다.
4. 아핀 절단(Affine Sections) 처리: 전체 튜브 공식을 위해서는 다양한 차원의 아핀 부분 공간과의 교차에 대한 경계가 필요하다. 저자들은 일반적인 절단(generic sections)이 BKK 접근법에 필요한 유리 격자 구조를 파괴하지만, 곱셈 차트 변환(multiplicative chart transformation)을 통해 해당 시스템을 체인 길이가 너비와 독립적인 파파프 시스템으로 취급할 수 있음을 보여주며, 이를 통해 모든 절단 차수에 대해 $O(w^{2n})$의 다항식 경계를 얻는다.

주요 기여 및 결과

• 파파프 초곡면에 대한 일반 튜브 경계 (정리 3.6): 저자들은 매끄럽고 유계인 파파프 초곡면 $V = Z(f)$의 튜브 근방 부피 경계를 설정한다. 점 $X$가 구 $B(p, \rho)$ 내에서 균등 분포를 따를 때, $X$가 $V$로부터 거리 $\varepsilon$ 이내에 존재할 확률은 다음과 같이 제한된다:
  $$P\{d(X, V) \le \varepsilon\} \le C_{\alpha,\beta,s,n} \left[ \left(1 + \frac{(\alpha+\beta+1)\varepsilon}{\rho}\right)^n - \left(1 + \frac{\varepsilon}{\rho}\right)^n \right]$$
  여기서 상수 $C$는 파파프 포맷에 의존한다. 이는 대수적 다양체에 대한 기존 결과들을 일반화한다.

• 일반 파파프 네트워크에 대한 강건성 보장 (정리 5.4, 추론 5.7): 튜브 공식을 신경망에 적용하여, 저자들은 조건수 $C(X)$에 대한 꼬리 경계를 도출한다. $\ell$개의 은닉층과 $h$개의 총 유닛을 가진 네트워크의 경우, 꼬리 확률은 $O(1/t)$로 감소한다. 그러나 상수는 체인 길이에 대한 표준 Khovanskii 경계로부터 발생하는 $2^{h(h-1)/2}$의 지수적 인자를 포함한다.

• 단일층 시그모이드 네트워크에 대한 너비 다항식 경계 (정리 4.15, 추론 5.8): 유리수 가중치를 가진 단일 은닉층 네트워크의 경우, 저자들은 지수적인 Khovanskii 인자를 제거한다. 이들은 가우스 사상의 최대 차수가 $C(n, L) \cdot w^n$ (및 절단 차수는 $w^{2n}$)으로 제한됨을 증명하며, 여기서 $L$은 가중치와 관련된 격자 상수이다. 결과적으로, 조건수의 꼬리 경계는 너비 $w$에 대해 다항식이 된다:
  $$P\{C_p(X) > t\} \le O\left(\frac{w^n}{t}\right)$$
  이 결과는 구성적 하한(lower bound, 명제 4.11)을 통해 $w$에 대한 의존성이 날카롭다(sharp)는 것이 입증되었다.

• 가우시안 vs 균등 설정: 논문은 구(ball) 상의 균등 분포와 가우시안 섭동(perturbation)에 대한 꼬리 경계를 모두 제공한다. 가우시안 케이스의 경우, 저자들은 다항식 경계가 "큰 반지름" 부분의 적분에는 유효하지만, "작은 반지름" 부분은 여전히 일반적인 파파프 경계에 의존하여, 특정 집중 조건(concentration conditions)이 충족되지 않는 한 지수적 인자가 지배적일 수 있는 혼합 경계(hybrid bound)를 형성한다고 언급한다 (주석 5.11).

의의 및 주장
본 논문은 단순히 네트워크 크수에 대해 지수적이지 않은, 초월적 활성화 함수를 가진 신경잡에 대한 최초의 효과적이고 정량적인 강건성 보장을 제공한다고 주장한다. 파파프 설정을 통해 튜브 근방 이론을 일반화함으로써, 저자들은 수치 해석의 고전적 조건화 이론과 현대 딥러닝 사이의 간극을 메운다.

주된 의의는 단일층 네트워크에 대한 경계의 정교화에 있다. 저자들은 "기성품(off-the-shelf)" 방식의 Khovanskii 정리 적용이 지나치게 비관적인 지수적 경계를 산출하는 반면, 유리 가중치와 단일층 구조의 특수성을 활용하면 다항식 경계를 얻을 수 있음을 보여준다. 이는 단층 네트워크의 결정 경계가 갖는 기하학적 복잡성이 일반적인 fewnomial 이론이 시사하는 것보다 훨씬 낮음을 의미한다.

저자들은 다층 네트워크에 대해서는 신중한 태도를 유지한다. 이들은 단일층에 대한 너비 다항식 경계가 "layered-Rolle 장애물(layered-Rolle obstruction)"과 층상 체인(layered chains)에 대한 다차원 Rolle 르마의 부재로 인해 자동으로 심층 네트워크으로 확장되지 않음을 명시한다. 저자들은 완전한 다항식 경계가 존재할 수 있음을 시사하는 블록 Khovanskii 경계(Conjecture 6.1)와 추측 4.13을 제안하며, 이를 증명하기 위해서는 현재의 순차적 Khovanskii 적용을 넘어서는 새로운 도구가 필요하다고 밝힌다. 또한, 현재의 결과는 매끄러움(gradient가 0이 아님)을 요구하며, (ReLU 네트워크나 특정 가중치 설정에서 흔히 나타나는) 특이 결정 경계(singular decision boundaries)로 경계를 확장하는 것은 여전히 미해결 과제로 남아 있다.