一般的に教師あり学習モデルは，任意の損失関数に対してデータの「当てはまり具合」を最適化するように関数 $f(x)$ を選択する．

しかし，この関数 $f(x)$ が与えられたデータに対してあまりに複雑すぎると，今現在手元にある学習データのみに適合してしまい，未知のデータに弱くなってしまう過学習(over fitting)を引き起こしてしまう．過学習は，モデルが複雑な場合に訓練誤差と汎化誤差の間に大きな差が生じてしまうことに起因する．

正則化

過学習を避ける方法として，より単純なモデルを選ぶといったモデルの選択の他に，正則化(regularization)が存在する．

ここで，モデルの選択も正則化も，データにふさわしい適切な複雑さの関数を選択するという意味では本質的には同じと捉えられる．

正則化は，モデルの訓練誤差を最小化する際，そのモデルの「複雑」さに対する罰則を加えて最小化を行う．この「複雑さ」を定義する関数を正則化関数(regularization function)と呼ぶ．正則化関数を $R(f)$ とすると，一般的な正則化学習法は，

$\min_{f\in{F}} \sum^{n}_{i=1} l(y_{i}, f(x_{i})) + \lambda R(f)$

ここで $\lambda > 0$ は正則化の強さを調整するパラメータ．上式は，データへの当てはまり具合を表す第一項とモデルの複雑さへの罰則を表す第二項から成り立っている．この罰則項の働きによってモデルの過学習を抑えることができる．

線形モデル $f(x) = \beta^{T}x$ について，正則化項 $R(f) = R(\beta)$ としたとき，以下のような正則化関数がよく用いられる．

リッジ正則化 [1]：

$R(\beta) = ||\beta||^{2}_{2} := \sum^{p}_{j=1} \beta^{2}_{j}$

L1正則化 [2]：

$R(\beta) = ||\beta||_{1} := \sum^{p}_{j=1} |\beta_{j}|$

ブリッジ正則化 [3]：ある $\gamma > 0$ を用いて，

$R(\beta) = ||\beta||^{\gamma}_{\gamma} := \sum^{p}_{j=1} |b_{j}|^{\gamma}$

エラスティックネット正則化 [4]：ある $\theta \in [0, 1$ ]を用いて，

$R(\beta) = \theta ||\beta||_{1} + (1 - \theta) ||\beta||^{2}_{2}$

SCAD (smoothly clipped absolute deviation) [5]：ある $\lambda > 0$ と $a > 1$ を用いて，

$R(\beta) =$

$\sum^{p}_{j=1} \lambda |\beta_{j}| \ \ (|\beta_{j}| \leq \lambda)$

$\sum^{p}_{j=1} - \frac{|\beta_{j}|^{2} - 2a \lambda |\beta_{j}| + \lambda^{2}}{2(a - 1)}$

$\sum^{p}_{j=1} \frac{(a+1) \lambda^{2}}{2}$

上記から，ブリッジ正則化はL1正則化とリッジ正則化の一般化であることがわかる（ $\gamma = 1$ のときL1正則化， $\gamma = 2$ のときリッジ正則化）．また，SCAD正則化は非凸関数であるが， $\beta_{j} \to \infty$ で勾配が0になるため推定量にバイアスが乗りにくい．

最も単純なモデルである線形モデルであったとしても，次元が高い場合は自由度が高くなり，過学習を起こす可能性が存在してしまうため，上記のような正則化を用いることで過学習をを回避することができる．

f:id:noconocolib:20190312181943p:plain — 各正則化項のプロット

スパース正則化としてのL1正則化

L1正則化は，学習結果 $\beta$ をスパースにさせやすいという性質を持っている．ここで学習結果 $\beta$ がスパースであるとは， $\beta$ の多くの成分が0であるという意味．

これは，予測に必要のない無駄な特徴量を切り捨てて，特徴選択を行っているとみなせる．

古くから，そうした特徴選択を実現する手法として赤池情報量基準(Akaike information criterion, AIC)が用いられてきた．例えば回帰において，ノイズが分散が $\sigma^{2}$ のガウス分布に従っているとき， $l(y, f) = -\log (\frac{1}{\sqrt{2\pi \sigma^{2}}} \exp (- \frac{(y - f)^{2}}{2\sigma^{2}}))$ であるような設定を考える．このとき，赤池情報量基準に従った特徴選択は，

$\min_{\beta \in \mathbb{R}^{p}} 2 \sum^{n}_{i=1} l(y_{i}, x_{i}^{T} \beta) + 2 ||\beta||_{0}$

ここで，p $||\beta||_{0}$ は $\beta$ の非ゼロ要素の数で， $L_0$ ノルムと呼ばれる． $||\beta||_{0}$ を訓練誤差に足すのは，汎化誤差と訓練誤差の差を補うためであり，特徴量の数を罰則として訓練誤差に足すことで，学習結果をスパースにできる．より多くの特徴量を用いることは，それだけ複雑な関数を用いることに等しくなり，現在手元にある訓練データに当てはまりやすく，訓練誤差と汎化誤差の乖離が大きくなってしまう．AICはこのような乖離を補正するためには $2||\beta||_{0}$ を足せば良いと主張している．

