해당 게시물은 Standford 2017 CS231n 강의와 2022년 슬라이드를 바탕으로 작성되었습니다.

Last time: Activation Functions

• 지난시간에 Nerural networks를 학습 시킬 때 필요한 여러가지 중요한 것들을 배웠습니다.
• 다양한 Activation Function 과 각각의 특성이 존재했는데, 과거에는 sigmoid를 썼지만 Gradients Vanishing 문제때문에 요즘은 대부분 ReLU를 씁니다.

Last time: Weight Initialization

• Weight Initialization 에 대해서도 배웠습니다.
  • 가중치가 지나치게 작으면 activation이 사라지는데, 작은 값이 여러 번 곱해지기 때문에 점점 0이 되어, 결국 모든 값이 0이 되고 학습은 일어나지 않습니다.
  • 반면에 가중치가 너무 큰 값으로 초기화되면 그 값이 또 계속 곱해질 것이고 결국은 폭발합니다. 이 경우에도 학습이 일어나지 않을 것입니다.
• Xavier/MSRA(HE) Initialzation 같은 방법으로 초기화를 잘 시켜주면 Activation의 분포를 좋게 유지시킬 수 있습니다.
• 특히 Network가 깊어지면 깊어질수록 가중치를 더 많이 곱하게 되기 때문에 가중치 초기화와 활성함수는 더 중요합니다.

Last time: Data Preprocessing

• 여러가지 Data Preprocessing 기법이 있었고, image data는 주로 zero-mean을 주로 사용합니다.

• 왜 normalization가 중요한지에 대한 직관
• Linear Binary classification 문제(빨간/파란 점들을 나누는 것)를 푼다고 가정하겠습니다.
  • 왼쪽
    • not normalized/centered data 입니다.
    • classification 자체는 가능하지만, 선이 조금만 움직여도 classification이 잘 되지 않습니다.
    • 즉, 손실 함수가 아주 약간의 가중치 변화에도 엄청 예민합니다.
    • Loss가 파라미터에 너무 민감하기 때문에, 동일한 함수를 쓰더라도 학습 시키기 아주 어렵습니다.
  • 오른쪽
    • zero-center data, Unit variance 로 만들어 준 경우 입니다.
    • 선이 조금만 움직여도 손실 함수는 이런 가중치의 변동에 덜 민감합니다.
    • 이 경우 최적화가 더 쉬우며, 학습이 더 잘됩니다.

normalization은 Linear classification의 경우에만 국한되는 것이 아니라, Neural network 내부에도 다수의 linear classifer가 있다고 생각할 수 있는데, 이 경우 Neural network의 입력이 zero-centered가 아니고 Unit variance가 아닌 경우라면 레이어의 Weight matrix가 아주 조금만 변해도 출력은 엄청 심하게 변하게 됩니다. 이는 학습을 어렵게 합니다.

Last time: Batch Normalization

• Normalization이 엄청 중요하다는 것을 알고있기 때문에, batch normalization 도 배웠습니다.
• activations이 zero mean과 unit variance가 될 수 있도록 레이어를 하나 추가하는 방법이었습니다.
  • forward pass 시에 미니배치에서의 평균과 표준편차를 계산해서 Normalization을 수행했습니다.
  • 그리고 레이어의 유연한 표현성(expressivity)을 위해서 scale, shift 파라미터를 추가했습니다.

Last time: Babysitting Learning

• 학습 과정(Loss curve가 어떻게 보여야 하는지) 을 다루는 방법도 배웠습니다.
• 위 슬라이드를 해석해보면 Training set의 성능을 계속 올라가며 Loss는 계속 내려갑니다. 하지만 validation은 침체하고 있습니다.
  • 위 상황은 overfititing.
  • 추가적인 regularization이 필요합니다.

Last time: Hyperparameter Search

• hyperparameter search 도 배웠습니다.
• 네트워크에는 무수히 많은 하이퍼파라미터가 존재하며, 이를 올바르게 잘 선택하는 것은 상당히 중요합니다.
• grid search와 random search를 배웠으며, 이론상 random search가 더 좋았습니다.
  • 왜냐하면 성능이 특정 하이퍼파라미터에 의해 크게 좌우될 때 그 파라미터를 좀 더 넓은 범위로 탐색할 수 있기 때문입니다.
• 그리고 하이퍼파라미터 최적화 시에 coarse search 이후 fine search를 합니다.
  • coarse search
    • 처음에는 하이퍼파라미터를 가능한 최대한 넓은 범위를 설정해서 찾습니다.
    • 그 범위가 하이퍼파라미터 범위의 끝에서 끝까지 다 살펴볼 수 있도록 할수록 좋습니다.
    • Interation도 작게 줘서 학습시켜봅니다.
    • 그리고 결과가 좋은 범위로 좁히는 것입니다.
  • fine search
    • iterations를 조금 더 돌면서 더 작은 범위를 다시 탐색합니다.
  • 적절한 하이퍼파라미터를 찾을 때 까지 이 과정을 반복합니다.

Gradient descent for optimization

• Fancier optimization을 살펴보기전에 Gradient descent를 다시 짚어보고, 문제점을 살펴보겠습니다.
• 이전에 Loss function에 대한 정의 및 역할이 제시 되었습니다.
  • 최적의 $W$ 를 찾아서 classifier가 이미지들을 잘 분류하고 있는지 검사를 해야하는데, 즉, $W$ (weight)가 좋은지 아닌지 정량화 할 수 있는 기준이 필요했기에 Loss function이 등장했습니다.
  • 손실 함수(Loss Function)는 현재 분류기(classifier)가 얼마나 좋은지를 알려줍니다. 다르게 표현하면 현재의 $W$ 가 얼마나 BADNESS한지 를 알려주는 것입니다.
• 기존의 Loss function은 문제점을 가지고 있었습니다.
  • training data에 대해 좋은 성능을 만들려고 합니다.
  • 하지만 우리가 원하는것은 test data에 대한 일반화입니다.
• 이러한 문제점은 Overfiiting으로 이어집니다.
  • 즉 모델이 training data에 대해서만 잘 수행하고, unseen data에 대해 낮은 성능을 보이는 현상입니다.
• Overfitting을 방지하기 위해 Data loss term에 Regularization term을 추가하였습니다.
  • 즉, Simpler Models을 선호하게 하여 Overfit을 방지합니다.
  • 일반적으로 L2 regularization를 사용합니다.
  • 더 복잡한 regularization은 Dropout, Batch normalization, Cutout, Mixup, Stochastic depth 등등 여러가지 방법론이 존재합니다.

정리하면, nice(좋은)한 $W$를 찾기 위한 Loss function은 training data에 맞는 Data Loss과 Overfitting을 방지하기 위한 regularization으로 구성됩니다.

• 그리고 최종적으로 $L(W)$ 함숫값을 최소화하는 최적의 W를 구하는 것이 목적입니다.
• 따라서, 최적의 $W$ 는 $W^*\ =\ argmin_wL(W)$ 의 식으로 구합니다.
  • argmin : minimizer
  • $L(W)$를 최솟값으로 만드는 $W$를 $W^*$로 정의합니다.

• 그렇다면 이 $W_*$ 를 어떻게 찾을까?
  • 최적의 $W$ 값을 찾기는 어렵습니다. 하지만 찾고자 하는 방법으로 2가지가 있습니다.
    1. Random search
    2. slope를 따라내려가는 방법
  • Random search는 랜덤으로 $W$ 값의 후보를 정해서 함숫값을 구하는데, 즉, 매번 $W$ 를 조금씩 개선시켜 loss를 낮추고자 하는 것입니다.
    • 좋은 방법이 절대 아니며, 성능또한 좋지 않고, 차원의 저주에 빠질 수 있습니다.
• 위 질문은 gradient descent 로 이어집니다.
  • $L(W)$ 는 주로 전체 개형을 알 수 있는 함수가 아닙니다.
  • 개형은 알지 못하고, $W=W0$ 라는 점이 주어졌을 때 그 근접한 곳만 알 수 있습니다.
  • 여기서 할 수 있는 방법으로 slope를 따라내려가는 방법 이 있습니다.
    • 경사를 따라내려가는 방법은 곧 함수에서의 derivative(미분)를 따라가는 것입니다.
    • 그래디언트의 기하학적 의미: 그래디언트 방향은 함수가 가장 증가하는 방향.
    • 다르게 이야기하면, 그 점에서 loss function이 가장 감소할 수 있는 방향을 의미하며, 따라서 negative gradient의 방향으로 점점 가면 최소점에 도달할 것 입니다.
• 그렇다면 함수의 개형을 알지 못하는 상황에서 어디가 최적점인지 어떻게 알 수 있을까?
  • 그냥 내려가봐야 합니다.
  • 그래디언트를 구해서 함수가 감소하는 방향으로 가는 것이 절대 전체적인 최적의 global minimum으로 가는 것을 보장하지는 않습니다.
  • 즉, 전체 shape에 대해 전혀 알지 못하지만, 내리막길을 따라가면 낮은 곳으로 가게 될 것이라고 믿습니다.(최적점인지에 대한 확신은 없습니다.)

• 즉, 그래디언트 계산법에는 2가지가 있습니다.
  • 수치적 그래디언트: 근삿값을 계산하며, 계산이 느리지만, 쓰기 쉽습니다.
  • 해석적 그래디언트: 정확한 값을 계산하고, 빠르지만, error가 발생하기 쉽습니다.
• 실제로 그래디언트를 계산할때는, 항상 해석 그래디언트를 활용하면서 **gradient check를 거칩니다.

(Full-Batch)Gradient descent

• $L(W)$ 의 가장 낮은 점(최적점, global minimum)을 향해서 가는 방법 중 gradient negative한 방향을 따라가는 알고리즘인 Grdient descent 를 소개합니다.
• Gradient descent는 negative gradient 방향으로 이동하면서, 계속해서(t=0, 1, 2, . . .반복) $W$ 값을 update시키는 방법 입니다.
• 위의 간단한 알고리즘은 우리가 initialized_weights를 통해 아무데서나 시작하고 고정된 num of iteration (num_steps)만큼 루프를 반복하며 매 step마다 현재 위치의 gradient를 계산하고 negative gradient direction으로 조금씩 이동하게된다는 코드입니다.
• Gradient descent를 구현할 때 필요한 hyperparameter 로 다음과 같습니다.
  • Weight 초기값을 설정하는 방법: 초기값이 어디냐에 따라 수렴하는 위치가 달라집니다.
  • 얼마나 반복할 것인지: steps의 수가 너무 크면, 시간이 소요되고, 너무 작으면, 충분히 내려가기전에 알고리즘이 끝날 수 있기때문에 적당히 설정하는 것이 중요합니다.
  • Learning rate: 크게 설정하면, 너무 넓게 뛰어, 오히려 loss값이 높은 곳으로 갈 수 있고, 작게 설정하면 최적점까지 가는 step이 너무 오래 걸립니다.
• 위 슬라이드의 우측 이미지는 Gradient descent의 기하학적인 해석입니다.
  • 현재 $L(W)$ 함수의 형태는 2차원 convex함수로, Negative gradient방향을 따라 이동하면서 $W$ 를 update시키면 optimal로 갈 수 있습니다.

(mini-Batch)Stochastic Gradient descent

• 지금까지 설명한 Gradient Descent방식은 모든 트레이닝 데이터를 계산에 활용하는 Full-Batch Gradient Descent입니다.
• Training data 사이즈가 매우 크다면, 파라미터 W를 한 번 update하기 위해 모든 트레이닝 데이터를 활용하는 것은 비용측면에서 효율적이지 못합니다.
• Full-batch GD방법은 시간이 너무 오래 걸리기때문에, 트레이닝 셋의 모든 N개를 실행하지않고, 트레이닝셋에서 샘플을 랜덤으로 추출하여 실행하는 Stochastic Gradient Descent(SGD) 방법을 주로 활용합니다.
  • 트레이닝셋에서 랜덤으로 추출한 것을 미니배치라고 부르며, 미니배치 사이즈는 주로 32, 64, 128개로 정합니다.
• SGD를 활용하면 미리 정해야 할 hyperparameter 가 더 늘어납니다.
  • Weight 초기값을 설정하는 방법
  • 얼마나 반복할 것인지
  • Learning rate
  • Batch size: 미니배치의 사이즈
  • Data sampling: 데이터 샘플링하는 방법

원래 Stochastic Gradient descent는 mini-batch를 사용하는 것이 아닌 전체 training set에서 랜덤하게 뽑은 단 1개의 데이터의 gradient를 계산하고 weight update시키는 방식을 training set 크기만큼 반복하는 것이라 이러한 random성 때문에 stochastic이라는 이름이 붙은 것 입니다. 하지만 mini-batch gradient descent가 굉장히 보편화되며 SGD라는 용어가 mini-batch gradient descent를 의미하는 경우가 많아졌습니다.

• SGD에서는 loss function을 확률론적으로 접근하기 때문에 stochastic 이라는 이름이 붙여졌습니다. 우리가 data set을 확률분포로 부터 샘플링된 것으로 생각했을때 우리는 loss function을 모든 가능한 sample들에 대한 expectation으로 생각할 수 있으며, 수식과 같이 표현 할 수 있습니다.
  • mini-batch 데이터는 임의의 확률분포 $P$ 를 따르는 확률변수 $X$, $Y$ 를 따릅니다.
  • $∇_WL(W)$ : 우리가 모르는 $P$ 라는 분포에서 N개의 데이터를 샘플링했을 때, 그 샘플링된 데이터에서 그래디언트를 계산하여 모집단 평균 그래디언트를 sample 평균 그래디언트로 근사합니다.

Optimization

• 즉 Neural network에서 가장 중요한 것 은 바로 Optimization Problem 입니다.
  • Nerwork의 가중치에 대해서 Loss function를 정의해 놓으면 이 Loss function은 그 가중치가 얼마나 좋은지 나쁜지를 알려줍니다.
  • 그리고 Loss function이 가중치에 대한 “산(landscape)”이라고 상상해 볼 수 있습니다.
• 오른쪽 이미지인 2차원의 문제를 두 개의 가중치 W_1과 W_2를 최적화 시키는 문제라고 생각해봅니다.
  • X/Y축은 두 개의 가중치를 의미하며, 각 색깔은 Loss의 값을 나타냅니다.
  • 우리의 목적은 가장 붉은색인 지점을 찾는 것입니다. 즉 가장 낮은 Loss를 가진 가중치를 찾는 것 입니다.

가장 간단한 최적화 알고리즘인 Stochastic Gradient Descent를 이용해 미니 배치 안의 데이터에서 Loss를 계산하고, “Gradient의 반대 방향”을 이용해서 parameter vector를 업데이트합니다. 이 단계를 계속 반복하면 결국 붉은색 지역으로 수렴할 것이고 Loss가 낮아질 것입니다.

정리하면, Optimization 은 업데이트(학습)를 통해 손실함수(Loss function)의 가장 낮은 곳의 $W$ 값 까지 도달하는 것이 목표 이고, 이것을 어떻게 가장 효율적인 방법으로 도달할 수 있느냐에 대한 방법론 입니다.

Optimization: Problem #1 with SGD

• 하지만, Stochastic Gradient Descent에는 Poor conditioning 문제점 이 있습니다.
  • 위 슬라이드와 같이 가로 방향으로 긴 형태(like taco shell)의 손실함수에서는, 가로 축으로의 이동보다 세로 축으로의 이동이 더욱 큰 영향을 주게 됩니다.
    • 이 경우, loss function의 경사가 수직 방향으로의 gradient는 매우 크고, 수평 방향으로의 gradient는 매우 작아, 수평 축의 가중치는 변해도 Loss가 아주 천천히 줄어듭니다.
  • 즉, 수평 방향의 가중치(W_1)가 변하더라도 Loss는 아주 천천히 줄어들기 때문에, 수평 방향의 가중치(W_1)보다 수직 방향의 가중치(W_2) 변화에 더욱 민감하게 반응할 것 입니다.
  • 즉 업데이트가 잘 안되는 경우이며, 이를 poor conditioning 라고 부른다.
• 현재 지점에서 Loss는 bad condition number를 지니고 있다 고 말할 수 있습니다.
  • condition number : 입력값의 작은변화에 대한 출력값의 변화의 정도를 측정하는 지표로 시스템이 민감한 정도를 정량적으로 보여주는 값을 뜻합니다.
  • 즉 이 지점의 Hessian maxrix의 최대/최소 singular values값의 비율이 매우 안좋다는 뜻입니다.
  • 즉, $∇^2L(W)$ 의 $\frac{largest\ eigenvalue}{smallest\ eigenvalue}$
  • ex. $L(W) = \frac{W_1^2}{64} + W_2^2$
  • $∇^2L(W) = \begin{bmatrix} \frac{1}{32} & 0 \\ 0 & 2 \end{bmatrix}$
  • condition number = $\frac{2}{\frac{1}{32}} = 64$

• 이런 상황에서 SGD으로 학습이 되는 모습을 생각해볼때, gradient의 방향이 고르지 못하기 때문에 위 그림과 같이 지그재그로 수렴하는 형상 을 띄게 됩니다.
  • 즉 step에 따른 Weight of matrix 의 변화가 zigzag pattern or 지저분하게(nasty) 보이며 변화 할 수 있습니다.
  • 이는 바람직하지 않으며, 더 많은 step이 소요되며, 고차원의 공간에서 주로 발생합니다.
  • 또한 이 때문에 SGD는 Full Batch보다 Overshoot문제에도 더 취약합니다.
• 위의 예에서는 단순히 2차원이지만, 실제로는 가중치가 수억개일 수 있습니다.
  • 이때는 수억개의 방향으로의 불균형한 방향이 존재할 수 있으며, 수억개의 방향으로 움직일 수 있으므로, SGD는 잘 동작하지 않을 것입니다.
  • 고차원 공간에서 발생하는 이런 문제는 실제로도 큰 문제가 됩니다.

Optimization: Problem #2 with SGD

• SGD의 또다른 문제는 Local Minima 와 Saddle Point 입니다.
  • Local minima 는 업데이트 중에 작은 valley를 만나 gradient가 0이 되어 학습을 멈추게 되는 문제 입니다.
    • 즉, global minimum point가 아닌 local minimum point 입니다.
  • Saddle point 는 gradient가 0이 되는 지점에서 학습을 멈추는 문제 입니다.
    • 즉, 최적이 아닌 위치에서 그래디언트 값이 0이 되면, 여기에 갇혀서 더 이상 W값이 업데이트 되지 못 합니다.
• 위 그림과 같이 1차원의 예에서는 local minima가 더욱 심각해 보이지만, 고차원 공간에서는 그 반대입니다.
  • 고차원 공간에서 Saddle point는 어떤 방향은 loss가 증가하고 몇몇 방향은 loss가 감소하고 있는 지점으로 생각할 수 있는데, 수억차원에서 생각해보면 이는 거의 모든 곳에서 발생한다고 할 수 있습니다.
  • 반면, 고차원 공간에서 local minima는 수억개의 방향을 계산했는데 이 방향이 모두 loss가 상승하는 방향인 경우이므로, 매우 드물게 발생합니다.
• 즉 매우 큰 규모의 신경망 모델 에서는 local minima보다 saddle point에 더욱 취약 한 것으로 알려져 있습니다.
  • Saddle point에서 gradient가 0이 되는 것도 있지만, saddle point 근처에서 gradient가 아주 작아지기 때문에 업데이트가 느려져서 문제가 됩니다.

• 또한, SGD에서(데이터의 크기가 매우 커서) mini-batch로 gradient를 계산할때 small estimate of full data set만을 사용하기 때문에 모든 step에서의 gradient가 minima로 향하는 올바른 direction과는 상관관계가 없기에 그림에서 볼 수 있듯이 noisy estimate 합니다.
  • 이는 mini-batch의 데이터만으로 실제 loss와 gradient를 추정하는 것입니다.
  • 즉 매번 정확한 gradient를 얻을 수가 없다는 것을 의미 하며, 부정확한 추정값(noisy estimate)인 gradient를 얻게 된다는 문제 가 있습니다.
• 따라서, 위 슬라이드의 오른쪽 그림과 같이 손실함수 공간을 비틀거리면서 minima로 수렴하기 때문에 학습 시간이 오래걸리게 됩니다.

Next Optimizer

• 이러한 SGD의 여러가지 문제점을 해결하기 위해 여러 개의 optimizer들이 차례로 등장하게 됩니다.
• 개선된 optimizer들은 각각의 특징들이 있는데, 크게 방향을 중심 으로 하느냐, 보폭을 중심 으로 하느냐로 나뉩니다.
• 지금부터 SGD를 개선한 optimizer를 살펴보겠습니다.

SGD + Momentum

• SGD의 여러 문제점들을 해결하는 간단한 방법은 SGD에 momentum term 을 추가하는 것입니다.
• SGD + Momentum의 아이디어는 단순히 velocity를 유지하는 것 입니다.
  • 즉, 현재 mini-batch의 gradient 방향만 고려하는 것이 아니라 velocity도 같이 고려하여, gradient descent가 되는 과정에서 생기는 속도(velocity)를 어느 정도 유지하자는 의미 입니다.
  • $ρ$ : momentum의 비율(velocity의 영향력) or 속도(velocity)를 얼마나 고려할 것인가의 비율을 나타냅니다.
    • 보통 0.9 or 0.99 로 설정합니다.
  • $V_t$ : velocity
• 즉, Momentum 최적화는 이전 gradient가 얼마였는지를 상당히 중요하게 생각 합니다.
  • Momentum의 핵심 idea는 weight를 업데이트 할 때 이 전에 계산한 gradient도 반영을 해주자는 것으로 다르게 말하면, $V_t$ (현재 속도)에 그래디언트가 누적되면서, 과거의 그래디언트는 점점 잊혀지는 알고리즘입니다.
  • 식을 살펴볼때, 매 스텝마다 gradient가 동일한 부호를 가지면 v의 절댓값은 계속 증가할 수 밖에 없습니다. v가 증가함에 따라 x의 변화폭이 커지고, 이는 즉 같은 방향으로 이동할수록 더 많이 이동하게 하여 가속화한다는 말 과 같습니다.
  • 그래서 local minima나 saddle point에서 gradient가 0이라 하더라도, 이전 step에서 축적되어온 v값이 더해지면서 멈추지 않고 이동할 수 있습니다.

• SGD + Momentum은 정해진 방법으로만 사용하는 것이 아니라 세부 구현은 약간씩 다를 수 있습니다.

• SGD + Momentum은 다음과 같은 본 SGD의 문제들을 해결 할 수 있습니다.
  • Local minima와 saddle point 문제
    • 위 슬라이드의 왼쪽 위 그림에서, 빨간색 공은 local minima나 saddle point에 도달하더라도 여전히 velocity를 가지고 있기 때문에 gradient가 0이더라도 계속해서 나아갈 수 있습니다.
  • Poor conditioning 문제
    • 위 슬라이드의 왼쪽 아래 그림에서, 지그재그로 수렴하는 움직임도 momentum을 통해 상쇄할 수 있기 때문에 민감한 수직방향의 변동은 줄어들고 수평방향의 움직임은 점차 가속화 됩니다.
  • Gradient Noise 문제
    • 위 슬라이드의 오른쪽 그림에서, 파란색 선은 Momentum이 추가된 SGD이고 검정색 선은 그냥 SGD입니다.
    • Momentum항이 추가되면 noise를 평균내버려서 그냥 SGD보다 더 smooth하게 수렴하게 됩니다.

Nesterov Momentum

• 좌측 슬라이드는 SGD + Momentum이 나아가는 형태를 직관적으로 보여줍니다.
  • Momentum 업데이트는 현재 지점까지 그동안 누적되어온 velocity와 gradient값이 더해져서 실제 step을 이루는 방식이었습니다.
  • 실제 업데이트는(autual step) 현재 지점에서의 gradient의 방향과 Velocity vector의 가중평균으로 구할 수 있습니다. 이는 gradient의 noise를 극복할 수 있게 해줍니다.
• 우측 슬라이드는 Nesterov Momentum 으로, 앞에서 살펴본 momentum을 추가하는 방식의 변형입니다.
  • NAG(Nesterov Accelerated Gradient) 라고도 부릅니다.
  • 원점에서 구한 gradient와 velocity를 더하는 SGD+Momentum와 달리, Nesterov는 원점에서 velocity를 구한 다음 velocity의 지점에서 gradient를 계산하고 다시 본래 자리로 돌아와 actual step을 나아가는 형태 입니다.
    • 이 방법은 velocity의 방향이 잘못된 경우에 현재 gradient의 방향을 활용하여 좀 더 올바른 방향으로 가게하는 것으로 이해할 수 있습니다.
    • 즉 누적된 과거의 gradient가 가리키는 방향을 현재 gradient에 보정하는 효과를 가지게 됩니다.
  • Nesterov Momentum은 convex optimization에서는 뛰어난 성능을 보이지만, neural network와 같은 non-convex problem에서는 성능이 보장되지 않습니다.

• 위 슬라이드는 Nesterov Momentum을 구하는 식입니다.
• 위쪽 검은색 박스의 파란색 박스 식을 보면, gradient를 한 지점에서 구하지 않는 것을 확인할 수 있습니다. 이러한 형태는 까다로우므로, 변수를 적절히 바꿔주어 아래쪽 검은색 박스의 식과 같이 gradient를 한 지점에서 구하는 식으로 다시 나타낼 수 있습니다.
• 아래쪽 검은색 박스의 식으로부터 Nesterov는 다음과 같이 동작합니다.
  • $v_{t+1}$ 은 Vanilla SGD+Momentum과 같이 velocity와 gradient를 일정 비율로 섞어 준 것으로 이해할 수 있습니다.
  • $\tilde{x}_{t+1}$ 는 마지막 식의 형태만 보면 됩니다.
    • 이전 위치와 현재의 velocity를 더한 값에 현재와 이전의 velocity 차이에 일정 비율 $\rho$ 를 곱한 값을 더해주며 구하게 됩니다.
• 따라서, Nesterov는 현재와 이전의 velocity간 error-correcting term(에러 보정 항)이 추가된 것으로 이해 할 수 있습니다.

• 위 슬라이드는 SGD, Mementum, Nesterov의 움직임을 나타낸 것으로, SGD+Momentum과 Nesterov는 빠르게 수렴 하는데 반해 SGD는 느리게 수렴 합니다.
• 또한, SGD+Momentum과 Nesterov는 velocity 때문에 minima를 지나친 후, 다시 경로를 틀어 minima로 수렴하는 형태 를 보입니다.
  • SGD+Momentum과 Nesterov는 아주 좁고 깊은 minima를 지나칠 수 있습니다. 하지만, 그러한 minima는 아주 overfit된 경우이기 때문에 test data에서 좋은 일반화 성능을 보이는 지점이 아닙니다.
  • 따라서, 위 슬라이드 그림과 같이 넓고 평평한 지점에서의 minima를 찾는 것이 우리의 목적이며, 좁고 깊은 minima를 건너뛰면서 우리가 원하는 minima를 찾는데 momentum 방법들이 도움이 된다는 것도 좋은 점이라고 볼 수 있습니다.

AdaGrad

• 또다른 최적화 방법으로 AdaGrad 가 있습니다.
• AdaGrad는 Adaptive Gradient를 뜻하며, gradient descent가 되는 정도를 상황에 맞게 조정하는 것 입니다.
  • 조금더 엄밀히 말하면, 이전의 learning rate가 일괄적으로 적용되고 있어 overshooting 되었던 문제를 learning rate를 가변적으로 적용하여 해결하고자 합니다.
  • velocity term 대신에 grad squared term을 이용합니다.
  • 이 방법은 학습 중에 계산되는 모든 gradient의 제곱을 계속해서 누적합시켜 더해갑니다. 그리고 gradient를 루트를 취해 나눠준 값으로 업데이트 하여 step마다 learning rate를 가변적으로 적용하는 방법입니다.
    • 이는 기울기가 가파를수록 조금만 이동하고, 완만할 수록 조금 더 이동하게 함으로써 변동을 줄이는 효과가 있습니다.
    • 또 행렬곱 연산을 통해 가중치마다 다른 학습률을 적용한다는 점에서 더욱 정교한 최적화가 가능 해집니다.
• 즉, 학습이 진행됨에 따라 gradient의 제곱이 계속 커질 것이고, 업데이트 되는 gradient는 점점 작아지는 것입니다.

• 위 슬라이드의 그림에서, gradient를 가로, 세로 축으로 생각하고 AdaGrad의 동작을 이해해보면 다음과 같습니다.
  • 가로 축으로는 gradient가 항상 작고, 세로 축으로는 gradient가 항상 큽니다. 따라서, 제곱해서 더해지는 항이 가로 축에서는 작을 것이고, 세로 축에서는 클 것입니다.
    • y축 방향(“steep”): grad_square is big
      • 따라서 grad_square로 나누면, 가려던 방향으로 원래 가려던 것보다 덜 갑니다.
    • x축 방향(“flat”): grad_square is small
      • 따라서 grad_square로 나누면, 가려던 방향으로 원래 가려던 것보다 더 갑니다.
  • 이로 인해, 세로 축 방향으로의 움직임에서는 gradient가 큰 값으로 나누어 진행을 약화시키고, 가로 축 방향으로의 움직임에서는 작은 값으로 나누어 accelerating motion 효과를 줍니다.
  • 따라서, 중앙 지점까지 가로축 세로축 모두에서 적절한 속도로 수렴하게 되는 것입니다.
• 하지만, AdaGrad는 Step을 진행할 수록, 계속해서 값이 작아진다는 문제 가 있습니다.
  • Convex case에서는 minimum에 근접하면서 속도를 줄일 수 있기 때문에 좋은 방법이지만, Non-convex case에서는 saddle point에 걸렸을 때, 더이상 진행하지 못하기 때문에 좋은 방법이 아닙니다.
• 또한 non-covex problem 경우에서 학습이 길어질 경우, 기울기가 0인 부근에서 학습이 급격하게 느려져, 학습 속도가 점점 줄어들어 결국 멈추어버린다는 문제점 도 있습니다.
• 따라서, Neural Network를 학습시킬 때에는 AdaGrad를 잘 사용하지 않습니다.

RMSProp: “Leaky AdaGrad”

• RMSProp 은 AdaGrad의 앞선 문제점을 개선시킨 최적화 방법으로 Leaky AdaGrad라고 합니다.
  • AdaGrad는 과거 정보를 계속 누적하는 반면
  • RMSProp은 과거 정보를 조금씩 축소시켜서 받아들입니다.
