[U] Day 07 - 경사하강법

(3강) 경사하강법 I

경사하강법이란?

미분이란?

미분과 경사하강법

변수가 2개 이상인 벡터의 경우

(4강) 경사하강법 II

경사하강법을 통한 선형회귀분석 개요

목적식과 $\nabla_{\beta}$

$\beta$의 업데이트

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

경사하강법에 대한 고민

확률적 경사하강법

---

(3강) 경사하강법 I

💡

미분의 개념과 그래디언트 벡터에 대해 알아본다.

경사하강법이란?

경사하강법(Gradient Descent)은 기계학습에서 자주 사용되는 최적화 방법이다. 데이터에 대해 오차를 최소화하는 Parameter를 구할 때 사용되며, 이를 이해하기 위해선 미분에 대해서 먼저 알아야 한다.

미분이란?

미분은 영어로 Differentiation이다. 말 그대로, 변수의 움직임에 따라 변화하는 함수값을 측정할 때 사용되는 개념이다. 함수 내에서 미분을 사용하면 변수의 특정 값에서의 기울기를 구할 수 있다. $f(x) = x^2 + 2x + 3$의 미분은 $f'(x) = 2x + 2$이다. $x$의 값에 따라 기울기는 양수가 될 수도, 음수가 될 수도 있다.

미분의 계산 예시

Python에서는 sympy Module을 통해 미분을 수행할 수 있다.

미분과 경사하강법

미분을 통해 구한 값. 즉, 기울기는 변수의 증감에 따른 함수값의 증감을 알려준다. 이 때, 어떤 경우이든 $x$에 $f'(x)$값을 더하면 $f(x)$는 증가하고, 빼면 감소한다. $f'(x)$의 값이 양수이든 음수이든 어떤 경우에도 동일하다.

만약 $f(x)$의 값을 증가시시키고 싶다면, $x$에 $f'(x)$를 더하면 된다. $f'(x) = 0$인 지점에 도달하게 되면, 극대값에 해당하는 $x$를 찾은 것이다. 이를 경사상승법이라고 칭한다. 우리는 극소값에 해당하는 $x$의 값을 찾기를 바라기 때문에, $f'(x)=0$인 지점까지 $x$에서 $f'(x)$의 값을 뺀다. 기울기를 따라 계속 하강하기 때문에 경사하강법, Gradient descent라고 한다.

경사 하강법의 시각화 예시

단, Code 상에서는 0의 값 대신 일정 수치에 해당하는 epsilon을 지정할 것인데, 이는 컴퓨터 상에서 완전한 0의 값을 갖기는 매우 어렵기 때문이다. 경사하강법 알고리즘은 다음과 같이 구현할 수 있다.

경사하강법의 Pseudo Code

$x^2 + 2x + 3$ 함수에 경사하강법을 적용해 최소값과 x값을 찾는 예시 코드는 다음과 같다.

경사하강법을 실제 수식에 적용하는 Code의 예시

변수가 2개 이상인 벡터의 경우

변수가 1개인 경우 위와 같이 통미분을 통해 경사하강법을 쓸 수 있다. 하지만, 변수의 갯수가 늘어나는 경우에는 이와 같은 방법을 쓸 수 없다. 변수의 수 만큼 차원이 늘어나기 때문에, 공간 상에서의 움직임을 결정해야하기 때문이다.

변수가 2개 이상인 경우 즉, 벡터인 경우에는 편미분을 통해 Gradient Vector를 구해야한다. $f(x,y) = x^2 + 2xy + 3 + cos(x+2y)$일 때, 각 $x$와 $y$에 대한 편미분을 구하면 다음과 같다.

$x$에 대한 편미분은 $\delta_xf(x,y) = 2x + 2y - sin(x+2y)$이다.

$y$에 대한 편미분은 $\delta_yf(x,y) = 2x - sin(x+2y)$이다.

위 식을 Python Code로도 구현할 수 있다.

벡터의 편미분 예시

각 변수에 대한 편미분 값을 요소로 갖는 벡터가 Gradient Vector이며, 공간 상에서 특정 값의 기울기가 된다. 표기는 $\nabla{f} = (\delta_xf, \delta_yf)$와 같다. 이를 일반화하여 표현하면, $x$와 $y$대신 $(x\_1, x\_2, ..., x\_d)$로 표현할 수 있다.

편미분 값을 요소로 갖는 Gradient Vector의 예시

$\nabla{f}$를 통해 모든 변수 벡터 $\mathbf{x}=(x\_1, x\_2, ..., x\_d)$를 동시에 업데이트 할 수 있다. 단변수인 경우에는 기울기를 바로 사용할 수 있었으나, 벡터는 그 자체로 크기를 의미하지 않는다. 이를 적용하기 위해 우리는 벡터의 크기를 의미하는 norm을 구해야한다. 최종적으로 업데이트에 대한 식은 다음과 같다. $\mathbf{x}^{(t+1)} \leftarrow \mathbf{x}^{(t)}-\nabla{f}$ Python Code로는 다음과 같다.

단변수에 대한 경사하강법과의 차이점은 Norm에 대한 계산 뿐이다.

$x^2 + 2xy + 2$ 함수에 경사하강법을 적용한 예시 코드는 다음과 같다.

벡터에 대해 경사하강법을 적용한 코드의 예시

---

(4강) 경사하강법 II

