- 追加された行はこの色です。
- 削除された行はこの色です。
- VC次元 へ行く。
*VC次元 (Vapnik-Chervonenkis dimension) [#s5c9c82f]
バイナリ関数のクラスが点集合をshatterするとは，バイナリのラベルをそれらの点にどのようにつけても，それらの点を分離するような関数がそのクラスに含まれること．
\(n\)個の点であれば，任意の点の配置とラベル付けに対して，shatterできるような関数がクラスに含まれるが，それ以上点を増やすとshatterできなくなる場合があるとき，その関数クラスのVC次元は \(n\)．
> -- しましま
汎化誤差を評価するために導入された学習機械の複雑さを表す指標．~
なんでこんなものを導入したかというと．．．~
汎化誤差と経験誤差との違いを評価する際に，学習機械のパラメータ \(\theta\) を固定すれば
（つまり正解を知っていれば）大数の法則が使えるが，真の \(\theta\) は知らないので，
その違いをまず \(\theta\) に関する最大値(sup)でバウンドし，その次に最大値(sup)を，全部の \(\theta\) に関する場合の数だけの和で置き換える． これはサンプル数を \(n\) とすると，バイナリ損失の場合最大 \(2^n\) 通りあって，そのままでは \(n\) が増えると和を取る数も指数的に増えてしまう． ところが，もし学習機械のVC 次元 \(h\) が有限ならこれは \(O(n^h)\) という \(n\) の多項式でバウンドされ，より少ない数の場合の数の和となる．
結果として，汎化誤差と経験誤差の差は \(h\) が小さいほど小さくなる． 連続関数のクラスの場合の VC 次元も基本的にバイナリ関数の VC 次元に帰着して定義される．
> --あかほ
**関連項目 [#u346e414]
-[[VC dimension]]
-[[Vapnik-Chervonenkis dimension]]
#br
-[[VCエントロピー]]
-[[Chernoff限界]]
-[[Hoeffdingの不等式]]
-[[極限定理]]
-[[次元の呪い]]
-[[SVM]]
-[[マージン]]
-[[構造的損失最小化]]
#br
-[[検索:VC次元 Vapnik-Chervonenkis次元]]
** リンク集 [#re40297a]
-[[VC dimension>http://www.autonlab.org/tutorials/vcdim.html]] @ Andrew Moore
#br
-[[Wikipedia:VC_dimension]]
** 関連文献 [#xad8d2bf]
-[[Book/サポートベクターマシン(知の科学)]] 6.2節
-[[Book/Pattern Recognition and Machine Learning]] 7.1.5章
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
