経験損失を最小化する仮説を導く学習アルゴリズムとその評価 - 数学、ときどき統計、ところによりＩＴ

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

本記事中で使用する確率論に関する用語および記号は「数理統計学４　測度論的確率論」をご参照下さい。

定義１　 $(\Omega,\mathcal{F},P)$ を確率空間、 $S:=( (X_{1},Y_{1})$ , $(X_{2},Y_{2}),$ $\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})$ , $(x_{2},y_{2}),$ $\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)$ と書くことにします。

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

命題１　 $(\Omega,\mathcal{F},P)$ を確率空間、 $S:=( (X_{1},Y_{1})$ , $(X_{2},Y_{2}),$ $\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)$

が成り立つ。（証明終）

以下、学習アルゴリズム $\hat{h}$ として経験損失を最小にするものを考えます：

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

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

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

定理１　教師データ $(X_{1},Y_{1})$ , $\ldots$ , $(X_{n},Y_{n})$ およびテストデータ $(X,Y)$ は独立同分布な確率変数列とする。また出力値全体 $\mathcal{Y}$ および仮説集合 $\mathcal{H}$ を有限集合とする。このとき任意の $\varepsilon \gt 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}}{\varepsilon}\right)}\right)\le\varepsilon \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\lt \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{equation*}\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}\end{equation*}よって \begin{equation*} \begin{split}\bigl\{\,s\in & (\mathcal{X}\times\mathcal{Y})^{n}\,\big|\,R(\hat{h}_{s})-R(h_{0})\ge\delta\,\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{\delta-(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{\delta-(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{\delta-(R(h_{\mathcal{H}})-R(h_{0}))}{2}\,\biggr\} . \end{split}\end{equation*}となるので\begin{equation*}\begin{split} P^{S} & (R(\hat{h}_{s})-R(h_{0})\ge\delta)\\ & \le\sum_{h\in\mathcal{H}}P^{S}\left(|\hat{R}(h,s)-R(h)|\ge\frac{\delta-(R(h_{\mathcal{H}})-R(h_{0}))}{2}\right) . \end{split}\end{equation*}

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

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

ここで任意の $\varepsilon\gt 0$ に対して $\delta\gt 0$ を

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

と取ると、

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

が成り立つ。（証明終）

学習アルゴリズムの精度について考察を進めるため、以下を定義します。

定義２　任意の $\varepsilon\gt 0$ に対して、ある $\mathrm{var}_{\hat{h}}\gt 0$ が存在して

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

と書けるとき $\mathrm{var}_{\hat{h}}$ を学習アルゴリズム $\hat{h}$ に関する推定誤差という。また $R(h_{\mathcal{H}})-R(h_{0})$ を $\mathrm{bias}_{\mathcal{H}}$ と書き、これを近似誤差と呼ぶ。

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

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

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

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

ただし値域が $\mathcal{H}$ である学習アルゴリズムを $\hat{h}^{\mathcal{H}}$ とした。

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

$\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} により、推定誤差を小さくするためには教師データの数を増やせば良いことが分かります。また命題２により、近似誤差を小さくするためには仮説集合のサイズを大きくすれば良いことも分かります。しかし仮説集合のサイズを大きくすると、推定誤差は大きくなってしまいます。

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

参考文献

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

*1:確率不等式の補題３参照