[AI Math] 2. 경사하강법

경사하강법(Gradient Descent, GD)

• 경사하강법은 딥러닝에서 사용되는 최적화 방법이다. 이러한 경사하강법을 이해하기 위해서는 미분을 이해해야 한다.

미분

• 미분(differentiation)은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구로 최적화에서 제일 많이 사용하는 기법이다.

  \[f'(x) = \displaystyle\lim_{h \to0} \frac{f(x+h) - f(x)}{h}\]
• 위 수식에서 보듯, 미분은 변화율의 극한(limit)으로 정의한다.
• 주어진 한 점 $x$의 함수값과 $h$ 만큼 이동한 $x+h$ 에서의 함수값의 차이를 움직인 거리 $h$ 로 나눈 값을 기울기라고 부른다. 이 기울기를 변화율이라 부르는데, 이 변화율의 극한을 미분으로 정의한다.

• 아래는 2차 방정식에 대한 미분이다.

  \[\begin{aligned} f(x) &= x^2 + 2x + 3 \\ f'(x) &= 2x + 2 \end{aligned}\]

• 최근에는 미분을 손으로 직접 계산하는 대신 컴퓨터가 계산해줄 수 있다.

    import sympy as sym
    from sympy.abc import x
      
    sym.diff(sym.poly(x**2 + 2*x + 3), x)
    # 출력 Poly(2*x + 2, x, domain='ZZ')
  

• sympy 라이브러리를 이용하면 어떤 함수를 symbolic 하게 기호로 이해할 수 있다. poly 는 다항함수를 뜻한다.
• 이를 활용하면 아주 다양한 함수의 미분을 계산할 때 컴퓨터로 계산해서 검증할 수 있다. 따라서 딥러닝에서는 사람이 일일이 미분을 계산하지 않고 컴퓨터로 계산해서 최적화에 사용한다.

• 그러나 미분의 개념은 이해하고 있어야 한다. 미분은 함수 $f$ 의 주어진 점 $(x, f(x))$ 에서의 접선의 기울기를 구한다. 즉 주어진 점에서의 접선의 기울기를 계산하는 것이 미분이다.

  

• 함수 $f$ 가 미분이 가능하려면 매끄럽게 연속이어야 한다.
• 이 때 $h$ 를 0으로 보내면 $x$ 에서의 접선의 기울기로 수렴하게 된다. 그것이 $f’(x)$ 가 된다.
• 한 점에서의 접선의 기울기를 알면 어느 방향으로 점을 움직여야 함수값이 증가하는지 또는 감소하는지 알 수 있다.
• 차원이 높아질수록 어느 방향으로 가야 함수값을 증가/감소시킬지 아는 것은 불가능하다. 머릿속에 높은 차원을 떠올릴 수 없기 때문이다. 이 때 미분을 사용하면 어느 방향으로 움직여야 함수값이 증가/감소하는지를 알 수 있다. 이를 이용해서 함수를 최적화를 한다.

• 함수값을 증가시키고 싶다면 $x$ 에 미분값을 더하고 감소시키고 싶다면 $x$ 에 미분값을 뺀다.

  

• 위 그림에서 접선의 기울기는 음수이기 때문에 미분값이 음수다. 미분값을 더해주면 음수를 더해주는 것이기 때문에 뺄셈이 된다. 따라서 미분값을 더해주면 왼쪽으로 이동하여 함수값이 증가한다. 위 그림에서 보면 미분값이 음수라서 $x + f’(x) < x$ 는 왼쪽으로 이동하여 함수값이 증가한다.

• 이처럼 $x$ 에 미분값을 더해주게 되면 미분값의 양/음과 관계없이 함수값이 증가하게 된다.

  

• 미분값(기울기)이 양수라면 $x + f’(x) > x$ 는 오른쪽으로 이동하여 함수값이 증가한다.

• 반대로 함수값을 감소시키고 싶다면 미분값의 양/음에 관계없이 $x$ 에 미분값을 빼주면 된다. 미분값이 음수라면 $x - f’(x) > x$ 는 $x$ 값이 오른쪽으로 이동하여 함수값이 감소하게 된다.

  

• 따라서 함수를 증가시키고 싶으면 미분값을 더해주고, 함수를 감소시키고 싶으면 미분값을 빼주면 된다! 즉 미분값을 더해주면 함수를 최대화시킬 수 있고, 미분값을 빼주면 함수를 최소화시킬 수 있다.

• 이렇게 미분값을 더해줌으로써 함수값을 점차 극대화시키는 것을 경사상승법(gradient ascent)라고 한다. 즉 목적함수를 최대화할 때 사용한다.

  

• 미분값을 더해줌으로써 주어진 점에서 함수가 커지는 방향으로 점점 이동하는 것이다.

• 반대로 미분값을 빼줌으로써 함수값을 점차 극소화시키는 것을 경사하강법(gradient descent) 라고 한다. 즉 목적함수를 최소화할 때 사용한다.

  

• 주어진 점에서 근처의 극소값으로 향하는 것을 볼 수 있다.
• 정리하면, 주어진 함수를 최대화할 때는 경사상승법을 사용하고, 함수를 최소화하고 싶다면 경사하강법을 이용하게 된다.

• 또한 경사상승법이든 경사하강법이든 극값에 도달하면 움직임을 멈춘다. 극값에서는 미분값이 0 이므로 더 이상 미분값을 더하거나 빼더라도 0 이기 때문에 업데이트가 되지 않는다. 따라서 목적함수 최적화가 자동으로 끝난다.

  

경사하강법 알고리즘(1)

• 경사하강법 알고리즘을 이해하기 위해서는 미분을 계산하는 gradient 함수가 필요하다.
• 경사하강법, 경사상승법은 미분값이 0 이 되면 업데이트가 일어나지 않지만, 컴퓨터로 계산할 때 미분값이 정확히 0이 되는 것은 불가능하다.
• 따라서 알고리즘이 종료되기 위해서는 특정 종료조건 eps 를 설정해서, eps 보다 미분의 절대값이 작아지게 되면 알고리즘을 종료하는 조건을 설정해줄 수 있다.

• 경사하강법의 경우 미분값을 주어진 변수에 빼주게 된다.

    # input: gradient, init, lr, eps
    # output : var
    var = init # 시작점
    grad = gradient(var)
      
    while(abs(grad) > eps):
        var = var - lr * grad # 학습률 * 미분값
        grad = gradient(var)
  

• lr 은 학습률(learning rate) 로써, 경사하강법의 업데이트 속도를 조절하는 상수다. 논문이나 라이브러리에서 $\lambda$ 로 나타낸다.
• 이 학습률을 통해서 알고리즘을 더 빠르게 수렴시킬 수도 있고 좀 더 느리고 확실하게 수렴시킬 수도 있다. 즉 학습률을 통제함으로써 미분을 통한 경사하강법 업데이트의 속도를 조절할 수 있다.
• 주의할 점은 학습률의 경우 주의깊게 제어해야만 실제 경사하강법 알고리즘이 수렴하는데 중요하게 역할을 한다.
• 미분(gradient)을 통한 경사하강법을 통해서 var 을 업데이트해서 위치를 계속해서 이동시키게 된다. 미분값을 계속 빼주어 이동시키게 되는 경사하강법 알고리즘을 통해서 주어진 함수의 극값을 찾게 된다.

벡터의 경사하강법

• 지금까지 본 경사하강법은 변수가 하나인 경우, 즉 수직선 상에서 $x$ 가 미분 결과를 이용하여 두 방향으로만 움직였다.
• 만약 변수가 벡터나 행렬이라면 미분을 계산할 때 양/음으로 계산하기 어렵다. 벡터의 경우 $n$ 차원 공간에서 계산되는 한 점이기 때문에 이동을 할 때 많은 방향으로 이동할 수 있다. 이런 경우에는 특별한 방식의 미분을 사용한다.

• 벡터가 입력인 다변수 함수의 경우 편미분(partial differentiation) 을 이용한다.

  \[\partial_{x_i}f(\mathbf{x}) = \lim_{h \to 0} \frac{f(\mathbf{x} + h\mathbf{e}_i) - f(\mathbf{x})}{h}\]
• 편미분은 특정 방향의 좌표축으로 이동하는 형식으로 미분을 정의한다.
• 위 공식에서, $\mathbf{e}_i$ 는 $i$ 번째 값만 1 이고 나머지는 0 인 단위벡터다. 즉 $\mathbf{e}_i$ 는 주어진 벡터 $\mathbf{x}$ 가 있을 때 그 $\mathbf{x}$ 의 $i$ 번째 구성성분에만 영향을 주고 나머지는 변화를 주지 않는다.
• 이 단위벡터를 이용해서 특정 $\mathbf{x}$ 벡터의 $i$ 번째 구성성분만 변화율을 주는 것이다.
• 이런 방식으로 변화율을 구성해서 극한을 계산하면, $i$ 번째 방향에서의 변화율만 계산할 수 있다. 다시 말해서 $i$ 번째 변수에서만 변화율을 계산할 수 있기 때문에 변수가 벡터인 경우에도 편미분을 이용해서 경사하강법 알고리즘을 똑같이 사용해볼 수 있다.

• 구체적인 예시를 보자.

  \[\begin{aligned} f(x, y) &= x^2 + 2xy + 3 + \cos(x+2y) \\ \partial_x f(x, y) &= 2x + 2y - \sin(x+2y) \end{aligned}\]
• 만약 $x$ 방향으로서의 변화율만 편미분을 계산하면 위와 같이 된다. 이 때 $y$ 를 상수로 취급하고 $x$ 에 대해서 미분한 결과만 나온다.
• 즉, $y$ 변수는 변화시키지 않고 오로지 $x$ 변수만 변화시킴으로 편미분을 계산할 수 있고, 이 편미분은 $x$ 방향의 움직임만 분석하는 변화율이 된다.
• 당연히 $y$ 방향의 편미분도 계산할 수 있다. 따라서 편미분은 주어진 함수의 변수의 개수만큼 계산해볼 수 있다.

• 코드로도 똑같이 계산할 수 있다.

    import sympy as sym
    from sympy.abc import x, y
      
    sym.diff(sym.poly(x**2 + 2*x*y +3) + sym.cos(x + 2*y), x)
    # 출력 2*x + 2*y - sin(x + 2*y)
  

• 각 변수 별로 편미분을 계산한 그레디언트(gradient) 벡터를 이용하여 경사하강/경사상승법에 사용할 수 있다.

  \[\begin{aligned} \partial_{x_i}f(\mathbf{x}) &= \lim_{h \to 0} \frac{f(\mathbf{x} + h\mathbf{e}_i) - f(\mathbf{x})}{h} \\ \nabla{f} &= (\partial_{x_1}f, \partial_{x_2}f, \cdots, \partial_{x_d}f) \end{aligned}\]
• $d$ 차원 벡터를 입력으로 가지는 함수라면 편미분을 $d$ 개 만큼 계산할 수 있다. 각 변수 $d$ 개 만큼 편미분을 계산한 함수들을 벡터로 표현할 수 있다. 이 벡터를 그레디언트 벡터라고 부르게 된다. 각 그레디언트 벡터의 $i$ 번째 구성 성분은 위에서 정의한 편미분으로 정의를 하게 된다.
• 수식은 $\nabla$ 기호를 사용해서, 다변수를 입력으로 가지는 함수의 그레디언트 벡터를 표시하는 기호로 사용하게 된다.
• 앞서 사용한 미분값인 $f’(x)$ 대신 그레디언트 벡터 $\nabla f$ 를 사용하여 변수 $\mathbf{x} = (x_i, \cdots, x_d)$ 를 동시에 업데이트 가능하다.
• 즉, 수직선 상에서 $x$ 값을 업데이트 하는 것이 아니라 일반적인 $d$ 차원 공간에서 벡터에 적용되는 경사하강법을 사용하게 되는 것이다.

그레디언트 벡터

• 위 그림에서의 함수는 $x$ 와 $y$ 를 2변수로 받는 함수이고, 그 결과값이 $z$ 축으로 3차원 상에서 표현이 된 함수다.
• 이 함수를 가지고 그레디언트 벡터를 계산하면 오른쪽 그림과 된다.
• 이 때 $(x, y, z)$ 라는 3차원 공간 상에서 $f(x, y)$ 함수의 표면을 따라서 그레디언트 벡터에 - 를 붙이게 되면 오른쪽 그림과 같이 $f(x, y)$ 의 최소점, 정확히 말하면 극소점으로 향하는 화살표들의 움직임을 볼 수 있다.
• 이 $f(x, y)$ 의 어떤 점에서 출발하던지 간에, $-\nabla f$ 방향으로 따라가기만 하면 $f(x,y)$ 의 최소점으로 흐르게 되는 것이다.
• 등고선(contour)으로 이해해보자. $(0, 0)$ 을 중심으로 등고선이 그려질 수 있다.

• 그레디언트 벡터 $\nabla f(x, y)$ 는 각 점 $(x, y)$ 에서 가장 빨리 증가하는 방향으로 흐르게 된다.

  

• 즉, 원점에서 가장 빨리 증가하게 되는 방향으로 그레디언트 벡터를 표시하게 된다.

• 여기다가 - 를 붙힌 $-\nabla f$ 는 $\nabla (-f)$ 와 같고 이는 각 점에서 가장 빨리 감소하게 되는 방향과 같다.

  

• 즉 - 를 붙인 그레디언트 벡터를 표시하게 되면 임의의 점에서 출발을 해서 최소점인 $(0, 0)$ 으로 가장 빨리 감소하는 방향으로 움직이게 되는 것이다.
• 이처럼 그레디언트 벡터를 이용해서 주어진 함수의 극대점 또는 극소점으로 향하는 방향을 알 수 있게 된다.
• 따라서 3, 4, 또는 임의의 차원에서 그레디언트 벡터를 이용하게 되면 주어진 함수의 최소값이나 최대값을 구하는데 활용할 수 있고, 경사상승/경사하강법 알고리즘을 이용하면 최적화를 할 수 있게 된다.

경사하강법 알고리즘(2)

• 앞에서는 종료조건으로 미분값(gradient)의 절대값을 계산했지만 이제 gradient 는 벡터이기 때문에 절대값을 계산할 수는 없고 노름을 대신 계산해서 종료조건을 설정한다.

    var = init
    grad = gradient(var)
      
    while(norm(grad) > eps): # 노름으로 종료조건 설정
        var = var - lr * grad
        grad = gradient(var)
  

• 이렇게 정의된 경사하강법 알고리즘을 이용하면 어떤 함수의 최소값, 최대값을 구할 때 활용할 수 있다.즉 어떤 함수가 주어졌을 때 그 함수의 극소, 극대, 최소, 최대를 구하는데 활용할 수 있다.
• 딥러닝에서 가장 중요한 최적화 알고리즘이 이 경사하강법 알고리즘이다.

선형회귀분석

• $n$ 개 데이터가 주어진 상황에서 데이터를 가장 잘 표현하는 선형모델을 찾는 문제를 선형회귀분석이라 한다.
• 이 때 무어 펜로즈 역행렬을 이용해서 선형 모델의 해를 찾을 때 이용할 수 있었다.
• 무어 펜로즈 역행렬을 이용하면 주어진 데이터의 정답에 해당하는 $y$ 와 가장 근사적으로 가까운 선형모델을 찾을 수 있다. 즉, $L2$ 노름을 최소화하는 선형모델을 찾기 위해서 계수를 무어 펜로즈 역행렬로 찾을 수 있었다.
• 이제 무어 펜로즈 역행렬을 이용하지 않고 경사하강법 알고리즘을 이용해서 선형모델을 찾아보자.
• 무어 펜로즈 역행렬을 이용하지 않는 이유는, 선형모델을 이용해서 분석을 하게 된다면 경사하강법을 이용하지 않아도 되지만, 선형 모델이 아닌 다른 방식의 모델을 사용할 때는 경사하강법을 이용해서 최적의 모델을 찾을 수 있기 때문이다.

• 따라서 좀 더 일반적인 기계학습 모형에서 최적화를 할 때 사용하는 방법론이 경사하강법 알고리즘을 이용한 최적화 방법이다.

  경사하강법으로 선형회귀 계수 구하기

  • 이를 위해 주어진 선형회귀의 목적식을 이해하고 이 목적식을 최소화해야 한다. 따라서 목적식을 최소화하는 방향으로서의 미분을 계산할 수 있어야 한다.
  • 선형회귀에서 사용되는 목적식은 $L2$ 노름이다. 주어진 데이터에서 정답에 해당하는 $\mathbf{y}$ 와 사용하는 선형모델 $\mathbf{X}\beta$ 두 벡터의 차이의 $L2$ 노름을 최소화하는 $\beta$ 를 찾는 것이 선형회귀분석의 목적이다.
  • 이 목적식을 최소화하고 싶다면 이 목적식을 $\beta$ 로 미분을 한 다음, 주어진 $\beta$ 에서 미분값을 빼주게 되면 경사하강법 알고리즘으로 최소에 해당하는 점을 구할 수 있다.

  • 다시 정리하면, 선형회귀의 목적식은 정답과 예측의 $L2$ 노름이고, 이를 최소화하는 $\beta$ 를 찾기 위해서 그레디언트 벡터를 계산해야 한다.

    \[\text{objective func} = \Vert\mathbf{y} - \mathbf{X}\beta \Vert_2 \\ \\ \nabla_{\beta} \Vert \mathbf{y}-\mathbf{X}\beta \Vert_2 = (\partial_{\beta_1} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2 , \cdots, \partial_{\beta_d} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2)\]
  • 주어진 목적식 $L2$ 노름에 계수 $\beta$ 로 그레디언트 벡터를 계산하면 각각의 계수마다 목적식을 미분하는 계산을 하게 된다. 이 때 목적식 $L2$ 노름을 $\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2$ 가 아닌 $\Vert \mathbf{y} - \mathbf{X}\beta \Vert^2_2$ 로 제곱한 형태의 목적식을 최소화해도 된다.
  • 그레디언트 벡터를 계산해보자. 주어진 $\beta$ 벡터 내에서 $k$ 번째 계수에 해당하는 $\beta_k$ 를 가지고 목적식을 편미분한다.

  • 먼저 $\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2$ 을 풀어쓰게 되면 아래 수식에서 우측 수식이 나온다.

    \[\partial_{\beta_k} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2 = \partial_{\beta_k} \left \{ \frac{1}{n} \sum^n_{i=1} \left( y_i - \sum^d_{j=1}X_{ij}\beta_j\right)^2\right \}^{1/2}\]
  • 이 때의 $L2$ 노름은 원래의 $L2$ 노름과 살짝 차이가 있다. 여기서 사용된 $L2$ 노름은 $n$ 개의 데이터를 가지고 계산된 $L2$ 노름이기 때문에 $i=1 \sim n$ 까지 더해준 다음에 제곱근을 취해주는 것이 아니고, 평균값을 계산해주기 위해서 $1/n$ 으로 나눈 후에 제곱근을 계산해준다.

  • 이 목적식을 가지고 최소화를 하는 방식이 보통 선형회귀의 목적식이다. 이 수식을 $\beta_k$ 로 편미분하게 되면 아래와 같다.

    \[\begin{aligned} \partial_{\beta_k} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2 &= \partial_{\beta_k} \left \{ \frac{1}{n} \sum^n_{i=1} \left( y_i - \sum^d_{j=1}X_{ij}\beta_j\right)^2\right \}^{1/2} \\ &= - \frac{\mathbf{X}^T_k(\mathbf{y}-\mathbf{X}\beta)}{n\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2} \end{aligned}\]
  • 편미분 결과를 잘 보면, 원래 목적식 $L2$ 노름에 해당하는 $\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2$ 이 분모로 가게 되고, $L2$ 노름을 씌우기 전인 $\mathbf{y} - \mathbf{X}\beta$ 와 $\mathbf{X}$ 의 전치행렬의 $k$ 번째 열벡터를 곱해준 것이 분자로 가게 된다.

  • 이것이 $k$ 번째 계수 $\beta_k$ 에 대한 목적식의 편미분이다. 이제 각각의 $k$ 번째 성분에 대한 편미분을 계산하면 아래와 같다.

    \[\begin{aligned} \nabla_{\beta} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2 &= (\partial_{\beta_1} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2 , \cdots, \partial_{\beta_d} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2) \\ &= \left( - \frac{\mathbf{X}^T_1(\mathbf{y}-\mathbf{X}\beta)}{n\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2} , \cdots, - \frac{\mathbf{X}^T_d(\mathbf{y}-\mathbf{X}\beta)}{n\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2} \right) \end{aligned}\]

  • 여기서 1 부터 $d$ 까지에 해당하는 $\mathbf{X}^T$의 $k$ 번째 열벡터의 표기를 행렬로 표시하게 되면 아래와 같이 깔끔하게 나타낼 수 있다.

    \[\begin{aligned} \nabla_{\beta} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2 &= (\partial_{\beta_1} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2 , \cdots, \partial_{\beta_d} \Vert \mathbf{y} - \mathbf{X}\beta \Vert_2) \\ &= \left( - \frac{\mathbf{X}^T_1(\mathbf{y}-\mathbf{X}\beta)}{n\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2} , \cdots, - \frac{\mathbf{X}^T_d(\mathbf{y}-\mathbf{X}\beta)}{n\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2} \right) \\ &= - \frac{\mathbf{X}^T(\mathbf{y}-\mathbf{X}\beta)}{n\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2} \end{aligned}\]
  • 복잡한 계산이지만 사실 $\mathbf{X}\beta$ 라는 선형모델을 계수 $\beta$ 에 대해 미분한 결과가 $\mathbf{X}^T$ 이기 때문에, $d$ 차원에서의 미분을 계산하는 방법이 1차원에서 미분을 계산하는 방법과 직관적으로 동일하다는 것을 알 수 있다.

  • 예를 들어보자.

    \[\mathbf{X} = \begin{pmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \\ \end{pmatrix} \quad \beta = \begin{pmatrix} \beta_1 \\ \beta_2 \end{pmatrix}\]

  • 위와 같이 $\mathbf{X}$ 와 $\beta$ 가 있을 때, $\mathbf{X}\beta$ 는 아래와 같다.

    \[\mathbf{X}\beta = \begin{pmatrix} x_{11}\beta_1 + x_{12}\beta_2 \\ x_{21}\beta_1 + x_{22}\beta_2 \end{pmatrix}\]
  • 이제 이 벡터를 $\beta$ 에 대해 미분하면, 각 성분에 대해 다음과 같이 미분한다.
    • $\frac{\partial}{\partial \beta_1}$ : $\mathbf{X}$ 의 첫 번째 열이 남는다.
    • $\frac{\partial}{\partial \beta_2}$ : $\mathbf{X}$ 의 두 번째 열이 남는다.
  • 이를 전부 모으면 결과적으로 $\mathbf{X}^T$ 가 나온다.

  • 이제 목적식을 최소화하는 $\beta$ 를 구하는 경사하강법 알고리즘은 다음과 같다.

    \[\beta^{(t+1)} \leftarrow \beta^{(t)} - \lambda\nabla_{\beta}\Vert \mathbf{y} - \mathbf{X}\beta^{(t)}\Vert\]
  • 미분값, 즉 그레디언트 벡터를 빼주게 되면 경사하강법 원리에 따라 목적식을 최소화할 수 있다. 이 때도 학습률($\lambda$) 을 사용하여 수렴 속도를 결정해줄 수 있다.
  • $t$ 번째 $\beta$ 에 계속해서 그레디언트 벡터를 구해서 빼주면서 업데이트 해주면, 즉 $t$ 를 계속해서 반복적으로 나아가면서 목적식을 최소화하는 $\beta$ 를 찾을 수 있게 된다.

  • 그레디언트 벡터를 빼주게 됐을 때 그레디언트 벡터에 음수 기호가 붙어있기 때문에 실제로 식을 쓰게 되면 아래와 같다.

    \[\beta^{(t+1)} \leftarrow \beta^{(t)} + \frac{\lambda}{n}\frac{\mathbf{X}^T(\mathbf{y}-\mathbf{X}\beta^{(t)})}{\Vert \mathbf{y} - \mathbf{X}\beta^{(t)}\Vert_2}\]
  • 여기서 선형회귀의 목적식인 $L2$ 노름을 계산할 때 제곱근을 이용하지 않고 $L2$ 노름의 제곱을 목적식으로 해서 최소화를 해도 최적화하는 방향이 똑같다.
  • $L2$ 노름을 최소화하는 $\beta$ 를 찾나 $L2$ 노름의 제곱을 최소화하는 $\beta$ 를 찾나 둘 다 똑같은 결과값을 가져온다는 것이다.

  • $\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2$ 대신 $\Vert \mathbf{y} - \mathbf{X}\beta \Vert^2_2$ 를 사용하여 최소화하면 식이 좀 더 간단해진다.

    \[\begin{aligned} \nabla_{\beta} \Vert \mathbf{y} - \mathbf{X}\beta \Vert^2_2 &= (\partial_{\beta_1} \Vert \mathbf{y} - \mathbf{X}\beta \Vert^2_2 , \cdots, \partial_{\beta_d} \Vert \mathbf{y} - \mathbf{X}\beta \Vert^2_2) \\ &= - \frac{2}{n}\mathbf{X}^T(\mathbf{y}-\mathbf{X}\beta)\end{aligned} \\ \\ \beta^{(t+1)} \leftarrow \beta^{(t)} + \frac{2\lambda}{n}\mathbf{X}^T(\mathbf{y}-\mathbf{X}\beta^{(t)})\]
  • 이처럼 그레디언트 벡터를 좀 더 쉽게 계산하기 위해서 $L2$ 노름의 제곱을 이용해서 그레디언트 벡터를 계산하게 된다. 이를 이용해서 경사하강법에 이용해도 된다는 것이다.

  경사하강법 기반 선형회귀 알고리즘

  • 정답에 해당하는 $\mathbf{y}$ 와 선형모델에 해당하는 $\mathbf{X}$ 행렬과 $\beta$ 벡터의 행렬곱을 빼준 항을 error term 으로 정의한다.
  • 즉 error term 은 $\mathbf{y}-\mathbf{X}\beta^{(t)}$ 와 동일한 식이 된다.
  • 이제 그레디언트 벡터를 계산할 때는 error term 에 $\mathbf{X}$ 의 전치행렬을 행렬곱으로 곱해주고 - 를 붙이면 그레디언트 벡터가 된다.

  • 이를 이용해서 $\beta$ 를 업데이트를 하는 아래와 같은 경사하강법 알고리즘을 짤 수 있다.

      # input : X, y, lr, T
      # output : beta
      # norm : L2 norm 을 계산하는 함수
      # lr : 학습률
      # T : 학습횟수
            
      for t in range(T):
          error = y - X @ beta
          grad = - transpose(X) @ error
          beta = beta - lr * grad
    

  • 이 때 종료조건으로 eps 가 아니라 특정 T 로 표현되는 학습횟수가 있다.
  • 그레디언트 벡터가 특정 이하로 떨어질 때까지 업데이트하는 알고리즘(eps)을 써도 되고, 학습 알고리즘을 지정된 시간 동안 수행하고 싶다면 종료조건을 학습횟수(T)로 변경할 수 있다.
  • 오늘날 딥러닝 알고리즘에서 사용되는 경사하강법 알고리즘들은 종료조건이 이와 같이 학습횟수로 제어하게 된다.
  • 주의할 점은, 학습횟수를 너무 작게 잡게 되면 경사하강법 알고리즘이 수렴하지 못하게 될 수도 있다.
  • 정리하면 error term 을 계산하고 이를 이용해서 그레디언트 벡터(grad)를 계산할 수 있고, 이 때 계산된 grad 는 $\nabla_{\beta} \Vert \mathbf{y} - \mathbf{X}\beta \Vert^2_2$ 를 계산한 것이다.
  • 이를 이용해서 $\beta$ 를 계속 업데이트 함으로써 주어진 목적식을 최소화하는 선형 모델의 계수 $\beta$ 를 구할 수 있다.
  • 이제 무어-펜로즈 역행렬을 이용하지 않고 경사하강법 알고리즘으로 충분히 회귀계수를 찾을 수 있다.
  • 그러나 경사하강법 알고리즘도 무어-펜로즈 역행렬을 이용하는 것처럼 정확한 값에 도달할 때까지 계속해서 수렴하는 것은 아니기 때문에 학습횟수를 너무 작게 설정하면 실제로 목표로 하는 계수를 찾지 못할수도 있다.
  • 따라서 학습률과 학습횟수를 적절하게 조절해야 실제로 목표하는 계수들을 찾는데 잘 활용할 수 있다. 따라서 학습률과 학습횟수가 중요한 하이퍼 파라미터가 된다.
  • 학습률을 너무 작게 하면 수렴을 너무 늦게 하게 되고, 크게 잡게 되면 경사하강법 알고리즘이 불안정하게 움직이게 된다.
  • 만약 학습횟수를 너무 적게 잡게 되면 경사하강법 알고리즘의 수렴이 잘 안될 수 있고, 중간에 멈출 수도 있다.

경사하강법은 만능?

• 경사하강법은 사실 만능이 아니다.
• 역행렬을 사용하지 않고도 최적화를 시킬 수 있기 때문에 편리한 최적화 알고리즘이기는 하지만, 학습률과 학습횟수를 매우 적절하게 선택을 했을 때만 이론적으로 수렴이 가능하다.
• 즉 이론적으로 경사하강법은 미분 가능하고 볼록(convex)한 함수에 대해선 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어 있다.

• 볼록한 함수는 그레디언트 벡터가 항상 최소점을 향한다.

  

• 특히 선형회귀의 경우 목적식은 $L2$ 노름을 사용한 $\Vert \mathbf{y} - \mathbf{X}\beta \Vert_2$ 가 되는데, 이 목적식은 회귀계수 $\beta$ 에 대해서 볼록함수가 된다.
• 따라서 선형회귀를 돌리는 경우 경사하강법을 사용했을 때 알고리즘을 충분히 돌리면 목적으로 하는 선형모델의 계수 $\beta$ 를 찾을 수 있다. 즉 수렴이 보장된다.
• 문제는 선형 모델이 아니라 비선형회귀, 다시 말해 non-linear regression 문제나 목적식이 볼록하지 않은 경우가 있다. 이런 경우에는 경사하강법 알고리즘이 항상 수렴을 보장하지는 않는다.
• 특히 딥러닝은 목적식이 대부분 볼록함수가 아니고 아래 그림과 같이 볼록한 부분이 여러 곳에 있을 수 있다. 이런 경우를 볼록하지 않은 non-convex 함수라고 한다.

• 딥러닝에서 사용하는 대부분의 모델과 목적식의 경우 이런 식으로 볼록성을 보장하지 못하기 때문에 경사하강법 알고리즘이 항상 수렴하지는 않는다.

  

• 따라서 경사하강법을 딥러닝에 쓸 때는 그냥 경사하강법을 쓸 수는 없다. 변형된 경사하강법 알고리즘을 사용해야 한다.

확률적 경사하강법(SGD)

• non-convex 인 목적식에서 일반적인 경사하강법(GD)은 최적화(최소값, 극점 찾기)하기 힘들다. 이 때 경사하강법을 대체할 수 있는 확률적 경사하강법(stochastic gradient descent)을 사용할 수 있다.
• 딥러닝 논문들을 볼 때 SGD 를 보게 되는데, 이것이 확률적 경사하강법이다.
• SGD 는 일반 경사하강법과 달리 모든 데이터를 사용해서 업데이트하는 것이 아니라, 즉 모든 데이터를 사용해서 그레디언트를 계산하는 것이 아니라, 데이터를 한 개 또는 일부 활용해서 그레디언트를 계산해서 업데이트하는 방식이다.
• 데이터 일부를 활용하는 것을 mini-batch 라고 부른다. 데이터를 한 개만 활용하는 경우 그냥 SGD 라 부르고 mini-batch 를 사용해서 업데이트를 하게 되면 mini-batch SGD 라고 부른다.
• 오늘날 딥러닝에서 거의 일반적으로 사용되는 SGD 는, 데이터를 한 개만 사용하면 비효율적이기 때문에 mini-batch 를 사용한다. 따라서 SGD 를 부르는 것은 보통 mini-batch SGD 를 나타낸다고 볼 수 있다.
• SGD 는 non-convex 목적식인 경우에 경사하강법과 달리 최적화된 값을 찾을 수 있다. 이름에 들어가 있는 의미처럼 경사하강법을 확률적으로 시도하는 것이다.
• 경사하강법(GD)에서 그레디언트를 계산할 때는 모든 데이터를 사용해서 그레디언트 벡터를 계산했었는데, SGD 는 모든 데이터가 아니라 데이터의 일부만 가지고 그레디언트 벡터를 계산한다. 따라서 모든 데이터에서 계산한 그레디언트 벡터와 유사하기는 하지만, 그 그레디언트 벡터와 절대 같을 수는 없다.

• 하지만 데이터의 일부 활용으로 계산한 그레디언트 벡터의 기댓값이 모든 데이터를 사용해서 계산한 그레디언트 벡터와 유사할 것이라는 것이 확률적으로 보장된다. 이를 이용해서 실제 그레디언트 벡터를 이용해서 수행되는 경사하강법과 유사한 방식으로 사용할 수 있다.

  \[\theta^{(t+1)} \leftarrow \theta^{(t)} - \widehat{\nabla_{\theta}\mathcal{L}}(\theta^{(t)}) \quad \quad \mathbb{E}[\widehat{\nabla_{\theta}\mathcal{L}}] \approx \nabla_{\theta}\mathcal{L}\]
• 물론 SGD 또한 학습률과 학습횟수를 고려해야 하기 때문에 만능은 아니지만, 딥러닝의 경우 SGD 를 사용하는 것이 경사하강법(GD)보다 실증적으로 더 낫다는 것이 많이 검증되어 있다.
• 확률적 경사하강법을 사용하게 되면 데이터의 일부를 가지고 파라미터를 업데이터하기 때문에, 모든 데이터를 활용해서 업데이트하는 것보다 연산자원을 좀 더 효율적으로 활용하는데 도움이 된다.
• 만약 모든 데이터를 가지고 그레디언트 벡터를 계산할 때 데이터의 개수가 $n$ 개라면 연산량이 $d^2n$ 정도 된다.
• 그러나 $n$ 개의 모든 데이터가 아니라 그 중에서 일부 $b$ 개의 mini-batch 를 가지고 그레디언트 벡터를 계산하면 $d^2b$ 만큼의 연산량으로 줄어들게 된다.

• 이 때 계산되는 그레디언트 벡터는 비록 GD 를 통해 계산되는 그레디언트 벡터와 동일하지는 않지만, 확률적으로 기댓값의 관점에서 원래 그레디언트 벡터와 유사하게 사용할 수 있기 때문에, 정확한 그레디언트 벡터는 아니라 하더라도 연산량을 훨씬 더 효율적으로 활용함과 동시에 그레디언트 벡터와 유사한 효과를 발휘할 수 있다.

  \[\small{\beta^{(t+1)} \leftarrow \beta^{(t)} + \frac{2\lambda}{n}\mathbf{X}^T(\mathbf{y}-\mathbf{X}\beta^{(t)}) \; \xrightarrow{O(d^2n) \; \rightarrow \; O(d^2b)} \; \beta^{(t+1)} \leftarrow \beta^{(t)} + \frac{2\lambda}{\color{red}b}\mathbf{X}^T_{\color{red}{(b)}}(\mathbf{y_{\color{red}{(b)}}}-\mathbf{X}_{\color{red}{(b)}}\beta^{(t)})}\]
• 즉 전체 데이터 ($\mathbf{X, y}$) 를 쓰지 않고 mini-batch ($\mathbf{X_{(b)}, y_{(b)}}$) 를 써서 업데이트 하므로 연산량이 $\frac{b}{n}$ 만큼 감소한다.
• 따라서 SGD 를 통해서 목적식을 최적화할 수 있고, 좀 더 연산자원을 효율적으로 사용해서 목적으로 하는 파라미터의 최적화도 가능하다.

확률적 경사하강법의 원리: 미니배치 연산

• 경사하강법은 전체 데이터 $\mathscr{D} = (\mathbf{X, y})$ 를 가지고 목적식($L$)의 그레디언트 벡터인 $\nabla_{\theta}L(\mathscr{D},\theta)$ 를 계산한다.

• $\nabla_{\theta}L(\mathscr{D},\theta)$ 은 현재 주어진 파라미터 $\theta$ 에서 주어진 목적식의 최소점으로 향하는 방향을 안내해준다. 이 때 $L(\mathscr{D},\theta)$ 은 전체 데이터 $\mathscr{D}$ 와 파라미터 $\theta$ 로 측정한 목적식이다.

  

• SGD 의 경우 미니배치, 즉 전체 데이터의 일부($\mathscr{D}_{(b)}$)를 가지고 그레디언트 벡터를 계산하기 때문에, 목적식을 계산할 때 전체 목적식을 계산하는 것이 아니라서 아래 그림과 같이 목적식이 살짝 바뀌게 된다.

  \[\mathscr{D}_{(b)} = (\mathbf{X}_{(b)}, \mathbf{y}_{(b)}) \subset \mathscr{D}\]

  

• 미니배치를 사용해서 목적식을 계산했기 때문에 그레디언트 벡터값이 좀 다를 수 있겠지만 방향은 유사할 것이라고 기대할 수 있다.
• 즉, 미니배치를 이용해서 그레디언트 벡터를 계산하는 SGD 를 사용하게 되면 원래 경사하강법에서 이동시키고 싶어하는 파라미터의 방향과 유사하게 이동시키는 게 가능하다.

• 미니배치는 확률적으로 선택하므로 목적식 모양이 바뀌게 된다. 또한 매번 다른 미니배치를 사용하기 때문에 곡선 모양이 바뀌게 된다.

  

• 경사하강법에서 step 이라는 용어를 쓰게 되는데, $t$ step, $t+1$ step, $t+2$ step 이렇게 경사하강법을 순차적으로 적용하게 되면 미니배치를 매번 다르게 사용해서 그레디언트 벡터를 계산하게 된다.
• 따라서 위 그림처럼 목적식의 모양이 고정되지 않고 매번 미니배치를 샘플링하게 될 때마다 목적식 모양이 점점 바뀌게 된다.
• 이 때 앞 step 에서 찾은 새로운 파라미터($\theta$, 점)로 그레디언트 벡터를 계산하고, 하나의 목적식에서 계산된 그레디언트 벡터가 아니라 바뀐 모양에서의 그레디언트 벡터를 계산한다. 중요한 것은 원래 경사하강법에서 사용되는 그레디언트 벡터랑 다른 값이 나오게 될 수도 있지만 방향은 비슷한 방향으로 갈 수가 있다.
• 이렇게 서로 다른 미니배치를 사용하여 곡선 모양이 다른 모양으로 바뀌게 되는 것은 의미가 있다. 볼록 함수가 아닌 non-convex 함수일 때 로컬 포인트, 즉 극소점이나 극대점에 도달해서 그레디언트 벡터가 영벡터가 되는 경우가 있다고 하더라도, SGD 를 통해 극소점이나 극대점에서 목적식이 확률적으로 바뀌어 극소점이 더 이상 아니게 될 확률이 발생하게 된다.
• 확률적으로 극소점이 더 이상 아니게 되면 SGD 의 원리상 원래 경사하강법에서 사용했던 그레디언트 벡터가 영벡터라 하더라도, 목적식이 바뀐 상태에서 그레디언트 벡터를 계산하게 되면 값이 영벡터가 아니기 때문에 극소점에서 탈출하는 것이 가능하게 된다.
• 이것을 이용해서 SGD 는 볼록함수가 아닌 non-convex 함수라 하더라도 최소점을 찾는데 활용할 수 있게 된다.

• 이처럼 SGD 는 볼록이 아닌 목적식에서 사용 가능하지만, 경사하강법처럼 정확하게 그레디언트 벡터를 계산해서 흐르는 것은 아니다보니, 그레디언트 벡터가 확률적으로 움직이는 모양처럼 흐르게 된다. 따라서 경사하강법처럼 똑바른 방향으로 최소점을 향하는 것은 아니고, 왔다갔다하는 모양새로 움직이게 된다.

  

• 그러나 SGD 도 데이터를 가지고 그레디언트 벡터를 계산해서 움직이기 때문에 최소점으로 향하는 움직임은 똑같은 경향을 가지게 된다.
• 무엇보다 경사하강법은 모든 데이터를 가지고 그레디언트 벡터를 계산하는 반면에 SGD 는 미니배치를 가지고 그레디언트 벡터를 계산하여 각각의 화살표를 계산할 때 연산속도가 경사하강법보다 훨씬 더 빠르다.
• 다시 말해 SGD 는 정확하지 않은 방향이지만, 훨씬 더 빠르게 움직일 수 있다. 따라서 경사하강법 알고리즘보다 훨씬 더 연산에 효율적이다.
• 또한 맨 오른쪽 그림을 보면 경사하강법(GD)을 활용할 때와 미니배치 크기에 따른 SGD 의 수렴 속도 차이를 볼 수 있다.
• $x$ 축은 경사하강법을 돌리는 step 이라 볼 수 있고, $y$ 축은 목적식에 해당하는 loss function 이다.
• 미니배치 SGD 를 적용했을 때 경사하강법을 적용하는 것보다 훨씬 더 빠르게 최소점에 도달하는 것을 볼 수 있다.
• 또한 SGD 에서 미니배치 크기를 너무 작게 잡게 되면 경사하강법 알고리즘보다 훨씬 더 느리게 수렴할 수도 있음을 알 수 있다.
• 경사하강법에서 고려해야 했던 학습률, 학습횟수를 SGD 에서도 고려하고, 이 뿐만 아니라 미니배치 크기도 학습에서 고려해야 하는 요인 중 하나가 되는 것이다.

확률적 경사하강법의 원리 : 하드웨어

• 오늘날 딥러닝에서 사용되는 데이터는 사이즈도 크고 데이터 양도 크다.
• 이미지 데이터를 예제로 들면, 256 x 256 x 3 에 해당하는 이미지가 100만장 있을 때, $2^{37}$ 정도 되는 byte 를 차지한다. 이 이미지 데이터를 통째로 경사하강법을 계산하려고 한다면 하드웨어적인 한계 때문에 경사하강법을 이용해서 업데이트 할 때 메모리 부족인 OOM(Out Of Memory) 현상이 발생한다.
• 이처럼 GPU 상에서의 메모리가 통제가 되지 않기 때문에 일반적인 GD 로 딥러닝 학습을 돌리는 것이 학습에 도움이 되지도 않을 뿐만 아니라 하드웨어적인 한계를 가져오기 쉽다.
• 그러나 SGD 를 이용해서 미니배치로 쪼개서 하게 되면, 전체 이미지 데이터를 가지고 하는 것이 아니라 일부 미니배치 데이터를 가지고 업로드가 가능하고 경사하강법 업데이트를 할 수 있다. 따라서 좀 더 빠르게 연산도 가능하고 하드웨어의 한계를 극복해서 병렬 연산을 통해 딥러닝 학습이 가능하다.
• GPU 에서 행렬 연산과 모델 파라미터를 업데이트 하는 동안, CPU 는 전처리와 GPU 에서 업로드할 데이터를 준비한다.
• 오늘날 딥러닝 학습에서는 GD 가 아니라 SGD 가 알고리즘의 효율성과 하드웨어를 고려했을 때 반드시 필수적인 알고리즘이 되었다.

맨 위로 이동 ↑