• AdaGrad에서처럼 제곱 항을 그냥 누적하지 않고, decay_rate를 곱해서 누적하는 형태로 문제점을 개선하였습니다.
  • 누적된 gradient 값에 decay rate를 곱해주고, 현재 gradient의 제곱값에 1 - decay rate를 곱하여 누적해서 더해줌으로써 아주 미세하게(leaky) step size를 조절 할 수 있게 되었습니다.
  • 이때, decay_rate는 주로 0.9나 0.99를 사용합니다.
  • 이전 스텝의 기울기를 더 크게 반영하여 h 값이 단순 누적되는 것을 방지할 수 있습니다.
• 즉, RMSProp은 gradient의 제곱을 나눠준다는 점은 동일하지만, 속도가 줄어드는 문제는 해결한 형태 라고 볼 수 있습니다.
  • 보폭을 갈수록 줄이되, 이전 기울기 변화의 맥락을 살피자는 것입니다.

• 위 슬라이드는 SGD, SGD+Momentum, RMSProp을 비교한 것입니다.
• SGD+Momentum은 한번 overshoot 한 뒤에 다시 minima로 수렴하는 궤적을 그리지만, RMSProp은 각 step마다 각 차원의 상황에 맞도록 적절하게 궤적을 수정하면서 수렴하는 형태 를 보입니다.

Adam(Adaptive moments) = RMSProp + Momentum

• Adam 알고리즘 은 RMSProp과 Momentum이 합쳐진 개념으로 보폭도, 방향도 적절하게 조절하는 optimizer 라고 생각할 수 있습니다.
• 위 슬라이드의 식은 완전한 Adam은 아니지만, Adam의 컨셉을 나타낸 것입니다.

• Momentum에서 과거 velocity와 현재의 gradient를 더해서 나아가는 방식을 차용 합니다.
• 과거의 정보는 조금씩 잊으면서, 현재 점에서의 새로운 그래디언트로 보강하여 $W$ 를 업데이트합니다.

• AdaGrad와 RMSProp에서는 gradient를 제곱하여 과거의 정보를 누적하면서 $W$ 를 업데이트시에 가려던 방향으로 나눠주는 방식을 차용 합니다.
• (과거는 축소시키면서) dw의 제곱값을 누적시키고, 분모로 moment2 값을 사용하여 $W$ 를 업데이트합니다.

• 하지만, 문제가 있습니다. 만약 Beta2가 0.999일때, 초기 step에서 어떤 일이 발생할지 생각해봅니다.
  • moment2 는 처음에 0으로 초기화 됩니다. 그리고 beta2(decay_rate에 해당)도 보통 0.9 ~ 0.99의 값을 가지므로 및 (1 - beta2) * dx * dx 항도 0에 가까울 것입니다. 따라서, moment2 는 처음에 1번 업데이트 한 이후에도 여전히 0에 가깝게 됩니다.
  • 이로 인한 문제는 바로 다음의 업데이트 단계에서 일어나는데, 매우 작은 moment2 로 나누게 되어 초기 step이 매우 커지게 되는 문제인데, 이는 한번 발생하면 매우 나쁜 상황이 됩니다.
  • 매우 커진 초기 step으로 인해 초기화가 엉망이 될 것이고, 전혀 엉뚱한 곳으로 이동하게 될 수도 있습니다. 이는 수렴할 수 없는 현상을 초래하기도 하므로 매우 좋지 못합니다.
• 위 수식에서는 moment1, moment2 둘 다 0 에 수렴하기 때문에 상쇄될 수도 있지만, 상황에 따라 엄청 큰 step size가 발생하는 경우도 있어서 아주 큰 문제가 됩니다.
• 따라서 실제 Adam 에서는 moment1와 moment2에 bias correction term을 추가 해 이것을 보정합니다.

• 위 슬라이드는 완전한 형태의 Adam입니다.
• 앞에서 살펴본 (완전하지 않은) Adam은 초기 step이 매우 커질 수 있다는 문제가 있었습니다. 따라서, 실제 (완전한 형태의) Adam은 이를 해결하기 위해 보정하는 항(bias correction term)을 추가한 형태 입니다.
• 위 식을 하나씩 살펴보면 다음과 같습니다.
  • 먼저, moment1와 moment2를 업데이트 합니다.
  • 그리고 t(현재 step)에 맞는 적절한 unbiased term(moment1_unbiased과 moment2_unbiased)을 계산합니다.(앞에서의 문제를 해결하기 위해 추가된 부분)
  • 마지막으로, 앞서 구한 unbiased term을 통해 업데이트를 수행합니다.
• 즉, (완전한 형태의) Adam은 moment1와 moment2만 계산하는 것이 아니라, unbiased term을 계산해서 동작하는 것입니다.
• Adam은 다양한 문제들에서 잘 동작하기 때문에 아주 좋습니다.
  • 특히, beta_1 = 0.9, beta_2 = 0.999, learning_rate = 1e-3, 5e-4, 1e-4 정도로만 설정하면 거의 모든 모델에서 잘 동작하는 기본 설정이 될 수 있습니다.

• 동일한 환경에서 SGD, Momentum, RMSProp, Adam을 비교한 그림입니다.
• Adam의 궤적은 SGD+Momentum과 RMSProp의 궤적을 절충한 형태로 그려집니다.
  • overshoot하기는 하지만 SGD+Momentum보다는 정도가 약합니다.
  • RMSProp처럼 각 차원의 상황에 맞도록 적절하게 궤적을 수정하면서 step을 이동합니다.

Optimization Algorithm Comparison

• 지금까지 소개한 최적화 알고리즘들을 비교하겠습니다.
  1. 첫번째의 속도를 추적할 수 있는가?
     • SGD+Momentum, Nesterov, Adam
  2. Elementwise하게 곱해서 제곱term을 보관하는가?(너무 많이 간 방향으로는 많이 가지 못하게 보정)
     • AdaGrad, RMSProp, Adam
  3. 과거를 잊고있는가?
     • RMSProp, Adam
  4. 처음 가려는 방향(초기step)에 대해 너무 느린 것을 보정하는가?
     • Adam

Learning Rate Schedules

• 이전에 보았던 모든 optimization기법들은 learning rate 를 hyperparameter로 가지고 있었습니다. 이것은 deep learning model에서 가장 중요한 우선순위의 hyperparameter로 다루어지고 있습니다.
• 학습 과정에서 learning rate을 하나의 값으로만 정해놓는다면, 좋은 값을 설정하기가 어렵습니다. 그렇다면 “어떻게 최적의 learning rate를 찾아야할까?” 라는 질문에, Learning rate decay 가 좋은 전략이 될 수 있습니다.
  • training 초반에는 green line을 따르는 high learning rate을 사용하여 빠르게 학습시켜야하고, 시간이 지남에 따라 blue line을 보이는 low learning rate로 learning rate를 decay 시키는, 즉 red line을 따르는 것이 이상적인 방법입니다.
• Learning rate decay는 처음에 learning rate을 높게 설정한 후, 학습이 진행될수록 learning rate를 점점 낮추는 방법이며 다음의 두가지 방법 이 있습니다.
  1. 특정 순간마다 learning rate을 감소시키는 방법입니다.
     • 예) Step decay : 몇번의 epoch마다 learning rate을 감소시킵니다.
  2. 꾸준히 learning rate을 감소시키는 방법입니다.
     • 학습 동안에 꾸준히 learning rate을 감소시키는 방법입니다.
     • 예) exponential decay와 1/t decay : 위 슬라이드의 식 참고
     • 꾸준히 learning rate을 감소시키는 방법에는 다양한 전략이 있을 수 있습니다.

• 위 슬라이드는 ResNet 논문에 있는 학습 그래프로, 화살표로 표시된 지점은 step decay가 적용되어 learning rate가 줄어든 지점입니다.
• learning rate가 decay되어야 하는 순간 은 다음과 같습니다.
  • 현재 수렴을 잘 하고 있는 상태에서 gradient가 작아졌고, learning rate가 너무 높아서 더 깊게 들어가지 못하는 상태(bouncing around too much) 에 decay가 되어야 합니다.
  • 이때, learning rate를 낮추게 되면 속도가 줄어들어 더 깊게 들어가며 loss를 낮출 수 있습니다.
• Learning rate decay와 관련된 추가적인 내용들
  • Learning rate decay는 Adam보다 SGD Momentum을 사용할 때 자주 사용합니다.
  • Learning rate decay는 두번째로 고려해야 하는 하이퍼파라미터입니다.
    • 학습 초기에는 learning rate decay를 고려하지 말고 learning rate 자체를 잘 선택해야 합니다. 그 이유는 초기 learning rate와 decay를 cross-validate하려고 하면 너무 문제가 복잡해 지기 때문입니다.
    • 따라서, Learning rate decay를 적용할 때에는 먼저, decay 없이 학습을 시도하고, loss curve를 살펴보면서 decay가 필요한 곳이 어디인지 고려해서 사용해야 합니다.
• 이렇게 training process동안 시간이 지남에 따라 learning rate를 변경시키는것을 learning rate schedule 이라고 합니다.

Learning Rate Decay: Step

• Learning rate를 decay시키는 방법인 Step 방법으로, noncontinous하게 decay시키는 방법입니다.
  • 일정 범위의 epoch마다 discrete value를 learning rate로 사용하고 점차 decay시켜 계단모양의 learning rate를 보이게 되는 decay schedule입니다.
• 어떤 고정된 지점들에서 learning rate를 낮추는 것 입니다.
  • 예를 들면, ResNet에서는 epoch가 30씩 지날때마다, LR를 0.1씩 곱해서 감소시킵니다.
• step learning rate schedule은 step마다 learning rate를 고정시킬 epoch의 범위, step마다 learning rate 를 감쇠시킬 decay rate가 새로운 hyperparameter로 추가되는 문제가 있습니다.

Learning Rate Decay: Cosine

• 다음은 Cosine 방법으로, continous하게 decay시키는 방법입니다.
• Step learning rate schedule과는 달리 decay rate나 epoch의 범위를 설정해 줄 필요 없이 위 그림의 공식을 따라 매 epoch마다 learning rate을 decay시키게 됩니다.
  • T는 training하는 전체 epoch의 수, t는 현재 epoch, $\alpha_0$ 은 사전 지정이 필요한 hyperparameter입니다.
  • 사전에, $alpha_0$과 T만 지정하면, epoch가 지남에 따라 LR이 감소하며, loss도 smooth하게 감소합니다.
• tuning해주어야 할 hyperparameter가 적기 때문에 최근에 많이 사용된다고 합니다.

Learning Rate Decay: Linear

• 다음은 Linear 방법으로, continous하게 decay시키는 방법입니다.
• 직선의 형태로 learning rate가 감소합니다.
  • 기울기로 활용할 $alpha_0$ 와 T가 hyperparameter로 필요합니다.
• linear learning rate schedule은 간단하지만 자주 사용되며 각 model마다, 각 problem마다 사용하는 learning rate schedule은 다르며, 이런 learning rate schedule들은 어느게 좋은지 비교할 수는 없습니다.
  • computer vision 분야에서는 Cosine learning rate decay schedule 을 많이 사용합니다.
  • large-scale netural language processing 에서는 linear learning rate schedule 을 많이 사용합니다.

Learning Rate Decay: Inverse Sqrt

• 다음은 Inverse Sqrt 방법으로, LR를 초반에 빠르게 decay시킵니다.
• Cosine schedule, Linear schedule 과 다르게 거의 사용되지 않습니다.

Learning Rate Decay: Constant

• 다음은 Constant 방법으로, epoch가 진행되어도 LR는 같은 값을 유지합니다.
• Constant learning rate schedule은 가장 흔하게 볼 수 있으며, Constant schedule은 다른 복잡한 laerning rate schedule과 비교해 model, problem에 따라 성능이 좋아질 수도 나빠질 수도 있으며, 가능한 빠르게 model을 만들어야 할때는 좋은 선택이 됩니다.
• 또한 momentum같은 optimizer를 사용할때는 복잡한 learning rate decay schedule을 사용하는것이 좋지만 Adam or RmsProp를 사용할때는 (Bias correction이 붙었으므로) learning rate decay가 중요하지 않기에 그냥 Constant learning rate를 사용하는것이 좋습니다.

Learning Rate Decay: Linear Warmup

• Goyal et al, “Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour”, arXiv 2017
• 다음은 Linear Warmup 으로, 높은 초기 learning rates는 Loss를 explode하게 만들 수 있기때문에, 첫 번째 ~ 5,000회 동안 학습 속도를 0에서 선형적으로 증가시키면 이를 방지할 수 있습니다.

Early Stopping

• 결국 좋은 optimization과 learning rate decay 등의 방법론을 쓸때, Loss는 계속 낮아지겠지만, validation set의 accuracy가 감소하려고할때 즉, Loss decay와 accuracy plot을 함께 보면서 overfitting되기 전에 iteration을 멈추어야합니다.
• 학습시 우리가 얼만큼의 epoch or iteration으로 model을 훈련시켜야 할 지 모르겠을때 사용할 수 있는 좋은 mechanism으로 Early Stopping 이 있습니다.
• 따라서, 매 iteration마다의 모델의 스냅샷을 저장한 후, val set에서 가장 잘 워크할 때의 iteration때의 weight를 불러옵니다.

why use First-Order Optimization?

• 그렇다면 왜 2차 근사 대신 1차 근사를 활용하여 최적화를 하는지 살펴보겠습니다.

First-Order Optimization

• 지금까지 배운 최적화 기법들은 모두 1차 미분을 이용한(first-order) 형태였습니다.
• 즉, 위 슬라이드와 같이 현재 지점에서 gradient를 계산하고, 이를 통해 loss 함수를 선형 함수로 근사시키는 방법이었습니다.(일종의 1차 first-order Taylor approximation)
• 하지만 1차 근사 함수의 미분값으로는 멀리 나아갈 수 없습니다.(수렴 속도가 느리다)

Second-Order Optimization

• 1차 근사 함수의 미분보다 조금 더 빠른 방법으로, 2차 근사 함수를 추가적으로 사용하는 것을 생각해 볼 수 있습니다. (Second-order optimization의 기본 아이디어)
  • 2차 근사는 2차 다변수함수의 최적점을 찾아서 이동하는 방식입니다.
• 이는 위 그림과 같이 minima로 더 빨리 수렴할 수 있다는 장점이 있습니다.
• 또다른 장점으로는 flat한 지역이 있을 때, 한 번에 많은 steps를 이동할 수 있다는 점입니다. 즉, loss surface에 따라 유연하게 대처할 수 있습니다.

• 2차 근사함수를 사용하는 Optimization 방법을 Newton’s Method 라고 합니다.
• 2차 미분 값들로 된 행렬인 Hessian Matrix를 계산하고 이 행렬의 inverse를 이용하게 되면, 실제 Loss함수의 2차 근사를 이용해 minima로 바로 이동할 수 있게 됩니다.
• 이와 같은 Newton’s Method에서는 단지 매 step마다 2차 근사 함수의 minima로 이동하면 되기 때문에, learning rate가 필요 없다는 특징이 있습니다.
  • 실제로는 minima로 이동하는게 아니라 minima의 방향으로 이동하는 것이기 때문에 learning rate가 필요하지만, 기본 형태에서는 learning rate가 없습니다.
• 하지만 이 방법은 딥러닝에 사용할 수 없습니다.
  • Hessian Matrix는 N X N의 크기인데, 여기서 N은 파라미터 수 입니다. 따라서, 이러한 큰 행렬을 메모리에 저장하는 것은 불가능하며, 역행렬을 구하는 것도 불가능합니다.

• 그래서 실제로는 Full Hessian을 Low-rank로 approximation하는 Quasi-Newton method 를 사용하게 됩니다.

Second-Order Optimization: L-BFGS

• Hessian Matrix를 근사시키는 방법을 사용한 Second-order optimization 방법으로는 L-BFGS 가 있습니다.
• 그러나 Full batch에서는 잘 작동하지만, 소량의 샘플을 뽑아서 그래디언트/헤시안 매트릭스를 계산하는 mini-batch 환경에서는 잘 작동하지 않습니다. Large-scale에 2차근사 방법을 적용시키면, Stochastic setting의 노이즈가 커집니다.
• 또한 L-BFGS와 같은 이러한 2nd order opproximation은 stochastic case와 non-convex case에서 잘 동작하지 않기 때문에, DNN에서는 잘 사용되지 않습니다.

Optimization Summary

• W의 최적점을 찾는 최적화 알고리즘으로 Adam을 주로 좋은 디폴트 초이스로 활용합니다.
• SGD + Momentum이 더 좋은 성능을 낼 수 있지만, 튜닝에의 더 많은 노력이 필요합니다.
• 또한 만약 full batch updates를 하게된다면, L-BFGS를 활용해보는 것도 좋습니다.

Beyond Training Error

• 지금까지 이야기했던 모든 것들을 전부 training error를 줄이기 위한 방법들이었습니다.
  • optimization 알고리즘들은 training error를 줄이고 손실함수를 최소화시키기 위한 역할을 수행합니다.
• 즉 최적화(Optimization) 과정이 손실함수의 최솟값을 찾아나가며 train error를 줄이는데 집중했다면 이제는 valid error와의 차이를 줄여 과적합을 방지할 차례입니다.
  • 정리하자면, test set의 loss가 낮게 나오는 것을 원하기에, test set의 loss값과 training set의 loss값의 차이(gap)를 줄여야 합니다.
• 학습에서 Loss 함수의 최적화시, overfitting을 방지하는 동시에 Test에서의 성능을 높이기 위한 가장 쉬운 방법은 무엇이 있을까?
  • 이 질문은 Regularization 으로 이어집니다.

Model Ensembles

• 우선 가장 쉬운 방법으로는 Ensembles 이 있습니다.
• 앙상블은 여러개의 독립된 여러모델을 학습시킨 후, test time시에 이들의 결과를 평균내는 방법 입니다.
  • 모델의 수가 늘어날수록 overfitting이 줄어들고 성능이 조금씩 향상됨 (보통 2% 정도 증가함)
  • 이를 통해 validation set과 training set의 갭을 줄이고 robust한 결과 를 낼 수 있도록 합니다.
  • Imagenet 같은 대회에서는 모델의 성능을 최대화 시키기 위해서 앙상블을 사용하는 경향이 다수 존재합니다.

Model Ensembles: Tips and Tricks

• 하나의 모델에서 학습 도중 중간중간에 snap shot을 찍은 후(모델의 가중치를 저장), Test 시에 이들 snap shot들에서 나온 prediction들을 평균내어 사용하는 앙상블 방법이 있습니다.
• ICLR에서 발표된 한 논문에서는 매우 독특한 Learning rate scheduling을 사용하여 조금 더 향상된 앙상블 알고리즘이 발표되었습니다.
  • Learning rate을 매우 낮췄다가 매우 높였다가를 반복하면서 학습 과정에서 Loss 함수의 다양한 지역에서 수렴하도록 만듭니다. 이때, 수렴할 때마다 snap shot을 찍습니다.
  • 그리고 이들 snap shot들을 모두 앙상블합니다.
  • 이 방법은 모델을 한번만 학습시켜도 좋은 성능을 얻을 수 있게 해줍니다.
• 정리하면 모델을 여러 개 training 해서 model ensembles를 하는경우도 있으며, learning rate schedule을 활용하여 하나의 모델 훈련만으로도 앙상블의 효과 를 낼 수 있는 방법이 있습니다. LR decay를 주고, 특정 시점마다 다시 LR을 높게 주면서, 구간 별 모델의 스냅샷을 저장하여 모델이 낸 결과를 평균내어 앙상블을 구현합니다.

• 또다른 앙상블 방법으로는 Polyak averaging이라는 방법이 있습니다.
• 이 방법은 학습하는 동안에 파라미터 벡터의 exponentially decaying average를 keep해뒀다가, Test시에 checkpoint에서의 파라미터가 아닌 smoothly decaying average를 사용하는 방법입니다.
• 이는 학습중인 네트워크의 smooth 앙상블 효과를 얻을 수 있으며, 때때로 약간의 성능향상을 보이게 됩니다.(시도할만하지만 실제로는 잘 사용하지 않음)

How to improve single-model performance?

• 그렇다면 앙상블이 아닌 단일 모델의 성능을 향상시키기 위해서는 어떻게 해야 할까?
• 여러 모델을 ensemble 하지 않고, 단일 모델로 validation set(test set)의 성능을 올리는 좋은 방법 으로 Regularization 이 있습니다.
  • 즉, 단일 모델의 성능을 올리는 것이 우리가 정말 원하는 것으로, 훈련과정 자체에서 regularization을 추가하여 모델이 training data에만 fit하는 것을 막아주어서, unseen data에서의 성능을 향상시켜 줍니다.

Regularization: Add term to loss

• 앞 장에서 Loss에 regularization term 을 붙이는 방법을 배웠습니다. $R(W)$ term을 통해, $L(W)$ 가 취할 수 있는 영역에 제한을 두어, training을 방해합니다.
  • 즉 Loss항에 L1 regularization, L2 regularization과 같은 항을 추가해줌으로써 training data에만 잘 맞는 상황에 패널티를 주는 것입니다.
    • L1 regularization 은 학습에 기여하지 못하는 가중치를 0으로 만들어 버립니다.
    • L2 regularization 은 학습에 기여하지 못하는 가중치를 0에 가깝게 만들어 버립니다.
  • 통계학에서 유의하지 않은 독립변수를 제거하는 검정과 유사합니다.
• 하지만 이러한 Regularization 방법은 Neural Network 에서는 잘 어울리지 않아 다른 방법을 사용합니다.

Regularization: Dropout

• Neural Network에서 가장 많이 사용되는 regularization 방법은 Dropout 입니다.
• Dropout의 동작 방식은 단순히 Forward pass 과정에서 임의로 일부 뉴런의 출력을 0으로 만드는 것 입니다.
  • 이때, Random하게 일부 뉴런을 선택하므로 매 forward pass 반복마다 출력이 0이 되는 뉴런은 바뀝니다.
  • 말 그대로 랜덤으로 뉴런 값을 0으로 보내버리는 것입니다.
  • 뉴런을 얼마나 drop 할 것인가는 하이퍼파라미터입니다. 보통은 0.5를 사용합니다.
• 즉 Dropout은 Neural network의 forward pass에서 각 layer의 neuron(hidden unit)을 ramdom하게 0로 만들어 해당 노드를 삭제(drop)하는 것이 핵심 idea 입니다.
  • 보통 Fully Connected Layer에서 더 많이 쓰이며, CNN에서는 보통 채널 단위로 적용 됩니다.
• 최근 Network 아키텍쳐에서는 많이 사용하지는 않습니다.

• 위 코드는 3-layer neural network의 (forward pass중) 각 layer마다 binary mask (p를 0.5로 설정해줬으니 binary)를 취해주어 drop시키는 형태의 구현입니다.
  • drop 할 뉴런의 activation을 0으로 만들어 필요한 뉴런만 사용 하게 됩니다.

• 그렇다면 일부 뉴런을 drop하는 dropout이 어떻게 regularization효과를 가져올 수 있는 것일까?
• Dropout의 원리를 대략적으로 이해하자면, feature들 간의 상호작용(co-adaption)을 예방 또는 방지하는 것 이라고 볼 수 있습니다.
  • 예를 들어, 고양이를 인식하는, 분류하는 어떤 네트워크가 있다고 할 때, 어떤 뉴런은 고양이의 귀, 어떤 뉴런은 고양이의 털, 어떤 뉴런은 고양이의 꼬리에 대해 학습된다고 생각해보겠습니다.
  • 고양이 인식 모델은 이들의 정보를 모두 모아서 출력을 내게 되는데, 이때, dropout을 적용하게 되면, 네트워크가 일부 feature에 의존하지 못하게 해줍니다.
  • 즉, 네트워크가 고양이라고 예측할 때, 다양한 feature들을 골고루 이용할 수 있게 되는 것이며, 이는 Overfitting을 어느정도 막아준다고 볼 수 있습니다.
• 풀어 말하면 Randomness를 부여해 모든 feature에 대한 weights를 분산시키는 역할을 하여, model이 많은 feature들 중 특정 feature에 의존하게 되는 현상을 줄이고, 여러 feature 들을 골고루 사용할 수 있게 하는 것 입니다.
  • 모델이 학습을 하다 보면 비슷한 정보를 가지는 노드가 생기기 마련 입니다.
  • 이는 과적합을 야기할 수 있기 때문에 입력값의 일부를 0으로 두어 역전파시 파라미터 업데이트가 되지 않게하여, 모형의 불확실성을 증가시켜 과적합 해결에 기여 하게 됩니다.

• Dropout에 대한 새로운 해석으로는 단일 모델로 ensemble 하는 효과 를 가질 수 있다는 것입니다.
  • 위 슬라이드의 왼쪽 그림과 같이, dropout을 적용한 network를 보면 일종의 sub network라고 볼 수 있습니다. 그리고 매 반복마다 이러한 sub network들은 다양하게 생성됩니다.
  • 따라서, Dropout은 이러한 sub network들의 거대한 앙상블을 동시에 학습시키는 것이라고도 해석 할 수 있습니다.
• 즉 training시 각 sample마다 다른 mask가 적용되어 하나의 모델이 되어서, 결국 full-training에선 각 model들의 ensemble이 된다는 뜻 입니다.

Dropout: Test time

• 여기서 dropout을 train data로 모델을 학습시킬 때만 활용하고 test data를 적용할때는 사용하지 않는 것으로만 알고 있는 사람들이 많은데, test 단계에서 dropout이 아예 쓰이지 않는 것이 아닙니다. 정확하게 짚고 가겠습니다.
• 우선 Test time 때에도 dropout을 적용하게 되면, 이미 학습된 네트워크의 Test time에 randomness를 부여하는 문제를 야기시킵니다.
  • 즉 테스트할 때마다 결과가 다르게 나옵니다.
  • 기존의 Neural network의 출력은 $f(w, x)$ 였지만, dropout으로 인해 입력에 random dropout mask $z$ 가 추가됩니다. 하지만, Test time에 이러한 randomness를 부여하는 것은 nice하지 않습니다.
  • Ex) 고양이와 개를 분류하는 모델이 같은 이미지에 대해서, 어제는 개를 출력하고 오늘은 고양이를 출력하면 신뢰할 수 없습니다.
• 즉 dropout은 test-time operation에서 사실상 random output을 만들기에 문제가 됩니다. 이는 매번 다른 예측을 가져올 수 있다는 것을 뜻하므로, 우리는 output이 deterministic이기를 원합니다.
• 그렇므로 test-time에서 randomness를 없애기 위해 서 average out 해야합니다.
  • output을 z에 대한 expectation으로 볼 수 있습니다. 다른말로 적분을 통해 randomness를 marginalize out시키는 것으로 생각할 수 있습니다.
  • 즉 모든 뉴런을 켜고, 각 뉴런의 결과값에 확률 $p(z)$ 를 곱합니다.
  • 하지만, 이러한 적분을 다루기는 상당히 까다롭습니다.
• 적분이 어렵다면, 간단히 샘플링을 통해서 적분을 근사하는 방법도 생각해 볼 수 있습니다.
  • z를 여러번 샘플링해서 Test time에 average out시키는 방법
  • 하지만, 이 방법도 여전히 Test time에서의 randomness를 만들어 내기 때문에 좋지 않습니다.

• 앞에서 살펴본 문제들로 인해, dropout에서는 다음과 같이 단순한 방법을 통해 randomness 없이 적분을 근사 하게 됩니다.
  • Training과 Test에서의 기댓값
    • Test
      • 단순히, weighted sum을 구하면 됩니다.
      • 기댓값 : $w_1x + w_2y$
    • Training
      • x를 활성화/비활성화, y를 활성화/비활성화하는 총 4가지의 경우가 있습니다. 확률과 뉴런의 결과값을 모두 곱해줍니다.
      • 0.5의 dropout이라고 가정할 때, 나올 수 있는 4가지 네트워크에서의 출력들을 구하고, 4로 나눠서 평균낸 후 더합니다.
      • 기댓값 : $\frac{1}{2}(w_1x+w_2y)$
  • 위와 같이 Train과 Test에서의 기댓값이 서로 다른 경우에서 randomness 없이 적분을 근사할 수 있는 단순한 방법 중 하나는 dropout probability를 출력에 곱하는 것 입니다.
    • Dropout probability 0.5를 Test의 출력인 $w_1x + w_2y$ 에 곱해주면, training에서의 기댓값과 같은 결과를 얻게 됩니다.
    • 기댓값 : $(0.5) × (w_1x + w_2y) = \frac{1}{2}(w_1x+w_2y)$
• 정리하면, test time에는 어떤 노드도 버리지않고, p값을 곱해주어야 합니다.
  • 이는 dot product의 single scalar output에 dropdout probability를 곱해준 형태가 됩니다.
  • 따라서 test time시 dropout probability를 곱하여 계산하기만 하면 간단하게 적분을 근사할 수 있습니다.
• 이 방법은 이전 슬라이드에서 살펴본 복잡한 적분식을 보다 cheap하게 locally approximate한 방법이며, 실제로 Dropout을 사용할 때 이 방법을 많이 사용합니다.

• Dropout의 Test time에서는 모든 뉴런을 활성화한 결과에 dropout probability를 곱합니다.
• 이러한 test-time에서의 구현은, training시 dropout을 거친 neuron의 output 기대값과 test-time시 neuron의 output 기대값의 scale이 달라지게되는 문제 를, test-time에서 기댓값을 scaling 시켜주어 해결 할 수 있게 되었습니다.

• Dropout은 위와 같이 몇줄의 코드로 쉽게 구현할 수 있습니다.
  • Training시 매 layer사이에서 mask를 drop시킵니다.
  • Test시 값에 확률값 p를 곱해줍니다.
• Neural network의 Regularization에 상당히 효과적입니다.
• 하지만 test-time은 predict를 위한 것이니 우리는 위와같이 결과에 ramdomness가 추가되는 것을 원치 않을 수 있습니다.

• 그리고 더 일반적으로 test time에서의 계산효율을 더 높이기 위해 Inverted dropout 을 사용합니다.
  • Test time에서 dropout probability p를 곱해주는 연산을 줄이는 방법 대신, Train time에서 p로 나눠주는 방법이 있습니다.
