統計的学習理論と正則化に関するちょっと数理的な基礎

今回は機械学習でよく出てくる正則化の数理的基礎についてまとめたいと思います． ちょっと数理的なお話が多くなりますが， 大学院に居たときも今の職場で話しているときにも，この辺の事を理解している人は意外と多くないのかなと思ったので， 記事にしてみました． なお，本記事の内容の大部分は

• 金森敬文. (2015). 統計的学習理論 (機械学習プロフェッショナルシリーズ).

を参考に書いています．

一般的な学習理論のお話

回帰にしろ分類にしろ，機械学習の理論はある程度統一的に扱うことが出来ます． 目的変数$y$が離散変数であれば分類問題になりますし，連続変数であれば回帰になります． ここでは，回帰・分類を統一的に扱い，学習理論一般に関する説明を少しだけしたいと思います．

入力ベクトルを$\boldsymbol{X}\in \mathcal{X} \subset \mathbb{R}^d$， 目的変数を$Y\in \mathcal{Y} \subset \mathbb{R}$で表します． $\boldsymbol{X}, Y$はともに確率変数です． 仮説$h$を$h:\mathcal{X} \to \mathcal{Y}$で定義します． 線形回帰の場合なら，仮説集合$\mathcal{H}$が $\mathcal{H} = \left\{ h(\boldsymbol{x}) = \boldsymbol{\beta}^T \boldsymbol{x} + \beta_0 | \beta_0, \cdots, \beta_d \in \mathbb{R} \right\}$ なわけですね． この$h$を決定する，すなわち仮説集合から$h$を選んでくる作業が，最小二乗法などの最適化問題を解くステップになります．

予測損失と経験損失

$h$の決定の部分について，少し一般的に説明します． まず，予測損失$R(h)$と経験損失$\widehat{R}(h)$を定義します： \begin{align} R(h)& := \mathbb{E}_{(\boldsymbol{X}, Y)\sim D}\left[ \ell(h(\boldsymbol{X}) , Y)\right] =\int \ell \left( h(X), Y\right)\, dD, \\ \widehat{R}(h) & := \frac{1}{n}\sum_{i=1}^{n} \ell \left( h(\boldsymbol{X}_i ), Y_i)\right) \end{align} $D$は$(\boldsymbol{X}, Y)$の分布を表します． 本当は$R(h)$を最小にするような$h$を発見したいのですが，一般的にはデータの分布は未知です． ですので，代わりにデータから計算できる$\widehat{R}(h)$を最小化するような$h$を決定します． 「なんで$R(h)$の代わりに$\widehat{R}(h)$を使っても大丈夫なの？」という疑問があると思いますが，それは，$\widehat{R}(h)$が$R(h)$の普遍推定量になっているからです． ちなみに，$(\boldsymbol{X}_{1}, Y_{1}), \cdots, (\boldsymbol{X}_{n}, Y_{n})$が無作為標本（つまりiid）の場合は$\widehat{R}(h)$は$R(h)$に確率収束します．

期待予測損失

データ集合$S=\left\{ (\boldsymbol{X}_1, Y), \cdots, (\boldsymbol{X}_n, Y_n)\right\}$ から得られる仮説を$h_S$で表します． このとき，期待予測損失を \begin{equation} \mathbb{E}_{S\sim D^n} \left[ R(h_S) \right] = \int R(h_{S} )\, dD^n \end{equation} で定義します．

ここで注意するべきなのは，$R(h_S)$に対して$D^n$で期待値を撮とっている，つまり$R(h_S)$は確率変数だということです． もう少し具体的に書けば，$h_S$は$h_S(\boldsymbol{X}; (\boldsymbol{X}_1, Y_1),\cdots, (\boldsymbol{X}_n, Y_n))$と書けて， $R(h_S)$の部分で$(\boldsymbol{X}, Y)$に対して期待値をとり， さらに$(\boldsymbol{X}_1, Y_1),\cdots, (\boldsymbol{X}_n, Y_n)$ に対して分布$D^n$で期待値をとることが出来ます．

近似誤差と推定誤差

