(머신러닝) 5 - Normal Equation

오늘은 Normal Equation 이라는 tiral and error 보다는 analytic한 방법을 통해서 hypothesis function을 구하는 법을 알아보겠다.

먼저, 기본적인 idea는 고등 미적분의 local minimum에서의 미분계수가 0이라는 사실에 근거한다.

 

포물선의 최소값에서는 함수 f의 theta에 대한 미분계수가 0이다. 이 사실을 cost function에 적용하여 cost function의 최소값에서의 $$\theta$$를 구하는 것이다. 하지만 보통 cost function은 2개 이상의 feature와 parameter가 있기때문에 vector와 matrix 형태의 선형대수학으로 풀어야한다.

$$\triangledown J({ \theta })=(\frac { \partial J }{ \partial { \theta }_{ 0 } } , \frac { \partial J }{ \partial { \theta }_{ 1 } } , \frac { \partial J }{ \partial { \theta }_{ 2 } } , \cdot \cdot \cdot , \frac { \partial J }{ \partial { \theta }_{ n } } )=(0, 0, 0, \cdot \cdot \cdot , 0)$$

$$J(\theta )=\frac { 1 }{ 2m } { (X\theta -y) }^{ T }(X\theta -y)$$ 공식을 위의 방정식에 넣고 정리하면 다음과 같은 결과가 나온다.

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

이 θ는 정확히 기울기가 0이 되게하는, 즉 J(θ)가 최소일 때의 θ이다.

 

normal equation을 사용하면 귀찮게 learning rate를 찾아가며 결정해야 할 필요도 없고 gradient descent의 반복적인 iteration도 할 필요가 없다. 하지만 normal equation은 단점도 가지고 있다. X는 m×n(m = #training data set, n = #feature) 행렬이기때문에 위의 식에서 (XTX)는 n × n 행렬이 된다. 따라서 n이 매우 크다면 이 행렬을 계산하기에는 컴퓨터에도 벅차기에 느린 작업이 될 것이다. 요즘 컴퓨터로는 10,000 × 10,000 행렬 정도는 충분히 수월하게 계산이 된다. 하지만 n이 100,000 혹은 1,000,000이나 그 이상이라면 이야기는 달라진다.

얼핏 들으면 gradient descent는 잘 쓸 일이 없어보이지만 그렇지 않다. feature나 parameter가 매우 많은경우 Normal Equation은 매우 높은 계산비용이 들기 때문에 잘 맞지 않는다.

 

※$$\mathbf{(X^{T}X)^{-1}}$$ 가 존재하지 않는다면?

만약 X'(X transpose이다.)와 X의 곱인 X’X가 역행렬을 가지지 않는다면? 선형대수학에서 배웠다면 알겠지만 역행렬을 가지지 않는(non-invertible) 행렬이 있고 이를 degenerate 혹은 singular 하다고 한다. 모든 행렬에 역행렬이 있는 것은 아니다. 가장 대표적인 case로 두 개 이상의 row 나 column이 linearly dependent하다면 이 행렬은 역행렬이 존재하지 않는다. 가령 집값을 예측해주는 프로그램에서 x_1 = feet단위로 표현된 집의 크기이고 x_2는 m단위의 집의 크기라면 모든 training set 행렬 X에서 x_2 column은 x_1 column의 값에 단순히 3.28을 곱한 값이기 때문이다.(1m = 3.28feet)

 

X’X가 non-invertible하여 feature의 수를 줄이고 싶은 경우에는 여러가지 dimensionality reduction 방법이 있다. 대표적으로 PCA와 LDA 등이 있는데, 이후에 다룰 것이다.

 

사실 cost function의 minimum을 구하는 상황에서 X’X의 역행렬이 존재하지 않는 경우는 거의 없다. 그리고 있다고 하더라도 거의 오차가 0에 가깝게 근사적으로 계산할 수 있다. octave의 pinv 함수를 이용한다면 말이다. octave에는 inv 함수와 pinv 함수가 있는데 inv는 기술적으로 일반적인 역행렬(inverse) 계산이고 pinv는 pseudo inverse를 계산해준다.