[DAY3] AI math 4. 경사하강법 -2

경사하강법으로 선형괴휘 계수 구하기

2022.01.19 - [부스트캠프 AI Tech 3기/이론 : U-stage] - [DAY3] AI math 2. 행렬이 뭐예요?

[DAY3] AI math 2. 행렬이 뭐예요?

의 맨 마지막을 보면 예측한 선형식의 값 $\hat{y}$과 원래 y값의 차이($\hat{y}-y$)를 최소화하는 것이 선형회귀의 방향이다.

$$\hat{y}=X\beta$$

이므로 선형회귀의 목적식은 $\parallel{y}-X\beta{\parallel}_2$ 이고,

목적식을 최소화해야하는 $\beta$를 찾아야 하기 때문에 목적식의 $\beta$로 미분해야 한다.

$$\nabla_{\beta}\parallel{y}-X\beta{\parallel}_2$$ 을 구하면 된다.

 

$\nabla_{\beta}\parallel{y}-X\beta{\parallel}_2$ 를 벡터로 펼쳐 보면

 

$$ ( \partial_{\beta_1}\parallel y-X \beta \parallel_2 , \dotsb , \partial_{\beta_d}\parallel y-X \beta \parallel_2 ) $$

와 같이 각각의 $\beta$ 에 대해서 편미분을 한 것이 들어가게 된다.

그렇다면 $ \partial_{\beta_k}\parallel y-X \beta \parallel_2 $ 와 같은 편미분은 어떻게 할까

편미분 계산 과정을 나중에 꼭 시도해봐야겠다 ㅠㅠ

 

그래서 이 편미분을 각 성분에 대해 적용해서 gradient vector를 구할 수 있다

 

그러면

$\nabla_{\beta}\parallel{y}-X\beta{\parallel}_2$

$= ( \partial_{\beta_1}\parallel y-X \beta \parallel_2 , \dotsb , \partial_{\beta_d}\parallel y-X \beta \parallel_2 ) $

이 성분들에 하나씩 편미분을 하면

$ = ( -\frac{X^{T}_1 (y-X\beta) }{n \parallel{y}-X\beta \parallel_2},-\frac{X^{T}_2 (y-X\beta) }{n \parallel{y}-X\beta \parallel_2}, \dotsb, -\frac{X^{T}_d (y-X\beta) }{n \parallel{y}-X\beta \parallel_2})$

이렇게 되고, 모든 것을 합쳐서 행렬로 표현하면

$= -\frac{X^{T} (y-X\beta) }{n \parallel{y}-X\beta \parallel_2}$

와 같이 전치행렬로 나타낼 수 있다.

 

경사하강법 알고리즘 적용

드디어 구한 gradient vector를 경사하강법에 적용하면

$$ \beta^{(t+1)} \leftarrow \beta^{t} - \lambda \nabla_{\beta}\parallel{y}-X\beta^{(t)}{\parallel}$$

$\beta$ 벡터에 gradient vector를 빼주어 함숫갑이 줄어드는 방향으로 업데이트한 후 새로운 $\beta$ 벡터를 만드는 것이다.

$\lambda$ 람다는 학습률 (learning rate)이다. 학습률로 수렴속도를 결정할 수 있다. 

 

위의 식에 gradient vector를 대입하면

$$ \beta^{(t+1)} \leftarrow \beta^{t} + \frac{\lambda}{n} \frac{X^T (y - X\beta^{(t)} )}{\parallel{y} -X\beta^{(t)}\parallel} $$

gradient vector가 음수라서 +부호로 바뀌게 된다.

 

 

 

L2 norm을 계산할 때

각 요소의 제곱을 더해서 마지막에 제곱근을 취해주었었는데, gradient vector를 좀 더 간단하게 계산하기 위해서는 제곱근을 취하지 않아도 상관없다. 그래도 결과는 같고 식이 좀 더 간단해진다.

 

$$ \nabla_{\beta}\parallel y-X\beta\parallel_2^{2} = (\partial_{\beta_{1}} \parallel y-X\beta\parallel_2^{2}, \dotsb, \partial_{\beta_{d}} \parallel y-X\beta\parallel_2^{2}) $$

$$=-\frac{2}{n}X^T (y-X\beta)$$

 

이렇게 정리 된다.

결과를 경사하강법 알고리즘에 넣으면 다음과 같다.

 

$$ \beta^{(t+1)} \leftarrow \beta^{t} + \frac{2\lambda}{n}X^T (y - X\beta^{(t)}) $$

 

경사하강법 사용

• 학습률과 학습횟수를 적절히 선택해야 한다.
  너무 적으면 학습이 덜 된다.
• 볼록함수인 경우에는 항상 최소점을 향하게 보장된다.
  특히 선형회귀의 경우 L2 norm으로 만든 목적함수는 볼록함수이기 때문에 수렴이 보장된다.
• 비선형회귀의 경우는 볼록하지 않으므로(non convex) 수렴이 보장되지는 않는다.
  볼록한 부분이 여러군데 있을 수 있다.

확률적 경사하강법 SGD : Stochastic Gradient Descent

모든 데이터를 사용하지 않고 데이터를 한 개만 활용하여 업데이트한다.

한 개가 아닌 일부를 사용하는 것은 Mini batch SGD라고 한다. 

 

보통 1개만 사용하면 비효율적이어서 그냥 SGD라고 쓰여 있어도 mini batch 인 경우가 많다.

non-convex목적식을 SGD로 최적화가 가능하다.

딥러닝의 경우 SGD가 모든 데이터를 사용하는 경사하강법보다 실증적으로 더 낫다.

또한 일부를 가지고 연산하기 때문에 자원에 대해서 효율적이다.

 

매번 배치가 바뀌기 때문에 목적식 모양이 일정하지 않고 계속해서 바뀌게 된다. 그래서 non-convex함수에서도 극솟점이 아닌 점을 탈출할 수 있다.

경사하강법

 

SGD

하지만 방향은 비슷하게 흘러간다. 정확하진 않지만 빠르게 정답으로 다가간다.

또한 미니배치의 크기에 따라서 ex)100,30,10 속도가 다를 수  있으니 조절이 필요하다.

 

또한 하드웨어에 큰 데이터를 모두 올리기에는 공간이 부족할 수 있기 때문에 SGD를 더 사용한다.