4. The Hessian Matrix

지금까지 우리는 backprop 기법을 이용하여 에러 함수에 대한 $ {\bf w} $ 1차 미분값을 계산할 수 있었다.
이를 확장하여 2차 미분값인 Hessian 행렬을 계산하는 방법을 살펴보도록 하자.

$\frac{\partial^2 E}{\partial w_{ji} \partial w_{lk} } \qquad{(5.78)}$

여기서 $ 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으로 치환
- 대각 행렬의 경우 역행렬을 구할 수 있음이 보장된다.

$\frac{\partial^2 E_n}{\partial w^2_{ji}} = \frac{\partial^2 E_n}{\partial a^2_j}z^2_i \qquad{(5.79)}$

참고로 위의 식은 다음과 같이 전개하여 얻은 식이다.

$\frac{\partial^2 E_n}{\partial w^2_{ji}} = \frac{\partial^2 E_n}{\partial a^2_{j}} \frac{\partial a^2_{j} }{\partial w^2_{ji}} = \frac{\partial^2 E_n}{\partial a^2_j}z^2_i$

식(5.48)과 식(5.49)를 사용하여 식(5.79)의 오른쪽 항을 체인(chain) 형태로 전개할 수 있다.

$\frac{\partial^2 E_n}{\partial a^2_j} = h'(a_j)^2\sum_k\sum_{k'} w_{kj}w_{k'j}\frac{\partial^2 E_n}{\partial{a_k} \partial{a_{k'}} } + h''(a_j)\sum_k w_{kj}\frac{\partial E_n}{\partial a_k} \qquad{(5.80)}$

참고로 $a_k$ 와 $a_{k’}$ 는 동일한 레이어의 유닛을 의미한다. $k$ 와 $k’$가 다른 경우를 모두 무시하면 다음 식을 얻게 된다.
- 즉, 대각만 남기고 다른 요소들은 모두 삭제한다.
- Becker & Le Cun (1989)

$\frac{\partial^2 E_n}{\partial a^2_j} = h'(a_j)^2\sum_k w^2_{kj}\frac{\partial^2 E_n}{a^2_k} + h''(a_j)\sum_k w_{kj}\frac{\partial E_n}{\partial a_k} \qquad{(5.81)}$

이 때의 연산 비용은 $O(W)$ 가 된다. (실제 헤시안 행렬은 $O(W^2)$임을 이미 확인했다.)
게다가 연산도 쉬운데 backprop 에서 얻어진 에러 $ \delta $ 를 이용하여 $ \frac {\partial^2 E_n }{\partial a^2_j} $ 만 구하면 헤시한 행렬을 구할 수 있다.
하지만 현실적으로 헤시안 행렬 자체는 대각행렬만으로 구성되는 경우는 거의 없다.
- 따라서 헤시안 행렬의 대각 근사 자체를 잘 사용하지 않는다. (왜 다룬거야!)

5.4.2. 외적 근사 (Outer product approximation)

회귀(regression) 문제로 돌아가 에러 함수를 잠시 꺼내와보자.

$E = \frac{1}{2} \sum_{n=1}^N (y_n - t_n)^2 \qquad{(5.82)}$

이에 대한 헤시안 행렬은 다음과 같이 구할 수 있다.

${\bf H} = \nabla \nabla E = \sum_{n=1}^N \nabla y_n (\nabla y_n)^T + \sum_{n=1}^N(y_n - t_n)\nabla\nabla y_n \qquad{(5.83)}$

만약 충분한 데이터로 학습이 잘 이루어져서 네크워크 망의 출력값 $y_n$ 가 $t_n$ 와 매우 비슷한 값을 내어준다면 위의 식에서 2번째 텀은 생략 가능하다.
- 물론 제대로 하려면 섹션 1.5.5 에서 다루었듯 출력 값의 조건부 평균을 사용해야 겠지만 일단 넘어가자.
- 식(5.83)에서 두번째 텀을 생략한 식을 Levenberg-Marquardt 근사 또는 외적 근사(outer product approx.)라고 부른다.
- 사실 헤시안 행렬 자체가 외적의 합으로 이루어진 행렬이다.

${\bf H} \simeq \sum_{n=1}^N {\bf b_n}{\bf b_n}^T \qquad{(5.84)}$

