[머신러닝] Normal Equation vs Gradient Descent Algorithm(경사 하강 알고리즘) in 선형 회귀(linear regression)

시작하며

경사 하강 알고리즘(Gradient Descent Algorithm)은 선형 회귀(Linear Regression)에서 비용 함수(Cost Function)를 최소화하는 θ를 찾기 위한 방법 중 하나입니다.

이번 포스팅에선 이러한 θ를 찾는 또 다른 방법인 Normal Equation 에 대해 알아보고 경사 하강 알고리즘과의 차이점까지 알아보겠습니다.

---

Normal Equation

Gradient Descent Algorithm은 미분 값을 이용하여 반복적으로 θ를 갱신하면서 최적의 θ를 찾게 됩니다.

여기서 반복적인 연산이 이뤄진다는 점이 경사 하강 알고리즘의 단점 이라고 할 수 있습니다. 하지만 Normal Eqution을 이용하면 한번에 θ를 구할 수 있습니다.

우선 Normal Equation은 데이터가 실수일 때만 적용이 가능하며, 데이터가 n+1차원일 때 비용함수 J를 모든 θ에 대해 편미분 하여 구하여 한번의 연산으로 θ를 알아내는 것입니다.

이것이 Normal Equation으로 우리가 원하는 θ를 구하는 공식이고 아래는 증명입니다. 행렬에 대한 이해가 부족하신 분은 아래 포스팅을 통해 개념을 공부하시고 오시면 좋습니다.

---

[머신러닝] 머신러닝 공부하기 전 꼭 알아야 할 행렬(Matreix)과 벡터(Vector)
https://box-world.tistory.com/8

---

위 데이터를 예시로 들겠습니다. 우선 주어진 데이터를 matrix로 바꿔 줍니다.

위는 4개의 feature를 가지는 데이터이며 x0는 따로 추가해준 행렬로 그냥 상수라고 생각하시면 됩니다.

 

다음으로 각각의 x vector를 역행렬 연산(transpose)하여 X^t를 구합니다. 이는 공식에 보이는대로 X^t와 y를 곱하기 위함입니다. 이때 feature의 갯수가 많아질수록 X^t를 구하는데 많은 시간을 요하고 속도는 O(n^3) 입니다.

게다가 Gradient Descent algorithm는 데이터 Scaling이 필요했지만, Normal Equation의 경우 한번에 결과값을 구하기 때문에 이러한 Scaling이 필요하지 않습니다.

---

Gradient descent algorithm vs Normal Equation

이제 두 방법의 차이점을 알아보겠습니다.

1) Gradient Descent algorithm은 적절한 learning rate 를 찾아야 하며, 반복적인 연산 이 필요합니다. 이에 비해 Normal Equation은 알파 값이 없이 한번의 연산으로 θ를 찾을 수 있습니다.

2) 위에서 언급했듯 Normal Equation에서는 X^t를 구하는데 있어서 feature의 갯수에 많은 영향을 받습니다. 그래서 보통 feature가 10000개 이하 라면 Normal Equation이 훨씬 좋은 성능을 보이지만, 그 이상 이라면 Gradient Descent algorithm이 좋습니다.

---

Normal Equation의 문제점

Normal Equation의 핵심은 결국 역행렬 X^t를 계산하는 것 인데, 다음에서 행렬 X가 역행렬이 존재하지 않는 비가역행렬(non-invertible matrix)인 두가지 경우를 설명드리겠습니다.

1) 불필요한 feature를 가지고 있는 경우 : 두개의 feature가 서로 유사한 경우 하나를 지워야 합니다.

2) 보유한 데이터의 크기보다 feature의 수가 많은 경우 ( M(데이터) <= n(feature) ) : -> 이때 feature를 일부 지우거나 다음에 배울 regularzation을 적용해야 합니다.

---

요약

• Gradient descent

  • 장점
    1) 데이터의 Feature의 갯수에 영향을 받지 않는다.

  • 단점
    1) 적절한 learning rate 설정 필요
    2) 반복 연산이 필요하다.

#

• Normal Equation

  • 장점
    1) learning rate 불필요
    2) 한번에 계산된다.

  • 단점
    1) 데이터의 Feature가 10000개 이상 넘어가면 효율성이 매우 떨어진다.