(補足)乱択化フーリエ特徴を用いたリッジ回帰

#1.目的
前稿では、学習データ数が少なく計算時間の観点から乱択化フーリエ特徴を用いた場合の利得が見られませんでした。本稿では、教師データ数をパラメータとし、カーネル法及び乱択化フーリエ特徴を用いた場合の計算時間について確認します。また、多次元入力に対応した乱択化フーリエ特徴を用いたリッジ回帰の実装を示します。

前回投稿
https://qiita.com//hiroponX/items/448daec79fac2ffd82a0

#2.計算時間
最初に、リッジ回帰にカーネル法及び乱択化フーリエ特徴を用いた場合の計算時間について、前回実装したクラスを用いて確認してみます。教師データは前稿と同様、$g(x)=xsin(x)+ε$に基づき生成します（$ε$は平均0、分散0.2の正規分布）。

*Rff : 乱択化フーリエ特徴(Random Fourier Features)、mfは$u$のサンプリング数を示す。
注目すべきは、乱択化フーリエ特徴を用いた場合、通常のリッジ回帰と同様に計算時間が$O(N)$であることです。参考のためscikit-learnのカーネルリッジ回帰(sklearn.kernel_ridge.KernelRidge)での計算時間も示しました。やはり、カーネル法は計算時間が$O(N^2)$となることから、大規模データへの適用は難しそうですね。

#3.多次元化
次に、入力値が多次元の場合の実装を示します。多次元化に伴う変更点は、三角関数の中身がスカラー量$u$と$x$の積から、ベクトル量$u^T$と$x$の内積に変更されている点のみです。1次元の時と同様、$u$は$p(u)$に従いランダムに$M$個サンプリングします。ただし、1次元の場合と異なり、$u$は入力次元数$D$と同じ次元数のベクトルとなります。

\begin{align}
k(x, x_n)&=\int_{R}\exp(iu^T(x-x_n))dp(u)=\int_{R}\cos(u^T(x-x_n))dp(u)\\
&\approx\sum_{m=1}^M\cos(u_m^T(x-x_n))\\
&=\sum_{m=1}^M\cos(u_m^Tx)\cos(u_m^Tx)+\sin(u_m^Tx)\sin(u_m^Tx)
\end{align}

カーネルは下式に示すような基底関数に分解できます。

$$k(x, x_n)=\sum_{m=1}^{2M}\phi_m(x)\phi_m(x_n)$$

\begin{align}
&\phi_m(x)=\cos(u_m^Tx)\quad (m=1,2,3\dots,M)\\
&\phi_m(x)=\sin(u_{m-M}^Tx)\quad (m=M+1,M+2,M+3\dots,2M)\\
\end{align}

変更点は僅かであり、1次元から多次元への拡張は容易です。

rff.py

import numpy as np
class RffRegression(object):
    def __init__(self, lamda=0.1, sigma=1, mf=100):
        self.lamda = lamda
        self.sigma = sigma
        self.mf = mf
        
    def fit(self, X, t):
        self.X = X
        self.N = len(t)
        self.D = X.shape[1]
        self.u = np.random.normal(0, self.sigma*self.sigma, (self.mf, self.D))
        Phi = np.zeros((self.N, 2*self.mf))
        for n in range(self.N):
            Phi[n, :] = self.func(X[n,:])
        A = np.dot(Phi.T, Phi) + np.identity(2*self.mf) * self.lamda
        b = np.dot(Phi.T, t)
        self.w = np.linalg.solve(A, b)
        
    def predict(self, x):
        return np.dot(self.w, self.func(x))
    
    def func(self, x1):
        cosf = np.cos(np.dot(self.u, x1))
        sinf = np.sin(np.dot(self.u, x1))
        return np.hstack((cosf, sinf))

ここで、実装した回帰モデルを用いて$f(x,y)=\sin(x\cos(y))$から生成される2500点の教師データを基に、$f(x,y)$を再現可能であるかを確認してみます。なお、ここではサンプリング数は1000としました。
下図が結果になります。それぞれ、左上が2500点の教師データ、左下が$f(x,y)$、右下が回帰モデルにより再現された$f(x,y)$、右上が真の$f(x,y)$と回帰モデルにより再現された$f(x,y)$の差の絶対値です。回帰モデルにより$f(x,y)$が概ね良好に再現されています。

#4.まとめ
前稿の補足として、リッジ回帰にカーネル法及び乱択化フーリエ特徴を用いた場合の計算時間の確認、及び乱択化フーリエ特徴を用いたリッジ回帰の多次元入力対応実装を示しましたした。