경사하강법

핵심 주제

  1. 경사하강법 의미
  2. 그레이디언트 계산
  3. 경사하강법과 선형회귀
  4. 미니배치/확률적 경사하강법

필수 모듈 불러오기

이전에 정의한 함수를 사용하기 위한 준비가 필요하며, 이전에 사용한 모든 파이썬 코드가 ../scratch/ 디렉토리에 저장되어 있다고 가정한다.

여기서는 선형대수 모듈에 포함되어 있는 Vector 자료형과 dot (벡터곱)함수를 불러온다.

핵심 1: 경사하강법 의미

주어진 데이터셋을 가장 잘 반영하는 최적의 수학적 모델을 찾으려 할 때 가장 기본적으로 사용되는 기법이 경사하강법(gradient descent)이다. 최적의 모델에 대한 기준은 학습법에 따라 다르지만, 보통 학습된 모델의 오류를 최소화하도록 유도하는 기준을 사용한다.

여기서는 선형회귀 모델을 학습하는 데에 기본적으로 사용되는 평균 제곱 오차(mean squared error, MSE)를 최소화하기 위해 경사하강법을 적용하는 과정을 살펴본다.

경사하강법 기본 아이디어

함수 $f:\textbf{R}^n \to \textbf{R}$의 최댓값(최솟값)을 구하고자 한다. 예를 들어, 길이가 $n$인 실수 벡터를 입력받아 항목들의 제곱의 합을 계산하는 함수가 다음과 같다고 하자.

$$ f(\mathbf x) = f(x_1, ..., x_n) = \sum_{k=1}^{n} x_k^2 = x_1^2 + \cdots x_n^2 $$

아래 코드에서 정의된 sum_of_squares()가 위 함수를 파이썬으로 구현한다.

이제 sum_of_squares(v)가 최대 또는 최소가 되는 벡터 v를 찾고자 한다.

그런데 특정 함수의 최댓값(최솟값)이 존재한다는 것이 알려졌다 하더라도 실제로 최댓값(최솟값) 지점을 확인하는 일은 일반적으로 매우 어렵고, 경우에 따라 불가능하다. 따라서 보통 해당 함수의 그래프 위에 존재하는 임의의 점에서 시작한 후 그레이디언트를 방향(반대 방향)으로 조금씩 이동하면서 최댓값(최솟값) 지점을 찾아가는 경사하강법(gradient descent)을 이용한다.

그레이디언트의 정의와 의미

함수 $f:\textbf{R}^n \to \textbf{R}$가 vector $\textbf{x}\in \textbf{R}$에서 미분 가능할 때 그레이디언트는 다음처럼 편미분으로 이루어진 벡터로 정의된다.

$$ \nabla f(\textbf{x}) = \begin{bmatrix} \frac{\partial}{\partial x_1} f(\textbf{x}) \\ \vdots \\ \frac{\partial}{\partial x_n} f(\textbf{x}) \end{bmatrix} $$

아래에서 왼편 그림은 $n=1$인 경우 2차원 상에서, 오른편 그림은 $n=2$인 경우에 3차원 상에서 그려지는 함수의 그래프와 특정 지점에서의 그레이디언트를 보여주고 있다.

경사하강법 경사하강법
<출처 > 위키:미분 <출처 > pvigier: gradient-descent

경사하강법 작동 방식

경사하강법은 다음 과정을 반복하여 최댓값(최솟값) 지점을 찾아가는 것을 의미한다.

아래 그림은 2차원 함수의 최솟값을 경사하강법으로 찾아가는 과정을 보여준다. 최솟값은 해당 지점에서 구한 그레이디언트의 반대방향으로 조금씩 이동하는 방식으로 이루어진다.

최솟값 지점에 가까워질 수록 그레이디언트는 점점 0벡터에 가까워진다. 따라서 그레이디언트가 충분히 작아지면 최솟값 지점에 매우 가깞다고 판단하여 그 위치에서 최솟값의 근사치를 구하여 활용할 수 있다.

경사하강법 <출처 > <a href=""https://github.com/pvigier/gradient-descent>pvigier: gradient-descent </a>

주의사항

경사하강법은 지역 최솟값(local minimum)이 없고 전역 최솟값(global mininum)이 존재할 경우 유용하게 활용된다. 반면에 지역 최솟값이 존재할 경우 제대로 작동하지 않을 수 있기 때문에 많은 주의를 요한다. 아래 그림은 출발점과 이동 방향에 따라 도착 지점이 전역 또는 지역 최솟점이 될 수 있음을 잘 보여준다.