ここでは，話を簡単にするために2クラス分類問題を考え，損失関数として0-1 loss を採用します．

仮説集合$\mathcal{H}$の中で$R(h)$を最小にする仮説を$h_{\mathcal{H}}$とします． このとき，任意の$\delta > 0$に対して \begin{equation} \textrm{Pr}\left( R(h_{S}) - R(h_{0}) \leq R(h_{\mathcal{H}}) - R(h_{0}) + \sqrt{\frac{2}{n}\log \frac{2 |\mathcal{H}|}{\delta}} \right), \quad h_0 = \inf_{h: {\rm measurable}} R(h) \label{stochastic inequality 1} \end{equation} が成り立ちます．

これはたとえば，$\delta=0.05$としたときに$R(h_{\mathcal{H}}) - R(h_{0}) + \sqrt{(2/n)\log (2|\mathcal{X}|/\delta)}=c$だとすると， 「$95\%$以上の確率で今回選ばれた仮説$h_S$と一番理想的な仮説$h_0$との差は$c$以下だよ」 ということを教えてくれます． そして，Eq. (\ref{stochastic inequality 1}) における$h_S - h_0$の上界の各項から近似誤差${\rm bias}_{\mathcal{H}}$と 推定誤差${\rm var}_{\mathcal{H}}$を定義します： \begin{align} {\rm bias}_{\mathcal{H}} & = R(h_{\mathcal{H}}) - R(h_{0}), \label{definition of bias} \\ {\rm var}_{\mathcal{H}} & = \sqrt{\frac{2}{n}\log \frac{2 |\mathcal{H}|}{\delta}}. \label{definition of variance} \end{align}

この他にもEq. (\ref{stochastic inequality 1}) はいろいろな事を教えてくれますが，それは最後のおまけに回したいと思います．

なぜ正則化を行うのか？

さて，ここからようやく正則化の話に入ります． Eq. (\ref{definition of bias}), Eq. (\ref{definition of variance}) の定義からも分かるように， 仮説集合$\mathcal{H}_1, \cdots, \mathcal{H}_{M}$が$\mathcal{H}_1 \subset \cdots \subset \mathcal{H}_{M}$を満たすとき \begin{align} & {\rm bias}_{\mathcal{H}_1} \geq \cdots \geq {\rm bias}_{\mathcal{H}_M}, \\ & {\rm var}_{\mathcal{H}_1} \leq \cdots \leq {\rm var}_{\mathcal{H}_M} \end{align} が成り立ちます． つまり，「仮説集合が大きくなるほど近似誤差は小さくなるけど，推定誤差は大きくなる」というトレードオフが成り立っているわけですね． ですので，$\hat{m} = {\mathop{\rm arg~min}\limits}_{m}({\rm bias}_{\mathcal{H}_{m}} + {\rm var}_{\mathcal{H}_{m}})$ として$\mathcal{H}_{m}$を仮説集合として用いれば良いということになります． しかし，${\rm bias}_{\mathcal{H}_{m}}$はデータの分布が分からないと決定できません． 実際の問題ではデータの分布は未知なので，この方法は使えないことになります． そこで登場するのが「正則化」です．

正則化は「無駄に大きな仮説集合を使うことにペナルティを課す手法」です． 仮説集合$\mathcal{H}_{1} \subset \cdots \subset \mathcal{H}_{M}$を用いて学習を行うとします． 仮説$h$に対するペナルティ$\Phi: \mathcal{H}_M \to \mathbb{R}_{\geq 0}$として$m_1 < m_2$に対して \begin{equation} h\in \mathcal{H}_{m_1},\, h' \in \mathcal{H_{m_2}} \backslash \mathcal{H_{m_1}} \Longrightarrow \Phi(h) \leq \Phi (h') \end{equation} を満たすような関数$\Phi$を考えます． つまり，仮説集合$\mathcal{H}_{m_1}$よりも大きな仮説集合から取ってきた仮説$h'$に対しては $h$よりも大きなペナルティを与えるということを示しています． 実際の教師あり機械学習を使う範囲では，仮説$h$に対してノルムが定まっているので，そのノルムを$\Phi$に使うことがほとんどです．

