機械学習の問題設定

機械学習の問題設定を見直したのでメモ．

$(\Omega, \mathcal{F}, P)$: ベースとなる確率空間
$(\mathcal{X}, \mathcal{F}_{\mathcal{X}})$: 入力となる可測空間
$(\mathcal{Y}, \mathcal{F}_{\mathcal{Y}})$: 出力となる可測空間
$\mathcal{Z} = \mathcal{X} \times \mathcal{Y}$
$m \in \mathbb{N}$: サンプル数
$X_i: \Omega \to \mathcal{X}, \forall i = 1, \ldots, m$
$Y_i: \Omega \to \mathcal{Y}, \forall i = 1, \ldots, m$
$Z_i = (X_i, Y_i): \omega \mapsto (X_i(\omega), Y_i(\omega)), \forall i = 1, \ldots, m$
$S_m: \omega \mapsto (Z_1(\omega), \ldots, Z_m(\omega))$: サンプル

i.i.d.
For all $i \neq j$, $Z_i$と$Z_j$は独立
$P \circ Z_1^{-1} = \cdots = P \circ Z_m^{-1}$

$P_{Z} = P \circ Z_1^{-1}$とする．
$D_m = P \circ S_m^{-1}$

ここまでで一通りの準備を終えた．

$\mathcal{H}$: hypothesis set
$\ell: \mathcal{H} \times \mathcal{Z} \to [0, \infty)$: loss function

generalization error

$\begin{aligned} L(h) := \mathbb{E}_{P_Z} \left[\ell(h, z)\right] \end{aligned}$

ここで，Agnostic PAC learningという概念を紹介しておく．ざっくり書くと，以下のような感じ．

$\mathcal{H}$ is Agnostic PAC learnable if there exists sample complexity $m_\mathcal{H}: (0, 1)^2 \to \mathbb{N}$ and learning algorithm $\mathcal{A}_\mathcal{H}: S_m \mapsto B \subset \mathcal{H}$ which satisfy the following property:

For all $\epsilon, \delta \in (0, 1)$

$\begin{aligned} m \geq m_\mathcal{H}(\epsilon, \delta) \Rightarrow \forall h \in \mathcal{A}_{\mathcal{H}}(S_m), L(h) \leq \epsilon \end{aligned}$

with probability at least $1 - \delta$

まず，我々は$\ell$を定めることから始める．$L$を定めてもいい．よくある二乗誤差なんかをここで使うべきではなく（使っても良いけど），本当に最小化したいものをここに持ってくる．indicator functionを使うといいと思う．

$\mathcal{H}$と$\ell$が与えられればAgnostic PAC learnableかどうか調べ始めることは可能だと思うが，普通はそうしないと思う．個人的には，$\mathcal{H}$はアルゴリズムとセットで考えるべきだと思っている．アルゴリズムまで考えて，それが，Agnostic PAC learnerかどうかを調べるのが良いと思う．

Written with StackEdit.

20190829

述語なのか，命題なのかを注意して式をみる．

急に収束の速さに興味が湧いたので，関係ありそうなオーダー記法を勉強してみる．

オーダー記法

参考:

• https://azapen6.hatenablog.com/entry/2013/02/07/155401

---

Big O

$\begin{aligned} f(x) = O(g(x)) \quad (x \to \infty) \end{aligned}$

十分先で$f(x)$は$g(x)$の定数倍で抑えられる．
$\exists c > 0; \exists x_0 > 0; \forall x; x \geq x_0 \Rightarrow |f(x)| \leq c |g(x)|$．

$\begin{aligned} f(x) = O(g(x)) \quad (x \to a) \end{aligned}$

$a$らへんで，$f(x)$は$g(x)$の定数倍で抑えられる．
$\exists c > 0; \exists \delta > 0; \forall x; 0 < |x - a| < \delta \Rightarrow |f(x)| \leq c |g(x)|$．

これは，グローバルな$x_0$と$c$の存在をいっている．

---

small o

$\begin{aligned} f(x) = o(g(x)) \quad (x \to \infty) \end{aligned}$

Big Oとは違って，$c$によって，$x_0$が変わる．

$\forall c > 0; \exists x_0 > 0; \forall x; x \geq x_0 \Rightarrow |f(x)| < c |g(x)|$

$x \to a$の時:

$\begin{aligned} f(x) = o(g(x)) \quad (x \to a). \end{aligned}$

$\forall c > 0; \exists \delta > 0; \forall x; 0 < |x - a| < \delta \Rightarrow |f(x)| < c |g(x)|$

式に出てくる場合

$f(x) = 1 + 3x + O(x^2) \quad (x \to 0)$

