数学、ときどき統計、ところによりIT

理論と実践の狭間で漂流する数学趣味人の記録

経験損失を最小化する仮説を導く学習アルゴリズムとその評価

今回は経験損失を最小化する学習アルゴリズムとその評価について議論します。

定義1  (\Omega,\mathcal{F},P) を確率空間、S:=\{(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\}:\Omega \to (\mathcal{X}\times \mathcal{Y} )^{n} を教師データとする。S に関する統計量

\displaystyle \hat{R}(h,\ell,S):=\frac{1}{n}\sum_{i=1}^{n}\ell(h(X_{i}),Y_{i})

を損失関数 \ell の下での仮説 h の経験損失という。

また s=\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\} \in (\mathcal{X}\times \mathcal{Y} )^{n} に対して

\displaystyle \hat{R}(h,\ell,s):=\frac{1}{n}\sum_{i=1}^{n}\ell(h(x_{i}),y_{i})

も損失関数 \ell の下での仮説 h の経験損失と呼ぶ。

 

予測損失の場合と同様、\hat{R}(h,\ell,S) および \hat{R}(h,\ell,s) に関する議論において特に \ell を明示する必要が無い場合は \ell を省略して \hat{R}(h,S) および \hat{R}(h,s) と書くことにします。

テストデータの分布は一般には未知ですが、仮に経験損失に関する分布と一致している場合には次が成り立ちます。

