[4주차] Optimization

 Optimization

최적화란 말 그대로 최적의 해를 찾도록 하는 것이다. 어떠한 목적 함수에 대한 parameter(𝜽) 를 추정하는 Cost Function 𝐽(𝜽) 가 있다고 가정해보자. 우리가 이 비용 함수의 모양을 알 수 있다면, 초기 값을 어디로 잡을지와 어떤 방향으로 개선할지 알 수가 있다. 하지만, 다차원의 함수 모양을 알 수 없기 때문에 이를 해결하기 위한 다양한 최적화 기법을 다뤄보도록 한다.

\[ 𝐽(𝜽) = \frac{1}{n} \sum \sideset{_{}^{}}{_{(x_i,y_i) ∈ D}}{} \, {L(y_i, f(x_i; 𝜽))} \]

initial point to optimal point w*

 

 How to Optimize a given Cost Function?

먼저, 전통적인 최적화에 대한 개념과 머신 러닝에서의 최적화 개념을 살펴보고 최적화에 사용되는 용어와 방법을 알아보도록 한다.

 

- Optimization in Machin Learning

전통적인 의미에서의 최적화는 목적 함수(objective function) 그 자체를 직접 최적화하는데 의미가 있었다.

하지만, 기계 학습(지도학습 기반의)에서 말하는 최적화는 일반화 성능을 만족하여야 한다.

다시 말하면, 데이터로부터 학습한 모델의 성능이 실제 데이터가 들어왔을 경우에도 동일한 성능을 보일 것인가에 대한 대답이 되어야 한다. 따라서, 목적 함수(objective function) 최적화가 아닌 비용 함수(cost function) 최소화가 곧 일반화 성능을 만족하는 것으로 기대할 수 있다고 설명한다. (cost function = summation of loss function)

 

- Empirical Risk Minimization

1) Expected Risk (또는 일반적으로 Risk)

  -. 일반적으로 Risk 라고 하면,

  우리가 알지 못하는 실제 데이터 분포(true data distribution - 𝑝 data) 의 일반화 오류의 기대치를 말한다. 

 

2) Empirical Risk

   -. 경험적 Risk 라고 하면,

   이미 관측된 경험 데이터 분포(empirical data distribution - 𝑝̂ data) 의 일반화 오류의 기대치를 말한다.

 

3) Empirical Risk Minimization (ERM)

   -. 따라서, 이미 관측된 training dataset 으로부터 뽑은,

   데이터의 일반화 오류의 기대치를 최소화 하는것이 바로 ERM 이다.

   -. 하지만 실제로는 학습 데이터에 의존된 모델이 나타나는 오버피팅을 방지하기 위해서

   파라미터 제약을 위한 정규화를 같이 사용한다.

   -. 또는, 용량 제어 관점에서의 Structural Risk Minimization (SRM) : 가설 공간 복잡성과 훈련 모델 피팅 간의 trade-off 관계를 조절하는 방법를 사용하기도 한다. (e.g., some regularization techniques, support vector machines)

 

최적화는 앞서 DNN 단계 중 2, 3. 부분에 해당한다.

 

- Parameter Initialization

그렇다면, 초기해의 파라미터는 어디에서 시작해야 하는 것인가?

초기해를 잘못 잡게되면, local min 값으로 빠지거나 optimal 값으로 도달하는데 오래 걸릴 수 있다.

현재까지는 초기해를 딱 이렇게 잡아야 한다는 결론은 없다. 다만, 휴리스틱(heuristics)하게 이 정도면 무난한 초기해라고 결정할 수 있는 근거는 있다.

 

① Zero Initialization (all the parameters with zero)

   -. 만약, 모든 parameter = 0 초기해로 설정한다면 다음과 같은 문제가 있다.

   1) ReLU Activation Function 사용 시, Gradient 계산을 할 수 없다.

   2) 히든 레이어 안의 모든 유닛들은 몇개가 있던 동일한 계산을 수행할 것이다.

   ※ 동일한 parameter setting 은 동일한 결과를 초래하여 결국 symmetry 한 결과가 발생하고 뉴럴넷을 사용하는 의미가 없게 된다. 따라서, 중요한 것은 파라미터 설정 시 이 대칭(symmetry)을 깨야한다는 것이다.

 

② Random Initialization

   -. 랜덤성을 띄면, 동일한 계산을 하지 않기 때문에 확실하게 대칭을 깰 수 있다.

   -. 다만, 초기 파라미터를 너무 작게 잡거나, 너무 크게 잡으면 문제가 발생할 수 있다.

   1) 너무 작게 잡은 경우

   : Activation range 축소로 인한 느린 수렴

   2) 너무 크게 잡은 경우

   : Exploding values 또는 sigmoid/tanh 사용 시 Vanishing gradient 문제가 발생

 

③ Heuristics (Random Initialization with normalization)

   -. 랜덤하게 하되 표준화를 적용하여 적당히 설정한다.

   가령, m개의 입력과 n개의 출력이 완전 연결 계층에 있다면 다음과 같은 균일 분포에서 샘플링된다.

\[ U{(-\sqrt{\frac{6}{m+n}},\sqrt{\frac{6}{m+n}})} \]

 

④ Transfer Learning (전이 학습)

   -. 다음 정규화에서 소개하겠지만, 이전 학습했던 초기 파라미터 값을 전이하여 일부 적용하는 방법이다.

 

- Training a Neural Network

다음 과정을 거쳐 비용 함수에 대한 parameter update 를 반복 수행하여 최적해에 접근하게 된다.

경사 하강법(gradient descent)

