Optimal Brain Damage : 局所二次近似と極値判定（凸関数, 勾配, ヘッセ行列）

1. 背景
2. 準備：凸関数とテイラー展開
3. 局所二次近似
4. 極値判定
参考

このポストでは，ニューラルネットワークモデルにおける「パラメータを訓練(学習)させるためのアルゴリズム」に注目したいと思います．ニューラルネットワークモデルについては，

「特徴量（=パラメータ）を人間が与えなくとも，機械(=コンピュータ)が勝手にその "重要度" を評価し，学習する」

という内容で，その新奇性を紹介されることが多いですが．この主張の要点は，

各重み (params) の性能への"寄与度"を機械 (model) が自動的に評価すること
各重み (params) の性能への"寄与度"を機械 (model) が評価した後に，その情報を機械 (model) に反映させること

の２つに集約できます．しかし，前者に関しては，適応信号処理や情報検索，機械学習などで既に多くの一般的な研究成果が与えられているため，ニューラルネットワーク特有の性質とは言えません．その意味で，個人的には，後者：「各重み (params) の性能への"寄与度"を機械 (model) が評価した後に，その情報を機械(model) に自動的に反映させること」こそがニューラルネットワークモデルのクリティカルな性質であると言って良いでしょう．そしてこれは，具体的に「誤差逆伝播法」というアイデアと，これを解くための「最急降下法」という最適化アルゴリズムに基づきます．

以上を踏まえ，このポストでは，ニューラルネットワークモデルの核である「誤差逆伝播法」「最急降下法」に注目した上で，その原理となる「局所二次近似」や「凸最適化」についてまとめてみたいと思います．

1. 背景

Optimal Brain Damage (: OBD)とは，ニューラルネットワークを用いた目的変数の予測問題において、パラメータ数を縮減するための方法であり，局所二次近似 (Approximation of Second-order Derivatives) とは，OBDを実装する際に必要となる計算アルゴリズムのことです。具体的には，目的関数(=誤差関数, 損失関数)を２次の項までのテイラー展開によって近似することで，あるパラメータの組み合わせに対する「勾配」を求めます．

なお．OBDは、Yann Le Can らによって書かれた初期のニューラルネットワーク研究における有名な論文：Optimal Brain Damage [Yan, et al. 1990]によって提案されました．また，OBDに関連する概念・用語としては，以下のようなものが挙げられます．

OBD: Optimal Brain Damage
OBS: Optimal Brain Surgeon
OCD: Optimal Cell Damage

ここからは、局所二次近似について考えてみましょう．

2. 準備：凸関数とテイラー展開

まず，凸関数(Convex function)，勾配(Gradient)，ヘッセ行列(Hessian)の定義を与えます．

2. 1. 凸関数

n個のスカラー変量 $\{x_n\}$ からなる多変数関数： $f(x_1, x_2, ... x_n)~=f({\bf x})$ を考える．

定義域上の任意の2点 ${\bf x_a}, ~{\bf x_b}$ (n次元ベクトル)において，次の不等式を満たすとき， $f$ を「凸関数」(: Convex function)という．

$\begin{equation} {\lambda}{\cdot}f({\bf x_a})+(1-{\lambda}){\cdot}f({\bf x_b})~~{\geq}~~f({\lambda}{\cdot}{\bf x_a}+(1-{\lambda}){\cdot}{\bf x_b}) \end{equation}$

なお，等号成立が ${\bf x_a}~=~{\bf x_b}$ の場合に限るとき， $f$ を「狭義の凸関数」という．

2. 2. 勾配 - Gradient

n個のスカラー変量 $\{x_n\}$ からなる多変数関数： $f(x_1, x_2, ... x_n)~=f({\bf x})$ を考える．

$f(x_1, x_2, ... x_n)$ が，任意の変数 $x_1, x_2, ... x_n$ について1階偏導関数が定義されているとき， $f$ に対する1階微分の情報を包括的に含む以下のn次元ベクトル $\bf\nabla$ が定められる．これを「 $f$ の勾配(gradient, $grad f)$ 」という．

${\bf\nabla}f({\bf x})=\left( \begin{array}{cccc} \frac{\partial f({\bf x})}{\partial x_1} \\ \frac{\partial f({\bf x})}{\partial x_2} \\ \vdots \\ \frac{\partial f({\bf x})}{\partial x_n} \end{array} \right)$

