楠岡 成雄「Rademacher 複雑度と正則化」
§1 初めに

$(E, \mathcal {E})$ は可測空間、$\Theta$ は距離空間とする。$\Theta$ をパラメータの集合と考える。$F : E\times \Theta \rightarrow \mathbb {R}$ は可測関数であり、$F(x, \cdot ) : \Theta \rightarrow \mathbb {R},$ $x\in E,$ は連続とする。$E$-値確率変数 $X$ に対して $$\begin{align*} F_0(\theta ) = \mathrm {E}[F(X, \theta )], \ \ \ \ \ \theta \in \Theta \end{align*}$$ とおき、$F_0(\theta )$ を最小とする $\theta _0\in \Theta$ を見つけるという問題を考える。このような問題は機械学習 (教師付学習、強化学習) などにしばしば現れる。しかし、多くの場合、$X$ の確率法則が不明である、あるいはわかっていても $F_0(\theta )$ の計算が容易でないといった理由により $\theta _0$ を見つけることは困難であることが多い。

この問題を解決する方法として $X$ の確率法則と同じ確率法則を持つ独立な $E$-値確率変数 $X_1, \ldots , X_n$ が与えられていて、 $$\begin{align*} \hat {F}_n(\theta ) = \frac{1}{n}\sum ^n_{i=1}F(X_i, \theta ) \end{align*}$$ は計算可能として考えることがある。この時、 $$\hat {\theta }_0 = \mathrm {argmin}_{\theta \in \Theta }\hat {F}_n(\theta )$$ を $\theta _0$ の「推定値」として良いであろうか？

今、$F(x, \theta )$ の例として以下のような線形モデルを考える。$g_i : E\rightarrow \mathbb {R},$ $i = 1, \ldots , m,$ は可測関数、$\Theta = \mathbb {R}^m$ とし、$L : \mathbb {R}\times E\rightarrow [0, \infty )$ が与えられており、 $$F(x, \theta ) = L\left(\sum ^m_{i=1}\theta _ig_i(x), x\right), \ \ \ \ \ x\in E, \ \theta \in \mathbb {R}$$ とする。もし $m > n$ であれば $$\hat {F}_n(\hat {\theta }) = \frac{1}{n}\sum ^n_{i=1}F(X_i, \hat {\theta }) = \min _{\theta \in \mathbb {R}^m}\hat {F}_n(\theta )$$ となる $\hat {\theta}$ が無限に存在する。これが、overfitting や過学習と呼ばれる問題である。このような問題は、まず最尤推定量に関する問題として現れた。この問題に対する赤池さんの答え (AIC) は「パラメータの次元は観測数 $n$ に対してあまり大きくなってはならない」ということである。しかし近年の「機械学習」においてはパラメータの次元 $\gg n$ となることが普通である。そのために正則化という概念が生まれた。

正則化とは、正則化関数 $\phi : \Theta \rightarrow [0, \infty )$ 及び $\lambda > 0$ を選び $$\hat {F}_n(\theta ) + \lambda \phi (\theta )$$ を最小にする $\theta$ を選ぶという考えである。

正則化関数の例としては以下のようなものがある。

($L^1$ 正則化)  $\phi (\theta ) = ||\theta ||_1 = \sum ^m_{i=1}|\theta _i|$
($L^2$ 正則化)  $\phi (\theta ) = ||\theta ||_2 = \left(\sum ^m_{i=1}|\theta _i|^2\right)^{1/2}$ または $\phi (\theta ) = ||\theta ||^2_2 = \sum ^m_{i=1}|\theta _i|^2$

ここで以下のような疑問が生ずる。

1. 正則化の役割は overfitting を回避するだけか？
2. どのような正則化関数を用いるべきか？
3. $\lambda$ をどこまで小さくとれるのか？

これらに対する一つの解答を与えるのが本ノートの目的である。

なお、参考文献として 金森 敬文「統計的学習理論」(講談社サイエンティフィク　機械学習プロフェッショナルシリーズ (MLP), 2015) がある。