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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Размерность Вапника — Червоненкиса или 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-размерность линейного классификатора на плоскости равна трём.

VC1.svg VC2.svg VC3.svg VC4.svg
Примеры разделения трёх
точек на два класса
Разделение невозможно
для этих четырёх точек

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

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Hastie, T., Tibshirani R., Friedman J. Chapter 7.9. Vapnik–Chervonenkis Dimension // The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0.