エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

二値分類の数理(ベイズ分類器，経験損失最小化，超過損失とくに推定誤差の確率的な評価など)についてまとめる

情報学 機械学習

勉強を進めていて，機械学習であつかう基本的な問題の一つである二値分類(binary classification)の数理について知りました．性能のよい分類器とはどのようなものかを考えるという内容で，具体的には，ベイズ分類器，経験損失最小化，超過損失とくに推定誤差の確率的な評価，などです．本記事ではそれらについて文献[1]のpp.1-16をベースにしてまとめることにしました．


=================================================================================
[ 1.1 二値分類問題の設定とベイズ分類器 ]
(真の)同時確率分布 {\displaystyle P_{X,Y} } に従う確率変数の組 {\displaystyle (X,Y)\in \mathcal{X} \times \{ 0,1 \} } のそれぞれ独立な {\displaystyle n } 個の実現値の列(訓練データ) {\displaystyle \mathcal{D}_n = \{ (X_1,Y_1),\ldots,(X_n,Y_n) \} } を観測するとします．{\displaystyle Y \in \{0,1\} } はラベル(label)という変数であり， 変数 {\displaystyle X \in \mathcal{X} } は問題の特徴(feature)を表します．本記事では {\displaystyle \mathcal{X}=\mathbb{R}^d } と考えて差し支えありません．二値分類の目的は，訓練データ {\displaystyle \mathcal{D}_n } のみを用いて，特徴 {\displaystyle X } からラベル {\displaystyle Y } を予測する分類器(classifer)という関数 {\displaystyle h:\mathcal{X}\to \{ 0,1 \} } を構成することです．すべての {\displaystyle h(\cdot) } からなる集合を {\displaystyle \mathcal{H}_{\mathrm{all}} } とします．

同時確率分布 {\displaystyle P_{X,Y} } の {\displaystyle X } についての周辺分布を {\displaystyle P_X } とし，{\displaystyle Y } が与えられた下での {\displaystyle X } の条件付き確率変数 {\displaystyle Y|X } はベルヌーイ分布(文献[5]にあります)に従うとします．{\displaystyle \eta(\cdot) } を回帰関数(regression function)といいます．

(1.1.1){\displaystyle \;\;\; Y|X \sim \mathrm{Bernoulli}(\eta(X)) }
(1.1.2){\displaystyle \;\;\; \eta(X)=P(Y=1|X) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; =1 \cdot P(Y=1|X) + 0 \cdot P(Y=0|X) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; =E [ Y|X ] }


ベイズ分類器(Bays classifier)を定義します．{\displaystyle \mathbf{1}(p) } は {\displaystyle p } が真のとき {\displaystyle 1}，そうでないとき {\displaystyle 0} となる関数とします．

定義 1.1.1.  {\displaystyle Y } が与えられた下での {\displaystyle X } のベイズ分類器 {\displaystyle h^*:\mathcal{X} \to \{ 0,1 \} } は以下の関数である．

(1.1.3){\displaystyle \;\;\; h^*(x)= \mathbf{1}(\eta(x) \gt 1/2) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathbf{1}(P(Y=1|X=x) \gt 1/2) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathbf{1}(P(Y=1|X=x) \gt P(Y=0|X=x)) }

 ベイズ分類器は {\displaystyle \eta(\cdot) } が既知，すなわち {\displaystyle Y|X } の確率分布(1.1.1)(1.1.2)が既知ならば構成できます．{\displaystyle \eta(X) \gt 1/2 } ならば {\displaystyle Y=1 } が正しい予測となりそうであると考えます．{\displaystyle \eta(X)=1/2 } のとき {\displaystyle X } は {\displaystyle Y } について何の情報も含んでいないといえます．


分類器 {\displaystyle h(\cdot) } の性能評価を行う指標として，分類誤差(classification error) {\displaystyle R(h) } と超過損失(excess risk) {\displaystyle \mathcal{E}(h) } を以下で定義します．{\displaystyle R(h^*) } をベイズ損失(Bayes risk)といいます．

(1.1.4){\displaystyle \;\;\; R(h)=P(Y \neq h(X)) }

(1.1.5){\displaystyle \;\;\; \mathcal{E}(h) = R(h)-R(h^*) }


