Размерность Вапника-Червоненкиса
Материал из MachineLearning.
(дополнение) |
(дополнение, ссылки) |
||
| Строка 1: | Строка 1: | ||
{{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}} | {{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}} | ||
| - | '''Размерность Вапника-Червоненкиса''' (ёмкость, VC-dimension) — | + | '''Размерность Вапника-Червоненкиса''' (ёмкость, VC-dimension) — это характеристика семейства алгоритмов (или классифицирующих функций) для решения [[Классификация|задачи классификации]], характеризующая сложность или ёмкость этого семейства. Является одним из ключевых понятий в [[Теория Вапника-Червоненкиса|теории Вапника-Червоненкиса]] о статистическом машинном обучении, названа в честь [[Вапник, Владимир Наумович|{{S|В. Н. Вапника}}]] и |
| + | [[Червоненкис, Алексей Яковлевич|{{S|А. Я. Червоненкиса}}]]. | ||
== Определение == | == Определение == | ||
Если существует число <tex>h</tex> такое, что [[Функция роста | функция роста]] <tex>\Delta A(h) = 2^h</tex> и <tex>\Delta A(h+1) < 2^{h+1}</tex>, то оно | Если существует число <tex>h</tex> такое, что [[Функция роста | функция роста]] <tex>\Delta A(h) = 2^h</tex> и <tex>\Delta A(h+1) < 2^{h+1}</tex>, то оно | ||
| Строка 40: | Строка 41: | ||
Таким образом, размерность Вапника-Червоненкиса класса выпуклых d-угольников на плоскости равна 2d + 2. Если рассмотреть класс всевозможных выпуклых многоугольников на плоскости, то получим размерность Вапника-Червоненкиса, равную бесконечности. | Таким образом, размерность Вапника-Червоненкиса класса выпуклых d-угольников на плоскости равна 2d + 2. Если рассмотреть класс всевозможных выпуклых многоугольников на плоскости, то получим размерность Вапника-Червоненкиса, равную бесконечности. | ||
| - | == | + | |
| + | == Некоторые соотношения для размерности Вапника-Червоненкиса == | ||
| + | |||
== Литература == | == Литература == | ||
#{{книга | #{{книга | ||
| Строка 51: | Строка 54: | ||
# 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. | # 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. | ||
| + | == Ссылки == | ||
| + | # {{книга | ||
| + | |автор = Goldman S.A. | ||
| + | |часть = Computational Learning Theory | ||
| + | |заглавие = Washington University, lecture Notes | ||
| + | |год = 1991 | ||
| + | |ссылка = http://www.cs.wustl.edu/~sg/CS527_SP02/learning-theory-notes.pdf | ||
| + | }} | ||
[[Категория:Теория вычислительного обучения]] | [[Категория:Теория вычислительного обучения]] | ||
Версия 20:57, 3 января 2010
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Размерность Вапника-Червоненкиса (ёмкость, VC-dimension) — это характеристика семейства алгоритмов (или классифицирующих функций) для решения задачи классификации, характеризующая сложность или ёмкость этого семейства. Является одним из ключевых понятий в теории Вапника-Червоненкиса о статистическом машинном обучении, названа в честь В. Н. Вапника и
А. Я. Червоненкиса.
Содержание |
Определение
Если существует число такое, что функция роста
и
, то оно
называется ёмкостью или размерностью Вапника-Червоненкиса (VC-dimension) семейства алгоритмов
. Если такого числа
не существует, то говорят, что семейство
имеет бесконечную ёмкость.
Другая формулировка определения (через разнообразие): Пусть задано множество объектов и некоторое семейство функций (алгоритмов классификации, решающих правил)
, которые сопоставляют каждому объекту множества
один из двух заданных классов. Ёмкостью семейства
называется наибольшее число
, такое, что существует подмножество из
объектов в множестве
, которое функции из
могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого
, то ёмкость полагается равной бесконечности.
Если семейство алгоритмов имеет конечную размерность Вапника-Червоненкиса, то такое семейство называют классом Вапника-Червоненкиса.
Примеры
Линейный классификатор
Как пример, рассмотрим задачу о разбиении точек на плоскости на два класса прямой линией — это так называемый линейный классификатор. Множество из любых трёх точек, не лежащих на одной прямой, может быть разделено прямой линией на два класса всеми возможными способами (2³ = 8 способами, на рисунке ниже показаны два из них), но множества из четырёх и более точек — уже нет. Поэтому размерность Вапника-Червоненкиса линейного классификатора на плоскости равна трём.
| 
| 
|
| Примеры разделения трёх точек на два класса | Разделение невозможно для этих четырёх точек | |
В общем случае, размерность Вапника-Червоненкиса семейства линейных классификаторов в n-мерном пространстве равна n + 1.
Отрезки на действительной прямой
Класс алгоритмов - множество отрезков на действительной прямой. Точка, лежащая внутри отрезка, классифицируется положительно, лежащая вне отрезка — отрицательно.
Очевидно, что существует множество, состоящее из двух элементов, разбиваемое классом алгоритмов: любые две различные точки на прямой можно покрыть любым из четырех возможных случаев (покрытие только первой точки, покрытие только второй точки, покрытие двух точек, покрытие пустого множества точек).
Не существует множества из трех точек, которое можно разбить, используя множество отрезков на действительной прямой. Пусть точки упорядочены по значению . Любой отрезок, покрывающий точки
и
, покрывает также и точку
.
Таким образом, размерность Вапника-Червоненкиса множества отрезков на действительной прямой равна 2.
Выпуклые d-угольники на плоскости
Класс алгоритмов — выпуклые многоугольники с d сторонами на плоскости. Точка, лежащая внутри многоугольника, классифицируется положительно, лежащая вне многоугольника — отрицательно.
Сначала покажем, что существует множество из 2d + 1 точек, которые могут быть разбиты с помощью выбранного класса алгоритмов. Расположим 2d + 1 точек равномерно по кругу. Для любой маркировки этих точек можно найти d-угольник, соответствующий маркировке. Если отрицательных точек больше чем положительных, используем положительные точки как вершины вершины d-угольника. Если будет больше положительных точек, используем касательные к отрицательным точкам как стороны d-угольника.
Не существует множества из 2d + 2 точек, которое можно разбить, используя класс выпуклых многоугольников с d сторонами. Очевидно, что для точек, не расположенных на окружности, всевозможные разбиения получить не удастся. Для точек, расположенных на окружности, сделаем пометки, чередуя положительные и отрицательные. Такое множество нельзя разбить любым d-угольником.
Таким образом, размерность Вапника-Червоненкиса класса выпуклых d-угольников на плоскости равна 2d + 2. Если рассмотреть класс всевозможных выпуклых многоугольников на плоскости, то получим размерность Вапника-Червоненкиса, равную бесконечности.
Некоторые соотношения для размерности Вапника-Червоненкиса
Литература
- Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 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.
Ссылки
- Goldman S.A. Computational Learning Theory // Washington University, lecture Notes. — 1991.
