VC次元と容量

ヴァプニク・チェルヴォネンキス次元は、モデルクラスが可能なすべての方法でラベル付けできる点の最大集合によってその容量を測定し、学習器の複雑さを定量化する。

Definition

分類器のクラスのヴァプニク・チェルヴォネンキス次元とは、そのクラスが可能なすべての方法でラベル付けできる点の最大数である。これは、クラスがどの程度過学習しうるか、したがって信頼性のある学習にどの程度のデータが必要かを示す容量の尺度である。

Scope

このトピックでは、仮説クラスの豊かさの尺度について扱う。すなわち、点集合をシャタリングするという概念、最大シャタリング集合のサイズとしてのヴァプニク・チェルヴォネンキス次元、成長関数、そしてこれらの容量尺度がどのように汎化限界に関与するかについてである。また、パラメータ数だけではなく容量が汎化能力を決定する理由についても説明する。

Core questions

• モデルクラスが点集合をシャタリングするとはどういう意味か？
• ヴァプニク・チェルヴォネンキス次元はどのように定義され、計算されるか？
• なぜパラメータ数ではなく容量が汎化を決定するのか？
• 容量は訓練誤差と真の誤差の間のギャップの限界にどのように関与するか？

Key theories

シャタリングと容量

クラスが点集合をシャタリングするとは、その点の可能なすべてのラベル付けを実現できる場合を指す。このような最大の集合がヴァプニク・チェルヴォネンキス次元を定義し、これはクラスの柔軟性を示す分布によらない尺度である。

容量は一様収束を制御する

有限の容量は、経験的誤差がクラス全体で一様に真の誤差に収束することを保証するため、ヴァプニク・チェルヴォネンキス次元が有界な学習器は、データが増加しても任意に過学習することはない。

容量とパラメータ数

汎化を決定するのは、パラメータの生数ではなく容量であるため、同じパラメータ数を持つ2つのモデルでも、必要とするデータ量には大きな違いが生じうる。

Clinical relevance

ヴァプニク・チェルヴォネンキス次元は、古典的な学習理論における中心的な容量尺度を提供し、モデルの複雑さを制御する実践を正当化する。これはサポートベクターマシンのマージンベースの分析の基礎となり、一部の非常に高容量なモデルがそれでもなお汎化する理由を理解するための継続的な取り組みを枠組み化する。

History

ヴァプニクとチェルヴォネンキスは、1960年代後半の研究と1971年の均一収束に関する論文において、彼らの名を冠した次元を導入し、分布によらない容量の理論を確立した。この概念は、サポートベクターマシンおよび汎化のより広範な分析の基礎となった。

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

シャタリングとは何を意味するのか？

点集合がモデルクラスによってシャタリングされるとは、それらの点へのラベルの可能なすべての割り当てに対して、そのクラス内の何らかのモデルが正確にそのラベル付けを生成する場合を指す。シャタリング可能な最大の集合のサイズがヴァプニク・チェルヴォネンキス次元である。

パラメータが多いモデルは常に容量が高いのか？

必ずしもそうではない。容量はヴァプニク・チェルヴォネンキス次元または関連する量によって測定され、これらはパラメータ数とは異なる場合がある。汎化のための複雑さの適切な尺度は、単にモデルが持つパラメータの数ではなく、容量である。