次の定理はベイズ分類器が分類誤差について最適，いいかえると分類誤差を最小にする分類器であることを主張しています．

定理 1.1.2.  任意の分類器 {\displaystyle h(\cdot) \in \mathcal{H}_{\mathrm{all}} } について以下が成り立つ．

(1.1.6){\displaystyle \;\;\; \mathcal{E}(h) = R(h)-R(h^*) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \int_{ \{ x \in \mathcal{X} \ | \ h(x) \neq h^*(x) \} } \left| \eta(x)- \frac{1}{2} \right| P_x(dx) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \int_{ \mathcal{X} } \left| \eta(x)-\frac{1}{2} \right| \mathbf{1}( h(x) \neq h^*(x)) P_x(dx) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 E \left[ \left| \eta(X)-\frac{1}{2} \right| \mathbf{1}( h(X) \neq h^*(X)) \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge 0 }

また以下が成り立つ．

(1.1.7){\displaystyle \;\;\; R(h^*) =P(Y \neq h^* (X)) \;\;\;\;\;\; \because } (1.1.4)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_{h(\cdot) \in \mathcal{H}_{\mathrm{all}} }R(h) \;\;\;\;\;\;\;\;\;\; \because } (1.1.6)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = E \left[ \min (\eta(X),1-\eta(X)) \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{1}{2} }

証明.
省略．文献[1]参照．

 この定理からわかることをまとめます．

  • (1.1.6)より {\displaystyle h(\cdot) } を {\displaystyle h^*(\cdot) } と類似する性質をもつように構成することで，超過損失を小さくすることができます．
  • (1.1.7)よりすべての {\displaystyle x \in \mathcal{X} } について {\displaystyle \eta(x) \in \{ 0,1 \} } のとき {\displaystyle R(h^*)=0 } となり，ある {\displaystyle x \in \mathcal{X} } について {\displaystyle \eta(x) \notin \{ 0,1 \} } のとき {\displaystyle R(h^*) \neq 0 } となることがわかります．
  • (1.1.7)より {\displaystyle R(h^*) = 1/2} が成り立つための必要十分条件はほとんど確実に(almost surely) {\displaystyle \eta(X) = 1/2} が成り立つことです．すなわちベイズ損失がその最大値 {\displaystyle 1/2 } をとるのは {\displaystyle X } が {\displaystyle Y } について何の情報も含まないとき，またそのときに限ります．
  • (1.1.6)より超過損失 {\displaystyle \mathcal{E}(h) } は {\displaystyle \eta(x) } が {\displaystyle 1/2 } からどの程度はなれているか(を意味する非積分関数)を {\displaystyle h(x) \neq h^*(x) } となる {\displaystyle x } の領域で重みをつけることがわかります．(1.1.7)より {\displaystyle \eta(x) } が {\displaystyle 1/2 } に近い値をとるとき，ベイズ分類器はうまく機能せずベイズ損失は大きくなり，超過損失は小さくなります．これは困難な二値分類問題です．{\displaystyle \eta(x) } が {\displaystyle 1/2 } に遠い値をとるとき，ベイズ分類器はうまく機能しベイズ損失は小さくなり，その他の分類器により重いペナルティを課し超過損失は大きくなります．これは簡単な二値分類問題です．


本節では，二値分類問題を設定し，その評価指標として分類誤差を導入しました．また，真の同時確率分布が既知のときに定義できるベイズ分類器が，分類誤差を最小にする分類器であることを述べました．

 

[ 1.2 経験損失による分類誤差の近似と経験損失最小化 ]
前節の議論は同時確率分布を既知としその性質を扱っているという意味で確率論的ですが，現実には真の同時確率分布 {\displaystyle P_{X,Y} } は未知です．すなわち回帰関数 {\displaystyle \eta(\cdot) } が未知なのでベイズ分類器 {\displaystyle h^*(\cdot) } を計算できず，{\displaystyle \eta(\cdot) } についてのいくらか(すべてではない)の情報を含む独立同分布({\displaystyle \mathrm{i.i.d.} })の実現値の列(訓練データ) {\displaystyle \mathcal{D}_n = \{ (X_1,Y_1),\ldots,(X_n,Y_n) \} } のみ利用できます．したがって統計学的な観点から考えていきます．


