[2019-05-27 업데이트: 로또 티켓 가설 (Lottery Ticket Hypothesis) 섹션 추가]

전통적인 머신러닝 경험을 바탕으로 딥러닝 분야에 진입하신다면, 다음과 같은 질문을 자주 고민해 보실 것입니다. "일반적인 딥 신경망은 파라미터가 너무 많고 학습 오류는 쉽게 완벽해질 수 있으므로, 반드시 심각한 과적합 (overfitting) 을 겪어야 할 것인데 어떻게 오프샘플 데이터 포인트로 일반화될 수 있는가?"

딥 신경망이 왜 어떤 식으로든 일반화할 수 있는지 이해하려는 노력은 생물학에 관한 흥미로운 논문 "생물학자가 라디오를 고칠 수 있는가?" (Lazebnik, 2002) 를 생각나게 합니다. 생물학자가 생물학적 시스템을 다루는 것처럼 라디오 장치를 고치려 한다면 삶은 어려울 것입니다. 라디오 시스템의 전체 메커니즘이 드러나지 않기 때문에, 작은 지역적인 기능성을 조작하는 것은 어떤 힌트를 줄 수 있지만, 시스템 내의 모든 상호작용을 제시할 수는 없고, 더구나 전체 작동 흐름을 제시할 수는 없습니다. 딥러닝과 관련이 있는지 여부에 상관없이, 이것은 매우 흥미로운 독서입니다.

이 글에서는 일반화성과 복잡성 측정에 관한 몇 편의 논문을 논의하고 싶습니다. 이것이 왜 DNN (딥 신경망) 이 일반화할 수 있는지에 대한 이해로 가는你们的 사고 경로를 밝히는 데 도움이 되기를 바랍니다.

압축과 모델 선택에 관한 고전 정리들#

분류 문제와 데이터셋이 있다고 가정해 보겠습니다. 우리는 이를 해결하기 위해 단순한 선형 회귀부터 디스크 공간에 전체 데이터셋을 암기하는 것까지 많은 모델을 개발할 수 있습니다. 어느 것이 더 좋을까요? 만약 우리가 학습 데이터의 정확성만 관심으로 둔다면 (특히 테스트 데이터가 알려지지 않았다고 가정할 때), 암기 접근법은 가장 좋은 것 같습니다 — 음, 이것은 맞지 않는다는 것을 알 수 있습니다.

이러한 상황에서 어떤 유형의 속성을 가진 모델이 좋을지를 결정할 때 우리를 안내해 주는 많은 고전 정리들이 있습니다.

"더 간단한 해결책은 더 복잡한 것보다 옳을 가능성이 큽니다."

이 문장은 우리가 세상을 설명하기 위한 여러 후보 이론에 직면하고 하나를 선택해야 할 때 매우 강력한 힘을 발휘합니다. 너무 많은 불필요한 가정이 어떤 문제에는 합리적으로 보일 수 있지만, 다른 복잡성으로 일반화하거나 결국 우주의 기본 원리로 이어지는 것은 어렵습니다.

이것을 생각해 보세요. 하늘이 낮에는 파란색이고 일몰 때는 붉은색인 이유는 같은 이유 (레이리 산란) 때문이라는 것을 사람들이 수백 년 만에 깨달았습니다. 두 현상은 매우 다르게 보이지만, 사람들은 아마도 각각 다른 설명을 제안했을 것입니다. 그러나 통합적이고 간단한 버전이 결국 승리했습니다.