${\bf\nabla}f({\bf x})={\large\frac{\partial f}{\partial x_1}}\mathbf{e_1}+{\large\frac{\partial f}{\partial x_2}}\mathbf{e_2}+\ldots+{\large\frac{\partial f}{\partial x_n}}\mathbf{e_n}$

2. 3. ヘッセ行列 - Hessian Matrix

n個のスカラー変量 $\{x_n\}$ からなる多変数関数： $f(x_1, x_2, ... x_n)~=f({\bf x})$ を考える．

$f(x_1, x_2, ... x_n)$ が，任意の変数 $x_1, x_2, ... x_n$ について2階偏導関数が定義されているとき， $f$ に対する2階微分の情報を包括的に含む以下のn×n正方行列: ${\bf H}~={\nabla^2}f({\bf x})$ が定められる．これをヘッセ行列という．

${\bf H}={{\bf\nabla}^2}f({\bf x})=\left( \begin{array}{cccc} {\frac{{\partial}^2 f({\bf x})}{{\partial x_1}{\partial x_1}}} & {\frac{{\partial}^2 f({\bf x})}{{\partial x_1}{\partial x_2}}} & \ldots & {\frac{{\partial}^2 f({\bf x})}{{\partial x_1}{\partial x_n}}} \\ {\frac{{\partial}^2 f({\bf x})}{{\partial x_2}{\partial x_1}}} & {\frac{{\partial}^2 f({\bf x})}{{\partial x_2}{\partial x_2}}} & \ldots & {\frac{{\partial}^2 f({\bf x})}{{\partial x_2}{\partial x_n}}} \\ \vdots & \vdots & \ddots & \vdots \\ {\frac{{\partial}^2 f({\bf x})}{{\partial x_n}{\partial x_1}}} & {\frac{{\partial}^2 f({\bf x})}{{\partial x_n}{\partial x_2}}} & \ldots & {\frac{{\partial}^2 f({\bf x})}{{\partial x_n}{\partial x_n}}} \end{array} \right)$

ただし，ヘッセ行列 ${\bf H}$ の各要素は次のように定義される．

$h_{ij}~=~\frac{{\partial}^2 f}{{\partial x_i}{\partial x_j}}$

2. 4. テイラー展開による2次の近似

n個のスカラー変量 $\{x_n\}$ からなる多変数関数： $f(x_1, x_2, ... x_n)~=f({\bf x})$ を考える．

テイラー展開より， $f$ を任意の点 ${\bf \hat{x}~(=a)}$ によって近似すると，次式を得る．

$f({\bf x})= f({\bf a})+\sum_{n=1}^{\infty}{\large\frac{f^{(n)}({\bf a})}{n!}}({\bf x}-{\bf a})^n$

$f({\bf x}) = f({\bf a})+{\large\frac{f^{(1)}({\bf a})}{1!}}({\bf x}-{\bf a})+{\large\frac{f^{(2)}({\bf a})}{2!}}({\bf x}-{\bf a})^2+{\large\frac{f^{(3)}({\bf a})}{3!}}({\bf x}-{\bf a})^3+~\cdots$

ここで、 $f(x_1, x_2, ... x_n)~=f({\bf x})$ を、2次までのテイラー展開によって近似すると、

$f({\bf x})~{\fallingdotseq}~f({\bf a})+{\large\frac{f^{(1)}({\bf a})}{1!}}({\bf x}-{\bf a})+{\large\frac{f^{(2)}({\bf a})}{2!}}({\bf x}-{\bf a})^2$

となり、既知の値 ${\bf \hat{x}~(=a)}$ によって、 $f$ を推定することができる。

3. 局所二次近似

さて，ここまでの議論で共通して登場してきた

「n個のスカラー変量 $\{x_n\}$ からなる多変数関数： $f(x_1, x_2, ... x_n)~=f({\bf x})$ 」

は，予測問題の文脈では

「n次元のベクトル ${\bf w}$ に関する誤差関数(=目的関数)： $E({(w_1, w_2, ... w_n)}^{\mathrm{T}})~=E({\bf w})$ 」

とみなすことができます.

誤差関数 $E({\bf x})$ に対するパラメータベクトル ${\bf w}$ に，既知の値 $\hat{w}$ を与えて，2次のテイラー展開によって近似してみましょう．

$E({\bf w})~{\fallingdotseq}~E({\bf \hat{w}})+{\large\frac{E^{(1)}({\bf \hat{w}})}{1!}}({\bf w}-{\bf \hat{w}})+{\large\frac{E^{(2)}({\bf \hat{w}})}{2!}}({\bf w}-{\bf \hat{w}})^2$