The PAC Learning Frameworkについて

The PAC Learning Framework

二章のThe PAC Learning Frameworkについてやっていきます．

モチベーション

与えられたサンプルから，何かを学習するアルゴリズムを考える時，

何が効率的に学べるのか？
何が本質的に学ぶのが難しいのか？
どのくらいのサンプルが正しく学習するのに必要か？
学習の一般的なモデルはあるのか？

などについて考慮する必要があります．これらを包括的に議論することができる枠組み (Framework) としてここではPAC学習を導入しています．

つまり，PAC学習という学習モデルを用いることで，問題に対する難しさや本当に学習できるのかと言った学習保証の指標となる，といったところでしょうか．

それではPAC学習というものについて，詳しく見ていきます．

PAC学習とは

Probably Approximately Correct Learning (PAC学習)とは，学習モデルの一つであり，訳すと確立的に大体正しい学習となります．

厳密に正しいものを学習するというよりは，多少は間違えてもいいからそれっぽい答えを学習するモデルがPAC学習モデルです．

例として，四角形の大きさを予測する問題を考えましょう．

f:id:it_k:20171001155454p:plain

ここで，入力データは

$\mathcal{X} = \{(x_1, y_1),(x_2, y_2), \cdots\} \\ \mathcal{Y} = \{0, 1} \$

のようになり， ${\mathcal{X}}$ はx座標とy座標のデータを表しており， ${ \mathcal{Y}}$ はデータに対して，正解の四角形の中にあれば1，外にあれば0になる正解ラベルを表しています．

ちなみに，今回の「四角形」のような学習対象のことを概念といいます．

また，PAC学習によって概念に近づけていくもののことを仮説といい，仮説と概念の間の誤差がある一定以上になるまで学習して仮説を更新していくことがPAC学習の流れとなります．

概念や仮説といった単語は今後もでてくるかと思います．

それでは，今回は以下の図に示されるようなサンプルデータをもらえたとします．今回は座標データに基いて座標軸上にプロットし，点の形をラベルが1ならマル，0ならバツで表記しています（実際は座標とラベルがセットになったデータ列が渡され，赤枠の四角形の外形はわかりません）．

f:id:it_k:20171001161244p:plain

これらのデータから，赤枠の四角形の大きさをどのように学習すればいいか，仮説を立てます．

ここでは仮説を「正解のラベルをぎりぎり囲む四角形」としましょう．

すると，学習の結果得られた四角形は以下の図の青枠となります．

f:id:it_k:20171001162204p:plain

だいぶ誤差はありますが，それなりに近い四角形が描けました．

今度はこの結果を答えとしていいのかどうかの指標が必要になります．

PAC学習では確立的に大体正しければ良いので，誤差がある確立 ${\epsilon}$ で抑えられているならば答えとして正しいことになります（つまり， $\epsilon$ は誤差の許容範囲です）．

誤差がどのくらいであるかは，次に来るデータのラベルをどれだけ正解と同じに応えられるか，で測ることができます．

今回得られるデータはすべて互いに独立で同一の確立分布のもとで発生したデータであると考えると，誤差というものは，次に来るデータが「仮説でつくられた青の四角形の外で，かつ正解の赤の四角形の中に来る確立」で定義できることになります．

f:id:it_k:20171001211802p:plain

これを数式で表せるようにします．今回は四角形なので，上（ ${r_4}$ の部分），下（ ${r_2}$ の部分），右（ ${r_1}$ の部分），左（ ${r_3}$ の部分）で分けて考え，最後に４つを足し合わせる方法を取ってみます（図の青四角形がずれてますが，見やすくするためです）．

f:id:it_k:20171001213059p:plain

単に四等分しただけなので，それぞれの確立は少なくとも ${\frac{\displaystyle \epsilon}{4}}$ です．

ここで，青い四角形を ${\mathrm{R_s}}$ とおくと，

$\underset{S \sim D^{m}}{\mathrm{Pr}} [R(\mathrm{R_s}) \gt \epsilon ] \leq\underset{S \sim D^{m}}{\mathrm{Pr}} \left[\bigcup^{4}_{i=1}{\mathrm{R_s} \cap r_i = \emptyset } \right]$

と書き表すことができます．

ここで， ${\underset{S \sim D^{m}}{\mathrm{Pr}}[x]}$ とは， $x$ が分布 $D^m$ 上で起こりうる確立のことで， $R(\mathrm{R_s})$ は $\mathrm{R_s}$ と目標としている概念との誤差を示します．よって，上記の式の左辺は $\mathrm{R_s}$ （青の四角形）と目標の概念（赤の四角形）との誤差が $\epsilon$ を超過していることを示しています． $\epsilon$ は誤差の許容範囲のことですので，要するに仮説（今回は $\mathrm{R_s}$ ）が間違いであることを意味しています．

