Nyström 近似
カーネル法におけるグラム行列の Nyström 近似（ニストローム近似[注釈1]）とは、グラム行列の固有値分解を、一部のサンプルに対応するグラム行列の固有値分解から近似的に求めたもの（またはそこからさらに絶対値の小さい固有値を切り捨てて低ランクにしたもの）である、と思われる。
固有値分解があればグラム行列を好きなだけ低ランクに近似することができ、グラム行列の逆行列計算の計算量を削減できる。が、固有値分解に $\mathcal{O}(n^3)$ の計算量がかかるため普通に固有値分解するのでは本末転倒になる。そこで、「グラム行列の固有ベクトルが正定値カーネルで定まる積分作用素の固有値問題の数値解になる」という積分方程式の数値解法としての Nyström 法の結果を利用し、固有値分解を近似的に求めたものが Nyström 近似となっている。
具体的には、グラム行列 $K^{(n)} \in \mathbb{R}^{n \times n}$ の固有値 $\lambda_{1}^{(n)}, \cdots, \lambda_{n}^{(n)}$ と固有ベクトル $u_{1}^{(n)}, \cdots, u_{n}^{(n)}$ を、$m$ 個の部分データに対するグラム行列 $K^{(m)}$ の固有値 $\lambda_{1}^{(m)}, \cdots, \lambda_{m}^{(m)}$ と固有ベクトル $u_{1}^{(m)}, \cdots, u_{m}^{(m)}$ を利用して近似した $\tilde{\lambda}_{1}^{(n,m)}, \cdots, \tilde{\lambda}_{m}^{(n,m)}$ と $\tilde{u}_{1}^{(n,m)}, \cdots, \tilde{u}_{m}^{(n,m)}$ で代用する（右肩の $(n,m)$ は $n$ 次元の固有値分解を $m$ 次元の固有値分解で近似したという意味）。このとき固有値分解の近似は以下のようになる。最後の和を $m$ 未満で打ち切ってもよい。
$$
\begin{align}
\tilde{K}^{(n,m)} &= \begin{pmatrix}
\tilde{u}_{1,1}^{(n,m)} & \cdots & \tilde{u}_{m,1}^{(n,m)} \\
\tilde{u}_{1,2}^{(n,m)} & \cdots & \tilde{u}_{m,2}^{(n,m)} \\
\vdots & \ddots & \vdots \\
\tilde{u}_{1,n}^{(n,m)} & \cdots & \tilde{u}_{m,n}^{(n,m)} \\
\end{pmatrix}
\begin{pmatrix}
\tilde{\lambda}_{1}^{(n,m)} & 0 & \cdots & 0 \\
0 & \tilde{\lambda}_{2}^{(n,m)} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \tilde{\lambda}_{m}^{(n,m)} \\
\end{pmatrix}
\begin{pmatrix}
\tilde{u}_{1,1}^{(n,m)} & \tilde{u}_{1,2}^{(n,m)} & \cdots & \tilde{u}_{1,n}^{(n,m)} \\
\vdots & \vdots & \ddots & \vdots \\
\tilde{u}_{m,1}^{(n,m)} & \tilde{u}_{m,2}^{(n,m)} & \cdots & \tilde{u}_{m,n}^{(n,m)} \\
\end{pmatrix} \\
&= \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n,m)} \tilde{u}_{l}^{(n,m)} \tilde{u}_{l}^{(n,m) \top}
\end{align}
$$
参考文献
- 福水 健次. カーネル法入門. 朝倉書店, 2010.
- Christopher Williams, Matthias Seeger. Using the Nyström Method to Speed Up Kernel Machines. In NIPS 2000.[link]
- グラム行列の Nyström 近似の原論文である。
Nyström 近似
カーネル法ではデータ $X_1, \cdots, X_n$ から得られるグラム行列 $K^{(n)}$ を通してデータを分析する。ここで $k(\cdot, \cdot)$ は採用した正定値カーネルである。
$$
K^{(n)} = \begin{pmatrix}
k(X_1, X_1) & k(X_1, X_2) & \cdots & k(X_1, X_n) \\
k(X_2, X_1) & k(X_2, X_2) & \cdots & k(X_2, X_n) \\
\vdots & \vdots & \ddots & \vdots \\
k(X_n, X_1) & k(X_n, X_2) & \cdots & k(X_n, X_n) \\
\end{pmatrix}
$$
例えばカーネルリッジ回帰では回帰係数に $K^{(n)} + \lambda I_n$ の逆行列が含まれるため、$n$ が大きいと計算量が大きくなり、何らかの計算量削減方法が必要になってくる。
一案として、カルマンフィルタを思い出すと、もし $K^{(n)} = BDC$ $( B \in \mathbb{R}^{n \times m},$ $C \in \mathbb{R}^{m \times m},$ $D \in \mathbb{R}^{m \times n},$ $m < n )$ の形の低ランク近似があれば、Sherman-Morrison-Woodbury の公式[注釈2]により逆行列を計算すべき行列のサイズが $m \times m$ にできるとわかる。しかし、グラム行列はカルマンフィルタの分散共分散行列とは違い、自ら $K^{(n)} = BDC$ の形をしていない。固有値分解[注釈3]して絶対値の小さい固有値を切り捨てればこの形にできるが、固有値分解には $\mathcal{O}(n^3)$ の計算量がかかるため、普通に固有値分解するのでは計算量を削減する目的としては本末転倒になる。
グラム行列の固有ベクトルと正定値カーネルの固有関数の関係
より小さい計算量で近似的にグラム行列 $K^{(n)}$ の固有値分解を得るにはどうすればよいだろうか。$K^{(n)}$ を固有値分解するとは以下の $\lambda_{1}^{(n)}, \cdots, \lambda_{n}^{(n)}, u_{1}^{(n)}, \cdots, u_{n}^{(n)}$ を求めることに他ならない。
なお、以降固有ベクトル $u_{1}^{(n)}, \cdots, u_{n}^{(n)}$ は単位固有ベクトルとする。
$$
k(X_i, X_j) = \sum_{l=1}^{n} \lambda_{l}^{(n)} u_{l, i}^{(n)} u_{l, j}^{(n)}
\tag{1}
$$
他方、正定値カーネル $k(\cdot, \cdot)$ は Mercer の定理を満たすので、可算個の固有関数 $\psi_l(\cdot)$ を用いて以下のように表現できる。ここで固有関数 $\psi_l(\cdot)$ は直交性 $\int \psi_l(x) \psi_{l'}(x) p(x) dx = \delta_{l, l'}$ を満たす。
$$
k(x, y) = \sum_{l=1}^{\infty} \gamma_{l} \psi_{l}(x) \psi_{l}(y)
\tag{2}
$$
式 $(1)$ と式 $(2)$ は似ている。式 $(1)$ は、式 $(2)$ を、データ $X_1, \cdots, X_n$ 上だけで数値近似したようなものにもみえる。両者の関係を確かめるために式 $(2)$ を $\psi_l(\cdot)$ のみの方程式にしよう。両辺に $\psi_l(x)$ をかけて入力空間全体で積分することで以下の積分方程式になる。
$$
\int k(x, y) \psi_{l}(x) p(x) dx = \gamma_{l} \psi_{l}(y)
\tag{3}
$$
この式 $(3)$ は「等質な第二種フレドホルム積分方程式」というクラスの積分方程式であり、このクラスの積分方程式を、「積分を $n$ 個の代表点における値の重み付き和に近似」して解く数値解法を
Nyström 法という、はずである。つまり、式 $(3)$ を以下の式 $(4)$ に数値近似して、この $y$ に $X_j$ を代入した $n$ 個の連立方程式 $(5)$ を解き、固有値の近似 $\tilde{\gamma}_l^{(n)}$ と $n$ 個の代表点の上の固有関数の値の近似 $\tilde{\psi}_l^{(n)}(X_j)$ を得る（方程式の数 $n$ に対し未知変数の数が $n+1$ なので自由度があり、$n$ 個の固有値と対応する固有関数が得られることになる）。
$$
\frac{1}{n} \sum_{i=1}^n k(X_i, y) \tilde{\psi}_{l}^{(n)}(X_i) = \tilde{\gamma}_{l}^{(n)} \tilde{\psi}_{l}(y)
\tag{4}
$$
$$
\frac{1}{n} \sum_{i=1}^n k(X_i, X_j) \tilde{\psi}_{l}^{(n)}(X_i) = \tilde{\gamma}_{l}^{(n)} \tilde{\psi}_{l}(X_j)
\tag{5}
$$
そして式 $(5)$ は $1/n$ のファクターを除いて $K^{(n)}$ の固有値分解に他ならない。両者の関係は
$$
\tilde{\gamma}_{l}^{(n)} = (1/n) \lambda_{l}^{(n)} , \; \; \tilde{\psi}_{l}^{(n)}(X_j) = \sqrt{n} u_{l, j}^{(n)}
\tag{6}
$$
となる。後者は固有関数の直交性からの要請 $(1/n)\sum_{i=1}^n \tilde{\psi}_{l}^{(n)}(X_i)^2 = 1$ によった。このとき未知の点 $y$ における固有関数の値の近似を得るには、$(6)$ を $(4)$ に代入し直せばよい。$y$ を含めて固有値分解をし直す必要はない（計算量が許すならば固有値分解し直してもよいが）。
$$
\tilde{\psi}_{l}^{(n)}(y) = \frac{\sqrt{n}}{\lambda_{l}^{(n)}} \sum_{i=1}^n k(X_i, y) u_{l, i}^{(n)}
\tag{7}
$$
グラム行列の固有値分解の近似
式 $(6)$ より、グラム行列 $K^{(n)}$ の固有値と固有ベクトルはスケールファクターを除いて正定値カーネルの固有値及びデータ点上の固有関数の値を近似していることがわかった。また、式 $(7)$ より、未知の点における固有関数の値を近似できることもわかった（$n$ 個まで）。
式 $(6)$ を逆向きに使おう。固有関数の値を固有値と固有ベクトルで近似するのではなく、固有値と固有ベクトルを固有関数の値で近似する。と固有関数の値がわからないので、手元のデータから $m$ 個をサンプリングして式 $(7)$ で近似するのである。
$$
\tilde{\lambda}_{l}^{(n, m)} = n \tilde{\gamma}_{l}^{(m)} = \frac{n}{m} \lambda_{l}^{(m)} , \; \; \tilde{u}_{l, j}^{(n, m)} = \frac{\tilde{\psi}_{l}^{(m)}(X_j)}{\sqrt{n}} = \frac{1}{\lambda_{l}^{(m)}} \sqrt{\frac{m}{n}} \sum_{i=1}^m k(X_i, X_j) u_{l, i}^{(m)}
$$
無論この方法では $m$ 個の固有値と固有ベクトルしか得られない。しかし、$K^{(n)}$ の固有値のうち絶対値が特に大きいものが $m$ 個以内であるならば、以下は $K^{(n)}$ のよい近似になるはずである。
$$
\tilde{K}^{(n,m)} = \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n,m)} \tilde{u}_{l}^{(n,m)} \tilde{u}_{l}^{(n,m) \top}
$$
グラム行列の Nyström 近似の性質
$K^{(n)}$ の $a$ 行目までかつ $b$ 列目までをとった行列を $K_{a, b}^{(n)}$ とする。また、$K_{m, m}^{(n)} = K^{(m)}$ が正則であるとする。このとき $\tilde{K}^{(n,m)} = K_{n, m}^{(n)} {K_{m,m}^{(n)}}^{-1} K_{n, m}^{(n,m) \top}$ の関係があり、$\tilde{K}^{(n,m)}$ は右下 $(n-m) \times (n-m)$ ブロックを除き $K^{(n)}$ と一致する [2] [注釈4]。
注釈
- Nyström 氏の名前にこれが決定版といった仮名表記はみうけられないが、筆者はインターネットで調べた結果、「ルンゲクッタ-ニストローム法」で表記がみられる「ニストローム」を採用する。
- 雑記： Schur 補行列と Sherman-Morrison-Woodbury の公式とカルマンフィルタとガウス過程回帰の整理 - クッキーの日記
- これはメモだが、グラム行列は対称行列なので直交行列で対角化可能であり、また、半正定値であるので固有値はすべて非負である。
- 雑記 - クッキーの日記