선형 회귀(Linear Regression)와 경사하강법(Gradient Descent)

 

선형 회귀(Linear Regression)는 머신러닝의 가장 기본이 되는 알고리즘이다.
머신러닝은 기본적으로 훈련 데이터를 이용해 알고리즘을 학습시키고, 그 결과로 어떤 가설을 도출하는 것이다.
이 가설(또는 함수)을 가지고 새로운 input이 주어졌을 때, 그에 맞는 output을 예측하여 내놓는다.
다음 그림은 이러한 머신러닝의 메커니즘을 보여준다.

기본적인 머신러닝의 메커니즘

 

예를 들어 우리가 다음과 같은 데이터를 가지고 있다고 가정해보자.
충분히 많은 데이터만 있다면, 어떤 집의 면적과 침실의 개수 등과 같은 정보만 가지고 그 집이 얼마일지 예측하는 데 이용할 수 있다.

Size (sqft)	# Bedrooms	Price (1K$)
2,104	5	460
1,416	3	232
...	...	...

 

이때 이러한 가설(Hypothesis) `h`는 다음과 같은 식으로 나타낼 수 있다.
여기서 `x_1`은 면적, `x_2`는 침실의 개수를 의미한다고 하자.

$$h(x) = \theta_0 + \theta_1x_1 + \theta_2x_2$$

이 식을 좀 더 간단히 표현하기 위해 `\sum`로 묶으면 다음과 같다. (단, `x_0 = 1`)

$$h(x) = \sum_{j=0}^{2}\theta_jx_j$$

여기서 `x`는 각각 input data, 즉 feature를 의미하는데, feature의 개수는 보통 `n`으로 표기한다.
따라서 위 식에 따르면 feature가 두 개이므로 `n = 2`이다.

`\theta`는 학습 알고리즘(Learning Algorithm)의 매개변수(Parameter)를 의미한다.
궁극적으로 알고리즘이 목표하는 것이 바로 이 매개변수들의 최적 값을 찾는 것이다.
최적의 값이란 바로 `h(x)`가 훈련 데이터셋의 정답(Label) `y`, 이 예시에서는 집값(Price)과 가장 가깝도록 만드는 `\theta`를 말한다.

다시 말해, 만약 우리가 `m`개의 데이터를 가지고 있다면 모든 데이터에 대해 예측한 가격 `h(x)`과 실제 가격 `y`의 차이를 모두 더한 값을 최소로 만드는 파라미터 `\theta`를 찾아야 한다.
이는 수식으로 다음과 같이 나타낼 수 있는데, 이를 `\theta`에 대한 비용 함수(Cost Function)라고 부른다.

$$J(\theta) = \frac{1}{2}\sum_{i=1}^{m}\left (h(x^{(i)}) - y^{(i)} \right )^2$$

갑자기 `\frac{1}{2}`을 곱해주는 이유는 나중에 미분을 해야할 때 계산을 간단히 해주기 때문이다.
또 차이의 절대값도 아닌 제곱을 취하는 이유는 결과적으로 비용함수를 2차 함수로 만들어서 지역적 최소값(Local Minimum)과 같은 경우가 생기지 않도록 하기 위함이다.

 

이게 무슨 말인지, 본격적으로 비용 함수를 어떻게 최소화할 수 있는지를 통해 이해해보자.
이때 사용할 것은 경사하강법(Gradient Descent)이라는 알고리즘이다.
`\theta_0`와 `\theta_1`을 기준으로 `J(\theta)` 값을 다음과 같은 3차원 그래프로 나타내 보았다.
(물론 위에서 설명한 것처럼 우리는 비용함수를 2차 함수로 만들었기 때문에 이렇게 복잡한 형태가 될 리는 없다.)

다시 한 번 우리의 목표를 되새겨 보면, 이 울퉁불퉁한 그래프에서 가장 낮은 지점을 찾아 내려가서 그 위치에서의 `\theta_0, \theta_1`을 찾는 것이다.

 

