過学習を防ぐ2つの方法！〜統計的機械学習の基礎〜

機械学習と過学習
期待損失
経験損失
経験損失最小化
有限仮説集合
実現可能性
有限仮説集合と実現可能性を仮定した期待損失
まとめ
参考文献

機械学習と過学習

機械学習モデルを訓練すると、しばしば過学習に陥ります。過学習というのは訓練データに過剰に適合してしまい、未知のデータに対してうまく適合しなくなってしまう、すなわち汎化能力が低い状態を表します。過学習を防ぐためには訓練データを増やせば良い！と言われることがありますがそれは何故でしょうか？ここでは統計的機械学習の理論から過学習を防ぐ方法について考えてみようと思います。まずは、未知のデータや訓練データに対してモデルがどれほど適合しているかを表す期待損失、経験損失を定義しましょう。

期待損失

データの入力を $x$ とし、分布 $\mathcal{D}$ に従うとします。データの出力を $y$ とし、 $y=f(x)$ となるような関数 $f$ があるとします。ここで、分布 $\mathcal{D}$ と関数 $f$ は真の分布と関数であり未知であることに注意します。さて、今ある仮説（予測モデル） $h$ を考えるとき、この仮説が真のデータ分布と関数に対してどれほど不正確であるかは予測結果が真の関数の出力と異なる確率すなわち、

$L_{\mathcal{D}, f}(h)\\ \equiv \mathbb{P}_{x \sim D}[h(x) \neq f(x)]\\ \equiv \mathcal{D}(\{x: h(x) \neq f(x)\})\\$

で表されます。この確率を期待損失と言います（損失関数として0-1損失を選んでいます）。

経験損失

一方で、経験損失は訓練データに対して仮説が真の関数に対してどれほど不正確であるかを表します。すなわち、

$\displaystyle L_{S}(h) \equiv \frac{|\{i \in [m]: h(x_i) \neq y_i\}|}{m}\\ where \, [m]=\{1, \ldots, m\}\\$

で表されます。ただし、 $m$ は訓練データの個数です。

経験損失最小化

さて、機械学習では訓練データからデータの背後にある真の関数を探す、すなわち訓練データではなく未知のデータへ適合するような関数を探すことが目的です。よって、期待損失を最小化したいのですが当然真の分布や関数は未知であり、直接最小化できません。そこで、期待損失の代わりに訓練データから求められる経験損失を最小化することを考えます。これによって期待損失も小さくなることが期待されるでしょう。しかし闇雲に経験損失を最小化すれば良いのかというとそうではありません。経験損失が小さくなっても期待損失が小さくならないことがあるのです！1つ例を挙げて説明しましょう。

f:id:hiden-cubist:20190123155104p:plain

上の図で内側の点線内は1、内側の点線と外側の実線の間は0を返す分布があるとします。青と赤の点はその分布からサンプルした点で、それぞれ青は1、赤は0を表しています。また、内側の正方形と外側の正方形の面積はそれぞれ1、2とします。この時、以下のような仮説を考えてみます。

$h_s(x)= \begin{cases} y_i \quad if \, \exists i \in [m] \, s.t. \, x_i = x\\ 0 \quad otherwise. \end{cases}\\$

この仮説は、サンプルした青の点上では1、赤の点上では0、それ以外の場所では全て0を返すことを意味します。すなわち、サンプルした点の上では必ず予測が正しいことになり経験損失は0となります。一方で期待損失は、有限のサンプルした点以外の場所では必ず0を返すことから、予測が正しくなるのは外側の正方形に対する内側の正方形の面積の比に等しく1/2となってしまいます！この予測は明らかに良い予測とは言えません。これが過学習の問題です。

有限仮説集合

前章の例で起きたような過学習を防ぐための単純なアイデアとして、考える仮説の集合を制限することが挙げられます。つまり、先ほどの例のようなサンプルした点の上でのみ必ず正しい予測を返すような極端な仮説を立てられないようにするわけです。仮説集合を制限すればするほど過学習は防げると考えられますが、一方で最小となる経験損失が大きくなってしまう可能性がありトレードオフとなります。さて、特に仮説集合のうち仮説の個数が有限のものを有限仮説集合と言い、仮説集合の中で経験損失を最小にするような仮説を、

