4. The Hessian Matrix


  • 지금까지 우리는 backprop 기법을 이용하여 에러 함수에 대한 \( {\bf w} \) 1차 미분값을 계산할 수 있었다.
  • 이를 확장하여 2차 미분값인 Hessian 행렬을 계산하는 방법을 살펴보도록 하자.
  • 여기서 \( i, j \in \{ 1, …, W \} \) 이고 \( W \) 는 모든 weight 와 bias를 포함한다.
  • 이 때 각각의 2차 미분 값을 \( H_{ij} \) 로 표기하고 이것으로 만들어지는 행렬을 헤시안(Hessian) 행렬 \( {\bf H} \) 라고 정의한다.
  • 신경망에서 헤시안 행렬은 중요하게 여겨진다.
    • 일부 비선형 최적화 알고리즘에서 에러 곡면의 2차 미분 값을 사용한다.
    • 이미 학습이 완료된 신경망에 조금 변경된 데이터를 입력으로 주고 빠르게 재학습 시킬 때 사용된다.
    • ‘pruning’ 알고리즘의 일부로 least significant weights 를 식별할 때 헤시안 역행렬이 사용된다.
    • 베이지안 신경망을 위한 라플라스 근사식에서 중요한 역할을 차지한다. (5.7절 참고)
    • 설명이 너무 어려워서 이해가 안된다면 그냥 backprop 업데이트시 다양한 형태의 방식을 사용할 수 있고 이 때 헤시안 행렬을 이용하연 좋은 결과를 얻을 수 있다고만 이해하고 넘어가자.
  • 헤시안 행렬의 연산량은 매우 높다.
    • 신경망에 \( W \) 개의 weight 가 존재한다면 헤시안은 \( W \times W \) 행렬이 된다.
    • 따라서 연산량은 입력 샘플당 \( O(W^2) \) 이 필요하다.

5.4.1. 대각 근사 ( Diagonal approximation)

  • 헤시안 행렬을 사용하는 많은 경우에서 헤시안 행렬의 역행렬(inverse)을 이용하는 경우가 많다.
  • 이 때 정방 행렬인 헤시안 행렬의 역행렬이 존재하려면 (즉, invertible or nonsingular) \(det({\bf H})\) 의 값이 \(0\) 이 아니어야 한다.
  • 이 때 헤시안 행렬을 대각 근사하면 \(det({\bf H})\) 가 \(0\) 인 경우가 발생하지 않는다.
    • 즉, 대각만 남기고 다른 값들을 모두 0으로 치환
    • 대각 행렬의 경우 역행렬을 구할 수 있음이 보장된다.
  • 참고로 위의 식은 다음과 같이 전개하여 얻은 식이다.
  • 식(5.48)과 식(5.49)를 사용하여 식(5.79)의 오른쪽 항을 체인(chain) 형태로 전개할 수 있다.
  • 참고로 \(a_k\) 와 \(a_{k’}\) 는 동일한 레이어의 유닛을 의미한다. \(k\) 와 \(k’\)가 다른 경우를 모두 무시하면 다음 식을 얻게 된다.
    • 즉, 대각만 남기고 다른 요소들은 모두 삭제한다.
    • Becker & Le Cun (1989)
  • 이 때의 연산 비용은 \(O(W)\) 가 된다. (실제 헤시안 행렬은 \(O(W^2)\)임을 이미 확인했다.)
  • 게다가 연산도 쉬운데 backprop 에서 얻어진 에러 \( \delta \) 를 이용하여 \( \frac {\partial^2 E_n }{\partial a^2_j} \) 만 구하면 헤시한 행렬을 구할 수 있다.
  • 하지만 현실적으로 헤시안 행렬 자체는 대각행렬만으로 구성되는 경우는 거의 없다.
    • 따라서 헤시안 행렬의 대각 근사 자체를 잘 사용하지 않는다. (왜 다룬거야!)

5.4.2. 외적 근사 (Outer product approximation)

  • 회귀(regression) 문제로 돌아가 에러 함수를 잠시 꺼내와보자.
  • 이에 대한 헤시안 행렬은 다음과 같이 구할 수 있다.
  • 만약 충분한 데이터로 학습이 잘 이루어져서 네크워크 망의 출력값 \(y_n\) 가 \(t_n\) 와 매우 비슷한 값을 내어준다면 위의 식에서 2번째 텀은 생략 가능하다.
    • 물론 제대로 하려면 섹션 1.5.5 에서 다루었듯 출력 값의 조건부 평균을 사용해야 겠지만 일단 넘어가자.
    • 식(5.83)에서 두번째 텀을 생략한 식을 Levenberg-Marquardt 근사 또는 외적 근사(outer product approx.)라고 부른다.
    • 사실 헤시안 행렬 자체가 외적의 합으로 이루어진 행렬이다.
  • 여기서 \({\bf b_n} \equiv \nabla a_n = y_n\) 이다.
    • 회귀 문제에서는 마지막 레이어의 활성(activation) 함수가 Identity 함수이기 때문이다.
  • 이 근사법은 헤시안을 구하기 위해 오로지 1차 미분만을 요구하고 backprop 시 \(O(W)\) 에 값을 구할 수 있다.
  • 그리고 \(W\) 차원의 두 벡터를 외적할 때 \( O(W^2) \) 이 요구된다.

  • 로지스틱 시그모이드(logistic sigmoid) 활성 함수를 가지는 크로스 엔트로피(cross-entropy)를 사용하는 경우 근사식은 다음과 같이 된다.
  • 다중부류(multi-class)로도 쉽게 확장된다.