(1.1.4)より {\displaystyle R(\cdot) } は未知の同時確率分布 {\displaystyle P_{X,Y} } に依存するので同じく未知です．したがって {\displaystyle R(\cdot) } を以下の経験損失(empirical risk)で近似することを考えます．

定義 1.2.1.  以下の {\displaystyle \hat{R}_n(\cdot) } を分類器 {\displaystyle h } の経験損失という．

(1.2.1){\displaystyle \;\;\; \hat{R}_n(h)=\frac{1}{n}\sum_{i=1}^n \mathbf{1}(Y_i \neq h(X_i)) }

 この定義より

(1.2.2){\displaystyle \;\;\; E [ \hat{R}_n(h) ] = E \left[ \frac{1}{n}\sum_{i=1}^n \mathbf{1}(Y_i \neq h(X_i)) \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{n}\sum_{i=1}^n E [ \mathbf{1}(Y_i \neq h(X_i)) ] \;\;\;\;\;\; \because \mathrm{i.i.d.} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{n}\sum_{i=1}^n P( h(X_i) \neq Y_i ) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{n}\sum_{i=1}^n P( h(X) \neq Y ) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = R(h) \;\;\;\;\;\; \because } (1.1.4)

を得るので，{\displaystyle \hat{R}_n(h) } は {\displaystyle R(h) } の不偏推定量(unbiased estimator)です．さらに，任意の {\displaystyle h(\cdot) } について，対数の強法則より以下が成り立ちます，すなわち {\displaystyle n } が十分大きいとき {\displaystyle \hat{R}_n(h) } は {\displaystyle R(h) } に概収束します．

(1.2.3){\displaystyle \;\;\; \lim_{n \to \infty} \hat{R}_n(h) = \lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^n \mathbf{1}(Y_i \neq h(X_i)) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = E [ \mathbf{1}(Y \neq h(X)) ] \;\;\;\;\;\; \mathrm{a.s.} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = P( h(X) \neq Y ) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = R(h) }


{\displaystyle \mathcal{D}_n } から構成する分類器を {\displaystyle \hat{h}_n(\cdot) = \hat{h}_n (X) } とします．この分類器は {\displaystyle X } の関数であるという意味と確率変数である訓練データ {\displaystyle \mathcal{D}_n } に依存するという意味で確率変数です．次節以降でこの分類器を {\displaystyle \mathcal{D}_n } に依存する(積分するので {\displaystyle X } には依存しません)確率変数 {\displaystyle \mathcal{E}(\hat{h}_n) } で評価することになるのですが，確率変数なのでその期待値や分位数(高い確率で起こりうる点)を考えることになります．


ベイズ分類器 {\displaystyle h^*(\cdot) } に類似するものを構成するために経験損失(1.2.1)を用いることを考えます．経験損失最小化(empirical risk minimization; ERM)を達成する分類器である経験損失最小解(empirical risk minimizer)を以下で定義します．

(1.2.4){\displaystyle \;\;\; \hat{h}_n^{\mathrm{all}} = \mathrm{arg} \ \mathrm{min}_{h \in \mathcal{H}_{\mathrm{all}}} \hat{R}_n(h) }

これは以下のように容易に構成できます．

(1.2.5){\displaystyle \;\;\; \hat{h}_n^{\mathrm{all}}(x)= \begin{cases} Y_i, \;\;\;\;\; x \in \{ X_1,\cdots,X_n \} \\ 0, \;\;\;\;\;\; x \notin \{ X_1,\cdots,X_n \} \end{cases} }

明らかにこの分類器は {\displaystyle \hat{R}_n(\hat{h}_n^{\mathrm{all}}) = 0 } を実現しています．一方で，訓練データに含まれない(訓練データと同一でない)任意の {\displaystyle x } をすべてラベル {\displaystyle 0 } であると予測するという明かな問題があり， {\displaystyle E [ R(\hat{h}_n^{\mathrm{all}}) ] } は小さくなりそうもありません，すなわち汎化性能が低いといえます．

このように分類器を訓練データに完全に適合させることで経験損失をどのような訓練データに対しても最小化可能( {\displaystyle 0 } にできる)であるので，すべての分類器を対象として経験損失を最小化することは実用的ではありません．それゆえ対象をある分類器の集合 {\displaystyle \mathcal{H} } に制限する必要があります．

定義 1.2.2.  {\displaystyle \mathcal{H} \subset \mathcal{H}_{\mathrm{all}} } 上の経験損失最小解は以下である．

(1.2.6){\displaystyle \;\;\; \hat{h}_n = \mathrm{arg} \ \mathrm{min}_{h \in \mathcal{H}} \hat{R}_n(h) }

 {\displaystyle \mathcal{H} } はすべての分類器からなる集合 {\displaystyle \mathcal{H}_{\mathrm{all}} } に含まれますが，{\displaystyle R(\hat{h}_n) } はベイズ損失 {\displaystyle R(h^*) } に近い値となってほしいので，{\displaystyle \mathcal{H} } が小さすぎてもいけません．次節ではこのトレードオフを定量化するための道具を導入します．


本節では，分類誤差の(概収束の意味での)近似である経験損失を定義し，それが不偏推定量でもあることを示しました．また，汎化性能を向上するためには，経験損失を最小化する分類器を見つける際に対象となる分類器の集合を制限する必要があることを述べました．

 

[ 1.3 超過損失のトレードオフ : 推定と近似 ]
{\displaystyle \mathcal{H} } が与えられた下で分類誤差 {\displaystyle R(h) } を最小化する分類器をオラクル(oracle)といい以下で定義します．真の同時確率分布は未知なので訓練データからオラクルを決定することはできません．

(1.3.1){\displaystyle \;\;\; \bar{h}= \mathrm{arg} \ \mathrm{min}_{h \in \mathcal{H}} R(h) }


超過損失(1.1.5)について以下を得ます．

(1.3.2){\displaystyle \;\;\; \mathcal{E}(\hat{h}_n)= R(\hat{h}_n) - R(h^*) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = ( R(\hat{h}_n) - R(\bar{h}) ) + ( R(\bar{h}) - R(h^*) ) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left( R(\hat{h}_n) - \inf_{h(\cdot) \in \mathcal{H} } R(h) \right) + \left( \inf_{h(\cdot) \in \mathcal{H} } R(h) - R(h^*) \right) \;\;\; \because } (1.3.1)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left( R \left( \mathrm{arg} \ \mathrm{min}_{h \in \mathcal{H}} \hat{R}_n(h) \right) - \inf_{h(\cdot) \in \mathcal{H} } R(h) \right) + \left( \inf_{h(\cdot) \in \mathcal{H} } R(h) - R(h^*) \right) \;\;\; \because } (1.2.6)


