Размерность Вапника-Червоненкиса
Материал из MachineLearning.
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Размерность Вапника-Червоненкиса (ёмкость, VC-dimension) —
Содержание |
Определение
Если существует число такое, что функция роста
и
, то оно
называется ёмкостью или размерностью Вапника-Червоненкиса (VC-dimension) семейства алгоритмов
. Если такого числа
не существует, то говорят, что семейство
имеет бесконечную ёмкость.
Другая формулировка определения (через разнообразие): Пусть задано множество объектов и некоторое семейство функций (алгоритмов классификации, решающих правил)
, которые сопоставляют каждому объекту множества
один из двух заданных классов. Ёмкостью семейства
называется наибольшее число
, такое, что существует подмножество из
объектов в множестве
, которое функции из
могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого
, то ёмкость полагается равной бесконечности.
Если семейство алгоритмов имеет конечную размерность Вапника-Червоненкиса, то такое семейство называют классом Вапника-Червоненкиса.
Примеры
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (2³ = 8 способами, на рисунке ниже показаны два из них), но множества из четырёх и более точек — уже нет. Поэтому размерность Вапника-Червоненкиса линейного классификатора на плоскости равна трём.
| 
| 
|
| Примеры разделения трёх точек на два класса | Разделение невозможно для этих четырёх точек | |
В общем случае, размерность Вапника-Червоненкиса семейства линейных классификаторов в n-мерном пространстве равна n + 1.
Связь с размером обучающей выборки
Литература
- Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974.
- A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. "Learnability and the Vapnik–Chervonenkis dimension." Journal of the ACM, 36(4):929–865, 1989.
