0. 논문 원문

1. Introduction

최근 들어 딥러닝이 큰 화두가 되었고, 다양한 구조와 방법론이 제시되었습니다. 딥러닝은 점점 더 다양한 주제의 문제를 다룰 수 있게 되었고, 이에 맞춰 다양한 딥러닝 구조가 제시되었습니다. 모델의 성능 향상 또한 지속해서 이루어졌습니다. 그리고 성능 향상을 위해 레이어를 깊게 쌓는 것은 보편화되어 있는 방법입니다.

그러나 이러한 발전은 통계 기법의 입장에서는 받아들이기 어려운 부분입니다. 왜냐하면 레이어를 깊게 쌓는다는 것은 모델 파라메터가 많아진다는 것이고, 일반적으로 필요 이상의 과한 파라메터 개수는 모델 성능 저하를 일으키기 때문입니다. 그럼에도 현실적으로, 많은 문제에 대해서 레이어를 깊게 쌓음으로써 모델 성능 향상이 이루어졌습니다.

그래서 연구자들은 이러한 현상을 이해하기 위해 다양한 연구를 진행했습니다. 한편 이 논문은 이러한 현상을 수학적으로 해석해보거나 또는 한계를 파악해보고자 했던 논문입니다. 정말 그냥 대충 요약하면 결론은, 수학적으로 서로 다른 두 뉴럴 네트워크가 같은 결과를 출력하는 경우는 생각보다 많지 않다는 것입니다.

2. Result

논문에서 주장하는 결론은 아래의 명제입니다.

