2. 경사하강법 (Gradient Descent)

회귀계수의 개수가 적으면, 고차원 방정식으로 비용함수가 최소가 되는 계수를 탐색할 순 있지만, 

회귀계수의 개수가 많으면 고차원 방정식을 동원하더라도 풀기 어려운 문제가 존재한다.

 

비용함수 (cost function)
: 실제값과 예측값 사이 오차를 나타내는 것으로 오차제곱의 평균인 Mean Squared Error(MSE), 절대오차의 평균인 Mean Absolute Error(MAE) 등 다양하게 존재한다. 비용함수의 값이 작을수록, 가설함수가 실제함수와 유사하다는 것을 의미한다.

주어진 데이터 $(x_{1}, y_{1}), \cdots , (x_{m}, y_{m})$에 대해, $y$는 실제값, $h(x) = ax+b$는 가설함수라 할 때, 비용함수 ($cost(a, b)$)는 다음과 같이 정의할 수 있다. 

- Mean Squared Error(MSE)
$cost(a, b) = \frac{1}{m}\sum^{m}_{i=1}(h(x_{i}) - y_{i})^{2}$

- Mean Absolute Error(MAE)
$cost(a,b) = \frac{1}{m}\sum^{m}_{i=1}|h(x_{i}) - y_{i}|$

 

 

경사하강법(점진적으로 하강)은 데이터에 존재하는 알고리즘을 스스로 학습하여 최적의 회귀계수 값을 탐색하는 알고리즘 방법이다. 이번 포스트에서는 경사하강법에 대해서 알아보고, 실제 데이터에서 선형회귀와 경사하강법의 결과를 비교해보고자 한다.

 

0. 기본 개념

1. 경사하강법

2. 기울기와 학습률

3. 경사하강법 단점

4. 예제

---

0. 기본 개념

 

경사하강법은 점진적으로 하강한다는 말 그대로 "점진적으로 최적 회귀계수에 다가간다"고 이해하면 된다.

 

예를 들어, 야구공을 던지게 되면, 야구공의 속도는 처음에는 증가하다가 점차 감소하면서 땅에 떨어지게 될 것이다.

이처럼, 경사하강법은 처음에는 빠르게 최적값에 가까워지다가 어느정도 최적값과 비슷해지면 점차 속도가 감소한다. 

 

아래 그림은 경사하강법을 통해 최적 회귀계수를 탐색하는 과정으로 초기 회귀계수 추정값이 빠르게 감소하다가 $\hat{\theta}$에 가까워지면서 움직이는 보폭의 크기가 작아짐을 볼 수 있다. 

 

경사하강법 예시

 

비용함수가 이차함수라고 가정했을 때, 비용함수의 최저점은 비용함수의 미분값인 1차 함수의 기울기가 가장 최소일 때임을 알 수 있다. 경사하강법은 이러한 1차 함수의 기울기를 이용한다!

 

즉, 기울기가 감소하는 방향으로 이동하다 더이상 기울기가 감소하지 않는 지점(비용함수가 최소인 지점)을 찾아낸다

---

1. 경사하강법

 

비용함수는 $MSE(w) = \frac{1}{N}\sum^{N}_{i=1}(y_{i} - (w_{0} + w_{1} \times x_{i}))^{2}$라 하자.

이때, 비용함수가 최소가 되는 $w_{0}, w_{1}$을 찾아 최종 가설 함수 $w_{0} + w_{1} \times x_{i}$를 찾는 것이 목적이다.

경사하강법을 적용하기 위해서, $MSE(w)$에 대한 미분 함수를 계산해야한다. 

 

- $\frac{\delta MSE(w)}{\delta w_{0}} = -\frac{2}{N}\sum_{i=1}^{N} (y_{i} - (w_{0} + w_{1} \times x_{i}))$

 

- $\frac{\delta MSE(w)}{\delta w_{1}} = -\frac{2}{N}\sum_{i=1}^{N} x_{i} \times (y_{i} - (w_{0} + w_{1} \times x_{i}))$

 

이 미분값을 이용하여 $w_{0}, w_{1}$을 업데이트하며, 이때 구한 미분 함수 값에 (-)를 적용하여 계산한다.

편미분 값이 매우 클 수 있으므로 이를 조정하기 위해 학습률($\alpha$)를 곱해준다.

 

- $new$ $w{0} = w_{0} - \alpha\frac{\delta MSE(w)}{\delta w_{0}} = w_{0} + \alpha\frac{2}{N}\sum_{i=1}^{N}(y_{i} - (w_{0} + w_{1} \times x_{i}))$

 

- $new$ $w{1} = w_{1} - \alpha\frac{\delta MSE(w)}{\delta w_{1}} = w_{1} + \alpha\frac{2}{N}\sum_{i=1}^{N} x_{i} \times (y_{i} - (w_{0} + w_{1} \times x_{i}))$

 