경사하강법 <출처 > 위키:미분

핵심 2: 그레이디언트 계산

단변수 함수와 다변수 함수의 경우 그레이디언트 계산이 조금 다르다.

단변수 함수의 도함수 계산

$f$가 단변수 함수(1차원 함수)일 때, 점 $x$에서의 그레이디언트는 다음과 같이 구한다.

$$ f'(x) = \lim_h \frac{f(x+h) - f(x)}{h} $$

즉, $f'(x)$ 는 $x$가 아주 조금 변할 때 $f(x)$가 변하는 정도, 즉 함수 $f$의 $x$에서의 미분값이 된다. 이때 함수 $f'$ 을 함수 $f$의 도함수라 부른다.

예를 들어, 제곱 함수 $f(x) = x^2$에 해당하는 square()가 아래와 같이 주어졌다고 하자.

그러면 square()의 도함수 $f'(x) = 2x$는 다음과 같다.

이와 같이 미분함수가 구체적으로 주어지는 경우는 많지 않다. 따라서 여기서는 많은 경우 충분히 작은 $h$에 대한 함수의 변화율을 측정하면 미분값의 근사치를 사용할 수 있다는 사실을 확인하고자 한다.

아래 그림은 $h$가 작아질 때 두 점 $f(x+h)$ 와 $f(x)$ 지나는 직선이 변하는 과정을 보여준다. $h$가 0에 수렴하면 최종적으로 점 $x$에서의 접선이 되고 미분값 $f'(x)$는 접선의 기울기가 된다.

경사하강법 <출처 > 위키:미분

아래 코드는 임의의 단변수 함수에 대해 함수 변화율을 구해주는 함수를 간단하게 구현한 것이다.

아래 코드는 square()의 도함수 derivative() 를 difference_quotient()를 이용하여 충분히 근사적으로 구현할 수 있음을 그래프로 보여준다. 근사치 계산을 위해 h=0.001 를 사용한다.

다변수 함수의 그레이디언트 계산

다변수 함수의 그레이디언트는 매개변수 각가에 대한 편도함수(partial derivative)로 구성된 벡터로 구성된다. 예를 들어, $i$번째 편도함수는 $i$번째 매개변수를 제외한 다른 모든 매개변수를 고정하는 방식으로 계산된다.

$f$가 다변수 함수(다차원 함수)일 때, 점 $\mathbf{x}$에서의 $i$번째 도함수는 다음과 같다.

$$ \frac{\partial}{\partial x_i}f(\mathbf x) = \lim_h \frac{f(\mathbf{x}_h) - f(\mathbf x)}{h} $$

여기서 $\mathbf{x}_h$는 $\mathbf x$의 $i$번째 항목에 $h$를 더한 벡터를 가리킨다. 즉, $\frac{\partial}{\partial x_i} f(\mathbf x)$ 는 $x_i$가 아주 조금 변할 때 $f(\mathbf x)$가 변하는 정도, 즉 함수 $f$의 $x$에서의 $i$번째 편미분값이 된다. 이때 함수 $\frac{\partial}{\partial x_i}f$ 를 함수 $f$의 $i$번째 편도함수라 부른다.

아래 코드에서 정의된 partial_difference_quotient는 주어진 다변수 함수의 $i$번째 편도함수의 근사치를 계산해주는 함수이다. 사용되는 매개변수는 difference_quotient() 함수의 경우와 거의 같다. 다만 i번째 편도함수의 근사치를 지정하기 위해 i번째 매개변수에만 h가 더해짐에 주의하라.

다음 estimate_gradient() 함수는 편미분 근사치를 이용하여 그레이디언트의 근사치에 해당하는 벡터를 리스트로 계산한다. 근사치 계산에 사용된 h의 기본값은 0.0001이다.

주의사항

그레이디언트를 두 개의 함수값의 차이를 이용하여 근사치로 계산하는 방식은 계산 비용이 크다. 벡터 v의 길이가 $n$이면 estimate_gradient() 함수를 호출할 때마다 f를 $2n$ 번 호출해야 하기 때문이다. 따라서 앞으로는 그레이디언트 함수가 수학적으로 쉽게 계산되는 경우만을 사용하여 경사하강법의 용도를 살펴볼 것이다.

