はじめに
最小二乗法やリッジ回帰（L2正則化最小二乗法）の場合、Leave-One-Out Cross-Validationには解析解があります。導出を久しぶりに追ったのでメモしました。
最小二乗法のLeave-One-Out誤差の解析解の導出
最小二乗法の解析解は
\begin{align}
\hat{\boldsymbol{w}} = (\boldsymbol{X}^\top \boldsymbol{X})^{-1} \boldsymbol{X}^\top \boldsymbol{y}
\end{align}
で、Leave-One-Out二乗誤差は
\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回帰係数
まず
\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}
で、
\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}
より
\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}$ を掛けると
\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$ を代入すると
\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}}$ を引くと
\begin{align}
\hat{\boldsymbol{w}} &= \hat{\boldsymbol{w}}_{(n)} + (\boldsymbol{X}_{(n)}^\top \boldsymbol{X}_{(n)})^{-1} \boldsymbol{x}_n r_n
\end{align}
このあと導出する式：
\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}
を用いると
\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に対して予測）は
\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な残差は
\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)}$ の表記を除くことを考えます。
ブロック行列
\begin{align}
\left(
\begin{array}{ll}
\boldsymbol{A} & \boldsymbol{B} \\
\boldsymbol{C} & \boldsymbol{D}
\end{array}
\right)
\end{align}
の逆行列から導かれるSherman-Morrison-Woodburyの公式：
\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}
に
\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}
を代入すると
\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}
より
\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$ を掛けて
\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$ は
\begin{align}
h_n
&\equiv \boldsymbol{x}_n^\top (\boldsymbol{X} \boldsymbol{X}^\top + \lambda \boldsymbol{I})^{-1} \boldsymbol{x}_n
\end{align}
となりますが、残差の関係式：
\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}
は変わりません。