狠狠撸

計算論的学習理論入門
PAC学習とかVC次元とか
Last update: 2013-06-23
Since: 2011-04-23
Yoshihiko Suhara
1
v.0.1

計算論的学習理論の歴史
? 極限における同定
– 訓練データが無限個与えられた場合に学習可能なクラス (文法)
を議論
? PAC学習
– 仮説集合?の学習問題において，危険率?で汎化誤差?の予測
器を学習するために必要な訓練データ数の下界を求める枠組み
? [証明が入ります]
? VC理論
– PAC学習の枠組みを無限の仮説集合へ拡張
– マージン最大化により汎化誤差が抑えられることを証明 [ゴール]
2

極限における同定
? 主に文法学習を対象
? 帰納推論の成功基準 [Gold 67]
– 無限の事例が与えられる (完全提示) 場合に完全学習可能な文法ク
ラスを議論する研究分野
– 無限個だったら汎化する必要ないのでは?
? 多項式時間など，収束の速さも同時に議論
? 文法の場合は全データを有限時間内に完全網羅することは不可能
? 正例と負例が十分にないと学習可能なクラスは少ない [Gold 67]
? 発展分野: 正例からの学習
– 負例がない場合の学習理論
– 負例がなくてもけっこう学習可能らしい
4

PACモデル [Valiant 84]
? 確率的近似学習
– PAC; Probably Approximately Correct (確率的に大体正
しい)
– 仮説集合が有限における学習可能性を扱う枠組み
? 極限における学習においては完全学習 (汎化誤
差0) を対象にしていた
? モチベーション: まぁまぁ良い学習をするためにど
の程度学習データが必要かという枠組みで議論
がしたい
6(*) 余談だがPAC学習という名前をつけたのはValiant本人ではなくDana Angluin [Angluin 87]

補足: 仮説集合とは?
? 既に機械学習に対する理解があるのであれば，仮説
≒分類モデルと理解すればよい
? 特徴空間と学習アルゴリズムによって仮説集合が決定
– 例) カープ判別問題
? 2次元のバイナリ特徴に対する決定木の場合，モデルの候補 (仮説
集合) は24 = 16通り存在
7
セリーグか?
(? ?)
チームカ
ラーは赤
か? (? ?)
カープか
True True YES
True False NO
False True NO
False False NO
False True
FalseTrue
○×
× ×
?1
?2
+-
仮説の一例

PAC学習の考え方
? PAC学習の考え方
– データは同じ分布から独立に取得されるものとする
? 分布の形は仮定していない (distribution free)
? ここがBayes的な方法と異なる
– 汎化誤差が?より大きい，かつ，?個の訓練データ
に無矛盾な仮説を選択してしまう確率を?以下に抑
えたい
? ?は仮説検定における危険率と同じと考えればよい
8

定理
? 定理
– 仮説集合?において危険率?以下で汎化誤差が
高々?の仮説を学習するために必要な訓練デー
タは
1
?
log
?
?
以上．すなわち，
1
?
log
?
?
≤ ?
9
仮説集合が決まれば，危険率?と汎化誤差?に対して必要な訓練データ数を評価できる
同様に，他を固定すれば汎化誤差や危険率の上界値を求めることができる
嬉しさのポイント

証明 (1/2)
? (1) 汎化誤差が?より大きい場合，?個の訓練データに対して全正解する
確率は高々
1 ? ? ?
– ※ 誤差?のときの確率で抑える
? (2) ? 個の仮説集合のうち全ての仮説の汎化誤差が?より大きい場合，
訓練データに対して全正解する確率は高々
|?| 1 ? ? ?
– 和事象の不等式 ? ? ∪ ? ≤ ? ? + ?(?)を利用
? (3) 1 +
?
?
?
< exp ? より，? = ?，? = ???とすると，
? 1 ? ? ?
≤ ? exp(???)
? 右辺の確率が危険率?以下であればよい
10

証明 (2/2)
? 前頁の結果より，
? exp(???) ≤ ?
? 両辺の対数を取ると
log |?| ? ?? ≤ log ?
? 式を整理すると
log |?| ? log ? ≤ ??
1
?
log
?
?
≤ ?
? よって，仮説集合?において危険率?以下で汎化誤差が高々?の仮説を
学習するために必要な訓練データは
1
?
log
?
?
以上
– ?「大」→?「大」
– ?「小」→ ?「大」
– ?「小」→?「大」
11

補足: 1 +
?
?
?
< exp ? の証明
? exp(?)のマクローリン展開を行う
exp ? = 1 + ? +
?2
2!
+
?3
3!
+ ?
?
? ?
?!
>
? ?+1
(?+1)!
より，? ≠ 0の際，
exp ? > 1 + ?
? ? =
?
?
とおく
exp
?
?
> 1 +
?
?
?
?
?
≥ ?1
?
?
≠ 0 の際，両辺共に非負，両辺を?乗すると
– 注:
?
?
= ?? 0 < ? ≤ 1 とおいて利用するのでこれでよい
exp ? > 1 +
?
?
?
12

