선형대수학 :: Gradient Descent Methods

Gradient Descent Methods

경사 하강법

---

 

Optimization Problems

최적화 문제

 

• f(x)가 최소가 되도록 하는 x를 찾는 문제
• 이때 f는 미분 가능 함수만을 고려.

---

Gradient

• f(x)가 최소가 되도록 하는 x를 찾는 방법
  1. 출발 지점에서 함수 그래프를 따라서 기울기를 보며 x쪽으로 계속 내려간다.
  2. 그렇게 내려가다 보면 언젠간 x를 찾게 된다.

 

$\begin{gather*}∇f(x)=\begin{bmatrix} \frac{∂f(x)}{∂x_1} \\ \frac{∂f(x)}{∂x_2} \\ ...\\ \frac{∂f(x)}{∂x_n} \\ \end{bmatrix}\end{gather*}$

 

• 각 원소는 xn에 따른 f(x)의 변화량, 즉, 기울기를 의미.

---

Taylor’s Theorem (first-order approximation)

f(x) 근사하는 방법

• x 변수가 하나 일 때,
  미분이 2번 가능해서 이계도함수가 존재하고,
  이계도함수가 연속함수라면
  다음과 같이 근사 가능.
  
  
  

  $\begin{gather*}f(x)=f(a)+f'(a)(x-a) + o(|x-a|)\end{gather*}$

  
  
  • x가 a에 가까우면 o 무시 가능
    
    
    

    $\begin{gather*}|x-a|≈0, \ \ \ \ \ f(x)≈f(a)+f'(a)(x-a)\end{gather*}$

  • small-o(notation)
    
    
    

    $\begin{gather*}\lim_{\delta \to0}\frac{o(\delta)}{\delta}=0\end{gather*}$

    
    의미 : δ보다 o(δ)가 0으로 더 빨리 간다.

• x 변수가 많을 때 (x가 벡터로 주어질 때)
  미분이 2번 가능해서 이계도함수가 존재하고,
  이계도함수가 연속함수라면 
  다음과 같이 근사 가능.
  
  
  

  $\begin{gather*}f(x)=f(a)+(∇f(a))^T(x-a) + o(||x-a||)\end{gather*}$

  
  
  • x가 a에 가까우면 o 무시 가능
    
    
    

    $\begin{gather*}||x-a||≈0, \ \ \ \ \ f(x)≈f(a)+(∇f(a))^T(x-a)\end{gather*}$

---

 

Matrix Norms

• Induced Norm
  
  

  $\begin{gather*}||A||=\max_{x\not=0}\frac{||Ax||}{||x||}\end{gather*}$

  
  Ax 벡터 norm을 x 벡터 norm으로 나눈 것들 중 최댓값이 행렬 A의 induced norm
  여기서 A는 2차원만을 가정.

• A^T=A 즉, symmetric 일 때
  eigenvalue가 실수
  A^TA = A^2 는 symmetric positive semidefinite
  Induced Norm은 다음과 같다.
  
  

  $\begin{gather*}||A||=\lambda_{max}(A)=max_i|\lambda_i|\end{gather*}$

• 특징
  
  

  $\begin{gather*}||Ax||\le||A||||x||, \ \ \ \ \forall x\end{gather*}$

---

 

Gradient Descent Methods - Motivation

• x_α : x에서 그라디언트 방향으로 조금 움직임, 이때 α는 충분히 작은 값.
  
  

  $\begin{gather*}x \in R^n, \ \ \ \ ∇f(x) \not=0, \ \ \ \ \alpha>0\\ x_\alpha=x-\alpha∇f(x)\end{gather*}$

• 테일러 정리에 적용

$\begin{gather*}x\to x_\alpha, \ \ \ \ \alpha\to x \\ f(x_\alpha)=f(x)+(∇f(x))^T(x_\alpha-x) + o(||x_\alpha-x||)\end{gather*}$

 

$\begin{gather*}x_\alpha\to x-\alpha∇f(x) \\ f(x_\alpha)=f(x)-\alpha||∇f(x)||^2 + o(\alpha) \\ ≈f(x)-\alpha||∇f(x)||^2 \end{gather*}$

 

• 결국 x가 그라디언트를 따라 움직이면 함숫값이 줄어든다. (충분히 작은 α에 대해서)
  
  

  $\begin{gather*}f(x-\alpha∇f(x)) < f(x)\end{gather*}$