💡

경사하강법 기반의 선형회귀 알고리즘과 확률적 경사하강법에 대해 알아본다.

경사하강법을 통한 선형회귀분석 개요

행렬 $\mathbf{X}$에 $m$개의 변수와 $n$개의 샘플이 있고, 각 샘플에 대한 결과값인 $\mathbf{y}$가 있는 상태를 가정하자. 이 때, $\mathbf{X}\beta \approx \mathbf{y}$를 만족하는 $\beta$를 찾고자 하는 것이 선형회귀분석이다.

하지만, 어떤 $\beta$도 이 등호를 만족시킬 수는 없으므로, 우리는 목적함수를 설정한다. 목적함수는 L2 Norm을 최소화하는 것으로 한다.

$\mathbf{X}\beta$는 $\mathbf{y}$를 추정한다는 의미에서 $\hat{\mathbf{y}}$으로 치환할 수 있으므로, 목적식은 다음과 같이 정리할 수 있다. $min_\beta||\mathbf{y} - \hat{\mathbf{y}}||_2$

모든 $y$를 만족시킬 수 없기 때문에, L2 Norm을 최소화하는 $\beta$를 찾는다.

목적식과 $\nabla_{\beta}$

위 목적식을 따라 $\beta$를 업데이트 하기 위해선 $\beta$에 대한 gradient vector를 구해야 한다. 목적식을 최소화하고자 하며, 이를 위한 기울기는 다음과 같다. $\nabla_{\beta}||\mathbf{y} - \hat{\mathbf{y}}||_2$ 위 수식은 곧, $\nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta||_2$를 의미 한다. 이를 전개하면 다음과 같다. $\nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta||_2=(\delta_{\beta\_1}||\mathbf{y} - \mathbf{X}\beta||\_2, ..., \delta_{\beta\_k}||\mathbf{y} - \mathbf{X}\beta||\_2)$

위 식에서 $k$번째 $\beta$에 대한 미분값을 확인하면 다음과 같다. $δ_{β_{k}}||y−Xβ||2=δ_{β_k}\{\frac{1}{n}∑^n_{i=1}(y_i−∑^d_{j=1}X_{ij}β_j)^2\}^\frac{1}{2}$

이에 대한 값을 구하면 다음과 같다. $(-\frac{\mathbf{X}_{k}^{T}(\mathbf{y} - \mathbf{X}\beta)}{n||\mathbf{y} - \mathbf{X}\beta||_2})$

이를 모든 $k$ 즉, $\beta$에 대한 값으로 바꾸면 다음과 같은 식이 완성된다. $\nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta||_2 = -\frac{\mathbf{X}^{T}(\mathbf{y} - \mathbf{X}\beta)}{n||\mathbf{y} - \mathbf{X}\beta||_2}$

Gradient Vector를 구하는 식의 전개

$\beta$의 업데이트

목적식을 최소화하는 업데이트 식에, 위를 통해 도출된 식을 대입하면 다음과 같다. $\beta^{(t+1)} \leftarrow \beta^{(t)} - \lambda\nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta^{(t)}||_2$

전체 식의 전개과정은 다음과 같다.

업데이트 공식이 얻어지기 까지의 과정

위의 목적식은 제곱근을 추가한 RMSE이나, MSE의 형태로 계산하여도 동일한 목적을 달성할 수 있다. MSE를 사용하면 식이 간결해지는 효과를 얻을 수 있다.

목적함수를 MSE로 계산했을 경우의 수식

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

이를 Python code로 나타내면 다음과 같이 나타낼 수 있다. 학습종료 조건을 gradient vector의 norm값으로 정할수도 있으나, 근래에는 학습 횟수와 같은 종료조건을 사용하기도 한다. (이와 같은 경우 T, lr 모두 적절한 값을 지정해야 한다.)

선형회귀에 경사하강법을 적용하는 Pseudo Code의 예시

$\beta$의 참 값이 1, 2, 3인 선형회귀 문제에 경사하강법을 적용하는 예시는 다음과 같다.

예제를 계산하는 Python Code의 예시

경사하강법에 대한 고민

위의 알고리즘은 모든 상황에서 작동하지는 않는다. 먼저, 이는 모든 지점에서 미분이 가능해야하며, error에 대한 함수가 볼록한 형태를 가져야 한다. 또한, 비선형적인 모양으로 지역최소값이 있는 경우 최소값으로 수렴한다고 보장할 수 없다.

경사하강법의 약점에 대한 설명

이와 같은 약점을 해소하기 위해 확률적 경사하강법(Stochastic Gradient Descent) 를 사용한다.

확률적 경사하강법

확률적 경사하강법은 매 업데이트마다 일부의 데이터만 사용하는 기법이다. 이를 통해 얻을 수 있는 장점은 다음과 같다.

• 연산이 효율적이다. (모든 데이터에 대한 연산을 하지 않기 때문이다.)

• 지역최소값을 탈출할 수 있다. (매 번 데이터가 달라져서 목적식이 변하기 때문이다.)

• 훨씬 빠르게 최소점을 찾는다. (연산이 효율적이기 때문이다.)

• 병렬연산이 가능하다. (업데이트 동안 데이터 전처리 및 계산 준비를 할 수 있다.)

확률적 경사하강법의 수식

Uploaded by Notion2Tistory v1.1.0