• 이러한 방법을 사용하는 이유는, Train time에서는 GPU를 사용해서 곱하기 몇번 추가되는 것이 큰 영향이 없지만, Test time에서는 계산효율, 즉 가능한 빠른속도로 효율적으로 동작해야 하기 때문 입니다.
  • 이로써 test time 에서의 계산을 최소화 할 수 있습니다.
• Dropout을 사용하게 되면 전체 학습시간은 늘어나지만 모델이 수렴한 후에는 더 좋은 일반화 능력을 얻을 수 있습니다.
  • dropout을 사용하게 되면 Train time에서 Dropout이 0이 아닌 뉴런에대해서 gradient backprop이 발생하게 됩니다.
  • 각 스텝마다 업데이드되는 파라미터의 수가 줄어들기 때문에 dropout을 사용하게 되면 전체 학습시간이 늘어납니다.

Dropout architectures

• AlexNet, VGG에서는 많은 parameter들이 사용되는, 아키텍쳐의 맨 윗단 레이어인 fully-connected layer에서 dropout을 적용 합니다.
  • 보통 regularization을 사용하는 이유는 overfitting을 방지하기 위해서인데, 어떤 layer에 hidden unit size가 클 수록 (parameter수가 많아지니) overfitting될 가능성이 높기 때문에 dropout을 사용 하며, size가 작은 layer에서는 dropout을 사용하지 않습니다.
• 하지만 비교적 최근 architecture인 GoogLeNet, ResNet에선 fc layer대신 global polling layer를 사용하기에 dropout을 사용하지 않습니다.

Regularization: A common pattern

이러한 dropout에서 나타나는 것 처럼 neural network의 다른 regularization에서도 찾아볼 수 있는 흔한 패턴이 있습니다.

• Regularization의 일반적인 패턴 을 정리하면 다음과 같습니다.
  • Training : 무작위성(randomness)를 부여 하여 training data에 대해 overfitting을 막습니다.
  • Test : randomness를 평균 또는 근사해서 generalization 효과 를 줍니다.
• Dropout외에도 이러한 패턴으로 regularization 효과를 불러오는 방법으로는 Batch Normalization 이 있습니다.
  • Training에서는 mini-batch로 데이터가 샘플링 될 때마다 서로 다른 데이터들과 만나게 됩니다. 이때 각 데이터들을 얼마나 normalize 시킬 것인지에 대한 randomness(또는 stochasticity)를 부여 하여 training data에 대해 overfitting을 막습니다.
  • Test에서는 mini-batch 단위가 아닌 global 단위로 normalization을 수행함으로써 이러한 randomness(또는 stochasticity)를 평균내어 generalization 효과 를 줍니다.
  • 즉, Batch Normalization은 train에서 stochasticity(noise)가 추가되지만, Test time에서 모두 average out하기 때문에 regularization 효과가 있게 되는 것입니다.
• 이러한 이유로 인해, 실제로 Batch Normalization을 사용할 때에는 Dropout을 사용하지 않습니다.
  • 충분한 Regularization 효과가 있기 때문입니다.

Regularization: Data Augmentation

• regularization의 패턴에 부합하는 또다른 regularization 방법으로는 data augmentation 이 있습니다.
• Data Augmentation이란, training data를 무작위로 변형시키고 원래의 label 값을 그대로 이용하여 학습시키는 방법 입니다.
  • 즉 원본 이미지를 사용하는 것이 아니라 무작위로 변환시킨 이미지로 학습하게 됩니다.
• 비슷한 이미지지만, CNN 모델은 다른 이미지로 인식하며, 밝기 조절 혹은 좌우 대칭 등을 randomness의 일종으로 볼 수 있습니다.

Data Augmentation: Horizontal Flips

• 간단한 예로, 이미지를 horizontal flips 할 수 있습니다. 이미지가 반전되도 고양이는 여전히 고양이 입니다.
• 이러한 이미지 특징을 이용해 다양한 데이터에 대해 모델이 학습할 수 있게 해주는 것이 Data Augmentation 입니다.

Data Augmentation: Random Crops and Scales

• 이미지를 임의의 다양한 사이즈로 잘라서(crop) 사용할 수도 있습니다. 여전히 이미지는 고양이 입니다.
• Data Augmentation이 regularization pattern에 부합하는지를 살펴보면 다음과 같습니다.(Resnet)
  • Training
    • Random하게 cropping하거나 scaling 등을 수행해서 학습합니다.
    • 즉, randomness가 추가되는 것입니다.
  • Testing
    • Test할 하나의 이미지에서, 5개의 scale로 조정하고, 각 scale별 (네개의 각 코너와 중앙에서 crop한 이미지와 이들의 flipped image) = (4개코너 + 중앙) X (원본 + flipped) = 10개의 이미지를 추출해서 성능을 평가합니다.
    • 즉, stochasticity를 average out하게 되는 것입니다.

Data Augmentation: Color Jitter

• Data augmentation으로 color jittering도 있습니다.
  • 학습 시 이미지의 contrast 또는 brightness를 바꿔줍니다.
• 조금 더 복잡한 방법으로, R, G, B 픽셀에 대해 PCA의 방향을 고려하여 color offset을 조절하는 방법입니다.
  • 즉 조도를 조절하는 방법입니다.
  • 이 방법은 color jittering을 좀 더 data-dependent한 방법으로 진행하는 것입니다.
  • 자주 사용하는 방법은 아닙니다.

Data Augmentation: Get creative for your problem!

• 다양한 augmentation 방법들이 있으며, 이는 각 data, 각 problem에따라 다른 transform이 필요할 것이며 명확한 답이 없습니다.
• Data Augmentation은 어떠한 문제에도 적용해 볼 수 있는 아주 일반적인 regularization 방법이라고 볼 수 있습니다.
  • Label을 바꾸지 않고 데이터에만 변환을 줄 수 있는 많은 방법들이 모두 Data Augmentation에 사용될 수 있습니다.

Regularization: A common pattern

• 정리하면 Dropout, Batch Normalization, Data Augmentation같은 기법은 일반적인 Regularization 기법입니다.
• regularization의 common pattern 의 관점에서 보면, data augmentation을 함으로써 train time에 다양한 stochasicity 를 일으키고, 최종적으로 test time에 average out하는 효과 를 얻음으로써 regularization효과가 있습니다.

Regularization: DropConnect

• 지금까지 살펴본 Regularization pattern을 잘 숙지하고 논문을 읽다보면, 여러가지 regularization 방법들이 눈에 들어오게 됩니다.
• 그 중 한 예로는, DropConnect 라는 방법이 있습니다.
  • 이는 Dropout과 유사한 방법이며 activation이 아닌 weight matrix를 0으로 만들어 주는 것이 차이점입니다.
  • Dropout과 동작이 아주 비슷합니다.
• 즉, DropConnect는 활성화가 아닌 가중치를 임의적으로 0을 만드는 걸 말합니다.
  • 가중치를 0으로 만드는 건 training 때 그렇고, testing에는 모든 연결선을 사용합니다.

Regularization: Fractional Pooling

• 또 다른 Regularization 방법으로는 Fractional Max Pooling 이 있습니다.
• 일반적인 2x2 Max Pooling 연산은 고정된 2x2 지역에서 수행하지만, 이 방법에서는 Pooling 연산을 수행할 지역이 random하게 선정 하게 됩니다.
  • 위 슬라이드의 그림은 Train time에 샘플링될 수 있는 random한 pooling region을 나타낸 것입니다.
  • Test time에서는 pooling 영역을 고정하거나 또는 여러개의 pooling 영역을 만들고 average out시키는 방법을 사용합니다.

Regularization: Stochastic Depth

• Stochastic Depth 이라는 방법도 있습니다.
  • Train time에는 layer중 일부를 random 하게 drop하고 일부만 사용해서 학습을 수행합니다.
    • 즉 랜덤하게 몇 개의 레지듀얼 블락을 무시합니다.
  • Test time에서는 전체 네트워크를 사용합니다.
• 이 방법도 마찬가지로 regularization 효과는 dropout과 같은 다른 방법들과 유사합니다.

Regularization: Cutout

• 비교적 최신기법인 Cutout 방법론이 있습니다.
  • Cutout은 image에 일정 region을 zero로 만들어 randomness를 부여하는 방식입니다.
  • test시엔 whole image를 사용합니다.

Regularization: Mixup

• 다음은 Mixup 방법론이 있습니다.
  • Mixup은 training image를 label별 random한 weight 비율로 blend시키는 방식입니다.
  • 이때 sample은 beta distribution을 통해 blend weights가 확률적으로 정해집니다.

Regularization Summary

• 여러 종류의 regularization을 살펴보았습니다.
• 각각 regularization의 scheme은 다를 수 있지만 대부분 regularization은 training시에 randomness를 부여하고, test시에 average out 시키는 형태의 패턴 을 갖고있습니다.
• 결국 regularization은 model이 high variance를 가져 overfitting되는 현상을 완화 시키고자 각 regularization마다 (intput값이던, pooling layer의 kernel이건 등등의) 특정 randomness를 부여하여 training시킨다는 것이 핵심 입니다.

Transfer Learning

• 지금까지 Overfitting을 해결하는 Regularization 방법들에 대해 알아봤습니다.
• 사실 Overfitting을 해결하는 가장 좋은 방법은 train data의 양을 늘리는 것입니다.
• 그렇다면, 좋은 성능의 classifier를 만들기 위해서는 무조건 많은 데이터가 필요할까?
  • 이 질문은 *Transfer Learning**으로 이어집니다.
• Transfer Learning의 기본 철학은 좋은 성능의 classifier를 만들기 위해서는 무조건 많은 데이터가 필요한 것은 아니라는 것입니다.
  • 즉, *Transfer learning을 사용하면 적은 양의 데이터로도 Deep Neural Network 모델을 사용할 수** 있습니다.

Transfer Learning with CNNs

• ransfer learning 의 개념은, 기존에 사전 학습된 (pre-trained) 가중치를 이용하고 추가적으로 내 데이터에 맞게 $W$ 의 일부만을 학습시키는 것 입니다.
  1. 기본 idea는 첫번째로 imagenet과 같은 큰 data set으로 학습된 CNN model을 가져옵니다.
     • VGG CNN 아키텍쳐를 다운받았다고 생각해봅시다.
  2. 그리고 다음 단계는 앞서 ImageNet에서 학습된 feature를 우리가 학습할 작은 데이터셋에 적용하는 것입니다.
     • 가져온 model의 Last layer인 fully-connected layer는 Imagenet에서의 클래스 분류를 위한 것이므로 삭제를 합니다.
     • 직전 layer까지의 weight들 은 모두 requires_grad = False로 설정하여 freeze 하고, 업데이트에 사용하지 않습니다. 즉 feature extractor로 사용하는 것 입니다.
• 데이터 수에 따라 학습 방법에 조금 차이가 있습니다.
  • 데이터가 적은 경우
    • 우리가 원하는 출력 클래스 수 C를 출력하도록 제일 마지막 layer만 초기화 한 후, 이 layer를 제외한 나머지 layer는 freeze시킨 후, 학습을 진행 합니다.
    • 즉, 마지막 출력 layer만 학습시키는 것으로, linear classifier를 학습시키는 것과 같습니다.
  • 데이터가 조금 더 있는 경우
    • 데이터가 적은 경우에서와 같이 마지막 layer를 초기화 하는 것은 동일하지만, 여기서는 데이터가 더 많으므로, 몇개의 layer를 더 학습에 추가할 수 있습니다.
• 이렇게 pre-trained된 model을 가져와 transfer learning을 하는 것은, 한정된 dataset을 가지는 상황에서 성능을 향상시키는데 도움이 됩니다.

• 위 그림은 “Caltech-101” 이라는 101개의 categories를 가진 적은 양의 dataset의 classification 문제에서 모델별 성능을 나타내는 그래프입니다.
  • 빨간 그래프는 기존의 Caltech-101 dataset만을 학습시킨 모델의 성능을 나타냅니다.
  • 파란색과 초록색 그래프는 transfer learning을 활용하여 imagenet을 pre-trained 시킨 AlexNet을 사용하여 feature vector를 뽑아내고, 간단한 logistic regressor와 SVM을 사용하여 train시킨 model이다.
• 즉 파란색과 초록색 그래프는 top layer를 제거하여 feature extractor로 활용한 후, 그 위에 linear classification을 적용하여 학습한 방법입니다. 이 방법이 성능이 더 좋음을 알 수 있습니다.

• 위 그래프는 AlexNet의 FC 레이어를 날리고, 다른 방법을 활용하면 성능을 더 올릴 수 있다는 것을 보여주는 그래프입니다.
• 정리하면, 우리가 가진 data가 적다면 pre-trained CNN model을 feature extractor로 사용하고 output layer만 liniear classifier같은 간단한 algorithm으로 수정하여 사용할 수 있습니다.

Fine-Tuning

• 하지만, 만약에 좀더 큰 dataset을 가지고있다면 Fine-Tuning 이라는 과정을 사용하여 transfer learning을 통해 좀더 좋은 성능을 낼 수 있습니다.
• Fine-Tuning이란 다운받은 모델(ex. AlexNet)의 weight를 initial weight로 설정하고, 우리가 가진 데이터셋에 새로 훈련하는 것입니다.
  • pre-trained entire model을 new dataset에 학습시키는 것으로, 전체 model의 weights들을 backpropagation을 통해 계속 update시켜 성능을 향상시키는 것입니다.
• Fine-tuning할 때의 몇 가지 tricks
  1. Fine-tuning하기 전에, feature extractor로 한 번 사용해보면, 이 것이 baseline 성능이 됩니다.
     • 즉, Fine-tuning의 목적은 baseline보다 성능을 끌어올리는 것입니다.
  2. 낮은 Learning rate를 사용합니다.
     • 기존에 ImageNet에서 학습된 가중치들이 잘 학습되어 있고, 대부분 잘 동작하기 때문에, 우리의 데이터셋에서 성능을 높이는데에는 약간의 가중치 수정만 필요하기 때문입니다.
  3. 연산 비용을 절약하기 위해 Image input 근처의 lower level layer들은 그대로 사용할 수 있습니다.

• 위 그래프를 보면, feature extractor로만 사용했을 때보다, Fine-tuning을 했을 때 성능이 훨씬 좋아졌음을 알 수 있습니다.

Transfer Learning with CNNs: Architecture Matters!

• 실제로 매우 많이 활용합니다.
• AlexNet이외에 다른 아키텍쳐들을 활용할 수 있고, Imagenet에서 잘 수행하는 아키텍쳐일 수록 다른 데이터셋에 대해서도 잘 할 가능성이 큽니다.

• 또한 Object Detection 또는 다른 Task 에서는 밑단에 feature extractor가 필요합니다.
• 이때 feature extractor를 AlexNet, Vgg, ResNet, ResNeXt로 활용했을 때, 점점 성능이 높아짐을 알 수 있습니다.

Transfer Learning with CNNs: Strategy

• 그렇다면, CNN 아키텍쳐들을 Imagenet과 같이 다른 데이터셋에 적용을 할 때, 경우에 따라 어떤 방법을 활용하면 좋을 지를 살펴보겠습니다.
  • very similar dataset
    • 유사한 데이터셋에 대한 것입니다.
    • 즉, 데이터 distribution가 가깝기 때문에, pretrained model instance들이 더 많은 도움을 줄 것입니다.
  • very different dataset
    • 반대로 유사하지 않은 데이터셋에 대한 것입니다.
    • 데이터 distribution도 매우 다르기때문에, 다운받은 model instance들이 큰 도움을 주지 못할 것입니다.
  • very little data
    • 일반적으로 10 ~ 100개의 카테고리 개수를 가집니다.
  • quite a lot of data
    • 일반적으로 100 ~ 1000개의 카테고리 개수를 가집니다.
• 따라서 데이터의 보유량, 데이터가 pre-trained dataset 과 비슷한지 여부 에 따라 어떻게 transfer learning을 진행할지를 정리할 수 있습니다.
  • 데이터 많고, 기존 데이터셋과 비슷할 경우
    • 더 많은 레이어들을 fine tuning에 활용하면 더 좋은 성능을 기대해볼 수 있습니다.
    • 즉 적은 양의 Layer 만 fine-tunning 하는 것이 좋습니다.
  • 데이터 적고, 기존 데이터셋과 비슷할 경우
    • 마지막 top layer만 날리고 feature extractor로 활용하는 것이 좋습니다.
    • 즉 마지막 FC-Layer만 학습하는 것이 좋습니다.
  • 데이터 많고, 기존 데이터셋과 다른 경우
    • 데이터셋의 Domain과 많이 다르고, 데이터셋이 크다면 더 많은 레이어들을 fine tuning에 활용하면 해당 데이터셋에 맞게 활용할 수 있습니다.
    • 즉 많은 양의 layer 를 fine-tunning 하는 것이 좋습니다.
  • 데이터 적고, 기존 데이터셋과 다른 경우
    • 만약, 우리가 가진 데이터가 Transfer learning을 수행하려는 모델에 사용한 데이터와 차이가 난다면 Transfer Learning이 큰 효과를 내지 못할 수 있습니다.
      • 예를 들어, 의료영상 데이터는 ImageNet 데이터와 큰 차이가 있기 때문에, 큰 효과를 내지 못할 수도 있습니다.

• CNN에서는 Transfer learning이 매우 보편적으로 사용됩니다.
• Object detection, image caption에서도 이미지를 인식하는 feature extractor부분이 필요합니다.
  • 위 슬라이드의 모델에서도 모두 ImageNet에서 학습된 CNN을 사용하고 있습니다.
  • (좌)Object Detection, (우)Image Captioning
• 위 슬라이드의 오른쪽 초록색 박스부분을 보면 CNN뿐만 아니라 Image captioning의 language model파트에서는 NLP에서 주로 활용하는 word2vec의 pretrain된 모델을 사용하고 있는 것을 볼 수 있습니다.
• 즉 거의 모든 computer vision 관련 응용 알고리즘들이 모델들을 밑바닥부터(from scrtch) 학습시키지 않으며, 대부분은 ImageNet pretrained-model을 사용하고 현재 본인의 task에 맞도록 fine tune 합니다.

• 이미지 모델 파트에서는 잘 pretrain된 CNN 모델을 활용해서 fine tuning을 하고, 언어 모델 파트에서는 BERT를 활용하면, Visual question answering를 잘할 수 있습니다.

• 그러나 transfer learning은 역시 practical한 이야기이므로, 잘 작동하지 않을 수 있습니다.
• 그래프에서 회색 선이 pretrain 된 모델, 보라색 선이 random initialization으로 한 모델에 대한 성능을 나타냅니다.
  • 그래프를 보면, 트레이닝을 3배 정도 더 하면, 랜덤 초기화방법도 pretrain된 모델과 비슷한 성능을 낼수 있습니다.
  • 즉, ImagNet에 대해 pretraining한 것이 이론적으로 더 높은 성능을 낸다는 것은 아닙니다.
• 결국은 pretraining 하는 것 보다 더 많은 데이터를 수집하는 것이 더 효과적 입니다.

• Transfer learning에 대한 Justin의 시각은 다음과 같습니다.
  • Pretrain + finetuning은 빠르고, 괜찮은 성능을 내기 때문에 첫번째로 시도해볼 만 합니다.
  • 데이터셋이 많다면, random initialization으로 직접 트레이닝을 해도 괜찮은 성능을 낼 수 있습니다.
  • Transfer learning은 아직 이론적으로 많은 규명 작업이 필요합니다.

• 따라서, 프로젝트 수행 시 데이터가 부족할 때 Transfer Learning을 사용하는 것이 좋습니다.
  • 만약 어떤 문제가 있는데, 이 문제에 대한 데이터셋이 크지 않은 경우라면 우선 프로젝트의 task와 유사한 데이터셋으로 학습된 pretrained model을 다운로드 받이서 모델의 일부를 초기화시키고, 새로운 데이터로 모델을 fine-tune 합니다.
• 또한, 전이학습은 아주 일반적인 방법이므로 대부분의 딥러닝 프레임워크에서도 다양한 pretrained model을 쉽게 다운받을 수 있도록 Model Zoo를 제공합니다.

Summary

• 요약하자면 training loss를 개선 optimization을 배웠습니다.
• test data에서의 성능을 향상시키는 방법 regularization에 대해서도 배웠습니다.
• 그리고 데이터가 적을때 할 수 있는 아주 좋은 방법인 transfer learning에 대해서도 배웠습니다.

해당 게시물은 Standford 2017 CS231n 강의와 2022년 슬라이드를 바탕으로 작성되었습니다.

Training Neural Networks

• 이번 시간에는 nerural network를 학습시키는 방법을 살펴보겠습니다.
  1. One time set up
     • activation functions
     • preprocessing
     • weight initialization
     • regularization
     • gradient checking
  2. Training dynamics
     • babysitting the learning process
     • parameter updates
     • hyperparameter optimization
  3. Evaluation
     • model ensembles
     • test-time augmentation
     • transfer learning

Activation Functions

• Activation unction(활성화 함수) 는 신경망의 출력을 결정하는 식입니다.
  • 위 그림에서는 하나의 Neuron에서 input $x$ 와 weights $w$ 를 dot product하여 activation function의 input으로 들어가게 되고, non-linear activation function을 거쳐 다음 layer로 출력하게 됩니다.
  • 그림과 같이 신경망에서는 뉴런에 연산 값을 계속 전달해주는 방식으로 가중치를 훈련하고 예측을 진행합니다.
  • 이 때 각각의 활성화 함수는 네트워크의 각 뉴런에 연결되어 있고, 각 뉴런의 입력이 모델의 예측과 관련되어 있는지의 여부에 따라 활성화됩니다. 활성화 함수는 훈련과정이나 역전파 과정에서 계산량이 많으므로 비선형성 및 효율성이 중요 합니다.
• Activation function은 크게 3가지로 분류할 수 있습니다.
  1. Binary Step function
     • 다중 분류 문제에서 다중 출력을 할 수 없습니다.
  2. Linear Activation function(선형 활성화 함수)
     • Step function과 달리 다중 출력이 가능합니다.
     • 하지만 backpropagation 사용이 불가능합니다.(물론 사용 자체는 가능)
       • 역전파는 함수를 미분하여 사용하는 과정인데 선형함수의 미분은 상수이기 때문에 입력값과 무관한 결과가 나오기 때문입니다.
     • 또한 얻을 수 있는 정보가 제한적이어서, hidden layer 사용이 의미가 없어집니다.
       • 활성화 함수를 여러 층에서 쓰면서 필요한 정보를 얻어야 하는데, 선형함수를 여러 번 사용하는 것은 마지막에 선형함수 한 번 사용하는 정도밖에 안됩니다. 따라서 hidden layer를 여러 번 사용하는게 의미가 없게 됩니다.
  3. Non-linear activation function
     • 위와 같은 단점들 때문에 보통 비선형 함수를 사용합니다.
     • 입출력간의 복잡한 관계를 만들어서 필요한 정보를 얻는 것 입니다.
     • 이는 Linear activation function과 달리 backpropagation이 가능하고, hidden layer를 통해 더 많은 정보들을 얻는 게 가능해지기 때문에 사용합니다.

결과적으로, 모든 layer(혹은 node)에서 어떠한 activation fcuntion을 갖는데, 이때 activation fcuntion이 없다면 전체 neural network가 단순한 linear model과 다를바 없게 되기에 activation fcuntion의 역할은 상당히 중요합니다. 그러므로 linear한 모델에 non-linearity(비선형성)를 부여하기 위해 sigmoid 나 ReLU 와 같은 non-linear activation function(비선형 활성화 함수)을 사용했습니다.

Type of activation function

여러가지의 Activation function 각각이 어떤 특징을 갖고있고, 어떤 장단점이 있는지 살펴보겠습니다.

Activation Function: Sigmoid

• 전통적으로 사용해온 활성함수로서, Sigmoid 함수는 로지스틱 회귀분석으로부터 왔고, 확률적인 해석이 가능합니다. 따라서 확률과 비슷하게 [0, 1] 값을 가집니다.
  • $𝜎(x)\ =\ 0.8$ 이면, 다음 레이어의 특정 노드를 활성화시킬 확률이 0.8이라고 해석할 수 있습니다.
  • 또한 the presence or absence of a boolean variable의 확률로 해석할 수 있습니다.
• 입력의 값이 크면 Sigmoid의 출력은 1에 가까울 것이고, 값이 작으면 0에 가깝습니다.
• 즉, 시그모이드(Sigmoid)는 $x$ 값을 받아서 0 ~ 1 사이의 값으로 뭉갭니다(squash).

하지만 Sigmoid function은 3가지 문제점이 있습니다.

1. Saturated neurons “kill” the gradients
2. Sigmoid outputs are not zero-centered
3. exp() is a bit compute expensive

Problem 1. Saturated neurons “kill” the gradients

• Sigmoid function의 saturated neuron이 gradient를 죽입니다.
  • 여기서 말하는 saturated 의 의미는 input값이 아주 커지거나 작아져서 sigmoid 함수의 0, 1에 가까운 평평한 곳(거의 수평인 부분)에 위치한다는 의미입니다.
  • ssigmoid function은 처음과 끝 부분에 flat한 형태를 갖고있기에 zero-gradient의 saturated regimes(포화 상태)를 가져 이는 사실상 gradient를 죽게하여 network가 robust한 학습을 어렵게 합니다.
  • 왜냐하면 sigmoid의 경우 양 끝단으로 다가갈수록 gradient는 0에 더 가까워지고, computational graph의 노드에서는 upstream gradient가 0에 근접한 수이면 downstream gradient도 0에 근접하게 되는데, 이 때문에 모델이 ‘deep’ 해질수록 레이어의 gradient가 0이 되어 학습이 진행되지 않는 ‘죽은’ 레이어가 생기게 됩니다.
    • 즉, sigmoid를 사용하면 Sigmoid의 입력이 0 근처의 값이 들어와야만 한다는 강력한 제약조건이 붙습니다.
    • 이러한 saturation을 포함해 $w$ 의 gradient가 0으로 수렴해 update가 중지하는 현상을 gradient vanishing 이라 합니다.

Sigmoid의 그래프와 Sigmoid의 미분 그래프 및 수식을 그려보면 다음과 같습니다.

그래프

[\frac{∂\sigma(x)}{∂x} = \sigma(x)(1-\sigma(x))]

What happens when x = -10?

• $\sigma(x)\ =\ ~0$
• $\frac{∂\sigma(x)}{∂x} = \sigma(x)(1-\sigma(x)) = 0(1 - 0) = 0$
• 즉, $x$ 가 $-$ 로 갈수록 graph에 기울기가 거의 없으므로, gradient가 0이 됩니다.

What happens when x = 0?

• $\sigma(x)\ =\ ~0.5$
• $\frac{∂\sigma(x)}{∂x} = \sigma(x)(1-\sigma(x)) = 0.5(1 - 0.5) = 0.25$
• 즉, $x = 0$ 근처 일때 graph에 기울기가 있으므로, 적절한 gradient를 얻을 수 있습니다.

What happens when x = 10?

• $\sigma(x)\ =\ ~1$
• $\frac{∂\sigma(x)}{∂x} = \sigma(x)(1-\sigma(x)) = 1(1 - 1) = 0$
• 즉, $x$ 가 $+$ 로 갈수록 graph에 기울기가 거의 없으므로, gradient가 0이 됩니다.

정리하자면, input $x$ 가 다소 정성적인 표현이지만, 조금만 크거나 작은값이라면 sigmoid function을 사용할 때 backprop과정에서 local gradinet(dL/dw)는 0에 가깝게 수렴하게 되고, 이는 upstream gradient가 어떻든간에 chain rule을 통해 downstream gradient가 0에 가까운 매우 작은값만큼 update됨을 뜻합니다. 이는 이후의 backprop에서도 layer들도 saturation 되어 w가 매우 작은 값으로 update됩니다.

이러한 현상을 gradient가 killed 되었다라고 표현하며, 더 나아가 Deep neural network에서 saturation을 포함해 계속해서 1보다 작은 값들이 곱해지다 보면 $w$ 의 gradient가 0으로 수렴해 update가 중지하는 현상이 발생하는데, 이를 gradient vanishing이라 합니다.

Problem 2. Sigmoid outputs are not zero-centered

• Sigmoid function의 output이 zero-centered가 아니라 input이 어떻든지 항상 0~1 사이의 positive값을 출력합니다.
• 뉴런의 뒤쪽 레이어 뉴런들이 0이 중심이 아닌 데이터를 얻기 때문에 경사하강법의 dynamics에 영향을 미치게 됩니다.
• 이전 layer에서 sigmoid function을 사용했다고 하였을때 input $x^{(l)}$ 는 positive값이 되고 이때 $w^{(l)}$ 의 gradient는 어떻게 되는지 생각보겠습니다.
  • $x^{(l)}$ 이 항상 positive이기 때문에 $w^{(l)}$ 에 대한 local gradient는 항상 positive입니다.
  • $f = \sum w_ix_i + b \ \frac{∂f}{∂w_i} = x_i = (positive) \ \frac{∂L}{∂w_i} = \frac{∂L}{∂f}\frac{∂f}{∂w_i} = \frac{∂L}{∂f}x_i$
  • 위 상황에서 sigmoid는 $\frac{∂f}{∂w_i} = x_i$ (local gradient)가 항상 양의 값이기 때문에, $\frac{∂L}{∂w_i}$ 는 $\frac{∂L}{∂f}$ (upstream gradient)와 항상 같은 부호를 갖게 됩니다.
• 정리하자면 sigmoid function의 input에 모두 양수값 으로 들어가게 된다면, 모든 $W$ 에 대한 gradient는 upstream gradient와 같은 부호 (모두 양수 혹은 모두 음수)를 가지게 됩니다.
  • 따라서 모든 gradient는 모두 같은 부호 를 가집니다.
  • 또한 이는 gradient에 의해 $W$ 가 학습되는 방향을 제한 시키게 됩니다.
  • 즉, 파라미터 업데이트를 할 때 모두 같이 증가하거나, 모두 같이 감소할 수 밖에 없습니다.

• 따라서, Optimal한 solution으로 곧장 나아가지 못하고, 위 슬라이드와 같이 zig zag path 로 나아가게 됩니다.
  • 위 슬라이드의 그림을 2차원의 $W$ 라고 가정하고, x축이 $w1$, y축이 $w2$ 라고 하면 다음과 같이 4분면 중 두가지 경우(방향)로만 움직이게 됩니다.
    • $w1$, $w2$ 가 모두 $+$ 면 gradient의 update는 오른쪽 위로 진행합니다.
    • $w1$, $w2$ 가 모두 $−$ 면 gradient의 update는 왼쪽 아래로 진행합니다.
