Размерность Вапника — Червоненкиса

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

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

Пусть задано множество ${\displaystyle X}$ и некоторое семейство индикаторных функций (алгоритмов классификации, решающих правил) ${\displaystyle {\mathcal {F}}=\{f(x,\alpha )\}}$, где ${\displaystyle x\in X}$ — аргумент функций, ${\displaystyle \alpha }$ — вектор параметров, задающий функцию. Каждая такая функция ${\displaystyle f(x,\alpha )}$ сопоставляет каждому элементу множества ${\displaystyle X}$ один из двух заданных классов. VC-размерностью семейства ${\displaystyle {\mathcal {F}}}$ называется наибольшее число ${\displaystyle h}$, такое, что существует подмножество из ${\displaystyle h}$ элементов множества ${\displaystyle X}$, которые функции из ${\displaystyle {\mathcal {F}}}$ могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого ${\displaystyle h}$, то VC-размерность полагается равной бесконечности.

VC-размерность можно обобщить и на случай семейства функций ${\displaystyle \{g(x,\alpha )\}}$, принимающих действительные значения. Его VC-размерность определяется как VC-размерность семейства индикаторных функций ${\displaystyle \{I(g(x,\alpha )>\beta )\}}$, где ${\displaystyle \beta }$ пробегает область значений функций ${\displaystyle g}$.^[1]

Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (${\displaystyle 2^{3}=8}$ способами, на рисунке ниже показаны три из них), но множества из четырёх и более точек — уже нет. Поэтому VC-размерность линейного классификатора на плоскости равна трём.

Примеры разделения трёх точек на два класса			Разделение невозможно для этих четырёх точек

В общем случае, VC-размерность линейных классификаторов в ${\displaystyle n}$-мерном пространстве равна ${\displaystyle n+1}$.

• Метод опорных векторов

• Информация с сайта www.machinelearning.ru