2,3,4行目の第二項は近似誤差(approximation error)といいます．{\displaystyle \mathcal{H} } に含まれる分類器がどの程度ベイズ分類器 {\displaystyle h^* } を近似しているかを意味し，{\displaystyle \mathcal{H} } を固定したときその {\displaystyle \mathcal{H} } に固有のものであり改善のしようがありません．

2,3,4行目の第一項は推定誤差(estimation error)といいます．分類誤差 {\displaystyle R(\cdot) } ではなく経験損失 {\displaystyle R_n(\cdot) } を最小化することの効果がどの程度かを意味します．これは(経験損失は分類誤差に概収束することから)サンプル数 {\displaystyle n } は有限なので同時確率分布 {\displaystyle P_{X,Y} } の情報は部分的にしかわからないことによります．推定誤差は {\displaystyle n } に依存し，(1.2.3)を考慮すると {\displaystyle n \to \infty } とすればこの推定誤差が {\displaystyle 0} となる，すなわち {\displaystyle \hat{h}_n } が( {\displaystyle \mathcal{H} } に制限した下での)最良の性能をもつ分類器となることが望ましいです．しかしノーフリーランチ定理より，{\displaystyle \mathcal{H} = \mathcal{H}_{\mathrm{all}} } ならばそれは成り立ちません(文献[3]が参考になります)．それゆえ推定誤差を小さくするためには {\displaystyle \mathcal{H} \subset \mathcal{H}_{\mathrm{all}} } を小さくとる必要がありますが，このとき近似誤差は大きくなる，すなわち {\displaystyle h^* } に近い機能をもつ分類器をみつけにくくなります．次節の目標は {\displaystyle n } と {\displaystyle \mathcal{H} } の(大きさの)関数としての推定誤差をどのように {\displaystyle 0 } にするかを理解することです．

