20190823

学習理論的な話

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

昨日の疑問

以下は言っていいんだと思う．なぜなら，左辺の集合は右辺の集合の部分集合だから．

$\begin{aligned} P \left(\left\{\omega \in \Omega | |\hat{R}(h)(\omega) - R(h)| \geq \epsilon\right\}\right) \leq P \left(\left\{\omega \in \Omega | |\hat{R}(h)(\omega) - R(h)| > \epsilon\right\}\right) \end{aligned}$

これは解決．今日はもう少し進む．

今まで有限個の仮説集合$\mathcal{H}$を考えてきたけど，現実的にはこれは無限個ある．例えば線形モデルの場合，仮説集合は，$\mathbb{R}^d$．

直感的には，仮説集合が大きければ大きいほどempirical errorを小さくできる．
有限個の仮説集合では，learning boundに$\log|H|$が出てきていて，仮説集合を大きくしすぎると，generalization errorが大きくなる恐れがある．要はトレードオフだ．この辺をやるのが正則化なんだろうけど，それはまたの話．

「大きさ」という表現をしてきたが，「複雑度」という言葉に変えようと思う．個人的には「対応力」がしっくりくるんだけども．

変な脱線

想像しやすいところから．
2クラス分類問題．

$y \in \{-1, 1\}$
$g: \mathcal{X} \to \mathbb{R}$

$yg(x)$は大きければ大きいほどいい．
多分これはマージン最大化の考え方でここでは適切ではないかもしれない．

$Y: \Omega \to \{-1, 1\}$
$X: \Omega \to \mathcal{X}$

$Y(\cdot) g \circ X(\cdot)$っていう確率変数を考える．
この期待値が大きい$f$がいいよね．
というわけで，

$\begin{aligned} \mathscr{R}(G) = \sup_{g \in G} \mathbb{E}_P \left[Y(\cdot) g \circ X(\cdot)\right] \end{aligned}$

を一種の複雑度として見ても良いような気がする．

サンプル

サンプル$S: \omega \mapsto (X_1(\omega), \ldots, X_m(\omega))$と，関数$f: \mathcal{X}^m \to [0, \infty)$の合成関数$f \circ S$をよく考える．

例えば，サンプルを$S: \omega \mapsto ((X_1, Y_1)(\omega), \ldots, (X_m, Y_m)(\omega))$として，以下の関数を考える．

$\begin{aligned} R_f: s \mapsto \frac{1}{m} \sum_{i=1}^m \ell(y_i, f(x_i)) \end{aligned}$

で，この期待値は，

$\begin{aligned} \mathbb{E}_P \left[R_f \circ S\right] \end{aligned}$

と表される．

適当に関数書いて，あとで引数を確率変数化すると楽しそう．

学習理論的な話に戻る

empirical系は全部$(\Omega, \mathcal{F}, P)$上の確率変数なんじゃないかな．

Empirical Rademacher complexity

$\begin{aligned} \hat{\mathscr{R}}_S(G) = \mathbb{E}_{P_\sigma} \left[\sup_{g \in G} \frac{1}{m}\sum_{i=1}^m \sigma_i g(z_i)\right] \end{aligned}$

$\sigma_i$はindependent uniform random variable．

この辺も$\bm{\sigma}: \omega \mapsto (\sigma_1(\omega), \ldots, \sigma_m(\omega))$を用意して，

$\begin{aligned} f: \bm{\sigma} \mapsto \sup_{g \in G} \frac{1}{m} \sum_{i=1}^m \sigma_i g(z_i) \end{aligned}$

$\begin{aligned} \mathbb{E}_P \left[f \circ \bm{\sigma}\right] = \mathbb{E}_{P_{\bm{\sigma}}} \left[f\right]. \end{aligned}$

Rademacher complexity

$\begin{aligned} \mathbb{E}_{P_S} \left[\hat{\mathscr{R}}(G)\right] \end{aligned}$

empirical distributionについて（何回目だろうか．．．）

$(\mathcal{Z}, \mathcal{F}_Z, P_Z)$上の$\mathcal{F}_Z$-可測な関数$g: \mathcal{Z} \to \mathbb{R}_+$を考える．

$g$に単調増加に各点収束する非負の単関数列$\{g_n\}_{n \in \mathbb{N}}$が存在する．

$\begin{aligned} g_n(z) = \sum_{j=1}^n a_j 1_{A_j}(z) \end{aligned}$

とする．

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

とする．

$\begin{aligned} \mathbb{E}_{D_m} \left[g_n\right] &= \int g_n dD_m \\ &= \sum_{j=1}^n a_j D_m(A_j) \\ &= \frac{1}{m} \sum_{i=1}^m \sum_{j=1}^n a_j 1_{A_j}(z_i) \\ &= \frac{1}{m} \sum_{i=1}^m g_n(z_i) \\ \end{aligned}$

なので，

$\begin{aligned} \mathbb{E}_{D_m} \left[g\right] &= \lim_{n \to \infty} \mathbb{E}_{D_m} \left[g_n\right] \\ &= \frac{1}{m} \sum_{i=1}^m g(z_i) \end{aligned}$

となる．
で，$z_i$も確率変数とみなせば，$\mathbb{E}_{D_m} \left[g\right]$も確率変数なのでは．
つまり，$Z_i: \Omega \to \mathcal{Z}$として，

$\begin{aligned} \mathbb{E}_{D_m} \left[g\right] = \frac{1}{m} \sum_{i=1}^m g \circ Z_i \end{aligned}$

これは，$(\Omega, \mathcal{F}, P)$上の確率変数になっているのだろうか．

Markov’s inequality

$\begin{aligned} P(\left\{\omega \in \Omega | X(\omega) \geq \epsilon\right\}) \end{aligned}$

以下を確認する．

$\begin{aligned} 1_{\left\{\omega \in \Omega | X(\omega) \geq \epsilon\right\}}(\omega) \leq \frac{|X(\omega)|}{\epsilon} \end{aligned}$

これより，両辺期待値をとって，

$\begin{aligned} P(\left\{\omega \in \Omega | X(\omega) \geq \epsilon\right\}) \leq \frac{\mathbb{E}[|X|]}{\epsilon} \end{aligned}$

今日は色々やって力尽きた．明日に持ち越し．

Written with StackEdit.