Русская Википедия:Размерность Вапника — Червоненкиса
Размерность Вапника — Червоненкиса или VC-размерность — это характеристика семейства алгоритмов для решения задачи классификации с двумя классами, характеризующая сложность или ёмкость этого семейства. Это одно из ключевых понятий в теории Вапника-Червоненкиса о статистическом машинном обучении, названное в честь Владимира Вапника и Алексея Червоненкиса.
Сами Вапник и Червоненкис предпочитают называть эту величину комбинаторной размерностью, так как выяснилось, она была известна алгебраистам еще до открытия их теории машинного обучения.
Определение
Пусть задано множество <math>X</math> и некоторое семейство индикаторных функций (алгоритмов классификации, решающих правил) <math>\mathcal{F} = \{ f(x, \alpha) \}</math>, где <math>x \in X</math> — аргумент функций, <math>\alpha</math> — вектор параметров, задающий функцию. Каждая такая функция <math>f(x, \alpha)</math> сопоставляет каждому элементу множества <math>X</math> один из двух заданных классов. VC-размерностью семейства <math>\mathcal{F}</math> называется наибольшее число <math>h</math>, такое, что существует подмножество из <math>h</math> элементов множества <math>X</math>, которые функции из <math>\mathcal{F}</math> могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого <math>h</math>, то VC-размерность полагается равной бесконечности.
VC-размерность можно обобщить и на случай семейства функций <math>\{ g(x, \alpha) \}</math>, принимающих действительные значения. Его VC-размерность определяется как VC-размерность семейства индикаторных функций <math>\{ I(g(x, \alpha) > \beta) \}</math>, где <math>\beta</math> пробегает область значений функций <math>g</math>.[1]
Примеры
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (<math>2^3 = 8</math> способами, на рисунке ниже показаны три из них), но множества из четырёх и более точек — уже нет. Поэтому VC-размерность линейного классификатора на плоскости равна трём.
| Файл:VC1.svg | Файл:VC2.svg | Файл:VC3.svg | Файл:VC4.svg |
| Примеры разделения трёх точек на два класса |
Разделение невозможно для этих четырёх точек | ||
В общем случае, VC-размерность линейных классификаторов в <math>n</math>-мерном пространстве равна <math>n + 1</math>.
См. также
Ссылки
Примечания
Шаблон:Примечания Шаблон:Машинное обучение
