leave-one-out cross-validation(LOOCV,一個抜き交差検証)を線形回帰モデルに

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

今回は交差検証、cross validationについて書いてみます。

## validation

cross validationは、機械学習モデルの汎化性能を検証するためのもので、一般的にはK分割交差検証(K-fold cross validation)を指します。

これは、訓練データセットをK分割し、一つのグループ以外の(K-1)個のかたまりでモデルを学習し、残りの一つのグループで性能を評価します。

これをK回、すなわち性能評価用のデータを毎回変えながら実験し、最後にK回の性能評価を平均して最終的な出力とします。

他にも、ホールドアウト検証というものもあります。
これは評価用のデータは固定されていて、性能評価を平均したりはしません。
交差していないので交差検証には含まれないです。

検証のためのデータを学習に使えないので、K-foldよりデータを有効に使えていないイメージです。

今回焦点を当てるのは一個抜き交差検証(leave-one-out cross-validation)です。
これは、K-foldのKをデータ数と同じ個数にしたものと等しいです。

つまり、訓練データ一つを選び、それ以外のデータで学習して最後に一つの評価データで評価します。これを全データで繰り返し行い最後に評価を平均します。

データセットを無駄にせずに余すことなく使っているかんじですが、想像するとわかる通り学習に時間がかかるのが難点です。(データの個数回の学習が走るので)

そのためあまり一個抜き交差検証は実用的ではありませんが、線形回帰モデル(l2正則化つきでも)だと汎化性能を解析的に求めることができます。

## 線形回帰モデルで一個抜き交差検証

線形回帰モデル(l2正則化つき)はこのようなモデルです。

$$f(x) = \sum_i^d \theta_i \phi(x_i) $$

$$\min \sum_i^n|y_i-f(x_i)|^2 + \lambda|\theta|^2$$

一個抜き交差検証は、それぞれ一つずつデータを抜いて上のモデルを学習して、それらの残しておいた1つのデータについての誤差の平均を最終的な汎化性能とみなします。

最終的に、最終的な汎化性能は以下のようになります。

$$\frac{1}{n}\sum_{i=1}^n ||\phi_i^T \hat{\theta_i}-y_i||^2 =\frac{1}{n}||\tilde H^{-1}H\bm{y}||^2$$

ただし、

$(\bm{x}_i,y_i)$以外のデータセットのみで学習して得られるパラメータを$\hat{\theta}_i$と書きます。

また$\phi_i$を$\phi(x_i)$とし、

$$H=I - \Phi U^{-1}\Phi^T$$
$\tilde H$は$H$と対角成分が同じ、他の成分がすべて0の行列です。

以下、これを証明していきます。

$l2$正則化の線形回帰は$\theta$に関して微分することで解析的に解くことができ、今回は以下のようになります。

$$
    \hat{\theta}_i = (\lambda I + \Phi_i^T\Phi_i)^{-1}\Phi_i^T \bm{y}_i
$$
ただし$I$は単位行列、$\Phi_i$は$i$番目のデータを$\Phi$から除外したもの
($\phi_i$と間違えないように注意！)、$\bm{y}_i$も同様に$\bm y$から$y_i$を除いたものです。

ここで、簡単な計算から以下の等式が成り立ちます。

$$\Phi_i^T\Phi_i=\Phi^T\Phi - \phi_i^T\phi_i$$

$$\Phi_i^T\bm y_i=\Phi \bm y - y_i\phi_i^T$$

これらの関係を用いて$\hat{\theta}_i$を書き直すと以下のようになります。
$$\hat{\theta}_i = (U-\phi_i\phi_i^T)^{-1}(\Phi \bm{y}-y_i\phi_i)$$

ただし
$$U=\Phi^T\Phi +\lambda I $$
とします。

これを用いて一個抜き交差検証のlossを計算します。
Sherman-Morrison-Woodbury公式の特別な形である逆行列の公式を使用して変形していくと以下のようになります。

<a href="http://ibisforest.org/index.php?Sherman-Morrison%E3%81%AE%E5%85%AC%E5%BC%8F">Sherman-Morrison-Woodbury公式</a>

$$\begin{aligned}
    \phi_i^T \hat{\theta}_i &= \phi_i^T (U-\phi_i\phi_i^T)^{-1}(\Phi \bm{y}-y_i\phi_i)\cr
                            &= \phi_i^T (U^{-1} + \frac{U^{-1}\phi_i\phi_i^T U^{-1}}{1-\phi_i^TU^{-1}\phi_i})(\Phi \bm{y}-y_i\phi_i)\cr
                            &= \phi_i^T \frac{U^{-1} -\phi_i^T U^{-1} \phi_i U^{-1} + U^{-1}\phi_i\phi_i^T U^{-1}}{1-\phi_i^TU^{-1}\phi_i}(\Phi \bm{y}-y_i\phi_i)\cr
                            &= \frac{\phi_i^T U^{-1} -\phi_i^T\phi_i^T U^{-1} \phi_i U^{-1} + \phi_i^T U^{-1}\phi_i\phi_i^T U^{-1}}{1-\phi_i^T U^{-1}\phi_i}(\Phi \bm{y}-y_i\phi_i)\cr
                            &= \frac{\phi_i^TU^{-1}(\Phi \bm y-y_i\phi_i)}{1-\phi_i^TU^{-1}\phi_i}
\end{aligned}$$

よって、

$$\begin{aligned}
    \frac{1}{n}\sum_{i=1}^n ||\phi_i^T \hat{\theta_i}-y_i||^2 &= \frac{1}{n}\sum_{i=1}^n (\frac{\phi_i^TU^{-1}\Phi \bm{y} -y_i}{1-\phi_i^TU^{-1}\phi_i})^2 \cr
                                                            &= \frac{1}{n}||\tilde H^{-1}H\bm{y}||^2
\end{aligned}$$
となります。

## おわりに

ハイパーパラメータである$\lambda$をチューニングする際に、これを使えば汎化性能がモデルの学習せずに得られるので便利そうですね。

このブログを検索

ぐぐりらにっき

leave-one-out cross-validation(LOOCV,一個抜き交差検証)を線形回帰モデルに

コメント

コメントを投稿

leave-one-out cross-validation(LOOCV,一個抜き交差検証)を線形回帰モデルに

この記事をシェアする

コメント

コメントを投稿