오컴의 면도날 (Occam's Razor) 원리는 기계 학습 모델에도 마찬가지로 적용할 수 있습니다. 이러한 개념의 공식화된 버전은 최소 설명 길이 (Minimum Description Length, MDL) 원리로 불리며, 관측된 데이터를 기반으로 경쟁하는 모델/해설을 비교하는 데 사용됩니다.

"이해는 압축입니다."

MDL 의 기본 아이디어는 학습을 데이터 압축으로 보는 것입니다. 데이터를 압축함으로써, 우리는 일반화되지 않은 샘플로 일반화할 높은 잠재력을 가진 데이터의 규칙성이나 패턴을 발견해야 합니다. 정보 병목 이론 (Information Bottleneck Theory) 은 딥 신경망이 일반화 오류를 최소화하여 데이터를 표현하는 것을 먼저 학습하고 이 표현을 잡음 제거 (noise trimming) 를 통해 압축하는 것으로 학습된다고 믿습니다.

동시에, MDL 은 모델 설명을 압축 전달의 일부로 간주하므로, 모델은 임의적으로 커질 수 없습니다."

MDL 원리의 두 가지 버전은 다음과 같이 정의됩니다: 데이터셋 $
\mathcal{D}$ 를 설명할 수 있는 모델 목록 $\mathcal{H}^{(1)}, \mathcal{H}^{(2)}, \dots$ 가 주어졌을 때, 이 중 가장 좋은 가설은 다음 합을 최소화하는 모델이어야 합니다:

$L(\mathcal{H})$ 는 모델 $\mathcal{H}$ 의 비트 단위로 된 설명 길이를 나타냅니다.

$L(\mathcal{D}\vert\mathcal{H})$ 는 $\mathcal{H}$ 를 사용하여 데이터 $\mathcal{D}$ 를 인코딩할 때의 비트 단위로 된 설명 길이를 나타냅니다.

간단히 말하면, 가장 좋은 모델은 인코딩된 데이터와 모델 자체를 포함하는 가장 작은 모델입니다. 이 기준에 따라 본 섹션 초반에 제안한 기억 방식 (memorization approach) 은 훈련 데이터에서 얼마나 높은 정확도를 달성하더라도 끔찍하게 들립니다.

사람들은 Occam's Razor 가 틀렸다고 주장할 수 있습니다. 왜냐하면 현실 세계는 임의적으로 복잡할 수 있으므로, 우리는 왜 단순한 모델을 찾아야 하는지 묻기 때문입니다. MDL 의 흥미로운 관점은 모델을 근본적인 생성 정리 (generative theorems) 대신 "언어"로 간주하는 것입니다. 우리는 소수의 샘플에서 규칙성을 설명하기 위한 좋은 압축 전략을 찾고자 하며, 그들은 현상을 설명하기 위한 "실제" 생성 모델이 될 필요는 없습니다. 모델은 틀릴 수 있지만 여전히 유용할 수 있습니다 (즉, 어떤 베이즈 사전 (Bayesian prior) 을 생각해보세요).

Kolmogorov Complexity 는 현대 컴퓨터의 개념에 의존하여 객체의 알고리즘적 (설명) 복잡도를 정의합니다: 그것은 해당 객체를 설명하는 가장 짧은 이진 컴퓨터 프로그램의 길이입니다. MDL 에 따라, 컴퓨터는 본질적으로 가장 일반적인 데이터 압축기 형태입니다.

Kolmogorov Complexity 의 형식적 정의는 다음과 같습니다: 보편적인 컴퓨터 $\mathcal{U}$ 와 프로그램 $p$ 가 주어졌을 때, 컴퓨터가 프로그램을 처리하여 출력하는 것을 $\mathcal{U}(p)$ 로 표시하고, 프로그램의 설명 길이를 $L(p)$ 로 표시합니다. 그러면 보편적인 컴퓨터 $\mathcal{U}$ 에 대한 문자열 $s$ 의 Kolmogorov Complexity $K_\mathcal{U}$ 는 다음과 같습니다:

[여기서 공식이 누락되었으므로 원문과 동일하게 유지]

참고로, 보편적인 컴퓨터는 다른 모든 컴퓨터의 동작을 모방할 수 있는 것입니다. 모든 현대 컴퓨터는 튜링 머신으로 환원될 수 있으므로 모두 보편적입니다. 우리는 어떤 컴퓨터를 사용하든 정의가 보편적이라는 것은, 다른 보편적인 컴퓨터는 항상 $\mathcal{U}$ 의 동작을 클론하는 것을 프로그래밍할 수 있으며, 이 클론 프로그램의 인코딩은 상수일 뿐이기 때문입니다.

Kolmogorov Complexity 와 Shannon Information Theory 사이에는 많은 연결이 있습니다. 왜냐하면 둘 다 보편적 인코딩 (universal coding) 과 관련되기 때문입니다. 이는 놀라운 사실입니다: 무작위 변수의 기대 Kolmogorov Complexity 는 그 Shannon 엔트로피와 대략적으로 같습니다 (보고서 2.3 절 참조). 이 주제에 대한 더 많은 내용은 여기 범위를 벗어납니다. 하지만 온라인에는 흥미로운 독서가 많습니다. 스스로 도와주세요 :)

Occam's Razor 의 또 다른 수학적 형식화는 Solomonoff 의 보편적 추론 이론 (Solomonoff, 1964) 입니다. 원리는 Kolmogorov 복잡도에 기반하여 훈련 데이터를 생성하는 "가장 짧은 프로그램"에 해당하는 모델을 선호하는 것입니다.

딥 신경망은 전통적인 통계 모델에 비해 매우 많은 수의 파라미터를 가지고 있습니다. 만약 MDL 을 사용하여 딥 신경망의 복잡도를 측정하고, 파라미터 수를 모델 설명 길이로 고려한다면 그것은 끔찍하게 들릴 것입니다. 모델 설명 $L(\mathcal{H})$ 는 쉽게 통제할 수 없는 수준으로 성장할 수 있습니다.