これをみたとき，

$f(x) \leq 1 + 3x + c x^2$

を考えるのかなと思った．で，これが$0$らへんで成り立つと．
基本的に，不等式を書き直すためにあると思う．

全然進まなかったけどとりあえずこの辺で．明日もやる．

Written with StackEdit.

20190828

興味がコロコロ変わって困ってるがこれはこれで楽しい．縛られない勉強．解析学の知識がほとんどないので，本を読んでいても結構辛いことがある．というわけで復習しようと思う．やることが増えた．

• 解析学
• 学習理論
• その他

という感じ．

朝：解析学
昼：仕事
夜：学習理論

という感じで行こうと思う．空いた時間は好きなことを考える時間にする．まああくまでも目標．

土日の昼はテキストマイニングツールの開発に当てる．

とにかく焦らない．じっくり考える．わからないこと，知らないことは別に恥じゃない．

朝数学

測度論少し思い出す．

$\prod_{j=1}^d (a_j, b_j]$, $\prod_{j=1}^d [a_j, b_j]$, $\prod_{j=1}^d (a_j, b_j)$の体積を$\prod_{j=1}^d (b_j - a_j)$と定義する．いろんな関数の積分の計算をここに持ってくる．

関数を単関数で近似しても，$f^{-1}(B)$を計算するのが結構しんどいと思う．この辺はどうするんだろう？多分上の形に持ってくるのではないかと思う．それか普通にリーマン積分に持っていく．

---

$h \to a$というのは，
$h = a + 1 / n$として，$n \to \infty$（右側）,
$h = a - 1 / n$として，$n \to \infty$（左側）
のことなのかなと思う．こうすると，$\left\{a + 1 / n\right\}_{n \in \mathbb{N}}$という数列が作れる．

関数の微分を考えてみる．$f$の$x$における微分係数$f'(x)$は，

$\begin{aligned} f'(x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h} \end{aligned}$

と定義される．
このままでは意味がわからないので，$h = 1 / n$としよう．$n(f(1 + 1 / n) - f(x))$の$n \to \infty$での極限を考えたいわけだけど，$f(1 + 1 / n)$によっては発散しそう．

例えば，$f(x) = x$．
$n(f(x + 1 / n) - f(x))= n (x + 1 / n - x) = 1$
だから，$f'(x) = 1$なんだろうか．

次に，$f(x) = x^2$．
$n(f(x + 1 / n) - f(x)) = 2 x + 1 / n$
だから，$f'(x) = 2x$なんだろうか．

でも$1 / n$じゃなくても，$1 / 2^n$とかでもいいよなあ．なんかこの辺に違和感がある．

---

関数の極限を考えてみよう．

任意の$\epsilon > 0$に対して，ある$\delta > 0$が存在して，$0 < |x - a| < \delta \Rightarrow |f(x) - l| < \epsilon$が成り立つとき，$\lim_{x \to a} f(x) = l$と書くんだ．$l = f(a)$のとき，$f$は連続というんだ．

これの肝は，$x$は$a$に近いところから取ってくればいいんだけど，$a$にはなれないということ．もし$l = f(a)$なら，$a$になれないのに，$f(a)$にいくらでも近づけることができるという不思議なことが起こる．

個人的には，これよりも上に書いたように数列に変換してしまうのが好き．そこで，スモールオー，ビッグオーというのを思い出した．

---

ランダウの記号（スモールオー）

参考:

• https://motochans.blogspot.com/2014/10/blog-post_13.html

$\frac{f(x)}{h(x)} \to 0 \quad (x \to a)$なら，

• $f$が$h$よりも速く0に収束する
• $h$が$f$よりも速く$\infty$に発散する

のどちらかだ．この場合，$f(x) = o(h(x))$と書く．どちらの意味で捉えてもいい．

$f$が発散しても，それよりも速く発散する$h$を分母に持ってくれば，何かしらの極限が存在することになる気がする．逆に$h$が$0$に収束しても，それよりも速く$0$に収束する$f$を分母に持ってくれば何かしらの極限が存在することになる．個人的には発散すると捉える方がしっくりくる．

$x^{n}$よりも$x^{n+1}$の方が速く発散する．なので，$x^{n} = o(x^{n+1}) \quad (x \to \infty)$．

なんか不等式も同じような感じがする．
また戻ってこれなさそうなので，この辺でやめとこ．

---

上で$\frac{1}{n}$でも$\frac{1}{2^n}$でも0に収束するなら，それ以外でもいいと書いたけど，違いは収束の速さな気がする．

---

考えたいけど，眠いから寝よう．．．

Written with StackEdit.