경사하강법

1. 미분

---

• 미분은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구

• python sympy.diff를 통해 미분 계산 가능.

• 미분의 값은 함수 f의 주어진 점(x, f(x))에서의 접선의 기울기이다.
  → 어느 방향으로 점을 움직여야 함수값이 증가/감소 하는지 알 수 있다.
  → 미분값을 해당 점에 더하면 증가하는 방향, 빼면 감소하는 방향으로 움직인다.

• 미분값을 더하면 경사상승법(gradient ascent) → 극대값의 위치를 구할 수 있다.

• 미분값을 빼면 경사하강법(gradient descent) → 극소값의 위치를 구할 수 있다.

• 변수가 많을 때(변수가 벡터일 때), 편미분을 사용한다.

• ei는 i번째 값만 1이고 나머지는 0인 단위 벡터라고 했을 때, 아래 식은 i번째 변수에 관한 변화율을 구하는 식이다.

• 그레디언 벡터는 각 변수 별로 편미분을 계산한 것이다. 구하는 방법은 아래와 같다.
  (▽ 기호를 nabla라 부른다.)
  $\bigtriangledown f = <\partial_{x_1}f, \cdots , \partial_{x_n}f>$

경사 하강법 pseudo code

#!/usr/bin/python

point = [ ... ] # 점의 위치
grad = gradient(point) # 미분값

# 컴퓨터에서 정확히 0은 구할 수 없으므로,
# eps(epsilon)보다 작을 때 종료한다.
while (norm_l2(grad) > eps):
    # lr은 learning rate로 극소값으로 가는 속도,
    # 수렴, local minima 등의 문제와 관련이 있다.
    # → 조심히 다뤄야 한다.
    point = point - lr * grad
    grad = gradient(point)

2. 경사하강법

---

• 노름과 역행렬에서 Moore-Penrose를 이용해 선형회귀분석을 구할 수 있었다.

• 하지만, Moore-Penrose는 오직 선형회귀분석에서만 적용가능하므로, 선형회귀분석 모델이 아닌 다른 모델에도 적용할 수 있는, 일반적인 방법인 경사하강법에 대해 알아보자.

2.1. 계수(coefficient) 구하기

• 선형회귀의 목적식은 $||\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\beta}||_{2} (=||\boldsymbol{y}-\boldsymbol{\hat{y}||_2})$ 이고, 이를 최소화 하는 $\boldsymbol{\beta}$(계수의 벡터)를 찾아야 한다.

• 따라서 목적식을 $\boldsymbol{\beta}$에 대해서 미분을 한다음 그 값을 빼줘야하기 때문에, 목적식의 그레디언트 벡터를 구해야한다.

• 목적식의 그레디언트 벡터를 구하는 것은 다음과 같이, k번째 계수 $\beta_k$에 대해 $||\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\beta}||_2$를 편미분 해야한다.

• $||\boldsymbol{y - X\beta}||_2$ 대신 $||\boldsymbol{y - X\beta}||_2^2$를 통해 목적식의 그레디언트 벡터를 구해도 된다.

• loss function관점에서 전자를 RMSE, 후자를 MSE라고 볼 수 있다.

• m을 나누어 평균을 구해주는 것은, 데이터가 많아서 오차의 합이 큰지와 실제 오차가 커서 오차의 합이 큰지를 구분하기 위한 것이다.

• 만약 m을 나눠주지 않는다면, 데이터가 많을수록 오차의 합이 커진다.

• 이것은 다시 아래와 같이 표현할 수 있다.

$\partial_{\beta_k}||\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\beta}||_2$

$=\partial_{\beta_k}\Bigg\{ \frac{1}{m} \sum\limits_{i=1}^{m} \Bigg( y_i - \sum\limits_{j=1}^{n} X_{ij}\beta_j \Bigg)^2 \Bigg\}^{1/2}$

$= \frac{\partial_{\beta_k}\sqrt{(y_1 - (X\beta)_1)^2+\cdots+(y_m - (X\beta)_m)^2}}{\sqrt{m}}$

$= \frac{\Big\{(y_1 - (X\beta)_1)^2+\cdots+(y_m - (X\beta)_m)^2\Big\}^{-\frac{1}{2}} \ \cdot \ -2 \ \cdot \ \Big\{(y_1 - (X\beta)_1)X_{1k}+ \cdots + (y_m - (X\beta)_m)X_{mk} \ \Big\}}{2\sqrt{m}}$