$p$ がサンプル数より十分小さいとき，

$\frac{1}{n} E_{x_{i}, y_{i}} s\sum^{n}_{i+1} l(y_{i}, x_{i}^{T} ||\beta||_{0})$

$= E_{x_{i}, y_{i}} (E_{X, Y} (2l(Y, X^{T} \beta) ))+ O(\frac{1}{n^{2}})$

となる．左辺は目的関数の訓練データの出方に対する期待値，右辺の第一項は汎化誤差の期待値，第二項はサンプルサイズ $n$ が増えるに連れて消えていく項になる．

AICは汎化誤差の不偏推定量であり，AICを最小化する推定量は過学習を避けて正しく汎化誤差を小さくすることができる．しかし，次元 $p$ が大きい場合，AICの最小化は組み合わせ最適化問題となり，NP困難であることが知られている．

そこで， $L_0$ ノルムの代わりに $L1$ ノルムという凸関数を用いるというのが $L1$ 正則化の発想．実際， $L1$ ノルムは $L_0$ ノルムを下から抑える最大の凸関数になっており，最適化の際に非常に都合が良い．

また，L1正則化を用いた線形回帰手法をLassoと呼ぶ．

L1正則化のようにスパースな学習結果を導く正則化をスパース正則化という．

スパース正則化

スパース正則化は，高次元な学習問題において非常に強力な手法である．ここで，スパース性をより広く，ある種の低次元性と捉えると，他にも様々なスパース正則化が考えられる．

グループ正則化

特徴量がいくつかのグループに分かれていると仮定する．グループ正則化は，同じグループに属する特徴量をまとめて一つの特徴量のように扱うスパース正則化である．グループをそれぞれインデックス集合 $g\subseteq \{ 1,\dots,p\} (k=1,\dots,M)$ とする．インデックス集合 $g$ に対する $\beta\in\mathbb{R}^{p}$ の部分ベクトルを $\beta_{g}$ とすると，グループ正則化は以下で表される．

$||\beta||_{G} = \sum^{M}_{k=1} ||\beta_{gk}||_{2}$

一般化連結正則化

一般連結正則化は，あるグラフに関して隣接した変数は同じ値になるようにする正則化である．グラフ $G = (V, E)$ について，一般化連結正則化は，

$||\beta||_{Fused} = \sum_{(i, j)\in{E}} |\beta_{i} - \beta_{j}|$

として与えられる．

トレースノルム正則化

トレースノルム正則化は，低ランク行列を学習したい場合に用いられる． $\beta$ を並び替えた行列 $B$ を考え，その $k$ 番目の特異値を $\sigma_{k} (B) \geq 0$ と表すと，トレースノルム正則化は，

$||B||_{tr} = \sum^{\min \{q, r\}}_{k=1} \sigma_{j} (B)$

となる．これは特異値ベクトルへの $L1$ 正則化とみなせるので，スパースな特異値を持つ行列，すなわち低ランクな行列が学習されることになる．

正則化関数の組み合わせ

以上のように，正則化関数には多くの例が存在する．これらの正則化関数は，単独で用いるだけでなく，複合して適用することもできる．

正則化関数 $h_{1},\dots,h_{K}$ の組み合わせ方には，例えば以下のような方法がある．

和型：

$\hat{h} (\beta) = \sum^{K}_{k=1} h_{k} (\beta)$

畳み込み型

$\underline{h} (\beta) = \inf \sum^{K}_{k=1} h_{k} (\beta_{k}) =: (h_{1} * \cdots * h_{K})$

ちなみに，和型と畳込み型の２つの形式には，以下のような双対関係が成り立っている．

$(h_{1} + \dots +h_{K})^{*} (\beta) = (h^{*}_{1} \cdots h^{*}_{K}) (\beta) (\forall{\beta \in \mathbb{R}^{p}})$

ここで $f^{*}$ は凸関数 $f$ のルシャンドル変換．

参考文献

[1] Hoerl, Arthur E., and Robert W. Kennard. "Ridge regression: Biased estimation for nonorthogonal problems." Technometrics 12.1 (1970): 55-67.
[2] Tibshirani, Robert. "Regression shrinkage and selection via the lasso." Journal of the Royal Statistical Society: Series B (Methodological) 58.1 (1996): 267-288.
[3] Frank, LLdiko E., and Jerome H. Friedman. "A statistical view of some chemometrics regression tools." Technometrics 35.2 (1993): 109-135.
[4] Zou, Hui, and Trevor Hastie. "Regularization and variable selection via the elastic net." Journal of the royal statistical society: series B (statistical methodology) 67.2 (2005): 301-320.
[5] Fan, Jianqing, and Runze Li. "Variable selection via nonconcave penalized likelihood and its oracle properties." Journal of the American statistical Association 96.456 (2001): 1348-1360.