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$も無限個ある．

20190820

わかったこと

なんか基礎的なこと

存在量化子と全称量化子の間を取るのが確率なのかも．
以下の二つはどちらもtrueかfalseである．

• $\exists x \in \mathcal{X}: f(x)$
• $\forall x \in \mathcal{X}: f(x)$

$P(\left\{x \in \mathcal{X} | f(x) \right\})$のように確率を使って，この間を取ることができる．1なら下が成り立つと解釈してもいいし，0じゃないなら上が成り立つと解釈してもいいだろう．

二変数以上の場合を考えると，全称と存在を述語に入れなければならないケースが出てくる．以下の二つの述語を考える．

• $\exists x \in \mathcal{X}: f(x, y)$
• $\forall x \in \mathcal{X}: f(x, y)$

例えば，$f_x(y) = f(x, y)$という述語が成り立つ確率を知りたい場合は，

$\begin{aligned} P(\left\{y \in \mathcal{Y} | \exists x \in \mathcal{X}: f(x, y) \right\}) &= P(\left\{y \in \mathcal{Y} | \vee_{x \in \mathcal{X}} f(x, y) \right\}) \\ &= P(\cup_{x \in \mathcal{X}} \left\{y \in \mathcal{Y} | f(x, y) \right\}) \\ &\leq \sum_{x \in \mathcal{X}} P(\left\{y \in \mathcal{Y} | f(x, y) \right\}) \end{aligned}$

と，上界を出すことができる．

全称の場合はこんなにうまく出せないので確率の性質$P(\mathcal{Y}) = 1$を使う．

$\forall x \in \mathcal{X}: f(x, y)$の否定は，$\exists x \in \mathcal{X}: \neg f(x, y)$なので，上と同様にして，

$\begin{aligned} P(\left\{y \in \mathcal{Y} | \exists x \in \mathcal{X}: \neg f(x, y)\right\}) &= P(\left\{y \in \mathcal{Y} | \vee_{x \in \mathcal{X}} \neg f(x, y)\right\}) \\ &= P(\cup_{x \in \mathcal{X}} \left\{y \in \mathcal{Y} | \neg f(x, y)\right\}) \\ &\leq \sum_{x \in \mathcal{X}} P(\left\{y \in \mathcal{Y} | \neg f(x, y)\right\}) =: \delta \end{aligned}$

となるので，

$\begin{aligned} 1 - P(\left\{y \in \mathcal{Y} | \forall x \in \mathcal{X}: f(x, y)\right\}) \leq \delta \\ \Leftrightarrow P(\left\{y \in \mathcal{Y} | \forall x \in \mathcal{X}: f(x, y)\right\}) \geq 1 - \delta \end{aligned}$

と書ける．これはめちゃめちゃ使うので理解しないといけない．

Written with StackEdit.

述語論理と集合

復習したのでメモ．

$f: \mathcal{X} \to \{0, 1\}$を述語（条件）と言おう（0はfalse, 1はtrueを表す）．$\left\{x \in \mathcal{X} | f(x) = 1\right\}$を，単に$\left\{x \in \mathcal{X} | f(x)\right\}$と書こう．述語は自然言語で書いてもいいので，かなり自由度が高い．

全称と存在を考える．以下は命題になる．

$\begin{aligned} \forall x \in \mathcal{X}, f(x) \\ \end{aligned}$

ちょっと見方を変えると，これは，

$\begin{aligned} \wedge_{x \in \mathcal{X}} f(x) \end{aligned}$

と同じ多分．$\mathcal{X}$が有限じゃない時とかはよくわからんけど．

存在も以下のように似たように考えればいい．

$\begin{aligned} \exists x \in \mathcal{X}, f(x) \Leftrightarrow \vee_{x \in \mathcal{X}} f(x) \end{aligned}$

$f: \mathcal{X} \times \mathcal{Y} \to \{0, 1\}$を考える．以下は述語．

$\begin{aligned} \wedge_{x \in \mathcal{X}} f(x, y) \end{aligned}$

これが成り立つ$y$の集合を考える．

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

おそらく，

$\begin{aligned} \left\{y \in \mathcal{Y} | \wedge_{x \in \mathcal{X}} f(x, y) \right\} = \cap_{x \in \mathcal{X}} \left\{y \in \mathcal{Y} | f(x, y)\right\} \end{aligned}$

となる．

存在の方も同様に，

$\begin{aligned} \left\{y \in \mathcal{Y} | \vee_{x \in \mathcal{X}} f(x, y) \right\} \Leftrightarrow \cup_{x \in \mathcal{X}} \left\{y \in \mathcal{Y} | f(x, y)\right\} \end{aligned}$

となると思う．

これは，確率を考える上でかなり大事になってくると思う．
何かが存在する確率を，和集合の確率で表すことができて，そのupper boundが簡単にでる．この辺はまた今度気が向いたら書こうと思う．