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

Материал из MachineLearning.

Перейти к: навигация, поиск
Данная статья является непроверенным учебным заданием.
Студент: Участник:DmitryKonstantinov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


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

Содержание

Определение

Если существует число h такое, что функция роста \Delta A(h) = 2^h и \Delta A(h+1) < 2^{h+1}, то оно называется ёмкостью или размерностью Вапника-Червоненкиса (VC-dimension) семейства алгоритмов A. Если такого числа h не существует, то говорят, что семейство A имеет бесконечную ёмкость.

Другая формулировка определения (через разнообразие): Пусть задано множество объектов X и некоторое семейство функций (алгоритмов классификации, решающих правил) A, которые сопоставляют каждому объекту множества X один из двух заданных классов. Ёмкостью семейства A называется наибольшее число h, такое, что существует подмножество из h объектов в множестве X, которое функции из A могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого h, то ёмкость полагается равной бесконечности.

Если семейство алгоритмов имеет конечную размерность Вапника-Червоненкиса, то такое семейство называют классом Вапника-Червоненкиса.

Примеры

Линейный классификатор

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

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

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

Отрезки на действительной прямой

Класс алгоритмов - множество отрезков на действительной прямой. Точка, лежащая внутри отрезка, классифицируется положительно, лежащая вне отрезка — отрицательно.

Очевидно, что существует множество, состоящее из двух элементов, разбиваемое классом алгоритмов: любые две различные точки на прямой можно покрыть любым из четырех возможных случаев (покрытие только первой точки, покрытие только второй точки, покрытие двух точек, покрытие пустого множества точек).

Не существует множества из трех точек, которое можно разбить, используя множество отрезков на действительной прямой. Пусть точки упорядочены по значению x_1 < x_2 < x_3. Любой отрезок, покрывающий точки x_1 и x_3, покрывает также и точку x_2.

Таким образом, размерность Вапника-Червоненкиса множества отрезков на действительной прямой равна 2.

Выпуклые d-угольники на плоскости

Класс алгоритмов — выпуклые многоугольники с d сторонами на плоскости. Точка, лежащая внутри многоугольника, классифицируется положительно, лежащая вне многоугольника — отрицательно.

Сначала покажем, что существует множество из 2d + 1 точек, которые могут быть разбиты с помощью выбранного класса алгоритмов. Расположим 2d + 1 точек равномерно по кругу. Для любой маркировки этих точек можно найти d-угольник, соответствующий маркировке. Если отрицательных точек больше чем положительных, используем положительные точки как вершины вершины d-угольника. Если будет больше положительных точек, используем касательные к отрицательным точкам как стороны d-угольника.

Не существует множества из 2d + 2 точек, которое можно разбить, используя класс выпуклых многоугольников с d сторонами. Очевидно, что для точек, не расположенных на окружности, всевозможные разбиения получить не удастся. Для точек, расположенных на окружности, сделаем пометки, чередуя положительные и отрицательные. Такое множество нельзя разбить любым d-угольником.

Таким образом, размерность Вапника-Червоненкиса класса выпуклых d-угольников на плоскости равна 2d + 2. Если рассмотреть класс всевозможных выпуклых многоугольников на плоскости, то получим размерность Вапника-Червоненкиса, равную бесконечности.

Некоторые соотношения для размерности Вапника-Червоненкиса

Предполагается, что все классы алгоритмов содержат алгоритмы классификации на два класса и действуют на одном множестве объектов.

  • Если A_1 \subseteq A_2, то VCD(A_1) \leq VCD(A_2)
  • |A| \geq 2^{VCD(A)}
  • Пусть A = A_1 \cup A_2, тогда VCD(A) \leq VCD(A_1) + VCD(A_2) + 1
  • A_s = \{\bigcup_{i=1}^s a_i | a_i \in A\}, тогда VCD(A_s) = O(VCD(A) s \ln(s))

Литература

  1. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974.
  2. 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.

Ссылки

  1. Goldman S.A. Computational Learning Theory // Washington University, lecture Notes. — 1991.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%92%D0%B0%D0%BF%D0%BD%D0%B8%D0%BA%D0%B0-%D0%A7%D0%B5%D1%80%D0%B2%D0%BE%D0%BD%D0%B5%D0%BD%D0%BA%D0%B8%D1%81%D0%B0»