---

Convergence Rate Analysis for Quadratic Cost Functions

• A : symmetric positive definite
  ⇒ x^TAx > 0
  
  

  $\begin{gather*}f(x)=\frac{1}{2}x^TAx\end{gather*}$

  
  f(x)의 최솟값 찾기.
  positive definite에 의해 x^TAx > 0, x≠0 이므로 x가 0에 가까울수록 최소.
• Gradient descent method 적용
  즉, x를 초기값에서 그라디언트 방향으로 계속 움직이면
  언젠간 f(x)를 최소로 하는 x에 닿을 것이다.

 

$\begin{gather*}x_{k+1}=x_{k}-\alpha∇f(x_k)\end{gather*}$

 

$\begin{gather*}x_k \not=0, \\ \frac{||x_{k+1}||}{||x_k||} \le \max\{|1-\alpha m|, |1-\alpha M|\}\end{gather*}$

 

이때, M은 A의 eigenvalue중 최대이고, m은 최소이다.

 

---

증명

 

$\begin{gather*}f(x)=\frac{1}{2}x^TAx, \ \ \ \ ∇f(x_k) = Ax_k\end{gather*}$

 

$\begin{gather*}x_{k+1}=x_{k}-\alpha∇f(x_k) \\ =(I-\alpha A)x_k \end{gather*}$

I-alpha A는 symmetric 이므로

$\begin{gather*}x^Tx =||x||^2, \ \ \ \ \\ ||x_{k+1}||^2=(x_k(I-\alpha A))^T(I-\alpha A)x_k \\ =x_k^T(I-\alpha A)^2x_k \\ \le \lambda_{max}((I-\alpha A)^2)||x_k||^2\end{gather*}$

 

I-alpha A의 eigenvalue들 중 절댓값이 가장 큰 것을 골라야 하므로

$\begin{gather*}\frac{||x_{k+1}||}{||x_k||} \le \max\{|1-\alpha m|, |1-\alpha M|\}\end{gather*}$

 

---

• 적당한 α 에 대하여
  
  

  $\begin{gather*}\alpha=\frac{2}{m+M}, \ \ \ \ \frac{||x_{k+1}||}{||x_k||} \le \frac{M-m}{M+m}\end{gather*}$

• 의미 분석
  k가 커질수록 ||x_k||는 0으로 수렴한다. 
  즉, x_k는 0으로 수렴한다.
  M-m이 작을수록 0에 빠르게 수렴한다. 
  따라서 다음이 성립한다.
  
  

  $\begin{gather*}||x_k||\le (\frac{M-m}{M+m})^k||x_0||\end{gather*}$

---

Slow Convergence of GD

• 예시, 이때 0<b≤1
  
  

  $\begin{gather*}f(x,y)=\frac{1}{2}(x^2+by^2)\end{gather*}$

• 다음처럼 행렬 곱으로 나타내기
  
  

  $\begin{gather*}f(x,y)=\frac{1}{2}\begin{bmatrix}x & y\end{bmatrix}\begin{bmatrix}1 & 0 \\ 0 & b\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix}\end{gather*}$

  
  이때 가운데 [1 0 \\ 0 b]는 symmetric 이므로 positive definite
  즉, 경사 하강법 적용 가능
• 경사하강법 적용
  
  

  $\begin{gather*}x_{k+1}=x_{k}-\alpha∇f(x_k)\end{gather*}$

  
  이므로
  
  

  $\begin{gather*}\begin{bmatrix}x_{k+1} \\ y_{k+1}\end{bmatrix}=\begin{bmatrix}x_{k} \\ y_{k}\end{bmatrix}-\alpha\begin{bmatrix}x_{k} \\ by_{k}\end{bmatrix}\end{gather*}$

• M=1, m = b 이므로 적당한 α에 대하여
  
  

  $\begin{gather*}\begin{Vmatrix}x_{k} \\ y_{k}\end{Vmatrix}=(\frac{1-b}{1+b})^k\begin{Vmatrix}x_{0} \\ y_{0}\end{Vmatrix}\end{gather*}$

  
  b=1 일수록 수렴이 빠르다. (직진성을 띤다.)
  b가 작을수록 수렴이 느리다. (곡선을 띤다.)