今回はメインの結論に近いところから学んでいて、メインの結論を直感的に理解することを目的とします。前回は、McDiarmid's inequalityをつまみ食いしたので、今回はLemma 1 (Estimation error suboptimality bound)と、risk decomposisionの２つを学んで。。そこからERM (empirical risk minimization)における、SLTの興味深い主な結論を理解することをゴールとします。
前回の記事:
各コンセプトを図示したところ、今回は最後の重要な結論の緑の箇所"Main Concentration Results for ERM"の結論に直結した２つを学びます。
Lemma 1 (帽子) Estimation Error Suboptimality Bound
Lemma 1
$$L(\hat{g}) - L(g^*) \le 2 \sup_{g \in \mathcal{G}} \left| \hat{L}(g) - L(g) \right|$$
これ理解するための記号とか頭に入ってないな。まずセクション１見てから、Lemma 1に戻る。
- -1, +1のラベルの分類設定 ($g : \mathbb{R}^d \to {-1, +1}$)
- Lemma 1の右辺の$L(g)$はexpected lossで、$S_n$はトレーニングデータ。$l$はロス関数で、引数の２つの変数を比べる。
$$L(g) := \mathbb{E}[l(g(X), Y) | S_n],$$ - 上述のロスの$L(g)$のなかに、ロス関数$l$が入っているのでややこしい。
- ロス関数の例: $l(s, t) = \mathbb{I}_{{s \neq t}},$
- Lemma 1の左辺の$\hat{L}$は実際のempiricalなロスで、添字がついたのは具体的なサンプルたち。
$$\hat{L}(g) := \frac{1}{n} \sum_{i=1}^n l(g(X_i), Y_i)$$ - それと似た$L(\hat{g})$もKenna 1の左側あるけど、ハットは内側の$\hat{g}$についている。これを再確認したい。記号付きの$g$の親戚はふたつ($\hat{g}$, $g^*$)あり、すでに確認した$\hat{L(g)}$, $L(g)$などから定義される。
$$\hat{g} := \operatorname{argmin}_{g \in \mathcal{G}} \hat{L}(g)$$
$$g^* := \operatorname{argmin}_{g \in \mathcal{G}} L(g)$$
Lemma 1の不等式を眺める。上から抑えるような不等式では、実際は左側にあるものを求めるのが難しいから、右側という実験的に測定しやすいもので置き換えているのか？と式をよく読まずに思ったが、よくみてみるとそうではない。Lemma 1では、つまり、特に記号がついていない左辺の$L(\hat{g})$, $L(\hat{g})$と、右辺の$L(g)$の両方は、実際は我々に求められない。いっぽうで、のこりひとつの$\hat{L}(g)$は実験的に求められるようだ。
結局、左辺と右辺に我々が知り得ない項が３つもまだあるのが興味深い。おそらくただ単にLemma 1は中間地点だけなのかもしれない。ただ、すくなくとも、まったくわけのわからない左辺を、一つだけ具体的なもので置き換えることに成功したので、そこまで悲観的にならなくてもよさそうだ。
さきにすすむとLemma 1を使う議論が出てくるが、$L(g^*)$が$L(g_B)$に置き換わっていて、この$g_B$はBayes classifierの最適解だ。これはあくまで具体的な話をするために$g_B$にしたのだろう。そして、それをLemma 1で上から抑えたときのsupを$Z$として以下のようにいて、これからさらに不等式を変形していくようだ。
$$Z:=\sup_{g \in \mathcal{G}} \left| \hat{L}(g) - L(g) \right|$$
Z = Z - EZ + EZ
次のおおまかなながれとしては、以下のようなトリックをもちいて、McDiarmidの形に近づけるようだ。
$$Z = \underbrace{Z - \mathbb{E}Z}_{McDiarmid} +\mathbb{E}Z$$
この部分で、前回のMcDiarmidの前提条件に、今回の状況がどう当てはまるか理解する必要がありそうだ。
McDirmidを使うために前提を確認する
このトリックのあとにでてくる、以下の数式の事項が、上の概要のトリックにどう関連しているのか、ぱっとみよくわからないな。てっきりLemma 1の右側を変形していくのかと思いきや、Lemma 1の左側に近いものを、上から抑えている。ZはLemma 1の右側のsupを置き換えたものだしな。なるほど、ここでは、Lemma 1の左側残しつつ、Lemma 1の右側を、例のトリックでさらに変形したことが推察される。
$$L(\hat{g}) - L(g_B) \le 2B\sqrt{\frac{\ln(1/\delta)}{2n}} + 2\mathbb{E}Z$$
ここでは、実はいくつか変数と条件が追加されている。
- ロス関数$l$は区間の大きさが$B$を超えない。
- $\delta\in(0, 1]$のとき、上記の不等式は確率 $1-\delta$で成り立つ。
McDiarmid inequalityを使う際に、$Z$を$Z_i$の関数$f$として置き換えていいのは、$Z_i$が$\hat{L}(g)$を決定するから。
$$Z := f(Z_1, \dots, Z_n) = \sup_{g \in \mathcal{G}} |\hat{L}(g) - L(g)|$$
この$Z_i$ の登場によって、McDiarmid inequalityの前提条件を考えていく必要があり、$Z_i$と、supの中の$\hat{L}(g)$の関係を知りたい。
$$\hat{L}(g) = \frac{1}{n} \sum_{i=1}^n l(g(X_i), Y_i)$$
これと$Z_i$ の関係がわかりにくいが、$Z_i=(X_i, Yi)$だったので、以下のようにかける。
$$\hat{L}(g) = \frac{1}{n} \sum_{i=1}^n l(g; Z_i)$$
さきほどの$l$の変化が$B$を超えないという条件があるので、$Z_i$を$Z^{'}_i$に変化させたとき、$\hat{L}(g)$の変化はおおくても$B/n$である。これはMcDirmidtの前提条件のBounded differenceに対応させることができる。この前提条件を再び記述すると、条件を満たしていることがわかる。($c_i = \frac{B}{n} \quad \text{for all } i = 1, \dots, n$)
Assumption 14 (BOUNDED DIFFERENCE ASSUMPTION). Let $A$ be some set; a function $f : A^n \rightarrow \mathbb{R}$ satisfies the bounded difference assumption, if there exist real numbers $c_1, \dots, c_n > 0$ so that for all $i = 1, \dots, n$,
$$\sup_{z_1, \dots, z_n, z_i' \in A} |f(z_1, \dots, z_n) - f(z_1, \dots, z_{i-1}, z_i', z_{i+1}, \dots, z_n)| \leq c_i.$$
McDirmdt inequalityを適用する
McDirmdt inequalityを思い出すとと以下：
$Z_1, \dots, Z_n$ be independent random variables taking values in some set $A$. Under the bounded difference assumption, it holds, for all $t > 0$,
$$\mathbb{P}(f(Z_1, \dots, Z_n) - \mathbb{E}f(Z_1, \dots, Z_n) \ge t) \le e^{-2t^2 / \sum_{i=1}^n c_i^2}.$$
この左はZ-EZの形になっているので、あとは右辺を具体的に$c_i$の値を代入するだけでこうなる。
$$P\left( Z - \mathbb{E}Z \geq t \right) \leq e^{-\frac{2nt^2}{B^2}}$$
これでもZ-EZの部分の話はおわりかとおもいきや、この左辺は確率を考えているので、右辺は上限の確率であり、これを$\delta$と読んでいる。これは、$t$を超えてしまう確率の上限なので、逆に、超えないとくの確率として、 「上記の確率は$1-\delta$でなりたつ」の部分に対応している。
このあと$t$が定まっている議論があるがなぜ？すべての$t$についてじゃなかったの？なぜt求める必要がある？
$t$は統計の授業でたまにみる、ある確率変数が平均から外れてしまうときの、最低のラインを意味する。でも、今回はそちらではなく、右辺の$\delta$ (or $1-\delta$)に関して興味があり、この不等式が成り立つ確率的な度合いを知りたいし、成り立つ確率を高めたい。
つまり、「失敗する確率（外れる確率）を $\delta$ 以下に抑えたいとき、そのときの誤差の閾値 $t$ は具体的にいくつになるか？」、ということになる。
これをもとめるために、右辺を$\delta$とおき、$t$に付いて解く作業をする。
$$e^{-\frac{2nt^2}{B^2}}=\delta$$
結果的にこうなる。
$$t = B\sqrt{\frac{\ln(1/\delta)}{2n}}$$
これで、$t$が求まったのはわかった。これにより、Z-EZがこの具体的なしきい値をこえる、失敗するイベントは多くとも確率$\delta$で発生することがわかったので、これはうらがえしに：
$$Z - \mathbb{E}Z < B\sqrt{\frac{\ln(1/\delta)}{2n}}$$が確率 $1-\delta$ で成り立つということ。
これまでのまとめ
Lemma 1でベイズ分類器を$g_B$として理想的な解としたあと、この結果を適用すると少なくとも確率$1-\delta$でいかが成り立つ：
$$L(\hat{g}) - L(g_B) \le 2B\sqrt{\frac{\ln(1/\delta)}{2n}} + 2\mathbb{E}Z $$
ここまで来たので、あとは右辺の$\mathbb{E}Z$を評価したいところです。それにはRademecher complexityというものを理解しないといけないので、それは次の記事にて。
References
RPTU ML3 (Learning Theory) Lecture notes from Prof. Marius Kloft