핵심 3: 경사하강법과 선형회귀

앞서 정의한 제곱함수 sum_of_squares() 는 v가 0 벡터일 때 가장 작은 값을 갖는다. 이 사실을 경사하강법을 이용하여 확인해보자.

먼저, sum_of_squares() 함수의 그레이디언트는 다음과 같이 정의된다.

$$ \nabla f(\textbf{x}) = \begin{bmatrix} \frac{\partial}{\partial x_1} f(\textbf{x}) \\ \frac{\partial}{\partial x_2} f(\textbf{x}) \end{bmatrix} $$

아래 코드는 리스트를 이용하여 그레이디언트를 구현하였다.

아래 코드는 임의의 지점(v)에서 계산된 그레이디언트에 스텝(step)이라는 특정 상수를 곱한 값을 더해 새로운 지점을 계산하는 함수를 구현한다.

이제 임의의 지점에서 출발하여 gradient_step을 충분히 반복하면 제곱함수의 최솟점에 충분히 가깝게 근사할 수 있음을 아래 코드가 보여준다. 실제로 1.0e-07보다 작다.

에포크와 스텝 크기

앞서 사용된 코드에서 에포크(epoch)는 이동 횟수를 가리키며, 에포크를 크게 하면 최솟값 지점에 보다 가까워진다. 하지만 항상 수렴하는 방향으로 이동하는 것은 아니다. 하지만 여기서는 스텝 크기를 너무 크게 지정하지만 않으면 항상 최솟값에 수렴하는 볼록함수만 다룬다. 스텝 크기에 따른 수렴속도는 다음과 같다.

하지만 다루는 함수에 따른 적당한 스텝의 크기가 달라지며, 보통 여러 실혐을 통해 정해야 한다.

선형회귀

경사하강법을 이용하여 주어진 데이터들의 분포에 대한 선형 모델을 구하는 방법을 선형회귀(linear regression)라 부른다.

먼저 $y = f(x) = 20*x + 5$ 일차함수의 그래프에 해당하는 데이터를 구한다. 여기서 $x$는 -0.5에서 0.5 사이에 있는 100개의 값으로 주어지며, $y$값에 약간의 잡음(가우시안 잡음)이 추가된다.

아래 프로그램은 잡음이 포함되어 직선으로 그려지지 않는 데이터의 분포를 보여준다.

이제 위 그래프를 선형적으로 묘사하는 함수를 경사하강법을 이용하여 구현한다. 구현 대상은 아래 모양의 함수이다.

$$ \hat y = f(x) = \theta_0 x + \theta_1 $$

목표

위 그래프를 가장 잘 묘사하는 직선을 구해야 한다. 즉, 적절한 $\theta_0$와 $\theta_1$을 구해야 한다.

기준

경사하강법을 적용하려면 최소화 대상함수를 정해야 한다. 여기서는 예측치 $\hat y$와 실제 $y$ 사이의 오차의 평균제곱오차(mean squared error, MSE)를 계산하는 함수를 사용한다.

$$ \textrm{MSE}(\theta_0, \theta_1) = \sum_{y \in ys} (\hat y - y)^2 = \sum_{x \in \textrm{xs}} (\theta_0 x + \theta_1 - y)^2 $$

즉, MSE를 최소로 하는 $\theta_0, \theta_1$을 구해야 한다. MSE의 그레이디언트는 다음과 같다.

$$ \frac{\partial}{\partial \theta_0} \textrm{MSE}(\theta_0, \theta_1) = \sum_{x \in \textrm{xs}} 2(\hat y - y) x\, , \qquad \frac{\partial}{\partial \theta_1} \textrm{MSE}(\theta_0, \theta_1) = \sum_{x \in \textrm{xs}} 2(\hat y - y) $$

아래 코드는 특정 x에 대한 실제 값 y와 예측치 $\hat y$ 사이의 제곱오차와 제곱오차의 그레이디언트를 계산한다.

이제 임의의 $\theta = (\theta_0, \theta_1)$로 시작한 후에 경사하강법으로 평균제곱오차의 최솟값 지점을 구할 수 있다.

아래 코드에서 사용한 학습률은 0.001이다.

그런데 최종 기울기가 11.398로 애초에 사용한 20과 차이가 크다. 이유는 학습률이 너무 낮아서 5000번의 에포크가 충북한 학습을 위해 부족했기 때문이다. 이에 대한 해결책은 보통 두 가지이다.

