仮説集合の複雑度#
VC次元#
VC次元 (VC dimension) は仮説集合の複雑度の指標の一つ。 主に2値判別問題の仮説集合に用いられるが、多値判別問題や回帰問題に拡張することも可能。 名前の由来は理論の創始者であるVapnikとChervonenkisから。
2値判別のための仮説集合を
の要素数を
とおく(英語だとGrowth Functionと呼ばれる様子)。
定義より
である。
入力の数
数式的には、
と定義される。また、任意の
VC次元は言葉で説明すると「仮説集合
例:step function#
1直線上に並ぶ点で、step functionのようにラベルが変化する(positive raysと呼ばれる?)なら、1つの点で分離できる。
Growth functionは

例:intervals#
1直線上で、ある区間だけ
Growth functionは
となり、

例:3点#
一直線上にない3点までなら、1つの直線でグループを2つに分けられる。4点になると分けられないものが出てくる(線形分離不可能問題)
サウアーの補題#
サウアーの補題(Sauer’s lemma)
2 値ラベルに値をとる仮説集合
が成り立つ。 ここで
VC次元と予測誤差の関係#
定理
2 値ラベルに値をとる仮説集合
が成り立つ。
この定理の証明にはラデマッハ複雑度による一様大数の法則が用いられる。
学習データ
が常に成り立つ。そして以下が成り立つ
(以下は金森(2015)のp.22の式展開を想像で補ったりしたもの)
確率オーダーで表現すると
となり、予測誤差はデータ数とVC次元の比
PAC学習との関係#
VC次元は、PAC学習の理論を仮説集合が有限でない場合にも拡張する際に登場する指標らしい(VC次元の意味と例 - 具体例で学ぶ数学)