그러나 많은 파라미터를 갖는 것은 신경망이 높은 표현력을 얻기 위해 필수적입니다. 유연한 데이터 표현을 포착할 수 있는 능력으로 인해 딥러닝은 다양한 응용 분야에서 큰 성공을 거두었습니다.

유니버설 근사 정리는 선형 출력 레이어가 있고, 1) 유한개의 뉴런을 가진 적어도 하나의 히든 레이어가 있으며, 2) 어떤 활성화 함수를 가지는 피드포워드 네트워크가 $oldsymbol{R}^n$ 의 콤팩트 부분집합에서 정의된 임의의 연속 함수를 임의의 정확도로 근사할 수 있다고 합니다. 이 정리는 시그모이드 활성화 함수에 대해 먼저 증명되었습니다 (Cybenko, 1989). 이후 유니버설 근사 속성은 활성화 함수의 선택에 특정되지 않지만 다층 피드포워드 아키텍처에 국한된다는 것이 밝혀졌습니다 (Hornik, 1991).

단일 레이어를 가진 피드포워드 네트워크는 어떤 함수를 표현하기에 충분하지만, 너비 (width) 는 지수적으로 커야 합니다. 유니버설 근사 정리는 모델이 학습되거나 일반화될 수 있는지 보장하지 않습니다. 종종 더 많은 레이어를 추가하면 얕은 네트워크에서 필요한 히든 뉴런의 수를 줄이는 데 도움이 됩니다.

유니버설 근사 정리를 활용하려면, 우리는 원하는 임계값 이하의 오차로 타겟 함수를 표현할 수 있는 신경망을 항상 찾을 수 있지만, 그 대가로 네트워크가 초거대해질 수 있습니다.

증명: 2 레이어 NN 의 유한 샘플 표현력#

지금까지 논의해 온 유니버설 근사 정리는 유한 샘플 집합을 고려하지 않습니다. Zhang, et al. (2017) 은 2 레이어 신경 네트워크의 유한 샘플 표현력에 대한 깔끔한 증명을 제공했습니다.

신경망 $C$ 가 $d$ 차원에서 샘플 크기 $n$ 이 주어졌을 때 어떤 함수를 표현할 수 있는 조건은 다음과 같습니다: 모든 유한 샘플 집합 $S \subseteq \mathbb{R}^d$ 와 $\\vert S \vert = n$, 그리고 이 샘플 집합에 정의된 모든 함수 $f: S \mapsto \mathbb{R}$ 에 대해, $C(oldsymbol{x}) = f(oldsymbol{x}), orall oldsymbol{x} \in S$ 를 만족하는 $C$ 의 가중치 구성을 찾을 수 있어야 합니다.

이 논문은 다음과 같은 정리를 제안했습니다:
$d$ 차원에서 크기 $n$ 의 샘플에 대해 어떤 함수를 표현할 수 있는 ReLU 활성화 함수와 $2n + d$ 개의 가중치를 가진 2 레이어 신경 네트워크가 존재합니다.

증명. 먼저 2 레이어 신경망 $C: \mathbb{R}^d \mapsto \mathbb{R}$ 를 구성하고자 합니다. 입력은 $d$ 차원 벡터 $oldsymbol{x} \in \mathbb{R}^d$ 입니다. 히든 레이어는 $h$ 개의 히든 유닛을 가지며, 가중치 행렬 $oldsymbol{W} \in \mathbb{R}^{d imes h}$, 편향 벡터 $oldsymbol{-b} \in \mathbb{R}^h$, 그리고 ReLU 활성화 함수를 갖습니다. 2 번째 레이어는 가중치 벡터 $oldsymbol{v} \in \mathbb{R}^h$ 와 0 편향을 가진 스칼라 값을 출력합니다.

네트워크 $C$ 의 입력 벡터 $oldsymbol{x}$ 에 대한 출력은 다음과 같이 표현할 수 있습니다:

여기서 $oldsymbol{W}_{(:,i)}$ 는 $d imes h$ 행렬의 $i$ 번째 열입니다.

샘플 집합 $S = \{oldsymbol{x}_1, \\dots, \\boldsymbol{x}_n\ ext{와 타겟 값 } \\boldsymbol{y} = \{y_1, \\dots, y_n \}$을 주었을 때, $C(oldsymbol{x}_i) = y_i, orall i=1,\dots,n$ 을 만족하도록 적절한 가중치 $oldsymbol{W} \in \mathbb{R}^{d imes h}$, $oldsymbol{b}, oldsymbol{v} \in \mathbb{R}^h$ 를 찾을하고자 합니다.

모든 샘플 포인트를 하나의 입력 행렬 $oldsymbol{X} \in \mathbb{R}^{n imes d}$ 로 하나의 배치로 결합해 봅시다. 집합 $h=n$ 이라면, $oldsymbol{X}oldsymbol{W} - oldsymbol{b}$ 는 $n imes n$ 크기의 정방 행렬이 됩니다.