Gradient Descent Method

※ Challenges of Optimization Problem

 

Finding minimum by closed form is often difficult or impossible.

Quadratic functions in many variables

  - System of equations for partial derivatives may be ill-conditioned.

m개의 변수보다 더 많은 파라메터를 가진 경우 기본적으로 analytic solution 을

구하는 것이 불가능하다.

 

Other convex functions

 - Global minimum exists, but there is no closed form solution.

convex function은 위와 같이 웅덩이 모양의 볼록 함수 모양이다.

위와 같이 아래로 볼록한 형태에는 최적의 해를 구할 수 있지만, 

analytic 한 closed form 으로 표현되지 않는 경우에는 구할 수 없다.

 

Nonlinear functions

 - Ppartial derivatives are not linear.

 - E.g., \(f(x_{1}, x_{2}) = x_{1}(sin(x_{1}x_{2})) + x_{2}^{2}\)

 - E.g., sum of transfer functions in neural networks.

 

Many approximate methods for finding minima

 - Gradient descent method

 - Newton method

 - Gauss-Newton

 - Etc.

최적의 해를 찾기 위한 근사해로 approximate solution 을 이용한다.

대표적으로 1차 미분을 사용하는 Gradient descent method 가 있다.

 

 

※ What is a Gradient?

 

Gradient is a vector.

Each element in the gradient is the partial derivative of function with

respect to one of the variables.

\(\bigtriangledown f(w) = \bigtriangledown f(w_{1}, w_{2}, ..., w_{m}) = \begin{bmatrix} \frac{\partial f(w)}{\partial w_{1}}\\ \frac{\partial f(w)}{\partial w_{2}} \\ \vdots \\ \frac{\partial f(w)}{\partial w_{m}} \\ \end{bmatrix}\)

 

정리하자면 \(w_{1}\) 부터 \(w_{m}\) 까지의 편미분한 각각의 값들을 모아놓은 것이 gradient 이다.

 

It is the vector \(\bigtriangledown f(p)\) whose components are the partial derivatives

of \(f\) at a given point \(p\).

 

 

※ Finding Some Minimal Positions

 

How to minimize the error between \(f(x)\) and \(y\)?

\(E(w_{1}, w_{2}, ..., w_{m}) = \sum_{(x, y)\in Data}^{} (y - f(x; w_{1}, w_{2}, ..., w_{m}))^{2}\)

 

 

결국 주어진 error function을 편미분하여 편미분한 값이 0인 지점을 찾는다.

위와 같은 경우에 편미분한 값이 0인 지점이 여러개 존재하는데, 이 많은 부분 중에서

특정한 부분을 Gradient descent를 통해서 찾게 되는 것이라고 볼 수 있다.

 

 

※ How to Update w?

 

We want to update w satisfying \(E(w_{new}) < E(w)\).

  - When \(w_{new} = w + \bigtriangleup w, E(w_{new}) < E(w)\)

새롭게 결정한 \(w_{new}\) 에 대해 error function 값을 업데이트 할 때,

이전에 결정한 \(w\) 에 대한 error function 값보다 작은 방향으로 \(w_{new}\) 를 결정해야 한다.

 

The slope at a position == deffierential value at a position

  - If \(E(w)\) is differentiable, it is easy to find out the slope.

이러한 방법은 error function 이 모든 구간에 대해 미분 가능해야 적용이 가능함을 알 수 있다.

 

 

위와 같이 특정 지점에서 미분하여 왼쪽으로 이동하는게 좋을지, 오른쪽으로 이동하는게 좋을지에 

대해서 살펴보도록 한다.

 

Move the reverse direction of the gradient.

  - If the slope is positive, move w to the negative direction.

  - If the slope is negative, move w to the positive direction.

When \(w_{new} = w - \frac{\partial E}{\partial w}, E(w_{new}) < E(w)\)

 

 

위와 같이 기울기가 음수인 경우에 대해선 오른쪽으로 이동해야 된다.

만약 w의 미분 값이 양수일 경우에 대해선 왼쪽으로 이동해야 된다.

 

Suppose that \(w\) is a vector and so is \(\bigtriangleup w \).

When we consider the sum of two vectors, the sum of two vectors can be quite large,

beacause of taking a large step \(\bigtriangleup w\).

  - This is important because if we make large updates \(\bigtriangleup w\) to \(w\),

     we might miss out on global minimum of error function \(E(w)\).

 

 

미분 값을 더하는 과정에서 미분 값이 다소 크다면 값을 조정하는 방법이 존재한다.

위와 같이 미분 값에 임의의 값을 곱해서 더하는 방법이 존재하는데 임의의 값을 learning rate 라 부른다.

그리고 \( \eta \) 기호를 에타라고 부른다.

 

Move until the gradient of E(w) is zero.

Using a learning rate that limits the size of update for w.

 

 

위와 같이 과정을 계속해서 반복하여 이동한다면 궁극적으로 주어진 error function 값이 0에 가까운 지점으로

다가갈 수 있게 된다.

그리고 \( \eta \) 값이 매우 작다면 이동폭을 매우 줄여서 이동하게 된다.

 

 

※ What is the Learning Rate?

 

\( \eta \) is used to control the step size of step length.

  -> Too small \( \eta \) can cause slow convergence.
  -> Too large \( \eta \) can cause overshoot the minima and diverge.

 

 

왼쪽 케이스는 \( \eta \) 값이 굉장히 작아서 gradient 값이 0이 되는 지점에 도달하기까지 너무나도

