最小二乗法のLeave-One-Out誤差の解析解

# はじめに
最小二乗法やリッジ回帰（L2正則化最小二乗法）の場合、Leave-One-Out Cross-Validationには解析解があります。導出を久しぶりに追ったのでメモしました。

# 最小二乗法のLeave-One-Out誤差の解析解の導出
最小二乗法の解析解は

```math
\begin{align}
  \hat{\boldsymbol{w}} = (\boldsymbol{X}^\top \boldsymbol{X})^{-1} \boldsymbol{X}^\top \boldsymbol{y}
\end{align}
```
で、Leave-One-Out二乗誤差は

```math
\begin{align}
J_{\rm LOOCV}
 &= \sum_{n=1}^N (y_n - \boldsymbol{x}_n^\top \hat{\boldsymbol{w}}_{(n)})^2 \\
\hat{\boldsymbol{w}}_{(n)}
 &= (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{X}_{(n)}^\top \boldsymbol{y}_{(n)}
\end{align}
```
です。ここで (n) は n 番目のサンプルを除いたものとします。Leave-One-Outな残差 $y_n - \boldsymbol{x}\_n^\top \hat{\boldsymbol{w}}_{(n)}$ を、Leave-One-Outでない残差 $r_n = y_n - \boldsymbol{x}_n^\top \hat{\boldsymbol{w}}$ で表現することを目指します。

## Leave-One-Out回帰係数
まず

```math
\begin{align}
\boldsymbol{X}^\top \boldsymbol{X} \hat{\boldsymbol{w}} = \boldsymbol{X}^\top \boldsymbol{X} (\boldsymbol{X}^\top \boldsymbol{X})^{-1} \boldsymbol{X}^\top \boldsymbol{y} = \boldsymbol{X}^\top \boldsymbol{y}
\end{align}
```
で、

```math
\begin{align}
\boldsymbol{X}^\top \boldsymbol{X} &= \boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)} + \boldsymbol{x}_n \boldsymbol{x}_n^\top \\
\boldsymbol{X}^\top \boldsymbol{y} &= \boldsymbol{X}_{(n)}^\top \boldsymbol{y}_{(n)} + y_n \boldsymbol{x}_n
\end{align}
```
より

```math
\begin{align}
(\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)} + \boldsymbol{x}_n \boldsymbol{x}_n^\top) \hat{\boldsymbol{w}}
 &= \boldsymbol{X}_{(n)}^\top \boldsymbol{y}_{(n)} + y_n \boldsymbol{x}_n
\end{align}
```
両辺に左から $(\boldsymbol{X}\_{(n)}^\top \boldsymbol{X}\_{(n)})^{-1}$ を掛けると

```math
\begin{align}
(\boldsymbol{I} + (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{x}_n \boldsymbol{x}_n^\top) \hat{\boldsymbol{w}}
 &= (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{X}_{(n)}^\top \boldsymbol{y}_{(n)}
  + (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{x}_n y_n
\end{align}
```
第一項の $(\boldsymbol{X}\_{(n)}^\top \boldsymbol{X}\_{(n)})^{-1} \boldsymbol{X}\_{(n)}^\top \boldsymbol{y}\_{(n)}$ は $\hat{\boldsymbol{w}}\_{(n)}$ であり、Leave-One-Outでない残差は $r_n = y_n - \boldsymbol{x}\_n^\top \hat{\boldsymbol{w}}$ なので第二項に $y_n = \boldsymbol{x}\_n^\top \hat{\boldsymbol{w}} + r_n$ を代入すると

```math
\begin{align}
(\boldsymbol{I} + (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{x}_n \boldsymbol{x}_n^\top) \hat{\boldsymbol{w}}
 &= \hat{\boldsymbol{w}}_{(n)} + (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{x}_n (\boldsymbol{x}_n^\top \hat{\boldsymbol{w}} + r_n)
\end{align}
```
両辺から $(\boldsymbol{X}\_{(n)}^\top \boldsymbol{X}\_{(n)})^{-1} \boldsymbol{x}\_n \boldsymbol{x}\_n^\top \hat{\boldsymbol{w}}$ を引くと

```math
\begin{align}
  \hat{\boldsymbol{w}} &= \hat{\boldsymbol{w}}_{(n)} + (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{x}_n r_n
\end{align}
```
このあと導出する式：

```math
\begin{align}
(\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{x}_n \tag{1}
 &= \frac{1}{1 - h_n} (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n \\
h_n
 &\equiv \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n
\end{align}
```
を用いると

```math
\begin{align}
  \hat{\boldsymbol{w}} &= \hat{\boldsymbol{w}}_{(n)} + \frac{r_n}{1 - h_n} (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n
\end{align}
```
を得ます。

## Leave-One-Out予測値
Leave-One-Out回帰係数を用いて、Leave-One-Out予測値（サンプルnを用いずに回帰係数を求めて、サンプルnに対して予測）は

```math
\begin{align}
\boldsymbol{x}_n^\top \hat{\boldsymbol{w}}_{(n)}
 &= \boldsymbol{x}_n^\top \left(\hat{\boldsymbol{w}} - \frac{r_n}{1 - h_n} (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n\right) \\
 &= \boldsymbol{x}_n^\top \hat{\boldsymbol{w}} - \frac{r_n}{1 - h_n} \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n \\
 &= \boldsymbol{x}_n^\top \hat{\boldsymbol{w}} - \frac{h_n}{1 - h_n} r_n
\end{align}
```
を得ます。**Leave-One-Outでない予測値 $\boldsymbol{x}_n^\top \hat{\boldsymbol{w}}$ から、$\frac{h_n}{1 - h_n} r_n$ を差し引いたものが、Leave-One-Outな回帰係数による予測値になっています。**

