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

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

(Различия между версиями)
Перейти к: навигация, поиск
(дополнение, иллюстрации, литература)
(дополнение)
Строка 9: Строка 9:
Если семейство алгоритмов имеет конечную размерность Вапника-Червоненкиса, то такое семейство называют классом Вапника-Червоненкиса.
Если семейство алгоритмов имеет конечную размерность Вапника-Червоненкиса, то такое семейство называют классом Вапника-Червоненкиса.
== Примеры ==
== Примеры ==
-
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (2³ = 8 способами, на рисунке ниже показаны два из них), но множества из четырёх и более точек — уже нет. Поэтому размерность Вапника-Червоненкиса линейного классификатора на плоскости равна трём.
+
=== Линейный классификатор ===
 +
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый [[Линейный классификатор|линейный классификатор]]. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (2³ = 8 способами, на рисунке ниже показаны два из них), но множества из четырёх и более точек — уже нет. Поэтому размерность Вапника-Червоненкиса линейного классификатора на плоскости равна трём.
{| border="0" cellpadding="4" cellspacing="0" align="center"
{| border="0" cellpadding="4" cellspacing="0" align="center"
Строка 22: Строка 23:
В общем случае, размерность Вапника-Червоненкиса семейства линейных классификаторов в n-мерном пространстве равна n + 1.
В общем случае, размерность Вапника-Червоненкиса семейства линейных классификаторов в n-мерном пространстве равна n + 1.
 +
=== Отрезки на действительной прямой ===
 +
Класс алгоритмов - множество отрезков на действительной прямой. Точка, лежащая внутри отрезка, классифицируется положительно, лежащая вне отрезка — отрицательно.
 +
Очевидно, что существует множество, состоящее из двух элементов, разбиваемое классом алгоритмов: любые две различные точки на прямой можно покрыть любым из четырех возможных случаев (покрытие только первой точки, покрытие только второй точки, покрытие двух точек, покрытие пустого множества точек).
 +
 +
Не существует множества из трех точек, которое можно разбить, используя множество отрезков на действительной прямой. Пусть точки упорядочены по значению <tex>x_1 < x_2 < x_3</tex>. Любой отрезок, покрывающий точки <tex>x_1</tex> и <tex>x_3</tex>, покрывает также и точку <tex>x_2</tex>.
 +
 +
Таким образом, размерность Вапника-Червоненкиса множества отрезков на действительной прямой равна 2.
 +
=== Выпуклые d-угольники на плоскости ===
 +
Класс алгоритмов — выпуклые многоугольники с d сторонами на плоскости. Точка, лежащая внутри многоугольника, классифицируется положительно, лежащая вне многоугольника — отрицательно.
 +
 +
Сначала покажем, что существует множество из 2d + 1 точек, которые могут быть разбиты с помощью выбранного класса алгоритмов. Расположим 2d + 1 точек равномерно по кругу. Для любой маркировки этих точек можно найти d-угольник, соответствующий маркировке. Если отрицательных точек больше чем положительных,
 +
используем положительные точки как вершины вершины d-угольника. Если будет больше положительных точек, используем касательные к отрицательным точкам как стороны d-угольника.
 +
 +
Не существует множества из 2d + 2 точек, которое можно разбить, используя класс выпуклых многоугольников с d сторонами. Очевидно, что для точек, не расположенных на окружности, всевозможные разбиения получить не удастся. Для точек, расположенных на окружности, сделаем пометки, чередуя положительные и отрицательные. Такое множество нельзя разбить любым d-угольником.
 +
 +
Таким образом, размерность Вапника-Червоненкиса класса выпуклых d-угольников на плоскости равна 2d + 2. Если рассмотреть класс всевозможных выпуклых многоугольников на плоскости, то получим размерность Вапника-Червоненкиса, равную бесконечности.
== Связь с размером обучающей выборки ==
== Связь с размером обучающей выборки ==
== Литература ==
== Литература ==

Версия 20:26, 3 января 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник: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. Если рассмотреть класс всевозможных выпуклых многоугольников на плоскости, то получим размерность Вапника-Червоненкиса, равную бесконечности.

Связь с размером обучающей выборки

Литература

  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.
Личные инструменты