ノーフリーランチ定理は以下の過去記事にもあります．

二値分類におけるノーフリーランチ定理を証明する - エンジニアを目指す浪人のブログ


本節では，分類誤差を最小にする分類器であるオラクルを導入しました．また，超過損失が推定誤差と近似誤差に分解され，それらは候補となる分類器の集合の大小についてトレードオフの関係にあることを述べました．

 

[ 1.4 オラクル不等式 ]
オラクル不等式とは推定誤差をある値で抑えることを意味する以下のような不等式のことです．

(1.4.1){\displaystyle \;\;\; R(\hat{h}_n) - R(\bar{h}) \le \epsilon }

{\displaystyle \mathcal{H} } が数少ない {\displaystyle h } からなるとき，{\displaystyle \bar{h}(\cdot) } の性能は低下し {\displaystyle R(\bar{h}) } は大きくなりますが，({\displaystyle \epsilon } は小さくなり) {\displaystyle \hat{h}_n } は {\displaystyle \bar{h} } のよい近似になるかもしれません(すぐわかるように {\displaystyle \mathcal{H} } がただ一つの関数のとき {\displaystyle \bar{h}=\hat{h}_n } となり {\displaystyle \epsilon =0 } です)．一方で，{\displaystyle \mathcal{H} } が数多くの {\displaystyle h } からなるとき，{\displaystyle \bar{h}(\cdot) } の性能は向上し {\displaystyle R(\bar{h}) } は小さくなりますが，({\displaystyle \epsilon } は大きくなり) {\displaystyle \hat{h}_n } による {\displaystyle \bar{h} } の統計学的な近似はより困難となります，いいかえると，同じ性能を達成するためにより多くのサンプルが必要です．以下ではこれらのことを具体的に数式で考えていきます．

{\displaystyle R(\hat{h}_n) } は確率変数なので，実際には以下のような期待値あるいは確率分布の裾を評価する不等式を証明する必要があります． {\displaystyle \Delta_{n,\delta}(\mathcal{H}) } はサンプル数 {\displaystyle n } と信頼水準 {\displaystyle \delta \in ( 0,1 ) } に依存する {\displaystyle \mathcal{H} } の関数です．

(1.4.2){\displaystyle \;\;\; E [ R(\hat{h}_n) ] \le R(\bar{h}) + \epsilon }

(1.4.3){\displaystyle \;\;\; P \left( R(\hat{h}_n) - R(\bar{h}) \le \Delta_{n,\delta}(\mathcal{H}) \right) \ge 1- \delta }


{\displaystyle \mathcal{H} } が有限個の分類器からなる，すなわち {\displaystyle \mathcal{H} = \{ h_1,\ldots,h_M \} } とし，{\displaystyle M } と {\displaystyle n } が変化する場合のこれら不等式のふるまいを考えます．以下の定理は，一般に {\displaystyle \hat{h}_n } は {\displaystyle \bar{h} } よりもよい性能となることは望めないけれども，サンプル数 {\displaystyle n } が分類器の候補の数 {\displaystyle M } と比較して十分小さくなる場合を除けば分類誤差の差はそれほど大きくならないことを主張しています．またその場合，分類誤差と経験損失の差(の絶対値)もそれほど大きくならないことが証明からわかります．定理の証明で用いる Jensen's inequality は文献[6]にあります．Hoeffding's lemma と Hoeffding's inequality は以下の過去記事にあります． 