## Leave-One-Out残差
Leave-One-Outな残差は

```math
\begin{align}
y_n - \boldsymbol{x}_n^\top \hat{\boldsymbol{w}}_{(n)}
 &= y_n - \left( \boldsymbol{x}_n^\top \hat{\boldsymbol{w}} - \frac{h_n}{1 - h_n} r_n \right) \\
 &= r_n + \frac{h_n}{1 - h_n} r_n \\
 &= \frac{1}{1 - h_n} r_n \\
 &= \frac{1}{1 - h_n} (y_n - \boldsymbol{x}_n^\top \hat{\boldsymbol{w}})
\end{align}
```
を得ます。Leave-One-Outな残差を、Leave-One-Outでない残差で表現できました。**Leave-One-Outでない残差を (1 - h_n) で割るだけでLeave-One-Outな残差が得られます。**

## (1)式の導出
まず $(\boldsymbol{X}\_{(n)} \boldsymbol{X}\_{(n)}^\top)^{-1}$ から $\boldsymbol{X}\_{(n)}$ の表記を除くことを考えます。
ブロック行列

```math
\begin{align}
  \left(
    \begin{array}{ll}
      \boldsymbol{A} & \boldsymbol{B} \\
      \boldsymbol{C} & \boldsymbol{D}
    \end{array}
  \right)
\end{align}
```
の逆行列から導かれるSherman-Morrison-Woodburyの公式：

```math
\begin{align}
(\boldsymbol{A} - \boldsymbol{B} \boldsymbol{D}^{-1} \boldsymbol{C})^{-1}
 &= \boldsymbol{A}^{-1} + \boldsymbol{A}^{-1} \boldsymbol{B} \boldsymbol{S}^{-1} \boldsymbol{C} \boldsymbol{A}^{-1} \\
\boldsymbol{S}
 &\equiv \boldsymbol{D} - \boldsymbol{C} \boldsymbol{A}^{-1} \boldsymbol{B}
\end{align}
```
に

```math
\begin{align}
  \left(
    \begin{array}{cc}
      \boldsymbol{A} & \boldsymbol{B} \\
      \boldsymbol{C} & \boldsymbol{D}
    \end{array}
  \right)
  &= \left(
    \begin{array}{cc}
      \boldsymbol{X} \boldsymbol{X}^\top & \boldsymbol{x}_n \\
      \boldsymbol{x}_n^\top & 1
    \end{array}
  \right)
\end{align}
```
を代入すると

```math
\begin{align}
\boldsymbol{A} - \boldsymbol{B} \boldsymbol{D}^{-1} \boldsymbol{C}
 &= \boldsymbol{X} \boldsymbol{X}^\top - \boldsymbol{x}_n \boldsymbol{x}_n^\top = \boldsymbol{X}_{(n)} \boldsymbol{X}_{(n)}^\top \\
\boldsymbol{S}
 &= 1 - \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n
\end{align}
```
より

```math
\begin{align}
(\boldsymbol{X}_{(n)} \boldsymbol{X}_{(n)}^\top)^{-1}
  &= (\boldsymbol{X} \boldsymbol{X}^\top)^{-1}
  + \frac{(\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1}}
         {1 - \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n}
\end{align}
```
を得ます。両辺に右から $\boldsymbol{x}_n$ を掛けて

```math
\begin{align}
(\boldsymbol{X}_{(n)} \boldsymbol{X}_{(n)}^\top)^{-1} \boldsymbol{x}_n
  &= \left( (\boldsymbol{X} \boldsymbol{X}^\top)^{-1}
   + \frac{(\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1}}
        {1 - \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n} \right) \boldsymbol{x}_n \\
  &= (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n
   + (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n
     \frac{\boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n}
          {1 - \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n} \\
  &= \left(1 + \frac{\boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n}{1 - \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n} \right) (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n \\
  &= \frac{1}{1 - \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n} (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n \\
  &= \frac{1}{1 - h_n} (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n \\
h_n
  &\equiv \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top)^{-1} \boldsymbol{x}_n
\end{align}
```
を得ます。

## L2正則化最小二乗法（リッジ回帰）の場合
導出の $\boldsymbol{X}^\top \boldsymbol{X}$ になっている部分を $\boldsymbol{X}^\top \boldsymbol{X} + \lambda \boldsymbol{I}$ に置き換えれば、L2正則化最小二乗法（リッジ回帰）の場合の導出となり、$h_n$ は

```math
\begin{align}
h_n
 &\equiv \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top + \lambda \boldsymbol{I})^{-1} \boldsymbol{x}_n
\end{align}
```

となりますが、残差の関係式：

```math
\begin{align}
y_n - \boldsymbol{x}_n^\top \hat{\boldsymbol{w}}_{(n)}
 &= \frac{1}{1 - h_n} (y_n - \boldsymbol{x}_n^\top \hat{\boldsymbol{w}})
\end{align}
```
は変わりません。

## 参考
- [Proof of LOOCV formula - Cross Validated](https://stats.stackexchange.com/questions/164223/proof-of-loocv-formula)