신경망의 위상수학적 표현력에 대한 구성적 한계
Constructive Bounds for the Topological Expressivity of Neural Networks
한국어 초록
신경망(neural network) $Φ$의 표현력(expressivity)은 해당 네트워크가 표현할 수 있는 함수의 클래스를 설명합니다. 위상수학적 표현력(topological expressivity)이라는 용어는 이진 분류(classification)를 이해하는 데 특히 적합한 일련의 척도를 의미하며, 종종 결정 경계의 베티 수(Betti number)인 $β(Φ^{-1}(0))$의 관점에서 공식화됩니다. 이러한 대중성에도 불구하고, 이 척도는 회귀 및 결정 경계를 수반하지 않는 기타 문제에는 그다지 유용하지 않습니다. 대신, 본 논문에서는 신경망 출력의 베티 수인 $β(Φ(X))$의 관점에서 위상수학적 표현력을 연구할 것을 제안합니다. 우리는 구조가 $(d,\sum\limits_{k=1}^{d } β_k(3k+2),\sum\limits_{k=1}^{d}β_k(k+1))$인 렐루(ReLU) 네트워크가 임의의 베티 수를 갖는 구(sphere)들의 쐐기합(wedge sum)과 호모토피 동치(homotopy equivalent)인 공간을 표현할 수 있음을 엄밀하게 증명합니다. 이는 임의의 연결된($β_0=1$) 베티 수 수열에 대한 상한을 제공하지만, 차원이 $d_1,...,d_N$인 $N$개 구의 곱과 호모토피 동치인 공간을 구성함으로써 $\prod_n (1+x^{d_n})$으로 주어지는 베티 수에 대해 훨씬 더 나은 한계인 $(\sum\limits_{n=1} d_n, 3\sum\limits_{n=1}\limits^N d_n + 2N, \sum\limits_{n=1}\limits^N d_n + N)$을 얻습니다. 마지막으로, 우리는 구와 위상동형(homeomorphic)인 공간에 대해 구조적 한계 $(d,d+1,d+1)$을 제공하는 훨씬 더 강력하고 타이트한 한계를 제시(conjecture)합니다.
원문 초록
The expressivity of a neural network $Φ$ describes the class of functions that a network can express. The term topological expressivity refers to a family of measures particularly suited to understand binary classification and is often formulated in terms of the Betti numbers of a decision boundary $β(Φ^{-1}(0))$. Despite its popularity, this measure is not as useful for regression and other problems that do not involve a decision boundary. Instead, we propose to study topological expressivity in terms of the Betti numbers of the output of a neural network $β(Φ(X))$. We formally prove that a ReLU network with architecture $(d,\sum\limits_{k=1}^{d } β_k(3k+2),\sum\limits_{k=1}^{d}β_k(k+1))$ can express spaces homotopy equivalent to wedge sums of spheres with arbitrary Betti numbers. This gives upper bounds for any arbitrary connected ($β_0=1$) sequence of Betti numbers, but by constructing spaces homotopy equivalent to products of $N$ spheres of dimension $d_1,...,d_N$ we achieve much better bounds $(\sum\limits_{n=1} d_n, 3\sum\limits_{n=1}\limits^N d_n + 2N, \sum\limits_{n=1}\limits^N d_n + N) $ for Betti numbers given by $\prod_n (1+x^{d_n})$. Finally we conjecture a much stronger tight bound which gives the architectural bound $(d,d+1,d+1)$ for a space homeomorphic to the sphere.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
심층 렐루(ReLU) 네트워크의 강건성에 대한 이론적 하한
Theoretical Lower Bounds on the Robustness of Deep ReLU Networks
본 논문에서는 무작위 입력 섭동(random input perturbation)에 대한 매개변수화된 신경망의 강건성에 대한 이론적 연구를 제시합니다. 구체적으로, 주어진 입력의 무작위 $L_2$-섭동이 올바른 분류(classification) 결과를 도출할 확률을 정량화하여 국소 강건성(local robustness)을 분석합니다. 심층 렐루(ReLU) 네트워크에 대해, 고차원 기하학의 도구, 특히 측도 집중 현상(concentration of measure)과 입력-출력 함수에 의해 유도되는 기하학적 구조의 새로운 특성화를 결합하여 국소 강건성의 하한을 도출합니다. 네트워크의 깊이나 아키텍처와 관계없이, 렐루 네트워크에 의해 유도된 입력 공간의 분할에서 각 볼록 다포체(convex polyhedral) 영역은 기껏해야 네트워크 유닛 수만큼의 면을 가짐을 증명합니다. 이러한 기하학적 특성은 본 연구의 강건성 분석에서 핵심적인 요소로 작용합니다. 마지막으로 국소 강건성이 입력 차원에 따라 어떻게 스케일링되는지 분석하고 이웃 영역에 적대적 예제(adversarial example)가 포함될 가능성이 가장 높은 입력 집합들을 특성화합니다. 취약한 지점을 포함하는 결정 경계 이웃의 너비는 차원이 증가함에 따라 급격히 줄어들고 네트워크 유닛 수에 대해서는 로그 형태로만 증가함을 보입니다. 또한 결정 경계의 대략적인 공간 채움 형태(space-filling shapes) 관점에서 취약한 지점 집합의 부피에 대해 논의합니다.
최소 노름 일변수 2층 ReLU 분류: 정확한 해와 스킵 연결을 통한 전역 최적성
Minimal-Norm Univariate Two-Layer ReLU Classification: Exact Solutions and Global Optimality with Skip Connections
우리는 일변수 2층 ReLU 네트워크를 이용한 이진 분류에서 최소 노름 보간(minimal-norm interpolation)과 $\ell_2$ 정규화 로지스틱 손실 최소화를 연구한다. 함수 공간에서 최적 분류기에 대한 완전한 기하학적 특성을 제시하며, 은닉층 바이어스가 매개변수 노름에 포함되는지 여부에 따라 해가 어떻게 달라지는지를 규명한다. 바이어스에 페널티를 부과하지 않는 경우, 최소 노름 보간 함수는 모든 레이블 전환 지점에 밀착하고 적절한 볼록성을 갖는 꺾임점(kink)을 지니는 연속 구간별 아핀 함수들과 정확히 일치한다. 바이어스에 페널티를 부과하는 경우, 최소해는 함수 공간에서 유일하며, 레이블이 같은 각 중간 구간마다 정확히 하나의 꺾임점을 갖고, 따라서 가장 희소한 양의 마진 분류기가 된다. 나아가 자유 아핀 스킵 연결(affine skip connection)을 추가해도 이러한 함수 공간의 해는 변하지 않지만 매개변수 공간의 지형(landscape)은 근본적으로 개선됨을 보인다. 즉, 제약 문제의 모든 KKT 점이 전역 최적해가 되는 반면, 스킵 연결이 없으면 차선(suboptimal) KKT 점이 나타날 수 있다. 로지스틱 손실에 대한 $\ell_2$ 정규화가 충분히 약한 경우에 대해서도 유사한 전역 최적성 및 기하학적 결과를 확립한다. 바이어스에 페널티를 부과하지 않는 경우에는 추가적인 희소성 유사 제약을 규명하였으며, 이는 대부분의 최소 노름 보간 함수가 마진 정규화된 로지스틱 손실 최소해의 작은 정규화 극한으로 나타날 수 없음을 의미한다. 데이터셋 복잡도와 네트워크 너비를 달리한 수치 실험은 예측된 지형 및 희소성 현상을 뒷받침한다.
이방성 및 혼합 매끄러움 함수의 심층 렐루 신경망 근사와 학습
Approximation and learning of anisotropic and mixed smooth functions by deep ReLU neural networks
본 논문은 심층 렐루(ReLU) 신경망이 매끄러운 함수를 얼마나 효율적으로 근사하고 학습할 수 있는지를 연구한다. 오차가 $L^p([0,1]^d)$ 노름으로 측정되고 근사자가 폭 $W$와 깊이 $L$을 갖는 네트워크일 때, 최근 연구들은 Sobolev 임베딩(embedding) 조건 $s/d>1/q-1/p$ 하에서 Besov 공간 $\mathcal{B}^s_{q,r}([0,1]^d)$에 대해 초근사율 $\mathcal{O}((WL)^{-2s/d})$를 증명하였다. 이 비율에서 차원의 저주(curse of dimensionality)를 극복하기 위해, 우리는 이 결과를 이방성 및 혼합 매끄러움 함수 클래스로 확장한다. 임베딩 조건 $\tilde{s} > 1/q-1/p$ 하에서 이방성 매끄러움 $\boldsymbol{s}=(s_1,\dots,s_d)$을 갖는 이방성 Besov 공간 $\mathcal{B}^{\boldsymbol{s}}_{q,r}([0,1]^d)$에 대해 근사율 $\mathcal{O}((WL)^{-2\tilde{s}})$를 확립한다. 여기서 평균 매끄러움 $\tilde{s} = (\sum_{i=1}^d s_i^{-1})^{-1}$이다. 혼합 매끄러움 $s>1/q-1/p$을 갖는 혼합 매끄러움 Besov 공간 $\mathcal{MB}^s_{q,r}([0,1]^d)$에 대해서는 근사율 $\mathcal{O}((WL)^{-2s})$가 대수(logarithmic) 인자까지 성립함을 보인다. 이러한 결과를 이용하여 이방성 Besov 함수의 합성(composition)에 대한 근사 경계도 유도한다. 응용으로, 심층 렐루 신경망이 광범위한 매끄러움 함수 클래스에 대해 대수 인자까지 minimax 최적(minimax optimal) 비율을 달성할 수 있음을 보인다.
데이터 과학에서의 표현 비용: 기초와 심층 신경망의 �asi-바나흐 공간
Representation Costs in Data Science: Foundations and the Quasi-Banach Spaces of Deep Neural Networks
우리는 데이터 적합(data-fitting) 방법에서 매개변수 공간 정규화(parameter-space regularizers)에 의해 유도되는 표현 비용(representation costs)을 분석하기 위한 일반적 프레임워크를 개발한다. 임의의 매개변수적 방법(parametric method)에 대해 표현 비용과 고유(native) 함수 공간(function space)을 정의하고, 존재성을 증명하며, 매개변수 공간 문제와 함수 공간 문제의 최솟값(infimal values)이 같고 최소화자(minimizers)가 서로 간에 전달(transfer)되는 조건을 규명한다. 이 프레임워크는 리프레젠터 정리(representer theorems)를 도출하고, 커널 방법과 RKHS, 웨이블릿(wavelets)과 Besov 공간, 얕은 신경망(shallow neural networks)과 변분 공간(variation spaces)을 포함한 고전적 공식화를 특수 경우로 복원한다. 우리의 주요 새로운 결과는 가중치 감쇠(weight-decay) 정규화를 적용한 깊이 $L$ 순전파 렐루(ReLU) 네트워크에 관한 것이다. 이러한 네트워크에 대해, 표현 비용이 �asi-반노름(quasi-seminorm)의 거듭제곱(power)임을 증명하고, 적절한 가설 하에서 고유 공간이 $L > 2$일 때 비볼록(nonconvex) 단위 공(unit ball)을 갖는 �asi-바나흐 공간(quasi-Banach space)임을 보인다. 이 결과들은 가중치 감쇠에 의해 유도되는 새로운 깊이 의존적(depth-dependent) �asi-바나흐 함수 공간 기하학(function-space geometry)을 밝힌다.
잔차 메모리와 오프셋 프레임을 통한 아핀 1차원 정제 반복의 정확한 렐루 실현
Exact ReLU realization of affine one-dimensional refinement iterates via residual memory and offset frames
우리는 유한 지원 행렬 마스크와 컴팩트 지원 연속 구간별 선형 입력 및 forcing 데이터를 갖는 형태 [(Wγ)(t)=\sum_{j\in\mathbb{Z}} A_jγ(Mt-j)+B(t),]의 벡터값 아핀 정제 연산자를 연구한다. (B\equiv 0)에 대한 동차 실현 정리에 기초하여, (M\ge 3)에 대해 모든 유한 아핀 반복 (W^nγ)이 깊이가 (O(n))인 정확한 고정 폭 렐루 실현을 허용함을 증명한다. 주요 새로운 요소는 잔차 메모리 컨트롤러이다. 이는 비가역적 잔차 역학을 단사 skew-product로 대체하고, 아핀 forcing 합의 Horner형 평가에 필요한 잔차 상태의 정확한 역방향 재생을 가능하게 한다. 오프셋 프레임은 forcing 원자를 잔차 이음(seam)으로부터 멀리 정렬하여, 상보적 루프 판독(readout)이 그 값을 정확히 복원할 수 있게 한다. 남은 분기 선택 모호성은 누적된 아핀 상태가 이미 소멸한 지점에서만 발생한다. (M\ge 3)에 대해, 결과는 임의의 컴팩트 지원 연속 구간별 선형 forcing 항에 적용된다. (M=2)에 대해서는 동일한 구성이 일반 프레임 이음 분리 forcing에 적용된다. 또한 고정된 유한차원 연속 구간별 선형 span 내 forcing 항에 대한 단계 의존적 확장을 증명하고, 개방 곡선(open-curve), 유한 상태(finite-state), Hilbert- 및 Morton형 재귀 구성에 대한 결과적 선형 깊이 향상을 기록한다.
신경망 학습의 다항 시간 해결 가능성에 대한 새로운 복잡도 이론적 경계
New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
현대 기계학습 연구에서 신경망이 근본적인 역할을 수행함에도 불구하고, 신경망을 최적으로 학습하는 문제의 계산 복잡도에 대한 이해는 가장 단순한 종류의 활성화 함수를 다루는 경우에도 여전히 불완전하다. 실제로 선형 및 렐루 활성화 함수 하에서 이 문제에 대해 점점 더 엄격한 하한을 확립하는 매우 최근의 결과들이 다수 있었지만, 새로운 다항 시간 내 해결 가능한 신경망 구조를 식별하는 데에는 그에 비해 진전이 적었다. 본 논문에서는 선형 및 렐루 활성화 신경망을 최적으로 학습하는 문제에 대한 새로운 알고리즘적 상한을 제시하여, 이러한 문제들의 다항 시간 해결 가능성 경계를 기존 최첨단을 넘어 확장한다. 특히 렐루 신경망의 경우, 은닉 뉴런의 출력 차수(out-degree)가 $1$인 모든 구조에 대한 다항 시간 해결 가능성을 확립함으로써 Arora, Basu, Mianjy 및 Mukherjee의 기존 알고리즘을 개선한다. 한편 선형 활성화 함수를 갖는 신경망에 대해서는, 새로운 데이터 처리량(data throughput) 조건을 만족하는 신경망 구조를 최적으로 학습할 수 있는 알고리즘을 통해 자명하지 않은 최초의 다항 시간 해결 가능 신경망 클래스를 식별한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.