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

ここで,入力データは

{\displaystyle \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}の部分)で分けて考え,最後に4つを足し合わせる方法を取ってみます(図の青四角形がずれてますが,見やすくするためです).

f:id:it_k:20171001213059p:plain

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

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

 {\displaystyle \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})が間違いであることを意味しています.

これに対して,右辺では言い換えを行っています.仮説が間違っている,ということは4つにわけた許容誤差の 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)を用いることで,最終的には

 {\displaystyle \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学習についての理解の一助となれば幸いです.また,なんか間違ってない?ここおかしくない?等あれば指摘していただければと思います.

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

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

はじめに

目的

 

このブログは機械学習の書籍であるFoundations of  Machine Learning(FML)について,筆者なりに読んで理解したところをしたためていくシリーズにするつもりです

 

Foundations of Machine Learning (Adaptive Computation and Machine Learning series)

Foundations of Machine Learning (Adaptive Computation and Machine Learning series)

 

 

 

 

 

この本は研究室の輪読で使用しており,自分が理解しきれなかったところを再度理解しつつ,まとめていく所存です(現在も輪読中).

ちなみに自分は機械学習を勉強し始めた最初がこの輪読会となります(機械学習のプロではないので,予めご了承ください).

 

本書の目次です.一応この通りに記事も書いていくつもりですが,順番が変わっていたり,飛ばしたりする箇所もあるかもしれないことはご了承ください. 

  1. Introduction
  2. The PAC Learning Framework
  3. Rademacher Complexity and VC-Dimension
  4. Support Vector Machines
  5. Kernel Methods
  6. Boosting
  7. On-Line Learning
  8. Multi-Class Classification
  9. Ranking
  10. Regression
  11. Algorithmic Stability
  12. Dimensionality Reduction
  13. Learning Automata and Languages
  14. Reinforcement Learning

今回の記事では軽く,1章のIntroductionについて書いていきます.

 

1章 Introduction

機械学習とは

機械学習とは過去の情報(サンプル)を利用して,未知の情報の予測や分類を行うことです.
過去の情報の質と量によって学習機の精度が左右されることは容易に想像できますよね.そのため,機械学習アルゴリズムでは時間と空間の複雑さの他に,サンプルの複雑度も導入されます.
学習アルゴリズムがうまくいくかは使用するサンプルに依存するため,機械学習はデータ分析や統計の知識も求められます(なので自分もこの辺りに関する記事も別に書くつもりでいます).

 

何に使われているか 

最近であればあらゆるものに機械学習が使われているのではないかと思うこともありますが,一般的に知られているものは

などでしょうか.

 

機械学習のタイプ

未知の情報の予測・分類といってもどのように予測するかを 事前に決めておかなければ,何を学習すればよいかわかりません.以下のような種類で分けられることがほとんどではないかと思います.

  1. 分類
    ラベル付けされたサンプルが渡され,未知のデータに対して,なんのラベルが当てはまるかを予測する.
    例:画像分類や文字認識など

  2. 回帰
    実数値などがサンプルとして渡され,次の実数値をピタリと予測する.
    例:株価予測や天気予報など

  3. ランキング
    渡されたサンプルから基準を見出し,ランク付けし,新しいアイテムのランクを予測する.
    例:Web検索など

  4. クラスタリング
    ラベル等はつけられていないサンプルをサンプルの情報から何らかの指標をもってグループわけし,未知のデータがどのグループか予測する.
    例:コミュニティ抽出など

  5. 次元削減
    サンプルの重要な特徴を保持しつつ,次元を削減(パラメータを少なく)する.
    例?:画像処理の前処理など

以上が大まかな機械学習の予測タイプです.機械学習でなにかする,というときはサンプルから何を知りたいか,何を予測するかで手法が(当たり前ですが)変わります.どんな手法を使うかは予め自分が機械学習に何をさせたいかはっきりさせる必要があります.

 

学習の種類

機械学習の学習の仕方はアルゴリズムによって異なりますが,ここにも大まかな分類が存在しています.学習の仕方によって予測タイプの得意不得意がありますので,上の分類とともに覚えることになるでしょう.

  1. 教師あり学習
    サンプルに対して正解も共に渡され,これを元に未知のデータに対して予測できるよう学習する.
    予測タイプ:分類,回帰,ランキングなど

  2. 教師なし学習
    正解が与えられず,サンプルの情報のみから未知のデータに対して予測できるよう学習する.
    予測タイプ:クラスタリング,次元削減など

  3. 半教師あり学習
    半分正解がついている.
    予測タイプというより,データが欠損している場合など

  4. オンライン学習
    時刻毎に入力と出力(正解)のサンプルデータが渡されていき,予測モデルを更新していく.

  5. 強化学習
    学習機がアクションを起こし,それに対して報酬が返される.この報酬が各時刻において最大になるようにアクションを学習していく.
    予測タイプ:ゲームなど

  6. アクティブ・ラーニング
    学習機が能動的に(学習するにおいて)効率の良いデータを選択する.Oracle(神)に問い合わせて正解をもらい,これを学習データとして学習する.

以上が主な学習の種類となります(得意不得意があるといいながらあまり例を挙げれてないですね).

問題に対し,何を学習・予測することが解決につながるかは,人間が理解しなければなりません.このあたりを上手に把握し,適切な手法を用いることで,精度の良い予測モデルを構築することができるのでしょう.

 

今後の予定

 

今回の記事ではFMLの一章を簡単にまとめてみました.
今後も一章ずつまとめていこうかと思いましたが,一章ごとの内容を一つの記事に収めるのは大変なので,区切りのいいところで記事にしていこうと思います.

また,すべての内容に触れることはできませんので,それぞれで要点を抑えていく記事にしていけたらと思っています.

 

もし間違いや物申したい箇所等ありましたら,どんどん指摘いただけたらと思います.

間違った知識を広めたくもありませんし,残したくもありませんので(間違い自体は恥ずべきことではないと思います).

 

ご精読ありがとうございました.