20190822

ほとんど寝ていた気がする．．．
タバコのせいで集中力を削がれている気がする．．．

学習理論的なこと

今日も$(\Omega, \mathcal{F}, P)$を忘れない．

generalization errorとempirical errorを誤解していたかもしれない．

サンプル$S: \omega \mapsto (X_1(\omega), \ldots, X_m(\omega))$を用意．

今回から，$h_s$というのを考える．

generalization error:

$\begin{aligned} R(h_s) = P_X(\left\{x \in \mathcal{X} | h_s(x) \neq c(x) \right\}) \end{aligned}$

これは，確率変数．なので，以下のように確率を考えられる．

$\begin{aligned} P \circ S^{-1} (\left\{s \in \mathcal{X}^m | R(h_s) > \epsilon\right\}) \end{aligned}$

次に，empirical error．

$\begin{aligned} \hat{R}(h_s) &= D \left(\left\{x \in \mathcal{X} | h_s(x) \neq c(x)\right\}\right) \\ \end{aligned}$

これも確率変数なので，

$\begin{aligned} P \circ S^{-1} (\left\{s \in \mathcal{X}^m | \hat{R}(h_s) > \epsilon\right\}) \end{aligned}$

を考えられる．

empirical distributionについてもう少し詳しく

empirical distribution:

$\begin{aligned} D_m = \frac{1}{m}\sum_{i=1}^m \delta_{X_i} \end{aligned}$

$X_i$は$(\Omega, \mathcal{F}, P)$上で定義された確率変数．

empirical distributionの値:

$\begin{aligned} D_m(B)(\omega) &= \frac{1}{m}\sum_{i=1}^m \delta_{X_i(\omega)} (B) \ \cdots \ (1) \\ D_m(B)(s) &= \frac{1}{m}\sum_{i=1}^m 1_{B} (x_i) \ \cdots \ (2) \end{aligned}$

どっちも同じことなのだけれど，(1)のようにみれば，$P$で測れて，(2)のようにみれば，$P \circ S^{-1}$で測れる．だいたい(2)なのではないかと思う．試しにempirical errorの期待値を見てみる．sampleは独立に同一の分布に従うとする．

$B_h = \left\{x \in \mathcal{X} | h(x) \neq c(x) \right\}$

empirical error:

$\begin{aligned} \mathbb{E}_P [\hat{R}(h)] &= \frac{1}{m} \sum_{i=1}^m \mathbb{E}_P \left[1_{B_h} \circ X_i\right] \\ &= \frac{1}{m} \sum_{i=1}^m \mathbb{E}_{P_X} \left[1_{B_h}\right] \ \text{(transformation formula)}\\ &= R(h) \end{aligned}$

どう頑張っても，$R(h)$は確率変数ではない．$R(h_s)$は確率変数だが．

確率変数$\hat{R}(h)$の期待値が$R(h)$なことを利用して様々なことが言える．

Hoeffding’s inequality

独立な確率変数の和$S_m = \sum_{i=1}^m X_i$を考える．$X_i: \Omega \to [a_i, b_i]$とする．

$\begin{aligned} P(\left\{\omega \in \Omega | S_m(\omega) - \mathbb{E} [S_m] \geq \epsilon\right\}) &\leq \exp \left(- 2 \epsilon^2 / \sum_{i=1}^m (b_i - a_i)^2\right) \\ P(\left\{\omega \in \Omega | S_m(\omega) - \mathbb{E} [S_m] \leq - \epsilon\right\}) &\leq \exp \left(- 2 \epsilon^2 / \sum_{i=1}^m (b_i - a_i)^2\right) \end{aligned}$

ってのが，Hoeffding’s inequalith．

$S_m = \sum_{i=1}^m \frac{1_{B_h} \circ X_i}{m}$という確率変数を考えれば，$\frac{1_{B_h} \circ X_i}{m} \in \{0, 1/m\}$なので，

$\begin{aligned} P \left( \left\{\omega \in \Omega | \hat{R}(h) - R(h) \geq \epsilon\right\}\right) &\leq \exp \left( - 2 m \epsilon^2\right) \\ P \left( \left\{\omega \in \Omega | \hat{R}(h) - R(h) \leq - \epsilon\right\}\right) &\leq \exp \left( - 2 m \epsilon^2\right) \end{aligned}$

が言える．さらに，

$\begin{aligned} P \left( \left\{\omega \in \Omega | |\hat{R}(h) - R(h)| \geq \epsilon\right\}\right) &\leq P \left( \left\{\omega \in \Omega | \hat{R}(h) - R(h) \leq - \epsilon\right\}\right) \\ &+ P \left( \left\{\omega \in \Omega | \hat{R}(h) - R(h) \geq \epsilon\right\}\right) \ \text{(union bound)} \\ &\leq 2 \exp \left(- 2m \epsilon^2\right) \end{aligned}$

も言える．

Learning boundの話

本当に最小化したいのは$R(h)$なのだけど，実際に評価できるのは$\hat{R}(h)$．
この差がどれくらいあるのかに興味がある．ものすごく開いているなら，そもそも意味がないからだ．
実際に差を出せればいいのだが，$\hat{R}(h)$がsampleに依存するので確率的に評価しなければならない．まあこの辺がPAC learningのモチベ．

Hoeffding’s inequalityから，すぐにlearning boundがでる．

$\begin{aligned} P \left(\left\{ \omega \in \Omega | \exists h \in \mathcal{H}: |\hat{R}(h)(\omega) - R(h) | > \epsilon\right\}\right) &\leq \sum_{h \in \mathcal{H}} P \left(\left\{\omega \in \Omega | |\hat{R}(h)(\omega) - R(h)| > \epsilon\right\}\right) \\ &\leq 2 |\mathcal{H}| \exp \left(-2m\epsilon^2\right) =: \delta \end{aligned}$

最後ちょっと疑問．
$\geq\epsilon$じゃなくて，$>\epsilon$だけど，不等式適用していいのだろうか？

$\begin{aligned} -2 m \epsilon^2 = \log \frac{\delta}{2 |\mathcal{H}|} &\Leftrightarrow \epsilon^2 = \frac{1}{2m} \log \frac{2 |\mathcal{H}|}{\delta}\\ &\Leftrightarrow \epsilon = \sqrt{\frac{\log |\mathcal{H}| + \log \frac{2}{\delta}}{2m}} \end{aligned}$

となって，少なくとも$1 - \delta$の確率で，$\forall h \in \mathcal{H}$に対して

$\begin{aligned} |\hat{R}(h) - R(h)| \leq \sqrt{\frac{\log |\mathcal{H}| + \log \frac{2}{\delta}}{2m}} \end{aligned}$

が成り立つと．

$\begin{aligned} R(h) \leq \hat{R}(h) + \sqrt{\frac{\log |\mathcal{H}| + \log \frac{2}{\delta}}{2m}} \end{aligned}$

とみるのが良さそうね．左辺を小さくしたいなら，

• $\hat{R}(h)$を小さくすればいい
• サンプル数$m$を大きくすればいい
• $\mathcal{H}$が大きいとまずい．でも$\log$なので一定のところからは気にならなくなる

こうすると，どの項がどれぐらい寄与するかを見れるのかもしれない．

今日はここまで．
今日もガンバった！

Written with StackEdit.