$\newcommand{\argmin}{\mathop{\rm arg~min}\limits} h_S \in \argmin_{h \in \mathcal{H}} L_S(h)\\$

とします。

実現可能性

期待損失を最小化する上で、簡単のために実現可能性という仮定を考えます。実現可能性というのは仮説集合の中に、期待損失を0にするような仮説が含まれていること、すなわち

$h^* \in \mathcal{H} \, s.t. \, L_{\mathcal{D}, f}(h^*)=0\\$

を表します。この仮定は、どのように分布からサンプルしても

$L_S(h^*)=0\\$

となること、また、

$L_S(h_S)=0\\$

となることを意味します。しかし、我々が興味があるのは経験損失を最小にする仮説 $h_S$ や、その仮説に対する期待損失 $L_{\mathcal{D}, f}(h_S)$ なのです。

有限仮説集合と実現可能性を仮定した期待損失

経験損失を最小化するような仮説を選んだ時にその仮説の期待損失がどれほどになるかを知りたいので、その仮説の期待損失が $\epsilon$ より大きくなってしまう確率、

$\mathcal{D}^m(\{S|_x:L_{\mathcal{D}, f}(h_S) \gt \epsilon\})\\$

の上限を考えることにします。ただし、 $S|_x=(x_1, \ldots, x_m)$ であり、 $\mathcal{D}^m$ は $m$ 個のデータを分布 $\mathcal{D}$ から独立にサンプルした時の確率を表します。ここでは、前章で述べた有限仮説集合と実現可能性を仮定することにします。まず、仮説集合の中で期待損失が $\epsilon$ より大きくなってしまう仮説を、

$\mathcal{H}_B = \{h \in \mathcal{H} :L_{\mathcal{D}, f}(h) \gt \epsilon\}\\$

とします。実現可能性の仮定より、 $L_S(h_S)=0$ であることに注意すると、

$\displaystyle \{S|_x:L_{\mathcal{D}, f}(h_S) \gt \epsilon\} \subset \bigcup_{h \in \mathcal{H}_B} \{S|_x:L_S(h)=0\}\\$

が成り立ちます。よって、

$\mathcal{D}^m(\{S|_x:L_{\mathcal{D}, f}(h_S) \gt \epsilon\})\\ \displaystyle \leq \mathcal{D}^m(\bigcup_{h \in \mathcal{H}_B} \{S|_x:L_S(h)=0\})\\ \displaystyle \leq \sum_{h \in \mathcal{H}_B} \mathcal{D}^m(\{S|_x:L_S(h)=0\})\\ \displaystyle = \sum_{h \in \mathcal{H}_B} \mathcal{D}^m(\{S|_x:\forall i,h(x_i)=f(x_i)\})\\ \displaystyle = \sum_{h \in \mathcal{H}_B} \prod_{i=1}^m \mathcal{D}(\{x_i:h(x_i)=f(x_i)\})\\ \displaystyle \leq \sum_{h \in \mathcal{H}_B} \prod_{i=1}^m (1-\epsilon) \quad \cdots(1)\\ \displaystyle = \sum_{h \in \mathcal{H}_B} (1-\epsilon)^m\\ \displaystyle \leq \sum_{h \in \mathcal{H}_B} e^{-\epsilon m}\\ \displaystyle = |\mathcal{H}_B| e^{-\epsilon m}\\ \displaystyle \leq |\mathcal{H}| e^{-\epsilon m}\\$

となります。ただし、(1)式では、 $h \in \mathcal{H}_B$ であることを利用しました。つまり、経験損失を最小化する仮説の期待損失が $\epsilon$ より大きくなってしまう確率は、 $|\mathcal{H}| e^{-\epsilon m}$ で抑えられることがわかりました。

最後の式の右辺を $\delta$ とおいて、これを言い換えれば、以下のような定理が成立します。

有限仮説集合と実現可能性の仮定のもとで、データをサンプルした時に少なくとも確率 $1-\delta$ で、経験損失を最小化する仮説の期待損失は、 $\displaystyle L_{\mathcal{D}, f}(h_S) \leq \frac{\log(|\mathcal{H}|/\delta)}{m}\\$ となる。