오랜 시간이 소요된다는 점이다.

오른쪽 케이스는 \( \eta \) 값이 너무 커서 gradient 값이 0이 되기는 커녕 아예 애초에 학습이 전혀

이루어지지 않는 현상이 발생하게 된다.

 

 

※ Gradient Descent (GD)

 

Randomly choose an initial solution \(w^{0}\), 

Repeat

  \(w^{t+1}=w^{t}-\eta \frac{dE}{dW}\mid_{w=w^{t}} \)
  learning rate: controlling the step size.

 

Until stopping condition is satisfied.

  - \(|w^{t+1}-w^{t}|\) is very small.

  - \(f(w)\) little moves.

  - fixed number of iterations.

 

처음에는 \(w^{0}\) 값을 랜덤하게 결정하고, \(\eta\) 값을 0.1 ~ 0.01 으로 지정한다.

그 후에는 계속해서 w 값에 대응되는 gradient 값을 구해서 계속 w 값을 업데이트한다.

그리고 stopping condition 을 통해 학습을 종료시킬 수 있다.

 

Randomly choose an initial solution \(w^{0}\), \(w^{1}\), 

Repeat

  \(w_{0}^{t+1}=w_{0}^{t}-\eta \frac{\partial E}{\partial w_{0}}\mid_{w_{0}=w_{0}^{t}, w_{1}=w_{1}^{t}} \)
  \(w_{1}^{t+1}=w_{1}^{t}-\eta \frac{\partial E}{\partial w_{1}}\mid_{w_{0}=w_{0}^{t}, w_{1}=w_{1}^{t}} \)

 

Until Stopping condition is satisfied.

 

w값이 두 개인 경우에는 각각에 대해서 parallel 하게 계속해서 업데이트 해주면 된다.

 

Convex Function

 

※ What is the Convex Function?

 

A function \(f\) is convex ↔ the function \(f\) is below any line segment 

between two points on \(f\) .

  \(f(tx + (1 - t)x')\) \(\leq\) \(tf(x) + (1 - t)f(x') \) for any \(x, x' \in  X\) and \(t \in [0, 1]\)

 

Convex function 이란 주어진 함수가 위와 같은 식을 만족한다.

Convex function 은 최적의 해를 찾을 수 있음을 보장할 수 있게 되어있다.

따라서 주어진 함수가 Convex function 인지 아닌지는 중요한 요소이다.

 

 

Convex function 임을 확인하기 위해 위와 같이 임의의 두 점에 대해서 

\(f\) 함수에 대해 적용하는 경우와 각각을 따로 나누어서 \(f\) 에 대해 적용하고 t 부분으로

각각 곱한 경우에 대해 상대적으로 이 차이가 얼마인지를 판단하는 방식으로 결정할 수 있다.

하나라도 위와 같은 조건을 만족하지 않는다면 Convex function 이 아니다.

 

 

※ Examples of Convex Functions

 

Quadratic function: \(f(x) = x^{2}\)

Exponential functions: \(f(x) = 2^{x}\)

Negative logarithm function: \(f(x) = -lnx\)

 

 

항상 두 점을 지나는 직선 아래에 함수 값이 존재하는 것을 알 수 있다.

 

 

※ Non-convex function

 

\(\bigtriangledown f(w^{*}) = 0 \Leftrightarrow  w^{*} \) is a global min, 

local min or saddle point (also called stationary points)

Most algorithms only converge to stationary points.

 

 

Non-convex function 인 경우에는 non-linear 모델로 구성된 많은 parameter 를 가진

뉴럴 네트워크 모델이 있다.

오른쪽과 같이 반드시 global optima 를 보장해주지 못할 수 있다.

때로는 local optima 이거나 saddle point 에 빠질 수 있게 된다.

 

Linear Regression using the Gradien Descent Method

 

※ Computing the Gradient

 

Calculate the gradient for a given error function.

\(E(w_{0}, w_{1}) = 2w_{1}^{2} + 3w_{0}^{2} - 6w_{1} - 6w_{0} + 4w_{1}w_{0} + 5\)
\(\bigtriangledown E(w_{0}, w_{1}) = [4w_{1} + 4w_{0} - 6, 4w_{1} + 6w_{0} - 6]\)

 

 

gradient descent 를 이용하여 \(w_{0}, w_{1}\) 두 개의 파라메터를 parallel 하게 

\(w_{0}, w_{1}\) 을 업데이트를 계속해서 반복한다.

실제로 저 식을 대입했을 때 어떻게 달라지는지 살펴보도록 한다.

 

Find \(w_{0}, w_{1}\) that minimizes the error function.

  - Choose a learning rate \(\eta\), e.g, \(\eta\) = 0.1

  - Initialize \(w_{0}^{0}, w_{1}^{0}\) as random values, e.g., \(w_{0}^{0} = 1, w_{1}^{0} = 1\) 

 

 

위와 같이 병렬적으로 동시에 이전 값을 사용하여 업데이트하는 것을 볼 수 있다.

이러한 과정을 계속해서 반복하다가 100번째에 도달하게 되면

\(w_{0}^{100} = 0.00007713\), \(w_{1}^{100} = 1.49989171\) 이 되게 된다.

 

 

단순하게 gradient 값이 0 이 되도록 하는 \(w_{0}\), \(w_{1}\) 의 값은 \(0, 1.5\) 이였다.

그러나 gradient descent method 를 활용한 결과 거의 근접한 결과에 도달했음을 알 수 있다.