여기서 ${\bf b_n} \equiv \nabla a_n = y_n$ 이다.
- 회귀 문제에서는 마지막 레이어의 활성(activation) 함수가 Identity 함수이기 때문이다.
이 근사법은 헤시안을 구하기 위해 오로지 1차 미분만을 요구하고 backprop 시 $O(W)$ 에 값을 구할 수 있다.
그리고 $W$ 차원의 두 벡터를 외적할 때 $ O(W^2) $ 이 요구된다.
로지스틱 시그모이드(logistic sigmoid) 활성 함수를 가지는 크로스 엔트로피(cross-entropy)를 사용하는 경우 근사식은 다음과 같이 된다.

${\bf H} \simeq \sum_{n=1}^N y_n(1-y_n){\bf b_n}{\bf b_n}^T \qquad{(5.85)}$

다중부류(multi-class)로도 쉽게 확장된다.

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

헤시안을 응용하는 곳에서는 주로 헤시안 역행렬을 사용하는 경우가 많다. (물론 신경망에서도!!!)
앞서 살펴보았던 외적 근사 기법을 통해 헤시안의 역행렬을 구하는 방법을 살펴볼 것이다.
끝에 나오는 quasi-Newton 을 주의깊게 살펴보자.

${\bf H}_N = \sum_{n=1}^N {\bf b_n}{\bf b_n}^T \qquad{(5.86)}$

여기서 $ {\bf b_n} \equiv \nabla a_n $ 이다.
각 데이터 n 으로부터 얻어지는 활성 함수의 출력값을 미분하여 얻을 수 있다.
이제 이 값을 하나씩 갱신해나갈 수 있는 식을 작성해보자. (점진적 구축 방식)

${\bf H_{L+1} } = {\bf H}_L + {\bf b}_{L+1}{\bf b}_{L+1}^T \qquad{(5.86)}$

역 헤시안을 구하기 위해 이미 알려진 식을 사용한다.

$({\bf M} + {\bf vv}^T)^{-1} = {\bf M}^{-1} - \frac{({\bf M}^{-1}{\bf v})({\bf v}^T {\bf M}^{-1})}{1+{\bf v}^T {\bf M}^{-1} {\bf v}} \qquad{(5.87)}$

아래 식은 Woodbury identy 라는 식이다. (Appendix. C.7을 참고하자)

$(A+BD^{-1}C)^{-1} = A^{-1} - A^{-1}B(D+CA^{-1}B)^{-1}CA^{-1} \qquad{(C.7)}$

이 식을 이용하여 헤시안 역행렬을 구할 수 있다.

${\bf H}_{L+1}^{-1} = {\bf H}_{L}^{-1} - \frac{ {\bf H}_{L}^{-1} {\bf b}_{L+1} {\bf b}_{L+1}^{T} {\bf H}_{L}^{-1} }{ 1 + {\bf b}_{L+1}^{T} {\bf H}_{L}^{-1} {\bf b}_{L+1} } \qquad{(5.89)}$

이제 식(5.87)과 식(5.88)을 활용해서 헤시안 역행렬을 전진적인 방식(incremental)으로 근사 할 수 있다.
참고로 Woodbury identity 에 대응되는 식은 다음과 같다.

${\bf b}_{L+1} = {\bf v}$ ${\bf H}_{L} = {\bf M}$ ${\bf H}_{L+1} = {\bf M} + {\bf v}{\bf v}^T$

5.4.4 유한 차분법 (Finite differences)

에러 함수를 한번 미분하는 방식과 마찬가지로 두번 미분해서 결과를 얻어낼 수 있다.
이건 이미 앞에서 한번 살펴본 방식이다.
다시 설명할 필요는 없을 듯 하고 식을 우선 보자.

$\frac{\partial^2 E}{\partial w_{ji} w_{lk} } = \frac{1}{4e^2} \left\{ E(w_{ji} + e, w_{lk} + e) - E(w_{ji} + e, w_{lk}-e) \\ - E(w_{ji}-e, w_{lk}+e) + E(w_{ji}-e, w_{lk}-e)\right\} + O(e^2)\qquad{(5.90)}$

symmetric 미분 방식으로 인해서 $ O(e) $ 대신 $ O(e^2) $ 를 사용하게 된다. (앞서 살펴보았다.)
문제는 실제 연산량이 $ O(W^3) $ 이라는 것이다.
- 따라서 이 방식을 도입하기가 현실적으로 어려운 점이 있다.
- 대응 방법으로 다음과 같은 방식의 식을 사용할 수도 있다.

$\frac{\partial^2 E}{\partial w_{ji} \partial w_{lk}} = \frac{1}{2}\left\{ \frac{\partial E}{\partial w_{ji}}(w_{lk}+e) - \frac{\partial E}{\partial w_{ji}}(w_{lk}-e) \right\} \qquad{(5.91)}$