아래 코드는 먼저 에포크를 네 배 늘린 결과를 보여준다.

반면에 아래 코드는 학습률을 0.01로 키웠다.

위 결과를 비교했을 때 학습률을 키우는 것이 보다 효과적이다. 최종적으로 구해진 기울기와 절편을 이용하여 처음에 주어진 데이터의 분포를 선형적으로 학습한 1차함수의 그래프는 다음과 같다.

핵심 4: 미니배치/확률적 경사하강법

앞서 사용한 경사하강법은 주어진 데이터셋 전체를 대상으로 평균제곱오차와 그레이디언트를 계산하였다. 이런 방식을 배치 경사하강법이라 부른다.

주의: 배치(batch)는 원래 하나의 묶음을 나타내지만 여기서는 주어진 (훈련) 데이터셋 전체를 가리키는 의미로 사용된다.

그런데 사용된 데이터셋의 크기가 100이었기 때문에 계산이 별로 오래 걸리지 않았지만, 데이터셋이 커지면 그러한 계산이 매우 오래 걸릴 수 있다. 실전에서 사용되는 데이터셋의 크기는 몇 만에서 수십억까지 다양하며, 그런 경우에 적절한 학습률을 찾는 과정이 매우 오래 걸릴 수 있다.

데이터셋이 매우 큰 경우에는 따라서 아래 두 가지 방식을 추천한다.

미니배치 경사하강법

배치 경사하강법과는 달리 미니매치 경사하강법(mini-batch gradient descent)은 일정 크기의 훈련 데이터를 대상으로 그레이디언트를 계산한다.

예를 들어, 전체 데이터셋의 크기가 1000이고 미니배치의 크기를 10이라 하면, 배치 경사하강법에서는 하나의 에포크를 돌 때마다 한 번 MSE와 그레이디언트를 계산하였지만 미니배치 경사하강법에서는 10개의 데이터를 확인할 때마다 MSE와 그레이디언트를 계산하여 하나의 에포크를 돌 때마다 총 100번 기울기와 절편을 업데이트한다.

아래 코드에서 정의된 minibatches() 함수는 호출될 때마다 batch_size로 지정된 크기의 데이터 세트를 전체 데이터셋에서 선택해서 내준다.

데이터를 선택하는 방식은 다음과 같다.

이제 미니배치 경사하강법을 이전에 사용했던 데이터에 대해 적용한다. 학습률(learning_rate)을 0.001로 하면 학습이 제대로 이루어지지 않는다. 에포크 수를 키우거나 합습률을 크게 해야 한다.

학습률을 0.01로 키우면 좋은 결과가 나온다.

학습률을 0.01로 두고 에포크를 3000으로 늘려도 성능이 그렇게 좋아지지 않는다.

학습 과정을 살펴보면 기울기가 19.966 정도에서 더 이상 좋아지지 않는다. 이런 경우 특별히 더 좋은 결과를 얻을 수 없다는 것을 의미한다. 사실, 데이터셋을 지정할 때 가우시안 잡음을 추가하였기에 완벽한 선형함수를 찾는 것은 애초부터 불가능하다. 따라서 위 결과를 미니배치 경사하강법을 사용한 선형회귀로 얻을 수 있는 최선으로 볼 수 있다.

확률적 경사하강법

확률적 경사하강법(stochastic gradient descent, SGD)은 미니배치의 크기가 1인 미니배치 경사하강법을 가리킨다. 즉, 하나의 데이터를 학습할 때마다 그레이디언트를 계산하여 기울기와 절편을 업데이트 한다.

아래 코드는 주어진 데이터셋을 대상로 SGD를 적용하는 방식을 보여준다. 학습률을 0.001로 했음에도 불구하여 1000번의 에포크를 반복한 후에 이전에 0.01을 사용했던 경우와 거의 동일한 결과를 얻는다는 것을 확인할 수 있다.

학습률을 0.01로 하면 오히려 결과가 나빠진다.

경사하강법 비교

앞서 살펴본 것에 따르면 확률적 경사하강법의 성능이 가장 좋았다. 하지만 이것은 경우에 따라 다르다. 배치 경사하강법, 미니배치 경사하강법, 확률적 경사하강법 각각의 장단점이 있지만 여기서는 더 이상 자세히 다루지 않는다.