2-2 Computing Parameters Analytically

특정 선형회귀 문제에서 최적의 파라미터 θ를 구하는 또 다른 알고리즘 Normal equation에 대해 알아본다.

Gradient descent는 iteration을 여러 번 하여 최소값을 찾아 나가지만 Normal equation은 θ를 분석적으로 구하기 때문에 알고리즘을 반복할 필요 없이 한번에 최적값을 구할 수 있다.

θ가 실수일 때, 우리는 미분을 통해 기울기가 0이 되는 지점이 cost가 최소가 되는 위치라는 걸 알 수 있다.

이와 반대로 θ가 실수가 아닌 n+1차원의 파라미터 벡터인 경우 편미분을 이용하여 각 파라미터 θ에 대해 미분을 하여 0이 되는 지점을 찾아나가면 cost function을 최소화 할 수 있다. 하지만 파라미터 벡터의 차원이 매우 큰 경우 미분을 통해 일일이 계산하면 계산량이 너무 커지게 된다.

따라서 미분을 통해 계산하지 않고 다른 방법을 이용한다.

위와 같은 data set을 이용할 것이다. 이 data set은 4개의 feature가 존재한다.

이제 왼쪽에 x_0라는 feature를 하나 추가하고 그 값을 모두 1로 설정한다.

그런 다음 X라는 행렬을 만들어 feature 정보를 모두 가져온다. 마찬가지로 y값도 열벡터로 만들어준다.

우리는 m x (n+1) 차원의 행렬 X와, m차원 벡터 y를 만들었다.

이제 행렬 X와 벡터 y를 가지고

이 식을 계산하면 cost function이 최소화된 θ 값을 구할 수 있게 된다.

해당 예제를 좀 더 일반화해보자

m개의 training example이 있고 n개의 feature가 있다.

따라서 x^(i)는 n+1차원의 벡터로 나타낼 수 있다.

 이제 위에서 했던 것처럼 행렬 X를 만들어본다. 이러한 행렬 X를 design matrix라고도 한다.

X를 만드는 방법은 각 train example의 벡터를 transpose하여 X의 각 행으로 집어넣는다.

첫번째 feature 벡터의 transpose된 것이 X의 첫번째 행으로 들어간다. 따라서 X는 m x n+1 차원의 행렬이 된다.

 

아래의 예는 feature가 하나 있을 때 X와 y를 행렬과 벡터로 만들어본 것이다.

그리고 이렇게 만들어진 X와 y를 가지고 아까 했던 것처럼 아래 식대로 θ를 구한다.

우리는 X와 y를 만들어서 위 식을 이용하여 cost값이 최소화된 최적의 θ를 한 번에 구할 수 있다.

또한 이렇게 normal equation을 사용하면 feature scaling을 해주지 않아도 된다는 장점이 있다.

그럼 normal equation이 gradient descent보다 더 좋은 것인가?

두 알고리즘을 비교해보고 언제 어떤 것을 사용해야 하는지 알아보자

우선 gradient descent의 단점은 learning rate를 결정해줘야 한다는 것이다. 적절한 learning rate를 찾는 것도 쉽지 않은 문제이며 cost function의 최소값을 찾기 위해 알고리즘을 여러 번 반복해야 한다는 문제도 있다. 이와 반대로 normal equation은 learning rate를 정할 필요가 없으며 수렴이 잘 됐는 지 확인하는 작업도 없고 알고리즘을 여러 번 반복할 필요 없이 그저 한번 실행하면 된다. 그래서 심플하면서 구현하기도 간단하다.

그럼 normal equation과 비교했을 때 gradient descent의 장점은 무엇일까?

Gradient descent는 feature가 많을 때 효과적이다. 우리가 제대로 파악하기도 힘들만큼 수백만 수천만개의 feature를 다루어야 할지라도 gradient descent는 잘 작동할 것이다. 이와 반대로 feature가 굉장히 많을 때 normal equation은 최적의 파라미터 θ를 구하기 위한 계산이 오래 걸린다는 단점이 있다.

우리는 normal equation을 사용할 때 X'X의 역행렬을 구해야 했다.