• 업데이트가 될 수 있는 방향이 제한됨으로써 제한된 방향으로 여러 번 반복하여 gradient를 update 해야합니다.
  • 즉, 위 슬라이드 그림의 파란색 선이 gradient가 update되어야 하는 방향이라고 할 때, 파란색 선과 같이 곧게 뻗어나가지 못하고 빨간색 선과 같이 지그재그로 나아가게 되므로 여러번 gradient 업데이트를 해주어야 하는데, 이는 상당히 비효율적입니다.
• 위와 같은 이유로 zero-centered를 원합니다.
  • 같은 말로 zero-centered가 아니기 때문에 gradient 업데이트가 효율적이지 않습니다.

위 사항들을 정리하면 다음과 같습니다.

• Sigmoid의 출력은 ‘zero-centered’가 아니고 항상 양수이므로, 이 경우 신경망의 각 레이어의 입력은 양수만 존재한다는 의미이고, 즉 $x^{(l)}$ 이 항상 positive이기 때문에 $w^{(l)}$ 에 대한 local gradient는 항상 positive입니다.
• 하지만 chain rule에 의해 곱해질 upstream gradient는 positive값이 될 수도 negative값이 될 수도 있습니다. 이는 (update되어야할)downstream gradient가 항상 upstream gradient의 부호(positive or negative)와 같아진다는 것이고, 이는 항상 같은 부호를 갖고(+ or -) update가 되어 아래의 그림과 같은 zigzag pattern현상이 발생하여 학습(update)속도가 느려지게 됩니다.
• 또한 이러한 움직임으로 인한 노이즈는 데이터의 차원이 크면 클수록 많아집니다. 특히 step의 크기, learning rate가 크면 이러한 노이즈는 더욱 증가합니다.
  • 하지만 이 문제는 데이터 1개에 대해서 학습을 진행하기보다 mini batch를 사용한다면 어느 정도 방지할 수 있습니다.
  • mini batch를 사용하면 weight의 step은 각 batch의 step의 합으로 이루어져 있기때문에 weight의 모든 원소에 대한 step의 부호가 같은 일(all negative, all positive)은 일어나기 힘들기 때문입니다.

Problem 3. exp() is a bit compute expensive

• 또한 Sigmoid의 $exp()$ 는 비싼(cexpensive) 연산을 가지고 있습니다.
  • 즉, $exp()$ 연산이 다른 기본 연산(+,- 등) 에 비해 복잡하고 시간이 걸립니다.
  • ‘ReLU’와 같은 것들에 비하면 매우 값비싼 연산입니다.
  • GPU를 사용할 때는 메인 메모리와 GPU 메모리 간의 데이터 이동이 대부분의 시간을 잡아먹기에 상관이 없지만, 모바일에서 구동할 때나, GPU를 사용할 수 없는 환경에서는 매우 치명적인 문제가 됩니다.
• 하지만, 이 문제는 다른 문제들에 비해 큰 문제까지는 아닙니다.

Activation Function: Hyperbolic Tangent(tanh)

• 다음은 Hyperbolic Tangent(tanh) activation function 으로 squash된 형태입니다.
• tanh는 sigmoid 함수와 유사하지만, 큰 차이점은 tanh는 zero-centered 되었다는 점입니다. tanh 함수는 입력값을 받아 -1 ~ 1 사이의 output 을 출력합니다.
  • zero-centered(0에 중심) 되어있으므로, single element에 대해서 $w$ 의 그래디언트 방향이 다양해질 수 있습니다.
• tanh function은 기본적으로 scaled and shifted version of sigmoid으로 zero-centered 문제는 해결 하였지만 여전히 x가 크거나 작은 값일때, saturation현상 을 갖게됩니다.
  • 여전히 saturated 되는 구간에서 gradient가 평평해져 gradient가 0으로 수렴하는 문제(kill gradient)가 있습니다.
  • 즉, gradient vanishing 문제가 여전히 존재 합니다.
• 또한 exp term이 4개라 연산속도가 느립니다.

Activation Function: Rectified Linear Unit(ReLU)

• 다음은 ReLU activation function으로, non-linear하면서 가장 심플하여 가장 빠르고, 입력이 음수면 값이 0, 양수면 입력 값 그대로를 출력합니다.
• 장점
  • +의 구간에서 saturation되지 않습니다.
    • 즉, input의 절반은 saturation되지 않고 gradient가 살아있습니다.
    • input이 positive값이라면, 아무리 큰 값이어도 kill될 일은 없습니다.
  • 단순히 max 연산이라서 계산 효율 및 연산 속도가 굉장히 빠릅니다.
    • 음수 부분을 일부 정보에 대한 무시와 수용이 일어난다고 볼 수 있습니다.
    • AlexNet에서 sigmoid, tanh에 6배가량 빠르게 loss에 수렴합니다.
    • 따라서, sigmoid나 tanh에 비해 더 빨리 수렴하게 됩니다.
  • 실제 생물학적으로도 sigmoid보다 생물학적 뉴런과 더 유사한 출력 형태입니다.
• 단점
  • sigmoid 처럼 zero-centered가 아닙니다.
    • output이 positive 또는 0 값만을 갖기에 not zero-centered ouput 문제를 가지므로, 여전히 zig-zag pattern 현상을 겪습니다.
  • x가 0보다 작은 영역에서 gradient가 죽어버립니다.
    • input이 양수일때는 saturated 되지않지만 반대로 음수일때는 local gradient가 정확이 0을 갖게되어, 역전파시 downstream gradient은 0이 되고, 이후 계속 0을 전파하여 saturated되는 문제를 가집니다.
      • sigmoid는 0에 수렴한 값을 갖지만(output으로) ReLU는 명백히 zero-gradient를 갖기에 아예 update가 멈추게 됩니다.
    • 즉, ReLU 에서 input이 음수일때는 sigmoid에서 발생하던 문제와 동일하게 saturated되어 전체 gradient의 절반이 죽어버리는(0이 되어버리는) 문제가 발생합니다. -> dead ReLU
    • 따라서, initialization에서 운이 좋지 않은 몇개의 neuron들은 gradient가 update가 되지 않습니다.

• ReLU gate의 local gradient는 0 또는 1입니다.
  1. x = -10
     • local gradient가 0이므로, downstream도 0이 됩니다.
  2. x = 0
     • 부동소수점 연산을 하므로, 고려하지않아도 되는 상황입니다.
  3. x = 10
     • local gradient가 1이므로, upstream값이 그대로 downstream으로 전달됩니다.

• 위 슬라이드와 같이 traing data들이 분포한다고 할때, 데이터들이 분포하는 위치를 data cloud라고 생각하겠습니다.
• ReLU는 가중치 평면(초록 빨강 직선)의 절반(한 쪽 방향)만 activate 한다는 것을 알 수 있습니다.
  • 즉, ReLU를 지나면서 절대 그래디언트가 업데이트되지않는 영역이 생길 수 있습니다.
  • 가중치 평면이 data cloud와 멀리 떨어져 있으면, input data에 대해서 activate 되지 않고 가중치(W)가 업데이트 되지 않아 “dead ReLU” 가 발생할 수 있습니다.
  • 업데이트가 정상적으로 되기 위해서는 위 그림에서 초록색 가중치 평면 처럼 activate되는 data들이 존재하여 gradient가 살아있어야합니다.

몇 가지 이유로 이런 일이 발생할 수 있습니다.

• 첫 번째는 $W$ 초기화를 잘못했을 경우
  • $W$ 초기화 시 $W$ 평면이 input data cloud와 멀리 떨어진 값으로 초기화 되었을때 dead ReLU 현상이 발생합니다.
• 두 번째는 learning rate가 지나치게 높은 경우
  • 처음에 적절한 $W$ 평면에서 시작하더라도 학습과정 중에 learning rate가 높아 지나치게 크게 update 해서 $W$ 평면이 data cloud와 멀리까지 가버린다면 dead ReLU 현상이 발생합니다.
  • 즉, 처음에는 학습이 잘 되다가 갑자기 죽어버리는 경우 입니다.
• 실제로 학습을 다 시켜놓은 네트워크를 살펴보면, 10~20% 가량은 dead ReLU가 되어 있습니다.
  • 하지만 네트워크 학습에 크게 지장이 있지는 않습니다.

실제로 ReLU를 초기화할 때 positive biases(0.01)를 추가해 주기도 합니다. 이는 가중치를 업데이트 할 때 active ReLU가 될 가능성을 높여주기 위함입니다.

참고로 모든 ReLU 계열의 함수들은 0에서 미분이 불가능하여 임의로 0+나 0-에서의 gradient 값으로 선택하는데, 확률적으로 입력이 0으로 주어지는 경우는 매우 드물기에 어떤 것을 선택하던지 상관없습니다.

Activation Function: Leaky ReLU & PReLU

• Leaky ReLU
  • ReLU를 변형한 형태입니다.
  • Dead ReLU문제점 해결을 위해, negative값에 대한 그래디언트 값을 0으로 만드는 것 보다 조금이라도 업데이트되는 방안을 고려했습니다.
  • x가 0보다 작은 영역에서도 작은 기울기를 줌으로써 saturation하지 않습니다.
  • 여전히 max연산을 사용하므로, sigmoid나 tanh에 비해 ReLU와 동일하게 계산에서 효율적입니다.
  • 결과적으로 saturation되지 않아 ReLU 에서 발생하는, neuron이 죽는 문제(dead ReLU)를 해결</span>** 했습니다.
• Parametric Rectifier(PReLU)
  • Leaky ReLU에서 0.01을 하드코딩한 것과 달리, 이 값을 $α$ 라는 learnable parameter(backprop으로 학습됨)로 조절하는 형태로, backpropagation단게에서 $α$ 에 대한 그래디언트가 계산되어 업데이트가 됩니다.
  • Leaky ReLU에 더 많은 유연성을 제공 합니다.

Activation Function: ELU

• ELU(Exponential Linear Units)는 ReLU의 이점들을 모두 가져오며 더 smooth 합니다.
• 출력값이 zero-mean와 가까워져 sigmoid와 ReLU에서 발생한 zero-centered가 되지 못해 학습이 비효율적으로 이루어진다는 문제점을 해결했습니다.
• 지수함수를 이용하여 입력이 0이하일때 부드러운 곡선을 갖습니다.
  • ReLU와 Leaky ReLU의 중간 형태
  • ReLU의 ‘음수값을 0으로 죽이는 문제’에 대해 leaky relu보다 노이즈에 더 강건하게 대응합니다.
  • 의도적으로 negative saturation regime을 설계했는데, Negative 영역은 noise일 확률이 높기 때문에 학습을 하면 overfitting 되거나 성능에 악영향을 미칠 수 있으므로, x가 0보다 작은 영역에서 약간의 saturation을 허용하는 것(neuron(gradient)이 죽는 것)이 noise에 조금 더 robust 하다는 주장입니다.
• 연산에 exp()이 포함되어 있습니다.
  • exp 연산의 결과값에 1을 빼주는데, 이는 gradient가 0이 나오는 것을 막기 위해 사용한다고 하며, 거기다 임의의 hyperparameter alpha를 곱해서 스케일 해줍니다.
  • 기존 ReLU의 문제를 해결할 수 있지만 exp 연산의 비용이 ReLU와 비교하면 매우 크다는 한계를 가집니다.

Activation Function: SELU

• SELU(Scaled Exponential Linear Units)는 심층 신경망의 자기 정규화(Self-normalizing)에 더 잘 작동하는 ELU의 확장 버전입니다.
  • 아주 deep한 네트워크를 설정하면, BatchNorm없이도 계속 activate되는 람다, 알파값들이 mean = 0, sd = 1로 normalization된 후, 다음 레이어에 들어갑니다.
  • 즉, 배치 정규화(Batch Normalization)없이 심층 SELU 신경망을 학습할 수 있습니다.

Activation Function: Maxout

• Maxout Neuron은 ReLU와 Leaky ReLU를 일반화한 형태입니다.
  • 2개의 linear function에서 max연산을 취하기 때문에 일반화라고 표현했습니다.
  • maxout은 두 가지 파라미터들($W$, $b$)을 각각 연산에 더 큰 값을 선택하는 방식으로 진행됩니다.
• 장점으로, Linear이므로, saturate하지 않아서 neuron이 죽는 문제가 없습니다.
• 단점으로, 뉴런당 파라미터의 수가 2배가 됩니다.

Activation Function Summary

• 유명한 네트워크 아키텍쳐에서는 활성함수의 차이가 크게 나지 않습니다.
• 또한 네트워크 아키텍쳐마다 제일 accuracy가 높은 활성함수가 다른 것으로 보입니다.

• Activation Function에 대해서 정리하자면,
  • 특별한 이유 없으면 ReLU를 쓰면 무난하다.
  • 따라서, ReLU를 사용하고, 만약 더 높은 accuracy를 끌어올려야하는 상황이라면, Leaky ReLU, ELU, SELU, GELU를 활용해보면 됩니다.
  • 다만 sigmoid와 tanh의 사용은 피해야 합니다.
• 그리고 지금까지 다룬 Activation Function 모두 단조함수인데, 단조함수가 아니라 Cosine 함수 같은 그래프를 그리는 함수를 사용할 경우, 모델의 학습에 문제가 생기기 쉽습니다.
• 그래도 불가능한 것은 아니라서 드물게 사용되기는 하지만, GELU와 같이 단조함수가 아닌 activation도 있습니다.

Data Preprocessing

• 일반적인 머신러닝 문제에서 실제 네트워크를 훈련시킬 때는 zero centering 후, standard deviation으로 normalize를 수행합니다.
  • Input이미지가 2차원상의 점 하나에 대응된다고 가정할 때, Original데이터가 타원형으로 펼쳐져 있습니다.
    • 0번째 dimension: 샘플 하나하나 해당
    • 1 ~ 3번째: 컬러채널, 세로, 가로에 해당
  • Zero-centered data
    • data 자체를 dim=0에 대해 mean시켜서, $X$ 에 대해서 빼주는 것입니다.
    • 데이터 군집을 모든 차원에 대해 원점으로 이동시킨다는 의미가 있습니다.
    • 즉, 데이터를 중앙으로 모이게 해줍니다.
    • 평균을 0 으로 만들어 zero-centered 한 데이터로 만들어주는 이유는 sigmoid 활성화 함수의 zero-centered가 안되었을때 발생하는 문제점을 생각하면 되는데, data가 모두 양수이거나 모두 음수일 경우, backpropagation 과정에서 gradient가 모두 같은 부호가 되어 학습이 비효율적인 방향으로 일어난다는 문제가 발생했기 때문에, 이러한 방법론을 사용합니다.
  • Normalized data
    • 각 variable별로 std를 샘플에 대해서 reduction해서 나누는 것입니다.
    • Normalize를 한 후, 위 아래와 좌우의 변동성이 균등하게 조절됩니다.
    • 즉, 데이터를 특정 범위 안으로 모이게 해줍니다.
    • normalization 을 수행하는 이유는 입력 데이터의 모든 차원이 동일한 범위 내에 있게 만들어줘서 동등한 기여(contribution)을 하게 함을 위한 것입니다. 만약 특정 차원의 분포만 엄청 넓게 있다보면 해당 차원의 데이터만을 중요하게 학습하게 될 것이기에, 모든 차원의 데이터를 같은 분포로 전처리 해줍니다.
• 즉, 모델을 학습시키기 전에 데이터를 전처리를 함으로써 데이터의 분포를 개선시키는데, 각 데이터에 평균을 빼서 데이터가 zero-centered 하게 만들고, 표준편차로 나눔으로써 각 feature들의 분산을 동일하게 해줍니다.

그렇다면 궁극적으로 왜 preprocessing이 필요할까?

• non zero-centered를 생각해보면, 만약 모든 데이터가 양수 혹은 음수를 가지는 경우 gradient도 한쪽으로 편향되어 update되는데 데이터의 평균을 0으로 만들어 주면 이를 방지할 수 있습니다.
• 즉 Loss가 최소인 지점은 변하지 않지만, preprocessing을 하면 gradient계산에 조금 유리해집니다.
  • Before normalization
    • 분류 손실(classification loss)은 가중치 행렬의 변화에 매우 민감하며, 최적화하기 어렵습니다.
    • Center가 0이 아니게 데이터들이 분포해있습니다. 이런 경우에서 만약 decision boundary의 slope가 조금 바뀐다면, slope의 미미한 변화에도 데이터의 분류 상황이 많이 바뀌며, classification loss가 많이 바뀝니다. 결론적으로 optimization process를 어렵게 만듭니다.
  • After normalization
    • 가중치의 작은 변화에 덜 민감하고, 최적화하기 쉽습니다.
    • 원점에 데이터들이 분포해있습니다. 이런 상황에서는 작은 변화에 덜 민감합니다. 따라서 optimization process가 비교적 쉬워집니다.

• Machine learning에서 정형데이터의 경우, PCA나 whitening 같이 더 복잡한 전처리 과정도 있습니다.
  • 이는 각각 decorrelated data, whitened data를 뜻합니다.
  • image 데이터를 다룰 때에 굳이 쓰지않음
• 실제로, image 데이터의 경우는 데이터 전처리 과정으로 zero-mean만 수행하고, 다른기법은 잘 사용하지 않습니다.
  • 보통 이미지는 각 차원의 분포가 또는 각 차원 간의 크기(scale)가 이미 어느 정도 동일하게 만들어졌기 때문입니다.
    • ex. RGB 값은 각 차원 모두 0~255 사이의 값을 가짐
  • 일반적으로 이미지를 다룰 때는 PCA같이 더 낮은 차원으로 정사영(projection)시키지 않습니다.
  • CNN에서는 원본 이미지(original data) 자체의 공간 정보를 활용해서 이미지의 공간 구조를 확보할 수 있습니다.
  • 엄밀하게 따지자면, 첫번째 layer의 input에서만 zero mean이 되고, 네트워크가 깊어지면서 데이터는 zero mean이 되지 않음

Data Preprocessing Summary

• 정리하자면 다음과 같습니다.
  • image data를 다룰때는 기본적으로 zero-mean 으로 전처리를 해줍니다.
  • 하지만 일관적이지 않으며, 각 모델 또는 데이터에 맞게 진행해 주면 됩니다.
  • 다음은 zero-mean을 하는 대표적인 process 입니다.
    1. 전체 데이터의 평균을 구해서 각 데이터마다 그 평균 값을 빼주는 방법
    2. 전체 데이터의 각 채널 마다 평균을 구해 각 데이터의 채널마다 해당 채널의 평균을 빼주는 방법

Weight Initialization

• Weight Initialization 은 처음에 weight가 어떤 값으로 초기화되느냐에 따라서 모델 학습이 잘 되는지 안되는지를 결정하기 때문에, 이 부분은 굉장히 중요한 부분입니다.
• 만약 fully-connected network에서 모든 Weight를 0으로 초기화(또는 모두 같은 값으로 초기화)한다면 어떻게 될까?
  • 0으로 모두 초기화 를 하면, 해당 layer의 output이 input에 상관 없이 모두 zero가 될 것이이며 (activation funcion이 ReLU일 경우) gradient도 zero가 될 것입니다(마지막 bias 제외). 이는 weights update가 되지 않는다는 뜻이고 학습이 되지 않습니다.
  • Constant로 초기화 해도 모든 neuron의 gradient가 같아질 것이기 때문에 “not having symmetry breaking” 라고 표현하며, 이는 어느 neuron(one hidden unit)이던 forward pass에선 모든 input feature에 대해 같은 weights로 반응하며, backprop 에선 모든 feature에 대응하는 weights들이 same gradient가 적용되어 같은 크기로 update된다는 것을 의미합니다.
  • 이 때문에 모두 같은 방식으로 update가 되며, 모든 neuron이 같아지게 되는 문제가 있습니다.
    • 모델이 이런 상황에 처하게 되는 것을 ‘symmetry braeaking’ 에 실패했다고 하며, 그렇기에 weight을 0 또는 Constant로 초기화해서는 안됩니다.
    • $W$ 의 변화가 없는 것을 딥러닝에서 symmetry라고 표현합니다.
• 그러므로 가중치 초기화시 W와 b가 모두 조금씩 달라서, layer의 모든 노드들이 다른 역할을 하도록 만들어주어야 다음 process에서 각자의 역할을 찾아갑니다.

Test1: Initialize with small random values

• 이전 zero initialization의 문제점을 보완하고자 small random values 로 초기화하려 합니다.
• $W$ 를 작은 난수값으로 초기화(Gaussian distribution, standard deviation = 0.01)하면 어떻게 될까?
  • zero-mean, unit-std를 갖는 가우시안 분포를 따르는 값들을 0.01 scaling 시켜주어 (std=0.01 로 만듦) 초기화시켜준 것입니다.
  • 작은 네트워크에서는 symmetry breaking 할 수 있어서 괜찮지만, 깊은 neural networks에서는 문제가 됩니다.

• 깊은 네트워크에서의 문제를 위 슬라이드를 통해 더 자세히 살펴보겠습니다.
  • Forward pass에서의 문제
    • 서로 작은 $W$ 값들을 계속해서 곱하면서 이 값들이 매우 빠르게 작아지기 때문에 Activaiton이 0이 됩니다.
    • 처음에는 mean = 0에 적당한 std로 분포되어 있지만, layer가 쌓이면서 점점 0쪽으로 sqeeuze된다. 즉, activated값이 균질하지 않아집니다.
    • 이러한 문제가 발생하는 이유는 $W$ 가 너무 작은 값이다보니 $Wx$ 연산 과정을 하고 tanh을 거친 출력값들 또한 엄청 작은 값이 나오게 될 것이고, 이 과정이 반복되어 깊은 레이어에서는 거의 0에 수렴하는 출력값이 나오게 될 것입니다.
  • Backward gradient update에서의 문제
    • 작은 $W$ 값으로 인해 input $x$가 매우 작습니다. 즉 점점 0에 수렴합니다.
    • 따라서, local gradient $dW/df = x$ 도 작아지고, 결국 가중치는 아주 작은 gradient를 얻게 되어 update가 일어나지 않게 됩니다.

Test2: Initialize with big random values

• 큰 난수값 으로 초기화(Gaussian distribution, standard deviation = 0.05)하면 어떻게 될까?
  • $W$ 가 1또는 -1에 수렴하게 됩니다.
  • 이때, local gradient 계산시, tanh함수는 -1, 1값에 대해 gradient를 0근처로 반환한다. 따라서 또 다시 학습이 거의 되지않습니다.
  • 따라서, 값들이 saturation 되어 gradient가 0이되고, update가 일어나지 않습니다.

Xavier Initialization

• 큰 난수값과 작은 난수값 모두 문제가 있습니다. 따라서, 적절한 값으로 초기화 하는 방법이 필요합니다.
  • 보통 랜덤하게 초기화된 뉴런의 출력값은 input 개수가 많아질수록 큰 분산을 갖는다고 합니다.
• Xavier Initialization 은 입력과 출력의 분산이 동일하도록 하는 초기화 방법 입니다.
  • 입력의 분산이 출력의 분산과 동일하도록 weight가 어떻게 되어야 할지를 유도하면, Xavier Initialization의 공식을 얻을 수 있습니다.
  • 가우시안 분포에서 뽑은 값을 input 수의 제곱근으로 나누어 스케일링함으로써 $W$ 값을 정합니다.
  • 각 레이어의 출력값들이 비슷한 분포(가우시안 분포)를 가지는 것을 시각적으로 확인할 수 있습니다.
  • 또한 이러한 분포를 가지는 출력값들이 active region에 있다는 가정이 있어야 학습이 잘 이루어질 수 있습니다.
• Xavier Initialization의 동작 예
  • 입력이 작다면 더 작은 수로 나누게 되고, 더 큰 weight를 얻게 됨
    • 작은 입력과 큰 weight를 곱하므로, 적절한 값이 나오게 됩니다.
  • 입력이 크다면 더 큰 수로 나누게 되고, 더 작은 weight를 얻게 됨
    • 큰 입력과 작은 weight를 곱하므로, 적절한 값이 나오게 됩니다.

• 결국 Xavier Initialization의 목표는 output노드들의 activation variance와 input노드들의 activation variance가 같도록하는 것 입니다.
  • Let: $y\ =\ x_1w_1\ +\ x_2w_2\ +\ …\ +\ x_{Din}w_{Din}$
  • Assume: $Var(x_1)\ =\ Var(x_2)\ =\ …\ =\ Var(x_{Din})$
  • $Var(y) \ =\ Var(x_1w_1\ +\ x_2w_2\ +\ …\ +\ x_{Din}w_{Din}) \ =\ Din\ *\ Var(x_iw_i)$
  • X와 W가 독립적이라는 가정하에, $Var(x_iw_i)\ =\ (E[x^2_i]E[w^2_i]\ −\ E[x_i]^2E[w_i]^2)$
  • X와 W가 평균이 0라고 가정하면, $(E[x^2_i]E[w^2_i]\ −\ E[x_i]^2E[w_i]^2)\ =\ E[x^2_i]E[w^2_i]\ =\ Var(x_i)Var(w_i)$
  • 이때, $Var(w_i)\ =\ \frac{1}{Din}$ 으로 설정하면, 결과적으로 $Var(x_i)\ =\ Var(y_i)$ 가 됩니다.

He Initialization

• ReLU는 절반의 unit을 죽이기 때문에 Xavier를 사용해서 얻은 분산의 절반이 없어지게 됩니다.
  • 즉 출력의 분산을 반토막 내버려, 출력의 분포가 점점 줄어들게 되므로 ReLU에서는 Xavier initialization이 적절하지 않습니다.
  • 레이어를 거칠때마다 출력의 분산을 반으로 줄이게 되며, 점점 더 많은 값들이 0이 되고, 결국 비활성(deactivated) 됩니다.

• He Initialization 은 Xavier에서 입력을 2로 나눈 초기화 방법 입니다.
  • 즉, $W$ 를 초기화 할때 가우시안분포를 따라 샘플링한 값을 input의 개수를 절반으로 나눈 값에 제곱근을 나누어 스케일링하는 방법을 사용합니다.
  • Xavier를 사용하면 얻은 분산의 절반이 없어지므로, Xavier의 식에서 입력을 2로 나누게 되면 위와 같이 출력의 분포가 줄어들지 않게 됩니다.

Weight initialization은 다양한 방법으로 연구되고 있으며, 우선은 Xavier initialization을 추천합니다.

Batch Normalization

• Batch Normalization 은 모델의 internal covariate shift를 줄임 으로써 learning process를 더 가속화시키는 역할을 함으로써 더 높은 learning rate와 더 빠른 convergence을 허용하고, 모델 weight initialization의 영향을 줄이며, regularize 역할을 합니다.
• 지금부터 Batch Normalization로 가기위한 Motivation 부터 시작하겠습니다.

Motivation: Gradient Vanishing & Exploding Problem

Neural Network에서의 학습시 Global optimization를 하기위해 stochastic gradient descent등의 알고리즘을 통해 parameter(weight and bias)와 Loss간의 관계를 Gradient 기반으로 학습시켜 parameter들을 update 합니다. 이때 parameter의 값들이 Vanishing 또는 Exploding 된다면 학습이 불안정하게 수행되어 Error rate 가 낮아지지 않고 수렴해버리는 문제가 발생하게 됩니다. 결과적으로 Neural Network을 효과적으로 학습시키지 못합니다.

Motivation: How to speed up training?

• Gradient vanishing
  • backpropagation algorithm에서 아래 layer로 내려갈수록, 현재 parameter의 gradient를 계산했을 때 앞에서 받은 미분 값들이 곱해지면서 그 값이 거의 없어지는 (vanish하는) 현상을 의미합니다.
• Gradient exploding
  • learning rate가 너무 높아 diverge하는 현상을 말합니다.

deep neural network의 train 속도를 높이는 것은 일반적으로 전체적인 성능 향상에 도움이 됩니다. train의 속도, 즉 gradient method의 converge 속도를 빠르게 하기 위해서는 learning rate를 높게 설정합니다.

하지만 Learning rate의 값이 크면 이 두 가지 현상이 발생할 확률이 높기 때문에 우리는 보통 작은 learning rate를 고르게 됩니다. 그러나 일반적으로 learning rate의 값이 diverge하지 않을 정도로 크면 gradient method의 converge 속도가 향상됩니다.

따라서 본 논문이 던지는 질문 은 다음과 같습니다.

• Gradient vanishing/exploding problem이 발생하지 않도록 하면서, input이 zreo-centerd하게 하면서, learning rate 값을 크게 설정할 수 있는 neural network model을 어떻게 design할 수 있는가?

Internal Covariate Shift

Gradient vanishing problem이 발생하는 이유에 대해서는 여러가지 설명이 가능하지만 이 논문에서는 internal covariate shift라는 개념을 제안합니다.

• Covariate(공변량) : 종속변수에 대하여 독립변수와 기타 잡음인자들이 공유하는 변량
  • 다른말로 실험 설계에 독립변수로 설정되어 있지 않았지만, 종속변수에 영향을 미칠 수 있기 때문에 통제되어야 할 변수를 말합니다.
  • 즉, 독립변수와 종속변수의 관계를 명확하게 밝히려 할 때 방해가 될 수 있는 요인입니다.
• Covariate shift : machine learning problem에서 train data와 test data의 data distribution이 다른 현상을 의미 합니다.
  • DNN에서 training data를 잘 학습시켜 test data를 잘 분류해야 하기 때문에, DNN 모델이 가지는 가중치는 같은 분포를 띄어야 합니다.
  • 또한 DNN train은 이전 계층에 비선형성을 적용한 후 다음 계층에 대한 입력으로 출력한다는 사실 때문에 복잡합니다. 훈련하는 동안 이전 계층의 매개변수가 변경되기 때문에 입력 분포가 변경됩니다.
  • 서로 다른 분포를 가지는 현상을 covariate shift라 합니다.
• Internal Covariate shift : 레이어를 통과할 때 마다 Covariate Shift 가 일어나면서 입력의 분포가 변하는 현상 을 의미합니다.
  • 논문에서는 단순히 train/test input data의 distribution이 변하는 것 뿐 아니라, 각각의 layer들의 input distribution이 training 과정에서 일정하지 않기 때문에 문제가 발생한다고 주장 하며, 이렇게 각각의 layer들의 input distribution이 consistent하지 않은 현상을 internal convariate shift라고 정의합니다.