5.4.3. 헤시안 역행렬 (Inverse Hessian)

  • 헤시안을 응용하는 곳에서는 주로 헤시안 역행렬을 사용하는 경우가 많다. (물론 신경망에서도!!!)
  • 앞서 살펴보았던 외적 근사 기법을 통해 헤시안의 역행렬을 구하는 방법을 살펴볼 것이다.
  • 끝에 나오는 quasi-Newton 을 주의깊게 살펴보자.
  • 여기서 \( {\bf b_n} \equiv \nabla a_n \) 이다.
  • 각 데이터 n 으로부터 얻어지는 활성 함수의 출력값을 미분하여 얻을 수 있다.
  • 이제 이 값을 하나씩 갱신해나갈 수 있는 식을 작성해보자. (점진적 구축 방식)
  • 역 헤시안을 구하기 위해 이미 알려진 식을 사용한다.
  • 아래 식은 Woodbury identy 라는 식이다. (Appendix. C.7을 참고하자)
  • 이 식을 이용하여 헤시안 역행렬을 구할 수 있다.
  • 이제 식(5.87)과 식(5.88)을 활용해서 헤시안 역행렬을 전진적인 방식(incremental)으로 근사 할 수 있다.
  • 참고로 Woodbury identity 에 대응되는 식은 다음과 같다.

5.4.4 유한 차분법 (Finite differences)

  • 에러 함수를 한번 미분하는 방식과 마찬가지로 두번 미분해서 결과를 얻어낼 수 있다.
  • 이건 이미 앞에서 한번 살펴본 방식이다.
  • 다시 설명할 필요는 없을 듯 하고 식을 우선 보자.
  • symmetric 미분 방식으로 인해서 \( O(e) \) 대신 \( O(e^2) \) 를 사용하게 된다. (앞서 살펴보았다.)
  • 문제는 실제 연산량이 \( O(W^3) \) 이라는 것이다.
    • 따라서 이 방식을 도입하기가 현실적으로 어려운 점이 있다.
    • 대응 방법으로 다음과 같은 방식의 식을 사용할 수도 있다.
  • 이 식을 사용하면 \( O(W^2) \) 으로 연산이 가능하다.
  • 방식은 그냥 \( \frac{\partial E}{\partial w_{ji}} \) 를 함수로 생각하고 central 미분 방식을 도입. (식 (5.69)를 참고하자.)

5.4.5 제대로 헤시안 행렬을 구해보기 (Extract evaluation of the Hessian)

  • 지금까지는 헤시안 행렬을 근사적 방식으로 얻어내는 것을 소개했다.
  • 제대로 헤시안을 구하는 방법도 고려해보자.
    • 놀랍게도 backprop 방식을 확장해서 \( O(W^2) \) 에 이 계산을 수행할 수 있다.
    • 이를 확인해보기 위해 앞서 설명했던 내용들을 간단히 확장해보자.
  • 간단하게 모델을 구성하고 식을 아래와 같이 정의한다.
    • 사용되는 모델은 히든 레이어가 1개인 간단한 신경망을 사용한다.
    • 입력 레이어의 인덱스는 \(i\), 히든 레이어의 인덱스는 \(j\), 출력 레이어의 인덱스는 \(k\) 로 정의한다.
  • 일단 지금까지 다루었던 일차 미분방식에서는 \(\delta_k\) 만 backprop 대상으로 삼았는데,
  • 헤시안을 활용하기 위해서는 \(M_{kk’}\) 도 backprop 대상으로 삼아야 한다.

  • 일단 두번째 레이어 (즉, 마지막 레이어) 에서의 backprop 을 확인해본다.
  • 이어서 첫번째 레이어의 weight 값을 확인해보자.
  • 교재에서 기술된 것과 다르게 식을 좀 분리해서 썼다.
    • 사실 이 식의 전개 과정은 식(5.80)과 거의 같다.
  • 이차 미분을 사용하고 있으므로 각 레이어에 대한 weight 값도 필요하다.
    • 즉, 첫번째 레이어, 두번재 레이어 각각에 대해 한번씩 미분한 값.

헤시안을 이용한 빠른 곱 (Fast multiplication by the Hessian)

  • 헤시안 \(H\)를 응용하는 방법들은 대부분 헤시안 행렬 그 자체를 얻는 것보다 \(H\) 에 어떤 벡터를 곱에 얻는 값을 활용하는 경우가 많다.
  • 그리고 헤시안 \(H\) 계산의 시간 복잡도는 \(O(W^2)\) 이고 공간 복잡도도 \(O(W^2)\) 임을 이미 확인했다.
  • 실제 \(H\) 의 차원은 \(W \times W\) 이지만 실제 벡터 \(v\) 를 곱한 \(v^T\dot H\) 의 필요 차원은 \(W\) 이다.
  • 이제 \(O(W^2)\) 복잡도를 가지는 \(H\) 를 계산한 뒤 다시 \(v^T \dot H\) 를 계산하는 것이 아니라 바로 \(v^T\dot H\) 를 계산하는 방법을 살펴볼 것이다.
  • 일단 식을 먼저 보자.
  • 이 때 \(\nabla E\) 는 backprop 과정 중에 얻을 수 있다.