実際に皆さんが利用している正則化を用いた手法は，Ridge回帰であれLassoであれ，経験損失と仮説に対するペナルティを考慮した最小化を行ってパラメータを決定します： \begin{equation} \min_{h \in \mathcal{H}_{M}} \widehat{R}(h) + \lambda \Phi(h). \end{equation}

正則化手法の具体例

ここでは，正則化を用いた手法の中でも特に有名なリッジ回帰とLassoを取り上げます． これらはともに，線形回帰モデルに正則化を適用した手法です． 線形回帰モデルでは，データ$(\boldsymbol{x}_1, y_1), \cdots, (\boldsymbol{x}_n, y_n)$が与えられたときに， 以下のモデルで$y$を予測します：

\begin{equation} y = \boldsymbol{x}^T \boldsymbol{\beta} + \varepsilon, \quad \boldsymbol{\beta} = \begin{bmatrix} \beta_1 \\ \vdots \\ \beta_d \\ \beta_{d+1} \end{bmatrix},\quad \boldsymbol{x} = \begin{bmatrix} x_1 \\ \vdots \\ x_d \\ 1 \end{bmatrix}. \end{equation}

ここまでの話の流れに沿って記述するなら，最小二乗法による回帰直線の決定とは， \begin{gather} \mathcal{H} = \left\{ \boldsymbol{x}^T \boldsymbol{\beta} | \boldsymbol{\beta} \in \mathbb{R}^{d + 1}\right\}, \\ h(\boldsymbol{x}) = \boldsymbol{x}^T \hat{\boldsymbol{\beta}}, \\ \ell(\boldsymbol{x}, y) = \left( h(\boldsymbol{x}) - y \right) ^2 \end{gather} としたときに \begin{equation} \newcommand{\argmin}{\mathop{\rm arg~min}\limits} \hat{\boldsymbol{\beta}} = \argmin_{\boldsymbol{\beta}}\hat{R}(h) = \argmin_{\boldsymbol{\beta}} \frac{1}{n} \sum_{i=1}^{n} \ell(\boldsymbol{x}_i, y_i) = \argmin_{\boldsymbol{\beta}} \left\| \boldsymbol{y} - \mathbf{X} \beta \right\|_2, \quad \mathbf{X} = \begin{bmatrix} \boldsymbol{x}_{1}^T \\ \vdots \\ \boldsymbol{x}_{n}^T \end{bmatrix} \end{equation} によって$\hat{\boldsymbol{\beta}}$を決定することに相当します． なお，$\| \cdot \|_2$は$L_2$ノルムです．

リッジ回帰

リッジ回帰は上記の最適化問題の目的関数に正則化項として$\lambda \left\| \beta \right\|_2$を加えたものです： \begin{equation} \widehat{\boldsymbol{\beta}}^{\rm Ridge} = \argmin_{\boldsymbol{\beta}}\widehat{R}(h) + \lambda \left\| \beta \right\|_2 =\argmin_{\boldsymbol{\beta}} \frac{1}{n} \sum_{i=1}^{n} \ell(\boldsymbol{x}_i, y_i) + \lambda \left\| \boldsymbol{\beta} \right\|_2 =\argmin_{\boldsymbol{\beta}} \left\| \boldsymbol{y} - \mathbf{X} \beta \right\|_2 + \lambda \left\| \boldsymbol{\beta} \right\|_2. \end{equation} ただし，ここでの$\mathbf{X}, \boldsymbol{\beta}$は \begin{equation} \mathbf{X} =\begin{bmatrix} \boldsymbol{x}_1^T \\ \vdots \\ \boldsymbol{x}_n^T \end{bmatrix} =\begin{bmatrix} x_{11} & \cdots & x_{1d} \\ \cdots & \ddots & \vdots \\ x_{n1} & \cdots & x_{nd} \end{bmatrix}, \quad \boldsymbol{\beta} = \begin{bmatrix} \beta_1 \\ \vdots \\ \beta_{d} \end{bmatrix} \end{equation} であり， \begin{equation} \overline{x}_{\cdot j} = \frac{1}{n}\sum_{i=1}^{n} x_{ij} = 0 \end{equation} を満たすとします． つまり，任意の特徴量に対してサンプルに渡る標本平均と計算すると$0$になっているということですね．

