2つの正則化が特定条件下において等価であることを示す
この記事は東大電気電子情報系アドベントカレンダーの12/20の記事となっています。
Deep Learningの理論系の本を読んでいる時, うおおとなった帰結をまとめてみました。
この記事の内容はDeep Learning(2015, Ian Goodfellow et al)のp165, p179辺りの内容となります。世界的な教科書のため, 一度は読んでみましょう。
この記事はベクトル解析レベルの数学, 最急勾配法に関する知識,正則化について聞いたことがあるよレベルの読者を想定しています。
かなり数式が長いので手元に紙を用意して読んでください
TR;DR
- 正則化の手法である$L^2$正則化と早期打ち切りが特定の条件下において等しい
正則化に関して簡単におさらい
機械学習では訓練データを上手く予測できるようパラメーターを調整して訓練を行います。
しかしそれでは訓練データにフィットしてもテストデータにはフィットしないという過学習がなされたモデルが出来上がってしまいます。
そこで, パラメーターの値に対する制約を課すことで, 訓練データへの過剰な適合を抑え, テストデータへのフィッティング性能を向上させることが正則化と呼ばれています。
この時, 最小化する目的関数を$J(w;X,y)$とすると($w$はパラメータ, $X$は学習データ, $y$は正解データ), 正則化された目的関数$\tilde{J}(w;X,y)$はパラメーターペナルティ$Ω(w)$を用いて以下の通りとなります。
$$
\tilde{J}(w;X,y) = J(w;X,y) + αΩ(w)
$$
ここでαは正則化の強さを示す度合いであり, ハイパーパラメーターとなります。
L2正則化
$L^2$正則化は上の式において$Ω(w)=\frac{1}{2}\lVert{w}\rVert{}^{2}_{2}$とした場合にあたります。この時, 正則化された目的関数$\tilde{J}(w;X,y)$は
$$
\tilde{J}(w;X,y) = J(w;X,y) + \frac{α}{2}\lVert{w}\rVert{}^{2}_{2}
$$
となります。これをパラメーターに関して勾配を計算すると
$$
\nabla_{w}\tilde{J}(w;X,y) = \nabla_{w}{J(w;X,y)} + αw
$$
となります。
さて最適なパラメーターでは$\nabla_{w}\tilde{J}(w;X,y)=0$となることが期待されます。
ここからがズルイ議論で, わざわざTR;DRで特定の条件下という文言を追加した理由ではあるのですが, 最適な$J(w;X,y)$を最適化していくときの最適なパラメーターを$w^{*}$として$\nabla_{w}{J(w^{*};X,y)}=0$, この時, $J(w;X,y)$を$w^{*}$近傍で二次まで展開することを考えると、$\nabla_{w}{J(w^{*};X,y)}=0$より,
$$
J(w;X,y) = J(w^{*};X,y)+\dfrac{1}{2}(w-w^{*})^{T}H(w-w^{*})
$$
となります。ただし, $H$は$w^{*}$で評価される$w$に関するヘッセ行列です。
$w^{*}$は$J(w;X,y)$が最小となる位置であるため, $H$は半正定値であることも言えます。
ここで、二次近似を用いて$\nabla_{w}\tilde{J}(w;X,y)$を表現すると,
$$
\nabla_{w}{J(w;X,y)} = H(w-w^{*})
$$
であるから,
$$
\nabla_{w}\tilde{J}(w;X,y) = H(w-w^{*}) + αw
$$
となります。ここで, $\nabla_{w}\tilde{J}(w;X,y) = 0$を満たすような正則化した時の最適なパラメーターを$\hat{w}$とすると、単位行列を$I$として
$$
H(\hat{w}-w^{*}) + α\hat{w} = 0
$$
$$
\hat{w} = (H+αI)^{-1}Hw^{*}
$$
となります。ここで$H$は実対称行列なので, 対角行列$\Lambda$と直交行列$Q$を用いて$H = Q \Lambda Q^{T}$と表せることを用いると、
$$
\hat{w} = (Q \Lambda Q^{T}+αI)^{-1}Q \Lambda Q^{T}w^{*}
$$
$$
\hat{w} = (Q (\Lambda +αI)Q^{T})^{-1}Q \Lambda Q^{T}w^{*}
$$
$$
\hat{w} = Q(\Lambda +αI)^{-1}\Lambda Q^{T}w^{*}
$$
$$
Q^{T} \hat{w} = (\Lambda +αI)^{-1}\Lambda Q^{T}w^{*}
$$
を最適なパラメーター$\hat{w}$は満たします。ここまでで$L^2$最適化の議論は終えます。暇な方は$α$を大小させた時にどういう変化をするかを少し考えてみてください。
ここまでの条件
- 最適なパラメーター$w^{*}$近傍で損失関数$J(w;X,y)$を展開した時の最適なパラメーター$\hat{w}$を求めた
早期打ち切り
早期打ち切りは検証誤差が小さくなるまでパラメーターの更新を続け, 検証誤差の最小値が一定回数更新されなかったらそこで訓練を打ち切るという学習手法である。
打ち切りのない学習を無限回のパラメーター更新とすると,
早期打ち切りはパラメーターの更新を$τ$回することに対応する。(正直ほんまか？と思う)
最適化対象の損失関数を$J(w;X,y)$とする。これを$L^2$正則化と同じように最適パラメーター$w^{*}$の近傍で展開すると, $L^2$正則化と同じ議論により
$$
J(w;X,y) = J(w^{*};X,y)+\dfrac{1}{2}(w-w^{*})^{T}H(w-w^{*})
$$
従って,
$$
\nabla_{w}{J(w;X,y)} = H(w-w^{*})
$$
これを学習率$\epsilon$で最急勾配法によりパラメーターを更新することを考えると
$$
w^{(t)} = w^{(t-1)} - \epsilon{\nabla_{w}{J(w;X,y)}}
$$
$$
w^{(t)} = w^{(t-1)} - \epsilon{H(w^{(t-1)}-w^{*})}
$$
両辺に$w^{*}$を引くと
$$
w^{(t)} - w^{*} = (I - \epsilon{H}) (w^{(t-1)}-w^{*})
$$
ヘッセ行列$H$を$L^2$正則化と同じように固有値分解して$H = Q \Lambda Q^{T}$と表すと,
$$
w^{(t)} - w^{*} = (I - \epsilon{Q \Lambda Q^{T}}) (w^{(t-1)}-w^{*})
$$
$$
Q^{T}(w^{(t)} - w^{*}) = (I - \epsilon{\Lambda})Q^{T}(w^{(t-1)}-w^{*})
$$
ここで,$w^{(0)} = 0$として上の漸化式を解く、$w^{(0)} = 0$とすることの妥当性としては, Deep Learning(2015, Ian Goodfellow et al)によると, この後行う議論は、ほかのどんな初期値$w^{(0)}$に対してもなりたつので$w^{(0)} = 0$として簡単にしている(らしい)
$w^{(0)} = 0$として上の漸化式を解くと,
$$
Q^{T}(w^{(τ)} - w^{*}) = (I - \epsilon{\Lambda})^{τ}Q^{T}(w^{(0)}-w^{*})
$$
$$
Q^{T}w^{(τ)} = [I-(I - \epsilon{\Lambda})^{τ}]Q^{T}w^{*}
$$
となる。
ここまでの条件
- $L^2$正則化において, 最適なパラメーター$w^{*}$近傍で損失関数$J(w;X,y)$を展開した時の最適なパラメーター$\hat{w}$を求めた
- 早期打ち切りにおいて, 最適なパラメーター$w^{*}$近傍で損失関数$J(w;X,y)$を展開した時, 最急勾配法でτ回更新した時のパラメーター$w^{(τ)}$を求めた
L2最適化により得られる最適なパラメーターと早期打ち切りにより得られるパラメーターが等価であることの提示
ここまでで行った正則化により求められたパラメーターが成り立つ式を再度提示します。
$L^2$正則化の場合の最適なパラメーター$\hat{w}$
$$
Q^{T} \hat{w} = (\Lambda +αI)^{-1}\Lambda Q^{T}w^{*}
$$
$L^2$正則化の場合の最適なパラメーター$\hat{w}$が満たす式は, 式変形により以下の式に変形できます。
$$
Q^{T} \hat{w} = (\Lambda +αI)^{-1}\Lambda Q^{T}w^{*}
$$
$$
Q^{T} \hat{w} = (\Lambda +αI)^{-1}(\Lambda +αI - αI)Q^{T}w^{*}
$$
$$
Q^{T} \hat{w} = (I - (\Lambda +αI)^{-1}α)Q^{T}w^{*}
$$
早期打ち切りの場合のパラメーター$w^{(τ)}$は以下の通りになりました。
$$
Q^{T}w^{(τ)} = [I-(I - \epsilon{\Lambda})^{τ}]Q^{T}w^{*}
$$
いかがでしたか?
$\hat{w}$と$w^{(τ)}$は$(\Lambda +αI)^{-1}α = (I - \epsilon{\Lambda})^{τ}$の時に等しくなることがわかりました。このような等号が実際に成り立つことを示してみましょう。
$\Lambda = \text{diag}(\lambda_{1}, \lambda_{2}, ..., \lambda_{i}, ...)$とする時, $(\Lambda +αI)^{-1}α$と$(I - \epsilon{\Lambda})^{τ}$のそれぞれ対角成分$i$番目に注目すると,
$$
(1-\epsilon λ_{i})^{τ} = \dfrac{α}{α+\lambda_{i}}
$$
これの両辺を対数を取ると
$$
τ\log{(1-\epsilon λ_{i})} = \log{(\dfrac{1}{1+\dfrac{\lambda_{i}}{\alpha}})}
$$
$$
τ\log{(1-\epsilon λ_{i})} = -\log{(1+\dfrac{\lambda_{i}}{\alpha})}
$$
これを
$$
\epsilon λ_{i} \ll 1 , \dfrac{\lambda_{i}}{\alpha} \ll 1
$$
のもとで$\log{(1+x)} \approx x$の近似を用いると
$$
τ\log{(1-\epsilon λ_{i})} = -\log{(1+\dfrac{\lambda_{i}}{\alpha})}
$$
$$
-τε\lambda_{i} \approx -\dfrac{\lambda_{i}}{\alpha}
$$
$$
α \approx \dfrac{1}{τε}
$$
いかがでしたか?
$$
\epsilon λ_{i} \ll 1 , \dfrac{\lambda_{i}}{\alpha} \ll 1
$$
のもとで$α \approx \frac{1}{τε}$と設定すると, $(\Lambda +αI)^{-1}α = (I - \epsilon{\Lambda})^{τ}$が成り立ち, $L^2$正則化で求められたパラメーターと早期打ち切りで求められたパラメーターが近似的に等しくなることがわかりました。
結果についてのさらなる考察
$$
α \approx \dfrac{1}{τε}
$$
についてもう少し自分なりの考察をします。
左辺は$L^2$正則化のハイパーパラメーター, 右辺は早期打ち切りのハイパーパラメーターで整理を行いました。
これは$\epsilon$が小さいほどαが大きくなるため, $L^2$正則度合いが大きくなることを表しています。これは学習率が小さいほど正則度合いが大きくなると言い換えることもできます。
次に, $τ$が大きいほど$L^2$正則度合いが小さくなります。これは$τ$が大きいほどどんどん学習が進み, 過学習が進むことからも明らかでしょう。
また, 上の式は学習率$τ$に対して$α \approx \frac{1}{τε}$となるように$\epsilon$を設定することで, ハイパーパラーメーター$α$を設定したのと同じ$L^2$正則度合いが得られると考えることもできます。
ハイパーパラメーターを決める際の一つの理論的な決め方の指標になりそうです。
いかがでしたか?
まとめると,
条件
- $L^2$正則化において, 最適なパラメーター$w^{*}$近傍で損失関数$J(w;X,y)$を展開した時の最適なパラメーター$\hat{w}$を求めた
- 早期打ち切りにおいて, 最適なパラメーター$w^{*}$近傍で損失関数$J(w;X,y)$を展開した時, 最急勾配法でτ回更新した時のパラメーター$w^{(τ)}$を求めた
- $\epsilon λ_{i} \ll 1 , \frac{\lambda_{i}}{\alpha} \ll 1$
の元で,
$$
α \approx \dfrac{1}{τε}
$$
とすると, $(\Lambda +αI)^{-1}α = (I - \epsilon{\Lambda})^{τ}$が近似的に成り立ち, $L^2$正則化で求められたパラメーターと早期打ち切りで求められたパラメーターが近似的に等しくなることがわかりました。
たまには数式で機械学習を考えてみるのも楽しいかもしれません。