20190821

わかったこと

なんか基礎的なこと

確率変数の概念を導入しよう．

$(\Omega, \mathcal{F}, P)$を確率空間とし，$X: \Omega \to \mathcal{X}$を確率変数とする．それでもって，述語$f \circ X$が成り立つ確率を考える．

これは，$B_f = \left\{x \in \mathcal{X} | f(x)\right\}$と定義して，

$\begin{aligned} P \circ X^{-1} (B_f) = P(\left\{\omega \in \Omega | X(\omega) \in B_f\right\}) \end{aligned}$

と表せる．

二変数の場合，$Y: \Omega \to \mathcal{Y}$を用意して，$(X, Y): \omega \mapsto (X(\omega), Y(\omega))$とする．さらに，$B_f = \left\{(x, y) \in \mathcal{X} \times \mathcal{Y} | f(x, y)\right\}$とする．こうすると，$f$が成り立つ確率が，

$\begin{aligned} P \circ (X, Y)^{-1} (B_f) = P (\left\{\omega \in \Omega | (X, Y)(\omega) \in B_f\right\}) \end{aligned}$

と書ける．

昨日は，

$\begin{aligned} P(\left\{y \in \mathcal{Y} | \exists x \in \mathcal{X}: f(x, y) \right\}) \end{aligned}$

というのを考えたけど，これ，$f_y(x)$を考えている．つまり，$|\mathcal{Y}|$の数だけ述語を考えている．関数の集合を考えるのではなくて，$y$を使って関数を表している．この考え方はだいぶ使えそう．

述語の集合を$\mathcal{F}$と書くと確率空間の$\sigma$-algebraと混同して紛らわしいので，述語を$h$で表して，その集合を$\mathcal{H}$と書くことにする．

$\omega$を使って関数を表そう！

学習理論的なこと

裏にある，$(\Omega, \mathcal{F}, P)$という確率空間を忘れないこと．
扱う問題が，$\omega$の述語になっていることが多いが，それがほとんどの場合省略されている．

$B_{h, c} = \left\{x \in \mathcal{X} | h(x) \neq c(x)\right\}$という集合を考える．

generalization errorは$P_X = P \circ X^{-1}$で$B_{h, c}$を測ったもの．

$\begin{aligned} R(h) = P(\left\{\omega \in \Omega | X(\omega) \in B_{h, c}\right\}) = P \circ X^{-1} (B_{h, c}) \end{aligned}$

empirical distribution

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

empirical errorは，empirical distributionで$B_{h, c}$を測ったもの．

$\begin{aligned} \hat{R}(h) &= D_m (B_{h, c}) \\ \end{aligned}$

empirical distributionの値は確率変数（多分）．なのでempirical errorも確率変数．

$\begin{aligned} \hat{R}(h)(\omega) = D_m(B_{h, c})(\omega) &= \frac{1}{m}\sum_{i=1}^m 1_{B_{h, c}} \circ X_i (\omega) \end{aligned}$

これはサンプルによるのだから，当たり前といえば当たり前．

一方で，generalization errorは定数．

$\hat{R}(h) = 0$なる$h$を，consistent hypothesisと呼ぶ．
これは常に存在するとは限らないので，存在確率を考えてみよう．

$\begin{aligned} P \left(\left\{\omega \in \Omega | \exists h \in \mathcal{H}: \hat{R}(h)(\omega) = 0\right\}\right) &= P \left(\left\{\omega \in \Omega | \vee_{h \in \mathcal{H}} \hat{R}(h)(\omega) = 0\right\}\right) \\ &= P \left(\cup_{h \in \mathcal{H}} \left\{\omega \in \Omega | \hat{R}(h)(\omega) = 0\right\}\right) \\ &\leq \sum_{h \in \mathcal{H}} P \left(\left\{\omega \in \Omega | \hat{R}(h)(\omega) = 0\right\}\right) \end{aligned}$

右辺の中身を少し調べると，

$\begin{aligned} \hat{R}(h)(\omega) = 0 &\Leftrightarrow \wedge_{i=1}^m 1_{B_{h, c}} \circ X_i (\omega) = 0 \\ &\Leftrightarrow \wedge_{i=1}^m X_i(\omega) \notin B_{h, c} \\ \end{aligned}$

となるので，

$\begin{aligned} P \left(\left\{\omega \in \Omega | \exists h \in \mathcal{H}: \hat{R}(h)(\omega) = 0\right\}\right) &\leq \sum_{h \in \mathcal{H}} P \left(\cap_{i=1}^m X_i^{-1}(B^c_{h, c})\right) \\ &= \sum_{h \in \mathcal{H}} \prod_{i=1}^m P \circ X_i^{-1}(B^{c}_{h, c}) \\ &= \sum_{h \in \mathcal{H}} \prod_{i=1}^m (1 - P \circ X_i^{-1}(B_{h, c})) \\ &= \sum_{h \in \mathcal{H}} (1 - P \circ X^{-1}(B_{h, c}))^m \\ &= \sum_{h \in \mathcal{H}} (1 - R(h))^m \\ &= |\mathcal{H}| (1 - R(h))^m =: \delta\\ \end{aligned}$

consistent hypothesisが存在する確率が，generalization errorを使って抑えられている．

ちょっとよくわからんけど，こんなバウンドを出せたのは初めてなので進歩したと思っておく．

sampleの話

$S: \omega \mapsto (X_1(\omega), \ldots, X_m(\omega))$という確率変数を考える．
$B \subset \mathcal{X}^m$に対して

$P \circ S^{-1}(B) = P(\left\{\omega \in \Omega | S(\omega) \in B\right\})$

を考える．これとempirical distributionとの関係は？

$P \circ S^{-1}$は$\mathcal{X}^m$上の測度っぽいけど，empirical distributionは$\mathcal{X}$上の測度．で，多分これもいろいろなところで使う．

$h_S$なんかはサンプルに依存してるので，$R(h_S)$とかを扱う際にはこれで測ることになる．結構複雑だ．あれ，ちょっと思いついた．

学習理論的なこと part 2

サンプルを使って出した$h_S \in \mathcal{H}$がconsistentだとする．これは，$S$に依存していて，確率変数とみなせる．

$\begin{aligned} B_{c} = \left\{s \in \mathcal{X}^m | P \circ X^{-1}\left(\left\{x \in \mathcal{X} | h_s(x) \neq c(x)\right\}\right)\right\} \end{aligned}$

これはまさに，$h$を$s$で表している！$P \circ S^{-1}$で測れる．多分$s$は無限個あるので，$h_s$も無限個ある．