이를 반복하면서, 더이상 비용함수 값이 감소하지 않으면, 업데이트를 종료한다. 

 

경사하강법

step1. 초기 매개변수 값을 임의로 지정한다.

step2. 미분 함수를 이용하여 매개변수를 업데이트한다.

step3. 비용함수의 값이 감소하면 step2를 반복하며, 더이상 감소하지 않으면 종료한다.

---

2. 기울기와 학습률

경사하강법에서 기울기의 부호는 각 매개변수가 움직이는 방향을 지정해주며, 움직이는 보폭의 크기는 학습률 $\alpha$를 통해 조정한다. 

 

- 기울기 부호

# 1. $\hat{\theta}$보다 좌측에서 시작하는 경우

초기 매개변수 $\theta$에 대한 기울기 부호는 음수이므로 (-)를 곱해 업데이트하면 $\theta$는 증가한다.

시작점이 최솟값보다 작은 경우

#2. $\hat{\theta}$보다 우측에서 시작하는 경우

초기 매개변수 $\theta$에 대한 기울기 부호는 양수이므로 (-)를 곱해 업데이트하면 $\theta$는 감소한다. 

시작점이 최솟값보다 큰 경우

 

- 학습률 $\alpha$

비용함수가 $\frac{cos(3 \pi x)}{x}$로 주어졌을 때, 학습률에 따라 어떻게 변화하는지 알아보고자 한다. 모두 초기값 0.15에서 시작하였다.

학습률이 0.0001, 0.0005일 때 경사하강법

학습률이 0.0001일 때보다 0.0005인 경우 눈에 띄게 최솟값에 빠르게 도달함을 볼 수 있다. 이처럼 학습률이 너무 작으면 최솟값에 도달하는데 많은 시간이 소요됨을 볼 수 있다. 

학습률이 0.015, 0.0005일 때 경사하강법

학습률이 0.015로 이전보다 매우 커지면, 우리가 찾고자 하는 최솟값을 벗어나서 다른 local minima에 빠짐을 볼 수 있다.

 

따라서, 데이터에 따라 적절한 학습률을 설정하는 것이 중요하며, 일반적으로 학습률은 0.01로 설정한다.

---

위 그림 예제는 아래 코드를 이용하여 생성하였다.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

''' 경사하강법 '''
# 비용함수
def cost(x):
    return np.cos(3*np.pi*x)/x

# 비용함수 미분
def diff_cost(x):
    return -(3*np.pi*x*np.sin(3*np.pi*x)+np.cos(3*np.pi*x))/x**2

x = np.arange(0.1, 1.1, 0.01)

# 초기 설정 (시작점, 학습률)
prev_x, alpha = 0.15, 0.0005

iteration = 0
prev_x_info = []
while True:
    
    iteration += 1
    update_x = prev_x - alpha * diff_cost(prev_x)    
    
    # 업데이트 이전, 이후 비용함수
    prev_cost, update_cost = cost(prev_x), cost(update_x)
    prev_x_info.append(prev_x)
    
    # 비용함수 차이가 매우 작은 경우 종료
    if abs(prev_cost - update_cost) < 1e-16:
        break

    else:
        prev_x = update_x


''' 그래프 '''
fig, ax = plt.subplots()

# 비용함수 그래프
ax.plot(x, cost(x), color = "black", zorder = 1)

x, y = [], []
line, = plt.plot([], [], 'bo')

def update(frame):
    x.append(frame)
    y.append(cost(frame))
    line.set_data(x, y)
    return line,

# 점 찍기
ani = FuncAnimation(fig, update, frames=prev_x_info)

plt.title("alpha: %s, iteration: %d"%(alpha, iteration))
plt.xlabel(r'$\theta$')
plt.ylabel("cost")
plt.show()

---

3. 경사하강법 단점

경사하강법은 가장 기본적이면서 쉬운 알고리즘이지만, 기울기를 계산할 때, 전체 데이터를 모두 사용하여 기울기를 계산한다. 따라서, 데이터의 크기가 커지면 훈련 속도가 느려진다. 또한, 시작점에 따라 최솟값이 달라질 수 있다. 

 

아래 그림은 시작점을 다르게 줬을 때, 경사하강법을 통해 찾은 최솟값을 나타낸다.

시작점이 다를 때, 경사하강법 결과

왼쪽 그림은 global minima를 찾아냈지만, 오른쪽 그림은 시작점으로부터 기울기가 감소하는 방향으로 도달하다보니 local minima에 빠졌음을 볼 수 있다. 따라서, 경사하강법에서는 초기값을 어떻게 주느냐에 따라 결과가 달라질 수 있다는 문제가 존재한다.

