- Размерность Вапника
-
Размерность Вапника — Червоненкиса или VC-размерность — это характеристика семейства алгоритмов для решения задачи классификации с двумя классами, характеризующая сложность или ёмкость этого семейства. Это одно из ключевых понятий в теории Вапника-Червоненкиса о статистическом машинном обучении, названное в честь Владимира Вапника и Алексея Червоненкиса.
Сами Вапник и Червоненкис предпочитают называть эту величину комбинаторной размерностью, так как, как выяснилось, она была известна алгебраистам еще до открытия их теории машинного обучения.
Содержание
Определение
Пусть задано множество
и некоторое семейство индикаторных функций (алгоритмов классификации, решающих правил)
, где
— аргумент функций,
— вектор параметров, задающий функцию. Каждая такая функция
сопоставляет каждому элементу множества
один из двух заданных классов. VC-размерностью семейства
называется наибольшее число
, такое, что существует подмножество из
элементов множества
, которые функции из
могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого
, то VC-размерность полагается равной бесконечности.
VC-размерность можно обобщить и на случай семейства функций
, принимающих действительные значения. Его VC-размерность определяется как VC-размерность семейства индикаторных функций
, где
пробегает область значений функций
.[1]
Примеры
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (
способами, на рисунке ниже показаны три из них), но множества из четырёх и более точек — уже нет. Поэтому VC-размерность линейного классификатора на плоскости равна трём.
Примеры разделения трёх
точек на два классаРазделение невозможно
для этих четырёх точекВ общем случае, VC-размерность линейных классификаторов в
-мерном пространстве равна
.
Ссылки
Примечания
- ↑ 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.
Категория:- Машинное обучение
Wikimedia Foundation. 2010.