• Optimization based on First-Order Approximation (Gradient)
  \(𝜽 := 𝜽-𝜖𝛻_𝜽𝐽(𝜽)\) ⋯ update parameter 𝜽
  그렇다면, 왜 parameter 𝜽 업데이트를 위와 같이 해야만 하는가?
  일단, 목적 함수 𝐽(𝜽) 를 테일러 전개해보면
  \[ 𝐽(𝜽) = 𝐽(𝜽_0) + {(𝜽-𝜽_0)}^𝑇𝛻_𝜽{𝐽(𝜽_0)} {\color{Red}+ \frac{1}{2} {(𝜽-𝜽_0)}^𝑇𝛻_𝜽^2{𝐽(𝜽_0)}{(𝜽-𝜽_0)} + ⋯} \]
  여기서, First-order approximation 값은 \(𝜽\)와 \(𝜽_0\)가 아주 가깝다고 가정하면 아래와 같다.
  \[ 𝐽(𝜽) ≃ 𝐽(𝜽_0) + {(𝜽-𝜽_0)}^𝑇𝛻_𝜽{𝐽(𝜽_0)} \]
  이 식에서, 목적 함수를 줄이는 방향(\(𝜽⇒𝜽_0\))으로 나아가야 하기 때문에
  \[ 𝐽(𝜽)-𝐽(𝜽_0) ≃ {(𝜽-𝜽_0)}^𝑇𝛻_𝜽{𝐽(𝜽_0)}＜0 \]
  이를, parameter 𝜽 에 관한 결과는 아래와 같다. (𝜖 = step size;learning rate)
\[ \eqalign{ &(𝜽-𝜽_0)∝-𝛻_𝜽𝐽(𝜽) \\ &(𝜽-𝜽_0)=-{\color{Red}𝜖}𝛻_𝜽𝐽(𝜽){\color{Red},𝜖＞0} \\ &𝜽-𝜽_0=-{\color{Red}𝜖}𝛻_𝜽𝐽(𝜽){\color{Red},𝜖＞0} } \]

경사의 반대 방향으로 아주 조금씩 이동

※ \(𝜽_0 \, to \, 𝜽\) 거리가 아주 가깝다는 가정이 깨지지 않으려면, 𝜖 값은 양수이되 아주 작은 값이어야 한다.
- Gradient Descent vs. Stochastic Gradient Descent
  -. 만약 계산량이 많은 대용량 데이터를 다룬다고 하면,
  mini-batch (size=1) 샘플을 뽑아 데이터의 일부로 확률적 경사 하강법(Stochastic Gradient Descent)을 시행하기도 한다.

Note
• epoch: 모든 training dataset 에 대한 iteration 과정을 1 cycle 끝낸 것 (∀ mini-batch)
• mini-batch: 샘플 크기, 일반적으로 size=32 이상은 피하도록 한다.
• iteration: 여러 개의 mini-batch 중 1개의 parameter update 1회 수행한 것

gradient 고려한 방향 찾기

learning rate 고려한 스탭 개선

※ 시간에 따라 Learning Rate 를 줄이면서, 각각의 parameter 마다 다른 학습 률을 적용한다.

Adam Optimizer

• Optimization based on Second-Order Approximation (Hessian)
  위의 First-Order approximation 테일러 전개식에서 이제 Second-Order 까지 고려하면 다음과 같다.
  \[ 𝐽(𝜽) ≃ 𝐽(𝜽_0) + {(𝜽-𝜽_0)}^𝑇𝛻_𝜽{𝐽(𝜽_0)} + {\color{Red}\frac{1}{2} {(𝜽-𝜽_0)}^𝑇𝛻_𝜽^2{𝐽(𝜽_0)}{(𝜽-𝜽_0)}} \]
  \({\color{Red}𝑯(𝜽_0) = 𝛻_𝜽^2{𝐽(𝜽_0)}}\) is the Hessian of 𝐽 with respect to \(𝜽\) evaluated at \(𝜽_0\).
  이 식에서, 목적 함수를 줄이는 방향(\(𝜽⇒𝜽_0\))으로 나아가야 하기 때문에
  \[ \operatorname*{argmin}\limits_{𝜽}\, {[𝐽(𝜽)-𝐽(𝜽_0)]} ≃ {[{(𝜽-𝜽_0)}^𝑇𝛻_𝜽{𝐽(𝜽_0)} + \frac{1}{2} {(𝜽-𝜽_0)}^𝑇{{\color{Red}𝑯(𝜽_0)}}{(𝜽-𝜽_0)}]}＜0 \]
  이를, parameter 𝜽 에 관한 결과는 아래와 같다. (이제 learning rate 𝜖 불필요)
\[ \eqalign{ &𝛻_𝜽{[𝐽(𝜽)-𝐽(𝜽_0)]}=0 \\ &𝜽^*=𝜽_0{\color{Red}-{𝑯(𝜽_0)}^{-1}}𝛻_𝜽{𝐽(𝜽_0)} } \]

convext function with quadratic approximation

- 기본적인 Newton's Method 기반으로 2차 도함수(convex quadratic) 값으로 빠르게 접근한다. (no learning rate)
  하지만, d×d matrix inversion : 모든 parameter 에 대한 gradient 와 hessian 값을 계산해야 한다. (=no mini-batch)
- Inexact Newton Method (Conjugate Gradient) Stop 조건을 걸어 바운드되는 근사값으로 개선하거나,
- Quasi-Newton Method (BFGS, L-BFGS) curvature condition 을 통해 근사값을 개선해본다.
  ※ Large dataset 에 대한 hessian 계산량을 잡기위해 Stochastic Version 및 다양한 연구가 진행중이다.

Practical Guideline Lecture 6 of Stanford CS231n
• Adam: 일반적으로 좋은 성능을 발휘한다. (mini-batch)
• L-BFGS: full-batch updates 할수 있다면, L-BFGS 방법도 나쁘지 않다. (small dataset)