경사하강법 문제점

1. 데이터의 크기가 커지면 훈련 속도가 느려짐
2. 시작점에 따라 최솟값이 달라질 수 있음 (local minima에 빠질 위험이 존재함)

 

이를 해결하기 위해, mini-batch 경사하강법, stochastic 경사하강법이 등장하였다. 

---

4. 예제

sklearn의 LinearRegression의 결과와 경사하강법의 결과가 동일한지 알아보기 위해, 간단한 예제를 이용하여 살펴보고자 한다. 아래 그림은 $-2x + 5$ 주변으로 생성된 점들을 나타낸다. 이때, 실제 함수 식과 근접한 결과를 내는지 알아보고자 한다.

예제

실제 함수 식: $-2x + 5$

	Sklearn LinearRegression	Gradient Descent (iter: 291)
예측 회귀식	$\hat{y} = -1.910995x + 4.905573$	$\hat{y} = -1.910996x + 4.905538$

 

회귀 결과, Sklearn Linear Regression과 Gradient Descent 둘다 비슷한 결과를 보이고 있다. 또한, 실제 함수 식과 매우 근접하였음을 볼 수 있다.

---

from sklearn.linear_model import LinearRegression
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

x = np.random.uniform(-2, 2, 150).reshape(-1,1)
y = np.array([-2 * xx + 5 + np.random.normal() for xx in x]).reshape(-1,)


'''
Sklearn LinearRegression
'''

lr = LinearRegression().fit(x, y) 
lr_ypred = lr.predict(x)

print("LinearRegression")
print("pred_fuc: %.6f * x + %.6f"%(lr.coef_, lr.intercept_))


'''
Gradient Descent
'''

# 가설함수
def hx_fuc(a, b):
    return (a*x+b).reshape(-1, )

# 비용함수
def cost(h_x):
    return 1/len(y)*np.sum((y-h_x)**2)

# 비용함수 a에 대한 편미분
def diff_coef(h_x):
    x_sh = x.reshape(-1, )
    return -2/len(y)*np.sum((y-h_x) * x_sh)

# 비용함수 b에 대한 편미분
def diff_intercept(h_x):
    return -2/len(y)*np.sum((y-h_x))

# 초기설정(시작점, 학습률)
prev_a, prev_b = 0, 0
prev_hx = hx_fuc(prev_a, prev_b) # 초기 가설함수

alpha = 0.02

iteration = 0
prev_a_info, prev_b_info = [], []
while True:
    
    iteration += 1
    
    # 이전 변수를 이용해 업데이트
    update_a, update_b = prev_a - alpha*diff_coef(prev_hx), prev_b - alpha*diff_intercept(prev_hx)
    update_hx = hx_fuc(update_a, update_b)
    
    # 업데이트 이전, 이후 비용함수
    prev_cost, update_cost = cost(prev_hx), cost(update_hx)
    
    prev_a_info.append(prev_a)
    prev_b_info.append(prev_b)
    
    # 비용함수 차이가 매우 작은 경우 종료
    if abs(prev_cost - update_cost) < 1e-10:
        break

    else:
        prev_a, prev_b = update_a, update_b
        prev_hx = hx_fuc(prev_a, prev_b)

print()
print("Gradient Descent")
print("iter:", iteration)
print("pred_fuc: %.6f * x + %.6f"%(prev_a, prev_b))


'''
그래프
'''

fig_x = np.linspace(min(x), max(x), 10000)

# Gradient Descent를 통해 얻은 예측값 저장 (iteration마다)
pred_value = np.array([a * fig_x + b for a, b in zip(prev_a_info, prev_b_info)])

fig, ax = plt.subplots()
ax.scatter(x.reshape(-1, ), y, color = "black", s = 15)
ax.plot(fig_x, lr.predict(fig_x.reshape(-1, 1)), color = "red", label = "Sklearn LR func")

line, = ax.plot([], [], color = "blue", label = "GD predict func")

def update(iter):
    ax.set_title("iteration: %s"%iter)
    y = prev_a_info[iter] * fig_x + prev_b_info[iter]
    line.set_data(fig_x, y)
    return line, ax
plt.legend(loc = "upper right")
plt.xlabel("x")
plt.ylabel("y")
ani = FuncAnimation(fig, update, frames= iteration - 1, interval=10, blit=False)

---

오늘은 경사하강법에 대해 알아보고, 예제를 통해 구현해보았다. 실제로는 예제와 같은 단순한 형태가 아닌 복잡한 데이터에 대한 선형회귀결과를 구해야 할 때가 많다. 따라서, 다음 포스트는 실제 데이터에 대해서 경사하강법을 적용해보고자 한다.