PAC学習とVC理論

お久しぶりです、ロードローラーです。最近は7月のICMLに参加すべく勉強の日々を過ごしています。

ディープラーニングをあれこれとやって知ったつもりになっていましたが、ディープラーニングは機械学習の一部でしかなく(さらに言うならニューラルネットワーク手法の1つでしかない)、まだまだ勉強することは山のようにあります。

そんな中で、本日は機会学習のPAC学習とVC理論を調べました


PAC学習

参考サイト:朱鷺の杜Wiki

パラメータ:入力の誤差 ϵ,信頼度 δ,学習する概念の複雑さの上限 s

学習する概念についてのエラーがたかだか ϵ である確率が 1δ より大きくなるような仮説を出力できるアルゴリズムが存在するとき PAC学習可能 (probably approximately correct learnable). こうした学習問題を扱うのがPAC学習 (probably approximately correct learning)

さらに,1/ϵ1/δs について,計算時間が多項式時間で抑えられるとき,多項式時間PAC学習可能であるという.


こちらでもわかりやすくまとめられています

 

~要約~

PAC学習のモチベーションは『 まぁまぁ良い学習をするためにどの程度学習データが必要か見定めたい 』こと。

仮説集合𝐻(≒分類モデル)において『汎化誤差が𝜖より大きい,かつ,ℓ個の訓練データ に無矛盾な仮説を選択してしまう確率を𝛿以下に抑 えたい』とき、すなわち危険率𝛿以下で汎化誤差が 高々𝜖の仮説を学習するために必要な訓練デー タは次の式で求められる

問題点が2つあり、1つ目は思った以上に非常に大きい数値が算出されてしまうこと、2つ目は仮説集合𝐻(≒分類モデル)が無限の場合に対応できないこと。

実際問題、パラメータ数次第で分類モデルの構築方法は無限に考えられるので(だからパラメータチューニングが難しい)、仮説集合Hが有限となるシチュエーションは限られています。


VC次元による問題解決

仮説集合Hが有限でなければ先ほどの計算式のうち|H|が∞となり、必要な訓練データ数ℓも∞に発散してしまいます。そこでVC次元という考えを導入して、仮説集合HではなくVC次元数dによって下記式から必要な訓練データ数にあたりをつけます。

さて、それではVC次元とは何なのか??朱鷺の杜Wikiに再登場して頂きましょう。勝手に私が要約した内容が以下です。

・shatterするとは,点集合のそれぞれの点にどのようにラベルをつけても,それらの点を分離するような関数(≒分類モデル)がその仮説集合𝐻に含まれること.

・n個の点に対して,任意の配置とラベルであってもshatterできるような関数があり、それ以上点を増やすとshatterできなくなるとき,その関数(≒分類モデル)のVC次元は n.


ICML2017でも研究対象に

パラメータ再利用の転移学習時のリスクを算出するために、PAC学習やVC次元が利用された研究があったようです。

論文:
Risk Bounds for Transferring Representations With and Without Fine-Tuning

ちょっと理解するのが難しそうなので、これはまた今度で・・・・←

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください