カーネルモデルを近似する手法: Random Feature
自分の備忘録も兼ねて, カジュアルに機械学習のちょっとした Tips をまとめるシリーズを始めてみたいと思います. 第一弾はカーネルモデルに対する近似手法について.
カーネルモデルを近似する方法としていくつかの方法 (Nyström近似など) がありますが, そのうちランダムな基底 (特徴) を用いて近似する手法を Random Feature といいます. これは [Rahimi and Recht, NeurIPS, 2008]によって提案された手法で, アイディアはシンプルですが非常に面白いです.
Bochner の定理と Random Feature
$\mathbb{R}^d$ 上の連続な平行移動不変カーネル $k(x, y) = k(x - y)$ が正定値であることの必要十分条件は $k(\delta)$ が非負測度のフーリエ変換となることである.
これは
Bochner の定理と呼ばれるものです. この結果から具体的な表式として, 平行移動不変なカーネル関数はある確率分布 $p(\omega)$ を用いて次のように表現することができます.
\begin{align}
k(x-y) &= \int_{\mathbb{R}^d} p(\omega) e^{i \omega^{\top}(x-y)} d \omega\\
&= \mathbb{E} [e^{i \omega^{\top}x} \overline{e^{i \omega^{\top} y}}]
\end{align}
ここでさらに, 実用上実数値カーネルを考えれば十分であることに注意し, 加法定理を用いて整理すると
\begin{align}
k(x-y) &= \mathbb{E}[\sqrt{2} \cos (\omega^{\top}x + b) \sqrt{2} \cos (\omega^{\top}y + b)]\\
&\approx \frac{1}{D} \sum_{j=1}^{D} \sqrt{2} \cos (\omega^{\top}_{j} x + b_j) \sqrt{2} \cos (\omega^{\top}_{j} y + b_j)
\end{align}
と表すことができます. なおここで $\omega, \omega_j \sim p(\omega), b, b_j \sim U[0, 2\pi]$ です. このとき, 上の期待値の不偏推定量による近似をシンプルに考えています.
さて, ここで
\begin{align}
z(x) = \begin{pmatrix}
\sqrt{\frac{2}{D}} \cos(\omega_1^{\top} x + b_1)\\
\vdots \\
\sqrt{\frac{2}{D}} \cos(\omega_D^{\top} x + b_D)
\end{pmatrix}
\end{align}
という関数を考えると, ランダムに $x$ を $\mathbb{R}^D$ 上へ埋め込んでいる関数になっており, 先ほどの推定量は $z(x)^{\top} z(y)$ と書くことができます. この $z(x)$ こそが Random Features であって, 「(一般には無限次元空間への写像となりがちな) 特徴写像をランダムに (低次元空間への写像として) 近似したもの」と見ることもできるというカラクリです. 非常に面白いですね.
References
