モチベーション
本記事で一番書きたいことは、ridge正則化における重みの最適解の中にでてくる逆行列についてで、$\mathbf {X^\top X}$が正則でなくても$\mathbf{X^\top X + \lambda I}$の逆行列が常に存在することについての軽い証明です。
いろんな記事を探ってみましたが、この部分についてちゃんと説明しているものが見当たらなかったので、参考文献をもとに勉強したことをアウトプットとしてまとめてみます。
ridge正則化における解析的解
Ridge回帰はモデルが複雑になるのを抑制するために二乗和誤差に重みパラメータ$\mathbf w$の二乗ノルム$||\mathbf w||_2^2$に正則化パラメータ$\lambda>0$を掛けた項を加えるものです。
L = \frac{1}{2} \sum_{n=1}^N (\hat y_n - t_n)^2 + \frac{\lambda}{2}\|\mathbf w\|_2^2
って感じです。
回帰モデルの式として行列とベクトルを用いて表現すると
y(\mathbf X) = \mathbf{X w}
です。これを目的関数Lにぶちこんで$\mathbf w$に関する微分を0とおくと
\hat{\mathbf w} = (\mathbf{X^\top X + \lambda I})^{-1}\mathbf{X^\top t}
という解析的な解が得られます。
最小二乗法の時は$\lambda=0$のときに対応するわけですが、そのときは実対称行列$\mathbf {X^\top X}\in \mathbb R^{d\times d}$が正則でないと逆行列は計算できません。
正則でない場合については「ムーアペンローズの擬似逆行列$\mathbf X^\dagger$を使いますよ」という補足がよく参考書とかでは入ります。いつものやつです。
でも$\lambda > 0$の場合、つまりridge正則化をするときはこのような注釈は特に入りません。その理由を次項で説明します。
逆行列が存在するかしないか
$\mathbf {X^\top X}$が実対称行列であることに着目すると、次のように直交行列$\mathbf P$を用いて対角化できます。
\mathbf{X^\top X} = \mathbf{P\Gamma P}^\top = \mathbf P \rm{diag}(\gamma_1,\dots,\gamma_d) \mathbf P^\top
ただし$\mathbf \Gamma$は$\mathbf {X^\top X}$の固有値$(\gamma_1 \ge \dots \ge \gamma_d\ge0)$からなる対角行列。
ここで最小の固有値$\gamma_d$について$\gamma_d > 0$とします。
このとき$\mathbf{X^\top X}$の逆行列について
\begin{aligned}
(\mathbf {X^\top X})^{-1} &= (\mathbf{P\Gamma P^\top})^{-1}\\
&=(\mathbf{P \rm{diag}(\gamma_1,\dots,\gamma_d)\mathbf P}^\top)^{-1}\\
&=\mathbf{P}\rm{diag}(1/\gamma_1,\dots,1/\gamma_d)\mathbf P^\top\\
\end{aligned}
いま、$\gamma_d \rightarrow 0$の極限を考えると、$1/\gamma_d \rightarrow \infty$となり、逆行列は計算できなくなります。
さて、ここからが本題ですが、ridge正則化の時に現れる$\mathbf{X^\top X + \lambda I}$の逆行列は常に存在するのでしょうか。
先ほどと同様に$\mathbf{X^\top X}$の対角化を用いて考えてみます。
\begin{aligned}
(\mathbf {X^\top X + \lambda I})^{-1} &= \{\mathbf{P\Gamma P}^\top +\lambda \mathbf I \} ^{-1}\\
&=\{\mathbf{P(\Gamma + \lambda I)P^\top} \}^{-1}\\
&=\mathbf{P}(\mathbf{\Gamma+ \lambda I})^{-1}\mathbf{P}^\top \\
&=\mathbf{P}\rm{diag}(1/(\gamma_1 + \lambda),\dots,1/(\gamma_d + \lambda))\mathbf{P}^\top
\end{aligned}
途中の式変形では直交行列の性質を用いました。
\begin{aligned}
\mathbf{P}^{-1} &= \mathbf{P}^\top\\
\mathbf{PP^\top} &=\mathbf{P^\top P} = \mathbf I
\end{aligned}
ここでも$\gamma_d \rightarrow 0$の極限を考えてみると、$1/(\gamma_d + \lambda) \rightarrow 1/\lambda > 0(\because\lambda > 0)$となり、逆行列が計算できます。
したがって、$\mathbf{X^\top X}$の逆行列が存在しない場合においても、$\mathbf{X^\top X + \lambda I}$の逆行列は常に存在するといえます。