これに対して，右辺では言い換えを行っています．仮説が間違っている，ということは４つにわけた許容誤差の $r$ それぞれに対して，どれか一箇所でも重なっていない場所がある，ということに言い換えられます．

さらにこの式を変形していきます．確立を ${P(x)}$ と表すときに

${P(A_1 \cup \cdots \cup A_n) = \sum_{i=1}^{n}P(A_i)}$

であることを利用すると，右辺において総和を使用した形に置き換えられます．よって右辺は

$\displaystyle \leq \sum_{i=1}^{n} \underset{S \sim D^{m}}{\mathrm{Pr}} [ \mathrm{R_s} \cap r_i = \emptyset ]$

のように書き換えることができ，これによってそれぞれの $r$ について考えることができます．

さらにこの式を変形させていくのですが，ここでようやくサンプル数 $m$ が登場します．元々，サンプル数がどれだけ必要か，効率良く学習できるのかの指標としてPAC学習が導入されたという話でした．式中の $\mathrm{R_s} \cap r_i = \emptyset$ をサンプル数 $m$ で具体的に表します．

ある確立 $p$ で発生するサンプルが $m$ 回の試行で一度も得られない確立は $\displaystyle (1-p)^m$ で表すことができます．

これを先程の式にも当てはめてみると， $\frac{\epsilon}{4}$ の確立で発生する例が $m$ 回の試行で一度も得られない確立（すなわち $\underset{S \sim D^{m}}{\mathrm{Pr}} [ \mathrm{R_s} \cap r_i = \emptyset ]$ ）とは $\displaystyle (1- \frac{\epsilon}{4})^m$ として表す事ができます．これによって右辺はさらに

$\displaystyle \leq 4(1-\frac{\epsilon}{4})^m$

と書き換えることが出来ます．また，よく知られた不等式である $1-x \leq \exp(-x)$ を用いることで，最終的には

$\underset{S \sim D^{m}}{\mathrm{Pr}} [R(\mathrm{R_s}) \gt \epsilon ] \leq 4 \exp(-\frac{\epsilon m}{4})$

と書き表す事ができます．

さて，ここまできて何が嬉しいかというと，仮説 $\mathrm{R_s}$ が間違っている（誤差 $\epsilon$ 以上である）確立というものが，試行回数 $m$ を用いた式で表現できたのです．簡単に言えば， $m$ 回くらいやって初めて間違えるくらいの仮説だよ，という評価が行えるということです．

ここで， $\underset{S \sim D^{m}}{\mathrm{Pr}} [R(\mathrm{R_s}) \gt \epsilon ]$ とは，間違える確立，という話でした．なので，これ自体も信頼度 $\delta$ で表現することにします．すなわち， $\underset{S \sim D^{m}}{\mathrm{Pr}} [R(\mathrm{R_s}) \gt \epsilon ] \leq \delta$ という式で表します．誤差も確立なので混同しがちですが，例えるならば，テストの点が80点で合格（誤差が20点）のところ，テスト10回受けて9回それができれば良い（信頼度が10分の1），ということです．

以上から信頼度 $\delta$ を用いると，上式から

${\displaystyle4 \exp(-\frac{\epsilon m}{4}) \leq\delta \iff m \geq \frac{4}{\epsilon}\log{\frac{4}{\delta}}}$

とすることができますので，最終的な意味としては，この仮説で誤差 $\epsilon$ と信頼度 $\delta$ を保証するには少なくともサンプルが $m$ 個必要，となります．

この式により，何かを学習するアルゴリズム（仮説）を考えた時，それが十分使える誤差，信頼度を与えた場合に必要とするサンプル数が現実的な数か否かや，数値の比較でどっちが効率的かなどが議論できるはずです．そしてこのような不等式が成り立つとき，その学習させたい問題はPAC学習可能であるといいます．（ちなみに今回の例に使った四角形の大きさ予測問題の学習の難しさは $O(\frac{1}{\epsilon}\log{\frac{1}{\delta}})$ と表す事ができます．）

このようにしてPAC学習という枠組みが，その問題がそもそもどれくらい難しいか，どれだけサンプルを必要とするのか，そもそも学習可能なのか，を示す指標となりうるのです．

本章ではさらにこの後定理や証明その他が続いておりますが，今回記事でまとめたかったPAC学習についてはこのくらいでいいかなと思いますので，2章についてはここで終わりとさせていただきます．

おわりに

いかがだったでしょうか．このように記事でまとめるという作業自体が初めてで，記事を書くことに大変時間がかかってしまいました．拙い文章で申し訳ないですが，少しでもPAC学習についての理解の一助となれば幸いです．また，なんか間違ってない？ここおかしくない？等あれば指摘していただければと思います．

更新が長いあいだ滞ってましたが，気楽に続けていきます．次回からはもっとざっくりとエッセンスをまとめて見やすくわかりやすくして，まずはとにかくどんどん章を進ませていきたいと思います．

最後まで読んでくださりありがとうございました．