Разнообразие
Материал из MachineLearning.
м (оформление) |
м (литература) |
||
Строка 11: | Строка 11: | ||
Рассмотрим задачу классификации на два класса. Пусть множество <tex>X</tex> — множество объектов; <tex>Y = \{0,1\}</tex> - множество ответов; класс множеств <tex>C</tex> — класс алгоритмов, множество целевых функций вида <tex>X \rightarrow Y</tex>; <tex>X^L</tex> — подмножество <tex>X</tex> мощности <tex>L</tex>. Класс алгоритмов <tex>C</tex> имеет многообразие <tex>X^L</tex> (разбивает <tex>X^L</tex>), если для любого подмножества <tex>T</tex> множества <tex>X^L</tex> существует алгоритм из класса <tex>C</tex>, отделяющий объекты из <tex>T</tex> от объектов из <tex>X^L\setminus T</tex>. | Рассмотрим задачу классификации на два класса. Пусть множество <tex>X</tex> — множество объектов; <tex>Y = \{0,1\}</tex> - множество ответов; класс множеств <tex>C</tex> — класс алгоритмов, множество целевых функций вида <tex>X \rightarrow Y</tex>; <tex>X^L</tex> — подмножество <tex>X</tex> мощности <tex>L</tex>. Класс алгоритмов <tex>C</tex> имеет многообразие <tex>X^L</tex> (разбивает <tex>X^L</tex>), если для любого подмножества <tex>T</tex> множества <tex>X^L</tex> существует алгоритм из класса <tex>C</tex>, отделяющий объекты из <tex>T</tex> от объектов из <tex>X^L\setminus T</tex>. | ||
+ | == Литература == | ||
+ | # Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):929-965, October 1989. | ||
[[Категория:Теория вычислительного обучения]] | [[Категория:Теория вычислительного обучения]] |
Версия 17:59, 3 января 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Концепция разнообразия играет важную роль в теории Вапника-Червоненкиса. Разнообразие класса связано с такими ключевыми понятиями, как коэффициент разнообразия, функция роста, размерность Вапника-Червоненкиса.
Разнообразие класса
Пусть имеются - класс множеств и некоторое множество
. Говорят, что
имеет разнообразие
(
to shatter
), если для любого подмножества
существует
такой, что
.
Альтернативная формуровка: имеет разнообразие
, если
— булеан (множество всех подмножеств) совпадает с множеством
.
Пример: класс — класс полуплоскостей плоскости,
— множество из произвольных 4 точек на плоскости.
не имеет разнообразия
, поскольку всегда можно выбрать такие две точки из множества 4 точек на плоскости, что нельзя отделить эти две точки от оставшихся двух с помощью ограничивающей полуплоскость прямой.
Рассмотрим задачу классификации на два класса. Пусть множество — множество объектов;
- множество ответов; класс множеств
— класс алгоритмов, множество целевых функций вида
;
— подмножество
мощности
. Класс алгоритмов
имеет многообразие
(разбивает
), если для любого подмножества
множества
существует алгоритм из класса
, отделяющий объекты из
от объектов из
.
Литература
- Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):929-965, October 1989.