만약 n개의 feature를 사용한다면 X'X는 n x n 행렬이 되며 이때 역행렬을 구하는데 걸리는 시간은 O(n^3)이 걸리게 된다.

Feature가 많으면 많을 수록 normal equation은 훨씬 느려지게 된다.

그럼 feature 수가 작고 크다는 기준을 어떻게 봐야 할까?

요즘 시대의 컴퓨터로 n이 100 혹은 1000이어도 역행렬을 구하는데 오래 걸리지 않는다.

N이 10,000개 이상이면 역행렬을 구하는데 좀 걸릴 것이고 이보다 더 많은 feature를 사용해야 한다면 훨씬 더 오래 걸릴 것이다. 이러한 경우엔 gradient descent를 사용하면 된다. 정확히 몇 개일 때 gradient descent를 사용하고 몇 개일 때 normal equation을 사용해야 한다는 rule은 없지만 교수님은 보통 1만개 정도가 넘어가면 gradient descent를 사용하거나 다른 알고리즘을 고려한다고 하신다.

물론 feature 수가 많지 않다면 normal equation을 사용하는 것이 효과적일 것이다.

결과적으로 어떤 특정 문제에 더 적합한 알고리즘이 있을 것이고 우리는 그것을 feature의 수를 보고 장단점을 비교하였다.

이 외에도 다른 알고리즘들이 많이 있으니까 많이 배워 놓으면 내가 해결해야 하는 문제에 맞는 알고리즘을 잘 선택할 수 있을 것이다.

Normal equation을 사용할 때 역행렬이 없는 경우에 대해서 알아본다.

θ를 계산할 때 (X'X)의 역행렬을 구하게 되는데 이때 역행렬이 존재하지 않으면 어떻게 될까?

모든 행렬이 역행렬을 가지고 있는 것은 아니기 때문에 이런 생각을 충분히 해볼 수 있다.

(역행렬이 없는 행렬을 non-invertible matrix(비가역행렬), singular(특이행렬) 혹은 degenerate 행렬이라고 한다)

 

역행렬이 없는 경우는 거의 없고 Octave에서 θ를 구하기 위해 역행렬을 구할 때 inv나 pinv라는 함수를 사용한다.

Pinv는 pseudo-inverse라는 뜻이며 만약 역행렬이 존재하지 않더라도 올바른 값으로 계산될 수 있게 해준다고 한다.

(X'X)의 역행렬이 없는 경우는 대체로 두 가지 경우가 있다.

첫번째 원인은 문제에서 불필요한 feature를 가지고 있는 경우다.

집의 크기를 나타내는 x_1, x_2 두 개의 feature가 있다. 두 feature는 사이즈를 나타내는 단위만 다를 뿐이지 같은 feature라고 봐도 무방하다.

1m가 3.28feet이기 때문에 feet^2와 m^2사이의 관계에 따라 x_1 = (3.28)^2 * x_2라는 관계식을 가지게 된다.

두 feature가 서로 관련이 있고 이와 같은 선형방정식으로 나타낼 수 있으면 역행렬이 없다고 증명된다.

역행렬이 없는 두 번째 원인은 너무 많은 feature를 가지고 학습 알고리즘을 사용할 때이다.

구체적으로 train sample보다 feature의 수가 더 많은 경우를 뜻한다.

만약 train sample m이 10이고 feature n이 100이라면 파라미터 벡터 θ는 n+1차원의 벡터가 된다.

이때 10개의 training example을 가지고 101개의 파라미터를 표현하려고 하는 것은 가끔은 돌아갈 수도 있지만 문제가 생길 수도 있다.

이처럼 data가 충분하지 않은 것은 분명히 문제가 된다. 이렇게 m이 n보다 작은 경우 불필요한 feature를 몇 개 없애거나 regularization을 사용한다.

다시 정리하면 역행렬이 없는 경우 feature를 잘 분석하여 불필요한 feature가 없는지 확인하여 종속성이 있는 두 개의 feature 중 하나를 지우는 것이다.

이런 식으로 불필요한 게 있으면 없어질 때까지 feature를 지우고 불필요한 feature가 없다면 feature가 너무 많은 것은 아닌지 확인하여 굳이 없어도 되는 feature를 지우거나 regularization을 사용하면 된다.