$= -\frac{(y_1 - (X\beta)_1)X_{1k}+ \cdots + (y_m - (X\beta)_m)X_{mk}}{\sqrt{m}\sqrt{(y_1 - (X\beta)_1)^2+\cdots+(y_m - (X\beta)_m)^2}}$

$= -\frac{(y_1 - (X\beta)_1)X_{1k}+ \cdots + (y_m - (X\beta)_m)X_{mk}}{m\sqrt{\frac{(y_1 - (X\beta)_1)^2+\cdots+(y_m - (X\beta)_m)^2}{m}}}$

$= -\frac{\boldsymbol{X}^T_k(\boldsymbol{y} - \boldsymbol{X\beta})}{m||\boldsymbol{y} - \boldsymbol{X\beta}||_2}$

여기서 $||\boldsymbol{y} - \boldsymbol{X\beta}||_2$는 제곱오차에서 m을 나눠야 한다.

벡터의 $L_2$ norm와 다르다. 이것은 아까 살펴보았듯이 데이터가 많아서 오차가 큰지, 실제 오차가 큰지를 구분하기 위한 것이다.

• $\boldsymbol{X}^T_k$은 행렬 $\boldsymbol{X}$의 k번째 열 벡터를 전치시킨 것이다.

• 복잡한 계산이지만, $\boldsymbol{X\beta}$라는 선형 모델을 계수 $\boldsymbol{\beta}$에 대해 미분한 결과인 $\boldsymbol{X}^T$만 곱해지는 것이다.

• $\beta_k$에 대해 미분하기 때문에 나머지 계수($\beta_1, \cdots)$에 대응하는 항은 사라지게 되어, k번째 데이터만 오차에 곱해진다.

• 따라서 $\boldsymbol{X}^T_k(\boldsymbol{y} - \boldsymbol{X\beta})$는 k번째 계수에 대응하는 $\boldsymbol{x}$ 벡터가 오차에 곱해지는 것이라고 볼 수 있다.

• 뒤의 예시에서 직관적으로 알아보자.

• 앞에서 구한 목적식의 그레디언브 벡터를 통해 목적식을 최소화하는 $\boldsymbol{\beta}$를 구하는 알고리즘은 아래와 같다.

• $\lambda$는 learning rate 이다.

• $||\boldsymbol{y - X\beta}||_2$ 대신 $||\boldsymbol{y - X\beta}||_2^2$을 최소화하면 식이 좀 더 간단해진다.

• 주의할 점은 paramter($\beta$)들을 동시에 업데이트 해야한다.

$y = 7x + 2$를 예로 들어보자.

데이터 x가 [1, $\cdots$, 1000], 초기 $w = 0, b=0$라 하자.

$||\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\beta}||_2^2$의 최소하에 대해 생각해보자.

$\hat{y} = w \times x + b$이고, $error$ 값은 $\frac{1}{m} \sum\limits_{i=1}^{m} \Big( w \times x_i + b - y_i \Big)^2$ 이다.

우선 $error$ 값을 $w$에 대해 미분하면, $\frac{2}{m} \sum\limits_{i=1}^{m} \Big( w \times x_i + b - y_i \Big) \times x_i$가 된다.

그리고 $error$ 값을 $b$에 대해 미분하면, $\frac{2}{m} \sum\limits_{i=1}^{m} \Big( w \times x_i + b - y_i \Big) \times 1$가 된다.

이를 행렬로 나타내보자.

우선 $\boldsymbol{X}$에 bias를 추가해주기 위해 $\boldsymbol{X}=[\boldsymbol{X}|1]$ 같은 형태로 expand해줘야 한다.

그리고 편미분한 결과는 $\beta_{k}$에 대응하는 $x_k$만 살아남아 $\hat{y}_k-y_k$에 곱해진다.

따라서 그레디언 벡터는 $\bigtriangledown_{\beta}||\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\beta}||_2 = \frac{2}{m} \boldsymbol{X}^T(\boldsymbol{X\beta} - \boldsymbol{y})$ 같은 형태가 된다.

그레디언 벡터에 음수의 유무는 $\hat{y}$, $y$의 순서차이이다.

만약 $y - \hat{y}$로 한다면 편미분할 시, 음수가 나오게 되므로 앞에 '$-$'를 붙여야 한다.