이 식을 사용하면 $ 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 = \frac{\partial E_n}{\partial a_k}, \qquad M_{kk'} \equiv \frac{\partial^2 E}{\partial a_k \partial a_{k'}} \qquad{(5.92)}$

일단 지금까지 다루었던 일차 미분방식에서는 $\delta_k$ 만 backprop 대상으로 삼았는데,
헤시안을 활용하기 위해서는 $M_{kk’}$ 도 backprop 대상으로 삼아야 한다.
일단 두번째 레이어 (즉, 마지막 레이어) 에서의 backprop 을 확인해본다.

$\frac{\partial^{2} E_{n}}{\partial w_{kj}^{(2)} \partial w_{k'j'}^{(2)}} = \frac{\partial a_{k}}{\partial w_{kj}^{(2)}} \frac{\partial a_{k'}}{\partial w_{k'j'}^{(2)}} \frac{\partial^{2} E_{n}}{\partial a_{k} \partial a_{k'}} = z_{j} z_{j'} M_{kk'}\qquad{(5.93)}$

이어서 첫번째 레이어의 weight 값을 확인해보자.

$\frac{\partial^2 E_n}{\partial w_{ji}^{(1)} \partial w_{j'i'}^{(1)}} = \frac{\partial a_j}{\partial w_{ji}^{(2)}} \frac{\partial a_{j'}}{\partial w_{j'i'}^{(2)}} \frac{\partial^2 E_n}{\partial a_j \partial a_{j'}} = x_i x_{i'} M_{jj'} \qquad{(5.94)}$ $M_{jj'} \equiv \frac{\partial^2 E_n}{\partial a_j \partial a_{j'}} = {h''}(a_{j'}) I_{jj'} \sum_k w_{kj'}^{(2)} \delta_k\ +\ {h'}(a_{j'}) {h'}(a_j) \sum_k \sum_{k'} w_{kj'}^{(2)} w_{k'j}^{(2)} M_{kk'}$

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

$\frac{\partial^2 E_n}{\partial w_{ji}^{(1)} \partial w_{kj'}^{(2)}} = x_i {h'}(a_{j}) \left\{ \delta_{k} I_{jj'} + z_{j'} \sum_{k'} w_{k'j}^{(2)} M_{kk'} \right\}\qquad{(5.95)}$

헤시안을 이용한 빠른 곱 (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$ 를 계산하는 방법을 살펴볼 것이다.
일단 식을 먼저 보자.

$v^T H = v^T \nabla (\nabla E)\qquad{(5.96)}$

이 때 $\nabla E$ 는 backprop 과정 중에 얻을 수 있다.

$R\{w\} = v\qquad{(5.99)}$ $a_{j} = \sum_i w_{ji} x_i\qquad{(5.98})$ $z_{j} = h(a_j)\qquad{(5.99)}$ $y_{k} = a_k = \sum_j w_{kj} z_j\qquad{(5.100)}$ $R\{a_j\} = \sum_i v_{ji} x_i\qquad{(5.101)}$ $R\{z_j\} = {h'}(a_j) R\{a_j\}\qquad{(5.102)}$ $R\{y_k\} = \sum_j w_{kj} R\{z_j\}\ +\ \sum_j v_{kj} z_j\qquad{(5.103)}$ $\delta_k = y_k - t_k\qquad{(5.104)}$ $\delta_j = {h'}(a_j) \sum_k w_{kj} \delta_k\qquad{(5.105)}$ $R\{\delta_k\} = R\{y_k\}\qquad{(5.106)}$ $R\{\delta_j\} = {h''}(a_j) R\{a_j\} \sum_k w_{kj} \delta_k\ +\ {h'}(a_j) \sum_k v_{kj} \delta_k\ +\ {h'}(a_j) \sum_k w_{kj} R\{\delta_k\}\qquad{(5.107)}$ $\frac{\partial E}{\partial w_{kj}} = \delta_k z_j\qquad{(5.108)}$ $\frac{\partial E}{\partial w_{ji}} = \delta_j x_i\qquad{(5.109)}$ $R \left\{ \frac{\partial E}{\partial w_{kj}} \right\} = R\{\delta_k\} z_j\ +\ \delta_k R\{z_j\}\qquad{(5.110)}$ $R \left\{ \frac{\partial E}{\partial w_{ji}} \right\} = x_i R\{\delta_j\}\qquad{(5.111)}$

Chapter. 5