VC-размерность и емкость

Размерность Вапника-Червоненкиса измеряет емкость класса моделей по наибольшему набору точек, который он может разметить всеми возможными способами, количественно определяя сложность обучающегося алгоритма.

Definition

Размерность Вапника-Червоненкиса класса классификаторов — это наибольшее число точек, которые класс может разметить всеми возможными способами; это мера емкости, которая ограничивает, насколько класс может переобучаться, и, следовательно, сколько данных необходимо для надежного обучения.

Scope

Эта тема охватывает меры богатства класса гипотез: понятие разбиения набора точек, размерность Вапника-Червоненкиса как размер наибольшего разбитого набора, функцию роста и то, как эти меры емкости входят в границы обобщения. Она объясняет, почему емкость, а не только количество параметров, определяет способность к обобщению.

Core questions

• Что означает для класса моделей разбивать набор точек?
• Как определяется и вычисляется размерность Вапника-Червоненкиса?
• Почему емкость, а не количество параметров, определяет обобщение?
• Как емкость входит в границы разрыва между ошибкой на обучающей выборке и истинной ошибкой?

Key theories

Разбиение и емкость

Класс разбивает набор точек, если он может реализовать каждую возможную разметку этих точек; наибольший такой набор определяет размерность Вапника-Червоненкиса, меру гибкости класса, не зависящую от распределения.

Емкость контролирует равномерную сходимость

Конечная емкость гарантирует, что эмпирическая ошибка сходится к истинной ошибке равномерно по всему классу, поэтому обучающийся алгоритм с ограниченной размерностью Вапника-Червоненкиса не может произвольно переобучаться по мере роста данных.

Емкость против количества параметров

Емкость, а не сырое количество параметров, определяет обобщение, поэтому две модели с одинаковым количеством параметров могут значительно различаться по объему требуемых данных.

Clinical relevance

Размерность Вапника-Червоненкиса обеспечивает центральную меру емкости классической теории обучения и обосновывает практику контроля сложности модели; она лежит в основе анализа машин опорных векторов, основанного на отступах, и формирует текущие усилия по пониманию того, почему некоторые модели очень высокой емкости, тем не менее, хорошо обобщают.

History

Вапник и Червоненкис ввели размерность, носящую их имена, в работах конца 1960-х годов и в статье 1971 года о равномерной сходимости, создав теорию емкости, не зависящую от распределения. Эта концепция стала основополагающей для машин опорных векторов и для более широкого анализа обобщения.

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

Что означает разбиение (shattering)?

Набор точек разбивается классом моделей, если для каждого возможного присвоения меток этим точкам некоторая модель в классе производит именно такую разметку. Размер наибольшего разбиваемого набора является размерностью Вапника-Червоненкиса.

Всегда ли модель с большим количеством параметров имеет более высокую емкость?

Не обязательно. Емкость измеряется размерностью Вапника-Червоненкиса или связанными величинами, которые могут отличаться от количества параметров. Правильной мерой сложности для обобщения является емкость, а не просто количество параметров у модели.