$\text{Consider a bounded open nonempty domain} \; \mathcal{Z} \subseteq \mathbb{R}^{d_0} \text{ and any architecture} (d_0, ..., d_L)\\ \text{with } d_0 \ge d_1 \ge \cdots \ge d_{L-1} \ge 2, \; d_L=1. \\ \text{For this architecture, there exist a ReLU network } h_{\theta}: \mathcal{Z} \rightarrow \mathbb{R}, \\ \text{or equivalently a setting of the weights } \theta \overset{\vartriangle}{=} \left(W_1, b_1, ..., W_L, b_L \right), \\ \text{such that for any ‘general' ReLU network } h_{\eta}: \mathcal{Z} \rightarrow \mathbb{R} \text{ (with same architecture)} \\ \text{satisfying } h_{\theta}(z)=h_{\eta}(z) \text{ for all } z \in \mathcal{Z}, \text{ there exist permutation matrices } P_1, ..., P_{L-1}, \\ \text{and positive diagonal matrices } M_1, ..., M_{L-1}, \text{ such that} \\ \text{ }\\ \quad W_1=M_1 P_1 W'_1, \; b_1 = M_1 P_1 b'1, \\ \quad W_l = M_l P_l W'l P{l-1}^{-1}M{l-1}^{-1}, \; b_l=M_l P_l b'l, \; l \in \left\{2, ..., L-1\right\}, \\ \quad W_L = W'L P{L-1}^{-1}M{L-1}^{-1}, \; b_L=b'_L \\ \text{ }\\ \text{where } \eta \overset{\vartriangle}{=}(W'_1,b'_1, ...,W'_L,b'L) \text{ are the parameters of } h{\eta}.$

조건도 많고 명제도 길지만 결론적으로 얘기하는 것은 똑같은 구조의 ReLU Network 가 동일한 입력에 대해 동일한 출력을 갖기 위해서는 각 레이어가 Permutation Matrix(각 노드의 순서를 바꾸는 행렬) 과 Positive Diagonal Matrix(각 노드 값의 양의 배수를 취하는 행렬)으로 서로 변환될 수 있어야 한다는 의미입니다.

즉, 행렬이 가질 수 있는 자유도(?)를 생각해봤을 때, 두 네트워크가 같은 값을 가지는 경우는 많지 않다는 것을 증명하는 명제입니다. 주의해야 할 점은 위 명제에서 한정하는 네트워크 구조는 가장 단순한 Feed Forward 네트워크 구조입니다. CNN, Residual, RNN 등의 구조는 위 명제에 대해 증명되지 않았습니다. 또한 활성화 함수 또한 ReLU여야 합니다.

명제를 증명하기 위해 몇 가지 가정이 존재합니다. Z(입력값 범위)가 open nonempty 여야 하고, 레이어 넓이가 non-increasing 이어야 합니다. 또한 마지막 hidden layer 의 넓이가 2 이상이어야 합니다. 위 가정은 명제를 증명함에 있어 필요한 가정입니다.

그리고 'general' ReLU network 라는 개념이 등장합니다. 이 개념에 대한 소개는 아래에 다루도록 하겠습니다.

3. Discussion

저자는 위 명제를 바탕으로 서로 다른 두 ReLU network 가 동일한 출력을 만드는 경우가 생각보다 많지 않으며, over parametrization 에 따른 parameterization redundancy 가 적다고 이야기 합니다. 이러한 결론은 일반적인 생각과 모순되는데, 이는 아래와 같은 다양한 이유로 설명될 수 있다고 합니다.

4. Definition & Prove

위 명제를 증명하기 위해 필요한 개념과 보조 정리를 소개합니다. 위 명제를 증명하기 위해 다양한 개념을 설정하는 데, 천천히 읽으며 이해한다면 그 나름의 재미를 느낄 수가 있습니다.

4-1. ReLU Network

위 명제를 이해하기 위해 General ReLU network 를 알아야 합니다. General ReLU network 를 소개하기에 앞서 이 논문에서 말하는 ReLU network 가 무엇인지 소개합니다.

$\text{ReLU Netowrk} \\ \text{Let } \mathcal{Z} \subseteq \mathbb{R}^{d_0} \text{ with } d_0 \ge 2 \text{ be a nonempty open set, and let } \theta \overset{\vartriangle}{=} \left(W_1,b_1, ...,W_L,b_L\right) \\ \text{be the network's parameters, with } W_l \in \mathbb{R}^{d_l \times d_{l-1}},b_l \in \mathbb{R}^{d_l}, \text{ and } d_L=1. \\ \text{We denote the corresponding ReLU network by } h_{\theta}: \mathcal{Z} \rightarrow \mathbb{R}, \text{ where} \\ \sigma \text{ is a ReLU fucntion.}\\ \text{}\\ \quad h_{\theta} \overset{\vartriangle}{=} h_{\theta}^L \circ \sigma \circ h_{\theta}^{L-1} \circ \cdots \circ h_{\theta}^1, \\ \text{}\\ \text{and } h_{\theta}^l(\mathbf{z})=W_1 \cdot \mathbf{z} + b_l. \text{ For } 1 \le l \le k \le L, \text{ we also introduce notation for } \\ \text{truncated networks,}\\ \text{}\\ \quad h_{\theta}^{l:k} \overset{\vartriangle}{=} h_{\theta}^k \circ \sigma \circ h_{\theta}^{k-1} \circ \cdots \circ h_{\theta}^l. \\ \text{}\\ \text{We will omit the subscript } \theta \text{ when it is clear from the context.}$

위 정의에서 알 수 있듯이 이 논문에서 말하는 ReLU network 는 가장 단순한 형태의 네트워크입니다. 모든 이전 레이어의 모든 노드를 활용하여 현재 노드값을 계산하고, Residual 과 Recurrent 등이 없는 가장 단순한 형태의 네트워크입니다.

General ReLU network 는 특수한 성질을 만족하는 ReLU network 로, 연구에 용이하다고 합니다. 간단하게 말하면 general ReLU network는 모든 truncated network 가 서로 다른 입력 값에 대하여 서로 다른 출력이 나오도록 하는 네트워크입니다. 아래 명제에서는 truncated network 표현에서 $\theta$ 가 생략되고, 노드 위치를 나타내는 $i,j$ 가 추가되었습니다.

$\text{General ReLU network is one that satisfies the following three conditions.} \\ \text{} \\ \quad \text{1. For any unit } \left(l,i \right), \text{the local optima of } h_{i}^{1:l} \text{ do not have value exactly zero.} \\ \quad \text{2. For all } k \le l \text{ and all diagonal matrices } \left(I_k, ..., I_l \right) \text{ with entries in} \left\{0,1 \right\}, \\ \quad \quad rank(I_l W_l I_{l-1} \cdots I_k W_k) = \min(d_{k-1},rank(I_k), ..., rank(I_{l-1}), rank(I_l)) \\ \quad \text{3. For any two units } (l,i), \; (k,j), \text{ any linear region } \mathcal{R}_1 \subseteq \mathcal{Z} \text{ of } h_i^{1:l}, \\ \quad \quad \text{and any linear region } \mathcal{R}2 \subseteq \mathcal{Z} \text{ of } h_j^{1:k}, \text{ the linear functions implemented} \\ \quad \quad \text{by } h{i}^{1:l} \text{ on } \mathcal{R}_1 \text{ and } h_j^{1:k} \text{ on } \mathcal{R}_2 \text{ are not multiples of each other.}$

추가로, Transparent ReLU network를 정의합니다. Transparent ReLU network 는 어떤 입력이 들어와도 모든 레이어에서 적어도 하나의 노드 값은 active 되는 성질을 갖는 네트워크입니다. 대괄호는 정수 집합을 의미합니다. 예를 들어 [3] 은 1,2,3 으로 이루어전 집합을 의미합니다.

$\text{Transparent ReLU Network} \\ \text{A ReLU network} h: \mathcal{Z} \rightarrow \mathbb{R} \text{ is called transparent if for all } \mathbf{z} \in \mathcal{Z} \text{ and } l\in [L-1], \\ \text{there exists } i \in [d_l] \text{ such that } h_{i}^{1:l}(\mathbf{z}) \ge 0.$

ReLU network 와 관련된 정의를 마쳤습니다. 이제 논문에서는 위 정의를 바탕으로 논리를 전개해나갑니다.

4-2. Fold Set

Fold Sets 라는 새로운 개념을 제시합니다. Fold Set 은 그 이름에서 유추할 수 있듯이 공간이 접히는 부분으로, ReLU 함수를 생각해보면 x=0 에서 출력값이 접힙니다. Fold Set 는 ReLU 함수의 접히는 부분을 보다 일반화하여 표현한 것이라고 할 수 있습니다.

$\text{Fold Set}\\ \text{Denoted } \mathcal{F}(f), \text{ defined as } \left\{\mathbf{z}:\mathbf{z} \in \mathcal{Z} \text{ and } f \text{ is non-differentiable at } \mathbf{z} \right\}$

또한 주어진 ReLU network 가 위에서 정의한 'general' ReLU network 이면서 'transparent' ReLU network 라면 아래 정리가 성립합니다. 즉, 각 레이어의 각 노드 값이 0이 되는 모든 입력값의 집합이 Fold Set 이 됩니다.

$\text{보조정리1} \\ If \; h: \mathcal{Z} \rightarrow \mathbb{R} \text{ is a general and transparent ReLU network, then} \\ \quad \mathcal{F}(h) = \underset{l,i}{\bigcup} \left\{ \mathbf{z}:h_i^{1:l}(\mathbf{z})=0 \right\}$

아래 그림은 Fold Set 을 각 레이어 별로 구분지어 표현한 예시입니다. 예를 들어 첫 레이어에서는 가장 왼쪽 세 개의 선의 Fold Set 으로 인식됩니다. 이후 두번째, 세번째 레이어에서는 각각 주황 선과 검은 선이 Fold Set 으로 인식됩니다. Fold Set 은 주어진 모든 선을 합친 집합으로, 가장 오른쪽 그림의 모든 선과 같습니다.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/cba19549-745a-4709-8816-83499f41034e/Untitled.png

4-3. Piece-wise Linear Surface