命題1 (\Omega,\mathcal{F},P) を確率空間、S:=\{(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\}:\Omega\to(\mathcal{X}\times\mathcal{Y})^{n} を教師データ、(X,Y):\Omega\to\mathcal{X}\times\mathcal{Y} をテストデータとする。テストデータの確率分布 P^{(X,Y)} が教師データの確率分布 P^{(X_{i},Y_{i})} (i=1,2,\ldots,n) に等しいとき、経験損失 \hat{R}(h,S) は予測損失 R(h) の不偏推定量である。つまり

\displaystyle E_{P}\left[\hat{R}(h,S)\right]=R(h).

証明 P^{(X_{i},Y_{i})}=P^{(X,Y)} より\begin{align*} E_{P}[\ell(h(X_{i}),Y_{i})] & =\int_{\mathcal{X}\times\mathcal{Y}}\ell(h(x),y)P^{(X_{i},Y_{i})}(d(x,y))\\ & =\int_{\mathcal{X}\times\mathcal{Y}}\ell(h(x),y)P^{(X,Y)}(d(x,y))\\ & =E_{P}[\ell(h(X),Y)] \end{align*}であるから

\displaystyle E_{P}\left[\hat{R}(h,S)\right]=\frac{1}{n}\sum_{i=1}^{n}E_{P}[\ell(h(X_{i}),Y_{i})]=R(h)

が成り立つ。(証明終)

 

以下、学習アルゴリズムとして経験損失を最小にするものを考えます:

\displaystyle \hat{h}_{s}:=\underset{h\in\mathcal{H}}{\mathrm{arg\, min}}\, \hat{R}(h,\ell,s).

仮説集合 \mathcal{H} が有限集合の場合、経験損失を最小にする学習アルゴリズムは存在します。実際、各 s\in(\mathcal{X}\times\mathcal{Y})^{n} に対して \{\hat{R}(h,\ell,s)\,|\,h\in\mathcal{H}\} は有限集合なので、高々有限回の比較作業により経験損失を最小化する仮説を特定することが可能です。

経験損失を最小にする学習アルゴリズムから得られる仮説について次の評価が成り立ちます。

定理1 教師データ (X_{1},Y_{1}) , \ldots, (X_{n},Y_{n}) およびテストデータ(X,Y) は独立同分布な確率変数列とする。また出力値全体 \mathcal{Y} および仮説集合 \mathcal{H} を有限集合とする。このとき任意の \(\delta > 0\) に対して次が成り立つ: \begin{equation} P^{S}\left(R(\hat{h}_{s})-R(h_{0})\ge R(h_{\mathcal{H}})-R(h_{0})+(b-a)\sqrt{\frac{2}{n}\log\left(\frac{2\#\mathcal{H}}{\delta}\right)}\right)\le\delta\label{eq:estimation_for_empirical_risk_minimization} \end{equation} ただし  h_{\mathcal{H}}:=\mathrm{arg}\min_{h\in\mathcal{H}} R(h)a:=\inf_{(x,y)}\ell(h(x),y)b:=\sup_{(x,y)}\ell(h(x),y) である。

証明 \mathcal{Y} が有限集合より \(0\le a\le b<\infty\) である。また \mathcal{H} が有限集合より h_{\mathcal{H}} が存在する。

\hat{h}_{s}h_{\mathcal{H}}h_{0} の定義より

 R(h_{0})\le R(h_{\mathcal{H}})\le R(\hat{h}_{s}),\quad\hat{R}(\hat{h}_{s},s)\le\hat{R}(h_{\mathcal{H}},s)

であるから、任意の s\in(\mathcal{X}\times\mathcal{Y})^{n} に対して

\[\begin{split}R(\hat{h}_{s})-R(h_{0}) & =R(\hat{h}_{s})-\hat{R}(\hat{h}_{s},s)+\hat{R}(\hat{h}_{s},s)-R(h_{\mathcal{H}})+R(h_{\mathcal{H}})-R(h_{0})\\ & \le R(\hat{h}_{s})-\hat{R}(\hat{h}_{s},s)+\hat{R}(h_{\mathcal{H}},s)-R(h_{\mathcal{H}})+R(h_{\mathcal{H}})-R(h_{0})\\ & \le2\,\max_{h\in\mathcal{H}}|\hat{R}(h,s)-R(h)|+R(h_{\mathcal{H}})-R(h_{0}). \end{split}\]よって \[ \begin{split}\bigl\{\,s\in & (\mathcal{X}\times\mathcal{Y})^{n}\,\big|\,R(\hat{h}_{s})-R(h_{0})\ge\varepsilon\,\bigr\}\\ \subset & \left\{ \,s\in(\mathcal{X}\times\mathcal{Y})^{n}\,\bigg|\,\max_{h\in\mathcal{H}}|\hat{R}(h,s)-R(h)|\ge\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{2}\right\} \\ = & \bigcup_{h\in\mathcal{H}}\biggl\{\,s\in(\mathcal{X}\times\mathcal{Y})^{n}\,\bigg|\,\underset{h'\in\mathcal{H}}{\mathrm{arg\, max}}\, |\hat{R}(h',s)-R(h')|=h,\\ & \qquad\qquad\qquad|\hat{R}(h,s)-R(h)|\ge\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{2}\biggr\}\\ \subset & \bigcup_{h\in\mathcal{H}}\biggl\{\,s\in(\mathcal{X}\times\mathcal{Y})^{n}\,\biggl|\,|\hat{R}(h,s)-R(h)|\ge\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{2}\,\biggr\} . \end{split} \]となるので\[\begin{split} P^{S} & (R(\hat{h}_{s})-R(h_{0})\ge\varepsilon)\\ & \le\sum_{h\in\mathcal{H}}P^{S}\left(|\hat{R}(h,s)-R(h)|\ge\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{2}\right) . \end{split}\]

ところで \{(X_{i},Y_{i})\}_{i=1}^{n} は独立同分布な確率変数列であるから \{\ell(h(X_{i}),Y_{i})\}_{i=1}^{n} も独立同分布な確率変数列となる。このことと命題1を合わせて考えれば、確率変数列 \{\ell(h(X_{i}),Y_{i})\}_{i=1}^{n} に対してヘフディングの不等式*1を適用することが出来るから、\varepsilon を正数として\[\begin{split}P^{S} \bigg(|\hat{R}(h,s) &-R(h)|\ge\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{2}\bigg)\\ & \le2\exp\left(-\frac{n}{2}\left(\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{b-a}\right)^{2}\right)\end{split}\]が成り立つ。従って

 \displaystyle P^{S}(R(\hat{h}_{s})-R(h_{0})\ge\varepsilon)\le2\#\mathcal{H}\exp\left(-\frac{n}{2}\left(\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{b-a}\right)^{2}\right).

ここで任意の \(\delta>0\) に対して \(\varepsilon>0\) を

\displaystyle \delta=2\#\mathcal{H}\exp\left(-\frac{n}{2}\left(\frac{\varepsilon-(R(h_{\mathcal{H}})-R(h_{0}))}{b-a} \right)^{2}\right)

を満たすように取る、つまり

 \displaystyle \varepsilon=R(h_{\mathcal{H}})-R(h_{0})+(b-a)\sqrt{\frac{2}{n}\log\left(\frac{2\#\mathcal{H}}{\delta}\right)}

と取ると、

 \displaystyle P^{S}(R(\hat{h}_{s})-R(h_{0})\ge\varepsilon)\le\delta.

が成り立つ。(証明終)

 

学習アルゴリズムによって得られる仮説に関する精度について考察を進めるため、以下を定義します。

定義2 学習アルゴリズム \hat{h} が任意の \(\delta>0\) に対して、ある \(\mathrm{var}_{\mathcal{H}}>0\) が存在して

P^{S}(R(\hat{h}_{s})-R(h_{0})\ge R(h_{\mathcal{H}})-R(h_{0})+\mathrm{var}_{\mathcal{H}})\le\delta

と書けるとき \mathrm{var}_{\mathcal{H}} を推定誤差という。また \mathrm{bias}_{\mathcal{H}}:=R(h_{\mathcal{H}})-R(h_{0}) を近似誤差と呼ぶ。

\mathrm{bias}_{\mathcal{H}}ベイズ誤差 h_{0}\mathcal{H} の要素で近似することに伴う誤差であり、\mathrm{var}_{\mathcal{H}} は予測誤差 R に関して \mathcal{H} の中で最も適した仮説 h_{\mathcal{H}} ではなく、推定量 \hat{h}_{s} を予測に用いることで生じる誤差を表しています。

経験損失を最小にする仮説を導く学習アルゴリズムに対する評価式 \eqref{eq:estimation_for_empirical_risk_minimization} の場合、 \begin{equation}\displaystyle \mathrm{var}_{\mathcal{H}}=(b-a)\sqrt{\frac{2}{n}\log\left(\frac{2\#\mathcal{H}}{\delta}\right)} \label{eq:variance_for_empirical_risk_minimization} \end{equation} となります。この場合、次のことが成り立ちます。

命題2 定理1と同じ状況の下で、2つの仮説集合 \mathcal{H}_{1}\subset\mathcal{H}_{2} に対して次が成り立つ:

\mathrm{bias}_{\mathcal{H}_{1}}\ge\mathrm{bias}_{\mathcal{H}_{2}},\quad\mathrm{var}_{\mathcal{H}_{1}}\le\mathrm{var}_{\mathcal{H}_{2}}.

証明 推定誤差についての不等式は明らか。また近似誤差についても

 \displaystyle R(h_{\mathcal{H}_{1}})=\min_{h\in\mathcal{H}_{1}}R(h)\ge\min_{h\in\mathcal{H}_{2}}R(h)=R(h_{\mathcal{H}_{2}})

より直ちに分かる。(証明終)

 

ここで経験損失を最小化する仮説を導く学習アルゴリズムについて、推定誤差および近似誤差を小さくするための条件についてまとめておきましょう。まず \eqref{eq:variance_for_empirical_risk_minimization} により、推定誤差を小さくするためには教師データの数を増やせば良いことが分かります。また命題2により、近似誤差を小さくするためには仮説集合のサイズを大きくすれば良いことも分かります。しかし仮説集合のサイズを大きくすると、推定誤差は大きくなってしまいます。

以上のことから、十分な数の教師データがある場合、より沢山の仮説の中からデータに対する説明力・予測力が高い仮説を見つけ出すことが出来ます。一方で教師データの数が十分でない場合には、近似誤差と推定誤差のどちらか一方が極端に大きくなることが無いような適切な仮説集合を設定する必要があります。しかし(R(h) の定義により)\mathrm{bias}_{\mathcal{H}} は教師データの分布 P^{S} に依存することから、そうした仮説集合を組織的に見つけることは難しい為、この問題に対する処方箋として正則化と呼ばれる手法が用いられます。

 

参考文献

  • 金森敬文,統計的学習理論, 講談社, 2015