논문에서 이것이 문제가 된다고 주장하는 이유는, 각각의 layer parameter들은 현재 layer에 들어오는 input data 뿐만 아니라 다른 model parameter들에도 영향을 받기 때문이라고 합니다.

기존에는 이런 현상을 방지하기 위하여, activation function를 변경하거나, Careful initialization를 하거나, leanring rate를 작게 취하는 등의 전략을 사용했지만, 그런 방법이 아닌 다른 방법을 통해 internal covariate shift 문제가 해결이 된다면 학습하는 과정 자체가 전체적으로 안정화되는 동시에 더 높은 learning rate를 선택하여 learning 속도를 빠르게하는 것이 가능할 것입니다.

따라서 본 논문의 목표는 internal covariate shift를 줄이는 것 입니다.

bad approach: Whitening

• Whitening
  • 각 layer의 input distribution을 zero mean, unit variance를 가지는 normal distribution으로 normalize
  • 주어진 column data $X∈R^{d×n}$ 에 대해 whitening transform은 다음과 같습니다.

[X̂ = Cov(X)^{−1/2}X, Cov(X)=E[(X−E[X])(X−E[X])^⊤]]

• 그러나 이런 approach에서는 문제점들이 발생하게 됩니다.
  • multi variate normal distribution으로 normalize를 하려면 inverse의 square root를 계산해야 하기 때문에 필요한 계산량이 많다.
  • 전체 데이터를 기준으로 mean/variance를 training마다 계산하면 계산량이 많이 필요하다.
  • 또한 일부 parameter(bias)들의 영향이 무시됩니다.

따라서 이 논문에서는 이런 문제점들을 해결할 수 있으면서, 동시에 everywhere differentiable하여 backpropagation algorithm을 적용하는 데에 큰 문제가 없는 간단한 simplification을 제안합니다.

nice approach: Batch Normalization Transform

• 앞서 제시된 문제점들을 해결하기 위하여 본 논문에서는 두 가지 approach 를 제안합니다.
  1. 각 차원들이 서로 independent하다고 가정하고 각 차원 별로 따로 estimate를 하고 그 대신 표현형을 더 풍성하게 해 줄 linear transform도 함께 learning 합니다.
  2. 전체 데이터에 대해 mean/variance를 계산하는 대신 지금 계산하고 있는 batch에 대해서만 mean/variance를 구한 다음 inference를 할 때에만 real mean/variance를 계산합니다.

먼저 Whitening approach에서 covariance matrix의 inverse square root를 계산해야했던 이유는 모든 feature들이 서로 correlated되었다고 가정했기 때문이지만, 각각이 independent하다고 가정함으로써, 단순 scalar 계산만으로 normalization이 가능해집니다. 그럼 다시 슬라이드로 돌아가겠습니다.

• Batch Normalization 은 입력의 mini-batch별로 평균과 분산을 계산해서 normalize하는 방법 입니다.
  • 즉, layer를 통과한 후에도 분포가 Unit gaussian 이 되도록 하는 방법입니다.

• 배치당 NxD shape의 x가 있습니다.
  • N: batch size
  • D: Variable수(이전 hidden 노드의 수)
• 각 차원별로 평균(mean)을 각각 계산합니다.
• 하나의 배치 내에서 전부 계산하여 정규화 합니다.
  • 여기서 $ϵ$ 은 계산할 때 0으로 나눠지는 문제가 발생하는 것을 막기 위한 수치적 안정성을 보장하기 위한 아주 작은 숫자입니다.
• 즉, 각 차원에 대한 경험적 평균과 분산을 독립적으로 계산 합니다.

• 그러나 이렇게 correlation을 무시하고 learning하는 경우 각각의 관계가 중요한 경우 제대로 되지 못한 training을 하게 될 수도 있으므로 이를 방지하기 위한 linear transform을 각각의 dimension D마다 learning해줍니다.
  • 이 transform은 scaling 과 shifting 을 포함합니다.
  • parameter $γ$, $β$ 는 neural network를 train하면서 마치 weight를 update하듯 같이 update하는 model parameter입니다.
• 또 다르게 해석을 하면 Batch Normalization을 진행함으로써 입력을 linear한 부분으로만 제한함으로써 non-linear한 activation function의 영향력이 감소하게 됩니다.
  • 즉 모델의 비선형성을 잃게 되는것입니다.
  • 이를 해결하기 위해 우리는 input의 값을 무조건적으로 linear한 부분에만 제한하는게 아니라 유연하게 조절할 필요가 생깁니다.
  • 또한 실제로는 일부 출력값은 saturation 되어야 노이즈에 좀 더 robust한 경우도 있습니다.
  • 따라서 saturation이 무조건적으로 전혀 일어나지 않는 것보다 얼마나 saturation이 일어날지를 설정할 수 있게 하기위해 scaling과 shifting을 포함합니다.

Batch Normalization: Test-Time

• Training단계에서는 N개씩의 미니 배치 샘플이 적용되지만, Val/test 단계에서는 계산이 이상해집니다.
  • 배치를 뭘로 볼 것인지가 문제가 됩니다.
• 따라서 유의할 것으로, training과 test코드가 다르게 구현되어야 합니다.

• Test에서는 mean과 std를 계산하지 않고, Training 단계마다 기록되는 mean, variance term을 저장했다가 사용합니다.
  • 예를 들어, training에서의 moving average를 사용해서 값을 구하는 방법 등
• 그리고 test에서 추가적 계산 없이 평균이라는 상수를 사용하기 때문에 Batch Normalization은 Linear operator로 볼 수 있게 되고, 그래서 Fully-Connected Layer나 Convolution Layer와 합쳐질 수 있다고 합니다.

Batch Normalization for ConvNets

• Batch Normalization은 Fully-connected network와 Convolutional network에서 모두 사용 가능합니다.
  • Spatial structure가 포함되는 Conv Net 특성상, Batch norm도 spatial dimension을 고려합니다.
• 즉, fully-connected networks에선 N x D의 input x 를 batch N에 대해 averaging(scale and shift) 시켜 D-dim vector에 normalize 시킵니다.
• Conv net에선 batch dimension N에대해 averaging 시킬뿐 만아니라 모든 spatial dimension인 H,W에 대해서도 averaging 하여 C-dim vector 에 normalize 시킵니다.

usually insert

• 주로 Fully connected layer나 Conv layer를 통과한 후에 데이터의 분포가 바뀌기 때문에, 이들을 통과한 후에 batch normalization을 수행하는 것이 일반적 입니다.
  • 엄밀히 따지자면, Fully connected layer와 달리 Conv layer에서는 출력 Activation Map마다 평균과 분산을 가지고 정규화하게 됩니다.

• 장점
  • BN을 씌우니까 더 적은 iteration으로 더 높은 accuracy를 달성합니다.
  • deep network에도 학습이 잘 됩니다.
  • 트레이닝 단계에서 regularizaion의 효과가 있습니다.
  • Test단계에서 추가적인 계산이 필요없습니다.
• 단점
  • 하지만 이론적으로 완벽히 증명된 것이 아닙니다.
  • 트레이닝, 테스트시 다르게 작동하므로 버그가 자주 발생합니다.
• 저자가 주장하는 장점
  • 더 큰 learning rate를 쓸 수 있습니다. internal covariate shift를 감소시키고, parameter scaling에도 영향을 받지 않고, 더 큰 weight가 더 작은 gradient를 유도하기 때문에 parameter growth가 안정화되는 효과가 있다.
  • Training 과정에서 mini-batch를 어떻게 설정하느냐에 따라 같은 sample에 대해 다른 결과가 나옵니다. 따라서 더 general한 model을 learning하는 효과가 있고, drop out, l2 regularization 등에 대한 의존도가 떨어집니다.

Batch Normalization Summary

• Batch Normalization을 요약하면 다음과 같습니다.
  • 입력이 주어지면 미니배치의 평균과 분산을 구하고 normalize합니다.
    • 이때, scaling factor $γ$ 와 shifting factor $β$ 로 normalization의 정도를 조절합니다.
  • Batch Normalization은 gradient flow를 향상시키고, 네트워크를 더 robust하게 해줍니다.
    • 더 많은 learning rate와 다양한 initialization에서 동작하기 때문에 훈련하기 더 쉬워집니다.
  • Batch Normalization은 Regularization의 역할도 수행합니다.
    • 각 layer의 입력(mini batch)은 표본이라고 볼 수 있으므로, 이들의 출력이 normalize되는 것은 각각 표본평균과 표본분산을 통해 normalize되는 것이라고 볼 수 있습니다. 이는 각 layer의 출력은 더이상 해당 mini batch에만 deterministic한 것이 아니라, 전체 데이터들에 영향을 받게 되는 것이라고 해석할 수 있습니다.
    • 즉, X의 representation이 약간씩 jitter되면서 일종의 regularization 효과를 얻게 되는 것입니다.

Babysitting the Learning process

• 이제 학습 과정을 어떻게 모니터링하고 좋은 성능을 내는 하이퍼 파라미터를 어떻게 설정할 것인가 에 대해 살펴보겠습니다.
• 모델 학습의 전반적인 과정에 대해 단계별로 살펴보겠습니다.

Preprocess the data

• 우리가 가장 먼저 해야할 일은 데이터 전처리 입니다.
  • zero-mean을 사용합니다.

Choose the architecture

• 그 다음으로는 어떤 아키텍쳐를 사용할지 선택해야합니다.
  • 하나의 hidden layer 와 50개의 뉴런을 가진 모델을 사용해봅니다.

Double check that the loss is reasonable

• Loss function도 잘 동작하는지 검사합니다.(sanity check)
  1. Loss가 잘 계산되는지 검사합니다.
     • softmax를 사용하여 -log(1/class수)가 되어야 하기 때문에 -log(1/10) ~ 2.3이 나오는지 검사합니다.
  2. 약간의 Regularization을 주었을 때, Loss가 증가하는지 검사합니다.

train

• 모델학습을 시작합니다.
  • 처음에는 작은 양의 일부 데이터만을 이용해서 Loss가 잘 줄어드나를 확인해야합니다.
  • 이 과정에서 데이터가 적음으로 인해 overfit이 생겨야합니다.
    • 즉, loss가 엄청 작은 값까지 내려가고 accuracy가 엄청 높아야합니다.
  • 이때는 regularization를 사용하지 않습니다.
• 실험을 살펴보면 다음과 같습니다.
  • Loss가 내려감과 동시에 Train Accuracy는 점점 증가합니다.
  • 데이터가 작은 경우라면 모델이 완벽하게 데이터를 overfit할 수 있어야 합니다.

• 모든 sanity check 가 완료됐다면,다음으로 전체 데이터를 이용해 실제학습을 합니다.
• 약간의 regularization을 준 상태에서 최적의 learning rate을 찾습니다.
  • 이때, loss가 크게 변하지 않는다면, learning rate가 작은 경우입니다.
  • Learning rate는 가장 중요한 하이퍼파라미터 중 하나로, 가장 먼저 정해야만 하는 하이퍼파라미터 입니다.
• 위 슬라이드에서와 같이 learning rate를 1e-6으로 설정 후 훈련시, loss는 큰 변화가 없지만 accuracy만 증가하게 되는 경우도 있습니다.(loss는 큰 변화 없지만, accuray는 20%까지 증가)
  • 전체 확률은 널리 퍼져있고, softmax의 loss도 이와 매우 유사하다.
  • 학습이 진행되면서 올바른 방향으로 전체 확률을 약간 이동시킨다면, loss는 여전히 분산되어 있지만 accuracy는 최대로 맞힌 횟수를 헤아리기 때문에 accuracy만 갑자기 증가할 수 있습니다.

• learning rate를 크게하면(앞에서는 1-e6인데 여기서는 1e6), loss가 exploding하게 됩니다.
  • 결과를 보면 cost가 NaNs, 즉 cost가 발산(exploded)했습니다.
  • 주된 이유는 learning rate가 지나치게 높기 때문입니다.

• 이러한 경우에는 다시 값을 줄여서 시도해보고, 그래도 크다면 조금 더 줄이고, 너무 작다면 다시 키우면서 최적의 learning rate를 찾아가면 됩니다.
  • 이 경우 learning rate를 낮춰야하기 때문에, 3e-3으로 했는데, 여전히 발산합니다.
• 보통 learning rate는 1e-3 에서 1e-5사이의 값을 사용합니다.(해당 데이터 한정)
• 이 범위 사이의 값을 이용해서 cross-validation 을 수행해 줍니다.
  • 사이의 값들을 이용해서 learning rate가 지나치게 작은지 아니면 큰지를 결정할 수 있습니다.

Hyperparameter Optimization

하이퍼 파라미터를 어떻게 최적화시키고 그중 가장 좋은 것을 선택하려면 어떻게 해야 하는지 살펴보겠습니다.

Cross-validation strategy

• 하이퍼파라미터 최적화는 다음의 단계로 수행합니다.
  • First stage
    • 하이퍼파라미터 값을 넓은 범위에서 설정해보면서(coarse search), 잘 학습되는 적절한 하이퍼파라미터 범위를 찾는다.
    • 몇번의 epoch동안만 돌려봐도 잘 동작하는지 알 수 있므로, 잘 동작하지 않는 경우 바로 학습을 중단하고 다시 잘 동작하는 범위를 찾는 과정을 반복한다.
      • Ex) 학습을 시작한 후, loss가 처음의 값보다 3배 이상으로 커진다면 아주 빠르게 증가한다는 의미이므로, 바로 중단하고 다른 값을 시도
  • Second stage
    • 앞의 과정에서 찾은 적절한 범위에서 더 미세하게 찾는다.(fine search)

• 첫번째 단계인 넓은 범위에서 적절한 값의 범위를 찾는 과정입니다.(coarse search)
  • 여기에서 확인 해야 할 것은 validation accuracy 입니다.
  • 빨간색 박스로 표시된 부분이 fine-stage를 시작할 만한 적절한 값의 범위입니다.
  • 하이퍼 파라미터 최적화 시에는 Log scale로 값을 주는 것이 좋습니다.
    • 즉, 파라미터 값을 샘플링할때 10^-3 ~ 10^-6 을 샘플링하지 말고, 10의 차수 값만 샘플링하는 것이 좋습니다.(-3 ~ -6)
    • learning rate는 gradient와 곱해지기 때문에, learning rate의 선택 범위를 log scale을 사용하는 편이 좋습니다.

• 앞에서 찾은 범위에서 다시 미세하게 찾아나갑니다.
• 위 슬라이드에서는 좋은 결과들을 빨간색 박스로 표시하였는데, 이들간의 learning rate에 큰 차이가 없는 범위내에서만 좋은 결과가 나오면 좋지 않다.(빨간글씨부분)
  • 저 범위 외에 더 좋은 값이 있을 수도 있기 때문입니다.
• 또한 다시 좁혀 설정한 범위의 경계부분에 집중되어 있다는 것을 알 수 있습니다.
  • 이렇게 되면 최적의 Learning rate를 효율적으로 탐색할 수 없을 수도 있습니다.
  • 실제로 최적의 값이 1E-5, 또는 1E-6 근처에 존재할 수도 있습니다.

Random Search vs. Grid Search

• Grid Search
  • 하이퍼파라미터를 특정 간격으로 샘플링해서 최적의 hyperparameter를 찾는 방법입니다.
• random search
  • 특정 범위 내에서 임의로 hyperparameter를 설정하고 비교하는 방법입니다.
• Hyperparameter를 탐색하는 방법은 위 슬라이드와 같이 2가지가 있는데, Grid Search에는 문제가 있습니다.
  • 실제로는 오른쪽 그림에서와 같이 여러 parameter들이 다차원의 형태로 존재합니다.
  • 따라서, 왼쪽 그림과 같이 grid로 탐색하게되면 9번을 하더라도 다른 차원에서는 3번밖에 searching을 수행하지 않은 결과가 나타날 수 있습니다.
• 따라서, random search 를 하면 모델의 성능이 어떤 파라미터에 대해 더 민감하게 반응하는지에 대해 알 수 있기 때문에, Random search가 더 좋은 방법입니다.

• 여기서는 주로 learning rate를 다루었지만, 그 밖에 decay schedule, update type, regularization, network architecture, hidden unit과 depth의 수 등 이 모든 하이퍼파라미터를 전부 다 최적화 시킬 수 있으며, 모두 조정하면서 최적의 조합을 찾아야 합니다.
• 일종의 art…

Hyperparameters Tuning Process

• 지금부터 Hyperparameters Tuning에 대한 전체적인 과정을 살펴보겠습니다.
• 하이퍼파라미터를 고르는 step입니다.

• weight decay를 설정하지 않은 상태에서 1 iteration만을 학습시켜, sanity check를 통해 random initialization후 첫 iteration에서 계산된 loss와 이론적인 loss의 기대값을 비교한다.
• 예를 들어, softmax에서 맨 처음 loss값이 logC가 아니라면, 네트워크에 오류가 있을 것입니다.
• 또는 cross-entropy loss를 예로 들면 loss의 기대값이 -log(1/C)가 되어야 합니다.

• 모델의 optimization 과정을 관찰하기 위해서 Regularization을 사용하지 않고, 5~10 mini batch 정도의 소규모 데이터에 100% train accuracy가 나오도록 모델 아키텍처를 조정해가며 정규화를 하지않고 overfit 시켜봅니다.
  • 이때 architecture, learning rate, weight initialization를 매우 작은 set에서 빠르게 interactively하게 조정하여 해당 architecture의 optimization이 올바르게 작동하는지 살펴보는 것이 목적입니다.
  • small training dataset으로 테스트하는 이유는, 이때 overfit되지 않는다면 실제 training set에서 fitting되지 않을 것이라는게 포인트이며, overfit되지 않는다면 optimization process에서 문제가 있다는 것을 뜻합니다.
• 만약 loss가 감소하지 않는다면 LR이 너무 낮거나 parameter initialization이 잘못된 것입니다.
• 만약 loss가 급증하거나 Not a Number로 나온다면 LR이 너무 높거나 parameter initialization이 잘못된 것입니다.

• 이전 과정에서 찾은 모델 architecture에 작은 weight decay를 사용해 모든 training data에 대해 training시켜 100정도의 iteration안에 loss가 유의미하게 감소하는지 살펴보며 적절한 learning rate를 찾습니다.
• 시도하기에 좋은 learning rate는 1e-1, 1e-2, 1e-3, 1e-4 입니다.

• 이전 스텝에서 찾은 learning rate와 weight decay를 적용하여 몇개의 모델에 대해 1~5의 epoch 정도를 학습시킵니다.
• 이는 training set을 넘어 valid set을 통해 모델의 일반화된 성능을 어느정도 파악할 수 있게 만들어 줍니다.
• 시도하기에 좋은 weight decay는 1e-4, 1e-5, 0 입니다.

• 이전 스텝에서 가장 괜찮은 모델에 대해 조금 더 길게(10~20 epoch)학습을 시켜봅니다. 이 때 learning rate decay는 사용하지 않습니다.

Monitor and visualize the loss curve

• 실제 cross validation으로 엄청나게 많은 하이퍼파라미터를 직접 돌려보고 모니터해서 어떤 값이 좋고 나쁜지를 확인해야 합니다.
• Learning Curves 를 보면서, 좋은 것을 찾아서 시도해보는 일을 계속 반복해야 합니다.
• 슬라이드의 오른쪽 그래프에서, 빨간색 곡선이 이상적인 형태의 loss curve 입니다.

• Loss값이 처음에 평평하다가 갑자기 감소하는 경우, Weight initialization이 잘못된 것을 나타내기에 weight initialization을 다시 시도해봐야 합니다.

• Loss값이 감소하다가 더 떨어질 가능성이 있지만 떨어지지 않는 경우에는, Learning rate decay를 시도해보면 됩니다.

• 이 경우는 너무 빨리 LR를 줄여버린 경우입니다. Loss가 flat해지는 지점까지 기다렸다가 decay를 해보면 됩니다.

• Iteratino에 따라서 Training/validation set의 accuracy를 찍어본 plot입니다.
• Training set과 val set의 accuracy가 같이 증가하며, 적당한 차이를 유지합니다.
• 즉, 위 그림처럼 train accuracy와 valid accuracy가 처음에 exponentially하게 증가하다 일정 gap을두며 linearly하게 천천히 증가한다면 잘 학습되고 있다는 뜻으로 더 길게 학습해야합니다.

• 만약 Training set의 accuracy만 증가하고, val set의 accuracy는 어느 순간부터 낮아지기 시작하여, 두 선의 차이가 커진다면, 이는 곧 overfitting을 의미합니다.
• 이를 해결하기 위해서는, regularization을 세게 주거나, 데이터를 더 모아보는 방법이 있습니다. 이때, regularization을 세게 주는 것은, L2 regularization에서 람다를 크게 지정하는 것이나, data augmentation과 같은 방법을 의미합니다.

• Training set과 val set의 accuracy가 같이 증가하지만, 두 선의 차이가 너무 없다면, underfitting을 의심해보아야 합니다.
• 즉, bigger model 을 사용하거나, regularization을 줄여야 합니다.

Track the ratio of weight updates / weight magnitudes:

• 학습 중에 W의 파라미터 크기와 업데이트될 값의 크기를 각각 norm 연산을 통해 구한 후, 이들의 비율을 계산하면 업데이트가 잘 수행되는지 확인할 수 있습니다.
  • Ex) 업데이트가 파라미터에 비해 너무 많이 수행된다면 ratio가 매우 클 것이고, 너무 적게 수행된다면 ratio가 매우 작을 것입니다.
• 이 방법은 학습에서 무엇이 문제가 되는지 확인하는 디버깅 용도로 사용 가능합니다.

Summary

• 각각의 주제에 명심해야할 내용입니다.
• 다음 강의에서 이어서 NN을 학습 시키는 데에 필요한 것들에 대해 더 알아보겠습니다.

해당 게시물은 Standford 2017 CS231n 강의와 2022년 슬라이드를 바탕으로 작성되었습니다.

Recap: Image Classification with Linear Classifier

Linear Classifier를 다시 생각해보면 3가지 관점이 있었습니다.

• Algebric Viewpoint
  • 이 관점에서는 Linear Classifier를 단순히 행렬과 벡터의 곱에 bias 벡터를 더한 것으로 봅니다.
  • 이렇게 바라보면 Bias Trick한 장점이 있습니다.
    • Bias Trick은 bias를 weight의 마지막 열로 추가시키고, data vector의 마지막 원소로 1을 추가하면, 단순히 곱하기만 하면 간단히 계산할 수 있습니다.
  • 또 다른 이점은 Linear Classifier의 결과가 이름대로 결과도 Linear 하다는 것을 한눈에 알 수 있습니다.
• Visual Viewpoint(Template Matching)
  • Weight의 각 행을 input image의 크기로 변환하고 각각 image와 내적을 하고 weight의 각 행에 대응하는 bias를 더해주는 관점이 있는데, 이를 Visual Viewpoint 또는 template matching이라 합니다.
    • 왜냐하면 classifier가 wieght을 학습하는 것을 카테고리 당 하나의 이미지 템플릿을 학습한다고 볼 수 있기 때문입니다.
  • Linear Classifier는 카테고리 당 1개의 템플릿만 학습 가능하지만, 이미지 속의 물체는 항상 같은 방향, 같은 자세, 같은 색상 등으로 존재하지 않습니다.
• Geometric Viewpoint
  • 이 관점에서는 Linear Classifier에서 이미지는 고차원의 유클리드 공간에서 존재하며, 각 카테고리는 각각 1개의 초평면이 존재하며 이 초평면이 이미지를 2등분한다고 봅니다.
  • 이러한 관점에서 보면 고차원 공간에서의 Linear Classifier를 3차원인 우리가 완전히 이해하기 어려울 수 있지만, 적어도 Linear Classifier가 어떤 것은 할 수 있고, 어떤 것은 할 수 없는지 그 한계를 이해하는 것에 도움이 됩니다.

Problem: Linear Classifiers are not very powerful

Linear Classifier는 간단한만큼, Geometric Viewpoint나 Visual Viewpoint에서 확인할 수 있듯이, 한계가 많습니다.

• Visual Viewpoint
  • Linear classifiers는 class당 하나의 template만 학습합니다.
• Geometric Viewpoint
  • Linear classifiers는 오직 linear decision boundaries만 그릴 수 있습니다.

Last Time: Neural Networks

또한 Neural Networks와 선형 함수들을 살펴보았습니다.

• 선형 레이어를 쌓고 그 사이에 비선형 레이어를 추가하여 Neural Network를 만들었습니다.
• 다양한 종류의 class를 올바르게 분류하기 위해 “중간 단계의 template”을 학습시켰습니다. 그리고 이 template들을 결합해서 최종 클래스 스코어를 계산합니다.

하지만 학습시 다차원 배열로 구성된 이미지를 벡터로 만들어서 처리했는데, 이 과정에서 spatial structure는 사라지게 되었습니다. 그래서 이번 시간에는 spatial structure를 처리할 수 있는 Convolutional Network에 대해 배울 것입니다.

Next: Convolutional Neural Networks

Convolutional Layer 는 기본적으로 NN과 비교할때 “Spatial Structure(공간적 구조)” 를 유지합니다.

The history of nNeural Networks and CNNs

• 1957년, Frank Rosenblatt가 Mark I Perceptron machine을 개발했습니다.
  • 이 기계는 “perceptron”을 구현한 최초의 기계
  • “Perceptron”은 $Wx + b$ 와 유사한 함수를 사용하며, 출력 값이 0 또는 1입니다.
  • 가중치 W를 Update 하는 Update Rule이 존재합니다.
  • 하지만 당시에는 backprob이라는 개념이 없어서, 단지 W를 이리저리 조절하면서 맞추는 식이었습니다.

• 1960년, Widrow와 Hoff가 Adaline and Madaline을 개발했습니다.
  • 최초의 Multilayer Perceptron Network
  • 비로소 Neural network와 비슷한 모양을 하기 시작하긴 했지만, 아직 Backprob같은 학습 알고리즘은 없었습니다.

• 1986년, 최초의 Backporp을 Rumelhart가 제안하였습니다.
  • Chain rule과 Update rule을 볼 수 있습니다.
  • 이때 최초로 network를 학습시키는 것에 관한 개념이 정립되기 시작했습니다.

• 하지만 그 이후로 NN을 더 크게 만들지는 못했으며, 한동안은 새로운 이론이 나오지 못했고, 널리 쓰이지도 못 했습니다.
• 하지만 2000년대부터 다시 발전하기 시작했습니다.
• 2006년, Geoff Hinton 과 Ruslan Salakhutdinov의 논문에서 DNN의 학습가능성을 선보였고, 실제로 아주 효과적이라는 것을 보여주었습니다.
  • 하지만 아직까지 모던한 NN는 아니었고, backprop이 가능하려면 아주 세심하게 초기화를 해야 했습니다.
  • 그래서 전처리 과정이 필요했고, 초기화를 위해 RBM을 이용해서 각 히든레이어 가중치를 학습시켜야 했습니다.
  • 초기화된 hidden layer를 이용해서 전체 신경망을 backprop하거나 fine tune하는 것이었습니다.

• 실제 neural networks이 유행하기 시작한 때는 2012년입니다.
  • neural networks이 음성인식에서 아주 좋은 성능을 보였습니다.
    • Hintin lab에서 나온 것인데 acoustic modeling과 speech recognition에 관한 것.
  • 또한 2012년에는 Hinton lab의 Alex Krizhevsky에서 영상 인식에 관한 landmark paper 가 등장합니다.
    • ImageNet Classification에서 최초로 neural networks(ConNets)을 사용했고, 결과는 정말 놀라웠습니다.
    • AlexNet은 ImageNet benchmark의 Error를 극적으로 감소시켰습니다.

How did CNN become famous?

구체적으로 “CNN이 어떻게 유명해졌는지” 에 대해 살펴보겠습니다.

• 1950년대, Hubel과 Wiesel이 일차시각피질의 뉴런에 관한 연구를 수행했습니다.
  • 고양이의 뇌에 전극을 꽂는 실험을 했고, 고양이에게 다양한 자극을 주며 실험을 했습니다.
  • 이 실험에서 뉴런이 oriented edges와 shapes같은 것에 반응 한다는 것을 알아냈습니다.

• 이 실험에서 내린 몇 가지 결론은 아주 중요했습니다.
• 그중 하나는 바로 피질 내부에 지형적인 매핑(topographical mapping) 이 있다는 것입니다.
  • 피질 내 서로 인접해 있는 세포들은 visual field내에 어떤 지역성을 띄고 있습니다.

• 또한 뉴런들이 계층구조를 지닌다는 것도 발견했습니다.
  • 다양한 종류의 시각자극을 관찰하면서 시각 신호가 가장 먼저 도달하는 곳이 바로 Retinal ganglion 이라는 것을 발견합니다.
    • Retinal ganglion cell은 원형으로 생긴 지역입니다.
  • 가장 상위에는 Simple cells이 있는데, 이 세포들은 다양한 edges의 방향과 빛의 방향에 반응했습니다.
  • 또한 Simple Cells이 Complex cells과 연결되어 있다는 것을 발견했습니다.
  • Complex cells는 빛의 방향 뿐만 아니라 움직임에서 반응했습니다.
  • 복잡도가 증가함게 따라, 가령 hypercomplex cells은 끝 점(end point)과 같은것에 반응하게 되는 것입니다.
• 이런 결과로부터 “corner” 나 “blob” 에 대한 아이디어를 얻기 시작했습니다.

• 1980년, neocognitron 은 Hubel과 Wiesel이 발견한 simple/complex cells의 아이디어를 사용한 최초의 NN입니다.
  • Fukishima는 simple/complex cells을 교차시켰습니다.
  • Simple cells은 학습가능한 parameters를 가지고 있고, Complex cells은 pooling과 같은 것으로 구현했는데 작은 변화에 Simple cells보다 좀 더 강건합니다.

• 1998년 Yann LeCun 이 최초로 NN을 학습시키기 위해 Backprob과 gradient-based learning을 적용했습니다.
  • 문서 및 우편번호의 숫자 인식에 아주 잘 동작했습니다.
  • 하지만 아직 이 Network를 더 크게 만들 수는 없었으며, 데이터가 단순했습니다.

