[Incarnate the Algorithm] Gradient Descent

gradient descent는 first-order optimization에서 가장 대표적인 알고리즘이다.

zero-order optimization에서와 마찬가지로 이전의 위치에서 가장 cost를 적게 줄이는 descent direction을 구해서 다음 위치를 계산한다. 이때, zero-order와는 다르게 미분을 통해 descent direction을 설정한다. 

 

w_k = w_(k-1) - alpha * grad[g{w_(k-1)}]이 gradient descent 알고리즘의 식이다. ( 헷갈리지 않도록 다른 괄호로 표기했다 )

# alpha : steplength parameter; 임의로 정할 수 있으면 고정형과 감쇄형이 있다.

# grad : (del연산자), 즉 gradient를 의미한다.

 

 

이제 위 식을 이용하여 gradient descent function을 구현해보자. 코드는 다음과 같다.

from autograd import grad 
import autograd.numpy as np 

# gradient descent function 
def gradient_descent(g,alpha,max_its,w,x,y):
    # g : 사용하고자 하는 cost function
    # alpha : steplength
    # max_its : iteration 횟수
    # w : 구하고자 하는 weight vector
    # x : input data, y : output data(정답)
    # compute gradient module using autograd
    gradient = grad(g) # get the differentiated function of g

    # run the gradient descent loop
    weight_history = [w] # weight history container
    cost_history = [g(w,x,y)] # cost function history container
    for k in range(max_its):
        # evaluate the gradient
        grad_eval = gradient(w, x, y)

        # take gradient descent step
        w = w - alpha*grad_eval
        
        # record weight and cost
        weight_history.append(w)
        cost_history.append(g(w, x, y))
    return weight_history,cost_history

 

다음과 같은 cost function이 있다고 하자.

# 함수정의
def cost(w):
    return w[0]**2. + w[1]**2. + 2.*np.sin((1.5*(w[0] + w[1]))**2.) + 2.
 
# run gradient descent to minimize g(w)
np.random.seed(28)
g = cost
w0 = 0.1*np.random.randn(2,1)
max_its = 1000
alpha_choice = 10**(-2)
w_history, cost_history = gradient_descent(g,alpha_choice,max_its,w0)

임의의 w를 랜덤으로 생성하고 iteration의 횟수와 알파를 임의로 정한다.

이를 통해 앞서 정의한 gradient descent function에 적용시킨다.

 

구한 값으로 cost function과 w value의 history plot을 그리면 다음과 같다.

# w 값이 랜덤으로 변하기 떄문에 매번 다른 그림이 나올 것이다.

 

초반의 몇 번의 반복을 제외하면 cost function과 w1, w2 value의 변화가 매우 미미한 것을 알 수 있다. 이는 gradient algorithm의 큰 단점 중 하나다. 이로 인해 최솟값 근처에서 매우 오랜 시간이 걸린다. 이를 해결하는 방안 중 하나는 alpha / | alpha | 로 다음 step으로의 방향만 정하고 alpha의 값을 임의로 변화시켜 주는 것이 있다.