共役勾配法などにおける行列にヘッセ行列(Hessian Matrix)を用いる場合、ニューラルネットワークのようにパラメータが多い場合はヘッセ行列の要素が多いことで計算が難しくなります。このような際にHessian-free optimizationが有用なので、当記事では概要について取りまとめました。
“Training Deep and Recurrent Networks with Hessian-Free Optimization”の内容を参考に作成を行いました。
https://www.cs.toronto.edu/~jmartens/docs/HF_book_chapter.pdf
・用語/公式解説
https://www.hello-statisticians.com/explain-terms
Contents
前提の理解
ヘッセ行列の定義
$p$次元のベクトル$\displaystyle \mathbf{x} = \left(\begin{array}{c} x_1 \\ \vdots \\ x_p \end{array} \right)$に関するスカラー関数$f(\mathbf{x})$のヘッセ行列$H(f)$は下記のように定義される。
$$
\large
\begin{align}
H(f) &= \nabla \otimes \nabla f(\mathbf{x}) \\
&= \left(\begin{array}{c} \displaystyle \frac{\partial}{\partial x_1} \\ \vdots \\ \displaystyle \frac{\partial}{\partial x_p} \end{array} \right) \left(\begin{array}{ccc} \displaystyle \frac{\partial f}{\partial x_1} & \cdots & \displaystyle \frac{\partial f}{\partial x_p} \end{array} \right) \\
&= \left(\begin{array}{ccc} \displaystyle \frac{\partial^2 f}{\partial x_1^2} & \cdots & \displaystyle \frac{\partial^2 f}{\partial x_1 \partial x_p} \\ \vdots & \ddots & \vdots \\ \displaystyle \frac{\partial^2 f}{\partial x_p \partial x_1} & \cdots & \displaystyle \frac{\partial^2 f}{\partial x_p^2} \end{array} \right)
\end{align}
$$
ヘッセ行列について詳しくは下記で取り扱った。
ヘッセ行列の活用例：共役勾配法
共役勾配法では下記のような式に基づいて最適化を行う際にパラメータを移動させる方向を計算する。
$$
\large
\begin{align}
\mathbf{d}_{2} = \mathbf{v}_{2} – \frac{\mathbf{v}_{1}^{\mathrm{T}} A \mathbf{v}_{2}}{\mathbf{v}_{1}^{\mathrm{T}} A \mathbf{v}_{1}} \mathbf{v}_{1} \quad (1)
\end{align}
$$
$(1)$式の詳細は「共役勾配法の原理と具体的な計算例」、「共役勾配法のPythonを用いた計算例」などで取り扱った。ここで$(1)$式の対称行列$A$は数値で与えられることもあるが、多変数関数の最適化などの場合はヘッセ行列$H$が用いられる。
ヘッセ行列と多変数関数のテイラー二次近似
多変数関数$f(\mathbf{x})$の$\mathbf{x}$における近傍$\mathbf{x} + \varepsilon\mathbf{v}$について、下記のような一次のテイラー近似を行うことができる。
$$
\large
\begin{align}
f(\mathbf{x} + \varepsilon \mathbf{v}) & \simeq f(\mathbf{x}) + \frac{\varepsilon \nabla f(\mathbf{x})^{\mathrm{T}} \mathbf{v}}{1!} \quad (2) \\
\mathbf{x} & \in \mathbb{R}^{p}, \, \mathbf{v} \in \mathbb{R}^{p}
\end{align}
$$
同様な表記は下記でも取り扱った。
Hessian-free optimization
問題設定
ニューラルネットワークなどの多変量のパラメータベクトルを$\boldsymbol{\theta} \in \mathbb{R}^{p}$、尤度などに基づく目的関数を$f(\boldsymbol{\theta})$のように定義する。このとき勾配ベクトル$\nabla f(\boldsymbol{\theta})$、ヘッセ行列$H$は下記のように表せる。
$$
\large
\begin{align}
\nabla f(\boldsymbol{\theta}) &= \left(\begin{array}{c} \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_1} \\ \vdots \\ \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_p} \end{array} \right) \\
H &= \left(\begin{array}{ccc} \displaystyle \frac{\partial^2 f}{\partial \theta_1^2} & \cdots & \displaystyle \frac{\partial^2 f}{\partial \theta_1 \partial \theta_p} \\ \vdots & \ddots & \vdots \\ \displaystyle \frac{\partial^2 f}{\partial \theta_p \partial \theta_1} & \cdots & \displaystyle \frac{\partial^2 f}{\partial \theta_p^2} \end{array} \right)
\end{align}
$$
Hessian-vector productの近似
前節の$(2)$式に前項の「問題設定」を適用すると下記のように表せる。
$$
\large
\begin{align}
f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) & \simeq f(\boldsymbol{\theta}) + \frac{\varepsilon \nabla f(\boldsymbol{\theta})^{\mathrm{T}} \mathbf{u}}{1!} \quad (3)
\end{align}
$$
$(3)$式は下記のように変形できる。
$$
\large
\begin{align}
f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) & \simeq f(\boldsymbol{\theta}) + \frac{\varepsilon \nabla f(\boldsymbol{\theta})^{\mathrm{T}} \mathbf{u}}{1!} \quad (3) \\
\nabla f(\boldsymbol{\theta})^{\mathrm{T}} \mathbf{u} & \simeq \frac{f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – f(\boldsymbol{\theta})}{\varepsilon} \\
\left(\begin{array}{c} \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_1} & \cdots & \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_p} \end{array} \right) \mathbf{u} & \simeq \frac{f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – f(\boldsymbol{\theta})}{\varepsilon} \quad (4)
\end{align}
$$
ここで$(4)$式の両辺に対し、$\nabla$を計算すると下記が得られる。
$$
\large
\begin{align}
\left(\begin{array}{ccc} \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_1} & \cdots & \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_p} \end{array} \right) \mathbf{u} & \simeq \frac{f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – f(\boldsymbol{\theta})}{\varepsilon} \quad (4) \\
\nabla \left(\begin{array}{ccc} \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_1} & \cdots & \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_p} \end{array} \right) \mathbf{u} & \simeq \nabla \left( \frac{f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – f(\boldsymbol{\theta})}{\varepsilon} \right) \\
\left(\begin{array}{c} \displaystyle \frac{\partial}{\partial \theta_1} \\ \vdots \\ \displaystyle \frac{\partial}{\partial \theta_p} \end{array} \right) \left(\begin{array}{ccc} \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_1} & \cdots & \displaystyle \frac{\partial f(\boldsymbol{\theta})}{\partial \theta_p} \end{array} \right) & \simeq \frac{\nabla f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – \nabla f(\boldsymbol{\theta})}{\varepsilon} \\
\left(\begin{array}{ccc} \displaystyle \frac{\partial^2 f}{\partial \theta_1^2} & \cdots & \displaystyle \frac{\partial^2 f}{\partial \theta_1 \partial \theta_p} \\ \vdots & \ddots & \vdots \\ \displaystyle \frac{\partial^2 f}{\partial \theta_p \partial \theta_1} & \cdots & \displaystyle \frac{\partial^2 f}{\partial \theta_p^2} \end{array} \right) \mathbf{u} & \simeq \frac{\nabla f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – \nabla f(\boldsymbol{\theta})}{\varepsilon} \\
H \mathbf{u} & \simeq \frac{\nabla f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – \nabla f(\boldsymbol{\theta})}{\varepsilon} \quad (5)
\end{align}
$$
$(5)$式に対し、$\varepsilon \to 0$を考えると下記のように表せる。
$$
\large
\begin{align}
H \mathbf{u} = \lim_{\varepsilon \to 0} \frac{\nabla f(\boldsymbol{\theta} + \varepsilon \mathbf{u}) – \nabla f(\boldsymbol{\theta})}{\varepsilon} \quad (6)
\end{align}
$$
$(6)$式を用いて$(1)$式の$A \mathbf{v}_{1}, \, A \mathbf{v}_{2}$を計算すれば、ヘッセ行列を計算せずにヘッセ行列とベクトルの積を近似することができる。
[…] Hessian-free optimizationにおける二次形式の計算の軽量化 […]