• 이후 2012년 Alex Krizhevsky(AlexNet) 가 CNN의 현대화 바람을 이르켰습니다.
  • Yann LeCun의 CNN과 크게 달라보이진 않으며, 다만 더 크고 깊어졌습니다.
• 가장 중요한 점은 지금은 ImageNet dataset과 같이 대규모의 데이터를 활용할 수 있다는 것입니다.
• 또한 GPU의 힘도 있었습니다.

Fast-forward to today: ConvNets are everywhere

ConvNet이 어디 쓰이는지, 어떤 Task들이 있는지 살펴보겠습니다.

• ConvNets은 모든 곳에 쓰입니다.
• AlexNet의 ImageNet 데이터 분류 결과를 살펴보면, 이미지 검색에 정말 좋은 성능을 보이고 있습니다.

• Detection에서도 ConvNet을 사용합니다.
  • 영상 내에 객체가 어디에 있는지를 아주 잘 찾아냅니다.
• segmentation은 단지 네모박스만 치는 것이 아니라 나무나 사람 등을 구별하는데 픽셀 하나 하나에 모두 레이블링하는 것입니다.
  • 이런 알고리즘은 자율주행 자동차에 사용할 수 있습니다.

• 대부분의 작업은 GPU가 수행할 수 있으며, 병렬처리를 통해 ConvNet을 아주 효과적으로 훈련하고 실행시킬 수 있습니다.

• 위 슬라이드 모두는 Convnet을 활용할 수 있는 다양한 애플리케이션의 예 입니다.
• 얼굴인식의 예를 보면 얼굴 이미지를 입력으로 받아서 이 사람이 누구인지에 대한 확률을 추정할 수 있습니다.
• 또한 ConvNets을 비디오에도 활용할 수 있는데, 단일 이미지의 정보 뿐만 아니라 시간적 정보도 같이 활용하는 방법입니다.

• pose recognition도 가능합니다.
  • 어깨나 팔꿈치와 같은 다양한 관절들을 인식해 낼 수 있습니다.
• Convnet을 가지고 게임도 할 수 있습니다.
  • 강화학습을 통해서 Atari 게임을 하거나, 바둑을 두는 모습도 볼 수 있습니다.

• 또한 의학 영상을 가지고 해석을 하거나 진단을 하는데도 이용할 수 있습니다.
• 또한 은하를 분류하거나 표지판을 인식하는데도 쓰입니다.

• 또한 항공지도를 가지고 어디가 길이고 어디가 건물인지를 인식하기도 합니다.

• Image Captioning도 있습니다.
  • 이미지가 주어지면 이미지에 대한 설명을 문장으로 만들어 내는 것입니다.

• 또한 Neural Network를 이용해 예술작품도 만들어 낼 수 있습니다.
  • 왼쪽은 Deep Dream 알고리즘의 결과
• 또한 Style Transfer라는 방법은 원본 이미지를 가지고 특정 화풍으로 다시 그려주는 알고리즘도 있습니다.

그럼, 지금부터 Convolutional Neural Network가 어떻게 작동하는지를 살펴보겠습니다.

Convolutional Neural Networks(CNNs)

Recap: Fully Connected Layer

• Fully Connected Layer의 하는 일은 어떤 벡터를 가지고 연산을 하는 것이었습니다.
• Fully connected layer에 $32\ ×\ 32\ ×\ 3$ 의 input image가 입력되었을 때, $32\ ×\ 32\ ×\ 3$ 의 matrix가 1차원적으로 펼쳐져서 $1\ ×\ 3072$ 의 shape으로 input vector가 만들어지게 되고, $1\ ×\ 3072$ size의 input vector가 $3072\ ×\ 10$ size의 W 행렬(가중치 행렬)과 dot product(내적)되어 결과적으로 $1\ ×\ 10$ size의 output vector(activation)가 만들어지게 됩니다.
  • 10개의 출력이 있으며, 각 1개의 출력은 Neuron의 한 값 이라고 할 수 있습니다.
• 이 과정에서 이미지 데이터의 주변 위치 정보에 대한 내용이 무시됩니다.
  • 이러한 문제를 해결하기 위한 방법이 바로 Convolution layer를 이용한 CNN 입니다.
  • CNN은 기존의 input image에 대한 구조를 보존 시키며 주변 픽셀에 대한 정보 (위치정보)를 고려 할 수 있게 만든 방법 입니다.
  • 즉, 기존의 FC Layer가 입력 이미지를 길게 쭉 폈다면, CNN은 기존의 이미지 구조를 그대로 유지하게 됩니다.

Convolution Layer

• Convolutional Layer는 입력보다 작은 크기의 filter가 이미지 위로 슬라이딩하면서 공간적으로 dot product를 수행하는 방식으로 동작 합니다.
  • 여기서 dot product는 같은 위치의 input image와 filter의 픽셀간 곱셈 연산 후 모두 더하는 연산을 의미합니다.
• 또한, filter의 depth는 input image의 depth와 항상 동일 합니다.
  • filter의 width나 height은 필터의 크기를 얼마나 크게 할 것이냐에 따라 임의로 정할 수 있지만, 채널(depth)는 항상 input data 의 채널수(depth)와 동일해야합니다.
  • 여기서 하나의 필터는 아주 작은 부분만을 취합니다. 즉 전체 $32\ x\ 32$ 이미지의 $5\ x\ 5$ 만 취합니다.
  • 하지만 깊이를 보면 전체 깊이를 전부 취합니다.
  • 그러므로 슬라이드의 filter의 shape은 $5\ x\ 5\ x\ 3$ 입니다.
  • 이 filter 에 해당하는 matrix가 바로 가중치(W)행렬 입니다.

• 반복하면, Convolutional Layer는 filter를 가지고 image에 대해 dot product를 input channel별로 수행하고, 이들을 모두 더해서 하나의 값을 출력합니다.
  • 즉, 같은 위치의 픽셀끼리 element wise 곱셈 후 모두 더하는 것을 channel별로 수행하고, channel별 결과들을 모두 더해서 한개의 값을 출력하게 됩니다.
• convolution 연산시 $W^Tx + b$ 라고 표기한 이유는, 내적을 수학적으로 표현하기 위해서 1D로 펼친 후 dot product하는 것과 같은 결과이기 때문입니다.
  • 각 원소끼리 Convolution을 하는 거나 쭉 펴서 내적을 하는거나 똑같은 일을 하는 것이기 떄문입니다.
  • 즉 필터를 이미지에 겹쳐놓고 해당하는 값들을 서로 곱하는데, 실제로는 모두 펴서 벡터간 내적을 구하는 것입니다.

• Convolution 연산시 슬라이딩은 이미지의 좌상단부터 시작하여, 필터의 중앙에 값들을 모으게 됩니다.
• filter와 겹쳐진 input 이미지 부분에 대해 내적(dot product)를 하여 하나의 값이 나오게 되고, filter가 일정 간격으로 움직여(sliding) 전체 이미지에 대해 이 작업을 반복하면 최종의 activation map (output matrix) 이 생성됩니다.
• 출력 행렬의 크기는 슬라이드를 어떻게 하느냐에 따라 다르게 됩니다.

• 정리하면 Filter를 통해 출력된 각 위치에서의 값들을 이미지 형태로 합친 것을 Activation Map 이라고 합니다.
• 보통 Convolution Layer에서는 여러개의 filter를 사용 합니다.
  • filter마다 다른 특징을 추출하고 싶기 때문입니다.
  • 즉 한 Layer에서 원하는 만큼 여러개의 필터를 사용할 수 있습니다.
• 여러 개의 filter를 사용하면, 더 많은 수의 activation map을 출력할 수 있습니다.
  • 즉, output channel의 개수는 조절 가능합니다.
• 위 슬라이드는 $3\ x\ 5\ x\ 5$ 크기의 filter를 통해 총 6개의 output channel을 출력한 것이며, 이때 filter의 shape는 다음과 같습니다.
  • 6개의 $3\ x\ 5\ x\ 5$ 크기의 filter를 사용하면 6개의 Activation Map이 각각 $1\ x\ 28\ x\ 28$ 크기를 가집니다.
  • $Channel_out\ ×\ Channel_in\ ×\ Height_filter\ ×\ Width_filter\ =\ 6\ ×\ 3\ ×\ 28\ ×\ 28$
  • 따라서, Convolutional layer에서 filter는 4차원의 shape를 가지게 됩니다.
• 또한 이 과정에서 이미지 전체적인 spatial structure는 사라질 수 있지만, local spatial structure는 보존 될 수 있습니다.

또한 당연히 Batch 개념을 적용할 수 있으며, Batch로 처리 를 한다면 위 그림과 같이 출력됩니다.

• Convolutional Network 구조를 가진 CNN 에서는 위와 같이 Convolution layer가 연속된 형태로 만들어져 깊은 Network를 형성 합니다.
  • 보통 Linear한 Convolution layer에 비선형성을 부여하기 위해 ReLU와 같은 NonLinearity activation function를 붙여서 한 층을 이루게 됩니다.
  • 즉, Conv-ReLU 의 형태의 layer가 반복된다고 생각하면 됩니다.
  • 또한 pooling layer가 적용되기도 합니다.
  • 그리고 각 Layer의 출력은 다음 Layer의 입력이 됩니다.
• 정리하면 이러한 각 filter는 input data와 연산되어 각각의 activation map을 출력합니다. 즉, 각 layer 에 있는 filter 들이 계층별로 학습 이 되게 됩니다.

What do convolutional filters learn?

그렇다면 convolutional filters들은 어떤것을 학습하는지 의문이 듭니다.

Linear classifier: One template per class

Linear classifier는 class당 하나의 weights vector만 가지고 있기에, class당 한개의 template을 학습하기에 하나의 template을 가진 형태 로 볼 수 있습니다.

MLP: Bank of whole-image templates

Multi-Layer Perceptron을 살펴 본다면, hidden layer의 크기에 대응하는 $W$ 의 크기만큼 여러개의 template을 갖는(Bank of whole-image templates을 갖는) 형태 입니다.

Convolutional Filters

위 슬라이드는 각 filter 가 어떻게 학습이 되는지 시각적으로 보기 위해 VGG-16 이라는 Conv layer를 이용한 네트워크에 강아지 사진을 학습시키고, 그에 따라 각 layer 에서 학습이 되어 나오는 filter를 시각적으로 나타냈습니다.

• Convolution Layer도 filter들이 계층별로 학습 이 됩니다.
• Convolution Layer는 Fully-Connected Layer가 입력과 동일한 이미지의 템플릿을 학습하는 것과 달리, filter가 local template을 학습 한다는 점이 특징입니다.
  • 앞 쪽(input 과 가까운 쪽, 초기 layer)에 있는 layer의 filter에서는 모서리(edge) 와 같은 단순한 low-level features 를 학습합니다.
  • 중간에 있는 layer의 filter는 코너(corner) 와 얼룩(blobs) 과 같이 조금 더 복잡한 midle-level features 를 학습합니다.
  • 그리고 더 깊은 layer에 있는 filter는 객체와 닮은 듯한 high-level feature 를 학습하게 됩니다.
• 그리고 output에서의 feature vector의 각 원소는 각 filter(local pattern)와 얼마나 일치하는지를 나타내는데, 이건 Hubol과 Wiesel의 연구에서 고양이가 시각적인 local pattern에 반응한 것과 비슷합니다.
  • 네트워크에 앞쪽에서는 단순한 것들일 처리하고, 뒤로 갈수록 점점 더 복잡해 지는 식입니다.

특히 여기에서 시각화 한 것은 다음과 같습니다.

• 각 그리드의 요소가 하나의 뉴런(필터) 입니다.
• 그리고 시각화 시킨 이 뉴런의 모습은 바로 이미지가 어떻게 생겨야 해당 뉴런의 활성을 최대화시킬 수 있는지 를 나타내는 것입니다.
• 즉 이미지가 뉴런과 비슷하게 생겼으면 출력 값을 큰 값을 가지게 됩니다.

정리하면 다음과 같습니다.

• 각 layer의 필터는 위와 같이 hierarchical하게 feature를 학습합니다.
  • 낮은 layer의 filter일수록, 저수준의 feature를 학습합니다.
    • Ex) 가장자리, 선 등
  • 높은 layer의 filter일수록, 고수준의 feature를 학습합니다.
    • Ex) 코너, 동그라미 등
• Layer는 계층에 따라 단순/복잡한 특징이 존재합니다.
• 기본적으로 그리드의 각 요소는 각 뉴런의 활성을 최대화시키는 입력의 모양을 나타내게 됩니다.
  • 그런 의미에서 뉴런이 어떻게 생겼는지를 의미합니다.

• 위와 같은 다양한 filter와 input image가 convolution 연산되어 각 필터가 만든 출력값이자 다양한 Activation map을 생성합니다.
• activation map를 보면 이미지에서 어떤 부분이 filter 에 크게 반응하는지를 알 수 있습니다.

결과적으로 CNN이 어떻게 수행되는지를 살펴보면 입력 이미지는 여러 레이어를 통과하게 됩니다.

• 가령 첫 번째 Conv Layer후에는 non-linear layer를 통과합니다.
• Conv, ReLU, Conv, ReLU를 하고나면 pooling layer를 거치게 됩니다.
• 그리고 CNN의 끝단에는 마지막 Conv 출력 모두와 연결되어 있으며 최종 스코어를 계산하기 위해 FC-Layer가 있습니다.

Spatial Dimensions: Stride

위에서 $32\ ×\ 32\ ×\ 3$ size의 이미지에 $5\ ×\ 5\ ×\ 3$ filter로 convolution 연산을 진행했을때, $28\ ×\ 28\ ×\ 1$ 의 output activation map 이 나오는 것을 확인했습니다.

그렇다면 어떻게 해당 size의 output이 생성되는지 자세히 살펴보겠습니다. 간단한 예시로 $7 x 7$ 입력에 $3 x 3$ 필터가 있다고 할 때, 필터를 이미지의 좌상단부터 진행됩니다.

7x7 input(spatially) assume 3x3 filter applied with stride 1

• stride가 1이기 때문에 5x5 Output이 나옵니다.

7x7 input(spatially) assume 3x3 filter applied with stride 2

• stride가 2이기 때문에 3x3 Output이 나옵니다.

7x7 input(spatially) assume 3x3 filter applied with stride 3

• stride 3 을 적용한다면, 이미지 size, filter size 와 맞지 않게 됩니다.
  • 즉 이미지에대해 슬라이딩해도 필터가 모든 이미지를 커버할 수 없습니다.
• 따라서 이렇게 잘 맞지않는 stride 를 적용하게 된다면 잘 동작하지않게 됩니다.
  • 불균형한 결과를 볼 수도 있기 때문입니다.

Output size 계산

• Output(Activation Map)의 가로, 세로 크기는 다음의 식으로 계산할 수 있습니다.
  • $(N\ −\ F)\ /\ stride\ +\ 1$
  • N: 입력 차원
  • F: 필터 사이즈
• 여기서, stride는 filter가 한번에 움직이는 크기를 의미합니다.

Spatial Dimensions: Padding + Stride

stride만을 사용할 때 문제점들을 살펴보겠습니다.

• filter를 통해 convolution을 거치면 가장자리에 있는 이미지 데이터들은 filter의 중앙에 닿지 않는 문제점.
  • 즉, 가장자리 부분 이미지 데이터의 특징들은 filter를 통해 잘 추출이 되지 못합니다.
• CNN 에서 여러 개의 convolutional layer을 거치다 보면 점점 output size가 작아지는 문제점.
  • 이렇게 된다면, 깊은 CNN 구조에서는 output의 size가 너무 작아져 input 이미지의 특징들을 잘 못 나타낼 수도 있습니다.

• 출력의 size를 의도대로 만들어 주기 위해 가장 흔히 쓰는 기법은 zero-padding 입니다.
  • 즉 Image의 테두리에 Padding을 추가해 Output의 크기를 동일하게 유지할 수도 있습니다.
  • Padding은 일반적으로 zero padding이 가장 잘 동작합니다.
• Padding을 추가하는 것은 filter를 통과하면서 크기가 너무 작아지면 많은 정보를 잃게 되기 때문에 이를 방지하기 위해서 사용하는 방법 중 하나입니다.
• 위 슬라이드 예시는, $7\ ×\ 7$ size의 이미지에 zero padding with 1 (1칸 zero padding)을 적용하여 $9\ x\ 9$ 의 input으로 만든다음, $3\ ×\ 3$ filter, stride 1 로 convolution 하였습니다.
  • 결과적으로 $7\ ×\ 7$ 의 output (activation map) 이 생성되는 것을 확인 할 수 있습니다.
• Output(Activation Map)의 가로, 세로 크기는 다음의 식으로 계산할 수 있습니다.
  • $(N\ +\ 2P\ -\ F)\ /\ stride\ +\ 1$
• 어떤 stride와 filter를 쓸건지를 일반적으로 정하는 방법이 있습니다.
  • 보통 filter는 $3 × 3$, $5 × 5$, $7 × 7$ 을 씁니다.
  • 또한 $F\ ×\ F$ size 의 filter with stride 1로 수행되는 conv layer가 있다고 할때, $(F\ −\ 1)\ /\ 2$ 칸의 패딩을 사용합니다.
  • 보통 $3 × 3$ filter에는 stride를 1을 줍니다.
  • 보통 $5 × 5$ filter에는 stride를 2을 줍니다.
  • 보통 $7 × 7$ filter에는 stride를 3을 줍니다.

Quiz 1

• Padding이 있는 경우의 Output의 가로, 세로 크기는 다음과 같이 계산합니다.
  • $(N\ +\ 2P\ -\ F)\ /\ stride\ +\ 1\ =\ (32\ +\ 2*2\ -\ 5)\ /\ 1\ +\ 1\ =\ 32$
• 따라서, 정답은 $32\ ×\ 32\ ×\ 10$ 입니다.

Quiz 2

• Parameter는 filter에 존재하고, bias term을 고려해야합니다.
• 먼저, bias term 1개를 고려한 각 filter의 parameter 수는 다음과 같다.
  • $5\ ×\ 5\ ×\ 3\ +\ 1\ =\ 76$
• 여기에 output channel의 크기를 곱하면, 전체 parameter수를 구할 수 있습니다.
  • $10\ ×\ 76\ =\ 760$

Spatial Dimensions: Receptive Fields

• Convolution layer가 무엇을 하는지 생각해볼 수 있는 또다른 방식이 Receptive field 입니다. 이는 output image의 각 spatial position이 input image에서 얼마만큼의 region에 영향을 받는가 를 뜻합니다.
• 다시 이야기를 하면, Convolution Layer에서의 Output의 한 원소는 해당 filter가 참조하는 local region의 영역의 값만 영향을 받는데, 이 local region을 ‘Receptive Field’ 라 합니다.
• 그리고 Neural Network에서 Convolution Layer가 transitive하게 연결되어 있는 경우 해당 Layer의 Output의 원소는 그 Layer의 Input의 local region만이 아니라, 이전 Layer의 Input의 local region의 영향을 받는다 라고도 할 수 있습니다.
• 그래서 Receptive Field의 의미는 고정된 것이 아니고 보통 두 개의 의미로 사용됩니다.
  • 하나는 Layer의 Input에서 영향을 받는 부분 을 말합니다.
  • 다른 하나는 모델의 Input에서 영향을 받는 부분 을 말합니다.

• 위 예시는 3-conv layers일때의 receptive field 예시입니다. output tensor부터 점점 확장해 나가며 $3 × 3$ regin이 $5 × 5$ region이 되고 $7 × 7$ region이 최종 receptive fild size가 됩니다.
• 이러한 receptive field size를 $1\ +\ L\ *\ (K\ -\ 1)$ 으로 계산할 수 있습니다.
• 하지만 input image의 해상도가 커질수록 그만큼 conv layer가 많아지며 (1024 x 1024 크기의 이미지에 kernel size가 위와같이 3일경우엔 500개 가량의 convlayer가 필요) output에서 각 spatial position이 매우 큰 receptive field size를 커버한다는 뜻이므로 좋지 않은 형태입니다.
• 위와같은 문제를 해결하기 위해 또다른 hyper parameter를 적용하여 downsample을 해줘야 합니다.

Hyperparameters

• 어떤 필터를 쓸지, 몇개의 필터를 쓸건지, 필터 크기는 몇인지, stride는 몇으로 할지 zero-padding은 몇 으로 할지를 다 정해줘야합니다.
• 또한 앞서 말한 수식을 이용해서 출력의 사이즈가 어떻게 될 것인지, 전체 파라미터가 몇개가 될 것인지도 확인해 봐야 합니다.
• Convolutional layer의 하이퍼파라미터는 일반적으로 다음과 같이 설정합니다.
  • Filter의 크기 : $3\ ×\ 3$, $5\ ×\ 5$
  • Filter의 수 : 2의제곱
    • ex) 32, 64, 128, 512
  • Stride : 1 또는 2
  • Padding : 공간정보를 보존할 수 있는 무엇이든 가능

1x1 convolution

• $1 × 1$ Convolution은 공간적인 정보를 이용하지 않습니다.
  • 하지만 이 필터는 Depth만큼 연산을 수행하며, output filter의 수를 줄일 수 있습니다.
• $56\ ×\ 56\ ×\ 64$ size의 input에 $1\ ×\ 1\ ×\ 64$ filter 32개를 사용하여 convolution을 진행하면 $56\ ×\ 56\ ×\ 32$ size의 output이 생성되게 됩니다.
• 즉, $1\ ×\ 1\ ×\ D$ convolution layer는 차원을 줄여주는 역할 을 합니다.

The brain/neuron view of CONV Layer

Brain Neuron 관점에서 Convolution layer에 대해 살펴보겠습니다.

• Fully Connected Layer
  • FC-layer의 뉴런들은 하나의 뉴런이 데이터의 모든 정보를 다 받아서 가중치(W) 와 bias를 이용해 계산하여 output을 출력했습니다.
• Convolutional Layer
  • 그러나 Conv layer에서 하나의 뉴런(노드)이 전체 입력 데이터를 받아오는 것이 아니라는 점이 가장 큰 차이점 입니다.
  • 즉, 하나의 뉴런이 전체 입력데이터를 가져와 $W$, $b$ 를 이용해 계산을 하는 것이 아니라, convolution layer의 하나의 filter의 크기만큼의 데이터만을 받아와 계산을 합니다.
  • 그러므로 ConvNet의 각각의 뉴런은 Local connectivity 를 가집니다.

Convolutional Layer은 하나의 뉴런이 sliding 하면서 모든 입력 이미지(데이터)를 처리하는 것이 아니라, 하나의 뉴런은 한 부분만 처리하고, filter가 sliding될때마다 또 다른 뉴런이 각각의 영역을 처리하는 방식 입니다.

• 이러한 많은 뉴런들이 모여서 전체 이미지를 처리하게 됩니다.
• spatial structure를 유지한 채로 Layer의 출력인 activation map을 만듭니다.

• 또한 위에서 언급했지만 한 뉴런이 담당하는 영역 을 Receptive Field 라고 합니다.
• 다시 언급하면 “Receptive field” 란 한 뉴런이 한 번에 수용할 수 있는 영역 을 의미합니다.
• 즉, $5\ ×\ 5\ ×\ 3$ filter을 사용했을때, 각각의 뉴런의 receptive field 는 $5\ ×\ 5\ ×\ 3$ 라고 할 수 있습니다.

Convolutional Layer와 Fully Connected Layer의 차이점

위와 같이 $32\ ×\ 32\ ×\ 3$ 의 이미지에 5개의 $5\ ×\ 5\ ×\ 3$ filter를 사용한 convolution layer를 통과시키면 $28\ ×\ 28\ ×\ 5$ 의 output 이 생성됩니다.

• Fully Connected Layer에서 특징을 추출할때에는 전체 데이터를 모두 이용해서 feature를 추출합니다.
• Convolutional Layer에서는 한 receptive field의 데이터만을 이용해서 해당 구역만의 feature를 추출 한 것을 확인할 수 있습니다.
  • 한개의 receptive field 에서 5개의 값이 나온 것을 확인할 수 있습니다.
  • 정확하게 같은 지역에서 추출된 서로다른 특징 이라 할 수 있습니다.
  • 각 필터는 서로 다른 특징을 추출하므로, 각 필터는 이미지에서 같은 지역을 돌더라도 filter 마다 서로 다른 특징을 뽑아낸다고 볼 수 있습니다.

Pooling Layer

• Pooling layer 는 데이터(features, representation)를 작게 만드는(downsampling) 하는 역할을 합니다.
  • 여기서 representation은 conv layer을 통과해 추출된 feature, activation map을 의미합니다.
  • representation이 작아지면 파라미터 수가 줄어듦으로써 모델이 좀 더 가벼워지는 효과가 있습니다.
• 즉, Pooling Layer는 Spatial downsampling을 수행하기 위한 목적으로 사용 되는 layer입니다.
  • pooling layer 를 통해 각 영역에 대한 정보의 손실을 최소화하며 downsampling 을 할 수 있습니다.
  • 참고) Convolutional Layer에서 stride를 크게 하는 것도 downsampling을 수행하는 방법 중 하나입니다.
    • 강의 녹화 기준으로, 최근의 연구들에서 Pooling Layer보다 stride를 크게 해서 수행하는 downsampling이 더 좋은 결과들을 얻고 있다고 합니다.
• Pooling Layer의 몇가지 특징은 다음과 같습니다.
  • Output channel의 수가 그대로 유지된다. (Convolutional layer와의 차이점)
    • 단순히 각 채널별로 filter를 움직이면서 값의 출력만을 반복합니다.
  • 학습되는 parameter가 없다.
  • Output의 가로, 세로 크기는 Convolutional layer에서와 같은 방식으로 계산할 수 있다.
    • $(N\ −\ F)\ /\ stride\ +\ 1$

Max Pooling

• Max Pooling 은 filter에서 가장 큰 값만을 출력하는 방법이며, 가장 일반적인 방법입니다.
  • 직관적으로는 Neuron이 얼마나 많이 활성화되는가로 생각할 수 있는데, 이렇게 생각하는 것이 recognition이나 detection 등에서도 더 make sense하다고 볼 수 있습니다.
• Pooling Layer에서의 stride는 filter가 서로 안겹치게 하는 것이 일반적 입니다.
  • filter size 2, stride 2가 일반적.
• Downsampling에서 Pooling은 Convolution Layer에서의 stride 보다 더 선호되는데, Pooling에서는 어떠한 learnable parameter도 없으며 약간의 spatial shift에도 invariance가 보장되기 때문입니다.
  • 하지만, 최근에는 conv layer에서 stride를 조절해서 input의 이미지를 downsampling하는 방법들이 많이 쓰이고 있습니다.
  • 성능 또한, pooling layer를 따로 거치는 것보다 conv layer에서 stride를 조절해 자체적으로 input 데이터의 size를 줄이는 방법이 많이 사용되고 있습니다.

• Pooling layer의 하이퍼파라미터는 일반적으로 다음과 같이 설정합니다.
  • Filter의 크기 : $2\ x\ 2$, $3\ x\ 3$
  • Stride : 2
  • Padding : Pooling layer에서는 잘 사용하지 않음

Fully Connected Layer(FC Layer)

• CNN의 마지막에는 Fully Connected Layer를 통해 prediction을 수행합니다.
  • Convolutional Layer와 downsampling을 위한 Pooling로 이루어진 network에서 출력된 최종 output인 3차원 volume을 모두 펼친 후(stretch), 1차원 벡터로 만들어서 Fully Connected Layer에 입력으로 넣습니다.
• 즉, (Conv + Pooling으로) 공간 구조를 보존하며 추출해온 정보 모두를 모아서 추론(Inference)을 수행하는 것으로 이해할 수 있습니다.
• FC Layer를 거쳐 나온 값은 class별 score이고, 각 값들은 각 필터가 가진 templete이 얼마나 활성화 되었는지를 표현합니다.

Summary

• 요약하면, CNN이 어떻게 동작하는지를 배웠습니다.
• 기본적으로는 Conv와 Pooling을 쌓아 올리다가 마지막에 FC Layer로 끝나게 됩니다.
• 네트워크의 필터는 점점 더 작아지고, 아키텍쳐는 점점 깊어지는 경향을 배웠습니다.
  • Pooling 이나 FC Layer를 점점 더 없애는 추세입니다.
  • 그냥 Conv Layer만 깊게 쌓는 것
• 전형적인 CNN 아키텍쳐는 Conv와 ReLU를 n번 반복합니다. 그리고 FC Layer가 이어집니다.
• Class score를 구하기 위해 softmax를 사용합니다.
• 정리하면 엄청 깊은 Conv, ReLU, Pool 시퀀스를 구성하게될 것이고, 그 다음 한두 번의 FC Layer가 이어지는 것입니다.

해당 게시물은 Standford 2017 CS231n 강의와 2022년 슬라이드를 바탕으로 작성되었습니다.

Lecture3 Recap

함수 $f$ 를 통해 어떻게 classifier를 정의하는지 다뤘습니다.

• weights W를 파라미터로 가집니다.
• 함수 f의 입력(input)은 데이터 $x$,
• 함수 f의 출력(output)은 분류하고자 하는 클래스들에 대한 score vector

또한 loss function을 정의했습니다.

• classifier 얼마나 badness한지 점수로 나타내기위해 Full loss 항(term)을 정의.
• Full loss = data loss + regularization
• regularization은 얼마나 우리의 모델이 단순한지, 더 나은 일반화를 위해 적합한 모델을 가지고 있는지를 표현.

또한 최적의 loss를 갖게 하는 파라미터 $W$ 를 찾고 싶어서, loss function의 W에 관한 gradient를 찾았습니다

• Gradient Descent를 통해 optimization을 하여 최적의 $W$ 를 찾습니다.
• gradient가 음수인 방향, 즉 경사가 하강하는 방향을 반복적으로 구해 아래로 나아가 가장 낮은 loss에 찾습니다.

또한 gradient를 구하는 다른 방법에 대해서도 이야기했습니다.

• 수학적으로 유한 차분 근사(finite differnce approximation)를 이용해 계산가능.
  • 느리고 또한 근사치이지만 써내려가면서 하기에 가장 쉬운 방법
• analytic gradient를 어떻게 사용하지 그리고 계산하는 것까지 이야기했습니다.
  • analytic gradient를 사용하는 것은 빠르고 정확합니다.