いくつかの集中不等式(Hoeffding's Inequalityなど)を証明する - エンジニアを目指す浪人のブログ

 

定理 1.4.1.  {\displaystyle \mathcal{H} = \{ h_1,\ldots,h_M \} } のとき，経験損失最小解 {\displaystyle \hat{h}_n } について以下が成り立つ．{\displaystyle \delta \in ( 0,1 ) } とする．

{\displaystyle \;\;\; P \left( R(\hat{h}_n) \le R(\bar{h}) + \sqrt{ \frac{2 \log(2 M / \delta) }{n} } \right) \ge 1 - \delta }

{\displaystyle \;\;\; E [ R(\hat{h}_n) ] \le R(\bar{h}) + \sqrt{ \frac{2 \log(2 M ) }{n} } }


証明.
オラクル不等式について以下を得る．これは定理の前半と後半両方の証明に用いる．

{\displaystyle \;\;\; R(\hat{h}_n) - R(\bar{h}) = R(\hat{h}_n) - \hat{R}_n(\hat{h}_n) + \hat{R}_n(\bar{h}) - R(\bar{h}) + \hat{R}_n(\hat{h}_n)-\hat{R}_n(\bar{h}) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le R(\hat{h}_n) - \hat{R}_n(\hat{h}_n) + \hat{R}_n(\bar{h}) - R(\bar{h}) \;\;\;\;\;\; \because \hat{R}_n(\hat{h}_n) \le \hat{R}_n(\bar{h}) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le | R(\hat{h}_n) - \hat{R}_n(\hat{h}_n) | + | \hat{R}_n(\bar{h}) - R(\bar{h}) | }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = | \hat{R}_n(\hat{h}_n) - R(\hat{h}_n) | + | \hat{R}_n(\bar{h}) - R(\bar{h}) | }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le 2 \max_{j \in \{ 1, \ldots,M \} } | \hat{R}_n(h_j) - R(h_j) | }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \max_{j \in \{ 1, \ldots,M \} } \left| \hat{R}_n(h_j) - E [ \hat{R}_n(h_j) ] \right| \;\;\; \because } (1.2.2)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \max_{j \in \{ 1, \ldots,M \} } \frac{1}{n} \left| n \hat{R}_n(h_j) - E [ n \hat{R}_n(h_j) ] \right| \;\;\; } (※)

これを用いて以下を得る．

{\displaystyle \;\;\; P \left( R(\hat{h}_n) - R(\bar{h}) \gt \sqrt{ \frac{2 \log(2 M / \delta) }{n} } \right) }
{\displaystyle \;\;\;\;\;\; \le P \left( 2 \max_{j \in \{ 1, \ldots,M \} } \frac{1}{n} \left| n \hat{R}_n(h_j) - E [ n \hat{R}_n(h_j) ] \right| \gt \sqrt{ \frac{2 \log(2 M / \delta) }{n} } \right) \;\;\; \because } (※)
{\displaystyle \;\;\;\;\;\; = P \left( \max_{j \in \{ 1, \ldots,M \} } \left| n \hat{R}_n(h_j) - E [ n \hat{R}_n(h_j) ] \right| \gt \frac{n}{2} \sqrt{ \frac{2 \log(2 M / \delta) }{n} } \right) }
{\displaystyle \;\;\;\;\;\; \le \sum_{j=1}^M \ P \left( \left| n \hat{R}_n(h_j) - E [ n \hat{R}_n(h_j) ] \right| \gt \frac{n}{2} \sqrt{ \frac{2 \log(2 M / \delta) }{n} } \right) }
{\displaystyle \;\;\;\;\;\; \le 2 M \ \mathrm{exp} \left\{ -2 \frac{n^2}{2^2} \frac{2 \log(2 M / \delta) }{n} \frac{1}{ \sum_{i=1}^n 1 } \right\} \;\;\; \because } Hoeffding's inequality
{\displaystyle \;\;\;\;\;\; = 2M \ \mathrm{exp} \left\{ \log( \delta / 2M ) \right\} }
{\displaystyle \;\;\;\;\;\; = \delta }

したがって以下を得ることができ，定理の前半を示せた．

{\displaystyle \;\;\; P \left( R(\hat{h}_n) \le R(\bar{h}) + \sqrt{ \frac{2 \log(2 M / \delta) }{n} } \right) }
{\displaystyle \;\;\;\;\;\; = 1 - P \left( R(\hat{h}_n) - R(\bar{h}) \gt \sqrt{ \frac{2 \log(2 M / \delta) }{n} } \right) }
{\displaystyle \;\;\;\;\;\; \ge 1 - \delta }


定理の後半の証明に進む．

