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.