Problem: How to compute gradients?

analytic gradient를 사용하면 계산이 빠르고 정확하다 했는데, 그렇다면 gradient를 어떻게 구할 것인지 생각해봐야 합니다. 지금부터 왜 Computational graphs + Backpropagation 이 nice한지 부터 출발해보겠습니다.

• 우선 W에 대한 optimization이 까다로워지며, Gradient계산부터 복잡합니다.
• 2-layer neural networks Loss에 대해 W의 미분을 계산한다라고 했을때, W1, W2에 대한 gradient = loss를 W1, W2의 함수로 보고 각각에 대해 편미분을 합니다.

• 손으로 gradient를 직접 계산하려고 한다면, 매우 많은 수식과 종이가 필요합니다.
• 또한 Loss식(SVM 대신 cross-entropy loss를 사용)을 바꾸면, gradient를 새롭게 계산해야합니다.
• 매우 복잡한 모델에는 적합하지 않습니다.

Better Idea: Computational graphs + Backpropagation

따라서 아무리 복잡한 모델이 와도 컴퓨터가 계산할 수 있는 모듈을 만들고자 합니다. 이 때 모듈 계산을 도와주는 것이 computational graph 입니다.

임의의 복잡한 함수를 통해 어떻게 analytic gradient를 계산하는방법

• computational graph framework 사용합니다.
• computational graph를 이용하면 어떤 함수든지 표현할 수 있습니다.

그래프의 각 노드는 연산 단계를 나타냅니다. input이 $x$, $W$ 인 선형 classifier인 경우

• 처음 노드는 곱셈 노드입니다. 파라미터 $W$(weight)와 입력 데이터($x$)의 행렬 곱셈을 의미하고, 그 결과로 $s$(score) vector가 출력됩니다.
• 그 바로 다음 단계의 노드는 전단계에서 계산된 $s$ (score)을 이용해 loss 즉, $L_i$ 를 계산 하는 노드입니다. 이때 계산에 이용되는 손실함수는 hinge loss로 계산이 되어지는 것을 확인 할 수 있습니다.
• 또한 overfitting을 막기 위해 Regularization term을 더해주는 노드를 확인 할 수 있습니다.
• 그리고 최종 loss $L$ 은 regularization term과 data term의 합입니다.

computational graph를 사용해 함수를 표현하게 됨으로써, backpropagation을 사용할 수 있게 됩니다. backpropagation 은 gradient를 얻기위해 computational graph 내부의 모든 변수에 대해 chain rule을 재귀적으로 사용합니다.

computational graph는 매우 복잡한 함수를 이용하여 작업할때 아주 유용하게 사용됩니다. 예를들어 CNN은 가장 윗층(top)에 입력 이미지가 들어가고 아래(bottom)에는 loss가 있습니다. 입력 이미지는 loss function으로 가기까지 많은 layer를 거쳐 변형을 겪게 됩니다.

심지어 이렇게 복잡한 neural networks도 computational graph를 통해 손쉽게 계산이 가능합니다. 그렇다면 지금부터 backpropagation이 어떻게 동작하는지 간단한 예제를 살펴보겠습니다.

Backpropagation using computational graph

Forward Pass

$f(x,\ y,\ z)\ =\ (x\ +\ y)z$ 라는 함수가 있고 덧셈노드, 곱셈노드로 구성된 computational graph가 표현되어 있습니다. 그리고 $x=-2$, $y=5$, $z=-4$ 의 입력값을 넣어 각 연산 과정에서 계산된 값들을 적어두었습니다.

목표는 function $f$ 의 출력에 대한 어떤 변수의 gradient를 찾기 원합니다. 그렇기에 처음에는 항상 함수 $f$ 를 이용해서 computational graph로 나타내는 것입니다. 그리고 이 네트워크에 우리가 가지고 있는 값을 전달합니다.

• 우리가 찾기 원하는것은 $x$, $y$, $z$ 각각에 대한 $f$ 의 gradient입니다.
• 다음과 같이 정의한다면, $f(x,\ y,\ z)\ =\ (x\ +\ y)z\ =\ qz$ 라고 표현 가능합니다.
  • $x\ +\ y$ 덧셈 노드를 $q$ 라고 정의
  • $q\ *\ z$ 곱셈 노드를 $f$ 라고 정의
• 위 두 식에 각 변수에대해 편미분을 실행하면 다음과 같습니다.
  • $x$ 변화량에 따른 $q$ 변화량, $\frac{∂q}{∂x}\ =\ 1$
  • $y$ 변화량에 따른 $q$ 변화량, $\frac{∂q}{∂y}\ =\ 1$
  • $q$ 변화량에 따른 $f$ 변화량, $\frac{∂f}{∂q}\ =\ z$
  • $z$ 변화량에 따른 $f$ 변화량, $\frac{∂f}{∂z}\ =\ q$

Backward Pass

• backpropagation은 chain rule의 재귀적인 응용입니다.
  • chiain rule에 의해 computational graph의 가장 끝, 뒤에서부터 gradient를 계산합니다.
  • 우선 제일 뒷부분, 즉 출력 $f$ 에 대한 gradient를 계산하길 원합니다.
  • 제일 뒷부분의 gradient는 $\frac{∂f}{∂f}\ =\ 1$ 입니다.

• 다음으로, 뒤로 이동해서 $z$ 에 대한 $f$ 의 gradient를 계산합니다.
  • $z$ 에 대한 $f$ 의 gradient, 즉 $\frac{∂f}{∂z}$ 를 계산합니다.
  • 해당 값은 이미 Forward Pass 과정에서 이미 $\frac{∂f}{∂z}\ =\ q$ 라고 계산해두었습니다.
  • 따라서 $z$ 에 대한 $f$ 의 미분값은 $\frac{∂f}{∂z}\ =\ q\ =\ x\ +\ y\ =\ −2\ +\ 5\ =\ 3$ 가 됩니다.

• 다음으로, 뒤로 이동해서 $q$ 에 대한 $f$ 의 gradient를 계산합니다.
  • $q$ 에 대한 $f$ 의 gradient, 즉 $\frac{∂f}{∂q}$ 를 계산합니다.
  • 해당 값은 이미 Forward Pass 과정에서 이미 $\frac{∂f}{∂q}\ =\ z$ 라고 계산해두었습니다.
  • 따라서 $z$ 에 대한 $f$ 의 미분값은 $\frac{∂f}{∂q}\ =\ z\ =\ -4$ 가 됩니다.

• 이제, 계산그래프 뒤로 이동해서 $y$ 에 대한 $f$ 의 gradient를 계산합니다.
  • $y$ 에 대한 $f$ 의 gradient, 즉 $\frac{∂f}{∂y}$ 를 계산합니다.
  • 하지만 여기의 $y$ 는 $f$ 와 바로 연결되어 있지 않습니다.
  • 이때 이 값을 구할 때 chain rule 을 사용합니다.
  • 즉, 해당 값을 $\frac{∂f}{∂y}\ =\ \frac{∂f}{∂q} \frac{∂q}{∂y}$ 로 나타낼 수 있으며, 이 것은 Forward Pass 에서 계산한 $\frac{∂f}{∂q}\ =\ z$, $\frac{∂q}{∂y}\ =\ 1$ 를 이용해 계산할 수 있습니다.
  • 따라서 $y$ 에 대한 $f$ 의 미분값은 $\frac{∂f}{∂y}\ =\ \frac{∂f}{∂q} \frac{∂q}{∂y}\ =\ z\ ∗\ 1\ =\ −4$ 가 됩니다.
• 직관적으로 $y$ 가 $f$ 에 미치는 영향을 구하기 위한 것을 알 수 있습니다.
  • 즉, $y$ 를 조금 바꿨을때 그것이 $q$ 에 대해 1만큼의 영향력을 미치는 것을 의미합니다.
  • 또한 $f$ 에 대한 $q$ 의 영향력은 정확하게 -4 입니다.
  • 결과적으로 이것들을 곱해보면 $f$ 에 대한 $y$ 의 영향력으로 $1\ *\ -4\ =\ -4$ 를 얻습니다.

• 이제, 계산그래프 뒤로 이동해서 $x$ 에 대한 $f$ 의 gradient를 계산합니다.
  • $x$ 에 대한 $f$ 의 gradient, 즉 $\frac{∂f}{∂x}$ 를 계산합니다.
  • 하지만 여기의 $x$ 는 $f$ 와 바로 연결되어 있지 않습니다.
  • 이때 이 값을 구할 때 chain rule을 사용합니다.
  • 즉, 해당 값을 $\frac{∂f}{∂x}\ =\ \frac{∂f}{∂q} \frac{∂q}{∂x}$ 로 나타낼 수 있으며, 이 것은 Forward Pass 에서 계산한 $\frac{∂f}{∂q}\ =\ z$, $\frac{∂q}{∂x}\ =\ 1$ 를 이용해 계산할 수 있습니다.
  • 따라서 $x$ 에 대한 $f$ 의 미분값은 $\frac{∂f}{∂x}\ =\ \frac{∂f}{∂q} \frac{∂q}{∂x}\ =\ z\ ∗\ 1\ =\ −4$ 가 됩니다.
• 직관적으로 $x$ 가 $f$ 에 미치는 영향을 구하기 위한 것을 알 수 있습니다.
  • 즉, $x$ 를 조금 바꿨을때 그것이 $q$ 에 대해 1만큼의 영향력을 미치는 것을 의미합니다.
  • 또한 $f$ 에 대한 $q$ 의 영향력은 정확하게 -4 입니다.
  • 결과적으로 이것들을 곱해보면 $f$ 에 대한 $x$ 의 영향력으로 $1\ *\ -4\ =\ -4$ 를 얻습니다.

Local gradient와 Upstream gradient

• 지금까지 Backpropagation을 통해 모든 지점에서의 gradient를 구해보았습니다.
• 각 단계에서의 과정을 살펴보면, 일정한 규칙 이 있다는 것을 알 수 있습니다.
  • Computational graph의 모든 연산 단계에는 노드가 있습니다.
  • $x$, $y$ 는 local input 입니다.
  • 현재 지점에서의 노드의 출력에 대한 gradient를 local gradient 입니다.
    • local input 인 $x$, $y$ 변화량에 따른 $z$ 의 변화량, 각각 $\frac{∂z}{∂x}$, $\frac{∂z}{∂y}$
  • 다음 node에서 내려오는 gradient를 upstream gradient 입니다.
    • 위 그림에서는 $\frac{∂L}{∂z}$
  • Upstream gradient와 local gradient를 곱하면, chain rule에 따라 우리가 원하는 최종 출력에 대한 현재 지점에서의 gradient 를 구할 수 있습니다.
    • $\frac{∂L}{∂x}\ =\ \frac{∂L}{∂z} \frac{∂z}{∂x}$, $\frac{∂L}{∂y}\ =\ \frac{∂L}{∂y} \frac{∂z}{∂y}$ 가 됩니다.
  • 또한, 이 gradient는 다시 이전 노드의 Upstream gradient가 됩니다.
• 따라서, Backpropagation의 계산 은 recursive하게 구현이 가능 하기에, 우리가 원하는 모든 변수에 대한 gradient를 미적분계산 없이 효율적으로 구할 수 있습니다.
• 정리하면, 각 노드는 우리가 계산한 local gradient를 가지고 있으며, backpropagation을 통해 gradient을 얻습니다. 우리는 이것을 받아서 local gradient와 곱하기만 하면됩니다. 노드와 연결된, 노드 이외의 다른 어떤 값에 대하여 신경쓰지 않아도 됩니다.

Backpropagation using computational graph: Sigmoid

또 다른 예제로 $w$, $x$에 대한 함수 $f$ 는 $\frac{1}{1\ +\ e^{-(w0x0 + w1x1 + w2)}}$ 와 같습니다.

• 이전 예제와 마찬가지로, Computational graph를 그린 후, 차례대로 출력을 계산합니다.
• Sigmoid함수의 Forward Pass입니다. 위 슬라이드를 바탕으로 Backward Pass를 진행하겠습니다.

• 우선 최종 출력에서의 gradient를 구합니다.
  • $\frac{∂f}{∂f}\ =\ 1$

• 노드들은 recursive하므로, 지금부터 upstream gradient $\frac{∂L}{∂f}$ 와 local gradient $\frac{∂f}{∂x}$ 로 생각하겠습니다.
• 앞에서 구한 gradient는 현재 지점에서의 upstream gradient가 되므로, 다음과 같습니다.
  • $\frac{∂L}{∂f}\ =\ 1$
• 그리고 local gradient는 위 슬라이드의 미분식에 따라 다음과 같습니다.
  • $\frac{∂f}{∂x}\ =\ \frac{−1}{x^2}\ =\ \frac{−1}{1.37^2}$
• 따라서, 최종 출력에 대한 현재 지점에서의 gradient는 다음과 같습니다.
  • $\frac{∂L}{∂f} \frac{∂f}{∂x}\ =\ \frac{∂L}{∂x}\ =\ (1)(\frac{−1}{1.37^2})\ =\ −0.53$

• 앞에서 구한 gradient는 현재 지점에서의 upstream gradient가 되므로, 다음과 같습니다.
  • $\frac{∂L}{∂f}\ =\ −0.53$
• 그리고 local gradient는 위 슬라이드의 미분식에 따라 다음과 같습니다.
  • $\frac{∂f}{∂x}\ =\ 1$
• 따라서, 최종 출력에 대한 현재 지점에서의 gradient는 다음과 같습니다.
  • $\frac{∂L}{∂f} \frac{∂f}{∂x}\ =\ \frac{∂L}{∂x}\ =\ (-0.53)(1)\ =\ −0.53$

• 앞에서 구한 gradient는 현재 지점에서의 upstream gradient가 되므로, 다음과 같습니다.
  • $\frac{∂L}{∂f}\ =\ −0.53$
• 그리고 local gradient는 위 슬라이드의 미분식에 따라 다음과 같습니다.
  • $\frac{∂f}{∂x}\ =\ e^x\ =\ e^{-1}$
• 따라서, 최종 출력에 대한 현재 지점에서의 gradient는 다음과 같습니다.
  • $\frac{∂L}{∂f} \frac{∂f}{∂x}\ =\ \frac{∂L}{∂x}\ =\ (-0.53)(e^{-1})\ =\ −0.20$

• 앞에서 구한 gradient는 현재 지점에서의 upstream gradient가 되므로, 다음과 같습니다.
  • $\frac{∂L}{∂f}\ =\ −0.20$
• 그리고 local gradient는 위 슬라이드의 미분식에 따라 다음과 같습니다.
  • $\frac{∂f}{∂x}\ =\ a\ =\ -1$
• 따라서, 최종 출력에 대한 현재 지점에서의 gradient는 다음과 같습니다.
  • $\frac{∂L}{∂f} \frac{∂f}{∂x}\ =\ \frac{∂L}{∂x}\ =\ (-0.20)(-1)\ =\ 0.20$

• 이제 덧셈 노드에 도달했습니다. 이번에는 위 아래로 나뉘어지는데, 각각에 대해 지금까지와 동일하게 수행하면 됩니다.
• 앞에서 구한 gradient는 현재 지점에서의 upstream gradient가 되므로, 다음과 같습니다.
  • $\frac{∂L}{∂f}\ =\ 0.20$
• 그리고 local gradient는 $+$ 연산자이므로, 다음과 같습니다.
  • 윗쪽 노드
    • $\frac{∂f}{∂x}\ =\ 1$
  • 아래쪽 노드($w_2$)
    • $\frac{∂f}{∂w_2}\ =\ 1$
• 그러므로 최종 출력에 대한 각 지점에서의 gradient는 다음과 같습니다.
  • 윗쪽 노드
    • $\frac{∂L}{∂f} \frac{∂f}{∂x}\ =\ \frac{∂L}{∂x}\ =\ (0.20)(1)\ =\ 0.20$
  • 아래쪽 노드($w_2$)
    • $\frac{∂L}{∂f} \frac{∂f}{∂w_2}\ =\ \frac{∂L}{∂w_2}\ =\ (0.20)(1)\ =\ 0.20$

• 이제 곱셈 노드에 도달했습니다. 이번에는 위 아래로 나뉘어지는데, 각각에 대해 지금까지와 동일하게 수행하면 됩니다.
• 앞에서 구한 gradient는 현재 지점에서의 upstream gradient가 되므로, 다음과 같습니다.
  • $\frac{∂L}{∂f}\ =\ 0.20$
• 그리고 local gradient는 $*$ 연산자이므로, 다음과 같습니다.
  • 윗쪽 노드($w_0$)
    • $\frac{∂f}{∂w_0}\ =\ x_0\ =\ -1$
  • 아래쪽 노드($x_0$)
    • $\frac{∂f}{∂x_0}\ =\ w_0\ =\ 2$
• 그러므로 최종 출력에 대한 각 지점에서의 gradient는 다음과 같습니다.
  • 윗쪽 노드($w_0$)
    • $\frac{∂L}{∂f} \frac{∂f}{∂w_0}\ =\ \frac{∂L}{∂w_0}\ =\ (0.20)(x_0)\ =\ (0.20)(-1)\ =\ -0.20$
  • 아래쪽 노드($x_0$)
    • $\frac{∂L}{∂f} \frac{∂f}{∂x_0}\ =\ \frac{∂L}{∂x_0}\ =\ (0.20)(w_0)\ =\ (0.20)(2)\ =\ 0.40$

위와 마찬가지로, $w1$ 과 $x1$ 도 구해보겠습니다.

• local gradient는 $*$ 연산자이므로, 다음과 같습니다.
  • 윗쪽 노드($w_1$)
    • $\frac{∂f}{∂w_0}\ =\ x_1\ =\ -2$
  • 아래쪽 노드($x_1$)
    • $\frac{∂f}{∂x_0}\ =\ w_1\ =\ -3$
• 그러므로 최종 출력에 대한 각 지점에서의 gradient는 다음과 같습니다.
  • 윗쪽 노드($w_1$)
    • $\frac{∂L}{∂f} \frac{∂f}{∂w_1}\ =\ \frac{∂L}{∂w_1}\ =\ (0.20)(x_1)\ =\ (0.20)(-2)\ =\ -0.40$
  • 아래쪽 노드($x_1$)
    • $\frac{∂L}{∂f} \frac{∂f}{∂x_1}\ =\ \frac{∂L}{∂x_1}\ =\ (0.20)(w_1)\ =\ (0.20)(-3)\ =\ -0.60$

지금까지의 과정을 정리하면 다음과 같습니다.

1. 먼저, 식을 computational graph로 표현합니다.
2. forward pass 계산합니다. (초록색 숫자들)
3. backward gradient 계산합니다. (빨간색 숫자들)
   • local gradient와 upstream gradient의 곱을 계속해서 구하면 됩니다.
   • 즉 chain rule을 사용했습니다.
   • 이때, local gradient는 각 연산에 따른 미분을 통해 구합니다.

Computational Graph can be easily expressed

• 위 슬라이드의 파란색 박스 부분 연산들은 사실 Sigmoid 함수를 풀어서 나타낸 것입니다.
• 따라서, Computational Graph로 생각하는 것의 장점은 Sigmoid와 같은 복잡한 함수도 computational graph를 작성하고 simple한 연산들의 조합으로 (local gradient를 구하는 과정을 반복해서) gradient를 구할 수 있습니다.
  • 즉 computational graph를 만들 때, computational 노드에 대해 우리가 원하는 세분화된 정의를 할 수 있습니다.

• 다시 예를 들어 sigmoid 함수를 볼 때 gradient를 계산할 수 있습니다.
  • 분석적으로 이를 살펴본다면 sigmoid의 gradient는 $(1 - sigma(x)) * sigma(x)$ 와 같습니다.
• 하나의 big 노드, sigmoid로 바꿀 수 있습니다.
  • 입력이 1(초록색) 출력은 0.73을 갖습니다.
  • gradient를 얻기 위해 하나의 완전한 sigmoid 노드를 이용한다면, (1-sigmoid(x)) * sigmoid(x)를 이용할 수 있습니다.
  • x는 0.73이고 이 값을 위의 식에 대입하면 gradient로 0.2를 얻게 됩니다.
  • upstream gradient인 1과 곱하면 sigmoid gate로 바꾸기 이전의 작은 노드들로 계산된 값과 정확히 같은 값을 얻을 수 있습니다.
• 만약, 아주 복잡한 식에 backpropagation을 적용하기 위해 gradient를 구해야 한다면, Computational graph를 작성하고 하나하나의 local gradient를 구한 후, chain rule을 적용하면 빠르게 문제해결이 가능합니다.

Patterns in gradient flow

• Backpropagation에서 backward pass 과정을 하다보면 일관된 패턴 을 발견할 수 있습니다.
  • add gate : upstream gradient가 연결된 브랜치에 똑같이 같은 값으로 분배됩니다.(gradient distributor)
  • max gate : 큰 값의 local gradient는 1, 작은 값의 local gradient는 0이 되므로 여러 개 중에 가장 큰 값에만 gradient를 전달합니다. 즉, gradient가 한쪽으로만 흐릅니다.(gradient router)
  • mul gate : local gradient가 다른 반대 편 변수의 값이므로, upstream gradient를 받아 다른 변수 값으로 scaling 합니다. 즉, gradient가 switch되며, swithing + scaling의 역할을 합니다.(gradient switcher)
  • copy gate : gradient가 단순히 더해집니다.(gradient adder)

Backprop Implementation: “Flat” code

위 과정들을 실제 Flat한 code 형태로 진행과정을 살펴보겠습니다.

def f(w0, x0, w1, x1, w2):
    # Forward pass: Compute output
    s0 = w0 * x0
    s1 = w1 * x1
    s2 = s0 * s1
    s3 = s2 * w2
    L = sigmoid(s3)

    #Backward pass: Compute grads
    grad_L = 1.0
    grad_s3 = grad_L * (1 - L) * L
    grad_w2 = grad_s3
    grad_s2 = grad_s3
    grad_s0 = grad_s2
    grad_s1 = grad_s2
    grad_w1 = grad_s1 * x1
    grad_x1 = grad_s1 * w1
    grad_w0 = grad_s0 * x0
    grad_x0 = grad_s0 * w0

Vector derivatives

vector to vector의 경우에 derivative는 Jacobian입니다.

• Input, output이 모두 scala일때는, 미분도 scala로 정의가 됩니다.
• 가장 많이 보는 형태로, output은 scala, input은 vector인 경우입니다.
  • 이런 경우, gradient는 input과 차원수가 같습니다.
  • gradient의 n번째 component는 n번째 input이 조금 변화했을 때, 전체 output이 얼마나 변하는 지에 대한 값입니다.
• 다변수함수의 경우, Input, output이 모두 다변수인 경우에, 미분(derivative)은 jacobian으로 표현됩니다.
  • 즉, jacobian의 (n,m) component는 n번째 input이 변화할 때, m번째 output의 변화 정도를 의미합니다.

Gradients for vectorized code

• 위 슬라이드는 Upstream gradient, local gradient, Downstream gradient의 관계를 보여줍니다.
  • 위 슬라이드는 $x$, $y$, $z$ 가 모두 vector인 상황이며, 차원(dimension)이 각각 $D_X$, $D_Y$, $D_Z$ 입니다.
  • Gradient는 input값과 차원이 같기 때문에, upstream gradient는 똑같이 $D_Z$ 차원, downstream gradient는 각각 $D_X$, $D_Y$ 차원 입니다.
  • Local gradient를 구하는 과정을 살펴볼때, 다변수 input, 다변수 output이므로, jacobian 행렬의 형태가 됩니다.
  • 따라서 chain rule로 downstream gradient를 구하는 과정은 행렬과 벡터의 곱으로 표현됩니다.
    • [Downstream] = [Local] * [Upstream] = $(D_x\ ×\ D_z)$ * $D_z$ = $D_x$
  • 이때, 행렬이 매우 커질 가능성이 있기때문에, 메모리에 모두 올리는 것이 바람직하지않을 수 있습니다.
  • 따라서, 연산의 패턴을 파악한 후, 메모리를 절약할 수 있는 방향으로 코드를 작성하는 방법을 살펴보겠습니다.
• 즉 x, y, z는 scalar 대신에 vector를 가지는것이 일반적이며, vector인 경우에는 local gradient가 Jacobian Matrix가 됩니다.
  • Loss L은 여전히 scalar입니다.
  • Gradients of variables wrt loss have same dims as the original variable
  • gradient는 Jacobian 행렬이 되며, 각 요소의 미분을 포함하는 행렬이 됩니다.(예를들어 x의 각 원소에 대해 z에 대한 미분을 포함하는)

정리하자면 지금까지는 scalar값에 대해 backpropagation을 진행해 gradient를 구하는 방법에 대해 살펴봤지만, 실제로 입력값으로 넣어주는 파라미터 $W$ 는 matrix로 되어 있기 때문에 입력값이 vector로 들어가는 경우가 많습니다.

• 입력이 vector로 들어가게 되어도 전체적인 흐름은 같고 gradient의 형태, Jacobian matrix(자코비안 행렬, 다변수 벡터 함수의 도함수 행렬)로 표현됩니다.
• 이때, 행렬의 크기가 매우 커질 가능성이 있기때문에, 연산의 패턴을 파악한 후, 메모리를 절약할 수 있는 방법을 살펴보겠습니다.

What is the Jacobian matrix?

The Jacobian matrix is a matrix composed of the first-order partial derivatives of a multivariable function.

The formula for the Jacobian matrix is the following:

Example of Jacobian matrix

Having seen the meaning of the Jacobian matrix, we are going to see step by step how to compute the Jacobian matrix of a multivariable function.

• Find the Jacobian matrix at the point (1,2) of the following function:
  • $f(x,\ y) = (x^4\ +\ 3y^2x,\ 5y^2\ -\ 2xy\ +\ 1)$
• First of all, we calculate all the first-order partial derivatives of the function:
  • $\frac{∂f_1}{∂x}\ =\ 4x^3\ +\ 3y^2$
  • $\frac{∂f_1}{∂y}\ =\ 6yx$
  • $\frac{∂f_2}{∂x}\ =\ -2y$
  • $\frac{∂f_2}{∂y}\ =\ 10y\ -\ 2x$

정리하면 다음과 같이 나타낼 수 있습니다.

Once we have found the expression of the Jacobian matrix, we evaluate it at the point (1,2):

Vectorized operations

$4096×1$ 크기를 가진 vector가 입력값(input)으로 들어간다고 하고 $4096×1$ 크기의 vector가 결과값(output)으로 나온다고 할때, 요소별로(elementwise) 최대값을 취하는 예제입니다.

• Jacobian matrix의 사이즈는 얼마인가요?
  • $4096\ ∗\ 4096$ size가 됩니다.
• 만약 100개의 input을 동시에 입력으로 갖는 배치를 이용해 작업할 수 있습니다.
  • 노드를 더욱 효율적으로 만들지만 100배 커지게 만듭니다.
  • 즉 Jacobian은 $4096000\ *\ 4096000$ 입니다.
  • 정리하면 데이터의 차원이 커질때, Jacobian matrix의 크기가 제곱으로 커지게 됩니다. 이는 실용적이지 않으며, 실제로는 이렇게 큰 Jacobian을 계산할 필요가 없습니다.

Backprop with Vectors

또한 Jacobian matrix의 형태(구조)를 살펴볼 수 있습니다.

• 위 슬라이드를 보면, $x ∈ ℝ^4, y ∈ ℝ^4$ 이며, $y = max(0, x)$ 로 elementwise하게 max를 취합니다.
  • forward pass는 함숫값을 취하면 되므로 $x = (1, −2, 3, −1)$ 일 때, $y = (1, 0, 3, 0)$ 입니다.
• Backwardpass를 생각해볼때, Upstream gradient를 계산합니다.
  • upstream gradient인 $dL/dy$ 는 4차원입니다. (Loss는 scala, y는 4차원이므로, scala를 4차원의 y로 미분하면 4차원벡터.)
  • $dL/dx$ 를 구하기위해, local gradient인 Jacobian 행렬을 구합니다.
  • Jacobian($dy/dx$)의 off-diagonal(비대각)요소들은 전부 0값을 갖게 됩니다.
• 결론적으로, downstream gradient는 “jacobian의 대각요소가 1인 행”에 대해서는 upstream gradient값을 가져오고, 0인 행에 대해서는 0값을 갖습니다.
• 현재의 Jacobian은 매우 sparse한 형태입니다. 비대각요소들이 전부 0이므로, 코드를 짤 때 메모리에 모두 업로드하는 것은 매우 비효율적입니다.

• [Downstream]의 i번째 성분 : input 데이터(x)가 양수(+)인지, 음수(-)인지에 따라서 upstream데이터를 그대로 유지할 지, 0으로 truncate할 지 정해집니다.
• 즉 Jacobian matrix의 형태를 보면 대각성분을 제외한 나머지 성분들이 0이 되는 diagonal matrix가 되므로, Jacobian matrix를 모두 작성하지 않고 diagonal 성분만을 사용해서 gradient를 구할 수 있습니다.
  • input의 n번째 차원의 element는 output의 n번째 차원의 element에만 영향을 미칩니다.
  • 따라서, 각 차원의 element끼리만 영향을 주므로, Jacobian matrix에서 대각성분만 모두 남게되는 것 입니다.
  • 즉 Jacobian행렬은 대각행렬이 됩니다.
  • 출력에 대한 x의 영향에 대해서, 그리고 이 값을 사용하는 것에 대해서만 알면 됩니다.

Backprop with Matrices(or Tensors)

$x$, $y$, $z$ 가 모두 matrix or tensor인 상황에도 같은 개념으로 구현할 수 있습니다.

• Matrix를 모두 벡터로 펼쳐서 생각해본다면, Local gradient는 여전히 jacobian matrix를 갖습니다.
• 따라서, downstream gradient는 행렬-벡터간 곱셈이 됩니다.
  • 여전히 jacobian 행렬의 메모리 문제를 안고있습니다.
• [Local]*[Upstream] 방식이 간략하게 표현하기 위해서, Local gate가 어떠한 방식으로 정의되는지가 중요합니다.

Example: Matrix Multiplication

Matrix Multiplication에 대한 예시를 살펴보겠습니다.