なお，一般的に正則化項にはパラメータベクトル$\boldsymbol{\beta}$の2次形式$\boldsymbol{\beta}^T \mathbf{K} \boldsymbol{\beta}$で表される事が多いです． つまり，正則化最小2乗推定量は一般的に \begin{equation} S(\boldsymbol{\beta}) = (\boldsymbol{y} - \mathbf{X}\boldsymbol{\beta})^T (\boldsymbol{y} - \mathbf{X}\boldsymbol{\beta}) + \lambda \boldsymbol{\beta}^T \mathbf{K} \boldsymbol{\beta} \end{equation} を最小化する解として与えられます． これは以下のように解析的に求めることが出来ます： \begin{align} & \frac{\partial S(\boldsymbol{\beta})}{\partial \boldsymbol{\beta}} = -2\mathbf{X}^T \boldsymbol{y} + 2\mathbf{X}^T \mathbf{X} \boldsymbol{\beta} + 2 \lambda \mathbf{K} \boldsymbol{\beta} = 0 \\ \Longrightarrow & \, \widehat{\boldsymbol{\beta}} = \left( \mathbf{X}^T \mathbf{X} + \lambda \mathbf{K} \right) ^{-1} \mathbf{X}^T \boldsymbol{y} \end{align} 今回の場合は，$\mathbf{K}=\mathbf{I}_{d+1}$の場合に相当するので，リッジ回帰の最小2乗推定量は \begin{equation} \widehat{\boldsymbol{\beta}} = \left( \mathbf{X}^T \mathbf{X} + \lambda \mathbf{I}_{d+1} \right)^{-1} \mathbf{X}^T \boldsymbol{y} \end{equation} となります．

Lasso

Lasso (Least absolute shrinkage and selection operator) は，リッジ回帰における正則化項を$L_1$ノルムに置き換えたものです： \begin{equation} \widehat{\boldsymbol{\beta}}^{\rm Lasso} = \argmin_{\boldsymbol{\beta}}\widehat{R}(h) + \lambda \left\| \beta \right\|_1 =\argmin_{\boldsymbol{\beta}} \left\| \boldsymbol{y} - \mathbf{X} \beta \right\|_2 + \lambda \left\| \boldsymbol{\beta} \right\|_1. \label{optimization of lasso} \end{equation} Eq. (\ref{optimization of lasso}) は解析的に解を求めることは出来ません． ですので，shooting algorighm (Fu (1998)) や Efron et al. (2004) によるLARS( Least Angle Regression) によって$\widehat{\boldsymbol{\beta}}$を決定します．

まとめ

今回は正則化に関する数理的な基礎（本当に基礎の基礎）について簡単にまとめました． 統計的学習理論の本を読めば普通に載っている内容ですので， この記事を読んで「もう少しちゃんと知りたい」となった方は，是非専門書を手にとってください．

おまけ

Eq. (\ref{stochastic inequality 1}) に関するRemark

上では本筋から外れるので省略しましたが，Eq. (\ref{stochastic inequality 1}) からは次のようなことも分かります： \begin{equation} R(h_S) = R(h_0 ) + O_p \left( \sqrt{\frac{\log |\mathcal{H}|}{n}} \right) . \end{equation} これはすなわち， \begin{equation} \lim_{z\to \infty}\limsup\limits_{m\to \infty} {\rm Pr} \left( \frac{\left| R(h_{S_{m}}) - R(h_0)\right|}{ \sqrt{\log |\mathcal{H}| / n} } > z \right) =0, \quad z:= 1 + \frac{\log (2/\delta)}{\log |\mathcal{H}|} \end{equation} ということです． 直感的には，$R(h_{S_m}) - R(h_{0})$の分布の裾が$\sqrt{\log |\mathcal{H}|/n}$のオーダーで漸近的に$0$に落ちているということですね．