이 논문에서는 신경망의 각 레이어에 의한 forward에 해당하는 식이 동역학 시스템의 이산시간 운동방정식과 동일한 형태를 갖는다는 점에 착안하여, 신경망 학습에 최적 제어 이론을 적용하였습니다. 최적 제어 이론 중에서도 가장 기본이 되는 Pontryagin's maximum/minimum principle에서 출발하여, costate equation을 backward propagation 시킨 후 이를 바탕으로 각 레이어의 학습이 모두 병렬적으로 이루어질 수 있는 알고리즘을 제안하고 있습니다.
Introduction
기존의 신경망 학습에 사용되는 방법들에는 다음과 같은 문제점들이 있습니다:
- (특히 초반에) 느린 파라미터 업데이트
- back-propagation 과정 이외에는 신경망 자체 구조에 대한 정보를 사용하지 않음
이 논문에서는 신경망 학습을 (이산시간에서의) 최적 제어 문제로 변환하여, 제어 문제에서 최적성을 위해 사용하는 필요 조건들을 이용한 학습법을 제안합니다. 이 경우 Hamiltonian's equation과 경계조건을 이용한 propagation 후 optimization step에서 각 layer들의 의존성이 완전히 사라지기 때문에, 연산 과정에서의 이점이 있습니다. 또한, error estimation과 convergence에 대한 해석도 가능하며, 수치적으로는
- 경사하강법에서 flat이나 saddle과 같은 manifold에서 수렴 속도가 저하되는 현상을 해결할 수 있었으며,
- 동일 iteration에서의 더 빠른 수렴성
과 같은 장점들이 있다고 언급하고 있습니다.
Theoretical Backgrounds and Derivations
Function Approximation by Dynamical Systems
이미지, 시계열값 등의 input을 X, 카테고리나 기타 수치적 예측값인 output을 Y라고 하면 supervised learning의 목적은
인 함수 F를 neural network 형태로 근사하는 것이라고 할 수 있습니다.
먼저 이 논문의 전개를 따라가기 위해 supervised learning의 objective를 dynamical system에서의 수식으로 표현합니다. 다음과 같이 일반적인 운동방정식을 고려합니다.
제어 문제의 일반적인 형태는 다음과 같이 나타낼 수 있습니다.
보통 deep learning에서의 f는 linear transformation과 activation function가 결합된 형태로 나타나며, 목적함수 L은 각 layer의 파라미터와 관련된 값이므로 regularization에 해당합니다.
위 문제는 일반적인 최적제어 문제에 해당합니다. 즉 위와 같이 표현할 경우, 일반적인 딥러닝에서 접근하는 방법과는 반대로, 위 문제의 최적의 해를 찾은 다음에 최적화하는 방식의 접근이 가능합니다.
특히 deep residual network의 경우에는 연속시간 운동방정식이 이산화된 형태로 해석할 수 있습니다 (E, 2017). 이 논문의 나머지 부분에서는 이러한 연결고리에 주목하여 residual network들을 다루며, 일반적인 DNN들에 대해서는 PMP가 성립하는지 아직 확실치 않습니다.
Pontryagin's Maximum Principle
먼저 다음과 같이 Hamiltonian을 정의합니다.
이 때, 필요조건들은 Hamilton's equation과 그 경계조건,
그리고 Pontryagin's maximum principle
입니다. (일반적으로 optimal control 문제에서의 필요조건에 해당하며, calculus of variation으로부터 유도할 수 있습니다.)
위의 필요조건들에서 optimal control \theta^*는 feedback control이 아니므로, Hamilton's equation과 동시에 forward/backward propagation이 가능합니다. 일반적인 control theory에서는 feedback control을 가정하기 때문에, dynamic programming/HJB equation 등을 이용해서 해를 구하지만 신경망 학습에서는 파라미터들이 input에 따라 변하는 것이 아니기 때문에, open-loop solution을 적용할 수 있습니다.
Basic MSA
PMP의 수치적인 해를 구하는 방법들은 여러가지 방법 중, 스케일 상 머신러닝 문제에의 적용이 적합한 방법 중 하나로 method of successive approximations (MSA; Chernousko and Lyubushin, 1982)가 있습니다. 이 방법은 propagation과 optimization step을 번갈아가면서 연산하는 반복적 방법입니다.
위의 알고리즘을 살펴보면 forward-backward Hamiltonian dynamics와 maximization의 두 단계로 이루어진 것을 볼 수 있습니다. (앞서 언급한 바와 같이 일반적으로 control theory에서 다루는 문제와 다르게 propagation과 optimization을 분리할 수 있는 이유는, control variable/parameter \theta가 costate P에 의존하지 않기 때문입니다.) 이 알고리즘을 적용했을 때의 가장 큰 장점은, 각 t마다 maximization을 따로 연산할 수 있다는 점입니다. 즉, 각 layer들의 최적화 과정이 서로 의존적이지 않기 때문에 이 부분을 완전하게 병렬처리할 수 있습니다.
Error Estimate for the Basic MSA
Extended PMP and Extended MSA
MSA는 LQR의 경우에는 잘 수렴하지만, 일반적인 문제에서는 initial guess에 따라 발산할 수 있는 것으로 알려져 있습니다. 이는 optimization의 constraint에 해당하는 Hamilton's equation 때문에 feasibility error가 커져서 발생하는 것이며, 이를 lemma 2를 통해서 다루고 있으나, 이 리뷰에서는 생략하도록 하겠습니다.
Algorithm 1에서의 feasibility error를 줄이기 위해서 augmented Lagrangians를 사용합니다. 상수 \rho>0 에 대해서 Hamiltonian dynamics에 페널티를 부과한 항을 추가함으로써 다음과 같이 augmented Hamiltonian을 정의합니다.
이 augmented Hamiltonian에 대해서 다시 optimality condition들을 rewrite하면 다음과 같습니다. 논문에서는 이를 extended PMP로 지칭합니다.
Extended PMP (11번 식)은 원래의 PMP보다 더 *약한* 필요조건이지만, 충분히 큰 rho를 선택했을 때 hamiltonian equation의 페널티 항 덕분에 feasibility error가 작아져서 발산하지 않는다는 장점이 있습니다. 또한 페널티 항들은 원래의 hamiltonian equation에 영향을 주지 않기 때문에, 9,10번 식은 원래의 운동방정식을 그대로 사용할 수 있습니다. 즉, algorithm 1에서 Hamiltonian만 augmented Hamiltonian으로 치환한 형태가 됩니다.
Discrete-Time Formulation
앞에서 정의한 PMP와 E-MSA를 이산시간 formulation으로 변환합니다. 운동방정식인 (1)번 식을 Euler-discretization을 한 후에 control problem(2)를 재정의하면
의 형태를 얻을 수 있습니다. 여기서 \delta는 T를 step-size로 나눈 discretization step에 해당합니다. 이산화된 운동방정식에서 \delta를 무시할 경우 residual network의 형태와 동일하기 때문에, 적절한 이산화 간격을 선택할 경우 E-MSA는 PMP를 이용한 residual neural network의 해라고도 볼 수 있습니다.
이산화한 운동방정식을 아래와 같이 g로 재정의하고, 이를 이용해서 각 layer의 discrete Hamiltonian을 나타냅니다.
그러면 PMP로부터 다음과 같은 필요조건들이 유도됩니다. (일반적으로 PMP가 이산시간운동방정식에 대해서도 성립하는지는 이산화간격을 어떻게 설정하는지와 관련있지만, 여기서는 실제로 '연속시간운동방정식을 이산화'한 것이 아니기 때문에, 고려하지 않아도 됩니다.)
이 시점에서 E-MSA의 monotonicity 증명에 대해서 다뤄야 하지만 미래에 하겠다고....(!)
E-MSA의 이산화된 버전은 다음과 같이 적용됩니다. 연속시간에서와 마찬가지로 Hamiltonian maximization step이 각 레이어마다 분리되기 때문에 병렬 연산이 가능한 것을 확인할 수 있습니다.
Gradient Descent and Back-propagation
문제 전체의 loss function
을 파라미터에 대해 편미분을 취하면 다음과 같습니다.
Algorithm 2에서의 update 부분을 (maximization이므로) learning rate \eta를 이용한 gradient ascent로
와 같이 나타낼 수 있는데, 이를 위의 식을 이용해서 치환하면
일반적인 gradient descent와 동일해지는 것을 확인할 수 있습니다. 연속시간에서 PMP와 MSA는 파라미터가 미분가능하지 않아도 수렴성이 보장되기 때문에, back-propagation의 일반화된 형태라고 볼 수 있습니다. 또한, PMP formalism을 이용하면 back-propagation이 costate equation에 의해서만 결정될 뿐, 파라미터에 따른 gradient와는 관련이 없기 때문에, optimization이 각 layer별로 독립적으로 이루어질 수 있습니다.
Mini-batch Algorithms
이 논문에서 전개한 수식들은 input x가 training input의 full set을 포함할 때 성립합니다. Mini-batch를 고려할 경우 Hamilton's equation은 변하지 않고, PMP는 다음과 같이 (각 batch에서의 hamiltonian들의 합을 최소화하는 theta로) 바뀌어야 합니다.
각 batch size m이 충분히 클 경우, mini-batch sum은 full-batch sum과 동일해지는 것으로 알려져 있습니다. 따라서 이 연구에서는 mini-batch version을 따로 구별하지 않습니다.
Experiment
수치적으로 간단한 예제를 실험하기 위해서, 5-layer network를 이용해서 sin(x) 함수를 근사하는 실험을 하였습니다. T=5, 이산화 간격은 0.25로 하여 20개의 layer를 설정하였고 각 layer는 5개의 노드를 가지고 있으며, tanh를 activation function으로 사용하였습니다. 1000개의 샘플을 이용하여 학습 후 SGD, Adam, Adagrad와 결과를 비교하였습니다.
그림에서 (a)는 weights는 std 0.1, bias는 constant 0.1로 초기화했을 때의 결과입니다. (b)에서는 weight랑 bias를 전부 0으로 초기화했을 때의 결과입니다. 모든 경우에서 E-MSA가 더 빠르게 수렴하며, 특히 초기화 값이 좋지 못한 경우에 다른 알고리즘에 비해 장점이 확연하게 드러나는 것을 확인할 수 있습니다. 특히 경사하강법은 flat이나 saddle-point 근처에서 굉장히 시간이 오래 걸리는 편인데, (b)에서 이러한 flat에서의 behavior를 확인할 수 있었습니다. 해당 지점 근처에서 Hessian의 eigenvalue를 확인해보자 해당 지점이 saddle point에 근접한 것을 확인할 수 있었습니다. 반면 E-MSA의 경우에는 flat region을 빠르게 탈출하여 minimum으로 수렴하는 것을 확인할 수 있는데, 그 이유로는 L-BFGS에서 사용하는 2nd-order 정보가 도움이 되는 것으로 생각됩니다.
다음으로는 MNIST dataset을 이용해서 실험한 결과입니다. 총 10개의 레이어를 사용하고 input, output을 copy하는 레이어 (projection layer)를 양단에 두면, fc layer 1개, residual layer는 7개이므로 discretization 간격은 0.5, T=3.5로 설정하였습니다. 마지막 레이어에서는 fully-connected + softmax + cross-entropy loss를 사용하였습니다. 이렇게 했을 때, 첫번째 레이어와 마지막 레이어는 residual form이 아니라는 문제가 있지만 altorighm 3에서 g를 조절함으로써 해결했습니다. convolution filter의 크기는 3*3, channel은 32를 사용했습니다. activation function은 마찬가지로 tanh를 사용했습니다. 사이즈 100의 mini-batch를 이용하였고, E-MSA에 대해서는 L-BFGS를 10 iteration 반복함으로써 Hamiltonian maximization을 풀었습니다.
(a)는 training epoch에 따른 loss, (b)는 training epoch에 따른 accuracy를 나타냅니다. 초기 epoch에서는 E-MSA가 훨씬 좋은 성능을 보이는 것을 확인할 수 있습니다.
다만 실제 시간(wall-clock basis)을 따져보면 E-MSA의 수렴이 확연히 느린 것을 확인할 수 있는데, 이는 E-MSA가 CPU에서 돌아가도록 구현이 되어 있기 때문이라고 합니다.
Share article