2.2. 선형회귀 경사하강법 구현

• pseudo code

# l2 노름의 제곱을 이용해 beta를 업데이트하는 코드이다.
# 보통 eps보다 학습 횟수를 통해 model을 최적화 한다.
# T는 학습 횟수이다.
# 정확한 계수를 찾을 수 없으므로 lr과 T를 적절히 선택해야한다.
for t in range(T):
    error = y - X @ beta
    grad = - transpose(X) @ error
    beta = beta - lr * grad

• RMSE code: $y = wx + b$

for i in range(100):
    ## Todo
    # 예측값 y
    y_hat = w * train_x + b

    # gradient
    # gradient를 구할 때, y_hat - train_y로 했다면 -를 붙일 필요가 없다.
    # 둘의 위치에 따라 편미분 하면서 1 또는 -1이 나오기 때문이다.
    gradient_w = np.sqrt(1/n_data) * np.sqrt(1/np.sum((train_y - y_hat) ** 2)) * -1 * np.sum((train_y - y_hat) * train_x)
    gradient_b = np.sqrt(1/n_data) * np.sqrt(1/np.sum((train_y - y_hat) ** 2)) * -1 * np.sum(train_y - y_hat)

    # w, b update with gradient and learning rate    
    w -= lr_rate * gradient_w
    b -= lr_rate * gradient_b

    # L2 norm과 np_sum 함수 활용해서 error 정의
    error = np.sqrt(((train_y - y_hat) ** 2).mean())
    # Error graph 출력하기 위한 부분
    errors.append(error)

2.3. 경사하강법에 대하여

• 경사하강법은 만능이 아니다. 이론적으로 경사하강법은 미분가능하고 볼록(convex)한 함수에 대해서 적절한 learning rate와 학습횟수를 선택했을 때 수렴이 보장된다.

• 선형회귀에서 $||\boldsymbol{y - X\beta}||_2$은 회귀계수 $\beta$에 대해 미분가능하고 볼록한 함수이기 때문에 수렴이 보장된다.

• 비선형회귀인 경우 대부분 볼록한 함수가 아니기(non-convex) 때문에 수렴이 항상 보장되지 않는다. 이 경우 확률적 경사하강법을 사용한다.

3. 확률적 경사하강법(SGD: Stochastic Gradient)

---

• non-convex한 목적식은 SGD를 통해 최적화할 수 있다.

• SGD는 모든데이터를 사용해 업데이트하는 대신 데이터 한개 또는 일부 활용하여 업데이트한다.

• 데이터 일부만 활용하기 때문에 연산자원을 좀 더 효율적으로 활용할 수 있다.

• 대부분 ML 학습 모델은 비선형이기 때문에 SGD를 사용하는 것이 더 효율적이다.

• 한개를 사용할 경우 SGD라고 부르고, 일부를 활용할 경우 Mini-Batch SGD라고 부른다.

• Mini-Batch SGD의 기대값이 모든 데이터를 활용한 것과 유사하는 것이 증명되어 있다.

• 대부분 Mini-Batch SGD를 활용한다. 최적화한 결과가 모든 데이터를 활용한 것과 유사하나 같지는 않다.

• SGD도 만능이 아니지만, 딥러닝의 경우 SGD가 경사하강법보다 실증적으로 더 낫다고 검증되었다.

• Mini-Batch는 step마다 매번 다른 것을 사용하기 때문에 목적식의 모양도 바뀌게 된다.

• 그렇기 때문에 모든 데이터를 사용했을 때 local minima인 점이 SGD에서는 극소값이 아닐 수 있게되어, local minima를 탈출할 수 있게 된다.

• 이것이 non-convex에서 SGD를 사용하는 이유이다.

• SGD는 경사하강법과 다르게 통통 튀지만, 데이터를 더 적게 사용하므로 더 빠르게 수렴가능하다.

• 하지만, Mini-Batch 사이즈가 너무 작으면 수렴하는데 경사하강법보다 더 오래 걸린다.

• 컴퓨터 메모리가 부족하여 경사하강법을 적용할 수 없을 수도 있기 때문에, 데이터 일부만 사용해 병렬적으로 처리할 수 있는 SGD가 하드웨어 관점에서도 더 효율적이다.

4. 기타 최적화 알고리즘

---

Refernces

---

• 강의: 경사하강법
• MSE
• 기타 최적화 알고리즘