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

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

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

Определение [править]

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

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

Примеры [править]

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


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