우리가 위 그림에 보이는 언덕 중 파란 점에서 시작해 한 발자국씩 아래로 내려가고 있다고 상상해보자.
그 한 발자국(앞으로 스텝 step이라고 표현하겠다)을 수식으로 나타내면 다음과 같을 것이다.

$$\theta_j := \theta_j - \alpha \frac{\partial }{\partial \theta_j}J(\theta)$$

:= 는 파이썬 3.8부터 도입된 왈러스 연산자(Walrus Operator)로, 오른쪽 값을 왼쪽 변수에 할당하겠다는 의미이다.

`\alpha`는 학습률(Learning Rate)이라는 하이퍼파라미터를 가리킨다. 얼마나 크게 한 step을 뗄 것인지를 결정하는 매우 중요한 역할을 한다.
이 학습률을 너무 크게 잡을 경우 보폭이 너무 커서 최소값이 있는 지점을 지나칠 수 있고,
너무 작게 잡는다면 보폭이 너무 작아서 가장 낮은 지점까지는 내려가는 데에, 학습하는 데에 시간이 오래 걸린다.

https://ichi.pro/ko/choejeoghwa-algolijeum-ihae-53453022124445

 

이제 위 식에서 `J(\theta)`를 `\theta_j`에 대해 편미분한 값을 대입해서 정리하면 다음과 같다.

$$\theta_j := \theta_j - \alpha \sum_{i=1}^{m}(h(x^{(i)}) - y^{(i)})\cdot x^{(i)}_j$$

즉 오른쪽 항의 결과 값으로 `\theta_j`를 갱신하는 과정을 `n`번 반복하는 것이다. (`j = 1, 2, ..., n`)

그런데 여기서 우리가 간과하면 안 되는 것은 이 식이 단 한 번의 스텝을 계산하기 위한 것이라는 데 있다.
가중치(Weight) `\theta` 하나를 업데이트하기도 전에 `m` 개의 모든 데이터셋에 대한 계산이 필요한 것이다.

이 어마어마한 계산량에 대한 대안으로 제시된 것이 바로 확률적 경사하강법(Stochastic Gradient Descent)이다.
SGD에서는 `\theta` 하나를 업데이트하기 위해 모든 데이터셋에 대해 연산을 하는 것이 아니라, 각 데이터 row에 대해서 아래 계산식을 계산한다.

$$\theta_j := \theta_j - \alpha(h(x^{(i)}) - y^{(i)})\cdot x^{(i)}_j$$

그러니까 위 계산식이 update_theta라는 함수로 정의되어 있다고 가정할 때, 다음과 같은 for문을 실행하는 것이다.
데이터셋의 크기가 매우 큰 경우에는 SGD를 이용하는 것이 훨씬 빠르다는 장점이 있다.

for i in m[1:]:
	theta[i] = update_theta(theta[i])

https://pythonmachinelearning.pro/wp-content/uploads/2017/09/GD-v-SGD.png

 

사실 이렇게 복잡한 방법 외에도 오직 선형 회귀에만 적용할 수 있는 방법이 하나 있는데, 바로 정규 방정식(Normal Equation)이다.
만약 feature의 개수 `n`이 작다면 경사 하강법보다 이 정규 방정식을 이용해 `\theta`를 구하는 것이 좋다.
또 이 정규 방정식은 `\alpha`와 같은 하이퍼파라미터에 대해 고민하지 않아도 되고, 복잡한 계산을 반복하지 않아도 된다는 장점이 있다.
주어진 데이터를 행렬 `X`로 표현할 때, `\theta`를 구하기 위한 정규 방정식은 다음과 같다.

$$\theta = (X^T X)^{-1} X^Ty$$

이때 `(X^TX)^{-1}`는 행렬 `X^TX`의 역행렬을 의미한다.

 

아래 내용을 정리한 글입니다.

• Prof. Andrew Ng, Stanford University CS229: Machine Learning Lecture 2 (Autumn 2018)