• Forward pass: 주어진 값으로 행렬간 곱셈을 계산합니다.
• Backward pass: Upstream gradient가 들어왔을 때, $dL/dy$ 는 y와 같은 차원이므로 $N * M$.
  • Downstream gradient는 x와 같은 차원인 N * D를 가져야 합니다.
  • Mul gate는 swap multipier 역할을 하기때문에, $dL/dx$ 는 w값과 upstream이 곱해진 값을 갖게됩니다.
  • $\frac{∂L}{∂x} = (sth\ about\ w) * \frac{∂L}{∂y} = \frac{∂L}{∂y} * w^T$
  • mulitplication operation의 특성상 전치.

일반적으로 어떻게 되는지, $\frac{dL}{dx_{1,1}}$ 을 먼저 채워보겠습니다.

• $y_{1,1} = x_{1,1}w_{1,1} + x_{1,2}w_{2,1} + x_{1,3}w_{3,1} = \sum_K x_{1,K}W_{K,1}$
  • $\frac{dy_{1,1}}{dx_{1,1}} = w_{1,1} = 3$

• $y_{1,2} = x_{1,1}w_{1,2} + x_{1,2}w_{2,2} + x_{1,3}w_{3,2} = \sum_K x_{1,K}W_{K,2}$
  • $\frac{dy_{1,2}}{dx_{1,1}} = w_{1,2} = 2$

• $y_{1,3} = x_{1,1}w_{1,3} + x_{1,2}w_{2,3} + x_{1,3}w_{3,3} = \sum_K x_{1,K}W_{K,3}$
  • $\frac{dy_{1,3}}{dx_{1,1}} = w_{1,3} = 1$
• $y_{1,4} = x_{1,1}w_{1,4} + x_{1,2}w_{2,4} + x_{1,3}w_{3,4} = \sum_K x_{1,K}W_{K,4}$
  • $\frac{dy_{1,4}}{dx_{1,1}} = w_{1,4} = -1$

• $y_{2,1} = x_{2,1}w_{1,1} + x_{2,2}w_{2,1} + x_{2,3}w_{3,1} = \sum_K x_{2,K}W_{K,1}$
  • $\frac{dy_{2,1}}{dx_{1,1}} = 0$

• $y_{2,2} = x_{2,1}w_{1,2} + x_{2,2}w_{2,2} + x_{2,3}w_{3,2} = \sum_K x_{2,K}W_{K,2}$
  • $\frac{dy_{2,1}}{dx_{1,1}} = 0$
• $y_{2,3} = x_{2,1}w_{1,3} + x_{2,2}w_{2,3} + x_{2,3}w_{3,3} = \sum_K x_{2,K}W_{K,3}$
  • $\frac{dy_{2,1}}{dx_{1,1}} = 0$
• $y_{2,4} = x_{2,1}w_{1,4} + x_{2,2}w_{2,4} + x_{2,3}w_{3,4} = \sum_K x_{2,K}W_{K,4}$
  • $\frac{dy_{2,1}}{dx_{1,1}} = 0$

$x_{1,1}$ 에 대한 local gradient가 완성되었습니다.

• $\frac{∂L}{∂x_{1,1}} \ = \frac{∂y}{∂x_{1,1}} \frac{∂L}{∂y} \ = [row\ 1\ of\ matrix\ w] \frac{∂L}{∂y{1,:}} \ = (w_{1,:}) (\frac{∂L}{∂y{1,:}})$

• $\frac{dy_{1,K}}{dx_{2,3}} = 0$
• $\frac{dy_{2,1}}{dx_{2,3}} = w_{3,1} = 3$
• $\frac{dy_{2,2}}{dx_{2,3}} = w_{3,2} = 2$
• $\frac{dy_{2,3}}{dx_{2,3}} = w_{3,3} = 1$
• $\frac{dy_{2,4}}{dx_{2,3}} = w_{3,4} = -2$
• $\frac{∂L}{∂x_{2,3}} = (w_{3,:}) (\frac{∂L}{∂y{2,:}})$

위와 같은 방식 그대로 계산한다면, 모든 값을 채울 수 있습니다.

• 또한 일반화된 식을 도출 할 수 있습니다.
  • $\frac{∂L}{∂x_{i,j}} \ = \frac{∂y}{∂x_{i,j}} \frac{∂L}{∂y} \ = (w_{j,:}) (\frac{∂L}{∂y_{i,:}})$
  • $dL/dx = (dL/dy)w^T$
• w에 대해서도 마찬가지로 도출됩니다.
  • $dL/dw = x^T (dL/dy)$

• 위 슬라이드와 같이 영향력을 볼 수 있습니다.
• $y$ 의 어떤 부분이 $x$ 의 한 요소에 의해 영향을 받습니까?
  • $x_{n, d}$ 는 전체 행 $y_{n, .}$ 에 영향을 미칩니다.
  • $\frac{∂L}{∂x_{n,d}} = \sum_m \frac{∂L}{∂y_{n,m}} \frac{∂y_{n,m}}{∂x_{n,d}}$
• $x_{n,d} 는 y_{n,m} 에 얼마나 영향을 미칩니까?
  • $w_{d,m}$
  • $\frac{∂L}{∂x_{n,d}} = \sum_m \frac{∂L}{∂y_{n,m}} \frac{∂y_{n,m}}{∂x_{n,d}} = \sum_m \frac{∂L}{∂y_{n,m}} w_{d,m}$

A vectorized example

computational graph보다 구체적인 벡터화 된 예제를 살펴보겠습니다.

• Matrix에서 Backpropagation을 수행합니다.
• 출력에 대한 upstream gradient는 이전과 동일하게 1입니다.
  • $\frac{∂f}{∂f}\ =\ 1$
• local gradient는 L2 연산에서 제곱을 하므로 q2의 미분인 2q입니다.
  • $W⋅x$ 연산을 $q$ 라고 한다면, $f(q)\ =\ q^2_1\ +\ q^2_2\ +\ …\ +\ q^2_n$ 으로 나타낼 수 있고, 각 $q_i$ 에 대해 편미분하면 $\frac{∂f}{∂q}\ =\ 2q_i$ 로 나타낼 수 있습니다.
  • 즉, gradient 는 $∇_qf\ =\ 2q$ 입니다.
  • $\frac{∂f}{∂q}\ =\ 2q\ =\ 2 \begin{bmatrix}0.22 \ 0.26\end{bmatrix}\ =\ \begin{bmatrix}0.44 \ 0.52\end{bmatrix}$
• 따라서, 최종 출력에 대한 q에서의 gradient는 다음과 같습니다.
  • $\frac{∂f}{∂f} \frac{∂f}{∂q}\ =\ \frac{∂f}{∂q}\ =\ 2q\ =\ \begin{bmatrix}0.44 \ 0.52\end{bmatrix}$

• 다음으로, 곱셈 노드의 $W$ 브랜치를 계산하겠습니다.
• $W$ 변화량에 따른 $f$ 의 변화량, 즉 $\frac{∂f}{∂W}$ 을 구해야합니다.
• chain rule 적용 위해 $W$ 변화량에 따른 $q$ 의 변화량, $\frac{∂q}{∂W}$ 을 알아야합니다.
• mul gate 는 swithching 역할을 하며, 각 행을 계산할때 다른 행은 관여하면 안되기때문에 $k$ 가 $i$ 일때는 1 을 곱해주고, 아닐때에는 0을 곱해줍니다.
  • $\frac{∂q_k}{∂W_{i,j}}\ =\ 1_{k=i}x_j$
• 이것을 chain rule을 이용해서 $W$ 변화량에 따른 $f$ 의 변화량, $\frac{∂f}{∂W}$ 을 구할 수 있습니다.
  • $\frac{∂f}{∂W_{i,j}}\ =\ \sum_k \frac{∂f}{∂q_k} \frac{∂q_k}{∂W_{i,j}}\ =\ \sum_k(2q_k)(1_{k=i}x_j)\ =\ 2q_ix_j$
• 그러므로 gradient는 $∇_Wf=2q⋅x^T$ 입니다.

즉 정리하면 다음과 같습니다.

[\frac{∂f}{∂W}\ =\ \frac{∂f}{∂q}x^T\ =\ (2q)x^T\ =\ \begin{bmatrix}0.44 \ 0.52\end{bmatrix} [0.2\ 0.4]\ =\ \begin{bmatrix}0.088\ 0.176 \ 0.104\ 0.208\end{bmatrix}]

• 다음으로, 곱셈 노드의 $x$ 브랜치를 계산하겠습니다.
• $x$ 변화량에 따른 $f$ 의 변화량, 즉 $\frac{∂f}{∂x}$ 을 구해야합니다.
• chain rule 적용 위해 $x$ 변화량에 따른 $q$ 의 변화량, $\frac{∂q}{∂x}$ 을 알아야합니다.
  • $\frac{∂q_k}{∂x_i}\ =\ W_{k,i}$
• 이것을 chain rule을 이용해서 $x$ 변화량에 따른 $f$ 의 변화량, $\frac{∂f}{∂x}$ 을 구할 수 있습니다.
  • $\frac{∂f}{∂x_i}\ =\ \sum_k \frac{∂f}{∂q_k} \frac{∂q_k}{∂x_i}\ =\ \sum_k(2q_k)(W_{k,i})\ =\ 2q_ix_j$
• 그러므로 gradient는 $∇_xf=W^T⋅q$ 입니다.

즉 정리하면 다음과 같습니다.

[\frac{∂f}{∂X}\ =\ W^T\frac{∂f}{∂q}\ =\ W^T(2q) = \begin{bmatrix}0.1\ -0.3 \ 0.5\ 0.8\end{bmatrix} \begin{bmatrix}0.44 \ 0.52\end{bmatrix}\ =\ \begin{bmatrix}-0.112 \ 0.636\end{bmatrix}]

지금까지의 중요한 점은 다음과 같습니다.

• 벡터의 gradient는 항상 원본 벡터의 사이즈와 같습니다.
• 항상 gradient의 shape을 확인해야하며, gradient의 값을 계산했을 때 shape가 다른 결과가 나올 수 있기에 shape은 중요합니다.
• gradient의 각 요소는 함수의 최종 출력에 얼마나 특별한 영향을 미치는지 의미합니다.

Modularized implementation: forward / backward API

• computational graph에서의 과정을 실제 코드로 모듈화 된 구현이 가능합니다.
  • 각 노드를 local하게 보았고 upstream gradient와 함께 chain rule을 이용해서 local gradient를 계산했습니다.
  • 이것을 forward pass, 그리고 backward pass의 API로 생각할 수 있습니다.
  • forward pass에서는 노드의 출력을 계산하는 함수를 구현하고, backward pass에서는 gradient를 계산합니다.
• 또한 위치적으로 정렬 된 순서로 수행하기를 원합니다.
  • 노드를 처리하기 전에 이 전에 노드로 들어오는 모든 입력을 처리합니다.
  • 그리고 backward로 보면, 역순서로 모든 게이트를 통과한 다음에 게이트 각각을 거꾸로 호출합니다.

• 또한 특정 게이트, 곱셈 게이트를 살펴보면 forward()와 backward()로 구성되어있습니다.
• forward pass
  • x, y를 입력으로 받고 z를 리턴합니다.
  • 중요한 것은 값을 저장(cache)해야합니다. backward pass에서 더 많이 사용하기 때문입니다.
• backward pass
  • 입력으로 upstream gradient인 dz를 받고 출력으로 입력인 x와 y에 gradient를 전달합니다.
  • 여기서 출력은 dx와 dy입니다.
  • chain rule을 사용하여 upstream gradient 값을 이용해 다른 브랜치의 값과 곱합니다.

Summary so far…

• 신경망은 정말로 크고 복잡합니다.
• 그렇기에 모든 파라미터에 대해 gradient를 손으로 구하고 써내려가는 것은 비현실적입니다.
• 그래서 gradient를 계산하기 위해서 backpropagation을 사용하는 방법에 대해서 언급했고, 신경망의 핵심 기술입니다.
• 그리고 computational graph에서 chain rule을 재귀적으로 적용한 것입니다.
• 또한 각각의 노드에 대한 그래프 구조에 대해 어떻게 forward, backward API 구현으로 나타내는지에 대해서 이야기 했었습니다.
• forward pass에서는 나중에 gradient를 계산할 때 backward pass에서 chain rule에서 사용하기 위해 연산 결과를 계산하고 결과를 저장합니다.
• backward pass에서는 upstream gradient와 저장한 값들을 곱해 각 노드의 input에 대한 gradient를 구하고, 연결된 이전 노드로 통과시킵니다.

Fully-connected Neural Networks

Neural networks: the original linear classifier

• Neural Network를 알아보기 전에 linear classifier부터 짚고 넘어가겟습니다.
• linear classifier는 단순히 $W$ (weight) 와 input $x$ 를 곱해주는 $f=Wx$ 의 함수를 통해 클래스의 score를 계산했습니다.

• 하지만 다음과 같은 단점이 있었습니다.
  • Geometric Viewpoint
    • Linear classifiers로는 이런 형식의 데이터는 좋은 성능으로 분류하는 것이 불가능합니다.
  • Visual Viewpoint
    • 클래스 당 하나의 템플릿만 가질 수 있기때문에, 실제로 같은 class여도 정해진 템플릿과 비슷한 생김새가 아니라면 그 class로 인식될 수 없게 됩니다.
• 즉 정리해보면, Linear classifier의 문제점은 한 class 내에 다양한 특징들이 존재할 수 있지만, 모든 것들을 평균화시킨다는 점이 있습니다.
  • 앞서 CIFAR-10 예시를 보면 horse class에 대한 $W$ 행을 시각화한 이미지를 확인하면, 말의 머리가 양쪽으로 있는 것을 확인할 수 있습니다. 이러한 점이 하나의 linear classifier 이 가지는 문제가 드러나는 모습임을 알 수 있습니다.
  • 또한 car class 분류에 대한 $W$ 를 시각화 한 것을 보면 빨간색 차의 앞모습으로 보이는 물체만 있습니다. 빨간색이 아닌, 다른 색깔의 차 혹은 차의 앞모습이 아닌 옆모습의 이미지는 잘 분류할 수 없다는 문제가 있습니다.

만약, 하나의 class에 대해 하나의 $W$ (템플릿)이 아니라 여러 개의 템플릿이 존재하면 다양한 이미지에 대해서 분류를 해낼 수 있습니다. 예를들어, car class 에 대한 템플릿으로 빨간색 차, 노란색 차, 차의 옆모습 등등 의 다양한 템플릿을 생성하는 모습을 생각해볼 수 있습니다.

그러므로 Linear Classifier 모델의 성능이 나쁜 것을, 여러 개의 Layers를 사용한 neural networks 를 사용해서 해결하고자 합니다.

Neural networks: 2-layers also called fully connected network

• 지금까지의 linear score function은 $f(x, W) = Wx$
• 2-layer Neural Network부터 $f(x;W_1, W_2) = W_2max(0, W_1x)$ 형식으로 변합니다.
  • $W_1x$: 한 번 matrix-vector multiplication(행렬-벡터의 곱셈)
  • $max(0, W_1x)$: 0과 elementwise하게 max
    • $W_1x$ 의 음수 값은 0으로 대체(truncate)
    • H x 1 vector
  • $W_2max(0, W_1x)$: 다시 matrix-vector multiplication.
• 2-layer Neural Network의 형태: 선형(비선형(선형 변환(x))
  • 선형과 비선형의 합성함수를 계속 반복하여 적용한다.
  • 2개의 weight, 1개의 nonlinear activation을 이용합니다.
• Bias를 집어넣으면, $f(x;W_1,b1,\ W_2,b_2) = W_2max(0, W_1x + b_1) + b_2$

• $(W1)_{i,j}$ 성분을 살펴보겠습니다.
  • $h_1 = W_1x$
  • $h_i= ∑k(W_1){i,k} x_k$
  • $(W_1)_{i, j}$ 성분이 $x_j$ 를 $h_i$ 로 만드는 데에 주요한 역할을 합니다.(contribution)
• $h_i$ 는 $x_1 ~ x_D$ 이 각각 $(W_1)i$ 와 곱해져서 구성되는데, $h_i$ 를 구성하기 위해 $x_j$ 가 contribute한 만큼, $(W_1){i,j}$ 도 contribute합니다.
• 즉, $(W_1)_{i,j}$, 성분 = $h_i$ 에 대해서 $x_j$ 가 얼마만큼 contribute하는지 결정합니다.
  • $x$ 의 각 component가 $h$ 의 각 component로 contribute 합니다.($W_1$이 꽉 차있는 matrix이기 때문)
• 결과적으로, Fully-Connected NN : 이전 레이어의 모든 벡터들이 다음 레이어의 모든 벡터에 영향을 미칩니다.

Template of Neural Networks

• $W$ 의 row 하나(class 하나에 대응됨)를 그림처럼 나타낸 것이 template 입니다.
• Linear classifier 일때는 클래스 하나당 하나의 template이 만들어지며, 이는 $W_1$ 하나만 있는 것으로 생각 할 수 있습니다.
  • 입력과 직접적으로 연결되어 있으므로, 이 template을 공식화 할 수 있기 때문에 해석가능합니다.

• Neural Networks부터는 layer가 여러 개 입니다.
• $h$ 하나를 만들기 위해 템플릿($W_1$)을 한번 매칭한 후, 새로 만들어진 템플릿($W_2$)을 다시 한 번 조합합니다.
• 즉, 2-Layer Neural Network 에서는 카테고리당 1개의 템플릿만을 만드는 것이 아니고, 첫 번째 레이어에서 각각의 Weigth 마다 템플릿을 만들어 내고, 두번째 레이어에서는 이전에 만든 템플릿들을 재조합해서 class score를 만들어 냅니다.
  • 이처럼 1개의 템플릿이 아닌 여러 개의 템플릿의 조합으로 class를 표현한다고 해서 이 방식을 ‘Distributed Representation’이라고 부르기도 합니다.
  • 신경망 모델에서는 여러 개의 템플릿을 만들기에 중복된 정보를 가진 템플릿을 만들 수도 있지만, Network Pruning과 같은 기술들로 어느 정도는 해소할 수 있다고 합니다.

• 레이어가 두 개가 되면, horse에 대한 템플릿이 여러개일 때, 조합할 수 있게 됩니다.

• 하지만 각자 template에 대한 해석은 쉽지 않아집니다.
  

• 위 그림은 Layer가 6개인 6-layer Neural Networks를 그림으로 나타낸 것입니다.
  • 세로(=너비)는 input의 차원(dimension)에 대응합니다.
  • 보통 FC를 만들 때, H1 = H2 = H3 = H4 = H5를 같게 하는 경우가 많습니다. 혹은 1/2씩 곱해나가기도 합니다. (ex. H1=256, H2=128, H3=64, H4=32, H5=16)
• 위의 예시에서 $f = W_2max(0, W_1x)$ 이 이상으로 표현했습니다.
  • $max(0, W_1x)$ 는 ReLu 라고 불리는 자주 쓰이는 activation function입니다.
• 따라서 여러 개의 $W (W_1, W_2, …, W_n)$ 이 학습되고, 이 각각의 $W$ 들은 각각의 중간 과정에서 하나의 class에 대한 다른 템플릿을 만들어내는 효과를 가지게 됩니다.
• 또한 linear classifier의 문제를 해결하기 위해, 여러 개의 레이어를 사용하여 classifier에 비선형성을 부여하여, 선형 문제에서는 해결할 수 없었던 문제들에 들을 해결할 수 있게 됩니다.
  • $f = W(h(x))$ 의 형태에서 내부의 함수 $h(x)$ 는 비선형 함수여야만 합니다.

위와같이 layer를 깊게 쌓은 것을 Deep neural network 라고 지칭합니다.

• 정리하면 다음과 같습니다.
  • Neural network는 지금까지 다루어온 Linear score function을 여러 개 쌓은 형태입니다.
    • 입력 x를 받아 첫번째 W와 곱하고 출력한 일종의 score를 다시 받아 W를 곱하고 또 출력하고 이런식으로 반복하는 형태입니다.
    • 하나의 Layer가 아니라 여러개의 Layer로 구성됩니다.
  • 이때, 각각의 출력에 비선형함수를 사용해서 비선형성을 추가해줍니다.

• 만약 Neural network내에 activation function을 쓰지않으면 $f = W_1W_2x$ 형태가 됩니다.
  • 즉, x에 대한 선형변환만 될 뿐입니다.
• 선형변환은 decision boundary가 linear하게 그어지므로, 충분히 복잡한 함수를 표현할 수 없습니다.
  • 즉, ReLU와 같은 activation function이 있어야 $f(x; W)$ 가 $x$ 의 함수로서 더 다양한 함수를 표현할 수 있습니다.

Biologocal vs. artificual neurons

신경망이 무엇인지 함수로써 살펴보았는데, 보통 Neural Network를 설명할때는 신경망에 대한 생물학적 영감에 대해, 인간 두뇌의 신경망과 연관지어 설명합니다.

• dendrite(수상돌기)를 통해 특정 신호가 입력되게 됩니다.
• 들어온 신호들은 cell body 에서 종합되어 합쳐집니다.
• 이후, 합쳐진 신호는 axon 을 통해 다음 뉴런으로 전달되게 됩니다.
• 이때 받은 자극을 그대로 전달하지 않고, Input된 자극을 nonlinear하게 변환해서 전달해줍니다.

이러한 구조는 앞에서 다뤘던 computational graph의 각 노드에서 일어나는 과정과 굉장히 유사합니다.

• 이 현상을 수학적으로 모델링 한 것이 현재의 neural network 입니다.
  • input된 자극을 $x_0$ 라고 할 때, 시냅스를 통해 신호가 조금 바뀐 형태로 $w_0 * x_0$ 가 출력되며, cell body에서는 모은 정보를 종합하고, activation function인 $f$ 를 적용하여 다른 뉴런으로 전달해줍니다.
• 여기서 주의할 점은 인공신경망 neural network은 인간의 실제 두뇌 신경망과는 완전히 같지는 않다는 점입니다. 실제 인간의 두뇌는 훨씬 더 복잡한 비선형 시스템입니다.

Activation functions

• 실제 사용될 수 있는 많은 다른 종류의 activation function이 존재합니다.
• ReLu 가 가장 일반적으로 사용됩니다.

Neural networks: Architectures

• Neural network에서 위와 같이 모든 노드의 출력이 모든 다음 노드의 입력으로 연결된 layer 형태를 Fully connected layer라고 합니다.

Example feed-forward computation of a neural network

# forward-pass of a 3-layer neural network:

f = lambda x: 1.0/(1.0 + np.exp(-x)) # activation function (use sigmoid)
x = np.random.randn(3, 1) # random input vector of three numbers (3x1)
h1 = f(np.dot(W1, x) + b1) # calculate first hidden later activations (4x1)
h2 = f(np.dot(W2, h1) + b2) # calculate second hidden later activations (4x1)
out = np.dot(W3, h2) + b3 # output neuron (1x1)

Summary

해당 게시물은 이것이 코딩 테스트다 with 파이썬을 바탕으로 언제든지 블로그에 들어와서 보기위해 작성되었습니다.

그리디(Greedy)

• 그리디 알고리즘(탐욕법)은 “현재 상황에서 지금 당장 좋은 것만 고르는 방법” 을 의미합니다.
• 즉 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘으로, 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
• 그리디 해법은 그 정당성 분석이 중요 합니다.
  • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.

[문제 상황] 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.

최적은 해는 무엇인가요?

• 5 -> 7 -> 9로 가는 것이 가장 큰 값을 얻을 수 있는 방향입니다.

단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?

• 루트노드에서 인접한 노드는 7, 10, 8이므로 현재상황에서 가장 큰 값인 10으로 이동합니다.
• 10에서 이동할 수 있는 4와 3중 더 큰 값을 가지는 4로 이동할 수 있습니다.
• 여기서는 5 + 10 + 4 = 19로 최적의 해인 21보다는 낮은 값입니다.

그리디 알고리즘은 이처럼 단순히 매 상황에서 가장 큰 값만 고르는 방식이라고 말할 수 있습니다.

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.
• 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황해서, 이를 추론 할 수 있어야 풀리도록 출제됩니다.

거스름돈

문제 정의

• 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

문제 해설

• 해당 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제입니다.
• 간단한 아이디어를 생각하면 “가장 큰 화폐 단위부터 돈을 거슬러 주는 것” 입니다.
• N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 주고, 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있습니다.

예를 들어 입력으로 주어진 N이 1,260이라면 다음과 같이 가장 큰 화폐 단위부터 거슬러 주는 과정을 통해 1,260원을 모두 거슬러 줄 수 있습니다.

step 0 - 남은 돈: 1,260원

step 1 - 남은 돈: 260원

step 2 - 남은 돈: 60원

step 3 - 남은 돈: 10원

step 4 - 남은 돈: 0원

Solution

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

• 그리디 알고리즘으로 문제의 해법을 찾았을 때는 정당성을 검토해야 합니다.
• 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유
  • 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문 입니다.
• 만약 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면?
  • 이 경우 그리디 알고리즘으로 4개의 동전(500원 + 100원 + 100원 + 100원)을 거슬러 줘야 합니다.
  • 하지만 최적의 해는 2개의 동전 (400원 + 400원)을 거슬러 주는 것입니다.
  • 이 문제에서는 큰 단위가 작은 단위의 배수 형태이므로, ‘가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다’는 아이디어는 정당합니다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있습니다.

큰 수의 법칙

문제 정의

• 예제의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M 번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
• 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.
• 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자. 이 경우 두 번째원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다. 결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4인 28이 도출된다.
• 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

입력 조건

• 입력 조건첫째 줄에 N (2N≤ 1,000), M(1 ≤ M ≤ 10,000), K(1≤K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 출력 조건첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

Test Case

[input]
5 8 3
2 4 5 4 6

[output]
46

My Solution

_, M, K = map(int, input().split())
input_data = list(map(int, input().split()))

input_data.sort(reverse=True)
first_data = input_data[0] # 첫번째로 큰 수
second_data = input_data[1] # 두번째로 큰 수

result = 0

for m in range(M):
    if m == 0:
        result += first_data
        continue
    
    if m % K == 0:
        result += second_data
    else:
        result += first_data

print(result)

Solution 1

# N, M, K를 공백으로 구분하여 입력받기
from unittest import result


n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort() # 입력받은 수들 정렬하기
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두 번째로 큰 수

result = 0

while True:
    for i in range(k): # 가장 큰 수를 K번 더하기
        if m == 0: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1
        
    if m == 0: # m이 0이라면 반복문 탈출
        break
    
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때마다 1씩 빼기

print(result) # 최종 답안 출력

• 이 문제는 전형적인 그리디 알고리즘 문제로, 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 됩니다.
• 연속으로 더할 수 있는 횟수는 최대 K번이므로 ‘가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산’을 반복하면 됩니다.

Solution2

# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
data = list(map(int, input().split()))

data.sort() # 입력 받은 수들 정렬하기
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기

print(result) # 최종 답안 출력

• Test Case를 보면 다음과 같다.
  • 가장 큰 수: 6
  • 두 번째로 큰 수: 5
• 이때 M이 8이고, K가 3이라면 (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5)와 같이 더했을 때 합을 최대로 할 수 있다. 정답은 46이 됩니다.
• 이 문제를 풀려면 가장 먼저 반복되는 수열 에 대해서 파악해야 합니다.
• 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있습니다.
  • 위의 예시에서는 수열 {6, 6, 6, 5}가 반복됩니다.
  • 반복되는 수열의 길이는 (K+1)로 위의 예시에서는 4가 됩니다.
  • 따라서 M (K + 1)로 나눈 몫이 수열이 반복되는 횟수가 됩니다.
  • 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 됩니다.
• 이때 M이 (K + 1)로 나누어떨어지지 않는 경우도 고려해야 합니다.
  • 그럴 때는 M을 (K + 1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 합니다.
  • 즉, ‘가장 큰 수가 더해지는 횟수’는 다음과 같습니다.

[int(M\ /\ (K\ +\ 1))\ *\ K\ +\ M\ \%\ (K\ +\ 1)]

숫자 카드 게임

문제 정의

• 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
  1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
  2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
  3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
  4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

예를 들어 3×3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자.

3 1 2
4 1 4
2 2 2

여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다. 따라서 이 예제에서는 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다. 카드들이 N × M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

입력 조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1≤ N, M≤ 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력 조건

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

Test Case

[input]
2 4
7 3 1 8
3 3 3 4

[output]
3

My Solution

N, _ = map(int, input().split())

result = 0
for i in range(N):
    dummy = min(list(map(int, input().split())))
    result = max(dummy, result)

print(result)

• 이 문제를 푸는 아이디어는 바로 각 행마다 가장 작은 수를 찾은 뒤에 그 수중에서 가장 큰 수를 찾는 것 입니다.
• 입력 조건에서 입력으로 들어오는 수는 모두 10,000 이하이므로 단순히 배열에서 가장 작은 수를 찾는 기본 문법을 이용하여 각 행에서 가장 작은 수를 찾은 다음 그 수중에서 가장 큰 수를 찾는 방식으로 문제를 해결할 수 있습니다.

Solution 1

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = min(data)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

Solution2

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

1이 될 때까지

문제 정의

• 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단,두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
  1. N에서 1을 뺀다.
  2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 N (2 N 100,000)과 K2 ≤K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다.
• 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력 조건

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

Test Case

[input]
25 5

[output]
2

My Solution

n, k = map(int, input().split())

result = 0
while 1:
    if n == 1:
        break
    
    result += 1
    if n % k == 0:
        n /= k
    else:
        n -= 1

print(result)

• 해당 문제는 주어진 N에 대하여 ‘최대한 많이 나누기’ 를 수행하면 됩니다.
  • 왜냐하면 어떠한 수가 있을 때, ‘2 이상의 수로 나누는 것’이 ‘1을 빼는 것’보다 숫자를 훨씬 많이 줄일 수 있기 때문입니다.
  • 문제에서는 K가 2 이상의 자연수이므로, 가능하면 나누는 것이 항상 더 숫자를 빠르게 줄이는 방법이 됩니다.
• 따라서 다음의 과정을 반복할 수 없을 때까지 반복하면 정답을 구할 수 있다.
  • N이 K의 배수가 될 때까지 1씩 빼기
  • N을 K로 나누기

예를 들어 N = 25, K=3 일 때는 다음과 같습니다.

6번의 과정으로 N = 1을 만들 수 있습니다.

Solution 1

n, k = map(int, input().split())
result = 0

# N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

while n > 1:
    n -= 1
    result += 1

print(result)

Solution2

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

• 해당 코드는 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식입니다.