簡単な例
? 先述のカープ判別問題
– 仮説集合の大きさは16
– 危険率 ? = 0.01，汎化誤差 ? = 0.1とすると，
1
0.1
log
8
0.01
= 32.04 < 33
– 33個の訓練データが必要
? そんないらんがな ?
13
定理の証明からわかるとおり，ひじょーに安全サイドに倒した
汎化誤差の評価をしているため，実用面から考えると
え??? な値になってしまう

その他の話題
? 多項式PAC学習
? Bayes-PAC学習
? など
14

Vladimir Vapnik 神
? 統計論的学習理論，VC理論の教祖，SVMの産みの親
– VC = Vapnik-Cherbonenkis
? AT&T Labs → NEC Lab. America
ご尊顔聖典

計算論的学習理論入門 -PAC学習とかVC次元とか-

PACモデルの問題点
? 従来のPACモデルでは有限の仮説集合しか扱う
ことができなかった
? 我々が普段使う手法の仮説集合は無限集合
– 例) N次元実数空間における線形識別モデルの仮説
は無限個
? このままでは無限集合であるような学習手法に
ついてPAC学習の枠組みで汎化性能を評価でき
ない ?
18

PACモデルの無限集合への拡張
? 無限の仮説集合の大きさを表すVC次元という
考え方を導入
19

VC次元の直感的な理解
? 仮説集合のVC次元 = 仮説集合に含まれる仮説
が細分 (shatter) できる点の数
– shatter とは，任意の2クラスに分類できること
20
直線によって任意の3点をshatterできる直線では4点をshatterできない
これより，2次元特徴空間における線形識別器のVC次元は3次元

VC次元に基づく汎化誤差の評価
? 以下の定理が成立
– 汎化誤差?，危険率?，データ数?，VC次元? とする
? ≤
2
?
? log
2??
?
+ log
2
?
– 仮説集合の大きさ?がVC次元?に変わっただけで
PAC学習と同じノリ
21
無限の仮説集合に対してもPAC学習と
同じ考え方が適用可能になった

線形識別モデルのVC次元は?
? N次元特徴空間の線形識別モデルのVC次元
はN+1
? あれ? 次元が増えるとVC次元も増えてしまう
– 理論的に保証される汎化性能が途端に悪くなっ
てしまう ?
? 全然うれしくない!
– でも経験的にはそんなことはない! どうすればい
いの?
22

便利！ただ問題
? 特徴次元が増加するとVC次元も増加
? 次元の呪いを克服していない
? カーネル利用により，高次元空間での線形識
別学習は，やはりVC次元も高次元になってし
まうのだろうか．．．
23

次元の呪いよさらば
? 汎化誤差に対して以下の定理が成り立つ
? ≤
2
?
64?2
?2
log
???
4?
log
128??2
?2
+ log
4
?
– ただし，? >
2
?
,
64R2
?2 < ? とする
? 式の中からVC次元が消え，マージンの大きさ?とデー
タ点を含む超球の半径?で汎化誤差を抑えている
– i.e., VC次元をマージンサイズと超球の半径で表現
– 次元の呪いよサヨウナラ!
24
※ 天下り的ですみません

マージン最大化がうれしい理由
? マージン最大化により，実行VC次元の大きさ
を抑えていると解釈できる
? 言い換えると
– マージンサイズによって仮説空間の複雑さをおさ
えることが可能になり，
– より少ない訓練データでよりよい汎化性能を得る
ことができる
25
※ 個人解釈が入っているので誤りのおそれがあります

まとめ
? 計算論的学習理論の歴史
? 極限における同定
? PACモデル
– PACモデルのうれしさ
– 定理の証明
? VC理論
– VC理論のうれしさ
– VC次元
– マージン最大化のモチベーション
26

References
? [Gold 67] E. M. Gold, “Language identification in the limit”, Information
and Control, 10, pp.447-474, 1967.
? [Valiant 84] L. G. Valiant, “A theory of the learnable”, Communications of
the Association for Computing Machinery, 27, pp.1134-1142, 1984.
? [Angluin 87] D. Angluin, “Learning regular sets from queries and counter-
examples”, Information and Computaion, 75, pp.87-106, 1987.
27

参考文献
? 榊原康文, 小林聡, 横森貴. 計算論的学習. 培風館 (2001).
? Philip D. Laird(著), 横森貴(訳). 例からの学習ー計算論的学
習理論ー. オーム社 (1992).
? Nello Cristianini, John Shawe-Taylor(著), 大北剛(訳), サポート
ベクターマシン入門, 共立出版 (2005).
28

狠狠撸

計算論的学習理論入門 -PAC学習とかVC次元とか-

Recommended

More Related Content

What's hot (20)

Similar to 計算論的学習理論入門 -PAC学習とかVC次元とか- (10)

More from sleepy_yoshi (20)

計算論的学習理論入門 -PAC学習とかVC次元とか-