はじめに
最近自身の研究で使うため統計的学習理論の勉強をしています. 2回に渡って基本的な内容をまとめてみます.
目次
定式化
まず, 統計的学習理論のモチベーションを述べます.
入力空間に値をとる確率変数を, 入力空間から出力空間への写像をとしてlabeling functionと呼ぶことにします.
また, 入力が従う確率分布をとします ().
損失関数としてを用いるとします.
このとき, ある仮説の予測損失は次のように定義されます.
つまり, 分布における予測値の損失の期待値です.
をできるだけ小さくするような仮説を見つけ出すことが目標です.
ここで, 予測損失がわかっていれば, 問題は随分簡単になるのですが, 残念ながらデータの真の分布は未知です.
よって, 有限の観測データから, 予測損失をできるだけ小さくする仮説を導く必要があります.
予測損失を観測データから評価する上で最も大きな手がかりは経験損失です. データ が観測されたときの経験損失は次のように定義されます.
ここで, をデータの経験分布としました. これは, データ数がのときに, 確率で各観測データの値をとるような分布のことです.
今をある有限な仮説集合とします.
このとき, この仮説集合に含まれる仮説の中で予測損失と経験損失を最小化するような仮説をそれぞれと表しておきます.
は, Empirical Risk Minimizerと呼んだりもします. について, 定義より次の2つの不等式が成り立ちます.
ここで私たちが導きたいのは, 観測データから計算できる経験損失を最小化する基準で得られる仮説の期待損失と
仮説集合を用いたときに達成され得る最小の期待損失の差を次のように評価することです.
少なくともの確率で次の不等式が成り立つ.
次章では, 仮説集合とに依存する [extra term]を具体的に求めます.
有限仮説集合の場合の予測損失の上界の導出
さて, 本記事で考えている仮説集合は有限でした. またここでは , 損失関数がある定数で上からboundできるとします (例えば, 01-lossの場合は, ). この場合, こちらの記事で紹介したHoeffding's ineqを用いてとの差を評価することができます.
まず,
ここで, 右辺の裾確率をunion boundとHoeffding's ineqを用いて次のように評価します. 途中で係数2が登場しているのは, 誤差の絶対値を評価するため両側の裾確率を考慮しているからです.
右辺をと置いてについて解けば,
よって,
なので, 少なくともの確率で次の不等式が成り立ちます.
以上の結果を統合すると, 最終的な目標であった次の不等式が少なくともの確率で成り立つという結果を得ます.
したがって, 仮説集合が有限である場合, はに 少なくともで収束することがわかります.
さいごに
今回は, 仮説集合が有限な場合のの予測損失の上界をHoeffding's ineqを用いて導出しました. しかし, 今回導いた上界は仮説集合が無限である場合 (i.e., ) 実用的ではありません. (上界の第2項を見れば一目瞭然.) よって, 次はRademacher Complexityという仮説集合の複雑さの指標を用いて仮説集合が無限の場合も意味を成す期待損失の上界を導いてみます.
参考
[金森 (2015)] 金森敬文. 2015. 統計的学習理論. 講談社 機械学習プロフェッショナルシリーズ.
[Mohri et al. (2012)] Mohri, M.; Rostamizadeh, A.; and Talwalkar, A. 2012. Foundations of Machine Learning. MIT Press.