{\displaystyle \;\;\; E \left[ \max_{j \in \{ 1,\ldots,M \} } \left| \hat{R}_n(h_j) - R(h_j) \right| \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \log \ \mathrm{exp} \left[ E \left[ \max_{j \in \{ 1,\ldots,M \} } \left| \hat{R}_n(h_j) - R(h_j) \right| \right] \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{s} \log \ \mathrm{exp} \left[ s E \left[ \max_{j \in \{ 1,\ldots,M \} } \left| \hat{R}_n(h_j) - R(h_j) \right| \right] \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{s} \log \ \mathrm{exp} \left[ E \left[ s \max_{j \in \{ 1,\ldots,M \} } \left| \hat{R}_n(h_j) - R(h_j) \right| \right] \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{1}{s} \log \ E \left[ \mathrm{exp} \left[ s \max_{j \in \{ 1,\ldots,M \} } \left| \hat{R}_n(h_j) - R(h_j) \right| \right] \right] \;\;\; \because } Jensen's inequality
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{1}{s} \log 2 \sum_{j=1}^M \ E \left[ \mathrm{exp} \left[ s \left| \hat{R}_n(h_j) - R(h_j) \right| \right] \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{s} \log 2 \sum_{j=1}^M \ E \left[ \mathrm{exp} \left[ s \left| \hat{R}_n(h_j) - E [ \hat{R}_n(h_j) ] \right| \right] \right] \;\;\; \because } (1.2.2)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{s} \log (2M) \ E \left[ \mathrm{exp} \left[ s \frac{1}{n} \left| n \hat{R}_n(h_j) - E [ n \hat{R}_n(h_j) ] \right| \right] \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{1}{s} \log (2M) \ \mathrm{exp} \left[ \frac{s^2}{8n} \right] \;\;\; \because } Hoeffding's lemma
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{\log (2M)}{s} + \frac{s}{8n} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{\log (2M)}{2 \sqrt{2n \log(2M)}} + \frac{2 \sqrt{2n \log(2M)}}{8n} \;\;\; \because s = 2 \sqrt{2n \log(2M)} \; } とする
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ \sqrt{ \log(2M)} }{2 \sqrt{2n}} + \frac{ \sqrt{ \log(2M)}}{ 2 \sqrt{ 2n } } }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sqrt{ \frac{ \log(2 M ) }{ 2 n} } \;\;\; } (※※)

(※)の期待値をとったものを考えると

{\displaystyle \;\;\; E [ R(\hat{h}_n) ] - R(\bar{h}) = E \left[ R(\hat{h}_n) - R(\bar{h}) \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le E \left[ 2 \max_{j \in \{ 1, \ldots,M \} } | \hat{R}_n(h_j) - R(h_j) | \right] \;\;\; \because } (※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 E \left[ \max_{j \in \{ 1, \ldots,M \} } | \hat{R}_n(h_j) - R(h_j) | \right] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le 2 \sqrt{ \frac{ \log(2 M ) }{ 2 n} } \;\;\; \because } (※※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \sqrt{ \frac{ 2 \log(2 M ) }{ n} } }
となり，定理の後半が示せた．(証明終わり)

 

本節では，推定誤差をある値で抑えることを意味するオラクル不等式が，サンプル数と(有限個の)分類器の候補の数にどのように依存するのかということを確率的な評価の観点で述べました．

=================================================================================

以上，二値分類の数理(ベイズ分類器，経験損失最小化，超過損失とくに推定誤差の確率的な評価など)についてまとめました．

 

参考文献
[1] Massachusetts Institute of Technology  Philippe Rigollet先生のノート https://ocw.mit.edu/courses/mathematics/18-657-mathematics-of-machine-learning-fall-2015/lecture-notes/MIT18_657F15_LecNote.pdf
[2] University of Michigan  Clayton Scott先生のノート
http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/01_prob_setting.pdf
http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/02_bayes_classifier.pdf
http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/03_hoeffding.pdf
http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/04_erm.pdf
[3] Ben-Gurion University of the Negev  Aryeh Kontorovich先生らのノート https://www.cs.bgu.ac.il/~inabd161/wiki.files/lecture3a_handouts.pdf
[4] Bottou, L. and Bousquet, O. (2008), The Tradeoffs of Large Scale Learning, Advances in Neural Information Processing Systems, NIPS Foundation (http://books.nips.cc), pp.161-168.
[5] Wikipedia  Bernoulli distributionのページ https://en.wikipedia.org/wiki/Bernoulli_distribution
[6] Wikipedia  Jensen's inequalityのページ https://en.wikipedia.org/wiki/Jensen%27s_inequality